1 // Copyright 2008 Google Inc. 2 // Author: Lincoln Smith 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 #ifndef OPEN_VCDIFF_VARINT_BIGENDIAN_H_ 17 #define OPEN_VCDIFF_VARINT_BIGENDIAN_H_ 18 19 // Functions for manipulating variable-length integers as described in 20 // RFC 3284, section 2. (See http://www.ietf.org/rfc/rfc3284.txt) 21 // This is the same format used by the Sfio library 22 // and by the public-domain Sqlite package. 23 // 24 // The implementation found in this file contains buffer bounds checks 25 // (not available in sqlite) and its goal is to improve speed 26 // by using as few test-and-branch instructions as possible. 27 // 28 // The Sqlite format has the refinement that, if a 64-bit value is expected, 29 // the ninth byte of the varint does not have a continuation bit, but instead 30 // encodes 8 bits of information. This allows 64 bits to be encoded compactly 31 // in nine bytes. However, that refinement does not appear in the format 32 // description in RFC 3284, and so it is not used here. In any case, 33 // this header file deals only with *signed* integer types, and so a 34 // "64-bit" integer is allowed to have only 63 significant bits; an additional 35 // 64th bit would indicate a negative value and therefore an error. 36 // 37 38 #include <config.h> 39 #include <stdint.h> // int32_t, int64_t 40 #include <string> 41 #include "vcdiff_defs.h" // RESULT_ERROR 42 43 namespace open_vcdiff { 44 45 class OutputStringInterface; 46 47 // This helper class is needed in order to ensure that 48 // VarintBE<SignedIntegerType>::kMaxBytes is treated 49 // as a compile-time constant when it is used as the size 50 // of a static array. 51 template <typename SignedIntegerType> class VarintMaxBytes; 52 53 // 31 bits of data / 7 bits per byte <= 5 bytes 54 template<> class VarintMaxBytes<int32_t> { 55 public: 56 static const int kMaxBytes = 5; 57 }; 58 59 // 63 bits of data / 7 bits per byte == 9 bytes 60 template<> class VarintMaxBytes<int64_t> { 61 public: 62 static const int kMaxBytes = 9; 63 }; 64 65 // Objects of type VarintBE should not be instantiated. The class is a 66 // container for big-endian constant values and functions used to parse 67 // and write a particular signed integer type. 68 // Example: to parse a 32-bit integer value stored as a big-endian varint, use 69 // int32_t value = VarintBE<int32_t>::Parse(&ptr, limit); 70 // Only 32-bit and 64-bit signed integers (int32_t and int64_t) are supported. 71 // Using a different type as the template argument will likely result 72 // in a link-time error for an undefined Parse() or Append() function. 73 // 74 template <typename SignedIntegerType> 75 class VarintBE { // BE stands for Big-Endian 76 public: 77 typedef std::string string; 78 79 // The maximum positive value represented by a SignedIntegerType. 80 static const SignedIntegerType kMaxVal; 81 82 // Returns the maximum number of bytes needed to store a varint 83 // representation of a <SignedIntegerType> value. 84 static const int kMaxBytes = VarintMaxBytes<SignedIntegerType>::kMaxBytes; 85 86 // Attempts to parse a big-endian varint from a prefix of the bytes 87 // in [ptr,limit-1] and convert it into a signed, non-negative 32-bit 88 // integer. Never reads a character at or beyond limit. 89 // If a parsed varint would exceed the maximum value of 90 // a <SignedIntegerType>, returns RESULT_ERROR and does not modify *ptr. 91 // If parsing a varint at *ptr (without exceeding the capacity of 92 // a <SignedIntegerType>) would require reading past limit, 93 // returns RESULT_END_OF_DATA and does not modify *ptr. 94 // If limit == NULL, returns RESULT_ERROR. 95 // If limit < *ptr, returns RESULT_END_OF_DATA. 96 static SignedIntegerType Parse(const char* limit, const char** ptr); 97 98 // Returns the encoding length of the specified value. 99 static int Length(SignedIntegerType v); 100 101 // Encodes "v" into "ptr" (which points to a buffer of length sufficient 102 // to hold "v")and returns the length of the encoding. 103 // The value of v must not be negative. 104 static int Encode(SignedIntegerType v, char* ptr); 105 106 // Appends the varint representation of "value" to "*s". 107 // The value of v must not be negative. 108 static void AppendToString(SignedIntegerType value, string* s); 109 110 // Appends the varint representation of "value" to output_string. 111 // The value of v must not be negative. 112 static void AppendToOutputString(SignedIntegerType value, 113 OutputStringInterface* output_string); 114 115 private: 116 // Encodes "v" into the LAST few bytes of varint_buf (which is a char array 117 // of size kMaxBytes) and returns the length of the encoding. 118 // The result will be stored in buf[(kMaxBytes - length) : (kMaxBytes - 1)], 119 // rather than in buf[0 : length]. 120 // The value of v must not be negative. 121 static int EncodeInternal(SignedIntegerType v, char* varint_buf); 122 123 // These are private to avoid constructing any objects of this type 124 VarintBE(); 125 VarintBE(const VarintBE&); // NOLINT 126 void operator=(const VarintBE&); 127 }; 128 129 } // namespace open_vcdiff 130 131 #endif // OPEN_VCDIFF_VARINT_BIGENDIAN_H_ 132