search

raphlinus / font-rs

Apache License 2.0
753 stars 49 forks source link

A rounding bug with glyph id search #32

Closed golddranks closed 5 years ago

golddranks commented 5 years ago

I'm getting a bug where the lookup_glyph_id function can't find a glyph even if it exists. Here's a "trace" of the binary search it performs:

code point dec: 36196 hex: 8d64 char: 赤
size: 4247, index: 2123, end value: 29650
size: 2123, index: 4246, end value: 65509
size: 1061, index: 3185, end value: 34851
size: 530, index: 3715, end value: 37587
size: 265, index: 3450, end value: 36118
size: 132, index: 3582, end value: 36921
size: 66, index: 3516, end value: 36557
size: 33, index: 3483, end value: 36362
size: 16, index: 3467, end value: 36290
size: 8, index: 3459, end value: 36229
size: 4, index: 3455, end value: 36209
size: 2, index: 3453, end value: 36203
size: 1, index: 3452, end value: 36199
Error: StringError("Glyph doesn\'t exist")

The actual range that includes the glyph is in index 3451, so it's off by one. It's still in the range when the size is 33: 3483-33 = 3450, but drops from the range the next step: 3467-16 = 3451 (this is non-inclusive, as the size printed here was the size of the last step).

We can see that the the correrct result is excluded from the range because of a rounding error: Rust rounds always towards zero so 33/2 becomes 16, which makes it here lose enough of it's "jumping power" for it not to reach the correct range.

It seems to me that the correct thing to do is to ensure that the result is always rounded up.

raphlinus commented 5 years ago

I think I see how to fix this properly. The logic is subtle. In any case, a good methodology for trying to fix this is to see whether you can replicate a test case with the existing font, then do cargo test before uploading a PR.