Commit | Line | Data |
---|---|---|
73f3d1b4 NT |
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 | ****************************************************************/ | |
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() ) */ | |
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 ! */ | |
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 */ | |
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 */ | |
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() */ | |
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 */ | |
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 | */ | |
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 | case 6: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[5]) << (sizeof(bitD->bitContainer) * 8 - 24); | |
263 | case 5: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[4]) << (sizeof(bitD->bitContainer) * 8 - 32); | |
264 | case 4: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[3]) << 24; | |
265 | case 3: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[2]) << 16; | |
266 | case 2: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[1]) << 8; | |
267 | default:; | |
268 | } | |
269 | { | |
270 | BYTE const lastByte = ((const BYTE *)srcBuffer)[srcSize - 1]; | |
271 | bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0; | |
272 | if (lastByte == 0) | |
273 | return ERROR(GENERIC); /* endMark not present */ | |
274 | } | |
275 | bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize) * 8; | |
276 | } | |
277 | ||
278 | return srcSize; | |
279 | } | |
280 | ||
281 | ZSTD_STATIC size_t BIT_getUpperBits(size_t bitContainer, U32 const start) { return bitContainer >> start; } | |
282 | ||
283 | ZSTD_STATIC size_t BIT_getMiddleBits(size_t bitContainer, U32 const start, U32 const nbBits) { return (bitContainer >> start) & BIT_mask[nbBits]; } | |
284 | ||
285 | ZSTD_STATIC size_t BIT_getLowerBits(size_t bitContainer, U32 const nbBits) { return bitContainer & BIT_mask[nbBits]; } | |
286 | ||
287 | /*! BIT_lookBits() : | |
288 | * Provides next n bits from local register. | |
289 | * local register is not modified. | |
290 | * On 32-bits, maxNbBits==24. | |
291 | * On 64-bits, maxNbBits==56. | |
292 | * @return : value extracted | |
293 | */ | |
294 | ZSTD_STATIC size_t BIT_lookBits(const BIT_DStream_t *bitD, U32 nbBits) | |
295 | { | |
296 | U32 const bitMask = sizeof(bitD->bitContainer) * 8 - 1; | |
297 | return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask - nbBits) & bitMask); | |
298 | } | |
299 | ||
300 | /*! BIT_lookBitsFast() : | |
301 | * unsafe version; only works only if nbBits >= 1 */ | |
302 | ZSTD_STATIC size_t BIT_lookBitsFast(const BIT_DStream_t *bitD, U32 nbBits) | |
303 | { | |
304 | U32 const bitMask = sizeof(bitD->bitContainer) * 8 - 1; | |
305 | return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask + 1) - nbBits) & bitMask); | |
306 | } | |
307 | ||
308 | ZSTD_STATIC void BIT_skipBits(BIT_DStream_t *bitD, U32 nbBits) { bitD->bitsConsumed += nbBits; } | |
309 | ||
310 | /*! BIT_readBits() : | |
311 | * Read (consume) next n bits from local register and update. | |
312 | * Pay attention to not read more than nbBits contained into local register. | |
313 | * @return : extracted value. | |
314 | */ | |
315 | ZSTD_STATIC size_t BIT_readBits(BIT_DStream_t *bitD, U32 nbBits) | |
316 | { | |
317 | size_t const value = BIT_lookBits(bitD, nbBits); | |
318 | BIT_skipBits(bitD, nbBits); | |
319 | return value; | |
320 | } | |
321 | ||
322 | /*! BIT_readBitsFast() : | |
323 | * unsafe version; only works only if nbBits >= 1 */ | |
324 | ZSTD_STATIC size_t BIT_readBitsFast(BIT_DStream_t *bitD, U32 nbBits) | |
325 | { | |
326 | size_t const value = BIT_lookBitsFast(bitD, nbBits); | |
327 | BIT_skipBits(bitD, nbBits); | |
328 | return value; | |
329 | } | |
330 | ||
331 | /*! BIT_reloadDStream() : | |
332 | * Refill `bitD` from buffer previously set in BIT_initDStream() . | |
333 | * This function is safe, it guarantees it will not read beyond src buffer. | |
334 | * @return : status of `BIT_DStream_t` internal register. | |
335 | if status == BIT_DStream_unfinished, internal register is filled with >= (sizeof(bitD->bitContainer)*8 - 7) bits */ | |
336 | ZSTD_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t *bitD) | |
337 | { | |
338 | if (bitD->bitsConsumed > (sizeof(bitD->bitContainer) * 8)) /* should not happen => corruption detected */ | |
339 | return BIT_DStream_overflow; | |
340 | ||
341 | if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) { | |
342 | bitD->ptr -= bitD->bitsConsumed >> 3; | |
343 | bitD->bitsConsumed &= 7; | |
344 | bitD->bitContainer = ZSTD_readLEST(bitD->ptr); | |
345 | return BIT_DStream_unfinished; | |
346 | } | |
347 | if (bitD->ptr == bitD->start) { | |
348 | if (bitD->bitsConsumed < sizeof(bitD->bitContainer) * 8) | |
349 | return BIT_DStream_endOfBuffer; | |
350 | return BIT_DStream_completed; | |
351 | } | |
352 | { | |
353 | U32 nbBytes = bitD->bitsConsumed >> 3; | |
354 | BIT_DStream_status result = BIT_DStream_unfinished; | |
355 | if (bitD->ptr - nbBytes < bitD->start) { | |
356 | nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */ | |
357 | result = BIT_DStream_endOfBuffer; | |
358 | } | |
359 | bitD->ptr -= nbBytes; | |
360 | bitD->bitsConsumed -= nbBytes * 8; | |
361 | bitD->bitContainer = ZSTD_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */ | |
362 | return result; | |
363 | } | |
364 | } | |
365 | ||
366 | /*! BIT_endOfDStream() : | |
367 | * @return Tells if DStream has exactly reached its end (all bits consumed). | |
368 | */ | |
369 | ZSTD_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t *DStream) | |
370 | { | |
371 | return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer) * 8)); | |
372 | } | |
373 | ||
374 | #endif /* BITSTREAM_H_MODULE */ |