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