OVR_Alg.h
Go to the documentation of this file.
00001 /************************************************************************************
00002 
00003 PublicHeader:   OVR.h
00004 Filename    :   OVR_Alg.h
00005 Content     :   Simple general purpose algorithms: Sort, Binary Search, etc.
00006 Created     :   September 19, 2012
00007 Notes       : 
00008 
00009 Copyright   :   Copyright 2012 Oculus VR, Inc. All Rights reserved.
00010 
00011 Use of this software is subject to the terms of the Oculus license
00012 agreement provided at the time of installation or download, or which
00013 otherwise accompanies this software in either electronic or hard copy form.
00014 
00015 ************************************************************************************/
00016 
00017 #ifndef OVR_Alg_h
00018 #define OVR_Alg_h
00019 
00020 #include "OVR_Types.h"
00021 #include <string.h>
00022 
00023 namespace OVR { namespace Alg {
00024 
00025 
00026 //-----------------------------------------------------------------------------------
00027 // ***** Operator extensions
00028 
00029 template <typename T> OVR_FORCE_INLINE void Swap(T &a, T &b) 
00030 {  T temp(a); a = b; b = temp; }
00031 
00032 
00033 // ***** min/max are not implemented in Visual Studio 6 standard STL
00034 
00035 template <typename T> OVR_FORCE_INLINE const T Min(const T a, const T b)
00036 { return (a < b) ? a : b; }
00037 
00038 template <typename T> OVR_FORCE_INLINE const T Max(const T a, const T b)
00039 { return (b < a) ? a : b; }
00040 
00041 template <typename T> OVR_FORCE_INLINE const T Clamp(const T v, const T minVal, const T maxVal)
00042 { return Max<T>(minVal, Min<T>(v, maxVal)); }
00043 
00044 template <typename T> OVR_FORCE_INLINE int     Chop(T f)
00045 { return (int)f; }
00046 
00047 template <typename T> OVR_FORCE_INLINE T       Lerp(T a, T b, T f) 
00048 { return (b - a) * f + a; }
00049 
00050 
00051 // These functions stand to fix a stupid VC++ warning (with /Wp64 on):
00052 // "warning C4267: 'argument' : conversion from 'size_t' to 'const unsigned', possible loss of data"
00053 // Use these functions instead of gmin/gmax if the argument has size
00054 // of the pointer to avoid the warning. Though, functionally they are
00055 // absolutelly the same as regular gmin/gmax.
00056 template <typename T>   OVR_FORCE_INLINE const T PMin(const T a, const T b)
00057 {
00058     OVR_COMPILER_ASSERT(sizeof(T) == sizeof(UPInt));
00059     return (a < b) ? a : b;
00060 }
00061 template <typename T>   OVR_FORCE_INLINE const T PMax(const T a, const T b)
00062 {
00063     OVR_COMPILER_ASSERT(sizeof(T) == sizeof(UPInt));
00064     return (b < a) ? a : b;
00065 }
00066 
00067 
00068 template <typename T>   OVR_FORCE_INLINE const T Abs(const T v)
00069 { return (v>=0) ? v : -v; }
00070 
00071 
00072 //-----------------------------------------------------------------------------------
00073 // ***** OperatorLess
00074 //
00075 template<class T> struct OperatorLess
00076 {
00077     static bool Compare(const T& a, const T& b)
00078     {
00079         return a < b;
00080     }
00081 };
00082 
00083 
00084 //-----------------------------------------------------------------------------------
00085 // ***** QuickSortSliced
00086 //
00087 // Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe.
00088 // The range is specified with start, end, where "end" is exclusive!
00089 // The comparison predicate must be specified.
00090 template<class Array, class Less> 
00091 void QuickSortSliced(Array& arr, UPInt start, UPInt end, Less less)
00092 {
00093     enum 
00094     {
00095         Threshold = 9
00096     };
00097 
00098     if(end - start <  2) return;
00099 
00100     SPInt  stack[80];
00101     SPInt* top   = stack; 
00102     SPInt  base  = (SPInt)start;
00103     SPInt  limit = (SPInt)end;
00104 
00105     for(;;)
00106     {
00107         SPInt len = limit - base;
00108         SPInt i, j, pivot;
00109 
00110         if(len > Threshold)
00111         {
00112             // we use base + len/2 as the pivot
00113             pivot = base + len / 2;
00114             Swap(arr[base], arr[pivot]);
00115 
00116             i = base + 1;
00117             j = limit - 1;
00118 
00119             // now ensure that *i <= *base <= *j 
00120             if(less(arr[j],    arr[i])) Swap(arr[j],    arr[i]);
00121             if(less(arr[base], arr[i])) Swap(arr[base], arr[i]);
00122             if(less(arr[j], arr[base])) Swap(arr[j], arr[base]);
00123 
00124             for(;;)
00125             {
00126                 do i++; while( less(arr[i], arr[base]) );
00127                 do j--; while( less(arr[base], arr[j]) );
00128 
00129                 if( i > j )
00130                 {
00131                     break;
00132                 }
00133 
00134                 Swap(arr[i], arr[j]);
00135             }
00136 
00137             Swap(arr[base], arr[j]);
00138 
00139             // now, push the largest sub-array
00140             if(j - base > limit - i)
00141             {
00142                 top[0] = base;
00143                 top[1] = j;
00144                 base   = i;
00145             }
00146             else
00147             {
00148                 top[0] = i;
00149                 top[1] = limit;
00150                 limit  = j;
00151             }
00152             top += 2;
00153         }
00154         else
00155         {
00156             // the sub-array is small, perform insertion sort
00157             j = base;
00158             i = j + 1;
00159 
00160             for(; i < limit; j = i, i++)
00161             {
00162                 for(; less(arr[j + 1], arr[j]); j--)
00163                 {
00164                     Swap(arr[j + 1], arr[j]);
00165                     if(j == base)
00166                     {
00167                         break;
00168                     }
00169                 }
00170             }
00171             if(top > stack)
00172             {
00173                 top  -= 2;
00174                 base  = top[0];
00175                 limit = top[1];
00176             }
00177             else
00178             {
00179                 break;
00180             }
00181         }
00182     }
00183 }
00184 
00185 
00186 //-----------------------------------------------------------------------------------
00187 // ***** QuickSortSliced
00188 //
00189 // Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe.
00190 // The range is specified with start, end, where "end" is exclusive!
00191 // The data type must have a defined "<" operator.
00192 template<class Array> 
00193 void QuickSortSliced(Array& arr, UPInt start, UPInt end)
00194 {
00195     typedef typename Array::ValueType ValueType;
00196     QuickSortSliced(arr, start, end, OperatorLess<ValueType>::Compare);
00197 }
00198 
00199 // Same as corresponding G_QuickSortSliced but with checking array limits to avoid
00200 // crash in the case of wrong comparator functor.
00201 template<class Array, class Less> 
00202 bool QuickSortSlicedSafe(Array& arr, UPInt start, UPInt end, Less less)
00203 {
00204     enum 
00205     {
00206         Threshold = 9
00207     };
00208 
00209     if(end - start <  2) return true;
00210 
00211     SPInt  stack[80];
00212     SPInt* top   = stack; 
00213     SPInt  base  = (SPInt)start;
00214     SPInt  limit = (SPInt)end;
00215 
00216     for(;;)
00217     {
00218         SPInt len = limit - base;
00219         SPInt i, j, pivot;
00220 
00221         if(len > Threshold)
00222         {
00223             // we use base + len/2 as the pivot
00224             pivot = base + len / 2;
00225             Swap(arr[base], arr[pivot]);
00226 
00227             i = base + 1;
00228             j = limit - 1;
00229 
00230             // now ensure that *i <= *base <= *j 
00231             if(less(arr[j],    arr[i])) Swap(arr[j],    arr[i]);
00232             if(less(arr[base], arr[i])) Swap(arr[base], arr[i]);
00233             if(less(arr[j], arr[base])) Swap(arr[j], arr[base]);
00234 
00235             for(;;)
00236             {
00237                 do 
00238                 {   
00239                     i++; 
00240                     if (i >= limit)
00241                         return false;
00242                 } while( less(arr[i], arr[base]) );
00243                 do 
00244                 {
00245                     j--; 
00246                     if (j < 0)
00247                         return false;
00248                 } while( less(arr[base], arr[j]) );
00249 
00250                 if( i > j )
00251                 {
00252                     break;
00253                 }
00254 
00255                 Swap(arr[i], arr[j]);
00256             }
00257 
00258             Swap(arr[base], arr[j]);
00259 
00260             // now, push the largest sub-array
00261             if(j - base > limit - i)
00262             {
00263                 top[0] = base;
00264                 top[1] = j;
00265                 base   = i;
00266             }
00267             else
00268             {
00269                 top[0] = i;
00270                 top[1] = limit;
00271                 limit  = j;
00272             }
00273             top += 2;
00274         }
00275         else
00276         {
00277             // the sub-array is small, perform insertion sort
00278             j = base;
00279             i = j + 1;
00280 
00281             for(; i < limit; j = i, i++)
00282             {
00283                 for(; less(arr[j + 1], arr[j]); j--)
00284                 {
00285                     Swap(arr[j + 1], arr[j]);
00286                     if(j == base)
00287                     {
00288                         break;
00289                     }
00290                 }
00291             }
00292             if(top > stack)
00293             {
00294                 top  -= 2;
00295                 base  = top[0];
00296                 limit = top[1];
00297             }
00298             else
00299             {
00300                 break;
00301             }
00302         }
00303     }
00304     return true;
00305 }
00306 
00307 template<class Array> 
00308 bool QuickSortSlicedSafe(Array& arr, UPInt start, UPInt end)
00309 {
00310     typedef typename Array::ValueType ValueType;
00311     return QuickSortSlicedSafe(arr, start, end, OperatorLess<ValueType>::Compare);
00312 }
00313 
00314 //-----------------------------------------------------------------------------------
00315 // ***** QuickSort
00316 //
00317 // Sort an array Array, ArrayPaged, ArrayUnsafe.
00318 // The array must have GetSize() function.
00319 // The comparison predicate must be specified.
00320 template<class Array, class Less> 
00321 void QuickSort(Array& arr, Less less)
00322 {
00323     QuickSortSliced(arr, 0, arr.GetSize(), less);
00324 }
00325 
00326 // checks for boundaries
00327 template<class Array, class Less> 
00328 bool QuickSortSafe(Array& arr, Less less)
00329 {
00330     return QuickSortSlicedSafe(arr, 0, arr.GetSize(), less);
00331 }
00332 
00333 
00334 //-----------------------------------------------------------------------------------
00335 // ***** QuickSort
00336 //
00337 // Sort an array Array, ArrayPaged, ArrayUnsafe.
00338 // The array must have GetSize() function.
00339 // The data type must have a defined "<" operator.
00340 template<class Array> 
00341 void QuickSort(Array& arr)
00342 {
00343     typedef typename Array::ValueType ValueType;
00344     QuickSortSliced(arr, 0, arr.GetSize(), OperatorLess<ValueType>::Compare);
00345 }
00346 
00347 template<class Array> 
00348 bool QuickSortSafe(Array& arr)
00349 {
00350     typedef typename Array::ValueType ValueType;
00351     return QuickSortSlicedSafe(arr, 0, arr.GetSize(), OperatorLess<ValueType>::Compare);
00352 }
00353 
00354 //-----------------------------------------------------------------------------------
00355 // ***** InsertionSortSliced
00356 //
00357 // Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe.
00358 // The range is specified with start, end, where "end" is exclusive!
00359 // The comparison predicate must be specified.
00360 // Unlike Quick Sort, the Insertion Sort works much slower in average, 
00361 // but may be much faster on almost sorted arrays. Besides, it guarantees
00362 // that the elements will not be swapped if not necessary. For example, 
00363 // an array with all equal elements will remain "untouched", while 
00364 // Quick Sort will considerably shuffle the elements in this case.
00365 template<class Array, class Less> 
00366 void InsertionSortSliced(Array& arr, UPInt start, UPInt end, Less less)
00367 {
00368     UPInt j = start;
00369     UPInt i = j + 1;
00370     UPInt limit = end;
00371 
00372     for(; i < limit; j = i, i++)
00373     {
00374         for(; less(arr[j + 1], arr[j]); j--)
00375         {
00376             Swap(arr[j + 1], arr[j]);
00377             if(j <= start)
00378             {
00379                 break;
00380             }
00381         }
00382     }
00383 }
00384 
00385 
00386 //-----------------------------------------------------------------------------------
00387 // ***** InsertionSortSliced
00388 //
00389 // Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe.
00390 // The range is specified with start, end, where "end" is exclusive!
00391 // The data type must have a defined "<" operator.
00392 template<class Array> 
00393 void InsertionSortSliced(Array& arr, UPInt start, UPInt end)
00394 {
00395     typedef typename Array::ValueType ValueType;
00396     InsertionSortSliced(arr, start, end, OperatorLess<ValueType>::Compare);
00397 }
00398 
00399 //-----------------------------------------------------------------------------------
00400 // ***** InsertionSort
00401 //
00402 // Sort an array Array, ArrayPaged, ArrayUnsafe.
00403 // The array must have GetSize() function.
00404 // The comparison predicate must be specified.
00405 
00406 template<class Array, class Less> 
00407 void InsertionSort(Array& arr, Less less)
00408 {
00409     InsertionSortSliced(arr, 0, arr.GetSize(), less);
00410 }
00411 
00412 //-----------------------------------------------------------------------------------
00413 // ***** InsertionSort
00414 //
00415 // Sort an array Array, ArrayPaged, ArrayUnsafe.
00416 // The array must have GetSize() function.
00417 // The data type must have a defined "<" operator.
00418 template<class Array> 
00419 void InsertionSort(Array& arr)
00420 {
00421     typedef typename Array::ValueType ValueType;
00422     InsertionSortSliced(arr, 0, arr.GetSize(), OperatorLess<ValueType>::Compare);
00423 }
00424 
00425 
00426 
00427 //-----------------------------------------------------------------------------------
00428 // ***** LowerBoundSliced
00429 //
00430 template<class Array, class Value, class Less>
00431 UPInt LowerBoundSliced(const Array& arr, UPInt start, UPInt end, const Value& val, Less less)
00432 {
00433     SPInt first = (SPInt)start;
00434     SPInt len   = (SPInt)(end - start);
00435     SPInt half;
00436     SPInt middle;
00437     
00438     while(len > 0) 
00439     {
00440         half = len >> 1;
00441         middle = first + half;
00442         if(less(arr[middle], val)) 
00443         {
00444             first = middle + 1;
00445             len   = len - half - 1;
00446         }
00447         else
00448         {
00449             len = half;
00450         }
00451     }
00452     return (UPInt)first;
00453 }
00454 
00455 
00456 //-----------------------------------------------------------------------------------
00457 // ***** LowerBoundSliced
00458 //
00459 template<class Array, class Value>
00460 UPInt LowerBoundSliced(const Array& arr, UPInt start, UPInt end, const Value& val)
00461 {
00462     return LowerBoundSliced(arr, start, end, val, OperatorLess<Value>::Compare);
00463 }
00464 
00465 //-----------------------------------------------------------------------------------
00466 // ***** LowerBoundSized
00467 //
00468 template<class Array, class Value>
00469 UPInt LowerBoundSized(const Array& arr, UPInt size, const Value& val)
00470 {
00471     return LowerBoundSliced(arr, 0, size, val, OperatorLess<Value>::Compare);
00472 }
00473 
00474 //-----------------------------------------------------------------------------------
00475 // ***** LowerBound
00476 //
00477 template<class Array, class Value, class Less>
00478 UPInt LowerBound(const Array& arr, const Value& val, Less less)
00479 {
00480     return LowerBoundSliced(arr, 0, arr.GetSize(), val, less);
00481 }
00482 
00483 
00484 //-----------------------------------------------------------------------------------
00485 // ***** LowerBound
00486 //
00487 template<class Array, class Value>
00488 UPInt LowerBound(const Array& arr, const Value& val)
00489 {
00490     return LowerBoundSliced(arr, 0, arr.GetSize(), val, OperatorLess<Value>::Compare);
00491 }
00492 
00493 
00494 
00495 //-----------------------------------------------------------------------------------
00496 // ***** UpperBoundSliced
00497 //
00498 template<class Array, class Value, class Less>
00499 UPInt UpperBoundSliced(const Array& arr, UPInt start, UPInt end, const Value& val, Less less)
00500 {
00501     SPInt first = (SPInt)start;
00502     SPInt len   = (SPInt)(end - start);
00503     SPInt half;
00504     SPInt middle;
00505     
00506     while(len > 0) 
00507     {
00508         half = len >> 1;
00509         middle = first + half;
00510         if(less(val, arr[middle]))
00511         {
00512             len = half;
00513         }
00514         else 
00515         {
00516             first = middle + 1;
00517             len   = len - half - 1;
00518         }
00519     }
00520     return (UPInt)first;
00521 }
00522 
00523 
00524 //-----------------------------------------------------------------------------------
00525 // ***** UpperBoundSliced
00526 //
00527 template<class Array, class Value>
00528 UPInt UpperBoundSliced(const Array& arr, UPInt start, UPInt end, const Value& val)
00529 {
00530     return UpperBoundSliced(arr, start, end, val, OperatorLess<Value>::Compare);
00531 }
00532 
00533 
00534 //-----------------------------------------------------------------------------------
00535 // ***** UpperBoundSized
00536 //
00537 template<class Array, class Value>
00538 UPInt UpperBoundSized(const Array& arr, UPInt size, const Value& val)
00539 {
00540     return UpperBoundSliced(arr, 0, size, val, OperatorLess<Value>::Compare);
00541 }
00542 
00543 
00544 //-----------------------------------------------------------------------------------
00545 // ***** UpperBound
00546 //
00547 template<class Array, class Value, class Less>
00548 UPInt UpperBound(const Array& arr, const Value& val, Less less)
00549 {
00550     return UpperBoundSliced(arr, 0, arr.GetSize(), val, less);
00551 }
00552 
00553 
00554 //-----------------------------------------------------------------------------------
00555 // ***** UpperBound
00556 //
00557 template<class Array, class Value>
00558 UPInt UpperBound(const Array& arr, const Value& val)
00559 {
00560     return UpperBoundSliced(arr, 0, arr.GetSize(), val, OperatorLess<Value>::Compare);
00561 }
00562 
00563 
00564 //-----------------------------------------------------------------------------------
00565 // ***** ReverseArray
00566 //
00567 template<class Array> void ReverseArray(Array& arr)
00568 {
00569     SPInt from = 0;
00570     SPInt to   = arr.GetSize() - 1;
00571     while(from < to)
00572     {
00573         Swap(arr[from], arr[to]);
00574         ++from;
00575         --to;
00576     }
00577 }
00578 
00579 
00580 // ***** AppendArray
00581 //
00582 template<class CDst, class CSrc> 
00583 void AppendArray(CDst& dst, const CSrc& src)
00584 {
00585     UPInt i;
00586     for(i = 0; i < src.GetSize(); i++) 
00587         dst.PushBack(src[i]);
00588 }
00589 
00590 //-----------------------------------------------------------------------------------
00591 // ***** ArrayAdaptor
00592 //
00593 // A simple adapter that provides the GetSize() method and overloads 
00594 // operator []. Used to wrap plain arrays in QuickSort and such.
00595 template<class T> class ArrayAdaptor
00596 {
00597 public:
00598     typedef T ValueType;
00599     ArrayAdaptor() : Data(0), Size(0) {}
00600     ArrayAdaptor(T* ptr, UPInt size) : Data(ptr), Size(size) {}
00601     UPInt GetSize() const { return Size; }
00602     const T& operator [] (UPInt i) const { return Data[i]; }
00603           T& operator [] (UPInt i)       { return Data[i]; }
00604 private:
00605     T*      Data;
00606     UPInt   Size;
00607 };
00608 
00609 
00610 //-----------------------------------------------------------------------------------
00611 // ***** GConstArrayAdaptor
00612 //
00613 // A simple const adapter that provides the GetSize() method and overloads 
00614 // operator []. Used to wrap plain arrays in LowerBound and such.
00615 template<class T> class ConstArrayAdaptor
00616 {
00617 public:
00618     typedef T ValueType;
00619     ConstArrayAdaptor() : Data(0), Size(0) {}
00620     ConstArrayAdaptor(const T* ptr, UPInt size) : Data(ptr), Size(size) {}
00621     UPInt GetSize() const { return Size; }
00622     const T& operator [] (UPInt i) const { return Data[i]; }
00623 private:
00624     const T* Data;
00625     UPInt    Size;
00626 };
00627 
00628 
00629 
00630 //-----------------------------------------------------------------------------------
00631 extern const UByte UpperBitTable[256];
00632 extern const UByte LowerBitTable[256];
00633 
00634 
00635 
00636 //-----------------------------------------------------------------------------------
00637 inline UByte UpperBit(UPInt val)
00638 {
00639 #ifndef OVR_64BIT_POINTERS
00640 
00641     if (val & 0xFFFF0000)
00642     {
00643         return (val & 0xFF000000) ? 
00644             UpperBitTable[(val >> 24)       ] + 24: 
00645             UpperBitTable[(val >> 16) & 0xFF] + 16;
00646     }
00647     return (val & 0xFF00) ?
00648         UpperBitTable[(val >> 8) & 0xFF] + 8:
00649         UpperBitTable[(val     ) & 0xFF];
00650 
00651 #else
00652 
00653     if (val & 0xFFFFFFFF00000000)
00654     {
00655         if (val & 0xFFFF000000000000)
00656         {
00657             return (val & 0xFF00000000000000) ?
00658                 UpperBitTable[(val >> 56)       ] + 56: 
00659                 UpperBitTable[(val >> 48) & 0xFF] + 48;
00660         }
00661         return (val & 0xFF0000000000) ?
00662             UpperBitTable[(val >> 40) & 0xFF] + 40:
00663             UpperBitTable[(val >> 32) & 0xFF] + 32;
00664     }
00665     else
00666     {
00667         if (val & 0xFFFF0000)
00668         {
00669             return (val & 0xFF000000) ? 
00670                 UpperBitTable[(val >> 24)       ] + 24: 
00671                 UpperBitTable[(val >> 16) & 0xFF] + 16;
00672         }
00673         return (val & 0xFF00) ?
00674             UpperBitTable[(val >> 8) & 0xFF] + 8:
00675             UpperBitTable[(val     ) & 0xFF];
00676     }
00677 
00678 #endif
00679 }
00680 
00681 //-----------------------------------------------------------------------------------
00682 inline UByte LowerBit(UPInt val)
00683 {
00684 #ifndef OVR_64BIT_POINTERS
00685 
00686     if (val & 0xFFFF)
00687     {
00688         return (val & 0xFF) ?
00689             LowerBitTable[ val & 0xFF]:
00690             LowerBitTable[(val >> 8) & 0xFF] + 8;
00691     }
00692     return (val & 0xFF0000) ?
00693             LowerBitTable[(val >> 16) & 0xFF] + 16:
00694             LowerBitTable[(val >> 24) & 0xFF] + 24;
00695 
00696 #else
00697 
00698     if (val & 0xFFFFFFFF)
00699     {
00700         if (val & 0xFFFF)
00701         {
00702             return (val & 0xFF) ?
00703                 LowerBitTable[ val & 0xFF]:
00704                 LowerBitTable[(val >> 8) & 0xFF] + 8;
00705         }
00706         return (val & 0xFF0000) ?
00707                 LowerBitTable[(val >> 16) & 0xFF] + 16:
00708                 LowerBitTable[(val >> 24) & 0xFF] + 24;
00709     }
00710     else
00711     {
00712         if (val & 0xFFFF00000000)
00713         {
00714              return (val & 0xFF00000000) ?
00715                 LowerBitTable[(val >> 32) & 0xFF] + 32:
00716                 LowerBitTable[(val >> 40) & 0xFF] + 40;
00717         }
00718         return (val & 0xFF000000000000) ?
00719             LowerBitTable[(val >> 48) & 0xFF] + 48:
00720             LowerBitTable[(val >> 56) & 0xFF] + 56;
00721     }
00722 
00723 #endif
00724 }
00725 
00726 
00727 
00728 // ******* Special (optimized) memory routines
00729 // Note: null (bad) pointer is not tested
00730 class MemUtil
00731 {
00732 public:
00733                                     
00734     // Memory compare
00735     static int      Cmp  (const void* p1, const void* p2, UPInt byteCount)      { return memcmp(p1, p2, byteCount); }
00736     static int      Cmp16(const void* p1, const void* p2, UPInt int16Count);
00737     static int      Cmp32(const void* p1, const void* p2, UPInt int32Count);
00738     static int      Cmp64(const void* p1, const void* p2, UPInt int64Count); 
00739 };
00740 
00741 // ** Inline Implementation
00742 
00743 inline int MemUtil::Cmp16(const void* p1, const void* p2, UPInt int16Count)
00744 {
00745     SInt16*  pa  = (SInt16*)p1; 
00746     SInt16*  pb  = (SInt16*)p2;
00747     unsigned ic  = 0;
00748     if (int16Count == 0)
00749         return 0;
00750     while (pa[ic] == pb[ic])
00751         if (++ic==int16Count)
00752             return 0;
00753     return pa[ic] > pb[ic] ? 1 : -1;
00754 }
00755 inline int MemUtil::Cmp32(const void* p1, const void* p2, UPInt int32Count)
00756 {
00757     SInt32*  pa  = (SInt32*)p1;
00758     SInt32*  pb  = (SInt32*)p2;
00759     unsigned ic  = 0;
00760     if (int32Count == 0)
00761         return 0;
00762     while (pa[ic] == pb[ic])
00763         if (++ic==int32Count)
00764             return 0;
00765     return pa[ic] > pb[ic] ? 1 : -1;
00766 }
00767 inline int MemUtil::Cmp64(const void* p1, const void* p2, UPInt int64Count)
00768 {
00769     SInt64*  pa  = (SInt64*)p1;
00770     SInt64*  pb  = (SInt64*)p2;
00771     unsigned ic  = 0;
00772     if (int64Count == 0)
00773         return 0;
00774     while (pa[ic] == pb[ic])
00775         if (++ic==int64Count)
00776             return 0;
00777     return pa[ic] > pb[ic] ? 1 : -1;
00778 }
00779 
00780 // ** End Inline Implementation
00781 
00782 
00783 //-----------------------------------------------------------------------------------
00784 // ******* Byte Order Conversions
00785 namespace ByteUtil {
00786 
00787     // *** Swap Byte Order
00788 
00789     // Swap the byte order of a byte array
00790     inline void     SwapOrder(void* pv, int size)
00791     {
00792         UByte*  pb = (UByte*)pv;
00793         UByte   temp;
00794         for (int i = 0; i < size>>1; i++)
00795         { 
00796             temp            = pb[size-1-i];
00797             pb[size-1-i]    = pb[i];
00798             pb[i]           = temp; 
00799         }
00800     }
00801 
00802     // Swap the byte order of primitive types
00803     inline UByte    SwapOrder(UByte v)      { return v; }
00804     inline SByte    SwapOrder(SByte v)      { return v; }
00805     inline UInt16   SwapOrder(UInt16 v)     { return UInt16(v>>8)|UInt16(v<<8); }
00806     inline SInt16   SwapOrder(SInt16 v)     { return SInt16((UInt16(v)>>8)|(v<<8)); }
00807     inline UInt32   SwapOrder(UInt32 v)     { return (v>>24)|((v&0x00FF0000)>>8)|((v&0x0000FF00)<<8)|(v<<24); }
00808     inline SInt32   SwapOrder(SInt32 p)     { return (SInt32)SwapOrder(UInt32(p)); }
00809     inline UInt64   SwapOrder(UInt64 v)
00810     { 
00811         return   (v>>56) |
00812                  ((v&UInt64(0x00FF000000000000))>>40) |
00813                  ((v&UInt64(0x0000FF0000000000))>>24) |
00814                  ((v&UInt64(0x000000FF00000000))>>8)  |
00815                  ((v&UInt64(0x00000000FF000000))<<8)  |
00816                  ((v&UInt64(0x0000000000FF0000))<<24) |
00817                  ((v&UInt64(0x000000000000FF00))<<40) |
00818                  (v<<56); 
00819     }
00820     inline SInt64   SwapOrder(SInt64 v)     { return (SInt64)SwapOrder(UInt64(v)); }
00821     inline float    SwapOrder(float p)      
00822     { 
00823         union {
00824             float p;
00825             UInt32 v;
00826         } u;
00827         u.p = p;
00828         u.v = SwapOrder(u.v);
00829         return u.p;
00830     }
00831 
00832     inline double   SwapOrder(double p)
00833     { 
00834         union {
00835             double p;
00836             UInt64 v;
00837         } u;
00838         u.p = p;
00839         u.v = SwapOrder(u.v);
00840         return u.p;
00841     }
00842     
00843     // *** Byte-order conversion
00844 
00845 #if (OVR_BYTE_ORDER == OVR_LITTLE_ENDIAN)
00846     // Little Endian to System (LE)
00847     inline UByte    LEToSystem(UByte  v)    { return v; }
00848     inline SByte    LEToSystem(SByte  v)    { return v; }
00849     inline UInt16   LEToSystem(UInt16 v)    { return v; }
00850     inline SInt16   LEToSystem(SInt16 v)    { return v; }
00851     inline UInt32   LEToSystem(UInt32 v)    { return v; }
00852     inline SInt32   LEToSystem(SInt32 v)    { return v; }
00853     inline UInt64   LEToSystem(UInt64 v)    { return v; }
00854     inline SInt64   LEToSystem(SInt64 v)    { return v; }
00855     inline float    LEToSystem(float  v)    { return v; }
00856     inline double   LEToSystem(double v)    { return v; }
00857 
00858     // Big Endian to System (LE)
00859     inline UByte    BEToSystem(UByte  v)    { return SwapOrder(v); }
00860     inline SByte    BEToSystem(SByte  v)    { return SwapOrder(v); }
00861     inline UInt16   BEToSystem(UInt16 v)    { return SwapOrder(v); }
00862     inline SInt16   BEToSystem(SInt16 v)    { return SwapOrder(v); }
00863     inline UInt32   BEToSystem(UInt32 v)    { return SwapOrder(v); }
00864     inline SInt32   BEToSystem(SInt32 v)    { return SwapOrder(v); }
00865     inline UInt64   BEToSystem(UInt64 v)    { return SwapOrder(v); }
00866     inline SInt64   BEToSystem(SInt64 v)    { return SwapOrder(v); }
00867     inline float    BEToSystem(float  v)    { return SwapOrder(v); }
00868     inline double   BEToSystem(double v)    { return SwapOrder(v); }
00869 
00870     // System (LE) to Little Endian
00871     inline UByte    SystemToLE(UByte  v)    { return v; }
00872     inline SByte    SystemToLE(SByte  v)    { return v; }
00873     inline UInt16   SystemToLE(UInt16 v)    { return v; }
00874     inline SInt16   SystemToLE(SInt16 v)    { return v; }
00875     inline UInt32   SystemToLE(UInt32 v)    { return v; }
00876     inline SInt32   SystemToLE(SInt32 v)    { return v; }
00877     inline UInt64   SystemToLE(UInt64 v)    { return v; }
00878     inline SInt64   SystemToLE(SInt64 v)    { return v; }
00879     inline float    SystemToLE(float  v)    { return v; }
00880     inline double   SystemToLE(double v)    { return v; }   
00881 
00882     // System (LE) to Big Endian
00883     inline UByte    SystemToBE(UByte  v)    { return SwapOrder(v); }
00884     inline SByte    SystemToBE(SByte  v)    { return SwapOrder(v); }
00885     inline UInt16   SystemToBE(UInt16 v)    { return SwapOrder(v); }
00886     inline SInt16   SystemToBE(SInt16 v)    { return SwapOrder(v); }
00887     inline UInt32   SystemToBE(UInt32 v)    { return SwapOrder(v); }
00888     inline SInt32   SystemToBE(SInt32 v)    { return SwapOrder(v); }
00889     inline UInt64   SystemToBE(UInt64 v)    { return SwapOrder(v); }
00890     inline SInt64   SystemToBE(SInt64 v)    { return SwapOrder(v); }
00891     inline float    SystemToBE(float  v)    { return SwapOrder(v); }
00892     inline double   SystemToBE(double v)    { return SwapOrder(v); }
00893 
00894 #elif (OVR_BYTE_ORDER == OVR_BIG_ENDIAN)
00895     // Little Endian to System (BE)
00896     inline UByte    LEToSystem(UByte  v)    { return SwapOrder(v); }
00897     inline SByte    LEToSystem(SByte  v)    { return SwapOrder(v); }
00898     inline UInt16   LEToSystem(UInt16 v)    { return SwapOrder(v); }
00899     inline SInt16   LEToSystem(SInt16 v)    { return SwapOrder(v); }
00900     inline UInt32   LEToSystem(UInt32 v)    { return SwapOrder(v); }
00901     inline SInt32   LEToSystem(SInt32 v)    { return SwapOrder(v); }
00902     inline UInt64   LEToSystem(UInt64 v)    { return SwapOrder(v); }
00903     inline SInt64   LEToSystem(SInt64 v)    { return SwapOrder(v); }
00904     inline float    LEToSystem(float  v)    { return SwapOrder(v); }
00905     inline double   LEToSystem(double v)    { return SwapOrder(v); }
00906 
00907     // Big Endian to System (BE)
00908     inline UByte    BEToSystem(UByte  v)    { return v; }
00909     inline SByte    BEToSystem(SByte  v)    { return v; }
00910     inline UInt16   BEToSystem(UInt16 v)    { return v; }
00911     inline SInt16   BEToSystem(SInt16 v)    { return v; }
00912     inline UInt32   BEToSystem(UInt32 v)    { return v; }
00913     inline SInt32   BEToSystem(SInt32 v)    { return v; }
00914     inline UInt64   BEToSystem(UInt64 v)    { return v; }
00915     inline SInt64   BEToSystem(SInt64 v)    { return v; }
00916     inline float    BEToSystem(float  v)    { return v; }
00917     inline double   BEToSystem(double v)    { return v; }
00918 
00919     // System (BE) to Little Endian
00920     inline UByte    SystemToLE(UByte  v)    { return SwapOrder(v); }
00921     inline SByte    SystemToLE(SByte  v)    { return SwapOrder(v); }
00922     inline UInt16   SystemToLE(UInt16 v)    { return SwapOrder(v); }
00923     inline SInt16   SystemToLE(SInt16 v)    { return SwapOrder(v); }
00924     inline UInt32   SystemToLE(UInt32 v)    { return SwapOrder(v); }
00925     inline SInt32   SystemToLE(SInt32 v)    { return SwapOrder(v); }
00926     inline UInt64   SystemToLE(UInt64 v)    { return SwapOrder(v); }
00927     inline SInt64   SystemToLE(SInt64 v)    { return SwapOrder(v); }
00928     inline float    SystemToLE(float  v)    { return SwapOrder(v); }
00929     inline double   SystemToLE(double v)    { return SwapOrder(v); }
00930 
00931     // System (BE) to Big Endian
00932     inline UByte    SystemToBE(UByte  v)    { return v; }
00933     inline SByte    SystemToBE(SByte  v)    { return v; }
00934     inline UInt16   SystemToBE(UInt16 v)    { return v; }
00935     inline SInt16   SystemToBE(SInt16 v)    { return v; }
00936     inline UInt32   SystemToBE(UInt32 v)    { return v; }
00937     inline SInt32   SystemToBE(SInt32 v)    { return v; }
00938     inline UInt64   SystemToBE(UInt64 v)    { return v; }
00939     inline SInt64   SystemToBE(SInt64 v)    { return v; }
00940     inline float    SystemToBE(float  v)    { return v; }
00941     inline double   SystemToBE(double v)    { return v; }
00942 
00943 #else
00944     #error "OVR_BYTE_ORDER must be defined to OVR_LITTLE_ENDIAN or OVR_BIG_ENDIAN"
00945 #endif
00946 
00947 } // namespace ByteUtil
00948 
00949 
00950 
00951 }} // OVR::Alg
00952 
00953 #endif


oculus_sdk
Author(s): Tully Foote
autogenerated on Thu Jun 6 2019 20:13:48