1ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru/* 2ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * 3ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * (C) Copyright IBM Corp. 1998-2004 - All Rights Reserved 4ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * 5ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru */ 6ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 7ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#include "LETypes.h" 8ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#include "LayoutTables.h" 9ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#include "LookupTables.h" 10ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#include "LESwaps.h" 11ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 12ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste QueruU_NAMESPACE_BEGIN 13ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 14ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru/* 15ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru These are the rolled-up versions of the uniform binary search. 16ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru Someday, if we need more performance, we can un-roll them. 17ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 18ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru Note: I put these in the base class, so they only have to 19ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru be written once. Since the base class doesn't define the 20ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru segment table, these routines assume that it's right after 21ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru the binary search header. 22ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 23ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru Another way to do this is to put each of these routines in one 24ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru of the derived classes, and implement it in the others by casting 25ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru the "this" pointer to the type that has the implementation. 26ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru*/ 27ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queruconst LookupSegment *BinarySearchLookupTable::lookupSegment(const LookupSegment *segments, LEGlyphID glyph) const 28ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru{ 29ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru le_int16 unity = SWAPW(unitSize); 30ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru le_int16 probe = SWAPW(searchRange); 31ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru le_int16 extra = SWAPW(rangeShift); 32ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru TTGlyphID ttGlyph = (TTGlyphID) LE_GET_GLYPH(glyph); 33ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru const LookupSegment *entry = segments; 34ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru const LookupSegment *trial = (const LookupSegment *) ((char *) entry + extra); 35ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 36ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if (SWAPW(trial->lastGlyph) <= ttGlyph) { 37ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru entry = trial; 38ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 39ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 40ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru while (probe > unity) { 41ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru probe >>= 1; 42ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru trial = (const LookupSegment *) ((char *) entry + probe); 43ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 44ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if (SWAPW(trial->lastGlyph) <= ttGlyph) { 45ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru entry = trial; 46ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 47ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 48ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 49ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if (SWAPW(entry->firstGlyph) <= ttGlyph) { 50ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return entry; 51ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 52ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 53ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return NULL; 54ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 55ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 56ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queruconst LookupSingle *BinarySearchLookupTable::lookupSingle(const LookupSingle *entries, LEGlyphID glyph) const 57ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru{ 58ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru le_int16 unity = SWAPW(unitSize); 59ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru le_int16 probe = SWAPW(searchRange); 60ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru le_int16 extra = SWAPW(rangeShift); 61ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru TTGlyphID ttGlyph = (TTGlyphID) LE_GET_GLYPH(glyph); 62ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru const LookupSingle *entry = entries; 63ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru const LookupSingle *trial = (const LookupSingle *) ((char *) entry + extra); 64ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 65ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if (SWAPW(trial->glyph) <= ttGlyph) { 66ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru entry = trial; 67ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 68ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 69ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru while (probe > unity) { 70ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru probe >>= 1; 71ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru trial = (const LookupSingle *) ((char *) entry + probe); 72ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 73ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if (SWAPW(trial->glyph) <= ttGlyph) { 74ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru entry = trial; 75ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 76ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 77ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 78ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if (SWAPW(entry->glyph) == ttGlyph) { 79ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return entry; 80ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 81ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 82ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return NULL; 83ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 84ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 85ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste QueruU_NAMESPACE_END 86