vp8/common/x86/boolcoder.cxx

   1 /*
   2  *  Copyright (c) 2010 The VP8 project authors. All Rights Reserved.
   3  *
   4  *  Use of this source code is governed by a BSD-style license and patent
   5  *  grant that can be found in the LICENSE file in the root of the source
   6  *  tree. All contributing project authors may be found in the AUTHORS
   7  *  file in the root of the source tree.
   8  */
   9
  10
  11
  12 /* Arithmetic bool coder with largish probability range.
  13    Timothy S Murphy  6 August 2004 */
  14
  15 #include <assert.h>
  16 #include <math.h>
  17
  18 #include "bool_coder.h"
  19
  20 #if tim_vp8
  21     extern "C" {
  22 #       include "VP8cx/treewriter.h"
  23     }
  24 #endif
  25
  26 int_types::~int_types() {}
  27
  28 void bool_coder_spec::check_prec() const {
  29     assert( w  &&  (r==Up || w > 1)  &&  w < 24  &&  (ebias || w < 17));
  30 }
  31
  32 bool bool_coder_spec::float_init( uint Ebits, uint Mbits) {
  33     uint b = (ebits = Ebits) + (mbits = Mbits);
  34     if( b) {
  35         assert( ebits < 6  &&  w + mbits < 31);
  36         assert( ebits + mbits  <  sizeof(Index) * 8);
  37         ebias = (1 << ebits) + 1 + mbits;
  38         mmask = (1 << mbits) - 1;
  39         max_index = ( ( half_index = 1 << b ) << 1) - 1;
  40     } else {
  41         ebias = 0;
  42         max_index = 255;
  43         half_index = 128;
  44     }
  45     check_prec();
  46     return b? 1:0;
  47 }
  48
  49 void bool_coder_spec::cost_init()
  50 {
  51     static cdouble c = -(1 << 20)/log( 2.);
  52
  53     FILE *f = fopen( "costs.txt", "w");
  54     assert( f);
  55
  56     assert( sizeof(int) >= 4);  /* for C interface */
  57     assert( max_index <= 255);   /* size of Ctbl */
  58     uint i = 0;  do {
  59         cdouble p = ( *this)( (Index) i);
  60         Ctbl[i] = (uint32) ( log( p) * c);
  61         fprintf(
  62             f, "cost( %d -> %10.7f) = %10d = %12.5f bits\n",
  63             i, p, Ctbl[i], (double) Ctbl[i] / (1<<20)
  64         );
  65     } while( ++i <= max_index);
  66     fclose( f);
  67 }
  68
  69 bool_coder_spec_explicit_table::bool_coder_spec_explicit_table(
  70     cuint16 tbl[256], Rounding rr, uint prec
  71 )
  72   : bool_coder_spec( prec, rr)
  73 {
  74     check_prec();
  75     uint i = 0;
  76     if( tbl)
  77         do { Ptbl[i] = tbl[i];}  while( ++i < 256);
  78     else
  79         do { Ptbl[i] = i << 8;}  while( ++i < 256);
  80     cost_init();
  81 }
  82
  83
  84 bool_coder_spec_exponential_table::bool_coder_spec_exponential_table(
  85     uint x, Rounding rr, uint prec
  86 )
  87   : bool_coder_spec( prec, rr)
  88 {
  89     assert( x > 1  &&  x <= 16);
  90     check_prec();
  91     Ptbl[128] = 32768u;
  92     Ptbl[0] = (uint16) pow( 2., 16. - x);
  93     --x;
  94     int i=1;  do {
  95         cdouble d = pow( .5, 1. + (1. - i/128.)*x) * 65536.;
  96         uint16 v = (uint16) d;
  97         if( v < i)
  98             v = i;
  99         Ptbl[256-i] = (uint16) ( 65536U - (Ptbl[i] = v));
 100     } while( ++i < 128);
 101     cost_init();
 102 }
 103
 104 bool_coder_spec::bool_coder_spec( FILE *fp) {
 105     fscanf( fp, "%d", &w);
 106     int v;
 107     fscanf( fp, "%d", &v);
 108     assert( 0 <= v  &&  v <= 2);
 109     r = (Rounding) v;
 110     fscanf( fp, "%d", &ebits);
 111     fscanf( fp, "%d", &mbits);
 112     if( float_init( ebits, mbits))
 113         return;
 114     int i=0;  do {
 115         uint v;
 116         fscanf( fp, "%d", &v);
 117         assert( 0 <=v  &&  v <= 65535U);
 118         Ptbl[i] = v;
 119     } while( ++i < 256);
 120     cost_init();
 121 }
 122
 123 void bool_coder_spec::dump( FILE *fp) const {
 124     fprintf( fp, "%d %d %d %d\n", w, (int) r, ebits, mbits);
 125     if( ebits  ||  mbits)
 126         return;
 127     int i=0;  do { fprintf( fp, "%d\n", Ptbl[i]);}  while( ++i < 256);
 128 }
 129
 130 vp8bc_index_t bool_coder_spec::operator()( double p) const
 131 {
 132     if( p <= 0.)
 133         return 0;
 134     if( p >= 1.)
 135         return max_index;
 136     if( ebias) {
 137         if( p > .5)
 138             return max_index - ( *this)( 1. - p);
 139         int e;
 140         uint m = (uint) ldexp( frexp( p, &e), mbits + 2);
 141         uint x = 1 << (mbits + 1);
 142         assert( x <= m  &&  m < x<<1);
 143         if( (m = (m >> 1) + (m & 1)) >= x) {
 144             m = x >> 1;
 145             ++e;
 146         }
 147         int y = 1 << ebits;
 148         if( (e += y) >= y)
 149             return half_index - 1;
 150         if( e < 0)
 151             return 0;
 152         return (Index) ( (e << mbits) + (m & mmask));
 153     }
 154
 155     cuint16 v = (uint16) (p * 65536.);
 156     int i = 128;
 157     int j = 128;
 158     uint16 w;
 159     while( w = Ptbl[i], j >>= 1) {
 160         if( w < v)
 161             i += j;
 162         else if( w == v)
 163             return (uchar) i;
 164         else
 165             i -= j;
 166     }
 167     if( w > v) {
 168         cuint16 x = Ptbl[i-1];
 169         if( v <= x  ||  w - v > v - x)
 170             --i;
 171     } else if( w < v  &&  i < 255) {
 172         cuint16 x = Ptbl[i+1];
 173         if( x <= v  ||  x - v < v - w)
 174             ++i;
 175     }
 176     return (Index) i;
 177 }
 178
 179 double bool_coder_spec::operator()( Index i) const {
 180     if( !ebias)
 181         return Ptbl[i]/65536.;
 182     if( i >= half_index)
 183         return 1. - ( *this)( (Index) (max_index - i));
 184     return ldexp( (double)mantissa( i), - (int) exponent( i));
 185 }
 186
 187
 188
 189 void bool_writer::carry() {
 190     uchar *p = B;
 191     assert( p > Bstart);
 192     while( *--p == 255) { assert( p > Bstart);  *p = 0;}
 193     ++*p;
 194 }
 195
 196
 197 bool_writer::bool_writer( c_spec& s, uchar *Dest, size_t Len)
 198   : bool_coder( s),
 199     Bstart( Dest),
 200     Bend( Len? Dest+Len : 0),
 201     B( Dest)
 202 {
 203     assert( Dest);
 204     reset();
 205 }
 206
 207 bool_writer::~bool_writer() { flush();}
 208
 209 #if 1
 210     extern "C" { int bc_v = 0;}
 211 #else
 212 #   define bc_v 0
 213 #endif
 214
 215
 216 void bool_writer::raw( bool value, uint32 s) {
 217     uint32 L = Low;
 218
 219     assert( Range >= min_range  &&  Range <= spec.max_range());
 220     assert( !is_toast  &&  s  &&  s < Range);
 221
 222     if( bc_v) printf(
 223         "Writing a %d, B %x  Low %x  Range %x  s %x   blag %d ...\n",
 224         value? 1:0, B-Bstart, Low, Range, s, bit_lag
 225     );
 226     if( value) {
 227         L += s;
 228         s = Range - s;
 229     } else
 230         s -= rinc;
 231     if( s < min_range) {
 232         int ct = bit_lag;  do {
 233             if( !--ct) {
 234                 ct = 8;
 235                 if( L & (1 << 31))
 236                     carry();
 237                 assert( !Bend  ||  B < Bend);
 238                 *B++ = (uchar) (L >> 23);
 239                 L &= (1<<23) - 1;
 240             }
 241         } while( L += L, (s += s + rinc) < min_range);
 242         bit_lag = ct;
 243     }
 244     Low = L;
 245     Range = s;
 246     if( bc_v)
 247         printf(
 248             "...done, B %x  Low %x  Range %x  blag %d \n",
 249                 B-Bstart, Low, Range, bit_lag
 250         );
 251 }
 252
 253 bool_writer& bool_writer::flush() {
 254     if( is_toast)
 255         return *this;
 256     int b = bit_lag;
 257     uint32 L = Low;
 258     assert( b);
 259     if( L & (1 << (32 - b)))
 260         carry();
 261     L <<= b & 7;
 262     b >>= 3;
 263     while( --b >= 0)
 264         L <<= 8;
 265     b = 4;
 266     assert( !Bend  ||  B + 4 <= Bend);
 267     do {
 268         *B++ = (uchar) (L >> 24);
 269         L <<= 8;
 270     } while( --b);
 271     is_toast = 1;
 272     return *this;
 273 }
 274
 275
 276 bool_reader::bool_reader( c_spec& s, cuchar *src, size_t Len)
 277   : bool_coder( s),
 278     Bstart( src),
 279     B( src),
 280     Bend( Len? src+Len : 0),
 281     shf( 32 - s.w),
 282     bct( 8)
 283 {
 284     int i = 4;  do { Low <<= 8;  Low |= *B++;}  while( --i);
 285 }
 286
 287
 288 bool bool_reader::raw( uint32 s) {
 289
 290     bool val = 0;
 291     uint32 L = Low;
 292     cuint32 S = s << shf;
 293
 294     assert( Range >= min_range  &&  Range <= spec.max_range());
 295     assert( s  &&  s < Range  &&  (L >> shf) < Range);
 296
 297     if( bc_v)
 298         printf(
 299             "Reading, B %x  Low %x  Range %x  s %x  bct %d ...\n",
 300             B-Bstart, Low, Range, s, bct
 301         );
 302
 303     if( L >= S) {
 304         L -= S;
 305         s = Range - s;
 306         assert( L < (s << shf));
 307         val = 1;
 308     } else
 309         s -= rinc;
 310     if( s < min_range) {
 311         int ct = bct;
 312         do {
 313             assert( ~L & (1 << 31));
 314             L += L;
 315             if( !--ct) {
 316                 ct = 8;
 317                 if( !Bend  ||  B < Bend)
 318                     L |= *B++;
 319             }
 320         } while( (s += s + rinc) < min_range);
 321         bct = ct;
 322     }
 323     Low = L;
 324     Range = s;
 325     if( bc_v)
 326         printf(
 327             "...done, val %d  B %x  Low %x  Range %x  bct %d\n",
 328             val? 1:0, B-Bstart, Low, Range, bct
 329         );
 330     return val;
 331 }
 332
 333
 334 /* C interfaces */
 335
 336 // spec interface
 337
 338 struct NS : bool_coder_namespace {
 339     static Rounding r( vp8bc_c_prec *p, Rounding rr =down_full) {
 340         return p? (Rounding) p->r : rr;
 341     }
 342 };
 343
 344 bool_coder_spec *vp8bc_vp6spec() {
 345     return new bool_coder_spec_explicit_table( 0, bool_coder_namespace::Down, 8);
 346 }
 347 bool_coder_spec *vp8bc_float_spec(
 348     unsigned int Ebits, unsigned int Mbits, vp8bc_c_prec *p
 349 ) {
 350     return new bool_coder_spec_float( Ebits, Mbits, NS::r( p), p? p->prec : 12);
 351 }
 352 bool_coder_spec *vp8bc_literal_spec(
 353     const unsigned short m[256], vp8bc_c_prec *p
 354 ) {
 355     return new bool_coder_spec_explicit_table( m, NS::r( p), p? p->prec : 16);
 356 }
 357 bool_coder_spec *vp8bc_exponential_spec( unsigned int x, vp8bc_c_prec *p)
 358 {
 359     return new bool_coder_spec_exponential_table( x, NS::r( p), p? p->prec : 16);
 360 }
 361 bool_coder_spec *vp8bc_spec_from_file( FILE *fp) {
 362     return new bool_coder_spec( fp);
 363 }
 364 void vp8bc_destroy_spec( c_bool_coder_spec *p) { delete p;}
 365
 366 void vp8bc_spec_to_file( c_bool_coder_spec *p, FILE *fp) { p->dump( fp);}
 367
 368 vp8bc_index_t vp8bc_index( c_bool_coder_spec *p, double x) {
 369     return ( *p)( x);
 370 }
 371
 372 vp8bc_index_t vp8bc_index_from_counts(
 373     c_bool_coder_spec *p, unsigned int L, unsigned int R
 374 ) {
 375     return ( *p)( (R += L)? (double) L/R : .5);
 376 }
 377
 378 double vp8bc_probability( c_bool_coder_spec *p, vp8bc_index_t i) {
 379     return ( *p)( i);
 380 }
 381
 382 vp8bc_index_t vp8bc_complement( c_bool_coder_spec *p, vp8bc_index_t i) {
 383     return p->complement( i);
 384 }
 385 unsigned int vp8bc_cost_zero( c_bool_coder_spec *p, vp8bc_index_t i) {
 386     return p->cost_zero( i);
 387 }
 388 unsigned int vp8bc_cost_one( c_bool_coder_spec *p, vp8bc_index_t i) {
 389     return p->cost_one( i);
 390 }
 391 unsigned int vp8bc_cost_bit( c_bool_coder_spec *p, vp8bc_index_t i, int v) {
 392     return p->cost_bit( i, v);
 393 }
 394
 395 #if tim_vp8
 396     extern "C" int tok_verbose;
 397
 398 #   define dbg_l 1000000
 399
 400     static vp8bc_index_t dbg_i [dbg_l];
 401     static char dbg_v [dbg_l];
 402     static size_t dbg_w = 0, dbg_r = 0;
 403 #endif
 404
 405 // writer interface
 406
 407 bool_writer *vp8bc_create_writer(
 408     c_bool_coder_spec *p, unsigned char *D, size_t L
 409 ) {
 410     return new bool_writer( *p, D, L);
 411 }
 412
 413 size_t vp8bc_destroy_writer( bool_writer *p) {
 414     const size_t s = p->flush().bytes_written();
 415     delete p;
 416     return s;
 417 }
 418
 419 void vp8bc_write_bool( bool_writer *p, int v, vp8bc_index_t i)
 420 {
 421 #   if tim_vp8
 422         // bc_v = dbg_w < 10;
 423         if( bc_v = tok_verbose)
 424             printf( " writing %d at prob %d\n", v? 1:0, i);
 425         accum_entropy_bc( &p->Spec(), i, v);
 426
 427         ( *p)( i, (bool) v);
 428
 429         if( dbg_w < dbg_l) {
 430             dbg_i [dbg_w] = i;
 431             dbg_v [dbg_w++] = v? 1:0;
 432         }
 433 #   else
 434         ( *p)( i, (bool) v);
 435 #   endif
 436 }
 437
 438 void vp8bc_write_bits( bool_writer *p, unsigned int v, int n)
 439 {
 440 #   if tim_vp8
 441         {
 442             c_bool_coder_spec * const s = & p->Spec();
 443             const vp8bc_index_t i = s->half_index();
 444             int m = n;
 445             while( --m >= 0)
 446                 accum_entropy_bc( s, i, (v>>m) & 1);
 447         }
 448 #   endif
 449
 450     p->write_bits( n, v);
 451 }
 452
 453 c_bool_coder_spec *vp8bc_writer_spec( c_bool_writer *w) { return & w->Spec();}
 454
 455 // reader interface
 456
 457 bool_reader *vp8bc_create_reader(
 458     c_bool_coder_spec *p, const unsigned char *S, size_t L
 459 ) {
 460     return new bool_reader( *p, S, L);
 461 }
 462
 463 void vp8bc_destroy_reader( bool_reader * p) { delete p;}
 464
 465 int vp8bc_read_bool( bool_reader *p, vp8bc_index_t i)
 466 {
 467 #   if tim_vp8
 468         // bc_v = dbg_r < 10;
 469         bc_v = tok_verbose;
 470         const int v = ( *p)( i)? 1:0;
 471         if( tok_verbose)
 472             printf( " reading %d at prob %d\n", v, i);
 473         if( dbg_r < dbg_l) {
 474             assert( dbg_r <= dbg_w);
 475             if( i != dbg_i[dbg_r]  ||  v != dbg_v[dbg_r]) {
 476                 printf(
 477         "Position %d: INCORRECTLY READING %d  prob %d, wrote %d  prob %d\n",
 478                     dbg_r, v, i, dbg_v[dbg_r], dbg_i[dbg_r]
 479                 );
 480             }
 481             ++dbg_r;
 482         }
 483         return v;
 484 #   else
 485         return ( *p)( i)? 1:0;
 486 #   endif
 487 }
 488
 489 unsigned int vp8bc_read_bits( bool_reader *p, int n) { return p->read_bits( n);}
 490
 491 c_bool_coder_spec *vp8bc_reader_spec( c_bool_reader *r) { return & r->Spec();}
 492
 493 #undef bc_v