1 /*
2 * Copyright © 2018, VideoLAN and dav1d authors
3 * Copyright © 2018, Two Orioles, LLC
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright notice, this
10 * list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright notice,
13 * this list of conditions and the following disclaimer in the documentation
14 * and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
20 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27
28 #include "config.h"
29
30 #include <limits.h>
31
32 #include "common/intops.h"
33
34 #include "src/getbits.h"
35
dav1d_init_get_bits(GetBits * const c,const uint8_t * const data,const size_t sz)36 void dav1d_init_get_bits(GetBits *const c, const uint8_t *const data,
37 const size_t sz)
38 {
39 assert(sz);
40 c->ptr = c->ptr_start = data;
41 c->ptr_end = &c->ptr_start[sz];
42 c->state = 0;
43 c->bits_left = 0;
44 c->error = 0;
45 }
46
dav1d_get_bit(GetBits * const c)47 unsigned dav1d_get_bit(GetBits *const c) {
48 if (!c->bits_left) {
49 if (c->ptr >= c->ptr_end) {
50 c->error = 1;
51 } else {
52 const unsigned state = *c->ptr++;
53 c->bits_left = 7;
54 c->state = (uint64_t) state << 57;
55 return state >> 7;
56 }
57 }
58
59 const uint64_t state = c->state;
60 c->bits_left--;
61 c->state = state << 1;
62 return (unsigned) (state >> 63);
63 }
64
refill(GetBits * const c,const int n)65 static inline void refill(GetBits *const c, const int n) {
66 assert(c->bits_left >= 0 && c->bits_left < 32);
67 unsigned state = 0;
68 do {
69 if (c->ptr >= c->ptr_end) {
70 c->error = 1;
71 if (state) break;
72 return;
73 }
74 state = (state << 8) | *c->ptr++;
75 c->bits_left += 8;
76 } while (n > c->bits_left);
77 c->state |= (uint64_t) state << (64 - c->bits_left);
78 }
79
80 #define GET_BITS(name, type, type64) \
81 type name(GetBits *const c, const int n) { \
82 assert(n > 0 && n <= 32); \
83 /* Unsigned cast avoids refill after eob */ \
84 if ((unsigned) n > (unsigned) c->bits_left) \
85 refill(c, n); \
86 const uint64_t state = c->state; \
87 c->bits_left -= n; \
88 c->state = state << n; \
89 return (type) ((type64) state >> (64 - n)); \
90 }
91
GET_BITS(dav1d_get_bits,unsigned,uint64_t)92 GET_BITS(dav1d_get_bits, unsigned, uint64_t)
93 GET_BITS(dav1d_get_sbits, int, int64_t)
94
95 unsigned dav1d_get_uleb128(GetBits *const c) {
96 uint64_t val = 0;
97 unsigned i = 0, more;
98
99 do {
100 const int v = dav1d_get_bits(c, 8);
101 more = v & 0x80;
102 val |= ((uint64_t) (v & 0x7F)) << i;
103 i += 7;
104 } while (more && i < 56);
105
106 if (val > UINT_MAX || more) {
107 c->error = 1;
108 return 0;
109 }
110
111 return (unsigned) val;
112 }
113
dav1d_get_uniform(GetBits * const c,const unsigned max)114 unsigned dav1d_get_uniform(GetBits *const c, const unsigned max) {
115 // Output in range [0..max-1]
116 // max must be > 1, or else nothing is read from the bitstream
117 assert(max > 1);
118 const int l = ulog2(max) + 1;
119 assert(l > 1);
120 const unsigned m = (1U << l) - max;
121 const unsigned v = dav1d_get_bits(c, l - 1);
122 return v < m ? v : (v << 1) - m + dav1d_get_bit(c);
123 }
124
dav1d_get_vlc(GetBits * const c)125 unsigned dav1d_get_vlc(GetBits *const c) {
126 if (dav1d_get_bit(c))
127 return 0;
128
129 int n_bits = 0;
130 do {
131 if (++n_bits == 32)
132 return 0xFFFFFFFFU;
133 } while (!dav1d_get_bit(c));
134
135 return ((1U << n_bits) - 1) + dav1d_get_bits(c, n_bits);
136 }
137
get_bits_subexp_u(GetBits * const c,const unsigned ref,const unsigned n)138 static unsigned get_bits_subexp_u(GetBits *const c, const unsigned ref,
139 const unsigned n)
140 {
141 unsigned v = 0;
142
143 for (int i = 0;; i++) {
144 const int b = i ? 3 + i - 1 : 3;
145
146 if (n < v + 3 * (1 << b)) {
147 v += dav1d_get_uniform(c, n - v + 1);
148 break;
149 }
150
151 if (!dav1d_get_bit(c)) {
152 v += dav1d_get_bits(c, b);
153 break;
154 }
155
156 v += 1 << b;
157 }
158
159 return ref * 2 <= n ? inv_recenter(ref, v) : n - inv_recenter(n - ref, v);
160 }
161
dav1d_get_bits_subexp(GetBits * const c,const int ref,const unsigned n)162 int dav1d_get_bits_subexp(GetBits *const c, const int ref, const unsigned n) {
163 return (int) get_bits_subexp_u(c, ref + (1 << n), 2 << n) - (1 << n);
164 }
165