Home | History | Annotate | Download | only in layout 
      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
    180