Home | History | Annotate | Download | only in debase
      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				(deUint32 a, deUint32* 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  *//*--------------------------------------------------------------------*/
     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  *//*--------------------------------------------------------------------*/
     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  *//*--------------------------------------------------------------------*/
     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  *//*--------------------------------------------------------------------*/
     85 DE_INLINE deUint32 deMinu32 (deUint32 a, deUint32 b)
     86 {
     87 	return (a <= b) ? a : b;
     88 }
     89 
     90 /*--------------------------------------------------------------------*//*!
     91  * \brief Compute the unsigned maximum of two values.
     92  * \param a	First input value.
     93  * \param b Second input value.
     94  * \return The largest of the two input values.
     95  *//*--------------------------------------------------------------------*/
     96 DE_INLINE deUint32 deMaxu32 (deUint32 a, deUint32 b)
     97 {
     98 	return (a >= b) ? a : b;
     99 }
    100 
    101 /*--------------------------------------------------------------------*//*!
    102  * \brief Check if a value is in the <b>inclusive<b> range [mn, mx].
    103  * \param a		Value to check for range.
    104  * \param mn	Range minimum value.
    105  * \param mx	Range maximum value.
    106  * \return True if (a >= mn) and (a <= mx), false otherwise.
    107  *
    108  * \see deInBounds32()
    109  *//*--------------------------------------------------------------------*/
    110 DE_INLINE deBool deInRange32 (int a, int mn, int mx)
    111 {
    112 	return (a >= mn) && (a <= mx);
    113 }
    114 
    115 /*--------------------------------------------------------------------*//*!
    116  * \brief Check if a value is in the half-inclusive bounds [mn, mx[.
    117  * \param a		Value to check for range.
    118  * \param mn	Range minimum value.
    119  * \param mx	Range maximum value.
    120  * \return True if (a >= mn) and (a < mx), false otherwise.
    121  *
    122  * \see deInRange32()
    123  *//*--------------------------------------------------------------------*/
    124 DE_INLINE deBool deInBounds32 (int a, int mn, int mx)
    125 {
    126 	return (a >= mn) && (a < mx);
    127 }
    128 
    129 /*--------------------------------------------------------------------*//*!
    130  * \brief Clamp a value into the range [mn, mx].
    131  * \param a		Value to clamp.
    132  * \param mn	Minimum value.
    133  * \param mx	Maximum value.
    134  * \return The clamped value in [mn, mx] range.
    135  *//*--------------------------------------------------------------------*/
    136 DE_INLINE int deClamp32 (int a, int mn, int mx)
    137 {
    138 	DE_ASSERT(mn <= mx);
    139 	if (a < mn) return mn;
    140 	if (a > mx) return mx;
    141 	return a;
    142 }
    143 
    144 /*--------------------------------------------------------------------*//*!
    145  * \brief Get the sign of an integer.
    146  * \param a	Input value.
    147  * \return +1 if a>0, 0 if a==0, -1 if a<0.
    148  *//*--------------------------------------------------------------------*/
    149 DE_INLINE int deSign32 (int a)
    150 {
    151 	if (a > 0) return +1;
    152 	if (a < 0) return -1;
    153 	return 0;
    154 }
    155 
    156 /*--------------------------------------------------------------------*//*!
    157  * \brief Extract the sign bit of a.
    158  * \param a	Input value.
    159  * \return 0x80000000 if a<0, 0 otherwise.
    160  *//*--------------------------------------------------------------------*/
    161 DE_INLINE int deSignBit32 (int a)
    162 {
    163 	return (a & 0x80000000);
    164 }
    165 
    166 /*--------------------------------------------------------------------*//*!
    167  * \brief Integer rotate right.
    168  * \param val	Value to rotate.
    169  * \param r		Number of bits to rotate (in range [0, 32]).
    170  * \return The rotated value.
    171  *//*--------------------------------------------------------------------*/
    172 DE_INLINE int deRor32 (int val, int r)
    173 {
    174 	DE_ASSERT(r >= 0 && r <= 32);
    175 	if (r == 0 || r == 32)
    176 		return val;
    177 	else
    178 		return (int)(((deUint32)val >> r) | ((deUint32)val << (32-r)));
    179 }
    180 
    181 /*--------------------------------------------------------------------*//*!
    182  * \brief Integer rotate left.
    183  * \param val	Value to rotate.
    184  * \param r		Number of bits to rotate (in range [0, 32]).
    185  * \return The rotated value.
    186  *//*--------------------------------------------------------------------*/
    187 DE_INLINE int deRol32 (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)(((deUint32)val << r) | ((deUint32)val >> (32-r)));
    194 }
    195 
    196 /*--------------------------------------------------------------------*//*!
    197  * \brief Check if a value is a power-of-two.
    198  * \param a Input value.
    199  * \return True if input is a power-of-two value, false otherwise.
    200  *
    201  * \note Also returns true for zero.
    202  *//*--------------------------------------------------------------------*/
    203 DE_INLINE deBool deIsPowerOfTwo32 (int a)
    204 {
    205 	return ((a & (a - 1)) == 0);
    206 }
    207 
    208 /*--------------------------------------------------------------------*//*!
    209  * \brief Check if an integer is aligned to given power-of-two size.
    210  * \param a		Input value.
    211  * \param align	Alignment to check for.
    212  * \return True if input is aligned, false otherwise.
    213  *//*--------------------------------------------------------------------*/
    214 DE_INLINE deBool deIsAligned32 (int a, int align)
    215 {
    216 	DE_ASSERT(deIsPowerOfTwo32(align));
    217 	return ((a & (align-1)) == 0);
    218 }
    219 
    220 /*--------------------------------------------------------------------*//*!
    221  * \brief Check if a pointer is aligned to given power-of-two size.
    222  * \param ptr	Input pointer.
    223  * \param align	Alignment to check for (power-of-two).
    224  * \return True if input is aligned, false otherwise.
    225  *//*--------------------------------------------------------------------*/
    226 DE_INLINE deBool deIsAlignedPtr (const void* ptr, deUintptr align)
    227 {
    228 	DE_ASSERT((align & (align-1)) == 0); /* power of two */
    229 	return (((deUintptr)ptr & (align-1)) == 0);
    230 }
    231 
    232 /*--------------------------------------------------------------------*//*!
    233  * \brief Align an integer to given power-of-two size.
    234  * \param val	Input to align.
    235  * \param align	Alignment to check for (power-of-two).
    236  * \return The aligned value (larger or equal to input).
    237  *//*--------------------------------------------------------------------*/
    238 DE_INLINE deInt32 deAlign32 (deInt32 val, deInt32 align)
    239 {
    240 	DE_ASSERT(deIsPowerOfTwo32(align));
    241 	return (val + align - 1) & ~(align - 1);
    242 }
    243 
    244 /*--------------------------------------------------------------------*//*!
    245  * \brief Align a pointer to given power-of-two size.
    246  * \param ptr	Input pointer to align.
    247  * \param align	Alignment to check for (power-of-two).
    248  * \return The aligned pointer (larger or equal to input).
    249  *//*--------------------------------------------------------------------*/
    250 DE_INLINE void* deAlignPtr (void* ptr, deUintptr align)
    251 {
    252 	deUintptr val = (deUintptr)ptr;
    253 	DE_ASSERT((align & (align-1)) == 0); /* power of two */
    254 	return (void*)((val + align - 1) & ~(align - 1));
    255 }
    256 
    257 /*--------------------------------------------------------------------*//*!
    258  * \brief Compute number of leading zeros in an integer.
    259  * \param a	Input value.
    260  * \return The number of leading zero bits in the input.
    261  *//*--------------------------------------------------------------------*/
    262 extern const deInt8 g_clzLUT[256];
    263 
    264 DE_INLINE int deClz32 (deUint32 a)
    265 {
    266 #if (DE_COMPILER == DE_COMPILER_MSC)
    267 	unsigned long i;
    268 	if (_BitScanReverse(&i, (unsigned long)a) == 0)
    269 		return 32;
    270 	else
    271 		return 31-i;
    272 #elif (DE_COMPILER == DE_COMPILER_GCC) || (DE_COMPILER == DE_COMPILER_CLANG)
    273 	if (a == 0)
    274 		return 32;
    275 	else
    276 		return __builtin_clz((unsigned int)a);
    277 #else
    278 	if ((a & 0xFF000000u) != 0)
    279 		return (int)g_clzLUT[a >> 24];
    280 	if ((a & 0x00FF0000u) != 0)
    281 		return 8 + (int)g_clzLUT[a >> 16];
    282 	if ((a & 0x0000FF00u) != 0)
    283 		return 16 + (int)g_clzLUT[a >> 8];
    284 	return 24 + (int)g_clzLUT[a];
    285 #endif
    286 }
    287 
    288 /*--------------------------------------------------------------------*//*!
    289  * \brief Compute integer 'floor' of 'log2' for a positive integer.
    290  * \param a	Input value.
    291  * \return floor(log2(a)).
    292  *//*--------------------------------------------------------------------*/
    293 DE_INLINE int deLog2Floor32 (deInt32 a)
    294 {
    295 	DE_ASSERT(a > 0);
    296 	return 31 - deClz32(a);
    297 }
    298 
    299 /*--------------------------------------------------------------------*//*!
    300  * \brief Compute integer 'ceil' of 'log2' for a positive integer.
    301  * \param a	Input value.
    302  * \return ceil(log2(a)).
    303  *//*--------------------------------------------------------------------*/
    304 DE_INLINE int deLog2Ceil32 (deInt32 a)
    305 {
    306 	int log2floor = deLog2Floor32(a);
    307 	if (deIsPowerOfTwo32(a))
    308 		return log2floor;
    309 	else
    310 		return log2floor+1;
    311 }
    312 
    313 /* \todo [2012-04-28 pyry] Badly named, deprecated variant of deLog2Ceil32(). Remove once code has been fixed. */
    314 DE_INLINE deUint32 deLog2Clz(deInt32 a)
    315 {
    316 	return (deUint32)deLog2Ceil32(a);
    317 }
    318 
    319 /*--------------------------------------------------------------------*//*!
    320  * \brief Compute the bit population count of an integer.
    321  * \param a	Input value.
    322  * \return The number of one bits in the input.
    323  *//*--------------------------------------------------------------------*/
    324 DE_INLINE int dePop32 (deUint32 a)
    325 {
    326 	deUint32 mask0 = 0x55555555; /* 1-bit values. */
    327 	deUint32 mask1 = 0x33333333; /* 2-bit values. */
    328 	deUint32 mask2 = 0x0f0f0f0f; /* 4-bit values. */
    329 	deUint32 mask3 = 0x00ff00ff; /* 8-bit values. */
    330 	deUint32 mask4 = 0x0000ffff; /* 16-bit values. */
    331 	deUint32 t = (deUint32)a;
    332 	t = (t & mask0) + ((t>>1) & mask0);
    333 	t = (t & mask1) + ((t>>2) & mask1);
    334 	t = (t & mask2) + ((t>>4) & mask2);
    335 	t = (t & mask3) + ((t>>8) & mask3);
    336 	t = (t & mask4) + (t>>16);
    337 	return (int)t;
    338 }
    339 
    340 DE_INLINE int dePop64 (deUint64 a)
    341 {
    342 	return dePop32((deUint32)(a & 0xffffffffull)) + dePop32((deUint32)(a >> 32));
    343 }
    344 
    345 /*--------------------------------------------------------------------*//*!
    346  * \brief Reverse bytes in 32-bit integer (for example MSB -> LSB).
    347  * \param a	Input value.
    348  * \return The input with bytes reversed
    349  *//*--------------------------------------------------------------------*/
    350 DE_INLINE deUint32 deReverseBytes32 (deUint32 v)
    351 {
    352 	deUint32 b0 = v << 24;
    353 	deUint32 b1 = (v & 0x0000ff00) << 8;
    354 	deUint32 b2 = (v & 0x00ff0000) >> 8;
    355 	deUint32 b3 = v >> 24;
    356 	return b0|b1|b2|b3;
    357 }
    358 
    359 DE_INLINE deInt32 deSafeMul32 (deInt32 a, deInt32 b)
    360 {
    361 	deInt32 res = a * b;
    362 	DE_ASSERT((deInt64)res == ((deInt64)a * (deInt64)b));
    363 	return res;
    364 }
    365 
    366 DE_INLINE deInt32 deSafeAdd32 (deInt32 a, deInt32 b)
    367 {
    368 	DE_ASSERT((deInt64)a + (deInt64)b == (deInt64)(a + b));
    369 	return (a + b);
    370 }
    371 
    372 /* \todo [petri] Move to deInt64.h? */
    373 
    374 DE_INLINE deInt32 deMulAsr32 (deInt32 a, deInt32 b, int shift)
    375 {
    376 	return (deInt32)(((deInt64)a * (deInt64)b) >> shift);
    377 }
    378 
    379 DE_INLINE deInt32 deSafeMulAsr32 (deInt32 a, deInt32 b, int shift)
    380 {
    381 	deInt64 res = ((deInt64)a * (deInt64)b) >> shift;
    382 	DE_ASSERT(res == (deInt64)(deInt32)res);
    383 	return (deInt32)res;
    384 }
    385 
    386 DE_INLINE deUint32 deSafeMuluAsr32 (deUint32 a, deUint32 b, int shift)
    387 {
    388 	deUint64 res = ((deUint64)a * (deUint64)b) >> shift;
    389 	DE_ASSERT(res == (deUint64)(deUint32)res);
    390 	return (deUint32)res;
    391 }
    392 
    393 DE_INLINE deInt64 deMul32_32_64 (deInt32 a, deInt32 b)
    394 {
    395 	return ((deInt64)a * (deInt64)b);
    396 }
    397 
    398 DE_INLINE deInt64 deAbs64 (deInt64 a)
    399 {
    400 	DE_ASSERT((deUint64) a != 0x8000000000000000LL);
    401 	return (a >= 0) ? a : -a;
    402 }
    403 
    404 DE_INLINE int deClz64 (deInt64 a)
    405 {
    406 	if (((deUint64)a >> 32) != 0)
    407 		return deClz32((deInt32)(a >> 32));
    408 	return deClz32((deInt32)a) + 32;
    409 }
    410 
    411 /* Common hash & compare functions. */
    412 
    413 DE_INLINE deUint32 deInt32Hash (deInt32 a)
    414 {
    415 	/* From: http://www.concentric.net/~Ttwang/tech/inthash.htm */
    416 	deUint32 key = a;
    417 	key = (key ^ 61) ^ (key >> 16);
    418 	key = key + (key << 3);
    419 	key = key ^ (key >> 4);
    420 	key = key * 0x27d4eb2d; /* prime/odd constant */
    421 	key = key ^ (key >> 15);
    422 	return key;
    423 }
    424 
    425 DE_INLINE deUint32 deInt64Hash (deInt64 a)
    426 {
    427 	/* From: http://www.concentric.net/~Ttwang/tech/inthash.htm */
    428 	deUint64 key = a;
    429 	key = (~key) + (key << 21); /* key = (key << 21) - key - 1; */
    430 	key = key ^ (key >> 24);
    431 	key = (key + (key << 3)) + (key << 8); /* key * 265 */
    432 	key = key ^ (key >> 14);
    433 	key = (key + (key << 2)) + (key << 4); /* key * 21 */
    434 	key = key ^ (key >> 28);
    435 	key = key + (key << 31);
    436 	return (deUint32)key;
    437 }
    438 
    439 DE_INLINE int		deInt16Hash		(deInt16 v)					{ return deInt32Hash(v);			}
    440 DE_INLINE int		deUint16Hash	(deUint16 v)				{ return deInt32Hash((deInt32)v);	}
    441 DE_INLINE int		deUint32Hash	(deUint32 v)				{ return deInt32Hash((deInt32)v);	}
    442 DE_INLINE int		deUint64Hash	(deUint64 v)				{ return deInt64Hash((deInt64)v);	}
    443 
    444 DE_INLINE deBool	deInt16Equal	(deInt16 a, deInt16 b)		{ return (a == b);	}
    445 DE_INLINE deBool	deUint16Equal	(deUint16 a, deUint16 b)	{ return (a == b);	}
    446 DE_INLINE deBool	deInt32Equal	(deInt32 a, deInt32 b)		{ return (a == b);	}
    447 DE_INLINE deBool	deUint32Equal	(deUint32 a, deUint32 b)	{ return (a == b);	}
    448 DE_INLINE deBool	deInt64Equal	(deInt64 a, deInt64 b)		{ return (a == b);	}
    449 DE_INLINE deBool	deUint64Equal	(deUint64 a, deUint64 b)	{ return (a == b);	}
    450 
    451 DE_INLINE int dePointerHash (const void* ptr)
    452 {
    453 	deUintptr val = (deUintptr)ptr;
    454 #if (DE_PTR_SIZE == 4)
    455 	return deInt32Hash((int)val);
    456 #elif (DE_PTR_SIZE == 8)
    457 	return deInt64Hash((deInt64)val);
    458 #else
    459 #	error Unsupported pointer size.
    460 #endif
    461 }
    462 
    463 DE_INLINE deBool dePointerEqual (const void* a, const void* b)
    464 {
    465 	return (a == b);
    466 }
    467 
    468 /**
    469  *	\brief	Modulo that generates the same sign as divisor and rounds toward
    470  *			negative infinity -- assuming c99 %-operator.
    471  */
    472 DE_INLINE deInt32 deInt32ModF (deInt32 n, deInt32 d)
    473 {
    474 	deInt32 r = n%d;
    475 	if ((r > 0 && d < 0) || (r < 0 && d > 0)) r = r+d;
    476 	return r;
    477 }
    478 
    479 DE_INLINE deBool deInt64InInt32Range (deInt64 x)
    480 {
    481 	return ((x >= (-1ll<<31)) && (x <= ((1ll<<31)-1)));
    482 }
    483 
    484 
    485 DE_INLINE deUint32 deBitMask32 (int leastSignificantBitNdx, int numBits)
    486 {
    487 	DE_ASSERT(deInRange32(leastSignificantBitNdx, 0, 32));
    488 	DE_ASSERT(deInRange32(numBits, 0, 32));
    489 	DE_ASSERT(deInRange32(leastSignificantBitNdx+numBits, 0, 32));
    490 
    491 	if (numBits < 32 && leastSignificantBitNdx < 32)
    492 		return ((1u<<numBits)-1u) << (deUint32)leastSignificantBitNdx;
    493 	else if (numBits == 0 && leastSignificantBitNdx == 32)
    494 		return 0u;
    495 	else
    496 	{
    497 		DE_ASSERT(numBits == 32 && leastSignificantBitNdx == 0);
    498 		return 0xFFFFFFFFu;
    499 	}
    500 }
    501 
    502 DE_INLINE deUint32 deUintMaxValue32 (int numBits)
    503 {
    504 	DE_ASSERT(deInRange32(numBits, 1, 32));
    505 	if (numBits < 32)
    506 		return ((1u<<numBits)-1u);
    507 	else
    508 		return 0xFFFFFFFFu;
    509 }
    510 
    511 DE_INLINE deInt32 deIntMaxValue32 (int numBits)
    512 {
    513 	DE_ASSERT(deInRange32(numBits, 1, 32));
    514 	if (numBits < 32)
    515 		return ((deInt32)1 << (numBits - 1)) - 1;
    516 	else
    517 	{
    518 		/* avoid undefined behavior of int overflow when shifting */
    519 		return 0x7FFFFFFF;
    520 	}
    521 }
    522 
    523 DE_INLINE deInt32 deIntMinValue32 (int numBits)
    524 {
    525 	DE_ASSERT(deInRange32(numBits, 1, 32));
    526 	if (numBits < 32)
    527 		return -((deInt32)1 << (numBits - 1));
    528 	else
    529 	{
    530 		/* avoid undefined behavior of int overflow when shifting */
    531 		return (deInt32)(-0x7FFFFFFF - 1);
    532 	}
    533 }
    534 
    535 DE_END_EXTERN_C
    536 
    537 #endif /* _DEINT32_H */
    538