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

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