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