1 // Copyright 2020 The Pigweed Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
4 // use this file except in compliance with the License. You may obtain a copy of
5 // the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
12 // License for the specific language governing permissions and limitations under
13 // the License.
14
15 #include "pw_varint/varint.h"
16
17 #include <algorithm>
18
19 namespace pw {
20 namespace varint {
21 namespace {
22
ZeroTerminated(pw_varint_Format format)23 inline bool ZeroTerminated(pw_varint_Format format) {
24 return (static_cast<unsigned>(format) & 0b10) == 0;
25 }
26
LeastSignificant(pw_varint_Format format)27 inline bool LeastSignificant(pw_varint_Format format) {
28 return (static_cast<unsigned>(format) & 0b01) == 0;
29 }
30
31 } // namespace
32
pw_varint_EncodeCustom(uint64_t input,void * output,size_t output_size,pw_varint_Format format)33 extern "C" size_t pw_varint_EncodeCustom(uint64_t input,
34 void* output,
35 size_t output_size,
36 pw_varint_Format format) {
37 size_t written = 0;
38 std::byte* buffer = static_cast<std::byte*>(output);
39
40 int value_shift = LeastSignificant(format) ? 1 : 0;
41 int term_shift = value_shift == 1 ? 0 : 7;
42
43 std::byte cont, term;
44 if (ZeroTerminated(format)) {
45 cont = std::byte(0x01) << term_shift;
46 term = std::byte(0x00) << term_shift;
47 } else {
48 cont = std::byte(0x00) << term_shift;
49 term = std::byte(0x01) << term_shift;
50 }
51
52 do {
53 if (written >= output_size) {
54 return 0;
55 }
56
57 bool last_byte = (input >> 7) == 0u;
58
59 // Grab 7 bits and set the eighth according to the continuation bit.
60 std::byte value = (static_cast<std::byte>(input) & std::byte(0x7f))
61 << value_shift;
62
63 if (last_byte) {
64 value |= term;
65 } else {
66 value |= cont;
67 }
68
69 buffer[written++] = value;
70 input >>= 7;
71 } while (input != 0u);
72
73 return written;
74 }
75
pw_varint_DecodeCustom(const void * input,size_t input_size,uint64_t * output,pw_varint_Format format)76 extern "C" size_t pw_varint_DecodeCustom(const void* input,
77 size_t input_size,
78 uint64_t* output,
79 pw_varint_Format format) {
80 uint64_t decoded_value = 0;
81 uint_fast8_t count = 0;
82 const std::byte* buffer = static_cast<const std::byte*>(input);
83
84 // The largest 64-bit ints require 10 B.
85 const size_t max_count = std::min(kMaxVarint64SizeBytes, input_size);
86
87 std::byte mask;
88 uint32_t shift;
89 if (LeastSignificant(format)) {
90 mask = std::byte(0xfe);
91 shift = 1;
92 } else {
93 mask = std::byte(0x7f);
94 shift = 0;
95 }
96
97 // Determines whether a byte is the last byte of a varint.
98 auto is_last_byte = [&](std::byte byte) {
99 if (ZeroTerminated(format)) {
100 return (byte & ~mask) == std::byte(0);
101 }
102 return (byte & ~mask) != std::byte(0);
103 };
104
105 while (true) {
106 if (count >= max_count) {
107 return 0;
108 }
109
110 // Add the bottom seven bits of the next byte to the result.
111 decoded_value |= static_cast<uint64_t>((buffer[count] & mask) >> shift)
112 << (7 * count);
113
114 // Stop decoding if the end is reached.
115 if (is_last_byte(buffer[count++])) {
116 break;
117 }
118 }
119
120 *output = decoded_value;
121 return count;
122 }
123
124 // TODO(frolv): Remove this deprecated alias.
pw_VarintEncode(uint64_t integer,void * output,size_t output_size)125 extern "C" size_t pw_VarintEncode(uint64_t integer,
126 void* output,
127 size_t output_size) {
128 return pw_varint_Encode(integer, output, output_size);
129 }
130
pw_varint_ZigZagEncode(int64_t integer,void * output,size_t output_size)131 extern "C" size_t pw_varint_ZigZagEncode(int64_t integer,
132 void* output,
133 size_t output_size) {
134 return pw_varint_Encode(ZigZagEncode(integer), output, output_size);
135 }
136
137 // TODO(frolv): Remove this deprecated alias.
pw_VarintDecode(const void * input,size_t input_size,uint64_t * output)138 extern "C" size_t pw_VarintDecode(const void* input,
139 size_t input_size,
140 uint64_t* output) {
141 return pw_varint_Decode(input, input_size, output);
142 }
143
pw_varint_ZigZagDecode(const void * input,size_t input_size,int64_t * output)144 extern "C" size_t pw_varint_ZigZagDecode(const void* input,
145 size_t input_size,
146 int64_t* output) {
147 uint64_t value = 0;
148 size_t bytes = pw_varint_Decode(input, input_size, &value);
149 *output = ZigZagDecode(value);
150 return bytes;
151 }
152
pw_varint_EncodedSize(uint64_t integer)153 extern "C" size_t pw_varint_EncodedSize(uint64_t integer) {
154 return EncodedSize(integer);
155 }
156
pw_varint_ZigZagEncodedSize(int64_t integer)157 extern "C" size_t pw_varint_ZigZagEncodedSize(int64_t integer) {
158 return ZigZagEncodedSize(integer);
159 }
160
161 } // namespace varint
162 } // namespace pw
163