This source file includes following definitions.
- BIT_highbit32
- BIT_initCStream
- BIT_addBits
- BIT_addBitsFast
- BIT_flushBitsFast
- BIT_flushBits
- BIT_closeCStream
- BIT_initDStream
- BIT_getUpperBits
- BIT_getMiddleBits
- BIT_getLowerBits
- BIT_lookBits
- BIT_lookBitsFast
- BIT_skipBits
- BIT_readBits
- BIT_readBitsFast
- BIT_reloadDStream
- BIT_endOfDStream
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41 #ifndef BITSTREAM_H_MODULE
42 #define BITSTREAM_H_MODULE
43
44
45
46
47
48
49
50
51
52
53 #include "error_private.h"
54 #include "mem.h"
55
56
57
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
65
66
67
68
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
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;
116
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
124
125
126
127
128
129
130
131
132
133
134
135
136 ZSTD_STATIC void BIT_addBitsFast(BIT_CStream_t *bitC, size_t value, unsigned nbBits);
137
138
139 ZSTD_STATIC void BIT_flushBitsFast(BIT_CStream_t *bitC);
140
141
142 ZSTD_STATIC size_t BIT_readBitsFast(BIT_DStream_t *bitD, unsigned nbBits);
143
144
145
146
147
148 ZSTD_STATIC unsigned BIT_highbit32(register U32 val) { return 31 - __builtin_clz(val); }
149
150
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};
154
155
156
157
158
159
160
161
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
175
176
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
184
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
192
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;
200 }
201
202
203
204
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;
214 }
215
216
217
218
219 ZSTD_STATIC size_t BIT_closeCStream(BIT_CStream_t *bitC)
220 {
221 BIT_addBitsFast(bitC, 1, 1);
222 BIT_flushBits(bitC);
223
224 if (bitC->ptr >= bitC->endPtr)
225 return 0;
226
227 return (bitC->ptr - bitC->startPtr) + (bitC->bitPos > 0);
228 }
229
230
231
232
233
234
235
236
237
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)) {
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;
253 if (lastByte == 0)
254 return ERROR(GENERIC);
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
263 case 6: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[5]) << (sizeof(bitD->bitContainer) * 8 - 24);
264
265 case 5: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[4]) << (sizeof(bitD->bitContainer) * 8 - 32);
266
267 case 4: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[3]) << 24;
268
269 case 3: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[2]) << 16;
270
271 case 2: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[1]) << 8;
272 default:;
273 }
274 {
275 BYTE const lastByte = ((const BYTE *)srcBuffer)[srcSize - 1];
276 bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0;
277 if (lastByte == 0)
278 return ERROR(GENERIC);
279 }
280 bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize) * 8;
281 }
282
283 return srcSize;
284 }
285
286 ZSTD_STATIC size_t BIT_getUpperBits(size_t bitContainer, U32 const start) { return bitContainer >> start; }
287
288 ZSTD_STATIC size_t BIT_getMiddleBits(size_t bitContainer, U32 const start, U32 const nbBits) { return (bitContainer >> start) & BIT_mask[nbBits]; }
289
290 ZSTD_STATIC size_t BIT_getLowerBits(size_t bitContainer, U32 const nbBits) { return bitContainer & BIT_mask[nbBits]; }
291
292
293
294
295
296
297
298
299 ZSTD_STATIC size_t BIT_lookBits(const BIT_DStream_t *bitD, U32 nbBits)
300 {
301 U32 const bitMask = sizeof(bitD->bitContainer) * 8 - 1;
302 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask - nbBits) & bitMask);
303 }
304
305
306
307 ZSTD_STATIC size_t BIT_lookBitsFast(const BIT_DStream_t *bitD, U32 nbBits)
308 {
309 U32 const bitMask = sizeof(bitD->bitContainer) * 8 - 1;
310 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask + 1) - nbBits) & bitMask);
311 }
312
313 ZSTD_STATIC void BIT_skipBits(BIT_DStream_t *bitD, U32 nbBits) { bitD->bitsConsumed += nbBits; }
314
315
316
317
318
319
320 ZSTD_STATIC size_t BIT_readBits(BIT_DStream_t *bitD, U32 nbBits)
321 {
322 size_t const value = BIT_lookBits(bitD, nbBits);
323 BIT_skipBits(bitD, nbBits);
324 return value;
325 }
326
327
328
329 ZSTD_STATIC size_t BIT_readBitsFast(BIT_DStream_t *bitD, U32 nbBits)
330 {
331 size_t const value = BIT_lookBitsFast(bitD, nbBits);
332 BIT_skipBits(bitD, nbBits);
333 return value;
334 }
335
336
337
338
339
340
341 ZSTD_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t *bitD)
342 {
343 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer) * 8))
344 return BIT_DStream_overflow;
345
346 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) {
347 bitD->ptr -= bitD->bitsConsumed >> 3;
348 bitD->bitsConsumed &= 7;
349 bitD->bitContainer = ZSTD_readLEST(bitD->ptr);
350 return BIT_DStream_unfinished;
351 }
352 if (bitD->ptr == bitD->start) {
353 if (bitD->bitsConsumed < sizeof(bitD->bitContainer) * 8)
354 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 nbBytes = (U32)(bitD->ptr - bitD->start);
362 result = BIT_DStream_endOfBuffer;
363 }
364 bitD->ptr -= nbBytes;
365 bitD->bitsConsumed -= nbBytes * 8;
366 bitD->bitContainer = ZSTD_readLEST(bitD->ptr);
367 return result;
368 }
369 }
370
371
372
373
374 ZSTD_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t *DStream)
375 {
376 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer) * 8));
377 }
378
379 #endif