1/* 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 3 * 4 * This code is free software; you can redistribute it and/or modify it 5 * under the terms of the GNU General Public License version 2 only, as 6 * published by the Free Software Foundation. Oracle designates this 7 * particular file as subject to the "Classpath" exception as provided 8 * by Oracle in the LICENSE file that accompanied this code. 9 * 10 * This code is distributed in the hope that it will be useful, but WITHOUT 11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 13 * version 2 for more details (a copy is included in the LICENSE file that 14 * accompanied this code). 15 * 16 * You should have received a copy of the GNU General Public License version 17 * 2 along with this work; if not, write to the Free Software Foundation, 18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 19 * 20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 21 * or visit www.oracle.com if you need additional information or have any 22 * questions. 23 * 24 */ 25 26/* 27 * 28 * (C) Copyright IBM Corp. 1998-2010 - All Rights Reserved 29 * 30 */ 31 32#include "LETypes.h" 33#include "OpenTypeTables.h" 34#include "OpenTypeUtilities.h" 35#include "LESwaps.h" 36 37U_NAMESPACE_BEGIN 38 39// 40// Finds the high bit by binary searching 41// through the bits in n. 42// 43le_int8 OpenTypeUtilities::highBit(le_int32 value) 44{ 45 if (value <= 0) { 46 return -32; 47 } 48 49 le_uint8 bit = 0; 50 51 if (value >= 1 << 16) { 52 value >>= 16; 53 bit += 16; 54 } 55 56 if (value >= 1 << 8) { 57 value >>= 8; 58 bit += 8; 59 } 60 61 if (value >= 1 << 4) { 62 value >>= 4; 63 bit += 4; 64 } 65 66 if (value >= 1 << 2) { 67 value >>= 2; 68 bit += 2; 69 } 70 71 if (value >= 1 << 1) { 72 value >>= 1; 73 bit += 1; 74 } 75 76 return bit; 77} 78 79 80Offset OpenTypeUtilities::getTagOffset(LETag tag, const LEReferenceToArrayOf<TagAndOffsetRecord> &records, LEErrorCode &success) 81{ 82 if(LE_FAILURE(success)) return 0; 83 const TagAndOffsetRecord *r0 = (const TagAndOffsetRecord*)records.getAlias(); 84 85 le_uint32 recordCount = records.getCount(); 86 le_uint8 bit = highBit(recordCount); 87 le_int32 power = 1 << bit; 88 le_int32 extra = recordCount - power; 89 le_int32 probe = power; 90 le_int32 index = 0; 91 92 { 93 const ATag &aTag = (r0+extra)->tag; 94 if (SWAPT(aTag) <= tag) { 95 index = extra; 96 } 97 } 98 99 while (probe > (1 << 0)) { 100 probe >>= 1; 101 102 { 103 const ATag &aTag = (r0+index+probe)->tag; 104 if (SWAPT(aTag) <= tag) { 105 index += probe; 106 } 107 } 108 } 109 110 { 111 const ATag &aTag = (r0+index)->tag; 112 if (SWAPT(aTag) == tag) { 113 return SWAPW((r0+index)->offset); 114 } 115 } 116 117 return 0; 118} 119 120le_int32 OpenTypeUtilities::getGlyphRangeIndex(TTGlyphID glyphID, const LEReferenceToArrayOf<GlyphRangeRecord> &records, LEErrorCode &success) 121{ 122 if(LE_FAILURE(success)) return -1; 123 124 le_uint32 recordCount = records.getCount(); 125 le_uint8 bit = highBit(recordCount); 126 le_int32 power = 1 << bit; 127 le_int32 extra = recordCount - power; 128 le_int32 probe = power; 129 le_int32 range = 0; 130 131 if (recordCount == 0) { 132 return -1; 133 } 134 135 if (SWAPW(records(extra,success).firstGlyph) <= glyphID) { 136 range = extra; 137 } 138 139 while (probe > (1 << 0) && LE_SUCCESS(success)) { 140 probe >>= 1; 141 142 if (SWAPW(records(range + probe,success).firstGlyph) <= glyphID) { 143 range += probe; 144 } 145 } 146 147 if (SWAPW(records(range,success).firstGlyph) <= glyphID && SWAPW(records(range,success).lastGlyph) >= glyphID) { 148 return range; 149 } 150 151 return -1; 152} 153 154le_int32 OpenTypeUtilities::search(le_uint32 value, const le_uint32 array[], le_int32 count) 155{ 156 le_int32 power = 1 << highBit(count); 157 le_int32 extra = count - power; 158 le_int32 probe = power; 159 le_int32 index = 0; 160 161 if (value >= array[extra]) { 162 index = extra; 163 } 164 165 while (probe > (1 << 0)) { 166 probe >>= 1; 167 168 if (value >= array[index + probe]) { 169 index += probe; 170 } 171 } 172 173 return index; 174} 175 176le_int32 OpenTypeUtilities::search(le_uint16 value, const le_uint16 array[], le_int32 count) 177{ 178 le_int32 power = 1 << highBit(count); 179 le_int32 extra = count - power; 180 le_int32 probe = power; 181 le_int32 index = 0; 182 183 if (value >= array[extra]) { 184 index = extra; 185 } 186 187 while (probe > (1 << 0)) { 188 probe >>= 1; 189 190 if (value >= array[index + probe]) { 191 index += probe; 192 } 193 } 194 195 return index; 196} 197 198// 199// Straight insertion sort from Knuth vol. III, pg. 81 200// 201void OpenTypeUtilities::sort(le_uint16 *array, le_int32 count) 202{ 203 for (le_int32 j = 1; j < count; j += 1) { 204 le_int32 i; 205 le_uint16 v = array[j]; 206 207 for (i = j - 1; i >= 0; i -= 1) { 208 if (v >= array[i]) { 209 break; 210 } 211 212 array[i + 1] = array[i]; 213 } 214 215 array[i + 1] = v; 216 } 217} 218 219U_NAMESPACE_END 220 221#if LE_ASSERT_BAD_FONT 222#include <stdio.h> 223 224static const char *letagToStr(LETag tag, char *str) { 225 str[0]= 0xFF & (tag>>24); 226 str[1]= 0xFF & (tag>>16); 227 str[2]= 0xFF & (tag>>8); 228 str[3]= 0xFF & (tag>>0); 229 str[4]= 0; 230 return str; 231} 232 233U_CAPI void U_EXPORT2 _debug_LETableReference(const char *f, int l, const char *msg, const LETableReference *what, const void *ptr, size_t len) { 234 char tagbuf[5]; 235 236 fprintf(stderr, "%s:%d: LETableReference@0x%p: ", f, l, what); 237 fprintf(stderr, msg, ptr, len); 238 fprintf(stderr, "\n"); 239 240 for(int depth=0;depth<10&&(what!=NULL);depth++) { 241 for(int i=0;i<depth;i++) { 242 fprintf(stderr, " "); // indent 243 } 244 if(!what->isValid()) { 245 fprintf(stderr, "(invalid)"); 246 } 247 fprintf(stderr, "@%p: tag (%s) font (0x%p), [0x%p+0x%lx]\n", what, letagToStr(what->getTag(), tagbuf), what->getFont(), 248 what->getAlias(), what->getLength()); 249 250 what = what->getParent(); 251 } 252} 253#endif 254