Computing remainders (Was: Re: [kaffe] Re: Problem compiling 1.1.0 with GCC 3.3 on GNU/Linux PowerPC, and 1 test failed)

[Dalibor Topic]

Hi Tony,

--- Tony Wyatt <wyattaw@optushome.com.au> wrote:
> Hi Luca and Dalibor,
> 
> On 27/06/03, you wrote:
> 
> >   One person kindly contacted me off-list saying I should define 
> > LONG_MODULO_BROKEN; I hardcoded it in config.h and that fixed the issue. 
> > In my opinion we need a check at configure time; it's easy. If I have 
> > understood correctly that person told me that such a check existed in 
> > release 1.0.7 for the 68000, which has the same problem.
> 
> That was I.

thought so ;) since we had the conversation about divtest.java off list.
 
> The Motorola M68k series and (it would seem) the PowerPC series processors
> do not generate an exception, but silently generate the wrong answer. 

Actually, I think the answer may be permitted by the ISO C 89 standard. See 
http://www.lysator.liu.se/c/rat/c3.html#3-3-5 for the rationale why C89 allowed
some flexibility with respect to the result of the remainder operation.

It may be better to use div, ldiv (and lldiv from C99) to compute division and
remainders, since they have "well-specified semantics for signed integral
division and remainder operations". See
http://www.lysator.liu.se/c/rat/d10.html#4-10-6-2 . Those semantics seem to
match (except for divide-by-zero, and MIN_VALUE) the semantics of java for
signed integral division and remainder operations, see
http://java.sun.com/docs/books/jls/second_edition/html/expressions.doc.html#24956
for a reference. 

One still has to special-case the MIN_VALUE % -1 == 0 case, though.  Since for
example LONG_MIN / -1 => LONG_MAX + 1 => overflow, resulting in undefined
behaviour.

Apparently, C99 clarifies the semantics of the remainder operator, see
http://groups.google.de/groups?hl=de&lr=&ie=UTF-8&oe=UTF-8&threadm=dfPd4.2269%24Mp.11306%40newsfeed.slurp.net&rnum=1&prev=/groups%3Fq%3Dremainder%2BC%2Bstandard%2Bnegative%26hl%3Dde%26lr%3D%26ie%3DUTF-8%26oe%3DUTF-8%26selm%3DdfPd4.2269%2524Mp.11306%2540newsfeed.slurp.net%26rnum%3D1

> Now, Dalibor, what happened to that patch I sent you months ago for
> "configure"? You asked me to supply a similar patch for "configure.in"
> instead
> of "configure", and I think I did, but if not, shall I send it again?

I've "back-ported" your patch to configure.in, and checked it in. I think that
the patched test is causing the problems now, but I didn't notice it since on
ix86 the test fails with a floating point exception anyway. Here's the current
test:

#include <limits.h>
#define T long
#ifndef LONG_MIN
# define LONG_MIN ((((unsigned T)(~(T)0))>>1)+1)
#endif
T foo(T i, T j);
int main() { return foo(LONG_MIN, -1l) == 0; }
T foo(T i, T j) { return i % j; }

According to what I've said above, the test is broken anyway, since LONG_MIN %
-1 will always overflow, resulting in undefined behavior. It has to be special
cased. 

The other issue is % with negative operands, which is not well-defined by C89.
So I'd like to propose something along these lines for icode.h :

static __inline__ jint jint_remainder(jint a, jint b) {
  /* choice of JINT_DIV_T and JINT_DIV_FUNC depends on siye of jint */
  /* temporary variable of div_t or ldiv_t type */
  JINT_DIV_T tmp;
  /* call suitable div or ldiv function */ 
  tmp = JINT_DIV_FUNC(a, b);
  return tmp.rem;
} 

# define rem_int(t, f1, f2) \
  /* check for MIN_VALUE % -1 */ \
  (t)[0].v.tint = ((((f2)[0].v.tint) == -1) ? \
    /* if so, result is 0 */ \
    (0 : \
    /* else check if f2 is 0 */ \
      ((((f2)[0].v.tint) == 0) ? \
       /* if so, trap division through 0 */ \
       ((f1)[0].v.tint) % ((f2)[0].v.tint) : \
       /* else compute the remainder with java semantics for negative operands
*/ \ 
       jint_remainder(((f1)[0].v.tint), ((f2)[0].v.tint))))

Analogous implementations should be made for long remainder, and both int and
long division. As usual, I'd like to hear your comments.

cheers,
dalibor topic

__________________________________
Do you Yahoo!?
SBC Yahoo! DSL - Now only $29.95 per month!
http://sbc.yahoo.com