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