legacy-libs/grpc-cloned/deps/grpc/third_party/abseil-cpp/absl/random/internal/fastmath.h

   1 // Copyright 2017 The Abseil Authors.
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License");
   4 // you may not use this file except in compliance with the License.
   5 // You may obtain a copy of the License at
   6 //
   7 //      https://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS,
  11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 // See the License for the specific language governing permissions and
  13 // limitations under the License.
  14
  15 #ifndef ABSL_RANDOM_INTERNAL_FASTMATH_H_
  16 #define ABSL_RANDOM_INTERNAL_FASTMATH_H_
  17
  18 // This file contains fast math functions (bitwise ops as well as some others)
  19 // which are implementation details of various absl random number distributions.
  20
  21 #include <cassert>
  22 #include <cmath>
  23 #include <cstdint>
  24
  25 #include "absl/base/internal/bits.h"
  26
  27 namespace absl {
  28 namespace random_internal {
  29
  30 // Returns the position of the first bit set.
  31 inline int LeadingSetBit(uint64_t n) {
  32   return 64 - base_internal::CountLeadingZeros64(n);
  33 }
  34
  35 // Compute log2(n) using integer operations.
  36 // While std::log2 is more accurate than std::log(n) / std::log(2), for
  37 // very large numbers--those close to std::numeric_limits<uint64_t>::max() - 2,
  38 // for instance--std::log2 rounds up rather than down, which introduces
  39 // definite skew in the results.
  40 inline int IntLog2Floor(uint64_t n) {
  41   return (n <= 1) ? 0 : (63 - base_internal::CountLeadingZeros64(n));
  42 }
  43 inline int IntLog2Ceil(uint64_t n) {
  44   return (n <= 1) ? 0 : (64 - base_internal::CountLeadingZeros64(n - 1));
  45 }
  46
  47 inline double StirlingLogFactorial(double n) {
  48   assert(n >= 1);
  49   // Using Stirling's approximation.
  50   constexpr double kLog2PI = 1.83787706640934548356;
  51   const double logn = std::log(n);
  52   const double ninv = 1.0 / static_cast<double>(n);
  53   return n * logn - n + 0.5 * (kLog2PI + logn) + (1.0 / 12.0) * ninv -
  54          (1.0 / 360.0) * ninv * ninv * ninv;
  55 }
  56
  57 // Rotate value right.
  58 //
  59 // We only implement the uint32_t / uint64_t versions because
  60 // 1) those are the only ones we use, and
  61 // 2) those are the only ones where clang detects the rotate idiom correctly.
  62 inline constexpr uint32_t rotr(uint32_t value, uint8_t bits) {
  63   return (value >> (bits & 31)) | (value << ((-bits) & 31));
  64 }
  65 inline constexpr uint64_t rotr(uint64_t value, uint8_t bits) {
  66   return (value >> (bits & 63)) | (value << ((-bits) & 63));
  67 }
  68
  69 }  // namespace random_internal
  70 }  // namespace absl
  71
  72 #endif  // ABSL_RANDOM_INTERNAL_FASTMATH_H_