1 /////////////////////////////////////////////////////////////////////////////////// 2 /// OpenGL Mathematics (glm.g-truc.net) 3 /// 4 /// Copyright (c) 2005 - 2014 G-Truc Creation (www.g-truc.net) 5 /// Permission is hereby granted, free of charge, to any person obtaining a copy 6 /// of this software and associated documentation files (the "Software"), to deal 7 /// in the Software without restriction, including without limitation the rights 8 /// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 9 /// copies of the Software, and to permit persons to whom the Software is 10 /// furnished to do so, subject to the following conditions: 11 /// 12 /// The above copyright notice and this permission notice shall be included in 13 /// all copies or substantial portions of the Software. 14 /// 15 /// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16 /// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17 /// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 18 /// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19 /// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 20 /// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 21 /// THE SOFTWARE. 22 /// 23 /// @ref core 24 /// @file glm/core/func_integer.inl 25 /// @date 2010-03-17 / 2011-06-15 26 /// @author Christophe Riccio 27 /////////////////////////////////////////////////////////////////////////////////// 28 29 #include "type_vec2.hpp" 30 #include "type_vec3.hpp" 31 #include "type_vec4.hpp" 32 #include "type_int.hpp" 33 #include "_vectorize.hpp" 34 #if(GLM_ARCH != GLM_ARCH_PURE) 35 #if(GLM_COMPILER & GLM_COMPILER_VC) 36 # include <intrin.h> 37 # pragma intrinsic(_BitScanReverse) 38 #endif//(GLM_COMPILER & GLM_COMPILER_VC) 39 #endif//(GLM_ARCH != GLM_ARCH_PURE) 40 #include <limits> 41 42 namespace glm 43 { 44 // uaddCarry 45 template <> 46 GLM_FUNC_QUALIFIER uint uaddCarry 47 ( 48 uint const & x, 49 uint const & y, 50 uint & Carry 51 ) 52 { 53 uint64 Value64 = static_cast<uint64>(x) + static_cast<uint64>(y); 54 uint32 Result = static_cast<uint32>(Value64 % (static_cast<uint64>(1) << static_cast<uint64>(32))); 55 Carry = (Value64 % (static_cast<uint64>(1) << static_cast<uint64>(32))) > 1 ? static_cast<uint32>(1) : static_cast<uint32>(0); 56 return Result; 57 } 58 59 template <> 60 GLM_FUNC_QUALIFIER uvec2 uaddCarry 61 ( 62 uvec2 const & x, 63 uvec2 const & y, 64 uvec2 & Carry 65 ) 66 { 67 return uvec2( 68 uaddCarry(x[0], y[0], Carry[0]), 69 uaddCarry(x[1], y[1], Carry[1])); 70 } 71 72 template <> 73 GLM_FUNC_QUALIFIER uvec3 uaddCarry 74 ( 75 uvec3 const & x, 76 uvec3 const & y, 77 uvec3 & Carry 78 ) 79 { 80 return uvec3( 81 uaddCarry(x[0], y[0], Carry[0]), 82 uaddCarry(x[1], y[1], Carry[1]), 83 uaddCarry(x[2], y[2], Carry[2])); 84 } 85 86 template <> 87 GLM_FUNC_QUALIFIER uvec4 uaddCarry 88 ( 89 uvec4 const & x, 90 uvec4 const & y, 91 uvec4 & Carry 92 ) 93 { 94 return uvec4( 95 uaddCarry(x[0], y[0], Carry[0]), 96 uaddCarry(x[1], y[1], Carry[1]), 97 uaddCarry(x[2], y[2], Carry[2]), 98 uaddCarry(x[3], y[3], Carry[3])); 99 } 100 101 // usubBorrow 102 template <> 103 GLM_FUNC_QUALIFIER uint usubBorrow 104 ( 105 uint const & x, 106 uint const & y, 107 uint & Borrow 108 ) 109 { 110 GLM_STATIC_ASSERT(sizeof(uint) == sizeof(uint32), "uint and uint32 size mismatch"); 111 112 Borrow = x >= y ? static_cast<uint32>(0) : static_cast<uint32>(1); 113 if(y >= x) 114 return y - x; 115 else 116 return static_cast<uint32>((static_cast<int64>(1) << static_cast<int64>(32)) + (static_cast<int64>(y) - static_cast<int64>(x))); 117 } 118 119 template <> 120 GLM_FUNC_QUALIFIER uvec2 usubBorrow 121 ( 122 uvec2 const & x, 123 uvec2 const & y, 124 uvec2 & Borrow 125 ) 126 { 127 return uvec2( 128 usubBorrow(x[0], y[0], Borrow[0]), 129 usubBorrow(x[1], y[1], Borrow[1])); 130 } 131 132 template <> 133 GLM_FUNC_QUALIFIER uvec3 usubBorrow 134 ( 135 uvec3 const & x, 136 uvec3 const & y, 137 uvec3 & Borrow 138 ) 139 { 140 return uvec3( 141 usubBorrow(x[0], y[0], Borrow[0]), 142 usubBorrow(x[1], y[1], Borrow[1]), 143 usubBorrow(x[2], y[2], Borrow[2])); 144 } 145 146 template <> 147 GLM_FUNC_QUALIFIER uvec4 usubBorrow 148 ( 149 uvec4 const & x, 150 uvec4 const & y, 151 uvec4 & Borrow 152 ) 153 { 154 return uvec4( 155 usubBorrow(x[0], y[0], Borrow[0]), 156 usubBorrow(x[1], y[1], Borrow[1]), 157 usubBorrow(x[2], y[2], Borrow[2]), 158 usubBorrow(x[3], y[3], Borrow[3])); 159 } 160 161 // umulExtended 162 template <> 163 GLM_FUNC_QUALIFIER void umulExtended 164 ( 165 uint const & x, 166 uint const & y, 167 uint & msb, 168 uint & lsb 169 ) 170 { 171 GLM_STATIC_ASSERT(sizeof(uint) == sizeof(uint32), "uint and uint32 size mismatch"); 172 173 uint64 Value64 = static_cast<uint64>(x) * static_cast<uint64>(y); 174 uint32* PointerMSB = (reinterpret_cast<uint32*>(&Value64) + 1); 175 msb = *PointerMSB; 176 uint32* PointerLSB = (reinterpret_cast<uint32*>(&Value64) + 0); 177 lsb = *PointerLSB; 178 } 179 180 template <> 181 GLM_FUNC_QUALIFIER void umulExtended 182 ( 183 uvec2 const & x, 184 uvec2 const & y, 185 uvec2 & msb, 186 uvec2 & lsb 187 ) 188 { 189 umulExtended(x[0], y[0], msb[0], lsb[0]); 190 umulExtended(x[1], y[1], msb[1], lsb[1]); 191 } 192 193 template <> 194 GLM_FUNC_QUALIFIER void umulExtended 195 ( 196 uvec3 const & x, 197 uvec3 const & y, 198 uvec3 & msb, 199 uvec3 & lsb 200 ) 201 { 202 umulExtended(x[0], y[0], msb[0], lsb[0]); 203 umulExtended(x[1], y[1], msb[1], lsb[1]); 204 umulExtended(x[2], y[2], msb[2], lsb[2]); 205 } 206 207 template <> 208 GLM_FUNC_QUALIFIER void umulExtended 209 ( 210 uvec4 const & x, 211 uvec4 const & y, 212 uvec4 & msb, 213 uvec4 & lsb 214 ) 215 { 216 umulExtended(x[0], y[0], msb[0], lsb[0]); 217 umulExtended(x[1], y[1], msb[1], lsb[1]); 218 umulExtended(x[2], y[2], msb[2], lsb[2]); 219 umulExtended(x[3], y[3], msb[3], lsb[3]); 220 } 221 222 // imulExtended 223 template <> 224 GLM_FUNC_QUALIFIER void imulExtended 225 ( 226 int const & x, 227 int const & y, 228 int & msb, 229 int & lsb 230 ) 231 { 232 GLM_STATIC_ASSERT(sizeof(int) == sizeof(int32), "int and int32 size mismatch"); 233 234 int64 Value64 = static_cast<int64>(x) * static_cast<int64>(y); 235 int32* PointerMSB = (reinterpret_cast<int32*>(&Value64) + 1); 236 msb = *PointerMSB; 237 int32* PointerLSB = (reinterpret_cast<int32*>(&Value64)); 238 lsb = *PointerLSB; 239 } 240 241 template <> 242 GLM_FUNC_QUALIFIER void imulExtended 243 ( 244 ivec2 const & x, 245 ivec2 const & y, 246 ivec2 & msb, 247 ivec2 & lsb 248 ) 249 { 250 imulExtended(x[0], y[0], msb[0], lsb[0]), 251 imulExtended(x[1], y[1], msb[1], lsb[1]); 252 } 253 254 template <> 255 GLM_FUNC_QUALIFIER void imulExtended 256 ( 257 ivec3 const & x, 258 ivec3 const & y, 259 ivec3 & msb, 260 ivec3 & lsb 261 ) 262 { 263 imulExtended(x[0], y[0], msb[0], lsb[0]), 264 imulExtended(x[1], y[1], msb[1], lsb[1]); 265 imulExtended(x[2], y[2], msb[2], lsb[2]); 266 } 267 268 template <> 269 GLM_FUNC_QUALIFIER void imulExtended 270 ( 271 ivec4 const & x, 272 ivec4 const & y, 273 ivec4 & msb, 274 ivec4 & lsb 275 ) 276 { 277 imulExtended(x[0], y[0], msb[0], lsb[0]), 278 imulExtended(x[1], y[1], msb[1], lsb[1]); 279 imulExtended(x[2], y[2], msb[2], lsb[2]); 280 imulExtended(x[3], y[3], msb[3], lsb[3]); 281 } 282 283 // bitfieldExtract 284 template <typename genIUType> 285 GLM_FUNC_QUALIFIER genIUType bitfieldExtract 286 ( 287 genIUType const & Value, 288 int const & Offset, 289 int const & Bits 290 ) 291 { 292 int GenSize = int(sizeof(genIUType)) << int(3); 293 294 assert(Offset + Bits <= GenSize); 295 296 genIUType ShiftLeft = Bits ? Value << (GenSize - (Bits + Offset)) : genIUType(0); 297 genIUType ShiftBack = ShiftLeft >> genIUType(GenSize - Bits); 298 299 return ShiftBack; 300 } 301 302 template <typename T, precision P> 303 GLM_FUNC_QUALIFIER detail::tvec2<T, P> bitfieldExtract 304 ( 305 detail::tvec2<T, P> const & Value, 306 int const & Offset, 307 int const & Bits 308 ) 309 { 310 return detail::tvec2<T, P>( 311 bitfieldExtract(Value[0], Offset, Bits), 312 bitfieldExtract(Value[1], Offset, Bits)); 313 } 314 315 template <typename T, precision P> 316 GLM_FUNC_QUALIFIER detail::tvec3<T, P> bitfieldExtract 317 ( 318 detail::tvec3<T, P> const & Value, 319 int const & Offset, 320 int const & Bits 321 ) 322 { 323 return detail::tvec3<T, P>( 324 bitfieldExtract(Value[0], Offset, Bits), 325 bitfieldExtract(Value[1], Offset, Bits), 326 bitfieldExtract(Value[2], Offset, Bits)); 327 } 328 329 template <typename T, precision P> 330 GLM_FUNC_QUALIFIER detail::tvec4<T, P> bitfieldExtract 331 ( 332 detail::tvec4<T, P> const & Value, 333 int const & Offset, 334 int const & Bits 335 ) 336 { 337 return detail::tvec4<T, P>( 338 bitfieldExtract(Value[0], Offset, Bits), 339 bitfieldExtract(Value[1], Offset, Bits), 340 bitfieldExtract(Value[2], Offset, Bits), 341 bitfieldExtract(Value[3], Offset, Bits)); 342 } 343 344 // bitfieldInsert 345 template <typename genIUType> 346 GLM_FUNC_QUALIFIER genIUType bitfieldInsert 347 ( 348 genIUType const & Base, 349 genIUType const & Insert, 350 int const & Offset, 351 int const & Bits 352 ) 353 { 354 GLM_STATIC_ASSERT(std::numeric_limits<genIUType>::is_integer, "'bitfieldInsert' only accept integer values"); 355 assert(Offset + Bits <= sizeof(genIUType)); 356 357 if(Bits == 0) 358 return Base; 359 360 genIUType Mask = 0; 361 for(int Bit = Offset; Bit < Offset + Bits; ++Bit) 362 Mask |= (1 << Bit); 363 364 return (Base & ~Mask) | (Insert & Mask); 365 } 366 367 template <typename T, precision P> 368 GLM_FUNC_QUALIFIER detail::tvec2<T, P> bitfieldInsert 369 ( 370 detail::tvec2<T, P> const & Base, 371 detail::tvec2<T, P> const & Insert, 372 int const & Offset, 373 int const & Bits 374 ) 375 { 376 return detail::tvec2<T, P>( 377 bitfieldInsert(Base[0], Insert[0], Offset, Bits), 378 bitfieldInsert(Base[1], Insert[1], Offset, Bits)); 379 } 380 381 template <typename T, precision P> 382 GLM_FUNC_QUALIFIER detail::tvec3<T, P> bitfieldInsert 383 ( 384 detail::tvec3<T, P> const & Base, 385 detail::tvec3<T, P> const & Insert, 386 int const & Offset, 387 int const & Bits 388 ) 389 { 390 return detail::tvec3<T, P>( 391 bitfieldInsert(Base[0], Insert[0], Offset, Bits), 392 bitfieldInsert(Base[1], Insert[1], Offset, Bits), 393 bitfieldInsert(Base[2], Insert[2], Offset, Bits)); 394 } 395 396 template <typename T, precision P> 397 GLM_FUNC_QUALIFIER detail::tvec4<T, P> bitfieldInsert 398 ( 399 detail::tvec4<T, P> const & Base, 400 detail::tvec4<T, P> const & Insert, 401 int const & Offset, 402 int const & Bits 403 ) 404 { 405 return detail::tvec4<T, P>( 406 bitfieldInsert(Base[0], Insert[0], Offset, Bits), 407 bitfieldInsert(Base[1], Insert[1], Offset, Bits), 408 bitfieldInsert(Base[2], Insert[2], Offset, Bits), 409 bitfieldInsert(Base[3], Insert[3], Offset, Bits)); 410 } 411 412 // bitfieldReverse 413 template <typename genIUType> 414 GLM_FUNC_QUALIFIER genIUType bitfieldReverse(genIUType const & Value) 415 { 416 GLM_STATIC_ASSERT(std::numeric_limits<genIUType>::is_integer, "'bitfieldReverse' only accept integer values"); 417 418 genIUType Out = 0; 419 std::size_t BitSize = sizeof(genIUType) * 8; 420 for(std::size_t i = 0; i < BitSize; ++i) 421 if(Value & (genIUType(1) << i)) 422 Out |= genIUType(1) << (BitSize - 1 - i); 423 return Out; 424 } 425 426 VECTORIZE_VEC(bitfieldReverse) 427 428 // bitCount 429 template <typename genIUType> 430 GLM_FUNC_QUALIFIER int bitCount(genIUType const & Value) 431 { 432 GLM_STATIC_ASSERT(std::numeric_limits<genIUType>::is_integer, "'bitCount' only accept integer values"); 433 434 int Count = 0; 435 for(std::size_t i = 0; i < sizeof(genIUType) * std::size_t(8); ++i) 436 { 437 if(Value & (1 << i)) 438 ++Count; 439 } 440 return Count; 441 } 442 443 template <typename T, precision P> 444 GLM_FUNC_QUALIFIER detail::tvec2<int, P> bitCount 445 ( 446 detail::tvec2<T, P> const & value 447 ) 448 { 449 return detail::tvec2<int, P>( 450 bitCount(value[0]), 451 bitCount(value[1])); 452 } 453 454 template <typename T, precision P> 455 GLM_FUNC_QUALIFIER detail::tvec3<int, P> bitCount 456 ( 457 detail::tvec3<T, P> const & value 458 ) 459 { 460 return detail::tvec3<int, P>( 461 bitCount(value[0]), 462 bitCount(value[1]), 463 bitCount(value[2])); 464 } 465 466 template <typename T, precision P> 467 GLM_FUNC_QUALIFIER detail::tvec4<int, P> bitCount 468 ( 469 detail::tvec4<T, P> const & value 470 ) 471 { 472 return detail::tvec4<int, P>( 473 bitCount(value[0]), 474 bitCount(value[1]), 475 bitCount(value[2]), 476 bitCount(value[3])); 477 } 478 479 // findLSB 480 template <typename genIUType> 481 GLM_FUNC_QUALIFIER int findLSB 482 ( 483 genIUType const & Value 484 ) 485 { 486 GLM_STATIC_ASSERT(std::numeric_limits<genIUType>::is_integer, "'findLSB' only accept integer values"); 487 if(Value == 0) 488 return -1; 489 490 genIUType Bit; 491 for(Bit = genIUType(0); !(Value & (1 << Bit)); ++Bit){} 492 return Bit; 493 } 494 495 template <typename T, precision P> 496 GLM_FUNC_QUALIFIER detail::tvec2<int, P> findLSB 497 ( 498 detail::tvec2<T, P> const & value 499 ) 500 { 501 return detail::tvec2<int, P>( 502 findLSB(value[0]), 503 findLSB(value[1])); 504 } 505 506 template <typename T, precision P> 507 GLM_FUNC_QUALIFIER detail::tvec3<int, P> findLSB 508 ( 509 detail::tvec3<T, P> const & value 510 ) 511 { 512 return detail::tvec3<int, P>( 513 findLSB(value[0]), 514 findLSB(value[1]), 515 findLSB(value[2])); 516 } 517 518 template <typename T, precision P> 519 GLM_FUNC_QUALIFIER detail::tvec4<int, P> findLSB 520 ( 521 detail::tvec4<T, P> const & value 522 ) 523 { 524 return detail::tvec4<int, P>( 525 findLSB(value[0]), 526 findLSB(value[1]), 527 findLSB(value[2]), 528 findLSB(value[3])); 529 } 530 531 // findMSB 532 #if((GLM_ARCH != GLM_ARCH_PURE) && (GLM_COMPILER & GLM_COMPILER_VC)) 533 534 template <typename genIUType> 535 GLM_FUNC_QUALIFIER int findMSB 536 ( 537 genIUType const & Value 538 ) 539 { 540 GLM_STATIC_ASSERT(std::numeric_limits<genIUType>::is_integer, "'findMSB' only accept integer values"); 541 if(Value == 0) 542 return -1; 543 544 unsigned long Result(0); 545 _BitScanReverse(&Result, Value); 546 return int(Result); 547 } 548 /* 549 // __builtin_clz seems to be buggy as it crasks for some values, from 0x00200000 to 80000000 550 #elif((GLM_ARCH != GLM_ARCH_PURE) && (GLM_COMPILER & GLM_COMPILER_GCC) && (GLM_COMPILER >= GLM_COMPILER_GCC40)) 551 552 template <typename genIUType> 553 GLM_FUNC_QUALIFIER int findMSB 554 ( 555 genIUType const & Value 556 ) 557 { 558 GLM_STATIC_ASSERT(std::numeric_limits<genIUType>::is_integer, "'findMSB' only accept integer values"); 559 if(Value == 0) 560 return -1; 561 562 // clz returns the number or trailing 0-bits; see 563 // http://gcc.gnu.org/onlinedocs/gcc-4.7.1/gcc/Other-Builtins.html 564 // 565 // NoteBecause __builtin_clz only works for unsigned ints, this 566 // implementation will not work for 64-bit integers. 567 // 568 return 31 - __builtin_clzl(Value); 569 } 570 */ 571 #else 572 573 /* SSE implementation idea 574 575 __m128i const Zero = _mm_set_epi32( 0, 0, 0, 0); 576 __m128i const One = _mm_set_epi32( 1, 1, 1, 1); 577 __m128i Bit = _mm_set_epi32(-1, -1, -1, -1); 578 __m128i Tmp = _mm_set_epi32(Value, Value, Value, Value); 579 __m128i Mmi = Zero; 580 for(int i = 0; i < 32; ++i) 581 { 582 __m128i Shilt = _mm_and_si128(_mm_cmpgt_epi32(Tmp, One), One); 583 Tmp = _mm_srai_epi32(Tmp, One); 584 Bit = _mm_add_epi32(Bit, _mm_and_si128(Shilt, i)); 585 Mmi = _mm_and_si128(Mmi, One); 586 } 587 return Bit; 588 589 */ 590 591 template <typename genIUType> 592 GLM_FUNC_QUALIFIER int findMSB 593 ( 594 genIUType const & Value 595 ) 596 { 597 GLM_STATIC_ASSERT(std::numeric_limits<genIUType>::is_integer, "'findMSB' only accept integer values"); 598 599 if(Value == genIUType(0) || Value == genIUType(-1)) 600 return -1; 601 else if(Value > 0) 602 { 603 genIUType Bit = genIUType(-1); 604 for(genIUType tmp = Value; tmp > 0; tmp >>= 1, ++Bit){} 605 return Bit; 606 } 607 else //if(Value < 0) 608 { 609 int const BitCount(sizeof(genIUType) * 8); 610 int MostSignificantBit(-1); 611 for(int BitIndex(0); BitIndex < BitCount; ++BitIndex) 612 MostSignificantBit = (Value & (1 << BitIndex)) ? MostSignificantBit : BitIndex; 613 assert(MostSignificantBit >= 0); 614 return MostSignificantBit; 615 } 616 } 617 #endif//(GLM_COMPILER) 618 619 template <typename T, precision P> 620 GLM_FUNC_QUALIFIER detail::tvec2<int, P> findMSB 621 ( 622 detail::tvec2<T, P> const & value 623 ) 624 { 625 return detail::tvec2<int, P>( 626 findMSB(value[0]), 627 findMSB(value[1])); 628 } 629 630 template <typename T, precision P> 631 GLM_FUNC_QUALIFIER detail::tvec3<int, P> findMSB 632 ( 633 detail::tvec3<T, P> const & value 634 ) 635 { 636 return detail::tvec3<int, P>( 637 findMSB(value[0]), 638 findMSB(value[1]), 639 findMSB(value[2])); 640 } 641 642 template <typename T, precision P> 643 GLM_FUNC_QUALIFIER detail::tvec4<int, P> findMSB 644 ( 645 detail::tvec4<T, P> const & value 646 ) 647 { 648 return detail::tvec4<int, P>( 649 findMSB(value[0]), 650 findMSB(value[1]), 651 findMSB(value[2]), 652 findMSB(value[3])); 653 } 654 }//namespace glm 655
