1 // Copyright 2010 Google Inc. All Rights Reserved.
2 //
3 // Use of this source code is governed by a BSD-style license
4 // that can be found in the COPYING file in the root of the source
5 // tree. An additional intellectual property rights grant can be found
6 // in the file PATENTS. All contributing project authors may
7 // be found in the AUTHORS file in the root of the source tree.
8 // -----------------------------------------------------------------------------
9 //
10 // Boolean decoder
11 //
12 // Author: Skal (pascal.massimino@gmail.com)
13
14 #include "./bit_reader.h"
15
16 #if defined(__cplusplus) || defined(c_plusplus)
17 extern "C" {
18 #endif
19
20 #ifndef USE_RIGHT_JUSTIFY
21 #define MK(X) (((range_t)(X) << (BITS)) | (MASK))
22 #else
23 #define MK(X) ((range_t)(X))
24 #endif
25
26 //------------------------------------------------------------------------------
27 // VP8BitReader
28
VP8InitBitReader(VP8BitReader * const br,const uint8_t * const start,const uint8_t * const end)29 void VP8InitBitReader(VP8BitReader* const br,
30 const uint8_t* const start, const uint8_t* const end) {
31 assert(br != NULL);
32 assert(start != NULL);
33 assert(start <= end);
34 br->range_ = MK(255 - 1);
35 br->buf_ = start;
36 br->buf_end_ = end;
37 br->value_ = 0;
38 br->bits_ = -8; // to load the very first 8bits
39 br->eof_ = 0;
40 }
41
42 const uint8_t kVP8Log2Range[128] = {
43 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
44 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
45 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
46 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
47 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
48 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
49 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
50 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
51 0
52 };
53
54 // range = (range << kVP8Log2Range[range]) + trailing 1's
55 const range_t kVP8NewRange[128] = {
56 MK(127), MK(127), MK(191), MK(127), MK(159), MK(191), MK(223), MK(127),
57 MK(143), MK(159), MK(175), MK(191), MK(207), MK(223), MK(239), MK(127),
58 MK(135), MK(143), MK(151), MK(159), MK(167), MK(175), MK(183), MK(191),
59 MK(199), MK(207), MK(215), MK(223), MK(231), MK(239), MK(247), MK(127),
60 MK(131), MK(135), MK(139), MK(143), MK(147), MK(151), MK(155), MK(159),
61 MK(163), MK(167), MK(171), MK(175), MK(179), MK(183), MK(187), MK(191),
62 MK(195), MK(199), MK(203), MK(207), MK(211), MK(215), MK(219), MK(223),
63 MK(227), MK(231), MK(235), MK(239), MK(243), MK(247), MK(251), MK(127),
64 MK(129), MK(131), MK(133), MK(135), MK(137), MK(139), MK(141), MK(143),
65 MK(145), MK(147), MK(149), MK(151), MK(153), MK(155), MK(157), MK(159),
66 MK(161), MK(163), MK(165), MK(167), MK(169), MK(171), MK(173), MK(175),
67 MK(177), MK(179), MK(181), MK(183), MK(185), MK(187), MK(189), MK(191),
68 MK(193), MK(195), MK(197), MK(199), MK(201), MK(203), MK(205), MK(207),
69 MK(209), MK(211), MK(213), MK(215), MK(217), MK(219), MK(221), MK(223),
70 MK(225), MK(227), MK(229), MK(231), MK(233), MK(235), MK(237), MK(239),
71 MK(241), MK(243), MK(245), MK(247), MK(249), MK(251), MK(253), MK(127)
72 };
73
74 #undef MK
75
VP8LoadFinalBytes(VP8BitReader * const br)76 void VP8LoadFinalBytes(VP8BitReader* const br) {
77 assert(br != NULL && br->buf_ != NULL);
78 // Only read 8bits at a time
79 if (br->buf_ < br->buf_end_) {
80 #ifndef USE_RIGHT_JUSTIFY
81 br->value_ |= (bit_t)(*br->buf_++) << ((BITS) - 8 - br->bits_);
82 #else
83 br->value_ = (bit_t)(*br->buf_++) | (br->value_ << 8);
84 #endif
85 br->bits_ += 8;
86 } else if (!br->eof_) {
87 #ifdef USE_RIGHT_JUSTIFY
88 // These are not strictly needed, but it makes the behaviour
89 // consistent for both USE_RIGHT_JUSTIFY and !USE_RIGHT_JUSTIFY.
90 br->value_ <<= 8;
91 br->bits_ += 8;
92 #endif
93 br->eof_ = 1;
94 }
95 }
96
97 //------------------------------------------------------------------------------
98 // Higher-level calls
99
VP8GetValue(VP8BitReader * const br,int bits)100 uint32_t VP8GetValue(VP8BitReader* const br, int bits) {
101 uint32_t v = 0;
102 while (bits-- > 0) {
103 v |= VP8GetBit(br, 0x80) << bits;
104 }
105 return v;
106 }
107
VP8GetSignedValue(VP8BitReader * const br,int bits)108 int32_t VP8GetSignedValue(VP8BitReader* const br, int bits) {
109 const int value = VP8GetValue(br, bits);
110 return VP8Get(br) ? -value : value;
111 }
112
113 //------------------------------------------------------------------------------
114 // VP8LBitReader
115
116 #define MAX_NUM_BIT_READ 25
117
118 #define LBITS 64 // Number of bits prefetched.
119 #define WBITS 32 // Minimum number of bytes needed after VP8LFillBitWindow.
120 #define LOG8_WBITS 4 // Number of bytes needed to store WBITS bits.
121
122 static const uint32_t kBitMask[MAX_NUM_BIT_READ] = {
123 0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767,
124 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215
125 };
126
VP8LInitBitReader(VP8LBitReader * const br,const uint8_t * const start,size_t length)127 void VP8LInitBitReader(VP8LBitReader* const br,
128 const uint8_t* const start,
129 size_t length) {
130 size_t i;
131 assert(br != NULL);
132 assert(start != NULL);
133 assert(length < 0xfffffff8u); // can't happen with a RIFF chunk.
134
135 br->buf_ = start;
136 br->len_ = length;
137 br->val_ = 0;
138 br->pos_ = 0;
139 br->bit_pos_ = 0;
140 br->eos_ = 0;
141 br->error_ = 0;
142 for (i = 0; i < sizeof(br->val_) && i < br->len_; ++i) {
143 br->val_ |= ((vp8l_val_t)br->buf_[br->pos_]) << (8 * i);
144 ++br->pos_;
145 }
146 }
147
VP8LBitReaderSetBuffer(VP8LBitReader * const br,const uint8_t * const buf,size_t len)148 void VP8LBitReaderSetBuffer(VP8LBitReader* const br,
149 const uint8_t* const buf, size_t len) {
150 assert(br != NULL);
151 assert(buf != NULL);
152 assert(len < 0xfffffff8u); // can't happen with a RIFF chunk.
153 br->eos_ = (br->pos_ >= len);
154 br->buf_ = buf;
155 br->len_ = len;
156 }
157
158 // If not at EOS, reload up to LBITS byte-by-byte
ShiftBytes(VP8LBitReader * const br)159 static void ShiftBytes(VP8LBitReader* const br) {
160 while (br->bit_pos_ >= 8 && br->pos_ < br->len_) {
161 br->val_ >>= 8;
162 br->val_ |= ((vp8l_val_t)br->buf_[br->pos_]) << (LBITS - 8);
163 ++br->pos_;
164 br->bit_pos_ -= 8;
165 }
166 }
167
VP8LFillBitWindow(VP8LBitReader * const br)168 void VP8LFillBitWindow(VP8LBitReader* const br) {
169 if (br->bit_pos_ >= WBITS) {
170 #if (defined(__x86_64__) || defined(_M_X64))
171 if (br->pos_ + sizeof(br->val_) < br->len_) {
172 br->val_ >>= WBITS;
173 br->bit_pos_ -= WBITS;
174 // The expression below needs a little-endian arch to work correctly.
175 // This gives a large speedup for decoding speed.
176 br->val_ |= *(const vp8l_val_t*)(br->buf_ + br->pos_) << (LBITS - WBITS);
177 br->pos_ += LOG8_WBITS;
178 return;
179 }
180 #endif
181 ShiftBytes(br); // Slow path.
182 if (br->pos_ == br->len_ && br->bit_pos_ == LBITS) {
183 br->eos_ = 1;
184 }
185 }
186 }
187
VP8LReadBits(VP8LBitReader * const br,int n_bits)188 uint32_t VP8LReadBits(VP8LBitReader* const br, int n_bits) {
189 assert(n_bits >= 0);
190 // Flag an error if end_of_stream or n_bits is more than allowed limit.
191 if (!br->eos_ && n_bits < MAX_NUM_BIT_READ) {
192 const uint32_t val =
193 (uint32_t)(br->val_ >> br->bit_pos_) & kBitMask[n_bits];
194 const int new_bits = br->bit_pos_ + n_bits;
195 br->bit_pos_ = new_bits;
196 // If this read is going to cross the read buffer, set the eos flag.
197 if (br->pos_ == br->len_) {
198 if (new_bits >= LBITS) {
199 br->eos_ = 1;
200 }
201 }
202 ShiftBytes(br);
203 return val;
204 } else {
205 br->error_ = 1;
206 return 0;
207 }
208 }
209
210 //------------------------------------------------------------------------------
211
212 #if defined(__cplusplus) || defined(c_plusplus)
213 } // extern "C"
214 #endif
215