bit_reader_utils.c (9097B)
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 non-inlined methods 11 // 12 // Author: Skal (pascal.massimino@gmail.com) 13 14 #ifdef HAVE_CONFIG_H 15 #include "src/webp/config.h" 16 #endif 17 18 #include <assert.h> 19 #include <stddef.h> 20 21 #include "src/webp/types.h" 22 #include "src/dsp/cpu.h" 23 #include "src/utils/bit_reader_inl_utils.h" 24 #include "src/utils/bit_reader_utils.h" 25 #include "src/utils/endian_inl_utils.h" 26 #include "src/utils/utils.h" 27 28 //------------------------------------------------------------------------------ 29 // VP8BitReader 30 31 void VP8BitReaderSetBuffer(VP8BitReader* const br, 32 const uint8_t* const start, 33 size_t size) { 34 assert(start != NULL); 35 br->buf = start; 36 br->buf_end = start + size; 37 br->buf_max = 38 (size >= sizeof(lbit_t)) ? start + size - sizeof(lbit_t) + 1 : start; 39 } 40 41 void VP8InitBitReader(VP8BitReader* const br, 42 const uint8_t* const start, size_t size) { 43 assert(br != NULL); 44 assert(start != NULL); 45 assert(size < (1u << 31)); // limit ensured by format and upstream checks 46 br->range = 255 - 1; 47 br->value = 0; 48 br->bits = -8; // to load the very first 8bits 49 br->eof = 0; 50 VP8BitReaderSetBuffer(br, start, size); 51 VP8LoadNewBytes(br); 52 } 53 54 void VP8RemapBitReader(VP8BitReader* const br, ptrdiff_t offset) { 55 if (br->buf != NULL) { 56 br->buf += offset; 57 br->buf_end += offset; 58 br->buf_max += offset; 59 } 60 } 61 62 const uint8_t kVP8Log2Range[128] = { 63 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 64 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 65 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 66 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 67 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 68 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 69 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 70 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 71 0 72 }; 73 74 // range = ((range - 1) << kVP8Log2Range[range]) + 1 75 const uint8_t kVP8NewRange[128] = { 76 127, 127, 191, 127, 159, 191, 223, 127, 77 143, 159, 175, 191, 207, 223, 239, 127, 78 135, 143, 151, 159, 167, 175, 183, 191, 79 199, 207, 215, 223, 231, 239, 247, 127, 80 131, 135, 139, 143, 147, 151, 155, 159, 81 163, 167, 171, 175, 179, 183, 187, 191, 82 195, 199, 203, 207, 211, 215, 219, 223, 83 227, 231, 235, 239, 243, 247, 251, 127, 84 129, 131, 133, 135, 137, 139, 141, 143, 85 145, 147, 149, 151, 153, 155, 157, 159, 86 161, 163, 165, 167, 169, 171, 173, 175, 87 177, 179, 181, 183, 185, 187, 189, 191, 88 193, 195, 197, 199, 201, 203, 205, 207, 89 209, 211, 213, 215, 217, 219, 221, 223, 90 225, 227, 229, 231, 233, 235, 237, 239, 91 241, 243, 245, 247, 249, 251, 253, 127 92 }; 93 94 void VP8LoadFinalBytes(VP8BitReader* const br) { 95 assert(br != NULL && br->buf != NULL); 96 // Only read 8bits at a time 97 if (br->buf < br->buf_end) { 98 br->bits += 8; 99 br->value = (bit_t)(*br->buf++) | (br->value << 8); 100 } else if (!br->eof) { 101 br->value <<= 8; 102 br->bits += 8; 103 br->eof = 1; 104 } else { 105 br->bits = 0; // This is to avoid undefined behaviour with shifts. 106 } 107 } 108 109 //------------------------------------------------------------------------------ 110 // Higher-level calls 111 112 uint32_t VP8GetValue(VP8BitReader* const br, int bits, const char label[]) { 113 uint32_t v = 0; 114 while (bits-- > 0) { 115 v |= VP8GetBit(br, 0x80, label) << bits; 116 } 117 return v; 118 } 119 120 int32_t VP8GetSignedValue(VP8BitReader* const br, int bits, 121 const char label[]) { 122 const int value = VP8GetValue(br, bits, label); 123 return VP8Get(br, label) ? -value : value; 124 } 125 126 //------------------------------------------------------------------------------ 127 // VP8LBitReader 128 129 #define VP8L_LOG8_WBITS 4 // Number of bytes needed to store VP8L_WBITS bits. 130 131 #if defined(__arm__) || defined(_M_ARM) || WEBP_AARCH64 || \ 132 defined(__i386__) || defined(_M_IX86) || \ 133 defined(__x86_64__) || defined(_M_X64) || \ 134 defined(__wasm__) 135 #define VP8L_USE_FAST_LOAD 136 #endif 137 138 static const uint32_t kBitMask[VP8L_MAX_NUM_BIT_READ + 1] = { 139 0, 140 0x000001, 0x000003, 0x000007, 0x00000f, 141 0x00001f, 0x00003f, 0x00007f, 0x0000ff, 142 0x0001ff, 0x0003ff, 0x0007ff, 0x000fff, 143 0x001fff, 0x003fff, 0x007fff, 0x00ffff, 144 0x01ffff, 0x03ffff, 0x07ffff, 0x0fffff, 145 0x1fffff, 0x3fffff, 0x7fffff, 0xffffff 146 }; 147 148 void VP8LInitBitReader(VP8LBitReader* const br, const uint8_t* const start, 149 size_t length) { 150 size_t i; 151 vp8l_val_t value = 0; 152 assert(br != NULL); 153 assert(start != NULL); 154 assert(length < 0xfffffff8u); // can't happen with a RIFF chunk. 155 156 br->len = length; 157 br->val = 0; 158 br->bit_pos = 0; 159 br->eos = 0; 160 161 if (length > sizeof(br->val)) { 162 length = sizeof(br->val); 163 } 164 for (i = 0; i < length; ++i) { 165 value |= (vp8l_val_t)start[i] << (8 * i); 166 } 167 br->val = value; 168 br->pos = length; 169 br->buf = start; 170 } 171 172 void VP8LBitReaderSetBuffer(VP8LBitReader* const br, 173 const uint8_t* const buf, size_t len) { 174 assert(br != NULL); 175 assert(buf != NULL); 176 assert(len < 0xfffffff8u); // can't happen with a RIFF chunk. 177 br->buf = buf; 178 br->len = len; 179 // 'pos' > 'len' should be considered a param error. 180 br->eos = (br->pos > br->len) || VP8LIsEndOfStream(br); 181 } 182 183 static void VP8LSetEndOfStream(VP8LBitReader* const br) { 184 br->eos = 1; 185 br->bit_pos = 0; // To avoid undefined behaviour with shifts. 186 } 187 188 // If not at EOS, reload up to VP8L_LBITS byte-by-byte 189 static void ShiftBytes(VP8LBitReader* const br) { 190 while (br->bit_pos >= 8 && br->pos < br->len) { 191 br->val >>= 8; 192 br->val |= ((vp8l_val_t)br->buf[br->pos]) << (VP8L_LBITS - 8); 193 ++br->pos; 194 br->bit_pos -= 8; 195 } 196 if (VP8LIsEndOfStream(br)) { 197 VP8LSetEndOfStream(br); 198 } 199 } 200 201 void VP8LDoFillBitWindow(VP8LBitReader* const br) { 202 assert(br->bit_pos >= VP8L_WBITS); 203 #if defined(VP8L_USE_FAST_LOAD) 204 if (br->pos + sizeof(br->val) < br->len) { 205 br->val >>= VP8L_WBITS; 206 br->bit_pos -= VP8L_WBITS; 207 br->val |= (vp8l_val_t)HToLE32(WebPMemToUint32(br->buf + br->pos)) << 208 (VP8L_LBITS - VP8L_WBITS); 209 br->pos += VP8L_LOG8_WBITS; 210 return; 211 } 212 #endif 213 ShiftBytes(br); // Slow path. 214 } 215 216 uint32_t VP8LReadBits(VP8LBitReader* const br, int n_bits) { 217 assert(n_bits >= 0); 218 // Flag an error if end_of_stream or n_bits is more than allowed limit. 219 if (!br->eos && n_bits <= VP8L_MAX_NUM_BIT_READ) { 220 const uint32_t val = VP8LPrefetchBits(br) & kBitMask[n_bits]; 221 const int new_bits = br->bit_pos + n_bits; 222 br->bit_pos = new_bits; 223 ShiftBytes(br); 224 return val; 225 } else { 226 VP8LSetEndOfStream(br); 227 return 0; 228 } 229 } 230 231 //------------------------------------------------------------------------------ 232 // Bit-tracing tool 233 234 #if (BITTRACE > 0) 235 236 #include <stdlib.h> // for atexit() 237 #include <stdio.h> 238 #include <string.h> 239 240 #define MAX_NUM_LABELS 32 241 static struct { 242 const char* label; 243 int size; 244 int count; 245 } kLabels[MAX_NUM_LABELS]; 246 247 static int last_label = 0; 248 static int last_pos = 0; 249 static const uint8_t* buf_start = NULL; 250 static int init_done = 0; 251 252 static void PrintBitTraces(void) { 253 int i; 254 int scale = 1; 255 int total = 0; 256 const char* units = "bits"; 257 #if (BITTRACE == 2) 258 scale = 8; 259 units = "bytes"; 260 #endif 261 for (i = 0; i < last_label; ++i) total += kLabels[i].size; 262 if (total < 1) total = 1; // avoid rounding errors 263 printf("=== Bit traces ===\n"); 264 for (i = 0; i < last_label; ++i) { 265 const int skip = 16 - (int)strlen(kLabels[i].label); 266 const int value = (kLabels[i].size + scale - 1) / scale; 267 assert(skip > 0); 268 printf("%s \%*s: %6d %s \t[%5.2f%%] [count: %7d]\n", 269 kLabels[i].label, skip, "", value, units, 270 100.f * kLabels[i].size / total, 271 kLabels[i].count); 272 } 273 total = (total + scale - 1) / scale; 274 printf("Total: %d %s\n", total, units); 275 } 276 277 void BitTrace(const struct VP8BitReader* const br, const char label[]) { 278 int i, pos; 279 if (!init_done) { 280 memset(kLabels, 0, sizeof(kLabels)); 281 atexit(PrintBitTraces); 282 buf_start = br->buf; 283 init_done = 1; 284 } 285 pos = (int)(br->buf - buf_start) * 8 - br->bits; 286 // if there's a too large jump, we've changed partition -> reset counter 287 if (abs(pos - last_pos) > 32) { 288 buf_start = br->buf; 289 pos = 0; 290 last_pos = 0; 291 } 292 if (br->range >= 0x7f) pos += kVP8Log2Range[br->range - 0x7f]; 293 for (i = 0; i < last_label; ++i) { 294 if (!strcmp(label, kLabels[i].label)) break; 295 } 296 if (i == MAX_NUM_LABELS) abort(); // overflow! 297 kLabels[i].label = label; 298 kLabels[i].size += pos - last_pos; 299 kLabels[i].count += 1; 300 if (i == last_label) ++last_label; 301 last_pos = pos; 302 } 303 304 #endif // BITTRACE > 0 305 306 //------------------------------------------------------------------------------