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
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
54
55Offset 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
95le_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
129le_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
151le_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//
176void 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
194U_NAMESPACE_END
195
196#if LE_ASSERT_BAD_FONT
197#include <stdio.h>
198
199static 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
208U_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