[Octave-bug-tracker] [bug #54572] int64 does not saturate correctly in negative direction

[Dan Sebald]

Follow-up Comment #40, bug #54572 (project octave):

I reran the tests with 50 trials rather than 10 to reduce the variance a bit. 
Numbers are:


50 TRIALS

64-BIT ADD
       WITH_FAST_INT   NO_FAST_INT   GCC_BUILTINS   NEW_CLEAN_INT

tgood     13.428         13.324        13.260          13.236
tover     16.724         16.568        16.740          16.220
to/tg     1.2455         1.2435        1.2624          1.2254

32-BIT ADD
       WITH_FAST_INT   NO_FAST_INT   GCC_BUILTINS   NEW_CLEAN_INT

tgood     6.9160         6.9680        6.8960          6.8280
tover     8.6240         8.5640        8.5920          8.5840
to/tg     1.2470         1.2290        1.2459          1.2572

16-BIT ADD
       WITH_FAST_INT   NO_FAST_INT   GCC_BUILTINS   NEW_CLEAN_INT

tgood     4.0600         4.4840        4.0240          3.9560
tover     4.9520         4.9840        7.1400          4.9120
to/tg     1.2197         1.1115        1.7744          1.2417

8-BIT ADD
       WITH_FAST_INT   NO_FAST_INT   GCC_BUILTINS   NEW_CLEAN_INT

tgood     2.0240         2.7080        1.8520          1.6560
tover     3.4320         2.7280        3.8160          1.8720
to/tg     1.6957         1.0074        2.0605          1.1304


I thought I had discovered a way to reduce the "straightforward" version by a
machine code or two by using the following construct:


    // We shall carefully avoid anything that may overflow.
    T u = x + y;

    if (y < 0)
      {
        if (u - octave_int_base<T>::min_val () < 0)
          u = octave_int_base<T>::min_val ();
      }
    else
      {
        if (u - octave_int_base<T>::max_val () > 0)
          u = octave_int_base<T>::max_val ();
      }

    return u;


(that's what the NEW_CLEAN_INT column in the table is), but it *does not* work
by producing the wrong saturation value.  The idea of the above construct is
that we can allow the wrap to take place, then unwrap by subtracting MIN or
MAX value appropriately and check if it ends up in the improper region.  That
concept is fine in low-level machine code (say if programming a DSP or
something), but in C/C++ that is not reliable because C/C++ *does not define*
how signed integers wrap.  Here's a nice brief post on the topic

https://stackoverflow.com/a/18195756

that mentions compiler authors often utilize this undefinedness for
optimization.

So, my adjustment above is no good for C++, generally speaking.  And I suspect
that is what the original issue for this bug report was too; that once the
overflow of a signed integer occurs, we can't expect it to be anything, even
if there is a limited set of outcomes, be it 1's complement, 2's complement or
sign/magnitude.  The optimizing compiler essentially is assuming no overflow
occurred.  That is, even though this change to fix the original issue:

http://hg.savannah.gnu.org/hgweb/octave/rev/26c41d8bf170

works, it is still relying on a value of u, post-overflow.  In other words, it
is probably the following that originally failed


         + __signbit (~u);


because of optimization.  But in the future it could possibly be its
replacement


            ? (u < 0


that fails for overflowed u because of optimization.

This is another argument for simply avoiding the fancier 1's-comp, 2's-comp,
sign/mag construct and not work on overflowed integer values.  One can't make
any case to a compiler author what the result should be because it is
undefined.

    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?54572>

_______________________________________________
  Message sent via Savannah
  https://savannah.gnu.org/