Home | History | Annotate | Download | only in src
      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 #include <config.h>
     17 #include "varint_bigendian.h"
     18 #include <stdint.h>  // int32_t, int64_t
     19 #include <string.h>  // memcpy
     20 #include <string>
     21 #include "logging.h"
     22 #include "google/output_string.h"
     23 
     24 namespace open_vcdiff {
     25 
     26 template<> const int32_t VarintBE<int32_t>::kMaxVal = 0x7FFFFFFF;
     27 template<> const int64_t VarintBE<int64_t>::kMaxVal = 0x7FFFFFFFFFFFFFFFULL;
     28 
     29 // Reads a variable-length integer from **varint_ptr
     30 // and returns it in a fixed-length representation.  Increments
     31 // *varint_ptr by the number of bytes read.  Will not read
     32 // past limit.  Returns RESULT_ERROR if the value parsed
     33 // does not fit in a non-negative signed integer, or if limit is NULL.
     34 // Returns RESULT_END_OF_DATA if address_stream_end is reached
     35 // before the whole integer can be decoded.
     36 //
     37 template <typename SignedIntegerType>
     38 SignedIntegerType VarintBE<SignedIntegerType>::Parse(const char* limit,
     39                                                      const char** varint_ptr) {
     40   if (!limit) {
     41     return RESULT_ERROR;
     42   }
     43   SignedIntegerType result = 0;
     44   for (const char* parse_ptr = *varint_ptr; parse_ptr < limit; ++parse_ptr) {
     45     result += *parse_ptr & 0x7F;
     46     if (!(*parse_ptr & 0x80)) {
     47       *varint_ptr = parse_ptr + 1;
     48       return result;
     49     }
     50     if (result > (kMaxVal >> 7)) {
     51       // Shifting result by 7 bits would produce a number too large
     52       // to be stored in a non-negative SignedIntegerType (an overflow.)
     53       return RESULT_ERROR;
     54     }
     55     result = result << 7;
     56   }
     57   return RESULT_END_OF_DATA;
     58 }
     59 
     60 template <typename SignedIntegerType>
     61 int VarintBE<SignedIntegerType>::EncodeInternal(SignedIntegerType v,
     62                                                 char* varint_buf) {
     63   if (v < 0) {
     64     LOG(DFATAL) << "Negative value " << v
     65                 << " passed to VarintBE::EncodeInternal,"
     66                    " which requires non-negative argument" << LOG_ENDL;
     67     return 0;
     68   }
     69   int length = 1;
     70   char* buf_ptr = &varint_buf[kMaxBytes - 1];
     71   *buf_ptr = static_cast<char>(v & 0x7F);
     72   --buf_ptr;
     73   v >>= 7;
     74   while (v) {
     75     *buf_ptr = static_cast<char>((v & 0x7F) | 0x80);  // add continuation bit
     76     --buf_ptr;
     77     ++length;
     78     v >>= 7;
     79   }
     80   return length;
     81 }
     82 
     83 template <typename SignedIntegerType>
     84 int VarintBE<SignedIntegerType>::Encode(SignedIntegerType v, char* ptr) {
     85   char varint_buf[kMaxBytes];
     86   const int length = EncodeInternal(v, varint_buf);
     87   memcpy(ptr, &varint_buf[kMaxBytes - length], length);
     88   return length;
     89 }
     90 
     91 template <typename SignedIntegerType>
     92 void VarintBE<SignedIntegerType>::AppendToString(SignedIntegerType value,
     93                                                  string* s) {
     94   char varint_buf[kMaxBytes];
     95   const int length = EncodeInternal(value, varint_buf);
     96   s->append(&varint_buf[kMaxBytes - length], length);
     97 }
     98 
     99 template <typename SignedIntegerType>
    100 void VarintBE<SignedIntegerType>::AppendToOutputString(
    101     SignedIntegerType value,
    102     OutputStringInterface* output_string) {
    103   char varint_buf[kMaxBytes];
    104   const int length = EncodeInternal(value, varint_buf);
    105   output_string->append(&varint_buf[kMaxBytes - length], length);
    106 }
    107 
    108 // Returns the encoding length of the specified value.
    109 template <typename SignedIntegerType>
    110 int VarintBE<SignedIntegerType>::Length(SignedIntegerType v) {
    111   if (v < 0) {
    112     LOG(DFATAL) << "Negative value " << v
    113                 << " passed to VarintBE::Length,"
    114                    " which requires non-negative argument" << LOG_ENDL;
    115     return 0;
    116   }
    117   int length = 0;
    118   do {
    119     v >>= 7;
    120     ++length;
    121   } while (v);
    122   return length;
    123 }
    124 
    125 template class VarintBE<int32_t>;
    126 template class VarintBE<int64_t>;
    127 
    128 }  // namespace open_vcdiff
    129