ceph/src/rocksdb/util/math128.h

   1 //  Copyright (c) Facebook, Inc. and its affiliates. 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 #pragma once
   7
   8 #include "util/coding_lean.h"
   9 #include "util/math.h"
  10
  11 #ifdef TEST_UINT128_COMPAT
  12 #undef HAVE_UINT128_EXTENSION
  13 #endif
  14
  15 namespace ROCKSDB_NAMESPACE {
  16
  17 // Unsigned128 is a 128 bit value supporting (at least) bitwise operators,
  18 // shifts, and comparisons. __uint128_t is not always available.
  19
  20 #ifdef HAVE_UINT128_EXTENSION
  21 using Unsigned128 = __uint128_t;
  22 #else
  23 struct Unsigned128 {
  24   uint64_t lo;
  25   uint64_t hi;
  26
  27   inline Unsigned128() {
  28     static_assert(sizeof(Unsigned128) == 2 * sizeof(uint64_t),
  29                   "unexpected overhead in representation");
  30     lo = 0;
  31     hi = 0;
  32   }
  33
  34   inline Unsigned128(uint64_t lower) {
  35     lo = lower;
  36     hi = 0;
  37   }
  38
  39   inline Unsigned128(uint64_t lower, uint64_t upper) {
  40     lo = lower;
  41     hi = upper;
  42   }
  43
  44   explicit operator uint64_t() { return lo; }
  45
  46   explicit operator uint32_t() { return static_cast<uint32_t>(lo); }
  47
  48   explicit operator uint16_t() { return static_cast<uint16_t>(lo); }
  49
  50   explicit operator uint8_t() { return static_cast<uint8_t>(lo); }
  51 };
  52
  53 inline Unsigned128 operator<<(const Unsigned128& lhs, unsigned shift) {
  54   shift &= 127;
  55   Unsigned128 rv;
  56   if (shift >= 64) {
  57     rv.lo = 0;
  58     rv.hi = lhs.lo << (shift & 63);
  59   } else {
  60     uint64_t tmp = lhs.lo;
  61     rv.lo = tmp << shift;
  62     // Ensure shift==0 shifts away everything. (This avoids another
  63     // conditional branch on shift == 0.)
  64     tmp = tmp >> 1 >> (63 - shift);
  65     rv.hi = tmp | (lhs.hi << shift);
  66   }
  67   return rv;
  68 }
  69
  70 inline Unsigned128& operator<<=(Unsigned128& lhs, unsigned shift) {
  71   lhs = lhs << shift;
  72   return lhs;
  73 }
  74
  75 inline Unsigned128 operator>>(const Unsigned128& lhs, unsigned shift) {
  76   shift &= 127;
  77   Unsigned128 rv;
  78   if (shift >= 64) {
  79     rv.hi = 0;
  80     rv.lo = lhs.hi >> (shift & 63);
  81   } else {
  82     uint64_t tmp = lhs.hi;
  83     rv.hi = tmp >> shift;
  84     // Ensure shift==0 shifts away everything
  85     tmp = tmp << 1 << (63 - shift);
  86     rv.lo = tmp | (lhs.lo >> shift);
  87   }
  88   return rv;
  89 }
  90
  91 inline Unsigned128& operator>>=(Unsigned128& lhs, unsigned shift) {
  92   lhs = lhs >> shift;
  93   return lhs;
  94 }
  95
  96 inline Unsigned128 operator&(const Unsigned128& lhs, const Unsigned128& rhs) {
  97   return Unsigned128(lhs.lo & rhs.lo, lhs.hi & rhs.hi);
  98 }
  99
 100 inline Unsigned128& operator&=(Unsigned128& lhs, const Unsigned128& rhs) {
 101   lhs = lhs & rhs;
 102   return lhs;
 103 }
 104
 105 inline Unsigned128 operator|(const Unsigned128& lhs, const Unsigned128& rhs) {
 106   return Unsigned128(lhs.lo | rhs.lo, lhs.hi | rhs.hi);
 107 }
 108
 109 inline Unsigned128& operator|=(Unsigned128& lhs, const Unsigned128& rhs) {
 110   lhs = lhs | rhs;
 111   return lhs;
 112 }
 113
 114 inline Unsigned128 operator^(const Unsigned128& lhs, const Unsigned128& rhs) {
 115   return Unsigned128(lhs.lo ^ rhs.lo, lhs.hi ^ rhs.hi);
 116 }
 117
 118 inline Unsigned128& operator^=(Unsigned128& lhs, const Unsigned128& rhs) {
 119   lhs = lhs ^ rhs;
 120   return lhs;
 121 }
 122
 123 inline Unsigned128 operator~(const Unsigned128& v) {
 124   return Unsigned128(~v.lo, ~v.hi);
 125 }
 126
 127 inline bool operator==(const Unsigned128& lhs, const Unsigned128& rhs) {
 128   return lhs.lo == rhs.lo && lhs.hi == rhs.hi;
 129 }
 130
 131 inline bool operator!=(const Unsigned128& lhs, const Unsigned128& rhs) {
 132   return lhs.lo != rhs.lo || lhs.hi != rhs.hi;
 133 }
 134
 135 inline bool operator>(const Unsigned128& lhs, const Unsigned128& rhs) {
 136   return lhs.hi > rhs.hi || (lhs.hi == rhs.hi && lhs.lo > rhs.lo);
 137 }
 138
 139 inline bool operator<(const Unsigned128& lhs, const Unsigned128& rhs) {
 140   return lhs.hi < rhs.hi || (lhs.hi == rhs.hi && lhs.lo < rhs.lo);
 141 }
 142
 143 inline bool operator>=(const Unsigned128& lhs, const Unsigned128& rhs) {
 144   return lhs.hi > rhs.hi || (lhs.hi == rhs.hi && lhs.lo >= rhs.lo);
 145 }
 146
 147 inline bool operator<=(const Unsigned128& lhs, const Unsigned128& rhs) {
 148   return lhs.hi < rhs.hi || (lhs.hi == rhs.hi && lhs.lo <= rhs.lo);
 149 }
 150 #endif
 151
 152 inline uint64_t Lower64of128(Unsigned128 v) {
 153 #ifdef HAVE_UINT128_EXTENSION
 154   return static_cast<uint64_t>(v);
 155 #else
 156   return v.lo;
 157 #endif
 158 }
 159
 160 inline uint64_t Upper64of128(Unsigned128 v) {
 161 #ifdef HAVE_UINT128_EXTENSION
 162   return static_cast<uint64_t>(v >> 64);
 163 #else
 164   return v.hi;
 165 #endif
 166 }
 167
 168 // This generally compiles down to a single fast instruction on 64-bit.
 169 // This doesn't really make sense as operator* because it's not a
 170 // general 128x128 multiply and provides more output than 64x64 multiply.
 171 inline Unsigned128 Multiply64to128(uint64_t a, uint64_t b) {
 172 #ifdef HAVE_UINT128_EXTENSION
 173   return Unsigned128{a} * Unsigned128{b};
 174 #else
 175   // Full decomposition
 176   // NOTE: GCC seems to fully understand this code as 64-bit x 64-bit
 177   // -> 128-bit multiplication and optimize it appropriately.
 178   uint64_t tmp = uint64_t{b & 0xffffFFFF} * uint64_t{a & 0xffffFFFF};
 179   uint64_t lower = tmp & 0xffffFFFF;
 180   tmp >>= 32;
 181   tmp += uint64_t{b & 0xffffFFFF} * uint64_t{a >> 32};
 182   // Avoid overflow: first add lower 32 of tmp2, and later upper 32
 183   uint64_t tmp2 = uint64_t{b >> 32} * uint64_t{a & 0xffffFFFF};
 184   tmp += tmp2 & 0xffffFFFF;
 185   lower |= tmp << 32;
 186   tmp >>= 32;
 187   tmp += tmp2 >> 32;
 188   tmp += uint64_t{b >> 32} * uint64_t{a >> 32};
 189   return Unsigned128(lower, tmp);
 190 #endif
 191 }
 192
 193 template <>
 194 inline int FloorLog2(Unsigned128 v) {
 195   if (Upper64of128(v) == 0) {
 196     return FloorLog2(Lower64of128(v));
 197   } else {
 198     return FloorLog2(Upper64of128(v)) + 64;
 199   }
 200 }
 201
 202 template <>
 203 inline int CountTrailingZeroBits(Unsigned128 v) {
 204   if (Lower64of128(v) != 0) {
 205     return CountTrailingZeroBits(Lower64of128(v));
 206   } else {
 207     return CountTrailingZeroBits(Upper64of128(v)) + 64;
 208   }
 209 }
 210
 211 template <>
 212 inline int BitsSetToOne(Unsigned128 v) {
 213   return BitsSetToOne(Lower64of128(v)) + BitsSetToOne(Upper64of128(v));
 214 }
 215
 216 template <>
 217 inline int BitParity(Unsigned128 v) {
 218   return BitParity(Lower64of128(v) ^ Upper64of128(v));
 219 }
 220
 221 template <>
 222 inline Unsigned128 EndianSwapValue(Unsigned128 v) {
 223   return (Unsigned128{EndianSwapValue(Lower64of128(v))} << 64) |
 224          EndianSwapValue(Upper64of128(v));
 225 }
 226
 227 template <>
 228 inline Unsigned128 ReverseBits(Unsigned128 v) {
 229   return (Unsigned128{ReverseBits(Lower64of128(v))} << 64) |
 230          ReverseBits(Upper64of128(v));
 231 }
 232
 233 template <>
 234 inline Unsigned128 DownwardInvolution(Unsigned128 v) {
 235   return (Unsigned128{DownwardInvolution(Upper64of128(v))} << 64) |
 236          DownwardInvolution(Upper64of128(v) ^ Lower64of128(v));
 237 }
 238
 239 template <typename T>
 240 struct IsUnsignedUpTo128
 241     : std::integral_constant<bool, std::is_unsigned<T>::value ||
 242                                        std::is_same<T, Unsigned128>::value> {};
 243
 244 inline void EncodeFixed128(char* dst, Unsigned128 value) {
 245   EncodeFixed64(dst, Lower64of128(value));
 246   EncodeFixed64(dst + 8, Upper64of128(value));
 247 }
 248
 249 inline Unsigned128 DecodeFixed128(const char* ptr) {
 250   Unsigned128 rv = DecodeFixed64(ptr + 8);
 251   return (rv << 64) | DecodeFixed64(ptr);
 252 }
 253
 254 // A version of EncodeFixed* for generic algorithms. Likely to be used
 255 // with Unsigned128, so lives here for now.
 256 template <typename T>
 257 inline void EncodeFixedGeneric(char* /*dst*/, T /*value*/) {
 258   // Unfortunately, GCC does not appear to optimize this simple code down
 259   // to a trivial load on Intel:
 260   //
 261   // T ret_val = 0;
 262   // for (size_t i = 0; i < sizeof(T); ++i) {
 263   //   ret_val |= (static_cast<T>(static_cast<unsigned char>(ptr[i])) << (8 *
 264   //   i));
 265   // }
 266   // return ret_val;
 267   //
 268   // But does unroll the loop, and does optimize manually unrolled version
 269   // for specific sizes down to a trivial load. I have no idea why it doesn't
 270   // do both on this code.
 271
 272   // So instead, we rely on specializations
 273   static_assert(sizeof(T) == 0, "No specialization provided for this type");
 274 }
 275
 276 template <>
 277 inline void EncodeFixedGeneric(char* dst, uint16_t value) {
 278   return EncodeFixed16(dst, value);
 279 }
 280 template <>
 281 inline void EncodeFixedGeneric(char* dst, uint32_t value) {
 282   return EncodeFixed32(dst, value);
 283 }
 284 template <>
 285 inline void EncodeFixedGeneric(char* dst, uint64_t value) {
 286   return EncodeFixed64(dst, value);
 287 }
 288 template <>
 289 inline void EncodeFixedGeneric(char* dst, Unsigned128 value) {
 290   return EncodeFixed128(dst, value);
 291 }
 292
 293 // A version of EncodeFixed* for generic algorithms.
 294 template <typename T>
 295 inline T DecodeFixedGeneric(const char* /*dst*/) {
 296   static_assert(sizeof(T) == 0, "No specialization provided for this type");
 297 }
 298
 299 template <>
 300 inline uint16_t DecodeFixedGeneric(const char* dst) {
 301   return DecodeFixed16(dst);
 302 }
 303 template <>
 304 inline uint32_t DecodeFixedGeneric(const char* dst) {
 305   return DecodeFixed32(dst);
 306 }
 307 template <>
 308 inline uint64_t DecodeFixedGeneric(const char* dst) {
 309   return DecodeFixed64(dst);
 310 }
 311 template <>
 312 inline Unsigned128 DecodeFixedGeneric(const char* dst) {
 313   return DecodeFixed128(dst);
 314 }
 315
 316 }  // namespace ROCKSDB_NAMESPACE