git.ozlabs.org Git - ccan/blob - ccan/alloc/bitops.c

   1 #include "bitops.h"
   2 #include "config.h"
   3 #include <ccan/build_assert/build_assert.h>
   4 #include <ccan/short_types/short_types.h>
   5 #include <ccan/ilog/ilog.h>
   6 #include <limits.h>
   7
   8 unsigned int fls(unsigned long val)
   9 {
  10         BUILD_ASSERT(sizeof(val) == sizeof(u32) || sizeof(val) == sizeof(u64));
  11         if (sizeof(val) == sizeof(u32))
  12                 return ilog32(val);
  13         else
  14                 return ilog64(val);
  15 }
  16
  17 /* FIXME: Move to bitops. */
  18 unsigned int ffsl(unsigned long val)
  19 {
  20 #if HAVE_BUILTIN_FFSL
  21         /* This is significantly faster! */
  22         return __builtin_ffsl(val);
  23 #else
  24         unsigned int r = 1;
  25
  26         if (!val)
  27                 return 0;
  28         if (sizeof(long) == sizeof(u64)) {
  29                 if (!(val & 0xffffffff)) {
  30                         /* Workaround gcc warning on 32-bit:
  31                            error: right shift count >= width of type */
  32                         u64 tmp = val;
  33                         tmp >>= 32;
  34                         val = tmp;
  35                         r += 32;
  36                 }
  37         }
  38         if (!(val & 0xffff)) {
  39                 val >>= 16;
  40                 r += 16;
  41         }
  42         if (!(val & 0xff)) {
  43                 val >>= 8;
  44                 r += 8;
  45         }
  46         if (!(val & 0xf)) {
  47                 val >>= 4;
  48                 r += 4;
  49         }
  50         if (!(val & 3)) {
  51                 val >>= 2;
  52                 r += 2;
  53         }
  54         if (!(val & 1)) {
  55                 val >>= 1;
  56                 r += 1;
  57         }
  58         return r;
  59 #endif
  60 }
  61
  62 unsigned int popcount(unsigned long val)
  63 {
  64 #if HAVE_BUILTIN_POPCOUNTL
  65         return __builtin_popcountl(val);
  66 #else
  67         if (sizeof(long) == sizeof(u64)) {
  68                 u64 v = val;
  69                 v = (v & 0x5555555555555555ULL)
  70                         + ((v >> 1) & 0x5555555555555555ULL);
  71                 v = (v & 0x3333333333333333ULL)
  72                         + ((v >> 1) & 0x3333333333333333ULL);
  73                 v = (v & 0x0F0F0F0F0F0F0F0FULL)
  74                         + ((v >> 1) & 0x0F0F0F0F0F0F0F0FULL);
  75                 v = (v & 0x00FF00FF00FF00FFULL)
  76                         + ((v >> 1) & 0x00FF00FF00FF00FFULL);
  77                 v = (v & 0x0000FFFF0000FFFFULL)
  78                         + ((v >> 1) & 0x0000FFFF0000FFFFULL);
  79                 v = (v & 0x00000000FFFFFFFFULL)
  80                         + ((v >> 1) & 0x00000000FFFFFFFFULL);
  81                 return v;
  82         }
  83         val = (val & 0x55555555ULL) + ((val >> 1) & 0x55555555ULL);
  84         val = (val & 0x33333333ULL) + ((val >> 1) & 0x33333333ULL);
  85         val = (val & 0x0F0F0F0FULL) + ((val >> 1) & 0x0F0F0F0FULL);
  86         val = (val & 0x00FF00FFULL) + ((val >> 1) & 0x00FF00FFULL);
  87         val = (val & 0x0000FFFFULL) + ((val >> 1) & 0x0000FFFFULL);
  88         return val;
  89 #endif
  90 }
  91
  92 unsigned long align_up(unsigned long x, unsigned long align)
  93 {
  94         return (x + align - 1) & ~(align - 1);
  95 }