Re: [Devel] pcf_cmap_char_next()

[David Turner]

Hello Owen,

Owen Taylor a écrit :
> 
> There is a bug in pcf_cmap_char_next() where it will
> frequently give the wrong result.
> 
> Example; charmap with three elements, searching for
>  a value of 1.
> 
>  encodings[0] = 0
>  encodings[1] = 31
>  encodings[2] = 33
> 
> On exit of the main loop, min = 1, so the return value
> is *charcode = encodings[2] or 33.
> 
> The attached patch seems to work for me. However,
> experience is that I never have any luck patching
> up a non-working bsearch. (I just have to get it
> right the first time.)
>

Thanks for spotting the bug. I've fixed it by simply
getting rid of the "++" in the last comparison. I don't
know if that can help you, but the value of "min" when
the lookup is exited with no match (i.e. when "min==max")
always corresponds to the array "slot" above the lookup
key.. 

However, as you rightly say, bsearch algorithms are always
slightly subtle to implement. It's like implementing quicksort
from scratch and having to decide between "<" and "<=" as the
comparison operator, that can be a real brainteaser :-)

By the way, I have also checked "src/psaux/t1cmap.c" which
uses a similar algorithm to implement Unicode charmaps;
fortunately, it didn't have the bug.


Thanks,

- David Turner
- The FreeType Project  (www.freetype.org)