Annotation of elwix/tools/oldlzma/SRC/7zip/Compress/RangeCoder/RangeCoder.h, revision 1.1
1.1 ! misho 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 _ffNum;
! 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: _ffNum = 0;
! 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: /*
! 58: void EncodeDirectBitsDiv(UInt32 value, UInt32 numTotalBits)
! 59: {
! 60: Low += value * (Range >>= numTotalBits);
! 61: Normalize();
! 62: }
! 63:
! 64: void EncodeDirectBitsDiv2(UInt32 value, UInt32 numTotalBits)
! 65: {
! 66: if (numTotalBits <= kNumBottomBits)
! 67: EncodeDirectBitsDiv(value, numTotalBits);
! 68: else
! 69: {
! 70: EncodeDirectBitsDiv(value >> kNumBottomBits, (numTotalBits - kNumBottomBits));
! 71: EncodeDirectBitsDiv(value & ((1 << kBottomValueBits) - 1), kNumBottomBits);
! 72: }
! 73: }
! 74: */
! 75: void ShiftLow()
! 76: {
! 77: if (Low < (UInt32)0xFF000000 || UInt32(Low >> 32) == 1)
! 78: {
! 79: Stream.WriteByte(Byte(_cache + Byte(Low >> 32)));
! 80: for (;_ffNum != 0; _ffNum--)
! 81: Stream.WriteByte(Byte(0xFF + Byte(Low >> 32)));
! 82: _cache = Byte(UInt32(Low) >> 24);
! 83: }
! 84: else
! 85: _ffNum++;
! 86: Low = UInt32(Low) << 8;
! 87: }
! 88:
! 89: void EncodeDirectBits(UInt32 value, int numTotalBits)
! 90: {
! 91: for (int i = numTotalBits - 1; i >= 0; i--)
! 92: {
! 93: Range >>= 1;
! 94: if (((value >> i) & 1) == 1)
! 95: Low += Range;
! 96: if (Range < kTopValue)
! 97: {
! 98: Range <<= 8;
! 99: ShiftLow();
! 100: }
! 101: }
! 102: }
! 103:
! 104: void EncodeBit(UInt32 size0, UInt32 numTotalBits, UInt32 symbol)
! 105: {
! 106: UInt32 newBound = (Range >> numTotalBits) * size0;
! 107: if (symbol == 0)
! 108: Range = newBound;
! 109: else
! 110: {
! 111: Low += newBound;
! 112: Range -= newBound;
! 113: }
! 114: while (Range < kTopValue)
! 115: {
! 116: Range <<= 8;
! 117: ShiftLow();
! 118: }
! 119: }
! 120:
! 121: UInt64 GetProcessedSize() { return Stream.GetProcessedSize() + _ffNum; }
! 122: };
! 123:
! 124: class CDecoder
! 125: {
! 126: public:
! 127: CInBuffer Stream;
! 128: UInt32 Range;
! 129: UInt32 Code;
! 130: bool Create(UInt32 bufferSize) { return Stream.Create(bufferSize); }
! 131:
! 132: void Normalize()
! 133: {
! 134: while (Range < kTopValue)
! 135: {
! 136: Code = (Code << 8) | Stream.ReadByte();
! 137: Range <<= 8;
! 138: }
! 139: }
! 140:
! 141: void SetStream(ISequentialInStream *stream) { Stream.SetStream(stream); }
! 142: void Init()
! 143: {
! 144: Stream.Init();
! 145: Code = 0;
! 146: Range = 0xFFFFFFFF;
! 147: for(int i = 0; i < 5; i++)
! 148: Code = (Code << 8) | Stream.ReadByte();
! 149: }
! 150:
! 151: void ReleaseStream() { Stream.ReleaseStream(); }
! 152:
! 153: UInt32 GetThreshold(UInt32 total)
! 154: {
! 155: return (Code) / ( Range /= total);
! 156: }
! 157:
! 158: void Decode(UInt32 start, UInt32 size)
! 159: {
! 160: Code -= start * Range;
! 161: Range *= size;
! 162: Normalize();
! 163: }
! 164:
! 165: /*
! 166: UInt32 DecodeDirectBitsDiv(UInt32 numTotalBits)
! 167: {
! 168: Range >>= numTotalBits;
! 169: UInt32 threshold = Code / Range;
! 170: Code -= threshold * Range;
! 171:
! 172: Normalize();
! 173: return threshold;
! 174: }
! 175:
! 176: UInt32 DecodeDirectBitsDiv2(UInt32 numTotalBits)
! 177: {
! 178: if (numTotalBits <= kNumBottomBits)
! 179: return DecodeDirectBitsDiv(numTotalBits);
! 180: UInt32 result = DecodeDirectBitsDiv(numTotalBits - kNumBottomBits) << kNumBottomBits;
! 181: return (result | DecodeDirectBitsDiv(kNumBottomBits));
! 182: }
! 183: */
! 184:
! 185: UInt32 DecodeDirectBits(int numTotalBits)
! 186: {
! 187: UInt32 range = Range;
! 188: UInt32 code = Code;
! 189: UInt32 result = 0;
! 190: for (int i = numTotalBits; i != 0; i--)
! 191: {
! 192: range >>= 1;
! 193: /*
! 194: result <<= 1;
! 195: if (code >= range)
! 196: {
! 197: code -= range;
! 198: result |= 1;
! 199: }
! 200: */
! 201: UInt32 t = (code - range) >> 31;
! 202: code -= range & (t - 1);
! 203: result = (result << 1) | (1 - t);
! 204:
! 205: if (range < kTopValue)
! 206: {
! 207: code = (code << 8) | Stream.ReadByte();
! 208: range <<= 8;
! 209: }
! 210: }
! 211: Range = range;
! 212: Code = code;
! 213: return result;
! 214: }
! 215:
! 216: UInt32 DecodeBit(UInt32 size0, UInt32 numTotalBits)
! 217: {
! 218: UInt32 newBound = (Range >> numTotalBits) * size0;
! 219: UInt32 symbol;
! 220: if (Code < newBound)
! 221: {
! 222: symbol = 0;
! 223: Range = newBound;
! 224: }
! 225: else
! 226: {
! 227: symbol = 1;
! 228: Code -= newBound;
! 229: Range -= newBound;
! 230: }
! 231: Normalize();
! 232: return symbol;
! 233: }
! 234:
! 235: UInt64 GetProcessedSize() {return Stream.GetProcessedSize(); }
! 236: };
! 237:
! 238: }}
! 239:
! 240: #endif
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to RangeCoder.h CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / elwix / tools / oldlzma / SRC / 7zip / Compress / RangeCoder