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 * This program is free software; you can redistribute it and/or modify it under
33 * the terms of the GNU General Public License version 2 as published by the
34 * Free Software Foundation. This program is dual-licensed; you may select
35 * either version 2 of the GNU General Public License ("GPL") or BSD license
36 * ("BSD").
37 *
38 * You can contact the author at :
39 * - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
40 */
41 #ifndef BITSTREAM_H_MODULE
42 #define BITSTREAM_H_MODULE
43
44 /*
45 * This API consists of small unitary functions, which must be inlined for best performance.
46 * Since link-time-optimization is not available for all compilers,
47 * these functions are defined into a .h to be included.
48 */
49
50 /*-****************************************
51 * Dependencies
52 ******************************************/
53 #include "error_private.h" /* error codes and messages */
54 #include "mem.h" /* unaligned access routines */
55
56 /*=========================================
57 * Target specific
58 =========================================*/
59 #define STREAM_ACCUMULATOR_MIN_32 25
60 #define STREAM_ACCUMULATOR_MIN_64 57
61 #define STREAM_ACCUMULATOR_MIN ((U32)(ZSTD_32bits() ? STREAM_ACCUMULATOR_MIN_32 : STREAM_ACCUMULATOR_MIN_64))
62
63 /*-******************************************
64 * bitStream encoding API (write forward)
65 ********************************************/
66 /* bitStream can mix input from multiple sources.
67 * A critical property of these streams is that they encode and decode in **reverse** direction.
68 * So the first bit sequence you add will be the last to be read, like a LIFO stack.
69 */
70 typedef struct {
71 size_t bitContainer;
72 int bitPos;
73 char *startPtr;
74 char *ptr;
75 char *endPtr;
76 } BIT_CStream_t;
77
78 ZSTD_STATIC size_t BIT_initCStream(BIT_CStream_t *bitC, void *dstBuffer, size_t dstCapacity);
79 ZSTD_STATIC void BIT_addBits(BIT_CStream_t *bitC, size_t value, unsigned nbBits);
80 ZSTD_STATIC void BIT_flushBits(BIT_CStream_t *bitC);
81 ZSTD_STATIC size_t BIT_closeCStream(BIT_CStream_t *bitC);
82
83 /* Start with initCStream, providing the size of buffer to write into.
84 * bitStream will never write outside of this buffer.
85 * `dstCapacity` must be >= sizeof(bitD->bitContainer), otherwise @return will be an error code.
86 *
87 * bits are first added to a local register.
88 * Local register is size_t, hence 64-bits on 64-bits systems, or 32-bits on 32-bits systems.
89 * Writing data into memory is an explicit operation, performed by the flushBits function.
90 * Hence keep track how many bits are potentially stored into local register to avoid register overflow.
91 * After a flushBits, a maximum of 7 bits might still be stored into local register.
92 *
93 * Avoid storing elements of more than 24 bits if you want compatibility with 32-bits bitstream readers.
94 *
95 * Last operation is to close the bitStream.
96 * The function returns the final size of CStream in bytes.
97 * If data couldn't fit into `dstBuffer`, it will return a 0 ( == not storable)
98 */
99
100 /*-********************************************
101 * bitStream decoding API (read backward)
102 **********************************************/
103 typedef struct {
104 size_t bitContainer;
105 unsigned bitsConsumed;
106 const char *ptr;
107 const char *start;
108 } BIT_DStream_t;
109
110 typedef enum {
111 BIT_DStream_unfinished = 0,
112 BIT_DStream_endOfBuffer = 1,
113 BIT_DStream_completed = 2,
114 BIT_DStream_overflow = 3
115 } BIT_DStream_status; /* result of BIT_reloadDStream() */
116 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
117
118 ZSTD_STATIC size_t BIT_initDStream(BIT_DStream_t *bitD, const void *srcBuffer, size_t srcSize);
119 ZSTD_STATIC size_t BIT_readBits(BIT_DStream_t *bitD, unsigned nbBits);
120 ZSTD_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t *bitD);
121 ZSTD_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t *bitD);
122
123 /* Start by invoking BIT_initDStream().
124 * A chunk of the bitStream is then stored into a local register.
125 * Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t).
126 * You can then retrieve bitFields stored into the local register, **in reverse order**.
127 * Local register is explicitly reloaded from memory by the BIT_reloadDStream() method.
128 * A reload guarantee a minimum of ((8*sizeof(bitD->bitContainer))-7) bits when its result is BIT_DStream_unfinished.
129 * Otherwise, it can be less than that, so proceed accordingly.
130 * Checking if DStream has reached its end can be performed with BIT_endOfDStream().
131 */
132
133 /*-****************************************
134 * unsafe API
135 ******************************************/
136 ZSTD_STATIC void BIT_addBitsFast(BIT_CStream_t *bitC, size_t value, unsigned nbBits);
137 /* faster, but works only if value is "clean", meaning all high bits above nbBits are 0 */
138
139 ZSTD_STATIC void BIT_flushBitsFast(BIT_CStream_t *bitC);
140 /* unsafe version; does not check buffer overflow */
141
142 ZSTD_STATIC size_t BIT_readBitsFast(BIT_DStream_t *bitD, unsigned nbBits);
143 /* faster, but works only if nbBits >= 1 */
144
145 /*-**************************************************************
146 * Internal functions
147 ****************************************************************/
BIT_highbit32(register U32 val)148 ZSTD_STATIC unsigned BIT_highbit32(register U32 val) { return 31 - __builtin_clz(val); }
149
150 /*===== Local Constants =====*/
151 static const unsigned BIT_mask[] = {0, 1, 3, 7, 0xF, 0x1F, 0x3F, 0x7F, 0xFF,
152 0x1FF, 0x3FF, 0x7FF, 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF, 0x1FFFF,
153 0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF, 0x3FFFFF, 0x7FFFFF, 0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF}; /* up to 26 bits */
154
155 /*-**************************************************************
156 * bitStream encoding
157 ****************************************************************/
158 /*! BIT_initCStream() :
159 * `dstCapacity` must be > sizeof(void*)
160 * @return : 0 if success,
161 otherwise an error code (can be tested using ERR_isError() ) */
BIT_initCStream(BIT_CStream_t * bitC,void * startPtr,size_t dstCapacity)162 ZSTD_STATIC size_t BIT_initCStream(BIT_CStream_t *bitC, void *startPtr, size_t dstCapacity)
163 {
164 bitC->bitContainer = 0;
165 bitC->bitPos = 0;
166 bitC->startPtr = (char *)startPtr;
167 bitC->ptr = bitC->startPtr;
168 bitC->endPtr = bitC->startPtr + dstCapacity - sizeof(bitC->ptr);
169 if (dstCapacity <= sizeof(bitC->ptr))
170 return ERROR(dstSize_tooSmall);
171 return 0;
172 }
173
174 /*! BIT_addBits() :
175 can add up to 26 bits into `bitC`.
176 Does not check for register overflow ! */
BIT_addBits(BIT_CStream_t * bitC,size_t value,unsigned nbBits)177 ZSTD_STATIC void BIT_addBits(BIT_CStream_t *bitC, size_t value, unsigned nbBits)
178 {
179 bitC->bitContainer |= (value & BIT_mask[nbBits]) << bitC->bitPos;
180 bitC->bitPos += nbBits;
181 }
182
183 /*! BIT_addBitsFast() :
184 * works only if `value` is _clean_, meaning all high bits above nbBits are 0 */
BIT_addBitsFast(BIT_CStream_t * bitC,size_t value,unsigned nbBits)185 ZSTD_STATIC void BIT_addBitsFast(BIT_CStream_t *bitC, size_t value, unsigned nbBits)
186 {
187 bitC->bitContainer |= value << bitC->bitPos;
188 bitC->bitPos += nbBits;
189 }
190
191 /*! BIT_flushBitsFast() :
192 * unsafe version; does not check buffer overflow */
BIT_flushBitsFast(BIT_CStream_t * bitC)193 ZSTD_STATIC void BIT_flushBitsFast(BIT_CStream_t *bitC)
194 {
195 size_t const nbBytes = bitC->bitPos >> 3;
196 ZSTD_writeLEST(bitC->ptr, bitC->bitContainer);
197 bitC->ptr += nbBytes;
198 bitC->bitPos &= 7;
199 bitC->bitContainer >>= nbBytes * 8; /* if bitPos >= sizeof(bitContainer)*8 --> undefined behavior */
200 }
201
202 /*! BIT_flushBits() :
203 * safe version; check for buffer overflow, and prevents it.
204 * note : does not signal buffer overflow. This will be revealed later on using BIT_closeCStream() */
BIT_flushBits(BIT_CStream_t * bitC)205 ZSTD_STATIC void BIT_flushBits(BIT_CStream_t *bitC)
206 {
207 size_t const nbBytes = bitC->bitPos >> 3;
208 ZSTD_writeLEST(bitC->ptr, bitC->bitContainer);
209 bitC->ptr += nbBytes;
210 if (bitC->ptr > bitC->endPtr)
211 bitC->ptr = bitC->endPtr;
212 bitC->bitPos &= 7;
213 bitC->bitContainer >>= nbBytes * 8; /* if bitPos >= sizeof(bitContainer)*8 --> undefined behavior */
214 }
215
216 /*! BIT_closeCStream() :
217 * @return : size of CStream, in bytes,
218 or 0 if it could not fit into dstBuffer */
BIT_closeCStream(BIT_CStream_t * bitC)219 ZSTD_STATIC size_t BIT_closeCStream(BIT_CStream_t *bitC)
220 {
221 BIT_addBitsFast(bitC, 1, 1); /* endMark */
222 BIT_flushBits(bitC);
223
224 if (bitC->ptr >= bitC->endPtr)
225 return 0; /* doesn't fit within authorized budget : cancel */
226
227 return (bitC->ptr - bitC->startPtr) + (bitC->bitPos > 0);
228 }
229
230 /*-********************************************************
231 * bitStream decoding
232 **********************************************************/
233 /*! BIT_initDStream() :
234 * Initialize a BIT_DStream_t.
235 * `bitD` : a pointer to an already allocated BIT_DStream_t structure.
236 * `srcSize` must be the *exact* size of the bitStream, in bytes.
237 * @return : size of stream (== srcSize) or an errorCode if a problem is detected
238 */
BIT_initDStream(BIT_DStream_t * bitD,const void * srcBuffer,size_t srcSize)239 ZSTD_STATIC size_t BIT_initDStream(BIT_DStream_t *bitD, const void *srcBuffer, size_t srcSize)
240 {
241 if (srcSize < 1) {
242 memset(bitD, 0, sizeof(*bitD));
243 return ERROR(srcSize_wrong);
244 }
245
246 if (srcSize >= sizeof(bitD->bitContainer)) { /* normal case */
247 bitD->start = (const char *)srcBuffer;
248 bitD->ptr = (const char *)srcBuffer + srcSize - sizeof(bitD->bitContainer);
249 bitD->bitContainer = ZSTD_readLEST(bitD->ptr);
250 {
251 BYTE const lastByte = ((const BYTE *)srcBuffer)[srcSize - 1];
252 bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0; /* ensures bitsConsumed is always set */
253 if (lastByte == 0)
254 return ERROR(GENERIC); /* endMark not present */
255 }
256 } else {
257 bitD->start = (const char *)srcBuffer;
258 bitD->ptr = bitD->start;
259 bitD->bitContainer = *(const BYTE *)(bitD->start);
260 switch (srcSize) {
261 case 7: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[6]) << (sizeof(bitD->bitContainer) * 8 - 16);
262 fallthrough;
263 case 6: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[5]) << (sizeof(bitD->bitContainer) * 8 - 24);
264 fallthrough;
265 case 5: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[4]) << (sizeof(bitD->bitContainer) * 8 - 32);
266 fallthrough;
267 case 4: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[3]) << 24;
268 fallthrough;
269 case 3: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[2]) << 16;
270 fallthrough;
271 case 2: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[1]) << 8;
272 fallthrough;
273 default:;
274 }
275 {
276 BYTE const lastByte = ((const BYTE *)srcBuffer)[srcSize - 1];
277 bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0;
278 if (lastByte == 0)
279 return ERROR(GENERIC); /* endMark not present */
280 }
281 bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize) * 8;
282 }
283
284 return srcSize;
285 }
286
BIT_getUpperBits(size_t bitContainer,U32 const start)287 ZSTD_STATIC size_t BIT_getUpperBits(size_t bitContainer, U32 const start) { return bitContainer >> start; }
288
BIT_getMiddleBits(size_t bitContainer,U32 const start,U32 const nbBits)289 ZSTD_STATIC size_t BIT_getMiddleBits(size_t bitContainer, U32 const start, U32 const nbBits) { return (bitContainer >> start) & BIT_mask[nbBits]; }
290
BIT_getLowerBits(size_t bitContainer,U32 const nbBits)291 ZSTD_STATIC size_t BIT_getLowerBits(size_t bitContainer, U32 const nbBits) { return bitContainer & BIT_mask[nbBits]; }
292
293 /*! BIT_lookBits() :
294 * Provides next n bits from local register.
295 * local register is not modified.
296 * On 32-bits, maxNbBits==24.
297 * On 64-bits, maxNbBits==56.
298 * @return : value extracted
299 */
BIT_lookBits(const BIT_DStream_t * bitD,U32 nbBits)300 ZSTD_STATIC size_t BIT_lookBits(const BIT_DStream_t *bitD, U32 nbBits)
301 {
302 U32 const bitMask = sizeof(bitD->bitContainer) * 8 - 1;
303 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask - nbBits) & bitMask);
304 }
305
306 /*! BIT_lookBitsFast() :
307 * unsafe version; only works only if nbBits >= 1 */
BIT_lookBitsFast(const BIT_DStream_t * bitD,U32 nbBits)308 ZSTD_STATIC size_t BIT_lookBitsFast(const BIT_DStream_t *bitD, U32 nbBits)
309 {
310 U32 const bitMask = sizeof(bitD->bitContainer) * 8 - 1;
311 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask + 1) - nbBits) & bitMask);
312 }
313
BIT_skipBits(BIT_DStream_t * bitD,U32 nbBits)314 ZSTD_STATIC void BIT_skipBits(BIT_DStream_t *bitD, U32 nbBits) { bitD->bitsConsumed += nbBits; }
315
316 /*! BIT_readBits() :
317 * Read (consume) next n bits from local register and update.
318 * Pay attention to not read more than nbBits contained into local register.
319 * @return : extracted value.
320 */
BIT_readBits(BIT_DStream_t * bitD,U32 nbBits)321 ZSTD_STATIC size_t BIT_readBits(BIT_DStream_t *bitD, U32 nbBits)
322 {
323 size_t const value = BIT_lookBits(bitD, nbBits);
324 BIT_skipBits(bitD, nbBits);
325 return value;
326 }
327
328 /*! BIT_readBitsFast() :
329 * unsafe version; only works only if nbBits >= 1 */
BIT_readBitsFast(BIT_DStream_t * bitD,U32 nbBits)330 ZSTD_STATIC size_t BIT_readBitsFast(BIT_DStream_t *bitD, U32 nbBits)
331 {
332 size_t const value = BIT_lookBitsFast(bitD, nbBits);
333 BIT_skipBits(bitD, nbBits);
334 return value;
335 }
336
337 /*! BIT_reloadDStream() :
338 * Refill `bitD` from buffer previously set in BIT_initDStream() .
339 * This function is safe, it guarantees it will not read beyond src buffer.
340 * @return : status of `BIT_DStream_t` internal register.
341 if status == BIT_DStream_unfinished, internal register is filled with >= (sizeof(bitD->bitContainer)*8 - 7) bits */
BIT_reloadDStream(BIT_DStream_t * bitD)342 ZSTD_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t *bitD)
343 {
344 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer) * 8)) /* should not happen => corruption detected */
345 return BIT_DStream_overflow;
346
347 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) {
348 bitD->ptr -= bitD->bitsConsumed >> 3;
349 bitD->bitsConsumed &= 7;
350 bitD->bitContainer = ZSTD_readLEST(bitD->ptr);
351 return BIT_DStream_unfinished;
352 }
353 if (bitD->ptr == bitD->start) {
354 if (bitD->bitsConsumed < sizeof(bitD->bitContainer) * 8)
355 return BIT_DStream_endOfBuffer;
356 return BIT_DStream_completed;
357 }
358 {
359 U32 nbBytes = bitD->bitsConsumed >> 3;
360 BIT_DStream_status result = BIT_DStream_unfinished;
361 if (bitD->ptr - nbBytes < bitD->start) {
362 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
363 result = BIT_DStream_endOfBuffer;
364 }
365 bitD->ptr -= nbBytes;
366 bitD->bitsConsumed -= nbBytes * 8;
367 bitD->bitContainer = ZSTD_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
368 return result;
369 }
370 }
371
372 /*! BIT_endOfDStream() :
373 * @return Tells if DStream has exactly reached its end (all bits consumed).
374 */
BIT_endOfDStream(const BIT_DStream_t * DStream)375 ZSTD_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t *DStream)
376 {
377 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer) * 8));
378 }
379
380 #endif /* BITSTREAM_H_MODULE */
381
