Mercurial > public > mercurial-scm > hg

annotate contrib/python-zstandard/zstd/common/bitstream.h @ 42070:675775c33ab6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
zstandard: vendor python-zstandard 0.11 The upstream source distribution from PyPI was extracted. Unwanted files were removed. The clang-format ignore list was updated to reflect the new source of files. The project contains a vendored copy of zstandard 1.3.8. The old version was 1.3.6. This should result in some minor performance wins. test-check-py3-compat.t was updated to reflect now-passing tests on Python 3.8. Some HTTP tests were updated to reflect new zstd compression output. # no-check-commit because 3rd party code has different style guidelines Differential Revision: https://phab.mercurial-scm.org/D6199
author Gregory Szorc <gregory.szorc@gmail.com>
date Thu, 04 Apr 2019 17:34:43 -0700
parents 73fef626dae3
children 69de49c4e39c
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
1 /* ******************************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
2 bitstream
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
3 Part of FSE library
40121
73fef626dae3 zstandard: vendor python-zstandard 0.10.1
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37495
diff changeset
4 Copyright (C) 2013-present, Yann Collet.
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
5
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
6 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
7
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
8 Redistribution and use in source and binary forms, with or without
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
9 modification, are permitted provided that the following conditions are
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
10 met:
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
11
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
12 * Redistributions of source code must retain the above copyright
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
13 notice, this list of conditions and the following disclaimer.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
14 * Redistributions in binary form must reproduce the above
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
15 copyright notice, this list of conditions and the following disclaimer
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
16 in the documentation and/or other materials provided with the
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
17 distribution.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
18
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
20 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
21 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
22 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
23 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
24 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
25 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
26 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
27 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
28 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
29 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
30
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
31 You can contact the author at :
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
32 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
33 ****************************************************************** */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
34 #ifndef BITSTREAM_H_MODULE
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
35 #define BITSTREAM_H_MODULE
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
36
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
37 #if defined (__cplusplus)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
38 extern "C" {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
39 #endif
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
40
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
41 /*
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
42 * This API consists of small unitary functions, which must be inlined for best performance.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
43 * Since link-time-optimization is not available for all compilers,
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
44 * these functions are defined into a .h to be included.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
45 */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
46
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
47 /*-****************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
48 * Dependencies
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
49 ******************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
50 #include "mem.h" /* unaligned access routines */
40121
73fef626dae3 zstandard: vendor python-zstandard 0.10.1
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37495
diff changeset
51 #include "debug.h" /* assert(), DEBUGLOG(), RAWLOG() */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
52 #include "error_private.h" /* error codes and messages */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
53
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
54
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
55 /*=========================================
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
56 * Target specific
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
57 =========================================*/
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
58 #if defined(__BMI__) && defined(__GNUC__)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
59 # include <immintrin.h> /* support for bextr (experimental) */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
60 #endif
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
61
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
62 #define STREAM_ACCUMULATOR_MIN_32 25
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
63 #define STREAM_ACCUMULATOR_MIN_64 57
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
64 #define STREAM_ACCUMULATOR_MIN ((U32)(MEM_32bits() ? STREAM_ACCUMULATOR_MIN_32 : STREAM_ACCUMULATOR_MIN_64))
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
65
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
66
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
67 /*-******************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
68 * bitStream encoding API (write forward)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
69 ********************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
70 /* bitStream can mix input from multiple sources.
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
71 * A critical property of these streams is that they encode and decode in **reverse** direction.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
72 * So the first bit sequence you add will be the last to be read, like a LIFO stack.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
73 */
40121
73fef626dae3 zstandard: vendor python-zstandard 0.10.1
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37495
diff changeset
74 typedef struct {
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
75 size_t bitContainer;
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
76 unsigned bitPos;
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
77 char* startPtr;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
78 char* ptr;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
79 char* endPtr;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
80 } BIT_CStream_t;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
81
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
82 MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC, void* dstBuffer, size_t dstCapacity);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
83 MEM_STATIC void BIT_addBits(BIT_CStream_t* bitC, size_t value, unsigned nbBits);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
84 MEM_STATIC void BIT_flushBits(BIT_CStream_t* bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
85 MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t* bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
86
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
87 /* Start with initCStream, providing the size of buffer to write into.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
88 * bitStream will never write outside of this buffer.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
89 * `dstCapacity` must be >= sizeof(bitD->bitContainer), otherwise @return will be an error code.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
90 *
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
91 * bits are first added to a local register.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
92 * Local register is size_t, hence 64-bits on 64-bits systems, or 32-bits on 32-bits systems.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
93 * Writing data into memory is an explicit operation, performed by the flushBits function.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
94 * Hence keep track how many bits are potentially stored into local register to avoid register overflow.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
95 * After a flushBits, a maximum of 7 bits might still be stored into local register.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
96 *
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
97 * Avoid storing elements of more than 24 bits if you want compatibility with 32-bits bitstream readers.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
98 *
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
99 * Last operation is to close the bitStream.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
100 * The function returns the final size of CStream in bytes.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
101 * If data couldn't fit into `dstBuffer`, it will return a 0 ( == not storable)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
102 */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
103
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
104
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
105 /*-********************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
106 * bitStream decoding API (read backward)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
107 **********************************************/
40121
73fef626dae3 zstandard: vendor python-zstandard 0.10.1
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37495
diff changeset
108 typedef struct {
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
109 size_t bitContainer;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
110 unsigned bitsConsumed;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
111 const char* ptr;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
112 const char* start;
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
113 const char* limitPtr;
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
114 } BIT_DStream_t;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
115
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
116 typedef enum { BIT_DStream_unfinished = 0,
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
117 BIT_DStream_endOfBuffer = 1,
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
118 BIT_DStream_completed = 2,
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
119 BIT_DStream_overflow = 3 } BIT_DStream_status; /* result of BIT_reloadDStream() */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
120 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
121
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
122 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
123 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
124 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
125 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
126
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
127
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
128 /* Start by invoking BIT_initDStream().
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
129 * A chunk of the bitStream is then stored into a local register.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
130 * Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t).
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
131 * You can then retrieve bitFields stored into the local register, **in reverse order**.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
132 * Local register is explicitly reloaded from memory by the BIT_reloadDStream() method.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
133 * A reload guarantee a minimum of ((8*sizeof(bitD->bitContainer))-7) bits when its result is BIT_DStream_unfinished.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
134 * Otherwise, it can be less than that, so proceed accordingly.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
135 * Checking if DStream has reached its end can be performed with BIT_endOfDStream().
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
136 */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
137
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
138
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
139 /*-****************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
140 * unsafe API
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
141 ******************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
142 MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC, size_t value, unsigned nbBits);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
143 /* faster, but works only if value is "clean", meaning all high bits above nbBits are 0 */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
144
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
145 MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
146 /* unsafe version; does not check buffer overflow */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
147
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
148 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
149 /* faster, but works only if nbBits >= 1 */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
150
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
151
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
152
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
153 /*-**************************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
154 * Internal functions
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
155 ****************************************************************/
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
156 MEM_STATIC unsigned BIT_highbit32 (U32 val)
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
157 {
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
158 assert(val != 0);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
159 {
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
160 # if defined(_MSC_VER) /* Visual */
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
161 unsigned long r=0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
162 _BitScanReverse ( &r, val );
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
163 return (unsigned) r;
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
164 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
165 return 31 - __builtin_clz (val);
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
166 # else /* Software version */
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
167 static const unsigned DeBruijnClz[32] = { 0, 9, 1, 10, 13, 21, 2, 29,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
168 11, 14, 16, 18, 22, 25, 3, 30,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
169 8, 12, 20, 28, 15, 17, 24, 7,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
170 19, 27, 23, 6, 26, 5, 4, 31 };
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
171 U32 v = val;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
172 v |= v >> 1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
173 v |= v >> 2;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
174 v |= v >> 4;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
175 v |= v >> 8;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
176 v |= v >> 16;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
177 return DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
178 # endif
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
179 }
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
180 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
181
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
182 /*===== Local Constants =====*/
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
183 static const unsigned BIT_mask[] = {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
184 0, 1, 3, 7, 0xF, 0x1F,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
185 0x3F, 0x7F, 0xFF, 0x1FF, 0x3FF, 0x7FF,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
186 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF, 0x1FFFF,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
187 0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF, 0x3FFFFF, 0x7FFFFF,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
188 0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF, 0x7FFFFFF, 0xFFFFFFF, 0x1FFFFFFF,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
189 0x3FFFFFFF, 0x7FFFFFFF}; /* up to 31 bits */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
190 #define BIT_MASK_SIZE (sizeof(BIT_mask) / sizeof(BIT_mask[0]))
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
191
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
192 /*-**************************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
193 * bitStream encoding
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
194 ****************************************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
195 /*! BIT_initCStream() :
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
196 * `dstCapacity` must be > sizeof(size_t)
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
197 * @return : 0 if success,
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
198 * otherwise an error code (can be tested using ERR_isError()) */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
199 MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
200 void* startPtr, size_t dstCapacity)
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
201 {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
202 bitC->bitContainer = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
203 bitC->bitPos = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
204 bitC->startPtr = (char*)startPtr;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
205 bitC->ptr = bitC->startPtr;
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
206 bitC->endPtr = bitC->startPtr + dstCapacity - sizeof(bitC->bitContainer);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
207 if (dstCapacity <= sizeof(bitC->bitContainer)) return ERROR(dstSize_tooSmall);
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
208 return 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
209 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
210
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
211 /*! BIT_addBits() :
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
212 * can add up to 31 bits into `bitC`.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
213 * Note : does not check for register overflow ! */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
214 MEM_STATIC void BIT_addBits(BIT_CStream_t* bitC,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
215 size_t value, unsigned nbBits)
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
216 {
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
217 MEM_STATIC_ASSERT(BIT_MASK_SIZE == 32);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
218 assert(nbBits < BIT_MASK_SIZE);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
219 assert(nbBits + bitC->bitPos < sizeof(bitC->bitContainer) * 8);
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
220 bitC->bitContainer |= (value & BIT_mask[nbBits]) << bitC->bitPos;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
221 bitC->bitPos += nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
222 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
223
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
224 /*! BIT_addBitsFast() :
40121
73fef626dae3 zstandard: vendor python-zstandard 0.10.1
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37495
diff changeset
225 * works only if `value` is _clean_,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37495
diff changeset
226 * meaning all high bits above nbBits are 0 */
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
227 MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
228 size_t value, unsigned nbBits)
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
229 {
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
230 assert((value>>nbBits) == 0);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
231 assert(nbBits + bitC->bitPos < sizeof(bitC->bitContainer) * 8);
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
232 bitC->bitContainer |= value << bitC->bitPos;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
233 bitC->bitPos += nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
234 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
235
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
236 /*! BIT_flushBitsFast() :
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
237 * assumption : bitContainer has not overflowed
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
238 * unsafe version; does not check buffer overflow */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
239 MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
240 {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
241 size_t const nbBytes = bitC->bitPos >> 3;
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
242 assert(bitC->bitPos < sizeof(bitC->bitContainer) * 8);
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
243 MEM_writeLEST(bitC->ptr, bitC->bitContainer);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
244 bitC->ptr += nbBytes;
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
245 assert(bitC->ptr <= bitC->endPtr);
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
246 bitC->bitPos &= 7;
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
247 bitC->bitContainer >>= nbBytes*8;
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
248 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
249
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
250 /*! BIT_flushBits() :
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
251 * assumption : bitContainer has not overflowed
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
252 * safe version; check for buffer overflow, and prevents it.
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
253 * note : does not signal buffer overflow.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
254 * overflow will be revealed later on using BIT_closeCStream() */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
255 MEM_STATIC void BIT_flushBits(BIT_CStream_t* bitC)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
256 {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
257 size_t const nbBytes = bitC->bitPos >> 3;
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
258 assert(bitC->bitPos < sizeof(bitC->bitContainer) * 8);
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
259 MEM_writeLEST(bitC->ptr, bitC->bitContainer);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
260 bitC->ptr += nbBytes;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
261 if (bitC->ptr > bitC->endPtr) bitC->ptr = bitC->endPtr;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
262 bitC->bitPos &= 7;
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
263 bitC->bitContainer >>= nbBytes*8;
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
264 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
265
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
266 /*! BIT_closeCStream() :
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
267 * @return : size of CStream, in bytes,
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
268 * or 0 if it could not fit into dstBuffer */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
269 MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t* bitC)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
270 {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
271 BIT_addBitsFast(bitC, 1, 1); /* endMark */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
272 BIT_flushBits(bitC);
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
273 if (bitC->ptr >= bitC->endPtr) return 0; /* overflow detected */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
274 return (bitC->ptr - bitC->startPtr) + (bitC->bitPos > 0);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
275 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
276
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
277
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
278 /*-********************************************************
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
279 * bitStream decoding
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
280 **********************************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
281 /*! BIT_initDStream() :
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
282 * Initialize a BIT_DStream_t.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
283 * `bitD` : a pointer to an already allocated BIT_DStream_t structure.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
284 * `srcSize` must be the *exact* size of the bitStream, in bytes.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
285 * @return : size of stream (== srcSize), or an errorCode if a problem is detected
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
286 */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
287 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
288 {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
289 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
290
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
291 bitD->start = (const char*)srcBuffer;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
292 bitD->limitPtr = bitD->start + sizeof(bitD->bitContainer);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
293
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
294 if (srcSize >= sizeof(bitD->bitContainer)) { /* normal case */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
295 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
296 bitD->bitContainer = MEM_readLEST(bitD->ptr);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
297 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
30822
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30434
diff changeset
298 bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0; /* ensures bitsConsumed is always set */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
299 if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
300 } else {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
301 bitD->ptr = bitD->start;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
302 bitD->bitContainer = *(const BYTE*)(bitD->start);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
303 switch(srcSize)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
304 {
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
305 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
306 /* fall-through */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
307
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
308 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer)*8 - 24);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
309 /* fall-through */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
310
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
311 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer)*8 - 32);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
312 /* fall-through */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
313
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
314 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[3]) << 24;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
315 /* fall-through */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
316
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
317 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[2]) << 16;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
318 /* fall-through */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
319
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
320 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[1]) << 8;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
321 /* fall-through */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
322
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
323 default: break;
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
324 }
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
325 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
326 bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
327 if (lastByte == 0) return ERROR(corruption_detected); /* endMark not present */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
328 }
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
329 bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
330 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
331
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
332 return srcSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
333 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
334
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
335 MEM_STATIC size_t BIT_getUpperBits(size_t bitContainer, U32 const start)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
336 {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
337 return bitContainer >> start;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
338 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
339
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
340 MEM_STATIC size_t BIT_getMiddleBits(size_t bitContainer, U32 const start, U32 const nbBits)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
341 {
42070
675775c33ab6 zstandard: vendor python-zstandard 0.11
Gregory Szorc <gregory.szorc@gmail.com>
parents: 40121
diff changeset
342 U32 const regMask = sizeof(bitContainer)*8 - 1;
675775c33ab6 zstandard: vendor python-zstandard 0.11
Gregory Szorc <gregory.szorc@gmail.com>
parents: 40121
diff changeset
343 /* if start > regMask, bitstream is corrupted, and result is undefined */
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
344 assert(nbBits < BIT_MASK_SIZE);
42070
675775c33ab6 zstandard: vendor python-zstandard 0.11
Gregory Szorc <gregory.szorc@gmail.com>
parents: 40121
diff changeset
345 return (bitContainer >> (start & regMask)) & BIT_mask[nbBits];
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
346 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
347
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
348 MEM_STATIC size_t BIT_getLowerBits(size_t bitContainer, U32 const nbBits)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
349 {
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
350 assert(nbBits < BIT_MASK_SIZE);
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
351 return bitContainer & BIT_mask[nbBits];
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
352 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
353
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
354 /*! BIT_lookBits() :
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
355 * Provides next n bits from local register.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
356 * local register is not modified.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
357 * On 32-bits, maxNbBits==24.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
358 * On 64-bits, maxNbBits==56.
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
359 * @return : value extracted */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
360 MEM_STATIC size_t BIT_lookBits(const BIT_DStream_t* bitD, U32 nbBits)
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
361 {
42070
675775c33ab6 zstandard: vendor python-zstandard 0.11
Gregory Szorc <gregory.szorc@gmail.com>
parents: 40121
diff changeset
362 /* arbitrate between double-shift and shift+mask */
675775c33ab6 zstandard: vendor python-zstandard 0.11
Gregory Szorc <gregory.szorc@gmail.com>
parents: 40121
diff changeset
363 #if 1
675775c33ab6 zstandard: vendor python-zstandard 0.11
Gregory Szorc <gregory.szorc@gmail.com>
parents: 40121
diff changeset
364 /* if bitD->bitsConsumed + nbBits > sizeof(bitD->bitContainer)*8,
675775c33ab6 zstandard: vendor python-zstandard 0.11
Gregory Szorc <gregory.szorc@gmail.com>
parents: 40121
diff changeset
365 * bitstream is likely corrupted, and result is undefined */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
366 return BIT_getMiddleBits(bitD->bitContainer, (sizeof(bitD->bitContainer)*8) - bitD->bitsConsumed - nbBits, nbBits);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
367 #else
42070
675775c33ab6 zstandard: vendor python-zstandard 0.11
Gregory Szorc <gregory.szorc@gmail.com>
parents: 40121
diff changeset
368 /* this code path is slower on my os-x laptop */
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
369 U32 const regMask = sizeof(bitD->bitContainer)*8 - 1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
370 return ((bitD->bitContainer << (bitD->bitsConsumed & regMask)) >> 1) >> ((regMask-nbBits) & regMask);
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
371 #endif
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
372 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
373
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
374 /*! BIT_lookBitsFast() :
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
375 * unsafe version; only works if nbBits >= 1 */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
376 MEM_STATIC size_t BIT_lookBitsFast(const BIT_DStream_t* bitD, U32 nbBits)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
377 {
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
378 U32 const regMask = sizeof(bitD->bitContainer)*8 - 1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
379 assert(nbBits >= 1);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
380 return (bitD->bitContainer << (bitD->bitsConsumed & regMask)) >> (((regMask+1)-nbBits) & regMask);
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
381 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
382
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
383 MEM_STATIC void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
384 {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
385 bitD->bitsConsumed += nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
386 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
387
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
388 /*! BIT_readBits() :
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
389 * Read (consume) next n bits from local register and update.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
390 * Pay attention to not read more than nbBits contained into local register.
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
391 * @return : extracted value. */
42070
675775c33ab6 zstandard: vendor python-zstandard 0.11
Gregory Szorc <gregory.szorc@gmail.com>
parents: 40121
diff changeset
392 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits)
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
393 {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
394 size_t const value = BIT_lookBits(bitD, nbBits);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
395 BIT_skipBits(bitD, nbBits);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
396 return value;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
397 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
398
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
399 /*! BIT_readBitsFast() :
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
400 * unsafe version; only works only if nbBits >= 1 */
42070
675775c33ab6 zstandard: vendor python-zstandard 0.11
Gregory Szorc <gregory.szorc@gmail.com>
parents: 40121
diff changeset
401 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits)
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
402 {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
403 size_t const value = BIT_lookBitsFast(bitD, nbBits);
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
404 assert(nbBits >= 1);
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
405 BIT_skipBits(bitD, nbBits);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
406 return value;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
407 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
408
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
409 /*! BIT_reloadDStream() :
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
410 * Refill `bitD` from buffer previously set in BIT_initDStream() .
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
411 * This function is safe, it guarantees it will not read beyond src buffer.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
412 * @return : status of `BIT_DStream_t` internal register.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
413 * when status == BIT_DStream_unfinished, internal register is filled with at least 25 or 57 bits */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
414 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
415 {
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
416 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* overflow detected, like end of stream */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
417 return BIT_DStream_overflow;
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
418
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
419 if (bitD->ptr >= bitD->limitPtr) {
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
420 bitD->ptr -= bitD->bitsConsumed >> 3;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
421 bitD->bitsConsumed &= 7;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
422 bitD->bitContainer = MEM_readLEST(bitD->ptr);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
423 return BIT_DStream_unfinished;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
424 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
425 if (bitD->ptr == bitD->start) {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
426 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
427 return BIT_DStream_completed;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
428 }
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
429 /* start < ptr < limitPtr */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
430 { U32 nbBytes = bitD->bitsConsumed >> 3;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
431 BIT_DStream_status result = BIT_DStream_unfinished;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
432 if (bitD->ptr - nbBytes < bitD->start) {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
433 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
434 result = BIT_DStream_endOfBuffer;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
435 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
436 bitD->ptr -= nbBytes;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
437 bitD->bitsConsumed -= nbBytes*8;
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
438 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD->bitContainer), otherwise bitD->ptr == bitD->start */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
439 return result;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
440 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
441 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
442
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
443 /*! BIT_endOfDStream() :
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
444 * @return : 1 if DStream has _exactly_ reached its end (all bits consumed).
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
445 */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
446 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
447 {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
448 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
449 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
450
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
451 #if defined (__cplusplus)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
452 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
453 #endif
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
454
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
455 #endif /* BITSTREAM_H_MODULE */