[HarfBuzz] TrueType spec bsearch algorithm?

[Eric Mader]

I was at Apple when the binary search header was adopted for TrueType. 
(circa 1989)Jonathan is correct, this was adopted so that the search 
could be as fast as possible in 68K assembler.

(There are many data structures in TrueType that were designed to be 
efficiently implemented in 68K assembler. Some were actually designed 
based on how the C compiler we were using at the time generated code.)

It's designed to always search a number of items that is a power of 2 so 
that it can use a shift rather than a divide to compute the new search 
range. (a divide was quite expensive on a 68K ;-)

I've attached some Java code I wrote a few years ago to test the 
performance of this algorithm in Java. It should give you a basic idea 
of how it's meant to work.

The "unrolled" version of the search doesn't use a loop. The idea was 
that eliminating the loop would make the search as fast as possible. 
These days I don't think that's actually worth the trouble.

Regards,
Eric Mader

On 11/5/10 6:34 AM, Jonathan Kew wrote:
> 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
>
> _______________________________________________
> HarfBuzz mailing list
> HarfBuzz at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/harfbuzz
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: BinarySearch.java
Type: text/x-java
Size: 3274 bytes
Desc: not available
URL: <http://lists.freedesktop.org/archives/harfbuzz/attachments/20101105/ae5933d5/attachment.java>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: LinearSearch.java
Type: text/x-java
Size: 561 bytes
Desc: not available
URL: <http://lists.freedesktop.org/archives/harfbuzz/attachments/20101105/ae5933d5/attachment-0001.java>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: RolledSearch.java
Type: text/x-java
Size: 650 bytes
Desc: not available
URL: <http://lists.freedesktop.org/archives/harfbuzz/attachments/20101105/ae5933d5/attachment-0002.java>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Searcher.java
Type: text/x-java
Size: 947 bytes
Desc: not available
URL: <http://lists.freedesktop.org/archives/harfbuzz/attachments/20101105/ae5933d5/attachment-0003.java>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: UnrolledSearch.java
Type: text/x-java
Size: 2016 bytes
Desc: not available
URL: <http://lists.freedesktop.org/archives/harfbuzz/attachments/20101105/ae5933d5/attachment-0004.java>