Commit | Line | Data |
---|---|---|
3144ee8a AT |
1 | /* pow2, Copyright (c) 2016 Dave Odell <dmo2118@gmail.com> |
2 | * | |
3 | * Permission to use, copy, modify, distribute, and sell this software and its | |
4 | * documentation for any purpose is hereby granted without fee, provided that | |
5 | * the above copyright notice appear in all copies and that both that | |
6 | * copyright notice and this permission notice appear in supporting | |
7 | * documentation. No representations are made about the suitability of this | |
8 | * software for any purpose. It is provided "as is" without express or | |
9 | * implied warranty. | |
10 | */ | |
11 | ||
12 | #include "pow2.h" | |
13 | ||
14 | #include <limits.h> | |
15 | ||
16 | int | |
17 | i_log2 (size_t x) | |
18 | { | |
19 | /* -1 works best for to_pow2. */ | |
20 | if (!x) | |
21 | return -1; | |
22 | ||
23 | /* GCC 3.4 also has this. */ | |
24 | # if defined __GNUC__ && __GNUC__ >= 4 || defined __clang__ | |
25 | return sizeof(long) * CHAR_BIT - __builtin_clzl(x) - 1; | |
26 | # else | |
27 | { | |
28 | unsigned bits = sizeof(x) * CHAR_BIT; | |
29 | size_t mask = (size_t)-1; | |
30 | unsigned result = bits - 1; | |
31 | ||
32 | while (bits) { | |
33 | if (!(x & mask)) { | |
34 | result -= bits; | |
35 | x <<= bits; | |
36 | } | |
37 | ||
38 | bits >>= 1; | |
39 | mask <<= bits; | |
40 | } | |
41 | ||
42 | return result; | |
43 | } | |
44 | # endif | |
45 | } | |
46 | ||
47 | size_t | |
48 | to_pow2 (size_t x) | |
49 | { | |
50 | return !x ? 1 : 1 << (i_log2(x - 1) + 1); | |
51 | } |