Home | History | Annotate | Download | only in Compress 
      1 // Compress/RangeCoder.h
      2 // 2013-01-10 : Igor Pavlov : Public domain
      3 
      4 #ifndef __COMPRESS_RANGE_CODER_H
      5 #define __COMPRESS_RANGE_CODER_H
      6 
      7 #include "../Common/InBuffer.h"
      8 #include "../Common/OutBuffer.h"
      9 
     10 namespace NCompress {
     11 namespace NRangeCoder {
     12 
     13 const unsigned kNumTopBits = 24;
     14 const UInt32 kTopValue = (1 << kNumTopBits);
     15 
     16 class CEncoder
     17 {
     18   UInt32 _cacheSize;
     19   Byte _cache;
     20 public:
     21   UInt64 Low;
     22   UInt32 Range;
     23   COutBuffer Stream;
     24   bool Create(UInt32 bufSize) { return Stream.Create(bufSize); }
     25 
     26   void SetStream(ISequentialOutStream *stream) { Stream.SetStream(stream); }
     27   void Init()
     28   {
     29     Stream.Init();
     30     Low = 0;
     31     Range = 0xFFFFFFFF;
     32     _cacheSize = 1;
     33     _cache = 0;
     34   }
     35 
     36   void FlushData()
     37   {
     38     // Low += 1;
     39     for (int i = 0; i < 5; i++)
     40       ShiftLow();
     41   }
     42 
     43   HRESULT FlushStream() { return Stream.Flush();  }
     44 
     45   void Encode(UInt32 start, UInt32 size, UInt32 total)
     46   {
     47     Low += start * (Range /= total);
     48     Range *= size;
     49     while (Range < kTopValue)
     50     {
     51       Range <<= 8;
     52       ShiftLow();
     53     }
     54   }
     55 
     56   void ShiftLow()
     57   {
     58     if ((UInt32)Low < (UInt32)0xFF000000 || (unsigned)(Low >> 32) != 0)
     59     {
     60       Byte temp = _cache;
     61       do
     62       {
     63         Stream.WriteByte((Byte)(temp + (Byte)(Low >> 32)));
     64         temp = 0xFF;
     65       }
     66       while (--_cacheSize != 0);
     67       _cache = (Byte)((UInt32)Low >> 24);
     68     }
     69     _cacheSize++;
     70     Low = (UInt32)Low << 8;
     71   }
     72 
     73   void EncodeDirectBits(UInt32 value, int numBits)
     74   {
     75     for (numBits--; numBits >= 0; numBits--)
     76     {
     77       Range >>= 1;
     78       Low += Range & (0 - ((value >> numBits) & 1));
     79       if (Range < kTopValue)
     80       {
     81         Range <<= 8;
     82         ShiftLow();
     83       }
     84     }
     85   }
     86 
     87   void EncodeBit(UInt32 size0, UInt32 numTotalBits, UInt32 symbol)
     88   {
     89     UInt32 newBound = (Range >> numTotalBits) * size0;
     90     if (symbol == 0)
     91       Range = newBound;
     92     else
     93     {
     94       Low += newBound;
     95       Range -= newBound;
     96     }
     97     while (Range < kTopValue)
     98     {
     99       Range <<= 8;
    100       ShiftLow();
    101     }
    102   }
    103 
    104   UInt64 GetProcessedSize() { return Stream.GetProcessedSize() + _cacheSize + 4; }
    105 };
    106 
    107 class CDecoder
    108 {
    109 public:
    110   CInBuffer Stream;
    111   UInt32 Range;
    112   UInt32 Code;
    113   bool Create(UInt32 bufSize) { return Stream.Create(bufSize); }
    114 
    115   void Normalize()
    116   {
    117     while (Range < kTopValue)
    118     {
    119       Code = (Code << 8) | Stream.ReadByte();
    120       Range <<= 8;
    121     }
    122   }
    123 
    124   void SetStream(ISequentialInStream *stream) { Stream.SetStream(stream); }
    125   void Init()
    126   {
    127     Stream.Init();
    128     Code = 0;
    129     Range = 0xFFFFFFFF;
    130     for (int i = 0; i < 5; i++)
    131       Code = (Code << 8) | Stream.ReadByte();
    132   }
    133 
    134   UInt32 GetThreshold(UInt32 total)
    135   {
    136     return (Code) / (Range /= total);
    137   }
    138 
    139   void Decode(UInt32 start, UInt32 size)
    140   {
    141     Code -= start * Range;
    142     Range *= size;
    143     Normalize();
    144   }
    145 
    146   UInt32 DecodeDirectBits(int numTotalBits)
    147   {
    148     UInt32 range = Range;
    149     UInt32 code = Code;
    150     UInt32 result = 0;
    151     for (int i = numTotalBits; i != 0; i--)
    152     {
    153       range >>= 1;
    154       /*
    155       result <<= 1;
    156       if (code >= range)
    157       {
    158         code -= range;
    159         result |= 1;
    160       }
    161       */
    162       UInt32 t = (code - range) >> 31;
    163       code -= range & (t - 1);
    164       result = (result << 1) | (1 - t);
    165 
    166       if (range < kTopValue)
    167       {
    168         code = (code << 8) | Stream.ReadByte();
    169         range <<= 8;
    170       }
    171     }
    172     Range = range;
    173     Code = code;
    174     return result;
    175   }
    176 
    177   UInt32 DecodeBit(UInt32 size0, UInt32 numTotalBits)
    178   {
    179     UInt32 newBound = (Range >> numTotalBits) * size0;
    180     UInt32 symbol;
    181     if (Code < newBound)
    182     {
    183       symbol = 0;
    184       Range = newBound;
    185     }
    186     else
    187     {
    188       symbol = 1;
    189       Code -= newBound;
    190       Range -= newBound;
    191     }
    192     Normalize();
    193     return symbol;
    194   }
    195 
    196   UInt64 GetProcessedSize() { return Stream.GetProcessedSize(); }
    197 };
    198 
    199 }}
    200 
    201 #endif
    202