silo/log2.hh

   1 // taken from xv6
   2
   3 #pragma once
   4
   5 #include <cstddef>
   6
   7 // Return ceil(log2(x)).
   8 static inline std::size_t
   9 ceil_log2(std::size_t x)
  10 {
  11   auto bits = sizeof(long long) * 8 - __builtin_clzll(x);
  12   if (x == (std::size_t)1 << (bits - 1))
  13     return bits - 1;
  14   return bits;
  15 }
  16
  17 // Return ceil(log2(x)).  This is slow, but can be evaluated in a
  18 // constexpr context.  'exact' is used internally and should not be
  19 // provided by the caller.
  20 static inline constexpr std::size_t
  21 ceil_log2_const(std::size_t x, bool exact = true)
  22 {
  23   return (x == 0) ? (1/x)
  24     : (x == 1) ? (exact ? 0 : 1)
  25     : 1 + ceil_log2_const(x >> 1, ((x & 1) == 1) ? false : exact);
  26 }
  27
  28 // Round up to the nearest power of 2
  29 static inline std::size_t
  30 round_up_to_pow2(std::size_t x)
  31 {
  32   auto bits = sizeof(long long) * 8 - __builtin_clzll(x);
  33   if (x == (std::size_t)1 << (bits - 1))
  34     return x;
  35   return (std::size_t)1 << bits;
  36 }
  37
  38 static inline constexpr std::size_t
  39 round_up_to_pow2_const(std::size_t x)
  40 {
  41   return (std::size_t)1 << ceil_log2_const(x);
  42 }