icuSources/layout/OpenTypeUtilities.cpp

   1 /*
   2  * @(#)OpenTypeUtilities.cpp    1.6 00/03/15
   3  *
   4  * (C) Copyright IBM Corp. 1998-2003 - All Rights Reserved
   5  *
   6  */
   7
   8 #include "LETypes.h"
   9 #include "OpenTypeTables.h"
  10 #include "OpenTypeUtilities.h"
  11 #include "LESwaps.h"
  12
  13 U_NAMESPACE_BEGIN
  14
  15 //
  16 // Finds the high bit by binary searching
  17 // through the bits in n.
  18 //
  19 le_int8 OpenTypeUtilities::highBit(le_int32 value)
  20 {
  21     if (value <= 0) {
  22         return -32;
  23     }
  24
  25     le_uint8 bit = 0;
  26
  27     if (value >= 1 << 16) {
  28         value >>= 16;
  29         bit += 16;
  30     }
  31
  32     if (value >= 1 << 8) {
  33         value >>= 8;
  34         bit += 8;
  35     }
  36
  37     if (value >= 1 << 4) {
  38         value >>= 4;
  39         bit += 4;
  40     }
  41
  42     if (value >= 1 << 2) {
  43         value >>= 2;
  44         bit += 2;
  45     }
  46
  47     if (value >= 1 << 1) {
  48         value >>= 1;
  49         bit += 1;
  50     }
  51
  52     return bit;
  53 }
  54
  55 Offset OpenTypeUtilities::getTagOffset(LETag tag, const TagAndOffsetRecord *records, le_int32 recordCount)
  56 {
  57     le_uint8 bit = highBit(recordCount);
  58     le_int32 power = 1 << bit;
  59     le_int32 extra = recordCount - power;
  60     le_int32 probe = power;
  61     le_int32 index = 0;
  62
  63     if (SWAPT(records[extra].tag) <= tag) {
  64         index = extra;
  65     }
  66
  67     while (probe > (1 << 0)) {
  68         probe >>= 1;
  69
  70         if (SWAPT(records[index + probe].tag) <= tag) {
  71             index += probe;
  72         }
  73     }
  74
  75     if (SWAPT(records[index].tag) == tag) {
  76         return SWAPW(records[index].offset);
  77     }
  78
  79     return 0;
  80 }
  81
  82 le_int32 OpenTypeUtilities::getGlyphRangeIndex(TTGlyphID glyphID, const GlyphRangeRecord *records, le_int32 recordCount)
  83 {
  84     le_uint8 bit = highBit(recordCount);
  85     le_int32 power = 1 << bit;
  86     le_int32 extra = recordCount - power;
  87     le_int32 probe = power;
  88     le_int32 range = 0;
  89
  90     if (SWAPW(records[extra].firstGlyph) <= glyphID) {
  91         range = extra;
  92     }
  93
  94     while (probe > (1 << 0)) {
  95         probe >>= 1;
  96
  97         if (SWAPW(records[range + probe].firstGlyph) <= glyphID) {
  98             range += probe;
  99         }
 100     }
 101
 102     if (SWAPW(records[range].firstGlyph) <= glyphID && SWAPW(records[range].lastGlyph) >= glyphID) {
 103         return range;
 104     }
 105
 106     return -1;
 107 }
 108
 109 le_int32 OpenTypeUtilities::search(le_uint32 value, const le_uint32 array[], le_int32 count)
 110 {
 111     le_int32 power = 1 << highBit(count);
 112     le_int32 extra = count - power;
 113     le_int32 probe = power;
 114     le_int32 index = 0;
 115
 116     if (value >= array[extra]) {
 117         index = extra;
 118     }
 119
 120     while (probe > (1 << 0)) {
 121         probe >>= 1;
 122
 123         if (value >= array[index + probe]) {
 124             index += probe;
 125         }
 126     }
 127
 128     return index;
 129 }
 130
 131 le_int32 OpenTypeUtilities::search(le_uint16 value, const le_uint16 array[], le_int32 count)
 132 {
 133     le_int32 power = 1 << highBit(count);
 134     le_int32 extra = count - power;
 135     le_int32 probe = power;
 136     le_int32 index = 0;
 137
 138     if (value >= array[extra]) {
 139         index = extra;
 140     }
 141
 142     while (probe > (1 << 0)) {
 143         probe >>= 1;
 144
 145         if (value >= array[index + probe]) {
 146             index += probe;
 147         }
 148     }
 149
 150     return index;
 151 }
 152
 153 //
 154 // Straight insertion sort from Knuth vol. III, pg. 81
 155 //
 156 void OpenTypeUtilities::sort(le_uint16 *array, le_int32 count)
 157 {
 158     for (le_int32 j = 1; j < count; j += 1) {
 159         le_int32 i;
 160         le_uint16 v = array[j];
 161
 162         for (i = j - 1; i >= 0; i -= 1) {
 163             if (v >= array[i]) {
 164                 break;
 165             }
 166
 167             array[i + 1] = array[i];
 168         }
 169
 170         array[i + 1] = v;
 171     }
 172 }
 173
 174
 175
 176 U_NAMESPACE_END