// 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 #include #include #include #include #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(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& 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& 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(width4x4), tile.frame_header().columns4x4 - block.column4x4, 16}); do { const BlockParameters& mv_bp = **bps; const int step = std::max( std::min(width4x4, static_cast(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(height4x4), tile.frame_header().rows4x4 - block.row4x4, 16}); do { const BlockParameters& mv_bp = **bps; const int step = std::max( std::min(height4x4, static_cast(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(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(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(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(block.height4x4), 16); const int column_end = column_start + std::min(static_cast(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& 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& 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(block.width4x4), tile.frame_header().columns4x4 - block.column4x4, static_cast(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(found_new_mv); *reference_mv_context = 2 + total_matches; break; default: *new_mv_context = 5 - static_cast(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& 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(found_row_match) + static_cast(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(found_row_match) + static_cast(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(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(block.width4x4), static_cast(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(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(block.height4x4), static_cast(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& 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