Bug 689794

Summary: gs gets /rangecheck in --initgraphics-- when compiled with -ffast-math
Product: Ghostscript Reporter: William Bader <williambader>
Component: GeneralAssignee: Henry Stiles <henry.stiles>
Status: RESOLVED FIXED    
Severity: normal CC: alex
Priority: P4    
Version: 8.62   
Hardware: PC   
OS: Linux   
Customer: Word Size: ---
Bug Depends on:    
Bug Blocks: 688581    
Attachments: gsinitbug.pat
gsinitbug.pdf
gsinitbug2.pat
makegs.sh
gsmisc-orig.s
gsmisc-fast.s
patch

Description William Bader 2008-04-16 20:20:45 UTC
gs gets /rangecheck in initgraphics with /Orientation != 0 when compiled with
-ffast-math using gcc version 4.1.2 20070925 (Red Hat 4.1.2-33)
gcc 4.1.2 is now too smart for the work-around for bug 687420.
As someone who did numerical programming on fortran almost 30 years ago, I would
never check real numbers for equality, especially after the values have gone
through a number of arithmetic operations.  gsmisc.c has some tests for floor(x)
== y and they need to be recoded as fabs(floor(x)-y) < eps.
Comment 1 William Bader 2008-04-16 20:26:56 UTC
Created attachment 3943 [details]
gsinitbug.pat

This patch fixes the problem on my system.
I replace
  if (floor(quot) == quot) ...
with
  #define is_integer(x) (fabs(floor((x) + 0.5) - (x)) < 1.0e-15)
  if (is_integer(quot)) ...
Maybe it would be safer to use <= instead of < for systems with limited ranges
for doubles.
I used the older fabs() and floor() instead of the newer round(), nearbyint()
or rint() to avoid adding more library dependencies.  gs already requires
fabs() and floor().
Comment 2 William Bader 2008-04-16 20:30:00 UTC
Created attachment 3944 [details]
gsinitbug.pdf

This PDF file demonstrates the problem.  Without the patch, under Fedora 8 and
gcc version 4.1.2 20070925 (Red Hat 4.1.2-33), gs8.62 fails with the message
$ gs862orig gsinitbug.pdf 
GPL Ghostscript 8.62 (2008-02-29)
Copyright (C) 2008 Artifex Software, Inc.  All rights reserved.
This software comes with NO WARRANTY: see the file PUBLIC for details.
Processing pages 1 through 1.
Page 1
Error: /rangecheck in --initgraphics--
Operand stack:
   --nostringval--   --dict:7/16(L)--	--dict:5/5(L)--   --nostringval--  
--dict:46/46(ro)(L)--	--dict:5/5(L)--   --dict:1/10(L)--  
--dict:47/56(ro)(L)--
Execution stack:
   %interp_exit   .runexec2   --nostringval--	--nostringval--  
--nostringval--   2   %stopped_push   --nostringval--	--nostringval--  
--nostringval--   false   1   %stopped_push   1873   1	 3   %oparray_pop  
1872   1   3   %oparray_pop   1856   1	 3   %oparray_pop   --nostringval--  
--nostringval--   2   1   1   --nostringval--	%for_pos_int_continue  
--nostringval--   1841	 3   7	 %oparray_pop	1843   8   7   %oparray_pop  
--nostringval--   1767	 8   7	 %oparray_pop	--nostringval--
Dictionary stack:
   --dict:1144/1684(ro)(G)--   --dict:1/20(G)--   --dict:75/200(L)--  
--dict:75/200(L)--   --dict:108/127(ro)(G)--   --dict:275/300(ro)(G)--	
--dict:21/25(L)--
Current allocation mode is local
Last OS error: 2
GPL Ghostscript 8.62: Unrecoverable error, exit code 1
Comment 3 Ray Johnston 2008-04-17 10:43:52 UTC
Assigning to "Mr. Precision" (one of our math experts)
Comment 4 William Bader 2008-04-18 13:55:32 UTC
Created attachment 3949 [details]
gsinitbug2.pat

Change is_integer to use <= eps instead of < eps in case eps becomes 0 on a
machine with limited real numbers.
Change fmod(quot, 4.0) to fmod(floor(quot+0.5), 4.0) because is_integer allows
quot to be slightly less than an integer.
Comment 5 Henry Stiles 2008-04-18 14:37:06 UTC
> As someone who did numerical programming on fortran almost 30 years ago, I would
> never check real numbers for equality, especially after the values have gone
> through a number of arithmetic operations. 

The difficulty with this approach is that equality is no longer transitive.

Has anyone looked to see if we are actually benefiting from this optimization on
modern systems.  This optimization is probably 20 years old.
Comment 6 William Bader 2008-04-18 16:50:24 UTC
Does it matter if it isn't transitive?
Isn't the worst that can happen is that rotation by an almost multiple of 90
followed by the reverse rotation by an almost multiple of 90 might now do one
exact and the other by the more general case instead of doing both by the more
general case?  Any small rotation by an almost multiple of 90 can cause the
rangecheck, so in the cases where it makes a difference, the result would
probably be a rangecheck, and even if gs didn't get a rangecheck, the trig
functions would probably not end up canceling exactly, so the result might still
be a very very small rotation.
My guess with the optimization is that trig functions are usually implemented
based on radians as series or tables, and if the function implementation itself
is an approximation and then if the argument to the function is an approximation
of a multiple of pi/2, getting multiples of 90 to return exact values could be
tricky, and very small values can cause problems.
Comment 7 William Bader 2008-04-19 14:29:19 UTC
Is transitivity the correct word?
Transitivity means A=B and B=C implies A=C, which involves three values.
Changing a condition F(x) from floor(x)==x to abs(floor(x+0.5)-x)<=eps affects a
function of only one variable, so transitivity is not relevant.
Changing a condition F(x,y) from floor(x)==y to abs(floor(x+0.5)-y)<=eps would
be a different matter.

My guess is that the original code was not for performance optimization but to
prevent small rounding errors from creating rotation matrices that cause
problems inverting.

Changing the condition causes differences only on rotations very near a multiple
of 90 like 89.9999999999999.  Would this ever be an issue except in test
patterns?  Printers can place at most on the order of 1000 dpi, so 6 or 7 digits
should be enough to position dots on the length of a page.  If two rotations
differ by 1e-15 degrees, how large a sheet of paper and how small dots would you
need before a dot is shifted to another position?
Comment 8 Henry Stiles 2008-04-20 20:49:30 UTC
I was thinking of the floor return value making a new variable and then the
equality is no longer an equivalence relation because it is not transitive.  In
any event, I think if we do anything at all we should emulate Adobe.  The trig
functions implement general purpose language operators in the postscript
language amongst other things so the issues are not limited to rotations and
page positioning.

There is a case to do nothing at all.  We release gs with a set of optimization
flags that are tested.  -ffast-math is not one of the tested flags.  Have you
added this flag or did the change originate with the distribution?

Maybe Leonardo (bug assignee) has a stronger opinion about making a modification
here, I don't see a strong case for changing the code.

The generated assembly code for the -ffast-math case vs. without might help us
make a better decision.  Thanks for looking into this.
Comment 9 William Bader 2008-04-21 03:01:20 UTC
Created attachment 3953 [details]
makegs.sh

top level of my personal build script
Comment 10 William Bader 2008-04-21 03:20:16 UTC
I build gs myself with a script that adds -O3 -ffast-math.
gs runs OK if I build without -ffast-math.
The gs 8.61 binary provided by Fedora 8 runs OK.
Comment 11 William Bader 2008-04-21 03:22:57 UTC
Created attachment 3954 [details]
gsmisc-orig.s

Assembly code without -ffast-math
I have 32-bit Fedora 8 on a Core2Duo.
gcc -O -pipe -Wall -Wpointer-arith -Wstrict-prototypes -Wwrite-strings \
	-DHAVE_MKSTEMP=1 -DOVERSAMPLE=0 -O3 -fomit-frame-pointer \
	-DFAX_INLINE=1 -I../obj -I. -S gsmisc.c
mv gsmisc.s gsmisc-orig.s
Comment 12 William Bader 2008-04-21 03:28:37 UTC
Created attachment 3955 [details]
gsmisc-fast.s

Assembly code with -fast-math.
uname -a shows
Linux laptop30 2.6.24.4-64.fc8 #1 SMP Sat Mar 29 09:54:46 EDT 2008 i686 i686
i386 GNU/Linux
gcc -v shows
Target: i386-redhat-linux
gcc version 4.1.2 20070925 (Red Hat 4.1.2-33)

gcc -O -pipe -Wall -Wpointer-arith -Wstrict-prototypes -Wwrite-strings \
	-DHAVE_MKSTEMP=1 -DOVERSAMPLE=0 -O3 -fomit-frame-pointer -ffast-math \
	-DFAX_INLINE=1 -I../obj -I. -S gsmisc.c
mv gsmisc.s gsmisc-fast.s
Comment 13 Alex Cherepanov 2010-12-12 16:17:23 UTC
Created attachment 7028 [details]
patch

The problem is reproduced on GCC 4.1.2, Linux i686.

This patch makes const_90_degrees an external variable (instead of static one)
to stop smart optimizers from converting angle/const_90_degrees into
angle*(1/const_90_degrees).
Comment 14 Alex Cherepanov 2010-12-12 16:21:22 UTC
The patch from the comment #13 has been committed as a rev. 11949.
Regression testing shows no differences.