1  // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
  2  // Use of this source code is governed by a BSD-style license that can be
  3  // found in the LICENSE file. See the AUTHORS file for names of contributors.
  4  
  5  #include "util/coding.h"
  6  
  7  namespace leveldb {
  8  
  9  void PutFixed32(std::string* dst, uint32_t value) {
 10    char buf[sizeof(value)];
 11    EncodeFixed32(buf, value);
 12    dst->append(buf, sizeof(buf));
 13  }
 14  
 15  void PutFixed64(std::string* dst, uint64_t value) {
 16    char buf[sizeof(value)];
 17    EncodeFixed64(buf, value);
 18    dst->append(buf, sizeof(buf));
 19  }
 20  
 21  char* EncodeVarint32(char* dst, uint32_t v) {
 22    // Operate on characters as unsigneds
 23    uint8_t* ptr = reinterpret_cast<uint8_t*>(dst);
 24    static const int B = 128;
 25    if (v < (1 << 7)) {
 26      *(ptr++) = v;
 27    } else if (v < (1 << 14)) {
 28      *(ptr++) = v | B;
 29      *(ptr++) = v >> 7;
 30    } else if (v < (1 << 21)) {
 31      *(ptr++) = v | B;
 32      *(ptr++) = (v >> 7) | B;
 33      *(ptr++) = v >> 14;
 34    } else if (v < (1 << 28)) {
 35      *(ptr++) = v | B;
 36      *(ptr++) = (v >> 7) | B;
 37      *(ptr++) = (v >> 14) | B;
 38      *(ptr++) = v >> 21;
 39    } else {
 40      *(ptr++) = v | B;
 41      *(ptr++) = (v >> 7) | B;
 42      *(ptr++) = (v >> 14) | B;
 43      *(ptr++) = (v >> 21) | B;
 44      *(ptr++) = v >> 28;
 45    }
 46    return reinterpret_cast<char*>(ptr);
 47  }
 48  
 49  void PutVarint32(std::string* dst, uint32_t v) {
 50    char buf[5];
 51    char* ptr = EncodeVarint32(buf, v);
 52    dst->append(buf, ptr - buf);
 53  }
 54  
 55  char* EncodeVarint64(char* dst, uint64_t v) {
 56    static const int B = 128;
 57    uint8_t* ptr = reinterpret_cast<uint8_t*>(dst);
 58    while (v >= B) {
 59      *(ptr++) = v | B;
 60      v >>= 7;
 61    }
 62    *(ptr++) = static_cast<uint8_t>(v);
 63    return reinterpret_cast<char*>(ptr);
 64  }
 65  
 66  void PutVarint64(std::string* dst, uint64_t v) {
 67    char buf[10];
 68    char* ptr = EncodeVarint64(buf, v);
 69    dst->append(buf, ptr - buf);
 70  }
 71  
 72  void PutLengthPrefixedSlice(std::string* dst, const Slice& value) {
 73    PutVarint32(dst, value.size());
 74    dst->append(value.data(), value.size());
 75  }
 76  
 77  int VarintLength(uint64_t v) {
 78    int len = 1;
 79    while (v >= 128) {
 80      v >>= 7;
 81      len++;
 82    }
 83    return len;
 84  }
 85  
 86  const char* GetVarint32PtrFallback(const char* p, const char* limit,
 87                                     uint32_t* value) {
 88    uint32_t result = 0;
 89    for (uint32_t shift = 0; shift <= 28 && p < limit; shift += 7) {
 90      uint32_t byte = *(reinterpret_cast<const uint8_t*>(p));
 91      p++;
 92      if (byte & 128) {
 93        // More bytes are present
 94        result |= ((byte & 127) << shift);
 95      } else {
 96        result |= (byte << shift);
 97        *value = result;
 98        return reinterpret_cast<const char*>(p);
 99      }
100    }
101    return nullptr;
102  }
103  
104  bool GetVarint32(Slice* input, uint32_t* value) {
105    const char* p = input->data();
106    const char* limit = p + input->size();
107    const char* q = GetVarint32Ptr(p, limit, value);
108    if (q == nullptr) {
109      return false;
110    } else {
111      *input = Slice(q, limit - q);
112      return true;
113    }
114  }
115  
116  const char* GetVarint64Ptr(const char* p, const char* limit, uint64_t* value) {
117    uint64_t result = 0;
118    for (uint32_t shift = 0; shift <= 63 && p < limit; shift += 7) {
119      uint64_t byte = *(reinterpret_cast<const uint8_t*>(p));
120      p++;
121      if (byte & 128) {
122        // More bytes are present
123        result |= ((byte & 127) << shift);
124      } else {
125        result |= (byte << shift);
126        *value = result;
127        return reinterpret_cast<const char*>(p);
128      }
129    }
130    return nullptr;
131  }
132  
133  bool GetVarint64(Slice* input, uint64_t* value) {
134    const char* p = input->data();
135    const char* limit = p + input->size();
136    const char* q = GetVarint64Ptr(p, limit, value);
137    if (q == nullptr) {
138      return false;
139    } else {
140      *input = Slice(q, limit - q);
141      return true;
142    }
143  }
144  
145  const char* GetLengthPrefixedSlice(const char* p, const char* limit,
146                                     Slice* result) {
147    uint32_t len;
148    p = GetVarint32Ptr(p, limit, &len);
149    if (p == nullptr) return nullptr;
150    if (p + len > limit) return nullptr;
151    *result = Slice(p, len);
152    return p + len;
153  }
154  
155  bool GetLengthPrefixedSlice(Slice* input, Slice* result) {
156    uint32_t len;
157    if (GetVarint32(input, &len) && input->size() >= len) {
158      *result = Slice(input->data(), len);
159      input->remove_prefix(len);
160      return true;
161    } else {
162      return false;
163    }
164  }
165  
166  }  // namespace leveldb