[HarfBuzz] TrueType spec bsearch algorithm?

[Behdad Esfahbod]

Thanks Jonathan and Eric,


On 11/05/10 15:18, Eric Mader wrote:

> 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 ;-)

Well, this is one part that always confused me.  In a normal binary search,
you need one addition and one divide-by-2, where the divide-by-2 is indeed
always implemented by shifting.  So I don't see the difference.


> 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.

Right!  This never occurred to me.  Cause, otherwise knowing the number of
iteration doesn't make the loop any faster.


> These days I don't think that's actually worth the trouble.

Right.  As I said, it was more about learning than actually wanting to
implement such stuff.


>> 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.

Thanks!  I always thought "if it's not in SearchRange, you end up with a
non-power-of-two anyway, so what is it improving."  Nice trick I've got to say.



behdad