1 // Copyright 2021 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifndef V8_BASE_VLQ_H_
6 #define V8_BASE_VLQ_H_
7
8 #include <limits>
9 #include <vector>
10
11 #include "src/base/memory.h"
12
13 namespace v8 {
14 namespace base {
15
16 static constexpr uint32_t kContinueShift = 7;
17 static constexpr uint32_t kContinueBit = 1 << kContinueShift;
18 static constexpr uint32_t kDataMask = kContinueBit - 1;
19
20 // Encodes an unsigned value using variable-length encoding and stores it using
21 // the passed process_byte function. The function should return a pointer to
22 // the byte that was written, so that VLQEncodeUnsigned can mutate it after
23 // writing it.
24 template <typename Function>
25 inline typename std::enable_if<
26 std::is_same<decltype(std::declval<Function>()(0)), byte*>::value,
27 void>::type
VLQEncodeUnsigned(Function && process_byte,uint32_t value)28 VLQEncodeUnsigned(Function&& process_byte, uint32_t value) {
29 byte* written_byte = process_byte(value);
30 if (value <= kDataMask) {
31 // Value fits in first byte, early return.
32 return;
33 }
34 do {
35 // Turn on continuation bit in the byte we just wrote.
36 *written_byte |= kContinueBit;
37 value >>= kContinueShift;
38 written_byte = process_byte(value);
39 } while (value > kDataMask);
40 }
41
42 // Encodes value using variable-length encoding and stores it using the passed
43 // process_byte function.
44 template <typename Function>
45 inline typename std::enable_if<
46 std::is_same<decltype(std::declval<Function>()(0)), byte*>::value,
47 void>::type
VLQEncode(Function && process_byte,int32_t value)48 VLQEncode(Function&& process_byte, int32_t value) {
49 // This wouldn't handle kMinInt correctly if it ever encountered it.
50 DCHECK_NE(value, std::numeric_limits<int32_t>::min());
51 bool is_negative = value < 0;
52 // Encode sign in least significant bit.
53 uint32_t bits = static_cast<uint32_t>((is_negative ? -value : value) << 1) |
54 static_cast<uint32_t>(is_negative);
55 VLQEncodeUnsigned(std::forward<Function>(process_byte), bits);
56 }
57
58 // Wrapper of VLQEncode for std::vector backed storage containers.
59 template <typename A>
VLQEncode(std::vector<byte,A> * data,int32_t value)60 inline void VLQEncode(std::vector<byte, A>* data, int32_t value) {
61 VLQEncode(
62 [data](byte value) {
63 data->push_back(value);
64 return &data->back();
65 },
66 value);
67 }
68
69 // Wrapper of VLQEncodeUnsigned for std::vector backed storage containers.
70 template <typename A>
VLQEncodeUnsigned(std::vector<byte,A> * data,uint32_t value)71 inline void VLQEncodeUnsigned(std::vector<byte, A>* data, uint32_t value) {
72 VLQEncodeUnsigned(
73 [data](byte value) {
74 data->push_back(value);
75 return &data->back();
76 },
77 value);
78 }
79
80 // Decodes a variable-length encoded unsigned value from bytes returned by
81 // successive calls to the given function.
82 template <typename GetNextFunction>
83 inline typename std::enable_if<
84 std::is_same<decltype(std::declval<GetNextFunction>()()), byte>::value,
85 uint32_t>::type
VLQDecodeUnsigned(GetNextFunction && get_next)86 VLQDecodeUnsigned(GetNextFunction&& get_next) {
87 byte cur_byte = get_next();
88 // Single byte fast path; no need to mask.
89 if (cur_byte <= kDataMask) {
90 return cur_byte;
91 }
92 uint32_t bits = cur_byte & kDataMask;
93 for (int shift = kContinueShift; shift <= 32; shift += kContinueShift) {
94 cur_byte = get_next();
95 bits |= (cur_byte & kDataMask) << shift;
96 if (cur_byte <= kDataMask) break;
97 }
98 return bits;
99 }
100
101 // Decodes a variable-length encoded unsigned value stored in contiguous memory
102 // starting at data_start + index, updating index to where the next encoded
103 // value starts.
VLQDecodeUnsigned(byte * data_start,int * index)104 inline uint32_t VLQDecodeUnsigned(byte* data_start, int* index) {
105 return VLQDecodeUnsigned([&] { return data_start[(*index)++]; });
106 }
107
108 // Decodes a variable-length encoded value stored in contiguous memory starting
109 // at data_start + index, updating index to where the next encoded value starts.
VLQDecode(byte * data_start,int * index)110 inline int32_t VLQDecode(byte* data_start, int* index) {
111 uint32_t bits = VLQDecodeUnsigned(data_start, index);
112 bool is_negative = (bits & 1) == 1;
113 int32_t result = bits >> 1;
114 return is_negative ? -result : result;
115 }
116
117 } // namespace base
118 } // namespace v8
119
120 #endif // V8_BASE_VLQ_H_
121