• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
~int_types()27 int_types::~int_types() {}
28 
check_prec() const29 void bool_coder_spec::check_prec() const {
30     assert( w  &&  (r==Up || w > 1)  &&  w < 24  &&  (ebias || w < 17));
31 }
32 
float_init(uint Ebits,uint Mbits)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 
cost_init()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 
bool_coder_spec_explicit_table(cuint16 tbl[256],Rounding rr,uint prec)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 
bool_coder_spec_exponential_table(uint x,Rounding rr,uint prec)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 
bool_coder_spec(FILE * fp)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 
dump(FILE * fp) const124 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 
operator ()(double p) const131 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 
operator ()(Index i) const180 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 
carry()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 
bool_writer(c_spec & s,uchar * Dest,size_t Len)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 
~bool_writer()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 
raw(bool value,uint32 s)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 
flush()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 
bool_reader(c_spec & s,cuchar * src,size_t Len)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 
raw(uint32 s)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 {
rNS340     static Rounding r( vp8bc_c_prec *p, Rounding rr =down_full) {
341         return p? (Rounding) p->r : rr;
342     }
343 };
344 
vp8bc_vp6spec()345 bool_coder_spec *vp8bc_vp6spec() {
346     return new bool_coder_spec_explicit_table( 0, bool_coder_namespace::Down, 8);
347 }
vp8bc_float_spec(unsigned int Ebits,unsigned int Mbits,vp8bc_c_prec * p)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 }
vp8bc_literal_spec(const unsigned short m[256],vp8bc_c_prec * p)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 }
vp8bc_exponential_spec(unsigned int x,vp8bc_c_prec * p)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 }
vp8bc_spec_from_file(FILE * fp)362 bool_coder_spec *vp8bc_spec_from_file( FILE *fp) {
363     return new bool_coder_spec( fp);
364 }
vp8bc_destroy_spec(c_bool_coder_spec * p)365 void vp8bc_destroy_spec( c_bool_coder_spec *p) { delete p;}
366 
vp8bc_spec_to_file(c_bool_coder_spec * p,FILE * fp)367 void vp8bc_spec_to_file( c_bool_coder_spec *p, FILE *fp) { p->dump( fp);}
368 
vp8bc_index(c_bool_coder_spec * p,double x)369 vp8bc_index_t vp8bc_index( c_bool_coder_spec *p, double x) {
370     return ( *p)( x);
371 }
372 
vp8bc_index_from_counts(c_bool_coder_spec * p,unsigned int L,unsigned int R)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 
vp8bc_probability(c_bool_coder_spec * p,vp8bc_index_t i)379 double vp8bc_probability( c_bool_coder_spec *p, vp8bc_index_t i) {
380     return ( *p)( i);
381 }
382 
vp8bc_complement(c_bool_coder_spec * p,vp8bc_index_t i)383 vp8bc_index_t vp8bc_complement( c_bool_coder_spec *p, vp8bc_index_t i) {
384     return p->complement( i);
385 }
vp8bc_cost_zero(c_bool_coder_spec * p,vp8bc_index_t i)386 unsigned int vp8bc_cost_zero( c_bool_coder_spec *p, vp8bc_index_t i) {
387     return p->cost_zero( i);
388 }
vp8bc_cost_one(c_bool_coder_spec * p,vp8bc_index_t i)389 unsigned int vp8bc_cost_one( c_bool_coder_spec *p, vp8bc_index_t i) {
390     return p->cost_one( i);
391 }
vp8bc_cost_bit(c_bool_coder_spec * p,vp8bc_index_t i,int v)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 
vp8bc_create_writer(c_bool_coder_spec * p,unsigned char * D,size_t L)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 
vp8bc_destroy_writer(bool_writer * p)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 
vp8bc_write_bool(bool_writer * p,int v,vp8bc_index_t i)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 
vp8bc_write_bits(bool_writer * p,unsigned int v,int n)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 
vp8bc_writer_spec(c_bool_writer * w)454 c_bool_coder_spec *vp8bc_writer_spec( c_bool_writer *w) { return & w->Spec();}
455 
456 // reader interface
457 
vp8bc_create_reader(c_bool_coder_spec * p,const unsigned char * S,size_t L)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 
vp8bc_destroy_reader(bool_reader * p)464 void vp8bc_destroy_reader( bool_reader * p) { delete p;}
465 
vp8bc_read_bool(bool_reader * p,vp8bc_index_t i)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 
vp8bc_read_bits(bool_reader * p,int n)490 unsigned int vp8bc_read_bits( bool_reader *p, int n) { return p->read_bits( n);}
491 
vp8bc_reader_spec(c_bool_reader * r)492 c_bool_coder_spec *vp8bc_reader_spec( c_bool_reader *r) { return & r->Spec();}
493 
494 #undef bc_v
495