1ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru/* 2ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * 359d709d503bab6e2b61931737e662dd293b40578ccornelius * (C) Copyright IBM Corp. 1998-2013 - 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*/ 2759d709d503bab6e2b61931737e662dd293b40578ccorneliusconst LookupSegment *BinarySearchLookupTable::lookupSegment(const LETableReference &base, const LookupSegment *segments, LEGlyphID glyph, LEErrorCode &success) const 28ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru{ 2959d709d503bab6e2b61931737e662dd293b40578ccornelius 30ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru le_int16 unity = SWAPW(unitSize); 31ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru le_int16 probe = SWAPW(searchRange); 32ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru le_int16 extra = SWAPW(rangeShift); 33ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru TTGlyphID ttGlyph = (TTGlyphID) LE_GET_GLYPH(glyph); 3459d709d503bab6e2b61931737e662dd293b40578ccornelius LEReferenceTo<LookupSegment> entry(base, success, segments); 3559d709d503bab6e2b61931737e662dd293b40578ccornelius LEReferenceTo<LookupSegment> trial(entry, success, extra); 3659d709d503bab6e2b61931737e662dd293b40578ccornelius 3759d709d503bab6e2b61931737e662dd293b40578ccornelius if(LE_FAILURE(success)) return NULL; 38ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 39ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if (SWAPW(trial->lastGlyph) <= ttGlyph) { 40ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru entry = trial; 41ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 42ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 4359d709d503bab6e2b61931737e662dd293b40578ccornelius while (probe > unity && LE_SUCCESS(success)) { 44ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru probe >>= 1; 4559d709d503bab6e2b61931737e662dd293b40578ccornelius trial = entry; // copy 4659d709d503bab6e2b61931737e662dd293b40578ccornelius trial.addOffset(probe, success); 47ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 48ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if (SWAPW(trial->lastGlyph) <= ttGlyph) { 49ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru entry = trial; 50ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 51ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 52ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 53ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if (SWAPW(entry->firstGlyph) <= ttGlyph) { 5459d709d503bab6e2b61931737e662dd293b40578ccornelius return entry.getAlias(); 55ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 56ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 57ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return NULL; 58ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 59ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 6059d709d503bab6e2b61931737e662dd293b40578ccorneliusconst LookupSingle *BinarySearchLookupTable::lookupSingle(const LETableReference &base, const LookupSingle *entries, LEGlyphID glyph, LEErrorCode &success) const 61ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru{ 62ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru le_int16 unity = SWAPW(unitSize); 63ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru le_int16 probe = SWAPW(searchRange); 64ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru le_int16 extra = SWAPW(rangeShift); 65ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru TTGlyphID ttGlyph = (TTGlyphID) LE_GET_GLYPH(glyph); 6659d709d503bab6e2b61931737e662dd293b40578ccornelius LEReferenceTo<LookupSingle> entry(base, success, entries); 6759d709d503bab6e2b61931737e662dd293b40578ccornelius LEReferenceTo<LookupSingle> trial(entry, success, extra); 68ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 69ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if (SWAPW(trial->glyph) <= ttGlyph) { 70ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru entry = trial; 71ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 72ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 7359d709d503bab6e2b61931737e662dd293b40578ccornelius while (probe > unity && LE_SUCCESS(success)) { 74ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru probe >>= 1; 7559d709d503bab6e2b61931737e662dd293b40578ccornelius trial = entry; 7659d709d503bab6e2b61931737e662dd293b40578ccornelius trial.addOffset(probe, success); 77ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 78ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if (SWAPW(trial->glyph) <= ttGlyph) { 79ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru entry = trial; 80ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 81ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 82ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 83ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if (SWAPW(entry->glyph) == ttGlyph) { 8459d709d503bab6e2b61931737e662dd293b40578ccornelius return entry.getAlias(); 85ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 86ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 87ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return NULL; 88ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 89ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 90ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste QueruU_NAMESPACE_END 91