diff options
Diffstat (limited to 'csrc/algorithms/bits/powers.h')
| -rw-r--r-- | csrc/algorithms/bits/powers.h | 245 |
1 files changed, 245 insertions, 0 deletions
diff --git a/csrc/algorithms/bits/powers.h b/csrc/algorithms/bits/powers.h new file mode 100644 index 0000000..1018036 --- /dev/null +++ b/csrc/algorithms/bits/powers.h @@ -0,0 +1,245 @@ +/** + * Copyright © 2014 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#ifndef ALGO_ALGORITHMS_BITS_POWERS_H +#define ALGO_ALGORITHMS_BITS_POWERS_H + + +/* NB! This will not play nice if the placeholder `T` is + * not set to a type only containing [0-9A-Za-z_] (and $ + * in GNU C). Therefore, with the exception of `char`, + * `short`, `int`, `long`, `float` and `double`, you + * should only use `typedef`:ed types. */ + +#include <limits.h> + +/* Note: These functions assume C-rules for integer encoding, + * namely, then n:th bit represent 2 to the power of n, and + * the bitwise or is equivalent to addition if all operands + * are single-bit valued. */ + + +/** + * Compute whether an integer is a power of two. + * Note that zero is indeed not a power of two. + * + * This function only works on integer types. And it + * assumes that C-rules for integer encoding applies. + * + * `algo_make_implementation_of_is_power_of_2(T)` + * is used to make this function available for a particular + * data type `T`. And implementation without modifiers and + * attributes will be expanded. You may add `static`, + * `inline` and `__attribute__` before calling + * `algo_make_implementation_of_is_power_of_2(T)`. + * + * `algo_make_prototype_of_is_power_of_2(T)` + * is the prototype counterpart of + * `algo_make_implementation_of_is_power_of_2(T)`. + * It too is will not add any modifiers or attributes by + * default. It will neither add a semicolon at the end of + * the prototype. + * + * `algo_is_power_of_2(T)` is used to get the version + * of the function that supports the data type `T`. + * `&(algo_is_power_of_2(T))` gets the address of this + * function and `algo_is_power_of_2(T)(items, n, min, max)` + * calls the function. + * + * This function is constant, if you are using GCC you + * should add `__attribute__((const))` to its prototype. + * + * @param value The integer. + * @return Whether the integer is a power of two. + */ +//>fun () { +int algo_is_power_of_2__##T(T value) +{ + /* The left hand side clears the least significant bit set. */ + return (value & (value - 1)) == 0; + /* Or alternatively: (value & -value) == value*/ +} +//>} ; . ../make_fun + + +/** + * Computes the nearest, but higher, power of two, + * independently of whether the current value is + * a power of two or not. + * + * This function only works on integer types. And it + * assumes that C-rules for integer encoding applies. + * + * `algo_make_implementation_of_next_power_of_2(T)` + * is used to make this function available for a particular + * data type `T`. And implementation without modifiers and + * attributes will be expanded. You may add `static`, + * `inline` and `__attribute__` before calling + * `algo_make_implementation_of_next_power_of_2(T)`. + * + * `algo_make_prototype_of_next_power_of_2(T)` + * is the prototype counterpart of + * `algo_make_implementation_of_next_power_of_2(T)`. + * It too is will not add any modifiers or attributes by + * default. It will neither add a semicolon at the end of + * the prototype. + * + * `algo_next_power_of_2(T)` is used to get the version + * of the function that supports the data type `T`. + * `&(algo_next_power_of_2(T))` gets the address of this + * function and `algo_next_power_of_2(T)(items, n, min, max)` + * calls the function. + * + * This function is constant, if you are using GCC you + * should add `__attribute__((const))` to its prototype. + * + * Undefined behaviour is invoked if `value` is negative. + * + * @param value The current value, must be non-negative. + * @return The next power of two. + */ +//>fun () { +T algo_next_power_of_2__##T(T value) +{ + size_t i, n = sizeof(T); + value |= value >> 1; + value |= value >> 2; + value |= value >> 3; + for (i = 1; n > i; i <<= 1) + value |= value >> (i * 8); + return value + 1; +} +//>} ; . ../make_fun + +/* Hopefully you compiler can unroll the loop fully + * and optimise out our helper variables. These are + * added simply for flexibility and not assuming + * any limitations on how large an integer can be. */ + + +/** + * Computes the nearest, but higher, power of two, + * but only if the current value is not a power of two. + * If the current value is a power of 2, that value + * will be returned. + * + * This function only works on integer types. And it + * assumes that C-rules for integer encoding applies. + * + * `algo_make_implementation_of_next_power_of_2(T)` + * is used to make this function available for a particular + * data type `T`. And implementation without modifiers and + * attributes will be expanded. You may add `static`, + * `inline` and `__attribute__` before calling + * `algo_make_implementation_of_next_power_of_2(T)`. + * + * `algo_make_prototype_of_next_power_of_2(T)` + * is the prototype counterpart of + * `algo_make_implementation_of_next_power_of_2(T)`. + * It too is will not add any modifiers or attributes by + * default. It will neither add a semicolon at the end of + * the prototype. + * + * `algo_next_power_of_2(T)` is used to get the version + * of the function that supports the data type `T`. + * `&(algo_next_power_of_2(T))` gets the address of this + * function and `algo_next_power_of_2(T)(items, n, min, max)` + * calls the function. + * + * This function is constant, if you are using GCC you + * should add `__attribute__((const))` to its prototype. + * + * Undefined behaviour is invoked if `value` is zero or + * negative. + * + * @param value The current value, must be positive. + * @return The next power of two, or the current + * value if it already is a power of 2. + */ +//>fun () { +T algo_next_power_of_2__##T(T value) +{ + size_t i, n = sizeof(T); + value -= 1; + value |= value >> 1; + value |= value >> 2; + value |= value >> 3; + for (i = 1; n > i; i <<= 1) + value |= value >> (i * 8); + return value + 1; +} +//>} ; . ../make_fun + + +/** + * Computes the nearest, but higher, power of two, + * but only if the current value is not a power of two. + * If the current value is a power of 2, that value + * will be returned. However, if the value is non-positive, + * zero will be returned. + * + * This function only works on integer types. And it + * assumes that C-rules for integer encoding applies. + * + * `algo_make_implementation_of_next_power_of_2_or_zero(T)` + * is used to make this function available for a particular + * data type `T`. And implementation without modifiers and + * attributes will be expanded. You may add `static`, + * `inline` and `__attribute__` before calling + * `algo_make_implementation_of_next_power_of_2_or_zero(T)`. + * + * `algo_make_prototype_of_next_power_of_2_or_zero(T)` + * is the prototype counterpart of + * `algo_make_implementation_of_next_power_of_2_or_zero(T)`. + * It too is will not add any modifiers or attributes by + * default. It will neither add a semicolon at the end of + * the prototype. + * + * `algo_next_power_of_2_or_zero(T)` is used to get the version + * of the function that supports the data type `T`. + * `&(algo_next_power_of_2_or_zero(T))` gets the address of this + * function and `algo_next_power_of_2_or_zero(T)(items, n, min, max)` + * calls the function. + * + * This function is constant, if you are using GCC you + * should add `__attribute__((const))` to its prototype. + * + * `algo_next_power_of_2_or_zero(T)(value | 1)` would behave + * the same way, except, 0 would map to 1. + * + * @param value The current value. + * @return The next power of two or zero, or the + * current value if it already is a power + * of 2 or zero. + */ +//>fun () { +T algo_next_power_of_2_or_zero__##T(T value) +{ + size_t i, n = sizeof(T); + value -= 1; + value &= ~((1 << (n * CHAR_BIT - 1)) - 1); + value |= value >> 1; + value |= value >> 2; + value |= value >> 3; + for (i = 1; n > i; i <<= 1) + value |= value >> (i * 8); + return value + 1; +} +//>} ; . ../make_fun + + +#endif + |