Botan  1.11.15
src/lib/utils/bit_ops.h
Go to the documentation of this file.
00001 /*
00002 * Bit/Word Operations
00003 * (C) 1999-2008 Jack Lloyd
00004 * (C) Copyright Projet SECRET, INRIA, Rocquencourt
00005 * (C) Bhaskar Biswas and  Nicolas Sendrier
00006 * (C) 2014 cryptosource GmbH
00007 * (C) 2014 Falko Strenzke fstrenzke@cryptosource.de
00008 *
00009 * Botan is released under the Simplified BSD License (see license.txt)
00010 */
00011 
00012 #ifndef BOTAN_BIT_OPS_H__
00013 #define BOTAN_BIT_OPS_H__
00014 
00015 #include <botan/types.h>
00016 
00017 namespace Botan {
00018 
00019 /**
00020 * Power of 2 test. T should be an unsigned integer type
00021 * @param arg an integer value
00022 * @return true iff arg is 2^n for some n > 0
00023 */
00024 template<typename T>
00025 inline bool is_power_of_2(T arg)
00026    {
00027    return ((arg != 0 && arg != 1) && ((arg & (arg-1)) == 0));
00028    }
00029 
00030 /**
00031 * Return the index of the highest set bit
00032 * T is an unsigned integer type
00033 * @param n an integer value
00034 * @return index of the highest set bit in n
00035 */
00036 template<typename T>
00037 inline size_t high_bit(T n)
00038    {
00039    for(size_t i = 8*sizeof(T); i > 0; --i)
00040       if((n >> (i - 1)) & 0x01)
00041          return i;
00042    return 0;
00043    }
00044 
00045 /**
00046 * Return the index of the lowest set bit
00047 * T is an unsigned integer type
00048 * @param n an integer value
00049 * @return index of the lowest set bit in n
00050 */
00051 template<typename T>
00052 inline size_t low_bit(T n)
00053    {
00054    for(size_t i = 0; i != 8*sizeof(T); ++i)
00055       if((n >> i) & 0x01)
00056          return (i + 1);
00057    return 0;
00058    }
00059 
00060 /**
00061 * Return the number of significant bytes in n
00062 * @param n an integer value
00063 * @return number of significant bytes in n
00064 */
00065 template<typename T>
00066 inline size_t significant_bytes(T n)
00067    {
00068    for(size_t i = 0; i != sizeof(T); ++i)
00069       if(get_byte(i, n))
00070          return sizeof(T)-i;
00071    return 0;
00072    }
00073 
00074 /**
00075 * Compute Hamming weights
00076 * @param n an integer value
00077 * @return number of bits in n set to 1
00078 */
00079 template<typename T>
00080 inline size_t hamming_weight(T n)
00081    {
00082    const byte NIBBLE_WEIGHTS[] = {
00083       0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
00084 
00085    size_t weight = 0;
00086    for(size_t i = 0; i != 2*sizeof(T); ++i)
00087       weight += NIBBLE_WEIGHTS[(n >> (4*i)) & 0x0F];
00088    return weight;
00089    }
00090 
00091 /**
00092 * Count the trailing zero bits in n
00093 * @param n an integer value
00094 * @return maximum x st 2^x divides n
00095 */
00096 template<typename T>
00097 inline size_t ctz(T n)
00098    {
00099    for(size_t i = 0; i != 8*sizeof(T); ++i)
00100       if((n >> i) & 0x01)
00101          return i;
00102    return 8*sizeof(T);
00103    }
00104 
00105 template<typename T>
00106 size_t ceil_log2(T x)
00107    {
00108    if(x >> (sizeof(T)*8-1))
00109       return sizeof(T)*8;
00110 
00111    size_t result = 0;
00112    T compare = 1;
00113 
00114    while(compare < x)
00115       {
00116       compare <<= 1;
00117       result++;
00118       }
00119 
00120    return result;
00121    }
00122 
00123 }
00124 
00125 #endif