// Copyright 2019 The libgav1 Authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#include "src/motion_vector.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <cstdlib>
#include <memory>
#include "src/dsp/dsp.h"
#include "src/utils/bit_mask_set.h"
#include "src/utils/common.h"
#include "src/utils/constants.h"
#include "src/utils/logging.h"
namespace libgav1 {
namespace {
// Entry at index i is computed as:
// Clip3(std::max(kBlockWidthPixels[i], kBlockHeightPixels[i], 16, 112)).
constexpr int kWarpValidThreshold[kMaxBlockSizes] = {
16, 16, 16, 16, 16, 16, 32, 16, 16, 16, 32,
64, 32, 32, 32, 64, 64, 64, 64, 112, 112, 112};
// 7.10.2.10.
void LowerMvPrecision(const ObuFrameHeader& frame_header,
MotionVector* const mvs) {
if (frame_header.allow_high_precision_mv) return;
if (frame_header.force_integer_mv != 0) {
for (auto& mv : mvs->mv) {
// The next line is equivalent to:
// const int value = (std::abs(static_cast<int>(mv)) + 3) & ~7;
// const int sign = mv >> 15;
// mv = ApplySign(value, sign);
mv = (mv + 3 - (mv >> 15)) & ~7;
}
} else {
for (auto& mv : mvs->mv) {
// The next line is equivalent to:
// if ((mv & 1) != 0) mv += (mv > 0) ? -1 : 1;
mv = (mv - (mv >> 15)) & ~1;
}
}
}
// 7.10.2.1.
void SetupGlobalMv(const Tile::Block& block, int index,
MotionVector* const mv) {
const BlockParameters& bp = *block.bp;
const ObuFrameHeader& frame_header = block.tile.frame_header();
ReferenceFrameType reference_type = bp.reference_frame[index];
const auto& gm = frame_header.global_motion[reference_type];
if (reference_type == kReferenceFrameIntra ||
gm.type == kGlobalMotionTransformationTypeIdentity) {
mv->mv32 = 0;
return;
}
if (gm.type == kGlobalMotionTransformationTypeTranslation) {
for (int i = 0; i < 2; ++i) {
mv->mv[i] = gm.params[i] >> (kWarpedModelPrecisionBits - 3);
}
LowerMvPrecision(frame_header, mv);
return;
}
const int x = MultiplyBy4(block.column4x4) + DivideBy2(block.width) - 1;
const int y = MultiplyBy4(block.row4x4) + DivideBy2(block.height) - 1;
const int xc = (gm.params[2] - (1 << kWarpedModelPrecisionBits)) * x +
gm.params[3] * y + gm.params[0];
const int yc = gm.params[4] * x +
(gm.params[5] - (1 << kWarpedModelPrecisionBits)) * y +
gm.params[1];
if (frame_header.allow_high_precision_mv) {
mv->mv[0] = RightShiftWithRoundingSigned(yc, kWarpedModelPrecisionBits - 3);
mv->mv[1] = RightShiftWithRoundingSigned(xc, kWarpedModelPrecisionBits - 3);
} else {
mv->mv[0] = MultiplyBy2(
RightShiftWithRoundingSigned(yc, kWarpedModelPrecisionBits - 2));
mv->mv[1] = MultiplyBy2(
RightShiftWithRoundingSigned(xc, kWarpedModelPrecisionBits - 2));
LowerMvPrecision(frame_header, mv);
}
}
constexpr BitMaskSet kPredictionModeNewMvMask(kPredictionModeNewMv,
kPredictionModeNewNewMv,
kPredictionModeNearNewMv,
kPredictionModeNewNearMv,
kPredictionModeNearestNewMv,
kPredictionModeNewNearestMv);
// 7.10.2.8.
void SearchStack(const Tile::Block& block, const BlockParameters& mv_bp,
int index, int weight, bool* const found_new_mv,
bool* const found_match, int* const num_mv_found) {
const BlockParameters& bp = *block.bp;
const std::array<GlobalMotion, kNumReferenceFrameTypes>& global_motion =
block.tile.frame_header().global_motion;
PredictionParameters& prediction_parameters = *bp.prediction_parameters;
MotionVector candidate_mv;
// LowerMvPrecision() is not necessary, since the values in
// |prediction_parameters.global_mv| and |mv_bp.mv| were generated by it.
const auto global_motion_type = global_motion[bp.reference_frame[0]].type;
if (IsGlobalMvBlock(mv_bp, global_motion_type)) {
candidate_mv = prediction_parameters.global_mv[0];
} else {
candidate_mv = mv_bp.mv.mv[index];
}
*found_new_mv |= kPredictionModeNewMvMask.Contains(mv_bp.y_mode);
*found_match = true;
MotionVector* const ref_mv_stack = prediction_parameters.ref_mv_stack;
const int num_found = *num_mv_found;
const auto result = std::find_if(ref_mv_stack, ref_mv_stack + num_found,
[&candidate_mv](const MotionVector& ref_mv) {
return ref_mv.mv32 == candidate_mv.mv32;
});
if (result != ref_mv_stack + num_found) {
prediction_parameters.IncreaseWeight(std::distance(ref_mv_stack, result),
weight);
return;
}
if (num_found >= kMaxRefMvStackSize) return;
ref_mv_stack[num_found] = candidate_mv;
prediction_parameters.SetWeightIndexStackEntry(num_found, weight);
++*num_mv_found;
}
// 7.10.2.9.
void CompoundSearchStack(const Tile::Block& block, const BlockParameters& mv_bp,
int weight, bool* const found_new_mv,
bool* const found_match, int* const num_mv_found) {
const BlockParameters& bp = *block.bp;
const std::array<GlobalMotion, kNumReferenceFrameTypes>& global_motion =
block.tile.frame_header().global_motion;
PredictionParameters& prediction_parameters = *bp.prediction_parameters;
// LowerMvPrecision() is not necessary, since the values in
// |prediction_parameters.global_mv| and |mv_bp.mv| were generated by it.
CompoundMotionVector candidate_mv = mv_bp.mv;
for (int i = 0; i < 2; ++i) {
const auto global_motion_type = global_motion[bp.reference_frame[i]].type;
if (IsGlobalMvBlock(mv_bp, global_motion_type)) {
candidate_mv.mv[i] = prediction_parameters.global_mv[i];
}
}
*found_new_mv |= kPredictionModeNewMvMask.Contains(mv_bp.y_mode);
*found_match = true;
CompoundMotionVector* const compound_ref_mv_stack =
prediction_parameters.compound_ref_mv_stack;
const int num_found = *num_mv_found;
const auto result =
std::find_if(compound_ref_mv_stack, compound_ref_mv_stack + num_found,
[&candidate_mv](const CompoundMotionVector& ref_mv) {
return ref_mv.mv64 == candidate_mv.mv64;
});
if (result != compound_ref_mv_stack + num_found) {
prediction_parameters.IncreaseWeight(
std::distance(compound_ref_mv_stack, result), weight);
return;
}
if (num_found >= kMaxRefMvStackSize) return;
compound_ref_mv_stack[num_found].mv64 = candidate_mv.mv64;
prediction_parameters.SetWeightIndexStackEntry(num_found, weight);
++*num_mv_found;
}
// 7.10.2.7.
void AddReferenceMvCandidate(const Tile::Block& block,
const BlockParameters& mv_bp, bool is_compound,
int weight, bool* const found_new_mv,
bool* const found_match, int* const num_mv_found) {
if (!mv_bp.is_inter) return;
const BlockParameters& bp = *block.bp;
if (is_compound) {
if (mv_bp.reference_frame[0] == bp.reference_frame[0] &&
mv_bp.reference_frame[1] == bp.reference_frame[1]) {
CompoundSearchStack(block, mv_bp, weight, found_new_mv, found_match,
num_mv_found);
}
return;
}
for (int i = 0; i < 2; ++i) {
if (mv_bp.reference_frame[i] == bp.reference_frame[0]) {
SearchStack(block, mv_bp, i, weight, found_new_mv, found_match,
num_mv_found);
}
}
}
int GetMinimumStep(int block_width_or_height4x4, int delta_row_or_column) {
assert(delta_row_or_column < 0);
if (block_width_or_height4x4 >= 16) return 4;
if (delta_row_or_column < -1) return 2;
return 0;
}
// 7.10.2.2.
void ScanRow(const Tile::Block& block, int mv_column, int delta_row,
bool is_compound, bool* const found_new_mv,
bool* const found_match, int* const num_mv_found) {
const int mv_row = block.row4x4 + delta_row;
const Tile& tile = block.tile;
if (!tile.IsTopInside(mv_row + 1)) return;
const int width4x4 = block.width4x4;
const int min_step = GetMinimumStep(width4x4, delta_row);
BlockParameters** bps = tile.BlockParametersAddress(mv_row, mv_column);
BlockParameters** const end_bps =
bps + std::min({static_cast<int>(width4x4),
tile.frame_header().columns4x4 - block.column4x4, 16});
do {
const BlockParameters& mv_bp = **bps;
const int step = std::max(
std::min(width4x4, static_cast<int>(kNum4x4BlocksWide[mv_bp.size])),
min_step);
AddReferenceMvCandidate(block, mv_bp, is_compound, MultiplyBy2(step),
found_new_mv, found_match, num_mv_found);
bps += step;
} while (bps < end_bps);
}
// 7.10.2.3.
void ScanColumn(const Tile::Block& block, int mv_row, int delta_column,
bool is_compound, bool* const found_new_mv,
bool* const found_match, int* const num_mv_found) {
const int mv_column = block.column4x4 + delta_column;
const Tile& tile = block.tile;
if (!tile.IsLeftInside(mv_column + 1)) return;
const int height4x4 = block.height4x4;
const int min_step = GetMinimumStep(height4x4, delta_column);
const ptrdiff_t stride = tile.BlockParametersStride();
BlockParameters** bps = tile.BlockParametersAddress(mv_row, mv_column);
BlockParameters** const end_bps =
bps + stride * std::min({static_cast<int>(height4x4),
tile.frame_header().rows4x4 - block.row4x4, 16});
do {
const BlockParameters& mv_bp = **bps;
const int step = std::max(
std::min(height4x4, static_cast<int>(kNum4x4BlocksHigh[mv_bp.size])),
min_step);
AddReferenceMvCandidate(block, mv_bp, is_compound, MultiplyBy2(step),
found_new_mv, found_match, num_mv_found);
bps += step * stride;
} while (bps < end_bps);
}
// 7.10.2.4.
void ScanPoint(const Tile::Block& block, int delta_row, int delta_column,
bool is_compound, bool* const found_new_mv,
bool* const found_match, int* const num_mv_found) {
const int mv_row = block.row4x4 + delta_row;
const int mv_column = block.column4x4 + delta_column;
const Tile& tile = block.tile;
if (!tile.IsInside(mv_row, mv_column) ||
!tile.HasParameters(mv_row, mv_column)) {
return;
}
const BlockParameters& mv_bp = tile.Parameters(mv_row, mv_column);
if (mv_bp.reference_frame[0] == kReferenceFrameNone) return;
AddReferenceMvCandidate(block, mv_bp, is_compound, 4, found_new_mv,
found_match, num_mv_found);
}
// 7.10.2.6.
void AddTemporalReferenceMvCandidate(
const ObuFrameHeader& frame_header, const int reference_offsets[2],
const MotionVector* const temporal_mvs,
const int8_t* const temporal_reference_offsets, int count, bool is_compound,
int* const zero_mv_context, int* const num_mv_found,
PredictionParameters* const prediction_parameters) {
const int mv_projection_function_index =
frame_header.allow_high_precision_mv ? 2 : frame_header.force_integer_mv;
const MotionVector* const global_mv = prediction_parameters->global_mv;
if (is_compound) {
alignas(kMaxAlignment)
CompoundMotionVector candidate_mvs[kMaxTemporalMvCandidatesWithPadding];
const dsp::Dsp& dsp = *dsp::GetDspTable(8);
dsp.mv_projection_compound[mv_projection_function_index](
temporal_mvs, temporal_reference_offsets, reference_offsets, count,
candidate_mvs);
if (*zero_mv_context == -1) {
int max_difference =
std::max(std::abs(candidate_mvs[0].mv[0].mv[0] - global_mv[0].mv[0]),
std::abs(candidate_mvs[0].mv[0].mv[1] - global_mv[0].mv[1]));
max_difference =
std::max(max_difference,
std::abs(candidate_mvs[0].mv[1].mv[0] - global_mv[1].mv[0]));
max_difference =
std::max(max_difference,
std::abs(candidate_mvs[0].mv[1].mv[1] - global_mv[1].mv[1]));
*zero_mv_context = static_cast<int>(max_difference >= 16);
}
CompoundMotionVector* const compound_ref_mv_stack =
prediction_parameters->compound_ref_mv_stack;
int num_found = *num_mv_found;
int index = 0;
do {
const CompoundMotionVector& candidate_mv = candidate_mvs[index];
const auto result =
std::find_if(compound_ref_mv_stack, compound_ref_mv_stack + num_found,
[&candidate_mv](const CompoundMotionVector& ref_mv) {
return ref_mv.mv64 == candidate_mv.mv64;
});
if (result != compound_ref_mv_stack + num_found) {
prediction_parameters->IncreaseWeight(
std::distance(compound_ref_mv_stack, result), 2);
continue;
}
if (num_found >= kMaxRefMvStackSize) continue;
compound_ref_mv_stack[num_found].mv64 = candidate_mv.mv64;
prediction_parameters->SetWeightIndexStackEntry(num_found, 2);
++num_found;
} while (++index < count);
*num_mv_found = num_found;
return;
}
MotionVector* const ref_mv_stack = prediction_parameters->ref_mv_stack;
if (reference_offsets[0] == 0) {
if (*zero_mv_context == -1) {
const int max_difference =
std::max(std::abs(global_mv[0].mv[0]), std::abs(global_mv[0].mv[1]));
*zero_mv_context = static_cast<int>(max_difference >= 16);
}
const MotionVector candidate_mv = {};
const int num_found = *num_mv_found;
const auto result =
std::find_if(ref_mv_stack, ref_mv_stack + num_found,
[&candidate_mv](const MotionVector& ref_mv) {
return ref_mv.mv32 == candidate_mv.mv32;
});
if (result != ref_mv_stack + num_found) {
prediction_parameters->IncreaseWeight(std::distance(ref_mv_stack, result),
2 * count);
return;
}
if (num_found >= kMaxRefMvStackSize) return;
ref_mv_stack[num_found] = candidate_mv;
prediction_parameters->SetWeightIndexStackEntry(num_found, 2 * count);
++*num_mv_found;
return;
}
alignas(kMaxAlignment)
MotionVector candidate_mvs[kMaxTemporalMvCandidatesWithPadding];
const dsp::Dsp& dsp = *dsp::GetDspTable(8);
dsp.mv_projection_single[mv_projection_function_index](
temporal_mvs, temporal_reference_offsets, reference_offsets[0], count,
candidate_mvs);
if (*zero_mv_context == -1) {
const int max_difference =
std::max(std::abs(candidate_mvs[0].mv[0] - global_mv[0].mv[0]),
std::abs(candidate_mvs[0].mv[1] - global_mv[0].mv[1]));
*zero_mv_context = static_cast<int>(max_difference >= 16);
}
int num_found = *num_mv_found;
int index = 0;
do {
const MotionVector& candidate_mv = candidate_mvs[index];
const auto result =
std::find_if(ref_mv_stack, ref_mv_stack + num_found,
[&candidate_mv](const MotionVector& ref_mv) {
return ref_mv.mv32 == candidate_mv.mv32;
});
if (result != ref_mv_stack + num_found) {
prediction_parameters->IncreaseWeight(std::distance(ref_mv_stack, result),
2);
continue;
}
if (num_found >= kMaxRefMvStackSize) continue;
ref_mv_stack[num_found] = candidate_mv;
prediction_parameters->SetWeightIndexStackEntry(num_found, 2);
++num_found;
} while (++index < count);
*num_mv_found = num_found;
}
// Part of 7.10.2.5.
bool IsWithinTheSame64x64Block(const Tile::Block& block, int delta_row,
int delta_column) {
const int row = (block.row4x4 & 15) + delta_row;
const int column = (block.column4x4 & 15) + delta_column;
// |block.height4x4| is at least 2 for all elements in |kTemporalScanMask|.
// So |row| are all non-negative.
assert(row >= 0);
return row < 16 && column >= 0 && column < 16;
}
constexpr BitMaskSet kTemporalScanMask(kBlock8x8, kBlock8x16, kBlock8x32,
kBlock16x8, kBlock16x16, kBlock16x32,
kBlock32x8, kBlock32x16, kBlock32x32);
// 7.10.2.5.
void TemporalScan(const Tile::Block& block, bool is_compound,
int* const zero_mv_context, int* const num_mv_found) {
const int step_w = (block.width4x4 >= 16) ? 4 : 2;
const int step_h = (block.height4x4 >= 16) ? 4 : 2;
const int row_start = block.row4x4 | 1;
const int column_start = block.column4x4 | 1;
const int row_end =
row_start + std::min(static_cast<int>(block.height4x4), 16);
const int column_end =
column_start + std::min(static_cast<int>(block.width4x4), 16);
const Tile& tile = block.tile;
const TemporalMotionField& motion_field = tile.motion_field();
const int stride = motion_field.mv.columns();
const MotionVector* motion_field_mv = motion_field.mv[0];
const int8_t* motion_field_reference_offset =
motion_field.reference_offset[0];
alignas(kMaxAlignment)
MotionVector temporal_mvs[kMaxTemporalMvCandidatesWithPadding];
int8_t temporal_reference_offsets[kMaxTemporalMvCandidatesWithPadding];
int count = 0;
int offset = stride * (row_start >> 1);
int mv_row = row_start;
do {
int mv_column = column_start;
do {
// Both horizontal and vertical offsets are positive. Only bottom and
// right boundaries need to be checked.
if (tile.IsBottomRightInside(mv_row, mv_column)) {
const int x8 = mv_column >> 1;
const MotionVector temporal_mv = motion_field_mv[offset + x8];
if (temporal_mv.mv[0] == kInvalidMvValue) {
if (mv_row == row_start && mv_column == column_start) {
*zero_mv_context = 1;
}
} else {
temporal_mvs[count] = temporal_mv;
temporal_reference_offsets[count++] =
motion_field_reference_offset[offset + x8];
}
}
mv_column += step_w;
} while (mv_column < column_end);
offset += stride * step_h >> 1;
mv_row += step_h;
} while (mv_row < row_end);
if (kTemporalScanMask.Contains(block.size)) {
const int temporal_sample_positions[3][2] = {
{block.height4x4, -2},
{block.height4x4, block.width4x4},
{block.height4x4 - 2, block.width4x4}};
// Getting the address of an element in Array2D is slow. Precalculate the
// offsets.
int temporal_sample_offsets[3];
temporal_sample_offsets[0] = stride * ((row_start + block.height4x4) >> 1) +
((column_start - 2) >> 1);
temporal_sample_offsets[1] =
temporal_sample_offsets[0] + ((block.width4x4 + 2) >> 1);
temporal_sample_offsets[2] = temporal_sample_offsets[1] - stride;
for (int i = 0; i < 3; i++) {
const int row = temporal_sample_positions[i][0];
const int column = temporal_sample_positions[i][1];
if (!IsWithinTheSame64x64Block(block, row, column)) continue;
const int mv_row = row_start + row;
const int mv_column = column_start + column;
// IsWithinTheSame64x64Block() guarantees the reference block is inside
// the top and left boundary.
if (!tile.IsBottomRightInside(mv_row, mv_column)) continue;
const MotionVector temporal_mv =
motion_field_mv[temporal_sample_offsets[i]];
if (temporal_mv.mv[0] != kInvalidMvValue) {
temporal_mvs[count] = temporal_mv;
temporal_reference_offsets[count++] =
motion_field_reference_offset[temporal_sample_offsets[i]];
}
}
}
if (count != 0) {
BlockParameters* const bp = block.bp;
int reference_offsets[2];
const int offset_0 = tile.current_frame()
.reference_info()
->relative_distance_to[bp->reference_frame[0]];
reference_offsets[0] =
Clip3(offset_0, -kMaxFrameDistance, kMaxFrameDistance);
if (is_compound) {
const int offset_1 = tile.current_frame()
.reference_info()
->relative_distance_to[bp->reference_frame[1]];
reference_offsets[1] =
Clip3(offset_1, -kMaxFrameDistance, kMaxFrameDistance);
// Pad so that SIMD implementations won't read uninitialized memory.
if ((count & 1) != 0) {
temporal_mvs[count].mv32 = 0;
temporal_reference_offsets[count] = 0;
}
} else {
// Pad so that SIMD implementations won't read uninitialized memory.
for (int i = count; i < ((count + 3) & ~3); ++i) {
temporal_mvs[i].mv32 = 0;
temporal_reference_offsets[i] = 0;
}
}
AddTemporalReferenceMvCandidate(
tile.frame_header(), reference_offsets, temporal_mvs,
temporal_reference_offsets, count, is_compound, zero_mv_context,
num_mv_found, &(*bp->prediction_parameters));
}
}
// Part of 7.10.2.13.
void AddExtraCompoundMvCandidate(const Tile::Block& block, int mv_row,
int mv_column, int* const ref_id_count,
MotionVector ref_id[2][2],
int* const ref_diff_count,
MotionVector ref_diff[2][2]) {
const auto& bp = block.tile.Parameters(mv_row, mv_column);
const std::array<bool, kNumReferenceFrameTypes>& reference_frame_sign_bias =
block.tile.reference_frame_sign_bias();
for (int i = 0; i < 2; ++i) {
const ReferenceFrameType candidate_reference_frame = bp.reference_frame[i];
if (candidate_reference_frame <= kReferenceFrameIntra) continue;
for (int j = 0; j < 2; ++j) {
MotionVector candidate_mv = bp.mv.mv[i];
const ReferenceFrameType block_reference_frame =
block.bp->reference_frame[j];
if (candidate_reference_frame == block_reference_frame &&
ref_id_count[j] < 2) {
ref_id[j][ref_id_count[j]] = candidate_mv;
++ref_id_count[j];
} else if (ref_diff_count[j] < 2) {
if (reference_frame_sign_bias[candidate_reference_frame] !=
reference_frame_sign_bias[block_reference_frame]) {
candidate_mv.mv[0] *= -1;
candidate_mv.mv[1] *= -1;
}
ref_diff[j][ref_diff_count[j]] = candidate_mv;
++ref_diff_count[j];
}
}
}
}
// Part of 7.10.2.13.
void AddExtraSingleMvCandidate(const Tile::Block& block, int mv_row,
int mv_column, int* const num_mv_found) {
const auto& bp = block.tile.Parameters(mv_row, mv_column);
const std::array<bool, kNumReferenceFrameTypes>& reference_frame_sign_bias =
block.tile.reference_frame_sign_bias();
const ReferenceFrameType block_reference_frame = block.bp->reference_frame[0];
PredictionParameters& prediction_parameters =
*block.bp->prediction_parameters;
MotionVector* const ref_mv_stack = prediction_parameters.ref_mv_stack;
int num_found = *num_mv_found;
for (int i = 0; i < 2; ++i) {
const ReferenceFrameType candidate_reference_frame = bp.reference_frame[i];
if (candidate_reference_frame <= kReferenceFrameIntra) continue;
MotionVector candidate_mv = bp.mv.mv[i];
if (reference_frame_sign_bias[candidate_reference_frame] !=
reference_frame_sign_bias[block_reference_frame]) {
candidate_mv.mv[0] *= -1;
candidate_mv.mv[1] *= -1;
}
assert(num_found <= 2);
if ((num_found != 0 && ref_mv_stack[0].mv32 == candidate_mv.mv32) ||
(num_found == 2 && ref_mv_stack[1].mv32 == candidate_mv.mv32)) {
continue;
}
ref_mv_stack[num_found] = candidate_mv;
prediction_parameters.SetWeightIndexStackEntry(num_found, 0);
++num_found;
}
*num_mv_found = num_found;
}
// 7.10.2.12.
void ExtraSearch(const Tile::Block& block, bool is_compound,
int* const num_mv_found) {
const Tile& tile = block.tile;
const int num4x4 = std::min({static_cast<int>(block.width4x4),
tile.frame_header().columns4x4 - block.column4x4,
static_cast<int>(block.height4x4),
tile.frame_header().rows4x4 - block.row4x4, 16});
int ref_id_count[2] = {};
MotionVector ref_id[2][2] = {};
int ref_diff_count[2] = {};
MotionVector ref_diff[2][2] = {};
PredictionParameters& prediction_parameters =
*block.bp->prediction_parameters;
for (int pass = 0; pass < 2 && *num_mv_found < 2; ++pass) {
for (int i = 0; i < num4x4;) {
const int mv_row = block.row4x4 + ((pass == 0) ? -1 : i);
const int mv_column = block.column4x4 + ((pass == 0) ? i : -1);
if (!tile.IsTopLeftInside(mv_row + 1, mv_column + 1)) break;
if (is_compound) {
AddExtraCompoundMvCandidate(block, mv_row, mv_column, ref_id_count,
ref_id, ref_diff_count, ref_diff);
} else {
AddExtraSingleMvCandidate(block, mv_row, mv_column, num_mv_found);
if (*num_mv_found >= 2) break;
}
const auto& bp = tile.Parameters(mv_row, mv_column);
i +=
(pass == 0) ? kNum4x4BlocksWide[bp.size] : kNum4x4BlocksHigh[bp.size];
}
}
if (is_compound) {
// Merge compound mode extra search into mv stack.
CompoundMotionVector* const compound_ref_mv_stack =
prediction_parameters.compound_ref_mv_stack;
CompoundMotionVector combined_mvs[2] = {};
for (int i = 0; i < 2; ++i) {
int count = 0;
assert(ref_id_count[i] <= 2);
for (int j = 0; j < ref_id_count[i]; ++j, ++count) {
combined_mvs[count].mv[i] = ref_id[i][j];
}
for (int j = 0; j < ref_diff_count[i] && count < 2; ++j, ++count) {
combined_mvs[count].mv[i] = ref_diff[i][j];
}
for (; count < 2; ++count) {
combined_mvs[count].mv[i] = prediction_parameters.global_mv[i];
}
}
if (*num_mv_found == 1) {
if (combined_mvs[0].mv64 == compound_ref_mv_stack[0].mv64) {
compound_ref_mv_stack[1].mv64 = combined_mvs[1].mv64;
} else {
compound_ref_mv_stack[1].mv64 = combined_mvs[0].mv64;
}
prediction_parameters.SetWeightIndexStackEntry(1, 0);
} else {
assert(*num_mv_found == 0);
for (int i = 0; i < 2; ++i) {
compound_ref_mv_stack[i].mv64 = combined_mvs[i].mv64;
prediction_parameters.SetWeightIndexStackEntry(i, 0);
}
}
*num_mv_found = 2;
} else {
// single prediction mode
MotionVector* const ref_mv_stack = prediction_parameters.ref_mv_stack;
for (int i = *num_mv_found; i < 2; ++i) {
ref_mv_stack[i] = prediction_parameters.global_mv[0];
prediction_parameters.SetWeightIndexStackEntry(i, 0);
}
}
}
void DescendingOrderTwo(int* const a, int* const b) {
if (*a < *b) {
std::swap(*a, *b);
}
}
// Comparator used for sorting candidate motion vectors in descending order of
// their weights (as specified in 7.10.2.11).
bool CompareCandidateMotionVectors(const int16_t& lhs, const int16_t& rhs) {
return lhs > rhs;
}
void SortWeightIndexStack(const int size, const int sort_to_n,
int16_t* const weight_index_stack) {
if (size <= 1) return;
if (size <= 3) {
// Specialize small sort sizes to speed up.
int weight_index_0 = weight_index_stack[0];
int weight_index_1 = weight_index_stack[1];
DescendingOrderTwo(&weight_index_0, &weight_index_1);
if (size == 3) {
int weight_index_2 = weight_index_stack[2];
DescendingOrderTwo(&weight_index_1, &weight_index_2);
DescendingOrderTwo(&weight_index_0, &weight_index_1);
weight_index_stack[2] = weight_index_2;
}
weight_index_stack[0] = weight_index_0;
weight_index_stack[1] = weight_index_1;
return;
}
if (sort_to_n == 1) {
// std::max_element() is not efficient. Find the max element in a loop.
int16_t max_element = weight_index_stack[0];
int i = 1;
do {
max_element = std::max(max_element, weight_index_stack[i]);
} while (++i < size);
weight_index_stack[0] = max_element;
return;
}
std::partial_sort(&weight_index_stack[0], &weight_index_stack[sort_to_n],
&weight_index_stack[size], CompareCandidateMotionVectors);
}
// 7.10.2.14 (part 2).
void ComputeContexts(bool found_new_mv, int nearest_matches, int total_matches,
int* new_mv_context, int* reference_mv_context) {
switch (nearest_matches) {
case 0:
*new_mv_context = std::min(total_matches, 1);
*reference_mv_context = total_matches;
break;
case 1:
*new_mv_context = 3 - static_cast<int>(found_new_mv);
*reference_mv_context = 2 + total_matches;
break;
default:
*new_mv_context = 5 - static_cast<int>(found_new_mv);
*reference_mv_context = 5;
break;
}
}
// 7.10.4.2.
void AddSample(const Tile::Block& block, int delta_row, int delta_column,
int* const num_warp_samples, int* const num_samples_scanned,
int candidates[kMaxLeastSquaresSamples][4]) {
if (*num_samples_scanned >= kMaxLeastSquaresSamples) return;
const int mv_row = block.row4x4 + delta_row;
const int mv_column = block.column4x4 + delta_column;
const Tile& tile = block.tile;
if (!tile.IsInside(mv_row, mv_column) ||
!tile.HasParameters(mv_row, mv_column)) {
return;
}
const BlockParameters& bp = *block.bp;
const BlockParameters& mv_bp = tile.Parameters(mv_row, mv_column);
if (mv_bp.reference_frame[0] != bp.reference_frame[0] ||
mv_bp.reference_frame[1] != kReferenceFrameNone) {
return;
}
++*num_samples_scanned;
const int candidate_height4x4 = kNum4x4BlocksHigh[mv_bp.size];
const int candidate_row = mv_row & ~(candidate_height4x4 - 1);
const int candidate_width4x4 = kNum4x4BlocksWide[mv_bp.size];
const int candidate_column = mv_column & ~(candidate_width4x4 - 1);
const BlockParameters& candidate_bp =
tile.Parameters(candidate_row, candidate_column);
const int mv_diff_row =
std::abs(candidate_bp.mv.mv[0].mv[0] - bp.mv.mv[0].mv[0]);
const int mv_diff_column =
std::abs(candidate_bp.mv.mv[0].mv[1] - bp.mv.mv[0].mv[1]);
const bool is_valid =
mv_diff_row + mv_diff_column <= kWarpValidThreshold[block.size];
if (!is_valid && *num_samples_scanned > 1) {
return;
}
const int mid_y =
MultiplyBy4(candidate_row) + MultiplyBy2(candidate_height4x4) - 1;
const int mid_x =
MultiplyBy4(candidate_column) + MultiplyBy2(candidate_width4x4) - 1;
candidates[*num_warp_samples][0] = MultiplyBy8(mid_y);
candidates[*num_warp_samples][1] = MultiplyBy8(mid_x);
candidates[*num_warp_samples][2] =
MultiplyBy8(mid_y) + candidate_bp.mv.mv[0].mv[0];
candidates[*num_warp_samples][3] =
MultiplyBy8(mid_x) + candidate_bp.mv.mv[0].mv[1];
if (is_valid) ++*num_warp_samples;
}
// 7.9.2.
// In the spec, |dst_sign| is either 1 or -1. Here we set |dst_sign| to either 0
// or -1 so that it can be XORed and subtracted directly in ApplySign() and
// corresponding SIMD implementations.
bool MotionFieldProjection(
const ObuFrameHeader& frame_header,
const std::array<RefCountedBufferPtr, kNumReferenceFrameTypes>&
reference_frames,
ReferenceFrameType source, int reference_to_current_with_sign, int dst_sign,
int y8_start, int y8_end, int x8_start, int x8_end,
TemporalMotionField* const motion_field) {
const int source_index =
frame_header.reference_frame_index[source - kReferenceFrameLast];
auto* const source_frame = reference_frames[source_index].get();
assert(source_frame != nullptr);
assert(dst_sign == 0 || dst_sign == -1);
if (source_frame->rows4x4() != frame_header.rows4x4 ||
source_frame->columns4x4() != frame_header.columns4x4 ||
IsIntraFrame(source_frame->frame_type())) {
return false;
}
assert(reference_to_current_with_sign >= -kMaxFrameDistance);
if (reference_to_current_with_sign > kMaxFrameDistance) return true;
const ReferenceInfo& reference_info = *source_frame->reference_info();
const dsp::Dsp& dsp = *dsp::GetDspTable(8);
dsp.motion_field_projection_kernel(
reference_info, reference_to_current_with_sign, dst_sign, y8_start,
y8_end, x8_start, x8_end, motion_field);
return true;
}
} // namespace
void FindMvStack(const Tile::Block& block, bool is_compound,
MvContexts* const contexts) {
PredictionParameters& prediction_parameters =
*block.bp->prediction_parameters;
SetupGlobalMv(block, 0, &prediction_parameters.global_mv[0]);
if (is_compound) SetupGlobalMv(block, 1, &prediction_parameters.global_mv[1]);
bool found_new_mv = false;
bool found_row_match = false;
int num_mv_found = 0;
ScanRow(block, block.column4x4, -1, is_compound, &found_new_mv,
&found_row_match, &num_mv_found);
bool found_column_match = false;
ScanColumn(block, block.row4x4, -1, is_compound, &found_new_mv,
&found_column_match, &num_mv_found);
if (std::max(block.width4x4, block.height4x4) <= 16) {
ScanPoint(block, -1, block.width4x4, is_compound, &found_new_mv,
&found_row_match, &num_mv_found);
}
const int nearest_matches =
static_cast<int>(found_row_match) + static_cast<int>(found_column_match);
prediction_parameters.nearest_mv_count = num_mv_found;
if (block.tile.frame_header().use_ref_frame_mvs) {
// Initialize to invalid value, and it will be set when temporal mv is zero.
contexts->zero_mv = -1;
TemporalScan(block, is_compound, &contexts->zero_mv, &num_mv_found);
} else {
contexts->zero_mv = 0;
}
bool dummy_bool = false;
ScanPoint(block, -1, -1, is_compound, &dummy_bool, &found_row_match,
&num_mv_found);
static constexpr int deltas[2] = {-3, -5};
for (int i = 0; i < 2; ++i) {
if (i == 0 || block.height4x4 > 1) {
ScanRow(block, block.column4x4 | 1, deltas[i] + (block.row4x4 & 1),
is_compound, &dummy_bool, &found_row_match, &num_mv_found);
}
if (i == 0 || block.width4x4 > 1) {
ScanColumn(block, block.row4x4 | 1, deltas[i] + (block.column4x4 & 1),
is_compound, &dummy_bool, &found_column_match, &num_mv_found);
}
}
if (num_mv_found < 2) {
ExtraSearch(block, is_compound, &num_mv_found);
} else {
// The sort of |weight_index_stack| could be moved to Tile::AssignIntraMv()
// and Tile::AssignInterMv(), and only do a partial sort to the max index we
// need. However, the speed gain is trivial.
// For intra case, only the first 1 or 2 mvs in the stack will be used.
// For inter case, |prediction_parameters.ref_mv_index| is at most 3.
// We only need to do the partial sort up to the first 4 mvs.
SortWeightIndexStack(prediction_parameters.nearest_mv_count, 4,
prediction_parameters.weight_index_stack);
// When there are 4 or more nearest mvs, the other mvs will not be used.
if (prediction_parameters.nearest_mv_count < 4) {
SortWeightIndexStack(
num_mv_found - prediction_parameters.nearest_mv_count,
4 - prediction_parameters.nearest_mv_count,
prediction_parameters.weight_index_stack +
prediction_parameters.nearest_mv_count);
}
}
prediction_parameters.ref_mv_count = num_mv_found;
const int total_matches =
static_cast<int>(found_row_match) + static_cast<int>(found_column_match);
ComputeContexts(found_new_mv, nearest_matches, total_matches,
&contexts->new_mv, &contexts->reference_mv);
// The mv stack clamping process is in Tile::AssignIntraMv() and
// Tile::AssignInterMv(), and only up to two mvs are clamped.
}
void FindWarpSamples(const Tile::Block& block, int* const num_warp_samples,
int* const num_samples_scanned,
int candidates[kMaxLeastSquaresSamples][4]) {
const Tile& tile = block.tile;
bool top_left = true;
bool top_right = true;
int step = 1;
if (block.top_available[kPlaneY]) {
BlockSize source_size =
tile.Parameters(block.row4x4 - 1, block.column4x4).size;
const int source_width4x4 = kNum4x4BlocksWide[source_size];
if (block.width4x4 <= source_width4x4) {
// The & here is equivalent to % since source_width4x4 is a power of two.
const int column_offset = -(block.column4x4 & (source_width4x4 - 1));
if (column_offset < 0) top_left = false;
if (column_offset + source_width4x4 > block.width4x4) top_right = false;
AddSample(block, -1, 0, num_warp_samples, num_samples_scanned,
candidates);
} else {
for (int i = 0;
i < std::min(static_cast<int>(block.width4x4),
tile.frame_header().columns4x4 - block.column4x4);
i += step) {
source_size =
tile.Parameters(block.row4x4 - 1, block.column4x4 + i).size;
step = std::min(static_cast<int>(block.width4x4),
static_cast<int>(kNum4x4BlocksWide[source_size]));
AddSample(block, -1, i, num_warp_samples, num_samples_scanned,
candidates);
}
}
}
if (block.left_available[kPlaneY]) {
BlockSize source_size =
tile.Parameters(block.row4x4, block.column4x4 - 1).size;
const int source_height4x4 = kNum4x4BlocksHigh[source_size];
if (block.height4x4 <= source_height4x4) {
const int row_offset = -(block.row4x4 & (source_height4x4 - 1));
if (row_offset < 0) top_left = false;
AddSample(block, 0, -1, num_warp_samples, num_samples_scanned,
candidates);
} else {
for (int i = 0; i < std::min(static_cast<int>(block.height4x4),
tile.frame_header().rows4x4 - block.row4x4);
i += step) {
source_size =
tile.Parameters(block.row4x4 + i, block.column4x4 - 1).size;
step = std::min(static_cast<int>(block.height4x4),
static_cast<int>(kNum4x4BlocksHigh[source_size]));
AddSample(block, i, -1, num_warp_samples, num_samples_scanned,
candidates);
}
}
}
if (top_left) {
AddSample(block, -1, -1, num_warp_samples, num_samples_scanned, candidates);
}
if (top_right && block.size <= kBlock64x64) {
AddSample(block, -1, block.width4x4, num_warp_samples, num_samples_scanned,
candidates);
}
if (*num_warp_samples == 0 && *num_samples_scanned > 0) *num_warp_samples = 1;
}
void SetupMotionField(
const ObuFrameHeader& frame_header, const RefCountedBuffer& current_frame,
const std::array<RefCountedBufferPtr, kNumReferenceFrameTypes>&
reference_frames,
int row4x4_start, int row4x4_end, int column4x4_start, int column4x4_end,
TemporalMotionField* const motion_field) {
assert(frame_header.use_ref_frame_mvs);
const int y8_start = DivideBy2(row4x4_start);
const int y8_end = DivideBy2(std::min(row4x4_end, frame_header.rows4x4));
const int x8_start = DivideBy2(column4x4_start);
const int x8_end =
DivideBy2(std::min(column4x4_end, frame_header.columns4x4));
const int last_index = frame_header.reference_frame_index[0];
const ReferenceInfo& reference_info = *current_frame.reference_info();
if (!IsIntraFrame(reference_frames[last_index]->frame_type())) {
const int last_alternate_order_hint =
reference_frames[last_index]
->reference_info()
->order_hint[kReferenceFrameAlternate];
const int current_gold_order_hint =
reference_info.order_hint[kReferenceFrameGolden];
if (last_alternate_order_hint != current_gold_order_hint) {
const int reference_offset_last =
-reference_info.relative_distance_from[kReferenceFrameLast];
if (std::abs(reference_offset_last) <= kMaxFrameDistance) {
MotionFieldProjection(frame_header, reference_frames,
kReferenceFrameLast, reference_offset_last, -1,
y8_start, y8_end, x8_start, x8_end, motion_field);
}
}
}
int ref_stamp = 1;
const int reference_offset_backward =
reference_info.relative_distance_from[kReferenceFrameBackward];
if (reference_offset_backward > 0 &&
MotionFieldProjection(frame_header, reference_frames,
kReferenceFrameBackward, reference_offset_backward,
0, y8_start, y8_end, x8_start, x8_end,
motion_field)) {
--ref_stamp;
}
const int reference_offset_alternate2 =
reference_info.relative_distance_from[kReferenceFrameAlternate2];
if (reference_offset_alternate2 > 0 &&
MotionFieldProjection(frame_header, reference_frames,
kReferenceFrameAlternate2,
reference_offset_alternate2, 0, y8_start, y8_end,
x8_start, x8_end, motion_field)) {
--ref_stamp;
}
if (ref_stamp >= 0) {
const int reference_offset_alternate =
reference_info.relative_distance_from[kReferenceFrameAlternate];
if (reference_offset_alternate > 0 &&
MotionFieldProjection(frame_header, reference_frames,
kReferenceFrameAlternate,
reference_offset_alternate, 0, y8_start, y8_end,
x8_start, x8_end, motion_field)) {
--ref_stamp;
}
}
if (ref_stamp >= 0) {
const int reference_offset_last2 =
-reference_info.relative_distance_from[kReferenceFrameLast2];
if (std::abs(reference_offset_last2) <= kMaxFrameDistance) {
MotionFieldProjection(frame_header, reference_frames,
kReferenceFrameLast2, reference_offset_last2, -1,
y8_start, y8_end, x8_start, x8_end, motion_field);
}
}
}
} // namespace libgav1