1/*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
3 *
4 * This code is free software; you can redistribute it and/or modify it
5 * under the terms of the GNU General Public License version 2 only, as
6 * published by the Free Software Foundation.  Oracle designates this
7 * particular file as subject to the "Classpath" exception as provided
8 * by Oracle in the LICENSE file that accompanied this code.
9 *
10 * This code is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
13 * version 2 for more details (a copy is included in the LICENSE file that
14 * accompanied this code).
15 *
16 * You should have received a copy of the GNU General Public License version
17 * 2 along with this work; if not, write to the Free Software Foundation,
18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 *
20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 * or visit www.oracle.com if you need additional information or have any
22 * questions.
23 *
24 */
25
26/*
27 *
28 * (C) Copyright IBM Corp. 1998-2010 - All Rights Reserved
29 *
30 */
31
32#include "LETypes.h"
33#include "OpenTypeTables.h"
34#include "OpenTypeUtilities.h"
35#include "LESwaps.h"
36
37U_NAMESPACE_BEGIN
38
39//
40// Finds the high bit by binary searching
41// through the bits in n.
42//
43le_int8 OpenTypeUtilities::highBit(le_int32 value)
44{
45    if (value <= 0) {
46        return -32;
47    }
48
49    le_uint8 bit = 0;
50
51    if (value >= 1 << 16) {
52        value >>= 16;
53        bit += 16;
54    }
55
56    if (value >= 1 << 8) {
57        value >>= 8;
58        bit += 8;
59    }
60
61    if (value >= 1 << 4) {
62        value >>= 4;
63        bit += 4;
64    }
65
66    if (value >= 1 << 2) {
67        value >>= 2;
68        bit += 2;
69    }
70
71    if (value >= 1 << 1) {
72        value >>= 1;
73        bit += 1;
74    }
75
76    return bit;
77}
78
79
80Offset OpenTypeUtilities::getTagOffset(LETag tag, const LEReferenceToArrayOf<TagAndOffsetRecord> &records, LEErrorCode &success)
81{
82  if(LE_FAILURE(success)) return 0;
83  const TagAndOffsetRecord *r0 = (const TagAndOffsetRecord*)records.getAlias();
84
85  le_uint32 recordCount = records.getCount();
86  le_uint8 bit = highBit(recordCount);
87  le_int32 power = 1 << bit;
88  le_int32 extra = recordCount - power;
89  le_int32 probe = power;
90  le_int32 index = 0;
91
92  {
93    const ATag &aTag = (r0+extra)->tag;
94    if (SWAPT(aTag) <= tag) {
95      index = extra;
96    }
97  }
98
99  while (probe > (1 << 0)) {
100    probe >>= 1;
101
102    {
103      const ATag &aTag = (r0+index+probe)->tag;
104      if (SWAPT(aTag) <= tag) {
105        index += probe;
106      }
107    }
108  }
109
110  {
111    const ATag &aTag = (r0+index)->tag;
112    if (SWAPT(aTag) == tag) {
113      return SWAPW((r0+index)->offset);
114    }
115  }
116
117  return 0;
118}
119
120le_int32 OpenTypeUtilities::getGlyphRangeIndex(TTGlyphID glyphID, const LEReferenceToArrayOf<GlyphRangeRecord> &records, LEErrorCode &success)
121{
122  if(LE_FAILURE(success)) return -1;
123
124    le_uint32 recordCount = records.getCount();
125    le_uint8 bit = highBit(recordCount);
126    le_int32 power = 1 << bit;
127    le_int32 extra = recordCount - power;
128    le_int32 probe = power;
129    le_int32 range = 0;
130
131    if (recordCount == 0) {
132      return -1;
133    }
134
135    if (SWAPW(records(extra,success).firstGlyph) <= glyphID) {
136        range = extra;
137    }
138
139    while (probe > (1 << 0) && LE_SUCCESS(success)) {
140        probe >>= 1;
141
142        if (SWAPW(records(range + probe,success).firstGlyph) <= glyphID) {
143            range += probe;
144        }
145    }
146
147    if (SWAPW(records(range,success).firstGlyph) <= glyphID && SWAPW(records(range,success).lastGlyph) >= glyphID) {
148        return range;
149    }
150
151    return -1;
152}
153
154le_int32 OpenTypeUtilities::search(le_uint32 value, const le_uint32 array[], le_int32 count)
155{
156    le_int32 power = 1 << highBit(count);
157    le_int32 extra = count - power;
158    le_int32 probe = power;
159    le_int32 index = 0;
160
161    if (value >= array[extra]) {
162        index = extra;
163    }
164
165    while (probe > (1 << 0)) {
166        probe >>= 1;
167
168        if (value >= array[index + probe]) {
169            index += probe;
170        }
171    }
172
173    return index;
174}
175
176le_int32 OpenTypeUtilities::search(le_uint16 value, const le_uint16 array[], le_int32 count)
177{
178    le_int32 power = 1 << highBit(count);
179    le_int32 extra = count - power;
180    le_int32 probe = power;
181    le_int32 index = 0;
182
183    if (value >= array[extra]) {
184        index = extra;
185    }
186
187    while (probe > (1 << 0)) {
188        probe >>= 1;
189
190        if (value >= array[index + probe]) {
191            index += probe;
192        }
193    }
194
195    return index;
196}
197
198//
199// Straight insertion sort from Knuth vol. III, pg. 81
200//
201void OpenTypeUtilities::sort(le_uint16 *array, le_int32 count)
202{
203    for (le_int32 j = 1; j < count; j += 1) {
204        le_int32 i;
205        le_uint16 v = array[j];
206
207        for (i = j - 1; i >= 0; i -= 1) {
208            if (v >= array[i]) {
209                break;
210            }
211
212            array[i + 1] = array[i];
213        }
214
215        array[i + 1] = v;
216    }
217}
218
219U_NAMESPACE_END
220
221#if LE_ASSERT_BAD_FONT
222#include <stdio.h>
223
224static const char *letagToStr(LETag tag, char *str) {
225  str[0]= 0xFF & (tag>>24);
226  str[1]= 0xFF & (tag>>16);
227  str[2]= 0xFF & (tag>>8);
228  str[3]= 0xFF & (tag>>0);
229  str[4]= 0;
230  return str;
231}
232
233U_CAPI void U_EXPORT2 _debug_LETableReference(const char *f, int l, const char *msg, const LETableReference *what, const void *ptr, size_t len) {
234  char tagbuf[5];
235
236  fprintf(stderr, "%s:%d: LETableReference@0x%p: ", f, l, what);
237  fprintf(stderr, msg, ptr, len);
238  fprintf(stderr, "\n");
239
240  for(int depth=0;depth<10&&(what!=NULL);depth++) {
241    for(int i=0;i<depth;i++) {
242      fprintf(stderr, " "); // indent
243    }
244    if(!what->isValid()) {
245      fprintf(stderr, "(invalid)");
246    }
247    fprintf(stderr, "@%p: tag (%s) font (0x%p), [0x%p+0x%lx]\n", what, letagToStr(what->getTag(), tagbuf), what->getFont(),
248            what->getAlias(), what->getLength());
249
250    what = what->getParent();
251  }
252}
253#endif
254