oculus1
diff libovr/Src/Kernel/OVR_Alg.h @ 3:b069a5c27388
added a couple more stuff, fixed all the LibOVR line endings
| author | John Tsiombikas <nuclear@member.fsf.org> |
|---|---|
| date | Sun, 15 Sep 2013 04:10:05 +0300 |
| parents | e2f9e4603129 |
| children |
line diff
1.1 --- a/libovr/Src/Kernel/OVR_Alg.h Sat Sep 14 17:51:03 2013 +0300 1.2 +++ b/libovr/Src/Kernel/OVR_Alg.h Sun Sep 15 04:10:05 2013 +0300 1.3 @@ -1,1 +1,953 @@ 1.4 -/************************************************************************************ 1.5 1.6 PublicHeader: OVR.h 1.7 Filename : OVR_Alg.h 1.8 Content : Simple general purpose algorithms: Sort, Binary Search, etc. 1.9 Created : September 19, 2012 1.10 Notes : 1.11 1.12 Copyright : Copyright 2012 Oculus VR, Inc. All Rights reserved. 1.13 1.14 Use of this software is subject to the terms of the Oculus license 1.15 agreement provided at the time of installation or download, or which 1.16 otherwise accompanies this software in either electronic or hard copy form. 1.17 1.18 ************************************************************************************/ 1.19 1.20 #ifndef OVR_Alg_h 1.21 #define OVR_Alg_h 1.22 1.23 #include "OVR_Types.h" 1.24 #include <string.h> 1.25 1.26 namespace OVR { namespace Alg { 1.27 1.28 1.29 //----------------------------------------------------------------------------------- 1.30 // ***** Operator extensions 1.31 1.32 template <typename T> OVR_FORCE_INLINE void Swap(T &a, T &b) 1.33 { T temp(a); a = b; b = temp; } 1.34 1.35 1.36 // ***** min/max are not implemented in Visual Studio 6 standard STL 1.37 1.38 template <typename T> OVR_FORCE_INLINE const T Min(const T a, const T b) 1.39 { return (a < b) ? a : b; } 1.40 1.41 template <typename T> OVR_FORCE_INLINE const T Max(const T a, const T b) 1.42 { return (b < a) ? a : b; } 1.43 1.44 template <typename T> OVR_FORCE_INLINE const T Clamp(const T v, const T minVal, const T maxVal) 1.45 { return Max<T>(minVal, Min<T>(v, maxVal)); } 1.46 1.47 template <typename T> OVR_FORCE_INLINE int Chop(T f) 1.48 { return (int)f; } 1.49 1.50 template <typename T> OVR_FORCE_INLINE T Lerp(T a, T b, T f) 1.51 { return (b - a) * f + a; } 1.52 1.53 1.54 // These functions stand to fix a stupid VC++ warning (with /Wp64 on): 1.55 // "warning C4267: 'argument' : conversion from 'size_t' to 'const unsigned', possible loss of data" 1.56 // Use these functions instead of gmin/gmax if the argument has size 1.57 // of the pointer to avoid the warning. Though, functionally they are 1.58 // absolutelly the same as regular gmin/gmax. 1.59 template <typename T> OVR_FORCE_INLINE const T PMin(const T a, const T b) 1.60 { 1.61 OVR_COMPILER_ASSERT(sizeof(T) == sizeof(UPInt)); 1.62 return (a < b) ? a : b; 1.63 } 1.64 template <typename T> OVR_FORCE_INLINE const T PMax(const T a, const T b) 1.65 { 1.66 OVR_COMPILER_ASSERT(sizeof(T) == sizeof(UPInt)); 1.67 return (b < a) ? a : b; 1.68 } 1.69 1.70 1.71 template <typename T> OVR_FORCE_INLINE const T Abs(const T v) 1.72 { return (v>=0) ? v : -v; } 1.73 1.74 1.75 //----------------------------------------------------------------------------------- 1.76 // ***** OperatorLess 1.77 // 1.78 template<class T> struct OperatorLess 1.79 { 1.80 static bool Compare(const T& a, const T& b) 1.81 { 1.82 return a < b; 1.83 } 1.84 }; 1.85 1.86 1.87 //----------------------------------------------------------------------------------- 1.88 // ***** QuickSortSliced 1.89 // 1.90 // Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe. 1.91 // The range is specified with start, end, where "end" is exclusive! 1.92 // The comparison predicate must be specified. 1.93 template<class Array, class Less> 1.94 void QuickSortSliced(Array& arr, UPInt start, UPInt end, Less less) 1.95 { 1.96 enum 1.97 { 1.98 Threshold = 9 1.99 }; 1.100 1.101 if(end - start < 2) return; 1.102 1.103 SPInt stack[80]; 1.104 SPInt* top = stack; 1.105 SPInt base = (SPInt)start; 1.106 SPInt limit = (SPInt)end; 1.107 1.108 for(;;) 1.109 { 1.110 SPInt len = limit - base; 1.111 SPInt i, j, pivot; 1.112 1.113 if(len > Threshold) 1.114 { 1.115 // we use base + len/2 as the pivot 1.116 pivot = base + len / 2; 1.117 Swap(arr[base], arr[pivot]); 1.118 1.119 i = base + 1; 1.120 j = limit - 1; 1.121 1.122 // now ensure that *i <= *base <= *j 1.123 if(less(arr[j], arr[i])) Swap(arr[j], arr[i]); 1.124 if(less(arr[base], arr[i])) Swap(arr[base], arr[i]); 1.125 if(less(arr[j], arr[base])) Swap(arr[j], arr[base]); 1.126 1.127 for(;;) 1.128 { 1.129 do i++; while( less(arr[i], arr[base]) ); 1.130 do j--; while( less(arr[base], arr[j]) ); 1.131 1.132 if( i > j ) 1.133 { 1.134 break; 1.135 } 1.136 1.137 Swap(arr[i], arr[j]); 1.138 } 1.139 1.140 Swap(arr[base], arr[j]); 1.141 1.142 // now, push the largest sub-array 1.143 if(j - base > limit - i) 1.144 { 1.145 top[0] = base; 1.146 top[1] = j; 1.147 base = i; 1.148 } 1.149 else 1.150 { 1.151 top[0] = i; 1.152 top[1] = limit; 1.153 limit = j; 1.154 } 1.155 top += 2; 1.156 } 1.157 else 1.158 { 1.159 // the sub-array is small, perform insertion sort 1.160 j = base; 1.161 i = j + 1; 1.162 1.163 for(; i < limit; j = i, i++) 1.164 { 1.165 for(; less(arr[j + 1], arr[j]); j--) 1.166 { 1.167 Swap(arr[j + 1], arr[j]); 1.168 if(j == base) 1.169 { 1.170 break; 1.171 } 1.172 } 1.173 } 1.174 if(top > stack) 1.175 { 1.176 top -= 2; 1.177 base = top[0]; 1.178 limit = top[1]; 1.179 } 1.180 else 1.181 { 1.182 break; 1.183 } 1.184 } 1.185 } 1.186 } 1.187 1.188 1.189 //----------------------------------------------------------------------------------- 1.190 // ***** QuickSortSliced 1.191 // 1.192 // Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe. 1.193 // The range is specified with start, end, where "end" is exclusive! 1.194 // The data type must have a defined "<" operator. 1.195 template<class Array> 1.196 void QuickSortSliced(Array& arr, UPInt start, UPInt end) 1.197 { 1.198 typedef typename Array::ValueType ValueType; 1.199 QuickSortSliced(arr, start, end, OperatorLess<ValueType>::Compare); 1.200 } 1.201 1.202 // Same as corresponding G_QuickSortSliced but with checking array limits to avoid 1.203 // crash in the case of wrong comparator functor. 1.204 template<class Array, class Less> 1.205 bool QuickSortSlicedSafe(Array& arr, UPInt start, UPInt end, Less less) 1.206 { 1.207 enum 1.208 { 1.209 Threshold = 9 1.210 }; 1.211 1.212 if(end - start < 2) return true; 1.213 1.214 SPInt stack[80]; 1.215 SPInt* top = stack; 1.216 SPInt base = (SPInt)start; 1.217 SPInt limit = (SPInt)end; 1.218 1.219 for(;;) 1.220 { 1.221 SPInt len = limit - base; 1.222 SPInt i, j, pivot; 1.223 1.224 if(len > Threshold) 1.225 { 1.226 // we use base + len/2 as the pivot 1.227 pivot = base + len / 2; 1.228 Swap(arr[base], arr[pivot]); 1.229 1.230 i = base + 1; 1.231 j = limit - 1; 1.232 1.233 // now ensure that *i <= *base <= *j 1.234 if(less(arr[j], arr[i])) Swap(arr[j], arr[i]); 1.235 if(less(arr[base], arr[i])) Swap(arr[base], arr[i]); 1.236 if(less(arr[j], arr[base])) Swap(arr[j], arr[base]); 1.237 1.238 for(;;) 1.239 { 1.240 do 1.241 { 1.242 i++; 1.243 if (i >= limit) 1.244 return false; 1.245 } while( less(arr[i], arr[base]) ); 1.246 do 1.247 { 1.248 j--; 1.249 if (j < 0) 1.250 return false; 1.251 } while( less(arr[base], arr[j]) ); 1.252 1.253 if( i > j ) 1.254 { 1.255 break; 1.256 } 1.257 1.258 Swap(arr[i], arr[j]); 1.259 } 1.260 1.261 Swap(arr[base], arr[j]); 1.262 1.263 // now, push the largest sub-array 1.264 if(j - base > limit - i) 1.265 { 1.266 top[0] = base; 1.267 top[1] = j; 1.268 base = i; 1.269 } 1.270 else 1.271 { 1.272 top[0] = i; 1.273 top[1] = limit; 1.274 limit = j; 1.275 } 1.276 top += 2; 1.277 } 1.278 else 1.279 { 1.280 // the sub-array is small, perform insertion sort 1.281 j = base; 1.282 i = j + 1; 1.283 1.284 for(; i < limit; j = i, i++) 1.285 { 1.286 for(; less(arr[j + 1], arr[j]); j--) 1.287 { 1.288 Swap(arr[j + 1], arr[j]); 1.289 if(j == base) 1.290 { 1.291 break; 1.292 } 1.293 } 1.294 } 1.295 if(top > stack) 1.296 { 1.297 top -= 2; 1.298 base = top[0]; 1.299 limit = top[1]; 1.300 } 1.301 else 1.302 { 1.303 break; 1.304 } 1.305 } 1.306 } 1.307 return true; 1.308 } 1.309 1.310 template<class Array> 1.311 bool QuickSortSlicedSafe(Array& arr, UPInt start, UPInt end) 1.312 { 1.313 typedef typename Array::ValueType ValueType; 1.314 return QuickSortSlicedSafe(arr, start, end, OperatorLess<ValueType>::Compare); 1.315 } 1.316 1.317 //----------------------------------------------------------------------------------- 1.318 // ***** QuickSort 1.319 // 1.320 // Sort an array Array, ArrayPaged, ArrayUnsafe. 1.321 // The array must have GetSize() function. 1.322 // The comparison predicate must be specified. 1.323 template<class Array, class Less> 1.324 void QuickSort(Array& arr, Less less) 1.325 { 1.326 QuickSortSliced(arr, 0, arr.GetSize(), less); 1.327 } 1.328 1.329 // checks for boundaries 1.330 template<class Array, class Less> 1.331 bool QuickSortSafe(Array& arr, Less less) 1.332 { 1.333 return QuickSortSlicedSafe(arr, 0, arr.GetSize(), less); 1.334 } 1.335 1.336 1.337 //----------------------------------------------------------------------------------- 1.338 // ***** QuickSort 1.339 // 1.340 // Sort an array Array, ArrayPaged, ArrayUnsafe. 1.341 // The array must have GetSize() function. 1.342 // The data type must have a defined "<" operator. 1.343 template<class Array> 1.344 void QuickSort(Array& arr) 1.345 { 1.346 typedef typename Array::ValueType ValueType; 1.347 QuickSortSliced(arr, 0, arr.GetSize(), OperatorLess<ValueType>::Compare); 1.348 } 1.349 1.350 template<class Array> 1.351 bool QuickSortSafe(Array& arr) 1.352 { 1.353 typedef typename Array::ValueType ValueType; 1.354 return QuickSortSlicedSafe(arr, 0, arr.GetSize(), OperatorLess<ValueType>::Compare); 1.355 } 1.356 1.357 //----------------------------------------------------------------------------------- 1.358 // ***** InsertionSortSliced 1.359 // 1.360 // Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe. 1.361 // The range is specified with start, end, where "end" is exclusive! 1.362 // The comparison predicate must be specified. 1.363 // Unlike Quick Sort, the Insertion Sort works much slower in average, 1.364 // but may be much faster on almost sorted arrays. Besides, it guarantees 1.365 // that the elements will not be swapped if not necessary. For example, 1.366 // an array with all equal elements will remain "untouched", while 1.367 // Quick Sort will considerably shuffle the elements in this case. 1.368 template<class Array, class Less> 1.369 void InsertionSortSliced(Array& arr, UPInt start, UPInt end, Less less) 1.370 { 1.371 UPInt j = start; 1.372 UPInt i = j + 1; 1.373 UPInt limit = end; 1.374 1.375 for(; i < limit; j = i, i++) 1.376 { 1.377 for(; less(arr[j + 1], arr[j]); j--) 1.378 { 1.379 Swap(arr[j + 1], arr[j]); 1.380 if(j <= start) 1.381 { 1.382 break; 1.383 } 1.384 } 1.385 } 1.386 } 1.387 1.388 1.389 //----------------------------------------------------------------------------------- 1.390 // ***** InsertionSortSliced 1.391 // 1.392 // Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe. 1.393 // The range is specified with start, end, where "end" is exclusive! 1.394 // The data type must have a defined "<" operator. 1.395 template<class Array> 1.396 void InsertionSortSliced(Array& arr, UPInt start, UPInt end) 1.397 { 1.398 typedef typename Array::ValueType ValueType; 1.399 InsertionSortSliced(arr, start, end, OperatorLess<ValueType>::Compare); 1.400 } 1.401 1.402 //----------------------------------------------------------------------------------- 1.403 // ***** InsertionSort 1.404 // 1.405 // Sort an array Array, ArrayPaged, ArrayUnsafe. 1.406 // The array must have GetSize() function. 1.407 // The comparison predicate must be specified. 1.408 1.409 template<class Array, class Less> 1.410 void InsertionSort(Array& arr, Less less) 1.411 { 1.412 InsertionSortSliced(arr, 0, arr.GetSize(), less); 1.413 } 1.414 1.415 //----------------------------------------------------------------------------------- 1.416 // ***** InsertionSort 1.417 // 1.418 // Sort an array Array, ArrayPaged, ArrayUnsafe. 1.419 // The array must have GetSize() function. 1.420 // The data type must have a defined "<" operator. 1.421 template<class Array> 1.422 void InsertionSort(Array& arr) 1.423 { 1.424 typedef typename Array::ValueType ValueType; 1.425 InsertionSortSliced(arr, 0, arr.GetSize(), OperatorLess<ValueType>::Compare); 1.426 } 1.427 1.428 1.429 1.430 //----------------------------------------------------------------------------------- 1.431 // ***** LowerBoundSliced 1.432 // 1.433 template<class Array, class Value, class Less> 1.434 UPInt LowerBoundSliced(const Array& arr, UPInt start, UPInt end, const Value& val, Less less) 1.435 { 1.436 SPInt first = (SPInt)start; 1.437 SPInt len = (SPInt)(end - start); 1.438 SPInt half; 1.439 SPInt middle; 1.440 1.441 while(len > 0) 1.442 { 1.443 half = len >> 1; 1.444 middle = first + half; 1.445 if(less(arr[middle], val)) 1.446 { 1.447 first = middle + 1; 1.448 len = len - half - 1; 1.449 } 1.450 else 1.451 { 1.452 len = half; 1.453 } 1.454 } 1.455 return (UPInt)first; 1.456 } 1.457 1.458 1.459 //----------------------------------------------------------------------------------- 1.460 // ***** LowerBoundSliced 1.461 // 1.462 template<class Array, class Value> 1.463 UPInt LowerBoundSliced(const Array& arr, UPInt start, UPInt end, const Value& val) 1.464 { 1.465 return LowerBoundSliced(arr, start, end, val, OperatorLess<Value>::Compare); 1.466 } 1.467 1.468 //----------------------------------------------------------------------------------- 1.469 // ***** LowerBoundSized 1.470 // 1.471 template<class Array, class Value> 1.472 UPInt LowerBoundSized(const Array& arr, UPInt size, const Value& val) 1.473 { 1.474 return LowerBoundSliced(arr, 0, size, val, OperatorLess<Value>::Compare); 1.475 } 1.476 1.477 //----------------------------------------------------------------------------------- 1.478 // ***** LowerBound 1.479 // 1.480 template<class Array, class Value, class Less> 1.481 UPInt LowerBound(const Array& arr, const Value& val, Less less) 1.482 { 1.483 return LowerBoundSliced(arr, 0, arr.GetSize(), val, less); 1.484 } 1.485 1.486 1.487 //----------------------------------------------------------------------------------- 1.488 // ***** LowerBound 1.489 // 1.490 template<class Array, class Value> 1.491 UPInt LowerBound(const Array& arr, const Value& val) 1.492 { 1.493 return LowerBoundSliced(arr, 0, arr.GetSize(), val, OperatorLess<Value>::Compare); 1.494 } 1.495 1.496 1.497 1.498 //----------------------------------------------------------------------------------- 1.499 // ***** UpperBoundSliced 1.500 // 1.501 template<class Array, class Value, class Less> 1.502 UPInt UpperBoundSliced(const Array& arr, UPInt start, UPInt end, const Value& val, Less less) 1.503 { 1.504 SPInt first = (SPInt)start; 1.505 SPInt len = (SPInt)(end - start); 1.506 SPInt half; 1.507 SPInt middle; 1.508 1.509 while(len > 0) 1.510 { 1.511 half = len >> 1; 1.512 middle = first + half; 1.513 if(less(val, arr[middle])) 1.514 { 1.515 len = half; 1.516 } 1.517 else 1.518 { 1.519 first = middle + 1; 1.520 len = len - half - 1; 1.521 } 1.522 } 1.523 return (UPInt)first; 1.524 } 1.525 1.526 1.527 //----------------------------------------------------------------------------------- 1.528 // ***** UpperBoundSliced 1.529 // 1.530 template<class Array, class Value> 1.531 UPInt UpperBoundSliced(const Array& arr, UPInt start, UPInt end, const Value& val) 1.532 { 1.533 return UpperBoundSliced(arr, start, end, val, OperatorLess<Value>::Compare); 1.534 } 1.535 1.536 1.537 //----------------------------------------------------------------------------------- 1.538 // ***** UpperBoundSized 1.539 // 1.540 template<class Array, class Value> 1.541 UPInt UpperBoundSized(const Array& arr, UPInt size, const Value& val) 1.542 { 1.543 return UpperBoundSliced(arr, 0, size, val, OperatorLess<Value>::Compare); 1.544 } 1.545 1.546 1.547 //----------------------------------------------------------------------------------- 1.548 // ***** UpperBound 1.549 // 1.550 template<class Array, class Value, class Less> 1.551 UPInt UpperBound(const Array& arr, const Value& val, Less less) 1.552 { 1.553 return UpperBoundSliced(arr, 0, arr.GetSize(), val, less); 1.554 } 1.555 1.556 1.557 //----------------------------------------------------------------------------------- 1.558 // ***** UpperBound 1.559 // 1.560 template<class Array, class Value> 1.561 UPInt UpperBound(const Array& arr, const Value& val) 1.562 { 1.563 return UpperBoundSliced(arr, 0, arr.GetSize(), val, OperatorLess<Value>::Compare); 1.564 } 1.565 1.566 1.567 //----------------------------------------------------------------------------------- 1.568 // ***** ReverseArray 1.569 // 1.570 template<class Array> void ReverseArray(Array& arr) 1.571 { 1.572 SPInt from = 0; 1.573 SPInt to = arr.GetSize() - 1; 1.574 while(from < to) 1.575 { 1.576 Swap(arr[from], arr[to]); 1.577 ++from; 1.578 --to; 1.579 } 1.580 } 1.581 1.582 1.583 // ***** AppendArray 1.584 // 1.585 template<class CDst, class CSrc> 1.586 void AppendArray(CDst& dst, const CSrc& src) 1.587 { 1.588 UPInt i; 1.589 for(i = 0; i < src.GetSize(); i++) 1.590 dst.PushBack(src[i]); 1.591 } 1.592 1.593 //----------------------------------------------------------------------------------- 1.594 // ***** ArrayAdaptor 1.595 // 1.596 // A simple adapter that provides the GetSize() method and overloads 1.597 // operator []. Used to wrap plain arrays in QuickSort and such. 1.598 template<class T> class ArrayAdaptor 1.599 { 1.600 public: 1.601 typedef T ValueType; 1.602 ArrayAdaptor() : Data(0), Size(0) {} 1.603 ArrayAdaptor(T* ptr, UPInt size) : Data(ptr), Size(size) {} 1.604 UPInt GetSize() const { return Size; } 1.605 const T& operator [] (UPInt i) const { return Data[i]; } 1.606 T& operator [] (UPInt i) { return Data[i]; } 1.607 private: 1.608 T* Data; 1.609 UPInt Size; 1.610 }; 1.611 1.612 1.613 //----------------------------------------------------------------------------------- 1.614 // ***** GConstArrayAdaptor 1.615 // 1.616 // A simple const adapter that provides the GetSize() method and overloads 1.617 // operator []. Used to wrap plain arrays in LowerBound and such. 1.618 template<class T> class ConstArrayAdaptor 1.619 { 1.620 public: 1.621 typedef T ValueType; 1.622 ConstArrayAdaptor() : Data(0), Size(0) {} 1.623 ConstArrayAdaptor(const T* ptr, UPInt size) : Data(ptr), Size(size) {} 1.624 UPInt GetSize() const { return Size; } 1.625 const T& operator [] (UPInt i) const { return Data[i]; } 1.626 private: 1.627 const T* Data; 1.628 UPInt Size; 1.629 }; 1.630 1.631 1.632 1.633 //----------------------------------------------------------------------------------- 1.634 extern const UByte UpperBitTable[256]; 1.635 extern const UByte LowerBitTable[256]; 1.636 1.637 1.638 1.639 //----------------------------------------------------------------------------------- 1.640 inline UByte UpperBit(UPInt val) 1.641 { 1.642 #ifndef OVR_64BIT_POINTERS 1.643 1.644 if (val & 0xFFFF0000) 1.645 { 1.646 return (val & 0xFF000000) ? 1.647 UpperBitTable[(val >> 24) ] + 24: 1.648 UpperBitTable[(val >> 16) & 0xFF] + 16; 1.649 } 1.650 return (val & 0xFF00) ? 1.651 UpperBitTable[(val >> 8) & 0xFF] + 8: 1.652 UpperBitTable[(val ) & 0xFF]; 1.653 1.654 #else 1.655 1.656 if (val & 0xFFFFFFFF00000000) 1.657 { 1.658 if (val & 0xFFFF000000000000) 1.659 { 1.660 return (val & 0xFF00000000000000) ? 1.661 UpperBitTable[(val >> 56) ] + 56: 1.662 UpperBitTable[(val >> 48) & 0xFF] + 48; 1.663 } 1.664 return (val & 0xFF0000000000) ? 1.665 UpperBitTable[(val >> 40) & 0xFF] + 40: 1.666 UpperBitTable[(val >> 32) & 0xFF] + 32; 1.667 } 1.668 else 1.669 { 1.670 if (val & 0xFFFF0000) 1.671 { 1.672 return (val & 0xFF000000) ? 1.673 UpperBitTable[(val >> 24) ] + 24: 1.674 UpperBitTable[(val >> 16) & 0xFF] + 16; 1.675 } 1.676 return (val & 0xFF00) ? 1.677 UpperBitTable[(val >> 8) & 0xFF] + 8: 1.678 UpperBitTable[(val ) & 0xFF]; 1.679 } 1.680 1.681 #endif 1.682 } 1.683 1.684 //----------------------------------------------------------------------------------- 1.685 inline UByte LowerBit(UPInt val) 1.686 { 1.687 #ifndef OVR_64BIT_POINTERS 1.688 1.689 if (val & 0xFFFF) 1.690 { 1.691 return (val & 0xFF) ? 1.692 LowerBitTable[ val & 0xFF]: 1.693 LowerBitTable[(val >> 8) & 0xFF] + 8; 1.694 } 1.695 return (val & 0xFF0000) ? 1.696 LowerBitTable[(val >> 16) & 0xFF] + 16: 1.697 LowerBitTable[(val >> 24) & 0xFF] + 24; 1.698 1.699 #else 1.700 1.701 if (val & 0xFFFFFFFF) 1.702 { 1.703 if (val & 0xFFFF) 1.704 { 1.705 return (val & 0xFF) ? 1.706 LowerBitTable[ val & 0xFF]: 1.707 LowerBitTable[(val >> 8) & 0xFF] + 8; 1.708 } 1.709 return (val & 0xFF0000) ? 1.710 LowerBitTable[(val >> 16) & 0xFF] + 16: 1.711 LowerBitTable[(val >> 24) & 0xFF] + 24; 1.712 } 1.713 else 1.714 { 1.715 if (val & 0xFFFF00000000) 1.716 { 1.717 return (val & 0xFF00000000) ? 1.718 LowerBitTable[(val >> 32) & 0xFF] + 32: 1.719 LowerBitTable[(val >> 40) & 0xFF] + 40; 1.720 } 1.721 return (val & 0xFF000000000000) ? 1.722 LowerBitTable[(val >> 48) & 0xFF] + 48: 1.723 LowerBitTable[(val >> 56) & 0xFF] + 56; 1.724 } 1.725 1.726 #endif 1.727 } 1.728 1.729 1.730 1.731 // ******* Special (optimized) memory routines 1.732 // Note: null (bad) pointer is not tested 1.733 class MemUtil 1.734 { 1.735 public: 1.736 1.737 // Memory compare 1.738 static int Cmp (const void* p1, const void* p2, UPInt byteCount) { return memcmp(p1, p2, byteCount); } 1.739 static int Cmp16(const void* p1, const void* p2, UPInt int16Count); 1.740 static int Cmp32(const void* p1, const void* p2, UPInt int32Count); 1.741 static int Cmp64(const void* p1, const void* p2, UPInt int64Count); 1.742 }; 1.743 1.744 // ** Inline Implementation 1.745 1.746 inline int MemUtil::Cmp16(const void* p1, const void* p2, UPInt int16Count) 1.747 { 1.748 SInt16* pa = (SInt16*)p1; 1.749 SInt16* pb = (SInt16*)p2; 1.750 unsigned ic = 0; 1.751 if (int16Count == 0) 1.752 return 0; 1.753 while (pa[ic] == pb[ic]) 1.754 if (++ic==int16Count) 1.755 return 0; 1.756 return pa[ic] > pb[ic] ? 1 : -1; 1.757 } 1.758 inline int MemUtil::Cmp32(const void* p1, const void* p2, UPInt int32Count) 1.759 { 1.760 SInt32* pa = (SInt32*)p1; 1.761 SInt32* pb = (SInt32*)p2; 1.762 unsigned ic = 0; 1.763 if (int32Count == 0) 1.764 return 0; 1.765 while (pa[ic] == pb[ic]) 1.766 if (++ic==int32Count) 1.767 return 0; 1.768 return pa[ic] > pb[ic] ? 1 : -1; 1.769 } 1.770 inline int MemUtil::Cmp64(const void* p1, const void* p2, UPInt int64Count) 1.771 { 1.772 SInt64* pa = (SInt64*)p1; 1.773 SInt64* pb = (SInt64*)p2; 1.774 unsigned ic = 0; 1.775 if (int64Count == 0) 1.776 return 0; 1.777 while (pa[ic] == pb[ic]) 1.778 if (++ic==int64Count) 1.779 return 0; 1.780 return pa[ic] > pb[ic] ? 1 : -1; 1.781 } 1.782 1.783 // ** End Inline Implementation 1.784 1.785 1.786 //----------------------------------------------------------------------------------- 1.787 // ******* Byte Order Conversions 1.788 namespace ByteUtil { 1.789 1.790 // *** Swap Byte Order 1.791 1.792 // Swap the byte order of a byte array 1.793 inline void SwapOrder(void* pv, int size) 1.794 { 1.795 UByte* pb = (UByte*)pv; 1.796 UByte temp; 1.797 for (int i = 0; i < size>>1; i++) 1.798 { 1.799 temp = pb[size-1-i]; 1.800 pb[size-1-i] = pb[i]; 1.801 pb[i] = temp; 1.802 } 1.803 } 1.804 1.805 // Swap the byte order of primitive types 1.806 inline UByte SwapOrder(UByte v) { return v; } 1.807 inline SByte SwapOrder(SByte v) { return v; } 1.808 inline UInt16 SwapOrder(UInt16 v) { return UInt16(v>>8)|UInt16(v<<8); } 1.809 inline SInt16 SwapOrder(SInt16 v) { return SInt16((UInt16(v)>>8)|(v<<8)); } 1.810 inline UInt32 SwapOrder(UInt32 v) { return (v>>24)|((v&0x00FF0000)>>8)|((v&0x0000FF00)<<8)|(v<<24); } 1.811 inline SInt32 SwapOrder(SInt32 p) { return (SInt32)SwapOrder(UInt32(p)); } 1.812 inline UInt64 SwapOrder(UInt64 v) 1.813 { 1.814 return (v>>56) | 1.815 ((v&UInt64(0x00FF000000000000))>>40) | 1.816 ((v&UInt64(0x0000FF0000000000))>>24) | 1.817 ((v&UInt64(0x000000FF00000000))>>8) | 1.818 ((v&UInt64(0x00000000FF000000))<<8) | 1.819 ((v&UInt64(0x0000000000FF0000))<<24) | 1.820 ((v&UInt64(0x000000000000FF00))<<40) | 1.821 (v<<56); 1.822 } 1.823 inline SInt64 SwapOrder(SInt64 v) { return (SInt64)SwapOrder(UInt64(v)); } 1.824 inline float SwapOrder(float p) 1.825 { 1.826 union { 1.827 float p; 1.828 UInt32 v; 1.829 } u; 1.830 u.p = p; 1.831 u.v = SwapOrder(u.v); 1.832 return u.p; 1.833 } 1.834 1.835 inline double SwapOrder(double p) 1.836 { 1.837 union { 1.838 double p; 1.839 UInt64 v; 1.840 } u; 1.841 u.p = p; 1.842 u.v = SwapOrder(u.v); 1.843 return u.p; 1.844 } 1.845 1.846 // *** Byte-order conversion 1.847 1.848 #if (OVR_BYTE_ORDER == OVR_LITTLE_ENDIAN) 1.849 // Little Endian to System (LE) 1.850 inline UByte LEToSystem(UByte v) { return v; } 1.851 inline SByte LEToSystem(SByte v) { return v; } 1.852 inline UInt16 LEToSystem(UInt16 v) { return v; } 1.853 inline SInt16 LEToSystem(SInt16 v) { return v; } 1.854 inline UInt32 LEToSystem(UInt32 v) { return v; } 1.855 inline SInt32 LEToSystem(SInt32 v) { return v; } 1.856 inline UInt64 LEToSystem(UInt64 v) { return v; } 1.857 inline SInt64 LEToSystem(SInt64 v) { return v; } 1.858 inline float LEToSystem(float v) { return v; } 1.859 inline double LEToSystem(double v) { return v; } 1.860 1.861 // Big Endian to System (LE) 1.862 inline UByte BEToSystem(UByte v) { return SwapOrder(v); } 1.863 inline SByte BEToSystem(SByte v) { return SwapOrder(v); } 1.864 inline UInt16 BEToSystem(UInt16 v) { return SwapOrder(v); } 1.865 inline SInt16 BEToSystem(SInt16 v) { return SwapOrder(v); } 1.866 inline UInt32 BEToSystem(UInt32 v) { return SwapOrder(v); } 1.867 inline SInt32 BEToSystem(SInt32 v) { return SwapOrder(v); } 1.868 inline UInt64 BEToSystem(UInt64 v) { return SwapOrder(v); } 1.869 inline SInt64 BEToSystem(SInt64 v) { return SwapOrder(v); } 1.870 inline float BEToSystem(float v) { return SwapOrder(v); } 1.871 inline double BEToSystem(double v) { return SwapOrder(v); } 1.872 1.873 // System (LE) to Little Endian 1.874 inline UByte SystemToLE(UByte v) { return v; } 1.875 inline SByte SystemToLE(SByte v) { return v; } 1.876 inline UInt16 SystemToLE(UInt16 v) { return v; } 1.877 inline SInt16 SystemToLE(SInt16 v) { return v; } 1.878 inline UInt32 SystemToLE(UInt32 v) { return v; } 1.879 inline SInt32 SystemToLE(SInt32 v) { return v; } 1.880 inline UInt64 SystemToLE(UInt64 v) { return v; } 1.881 inline SInt64 SystemToLE(SInt64 v) { return v; } 1.882 inline float SystemToLE(float v) { return v; } 1.883 inline double SystemToLE(double v) { return v; } 1.884 1.885 // System (LE) to Big Endian 1.886 inline UByte SystemToBE(UByte v) { return SwapOrder(v); } 1.887 inline SByte SystemToBE(SByte v) { return SwapOrder(v); } 1.888 inline UInt16 SystemToBE(UInt16 v) { return SwapOrder(v); } 1.889 inline SInt16 SystemToBE(SInt16 v) { return SwapOrder(v); } 1.890 inline UInt32 SystemToBE(UInt32 v) { return SwapOrder(v); } 1.891 inline SInt32 SystemToBE(SInt32 v) { return SwapOrder(v); } 1.892 inline UInt64 SystemToBE(UInt64 v) { return SwapOrder(v); } 1.893 inline SInt64 SystemToBE(SInt64 v) { return SwapOrder(v); } 1.894 inline float SystemToBE(float v) { return SwapOrder(v); } 1.895 inline double SystemToBE(double v) { return SwapOrder(v); } 1.896 1.897 #elif (OVR_BYTE_ORDER == OVR_BIG_ENDIAN) 1.898 // Little Endian to System (BE) 1.899 inline UByte LEToSystem(UByte v) { return SwapOrder(v); } 1.900 inline SByte LEToSystem(SByte v) { return SwapOrder(v); } 1.901 inline UInt16 LEToSystem(UInt16 v) { return SwapOrder(v); } 1.902 inline SInt16 LEToSystem(SInt16 v) { return SwapOrder(v); } 1.903 inline UInt32 LEToSystem(UInt32 v) { return SwapOrder(v); } 1.904 inline SInt32 LEToSystem(SInt32 v) { return SwapOrder(v); } 1.905 inline UInt64 LEToSystem(UInt64 v) { return SwapOrder(v); } 1.906 inline SInt64 LEToSystem(SInt64 v) { return SwapOrder(v); } 1.907 inline float LEToSystem(float v) { return SwapOrder(v); } 1.908 inline double LEToSystem(double v) { return SwapOrder(v); } 1.909 1.910 // Big Endian to System (BE) 1.911 inline UByte BEToSystem(UByte v) { return v; } 1.912 inline SByte BEToSystem(SByte v) { return v; } 1.913 inline UInt16 BEToSystem(UInt16 v) { return v; } 1.914 inline SInt16 BEToSystem(SInt16 v) { return v; } 1.915 inline UInt32 BEToSystem(UInt32 v) { return v; } 1.916 inline SInt32 BEToSystem(SInt32 v) { return v; } 1.917 inline UInt64 BEToSystem(UInt64 v) { return v; } 1.918 inline SInt64 BEToSystem(SInt64 v) { return v; } 1.919 inline float BEToSystem(float v) { return v; } 1.920 inline double BEToSystem(double v) { return v; } 1.921 1.922 // System (BE) to Little Endian 1.923 inline UByte SystemToLE(UByte v) { return SwapOrder(v); } 1.924 inline SByte SystemToLE(SByte v) { return SwapOrder(v); } 1.925 inline UInt16 SystemToLE(UInt16 v) { return SwapOrder(v); } 1.926 inline SInt16 SystemToLE(SInt16 v) { return SwapOrder(v); } 1.927 inline UInt32 SystemToLE(UInt32 v) { return SwapOrder(v); } 1.928 inline SInt32 SystemToLE(SInt32 v) { return SwapOrder(v); } 1.929 inline UInt64 SystemToLE(UInt64 v) { return SwapOrder(v); } 1.930 inline SInt64 SystemToLE(SInt64 v) { return SwapOrder(v); } 1.931 inline float SystemToLE(float v) { return SwapOrder(v); } 1.932 inline double SystemToLE(double v) { return SwapOrder(v); } 1.933 1.934 // System (BE) to Big Endian 1.935 inline UByte SystemToBE(UByte v) { return v; } 1.936 inline SByte SystemToBE(SByte v) { return v; } 1.937 inline UInt16 SystemToBE(UInt16 v) { return v; } 1.938 inline SInt16 SystemToBE(SInt16 v) { return v; } 1.939 inline UInt32 SystemToBE(UInt32 v) { return v; } 1.940 inline SInt32 SystemToBE(SInt32 v) { return v; } 1.941 inline UInt64 SystemToBE(UInt64 v) { return v; } 1.942 inline SInt64 SystemToBE(SInt64 v) { return v; } 1.943 inline float SystemToBE(float v) { return v; } 1.944 inline double SystemToBE(double v) { return v; } 1.945 1.946 #else 1.947 #error "OVR_BYTE_ORDER must be defined to OVR_LITTLE_ENDIAN or OVR_BIG_ENDIAN" 1.948 #endif 1.949 1.950 } // namespace ByteUtil 1.951 1.952 1.953 1.954 }} // OVR::Alg 1.955 1.956 #endif 1.957 \ No newline at end of file 1.958 +/************************************************************************************ 1.959 + 1.960 +PublicHeader: OVR.h 1.961 +Filename : OVR_Alg.h 1.962 +Content : Simple general purpose algorithms: Sort, Binary Search, etc. 1.963 +Created : September 19, 2012 1.964 +Notes : 1.965 + 1.966 +Copyright : Copyright 2012 Oculus VR, Inc. All Rights reserved. 1.967 + 1.968 +Use of this software is subject to the terms of the Oculus license 1.969 +agreement provided at the time of installation or download, or which 1.970 +otherwise accompanies this software in either electronic or hard copy form. 1.971 + 1.972 +************************************************************************************/ 1.973 + 1.974 +#ifndef OVR_Alg_h 1.975 +#define OVR_Alg_h 1.976 + 1.977 +#include "OVR_Types.h" 1.978 +#include <string.h> 1.979 + 1.980 +namespace OVR { namespace Alg { 1.981 + 1.982 + 1.983 +//----------------------------------------------------------------------------------- 1.984 +// ***** Operator extensions 1.985 + 1.986 +template <typename T> OVR_FORCE_INLINE void Swap(T &a, T &b) 1.987 +{ T temp(a); a = b; b = temp; } 1.988 + 1.989 + 1.990 +// ***** min/max are not implemented in Visual Studio 6 standard STL 1.991 + 1.992 +template <typename T> OVR_FORCE_INLINE const T Min(const T a, const T b) 1.993 +{ return (a < b) ? a : b; } 1.994 + 1.995 +template <typename T> OVR_FORCE_INLINE const T Max(const T a, const T b) 1.996 +{ return (b < a) ? a : b; } 1.997 + 1.998 +template <typename T> OVR_FORCE_INLINE const T Clamp(const T v, const T minVal, const T maxVal) 1.999 +{ return Max<T>(minVal, Min<T>(v, maxVal)); } 1.1000 + 1.1001 +template <typename T> OVR_FORCE_INLINE int Chop(T f) 1.1002 +{ return (int)f; } 1.1003 + 1.1004 +template <typename T> OVR_FORCE_INLINE T Lerp(T a, T b, T f) 1.1005 +{ return (b - a) * f + a; } 1.1006 + 1.1007 + 1.1008 +// These functions stand to fix a stupid VC++ warning (with /Wp64 on): 1.1009 +// "warning C4267: 'argument' : conversion from 'size_t' to 'const unsigned', possible loss of data" 1.1010 +// Use these functions instead of gmin/gmax if the argument has size 1.1011 +// of the pointer to avoid the warning. Though, functionally they are 1.1012 +// absolutelly the same as regular gmin/gmax. 1.1013 +template <typename T> OVR_FORCE_INLINE const T PMin(const T a, const T b) 1.1014 +{ 1.1015 + OVR_COMPILER_ASSERT(sizeof(T) == sizeof(UPInt)); 1.1016 + return (a < b) ? a : b; 1.1017 +} 1.1018 +template <typename T> OVR_FORCE_INLINE const T PMax(const T a, const T b) 1.1019 +{ 1.1020 + OVR_COMPILER_ASSERT(sizeof(T) == sizeof(UPInt)); 1.1021 + return (b < a) ? a : b; 1.1022 +} 1.1023 + 1.1024 + 1.1025 +template <typename T> OVR_FORCE_INLINE const T Abs(const T v) 1.1026 +{ return (v>=0) ? v : -v; } 1.1027 + 1.1028 + 1.1029 +//----------------------------------------------------------------------------------- 1.1030 +// ***** OperatorLess 1.1031 +// 1.1032 +template<class T> struct OperatorLess 1.1033 +{ 1.1034 + static bool Compare(const T& a, const T& b) 1.1035 + { 1.1036 + return a < b; 1.1037 + } 1.1038 +}; 1.1039 + 1.1040 + 1.1041 +//----------------------------------------------------------------------------------- 1.1042 +// ***** QuickSortSliced 1.1043 +// 1.1044 +// Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe. 1.1045 +// The range is specified with start, end, where "end" is exclusive! 1.1046 +// The comparison predicate must be specified. 1.1047 +template<class Array, class Less> 1.1048 +void QuickSortSliced(Array& arr, UPInt start, UPInt end, Less less) 1.1049 +{ 1.1050 + enum 1.1051 + { 1.1052 + Threshold = 9 1.1053 + }; 1.1054 + 1.1055 + if(end - start < 2) return; 1.1056 + 1.1057 + SPInt stack[80]; 1.1058 + SPInt* top = stack; 1.1059 + SPInt base = (SPInt)start; 1.1060 + SPInt limit = (SPInt)end; 1.1061 + 1.1062 + for(;;) 1.1063 + { 1.1064 + SPInt len = limit - base; 1.1065 + SPInt i, j, pivot; 1.1066 + 1.1067 + if(len > Threshold) 1.1068 + { 1.1069 + // we use base + len/2 as the pivot 1.1070 + pivot = base + len / 2; 1.1071 + Swap(arr[base], arr[pivot]); 1.1072 + 1.1073 + i = base + 1; 1.1074 + j = limit - 1; 1.1075 + 1.1076 + // now ensure that *i <= *base <= *j 1.1077 + if(less(arr[j], arr[i])) Swap(arr[j], arr[i]); 1.1078 + if(less(arr[base], arr[i])) Swap(arr[base], arr[i]); 1.1079 + if(less(arr[j], arr[base])) Swap(arr[j], arr[base]); 1.1080 + 1.1081 + for(;;) 1.1082 + { 1.1083 + do i++; while( less(arr[i], arr[base]) ); 1.1084 + do j--; while( less(arr[base], arr[j]) ); 1.1085 + 1.1086 + if( i > j ) 1.1087 + { 1.1088 + break; 1.1089 + } 1.1090 + 1.1091 + Swap(arr[i], arr[j]); 1.1092 + } 1.1093 + 1.1094 + Swap(arr[base], arr[j]); 1.1095 + 1.1096 + // now, push the largest sub-array 1.1097 + if(j - base > limit - i) 1.1098 + { 1.1099 + top[0] = base; 1.1100 + top[1] = j; 1.1101 + base = i; 1.1102 + } 1.1103 + else 1.1104 + { 1.1105 + top[0] = i; 1.1106 + top[1] = limit; 1.1107 + limit = j; 1.1108 + } 1.1109 + top += 2; 1.1110 + } 1.1111 + else 1.1112 + { 1.1113 + // the sub-array is small, perform insertion sort 1.1114 + j = base; 1.1115 + i = j + 1; 1.1116 + 1.1117 + for(; i < limit; j = i, i++) 1.1118 + { 1.1119 + for(; less(arr[j + 1], arr[j]); j--) 1.1120 + { 1.1121 + Swap(arr[j + 1], arr[j]); 1.1122 + if(j == base) 1.1123 + { 1.1124 + break; 1.1125 + } 1.1126 + } 1.1127 + } 1.1128 + if(top > stack) 1.1129 + { 1.1130 + top -= 2; 1.1131 + base = top[0]; 1.1132 + limit = top[1]; 1.1133 + } 1.1134 + else 1.1135 + { 1.1136 + break; 1.1137 + } 1.1138 + } 1.1139 + } 1.1140 +} 1.1141 + 1.1142 + 1.1143 +//----------------------------------------------------------------------------------- 1.1144 +// ***** QuickSortSliced 1.1145 +// 1.1146 +// Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe. 1.1147 +// The range is specified with start, end, where "end" is exclusive! 1.1148 +// The data type must have a defined "<" operator. 1.1149 +template<class Array> 1.1150 +void QuickSortSliced(Array& arr, UPInt start, UPInt end) 1.1151 +{ 1.1152 + typedef typename Array::ValueType ValueType; 1.1153 + QuickSortSliced(arr, start, end, OperatorLess<ValueType>::Compare); 1.1154 +} 1.1155 + 1.1156 +// Same as corresponding G_QuickSortSliced but with checking array limits to avoid 1.1157 +// crash in the case of wrong comparator functor. 1.1158 +template<class Array, class Less> 1.1159 +bool QuickSortSlicedSafe(Array& arr, UPInt start, UPInt end, Less less) 1.1160 +{ 1.1161 + enum 1.1162 + { 1.1163 + Threshold = 9 1.1164 + }; 1.1165 + 1.1166 + if(end - start < 2) return true; 1.1167 + 1.1168 + SPInt stack[80]; 1.1169 + SPInt* top = stack; 1.1170 + SPInt base = (SPInt)start; 1.1171 + SPInt limit = (SPInt)end; 1.1172 + 1.1173 + for(;;) 1.1174 + { 1.1175 + SPInt len = limit - base; 1.1176 + SPInt i, j, pivot; 1.1177 + 1.1178 + if(len > Threshold) 1.1179 + { 1.1180 + // we use base + len/2 as the pivot 1.1181 + pivot = base + len / 2; 1.1182 + Swap(arr[base], arr[pivot]); 1.1183 + 1.1184 + i = base + 1; 1.1185 + j = limit - 1; 1.1186 + 1.1187 + // now ensure that *i <= *base <= *j 1.1188 + if(less(arr[j], arr[i])) Swap(arr[j], arr[i]); 1.1189 + if(less(arr[base], arr[i])) Swap(arr[base], arr[i]); 1.1190 + if(less(arr[j], arr[base])) Swap(arr[j], arr[base]); 1.1191 + 1.1192 + for(;;) 1.1193 + { 1.1194 + do 1.1195 + { 1.1196 + i++; 1.1197 + if (i >= limit) 1.1198 + return false; 1.1199 + } while( less(arr[i], arr[base]) ); 1.1200 + do 1.1201 + { 1.1202 + j--; 1.1203 + if (j < 0) 1.1204 + return false; 1.1205 + } while( less(arr[base], arr[j]) ); 1.1206 + 1.1207 + if( i > j ) 1.1208 + { 1.1209 + break; 1.1210 + } 1.1211 + 1.1212 + Swap(arr[i], arr[j]); 1.1213 + } 1.1214 + 1.1215 + Swap(arr[base], arr[j]); 1.1216 + 1.1217 + // now, push the largest sub-array 1.1218 + if(j - base > limit - i) 1.1219 + { 1.1220 + top[0] = base; 1.1221 + top[1] = j; 1.1222 + base = i; 1.1223 + } 1.1224 + else 1.1225 + { 1.1226 + top[0] = i; 1.1227 + top[1] = limit; 1.1228 + limit = j; 1.1229 + } 1.1230 + top += 2; 1.1231 + } 1.1232 + else 1.1233 + { 1.1234 + // the sub-array is small, perform insertion sort 1.1235 + j = base; 1.1236 + i = j + 1; 1.1237 + 1.1238 + for(; i < limit; j = i, i++) 1.1239 + { 1.1240 + for(; less(arr[j + 1], arr[j]); j--) 1.1241 + { 1.1242 + Swap(arr[j + 1], arr[j]); 1.1243 + if(j == base) 1.1244 + { 1.1245 + break; 1.1246 + } 1.1247 + } 1.1248 + } 1.1249 + if(top > stack) 1.1250 + { 1.1251 + top -= 2; 1.1252 + base = top[0]; 1.1253 + limit = top[1]; 1.1254 + } 1.1255 + else 1.1256 + { 1.1257 + break; 1.1258 + } 1.1259 + } 1.1260 + } 1.1261 + return true; 1.1262 +} 1.1263 + 1.1264 +template<class Array> 1.1265 +bool QuickSortSlicedSafe(Array& arr, UPInt start, UPInt end) 1.1266 +{ 1.1267 + typedef typename Array::ValueType ValueType; 1.1268 + return QuickSortSlicedSafe(arr, start, end, OperatorLess<ValueType>::Compare); 1.1269 +} 1.1270 + 1.1271 +//----------------------------------------------------------------------------------- 1.1272 +// ***** QuickSort 1.1273 +// 1.1274 +// Sort an array Array, ArrayPaged, ArrayUnsafe. 1.1275 +// The array must have GetSize() function. 1.1276 +// The comparison predicate must be specified. 1.1277 +template<class Array, class Less> 1.1278 +void QuickSort(Array& arr, Less less) 1.1279 +{ 1.1280 + QuickSortSliced(arr, 0, arr.GetSize(), less); 1.1281 +} 1.1282 + 1.1283 +// checks for boundaries 1.1284 +template<class Array, class Less> 1.1285 +bool QuickSortSafe(Array& arr, Less less) 1.1286 +{ 1.1287 + return QuickSortSlicedSafe(arr, 0, arr.GetSize(), less); 1.1288 +} 1.1289 + 1.1290 + 1.1291 +//----------------------------------------------------------------------------------- 1.1292 +// ***** QuickSort 1.1293 +// 1.1294 +// Sort an array Array, ArrayPaged, ArrayUnsafe. 1.1295 +// The array must have GetSize() function. 1.1296 +// The data type must have a defined "<" operator. 1.1297 +template<class Array> 1.1298 +void QuickSort(Array& arr) 1.1299 +{ 1.1300 + typedef typename Array::ValueType ValueType; 1.1301 + QuickSortSliced(arr, 0, arr.GetSize(), OperatorLess<ValueType>::Compare); 1.1302 +} 1.1303 + 1.1304 +template<class Array> 1.1305 +bool QuickSortSafe(Array& arr) 1.1306 +{ 1.1307 + typedef typename Array::ValueType ValueType; 1.1308 + return QuickSortSlicedSafe(arr, 0, arr.GetSize(), OperatorLess<ValueType>::Compare); 1.1309 +} 1.1310 + 1.1311 +//----------------------------------------------------------------------------------- 1.1312 +// ***** InsertionSortSliced 1.1313 +// 1.1314 +// Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe. 1.1315 +// The range is specified with start, end, where "end" is exclusive! 1.1316 +// The comparison predicate must be specified. 1.1317 +// Unlike Quick Sort, the Insertion Sort works much slower in average, 1.1318 +// but may be much faster on almost sorted arrays. Besides, it guarantees 1.1319 +// that the elements will not be swapped if not necessary. For example, 1.1320 +// an array with all equal elements will remain "untouched", while 1.1321 +// Quick Sort will considerably shuffle the elements in this case. 1.1322 +template<class Array, class Less> 1.1323 +void InsertionSortSliced(Array& arr, UPInt start, UPInt end, Less less) 1.1324 +{ 1.1325 + UPInt j = start; 1.1326 + UPInt i = j + 1; 1.1327 + UPInt limit = end; 1.1328 + 1.1329 + for(; i < limit; j = i, i++) 1.1330 + { 1.1331 + for(; less(arr[j + 1], arr[j]); j--) 1.1332 + { 1.1333 + Swap(arr[j + 1], arr[j]); 1.1334 + if(j <= start) 1.1335 + { 1.1336 + break; 1.1337 + } 1.1338 + } 1.1339 + } 1.1340 +} 1.1341 + 1.1342 + 1.1343 +//----------------------------------------------------------------------------------- 1.1344 +// ***** InsertionSortSliced 1.1345 +// 1.1346 +// Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe. 1.1347 +// The range is specified with start, end, where "end" is exclusive! 1.1348 +// The data type must have a defined "<" operator. 1.1349 +template<class Array> 1.1350 +void InsertionSortSliced(Array& arr, UPInt start, UPInt end) 1.1351 +{ 1.1352 + typedef typename Array::ValueType ValueType; 1.1353 + InsertionSortSliced(arr, start, end, OperatorLess<ValueType>::Compare); 1.1354 +} 1.1355 + 1.1356 +//----------------------------------------------------------------------------------- 1.1357 +// ***** InsertionSort 1.1358 +// 1.1359 +// Sort an array Array, ArrayPaged, ArrayUnsafe. 1.1360 +// The array must have GetSize() function. 1.1361 +// The comparison predicate must be specified. 1.1362 + 1.1363 +template<class Array, class Less> 1.1364 +void InsertionSort(Array& arr, Less less) 1.1365 +{ 1.1366 + InsertionSortSliced(arr, 0, arr.GetSize(), less); 1.1367 +} 1.1368 + 1.1369 +//----------------------------------------------------------------------------------- 1.1370 +// ***** InsertionSort 1.1371 +// 1.1372 +// Sort an array Array, ArrayPaged, ArrayUnsafe. 1.1373 +// The array must have GetSize() function. 1.1374 +// The data type must have a defined "<" operator. 1.1375 +template<class Array> 1.1376 +void InsertionSort(Array& arr) 1.1377 +{ 1.1378 + typedef typename Array::ValueType ValueType; 1.1379 + InsertionSortSliced(arr, 0, arr.GetSize(), OperatorLess<ValueType>::Compare); 1.1380 +} 1.1381 + 1.1382 + 1.1383 + 1.1384 +//----------------------------------------------------------------------------------- 1.1385 +// ***** LowerBoundSliced 1.1386 +// 1.1387 +template<class Array, class Value, class Less> 1.1388 +UPInt LowerBoundSliced(const Array& arr, UPInt start, UPInt end, const Value& val, Less less) 1.1389 +{ 1.1390 + SPInt first = (SPInt)start; 1.1391 + SPInt len = (SPInt)(end - start); 1.1392 + SPInt half; 1.1393 + SPInt middle; 1.1394 + 1.1395 + while(len > 0) 1.1396 + { 1.1397 + half = len >> 1; 1.1398 + middle = first + half; 1.1399 + if(less(arr[middle], val)) 1.1400 + { 1.1401 + first = middle + 1; 1.1402 + len = len - half - 1; 1.1403 + } 1.1404 + else 1.1405 + { 1.1406 + len = half; 1.1407 + } 1.1408 + } 1.1409 + return (UPInt)first; 1.1410 +} 1.1411 + 1.1412 + 1.1413 +//----------------------------------------------------------------------------------- 1.1414 +// ***** LowerBoundSliced 1.1415 +// 1.1416 +template<class Array, class Value> 1.1417 +UPInt LowerBoundSliced(const Array& arr, UPInt start, UPInt end, const Value& val) 1.1418 +{ 1.1419 + return LowerBoundSliced(arr, start, end, val, OperatorLess<Value>::Compare); 1.1420 +} 1.1421 + 1.1422 +//----------------------------------------------------------------------------------- 1.1423 +// ***** LowerBoundSized 1.1424 +// 1.1425 +template<class Array, class Value> 1.1426 +UPInt LowerBoundSized(const Array& arr, UPInt size, const Value& val) 1.1427 +{ 1.1428 + return LowerBoundSliced(arr, 0, size, val, OperatorLess<Value>::Compare); 1.1429 +} 1.1430 + 1.1431 +//----------------------------------------------------------------------------------- 1.1432 +// ***** LowerBound 1.1433 +// 1.1434 +template<class Array, class Value, class Less> 1.1435 +UPInt LowerBound(const Array& arr, const Value& val, Less less) 1.1436 +{ 1.1437 + return LowerBoundSliced(arr, 0, arr.GetSize(), val, less); 1.1438 +} 1.1439 + 1.1440 + 1.1441 +//----------------------------------------------------------------------------------- 1.1442 +// ***** LowerBound 1.1443 +// 1.1444 +template<class Array, class Value> 1.1445 +UPInt LowerBound(const Array& arr, const Value& val) 1.1446 +{ 1.1447 + return LowerBoundSliced(arr, 0, arr.GetSize(), val, OperatorLess<Value>::Compare); 1.1448 +} 1.1449 + 1.1450 + 1.1451 + 1.1452 +//----------------------------------------------------------------------------------- 1.1453 +// ***** UpperBoundSliced 1.1454 +// 1.1455 +template<class Array, class Value, class Less> 1.1456 +UPInt UpperBoundSliced(const Array& arr, UPInt start, UPInt end, const Value& val, Less less) 1.1457 +{ 1.1458 + SPInt first = (SPInt)start; 1.1459 + SPInt len = (SPInt)(end - start); 1.1460 + SPInt half; 1.1461 + SPInt middle; 1.1462 + 1.1463 + while(len > 0) 1.1464 + { 1.1465 + half = len >> 1; 1.1466 + middle = first + half; 1.1467 + if(less(val, arr[middle])) 1.1468 + { 1.1469 + len = half; 1.1470 + } 1.1471 + else 1.1472 + { 1.1473 + first = middle + 1; 1.1474 + len = len - half - 1; 1.1475 + } 1.1476 + } 1.1477 + return (UPInt)first; 1.1478 +} 1.1479 + 1.1480 + 1.1481 +//----------------------------------------------------------------------------------- 1.1482 +// ***** UpperBoundSliced 1.1483 +// 1.1484 +template<class Array, class Value> 1.1485 +UPInt UpperBoundSliced(const Array& arr, UPInt start, UPInt end, const Value& val) 1.1486 +{ 1.1487 + return UpperBoundSliced(arr, start, end, val, OperatorLess<Value>::Compare); 1.1488 +} 1.1489 + 1.1490 + 1.1491 +//----------------------------------------------------------------------------------- 1.1492 +// ***** UpperBoundSized 1.1493 +// 1.1494 +template<class Array, class Value> 1.1495 +UPInt UpperBoundSized(const Array& arr, UPInt size, const Value& val) 1.1496 +{ 1.1497 + return UpperBoundSliced(arr, 0, size, val, OperatorLess<Value>::Compare); 1.1498 +} 1.1499 + 1.1500 + 1.1501 +//----------------------------------------------------------------------------------- 1.1502 +// ***** UpperBound 1.1503 +// 1.1504 +template<class Array, class Value, class Less> 1.1505 +UPInt UpperBound(const Array& arr, const Value& val, Less less) 1.1506 +{ 1.1507 + return UpperBoundSliced(arr, 0, arr.GetSize(), val, less); 1.1508 +} 1.1509 + 1.1510 + 1.1511 +//----------------------------------------------------------------------------------- 1.1512 +// ***** UpperBound 1.1513 +// 1.1514 +template<class Array, class Value> 1.1515 +UPInt UpperBound(const Array& arr, const Value& val) 1.1516 +{ 1.1517 + return UpperBoundSliced(arr, 0, arr.GetSize(), val, OperatorLess<Value>::Compare); 1.1518 +} 1.1519 + 1.1520 + 1.1521 +//----------------------------------------------------------------------------------- 1.1522 +// ***** ReverseArray 1.1523 +// 1.1524 +template<class Array> void ReverseArray(Array& arr) 1.1525 +{ 1.1526 + SPInt from = 0; 1.1527 + SPInt to = arr.GetSize() - 1; 1.1528 + while(from < to) 1.1529 + { 1.1530 + Swap(arr[from], arr[to]); 1.1531 + ++from; 1.1532 + --to; 1.1533 + } 1.1534 +} 1.1535 + 1.1536 + 1.1537 +// ***** AppendArray 1.1538 +// 1.1539 +template<class CDst, class CSrc> 1.1540 +void AppendArray(CDst& dst, const CSrc& src) 1.1541 +{ 1.1542 + UPInt i; 1.1543 + for(i = 0; i < src.GetSize(); i++) 1.1544 + dst.PushBack(src[i]); 1.1545 +} 1.1546 + 1.1547 +//----------------------------------------------------------------------------------- 1.1548 +// ***** ArrayAdaptor 1.1549 +// 1.1550 +// A simple adapter that provides the GetSize() method and overloads 1.1551 +// operator []. Used to wrap plain arrays in QuickSort and such. 1.1552 +template<class T> class ArrayAdaptor 1.1553 +{ 1.1554 +public: 1.1555 + typedef T ValueType; 1.1556 + ArrayAdaptor() : Data(0), Size(0) {} 1.1557 + ArrayAdaptor(T* ptr, UPInt size) : Data(ptr), Size(size) {} 1.1558 + UPInt GetSize() const { return Size; } 1.1559 + const T& operator [] (UPInt i) const { return Data[i]; } 1.1560 + T& operator [] (UPInt i) { return Data[i]; } 1.1561 +private: 1.1562 + T* Data; 1.1563 + UPInt Size; 1.1564 +}; 1.1565 + 1.1566 + 1.1567 +//----------------------------------------------------------------------------------- 1.1568 +// ***** GConstArrayAdaptor 1.1569 +// 1.1570 +// A simple const adapter that provides the GetSize() method and overloads 1.1571 +// operator []. Used to wrap plain arrays in LowerBound and such. 1.1572 +template<class T> class ConstArrayAdaptor 1.1573 +{ 1.1574 +public: 1.1575 + typedef T ValueType; 1.1576 + ConstArrayAdaptor() : Data(0), Size(0) {} 1.1577 + ConstArrayAdaptor(const T* ptr, UPInt size) : Data(ptr), Size(size) {} 1.1578 + UPInt GetSize() const { return Size; } 1.1579 + const T& operator [] (UPInt i) const { return Data[i]; } 1.1580 +private: 1.1581 + const T* Data; 1.1582 + UPInt Size; 1.1583 +}; 1.1584 + 1.1585 + 1.1586 + 1.1587 +//----------------------------------------------------------------------------------- 1.1588 +extern const UByte UpperBitTable[256]; 1.1589 +extern const UByte LowerBitTable[256]; 1.1590 + 1.1591 + 1.1592 + 1.1593 +//----------------------------------------------------------------------------------- 1.1594 +inline UByte UpperBit(UPInt val) 1.1595 +{ 1.1596 +#ifndef OVR_64BIT_POINTERS 1.1597 + 1.1598 + if (val & 0xFFFF0000) 1.1599 + { 1.1600 + return (val & 0xFF000000) ? 1.1601 + UpperBitTable[(val >> 24) ] + 24: 1.1602 + UpperBitTable[(val >> 16) & 0xFF] + 16; 1.1603 + } 1.1604 + return (val & 0xFF00) ? 1.1605 + UpperBitTable[(val >> 8) & 0xFF] + 8: 1.1606 + UpperBitTable[(val ) & 0xFF]; 1.1607 + 1.1608 +#else 1.1609 + 1.1610 + if (val & 0xFFFFFFFF00000000) 1.1611 + { 1.1612 + if (val & 0xFFFF000000000000) 1.1613 + { 1.1614 + return (val & 0xFF00000000000000) ? 1.1615 + UpperBitTable[(val >> 56) ] + 56: 1.1616 + UpperBitTable[(val >> 48) & 0xFF] + 48; 1.1617 + } 1.1618 + return (val & 0xFF0000000000) ? 1.1619 + UpperBitTable[(val >> 40) & 0xFF] + 40: 1.1620 + UpperBitTable[(val >> 32) & 0xFF] + 32; 1.1621 + } 1.1622 + else 1.1623 + { 1.1624 + if (val & 0xFFFF0000) 1.1625 + { 1.1626 + return (val & 0xFF000000) ? 1.1627 + UpperBitTable[(val >> 24) ] + 24: 1.1628 + UpperBitTable[(val >> 16) & 0xFF] + 16; 1.1629 + } 1.1630 + return (val & 0xFF00) ? 1.1631 + UpperBitTable[(val >> 8) & 0xFF] + 8: 1.1632 + UpperBitTable[(val ) & 0xFF]; 1.1633 + } 1.1634 + 1.1635 +#endif 1.1636 +} 1.1637 + 1.1638 +//----------------------------------------------------------------------------------- 1.1639 +inline UByte LowerBit(UPInt val) 1.1640 +{ 1.1641 +#ifndef OVR_64BIT_POINTERS 1.1642 + 1.1643 + if (val & 0xFFFF) 1.1644 + { 1.1645 + return (val & 0xFF) ? 1.1646 + LowerBitTable[ val & 0xFF]: 1.1647 + LowerBitTable[(val >> 8) & 0xFF] + 8; 1.1648 + } 1.1649 + return (val & 0xFF0000) ? 1.1650 + LowerBitTable[(val >> 16) & 0xFF] + 16: 1.1651 + LowerBitTable[(val >> 24) & 0xFF] + 24; 1.1652 + 1.1653 +#else 1.1654 + 1.1655 + if (val & 0xFFFFFFFF) 1.1656 + { 1.1657 + if (val & 0xFFFF) 1.1658 + { 1.1659 + return (val & 0xFF) ? 1.1660 + LowerBitTable[ val & 0xFF]: 1.1661 + LowerBitTable[(val >> 8) & 0xFF] + 8; 1.1662 + } 1.1663 + return (val & 0xFF0000) ? 1.1664 + LowerBitTable[(val >> 16) & 0xFF] + 16: 1.1665 + LowerBitTable[(val >> 24) & 0xFF] + 24; 1.1666 + } 1.1667 + else 1.1668 + { 1.1669 + if (val & 0xFFFF00000000) 1.1670 + { 1.1671 + return (val & 0xFF00000000) ? 1.1672 + LowerBitTable[(val >> 32) & 0xFF] + 32: 1.1673 + LowerBitTable[(val >> 40) & 0xFF] + 40; 1.1674 + } 1.1675 + return (val & 0xFF000000000000) ? 1.1676 + LowerBitTable[(val >> 48) & 0xFF] + 48: 1.1677 + LowerBitTable[(val >> 56) & 0xFF] + 56; 1.1678 + } 1.1679 + 1.1680 +#endif 1.1681 +} 1.1682 + 1.1683 + 1.1684 + 1.1685 +// ******* Special (optimized) memory routines 1.1686 +// Note: null (bad) pointer is not tested 1.1687 +class MemUtil 1.1688 +{ 1.1689 +public: 1.1690 + 1.1691 + // Memory compare 1.1692 + static int Cmp (const void* p1, const void* p2, UPInt byteCount) { return memcmp(p1, p2, byteCount); } 1.1693 + static int Cmp16(const void* p1, const void* p2, UPInt int16Count); 1.1694 + static int Cmp32(const void* p1, const void* p2, UPInt int32Count); 1.1695 + static int Cmp64(const void* p1, const void* p2, UPInt int64Count); 1.1696 +}; 1.1697 + 1.1698 +// ** Inline Implementation 1.1699 + 1.1700 +inline int MemUtil::Cmp16(const void* p1, const void* p2, UPInt int16Count) 1.1701 +{ 1.1702 + SInt16* pa = (SInt16*)p1; 1.1703 + SInt16* pb = (SInt16*)p2; 1.1704 + unsigned ic = 0; 1.1705 + if (int16Count == 0) 1.1706 + return 0; 1.1707 + while (pa[ic] == pb[ic]) 1.1708 + if (++ic==int16Count) 1.1709 + return 0; 1.1710 + return pa[ic] > pb[ic] ? 1 : -1; 1.1711 +} 1.1712 +inline int MemUtil::Cmp32(const void* p1, const void* p2, UPInt int32Count) 1.1713 +{ 1.1714 + SInt32* pa = (SInt32*)p1; 1.1715 + SInt32* pb = (SInt32*)p2; 1.1716 + unsigned ic = 0; 1.1717 + if (int32Count == 0) 1.1718 + return 0; 1.1719 + while (pa[ic] == pb[ic]) 1.1720 + if (++ic==int32Count) 1.1721 + return 0; 1.1722 + return pa[ic] > pb[ic] ? 1 : -1; 1.1723 +} 1.1724 +inline int MemUtil::Cmp64(const void* p1, const void* p2, UPInt int64Count) 1.1725 +{ 1.1726 + SInt64* pa = (SInt64*)p1; 1.1727 + SInt64* pb = (SInt64*)p2; 1.1728 + unsigned ic = 0; 1.1729 + if (int64Count == 0) 1.1730 + return 0; 1.1731 + while (pa[ic] == pb[ic]) 1.1732 + if (++ic==int64Count) 1.1733 + return 0; 1.1734 + return pa[ic] > pb[ic] ? 1 : -1; 1.1735 +} 1.1736 + 1.1737 +// ** End Inline Implementation 1.1738 + 1.1739 + 1.1740 +//----------------------------------------------------------------------------------- 1.1741 +// ******* Byte Order Conversions 1.1742 +namespace ByteUtil { 1.1743 + 1.1744 + // *** Swap Byte Order 1.1745 + 1.1746 + // Swap the byte order of a byte array 1.1747 + inline void SwapOrder(void* pv, int size) 1.1748 + { 1.1749 + UByte* pb = (UByte*)pv; 1.1750 + UByte temp; 1.1751 + for (int i = 0; i < size>>1; i++) 1.1752 + { 1.1753 + temp = pb[size-1-i]; 1.1754 + pb[size-1-i] = pb[i]; 1.1755 + pb[i] = temp; 1.1756 + } 1.1757 + } 1.1758 + 1.1759 + // Swap the byte order of primitive types 1.1760 + inline UByte SwapOrder(UByte v) { return v; } 1.1761 + inline SByte SwapOrder(SByte v) { return v; } 1.1762 + inline UInt16 SwapOrder(UInt16 v) { return UInt16(v>>8)|UInt16(v<<8); } 1.1763 + inline SInt16 SwapOrder(SInt16 v) { return SInt16((UInt16(v)>>8)|(v<<8)); } 1.1764 + inline UInt32 SwapOrder(UInt32 v) { return (v>>24)|((v&0x00FF0000)>>8)|((v&0x0000FF00)<<8)|(v<<24); } 1.1765 + inline SInt32 SwapOrder(SInt32 p) { return (SInt32)SwapOrder(UInt32(p)); } 1.1766 + inline UInt64 SwapOrder(UInt64 v) 1.1767 + { 1.1768 + return (v>>56) | 1.1769 + ((v&UInt64(0x00FF000000000000))>>40) | 1.1770 + ((v&UInt64(0x0000FF0000000000))>>24) | 1.1771 + ((v&UInt64(0x000000FF00000000))>>8) | 1.1772 + ((v&UInt64(0x00000000FF000000))<<8) | 1.1773 + ((v&UInt64(0x0000000000FF0000))<<24) | 1.1774 + ((v&UInt64(0x000000000000FF00))<<40) | 1.1775 + (v<<56); 1.1776 + } 1.1777 + inline SInt64 SwapOrder(SInt64 v) { return (SInt64)SwapOrder(UInt64(v)); } 1.1778 + inline float SwapOrder(float p) 1.1779 + { 1.1780 + union { 1.1781 + float p; 1.1782 + UInt32 v; 1.1783 + } u; 1.1784 + u.p = p; 1.1785 + u.v = SwapOrder(u.v); 1.1786 + return u.p; 1.1787 + } 1.1788 + 1.1789 + inline double SwapOrder(double p) 1.1790 + { 1.1791 + union { 1.1792 + double p; 1.1793 + UInt64 v; 1.1794 + } u; 1.1795 + u.p = p; 1.1796 + u.v = SwapOrder(u.v); 1.1797 + return u.p; 1.1798 + } 1.1799 + 1.1800 + // *** Byte-order conversion 1.1801 + 1.1802 +#if (OVR_BYTE_ORDER == OVR_LITTLE_ENDIAN) 1.1803 + // Little Endian to System (LE) 1.1804 + inline UByte LEToSystem(UByte v) { return v; } 1.1805 + inline SByte LEToSystem(SByte v) { return v; } 1.1806 + inline UInt16 LEToSystem(UInt16 v) { return v; } 1.1807 + inline SInt16 LEToSystem(SInt16 v) { return v; } 1.1808 + inline UInt32 LEToSystem(UInt32 v) { return v; } 1.1809 + inline SInt32 LEToSystem(SInt32 v) { return v; } 1.1810 + inline UInt64 LEToSystem(UInt64 v) { return v; } 1.1811 + inline SInt64 LEToSystem(SInt64 v) { return v; } 1.1812 + inline float LEToSystem(float v) { return v; } 1.1813 + inline double LEToSystem(double v) { return v; } 1.1814 + 1.1815 + // Big Endian to System (LE) 1.1816 + inline UByte BEToSystem(UByte v) { return SwapOrder(v); } 1.1817 + inline SByte BEToSystem(SByte v) { return SwapOrder(v); } 1.1818 + inline UInt16 BEToSystem(UInt16 v) { return SwapOrder(v); } 1.1819 + inline SInt16 BEToSystem(SInt16 v) { return SwapOrder(v); } 1.1820 + inline UInt32 BEToSystem(UInt32 v) { return SwapOrder(v); } 1.1821 + inline SInt32 BEToSystem(SInt32 v) { return SwapOrder(v); } 1.1822 + inline UInt64 BEToSystem(UInt64 v) { return SwapOrder(v); } 1.1823 + inline SInt64 BEToSystem(SInt64 v) { return SwapOrder(v); } 1.1824 + inline float BEToSystem(float v) { return SwapOrder(v); } 1.1825 + inline double BEToSystem(double v) { return SwapOrder(v); } 1.1826 + 1.1827 + // System (LE) to Little Endian 1.1828 + inline UByte SystemToLE(UByte v) { return v; } 1.1829 + inline SByte SystemToLE(SByte v) { return v; } 1.1830 + inline UInt16 SystemToLE(UInt16 v) { return v; } 1.1831 + inline SInt16 SystemToLE(SInt16 v) { return v; } 1.1832 + inline UInt32 SystemToLE(UInt32 v) { return v; } 1.1833 + inline SInt32 SystemToLE(SInt32 v) { return v; } 1.1834 + inline UInt64 SystemToLE(UInt64 v) { return v; } 1.1835 + inline SInt64 SystemToLE(SInt64 v) { return v; } 1.1836 + inline float SystemToLE(float v) { return v; } 1.1837 + inline double SystemToLE(double v) { return v; } 1.1838 + 1.1839 + // System (LE) to Big Endian 1.1840 + inline UByte SystemToBE(UByte v) { return SwapOrder(v); } 1.1841 + inline SByte SystemToBE(SByte v) { return SwapOrder(v); } 1.1842 + inline UInt16 SystemToBE(UInt16 v) { return SwapOrder(v); } 1.1843 + inline SInt16 SystemToBE(SInt16 v) { return SwapOrder(v); } 1.1844 + inline UInt32 SystemToBE(UInt32 v) { return SwapOrder(v); } 1.1845 + inline SInt32 SystemToBE(SInt32 v) { return SwapOrder(v); } 1.1846 + inline UInt64 SystemToBE(UInt64 v) { return SwapOrder(v); } 1.1847 + inline SInt64 SystemToBE(SInt64 v) { return SwapOrder(v); } 1.1848 + inline float SystemToBE(float v) { return SwapOrder(v); } 1.1849 + inline double SystemToBE(double v) { return SwapOrder(v); } 1.1850 + 1.1851 +#elif (OVR_BYTE_ORDER == OVR_BIG_ENDIAN) 1.1852 + // Little Endian to System (BE) 1.1853 + inline UByte LEToSystem(UByte v) { return SwapOrder(v); } 1.1854 + inline SByte LEToSystem(SByte v) { return SwapOrder(v); } 1.1855 + inline UInt16 LEToSystem(UInt16 v) { return SwapOrder(v); } 1.1856 + inline SInt16 LEToSystem(SInt16 v) { return SwapOrder(v); } 1.1857 + inline UInt32 LEToSystem(UInt32 v) { return SwapOrder(v); } 1.1858 + inline SInt32 LEToSystem(SInt32 v) { return SwapOrder(v); } 1.1859 + inline UInt64 LEToSystem(UInt64 v) { return SwapOrder(v); } 1.1860 + inline SInt64 LEToSystem(SInt64 v) { return SwapOrder(v); } 1.1861 + inline float LEToSystem(float v) { return SwapOrder(v); } 1.1862 + inline double LEToSystem(double v) { return SwapOrder(v); } 1.1863 + 1.1864 + // Big Endian to System (BE) 1.1865 + inline UByte BEToSystem(UByte v) { return v; } 1.1866 + inline SByte BEToSystem(SByte v) { return v; } 1.1867 + inline UInt16 BEToSystem(UInt16 v) { return v; } 1.1868 + inline SInt16 BEToSystem(SInt16 v) { return v; } 1.1869 + inline UInt32 BEToSystem(UInt32 v) { return v; } 1.1870 + inline SInt32 BEToSystem(SInt32 v) { return v; } 1.1871 + inline UInt64 BEToSystem(UInt64 v) { return v; } 1.1872 + inline SInt64 BEToSystem(SInt64 v) { return v; } 1.1873 + inline float BEToSystem(float v) { return v; } 1.1874 + inline double BEToSystem(double v) { return v; } 1.1875 + 1.1876 + // System (BE) to Little Endian 1.1877 + inline UByte SystemToLE(UByte v) { return SwapOrder(v); } 1.1878 + inline SByte SystemToLE(SByte v) { return SwapOrder(v); } 1.1879 + inline UInt16 SystemToLE(UInt16 v) { return SwapOrder(v); } 1.1880 + inline SInt16 SystemToLE(SInt16 v) { return SwapOrder(v); } 1.1881 + inline UInt32 SystemToLE(UInt32 v) { return SwapOrder(v); } 1.1882 + inline SInt32 SystemToLE(SInt32 v) { return SwapOrder(v); } 1.1883 + inline UInt64 SystemToLE(UInt64 v) { return SwapOrder(v); } 1.1884 + inline SInt64 SystemToLE(SInt64 v) { return SwapOrder(v); } 1.1885 + inline float SystemToLE(float v) { return SwapOrder(v); } 1.1886 + inline double SystemToLE(double v) { return SwapOrder(v); } 1.1887 + 1.1888 + // System (BE) to Big Endian 1.1889 + inline UByte SystemToBE(UByte v) { return v; } 1.1890 + inline SByte SystemToBE(SByte v) { return v; } 1.1891 + inline UInt16 SystemToBE(UInt16 v) { return v; } 1.1892 + inline SInt16 SystemToBE(SInt16 v) { return v; } 1.1893 + inline UInt32 SystemToBE(UInt32 v) { return v; } 1.1894 + inline SInt32 SystemToBE(SInt32 v) { return v; } 1.1895 + inline UInt64 SystemToBE(UInt64 v) { return v; } 1.1896 + inline SInt64 SystemToBE(SInt64 v) { return v; } 1.1897 + inline float SystemToBE(float v) { return v; } 1.1898 + inline double SystemToBE(double v) { return v; } 1.1899 + 1.1900 +#else 1.1901 + #error "OVR_BYTE_ORDER must be defined to OVR_LITTLE_ENDIAN or OVR_BIG_ENDIAN" 1.1902 +#endif 1.1903 + 1.1904 +} // namespace ByteUtil 1.1905 + 1.1906 + 1.1907 + 1.1908 +}} // OVR::Alg 1.1909 + 1.1910 +#endif