SYSTEM_DIV(MIN(LONGINT), n) error

[Oleg-N-Cher]

The division function was implemented with errors:

LONGINT SYSTEM_DIV(LONGINT x, LONGINT y)
{
  if (x == 0) return 0;
  if (x >= 0)
    if (y >= 0) {return x/y;}
    else        {return -((x-y-1)/(-y));}
  else
    if (y >= 0) {return -((y-x-1)/y);}
    else        {return (-x)/(-y);}
}

Under the condition ( (x < 0) # (y < 0) ) & ( ABS(x) > MAX(LONGINT) - ABS(y) ) there will be an overflow despite the valid input parameters for division. According to the C standard, the overflow of signed integers is an undefined behavior, which does not allow predicting the behavior of the program for the general case - an emergency stop is also possible. If we use the -fwrapv compiler flag in GCC and CLang, the overflow will be performed according to machine calculations in the two’s complement. But even then the result in many cases will be incorrect. Also, because of the two’s complement, the incorrect equality MIN(LONGINT) DIV (-1) = MIN(LONGINT) will be executed. CLang can generate a crash for such a division, despite the flag -fwrap, which can be considered an advantage for diagnostics.

CPfront has not problems with overflow:

INTEGER SYSTEM_DIV(INTEGER x, INTEGER y)
{
   if (y > 0) {
      if (x < 0) return ~(~x / y);
      else return x / y;
   } else if (y < 0) {
      if (x > 0) return ~((x - 1) / -y);
      else return -x / -y;
   } else {
      __HALT(-5);
   }
}

Another advantage of this way is that it explicitly checks for division by 0. In C it is impossible to rely on the fact that when dividing by 0 there will be an emergency stop in the general case, because this is also undefined behavior. However, there is also a problem with dividing the minimum value by -1 in the Component Pascal solution, and tricks with bitwise negation are rigidly tied to the two’s complement.

This problem was found by ComDiv. Thanks him for the report. His own solution for Oberon-07 looks like this:

#define O7_INT_MAX 0x7fffffff
typedef char bool;

static inline bool o7_int_inited(int i) {
    return -O7_INT_MAX <= i;
}

#if defined(O7_CHECK_UNDEFINED)
    enum { O7_UNDEF = O7_CHECK_UNDEFINED };
#else
    enum { O7_UNDEF = 1 };
#endif

static inline int o7_int(int i) {
    if (O7_UNDEF) {
        assert(o7_int_inited(i));
    }
    return i;
}

#if defined(O7_CHECK_NATURAL_DIVISOR)
    enum { O7_NATURAL_DIVISOR = O7_CHECK_NATURAL_DIVISOR };
#else
    enum { O7_NATURAL_DIVISOR = 1 };
#endif

#if defined(O7_CHECK_OVERFLOW)
    enum { O7_OVERFLOW = O7_CHECK_OVERFLOW };
#else
    enum { O7_OVERFLOW = 1 };
#endif

#if defined(O7_CHECK_DIV_BY_ZERO)
    enum { O7_DIV_ZERO = O7_CHECK_DIV_BY_ZERO };
#else
    enum { O7_DIV_ZERO = 0 };
#endif

static inline int o7_divisor(int d) {
    if (O7_NATURAL_DIVISOR) {
        assert(0 < d);
    } else {
        if (O7_OVERFLOW && O7_DIV_ZERO) {
            assert(d != 0);
        }
        d = o7_int(d);
    }
    return d;
}

static inline int o7_div(int n, int d) {
    int r;
    if (0 <= n) {
        r = n / o7_divisor(d);
    } else {
        r = -1 - (-1 - o7_int(n)) / o7_divisor(d);
    }
    return  r;
}

Josef, I would like to hear your opinion how would you prefer to fix this issue?

[jtempl]

I think the problem is caused by the behavior of most C compilers to treat overflow in a constant expression (compile-time) differently from overflow during run-time. The same strategy as applied in Oberon but here it is a problem. We could, for example, handle constant division like variable division by calling __DIVF and then the behavior would be the same. But this needs a careful analysis. I don't want to call a function in all situations because it may be slower.

[Oleg-N-Cher]

Dear Josef, please run this test:

(-2147483647 - 1) DIV 8 = 268435455

See, not only the result is distorted here, but the sign of the expression. This is a very serious mistake. Can you test ofront on this line of code?

CONST c0 = (-32) * 8;

causes the problem:

err 204 product too large

This is a induced error caused by the sign distortion during division. You need to fix it.

Actually we have the function that consistently returns an incorrect result for MIN(LONGINT) DIV n. You can make a fix that won't cause slowdowns. I just suggest this replacement (thanked to Comdiv):

LONGINT SYSTEM_DIV(LONGINT x, LONGINT y)
{
  if (y > 0) {
    if (x < 0) return -1 - (-1 - x) / y;
    else       return x / y;
  }
  if (y < 0) {
    if (x > 0) return -1 + (x - 1) / y;
    else       return x / y;
  }
  __HALT(-12);
}

[jtempl]

the bug has been fixed by avoiding the C constant-div-overflow with unsigned arithmetics like in SYSTEM_DIV.

[Oleg-N-Cher]

Josef, why did you use return (-x)/(-y); ? return x/y; will be better.

ComDiv notes that operation of change sign is not safe for MIN(LONGINT) in some cases.

[jtempl]

where is a (-x)/(-y); ?

In general I am searching for a version that avoids the function call of SYSTEM_DIV with a lot of cases but I try to use an efficient inline macro instead, at least wherever it is possible, i.e. where there is no danger from side effects by executing functions repeatedly within that macro. But I am aware of the fact that it may not be easy to find a clean solution this way. What I have seen so far from tests is that the current fix works pretty well, doesn't it? Please note that I am not trying to support -x DIV -y, i.e. dividing by a negative value. This is not defined in Oberon, only in Component Pascal.

Regarding zero division: I have never seen a processor that ignores zero division. They all generate a trap. So I didn't want to spend time on such a test.

• Josef

Am Do., 31. Jan. 2019 um 23:03 Uhr schrieb Oleg N. Cher < notifications@github.com>:

Josef, why did you use return (-x)/(-y); ? return x/y; will be better.

ComDiv notes that operation of change sign is not safe for MIN(LONGINT) in some cases.

— You are receiving this because you modified the open/close state. Reply to this email directly, view it on GitHub https://github.com/jtempl/ofront/issues/36#issuecomment-459523601, or mute the thread https://github.com/notifications/unsubscribe-auth/AC00ayjhtFJMGKBgNQC5F3CM6AgVCWgkks5vI2gjgaJpZM4ZviWh .

[Oleg-N-Cher]

where is a (-x)/(-y); ?

It was present in earlier version of SYSTEM_DIV. I don't see it there now.

You can use the inline function __DIV instead of the macro. It will work in all modern C compilers. Also, the inline function solves the problem of side effects - double calculation of arguments in a macro.

In SYSTEM.h:

static inline LONGINT __DIV(LONGINT x, LONGINT y) {
  if (y > 0) {
    if (x < 0) return -1 - (-1 - x) / y;
    else       return x / y;
  }
  if (y < 0) {
    if (x > 0) return -1 + (x - 1) / y;
    else       return x / y;
  }
  __HALT(-12);
}

It's version for Component Pascal, and, of course, you can simplify it for only positive divisors.

I would recommend you take a look at our solution. It avoids the sign change operation (unsafe for MIN(LONGINT)), so it can be considered more reliable.

For a fault-tolerant system, it may be useful to intercept the division by 0 processing by replacing the HALT call handler to take action that is more reasonable than to give this processing to the overlying layer. At the same time, the operations of checking for 0 and for negative are very cheap and usually just boil down to checking the CPU flag.

Stefan Vorkoetter did some tests. I'll mail them to you.