headers/private/kernel/util/BitUtils.h

   1 /*
   2  * Copyright 2013 Haiku, Inc. All rights reserved.
   3  * Distributed under the terms of the MIT License.
   4  *
   5  * Authors:
   6  *              Paweł Dziepak, pdziepak@quarnos.org
   7  */
   8 #ifndef KERNEL_UTIL_BITUTIL_H
   9 #define KERNEL_UTIL_BITUTIL_H
  10
  11
  12 #include <SupportDefs.h>
  13
  14
  15 // http://graphics.stanford.edu/~seander/bithacks.html
  16 static inline uint32
  17 next_power_of_2(uint32 v)
  18 {
  19         v--;
  20         v |= v >> 1;
  21         v |= v >> 2;
  22         v |= v >> 4;
  23         v |= v >> 8;
  24         v |= v >> 16;
  25         v++;
  26
  27         return v;
  28 }
  29
  30
  31 // http://graphics.stanford.edu/~seander/bithacks.html
  32 static inline uint32
  33 count_set_bits(uint32 v)
  34 {
  35         v = v - ((v >> 1) & 0x55555555);
  36         v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
  37         return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
  38 }
  39
  40
  41 static inline uint32
  42 log2(uint32 v)
  43 {
  44         static const int MultiplyDeBruijnBitPosition[32] = {
  45                 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
  46                 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
  47         };
  48
  49         v |= v >> 1;
  50         v |= v >> 2;
  51         v |= v >> 4;
  52         v |= v >> 8;
  53         v |= v >> 16;
  54
  55         return MultiplyDeBruijnBitPosition[(uint32)(v * 0x07C4ACDDU) >> 27];
  56 }
  57
  58
  59 #endif  // KERNEL_UTIL_BITUTIL_H
  60