libavcodec/golomb.h

   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 */