Results 1 to 5 of 5

Thread: Questions on range encoder implementation

  1. #1
    Member
    Join Date
    Mar 2012
    Location
    Ukraine
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Questions on range encoder implementation

    Hi!

    I'm trying to implement a simple range encoder and despite lots of material on the Net on this topic, I start feeling that I'm getting lost. There are lots of examples, all of them different and lots of implementation choices nearly in every line one would wright down.

    So, I would appreciate very much if anybody could answer some of my questions:

    First of all I've chosen one implementation to follow: "Range Encoder" by Arturo Campos, just because it was mentioned in the Arithmetic Coding tutorial which I'm following.

    My concern is primarily about compression ratio and then about the speed. The speed is very important too, but not at the expense of any significant compression ratio losses.

    So, the Q.1 is - if my choice was right at all (rate coding instead of simple arithmetic coding, and Arturo Campos implementation as a reference)

    As for theory and practice, I understand everything except encoder renormalize phase. I have so many questions here that I don't even know where to start. Lets start from the beginning:

    Question 2: Range initialization value:

    In Campos' code the range initial value is 0x80000000. In some other implementations I've walked through init values are something like DWORD(-1), which is 0xFFFFFFFF. Both options have no sense to me. As far as I understand we decide to work with 32bit integers without last bit to prevent overflow. What would make sense here is something like 0x7FFFFFFF - the largest 31bit number. Why 0x80000000? Why 0xFFFFFFFF?...


    The other questions are about the code. Here it is:

    Encoder renormalize:
    • While ( range <= Bottom_value ) As long as it's not above than Bottom_value (it means we can still output)
      • if ( low < ( 0FFh << Shift_bits ) ) If higher part is 0FFh a carry will occur which we can't afford
      • Yes We had a range with a potential carry (which we can't capture with our precision)
        • Output_byte ( buffer ) Output the byte
        • For ( ; help != 0 ; --help ) Output all underflow bytes pending for output
          • Output_byte ( 0FFh )
        • Buffer = low >> Shift_bits Assign to the byte to output the high bytes of low
      • No Now check for actual carry
        • if ( ( low And Top_value) != 0) Check carry bit
        • Yes
          • Output_byte ( buffer + 1 ) The +1 comes from the carry which propagates till the byte saved
          • For ( ; help != 0 ; --help ) Output all underflow bytes pending for output
            • Output_byte ( 00h ) 0FFh's become 0's (the carry!)
          • Buffer = low >> Shift_bits Assign to the byte to output the high bytes of low
        • No
          • ++Buffer
      • Range << 8 Shift out byte which we have already outputted or are going to be outputted (in case of 0FFh)
      • Low << 8
      • Low And ( Top_value - 1 ) Clear carry bit
      • Repeat


    Question 3:
    the loop condition.

    In wikipedia article on Range encoding, the loop condition is written like this:

    // check if left-most digit is same throughout range
    while (low / 10000 == (low + range) / 10000)

    I do understand what happens here: for all further (low, range) values that we will get in further iterations the first digit will stay the same and hence we can output it already, etc... I suspect that this: While ( range <= Bottom_value ) has to mean the same, but I really don't understand why. The Bottom_value is 0x00800000.

    Question 4: The overflow and underflow and handling of them

    The most dark part for me. As I understand, we can get two situations when iterating low and range, each of which we have to handle exceptionally:

    a) Overflow: when low + new_value will become more than 0x7FFFFFFF. Then we have to handle it somehow.
    b) Undeflow: when low and range become so close to each other that there is no more bits left between them to represent the interval and thus continue iterations.

    So, I absolutely don't understand how these situations are handled in inner if ( low < ( 0FFh << Shift_bits ) ) { ... } branch and why does it look like this. Could anyone explain?

    Thank you in advance,
    Ilya.
    Last edited by ilya; 16th March 2012 at 19:52.

  2. #2
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,257
    Thanks
    307
    Thanked 797 Times in 489 Posts
    Is this for coding bits or for a larger alphabet?

  3. #3
    Member
    Join Date
    Mar 2012
    Location
    Ukraine
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts
    This is for alphabet of size 2^15

  4. #4
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,257
    Thanks
    307
    Thanked 797 Times in 489 Posts
    Maybe try the carryless range coder from PPMd? I think if the range crosses a byte boundary that wouldn't let you normalize then you throw away part of the range.

  5. #5
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,982
    Thanks
    298
    Thanked 1,309 Times in 745 Posts
    > There are lots of examples, all of them different and lots of
    > implementation choices nearly in every line one would wright down.

    Yeah, but in fact lots of these choices affect the coder properties
    (like max speed with specific precision of symbol probabilities,
    coder/decoder delay, support for >binary alphabets etc - there's lot
    more to it than just speed and compression).

    > First of all I've chosen one implementation to follow: "Range
    > Encoder" by Arturo Campos, just because it was mentioned in the
    > Arithmetic Coding tutorial which I'm following.

    I'd suggest http://www.ctxmodel.net/rem.pl?-37
    http://encode.su/threads/1153-Simple...angecoder-demo

    Overall, it seems that "compression scene" and "official" sources
    (books, academic papers etc) are especially out of sync on this topic.

    > My concern is primarily about compression ratio and then about the speed.
    > The speed is very important too, but not at the expense of any
    > significant compression ratio losses.

    Ok, but actually with current cpu architectures (32-bit and more)
    the coding precision is hardly an issue at all.
    The overheads which we're normally able to encounter are at the
    scale of 100 bytes per 1M of compressed data, ie 0.01%.

    Anyway, the model is much more important in that sense.

    > In Campos' code the range initial value is 0x80000000. In some other
    > implementations I've walked through init values are something like
    > DWORD(-1), which is 0xFFFFFFFF. Both options have no sense to me. As
    > far as I understand we decide to work with 32bit integers without
    > last bit to prevent overflow. What would make sense here is
    > something like 0x7FFFFFFF - the largest 31bit number. Why
    > 0x80000000? Why 0xFFFFFFFF?...

    Some versions work with 32-bit range - these would usually set initial range to 2^32-1,
    because they can't put 2^32 there and also initial value doesn't really matter all that much -
    at worst we'd only lose a few bits even if its initialized with 1<<16 or something.

    Also there's an additional option of storing (range-1) in the variable
    and fixing it up by extra tweaks in range update:
    1) range' = range*freq/total; // normal
    2) range' = (range*freq+range)/total-1; // range-1 fixup
    The latter is in theory more precise, but the actual difference is really hard to notice
    (usually less than a byte).

    Then, other versions (like original M.Schindler's rangecoder) work with 31-bit range
    because like that it becomes easier to detect carry - in practice this doesn't make
    any sense at all, aside from making the coder more complicated due to extra shifts.
    Anyway, in this case the full initial range should be 2^31 if range variable is unsigned,
    but it can be also set to 2^31-1 if it has to be signed for some reasons (like java not
    having unsigned types).

    > while (low / 10000 == (low + range) / 10000)
    > I suspect that this: While ( range <= Bottom_value ) has to mean the
    > same, but I really don't understand why.

    Its not really the same. Low's bits higher than log2(range)'th can only
    be affected by carry (not directly by bits of symbol's interval low bound,
    which is <range), which allows for a simple implementation of long addition.

    Actually there's a tradeoff, because higher range value means better compression
    (ideally we can do bitwise renorm so range would be always in [2^31..2^32-1] )
    but having to do more renorm iterations makes coding slower.
    Still, in rangecoders, normally the Bottom_value is Initial_value/256, because that
    allows to shift out a whole byte from low.

    > a) Overflow: when low + new_value will become more than 0x7FFFFFFF.
    > Then we have to handle it somehow.

    Yes, but in this case we just have to proparage the carry.
    Low is actually stored with higher precision than it looks
    (there's a cached leading byte ("buffer" in your code) and potentially a string of FFs
    (of length "help" in your code))
    and the carry doesn't fit in the low part, so we have to update
    the cached part too (but then we can flush it).

    > b) Undeflow: when low and range become so close to each other that
    > there is no more bits left between them to represent the interval
    > and thus continue iterations.

    Yes, but this only matters in carryless coders (which avoid the carry
    by reducing the range, instead of doing the long arithmetics).

    > So, I absolutely don't understand how these situations are handled
    > in inner if ( low < ( 0FFh << Shift_bits ) ) { ... } branch and why
    > does it look like this. Could anyone explain?

    Well, as I said, the full value of low is Buffer . 0xFF x help . low.
    Now, (low<(0FFh<<Shift_bits)) means that high byte of low is not 0xFF
    so we can't just increment the 0xFF counter, and (low And Top_value)
    means the carry, because low is stored with 31-bit precision there.

Similar Threads

  1. Greetings, Questions, and Benchmarks
    By musicdemon in forum Data Compression
    Replies: 4
    Last Post: 8th January 2012, 21:45
  2. Questions about compression
    By 0011110100101001 in forum Data Compression
    Replies: 12
    Last Post: 8th December 2011, 01:31
  3. Hashing a large range of integers to a smaller range
    By mtwaha in forum Data Compression
    Replies: 3
    Last Post: 11th April 2011, 23:27
  4. Replies: 7
    Last Post: 19th March 2011, 10:50
  5. How fast should be a range coder ?
    By Cyan in forum Data Compression
    Replies: 33
    Last Post: 16th November 2009, 16:02

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •