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