icuSources/layout/OpenTypeUtilities.cpp

   1 /*
   2  *
   3  * (C) Copyright IBM Corp. 1998-2004 - 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 (SWAPW(records[extra].firstGlyph) <= glyphID) {
  90         range = extra;
  91     }
  92
  93     while (probe > (1 << 0)) {
  94         probe >>= 1;
  95
  96         if (SWAPW(records[range + probe].firstGlyph) <= glyphID) {
  97             range += probe;
  98         }
  99     }
 100
 101     if (SWAPW(records[range].firstGlyph) <= glyphID && SWAPW(records[range].lastGlyph) >= glyphID) {
 102         return range;
 103     }
 104
 105     return -1;
 106 }
 107
 108 le_int32 OpenTypeUtilities::search(le_uint32 value, const le_uint32 array[], le_int32 count)
 109 {
 110     le_int32 power = 1 << highBit(count);
 111     le_int32 extra = count - power;
 112     le_int32 probe = power;
 113     le_int32 index = 0;
 114
 115     if (value >= array[extra]) {
 116         index = extra;
 117     }
 118
 119     while (probe > (1 << 0)) {
 120         probe >>= 1;
 121
 122         if (value >= array[index + probe]) {
 123             index += probe;
 124         }
 125     }
 126
 127     return index;
 128 }
 129
 130 le_int32 OpenTypeUtilities::search(le_uint16 value, const le_uint16 array[], le_int32 count)
 131 {
 132     le_int32 power = 1 << highBit(count);
 133     le_int32 extra = count - power;
 134     le_int32 probe = power;
 135     le_int32 index = 0;
 136
 137     if (value >= array[extra]) {
 138         index = extra;
 139     }
 140
 141     while (probe > (1 << 0)) {
 142         probe >>= 1;
 143
 144         if (value >= array[index + probe]) {
 145             index += probe;
 146         }
 147     }
 148
 149     return index;
 150 }
 151
 152 //
 153 // Straight insertion sort from Knuth vol. III, pg. 81
 154 //
 155 void OpenTypeUtilities::sort(le_uint16 *array, le_int32 count)
 156 {
 157     for (le_int32 j = 1; j < count; j += 1) {
 158         le_int32 i;
 159         le_uint16 v = array[j];
 160
 161         for (i = j - 1; i >= 0; i -= 1) {
 162             if (v >= array[i]) {
 163                 break;
 164             }
 165
 166             array[i + 1] = array[i];
 167         }
 168
 169         array[i + 1] = v;
 170     }
 171 }
 172
 173
 174
 175 U_NAMESPACE_END