// Copyright 2016 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "quiche/http2/hpack/varint/hpack_varint_decoder.h"

// Test HpackVarintDecoder against data encoded via HpackBlockBuilder,
// which uses HpackVarintEncoder under the hood.

#include <stddef.h>

#include <iterator>
#include <set>
#include <utility>
#include <vector>

#include "absl/strings/str_cat.h"
#include "absl/strings/str_format.h"
#include "absl/strings/string_view.h"
#include "quiche/http2/test_tools/hpack_block_builder.h"
#include "quiche/http2/test_tools/random_decoder_test_base.h"
#include "quiche/common/platform/api/quiche_logging.h"
#include "quiche/common/platform/api/quiche_test.h"
#include "quiche/common/quiche_text_utils.h"

using ::testing::AssertionFailure;
using ::testing::AssertionSuccess;

namespace http2 {
namespace test {
namespace {

// Returns the highest value with the specified number of extension bytes
// and the specified prefix length (bits).
uint64_t HiValueOfExtensionBytes(uint32_t extension_bytes,
                                 uint32_t prefix_length) {
  return (1 << prefix_length) - 2 +
         (extension_bytes == 0 ? 0 : (1LLU << (extension_bytes * 7)));
}

class HpackVarintRoundTripTest : public RandomDecoderTest {
 protected:
  HpackVarintRoundTripTest() : prefix_length_(0) {}

  DecodeStatus StartDecoding(DecodeBuffer* b) override {
    QUICHE_CHECK_LT(0u, b->Remaining());
    uint8_t prefix = b->DecodeUInt8();
    return decoder_.Start(prefix, prefix_length_, b);
  }

  DecodeStatus ResumeDecoding(DecodeBuffer* b) override {
    return decoder_.Resume(b);
  }

  void DecodeSeveralWays(uint64_t expected_value, uint32_t expected_offset) {
    // The validator is called after each of the several times that the input
    // DecodeBuffer is decoded, each with a different segmentation of the input.
    // Validate that decoder_.value() matches the expected value.
    Validator validator = [expected_value, this](
                              const DecodeBuffer& /*db*/,
                              DecodeStatus /*status*/) -> AssertionResult {
      if (decoder_.value() != expected_value) {
        return AssertionFailure()
               << "Value doesn't match expected: " << decoder_.value()
               << " != " << expected_value;
      }
      return AssertionSuccess();
    };

    // First validate that decoding is done and that we've advanced the cursor
    // the expected amount.
    validator = ValidateDoneAndOffset(expected_offset, std::move(validator));

    // StartDecoding, above, requires the DecodeBuffer be non-empty so that it
    // can call Start with the prefix byte.
    bool return_non_zero_on_first = true;

    DecodeBuffer b(buffer_);
    EXPECT_TRUE(
        DecodeAndValidateSeveralWays(&b, return_non_zero_on_first, validator));

    EXPECT_EQ(expected_value, decoder_.value());
    EXPECT_EQ(expected_offset, b.Offset());
  }

  void EncodeNoRandom(uint64_t value, uint8_t prefix_length) {
    QUICHE_DCHECK_LE(3, prefix_length);
    QUICHE_DCHECK_LE(prefix_length, 8);
    prefix_length_ = prefix_length;

    HpackBlockBuilder bb;
    bb.AppendHighBitsAndVarint(0, prefix_length_, value);
    buffer_ = bb.buffer();
    ASSERT_LT(0u, buffer_.size());

    const uint8_t prefix_mask = (1 << prefix_length_) - 1;
    ASSERT_EQ(static_cast<uint8_t>(buffer_[0]),
              static_cast<uint8_t>(buffer_[0]) & prefix_mask);
  }

  void Encode(uint64_t value, uint8_t prefix_length) {
    EncodeNoRandom(value, prefix_length);
    // Add some random bits to the prefix (the first byte) above the mask.
    uint8_t prefix = buffer_[0];
    buffer_[0] = prefix | (Random().Rand8() << prefix_length);
    const uint8_t prefix_mask = (1 << prefix_length_) - 1;
    ASSERT_EQ(prefix, buffer_[0] & prefix_mask);
  }

  // This is really a test of HpackBlockBuilder, making sure that the input to
  // HpackVarintDecoder is as expected, which also acts as confirmation that
  // my thinking about the encodings being used by the tests, i.e. cover the
  // range desired.
  void ValidateEncoding(uint64_t value, uint64_t minimum, uint64_t maximum,
                        size_t expected_bytes) {
    ASSERT_EQ(expected_bytes, buffer_.size());
    if (expected_bytes > 1) {
      const uint8_t prefix_mask = (1 << prefix_length_) - 1;
      EXPECT_EQ(prefix_mask, buffer_[0] & prefix_mask);
      size_t last = expected_bytes - 1;
      for (size_t ndx = 1; ndx < last; ++ndx) {
        // Before the last extension byte, we expect the high-bit set.
        uint8_t byte = buffer_[ndx];
        if (value == minimum) {
          EXPECT_EQ(0x80, byte) << "ndx=" << ndx;
        } else if (value == maximum) {
          if (expected_bytes < 11) {
            EXPECT_EQ(0xff, byte) << "ndx=" << ndx;
          }
        } else {
          EXPECT_EQ(0x80, byte & 0x80) << "ndx=" << ndx;
        }
      }
      // The last extension byte should not have the high-bit set.
      uint8_t byte = buffer_[last];
      if (value == minimum) {
        if (expected_bytes == 2) {
          EXPECT_EQ(0x00, byte);
        } else {
          EXPECT_EQ(0x01, byte);
        }
      } else if (value == maximum) {
        if (expected_bytes < 11) {
          EXPECT_EQ(0x7f, byte);
        }
      } else {
        EXPECT_EQ(0x00, byte & 0x80);
      }
    } else {
      const uint8_t prefix_mask = (1 << prefix_length_) - 1;
      EXPECT_EQ(value, static_cast<uint32_t>(buffer_[0] & prefix_mask));
      EXPECT_LT(value, prefix_mask);
    }
  }

  void EncodeAndDecodeValues(const std::set<uint64_t>& values,
                             uint8_t prefix_length, size_t expected_bytes) {
    QUICHE_CHECK(!values.empty());
    const uint64_t minimum = *values.begin();
    const uint64_t maximum = *values.rbegin();
    for (const uint64_t value : values) {
      Encode(value, prefix_length);  // Sets buffer_.

      std::string msg = absl::StrCat("value=", value, " (0x", absl::Hex(value),
                                     "), prefix_length=", prefix_length,
                                     ", expected_bytes=", expected_bytes, "\n",
                                     quiche::QuicheTextUtils::HexDump(buffer_));

      if (value == minimum) {
        QUICHE_LOG(INFO) << "Checking minimum; " << msg;
      } else if (value == maximum) {
        QUICHE_LOG(INFO) << "Checking maximum; " << msg;
      }

      SCOPED_TRACE(msg);
      ValidateEncoding(value, minimum, maximum, expected_bytes);
      DecodeSeveralWays(value, expected_bytes);

      // Append some random data to the end of buffer_ and repeat. That random
      // data should be ignored.
      buffer_.append(Random().RandString(1 + Random().Uniform(10)));
      DecodeSeveralWays(value, expected_bytes);

      // If possible, add extension bytes that don't change the value.
      if (1 < expected_bytes) {
        buffer_.resize(expected_bytes);
        for (uint8_t total_bytes = expected_bytes + 1; total_bytes <= 6;
             ++total_bytes) {
          // Mark the current last byte as not being the last one.
          EXPECT_EQ(0x00, 0x80 & buffer_.back());
          buffer_.back() |= 0x80;
          buffer_.push_back('\0');
          DecodeSeveralWays(value, total_bytes);
        }
      }
    }
  }

  // Encode values (all or some of it) in [start, start+range).  Check
  // that |start| is the smallest value and |start+range-1| is the largest value
  // corresponding to |expected_bytes|, except if |expected_bytes| is maximal.
  void EncodeAndDecodeValuesInRange(uint64_t start, uint64_t range,
                                    uint8_t prefix_length,
                                    size_t expected_bytes) {
    const uint8_t prefix_mask = (1 << prefix_length) - 1;
    const uint64_t beyond = start + range;

    QUICHE_LOG(INFO)
        << "############################################################";
    QUICHE_LOG(INFO) << "prefix_length=" << static_cast<int>(prefix_length);
    QUICHE_LOG(INFO) << "prefix_mask=" << std::hex
                     << static_cast<int>(prefix_mask);
    QUICHE_LOG(INFO) << "start=" << start << " (" << std::hex << start << ")";
    QUICHE_LOG(INFO) << "range=" << range << " (" << std::hex << range << ")";
    QUICHE_LOG(INFO) << "beyond=" << beyond << " (" << std::hex << beyond
                     << ")";
    QUICHE_LOG(INFO) << "expected_bytes=" << expected_bytes;

    if (expected_bytes < 11) {
      // Confirm the claim that beyond requires more bytes.
      Encode(beyond, prefix_length);
      EXPECT_EQ(expected_bytes + 1, buffer_.size())
          << quiche::QuicheTextUtils::HexDump(buffer_);
    }

    std::set<uint64_t> values;
    if (range < 200) {
      // Select all values in the range.
      for (uint64_t offset = 0; offset < range; ++offset) {
        values.insert(start + offset);
      }
    } else {
      // Select some values in this range, including the minimum and maximum
      // values that require exactly |expected_bytes| extension bytes.
      values.insert({start, start + 1, beyond - 2, beyond - 1});
      while (values.size() < 100) {
        values.insert(Random().UniformInRange(start, beyond - 1));
      }
    }

    EncodeAndDecodeValues(values, prefix_length, expected_bytes);
  }

  HpackVarintDecoder decoder_;
  std::string buffer_;
  uint8_t prefix_length_;
};

// To help me and future debuggers of varint encodings, this HTTP2_LOGs out the
// transition points where a new extension byte is added.
TEST_F(HpackVarintRoundTripTest, Encode) {
  for (int prefix_length = 3; prefix_length <= 8; ++prefix_length) {
    const uint64_t a = HiValueOfExtensionBytes(0, prefix_length);
    const uint64_t b = HiValueOfExtensionBytes(1, prefix_length);
    const uint64_t c = HiValueOfExtensionBytes(2, prefix_length);
    const uint64_t d = HiValueOfExtensionBytes(3, prefix_length);
    const uint64_t e = HiValueOfExtensionBytes(4, prefix_length);
    const uint64_t f = HiValueOfExtensionBytes(5, prefix_length);
    const uint64_t g = HiValueOfExtensionBytes(6, prefix_length);
    const uint64_t h = HiValueOfExtensionBytes(7, prefix_length);
    const uint64_t i = HiValueOfExtensionBytes(8, prefix_length);
    const uint64_t j = HiValueOfExtensionBytes(9, prefix_length);

    QUICHE_LOG(INFO)
        << "############################################################";
    QUICHE_LOG(INFO) << "prefix_length=" << prefix_length << "   a=" << a
                     << "   b=" << b << "   c=" << c << "   d=" << d
                     << "   e=" << e << "   f=" << f << "   g=" << g
                     << "   h=" << h << "   i=" << i << "   j=" << j;

    std::vector<uint64_t> values = {
        0,     1,                       // Force line break.
        a - 1, a, a + 1, a + 2, a + 3,  // Force line break.
        b - 1, b, b + 1, b + 2, b + 3,  // Force line break.
        c - 1, c, c + 1, c + 2, c + 3,  // Force line break.
        d - 1, d, d + 1, d + 2, d + 3,  // Force line break.
        e - 1, e, e + 1, e + 2, e + 3,  // Force line break.
        f - 1, f, f + 1, f + 2, f + 3,  // Force line break.
        g - 1, g, g + 1, g + 2, g + 3,  // Force line break.
        h - 1, h, h + 1, h + 2, h + 3,  // Force line break.
        i - 1, i, i + 1, i + 2, i + 3,  // Force line break.
        j - 1, j, j + 1, j + 2, j + 3,  // Force line break.
    };

    for (uint64_t value : values) {
      EncodeNoRandom(value, prefix_length);
      std::string dump = quiche::QuicheTextUtils::HexDump(buffer_);
      QUICHE_LOG(INFO) << absl::StrFormat("%10llu %0#18x ", value, value)
                       << quiche::QuicheTextUtils::HexDump(buffer_).substr(7);
    }
  }
}

TEST_F(HpackVarintRoundTripTest, FromSpec1337) {
  DecodeBuffer b(absl::string_view("\x1f\x9a\x0a"));
  uint32_t prefix_length = 5;
  uint8_t p = b.DecodeUInt8();
  EXPECT_EQ(1u, b.Offset());
  EXPECT_EQ(DecodeStatus::kDecodeDone, decoder_.Start(p, prefix_length, &b));
  EXPECT_EQ(3u, b.Offset());
  EXPECT_EQ(1337u, decoder_.value());

  EncodeNoRandom(1337, prefix_length);
  EXPECT_EQ(3u, buffer_.size());
  EXPECT_EQ('\x1f', buffer_[0]);
  EXPECT_EQ('\x9a', buffer_[1]);
  EXPECT_EQ('\x0a', buffer_[2]);
}

// Test all the values that fit into the prefix (one less than the mask).
TEST_F(HpackVarintRoundTripTest, ValidatePrefixOnly) {
  for (int prefix_length = 3; prefix_length <= 8; ++prefix_length) {
    const uint8_t prefix_mask = (1 << prefix_length) - 1;
    EncodeAndDecodeValuesInRange(0, prefix_mask, prefix_length, 1);
  }
}

// Test all values that require exactly 1 extension byte.
TEST_F(HpackVarintRoundTripTest, ValidateOneExtensionByte) {
  for (int prefix_length = 3; prefix_length <= 8; ++prefix_length) {
    const uint64_t start = HiValueOfExtensionBytes(0, prefix_length) + 1;
    EncodeAndDecodeValuesInRange(start, 128, prefix_length, 2);
  }
}

// Test *some* values that require exactly 2 extension bytes.
TEST_F(HpackVarintRoundTripTest, ValidateTwoExtensionBytes) {
  for (int prefix_length = 3; prefix_length <= 8; ++prefix_length) {
    const uint64_t start = HiValueOfExtensionBytes(1, prefix_length) + 1;
    const uint64_t range = 127 << 7;

    EncodeAndDecodeValuesInRange(start, range, prefix_length, 3);
  }
}

// Test *some* values that require 3 extension bytes.
TEST_F(HpackVarintRoundTripTest, ValidateThreeExtensionBytes) {
  for (int prefix_length = 3; prefix_length <= 8; ++prefix_length) {
    const uint64_t start = HiValueOfExtensionBytes(2, prefix_length) + 1;
    const uint64_t range = 127 << 14;

    EncodeAndDecodeValuesInRange(start, range, prefix_length, 4);
  }
}

// Test *some* values that require 4 extension bytes.
TEST_F(HpackVarintRoundTripTest, ValidateFourExtensionBytes) {
  for (int prefix_length = 3; prefix_length <= 8; ++prefix_length) {
    const uint64_t start = HiValueOfExtensionBytes(3, prefix_length) + 1;
    const uint64_t range = 127 << 21;

    EncodeAndDecodeValuesInRange(start, range, prefix_length, 5);
  }
}

// Test *some* values that require 5 extension bytes.
TEST_F(HpackVarintRoundTripTest, ValidateFiveExtensionBytes) {
  for (int prefix_length = 3; prefix_length <= 8; ++prefix_length) {
    const uint64_t start = HiValueOfExtensionBytes(4, prefix_length) + 1;
    const uint64_t range = 127llu << 28;

    EncodeAndDecodeValuesInRange(start, range, prefix_length, 6);
  }
}

// Test *some* values that require 6 extension bytes.
TEST_F(HpackVarintRoundTripTest, ValidateSixExtensionBytes) {
  for (int prefix_length = 3; prefix_length <= 8; ++prefix_length) {
    const uint64_t start = HiValueOfExtensionBytes(5, prefix_length) + 1;
    const uint64_t range = 127llu << 35;

    EncodeAndDecodeValuesInRange(start, range, prefix_length, 7);
  }
}

// Test *some* values that require 7 extension bytes.
TEST_F(HpackVarintRoundTripTest, ValidateSevenExtensionBytes) {
  for (int prefix_length = 3; prefix_length <= 8; ++prefix_length) {
    const uint64_t start = HiValueOfExtensionBytes(6, prefix_length) + 1;
    const uint64_t range = 127llu << 42;

    EncodeAndDecodeValuesInRange(start, range, prefix_length, 8);
  }
}

// Test *some* values that require 8 extension bytes.
TEST_F(HpackVarintRoundTripTest, ValidateEightExtensionBytes) {
  for (int prefix_length = 3; prefix_length <= 8; ++prefix_length) {
    const uint64_t start = HiValueOfExtensionBytes(7, prefix_length) + 1;
    const uint64_t range = 127llu << 49;

    EncodeAndDecodeValuesInRange(start, range, prefix_length, 9);
  }
}

// Test *some* values that require 9 extension bytes.
TEST_F(HpackVarintRoundTripTest, ValidateNineExtensionBytes) {
  for (int prefix_length = 3; prefix_length <= 8; ++prefix_length) {
    const uint64_t start = HiValueOfExtensionBytes(8, prefix_length) + 1;
    const uint64_t range = 127llu << 56;

    EncodeAndDecodeValuesInRange(start, range, prefix_length, 10);
  }
}

// Test *some* values that require 10 extension bytes.
TEST_F(HpackVarintRoundTripTest, ValidateTenExtensionBytes) {
  for (int prefix_length = 3; prefix_length <= 8; ++prefix_length) {
    const uint64_t start = HiValueOfExtensionBytes(9, prefix_length) + 1;
    const uint64_t range = std::numeric_limits<uint64_t>::max() - start;

    EncodeAndDecodeValuesInRange(start, range, prefix_length, 11);
  }
}

}  // namespace
}  // namespace test
}  // namespace http2