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