1 // Compress/RangeCoder/RangeCoder.h

     2 

     3 #ifndef __COMPRESS_RANGECODER_H

     4 #define __COMPRESS_RANGECODER_H

     5 

     6 #include "../../Common/InBuffer.h"

     7 #include "../../Common/OutBuffer.h"

     8 

     9 namespace NCompress {

    10 namespace NRangeCoder {

    11 

    12 const int kNumTopBits = 24;

    13 const UInt32 kTopValue = (1 << kNumTopBits);

    14 

    15 class CEncoder

    16 {

    17   UInt32 _cacheSize;

    18   Byte _cache;

    19 public:

    20   UInt64 Low;

    21   UInt32 Range;

    22   COutBuffer Stream;

    23   bool Create(UInt32 bufferSize) { return Stream.Create(bufferSize); }

    24 

    25   void SetStream(ISequentialOutStream *stream) { Stream.SetStream(stream); }

    26   void Init()

    27   {

    28     Stream.Init();

    29     Low = 0;

    30     Range = 0xFFFFFFFF;

    31     _cacheSize = 1;

    32     _cache = 0;

    33   }

    34 

    35   void FlushData()

    36   {

    37     // Low += 1; 

    38     for(int i = 0; i < 5; i++)

    39       ShiftLow();

    40   }

    41 

    42   HRESULT FlushStream() { return Stream.Flush();  }

    43 

    44   void ReleaseStream() { Stream.ReleaseStream(); }

    45 

    46   void Encode(UInt32 start, UInt32 size, UInt32 total)

    47   {

    48     Low += start * (Range /= total);

    49     Range *= size;

    50     while (Range < kTopValue)

    51     {

    52       Range <<= 8;

    53       ShiftLow();

    54     }

    55   }

    56 

    57   void ShiftLow()

    58   {

    59     if ((UInt32)Low < (UInt32)0xFF000000 || (int)(Low >> 32) != 0) 

    60     {

    61       Byte temp = _cache;

    62       do

    63       {

    64         Stream.WriteByte((Byte)(temp + (Byte)(Low >> 32)));

    65         temp = 0xFF;

    66       }

    67       while(--_cacheSize != 0);

    68       _cache = (Byte)((UInt32)Low >> 24);                      

    69     } 

    70     _cacheSize++;                               

    71     Low = (UInt32)Low << 8;                           

    72   }

    73   

    74   void EncodeDirectBits(UInt32 value, int numTotalBits)

    75   {

    76     for (int i = numTotalBits - 1; i >= 0; i--)

    77     {

    78       Range >>= 1;

    79       if (((value >> i) & 1) == 1)

    80         Low += Range;

    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