src/lib/intmath/bits.c

   1 /* Copyright (c) 2003-2004, Roger Dingledine
   2  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
   3  * Copyright (c) 2007-2019, The Tor Project, Inc. */
   4 /* See LICENSE for licensing information */
   5
   6 /**
   7  * \file bits.c
   8  *
   9  * \brief Count the bits in an integer, manipulate powers of 2, etc.
  10  **/
  11
  12 #include "lib/intmath/bits.h"
  13
  14 /** Returns floor(log2(u64)).  If u64 is 0, (incorrectly) returns 0. */
  15 int
  16 tor_log2(uint64_t u64)
  17 {
  18   int r = 0;
  19   if (u64 >= (UINT64_C(1)<<32)) {
  20     u64 >>= 32;
  21     r = 32;
  22   }
  23   if (u64 >= (UINT64_C(1)<<16)) {
  24     u64 >>= 16;
  25     r += 16;
  26   }
  27   if (u64 >= (UINT64_C(1)<<8)) {
  28     u64 >>= 8;
  29     r += 8;
  30   }
  31   if (u64 >= (UINT64_C(1)<<4)) {
  32     u64 >>= 4;
  33     r += 4;
  34   }
  35   if (u64 >= (UINT64_C(1)<<2)) {
  36     u64 >>= 2;
  37     r += 2;
  38   }
  39   if (u64 >= (UINT64_C(1)<<1)) {
  40     // u64 >>= 1; // not using this any more.
  41     r += 1;
  42   }
  43   return r;
  44 }
  45
  46 /** Return the power of 2 in range [1,UINT64_MAX] closest to <b>u64</b>.  If
  47  * there are two powers of 2 equally close, round down. */
  48 uint64_t
  49 round_to_power_of_2(uint64_t u64)
  50 {
  51   int lg2;
  52   uint64_t low;
  53   uint64_t high;
  54   if (u64 == 0)
  55     return 1;
  56
  57   lg2 = tor_log2(u64);
  58   low = UINT64_C(1) << lg2;
  59
  60   if (lg2 == 63)
  61     return low;
  62
  63   high = UINT64_C(1) << (lg2+1);
  64   if (high - u64 < u64 - low)
  65     return high;
  66   else
  67     return low;
  68 }
  69
  70 /** Return the number of bits set in <b>v</b>. */
  71 int
  72 n_bits_set_u8(uint8_t v)
  73 {
  74   static const int nybble_table[] = {
  75     0, /* 0000 */
  76     1, /* 0001 */
  77     1, /* 0010 */
  78     2, /* 0011 */
  79     1, /* 0100 */
  80     2, /* 0101 */
  81     2, /* 0110 */
  82     3, /* 0111 */
  83     1, /* 1000 */
  84     2, /* 1001 */
  85     2, /* 1010 */
  86     3, /* 1011 */
  87     2, /* 1100 */
  88     3, /* 1101 */
  89     3, /* 1110 */
  90     4, /* 1111 */
  91   };
  92
  93   return nybble_table[v & 15] + nybble_table[v>>4];
  94 }