alloc: first cut of tiny allocator (down to 2 bytes!)
[ccan] / 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 }