On 14-07-04 03:59 PM, Alexei Podtelezhnikov wrote: > > On Fri, Jul 4, 2014 at 3:30 PM, Behdad Esfahbod <[email protected] > <mailto:[email protected]>> wrote: > > On 14-07-04 03:09 PM, Alexei Podtelezhnikov wrote: > > > > > > You force me to think, man. To avoid any overflow it is sufficient to > satisfy > > this inequality > > > > a + b < 2 * sqrt(X - c/2) > > > > where X is 2^31 - 1. Using Taylor series it can replaces with a > *stronger* > > inequality > > > > a + b < 2 * sqrt(X) - c / (2 * sqrt(X)) > > > > or > > > > a + b < 92681.9 - c / 92681.9 > > > > Now we get rid of impractical division > > > > a + b < 92681.9 - (c >> 16) + (c >> 18) > > > > where the right side got a bit smaller again as the denominator became > > 87381.3. We can finally turn the whole thing integer > > > > a + b < 92681 - (c >> 16) + ((c+ 235935) >> 18) > > > > Therefore, we do not need a special limit on c. The whole thing becomes > more > > permissive. > > You could write it with <= instead of <. No? > > How about the simpler: > > a + b <= 92681 - (c >> 16) > > This has the same number of operations as my previous patch, but more > permissive for all practical purposes though not *completely* covering the > previous case. > > I agree. The short version is kinda beautiful. It should not overflow by > itself like this > > (FT_ULong)a + (FT_ULong)b < 92681UL - ((FT_ULong)c >> 16)
Very good point. -- behdad http://behdad.org/ _______________________________________________ Freetype-devel mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/freetype-devel
