alloc: move into antithread/alloc.
[ccan] / ccan / antithread / 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 >> 2) & 0x3333333333333333ULL);
74                 v = (v & 0x0F0F0F0F0F0F0F0FULL)
75                         + ((v >> 4) & 0x0F0F0F0F0F0F0F0FULL);
76                 v = (v & 0x00FF00FF00FF00FFULL)
77                         + ((v >> 8) & 0x00FF00FF00FF00FFULL);
78                 v = (v & 0x0000FFFF0000FFFFULL)
79                         + ((v >> 16) & 0x0000FFFF0000FFFFULL);
80                 v = (v & 0x00000000FFFFFFFFULL)
81                         + ((v >> 32) & 0x00000000FFFFFFFFULL);
82                 return v;
83         }
84         val = (val & 0x55555555ULL) + ((val >> 1) & 0x55555555ULL);
85         val = (val & 0x33333333ULL) + ((val >> 2) & 0x33333333ULL);
86         val = (val & 0x0F0F0F0FULL) + ((val >> 4) & 0x0F0F0F0FULL);
87         val = (val & 0x00FF00FFULL) + ((val >> 8) & 0x00FF00FFULL);
88         val = (val & 0x0000FFFFULL) + ((val >> 16) & 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 }