[tex-k] Metafont bug located

[Julian Gilbey]

On Mon, Jan 22, 2001 at 02:47:50PM +0000, Julian Gilbey wrote:
> Wow!  I got a MetaFont "This can't happen (m)" error.  Here's how I
> did it.
> [...]

And the easiest way to reproduce it is (using the plain.mf base):
  addto currentpicture contour (-2391.03369,0)--(2391.03369,0)--
  (2391.03369,0.0001)--(-2391.03369,0.0001)--cycle;

Here follows a detailed explanation of where the bug occurs and a
possible fix.

At the start of the make_spec routine, before subdivision and
autorounding, the cycle looks like this (node numbers may be
different, though):

node (p)            3079         3072         3065         3079
x_coord(p)    -156698784    156698784    156698784*  -156698784*
y_coord(p)             0            0            7*           7*
left_x(p)     -156698784*    52232928    156698784    -52232928*
left_y(p)              2*           0            5            7*
right_x(p)     -52232928    156698784     52232928*  -156698784*
right_y(p)             0            2            7*           5*
link(p)             3072         3065         3058         3079
left_type(p)           1            1            1            1
right_type(p)          1            1            1            1

quadrant_subdivide negates those values which are asterisked and
changes the type lines to become:

left_type(p)           4            1            2            3
right_type(p)          1            1            4            4

It does nothing else.  Then the autorounding begins, and xy_round
begins.  It notices that the third and first nodes (3065 and 3079) are
transition points for x coordinates, so it calculates the following
before and after values:

q         3065        3079
b    156698784  -156698784
a    156696576  -156696576

Then we transform the x coordinates.  But look what happens.  We start
working from node 3079 to node 3065.  alpha is calculated to be
  make_fraction(2*156696576,2*156698784) = make_fraction(2a,2b) =
    floor(268431673.5489+0.5) = 268431674
Then the x_coord of 3079 is found to be
  take_fraction(alpha, x_coord(3079) - b) + a =
    take_fraction(alpha, 0) + a = a = -156696576
The x_coord of 3072 is then calculated similarly to be:
  take_fraction(alpha, x_coord(3072) - b) + a =
    take_fraction(alpha, 2*156698784) + a =
    (2*156696576+1) - 156696576 = 156696577
Note the calculation:
  take_fraction(alpha, 2*156698784) =
    floor(268431674*313397568/2^28+0.5) = floor(313393152.5266+0.5)
shows that we have twice made errors of approximately 0.5 scaled units
in the same direction, which has led to the out-by-one error.

Now to finish the problem, the same calculations are performed for
nodes 3065 and 3058, leading to the following situation:

node               3072        3065
x_coord       156696577  -156696576
right_type            1           4

Thus, we have to negate_x for node 3065 when comparing it to node
3072, yielding (after transforming the coordinates of 3065 to the same
octant as 3072):

node               3072        3065
x_coord       156696577   156696576
right_type            1           -

But now we have our fatal error: the cubic from 3072 to 3065 has final
x_coord less than initial x_coord, so eventually the make_moves
procedure dies with a fatal error when it tries to process this curve.

So what could be done to fix this problem?  I have not analysed it
fully, but it seems likely that at worst there will be an off-by-one
error due to this behaviour.  An obvious fix would be to check during
the <Transform the $x$ coordinates 436> module that this problem is
not being introduced, or to do so shortly thereafter; it is not
obvious at first glance how best to do this.  This check will clearly
have to be performed on the corresponding $y$ coordinates module,
although I don't know whether it will need doing for the diagonal
autorounding (round_diag) procedure.

   Julian

-- 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

         Julian Gilbey, Dept of Maths, Queen Mary, Univ. of London
       Debian GNU/Linux Developer,  see http://people.debian.org/~jdg
  Donate free food to the world's hungry: see http://www.thehungersite.com/