bits.h (3542B)
1 /* GRAPHITE2 LICENSING 2 3 Copyright 2012, SIL International 4 All rights reserved. 5 6 This library is free software; you can redistribute it and/or modify 7 it under the terms of the GNU Lesser General Public License as published 8 by the Free Software Foundation; either version 2.1 of License, or 9 (at your option) any later version. 10 11 This program is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14 Lesser General Public License for more details. 15 16 You should also have received a copy of the GNU Lesser General Public 17 License along with this library in the file named "LICENSE". 18 If not, write to the Free Software Foundation, 51 Franklin Street, 19 Suite 500, Boston, MA 02110-1335, USA or visit their web page on the 20 internet at http://www.fsf.org/licenses/lgpl.html. 21 22 Alternatively, the contents of this file may be used under the terms of the 23 Mozilla Public License (http://mozilla.org/MPL) or the GNU General Public 24 License, as published by the Free Software Foundation, either version 2 25 of the License or (at your option) any later version. 26 */ 27 #pragma once 28 29 namespace graphite2 30 { 31 32 33 #if defined GRAPHITE2_BUILTINS && (defined __GNUC__ || defined __clang__) 34 35 template<typename T> 36 inline unsigned int bit_set_count(T v) 37 { 38 return __builtin_popcount(v); 39 } 40 41 template<> 42 inline unsigned int bit_set_count(int16 v) 43 { 44 return __builtin_popcount(static_cast<uint16>(v)); 45 } 46 47 template<> 48 inline unsigned int bit_set_count(int8 v) 49 { 50 return __builtin_popcount(static_cast<uint8>(v)); 51 } 52 53 template<> 54 inline unsigned int bit_set_count(unsigned long v) 55 { 56 return __builtin_popcountl(v); 57 } 58 59 template<> 60 inline unsigned int bit_set_count(signed long v) 61 { 62 return __builtin_popcountl(v); 63 } 64 65 template<> 66 inline unsigned int bit_set_count(unsigned long long v) 67 { 68 return __builtin_popcountll(v); 69 } 70 71 template<> 72 inline unsigned int bit_set_count(signed long long v) 73 { 74 return __builtin_popcountll(v); 75 } 76 77 #else 78 79 template<typename T> 80 inline unsigned int bit_set_count(T v) 81 { 82 static size_t const ONES = ~0; 83 84 v = v - ((v >> 1) & T(ONES/3)); // temp 85 v = (v & T(ONES/15*3)) + ((v >> 2) & T(ONES/15*3)); // temp 86 v = (v + (v >> 4)) & T(ONES/255*15); // temp 87 return (T)(v * T(ONES/255)) >> (sizeof(T)-1)*8; // count 88 } 89 90 #endif 91 92 //TODO: Changed these to uintmax_t when we go to C++11 93 template<int S> 94 inline size_t _mask_over_val(size_t v) 95 { 96 v = _mask_over_val<S/2>(v); 97 v |= v >> S*4; 98 return v; 99 } 100 101 //TODO: Changed these to uintmax_t when we go to C++11 102 template<> 103 inline size_t _mask_over_val<1>(size_t v) 104 { 105 v |= v >> 1; 106 v |= v >> 2; 107 v |= v >> 4; 108 return v; 109 } 110 111 template<typename T> 112 inline T mask_over_val(T v) 113 { 114 return T(_mask_over_val<sizeof(T)>(v)); 115 } 116 117 template<typename T> 118 inline unsigned long next_highest_power2(T v) 119 { 120 return _mask_over_val<sizeof(T)>(v-1)+1; 121 } 122 123 template<typename T> 124 inline unsigned int log_binary(T v) 125 { 126 return bit_set_count(mask_over_val(v))-1; 127 } 128 129 template<typename T> 130 inline T has_zero(const T x) 131 { 132 return (x - T(~T(0)/255)) & ~x & T(~T(0)/255*128); 133 } 134 135 template<typename T> 136 inline T zero_bytes(const T x, unsigned char n) 137 { 138 const T t = T(~T(0)/255*n); 139 return T((has_zero(x^t) >> 7)*n); 140 } 141 142 #if 0 143 inline float float_round(float x, uint32 m) 144 { 145 *reinterpret_cast<unsigned int *>(&x) &= m; 146 return *reinterpret_cast<float *>(&x); 147 } 148 #endif 149 150 }