gwnavruntime/kernel/SF_Alg.h Source File

SF_Alg.h
Go to the documentation of this file.
1 /*
2 * Copyright 2016 Autodesk, Inc. All rights reserved.
3 * Use of this software is subject to the terms of the Autodesk license agreement and any attachments or Appendices thereto provided at the time of installation or download,
4 * or which otherwise accompanies this software in either electronic or hard copy form, or which is signed by you and accepted by Autodesk.
5 */
6 
7 /**************************************************************************
8 
9 PublicHeader: None
10 Filename : KY_Alg.h
11 Content : Simple general purpose algorithms: Sort, Binary Search, etc.
12 Created :
13 Authors : Maxim Shemanarev
14 
15 **************************************************************************/
16 
17 #ifndef INC_KY_Kernel_Alg_H
18 #define INC_KY_Kernel_Alg_H
19 
20 #include "gwnavruntime/kernel/SF_Types.h"
21 #include <string.h>
22 
23 namespace Kaim { namespace Alg {
24 
25 
26 // ***** Operator extensions
27 
28 template <typename T> KY_INLINE void Swap(T &a, T &b)
29  { T temp(a); a = b; b = temp; }
30 
31 // Specialization for Pair()
32 template <typename T1, typename T2> KY_INLINE void Swap(Pair<T1, T2>& l, Pair<T1, T2>& r)
33  { Swap(l.First, r.First); Swap(l.Second, r.Second); }
34 
35 // ***** min/max are not implemented in Visual Studio 6 standard STL
36 
37 template <typename T> KY_INLINE const T Min(const T a, const T b)
38  { return (a < b) ? a : b; }
39 
40 template <typename T> KY_INLINE const T Max(const T a, const T b)
41  { return (b < a) ? a : b; }
42 
43 template <typename T> KY_INLINE const T Clamp(const T v, const T minVal, const T maxVal)
44  { return Max<T>(minVal, Min<T>(v, maxVal)); }
45 
46 template <typename T> KY_INLINE int Chop(T f)
47  { return (int)f; }
48 
49 template <typename T> KY_INLINE T Lerp(T a, T b, T f)
50  { return (b - a) * f + a; }
51 
52 template <typename T> KY_INLINE int IRound(const T a)
53  { return (a > 0.0) ? (int)(a + 0.5) : (int)(a - 0.5); }
54 
55 template <typename T> KY_INLINE unsigned URound(const T a)
56  { return (unsigned)(a + 0.5); }
57 
58 // These functions stand to fix a stupid VC++ warning (with /Wp64 on):
59 // "warning C4267: 'argument' : conversion from 'size_t' to 'const unsigned', possible loss of data"
60 // Use these functions instead of gmin/gmax if the argument has size
61 // of the pointer to avoid the warning. Though, functionally they are
62 // absolutelly the same as regular gmin/gmax.
63 template <typename T> KY_INLINE const T PMin(const T a, const T b)
64 {
65  KY_COMPILER_ASSERT(sizeof(T) == sizeof(UPInt));
66  return (a < b) ? a : b;
67 }
68 template <typename T> KY_INLINE const T PMax(const T a, const T b)
69 {
70  KY_COMPILER_ASSERT(sizeof(T) == sizeof(UPInt));
71  return (b < a) ? a : b;
72 }
73 
74 // Do not change the order of lines below, otherwise VC++ will gen warnings in /Wp64 mode
75 inline bool IsMax(UPInt v) { return v == KY_MAX_UPINT; }
76 #ifdef KY_64BIT_POINTERS
77 inline bool IsMax(unsigned v) { return v == KY_MAX_UINT; }
78 #endif
79 
80 // ***** abs
81 
82 template <typename T> KY_INLINE const T Abs(const T v)
83  { return (v>=0) ? v : -v; }
84 
85 
86 // ***** OperatorLess
87 //
88 //------------------------------------------------------------------------
89 template<class T> struct OperatorLess
90 {
91  static bool Compare(const T& a, const T& b)
92  {
93  return a < b;
94  }
95 };
96 
97 
98 // ***** QuickSortSliced
99 //
100 // Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe.
101 // The range is specified with start, end, where "end" is exclusive!
102 // The comparison predicate must be specified.
103 //
104 // The code of QuickSort, was taken from the
105 // Anti-Grain Geometry Project and modified for the use by Scaleform.
106 // Permission to use without restrictions is hereby granted to
107 // Scaleform Corp. by the author of Anti-Grain Geometry Project.
108 //------------------------------------------------------------------------
109 template<class Array, class Less>
110 void QuickSortSliced(Array& arr, UPInt start, UPInt end, Less less)
111 {
112  enum
113  {
114  Threshold = 9
115  };
116 
117  if(end - start < 2) return;
118 
119  SPInt stack[80];
120  SPInt* top = stack;
121  SPInt base = (SPInt)start;
122  SPInt limit = (SPInt)end;
123 
124  for(;;)
125  {
126  SPInt len = limit - base;
127  SPInt i, j, pivot;
128 
129  if(len > Threshold)
130  {
131  // we use base + len/2 as the pivot
132  pivot = base + len / 2;
133  Swap(arr[base], arr[pivot]);
134 
135  i = base + 1;
136  j = limit - 1;
137 
138  // now ensure that *i <= *base <= *j
139  if(less(arr[j], arr[i])) Swap(arr[j], arr[i]);
140  if(less(arr[base], arr[i])) Swap(arr[base], arr[i]);
141  if(less(arr[j], arr[base])) Swap(arr[j], arr[base]);
142 
143  for(;;)
144  {
145  do i++; while( less(arr[i], arr[base]) );
146  do j--; while( less(arr[base], arr[j]) );
147 
148  if( i > j )
149  {
150  break;
151  }
152 
153  Swap(arr[i], arr[j]);
154  }
155 
156  Swap(arr[base], arr[j]);
157 
158  // now, push the largest sub-array
159  if(j - base > limit - i)
160  {
161  top[0] = base;
162  top[1] = j;
163  base = i;
164  }
165  else
166  {
167  top[0] = i;
168  top[1] = limit;
169  limit = j;
170  }
171  top += 2;
172  }
173  else
174  {
175  // the sub-array is small, perform insertion sort
176  j = base;
177  i = j + 1;
178 
179  for(; i < limit; j = i, i++)
180  {
181  for(; less(arr[j + 1], arr[j]); j--)
182  {
183  Swap(arr[j + 1], arr[j]);
184  if(j == base)
185  {
186  break;
187  }
188  }
189  }
190  if(top > stack)
191  {
192  top -= 2;
193  base = top[0];
194  limit = top[1];
195  }
196  else
197  {
198  break;
199  }
200  }
201  }
202 }
203 
204 // ***** QuickSortSliced
205 //
206 // Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe.
207 // The range is specified with start, end, where "end" is exclusive!
208 // The data type must have a defined "<" operator.
209 //------------------------------------------------------------------------
210 template<class Array>
211 void QuickSortSliced(Array& arr, UPInt start, UPInt end)
212 {
213  typedef typename Array::ValueType ValueType;
214  QuickSortSliced(arr, start, end, OperatorLess<ValueType>::Compare);
215 }
216 
217 // Same as corresponding G_QuickSortSliced but with checking array limits to avoid
218 // crash in the case of wrong comparator functor.
219 template<class Array, class Less>
220 bool QuickSortSlicedSafe(Array& arr, UPInt start, UPInt end, Less less)
221 {
222  enum
223  {
224  Threshold = 9
225  };
226 
227  if(end - start < 2) return true;
228 
229  SPInt stack[80];
230  SPInt* top = stack;
231  SPInt base = (SPInt)start;
232  SPInt limit = (SPInt)end;
233 
234  for(;;)
235  {
236  SPInt len = limit - base;
237  SPInt i, j, pivot;
238 
239  if(len > Threshold)
240  {
241  // we use base + len/2 as the pivot
242  pivot = base + len / 2;
243  Swap(arr[base], arr[pivot]);
244 
245  i = base + 1;
246  j = limit - 1;
247 
248  // now ensure that *i <= *base <= *j
249  if(less(arr[j], arr[i])) Swap(arr[j], arr[i]);
250  if(less(arr[base], arr[i])) Swap(arr[base], arr[i]);
251  if(less(arr[j], arr[base])) Swap(arr[j], arr[base]);
252 
253  for(;;)
254  {
255  do
256  {
257  i++;
258  if (i >= limit)
259  return false;
260  } while( less(arr[i], arr[base]) );
261  do
262  {
263  j--;
264  if (j < 0)
265  return false;
266  } while( less(arr[base], arr[j]) );
267 
268  if( i > j )
269  {
270  break;
271  }
272 
273  Swap(arr[i], arr[j]);
274  }
275 
276  Swap(arr[base], arr[j]);
277 
278  // now, push the largest sub-array
279  if(j - base > limit - i)
280  {
281  top[0] = base;
282  top[1] = j;
283  base = i;
284  }
285  else
286  {
287  top[0] = i;
288  top[1] = limit;
289  limit = j;
290  }
291  top += 2;
292  }
293  else
294  {
295  // the sub-array is small, perform insertion sort
296  j = base;
297  i = j + 1;
298 
299  for(; i < limit; j = i, i++)
300  {
301  for(; less(arr[j + 1], arr[j]); j--)
302  {
303  Swap(arr[j + 1], arr[j]);
304  if(j == base)
305  {
306  break;
307  }
308  }
309  }
310  if(top > stack)
311  {
312  top -= 2;
313  base = top[0];
314  limit = top[1];
315  }
316  else
317  {
318  break;
319  }
320  }
321  }
322  return true;
323 }
324 
325 template<class Array>
326 bool QuickSortSlicedSafe(Array& arr, UPInt start, UPInt end)
327 {
328  typedef typename Array::ValueType ValueType;
329  return QuickSortSlicedSafe(arr, start, end, OperatorLess<ValueType>::Compare);
330 }
331 
332 //------------------------------------------------------------------------
333 // ***** QuickSort
334 //
335 // Sort an array Array, ArrayPaged, ArrayUnsafe.
336 // The array must have GetSize() function.
337 // The comparison predicate must be specified.
338 //------------------------------------------------------------------------
339 template<class Array, class Less>
340 void QuickSort(Array& arr, Less less)
341 {
342  QuickSortSliced(arr, 0, arr.GetSize(), less);
343 }
344 
345 // checks for boundaries
346 template<class Array, class Less>
347 bool QuickSortSafe(Array& arr, Less less)
348 {
349  return QuickSortSlicedSafe(arr, 0, arr.GetSize(), less);
350 }
351 
352 
353 //------------------------------------------------------------------------
354 // ***** QuickSort
355 //
356 // Sort an array Array, ArrayPaged, ArrayUnsafe.
357 // The array must have GetSize() function.
358 // The data type must have a defined "<" operator.
359 template<class Array>
360 void QuickSort(Array& arr)
361 {
362  typedef typename Array::ValueType ValueType;
363  QuickSortSliced(arr, 0, arr.GetSize(), OperatorLess<ValueType>::Compare);
364 }
365 
366 template<class Array>
367 bool QuickSortSafe(Array& arr)
368 {
369  typedef typename Array::ValueType ValueType;
370  return QuickSortSlicedSafe(arr, 0, arr.GetSize(), OperatorLess<ValueType>::Compare);
371 }
372 
373 // ***** InsertionSortSliced
374 //
375 // Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe.
376 // The range is specified with start, end, where "end" is exclusive!
377 // The comparison predicate must be specified.
378 // Unlike Quick Sort, the Insertion Sort works much slower in average,
379 // but may be much faster on almost sorted arrays. Besides, it guarantees
380 // that the elements will not be swapped if not necessary. For example,
381 // an array with all equal elements will remain "untouched", while
382 // Quick Sort will considerably shuffle the elements in this case.
383 //------------------------------------------------------------------------
384 template<class Array, class Less>
385 void InsertionSortSliced(Array& arr, UPInt start, UPInt end, Less less)
386 {
387  UPInt j = start;
388  UPInt i = j + 1;
389  UPInt limit = end;
390 
391  for(; i < limit; j = i, i++)
392  {
393  for(; less(arr[j + 1], arr[j]); j--)
394  {
395  Swap(arr[j + 1], arr[j]);
396  if(j <= start)
397  {
398  break;
399  }
400  }
401  }
402 }
403 
404 
405 
406 
407 // ***** InsertionSortSliced
408 //
409 // Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe.
410 // The range is specified with start, end, where "end" is exclusive!
411 // The data type must have a defined "<" operator.
412 //------------------------------------------------------------------------
413 template<class Array>
414 void InsertionSortSliced(Array& arr, UPInt start, UPInt end)
415 {
416  typedef typename Array::ValueType ValueType;
417  InsertionSortSliced(arr, start, end, OperatorLess<ValueType>::Compare);
418 }
419 
420 
421 // ***** InsertionSort
422 //
423 // Sort an array Array, ArrayPaged, ArrayUnsafe.
424 // The array must have GetSize() function.
425 // The comparison predicate must be specified.
426 //------------------------------------------------------------------------
427 template<class Array, class Less>
428 void InsertionSort(Array& arr, Less less)
429 {
430  InsertionSortSliced(arr, 0, arr.GetSize(), less);
431 }
432 
433 
434 // ***** InsertionSort
435 //
436 // Sort an array Array, ArrayPaged, ArrayUnsafe.
437 // The array must have GetSize() function.
438 // The data type must have a defined "<" operator.
439 //------------------------------------------------------------------------
440 template<class Array>
441 void InsertionSort(Array& arr)
442 {
443  typedef typename Array::ValueType ValueType;
444  InsertionSortSliced(arr, 0, arr.GetSize(), OperatorLess<ValueType>::Compare);
445 }
446 
447 
448 
449 
450 // ***** LowerBoundSliced
451 //
452 //-----------------------------------------------------------------------
453 template<class Array, class Value, class Less>
454 UPInt LowerBoundSliced(const Array& arr, UPInt start, UPInt end, const Value& val, Less less)
455 {
456  SPInt first = (SPInt)start;
457  SPInt len = (SPInt)(end - start);
458  SPInt half;
459  SPInt middle;
460 
461  while(len > 0)
462  {
463  half = len >> 1;
464  middle = first + half;
465  if(less(arr[middle], val))
466  {
467  first = middle + 1;
468  len = len - half - 1;
469  }
470  else
471  {
472  len = half;
473  }
474  }
475  return (UPInt)first;
476 }
477 
478 
479 // ***** LowerBoundSliced
480 //
481 //-----------------------------------------------------------------------
482 template<class Array, class Value>
483 UPInt LowerBoundSliced(const Array& arr, UPInt start, UPInt end, const Value& val)
484 {
485  return LowerBoundSliced(arr, start, end, val, OperatorLess<Value>::Compare);
486 }
487 
488 
489 // ***** LowerBoundSized
490 //
491 //-----------------------------------------------------------------------
492 template<class Array, class Value>
493 UPInt LowerBoundSized(const Array& arr, UPInt size, const Value& val)
494 {
495  return LowerBoundSliced(arr, 0, size, val, OperatorLess<Value>::Compare);
496 }
497 
498 
499 // ***** LowerBound
500 //
501 //-----------------------------------------------------------------------
502 template<class Array, class Value, class Less>
503 UPInt LowerBound(const Array& arr, const Value& val, Less less)
504 {
505  return LowerBoundSliced(arr, 0, arr.GetSize(), val, less);
506 }
507 
508 
509 // ***** LowerBound
510 //
511 //-----------------------------------------------------------------------
512 template<class Array, class Value>
513 UPInt LowerBound(const Array& arr, const Value& val)
514 {
515  return LowerBoundSliced(arr, 0, arr.GetSize(), val, OperatorLess<Value>::Compare);
516 }
517 
518 
519 
520 
521 // ***** UpperBoundSliced
522 //
523 //-----------------------------------------------------------------------
524 template<class Array, class Value, class Less>
525 UPInt UpperBoundSliced(const Array& arr, UPInt start, UPInt end, const Value& val, Less less)
526 {
527  SPInt first = (SPInt)start;
528  SPInt len = (SPInt)(end - start);
529  SPInt half;
530  SPInt middle;
531 
532  while(len > 0)
533  {
534  half = len >> 1;
535  middle = first + half;
536  if(less(val, arr[middle]))
537  {
538  len = half;
539  }
540  else
541  {
542  first = middle + 1;
543  len = len - half - 1;
544  }
545  }
546  return (UPInt)first;
547 }
548 
549 
550 // ***** UpperBoundSliced
551 //
552 //-----------------------------------------------------------------------
553 template<class Array, class Value>
554 UPInt UpperBoundSliced(const Array& arr, UPInt start, UPInt end, const Value& val)
555 {
556  return UpperBoundSliced(arr, start, end, val, OperatorLess<Value>::Compare);
557 }
558 
559 
560 // ***** UpperBoundSized
561 //
562 //-----------------------------------------------------------------------
563 template<class Array, class Value>
564 UPInt UpperBoundSized(const Array& arr, UPInt size, const Value& val)
565 {
566  return UpperBoundSliced(arr, 0, size, val, OperatorLess<Value>::Compare);
567 }
568 
569 
570 // ***** UpperBound
571 //
572 //-----------------------------------------------------------------------
573 template<class Array, class Value, class Less>
574 UPInt UpperBound(const Array& arr, const Value& val, Less less)
575 {
576  return UpperBoundSliced(arr, 0, arr.GetSize(), val, less);
577 }
578 
579 
580 // ***** UpperBound
581 //
582 //-----------------------------------------------------------------------
583 template<class Array, class Value>
584 UPInt UpperBound(const Array& arr, const Value& val)
585 {
586  return UpperBoundSliced(arr, 0, arr.GetSize(), val, OperatorLess<Value>::Compare);
587 }
588 
589 
590 // ***** ReverseArray
591 //
592 //-----------------------------------------------------------------------
593 template<class Array> void ReverseArray(Array& arr)
594 {
595  SPInt from = 0;
596  SPInt to = arr.GetSize() - 1;
597  while(from < to)
598  {
599  Swap(arr[from], arr[to]);
600  ++from;
601  --to;
602  }
603 }
604 
605 
606 
607 // ***** AppendArray
608 //
609 template<class CDst, class CSrc>
610 void AppendArray(CDst& dst, const CSrc& src)
611 {
612  UPInt i;
613  for(i = 0; i < src.GetSize(); i++)
614  dst.PushBack(src[i]);
615 }
616 
617 
618 // ***** ArrayAdaptor
619 //
620 // A simple adapter that provides the GetSize() method and overloads
621 // operator []. Used to wrap plain arrays in QuickSort and such.
622 //------------------------------------------------------------------------
623 template<class T> class ArrayAdaptor
624 {
625 public:
626  typedef T ValueType;
627  ArrayAdaptor() : Data(0), Size(0) {}
628  ArrayAdaptor(T* ptr, UPInt size) : Data(ptr), Size(size) {}
629  UPInt GetSize() const { return Size; }
630  const T& operator [] (UPInt i) const { return Data[i]; }
631  T& operator [] (UPInt i) { return Data[i]; }
632 private:
633  T* Data;
634  UPInt Size;
635 };
636 
637 
638 // ***** GConstArrayAdaptor
639 //
640 // A simple const adapter that provides the GetSize() method and overloads
641 // operator []. Used to wrap plain arrays in LowerBound and such.
642 //------------------------------------------------------------------------
643 template<class T> class ConstArrayAdaptor
644 {
645 public:
646  typedef T ValueType;
647  ConstArrayAdaptor() : Data(0), Size(0) {}
648  ConstArrayAdaptor(const T* ptr, UPInt size) : Data(ptr), Size(size) {}
649  UPInt GetSize() const { return Size; }
650  const T& operator [] (UPInt i) const { return Data[i]; }
651 private:
652  const T* Data;
653  UPInt Size;
654 };
655 
656 
657 
658 //------------------------------------------------------------------------
659 extern const UByte UpperBitTable[256];
660 extern const UByte LowerBitTable[256];
661 
662 
663 
664 //------------------------------------------------------------------------
665 inline UByte UpperBit(UPInt val)
666 {
667 #ifndef KY_64BIT_POINTERS
668 
669  if (val & 0xFFFF0000)
670  {
671  return (val & 0xFF000000) ?
672  UpperBitTable[(val >> 24) ] + 24:
673  UpperBitTable[(val >> 16) & 0xFF] + 16;
674  }
675  return (val & 0xFF00) ?
676  UpperBitTable[(val >> 8) & 0xFF] + 8:
677  UpperBitTable[(val ) & 0xFF];
678 
679 #else
680 
681  if (val & 0xFFFFFFFF00000000)
682  {
683  if (val & 0xFFFF000000000000)
684  {
685  return (val & 0xFF00000000000000) ?
686  UpperBitTable[(val >> 56) ] + 56:
687  UpperBitTable[(val >> 48) & 0xFF] + 48;
688  }
689  return (val & 0xFF0000000000) ?
690  UpperBitTable[(val >> 40) & 0xFF] + 40:
691  UpperBitTable[(val >> 32) & 0xFF] + 32;
692  }
693  else
694  {
695  if (val & 0xFFFF0000)
696  {
697  return (val & 0xFF000000) ?
698  UpperBitTable[(val >> 24) ] + 24:
699  UpperBitTable[(val >> 16) & 0xFF] + 16;
700  }
701  return (val & 0xFF00) ?
702  UpperBitTable[(val >> 8) & 0xFF] + 8:
703  UpperBitTable[(val ) & 0xFF];
704  }
705 
706 #endif
707 }
708 
709 //------------------------------------------------------------------------
710 inline UByte LowerBit(UPInt val)
711 {
712 #ifndef KY_64BIT_POINTERS
713 
714  if (val & 0xFFFF)
715  {
716  return (val & 0xFF) ?
717  LowerBitTable[ val & 0xFF]:
718  LowerBitTable[(val >> 8) & 0xFF] + 8;
719  }
720  return (val & 0xFF0000) ?
721  LowerBitTable[(val >> 16) & 0xFF] + 16:
722  LowerBitTable[(val >> 24) & 0xFF] + 24;
723 
724 #else
725 
726  if (val & 0xFFFFFFFF)
727  {
728  if (val & 0xFFFF)
729  {
730  return (val & 0xFF) ?
731  LowerBitTable[ val & 0xFF]:
732  LowerBitTable[(val >> 8) & 0xFF] + 8;
733  }
734  return (val & 0xFF0000) ?
735  LowerBitTable[(val >> 16) & 0xFF] + 16:
736  LowerBitTable[(val >> 24) & 0xFF] + 24;
737  }
738  else
739  {
740  if (val & 0xFFFF00000000)
741  {
742  return (val & 0xFF00000000) ?
743  LowerBitTable[(val >> 32) & 0xFF] + 32:
744  LowerBitTable[(val >> 40) & 0xFF] + 40;
745  }
746  return (val & 0xFF000000000000) ?
747  LowerBitTable[(val >> 48) & 0xFF] + 48:
748  LowerBitTable[(val >> 56) & 0xFF] + 56;
749  }
750 
751 #endif
752 }
753 
754 
755 
756 // ******* Special (optimized) memory routines
757 // Note: null (bad) pointer is not tested
758 class MemUtil
759 {
760 public:
761 
762  // Memory copy
763  static void* Copy (void* pdest, const void* psrc, UPInt byteCount) { return memcpy(pdest, psrc, byteCount); }
764  static void* Copy16(void* pdest, const void* psrc, UPInt int16Count) { return memcpy(pdest, psrc, int16Count*2); }
765  static void* Copy32(void* pdest, const void* psrc, UPInt int32Count) { return memcpy(pdest, psrc, int32Count*4); }
766  static void* Copy64(void* pdest, const void* psrc, UPInt int64Count) { return memcpy(pdest, psrc, int64Count*8); }
767 
768  // Memory move
769  static void* Move (void* pdest, const void* psrc, UPInt byteCount) { return memmove(pdest, psrc, byteCount); }
770  static void* Move16(void* pdest, const void* psrc, UPInt int16Count) { return memmove(pdest, psrc, int16Count*2); }
771  static void* Move32(void* pdest, const void* psrc, UPInt int32Count) { return memmove(pdest, psrc, int32Count*4); }
772  static void* Move64(void* pdest, const void* psrc, UPInt int64Count) { return memmove(pdest, psrc, int64Count*8); }
773 
774  // Memory compare
775  static int Cmp (const void* p1, const void* p2, UPInt byteCount) { return memcmp(p1, p2, byteCount); }
776  static int Cmp16(const void* p1, const void* p2, UPInt int16Count);
777  static int Cmp32(const void* p1, const void* p2, UPInt int32Count);
778  static int Cmp64(const void* p1, const void* p2, UPInt int64Count);
779 
780  // Memory set
781  static void Set (void* pdest, int value, UPInt byteCount) { memset(pdest, value, byteCount); }
782 };
783 
784 // ** Inline Implementation
785 
786 inline int MemUtil::Cmp16(const void* p1, const void* p2, UPInt int16Count)
787 {
788  SInt16* pa = (SInt16*)p1;
789  SInt16* pb = (SInt16*)p2;
790  unsigned ic = 0;
791  if (int16Count == 0)
792  return 0;
793  while (pa[ic] == pb[ic])
794  if (++ic==int16Count)
795  return 0;
796  return pa[ic] > pb[ic] ? 1 : -1;
797 }
798 
799 inline int MemUtil::Cmp32(const void* p1, const void* p2, UPInt int32Count)
800 {
801  SInt32* pa = (SInt32*)p1;
802  SInt32* pb = (SInt32*)p2;
803  unsigned ic = 0;
804  if (int32Count == 0)
805  return 0;
806  while (pa[ic] == pb[ic])
807  if (++ic==int32Count)
808  return 0;
809  return pa[ic] > pb[ic] ? 1 : -1;
810 }
811 inline int MemUtil::Cmp64(const void* p1, const void* p2, UPInt int64Count)
812 {
813  SInt64* pa = (SInt64*)p1;
814  SInt64* pb = (SInt64*)p2;
815  unsigned ic = 0;
816  if (int64Count == 0)
817  return 0;
818  while (pa[ic] == pb[ic])
819  if (++ic==int64Count)
820  return 0;
821  return pa[ic] > pb[ic] ? 1 : -1;
822 }
823 
824 // ** End Inline Implementation
825 
826 
827 
828 // ******* Byte Order Conversions
829 namespace ByteUtil {
830 
831  // *** Swap Byte Order
832 
833  // Swap the byte order of a byte array
834  inline void SwapOrder(void* pv, int size)
835  {
836  UByte* pb = (UByte*)pv;
837  UByte temp;
838  for (int i = 0; i < size>>1; i++)
839  {
840  temp = pb[size-1-i];
841  pb[size-1-i] = pb[i];
842  pb[i] = temp;
843  }
844  }
845 
846  // Swap the byte order of primitive types
847  inline UInt8 SwapOrder(UInt8 v) { return v; }
848  inline SInt8 SwapOrder(SInt8 v) { return v; }
849  inline UInt16 SwapOrder(UInt16 v) { return UInt16(v>>8)|UInt16(v<<8); }
850  inline SInt16 SwapOrder(SInt16 v) { return SInt16((UInt16(v)>>8)|(v<<8)); }
851  inline UInt32 SwapOrder(UInt32 v) { return (v>>24)|((v&0x00FF0000)>>8)|((v&0x0000FF00)<<8)|(v<<24); }
852  inline SInt32 SwapOrder(SInt32 p) { return (SInt32)SwapOrder(UInt32(p)); }
853  inline UInt64 SwapOrder(UInt64 v)
854  {
855  return (v>>56) |
856  ((v&KY_UINT64(0x00FF000000000000))>>40) |
857  ((v&KY_UINT64(0x0000FF0000000000))>>24) |
858  ((v&KY_UINT64(0x000000FF00000000))>>8) |
859  ((v&KY_UINT64(0x00000000FF000000))<<8) |
860  ((v&KY_UINT64(0x0000000000FF0000))<<24) |
861  ((v&KY_UINT64(0x000000000000FF00))<<40) |
862  (v<<56);
863  }
864  inline SInt64 SwapOrder(SInt64 v) { return (SInt64)SwapOrder(UInt64(v)); }
865  inline float SwapOrder(float p)
866  {
867  union {
868  float p;
869  UInt32 v;
870  } u;
871  u.p = p;
872  u.v = SwapOrder(u.v);
873  return u.p;
874  }
875 
876  inline double SwapOrder(double p)
877  {
878  union {
879  double p;
880  UInt64 v;
881  } u;
882  u.p = p;
883  u.v = SwapOrder(u.v);
884  return u.p;
885  }
886 
887  // *** Byte-order conversion
888 
889 #if (KY_BYTE_ORDER == KY_LITTLE_ENDIAN)
890  // Little Endian to System (LE)
891  inline UInt8 LEToSystem(UInt8 v) { return v; }
892  inline SInt8 LEToSystem(SInt8 v) { return v; }
893  inline UInt16 LEToSystem(UInt16 v) { return v; }
894  inline SInt16 LEToSystem(SInt16 v) { return v; }
895  inline UInt32 LEToSystem(UInt32 v) { return v; }
896  inline SInt32 LEToSystem(SInt32 v) { return v; }
897  inline UInt64 LEToSystem(UInt64 v) { return v; }
898  inline SInt64 LEToSystem(SInt64 v) { return v; }
899  inline float LEToSystem(float v) { return v; }
900  inline double LEToSystem(double v) { return v; }
901  // Big Endian to System (LE)
902  inline UInt8 BEToSystem(UInt8 v) { return SwapOrder(v); }
903  inline SInt8 BEToSystem(SInt8 v) { return SwapOrder(v); }
904  inline UInt16 BEToSystem(UInt16 v) { return SwapOrder(v); }
905  inline SInt16 BEToSystem(SInt16 v) { return SwapOrder(v); }
906  inline UInt32 BEToSystem(UInt32 v) { return SwapOrder(v); }
907  inline SInt32 BEToSystem(SInt32 v) { return SwapOrder(v); }
908  inline UInt64 BEToSystem(UInt64 v) { return SwapOrder(v); }
909  inline SInt64 BEToSystem(SInt64 v) { return SwapOrder(v); }
910  inline float BEToSystem(float v) { return SwapOrder(v); }
911  inline double BEToSystem(double v) { return SwapOrder(v); }
912  // System (LE) to Little Endian
913  inline UInt8 SystemToLE(UInt8 v) { return v; }
914  inline SInt8 SystemToLE(SInt8 v) { return v; }
915  inline UInt16 SystemToLE(UInt16 v) { return v; }
916  inline SInt16 SystemToLE(SInt16 v) { return v; }
917  inline UInt32 SystemToLE(UInt32 v) { return v; }
918  inline SInt32 SystemToLE(SInt32 v) { return v; }
919  inline UInt64 SystemToLE(UInt64 v) { return v; }
920  inline SInt64 SystemToLE(SInt64 v) { return v; }
921  inline float SystemToLE(float v) { return v; }
922  inline double SystemToLE(double v) { return v; }
923  // System (LE) to Big Endian
924  inline UInt8 SystemToBE(UInt8 v) { return SwapOrder(v); }
925  inline SInt8 SystemToBE(SInt8 v) { return SwapOrder(v); }
926  inline UInt16 SystemToBE(UInt16 v) { return SwapOrder(v); }
927  inline SInt16 SystemToBE(SInt16 v) { return SwapOrder(v); }
928  inline UInt32 SystemToBE(UInt32 v) { return SwapOrder(v); }
929  inline SInt32 SystemToBE(SInt32 v) { return SwapOrder(v); }
930  inline UInt64 SystemToBE(UInt64 v) { return SwapOrder(v); }
931  inline SInt64 SystemToBE(SInt64 v) { return SwapOrder(v); }
932  inline float SystemToBE(float v) { return SwapOrder(v); }
933  inline double SystemToBE(double v) { return SwapOrder(v); }
934 
935 #elif (KY_BYTE_ORDER == KY_BIG_ENDIAN)
936  // Little Endian to System (BE)
937  inline UInt8 LEToSystem(UInt8 v) { return SwapOrder(v); }
938  inline SInt8 LEToSystem(SInt8 v) { return SwapOrder(v); }
939  inline UInt16 LEToSystem(UInt16 v) { return SwapOrder(v); }
940  inline SInt16 LEToSystem(SInt16 v) { return SwapOrder(v); }
941  inline UInt32 LEToSystem(UInt32 v) { return SwapOrder(v); }
942  inline SInt32 LEToSystem(SInt32 v) { return SwapOrder(v); }
943  inline UInt64 LEToSystem(UInt64 v) { return SwapOrder(v); }
944  inline SInt64 LEToSystem(SInt64 v) { return SwapOrder(v); }
945  inline float LEToSystem(float v) { return SwapOrder(v); }
946  inline double LEToSystem(double v) { return SwapOrder(v); }
947  // Big Endian to System (BE)
948  inline UInt8 BEToSystem(UInt8 v) { return v; }
949  inline SInt8 BEToSystem(SInt8 v) { return v; }
950  inline UInt16 BEToSystem(UInt16 v) { return v; }
951  inline SInt16 BEToSystem(SInt16 v) { return v; }
952  inline UInt32 BEToSystem(UInt32 v) { return v; }
953  inline SInt32 BEToSystem(SInt32 v) { return v; }
954  inline UInt64 BEToSystem(UInt64 v) { return v; }
955  inline SInt64 BEToSystem(SInt64 v) { return v; }
956  inline float BEToSystem(float v) { return v; }
957  inline double BEToSystem(double v) { return v; }
958  // System (BE) to Little Endian
959  inline UInt8 SystemToLE(UInt8 v) { return SwapOrder(v); }
960  inline SInt8 SystemToLE(SInt8 v) { return SwapOrder(v); }
961  inline UInt16 SystemToLE(UInt16 v) { return SwapOrder(v); }
962  inline SInt16 SystemToLE(SInt16 v) { return SwapOrder(v); }
963  inline UInt32 SystemToLE(UInt32 v) { return SwapOrder(v); }
964  inline SInt32 SystemToLE(SInt32 v) { return SwapOrder(v); }
965  inline UInt64 SystemToLE(UInt64 v) { return SwapOrder(v); }
966  inline SInt64 SystemToLE(SInt64 v) { return SwapOrder(v); }
967  inline float SystemToLE(float v) { return SwapOrder(v); }
968  inline double SystemToLE(double v) { return SwapOrder(v); }
969  // System (BE) to Big Endian
970  inline UInt8 SystemToBE(UInt8 v) { return v; }
971  inline SInt8 SystemToBE(SInt8 v) { return v; }
972  inline UInt16 SystemToBE(UInt16 v) { return v; }
973  inline SInt16 SystemToBE(SInt16 v) { return v; }
974  inline UInt32 SystemToBE(UInt32 v) { return v; }
975  inline SInt32 SystemToBE(SInt32 v) { return v; }
976  inline UInt64 SystemToBE(UInt64 v) { return v; }
977  inline SInt64 SystemToBE(SInt64 v) { return v; }
978  inline float SystemToBE(float v) { return v; }
979  inline double SystemToBE(double v) { return v; }
980 
981 #else
982  #error "! KY_BYTE_ORDER must be defined to KY_LITTLE_ENDIAN or KY_BIG_ENDIAN !"
983 #endif
984 
985 } // namespace ByteUtil
986 
987 
988 template <class T>
989 inline UInt8 Cardinality(T v)
990 {
991  const T MASK_01010101 = (((T)(-1))/3);
992  const T MASK_00110011 = (((T)(-1))/5);
993  const T MASK_00001111 = (((T)(-1))/17);
994 
995  v = (v & MASK_01010101) + ((v >> 1) & MASK_01010101) ;
996  v = (v & MASK_00110011) + ((v >> 2) & MASK_00110011) ;
997  v = (v & MASK_00001111) + ((v >> 4) & MASK_00001111) ;
998  return (UInt8)(v % 255);
999 }
1000 
1001 
1002 inline UInt8 BitCount32(UInt32 value)
1003 {
1004  /* Binary search - decision tree (5 tests, rarely 6) */
1005  return
1006  ((value < 1UL<<15) ?
1007  ((value < 1UL<<7) ?
1008  ((value < 1UL<<3) ?
1009  ((value < 1UL<<1) ? ((value < 1UL<<0) ? 0 : 1) : ((value < 1UL<<2) ? 2 : 3)) :
1010  ((value < 1UL<<5) ? ((value < 1UL<<4) ? 4 : 5) : ((value < 1UL<<6) ? 6 : 7))) :
1011  ((value < 1UL<<11) ?
1012  ((value < 1UL<<9) ? ((value < 1UL<<8) ? 8 : 9) : ((value < 1UL<<10) ? 10 : 11)) :
1013  ((value < 1UL<<13) ? ((value < 1UL<<12) ? 12 : 13) : ((value < 1UL<<14) ? 14 : 15)))) :
1014  ((value < 1UL<<23) ?
1015  ((value < 1UL<<19) ?
1016  ((value < 1UL<<17) ? ((value < 1UL<<16) ? 16 : 17) : ((value < 1UL<<18) ? 18 : 19)) :
1017  ((value < 1UL<<21) ? ((value < 1UL<<20) ? 20 : 21) : ((value < 1UL<<22) ? 22 : 23))) :
1018  ((value < 1UL<<27) ?
1019  ((value < 1UL<<25) ? ((value < 1UL<<24) ? 24 : 25) : ((value < 1UL<<26) ? 26 : 27)) :
1020  ((value < 1UL<<29) ? ((value < 1UL<<28) ? 28 : 29) : ((value < 1UL<<30) ? 30 :
1021  ((value < 1UL<<31) ? 31 : 32))))));
1022 }
1023 
1024 }} // Scaleform Alg
1025 
1026 #endif
SF_Types.h
Kaim::SInt64
std::int64_t SInt64
int64_t
Definition: SF_Types.h:132
Kaim::UInt16
std::uint16_t UInt16
uint16_t
Definition: SF_Types.h:136
Kaim::UByte
std::uint8_t UByte
uint8_t
Definition: SF_Types.h:134
Kaim::SInt32
std::int32_t SInt32
int32_t
Definition: SF_Types.h:131
Kaim::UInt32
std::uint32_t UInt32
uint32_t
Definition: SF_Types.h:137
Kaim::SInt8
std::int8_t SInt8
int8_t
Definition: SF_Types.h:129
Kaim
The Autodesk Navigation namespace.
Definition: gamekitcrowddispersion.cpp:17
Kaim::UInt8
std::uint8_t UInt8
uint8_t
Definition: SF_Types.h:135
Kaim::UInt64
std::uint64_t UInt64
uint64_t
Definition: SF_Types.h:138
Kaim::SInt16
std::int16_t SInt16
int16_t
Definition: SF_Types.h:130
Please send us your comment about this page