source: thirdparty/blosc/internal-complibs/zstd-0.7.4/common/bitstream.h @ 8ebc79b

Revision 8ebc79b, 16.2 KB checked in by Hal Finkel <hfinkel@…>, 8 years ago (diff)

Add the other internal compression libraries from blocs

  • Property mode set to 100644
Line 
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)
39extern "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*/
71typedef struct
72{
73    size_t bitContainer;
74    int    bitPos;
75    char*  startPtr;
76    char*  ptr;
77    char*  endPtr;
78} BIT_CStream_t;
79
80MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC, void* dstBuffer, size_t dstCapacity);
81MEM_STATIC void   BIT_addBits(BIT_CStream_t* bitC, size_t value, unsigned nbBits);
82MEM_STATIC void   BIT_flushBits(BIT_CStream_t* bitC);
83MEM_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**********************************************/
106typedef struct
107{
108    size_t   bitContainer;
109    unsigned bitsConsumed;
110    const char* ptr;
111    const char* start;
112} BIT_DStream_t;
113
114typedef 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
120MEM_STATIC size_t   BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
121MEM_STATIC size_t   BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
122MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD);
123MEM_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******************************************/
140MEM_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
143MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC);
144/* unsafe version; does not check buffer overflow */
145
146MEM_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****************************************************************/
154MEM_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    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   =====*/
175static 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() ) */
185MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC, void* startPtr, size_t dstCapacity)
186{
187    bitC->bitContainer = 0;
188    bitC->bitPos = 0;
189    bitC->startPtr = (char*)startPtr;
190    bitC->ptr = bitC->startPtr;
191    bitC->endPtr = bitC->startPtr + dstCapacity - sizeof(bitC->ptr);
192    if (dstCapacity <= sizeof(bitC->ptr)) return ERROR(dstSize_tooSmall);
193    return 0;
194}
195
196/*! BIT_addBits() :
197    can add up to 26 bits into `bitC`.
198    Does not check for register overflow ! */
199MEM_STATIC void BIT_addBits(BIT_CStream_t* bitC, size_t value, unsigned nbBits)
200{
201    bitC->bitContainer |= (value & BIT_mask[nbBits]) << bitC->bitPos;
202    bitC->bitPos += nbBits;
203}
204
205/*! BIT_addBitsFast() :
206 *  works only if `value` is _clean_, meaning all high bits above nbBits are 0 */
207MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC, size_t value, unsigned nbBits)
208{
209    bitC->bitContainer |= value << bitC->bitPos;
210    bitC->bitPos += nbBits;
211}
212
213/*! BIT_flushBitsFast() :
214 *  unsafe version; does not check buffer overflow */
215MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC)
216{
217    size_t const nbBytes = bitC->bitPos >> 3;
218    MEM_writeLEST(bitC->ptr, bitC->bitContainer);
219    bitC->ptr += nbBytes;
220    bitC->bitPos &= 7;
221    bitC->bitContainer >>= nbBytes*8;   /* if bitPos >= sizeof(bitContainer)*8 --> undefined behavior */
222}
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() */
227MEM_STATIC void BIT_flushBits(BIT_CStream_t* bitC)
228{
229    size_t const nbBytes = bitC->bitPos >> 3;
230    MEM_writeLEST(bitC->ptr, bitC->bitContainer);
231    bitC->ptr += nbBytes;
232    if (bitC->ptr > bitC->endPtr) bitC->ptr = bitC->endPtr;
233    bitC->bitPos &= 7;
234    bitC->bitContainer >>= nbBytes*8;   /* if bitPos >= sizeof(bitContainer)*8 --> undefined behavior */
235}
236
237/*! BIT_closeCStream() :
238 *  @return : size of CStream, in bytes,
239              or 0 if it could not fit into dstBuffer */
240MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t* bitC)
241{
242    BIT_addBitsFast(bitC, 1, 1);   /* endMark */
243    BIT_flushBits(bitC);
244
245    if (bitC->ptr >= bitC->endPtr) return 0; /* doesn't fit within authorized budget : cancel */
246
247    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*/
260MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
261{
262    if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
263
264    if (srcSize >=  sizeof(bitD->bitContainer)) {  /* normal case */
265        bitD->start = (const char*)srcBuffer;
266        bitD->ptr   = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer);
267        bitD->bitContainer = MEM_readLEST(bitD->ptr);
268        { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
269          bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0;
270          if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
271    } else {
272        bitD->start = (const char*)srcBuffer;
273        bitD->ptr   = bitD->start;
274        bitD->bitContainer = *(const BYTE*)(bitD->start);
275        switch(srcSize)
276        {
277            case 7: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);
278            case 6: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer)*8 - 24);
279            case 5: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer)*8 - 32);
280            case 4: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[3]) << 24;
281            case 3: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[2]) << 16;
282            case 2: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[1]) <<  8;
283            default:;
284        }
285        { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
286          bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0;
287          if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
288        bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8;
289    }
290
291    return srcSize;
292}
293
294MEM_STATIC size_t BIT_getUpperBits(size_t bitContainer, U32 const start)
295{
296    return bitContainer >> start;
297}
298
299MEM_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
313MEM_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 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    U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1;
331    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 */
337MEM_STATIC size_t BIT_lookBitsFast(const BIT_DStream_t* bitD, U32 nbBits)
338{
339    U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1;
340    return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
341}
342
343MEM_STATIC void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits)
344{
345    bitD->bitsConsumed += nbBits;
346}
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 */
353MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, U32 nbBits)
354{
355    size_t const value = BIT_lookBits(bitD, nbBits);
356    BIT_skipBits(bitD, nbBits);
357    return value;
358}
359
360/*! BIT_readBitsFast() :
361*   unsafe version; only works only if nbBits >= 1 */
362MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, U32 nbBits)
363{
364    size_t const value = BIT_lookBitsFast(bitD, nbBits);
365    BIT_skipBits(bitD, nbBits);
366    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 */
374MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD)
375{
376        if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8))  /* should not happen => corruption detected */
377                return BIT_DStream_overflow;
378
379    if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) {
380        bitD->ptr -= bitD->bitsConsumed >> 3;
381        bitD->bitsConsumed &= 7;
382        bitD->bitContainer = MEM_readLEST(bitD->ptr);
383        return BIT_DStream_unfinished;
384    }
385    if (bitD->ptr == bitD->start) {
386        if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
387        return BIT_DStream_completed;
388    }
389    {   U32 nbBytes = bitD->bitsConsumed >> 3;
390        BIT_DStream_status result = BIT_DStream_unfinished;
391        if (bitD->ptr - nbBytes < bitD->start) {
392            nbBytes = (U32)(bitD->ptr - bitD->start);  /* ptr > start */
393            result = BIT_DStream_endOfBuffer;
394        }
395        bitD->ptr -= nbBytes;
396        bitD->bitsConsumed -= nbBytes*8;
397        bitD->bitContainer = MEM_readLEST(bitD->ptr);   /* reminder : srcSize > sizeof(bitD) */
398        return result;
399    }
400}
401
402/*! BIT_endOfDStream() :
403*   @return Tells if DStream has exactly reached its end (all bits consumed).
404*/
405MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)
406{
407    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 */
Note: See TracBrowser for help on using the repository browser.