bn.js - npm Package Compare versions

Comparing version 0.2.2 to 0.3.0

lib/bn.js

@@ -1,3 +0,11 @@
-var assert = require('assert');
+function assert(val, msg) {
+  if (!val)
+    throw new Error(msg || 'Assertion failed');
+}
 
+function assertEqual(l, r, msg) {
+  if (l != r)
+    throw new Error(msg || ('Assertion failed: ' + l + ' != ' + r));
+}
+
 function BN(number, base) {
@@ -65,2 +73,4 @@ if (number instanceof BN)
     this.sign = true;
+
+  this.strip();
 };
@@ -107,3 +117,3 @@
       this.mul(bigQ).copy(this);
-      this.add(new BN(word)).copy(this);
+      this.iadd(new BN(word));
       word = 0;
@@ -116,3 +126,3 @@ q = 1;
     this.mul(new BN(q)).copy(this);
-    this.add(new BN(word)).copy(this);
+    this.iadd(new BN(word));
   }
@@ -149,34 +159,23 @@ };
 
-function zero6(word) {
-  if (word.length === 5)
-    return '0' + word;
-  else if (word.length === 4)
-    return '00' + word;
-  else if (word.length === 3)
-    return '000' + word;
-  else if (word.length === 2)
-    return '0000' + word;
-  else if (word.length === 1)
-    return '00000' + word;
-  else
-    return word;
-}
+function _zero(n) {
+  var code = '';
+  for (var i = n - 1; i > 0; i--) {
+    var pad = '';
+    for (var j = 0; j < n - i; j++)
+      pad += '0';
+    code += 'if (w.length === ' + i + ') return \'' + pad + '\' + w;\n';
+  }
+  code += 'return w';
 
-function zero7(word) {
-  if (word.length === 6)
-    return '0' + word;
-  else if (word.length === 5)
-    return '00' + word;
-  else if (word.length === 4)
-    return '000' + word;
-  else if (word.length === 3)
-    return '0000' + word;
-  else if (word.length === 2)
-    return '00000' + word;
-  else if (word.length === 1)
-    return '000000' + word;
-  else
-    return word;
+  return new Function('w', code);
 }
 
+var zero6 = _zero(6);
+var zero14 = _zero(14);
+
+// Precomputed divisor for `.toString(10)` = 10 ^ 14
+var div10 = new BN(null);
+div10.words = [ 0x7A4000, 0x5AF310 ];
+div10.length = 2;
+
 BN.prototype.toString = function toString(base) {
@@ -199,9 +198,12 @@ base = base || 10;
     while (c.cmp(0) !== 0) {
-      var r = c.mod(10000000);
-      c = c.div(10000000);
-      assert.equal(r.length, 1);
+      var tmp = c._div(div10);
+      var r = tmp.mod;
+      c = tmp.div;
+
+      assert(r.length <= 2);
+      r = r.length === 2 ? (r.words[0] + r.words[1] * 0x1000000) : r.words[0];
       if (c.cmp(0) !== 0)
-        out = zero7(r.words[0] + '') + out;
+        out = zero14(r + '') + out;
       else
-        out = r.words[0] + out;
+        out = r + out;
     }
@@ -230,3 +232,3 @@ if (this.cmp(0) === 0)
     var b = q.andl(0xff);
-    q.ishr(8);
+    q.ishrn(8);
 
@@ -277,12 +279,23 @@ // Assume big-endian
 
-// Add `num` to `this`
-BN.prototype.add = function add(num, base) {
+// Add `num` to `this` in-place
+BN.prototype.iadd = function iadd(num, base) {
   if (!(num instanceof BN))
     num = new BN(num, base);
 
-  if (num.sign && !this.sign)
-    return this.sub(num.neg());
-  else if (!num.sign && this.sign)
-    return num.sub(this.neg());
+  // negative + positive
+  if (this.sign && !num.sign) {
+    this.sign = false;
+    var r = this.isub(num);
+    this.sign = !this.sign;
+    return this;
 
+  // positive + negative
+  } else if (!this.sign && num.sign) {
+    num.sign = false;
+    var r = this.isub(num);
+    num.sign = true;
+    return r;
+  }
+
+  // a.length > b.length
   var a;
@@ -297,53 +310,87 @@ var b;
   }
-  // a.length > b.length
-  var result = new BN(null);
-  result.sign = num.sign;
-  result.length = a.length;
-  result.words = a.words.slice();
 
   var carry = 0;
   for (var i = 0; i < b.length; i++) {
-    var r = result.words[i] + b.words[i] + carry;
-    result.words[i] = r & 0xffffff;
+    var r = a.words[i] + b.words[i] + carry;
+    this.words[i] = r & 0xffffff;
     carry = r >> 24;
   }
-  for (; carry != 0 && i < a.length; i++) {
-    var r = result.words[i] + carry;
-    result.words[i] = r & 0xffffff;
+  for (; carry !== 0 && i < a.length; i++) {
+    var r = a.words[i] + carry;
+    this.words[i] = r & 0xffffff;
     carry = r >> 24;
   }
-  if (carry) {
-    result.words.push(carry);
-    result.length++;
+
+  this.length = a.length;
+  if (carry !== 0) {
+    this.words.push(carry);
+    this.length++;
+  // Copy the rest of the words
+  } else if (a !== this) {
+    for (; i < a.length; i++)
+      this.words[i] = a.words[i];
   }
 
-  return result;
+  return this;
 };
 
-// Subtract `num` from `this`
-BN.prototype.sub = function sub(num, base) {
+// Add `num` to `this`
+BN.prototype.add = function add(num, base) {
   if (!(num instanceof BN))
     num = new BN(num, base);
 
-  if (num.sign)
-    return this.add(num.neg());
-  else if (this.sign)
-    return this.neg().add(num).neg();
+  if (num.sign && !this.sign)
+    return this.sub(num.neg());
+  else if (!num.sign && this.sign)
+    return num.sub(this.neg());
 
+  if (this.length > num.length)
+    return this.clone().iadd(num);
+  else
+    return num.clone().iadd(this);
+};
+
+// Subtract `num` from `this` in-place
+BN.prototype.isub = function isub(num, base) {
+  if (!(num instanceof BN))
+    num = new BN(num, base);
+
+  // this - (-num) = this + num
+  if (num.sign) {
+    num.sign = false;
+    var r = this.iadd(num);
+    num.sign = true;
+    return r;
+
+  // -this - num = -(this + num)
+  } else if (this.sign) {
+    this.sign = false;
+    this.iadd(num);
+    this.sign = true;
+    return this;
+  }
+
   // At this point both numbers are positive
   var cmp = this.cmp(num);
-  if (cmp === 0)
-    return new BN(0);
-  else if (cmp < 0)
-    return num.sub(this).neg();
 
-  // At this point `this` is > `num`
-  var result = new BN(null);
-  result.words = new Array(this.length);
+  // Optimization - zeroify
+  if (cmp === 0) {
+    this.sign = false;
+    this.length = 1;
+    this.words = [ 0 ];
+    return this;
+  }
 
+  // a > b
+  if (cmp > 0) {
+    var a = this;
+    var b = num;
+  } else {
+    var a = num;
+    var b = this;
+  }
+
   var carry = 0;
-  for (var i = 0; i < this.length; i++) {
-    var a = this.words[i];
-    var b = i < num.length ? num.words[i] : 0;
-    var r = a - b - carry;
+  for (var i = 0; i < b.length; i++) {
+    var r = a.words[i] - b.words[i] - carry;
     if (r < 0) {
@@ -355,18 +402,32 @@ r += 0x1000000;
     }
-    result.words[i] = r;
-
-    // Optimization
-    if (carry === 0 && i >= num.length) {
-      // Copy rest of the words
-      i++;
-      for (; i < this.length; i++)
-        result.words[i] = this.words[i];
-      break;
+    this.words[i] = r;
+  }
+  for (; carry !== 0 && i < a.length; i++) {
+    var r = a.words[i] - carry;
+    if (r < 0) {
+      r += 0x1000000;
+      carry = 1;
+    } else {
+      carry = 0;
     }
+    this.words[i] = r;
   }
-  result.length = result.words.length;
 
-  return result.strip();
+  // Copy rest of the words
+  if (carry === 0 && i < a.length && a !== this)
+    for (; i < a.length; i++)
+      this.words[i] = a.words[i];
+  this.length = this.words.length;
+
+  if (a !== this)
+    this.sign = true;
+
+  return this.strip();
 };
 
+// Subtract `num` from `this`
+BN.prototype.sub = function sub(num, base) {
+  return this.clone().isub(num, base);
+};
+
 // Multiply `this` by `num`
@@ -465,4 +526,4 @@ BN.prototype.mul = function mul(num, base) {
 // Shift-left in-place
-BN.prototype.ishl = function ishl(bits) {
-  assert(typeof bits === 'number');
+BN.prototype.ishln = function ishln(bits) {
+  assert(typeof bits === 'number' && bits >= 0);
   var r = bits % 24;
@@ -499,4 +560,4 @@ var s = (bits - r) / 24;
 // NOTE: `hint` is a lowest bit before trailing zeroes
-BN.prototype.ishr = function ishr(bits, hint) {
-  assert(typeof bits === 'number');
+BN.prototype.ishrn = function ishrn(bits, hint) {
+  assert(typeof bits === 'number' && bits >= 0);
   if (!hint)
@@ -537,18 +598,18 @@ hint = 0;
 // Shift-left
-BN.prototype.shl = function shl(bits) {
-  return this.clone().ishl(bits);
+BN.prototype.shln = function shln(bits) {
+  return this.clone().ishln(bits);
 };
 
 // Shift-right
-BN.prototype.shr = function shr(bits) {
-  return this.clone().ishr(bits);
+BN.prototype.shrn = function shrn(bits) {
+  return this.clone().ishrn(bits);
 };
 
 // Return only lowers bits of number (in-place)
-BN.prototype.imask = function imask(bits) {
-  assert(typeof bits === 'number');
+BN.prototype.imaskn = function imaskn(bits) {
+  assert(typeof bits === 'number' && bits >= 0);
   var r = bits % 24;
   var s = (bits - r) / 24;
 
-  assert(!this.sign, 'imask works only with positive numbers');
+  assert(!this.sign, 'imaskn works only with positive numbers');
 
@@ -569,11 +630,11 @@ if (r !== 0)
 // Return only lowers bits of number
-BN.prototype.mask = function mask(bits) {
-  return this.clone().imask(bits);
+BN.prototype.maskn = function maskn(bits) {
+  return this.clone().imaskn(bits);
 };
 
 // Add plain number `num` to `this`
-BN.prototype.iadd = function iadd(num) {
+BN.prototype.iaddn = function iaddn(num) {
   assert(typeof num === 'number');
   if (num < 0)
-    return this.isub(num);
+    return this.isubn(num);
   this.words[0] += num;
@@ -595,7 +656,7 @@
 // Subtract plain number `num` from `this`
-BN.prototype.isub = function isub(num) {
+BN.prototype.isubn = function isubn(num) {
   assert(typeof num === 'number');
-  assert(this.cmp(num) >= 0, 'Sign change is not supported in isub');
+  assert(this.cmp(num) >= 0, 'Sign change is not supported in isubn');
   if (num < 0)
-    return this.iadd(-num);
+    return this.iaddn(-num);
   this.words[0] -= num;
@@ -615,5 +676,5 @@
   var shift = Math.max(0, this.bitLength() - num.bitLength());
-  var max = num.shl(shift);
+  var max = num.shln(shift);
   if (shift > 0 && this.cmp(max) < 0) {
-    max.ishr(1, shift);
+    max.ishrn(1, shift);
     shift--;
@@ -623,3 +684,3 @@ }
 
-  var c = this;
+  var c = this.clone();
   var r = new BN(0);
@@ -629,7 +690,7 @@ while (c.cmp(num) >= 0) {
     if (c.cmp(max) >= 0) {
-      c = c.sub(max);
+      c.isub(max);
       r.binc(shift);
     }
     var delta = Math.max(1, maxLen - c.bitLength());
-    max.ishr(delta, shift);
+    max.ishrn(delta, shift);
     maxLen -= delta;
@@ -686,3 +747,3 @@ shift -= delta;
   var a = this;
-  var b = p;
+  var b = p.clone();
 
@@ -699,21 +760,21 @@ if (a.sign)
     while (a.isEven()) {
-      a.ishr(1);
+      a.ishrn(1);
       if (x1.isEven())
-        x1.ishr(1);
+        x1.ishrn(1);
       else
-        x1 = x1.add(p).ishr(1);
+        x1 = x1.add(p).ishrn(1);
     }
     while (b.isEven()) {
-      b.ishr(1);
+      b.ishrn(1);
       if (x2.isEven())
-        x2.ishr(1);
+        x2.ishrn(1);
       else
-        x2 = x2.add(p).ishr(1);
+        x2 = x2.add(p).ishrn(1);
     }
     if (a.cmp(b) >= 0) {
-      a = a.sub(b);
-      x1 = x1.sub(x2);
+      a.isub(b);
+      x1.isub(x2);
     } else {
-      b = b.sub(a);
-      x2 = x2.sub(x1);
+      b.isub(a);
+      x2.isub(x1);
     }
@@ -853,3 +914,3 @@ }
   assert(!this.sign, 'mont works only with positives');
-  var res = this.shl(ctx.shift).mod(ctx.m);
+  var res = this.shln(ctx.shift).mod(ctx.m);
   res.mont = ctx;
@@ -865,13 +926,17 @@ return res;
 
-BN.prototype.montAdd = function montAdd(num, base) {
-  if (!(num instanceof BN))
-    num = new BN(num, base).toMont(this.mont);
+BN.prototype._montVerify = function _montVerify(num) {
   assert(!this.sign && !num.sign, 'mont works only with positives');
   assert(this.mont && this.mont === num.mont,
          'montAdd works only with mont numbers');
+};
 
+BN.prototype.montAdd = function montAdd(num, base) {
+  if (!(num instanceof BN))
+    num = new BN(num, base).toMont(this.mont);
+  this._montVerify(num);
+
   var mont = this.mont;
   var res = this.add(num);
   if (res.cmp(mont.m) >= 0)
-    res = res.sub(mont.m);
+    res.isub(mont.m);
   res.mont = mont;
@@ -881,8 +946,19 @@ return res;
 
+BN.prototype.montIAdd = function montIAdd(num, base) {
+  if (!(num instanceof BN))
+    num = new BN(num, base).toMont(this.mont);
+  this._montVerify(num);
+
+  var mont = this.mont;
+  var res = this.iadd(num);
+  if (res.cmp(mont.m) >= 0)
+    res.isub(mont.m);
+  res.mont = mont;
+  return res;
+};
+
 BN.prototype.montSub = function montSub(num, base) {
   if (!(num instanceof BN))
     num = new BN(num, base).toMont(this.mont);
-  assert(!this.sign && !num.sign, 'mont works only with positives');
-  assert(this.mont && this.mont === num.mont,
-         'montSub works only with mont numbers');
+  this._montVerify(num);
 
@@ -892,3 +968,3 @@ var mont = this.mont;
   if (res.cmp(0) < 0)
-    res = res.add(mont.m);
+    res.iadd(mont.m);
 
@@ -899,2 +975,15 @@ res.mont = mont;
 
+BN.prototype.montISub = function montISub(num, base) {
+  if (!(num instanceof BN))
+    num = new BN(num, base).toMont(this.mont);
+  this._montVerify(num);
+
+  var mont = this.mont;
+  var res = this.isub(num);
+  if (res.cmp(0) < 0)
+    res.iadd(mont.m);
+  res.mont = mont;
+  return res;
+};
+
 BN.prototype.montShl = function montShl(num) {
@@ -905,3 +994,3 @@ assert(!this.sign, 'mont works only with positives');
   var mont = this.mont;
-  var res = this.shl(num).mod(mont.m);
+  var res = this.shln(num).mod(mont.m);
 
@@ -915,5 +1004,3 @@ res.mont = mont;
     num = new BN(num, base).toMont(this.mont);
-  assert(!this.sign && !num.sign, 'mont works only with positives');
-  assert(this.mont && this.mont === num.mont,
-         'montMul works only with mont numbers');
+  this._montVerify(num);
 
@@ -928,9 +1015,9 @@ var mont = this.mont;
   var t = this.mul(num);
-  var c = t.mul(mont.minv).imask(mont.shift).mul(mont.m);
-  var u = t.sub(c).ishr(mont.shift);
+  var c = t.mul(mont.minv).imaskn(mont.shift).mul(mont.m);
+  var u = t.isub(c).ishrn(mont.shift);
   var res = u;
   if (u.cmp(mont.m) >= 0)
-    res = u.sub(mont.m);
+    res = u.isub(mont.m);
   else if (u.cmp(0) < 0)
-    res = u.add(mont.m);
+    res = u.iadd(mont.m);
 
@@ -945,9 +1032,2 @@ res.mont = mont;
 
-BN.prototype._fastSqrtm = function _fastSqrtm(odd, num) {
-  assert(this.mont);
-
-
-  return r;
-};
-
 // Square root over p
@@ -963,3 +1043,3 @@ BN.prototype.montSqrt = function montSqrt() {
   if (mont.m.andl(3) === 3) {
-    var pow = mont.m.add(1).ishr(2);
+    var pow = mont.m.add(1).ishrn(2);
     var r = this.montPow(pow);
@@ -988,3 +1068,3 @@ return r;
   r.sign = !this.sign;
-  r = r.add(this.mont.m);
+  r = r.iadd(this.mont.m);
   r.mont = this.mont;
@@ -1003,3 +1083,3 @@ return r;
     w.push(q.andl(1));
-    q.ishr(1);
+    q.ishrn(1);
   }
@@ -1034,3 +1114,3 @@
     this.shift += 24 - (this.shift % 24);
-  this.r = new BN(1).ishl(this.shift);
+  this.r = new BN(1).ishln(this.shift);
   this.r2 = this.r.sqr().mod(this.m);
@@ -1037,0 +1117,0 @@ this.rinv = this.r.invm(this.m);

package.json

 {
   "name": "bn.js",
-  "version": "0.2.2",
+  "version": "0.3.0",
   "description": "Big number implementation in pure javascript",
@@ -5,0 +5,0 @@ "main": "lib/bn.js",

test/bn-test.js

@@ -52,2 +52,8 @@ var assert = require('assert');
     assert.equal(r.toString(16), '125868');
+
+    var k = bn('abcdefabcdefabcdef', 16);
+    var r = bn('deadbeef', 16);
+    for (var i = 0; i < 257; i++)
+      r.iadd(k);
+    assert.equal(r.toString(16), 'ac79bd9b79be7a277bde');
   });
@@ -61,8 +67,26 @@
 
-    var a = '31ff3c61db2db84b9823d320907a573f6ad37c437abe458b1802cda041d6384' +
-            'a7d8daef41395491e2';
-    var b = '6f0e4d9f1d6071c183677f601af9305721c91d31b0bbbae8fb790000';
-    var r = '31ff3c61db2db84b9823d3208989726578fd75276287cd9516533a9acfb9a67' +
-            '76281f34583ddb91e2';
-    assert.equal(bn(a, 16).sub(b, 16).toString(16), r);
+    var a = new bn(
+      '31ff3c61db2db84b9823d320907a573f6ad37c437abe458b1802cda041d6384' +
+          'a7d8daef41395491e2',
+      16);
+    var b = new bn(
+      '6f0e4d9f1d6071c183677f601af9305721c91d31b0bbbae8fb790000',
+      16);
+    var r = new bn(
+      '31ff3c61db2db84b9823d3208989726578fd75276287cd9516533a9acfb9a67' +
+          '76281f34583ddb91e2',
+      16);
+    assert.equal(a.sub(b).cmp(r), 0);
+
+    // In-place
+    assert.equal(b.clone().isub(a).neg().cmp(r), 0);
+
+    // Carry and copy
+    var a = new bn('12345', 16);
+    var b = new bn('1000000000000', 16);
+    assert.equal(a.isub(b).toString(16), '-fffffffedcbb');
+
+    var a = new bn('12345', 16);
+    var b = new bn('1000000000000', 16);
+    assert.equal(b.isub(a).toString(16), 'fffffffedcbb');
   });
@@ -129,5 +153,5 @@
   it('should shl numbers', function() {
-    assert.equal(bn('69527932928').shl(13).toString(16),
+    assert.equal(bn('69527932928').shln(13).toString(16),
                  '2060602000000');
-    assert.equal(bn('69527932928').shl(45).toString(16),
+    assert.equal(bn('69527932928').shln(45).toString(16),
                  '206060200000000000000');
@@ -137,5 +161,5 @@ });
   it('should shr numbers', function() {
-    assert.equal(bn('69527932928').shr(13).toString(16),
+    assert.equal(bn('69527932928').shrn(13).toString(16),
                  '818180');
-    assert.equal(bn('69527932928').shr(17).toString(16),
+    assert.equal(bn('69527932928').shrn(17).toString(16),
                  '81818');
@@ -166,8 +190,8 @@ });
 
-  it('should support imask', function() {
-    assert.equal(bn(0).imask(1).toString(16), '0');
-    assert.equal(bn(3).imask(1).toString(16), '1');
-    assert.equal(bn('123456789', 16).imask(4).toString(16), '9');
-    assert.equal(bn('123456789', 16).imask(16).toString(16), '6789');
-    assert.equal(bn('123456789', 16).imask(28).toString(16), '3456789');
+  it('should support imaskn', function() {
+    assert.equal(bn(0).imaskn(1).toString(16), '0');
+    assert.equal(bn(3).imaskn(1).toString(16), '1');
+    assert.equal(bn('123456789', 16).imaskn(4).toString(16), '9');
+    assert.equal(bn('123456789', 16).imaskn(16).toString(16), '6789');
+    assert.equal(bn('123456789', 16).imaskn(28).toString(16), '3456789');
   });
@@ -174,0 +198,0 @@

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Uses eval

Supply chain risk

Package uses dynamic code execution (e.g., eval()), which is a dangerous practice. This can prevent the code from running in certain environments and increases the risk that the code may contain exploits or malicious behavior.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

34698

increased by6.21%

Lines of code

1134

increased by8%

Number of medium supply chain risk alerts

0

decreased by-100%

No dependency changes