ovr_sdk
view LibOVR/Src/Kernel/OVR_Alg.h @ 3:f12a8f74fe1f
added the Xcode project
| author | John Tsiombikas <nuclear@member.fsf.org> |
|---|---|
| date | Wed, 21 Jan 2015 11:37:50 +0200 |
| parents | |
| children |
line source
1 /************************************************************************************
3 PublicHeader: OVR_Kernel.h
4 Filename : OVR_Alg.h
5 Content : Simple general purpose algorithms: Sort, Binary Search, etc.
6 Created : September 19, 2012
7 Notes :
9 Copyright : Copyright 2014 Oculus VR, LLC All Rights reserved.
11 Licensed under the Oculus VR Rift SDK License Version 3.2 (the "License");
12 you may not use the Oculus VR Rift SDK except in compliance with the License,
13 which is provided at the time of installation or download, or which
14 otherwise accompanies this software in either electronic or hard copy form.
16 You may obtain a copy of the License at
18 http://www.oculusvr.com/licenses/LICENSE-3.2
20 Unless required by applicable law or agreed to in writing, the Oculus VR SDK
21 distributed under the License is distributed on an "AS IS" BASIS,
22 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
23 See the License for the specific language governing permissions and
24 limitations under the License.
26 ************************************************************************************/
28 #ifndef OVR_Alg_h
29 #define OVR_Alg_h
31 #include "OVR_Types.h"
32 #include <string.h>
34 namespace OVR { namespace Alg {
37 //-----------------------------------------------------------------------------------
38 // ***** Operator extensions
40 template <typename T> OVR_FORCE_INLINE void Swap(T &a, T &b)
41 { T temp(a); a = b; b = temp; }
44 // ***** min/max are not implemented in Visual Studio 6 standard STL
46 template <typename T> OVR_FORCE_INLINE const T Min(const T a, const T b)
47 { return (a < b) ? a : b; }
49 template <typename T> OVR_FORCE_INLINE const T Max(const T a, const T b)
50 { return (b < a) ? a : b; }
52 template <typename T> OVR_FORCE_INLINE const T Clamp(const T v, const T minVal, const T maxVal)
53 { return Max<T>(minVal, Min<T>(v, maxVal)); }
55 template <typename T> OVR_FORCE_INLINE int Chop(T f)
56 { return (int)f; }
58 template <typename T> OVR_FORCE_INLINE T Lerp(T a, T b, T f)
59 { return (b - a) * f + a; }
62 // These functions stand to fix a stupid VC++ warning (with /Wp64 on):
63 // "warning C4267: 'argument' : conversion from 'size_t' to 'const unsigned', possible loss of data"
64 // Use these functions instead of gmin/gmax if the argument has size
65 // of the pointer to avoid the warning. Though, functionally they are
66 // absolutelly the same as regular gmin/gmax.
67 template <typename T> OVR_FORCE_INLINE const T PMin(const T a, const T b)
68 {
69 OVR_COMPILER_ASSERT(sizeof(T) == sizeof(size_t));
70 return (a < b) ? a : b;
71 }
72 template <typename T> OVR_FORCE_INLINE const T PMax(const T a, const T b)
73 {
74 OVR_COMPILER_ASSERT(sizeof(T) == sizeof(size_t));
75 return (b < a) ? a : b;
76 }
79 template <typename T> OVR_FORCE_INLINE const T Abs(const T v)
80 { return (v>=0) ? v : -v; }
83 //-----------------------------------------------------------------------------------
84 // ***** OperatorLess
85 //
86 template<class T> struct OperatorLess
87 {
88 static bool Compare(const T& a, const T& b)
89 {
90 return a < b;
91 }
92 };
95 //-----------------------------------------------------------------------------------
96 // ***** QuickSortSliced
97 //
98 // Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe.
99 // The range is specified with start, end, where "end" is exclusive!
100 // The comparison predicate must be specified.
101 template<class Array, class Less>
102 void QuickSortSliced(Array& arr, size_t start, size_t end, Less less)
103 {
104 enum
105 {
106 Threshold = 9
107 };
109 if(end - start < 2) return;
111 intptr_t stack[80];
112 intptr_t* top = stack;
113 intptr_t base = (intptr_t)start;
114 intptr_t limit = (intptr_t)end;
116 for(;;)
117 {
118 intptr_t len = limit - base;
119 intptr_t i, j, pivot;
121 if(len > Threshold)
122 {
123 // we use base + len/2 as the pivot
124 pivot = base + len / 2;
125 Swap(arr[base], arr[pivot]);
127 i = base + 1;
128 j = limit - 1;
130 // now ensure that *i <= *base <= *j
131 if(less(arr[j], arr[i])) Swap(arr[j], arr[i]);
132 if(less(arr[base], arr[i])) Swap(arr[base], arr[i]);
133 if(less(arr[j], arr[base])) Swap(arr[j], arr[base]);
135 for(;;)
136 {
137 do i++; while( less(arr[i], arr[base]) );
138 do j--; while( less(arr[base], arr[j]) );
140 if( i > j )
141 {
142 break;
143 }
145 Swap(arr[i], arr[j]);
146 }
148 Swap(arr[base], arr[j]);
150 // now, push the largest sub-array
151 if(j - base > limit - i)
152 {
153 top[0] = base;
154 top[1] = j;
155 base = i;
156 }
157 else
158 {
159 top[0] = i;
160 top[1] = limit;
161 limit = j;
162 }
163 top += 2;
164 }
165 else
166 {
167 // the sub-array is small, perform insertion sort
168 j = base;
169 i = j + 1;
171 for(; i < limit; j = i, i++)
172 {
173 for(; less(arr[j + 1], arr[j]); j--)
174 {
175 Swap(arr[j + 1], arr[j]);
176 if(j == base)
177 {
178 break;
179 }
180 }
181 }
182 if(top > stack)
183 {
184 top -= 2;
185 base = top[0];
186 limit = top[1];
187 }
188 else
189 {
190 break;
191 }
192 }
193 }
194 }
197 //-----------------------------------------------------------------------------------
198 // ***** QuickSortSliced
199 //
200 // Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe.
201 // The range is specified with start, end, where "end" is exclusive!
202 // The data type must have a defined "<" operator.
203 template<class Array>
204 void QuickSortSliced(Array& arr, size_t start, size_t end)
205 {
206 typedef typename Array::ValueType ValueType;
207 QuickSortSliced(arr, start, end, OperatorLess<ValueType>::Compare);
208 }
210 // Same as corresponding G_QuickSortSliced but with checking array limits to avoid
211 // crash in the case of wrong comparator functor.
212 template<class Array, class Less>
213 bool QuickSortSlicedSafe(Array& arr, size_t start, size_t end, Less less)
214 {
215 enum
216 {
217 Threshold = 9
218 };
220 if(end - start < 2) return true;
222 intptr_t stack[80];
223 intptr_t* top = stack;
224 intptr_t base = (intptr_t)start;
225 intptr_t limit = (intptr_t)end;
227 for(;;)
228 {
229 intptr_t len = limit - base;
230 intptr_t i, j, pivot;
232 if(len > Threshold)
233 {
234 // we use base + len/2 as the pivot
235 pivot = base + len / 2;
236 Swap(arr[base], arr[pivot]);
238 i = base + 1;
239 j = limit - 1;
241 // now ensure that *i <= *base <= *j
242 if(less(arr[j], arr[i])) Swap(arr[j], arr[i]);
243 if(less(arr[base], arr[i])) Swap(arr[base], arr[i]);
244 if(less(arr[j], arr[base])) Swap(arr[j], arr[base]);
246 for(;;)
247 {
248 do
249 {
250 i++;
251 if (i >= limit)
252 return false;
253 } while( less(arr[i], arr[base]) );
254 do
255 {
256 j--;
257 if (j < 0)
258 return false;
259 } while( less(arr[base], arr[j]) );
261 if( i > j )
262 {
263 break;
264 }
266 Swap(arr[i], arr[j]);
267 }
269 Swap(arr[base], arr[j]);
271 // now, push the largest sub-array
272 if(j - base > limit - i)
273 {
274 top[0] = base;
275 top[1] = j;
276 base = i;
277 }
278 else
279 {
280 top[0] = i;
281 top[1] = limit;
282 limit = j;
283 }
284 top += 2;
285 }
286 else
287 {
288 // the sub-array is small, perform insertion sort
289 j = base;
290 i = j + 1;
292 for(; i < limit; j = i, i++)
293 {
294 for(; less(arr[j + 1], arr[j]); j--)
295 {
296 Swap(arr[j + 1], arr[j]);
297 if(j == base)
298 {
299 break;
300 }
301 }
302 }
303 if(top > stack)
304 {
305 top -= 2;
306 base = top[0];
307 limit = top[1];
308 }
309 else
310 {
311 break;
312 }
313 }
314 }
315 return true;
316 }
318 template<class Array>
319 bool QuickSortSlicedSafe(Array& arr, size_t start, size_t end)
320 {
321 typedef typename Array::ValueType ValueType;
322 return QuickSortSlicedSafe(arr, start, end, OperatorLess<ValueType>::Compare);
323 }
325 //-----------------------------------------------------------------------------------
326 // ***** QuickSort
327 //
328 // Sort an array Array, ArrayPaged, ArrayUnsafe.
329 // The array must have GetSize() function.
330 // The comparison predicate must be specified.
331 template<class Array, class Less>
332 void QuickSort(Array& arr, Less less)
333 {
334 QuickSortSliced(arr, 0, arr.GetSize(), less);
335 }
337 // checks for boundaries
338 template<class Array, class Less>
339 bool QuickSortSafe(Array& arr, Less less)
340 {
341 return QuickSortSlicedSafe(arr, 0, arr.GetSize(), less);
342 }
345 //-----------------------------------------------------------------------------------
346 // ***** QuickSort
347 //
348 // Sort an array Array, ArrayPaged, ArrayUnsafe.
349 // The array must have GetSize() function.
350 // The data type must have a defined "<" operator.
351 template<class Array>
352 void QuickSort(Array& arr)
353 {
354 typedef typename Array::ValueType ValueType;
355 QuickSortSliced(arr, 0, arr.GetSize(), OperatorLess<ValueType>::Compare);
356 }
358 template<class Array>
359 bool QuickSortSafe(Array& arr)
360 {
361 typedef typename Array::ValueType ValueType;
362 return QuickSortSlicedSafe(arr, 0, arr.GetSize(), OperatorLess<ValueType>::Compare);
363 }
365 //-----------------------------------------------------------------------------------
366 // ***** InsertionSortSliced
367 //
368 // Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe.
369 // The range is specified with start, end, where "end" is exclusive!
370 // The comparison predicate must be specified.
371 // Unlike Quick Sort, the Insertion Sort works much slower in average,
372 // but may be much faster on almost sorted arrays. Besides, it guarantees
373 // that the elements will not be swapped if not necessary. For example,
374 // an array with all equal elements will remain "untouched", while
375 // Quick Sort will considerably shuffle the elements in this case.
376 template<class Array, class Less>
377 void InsertionSortSliced(Array& arr, size_t start, size_t end, Less less)
378 {
379 size_t j = start;
380 size_t i = j + 1;
381 size_t limit = end;
383 for(; i < limit; j = i, i++)
384 {
385 for(; less(arr[j + 1], arr[j]); j--)
386 {
387 Swap(arr[j + 1], arr[j]);
388 if(j <= start)
389 {
390 break;
391 }
392 }
393 }
394 }
397 //-----------------------------------------------------------------------------------
398 // ***** InsertionSortSliced
399 //
400 // Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe.
401 // The range is specified with start, end, where "end" is exclusive!
402 // The data type must have a defined "<" operator.
403 template<class Array>
404 void InsertionSortSliced(Array& arr, size_t start, size_t end)
405 {
406 typedef typename Array::ValueType ValueType;
407 InsertionSortSliced(arr, start, end, OperatorLess<ValueType>::Compare);
408 }
410 //-----------------------------------------------------------------------------------
411 // ***** InsertionSort
412 //
413 // Sort an array Array, ArrayPaged, ArrayUnsafe.
414 // The array must have GetSize() function.
415 // The comparison predicate must be specified.
417 template<class Array, class Less>
418 void InsertionSort(Array& arr, Less less)
419 {
420 InsertionSortSliced(arr, 0, arr.GetSize(), less);
421 }
423 //-----------------------------------------------------------------------------------
424 // ***** InsertionSort
425 //
426 // Sort an array Array, ArrayPaged, ArrayUnsafe.
427 // The array must have GetSize() function.
428 // The data type must have a defined "<" operator.
429 template<class Array>
430 void InsertionSort(Array& arr)
431 {
432 typedef typename Array::ValueType ValueType;
433 InsertionSortSliced(arr, 0, arr.GetSize(), OperatorLess<ValueType>::Compare);
434 }
436 //-----------------------------------------------------------------------------------
437 // ***** Median
438 // Returns a median value of the input array.
439 // Caveats: partially sorts the array, returns a reference to the array element
440 // TBD: This needs to be optimized and generalized
441 //
442 template<class Array>
443 typename Array::ValueType& Median(Array& arr)
444 {
445 size_t count = arr.GetSize();
446 size_t mid = (count - 1) / 2;
447 OVR_ASSERT(count > 0);
449 for (size_t j = 0; j <= mid; j++)
450 {
451 size_t min = j;
452 for (size_t k = j + 1; k < count; k++)
453 if (arr[k] < arr[min])
454 min = k;
455 Swap(arr[j], arr[min]);
456 }
457 return arr[mid];
458 }
460 //-----------------------------------------------------------------------------------
461 // ***** LowerBoundSliced
462 //
463 template<class Array, class Value, class Less>
464 size_t LowerBoundSliced(const Array& arr, size_t start, size_t end, const Value& val, Less less)
465 {
466 intptr_t first = (intptr_t)start;
467 intptr_t len = (intptr_t)(end - start);
468 intptr_t half;
469 intptr_t middle;
471 while(len > 0)
472 {
473 half = len >> 1;
474 middle = first + half;
475 if(less(arr[middle], val))
476 {
477 first = middle + 1;
478 len = len - half - 1;
479 }
480 else
481 {
482 len = half;
483 }
484 }
485 return (size_t)first;
486 }
489 //-----------------------------------------------------------------------------------
490 // ***** LowerBoundSliced
491 //
492 template<class Array, class Value>
493 size_t LowerBoundSliced(const Array& arr, size_t start, size_t end, const Value& val)
494 {
495 return LowerBoundSliced(arr, start, end, val, OperatorLess<Value>::Compare);
496 }
498 //-----------------------------------------------------------------------------------
499 // ***** LowerBoundSized
500 //
501 template<class Array, class Value>
502 size_t LowerBoundSized(const Array& arr, size_t size, const Value& val)
503 {
504 return LowerBoundSliced(arr, 0, size, val, OperatorLess<Value>::Compare);
505 }
507 //-----------------------------------------------------------------------------------
508 // ***** LowerBound
509 //
510 template<class Array, class Value, class Less>
511 size_t LowerBound(const Array& arr, const Value& val, Less less)
512 {
513 return LowerBoundSliced(arr, 0, arr.GetSize(), val, less);
514 }
517 //-----------------------------------------------------------------------------------
518 // ***** LowerBound
519 //
520 template<class Array, class Value>
521 size_t LowerBound(const Array& arr, const Value& val)
522 {
523 return LowerBoundSliced(arr, 0, arr.GetSize(), val, OperatorLess<Value>::Compare);
524 }
528 //-----------------------------------------------------------------------------------
529 // ***** UpperBoundSliced
530 //
531 template<class Array, class Value, class Less>
532 size_t UpperBoundSliced(const Array& arr, size_t start, size_t end, const Value& val, Less less)
533 {
534 intptr_t first = (intptr_t)start;
535 intptr_t len = (intptr_t)(end - start);
536 intptr_t half;
537 intptr_t middle;
539 while(len > 0)
540 {
541 half = len >> 1;
542 middle = first + half;
543 if(less(val, arr[middle]))
544 {
545 len = half;
546 }
547 else
548 {
549 first = middle + 1;
550 len = len - half - 1;
551 }
552 }
553 return (size_t)first;
554 }
557 //-----------------------------------------------------------------------------------
558 // ***** UpperBoundSliced
559 //
560 template<class Array, class Value>
561 size_t UpperBoundSliced(const Array& arr, size_t start, size_t end, const Value& val)
562 {
563 return UpperBoundSliced(arr, start, end, val, OperatorLess<Value>::Compare);
564 }
567 //-----------------------------------------------------------------------------------
568 // ***** UpperBoundSized
569 //
570 template<class Array, class Value>
571 size_t UpperBoundSized(const Array& arr, size_t size, const Value& val)
572 {
573 return UpperBoundSliced(arr, 0, size, val, OperatorLess<Value>::Compare);
574 }
577 //-----------------------------------------------------------------------------------
578 // ***** UpperBound
579 //
580 template<class Array, class Value, class Less>
581 size_t UpperBound(const Array& arr, const Value& val, Less less)
582 {
583 return UpperBoundSliced(arr, 0, arr.GetSize(), val, less);
584 }
587 //-----------------------------------------------------------------------------------
588 // ***** UpperBound
589 //
590 template<class Array, class Value>
591 size_t UpperBound(const Array& arr, const Value& val)
592 {
593 return UpperBoundSliced(arr, 0, arr.GetSize(), val, OperatorLess<Value>::Compare);
594 }
597 //-----------------------------------------------------------------------------------
598 // ***** ReverseArray
599 //
600 template<class Array> void ReverseArray(Array& arr)
601 {
602 intptr_t from = 0;
603 intptr_t to = arr.GetSize() - 1;
604 while(from < to)
605 {
606 Swap(arr[from], arr[to]);
607 ++from;
608 --to;
609 }
610 }
613 // ***** AppendArray
614 //
615 template<class CDst, class CSrc>
616 void AppendArray(CDst& dst, const CSrc& src)
617 {
618 size_t i;
619 for(i = 0; i < src.GetSize(); i++)
620 dst.PushBack(src[i]);
621 }
623 //-----------------------------------------------------------------------------------
624 // ***** ArrayAdaptor
625 //
626 // A simple adapter that provides the GetSize() method and overloads
627 // operator []. Used to wrap plain arrays in QuickSort and such.
628 template<class T> class ArrayAdaptor
629 {
630 public:
631 typedef T ValueType;
632 ArrayAdaptor() : Data(0), Size(0) {}
633 ArrayAdaptor(T* ptr, size_t size) : Data(ptr), Size(size) {}
634 size_t GetSize() const { return Size; }
635 int GetSizeI() const { return (int)GetSize(); }
636 const T& operator [] (size_t i) const { return Data[i]; }
637 T& operator [] (size_t i) { return Data[i]; }
638 private:
639 T* Data;
640 size_t Size;
641 };
644 //-----------------------------------------------------------------------------------
645 // ***** GConstArrayAdaptor
646 //
647 // A simple const adapter that provides the GetSize() method and overloads
648 // operator []. Used to wrap plain arrays in LowerBound and such.
649 template<class T> class ConstArrayAdaptor
650 {
651 public:
652 typedef T ValueType;
653 ConstArrayAdaptor() : Data(0), Size(0) {}
654 ConstArrayAdaptor(const T* ptr, size_t size) : Data(ptr), Size(size) {}
655 size_t GetSize() const { return Size; }
656 int GetSizeI() const { return (int)GetSize(); }
657 const T& operator [] (size_t i) const { return Data[i]; }
658 private:
659 const T* Data;
660 size_t Size;
661 };
665 //-----------------------------------------------------------------------------------
666 extern const uint8_t UpperBitTable[256];
667 extern const uint8_t LowerBitTable[256];
671 //-----------------------------------------------------------------------------------
672 inline uint8_t UpperBit(size_t val)
673 {
674 #ifndef OVR_64BIT_POINTERS
676 if (val & 0xFFFF0000)
677 {
678 return (val & 0xFF000000) ?
679 UpperBitTable[(val >> 24) ] + 24:
680 UpperBitTable[(val >> 16) & 0xFF] + 16;
681 }
682 return (val & 0xFF00) ?
683 UpperBitTable[(val >> 8) & 0xFF] + 8:
684 UpperBitTable[(val ) & 0xFF];
686 #else
688 if (val & 0xFFFFFFFF00000000)
689 {
690 if (val & 0xFFFF000000000000)
691 {
692 return (val & 0xFF00000000000000) ?
693 UpperBitTable[(val >> 56) ] + 56:
694 UpperBitTable[(val >> 48) & 0xFF] + 48;
695 }
696 return (val & 0xFF0000000000) ?
697 UpperBitTable[(val >> 40) & 0xFF] + 40:
698 UpperBitTable[(val >> 32) & 0xFF] + 32;
699 }
700 else
701 {
702 if (val & 0xFFFF0000)
703 {
704 return (val & 0xFF000000) ?
705 UpperBitTable[(val >> 24) ] + 24:
706 UpperBitTable[(val >> 16) & 0xFF] + 16;
707 }
708 return (val & 0xFF00) ?
709 UpperBitTable[(val >> 8) & 0xFF] + 8:
710 UpperBitTable[(val ) & 0xFF];
711 }
713 #endif
714 }
716 //-----------------------------------------------------------------------------------
717 inline uint8_t LowerBit(size_t val)
718 {
719 #ifndef OVR_64BIT_POINTERS
721 if (val & 0xFFFF)
722 {
723 return (val & 0xFF) ?
724 LowerBitTable[ val & 0xFF]:
725 LowerBitTable[(val >> 8) & 0xFF] + 8;
726 }
727 return (val & 0xFF0000) ?
728 LowerBitTable[(val >> 16) & 0xFF] + 16:
729 LowerBitTable[(val >> 24) & 0xFF] + 24;
731 #else
733 if (val & 0xFFFFFFFF)
734 {
735 if (val & 0xFFFF)
736 {
737 return (val & 0xFF) ?
738 LowerBitTable[ val & 0xFF]:
739 LowerBitTable[(val >> 8) & 0xFF] + 8;
740 }
741 return (val & 0xFF0000) ?
742 LowerBitTable[(val >> 16) & 0xFF] + 16:
743 LowerBitTable[(val >> 24) & 0xFF] + 24;
744 }
745 else
746 {
747 if (val & 0xFFFF00000000)
748 {
749 return (val & 0xFF00000000) ?
750 LowerBitTable[(val >> 32) & 0xFF] + 32:
751 LowerBitTable[(val >> 40) & 0xFF] + 40;
752 }
753 return (val & 0xFF000000000000) ?
754 LowerBitTable[(val >> 48) & 0xFF] + 48:
755 LowerBitTable[(val >> 56) & 0xFF] + 56;
756 }
758 #endif
759 }
763 // ******* Special (optimized) memory routines
764 // Note: null (bad) pointer is not tested
765 class MemUtil
766 {
767 public:
769 // Memory compare
770 static int Cmp (const void* p1, const void* p2, size_t byteCount) { return memcmp(p1, p2, byteCount); }
771 static int Cmp16(const void* p1, const void* p2, size_t int16Count);
772 static int Cmp32(const void* p1, const void* p2, size_t int32Count);
773 static int Cmp64(const void* p1, const void* p2, size_t int64Count);
774 };
776 // ** Inline Implementation
778 inline int MemUtil::Cmp16(const void* p1, const void* p2, size_t int16Count)
779 {
780 int16_t* pa = (int16_t*)p1;
781 int16_t* pb = (int16_t*)p2;
782 unsigned ic = 0;
783 if (int16Count == 0)
784 return 0;
785 while (pa[ic] == pb[ic])
786 if (++ic==int16Count)
787 return 0;
788 return pa[ic] > pb[ic] ? 1 : -1;
789 }
790 inline int MemUtil::Cmp32(const void* p1, const void* p2, size_t int32Count)
791 {
792 int32_t* pa = (int32_t*)p1;
793 int32_t* pb = (int32_t*)p2;
794 unsigned ic = 0;
795 if (int32Count == 0)
796 return 0;
797 while (pa[ic] == pb[ic])
798 if (++ic==int32Count)
799 return 0;
800 return pa[ic] > pb[ic] ? 1 : -1;
801 }
802 inline int MemUtil::Cmp64(const void* p1, const void* p2, size_t int64Count)
803 {
804 int64_t* pa = (int64_t*)p1;
805 int64_t* pb = (int64_t*)p2;
806 unsigned ic = 0;
807 if (int64Count == 0)
808 return 0;
809 while (pa[ic] == pb[ic])
810 if (++ic==int64Count)
811 return 0;
812 return pa[ic] > pb[ic] ? 1 : -1;
813 }
815 // ** End Inline Implementation
818 //-----------------------------------------------------------------------------------
819 // ******* Byte Order Conversions
820 namespace ByteUtil {
822 // *** Swap Byte Order
824 // Swap the byte order of a byte array
825 inline void SwapOrder(void* pv, int size)
826 {
827 uint8_t* pb = (uint8_t*)pv;
828 uint8_t temp;
829 for (int i = 0; i < size>>1; i++)
830 {
831 temp = pb[size-1-i];
832 pb[size-1-i] = pb[i];
833 pb[i] = temp;
834 }
835 }
837 // Swap the byte order of primitive types
838 inline uint8_t SwapOrder(uint8_t v) { return v; }
839 inline int8_t SwapOrder(int8_t v) { return v; }
840 inline uint16_t SwapOrder(uint16_t v) { return uint16_t(v>>8)|uint16_t(v<<8); }
841 inline int16_t SwapOrder(int16_t v) { return int16_t((uint16_t(v)>>8)|(v<<8)); }
842 inline uint32_t SwapOrder(uint32_t v) { return (v>>24)|((v&0x00FF0000)>>8)|((v&0x0000FF00)<<8)|(v<<24); }
843 inline int32_t SwapOrder(int32_t p) { return (int32_t)SwapOrder(uint32_t(p)); }
844 inline uint64_t SwapOrder(uint64_t v)
845 {
846 return (v>>56) |
847 ((v&uint64_t(0x00FF000000000000ULL))>>40) |
848 ((v&uint64_t(0x0000FF0000000000ULL))>>24) |
849 ((v&uint64_t(0x000000FF00000000ULL))>>8) |
850 ((v&uint64_t(0x00000000FF000000ULL))<<8) |
851 ((v&uint64_t(0x0000000000FF0000ULL))<<24) |
852 ((v&uint64_t(0x000000000000FF00ULL))<<40) |
853 (v<<56);
854 }
855 inline int64_t SwapOrder(int64_t v) { return (int64_t)SwapOrder(uint64_t(v)); }
856 inline float SwapOrder(float p)
857 {
858 union {
859 float p;
860 uint32_t v;
861 } u;
862 u.p = p;
863 u.v = SwapOrder(u.v);
864 return u.p;
865 }
867 inline double SwapOrder(double p)
868 {
869 union {
870 double p;
871 uint64_t v;
872 } u;
873 u.p = p;
874 u.v = SwapOrder(u.v);
875 return u.p;
876 }
878 // *** Byte-order conversion
880 #if (OVR_BYTE_ORDER == OVR_LITTLE_ENDIAN)
881 // Little Endian to System (LE)
882 inline uint8_t LEToSystem(uint8_t v) { return v; }
883 inline int8_t LEToSystem(int8_t v) { return v; }
884 inline uint16_t LEToSystem(uint16_t v) { return v; }
885 inline int16_t LEToSystem(int16_t v) { return v; }
886 inline uint32_t LEToSystem(uint32_t v) { return v; }
887 inline int32_t LEToSystem(int32_t v) { return v; }
888 inline uint64_t LEToSystem(uint64_t v) { return v; }
889 inline int64_t LEToSystem(int64_t v) { return v; }
890 inline float LEToSystem(float v) { return v; }
891 inline double LEToSystem(double v) { return v; }
893 // Big Endian to System (LE)
894 inline uint8_t BEToSystem(uint8_t v) { return SwapOrder(v); }
895 inline int8_t BEToSystem(int8_t v) { return SwapOrder(v); }
896 inline uint16_t BEToSystem(uint16_t v) { return SwapOrder(v); }
897 inline int16_t BEToSystem(int16_t v) { return SwapOrder(v); }
898 inline uint32_t BEToSystem(uint32_t v) { return SwapOrder(v); }
899 inline int32_t BEToSystem(int32_t v) { return SwapOrder(v); }
900 inline uint64_t BEToSystem(uint64_t v) { return SwapOrder(v); }
901 inline int64_t BEToSystem(int64_t v) { return SwapOrder(v); }
902 inline float BEToSystem(float v) { return SwapOrder(v); }
903 inline double BEToSystem(double v) { return SwapOrder(v); }
905 // System (LE) to Little Endian
906 inline uint8_t SystemToLE(uint8_t v) { return v; }
907 inline int8_t SystemToLE(int8_t v) { return v; }
908 inline uint16_t SystemToLE(uint16_t v) { return v; }
909 inline int16_t SystemToLE(int16_t v) { return v; }
910 inline uint32_t SystemToLE(uint32_t v) { return v; }
911 inline int32_t SystemToLE(int32_t v) { return v; }
912 inline uint64_t SystemToLE(uint64_t v) { return v; }
913 inline int64_t SystemToLE(int64_t v) { return v; }
914 inline float SystemToLE(float v) { return v; }
915 inline double SystemToLE(double v) { return v; }
917 // System (LE) to Big Endian
918 inline uint8_t SystemToBE(uint8_t v) { return SwapOrder(v); }
919 inline int8_t SystemToBE(int8_t v) { return SwapOrder(v); }
920 inline uint16_t SystemToBE(uint16_t v) { return SwapOrder(v); }
921 inline int16_t SystemToBE(int16_t v) { return SwapOrder(v); }
922 inline uint32_t SystemToBE(uint32_t v) { return SwapOrder(v); }
923 inline int32_t SystemToBE(int32_t v) { return SwapOrder(v); }
924 inline uint64_t SystemToBE(uint64_t v) { return SwapOrder(v); }
925 inline int64_t SystemToBE(int64_t v) { return SwapOrder(v); }
926 inline float SystemToBE(float v) { return SwapOrder(v); }
927 inline double SystemToBE(double v) { return SwapOrder(v); }
929 #elif (OVR_BYTE_ORDER == OVR_BIG_ENDIAN)
930 // Little Endian to System (BE)
931 inline uint8_t LEToSystem(uint8_t v) { return SwapOrder(v); }
932 inline int8_t LEToSystem(int8_t v) { return SwapOrder(v); }
933 inline uint16_t LEToSystem(uint16_t v) { return SwapOrder(v); }
934 inline int16_t LEToSystem(int16_t v) { return SwapOrder(v); }
935 inline uint32_t LEToSystem(uint32_t v) { return SwapOrder(v); }
936 inline int32_t LEToSystem(int32_t v) { return SwapOrder(v); }
937 inline uint64_t LEToSystem(uint64_t v) { return SwapOrder(v); }
938 inline int64_t LEToSystem(int64_t v) { return SwapOrder(v); }
939 inline float LEToSystem(float v) { return SwapOrder(v); }
940 inline double LEToSystem(double v) { return SwapOrder(v); }
942 // Big Endian to System (BE)
943 inline uint8_t BEToSystem(uint8_t v) { return v; }
944 inline int8_t BEToSystem(int8_t v) { return v; }
945 inline uint16_t BEToSystem(uint16_t v) { return v; }
946 inline int16_t BEToSystem(int16_t v) { return v; }
947 inline uint32_t BEToSystem(uint32_t v) { return v; }
948 inline int32_t BEToSystem(int32_t v) { return v; }
949 inline uint64_t BEToSystem(uint64_t v) { return v; }
950 inline int64_t BEToSystem(int64_t v) { return v; }
951 inline float BEToSystem(float v) { return v; }
952 inline double BEToSystem(double v) { return v; }
954 // System (BE) to Little Endian
955 inline uint8_t SystemToLE(uint8_t v) { return SwapOrder(v); }
956 inline int8_t SystemToLE(int8_t v) { return SwapOrder(v); }
957 inline uint16_t SystemToLE(uint16_t v) { return SwapOrder(v); }
958 inline int16_t SystemToLE(int16_t v) { return SwapOrder(v); }
959 inline uint32_t SystemToLE(uint32_t v) { return SwapOrder(v); }
960 inline int32_t SystemToLE(int32_t v) { return SwapOrder(v); }
961 inline uint64_t SystemToLE(uint64_t v) { return SwapOrder(v); }
962 inline int64_t SystemToLE(int64_t v) { return SwapOrder(v); }
963 inline float SystemToLE(float v) { return SwapOrder(v); }
964 inline double SystemToLE(double v) { return SwapOrder(v); }
966 // System (BE) to Big Endian
967 inline uint8_t SystemToBE(uint8_t v) { return v; }
968 inline int8_t SystemToBE(int8_t v) { return v; }
969 inline uint16_t SystemToBE(uint16_t v) { return v; }
970 inline int16_t SystemToBE(int16_t v) { return v; }
971 inline uint32_t SystemToBE(uint32_t v) { return v; }
972 inline int32_t SystemToBE(int32_t v) { return v; }
973 inline uint64_t SystemToBE(uint64_t v) { return v; }
974 inline int64_t SystemToBE(int64_t v) { return v; }
975 inline float SystemToBE(float v) { return v; }
976 inline double SystemToBE(double v) { return v; }
978 #else
979 #error "OVR_BYTE_ORDER must be defined to OVR_LITTLE_ENDIAN or OVR_BIG_ENDIAN"
980 #endif
982 } // namespace ByteUtil
986 // Used primarily for hardware interfacing such as sensor reports, firmware, etc.
987 // Reported data is all little-endian.
988 inline uint16_t DecodeUInt16(const uint8_t* buffer)
989 {
990 return ByteUtil::LEToSystem ( *(const uint16_t*)buffer );
991 }
993 inline int16_t DecodeSInt16(const uint8_t* buffer)
994 {
995 return ByteUtil::LEToSystem ( *(const int16_t*)buffer );
996 }
998 inline uint32_t DecodeUInt32(const uint8_t* buffer)
999 {
1000 return ByteUtil::LEToSystem ( *(const uint32_t*)buffer );
1001 }
1003 inline int32_t DecodeSInt32(const uint8_t* buffer)
1004 {
1005 return ByteUtil::LEToSystem ( *(const int32_t*)buffer );
1006 }
1008 inline float DecodeFloat(const uint8_t* buffer)
1009 {
1010 union {
1011 uint32_t U;
1012 float F;
1013 };
1015 U = DecodeUInt32(buffer);
1016 return F;
1017 }
1019 inline void EncodeUInt16(uint8_t* buffer, uint16_t val)
1020 {
1021 *(uint16_t*)buffer = ByteUtil::SystemToLE ( val );
1022 }
1024 inline void EncodeSInt16(uint8_t* buffer, int16_t val)
1025 {
1026 *(int16_t*)buffer = ByteUtil::SystemToLE ( val );
1027 }
1029 inline void EncodeUInt32(uint8_t* buffer, uint32_t val)
1030 {
1031 *(uint32_t*)buffer = ByteUtil::SystemToLE ( val );
1032 }
1034 inline void EncodeSInt32(uint8_t* buffer, int32_t val)
1035 {
1036 *(int32_t*)buffer = ByteUtil::SystemToLE ( val );
1037 }
1039 inline void EncodeFloat(uint8_t* buffer, float val)
1040 {
1041 union {
1042 uint32_t U;
1043 float F;
1044 };
1046 F = val;
1047 EncodeUInt32(buffer, U);
1048 }
1050 // Converts an 8-bit binary-coded decimal
1051 inline int8_t DecodeBCD(uint8_t byte)
1052 {
1053 uint8_t digit1 = (byte >> 4) & 0x0f;
1054 uint8_t digit2 = byte & 0x0f;
1055 int decimal = digit1 * 10 + digit2; // maximum value = 99
1056 return (int8_t)decimal;
1057 }
1060 }} // OVR::Alg
1062 #endif