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  // Endian-neutral encoding:
  6  // * Fixed-length numbers are encoded with least-significant byte first
  7  // * In addition we support variable length "varint" encoding
  8  // * Strings are encoded prefixed by their length in varint format
  9  
 10  #ifndef STORAGE_LEVELDB_UTIL_CODING_H_
 11  #define STORAGE_LEVELDB_UTIL_CODING_H_
 12  
 13  #include <cstdint>
 14  #include <cstring>
 15  #include <string>
 16  
 17  #include "leveldb/slice.h"
 18  #include "port/port.h"
 19  
 20  namespace leveldb {
 21  
 22  // Standard Put... routines append to a string
 23  void PutFixed32(std::string* dst, uint32_t value);
 24  void PutFixed64(std::string* dst, uint64_t value);
 25  void PutVarint32(std::string* dst, uint32_t value);
 26  void PutVarint64(std::string* dst, uint64_t value);
 27  void PutLengthPrefixedSlice(std::string* dst, const Slice& value);
 28  
 29  // Standard Get... routines parse a value from the beginning of a Slice
 30  // and advance the slice past the parsed value.
 31  bool GetVarint32(Slice* input, uint32_t* value);
 32  bool GetVarint64(Slice* input, uint64_t* value);
 33  bool GetLengthPrefixedSlice(Slice* input, Slice* result);
 34  
 35  // Pointer-based variants of GetVarint...  These either store a value
 36  // in *v and return a pointer just past the parsed value, or return
 37  // nullptr on error.  These routines only look at bytes in the range
 38  // [p..limit-1]
 39  const char* GetVarint32Ptr(const char* p, const char* limit, uint32_t* v);
 40  const char* GetVarint64Ptr(const char* p, const char* limit, uint64_t* v);
 41  
 42  // Returns the length of the varint32 or varint64 encoding of "v"
 43  int VarintLength(uint64_t v);
 44  
 45  // Lower-level versions of Put... that write directly into a character buffer
 46  // and return a pointer just past the last byte written.
 47  // REQUIRES: dst has enough space for the value being written
 48  char* EncodeVarint32(char* dst, uint32_t value);
 49  char* EncodeVarint64(char* dst, uint64_t value);
 50  
 51  // Lower-level versions of Put... that write directly into a character buffer
 52  // REQUIRES: dst has enough space for the value being written
 53  
 54  inline void EncodeFixed32(char* dst, uint32_t value) {
 55    uint8_t* const buffer = reinterpret_cast<uint8_t*>(dst);
 56  
 57    // Recent clang and gcc optimize this to a single mov / str instruction.
 58    buffer[0] = static_cast<uint8_t>(value);
 59    buffer[1] = static_cast<uint8_t>(value >> 8);
 60    buffer[2] = static_cast<uint8_t>(value >> 16);
 61    buffer[3] = static_cast<uint8_t>(value >> 24);
 62  }
 63  
 64  inline void EncodeFixed64(char* dst, uint64_t value) {
 65    uint8_t* const buffer = reinterpret_cast<uint8_t*>(dst);
 66  
 67    // Recent clang and gcc optimize this to a single mov / str instruction.
 68    buffer[0] = static_cast<uint8_t>(value);
 69    buffer[1] = static_cast<uint8_t>(value >> 8);
 70    buffer[2] = static_cast<uint8_t>(value >> 16);
 71    buffer[3] = static_cast<uint8_t>(value >> 24);
 72    buffer[4] = static_cast<uint8_t>(value >> 32);
 73    buffer[5] = static_cast<uint8_t>(value >> 40);
 74    buffer[6] = static_cast<uint8_t>(value >> 48);
 75    buffer[7] = static_cast<uint8_t>(value >> 56);
 76  }
 77  
 78  // Lower-level versions of Get... that read directly from a character buffer
 79  // without any bounds checking.
 80  
 81  inline uint32_t DecodeFixed32(const char* ptr) {
 82    const uint8_t* const buffer = reinterpret_cast<const uint8_t*>(ptr);
 83  
 84    // Recent clang and gcc optimize this to a single mov / ldr instruction.
 85    return (static_cast<uint32_t>(buffer[0])) |
 86           (static_cast<uint32_t>(buffer[1]) << 8) |
 87           (static_cast<uint32_t>(buffer[2]) << 16) |
 88           (static_cast<uint32_t>(buffer[3]) << 24);
 89  }
 90  
 91  inline uint64_t DecodeFixed64(const char* ptr) {
 92    const uint8_t* const buffer = reinterpret_cast<const uint8_t*>(ptr);
 93  
 94    // Recent clang and gcc optimize this to a single mov / ldr instruction.
 95    return (static_cast<uint64_t>(buffer[0])) |
 96           (static_cast<uint64_t>(buffer[1]) << 8) |
 97           (static_cast<uint64_t>(buffer[2]) << 16) |
 98           (static_cast<uint64_t>(buffer[3]) << 24) |
 99           (static_cast<uint64_t>(buffer[4]) << 32) |
100           (static_cast<uint64_t>(buffer[5]) << 40) |
101           (static_cast<uint64_t>(buffer[6]) << 48) |
102           (static_cast<uint64_t>(buffer[7]) << 56);
103  }
104  
105  // Internal routine for use by fallback path of GetVarint32Ptr
106  const char* GetVarint32PtrFallback(const char* p, const char* limit,
107                                     uint32_t* value);
108  inline const char* GetVarint32Ptr(const char* p, const char* limit,
109                                    uint32_t* value) {
110    if (p < limit) {
111      uint32_t result = *(reinterpret_cast<const uint8_t*>(p));
112      if ((result & 128) == 0) {
113        *value = result;
114        return p + 1;
115      }
116    }
117    return GetVarint32PtrFallback(p, limit, value);
118  }
119  
120  }  // namespace leveldb
121  
122  #endif  // STORAGE_LEVELDB_UTIL_CODING_H_