1 /* Copyright 2013 Google Inc. All Rights Reserved.
2
3 Licensed under the Apache License, Version 2.0 (the "License");
4 you may not use this file except in compliance with the License.
5 You may obtain a copy of the License at
6
7 http://www.apache.org/licenses/LICENSE-2.0
8
9 Unless required by applicable law or agreed to in writing, software
10 distributed under the License is distributed on an "AS IS" BASIS,
11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 See the License for the specific language governing permissions and
13 limitations under the License.
14
15 Bit reading helpers
16 */
17
18 #ifndef BROTLI_DEC_BIT_READER_H_
19 #define BROTLI_DEC_BIT_READER_H_
20
21 #include <string.h>
22 #include "./streams.h"
23 #include "./types.h"
24
25 #if defined(__cplusplus) || defined(c_plusplus)
26 extern "C" {
27 #endif
28
29 #define BROTLI_MAX_NUM_BIT_READ 25
30 #define BROTLI_READ_SIZE 4096
31 #define BROTLI_IBUF_SIZE (2 * BROTLI_READ_SIZE + 32)
32 #define BROTLI_IBUF_MASK (2 * BROTLI_READ_SIZE - 1)
33
34 #define UNALIGNED_COPY64(dst, src) memcpy(dst, src, 8)
35
36 static const uint32_t kBitMask[BROTLI_MAX_NUM_BIT_READ] = {
37 0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767,
38 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215
39 };
40
41 typedef struct {
42 /* Input byte buffer, consist of a ringbuffer and a "slack" region where */
43 /* bytes from the start of the ringbuffer are copied. */
44 uint8_t buf_[BROTLI_IBUF_SIZE];
45 uint8_t* buf_ptr_; /* next input will write here */
46 BrotliInput input_; /* input callback */
47 uint64_t val_; /* pre-fetched bits */
48 uint32_t pos_; /* byte position in stream */
49 uint32_t bit_pos_; /* current bit-reading position in val_ */
50 uint32_t bit_end_pos_; /* bit-reading end position from LSB of val_ */
51 int eos_; /* input stream is finished */
52 } BrotliBitReader;
53
54 int BrotliInitBitReader(BrotliBitReader* const br, BrotliInput input);
55
56 /* Return the prefetched bits, so they can be looked up. */
BrotliPrefetchBits(BrotliBitReader * const br)57 static BROTLI_INLINE uint32_t BrotliPrefetchBits(BrotliBitReader* const br) {
58 return (uint32_t)(br->val_ >> br->bit_pos_);
59 }
60
61 /* For jumping over a number of bits in the bit stream when accessed with */
62 /* BrotliPrefetchBits and BrotliFillBitWindow. */
BrotliSetBitPos(BrotliBitReader * const br,uint32_t val)63 static BROTLI_INLINE void BrotliSetBitPos(BrotliBitReader* const br,
64 uint32_t val) {
65 #ifdef BROTLI_DECODE_DEBUG
66 uint32_t n_bits = val - br->bit_pos_;
67 const uint32_t bval = (uint32_t)(br->val_ >> br->bit_pos_) & kBitMask[n_bits];
68 printf("[BrotliReadBits] %010d %2d val: %6x\n",
69 (br->pos_ << 3) + br->bit_pos_ - 64, n_bits, bval);
70 #endif
71 br->bit_pos_ = val;
72 }
73
74 /* Reload up to 64 bits byte-by-byte */
ShiftBytes(BrotliBitReader * const br)75 static BROTLI_INLINE void ShiftBytes(BrotliBitReader* const br) {
76 while (br->bit_pos_ >= 8) {
77 br->val_ >>= 8;
78 br->val_ |= ((uint64_t)br->buf_[br->pos_ & BROTLI_IBUF_MASK]) << 56;
79 ++br->pos_;
80 br->bit_pos_ -= 8;
81 br->bit_end_pos_ -= 8;
82 }
83 }
84
85 /* Fills up the input ringbuffer by calling the input callback.
86
87 Does nothing if there are at least 32 bytes present after current position.
88
89 Returns 0 if either:
90 - the input callback returned an error, or
91 - there is no more input and the position is past the end of the stream.
92
93 After encountering the end of the input stream, 32 additional zero bytes are
94 copied to the ringbuffer, therefore it is safe to call this function after
95 every 32 bytes of input is read.
96 */
BrotliReadMoreInput(BrotliBitReader * const br)97 static BROTLI_INLINE int BrotliReadMoreInput(BrotliBitReader* const br) {
98 if (br->bit_end_pos_ > 256) {
99 return 1;
100 } else if (br->eos_) {
101 return br->bit_pos_ <= br->bit_end_pos_;
102 } else {
103 uint8_t* dst = br->buf_ptr_;
104 int bytes_read = BrotliRead(br->input_, dst, BROTLI_READ_SIZE);
105 if (bytes_read < 0) {
106 return 0;
107 }
108 if (bytes_read < BROTLI_READ_SIZE) {
109 br->eos_ = 1;
110 /* Store 32 bytes of zero after the stream end. */
111 #if (defined(__x86_64__) || defined(_M_X64))
112 *(uint64_t*)(dst + bytes_read) = 0;
113 *(uint64_t*)(dst + bytes_read + 8) = 0;
114 *(uint64_t*)(dst + bytes_read + 16) = 0;
115 *(uint64_t*)(dst + bytes_read + 24) = 0;
116 #else
117 memset(dst + bytes_read, 0, 32);
118 #endif
119 }
120 if (dst == br->buf_) {
121 /* Copy the head of the ringbuffer to the slack region. */
122 #if (defined(__x86_64__) || defined(_M_X64))
123 UNALIGNED_COPY64(br->buf_ + BROTLI_IBUF_SIZE - 32, br->buf_);
124 UNALIGNED_COPY64(br->buf_ + BROTLI_IBUF_SIZE - 24, br->buf_ + 8);
125 UNALIGNED_COPY64(br->buf_ + BROTLI_IBUF_SIZE - 16, br->buf_ + 16);
126 UNALIGNED_COPY64(br->buf_ + BROTLI_IBUF_SIZE - 8, br->buf_ + 24);
127 #else
128 memcpy(br->buf_ + (BROTLI_READ_SIZE << 1), br->buf_, 32);
129 #endif
130 br->buf_ptr_ = br->buf_ + BROTLI_READ_SIZE;
131 } else {
132 br->buf_ptr_ = br->buf_;
133 }
134 br->bit_end_pos_ += ((uint32_t)bytes_read << 3);
135 return 1;
136 }
137 }
138
139 /* Advances the Read buffer by 5 bytes to make room for reading next 24 bits. */
BrotliFillBitWindow(BrotliBitReader * const br)140 static BROTLI_INLINE void BrotliFillBitWindow(BrotliBitReader* const br) {
141 if (br->bit_pos_ >= 40) {
142 #if (defined(__x86_64__) || defined(_M_X64))
143 br->val_ >>= 40;
144 /* The expression below needs a little-endian arch to work correctly. */
145 /* This gives a large speedup for decoding speed. */
146 br->val_ |= *(const uint64_t*)(
147 br->buf_ + (br->pos_ & BROTLI_IBUF_MASK)) << 24;
148 br->pos_ += 5;
149 br->bit_pos_ -= 40;
150 br->bit_end_pos_ -= 40;
151 #else
152 ShiftBytes(br);
153 #endif
154 }
155 }
156
157 /* Reads the specified number of bits from Read Buffer. */
BrotliReadBits(BrotliBitReader * const br,int n_bits)158 static BROTLI_INLINE uint32_t BrotliReadBits(
159 BrotliBitReader* const br, int n_bits) {
160 uint32_t val;
161 BrotliFillBitWindow(br);
162 val = (uint32_t)(br->val_ >> br->bit_pos_) & kBitMask[n_bits];
163 #ifdef BROTLI_DECODE_DEBUG
164 printf("[BrotliReadBits] %010d %2d val: %6x\n",
165 (br->pos_ << 3) + br->bit_pos_ - 64, n_bits, val);
166 #endif
167 br->bit_pos_ += (uint32_t)n_bits;
168 return val;
169 }
170
171 #if defined(__cplusplus) || defined(c_plusplus)
172 } /* extern "C" */
173 #endif
174
175 #endif /* BROTLI_DEC_BIT_READER_H_ */
176