ceph/src/rocksdb/util/coding.h

   1 //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
   2 //  This source code is licensed under both the GPLv2 (found in the
   3 //  COPYING file in the root directory) and Apache 2.0 License
   4 //  (found in the LICENSE.Apache file in the root 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 // Encoding independent of machine byte order:
  11 // * Fixed-length numbers are encoded with least-significant byte first
  12 //   (little endian, native order on Intel and others)
  13 // * In addition we support variable length "varint" encoding
  14 // * Strings are encoded prefixed by their length in varint format
  15 //
  16 // Some related functions are provided in coding_lean.h
  17
  18 #pragma once
  19 #include <algorithm>
  20 #include <string>
  21
  22 #include "port/port.h"
  23 #include "rocksdb/slice.h"
  24 #include "util/coding_lean.h"
  25
  26 // Some processors does not allow unaligned access to memory
  27 #if defined(__sparc)
  28   #define PLATFORM_UNALIGNED_ACCESS_NOT_ALLOWED
  29 #endif
  30
  31 namespace ROCKSDB_NAMESPACE {
  32
  33 // The maximum length of a varint in bytes for 64-bit.
  34 const unsigned int kMaxVarint64Length = 10;
  35
  36 // Standard Put... routines append to a string
  37 extern void PutFixed16(std::string* dst, uint16_t value);
  38 extern void PutFixed32(std::string* dst, uint32_t value);
  39 extern void PutFixed64(std::string* dst, uint64_t value);
  40 extern void PutVarint32(std::string* dst, uint32_t value);
  41 extern void PutVarint32Varint32(std::string* dst, uint32_t value1,
  42                                 uint32_t value2);
  43 extern void PutVarint32Varint32Varint32(std::string* dst, uint32_t value1,
  44                                         uint32_t value2, uint32_t value3);
  45 extern void PutVarint64(std::string* dst, uint64_t value);
  46 extern void PutVarint64Varint64(std::string* dst, uint64_t value1,
  47                                 uint64_t value2);
  48 extern void PutVarint32Varint64(std::string* dst, uint32_t value1,
  49                                 uint64_t value2);
  50 extern void PutVarint32Varint32Varint64(std::string* dst, uint32_t value1,
  51                                         uint32_t value2, uint64_t value3);
  52 extern void PutLengthPrefixedSlice(std::string* dst, const Slice& value);
  53 extern void PutLengthPrefixedSliceParts(std::string* dst,
  54                                         const SliceParts& slice_parts);
  55 extern void PutLengthPrefixedSlicePartsWithPadding(
  56     std::string* dst, const SliceParts& slice_parts, size_t pad_sz);
  57
  58 // Standard Get... routines parse a value from the beginning of a Slice
  59 // and advance the slice past the parsed value.
  60 extern bool GetFixed64(Slice* input, uint64_t* value);
  61 extern bool GetFixed32(Slice* input, uint32_t* value);
  62 extern bool GetFixed16(Slice* input, uint16_t* value);
  63 extern bool GetVarint32(Slice* input, uint32_t* value);
  64 extern bool GetVarint64(Slice* input, uint64_t* value);
  65 extern bool GetVarsignedint64(Slice* input, int64_t* value);
  66 extern bool GetLengthPrefixedSlice(Slice* input, Slice* result);
  67 // This function assumes data is well-formed.
  68 extern Slice GetLengthPrefixedSlice(const char* data);
  69
  70 extern Slice GetSliceUntil(Slice* slice, char delimiter);
  71
  72 // Borrowed from
  73 // https://github.com/facebook/fbthrift/blob/449a5f77f9f9bae72c9eb5e78093247eef185c04/thrift/lib/cpp/util/VarintUtils-inl.h#L202-L208
  74 constexpr inline uint64_t i64ToZigzag(const int64_t l) {
  75   return (static_cast<uint64_t>(l) << 1) ^ static_cast<uint64_t>(l >> 63);
  76 }
  77 inline int64_t zigzagToI64(uint64_t n) {
  78   return (n >> 1) ^ -static_cast<int64_t>(n & 1);
  79 }
  80
  81 // Pointer-based variants of GetVarint...  These either store a value
  82 // in *v and return a pointer just past the parsed value, or return
  83 // nullptr on error.  These routines only look at bytes in the range
  84 // [p..limit-1]
  85 extern const char* GetVarint32Ptr(const char* p,const char* limit, uint32_t* v);
  86 extern const char* GetVarint64Ptr(const char* p,const char* limit, uint64_t* v);
  87 inline const char* GetVarsignedint64Ptr(const char* p, const char* limit,
  88                                         int64_t* value) {
  89   uint64_t u = 0;
  90   const char* ret = GetVarint64Ptr(p, limit, &u);
  91   *value = zigzagToI64(u);
  92   return ret;
  93 }
  94
  95 // Returns the length of the varint32 or varint64 encoding of "v"
  96 extern int VarintLength(uint64_t v);
  97
  98 // Lower-level versions of Put... that write directly into a character buffer
  99 // and return a pointer just past the last byte written.
 100 // REQUIRES: dst has enough space for the value being written
 101 extern char* EncodeVarint32(char* dst, uint32_t value);
 102 extern char* EncodeVarint64(char* dst, uint64_t value);
 103
 104 // Internal routine for use by fallback path of GetVarint32Ptr
 105 extern const char* GetVarint32PtrFallback(const char* p,
 106                                           const char* limit,
 107                                           uint32_t* value);
 108 inline const char* GetVarint32Ptr(const char* p,
 109                                   const char* limit,
 110                                   uint32_t* value) {
 111   if (p < limit) {
 112     uint32_t result = *(reinterpret_cast<const unsigned char*>(p));
 113     if ((result & 128) == 0) {
 114       *value = result;
 115       return p + 1;
 116     }
 117   }
 118   return GetVarint32PtrFallback(p, limit, value);
 119 }
 120
 121 // Pull the last 8 bits and cast it to a character
 122 inline void PutFixed16(std::string* dst, uint16_t value) {
 123   if (port::kLittleEndian) {
 124     dst->append(const_cast<const char*>(reinterpret_cast<char*>(&value)),
 125                 sizeof(value));
 126   } else {
 127     char buf[sizeof(value)];
 128     EncodeFixed16(buf, value);
 129     dst->append(buf, sizeof(buf));
 130   }
 131 }
 132
 133 inline void PutFixed32(std::string* dst, uint32_t value) {
 134   if (port::kLittleEndian) {
 135     dst->append(const_cast<const char*>(reinterpret_cast<char*>(&value)),
 136       sizeof(value));
 137   } else {
 138     char buf[sizeof(value)];
 139     EncodeFixed32(buf, value);
 140     dst->append(buf, sizeof(buf));
 141   }
 142 }
 143
 144 inline void PutFixed64(std::string* dst, uint64_t value) {
 145   if (port::kLittleEndian) {
 146     dst->append(const_cast<const char*>(reinterpret_cast<char*>(&value)),
 147       sizeof(value));
 148   } else {
 149     char buf[sizeof(value)];
 150     EncodeFixed64(buf, value);
 151     dst->append(buf, sizeof(buf));
 152   }
 153 }
 154
 155 inline void PutVarint32(std::string* dst, uint32_t v) {
 156   char buf[5];
 157   char* ptr = EncodeVarint32(buf, v);
 158   dst->append(buf, static_cast<size_t>(ptr - buf));
 159 }
 160
 161 inline void PutVarint32Varint32(std::string* dst, uint32_t v1, uint32_t v2) {
 162   char buf[10];
 163   char* ptr = EncodeVarint32(buf, v1);
 164   ptr = EncodeVarint32(ptr, v2);
 165   dst->append(buf, static_cast<size_t>(ptr - buf));
 166 }
 167
 168 inline void PutVarint32Varint32Varint32(std::string* dst, uint32_t v1,
 169                                         uint32_t v2, uint32_t v3) {
 170   char buf[15];
 171   char* ptr = EncodeVarint32(buf, v1);
 172   ptr = EncodeVarint32(ptr, v2);
 173   ptr = EncodeVarint32(ptr, v3);
 174   dst->append(buf, static_cast<size_t>(ptr - buf));
 175 }
 176
 177 inline char* EncodeVarint64(char* dst, uint64_t v) {
 178   static const unsigned int B = 128;
 179   unsigned char* ptr = reinterpret_cast<unsigned char*>(dst);
 180   while (v >= B) {
 181     *(ptr++) = (v & (B - 1)) | B;
 182     v >>= 7;
 183   }
 184   *(ptr++) = static_cast<unsigned char>(v);
 185   return reinterpret_cast<char*>(ptr);
 186 }
 187
 188 inline void PutVarint64(std::string* dst, uint64_t v) {
 189   char buf[kMaxVarint64Length];
 190   char* ptr = EncodeVarint64(buf, v);
 191   dst->append(buf, static_cast<size_t>(ptr - buf));
 192 }
 193
 194 inline void PutVarsignedint64(std::string* dst, int64_t v) {
 195   char buf[kMaxVarint64Length];
 196   // Using Zigzag format to convert signed to unsigned
 197   char* ptr = EncodeVarint64(buf, i64ToZigzag(v));
 198   dst->append(buf, static_cast<size_t>(ptr - buf));
 199 }
 200
 201 inline void PutVarint64Varint64(std::string* dst, uint64_t v1, uint64_t v2) {
 202   char buf[20];
 203   char* ptr = EncodeVarint64(buf, v1);
 204   ptr = EncodeVarint64(ptr, v2);
 205   dst->append(buf, static_cast<size_t>(ptr - buf));
 206 }
 207
 208 inline void PutVarint32Varint64(std::string* dst, uint32_t v1, uint64_t v2) {
 209   char buf[15];
 210   char* ptr = EncodeVarint32(buf, v1);
 211   ptr = EncodeVarint64(ptr, v2);
 212   dst->append(buf, static_cast<size_t>(ptr - buf));
 213 }
 214
 215 inline void PutVarint32Varint32Varint64(std::string* dst, uint32_t v1,
 216                                         uint32_t v2, uint64_t v3) {
 217   char buf[20];
 218   char* ptr = EncodeVarint32(buf, v1);
 219   ptr = EncodeVarint32(ptr, v2);
 220   ptr = EncodeVarint64(ptr, v3);
 221   dst->append(buf, static_cast<size_t>(ptr - buf));
 222 }
 223
 224 inline void PutLengthPrefixedSlice(std::string* dst, const Slice& value) {
 225   PutVarint32(dst, static_cast<uint32_t>(value.size()));
 226   dst->append(value.data(), value.size());
 227 }
 228
 229 inline void PutLengthPrefixedSliceParts(std::string* dst, size_t total_bytes,
 230                                         const SliceParts& slice_parts) {
 231   for (int i = 0; i < slice_parts.num_parts; ++i) {
 232     total_bytes += slice_parts.parts[i].size();
 233   }
 234   PutVarint32(dst, static_cast<uint32_t>(total_bytes));
 235   for (int i = 0; i < slice_parts.num_parts; ++i) {
 236     dst->append(slice_parts.parts[i].data(), slice_parts.parts[i].size());
 237   }
 238 }
 239
 240 inline void PutLengthPrefixedSliceParts(std::string* dst,
 241                                         const SliceParts& slice_parts) {
 242   PutLengthPrefixedSliceParts(dst, /*total_bytes=*/0, slice_parts);
 243 }
 244
 245 inline void PutLengthPrefixedSlicePartsWithPadding(
 246     std::string* dst, const SliceParts& slice_parts, size_t pad_sz) {
 247   PutLengthPrefixedSliceParts(dst, /*total_bytes=*/pad_sz, slice_parts);
 248   dst->append(pad_sz, '\0');
 249 }
 250
 251 inline int VarintLength(uint64_t v) {
 252   int len = 1;
 253   while (v >= 128) {
 254     v >>= 7;
 255     len++;
 256   }
 257   return len;
 258 }
 259
 260 inline bool GetFixed64(Slice* input, uint64_t* value) {
 261   if (input->size() < sizeof(uint64_t)) {
 262     return false;
 263   }
 264   *value = DecodeFixed64(input->data());
 265   input->remove_prefix(sizeof(uint64_t));
 266   return true;
 267 }
 268
 269 inline bool GetFixed32(Slice* input, uint32_t* value) {
 270   if (input->size() < sizeof(uint32_t)) {
 271     return false;
 272   }
 273   *value = DecodeFixed32(input->data());
 274   input->remove_prefix(sizeof(uint32_t));
 275   return true;
 276 }
 277
 278 inline bool GetFixed16(Slice* input, uint16_t* value) {
 279   if (input->size() < sizeof(uint16_t)) {
 280     return false;
 281   }
 282   *value = DecodeFixed16(input->data());
 283   input->remove_prefix(sizeof(uint16_t));
 284   return true;
 285 }
 286
 287 inline bool GetVarint32(Slice* input, uint32_t* value) {
 288   const char* p = input->data();
 289   const char* limit = p + input->size();
 290   const char* q = GetVarint32Ptr(p, limit, value);
 291   if (q == nullptr) {
 292     return false;
 293   } else {
 294     *input = Slice(q, static_cast<size_t>(limit - q));
 295     return true;
 296   }
 297 }
 298
 299 inline bool GetVarint64(Slice* input, uint64_t* value) {
 300   const char* p = input->data();
 301   const char* limit = p + input->size();
 302   const char* q = GetVarint64Ptr(p, limit, value);
 303   if (q == nullptr) {
 304     return false;
 305   } else {
 306     *input = Slice(q, static_cast<size_t>(limit - q));
 307     return true;
 308   }
 309 }
 310
 311 inline bool GetVarsignedint64(Slice* input, int64_t* value) {
 312   const char* p = input->data();
 313   const char* limit = p + input->size();
 314   const char* q = GetVarsignedint64Ptr(p, limit, value);
 315   if (q == nullptr) {
 316     return false;
 317   } else {
 318     *input = Slice(q, static_cast<size_t>(limit - q));
 319     return true;
 320   }
 321 }
 322
 323 // Swaps between big and little endian. Can be used to in combination
 324 // with the little-endian encoding/decoding functions to encode/decode
 325 // big endian.
 326 template <typename T>
 327 inline T EndianSwapValue(T v) {
 328   static_assert(std::is_integral<T>::value, "non-integral type");
 329
 330 #ifdef _MSC_VER
 331   if (sizeof(T) == 2) {
 332     return static_cast<T>(_byteswap_ushort(static_cast<uint16_t>(v)));
 333   } else if (sizeof(T) == 4) {
 334     return static_cast<T>(_byteswap_ulong(static_cast<uint32_t>(v)));
 335   } else if (sizeof(T) == 8) {
 336     return static_cast<T>(_byteswap_uint64(static_cast<uint64_t>(v)));
 337   }
 338 #else
 339   if (sizeof(T) == 2) {
 340     return static_cast<T>(__builtin_bswap16(static_cast<uint16_t>(v)));
 341   } else if (sizeof(T) == 4) {
 342     return static_cast<T>(__builtin_bswap32(static_cast<uint32_t>(v)));
 343   } else if (sizeof(T) == 8) {
 344     return static_cast<T>(__builtin_bswap64(static_cast<uint64_t>(v)));
 345   }
 346 #endif
 347   // Recognized by clang as bswap, but not by gcc :(
 348   T ret_val = 0;
 349   for (size_t i = 0; i < sizeof(T); ++i) {
 350     ret_val |= ((v >> (8 * i)) & 0xff) << (8 * (sizeof(T) - 1 - i));
 351   }
 352   return ret_val;
 353 }
 354
 355 inline bool GetLengthPrefixedSlice(Slice* input, Slice* result) {
 356   uint32_t len = 0;
 357   if (GetVarint32(input, &len) && input->size() >= len) {
 358     *result = Slice(input->data(), len);
 359     input->remove_prefix(len);
 360     return true;
 361   } else {
 362     return false;
 363   }
 364 }
 365
 366 inline Slice GetLengthPrefixedSlice(const char* data) {
 367   uint32_t len = 0;
 368   // +5: we assume "data" is not corrupted
 369   // unsigned char is 7 bits, uint32_t is 32 bits, need 5 unsigned char
 370   auto p = GetVarint32Ptr(data, data + 5 /* limit */, &len);
 371   return Slice(p, len);
 372 }
 373
 374 inline Slice GetSliceUntil(Slice* slice, char delimiter) {
 375   uint32_t len = 0;
 376   for (len = 0; len < slice->size() && slice->data()[len] != delimiter; ++len) {
 377     // nothing
 378   }
 379
 380   Slice ret(slice->data(), len);
 381   slice->remove_prefix(len + ((len < slice->size()) ? 1 : 0));
 382   return ret;
 383 }
 384
 385 template<class T>
 386 #ifdef ROCKSDB_UBSAN_RUN
 387 #if defined(__clang__)
 388 __attribute__((__no_sanitize__("alignment")))
 389 #elif defined(__GNUC__)
 390 __attribute__((__no_sanitize_undefined__))
 391 #endif
 392 #endif
 393 inline void PutUnaligned(T *memory, const T &value) {
 394 #if defined(PLATFORM_UNALIGNED_ACCESS_NOT_ALLOWED)
 395   char *nonAlignedMemory = reinterpret_cast<char*>(memory);
 396   memcpy(nonAlignedMemory, reinterpret_cast<const char*>(&value), sizeof(T));
 397 #else
 398   *memory = value;
 399 #endif
 400 }
 401
 402 template<class T>
 403 #ifdef ROCKSDB_UBSAN_RUN
 404 #if defined(__clang__)
 405 __attribute__((__no_sanitize__("alignment")))
 406 #elif defined(__GNUC__)
 407 __attribute__((__no_sanitize_undefined__))
 408 #endif
 409 #endif
 410 inline void GetUnaligned(const T *memory, T *value) {
 411 #if defined(PLATFORM_UNALIGNED_ACCESS_NOT_ALLOWED)
 412   char *nonAlignedMemory = reinterpret_cast<char*>(value);
 413   memcpy(nonAlignedMemory, reinterpret_cast<const char*>(memory), sizeof(T));
 414 #else
 415   *value = *memory;
 416 #endif
 417 }
 418
 419 }  // namespace ROCKSDB_NAMESPACE