HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
SYS_BitUtil.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: SYS_BitUtil.h (SYS Library, C++)
7  *
8  * COMMENTS: Functions for fast bit manipulation.
9  *
10  * SYSfirstBitSet - Get the index of the first (lowest-order) bit
11  * equal 1, else -1 if input is zero.
12  * SYSlastBitSet - Get the index of the last (highest-order) bit
13  * equal 1, else -1 if input is zero.
14  * SYScountBitsSet - Counts the number of bits equal to 1
15  * SYSisPow2 - Is it a power of two?
16  * SYSmakePow2 - Round up to nearest power of two
17  * SYSceilLog2 - ceil(log2(n))
18  */
19 
20 #ifndef __SYS_BitUtil__
21 #define __SYS_BitUtil__
22 
23 #include "SYS_Inline.h"
24 #include "SYS_Types.h"
25 
26 #if defined(_MSC_VER)
27  #include <intrin.h>
28 #endif
29 
30 static SYS_FORCE_INLINE int SYSfirstBitSet(uint v)
31 {
32 #if defined(_MSC_VER)
33  unsigned long result;
34  if (_BitScanForward(&result, v))
35  return int(result);
36  return -1;
37 #elif defined(GCC3)
38  int c;
39  asm(
40  "bsf %1, %0\n"
41  "cmove %2, %0\n"
42  : "=r" (c) : "r" (v), "r" (-1));
43  return c;
44 #else
45  if (!v)
46  return -1;
47  int result = 0;
48  if (v & 0x0000FFFF)
49  v &= 0x0000FFFF;
50  else
51  result |= 0x10;
52 
53  if (v & 0x00FF00FF)
54  v &= 0x00FF00FF;
55  else
56  result |= 0x08;
57 
58  if (v & 0x0F0F0F0F)
59  v &= 0x0F0F0F0F;
60  else
61  result |= 0x04;
62 
63  if (v & 0x33333333)
64  v &= 0x33333333;
65  else
66  result |= 0x02;
67 
68  if (v & 0x55555555)
69  v &= 0x55555555;
70  else
71  result |= 0x01;
72 
73  return result;
74 #endif
75 }
76 
77 static SYS_FORCE_INLINE int SYSfirstBitSet(uint64 v)
78 {
79 #if defined(_MSC_VER) && defined(AMD64)
80  unsigned long result;
81  if (_BitScanForward64(&result, v))
82  return int(result);
83  return -1;
84 #elif defined(GCC4) && defined(AMD64)
85  uint64 c;
86  asm(
87  "bsf %1, %0\n"
88  "cmove %2, %0\n"
89  : "=r" (c) : "r" (v), "r" (uint64(-1)));
90  return c;
91 #else
92  // Unfortunately, 64-bit BSF isn't supported on 32-bit CPUs
93  if (v & 0x00000000FFFFFFFFULL)
94  return SYSfirstBitSet(uint(v));
95  int result = SYSfirstBitSet(uint(v>>32));
96  if (result >= 0)
97  result += 32;
98  return result;
99 #endif
100 }
101 
102 static SYS_FORCE_INLINE int SYSfirstBitSet(int v)
103 {
104  return SYSfirstBitSet(uint(v));
105 }
106 
107 static SYS_FORCE_INLINE int SYSfirstBitSet(int64 v)
108 {
109  return SYSfirstBitSet(uint64(v));
110 }
111 
112 #if defined(MBSD)
113 static SYS_FORCE_INLINE int SYSfirstBitSet(size_t v)
114 {
115  return SYSfirstBitSet(uint64(v));
116 }
117 #endif
118 
119 static SYS_FORCE_INLINE int SYSlastBitSet(uint v)
120 {
121 #if defined(_MSC_VER)
122  unsigned long result;
123  if (_BitScanReverse(&result, v))
124  return int(result);
125  return -1;
126 #elif defined(GCC3)
127  int c;
128  asm(
129  "bsr %1, %0\n"
130  "cmove %2, %0\n"
131  : "=r" (c) : "r" (v), "r" (-1));
132  return c;
133 #else
134  if (!v)
135  return -1;
136  int result = 0;
137  if (v & 0xFFFF0000)
138  {
139  v &= 0xFFFF0000;
140  result |= 0x10;
141  }
142  if (v & 0xFF00FF00)
143  {
144  v &= 0xFF00FF00;
145  result |= 0x08;
146  }
147  if (v & 0xF0F0F0F0)
148  {
149  v &= 0xF0F0F0F0;
150  result |= 0x04;
151  }
152  if (v & 0xCCCCCCCC)
153  {
154  v &= 0xCCCCCCCC;
155  result |= 0x02;
156  }
157  if (v & 0xAAAAAAAA)
158  {
159  v &= 0xAAAAAAAA;
160  result |= 0x01;
161  }
162  return result;
163 #endif
164 }
165 
166 static SYS_FORCE_INLINE int SYSlastBitSet(uint64 v)
167 {
168 #if defined(_MSC_VER) && defined(AMD64)
169  unsigned long result;
170  if (_BitScanReverse64(&result, v))
171  return int(result);
172  return -1;
173 #elif defined(GCC4) && defined(AMD64)
174  uint64 c;
175  asm(
176  "bsr %1, %0\n"
177  "cmove %2, %0\n"
178  : "=r" (c) : "r" (v), "r" (uint64(-1)));
179  return c;
180 #else
181  // Unfortunately, 64-bit BSR isn't supported on 32-bit CPUs
182  if (v & 0xFFFFFFFF00000000ULL)
183  return SYSlastBitSet(uint(v>>32)) + 32;
184  return SYSlastBitSet(uint(v));
185 #endif
186 }
187 
188 static SYS_FORCE_INLINE int SYSlastBitSet(int v)
189 {
190  return SYSlastBitSet(uint(v));
191 }
192 
193 static SYS_FORCE_INLINE int SYSlastBitSet(int64 v)
194 {
195  return SYSlastBitSet(uint64(v));
196 }
197 
198 /// For a given bit index, finds the next bit above it that is set and returns
199 /// its index, or -1 if no bits are set. Use SYSfirstBitSet to get a seed bit,
200 /// if iterating over bits from lowest to highest set.
201 template<typename T>
202 static SYS_FORCE_INLINE int SYSnextBitSet(T v, int bit)
203 {
204  bit++;
205  if (bit <= 0 || bit >= std::numeric_limits<T>::digits)
206  return -1;
207 
208  int nbit = SYSfirstBitSet(v >> bit);
209  if (nbit == -1)
210  return -1;
211  return nbit + bit;
212 }
213 
214 #if defined(MBSD)
215 static SYS_FORCE_INLINE int SYSlastBitSet(size_t v)
216 {
217  return SYSlastBitSet(uint64(v));
218 }
219 #endif
220 
221 // Count number of bits set without using a lookup table.
222 // NOTE: There are intrinsics on recent Intel/AMD CPUs to count bits
223 // in hardware (e.g. __builtin_popcount on gcc and __popcnt in
224 // MSVC). However, they're dependent on certain CPU features
225 // being set, so we won't use them here. The code below pipelines
226 // pretty well anyway.
227 static SYS_FORCE_INLINE int SYScountBitsSet(uint v)
228 {
229  v = (v&0x55555555U) + ((v>>1 )&0x55555555U);
230  v = (v&0x33333333U) + ((v>>2 )&0x33333333U);
231  v = (v&0x0F0F0F0FU) + ((v>>4 )&0x0F0F0F0FU);
232  // The additions won't overflow 8 bits, so no more masks
233  // are needed until the end
234  v += (v>>8 );
235  v += (v>>16);
236  return ((int)v)&0xFF;
237 }
238 
239 static SYS_FORCE_INLINE int SYScountBitsSet(uint64 v)
240 {
241  v = (v&0x5555555555555555ULL) + ((v>>1 )&0x5555555555555555ULL);
242  v = (v&0x3333333333333333ULL) + ((v>>2 )&0x3333333333333333ULL);
243  v = (v&0x0F0F0F0F0F0F0F0FULL) + ((v>>4 )&0x0F0F0F0F0F0F0F0FULL);
244  // The additions won't overflow 8 bits, so no more masks
245  // are needed until the end
246  v += (v>>8 );
247  v += (v>>16);
248  v += (v>>32);
249  return ((int)v)&0xFF;
250 }
251 
252 /// NOTE: This does *not* consider zero to be a power of two
253 template <typename T>
254 static SYS_FORCE_INLINE bool SYSisPow2(T v)
255 {
256  return v>0 && !(v&(v-1));
257 }
258 
259 /// Round up to the nearest power of 2 greater (or equal) to v
260 template <typename T>
261 static SYS_FORCE_INLINE T SYSmakePow2(T v)
262 {
263  if (v <= 0)
264  return 1;
265  if (SYSisPow2(v))
266  return v;
267  T v2 = (T(1) << (SYSlastBitSet(v) + 1));
268  return v2;
269 }
270 
271 template <typename T>
272 static SYS_FORCE_INLINE int SYSceilLog2(T v)
273 {
274  if (v <= 0)
275  return 0;
276  bool isPow2 = SYSisPow2(v);
277  return SYSlastBitSet(v) + !isPow2;
278 }
279 
280 // A macro to compute floor(log2(x)) of an 8-bit number at compile time. Useful for computing
281 // bit masks.
282 #define SYS_LOG2F(x) ((((x)>=(1<< 1))?1:0) + (((x)>=(1<< 2))?1:0) + (((x)>=(1<< 3))?1:0) + (((x)>=(1<< 4))?1:0) + \
283  (((x)>=(1<< 5))?1:0) + (((x)>=(1<< 6))?1:0) + (((x)>=(1<< 7))?1:0) + (((x)>=(1<< 8))?1:0))
284 
285 static SYS_FORCE_INLINE int SYSfloorLog2(float v)
286 {
287  if (v <= 0)
288  return 0x80000000;
289  SYS_FPRealUnionF fori;
290  fori.fval = v;
291  int e = (fori.uval >> SYS_FPRealUnionF::MANTISSA_BITS) - 127;
292  // NOTE: Not quite right for denormal numbers or infinities.
293  return e;
294 }
295 static SYS_FORCE_INLINE int SYSfloorLog2(double v)
296 {
297  if (v <= 0)
298  return 0x80000000;
299  SYS_FPRealUnionD fori;
300  fori.fval = v;
301  int e = (fori.uval >> SYS_FPRealUnionD::MANTISSA_BITS) - 1023;
302  // NOTE: Not quite right for denormal numbers or infinities.
303  return e;
304 }
305 static SYS_FORCE_INLINE int SYSroundLog2(float v)
306 {
307  if (v <= 0)
308  return 0x80000000;
309  SYS_FPRealUnionF fori;
310  fori.fval = v;
311  int e = (fori.uval >> SYS_FPRealUnionF::MANTISSA_BITS) - 127;
312  // NOTE: Not quite right for denormal numbers or infinities.
313  // Magic number 3474676 is ceil((2^0.5 - 1)*(2^23))
314  if ((fori.uval & ((1<<SYS_FPRealUnionF::MANTISSA_BITS)-1)) >= 3474676)
315  ++e;
316  return e;
317 }
318 static SYS_FORCE_INLINE int SYSroundLog2(double v)
319 {
320  if (v <= 0)
321  return 0x80000000;
322  SYS_FPRealUnionD fori;
323  fori.fval = v;
324  int e = (fori.uval >> SYS_FPRealUnionD::MANTISSA_BITS) - 1023;
325  // NOTE: Not quite right for denormal numbers or infinities.
326  // Magic number 1865452045155277 is ceil((2^0.5 - 1)*(2^52))
327  if ((fori.uval & ((1ULL<<SYS_FPRealUnionD::MANTISSA_BITS)-1)) >= 1865452045155277ULL)
328  ++e;
329  return e;
330 }
331 static SYS_FORCE_INLINE int SYSceilLog2(float v)
332 {
333  if (v <= 0)
334  return 0x80000000;
335  SYS_FPRealUnionF fori;
336  fori.fval = v;
337  int e = (fori.uval >> SYS_FPRealUnionF::MANTISSA_BITS) - 127;
338  // NOTE: Not quite right for denormal numbers or infinities.
339  if ((fori.uval & ((1<<SYS_FPRealUnionF::MANTISSA_BITS)-1)) != 0)
340  ++e;
341  return e;
342 }
343 static SYS_FORCE_INLINE int SYSceilLog2(double v)
344 {
345  if (v <= 0)
346  return 0x80000000;
347  SYS_FPRealUnionD fori;
348  fori.fval = v;
349  int e = (fori.uval >> SYS_FPRealUnionD::MANTISSA_BITS) - 1023;
350  // NOTE: Not quite right for denormal numbers or infinities.
351  if ((fori.uval & ((1ULL<<SYS_FPRealUnionD::MANTISSA_BITS)-1)) != 0)
352  ++e;
353  return e;
354 }
355 
356 static SYS_FORCE_INLINE float SYSintExp2AsFloat(int e)
357 {
358  // Avoid include for SYSclamp by doing it manually
359  if (e < -127)
360  e = -127;
361  else if (e > 128)
362  e = 128;
363  SYS_FPRealUnionF fori;
364  fori.uval = (127+e)<<SYS_FPRealUnionF::MANTISSA_BITS;
365  return fori.fval;
366 }
367 
368 static SYS_FORCE_INLINE double SYSintExp2AsDouble(int e)
369 {
370  // Avoid include for SYSclamp by doing it manually
371  if (e < -1023)
372  e = -1023;
373  else if (e > 1024)
374  e = 1024;
375  SYS_FPRealUnionD fori;
377  return fori.fval;
378 }
379 
380 #endif
const GLdouble * v
Definition: glcorearb.h:836
GLfloat GLfloat GLfloat v2
Definition: glcorearb.h:817
long long int64
Definition: SYS_Types.h:107
unsigned long long uint64
Definition: SYS_Types.h:108
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
unsigned int uint
Definition: SYS_Types.h:40
typedef int
Definition: png.h:1175