golomb.h (15601B)
1 /* 2 * exp golomb vlc stuff 3 * Copyright (c) 2003 Michael Niedermayer <michaelni@gmx.at> 4 * Copyright (c) 2004 Alex Beregszaszi 5 * 6 * This file is part of FFmpeg. 7 * 8 * FFmpeg is free software; you can redistribute it and/or 9 * modify it under the terms of the GNU Lesser General Public 10 * License as published by the Free Software Foundation; either 11 * version 2.1 of the License, or (at your option) any later version. 12 * 13 * FFmpeg is distributed in the hope that it will be useful, 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 16 * Lesser General Public License for more details. 17 * 18 * You should have received a copy of the GNU Lesser General Public 19 * License along with FFmpeg; if not, write to the Free Software 20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 21 */ 22 23 /** 24 * @file 25 * @brief 26 * exp golomb vlc stuff 27 * @author Michael Niedermayer <michaelni@gmx.at> and Alex Beregszaszi 28 */ 29 30 #ifndef AVCODEC_GOLOMB_H 31 #define AVCODEC_GOLOMB_H 32 33 #include <stdint.h> 34 35 #include "get_bits.h" 36 37 #define INVALID_VLC 0x80000000 38 39 extern const uint8_t ff_golomb_vlc_len[512]; 40 extern const uint8_t ff_ue_golomb_vlc_code[512]; 41 extern const int8_t ff_se_golomb_vlc_code[512]; 42 43 extern const uint8_t ff_interleaved_golomb_vlc_len[256]; 44 extern const uint8_t ff_interleaved_ue_golomb_vlc_code[256]; 45 extern const int8_t ff_interleaved_se_golomb_vlc_code[256]; 46 extern const uint8_t ff_interleaved_dirac_golomb_vlc_code[256]; 47 48 /** 49 * Read an unsigned Exp-Golomb code in the range 0 to 8190. 50 * 51 * @returns the read value or a negative error code. 52 */ 53 static inline int get_ue_golomb(GetBitContext *gb) 54 { 55 unsigned int buf; 56 57 #if CACHED_BITSTREAM_READER 58 buf = show_bits_long(gb, 32); 59 60 if (buf >= (1 << 27)) { 61 buf >>= 32 - 9; 62 skip_bits_long(gb, ff_golomb_vlc_len[buf]); 63 64 return ff_ue_golomb_vlc_code[buf]; 65 } else { 66 int log = 2 * av_log2(buf) - 31; 67 68 skip_bits_long(gb, 32 - log); 69 if (log < 7) 70 return AVERROR_INVALIDDATA; 71 buf >>= log; 72 buf--; 73 74 return buf; 75 } 76 #else 77 OPEN_READER(re, gb); 78 UPDATE_CACHE(re, gb); 79 buf = GET_CACHE(re, gb); 80 81 if (buf >= (1 << 27)) { 82 buf >>= 32 - 9; 83 LAST_SKIP_BITS(re, gb, ff_golomb_vlc_len[buf]); 84 CLOSE_READER(re, gb); 85 86 return ff_ue_golomb_vlc_code[buf]; 87 } else { 88 int log = 2 * av_log2(buf) - 31; 89 LAST_SKIP_BITS(re, gb, 32 - log); 90 CLOSE_READER(re, gb); 91 if (log < 7) 92 return AVERROR_INVALIDDATA; 93 buf >>= log; 94 buf--; 95 96 return buf; 97 } 98 #endif 99 } 100 101 /** 102 * Read an unsigned Exp-Golomb code in the range 0 to UINT32_MAX-1. 103 */ 104 static inline unsigned get_ue_golomb_long(GetBitContext *gb) 105 { 106 unsigned buf, log; 107 108 buf = show_bits_long(gb, 32); 109 log = 31 - av_log2(buf); 110 skip_bits_long(gb, log); 111 112 return get_bits_long(gb, log + 1) - 1; 113 } 114 115 /** 116 * read unsigned exp golomb code, constraint to a max of 31. 117 * If the value encountered is not in 0..31, the return value 118 * is outside the range 0..30. 119 */ 120 static inline int get_ue_golomb_31(GetBitContext *gb) 121 { 122 unsigned int buf; 123 124 #if CACHED_BITSTREAM_READER 125 buf = show_bits_long(gb, 32); 126 127 buf >>= 32 - 9; 128 skip_bits_long(gb, ff_golomb_vlc_len[buf]); 129 #else 130 131 OPEN_READER(re, gb); 132 UPDATE_CACHE(re, gb); 133 buf = GET_CACHE(re, gb); 134 135 buf >>= 32 - 9; 136 LAST_SKIP_BITS(re, gb, ff_golomb_vlc_len[buf]); 137 CLOSE_READER(re, gb); 138 #endif 139 140 return ff_ue_golomb_vlc_code[buf]; 141 } 142 143 static inline unsigned get_interleaved_ue_golomb(GetBitContext *gb) 144 { 145 uint32_t buf; 146 147 #if CACHED_BITSTREAM_READER 148 buf = show_bits_long(gb, 32); 149 150 if (buf & 0xAA800000) { 151 buf >>= 32 - 8; 152 skip_bits_long(gb, ff_interleaved_golomb_vlc_len[buf]); 153 154 return ff_interleaved_ue_golomb_vlc_code[buf]; 155 } else { 156 unsigned ret = 1; 157 158 do { 159 buf >>= 32 - 8; 160 skip_bits_long(gb, FFMIN(ff_interleaved_golomb_vlc_len[buf], 8)); 161 162 if (ff_interleaved_golomb_vlc_len[buf] != 9) { 163 ret <<= (ff_interleaved_golomb_vlc_len[buf] - 1) >> 1; 164 ret |= ff_interleaved_dirac_golomb_vlc_code[buf]; 165 break; 166 } 167 ret = (ret << 4) | ff_interleaved_dirac_golomb_vlc_code[buf]; 168 buf = show_bits_long(gb, 32); 169 } while (get_bits_left(gb) > 0); 170 171 return ret - 1; 172 } 173 #else 174 OPEN_READER(re, gb); 175 UPDATE_CACHE(re, gb); 176 buf = GET_CACHE(re, gb); 177 178 if (buf & 0xAA800000) { 179 buf >>= 32 - 8; 180 LAST_SKIP_BITS(re, gb, ff_interleaved_golomb_vlc_len[buf]); 181 CLOSE_READER(re, gb); 182 183 return ff_interleaved_ue_golomb_vlc_code[buf]; 184 } else { 185 unsigned ret = 1; 186 187 do { 188 buf >>= 32 - 8; 189 LAST_SKIP_BITS(re, gb, 190 FFMIN(ff_interleaved_golomb_vlc_len[buf], 8)); 191 192 if (ff_interleaved_golomb_vlc_len[buf] != 9) { 193 ret <<= (ff_interleaved_golomb_vlc_len[buf] - 1) >> 1; 194 ret |= ff_interleaved_dirac_golomb_vlc_code[buf]; 195 break; 196 } 197 ret = (ret << 4) | ff_interleaved_dirac_golomb_vlc_code[buf]; 198 UPDATE_CACHE(re, gb); 199 buf = GET_CACHE(re, gb); 200 } while (ret<0x8000000U && BITS_AVAILABLE(re, gb)); 201 202 CLOSE_READER(re, gb); 203 return ret - 1; 204 } 205 #endif 206 } 207 208 /** 209 * read unsigned truncated exp golomb code. 210 */ 211 static inline int get_te0_golomb(GetBitContext *gb, int range) 212 { 213 av_assert2(range >= 1); 214 215 if (range == 1) 216 return 0; 217 else if (range == 2) 218 return get_bits1(gb) ^ 1; 219 else 220 return get_ue_golomb(gb); 221 } 222 223 /** 224 * read unsigned truncated exp golomb code. 225 */ 226 static inline int get_te_golomb(GetBitContext *gb, int range) 227 { 228 av_assert2(range >= 1); 229 230 if (range == 2) 231 return get_bits1(gb) ^ 1; 232 else 233 return get_ue_golomb(gb); 234 } 235 236 /** 237 * read signed exp golomb code. 238 */ 239 static inline int get_se_golomb(GetBitContext *gb) 240 { 241 unsigned int buf; 242 243 #if CACHED_BITSTREAM_READER 244 buf = show_bits_long(gb, 32); 245 246 if (buf >= (1 << 27)) { 247 buf >>= 32 - 9; 248 skip_bits_long(gb, ff_golomb_vlc_len[buf]); 249 250 return ff_se_golomb_vlc_code[buf]; 251 } else { 252 int log = 2 * av_log2(buf) - 31; 253 buf >>= log; 254 255 skip_bits_long(gb, 32 - log); 256 257 if (buf & 1) 258 buf = -(buf >> 1); 259 else 260 buf = (buf >> 1); 261 262 return buf; 263 } 264 #else 265 OPEN_READER(re, gb); 266 UPDATE_CACHE(re, gb); 267 buf = GET_CACHE(re, gb); 268 269 if (buf >= (1 << 27)) { 270 buf >>= 32 - 9; 271 LAST_SKIP_BITS(re, gb, ff_golomb_vlc_len[buf]); 272 CLOSE_READER(re, gb); 273 274 return ff_se_golomb_vlc_code[buf]; 275 } else { 276 int log = av_log2(buf), sign; 277 LAST_SKIP_BITS(re, gb, 31 - log); 278 UPDATE_CACHE(re, gb); 279 buf = GET_CACHE(re, gb); 280 281 buf >>= log; 282 283 LAST_SKIP_BITS(re, gb, 32 - log); 284 CLOSE_READER(re, gb); 285 286 sign = -(buf & 1); 287 buf = ((buf >> 1) ^ sign) - sign; 288 289 return buf; 290 } 291 #endif 292 } 293 294 static inline int get_se_golomb_long(GetBitContext *gb) 295 { 296 unsigned int buf = get_ue_golomb_long(gb); 297 int sign = (buf & 1) - 1; 298 return ((buf >> 1) ^ sign) + 1; 299 } 300 301 static inline int get_interleaved_se_golomb(GetBitContext *gb) 302 { 303 unsigned int buf; 304 305 #if CACHED_BITSTREAM_READER 306 buf = show_bits_long(gb, 32); 307 308 if (buf & 0xAA800000) { 309 buf >>= 32 - 8; 310 skip_bits_long(gb, ff_interleaved_golomb_vlc_len[buf]); 311 312 return ff_interleaved_se_golomb_vlc_code[buf]; 313 } else { 314 int log; 315 skip_bits(gb, 8); 316 buf |= 1 | show_bits(gb, 24); 317 318 if ((buf & 0xAAAAAAAA) == 0) 319 return INVALID_VLC; 320 321 for (log = 31; (buf & 0x80000000) == 0; log--) 322 buf = (buf << 2) - ((buf << log) >> (log - 1)) + (buf >> 30); 323 324 skip_bits_long(gb, 63 - 2 * log - 8); 325 326 return (signed) (((((buf << log) >> log) - 1) ^ -(buf & 0x1)) + 1) >> 1; 327 } 328 #else 329 OPEN_READER(re, gb); 330 UPDATE_CACHE(re, gb); 331 buf = GET_CACHE(re, gb); 332 333 if (buf & 0xAA800000) { 334 buf >>= 32 - 8; 335 LAST_SKIP_BITS(re, gb, ff_interleaved_golomb_vlc_len[buf]); 336 CLOSE_READER(re, gb); 337 338 return ff_interleaved_se_golomb_vlc_code[buf]; 339 } else { 340 int log; 341 LAST_SKIP_BITS(re, gb, 8); 342 UPDATE_CACHE(re, gb); 343 buf |= 1 | (GET_CACHE(re, gb) >> 8); 344 345 if ((buf & 0xAAAAAAAA) == 0) 346 return INVALID_VLC; 347 348 for (log = 31; (buf & 0x80000000) == 0; log--) 349 buf = (buf << 2) - ((buf << log) >> (log - 1)) + (buf >> 30); 350 351 LAST_SKIP_BITS(re, gb, 63 - 2 * log - 8); 352 CLOSE_READER(re, gb); 353 354 return (signed) (((((buf << log) >> log) - 1) ^ -(buf & 0x1)) + 1) >> 1; 355 } 356 #endif 357 } 358 359 static inline int dirac_get_se_golomb(GetBitContext *gb) 360 { 361 uint32_t ret = get_interleaved_ue_golomb(gb); 362 363 if (ret) { 364 int sign = -get_bits1(gb); 365 ret = (ret ^ sign) - sign; 366 } 367 368 return ret; 369 } 370 371 /** 372 * read unsigned golomb rice code (ffv1). 373 */ 374 static inline int get_ur_golomb(GetBitContext *gb, int k, int limit, 375 int esc_len) 376 { 377 unsigned int buf; 378 int log; 379 380 #if CACHED_BITSTREAM_READER 381 buf = show_bits_long(gb, 32); 382 383 log = av_log2(buf); 384 385 if (log > 31 - limit) { 386 buf >>= log - k; 387 buf += (30 - log) << k; 388 skip_bits_long(gb, 32 + k - log); 389 390 return buf; 391 } else { 392 skip_bits_long(gb, limit); 393 buf = get_bits_long(gb, esc_len); 394 395 return buf + limit - 1; 396 } 397 #else 398 OPEN_READER(re, gb); 399 UPDATE_CACHE(re, gb); 400 buf = GET_CACHE(re, gb); 401 402 log = av_log2(buf); 403 404 if (log > 31 - limit) { 405 av_assert2(log >= k); 406 buf >>= log - k; 407 buf += (30U - log) << k; 408 LAST_SKIP_BITS(re, gb, 32 + k - log); 409 CLOSE_READER(re, gb); 410 411 return buf; 412 } else { 413 LAST_SKIP_BITS(re, gb, limit); 414 UPDATE_CACHE(re, gb); 415 416 buf = SHOW_UBITS(re, gb, esc_len); 417 418 LAST_SKIP_BITS(re, gb, esc_len); 419 CLOSE_READER(re, gb); 420 421 return buf + limit - 1; 422 } 423 #endif 424 } 425 426 /** 427 * read unsigned golomb rice code (jpegls). 428 * 429 * @returns -1 on error 430 */ 431 static inline int get_ur_golomb_jpegls(GetBitContext *gb, int k, int limit, 432 int esc_len) 433 { 434 unsigned int buf; 435 int log; 436 437 #if CACHED_BITSTREAM_READER 438 buf = show_bits_long(gb, 32); 439 440 log = av_log2(buf); 441 442 if (log - k >= 1 && 32 - log < limit) { 443 buf >>= log - k; 444 buf += (30 - log) << k; 445 skip_bits_long(gb, 32 + k - log); 446 447 return buf; 448 } else { 449 int i; 450 for (i = 0; 451 i < limit && get_bits1(gb) == 0 && get_bits_left(gb) > 0; 452 i++); 453 454 if (i < limit - 1) { 455 buf = get_bits_long(gb, k); 456 457 return buf + (i << k); 458 } else if (i == limit - 1) { 459 buf = get_bits_long(gb, esc_len); 460 461 return buf + 1; 462 } else 463 return -1; 464 } 465 #else 466 OPEN_READER(re, gb); 467 UPDATE_CACHE(re, gb); 468 buf = GET_CACHE(re, gb); 469 470 log = av_log2(buf); 471 472 av_assert2(k <= 31); 473 474 if (log - k >= 32 - MIN_CACHE_BITS + (MIN_CACHE_BITS == 32) && 475 32 - log < limit) { 476 buf >>= log - k; 477 buf += (30U - log) << k; 478 LAST_SKIP_BITS(re, gb, 32 + k - log); 479 CLOSE_READER(re, gb); 480 481 return buf; 482 } else { 483 int i; 484 for (i = 0; i + MIN_CACHE_BITS <= limit && SHOW_UBITS(re, gb, MIN_CACHE_BITS) == 0; i += MIN_CACHE_BITS) { 485 if (gb->size_in_bits <= re_index) { 486 CLOSE_READER(re, gb); 487 return -1; 488 } 489 LAST_SKIP_BITS(re, gb, MIN_CACHE_BITS); 490 UPDATE_CACHE(re, gb); 491 } 492 for (; i < limit && SHOW_UBITS(re, gb, 1) == 0; i++) { 493 SKIP_BITS(re, gb, 1); 494 } 495 LAST_SKIP_BITS(re, gb, 1); 496 UPDATE_CACHE(re, gb); 497 498 if (i < limit - 1) { 499 if (k) { 500 if (k > MIN_CACHE_BITS - 1) { 501 buf = SHOW_UBITS(re, gb, 16) << (k-16); 502 LAST_SKIP_BITS(re, gb, 16); 503 UPDATE_CACHE(re, gb); 504 buf |= SHOW_UBITS(re, gb, k-16); 505 LAST_SKIP_BITS(re, gb, k-16); 506 } else { 507 buf = SHOW_UBITS(re, gb, k); 508 LAST_SKIP_BITS(re, gb, k); 509 } 510 } else { 511 buf = 0; 512 } 513 514 buf += ((SUINT)i << k); 515 } else if (i == limit - 1) { 516 buf = SHOW_UBITS(re, gb, esc_len); 517 LAST_SKIP_BITS(re, gb, esc_len); 518 519 buf ++; 520 } else { 521 buf = -1; 522 } 523 CLOSE_READER(re, gb); 524 return buf; 525 } 526 #endif 527 } 528 529 /** 530 * read signed golomb rice code (ffv1). 531 */ 532 static inline int get_sr_golomb(GetBitContext *gb, int k, int limit, 533 int esc_len) 534 { 535 unsigned v = get_ur_golomb(gb, k, limit, esc_len); 536 return (v >> 1) ^ -(v & 1); 537 } 538 539 /** 540 * read signed golomb rice code (flac). 541 * 542 * @returns INT_MIN on error 543 */ 544 static inline int get_sr_golomb_flac(GetBitContext *gb, int k, int limit, 545 int esc_len) 546 { 547 unsigned v = get_ur_golomb_jpegls(gb, k, limit, esc_len); 548 return (v >> 1) ^ -(v & 1); 549 } 550 551 /** 552 * read unsigned golomb rice code (shorten). 553 */ 554 static inline unsigned int get_ur_golomb_shorten(GetBitContext *gb, int k) 555 { 556 return get_ur_golomb_jpegls(gb, k, INT_MAX, 0); 557 } 558 559 /** 560 * read signed golomb rice code (shorten). 561 */ 562 static inline int get_sr_golomb_shorten(GetBitContext *gb, int k) 563 { 564 int uvar = get_ur_golomb_jpegls(gb, k + 1, INT_MAX, 0); 565 return (uvar >> 1) ^ -(uvar & 1); 566 } 567 568 #ifdef TRACE 569 570 static inline int get_ue(GetBitContext *s, const char *file, const char *func, 571 int line) 572 { 573 int show = show_bits(s, 24); 574 int pos = get_bits_count(s); 575 int i = get_ue_golomb(s); 576 int len = get_bits_count(s) - pos; 577 int bits = show >> (24 - len); 578 579 av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d ue @%5d in %s %s:%d\n", 580 bits, len, i, pos, file, func, line); 581 582 return i; 583 } 584 585 static inline int get_se(GetBitContext *s, const char *file, const char *func, 586 int line) 587 { 588 int show = show_bits(s, 24); 589 int pos = get_bits_count(s); 590 int i = get_se_golomb(s); 591 int len = get_bits_count(s) - pos; 592 int bits = show >> (24 - len); 593 594 av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d se @%5d in %s %s:%d\n", 595 bits, len, i, pos, file, func, line); 596 597 return i; 598 } 599 600 static inline int get_te(GetBitContext *s, int r, char *file, const char *func, 601 int line) 602 { 603 int show = show_bits(s, 24); 604 int pos = get_bits_count(s); 605 int i = get_te0_golomb(s, r); 606 int len = get_bits_count(s) - pos; 607 int bits = show >> (24 - len); 608 609 av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d te @%5d in %s %s:%d\n", 610 bits, len, i, pos, file, func, line); 611 612 return i; 613 } 614 615 #define get_ue_golomb(a) get_ue(a, __FILE__, __func__, __LINE__) 616 #define get_se_golomb(a) get_se(a, __FILE__, __func__, __LINE__) 617 #define get_te_golomb(a, r) get_te(a, r, __FILE__, __func__, __LINE__) 618 #define get_te0_golomb(a, r) get_te(a, r, __FILE__, __func__, __LINE__) 619 620 #endif /* TRACE */ 621 #endif /* AVCODEC_GOLOMB_H */