1 /* ******************************************* 1 /* ******************************************************************
2 * bitstream 2 * bitstream
3 * Part of FSE library 3 * Part of FSE library
4 * Copyright (c) Yann Collet, Facebook, Inc. 4 * Copyright (c) Yann Collet, Facebook, Inc.
5 * 5 *
6 * You can contact the author at : 6 * You can contact the author at :
7 * - Source repository : https://github.com/Cy 7 * - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
8 * 8 *
9 * This source code is licensed under both the 9 * This source code is licensed under both the BSD-style license (found in the
10 * LICENSE file in the root directory of this 10 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
11 * in the COPYING file in the root directory o 11 * in the COPYING file in the root directory of this source tree).
12 * You may select, at your option, one of the 12 * You may select, at your option, one of the above-listed licenses.
13 ********************************************** 13 ****************************************************************** */
14 #ifndef BITSTREAM_H_MODULE 14 #ifndef BITSTREAM_H_MODULE
15 #define BITSTREAM_H_MODULE 15 #define BITSTREAM_H_MODULE
16 16
17 /* 17 /*
18 * This API consists of small unitary function 18 * This API consists of small unitary functions, which must be inlined for best performance.
19 * Since link-time-optimization is not availab 19 * Since link-time-optimization is not available for all compilers,
20 * these functions are defined into a .h to be 20 * these functions are defined into a .h to be included.
21 */ 21 */
22 22
23 /*-**************************************** 23 /*-****************************************
24 * Dependencies 24 * Dependencies
25 ******************************************/ 25 ******************************************/
26 #include "mem.h" /* unaligned acces 26 #include "mem.h" /* unaligned access routines */
27 #include "compiler.h" /* UNLIKELY() */ 27 #include "compiler.h" /* UNLIKELY() */
28 #include "debug.h" /* assert(), DEBUG 28 #include "debug.h" /* assert(), DEBUGLOG(), RAWLOG() */
29 #include "error_private.h" /* error codes and 29 #include "error_private.h" /* error codes and messages */
30 30
31 31
32 /*========================================= 32 /*=========================================
33 * Target specific 33 * Target specific
34 =========================================*/ 34 =========================================*/
35 35
36 #define STREAM_ACCUMULATOR_MIN_32 25 36 #define STREAM_ACCUMULATOR_MIN_32 25
37 #define STREAM_ACCUMULATOR_MIN_64 57 37 #define STREAM_ACCUMULATOR_MIN_64 57
38 #define STREAM_ACCUMULATOR_MIN ((U32)(MEM_3 38 #define STREAM_ACCUMULATOR_MIN ((U32)(MEM_32bits() ? STREAM_ACCUMULATOR_MIN_32 : STREAM_ACCUMULATOR_MIN_64))
39 39
40 40
41 /*-****************************************** 41 /*-******************************************
42 * bitStream encoding API (write forward) 42 * bitStream encoding API (write forward)
43 ********************************************/ 43 ********************************************/
44 /* bitStream can mix input from multiple sourc 44 /* bitStream can mix input from multiple sources.
45 * A critical property of these streams is tha 45 * A critical property of these streams is that they encode and decode in **reverse** direction.
46 * So the first bit sequence you add will be t 46 * So the first bit sequence you add will be the last to be read, like a LIFO stack.
47 */ 47 */
48 typedef struct { 48 typedef struct {
49 size_t bitContainer; 49 size_t bitContainer;
50 unsigned bitPos; 50 unsigned bitPos;
51 char* startPtr; 51 char* startPtr;
52 char* ptr; 52 char* ptr;
53 char* endPtr; 53 char* endPtr;
54 } BIT_CStream_t; 54 } BIT_CStream_t;
55 55
56 MEM_STATIC size_t BIT_initCStream(BIT_CStream_ 56 MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC, void* dstBuffer, size_t dstCapacity);
57 MEM_STATIC void BIT_addBits(BIT_CStream_t* b 57 MEM_STATIC void BIT_addBits(BIT_CStream_t* bitC, size_t value, unsigned nbBits);
58 MEM_STATIC void BIT_flushBits(BIT_CStream_t* 58 MEM_STATIC void BIT_flushBits(BIT_CStream_t* bitC);
59 MEM_STATIC size_t BIT_closeCStream(BIT_CStream 59 MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t* bitC);
60 60
61 /* Start with initCStream, providing the size 61 /* Start with initCStream, providing the size of buffer to write into.
62 * bitStream will never write outside of this 62 * bitStream will never write outside of this buffer.
63 * `dstCapacity` must be >= sizeof(bitD->bitCo 63 * `dstCapacity` must be >= sizeof(bitD->bitContainer), otherwise @return will be an error code.
64 * 64 *
65 * bits are first added to a local register. 65 * bits are first added to a local register.
66 * Local register is size_t, hence 64-bits on 66 * Local register is size_t, hence 64-bits on 64-bits systems, or 32-bits on 32-bits systems.
67 * Writing data into memory is an explicit ope 67 * Writing data into memory is an explicit operation, performed by the flushBits function.
68 * Hence keep track how many bits are potentia 68 * Hence keep track how many bits are potentially stored into local register to avoid register overflow.
69 * After a flushBits, a maximum of 7 bits migh 69 * After a flushBits, a maximum of 7 bits might still be stored into local register.
70 * 70 *
71 * Avoid storing elements of more than 24 bits 71 * Avoid storing elements of more than 24 bits if you want compatibility with 32-bits bitstream readers.
72 * 72 *
73 * Last operation is to close the bitStream. 73 * Last operation is to close the bitStream.
74 * The function returns the final size of CStr 74 * The function returns the final size of CStream in bytes.
75 * If data couldn't fit into `dstBuffer`, it w 75 * If data couldn't fit into `dstBuffer`, it will return a 0 ( == not storable)
76 */ 76 */
77 77
78 78
79 /*-******************************************* 79 /*-********************************************
80 * bitStream decoding API (read backward) 80 * bitStream decoding API (read backward)
81 ********************************************** 81 **********************************************/
82 typedef struct { 82 typedef struct {
83 size_t bitContainer; 83 size_t bitContainer;
84 unsigned bitsConsumed; 84 unsigned bitsConsumed;
85 const char* ptr; 85 const char* ptr;
86 const char* start; 86 const char* start;
87 const char* limitPtr; 87 const char* limitPtr;
88 } BIT_DStream_t; 88 } BIT_DStream_t;
89 89
90 typedef enum { BIT_DStream_unfinished = 0, 90 typedef enum { BIT_DStream_unfinished = 0,
91 BIT_DStream_endOfBuffer = 1, 91 BIT_DStream_endOfBuffer = 1,
92 BIT_DStream_completed = 2, 92 BIT_DStream_completed = 2,
93 BIT_DStream_overflow = 3 } BIT_ 93 BIT_DStream_overflow = 3 } BIT_DStream_status; /* result of BIT_reloadDStream() */
94 /* 1,2,4,8 would be better for 94 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
95 95
96 MEM_STATIC size_t BIT_initDStream(BIT_DStrea 96 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
97 MEM_STATIC size_t BIT_readBits(BIT_DStream_t 97 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
98 MEM_STATIC BIT_DStream_status BIT_reloadDStrea 98 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD);
99 MEM_STATIC unsigned BIT_endOfDStream(const BIT 99 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);
100 100
101 101
102 /* Start by invoking BIT_initDStream(). 102 /* Start by invoking BIT_initDStream().
103 * A chunk of the bitStream is then stored int 103 * A chunk of the bitStream is then stored into a local register.
104 * Local register size is 64-bits on 64-bits s 104 * Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t).
105 * You can then retrieve bitFields stored into 105 * You can then retrieve bitFields stored into the local register, **in reverse order**.
106 * Local register is explicitly reloaded from 106 * Local register is explicitly reloaded from memory by the BIT_reloadDStream() method.
107 * A reload guarantee a minimum of ((8*sizeof( 107 * A reload guarantee a minimum of ((8*sizeof(bitD->bitContainer))-7) bits when its result is BIT_DStream_unfinished.
108 * Otherwise, it can be less than that, so pro 108 * Otherwise, it can be less than that, so proceed accordingly.
109 * Checking if DStream has reached its end can 109 * Checking if DStream has reached its end can be performed with BIT_endOfDStream().
110 */ 110 */
111 111
112 112
113 /*-**************************************** 113 /*-****************************************
114 * unsafe API 114 * unsafe API
115 ******************************************/ 115 ******************************************/
116 MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* 116 MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC, size_t value, unsigned nbBits);
117 /* faster, but works only if value is "clean", 117 /* faster, but works only if value is "clean", meaning all high bits above nbBits are 0 */
118 118
119 MEM_STATIC void BIT_flushBitsFast(BIT_CStream_ 119 MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC);
120 /* unsafe version; does not check buffer overf 120 /* unsafe version; does not check buffer overflow */
121 121
122 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream 122 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);
123 /* faster, but works only if nbBits >= 1 */ 123 /* faster, but works only if nbBits >= 1 */
124 124
125 125
126 126
127 /*-******************************************* 127 /*-**************************************************************
128 * Internal functions 128 * Internal functions
129 ********************************************** 129 ****************************************************************/
130 MEM_STATIC unsigned BIT_highbit32 (U32 val) 130 MEM_STATIC unsigned BIT_highbit32 (U32 val)
131 { 131 {
132 assert(val != 0); 132 assert(val != 0);
133 { 133 {
134 # if (__GNUC__ >= 3) /* Use GCC Intrinsic 134 # if (__GNUC__ >= 3) /* Use GCC Intrinsic */
135 return __builtin_clz (val) ^ 31; 135 return __builtin_clz (val) ^ 31;
136 # else /* Software version */ 136 # else /* Software version */
137 static const unsigned DeBruijnClz[32] 137 static const unsigned DeBruijnClz[32] = { 0, 9, 1, 10, 13, 21, 2, 29,
138 138 11, 14, 16, 18, 22, 25, 3, 30,
139 139 8, 12, 20, 28, 15, 17, 24, 7,
140 140 19, 27, 23, 6, 26, 5, 4, 31 };
141 U32 v = val; 141 U32 v = val;
142 v |= v >> 1; 142 v |= v >> 1;
143 v |= v >> 2; 143 v |= v >> 2;
144 v |= v >> 4; 144 v |= v >> 4;
145 v |= v >> 8; 145 v |= v >> 8;
146 v |= v >> 16; 146 v |= v >> 16;
147 return DeBruijnClz[ (U32) (v * 0x07C4A 147 return DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
148 # endif 148 # endif
149 } 149 }
150 } 150 }
151 151
152 /*===== Local Constants =====*/ 152 /*===== Local Constants =====*/
153 static const unsigned BIT_mask[] = { 153 static const unsigned BIT_mask[] = {
154 0, 1, 3, 7, 154 0, 1, 3, 7, 0xF, 0x1F,
155 0x3F, 0x7F, 0xFF, 0x1FF, 155 0x3F, 0x7F, 0xFF, 0x1FF, 0x3FF, 0x7FF,
156 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 156 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF, 0x1FFFF,
157 0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF 157 0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF, 0x3FFFFF, 0x7FFFFF,
158 0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF, 0x7FFFFF 158 0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF, 0x7FFFFFF, 0xFFFFFFF, 0x1FFFFFFF,
159 0x3FFFFFFF, 0x7FFFFFFF}; /* up to 31 bits 159 0x3FFFFFFF, 0x7FFFFFFF}; /* up to 31 bits */
160 #define BIT_MASK_SIZE (sizeof(BIT_mask) / size 160 #define BIT_MASK_SIZE (sizeof(BIT_mask) / sizeof(BIT_mask[0]))
161 161
162 /*-******************************************* 162 /*-**************************************************************
163 * bitStream encoding 163 * bitStream encoding
164 ********************************************** 164 ****************************************************************/
165 /*! BIT_initCStream() : 165 /*! BIT_initCStream() :
166 * `dstCapacity` must be > sizeof(size_t) 166 * `dstCapacity` must be > sizeof(size_t)
167 * @return : 0 if success, 167 * @return : 0 if success,
168 * otherwise an error code (can be 168 * otherwise an error code (can be tested using ERR_isError()) */
169 MEM_STATIC size_t BIT_initCStream(BIT_CStream_ 169 MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC,
170 void* startP 170 void* startPtr, size_t dstCapacity)
171 { 171 {
172 bitC->bitContainer = 0; 172 bitC->bitContainer = 0;
173 bitC->bitPos = 0; 173 bitC->bitPos = 0;
174 bitC->startPtr = (char*)startPtr; 174 bitC->startPtr = (char*)startPtr;
175 bitC->ptr = bitC->startPtr; 175 bitC->ptr = bitC->startPtr;
176 bitC->endPtr = bitC->startPtr + dstCapacit 176 bitC->endPtr = bitC->startPtr + dstCapacity - sizeof(bitC->bitContainer);
177 if (dstCapacity <= sizeof(bitC->bitContain 177 if (dstCapacity <= sizeof(bitC->bitContainer)) return ERROR(dstSize_tooSmall);
178 return 0; 178 return 0;
179 } 179 }
180 180
181 /*! BIT_addBits() : 181 /*! BIT_addBits() :
182 * can add up to 31 bits into `bitC`. 182 * can add up to 31 bits into `bitC`.
183 * Note : does not check for register overflo 183 * Note : does not check for register overflow ! */
184 MEM_STATIC void BIT_addBits(BIT_CStream_t* bit 184 MEM_STATIC void BIT_addBits(BIT_CStream_t* bitC,
185 size_t value, unsi 185 size_t value, unsigned nbBits)
186 { 186 {
187 DEBUG_STATIC_ASSERT(BIT_MASK_SIZE == 32); 187 DEBUG_STATIC_ASSERT(BIT_MASK_SIZE == 32);
188 assert(nbBits < BIT_MASK_SIZE); 188 assert(nbBits < BIT_MASK_SIZE);
189 assert(nbBits + bitC->bitPos < sizeof(bitC 189 assert(nbBits + bitC->bitPos < sizeof(bitC->bitContainer) * 8);
190 bitC->bitContainer |= (value & BIT_mask[nb 190 bitC->bitContainer |= (value & BIT_mask[nbBits]) << bitC->bitPos;
191 bitC->bitPos += nbBits; 191 bitC->bitPos += nbBits;
192 } 192 }
193 193
194 /*! BIT_addBitsFast() : 194 /*! BIT_addBitsFast() :
195 * works only if `value` is _clean_, 195 * works only if `value` is _clean_,
196 * meaning all high bits above nbBits are 0 * 196 * meaning all high bits above nbBits are 0 */
197 MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* 197 MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC,
198 size_t value, 198 size_t value, unsigned nbBits)
199 { 199 {
200 assert((value>>nbBits) == 0); 200 assert((value>>nbBits) == 0);
201 assert(nbBits + bitC->bitPos < sizeof(bitC 201 assert(nbBits + bitC->bitPos < sizeof(bitC->bitContainer) * 8);
202 bitC->bitContainer |= value << bitC->bitPo 202 bitC->bitContainer |= value << bitC->bitPos;
203 bitC->bitPos += nbBits; 203 bitC->bitPos += nbBits;
204 } 204 }
205 205
206 /*! BIT_flushBitsFast() : 206 /*! BIT_flushBitsFast() :
207 * assumption : bitContainer has not overflow 207 * assumption : bitContainer has not overflowed
208 * unsafe version; does not check buffer over 208 * unsafe version; does not check buffer overflow */
209 MEM_STATIC void BIT_flushBitsFast(BIT_CStream_ 209 MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC)
210 { 210 {
211 size_t const nbBytes = bitC->bitPos >> 3; 211 size_t const nbBytes = bitC->bitPos >> 3;
212 assert(bitC->bitPos < sizeof(bitC->bitCont 212 assert(bitC->bitPos < sizeof(bitC->bitContainer) * 8);
213 assert(bitC->ptr <= bitC->endPtr); 213 assert(bitC->ptr <= bitC->endPtr);
214 MEM_writeLEST(bitC->ptr, bitC->bitContaine 214 MEM_writeLEST(bitC->ptr, bitC->bitContainer);
215 bitC->ptr += nbBytes; 215 bitC->ptr += nbBytes;
216 bitC->bitPos &= 7; 216 bitC->bitPos &= 7;
217 bitC->bitContainer >>= nbBytes*8; 217 bitC->bitContainer >>= nbBytes*8;
218 } 218 }
219 219
220 /*! BIT_flushBits() : 220 /*! BIT_flushBits() :
221 * assumption : bitContainer has not overflow 221 * assumption : bitContainer has not overflowed
222 * safe version; check for buffer overflow, a 222 * safe version; check for buffer overflow, and prevents it.
223 * note : does not signal buffer overflow. 223 * note : does not signal buffer overflow.
224 * overflow will be revealed later on using B 224 * overflow will be revealed later on using BIT_closeCStream() */
225 MEM_STATIC void BIT_flushBits(BIT_CStream_t* b 225 MEM_STATIC void BIT_flushBits(BIT_CStream_t* bitC)
226 { 226 {
227 size_t const nbBytes = bitC->bitPos >> 3; 227 size_t const nbBytes = bitC->bitPos >> 3;
228 assert(bitC->bitPos < sizeof(bitC->bitCont 228 assert(bitC->bitPos < sizeof(bitC->bitContainer) * 8);
229 assert(bitC->ptr <= bitC->endPtr); 229 assert(bitC->ptr <= bitC->endPtr);
230 MEM_writeLEST(bitC->ptr, bitC->bitContaine 230 MEM_writeLEST(bitC->ptr, bitC->bitContainer);
231 bitC->ptr += nbBytes; 231 bitC->ptr += nbBytes;
232 if (bitC->ptr > bitC->endPtr) bitC->ptr = 232 if (bitC->ptr > bitC->endPtr) bitC->ptr = bitC->endPtr;
233 bitC->bitPos &= 7; 233 bitC->bitPos &= 7;
234 bitC->bitContainer >>= nbBytes*8; 234 bitC->bitContainer >>= nbBytes*8;
235 } 235 }
236 236
237 /*! BIT_closeCStream() : 237 /*! BIT_closeCStream() :
238 * @return : size of CStream, in bytes, 238 * @return : size of CStream, in bytes,
239 * or 0 if it could not fit into ds 239 * or 0 if it could not fit into dstBuffer */
240 MEM_STATIC size_t BIT_closeCStream(BIT_CStream 240 MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t* bitC)
241 { 241 {
242 BIT_addBitsFast(bitC, 1, 1); /* endMark 242 BIT_addBitsFast(bitC, 1, 1); /* endMark */
243 BIT_flushBits(bitC); 243 BIT_flushBits(bitC);
244 if (bitC->ptr >= bitC->endPtr) return 0; / 244 if (bitC->ptr >= bitC->endPtr) return 0; /* overflow detected */
245 return (bitC->ptr - bitC->startPtr) + (bit 245 return (bitC->ptr - bitC->startPtr) + (bitC->bitPos > 0);
246 } 246 }
247 247
248 248
249 /*-******************************************* 249 /*-********************************************************
250 * bitStream decoding 250 * bitStream decoding
251 ********************************************** 251 **********************************************************/
252 /*! BIT_initDStream() : 252 /*! BIT_initDStream() :
253 * Initialize a BIT_DStream_t. 253 * Initialize a BIT_DStream_t.
254 * `bitD` : a pointer to an already allocated 254 * `bitD` : a pointer to an already allocated BIT_DStream_t structure.
255 * `srcSize` must be the *exact* size of the b 255 * `srcSize` must be the *exact* size of the bitStream, in bytes.
256 * @return : size of stream (== srcSize), or a 256 * @return : size of stream (== srcSize), or an errorCode if a problem is detected
257 */ 257 */
258 MEM_STATIC size_t BIT_initDStream(BIT_DStream_ 258 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
259 { 259 {
260 if (srcSize < 1) { ZSTD_memset(bitD, 0, si 260 if (srcSize < 1) { ZSTD_memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
261 261
262 bitD->start = (const char*)srcBuffer; 262 bitD->start = (const char*)srcBuffer;
263 bitD->limitPtr = bitD->start + sizeof(bitD 263 bitD->limitPtr = bitD->start + sizeof(bitD->bitContainer);
264 264
265 if (srcSize >= sizeof(bitD->bitContainer) 265 if (srcSize >= sizeof(bitD->bitContainer)) { /* normal case */
266 bitD->ptr = (const char*)srcBuffer + 266 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer);
267 bitD->bitContainer = MEM_readLEST(bitD 267 bitD->bitContainer = MEM_readLEST(bitD->ptr);
268 { BYTE const lastByte = ((const BYTE*) 268 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
269 bitD->bitsConsumed = lastByte ? 8 - 269 bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0; /* ensures bitsConsumed is always set */
270 if (lastByte == 0) return ERROR(GENE 270 if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
271 } else { 271 } else {
272 bitD->ptr = bitD->start; 272 bitD->ptr = bitD->start;
273 bitD->bitContainer = *(const BYTE*)(bi 273 bitD->bitContainer = *(const BYTE*)(bitD->start);
274 switch(srcSize) 274 switch(srcSize)
275 { 275 {
276 case 7: bitD->bitContainer += (size_t) 276 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);
277 ZSTD_FALLTHROUGH; 277 ZSTD_FALLTHROUGH;
278 278
279 case 6: bitD->bitContainer += (size_t) 279 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer)*8 - 24);
280 ZSTD_FALLTHROUGH; 280 ZSTD_FALLTHROUGH;
281 281
282 case 5: bitD->bitContainer += (size_t) 282 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer)*8 - 32);
283 ZSTD_FALLTHROUGH; 283 ZSTD_FALLTHROUGH;
284 284
285 case 4: bitD->bitContainer += (size_t) 285 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[3]) << 24;
286 ZSTD_FALLTHROUGH; 286 ZSTD_FALLTHROUGH;
287 287
288 case 3: bitD->bitContainer += (size_t) 288 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[2]) << 16;
289 ZSTD_FALLTHROUGH; 289 ZSTD_FALLTHROUGH;
290 290
291 case 2: bitD->bitContainer += (size_t) 291 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[1]) << 8;
292 ZSTD_FALLTHROUGH; 292 ZSTD_FALLTHROUGH;
293 293
294 default: break; 294 default: break;
295 } 295 }
296 { BYTE const lastByte = ((const BYTE 296 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
297 bitD->bitsConsumed = lastByte ? 8 297 bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0;
298 if (lastByte == 0) return ERROR(co 298 if (lastByte == 0) return ERROR(corruption_detected); /* endMark not present */
299 } 299 }
300 bitD->bitsConsumed += (U32)(sizeof(bit 300 bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8;
301 } 301 }
302 302
303 return srcSize; 303 return srcSize;
304 } 304 }
305 305
306 MEM_STATIC FORCE_INLINE_ATTR size_t BIT_getUpp 306 MEM_STATIC FORCE_INLINE_ATTR size_t BIT_getUpperBits(size_t bitContainer, U32 const start)
307 { 307 {
308 return bitContainer >> start; 308 return bitContainer >> start;
309 } 309 }
310 310
311 MEM_STATIC FORCE_INLINE_ATTR size_t BIT_getMid 311 MEM_STATIC FORCE_INLINE_ATTR size_t BIT_getMiddleBits(size_t bitContainer, U32 const start, U32 const nbBits)
312 { 312 {
313 U32 const regMask = sizeof(bitContainer)*8 313 U32 const regMask = sizeof(bitContainer)*8 - 1;
314 /* if start > regMask, bitstream is corrup 314 /* if start > regMask, bitstream is corrupted, and result is undefined */
315 assert(nbBits < BIT_MASK_SIZE); 315 assert(nbBits < BIT_MASK_SIZE);
316 /* x86 transform & ((1 << nbBits) - 1) to 316 /* x86 transform & ((1 << nbBits) - 1) to bzhi instruction, it is better
317 * than accessing memory. When bmi2 instru 317 * than accessing memory. When bmi2 instruction is not present, we consider
318 * such cpus old (pre-Haswell, 2013) and t 318 * such cpus old (pre-Haswell, 2013) and their performance is not of that
319 * importance. 319 * importance.
320 */ 320 */
321 #if defined(__x86_64__) || defined(_M_X86) 321 #if defined(__x86_64__) || defined(_M_X86)
322 return (bitContainer >> (start & regMask)) 322 return (bitContainer >> (start & regMask)) & ((((U64)1) << nbBits) - 1);
323 #else 323 #else
324 return (bitContainer >> (start & regMask)) 324 return (bitContainer >> (start & regMask)) & BIT_mask[nbBits];
325 #endif 325 #endif
326 } 326 }
327 327
328 MEM_STATIC FORCE_INLINE_ATTR size_t BIT_getLow 328 MEM_STATIC FORCE_INLINE_ATTR size_t BIT_getLowerBits(size_t bitContainer, U32 const nbBits)
329 { 329 {
330 assert(nbBits < BIT_MASK_SIZE); 330 assert(nbBits < BIT_MASK_SIZE);
331 return bitContainer & BIT_mask[nbBits]; 331 return bitContainer & BIT_mask[nbBits];
332 } 332 }
333 333
334 /*! BIT_lookBits() : 334 /*! BIT_lookBits() :
335 * Provides next n bits from local register. 335 * Provides next n bits from local register.
336 * local register is not modified. 336 * local register is not modified.
337 * On 32-bits, maxNbBits==24. 337 * On 32-bits, maxNbBits==24.
338 * On 64-bits, maxNbBits==56. 338 * On 64-bits, maxNbBits==56.
339 * @return : value extracted */ 339 * @return : value extracted */
340 MEM_STATIC FORCE_INLINE_ATTR size_t BIT_lookB 340 MEM_STATIC FORCE_INLINE_ATTR size_t BIT_lookBits(const BIT_DStream_t* bitD, U32 nbBits)
341 { 341 {
342 /* arbitrate between double-shift and shif 342 /* arbitrate between double-shift and shift+mask */
343 #if 1 343 #if 1
344 /* if bitD->bitsConsumed + nbBits > sizeof 344 /* if bitD->bitsConsumed + nbBits > sizeof(bitD->bitContainer)*8,
345 * bitstream is likely corrupted, and resu 345 * bitstream is likely corrupted, and result is undefined */
346 return BIT_getMiddleBits(bitD->bitContaine 346 return BIT_getMiddleBits(bitD->bitContainer, (sizeof(bitD->bitContainer)*8) - bitD->bitsConsumed - nbBits, nbBits);
347 #else 347 #else
348 /* this code path is slower on my os-x lap 348 /* this code path is slower on my os-x laptop */
349 U32 const regMask = sizeof(bitD->bitContai 349 U32 const regMask = sizeof(bitD->bitContainer)*8 - 1;
350 return ((bitD->bitContainer << (bitD->bits 350 return ((bitD->bitContainer << (bitD->bitsConsumed & regMask)) >> 1) >> ((regMask-nbBits) & regMask);
351 #endif 351 #endif
352 } 352 }
353 353
354 /*! BIT_lookBitsFast() : 354 /*! BIT_lookBitsFast() :
355 * unsafe version; only works if nbBits >= 1 355 * unsafe version; only works if nbBits >= 1 */
356 MEM_STATIC size_t BIT_lookBitsFast(const BIT_D 356 MEM_STATIC size_t BIT_lookBitsFast(const BIT_DStream_t* bitD, U32 nbBits)
357 { 357 {
358 U32 const regMask = sizeof(bitD->bitContai 358 U32 const regMask = sizeof(bitD->bitContainer)*8 - 1;
359 assert(nbBits >= 1); 359 assert(nbBits >= 1);
360 return (bitD->bitContainer << (bitD->bitsC 360 return (bitD->bitContainer << (bitD->bitsConsumed & regMask)) >> (((regMask+1)-nbBits) & regMask);
361 } 361 }
362 362
363 MEM_STATIC FORCE_INLINE_ATTR void BIT_skipBits 363 MEM_STATIC FORCE_INLINE_ATTR void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits)
364 { 364 {
365 bitD->bitsConsumed += nbBits; 365 bitD->bitsConsumed += nbBits;
366 } 366 }
367 367
368 /*! BIT_readBits() : 368 /*! BIT_readBits() :
369 * Read (consume) next n bits from local regi 369 * Read (consume) next n bits from local register and update.
370 * Pay attention to not read more than nbBits 370 * Pay attention to not read more than nbBits contained into local register.
371 * @return : extracted value. */ 371 * @return : extracted value. */
372 MEM_STATIC FORCE_INLINE_ATTR size_t BIT_readBi 372 MEM_STATIC FORCE_INLINE_ATTR size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits)
373 { 373 {
374 size_t const value = BIT_lookBits(bitD, nb 374 size_t const value = BIT_lookBits(bitD, nbBits);
375 BIT_skipBits(bitD, nbBits); 375 BIT_skipBits(bitD, nbBits);
376 return value; 376 return value;
377 } 377 }
378 378
379 /*! BIT_readBitsFast() : 379 /*! BIT_readBitsFast() :
380 * unsafe version; only works only if nbBits 380 * unsafe version; only works only if nbBits >= 1 */
381 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream 381 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits)
382 { 382 {
383 size_t const value = BIT_lookBitsFast(bitD 383 size_t const value = BIT_lookBitsFast(bitD, nbBits);
384 assert(nbBits >= 1); 384 assert(nbBits >= 1);
385 BIT_skipBits(bitD, nbBits); 385 BIT_skipBits(bitD, nbBits);
386 return value; 386 return value;
387 } 387 }
388 388
389 /*! BIT_reloadDStreamFast() : 389 /*! BIT_reloadDStreamFast() :
390 * Similar to BIT_reloadDStream(), but with t 390 * Similar to BIT_reloadDStream(), but with two differences:
391 * 1. bitsConsumed <= sizeof(bitD->bitContain 391 * 1. bitsConsumed <= sizeof(bitD->bitContainer)*8 must hold!
392 * 2. Returns BIT_DStream_overflow when bitD- 392 * 2. Returns BIT_DStream_overflow when bitD->ptr < bitD->limitPtr, at this
393 * point you must use BIT_reloadDStream() 393 * point you must use BIT_reloadDStream() to reload.
394 */ 394 */
395 MEM_STATIC BIT_DStream_status BIT_reloadDStrea 395 MEM_STATIC BIT_DStream_status BIT_reloadDStreamFast(BIT_DStream_t* bitD)
396 { 396 {
397 if (UNLIKELY(bitD->ptr < bitD->limitPtr)) 397 if (UNLIKELY(bitD->ptr < bitD->limitPtr))
398 return BIT_DStream_overflow; 398 return BIT_DStream_overflow;
399 assert(bitD->bitsConsumed <= sizeof(bitD-> 399 assert(bitD->bitsConsumed <= sizeof(bitD->bitContainer)*8);
400 bitD->ptr -= bitD->bitsConsumed >> 3; 400 bitD->ptr -= bitD->bitsConsumed >> 3;
401 bitD->bitsConsumed &= 7; 401 bitD->bitsConsumed &= 7;
402 bitD->bitContainer = MEM_readLEST(bitD->pt 402 bitD->bitContainer = MEM_readLEST(bitD->ptr);
403 return BIT_DStream_unfinished; 403 return BIT_DStream_unfinished;
404 } 404 }
405 405
406 /*! BIT_reloadDStream() : 406 /*! BIT_reloadDStream() :
407 * Refill `bitD` from buffer previously set i 407 * Refill `bitD` from buffer previously set in BIT_initDStream() .
408 * This function is safe, it guarantees it wi 408 * This function is safe, it guarantees it will not read beyond src buffer.
409 * @return : status of `BIT_DStream_t` interna 409 * @return : status of `BIT_DStream_t` internal register.
410 * when status == BIT_DStream_unfini 410 * when status == BIT_DStream_unfinished, internal register is filled with at least 25 or 57 bits */
411 MEM_STATIC BIT_DStream_status BIT_reloadDStrea 411 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD)
412 { 412 {
413 if (bitD->bitsConsumed > (sizeof(bitD->bit 413 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* overflow detected, like end of stream */
414 return BIT_DStream_overflow; 414 return BIT_DStream_overflow;
415 415
416 if (bitD->ptr >= bitD->limitPtr) { 416 if (bitD->ptr >= bitD->limitPtr) {
417 return BIT_reloadDStreamFast(bitD); 417 return BIT_reloadDStreamFast(bitD);
418 } 418 }
419 if (bitD->ptr == bitD->start) { 419 if (bitD->ptr == bitD->start) {
420 if (bitD->bitsConsumed < sizeof(bitD-> 420 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
421 return BIT_DStream_completed; 421 return BIT_DStream_completed;
422 } 422 }
423 /* start < ptr < limitPtr */ 423 /* start < ptr < limitPtr */
424 { U32 nbBytes = bitD->bitsConsumed >> 3; 424 { U32 nbBytes = bitD->bitsConsumed >> 3;
425 BIT_DStream_status result = BIT_DStrea 425 BIT_DStream_status result = BIT_DStream_unfinished;
426 if (bitD->ptr - nbBytes < bitD->start) 426 if (bitD->ptr - nbBytes < bitD->start) {
427 nbBytes = (U32)(bitD->ptr - bitD-> 427 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
428 result = BIT_DStream_endOfBuffer; 428 result = BIT_DStream_endOfBuffer;
429 } 429 }
430 bitD->ptr -= nbBytes; 430 bitD->ptr -= nbBytes;
431 bitD->bitsConsumed -= nbBytes*8; 431 bitD->bitsConsumed -= nbBytes*8;
432 bitD->bitContainer = MEM_readLEST(bitD 432 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD->bitContainer), otherwise bitD->ptr == bitD->start */
433 return result; 433 return result;
434 } 434 }
435 } 435 }
436 436
437 /*! BIT_endOfDStream() : 437 /*! BIT_endOfDStream() :
438 * @return : 1 if DStream has _exactly_ reache 438 * @return : 1 if DStream has _exactly_ reached its end (all bits consumed).
439 */ 439 */
440 MEM_STATIC unsigned BIT_endOfDStream(const BIT 440 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)
441 { 441 {
442 return ((DStream->ptr == DStream->start) & 442 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
443 } 443 }
444 444
445 445
446 #endif /* BITSTREAM_H_MODULE */ 446 #endif /* BITSTREAM_H_MODULE */
447 447
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.