blob: 79f64d36e486ce2572f52b6649a00367e3bb26f2 [file] [log] [blame]
Vikas Aroraa2415722012-08-09 16:18:58 -07001// Copyright 2010 Google Inc. All Rights Reserved.
2//
Vikas Arora0406ce12013-08-09 15:57:12 -07003// 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.
Vikas Aroraa2415722012-08-09 16:18:58 -07008// -----------------------------------------------------------------------------
9//
10// Boolean decoder
11//
12// Author: Skal (pascal.massimino@gmail.com)
13
14#include "./bit_reader.h"
15
Vikas Arora1e7bf882013-03-13 16:43:18 -070016#ifndef USE_RIGHT_JUSTIFY
17#define MK(X) (((range_t)(X) << (BITS)) | (MASK))
18#else
19#define MK(X) ((range_t)(X))
20#endif
Vikas Aroraa2415722012-08-09 16:18:58 -070021
22//------------------------------------------------------------------------------
23// VP8BitReader
24
25void VP8InitBitReader(VP8BitReader* const br,
26 const uint8_t* const start, const uint8_t* const end) {
27 assert(br != NULL);
28 assert(start != NULL);
29 assert(start <= end);
30 br->range_ = MK(255 - 1);
31 br->buf_ = start;
32 br->buf_end_ = end;
33 br->value_ = 0;
Vikas Arora1e7bf882013-03-13 16:43:18 -070034 br->bits_ = -8; // to load the very first 8bits
Vikas Aroraa2415722012-08-09 16:18:58 -070035 br->eof_ = 0;
36}
37
38const uint8_t kVP8Log2Range[128] = {
39 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
40 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
41 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
42 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
43 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
44 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
45 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
46 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
47 0
48};
49
50// range = (range << kVP8Log2Range[range]) + trailing 1's
Vikas Arora1e7bf882013-03-13 16:43:18 -070051const range_t kVP8NewRange[128] = {
Vikas Aroraa2415722012-08-09 16:18:58 -070052 MK(127), MK(127), MK(191), MK(127), MK(159), MK(191), MK(223), MK(127),
53 MK(143), MK(159), MK(175), MK(191), MK(207), MK(223), MK(239), MK(127),
54 MK(135), MK(143), MK(151), MK(159), MK(167), MK(175), MK(183), MK(191),
55 MK(199), MK(207), MK(215), MK(223), MK(231), MK(239), MK(247), MK(127),
56 MK(131), MK(135), MK(139), MK(143), MK(147), MK(151), MK(155), MK(159),
57 MK(163), MK(167), MK(171), MK(175), MK(179), MK(183), MK(187), MK(191),
58 MK(195), MK(199), MK(203), MK(207), MK(211), MK(215), MK(219), MK(223),
59 MK(227), MK(231), MK(235), MK(239), MK(243), MK(247), MK(251), MK(127),
60 MK(129), MK(131), MK(133), MK(135), MK(137), MK(139), MK(141), MK(143),
61 MK(145), MK(147), MK(149), MK(151), MK(153), MK(155), MK(157), MK(159),
62 MK(161), MK(163), MK(165), MK(167), MK(169), MK(171), MK(173), MK(175),
63 MK(177), MK(179), MK(181), MK(183), MK(185), MK(187), MK(189), MK(191),
64 MK(193), MK(195), MK(197), MK(199), MK(201), MK(203), MK(205), MK(207),
65 MK(209), MK(211), MK(213), MK(215), MK(217), MK(219), MK(221), MK(223),
66 MK(225), MK(227), MK(229), MK(231), MK(233), MK(235), MK(237), MK(239),
67 MK(241), MK(243), MK(245), MK(247), MK(249), MK(251), MK(253), MK(127)
68};
69
70#undef MK
71
72void VP8LoadFinalBytes(VP8BitReader* const br) {
73 assert(br != NULL && br->buf_ != NULL);
74 // Only read 8bits at a time
75 if (br->buf_ < br->buf_end_) {
Vikas Arora1e7bf882013-03-13 16:43:18 -070076#ifndef USE_RIGHT_JUSTIFY
77 br->value_ |= (bit_t)(*br->buf_++) << ((BITS) - 8 - br->bits_);
78#else
79 br->value_ = (bit_t)(*br->buf_++) | (br->value_ << 8);
80#endif
81 br->bits_ += 8;
82 } else if (!br->eof_) {
83#ifdef USE_RIGHT_JUSTIFY
84 // These are not strictly needed, but it makes the behaviour
85 // consistent for both USE_RIGHT_JUSTIFY and !USE_RIGHT_JUSTIFY.
86 br->value_ <<= 8;
87 br->bits_ += 8;
88#endif
Vikas Aroraa2415722012-08-09 16:18:58 -070089 br->eof_ = 1;
90 }
91}
92
93//------------------------------------------------------------------------------
94// Higher-level calls
95
96uint32_t VP8GetValue(VP8BitReader* const br, int bits) {
97 uint32_t v = 0;
98 while (bits-- > 0) {
99 v |= VP8GetBit(br, 0x80) << bits;
100 }
101 return v;
102}
103
104int32_t VP8GetSignedValue(VP8BitReader* const br, int bits) {
105 const int value = VP8GetValue(br, bits);
106 return VP8Get(br) ? -value : value;
107}
108
109//------------------------------------------------------------------------------
110// VP8LBitReader
111
112#define MAX_NUM_BIT_READ 25
113
Vikas Arora1e7bf882013-03-13 16:43:18 -0700114#define LBITS 64 // Number of bits prefetched.
115#define WBITS 32 // Minimum number of bytes needed after VP8LFillBitWindow.
116#define LOG8_WBITS 4 // Number of bytes needed to store WBITS bits.
117
Vikas Aroraa2415722012-08-09 16:18:58 -0700118static const uint32_t kBitMask[MAX_NUM_BIT_READ] = {
119 0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767,
120 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215
121};
122
123void VP8LInitBitReader(VP8LBitReader* const br,
124 const uint8_t* const start,
125 size_t length) {
126 size_t i;
127 assert(br != NULL);
128 assert(start != NULL);
129 assert(length < 0xfffffff8u); // can't happen with a RIFF chunk.
130
131 br->buf_ = start;
132 br->len_ = length;
133 br->val_ = 0;
134 br->pos_ = 0;
135 br->bit_pos_ = 0;
136 br->eos_ = 0;
137 br->error_ = 0;
138 for (i = 0; i < sizeof(br->val_) && i < br->len_; ++i) {
Vikas Arora1e7bf882013-03-13 16:43:18 -0700139 br->val_ |= ((vp8l_val_t)br->buf_[br->pos_]) << (8 * i);
Vikas Aroraa2415722012-08-09 16:18:58 -0700140 ++br->pos_;
141 }
142}
143
Urvang Joshi40d32742014-04-22 17:24:23 -0700144// Special version that assumes br->pos_ <= br_len_.
145static int IsEndOfStreamSpecial(const VP8LBitReader* const br) {
146 assert(br->pos_ <= br->len_);
147 return br->pos_ == br->len_ && br->bit_pos_ >= LBITS;
148}
149
150static int IsEndOfStream(const VP8LBitReader* const br) {
151 return (br->pos_ > br->len_) || IsEndOfStreamSpecial(br);
152}
153
Vikas Aroraa2415722012-08-09 16:18:58 -0700154void VP8LBitReaderSetBuffer(VP8LBitReader* const br,
155 const uint8_t* const buf, size_t len) {
156 assert(br != NULL);
157 assert(buf != NULL);
158 assert(len < 0xfffffff8u); // can't happen with a RIFF chunk.
Vikas Aroraa2415722012-08-09 16:18:58 -0700159 br->buf_ = buf;
160 br->len_ = len;
Urvang Joshi40d32742014-04-22 17:24:23 -0700161 br->eos_ = IsEndOfStream(br);
Vikas Aroraa2415722012-08-09 16:18:58 -0700162}
163
Vikas Arora1e7bf882013-03-13 16:43:18 -0700164// If not at EOS, reload up to LBITS byte-by-byte
Vikas Aroraa2415722012-08-09 16:18:58 -0700165static void ShiftBytes(VP8LBitReader* const br) {
166 while (br->bit_pos_ >= 8 && br->pos_ < br->len_) {
167 br->val_ >>= 8;
Vikas Arora1e7bf882013-03-13 16:43:18 -0700168 br->val_ |= ((vp8l_val_t)br->buf_[br->pos_]) << (LBITS - 8);
Vikas Aroraa2415722012-08-09 16:18:58 -0700169 ++br->pos_;
170 br->bit_pos_ -= 8;
171 }
172}
173
174void VP8LFillBitWindow(VP8LBitReader* const br) {
Vikas Arora1e7bf882013-03-13 16:43:18 -0700175 if (br->bit_pos_ >= WBITS) {
176#if (defined(__x86_64__) || defined(_M_X64))
177 if (br->pos_ + sizeof(br->val_) < br->len_) {
178 br->val_ >>= WBITS;
179 br->bit_pos_ -= WBITS;
Vikas Aroraa2415722012-08-09 16:18:58 -0700180 // The expression below needs a little-endian arch to work correctly.
181 // This gives a large speedup for decoding speed.
Vikas Arora1e7bf882013-03-13 16:43:18 -0700182 br->val_ |= *(const vp8l_val_t*)(br->buf_ + br->pos_) << (LBITS - WBITS);
183 br->pos_ += LOG8_WBITS;
184 return;
Vikas Aroraa2415722012-08-09 16:18:58 -0700185 }
Vikas Aroraa2415722012-08-09 16:18:58 -0700186#endif
Vikas Arora1e7bf882013-03-13 16:43:18 -0700187 ShiftBytes(br); // Slow path.
Urvang Joshi40d32742014-04-22 17:24:23 -0700188 br->eos_ = IsEndOfStreamSpecial(br);
Vikas Aroraa2415722012-08-09 16:18:58 -0700189 }
Vikas Aroraa2415722012-08-09 16:18:58 -0700190}
191
192uint32_t VP8LReadBits(VP8LBitReader* const br, int n_bits) {
Vikas Aroraa2415722012-08-09 16:18:58 -0700193 assert(n_bits >= 0);
194 // Flag an error if end_of_stream or n_bits is more than allowed limit.
195 if (!br->eos_ && n_bits < MAX_NUM_BIT_READ) {
Vikas Arora1e7bf882013-03-13 16:43:18 -0700196 const uint32_t val =
197 (uint32_t)(br->val_ >> br->bit_pos_) & kBitMask[n_bits];
198 const int new_bits = br->bit_pos_ + n_bits;
199 br->bit_pos_ = new_bits;
Vikas Aroraa2415722012-08-09 16:18:58 -0700200 // If this read is going to cross the read buffer, set the eos flag.
Urvang Joshi40d32742014-04-22 17:24:23 -0700201 br->eos_ = IsEndOfStreamSpecial(br);
Vikas Arora1e7bf882013-03-13 16:43:18 -0700202 ShiftBytes(br);
203 return val;
Vikas Aroraa2415722012-08-09 16:18:58 -0700204 } else {
205 br->error_ = 1;
Vikas Arora1e7bf882013-03-13 16:43:18 -0700206 return 0;
Vikas Aroraa2415722012-08-09 16:18:58 -0700207 }
Vikas Aroraa2415722012-08-09 16:18:58 -0700208}
209
210//------------------------------------------------------------------------------
211