| 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 | } |