icuSources/layout/OpenTypeUtilities.cpp

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