[tex-k] Metafont bug located
Julian Gilbey
J.D.Gilbey@qmw.ac.uk
Fri, 26 Jan 2001 01:35:41 +0000
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/