Home | History | Annotate | Download | only in Compress 
      1 // Compress/RangeCoder.h
      2 // 2009-05-30 : 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 int 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 bufferSize) { return Stream.Create(bufferSize); }
     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 ReleaseStream() { Stream.ReleaseStream(); }
     46 
     47   void Encode(UInt32 start, UInt32 size, UInt32 total)
     48   {
     49     Low += start * (Range /= total);
     50     Range *= size;
     51     while (Range < kTopValue)
     52     {
     53       Range <<= 8;
     54       ShiftLow();
     55     }
     56   }
     57 
     58   void ShiftLow()
     59   {
     60     if ((UInt32)Low < (UInt32)0xFF000000 || (int)(Low >> 32) != 0)
     61     {
     62       Byte temp = _cache;
     63       do
     64       {
     65         Stream.WriteByte((Byte)(temp + (Byte)(Low >> 32)));
     66         temp = 0xFF;
     67       }
     68       while(--_cacheSize != 0);
     69       _cache = (Byte)((UInt32)Low >> 24);
     70     }
     71     _cacheSize++;
     72     Low = (UInt32)Low << 8;
     73   }
     74 
     75   void EncodeDirectBits(UInt32 value, int numBits)
     76   {
     77     for (numBits--; numBits >= 0; numBits--)
     78     {
     79       Range >>= 1;
     80       Low += Range & (0 - ((value >> numBits) & 1));
     81       if (Range < kTopValue)
     82       {
     83         Range <<= 8;
     84         ShiftLow();
     85       }
     86     }
     87   }
     88 
     89   void EncodeBit(UInt32 size0, UInt32 numTotalBits, UInt32 symbol)
     90   {
     91     UInt32 newBound = (Range >> numTotalBits) * size0;
     92     if (symbol == 0)
     93       Range = newBound;
     94     else
     95     {
     96       Low += newBound;
     97       Range -= newBound;
     98     }
     99     while (Range < kTopValue)
    100     {
    101       Range <<= 8;
    102       ShiftLow();
    103     }
    104   }
    105 
    106   UInt64 GetProcessedSize() {  return Stream.GetProcessedSize() + _cacheSize + 4; }
    107 };
    108 
    109 class CDecoder
    110 {
    111 public:
    112   CInBuffer Stream;
    113   UInt32 Range;
    114   UInt32 Code;
    115   bool Create(UInt32 bufferSize) { return Stream.Create(bufferSize); }
    116 
    117   void Normalize()
    118   {
    119     while (Range < kTopValue)
    120     {
    121       Code = (Code << 8) | Stream.ReadByte();
    122       Range <<= 8;
    123     }
    124   }
    125 
    126   void SetStream(ISequentialInStream *stream) { Stream.SetStream(stream); }
    127   void Init()
    128   {
    129     Stream.Init();
    130     Code = 0;
    131     Range = 0xFFFFFFFF;
    132     for(int i = 0; i < 5; i++)
    133       Code = (Code << 8) | Stream.ReadByte();
    134   }
    135 
    136   void ReleaseStream() { Stream.ReleaseStream(); }
    137 
    138   UInt32 GetThreshold(UInt32 total)
    139   {
    140     return (Code) / ( Range /= total);
    141   }
    142 
    143   void Decode(UInt32 start, UInt32 size)
    144   {
    145     Code -= start * Range;
    146     Range *= size;
    147     Normalize();
    148   }
    149 
    150   UInt32 DecodeDirectBits(int numTotalBits)
    151   {
    152     UInt32 range = Range;
    153     UInt32 code = Code;
    154     UInt32 result = 0;
    155     for (int i = numTotalBits; i != 0; i--)
    156     {
    157       range >>= 1;
    158       /*
    159       result <<= 1;
    160       if (code >= range)
    161       {
    162         code -= range;
    163         result |= 1;
    164       }
    165       */
    166       UInt32 t = (code - range) >> 31;
    167       code -= range & (t - 1);
    168       result = (result << 1) | (1 - t);
    169 
    170       if (range < kTopValue)
    171       {
    172         code = (code << 8) | Stream.ReadByte();
    173         range <<= 8;
    174       }
    175     }
    176     Range = range;
    177     Code = code;
    178     return result;
    179   }
    180 
    181   UInt32 DecodeBit(UInt32 size0, UInt32 numTotalBits)
    182   {
    183     UInt32 newBound = (Range >> numTotalBits) * size0;
    184     UInt32 symbol;
    185     if (Code < newBound)
    186     {
    187       symbol = 0;
    188       Range = newBound;
    189     }
    190     else
    191     {
    192       symbol = 1;
    193       Code -= newBound;
    194       Range -= newBound;
    195     }
    196     Normalize();
    197     return symbol;
    198   }
    199 
    200   UInt64 GetProcessedSize() {return Stream.GetProcessedSize(); }
    201 };
    202 
    203 }}
    204 
    205 #endif
    206