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