tor-browser

delta_encoding_unittest.cc (23942B)

---

/*
*  Copyright (c) 2018 The WebRTC project authors. All Rights Reserved.
*
*  Use of this source code is governed by a BSD-style license
*  that can be found in the LICENSE file in the root of the source
*  tree. An additional intellectual property rights grant can be found
*  in the file PATENTS.  All contributing project authors may
*  be found in the AUTHORS file in the root of the source tree.
*/

#include "logging/rtc_event_log/encoder/delta_encoding.h"

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <limits>
#include <numeric>
#include <optional>
#include <string>
#include <tuple>
#include <vector>

#include "rtc_base/checks.h"
#include "rtc_base/random.h"
#include "test/gmock.h"
#include "test/gtest.h"

namespace webrtc {

void SetFixedLengthEncoderDeltaSignednessForTesting(bool signedness);
void UnsetFixedLengthEncoderDeltaSignednessForTesting();

namespace {

using ::testing::Each;
using ::testing::Eq;

enum class DeltaSignedness { kNoOverride, kForceUnsigned, kForceSigned };

void MaybeSetSignedness(DeltaSignedness signedness) {
 switch (signedness) {
   case DeltaSignedness::kNoOverride:
     UnsetFixedLengthEncoderDeltaSignednessForTesting();
     return;
   case DeltaSignedness::kForceUnsigned:
     SetFixedLengthEncoderDeltaSignednessForTesting(false);
     return;
   case DeltaSignedness::kForceSigned:
     SetFixedLengthEncoderDeltaSignednessForTesting(true);
     return;
 }
 RTC_DCHECK_NOTREACHED();
}

uint64_t RandomWithMaxBitWidth(Random* prng, uint64_t max_width) {
 RTC_DCHECK_GE(max_width, 1u);
 RTC_DCHECK_LE(max_width, 64u);

 const uint64_t low = prng->Rand(std::numeric_limits<uint32_t>::max());
 const uint64_t high =
     max_width > 32u ? prng->Rand(std::numeric_limits<uint32_t>::max()) : 0u;

 const uint64_t random_before_mask = (high << 32) | low;

 if (max_width < 64) {
   return random_before_mask & ((static_cast<uint64_t>(1) << max_width) - 1);
 } else {
   return random_before_mask;
 }
}

// Encodes `values` based on `base`, then decodes the result and makes sure
// that it is equal to the original input.
// If `encoded_string` is non-null, the encoded result will also be written
// into it.
void TestEncodingAndDecoding(std::optional<uint64_t> base,
                            const std::vector<std::optional<uint64_t>>& values,
                            std::string* encoded_string = nullptr) {
 const std::string encoded = EncodeDeltas(base, values);
 if (encoded_string) {
   *encoded_string = encoded;
 }

 const std::vector<std::optional<uint64_t>> decoded =
     DecodeDeltas(encoded, base, values.size());

 EXPECT_EQ(decoded, values);
}

std::vector<std::optional<uint64_t>> CreateSequenceByFirstValue(
   uint64_t first,
   size_t sequence_length) {
 std::vector<std::optional<uint64_t>> sequence(sequence_length);
 std::iota(sequence.begin(), sequence.end(), first);
 return sequence;
}

std::vector<std::optional<uint64_t>> CreateSequenceByLastValue(
   uint64_t last,
   size_t num_values) {
 const uint64_t first = last - num_values + 1;
 std::vector<std::optional<uint64_t>> result(num_values);
 std::iota(result.begin(), result.end(), first);
 return result;
}

// If `sequence_length` is greater than the number of deltas, the sequence of
// deltas will wrap around.
std::vector<std::optional<uint64_t>> CreateSequenceByOptionalDeltas(
   uint64_t first,
   const std::vector<std::optional<uint64_t>>& deltas,
   size_t sequence_length) {
 RTC_DCHECK_GE(sequence_length, 1);

 std::vector<std::optional<uint64_t>> sequence(sequence_length);

 uint64_t previous = first;
 for (size_t i = 0, next_delta_index = 0; i < sequence.size(); ++i) {
   if (deltas[next_delta_index].has_value()) {
     sequence[i] =
         std::optional<uint64_t>(previous + deltas[next_delta_index].value());
     previous = sequence[i].value();
   }
   next_delta_index = (next_delta_index + 1) % deltas.size();
 }

 return sequence;
}

size_t EncodingLengthUpperBound(size_t delta_max_bit_width,
                               size_t num_of_deltas,
                               DeltaSignedness signedness_override) {
 std::optional<size_t> smallest_header_size_bytes;
 switch (signedness_override) {
   case DeltaSignedness::kNoOverride:
   case DeltaSignedness::kForceUnsigned:
     smallest_header_size_bytes = 1;
     break;
   case DeltaSignedness::kForceSigned:
     smallest_header_size_bytes = 2;
     break;
 }
 RTC_DCHECK(smallest_header_size_bytes);

 return delta_max_bit_width * num_of_deltas + *smallest_header_size_bytes;
}

// If `sequence_length` is greater than the number of deltas, the sequence of
// deltas will wrap around.
std::vector<std::optional<uint64_t>> CreateSequenceByDeltas(
   uint64_t first,
   const std::vector<uint64_t>& deltas,
   size_t sequence_length) {
 RTC_DCHECK(!deltas.empty());
 std::vector<std::optional<uint64_t>> optional_deltas(deltas.size());
 for (size_t i = 0; i < deltas.size(); ++i) {
   optional_deltas[i] = std::optional<uint64_t>(deltas[i]);
 }
 return CreateSequenceByOptionalDeltas(first, optional_deltas,
                                       sequence_length);
}

// Tests of the delta encoding, parameterized by the number of values
// in the sequence created by the test.
class DeltaEncodingTest
   : public ::testing::TestWithParam<
         std::tuple<DeltaSignedness, size_t, bool, uint64_t>> {
public:
 DeltaEncodingTest()
     : signedness_(std::get<0>(GetParam())),
       num_of_values_(std::get<1>(GetParam())),
       optional_values_(std::get<2>(GetParam())),
       partial_random_seed_(std::get<3>(GetParam())) {
   MaybeSetSignedness(signedness_);
 }

 ~DeltaEncodingTest() override = default;

 // Running with the same seed for all variants would make all tests start
 // with the same sequence; avoid this by making the seed different.
 uint64_t Seed() const {
   // Multiply everything but by different primes to produce unique results.
   return 2 * static_cast<uint64_t>(signedness_) + 3 * num_of_values_ +
          5 * optional_values_ + 7 * partial_random_seed_;
 }

 const DeltaSignedness signedness_;
 const uint64_t num_of_values_;
 const bool optional_values_;
 const uint64_t partial_random_seed_;  // Explained where it's used.
};

TEST_P(DeltaEncodingTest, AllValuesEqualToExistentBaseValue) {
 const std::optional<uint64_t> base(3432);
 std::vector<std::optional<uint64_t>> values(num_of_values_);
 std::fill(values.begin(), values.end(), base);
 std::string encoded;
 TestEncodingAndDecoding(base, values, &encoded);

 // Additional requirement - the encoding should be efficient in this
 // case - the empty string will be used.
 EXPECT_TRUE(encoded.empty());
}

TEST_P(DeltaEncodingTest, AllValuesEqualToNonExistentBaseValue) {
 if (!optional_values_) {
   return;  // Test irrelevant for this case.
 }

 const std::optional<uint64_t> base;
 std::vector<std::optional<uint64_t>> values(num_of_values_);
 std::fill(values.begin(), values.end(), base);
 std::string encoded;
 TestEncodingAndDecoding(base, values, &encoded);

 // Additional requirement - the encoding should be efficient in this
 // case - the empty string will be used.
 EXPECT_TRUE(encoded.empty());
}

TEST_P(DeltaEncodingTest, BaseNonExistentButSomeOtherValuesExist) {
 if (!optional_values_) {
   return;  // Test irrelevant for this case.
 }

 const std::optional<uint64_t> base;
 std::vector<std::optional<uint64_t>> values(num_of_values_);

 Random prng(Seed());

 const uint64_t max_bit_width = 1 + prng.Rand(63);  // [1, 64]

 for (size_t i = 0; i < values.size();) {
   // Leave a random number of values as non-existent.
   const size_t non_existent_count = prng.Rand(values.size() - i - 1);
   i += non_existent_count;

   // Assign random values to a random number of values. (At least one, to
   // prevent this iteration of the outer loop from being a no-op.)
   const size_t existent_count =
       std::max<size_t>(prng.Rand(values.size() - i - 1), 1);
   for (size_t j = 0; j < existent_count; ++j) {
     values[i + j] = RandomWithMaxBitWidth(&prng, max_bit_width);
   }
   i += existent_count;
 }

 TestEncodingAndDecoding(base, values);
}

TEST_P(DeltaEncodingTest, MinDeltaNoWrapAround) {
 const std::optional<uint64_t> base(3432);

 auto values = CreateSequenceByFirstValue(base.value() + 1, num_of_values_);
 ASSERT_GT(values[values.size() - 1], base) << "Sanity; must not wrap around";

 if (optional_values_) {
   // Arbitrarily make one of the values non-existent, to force
   // optional-supporting encoding.
   values[0] = std::optional<uint64_t>();
 }

 TestEncodingAndDecoding(base, values);
}

TEST_P(DeltaEncodingTest, BigDeltaNoWrapAround) {
 const uint64_t kBigDelta = 132828;
 const std::optional<uint64_t> base(3432);

 auto values =
     CreateSequenceByFirstValue(base.value() + kBigDelta, num_of_values_);
 ASSERT_GT(values[values.size() - 1], base) << "Sanity; must not wrap around";

 if (optional_values_) {
   // Arbitrarily make one of the values non-existent, to force
   // optional-supporting encoding.
   values[0] = std::optional<uint64_t>();
 }

 TestEncodingAndDecoding(base, values);
}

TEST_P(DeltaEncodingTest, MaxDeltaNoWrapAround) {
 const std::optional<uint64_t> base(3432);

 auto values = CreateSequenceByLastValue(std::numeric_limits<uint64_t>::max(),
                                         num_of_values_);
 ASSERT_GT(values[values.size() - 1], base) << "Sanity; must not wrap around";

 if (optional_values_) {
   // Arbitrarily make one of the values non-existent, to force
   // optional-supporting encoding.
   values[0] = std::optional<uint64_t>();
 }

 TestEncodingAndDecoding(base, values);
}

TEST_P(DeltaEncodingTest, SmallDeltaWithWrapAroundComparedToBase) {
 if (optional_values_ && num_of_values_ == 1) {
   return;  // Inapplicable
 }

 const std::optional<uint64_t> base(std::numeric_limits<uint64_t>::max());

 auto values = CreateSequenceByDeltas(*base, {1, 10, 3}, num_of_values_);
 ASSERT_LT(values[0], base) << "Sanity; must wrap around";

 if (optional_values_) {
   // Arbitrarily make one of the values non-existent, to force
   // optional-supporting encoding.
   values[1] = std::optional<uint64_t>();
 }

 TestEncodingAndDecoding(base, values);
}

TEST_P(DeltaEncodingTest, SmallDeltaWithWrapAroundInValueSequence) {
 if (num_of_values_ == 1 || (optional_values_ && num_of_values_ < 3)) {
   return;  // Inapplicable.
 }

 const std::optional<uint64_t> base(std::numeric_limits<uint64_t>::max() - 2);

 auto values = CreateSequenceByDeltas(*base, {1, 10, 3}, num_of_values_);
 ASSERT_LT(values[values.size() - 1], values[0]) << "Sanity; must wrap around";

 if (optional_values_) {
   // Arbitrarily make one of the values non-existent, to force
   // optional-supporting encoding.
   RTC_DCHECK_GT(values.size() - 1, 1u);  // Wrap around not cancelled.
   values[1] = std::optional<uint64_t>();
 }

 TestEncodingAndDecoding(base, values);
}

// Suppress "integral constant overflow" warning; this is the test's focus.
#ifdef _MSC_VER
#pragma warning(push)
#pragma warning(disable : 4307)
#endif
TEST_P(DeltaEncodingTest, BigDeltaWithWrapAroundComparedToBase) {
 if (optional_values_ && num_of_values_ == 1) {
   return;  // Inapplicable
 }

 const uint64_t kBigDelta = 132828;
 const std::optional<uint64_t> base(std::numeric_limits<uint64_t>::max() -
                                    kBigDelta + 3);

 auto values =
     CreateSequenceByFirstValue(base.value() + kBigDelta, num_of_values_);
 ASSERT_LT(values[0], base.value()) << "Sanity; must wrap around";

 if (optional_values_) {
   // Arbitrarily make one of the values non-existent, to force
   // optional-supporting encoding.
   values[1] = std::optional<uint64_t>();
 }

 TestEncodingAndDecoding(base, values);
}

TEST_P(DeltaEncodingTest, BigDeltaWithWrapAroundInValueSequence) {
 if (num_of_values_ == 1 || (optional_values_ && num_of_values_ < 3)) {
   return;  // Inapplicable.
 }

 const uint64_t kBigDelta = 132828;
 const std::optional<uint64_t> base(std::numeric_limits<uint64_t>::max() -
                                    kBigDelta + 3);

 auto values = CreateSequenceByFirstValue(std::numeric_limits<uint64_t>::max(),
                                          num_of_values_);
 ASSERT_LT(values[values.size() - 1], values[0]) << "Sanity; must wrap around";

 if (optional_values_) {
   // Arbitrarily make one of the values non-existent, to force
   // optional-supporting encoding.
   RTC_DCHECK_GT(values.size() - 1, 1u);  // Wrap around not cancelled.
   values[1] = std::optional<uint64_t>();
 }

 TestEncodingAndDecoding(base, values);
}
#ifdef _MSC_VER
#pragma warning(pop)
#endif

TEST_P(DeltaEncodingTest, MaxDeltaWithWrapAroundComparedToBase) {
 if (optional_values_ && num_of_values_ == 1) {
   return;  // Inapplicable
 }

 const std::optional<uint64_t> base(3432);
 auto values = CreateSequenceByFirstValue(*base - 1, num_of_values_);

 if (optional_values_) {
   // Arbitrarily make one of the values non-existent, to force
   // optional-supporting encoding.
   values[1] = std::optional<uint64_t>();
 }

 TestEncodingAndDecoding(base, values);
}

TEST_P(DeltaEncodingTest, MaxDeltaWithWrapAroundInValueSequence) {
 if (num_of_values_ == 1 || (optional_values_ && num_of_values_ < 3)) {
   return;  // Inapplicable.
 }

 const std::optional<uint64_t> base(3432);

 auto values = CreateSequenceByDeltas(
     *base, {0, std::numeric_limits<uint64_t>::max(), 3}, num_of_values_);
 // Wraps around continuously by virtue of being max(); will not ASSERT.

 if (optional_values_) {
   // Arbitrarily make one of the values non-existent, to force
   // optional-supporting encoding.
   RTC_DCHECK_GT(values.size() - 1, 1u);  // Wrap around not cancelled.
   values[1] = std::optional<uint64_t>();
 }

 TestEncodingAndDecoding(base, values);
}

// If num_of_values_ == 1, a zero delta will yield an empty string; that's
// already covered by AllValuesEqualToExistentBaseValue, but it doesn't hurt to
// test again. For all other cases, we have a new test.
TEST_P(DeltaEncodingTest, ZeroDelta) {
 const std::optional<uint64_t> base(3432);

 // Arbitrary sequence of deltas with intentional zero deltas, as well as
 // consecutive zeros.
 const std::vector<uint64_t> deltas = {0,      312, 11, 1,  1, 0, 0, 12,
                                       400321, 3,   3,  12, 5, 0, 6};
 auto values = CreateSequenceByDeltas(base.value(), deltas, num_of_values_);

 if (optional_values_) {
   // Arbitrarily make one of the values non-existent, to force
   // optional-supporting encoding.
   values[0] = std::optional<uint64_t>();
 }

 TestEncodingAndDecoding(base, values);
}

INSTANTIATE_TEST_SUITE_P(
   SignednessOverrideAndNumberOfValuesInSequence,
   DeltaEncodingTest,
   ::testing::Combine(::testing::Values(DeltaSignedness::kNoOverride,
                                        DeltaSignedness::kForceUnsigned,
                                        DeltaSignedness::kForceSigned),
                      ::testing::Values(1, 2, 100, 10000),
                      ::testing::Bool(),
                      ::testing::Values(10, 20, 30)));

// Tests over the quality of the compression (as opposed to its correctness).
// Not to be confused with tests of runtime efficiency.
class DeltaEncodingCompressionQualityTest
   : public ::testing::TestWithParam<
         std::tuple<DeltaSignedness, uint64_t, uint64_t, uint64_t>> {
public:
 DeltaEncodingCompressionQualityTest()
     : signedness_(std::get<0>(GetParam())),
       delta_max_bit_width_(std::get<1>(GetParam())),
       num_of_values_(std::get<2>(GetParam())),
       partial_random_seed_(std::get<3>(GetParam())) {
   MaybeSetSignedness(signedness_);
 }

 ~DeltaEncodingCompressionQualityTest() override = default;

 // Running with the same seed for all variants would make all tests start
 // with the same sequence; avoid this by making the seed different.
 uint64_t Seed() const {
   // Multiply everything but by different primes to produce unique results.
   return 2 * static_cast<uint64_t>(signedness_) + 3 * delta_max_bit_width_ +
          5 * delta_max_bit_width_ + 7 * num_of_values_ +
          11 * partial_random_seed_;
 }

 const DeltaSignedness signedness_;
 const uint64_t delta_max_bit_width_;
 const uint64_t num_of_values_;
 const uint64_t partial_random_seed_;  // Explained where it's used.
};

// If no wrap-around occurs in the stream, the width of the values does not
// matter to compression performance; only the deltas matter.
TEST_P(DeltaEncodingCompressionQualityTest, BaseDoesNotAffectEfficiency) {
 // 1. Bases which will not produce a wrap-around.
 // 2. The last base - 0xffffffffffffffff - does cause a wrap-around, but
 //    that still works, because the width is 64 anyway, and does not
 //    need to be conveyed explicitly in the encoding header.
 const uint64_t bases[] = {0, 0x55, 0xffffffff,
                           std::numeric_limits<uint64_t>::max()};

 std::vector<uint64_t> deltas(num_of_values_);

 // Allows us to make sure that the deltas do not produce a wrap-around.
 uint64_t last_element[std::size(bases)];
 memcpy(last_element, bases, sizeof(bases));

 // Avoid empty `deltas` due to first element causing wrap-around.
 deltas[0] = 1;
 for (uint64_t& element : last_element) {
   ++element;
 }

 Random prng(Seed());

 for (size_t i = 1; i < deltas.size(); ++i) {
   const uint64_t delta = RandomWithMaxBitWidth(&prng, delta_max_bit_width_);

   bool wrap_around = false;
   for (size_t j = 0; j < std::size(last_element); ++j) {
     last_element[j] += delta;
     if (last_element[j] < bases[j]) {
       wrap_around = true;
       break;
     }
   }

   if (wrap_around) {
     deltas.resize(i);
     break;
   }

   deltas[i] = delta;
 }

 std::string encodings[std::size(bases)];

 for (size_t i = 0; i < std::size(bases); ++i) {
   const auto values =
       CreateSequenceByDeltas(bases[i], deltas, num_of_values_);
   // Produce the encoding and write it to encodings[i].
   // By using TestEncodingAndDecoding() to do this, we also sanity-test
   // the encoding/decoding, though that is not the test's focus.
   TestEncodingAndDecoding(bases[i], values, &encodings[i]);
   EXPECT_LE(encodings[i].length(),
             EncodingLengthUpperBound(delta_max_bit_width_, num_of_values_,
                                      signedness_));
 }

 // Test focus - all of the encodings should be the same, as they are based
 // on the same delta sequence, and do not contain a wrap-around.
 EXPECT_THAT(encodings, Each(Eq(encodings[0])));
}

INSTANTIATE_TEST_SUITE_P(
   SignednessOverrideAndDeltaMaxBitWidthAndNumberOfValuesInSequence,
   DeltaEncodingCompressionQualityTest,
   ::testing::Combine(
       ::testing::Values(DeltaSignedness::kNoOverride,
                         DeltaSignedness::kForceUnsigned,
                         DeltaSignedness::kForceSigned),
       ::testing::Values(1, 4, 8, 15, 16, 17, 31, 32, 33, 63, 64),
       ::testing::Values(1, 2, 100, 10000),
       ::testing::Values(11, 12, 13)));

// Similar to DeltaEncodingTest, but instead of semi-surgically producing
// specific cases, produce large amount of semi-realistic inputs.
class DeltaEncodingFuzzerLikeTest
   : public ::testing::TestWithParam<
         std::tuple<DeltaSignedness, uint64_t, uint64_t, bool, uint64_t>> {
public:
 DeltaEncodingFuzzerLikeTest()
     : signedness_(std::get<0>(GetParam())),
       delta_max_bit_width_(std::get<1>(GetParam())),
       num_of_values_(std::get<2>(GetParam())),
       optional_values_(std::get<3>(GetParam())),
       partial_random_seed_(std::get<4>(GetParam())) {
   MaybeSetSignedness(signedness_);
 }

 ~DeltaEncodingFuzzerLikeTest() override = default;

 // Running with the same seed for all variants would make all tests start
 // with the same sequence; avoid this by making the seed different.
 uint64_t Seed() const {
   // Multiply everything but by different primes to produce unique results.
   return 2 * static_cast<uint64_t>(signedness_) + 3 * delta_max_bit_width_ +
          5 * delta_max_bit_width_ + 7 * num_of_values_ +
          11 * static_cast<uint64_t>(optional_values_) +
          13 * partial_random_seed_;
 }

 const DeltaSignedness signedness_;
 const uint64_t delta_max_bit_width_;
 const uint64_t num_of_values_;
 const bool optional_values_;
 const uint64_t partial_random_seed_;  // Explained where it's used.
};

TEST_P(DeltaEncodingFuzzerLikeTest, Test) {
 const std::optional<uint64_t> base(3432);

 Random prng(Seed());
 std::vector<std::optional<uint64_t>> deltas(num_of_values_);
 for (size_t i = 0; i < deltas.size(); ++i) {
   if (!optional_values_ || prng.Rand<bool>()) {
     deltas[i] = RandomWithMaxBitWidth(&prng, delta_max_bit_width_);
   }
 }
 const auto values =
     CreateSequenceByOptionalDeltas(base.value(), deltas, num_of_values_);

 TestEncodingAndDecoding(base, values);
}

INSTANTIATE_TEST_SUITE_P(
   SignednessOverrideAndDeltaMaxBitWidthAndNumberOfValuesInSequence,
   DeltaEncodingFuzzerLikeTest,
   ::testing::Combine(
       ::testing::Values(DeltaSignedness::kNoOverride,
                         DeltaSignedness::kForceUnsigned,
                         DeltaSignedness::kForceSigned),
       ::testing::Values(1, 4, 8, 15, 16, 17, 31, 32, 33, 63, 64),
       ::testing::Values(1, 2, 100, 10000),
       ::testing::Bool(),
       ::testing::Values(21, 22, 23)));

class DeltaEncodingSpecificEdgeCasesTest
   : public ::testing::TestWithParam<
         std::tuple<DeltaSignedness, uint64_t, bool>> {
public:
 DeltaEncodingSpecificEdgeCasesTest() {
   UnsetFixedLengthEncoderDeltaSignednessForTesting();
 }

 ~DeltaEncodingSpecificEdgeCasesTest() override = default;
};

// This case is special because it produces identical forward/backward deltas.
TEST_F(DeltaEncodingSpecificEdgeCasesTest, SignedDeltaWithOnlyTopBitOn) {
 MaybeSetSignedness(DeltaSignedness::kForceSigned);

 const std::optional<uint64_t> base(3432);

 const uint64_t delta = static_cast<uint64_t>(1) << 63;
 const std::vector<std::optional<uint64_t>> values = {base.value() + delta};

 TestEncodingAndDecoding(base, values);
}

TEST_F(DeltaEncodingSpecificEdgeCasesTest, MaximumUnsignedDelta) {
 MaybeSetSignedness(DeltaSignedness::kForceUnsigned);

 const std::optional<uint64_t> base((static_cast<uint64_t>(1) << 63) + 0x123);

 const std::vector<std::optional<uint64_t>> values = {base.value() - 1};

 TestEncodingAndDecoding(base, values);
}

// Check that, if all deltas are set to -1, things still work.
TEST_P(DeltaEncodingSpecificEdgeCasesTest, ReverseSequence) {
 MaybeSetSignedness(std::get<0>(GetParam()));
 const uint64_t width = std::get<1>(GetParam());
 const bool wrap_around = std::get<2>(GetParam());

 const uint64_t value_mask = (width == 64)
                                 ? std::numeric_limits<uint64_t>::max()
                                 : ((static_cast<uint64_t>(1) << width) - 1);

 const uint64_t base = wrap_around ? 1u : (0xf82d3 & value_mask);
 const std::vector<std::optional<uint64_t>> values = {
     (base - 1u) & value_mask, (base - 2u) & value_mask,
     (base - 3u) & value_mask};

 TestEncodingAndDecoding(base, values);
}

INSTANTIATE_TEST_SUITE_P(
   _,
   DeltaEncodingSpecificEdgeCasesTest,
   ::testing::Combine(
       ::testing::Values(DeltaSignedness::kNoOverride,
                         DeltaSignedness::kForceUnsigned,
                         DeltaSignedness::kForceSigned),
       ::testing::Values(1, 4, 8, 15, 16, 17, 31, 32, 33, 63, 64),
       ::testing::Bool()));

}  // namespace
}  // namespace webrtc