michael@0: // Compress/RangeCoder/RangeCoder.h
michael@0: 
michael@0: #ifndef __COMPRESS_RANGECODER_H
michael@0: #define __COMPRESS_RANGECODER_H
michael@0: 
michael@0: #include "../../Common/InBuffer.h"
michael@0: #include "../../Common/OutBuffer.h"
michael@0: 
michael@0: namespace NCompress {
michael@0: namespace NRangeCoder {
michael@0: 
michael@0: const int kNumTopBits = 24;
michael@0: const UInt32 kTopValue = (1 << kNumTopBits);
michael@0: 
michael@0: class CEncoder
michael@0: {
michael@0:   UInt32 _cacheSize;
michael@0:   Byte _cache;
michael@0: public:
michael@0:   UInt64 Low;
michael@0:   UInt32 Range;
michael@0:   COutBuffer Stream;
michael@0:   bool Create(UInt32 bufferSize) { return Stream.Create(bufferSize); }
michael@0: 
michael@0:   void SetStream(ISequentialOutStream *stream) { Stream.SetStream(stream); }
michael@0:   void Init()
michael@0:   {
michael@0:     Stream.Init();
michael@0:     Low = 0;
michael@0:     Range = 0xFFFFFFFF;
michael@0:     _cacheSize = 1;
michael@0:     _cache = 0;
michael@0:   }
michael@0: 
michael@0:   void FlushData()
michael@0:   {
michael@0:     // Low += 1; 
michael@0:     for(int i = 0; i < 5; i++)
michael@0:       ShiftLow();
michael@0:   }
michael@0: 
michael@0:   HRESULT FlushStream() { return Stream.Flush();  }
michael@0: 
michael@0:   void ReleaseStream() { Stream.ReleaseStream(); }
michael@0: 
michael@0:   void Encode(UInt32 start, UInt32 size, UInt32 total)
michael@0:   {
michael@0:     Low += start * (Range /= total);
michael@0:     Range *= size;
michael@0:     while (Range < kTopValue)
michael@0:     {
michael@0:       Range <<= 8;
michael@0:       ShiftLow();
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   void ShiftLow()
michael@0:   {
michael@0:     if ((UInt32)Low < (UInt32)0xFF000000 || (int)(Low >> 32) != 0) 
michael@0:     {
michael@0:       Byte temp = _cache;
michael@0:       do
michael@0:       {
michael@0:         Stream.WriteByte((Byte)(temp + (Byte)(Low >> 32)));
michael@0:         temp = 0xFF;
michael@0:       }
michael@0:       while(--_cacheSize != 0);
michael@0:       _cache = (Byte)((UInt32)Low >> 24);                      
michael@0:     } 
michael@0:     _cacheSize++;                               
michael@0:     Low = (UInt32)Low << 8;                           
michael@0:   }
michael@0:   
michael@0:   void EncodeDirectBits(UInt32 value, int numTotalBits)
michael@0:   {
michael@0:     for (int i = numTotalBits - 1; i >= 0; i--)
michael@0:     {
michael@0:       Range >>= 1;
michael@0:       if (((value >> i) & 1) == 1)
michael@0:         Low += Range;
michael@0:       if (Range < kTopValue)
michael@0:       {
michael@0:         Range <<= 8;
michael@0:         ShiftLow();
michael@0:       }
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   void EncodeBit(UInt32 size0, UInt32 numTotalBits, UInt32 symbol)
michael@0:   {
michael@0:     UInt32 newBound = (Range >> numTotalBits) * size0;
michael@0:     if (symbol == 0)
michael@0:       Range = newBound;
michael@0:     else
michael@0:     {
michael@0:       Low += newBound;
michael@0:       Range -= newBound;
michael@0:     }
michael@0:     while (Range < kTopValue)
michael@0:     {
michael@0:       Range <<= 8;
michael@0:       ShiftLow();
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   UInt64 GetProcessedSize() {  return Stream.GetProcessedSize() + _cacheSize + 4; }
michael@0: };
michael@0: 
michael@0: class CDecoder
michael@0: {
michael@0: public:
michael@0:   CInBuffer Stream;
michael@0:   UInt32 Range;
michael@0:   UInt32 Code;
michael@0:   bool Create(UInt32 bufferSize) { return Stream.Create(bufferSize); }
michael@0: 
michael@0:   void Normalize()
michael@0:   {
michael@0:     while (Range < kTopValue)
michael@0:     {
michael@0:       Code = (Code << 8) | Stream.ReadByte();
michael@0:       Range <<= 8;
michael@0:     }
michael@0:   }
michael@0:   
michael@0:   void SetStream(ISequentialInStream *stream) { Stream.SetStream(stream); }
michael@0:   void Init()
michael@0:   {
michael@0:     Stream.Init();
michael@0:     Code = 0;
michael@0:     Range = 0xFFFFFFFF;
michael@0:     for(int i = 0; i < 5; i++)
michael@0:       Code = (Code << 8) | Stream.ReadByte();
michael@0:   }
michael@0: 
michael@0:   void ReleaseStream() { Stream.ReleaseStream(); }
michael@0: 
michael@0:   UInt32 GetThreshold(UInt32 total)
michael@0:   {
michael@0:     return (Code) / ( Range /= total);
michael@0:   }
michael@0: 
michael@0:   void Decode(UInt32 start, UInt32 size)
michael@0:   {
michael@0:     Code -= start * Range;
michael@0:     Range *= size;
michael@0:     Normalize();
michael@0:   }
michael@0: 
michael@0:   UInt32 DecodeDirectBits(int numTotalBits)
michael@0:   {
michael@0:     UInt32 range = Range;
michael@0:     UInt32 code = Code;        
michael@0:     UInt32 result = 0;
michael@0:     for (int i = numTotalBits; i != 0; i--)
michael@0:     {
michael@0:       range >>= 1;
michael@0:       /*
michael@0:       result <<= 1;
michael@0:       if (code >= range)
michael@0:       {
michael@0:         code -= range;
michael@0:         result |= 1;
michael@0:       }
michael@0:       */
michael@0:       UInt32 t = (code - range) >> 31;
michael@0:       code -= range & (t - 1);
michael@0:       result = (result << 1) | (1 - t);
michael@0: 
michael@0:       if (range < kTopValue)
michael@0:       {
michael@0:         code = (code << 8) | Stream.ReadByte();
michael@0:         range <<= 8; 
michael@0:       }
michael@0:     }
michael@0:     Range = range;
michael@0:     Code = code;
michael@0:     return result;
michael@0:   }
michael@0: 
michael@0:   UInt32 DecodeBit(UInt32 size0, UInt32 numTotalBits)
michael@0:   {
michael@0:     UInt32 newBound = (Range >> numTotalBits) * size0;
michael@0:     UInt32 symbol;
michael@0:     if (Code < newBound)
michael@0:     {
michael@0:       symbol = 0;
michael@0:       Range = newBound;
michael@0:     }
michael@0:     else
michael@0:     {
michael@0:       symbol = 1;
michael@0:       Code -= newBound;
michael@0:       Range -= newBound;
michael@0:     }
michael@0:     Normalize();
michael@0:     return symbol;
michael@0:   }
michael@0: 
michael@0:   UInt64 GetProcessedSize() {return Stream.GetProcessedSize(); }
michael@0: };
michael@0: 
michael@0: }}
michael@0: 
michael@0: #endif