alloc: avoid dead store to hdrlen
[ccan] / 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 }