ceph/src/rocksdb/util/coding.h

   1 //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
   2 //  This source code is licensed under the BSD-style license found in the
   3 //  LICENSE file in the root directory of this source tree. An additional grant
   4 //  of patent rights can be found in the PATENTS file in the same directory.
   5 //
   6 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
   7 // Use of this source code is governed by a BSD-style license that can be
   8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
   9 //
  10 // Endian-neutral encoding:
  11 // * Fixed-length numbers are encoded with least-significant byte first
  12 // * In addition we support variable length "varint" encoding
  13 // * Strings are encoded prefixed by their length in varint format
  14
  15 #pragma once
  16 #include <algorithm>
  17 #include <stdint.h>
  18 #include <string.h>
  19 #include <string>
  20
  21 #include "rocksdb/write_batch.h"
  22 #include "port/port.h"
  23
  24 // Some processors does not allow unaligned access to memory
  25 #if defined(__sparc)
  26   #define PLATFORM_UNALIGNED_ACCESS_NOT_ALLOWED
  27 #endif
  28
  29 namespace rocksdb {
  30
  31 // The maximum length of a varint in bytes for 64-bit.
  32 const unsigned int kMaxVarint64Length = 10;
  33
  34 // Standard Put... routines append to a string
  35 extern void PutFixed32(std::string* dst, uint32_t value);
  36 extern void PutFixed64(std::string* dst, uint64_t value);
  37 extern void PutVarint32(std::string* dst, uint32_t value);
  38 extern void PutVarint32Varint32(std::string* dst, uint32_t value1,
  39                                 uint32_t value2);
  40 extern void PutVarint32Varint32Varint32(std::string* dst, uint32_t value1,
  41                                         uint32_t value2, uint32_t value3);
  42 extern void PutVarint64(std::string* dst, uint64_t value);
  43 extern void PutVarint64Varint64(std::string* dst, uint64_t value1,
  44                                 uint64_t value2);
  45 extern void PutVarint32Varint64(std::string* dst, uint32_t value1,
  46                                 uint64_t value2);
  47 extern void PutVarint32Varint32Varint64(std::string* dst, uint32_t value1,
  48                                         uint32_t value2, uint64_t value3);
  49 extern void PutLengthPrefixedSlice(std::string* dst, const Slice& value);
  50 extern void PutLengthPrefixedSliceParts(std::string* dst,
  51                                         const SliceParts& slice_parts);
  52
  53 // Standard Get... routines parse a value from the beginning of a Slice
  54 // and advance the slice past the parsed value.
  55 extern bool GetFixed64(Slice* input, uint64_t* value);
  56 extern bool GetFixed32(Slice* input, uint32_t* value);
  57 extern bool GetVarint32(Slice* input, uint32_t* value);
  58 extern bool GetVarint64(Slice* input, uint64_t* value);
  59 extern bool GetLengthPrefixedSlice(Slice* input, Slice* result);
  60 // This function assumes data is well-formed.
  61 extern Slice GetLengthPrefixedSlice(const char* data);
  62
  63 extern Slice GetSliceUntil(Slice* slice, char delimiter);
  64
  65 // Pointer-based variants of GetVarint...  These either store a value
  66 // in *v and return a pointer just past the parsed value, or return
  67 // nullptr on error.  These routines only look at bytes in the range
  68 // [p..limit-1]
  69 extern const char* GetVarint32Ptr(const char* p,const char* limit, uint32_t* v);
  70 extern const char* GetVarint64Ptr(const char* p,const char* limit, uint64_t* v);
  71
  72 // Returns the length of the varint32 or varint64 encoding of "v"
  73 extern int VarintLength(uint64_t v);
  74
  75 // Lower-level versions of Put... that write directly into a character buffer
  76 // REQUIRES: dst has enough space for the value being written
  77 extern void EncodeFixed32(char* dst, uint32_t value);
  78 extern void EncodeFixed64(char* dst, uint64_t value);
  79
  80 // Lower-level versions of Put... that write directly into a character buffer
  81 // and return a pointer just past the last byte written.
  82 // REQUIRES: dst has enough space for the value being written
  83 extern char* EncodeVarint32(char* dst, uint32_t value);
  84 extern char* EncodeVarint64(char* dst, uint64_t value);
  85
  86 // Lower-level versions of Get... that read directly from a character buffer
  87 // without any bounds checking.
  88
  89 inline uint32_t DecodeFixed32(const char* ptr) {
  90   if (port::kLittleEndian) {
  91     // Load the raw bytes
  92     uint32_t result;
  93     memcpy(&result, ptr, sizeof(result));  // gcc optimizes this to a plain load
  94     return result;
  95   } else {
  96     return ((static_cast<uint32_t>(static_cast<unsigned char>(ptr[0])))
  97         | (static_cast<uint32_t>(static_cast<unsigned char>(ptr[1])) << 8)
  98         | (static_cast<uint32_t>(static_cast<unsigned char>(ptr[2])) << 16)
  99         | (static_cast<uint32_t>(static_cast<unsigned char>(ptr[3])) << 24));
 100   }
 101 }
 102
 103 inline uint64_t DecodeFixed64(const char* ptr) {
 104   if (port::kLittleEndian) {
 105     // Load the raw bytes
 106     uint64_t result;
 107     memcpy(&result, ptr, sizeof(result));  // gcc optimizes this to a plain load
 108     return result;
 109   } else {
 110     uint64_t lo = DecodeFixed32(ptr);
 111     uint64_t hi = DecodeFixed32(ptr + 4);
 112     return (hi << 32) | lo;
 113   }
 114 }
 115
 116 // Internal routine for use by fallback path of GetVarint32Ptr
 117 extern const char* GetVarint32PtrFallback(const char* p,
 118                                           const char* limit,
 119                                           uint32_t* value);
 120 inline const char* GetVarint32Ptr(const char* p,
 121                                   const char* limit,
 122                                   uint32_t* value) {
 123   if (p < limit) {
 124     uint32_t result = *(reinterpret_cast<const unsigned char*>(p));
 125     if ((result & 128) == 0) {
 126       *value = result;
 127       return p + 1;
 128     }
 129   }
 130   return GetVarint32PtrFallback(p, limit, value);
 131 }
 132
 133 // -- Implementation of the functions declared above
 134 inline void EncodeFixed32(char* buf, uint32_t value) {
 135   if (port::kLittleEndian) {
 136     memcpy(buf, &value, sizeof(value));
 137   } else {
 138     buf[0] = value & 0xff;
 139     buf[1] = (value >> 8) & 0xff;
 140     buf[2] = (value >> 16) & 0xff;
 141     buf[3] = (value >> 24) & 0xff;
 142   }
 143 }
 144
 145 inline void EncodeFixed64(char* buf, uint64_t value) {
 146   if (port::kLittleEndian) {
 147     memcpy(buf, &value, sizeof(value));
 148   } else {
 149     buf[0] = value & 0xff;
 150     buf[1] = (value >> 8) & 0xff;
 151     buf[2] = (value >> 16) & 0xff;
 152     buf[3] = (value >> 24) & 0xff;
 153     buf[4] = (value >> 32) & 0xff;
 154     buf[5] = (value >> 40) & 0xff;
 155     buf[6] = (value >> 48) & 0xff;
 156     buf[7] = (value >> 56) & 0xff;
 157   }
 158 }
 159
 160 // Pull the last 8 bits and cast it to a character
 161 inline void PutFixed32(std::string* dst, uint32_t value) {
 162   if (port::kLittleEndian) {
 163     dst->append(const_cast<const char*>(reinterpret_cast<char*>(&value)),
 164       sizeof(value));
 165   } else {
 166     char buf[sizeof(value)];
 167     EncodeFixed32(buf, value);
 168     dst->append(buf, sizeof(buf));
 169   }
 170 }
 171
 172 inline void PutFixed64(std::string* dst, uint64_t value) {
 173   if (port::kLittleEndian) {
 174     dst->append(const_cast<const char*>(reinterpret_cast<char*>(&value)),
 175       sizeof(value));
 176   } else {
 177     char buf[sizeof(value)];
 178     EncodeFixed64(buf, value);
 179     dst->append(buf, sizeof(buf));
 180   }
 181 }
 182
 183 inline void PutVarint32(std::string* dst, uint32_t v) {
 184   char buf[5];
 185   char* ptr = EncodeVarint32(buf, v);
 186   dst->append(buf, static_cast<size_t>(ptr - buf));
 187 }
 188
 189 inline void PutVarint32Varint32(std::string* dst, uint32_t v1, uint32_t v2) {
 190   char buf[10];
 191   char* ptr = EncodeVarint32(buf, v1);
 192   ptr = EncodeVarint32(ptr, v2);
 193   dst->append(buf, static_cast<size_t>(ptr - buf));
 194 }
 195
 196 inline void PutVarint32Varint32Varint32(std::string* dst, uint32_t v1,
 197                                         uint32_t v2, uint32_t v3) {
 198   char buf[15];
 199   char* ptr = EncodeVarint32(buf, v1);
 200   ptr = EncodeVarint32(ptr, v2);
 201   ptr = EncodeVarint32(ptr, v3);
 202   dst->append(buf, static_cast<size_t>(ptr - buf));
 203 }
 204
 205 inline char* EncodeVarint64(char* dst, uint64_t v) {
 206   static const unsigned int B = 128;
 207   unsigned char* ptr = reinterpret_cast<unsigned char*>(dst);
 208   while (v >= B) {
 209     *(ptr++) = (v & (B - 1)) | B;
 210     v >>= 7;
 211   }
 212   *(ptr++) = static_cast<unsigned char>(v);
 213   return reinterpret_cast<char*>(ptr);
 214 }
 215
 216 inline void PutVarint64(std::string* dst, uint64_t v) {
 217   char buf[10];
 218   char* ptr = EncodeVarint64(buf, v);
 219   dst->append(buf, static_cast<size_t>(ptr - buf));
 220 }
 221
 222 inline void PutVarint64Varint64(std::string* dst, uint64_t v1, uint64_t v2) {
 223   char buf[20];
 224   char* ptr = EncodeVarint64(buf, v1);
 225   ptr = EncodeVarint64(ptr, v2);
 226   dst->append(buf, static_cast<size_t>(ptr - buf));
 227 }
 228
 229 inline void PutVarint32Varint64(std::string* dst, uint32_t v1, uint64_t v2) {
 230   char buf[15];
 231   char* ptr = EncodeVarint32(buf, v1);
 232   ptr = EncodeVarint64(ptr, v2);
 233   dst->append(buf, static_cast<size_t>(ptr - buf));
 234 }
 235
 236 inline void PutVarint32Varint32Varint64(std::string* dst, uint32_t v1,
 237                                         uint32_t v2, uint64_t v3) {
 238   char buf[20];
 239   char* ptr = EncodeVarint32(buf, v1);
 240   ptr = EncodeVarint32(ptr, v2);
 241   ptr = EncodeVarint64(ptr, v3);
 242   dst->append(buf, static_cast<size_t>(ptr - buf));
 243 }
 244
 245 inline void PutLengthPrefixedSlice(std::string* dst, const Slice& value) {
 246   PutVarint32(dst, static_cast<uint32_t>(value.size()));
 247   dst->append(value.data(), value.size());
 248 }
 249
 250 inline void PutLengthPrefixedSliceParts(std::string* dst,
 251                                         const SliceParts& slice_parts) {
 252   size_t total_bytes = 0;
 253   for (int i = 0; i < slice_parts.num_parts; ++i) {
 254     total_bytes += slice_parts.parts[i].size();
 255   }
 256   PutVarint32(dst, static_cast<uint32_t>(total_bytes));
 257   for (int i = 0; i < slice_parts.num_parts; ++i) {
 258     dst->append(slice_parts.parts[i].data(), slice_parts.parts[i].size());
 259   }
 260 }
 261
 262 inline int VarintLength(uint64_t v) {
 263   int len = 1;
 264   while (v >= 128) {
 265     v >>= 7;
 266     len++;
 267   }
 268   return len;
 269 }
 270
 271 inline bool GetFixed64(Slice* input, uint64_t* value) {
 272   if (input->size() < sizeof(uint64_t)) {
 273     return false;
 274   }
 275   *value = DecodeFixed64(input->data());
 276   input->remove_prefix(sizeof(uint64_t));
 277   return true;
 278 }
 279
 280 inline bool GetFixed32(Slice* input, uint32_t* value) {
 281   if (input->size() < sizeof(uint32_t)) {
 282     return false;
 283   }
 284   *value = DecodeFixed32(input->data());
 285   input->remove_prefix(sizeof(uint32_t));
 286   return true;
 287 }
 288
 289 inline bool GetVarint32(Slice* input, uint32_t* value) {
 290   const char* p = input->data();
 291   const char* limit = p + input->size();
 292   const char* q = GetVarint32Ptr(p, limit, value);
 293   if (q == nullptr) {
 294     return false;
 295   } else {
 296     *input = Slice(q, static_cast<size_t>(limit - q));
 297     return true;
 298   }
 299 }
 300
 301 inline bool GetVarint64(Slice* input, uint64_t* value) {
 302   const char* p = input->data();
 303   const char* limit = p + input->size();
 304   const char* q = GetVarint64Ptr(p, limit, value);
 305   if (q == nullptr) {
 306     return false;
 307   } else {
 308     *input = Slice(q, static_cast<size_t>(limit - q));
 309     return true;
 310   }
 311 }
 312
 313 // Provide an interface for platform independent endianness transformation
 314 inline uint64_t EndianTransform(uint64_t input, size_t size) {
 315   char* pos = reinterpret_cast<char*>(&input);
 316   uint64_t ret_val = 0;
 317   for (size_t i = 0; i < size; ++i) {
 318     ret_val |= (static_cast<uint64_t>(static_cast<unsigned char>(pos[i]))
 319                 << ((size - i - 1) << 3));
 320   }
 321   return ret_val;
 322 }
 323
 324 inline bool GetLengthPrefixedSlice(Slice* input, Slice* result) {
 325   uint32_t len = 0;
 326   if (GetVarint32(input, &len) && input->size() >= len) {
 327     *result = Slice(input->data(), len);
 328     input->remove_prefix(len);
 329     return true;
 330   } else {
 331     return false;
 332   }
 333 }
 334
 335 inline Slice GetLengthPrefixedSlice(const char* data) {
 336   uint32_t len = 0;
 337   // +5: we assume "data" is not corrupted
 338   // unsigned char is 7 bits, uint32_t is 32 bits, need 5 unsigned char
 339   auto p = GetVarint32Ptr(data, data + 5 /* limit */, &len);
 340   return Slice(p, len);
 341 }
 342
 343 inline Slice GetSliceUntil(Slice* slice, char delimiter) {
 344   uint32_t len = 0;
 345   for (len = 0; len < slice->size() && slice->data()[len] != delimiter; ++len) {
 346     // nothing
 347   }
 348
 349   Slice ret(slice->data(), len);
 350   slice->remove_prefix(len + ((len < slice->size()) ? 1 : 0));
 351   return ret;
 352 }
 353
 354 template<class T>
 355 inline void PutUnaligned(T *memory, const T &value) {
 356 #if defined(PLATFORM_UNALIGNED_ACCESS_NOT_ALLOWED)
 357   char *nonAlignedMemory = reinterpret_cast<char*>(memory);
 358   memcpy(nonAlignedMemory, reinterpret_cast<const char*>(&value), sizeof(T));
 359 #else
 360   *memory = value;
 361 #endif
 362 }
 363
 364 template<class T>
 365 inline void GetUnaligned(const T *memory, T *value) {
 366 #if defined(PLATFORM_UNALIGNED_ACCESS_NOT_ALLOWED)
 367   char *nonAlignedMemory = reinterpret_cast<char*>(value);
 368   memcpy(nonAlignedMemory, reinterpret_cast<const char*>(memory), sizeof(T));
 369 #else
 370   *value = *memory;
 371 #endif
 372 }
 373
 374 }  // namespace rocksdb