// Copyright 2015 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
//
// This file contains an implementation of a VP9 bitstream parser.
//
// VERBOSE level:
//  1 something wrong in bitstream
//  2 parsing steps
//  3 parsed values (selected)

#include "media/parsers/vp9_parser.h"

#include <algorithm>
#include <array>
#include <ranges>

#include "base/compiler_specific.h"
#include "base/containers/circular_deque.h"
#include "base/containers/span.h"
#include "base/containers/span_reader.h"
#include "base/functional/bind.h"
#include "base/logging.h"
#include "base/numerics/byte_conversions.h"
#include "base/numerics/checked_math.h"
#include "base/numerics/safe_conversions.h"
#include "media/parsers/vp9_uncompressed_header_parser.h"

namespace media {

namespace {

// Coefficients extracted verbatim from "VP9 Bitstream & Decoding Process
// Specification" Version 0.6, Sec 8.6.1 Dequantization functions, see:
// https://www.webmproject.org/vp9/#draft-vp9-bitstream-and-decoding-process-specification
constexpr size_t kQIndexRange = 256;
// clang-format off
// libva is the only user of high bit depth VP9 formats and only supports
// 10 bits per component, see https://github.com/01org/libva/issues/137.
// TODO(mcasas): Add the 12 bit versions of these tables.
constexpr auto kDcQLookup = std::to_array<std::array<const int16_t, kQIndexRange>>({
    {
        4,    8,    8,    9,    10,   11,   12,   12,  13,   14,   15,   16,
        17,   18,   19,   19,   20,   21,   22,   23,  24,   25,   26,   26,
        27,   28,   29,   30,   31,   32,   32,   33,  34,   35,   36,   37,
        38,   38,   39,   40,   41,   42,   43,   43,  44,   45,   46,   47,
        48,   48,   49,   50,   51,   52,   53,   53,  54,   55,   56,   57,
        57,   58,   59,   60,   61,   62,   62,   63,  64,   65,   66,   66,
        67,   68,   69,   70,   70,   71,   72,   73,  74,   74,   75,   76,
        77,   78,   78,   79,   80,   81,   81,   82,  83,   84,   85,   85,
        87,   88,   90,   92,   93,   95,   96,   98,  99,   101,  102,  104,
        105,  107,  108,  110,  111,  113,  114,  116, 117,  118,  120,  121,
        123,  125,  127,  129,  131,  134,  136,  138, 140,  142,  144,  146,
        148,  150,  152,  154,  156,  158,  161,  164, 166,  169,  172,  174,
        177,  180,  182,  185,  187,  190,  192,  195, 199,  202,  205,  208,
        211,  214,  217,  220,  223,  226,  230,  233, 237,  240,  243,  247,
        250,  253,  257,  261,  265,  269,  272,  276, 280,  284,  288,  292,
        296,  300,  304,  309,  313,  317,  322,  326, 330,  335,  340,  344,
        349,  354,  359,  364,  369,  374,  379,  384, 389,  395,  400,  406,
        411,  417,  423,  429,  435,  441,  447,  454, 461,  467,  475,  482,
        489,  497,  505,  513,  522,  530,  539,  549, 559,  569,  579,  590,
        602,  614,  626,  640,  654,  668,  684,  700, 717,  736,  755,  775,
        796,  819,  843,  869,  896,  925,  955,  988, 1022, 1058, 1098, 1139,
        1184, 1232, 1282, 1336,
    },
    {
        4,    9,    10,   13,   15,   17,   20,   22,   25,   28,   31,   34,
        37,   40,   43,   47,   50,   53,   57,   60,   64,   68,   71,   75,
        78,   82,   86,   90,   93,   97,   101,  105,  109,  113,  116,  120,
        124,  128,  132,  136,  140,  143,  147,  151,  155,  159,  163,  166,
        170,  174,  178,  182,  185,  189,  193,  197,  200,  204,  208,  212,
        215,  219,  223,  226,  230,  233,  237,  241,  244,  248,  251,  255,
        259,  262,  266,  269,  273,  276,  280,  283,  287,  290,  293,  297,
        300,  304,  307,  310,  314,  317,  321,  324,  327,  331,  334,  337,
        343,  350,  356,  362,  369,  375,  381,  387,  394,  400,  406,  412,
        418,  424,  430,  436,  442,  448,  454,  460,  466,  472,  478,  484,
        490,  499,  507,  516,  525,  533,  542,  550,  559,  567,  576,  584,
        592,  601,  609,  617,  625,  634,  644,  655,  666,  676,  687,  698,
        708,  718,  729,  739,  749,  759,  770,  782,  795,  807,  819,  831,
        844,  856,  868,  880,  891,  906,  920,  933,  947,  961,  975,  988,
        1001, 1015, 1030, 1045, 1061, 1076, 1090, 1105, 1120, 1137, 1153, 1170,
        1186, 1202, 1218, 1236, 1253, 1271, 1288, 1306, 1323, 1342, 1361, 1379,
        1398, 1416, 1436, 1456, 1476, 1496, 1516, 1537, 1559, 1580, 1601, 1624,
        1647, 1670, 1692, 1717, 1741, 1766, 1791, 1817, 1844, 1871, 1900, 1929,
        1958, 1990, 2021, 2054, 2088, 2123, 2159, 2197, 2236, 2276, 2319, 2363,
        2410, 2458, 2508, 2561, 2616, 2675, 2737, 2802, 2871, 2944, 3020, 3102,
        3188, 3280, 3375, 3478, 3586, 3702, 3823, 3953, 4089, 4236, 4394, 4559,
        4737, 4929, 5130, 5347
   }
});

constexpr auto kAcQLookup = std::to_array<std::array<const int16_t, kQIndexRange>>({
    {
        4,    8,    9,    10,   11,   12,   13,   14,   15,   16,   17,   18,
        19,   20,   21,   22,   23,   24,   25,   26,   27,   28,   29,   30,
        31,   32,   33,   34,   35,   36,   37,   38,   39,   40,   41,   42,
        43,   44,   45,   46,   47,   48,   49,   50,   51,   52,   53,   54,
        55,   56,   57,   58,   59,   60,   61,   62,   63,   64,   65,   66,
        67,   68,   69,   70,   71,   72,   73,   74,   75,   76,   77,   78,
        79,   80,   81,   82,   83,   84,   85,   86,   87,   88,   89,   90,
        91,   92,   93,   94,   95,   96,   97,   98,   99,   100,  101,  102,
        104,  106,  108,  110,  112,  114,  116,  118,  120,  122,  124,  126,
        128,  130,  132,  134,  136,  138,  140,  142,  144,  146,  148,  150,
        152,  155,  158,  161,  164,  167,  170,  173,  176,  179,  182,  185,
        188,  191,  194,  197,  200,  203,  207,  211,  215,  219,  223,  227,
        231,  235,  239,  243,  247,  251,  255,  260,  265,  270,  275,  280,
        285,  290,  295,  300,  305,  311,  317,  323,  329,  335,  341,  347,
        353,  359,  366,  373,  380,  387,  394,  401,  408,  416,  424,  432,
        440,  448,  456,  465,  474,  483,  492,  501,  510,  520,  530,  540,
        550,  560,  571,  582,  593,  604,  615,  627,  639,  651,  663,  676,
        689,  702,  715,  729,  743,  757,  771,  786,  801,  816,  832,  848,
        864,  881,  898,  915,  933,  951,  969,  988,  1007, 1026, 1046, 1066,
        1087, 1108, 1129, 1151, 1173, 1196, 1219, 1243, 1267, 1292, 1317, 1343,
        1369, 1396, 1423, 1451, 1479, 1508, 1537, 1567, 1597, 1628, 1660, 1692,
        1725, 1759, 1793, 1828,
    },
    {
        4,    9,    11,   13,   16,   18,   21,   24,   27,   30,   33,   37,
        40,   44,   48,   51,   55,   59,   63,   67,   71,   75,   79,   83,
        88,   92,   96,   100,  105,  109,  114,  118,  122,  127,  131,  136,
        140,  145,  149,  154,  158,  163,  168,  172,  177,  181,  186,  190,
        195,  199,  204,  208,  213,  217,  222,  226,  231,  235,  240,  244,
        249,  253,  258,  262,  267,  271,  275,  280,  284,  289,  293,  297,
        302,  306,  311,  315,  319,  324,  328,  332,  337,  341,  345,  349,
        354,  358,  362,  367,  371,  375,  379,  384,  388,  392,  396,  401,
        409,  417,  425,  433,  441,  449,  458,  466,  474,  482,  490,  498,
        506,  514,  523,  531,  539,  547,  555,  563,  571,  579,  588,  596,
        604,  616,  628,  640,  652,  664,  676,  688,  700,  713,  725,  737,
        749,  761,  773,  785,  797,  809,  825,  841,  857,  873,  889,  905,
        922,  938,  954,  970,  986,  1002, 1018, 1038, 1058, 1078, 1098, 1118,
        1138, 1158, 1178, 1198, 1218, 1242, 1266, 1290, 1314, 1338, 1362, 1386,
        1411, 1435, 1463, 1491, 1519, 1547, 1575, 1603, 1631, 1663, 1695, 1727,
        1759, 1791, 1823, 1859, 1895, 1931, 1967, 2003, 2039, 2079, 2119, 2159,
        2199, 2239, 2283, 2327, 2371, 2415, 2459, 2507, 2555, 2603, 2651, 2703,
        2755, 2807, 2859, 2915, 2971, 3027, 3083, 3143, 3203, 3263, 3327, 3391,
        3455, 3523, 3591, 3659, 3731, 3803, 3876, 3952, 4028, 4104, 4184, 4264,
        4348, 4432, 4516, 4604, 4692, 4784, 4876, 4972, 5068, 5168, 5268, 5372,
        5476, 5584, 5692, 5804, 5916, 6032, 6148, 6268, 6388, 6512, 6640, 6768,
        6900, 7036, 7172, 7312
   }
});
// clang-format on

static_assert(std::size(kDcQLookup[0]) == std::size(kAcQLookup[0]),
              "quantizer lookup arrays of incorrect size");

size_t ClampQ(int64_t q) {
  return q < 0 ? 0
               : base::checked_cast<size_t>(
                     std::min(q, static_cast<int64_t>(kQIndexRange - 1)));
}

int ClampLf(int lf) {
  constexpr int kMaxLoopFilterLevel = 63;
  return std::clamp(lf, 0, kMaxLoopFilterLevel);
}

std::string IncrementIV(std::string_view iv, uint32_t by) {
  // What we call the 'IV' value is actually somewhat of a misnomer:
  // "IV" = 0xFFFFFFFFFFFFFFFF0000000000000000
  //          └──actual IV───┘└─block counter┘
  //
  // We want to 'increment' this structure by incrementing just the block
  // counter. We pull out the block counter, convert to native endian,
  // increment, convert back to big endian and write it back into the byte
  // array. Then we return the byte array as a string.
  //
  // `by` is usually going to be the number of blocks (aka 16 byte chunks)
  //      of cipher data.
  DCHECK_EQ(iv.size(), 16u);
  std::array<uint8_t, 16u> bytes;
  base::span(bytes).copy_from(base::as_byte_span(iv).first<16u>());
  auto counter_bytes = base::span(bytes).last<8u>();
  counter_bytes.copy_from(
      base::U64ToBigEndian(base::U64FromBigEndian(counter_bytes) + by));
  return std::string(bytes.begin(), bytes.end());
}

// |frame_size|: The size of the current frame; this controls how long we
//               loop through the subsamples.
// |current_subsample_index|: An index into the |subsamples| vector, we need
//                            to have this saved between function calls.
// |extra_clear_bytes|: The previous call may have set this variable to show
//                      that a subsample mey have already started being parsed
//                      and that only X bytes of free data are left in it.
// |base_decrypt_config|: Not an output parameter, it is just a raw ptr from a
//                        unique_ptr.
// |subsamples|: A vector of subsamples.
// |iv|: The initialization vector (128bit number stored as std::string). This
//       gets incremented by (cipher_bytes % 16) for each frame, and must be
//       preserved across function calls.
std::unique_ptr<DecryptConfig> SplitSubsamples(
    uint32_t frame_size,
    size_t* current_subsample_index,
    size_t* extra_clear_subsample_bytes,
    const DecryptConfig* base_decrypt_config,
    const std::vector<SubsampleEntry>& subsamples,
    std::string* iv) {
  // We copy iv so that we can use the starting value in our
  // new config while still incrementing IV for the next frame.
  std::string frame_dc_iv = *iv;
  std::vector<SubsampleEntry> frame_dc_subsamples;
  do {
    if (*current_subsample_index >= subsamples.size()) {
      DVLOG(1) << "Not enough subsamples in the superframe decrypt config";
      return nullptr;
    }

    uint32_t subsample_clear = subsamples[*current_subsample_index].clear_bytes;
    uint32_t subsample_cipher =
        subsamples[*current_subsample_index].cypher_bytes;

    // if clear+cipher bytes would be over the max of uint32_t, we need to
    // quit immediately, to prevent malicious overflowing.
    if (!base::CheckAdd(subsample_clear, subsample_cipher).IsValid()) {
      DVLOG(1) << "Invalid subsample alignment";
      return nullptr;
    }

    // It's possible that the previous frame didn't use all the clear bytes
    // in this subsample, in which case we have to start from midway through
    // the clear section.
    if (*extra_clear_subsample_bytes) {
      subsample_clear = *extra_clear_subsample_bytes;
    }

    if (subsample_clear > frame_size) {
      // Support scenario where clear section is larger than our frame:
      // The entire length is clear. If |subsample_clear| is the same length,
      // we handle it below.
      frame_dc_subsamples.push_back(SubsampleEntry(frame_size, 0));
      *extra_clear_subsample_bytes = subsample_clear - frame_size;
      frame_size = 0;
    } else if (subsample_clear + subsample_cipher > frame_size) {
      // Only a clear section can cross over a frame boundary, otherwise
      // the frame header for the next frame would be encrypted, which is not
      // spec compliant.
      DVLOG(1) << "Invalid subsample alignment";
      return nullptr;
    } else if (subsample_clear + subsample_cipher <= frame_size) {
      // In this case a subsample is less than or equal to a whole frame
      // This is the most likely case for almost all encrypted media.
      // note that |subsample_cipher| can be 0.
      frame_dc_subsamples.push_back(
          SubsampleEntry(subsample_clear, subsample_cipher));
      frame_size -= (subsample_clear + subsample_cipher);
      *extra_clear_subsample_bytes = 0;

      // IV gets incremented by 1 for every 16 bytes of cypher
      *iv = IncrementIV(*iv, subsample_cipher >> 4);  // uint32 logical shift.
    }

    // Don't go to the next subsample if there are more clear bytes.
    if (!*extra_clear_subsample_bytes) {
      (*current_subsample_index)++;
    }

    // It is possible for there to be more than one subsample associated
    // with a single frame, so we need to try again if there are more bytes
    // left unaccounted for in this frame.
  } while (frame_size);

  return base_decrypt_config->CopyNewSubsamplesIV(frame_dc_subsamples,
                                                  frame_dc_iv);
}

bool IsByteNEncrypted(size_t byte,
                      const std::vector<SubsampleEntry>& subsamples) {
  size_t original_byte = byte;
  for (const SubsampleEntry& subsample : subsamples) {
    if (byte < 0) {
      return false;
    }
    if (byte < subsample.clear_bytes) {
      return false;
    }
    byte -= subsample.clear_bytes;
    if (byte < subsample.cypher_bytes) {
      return true;
    }
    byte -= subsample.cypher_bytes;
  }
  DVLOG(3) << "Subsamples do not extend to cover offset " << original_byte;
  return false;
}

template <typename T>
bool ContainsZero(const T& data) {
  base::span<const uint8_t> span = base::as_byte_span(data);
  // TODO(crbug.com/40284755): We should compare the performance differences
  // between `memchr` and `std::range::find`.
  return UNSAFE_TODO(memchr(span.data(), 0, span.size())) != nullptr;
}

}  // namespace

Vp9SegmentationParams::Vp9SegmentationParams() = default;
Vp9SegmentationParams::Vp9SegmentationParams(const Vp9SegmentationParams&) =
    default;
Vp9SegmentationParams::Vp9SegmentationParams(Vp9SegmentationParams&&) = default;
Vp9SegmentationParams& Vp9SegmentationParams::operator=(
    const Vp9SegmentationParams&) = default;
Vp9SegmentationParams& Vp9SegmentationParams::operator=(
    Vp9SegmentationParams&&) = default;
Vp9SegmentationParams::~Vp9SegmentationParams() = default;

Vp9FrameHeader::Vp9FrameHeader() = default;
Vp9FrameHeader::Vp9FrameHeader(const Vp9FrameHeader&) = default;
Vp9FrameHeader::Vp9FrameHeader(Vp9FrameHeader&&) = default;
Vp9FrameHeader& Vp9FrameHeader::operator=(const Vp9FrameHeader&) = default;
Vp9FrameHeader& Vp9FrameHeader::operator=(Vp9FrameHeader&&) = default;
Vp9FrameHeader::~Vp9FrameHeader() = default;

bool Vp9FrameHeader::IsKeyframe() const {
  // When show_existing_frame is true, the frame header does not precede an
  // actual frame to be decoded, so frame_type does not apply (and is not read
  // from the stream).
  return !show_existing_frame && frame_type == KEYFRAME;
}

bool Vp9FrameHeader::IsIntra() const {
  return !show_existing_frame && (frame_type == KEYFRAME || intra_only);
}

VideoColorSpace Vp9FrameHeader::GetColorSpace() const {
  gfx::ColorSpace::RangeID range = color_range
                                       ? gfx::ColorSpace::RangeID::FULL
                                       : gfx::ColorSpace::RangeID::LIMITED;
  switch (color_space) {
    case Vp9ColorSpace::RESERVED:
    case Vp9ColorSpace::UNKNOWN:
      return VideoColorSpace(VideoColorSpace::PrimaryID::UNSPECIFIED,
                             VideoColorSpace::TransferID::UNSPECIFIED,
                             VideoColorSpace::MatrixID::UNSPECIFIED, range);
    case Vp9ColorSpace::BT_601:
    case Vp9ColorSpace::SMPTE_170:
      return VideoColorSpace(VideoColorSpace::PrimaryID::SMPTE170M,
                             VideoColorSpace::TransferID::SMPTE170M,
                             VideoColorSpace::MatrixID::SMPTE170M, range);
    case Vp9ColorSpace::BT_709:
      return VideoColorSpace(VideoColorSpace::PrimaryID::BT709,
                             VideoColorSpace::TransferID::BT709,
                             VideoColorSpace::MatrixID::BT709, range);
    case Vp9ColorSpace::SMPTE_240:
      return VideoColorSpace(VideoColorSpace::PrimaryID::SMPTE240M,
                             VideoColorSpace::TransferID::SMPTE240M,
                             VideoColorSpace::MatrixID::SMPTE240M, range);
    case Vp9ColorSpace::BT_2020:
      return VideoColorSpace(VideoColorSpace::PrimaryID::BT2020,
                             VideoColorSpace::TransferID::BT2020_10,
                             VideoColorSpace::MatrixID::BT2020_NCL, range);
    case Vp9ColorSpace::SRGB:
      return VideoColorSpace(VideoColorSpace::PrimaryID::BT709,
                             VideoColorSpace::TransferID::IEC61966_2_1,
                             VideoColorSpace::MatrixID::BT709, range);
  }
  return VideoColorSpace();
}

Vp9Parser::FrameInfo::FrameInfo() = default;

Vp9Parser::FrameInfo::FrameInfo(base::span<const uint8_t> input)
    : data(input) {}

Vp9Parser::FrameInfo::FrameInfo(FrameInfo&& other) = default;

Vp9Parser::FrameInfo& Vp9Parser::FrameInfo::operator=(FrameInfo&& other) =
    default;

Vp9Parser::FrameInfo::~FrameInfo() = default;

bool Vp9FrameContext::IsValid() const {
  // probs should be in [1, 255] range.
  static_assert(sizeof(Vp9Prob) == 1,
                "following checks assuming Vp9Prob is single byte");
  if (ContainsZero(tx_probs_8x8)) {
    return false;
  }
  if (ContainsZero(tx_probs_16x16)) {
    return false;
  }
  if (ContainsZero(tx_probs_32x32)) {
    return false;
  }

  for (auto& a : coef_probs) {
    for (auto& ai : a) {
      for (auto& aj : ai) {
        auto [dc, ac] = base::span(aj).split_at<1u>();
        if (std::ranges::contains(
                base::as_byte_span(base::span(dc[0]).first<3u>()), 0)) {
          return false;
        }
        if (std::ranges::contains(base::as_byte_span(ac), 0)) {
          return false;
        }
      }
    }
  }
  if (ContainsZero(skip_prob)) {
    return false;
  }
  if (ContainsZero(inter_mode_probs)) {
    return false;
  }
  if (ContainsZero(interp_filter_probs)) {
    return false;
  }
  if (ContainsZero(is_inter_prob)) {
    return false;
  }
  if (ContainsZero(comp_mode_prob)) {
    return false;
  }
  if (ContainsZero(single_ref_prob)) {
    return false;
  }
  if (ContainsZero(comp_ref_prob)) {
    return false;
  }
  if (ContainsZero(y_mode_probs)) {
    return false;
  }
  if (ContainsZero(uv_mode_probs)) {
    return false;
  }
  if (ContainsZero(partition_probs)) {
    return false;
  }
  if (ContainsZero(mv_joint_probs)) {
    return false;
  }
  if (ContainsZero(mv_sign_prob)) {
    return false;
  }
  if (ContainsZero(mv_class_probs)) {
    return false;
  }
  if (ContainsZero(mv_class0_bit_prob)) {
    return false;
  }
  if (ContainsZero(mv_bits_prob)) {
    return false;
  }
  if (ContainsZero(mv_class0_fr_probs)) {
    return false;
  }
  if (ContainsZero(mv_fr_probs)) {
    return false;
  }
  if (ContainsZero(mv_class0_hp_prob)) {
    return false;
  }
  if (ContainsZero(mv_hp_prob)) {
    return false;
  }

  return true;
}

void Vp9Parser::Context::Reset() {
  segmentation_ = {};
  loop_filter_ = {};
  ref_slots_ = {};
}

const Vp9Parser::ReferenceSlot& Vp9Parser::Context::GetRefSlot(
    size_t ref_type) const {
  DCHECK_LT(ref_type, std::size(ref_slots_));
  return ref_slots_[ref_type];
}

void Vp9Parser::Context::UpdateRefSlot(
    size_t ref_type,
    const Vp9Parser::ReferenceSlot& ref_slot) {
  DCHECK_LT(ref_type, std::size(ref_slots_));
  ref_slots_[ref_type] = ref_slot;
}

Vp9Parser::Vp9Parser() {
  Reset();
}

Vp9Parser::~Vp9Parser() = default;

void Vp9Parser::SetStream(base::span<const uint8_t> stream,
                          const std::vector<uint32_t>& spatial_layer_frame_size,
                          std::unique_ptr<DecryptConfig> stream_config) {
  DCHECK(stream.data());
  stream_ = stream;
  frames_.clear();
  spatial_layer_frame_size_ = spatial_layer_frame_size;
  stream_decrypt_config_ = std::move(stream_config);
}

void Vp9Parser::SetStream(base::span<const uint8_t> stream,
                          std::unique_ptr<DecryptConfig> stream_config) {
  SetStream(stream, {}, std::move(stream_config));
}

void Vp9Parser::Reset() {
  stream_ = {};
  frames_.clear();
  spatial_layer_frame_size_.clear();

  context_.Reset();
}

bool Vp9Parser::ParseUncompressedHeader(const FrameInfo& frame_info,
                                        Vp9FrameHeader* fhdr,
                                        Result* result,
                                        Vp9Parser::Context* context) {
  curr_frame_header_ = {};
  *result = kInvalidStream;

  Vp9UncompressedHeaderParser uncompressed_parser(context);
  if (!uncompressed_parser.Parse(frame_info.data, &curr_frame_header_)) {
    *result = kInvalidStream;
    return true;
  }

  if (curr_frame_header_.header_size_in_bytes == 0) {
    // Verify padding bits are zero.
    const bool is_padding_bit_all_zero = std::ranges::all_of(
        frame_info.data.subspan(curr_frame_header_.uncompressed_header_size),
        [](const auto& v) { return v == 0; });
    if (!is_padding_bit_all_zero) {
      DVLOG(1) << "Padding bits are not zeros.";
      *result = kInvalidStream;
      return true;
    }
    *fhdr = curr_frame_header_;
    *result = kOk;
    return true;
  }

  size_t total_header_size;
  base::CheckedNumeric<size_t> total_header_size_checked =
      curr_frame_header_.uncompressed_header_size;
  total_header_size_checked += curr_frame_header_.header_size_in_bytes;
  if (!total_header_size_checked.AssignIfValid(&total_header_size) ||
      total_header_size > base::checked_cast<size_t>(frame_info.data.size())) {
    DVLOG(1) << "header_size_in_bytes="
             << curr_frame_header_.header_size_in_bytes
             << " is larger than bytes left in buffer: "
             << frame_info.data.size() -
                    curr_frame_header_.uncompressed_header_size;
    *result = kInvalidStream;
    return true;
  }

  return false;
}

Vp9Parser::Result Vp9Parser::ParseNextFrame(
    Vp9FrameHeader* fhdr,
    gfx::Size* allocate_size,
    std::unique_ptr<DecryptConfig>* frame_decrypt_config) {
  DCHECK(fhdr);
  DCHECK(allocate_size);
  DVLOG(2) << "ParseNextFrame";
  FrameInfo frame_info;
  Result result;

  if (frames_.empty()) {
    // No frames to be decoded, if there is no more stream, request more.
    if (stream_.empty()) {
      return kEOStream;
    }

    // New stream to be parsed, parse it and fill frames_.
    if (!spatial_layer_frame_size_.empty()) {
      // If it is SVC stream, we have to parse the stream with
      // |spatial_layer_frame_size_|.
      frames_ = ParseSVCFrame();
    } else {
      frames_ = ParseSuperframe();
    }

    if (frames_.empty()) {
      DVLOG(1) << "Failed parsing superframes/SVC frame";
      return kInvalidStream;
    }
  }

  frame_info = std::move(frames_.front());
  frames_.pop_front();
  if (frame_decrypt_config) {
    if (frame_info.decrypt_config) {
      *frame_decrypt_config = frame_info.decrypt_config->Clone();
    } else {
      *frame_decrypt_config = nullptr;
    }
  }

  if (ParseUncompressedHeader(frame_info, fhdr, &result, &context_)) {
    return result;
  }

  if (!SetupSegmentationDequant()) {
    return kInvalidStream;
  }
  SetupLoopFilter();
  UpdateSlots(&context_);

  *fhdr = curr_frame_header_;
  // show_frame must be true for the last frame, otherwise false in SVC frame.
  if (!spatial_layer_frame_size_.empty()) {
    fhdr->show_frame = frames_.empty();
  }

  if (frame_info.allocate_size.IsEmpty()) {
    allocate_size->SetSize(fhdr->frame_width, fhdr->frame_height);
  } else {
    *allocate_size = frame_info.allocate_size;
  }

  return kOk;
}

std::unique_ptr<DecryptConfig> Vp9Parser::NextFrameDecryptContextForTesting() {
  if (frames_.empty()) {
    // No frames to be decoded, if there is no more stream, request more.
    if (stream_.empty()) {
      return nullptr;
    }

    // New stream to be parsed, parse it and fill frames_.
    frames_ = ParseSuperframe();
    if (frames_.empty()) {
      return nullptr;
    }
  }
  FrameInfo frame_info = std::move(frames_.front());
  frames_.pop_front();
  return std::move(frame_info.decrypt_config);
}

std::string Vp9Parser::IncrementIVForTesting(std::string_view iv, uint32_t by) {
  return IncrementIV(iv, by);
}

// static
bool Vp9Parser::IsSuperframe(base::span<const uint8_t> stream,
                             const DecryptConfig* decrypt_config) {
  if (stream.size() < 1) {
    return false;
  }

  // The marker byte might be encrypted, in which case we should treat
  // the stream as a single frame.
  size_t marker_offset = stream.size() - 1;
  if (decrypt_config &&
      IsByteNEncrypted(marker_offset, decrypt_config->subsamples())) {
    return false;
  }

  // If this is a superframe, the last byte in the stream will contain the
  // superframe marker. If not, the whole buffer contains a single frame.
  uint8_t marker = stream.back();
  return ((marker & 0xe0) == 0xc0);
}

// static
base::circular_deque<Vp9Parser::FrameInfo> Vp9Parser::ExtractFrames(
    base::span<const uint8_t> stream,
    const DecryptConfig* decrypt_config) {
  base::circular_deque<FrameInfo> frames;

  if (stream.size() < 1) {
    return frames;
  }

  if (!IsSuperframe(stream, decrypt_config)) {
    frames.push_back(FrameInfo(stream));
    if (decrypt_config) {
      frames[0].decrypt_config = decrypt_config->Clone();
    }
    return frames;
  }

  const uint8_t marker = stream.back();

  DVLOG(1) << "Parsing a superframe";

  // The bytes immediately before the superframe marker constitute superframe
  // index, which stores information about sizes of each frame in it.
  // Calculate its size and set index_ptr to the beginning of it.
  const size_t num_frames = (marker & 0x7) + 1;
  const size_t mag = ((marker >> 3) & 0x3) + 1;
  const size_t index_size = 2 + mag * num_frames;

  if (stream.size() < index_size) {
    return base::circular_deque<FrameInfo>();
  }

  auto [frame_buffer, index] = stream.split_at(stream.size() - index_size);
  if (marker != index[0]) {
    return base::circular_deque<FrameInfo>();
  }

  base::SpanReader index_reader(index.subspan<1u>());
  base::SpanReader frame_reader(frame_buffer);

  // Parse frame information contained in the index and add a pointer to and
  // size of each frame to frames.

  // Use this to calculate the per-frame IV value.
  std::string iv;
  std::vector<SubsampleEntry> subsamples;
  size_t current_subsample = 0;
  size_t extra_clear_subsample_bytes = 0;
  if (decrypt_config) {
    iv = decrypt_config->iv();
    subsamples = decrypt_config->subsamples();
  }

  for (size_t i = 0; i < num_frames; ++i) {
    uint32_t size = 0;
    for (size_t j = 0; j < mag; ++j) {
      uint8_t value = 0;
      index_reader.ReadU8LittleEndian(value);
      size |= static_cast<uint32_t>(value) << (j * 8);
    }

    if (size > frame_reader.remaining()) {
      DVLOG(1) << "Not enough data in the buffer for frame " << i;
      frames.clear();
      return frames;
    }

    FrameInfo frame = FrameInfo(frame_reader.Read(size).value());
    if (subsamples.size()) {
      std::unique_ptr<DecryptConfig> frame_dc = SplitSubsamples(
          size, &current_subsample, &extra_clear_subsample_bytes,
          decrypt_config, subsamples, &iv);
      if (!frame_dc) {
        DVLOG(1) << "Failed to calculate decrypt config for frame " << i;
        frames.clear();
        return frames;
      }

      frame.decrypt_config = std::move(frame_dc);
    }

    frames.push_back(std::move(frame));

    DVLOG(1) << "Frame " << i << ", size: " << size;
  }

  return frames;
}

// Annex B Superframes
base::circular_deque<Vp9Parser::FrameInfo> Vp9Parser::ParseSuperframe() {
  base::span<const uint8_t> stream = stream_;

  // Make sure we don't parse stream_ more than once.
  stream_ = {};

  return ExtractFrames(stream, stream_decrypt_config_.get());
}

base::circular_deque<Vp9Parser::FrameInfo> Vp9Parser::ParseSVCFrame() {
  if (stream_decrypt_config_) {
    LOG(ERROR) << "Encrypted frame with SVC stream is not supported";
    return {};
  }

  base::span<const uint8_t> stream = stream_;

  // Make sure we don't parse stream_ more than once.
  stream_ = {};

  base::circular_deque<FrameInfo> frames;

  for (size_t i = 0; i < spatial_layer_frame_size_.size(); i++) {
    const uint32_t size = spatial_layer_frame_size_[i];
    if (size > stream.size()) {
      DVLOG(1) << "Not enough data in the buffer for frame " << i;
      return {};
    }

    auto [frame, remaining] = stream.split_at(size);
    frames.emplace_back(frame);
    stream = remaining;
    DVLOG(1) << "Frame " << i << ", size: " << size;
  }

  DCHECK(!frames.empty());

  gfx::Size max_frame_size;

  // Context is not copyable because it has base::WeakPtrFactory. The weak
  // pointer is necessary to update context for compressed header. To parse
  // uncompressed header, |segmentation_|, |loop_filter| and |ref_slots_| are
  // sufficient. Copy the variables manually here.
  Context tmp_context;
  tmp_context.segmentation_ = context_.segmentation_;
  tmp_context.loop_filter_ = context_.loop_filter_;
  base::span(tmp_context.ref_slots_)
      .copy_from_nonoverlapping(context_.ref_slots_);
  for (const auto& frame_info : frames) {
    // |curr_frame_header_| is used safely because it is reset every
    // ParseUncompressedHeader().
    Vp9FrameHeader dummy_fhdr;
    Result result;
    if (ParseUncompressedHeader(frame_info, &dummy_fhdr, &result,
                                &tmp_context) &&
        result != kOk) {
      return {};
    }
    UpdateSlots(&tmp_context);
    max_frame_size.SetToMax(gfx::Size(curr_frame_header_.frame_width,
                                      curr_frame_header_.frame_height));
  }

  for (auto& frame_info : frames) {
    frame_info.allocate_size = max_frame_size;
  }
  return frames;
}

// 8.6.1 Dequantization functions
int64_t Vp9Parser::GetQIndex(const Vp9QuantizationParams& quant,
                             size_t segid) const {
  const Vp9SegmentationParams& segmentation = context_.segmentation();

  if (segmentation.FeatureEnabled(segid,
                                  Vp9SegmentationParams::SEG_LVL_ALT_Q)) {
    int16_t feature_data =
        segmentation.FeatureData(segid, Vp9SegmentationParams::SEG_LVL_ALT_Q);
    int64_t q_index = segmentation.abs_or_delta_update
                          ? feature_data
                          : quant.base_q_idx + feature_data;
    return ClampQ(q_index);
  }
  return quant.base_q_idx;
}

// 8.6.1 Dequantization functions
bool Vp9Parser::SetupSegmentationDequant() {
  const Vp9QuantizationParams& quant = curr_frame_header_.quant_params;
  Vp9SegmentationParams& segmentation = context_.segmentation_;

  if (curr_frame_header_.bit_depth > 10) {
    DLOG(ERROR) << "bit_depth > 10 is not supported yet, kDcQLookup and "
                   "kAcQLookup need to be extended";
    return false;
  }
  const size_t bit_depth_index = (curr_frame_header_.bit_depth == 8) ? 0 : 1;

  if (segmentation.enabled) {
    for (size_t i = 0; i < Vp9SegmentationParams::kNumSegments; ++i) {
      const int64_t q_index = GetQIndex(quant, i);
      segmentation.y_dequant[i][0] =
          kDcQLookup[bit_depth_index][ClampQ(q_index + quant.delta_q_y_dc)];
      segmentation.y_dequant[i][1] =
          kAcQLookup[bit_depth_index][ClampQ(q_index)];
      segmentation.uv_dequant[i][0] =
          kDcQLookup[bit_depth_index][ClampQ(q_index + quant.delta_q_uv_dc)];
      segmentation.uv_dequant[i][1] =
          kAcQLookup[bit_depth_index][ClampQ(q_index + quant.delta_q_uv_ac)];
    }
  } else {
    const int64_t q_index = quant.base_q_idx;
    segmentation.y_dequant[0][0] =
        kDcQLookup[bit_depth_index][ClampQ(q_index + quant.delta_q_y_dc)];
    segmentation.y_dequant[0][1] = kAcQLookup[bit_depth_index][ClampQ(q_index)];
    segmentation.uv_dequant[0][0] =
        kDcQLookup[bit_depth_index][ClampQ(q_index + quant.delta_q_uv_dc)];
    segmentation.uv_dequant[0][1] =
        kAcQLookup[bit_depth_index][ClampQ(q_index + quant.delta_q_uv_ac)];
  }
  return true;
}

// 8.8.1 Loop filter frame init process
void Vp9Parser::SetupLoopFilter() {
  Vp9LoopFilterParams& loop_filter = context_.loop_filter_;
  if (!loop_filter.level) {
    return;
  }

  int scale = loop_filter.level < 32 ? 1 : 2;

  std::array<int, Vp9SegmentationParams::kNumSegments> levels;
  for (size_t i = 0; i < Vp9SegmentationParams::kNumSegments; ++i) {
    int level = loop_filter.level;
    const Vp9SegmentationParams& segmentation = context_.segmentation();

    if (segmentation.FeatureEnabled(i, Vp9SegmentationParams::SEG_LVL_ALT_LF)) {
      int feature_data =
          segmentation.FeatureData(i, Vp9SegmentationParams::SEG_LVL_ALT_LF);
      level = ClampLf(segmentation.abs_or_delta_update ? feature_data
                                                       : level + feature_data);
    }
    levels[i] = level;
  }

  if (loop_filter.delta_enabled) {
    for (auto [lvl, level] : std::views::zip(loop_filter.lvl, levels)) {
      lvl[Vp9RefType::VP9_FRAME_INTRA][0] = ClampLf(
          level + loop_filter.ref_deltas[Vp9RefType::VP9_FRAME_INTRA] * scale);
      lvl[Vp9RefType::VP9_FRAME_INTRA][1] = 0;

      auto remain_lvl = base::span(lvl).subspan<1u>();
      auto remain_ref_deltas = base::span(loop_filter.ref_deltas).subspan<1u>();
      DCHECK_EQ(remain_lvl.size(), remain_ref_deltas.size());
      for (auto [lvl_type, delta] :
           std::views::zip(remain_lvl, remain_ref_deltas)) {
        std::ranges::transform(loop_filter.mode_deltas, lvl_type.begin(),
                               ClampLf, [level, delta, scale](auto m) {
                                 return level + (delta + m) * scale;
                               });
      }
    }
  } else {
    for (auto [lvl, level] : std::views::zip(loop_filter.lvl, levels)) {
      std::ranges::fill(base::as_writable_byte_span(lvl), level);
    }
  }
}

void Vp9Parser::UpdateSlots(Vp9Parser::Context* context) {
  // 8.10 Reference frame update process
  for (size_t i = 0; i < kVp9NumRefFrames; i++) {
    if (curr_frame_header_.RefreshFlag(i)) {
      ReferenceSlot ref_slot;
      ref_slot.initialized = true;

      ref_slot.frame_width = curr_frame_header_.frame_width;
      ref_slot.frame_height = curr_frame_header_.frame_height;
      ref_slot.subsampling_x = curr_frame_header_.subsampling_x;
      ref_slot.subsampling_y = curr_frame_header_.subsampling_y;
      ref_slot.bit_depth = curr_frame_header_.bit_depth;

      ref_slot.profile = curr_frame_header_.profile;
      ref_slot.color_space = curr_frame_header_.color_space;
      context->UpdateRefSlot(i, ref_slot);
    }
  }
}

}  // namespace media