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