/* * Copyright © 2020, VideoLAN and dav1d authors * Copyright © 2020, Two Orioles, LLC * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * 1. Redistributions of source code must retain the above copyright notice, this *    list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright notice, *    this list of conditions and the following disclaimer in the documentation *    and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #include "config.h" #include <limits.h>#include <stdlib.h> #include "dav1d/common.h" #include "common/intops.h" #include "src/env.h"#include "src/refmvs.h" static void add_spatial_candidate(refmvs_candidate *const mvstack, int *const cnt,                                  const int weight, const refmvs_block *const b,                                  const union refmvs_refpair ref, const mv gmv[2],                                  int *const have_newmv_match,                                  int *const have_refmv_match){    if (b->mv.mv[0].n == INVALID_MV) return; // intra block, no intrabc     if (ref.ref[1] == -1) {        for (int n = 0; n < 2; n++) {            if (b->ref.ref[n] == ref.ref[0]) {                const mv cand_mv = ((b->mf & 1) && gmv[0].n != INVALID_MV) ?                                   gmv[0] : b->mv.mv[n];                 const int last = *cnt;                for (int m = 0; m < last; m++)                    if (mvstack[m].mv.mv[0].n == cand_mv.n) {                        mvstack[m].weight += weight;                        *have_refmv_match = 1;                        *have_newmv_match |= b->mf >> 1;                        return;                    }                 if (last < 8) {                    mvstack[last].mv.mv[0] = cand_mv;                    mvstack[last].weight = weight;                    *cnt = last + 1;                }                *have_refmv_match = 1;                *have_newmv_match |= b->mf >> 1;                return;            }        }    } else if (b->ref.pair == ref.pair) {        const refmvs_mvpair cand_mv = { .mv = {            [0] = ((b->mf & 1) && gmv[0].n != INVALID_MV) ? gmv[0] : b->mv.mv[0],            [1] = ((b->mf & 1) && gmv[1].n != INVALID_MV) ? gmv[1] : b->mv.mv[1],        }};         const int last = *cnt;        for (int n = 0; n < last; n++)            if (mvstack[n].mv.n == cand_mv.n) {                mvstack[n].weight += weight;                *have_refmv_match = 1;                *have_newmv_match |= b->mf >> 1;                return;            }         if (last < 8) {            mvstack[last].mv = cand_mv;            mvstack[last].weight = weight;            *cnt = last + 1;        }        *have_refmv_match = 1;        *have_newmv_match |= b->mf >> 1;    }} static int scan_row(refmvs_candidate *const mvstack, int *const cnt,                    const union refmvs_refpair ref, const mv gmv[2],                    const refmvs_block *b, const int bw4, const int w4,                    const int max_rows, const int step,                    int *const have_newmv_match, int *const have_refmv_match){    const refmvs_block *cand_b = b;    const enum BlockSize first_cand_bs = cand_b->bs;    const uint8_t *const first_cand_b_dim = dav1d_block_dimensions[first_cand_bs];    int cand_bw4 = first_cand_b_dim[0];    int len = imax(step, imin(bw4, cand_bw4));     if (bw4 <= cand_bw4) {        // FIXME weight can be higher for odd blocks (bx4 & 1), but then the        // position of the first block has to be odd already, i.e. not just        // for row_offset=-3/-5        // FIXME why can this not be cand_bw4?        const int weight = bw4 == 1 ? 2 :                           imax(2, imin(2 * max_rows, first_cand_b_dim[1]));        add_spatial_candidate(mvstack, cnt, len * weight, cand_b, ref, gmv,                              have_newmv_match, have_refmv_match);        return weight >> 1;    }     for (int x = 0;;) {        // FIXME if we overhang above, we could fill a bitmask so we don't have        // to repeat the add_spatial_candidate() for the next row, but just increase        // the weight here        add_spatial_candidate(mvstack, cnt, len * 2, cand_b, ref, gmv,                              have_newmv_match, have_refmv_match);        x += len;        if (x >= w4) return 1;        cand_b = &b[x];        cand_bw4 = dav1d_block_dimensions[cand_b->bs][0];        assert(cand_bw4 < bw4);        len = imax(step, cand_bw4);    }} static int scan_col(refmvs_candidate *const mvstack, int *const cnt,                    const union refmvs_refpair ref, const mv gmv[2],                    /*const*/ refmvs_block *const *b, const int bh4, const int h4,                    const int bx4, const int max_cols, const int step,                    int *const have_newmv_match, int *const have_refmv_match){    const refmvs_block *cand_b = &b[0][bx4];    const enum BlockSize first_cand_bs = cand_b->bs;    const uint8_t *const first_cand_b_dim = dav1d_block_dimensions[first_cand_bs];    int cand_bh4 = first_cand_b_dim[1];    int len = imax(step, imin(bh4, cand_bh4));     if (bh4 <= cand_bh4) {        // FIXME weight can be higher for odd blocks (by4 & 1), but then the        // position of the first block has to be odd already, i.e. not just        // for col_offset=-3/-5        // FIXME why can this not be cand_bh4?        const int weight = bh4 == 1 ? 2 :                           imax(2, imin(2 * max_cols, first_cand_b_dim[0]));        add_spatial_candidate(mvstack, cnt, len * weight, cand_b, ref, gmv,                            have_newmv_match, have_refmv_match);        return weight >> 1;    }     for (int y = 0;;) {        // FIXME if we overhang above, we could fill a bitmask so we don't have        // to repeat the add_spatial_candidate() for the next row, but just increase        // the weight here        add_spatial_candidate(mvstack, cnt, len * 2, cand_b, ref, gmv,                              have_newmv_match, have_refmv_match);        y += len;        if (y >= h4) return 1;        cand_b = &b[y][bx4];        cand_bh4 = dav1d_block_dimensions[cand_b->bs][1];        assert(cand_bh4 < bh4);        len = imax(step, cand_bh4);    }} static inline union mv mv_projection(const union mv mv, const int num, const int den) {    static const uint16_t div_mult[32] = {           0, 16384, 8192, 5461, 4096, 3276, 2730, 2340,        2048,  1820, 1638, 1489, 1365, 1260, 1170, 1092,        1024,   963,  910,  862,  819,  780,  744,  712,         682,   655,  630,  606,  585,  564,  546,  528    };    assert(den > 0 && den < 32);    assert(num > -32 && num < 32);    const int frac = num * div_mult[den];    const int y = mv.y * frac, x = mv.x * frac;    // Round and clip according to AV1 spec section 7.9.3    union mv res = {0}; // 0x3fff == (1 << 14) - 1    res.y = iclip((y + 8192 + (y >> 31)) >> 14, -0x3fff, 0x3fff);    res.x = iclip((x + 8192 + (x >> 31)) >> 14, -0x3fff, 0x3fff);    return res;} static void add_temporal_candidate(const refmvs_frame *const rf,                                   refmvs_candidate *const mvstack, int *const cnt,                                   const refmvs_temporal_block *const rb,                                   const union refmvs_refpair ref, int *const globalmv_ctx,                                   const union mv gmv[]){    if (rb->mv.n == INVALID_MV) return;     union mv mv = mv_projection(rb->mv, rf->pocdiff[ref.ref[0] - 1], rb->ref);    fix_mv_precision(rf->frm_hdr, &mv);     const int last = *cnt;    if (ref.ref[1] == -1) {        if (globalmv_ctx)            *globalmv_ctx = (abs(mv.x - gmv[0].x) | abs(mv.y - gmv[0].y)) >= 16;         for (int n = 0; n < last; n++)            if (mvstack[n].mv.mv[0].n == mv.n) {                mvstack[n].weight += 2;                return;            }        if (last < 8) {            mvstack[last].mv.mv[0] = mv;            mvstack[last].weight = 2;            *cnt = last + 1;        }    } else {        refmvs_mvpair mvp = { .mv = {            [0] = mv,            [1] = mv_projection(rb->mv, rf->pocdiff[ref.ref[1] - 1], rb->ref),        }};        fix_mv_precision(rf->frm_hdr, &mvp.mv[1]);         for (int n = 0; n < last; n++)            if (mvstack[n].mv.n == mvp.n) {                mvstack[n].weight += 2;                return;            }        if (last < 8) {            mvstack[last].mv = mvp;            mvstack[last].weight = 2;            *cnt = last + 1;        }    }} static void add_compound_extended_candidate(refmvs_candidate *const same,                                            int *const same_count,                                            const refmvs_block *const cand_b,                                            const int sign0, const int sign1,                                            const union refmvs_refpair ref,                                            const uint8_t *const sign_bias){    refmvs_candidate *const diff = &same[2];    int *const diff_count = &same_count[2];     for (int n = 0; n < 2; n++) {        const int cand_ref = cand_b->ref.ref[n];         if (cand_ref <= 0) break;         mv cand_mv = cand_b->mv.mv[n];        if (cand_ref == ref.ref[0]) {            if (same_count[0] < 2)                same[same_count[0]++].mv.mv[0] = cand_mv;            if (diff_count[1] < 2) {                if (sign1 ^ sign_bias[cand_ref - 1]) {                    cand_mv.y = -cand_mv.y;                    cand_mv.x = -cand_mv.x;                }                diff[diff_count[1]++].mv.mv[1] = cand_mv;            }        } else if (cand_ref == ref.ref[1]) {            if (same_count[1] < 2)                same[same_count[1]++].mv.mv[1] = cand_mv;            if (diff_count[0] < 2) {                if (sign0 ^ sign_bias[cand_ref - 1]) {                    cand_mv.y = -cand_mv.y;                    cand_mv.x = -cand_mv.x;                }                diff[diff_count[0]++].mv.mv[0] = cand_mv;            }        } else {            union mv i_cand_mv = {0};            i_cand_mv.x = -cand_mv.x;            i_cand_mv.y = -cand_mv.y;             if (diff_count[0] < 2) {                diff[diff_count[0]++].mv.mv[0] =                    sign0 ^ sign_bias[cand_ref - 1] ?                    i_cand_mv : cand_mv;            }             if (diff_count[1] < 2) {                diff[diff_count[1]++].mv.mv[1] =                    sign1 ^ sign_bias[cand_ref - 1] ?                    i_cand_mv : cand_mv;            }        }    }} static void add_single_extended_candidate(refmvs_candidate mvstack[8], int *const cnt,                                          const refmvs_block *const cand_b,                                          const int sign, const uint8_t *const sign_bias){    for (int n = 0; n < 2; n++) {        const int cand_ref = cand_b->ref.ref[n];         if (cand_ref <= 0) break;        // we need to continue even if cand_ref == ref.ref[0], since        // the candidate could have been added as a globalmv variant,        // which changes the value        // FIXME if scan_{row,col}() returned a mask for the nearest        // edge, we could skip the appropriate ones here         mv cand_mv = cand_b->mv.mv[n];        if (sign ^ sign_bias[cand_ref - 1]) {            cand_mv.y = -cand_mv.y;            cand_mv.x = -cand_mv.x;        }         int m;        const int last = *cnt;        for (m = 0; m < last; m++)            if (cand_mv.n == mvstack[m].mv.mv[0].n)                break;        if (m == last) {            mvstack[m].mv.mv[0] = cand_mv;            mvstack[m].weight = 2; // "minimal"            *cnt = last + 1;        }    }} /* * refmvs_frame allocates memory for one sbrow (32 blocks high, whole frame * wide) of 4x4-resolution refmvs_block entries for spatial MV referencing. * mvrefs_tile[] keeps a list of 35 (32 + 3 above) pointers into this memory, * and each sbrow, the bottom entries (y=27/29/31) are exchanged with the top * (-5/-3/-1) pointers by calling dav1d_refmvs_tile_sbrow_init() at the start * of each tile/sbrow. * * For temporal MV referencing, we call dav1d_refmvs_save_tmvs() at the end of * each tile/sbrow (when tile column threading is enabled), or at the start of * each interleaved sbrow (i.e. once for all tile columns together, when tile * column threading is disabled). This will copy the 4x4-resolution spatial MVs * into 8x8-resolution refmvs_temporal_block structures. Then, for subsequent * frames, at the start of each tile/sbrow (when tile column threading is * enabled) or at the start of each interleaved sbrow (when tile column * threading is disabled), we call load_tmvs(), which will project the MVs to * their respective position in the current frame. */ void dav1d_refmvs_find(const refmvs_tile *const rt,                       refmvs_candidate mvstack[8], int *const cnt,                       int *const ctx,                       const union refmvs_refpair ref, const enum BlockSize bs,                       const enum EdgeFlags edge_flags,                       const int by4, const int bx4){    const refmvs_frame *const rf = rt->rf;    const uint8_t *const b_dim = dav1d_block_dimensions[bs];    const int bw4 = b_dim[0], w4 = imin(imin(bw4, 16), rt->tile_col.end - bx4);    const int bh4 = b_dim[1], h4 = imin(imin(bh4, 16), rt->tile_row.end - by4);    mv gmv[2], tgmv[2], imv = { .n = INVALID_MV };     *cnt = 0;    assert(ref.ref[0] >=  0 && ref.ref[0] <= 8 &&           ref.ref[1] >= -1 && ref.ref[1] <= 8);    if (ref.ref[0] > 0) {        tgmv[0] = get_gmv_2d(&rf->frm_hdr->gmv[ref.ref[0] - 1],                             bx4, by4, bw4, bh4, rf->frm_hdr);        gmv[0] = rf->frm_hdr->gmv[ref.ref[0] - 1].type > DAV1D_WM_TYPE_TRANSLATION ?                 tgmv[0] : imv;    } else {        memset(&tgmv[0], 0, sizeof(tgmv[0]));        gmv[0] = imv;    }    if (ref.ref[1] > 0) {        tgmv[1] = get_gmv_2d(&rf->frm_hdr->gmv[ref.ref[1] - 1],                             bx4, by4, bw4, bh4, rf->frm_hdr);        gmv[1] = rf->frm_hdr->gmv[ref.ref[1] - 1].type > DAV1D_WM_TYPE_TRANSLATION ?                 tgmv[1] : imv;    }     // top    int have_newmv = 0, have_col_mvs = 0, have_row_mvs = 0;    unsigned max_rows = 0, n_rows = ~0;    const refmvs_block *b_top;    if (by4 > rt->tile_row.start) {        max_rows = imin((by4 - rt->tile_row.start + 1) >> 1, 2 + (bh4 > 1));        b_top = &rt->r[(by4 & 31) - 1 + 5][bx4];        n_rows = scan_row(mvstack, cnt, ref, gmv, b_top,                          bw4, w4, max_rows, bw4 >= 16 ? 4 : 1,                          &have_newmv, &have_row_mvs);    }     // left    unsigned max_cols = 0, n_cols = ~0U;    refmvs_block *const *b_left;    if (bx4 > rt->tile_col.start) {        max_cols = imin((bx4 - rt->tile_col.start + 1) >> 1, 2 + (bw4 > 1));        b_left = &rt->r[(by4 & 31) + 5];        n_cols = scan_col(mvstack, cnt, ref, gmv, b_left,                          bh4, h4, bx4 - 1, max_cols, bh4 >= 16 ? 4 : 1,                          &have_newmv, &have_col_mvs);    }     // top/right    if (n_rows != ~0U && edge_flags & EDGE_I444_TOP_HAS_RIGHT &&        imax(bw4, bh4) <= 16 && bw4 + bx4 < rt->tile_col.end)    {        add_spatial_candidate(mvstack, cnt, 4, &b_top[bw4], ref, gmv,                              &have_newmv, &have_row_mvs);    }     const int nearest_match = have_col_mvs + have_row_mvs;    const int nearest_cnt = *cnt;    for (int n = 0; n < nearest_cnt; n++)        mvstack[n].weight += 640;     // temporal    int globalmv_ctx = rf->frm_hdr->use_ref_frame_mvs;    if (rf->use_ref_frame_mvs) {        const ptrdiff_t stride = rf->rp_stride;        const int by8 = by4 >> 1, bx8 = bx4 >> 1;        const refmvs_temporal_block *const rbi = &rt->rp_proj[(by8 & 15) * stride + bx8];        const refmvs_temporal_block *rb = rbi;        const int step_h = bw4 >= 16 ? 2 : 1, step_v = bh4 >= 16 ? 2 : 1;        const int w8 = imin((w4 + 1) >> 1, 8), h8 = imin((h4 + 1) >> 1, 8);        for (int y = 0; y < h8; y += step_v) {            for (int x = 0; x < w8; x+= step_h) {                add_temporal_candidate(rf, mvstack, cnt, &rb[x], ref,                                       !(x | y) ? &globalmv_ctx : NULL, tgmv);            }            rb += stride * step_v;        }        if (imin(bw4, bh4) >= 2 && imax(bw4, bh4) < 16) {            const int bh8 = bh4 >> 1, bw8 = bw4 >> 1;            rb = &rbi[bh8 * stride];            const int has_bottom = by8 + bh8 < imin(rt->tile_row.end >> 1,                                                    (by8 & ~7) + 8);            if (has_bottom && bx8 - 1 >= imax(rt->tile_col.start >> 1, bx8 & ~7)) {                add_temporal_candidate(rf, mvstack, cnt, &rb[-1], ref,                                       NULL, NULL);            }            if (bx8 + bw8 < imin(rt->tile_col.end >> 1, (bx8 & ~7) + 8)) {                if (has_bottom) {                    add_temporal_candidate(rf, mvstack, cnt, &rb[bw8], ref,                                           NULL, NULL);                }                if (by8 + bh8 - 1 < imin(rt->tile_row.end >> 1, (by8 & ~7) + 8)) {                    add_temporal_candidate(rf, mvstack, cnt, &rb[bw8 - stride],                                           ref, NULL, NULL);                }            }        }    }    assert(*cnt <= 8);     // top/left (which, confusingly, is part of "secondary" references)    int have_dummy_newmv_match;    if ((n_rows | n_cols) != ~0U) {        add_spatial_candidate(mvstack, cnt, 4, &b_top[-1], ref, gmv,                              &have_dummy_newmv_match, &have_row_mvs);    }     // "secondary" (non-direct neighbour) top & left edges    // what is different about secondary is that everything is now in 8x8 resolution    for (int n = 2; n <= 3; n++) {        if ((unsigned) n > n_rows && (unsigned) n <= max_rows) {            n_rows += scan_row(mvstack, cnt, ref, gmv,                               &rt->r[(((by4 & 31) - 2 * n + 1) | 1) + 5][bx4 | 1],                               bw4, w4, 1 + max_rows - n, bw4 >= 16 ? 4 : 2,                               &have_dummy_newmv_match, &have_row_mvs);        }         if ((unsigned) n > n_cols && (unsigned) n <= max_cols) {            n_cols += scan_col(mvstack, cnt, ref, gmv, &rt->r[((by4 & 31) | 1) + 5],                               bh4, h4, (bx4 - n * 2 + 1) | 1,                               1 + max_cols - n, bh4 >= 16 ? 4 : 2,                               &have_dummy_newmv_match, &have_col_mvs);        }    }    assert(*cnt <= 8);     const int ref_match_count = have_col_mvs + have_row_mvs;     // context build-up    int refmv_ctx, newmv_ctx;    switch (nearest_match) {    case 0:        refmv_ctx = imin(2, ref_match_count);        newmv_ctx = ref_match_count > 0;        break;    case 1:        refmv_ctx = imin(ref_match_count * 3, 4);        newmv_ctx = 3 - have_newmv;        break;    case 2:        refmv_ctx = 5;        newmv_ctx = 5 - have_newmv;        break;    }     // sorting (nearest, then "secondary")

Lines 1–500 of 912. Load more