xref: /third_party/node/deps/v8/src/base/vlq.h (revision 1cb0ef41) 
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
13namespace v8 {
14namespace base {
15
16static constexpr uint32_t kContinueShift = 7;
17static constexpr uint32_t kContinueBit = 1 << kContinueShift;
18static 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.
24template <typename Function>
25inline typename std::enable_if<
26    std::is_same<decltype(std::declval<Function>()(0)), byte*>::value,
27    void>::type
28VLQEncodeUnsigned(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.
44template <typename Function>
45inline typename std::enable_if<
46    std::is_same<decltype(std::declval<Function>()(0)), byte*>::value,
47    void>::type
48VLQEncode(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.
59template <typename A>
60inline 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.
70template <typename A>
71inline 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.
82template <typename GetNextFunction>
83inline typename std::enable_if<
84    std::is_same<decltype(std::declval<GetNextFunction>()()), byte>::value,
85    uint32_t>::type
86VLQDecodeUnsigned(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.
104inline 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.
110inline 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