ovr_sdk

annotate LibOVR/Src/Kernel/OVR_Alg.h @ 0:1b39a1b46319

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