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
43namespace open_vcdiff {
44
45class 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.
51template <typename SignedIntegerType> class VarintMaxBytes;
52
53// 31 bits of data / 7 bits per byte <= 5 bytes
54template<> 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
60template<> 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//
74template <typename SignedIntegerType>
75class 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