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#include "put_bits.h" 37 38#define INVALID_VLC 0x80000000 39 40extern const uint8_t ff_golomb_vlc_len[512]; 41extern const uint8_t ff_ue_golomb_vlc_code[512]; 42extern const int8_t ff_se_golomb_vlc_code[512]; 43extern const uint8_t ff_ue_golomb_len[256]; 44 45extern const uint8_t ff_interleaved_golomb_vlc_len[256]; 46extern const uint8_t ff_interleaved_ue_golomb_vlc_code[256]; 47extern const int8_t ff_interleaved_se_golomb_vlc_code[256]; 48extern const uint8_t ff_interleaved_dirac_golomb_vlc_code[256]; 49 50/** 51 * read unsigned exp golomb code. 52 */ 53static inline int get_ue_golomb(GetBitContext *gb) 54{ 55 unsigned int buf; 56 57 OPEN_READER(re, gb); 58 UPDATE_CACHE(re, gb); 59 buf = GET_CACHE(re, gb); 60 61 if (buf >= (1 << 27)) { 62 buf >>= 32 - 9; 63 LAST_SKIP_BITS(re, gb, ff_golomb_vlc_len[buf]); 64 CLOSE_READER(re, gb); 65 66 return ff_ue_golomb_vlc_code[buf]; 67 } else { 68 int log = 2 * av_log2(buf) - 31; 69 LAST_SKIP_BITS(re, gb, 32 - log); 70 CLOSE_READER(re, gb); 71 if (CONFIG_FTRAPV && log < 0) { 72 av_log(0, AV_LOG_ERROR, "Invalid UE golomb code\n"); 73 return AVERROR_INVALIDDATA; 74 } 75 buf >>= log; 76 buf--; 77 78 return buf; 79 } 80} 81 82/** 83 * Read an unsigned Exp-Golomb code in the range 0 to UINT32_MAX-1. 84 */ 85static inline unsigned get_ue_golomb_long(GetBitContext *gb) 86{ 87 unsigned buf, log; 88 89 buf = show_bits_long(gb, 32); 90 log = 31 - av_log2(buf); 91 skip_bits_long(gb, log); 92 93 return get_bits_long(gb, log + 1) - 1; 94} 95 96/** 97 * read unsigned exp golomb code, constraint to a max of 31. 98 * the return value is undefined if the stored value exceeds 31. 99 */ 100static inline int get_ue_golomb_31(GetBitContext *gb) 101{ 102 unsigned int buf; 103 104 OPEN_READER(re, gb); 105 UPDATE_CACHE(re, gb); 106 buf = GET_CACHE(re, gb); 107 108 buf >>= 32 - 9; 109 LAST_SKIP_BITS(re, gb, ff_golomb_vlc_len[buf]); 110 CLOSE_READER(re, gb); 111 112 return ff_ue_golomb_vlc_code[buf]; 113} 114 115static inline unsigned svq3_get_ue_golomb(GetBitContext *gb) 116{ 117 uint32_t buf; 118 119 OPEN_READER(re, gb); 120 UPDATE_CACHE(re, gb); 121 buf = GET_CACHE(re, gb); 122 123 if (buf & 0xAA800000) { 124 buf >>= 32 - 8; 125 LAST_SKIP_BITS(re, gb, ff_interleaved_golomb_vlc_len[buf]); 126 CLOSE_READER(re, gb); 127 128 return ff_interleaved_ue_golomb_vlc_code[buf]; 129 } else { 130 unsigned ret = 1; 131 132 do { 133 buf >>= 32 - 8; 134 LAST_SKIP_BITS(re, gb, 135 FFMIN(ff_interleaved_golomb_vlc_len[buf], 8)); 136 137 if (ff_interleaved_golomb_vlc_len[buf] != 9) { 138 ret <<= (ff_interleaved_golomb_vlc_len[buf] - 1) >> 1; 139 ret |= ff_interleaved_dirac_golomb_vlc_code[buf]; 140 break; 141 } 142 ret = (ret << 4) | ff_interleaved_dirac_golomb_vlc_code[buf]; 143 UPDATE_CACHE(re, gb); 144 buf = GET_CACHE(re, gb); 145 } while (ret<0x8000000U && HAVE_BITS_REMAINING(re, gb)); 146 147 CLOSE_READER(re, gb); 148 return ret - 1; 149 } 150} 151 152/** 153 * read unsigned truncated exp golomb code. 154 */ 155static inline int get_te0_golomb(GetBitContext *gb, int range) 156{ 157 av_assert2(range >= 1); 158 159 if (range == 1) 160 return 0; 161 else if (range == 2) 162 return get_bits1(gb) ^ 1; 163 else 164 return get_ue_golomb(gb); 165} 166 167/** 168 * read unsigned truncated exp golomb code. 169 */ 170static inline int get_te_golomb(GetBitContext *gb, int range) 171{ 172 av_assert2(range >= 1); 173 174 if (range == 2) 175 return get_bits1(gb) ^ 1; 176 else 177 return get_ue_golomb(gb); 178} 179 180/** 181 * read signed exp golomb code. 182 */ 183static inline int get_se_golomb(GetBitContext *gb) 184{ 185 unsigned int buf; 186 187 OPEN_READER(re, gb); 188 UPDATE_CACHE(re, gb); 189 buf = GET_CACHE(re, gb); 190 191 if (buf >= (1 << 27)) { 192 buf >>= 32 - 9; 193 LAST_SKIP_BITS(re, gb, ff_golomb_vlc_len[buf]); 194 CLOSE_READER(re, gb); 195 196 return ff_se_golomb_vlc_code[buf]; 197 } else { 198 int log = av_log2(buf); 199 LAST_SKIP_BITS(re, gb, 31 - log); 200 UPDATE_CACHE(re, gb); 201 buf = GET_CACHE(re, gb); 202 203 buf >>= log; 204 205 LAST_SKIP_BITS(re, gb, 32 - log); 206 CLOSE_READER(re, gb); 207 208 if (buf & 1) 209 buf = -(buf >> 1); 210 else 211 buf = (buf >> 1); 212 213 return buf; 214 } 215} 216 217static inline int get_se_golomb_long(GetBitContext *gb) 218{ 219 unsigned int buf = get_ue_golomb_long(gb); 220 221 if (buf & 1) 222 buf = (buf + 1) >> 1; 223 else 224 buf = -(buf >> 1); 225 226 return buf; 227} 228 229static inline int svq3_get_se_golomb(GetBitContext *gb) 230{ 231 unsigned int buf; 232 233 OPEN_READER(re, gb); 234 UPDATE_CACHE(re, gb); 235 buf = GET_CACHE(re, gb); 236 237 if (buf & 0xAA800000) { 238 buf >>= 32 - 8; 239 LAST_SKIP_BITS(re, gb, ff_interleaved_golomb_vlc_len[buf]); 240 CLOSE_READER(re, gb); 241 242 return ff_interleaved_se_golomb_vlc_code[buf]; 243 } else { 244 int log; 245 LAST_SKIP_BITS(re, gb, 8); 246 UPDATE_CACHE(re, gb); 247 buf |= 1 | (GET_CACHE(re, gb) >> 8); 248 249 if ((buf & 0xAAAAAAAA) == 0) 250 return INVALID_VLC; 251 252 for (log = 31; (buf & 0x80000000) == 0; log--) 253 buf = (buf << 2) - ((buf << log) >> (log - 1)) + (buf >> 30); 254 255 LAST_SKIP_BITS(re, gb, 63 - 2 * log - 8); 256 CLOSE_READER(re, gb); 257 258 return (signed) (((((buf << log) >> log) - 1) ^ -(buf & 0x1)) + 1) >> 1; 259 } 260} 261 262static inline int dirac_get_se_golomb(GetBitContext *gb) 263{ 264 uint32_t ret = svq3_get_ue_golomb(gb); 265 266 if (ret) { 267 uint32_t buf; 268 OPEN_READER(re, gb); 269 UPDATE_CACHE(re, gb); 270 buf = SHOW_SBITS(re, gb, 1); 271 LAST_SKIP_BITS(re, gb, 1); 272 ret = (ret ^ buf) - buf; 273 CLOSE_READER(re, gb); 274 } 275 276 return ret; 277} 278 279/** 280 * read unsigned golomb rice code (ffv1). 281 */ 282static inline int get_ur_golomb(GetBitContext *gb, int k, int limit, 283 int esc_len) 284{ 285 unsigned int buf; 286 int log; 287 288 OPEN_READER(re, gb); 289 UPDATE_CACHE(re, gb); 290 buf = GET_CACHE(re, gb); 291 292 log = av_log2(buf); 293 294 if (log > 31 - limit) { 295 buf >>= log - k; 296 buf += (30 - log) << k; 297 LAST_SKIP_BITS(re, gb, 32 + k - log); 298 CLOSE_READER(re, gb); 299 300 return buf; 301 } else { 302 LAST_SKIP_BITS(re, gb, limit); 303 UPDATE_CACHE(re, gb); 304 305 buf = SHOW_UBITS(re, gb, esc_len); 306 307 LAST_SKIP_BITS(re, gb, esc_len); 308 CLOSE_READER(re, gb); 309 310 return buf + limit - 1; 311 } 312} 313 314/** 315 * read unsigned golomb rice code (jpegls). 316 */ 317static inline int get_ur_golomb_jpegls(GetBitContext *gb, int k, int limit, 318 int esc_len) 319{ 320 unsigned int buf; 321 int log; 322 323 OPEN_READER(re, gb); 324 UPDATE_CACHE(re, gb); 325 buf = GET_CACHE(re, gb); 326 327 log = av_log2(buf); 328 329 if (log - k >= 32 - MIN_CACHE_BITS + (MIN_CACHE_BITS == 32) && 330 32 - log < limit) { 331 buf >>= log - k; 332 buf += (30 - log) << k; 333 LAST_SKIP_BITS(re, gb, 32 + k - log); 334 CLOSE_READER(re, gb); 335 336 return buf; 337 } else { 338 int i; 339 for (i = 0; i < limit && SHOW_UBITS(re, gb, 1) == 0; i++) { 340 if (gb->size_in_bits <= re_index) 341 return -1; 342 LAST_SKIP_BITS(re, gb, 1); 343 UPDATE_CACHE(re, gb); 344 } 345 SKIP_BITS(re, gb, 1); 346 347 if (i < limit - 1) { 348 if (k) { 349 buf = SHOW_UBITS(re, gb, k); 350 LAST_SKIP_BITS(re, gb, k); 351 } else { 352 buf = 0; 353 } 354 355 CLOSE_READER(re, gb); 356 return buf + (i << k); 357 } else if (i == limit - 1) { 358 buf = SHOW_UBITS(re, gb, esc_len); 359 LAST_SKIP_BITS(re, gb, esc_len); 360 CLOSE_READER(re, gb); 361 362 return buf + 1; 363 } else 364 return -1; 365 } 366} 367 368/** 369 * read signed golomb rice code (ffv1). 370 */ 371static inline int get_sr_golomb(GetBitContext *gb, int k, int limit, 372 int esc_len) 373{ 374 int v = get_ur_golomb(gb, k, limit, esc_len); 375 376 v++; 377 if (v & 1) 378 return v >> 1; 379 else 380 return -(v >> 1); 381 382// return (v>>1) ^ -(v&1); 383} 384 385/** 386 * read signed golomb rice code (flac). 387 */ 388static inline int get_sr_golomb_flac(GetBitContext *gb, int k, int limit, 389 int esc_len) 390{ 391 int v = get_ur_golomb_jpegls(gb, k, limit, esc_len); 392 return (v >> 1) ^ -(v & 1); 393} 394 395/** 396 * read unsigned golomb rice code (shorten). 397 */ 398static inline unsigned int get_ur_golomb_shorten(GetBitContext *gb, int k) 399{ 400 return get_ur_golomb_jpegls(gb, k, INT_MAX, 0); 401} 402 403/** 404 * read signed golomb rice code (shorten). 405 */ 406static inline int get_sr_golomb_shorten(GetBitContext *gb, int k) 407{ 408 int uvar = get_ur_golomb_jpegls(gb, k + 1, INT_MAX, 0); 409 if (uvar & 1) 410 return ~(uvar >> 1); 411 else 412 return uvar >> 1; 413} 414 415#ifdef TRACE 416 417static inline int get_ue(GetBitContext *s, const char *file, const char *func, 418 int line) 419{ 420 int show = show_bits(s, 24); 421 int pos = get_bits_count(s); 422 int i = get_ue_golomb(s); 423 int len = get_bits_count(s) - pos; 424 int bits = show >> (24 - len); 425 426 print_bin(bits, len); 427 428 av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d ue @%5d in %s %s:%d\n", 429 bits, len, i, pos, file, func, line); 430 431 return i; 432} 433 434static inline int get_se(GetBitContext *s, const char *file, const char *func, 435 int line) 436{ 437 int show = show_bits(s, 24); 438 int pos = get_bits_count(s); 439 int i = get_se_golomb(s); 440 int len = get_bits_count(s) - pos; 441 int bits = show >> (24 - len); 442 443 print_bin(bits, len); 444 445 av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d se @%5d in %s %s:%d\n", 446 bits, len, i, pos, file, func, line); 447 448 return i; 449} 450 451static inline int get_te(GetBitContext *s, int r, char *file, const char *func, 452 int line) 453{ 454 int show = show_bits(s, 24); 455 int pos = get_bits_count(s); 456 int i = get_te0_golomb(s, r); 457 int len = get_bits_count(s) - pos; 458 int bits = show >> (24 - len); 459 460 print_bin(bits, len); 461 462 av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d te @%5d in %s %s:%d\n", 463 bits, len, i, pos, file, func, line); 464 465 return i; 466} 467 468#define get_ue_golomb(a) get_ue(a, __FILE__, __PRETTY_FUNCTION__, __LINE__) 469#define get_se_golomb(a) get_se(a, __FILE__, __PRETTY_FUNCTION__, __LINE__) 470#define get_te_golomb(a, r) get_te(a, r, __FILE__, __PRETTY_FUNCTION__, __LINE__) 471#define get_te0_golomb(a, r) get_te(a, r, __FILE__, __PRETTY_FUNCTION__, __LINE__) 472 473#endif /* TRACE */ 474 475/** 476 * write unsigned exp golomb code. 477 */ 478static inline void set_ue_golomb(PutBitContext *pb, int i) 479{ 480 av_assert2(i >= 0); 481 482#if 0 483 if (i = 0) { 484 put_bits(pb, 1, 1); 485 return; 486 } 487#endif 488 if (i < 256) 489 put_bits(pb, ff_ue_golomb_len[i], i + 1); 490 else { 491 int e = av_log2(i + 1); 492 put_bits(pb, 2 * e + 1, i + 1); 493 } 494} 495 496/** 497 * write truncated unsigned exp golomb code. 498 */ 499static inline void set_te_golomb(PutBitContext *pb, int i, int range) 500{ 501 av_assert2(range >= 1); 502 av_assert2(i <= range); 503 504 if (range == 2) 505 put_bits(pb, 1, i ^ 1); 506 else 507 set_ue_golomb(pb, i); 508} 509 510/** 511 * write signed exp golomb code. 16 bits at most. 512 */ 513static inline void set_se_golomb(PutBitContext *pb, int i) 514{ 515#if 0 516 if (i <= 0) 517 i = -2 * i; 518 else 519 i = 2 * i - 1; 520#elif 1 521 i = 2 * i - 1; 522 if (i < 0) 523 i ^= -1; //FIXME check if gcc does the right thing 524#else 525 i = 2 * i - 1; 526 i ^= (i >> 31); 527#endif 528 set_ue_golomb(pb, i); 529} 530 531/** 532 * write unsigned golomb rice code (ffv1). 533 */ 534static inline void set_ur_golomb(PutBitContext *pb, int i, int k, int limit, 535 int esc_len) 536{ 537 int e; 538 539 av_assert2(i >= 0); 540 541 e = i >> k; 542 if (e < limit) 543 put_bits(pb, e + k + 1, (1 << k) + (i & ((1 << k) - 1))); 544 else 545 put_bits(pb, limit + esc_len, i - limit + 1); 546} 547 548/** 549 * write unsigned golomb rice code (jpegls). 550 */ 551static inline void set_ur_golomb_jpegls(PutBitContext *pb, int i, int k, 552 int limit, int esc_len) 553{ 554 int e; 555 556 av_assert2(i >= 0); 557 558 e = (i >> k) + 1; 559 if (e < limit) { 560 while (e > 31) { 561 put_bits(pb, 31, 0); 562 e -= 31; 563 } 564 put_bits(pb, e, 1); 565 if (k) 566 put_sbits(pb, k, i); 567 } else { 568 while (limit > 31) { 569 put_bits(pb, 31, 0); 570 limit -= 31; 571 } 572 put_bits(pb, limit, 1); 573 put_bits(pb, esc_len, i - 1); 574 } 575} 576 577/** 578 * write signed golomb rice code (ffv1). 579 */ 580static inline void set_sr_golomb(PutBitContext *pb, int i, int k, int limit, 581 int esc_len) 582{ 583 int v; 584 585 v = -2 * i - 1; 586 v ^= (v >> 31); 587 588 set_ur_golomb(pb, v, k, limit, esc_len); 589} 590 591/** 592 * write signed golomb rice code (flac). 593 */ 594static inline void set_sr_golomb_flac(PutBitContext *pb, int i, int k, 595 int limit, int esc_len) 596{ 597 int v; 598 599 v = -2 * i - 1; 600 v ^= (v >> 31); 601 602 set_ur_golomb_jpegls(pb, v, k, limit, esc_len); 603} 604 605#endif /* AVCODEC_GOLOMB_H */ 606