Alexei Frolov | 8ecefe9 | 2020-01-13 10:40:08 -0800 | [diff] [blame] | 1 | // Copyright 2020 The Pigweed Authors |
Alexei Frolov | 82d3cb3 | 2019-11-27 14:38:39 -0800 | [diff] [blame] | 2 | // |
| 3 | // Licensed under the Apache License, Version 2.0 (the "License"); you may not |
Wyatt Hepler | 8c493bb | 2019-12-02 14:49:21 -0800 | [diff] [blame] | 4 | // use this file except in compliance with the License. You may obtain a copy of |
| 5 | // the License at |
Alexei Frolov | 82d3cb3 | 2019-11-27 14:38:39 -0800 | [diff] [blame] | 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 |
Wyatt Hepler | 8c493bb | 2019-12-02 14:49:21 -0800 | [diff] [blame] | 12 | // License for the specific language governing permissions and limitations under |
| 13 | // the License. |
Alexei Frolov | 82d3cb3 | 2019-11-27 14:38:39 -0800 | [diff] [blame] | 14 | |
| 15 | #include "pw_varint/varint.h" |
| 16 | |
| 17 | #include <algorithm> |
| 18 | |
Wyatt Hepler | 588907a | 2020-01-16 16:34:58 -0800 | [diff] [blame] | 19 | namespace pw { |
| 20 | namespace varint { |
Alexei Frolov | 247efd9 | 2021-03-10 20:16:16 -0800 | [diff] [blame] | 21 | namespace { |
Alexei Frolov | 82d3cb3 | 2019-11-27 14:38:39 -0800 | [diff] [blame] | 22 | |
Alexei Frolov | 247efd9 | 2021-03-10 20:16:16 -0800 | [diff] [blame] | 23 | inline bool ZeroTerminated(pw_varint_Format format) { |
| 24 | return (static_cast<unsigned>(format) & 0b10) == 0; |
| 25 | } |
| 26 | |
| 27 | inline bool LeastSignificant(pw_varint_Format format) { |
| 28 | return (static_cast<unsigned>(format) & 0b01) == 0; |
| 29 | } |
| 30 | |
| 31 | } // namespace |
| 32 | |
Ted Pudlik | 4180d4d | 2021-10-28 00:07:29 +0000 | [diff] [blame] | 33 | extern "C" size_t pw_varint_EncodeCustom(uint64_t integer, |
Alexei Frolov | 247efd9 | 2021-03-10 20:16:16 -0800 | [diff] [blame] | 34 | void* output, |
| 35 | size_t output_size, |
| 36 | pw_varint_Format format) { |
Alexei Frolov | 82d3cb3 | 2019-11-27 14:38:39 -0800 | [diff] [blame] | 37 | size_t written = 0; |
Alexei Frolov | 8ecefe9 | 2020-01-13 10:40:08 -0800 | [diff] [blame] | 38 | std::byte* buffer = static_cast<std::byte*>(output); |
| 39 | |
Alexei Frolov | 247efd9 | 2021-03-10 20:16:16 -0800 | [diff] [blame] | 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 | |
Alexei Frolov | 82d3cb3 | 2019-11-27 14:38:39 -0800 | [diff] [blame] | 52 | do { |
Alexei Frolov | 8ecefe9 | 2020-01-13 10:40:08 -0800 | [diff] [blame] | 53 | if (written >= output_size) { |
Alexei Frolov | 82d3cb3 | 2019-11-27 14:38:39 -0800 | [diff] [blame] | 54 | return 0; |
| 55 | } |
| 56 | |
Ted Pudlik | 4180d4d | 2021-10-28 00:07:29 +0000 | [diff] [blame] | 57 | bool last_byte = (integer >> 7) == 0u; |
Alexei Frolov | 82d3cb3 | 2019-11-27 14:38:39 -0800 | [diff] [blame] | 58 | |
Alexei Frolov | 247efd9 | 2021-03-10 20:16:16 -0800 | [diff] [blame] | 59 | // Grab 7 bits and set the eighth according to the continuation bit. |
Ted Pudlik | 4180d4d | 2021-10-28 00:07:29 +0000 | [diff] [blame] | 60 | std::byte value = (static_cast<std::byte>(integer) & std::byte(0x7f)) |
Alexei Frolov | 247efd9 | 2021-03-10 20:16:16 -0800 | [diff] [blame] | 61 | << value_shift; |
| 62 | |
| 63 | if (last_byte) { |
| 64 | value |= term; |
| 65 | } else { |
| 66 | value |= cont; |
| 67 | } |
| 68 | |
| 69 | buffer[written++] = value; |
Ted Pudlik | 4180d4d | 2021-10-28 00:07:29 +0000 | [diff] [blame] | 70 | integer >>= 7; |
| 71 | } while (integer != 0u); |
Alexei Frolov | 247efd9 | 2021-03-10 20:16:16 -0800 | [diff] [blame] | 72 | |
Alexei Frolov | 82d3cb3 | 2019-11-27 14:38:39 -0800 | [diff] [blame] | 73 | return written; |
| 74 | } |
| 75 | |
Alexei Frolov | 247efd9 | 2021-03-10 20:16:16 -0800 | [diff] [blame] | 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) { |
Alexei Frolov | 82d3cb3 | 2019-11-27 14:38:39 -0800 | [diff] [blame] | 80 | uint64_t decoded_value = 0; |
| 81 | uint_fast8_t count = 0; |
Alexei Frolov | 8ecefe9 | 2020-01-13 10:40:08 -0800 | [diff] [blame] | 82 | const std::byte* buffer = static_cast<const std::byte*>(input); |
Alexei Frolov | 82d3cb3 | 2019-11-27 14:38:39 -0800 | [diff] [blame] | 83 | |
| 84 | // The largest 64-bit ints require 10 B. |
Ewout van Bekkum | bd33812 | 2020-09-22 16:32:45 -0700 | [diff] [blame] | 85 | const size_t max_count = std::min(kMaxVarint64SizeBytes, input_size); |
Alexei Frolov | 82d3cb3 | 2019-11-27 14:38:39 -0800 | [diff] [blame] | 86 | |
Alexei Frolov | 247efd9 | 2021-03-10 20:16:16 -0800 | [diff] [blame] | 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 | |
Alexei Frolov | 82d3cb3 | 2019-11-27 14:38:39 -0800 | [diff] [blame] | 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. |
Alexei Frolov | 247efd9 | 2021-03-10 20:16:16 -0800 | [diff] [blame] | 111 | decoded_value |= static_cast<uint64_t>((buffer[count] & mask) >> shift) |
Alexei Frolov | 82d3cb3 | 2019-11-27 14:38:39 -0800 | [diff] [blame] | 112 | << (7 * count); |
| 113 | |
Alexei Frolov | 247efd9 | 2021-03-10 20:16:16 -0800 | [diff] [blame] | 114 | // Stop decoding if the end is reached. |
| 115 | if (is_last_byte(buffer[count++])) { |
Alexei Frolov | 82d3cb3 | 2019-11-27 14:38:39 -0800 | [diff] [blame] | 116 | break; |
| 117 | } |
| 118 | } |
| 119 | |
Alexei Frolov | 8ecefe9 | 2020-01-13 10:40:08 -0800 | [diff] [blame] | 120 | *output = decoded_value; |
Alexei Frolov | 82d3cb3 | 2019-11-27 14:38:39 -0800 | [diff] [blame] | 121 | return count; |
| 122 | } |
| 123 | |
Alexei Frolov | b9fda58 | 2021-03-13 18:02:52 -0800 | [diff] [blame] | 124 | // TODO(frolv): Remove this deprecated alias. |
Alexei Frolov | 247efd9 | 2021-03-10 20:16:16 -0800 | [diff] [blame] | 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 | |
| 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 | |
Alexei Frolov | b9fda58 | 2021-03-13 18:02:52 -0800 | [diff] [blame] | 137 | // TODO(frolv): Remove this deprecated alias. |
Alexei Frolov | 247efd9 | 2021-03-10 20:16:16 -0800 | [diff] [blame] | 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 | |
| 144 | extern "C" size_t pw_varint_ZigZagDecode(const void* input, |
| 145 | size_t input_size, |
| 146 | int64_t* output) { |
Alexei Frolov | 8ecefe9 | 2020-01-13 10:40:08 -0800 | [diff] [blame] | 147 | uint64_t value = 0; |
Alexei Frolov | 247efd9 | 2021-03-10 20:16:16 -0800 | [diff] [blame] | 148 | size_t bytes = pw_varint_Decode(input, input_size, &value); |
Alexei Frolov | 8ecefe9 | 2020-01-13 10:40:08 -0800 | [diff] [blame] | 149 | *output = ZigZagDecode(value); |
| 150 | return bytes; |
| 151 | } |
| 152 | |
Alexei Frolov | 247efd9 | 2021-03-10 20:16:16 -0800 | [diff] [blame] | 153 | extern "C" size_t pw_varint_EncodedSize(uint64_t integer) { |
Ewout van Bekkum | dc6d984 | 2020-09-23 18:05:19 -0700 | [diff] [blame] | 154 | return EncodedSize(integer); |
Alexei Frolov | 388d4b9 | 2020-05-20 13:30:07 -0700 | [diff] [blame] | 155 | } |
| 156 | |
Alexei Frolov | 247efd9 | 2021-03-10 20:16:16 -0800 | [diff] [blame] | 157 | extern "C" size_t pw_varint_ZigZagEncodedSize(int64_t integer) { |
Ewout van Bekkum | dc6d984 | 2020-09-23 18:05:19 -0700 | [diff] [blame] | 158 | return ZigZagEncodedSize(integer); |
Alexei Frolov | 388d4b9 | 2020-05-20 13:30:07 -0700 | [diff] [blame] | 159 | } |
| 160 | |
Wyatt Hepler | 588907a | 2020-01-16 16:34:58 -0800 | [diff] [blame] | 161 | } // namespace varint |
| 162 | } // namespace pw |