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