[ft-devel] [patch] use binary search for cmap format 12

[Chia-I Wu]

Hi,

This patch makes freetype use binary search to map charcode to glyph
index for truetype cmap format 12.

Testing with fonts from
http://freedesktop.org/wiki/Software_2fCJKUnifonts gives:

ukai.ttf
-------------
(original)
Get_Char_Index                 : 61.833 us/op
Charmap iteration              : 1605377.533 us/op

(binary)
Get_Char_Index                 : 0.444 us/op
Charmap iteration              : 2807.427 us/op

uming.ttf
-------------
(original)
Get_Char_Index                 : 63.230 us/op
Charmap iteration              : 1643916.969 us/op

(binary)
Get_Char_Index                 : 0.440 us/op
Charmap iteration              : 2749.562 us/op

Please test. If there is no problem nor objections, I will commit it in
2 or 3 days.

I am also looking into cmap format 4, to make freetype consider
overlapped segments sorted, provided their start/end points are sorted.
This could help a lot for bkai00mp.ttf:

bkai00mp.ttf
-------------
(original)
Get_Char_Index                 : 32.298 us/op
Charmap iteration              : 460667.588 us/op

(sorted)
Get_Char_Index                 : 0.407 us/op
Charmap iteration              : 1304.434 us/op

But there is one small performance problem with segment having offset
0xFFFF.  Currently, such segment is interpreted as empty segment.  Can
it be interpreted in other ways, like map every charcode to 0 or just
treat it as if the offset is 0?  The latter makes sense if it is always
used like this:

Segment=33 unicode-start=ffff end=ffff range-offset=65535 delta=1 End

-- 
Regards,
olv

cmap.12.patch
Description: Text document