1/*
2Copyright (C) 2002 Andrea Mazzoleni ( http://advancemame.sf.net )
3Copyright (C) 2001-4 Igor Pavlov ( http://www.7-zip.org )
4
5This library is free software; you can redistribute it and/or
6modify it under the terms of the GNU Lesser General Public
7License version 2.1 as published by the Free Software Foundation.
8
9This library is distributed in the hope that it will be useful,
10but WITHOUT ANY WARRANTY; without even the implied warranty of
11MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12Lesser General Public License for more details.
13
14You should have received a copy of the GNU Lesser General Public
15License along with this library; if not, write to the Free Software
16Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17*/
18
19#ifndef __COMPRESSION_RANGECODER_H
20#define __COMPRESSION_RANGECODER_H
21
22#include "inbyte.h"
23
24namespace NCompression {
25namespace NArithmetic {
26
27const UINT32 kNumTopBits = 24;
28const UINT32 kTopValue = (1 << kNumTopBits);
29
30class CRangeDecoder
31{
32public:
33 NStream::CInByte m_Stream;
34 UINT32 m_Range;
35 UINT32 m_Code;
36 UINT32 m_Word;
37 void Normalize()
38 {
39 while (m_Range < kTopValue)
40 {
41 m_Code = (m_Code << 8) | m_Stream.ReadByte();
42 m_Range <<= 8;
43 }
44 }
45
46 void Init(ISequentialInStream *aStream)
47 {
48 m_Stream.Init(aStream);
49 m_Code = 0;
50 m_Range = UINT32(-1);
51 for(int i = 0; i < 5; i++)
52 m_Code = (m_Code << 8) | m_Stream.ReadByte();
53 }
54
55 UINT32 GetThreshold(UINT32 aTotal)
56 {
57 return (m_Code) / ( m_Range /= aTotal);
58 }
59
60 void Decode(UINT32 aStart, UINT32 aSize, UINT32 aTotal)
61 {
62 m_Code -= aStart * m_Range;
63 m_Range *= aSize;
64 Normalize();
65 }
66
67 /*
68 UINT32 DecodeDirectBitsDiv(UINT32 aNumTotalBits)
69 {
70 m_Range >>= aNumTotalBits;
71 UINT32 aThreshold = m_Code / m_Range;
72 m_Code -= aThreshold * m_Range;
73
74 Normalize();
75 return aThreshold;
76 }
77
78 UINT32 DecodeDirectBitsDiv2(UINT32 aNumTotalBits)
79 {
80 if (aNumTotalBits <= kNumBottomBits)
81 return DecodeDirectBitsDiv(aNumTotalBits);
82 UINT32 aResult = DecodeDirectBitsDiv(aNumTotalBits - kNumBottomBits) << kNumBottomBits;
83 return (aResult | DecodeDirectBitsDiv(kNumBottomBits));
84 }
85 */
86
87 UINT32 DecodeDirectBits(UINT32 aNumTotalBits)
88 {
89 UINT32 aRange = m_Range;
90 UINT32 aCode = m_Code;
91 UINT32 aResult = 0;
92 for (UINT32 i = aNumTotalBits; i > 0; i--)
93 {
94 aRange >>= 1;
95 /*
96 aResult <<= 1;
97 if (aCode >= aRange)
98 {
99 aCode -= aRange;
100 aResult |= 1;
101 }
102 */
103 UINT32 t = (aCode - aRange) >> 31;
104 aCode -= aRange & (t - 1);
105 // aRange = aRangeTmp + ((aRange & 1) & (1 - t));
106 aResult = (aResult << 1) | (1 - t);
107
108 if (aRange < kTopValue)
109 {
110 aCode = (aCode << 8) | m_Stream.ReadByte();
111 aRange <<= 8;
112 }
113 }
114 m_Range = aRange;
115 m_Code = aCode;
116 return aResult;
117 }
118
119 UINT32 DecodeBit(UINT32 aSize0, UINT32 aNumTotalBits)
120 {
121 UINT32 aNewBound = (m_Range >> aNumTotalBits) * aSize0;
122 UINT32 aSymbol;
123 if (m_Code < aNewBound)
124 {
125 aSymbol = 0;
126 m_Range = aNewBound;
127 }
128 else
129 {
130 aSymbol = 1;
131 m_Code -= aNewBound;
132 m_Range -= aNewBound;
133 }
134 Normalize();
135 return aSymbol;
136 }
137
138 UINT64 GetProcessedSize() {return m_Stream.GetProcessedSize(); }
139};
140
141}}
142
143#endif
144