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

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