bigint enhancements.

🦋 Proposals
1

Motivation

bigints were a great addition to ES, but they often need to be converted to/from other datatypes for transport or integration with legacy systems. At the moment, every user has to re-implement those methods manually, some of which are easy to get wrong (like twos-complement encoding).

Proposal

  • Convert a bigint to a Uint8Array of the given number of bits.

    BigInt.toUint8Array(bits: number, signed: boolean = false)
    • BigEndian encoding order.
    • If the value cannot fit into the specified number of bits, the function MUST throw an Error.
    • If the value is negative, it should be encoded using two's complement.
    • If the value is negative and signed == false, the function MUST throw an Error

  • Convert a UInt8Array into a bigint.

    BigInt(bytes: Uint8Array, signed: boolean = false)
    • Interpret the bytes as big endian.
    • If signed is true then the bytes should be interpreted as two's complement.

  • Convert a bigint into a base radix string using two's complement for negative numbers and doing sign extension out to bits.

    BigInt.toString(radix: number, bits: number, signed: boolean = false)
    • If the value is negative and signed == false, then the function MUST throw an Error.

  • Convert a string into a bigint, interpreting it as a two's complement value

    BigInt(value: string, bits?: number, signed: boolean = false)
    • If the string is more than bits / 8 characters long after processing the leading 0x radix indicator, then the function MUST throw an Error.

Test Cases

(0n).toUint8Array(8, true) // [0x00]
(0n).toUint8Array(8, false) // [0x00]
(0n).toUint8Array(8) // [0x00]
(0n).toUint8Array(16) // [0x00, 0x00]
(1n).toUint8Array(8, true) // [0x01]
(127n).toUint8Array(8, true) // [0x7f]
(128n).toUint8Array(8, true) // error
(128n).toUint8Array(16, true) // [0x00, 0x80]
(128n).toUint8Array(8, false) // [0x80]
(128n).toUint8Array(8) // [0x80]
(255n).toUint8Array(8, false) // [0xff]
(256n).toUint8Array(8, false) // error
(256n).toUint8Array(16, false) // [0x01, 0x00]
(-129).toUint8Array(8, true) // error
(-129).toUint8Array(16, true) // [0xff, 0x7f]
(-128).toUint8Array(8, true) // [0x80]
(-1n).toUint8Array(8, true) // [0xff]
(-1n).toUint8Array(8, false) // error

BigInt(new Uint8Array([0x80])) // 128n
BigInt(new Uint8Array([0x80]), false) // 128n
BigInt(new Uint8Array([0x80]), true) // -128n

(0n).toString(16, 0) // ''
(0n).toString(16, 8) // '00'
(0n).toString(16, 16) // '0000'
(128n).toString(16, 8, true) // error
(128n).toString(16, 8, false) // '80'
(-128n).toString(16, 8, false) // error
(-128n).toString(16, 8, true) // '80'
(-128n).toString(16, 16, true) // 'ff80'

BigInt('0x80') // 128n
BigInt('0x80', 8) // 128n
BigInt('0x80', 8, false) // 128n
BigInt('0x80', 8, true) // -128n
BigInt('0x80', 16, true) // 128n
BigInt('0xff80', 16, true) // -128n

Considerations

Array instead of Uint8Array:

Array<number> may be preferable to Uint8Array as it is a "simpler" type, and thus more likely to be usable. Plus, it is trivial to convert an Array<number> into a Uint8Array if necessary. Uint8Array is more commonly used for data buffers and transport, hence why I went with that, but if others feel strongly about Array<number> I don't see any problem there.

Endianness

Big Endian is often called "Network Byte Order" due to how common it is for network payloads. Since JavaScript is used largely for "internet" applications, it makes sense to choose that byte order, even though it may be slightly less performant on little endian systems.

Two's Complement

This seems to have won out over ones' complement almost across the board. I don't really see any reason to pick ones' complement over the defacto standard in this case.

FromString length for bits?

We could infer the bits parameter for BigInt from string. This way we would only need a single boolean parameter and it would be up to the caller to provide a properly padded unsigned value, to ensure that the leading bit is not set. This means 0xff would always decode as -1n, and if you wanted 255n then you would need to pass 0x00ff. In general, I'm not a fan of inferring things like this because it is a vector for unexpected runtime errors, but I am open to being convinced it is a better API.

6 Likes
2

I acknowledge that there is a pretty common need to serialise BigInts in order to store them, communicate them between systems, etc., but I do not think we need a standard transcoder built in to the language, at least not now. There are many, many different "VLQ"/"varint" encodings of arbitrary-magnitude integers used in a variety of systems: MIDI popularised one, protobuffs popularised another, and git uses yet another. Each of them would be a valid way to encode BigInts, but none is so overwhelmingly popular among JavaScript users (yet) or hard enough to implement via libraries to justify inclusion in the language. For example, the one I've built (https://github.com/michaelficarra/bigint-serialiser) uses yet another "VLQ"/"varint" variant that makes the tradeoffs that I felt were appropriate for general usage, and its implementation is not particularly large or difficult to get correct, as you can see from the source and tests.

3

The most likely part to get wrong is the two's complement. Currently, ES can encode to arbitrary base string, which is pretty easy to convert to most other formats, with the exception of encoding negative numbers "reasonably" (I don't know of any other system that encodes a number by prefixing with a leading - sign aside from when it is presenting a base 10 number). Perhaps this proposal could be simplified/reduced just to making the toString method correctly handle negative numbers using the defacto standard of two's complement?

Do any of the protocls you mentioned above use anything other than two's complement for encoding negative numbers (before compression)? If not, then it seems that two's complement may be the common piece where we would get the most value out of an ES standard. We could have it only be part of the toString and from string methods, and scrap all of the Uint8Array stuff.

4

If the BigInt fits into 64 bits, you can just new BigInt64Array([some bigint]).buffer

5

I think most people don't care which format, as long as encoding and decoding works with same binary.
For those who care, they are mostly using crypto related algorithm, so we just need the same format used by webcrypto when encoding private/public keys into binary.

6

Overall, I think this is fine. I wouldn't want to have the bits parameter, though, it should just work and give me a result.

I think most people don't care which format, as long as encoding and decoding works with same binary.

+1.

7

In order for the system to be able to decode something that was previously encoded by the same system, either you need the bits parameter OR unsigned values may need a leading 0 byte sometimes. For example (128n).toString(16, true) would result in '0080'. This is because BigInt('0x80', true) would decode as -128.

Also, if we leave out the bits parameter then I believe the signed boolean becomes required since (128n).toString(16) currently will produce '80', and I don't think we can do a backward incompatible change like that.

8

I have been seeing a trend with LEB128 (signed and unsigned both) taking off as the predominant variable-length integer encoding, including in WebAssembly, LLVM, DWARF (debugging format), Protobufs, among others, so I wonder if it'd be worth exposing that. Also, some formats specify fixed-width integers larger than 64 bits, and so it'd be useful to be able to read that.

Concretely, I feel these would be best to add:

  • BigInt.prototype.bitLength - Basically, Math.floor(Math.log2(Math.abs(this))) + BigInt(this < 0), but would be a cheap O(1) operation in practice due to pervasive hardware and compiler support for "find first set", "count leading zeroes", "log base 2", etc. For standard JS numbers, it's 31 - Math.clz32(x) and thus trivial, but bigints could be any size and so this is necessary for them. It's also necessary to readily calculate how much was written for variadic integers. It returns a BigInt.
  • DataView.prototype.getBigIntN(width, index, littleEndian), DataView.prototype.getBigUintN(width, index, littleEndian) - Read bytes bytes starting at offset index into a bigint n and return BigInt.asIntN(width, n) or BigInt.asUintN(width, n) as appropriate. Note that result.bitLength won't necessarily equal width - it just can't be greater than it.
  • DataView.prototype.setBigIntN(width, index, value, littleEndian), DataView.prototype.setBigUintN(width, index, value, littleEndian) - Convert value to a bigint n via BigInt.asIntN(width, value) or BigInt.asUintN(width, value) as appropriate, and write it to the first bytes bytes starting at offset index, sign- or zero-extended as appropriate.
  • DataView.prototype.getBigIntVL(index), DataView.prototype.getBigUintVL(index) - Read a LEB128-encoded integer at index. Naturally, the number of bytes read is Math.floor(result.bitLength / 8).
  • DataView.prototype.setBigIntVL(index, value), DataView.prototype.setBigUintVL(index, value) - Write a LEB128-encoded integer at index. Naturally, the number of bytes written is Math.floor(value.bitLength / 8).

Note: bytes here is max(1, div_round_up(width, 8n)) + 1 for signed integers and max(1, div_round_up(width, 8n)) for unsigned integers, where width is the number of bits required to represent the integer as a two's complement signed integer. It's the minimum number of bytes required to represent it as either a signed or unsigned integer.

As for the need to convert into a Uint8Array, here's how this addresses that:

  1. If you really do want to convert to/from a Uint8Array, it's not too hard, just a little involved and naturally math-y. (You're probably already doing something math-y, so it's not going to be that much simpler.) Do note that you do have to take into account whether you want to treat it as signed.
function signedToArray(bigint, littleEndian) {
    const bits = bigint.bitLength
    const width = Math.max(1n, bits / 8n + BigInt(bits % 8n !== 0n)) * 8n
    const result = new Uint8Array(width)
    new DataView(result.buffer).setBigIntN(bits, width, bigint, littleEndian)
    return result
}

function unsignedToArray(bigint, littleEndian) {
    const bits = bigint.bitLength - 1
    const width = Math.max(1n, bits / 8n + BigInt(bits % 8n !== 0n)) * 8n
    const result = new Uint8Array(width)
    new DataView(result.buffer).setBigUintN(bits, 0, bigint, littleEndian)
    return result
}

function arrayToSigned(array, littleEndian) {
    return new DataView(array.buffer).getBigIntN(
        BigInt(array.length) * 8n, 0, littleEndian
    )
}

function arrayToUnsigned(array, littleEndian) {
    return new DataView(array.buffer).getBigUintN(
        BigInt(array.length) * 8n, 0, littleEndian
    )
}
  1. For bit vectors, you could do bits & 1n << BigInt(offset). It's a trivial thing for parsers to detect, and any reasonable implementation could optimize this to avoid the ceremony of a bit shift + a full bitwise AND across the entire bigint, even for large bit vectors. It's similar to C++'s vector<bool> specialization, but obviously immutable. Not sure any engines implement this optimization, though.
2 Likes
9

I think moving the to/from Uint8Array into DataView is probably a better solution than having those functions on BigInt. It would be nice if you could utilize that in one-line, rather than two (minimum), though. For example, if the DataView set functions functions returned this so you could do:

new Uint8Array(new DataView(new ArrayBuffer(byteLength)).setBigUintN(byteLength * 8, 0, false).buffer)

It would be nice if we could get that down a bit, but I think that is more an issue not being able to construct a DataView with an implicit ArrayBuffer by just providing a length, but it isn't too bad and if you are pulling more than a single number out of a byte array it gets better.

1 Like
10

VLQs encode this as the least or most significant bit of the message. It should just be handled by the format. If we consider this an opaque data format (composed of a variable number of ints), then this shouldn't be an issue.

11

If we use some specific variable length encoding format then yes. However, I would argue that is getting too opinionated unless we provide multiple encoding formats (or at least design for the addition of future encoding formats) since there isn't a clear winner at this time beyond "Big Endian" and "Two's Complement" (even Big Endian has only won within the context of network traffic). Any encoding beyond that is still a fairly competitive space in my experience, and thus it is probably not a good to bake one into ES as the "official encoding format".

Another option would be to have these functions take an encoding parameter, like TextEncoder used to have in some browsers prior to being well specified. In that case, I think choosing UTF-8 was reasonable beacuse it has "won" the character encoding competition for most of the internet (where JS is predominately used).

12

If we use some specific variable length encoding format then yes. However, I would argue that is getting too opinionated unless we provide multiple encoding formats (or at least design for the addition of future encoding formats) since there isn't a clear winner at this time beyond "Big Endian" and "Two's Complement" (even Big Endian has only won within the context of network traffic).

Going to have to disagree that big endian "won". It's used in most network traffic, but little endian won in the hardware space due to better read/write efficiency. (ARM is mostly little-endian, x86-64 is exclusively little-endian, and the remaining popular big-endian architectures are almost all older.) Little-endian also largely won the file space. Yes, most networking protocols use big-endian representation, but this is not universal.

Any encoding beyond that is still a fairly competitive space in my experience, and thus it is probably not a good to bake one into ES as the "official encoding format".

For variable-length quantities, I do see a winner here, and it aligns with my proposal:

  • The unsigned LEB128 format has pretty much won for unsigned integers, more than UTF-8 won the encoding wars - people were using this very format longer than the term "LEB128" was even a thing. DWARF, MIDI (page 2), ASN.1 BER (page 13), Google's Protocol Buffers, W3C's EXI spec, and .NET's BinaryReader and BinaryWriter classes. Also, several other specs use the format explicitly. LLVM bitcode itself generally follows that format without specifying it, but supports segments widths of fewer than 8 bits and adjusts accordingly. (This is rarely dealt with directly in JS, BTW.) Source maps use a similar system, but with 6-bit segments to fit in a base 64 encoding instead of 8-bit segments to fit in 8-bit bytes. (This is almost exclusive to build tooling and doesn't account for much of the time spent.) It all stems from using the high bit of a given segment as the "continuation bit". There's a couple more significant exceptions here:
    • QUIC sets the high 2 bits of the first byte to 00 for 6-bit integers, 01 for 14-bit integers, 10 for 30-bit integers, and 11 for 62-bit integers. They don't support arbitrary-length integers, though.
    • Git makes sure that the smallest N+1-byte octet represents one more than the highest N-byte octet, removing redundancy. Otherwise, it follows the same pattern as LEB128 for unsigned integers.
  • LEB128's form of truncating it to the smallest possible width that can represent it as two's complement and then sign-extending that to the nearest multiple of 7 also largely won. Signed integers in Protocol Buffers are an unusual exception that stores it as the unsigned representation of (n << 1) ^ (n >> 31) for 32-bit integers, (n << 1) ^ (n >> 63) for 64-bit integers, etc., but that transform is relatively trivial and easily converted to something in terms of dataView.setBigUintN(...). And the two main exceptions listed above lack variable-length signed integers entirely.
13

"bitLength" is needed for my implementation of Lehmer's GCD (to extract the leading bits).
or to do compute the initial approximation when finding integer square root, or, perhaps, to round the number to some specified number of binary digits.
Of course, it can be implemented in JS and be quite fast, but it would be nice to have it as optimized for different use cases code looks not very good.
It could also be added as a static method: BigInt.bitLength(bigint). My use cases do not need to call it with negative or zero values.

14

A polyfill may look like this:

// bitLength(a) = floor(log2(a)) + 1 if a > 0
if (typeof BigInt.bitLength !== 'function') {
  BigInt.bitLength = function bitLength(a) {
    const s = BigInt(a).toString(16);
    const c = s.charCodeAt(0) - '0'.charCodeAt(0);
    if (c <= 0) {
      throw new RangeError();
    }
    return (s.length - 1) * 4 + (32 - Math.clz32(Math.min(c, 8)));
  }
}