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 39extern const uint8_t ff_golomb_vlc_len[512]; 40extern const uint8_t ff_ue_golomb_vlc_code[512]; 41extern const int8_t ff_se_golomb_vlc_code[512]; 42 43extern const uint8_t ff_interleaved_golomb_vlc_len[256]; 44extern const uint8_t ff_interleaved_ue_golomb_vlc_code[256]; 45extern const int8_t ff_interleaved_se_golomb_vlc_code[256]; 46extern 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 */ 53static 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 */ 104static 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 */ 120static 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 143static 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 */ 211static 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 */ 226static 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 */ 239static 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 294static 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 301static 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 359static 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 */ 374static 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 buf >>= log - k; 406 buf += (30U - log) << k; 407 LAST_SKIP_BITS(re, gb, 32 + k - log); 408 CLOSE_READER(re, gb); 409 410 return buf; 411 } else { 412 LAST_SKIP_BITS(re, gb, limit); 413 UPDATE_CACHE(re, gb); 414 415 buf = SHOW_UBITS(re, gb, esc_len); 416 417 LAST_SKIP_BITS(re, gb, esc_len); 418 CLOSE_READER(re, gb); 419 420 return buf + limit - 1; 421 } 422#endif 423} 424 425/** 426 * read unsigned golomb rice code (jpegls). 427 */ 428static inline int get_ur_golomb_jpegls(GetBitContext *gb, int k, int limit, 429 int esc_len) 430{ 431 unsigned int buf; 432 int log; 433 434#if CACHED_BITSTREAM_READER 435 buf = show_bits_long(gb, 32); 436 437 log = av_log2(buf); 438 439 if (log - k >= 1 && 32 - log < limit) { 440 buf >>= log - k; 441 buf += (30 - log) << k; 442 skip_bits_long(gb, 32 + k - log); 443 444 return buf; 445 } else { 446 int i; 447 for (i = 0; 448 i < limit && get_bits1(gb) == 0 && get_bits_left(gb) > 0; 449 i++); 450 451 if (i < limit - 1) { 452 buf = get_bits_long(gb, k); 453 454 return buf + (i << k); 455 } else if (i == limit - 1) { 456 buf = get_bits_long(gb, esc_len); 457 458 return buf + 1; 459 } else 460 return -1; 461 } 462#else 463 OPEN_READER(re, gb); 464 UPDATE_CACHE(re, gb); 465 buf = GET_CACHE(re, gb); 466 467 log = av_log2(buf); 468 469 av_assert2(k <= 31); 470 471 if (log - k >= 32 - MIN_CACHE_BITS + (MIN_CACHE_BITS == 32) && 472 32 - log < limit) { 473 buf >>= log - k; 474 buf += (30U - log) << k; 475 LAST_SKIP_BITS(re, gb, 32 + k - log); 476 CLOSE_READER(re, gb); 477 478 return buf; 479 } else { 480 int i; 481 for (i = 0; i + MIN_CACHE_BITS <= limit && SHOW_UBITS(re, gb, MIN_CACHE_BITS) == 0; i += MIN_CACHE_BITS) { 482 if (gb->size_in_bits <= re_index) { 483 CLOSE_READER(re, gb); 484 return -1; 485 } 486 LAST_SKIP_BITS(re, gb, MIN_CACHE_BITS); 487 UPDATE_CACHE(re, gb); 488 } 489 for (; i < limit && SHOW_UBITS(re, gb, 1) == 0; i++) { 490 SKIP_BITS(re, gb, 1); 491 } 492 LAST_SKIP_BITS(re, gb, 1); 493 UPDATE_CACHE(re, gb); 494 495 if (i < limit - 1) { 496 if (k) { 497 if (k > MIN_CACHE_BITS - 1) { 498 buf = SHOW_UBITS(re, gb, 16) << (k-16); 499 LAST_SKIP_BITS(re, gb, 16); 500 UPDATE_CACHE(re, gb); 501 buf |= SHOW_UBITS(re, gb, k-16); 502 LAST_SKIP_BITS(re, gb, k-16); 503 } else { 504 buf = SHOW_UBITS(re, gb, k); 505 LAST_SKIP_BITS(re, gb, k); 506 } 507 } else { 508 buf = 0; 509 } 510 511 buf += ((SUINT)i << k); 512 } else if (i == limit - 1) { 513 buf = SHOW_UBITS(re, gb, esc_len); 514 LAST_SKIP_BITS(re, gb, esc_len); 515 516 buf ++; 517 } else { 518 buf = -1; 519 } 520 CLOSE_READER(re, gb); 521 return buf; 522 } 523#endif 524} 525 526/** 527 * read signed golomb rice code (ffv1). 528 */ 529static inline int get_sr_golomb(GetBitContext *gb, int k, int limit, 530 int esc_len) 531{ 532 unsigned v = get_ur_golomb(gb, k, limit, esc_len); 533 return (v >> 1) ^ -(v & 1); 534} 535 536/** 537 * read signed golomb rice code (flac). 538 */ 539static inline int get_sr_golomb_flac(GetBitContext *gb, int k, int limit, 540 int esc_len) 541{ 542 unsigned v = get_ur_golomb_jpegls(gb, k, limit, esc_len); 543 return (v >> 1) ^ -(v & 1); 544} 545 546/** 547 * read unsigned golomb rice code (shorten). 548 */ 549static inline unsigned int get_ur_golomb_shorten(GetBitContext *gb, int k) 550{ 551 return get_ur_golomb_jpegls(gb, k, INT_MAX, 0); 552} 553 554/** 555 * read signed golomb rice code (shorten). 556 */ 557static inline int get_sr_golomb_shorten(GetBitContext *gb, int k) 558{ 559 int uvar = get_ur_golomb_jpegls(gb, k + 1, INT_MAX, 0); 560 return (uvar >> 1) ^ -(uvar & 1); 561} 562 563#ifdef TRACE 564 565static inline int get_ue(GetBitContext *s, const char *file, const char *func, 566 int line) 567{ 568 int show = show_bits(s, 24); 569 int pos = get_bits_count(s); 570 int i = get_ue_golomb(s); 571 int len = get_bits_count(s) - pos; 572 int bits = show >> (24 - len); 573 574 av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d ue @%5d in %s %s:%d\n", 575 bits, len, i, pos, file, func, line); 576 577 return i; 578} 579 580static inline int get_se(GetBitContext *s, const char *file, const char *func, 581 int line) 582{ 583 int show = show_bits(s, 24); 584 int pos = get_bits_count(s); 585 int i = get_se_golomb(s); 586 int len = get_bits_count(s) - pos; 587 int bits = show >> (24 - len); 588 589 av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d se @%5d in %s %s:%d\n", 590 bits, len, i, pos, file, func, line); 591 592 return i; 593} 594 595static inline int get_te(GetBitContext *s, int r, char *file, const char *func, 596 int line) 597{ 598 int show = show_bits(s, 24); 599 int pos = get_bits_count(s); 600 int i = get_te0_golomb(s, r); 601 int len = get_bits_count(s) - pos; 602 int bits = show >> (24 - len); 603 604 av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d te @%5d in %s %s:%d\n", 605 bits, len, i, pos, file, func, line); 606 607 return i; 608} 609 610#define get_ue_golomb(a) get_ue(a, __FILE__, __func__, __LINE__) 611#define get_se_golomb(a) get_se(a, __FILE__, __func__, __LINE__) 612#define get_te_golomb(a, r) get_te(a, r, __FILE__, __func__, __LINE__) 613#define get_te0_golomb(a, r) get_te(a, r, __FILE__, __func__, __LINE__) 614 615#endif /* TRACE */ 616#endif /* AVCODEC_GOLOMB_H */ 617