Botan
1.11.15
|
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