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