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 #include <math.h>
13 #include <stdio.h>
14 #include <string.h>
15 #include <assert.h>
16 #include "onyx_int.h"
17 #include "tokenize.h"
18 #include "vpx_mem/vpx_mem.h"
19
20 /* Global event counters used for accumulating statistics across several
21 compressions, then generating context.c = initial stats. */
22
23 #ifdef VP8_ENTROPY_STATS
24 _int64 context_counters[BLOCK_TYPES] [COEF_BANDS] [PREV_COEF_CONTEXTS] [MAX_ENTROPY_TOKENS];
25 #endif
26 void vp8_stuff_mb(VP8_COMP *cpi, MACROBLOCK *x, TOKENEXTRA **t) ;
27 void vp8_fix_contexts(MACROBLOCKD *x);
28
29 #include "dct_value_tokens.h"
30 #include "dct_value_cost.h"
31
32 const TOKENVALUE *const vp8_dct_value_tokens_ptr = dct_value_tokens +
33 DCT_MAX_VALUE;
34 const short *const vp8_dct_value_cost_ptr = dct_value_cost + DCT_MAX_VALUE;
35
36 #if 0
37 int skip_true_count = 0;
38 int skip_false_count = 0;
39 #endif
40
41 /* function used to generate dct_value_tokens and dct_value_cost tables */
42 /*
43 static void fill_value_tokens()
44 {
45
46 TOKENVALUE *t = dct_value_tokens + DCT_MAX_VALUE;
47 const vp8_extra_bit_struct *e = vp8_extra_bits;
48
49 int i = -DCT_MAX_VALUE;
50 int sign = 1;
51
52 do
53 {
54 if (!i)
55 sign = 0;
56
57 {
58 const int a = sign ? -i : i;
59 int eb = sign;
60
61 if (a > 4)
62 {
63 int j = 4;
64
65 while (++j < 11 && e[j].base_val <= a) {}
66
67 t[i].Token = --j;
68 eb |= (a - e[j].base_val) << 1;
69 }
70 else
71 t[i].Token = a;
72
73 t[i].Extra = eb;
74 }
75
76 // initialize the cost for extra bits for all possible coefficient value.
77 {
78 int cost = 0;
79 const vp8_extra_bit_struct *p = vp8_extra_bits + t[i].Token;
80
81 if (p->base_val)
82 {
83 const int extra = t[i].Extra;
84 const int Length = p->Len;
85
86 if (Length)
87 cost += vp8_treed_cost(p->tree, p->prob, extra >> 1, Length);
88
89 cost += vp8_cost_bit(vp8_prob_half, extra & 1); // sign
90 dct_value_cost[i + DCT_MAX_VALUE] = cost;
91 }
92
93 }
94
95 }
96 while (++i < DCT_MAX_VALUE);
97
98 vp8_dct_value_tokens_ptr = dct_value_tokens + DCT_MAX_VALUE;
99 vp8_dct_value_cost_ptr = dct_value_cost + DCT_MAX_VALUE;
100 }
101 */
102
tokenize2nd_order_b(MACROBLOCK * x,TOKENEXTRA ** tp,VP8_COMP * cpi)103 static void tokenize2nd_order_b
104 (
105 MACROBLOCK *x,
106 TOKENEXTRA **tp,
107 VP8_COMP *cpi
108 )
109 {
110 MACROBLOCKD *xd = &x->e_mbd;
111 int pt; /* near block/prev token context index */
112 int c; /* start at DC */
113 TOKENEXTRA *t = *tp;/* store tokens starting here */
114 const BLOCKD *b;
115 const short *qcoeff_ptr;
116 ENTROPY_CONTEXT * a;
117 ENTROPY_CONTEXT * l;
118 int band, rc, v, token;
119 int eob;
120
121 b = xd->block + 24;
122 qcoeff_ptr = b->qcoeff;
123 a = (ENTROPY_CONTEXT *)xd->above_context + 8;
124 l = (ENTROPY_CONTEXT *)xd->left_context + 8;
125 eob = xd->eobs[24];
126 VP8_COMBINEENTROPYCONTEXTS(pt, *a, *l);
127
128 if(!eob)
129 {
130 /* c = band for this case */
131 t->Token = DCT_EOB_TOKEN;
132 t->context_tree = cpi->common.fc.coef_probs [1] [0] [pt];
133 t->skip_eob_node = 0;
134
135 ++x->coef_counts [1] [0] [pt] [DCT_EOB_TOKEN];
136 t++;
137 *tp = t;
138 *a = *l = 0;
139 return;
140 }
141
142 v = qcoeff_ptr[0];
143 t->Extra = vp8_dct_value_tokens_ptr[v].Extra;
144 token = vp8_dct_value_tokens_ptr[v].Token;
145 t->Token = token;
146
147 t->context_tree = cpi->common.fc.coef_probs [1] [0] [pt];
148 t->skip_eob_node = 0;
149 ++x->coef_counts [1] [0] [pt] [token];
150 pt = vp8_prev_token_class[token];
151 t++;
152 c = 1;
153
154 for (; c < eob; c++)
155 {
156 rc = vp8_default_zig_zag1d[c];
157 band = vp8_coef_bands[c];
158 v = qcoeff_ptr[rc];
159
160 t->Extra = vp8_dct_value_tokens_ptr[v].Extra;
161 token = vp8_dct_value_tokens_ptr[v].Token;
162
163 t->Token = token;
164 t->context_tree = cpi->common.fc.coef_probs [1] [band] [pt];
165
166 t->skip_eob_node = ((pt == 0));
167
168 ++x->coef_counts [1] [band] [pt] [token];
169
170 pt = vp8_prev_token_class[token];
171 t++;
172 }
173 if (c < 16)
174 {
175 band = vp8_coef_bands[c];
176 t->Token = DCT_EOB_TOKEN;
177 t->context_tree = cpi->common.fc.coef_probs [1] [band] [pt];
178
179 t->skip_eob_node = 0;
180
181 ++x->coef_counts [1] [band] [pt] [DCT_EOB_TOKEN];
182
183 t++;
184 }
185
186 *tp = t;
187 *a = *l = 1;
188
189 }
190
tokenize1st_order_b(MACROBLOCK * x,TOKENEXTRA ** tp,int type,VP8_COMP * cpi)191 static void tokenize1st_order_b
192 (
193 MACROBLOCK *x,
194 TOKENEXTRA **tp,
195 int type, /* which plane: 0=Y no DC, 1=Y2, 2=UV, 3=Y with DC */
196 VP8_COMP *cpi
197 )
198 {
199 MACROBLOCKD *xd = &x->e_mbd;
200 unsigned int block;
201 const BLOCKD *b;
202 int pt; /* near block/prev token context index */
203 int c;
204 int token;
205 TOKENEXTRA *t = *tp;/* store tokens starting here */
206 const short *qcoeff_ptr;
207 ENTROPY_CONTEXT * a;
208 ENTROPY_CONTEXT * l;
209 int band, rc, v;
210 int tmp1, tmp2;
211
212 b = xd->block;
213 /* Luma */
214 for (block = 0; block < 16; block++, b++)
215 {
216 const int eob = *b->eob;
217 tmp1 = vp8_block2above[block];
218 tmp2 = vp8_block2left[block];
219 qcoeff_ptr = b->qcoeff;
220 a = (ENTROPY_CONTEXT *)xd->above_context + tmp1;
221 l = (ENTROPY_CONTEXT *)xd->left_context + tmp2;
222
223 VP8_COMBINEENTROPYCONTEXTS(pt, *a, *l);
224
225 c = type ? 0 : 1;
226
227 if(c >= eob)
228 {
229 /* c = band for this case */
230 t->Token = DCT_EOB_TOKEN;
231 t->context_tree = cpi->common.fc.coef_probs [type] [c] [pt];
232 t->skip_eob_node = 0;
233
234 ++x->coef_counts [type] [c] [pt] [DCT_EOB_TOKEN];
235 t++;
236 *tp = t;
237 *a = *l = 0;
238 continue;
239 }
240
241 v = qcoeff_ptr[c];
242
243 t->Extra = vp8_dct_value_tokens_ptr[v].Extra;
244 token = vp8_dct_value_tokens_ptr[v].Token;
245 t->Token = token;
246
247 t->context_tree = cpi->common.fc.coef_probs [type] [c] [pt];
248 t->skip_eob_node = 0;
249 ++x->coef_counts [type] [c] [pt] [token];
250 pt = vp8_prev_token_class[token];
251 t++;
252 c++;
253
254 assert(eob <= 16);
255 for (; c < eob; c++)
256 {
257 rc = vp8_default_zig_zag1d[c];
258 band = vp8_coef_bands[c];
259 v = qcoeff_ptr[rc];
260
261 t->Extra = vp8_dct_value_tokens_ptr[v].Extra;
262 token = vp8_dct_value_tokens_ptr[v].Token;
263
264 t->Token = token;
265 t->context_tree = cpi->common.fc.coef_probs [type] [band] [pt];
266
267 t->skip_eob_node = (pt == 0);
268 ++x->coef_counts [type] [band] [pt] [token];
269
270 pt = vp8_prev_token_class[token];
271 t++;
272 }
273 if (c < 16)
274 {
275 band = vp8_coef_bands[c];
276 t->Token = DCT_EOB_TOKEN;
277 t->context_tree = cpi->common.fc.coef_probs [type] [band] [pt];
278
279 t->skip_eob_node = 0;
280 ++x->coef_counts [type] [band] [pt] [DCT_EOB_TOKEN];
281
282 t++;
283 }
284 *tp = t;
285 *a = *l = 1;
286 }
287
288 /* Chroma */
289 for (block = 16; block < 24; block++, b++)
290 {
291 const int eob = *b->eob;
292 tmp1 = vp8_block2above[block];
293 tmp2 = vp8_block2left[block];
294 qcoeff_ptr = b->qcoeff;
295 a = (ENTROPY_CONTEXT *)xd->above_context + tmp1;
296 l = (ENTROPY_CONTEXT *)xd->left_context + tmp2;
297
298 VP8_COMBINEENTROPYCONTEXTS(pt, *a, *l);
299
300 if(!eob)
301 {
302 /* c = band for this case */
303 t->Token = DCT_EOB_TOKEN;
304 t->context_tree = cpi->common.fc.coef_probs [2] [0] [pt];
305 t->skip_eob_node = 0;
306
307 ++x->coef_counts [2] [0] [pt] [DCT_EOB_TOKEN];
308 t++;
309 *tp = t;
310 *a = *l = 0;
311 continue;
312 }
313
314 v = qcoeff_ptr[0];
315
316 t->Extra = vp8_dct_value_tokens_ptr[v].Extra;
317 token = vp8_dct_value_tokens_ptr[v].Token;
318 t->Token = token;
319
320 t->context_tree = cpi->common.fc.coef_probs [2] [0] [pt];
321 t->skip_eob_node = 0;
322 ++x->coef_counts [2] [0] [pt] [token];
323 pt = vp8_prev_token_class[token];
324 t++;
325 c = 1;
326
327 assert(eob <= 16);
328 for (; c < eob; c++)
329 {
330 rc = vp8_default_zig_zag1d[c];
331 band = vp8_coef_bands[c];
332 v = qcoeff_ptr[rc];
333
334 t->Extra = vp8_dct_value_tokens_ptr[v].Extra;
335 token = vp8_dct_value_tokens_ptr[v].Token;
336
337 t->Token = token;
338 t->context_tree = cpi->common.fc.coef_probs [2] [band] [pt];
339
340 t->skip_eob_node = (pt == 0);
341
342 ++x->coef_counts [2] [band] [pt] [token];
343
344 pt = vp8_prev_token_class[token];
345 t++;
346 }
347 if (c < 16)
348 {
349 band = vp8_coef_bands[c];
350 t->Token = DCT_EOB_TOKEN;
351 t->context_tree = cpi->common.fc.coef_probs [2] [band] [pt];
352
353 t->skip_eob_node = 0;
354
355 ++x->coef_counts [2] [band] [pt] [DCT_EOB_TOKEN];
356
357 t++;
358 }
359 *tp = t;
360 *a = *l = 1;
361 }
362 }
363
364
mb_is_skippable(MACROBLOCKD * x,int has_y2_block)365 static int mb_is_skippable(MACROBLOCKD *x, int has_y2_block)
366 {
367 int skip = 1;
368 int i = 0;
369
370 if (has_y2_block)
371 {
372 for (i = 0; i < 16; i++)
373 skip &= (x->eobs[i] < 2);
374 }
375
376 for (; i < 24 + has_y2_block; i++)
377 skip &= (!x->eobs[i]);
378
379 return skip;
380 }
381
382
vp8_tokenize_mb(VP8_COMP * cpi,MACROBLOCK * x,TOKENEXTRA ** t)383 void vp8_tokenize_mb(VP8_COMP *cpi, MACROBLOCK *x, TOKENEXTRA **t)
384 {
385 MACROBLOCKD *xd = &x->e_mbd;
386 int plane_type;
387 int has_y2_block;
388
389 has_y2_block = (xd->mode_info_context->mbmi.mode != B_PRED
390 && xd->mode_info_context->mbmi.mode != SPLITMV);
391
392 xd->mode_info_context->mbmi.mb_skip_coeff =
393 mb_is_skippable(xd, has_y2_block);
394 if (xd->mode_info_context->mbmi.mb_skip_coeff)
395 {
396 if (!cpi->common.mb_no_coeff_skip)
397 {
398 vp8_stuff_mb(cpi, x, t);
399 }
400 else
401 {
402 vp8_fix_contexts(xd);
403 x->skip_true_count++;
404 }
405
406 return;
407 }
408
409 plane_type = 3;
410 if(has_y2_block)
411 {
412 tokenize2nd_order_b(x, t, cpi);
413 plane_type = 0;
414 }
415
416 tokenize1st_order_b(x, t, plane_type, cpi);
417 }
418
419
420 #ifdef VP8_ENTROPY_STATS
421
init_context_counters(void)422 void init_context_counters(void)
423 {
424 vpx_memset(context_counters, 0, sizeof(context_counters));
425 }
426
print_context_counters()427 void print_context_counters()
428 {
429
430 int type, band, pt, t;
431
432 FILE *const f = fopen("context.c", "w");
433
434 fprintf(f, "#include \"entropy.h\"\n");
435
436 fprintf(f, "\n/* *** GENERATED FILE: DO NOT EDIT *** */\n\n");
437
438 fprintf(f, "int Contexts[BLOCK_TYPES] [COEF_BANDS] [PREV_COEF_CONTEXTS] [MAX_ENTROPY_TOKENS];\n\n");
439
440 fprintf(f, "const int default_contexts[BLOCK_TYPES] [COEF_BANDS] [PREV_COEF_CONTEXTS] [MAX_ENTROPY_TOKENS] = {");
441
442 # define Comma( X) (X? ",":"")
443
444 type = 0;
445
446 do
447 {
448 fprintf(f, "%s\n { /* block Type %d */", Comma(type), type);
449
450 band = 0;
451
452 do
453 {
454 fprintf(f, "%s\n { /* Coeff Band %d */", Comma(band), band);
455
456 pt = 0;
457
458 do
459 {
460 fprintf(f, "%s\n {", Comma(pt));
461
462 t = 0;
463
464 do
465 {
466 const _int64 x = context_counters [type] [band] [pt] [t];
467 const int y = (int) x;
468
469 assert(x == (_int64) y); /* no overflow handling yet */
470 fprintf(f, "%s %d", Comma(t), y);
471
472 }
473 while (++t < MAX_ENTROPY_TOKENS);
474
475 fprintf(f, "}");
476 }
477 while (++pt < PREV_COEF_CONTEXTS);
478
479 fprintf(f, "\n }");
480
481 }
482 while (++band < COEF_BANDS);
483
484 fprintf(f, "\n }");
485 }
486 while (++type < BLOCK_TYPES);
487
488 fprintf(f, "\n};\n");
489 fclose(f);
490 }
491 #endif
492
493
stuff2nd_order_b(TOKENEXTRA ** tp,ENTROPY_CONTEXT * a,ENTROPY_CONTEXT * l,VP8_COMP * cpi,MACROBLOCK * x)494 static void stuff2nd_order_b
495 (
496 TOKENEXTRA **tp,
497 ENTROPY_CONTEXT *a,
498 ENTROPY_CONTEXT *l,
499 VP8_COMP *cpi,
500 MACROBLOCK *x
501 )
502 {
503 int pt; /* near block/prev token context index */
504 TOKENEXTRA *t = *tp; /* store tokens starting here */
505 VP8_COMBINEENTROPYCONTEXTS(pt, *a, *l);
506
507 t->Token = DCT_EOB_TOKEN;
508 t->context_tree = cpi->common.fc.coef_probs [1] [0] [pt];
509 t->skip_eob_node = 0;
510 ++x->coef_counts [1] [0] [pt] [DCT_EOB_TOKEN];
511 ++t;
512
513 *tp = t;
514 pt = 0;
515 *a = *l = pt;
516 }
517
stuff1st_order_b(TOKENEXTRA ** tp,ENTROPY_CONTEXT * a,ENTROPY_CONTEXT * l,int type,VP8_COMP * cpi,MACROBLOCK * x)518 static void stuff1st_order_b
519 (
520 TOKENEXTRA **tp,
521 ENTROPY_CONTEXT *a,
522 ENTROPY_CONTEXT *l,
523 int type,
524 VP8_COMP *cpi,
525 MACROBLOCK *x
526 )
527 {
528 int pt; /* near block/prev token context index */
529 int band;
530 TOKENEXTRA *t = *tp; /* store tokens starting here */
531 VP8_COMBINEENTROPYCONTEXTS(pt, *a, *l);
532 band = type ? 0 : 1;
533 t->Token = DCT_EOB_TOKEN;
534 t->context_tree = cpi->common.fc.coef_probs [type] [band] [pt];
535 t->skip_eob_node = 0;
536 ++x->coef_counts [type] [band] [pt] [DCT_EOB_TOKEN];
537 ++t;
538 *tp = t;
539 pt = 0; /* 0 <-> all coeff data is zero */
540 *a = *l = pt;
541 }
542
543 static
stuff1st_order_buv(TOKENEXTRA ** tp,ENTROPY_CONTEXT * a,ENTROPY_CONTEXT * l,VP8_COMP * cpi,MACROBLOCK * x)544 void stuff1st_order_buv
545 (
546 TOKENEXTRA **tp,
547 ENTROPY_CONTEXT *a,
548 ENTROPY_CONTEXT *l,
549 VP8_COMP *cpi,
550 MACROBLOCK *x
551 )
552 {
553 int pt; /* near block/prev token context index */
554 TOKENEXTRA *t = *tp; /* store tokens starting here */
555 VP8_COMBINEENTROPYCONTEXTS(pt, *a, *l);
556
557 t->Token = DCT_EOB_TOKEN;
558 t->context_tree = cpi->common.fc.coef_probs [2] [0] [pt];
559 t->skip_eob_node = 0;
560 ++x->coef_counts[2] [0] [pt] [DCT_EOB_TOKEN];
561 ++t;
562 *tp = t;
563 pt = 0; /* 0 <-> all coeff data is zero */
564 *a = *l = pt;
565 }
566
vp8_stuff_mb(VP8_COMP * cpi,MACROBLOCK * x,TOKENEXTRA ** t)567 void vp8_stuff_mb(VP8_COMP *cpi, MACROBLOCK *x, TOKENEXTRA **t)
568 {
569 MACROBLOCKD *xd = &x->e_mbd;
570 ENTROPY_CONTEXT * A = (ENTROPY_CONTEXT *)xd->above_context;
571 ENTROPY_CONTEXT * L = (ENTROPY_CONTEXT *)xd->left_context;
572 int plane_type;
573 int b;
574 plane_type = 3;
575 if((xd->mode_info_context->mbmi.mode != B_PRED
576 && xd->mode_info_context->mbmi.mode != SPLITMV))
577 {
578 stuff2nd_order_b(t,
579 A + vp8_block2above[24], L + vp8_block2left[24], cpi, x);
580 plane_type = 0;
581 }
582
583 for (b = 0; b < 16; b++)
584 stuff1st_order_b(t,
585 A + vp8_block2above[b],
586 L + vp8_block2left[b], plane_type, cpi, x);
587
588 for (b = 16; b < 24; b++)
589 stuff1st_order_buv(t,
590 A + vp8_block2above[b],
591 L + vp8_block2left[b], cpi, x);
592
593 }
vp8_fix_contexts(MACROBLOCKD * x)594 void vp8_fix_contexts(MACROBLOCKD *x)
595 {
596 /* Clear entropy contexts for Y2 blocks */
597 if (x->mode_info_context->mbmi.mode != B_PRED && x->mode_info_context->mbmi.mode != SPLITMV)
598 {
599 vpx_memset(x->above_context, 0, sizeof(ENTROPY_CONTEXT_PLANES));
600 vpx_memset(x->left_context, 0, sizeof(ENTROPY_CONTEXT_PLANES));
601 }
602 else
603 {
604 vpx_memset(x->above_context, 0, sizeof(ENTROPY_CONTEXT_PLANES)-1);
605 vpx_memset(x->left_context, 0, sizeof(ENTROPY_CONTEXT_PLANES)-1);
606 }
607
608 }
609