Comparing version 0.11.4 to 0.11.5
6
1.js
var bn = require('./'); | ||
var p = new bn('ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f', 16); | ||
var a = new bn('79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798', 16); | ||
var a = new bn('79be667e f9dcbbac 55a06295 ce870b07 029bfcdb 2dce28d9 59f2815b 16f81798', 16); | ||
var c = a.sqr(); | ||
console.log(c.divmod(p)); | ||
console.log(c._shiftDiv(p)); | ||
return; | ||
var m = bn.red('k256'); | ||
@@ -7,0 +11,0 @@ var am = a.toRed(m); |
136
lib/bn.js
@@ -848,40 +848,67 @@ // Utils | ||
BN.prototype._shiftDiv = function _shiftDiv(num, mode) { | ||
// Find maximum Q, Q * num <= this | ||
var shift = Math.max(0, this.bitLength() - num.bitLength()); | ||
var max = num.shln(shift); | ||
if (shift > 0 && this.cmp(max) < 0) { | ||
max.ishrn(1, shift); | ||
shift--; | ||
BN.prototype._wordDiv = function _wordDiv(num, mode) { | ||
var shift = this.length - num.length; | ||
var a = this.clone(); | ||
var b = num; | ||
var q = mode !== 'mod' && new BN(0); | ||
var sign = false; | ||
// Approximate quotient at each step | ||
while (a.length > b.length) { | ||
// NOTE: a.length is always >= 2, because of the condition .div() | ||
var hi = a.words[a.length - 1] * 0x4000000 + a.words[a.length - 2]; | ||
var sq = (hi / b.words[b.length - 1]); | ||
var sqhi = (sq / 0x4000000) | 0; | ||
var sqlo = sq & 0x3ffffff; | ||
sq = new BN(null); | ||
sq.words = [ sqlo, sqhi ]; | ||
sq.length = 2; | ||
// Collect quotient | ||
var shift = (a.length - b.length - 1) * 26; | ||
if (q) { | ||
var t = sq.shln(shift); | ||
if (a.sign) | ||
q.isub(t); | ||
else | ||
q.iadd(t); | ||
} | ||
sq = sq.mul(b).ishln(shift); | ||
if (a.sign) | ||
a.iadd(sq) | ||
else | ||
a.isub(sq); | ||
} | ||
var maxLen = max.bitLength(); | ||
// At this point a.length <= b.length | ||
while (a.ucmp(b) >= 0) { | ||
// NOTE: a.length is always >= 2, because of the condition above | ||
var hi = a.words[a.length - 1]; | ||
var sq = new BN((hi / b.words[b.length - 1]) | 0); | ||
var shift = (a.length - b.length) * 26; | ||
var c = this.clone(); | ||
if (mode === 'mod') { | ||
var r = null; | ||
while (c.cmp(num) >= 0) { | ||
assert(shift >= 0); | ||
if (c.cmp(max) >= 0) | ||
c.isub(max); | ||
var delta = Math.max(1, maxLen - c.bitLength()); | ||
max.ishrn(delta, shift); | ||
maxLen -= delta; | ||
shift -= delta; | ||
if (q) { | ||
var t = sq.shln(shift); | ||
if (a.sign) | ||
q.isub(t); | ||
else | ||
q.iadd(t); | ||
} | ||
} else { | ||
var r = new BN(0); | ||
while (c.cmp(num) >= 0) { | ||
assert(shift >= 0); | ||
if (c.cmp(max) >= 0) { | ||
c.isub(max); | ||
r.bincn(shift); | ||
} | ||
var delta = Math.max(1, maxLen - c.bitLength()); | ||
max.ishrn(delta, shift); | ||
maxLen -= delta; | ||
shift -= delta; | ||
} | ||
sq = sq.mul(b).ishln(shift); | ||
if (a.sign) | ||
a.iadd(sq); | ||
else | ||
a.isub(sq); | ||
} | ||
return { mod: c, div: r }; | ||
if (a.sign) { | ||
if (q) | ||
q.isubn(1); | ||
a.iadd(b); | ||
} | ||
return { div: q ? q : null, mod: a }; | ||
}; | ||
@@ -917,8 +944,18 @@ | ||
// Strip both numbers to approximate shift value | ||
this.strip(); | ||
num.strip(); | ||
if (num.length > this.length || this.cmp(num) < 0) | ||
return { div: new BN(0), mod: this }; | ||
else | ||
return this._shiftDiv(num, mode); | ||
// Very short reduction | ||
if (num.length === 1) { | ||
if (mode === 'div') | ||
return { div: this.divn(num.words[0]), mod: null }; | ||
else if (mode === 'mod') | ||
return { div: null, mod: new BN(this.modn(num.words[0])) }; | ||
return { | ||
div: this.divn(num.words[0]), | ||
mod: new BN(this.modn(num.words[0])) | ||
}; | ||
} | ||
return this._wordDiv(num, mode); | ||
}; | ||
@@ -983,2 +1020,6 @@ | ||
BN.prototype.divn = function divn(num) { | ||
return this.clone().idivn(num); | ||
}; | ||
BN.prototype._egcd = function _egcd(x1, p) { | ||
@@ -1111,10 +1152,16 @@ assert(!p.sign); | ||
this.strip(); | ||
num.strip(); | ||
var res = this.ucmp(num); | ||
if (this.sign) | ||
return -res; | ||
else | ||
return res; | ||
}; | ||
// Unsigned comparison | ||
BN.prototype.ucmp = function ucmp(num) { | ||
// At this point both numbers have the same sign | ||
if (this.length > num.length) | ||
return this.sign ? -1 : 1; | ||
return 1; | ||
else if (this.length < num.length) | ||
return this.sign ? 1 : -1; | ||
return -1; | ||
@@ -1134,6 +1181,3 @@ var res = 0; | ||
} | ||
if (this.sign) | ||
return -res; | ||
else | ||
return res; | ||
return res; | ||
}; | ||
@@ -1289,2 +1333,4 @@ | ||
r.isub(this.p); | ||
} else { | ||
r.strip(); | ||
} | ||
@@ -1291,0 +1337,0 @@ |
{ | ||
"name": "bn.js", | ||
"version": "0.11.4", | ||
"version": "0.11.5", | ||
"description": "Big number implementation in pure javascript", | ||
@@ -5,0 +5,0 @@ "main": "lib/bn.js", |
@@ -176,2 +176,25 @@ var assert = require('assert'); | ||
assert.equal(new BN('1').div(new BN('-5')).toString(10), '0'); | ||
// Regression after moving to word div | ||
var p = new BN( | ||
'ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f', | ||
16); | ||
var a = new BN( | ||
'79be667e f9dcbbac 55a06295 ce870b07 029bfcdb 2dce28d9 59f2815b 16f81798', | ||
16); | ||
var as = a.sqr(); | ||
assert.equal( | ||
as.div(p).toString(16), | ||
'39e58a8055b6fb264b75ec8c646509784204ac15a8c24e05babc9729e58090b9'); | ||
var p = new BN( | ||
'ffffffff00000001000000000000000000000000ffffffffffffffffffffffff', | ||
16); | ||
var a = new BN( | ||
'fffffffe00000003fffffffd0000000200000001fffffffe00000002ffffffff' + | ||
'ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff', | ||
16); | ||
assert.equal( | ||
a.div(p).toString(16), | ||
'ffffffff00000002000000000000000000000001000000000000000000000001'); | ||
}); | ||
@@ -186,2 +209,13 @@ | ||
'1000'); | ||
var p = new BN( | ||
'ffffffff00000001000000000000000000000000ffffffffffffffffffffffff', | ||
16); | ||
var a = new BN( | ||
'fffffffe00000003fffffffd0000000200000001fffffffe00000002ffffffff' + | ||
'ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff', | ||
16); | ||
assert.equal( | ||
a.mod(p).toString(16), | ||
'0'); | ||
}); | ||
@@ -188,0 +222,0 @@ |
Sorry, the diff of this file is not supported yet
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
2511947
1843