1311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// Copyright 2008 Google Inc. 2311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// Author: Lincoln Smith 3311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// 4311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// Licensed under the Apache License, Version 2.0 (the "License"); 5311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// you may not use this file except in compliance with the License. 6311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// You may obtain a copy of the License at 7311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// 8311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// http://www.apache.org/licenses/LICENSE-2.0 9311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// 10311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// Unless required by applicable law or agreed to in writing, software 11311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// distributed under the License is distributed on an "AS IS" BASIS, 12311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// See the License for the specific language governing permissions and 14311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// limitations under the License. 15311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff 16311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff#ifndef OPEN_VCDIFF_VARINT_BIGENDIAN_H_ 17311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff#define OPEN_VCDIFF_VARINT_BIGENDIAN_H_ 18311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff 19311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// Functions for manipulating variable-length integers as described in 20311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// RFC 3284, section 2. (See http://www.ietf.org/rfc/rfc3284.txt) 21311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// This is the same format used by the Sfio library 22311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// and by the public-domain Sqlite package. 23311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// 24311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// The implementation found in this file contains buffer bounds checks 25311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// (not available in sqlite) and its goal is to improve speed 26311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// by using as few test-and-branch instructions as possible. 27311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// 28311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// The Sqlite format has the refinement that, if a 64-bit value is expected, 29311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// the ninth byte of the varint does not have a continuation bit, but instead 30311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// encodes 8 bits of information. This allows 64 bits to be encoded compactly 31311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// in nine bytes. However, that refinement does not appear in the format 32311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// description in RFC 3284, and so it is not used here. In any case, 33311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// this header file deals only with *signed* integer types, and so a 34311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// "64-bit" integer is allowed to have only 63 significant bits; an additional 35311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// 64th bit would indicate a negative value and therefore an error. 36311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// 37311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff 38311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff#include <config.h> 39311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff#include <stdint.h> // int32_t, int64_t 40311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff#include <string> 41311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff#include "vcdiff_defs.h" // RESULT_ERROR 42311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff 43311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiffnamespace open_vcdiff { 44311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff 45311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiffclass OutputStringInterface; 46311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff 47311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// This helper class is needed in order to ensure that 48311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// VarintBE<SignedIntegerType>::kMaxBytes is treated 49311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// as a compile-time constant when it is used as the size 50311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// of a static array. 51311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdifftemplate <typename SignedIntegerType> class VarintMaxBytes; 52311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff 53311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// 31 bits of data / 7 bits per byte <= 5 bytes 54311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdifftemplate<> class VarintMaxBytes<int32_t> { 55311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff public: 56311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff static const int kMaxBytes = 5; 57311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff}; 58311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff 59311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// 63 bits of data / 7 bits per byte == 9 bytes 60311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdifftemplate<> class VarintMaxBytes<int64_t> { 61311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff public: 62311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff static const int kMaxBytes = 9; 63311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff}; 64311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff 65311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// Objects of type VarintBE should not be instantiated. The class is a 66311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// container for big-endian constant values and functions used to parse 67311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// and write a particular signed integer type. 68311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// Example: to parse a 32-bit integer value stored as a big-endian varint, use 69311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// int32_t value = VarintBE<int32_t>::Parse(&ptr, limit); 70311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// Only 32-bit and 64-bit signed integers (int32_t and int64_t) are supported. 71311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// Using a different type as the template argument will likely result 72311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// in a link-time error for an undefined Parse() or Append() function. 73311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff// 74311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdifftemplate <typename SignedIntegerType> 75311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiffclass VarintBE { // BE stands for Big-Endian 76311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff public: 7728db8079f707ebdf43ce62cdfd96eb39c8f889e0openvcdiff typedef std::string string; 7828db8079f707ebdf43ce62cdfd96eb39c8f889e0openvcdiff 79311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff // The maximum positive value represented by a SignedIntegerType. 80311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff static const SignedIntegerType kMaxVal; 81311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff 82311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff // Returns the maximum number of bytes needed to store a varint 83311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff // representation of a <SignedIntegerType> value. 84311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff static const int kMaxBytes = VarintMaxBytes<SignedIntegerType>::kMaxBytes; 85311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff 86311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff // Attempts to parse a big-endian varint from a prefix of the bytes 87311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff // in [ptr,limit-1] and convert it into a signed, non-negative 32-bit 88f1dd933c4e47a65889b4bba2a5f58b12aac53383openvcdiff@gmail.com // integer. Never reads a character at or beyond limit. 89311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff // If a parsed varint would exceed the maximum value of 90311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff // a <SignedIntegerType>, returns RESULT_ERROR and does not modify *ptr. 91311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff // If parsing a varint at *ptr (without exceeding the capacity of 92311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff // a <SignedIntegerType>) would require reading past limit, 93311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff // returns RESULT_END_OF_DATA and does not modify *ptr. 94f1dd933c4e47a65889b4bba2a5f58b12aac53383openvcdiff@gmail.com // If limit == NULL, returns RESULT_ERROR. 95f1dd933c4e47a65889b4bba2a5f58b12aac53383openvcdiff@gmail.com // If limit < *ptr, returns RESULT_END_OF_DATA. 96311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff static SignedIntegerType Parse(const char* limit, const char** ptr); 97311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff 98311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff // Returns the encoding length of the specified value. 99311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff static int Length(SignedIntegerType v); 100311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff 101311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff // Encodes "v" into "ptr" (which points to a buffer of length sufficient 102311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff // to hold "v")and returns the length of the encoding. 103311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff // The value of v must not be negative. 104311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff static int Encode(SignedIntegerType v, char* ptr); 105311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff 106311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff // Appends the varint representation of "value" to "*s". 107311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff // The value of v must not be negative. 108311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff static void AppendToString(SignedIntegerType value, string* s); 109311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff 110311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff // Appends the varint representation of "value" to output_string. 111311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff // The value of v must not be negative. 112311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff static void AppendToOutputString(SignedIntegerType value, 113311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff OutputStringInterface* output_string); 114311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff 115311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff private: 116311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff // Encodes "v" into the LAST few bytes of varint_buf (which is a char array 117311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff // of size kMaxBytes) and returns the length of the encoding. 118311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff // The result will be stored in buf[(kMaxBytes - length) : (kMaxBytes - 1)], 119311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff // rather than in buf[0 : length]. 120311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff // The value of v must not be negative. 121311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff static int EncodeInternal(SignedIntegerType v, char* varint_buf); 122311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff 123311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff // These are private to avoid constructing any objects of this type 124311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff VarintBE(); 125311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff VarintBE(const VarintBE&); // NOLINT 126311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff void operator=(const VarintBE&); 127311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff}; 128311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff 129311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff} // namespace open_vcdiff 130311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff 131311c71486f5f6074e5ba62a7f4c5397c8700b868openvcdiff#endif // OPEN_VCDIFF_VARINT_BIGENDIAN_H_ 132