Refactor bigint shifting code in preparation of shifting intrinsics.

runtime/lib/bigint.dart

 // Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 // Copyright 2009 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
 /*
  * Copyright (c) 2003-2005  Tom Wu
@@ skipping 153 matching lines @@
     if ((t = x >> 16) != 0) { x = t; r += 16; }
     if ((t = x >> 8) != 0) { x = t; r += 8; }
     if ((t = x >> 4) != 0) { x = t; r += 4; }
     if ((t = x >> 2) != 0) { x = t; r += 2; }
     if ((x >> 1) != 0) { r += 1; }
     return r;
   }
 
   // Return this << n*_DIGIT_BITS.
   _Bigint _dlShift(int n) {
-    var used = _used;
+    final used = _used;
     if (used == 0) {
       return _ZERO;
     }
-    var r_used = used + n;
-    var digits = _digits;
-    var r_digits = new Uint32List(r_used + (r_used & 1));
+    final r_used = used + n;
+    final digits = _digits;
+    final r_digits = new Uint32List(r_used + (r_used & 1));
     var i = used;
     while (--i >= 0) {
       r_digits[i + n] = digits[i];
     }
     return new _Bigint(_neg, r_used, r_digits);
   }
 
   // r_digits[0..r_used-1] = x_digits[0..x_used-1] << n*_DIGIT_BITS.
   // Return r_used.
   static int _dlShiftDigits(Uint32List x_digits, int x_used, int n,
                             Uint32List r_digits) {
     if (x_used == 0) {
       return 0;
     }
     if (n == 0 && r_digits == x_digits) {
       return x_used;
     }
-    var r_used = x_used + n;
+    final r_used = x_used + n;
     assert(r_digits.length >= r_used + (r_used & 1));
     var i = x_used;
     while (--i >= 0) {
       r_digits[i + n] = x_digits[i];
     }
     i = n;
     while (--i >= 0) {
       r_digits[i] = 0;
     }
     if (r_used.isOdd) {
       r_digits[r_used] = 0;
     }
     return r_used;
   }
 
   // Return this >> n*_DIGIT_BITS.
   _Bigint _drShift(int n) {
-    var used = _used;
+    final used = _used;
     if (used == 0) {
       return _ZERO;
     }
-    var r_used = used - n;
+    final r_used = used - n;
     if (r_used <= 0) {
       return _neg ? _MINUS_ONE : _ZERO;
     }
-    var digits = _digits;
-    var r_digits = new Uint32List(r_used + (r_used & 1));
+    final digits = _digits;
+    final r_digits = new Uint32List(r_used + (r_used & 1));
     for (var i = n; i < used; i++) {
       r_digits[i - n] = digits[i];
     }
-    var r = new _Bigint(_neg, r_used, r_digits);
+    final r = new _Bigint(_neg, r_used, r_digits);
     if (_neg) {
       // Round down if any bit was shifted out.
       for (var i = 0; i < n; i++) {
         if (digits[i] != 0) {
           return r._sub(_ONE);
         }
       }
     }
     return r;
   }
 
   // r_digits[0..r_used-1] = x_digits[0..x_used-1] >> n*_DIGIT_BITS.
   // Return r_used.
   static int _drShiftDigits(Uint32List x_digits, int x_used, int n,
                             Uint32List r_digits) {
-    var r_used = x_used - n;
+    final r_used = x_used - n;
     if (r_used <= 0) {
       return 0;
     }
     assert(r_digits.length >= r_used + (r_used & 1));
     for (var i = n; i < x_used; i++) {
       r_digits[i - n] = x_digits[i];
     }
     if (r_used.isOdd) {
       r_digits[r_used] = 0;
     }
     return r_used;
   }
 
+  // r_digits[0..r_used-1] = x_digits[0..x_used-1] << n.
+  static void _lsh(Uint32List x_digits, int x_used, int n,
+                   Uint32List r_digits) {
+    final ds = n ~/ _DIGIT_BITS;
+    final bs = n % _DIGIT_BITS;

[srdjan, 2015/03/27 22:29:54]

You compute now ds and bs twice: once here and once in caller. I guess it has no
performance impact because DIGIT_BITS is power of 2 and the oberhead of loop
dominates

[regis, 2015/03/27 22:41:46]

Correct. It is cheaper to recalculate the values from n, rather than pass them
as additional arguments.

+    final cbs = _DIGIT_BITS - bs;
+    final bm = (1 << cbs) - 1;
+    var c = 0;
+    var i = x_used;
+    while (--i >= 0) {
+      final d = x_digits[i];
+      r_digits[i + ds + 1] = (d >> cbs) | c;
+      c = (d & bm) << bs;
+    }
+    r_digits[ds] = c;
+    i = ds;
+    while (--i >= 0) {
+      r_digits[i] = 0;
+    }
+  }
+
   // Return this << n.
   _Bigint _lShift(int n) {
-    var ds = n ~/ _DIGIT_BITS;
-    var bs = n % _DIGIT_BITS;
+    final ds = n ~/ _DIGIT_BITS;
+    final bs = n % _DIGIT_BITS;
     if (bs == 0) {
       return _dlShift(ds);
     }
-    var cbs = _DIGIT_BITS - bs;
-    var bm = (1 << cbs) - 1;
     var r_used = _used + ds + 1;
-    var digits = _digits;
     var r_digits = new Uint32List(r_used + (r_used & 1));
-    var c = 0;
-    var i = _used;
-    while (--i >= 0) {
-      final d = digits[i];
-      r_digits[i + ds + 1] = (d >> cbs) | c;
-      c = (d & bm) << bs;
-    }
-    r_digits[ds] = c;
+    _lsh(_digits, _used, n, r_digits);
     return new _Bigint(_neg, r_used, r_digits);
   }
 
   // r_digits[0..r_used-1] = x_digits[0..x_used-1] << n.
   // Return r_used.
   static int _lShiftDigits(Uint32List x_digits, int x_used, int n,
                            Uint32List r_digits) {
-    var ds = n ~/ _DIGIT_BITS;
-    var bs = n % _DIGIT_BITS;
+    final ds = n ~/ _DIGIT_BITS;
+    final bs = n % _DIGIT_BITS;
     if (bs == 0) {
       return _dlShiftDigits(x_digits, x_used, ds, r_digits);
     }
-    var cbs = _DIGIT_BITS - bs;
-    var bm = (1 << cbs) - 1;
     var r_used = x_used + ds + 1;
     assert(r_digits.length >= r_used + (r_used & 1));
-    var c = 0;
-    var i = x_used;
-    while (--i >= 0) {
-      final d = x_digits[i];
-      r_digits[i + ds + 1] = (d >> cbs) | c;
-      c = (d & bm) << bs;
-    }
-    r_digits[ds] = c;
-    i = ds;
-    while (--i >= 0) {
-      r_digits[i] = 0;
-    }
+    _lsh(x_digits, x_used, n, r_digits);
     if (r_digits[r_used - 1] == 0) {
       r_used--;  // Clamp result.
     } else if (r_used.isOdd) {
       r_digits[r_used] = 0;
     }
     return r_used;
   }
 
+  // r_digits[0..r_used-1] = x_digits[0..x_used-1] >> n.
+  static void _rsh(Uint32List x_digits, int x_used, int n,
+                   Uint32List r_digits) {
+    final ds = n ~/ _DIGIT_BITS;
+    final bs = n % _DIGIT_BITS;
+    final cbs = _DIGIT_BITS - bs;
+    final bm = (1 << bs) - 1;
+    var c = x_digits[ds] >> bs;
+    final last = x_used - ds - 1;
+    for (var i = 0; i < last; i++) {
+      final d = x_digits[i + ds + 1];
+      r_digits[i] = ((d & bm) << cbs) | c;
+      c = d >> bs;
+    }
+    r_digits[last] = c;
+  }
+
   // Return this >> n.
   _Bigint _rShift(int n) {
-    var ds = n ~/ _DIGIT_BITS;
-    var bs = n % _DIGIT_BITS;
+    final ds = n ~/ _DIGIT_BITS;
+    final bs = n % _DIGIT_BITS;
     if (bs == 0) {
       return _drShift(ds);
     }
-    var r_used = _used - ds;
+    final used = _used;
+    final r_used = used - ds;
     if (r_used <= 0) {
       return _neg ? _MINUS_ONE : _ZERO;
     }
-    var cbs = _DIGIT_BITS - bs;
-    var bm = (1 << bs) - 1;
-    var digits = _digits;
-    var r_digits = new Uint32List(r_used + (r_used & 1));
-    r_digits[0] = digits[ds] >> bs;
-    var used = _used;
-    for (var i = ds + 1; i < used; i++) {
-      final d = digits[i];
-      r_digits[i - ds - 1] |= (d & bm) << cbs;
-      r_digits[i - ds] = d >> bs;
-    }
-    var r = new _Bigint(_neg, r_used, r_digits);
+    final digits = _digits;
+    final r_digits = new Uint32List(r_used + (r_used & 1));
+    _rsh(digits, used, n, r_digits);
+    final r = new _Bigint(_neg, r_used, r_digits);
     if (_neg) {
       // Round down if any bit was shifted out.
-      if ((digits[ds] & bm) != 0) {
+      if ((digits[ds] & ((1 << bs) - 1)) != 0) {
         return r._sub(_ONE);
       }
       for (var i = 0; i < ds; i++) {
         if (digits[i] != 0) {
           return r._sub(_ONE);
         }
       }
     }
     return r;
   }
 
   // r_digits[0..r_used-1] = x_digits[0..x_used-1] >> n.
   // Return r_used.
   static int _rShiftDigits(Uint32List x_digits, int x_used, int n,
                            Uint32List r_digits) {
-    var ds = n ~/ _DIGIT_BITS;
-    var bs = n % _DIGIT_BITS;
+    final ds = n ~/ _DIGIT_BITS;
+    final bs = n % _DIGIT_BITS;
     if (bs == 0) {
       return _drShiftDigits(x_digits, x_used, ds, r_digits);
     }
     var r_used = x_used - ds;
     if (r_used <= 0) {
       return 0;
     }
-    var cbs = _DIGIT_BITS - bs;
-    var bm = (1 << bs) - 1;
     assert(r_digits.length >= r_used + (r_used & 1));
-    r_digits[0] = x_digits[ds] >> bs;
-    for (var i = ds + 1; i < x_used; i++) {
-      final d = x_digits[i];
-      r_digits[i - ds - 1] |= (d & bm) << cbs;
-      r_digits[i - ds] = d >> bs;
-    }
+    _rsh(x_digits, x_used, n, r_digits);
     if (r_digits[r_used - 1] == 0) {
       r_used--;  // Clamp result.
     } else if (r_used.isOdd) {
       r_digits[r_used] = 0;
     }
     return r_used;
   }
 
   // Return 0 if abs(this) == abs(a).
   // Return a positive number if abs(this) > abs(a).
@@ skipping 1377 matching lines @@
 
   int _mul(Uint32List x_digits, int x_used,
            Uint32List y_digits, int y_used,
            Uint32List r_digits) {
     var r_used = _Bigint._mulDigits(x_digits, x_used,
                                     y_digits, y_used,
                                     r_digits);
     return _reduce(r_digits, r_used);
   }
 }