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 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 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