[Octave-bug-tracker] [bug #61300] integer range might exceed upper limit

[Arun Giridhar]

Follow-up Comment #12, bug #61300 (project octave):

Regarding the integer range bug outside of primes.m (not the integer division
bug inside primes.m), I have isolated one location in Range.h that triggers
it. Very ironically, it comes down to integer division again (!) but this time
in C++. You can try the attached WIP patch to see what happens.

The place that causes the problem of m_final exceeding m_limit is this
statement inside range<T>::init, specifically the division inside the
conditional statement:


      m_numel = ((m_increment == T (0)
                  || (m_limit > m_base && m_increment < T (0))
                  || (m_limit < m_base && m_increment > T (0)))
                 ? T (0)
                 : (m_limit - m_base + m_increment) / m_increment);

      m_final = m_base + (m_numel - 1) * m_increment;


When the template class T is one of the Octave integer types, that division
causes rounding rather than flooring, and m_numel sometimes becomes one unit
bigger than it should be, which causes m_final to exceed its value as well.

I demonstrate this bug by adding extra cout statements and by manually
decrementing m_numel and m_final with this check right afterwards. (This code
is also in the attached WIP patch).


      if ( (m_increment > T (0) && m_final > m_limit)
           || (m_increment < T (0) && m_final < m_limit) )
        {
          std::cout << "Out of limits, old == ";
          std::cout << m_base << ':' << m_increment << ':' << m_limit
                    << " Final=" << m_final << " Numel=" << m_numel
                    << "\tAdjusting..., new == ";

          m_final -= m_increment;
          m_numel--;

          std::cout << m_base << ':' << m_increment << ':' << m_limit
                    << " Final=" << m_final << " Numel=" << m_numel << '\n';
        }


The output is as follows:

  octave:9> uint64 (0) : uint64 (6) : uint64 (100)
  Out of limits, old == 0:6:100 Final=102 Numel=18      Adjusting..., new ==
0:6:100 Final=96 Numel=17
  ans =
     0   6  12  18  24  30  36  42  48  54  60  66  72  78  84  90  96

  octave:10> uint64 (1) : uint64 (6) : uint64 (100)
  Out of limits, old == 1:6:100 Final=103 Numel=18      Adjusting..., new ==
1:6:100 Final=97 Numel=17
  ans =
     1   7  13  19  25  31  37  43  49  55  61  67  73  79  85  91  97

  octave:11> uint64 (2) : uint64 (6) : uint64 (100)
  ans =
     2   8  14  20  26  32  38  44  50  56  62  68  74  80  86  92  98

  octave:12> uint64 (3) : uint64 (6) : uint64 (100)
  ans =
     3   9  15  21  27  33  39  45  51  57  63  69  75  81  87  93  99

  octave:13> uint64 (4) : uint64 (6) : uint64 (100)
  ans =
      4   10   16   22   28   34   40   46   52   58   64   70   76   82   88 
 94  100

  octave:14> uint64 (5) : uint64 (6) : uint64 (100)
  Out of limits, old == 5:6:100 Final=101 Numel=17      Adjusting..., new ==
5:6:100 Final=95 Numel=16
  ans =
     5  11  17  23  29  35  41  47  53  59  65  71  77  83  89  95


and for decreasing ranges:


octave:17> int64 (100) : int64 (-6) : 0
Out of limits, old == 100:-6:0 Final=-2 Numel=18        Adjusting..., new == 
100:-6:0
Final=4 Numel=17
ans =
  100   94   88   82   76   70   64   58   52   46   40   34   28   22   16  
10    4

octave:18> int64 (99) : int64 (-6) : 0
Out of limits, old == 99:-6:0 Final=-3 Numel=18 Adjusting..., new == 99:-6:0
Final=3 Numel=17
ans =
  99  93  87  81  75  69  63  57  51  45  39  33  27  21  15   9   3

octave:19> int64 (98) : int64 (-6) : 0
ans =
  98  92  86  80  74  68  62  56  50  44  38  32  26  20  14   8   2

octave:20> int64 (97) : int64 (-6) : 0
ans =
  97  91  85  79  73  67  61  55  49  43  37  31  25  19  13   7   1

octave:21> int64 (96) : int64 (-6) : 0
ans =
  96  90  84  78  72  66  60  54  48  42  36  30  24  18  12   6   0

octave:22> int64 (95) : int64 (-6) : 0
Out of limits, old == 95:-6:0 Final=-1 Numel=17 Adjusting..., new == 95:-6:0
Final=5 Numel=16
ans =
  95  89  83  77  71  65  59  53  47  41  35  29  23  17  11   5


If you work through the arithmetic for each of the above 12 cases, you will
see that all the cases with overruns are the cases where the expression
(m_limit - m_base + m_increment) / m_increment is rounded upwards instead of
being floored, and the other cases are where the value is rounded downwards,
therefore the same as being floored.

That if-check in the WIP patch stops m_final from exceeding m_limit, but that
is not a good solution. The real solution would be to find a way to calculate
"(m_limit - m_base + m_increment) / m_increment)" while ensuring it is always
floored, not rounded. Is there a way to do that?

(file #52360)
    _______________________________________________________

Additional Item Attachment:

File name: range_bug_isolation_WIP.patch  Size:2 KB
   
<https://file.savannah.gnu.org/file/range_bug_isolation_WIP.patch?file_id=52360>



    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?61300>

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