blob: e6c2228e9eece494cecda8891f4e88deace5b1f6 [file] [log] [blame]
Yann Colletb1f3f4b2015-10-18 22:18:32 +01001/* ******************************************************************
2 bitstream
3 Part of NewGen Entropy library
4 header file (to include)
5 Copyright (C) 2013-2015, 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 - Public forum : https://groups.google.com/forum/#!forum/lz4c
35****************************************************************** */
36#ifndef BITSTREAM_H_MODULE
37#define BITSTREAM_H_MODULE
38
39#if defined (__cplusplus)
40extern "C" {
41#endif
42
43
44/*
45* This API consists of small unitary functions, which highly benefit from being inlined.
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* Includes
52******************************************/
53#include "mem.h" /* unaligned access routines */
54#include "error.h" /* error codes and messages */
55
56
57/********************************************
58* bitStream compression API (write forward)
59********************************************/
60/*
61* bitStream can mix input from multiple sources.
62* A critical property of these streams is that they encode and decode in **reverse** direction.
63* So the first bit sequence you add will be the last to be read, like a LIFO stack.
64*/
65typedef struct
66{
67 size_t bitContainer;
68 int bitPos;
69 char* startPtr;
70 char* ptr;
71 char* endPtr;
72} BIT_CStream_t;
73
74MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC, void* dstBuffer, size_t maxDstSize);
75MEM_STATIC void BIT_addBits(BIT_CStream_t* bitC, size_t value, unsigned nbBits);
76MEM_STATIC void BIT_flushBits(BIT_CStream_t* bitC);
77MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t* bitC);
78
79/*
80* Start by initCStream, providing the maximum size of write buffer to write into.
81* bitStream will never write outside of this buffer.
82* buffer must be at least as large as a size_t, otherwise function result will be an error code.
83*
84* bits are first added to a local register.
85* Local register is size_t, hence 64-bits on 64-bits systems, or 32-bits on 32-bits systems.
86* Writing data into memory is a manual operation, performed by the flushBits function.
87* Hence keep track how many bits are potentially stored into local register to avoid register overflow.
88* After a flushBits, a maximum of 7 bits might still be stored into local register.
89*
90* Avoid storing elements of more than 25 bits if you want compatibility with 32-bits bitstream readers.
91*
92* Last operation is to close the bitStream.
93* The function returns the final size of CStream in bytes.
94* If data couldn't fit into dstBuffer, it will return a 0 ( == not storable)
95*/
96
97
98/**********************************************
99* bitStream decompression API (read backward)
100**********************************************/
101typedef struct
102{
103 size_t bitContainer;
104 unsigned bitsConsumed;
105 const char* ptr;
106 const char* start;
107} BIT_DStream_t;
108
109typedef enum { BIT_DStream_unfinished = 0,
110 BIT_DStream_endOfBuffer = 1,
111 BIT_DStream_completed = 2,
112 BIT_DStream_overflow = 3 } BIT_DStream_status; /* result of BIT_reloadDStream() */
113 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
114
115MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
116MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
117MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD);
118MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);
119
120
121/*
122* Start by invoking BIT_initDStream().
123* A chunk of the bitStream is then stored into a local register.
124* Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t).
125* You can then retrieve bitFields stored into the local register, **in reverse order**.
126* Local register is manually filled from memory by the BIT_reloadDStream() method.
127* A reload guarantee a minimum of ((8*sizeof(size_t))-7) bits when its result is BIT_DStream_unfinished.
128* Otherwise, it can be less than that, so proceed accordingly.
129* Checking if DStream has reached its end can be performed with BIT_endOfDStream()
130*/
131
132
133/******************************************
134* unsafe API
135******************************************/
136MEM_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
139MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC);
140/* unsafe version; does not check buffer overflow */
141
142MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);
143/* faster, but works only if nbBits >= 1 */
144
145
146
147/****************************************************************
148* Helper functions
149****************************************************************/
150MEM_STATIC unsigned BIT_highbit32 (register U32 val)
151{
152# if defined(_MSC_VER) /* Visual */
Yann Collet4114f952015-10-30 06:40:22 +0100153 unsigned long r=0;
Yann Colletb1f3f4b2015-10-18 22:18:32 +0100154 _BitScanReverse ( &r, val );
155 return (unsigned) r;
156# elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
157 return 31 - __builtin_clz (val);
158# else /* Software version */
159 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 };
160 U32 v = val;
161 unsigned r;
162 v |= v >> 1;
163 v |= v >> 2;
164 v |= v >> 4;
165 v |= v >> 8;
166 v |= v >> 16;
167 r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
168 return r;
169# endif
170}
171
172
173/****************************************************************
174* bitStream encoding
175****************************************************************/
176
177MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC, void* startPtr, size_t maxSize)
178{
179 bitC->bitContainer = 0;
180 bitC->bitPos = 0;
181 bitC->startPtr = (char*)startPtr;
182 bitC->ptr = bitC->startPtr;
183 bitC->endPtr = bitC->startPtr + maxSize - sizeof(bitC->ptr);
184 if (maxSize < sizeof(bitC->ptr)) return ERROR(dstSize_tooSmall);
185 return 0;
186}
187
188MEM_STATIC void BIT_addBits(BIT_CStream_t* bitC, size_t value, unsigned nbBits)
189{
190 static const unsigned 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 }; /* up to 25 bits */
191 bitC->bitContainer |= (value & mask[nbBits]) << bitC->bitPos;
192 bitC->bitPos += nbBits;
193}
194
195/*! BIT_addBitsFast
196 * works only if `value` is _clean_, meaning all high bits above nbBits are 0 */
197MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC, size_t value, unsigned nbBits)
198{
199 bitC->bitContainer |= value << bitC->bitPos;
200 bitC->bitPos += nbBits;
201}
202
203/*! BIT_flushBitsFast
204 * unsafe version; does not check buffer overflow */
205MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC)
206{
207 size_t nbBytes = bitC->bitPos >> 3;
208 MEM_writeLEST(bitC->ptr, bitC->bitContainer);
209 bitC->ptr += nbBytes;
210 bitC->bitPos &= 7;
211 bitC->bitContainer >>= nbBytes*8;
212}
213
214MEM_STATIC void BIT_flushBits(BIT_CStream_t* bitC)
215{
216 size_t nbBytes = bitC->bitPos >> 3;
217 MEM_writeLEST(bitC->ptr, bitC->bitContainer);
218 bitC->ptr += nbBytes;
219 if (bitC->ptr > bitC->endPtr) bitC->ptr = bitC->endPtr;
220 bitC->bitPos &= 7;
221 bitC->bitContainer >>= nbBytes*8;
222}
223
224/*! BIT_closeCStream
225 * @result : size of CStream, in bytes, or 0 if it cannot fit into dstBuffer */
226MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t* bitC)
227{
228 char* endPtr;
229
230 BIT_addBitsFast(bitC, 1, 1); /* endMark */
231 BIT_flushBits(bitC);
232
233 if (bitC->ptr >= bitC->endPtr) /* too close to buffer's end */
234 return 0; /* not storable */
235
236 endPtr = bitC->ptr;
237 endPtr += bitC->bitPos > 0; /* remaining bits (incomplete byte) */
238
239 return (endPtr - bitC->startPtr);
240}
241
242
243/**********************************************************
244* bitStream decoding
245**********************************************************/
246
247/*!BIT_initDStream
248* Initialize a BIT_DStream_t.
249* @bitD : a pointer to an already allocated BIT_DStream_t structure
250* @srcBuffer must point at the beginning of a bitStream
251* @srcSize must be the exact size of the bitStream
252* @result : size of stream (== srcSize) or an errorCode if a problem is detected
253*/
254MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
255{
256 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
257
258 if (srcSize >= sizeof(size_t)) /* normal case */
259 {
260 U32 contain32;
261 bitD->start = (const char*)srcBuffer;
262 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(size_t);
263 bitD->bitContainer = MEM_readLEST(bitD->ptr);
264 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
265 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
266 bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
267 }
268 else
269 {
270 U32 contain32;
271 bitD->start = (const char*)srcBuffer;
272 bitD->ptr = bitD->start;
273 bitD->bitContainer = *(const BYTE*)(bitD->start);
274 switch(srcSize)
275 {
276 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[6]) << (sizeof(size_t)*8 - 16);
277 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[5]) << (sizeof(size_t)*8 - 24);
278 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[4]) << (sizeof(size_t)*8 - 32);
279 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[3]) << 24;
280 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[2]) << 16;
281 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[1]) << 8;
282 default:;
283 }
284 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
285 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
286 bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
287 bitD->bitsConsumed += (U32)(sizeof(size_t) - srcSize)*8;
288 }
289
290 return srcSize;
291}
292
293/*!BIT_lookBits
294 * Provides next n bits from local register
295 * local register is not modified (bits are still present for next read/look)
296 * On 32-bits, maxNbBits==25
297 * On 64-bits, maxNbBits==57
298 * @return : value extracted
299 */
300MEM_STATIC size_t BIT_lookBits(BIT_DStream_t* bitD, U32 nbBits)
301{
302 const U32 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 */
308MEM_STATIC size_t BIT_lookBitsFast(BIT_DStream_t* bitD, U32 nbBits)
309{
310 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
311 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
312}
313
314MEM_STATIC void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits)
315{
316 bitD->bitsConsumed += nbBits;
317}
318
319/*!BIT_readBits
320 * Read next n bits from local register.
321 * pay attention to not read more than nbBits contained into local register.
322 * @return : extracted value.
323 */
324MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, U32 nbBits)
325{
326 size_t value = BIT_lookBits(bitD, nbBits);
327 BIT_skipBits(bitD, nbBits);
328 return value;
329}
330
331/*!BIT_readBitsFast :
332* unsafe version; only works only if nbBits >= 1 */
333MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, U32 nbBits)
334{
335 size_t value = BIT_lookBitsFast(bitD, nbBits);
336 BIT_skipBits(bitD, nbBits);
337 return value;
338}
339
340MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD)
341{
342 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */
343 return BIT_DStream_overflow;
344
345 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer))
346 {
347 bitD->ptr -= bitD->bitsConsumed >> 3;
348 bitD->bitsConsumed &= 7;
349 bitD->bitContainer = MEM_readLEST(bitD->ptr);
350 return BIT_DStream_unfinished;
351 }
352 if (bitD->ptr == bitD->start)
353 {
354 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
355 return BIT_DStream_completed;
356 }
357 {
358 U32 nbBytes = bitD->bitsConsumed >> 3;
359 BIT_DStream_status result = BIT_DStream_unfinished;
360 if (bitD->ptr - nbBytes < bitD->start)
361 {
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 = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
368 return result;
369 }
370}
371
372/*! BIT_endOfDStream
373* @return Tells if DStream has reached its exact end
374*/
375MEM_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#if defined (__cplusplus)
381}
382#endif
383
384#endif /* BITSTREAM_H_MODULE */