Skip to content

Instantly share code, notes, and snippets.

@josephrocca

josephrocca/BigMap.mjs

Last active June 10, 2019 16:49
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save josephrocca/019f091e5f83e410533caeb6f371200e to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save josephrocca/019f091e5f83e410533caeb6f371200e to your computer and use it in GitHub Desktop.
Download ZIP
BigMap.js
Raw
aaa.md

A browserified version of @ronomon's hash-table library. Packaged up with @feross's buffer lib (accessible at HashTable.Buffer). I've also included "BigMap.mjs" which is supposed to be an almost-drop-in replacement for the built-in Map for when you need to store many GBs of data. The delete() method and some other stuff isn't implemented yet though. See @ronomon/hash-table/README.md for more details:

https://github.com/ronomon/hash-table

Raw
BigMap.mjs
// This is very "hacked together" - not properly bug/security tested or anything.
// Slower than using @ronomon/hash-table directly, but still faster
// than V8 for strings right now: https://bugs.chromium.org/p/v8/issues/detail?id=9348
// and doesn't cause crash when memory usage pushes into dozens
// of GB: https://bugs.chromium.org/p/v8/issues/detail?id=9350
// You need to pass trackKeys:true into the constructor options argument object
// if you want to use map.keys() or the other iterators.
import HashTable from "./HashTable.mjs";
const Buffer = HashTable.Buffer;
// For some reason HashTable doesn't allow keys smaller than 4 bytes so
// I'm just disabling support for number types that are smaller than 4
// bytes for now:
const numberTypeToBufferMethodNameMap = {
// "uint8":"UInt8",
// "uint16":"UInt16BE",
"uint32":"UInt32BE",
"uint64":"BigUInt64BE",
// "int8":"Int8",
// "int16":"Int16BE",
"int32":"Int32BE",
"int64":"BigInt64BE",
"float32":"Float",
"float64":"Double",
};
const numberTypeToSizeMap = {
// "uint8":1,
// "uint16":2,
"uint32":4,
"uint64":8,
// "int8":1,
// "int16":2,
"int32":4,
"int64":8,
"float32":4,
"float64":8,
};
export default class BigMap {
constructor(startingEntries, {keyType, keySize, valueType, valueSize, trackKeys, elementsMin, elementsMax=4294967296}={}) {
if(startingEntries) throw new Error("not implemented yet");
this.keyType = keyType;
this.valueType = valueType;
if(this.keyType !== "string" && !numberTypeToBufferMethodNameMap[keyType]) throw new Error("invalid/unimplemented key type");
if(this.valueType !== "string" && !numberTypeToBufferMethodNameMap[valueType]) throw new Error("invalid/unimplemented value type");
this.keySize = keySize || numberTypeToSizeMap[keyType];
this.valueSize = valueSize || numberTypeToSizeMap[valueType];
if(!this.keySize || !this.valueSize) throw new Error("must specify size for string type");
if(typeof keySize !== 'undefined' && numberTypeToSizeMap[keyType] && keySize !== numberTypeToSizeMap[keyType]) throw new Error("keySize doesn't match the size of keyType. you can omit keySize if keyType is a number type");
if(typeof valueSize !== 'undefined' && numberTypeToSizeMap[valueType] && valueSize !== numberTypeToSizeMap[valueType]) throw new Error("valueSize doesn't match the size of valueType. you can omit valueSize if valueType is a number type");
this.hashTable = new HashTable(this.keySize, this.valueSize, elementsMin, elementsMax);
this.keyBuf = Buffer.alloc(this.keySize);
this.valueBuf = Buffer.alloc(this.valueSize);
this.keyTypeBufferMethodName = (this.keyType === "string") ? null : numberTypeToBufferMethodNameMap[keyType];
this.valueTypeBufferMethodName = (this.valueType === "string") ? null : numberTypeToBufferMethodNameMap[valueType];
this.keysBuffer = Buffer.alloc(1024*64);
this.keysBufferCurrentEndOffset = 0;
this.trackKeys = !!trackKeys;
}
set(key, value) {
if(this.keyType === "string" && key.length !== this.keySize) throw new Error("wrong key size");
if(this.valueType === "string" && value.length !== this.valueSize) throw new Error("wrong value size");
if(this.keyType === "string") this.keyBuf.write(key);
else this.keyBuf["write"+this.keyTypeBufferMethodName](key);
if(this.valueType === "string") this.valueBuf.write(value);
else this.valueBuf["write"+this.valueTypeBufferMethodName](value);
if(this.trackKeys && !this.has(key)) {
if(this.keyType === "string") this.keysBuffer.write(key, this.keysBufferCurrentEndOffset, this.keySize, 'utf8');
else this.keysBuffer["write"+this.keyTypeBufferMethodName](key, this.keysBufferCurrentEndOffset);
this.keysBufferCurrentEndOffset += this.keySize;
if(this.keysBuffer.length < this.keysBufferCurrentEndOffset+1024) { // extend keysBuffer if needed
const newBuf = Buffer.alloc(this.keysBuffer.length*2);
this.keysBuffer.copy(newBuf); // copies keysBuffer into newBuf
this.keysBuffer = newBuf;
}
}
return this.hashTable.set(this.keyBuf, 0, this.valueBuf, 0);
}
get(key) {
if(this.keyType === "string" && key.length !== this.keySize) throw new Error("wrong key size");
if(!this.has(key)) return undefined;
if(this.keyType === "string") this.keyBuf.write(key);
else this.keyBuf["write"+this.keyTypeBufferMethodName](key);
this.hashTable.get(this.keyBuf, 0, this.valueBuf, 0);
if(this.valueType === "string") return this.valueBuf.toString('utf8');
else return this.valueBuf["read"+this.valueTypeBufferMethodName]();
}
delete(key) {
throw new Error("haven't implemented deletion from keysBuffer yet (need to maintain list of deleted keys and skip them in iterator, and remove them from keysBuffer and reshuffle only once we reach some significant number of deleted keys - or something like that)");
// if(this.keyType === "string") this.keyBuf.write(key);
// else if(this.keyType === "uint32") return this.keyBuf.writeUInt32BE(key);
// return !!this.hashTable.unset(this.keyBuf, 0);
}
has(key) {
if(this.keyType === "string" && key.length !== this.keySize) throw new Error("wrong key size");
if(this.keyType === "string") this.keyBuf.write(key);
else return this.keyBuf["write"+this.keyTypeBufferMethodName](key);
return !!this.hashTable.exist(this.keyBuf, 0);
}
get size() {
return this.hashTable.size;
}
keys() {
if(!this.trackKeys) throw new Error("must pass trackKeys=true in constructor options to use this method");
let currentKeysBufferOffset = 0;
return {
next: () => {
if(currentKeysBufferOffset === this.keysBufferCurrentEndOffset) return {done:true};
let key;
if(this.keyType === "string") key = this.keysBuffer.toString('utf8', currentKeysBufferOffset, currentKeysBufferOffset+this.keySize);
else key = this.keysBuffer["read"+this.keyTypeBufferMethodName](currentKeysBufferOffset);
currentKeysBufferOffset += this.keySize;
return {value:key, done:false};
},
[Symbol.iterator]: function() { return this }
};
}
entries() {
if(!this.trackKeys) throw new Error("must pass trackKeys=true in constructor options to use this method");
let currentKeysBufferOffset = 0;
return {
next: () => {
if(currentKeysBufferOffset === this.keysBufferCurrentEndOffset) return {done:true};
let key;
if(this.keyType === "string") key = this.keysBuffer.toString('utf8', currentKeysBufferOffset, currentKeysBufferOffset+this.keySize);
else key = this.keysBuffer["read"+this.keyTypeBufferMethodName](currentKeysBufferOffset);
let value = this.get(key);
currentKeysBufferOffset += this.keySize;
return {value:[key, value], done:false};
},
[Symbol.iterator]: function() { return this }
};
}
values() {
if(!this.trackKeys) throw new Error("must pass trackKeys=true in constructor options to use this method");
let currentKeysBufferOffset = 0;
return {
next: () => {
if(currentKeysBufferOffset === this.keysBufferCurrentEndOffset) return {done:true};
let key;
if(this.keyType === "string") key = this.keysBuffer.toString('utf8', currentKeysBufferOffset, currentKeysBufferOffset+this.keySize);
else key = this.keysBuffer["read"+this.keyTypeBufferMethodName](currentKeysBufferOffset);
let value = this.get(key);
currentKeysBufferOffset += this.keySize;
return {value:value, done:false};
},
[Symbol.iterator]: function() { return this }
};
}
[Symbol.iterator]() {
return this.entries();
}
}
Raw
HashTable.mjs
var thePackage = (function(){function r(e,n,t){function o(i,f){if(!n[i]){if(!e[i]){var c="function"==typeof require&&require;if(!f&&c)return c(i,!0);if(u)return u(i,!0);var a=new Error("Cannot find module '"+i+"'");throw a.code="MODULE_NOT_FOUND",a}var p=n[i]={exports:{}};e[i][0].call(p.exports,function(r){var n=e[i][1][r];return o(n||r)},p,p.exports,r,e,n,t)}return n[i].exports}for(var u="function"==typeof require&&require,i=0;i<t.length;i++)o(t[i]);return o}return r})()({1:[function(require,module,exports){
'use strict'
exports.byteLength = byteLength
exports.toByteArray = toByteArray
exports.fromByteArray = fromByteArray
var lookup = []
var revLookup = []
var Arr = typeof Uint8Array !== 'undefined' ? Uint8Array : Array
var code = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
for (var i = 0, len = code.length; i < len; ++i) {
lookup[i] = code[i]
revLookup[code.charCodeAt(i)] = i
}
// Support decoding URL-safe base64 strings, as Node.js does.
// See: https://en.wikipedia.org/wiki/Base64#URL_applications
revLookup['-'.charCodeAt(0)] = 62
revLookup['_'.charCodeAt(0)] = 63
function getLens (b64) {
var len = b64.length
if (len % 4 > 0) {
throw new Error('Invalid string. Length must be a multiple of 4')
}
// Trim off extra bytes after placeholder bytes are found
// See: https://github.com/beatgammit/base64-js/issues/42
var validLen = b64.indexOf('=')
if (validLen === -1) validLen = len
var placeHoldersLen = validLen === len
? 0
: 4 - (validLen % 4)
return [validLen, placeHoldersLen]
}
// base64 is 4/3 + up to two characters of the original data
function byteLength (b64) {
var lens = getLens(b64)
var validLen = lens[0]
var placeHoldersLen = lens[1]
return ((validLen + placeHoldersLen) * 3 / 4) - placeHoldersLen
}
function _byteLength (b64, validLen, placeHoldersLen) {
return ((validLen + placeHoldersLen) * 3 / 4) - placeHoldersLen
}
function toByteArray (b64) {
var tmp
var lens = getLens(b64)
var validLen = lens[0]
var placeHoldersLen = lens[1]
var arr = new Arr(_byteLength(b64, validLen, placeHoldersLen))
var curByte = 0
// if there are placeholders, only get up to the last complete 4 chars
var len = placeHoldersLen > 0
? validLen - 4
: validLen
for (var i = 0; i < len; i += 4) {
tmp =
(revLookup[b64.charCodeAt(i)] << 18) |
(revLookup[b64.charCodeAt(i + 1)] << 12) |
(revLookup[b64.charCodeAt(i + 2)] << 6) |
revLookup[b64.charCodeAt(i + 3)]
arr[curByte++] = (tmp >> 16) & 0xFF
arr[curByte++] = (tmp >> 8) & 0xFF
arr[curByte++] = tmp & 0xFF
}
if (placeHoldersLen === 2) {
tmp =
(revLookup[b64.charCodeAt(i)] << 2) |
(revLookup[b64.charCodeAt(i + 1)] >> 4)
arr[curByte++] = tmp & 0xFF
}
if (placeHoldersLen === 1) {
tmp =
(revLookup[b64.charCodeAt(i)] << 10) |
(revLookup[b64.charCodeAt(i + 1)] << 4) |
(revLookup[b64.charCodeAt(i + 2)] >> 2)
arr[curByte++] = (tmp >> 8) & 0xFF
arr[curByte++] = tmp & 0xFF
}
return arr
}
function tripletToBase64 (num) {
return lookup[num >> 18 & 0x3F] +
lookup[num >> 12 & 0x3F] +
lookup[num >> 6 & 0x3F] +
lookup[num & 0x3F]
}
function encodeChunk (uint8, start, end) {
var tmp
var output = []
for (var i = start; i < end; i += 3) {
tmp =
((uint8[i] << 16) & 0xFF0000) +
((uint8[i + 1] << 8) & 0xFF00) +
(uint8[i + 2] & 0xFF)
output.push(tripletToBase64(tmp))
}
return output.join('')
}
function fromByteArray (uint8) {
var tmp
var len = uint8.length
var extraBytes = len % 3 // if we have 1 byte left, pad 2 bytes
var parts = []
var maxChunkLength = 16383 // must be multiple of 3
// go through the array every three bytes, we'll deal with trailing stuff later
for (var i = 0, len2 = len - extraBytes; i < len2; i += maxChunkLength) {
parts.push(encodeChunk(
uint8, i, (i + maxChunkLength) > len2 ? len2 : (i + maxChunkLength)
))
}
// pad the end with zeros, but make sure to not forget the extra bytes
if (extraBytes === 1) {
tmp = uint8[len - 1]
parts.push(
lookup[tmp >> 2] +
lookup[(tmp << 4) & 0x3F] +
'=='
)
} else if (extraBytes === 2) {
tmp = (uint8[len - 2] << 8) + uint8[len - 1]
parts.push(
lookup[tmp >> 10] +
lookup[(tmp >> 4) & 0x3F] +
lookup[(tmp << 2) & 0x3F] +
'='
)
}
return parts.join('')
}
},{}],2:[function(require,module,exports){
(function (Buffer){
/*!
* The buffer module from node.js, for the browser.
*
* @author Feross Aboukhadijeh <https://feross.org>
* @license MIT
*/
/* eslint-disable no-proto */
'use strict'
var base64 = require('base64-js')
var ieee754 = require('ieee754')
exports.Buffer = Buffer
exports.SlowBuffer = SlowBuffer
exports.INSPECT_MAX_BYTES = 50
var K_MAX_LENGTH = 0x7fffffff
exports.kMaxLength = K_MAX_LENGTH
/**
* If `Buffer.TYPED_ARRAY_SUPPORT`:
* === true Use Uint8Array implementation (fastest)
* === false Print warning and recommend using `buffer` v4.x which has an Object
* implementation (most compatible, even IE6)
*
* Browsers that support typed arrays are IE 10+, Firefox 4+, Chrome 7+, Safari 5.1+,
* Opera 11.6+, iOS 4.2+.
*
* We report that the browser does not support typed arrays if the are not subclassable
* using __proto__. Firefox 4-29 lacks support for adding new properties to `Uint8Array`
* (See: https://bugzilla.mozilla.org/show_bug.cgi?id=695438). IE 10 lacks support
* for __proto__ and has a buggy typed array implementation.
*/
Buffer.TYPED_ARRAY_SUPPORT = typedArraySupport()
if (!Buffer.TYPED_ARRAY_SUPPORT && typeof console !== 'undefined' &&
typeof console.error === 'function') {
console.error(
'This browser lacks typed array (Uint8Array) support which is required by ' +
'`buffer` v5.x. Use `buffer` v4.x if you require old browser support.'
)
}
function typedArraySupport () {
// Can typed array instances can be augmented?
try {
var arr = new Uint8Array(1)
arr.__proto__ = { __proto__: Uint8Array.prototype, foo: function () { return 42 } }
return arr.foo() === 42
} catch (e) {
return false
}
}
Object.defineProperty(Buffer.prototype, 'parent', {
enumerable: true,
get: function () {
if (!Buffer.isBuffer(this)) return undefined
return this.buffer
}
})
Object.defineProperty(Buffer.prototype, 'offset', {
enumerable: true,
get: function () {
if (!Buffer.isBuffer(this)) return undefined
return this.byteOffset
}
})
function createBuffer (length) {
if (length > K_MAX_LENGTH) {
throw new RangeError('The value "' + length + '" is invalid for option "size"')
}
// Return an augmented `Uint8Array` instance
var buf = new Uint8Array(length)
buf.__proto__ = Buffer.prototype
return buf
}
/**
* The Buffer constructor returns instances of `Uint8Array` that have their
* prototype changed to `Buffer.prototype`. Furthermore, `Buffer` is a subclass of
* `Uint8Array`, so the returned instances will have all the node `Buffer` methods
* and the `Uint8Array` methods. Square bracket notation works as expected -- it
* returns a single octet.
*
* The `Uint8Array` prototype remains unmodified.
*/
function Buffer (arg, encodingOrOffset, length) {
// Common case.
if (typeof arg === 'number') {
if (typeof encodingOrOffset === 'string') {
throw new TypeError(
'The "string" argument must be of type string. Received type number'
)
}
return allocUnsafe(arg)
}
return from(arg, encodingOrOffset, length)
}
// Fix subarray() in ES2016. See: https://github.com/feross/buffer/pull/97
if (typeof Symbol !== 'undefined' && Symbol.species != null &&
Buffer[Symbol.species] === Buffer) {
Object.defineProperty(Buffer, Symbol.species, {
value: null,
configurable: true,
enumerable: false,
writable: false
})
}
Buffer.poolSize = 8192 // not used by this implementation
function from (value, encodingOrOffset, length) {
if (typeof value === 'string') {
return fromString(value, encodingOrOffset)
}
if (ArrayBuffer.isView(value)) {
return fromArrayLike(value)
}
if (value == null) {
throw TypeError(
'The first argument must be one of type string, Buffer, ArrayBuffer, Array, ' +
'or Array-like Object. Received type ' + (typeof value)
)
}
if (isInstance(value, ArrayBuffer) ||
(value && isInstance(value.buffer, ArrayBuffer))) {
return fromArrayBuffer(value, encodingOrOffset, length)
}
if (typeof value === 'number') {
throw new TypeError(
'The "value" argument must not be of type number. Received type number'
)
}
var valueOf = value.valueOf && value.valueOf()
if (valueOf != null && valueOf !== value) {
return Buffer.from(valueOf, encodingOrOffset, length)
}
var b = fromObject(value)
if (b) return b
if (typeof Symbol !== 'undefined' && Symbol.toPrimitive != null &&
typeof value[Symbol.toPrimitive] === 'function') {
return Buffer.from(
value[Symbol.toPrimitive]('string'), encodingOrOffset, length
)
}
throw new TypeError(
'The first argument must be one of type string, Buffer, ArrayBuffer, Array, ' +
'or Array-like Object. Received type ' + (typeof value)
)
}
/**
* Functionally equivalent to Buffer(arg, encoding) but throws a TypeError
* if value is a number.
* Buffer.from(str[, encoding])
* Buffer.from(array)
* Buffer.from(buffer)
* Buffer.from(arrayBuffer[, byteOffset[, length]])
**/
Buffer.from = function (value, encodingOrOffset, length) {
return from(value, encodingOrOffset, length)
}
// Note: Change prototype *after* Buffer.from is defined to workaround Chrome bug:
// https://github.com/feross/buffer/pull/148
Buffer.prototype.__proto__ = Uint8Array.prototype
Buffer.__proto__ = Uint8Array
function assertSize (size) {
if (typeof size !== 'number') {
throw new TypeError('"size" argument must be of type number')
} else if (size < 0) {
throw new RangeError('The value "' + size + '" is invalid for option "size"')
}
}
function alloc (size, fill, encoding) {
assertSize(size)
if (size <= 0) {
return createBuffer(size)
}
if (fill !== undefined) {
// Only pay attention to encoding if it's a string. This
// prevents accidentally sending in a number that would
// be interpretted as a start offset.
return typeof encoding === 'string'
? createBuffer(size).fill(fill, encoding)
: createBuffer(size).fill(fill)
}
return createBuffer(size)
}
/**
* Creates a new filled Buffer instance.
* alloc(size[, fill[, encoding]])
**/
Buffer.alloc = function (size, fill, encoding) {
return alloc(size, fill, encoding)
}
function allocUnsafe (size) {
assertSize(size)
return createBuffer(size < 0 ? 0 : checked(size) | 0)
}
/**
* Equivalent to Buffer(num), by default creates a non-zero-filled Buffer instance.
* */
Buffer.allocUnsafe = function (size) {
return allocUnsafe(size)
}
/**
* Equivalent to SlowBuffer(num), by default creates a non-zero-filled Buffer instance.
*/
Buffer.allocUnsafeSlow = function (size) {
return allocUnsafe(size)
}
function fromString (string, encoding) {
if (typeof encoding !== 'string' || encoding === '') {
encoding = 'utf8'
}
if (!Buffer.isEncoding(encoding)) {
throw new TypeError('Unknown encoding: ' + encoding)
}
var length = byteLength(string, encoding) | 0
var buf = createBuffer(length)
var actual = buf.write(string, encoding)
if (actual !== length) {
// Writing a hex string, for example, that contains invalid characters will
// cause everything after the first invalid character to be ignored. (e.g.
// 'abxxcd' will be treated as 'ab')
buf = buf.slice(0, actual)
}
return buf
}
function fromArrayLike (array) {
var length = array.length < 0 ? 0 : checked(array.length) | 0
var buf = createBuffer(length)
for (var i = 0; i < length; i += 1) {
buf[i] = array[i] & 255
}
return buf
}
function fromArrayBuffer (array, byteOffset, length) {
if (byteOffset < 0 || array.byteLength < byteOffset) {
throw new RangeError('"offset" is outside of buffer bounds')
}
if (array.byteLength < byteOffset + (length || 0)) {
throw new RangeError('"length" is outside of buffer bounds')
}
var buf
if (byteOffset === undefined && length === undefined) {
buf = new Uint8Array(array)
} else if (length === undefined) {
buf = new Uint8Array(array, byteOffset)
} else {
buf = new Uint8Array(array, byteOffset, length)
}
// Return an augmented `Uint8Array` instance
buf.__proto__ = Buffer.prototype
return buf
}
function fromObject (obj) {
if (Buffer.isBuffer(obj)) {
var len = checked(obj.length) | 0
var buf = createBuffer(len)
if (buf.length === 0) {
return buf
}
obj.copy(buf, 0, 0, len)
return buf
}
if (obj.length !== undefined) {
if (typeof obj.length !== 'number' || numberIsNaN(obj.length)) {
return createBuffer(0)
}
return fromArrayLike(obj)
}
if (obj.type === 'Buffer' && Array.isArray(obj.data)) {
return fromArrayLike(obj.data)
}
}
function checked (length) {
// Note: cannot use `length < K_MAX_LENGTH` here because that fails when
// length is NaN (which is otherwise coerced to zero.)
if (length >= K_MAX_LENGTH) {
throw new RangeError('Attempt to allocate Buffer larger than maximum ' +
'size: 0x' + K_MAX_LENGTH.toString(16) + ' bytes')
}
return length | 0
}
function SlowBuffer (length) {
if (+length != length) { // eslint-disable-line eqeqeq
length = 0
}
return Buffer.alloc(+length)
}
Buffer.isBuffer = function isBuffer (b) {
return b != null && b._isBuffer === true &&
b !== Buffer.prototype // so Buffer.isBuffer(Buffer.prototype) will be false
}
Buffer.compare = function compare (a, b) {
if (isInstance(a, Uint8Array)) a = Buffer.from(a, a.offset, a.byteLength)
if (isInstance(b, Uint8Array)) b = Buffer.from(b, b.offset, b.byteLength)
if (!Buffer.isBuffer(a) || !Buffer.isBuffer(b)) {
throw new TypeError(
'The "buf1", "buf2" arguments must be one of type Buffer or Uint8Array'
)
}
if (a === b) return 0
var x = a.length
var y = b.length
for (var i = 0, len = Math.min(x, y); i < len; ++i) {
if (a[i] !== b[i]) {
x = a[i]
y = b[i]
break
}
}
if (x < y) return -1
if (y < x) return 1
return 0
}
Buffer.isEncoding = function isEncoding (encoding) {
switch (String(encoding).toLowerCase()) {
case 'hex':
case 'utf8':
case 'utf-8':
case 'ascii':
case 'latin1':
case 'binary':
case 'base64':
case 'ucs2':
case 'ucs-2':
case 'utf16le':
case 'utf-16le':
return true
default:
return false
}
}
Buffer.concat = function concat (list, length) {
if (!Array.isArray(list)) {
throw new TypeError('"list" argument must be an Array of Buffers')
}
if (list.length === 0) {
return Buffer.alloc(0)
}
var i
if (length === undefined) {
length = 0
for (i = 0; i < list.length; ++i) {
length += list[i].length
}
}
var buffer = Buffer.allocUnsafe(length)
var pos = 0
for (i = 0; i < list.length; ++i) {
var buf = list[i]
if (isInstance(buf, Uint8Array)) {
buf = Buffer.from(buf)
}
if (!Buffer.isBuffer(buf)) {
throw new TypeError('"list" argument must be an Array of Buffers')
}
buf.copy(buffer, pos)
pos += buf.length
}
return buffer
}
function byteLength (string, encoding) {
if (Buffer.isBuffer(string)) {
return string.length
}
if (ArrayBuffer.isView(string) || isInstance(string, ArrayBuffer)) {
return string.byteLength
}
if (typeof string !== 'string') {
throw new TypeError(
'The "string" argument must be one of type string, Buffer, or ArrayBuffer. ' +
'Received type ' + typeof string
)
}
var len = string.length
var mustMatch = (arguments.length > 2 && arguments[2] === true)
if (!mustMatch && len === 0) return 0
// Use a for loop to avoid recursion
var loweredCase = false
for (;;) {
switch (encoding) {
case 'ascii':
case 'latin1':
case 'binary':
return len
case 'utf8':
case 'utf-8':
return utf8ToBytes(string).length
case 'ucs2':
case 'ucs-2':
case 'utf16le':
case 'utf-16le':
return len * 2
case 'hex':
return len >>> 1
case 'base64':
return base64ToBytes(string).length
default:
if (loweredCase) {
return mustMatch ? -1 : utf8ToBytes(string).length // assume utf8
}
encoding = ('' + encoding).toLowerCase()
loweredCase = true
}
}
}
Buffer.byteLength = byteLength
function slowToString (encoding, start, end) {
var loweredCase = false
// No need to verify that "this.length <= MAX_UINT32" since it's a read-only
// property of a typed array.
// This behaves neither like String nor Uint8Array in that we set start/end
// to their upper/lower bounds if the value passed is out of range.
// undefined is handled specially as per ECMA-262 6th Edition,
// Section 13.3.3.7 Runtime Semantics: KeyedBindingInitialization.
if (start === undefined || start < 0) {
start = 0
}
// Return early if start > this.length. Done here to prevent potential uint32
// coercion fail below.
if (start > this.length) {
return ''
}
if (end === undefined || end > this.length) {
end = this.length
}
if (end <= 0) {
return ''
}
// Force coersion to uint32. This will also coerce falsey/NaN values to 0.
end >>>= 0
start >>>= 0
if (end <= start) {
return ''
}
if (!encoding) encoding = 'utf8'
while (true) {
switch (encoding) {
case 'hex':
return hexSlice(this, start, end)
case 'utf8':
case 'utf-8':
return utf8Slice(this, start, end)
case 'ascii':
return asciiSlice(this, start, end)
case 'latin1':
case 'binary':
return latin1Slice(this, start, end)
case 'base64':
return base64Slice(this, start, end)
case 'ucs2':
case 'ucs-2':
case 'utf16le':
case 'utf-16le':
return utf16leSlice(this, start, end)
default:
if (loweredCase) throw new TypeError('Unknown encoding: ' + encoding)
encoding = (encoding + '').toLowerCase()
loweredCase = true
}
}
}
// This property is used by `Buffer.isBuffer` (and the `is-buffer` npm package)
// to detect a Buffer instance. It's not possible to use `instanceof Buffer`
// reliably in a browserify context because there could be multiple different
// copies of the 'buffer' package in use. This method works even for Buffer
// instances that were created from another copy of the `buffer` package.
// See: https://github.com/feross/buffer/issues/154
Buffer.prototype._isBuffer = true
function swap (b, n, m) {
var i = b[n]
b[n] = b[m]
b[m] = i
}
Buffer.prototype.swap16 = function swap16 () {
var len = this.length
if (len % 2 !== 0) {
throw new RangeError('Buffer size must be a multiple of 16-bits')
}
for (var i = 0; i < len; i += 2) {
swap(this, i, i + 1)
}
return this
}
Buffer.prototype.swap32 = function swap32 () {
var len = this.length
if (len % 4 !== 0) {
throw new RangeError('Buffer size must be a multiple of 32-bits')
}
for (var i = 0; i < len; i += 4) {
swap(this, i, i + 3)
swap(this, i + 1, i + 2)
}
return this
}
Buffer.prototype.swap64 = function swap64 () {
var len = this.length
if (len % 8 !== 0) {
throw new RangeError('Buffer size must be a multiple of 64-bits')
}
for (var i = 0; i < len; i += 8) {
swap(this, i, i + 7)
swap(this, i + 1, i + 6)
swap(this, i + 2, i + 5)
swap(this, i + 3, i + 4)
}
return this
}
Buffer.prototype.toString = function toString () {
var length = this.length
if (length === 0) return ''
if (arguments.length === 0) return utf8Slice(this, 0, length)
return slowToString.apply(this, arguments)
}
Buffer.prototype.toLocaleString = Buffer.prototype.toString
Buffer.prototype.equals = function equals (b) {
if (!Buffer.isBuffer(b)) throw new TypeError('Argument must be a Buffer')
if (this === b) return true
return Buffer.compare(this, b) === 0
}
Buffer.prototype.inspect = function inspect () {
var str = ''
var max = exports.INSPECT_MAX_BYTES
str = this.toString('hex', 0, max).replace(/(.{2})/g, '$1 ').trim()
if (this.length > max) str += ' ... '
return '<Buffer ' + str + '>'
}
Buffer.prototype.compare = function compare (target, start, end, thisStart, thisEnd) {
if (isInstance(target, Uint8Array)) {
target = Buffer.from(target, target.offset, target.byteLength)
}
if (!Buffer.isBuffer(target)) {
throw new TypeError(
'The "target" argument must be one of type Buffer or Uint8Array. ' +
'Received type ' + (typeof target)
)
}
if (start === undefined) {
start = 0
}
if (end === undefined) {
end = target ? target.length : 0
}
if (thisStart === undefined) {
thisStart = 0
}
if (thisEnd === undefined) {
thisEnd = this.length
}
if (start < 0 || end > target.length || thisStart < 0 || thisEnd > this.length) {
throw new RangeError('out of range index')
}
if (thisStart >= thisEnd && start >= end) {
return 0
}
if (thisStart >= thisEnd) {
return -1
}
if (start >= end) {
return 1
}
start >>>= 0
end >>>= 0
thisStart >>>= 0
thisEnd >>>= 0
if (this === target) return 0
var x = thisEnd - thisStart
var y = end - start
var len = Math.min(x, y)
var thisCopy = this.slice(thisStart, thisEnd)
var targetCopy = target.slice(start, end)
for (var i = 0; i < len; ++i) {
if (thisCopy[i] !== targetCopy[i]) {
x = thisCopy[i]
y = targetCopy[i]
break
}
}
if (x < y) return -1
if (y < x) return 1
return 0
}
// Finds either the first index of `val` in `buffer` at offset >= `byteOffset`,
// OR the last index of `val` in `buffer` at offset <= `byteOffset`.
//
// Arguments:
// - buffer - a Buffer to search
// - val - a string, Buffer, or number
// - byteOffset - an index into `buffer`; will be clamped to an int32
// - encoding - an optional encoding, relevant is val is a string
// - dir - true for indexOf, false for lastIndexOf
function bidirectionalIndexOf (buffer, val, byteOffset, encoding, dir) {
// Empty buffer means no match
if (buffer.length === 0) return -1
// Normalize byteOffset
if (typeof byteOffset === 'string') {
encoding = byteOffset
byteOffset = 0
} else if (byteOffset > 0x7fffffff) {
byteOffset = 0x7fffffff
} else if (byteOffset < -0x80000000) {
byteOffset = -0x80000000
}
byteOffset = +byteOffset // Coerce to Number.
if (numberIsNaN(byteOffset)) {
// byteOffset: it it's undefined, null, NaN, "foo", etc, search whole buffer
byteOffset = dir ? 0 : (buffer.length - 1)
}
// Normalize byteOffset: negative offsets start from the end of the buffer
if (byteOffset < 0) byteOffset = buffer.length + byteOffset
if (byteOffset >= buffer.length) {
if (dir) return -1
else byteOffset = buffer.length - 1
} else if (byteOffset < 0) {
if (dir) byteOffset = 0
else return -1
}
// Normalize val
if (typeof val === 'string') {
val = Buffer.from(val, encoding)
}
// Finally, search either indexOf (if dir is true) or lastIndexOf
if (Buffer.isBuffer(val)) {
// Special case: looking for empty string/buffer always fails
if (val.length === 0) {
return -1
}
return arrayIndexOf(buffer, val, byteOffset, encoding, dir)
} else if (typeof val === 'number') {
val = val & 0xFF // Search for a byte value [0-255]
if (typeof Uint8Array.prototype.indexOf === 'function') {
if (dir) {
return Uint8Array.prototype.indexOf.call(buffer, val, byteOffset)
} else {
return Uint8Array.prototype.lastIndexOf.call(buffer, val, byteOffset)
}
}
return arrayIndexOf(buffer, [ val ], byteOffset, encoding, dir)
}
throw new TypeError('val must be string, number or Buffer')
}
function arrayIndexOf (arr, val, byteOffset, encoding, dir) {
var indexSize = 1
var arrLength = arr.length
var valLength = val.length
if (encoding !== undefined) {
encoding = String(encoding).toLowerCase()
if (encoding === 'ucs2' || encoding === 'ucs-2' ||
encoding === 'utf16le' || encoding === 'utf-16le') {
if (arr.length < 2 || val.length < 2) {
return -1
}
indexSize = 2
arrLength /= 2
valLength /= 2
byteOffset /= 2
}
}
function read (buf, i) {
if (indexSize === 1) {
return buf[i]
} else {
return buf.readUInt16BE(i * indexSize)
}
}
var i
if (dir) {
var foundIndex = -1
for (i = byteOffset; i < arrLength; i++) {
if (read(arr, i) === read(val, foundIndex === -1 ? 0 : i - foundIndex)) {
if (foundIndex === -1) foundIndex = i
if (i - foundIndex + 1 === valLength) return foundIndex * indexSize
} else {
if (foundIndex !== -1) i -= i - foundIndex
foundIndex = -1
}
}
} else {
if (byteOffset + valLength > arrLength) byteOffset = arrLength - valLength
for (i = byteOffset; i >= 0; i--) {
var found = true
for (var j = 0; j < valLength; j++) {
if (read(arr, i + j) !== read(val, j)) {
found = false
break
}
}
if (found) return i
}
}
return -1
}
Buffer.prototype.includes = function includes (val, byteOffset, encoding) {
return this.indexOf(val, byteOffset, encoding) !== -1
}
Buffer.prototype.indexOf = function indexOf (val, byteOffset, encoding) {
return bidirectionalIndexOf(this, val, byteOffset, encoding, true)
}
Buffer.prototype.lastIndexOf = function lastIndexOf (val, byteOffset, encoding) {
return bidirectionalIndexOf(this, val, byteOffset, encoding, false)
}
function hexWrite (buf, string, offset, length) {
offset = Number(offset) || 0
var remaining = buf.length - offset
if (!length) {
length = remaining
} else {
length = Number(length)
if (length > remaining) {
length = remaining
}
}
var strLen = string.length
if (length > strLen / 2) {
length = strLen / 2
}
for (var i = 0; i < length; ++i) {
var parsed = parseInt(string.substr(i * 2, 2), 16)
if (numberIsNaN(parsed)) return i
buf[offset + i] = parsed
}
return i
}
function utf8Write (buf, string, offset, length) {
return blitBuffer(utf8ToBytes(string, buf.length - offset), buf, offset, length)
}
function asciiWrite (buf, string, offset, length) {
return blitBuffer(asciiToBytes(string), buf, offset, length)
}
function latin1Write (buf, string, offset, length) {
return asciiWrite(buf, string, offset, length)
}
function base64Write (buf, string, offset, length) {
return blitBuffer(base64ToBytes(string), buf, offset, length)
}
function ucs2Write (buf, string, offset, length) {
return blitBuffer(utf16leToBytes(string, buf.length - offset), buf, offset, length)
}
Buffer.prototype.write = function write (string, offset, length, encoding) {
// Buffer#write(string)
if (offset === undefined) {
encoding = 'utf8'
length = this.length
offset = 0
// Buffer#write(string, encoding)
} else if (length === undefined && typeof offset === 'string') {
encoding = offset
length = this.length
offset = 0
// Buffer#write(string, offset[, length][, encoding])
} else if (isFinite(offset)) {
offset = offset >>> 0
if (isFinite(length)) {
length = length >>> 0
if (encoding === undefined) encoding = 'utf8'
} else {
encoding = length
length = undefined
}
} else {
throw new Error(
'Buffer.write(string, encoding, offset[, length]) is no longer supported'
)
}
var remaining = this.length - offset
if (length === undefined || length > remaining) length = remaining
if ((string.length > 0 && (length < 0 || offset < 0)) || offset > this.length) {
throw new RangeError('Attempt to write outside buffer bounds')
}
if (!encoding) encoding = 'utf8'
var loweredCase = false
for (;;) {
switch (encoding) {
case 'hex':
return hexWrite(this, string, offset, length)
case 'utf8':
case 'utf-8':
return utf8Write(this, string, offset, length)
case 'ascii':
return asciiWrite(this, string, offset, length)
case 'latin1':
case 'binary':
return latin1Write(this, string, offset, length)
case 'base64':
// Warning: maxLength not taken into account in base64Write
return base64Write(this, string, offset, length)
case 'ucs2':
case 'ucs-2':
case 'utf16le':
case 'utf-16le':
return ucs2Write(this, string, offset, length)
default:
if (loweredCase) throw new TypeError('Unknown encoding: ' + encoding)
encoding = ('' + encoding).toLowerCase()
loweredCase = true
}
}
}
Buffer.prototype.toJSON = function toJSON () {
return {
type: 'Buffer',
data: Array.prototype.slice.call(this._arr || this, 0)
}
}
function base64Slice (buf, start, end) {
if (start === 0 && end === buf.length) {
return base64.fromByteArray(buf)
} else {
return base64.fromByteArray(buf.slice(start, end))
}
}
function utf8Slice (buf, start, end) {
end = Math.min(buf.length, end)
var res = []
var i = start
while (i < end) {
var firstByte = buf[i]
var codePoint = null
var bytesPerSequence = (firstByte > 0xEF) ? 4
: (firstByte > 0xDF) ? 3
: (firstByte > 0xBF) ? 2
: 1
if (i + bytesPerSequence <= end) {
var secondByte, thirdByte, fourthByte, tempCodePoint
switch (bytesPerSequence) {
case 1:
if (firstByte < 0x80) {
codePoint = firstByte
}
break
case 2:
secondByte = buf[i + 1]
if ((secondByte & 0xC0) === 0x80) {
tempCodePoint = (firstByte & 0x1F) << 0x6 | (secondByte & 0x3F)
if (tempCodePoint > 0x7F) {
codePoint = tempCodePoint
}
}
break
case 3:
secondByte = buf[i + 1]
thirdByte = buf[i + 2]
if ((secondByte & 0xC0) === 0x80 && (thirdByte & 0xC0) === 0x80) {
tempCodePoint = (firstByte & 0xF) << 0xC | (secondByte & 0x3F) << 0x6 | (thirdByte & 0x3F)
if (tempCodePoint > 0x7FF && (tempCodePoint < 0xD800 || tempCodePoint > 0xDFFF)) {
codePoint = tempCodePoint
}
}
break
case 4:
secondByte = buf[i + 1]
thirdByte = buf[i + 2]
fourthByte = buf[i + 3]
if ((secondByte & 0xC0) === 0x80 && (thirdByte & 0xC0) === 0x80 && (fourthByte & 0xC0) === 0x80) {
tempCodePoint = (firstByte & 0xF) << 0x12 | (secondByte & 0x3F) << 0xC | (thirdByte & 0x3F) << 0x6 | (fourthByte & 0x3F)
if (tempCodePoint > 0xFFFF && tempCodePoint < 0x110000) {
codePoint = tempCodePoint
}
}
}
}
if (codePoint === null) {
// we did not generate a valid codePoint so insert a
// replacement char (U+FFFD) and advance only 1 byte
codePoint = 0xFFFD
bytesPerSequence = 1
} else if (codePoint > 0xFFFF) {
// encode to utf16 (surrogate pair dance)
codePoint -= 0x10000
res.push(codePoint >>> 10 & 0x3FF | 0xD800)
codePoint = 0xDC00 | codePoint & 0x3FF
}
res.push(codePoint)
i += bytesPerSequence
}
return decodeCodePointsArray(res)
}
// Based on http://stackoverflow.com/a/22747272/680742, the browser with
// the lowest limit is Chrome, with 0x10000 args.
// We go 1 magnitude less, for safety
var MAX_ARGUMENTS_LENGTH = 0x1000
function decodeCodePointsArray (codePoints) {
var len = codePoints.length
if (len <= MAX_ARGUMENTS_LENGTH) {
return String.fromCharCode.apply(String, codePoints) // avoid extra slice()
}
// Decode in chunks to avoid "call stack size exceeded".
var res = ''
var i = 0
while (i < len) {
res += String.fromCharCode.apply(
String,
codePoints.slice(i, i += MAX_ARGUMENTS_LENGTH)
)
}
return res
}
function asciiSlice (buf, start, end) {
var ret = ''
end = Math.min(buf.length, end)
for (var i = start; i < end; ++i) {
ret += String.fromCharCode(buf[i] & 0x7F)
}
return ret
}
function latin1Slice (buf, start, end) {
var ret = ''
end = Math.min(buf.length, end)
for (var i = start; i < end; ++i) {
ret += String.fromCharCode(buf[i])
}
return ret
}
function hexSlice (buf, start, end) {
var len = buf.length
if (!start || start < 0) start = 0
if (!end || end < 0 || end > len) end = len
var out = ''
for (var i = start; i < end; ++i) {
out += toHex(buf[i])
}
return out
}
function utf16leSlice (buf, start, end) {
var bytes = buf.slice(start, end)
var res = ''
for (var i = 0; i < bytes.length; i += 2) {
res += String.fromCharCode(bytes[i] + (bytes[i + 1] * 256))
}
return res
}
Buffer.prototype.slice = function slice (start, end) {
var len = this.length
start = ~~start
end = end === undefined ? len : ~~end
if (start < 0) {
start += len
if (start < 0) start = 0
} else if (start > len) {
start = len
}
if (end < 0) {
end += len
if (end < 0) end = 0
} else if (end > len) {
end = len
}
if (end < start) end = start
var newBuf = this.subarray(start, end)
// Return an augmented `Uint8Array` instance
newBuf.__proto__ = Buffer.prototype
return newBuf
}
/*
* Need to make sure that buffer isn't trying to write out of bounds.
*/
function checkOffset (offset, ext, length) {
if ((offset % 1) !== 0 || offset < 0) throw new RangeError('offset is not uint')
if (offset + ext > length) throw new RangeError('Trying to access beyond buffer length')
}
Buffer.prototype.readUIntLE = function readUIntLE (offset, byteLength, noAssert) {
offset = offset >>> 0
byteLength = byteLength >>> 0
if (!noAssert) checkOffset(offset, byteLength, this.length)
var val = this[offset]
var mul = 1
var i = 0
while (++i < byteLength && (mul *= 0x100)) {
val += this[offset + i] * mul
}
return val
}
Buffer.prototype.readUIntBE = function readUIntBE (offset, byteLength, noAssert) {
offset = offset >>> 0
byteLength = byteLength >>> 0
if (!noAssert) {
checkOffset(offset, byteLength, this.length)
}
var val = this[offset + --byteLength]
var mul = 1
while (byteLength > 0 && (mul *= 0x100)) {
val += this[offset + --byteLength] * mul
}
return val
}
Buffer.prototype.readUInt8 = function readUInt8 (offset, noAssert) {
offset = offset >>> 0
if (!noAssert) checkOffset(offset, 1, this.length)
return this[offset]
}
Buffer.prototype.readUInt16LE = function readUInt16LE (offset, noAssert) {
offset = offset >>> 0
if (!noAssert) checkOffset(offset, 2, this.length)
return this[offset] | (this[offset + 1] << 8)
}
Buffer.prototype.readUInt16BE = function readUInt16BE (offset, noAssert) {
offset = offset >>> 0
if (!noAssert) checkOffset(offset, 2, this.length)
return (this[offset] << 8) | this[offset + 1]
}
Buffer.prototype.readUInt32LE = function readUInt32LE (offset, noAssert) {
offset = offset >>> 0
if (!noAssert) checkOffset(offset, 4, this.length)
return ((this[offset]) |
(this[offset + 1] << 8) |
(this[offset + 2] << 16)) +
(this[offset + 3] * 0x1000000)
}
Buffer.prototype.readUInt32BE = function readUInt32BE (offset, noAssert) {
offset = offset >>> 0
if (!noAssert) checkOffset(offset, 4, this.length)
return (this[offset] * 0x1000000) +
((this[offset + 1] << 16) |
(this[offset + 2] << 8) |
this[offset + 3])
}
Buffer.prototype.readIntLE = function readIntLE (offset, byteLength, noAssert) {
offset = offset >>> 0
byteLength = byteLength >>> 0
if (!noAssert) checkOffset(offset, byteLength, this.length)
var val = this[offset]
var mul = 1
var i = 0
while (++i < byteLength && (mul *= 0x100)) {
val += this[offset + i] * mul
}
mul *= 0x80
if (val >= mul) val -= Math.pow(2, 8 * byteLength)
return val
}
Buffer.prototype.readIntBE = function readIntBE (offset, byteLength, noAssert) {
offset = offset >>> 0
byteLength = byteLength >>> 0
if (!noAssert) checkOffset(offset, byteLength, this.length)
var i = byteLength
var mul = 1
var val = this[offset + --i]
while (i > 0 && (mul *= 0x100)) {
val += this[offset + --i] * mul
}
mul *= 0x80
if (val >= mul) val -= Math.pow(2, 8 * byteLength)
return val
}
Buffer.prototype.readInt8 = function readInt8 (offset, noAssert) {
offset = offset >>> 0
if (!noAssert) checkOffset(offset, 1, this.length)
if (!(this[offset] & 0x80)) return (this[offset])
return ((0xff - this[offset] + 1) * -1)
}
Buffer.prototype.readInt16LE = function readInt16LE (offset, noAssert) {
offset = offset >>> 0
if (!noAssert) checkOffset(offset, 2, this.length)
var val = this[offset] | (this[offset + 1] << 8)
return (val & 0x8000) ? val | 0xFFFF0000 : val
}
Buffer.prototype.readInt16BE = function readInt16BE (offset, noAssert) {
offset = offset >>> 0
if (!noAssert) checkOffset(offset, 2, this.length)
var val = this[offset + 1] | (this[offset] << 8)
return (val & 0x8000) ? val | 0xFFFF0000 : val
}
Buffer.prototype.readInt32LE = function readInt32LE (offset, noAssert) {
offset = offset >>> 0
if (!noAssert) checkOffset(offset, 4, this.length)
return (this[offset]) |
(this[offset + 1] << 8) |
(this[offset + 2] << 16) |
(this[offset + 3] << 24)
}
Buffer.prototype.readInt32BE = function readInt32BE (offset, noAssert) {
offset = offset >>> 0
if (!noAssert) checkOffset(offset, 4, this.length)
return (this[offset] << 24) |
(this[offset + 1] << 16) |
(this[offset + 2] << 8) |
(this[offset + 3])
}
Buffer.prototype.readFloatLE = function readFloatLE (offset, noAssert) {
offset = offset >>> 0
if (!noAssert) checkOffset(offset, 4, this.length)
return ieee754.read(this, offset, true, 23, 4)
}
Buffer.prototype.readFloatBE = function readFloatBE (offset, noAssert) {
offset = offset >>> 0
if (!noAssert) checkOffset(offset, 4, this.length)
return ieee754.read(this, offset, false, 23, 4)
}
Buffer.prototype.readDoubleLE = function readDoubleLE (offset, noAssert) {
offset = offset >>> 0
if (!noAssert) checkOffset(offset, 8, this.length)
return ieee754.read(this, offset, true, 52, 8)
}
Buffer.prototype.readDoubleBE = function readDoubleBE (offset, noAssert) {
offset = offset >>> 0
if (!noAssert) checkOffset(offset, 8, this.length)
return ieee754.read(this, offset, false, 52, 8)
}
function checkInt (buf, value, offset, ext, max, min) {
if (!Buffer.isBuffer(buf)) throw new TypeError('"buffer" argument must be a Buffer instance')
if (value > max || value < min) throw new RangeError('"value" argument is out of bounds')
if (offset + ext > buf.length) throw new RangeError('Index out of range')
}
Buffer.prototype.writeUIntLE = function writeUIntLE (value, offset, byteLength, noAssert) {
value = +value
offset = offset >>> 0
byteLength = byteLength >>> 0
if (!noAssert) {
var maxBytes = Math.pow(2, 8 * byteLength) - 1
checkInt(this, value, offset, byteLength, maxBytes, 0)
}
var mul = 1
var i = 0
this[offset] = value & 0xFF
while (++i < byteLength && (mul *= 0x100)) {
this[offset + i] = (value / mul) & 0xFF
}
return offset + byteLength
}
Buffer.prototype.writeUIntBE = function writeUIntBE (value, offset, byteLength, noAssert) {
value = +value
offset = offset >>> 0
byteLength = byteLength >>> 0
if (!noAssert) {
var maxBytes = Math.pow(2, 8 * byteLength) - 1
checkInt(this, value, offset, byteLength, maxBytes, 0)
}
var i = byteLength - 1
var mul = 1
this[offset + i] = value & 0xFF
while (--i >= 0 && (mul *= 0x100)) {
this[offset + i] = (value / mul) & 0xFF
}
return offset + byteLength
}
Buffer.prototype.writeUInt8 = function writeUInt8 (value, offset, noAssert) {
value = +value
offset = offset >>> 0
if (!noAssert) checkInt(this, value, offset, 1, 0xff, 0)
this[offset] = (value & 0xff)
return offset + 1
}
Buffer.prototype.writeUInt16LE = function writeUInt16LE (value, offset, noAssert) {
value = +value
offset = offset >>> 0
if (!noAssert) checkInt(this, value, offset, 2, 0xffff, 0)
this[offset] = (value & 0xff)
this[offset + 1] = (value >>> 8)
return offset + 2
}
Buffer.prototype.writeUInt16BE = function writeUInt16BE (value, offset, noAssert) {
value = +value
offset = offset >>> 0
if (!noAssert) checkInt(this, value, offset, 2, 0xffff, 0)
this[offset] = (value >>> 8)
this[offset + 1] = (value & 0xff)
return offset + 2
}
Buffer.prototype.writeUInt32LE = function writeUInt32LE (value, offset, noAssert) {
value = +value
offset = offset >>> 0
if (!noAssert) checkInt(this, value, offset, 4, 0xffffffff, 0)
this[offset + 3] = (value >>> 24)
this[offset + 2] = (value >>> 16)
this[offset + 1] = (value >>> 8)
this[offset] = (value & 0xff)
return offset + 4
}
Buffer.prototype.writeUInt32BE = function writeUInt32BE (value, offset, noAssert) {
value = +value
offset = offset >>> 0
if (!noAssert) checkInt(this, value, offset, 4, 0xffffffff, 0)
this[offset] = (value >>> 24)
this[offset + 1] = (value >>> 16)
this[offset + 2] = (value >>> 8)
this[offset + 3] = (value & 0xff)
return offset + 4
}
Buffer.prototype.writeIntLE = function writeIntLE (value, offset, byteLength, noAssert) {
value = +value
offset = offset >>> 0
if (!noAssert) {
var limit = Math.pow(2, (8 * byteLength) - 1)
checkInt(this, value, offset, byteLength, limit - 1, -limit)
}
var i = 0
var mul = 1
var sub = 0
this[offset] = value & 0xFF
while (++i < byteLength && (mul *= 0x100)) {
if (value < 0 && sub === 0 && this[offset + i - 1] !== 0) {
sub = 1
}
this[offset + i] = ((value / mul) >> 0) - sub & 0xFF
}
return offset + byteLength
}
Buffer.prototype.writeIntBE = function writeIntBE (value, offset, byteLength, noAssert) {
value = +value
offset = offset >>> 0
if (!noAssert) {
var limit = Math.pow(2, (8 * byteLength) - 1)
checkInt(this, value, offset, byteLength, limit - 1, -limit)
}
var i = byteLength - 1
var mul = 1
var sub = 0
this[offset + i] = value & 0xFF
while (--i >= 0 && (mul *= 0x100)) {
if (value < 0 && sub === 0 && this[offset + i + 1] !== 0) {
sub = 1
}
this[offset + i] = ((value / mul) >> 0) - sub & 0xFF
}
return offset + byteLength
}
Buffer.prototype.writeInt8 = function writeInt8 (value, offset, noAssert) {
value = +value
offset = offset >>> 0
if (!noAssert) checkInt(this, value, offset, 1, 0x7f, -0x80)
if (value < 0) value = 0xff + value + 1
this[offset] = (value & 0xff)
return offset + 1
}
Buffer.prototype.writeInt16LE = function writeInt16LE (value, offset, noAssert) {
value = +value
offset = offset >>> 0
if (!noAssert) checkInt(this, value, offset, 2, 0x7fff, -0x8000)
this[offset] = (value & 0xff)
this[offset + 1] = (value >>> 8)
return offset + 2
}
Buffer.prototype.writeInt16BE = function writeInt16BE (value, offset, noAssert) {
value = +value
offset = offset >>> 0
if (!noAssert) checkInt(this, value, offset, 2, 0x7fff, -0x8000)
this[offset] = (value >>> 8)
this[offset + 1] = (value & 0xff)
return offset + 2
}
Buffer.prototype.writeInt32LE = function writeInt32LE (value, offset, noAssert) {
value = +value
offset = offset >>> 0
if (!noAssert) checkInt(this, value, offset, 4, 0x7fffffff, -0x80000000)
this[offset] = (value & 0xff)
this[offset + 1] = (value >>> 8)
this[offset + 2] = (value >>> 16)
this[offset + 3] = (value >>> 24)
return offset + 4
}
Buffer.prototype.writeInt32BE = function writeInt32BE (value, offset, noAssert) {
value = +value
offset = offset >>> 0
if (!noAssert) checkInt(this, value, offset, 4, 0x7fffffff, -0x80000000)
if (value < 0) value = 0xffffffff + value + 1
this[offset] = (value >>> 24)
this[offset + 1] = (value >>> 16)
this[offset + 2] = (value >>> 8)
this[offset + 3] = (value & 0xff)
return offset + 4
}
function checkIEEE754 (buf, value, offset, ext, max, min) {
if (offset + ext > buf.length) throw new RangeError('Index out of range')
if (offset < 0) throw new RangeError('Index out of range')
}
function writeFloat (buf, value, offset, littleEndian, noAssert) {
value = +value
offset = offset >>> 0
if (!noAssert) {
checkIEEE754(buf, value, offset, 4, 3.4028234663852886e+38, -3.4028234663852886e+38)
}
ieee754.write(buf, value, offset, littleEndian, 23, 4)
return offset + 4
}
Buffer.prototype.writeFloatLE = function writeFloatLE (value, offset, noAssert) {
return writeFloat(this, value, offset, true, noAssert)
}
Buffer.prototype.writeFloatBE = function writeFloatBE (value, offset, noAssert) {
return writeFloat(this, value, offset, false, noAssert)
}
function writeDouble (buf, value, offset, littleEndian, noAssert) {
value = +value
offset = offset >>> 0
if (!noAssert) {
checkIEEE754(buf, value, offset, 8, 1.7976931348623157E+308, -1.7976931348623157E+308)
}
ieee754.write(buf, value, offset, littleEndian, 52, 8)
return offset + 8
}
Buffer.prototype.writeDoubleLE = function writeDoubleLE (value, offset, noAssert) {
return writeDouble(this, value, offset, true, noAssert)
}
Buffer.prototype.writeDoubleBE = function writeDoubleBE (value, offset, noAssert) {
return writeDouble(this, value, offset, false, noAssert)
}
// copy(targetBuffer, targetStart=0, sourceStart=0, sourceEnd=buffer.length)
Buffer.prototype.copy = function copy (target, targetStart, start, end) {
if (!Buffer.isBuffer(target)) throw new TypeError('argument should be a Buffer')
if (!start) start = 0
if (!end && end !== 0) end = this.length
if (targetStart >= target.length) targetStart = target.length
if (!targetStart) targetStart = 0
if (end > 0 && end < start) end = start
// Copy 0 bytes; we're done
if (end === start) return 0
if (target.length === 0 || this.length === 0) return 0
// Fatal error conditions
if (targetStart < 0) {
throw new RangeError('targetStart out of bounds')
}
if (start < 0 || start >= this.length) throw new RangeError('Index out of range')
if (end < 0) throw new RangeError('sourceEnd out of bounds')
// Are we oob?
if (end > this.length) end = this.length
if (target.length - targetStart < end - start) {
end = target.length - targetStart + start
}
var len = end - start
if (this === target && typeof Uint8Array.prototype.copyWithin === 'function') {
// Use built-in when available, missing from IE11
this.copyWithin(targetStart, start, end)
} else if (this === target && start < targetStart && targetStart < end) {
// descending copy from end
for (var i = len - 1; i >= 0; --i) {
target[i + targetStart] = this[i + start]
}
} else {
Uint8Array.prototype.set.call(
target,
this.subarray(start, end),
targetStart
)
}
return len
}
// Usage:
// buffer.fill(number[, offset[, end]])
// buffer.fill(buffer[, offset[, end]])
// buffer.fill(string[, offset[, end]][, encoding])
Buffer.prototype.fill = function fill (val, start, end, encoding) {
// Handle string cases:
if (typeof val === 'string') {
if (typeof start === 'string') {
encoding = start
start = 0
end = this.length
} else if (typeof end === 'string') {
encoding = end
end = this.length
}
if (encoding !== undefined && typeof encoding !== 'string') {
throw new TypeError('encoding must be a string')
}
if (typeof encoding === 'string' && !Buffer.isEncoding(encoding)) {
throw new TypeError('Unknown encoding: ' + encoding)
}
if (val.length === 1) {
var code = val.charCodeAt(0)
if ((encoding === 'utf8' && code < 128) ||
encoding === 'latin1') {
// Fast path: If `val` fits into a single byte, use that numeric value.
val = code
}
}
} else if (typeof val === 'number') {
val = val & 255
}
// Invalid ranges are not set to a default, so can range check early.
if (start < 0 || this.length < start || this.length < end) {
throw new RangeError('Out of range index')
}
if (end <= start) {
return this
}
start = start >>> 0
end = end === undefined ? this.length : end >>> 0
if (!val) val = 0
var i
if (typeof val === 'number') {
for (i = start; i < end; ++i) {
this[i] = val
}
} else {
var bytes = Buffer.isBuffer(val)
? val
: Buffer.from(val, encoding)
var len = bytes.length
if (len === 0) {
throw new TypeError('The value "' + val +
'" is invalid for argument "value"')
}
for (i = 0; i < end - start; ++i) {
this[i + start] = bytes[i % len]
}
}
return this
}
// HELPER FUNCTIONS
// ================
var INVALID_BASE64_RE = /[^+/0-9A-Za-z-_]/g
function base64clean (str) {
// Node takes equal signs as end of the Base64 encoding
str = str.split('=')[0]
// Node strips out invalid characters like \n and \t from the string, base64-js does not
str = str.trim().replace(INVALID_BASE64_RE, '')
// Node converts strings with length < 2 to ''
if (str.length < 2) return ''
// Node allows for non-padded base64 strings (missing trailing ===), base64-js does not
while (str.length % 4 !== 0) {
str = str + '='
}
return str
}
function toHex (n) {
if (n < 16) return '0' + n.toString(16)
return n.toString(16)
}
function utf8ToBytes (string, units) {
units = units || Infinity
var codePoint
var length = string.length
var leadSurrogate = null
var bytes = []
for (var i = 0; i < length; ++i) {
codePoint = string.charCodeAt(i)
// is surrogate component
if (codePoint > 0xD7FF && codePoint < 0xE000) {
// last char was a lead
if (!leadSurrogate) {
// no lead yet
if (codePoint > 0xDBFF) {
// unexpected trail
if ((units -= 3) > -1) bytes.push(0xEF, 0xBF, 0xBD)
continue
} else if (i + 1 === length) {
// unpaired lead
if ((units -= 3) > -1) bytes.push(0xEF, 0xBF, 0xBD)
continue
}
// valid lead
leadSurrogate = codePoint
continue
}
// 2 leads in a row
if (codePoint < 0xDC00) {
if ((units -= 3) > -1) bytes.push(0xEF, 0xBF, 0xBD)
leadSurrogate = codePoint
continue
}
// valid surrogate pair
codePoint = (leadSurrogate - 0xD800 << 10 | codePoint - 0xDC00) + 0x10000
} else if (leadSurrogate) {
// valid bmp char, but last char was a lead
if ((units -= 3) > -1) bytes.push(0xEF, 0xBF, 0xBD)
}
leadSurrogate = null
// encode utf8
if (codePoint < 0x80) {
if ((units -= 1) < 0) break
bytes.push(codePoint)
} else if (codePoint < 0x800) {
if ((units -= 2) < 0) break
bytes.push(
codePoint >> 0x6 | 0xC0,
codePoint & 0x3F | 0x80
)
} else if (codePoint < 0x10000) {
if ((units -= 3) < 0) break
bytes.push(
codePoint >> 0xC | 0xE0,
codePoint >> 0x6 & 0x3F | 0x80,
codePoint & 0x3F | 0x80
)
} else if (codePoint < 0x110000) {
if ((units -= 4) < 0) break
bytes.push(
codePoint >> 0x12 | 0xF0,
codePoint >> 0xC & 0x3F | 0x80,
codePoint >> 0x6 & 0x3F | 0x80,
codePoint & 0x3F | 0x80
)
} else {
throw new Error('Invalid code point')
}
}
return bytes
}
function asciiToBytes (str) {
var byteArray = []
for (var i = 0; i < str.length; ++i) {
// Node's code seems to be doing this and not & 0x7F..
byteArray.push(str.charCodeAt(i) & 0xFF)
}
return byteArray
}
function utf16leToBytes (str, units) {
var c, hi, lo
var byteArray = []
for (var i = 0; i < str.length; ++i) {
if ((units -= 2) < 0) break
c = str.charCodeAt(i)
hi = c >> 8
lo = c % 256
byteArray.push(lo)
byteArray.push(hi)
}
return byteArray
}
function base64ToBytes (str) {
return base64.toByteArray(base64clean(str))
}
function blitBuffer (src, dst, offset, length) {
for (var i = 0; i < length; ++i) {
if ((i + offset >= dst.length) || (i >= src.length)) break
dst[i + offset] = src[i]
}
return i
}
// ArrayBuffer or Uint8Array objects from other contexts (i.e. iframes) do not pass
// the `instanceof` check but they should be treated as of that type.
// See: https://github.com/feross/buffer/issues/166
function isInstance (obj, type) {
return obj instanceof type ||
(obj != null && obj.constructor != null && obj.constructor.name != null &&
obj.constructor.name === type.name)
}
function numberIsNaN (obj) {
// For IE11 support
return obj !== obj // eslint-disable-line no-self-compare
}
}).call(this,require("buffer").Buffer)
},{"base64-js":1,"buffer":2,"ieee754":3}],3:[function(require,module,exports){
exports.read = function (buffer, offset, isLE, mLen, nBytes) {
var e, m
var eLen = (nBytes * 8) - mLen - 1
var eMax = (1 << eLen) - 1
var eBias = eMax >> 1
var nBits = -7
var i = isLE ? (nBytes - 1) : 0
var d = isLE ? -1 : 1
var s = buffer[offset + i]
i += d
e = s & ((1 << (-nBits)) - 1)
s >>= (-nBits)
nBits += eLen
for (; nBits > 0; e = (e * 256) + buffer[offset + i], i += d, nBits -= 8) {}
m = e & ((1 << (-nBits)) - 1)
e >>= (-nBits)
nBits += mLen
for (; nBits > 0; m = (m * 256) + buffer[offset + i], i += d, nBits -= 8) {}
if (e === 0) {
e = 1 - eBias
} else if (e === eMax) {
return m ? NaN : ((s ? -1 : 1) * Infinity)
} else {
m = m + Math.pow(2, mLen)
e = e - eBias
}
return (s ? -1 : 1) * m * Math.pow(2, e - mLen)
}
exports.write = function (buffer, value, offset, isLE, mLen, nBytes) {
var e, m, c
var eLen = (nBytes * 8) - mLen - 1
var eMax = (1 << eLen) - 1
var eBias = eMax >> 1
var rt = (mLen === 23 ? Math.pow(2, -24) - Math.pow(2, -77) : 0)
var i = isLE ? 0 : (nBytes - 1)
var d = isLE ? 1 : -1
var s = value < 0 || (value === 0 && 1 / value < 0) ? 1 : 0
value = Math.abs(value)
if (isNaN(value) || value === Infinity) {
m = isNaN(value) ? 1 : 0
e = eMax
} else {
e = Math.floor(Math.log(value) / Math.LN2)
if (value * (c = Math.pow(2, -e)) < 1) {
e--
c *= 2
}
if (e + eBias >= 1) {
value += rt / c
} else {
value += rt * Math.pow(2, 1 - eBias)
}
if (value * c >= 2) {
e++
c /= 2
}
if (e + eBias >= eMax) {
m = 0
e = eMax
} else if (e + eBias >= 1) {
m = ((value * c) - 1) * Math.pow(2, mLen)
e = e + eBias
} else {
m = value * Math.pow(2, eBias - 1) * Math.pow(2, mLen)
e = 0
}
}
for (; mLen >= 8; buffer[offset + i] = m & 0xff, i += d, m /= 256, mLen -= 8) {}
e = (e << mLen) | m
eLen += mLen
for (; eLen > 0; buffer[offset + i] = e & 0xff, i += d, e /= 256, eLen -= 8) {}
buffer[offset + i - d] |= s * 128
}
},{}],4:[function(require,module,exports){
// shim for using process in browser
var process = module.exports = {};
// cached from whatever global is present so that test runners that stub it
// don't break things. But we need to wrap it in a try catch in case it is
// wrapped in strict mode code which doesn't define any globals. It's inside a
// function because try/catches deoptimize in certain engines.
var cachedSetTimeout;
var cachedClearTimeout;
function defaultSetTimout() {
throw new Error('setTimeout has not been defined');
}
function defaultClearTimeout () {
throw new Error('clearTimeout has not been defined');
}
(function () {
try {
if (typeof setTimeout === 'function') {
cachedSetTimeout = setTimeout;
} else {
cachedSetTimeout = defaultSetTimout;
}
} catch (e) {
cachedSetTimeout = defaultSetTimout;
}
try {
if (typeof clearTimeout === 'function') {
cachedClearTimeout = clearTimeout;
} else {
cachedClearTimeout = defaultClearTimeout;
}
} catch (e) {
cachedClearTimeout = defaultClearTimeout;
}
} ())
function runTimeout(fun) {
if (cachedSetTimeout === setTimeout) {
//normal enviroments in sane situations
return setTimeout(fun, 0);
}
// if setTimeout wasn't available but was latter defined
if ((cachedSetTimeout === defaultSetTimout || !cachedSetTimeout) && setTimeout) {
cachedSetTimeout = setTimeout;
return setTimeout(fun, 0);
}
try {
// when when somebody has screwed with setTimeout but no I.E. maddness
return cachedSetTimeout(fun, 0);
} catch(e){
try {
// When we are in I.E. but the script has been evaled so I.E. doesn't trust the global object when called normally
return cachedSetTimeout.call(null, fun, 0);
} catch(e){
// same as above but when it's a version of I.E. that must have the global object for 'this', hopfully our context correct otherwise it will throw a global error
return cachedSetTimeout.call(this, fun, 0);
}
}
}
function runClearTimeout(marker) {
if (cachedClearTimeout === clearTimeout) {
//normal enviroments in sane situations
return clearTimeout(marker);
}
// if clearTimeout wasn't available but was latter defined
if ((cachedClearTimeout === defaultClearTimeout || !cachedClearTimeout) && clearTimeout) {
cachedClearTimeout = clearTimeout;
return clearTimeout(marker);
}
try {
// when when somebody has screwed with setTimeout but no I.E. maddness
return cachedClearTimeout(marker);
} catch (e){
try {
// When we are in I.E. but the script has been evaled so I.E. doesn't trust the global object when called normally
return cachedClearTimeout.call(null, marker);
} catch (e){
// same as above but when it's a version of I.E. that must have the global object for 'this', hopfully our context correct otherwise it will throw a global error.
// Some versions of I.E. have different rules for clearTimeout vs setTimeout
return cachedClearTimeout.call(this, marker);
}
}
}
var queue = [];
var draining = false;
var currentQueue;
var queueIndex = -1;
function cleanUpNextTick() {
if (!draining || !currentQueue) {
return;
}
draining = false;
if (currentQueue.length) {
queue = currentQueue.concat(queue);
} else {
queueIndex = -1;
}
if (queue.length) {
drainQueue();
}
}
function drainQueue() {
if (draining) {
return;
}
var timeout = runTimeout(cleanUpNextTick);
draining = true;
var len = queue.length;
while(len) {
currentQueue = queue;
queue = [];
while (++queueIndex < len) {
if (currentQueue) {
currentQueue[queueIndex].run();
}
}
queueIndex = -1;
len = queue.length;
}
currentQueue = null;
draining = false;
runClearTimeout(timeout);
}
process.nextTick = function (fun) {
var args = new Array(arguments.length - 1);
if (arguments.length > 1) {
for (var i = 1; i < arguments.length; i++) {
args[i - 1] = arguments[i];
}
}
queue.push(new Item(fun, args));
if (queue.length === 1 && !draining) {
runTimeout(drainQueue);
}
};
// v8 likes predictible objects
function Item(fun, array) {
this.fun = fun;
this.array = array;
}
Item.prototype.run = function () {
this.fun.apply(null, this.array);
};
process.title = 'browser';
process.browser = true;
process.env = {};
process.argv = [];
process.version = ''; // empty string to avoid regexp issues
process.versions = {};
function noop() {}
process.on = noop;
process.addListener = noop;
process.once = noop;
process.off = noop;
process.removeListener = noop;
process.removeAllListeners = noop;
process.emit = noop;
process.prependListener = noop;
process.prependOnceListener = noop;
process.listeners = function (name) { return [] }
process.binding = function (name) {
throw new Error('process.binding is not supported');
};
process.cwd = function () { return '/' };
process.chdir = function (dir) {
throw new Error('process.chdir is not supported');
};
process.umask = function() { return 0; };
},{}],5:[function(require,module,exports){
(function (Buffer){
'use strict';
var Assert = {};
Assert.GE = function(key, value, bound) {
if (!Number.isInteger(value)) throw new Error(key + ' must be an integer');
if (!Number.isInteger(bound)) throw new Error(key + ' bound not an integer');
if (value < bound) throw new Error(key + ' must be at least ' + bound);
};
Assert.LE = function(key, value, bound) {
if (!Number.isInteger(value)) throw new Error(key + ' must be an integer');
if (!Number.isInteger(bound)) throw new Error(key + ' bound not an integer');
if (value > bound) throw new Error(key + ' must be at most ' + bound);
};
Assert.P2 = function(key, value) {
if (!Number.isInteger(value)) throw new Error(key + ' must be an integer');
if (value <= 0) throw new Error(key + ' must be greater than 0');
if (value & (value - 1)) throw new Error(key + ' must be a power of 2');
};
// Hashes assigned by Hash() instead of using multiple return destructuring:
// We want to avoid allocating millions of objects just to return 2 hashes.
var H1 = 0;
var H2 = 0;
// Tabulation hash function:
function Hash(key, keyOffset, keySize) {
// Assigning to a local variable is faster than to a global variable:
var h1 = 0;
var h2 = 0;
var i = 0;
while (i < keySize) {
// Minimize cache misses by interleaving both tables into a single table:
// Minimize variable assignments by reusing k as an index into TABLE:
// Unrolled to process 4 bytes at a time:
h1 ^= (
TABLE[(((i << 1) + 0) << 8) + key[keyOffset + i + 0]] ^
TABLE[(((i << 1) + 1) << 8) + key[keyOffset + i + 1]] ^
TABLE[(((i << 1) + 2) << 8) + key[keyOffset + i + 2]] ^
TABLE[(((i << 1) + 3) << 8) + key[keyOffset + i + 3]]
);
h2 ^= (
TABLE[(((i << 1) + 4) << 8) + key[keyOffset + i + 0]] ^
TABLE[(((i << 1) + 5) << 8) + key[keyOffset + i + 1]] ^
TABLE[(((i << 1) + 6) << 8) + key[keyOffset + i + 2]] ^
TABLE[(((i << 1) + 7) << 8) + key[keyOffset + i + 3]]
);
i += 4;
}
H1 = h1;
H2 = h2;
}
// Slot lookup table, given 8-bits, return the index of an empty slot (if any):
// We use this to find an empty slot in a single branch.
var SLOT = (function() {
var slots = 8;
var table = new Uint8Array(1 << slots);
for (var index = 0; index < table.length; index++) {
for (var slot = 0; slot < slots; slot++) {
if ((index & (1 << slot)) === 0) break;
}
table[index] = slot;
}
return table;
})();
// Interleaved entropy table used by tabulation hash function:
var TABLE = (function() {
var word = 4;
var table = new Int32Array(64 * 256 * 2);
var buffer = require('randombytes')(table.length * word);
for (var index = 0, length = table.length; index < length; index++) {
table[index] = buffer.readInt32LE(index * word);
}
return table;
})();
// A fallback for when valueSize is 0 and the user does not pass a value buffer:
var VALUE = Buffer.alloc(0);
function HashTable(keySize, valueSize, elementsMin=1024, elementsMax=0) {
Assert.GE('keySize', keySize, HashTable.KEY_MIN);
Assert.LE('keySize', keySize, HashTable.KEY_MAX);
// We optimize the hash function significantly given key is a multiple of 4:
if (keySize % 4) throw new Error('keySize must be a multiple of 4');
Assert.GE('valueSize', valueSize, HashTable.VALUE_MIN);
Assert.LE('valueSize', valueSize, HashTable.VALUE_MAX);
Assert.GE('elementsMin', elementsMin, HashTable.ELEMENTS_MIN);
Assert.LE('elementsMin', elementsMin, HashTable.ELEMENTS_MAX);
if (elementsMax === 0) {
elementsMax = Math.max(elementsMin + 4194304, elementsMin * 1024);
elementsMax = Math.min(elementsMax, HashTable.ELEMENTS_MAX);
}
Assert.GE('elementsMax', elementsMax, 1);
Assert.GE('elementsMax', elementsMax, elementsMin);
Assert.LE('elementsMax', elementsMax, HashTable.ELEMENTS_MAX);
var capacityMin = HashTable.capacity(elementsMin);
var capacityMax = HashTable.capacity(elementsMax);
var buffers = HashTable.buffers(keySize, valueSize, capacityMax);
Assert.GE('buffers', buffers, HashTable.BUFFERS_MIN);
Assert.LE('buffers', buffers, HashTable.BUFFERS_MAX);
Assert.P2('buffers', buffers);
var buckets = HashTable.buckets(capacityMin, buffers);
if (buckets > HashTable.BUCKETS_MAX) buckets = HashTable.BUCKETS_MAX;
Assert.GE('buckets', buckets, HashTable.BUCKETS_MIN);
Assert.LE('buckets', buckets, HashTable.BUCKETS_MAX);
Assert.P2('buckets', buckets);
this.keySize = keySize;
this.valueSize = valueSize;
this.bucket = HashTable.bucket(keySize, valueSize);
this.capacity = buffers * buckets * 8;
this.length = 0;
this.mask = buffers - 1;
this.mode = 0; // 1 = resizing with set(), 2 = evicting with cache().
if (
this.capacity < elementsMin ||
this.bucket * buckets > HashTable.BUFFER_MAX
) {
throw new Error(HashTable.ERROR_MAXIMUM_CAPACITY_EXCEEDED);
}
this.tables = new Array(buffers);
for (var offset = 0; offset < buffers; offset++) {
this.tables[offset] = new Table(keySize, valueSize, this.bucket, buckets);
}
}
HashTable.prototype.cache = function(key, keyOffset, value, valueOffset) {
if (this.mode === 1) throw new Error(HashTable.ERROR_MODE);
this.mode = 2;
if (this.valueSize === 0) {
value = VALUE;
valueOffset = 0;
}
Hash(key, keyOffset, this.keySize);
var table = this.tables[(((H1 >> 24) << 8) | (H2 >> 24)) & this.mask];
var result = table.cache(H1, H2, key, keyOffset, value, valueOffset);
if (result === 0) this.length++;
return result;
};
HashTable.prototype.exist = function(key, keyOffset) {
Hash(key, keyOffset, this.keySize);
var table = this.tables[(((H1 >> 24) << 8) | (H2 >> 24)) & this.mask];
return table.exist(H1, H2, key, keyOffset);
};
HashTable.prototype.get = function(key, keyOffset, value, valueOffset) {
if (this.valueSize === 0) {
value = VALUE;
valueOffset = 0;
}
Hash(key, keyOffset, this.keySize);
var table = this.tables[(((H1 >> 24) << 8) | (H2 >> 24)) & this.mask];
return table.get(H1, H2, key, keyOffset, value, valueOffset);
};
Object.defineProperty(HashTable.prototype, 'load', {
get: function() {
return this.length / this.capacity;
}
});
HashTable.prototype.set = function(key, keyOffset, value, valueOffset) {
if (this.mode === 2) throw new Error(HashTable.ERROR_MODE);
this.mode = 1;
if (this.valueSize === 0) {
value = VALUE;
valueOffset = 0;
}
Hash(key, keyOffset, this.keySize);
var h1 = H1;
var h2 = H2;
var table = this.tables[(((h1 >> 24) << 8) | (h2 >> 24)) & this.mask];
var result = table.set(h1, h2, key, keyOffset, value, valueOffset);
if (result === 1) return 1;
if (result === 0) {
this.length++;
return 0;
}
for (var resize = 1; resize <= 2; resize++) {
var buckets = table.buckets;
if (table.resize(buckets << resize)) {
this.capacity -= buckets * 8;
this.capacity += table.buckets * 8;
var result = table.set(h1, h2, key, keyOffset, value, valueOffset);
if (result === 1) return 1;
if (result === 0) {
this.length++;
return 0;
}
}
}
throw new Error(HashTable.ERROR_SET);
};
Object.defineProperty(HashTable.prototype, 'size', {
get: function() {
var size = this.capacity / 8 * this.bucket;
Assert.GE('size', size, 0);
return size;
}
});
HashTable.prototype.unset = function(key, keyOffset) {
Hash(key, keyOffset, this.keySize);
var table = this.tables[(((H1 >> 24) << 8) | (H2 >> 24)) & this.mask];
var result = table.unset(H1, H2, key, keyOffset);
if (result === 1) this.length--;
return result;
};
// Constants:
HashTable.KEY_MIN = 4;
HashTable.KEY_MAX = 64;
HashTable.VALUE_MIN = 0;
HashTable.VALUE_MAX = 1048576; // See comments in HashTable.buffers().
HashTable.BUFFERS_MIN = 1;
HashTable.BUFFERS_MAX = 8192; // Javascript Arrays degrade at 10,000 elements.
HashTable.ELEMENTS_MIN = 0;
HashTable.ELEMENTS_MAX = 4294967296;
HashTable.BUCKETS_MIN = 2;
HashTable.BUCKETS_MAX = 65536;
HashTable.BUFFER_MAX = require('buffer').kMaxLength;
Assert.GE('BUFFER_MAX', HashTable.BUFFER_MAX, 0);
Assert.LE('BUFFER_MAX', HashTable.BUFFER_MAX, Math.pow(2, 32) - 1);
Assert.LE(
'ELEMENTS_MAX',
HashTable.ELEMENTS_MAX,
HashTable.BUFFERS_MAX * HashTable.BUCKETS_MAX * 8
);
Assert.GE('SLOT.length', SLOT.length, 256);
Assert.LE('SLOT.length', SLOT.length, 256);
Assert.GE('TABLE.length', TABLE.length, HashTable.KEY_MAX * 256 * 2);
Assert.LE('TABLE.length', TABLE.length, HashTable.KEY_MAX * 256 * 2);
// Too many elements or buffer allocation limit reached, add more buffers:
HashTable.ERROR_MAXIMUM_CAPACITY_EXCEEDED = 'maximum capacity exceeded';
// cache() and set() methods are mutually exclusive:
// Once cache() is called, the table switches to non-resizing, caching mode.
// Once set() is called, the table switches to resizing, second position mode.
// This enables several optimizations and is safer:
// 1. cache() does not need to scan second position for an element.
// 2. cache() can assume all elements are in first position when refiltering.
// 3. cache() might otherwise evict an element that was inserted using set().
HashTable.ERROR_MODE = 'cache() and set() methods are mutually exclusive';
// This might indicate an adversarial attack, or weak tabulation hash entropy:
HashTable.ERROR_SET = 'set() failed despite multiple resize attempts';
// The size of a cache-aligned bucket, given keySize and valueSize:
HashTable.bucket = function(keySize, valueSize) {
Assert.GE('keySize', keySize, HashTable.KEY_MIN);
Assert.LE('keySize', keySize, HashTable.KEY_MAX);
if (keySize % 4) throw new Error('keySize must be a multiple of 4');
Assert.GE('valueSize', valueSize, HashTable.VALUE_MIN);
Assert.LE('valueSize', valueSize, HashTable.VALUE_MAX);
// Bucket includes padding for 64-byte cache line alignment:
var bucket = Math.ceil((20 + (keySize + valueSize) * 8) / 64) * 64;
Assert.GE('bucket', bucket, 0);
return bucket;
};
// The number of buckets required to support elements at 100% load factor:
HashTable.buckets = function(elements, buffers) {
Assert.GE('elements', elements, HashTable.ELEMENTS_MIN);
Assert.LE('elements', elements, HashTable.ELEMENTS_MAX);
Assert.GE('buffers', buffers, HashTable.BUFFERS_MIN);
Assert.LE('buffers', buffers, HashTable.BUFFERS_MAX);
Assert.P2('buffers', buffers);
var power = Math.ceil(Math.log2(Math.max(1, elements / 8 / buffers)));
var buckets = Math.max(HashTable.BUCKETS_MIN, Math.pow(2, power));
Assert.GE('buckets', buckets, HashTable.BUCKETS_MIN);
// Buckets may exceed BUCKETS_MAX here so that buffers() can call buckets().
Assert.P2('buckets', buckets);
return buckets;
};
// The number of buffers required to support elements at 100% load factor:
HashTable.buffers = function(keySize, valueSize, elements) {
// Objectives:
//
// 1. Maximize the number of buckets (>= 64) for maximum load factor.
// 2. Minimize the number of buffers for less pointer overhead.
//
// The number of buckets places an upper bound on the maximum load factor:
// If, at maximum capacity, the number of buckets is less than 64 then the
// maximum load factor will be less than 100% (even when evicting).
//
// 64 buckets enable a maximum load factor of 100%.
// 32 buckets enable a maximum load factor of 75%.
// 16 buckets enable a maximum load factor of 62.5%.
// 8 buckets enable a maximum load factor of 56.25%.
// 4 buckets enable a maximum load factor of 53.125%.
// 2 buckets enable a maximum load factor of 51.5625%.
//
// Large value sizes interacting with BUFFER_MAX tend toward fewer buckets:
//
// When BUFFER_MAX is 2 GB, for all key and value size configurations:
// A value size of 1 MB guarantees 128 buckets.
// A value size of 2 MB guarantees 64 buckets.
// A value size of 4 MB guarantees 32 buckets.
//
// When BUFFER_MAX is 1 GB:
// A value size of 1 MB guarantees 64 buckets.
// A value size of 2 MB guarantees 32 buckets.
// A value size of 4 MB guarantees 16 buckets.
//
// We therefore set VALUE_MAX to 1 MB to preclude the possibility of a cache
// ever being artificially restricted to 75% occupancy (even when evicting).
//
// The above guarantees depend on KEY_MAX, VALUE_MAX and BUFFER_MAX:
Assert.LE('HashTable.KEY_MAX', HashTable.KEY_MAX, 64);
Assert.LE('HashTable.VALUE_MAX', HashTable.VALUE_MAX, 1048576);
Assert.GE('HashTable.BUFFER_MAX', HashTable.BUFFER_MAX, 1073741824 - 1);
Assert.GE('keySize', keySize, HashTable.KEY_MIN);
Assert.LE('keySize', keySize, HashTable.KEY_MAX);
if (keySize % 4) throw new Error('keySize must be a multiple of 4');
Assert.GE('valueSize', valueSize, HashTable.VALUE_MIN);
Assert.LE('valueSize', valueSize, HashTable.VALUE_MAX);
Assert.GE('elements', elements, HashTable.ELEMENTS_MIN);
Assert.LE('elements', elements, HashTable.ELEMENTS_MAX);
var bucket = HashTable.bucket(keySize, valueSize);
var buffers = HashTable.BUFFERS_MIN;
Assert.GE('buffers', buffers, 1);
var limit = 10000;
while (limit--) {
var buckets = HashTable.buckets(elements, buffers);
var buffer = buckets * bucket;
if (
(buffers === HashTable.BUFFERS_MAX) ||
(buckets <= HashTable.BUCKETS_MAX && buffer <= HashTable.BUFFER_MAX)
) {
break;
}
buffers = buffers * 2;
}
Assert.GE('buffers', buffers, HashTable.BUFFERS_MIN);
Assert.LE('buffers', buffers, HashTable.BUFFERS_MAX);
Assert.P2('buffers', buffers);
return buffers;
};
HashTable.capacity = function(elements) {
Assert.GE('elements', elements, HashTable.ELEMENTS_MIN);
Assert.LE('elements', elements, HashTable.ELEMENTS_MAX);
var capacity = Math.min(Math.floor(elements * 1.3), HashTable.ELEMENTS_MAX);
Assert.GE('capacity', capacity, elements);
return capacity;
};
function Table(keySize, valueSize, bucket, buckets) {
this.keySize = keySize;
this.valueSize = valueSize;
this.bucket = bucket;
this.buckets = buckets;
this.buffer = Buffer.alloc(this.bucket * this.buckets);
// Reduce branching through unrolled copy methods:
this.copyKey = this.copy(keySize) || this.copyKeyGeneric;
this.copyValue = this.copy(valueSize) || this.copyValueGeneric;
// Replace modulus with fast bitwise AND (buckets must be a power of 2):
this.mask = this.buckets - 1;
// Optimize global variable lookup:
this.SLOT = SLOT;
}
Table.prototype.assign = function(
bucket,
tag,
slot,
key,
keyOffset,
value,
valueOffset
) {
this.buffer[bucket + 9] |= (1 << slot); // Mark the slot as present.
this.buffer[bucket + 9 + 1 + slot] = tag; // Assign the element's tag.
this.copyKey(key, keyOffset, this.buffer, this.keyOffset(bucket, slot));
this.copyValue(
value,
valueOffset,
this.buffer,
this.valueOffset(bucket, slot)
);
};
Table.prototype.cache = function(h1, h2, key, keyOffset, value, valueOffset) {
// See comments in set():
var tag = (h1 >> 16) & 255;
var b1 = (h1 & this.mask) * this.bucket;
var b2 = (h2 & this.mask) * this.bucket;
var f1 = (tag >> 4) & 7;
var f2 = 1 << (tag & 7);
if (this.buffer[b1 + f1] & f2) {
var s1 = this.scan(b1, tag, key, keyOffset);
if (s1 < 8) {
// Mark the element as recently used:
this.buffer[b1 + 18] |= (1 << s1);
this.copyValue(value, valueOffset, this.buffer, this.valueOffset(b1, s1));
return 1;
}
}
// Evict the least recently used slot in first position:
var s3 = this.evict(b1);
var eviction = this.buffer[b1 + 9] & (1 << s3);
if (eviction) {
// Mark the slot as empty so that the element is excluded from its filter:
this.buffer[b1 + 9] &= ~(1 << s3);
// Reset the old element's filter:
this.filterReset(b1, this.buffer[b1 + 9 + 1 + s3] & 7);
}
// Add the new element in its place:
this.assign(b1, tag, s3, key, keyOffset, value, valueOffset);
// Add the new element to its filter (this can be a different filter):
this.buffer[b1 + f1] |= f2;
// Mark the element as recently used:
this.buffer[b1 + 18] |= (1 << s3);
return eviction ? 2 : 0;
};
Table.prototype.copy = function(size) {
switch (size) {
case 0: return this.copy00;
case 4: return this.copy04;
case 8: return this.copy08;
case 16: return this.copy16;
case 20: return this.copy20;
case 32: return this.copy32;
case 48: return this.copy48;
case 64: return this.copy64;
case 128: return this.copy128;
case 256: return this.copy256;
}
return undefined;
};
Table.prototype.copyKeyGeneric = function(s, sO, t, tO) {
var size = this.keySize;
var groups = size >>> 2;
while (groups--) {
t[tO + 0] = s[sO + 0];
t[tO + 1] = s[sO + 1];
t[tO + 2] = s[sO + 2];
t[tO + 3] = s[sO + 3];
tO += 4;
sO += 4;
size -= 4;
}
while (size--) t[tO++] = s[sO++];
};
Table.prototype.copyValueGeneric = function(s, sO, t, tO) {
var size = this.valueSize;
if (size < 128) {
var groups = size >>> 3;
while (groups--) {
t[tO + 0] = s[sO + 0];
t[tO + 1] = s[sO + 1];
t[tO + 2] = s[sO + 2];
t[tO + 3] = s[sO + 3];
t[tO + 4] = s[sO + 4];
t[tO + 5] = s[sO + 5];
t[tO + 6] = s[sO + 6];
t[tO + 7] = s[sO + 7];
tO += 8;
sO += 8;
size -= 8;
}
while (size--) t[tO++] = s[sO++];
} else {
s.copy(t, tO, sO, sO + size);
}
};
Table.prototype.copy00 = function(s, sO, t, tO) {};
Table.prototype.copy04 = function(s, sO, t, tO) {
t[tO + 0] = s[sO + 0];
t[tO + 1] = s[sO + 1];
t[tO + 2] = s[sO + 2];
t[tO + 3] = s[sO + 3];
};
Table.prototype.copy08 = function(s, sO, t, tO) {
t[tO + 0] = s[sO + 0];
t[tO + 1] = s[sO + 1];
t[tO + 2] = s[sO + 2];
t[tO + 3] = s[sO + 3];
t[tO + 4] = s[sO + 4];
t[tO + 5] = s[sO + 5];
t[tO + 6] = s[sO + 6];
t[tO + 7] = s[sO + 7];
};
Table.prototype.copy16 = function(s, sO, t, tO) {
t[tO + 0] = s[sO + 0];
t[tO + 1] = s[sO + 1];
t[tO + 2] = s[sO + 2];
t[tO + 3] = s[sO + 3];
t[tO + 4] = s[sO + 4];
t[tO + 5] = s[sO + 5];
t[tO + 6] = s[sO + 6];
t[tO + 7] = s[sO + 7];
t[tO + 8] = s[sO + 8];
t[tO + 9] = s[sO + 9];
t[tO + 10] = s[sO + 10];
t[tO + 11] = s[sO + 11];
t[tO + 12] = s[sO + 12];
t[tO + 13] = s[sO + 13];
t[tO + 14] = s[sO + 14];
t[tO + 15] = s[sO + 15];
};
Table.prototype.copy20 = function(s, sO, t, tO) {
t[tO + 0] = s[sO + 0];
t[tO + 1] = s[sO + 1];
t[tO + 2] = s[sO + 2];
t[tO + 3] = s[sO + 3];
t[tO + 4] = s[sO + 4];
t[tO + 5] = s[sO + 5];
t[tO + 6] = s[sO + 6];
t[tO + 7] = s[sO + 7];
t[tO + 8] = s[sO + 8];
t[tO + 9] = s[sO + 9];
t[tO + 10] = s[sO + 10];
t[tO + 11] = s[sO + 11];
t[tO + 12] = s[sO + 12];
t[tO + 13] = s[sO + 13];
t[tO + 14] = s[sO + 14];
t[tO + 15] = s[sO + 15];
t[tO + 16] = s[sO + 16];
t[tO + 17] = s[sO + 17];
t[tO + 18] = s[sO + 18];
t[tO + 19] = s[sO + 19];
};
Table.prototype.copy32 = function(s, sO, t, tO) {
t[tO + 0] = s[sO + 0];
t[tO + 1] = s[sO + 1];
t[tO + 2] = s[sO + 2];
t[tO + 3] = s[sO + 3];
t[tO + 4] = s[sO + 4];
t[tO + 5] = s[sO + 5];
t[tO + 6] = s[sO + 6];
t[tO + 7] = s[sO + 7];
t[tO + 8] = s[sO + 8];
t[tO + 9] = s[sO + 9];
t[tO + 10] = s[sO + 10];
t[tO + 11] = s[sO + 11];
t[tO + 12] = s[sO + 12];
t[tO + 13] = s[sO + 13];
t[tO + 14] = s[sO + 14];
t[tO + 15] = s[sO + 15];
t[tO + 16] = s[sO + 16];
t[tO + 17] = s[sO + 17];
t[tO + 18] = s[sO + 18];
t[tO + 19] = s[sO + 19];
t[tO + 20] = s[sO + 20];
t[tO + 21] = s[sO + 21];
t[tO + 22] = s[sO + 22];
t[tO + 23] = s[sO + 23];
t[tO + 24] = s[sO + 24];
t[tO + 25] = s[sO + 25];
t[tO + 26] = s[sO + 26];
t[tO + 27] = s[sO + 27];
t[tO + 28] = s[sO + 28];
t[tO + 29] = s[sO + 29];
t[tO + 30] = s[sO + 30];
t[tO + 31] = s[sO + 31];
};
Table.prototype.copy48 = function(s, sO, t, tO) {
this.copy32(s, sO + 0, t, tO + 0);
this.copy16(s, sO + 32, t, tO + 32);
};
Table.prototype.copy64 = function(s, sO, t, tO) {
this.copy32(s, sO + 0, t, tO + 0);
this.copy32(s, sO + 32, t, tO + 32);
};
Table.prototype.copy128 = function(s, sO, t, tO) {
this.copy32(s, sO + 0, t, tO + 0);
this.copy32(s, sO + 32, t, tO + 32);
this.copy32(s, sO + 64, t, tO + 64);
this.copy32(s, sO + 96, t, tO + 96);
};
Table.prototype.copy256 = function(s, sO, t, tO) {
this.copy32(s, sO + 0, t, tO + 0);
this.copy32(s, sO + 32, t, tO + 32);
this.copy32(s, sO + 64, t, tO + 64);
this.copy32(s, sO + 96, t, tO + 96);
this.copy32(s, sO + 128, t, tO + 128);
this.copy32(s, sO + 160, t, tO + 160);
this.copy32(s, sO + 192, t, tO + 192);
this.copy32(s, sO + 224, t, tO + 224);
};
Table.prototype.equal = function(a, aOffset, b, bOffset, size) {
while (size--) {
if (a[aOffset++] != b[bOffset++]) return 0;
}
return 1;
};
// Evict an element using the CLOCK eviction policy which approximates LRU:
Table.prototype.evict = function(bucket) {
// After the CLOCK hand wraps, we are guaranteed an eviction:
var tick = 8 + 1;
while (tick--) {
// Find the slot pointed to by CLOCK hand:
var slot = this.buffer[bucket + 18 + 1];
// Increment CLOCK hand regardless of whether slot was recently used:
this.buffer[bucket + 18 + 1] = (this.buffer[bucket + 18 + 1] + 1) & 7;
// Evict slot if slot was not recently used:
if ((this.buffer[bucket + 18] & (1 << slot)) === 0) break;
// Slot was recently used, clear recently used bit and keep ticking:
this.buffer[bucket + 18] &= ~(1 << slot);
}
return slot;
};
Table.prototype.exist = function(h1, h2, key, keyOffset) {
// See comments in set():
var tag = (h1 >> 16) & 255;
var b1 = (h1 & this.mask) * this.bucket;
var b2 = (h2 & this.mask) * this.bucket;
var f1 = (tag >> 4) & 7;
var f2 = 1 << (tag & 7);
if (this.buffer[b1 + f1] & f2) {
var s1 = this.scan(b1, tag, key, keyOffset);
if (s1 < 8) return 1;
var s2 = this.scan(b2, tag, key, keyOffset);
if (s2 < 8) return 1;
}
return 0;
};
// Decrement a filter's count of elements in second position:
Table.prototype.filterDecrementSecondPosition = function(bucket) {
if (this.buffer[bucket + 8] === 0) throw new Error('count should not be 0');
if (this.buffer[bucket + 8] < 255) {
this.buffer[bucket + 8]--;
if (this.buffer[bucket + 8] === 0) {
for (var filter = 0; filter < 8; filter++) {
this.filterReset(bucket, filter);
}
}
}
};
// Increment a filter's count of elements in second position:
Table.prototype.filterIncrementSecondPosition = function(bucket) {
// Once the counter saturates, it can no longer be incremented or decremented.
// This is extremely unlikely, we expect at most 4 elements and can count 254.
// Even if it does saturate, the worst is that we never reset the filter.
if (this.buffer[bucket + 8] < 255) this.buffer[bucket + 8]++;
};
// Reset a filter to remove stale entries:
Table.prototype.filterReset = function(bucket, filter) {
// Filter has elements in second position and cannot be reset:
if (this.buffer[bucket + 8] !== 0) return;
// Filter has no elements (since no bits are set):
if (this.buffer[bucket + filter] === 0) return;
// Reset filter and add elements back:
this.buffer[bucket + filter] = 0;
for (var slot = 0; slot < 8; slot++) {
// Slot must be present (not empty):
if (this.buffer[bucket + 9] & (1 << slot)) {
// Element must belong to the same filter (and be in first position):
// We do not check whether element is actually in second position.
// This would need special bookkeeping, is unlikely, and adds little.
var tag = this.buffer[bucket + 9 + 1 + slot];
var f1 = (tag >> 4) & 7;
if (f1 === filter) {
var f2 = 1 << (tag & 7);
this.buffer[bucket + filter] |= f2;
}
}
}
};
Table.prototype.get = function(h1, h2, key, keyOffset, value, valueOffset) {
// See comments in set():
var tag = (h1 >> 16) & 255;
var b1 = (h1 & this.mask) * this.bucket;
var b2 = (h2 & this.mask) * this.bucket;
var f1 = (tag >> 4) & 7;
var f2 = 1 << (tag & 7);
if (this.buffer[b1 + f1] & f2) {
var s1 = this.scan(b1, tag, key, keyOffset);
if (s1 < 8) {
// Mark element as recently used:
this.buffer[b1 + 18] |= (1 << s1);
this.copyValue(this.buffer, this.valueOffset(b1, s1), value, valueOffset);
return 1;
}
var s2 = this.scan(b2, tag, key, keyOffset);
if (s2 < 8) {
this.buffer[b2 + 18] |= (1 << s2);
this.copyValue(this.buffer, this.valueOffset(b2, s2), value, valueOffset);
return 1;
}
}
return 0;
};
Table.prototype.keyOffset = function(bucket, slot) {
// 20 = 8:Filter 1:FilterCount 1:Present 8:Tags 1:ClockUsed 1:ClockHand
// We keep the element's key and value together to optimize the common case of
// comparing the key and retrieving the value without a cache miss.
return bucket + 20 + (this.keySize + this.valueSize) * slot;
};
Table.prototype.resize = function(resizeBuckets) {
Assert.GE('resizeBuckets', resizeBuckets, this.buckets * 2);
Assert.P2('resizeBuckets', resizeBuckets);
if (
resizeBuckets > HashTable.BUCKETS_MAX ||
this.bucket * resizeBuckets > HashTable.BUFFER_MAX
) {
throw new Error(HashTable.ERROR_MAXIMUM_CAPACITY_EXCEEDED);
}
var buckets = this.buckets;
var buffer = this.buffer;
this.buckets = resizeBuckets;
this.buffer = Buffer.alloc(this.bucket * resizeBuckets);
this.mask = resizeBuckets - 1;
for (var index = 0; index < buckets; index++) {
var bucket = index * this.bucket;
for (var slot = 0; slot < 8; slot++) {
if (buffer[bucket + 9] & (1 << slot)) {
// We assume keyOffset, valueOffset depend only on bucket and slot:
var keyOffset = this.keyOffset(bucket, slot);
var valueOffset = this.valueOffset(bucket, slot);
Hash(buffer, keyOffset, this.keySize);
if (this.set(H1, H2, buffer, keyOffset, buffer, valueOffset) === -1) {
// Fail this resize() attempt (and restore back to before resize):
// The caller should try again with more resizeBuckets.
this.buckets = buckets;
this.buffer = buffer;
this.mask = buckets - 1;
return 0;
}
}
}
}
return 1;
};
Table.prototype.scan = function(bucket, tag, key, keyOffset) {
for (var slot = 0; slot < 8; slot++) {
if (
// Check the tag before checking presence bits:
// The tag is a better branch predictor with more entropy.
(this.buffer[bucket + 9 + 1 + slot] === tag) &&
(this.buffer[bucket + 9] & (1 << slot)) &&
this.equal(
this.buffer,
this.keyOffset(bucket, slot),
key,
keyOffset,
this.keySize
)
) {
break;
}
}
return slot;
};
Table.prototype.set = function(h1, h2, key, keyOffset, value, valueOffset) {
// Use the 2nd most significant byte of H1 for 1-byte tag:
var tag = (h1 >> 16) & 255;
// Use the 3rd and 4th most significant bytes of H1 and H2 for bucket offset:
var b1 = (h1 & this.mask) * this.bucket;
var b2 = (h2 & this.mask) * this.bucket;
// Reuse tag entropy for filter entropy (instead of using 2nd MSB from H2):
// This enables us to find the filter for any element without hashing its key.
// This increases tag-scanning false positives, but optimizes filter resets.
// This tradeoff is significant for cache(), where evictions reset filters.
// At 100% occupancy, 1 element per filter, we expect 1 in 9 false positives.
// See: https://hur.st/bloomfilter/?n=1&p=&m=8&k=1
var f1 = (tag >> 4) & 7; // Use tag's upper 4-bits to select a 1-byte filter.
var f2 = 1 << (tag & 7); // Use tag's lower 4-bits to select a bit.
// Check the filter to see if the element might exist:
if (this.buffer[b1 + f1] & f2) {
// Search for the element and update the element's value if found:
var s1 = this.scan(b1, tag, key, keyOffset);
if (s1 < 8) {
this.copyValue(value, valueOffset, this.buffer, this.valueOffset(b1, s1));
return 1;
}
var s2 = this.scan(b2, tag, key, keyOffset);
if (s2 < 8) {
this.copyValue(value, valueOffset, this.buffer, this.valueOffset(b2, s2));
return 1;
}
}
// Find an empty slot in first position:
var s3 = this.SLOT[this.buffer[b1 + 9]];
if (s3 < 8) {
this.assign(b1, tag, s3, key, keyOffset, value, valueOffset);
this.buffer[b1 + f1] |= f2;
return 0;
}
// Find an empty slot in second position:
var s4 = this.SLOT[this.buffer[b2 + 9]];
if (s4 < 8) {
this.assign(b2, tag, s4, key, keyOffset, value, valueOffset);
this.buffer[b1 + f1] |= f2;
this.filterIncrementSecondPosition(b1);
return 0;
}
// Vacate a slot in first position:
var s5 = this.vacate(b1);
if (s5 < 8) {
this.assign(b1, tag, s5, key, keyOffset, value, valueOffset);
this.buffer[b1 + f1] |= f2;
return 0;
}
// Vacate a slot in second position:
var s6 = this.vacate(b2);
if (s6 < 8) {
this.assign(b2, tag, s6, key, keyOffset, value, valueOffset);
this.buffer[b1 + f1] |= f2;
this.filterIncrementSecondPosition(b1);
return 0;
}
return -1;
};
Table.prototype.unset = function(h1, h2, key, keyOffset) {
// See comments in set():
var tag = (h1 >> 16) & 255;
var b1 = (h1 & this.mask) * this.bucket;
var b2 = (h2 & this.mask) * this.bucket;
var f1 = (tag >> 4) & 7;
var f2 = 1 << (tag & 7);
if (this.buffer[b1 + f1] & f2) {
var s1 = this.scan(b1, tag, key, keyOffset);
if (s1 < 8) {
this.buffer[b1 + 9] &= ~(1 << s1);
this.buffer[b1 + 9 + 1 + s1] = 0;
this.zero(this.keyOffset(b1, s1), this.keySize);
this.zero(this.valueOffset(b1, s1), this.valueSize);
this.filterReset(b1, f1);
return 1;
}
var s2 = this.scan(b2, tag, key, keyOffset);
if (s2 < 8) {
this.buffer[b2 + 9] &= ~(1 << s2);
this.buffer[b2 + 9 + 1 + s2] = 0;
this.zero(this.keyOffset(b2, s2), this.keySize);
this.zero(this.valueOffset(b2, s2), this.valueSize);
this.filterDecrementSecondPosition(b1);
return 1;
}
}
return 0;
};
Table.prototype.vacate = function(bucket) {
for (var slot = 0; slot < 8; slot++) {
var keyOffset = this.keyOffset(bucket, slot);
var valueOffset = this.valueOffset(bucket, slot);
Hash(this.buffer, keyOffset, this.keySize);
var tag = (H1 >> 16) & 255;
var b1 = (H1 & this.mask) * this.bucket;
var b2 = (H2 & this.mask) * this.bucket;
if (bucket === b1) {
// Move existing element to second position if there is an empty slot:
var s2 = this.SLOT[this.buffer[b2 + 9]];
if (s2 < 8) {
this.assign(
b2, tag, s2, this.buffer, keyOffset, this.buffer, valueOffset
);
this.filterIncrementSecondPosition(b1);
break;
}
// First and second positions are the same, or second position is full.
} else if (bucket === b2) {
// Move existing element back to first position if there is an empty slot:
var s1 = this.SLOT[this.buffer[b1 + 9]];
if (s1 < 8) {
this.assign(
b1, tag, s1, this.buffer, keyOffset, this.buffer, valueOffset
);
this.filterDecrementSecondPosition(b1);
break;
}
} else {
throw new Error('bucket !== b1 && bucket !== b2');
}
}
return slot;
};
Table.prototype.valueOffset = function(bucket, slot) {
// See comment in keyOffset():
return bucket + 20 + (this.keySize + this.valueSize) * slot + this.keySize;
};
Table.prototype.zero = function(offset, size) {
if (size < 64) {
var groups = size >>> 2;
while (groups--) {
this.buffer[offset + 0] = 0;
this.buffer[offset + 1] = 0;
this.buffer[offset + 2] = 0;
this.buffer[offset + 3] = 0;
offset += 4;
size -= 4;
}
while (size--) this.buffer[offset++] = 0;
} else {
this.buffer.fill(0, offset, offset + size);
}
};
module.exports = HashTable;
// S.D.G.
}).call(this,require("buffer").Buffer)
},{"buffer":2,"randombytes":6}],6:[function(require,module,exports){
(function (process,global){
'use strict'
// limit of Crypto.getRandomValues()
// https://developer.mozilla.org/en-US/docs/Web/API/Crypto/getRandomValues
var MAX_BYTES = 65536
// Node supports requesting up to this number of bytes
// https://github.com/nodejs/node/blob/master/lib/internal/crypto/random.js#L48
var MAX_UINT32 = 4294967295
function oldBrowser () {
throw new Error('Secure random number generation is not supported by this browser.\nUse Chrome, Firefox or Internet Explorer 11')
}
var Buffer = require('safe-buffer').Buffer
var crypto = global.crypto || global.msCrypto
if (crypto && crypto.getRandomValues) {
module.exports = randomBytes
} else {
module.exports = oldBrowser
}
function randomBytes (size, cb) {
// phantomjs needs to throw
if (size > MAX_UINT32) throw new RangeError('requested too many random bytes')
var bytes = Buffer.allocUnsafe(size)
if (size > 0) { // getRandomValues fails on IE if size == 0
if (size > MAX_BYTES) { // this is the max bytes crypto.getRandomValues
// can do at once see https://developer.mozilla.org/en-US/docs/Web/API/window.crypto.getRandomValues
for (var generated = 0; generated < size; generated += MAX_BYTES) {
// buffer.slice automatically checks if the end is past the end of
// the buffer so we don't have to here
crypto.getRandomValues(bytes.slice(generated, generated + MAX_BYTES))
}
} else {
crypto.getRandomValues(bytes)
}
}
if (typeof cb === 'function') {
return process.nextTick(function () {
cb(null, bytes)
})
}
return bytes
}
}).call(this,require('_process'),typeof global !== "undefined" ? global : typeof self !== "undefined" ? self : typeof window !== "undefined" ? window : {})
},{"_process":4,"safe-buffer":7}],7:[function(require,module,exports){
/* eslint-disable node/no-deprecated-api */
var buffer = require('buffer')
var Buffer = buffer.Buffer
// alternative to using Object.keys for old browsers
function copyProps (src, dst) {
for (var key in src) {
dst[key] = src[key]
}
}
if (Buffer.from && Buffer.alloc && Buffer.allocUnsafe && Buffer.allocUnsafeSlow) {
module.exports = buffer
} else {
// Copy properties from require('buffer')
copyProps(buffer, exports)
exports.Buffer = SafeBuffer
}
function SafeBuffer (arg, encodingOrOffset, length) {
return Buffer(arg, encodingOrOffset, length)
}
// Copy static methods from Buffer
copyProps(Buffer, SafeBuffer)
SafeBuffer.from = function (arg, encodingOrOffset, length) {
if (typeof arg === 'number') {
throw new TypeError('Argument must not be a number')
}
return Buffer(arg, encodingOrOffset, length)
}
SafeBuffer.alloc = function (size, fill, encoding) {
if (typeof size !== 'number') {
throw new TypeError('Argument must be a number')
}
var buf = Buffer(size)
if (fill !== undefined) {
if (typeof encoding === 'string') {
buf.fill(fill, encoding)
} else {
buf.fill(fill)
}
} else {
buf.fill(0)
}
return buf
}
SafeBuffer.allocUnsafe = function (size) {
if (typeof size !== 'number') {
throw new TypeError('Argument must be a number')
}
return Buffer(size)
}
SafeBuffer.allocUnsafeSlow = function (size) {
if (typeof size !== 'number') {
throw new TypeError('Argument must be a number')
}
return buffer.SlowBuffer(size)
}
},{"buffer":2}]},{},[5]);
// I have no idea how browserify works...
let HashTable = thePackage(5);
HashTable.Buffer = thePackage(2).Buffer;
export default HashTable;
Raw
index.html
<script type=module>
import HashTable from "./HashTable.mjs";
let Buffer = HashTable.Buffer;
const keySize = 16;
const valueSize = 4;
const elementsMin = 1024; // Optional. Reserve space for at least 1,024 elements.
const elementsMax = 65536; // Optional. Expect at most 65,536 elements.
const hashTable = new HashTable(keySize, valueSize, elementsMin, elementsMax);
// set():
let key = Buffer.alloc(keySize);
let keyOffset = 0;
let value = Buffer.alloc(valueSize);
let valueOffset = 0;
let result = hashTable.set(key, keyOffset, value, valueOffset);
if (result === 0) console.log('set(): element was inserted');
if (result === 1) console.log('set(): element was updated');
// etc.
// etc.
// see readme: https://github.com/ronomon/hash-table
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment