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