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