2 * Copyright (c) 2010 The WebM project authors. All Rights Reserved.
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.
12 #include "./vp9_rtcd.h"
13 #include "./vpx_config.h"
15 #include "vpx_mem/vpx_mem.h"
17 #include "vp9/common/vp9_idct.h"
18 #include "vp9/common/vp9_reconinter.h"
19 #include "vp9/common/vp9_reconintra.h"
20 #include "vp9/common/vp9_systemdependent.h"
22 #include "vp9/encoder/vp9_encodemb.h"
23 #include "vp9/encoder/vp9_quantize.h"
24 #include "vp9/encoder/vp9_rdopt.h"
25 #include "vp9/encoder/vp9_tokenize.h"
28 ENTROPY_CONTEXT ta[MAX_MB_PLANE][16];
29 ENTROPY_CONTEXT tl[MAX_MB_PLANE][16];
32 struct encode_b_args {
34 struct optimize_ctx *ctx;
38 void vp9_subtract_block_c(int rows, int cols,
39 int16_t *diff, ptrdiff_t diff_stride,
40 const uint8_t *src, ptrdiff_t src_stride,
41 const uint8_t *pred, ptrdiff_t pred_stride) {
44 for (r = 0; r < rows; r++) {
45 for (c = 0; c < cols; c++)
46 diff[c] = src[c] - pred[c];
54 void vp9_subtract_plane(MACROBLOCK *x, BLOCK_SIZE bsize, int plane) {
55 struct macroblock_plane *const p = &x->plane[plane];
56 const struct macroblockd_plane *const pd = &x->e_mbd.plane[plane];
57 const BLOCK_SIZE plane_bsize = get_plane_block_size(bsize, pd);
58 const int bw = 4 * num_4x4_blocks_wide_lookup[plane_bsize];
59 const int bh = 4 * num_4x4_blocks_high_lookup[plane_bsize];
61 vp9_subtract_block(bh, bw, p->src_diff, bw, p->src.buf, p->src.stride,
62 pd->dst.buf, pd->dst.stride);
65 #define RDTRUNC(RM, DM, R, D) ((128 + (R) * (RM)) & 0xFF)
67 typedef struct vp9_token_state {
75 // TODO(jimbankoski): experiment to find optimal RD numbers.
76 static const int plane_rd_mult[PLANE_TYPES] = { 4, 2 };
78 #define UPDATE_RD_COST()\
80 rd_cost0 = RDCOST(rdmult, rddiv, rate0, error0);\
81 rd_cost1 = RDCOST(rdmult, rddiv, rate1, error1);\
82 if (rd_cost0 == rd_cost1) {\
83 rd_cost0 = RDTRUNC(rdmult, rddiv, rate0, error0);\
84 rd_cost1 = RDTRUNC(rdmult, rddiv, rate1, error1);\
88 // This function is a place holder for now but may ultimately need
89 // to scan previous tokens to work out the correct context.
90 static int trellis_get_coeff_context(const int16_t *scan,
93 uint8_t *token_cache) {
94 int bak = token_cache[scan[idx]], pt;
95 token_cache[scan[idx]] = vp9_pt_energy_class[token];
96 pt = get_coef_context(nb, token_cache, idx + 1);
97 token_cache[scan[idx]] = bak;
101 static int optimize_b(MACROBLOCK *mb, int plane, int block,
102 BLOCK_SIZE plane_bsize, TX_SIZE tx_size, int ctx) {
103 MACROBLOCKD *const xd = &mb->e_mbd;
104 struct macroblock_plane *const p = &mb->plane[plane];
105 struct macroblockd_plane *const pd = &xd->plane[plane];
106 const int ref = is_inter_block(&xd->mi[0]->mbmi);
107 vp9_token_state tokens[1025][2];
108 unsigned best_index[1025][2];
109 uint8_t token_cache[1024];
110 const int16_t *const coeff = BLOCK_OFFSET(mb->plane[plane].coeff, block);
111 int16_t *const qcoeff = BLOCK_OFFSET(p->qcoeff, block);
112 int16_t *const dqcoeff = BLOCK_OFFSET(pd->dqcoeff, block);
113 const int eob = p->eobs[block];
114 const PLANE_TYPE type = pd->plane_type;
115 const int default_eob = 16 << (tx_size << 1);
116 const int mul = 1 + (tx_size == TX_32X32);
117 const int16_t *dequant_ptr = pd->dequant;
118 const uint8_t *const band_translate = get_band_translate(tx_size);
119 const scan_order *const so = get_scan(xd, tx_size, type, block);
120 const int16_t *const scan = so->scan;
121 const int16_t *const nb = so->neighbors;
122 int next = eob, sz = 0;
123 int64_t rdmult = mb->rdmult * plane_rd_mult[type], rddiv = mb->rddiv;
124 int64_t rd_cost0, rd_cost1;
125 int rate0, rate1, error0, error1, t0, t1;
126 int best, band, pt, i, final_eob;
128 assert((!type && !plane) || (type && plane));
129 assert(eob <= default_eob);
131 /* Now set up a Viterbi trellis to evaluate alternative roundings. */
133 rdmult = (rdmult * 9) >> 4;
135 /* Initialize the sentinel node of the trellis. */
136 tokens[eob][0].rate = 0;
137 tokens[eob][0].error = 0;
138 tokens[eob][0].next = default_eob;
139 tokens[eob][0].token = EOB_TOKEN;
140 tokens[eob][0].qc = 0;
141 tokens[eob][1] = tokens[eob][0];
143 for (i = 0; i < eob; i++)
144 token_cache[scan[i]] =
145 vp9_pt_energy_class[vp9_dct_value_tokens_ptr[qcoeff[scan[i]]].token];
147 for (i = eob; i-- > 0;) {
148 int base_bits, d2, dx;
149 const int rc = scan[i];
151 /* Only add a trellis state for non-zero coefficients. */
154 error0 = tokens[next][0].error;
155 error1 = tokens[next][1].error;
156 /* Evaluate the first possibility for this state. */
157 rate0 = tokens[next][0].rate;
158 rate1 = tokens[next][1].rate;
159 t0 = (vp9_dct_value_tokens_ptr + x)->token;
160 /* Consider both possible successor states. */
161 if (next < default_eob) {
162 band = band_translate[i + 1];
163 pt = trellis_get_coeff_context(scan, nb, i, t0, token_cache);
164 rate0 += mb->token_costs[tx_size][type][ref][band][0][pt]
165 [tokens[next][0].token];
166 rate1 += mb->token_costs[tx_size][type][ref][band][0][pt]
167 [tokens[next][1].token];
170 /* And pick the best. */
171 best = rd_cost1 < rd_cost0;
172 base_bits = vp9_dct_value_cost_ptr[x];
173 dx = mul * (dqcoeff[rc] - coeff[rc]);
175 tokens[i][0].rate = base_bits + (best ? rate1 : rate0);
176 tokens[i][0].error = d2 + (best ? error1 : error0);
177 tokens[i][0].next = next;
178 tokens[i][0].token = t0;
180 best_index[i][0] = best;
182 /* Evaluate the second possibility for this state. */
183 rate0 = tokens[next][0].rate;
184 rate1 = tokens[next][1].rate;
186 if ((abs(x) * dequant_ptr[rc != 0] > abs(coeff[rc]) * mul) &&
187 (abs(x) * dequant_ptr[rc != 0] < abs(coeff[rc]) * mul +
188 dequant_ptr[rc != 0]))
198 /* Consider both possible successor states. */
200 /* If we reduced this coefficient to zero, check to see if
201 * we need to move the EOB back here.
203 t0 = tokens[next][0].token == EOB_TOKEN ? EOB_TOKEN : ZERO_TOKEN;
204 t1 = tokens[next][1].token == EOB_TOKEN ? EOB_TOKEN : ZERO_TOKEN;
206 t0 = t1 = (vp9_dct_value_tokens_ptr + x)->token;
208 if (next < default_eob) {
209 band = band_translate[i + 1];
210 if (t0 != EOB_TOKEN) {
211 pt = trellis_get_coeff_context(scan, nb, i, t0, token_cache);
212 rate0 += mb->token_costs[tx_size][type][ref][band][!x][pt]
213 [tokens[next][0].token];
215 if (t1 != EOB_TOKEN) {
216 pt = trellis_get_coeff_context(scan, nb, i, t1, token_cache);
217 rate1 += mb->token_costs[tx_size][type][ref][band][!x][pt]
218 [tokens[next][1].token];
223 /* And pick the best. */
224 best = rd_cost1 < rd_cost0;
225 base_bits = vp9_dct_value_cost_ptr[x];
228 dx -= (dequant_ptr[rc != 0] + sz) ^ sz;
231 tokens[i][1].rate = base_bits + (best ? rate1 : rate0);
232 tokens[i][1].error = d2 + (best ? error1 : error0);
233 tokens[i][1].next = next;
234 tokens[i][1].token = best ? t1 : t0;
236 best_index[i][1] = best;
237 /* Finally, make this the new head of the trellis. */
240 /* There's no choice to make for a zero coefficient, so we don't
241 * add a new trellis node, but we do need to update the costs.
243 band = band_translate[i + 1];
244 t0 = tokens[next][0].token;
245 t1 = tokens[next][1].token;
246 /* Update the cost of each path if we're past the EOB token. */
247 if (t0 != EOB_TOKEN) {
248 tokens[next][0].rate +=
249 mb->token_costs[tx_size][type][ref][band][1][0][t0];
250 tokens[next][0].token = ZERO_TOKEN;
252 if (t1 != EOB_TOKEN) {
253 tokens[next][1].rate +=
254 mb->token_costs[tx_size][type][ref][band][1][0][t1];
255 tokens[next][1].token = ZERO_TOKEN;
257 best_index[i][0] = best_index[i][1] = 0;
258 /* Don't update next, because we didn't add a new node. */
262 /* Now pick the best path through the whole trellis. */
263 band = band_translate[i + 1];
264 rate0 = tokens[next][0].rate;
265 rate1 = tokens[next][1].rate;
266 error0 = tokens[next][0].error;
267 error1 = tokens[next][1].error;
268 t0 = tokens[next][0].token;
269 t1 = tokens[next][1].token;
270 rate0 += mb->token_costs[tx_size][type][ref][band][0][ctx][t0];
271 rate1 += mb->token_costs[tx_size][type][ref][band][0][ctx][t1];
273 best = rd_cost1 < rd_cost0;
275 vpx_memset(qcoeff, 0, sizeof(*qcoeff) * (16 << (tx_size * 2)));
276 vpx_memset(dqcoeff, 0, sizeof(*dqcoeff) * (16 << (tx_size * 2)));
277 for (i = next; i < eob; i = next) {
278 const int x = tokens[i][best].qc;
279 const int rc = scan[i];
285 dqcoeff[rc] = (x * dequant_ptr[rc != 0]) / mul;
287 next = tokens[i][best].next;
288 best = best_index[i][best];
292 mb->plane[plane].eobs[block] = final_eob;
296 static INLINE void fdct32x32(int rd_transform,
297 const int16_t *src, int16_t *dst, int src_stride) {
299 vp9_fdct32x32_rd(src, dst, src_stride);
301 vp9_fdct32x32(src, dst, src_stride);
304 void vp9_xform_quant(MACROBLOCK *x, int plane, int block,
305 BLOCK_SIZE plane_bsize, TX_SIZE tx_size) {
306 MACROBLOCKD *const xd = &x->e_mbd;
307 const struct macroblock_plane *const p = &x->plane[plane];
308 const struct macroblockd_plane *const pd = &xd->plane[plane];
309 const scan_order *const scan_order = &vp9_default_scan_orders[tx_size];
310 int16_t *const coeff = BLOCK_OFFSET(p->coeff, block);
311 int16_t *const qcoeff = BLOCK_OFFSET(p->qcoeff, block);
312 int16_t *const dqcoeff = BLOCK_OFFSET(pd->dqcoeff, block);
313 uint16_t *const eob = &p->eobs[block];
314 const int diff_stride = 4 * num_4x4_blocks_wide_lookup[plane_bsize];
316 const int16_t *src_diff;
317 txfrm_block_to_raster_xy(plane_bsize, tx_size, block, &i, &j);
318 src_diff = &p->src_diff[4 * (j * diff_stride + i)];
322 fdct32x32(x->use_lp32x32fdct, src_diff, coeff, diff_stride);
323 vp9_quantize_b_32x32(coeff, 1024, x->skip_block, p->zbin, p->round,
324 p->quant, p->quant_shift, qcoeff, dqcoeff,
325 pd->dequant, p->zbin_extra, eob, scan_order->scan,
329 vp9_fdct16x16(src_diff, coeff, diff_stride);
330 vp9_quantize_b(coeff, 256, x->skip_block, p->zbin, p->round,
331 p->quant, p->quant_shift, qcoeff, dqcoeff,
332 pd->dequant, p->zbin_extra, eob,
333 scan_order->scan, scan_order->iscan);
336 vp9_fdct8x8(src_diff, coeff, diff_stride);
337 vp9_quantize_b(coeff, 64, x->skip_block, p->zbin, p->round,
338 p->quant, p->quant_shift, qcoeff, dqcoeff,
339 pd->dequant, p->zbin_extra, eob,
340 scan_order->scan, scan_order->iscan);
343 x->fwd_txm4x4(src_diff, coeff, diff_stride);
344 vp9_quantize_b(coeff, 16, x->skip_block, p->zbin, p->round,
345 p->quant, p->quant_shift, qcoeff, dqcoeff,
346 pd->dequant, p->zbin_extra, eob,
347 scan_order->scan, scan_order->iscan);
354 static void encode_block(int plane, int block, BLOCK_SIZE plane_bsize,
355 TX_SIZE tx_size, void *arg) {
356 struct encode_b_args *const args = arg;
357 MACROBLOCK *const x = args->x;
358 MACROBLOCKD *const xd = &x->e_mbd;
359 struct optimize_ctx *const ctx = args->ctx;
360 struct macroblock_plane *const p = &x->plane[plane];
361 struct macroblockd_plane *const pd = &xd->plane[plane];
362 int16_t *const dqcoeff = BLOCK_OFFSET(pd->dqcoeff, block);
365 ENTROPY_CONTEXT *a, *l;
366 txfrm_block_to_raster_xy(plane_bsize, tx_size, block, &i, &j);
367 dst = &pd->dst.buf[4 * j * pd->dst.stride + 4 * i];
368 a = &ctx->ta[plane][i];
369 l = &ctx->tl[plane][j];
371 // TODO(jingning): per transformed block zero forcing only enabled for
372 // luma component. will integrate chroma components as well.
373 if (x->zcoeff_blk[tx_size][block] && plane == 0) {
380 vp9_xform_quant(x, plane, block, plane_bsize, tx_size);
382 if (x->optimize && (!x->skip_recode || !x->skip_optimize)) {
383 const int ctx = combine_entropy_contexts(*a, *l);
384 *a = *l = optimize_b(x, plane, block, plane_bsize, tx_size, ctx) > 0;
386 *a = *l = p->eobs[block] > 0;
392 if (x->skip_encode || p->eobs[block] == 0)
397 vp9_idct32x32_add(dqcoeff, dst, pd->dst.stride, p->eobs[block]);
400 vp9_idct16x16_add(dqcoeff, dst, pd->dst.stride, p->eobs[block]);
403 vp9_idct8x8_add(dqcoeff, dst, pd->dst.stride, p->eobs[block]);
406 // this is like vp9_short_idct4x4 but has a special case around eob<=1
407 // which is significant (not just an optimization) for the lossless
409 xd->itxm_add(dqcoeff, dst, pd->dst.stride, p->eobs[block]);
412 assert(0 && "Invalid transform size");
416 static void encode_block_pass1(int plane, int block, BLOCK_SIZE plane_bsize,
417 TX_SIZE tx_size, void *arg) {
418 MACROBLOCK *const x = (MACROBLOCK *)arg;
419 MACROBLOCKD *const xd = &x->e_mbd;
420 struct macroblock_plane *const p = &x->plane[plane];
421 struct macroblockd_plane *const pd = &xd->plane[plane];
422 int16_t *const dqcoeff = BLOCK_OFFSET(pd->dqcoeff, block);
425 txfrm_block_to_raster_xy(plane_bsize, tx_size, block, &i, &j);
426 dst = &pd->dst.buf[4 * j * pd->dst.stride + 4 * i];
428 vp9_xform_quant(x, plane, block, plane_bsize, tx_size);
430 if (p->eobs[block] > 0)
431 xd->itxm_add(dqcoeff, dst, pd->dst.stride, p->eobs[block]);
434 void vp9_encode_sby_pass1(MACROBLOCK *x, BLOCK_SIZE bsize) {
435 vp9_subtract_plane(x, bsize, 0);
436 vp9_foreach_transformed_block_in_plane(&x->e_mbd, bsize, 0,
437 encode_block_pass1, x);
440 void vp9_encode_sb(MACROBLOCK *x, BLOCK_SIZE bsize) {
441 MACROBLOCKD *const xd = &x->e_mbd;
442 struct optimize_ctx ctx;
443 MB_MODE_INFO *mbmi = &xd->mi[0]->mbmi;
444 struct encode_b_args arg = {x, &ctx, &mbmi->skip};
447 for (plane = 0; plane < MAX_MB_PLANE; ++plane) {
449 vp9_subtract_plane(x, bsize, plane);
451 if (x->optimize && (!x->skip_recode || !x->skip_optimize)) {
452 const struct macroblockd_plane* const pd = &xd->plane[plane];
453 const TX_SIZE tx_size = plane ? get_uv_tx_size(mbmi) : mbmi->tx_size;
454 vp9_get_entropy_contexts(bsize, tx_size, pd,
455 ctx.ta[plane], ctx.tl[plane]);
458 vp9_foreach_transformed_block_in_plane(xd, bsize, plane, encode_block,
463 static void encode_block_intra(int plane, int block, BLOCK_SIZE plane_bsize,
464 TX_SIZE tx_size, void *arg) {
465 struct encode_b_args* const args = arg;
466 MACROBLOCK *const x = args->x;
467 MACROBLOCKD *const xd = &x->e_mbd;
468 MB_MODE_INFO *mbmi = &xd->mi[0]->mbmi;
469 struct macroblock_plane *const p = &x->plane[plane];
470 struct macroblockd_plane *const pd = &xd->plane[plane];
471 int16_t *coeff = BLOCK_OFFSET(p->coeff, block);
472 int16_t *qcoeff = BLOCK_OFFSET(p->qcoeff, block);
473 int16_t *dqcoeff = BLOCK_OFFSET(pd->dqcoeff, block);
474 const scan_order *scan_order;
476 PREDICTION_MODE mode;
477 const int bwl = b_width_log2(plane_bsize);
478 const int diff_stride = 4 * (1 << bwl);
481 uint16_t *eob = &p->eobs[block];
482 const int src_stride = p->src.stride;
483 const int dst_stride = pd->dst.stride;
485 txfrm_block_to_raster_xy(plane_bsize, tx_size, block, &i, &j);
486 dst = &pd->dst.buf[4 * (j * dst_stride + i)];
487 src = &p->src.buf[4 * (j * src_stride + i)];
488 src_diff = &p->src_diff[4 * (j * diff_stride + i)];
492 scan_order = &vp9_default_scan_orders[TX_32X32];
493 mode = plane == 0 ? mbmi->mode : mbmi->uv_mode;
494 vp9_predict_intra_block(xd, block >> 6, bwl, TX_32X32, mode,
495 x->skip_encode ? src : dst,
496 x->skip_encode ? src_stride : dst_stride,
497 dst, dst_stride, i, j, plane);
498 if (!x->skip_recode) {
499 vp9_subtract_block(32, 32, src_diff, diff_stride,
500 src, src_stride, dst, dst_stride);
501 fdct32x32(x->use_lp32x32fdct, src_diff, coeff, diff_stride);
502 vp9_quantize_b_32x32(coeff, 1024, x->skip_block, p->zbin, p->round,
503 p->quant, p->quant_shift, qcoeff, dqcoeff,
504 pd->dequant, p->zbin_extra, eob, scan_order->scan,
507 if (!x->skip_encode && *eob)
508 vp9_idct32x32_add(dqcoeff, dst, dst_stride, *eob);
511 tx_type = get_tx_type(pd->plane_type, xd);
512 scan_order = &vp9_scan_orders[TX_16X16][tx_type];
513 mode = plane == 0 ? mbmi->mode : mbmi->uv_mode;
514 vp9_predict_intra_block(xd, block >> 4, bwl, TX_16X16, mode,
515 x->skip_encode ? src : dst,
516 x->skip_encode ? src_stride : dst_stride,
517 dst, dst_stride, i, j, plane);
518 if (!x->skip_recode) {
519 vp9_subtract_block(16, 16, src_diff, diff_stride,
520 src, src_stride, dst, dst_stride);
521 vp9_fht16x16(src_diff, coeff, diff_stride, tx_type);
522 vp9_quantize_b(coeff, 256, x->skip_block, p->zbin, p->round,
523 p->quant, p->quant_shift, qcoeff, dqcoeff,
524 pd->dequant, p->zbin_extra, eob, scan_order->scan,
527 if (!x->skip_encode && *eob)
528 vp9_iht16x16_add(tx_type, dqcoeff, dst, dst_stride, *eob);
531 tx_type = get_tx_type(pd->plane_type, xd);
532 scan_order = &vp9_scan_orders[TX_8X8][tx_type];
533 mode = plane == 0 ? mbmi->mode : mbmi->uv_mode;
534 vp9_predict_intra_block(xd, block >> 2, bwl, TX_8X8, mode,
535 x->skip_encode ? src : dst,
536 x->skip_encode ? src_stride : dst_stride,
537 dst, dst_stride, i, j, plane);
538 if (!x->skip_recode) {
539 vp9_subtract_block(8, 8, src_diff, diff_stride,
540 src, src_stride, dst, dst_stride);
541 vp9_fht8x8(src_diff, coeff, diff_stride, tx_type);
542 vp9_quantize_b(coeff, 64, x->skip_block, p->zbin, p->round, p->quant,
543 p->quant_shift, qcoeff, dqcoeff,
544 pd->dequant, p->zbin_extra, eob, scan_order->scan,
547 if (!x->skip_encode && *eob)
548 vp9_iht8x8_add(tx_type, dqcoeff, dst, dst_stride, *eob);
551 tx_type = get_tx_type_4x4(pd->plane_type, xd, block);
552 scan_order = &vp9_scan_orders[TX_4X4][tx_type];
553 mode = plane == 0 ? get_y_mode(xd->mi[0], block) : mbmi->uv_mode;
554 vp9_predict_intra_block(xd, block, bwl, TX_4X4, mode,
555 x->skip_encode ? src : dst,
556 x->skip_encode ? src_stride : dst_stride,
557 dst, dst_stride, i, j, plane);
559 if (!x->skip_recode) {
560 vp9_subtract_block(4, 4, src_diff, diff_stride,
561 src, src_stride, dst, dst_stride);
562 if (tx_type != DCT_DCT)
563 vp9_fht4x4(src_diff, coeff, diff_stride, tx_type);
565 x->fwd_txm4x4(src_diff, coeff, diff_stride);
566 vp9_quantize_b(coeff, 16, x->skip_block, p->zbin, p->round, p->quant,
567 p->quant_shift, qcoeff, dqcoeff,
568 pd->dequant, p->zbin_extra, eob, scan_order->scan,
572 if (!x->skip_encode && *eob) {
573 if (tx_type == DCT_DCT)
574 // this is like vp9_short_idct4x4 but has a special case around eob<=1
575 // which is significant (not just an optimization) for the lossless
577 xd->itxm_add(dqcoeff, dst, dst_stride, *eob);
579 vp9_iht4x4_16_add(dqcoeff, dst, dst_stride, tx_type);
589 void vp9_encode_block_intra(MACROBLOCK *x, int plane, int block,
590 BLOCK_SIZE plane_bsize, TX_SIZE tx_size,
591 unsigned char *skip) {
592 struct encode_b_args arg = {x, NULL, skip};
593 encode_block_intra(plane, block, plane_bsize, tx_size, &arg);
597 void vp9_encode_intra_block_plane(MACROBLOCK *x, BLOCK_SIZE bsize, int plane) {
598 const MACROBLOCKD *const xd = &x->e_mbd;
599 struct encode_b_args arg = {x, NULL, &xd->mi[0]->mbmi.skip};
601 vp9_foreach_transformed_block_in_plane(xd, bsize, plane, encode_block_intra,