1 /*
2 * Copyright 2021 Google LLC
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16 #pragma once
17
18 #include <cstdint>
19
20 #include "bits_util.h"
21
22 class Varint {
23 public:
24 // Maximum lengths of varint encoding of uint64
25 static constexpr int kMax64 = 10;
26
27 // REQUIRES "ptr" points to a buffer of length sufficient to hold "v".
28 // EFFECTS Encodes "v" into "ptr" and returns a pointer to the
29 // byte just past the last encoded byte.
30 static char* Encode32(char* ptr, uint32_t v);
31 static char* Encode64(char* ptr, uint64_t v);
32
33 // EFFECTS Returns the encoding length of the specified value.
34 static int Length64(uint64_t v);
35
36 private:
37 // A fully inlined version of Encode32: useful in the most time critical
38 // routines, but its code size is large
39 static char* Encode32Inline(char* ptr, uint32_t v);
40 };
41
Length64(uint64_t v)42 inline int Varint::Length64(uint64_t v) {
43 // This computes value == 0 ? 1 : floor(log2(v)) / 7 + 1 using an explicit
44 // multiplication to implement the division of a number in the 1..63 range.
45 // Explicit OR 0x1 to handle v == 0.
46 uint32_t log2value = BitsUtil::Log2FloorNonZero64(v | 0x1);
47 return static_cast<int>((log2value * 9 + 73) / 64);
48 }
49
Encode32Inline(char * sptr,uint32_t v)50 inline char* Varint::Encode32Inline(char* sptr, uint32_t v) {
51 // Operate on characters as unsigneds
52 uint8_t* ptr = reinterpret_cast<uint8_t*>(sptr);
53 static const uint32_t B = 128;
54 if (v < (1 << 7)) {
55 *(ptr++) = static_cast<uint8_t>(v);
56 } else if (v < (1 << 14)) {
57 *(ptr++) = static_cast<uint8_t>(v | B);
58 *(ptr++) = static_cast<uint8_t>(v >> 7);
59 } else if (v < (1 << 21)) {
60 *(ptr++) = static_cast<uint8_t>(v | B);
61 *(ptr++) = static_cast<uint8_t>((v >> 7) | B);
62 *(ptr++) = static_cast<uint8_t>(v >> 14);
63 } else if (v < (1 << 28)) {
64 *(ptr++) = static_cast<uint8_t>(v | B);
65 *(ptr++) = static_cast<uint8_t>((v >> 7) | B);
66 *(ptr++) = static_cast<uint8_t>((v >> 14) | B);
67 *(ptr++) = static_cast<uint8_t>(v >> 21);
68 } else {
69 *(ptr++) = static_cast<uint8_t>(v | B);
70 *(ptr++) = static_cast<uint8_t>((v >> 7) | B);
71 *(ptr++) = static_cast<uint8_t>((v >> 14) | B);
72 *(ptr++) = static_cast<uint8_t>((v >> 21) | B);
73 *(ptr++) = static_cast<uint8_t>(v >> 28);
74 }
75 return reinterpret_cast<char*>(ptr);
76 }
77