← Back to branch summary

~ubuntu-branches/ubuntu/gutsy/icu/gutsy-updates

« back to all changes in this revision

Viewing changes to source/layout/OpenTypeUtilities.cpp

  • Committer: Package Import Robot
  • Author(s): Jay Berkenbilt
  • Date: 2005-11-19 11:29:31 UTC
  • mfrom: (1.1.2)
  • Revision ID: package-import@ubuntu.com-20051119112931-vcizkrp10tli4enw
Tags: 3.4-3
Explicitly build with g++ 3.4.  The current ICU fails its test suite
with 4.0 but not with 3.4.  Future versions should work properly with
4.0.

Show diffs side-by-side

added added

removed removed

Lines of Context:
source/layout/OpenTypeUtilities.cpp
1
 
/*
2
 
 * @(#)OpenTypeUtilities.cpp    1.6 00/03/15
3
 
 *
4
 
 * (C) Copyright IBM Corp. 1998, 1999, 2000, 2001 - All Rights Reserved
5
 
 *
6
 
 */
7
 
 
8
 
#include "LETypes.h"
9
 
#include "OpenTypeTables.h"
10
 
#include "OpenTypeUtilities.h"
11
 
#include "LESwaps.h"
12
 
 
13
 
U_NAMESPACE_BEGIN
14
 
 
15
 
//
16
 
// Finds the high bit by binary searching
17
 
// through the bits in n.
18
 
//
19
 
le_int8 OpenTypeUtilities::highBit(le_int32 value)
20
 
{
21
 
    if (value <= 0)
22
 
    {
23
 
        return -32;
24
 
    }
25
 
 
26
 
    le_uint8 bit = 0;
27
 
 
28
 
    if (value >= 1 << 16)
29
 
    {
30
 
        value >>= 16;
31
 
        bit += 16;
32
 
    }
33
 
 
34
 
    if (value >= 1 << 8)
35
 
    {
36
 
        value >>= 8;
37
 
        bit += 8;
38
 
    }
39
 
 
40
 
    if (value >= 1 << 4)
41
 
    {
42
 
        value >>= 4;
43
 
        bit += 4;
44
 
    }
45
 
 
46
 
    if (value >= 1 << 2)
47
 
    {
48
 
        value >>= 2;
49
 
        bit += 2;
50
 
    }
51
 
 
52
 
    if (value >= 1 << 1)
53
 
    {
54
 
        value >>= 1;
55
 
        bit += 1;
56
 
    }
57
 
 
58
 
    return bit;
59
 
}
60
 
 
61
 
Offset OpenTypeUtilities::getTagOffset(LETag tag, const TagAndOffsetRecord *records, le_int32 recordCount)
62
 
{
63
 
    le_uint8 bit = highBit(recordCount);
64
 
    le_int32 power = 1 << bit;
65
 
    le_int32 extra = recordCount - power;
66
 
    le_int32 probe = power;
67
 
    le_int32 index = 0;
68
 
 
69
 
    if (SWAPT(records[extra].tag) <= tag)
70
 
    {
71
 
        index = extra;
72
 
    }
73
 
 
74
 
    while (probe > (1 << 0))
75
 
    {
76
 
        probe >>= 1;
77
 
 
78
 
        if (SWAPT(records[index + probe].tag) <= tag)
79
 
        {
80
 
            index += probe;
81
 
        }
82
 
    }
83
 
 
84
 
    if (SWAPT(records[index].tag) == tag)
85
 
    {
86
 
        return SWAPW(records[index].offset);
87
 
    }
88
 
 
89
 
    return 0;
90
 
}
91
 
 
92
 
le_int32 OpenTypeUtilities::getGlyphRangeIndex(LEGlyphID glyphID, const GlyphRangeRecord *records, le_int32 recordCount)
93
 
{
94
 
    le_uint8 bit = highBit(recordCount);
95
 
    le_int32 power = 1 << bit;
96
 
    le_int32 extra = recordCount - power;
97
 
    le_int32 probe = power;
98
 
    le_int32 range = 0;
99
 
 
100
 
    if (SWAPW(records[extra].firstGlyph) <= glyphID)
101
 
    {
102
 
        range = extra;
103
 
    }
104
 
 
105
 
    while (probe > (1 << 0))
106
 
    {
107
 
        probe >>= 1;
108
 
 
109
 
        if (SWAPW(records[range + probe].firstGlyph) <= glyphID)
110
 
        {
111
 
            range += probe;
112
 
        }
113
 
    }
114
 
 
115
 
    if (SWAPW(records[range].firstGlyph) <= glyphID && SWAPW(records[range].lastGlyph) >= glyphID)
116
 
    {
117
 
        return range;
118
 
    }
119
 
 
120
 
    return -1;
121
 
}
122
 
 
123
 
le_int32 OpenTypeUtilities::search(le_uint32 value, const le_uint32 array[], le_int32 count)
124
 
{
125
 
    le_int32 power = 1 << highBit(count);
126
 
    le_int32 extra = count - power;
127
 
    le_int32 probe = power;
128
 
    le_int32 index = 0;
129
 
 
130
 
    if (value >= array[extra]) {
131
 
        index = extra;
132
 
    }
133
 
 
134
 
    while (probe > (1 << 0)) {
135
 
        probe >>= 1;
136
 
 
137
 
        if (value >= array[index + probe]) {
138
 
            index += probe;
139
 
        }
140
 
    }
141
 
 
142
 
    return index;
143
 
}
144
 
 
145
 
le_int32 OpenTypeUtilities::search(le_uint16 value, const le_uint16 array[], le_int32 count)
146
 
{
147
 
    le_int32 power = 1 << highBit(count);
148
 
    le_int32 extra = count - power;
149
 
    le_int32 probe = power;
150
 
    le_int32 index = 0;
151
 
 
152
 
    if (value >= array[extra]) {
153
 
        index = extra;
154
 
    }
155
 
 
156
 
    while (probe > (1 << 0)) {
157
 
        probe >>= 1;
158
 
 
159
 
        if (value >= array[index + probe]) {
160
 
            index += probe;
161
 
        }
162
 
    }
163
 
 
164
 
    return index;
165
 
}
166
 
 
167
 
//
168
 
// Straight insertion sort from Knuth vol. III, pg. 81
169
 
//
170
 
void OpenTypeUtilities::sort(le_uint16 *array, le_int32 count)
171
 
{
172
 
    for (le_int32 j = 1; j < count; j += 1) {
173
 
        le_int32 i;
174
 
        le_uint16 v = array[j];
175
 
 
176
 
        for (i = j - 1; i >= 0; i -= 1) {
177
 
            if (v >= array[i]) {
178
 
                break;
179
 
            }
180
 
 
181
 
            array[i + 1] = array[i];
182
 
        }
183
 
 
184
 
        array[i + 1] = v;
185
 
    }
186
 
}
187
 
 
188
 
 
189
 
 
190
 
U_NAMESPACE_END