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 //
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
getTagOffset(LETag tag,const TagAndOffsetRecord * records,le_int32 recordCount)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
getGlyphRangeIndex(TTGlyphID glyphID,const GlyphRangeRecord * records,le_int32 recordCount)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
search(le_uint32 value,const le_uint32 array[],le_int32 count)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
search(le_uint16 value,const le_uint16 array[],le_int32 count)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 //
sort(le_uint16 * array,le_int32 count)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