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
26void vp8_stuff_mb(VP8_COMP *cpi, MACROBLOCK *x, TOKENEXTRA **t) ;
27void vp8_fix_contexts(MACROBLOCKD *x);
28
29#include "dct_value_tokens.h"
30#include "dct_value_cost.h"
31
32const TOKENVALUE *const vp8_dct_value_tokens_ptr = dct_value_tokens +
33        DCT_MAX_VALUE;
34const short *const vp8_dct_value_cost_ptr = dct_value_cost + DCT_MAX_VALUE;
35
36#if 0
37int skip_true_count = 0;
38int skip_false_count = 0;
39#endif
40
41/* function used to generate dct_value_tokens and dct_value_cost tables */
42/*
43static 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
103static 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
191static 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
365static 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
383void 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
422void init_context_counters(void)
423{
424    vpx_memset(context_counters, 0, sizeof(context_counters));
425}
426
427void 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
494static 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
518static 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
543static
544void 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
567void 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}
594void 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