1 // BitlDecoder.h -- the Least Significant Bit of byte is First
2 
3 #ifndef __BITL_DECODER_H
4 #define __BITL_DECODER_H
5 
6 #include "../IStream.h"
7 
8 namespace NBitl {
9 
10 const unsigned kNumBigValueBits = 8 * 4;
11 const unsigned kNumValueBytes = 3;
12 const unsigned kNumValueBits = 8 * kNumValueBytes;
13 
14 const UInt32 kMask = (1 << kNumValueBits) - 1;
15 
16 extern Byte kInvertTable[256];
17 
18 /* TInByte must support "Extra Bytes" (bytes that can be read after the end of stream
19    TInByte::ReadByte() returns 0xFF after the end of stream
20    TInByte::NumExtraBytes contains the number "Extra Bytes"
21 
22    Bitl decoder can read up to 4 bytes ahead to internal buffer. */
23 
24 template<class TInByte>
25 class CBaseDecoder
26 {
27 protected:
28   unsigned _bitPos;
29   UInt32 _value;
30   TInByte _stream;
31 public:
Create(UInt32 bufSize)32   bool Create(UInt32 bufSize) { return _stream.Create(bufSize); }
SetStream(ISequentialInStream * inStream)33   void SetStream(ISequentialInStream *inStream) { _stream.SetStream(inStream); }
Init()34   void Init()
35   {
36     _stream.Init();
37     _bitPos = kNumBigValueBits;
38     _value = 0;
39   }
40 
41   // the size of portion data in real stream that was already read from this object.
42   // it doesn't include unused data in BitStream object buffer (up to 4 bytes)
43   // it doesn't include unused data in TInByte buffers
44   // it doesn't include virtual Extra bytes after the end of real stream data
GetStreamSize()45   UInt64 GetStreamSize() const
46   {
47     return ExtraBitsWereRead() ?
48         _stream.GetStreamSize():
49         GetProcessedSize();
50   }
51 
52   // the size of virtual data that was read from this object.
GetProcessedSize()53   UInt64 GetProcessedSize() const { return _stream.GetProcessedSize() - ((kNumBigValueBits - _bitPos) >> 3); }
54 
ThereAreDataInBitsBuffer()55   bool ThereAreDataInBitsBuffer() const { return this->_bitPos != kNumBigValueBits; }
56 
57   MY_FORCE_INLINE
Normalize()58   void Normalize()
59   {
60     for (; _bitPos >= 8; _bitPos -= 8)
61       _value = ((UInt32)_stream.ReadByte() << (kNumBigValueBits - _bitPos)) | _value;
62   }
63 
64   MY_FORCE_INLINE
ReadBits(unsigned numBits)65   UInt32 ReadBits(unsigned numBits)
66   {
67     Normalize();
68     UInt32 res = _value & ((1 << numBits) - 1);
69     _bitPos += numBits;
70     _value >>= numBits;
71     return res;
72   }
73 
ExtraBitsWereRead()74   bool ExtraBitsWereRead() const
75   {
76     return (_stream.NumExtraBytes > 4 || kNumBigValueBits - _bitPos < (_stream.NumExtraBytes << 3));
77   }
78 
ExtraBitsWereRead_Fast()79   bool ExtraBitsWereRead_Fast() const
80   {
81     // full version is not inlined in vc6.
82     // return _stream.NumExtraBytes != 0 && (_stream.NumExtraBytes > 4 || kNumBigValueBits - _bitPos < (_stream.NumExtraBytes << 3));
83 
84     // (_stream.NumExtraBytes > 4) is fast overread detection. It's possible that
85     // it doesn't return true, if small number of extra bits were read.
86     return (_stream.NumExtraBytes > 4);
87   }
88 
89   // it must be fixed !!! with extra bits
90   // UInt32 GetNumExtraBytes() const { return _stream.NumExtraBytes; }
91 };
92 
93 template<class TInByte>
94 class CDecoder: public CBaseDecoder<TInByte>
95 {
96   UInt32 _normalValue;
97 
98 public:
Init()99   void Init()
100   {
101     CBaseDecoder<TInByte>::Init();
102     _normalValue = 0;
103   }
104 
105   MY_FORCE_INLINE
Normalize()106   void Normalize()
107   {
108     for (; this->_bitPos >= 8; this->_bitPos -= 8)
109     {
110       Byte b = this->_stream.ReadByte();
111       _normalValue = ((UInt32)b << (kNumBigValueBits - this->_bitPos)) | _normalValue;
112       this->_value = (this->_value << 8) | kInvertTable[b];
113     }
114   }
115 
116   MY_FORCE_INLINE
GetValue(unsigned numBits)117   UInt32 GetValue(unsigned numBits)
118   {
119     Normalize();
120     return ((this->_value >> (8 - this->_bitPos)) & kMask) >> (kNumValueBits - numBits);
121   }
122 
123   MY_FORCE_INLINE
MovePos(unsigned numBits)124   void MovePos(unsigned numBits)
125   {
126     this->_bitPos += numBits;
127     _normalValue >>= numBits;
128   }
129 
130   MY_FORCE_INLINE
ReadBits(unsigned numBits)131   UInt32 ReadBits(unsigned numBits)
132   {
133     Normalize();
134     UInt32 res = _normalValue & ((1 << numBits) - 1);
135     MovePos(numBits);
136     return res;
137   }
138 
AlignToByte()139   void AlignToByte() { MovePos((32 - this->_bitPos) & 7); }
140 
141   MY_FORCE_INLINE
ReadDirectByte()142   Byte ReadDirectByte() { return this->_stream.ReadByte(); }
143 
144   MY_FORCE_INLINE
ReadAlignedByte()145   Byte ReadAlignedByte()
146   {
147     if (this->_bitPos == kNumBigValueBits)
148       return this->_stream.ReadByte();
149     Byte b = (Byte)(_normalValue & 0xFF);
150     MovePos(8);
151     return b;
152   }
153 
154   // call it only if the object is aligned for byte.
155   MY_FORCE_INLINE
ReadAlignedByte_FromBuf(Byte & b)156   bool ReadAlignedByte_FromBuf(Byte &b)
157   {
158     if (this->_bitPos == kNumBigValueBits)
159       return this->_stream.ReadByte_FromBuf(b);
160     b = (Byte)(_normalValue & 0xFF);
161     MovePos(8);
162     return true;
163   }
164 };
165 
166 }
167 
168 #endif
169