delta_encoding.cc | Explore in Territory

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

#include "absl/memory/memory.h"
#include "absl/strings/string_view.h"
#include "absl/types/optional.h"
#include "logging/rtc_event_log/encoder/bit_writer.h"
#include "logging/rtc_event_log/encoder/var_int.h"
#include "rtc_base/bitstream_reader.h"
#include "rtc_base/checks.h"
#include "rtc_base/logging.h"

namespace webrtc {
namespace {

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

bool g_force_unsigned_for_testing = …;
bool g_force_signed_for_testing = …;

size_t BitsToBytes(size_t bits) { … }

// TODO(eladalon): Replace by something more efficient.
uint64_t UnsignedBitWidth(uint64_t input, bool zero_val_as_zero_width = false) { … }

uint64_t SignedBitWidth(uint64_t max_pos_magnitude,
                        uint64_t max_neg_magnitude) { … }

// Return the maximum integer of a given bit width.
// Examples:
// MaxUnsignedValueOfBitWidth(1) = 0x01
// MaxUnsignedValueOfBitWidth(6) = 0x3f
// MaxUnsignedValueOfBitWidth(8) = 0xff
// MaxUnsignedValueOfBitWidth(32) = 0xffffffff
uint64_t MaxUnsignedValueOfBitWidth(uint64_t bit_width) { … }

// Computes the delta between `previous` and `current`, under the assumption
// that wrap-around occurs after `width` is exceeded.
uint64_t UnsignedDelta(uint64_t previous, uint64_t current, uint64_t bit_mask) { … }

// 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 { … };

// 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 = …;
constexpr size_t kBitsInHeaderForDeltaWidthBits = …;
constexpr size_t kBitsInHeaderForSignedDeltas = …;
constexpr size_t kBitsInHeaderForValuesOptional = …;
constexpr size_t kBitsInHeaderForValueWidthBits = …;

static_assert …;

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

// Parameters for fixed-size delta-encoding/decoding.
// These are tailored for the sequence which will be encoded (e.g. widths).
class FixedLengthEncodingParameters final { … };

// 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 { … };

// TODO(eladalon): Reduce the number of passes.
std::string FixedLengthDeltaEncoder::EncodeDeltas(
    absl::optional<uint64_t> base,
    const std::vector<absl::optional<uint64_t>>& values) { … }

void FixedLengthDeltaEncoder::CalculateMinAndMaxDeltas(
    absl::optional<uint64_t> base,
    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,
    uint64_t* min_neg_signed_delta_out) { … }

void FixedLengthDeltaEncoder::ConsiderTestOverrides(
    FixedLengthEncodingParameters* params,
    uint64_t delta_width_bits_signed,
    uint64_t delta_width_bits_unsigned) { … }

FixedLengthDeltaEncoder::FixedLengthDeltaEncoder(
    const FixedLengthEncodingParameters& params,
    absl::optional<uint64_t> base,
    const std::vector<absl::optional<uint64_t>>& values,
    size_t existent_values_count)
    : … { … }

std::string FixedLengthDeltaEncoder::Encode() { … }

size_t FixedLengthDeltaEncoder::OutputLengthBytes(
    size_t existent_values_count) const { … }

size_t FixedLengthDeltaEncoder::HeaderLengthBits() const { … }

size_t FixedLengthDeltaEncoder::EncodedDeltasLengthBits(
    size_t existent_values_count) const { … }

void FixedLengthDeltaEncoder::EncodeHeader() { … }

void FixedLengthDeltaEncoder::EncodeDelta(uint64_t previous, uint64_t current) { … }

void FixedLengthDeltaEncoder::EncodeUnsignedDelta(uint64_t previous,
                                                  uint64_t current) { … }

void FixedLengthDeltaEncoder::EncodeSignedDelta(uint64_t previous,
                                                uint64_t current) { … }

// Perform decoding of a a delta-encoded stream, extracting the original
// sequence of values.
class FixedLengthDeltaDecoder final { … };

bool FixedLengthDeltaDecoder::IsSuitableDecoderFor(absl::string_view input) { … }

std::vector<absl::optional<uint64_t>> FixedLengthDeltaDecoder::DecodeDeltas(
    absl::string_view input,
    absl::optional<uint64_t> base,
    size_t num_of_deltas) { … }

std::unique_ptr<FixedLengthDeltaDecoder> FixedLengthDeltaDecoder::Create(
    absl::string_view input,
    absl::optional<uint64_t> base,
    size_t num_of_deltas) { … }

FixedLengthDeltaDecoder::FixedLengthDeltaDecoder(
    BitstreamReader reader,
    const FixedLengthEncodingParameters& params,
    absl::optional<uint64_t> base,
    size_t num_of_deltas)
    : … { … }

std::vector<absl::optional<uint64_t>> FixedLengthDeltaDecoder::Decode() { … }

uint64_t FixedLengthDeltaDecoder::ApplyDelta(uint64_t base,
                                             uint64_t delta) const { … }

uint64_t FixedLengthDeltaDecoder::ApplyUnsignedDelta(uint64_t base,
                                                     uint64_t delta) const { … }

uint64_t FixedLengthDeltaDecoder::ApplySignedDelta(uint64_t base,
                                                   uint64_t delta) const { … }

}  // namespace

std::string EncodeDeltas(absl::optional<uint64_t> base,
                         const std::vector<absl::optional<uint64_t>>& values) { … }

std::vector<absl::optional<uint64_t>> DecodeDeltas(
    absl::string_view input,
    absl::optional<uint64_t> base,
    size_t num_of_deltas) { … }

void SetFixedLengthEncoderDeltaSignednessForTesting(bool signedness) { … }

void UnsetFixedLengthEncoderDeltaSignednessForTesting() { … }

}  // namespace webrtc
chromium/third_party/webrtc/logging/rtc_event_log/encoder/delta_encoding.cc
