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 //
highBit(le_int32 value)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
getTagOffset(LETag tag,const LEReferenceToArrayOf<TagAndOffsetRecord> & records,LEErrorCode & success)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
getGlyphRangeIndex(TTGlyphID glyphID,const LEReferenceToArrayOf<GlyphRangeRecord> & records,LEErrorCode & success)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
search(le_uint32 value,const le_uint32 array[],le_int32 count)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
search(le_uint16 value,const le_uint16 array[],le_int32 count)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 //
sort(le_uint16 * array,le_int32 count)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
letagToStr(LETag tag,char * str)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
_debug_LETableReference(const char * f,int l,const char * msg,const LETableReference * what,const void * ptr,size_t len)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