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
