Fastest way to convert a integer to arbitrarily ordered byte arrays in JavaScript?

Question

I'm looking to convert the MIN_SAFE_INTEGER through MAX_SAFE_INTEGER range of a JavaScript number (53-bits not including the sign) into a string of bits spread over 7 bytes shifted two to allow for sign and null identifiers.

Thus far the best I've come up with is:

function toUint8Array(data) {
    data = data.toString(2);
    data = new Array(65 - data.length).join('0') + data;
    var ret = new Uint8Array(data.length / 8);
    for (var i = 0; i < 8; i++) {
        ret[i] = 0;
        ret[i] += (data[i * 8] == '1' ? 128 : 0);
        ret[i] += (data[(i * 8) + 1] == '1' ? 64 : 0);
        ret[i] += (data[(i * 8) + 2] == '1' ? 32 : 0);
        ret[i] += (data[(i * 8) + 3] == '1' ? 16 : 0);
        ret[i] += (data[(i * 8) + 4] == '1' ? 8 : 0);
        ret[i] += (data[(i * 8) + 5] == '1' ? 4 : 0);
        ret[i] += (data[(i * 8) + 6] == '1' ? 2 : 0);
        ret[i] += (data[(i * 8) + 7] == '1' ? 1 : 0);
    }
    return (ret);
}

Fiddle

As you can tell right off, this would be abominably slow (and the bits still haven't been shifted two places across all 7 active bytes.)

Is there any way to do this faster? Ideally by avoiding the string parsing altogether?

Answer 1

Bitwise ops in javascript are only 32 bits wide. But shifting is equivalent to multiplication or division by a power of two, and these happen with full floating-point precision.

So what you want to do is straightforward. Shift to get the interesting part in the low-order bits, and mask off the rest. E.g. you have a big number 0x123456789abc (20015998343868).

0x123456789abc / 0x1 = 0x123456789abc. Bitwise AND with 0xff gives 0xbc.

0x123456789abc / 0x100 = 0x123456789a.bc. Bitwise AND with 0xff gives 0x9a.

0x123456789abc / 0x10000 = 0x12345678.9abc. Bitwise AND with 0xff gives 0x78.

And so on. Code:

function toUint8Array(d) {
    var arr = new Uint8Array(7);
    for (var i=0, j=1; i<7; i++, j *= 0x100) {
        arr[i] = (d / j) & 0xff;
    }
    return arr;
}

With a Uint8Array life is even easier: the masking with 0xff is implicit as Uint8Arrays can only store integers between 0 and 255. But I've left it in for clarity, and so that the result will the same with different array types.

This code produces a little-endian array, e.g. toUint8Array(0x123456789abc) returns [0xbc,0x9a,0x78,0x56,0x34,0x12,0]. If you want big-endian, i.e. the bytes in the opposite order, replace arr[i] with arr[6-i].

(If you want the bits in each array entry in the opposite order this is slightly more complicated. Replace (d / j) & 0xff with bitrev((d / j) & 0xff), where bitrev looks something like this:

function bitrev(byte) {
   var table = [ 0b0000, 0b1000, 0b0100, 0b1100, 0b0010, 0b1010, 0b0110, 0b1110,
                 0b0001, 0b1001, 0b0101, 0b1101, 0b0011, 0b1011, 0b0111, 0b1111 ];
   return table[byte >> 4] + (table[byte & 0xf] << 4);
}

)

Finally, this only works on positive integers. But your shifting-by-two idea is easily implemented. d*4 is d shifted left by two bits. And d < 0 ? -d : d (or Math.abs(d)) is the absolute value of d. So arr = toUint8Array((d<0) ? 1-d*4 : d*4) returns d shifted left by two bits, with the sign bit in the least significant bit (LSB).

And you can check for not-numbers with isFinite(), but you have to be careful to call it only on numbers, as isFinite(null), say, is actually true due to implicit casting rules (this is fixed in ES6):

function toUint8Array_shifted_signed(d) {
   /* bit 0 is sign bit (0 for +ve); bit 1 is "not-a-number" */
   if (typeof d !== 'number' || !isFinite(d)) {
       d = 2; 
   } else {
       d = (d<0) ? 1-d*4 : d*4;
   }

   return toUint8Array(d);
}

Answer 2

I hit the books, and a couple more math-side CS friends of mine, and our current verdict is that this can't be done as you're describing it.

I think you're stuck with the string-parsing.