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-2004 - All Rights Reserved
29 *
30 */
31
32#include "LETypes.h"
33#include "LayoutTables.h"
34#include "LookupTables.h"
35#include "LESwaps.h"
36
37U_NAMESPACE_BEGIN
38
39/*
40    These are the rolled-up versions of the uniform binary search.
41    Someday, if we need more performance, we can un-roll them.
42
43    Note: I put these in the base class, so they only have to
44    be written once. Since the base class doesn't define the
45    segment table, these routines assume that it's right after
46    the binary search header.
47
48    Another way to do this is to put each of these routines in one
49    of the derived classes, and implement it in the others by casting
50    the "this" pointer to the type that has the implementation.
51*/
52const LookupSegment *BinarySearchLookupTable::lookupSegment(const LETableReference &base, const LookupSegment *segments, LEGlyphID glyph, LEErrorCode &success) const
53{
54
55    le_int16  unity = SWAPW(unitSize);
56    le_int16  probe = SWAPW(searchRange);
57    le_int16  extra = SWAPW(rangeShift);
58    TTGlyphID ttGlyph = (TTGlyphID) LE_GET_GLYPH(glyph);
59    LEReferenceTo<LookupSegment> entry(base, success, segments);
60    LEReferenceTo<LookupSegment> trial(entry, success, extra);
61
62    if(LE_FAILURE(success)) return NULL;
63
64    if (SWAPW(trial->lastGlyph) <= ttGlyph) {
65        entry = trial;
66    }
67
68    while (probe > unity && LE_SUCCESS(success)) {
69        probe >>= 1;
70        trial = entry; // copy
71        trial.addOffset(probe, success);
72
73        if (SWAPW(trial->lastGlyph) <= ttGlyph) {
74            entry = trial;
75        }
76    }
77
78    if (SWAPW(entry->firstGlyph) <= ttGlyph) {
79      return entry.getAlias();
80    }
81
82    return NULL;
83}
84
85const LookupSingle *BinarySearchLookupTable::lookupSingle(const LETableReference &base, const LookupSingle *entries, LEGlyphID glyph, LEErrorCode &success) const
86{
87    le_int16  unity = SWAPW(unitSize);
88    le_int16  probe = SWAPW(searchRange);
89    le_int16  extra = SWAPW(rangeShift);
90    TTGlyphID ttGlyph = (TTGlyphID) LE_GET_GLYPH(glyph);
91    LEReferenceTo<LookupSingle> entry(base, success, entries);
92    LEReferenceTo<LookupSingle> trial(entry, success, extra);
93
94    if (!LE_SUCCESS(success)) {
95        return NULL;
96    }
97
98    if (SWAPW(trial->glyph) <= ttGlyph) {
99        entry = trial;
100    }
101
102    while (probe > unity && LE_SUCCESS(success)) {
103        probe >>= 1;
104        trial = entry;
105        trial.addOffset(probe, success);
106
107        if (SWAPW(trial->glyph) <= ttGlyph) {
108            entry = trial;
109        }
110    }
111
112    if (SWAPW(entry->glyph) == ttGlyph) {
113      return entry.getAlias();
114    }
115
116    return NULL;
117}
118
119U_NAMESPACE_END
120