OpenTypeUtilities.cpp revision 51cfa1a9a96cad34675a6415fe86dfdf3f525bb6 
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
12U_NAMESPACE_BEGIN
13
14//
15// Finds the high bit by binary searching
16// through the bits in n.
17//
18le_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
54Offset 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
81le_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
112le_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
134le_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//
159void 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
179U_NAMESPACE_END
180