X-Git-Url: https://git.immae.eu/?a=blobdiff_plain;f=src%2Fjs%2Fentropy.js;h=3b62e1062a7a1ca89b126b4bd979d28ca80dbf03;hb=bf96267f89d18f278e78cf02c97ab1e7513fb871;hp=8a0c799f549ed4d2ef8b6b75e41592c0a0ef7f8f;hpb=886f06ee6bbca2e6e05109dbd7e264bdea35238f;p=perso%2FImmae%2FProjets%2FCryptomonnaies%2FBIP39.git

diff --git a/src/js/entropy.js b/src/js/entropy.js
index 8a0c799..3b62e10 100644
--- a/src/js/entropy.js
+++ b/src/js/entropy.js
@@ -16,7 +16,136 @@
 
 window.Entropy = new (function() {
 
-    var TWO = new BigInteger(2);
+    let eventBits = {
+
+    "binary": {
+        "0": "0",
+        "1": "1",
+    },
+
+    // log2(6) = 2.58496 bits per roll, with bias
+    // 4 rolls give 2 bits each
+    // 2 rolls give 1 bit each
+    // Average (4*2 + 2*1) / 6 = 1.66 bits per roll without bias
+    "base 6": {
+        "0": "00",
+        "1": "01",
+        "2": "10",
+        "3": "11",
+        "4": "0",
+        "5": "1",
+    },
+
+    // log2(6) = 2.58496 bits per roll, with bias
+    // 4 rolls give 2 bits each
+    // 2 rolls give 1 bit each
+    // Average (4*2 + 2*1) / 6 = 1.66 bits per roll without bias
+    "base 6 (dice)": {
+        "0": "00", // equivalent to 0 in base 6
+        "1": "01",
+        "2": "10",
+        "3": "11",
+        "4": "0",
+        "5": "1",
+    },
+
+    // log2(10) = 3.321928 bits per digit, with bias
+    // 8 digits give 3 bits each
+    // 2 digits give 1 bit each
+    // Average (8*3 + 2*1) / 10 = 2.6 bits per digit without bias
+    "base 10": {
+        "0": "000",
+        "1": "001",
+        "2": "010",
+        "3": "011",
+        "4": "100",
+        "5": "101",
+        "6": "110",
+        "7": "111",
+        "8": "0",
+        "9": "1",
+    },
+
+    "hexadecimal": {
+        "0": "0000",
+        "1": "0001",
+        "2": "0010",
+        "3": "0011",
+        "4": "0100",
+        "5": "0101",
+        "6": "0110",
+        "7": "0111",
+        "8": "1000",
+        "9": "1001",
+        "a": "1010",
+        "b": "1011",
+        "c": "1100",
+        "d": "1101",
+        "e": "1110",
+        "f": "1111",
+    },
+
+    // log2(52) = 5.7004 bits per card, with bias
+    // 32 cards give 5 bits each
+    // 16 cards give 4 bits each
+    // 4 cards give 2 bits each
+    // Average (32*5 + 16*4 + 4*2) / 52 = 4.46 bits per card without bias
+    "card": {
+        "ac": "00000",
+        "2c": "00001",
+        "3c": "00010",
+        "4c": "00011",
+        "5c": "00100",
+        "6c": "00101",
+        "7c": "00110",
+        "8c": "00111",
+        "9c": "01000",
+        "tc": "01001",
+        "jc": "01010",
+        "qc": "01011",
+        "kc": "01100",
+        "ad": "01101",
+        "2d": "01110",
+        "3d": "01111",
+        "4d": "10000",
+        "5d": "10001",
+        "6d": "10010",
+        "7d": "10011",
+        "8d": "10100",
+        "9d": "10101",
+        "td": "10110",
+        "jd": "10111",
+        "qd": "11000",
+        "kd": "11001",
+        "ah": "11010",
+        "2h": "11011",
+        "3h": "11100",
+        "4h": "11101",
+        "5h": "11110",
+        "6h": "11111",
+        "7h": "0000",
+        "8h": "0001",
+        "9h": "0010",
+        "th": "0011",
+        "jh": "0100",
+        "qh": "0101",
+        "kh": "0110",
+        "as": "0111",
+        "2s": "1000",
+        "3s": "1001",
+        "4s": "1010",
+        "5s": "1011",
+        "6s": "1100",
+        "7s": "1101",
+        "8s": "1110",
+        "9s": "1111",
+        "ts": "00",
+        "js": "01",
+        "qs": "10",
+        "ks": "11",
+    },
+
+    }
 
     // matchers returns an array of the matched events for each type of entropy.
     // eg
@@ -51,48 +180,28 @@ window.Entropy = new (function() {
         }
     }
 
-    // Convert array of cards from ["ac", "4d", "ks"]
-    // to numbers between 0 and 51 [0, 16, 51]
-    function convertCardsToInts(cards) {
-        var ints = [];
-        var values = "a23456789tjqk";
-        var suits = "cdhs";
-        for (var i=0; i<cards.length; i++) {
-            var card = cards[i].toLowerCase();
-            var value = card[0];
-            var suit = card[1];
-            var asInt = 13 * suits.indexOf(suit) + values.indexOf(value);
-            ints.push(asInt);
-        }
-        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 newParts = [];
-            var newInts = [];
-            for (var i=0; i<base.parts.length; i++) {
-                var c = base.parts[i];
+            var newEvents = [];
+            for (var i=0; i<base.events.length; i++) {
+                var c = base.events[i];
                 if ("12345".indexOf(c) > -1) {
-                    newParts[i] = base.parts[i];
-                    newInts[i] = base.ints[i];
+                    newEvents[i] = base.events[i];
                 }
                 else {
-                    newParts[i] = "0";
-                    newInts[i] = 0;
+                    newEvents[i] = "0";
                 }
             }
             base.str = "base 6 (dice)";
-            base.ints = newInts;
-            base.parts = newParts;
+            base.events = newEvents;
             base.matcher = matchers.base6;
         }
         // Detect empty entropy
-        if (base.parts.length == 0) {
+        if (base.events.length == 0) {
             return {
                 binaryStr: "",
                 cleanStr: "",
@@ -100,128 +209,23 @@ window.Entropy = new (function() {
                 base: base,
             };
         }
-        // Convert base.ints to BigInteger.
-        // Due to using unusual bases, eg cards of base52, this is not as simple as
-        // using BigInteger.parse()
-        var entropyInt = BigInteger.ZERO;
-        for (var i=base.ints.length-1; i>=0; i--) {
-            var thisInt = BigInteger.parse(base.ints[i]);
-            var power = (base.ints.length - 1) - i;
-            var additionalEntropy = BigInteger.parse(base.asInt).pow(power).multiply(thisInt);
-            entropyInt = entropyInt.add(additionalEntropy);
-        }
-        // 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;
-        }
-        // 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
-        if (base.asInt == 52) {
-            var totalDecks = Math.ceil(base.parts.length / 52);
-            var totalCards = totalDecks * 52;
-            var totalCombos = factorial(52).pow(totalDecks);
-            var totalRemainingCards = totalCards - base.parts.length;
-            var remainingDecks = Math.floor(totalRemainingCards / 52);
-            var remainingCards = totalRemainingCards % 52;
-            var remainingCombos = factorial(52).pow(remainingDecks).multiply(factorial(remainingCards));
-            var currentCombos = totalCombos.divide(remainingCombos);
-            var numberOfBits = Math.log2(currentCombos);
-            var maxWithoutReplace = BigInteger.pow(2, numberOfBits);
-            // Use a bunch of sorted decks to measure entropy from, populated
-            // as needed.
-            var sortedDecks = [];
-            // Initialize the final entropy value for these cards
-            var entropyInt = BigInteger.ZERO;
-            // Track how many instances of each card have been used, and thus
-            // how many decks are in use.
-            var cardCounts = {};
-            // Track the total bits of entropy that remain, which diminishes as
-            // each card is drawn.
-            var totalBitsLeft = numberOfBits;
-            // Work out entropy contribution of each card drawn
-            for (var i=0; i<base.parts.length; i++) {
-                // Get the card that was drawn
-                var cardLower = base.parts[i];
-                var card = cardLower.toUpperCase();
-                // Initialize the deck for this card if needed, to track how
-                // much entropy it adds.
-                if (!(card in cardCounts)) {
-                    cardCounts[card] = 0;
-                }
-                // Get the deck this card is from
-                var deckIndex = cardCounts[card];
-                while (deckIndex > sortedDecks.length-1) {
-                    sortedDecks.push(getSortedDeck());
-                }
-                // See how many bits this card contributes (depends on how many
-                // are left in the deck it's from)
-                var deckForCard = sortedDecks[deckIndex];
-                var cardsLeftInDeck = deckForCard.length;
-                var additionalBits = Math.log2(cardsLeftInDeck);
-                // Work out the min and max value for this card
-                var nextTotalBitsLeft = totalBitsLeft - additionalBits;
-                var minPossibleNewEntropy = TWO.pow(nextTotalBitsLeft).subtract(1);
-                var maxPossibleNewEntropy = TWO.pow(totalBitsLeft).subtract(1);
-                var diff = maxPossibleNewEntropy.subtract(minPossibleNewEntropy);
-                // BigInteger aggresively floors numbers which greatly affects
-                // the small numbers. In that case, use native Math library
-                var useBigInt = totalBitsLeft >= 32;
-                if (!useBigInt) {
-                    minPossibleNewEntropy = Math.round(Math.pow(2, nextTotalBitsLeft)-1);
-                    maxPossibleNewEntropy = Math.round(Math.pow(2, totalBitsLeft)-1);
-                    diff = maxPossibleNewEntropy - minPossibleNewEntropy;
-                }
-                // Scale the value between possible min and max depending on
-                // this card value
-                var thisCardIndex = deckForCard.indexOf(card);
-                var toAdd = BigInteger.ZERO;
-                if (cardsLeftInDeck > 1) {
-                    if (useBigInt) {
-                        toAdd = diff.multiply(thisCardIndex)
-                            .divide(deckForCard.length - 1)
-                            .add(minPossibleNewEntropy);
-                    }
-                    else {
-                        var ratio = thisCardIndex / (deckForCard.length -1);
-                        var f = diff * ratio;
-                        toAdd = new BigInteger(f).add(minPossibleNewEntropy);
-                    }
-                }
-                // Add this card entropy to existing entropy
-                entropyInt = entropyInt.add(toAdd);
-                // Remove this card from the deck it comes from
-                deckForCard.splice(thisCardIndex,1);
-                // Ensure the next insance of this card uses the next deck
-                cardCounts[card] = cardCounts[card] + 1;
-                // Next card drawn has less total remaining bits to work with
-                totalBitsLeft = nextTotalBitsLeft;
-            }
-            // Convert to binary
-            var entropyBin = entropyInt.toString(2);
-            var numberOfBitsInt = Math.floor(numberOfBits);
-            while (entropyBin.length < numberOfBitsInt) {
-                entropyBin = "0" + entropyBin;
-            }
-        }
+        // Convert entropy events to binary
+        var entropyBin = base.events.map(function(e) {
+            return eventBits[base.str][e.toLowerCase()];
+        }).join("");
+        // Get average bits per event
+        // which may be adjusted for bias if log2(base) is fractional
+        var bitsPerEvent = base.bitsPerEvent;
         // Supply a 'filtered' entropy string for display purposes
-        var entropyClean = base.parts.join("");
-        var entropyHtml = base.parts.join("");
+        var entropyClean = base.events.join("");
+        var entropyHtml = base.events.join("");
         if (base.asInt == 52) {
-            entropyClean = base.parts.join(" ").toUpperCase();
+            entropyClean = base.events.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 = base.events.join(" ").toUpperCase();
             entropyHtml = entropyHtml.replace(/C/g, "<span class='card-suit club'>\u2663</span>");
             entropyHtml = entropyHtml.replace(/D/g, "<span class='card-suit diamond'>\u2666</span>");
             entropyHtml = entropyHtml.replace(/H/g, "<span class='card-suit heart'>\u2665</span>");
@@ -232,113 +236,86 @@ window.Entropy = new (function() {
             binaryStr: entropyBin,
             cleanStr: entropyClean,
             cleanHtml: entropyHtml,
+            bitsPerEvent: bitsPerEvent,
             base: base,
         }
         return e;
     }
 
-    function getSortedDeck() {
-        var s = [];
-        var suits = "CDHS";
-        var values = "A23456789TJQK";
-        for (var i=0; i<suits.length; i++) {
-            for (var j=0; j<values.length; j++) {
-                s.push(values[j]+suits[i]);
-            }
-        }
-        return s;
-    }
-
-    function getBase(str) {
+    function getBase(str, baseStr) {
         // Need to get the lowest base for the supplied entropy.
         // This prevents interpreting, say, dice rolls as hexadecimal.
         var binaryMatches = matchers.binary(str);
         var hexMatches = matchers.hex(str);
+        var autodetect = baseStr === undefined;
         // Find the lowest base that can be used, whilst ignoring any irrelevant chars
-        if (binaryMatches.length == hexMatches.length && hexMatches.length > 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,
-                parts: binaryMatches,
+                events: binaryMatches,
                 matcher: matchers.binary,
                 asInt: 2,
+                bitsPerEvent: 1,
                 str: "binary",
             }
         }
         var cardMatches = matchers.card(str);
-        if (cardMatches.length >= hexMatches.length / 2) {
-            var ints = convertCardsToInts(cardMatches);
+        if ((cardMatches.length >= hexMatches.length / 2 && autodetect) || baseStr === "card") {
             return {
                 ints: ints,
-                parts: cardMatches,
+                events: cardMatches,
                 matcher: matchers.card,
                 asInt: 52,
+                bitsPerEvent: (32*5 + 16*4 + 4*2) / 52, // see cardBits
                 str: "card",
             }
         }
         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,
-                parts: diceMatches,
+                events: diceMatches,
                 matcher: matchers.dice,
                 asInt: 6,
+                bitsPerEvent: (4*2 + 2*1) / 6, // see diceBits
                 str: "dice",
             }
         }
         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,
-                parts: base6Matches,
+                events: base6Matches,
                 matcher: matchers.base6,
                 asInt: 6,
+                bitsPerEvent: (4*2 + 2*1) / 6, // see diceBits
                 str: "base 6",
             }
         }
         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,
-                parts: base10Matches,
+                events: base10Matches,
                 matcher: matchers.base10,
                 asInt: 10,
+                bitsPerEvent: (8*3 + 2*1) / 10, // see b10Bits
                 str: "base 10",
             }
         }
         var ints = hexMatches.map(function(i) { return parseInt(i, 16) });
         return {
             ints: ints,
-            parts: hexMatches,
+            events: hexMatches,
             matcher: matchers.hex,
             asInt: 16,
+            bitsPerEvent: 4,
             str: "hexadecimal",
         }
     }
 
-    // Polyfill for Math.log2
-    // See https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/log2#Polyfill
-    Math.log2 = Math.log2 || function(x) {
-        // The polyfill isn't good enough because of the poor accuracy of
-        // Math.LOG2E
-        // log2(8) gave 2.9999999999999996 which when floored causes issues.
-        // So instead use the BigInteger library to get it right.
-        return BigInteger.log(x) / BigInteger.log(2);
-    };
-
-    // Depends on BigInteger
-    function factorial(n) {
-        if (n == 0) {
-            return 1;
-        }
-        f = BigInteger.ONE;
-        for (var i=1; i<=n; i++) {
-            f = f.multiply(new BigInteger(i));
-        }
-        return f;
-    }
-
 })();