2

I'm using javascript, and I'm little rusty on my bit arithmetic.

Ultimately, my goal is to convert a UInt8Array into 11-bit numbers for use with a bip39 wordlist for converting a libsodium private box key to a mnemonic (I'm building a small p2p-ish chat app).

So, my thought process is:

  1. Uint8Array is returned from libsodium.crypto_box_keypair()
  2. Convert Uint8Array into a 256bit (boolean) array
  3. divide the 256bit array into 11bit buckets (2d array: ~24 x 11bits)
  4. convert each 11bit array to a base 10 number (between 0 and 2047)

Steps 2, 3, and 4 can be combined into the same loop.

The goal of all this is to efficiently convert from a Uint8Array to an array of 11bit numbers (efficient for the computer -- this hasn't been efficient for myself).

I have this at the moment, but it isn't quite right, and feels somewhat hacky (just from steps 2 and 3, where I try to create the 11bit buckets)

// inspired from: https://github.com/pvorb/node-md5/issues/25
export function toUint11Array(input: Uint8Array): boolean[][] {
  let result: boolean[][] = [];
  let currentChunk: boolean[] = [];

  input.forEach(byte => {
    for (var j = 7; j >= 0; j--) {
      var b = ((byte >> j) & 0x1) > 0;

      if (currentChunk.length === 11) {
        result.push(currentChunk);
        currentChunk = [];
      }

      currentChunk.push(b);
    }
  });

  return result;
}

Currently, for 2048, I get 2 11 bit arrays (expected), but the content / order is unexpected.

  [
    false, false, false, false,
    false, false, false, false,
    false, false, false
  ],
  [ false, true, false, false,
    false, false, false, false, 
    false, false, false
  ]

2048 is 0b100_000_000_000

where the 12th digit from the right is the 1 (added underscores for easier reading)

so maybe it looks like I have an endianness problem and and off by one issue? because the true in my dual array is the 13th position from the left.

though, when I test with 4096 (13 bits (0b1_000_000_000_000)), I get this:

  [
    false, false, false, false,
    false, false, false, false,
    false, false, false
  ],
  [
    true, false, false, false,
    false, false, false, false,
    false, false, false
  ],
  [
    false, false, false, false,
    false, false, false, false,
    false, false, false
  ]

Here, the true is 12th from the left, and 22nd from the right.

Update

per @bergi, who asked about endianness.

enter image description here

I don't know what endianness this is. :-\

Update 2

Thanks to @harold for coming up with the answer. I have some tests that I think confirm correctness. 

  const numbers = {
    ['32']: new Uint8Array([32]),
    ['64']: new Uint8Array([64]),
    ['2048']: new Uint8Array([8, 0]),
    ['4096']: new Uint8Array([16, 0]),
    ['7331']: new Uint8Array([28, 163])
  }

  test ('toUint11Array | converts | 32 (8 bits)', function(assert) {
    const result = toUint11Array(numbers['32']);
    const expected = [32];

    assert.deepEqual(result, expected);
  });

  test ('toUint11Array | converts | 2048 (12 bits)', function(assert) {
    const result = toUint11Array(numbers['2048']);
    const expected = [8, 0];

    assert.deepEqual(result, expected);
  });

  test ('toUint11Array | converts | 4096 (13 bits)', function(assert) {
    const result = toUint11Array(numbers['4096']);
    const expected = [16, 0];

    assert.deepEqual(result, expected);
  });



 test ('toUint11Array | converts | 7331 (13 bits)', function(assert) {
    const result = toUint11Array(numbers['7331']);
    const expected = [3, 1187];

    assert.deepEqual(result, expected);
  });

the first 3 pass, but the last does not.

when converting a Uint8Array(28, 163), I get [796, 28]

I'm not 100% sure that I converted 7331 into appropriate bytes correctly, but I did: 7331 = 0b1_1100_1010_0011 split: [1_1100, 1010_0011] -> [28, 163].

I suppose for the output, it should be: [11, 100_1010_0011] which is [3, 1187] which also doesn't match the output.

Improve this question
12
  • Does crypto_box_keypair() always return a 32-byte array? Commented May 10, 2018 at 21:30
  • What endianness do you need (both on bit and byte level)? Commented May 10, 2018 at 21:35
  • "Steps 2, 3, and 4 can be combined into the same loop" - I would recommend to use generator functions here, they should simplify the code a lot. Commented May 10, 2018 at 21:37
  • @Bergi yes, it's a 32 Byte Uint8Array Not sure about endianness. I'd like to stick with what is being used by default (I'll post a screenshot from the console). Generator Funciton? how so? I haven't actually written one before? (Just used them with redux sagas, and ember-concurrency) Commented May 10, 2018 at 22:25
  • There is no "default endianness", and your screenshot just shows a bunch of numbers. Commented May 11, 2018 at 11:44

2 Answers 2

Reset to default
2

I'm not as rusty on my bit arithmetic, so I propose a method without temporary boolean arrays:

  • read bytes into a buffer until there are at least 11 bits
  • extract 11 bits from the buffer
  • repeat

Actually a funny thing happens at the end since 11 does not divide 256, I assume padding with zeroes is OK.

So maybe something like this in JavaScript (but I am a little rusty on my JS)

function toUint11Array(input) {
    var buffer = 0, numbits = 0;
    var output = [];

    for (var i = 0; i < input.length; i++) {
        // prepend bits to buffer
        buffer |= input[i] << numbits;
        numbits += 8;
        // if there are enough bits, extract 11bit chunk
        if (numbits >= 11) {
            output.push(buffer & 0x7FF);
            // drop chunk from buffer
            buffer = buffer >> 11;
            numbits -= 11;
        }
    }
    // also output leftover bits
    if (numbits != 0)
        output.push(buffer);

    return output;
}
Improve this answer
Sign up to request clarification or add additional context in comments.

9 Comments

cool, thanks for this! I need to write a couple tests, and write the inverse of this to make sure conversion is working in both directions.
actually, Assuming I did math right, I think this works. (I haven't made the inverse yet, but I just made some Uint8 to Uint11 tests. I'll update my question with results.
I found a scenario where toUint11Array fails (I think) for 7331 (but as a Uint8Array) see my Update 2. I tried doing some google-assisted decimal -> binary -> decimal conversions, that could be where my error is in my tests. unsure atm.
@NullVoxPopuli are you sure about the expected result? I get [1187, 3] which makes sense, the 3 part are the high bits
what are you using for your input array? I manually got [1187, 3], but my test isn't getting that.
|
1

I'd go for generators:

function* bitsFromOctetsLE(octets) {
    for (let byte of octets) {
        for (let i=0; i<8; i++) {
            yield (byte & 1);
            byte >>= 1;
        }
    }
}
function* hendecadsFromBitsLE(bits) {
    let i=0;
    let val=0;
    for (const bit of bits) {
        if (i==11) {
            yield val;
            i = val = 0;
        }
        val |= bit << (i++);
    }
    if (i > 0) yield val;
}

Then use them like

const input = libsodium.crypto_box_keypair();
const result = Array.from(hendecadsFromBitsLE(bitsFromOctetsLE(input)))
Improve this answer

6 Comments

what's the advantage of yielding val and byte & 1?
oh I see now, when yielded, the other function evaluates. but there is no final return value?
Advantage over what?
@NullVoxPopuli The return value of a generator function call is a generator that produces the yielded values. Array.from will collect them into an array in the end.
ok, I figured it out, Array.from handles the yield conversion for me. But also, it looked like I was consistently missing the last section of data. so in hendecadsFromBitsLE, I added a yield val; at the end of the function, and now your answer yields the same results as @harold's answer. :-) Now I just need to figure out what's wrong with the 7331 test.
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.