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>
bit_set_count(T v)36 inline unsigned int bit_set_count(T v)
37 {
38 return __builtin_popcount(v);
39 }
40
41 template<>
bit_set_count(int16 v)42 inline unsigned int bit_set_count(int16 v)
43 {
44 return __builtin_popcount(static_cast<uint16>(v));
45 }
46
47 template<>
bit_set_count(int8 v)48 inline unsigned int bit_set_count(int8 v)
49 {
50 return __builtin_popcount(static_cast<uint8>(v));
51 }
52
53 template<>
bit_set_count(unsigned long v)54 inline unsigned int bit_set_count(unsigned long v)
55 {
56 return __builtin_popcountl(v);
57 }
58
59 template<>
bit_set_count(signed long v)60 inline unsigned int bit_set_count(signed long v)
61 {
62 return __builtin_popcountl(v);
63 }
64
65 template<>
bit_set_count(unsigned long long v)66 inline unsigned int bit_set_count(unsigned long long v)
67 {
68 return __builtin_popcountll(v);
69 }
70
71 template<>
bit_set_count(signed long long v)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>
_mask_over_val(size_t v)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>
mask_over_val(T v)112 inline T mask_over_val(T v)
113 {
114 return T(_mask_over_val<sizeof(T)>(v));
115 }
116
117 template<typename T>
next_highest_power2(T v)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>
log_binary(T v)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>
has_zero(const T x)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>
zero_bytes(const T x,unsigned char n)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 }
151