1 /* 2 * 3 * (C) Copyright IBM Corp. 1998-2013 - 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 55 Offset OpenTypeUtilities::getTagOffset(LETag tag, const LEReferenceToArrayOf<TagAndOffsetRecord> &records, LEErrorCode &success) 56 { 57 const TagAndOffsetRecord *r0 = (const TagAndOffsetRecord*)records.getAlias(); 58 if(LE_FAILURE(success)) return 0; 59 60 le_uint32 recordCount = records.getCount(); 61 le_uint8 bit = highBit(recordCount); 62 le_int32 power = 1 << bit; 63 le_int32 extra = recordCount - power; 64 le_int32 probe = power; 65 le_int32 index = 0; 66 67 { 68 const ATag &aTag = (r0+extra)->tag; 69 if (SWAPT(aTag) <= tag) { 70 index = extra; 71 } 72 } 73 74 while (probe > (1 << 0)) { 75 probe >>= 1; 76 77 { 78 const ATag &aTag = (r0+index+probe)->tag; 79 if (SWAPT(aTag) <= tag) { 80 index += probe; 81 } 82 } 83 } 84 85 { 86 const ATag &aTag = (r0+index)->tag; 87 if (SWAPT(aTag) == tag) { 88 return SWAPW((r0+index)->offset); 89 } 90 } 91 92 return 0; 93 } 94 95 le_int32 OpenTypeUtilities::getGlyphRangeIndex(TTGlyphID glyphID, const LEReferenceToArrayOf<GlyphRangeRecord> &records, LEErrorCode &success) 96 { 97 if(LE_FAILURE(success)) return -1; 98 99 le_uint32 recordCount = records.getCount(); 100 le_uint8 bit = highBit(recordCount); 101 le_int32 power = 1 << bit; 102 le_int32 extra = recordCount - power; 103 le_int32 probe = power; 104 le_int32 range = 0; 105 106 if (recordCount == 0) { 107 return -1; 108 } 109 110 if (SWAPW(records(extra,success).firstGlyph) <= glyphID) { 111 range = extra; 112 } 113 114 while (probe > (1 << 0) && LE_SUCCESS(success)) { 115 probe >>= 1; 116 117 if (SWAPW(records(range + probe,success).firstGlyph) <= glyphID) { 118 range += probe; 119 } 120 } 121 122 if (SWAPW(records(range,success).firstGlyph) <= glyphID && SWAPW(records(range,success).lastGlyph) >= glyphID) { 123 return range; 124 } 125 126 return -1; 127 } 128 129 le_int32 OpenTypeUtilities::search(le_uint32 value, const le_uint32 array[], le_int32 count) 130 { 131 le_int32 power = 1 << highBit(count); 132 le_int32 extra = count - power; 133 le_int32 probe = power; 134 le_int32 index = 0; 135 136 if (value >= array[extra]) { 137 index = extra; 138 } 139 140 while (probe > (1 << 0)) { 141 probe >>= 1; 142 143 if (value >= array[index + probe]) { 144 index += probe; 145 } 146 } 147 148 return index; 149 } 150 151 le_int32 OpenTypeUtilities::search(le_uint16 value, const le_uint16 array[], le_int32 count) 152 { 153 le_int32 power = 1 << highBit(count); 154 le_int32 extra = count - power; 155 le_int32 probe = power; 156 le_int32 index = 0; 157 158 if (value >= array[extra]) { 159 index = extra; 160 } 161 162 while (probe > (1 << 0)) { 163 probe >>= 1; 164 165 if (value >= array[index + probe]) { 166 index += probe; 167 } 168 } 169 170 return index; 171 } 172 173 // 174 // Straight insertion sort from Knuth vol. III, pg. 81 175 // 176 void OpenTypeUtilities::sort(le_uint16 *array, le_int32 count) 177 { 178 for (le_int32 j = 1; j < count; j += 1) { 179 le_int32 i; 180 le_uint16 v = array[j]; 181 182 for (i = j - 1; i >= 0; i -= 1) { 183 if (v >= array[i]) { 184 break; 185 } 186 187 array[i + 1] = array[i]; 188 } 189 190 array[i + 1] = v; 191 } 192 } 193 194 U_NAMESPACE_END 195 196 #if LE_ASSERT_BAD_FONT 197 #include <stdio.h> 198 199 static const char *letagToStr(LETag tag, char *str) { 200 str[0]= 0xFF & (tag>>24); 201 str[1]= 0xFF & (tag>>16); 202 str[2]= 0xFF & (tag>>8); 203 str[3]= 0xFF & (tag>>0); 204 str[4]= 0; 205 return str; 206 } 207 208 U_CAPI void U_EXPORT2 _debug_LETableReference(const char *f, int l, const char *msg, const LETableReference *what, const void *ptr, size_t len) { 209 char tagbuf[5]; 210 211 fprintf(stderr, "%s:%d: LETableReference@0x%p: ", f, l, what); 212 fprintf(stderr, msg, ptr, len); 213 fprintf(stderr, "\n"); 214 215 for(int depth=0;depth<10&&(what!=NULL);depth++) { 216 for(int i=0;i<depth;i++) { 217 fprintf(stderr, " "); // indent 218 } 219 if(!what->isValid()) { 220 fprintf(stderr, "(invalid)"); 221 } 222 fprintf(stderr, "@%p: tag (%s) font (0x%p), [0x%p+0x%lx]\n", what, letagToStr(what->getTag(), tagbuf), what->getFont(), 223 what->getAlias(), what->getLength()); 224 225 what = what->getParent(); 226 } 227 } 228 #endif 229
