Skip to content

Prevent floating point shenanigans in loop termination (fixes #5012)#5013

Merged
jtanx merged 1 commit intofontforge:masterfrom
skef:bg5012
Jul 3, 2022
Merged

Prevent floating point shenanigans in loop termination (fixes #5012)#5013
jtanx merged 1 commit intofontforge:masterfrom
skef:bg5012

Conversation

@skef
Copy link
Copy Markdown
Contributor

@skef skef commented May 16, 2022

WRT #5012, this is from splineoverlap.c:

    if (( Within16RoundingErrors(t1s[0],m1->tstart) && Within16RoundingErrors(t1s[1],m1->tend)) ||
        ( Within16RoundingErrors(t2s[0],m2->tstart) && Within16RoundingErrors(t2s[1],m2->tend)) )
        /* It covers one of the monotonics entirely */;
    else if ( RealWithin(t1s[0],t1s[1],.01) )
return( false );        /* But otherwise, don't create a new tiny spline */

    /* Ok, if we've gotten this far we know that two of the end points are  */
    /*  on both splines.                                                    */
    t1s[2] = t2s[2] = -1;
    if ( !m1->s->knownlinear || !m2->s->knownlinear ) {
        if ( t1s[1]<t1s[0] ) {
            extended temp = t1s[1]; t1s[1] = t1s[0]; t1s[0] = temp;
            temp = t2s[1]; t2s[1] = t2s[0]; t2s[0] = temp;
        }
        diff = (t1s[1]-t1s[0])/16;
        for ( t=t1s[0]+diff; t<t1s[1]-diff/4; t += diff ) {
            BasePoint here, slope;
            here.x = ((m1->s->splines[0].a*t+m1->s->splines[0].b)*t+m1->s->splines[0].c)*t+m1->s->splines[0].d;
            here.y = ((m1->s->splines[1].a*t+m1->s->splines[1].b)*t+m1->s->splines[1].c)*t+m1->s->splines[1].d;
            if ( (slope.x = (3*m1->s->splines[0].a*t+2*m1->s->splines[0].b)*t+m1->s->splines[0].c)<0 )
                slope.x = -slope.x;
            if ( (slope.y = (3*m1->s->splines[1].a*t+2*m1->s->splines[1].b)*t+m1->s->splines[1].c)<0 )
                slope.y = -slope.y;
            if ( slope.y>slope.x ) {
                t2 = IterateSplineSolveFixup(&m2->s->splines[1],t2s[0],t2s[1],here.y);
                if ( t2==-1 || !RealWithin(here.x,((m2->s->splines[0].a*t2+m2->s->splines[0].b)*t2+m2->s->splines[0].c)*t2+m2->s->splines[0].d,.1))
return( false );
            } else {
                t2 = IterateSplineSolveFixup(&m2->s->splines[0],t2s[0],t2s[1],here.x);
                if ( t2==-1 || !RealWithin(here.y,((m2->s->splines[1].a*t2+m2->s->splines[1].b)*t2+m2->s->splines[1].c)*t2+m2->s->splines[1].d,.1))
return( false );
            }
        }
    }

The narrow problem is that the for loop isn't terminating because diff (around 1e-17) isn't large enough to change the value of t (around 1).

There's already that false-returning RealWithin(t1s[0],t1s[1],.01) check, which may be intended to avoid this sort of problem. That isn't having an effect because the first guard succeeds -- the t2s and m2 values are all .000005 (or close enough to that that Within16RoundingErrors() returns true.

This is all old GW code, most recently adjusted like this:

commit 21adfc22a566c9f6f39a070196dec4e24d20625d
Author: George Williams <pfaedit@users.sourceforge.net>
Date:   Sat Jan 22 03:19:44 2011 +0000

    tweak for greater precision.

diff --git a/fontforge/splineoverlap.c b/fontforge/splineoverlap.c
index 145a6ce1c..7e7bb0c6d 100644
--- a/fontforge/splineoverlap.c
+++ b/fontforge/splineoverlap.c
@@ -1526,7 +1526,7 @@ static int CoincidentIntersect(Monotonic *m1,Monotonic *m2,BasePoint *pts,
     extended t, t2, diff;
 
     if ( m1==m2 )
-return( false );               /* Can't be coincident. Adjacent */
+return( false );               /* Stupid question */
     /* Adjacent splines can double back on themselves */
     if ( m1->next==m2 || m1->prev==m2 ) {
        /* But normally they'll only intersect in one point, where they join */
@@ -1566,8 +1566,11 @@ return( false );
     if ( cnt!=2 )
 return( false );
 
-    if ( RealWithin(t1s[0],t1s[1],.01) )
-return( false );
+    if (( Within16RoundingErrors(t1s[0],m1->tstart) && Within16RoundingErrors(t1s[1],m1->tend)) ||
+       ( Within16RoundingErrors(t2s[0],m2->tstart) && Within16RoundingErrors(t2s[1],m2->tend)) )
+       /* It covers one of the monotonics entirely */;
+    else if ( RealWithin(t1s[0],t1s[1],.01) )
+return( false );       /* But otherwise, don't create a new tiny spline */

I'm confused about the guard succeeding only on the basis of t2s checks and then subsequently throwing out the t2s values (by setting them to -1), but it's not conclusively invalid to do so.

Still, we're fixing a hang here and I'm not sure it's worth digging into these larger questions to do it. So in this PR I'm just replacing the direct loop comparison with an int that goes from 1 to 16 and some calculations at the start of the loop.

Closes #5012

@jtanx jtanx merged commit a1af225 into fontforge:master Jul 3, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

FontForge hangs when changing the weight of some glyphs

2 participants