logging/rtc_event_log/encoder/delta_encoding.cc

/*
 *  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 <limits>
#include <memory>
#include <utility>

#include "absl/memory/memory.h"
#include "rtc_base/bitbuffer.h"
#include "rtc_base/checks.h"
#include "rtc_base/constructormagic.h"
#include "rtc_base/logging.h"
#include "rtc_base/numerics/safe_conversions.h"

namespace webrtc {
namespace {

// TODO(eladalon): Only build the decoder in tools and unit tests.

size_t BitsToBytes(size_t bits) {
  return (bits / 8) + (bits % 8 > 0 ? 1 : 0);
}

// TODO(eladalon): Replace by something more efficient.
uint64_t BitWidth(uint64_t input) {
  uint64_t width = 0;
  do {  // input == 0 -> width == 1
    width += 1;
    input >>= 1;
  } while (input != 0);
  return width;
}

// Return the maximum integer of a given bit width.
// Examples:
// MaxValueOfBitWidth(1) = 0x01
// MaxValueOfBitWidth(6) = 0x3f
// MaxValueOfBitWidth(8) = 0xff
// MaxValueOfBitWidth(32) = 0xffffffff
uint64_t MaxValueOfBitWidth(uint64_t bit_width) {
  RTC_DCHECK_GE(bit_width, 1);
  RTC_DCHECK_LE(bit_width, 64);
  return (bit_width == 64) ? std::numeric_limits<uint64_t>::max()
                           : ((static_cast<uint64_t>(1) << bit_width) - 1);
}

// Computes the delta between |previous| and |current|, under the assumption
// that wrap-around occurs after width |bit_width| is exceeded.
uint64_t ComputeDelta(uint64_t previous, uint64_t current, uint64_t width) {
  RTC_DCHECK(width == 64 || current < (static_cast<uint64_t>(1) << width));
  RTC_DCHECK(width == 64 || previous < (static_cast<uint64_t>(1) << width));

  if (current >= previous) {
    // Simply "walk" forward.
    return current - previous;
  } else {  // previous > current
    // "Walk" until the max value, one more step to 0, then to |current|.
    return (MaxValueOfBitWidth(width) - previous) + 1 + current;
  }
}

// Determines the encoding type (e.g. fixed-size encoding).
// Given an encoding type, may also distinguish between some variants of it
// (e.g. which fields of the fixed-size encoding are explicitly mentioned by
// the header, and which are implicitly assumed to hold certain default values).
enum class EncodingType {
  kFixedSizeUnsignedDeltasNoEarlyWrapNoOpt = 0,
  kFixedSizeSignedDeltasEarlyWrapAndOptSupported = 1,
  kReserved1 = 2,
  kReserved2 = 3,
  kNumberOfEncodingTypes  // Keep last
};

// The width of each field in the encoding header. Note that this is the
// width in case the field exists; not all fields occur in all encoding types.
constexpr size_t kBitsInHeaderForEncodingType = 2;
constexpr size_t kBitsInHeaderForDeltaWidthBits = 6;
constexpr size_t kBitsInHeaderForSignedDeltas = 1;
constexpr size_t kBitsInHeaderForValuesOptional = 1;
constexpr size_t kBitsInHeaderForOriginalWidthBits = 6;

static_assert(static_cast<size_t>(EncodingType::kNumberOfEncodingTypes) <=
                  1 << kBitsInHeaderForEncodingType,
              "Not all encoding types fit.");

// Default values for when the encoding header does not specify explicitly.
constexpr bool kDefaultSignedDeltas = false;
constexpr bool kDefaultValuesOptional = false;
constexpr uint64_t kDefaultOriginalWidthBits = 64;

// Wrap BitBufferWriter and extend its functionality by (1) keeping track of
// the number of bits written and (2) owning its buffer.
class BitWriter final {
 public:
  explicit BitWriter(size_t byte_count)
      : buffer_(byte_count, '\0'),
        bit_writer_(reinterpret_cast<uint8_t*>(&buffer_[0]), buffer_.size()),
        written_bits_(0),
        valid_(true) {
    RTC_DCHECK_GT(byte_count, 0);
  }

  void WriteBits(uint64_t val, size_t bit_count) {
    RTC_DCHECK(valid_);
    const bool success = bit_writer_.WriteBits(val, bit_count);
    RTC_DCHECK(success);
    written_bits_ += bit_count;
  }

  // Returns everything that was written so far.
  // Nothing more may be written after this is called.
  std::string GetString() {
    RTC_DCHECK(valid_);
    valid_ = false;

    buffer_.resize(BitsToBytes(written_bits_));
    written_bits_ = 0;

    std::string result;
    std::swap(buffer_, result);
    return result;
  }

 private:
  std::string buffer_;
  rtc::BitBufferWriter bit_writer_;
  // Note: Counting bits instead of bytes wraps around earlier than it has to,
  // which means the maximum length is lower than it could be. We don't expect
  // to go anywhere near the limit, though, so this is good enough.
  size_t written_bits_;
  bool valid_;

  RTC_DISALLOW_COPY_AND_ASSIGN(BitWriter);
};

// Parameters for fixed-size delta-encoding/decoding.
// These are tailored for the sequence which will be encoded (e.g. widths).
struct FixedLengthEncodingParameters final {
  FixedLengthEncodingParameters(uint64_t delta_width_bits,
                                bool signed_deltas,
                                bool values_optional,
                                uint64_t original_width_bits)
      : delta_width_bits(delta_width_bits),
        signed_deltas(signed_deltas),
        values_optional(values_optional),
        original_width_bits(original_width_bits) {}

  // Number of bits necessary to hold the widest(*) of the deltas between the
  // values in the sequence.
  // (*) - Widest might not be the largest, if signed deltas are used.
  uint64_t delta_width_bits;

  // Whether deltas are signed.
  // TODO(eladalon): Add support for signed deltas.
  bool signed_deltas;

  // 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;

  // Number of bits necessary to hold the largest value in the sequence.
  uint64_t original_width_bits;
};

// Performs delta-encoding of a single (non-empty) sequence of values, using
// an encoding where all deltas are encoded using the same number of bits.
// (With the exception of optional elements; those are encoded as a bit vector
// with one bit per element, plus a fixed number of bits for every element that
// has a value.)
class FixedLengthDeltaEncoder final {
 public:
  // See webrtc::EncodeDeltas() for general details.
  // This function return a bit pattern that would allow the decoder to
  // 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);

 private:
  // FixedLengthDeltaEncoder objects are to be created by EncodeDeltas() and
  // released by it before it returns. They're mostly a convenient way to
  // avoid having to pass a lot of state between different functions.
  // 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);

  // 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 HeaderLengthBits() const;
  size_t EncodedDeltasLengthBits() const;

  // Encode the compression parameters into the stream.
  void EncodeHeader();

  // Encode a given delta into the stream.
  void EncodeDelta(uint64_t previous, uint64_t current);

  // The parameters according to which encoding will be done (width of
  // fields, whether signed deltas should be used, etc.)
  const FixedLengthEncodingParameters params_;

  // 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_;

  // The values to be encoded.
  // Note: This is a non-owning reference. See comment above ctor for details.
  const std::vector<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
  // ctor has finished running when this is constructed, so that the lower
  // bound on the buffer size would be guaranteed correct.
  std::unique_ptr<BitWriter> writer_;

  RTC_DISALLOW_COPY_AND_ASSIGN(FixedLengthDeltaEncoder);
};

// TODO(eladalon): Reduce the number of passes.
std::string FixedLengthDeltaEncoder::EncodeDeltas(
    uint64_t base,
    const std::vector<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]);
  }

  // If the sequence is non-decreasing, it may be assumed to have width = 64;
  // there's no reason to encode the actual max width in the encoding header.
  const uint64_t original_width_bits =
      non_decreasing ? 64 : BitWidth(max_value_including_base);

  uint64_t max_unsigned_delta =
      ComputeDelta(base, values[0], original_width_bits);
  for (size_t i = 1; i < values.size(); ++i) {
    const uint64_t unsigned_delta =
        ComputeDelta(values[i - 1], values[i], original_width_bits);
    max_unsigned_delta = std::max(unsigned_delta, max_unsigned_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();
  }

  const uint64_t delta_width_bits_unsigned = BitWidth(max_unsigned_delta);
  // This will prevent the use of signed deltas, by always assuming
  // they will not provide value over unsigned.
  // TODO(eladalon): Add support for signed deltas.
  const uint64_t delta_width_bits_signed = 64;

  // Note: Preference for unsigned if the two have the same width (efficiency).
  const bool signed_deltas =
      delta_width_bits_signed < delta_width_bits_unsigned;
  const uint64_t delta_width_bits =
      signed_deltas ? delta_width_bits_signed : delta_width_bits_unsigned;

  const bool values_optional = false;

  FixedLengthEncodingParameters params(delta_width_bits, signed_deltas,
                                       values_optional, original_width_bits);
  FixedLengthDeltaEncoder encoder(params, base, values);
  return encoder.Encode();
}

FixedLengthDeltaEncoder::FixedLengthDeltaEncoder(
    const FixedLengthEncodingParameters& params,
    uint64_t base,
    const std::vector<uint64_t>& values)
    : params_(params), base_(base), values_(values) {
  RTC_DCHECK_GE(params_.delta_width_bits, 1);
  RTC_DCHECK_LE(params_.delta_width_bits, 64);
  RTC_DCHECK_GE(params_.original_width_bits, 1);
  RTC_DCHECK_LE(params_.original_width_bits, 64);
  RTC_DCHECK_LE(params_.delta_width_bits, params_.original_width_bits);
  RTC_DCHECK(!values_.empty());
  writer_ = absl::make_unique<BitWriter>(OutputLengthBytes());
}

std::string FixedLengthDeltaEncoder::Encode() {
  EncodeHeader();

  uint64_t previous = base_;
  for (uint64_t value : values_) {
    EncodeDelta(previous, value);
    previous = value;
  }

  return writer_->GetString();
}

size_t FixedLengthDeltaEncoder::OutputLengthBytes() const {
  const size_t length_bits = HeaderLengthBits() + EncodedDeltasLengthBits();
  return BitsToBytes(length_bits);
}

size_t FixedLengthDeltaEncoder::HeaderLengthBits() const {
  if (params_.signed_deltas == kDefaultSignedDeltas &&
      params_.values_optional == kDefaultValuesOptional &&
      params_.original_width_bits == kDefaultOriginalWidthBits) {
    return kBitsInHeaderForEncodingType + kBitsInHeaderForDeltaWidthBits;
  } else {
    return kBitsInHeaderForEncodingType + kBitsInHeaderForDeltaWidthBits +
           kBitsInHeaderForSignedDeltas + kBitsInHeaderForValuesOptional +
           kBitsInHeaderForOriginalWidthBits;
  }
}

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;
}

void FixedLengthDeltaEncoder::EncodeHeader() {
  RTC_DCHECK(writer_);

  const EncodingType encoding_type =
      (params_.original_width_bits == kDefaultOriginalWidthBits &&
       params_.signed_deltas == kDefaultSignedDeltas &&
       params_.values_optional == kDefaultValuesOptional)
          ? EncodingType::kFixedSizeUnsignedDeltasNoEarlyWrapNoOpt
          : EncodingType::kFixedSizeSignedDeltasEarlyWrapAndOptSupported;

  writer_->WriteBits(static_cast<uint64_t>(encoding_type),
                     kBitsInHeaderForEncodingType);

  // Note: Since it's meaningless for a field to be of width 0, when it comes
  // to fields that relate widths, we encode  width 1 as 0, width 2 as 1,

  writer_->WriteBits(params_.delta_width_bits - 1,
                     kBitsInHeaderForDeltaWidthBits);

  if (encoding_type == EncodingType::kFixedSizeUnsignedDeltasNoEarlyWrapNoOpt) {
    return;
  }

  writer_->WriteBits(static_cast<uint64_t>(params_.signed_deltas),
                     kBitsInHeaderForSignedDeltas);
  writer_->WriteBits(static_cast<uint64_t>(params_.values_optional),
                     kBitsInHeaderForValuesOptional);
  writer_->WriteBits(params_.original_width_bits - 1,
                     kBitsInHeaderForOriginalWidthBits);
}

void FixedLengthDeltaEncoder::EncodeDelta(uint64_t previous, uint64_t current) {
  RTC_DCHECK(writer_);
  writer_->WriteBits(
      ComputeDelta(previous, current, params_.original_width_bits),
      params_.delta_width_bits);
}

// Perform decoding of a a delta-encoded stream, extracting the original
// sequence of values.
class FixedLengthDeltaDecoder final {
 public:
  // Checks whether FixedLengthDeltaDecoder is a suitable decoder for this
  // bitstream. Note that this does NOT imply that stream is valid, and will
  // be decoded successfully. It DOES imply that all other decoder classes
  // will fail to decode this input, though.
  static bool IsSuitableDecoderFor(const std::string& input);

  // Assuming that |input| is the result of fixed-size delta-encoding
  // that took place with the same value to |base| and over |num_of_deltas|
  // 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);

 private:
  // Reads the encoding header in |input| and returns a FixedLengthDeltaDecoder
  // with the corresponding configuration, that can be used to decode the
  // values in |input|.
  // If the encoding header is corrupt (contains an illegal configuration),
  // nullptr will be returned.
  // 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);

  // FixedLengthDeltaDecoder objects are to be created by DecodeDeltas() and
  // released by it before it returns. They're mostly a convenient way to
  // avoid having to pass a lot of state between different functions.
  // Therefore, it was deemed acceptable that |reader| does not own the buffer
  // it reads, meaning the lifetime of |this| must not exceed the lifetime
  // of |reader|'s underlying buffer.
  FixedLengthDeltaDecoder(std::unique_ptr<rtc::BitBuffer> reader,
                          const FixedLengthEncodingParameters& params,
                          uint64_t base,
                          size_t num_of_deltas);

  // Perform the decoding using the parameters given to the ctor.
  std::vector<uint64_t> Decode();

  // Attempt to parse a delta from the input reader.
  // Returns true/false for success/failure.
  // Writes the delta into |delta| if successful.
  bool ParseDelta(uint64_t* delta);

  // Add |delta| to |base| to produce the next value in a sequence.
  // The delta is applied as signed/unsigned depending on the parameters
  // given to the ctor. Wrap-around is taken into account according to the
  // values' width, as specified by the aforementioned encoding parameters.
  uint64_t ApplyDelta(uint64_t base, uint64_t delta) const;

  // Reader of the input stream to be decoded. Does not own that buffer.
  // See comment above ctor for details.
  const std::unique_ptr<rtc::BitBuffer> reader_;

  // The parameters according to which encoding will be done (width of
  // fields, whether signed deltas should be used, etc.)
  const FixedLengthEncodingParameters params_;

  // 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_;

  // The number of values to be known to be decoded.
  const size_t num_of_deltas_;

  // Bit mask corresponding to |params_.original_width_bits|. That is, the bits
  // necessary for encoding all of the values in the encoded sequence are on.
  // Used as an optimization.
  const uint64_t value_mask_;

  RTC_DISALLOW_COPY_AND_ASSIGN(FixedLengthDeltaDecoder);
};

bool FixedLengthDeltaDecoder::IsSuitableDecoderFor(const std::string& input) {
  if (input.length() < kBitsInHeaderForEncodingType) {
    return false;
  }

  rtc::BitBuffer reader(reinterpret_cast<const uint8_t*>(&input[0]),
                        kBitsInHeaderForEncodingType);

  uint32_t encoding_type_bits;
  const bool result =
      reader.ReadBits(&encoding_type_bits, kBitsInHeaderForEncodingType);
  RTC_DCHECK(result);

  const auto encoding_type = static_cast<EncodingType>(encoding_type_bits);
  return encoding_type ==
             EncodingType::kFixedSizeUnsignedDeltasNoEarlyWrapNoOpt ||
         encoding_type ==
             EncodingType::kFixedSizeSignedDeltasEarlyWrapAndOptSupported;
}

std::vector<uint64_t> FixedLengthDeltaDecoder::DecodeDeltas(
    const std::string& input,
    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 decoder->Decode();
}

std::unique_ptr<FixedLengthDeltaDecoder> FixedLengthDeltaDecoder::Create(
    const std::string& input,
    uint64_t base,
    size_t num_of_deltas) {
  if (input.length() < kBitsInHeaderForEncodingType) {
    return nullptr;
  }

  auto reader = absl::make_unique<rtc::BitBuffer>(
      reinterpret_cast<const uint8_t*>(&input[0]), input.length());

  // Encoding type
  uint32_t encoding_type_bits;
  const bool result =
      reader->ReadBits(&encoding_type_bits, kBitsInHeaderForEncodingType);
  RTC_DCHECK(result);
  const EncodingType encoding = static_cast<EncodingType>(encoding_type_bits);
  if (encoding != EncodingType::kFixedSizeUnsignedDeltasNoEarlyWrapNoOpt &&
      encoding !=
          EncodingType::kFixedSizeSignedDeltasEarlyWrapAndOptSupported) {
    RTC_LOG(LS_WARNING) << "Unrecognized encoding type.";
    return nullptr;
  }

  uint32_t read_buffer;

  // delta_width_bits
  if (!reader->ReadBits(&read_buffer, kBitsInHeaderForDeltaWidthBits)) {
    return nullptr;
  }
  RTC_DCHECK_LE(read_buffer, 64 - 1);  // See encoding for -1's rationale.
  const uint64_t delta_width_bits =
      read_buffer + 1;  // See encoding for +1's rationale.

  // signed_deltas, values_optional, original_width_bits
  bool signed_deltas;
  bool values_optional;
  uint64_t original_width_bits;
  if (encoding == EncodingType::kFixedSizeUnsignedDeltasNoEarlyWrapNoOpt) {
    signed_deltas = kDefaultSignedDeltas;
    values_optional = kDefaultValuesOptional;
    original_width_bits = kDefaultOriginalWidthBits;
  } else {
    // signed_deltas
    if (!reader->ReadBits(&read_buffer, kBitsInHeaderForSignedDeltas)) {
      return nullptr;
    }
    signed_deltas = rtc::dchecked_cast<bool>(read_buffer);
    if (signed_deltas) {
      RTC_LOG(LS_WARNING) << "Not implemented.";
      return nullptr;
    }

    // values_optional
    if (!reader->ReadBits(&read_buffer, kBitsInHeaderForValuesOptional)) {
      return nullptr;
    }
    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;
    }

    // original_width_bits
    if (!reader->ReadBits(&read_buffer, kBitsInHeaderForOriginalWidthBits)) {
      return nullptr;
    }
    RTC_DCHECK_LE(read_buffer, 64 - 1);     // See encoding for -1's rationale.
    original_width_bits = read_buffer + 1;  // See encoding for +1's rationale.
  }

  FixedLengthEncodingParameters params(delta_width_bits, signed_deltas,
                                       values_optional, original_width_bits);
  return absl::WrapUnique(new FixedLengthDeltaDecoder(std::move(reader), params,
                                                      base, num_of_deltas));
}

FixedLengthDeltaDecoder::FixedLengthDeltaDecoder(
    std::unique_ptr<rtc::BitBuffer> reader,
    const FixedLengthEncodingParameters& params,
    uint64_t base,
    size_t num_of_deltas)
    : reader_(std::move(reader)),
      params_(params),
      base_(base),
      num_of_deltas_(num_of_deltas),
      value_mask_(MaxValueOfBitWidth(params_.original_width_bits)) {
  RTC_DCHECK(reader_);
  // TODO(eladalon): Support signed deltas.
  RTC_DCHECK(!params.signed_deltas) << "Not implemented.";
  // 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_);

  uint64_t previous = base_;
  for (size_t i = 0; i < num_of_deltas_; ++i) {
    uint64_t delta;
    if (!ParseDelta(&delta)) {
      return std::vector<uint64_t>();
    }
    values[i] = ApplyDelta(previous, delta);
    previous = values[i];
  }

  return values;
}

bool FixedLengthDeltaDecoder::ParseDelta(uint64_t* delta) {
  RTC_DCHECK(reader_);
  RTC_DCHECK(!params_.signed_deltas) << "Not implemented.";    // Reminder.
  RTC_DCHECK(!params_.values_optional) << "Not implemented.";  // Reminder.

  // BitBuffer and BitBufferWriter read/write higher bits before lower bits.

  const size_t lower_bit_count =
      std::min<uint64_t>(params_.delta_width_bits, 32u);
  const size_t higher_bit_count =
      (params_.delta_width_bits <= 32u) ? 0 : params_.delta_width_bits - 32u;

  uint32_t lower_bits;
  uint32_t higher_bits;

  if (higher_bit_count > 0) {
    if (!reader_->ReadBits(&higher_bits, higher_bit_count)) {
      RTC_LOG(LS_WARNING) << "Failed to read higher half of delta.";
      return false;
    }
  } else {
    higher_bits = 0;
  }

  if (!reader_->ReadBits(&lower_bits, lower_bit_count)) {
    RTC_LOG(LS_WARNING) << "Failed to read lower half of delta.";
    return false;
  }

  const uint64_t lower_bits_64 = static_cast<uint64_t>(lower_bits);
  const uint64_t higher_bits_64 = static_cast<uint64_t>(higher_bits);

  *delta = (higher_bits_64 << 32) | lower_bits_64;
  return true;
}

uint64_t FixedLengthDeltaDecoder::ApplyDelta(uint64_t base,
                                             uint64_t delta) const {
  RTC_DCHECK(!params_.signed_deltas) << "Not implemented.";    // Reminder.
  RTC_DCHECK(!params_.values_optional) << "Not implemented.";  // Reminder.
  RTC_DCHECK_LE(base, MaxValueOfBitWidth(params_.original_width_bits));
  RTC_DCHECK_LE(delta, MaxValueOfBitWidth(params_.delta_width_bits));
  RTC_DCHECK_LE(params_.delta_width_bits,
                params_.original_width_bits);  // Reminder.
  return (base + delta) & value_mask_;
}

}  // namespace

std::string EncodeDeltas(uint64_t base, const std::vector<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) {
  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::fill(result.begin(), result.end(), base);
    return result;
  }

  if (FixedLengthDeltaDecoder::IsSuitableDecoderFor(input)) {
    return FixedLengthDeltaDecoder::DecodeDeltas(input, base, num_of_deltas);
  }

  RTC_LOG(LS_WARNING) << "Could not decode delta-encoded stream.";
  return std::vector<uint64_t>();
}

}  // namespace webrtc