media/libvpx/vp8/decoder/error_concealment.c@ac0c01689b40
media/libvpx/vp8/decoder/error_concealment.c
Thu, 15 Jan 2015 15:59:08 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Thu, 15 Jan 2015 15:59:08 +0100
- branch
- TOR_BUG_9701
- changeset 10
- ac0c01689b40
- permissions
- -rw-r--r--
Implement a real Private Browsing Mode condition by changing the API/ABI;
This solves Tor bug #9701, complying with disk avoidance documented in
https://www.torproject.org/projects/torbrowser/design/#disk-avoidance.
1 /*
2 * Copyright (c) 2011 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 */
11 #include <assert.h>
13 #include "error_concealment.h"
14 #include "onyxd_int.h"
15 #include "decodemv.h"
16 #include "vpx_mem/vpx_mem.h"
17 #include "vp8/common/findnearmv.h"
19 #define MIN(x,y) (((x)<(y))?(x):(y))
20 #define MAX(x,y) (((x)>(y))?(x):(y))
22 #define FLOOR(x,q) ((x) & -(1 << (q)))
24 #define NUM_NEIGHBORS 20
26 typedef struct ec_position
27 {
28 int row;
29 int col;
30 } EC_POS;
32 /*
33 * Regenerate the table in Matlab with:
34 * x = meshgrid((1:4), (1:4));
35 * y = meshgrid((1:4), (1:4))';
36 * W = round((1./(sqrt(x.^2 + y.^2))*2^7));
37 * W(1,1) = 0;
38 */
39 static const int weights_q7[5][5] = {
40 { 0, 128, 64, 43, 32 },
41 {128, 91, 57, 40, 31 },
42 { 64, 57, 45, 36, 29 },
43 { 43, 40, 36, 30, 26 },
44 { 32, 31, 29, 26, 23 }
45 };
47 int vp8_alloc_overlap_lists(VP8D_COMP *pbi)
48 {
49 if (pbi->overlaps != NULL)
50 {
51 vpx_free(pbi->overlaps);
52 pbi->overlaps = NULL;
53 }
55 pbi->overlaps = vpx_calloc(pbi->common.mb_rows * pbi->common.mb_cols,
56 sizeof(MB_OVERLAP));
58 if (pbi->overlaps == NULL)
59 return -1;
61 return 0;
62 }
64 void vp8_de_alloc_overlap_lists(VP8D_COMP *pbi)
65 {
66 vpx_free(pbi->overlaps);
67 pbi->overlaps = NULL;
68 }
70 /* Inserts a new overlap area value to the list of overlaps of a block */
71 static void assign_overlap(OVERLAP_NODE* overlaps,
72 union b_mode_info *bmi,
73 int overlap)
74 {
75 int i;
76 if (overlap <= 0)
77 return;
78 /* Find and assign to the next empty overlap node in the list of overlaps.
79 * Empty is defined as bmi == NULL */
80 for (i = 0; i < MAX_OVERLAPS; i++)
81 {
82 if (overlaps[i].bmi == NULL)
83 {
84 overlaps[i].bmi = bmi;
85 overlaps[i].overlap = overlap;
86 break;
87 }
88 }
89 }
91 /* Calculates the overlap area between two 4x4 squares, where the first
92 * square has its upper-left corner at (b1_row, b1_col) and the second
93 * square has its upper-left corner at (b2_row, b2_col). Doesn't
94 * properly handle squares which do not overlap.
95 */
96 static int block_overlap(int b1_row, int b1_col, int b2_row, int b2_col)
97 {
98 const int int_top = MAX(b1_row, b2_row); // top
99 const int int_left = MAX(b1_col, b2_col); // left
100 /* Since each block is 4x4 pixels, adding 4 (Q3) to the left/top edge
101 * gives us the right/bottom edge.
102 */
103 const int int_right = MIN(b1_col + (4<<3), b2_col + (4<<3)); // right
104 const int int_bottom = MIN(b1_row + (4<<3), b2_row + (4<<3)); // bottom
105 return (int_bottom - int_top) * (int_right - int_left);
106 }
108 /* Calculates the overlap area for all blocks in a macroblock at position
109 * (mb_row, mb_col) in macroblocks, which are being overlapped by a given
110 * overlapping block at position (new_row, new_col) (in pixels, Q3). The
111 * first block being overlapped in the macroblock has position (first_blk_row,
112 * first_blk_col) in blocks relative the upper-left corner of the image.
113 */
114 static void calculate_overlaps_mb(B_OVERLAP *b_overlaps, union b_mode_info *bmi,
115 int new_row, int new_col,
116 int mb_row, int mb_col,
117 int first_blk_row, int first_blk_col)
118 {
119 /* Find the blocks within this MB (defined by mb_row, mb_col) which are
120 * overlapped by bmi and calculate and assign overlap for each of those
121 * blocks. */
123 /* Block coordinates relative the upper-left block */
124 const int rel_ol_blk_row = first_blk_row - mb_row * 4;
125 const int rel_ol_blk_col = first_blk_col - mb_col * 4;
126 /* If the block partly overlaps any previous MB, these coordinates
127 * can be < 0. We don't want to access blocks in previous MBs.
128 */
129 const int blk_idx = MAX(rel_ol_blk_row,0) * 4 + MAX(rel_ol_blk_col,0);
130 /* Upper left overlapping block */
131 B_OVERLAP *b_ol_ul = &(b_overlaps[blk_idx]);
133 /* Calculate and assign overlaps for all blocks in this MB
134 * which the motion compensated block overlaps
135 */
136 /* Avoid calculating overlaps for blocks in later MBs */
137 int end_row = MIN(4 + mb_row * 4 - first_blk_row, 2);
138 int end_col = MIN(4 + mb_col * 4 - first_blk_col, 2);
139 int row, col;
141 /* Check if new_row and new_col are evenly divisible by 4 (Q3),
142 * and if so we shouldn't check neighboring blocks
143 */
144 if (new_row >= 0 && (new_row & 0x1F) == 0)
145 end_row = 1;
146 if (new_col >= 0 && (new_col & 0x1F) == 0)
147 end_col = 1;
149 /* Check if the overlapping block partly overlaps a previous MB
150 * and if so, we're overlapping fewer blocks in this MB.
151 */
152 if (new_row < (mb_row*16)<<3)
153 end_row = 1;
154 if (new_col < (mb_col*16)<<3)
155 end_col = 1;
157 for (row = 0; row < end_row; ++row)
158 {
159 for (col = 0; col < end_col; ++col)
160 {
161 /* input in Q3, result in Q6 */
162 const int overlap = block_overlap(new_row, new_col,
163 (((first_blk_row + row) *
164 4) << 3),
165 (((first_blk_col + col) *
166 4) << 3));
167 assign_overlap(b_ol_ul[row * 4 + col].overlaps, bmi, overlap);
168 }
169 }
170 }
172 void vp8_calculate_overlaps(MB_OVERLAP *overlap_ul,
173 int mb_rows, int mb_cols,
174 union b_mode_info *bmi,
175 int b_row, int b_col)
176 {
177 MB_OVERLAP *mb_overlap;
178 int row, col, rel_row, rel_col;
179 int new_row, new_col;
180 int end_row, end_col;
181 int overlap_b_row, overlap_b_col;
182 int overlap_mb_row, overlap_mb_col;
184 /* mb subpixel position */
185 row = (4 * b_row) << 3; /* Q3 */
186 col = (4 * b_col) << 3; /* Q3 */
188 /* reverse compensate for motion */
189 new_row = row - bmi->mv.as_mv.row;
190 new_col = col - bmi->mv.as_mv.col;
192 if (new_row >= ((16*mb_rows) << 3) || new_col >= ((16*mb_cols) << 3))
193 {
194 /* the new block ended up outside the frame */
195 return;
196 }
198 if (new_row <= (-4 << 3) || new_col <= (-4 << 3))
199 {
200 /* outside the frame */
201 return;
202 }
203 /* overlapping block's position in blocks */
204 overlap_b_row = FLOOR(new_row / 4, 3) >> 3;
205 overlap_b_col = FLOOR(new_col / 4, 3) >> 3;
207 /* overlapping block's MB position in MBs
208 * operations are done in Q3
209 */
210 overlap_mb_row = FLOOR((overlap_b_row << 3) / 4, 3) >> 3;
211 overlap_mb_col = FLOOR((overlap_b_col << 3) / 4, 3) >> 3;
213 end_row = MIN(mb_rows - overlap_mb_row, 2);
214 end_col = MIN(mb_cols - overlap_mb_col, 2);
216 /* Don't calculate overlap for MBs we don't overlap */
217 /* Check if the new block row starts at the last block row of the MB */
218 if (abs(new_row - ((16*overlap_mb_row) << 3)) < ((3*4) << 3))
219 end_row = 1;
220 /* Check if the new block col starts at the last block col of the MB */
221 if (abs(new_col - ((16*overlap_mb_col) << 3)) < ((3*4) << 3))
222 end_col = 1;
224 /* find the MB(s) this block is overlapping */
225 for (rel_row = 0; rel_row < end_row; ++rel_row)
226 {
227 for (rel_col = 0; rel_col < end_col; ++rel_col)
228 {
229 if (overlap_mb_row + rel_row < 0 ||
230 overlap_mb_col + rel_col < 0)
231 continue;
232 mb_overlap = overlap_ul + (overlap_mb_row + rel_row) * mb_cols +
233 overlap_mb_col + rel_col;
235 calculate_overlaps_mb(mb_overlap->overlaps, bmi,
236 new_row, new_col,
237 overlap_mb_row + rel_row,
238 overlap_mb_col + rel_col,
239 overlap_b_row + rel_row,
240 overlap_b_col + rel_col);
241 }
242 }
243 }
245 /* Estimates a motion vector given the overlapping blocks' motion vectors.
246 * Filters out all overlapping blocks which do not refer to the correct
247 * reference frame type.
248 */
249 static void estimate_mv(const OVERLAP_NODE *overlaps, union b_mode_info *bmi)
250 {
251 int i;
252 int overlap_sum = 0;
253 int row_acc = 0;
254 int col_acc = 0;
256 bmi->mv.as_int = 0;
257 for (i=0; i < MAX_OVERLAPS; ++i)
258 {
259 if (overlaps[i].bmi == NULL)
260 break;
261 col_acc += overlaps[i].overlap * overlaps[i].bmi->mv.as_mv.col;
262 row_acc += overlaps[i].overlap * overlaps[i].bmi->mv.as_mv.row;
263 overlap_sum += overlaps[i].overlap;
264 }
265 if (overlap_sum > 0)
266 {
267 /* Q9 / Q6 = Q3 */
268 bmi->mv.as_mv.col = col_acc / overlap_sum;
269 bmi->mv.as_mv.row = row_acc / overlap_sum;
270 }
271 else
272 {
273 bmi->mv.as_mv.col = 0;
274 bmi->mv.as_mv.row = 0;
275 }
276 }
278 /* Estimates all motion vectors for a macroblock given the lists of
279 * overlaps for each block. Decides whether or not the MVs must be clamped.
280 */
281 static void estimate_mb_mvs(const B_OVERLAP *block_overlaps,
282 MODE_INFO *mi,
283 int mb_to_left_edge,
284 int mb_to_right_edge,
285 int mb_to_top_edge,
286 int mb_to_bottom_edge)
287 {
288 int row, col;
289 int non_zero_count = 0;
290 MV * const filtered_mv = &(mi->mbmi.mv.as_mv);
291 union b_mode_info * const bmi = mi->bmi;
292 filtered_mv->col = 0;
293 filtered_mv->row = 0;
294 mi->mbmi.need_to_clamp_mvs = 0;
295 for (row = 0; row < 4; ++row)
296 {
297 int this_b_to_top_edge = mb_to_top_edge + ((row*4)<<3);
298 int this_b_to_bottom_edge = mb_to_bottom_edge - ((row*4)<<3);
299 for (col = 0; col < 4; ++col)
300 {
301 int i = row * 4 + col;
302 int this_b_to_left_edge = mb_to_left_edge + ((col*4)<<3);
303 int this_b_to_right_edge = mb_to_right_edge - ((col*4)<<3);
304 /* Estimate vectors for all blocks which are overlapped by this */
305 /* type. Interpolate/extrapolate the rest of the block's MVs */
306 estimate_mv(block_overlaps[i].overlaps, &(bmi[i]));
307 mi->mbmi.need_to_clamp_mvs |= vp8_check_mv_bounds(
308 &bmi[i].mv,
309 this_b_to_left_edge,
310 this_b_to_right_edge,
311 this_b_to_top_edge,
312 this_b_to_bottom_edge);
313 if (bmi[i].mv.as_int != 0)
314 {
315 ++non_zero_count;
316 filtered_mv->col += bmi[i].mv.as_mv.col;
317 filtered_mv->row += bmi[i].mv.as_mv.row;
318 }
319 }
320 }
321 if (non_zero_count > 0)
322 {
323 filtered_mv->col /= non_zero_count;
324 filtered_mv->row /= non_zero_count;
325 }
326 }
328 static void calc_prev_mb_overlaps(MB_OVERLAP *overlaps, MODE_INFO *prev_mi,
329 int mb_row, int mb_col,
330 int mb_rows, int mb_cols)
331 {
332 int sub_row;
333 int sub_col;
334 for (sub_row = 0; sub_row < 4; ++sub_row)
335 {
336 for (sub_col = 0; sub_col < 4; ++sub_col)
337 {
338 vp8_calculate_overlaps(
339 overlaps, mb_rows, mb_cols,
340 &(prev_mi->bmi[sub_row * 4 + sub_col]),
341 4 * mb_row + sub_row,
342 4 * mb_col + sub_col);
343 }
344 }
345 }
347 /* Estimate all missing motion vectors. This function does the same as the one
348 * above, but has different input arguments. */
349 static void estimate_missing_mvs(MB_OVERLAP *overlaps,
350 MODE_INFO *mi, MODE_INFO *prev_mi,
351 int mb_rows, int mb_cols,
352 unsigned int first_corrupt)
353 {
354 int mb_row, mb_col;
355 vpx_memset(overlaps, 0, sizeof(MB_OVERLAP) * mb_rows * mb_cols);
356 /* First calculate the overlaps for all blocks */
357 for (mb_row = 0; mb_row < mb_rows; ++mb_row)
358 {
359 for (mb_col = 0; mb_col < mb_cols; ++mb_col)
360 {
361 /* We're only able to use blocks referring to the last frame
362 * when extrapolating new vectors.
363 */
364 if (prev_mi->mbmi.ref_frame == LAST_FRAME)
365 {
366 calc_prev_mb_overlaps(overlaps, prev_mi,
367 mb_row, mb_col,
368 mb_rows, mb_cols);
369 }
370 ++prev_mi;
371 }
372 ++prev_mi;
373 }
375 mb_row = first_corrupt / mb_cols;
376 mb_col = first_corrupt - mb_row * mb_cols;
377 mi += mb_row*(mb_cols + 1) + mb_col;
378 /* Go through all macroblocks in the current image with missing MVs
379 * and calculate new MVs using the overlaps.
380 */
381 for (; mb_row < mb_rows; ++mb_row)
382 {
383 int mb_to_top_edge = -((mb_row * 16)) << 3;
384 int mb_to_bottom_edge = ((mb_rows - 1 - mb_row) * 16) << 3;
385 for (; mb_col < mb_cols; ++mb_col)
386 {
387 int mb_to_left_edge = -((mb_col * 16) << 3);
388 int mb_to_right_edge = ((mb_cols - 1 - mb_col) * 16) << 3;
389 const B_OVERLAP *block_overlaps =
390 overlaps[mb_row*mb_cols + mb_col].overlaps;
391 mi->mbmi.ref_frame = LAST_FRAME;
392 mi->mbmi.mode = SPLITMV;
393 mi->mbmi.uv_mode = DC_PRED;
394 mi->mbmi.partitioning = 3;
395 mi->mbmi.segment_id = 0;
396 estimate_mb_mvs(block_overlaps,
397 mi,
398 mb_to_left_edge,
399 mb_to_right_edge,
400 mb_to_top_edge,
401 mb_to_bottom_edge);
402 ++mi;
403 }
404 mb_col = 0;
405 ++mi;
406 }
407 }
409 void vp8_estimate_missing_mvs(VP8D_COMP *pbi)
410 {
411 VP8_COMMON * const pc = &pbi->common;
412 estimate_missing_mvs(pbi->overlaps,
413 pc->mi, pc->prev_mi,
414 pc->mb_rows, pc->mb_cols,
415 pbi->mvs_corrupt_from_mb);
416 }
418 static void assign_neighbor(EC_BLOCK *neighbor, MODE_INFO *mi, int block_idx)
419 {
420 assert(mi->mbmi.ref_frame < MAX_REF_FRAMES);
421 neighbor->ref_frame = mi->mbmi.ref_frame;
422 neighbor->mv = mi->bmi[block_idx].mv.as_mv;
423 }
425 /* Finds the neighboring blocks of a macroblocks. In the general case
426 * 20 blocks are found. If a fewer number of blocks are found due to
427 * image boundaries, those positions in the EC_BLOCK array are left "empty".
428 * The neighbors are enumerated with the upper-left neighbor as the first
429 * element, the second element refers to the neighbor to right of the previous
430 * neighbor, and so on. The last element refers to the neighbor below the first
431 * neighbor.
432 */
433 static void find_neighboring_blocks(MODE_INFO *mi,
434 EC_BLOCK *neighbors,
435 int mb_row, int mb_col,
436 int mb_rows, int mb_cols,
437 int mi_stride)
438 {
439 int i = 0;
440 int j;
441 if (mb_row > 0)
442 {
443 /* upper left */
444 if (mb_col > 0)
445 assign_neighbor(&neighbors[i], mi - mi_stride - 1, 15);
446 ++i;
447 /* above */
448 for (j = 12; j < 16; ++j, ++i)
449 assign_neighbor(&neighbors[i], mi - mi_stride, j);
450 }
451 else
452 i += 5;
453 if (mb_col < mb_cols - 1)
454 {
455 /* upper right */
456 if (mb_row > 0)
457 assign_neighbor(&neighbors[i], mi - mi_stride + 1, 12);
458 ++i;
459 /* right */
460 for (j = 0; j <= 12; j += 4, ++i)
461 assign_neighbor(&neighbors[i], mi + 1, j);
462 }
463 else
464 i += 5;
465 if (mb_row < mb_rows - 1)
466 {
467 /* lower right */
468 if (mb_col < mb_cols - 1)
469 assign_neighbor(&neighbors[i], mi + mi_stride + 1, 0);
470 ++i;
471 /* below */
472 for (j = 0; j < 4; ++j, ++i)
473 assign_neighbor(&neighbors[i], mi + mi_stride, j);
474 }
475 else
476 i += 5;
477 if (mb_col > 0)
478 {
479 /* lower left */
480 if (mb_row < mb_rows - 1)
481 assign_neighbor(&neighbors[i], mi + mi_stride - 1, 4);
482 ++i;
483 /* left */
484 for (j = 3; j < 16; j += 4, ++i)
485 {
486 assign_neighbor(&neighbors[i], mi - 1, j);
487 }
488 }
489 else
490 i += 5;
491 assert(i == 20);
492 }
494 /* Interpolates all motion vectors for a macroblock from the neighboring blocks'
495 * motion vectors.
496 */
497 static void interpolate_mvs(MACROBLOCKD *mb,
498 EC_BLOCK *neighbors,
499 MV_REFERENCE_FRAME dom_ref_frame)
500 {
501 int row, col, i;
502 MODE_INFO * const mi = mb->mode_info_context;
503 /* Table with the position of the neighboring blocks relative the position
504 * of the upper left block of the current MB. Starting with the upper left
505 * neighbor and going to the right.
506 */
507 const EC_POS neigh_pos[NUM_NEIGHBORS] = {
508 {-1,-1}, {-1,0}, {-1,1}, {-1,2}, {-1,3},
509 {-1,4}, {0,4}, {1,4}, {2,4}, {3,4},
510 {4,4}, {4,3}, {4,2}, {4,1}, {4,0},
511 {4,-1}, {3,-1}, {2,-1}, {1,-1}, {0,-1}
512 };
513 mi->mbmi.need_to_clamp_mvs = 0;
514 for (row = 0; row < 4; ++row)
515 {
516 int mb_to_top_edge = mb->mb_to_top_edge + ((row*4)<<3);
517 int mb_to_bottom_edge = mb->mb_to_bottom_edge - ((row*4)<<3);
518 for (col = 0; col < 4; ++col)
519 {
520 int mb_to_left_edge = mb->mb_to_left_edge + ((col*4)<<3);
521 int mb_to_right_edge = mb->mb_to_right_edge - ((col*4)<<3);
522 int w_sum = 0;
523 int mv_row_sum = 0;
524 int mv_col_sum = 0;
525 int_mv * const mv = &(mi->bmi[row*4 + col].mv);
526 mv->as_int = 0;
527 for (i = 0; i < NUM_NEIGHBORS; ++i)
528 {
529 /* Calculate the weighted sum of neighboring MVs referring
530 * to the dominant frame type.
531 */
532 const int w = weights_q7[abs(row - neigh_pos[i].row)]
533 [abs(col - neigh_pos[i].col)];
534 if (neighbors[i].ref_frame != dom_ref_frame)
535 continue;
536 w_sum += w;
537 /* Q7 * Q3 = Q10 */
538 mv_row_sum += w*neighbors[i].mv.row;
539 mv_col_sum += w*neighbors[i].mv.col;
540 }
541 if (w_sum > 0)
542 {
543 /* Avoid division by zero.
544 * Normalize with the sum of the coefficients
545 * Q3 = Q10 / Q7
546 */
547 mv->as_mv.row = mv_row_sum / w_sum;
548 mv->as_mv.col = mv_col_sum / w_sum;
549 mi->mbmi.need_to_clamp_mvs |= vp8_check_mv_bounds(
550 mv,
551 mb_to_left_edge,
552 mb_to_right_edge,
553 mb_to_top_edge,
554 mb_to_bottom_edge);
555 }
556 }
557 }
558 }
560 void vp8_interpolate_motion(MACROBLOCKD *mb,
561 int mb_row, int mb_col,
562 int mb_rows, int mb_cols,
563 int mi_stride)
564 {
565 /* Find relevant neighboring blocks */
566 EC_BLOCK neighbors[NUM_NEIGHBORS];
567 int i;
568 /* Initialize the array. MAX_REF_FRAMES is interpreted as "doesn't exist" */
569 for (i = 0; i < NUM_NEIGHBORS; ++i)
570 {
571 neighbors[i].ref_frame = MAX_REF_FRAMES;
572 neighbors[i].mv.row = neighbors[i].mv.col = 0;
573 }
574 find_neighboring_blocks(mb->mode_info_context,
575 neighbors,
576 mb_row, mb_col,
577 mb_rows, mb_cols,
578 mb->mode_info_stride);
579 /* Interpolate MVs for the missing blocks from the surrounding
580 * blocks which refer to the last frame. */
581 interpolate_mvs(mb, neighbors, LAST_FRAME);
583 mb->mode_info_context->mbmi.ref_frame = LAST_FRAME;
584 mb->mode_info_context->mbmi.mode = SPLITMV;
585 mb->mode_info_context->mbmi.uv_mode = DC_PRED;
586 mb->mode_info_context->mbmi.partitioning = 3;
587 mb->mode_info_context->mbmi.segment_id = 0;
588 }
590 void vp8_conceal_corrupt_mb(MACROBLOCKD *xd)
591 {
592 /* This macroblock has corrupt residual, use the motion compensated
593 image (predictor) for concealment */
595 /* The build predictor functions now output directly into the dst buffer,
596 * so the copies are no longer necessary */
598 }
