| 1 | {"version":3,"file":"rabin.cjs","sources":["../hash/rabin.js"],"sourcesContent":["/**\n * @module rabin\n *\n * Very efficient & versatile fingerprint/hashing algorithm. However, it is not cryptographically\n * secure. Well suited for fingerprinting.\n */\n\nimport * as buffer from '../buffer.js'\nimport * as map from '../map.js'\n\nexport const StandardIrreducible8 = new Uint8Array([1, 221])\nexport const StandardIrreducible16 = new Uint8Array([1, 244, 157])\nexport const StandardIrreducible32 = new Uint8Array([1, 149, 183, 205, 191])\nexport const StandardIrreducible64 = new Uint8Array([1, 133, 250, 114, 193, 250, 28, 193, 231])\nexport const StandardIrreducible128 = new Uint8Array([1, 94, 109, 166, 228, 6, 222, 102, 239, 27, 128, 184, 13, 50, 112, 169, 199])\n\n/**\n * Maps from a modulo to the precomputed values.\n *\n * @type {Map<string,Uint8Array>}\n */\nconst _precomputedFingerprintCache = new Map()\n\n/**\n * @param {Uint8Array} m\n */\nconst ensureCache = m => map.setIfUndefined(_precomputedFingerprintCache, buffer.toBase64(m), () => {\n const byteLen = m.byteLength\n const cache = new Uint8Array(256 * byteLen)\n // Use dynamic computing to compute the cached results.\n // Starting values: cache(0) = 0; cache(1) = m\n cache.set(m, byteLen)\n for (let bit = 1; bit < 8; bit++) {\n const mBitShifted = buffer.shiftNBitsLeft(m, bit)\n const bitShifted = 1 << bit\n for (let j = 0; j < bitShifted; j++) {\n // apply the shifted result (reducing the degree of the polynomial)\n const msb = bitShifted | j\n const rest = msb ^ mBitShifted[0]\n for (let i = 0; i < byteLen; i++) {\n // rest is already precomputed in the cache\n cache[msb * byteLen + i] = cache[rest * byteLen + i] ^ mBitShifted[i]\n }\n // if (cache[(bitShifted | j) * byteLen] !== (bitShifted | j)) { error.unexpectedCase() }\n }\n }\n return cache\n})\n\nexport class RabinEncoder {\n /**\n * @param {Uint8Array} m assert(m[0] === 1)\n */\n constructor (m) {\n this.m = m\n this.blen = m.byteLength\n this.bs = new Uint8Array(this.blen)\n this.cache = ensureCache(m)\n /**\n * This describes the position of the most significant byte (starts with 0 and increases with\n * shift)\n */\n this.bpos = 0\n }\n\n /**\n * @param {number} byte\n */\n write (byte) {\n // assert(this.bs[0] === 0)\n // Shift one byte to the left, add b\n this.bs[this.bpos] = byte\n this.bpos = (this.bpos + 1) % this.blen\n const msb = this.bs[this.bpos]\n for (let i = 0; i < this.blen; i++) {\n this.bs[(this.bpos + i) % this.blen] ^= this.cache[msb * this.blen + i]\n }\n // assert(this.bs[this.bpos] === 0)\n }\n\n getFingerprint () {\n const result = new Uint8Array(this.blen - 1)\n for (let i = 0; i < result.byteLength; i++) {\n result[i] = this.bs[(this.bpos + i + 1) % this.blen]\n }\n return result\n }\n}\n\n/**\n * @param {Uint8Array} irreducible\n * @param {Uint8Array} data\n */\nexport const fingerprint = (irreducible, data) => {\n const encoder = new RabinEncoder(irreducible)\n for (let i = 0; i < data.length; i++) {\n encoder.write(data[i])\n }\n return encoder.getFingerprint()\n}\n"],"names":["map.setIfUndefined","buffer.toBase64","buffer.shiftNBitsLeft"],"mappings":";;;;;;;;;;;;;;;;;;;AAAA;AACA;AACA;AACA;AACA;AACA;AAIA;AACY,MAAC,oBAAoB,GAAG,IAAI,UAAU,CAAC,CAAC,CAAC,EAAE,GAAG,CAAC,EAAC;AAChD,MAAC,qBAAqB,GAAG,IAAI,UAAU,CAAC,CAAC,CAAC,EAAE,GAAG,EAAE,GAAG,CAAC,EAAC;AACtD,MAAC,qBAAqB,GAAG,IAAI,UAAU,CAAC,CAAC,CAAC,EAAE,GAAG,EAAE,GAAG,EAAE,GAAG,EAAE,GAAG,CAAC,EAAC;AAChE,MAAC,qBAAqB,GAAG,IAAI,UAAU,CAAC,CAAC,CAAC,EAAE,GAAG,EAAE,GAAG,EAAE,GAAG,EAAE,GAAG,EAAE,GAAG,EAAE,EAAE,EAAE,GAAG,EAAE,GAAG,CAAC,EAAC;AACnF,MAAC,sBAAsB,GAAG,IAAI,UAAU,CAAC,CAAC,CAAC,EAAE,EAAE,EAAE,GAAG,EAAE,GAAG,EAAE,GAAG,EAAE,CAAC,EAAE,GAAG,EAAE,GAAG,EAAE,GAAG,EAAE,EAAE,EAAE,GAAG,EAAE,GAAG,EAAE,EAAE,EAAE,EAAE,EAAE,GAAG,EAAE,GAAG,EAAE,GAAG,CAAC,EAAC;AACnI;AACA;AACA;AACA;AACA;AACA;AACA,MAAM,4BAA4B,GAAG,IAAI,GAAG,GAAE;AAC9C;AACA;AACA;AACA;AACA,MAAM,WAAW,GAAG,CAAC,IAAIA,kBAAkB,CAAC,4BAA4B,EAAEC,iBAAe,CAAC,CAAC,CAAC,EAAE,MAAM;AACpG,EAAE,MAAM,OAAO,GAAG,CAAC,CAAC,WAAU;AAC9B,EAAE,MAAM,KAAK,GAAG,IAAI,UAAU,CAAC,GAAG,GAAG,OAAO,EAAC;AAC7C;AACA;AACA,EAAE,KAAK,CAAC,GAAG,CAAC,CAAC,EAAE,OAAO,EAAC;AACvB,EAAE,KAAK,IAAI,GAAG,GAAG,CAAC,EAAE,GAAG,GAAG,CAAC,EAAE,GAAG,EAAE,EAAE;AACpC,IAAI,MAAM,WAAW,GAAGC,uBAAqB,CAAC,CAAC,EAAE,GAAG,EAAC;AACrD,IAAI,MAAM,UAAU,GAAG,CAAC,IAAI,IAAG;AAC/B,IAAI,KAAK,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,UAAU,EAAE,CAAC,EAAE,EAAE;AACzC;AACA,MAAM,MAAM,GAAG,GAAG,UAAU,GAAG,EAAC;AAChC,MAAM,MAAM,IAAI,GAAG,GAAG,GAAG,WAAW,CAAC,CAAC,EAAC;AACvC,MAAM,KAAK,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,OAAO,EAAE,CAAC,EAAE,EAAE;AACxC;AACA,QAAQ,KAAK,CAAC,GAAG,GAAG,OAAO,GAAG,CAAC,CAAC,GAAG,KAAK,CAAC,IAAI,GAAG,OAAO,GAAG,CAAC,CAAC,GAAG,WAAW,CAAC,CAAC,EAAC;AAC7E,OAAO;AACP;AACA,KAAK;AACL,GAAG;AACH,EAAE,OAAO,KAAK;AACd,CAAC,EAAC;AACF;AACO,MAAM,YAAY,CAAC;AAC1B;AACA;AACA;AACA,EAAE,WAAW,CAAC,CAAC,CAAC,EAAE;AAClB,IAAI,IAAI,CAAC,CAAC,GAAG,EAAC;AACd,IAAI,IAAI,CAAC,IAAI,GAAG,CAAC,CAAC,WAAU;AAC5B,IAAI,IAAI,CAAC,EAAE,GAAG,IAAI,UAAU,CAAC,IAAI,CAAC,IAAI,EAAC;AACvC,IAAI,IAAI,CAAC,KAAK,GAAG,WAAW,CAAC,CAAC,EAAC;AAC/B;AACA;AACA;AACA;AACA,IAAI,IAAI,CAAC,IAAI,GAAG,EAAC;AACjB,GAAG;AACH;AACA;AACA;AACA;AACA,EAAE,KAAK,CAAC,CAAC,IAAI,EAAE;AACf;AACA;AACA,IAAI,IAAI,CAAC,EAAE,CAAC,IAAI,CAAC,IAAI,CAAC,GAAG,KAAI;AAC7B,IAAI,IAAI,CAAC,IAAI,GAAG,CAAC,IAAI,CAAC,IAAI,GAAG,CAAC,IAAI,IAAI,CAAC,KAAI;AAC3C,IAAI,MAAM,GAAG,GAAG,IAAI,CAAC,EAAE,CAAC,IAAI,CAAC,IAAI,EAAC;AAClC,IAAI,KAAK,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,IAAI,CAAC,IAAI,EAAE,CAAC,EAAE,EAAE;AACxC,MAAM,IAAI,CAAC,EAAE,CAAC,CAAC,IAAI,CAAC,IAAI,GAAG,CAAC,IAAI,IAAI,CAAC,IAAI,CAAC,IAAI,IAAI,CAAC,KAAK,CAAC,GAAG,GAAG,IAAI,CAAC,IAAI,GAAG,CAAC,EAAC;AAC7E,KAAK;AACL;AACA,GAAG;AACH;AACA,EAAE,cAAc,CAAC,GAAG;AACpB,IAAI,MAAM,MAAM,GAAG,IAAI,UAAU,CAAC,IAAI,CAAC,IAAI,GAAG,CAAC,EAAC;AAChD,IAAI,KAAK,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,MAAM,CAAC,UAAU,EAAE,CAAC,EAAE,EAAE;AAChD,MAAM,MAAM,CAAC,CAAC,CAAC,GAAG,IAAI,CAAC,EAAE,CAAC,CAAC,IAAI,CAAC,IAAI,GAAG,CAAC,GAAG,CAAC,IAAI,IAAI,CAAC,IAAI,EAAC;AAC1D,KAAK;AACL,IAAI,OAAO,MAAM;AACjB,GAAG;AACH,CAAC;AACD;AACA;AACA;AACA;AACA;AACY,MAAC,WAAW,GAAG,CAAC,WAAW,EAAE,IAAI,KAAK;AAClD,EAAE,MAAM,OAAO,GAAG,IAAI,YAAY,CAAC,WAAW,EAAC;AAC/C,EAAE,KAAK,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,IAAI,CAAC,MAAM,EAAE,CAAC,EAAE,EAAE;AACxC,IAAI,OAAO,CAAC,KAAK,CAAC,IAAI,CAAC,CAAC,CAAC,EAAC;AAC1B,GAAG;AACH,EAAE,OAAO,OAAO,CAAC,cAAc,EAAE;AACjC;;;;;;;;;;"} |