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