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