[HarfBuzz] TrueType spec bsearch algorithm?

[Jonathan Kew]

On 5 Nov 2010, at 00:02, Behdad Esfahbod wrote:

> Hi Jonathan,
> 
> So, many places in the TrueType spec, there are these searchRange,
> entrySelector, and rangeShift values that seem to be there to facilitate a
> fast binary search algorithm.  I cannot quite get the intended algorithm
> though (not that I want to implement it, just want to learn).  I know you've
> used them Firefox, can you please explain or point me to the code?
> 
> Thanks,
> behdad

I don't recall that I've actually used those fields in implementing a search. I think they're a legacy of when this stuff was being coded in 68K assembler, and every instruction was crucial....

Anyhow, the idea (as I understand it) is that SearchRange gives the size of a range that can be efficiently binary-searched because the number of entries in the range is guaranteed to be a power of 2, so a precisely known number of right-shifts can be used to narrow the search. The value is premultiplied by the entry size so that it can be used directly in pointer arithmetic. And RangeShift represents the "remainder" of the table, as the number of entries may not actually be a power of two.

So you do an initial test to see whether the required value is too large to fall within the SearchRange (from the beginning of the table); if so, you adjust the starting position by RangeShift so that you're binary-searching a range of the same size, but shifted to the end of the table. If the target value exists, it must be within this section.

Then EntrySelector is simply a count of the number iterations you'll need to do to search this range, handy as a loop counter.

(I've seen fonts "in the wild" where these fields are not set correctly, at least in some tables, so I'm doubtful whether any current implementations actually rely on them. To me it seems simplest - and perfectly adequate - to ignore them and do a straightforward binary search of the whole table; I don't think the tricks of using premultiplied counter values to save an operation during the address arithmetic are worthwhile these days.)

JK