# HG changeset patch
# User Lachlan Andrew <lachlanbis@gmail.com>
# Date 1452913425 -39600
# Node ID a93fa1b0796e347fed23a9b2e650a57ac02dc3c2
# Parent  6209f428426cdbe9d8f403932526491c5d35ec2c
Avoid overflow while reshaping large sparse matrices (bug #42850).

* Sparse.cc (reshape): track quotient and remainder of (i*old_nr)
divided by new_nr, instead of evaluating i*old_nr explicitly.

diff -r 6209f428426c -r a93fa1b0796e liboctave/array/Sparse.cc
--- a/liboctave/array/Sparse.cc	Sat Jan 09 20:40:49 2016 +1100
+++ b/liboctave/array/Sparse.cc	Sat Jan 16 14:03:45 2016 +1100
@@ -842,22 +842,35 @@
 
           octave_idx_type kk = 0;
           retval.xcidx (0) = 0;
+          // quotient and remainder of  i * old_nr divided by new_nr
+          // Track them individually to avoid overflow (bug #42850).
+          octave_idx_type i_old_qu = 0;
+          octave_idx_type i_old_rm = static_cast<octave_idx_type> (-old_nr);
           for (octave_idx_type i = 0; i < old_nc; i++)
-            for (octave_idx_type j = cidx (i); j < cidx (i+1); j++)
-              {
-                octave_idx_type tmp = i * old_nr + ridx (j);
-                if (tmp < 0)
-                  (*current_liboctave_error_handler)
-                    ("reshape: overflow in octave_idx_type prevents reshaping array");
-
-                octave_idx_type ii = tmp % new_nr;
-                octave_idx_type jj = (tmp - ii) / new_nr;
-                for (octave_idx_type k = kk; k < jj; k++)
-                  retval.xcidx (k+1) = j;
-                kk = jj;
-                retval.xdata (j) = data (j);
-                retval.xridx (j) = ii;
-              }
+            {
+              i_old_rm += old_nr;
+              if (i_old_rm >= new_nr)
+                {
+                  i_old_qu += i_old_rm / new_nr;
+                  i_old_rm = i_old_rm % new_nr;
+                }
+              for (octave_idx_type j = cidx (i); j < cidx (i+1); j++)
+                {
+                  octave_idx_type ii, jj;
+                  ii = (i_old_rm + ridx (j)) % new_nr;
+                  jj = i_old_qu + (i_old_rm + ridx (j)) / new_nr;
+
+                  // Original calculation subject to overflow
+                  // ii = (i*old_nr + ridx (j)) % new_nr
+                  // jj = (i*old_nr + ridx (j)) / new_nr
+
+                  for (octave_idx_type k = kk; k < jj; k++)
+                    retval.xcidx (k+1) = j;
+                  kk = jj;
+                  retval.xdata (j) = data (j);
+                  retval.xridx (j) = ii;
+                }
+            }
           for (octave_idx_type k = kk; k < new_nc; k++)
             retval.xcidx (k+1) = new_nnz;
         }