1 /*
2 * Copyright (c) 2021 The WebRTC project authors. All Rights Reserved.
3 *
4 * Use of this source code is governed by a BSD-style license
5 * that can be found in the LICENSE file in the root of the source
6 * tree. An additional intellectual property rights grant can be found
7 * in the file PATENTS. All contributing project authors may
8 * be found in the AUTHORS file in the root of the source tree.
9 */
10
11 #include "logging/rtc_event_log/events/fixed_length_encoding_parameters_v3.h"
12
13 #include <algorithm>
14
15 #include "absl/types/optional.h"
16 #include "api/array_view.h"
17 #include "logging/rtc_event_log/events/rtc_event_field_extraction.h"
18 #include "rtc_base/logging.h"
19
20 using webrtc_event_logging::MaxUnsignedValueOfBitWidth;
21 using webrtc_event_logging::SignedBitWidth;
22 using webrtc_event_logging::UnsignedBitWidth;
23 using webrtc_event_logging::UnsignedDelta;
24
25 namespace webrtc {
26
27 FixedLengthEncodingParametersV3
CalculateParameters(uint64_t base,const rtc::ArrayView<const uint64_t> values,uint64_t value_bit_width,bool values_optional)28 FixedLengthEncodingParametersV3::CalculateParameters(
29 uint64_t base,
30 const rtc::ArrayView<const uint64_t> values,
31 uint64_t value_bit_width,
32 bool values_optional) {
33 // As a special case, if all of the elements are identical to the base
34 // we just encode the base value with a special delta header.
35 if (std::all_of(values.cbegin(), values.cend(),
36 [base](uint64_t val) { return val == base; })) {
37 // Delta header with signed=true and delta_bitwidth=64
38 return FixedLengthEncodingParametersV3(/*delta_bit_width=*/64,
39 /*signed_deltas=*/true,
40 values_optional, value_bit_width);
41 }
42
43 const uint64_t bit_mask = MaxUnsignedValueOfBitWidth(value_bit_width);
44
45 // Calculate the bitwidth required to encode all deltas when using a
46 // unsigned or signed represenation, respectively. For the unsigned
47 // representation, we just track the largest delta. For the signed
48 // representation, we have two possibilities for each delta; either
49 // going "forward" (i.e. current - previous) or "backwards"
50 // (i.e. previous - current) where both values are calculated with
51 // wrap around. We then track the largest positive and negative
52 // magnitude across the batch, assuming that we choose the smaller
53 // delta for each element.
54 uint64_t max_unsigned_delta = 0;
55 uint64_t max_positive_signed_delta = 0;
56 uint64_t min_negative_signed_delta = 0;
57 uint64_t prev = base;
58 for (uint64_t current : values) {
59 uint64_t positive_delta = UnsignedDelta(prev, current, bit_mask);
60 uint64_t negative_delta = UnsignedDelta(current, prev, bit_mask);
61
62 max_unsigned_delta = std::max(max_unsigned_delta, positive_delta);
63
64 if (positive_delta < negative_delta) {
65 max_positive_signed_delta =
66 std::max(max_positive_signed_delta, positive_delta);
67 } else {
68 min_negative_signed_delta =
69 std::max(min_negative_signed_delta, negative_delta);
70 }
71
72 prev = current;
73 }
74
75 // We now know the largest unsigned delta and the largest magnitudes of
76 // positive and negative signed deltas. Get the bitwidths required for
77 // each of the two encodings.
78 const uint64_t unsigned_delta_bit_width =
79 UnsignedBitWidth(max_unsigned_delta);
80 const uint64_t signed_delta_bit_width =
81 SignedBitWidth(max_positive_signed_delta, min_negative_signed_delta);
82
83 // Note: Preference for unsigned if the two have the same width (efficiency).
84 bool use_signed_deltas = signed_delta_bit_width < unsigned_delta_bit_width;
85 uint64_t delta_bit_width =
86 use_signed_deltas ? signed_delta_bit_width : unsigned_delta_bit_width;
87
88 // use_signed_deltas && delta_bit_width==64 is reserved for "all values
89 // equal".
90 RTC_DCHECK(!use_signed_deltas || delta_bit_width < 64);
91
92 RTC_DCHECK(ValidParameters(delta_bit_width, use_signed_deltas,
93 values_optional, value_bit_width));
94 return FixedLengthEncodingParametersV3(delta_bit_width, use_signed_deltas,
95 values_optional, value_bit_width);
96 }
97
DeltaHeaderAsInt() const98 uint64_t FixedLengthEncodingParametersV3::DeltaHeaderAsInt() const {
99 uint64_t header = delta_bit_width_ - 1;
100 RTC_CHECK_LT(header, 1u << 6);
101 if (signed_deltas_) {
102 header += 1u << 6;
103 }
104 RTC_CHECK_LT(header, 1u << 7);
105 if (values_optional_) {
106 header += 1u << 7;
107 }
108 return header;
109 }
110
111 absl::optional<FixedLengthEncodingParametersV3>
ParseDeltaHeader(uint64_t header,uint64_t value_bit_width)112 FixedLengthEncodingParametersV3::ParseDeltaHeader(uint64_t header,
113 uint64_t value_bit_width) {
114 uint64_t delta_bit_width = (header & ((1u << 6) - 1)) + 1;
115 bool signed_deltas = header & (1u << 6);
116 bool values_optional = header & (1u << 7);
117
118 if (header >= (1u << 8)) {
119 RTC_LOG(LS_ERROR) << "Failed to parse delta header; unread bits remaining.";
120 return absl::nullopt;
121 }
122
123 if (!ValidParameters(delta_bit_width, signed_deltas, values_optional,
124 value_bit_width)) {
125 RTC_LOG(LS_ERROR) << "Failed to parse delta header. Invalid combination of "
126 "values: delta_bit_width="
127 << delta_bit_width << " signed_deltas=" << signed_deltas
128 << " values_optional=" << values_optional
129 << " value_bit_width=" << value_bit_width;
130 return absl::nullopt;
131 }
132
133 return FixedLengthEncodingParametersV3(delta_bit_width, signed_deltas,
134 values_optional, value_bit_width);
135 }
136
137 } // namespace webrtc
138