diff options
author | John Koleszar <jkoleszar@google.com> | 2010-05-18 11:58:33 -0400 |
---|---|---|
committer | John Koleszar <jkoleszar@google.com> | 2010-05-18 11:58:33 -0400 |
commit | 0ea50ce9cb4b65eee6afa1d041fe8beb5abda667 (patch) | |
tree | 1f3b9019f28bc56fd3156f96e5a9653a983ee61b /vp8/common/x86/boolcoder.cxx | |
download | libvpx-0ea50ce9cb4b65eee6afa1d041fe8beb5abda667.tar libvpx-0ea50ce9cb4b65eee6afa1d041fe8beb5abda667.tar.gz libvpx-0ea50ce9cb4b65eee6afa1d041fe8beb5abda667.tar.bz2 libvpx-0ea50ce9cb4b65eee6afa1d041fe8beb5abda667.zip |
Initial WebM release
Diffstat (limited to 'vp8/common/x86/boolcoder.cxx')
-rw-r--r-- | vp8/common/x86/boolcoder.cxx | 493 |
1 files changed, 493 insertions, 0 deletions
diff --git a/vp8/common/x86/boolcoder.cxx b/vp8/common/x86/boolcoder.cxx new file mode 100644 index 000000000..06faca69c --- /dev/null +++ b/vp8/common/x86/boolcoder.cxx @@ -0,0 +1,493 @@ +/* + * Copyright (c) 2010 The VP8 project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license and patent + * grant that can be found in the LICENSE file in the root of the source + * tree. All contributing project authors may be found in the AUTHORS + * file in the root of the source tree. + */ + + + +/* Arithmetic bool coder with largish probability range. + Timothy S Murphy 6 August 2004 */ + +#include <assert.h> +#include <math.h> + +#include "bool_coder.h" + +#if tim_vp8 + extern "C" { +# include "VP8cx/treewriter.h" + } +#endif + +int_types::~int_types() {} + +void bool_coder_spec::check_prec() const { + assert( w && (r==Up || w > 1) && w < 24 && (ebias || w < 17)); +} + +bool bool_coder_spec::float_init( uint Ebits, uint Mbits) { + uint b = (ebits = Ebits) + (mbits = Mbits); + if( b) { + assert( ebits < 6 && w + mbits < 31); + assert( ebits + mbits < sizeof(Index) * 8); + ebias = (1 << ebits) + 1 + mbits; + mmask = (1 << mbits) - 1; + max_index = ( ( half_index = 1 << b ) << 1) - 1; + } else { + ebias = 0; + max_index = 255; + half_index = 128; + } + check_prec(); + return b? 1:0; +} + +void bool_coder_spec::cost_init() +{ + static cdouble c = -(1 << 20)/log( 2.); + + FILE *f = fopen( "costs.txt", "w"); + assert( f); + + assert( sizeof(int) >= 4); /* for C interface */ + assert( max_index <= 255); /* size of Ctbl */ + uint i = 0; do { + cdouble p = ( *this)( (Index) i); + Ctbl[i] = (uint32) ( log( p) * c); + fprintf( + f, "cost( %d -> %10.7f) = %10d = %12.5f bits\n", + i, p, Ctbl[i], (double) Ctbl[i] / (1<<20) + ); + } while( ++i <= max_index); + fclose( f); +} + +bool_coder_spec_explicit_table::bool_coder_spec_explicit_table( + cuint16 tbl[256], Rounding rr, uint prec +) + : bool_coder_spec( prec, rr) +{ + check_prec(); + uint i = 0; + if( tbl) + do { Ptbl[i] = tbl[i];} while( ++i < 256); + else + do { Ptbl[i] = i << 8;} while( ++i < 256); + cost_init(); +} + + +bool_coder_spec_exponential_table::bool_coder_spec_exponential_table( + uint x, Rounding rr, uint prec +) + : bool_coder_spec( prec, rr) +{ + assert( x > 1 && x <= 16); + check_prec(); + Ptbl[128] = 32768u; + Ptbl[0] = (uint16) pow( 2., 16. - x); + --x; + int i=1; do { + cdouble d = pow( .5, 1. + (1. - i/128.)*x) * 65536.; + uint16 v = (uint16) d; + if( v < i) + v = i; + Ptbl[256-i] = (uint16) ( 65536U - (Ptbl[i] = v)); + } while( ++i < 128); + cost_init(); +} + +bool_coder_spec::bool_coder_spec( FILE *fp) { + fscanf( fp, "%d", &w); + int v; + fscanf( fp, "%d", &v); + assert( 0 <= v && v <= 2); + r = (Rounding) v; + fscanf( fp, "%d", &ebits); + fscanf( fp, "%d", &mbits); + if( float_init( ebits, mbits)) + return; + int i=0; do { + uint v; + fscanf( fp, "%d", &v); + assert( 0 <=v && v <= 65535U); + Ptbl[i] = v; + } while( ++i < 256); + cost_init(); +} + +void bool_coder_spec::dump( FILE *fp) const { + fprintf( fp, "%d %d %d %d\n", w, (int) r, ebits, mbits); + if( ebits || mbits) + return; + int i=0; do { fprintf( fp, "%d\n", Ptbl[i]);} while( ++i < 256); +} + +vp8bc_index_t bool_coder_spec::operator()( double p) const +{ + if( p <= 0.) + return 0; + if( p >= 1.) + return max_index; + if( ebias) { + if( p > .5) + return max_index - ( *this)( 1. - p); + int e; + uint m = (uint) ldexp( frexp( p, &e), mbits + 2); + uint x = 1 << (mbits + 1); + assert( x <= m && m < x<<1); + if( (m = (m >> 1) + (m & 1)) >= x) { + m = x >> 1; + ++e; + } + int y = 1 << ebits; + if( (e += y) >= y) + return half_index - 1; + if( e < 0) + return 0; + return (Index) ( (e << mbits) + (m & mmask)); + } + + cuint16 v = (uint16) (p * 65536.); + int i = 128; + int j = 128; + uint16 w; + while( w = Ptbl[i], j >>= 1) { + if( w < v) + i += j; + else if( w == v) + return (uchar) i; + else + i -= j; + } + if( w > v) { + cuint16 x = Ptbl[i-1]; + if( v <= x || w - v > v - x) + --i; + } else if( w < v && i < 255) { + cuint16 x = Ptbl[i+1]; + if( x <= v || x - v < v - w) + ++i; + } + return (Index) i; +} + +double bool_coder_spec::operator()( Index i) const { + if( !ebias) + return Ptbl[i]/65536.; + if( i >= half_index) + return 1. - ( *this)( (Index) (max_index - i)); + return ldexp( (double)mantissa( i), - (int) exponent( i)); +} + + + +void bool_writer::carry() { + uchar *p = B; + assert( p > Bstart); + while( *--p == 255) { assert( p > Bstart); *p = 0;} + ++*p; +} + + +bool_writer::bool_writer( c_spec& s, uchar *Dest, size_t Len) + : bool_coder( s), + Bstart( Dest), + Bend( Len? Dest+Len : 0), + B( Dest) +{ + assert( Dest); + reset(); +} + +bool_writer::~bool_writer() { flush();} + +#if 1 + extern "C" { int bc_v = 0;} +#else +# define bc_v 0 +#endif + + +void bool_writer::raw( bool value, uint32 s) { + uint32 L = Low; + + assert( Range >= min_range && Range <= spec.max_range()); + assert( !is_toast && s && s < Range); + + if( bc_v) printf( + "Writing a %d, B %x Low %x Range %x s %x blag %d ...\n", + value? 1:0, B-Bstart, Low, Range, s, bit_lag + ); + if( value) { + L += s; + s = Range - s; + } else + s -= rinc; + if( s < min_range) { + int ct = bit_lag; do { + if( !--ct) { + ct = 8; + if( L & (1 << 31)) + carry(); + assert( !Bend || B < Bend); + *B++ = (uchar) (L >> 23); + L &= (1<<23) - 1; + } + } while( L += L, (s += s + rinc) < min_range); + bit_lag = ct; + } + Low = L; + Range = s; + if( bc_v) + printf( + "...done, B %x Low %x Range %x blag %d \n", + B-Bstart, Low, Range, bit_lag + ); +} + +bool_writer& bool_writer::flush() { + if( is_toast) + return *this; + int b = bit_lag; + uint32 L = Low; + assert( b); + if( L & (1 << (32 - b))) + carry(); + L <<= b & 7; + b >>= 3; + while( --b >= 0) + L <<= 8; + b = 4; + assert( !Bend || B + 4 <= Bend); + do { + *B++ = (uchar) (L >> 24); + L <<= 8; + } while( --b); + is_toast = 1; + return *this; +} + + +bool_reader::bool_reader( c_spec& s, cuchar *src, size_t Len) + : bool_coder( s), + Bstart( src), + B( src), + Bend( Len? src+Len : 0), + shf( 32 - s.w), + bct( 8) +{ + int i = 4; do { Low <<= 8; Low |= *B++;} while( --i); +} + + +bool bool_reader::raw( uint32 s) { + + bool val = 0; + uint32 L = Low; + cuint32 S = s << shf; + + assert( Range >= min_range && Range <= spec.max_range()); + assert( s && s < Range && (L >> shf) < Range); + + if( bc_v) + printf( + "Reading, B %x Low %x Range %x s %x bct %d ...\n", + B-Bstart, Low, Range, s, bct + ); + + if( L >= S) { + L -= S; + s = Range - s; + assert( L < (s << shf)); + val = 1; + } else + s -= rinc; + if( s < min_range) { + int ct = bct; + do { + assert( ~L & (1 << 31)); + L += L; + if( !--ct) { + ct = 8; + if( !Bend || B < Bend) + L |= *B++; + } + } while( (s += s + rinc) < min_range); + bct = ct; + } + Low = L; + Range = s; + if( bc_v) + printf( + "...done, val %d B %x Low %x Range %x bct %d\n", + val? 1:0, B-Bstart, Low, Range, bct + ); + return val; +} + + +/* C interfaces */ + +// spec interface + +struct NS : bool_coder_namespace { + static Rounding r( vp8bc_c_prec *p, Rounding rr =down_full) { + return p? (Rounding) p->r : rr; + } +}; + +bool_coder_spec *vp8bc_vp6spec() { + return new bool_coder_spec_explicit_table( 0, bool_coder_namespace::Down, 8); +} +bool_coder_spec *vp8bc_float_spec( + unsigned int Ebits, unsigned int Mbits, vp8bc_c_prec *p +) { + return new bool_coder_spec_float( Ebits, Mbits, NS::r( p), p? p->prec : 12); +} +bool_coder_spec *vp8bc_literal_spec( + const unsigned short m[256], vp8bc_c_prec *p +) { + return new bool_coder_spec_explicit_table( m, NS::r( p), p? p->prec : 16); +} +bool_coder_spec *vp8bc_exponential_spec( unsigned int x, vp8bc_c_prec *p) +{ + return new bool_coder_spec_exponential_table( x, NS::r( p), p? p->prec : 16); +} +bool_coder_spec *vp8bc_spec_from_file( FILE *fp) { + return new bool_coder_spec( fp); +} +void vp8bc_destroy_spec( c_bool_coder_spec *p) { delete p;} + +void vp8bc_spec_to_file( c_bool_coder_spec *p, FILE *fp) { p->dump( fp);} + +vp8bc_index_t vp8bc_index( c_bool_coder_spec *p, double x) { + return ( *p)( x); +} + +vp8bc_index_t vp8bc_index_from_counts( + c_bool_coder_spec *p, unsigned int L, unsigned int R +) { + return ( *p)( (R += L)? (double) L/R : .5); +} + +double vp8bc_probability( c_bool_coder_spec *p, vp8bc_index_t i) { + return ( *p)( i); +} + +vp8bc_index_t vp8bc_complement( c_bool_coder_spec *p, vp8bc_index_t i) { + return p->complement( i); +} +unsigned int vp8bc_cost_zero( c_bool_coder_spec *p, vp8bc_index_t i) { + return p->cost_zero( i); +} +unsigned int vp8bc_cost_one( c_bool_coder_spec *p, vp8bc_index_t i) { + return p->cost_one( i); +} +unsigned int vp8bc_cost_bit( c_bool_coder_spec *p, vp8bc_index_t i, int v) { + return p->cost_bit( i, v); +} + +#if tim_vp8 + extern "C" int tok_verbose; + +# define dbg_l 1000000 + + static vp8bc_index_t dbg_i [dbg_l]; + static char dbg_v [dbg_l]; + static size_t dbg_w = 0, dbg_r = 0; +#endif + +// writer interface + +bool_writer *vp8bc_create_writer( + c_bool_coder_spec *p, unsigned char *D, size_t L +) { + return new bool_writer( *p, D, L); +} + +size_t vp8bc_destroy_writer( bool_writer *p) { + const size_t s = p->flush().bytes_written(); + delete p; + return s; +} + +void vp8bc_write_bool( bool_writer *p, int v, vp8bc_index_t i) +{ +# if tim_vp8 + // bc_v = dbg_w < 10; + if( bc_v = tok_verbose) + printf( " writing %d at prob %d\n", v? 1:0, i); + accum_entropy_bc( &p->Spec(), i, v); + + ( *p)( i, (bool) v); + + if( dbg_w < dbg_l) { + dbg_i [dbg_w] = i; + dbg_v [dbg_w++] = v? 1:0; + } +# else + ( *p)( i, (bool) v); +# endif +} + +void vp8bc_write_bits( bool_writer *p, unsigned int v, int n) +{ +# if tim_vp8 + { + c_bool_coder_spec * const s = & p->Spec(); + const vp8bc_index_t i = s->half_index(); + int m = n; + while( --m >= 0) + accum_entropy_bc( s, i, (v>>m) & 1); + } +# endif + + p->write_bits( n, v); +} + +c_bool_coder_spec *vp8bc_writer_spec( c_bool_writer *w) { return & w->Spec();} + +// reader interface + +bool_reader *vp8bc_create_reader( + c_bool_coder_spec *p, const unsigned char *S, size_t L +) { + return new bool_reader( *p, S, L); +} + +void vp8bc_destroy_reader( bool_reader * p) { delete p;} + +int vp8bc_read_bool( bool_reader *p, vp8bc_index_t i) +{ +# if tim_vp8 + // bc_v = dbg_r < 10; + bc_v = tok_verbose; + const int v = ( *p)( i)? 1:0; + if( tok_verbose) + printf( " reading %d at prob %d\n", v, i); + if( dbg_r < dbg_l) { + assert( dbg_r <= dbg_w); + if( i != dbg_i[dbg_r] || v != dbg_v[dbg_r]) { + printf( + "Position %d: INCORRECTLY READING %d prob %d, wrote %d prob %d\n", + dbg_r, v, i, dbg_v[dbg_r], dbg_i[dbg_r] + ); + } + ++dbg_r; + } + return v; +# else + return ( *p)( i)? 1:0; +# endif +} + +unsigned int vp8bc_read_bits( bool_reader *p, int n) { return p->read_bits( n);} + +c_bool_coder_spec *vp8bc_reader_spec( c_bool_reader *r) { return & r->Spec();} + +#undef bc_v |