1 #ifndef _DEINT32_H
2 #define _DEINT32_H
3 /*-------------------------------------------------------------------------
4 * drawElements Base Portability Library
5 * -------------------------------------
6 *
7 * Copyright 2014 The Android Open Source Project
8 *
9 * Licensed under the Apache License, Version 2.0 (the "License");
10 * you may not use this file except in compliance with the License.
11 * You may obtain a copy of the License at
12 *
13 * http://www.apache.org/licenses/LICENSE-2.0
14 *
15 * Unless required by applicable law or agreed to in writing, software
16 * distributed under the License is distributed on an "AS IS" BASIS,
17 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
18 * See the License for the specific language governing permissions and
19 * limitations under the License.
20 *
21 *//*!
22 * \file
23 * \brief 32-bit integer math.
24 *//*--------------------------------------------------------------------*/
25
26 #include "deDefs.h"
27
28
29 #if (DE_COMPILER == DE_COMPILER_MSC)
30 # include <intrin.h>
31 #endif
32
33 DE_BEGIN_EXTERN_C
34
35 enum
36 {
37 DE_RCP_FRAC_BITS = 30 /*!< Number of fractional bits in deRcp32() result. */
38 };
39
40 void deRcp32 (deUint32 a, deUint32* rcp, int* exp);
41 void deInt32_computeLUTs (void);
42 void deInt32_selfTest (void);
43
44 /*--------------------------------------------------------------------*//*!
45 * \brief Compute the absolute of an int.
46 * \param a Input value.
47 * \return Absolute of the input value.
48 *
49 * \note The input 0x80000000u (for which the abs value cannot be
50 * represented), is asserted and returns the value itself.
51 *//*--------------------------------------------------------------------*/
deAbs32(int a)52 DE_INLINE int deAbs32 (int a)
53 {
54 DE_ASSERT((unsigned int) a != 0x80000000u);
55 return (a < 0) ? -a : a;
56 }
57
58 /*--------------------------------------------------------------------*//*!
59 * \brief Compute the signed minimum of two values.
60 * \param a First input value.
61 * \param b Second input value.
62 * \return The smallest of the two input values.
63 *//*--------------------------------------------------------------------*/
deMin32(int a,int b)64 DE_INLINE int deMin32 (int a, int b)
65 {
66 return (a <= b) ? a : b;
67 }
68
69 /*--------------------------------------------------------------------*//*!
70 * \brief Compute the signed maximum of two values.
71 * \param a First input value.
72 * \param b Second input value.
73 * \return The largest of the two input values.
74 *//*--------------------------------------------------------------------*/
deMax32(int a,int b)75 DE_INLINE int deMax32 (int a, int b)
76 {
77 return (a >= b) ? a : b;
78 }
79
80 /*--------------------------------------------------------------------*//*!
81 * \brief Compute the unsigned minimum of two values.
82 * \param a First input value.
83 * \param b Second input value.
84 * \return The smallest of the two input values.
85 *//*--------------------------------------------------------------------*/
deMinu32(deUint32 a,deUint32 b)86 DE_INLINE deUint32 deMinu32 (deUint32 a, deUint32 b)
87 {
88 return (a <= b) ? a : b;
89 }
90
91 /*--------------------------------------------------------------------*//*!
92 * \brief Compute the unsigned minimum of two values.
93 * \param a First input value.
94 * \param b Second input value.
95 * \return The smallest of the two input values.
96 *//*--------------------------------------------------------------------*/
deMinu64(deUint64 a,deUint64 b)97 DE_INLINE deUint64 deMinu64 (deUint64 a, deUint64 b)
98 {
99 return (a <= b) ? a : b;
100 }
101
102 /*--------------------------------------------------------------------*//*!
103 * \brief Compute the unsigned maximum of two values.
104 * \param a First input value.
105 * \param b Second input value.
106 * \return The largest of the two input values.
107 *//*--------------------------------------------------------------------*/
deMaxu32(deUint32 a,deUint32 b)108 DE_INLINE deUint32 deMaxu32 (deUint32 a, deUint32 b)
109 {
110 return (a >= b) ? a : b;
111 }
112
113 /*--------------------------------------------------------------------*//*!
114 * \brief Check if a value is in the <b>inclusive<b> range [mn, mx].
115 * \param a Value to check for range.
116 * \param mn Range minimum value.
117 * \param mx Range maximum value.
118 * \return True if (a >= mn) and (a <= mx), false otherwise.
119 *
120 * \see deInBounds32()
121 *//*--------------------------------------------------------------------*/
deInRange32(int a,int mn,int mx)122 DE_INLINE deBool deInRange32 (int a, int mn, int mx)
123 {
124 return (a >= mn) && (a <= mx);
125 }
126
127 /*--------------------------------------------------------------------*//*!
128 * \brief Check if a value is in the half-inclusive bounds [mn, mx[.
129 * \param a Value to check for range.
130 * \param mn Range minimum value.
131 * \param mx Range maximum value.
132 * \return True if (a >= mn) and (a < mx), false otherwise.
133 *
134 * \see deInRange32()
135 *//*--------------------------------------------------------------------*/
deInBounds32(int a,int mn,int mx)136 DE_INLINE deBool deInBounds32 (int a, int mn, int mx)
137 {
138 return (a >= mn) && (a < mx);
139 }
140
141 /*--------------------------------------------------------------------*//*!
142 * \brief Clamp a value into the range [mn, mx].
143 * \param a Value to clamp.
144 * \param mn Minimum value.
145 * \param mx Maximum value.
146 * \return The clamped value in [mn, mx] range.
147 *//*--------------------------------------------------------------------*/
deClamp32(int a,int mn,int mx)148 DE_INLINE int deClamp32 (int a, int mn, int mx)
149 {
150 DE_ASSERT(mn <= mx);
151 if (a < mn) return mn;
152 if (a > mx) return mx;
153 return a;
154 }
155
156 /*--------------------------------------------------------------------*//*!
157 * \brief Get the sign of an integer.
158 * \param a Input value.
159 * \return +1 if a>0, 0 if a==0, -1 if a<0.
160 *//*--------------------------------------------------------------------*/
deSign32(int a)161 DE_INLINE int deSign32 (int a)
162 {
163 if (a > 0) return +1;
164 if (a < 0) return -1;
165 return 0;
166 }
167
168 /*--------------------------------------------------------------------*//*!
169 * \brief Extract the sign bit of a.
170 * \param a Input value.
171 * \return 0x80000000 if a<0, 0 otherwise.
172 *//*--------------------------------------------------------------------*/
deSignBit32(deInt32 a)173 DE_INLINE deInt32 deSignBit32 (deInt32 a)
174 {
175 return (deInt32)((deUint32)a & 0x80000000u);
176 }
177
178 /*--------------------------------------------------------------------*//*!
179 * \brief Integer rotate right.
180 * \param val Value to rotate.
181 * \param r Number of bits to rotate (in range [0, 32]).
182 * \return The rotated value.
183 *//*--------------------------------------------------------------------*/
deRor32(int val,int r)184 DE_INLINE int deRor32 (int val, int r)
185 {
186 DE_ASSERT(r >= 0 && r <= 32);
187 if (r == 0 || r == 32)
188 return val;
189 else
190 return (int)(((deUint32)val >> r) | ((deUint32)val << (32-r)));
191 }
192
193 /*--------------------------------------------------------------------*//*!
194 * \brief Integer rotate left.
195 * \param val Value to rotate.
196 * \param r Number of bits to rotate (in range [0, 32]).
197 * \return The rotated value.
198 *//*--------------------------------------------------------------------*/
deRol32(int val,int r)199 DE_INLINE int deRol32 (int val, int r)
200 {
201 DE_ASSERT(r >= 0 && r <= 32);
202 if (r == 0 || r == 32)
203 return val;
204 else
205 return (int)(((deUint32)val << r) | ((deUint32)val >> (32-r)));
206 }
207
208 /*--------------------------------------------------------------------*//*!
209 * \brief Check if a value is a power-of-two.
210 * \param a Input value.
211 * \return True if input is a power-of-two value, false otherwise.
212 *
213 * \note Also returns true for zero.
214 *//*--------------------------------------------------------------------*/
deIsPowerOfTwo32(int a)215 DE_INLINE deBool deIsPowerOfTwo32 (int a)
216 {
217 return ((a & (a - 1)) == 0);
218 }
219
220 /*--------------------------------------------------------------------*//*!
221 * \brief Check if a value is a power-of-two.
222 * \param a Input value.
223 * \return True if input is a power-of-two value, false otherwise.
224 *
225 * \note Also returns true for zero.
226 *//*--------------------------------------------------------------------*/
deIsPowerOfTwo64(deUint64 a)227 DE_INLINE deBool deIsPowerOfTwo64 (deUint64 a)
228 {
229 return ((a & (a - 1ull)) == 0);
230 }
231
232 /*--------------------------------------------------------------------*//*!
233 * \brief Check if a value is a power-of-two.
234 * \param a Input value.
235 * \return True if input is a power-of-two value, false otherwise.
236 *
237 * \note Also returns true for zero.
238 *//*--------------------------------------------------------------------*/
deIsPowerOfTwoSize(size_t a)239 DE_INLINE deBool deIsPowerOfTwoSize (size_t a)
240 {
241 #if (DE_PTR_SIZE == 4)
242 return deIsPowerOfTwo32(a);
243 #elif (DE_PTR_SIZE == 8)
244 return deIsPowerOfTwo64(a);
245 #else
246 # error "Invalid DE_PTR_SIZE"
247 #endif
248 }
249
250 /*--------------------------------------------------------------------*//*!
251 * \brief Roud a value up to a power-of-two.
252 * \param a Input value.
253 * \return Smallest power-of-two value that is greater or equal to an input value.
254 *//*--------------------------------------------------------------------*/
deSmallestGreaterOrEquallPowerOfTwoU32(deUint32 a)255 DE_INLINE deUint32 deSmallestGreaterOrEquallPowerOfTwoU32 (deUint32 a)
256 {
257 --a;
258 a |= a >> 1u;
259 a |= a >> 2u;
260 a |= a >> 4u;
261 a |= a >> 8u;
262 a |= a >> 16u;
263 return ++a;
264 }
265
266 /*--------------------------------------------------------------------*//*!
267 * \brief Roud a value up to a power-of-two.
268 * \param a Input value.
269 * \return Smallest power-of-two value that is greater or equal to an input value.
270 *//*--------------------------------------------------------------------*/
deSmallestGreaterOrEquallPowerOfTwoU64(deUint64 a)271 DE_INLINE deUint64 deSmallestGreaterOrEquallPowerOfTwoU64 (deUint64 a)
272 {
273 --a;
274 a |= a >> 1u;
275 a |= a >> 2u;
276 a |= a >> 4u;
277 a |= a >> 8u;
278 a |= a >> 16u;
279 a |= a >> 32u;
280 return ++a;
281 }
282
283 /*--------------------------------------------------------------------*//*!
284 * \brief Roud a value up to a power-of-two.
285 * \param a Input value.
286 * \return Smallest power-of-two value that is greater or equal to an input value.
287 *//*--------------------------------------------------------------------*/
deSmallestGreaterOrEquallPowerOfTwoSize(size_t a)288 DE_INLINE size_t deSmallestGreaterOrEquallPowerOfTwoSize (size_t a)
289 {
290 #if (DE_PTR_SIZE == 4)
291 return deSmallestGreaterOrEquallPowerOfTwoU32(a);
292 #elif (DE_PTR_SIZE == 8)
293 return deSmallestGreaterOrEquallPowerOfTwoU64(a);
294 #else
295 # error "Invalid DE_PTR_SIZE"
296 #endif
297 }
298
299 /*--------------------------------------------------------------------*//*!
300 * \brief Check if an integer is aligned to given power-of-two size.
301 * \param a Input value.
302 * \param align Alignment to check for.
303 * \return True if input is aligned, false otherwise.
304 *//*--------------------------------------------------------------------*/
deIsAligned32(int a,int align)305 DE_INLINE deBool deIsAligned32 (int a, int align)
306 {
307 DE_ASSERT(deIsPowerOfTwo32(align));
308 return ((a & (align-1)) == 0);
309 }
310
311 /*--------------------------------------------------------------------*//*!
312 * \brief Check if an integer is aligned to given power-of-two size.
313 * \param a Input value.
314 * \param align Alignment to check for.
315 * \return True if input is aligned, false otherwise.
316 *//*--------------------------------------------------------------------*/
deIsAligned64(deInt64 a,deInt64 align)317 DE_INLINE deBool deIsAligned64 (deInt64 a, deInt64 align)
318 {
319 DE_ASSERT(deIsPowerOfTwo64(align));
320 return ((a & (align-1)) == 0);
321 }
322
323 /*--------------------------------------------------------------------*//*!
324 * \brief Check if a pointer is aligned to given power-of-two size.
325 * \param ptr Input pointer.
326 * \param align Alignment to check for (power-of-two).
327 * \return True if input is aligned, false otherwise.
328 *//*--------------------------------------------------------------------*/
deIsAlignedPtr(const void * ptr,deUintptr align)329 DE_INLINE deBool deIsAlignedPtr (const void* ptr, deUintptr align)
330 {
331 DE_ASSERT((align & (align-1)) == 0); /* power of two */
332 return (((deUintptr)ptr & (align-1)) == 0);
333 }
334
335 /*--------------------------------------------------------------------*//*!
336 * \brief Align an integer to given power-of-two size.
337 * \param val Input to align.
338 * \param align Alignment to check for (power-of-two).
339 * \return The aligned value (larger or equal to input).
340 *//*--------------------------------------------------------------------*/
deAlign32(deInt32 val,deInt32 align)341 DE_INLINE deInt32 deAlign32 (deInt32 val, deInt32 align)
342 {
343 DE_ASSERT(deIsPowerOfTwo32(align));
344 return (val + align - 1) & ~(align - 1);
345 }
346
347 /*--------------------------------------------------------------------*//*!
348 * \brief Align an integer to given power-of-two size.
349 * \param val Input to align.
350 * \param align Alignment to check for (power-of-two).
351 * \return The aligned value (larger or equal to input).
352 *//*--------------------------------------------------------------------*/
deAlign64(deInt64 val,deInt64 align)353 DE_INLINE deInt64 deAlign64 (deInt64 val, deInt64 align)
354 {
355 DE_ASSERT(deIsPowerOfTwo64(align));
356 return (val + align - 1) & ~(align - 1);
357 }
358
359 /*--------------------------------------------------------------------*//*!
360 * \brief Align a pointer to given power-of-two size.
361 * \param ptr Input pointer to align.
362 * \param align Alignment to check for (power-of-two).
363 * \return The aligned pointer (larger or equal to input).
364 *//*--------------------------------------------------------------------*/
deAlignPtr(void * ptr,deUintptr align)365 DE_INLINE void* deAlignPtr (void* ptr, deUintptr align)
366 {
367 deUintptr val = (deUintptr)ptr;
368 DE_ASSERT((align & (align-1)) == 0); /* power of two */
369 return (void*)((val + align - 1) & ~(align - 1));
370 }
371
372 /*--------------------------------------------------------------------*//*!
373 * \brief Align a size_t value to given power-of-two size.
374 * \param ptr Input value to align.
375 * \param align Alignment to check for (power-of-two).
376 * \return The aligned size (larger or equal to input).
377 *//*--------------------------------------------------------------------*/
deAlignSize(size_t val,size_t align)378 DE_INLINE size_t deAlignSize (size_t val, size_t align)
379 {
380 DE_ASSERT(deIsPowerOfTwoSize(align));
381 return (val + align - 1) & ~(align - 1);
382 }
383
384 extern const deInt8 g_clzLUT[256];
385
386 /*--------------------------------------------------------------------*//*!
387 * \brief Compute number of leading zeros in an integer.
388 * \param a Input value.
389 * \return The number of leading zero bits in the input.
390 *//*--------------------------------------------------------------------*/
deClz32(deUint32 a)391 DE_INLINE int deClz32 (deUint32 a)
392 {
393 #if (DE_COMPILER == DE_COMPILER_MSC)
394 unsigned long i;
395 if (_BitScanReverse(&i, (unsigned long)a) == 0)
396 return 32;
397 else
398 return 31-i;
399 #elif (DE_COMPILER == DE_COMPILER_GCC) || (DE_COMPILER == DE_COMPILER_CLANG)
400 if (a == 0)
401 return 32;
402 else
403 return __builtin_clz((unsigned int)a);
404 #else
405 if ((a & 0xFF000000u) != 0)
406 return (int)g_clzLUT[a >> 24];
407 if ((a & 0x00FF0000u) != 0)
408 return 8 + (int)g_clzLUT[a >> 16];
409 if ((a & 0x0000FF00u) != 0)
410 return 16 + (int)g_clzLUT[a >> 8];
411 return 24 + (int)g_clzLUT[a];
412 #endif
413 }
414
415 extern const deInt8 g_ctzLUT[256];
416
417 /*--------------------------------------------------------------------*//*!
418 * \brief Compute number of trailing zeros in an integer.
419 * \param a Input value.
420 * \return The number of trailing zero bits in the input.
421 *//*--------------------------------------------------------------------*/
deCtz32(deUint32 a)422 DE_INLINE int deCtz32 (deUint32 a)
423 {
424 #if (DE_COMPILER == DE_COMPILER_MSC)
425 unsigned long i;
426 if (_BitScanForward(&i, (unsigned long)a) == 0)
427 return 32;
428 else
429 return i;
430 #elif (DE_COMPILER == DE_COMPILER_GCC) || (DE_COMPILER == DE_COMPILER_CLANG)
431 if (a == 0)
432 return 32;
433 else
434 return __builtin_ctz((unsigned int)a);
435 #else
436 if ((a & 0x00FFFFFFu) == 0)
437 return (int)g_ctzLUT[a >> 24] + 24;
438 if ((a & 0x0000FFFFu) == 0)
439 return (int)g_ctzLUT[(a >> 16) & 0xffu] + 16;
440 if ((a & 0x000000FFu) == 0)
441 return (int)g_ctzLUT[(a >> 8) & 0xffu] + 8;
442 return (int)g_ctzLUT[a & 0xffu];
443 #endif
444 }
445
446 /*--------------------------------------------------------------------*//*!
447 * \brief Compute integer 'floor' of 'log2' for a positive integer.
448 * \param a Input value.
449 * \return floor(log2(a)).
450 *//*--------------------------------------------------------------------*/
deLog2Floor32(deInt32 a)451 DE_INLINE int deLog2Floor32 (deInt32 a)
452 {
453 DE_ASSERT(a > 0);
454 return 31 - deClz32((deUint32)a);
455 }
456
457 /*--------------------------------------------------------------------*//*!
458 * \brief Compute integer 'ceil' of 'log2' for a positive integer.
459 * \param a Input value.
460 * \return ceil(log2(a)).
461 *//*--------------------------------------------------------------------*/
deLog2Ceil32(deInt32 a)462 DE_INLINE int deLog2Ceil32 (deInt32 a)
463 {
464 int log2floor = deLog2Floor32(a);
465 if (deIsPowerOfTwo32(a))
466 return log2floor;
467 else
468 return log2floor+1;
469 }
470
471 /*--------------------------------------------------------------------*//*!
472 * \brief Compute the bit population count of an integer.
473 * \param a Input value.
474 * \return The number of one bits in the input.
475 *//*--------------------------------------------------------------------*/
dePop32(deUint32 a)476 DE_INLINE int dePop32 (deUint32 a)
477 {
478 deUint32 mask0 = 0x55555555; /* 1-bit values. */
479 deUint32 mask1 = 0x33333333; /* 2-bit values. */
480 deUint32 mask2 = 0x0f0f0f0f; /* 4-bit values. */
481 deUint32 mask3 = 0x00ff00ff; /* 8-bit values. */
482 deUint32 mask4 = 0x0000ffff; /* 16-bit values. */
483 deUint32 t = (deUint32)a;
484 t = (t & mask0) + ((t>>1) & mask0);
485 t = (t & mask1) + ((t>>2) & mask1);
486 t = (t & mask2) + ((t>>4) & mask2);
487 t = (t & mask3) + ((t>>8) & mask3);
488 t = (t & mask4) + (t>>16);
489 return (int)t;
490 }
491
dePop64(deUint64 a)492 DE_INLINE int dePop64 (deUint64 a)
493 {
494 return dePop32((deUint32)(a & 0xffffffffull)) + dePop32((deUint32)(a >> 32));
495 }
496
497 /*--------------------------------------------------------------------*//*!
498 * \brief Reverse bytes in 32-bit integer (for example MSB -> LSB).
499 * \param a Input value.
500 * \return The input with bytes reversed
501 *//*--------------------------------------------------------------------*/
deReverseBytes32(deUint32 v)502 DE_INLINE deUint32 deReverseBytes32 (deUint32 v)
503 {
504 deUint32 b0 = v << 24;
505 deUint32 b1 = (v & 0x0000ff00) << 8;
506 deUint32 b2 = (v & 0x00ff0000) >> 8;
507 deUint32 b3 = v >> 24;
508 return b0|b1|b2|b3;
509 }
510
511 /*--------------------------------------------------------------------*//*!
512 * \brief Reverse bytes in 16-bit integer (for example MSB -> LSB).
513 * \param a Input value.
514 * \return The input with bytes reversed
515 *//*--------------------------------------------------------------------*/
deReverseBytes16(deUint16 v)516 DE_INLINE deUint16 deReverseBytes16 (deUint16 v)
517 {
518 return (deUint16)((v << 8) | (v >> 8));
519 }
520
deSafeMul32(deInt32 a,deInt32 b)521 DE_INLINE deInt32 deSafeMul32 (deInt32 a, deInt32 b)
522 {
523 deInt32 res = a * b;
524 DE_ASSERT((deInt64)res == ((deInt64)a * (deInt64)b));
525 return res;
526 }
527
deSafeAdd32(deInt32 a,deInt32 b)528 DE_INLINE deInt32 deSafeAdd32 (deInt32 a, deInt32 b)
529 {
530 DE_ASSERT((deInt64)a + (deInt64)b == (deInt64)(a + b));
531 return (a + b);
532 }
533
deDivRoundUp32(deInt32 a,deInt32 b)534 DE_INLINE deInt32 deDivRoundUp32 (deInt32 a, deInt32 b)
535 {
536 return a/b + ((a%b) ? 1 : 0);
537 }
538
539 /*--------------------------------------------------------------------*//*!
540 * \brief Return value a rounded up to nearest multiple of b.
541 * \param a Input value.
542 * \param b Alignment to use.
543 * \return a if already aligned to b, otherwise next largest aligned value
544 *//*--------------------------------------------------------------------*/
deRoundUp32(deInt32 a,deInt32 b)545 DE_INLINE deInt32 deRoundUp32(deInt32 a, deInt32 b)
546 {
547 deInt32 d = a / b;
548 return d * b == a ? a : (d + 1) * b;
549 }
550
551 /* \todo [petri] Move to deInt64.h? */
552
deMulAsr32(deInt32 a,deInt32 b,int shift)553 DE_INLINE deInt32 deMulAsr32 (deInt32 a, deInt32 b, int shift)
554 {
555 return (deInt32)(((deInt64)a * (deInt64)b) >> shift);
556 }
557
deSafeMulAsr32(deInt32 a,deInt32 b,int shift)558 DE_INLINE deInt32 deSafeMulAsr32 (deInt32 a, deInt32 b, int shift)
559 {
560 deInt64 res = ((deInt64)a * (deInt64)b) >> shift;
561 DE_ASSERT(res == (deInt64)(deInt32)res);
562 return (deInt32)res;
563 }
564
deSafeMuluAsr32(deUint32 a,deUint32 b,int shift)565 DE_INLINE deUint32 deSafeMuluAsr32 (deUint32 a, deUint32 b, int shift)
566 {
567 deUint64 res = ((deUint64)a * (deUint64)b) >> shift;
568 DE_ASSERT(res == (deUint64)(deUint32)res);
569 return (deUint32)res;
570 }
571
deMul32_32_64(deInt32 a,deInt32 b)572 DE_INLINE deInt64 deMul32_32_64 (deInt32 a, deInt32 b)
573 {
574 return ((deInt64)a * (deInt64)b);
575 }
576
deAbs64(deInt64 a)577 DE_INLINE deInt64 deAbs64 (deInt64 a)
578 {
579 DE_ASSERT((deUint64) a != 0x8000000000000000LL);
580 return (a >= 0) ? a : -a;
581 }
582
deClz64(deUint64 a)583 DE_INLINE int deClz64 (deUint64 a)
584 {
585 if ((a >> 32) != 0)
586 return deClz32((deUint32)(a >> 32));
587 return deClz32((deUint32)a) + 32;
588 }
589
590 /* Common hash & compare functions. */
591
deInt32Hash(deInt32 a)592 DE_INLINE deUint32 deInt32Hash (deInt32 a)
593 {
594 /* From: http://www.concentric.net/~Ttwang/tech/inthash.htm */
595 deUint32 key = (deUint32)a;
596 key = (key ^ 61) ^ (key >> 16);
597 key = key + (key << 3);
598 key = key ^ (key >> 4);
599 key = key * 0x27d4eb2d; /* prime/odd constant */
600 key = key ^ (key >> 15);
601 return key;
602 }
603
deInt64Hash(deInt64 a)604 DE_INLINE deUint32 deInt64Hash (deInt64 a)
605 {
606 /* From: http://www.concentric.net/~Ttwang/tech/inthash.htm */
607 deUint64 key = (deUint64)a;
608 key = (~key) + (key << 21); /* key = (key << 21) - key - 1; */
609 key = key ^ (key >> 24);
610 key = (key + (key << 3)) + (key << 8); /* key * 265 */
611 key = key ^ (key >> 14);
612 key = (key + (key << 2)) + (key << 4); /* key * 21 */
613 key = key ^ (key >> 28);
614 key = key + (key << 31);
615 return (deUint32)key;
616 }
617
deInt16Hash(deInt16 v)618 DE_INLINE deUint32 deInt16Hash (deInt16 v) { return deInt32Hash(v); }
deUint16Hash(deUint16 v)619 DE_INLINE deUint32 deUint16Hash (deUint16 v) { return deInt32Hash((deInt32)v); }
deUint32Hash(deUint32 v)620 DE_INLINE deUint32 deUint32Hash (deUint32 v) { return deInt32Hash((deInt32)v); }
deUint64Hash(deUint64 v)621 DE_INLINE deUint32 deUint64Hash (deUint64 v) { return deInt64Hash((deInt64)v); }
622
deInt16Equal(deInt16 a,deInt16 b)623 DE_INLINE deBool deInt16Equal (deInt16 a, deInt16 b) { return (a == b); }
deUint16Equal(deUint16 a,deUint16 b)624 DE_INLINE deBool deUint16Equal (deUint16 a, deUint16 b) { return (a == b); }
deInt32Equal(deInt32 a,deInt32 b)625 DE_INLINE deBool deInt32Equal (deInt32 a, deInt32 b) { return (a == b); }
deUint32Equal(deUint32 a,deUint32 b)626 DE_INLINE deBool deUint32Equal (deUint32 a, deUint32 b) { return (a == b); }
deInt64Equal(deInt64 a,deInt64 b)627 DE_INLINE deBool deInt64Equal (deInt64 a, deInt64 b) { return (a == b); }
deUint64Equal(deUint64 a,deUint64 b)628 DE_INLINE deBool deUint64Equal (deUint64 a, deUint64 b) { return (a == b); }
629
dePointerHash(const void * ptr)630 DE_INLINE deUint32 dePointerHash (const void* ptr)
631 {
632 deUintptr val = (deUintptr)ptr;
633 #if (DE_PTR_SIZE == 4)
634 return deInt32Hash((int)val);
635 #elif (DE_PTR_SIZE == 8)
636 return deInt64Hash((deInt64)val);
637 #else
638 # error Unsupported pointer size.
639 #endif
640 }
641
dePointerEqual(const void * a,const void * b)642 DE_INLINE deBool dePointerEqual (const void* a, const void* b)
643 {
644 return (a == b);
645 }
646
647 /**
648 * \brief Modulo that generates the same sign as divisor and rounds toward
649 * negative infinity -- assuming c99 %-operator.
650 */
deInt32ModF(deInt32 n,deInt32 d)651 DE_INLINE deInt32 deInt32ModF (deInt32 n, deInt32 d)
652 {
653 deInt32 r = n%d;
654 if ((r > 0 && d < 0) || (r < 0 && d > 0)) r = r+d;
655 return r;
656 }
657
deInt64InInt32Range(deInt64 x)658 DE_INLINE deBool deInt64InInt32Range (deInt64 x)
659 {
660 return ((x >= (((deInt64)((deInt32)(-0x7FFFFFFF - 1))))) && (x <= ((1ll<<31)-1)));
661 }
662
663
deBitMask32(int leastSignificantBitNdx,int numBits)664 DE_INLINE deUint32 deBitMask32 (int leastSignificantBitNdx, int numBits)
665 {
666 DE_ASSERT(deInRange32(leastSignificantBitNdx, 0, 32));
667 DE_ASSERT(deInRange32(numBits, 0, 32));
668 DE_ASSERT(deInRange32(leastSignificantBitNdx+numBits, 0, 32));
669
670 if (numBits < 32 && leastSignificantBitNdx < 32)
671 return ((1u<<numBits)-1u) << (deUint32)leastSignificantBitNdx;
672 else if (numBits == 0 && leastSignificantBitNdx == 32)
673 return 0u;
674 else
675 {
676 DE_ASSERT(numBits == 32 && leastSignificantBitNdx == 0);
677 return 0xFFFFFFFFu;
678 }
679 }
680
deUintMaxValue32(int numBits)681 DE_INLINE deUint32 deUintMaxValue32 (int numBits)
682 {
683 DE_ASSERT(deInRange32(numBits, 1, 32));
684 if (numBits < 32)
685 return ((1u<<numBits)-1u);
686 else
687 return 0xFFFFFFFFu;
688 }
689
deIntMaxValue32(int numBits)690 DE_INLINE deInt32 deIntMaxValue32 (int numBits)
691 {
692 DE_ASSERT(deInRange32(numBits, 1, 32));
693 if (numBits < 32)
694 return ((deInt32)1 << (numBits - 1)) - 1;
695 else
696 {
697 /* avoid undefined behavior of int overflow when shifting */
698 return 0x7FFFFFFF;
699 }
700 }
701
deIntMinValue32(int numBits)702 DE_INLINE deInt32 deIntMinValue32 (int numBits)
703 {
704 DE_ASSERT(deInRange32(numBits, 1, 32));
705 if (numBits < 32)
706 return -((deInt32)1 << (numBits - 1));
707 else
708 {
709 /* avoid undefined behavior of int overflow when shifting */
710 return (deInt32)(-0x7FFFFFFF - 1);
711 }
712 }
713
deSignExtendTo32(deInt32 value,int numBits)714 DE_INLINE deInt32 deSignExtendTo32 (deInt32 value, int numBits)
715 {
716 DE_ASSERT(deInRange32(numBits, 1, 32));
717
718 if (numBits < 32)
719 {
720 deBool signSet = ((deUint32)value & (1u<<(numBits-1))) != 0;
721 deUint32 signMask = deBitMask32(numBits, 32-numBits);
722
723 DE_ASSERT(((deUint32)value & signMask) == 0u);
724
725 return (deInt32)((deUint32)value | (signSet ? signMask : 0u));
726 }
727 else
728 return value;
729 }
730
deIntIsPow2(int powerOf2)731 DE_INLINE int deIntIsPow2(int powerOf2)
732 {
733 if (powerOf2 <= 0)
734 return 0;
735 return (powerOf2 & (powerOf2 - (int)1)) == (int)0;
736 }
737
deIntRoundToPow2(int number,int powerOf2)738 DE_INLINE int deIntRoundToPow2(int number, int powerOf2)
739 {
740 DE_ASSERT(deIntIsPow2(powerOf2));
741 return (number + (int)powerOf2 - (int)1) & (int)(~(powerOf2 - 1));
742 }
743
744 /*--------------------------------------------------------------------*//*!
745 * \brief Destructively loop over all of the bits in a mask as in:
746 *
747 * while (mymask) {
748 * int i = bitScan(&mymask);
749 * ... process element i
750 * }
751 * \param mask mask value, it will remove LSB that is enabled.
752 * \return LSB position that was enabled before overwriting the mask.
753 *//*--------------------------------------------------------------------*/
754 DE_INLINE deInt32
deInt32BitScan(deInt32 * mask)755 deInt32BitScan(deInt32 *mask)
756 {
757 const deInt32 i = deCtz32(*mask);
758 if (i == 32)
759 return i;
760 *mask ^= (1u << i);
761 return i;
762 }
763
764 DE_END_EXTERN_C
765
766 #endif /* _DEINT32_H */
767