Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

HuffmanTable* stuff needs an overhaul #148

Open
LebedevRI opened this issue Oct 16, 2018 · 1 comment
Open

HuffmanTable* stuff needs an overhaul #148

LebedevRI opened this issue Oct 16, 2018 · 1 comment

Comments

@LebedevRI
Copy link
Member

It's still too tightly coupled.
There are two things there:

  1. Generating Codes/Symbols as specified by JPEG spec
  2. Using some symbol table* to perform decoding
    It isn't necessary that said symbol table actually contains Huffman Codes as per JPEG spec,
    it only needs to satisfy the rules*
  • strict total ordering, no two codes have the same prefix
LebedevRI added a commit to LebedevRI/rawspeed that referenced this issue Oct 29, 2018
This is basically a direct resurrection (copy of relevant pieces) from
* RawSpeed/NikonDecompressor.{h,cpp}
* RawSpeed/LJpegDecompressor.{h,cpp}
back from it's state as of v3.0 tag,
when the support for Nikon Lossy After Split raws was working fine...

This will clearly need to undergo all the same evolution
as the other code did, and probably be deduplicated back after darktable-org#148.

But for now, a (long-overdue, almost 2 years) fix for a regression
is more important than horrible duplicated code.

This is indeed a second attempt.
I did this initially back during 2891a92
but introduced a bug (that was later fixed by 1f42e28)
which was causing mis-decoding, so i abandoned the initial attempt...

Fixes darktable-org#129.
Refs. darktable-org#100.
Refs. https://redmine.darktable.org/issues/12209
@LebedevRI
Copy link
Member Author

Some more unstructured minddumps, after staring at all that code for some time:

  • There are three ways to acquire code symbols:
    • The "smart" algo like in AbstractHuffmanTable::generateCodeSymbols()
    • The obviously-correct algo as in HuffmanTableTree
    • They could be pre-generated and provided
      • I strongly suspect VC5 codes fall in this category.
        They can't be decomposed into nCodesPerLen+codeValues,
        because while those seem to be correct code symbols (no two codes have the same prefix),
        IIRC they aren't properly "sorted", i.e. the algo used for the symbol generation is different.
  • All these HuffmanTable implementations strongly assume that value is a bit length.
    • Thus, they strongly insist that said value should be less than 16
      This assumption doesn't hold for:
      • CRW
      • Nikon Lossy-After-Split
      • VC5
    • BUT they already have a mode when they only decode the value (decodeLength())

It seems to me there are more layers of abstractions that are missing:

  • The base class AbstractHuffmanTable should be templated on a templated CodeSymbol:
    • variant 1 - current "LJPEG":
      ushort16 code;   // the code (bit pattern found inside the stream)
      uchar8 code_len; // the code length in bits, valid values are 1..16
    • variant 2 - "VC5":
      ushort32 code; // VC5 max code length is 26
      uchar8 code_len;
  • Given that we can't always just always call the setNCodesPerLenght(), it seems
    there should be a base class that would handle the generation of code symbols,
    with two options being available in API:
    • Generate the symbols from nCodesPerLenght
    • Use provided vector of pre-generated symbols.
  • All the HuffmanTable impls shouldn't have a fullDecode param to setup() / decode(),
    which specifies whether value is length to get and sign-extend, or just some value, but instead
    that should be a template param over the whole HuffmanTable{LUT,Lookup,Tree} class.
    And more importantly, that template param should not be just a boolean, but yet another
    class-to-help-with-abstractions.
  • HuffmanTableLUT should too be templated even further.
    It is not nice just how much logic of that LUT is hidden/scattered through that class.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant