1ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru/* 2ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru ********************************************************************** 3ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * Copyright (C) 2002-2003, International Business Machines 4ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * Corporation and others. All Rights Reserved. 5ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru ********************************************************************** 6ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru */ 7ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 8ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#include "layout/LETypes.h" 9ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#include "LXUtilities.h" 10ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 11ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste QueruU_NAMESPACE_BEGIN 12ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 13ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru// 14ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru// Finds the high bit by binary searching 15ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru// through the bits in n. 16ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru// 17ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Querule_int8 LXUtilities::highBit(le_int32 value) 18ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru{ 19ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if (value <= 0) { 20ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return -32; 21ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 22ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 23ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru le_int8 bit = 0; 24ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 25ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if (value >= 1 << 16) { 26ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru value >>= 16; 27ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru bit += 16; 28ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 29ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 30ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if (value >= 1 << 8) { 31ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru value >>= 8; 32ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru bit += 8; 33ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 34ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 35ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if (value >= 1 << 4) { 36ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru value >>= 4; 37ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru bit += 4; 38ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 39ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 40ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if (value >= 1 << 2) { 41ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru value >>= 2; 42ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru bit += 2; 43ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 44ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 45ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if (value >= 1 << 1) { 46ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru value >>= 1; 47ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru bit += 1; 48ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 49ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 50ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return bit; 51ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 52ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 53ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Querule_int32 LXUtilities::search(le_int32 value, const le_int32 array[], le_int32 count) 54ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru{ 55ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru le_int32 power = 1 << highBit(count); 56ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru le_int32 extra = count - power; 57ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru le_int32 probe = power; 58ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru le_int32 index = 0; 59ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 60ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if (value >= array[extra]) { 61ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru index = extra; 62ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 63ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 64ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru while (probe > (1 << 0)) { 65ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru probe >>= 1; 66ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 67ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if (value >= array[index + probe]) { 68ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru index += probe; 69ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 70ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 71ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 72ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return index; 73ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 74ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 75ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queruvoid LXUtilities::reverse(le_int32 array[], le_int32 length) 76ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru{ 77ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru le_int32 front, back; 78ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 79ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru for (front = 0, back = length - 1; front < back; front += 1, back -= 1) { 80ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru le_int32 swap = array[front]; 81ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 82ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru array[front] = array[back]; 83ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru array[back] = swap; 84ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 85ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 86ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 87ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queruvoid LXUtilities::reverse(float array[], le_int32 length) 88ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru{ 89ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru le_int32 front, back; 90ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 91ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru for (front = 0, back = length - 1; front < back; front += 1, back -= 1) { 92ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru float swap = array[front]; 93ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 94ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru array[front] = array[back]; 95ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru array[back] = swap; 96ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 97ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 98ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 99ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste QueruU_NAMESPACE_END 100