Add support for optional fields in FixedLengthDeltaEncoder
Optional fields are those which only occur sometimes. For example,
the sequence number field in an RTP packet always occurs, but
fields in optional RTP extensions only occur sometimes.
Bug: webrtc:8111
Change-Id: Iff2c35b73530c0a1db68e547b4caf34434aa4ace
Reviewed-on: https://webrtc-review.googlesource.com/c/103362
Commit-Queue: Elad Alon <eladalon@webrtc.org>
Reviewed-by: Björn Terelius <terelius@webrtc.org>
Cr-Commit-Position: refs/heads/master@{#25336}diff --git a/logging/rtc_event_log/encoder/delta_encoding.cc b/logging/rtc_event_log/encoder/delta_encoding.cc
index 755eb41..3d242ec 100644
--- a/logging/rtc_event_log/encoder/delta_encoding.cc
+++ b/logging/rtc_event_log/encoder/delta_encoding.cc
@@ -188,7 +188,6 @@
// Whether the values of the sequence are optional. That is, it may be
// that some of them do not have a value (not even a sentinel value indicating
// invalidity).
- // TODO(eladalon): Add support for optional elements.
bool values_optional() const { return values_optional_; }
// Number of bits necessary to hold the largest value in the sequence.
@@ -226,18 +225,20 @@
// determine whether it was produced by FixedLengthDeltaEncoder, and can
// therefore be decoded by FixedLengthDeltaDecoder, or whether it was produced
// by a different encoder.
- static std::string EncodeDeltas(uint64_t base,
- const std::vector<uint64_t>& values);
+ static std::string EncodeDeltas(
+ absl::optional<uint64_t> base,
+ const std::vector<absl::optional<uint64_t>>& values);
private:
// Calculate min/max values of unsigned/signed deltas, given the bit width
// of all the values in the series.
- static void CalculateMinAndMaxDeltas(uint64_t base,
- const std::vector<uint64_t>& values,
- uint64_t bit_width,
- uint64_t* max_unsigned_delta,
- uint64_t* max_pos_signed_delta,
- uint64_t* min_neg_signed_delta);
+ static void CalculateMinAndMaxDeltas(
+ uint64_t base,
+ const std::vector<absl::optional<uint64_t>>& values,
+ uint64_t bit_width,
+ uint64_t* max_unsigned_delta,
+ uint64_t* max_pos_signed_delta,
+ uint64_t* min_neg_signed_delta);
// No effect outside of unit tests.
// In unit tests, may lead to forcing signed/unsigned deltas, etc.
@@ -251,17 +252,18 @@
// Therefore, it was deemed acceptable to let them have a reference to
// |values|, whose lifetime must exceed the lifetime of |this|.
FixedLengthDeltaEncoder(const FixedLengthEncodingParameters& params,
- uint64_t base,
- const std::vector<uint64_t>& values);
+ absl::optional<uint64_t> base,
+ const std::vector<absl::optional<uint64_t>>& values,
+ size_t existent_values_count);
// Perform delta-encoding using the parameters given to the ctor on the
// sequence of values given to the ctor.
std::string Encode();
// Exact lengths.
- size_t OutputLengthBytes() const;
+ size_t OutputLengthBytes(size_t existent_values_count) const;
size_t HeaderLengthBits() const;
- size_t EncodedDeltasLengthBits() const;
+ size_t EncodedDeltasLengthBits(size_t existent_values_count) const;
// Encode the compression parameters into the stream.
void EncodeHeader();
@@ -278,11 +280,11 @@
// The encoding scheme assumes that at least one value is transmitted OOB,
// so that the first value can be encoded as a delta from that OOB value,
// which is |base_|.
- const uint64_t base_;
+ const absl::optional<uint64_t> base_;
// The values to be encoded.
// Note: This is a non-owning reference. See comment above ctor for details.
- const std::vector<uint64_t>& values_;
+ const std::vector<absl::optional<uint64_t>>& values_;
// Buffer into which encoded values will be written.
// This is created dynmically as a way to enforce that the rest of the
@@ -295,15 +297,34 @@
// TODO(eladalon): Reduce the number of passes.
std::string FixedLengthDeltaEncoder::EncodeDeltas(
- uint64_t base,
- const std::vector<uint64_t>& values) {
+ absl::optional<uint64_t> base,
+ const std::vector<absl::optional<uint64_t>>& values) {
RTC_DCHECK(!values.empty());
- bool non_decreasing = base <= values[0];
- uint64_t max_value_including_base = std::max(base, values[0]);
- for (size_t i = 1; i < values.size(); ++i) {
- non_decreasing &= (values[i - 1] <= values[i]);
- max_value_including_base = std::max(max_value_including_base, values[i]);
+ // As a special case, if all of the elements are identical to the base,
+ // (including, for optional fields, about their existence/non-existence),
+ // the empty string is used to signal that.
+ if (std::all_of(
+ values.cbegin(), values.cend(),
+ [base](absl::optional<uint64_t> val) { return val == base; })) {
+ return std::string();
+ }
+
+ const uint64_t base_val = base.value_or(0u);
+
+ bool non_decreasing = true;
+ uint64_t max_value_including_base = base_val;
+ uint64_t previous = base_val;
+ size_t existent_values_count = 0;
+ for (size_t i = 0; i < values.size(); ++i) {
+ if (!values[i].has_value()) {
+ continue;
+ }
+ ++existent_values_count;
+ non_decreasing &= (previous <= values[i].value());
+ max_value_including_base =
+ std::max(max_value_including_base, values[i].value());
+ previous = values[i].value();
}
// If the sequence is non-decreasing, it may be assumed to have width = 64;
@@ -314,16 +335,9 @@
uint64_t max_unsigned_delta;
uint64_t max_pos_signed_delta;
uint64_t min_neg_signed_delta;
- CalculateMinAndMaxDeltas(base, values, value_width_bits, &max_unsigned_delta,
- &max_pos_signed_delta, &min_neg_signed_delta);
-
- // We indicate the special case of all values being equal to the base with
- // the empty string.
- if (max_unsigned_delta == 0) {
- RTC_DCHECK(std::all_of(values.cbegin(), values.cend(),
- [base](uint64_t val) { return val == base; }));
- return std::string();
- }
+ CalculateMinAndMaxDeltas(base_val, values, value_width_bits,
+ &max_unsigned_delta, &max_pos_signed_delta,
+ &min_neg_signed_delta);
const uint64_t delta_width_bits_unsigned =
UnsignedBitWidth(max_unsigned_delta);
@@ -336,7 +350,7 @@
const uint64_t delta_width_bits =
signed_deltas ? delta_width_bits_signed : delta_width_bits_unsigned;
- const bool values_optional = false;
+ const bool values_optional = (existent_values_count < values.size());
FixedLengthEncodingParameters params(delta_width_bits, signed_deltas,
values_optional, value_width_bits);
@@ -345,13 +359,13 @@
ConsiderTestOverrides(¶ms, delta_width_bits_signed,
delta_width_bits_unsigned);
- FixedLengthDeltaEncoder encoder(params, base, values);
+ FixedLengthDeltaEncoder encoder(params, base, values, existent_values_count);
return encoder.Encode();
}
void FixedLengthDeltaEncoder::CalculateMinAndMaxDeltas(
uint64_t base,
- const std::vector<uint64_t>& values,
+ const std::vector<absl::optional<uint64_t>>& values,
uint64_t bit_width,
uint64_t* max_unsigned_delta_out,
uint64_t* max_pos_signed_delta_out,
@@ -369,8 +383,14 @@
uint64_t prev = base;
for (size_t i = 0; i < values.size(); ++i) {
- const uint64_t forward_delta = UnsignedDelta(prev, values[i], bit_mask);
- const uint64_t backward_delta = UnsignedDelta(values[i], prev, bit_mask);
+ if (!values[i].has_value()) {
+ continue;
+ }
+
+ const uint64_t current = values[i].value();
+
+ const uint64_t forward_delta = UnsignedDelta(prev, current, bit_mask);
+ const uint64_t backward_delta = UnsignedDelta(current, prev, bit_mask);
max_unsigned_delta = std::max(max_unsigned_delta, forward_delta);
@@ -380,7 +400,7 @@
min_neg_signed_delta = std::max(min_neg_signed_delta, backward_delta);
}
- prev = values[i];
+ prev = current;
}
*max_unsigned_delta_out = max_unsigned_delta;
@@ -405,28 +425,42 @@
FixedLengthDeltaEncoder::FixedLengthDeltaEncoder(
const FixedLengthEncodingParameters& params,
- uint64_t base,
- const std::vector<uint64_t>& values)
+ absl::optional<uint64_t> base,
+ const std::vector<absl::optional<uint64_t>>& values,
+ size_t existent_values_count)
: params_(params), base_(base), values_(values) {
RTC_DCHECK(!values_.empty());
- writer_ = absl::make_unique<BitWriter>(OutputLengthBytes());
+ writer_ =
+ absl::make_unique<BitWriter>(OutputLengthBytes(existent_values_count));
}
std::string FixedLengthDeltaEncoder::Encode() {
EncodeHeader();
- uint64_t previous = base_;
- for (uint64_t value : values_) {
- EncodeDelta(previous, value);
- previous = value;
+ if (params_.values_optional()) {
+ // Encode which values exist and which don't.
+ for (absl::optional<uint64_t> value : values_) {
+ writer_->WriteBits(value.has_value() ? 1u : 0u, 1);
+ }
+ }
+
+ uint64_t previous = base_.has_value() ? base_.value() : 0u;
+ for (absl::optional<uint64_t> value : values_) {
+ if (!value.has_value()) {
+ RTC_DCHECK(params_.values_optional());
+ continue;
+ }
+ EncodeDelta(previous, value.value());
+ previous = value.value();
}
return writer_->GetString();
}
-size_t FixedLengthDeltaEncoder::OutputLengthBytes() const {
- const size_t length_bits = HeaderLengthBits() + EncodedDeltasLengthBits();
- return BitsToBytes(length_bits);
+size_t FixedLengthDeltaEncoder::OutputLengthBytes(
+ size_t existent_values_count) const {
+ return BitsToBytes(HeaderLengthBits() +
+ EncodedDeltasLengthBits(existent_values_count));
}
size_t FixedLengthDeltaEncoder::HeaderLengthBits() const {
@@ -441,11 +475,21 @@
}
}
-size_t FixedLengthDeltaEncoder::EncodedDeltasLengthBits() const {
- // TODO(eladalon): When optional values are supported, iterate over the
- // deltas to check the exact cost of each.
- RTC_DCHECK(!params_.values_optional());
- return values_.size() * params_.delta_width_bits();
+size_t FixedLengthDeltaEncoder::EncodedDeltasLengthBits(
+ size_t existent_values_count) const {
+ if (params_.values_optional()) {
+ RTC_DCHECK_EQ(std::count_if(values_.begin(), values_.end(),
+ [](absl::optional<uint64_t> val) {
+ return val.has_value();
+ }),
+ existent_values_count);
+ // One bit for each delta, to indicate if the value exists, and delta_width
+ // for each existent value, to indicate the delta itself.
+ return (1 * values_.size()) +
+ (params_.delta_width_bits() * existent_values_count);
+ } else {
+ return values_.size() * params_.delta_width_bits();
+ }
}
void FixedLengthDeltaEncoder::EncodeHeader() {
@@ -534,9 +578,10 @@
// original values, this will return the sequence of original values.
// If an error occurs (can happen if |input| is corrupt), an empty
// vector will be returned.
- static std::vector<uint64_t> DecodeDeltas(const std::string& input,
- uint64_t base,
- size_t num_of_deltas);
+ static std::vector<absl::optional<uint64_t>> DecodeDeltas(
+ const std::string& input,
+ absl::optional<uint64_t> base,
+ size_t num_of_deltas);
private:
// Reads the encoding header in |input| and returns a FixedLengthDeltaDecoder
@@ -547,8 +592,10 @@
// When a valid FixedLengthDeltaDecoder is returned, this does not mean that
// the entire stream is free of error. Rather, only the encoding header is
// examined and guaranteed.
- static std::unique_ptr<FixedLengthDeltaDecoder>
- Create(const std::string& input, uint64_t base, size_t num_of_deltas);
+ static std::unique_ptr<FixedLengthDeltaDecoder> Create(
+ const std::string& input,
+ absl::optional<uint64_t> base,
+ size_t num_of_deltas);
// FixedLengthDeltaDecoder objects are to be created by DecodeDeltas() and
// released by it before it returns. They're mostly a convenient way to
@@ -558,11 +605,11 @@
// of |reader|'s underlying buffer.
FixedLengthDeltaDecoder(std::unique_ptr<rtc::BitBuffer> reader,
const FixedLengthEncodingParameters& params,
- uint64_t base,
+ absl::optional<uint64_t> base,
size_t num_of_deltas);
// Perform the decoding using the parameters given to the ctor.
- std::vector<uint64_t> Decode();
+ std::vector<absl::optional<uint64_t>> Decode();
// Attempt to parse a delta from the input reader.
// Returns true/false for success/failure.
@@ -590,7 +637,7 @@
// The encoding scheme assumes that at least one value is transmitted OOB,
// so that the first value can be encoded as a delta from that OOB value,
// which is |base_|.
- const uint64_t base_;
+ const absl::optional<uint64_t> base_;
// The number of values to be known to be decoded.
const size_t num_of_deltas_;
@@ -618,13 +665,13 @@
EncodingType::kFixedSizeSignedDeltasEarlyWrapAndOptSupported;
}
-std::vector<uint64_t> FixedLengthDeltaDecoder::DecodeDeltas(
+std::vector<absl::optional<uint64_t>> FixedLengthDeltaDecoder::DecodeDeltas(
const std::string& input,
- uint64_t base,
+ absl::optional<uint64_t> base,
size_t num_of_deltas) {
auto decoder = FixedLengthDeltaDecoder::Create(input, base, num_of_deltas);
if (!decoder) {
- return std::vector<uint64_t>();
+ return std::vector<absl::optional<uint64_t>>();
}
return decoder->Decode();
@@ -632,7 +679,7 @@
std::unique_ptr<FixedLengthDeltaDecoder> FixedLengthDeltaDecoder::Create(
const std::string& input,
- uint64_t base,
+ absl::optional<uint64_t> base,
size_t num_of_deltas) {
if (input.length() < kBitsInHeaderForEncodingType) {
return nullptr;
@@ -685,10 +732,6 @@
}
RTC_DCHECK_LE(read_buffer, 1);
values_optional = rtc::dchecked_cast<bool>(read_buffer);
- if (values_optional) {
- RTC_LOG(LS_WARNING) << "Not implemented.";
- return nullptr;
- }
// value_width_bits
if (!reader->ReadBits(&read_buffer, kBitsInHeaderForValueWidthBits)) {
@@ -716,28 +759,48 @@
FixedLengthDeltaDecoder::FixedLengthDeltaDecoder(
std::unique_ptr<rtc::BitBuffer> reader,
const FixedLengthEncodingParameters& params,
- uint64_t base,
+ absl::optional<uint64_t> base,
size_t num_of_deltas)
: reader_(std::move(reader)),
params_(params),
base_(base),
num_of_deltas_(num_of_deltas) {
RTC_DCHECK(reader_);
- // TODO(eladalon): Support optional values.
- RTC_DCHECK(!params.values_optional()) << "Not implemented.";
}
-std::vector<uint64_t> FixedLengthDeltaDecoder::Decode() {
- std::vector<uint64_t> values(num_of_deltas_);
+std::vector<absl::optional<uint64_t>> FixedLengthDeltaDecoder::Decode() {
+ RTC_DCHECK(reader_);
- uint64_t previous = base_;
+ std::vector<bool> existing_values(num_of_deltas_);
+ if (params_.values_optional()) {
+ for (size_t i = 0; i < num_of_deltas_; ++i) {
+ uint32_t exists;
+ if (!reader_->ReadBits(&exists, 1u)) {
+ RTC_LOG(LS_WARNING) << "Failed to read existence-indicating bit.";
+ return std::vector<absl::optional<uint64_t>>();
+ }
+ RTC_DCHECK_LE(exists, 1u);
+ existing_values[i] = (exists == 1);
+ }
+ } else {
+ std::fill(existing_values.begin(), existing_values.end(), true);
+ }
+
+ std::vector<absl::optional<uint64_t>> values(num_of_deltas_);
+
+ uint64_t previous = base_.has_value() ? base_.value() : 0u;
for (size_t i = 0; i < num_of_deltas_; ++i) {
+ if (!existing_values[i]) {
+ RTC_DCHECK(params_.values_optional());
+ continue;
+ }
+
uint64_t delta;
if (!ParseDelta(&delta)) {
- return std::vector<uint64_t>();
+ return std::vector<absl::optional<uint64_t>>();
}
values[i] = ApplyDelta(previous, delta);
- previous = values[i];
+ previous = values[i].value();
}
return values;
@@ -745,7 +808,6 @@
bool FixedLengthDeltaDecoder::ParseDelta(uint64_t* delta) {
RTC_DCHECK(reader_);
- RTC_DCHECK(!params_.values_optional()) << "Not implemented."; // Reminder.
// BitBuffer and BitBufferWriter read/write higher bits before lower bits.
@@ -781,7 +843,6 @@
uint64_t FixedLengthDeltaDecoder::ApplyDelta(uint64_t base,
uint64_t delta) const {
- RTC_DCHECK(!params_.values_optional()) << "Not implemented."; // Reminder.
RTC_DCHECK_LE(base, MaxUnsignedValueOfBitWidth(params_.value_width_bits()));
RTC_DCHECK_LE(delta, MaxUnsignedValueOfBitWidth(params_.delta_width_bits()));
return params_.signed_deltas() ? ApplySignedDelta(base, delta)
@@ -816,20 +877,22 @@
} // namespace
-std::string EncodeDeltas(uint64_t base, const std::vector<uint64_t>& values) {
+std::string EncodeDeltas(absl::optional<uint64_t> base,
+ const std::vector<absl::optional<uint64_t>>& values) {
// TODO(eladalon): Support additional encodings.
return FixedLengthDeltaEncoder::EncodeDeltas(base, values);
}
-std::vector<uint64_t> DecodeDeltas(const std::string& input,
- uint64_t base,
- size_t num_of_deltas) {
+std::vector<absl::optional<uint64_t>> DecodeDeltas(
+ const std::string& input,
+ absl::optional<uint64_t> base,
+ size_t num_of_deltas) {
RTC_DCHECK_GT(num_of_deltas, 0); // Allows empty vector to indicate error.
// The empty string is a special case indicating that all values were equal
// to the base.
if (input.empty()) {
- std::vector<uint64_t> result(num_of_deltas);
+ std::vector<absl::optional<uint64_t>> result(num_of_deltas);
std::fill(result.begin(), result.end(), base);
return result;
}
@@ -839,7 +902,7 @@
}
RTC_LOG(LS_WARNING) << "Could not decode delta-encoded stream.";
- return std::vector<uint64_t>();
+ return std::vector<absl::optional<uint64_t>>();
}
void SetFixedLengthEncoderDeltaSignednessForTesting(bool signedness) {
diff --git a/logging/rtc_event_log/encoder/delta_encoding.h b/logging/rtc_event_log/encoder/delta_encoding.h
index 7ce5e4f..9e5e8b7 100644
--- a/logging/rtc_event_log/encoder/delta_encoding.h
+++ b/logging/rtc_event_log/encoder/delta_encoding.h
@@ -14,6 +14,8 @@
#include <string>
#include <vector>
+#include "absl/types/optional.h"
+
namespace webrtc {
// Encode |values| as a sequence of deltas following on |base| and return it.
@@ -22,7 +24,9 @@
// |base| is not guaranteed to be written into |output|, and must therefore
// be provided separately to the decoder.
// This function never fails.
-std::string EncodeDeltas(uint64_t base, const std::vector<uint64_t>& values);
+// TODO(eladalon): Split into optional and non-optional variants (efficiency).
+std::string EncodeDeltas(absl::optional<uint64_t> base,
+ const std::vector<absl::optional<uint64_t>>& values);
// EncodeDeltas() and DecodeDeltas() are inverse operations;
// invoking DecodeDeltas() over the output of EncodeDeltas(), will return
@@ -30,9 +34,11 @@
// |num_of_deltas| must be greater than zero. If input is not a valid encoding
// of |num_of_deltas| elements based on |base|, the function returns an empty
// vector, which signals an error.
-std::vector<uint64_t> DecodeDeltas(const std::string& input,
- uint64_t base,
- size_t num_of_deltas);
+// TODO(eladalon): Split into optional and non-optional variants (efficiency).
+std::vector<absl::optional<uint64_t>> DecodeDeltas(
+ const std::string& input,
+ absl::optional<uint64_t> base,
+ size_t num_of_deltas);
} // namespace webrtc
diff --git a/logging/rtc_event_log/encoder/delta_encoding_unittest.cc b/logging/rtc_event_log/encoder/delta_encoding_unittest.cc
index d553517..1cf3b64 100644
--- a/logging/rtc_event_log/encoder/delta_encoding_unittest.cc
+++ b/logging/rtc_event_log/encoder/delta_encoding_unittest.cc
@@ -67,50 +67,56 @@
// 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(uint64_t base,
- const std::vector<uint64_t>& values,
- std::string* encoded_string = nullptr) {
+void TestEncodingAndDecoding(
+ absl::optional<uint64_t> base,
+ const std::vector<absl::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<uint64_t> decoded =
+ const std::vector<absl::optional<uint64_t>> decoded =
DecodeDeltas(encoded, base, values.size());
EXPECT_EQ(decoded, values);
}
-std::vector<uint64_t> CreateSequenceByFirstValue(uint64_t first,
- size_t sequence_length) {
- std::vector<uint64_t> sequence(sequence_length);
+std::vector<absl::optional<uint64_t>> CreateSequenceByFirstValue(
+ uint64_t first,
+ size_t sequence_length) {
+ std::vector<absl::optional<uint64_t>> sequence(sequence_length);
std::iota(sequence.begin(), sequence.end(), first);
return sequence;
}
-std::vector<uint64_t> CreateSequenceByLastValue(uint64_t last,
- size_t num_values) {
+std::vector<absl::optional<uint64_t>> CreateSequenceByLastValue(
+ uint64_t last,
+ size_t num_values) {
const uint64_t first = last - num_values + 1;
- std::vector<uint64_t> result(num_values);
+ std::vector<absl::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<uint64_t> CreateSequenceByDeltas(
+std::vector<absl::optional<uint64_t>> CreateSequenceByOptionalDeltas(
uint64_t first,
- const std::vector<uint64_t>& deltas,
+ const std::vector<absl::optional<uint64_t>>& deltas,
size_t sequence_length) {
RTC_DCHECK_GE(sequence_length, 1);
- std::vector<uint64_t> sequence(sequence_length);
+ std::vector<absl::optional<uint64_t>> sequence(sequence_length);
uint64_t previous = first;
for (size_t i = 0, next_delta_index = 0; i < sequence.size(); ++i) {
- sequence[i] = previous + deltas[next_delta_index];
+ if (deltas[next_delta_index].has_value()) {
+ sequence[i] =
+ absl::optional<uint64_t>(previous + deltas[next_delta_index].value());
+ previous = sequence[i].value();
+ }
next_delta_index = (next_delta_index + 1) % deltas.size();
- previous = sequence[i];
}
return sequence;
@@ -134,25 +140,59 @@
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<absl::optional<uint64_t>> CreateSequenceByDeltas(
+ uint64_t first,
+ const std::vector<uint64_t>& deltas,
+ size_t sequence_length) {
+ RTC_DCHECK(!deltas.empty());
+ std::vector<absl::optional<uint64_t>> optional_deltas(deltas.size());
+ for (size_t i = 0; i < deltas.size(); ++i) {
+ optional_deltas[i] = absl::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>> {
+class DeltaEncodingTest : public ::testing::TestWithParam<
+ std::tuple<DeltaSignedness, size_t, bool>> {
public:
DeltaEncodingTest()
: signedness_(std::get<0>(GetParam())),
- num_of_values_(std::get<1>(GetParam())) {
+ num_of_values_(std::get<1>(GetParam())),
+ optional_values_(std::get<2>(GetParam())) {
MaybeSetSignedness(signedness_);
}
+
~DeltaEncodingTest() override = default;
const DeltaSignedness signedness_;
const uint64_t num_of_values_;
+ const bool optional_values_;
};
-TEST_P(DeltaEncodingTest, AllValuesEqualToBaseValue) {
- const uint64_t base = 3432;
- std::vector<uint64_t> values(num_of_values_);
+TEST_P(DeltaEncodingTest, AllValuesEqualToExistentBaseValue) {
+ const absl::optional<uint64_t> base(3432);
+ std::vector<absl::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 absl::optional<uint64_t> base;
+ std::vector<absl::optional<uint64_t>> values(num_of_values_);
std::fill(values.begin(), values.end(), base);
std::string encoded;
TestEncodingAndDecoding(base, values, &encoded);
@@ -163,54 +203,89 @@
}
TEST_P(DeltaEncodingTest, MinDeltaNoWrapAround) {
- const uint64_t base = 3432;
+ const absl::optional<uint64_t> base(3432);
- const auto values = CreateSequenceByFirstValue(base + 1, num_of_values_);
+ 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] = absl::optional<uint64_t>();
+ }
+
TestEncodingAndDecoding(base, values);
}
TEST_P(DeltaEncodingTest, BigDeltaNoWrapAround) {
const uint64_t kBigDelta = 132828;
- const uint64_t base = 3432;
+ const absl::optional<uint64_t> base(3432);
- const auto values =
- CreateSequenceByFirstValue(base + kBigDelta, num_of_values_);
+ 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] = absl::optional<uint64_t>();
+ }
+
TestEncodingAndDecoding(base, values);
}
TEST_P(DeltaEncodingTest, MaxDeltaNoWrapAround) {
- const uint64_t base = 3432;
+ const absl::optional<uint64_t> base(3432);
- const auto values = CreateSequenceByLastValue(
- std::numeric_limits<uint64_t>::max(), num_of_values_);
+ 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] = absl::optional<uint64_t>();
+ }
+
TestEncodingAndDecoding(base, values);
}
TEST_P(DeltaEncodingTest, SmallDeltaWithWrapAroundComparedToBase) {
- const uint64_t base = std::numeric_limits<uint64_t>::max();
+ if (optional_values_ && num_of_values_ == 1) {
+ return; // Inapplicable
+ }
- const auto values = CreateSequenceByDeltas(base, {1, 10, 3}, num_of_values_);
- ASSERT_LT(values[values.size() - 1], base) << "Sanity; must wrap around";
+ const absl::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] = absl::optional<uint64_t>();
+ }
TestEncodingAndDecoding(base, values);
}
TEST_P(DeltaEncodingTest, SmallDeltaWithWrapAroundInValueSequence) {
- if (num_of_values_ == 1) {
+ if (num_of_values_ == 1 || (optional_values_ && num_of_values_ < 3)) {
return; // Inapplicable.
}
- const uint64_t base = std::numeric_limits<uint64_t>::max() - 2;
+ const absl::optional<uint64_t> base(std::numeric_limits<uint64_t>::max() - 2);
- const auto values = CreateSequenceByDeltas(base, {1, 10, 3}, num_of_values_);
+ 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] = absl::optional<uint64_t>();
+ }
+
TestEncodingAndDecoding(base, values);
}
@@ -220,27 +295,46 @@
#pragma warning(disable : 4307)
#endif
TEST_P(DeltaEncodingTest, BigDeltaWithWrapAroundComparedToBase) {
- const uint64_t kBigDelta = 132828;
- const uint64_t base = std::numeric_limits<uint64_t>::max() - kBigDelta + 3;
+ if (optional_values_ && num_of_values_ == 1) {
+ return; // Inapplicable
+ }
- const auto values =
- CreateSequenceByFirstValue(base + kBigDelta, num_of_values_);
- ASSERT_LT(values[values.size() - 1], base) << "Sanity; must wrap around";
+ const uint64_t kBigDelta = 132828;
+ const absl::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] = absl::optional<uint64_t>();
+ }
TestEncodingAndDecoding(base, values);
}
TEST_P(DeltaEncodingTest, BigDeltaWithWrapAroundInValueSequence) {
- if (num_of_values_ == 1) {
+ if (num_of_values_ == 1 || (optional_values_ && num_of_values_ < 3)) {
return; // Inapplicable.
}
const uint64_t kBigDelta = 132828;
- const uint64_t base = std::numeric_limits<uint64_t>::max() - kBigDelta + 3;
+ const absl::optional<uint64_t> base(std::numeric_limits<uint64_t>::max() -
+ kBigDelta + 3);
- const auto values = CreateSequenceByFirstValue(
- std::numeric_limits<uint64_t>::max(), num_of_values_);
- ASSERT_LT(values[values.size() - 1], base) << "Sanity; must wrap around";
+ 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] = absl::optional<uint64_t>();
+ }
TestEncodingAndDecoding(base, values);
}
@@ -249,36 +343,60 @@
#endif
TEST_P(DeltaEncodingTest, MaxDeltaWithWrapAroundComparedToBase) {
- const uint64_t base = 3432;
- const auto values = CreateSequenceByFirstValue(base - 1, num_of_values_);
+ if (optional_values_ && num_of_values_ == 1) {
+ return; // Inapplicable
+ }
+
+ const absl::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] = absl::optional<uint64_t>();
+ }
+
TestEncodingAndDecoding(base, values);
}
TEST_P(DeltaEncodingTest, MaxDeltaWithWrapAroundInValueSequence) {
- if (num_of_values_ == 1) {
+ if (num_of_values_ == 1 || (optional_values_ && num_of_values_ < 3)) {
return; // Inapplicable.
}
- const uint64_t base = 3432;
+ const absl::optional<uint64_t> base(3432);
- const auto values = CreateSequenceByDeltas(
- base, {0, std::numeric_limits<uint64_t>::max(), 3}, num_of_values_);
- ASSERT_LT(values[1], base) << "Sanity; must wrap around";
+ 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] = absl::optional<uint64_t>();
+ }
TestEncodingAndDecoding(base, values);
}
// If num_of_values_ == 1, a zero delta will yield an empty string; that's
-// already covered by AllValuesEqualToBaseValue, but it doesn't hurt to test
-// again. For all other cases, we have a new test.
+// 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 uint64_t base = 3432;
+ const absl::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};
- const auto values = CreateSequenceByDeltas(base, deltas, num_of_values_);
+ 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] = absl::optional<uint64_t>();
+ }
TestEncodingAndDecoding(base, values);
}
@@ -289,7 +407,8 @@
::testing::Combine(::testing::Values(DeltaSignedness::kNoOverride,
DeltaSignedness::kForceUnsigned,
DeltaSignedness::kForceSigned),
- ::testing::Values(1, 2, 100, 10000)));
+ ::testing::Values(1, 2, 100, 10000),
+ ::testing::Bool()));
// Tests over the quality of the compression (as opposed to its correctness).
// Not to be confused with tests of runtime efficiency.
@@ -332,7 +451,6 @@
// need to be conveyed explicitly in the encoding header.
const uint64_t bases[] = {0, 0x55, 0xffffffff,
std::numeric_limits<uint64_t>::max()};
-
const size_t kIntendedWrapAroundBaseIndex = arraysize(bases);
std::vector<uint64_t> deltas(num_of_values_);
@@ -408,12 +526,13 @@
// specific cases, produce large amount of semi-realistic inputs.
class DeltaEncodingFuzzerLikeTest
: public ::testing::TestWithParam<
- std::tuple<DeltaSignedness, uint64_t, uint64_t>> {
+ std::tuple<DeltaSignedness, uint64_t, uint64_t, bool>> {
public:
DeltaEncodingFuzzerLikeTest()
: signedness_(std::get<0>(GetParam())),
delta_max_bit_width_(std::get<1>(GetParam())),
- num_of_values_(std::get<2>(GetParam())) {
+ num_of_values_(std::get<2>(GetParam())),
+ optional_values_(std::get<3>(GetParam())) {
MaybeSetSignedness(signedness_);
}
@@ -427,24 +546,27 @@
// to produce unique results.
return non_zero_base_seed + 2 * static_cast<uint64_t>(signedness_) +
3 * delta_max_bit_width_ + 5 * delta_max_bit_width_ +
- 7 * num_of_values_;
+ 7 * num_of_values_ + 11 * static_cast<uint64_t>(optional_values_);
}
const DeltaSignedness signedness_;
const uint64_t delta_max_bit_width_;
const uint64_t num_of_values_;
+ const bool optional_values_;
};
TEST_P(DeltaEncodingFuzzerLikeTest, Test) {
- const uint64_t base = 3432;
+ const absl::optional<uint64_t> base(3432);
Random prng(Seed());
- std::vector<uint64_t> deltas(num_of_values_);
+ std::vector<absl::optional<uint64_t>> deltas(num_of_values_);
for (size_t i = 0; i < deltas.size(); ++i) {
- deltas[i] = RandomWithMaxBitWidth(&prng, delta_max_bit_width_);
+ if (!optional_values_ || prng.Rand<bool>()) {
+ deltas[i] = RandomWithMaxBitWidth(&prng, delta_max_bit_width_);
+ }
}
-
- const auto values = CreateSequenceByDeltas(base, deltas, num_of_values_);
+ const auto values =
+ CreateSequenceByOptionalDeltas(base.value(), deltas, num_of_values_);
TestEncodingAndDecoding(base, values);
}
@@ -457,7 +579,8 @@
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(1, 2, 100, 10000),
+ ::testing::Bool()));
class DeltaEncodingSpecificEdgeCasesTest
: public ::testing::TestWithParam<
@@ -474,10 +597,10 @@
TEST_F(DeltaEncodingSpecificEdgeCasesTest, SignedDeltaWithOnlyTopBitOn) {
MaybeSetSignedness(DeltaSignedness::kForceSigned);
- const uint64_t base = 3432;
+ const absl::optional<uint64_t> base(3432);
const uint64_t delta = static_cast<uint64_t>(1) << 63;
- const std::vector<uint64_t> values = {base + delta};
+ const std::vector<absl::optional<uint64_t>> values = {base.value() + delta};
TestEncodingAndDecoding(base, values);
}
@@ -485,9 +608,9 @@
TEST_F(DeltaEncodingSpecificEdgeCasesTest, MaximumUnsignedDelta) {
MaybeSetSignedness(DeltaSignedness::kForceUnsigned);
- const uint64_t base = (static_cast<uint64_t>(1) << 63) + 0x123;
+ const absl::optional<uint64_t> base((static_cast<uint64_t>(1) << 63) + 0x123);
- const std::vector<uint64_t> values = {base - 1};
+ const std::vector<absl::optional<uint64_t>> values = {base.value() - 1};
TestEncodingAndDecoding(base, values);
}
@@ -503,9 +626,9 @@
: ((static_cast<uint64_t>(1) << width) - 1);
const uint64_t base = wrap_around ? 1u : (0xf82d3 & value_mask);
- const std::vector<uint64_t> values = {(base - 1u) & value_mask,
- (base - 2u) & value_mask,
- (base - 3u) & value_mask};
+ const std::vector<absl::optional<uint64_t>> values = {
+ (base - 1u) & value_mask, (base - 2u) & value_mask,
+ (base - 3u) & value_mask};
TestEncodingAndDecoding(base, values);
}
