Line data Source code
1 : /* ******************************************************************
2 : bitstream
3 : Part of FSE library
4 : header file (to include)
5 : Copyright (C) 2013-2016, Yann Collet.
6 :
7 : BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
8 :
9 : Redistribution and use in source and binary forms, with or without
10 : modification, are permitted provided that the following conditions are
11 : met:
12 :
13 : * Redistributions of source code must retain the above copyright
14 : notice, this list of conditions and the following disclaimer.
15 : * Redistributions in binary form must reproduce the above
16 : copyright notice, this list of conditions and the following disclaimer
17 : in the documentation and/or other materials provided with the
18 : distribution.
19 :
20 : THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 : "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 : LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23 : A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24 : OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25 : SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26 : LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 : DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 : THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 : (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30 : OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 :
32 : You can contact the author at :
33 : - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
34 : ****************************************************************** */
35 : #ifndef BITSTREAM_H_MODULE
36 : #define BITSTREAM_H_MODULE
37 :
38 : #if defined (__cplusplus)
39 : extern "C" {
40 : #endif
41 :
42 :
43 : /*
44 : * This API consists of small unitary functions, which must be inlined for best performance.
45 : * Since link-time-optimization is not available for all compilers,
46 : * these functions are defined into a .h to be included.
47 : */
48 :
49 : /*-****************************************
50 : * Dependencies
51 : ******************************************/
52 : #include "mem.h" /* unaligned access routines */
53 : #include "error_private.h" /* error codes and messages */
54 :
55 :
56 : /*=========================================
57 : * Target specific
58 : =========================================*/
59 : #if defined(__BMI__) && defined(__GNUC__)
60 : # include <immintrin.h> /* support for bextr (experimental) */
61 : #endif
62 :
63 :
64 : /*-******************************************
65 : * bitStream encoding API (write forward)
66 : ********************************************/
67 : /* bitStream can mix input from multiple sources.
68 : * A critical property of these streams is that they encode and decode in **reverse** direction.
69 : * So the first bit sequence you add will be the last to be read, like a LIFO stack.
70 : */
71 : typedef struct
72 : {
73 : size_t bitContainer;
74 : int bitPos;
75 : char* startPtr;
76 : char* ptr;
77 : char* endPtr;
78 : } BIT_CStream_t;
79 :
80 : MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC, void* dstBuffer, size_t dstCapacity);
81 : MEM_STATIC void BIT_addBits(BIT_CStream_t* bitC, size_t value, unsigned nbBits);
82 : MEM_STATIC void BIT_flushBits(BIT_CStream_t* bitC);
83 : MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t* bitC);
84 :
85 : /* Start with initCStream, providing the size of buffer to write into.
86 : * bitStream will never write outside of this buffer.
87 : * `dstCapacity` must be >= sizeof(bitD->bitContainer), otherwise @return will be an error code.
88 : *
89 : * bits are first added to a local register.
90 : * Local register is size_t, hence 64-bits on 64-bits systems, or 32-bits on 32-bits systems.
91 : * Writing data into memory is an explicit operation, performed by the flushBits function.
92 : * Hence keep track how many bits are potentially stored into local register to avoid register overflow.
93 : * After a flushBits, a maximum of 7 bits might still be stored into local register.
94 : *
95 : * Avoid storing elements of more than 24 bits if you want compatibility with 32-bits bitstream readers.
96 : *
97 : * Last operation is to close the bitStream.
98 : * The function returns the final size of CStream in bytes.
99 : * If data couldn't fit into `dstBuffer`, it will return a 0 ( == not storable)
100 : */
101 :
102 :
103 : /*-********************************************
104 : * bitStream decoding API (read backward)
105 : **********************************************/
106 : typedef struct
107 : {
108 : size_t bitContainer;
109 : unsigned bitsConsumed;
110 : const char* ptr;
111 : const char* start;
112 : } BIT_DStream_t;
113 :
114 : typedef enum { BIT_DStream_unfinished = 0,
115 : BIT_DStream_endOfBuffer = 1,
116 : BIT_DStream_completed = 2,
117 : BIT_DStream_overflow = 3 } BIT_DStream_status; /* result of BIT_reloadDStream() */
118 : /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
119 :
120 : MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
121 : MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
122 : MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD);
123 : MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);
124 :
125 :
126 : /* Start by invoking BIT_initDStream().
127 : * A chunk of the bitStream is then stored into a local register.
128 : * Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t).
129 : * You can then retrieve bitFields stored into the local register, **in reverse order**.
130 : * Local register is explicitly reloaded from memory by the BIT_reloadDStream() method.
131 : * A reload guarantee a minimum of ((8*sizeof(bitD->bitContainer))-7) bits when its result is BIT_DStream_unfinished.
132 : * Otherwise, it can be less than that, so proceed accordingly.
133 : * Checking if DStream has reached its end can be performed with BIT_endOfDStream().
134 : */
135 :
136 :
137 : /*-****************************************
138 : * unsafe API
139 : ******************************************/
140 : MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC, size_t value, unsigned nbBits);
141 : /* faster, but works only if value is "clean", meaning all high bits above nbBits are 0 */
142 :
143 : MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC);
144 : /* unsafe version; does not check buffer overflow */
145 :
146 : MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);
147 : /* faster, but works only if nbBits >= 1 */
148 :
149 :
150 :
151 : /*-**************************************************************
152 : * Internal functions
153 : ****************************************************************/
154 2773204 : MEM_STATIC unsigned BIT_highbit32 (register U32 val)
155 : {
156 : # if defined(_MSC_VER) /* Visual */
157 : unsigned long r=0;
158 : _BitScanReverse ( &r, val );
159 : return (unsigned) r;
160 : # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
161 2773204 : return 31 - __builtin_clz (val);
162 : # else /* Software version */
163 : static const unsigned DeBruijnClz[32] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 };
164 : U32 v = val;
165 : v |= v >> 1;
166 : v |= v >> 2;
167 : v |= v >> 4;
168 : v |= v >> 8;
169 : v |= v >> 16;
170 : return DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
171 : # endif
172 : }
173 :
174 : /*===== Local Constants =====*/
175 : static const unsigned BIT_mask[] = { 0, 1, 3, 7, 0xF, 0x1F, 0x3F, 0x7F, 0xFF, 0x1FF, 0x3FF, 0x7FF, 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF, 0x1FFFF, 0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF, 0x3FFFFF, 0x7FFFFF, 0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF }; /* up to 26 bits */
176 :
177 :
178 : /*-**************************************************************
179 : * bitStream encoding
180 : ****************************************************************/
181 : /*! BIT_initCStream() :
182 : * `dstCapacity` must be > sizeof(void*)
183 : * @return : 0 if success,
184 : otherwise an error code (can be tested using ERR_isError() ) */
185 11576 : MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC, void* startPtr, size_t dstCapacity)
186 : {
187 11576 : bitC->bitContainer = 0;
188 11576 : bitC->bitPos = 0;
189 11576 : bitC->startPtr = (char*)startPtr;
190 11576 : bitC->ptr = bitC->startPtr;
191 11576 : bitC->endPtr = bitC->startPtr + dstCapacity - sizeof(bitC->ptr);
192 11576 : if (dstCapacity <= sizeof(bitC->ptr)) return ERROR(dstSize_tooSmall);
193 11576 : return 0;
194 : }
195 :
196 : /*! BIT_addBits() :
197 : can add up to 26 bits into `bitC`.
198 : Does not check for register overflow ! */
199 67208496 : MEM_STATIC void BIT_addBits(BIT_CStream_t* bitC, size_t value, unsigned nbBits)
200 : {
201 67208496 : bitC->bitContainer |= (value & BIT_mask[nbBits]) << bitC->bitPos;
202 67208496 : bitC->bitPos += nbBits;
203 67208496 : }
204 :
205 : /*! BIT_addBitsFast() :
206 : * works only if `value` is _clean_, meaning all high bits above nbBits are 0 */
207 139538332 : MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC, size_t value, unsigned nbBits)
208 : {
209 139538332 : bitC->bitContainer |= value << bitC->bitPos;
210 139538332 : bitC->bitPos += nbBits;
211 139538332 : }
212 :
213 : /*! BIT_flushBitsFast() :
214 : * unsafe version; does not check buffer overflow */
215 35012940 : MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC)
216 : {
217 35012940 : size_t const nbBytes = bitC->bitPos >> 3;
218 35012940 : MEM_writeLEST(bitC->ptr, bitC->bitContainer);
219 35012940 : bitC->ptr += nbBytes;
220 35012940 : bitC->bitPos &= 7;
221 35012940 : bitC->bitContainer >>= nbBytes*8; /* if bitPos >= sizeof(bitContainer)*8 --> undefined behavior */
222 35012940 : }
223 :
224 : /*! BIT_flushBits() :
225 : * safe version; check for buffer overflow, and prevents it.
226 : * note : does not signal buffer overflow. This will be revealed later on using BIT_closeCStream() */
227 11135682 : MEM_STATIC void BIT_flushBits(BIT_CStream_t* bitC)
228 : {
229 11135682 : size_t const nbBytes = bitC->bitPos >> 3;
230 11135682 : MEM_writeLEST(bitC->ptr, bitC->bitContainer);
231 11135682 : bitC->ptr += nbBytes;
232 11135682 : if (bitC->ptr > bitC->endPtr) bitC->ptr = bitC->endPtr;
233 11135682 : bitC->bitPos &= 7;
234 11135682 : bitC->bitContainer >>= nbBytes*8; /* if bitPos >= sizeof(bitContainer)*8 --> undefined behavior */
235 11135682 : }
236 :
237 : /*! BIT_closeCStream() :
238 : * @return : size of CStream, in bytes,
239 : or 0 if it could not fit into dstBuffer */
240 11576 : MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t* bitC)
241 : {
242 11576 : BIT_addBitsFast(bitC, 1, 1); /* endMark */
243 11576 : BIT_flushBits(bitC);
244 :
245 11576 : if (bitC->ptr >= bitC->endPtr) return 0; /* doesn't fit within authorized budget : cancel */
246 :
247 11576 : return (bitC->ptr - bitC->startPtr) + (bitC->bitPos > 0);
248 : }
249 :
250 :
251 : /*-********************************************************
252 : * bitStream decoding
253 : **********************************************************/
254 : /*! BIT_initDStream() :
255 : * Initialize a BIT_DStream_t.
256 : * `bitD` : a pointer to an already allocated BIT_DStream_t structure.
257 : * `srcSize` must be the *exact* size of the bitStream, in bytes.
258 : * @return : size of stream (== srcSize) or an errorCode if a problem is detected
259 : */
260 11416 : MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
261 : {
262 11416 : if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
263 :
264 11416 : if (srcSize >= sizeof(bitD->bitContainer)) { /* normal case */
265 11366 : bitD->start = (const char*)srcBuffer;
266 11366 : bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer);
267 11366 : bitD->bitContainer = MEM_readLEST(bitD->ptr);
268 11366 : { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
269 11366 : bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0;
270 11366 : if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
271 : } else {
272 50 : bitD->start = (const char*)srcBuffer;
273 50 : bitD->ptr = bitD->start;
274 50 : bitD->bitContainer = *(const BYTE*)(bitD->start);
275 50 : switch(srcSize)
276 : {
277 6 : case 7: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);
278 20 : case 6: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer)*8 - 24);
279 32 : case 5: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer)*8 - 32);
280 42 : case 4: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[3]) << 24;
281 50 : case 3: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[2]) << 16;
282 50 : case 2: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[1]) << 8;
283 : default:;
284 : }
285 50 : { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
286 50 : bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0;
287 50 : if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
288 50 : bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8;
289 : }
290 :
291 11416 : return srcSize;
292 : }
293 :
294 : MEM_STATIC size_t BIT_getUpperBits(size_t bitContainer, U32 const start)
295 : {
296 : return bitContainer >> start;
297 : }
298 :
299 : MEM_STATIC size_t BIT_getMiddleBits(size_t bitContainer, U32 const start, U32 const nbBits)
300 : {
301 : #if defined(__BMI__) && defined(__GNUC__) /* experimental */
302 : # if defined(__x86_64__)
303 : if (sizeof(bitContainer)==8)
304 : return _bextr_u64(bitContainer, start, nbBits);
305 : else
306 : # endif
307 : return _bextr_u32(bitContainer, start, nbBits);
308 : #else
309 : return (bitContainer >> start) & BIT_mask[nbBits];
310 : #endif
311 : }
312 :
313 : MEM_STATIC size_t BIT_getLowerBits(size_t bitContainer, U32 const nbBits)
314 : {
315 : return bitContainer & BIT_mask[nbBits];
316 : }
317 :
318 : /*! BIT_lookBits() :
319 : * Provides next n bits from local register.
320 : * local register is not modified.
321 : * On 32-bits, maxNbBits==24.
322 : * On 64-bits, maxNbBits==56.
323 : * @return : value extracted
324 : */
325 41168788 : MEM_STATIC size_t BIT_lookBits(const BIT_DStream_t* bitD, U32 nbBits)
326 : {
327 : #if defined(__BMI__) && defined(__GNUC__) /* experimental; fails if bitD->bitsConsumed + nbBits > sizeof(bitD->bitContainer)*8 */
328 : return BIT_getMiddleBits(bitD->bitContainer, (sizeof(bitD->bitContainer)*8) - bitD->bitsConsumed - nbBits, nbBits);
329 : #else
330 41168788 : U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1;
331 41168788 : return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
332 : #endif
333 : }
334 :
335 : /*! BIT_lookBitsFast() :
336 : * unsafe version; only works only if nbBits >= 1 */
337 116526234 : MEM_STATIC size_t BIT_lookBitsFast(const BIT_DStream_t* bitD, U32 nbBits)
338 : {
339 116526234 : U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1;
340 116526234 : return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
341 : }
342 :
343 157695022 : MEM_STATIC void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits)
344 : {
345 157695022 : bitD->bitsConsumed += nbBits;
346 157695022 : }
347 :
348 : /*! BIT_readBits() :
349 : * Read (consume) next n bits from local register and update.
350 : * Pay attention to not read more than nbBits contained into local register.
351 : * @return : extracted value.
352 : */
353 41168788 : MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, U32 nbBits)
354 : {
355 41168788 : size_t const value = BIT_lookBits(bitD, nbBits);
356 41168788 : BIT_skipBits(bitD, nbBits);
357 41168788 : return value;
358 : }
359 :
360 : /*! BIT_readBitsFast() :
361 : * unsafe version; only works only if nbBits >= 1 */
362 231524 : MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, U32 nbBits)
363 : {
364 231524 : size_t const value = BIT_lookBitsFast(bitD, nbBits);
365 231524 : BIT_skipBits(bitD, nbBits);
366 231524 : return value;
367 : }
368 :
369 : /*! BIT_reloadDStream() :
370 : * Refill `BIT_DStream_t` from src buffer previously defined (see BIT_initDStream() ).
371 : * This function is safe, it guarantees it will not read beyond src buffer.
372 : * @return : status of `BIT_DStream_t` internal register.
373 : if status == unfinished, internal register is filled with >= (sizeof(bitD->bitContainer)*8 - 7) bits */
374 40433060 : MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD)
375 : {
376 40433060 : if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should not happen => corruption detected */
377 3412 : return BIT_DStream_overflow;
378 :
379 40429648 : if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) {
380 40245276 : bitD->ptr -= bitD->bitsConsumed >> 3;
381 40245276 : bitD->bitsConsumed &= 7;
382 40245276 : bitD->bitContainer = MEM_readLEST(bitD->ptr);
383 40245276 : return BIT_DStream_unfinished;
384 : }
385 184372 : if (bitD->ptr == bitD->start) {
386 145900 : if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
387 6394 : return BIT_DStream_completed;
388 : }
389 38472 : { U32 nbBytes = bitD->bitsConsumed >> 3;
390 38472 : BIT_DStream_status result = BIT_DStream_unfinished;
391 38472 : if (bitD->ptr - nbBytes < bitD->start) {
392 6430 : nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
393 6430 : result = BIT_DStream_endOfBuffer;
394 : }
395 38472 : bitD->ptr -= nbBytes;
396 38472 : bitD->bitsConsumed -= nbBytes*8;
397 38472 : bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
398 38472 : return result;
399 : }
400 : }
401 :
402 : /*! BIT_endOfDStream() :
403 : * @return Tells if DStream has exactly reached its end (all bits consumed).
404 : */
405 8004 : MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)
406 : {
407 8004 : return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
408 : }
409 :
410 : #if defined (__cplusplus)
411 : }
412 : #endif
413 :
414 : #endif /* BITSTREAM_H_MODULE */
|
