X-Git-Url: https://git.immae.eu/?p=perso%2FImmae%2FProjets%2FCryptomonnaies%2FBIP39.git;a=blobdiff_plain;f=src%2Fjs%2Fentropy.js;h=62b271125a4939ac8d2249cd9d1508cadf966ae9;hp=92300afa352f27b48a1f600705fe5e04fe1383bc;hb=22f8766947313324c4acda2de4f170475d3c5ded;hpb=adc8ce127d4f8ea0d7e5ede6a82c2791d60ff4d2 diff --git a/src/js/entropy.js b/src/js/entropy.js index 92300af..62b2711 100644 --- a/src/js/entropy.js +++ b/src/js/entropy.js @@ -7,6 +7,7 @@ * dice 6 [1-6] * decimal [0-9] * hexadecimal [0-9A-F] + * card [A2-9TJQK][CDHS] * * Automatically uses lowest entropy to avoid issues such as interpretting 0101 * as hexadecimal which would be 16 bits when really it's only 4 bits of binary @@ -15,6 +16,8 @@ window.Entropy = new (function() { + var TWO = new libs.BigInteger.BigInteger(2); + // matchers returns an array of the matched events for each type of entropy. // eg // matchers.binary("010") returns ["0", "1", "0"] @@ -64,24 +67,28 @@ window.Entropy = new (function() { return ints; } - this.fromString = function(rawEntropyStr) { + this.fromString = function(rawEntropyStr, baseStr) { // Find type of entropy being used (binary, hex, dice etc) - var base = getBase(rawEntropyStr); + var base = getBase(rawEntropyStr, baseStr); // Convert dice to base6 entropy (ie 1-6 to 0-5) + // This is done by changing all 6s to 0s if (base.str == "dice") { - var newRawEntropyStr = ""; - for (var i=0; i -1) { - newRawEntropyStr += (parseInt(c) - 1).toString(); + var newParts = []; + var newInts = []; + for (var i=0; i -1) { + newParts[i] = base.parts[i]; + newInts[i] = base.ints[i]; } else { - newRawEntropyStr += c + newParts[i] = "0"; + newInts[i] = 0; } } - rawEntropyStr = newRawEntropyStr; base.str = "base 6 (dice)"; - base.parts = matchers.base6(rawEntropyStr); + base.ints = newInts; + base.parts = newParts; base.matcher = matchers.base6; } // Detect empty entropy @@ -89,73 +96,84 @@ window.Entropy = new (function() { return { binaryStr: "", cleanStr: "", + cleanHtml: "", base: base, }; } - // Pull leading zeros off - var leadingZeros = []; - while (base.ints[0] == "0") { - leadingZeros.push("0"); - base.ints.shift(); - } - // Convert leading zeros to binary equivalent - var numBinLeadingZeros = Math.floor(Math.log2(base.asInt) * leadingZeros.length); - var binLeadingZeros = ""; - for (var i=0; i=0; i--) { - var thisInt = BigInteger.parse(base.ints[i]); + var thisInt = libs.BigInteger.BigInteger.parse(base.ints[i]); var power = (base.ints.length - 1) - i; - var additionalEntropy = BigInteger.parse(base.asInt).pow(power).multiply(thisInt); + var additionalEntropy = libs.BigInteger.BigInteger.parse(base.asInt).pow(power).multiply(thisInt); entropyInt = entropyInt.add(additionalEntropy); } - // Convert entropy to different formats - var entropyBin = binLeadingZeros + entropyInt.toString(2); + // Convert entropy to binary + var entropyBin = entropyInt.toString(2); + // If the first integer is small, it must be padded with zeros. + // Otherwise the chance of the first bit being 1 is 100%, which is + // obviously incorrect. + // This is not perfect for non-2^n bases. + var expectedBits = Math.floor(base.parts.length * Math.log2(base.asInt)); + while (entropyBin.length < expectedBits) { + entropyBin = "0" + entropyBin; + } + // Calculate the number of bits per event + var bitsPerEvent = Math.log2(base.asInt); + // Cards binary must be handled differently, since they're not replaced + if (base.asInt == 52) { + var cardEntropy = processCardEntropy(base.parts); + entropyBin = cardEntropy.binaryStr; + bitsPerEvent = cardEntropy.bitsPerEvent; + } + // Supply a 'filtered' entropy string for display purposes var entropyClean = base.parts.join(""); + var entropyHtml = base.parts.join(""); + if (base.asInt == 52) { + entropyClean = base.parts.join(" ").toUpperCase(); + entropyClean = entropyClean.replace(/C/g, "\u2663"); + entropyClean = entropyClean.replace(/D/g, "\u2666"); + entropyClean = entropyClean.replace(/H/g, "\u2665"); + entropyClean = entropyClean.replace(/S/g, "\u2660"); + entropyHtml = base.parts.join(" ").toUpperCase(); + entropyHtml = entropyHtml.replace(/C/g, "\u2663"); + entropyHtml = entropyHtml.replace(/D/g, "\u2666"); + entropyHtml = entropyHtml.replace(/H/g, "\u2665"); + entropyHtml = entropyHtml.replace(/S/g, "\u2660"); + } + // Return the result var e = { binaryStr: entropyBin, cleanStr: entropyClean, + cleanHtml: entropyHtml, + bitsPerEvent: bitsPerEvent, base: base, } return e; } - function getBase(str) { + function getSortedDeck() { + var s = []; + var suits = "CDHS"; + var values = "A23456789TJQK"; + for (var i=0; i 0) { + if ((binaryMatches.length == hexMatches.length && hexMatches.length > 0 && autodetect) || baseStr === "binary") { var ints = binaryMatches.map(function(i) { return parseInt(i, 2) }); return { ints: ints, @@ -166,7 +184,7 @@ window.Entropy = new (function() { } } var cardMatches = matchers.card(str); - if (cardMatches.length >= hexMatches.length / 2) { + if ((cardMatches.length >= hexMatches.length / 2 && autodetect) || baseStr === "card") { var ints = convertCardsToInts(cardMatches); return { ints: ints, @@ -177,7 +195,7 @@ window.Entropy = new (function() { } } var diceMatches = matchers.dice(str); - if (diceMatches.length == hexMatches.length && hexMatches.length > 0) { + if ((diceMatches.length == hexMatches.length && hexMatches.length > 0 && autodetect) || baseStr === "dice") { var ints = diceMatches.map(function(i) { return parseInt(i) }); return { ints: ints, @@ -188,7 +206,7 @@ window.Entropy = new (function() { } } var base6Matches = matchers.base6(str); - if (base6Matches.length == hexMatches.length && hexMatches.length > 0) { + if ((base6Matches.length == hexMatches.length && hexMatches.length > 0 && autodetect) || baseStr === "base 6") { var ints = base6Matches.map(function(i) { return parseInt(i) }); return { ints: ints, @@ -199,7 +217,7 @@ window.Entropy = new (function() { } } var base10Matches = matchers.base10(str); - if (base10Matches.length == hexMatches.length && hexMatches.length > 0) { + if ((base10Matches.length == hexMatches.length && hexMatches.length > 0 && autodetect) || baseStr === "base 10") { var ints = base10Matches.map(function(i) { return parseInt(i) }); return { ints: ints, @@ -219,6 +237,90 @@ window.Entropy = new (function() { } } + // Assume cards are NOT replaced. + // Additional entropy decreases as more cards are used. This means + // total possible entropy is measured using n!, not base^n. + // eg the second last card can be only one of two, not one of fifty two + // so the added entropy for that card is only one bit at most + function processCardEntropy(cards) { + // Track how many instances of each card have been used, and thus + // how many decks are in use. + var cardCounts = {}; + var numberOfDecks = 0; + // Work out number of decks by max(duplicates) + for (var i=0; i numberOfDecks) { + numberOfDecks = cardCounts[card]; + } + } + // Work out the total number of bits for this many decks + // See http://crypto.stackexchange.com/q/41886 + var gainedBits = 0; + // Equivalent of Math.log2(factorial(52*numberOfDecks)) + // which becomes infinity for numberOfDecks > 4 + for (var i=1; i<=52*numberOfDecks; i++) { + gainedBits = gainedBits + Math.log2(i); + } + var lostBits = 52 * Math.log2(factorial(numberOfDecks)); + var maxBits = gainedBits - lostBits; + // Convert the drawn cards to a binary representation. + // The exact technique for doing this is unclear. + // See + // http://crypto.stackexchange.com/a/41896 + // "I even doubt that this is well defined (only the average entropy + // is, I believe)." + // See + // https://github.com/iancoleman/bip39/issues/33#issuecomment-263021856 + // "The binary representation can be the first log(permutations,2) bits + // of the sha-2 hash of the normalized deck string." + // + // In this specific implementation, the first N bits of the hash of the + // normalized cards string is being used. Uppercase, no spaces; eg + // sha256("AH8DQSTC2H") + var totalCards = numberOfDecks * 52; + var percentUsed = cards.length / totalCards; + // Calculate the average number of bits of entropy for the number of + // cards drawn. + var numberOfBits = Math.floor(maxBits * percentUsed); + // Create a normalized string of the selected cards + var normalizedCards = cards.join("").toUpperCase(); + // Convert to binary using the SHA256 hash of the normalized cards. + // If the number of bits is more than 256, multiple hashes + // are used until the required number of bits is reached. + var entropyBin = ""; + var iterations = 0; + while (entropyBin.length < numberOfBits) { + var hashedCards = sjcl.hash.sha256.hash(normalizedCards + ":" + iterations); + var hashHex = sjcl.codec.hex.fromBits(hashedCards); + for (var i=0; i - Copyright (c) 2010,2011 by John Tobey - Licensed under the MIT license. - - Support for arbitrary internal representation base was added by - Vitaly Magerya. -*/ - -/* - File: biginteger.js - - Exports: - - -*/ -(function(exports) { -"use strict"; -/* - Class: BigInteger - An arbitrarily-large integer. - - objects should be considered immutable. None of the "built-in" - methods modify *this* or their arguments. All properties should be - considered private. - - All the methods of instances can be called "statically". The - static versions are convenient if you don't already have a - object. - - As an example, these calls are equivalent. - - > BigInteger(4).multiply(5); // returns BigInteger(20); - > BigInteger.multiply(4, 5); // returns BigInteger(20); - - > var a = 42; - > var a = BigInteger.toJSValue("0b101010"); // Not completely useless... -*/ - -var CONSTRUCT = {}; // Unique token to call "private" version of constructor - -/* - Constructor: BigInteger() - Convert a value to a . - - Although is the constructor for objects, it is - best not to call it as a constructor. If *n* is a object, it is - simply returned as-is. Otherwise, is equivalent to - without a radix argument. - - > var n0 = BigInteger(); // Same as - > var n1 = BigInteger("123"); // Create a new with value 123 - > var n2 = BigInteger(123); // Create a new with value 123 - > var n3 = BigInteger(n2); // Return n2, unchanged - - The constructor form only takes an array and a sign. *n* must be an - array of numbers in little-endian order, where each digit is between 0 - and BigInteger.base. The second parameter sets the sign: -1 for - negative, +1 for positive, or 0 for zero. The array is *not copied and - may be modified*. If the array contains only zeros, the sign parameter - is ignored and is forced to zero. - - > new BigInteger([5], -1): create a new BigInteger with value -5 - - Parameters: - - n - Value to convert to a . - - Returns: - - A value. - - See Also: - - , -*/ -function BigInteger(n, s, token) { - if (token !== CONSTRUCT) { - if (n instanceof BigInteger) { - return n; - } - else if (typeof n === "undefined") { - return ZERO; - } - return BigInteger.parse(n); - } - - n = n || []; // Provide the nullary constructor for subclasses. - while (n.length && !n[n.length - 1]) { - --n.length; - } - this._d = n; - this._s = n.length ? (s || 1) : 0; -} - -BigInteger._construct = function(n, s) { - return new BigInteger(n, s, CONSTRUCT); -}; - -// Base-10 speedup hacks in parse, toString, exp10 and log functions -// require base to be a power of 10. 10^7 is the largest such power -// that won't cause a precision loss when digits are multiplied. -var BigInteger_base = 10000000; -var BigInteger_base_log10 = 7; - -BigInteger.base = BigInteger_base; -BigInteger.base_log10 = BigInteger_base_log10; - -var ZERO = new BigInteger([], 0, CONSTRUCT); -// Constant: ZERO -// 0. -BigInteger.ZERO = ZERO; - -var ONE = new BigInteger([1], 1, CONSTRUCT); -// Constant: ONE -// 1. -BigInteger.ONE = ONE; - -var M_ONE = new BigInteger(ONE._d, -1, CONSTRUCT); -// Constant: M_ONE -// -1. -BigInteger.M_ONE = M_ONE; - -// Constant: _0 -// Shortcut for . -BigInteger._0 = ZERO; - -// Constant: _1 -// Shortcut for . -BigInteger._1 = ONE; - -/* - Constant: small - Array of from 0 to 36. - - These are used internally for parsing, but useful when you need a "small" - . - - See Also: - - , , <_0>, <_1> -*/ -BigInteger.small = [ - ZERO, - ONE, - /* Assuming BigInteger_base > 36 */ - new BigInteger( [2], 1, CONSTRUCT), - new BigInteger( [3], 1, CONSTRUCT), - new BigInteger( [4], 1, CONSTRUCT), - new BigInteger( [5], 1, CONSTRUCT), - new BigInteger( [6], 1, CONSTRUCT), - new BigInteger( [7], 1, CONSTRUCT), - new BigInteger( [8], 1, CONSTRUCT), - new BigInteger( [9], 1, CONSTRUCT), - new BigInteger([10], 1, CONSTRUCT), - new BigInteger([11], 1, CONSTRUCT), - new BigInteger([12], 1, CONSTRUCT), - new BigInteger([13], 1, CONSTRUCT), - new BigInteger([14], 1, CONSTRUCT), - new BigInteger([15], 1, CONSTRUCT), - new BigInteger([16], 1, CONSTRUCT), - new BigInteger([17], 1, CONSTRUCT), - new BigInteger([18], 1, CONSTRUCT), - new BigInteger([19], 1, CONSTRUCT), - new BigInteger([20], 1, CONSTRUCT), - new BigInteger([21], 1, CONSTRUCT), - new BigInteger([22], 1, CONSTRUCT), - new BigInteger([23], 1, CONSTRUCT), - new BigInteger([24], 1, CONSTRUCT), - new BigInteger([25], 1, CONSTRUCT), - new BigInteger([26], 1, CONSTRUCT), - new BigInteger([27], 1, CONSTRUCT), - new BigInteger([28], 1, CONSTRUCT), - new BigInteger([29], 1, CONSTRUCT), - new BigInteger([30], 1, CONSTRUCT), - new BigInteger([31], 1, CONSTRUCT), - new BigInteger([32], 1, CONSTRUCT), - new BigInteger([33], 1, CONSTRUCT), - new BigInteger([34], 1, CONSTRUCT), - new BigInteger([35], 1, CONSTRUCT), - new BigInteger([36], 1, CONSTRUCT) -]; - -// Used for parsing/radix conversion -BigInteger.digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ".split(""); - -/* - Method: toString - Convert a to a string. - - When *base* is greater than 10, letters are upper case. - - Parameters: - - base - Optional base to represent the number in (default is base 10). - Must be between 2 and 36 inclusive, or an Error will be thrown. - - Returns: - - The string representation of the . -*/ -BigInteger.prototype.toString = function(base) { - base = +base || 10; - if (base < 2 || base > 36) { - throw new Error("illegal radix " + base + "."); - } - if (this._s === 0) { - return "0"; - } - if (base === 10) { - var str = this._s < 0 ? "-" : ""; - str += this._d[this._d.length - 1].toString(); - for (var i = this._d.length - 2; i >= 0; i--) { - var group = this._d[i].toString(); - while (group.length < BigInteger_base_log10) group = '0' + group; - str += group; - } - return str; - } - else { - var numerals = BigInteger.digits; - base = BigInteger.small[base]; - var sign = this._s; - - var n = this.abs(); - var digits = []; - var digit; - - while (n._s !== 0) { - var divmod = n.divRem(base); - n = divmod[0]; - digit = divmod[1]; - // TODO: This could be changed to unshift instead of reversing at the end. - // Benchmark both to compare speeds. - digits.push(numerals[digit.valueOf()]); - } - return (sign < 0 ? "-" : "") + digits.reverse().join(""); - } -}; - -// Verify strings for parsing -BigInteger.radixRegex = [ - /^$/, - /^$/, - /^[01]*$/, - /^[012]*$/, - /^[0-3]*$/, - /^[0-4]*$/, - /^[0-5]*$/, - /^[0-6]*$/, - /^[0-7]*$/, - /^[0-8]*$/, - /^[0-9]*$/, - /^[0-9aA]*$/, - /^[0-9abAB]*$/, - /^[0-9abcABC]*$/, - /^[0-9a-dA-D]*$/, - /^[0-9a-eA-E]*$/, - /^[0-9a-fA-F]*$/, - /^[0-9a-gA-G]*$/, - /^[0-9a-hA-H]*$/, - /^[0-9a-iA-I]*$/, - /^[0-9a-jA-J]*$/, - /^[0-9a-kA-K]*$/, - /^[0-9a-lA-L]*$/, - /^[0-9a-mA-M]*$/, - /^[0-9a-nA-N]*$/, - /^[0-9a-oA-O]*$/, - /^[0-9a-pA-P]*$/, - /^[0-9a-qA-Q]*$/, - /^[0-9a-rA-R]*$/, - /^[0-9a-sA-S]*$/, - /^[0-9a-tA-T]*$/, - /^[0-9a-uA-U]*$/, - /^[0-9a-vA-V]*$/, - /^[0-9a-wA-W]*$/, - /^[0-9a-xA-X]*$/, - /^[0-9a-yA-Y]*$/, - /^[0-9a-zA-Z]*$/ -]; - -/* - Function: parse - Parse a string into a . - - *base* is optional but, if provided, must be from 2 to 36 inclusive. If - *base* is not provided, it will be guessed based on the leading characters - of *s* as follows: - - - "0x" or "0X": *base* = 16 - - "0c" or "0C": *base* = 8 - - "0b" or "0B": *base* = 2 - - else: *base* = 10 - - If no base is provided, or *base* is 10, the number can be in exponential - form. For example, these are all valid: - - > BigInteger.parse("1e9"); // Same as "1000000000" - > BigInteger.parse("1.234*10^3"); // Same as 1234 - > BigInteger.parse("56789 * 10 ** -2"); // Same as 567 - - If any characters fall outside the range defined by the radix, an exception - will be thrown. - - Parameters: - - s - The string to parse. - base - Optional radix (default is to guess based on *s*). - - Returns: - - a instance. -*/ -BigInteger.parse = function(s, base) { - // Expands a number in exponential form to decimal form. - // expandExponential("-13.441*10^5") === "1344100"; - // expandExponential("1.12300e-1") === "0.112300"; - // expandExponential(1000000000000000000000000000000) === "1000000000000000000000000000000"; - function expandExponential(str) { - str = str.replace(/\s*[*xX]\s*10\s*(\^|\*\*)\s*/, "e"); - - return str.replace(/^([+\-])?(\d+)\.?(\d*)[eE]([+\-]?\d+)$/, function(x, s, n, f, c) { - c = +c; - var l = c < 0; - var i = n.length + c; - x = (l ? n : f).length; - c = ((c = Math.abs(c)) >= x ? c - x + l : 0); - var z = (new Array(c + 1)).join("0"); - var r = n + f; - return (s || "") + (l ? r = z + r : r += z).substr(0, i += l ? z.length : 0) + (i < r.length ? "." + r.substr(i) : ""); - }); - } - - s = s.toString(); - if (typeof base === "undefined" || +base === 10) { - s = expandExponential(s); - } - - var prefixRE; - if (typeof base === "undefined") { - prefixRE = '0[xcb]'; - } - else if (base == 16) { - prefixRE = '0x'; - } - else if (base == 8) { - prefixRE = '0c'; - } - else if (base == 2) { - prefixRE = '0b'; - } - else { - prefixRE = ''; - } - var parts = new RegExp('^([+\\-]?)(' + prefixRE + ')?([0-9a-z]*)(?:\\.\\d*)?$', 'i').exec(s); - if (parts) { - var sign = parts[1] || "+"; - var baseSection = parts[2] || ""; - var digits = parts[3] || ""; - - if (typeof base === "undefined") { - // Guess base - if (baseSection === "0x" || baseSection === "0X") { // Hex - base = 16; - } - else if (baseSection === "0c" || baseSection === "0C") { // Octal - base = 8; - } - else if (baseSection === "0b" || baseSection === "0B") { // Binary - base = 2; - } - else { - base = 10; - } - } - else if (base < 2 || base > 36) { - throw new Error("Illegal radix " + base + "."); - } - - base = +base; - - // Check for digits outside the range - if (!(BigInteger.radixRegex[base].test(digits))) { - throw new Error("Bad digit for radix " + base); - } - - // Strip leading zeros, and convert to array - digits = digits.replace(/^0+/, "").split(""); - if (digits.length === 0) { - return ZERO; - } - - // Get the sign (we know it's not zero) - sign = (sign === "-") ? -1 : 1; - - // Optimize 10 - if (base == 10) { - var d = []; - while (digits.length >= BigInteger_base_log10) { - d.push(parseInt(digits.splice(digits.length-BigInteger.base_log10, BigInteger.base_log10).join(''), 10)); - } - d.push(parseInt(digits.join(''), 10)); - return new BigInteger(d, sign, CONSTRUCT); - } - - // Do the conversion - var d = ZERO; - base = BigInteger.small[base]; - var small = BigInteger.small; - for (var i = 0; i < digits.length; i++) { - d = d.multiply(base).add(small[parseInt(digits[i], 36)]); - } - return new BigInteger(d._d, sign, CONSTRUCT); - } - else { - throw new Error("Invalid BigInteger format: " + s); - } -}; - -/* - Function: add - Add two . - - Parameters: - - n - The number to add to *this*. Will be converted to a . - - Returns: - - The numbers added together. - - See Also: - - , , , -*/ -BigInteger.prototype.add = function(n) { - if (this._s === 0) { - return BigInteger(n); - } - - n = BigInteger(n); - if (n._s === 0) { - return this; - } - if (this._s !== n._s) { - n = n.negate(); - return this.subtract(n); - } - - var a = this._d; - var b = n._d; - var al = a.length; - var bl = b.length; - var sum = new Array(Math.max(al, bl) + 1); - var size = Math.min(al, bl); - var carry = 0; - var digit; - - for (var i = 0; i < size; i++) { - digit = a[i] + b[i] + carry; - sum[i] = digit % BigInteger_base; - carry = (digit / BigInteger_base) | 0; - } - if (bl > al) { - a = b; - al = bl; - } - for (i = size; carry && i < al; i++) { - digit = a[i] + carry; - sum[i] = digit % BigInteger_base; - carry = (digit / BigInteger_base) | 0; - } - if (carry) { - sum[i] = carry; - } - - for ( ; i < al; i++) { - sum[i] = a[i]; - } - - return new BigInteger(sum, this._s, CONSTRUCT); -}; - -/* - Function: negate - Get the additive inverse of a . - - Returns: - - A with the same magnatude, but with the opposite sign. - - See Also: - - -*/ -BigInteger.prototype.negate = function() { - return new BigInteger(this._d, (-this._s) | 0, CONSTRUCT); -}; - -/* - Function: abs - Get the absolute value of a . - - Returns: - - A with the same magnatude, but always positive (or zero). - - See Also: - - -*/ -BigInteger.prototype.abs = function() { - return (this._s < 0) ? this.negate() : this; -}; - -/* - Function: subtract - Subtract two . - - Parameters: - - n - The number to subtract from *this*. Will be converted to a . - - Returns: - - The *n* subtracted from *this*. - - See Also: - - , , , -*/ -BigInteger.prototype.subtract = function(n) { - if (this._s === 0) { - return BigInteger(n).negate(); - } - - n = BigInteger(n); - if (n._s === 0) { - return this; - } - if (this._s !== n._s) { - n = n.negate(); - return this.add(n); - } - - var m = this; - // negative - negative => -|a| - -|b| => -|a| + |b| => |b| - |a| - if (this._s < 0) { - m = new BigInteger(n._d, 1, CONSTRUCT); - n = new BigInteger(this._d, 1, CONSTRUCT); - } - - // Both are positive => a - b - var sign = m.compareAbs(n); - if (sign === 0) { - return ZERO; - } - else if (sign < 0) { - // swap m and n - var t = n; - n = m; - m = t; - } - - // a > b - var a = m._d; - var b = n._d; - var al = a.length; - var bl = b.length; - var diff = new Array(al); // al >= bl since a > b - var borrow = 0; - var i; - var digit; - - for (i = 0; i < bl; i++) { - digit = a[i] - borrow - b[i]; - if (digit < 0) { - digit += BigInteger_base; - borrow = 1; - } - else { - borrow = 0; - } - diff[i] = digit; - } - for (i = bl; i < al; i++) { - digit = a[i] - borrow; - if (digit < 0) { - digit += BigInteger_base; - } - else { - diff[i++] = digit; - break; - } - diff[i] = digit; - } - for ( ; i < al; i++) { - diff[i] = a[i]; - } - - return new BigInteger(diff, sign, CONSTRUCT); -}; - -(function() { - function addOne(n, sign) { - var a = n._d; - var sum = a.slice(); - var carry = true; - var i = 0; - - while (true) { - var digit = (a[i] || 0) + 1; - sum[i] = digit % BigInteger_base; - if (digit <= BigInteger_base - 1) { - break; - } - ++i; - } - - return new BigInteger(sum, sign, CONSTRUCT); - } - - function subtractOne(n, sign) { - var a = n._d; - var sum = a.slice(); - var borrow = true; - var i = 0; - - while (true) { - var digit = (a[i] || 0) - 1; - if (digit < 0) { - sum[i] = digit + BigInteger_base; - } - else { - sum[i] = digit; - break; - } - ++i; - } - - return new BigInteger(sum, sign, CONSTRUCT); - } - - /* - Function: next - Get the next (add one). - - Returns: - - *this* + 1. - - See Also: - - , - */ - BigInteger.prototype.next = function() { - switch (this._s) { - case 0: - return ONE; - case -1: - return subtractOne(this, -1); - // case 1: - default: - return addOne(this, 1); - } - }; - - /* - Function: prev - Get the previous (subtract one). - - Returns: - - *this* - 1. - - See Also: - - , - */ - BigInteger.prototype.prev = function() { - switch (this._s) { - case 0: - return M_ONE; - case -1: - return addOne(this, -1); - // case 1: - default: - return subtractOne(this, 1); - } - }; -})(); - -/* - Function: compareAbs - Compare the absolute value of two . - - Calling is faster than calling twice, then . - - Parameters: - - n - The number to compare to *this*. Will be converted to a . - - Returns: - - -1, 0, or +1 if *|this|* is less than, equal to, or greater than *|n|*. - - See Also: - - , -*/ -BigInteger.prototype.compareAbs = function(n) { - if (this === n) { - return 0; - } - - if (!(n instanceof BigInteger)) { - if (!isFinite(n)) { - return(isNaN(n) ? n : -1); - } - n = BigInteger(n); - } - - if (this._s === 0) { - return (n._s !== 0) ? -1 : 0; - } - if (n._s === 0) { - return 1; - } - - var l = this._d.length; - var nl = n._d.length; - if (l < nl) { - return -1; - } - else if (l > nl) { - return 1; - } - - var a = this._d; - var b = n._d; - for (var i = l-1; i >= 0; i--) { - if (a[i] !== b[i]) { - return a[i] < b[i] ? -1 : 1; - } - } - - return 0; -}; - -/* - Function: compare - Compare two . - - Parameters: - - n - The number to compare to *this*. Will be converted to a . - - Returns: - - -1, 0, or +1 if *this* is less than, equal to, or greater than *n*. - - See Also: - - , , , -*/ -BigInteger.prototype.compare = function(n) { - if (this === n) { - return 0; - } - - n = BigInteger(n); - - if (this._s === 0) { - return -n._s; - } - - if (this._s === n._s) { // both positive or both negative - var cmp = this.compareAbs(n); - return cmp * this._s; - } - else { - return this._s; - } -}; - -/* - Function: isUnit - Return true iff *this* is either 1 or -1. - - Returns: - - true if *this* compares equal to or . - - See Also: - - , , , , , - , -*/ -BigInteger.prototype.isUnit = function() { - return this === ONE || - this === M_ONE || - (this._d.length === 1 && this._d[0] === 1); -}; - -/* - Function: multiply - Multiply two . - - Parameters: - - n - The number to multiply *this* by. Will be converted to a - . - - Returns: - - The numbers multiplied together. - - See Also: - - , , , -*/ -BigInteger.prototype.multiply = function(n) { - // TODO: Consider adding Karatsuba multiplication for large numbers - if (this._s === 0) { - return ZERO; - } - - n = BigInteger(n); - if (n._s === 0) { - return ZERO; - } - if (this.isUnit()) { - if (this._s < 0) { - return n.negate(); - } - return n; - } - if (n.isUnit()) { - if (n._s < 0) { - return this.negate(); - } - return this; - } - if (this === n) { - return this.square(); - } - - var r = (this._d.length >= n._d.length); - var a = (r ? this : n)._d; // a will be longer than b - var b = (r ? n : this)._d; - var al = a.length; - var bl = b.length; - - var pl = al + bl; - var partial = new Array(pl); - var i; - for (i = 0; i < pl; i++) { - partial[i] = 0; - } - - for (i = 0; i < bl; i++) { - var carry = 0; - var bi = b[i]; - var jlimit = al + i; - var digit; - for (var j = i; j < jlimit; j++) { - digit = partial[j] + bi * a[j - i] + carry; - carry = (digit / BigInteger_base) | 0; - partial[j] = (digit % BigInteger_base) | 0; - } - if (carry) { - digit = partial[j] + carry; - carry = (digit / BigInteger_base) | 0; - partial[j] = digit % BigInteger_base; - } - } - return new BigInteger(partial, this._s * n._s, CONSTRUCT); -}; - -// Multiply a BigInteger by a single-digit native number -// Assumes that this and n are >= 0 -// This is not really intended to be used outside the library itself -BigInteger.prototype.multiplySingleDigit = function(n) { - if (n === 0 || this._s === 0) { - return ZERO; - } - if (n === 1) { - return this; - } - - var digit; - if (this._d.length === 1) { - digit = this._d[0] * n; - if (digit >= BigInteger_base) { - return new BigInteger([(digit % BigInteger_base)|0, - (digit / BigInteger_base)|0], 1, CONSTRUCT); - } - return new BigInteger([digit], 1, CONSTRUCT); - } - - if (n === 2) { - return this.add(this); - } - if (this.isUnit()) { - return new BigInteger([n], 1, CONSTRUCT); - } - - var a = this._d; - var al = a.length; - - var pl = al + 1; - var partial = new Array(pl); - for (var i = 0; i < pl; i++) { - partial[i] = 0; - } - - var carry = 0; - for (var j = 0; j < al; j++) { - digit = n * a[j] + carry; - carry = (digit / BigInteger_base) | 0; - partial[j] = (digit % BigInteger_base) | 0; - } - if (carry) { - partial[j] = carry; - } - - return new BigInteger(partial, 1, CONSTRUCT); -}; - -/* - Function: square - Multiply a by itself. - - This is slightly faster than regular multiplication, since it removes the - duplicated multiplcations. - - Returns: - - > this.multiply(this) - - See Also: - -*/ -BigInteger.prototype.square = function() { - // Normally, squaring a 10-digit number would take 100 multiplications. - // Of these 10 are unique diagonals, of the remaining 90 (100-10), 45 are repeated. - // This procedure saves (N*(N-1))/2 multiplications, (e.g., 45 of 100 multiplies). - // Based on code by Gary Darby, Intellitech Systems Inc., www.DelphiForFun.org - - if (this._s === 0) { - return ZERO; - } - if (this.isUnit()) { - return ONE; - } - - var digits = this._d; - var length = digits.length; - var imult1 = new Array(length + length + 1); - var product, carry, k; - var i; - - // Calculate diagonal - for (i = 0; i < length; i++) { - k = i * 2; - product = digits[i] * digits[i]; - carry = (product / BigInteger_base) | 0; - imult1[k] = product % BigInteger_base; - imult1[k + 1] = carry; - } - - // Calculate repeating part - for (i = 0; i < length; i++) { - carry = 0; - k = i * 2 + 1; - for (var j = i + 1; j < length; j++, k++) { - product = digits[j] * digits[i] * 2 + imult1[k] + carry; - carry = (product / BigInteger_base) | 0; - imult1[k] = product % BigInteger_base; - } - k = length + i; - var digit = carry + imult1[k]; - carry = (digit / BigInteger_base) | 0; - imult1[k] = digit % BigInteger_base; - imult1[k + 1] += carry; - } - - return new BigInteger(imult1, 1, CONSTRUCT); -}; - -/* - Function: quotient - Divide two and truncate towards zero. - - throws an exception if *n* is zero. - - Parameters: - - n - The number to divide *this* by. Will be converted to a . - - Returns: - - The *this* / *n*, truncated to an integer. - - See Also: - - , , , , -*/ -BigInteger.prototype.quotient = function(n) { - return this.divRem(n)[0]; -}; - -/* - Function: divide - Deprecated synonym for . -*/ -BigInteger.prototype.divide = BigInteger.prototype.quotient; - -/* - Function: remainder - Calculate the remainder of two . - - throws an exception if *n* is zero. - - Parameters: - - n - The remainder after *this* is divided *this* by *n*. Will be - converted to a . - - Returns: - - *this* % *n*. - - See Also: - - , -*/ -BigInteger.prototype.remainder = function(n) { - return this.divRem(n)[1]; -}; - -/* - Function: divRem - Calculate the integer quotient and remainder of two . - - throws an exception if *n* is zero. - - Parameters: - - n - The number to divide *this* by. Will be converted to a . - - Returns: - - A two-element array containing the quotient and the remainder. - - > a.divRem(b) - - is exactly equivalent to - - > [a.quotient(b), a.remainder(b)] - - except it is faster, because they are calculated at the same time. - - See Also: - - , -*/ -BigInteger.prototype.divRem = function(n) { - n = BigInteger(n); - if (n._s === 0) { - throw new Error("Divide by zero"); - } - if (this._s === 0) { - return [ZERO, ZERO]; - } - if (n._d.length === 1) { - return this.divRemSmall(n._s * n._d[0]); - } - - // Test for easy cases -- |n1| <= |n2| - switch (this.compareAbs(n)) { - case 0: // n1 == n2 - return [this._s === n._s ? ONE : M_ONE, ZERO]; - case -1: // |n1| < |n2| - return [ZERO, this]; - } - - var sign = this._s * n._s; - var a = n.abs(); - var b_digits = this._d; - var b_index = b_digits.length; - var digits = n._d.length; - var quot = []; - var guess; - - var part = new BigInteger([], 0, CONSTRUCT); - - while (b_index) { - part._d.unshift(b_digits[--b_index]); - part = new BigInteger(part._d, 1, CONSTRUCT); - - if (part.compareAbs(n) < 0) { - quot.push(0); - continue; - } - if (part._s === 0) { - guess = 0; - } - else { - var xlen = part._d.length, ylen = a._d.length; - var highx = part._d[xlen-1]*BigInteger_base + part._d[xlen-2]; - var highy = a._d[ylen-1]*BigInteger_base + a._d[ylen-2]; - if (part._d.length > a._d.length) { - // The length of part._d can either match a._d length, - // or exceed it by one. - highx = (highx+1)*BigInteger_base; - } - guess = Math.ceil(highx/highy); - } - do { - var check = a.multiplySingleDigit(guess); - if (check.compareAbs(part) <= 0) { - break; - } - guess--; - } while (guess); - - quot.push(guess); - if (!guess) { - continue; - } - var diff = part.subtract(check); - part._d = diff._d.slice(); - } - - return [new BigInteger(quot.reverse(), sign, CONSTRUCT), - new BigInteger(part._d, this._s, CONSTRUCT)]; -}; - -// Throws an exception if n is outside of (-BigInteger.base, -1] or -// [1, BigInteger.base). It's not necessary to call this, since the -// other division functions will call it if they are able to. -BigInteger.prototype.divRemSmall = function(n) { - var r; - n = +n; - if (n === 0) { - throw new Error("Divide by zero"); - } - - var n_s = n < 0 ? -1 : 1; - var sign = this._s * n_s; - n = Math.abs(n); - - if (n < 1 || n >= BigInteger_base) { - throw new Error("Argument out of range"); - } - - if (this._s === 0) { - return [ZERO, ZERO]; - } - - if (n === 1 || n === -1) { - return [(sign === 1) ? this.abs() : new BigInteger(this._d, sign, CONSTRUCT), ZERO]; - } - - // 2 <= n < BigInteger_base - - // divide a single digit by a single digit - if (this._d.length === 1) { - var q = new BigInteger([(this._d[0] / n) | 0], 1, CONSTRUCT); - r = new BigInteger([(this._d[0] % n) | 0], 1, CONSTRUCT); - if (sign < 0) { - q = q.negate(); - } - if (this._s < 0) { - r = r.negate(); - } - return [q, r]; - } - - var digits = this._d.slice(); - var quot = new Array(digits.length); - var part = 0; - var diff = 0; - var i = 0; - var guess; - - while (digits.length) { - part = part * BigInteger_base + digits[digits.length - 1]; - if (part < n) { - quot[i++] = 0; - digits.pop(); - diff = BigInteger_base * diff + part; - continue; - } - if (part === 0) { - guess = 0; - } - else { - guess = (part / n) | 0; - } - - var check = n * guess; - diff = part - check; - quot[i++] = guess; - if (!guess) { - digits.pop(); - continue; - } - - digits.pop(); - part = diff; - } - - r = new BigInteger([diff], 1, CONSTRUCT); - if (this._s < 0) { - r = r.negate(); - } - return [new BigInteger(quot.reverse(), sign, CONSTRUCT), r]; -}; - -/* - Function: isEven - Return true iff *this* is divisible by two. - - Note that is even. - - Returns: - - true if *this* is even, false otherwise. - - See Also: - - -*/ -BigInteger.prototype.isEven = function() { - var digits = this._d; - return this._s === 0 || digits.length === 0 || (digits[0] % 2) === 0; -}; - -/* - Function: isOdd - Return true iff *this* is not divisible by two. - - Returns: - - true if *this* is odd, false otherwise. - - See Also: - - -*/ -BigInteger.prototype.isOdd = function() { - return !this.isEven(); -}; - -/* - Function: sign - Get the sign of a . - - Returns: - - * -1 if *this* < 0 - * 0 if *this* == 0 - * +1 if *this* > 0 - - See Also: - - , , , , -*/ -BigInteger.prototype.sign = function() { - return this._s; -}; - -/* - Function: isPositive - Return true iff *this* > 0. - - Returns: - - true if *this*.compare() == 1. - - See Also: - - , , , , , -*/ -BigInteger.prototype.isPositive = function() { - return this._s > 0; -}; - -/* - Function: isNegative - Return true iff *this* < 0. - - Returns: - - true if *this*.compare() == -1. - - See Also: - - , , , , , -*/ -BigInteger.prototype.isNegative = function() { - return this._s < 0; -}; - -/* - Function: isZero - Return true iff *this* == 0. - - Returns: - - true if *this*.compare() == 0. - - See Also: - - , , , , -*/ -BigInteger.prototype.isZero = function() { - return this._s === 0; -}; - -/* - Function: exp10 - Multiply a by a power of 10. - - This is equivalent to, but faster than - - > if (n >= 0) { - > return this.multiply(BigInteger("1e" + n)); - > } - > else { // n <= 0 - > return this.quotient(BigInteger("1e" + -n)); - > } - - Parameters: - - n - The power of 10 to multiply *this* by. *n* is converted to a - javascipt number and must be no greater than - (0x7FFFFFFF), or an exception will be thrown. - - Returns: - - *this* * (10 ** *n*), truncated to an integer if necessary. - - See Also: - - , -*/ -BigInteger.prototype.exp10 = function(n) { - n = +n; - if (n === 0) { - return this; - } - if (Math.abs(n) > Number(MAX_EXP)) { - throw new Error("exponent too large in BigInteger.exp10"); - } - // Optimization for this == 0. This also keeps us from having to trim zeros in the positive n case - if (this._s === 0) { - return ZERO; - } - if (n > 0) { - var k = new BigInteger(this._d.slice(), this._s, CONSTRUCT); - - for (; n >= BigInteger_base_log10; n -= BigInteger_base_log10) { - k._d.unshift(0); - } - if (n == 0) - return k; - k._s = 1; - k = k.multiplySingleDigit(Math.pow(10, n)); - return (this._s < 0 ? k.negate() : k); - } else if (-n >= this._d.length*BigInteger_base_log10) { - return ZERO; - } else { - var k = new BigInteger(this._d.slice(), this._s, CONSTRUCT); - - for (n = -n; n >= BigInteger_base_log10; n -= BigInteger_base_log10) { - k._d.shift(); - } - return (n == 0) ? k : k.divRemSmall(Math.pow(10, n))[0]; - } -}; - -/* - Function: pow - Raise a to a power. - - In this implementation, 0**0 is 1. - - Parameters: - - n - The exponent to raise *this* by. *n* must be no greater than - (0x7FFFFFFF), or an exception will be thrown. - - Returns: - - *this* raised to the *nth* power. - - See Also: - - -*/ -BigInteger.prototype.pow = function(n) { - if (this.isUnit()) { - if (this._s > 0) { - return this; - } - else { - return BigInteger(n).isOdd() ? this : this.negate(); - } - } - - n = BigInteger(n); - if (n._s === 0) { - return ONE; - } - else if (n._s < 0) { - if (this._s === 0) { - throw new Error("Divide by zero"); - } - else { - return ZERO; - } - } - if (this._s === 0) { - return ZERO; - } - if (n.isUnit()) { - return this; - } - - if (n.compareAbs(MAX_EXP) > 0) { - throw new Error("exponent too large in BigInteger.pow"); - } - var x = this; - var aux = ONE; - var two = BigInteger.small[2]; - - while (n.isPositive()) { - if (n.isOdd()) { - aux = aux.multiply(x); - if (n.isUnit()) { - return aux; - } - } - x = x.square(); - n = n.quotient(two); - } - - return aux; -}; - -/* - Function: modPow - Raise a to a power (mod m). - - Because it is reduced by a modulus, is not limited by - like . - - Parameters: - - exponent - The exponent to raise *this* by. Must be positive. - modulus - The modulus. - - Returns: - - *this* ^ *exponent* (mod *modulus*). - - See Also: - - , -*/ -BigInteger.prototype.modPow = function(exponent, modulus) { - var result = ONE; - var base = this; - - while (exponent.isPositive()) { - if (exponent.isOdd()) { - result = result.multiply(base).remainder(modulus); - } - - exponent = exponent.quotient(BigInteger.small[2]); - if (exponent.isPositive()) { - base = base.square().remainder(modulus); - } - } - - return result; -}; - -/* - Function: log - Get the natural logarithm of a as a native JavaScript number. - - This is equivalent to - - > Math.log(this.toJSValue()) - - but handles values outside of the native number range. - - Returns: - - log( *this* ) - - See Also: - - -*/ -BigInteger.prototype.log = function() { - switch (this._s) { - case 0: return -Infinity; - case -1: return NaN; - default: // Fall through. - } - - var l = this._d.length; - - if (l*BigInteger_base_log10 < 30) { - return Math.log(this.valueOf()); - } - - var N = Math.ceil(30/BigInteger_base_log10); - var firstNdigits = this._d.slice(l - N); - return Math.log((new BigInteger(firstNdigits, 1, CONSTRUCT)).valueOf()) + (l - N) * Math.log(BigInteger_base); -}; - -/* - Function: valueOf - Convert a to a native JavaScript integer. - - This is called automatically by JavaScipt to convert a to a - native value. - - Returns: - - > parseInt(this.toString(), 10) - - See Also: - - , -*/ -BigInteger.prototype.valueOf = function() { - return parseInt(this.toString(), 10); -}; - -/* - Function: toJSValue - Convert a to a native JavaScript integer. - - This is the same as valueOf, but more explicitly named. - - Returns: - - > parseInt(this.toString(), 10) - - See Also: - - , -*/ -BigInteger.prototype.toJSValue = function() { - return parseInt(this.toString(), 10); -}; - -var MAX_EXP = BigInteger(0x7FFFFFFF); -// Constant: MAX_EXP -// The largest exponent allowed in and (0x7FFFFFFF or 2147483647). -BigInteger.MAX_EXP = MAX_EXP; - -(function() { - function makeUnary(fn) { - return function(a) { - return fn.call(BigInteger(a)); - }; - } - - function makeBinary(fn) { - return function(a, b) { - return fn.call(BigInteger(a), BigInteger(b)); - }; - } - - function makeTrinary(fn) { - return function(a, b, c) { - return fn.call(BigInteger(a), BigInteger(b), BigInteger(c)); - }; - } - - (function() { - var i, fn; - var unary = "toJSValue,isEven,isOdd,sign,isZero,isNegative,abs,isUnit,square,negate,isPositive,toString,next,prev,log".split(","); - var binary = "compare,remainder,divRem,subtract,add,quotient,divide,multiply,pow,compareAbs".split(","); - var trinary = ["modPow"]; - - for (i = 0; i < unary.length; i++) { - fn = unary[i]; - BigInteger[fn] = makeUnary(BigInteger.prototype[fn]); - } - - for (i = 0; i < binary.length; i++) { - fn = binary[i]; - BigInteger[fn] = makeBinary(BigInteger.prototype[fn]); - } - - for (i = 0; i < trinary.length; i++) { - fn = trinary[i]; - BigInteger[fn] = makeTrinary(BigInteger.prototype[fn]); - } + // Depends on BigInteger + function factorial(n) { + if (n == 0) { + return 1; + } + f = libs.BigInteger.BigInteger.ONE; + for (var i=1; i<=n; i++) { + f = f.multiply(new libs.BigInteger.BigInteger(i)); + } + return f; + } - BigInteger.exp10 = function(x, n) { - return BigInteger(x).exp10(n); - }; - })(); })(); - -exports.BigInteger = BigInteger; -})(typeof exports !== 'undefined' ? exports : this);