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