3
\$\begingroup\$

tl;dr: How could you rewrite the buf_get and buf_set functions below to be most optimal?

It took me a long time and a lot of head banging on the wall to get these buf_* functions to work, but they are not very elegant and I'm sure many of you can easily spot how to do these "more correctly".

Basically, the uint8_* functions are an implementation of bitwise get/set/clear on 8-bit unsigned integers in JavaScript. Then the buf_* extend that to work on arbitrarily large 8-bit buffers, treating the bit buffer as chunks of 8-bits, but operating on potentially every individual bit... You pass in as parameters where you start and such relative to some 8-bit chunk in the buffer basically.

First, here are the 5 uint8_* functions, most of which were rewritten right-to-left in a simpler way here, but I couldn't integrate because it would mess up their usage in the buf_* functions.

function uint8_get_size(n) {
  let i = 0
  while (n) {
    i++
    n >>= 1
  }
  return i
}

function uint8_get(n, l, s) {
  let r = 8 - l - s
  let p = 1 << 8
  let o = p - 1
  let ol = o << r
  let or = o >> l
  let om = or & ol
  let x = n & om
  return x >> r
}

function uint8_set(n, i, x) {
  let o = 0xff // 0b11111111
  let c = uint8_get_size(x)
  let j = 8 - i // right side start
  let k = j - c // right side remaining
  let h = c + i
  let a = x << k // set bits
  let b = a ^ o // set bits flip
  let d = o >> h // mask right
  let q = d ^ b //
  let m = o >> j // mask left
  let s = m << j
  let t = s ^ q // clear bits!
  let w = n | a // set the set bits
  let z = w & ~t // perform some magic https://stackoverflow.com/q/8965521/169992
  return z
}

function uint8_clear(n, i, c) {
  let s = i + c
  let r = 8 - s
  let p = 1 << 8
  let o = p - 1
  let j = o >> i
  let k = o << r
  let h = j & k
  let g = ~h
  let z = n & g
  return z
}

function uint8_set_with_leading_space(uint8, left, size, value) {
  uint8 = uint8_clear(uint8, left, size)
  let writeSize = uint8_get_size(value)
  let newLeft = left + size - writeSize
  return uint8_set(uint8, newLeft, value)
}

Those are dependencies of the buf_* implementations.

So then here are the "main" functions of the topic of the question, the buf_* functions, which are currently quite tangled. The readUint8Buffer is assumed to be a large enough Uint8Array such as new Uint8Array(16777216) to hold the amount of data being operated on for all intents and purposes.

function buf_get(readUint8Buffer, readLeft, readSize, writeUint8Buffer, writeLeft) {
  buf_get_impl(readUint8Buffer, readLeft, readSize, writeLeft, function(l, s, b){
    buf_set_with_leading_space(writeUint8Buffer, l, s, b)
  })
}

// since this was used in two places above I refactored it out.
function buf_get_impl(readUint8Buffer, readLeft, readSize, writeLeft, cb) {
  let i = 0
  while (readSize) {
    let readUint8Offset = readLeft >> 3
    let readBitOffset = readLeft % 8
    let readRightBitSize = Math.min(8, readSize + readBitOffset) - readBitOffset
    var strange = (readBitOffset + readRightBitSize) == 8
    let uint8 = readUint8Buffer[readUint8Offset]
    let bits = uint8_get(uint8, readBitOffset, readRightBitSize)
    cb(writeLeft, strange ? readRightBitSize : 8, bits)
    readSize -= readRightBitSize
    if (strange) {
      let uint8 = readUint8Buffer[readUint8Offset + 1]
      let bits = uint8_get(uint8, 0, 8 - readRightBitSize)
      cb(writeLeft, 8, bits)
      writeLeft += (8 - readRightBitSize)
      readLeft += (8 - readRightBitSize)
      // readSize -= (8 - readRightBitSize)
    }
    writeLeft += readRightBitSize
    readLeft += readRightBitSize
  }
}

function buf_set_with_leading_space(writeUint8Buffer, left, size, writeUint8) {
  buf_clear(writeUint8Buffer, left, size - left)
  let writeSize = uint8_get_size(writeUint8)
  let newLeft = left + size - writeSize
  buf_set(writeUint8Buffer, newLeft, writeUint8)
}

function buf_set(writeUint8Buffer, left, writeUint8) {
  let writeSize = uint8_get_size(writeUint8)
  let writeUpdated = writeUint8 << (8 - writeSize)
  let readUint8Left = left >> 3
  let readUint8a = writeUint8Buffer[readUint8Left]
  let readBitLeft = left % 8
  let readStartSize = 8 - readBitLeft
  let writeUint8Subseta = uint8_get(writeUpdated, 0, readStartSize)
  let outUint8a = uint8_set(readUint8a, readBitLeft, writeUint8Subseta)
  writeUint8Buffer[readUint8Left] = outUint8a
  let extent = readBitLeft + writeSize
  if (extent > 8) {
    let writeUint8SubsetbSize = extent - 8
    let writeUint8Subsetb = uint8_get(writeUpdated, readStartSize, writeUint8SubsetbSize)
    let readUint8b = writeUint8Buffer[readUint8Left + 1]
    let clearedUint8 = uint8_clear(readUint8b, 0, writeUint8SubsetbSize)
    let outUint8b = uint8_set_with_leading_space(clearedUint8, 0, writeUint8SubsetbSize, writeUint8Subsetb)
    writeUint8Buffer[readUint8Left + 1] = outUint8b
  }
}

function buf_clear(writeUint8Buffer, left, size) {
  // this currently allows local tests to pass
  // as long as you are just loading into a buffer
  // straight left to right.
  // i haven't gotten to clearing buffers yet, so
  // you can just ignore this for now to keep it simpler.
}

This is all of the code with a few examples demonstrating the API I've been using.

const a1 = uint8_get(0b10100000, 0, 1)
assertBits(a1, '1')

const a2 = uint8_get(0b10100000, 0, 2)
assertBits(a2, '10')

const a3 = uint8_get(0b10100000, 0, 3)
assertBits(a3, '101')

const a4 = uint8_get(0b10111001, 2, 4)
assertBits(a4, '1110')

const a5 = uint8_get(0b10111001, 0, 6)
assertBits(a5, '101110')

const b0 = uint8_set(0, 1, 1)
assertBits(b0, '1000000')

const b1 = uint8_set(0b10111001, 1, 0b10)
assertBits(b1, '11011001')

const b2 = uint8_set(0b10111001, 1, 0b1001)
assertBits(b2, '11001001')

const b3 = uint8_set(0b10111001, 3, 0b1001)
assertBits(b3, '10110011')

const b4 = uint8_set(0b10111001, 4, 0b1001)
assertBits(b4, '10111001')

const b5 = uint8_set(0b10111001, 5, 0b101)
assertBits(b5, '10111101')

const c1 = uint8_clear(0b10111001, 2, 3)
assertBits(c1, '10000001')

const c2 = uint8_clear(0b10111001, 0, 3)
assertBits(c2, '11001')

const d1 = uint8_set_with_leading_space(0b10111001, 2, 3, 2)
assertBits(d1, '10010001')

const e1 = new Uint8Array(16)
buf_set(e1, 0, 5)
assertBuffer(e1, 0, '10100000')
buf_set(e1, 6, 5)
assertBuffer(e1, 0, '10100010')
assertBuffer(e1, 1, '10000000')

const e2 = new Uint8Array(16)
buf_set(e2, 0, 5)
assertBuffer(e2, 0, '10100000')
buf_set(e2, 20, 5)
assertBuffer(e2, 0, '10100000')
assertBuffer(e2, 1, '0')
assertBuffer(e2, 2, '1010')
assertBuffer(e2, 3, '0')

const f1 = new Uint8Array(16)
f1[0] = 0b10111001
f1[1] = 0b10111001
f1[3] = 0b10111001
const f2 = new Uint8Array(16)
buf_get(f1, 0, 8, f2, 0)
assertBuffer(f2, 0, '10111001')

const f3 = new Uint8Array(16)
f3[0] = 0b10111001
f3[1] = 0b10111001
f3[3] = 0b10111001
const f4 = new Uint8Array(16)
buf_get(f3, 1, 8, f4, 0)
assertBuffer(f4, 0, '1110011')
assertBuffer(f4, 1, '0')

const f5 = new Uint8Array(16)
f5[0] = 0b10111001
f5[1] = 0b10111001
f5[3] = 0b10111001
const f6 = new Uint8Array(16)
buf_get(f5, 0, 16, f6, 0)
assertBuffer(f6, 0, '10111001')
assertBuffer(f6, 1, '10111001')

const f7 = new Uint8Array(16)
f7[0] = 0b10111001
const f8 = new Uint8Array(16)
buf_get(f7, 2, 2, f8, 0)
assertBuffer(f8, 0, '11')

const f9 = new Uint8Array(16)
f9[0] = 0b10111001
f9[1] = 0b10111001
f9[3] = 0b10111001
const f10 = new Uint8Array(16)
buf_get(f9, 0, 2, f10, 0)
assertBuffer(f10, 0, '10')

const f11 = new Uint8Array(16)
f11[0] = 0b10111001
f11[1] = 0b10111001
f11[3] = 0b10111001
const f12 = new Uint8Array(16)
buf_get(f11, 1, 16, f12, 0)
assertBuffer(f12, 0, '1110011')
assertBuffer(f12, 1, '1110010')

function buf_get(readUint8Buffer, readLeft, readSize, writeUint8Buffer, writeLeft) {
  buf_get_impl(readUint8Buffer, readLeft, readSize, writeLeft, function(l, s, b){
    buf_set_with_leading_space(writeUint8Buffer, l, s, b)
  })
}

function buf_get_with_leading_space(readUint8Buffer, readLeft, readSize) {
  let uint32 = 0
  buf_get_impl(readUint8Buffer, readLeft, readSize, 0, function(l, s, b){
    uint32 = uint8_set_with_leading_space(uint32, l, s, b)
  })
  return uint32
}

// since this was used in two places above I refactored it out.
function buf_get_impl(readUint8Buffer, readLeft, readSize, writeLeft, cb) {
  let i = 0
  while (readSize) {
    let readUint8Offset = readLeft >> 3
    let readBitOffset = readLeft % 8
    let readRightBitSize = Math.min(8, readSize + readBitOffset) - readBitOffset
    var strange = (readBitOffset + readRightBitSize) == 8
    let uint8 = readUint8Buffer[readUint8Offset]
    let bits = uint8_get(uint8, readBitOffset, readRightBitSize)
    cb(writeLeft, strange ? readRightBitSize : 8, bits)
    readSize -= readRightBitSize
    if (strange) {
      let uint8 = readUint8Buffer[readUint8Offset + 1]
      let bits = uint8_get(uint8, 0, 8 - readRightBitSize)
      cb(writeLeft, 8, bits)
      writeLeft += (8 - readRightBitSize)
      readLeft += (8 - readRightBitSize)
      // readSize -= (8 - readRightBitSize)
    }
    writeLeft += readRightBitSize
    readLeft += readRightBitSize
  }
}

function buf_set_with_leading_space(writeUint8Buffer, left, size, writeUint8) {
  buf_clear(writeUint8Buffer, left, size - left)
  let writeSize = uint8_get_size(writeUint8)
  let newLeft = left + size - writeSize
  buf_set(writeUint8Buffer, newLeft, writeUint8)
}

function buf_set(writeUint8Buffer, left, writeUint8) {
  let writeSize = uint8_get_size(writeUint8)
  let writeUpdated = writeUint8 << (8 - writeSize)
  let readUint8Left = left >> 3
  let readUint8a = writeUint8Buffer[readUint8Left]
  let readBitLeft = left % 8
  let readStartSize = 8 - readBitLeft
  let writeUint8Subseta = uint8_get(writeUpdated, 0, readStartSize)
  let outUint8a = uint8_set(readUint8a, readBitLeft, writeUint8Subseta)
  writeUint8Buffer[readUint8Left] = outUint8a
  let extent = readBitLeft + writeSize
  if (extent > 8) {
    let writeUint8SubsetbSize = extent - 8
    let writeUint8Subsetb = uint8_get(writeUpdated, readStartSize, writeUint8SubsetbSize)
    let readUint8b = writeUint8Buffer[readUint8Left + 1]
    let clearedUint8 = uint8_clear(readUint8b, 0, writeUint8SubsetbSize)
    let outUint8b = uint8_set_with_leading_space(clearedUint8, 0, writeUint8SubsetbSize, writeUint8Subsetb)
    writeUint8Buffer[readUint8Left + 1] = outUint8b
  }
}

function buf_clear(writeUint8Buffer, left, size) {
  // this currently allows local tests to pass
  // as long as you are just loading into a buffer
  // straight left to right.
  // i haven't gotten to clearing buffers yet, so
  // you can just ignore this for now to keep it simpler.
}

function uint8_get_size(n) {
  let i = 0
  while (n) {
    i++
    n >>= 1
  }
  return i
}

function uint8_get(n, l, s) {
  let r = 8 - l - s
  let p = 1 << 8
  let o = p - 1
  let ol = o << r
  let or = o >> l
  let om = or & ol
  let x = n & om
  return x >> r
}

function uint8_set(n, i, x) {
  let o = 0xff // 0b11111111
  let c = uint8_get_size(x)
  let j = 8 - i // right side start
  let k = j - c // right side remaining
  let h = c + i
  let a = x << k // set bits
  let b = a ^ o // set bits flip
  let d = o >> h // mask right
  let q = d ^ b //
  let m = o >> j // mask left
  let s = m << j
  let t = s ^ q // clear bits!
  let w = n | a // set the set bits
  let z = w & ~t // perform some magic https://stackoverflow.com/q/8965521/169992
  return z
}

function uint8_clear(n, i, c) {
  let s = i + c
  let r = 8 - s
  let p = 1 << 8
  let o = p - 1
  let j = o >> i
  let k = o << r
  let h = j & k
  let g = ~h
  let z = n & g
  return z
}

function uint8_set_with_leading_space(uint8, left, size, value) {
  uint8 = uint8_clear(uint8, left, size)
  let writeSize = uint8_get_size(value)
  let newLeft = left + size - writeSize
  return uint8_set(uint8, newLeft, value)
}

function assertBits(a, b) {
  assertEqual(a.toString(2), b)
}

function assertBuffer(buffer, index, value) {
  assertEqual(buffer[index].toString(2), value)
}

function assertEqual(a, b) {
  if (a != b) {
    throw new Error(`${a} != b`)
  }
  console.log('success')
}

Could you show how to implement the buf_* functions (specifically just buf_get and buf_set) in the most optimal, simplified, straightforward manner, whatever implementation is fewest operations? The code can be reorganized or rearchitected however makes it possible, so if switching from left-to-right reading to right-to-left reading (per 8-bits) helps, then that makes sense.

\$\endgroup\$
  • \$\begingroup\$ I suggest sticking with right to left, because that's how they are done in all JS contexts. \$\endgroup\$ – FreezePhoenix Sep 25 '20 at 12:33
  • 4
    \$\begingroup\$ Additionally, your variable naming is very poor in your uint8_* functions. \$\endgroup\$ – FreezePhoenix Sep 25 '20 at 12:35
  • \$\begingroup\$ I noticed in your f7/f8 test case, you copy the two bits "11" over to the f8 buffer. Your last parameter to buf_get() was 0, which I presume means the zeroith index - if so, shouldn't the result be "11000000", not "11". Or am I misunderstanding what this parameter is. \$\endgroup\$ – Scotty Jamison Jan 12 at 5:57
6
+250
\$\begingroup\$

Keep it simple

OMDG it took me longer to work out what your code was doing than to write a solution.

Some of it seams to have taken the most complex possible path to a solution, and I am still not 100% sure (as I gave up deciphering that code) what the buf_get_with_leading_space means with leading_space. I am assuming you mean leading off bits?

I get the strong feeling you are not familiar with binary as you are doing some very strange things

For example

assertBuffer(f12, 0, '1110011')

function assertBuffer(buffer, index, value) {
  assertEqual(buffer[index].toString(2), value)
}

function assertEqual(a, b) {
  if (a != b) {
    throw new Error(`${a} != b`)
  }
  console.log('success')
}

Why convert the bytes to a string. Will also work as numbers

assertBuffer(f12, 0, 0b1110011);

function assertBuffer(buffer, index, value) {
  assertEqual(buffer[index], value);
}

function assertEqual(a, b) {
  if (a != b) { throw new Error(`${a} != b`) }
  console.log('success');
}

BTW

  • Please use semicolons.
  • DONT USE snake_case. Javascript uses camelCase.
  • Use constants when you can.
  • Give variables and functions meaningful names.

Bit order

Bits to the left are high order bits, bits to the right are low order bits.

As the calculations required to get a bit from a byte (word, long, whatever) change depending on the indexing you use high to low or low to high, you can use an array of bit masks to pre calculate the values needed

  • High to low bits would be [128, 64, 32, 16, 8, 4, 2, 1]
  • [1, 2, 4, 8, 16, 32, 64, 128] no surprise is low to high bits.

A function to create bit masks. It will create masks for any number of bits up to 32 (the limit using JS Number)

function createBitOrder(fromLeft, bits) {
    const bitMasks = [];
    var i = bits;
    while (i-- > 0) { bitMasks.push(fromLeft ? (1 << i) : (1 << (bits - 1 - i))) }
    return bitMasks;
}

Reading bits

Reading a bit is very easy, in this case using High to low order (using lookup array bits the example reads 4 bits from the 2 byte buffer

Example

   const bits = [128, 64, 32, 16, 8, 4, 2, 1];
   const readBit = (buf, bit) => buf[bit >> 3] & bits[bit % 8] ? 1 : 0;

   const buf = [2, 128];  // 6th and 8th bit from left set
   var bit = 6;
   console.log("bit: " + bit + " = " + readBit(buf, bit++));
   console.log("bit: " + bit + " = " + readBit(buf, bit++));
   console.log("bit: " + bit + " = " + readBit(buf, bit++));
   console.log("bit: " + bit + " = " + readBit(buf, bit++));

Write bits

To write a bit you need to first clear the bit at the write position and then set it.

Again to allow for bit order changes use an array to mask the bits you want to keep, then set the bit using the array bits

Example

const bits = [128, 64, 32, 16, 8, 4, 2, 1];
const masks = bits.map(v => 0xFF ^ v); // creates mask
const readBit = (buf, bit) => buf[bit >> 3] & bits[bit % 8] ? 1 : 0;

const setBit = (buf, bit, val) => 
    buf[bit >> 3] = (buf[bit >> 3] & masks[bit % 8]) + (val ? bits[bit % 8] : 0);

const buf = [2,0x80];  // 6th and 8th bit from left set
var bit = 6;
setBit(buf, 6, 0); // bit 6 to 0
setBit(buf, 7, 1); // bit 7 to 1
setBit(buf, 8, 0); // bit 8 to 0
setBit(buf, 9, 1); // bit 9 to 1

console.log("bit: " + bit + " = " + readBit(buf, bit++));
console.log("bit: " + bit + " = " + readBit(buf, bit++));
console.log("bit: " + bit + " = " + readBit(buf, bit++));
console.log("bit: " + bit + " = " + readBit(buf, bit++));

Bit stream

The common way to read and write bits is via a stream, in this case we would call it a bit stream.

A stream has a buffer from which to read or write and a position. Position is where in the buffer the read or write is. The position is in bits eg pos 8 is the high bit of the second byte if order is high to low

The stream is created by passing the mask that defines the order.

There are two setters to set the position and the buffer.

Reading and writing bits automatically increments the bit position

Example bit stream

function BitStream(mask) {
    var pos = 0, buf = [];
    const maskOut = mask.map(v => 0xFF ^ v);
    return {
        set pos(p) { pos = p },
        set buf(data) { buf = data },
        get bit() { return (buf[pos >> 3] & mask[pos++ % 8]) ? 1 : 0 },
        set bit(val) { 
            const byte = pos >> 3, bit = pos ++ % 8;
            buf[byte] = (buf[byte] & maskOut[bit]) + (val ? mask[bit] : 0);
        },
    };
}

Thus to use in one of your examples

const f11 = new Uint8Array(16)
f11[0] = 0b10111001
f11[1] = 0b10111001
f11[3] = 0b10111001
const f12 = new Uint8Array(16)
buf_get(f11, 1, 16, f12, 0)
assertBuffer(f12, 0, '1110011')
assertBuffer(f12, 1, '1110010')

Would be

const readStream = BitStream(createBitOrder(true, 8));
const writeStream = BitStream(createBitOrder(true, 8));


function bufGet(bufA, readPos, bits, bufB, writePos) {
    readStream.buf = bufA;     // set buffers
    writeStream.buf = bufB;
    readStream.pos = readPos;  // set read and write positions
    writeStream.pos = writePos;
    while (bits-- > 0) { writeStream.bit = readStream.bit }
}

const f11 = [0b10111001, 0b10111001, 0b10111001];
const f12 = [0, 0, 0];
bufGet(f11, 1, 16, f12, 0);

Complete example

Using bit streams.

It replaces your buf_clear with BitMovers.clearBits(buf, fromBit, numBits)

As all the other buf_* all do the same thing there is only a need for and all the others with BitMovers.moveBits(fromBuf, fromBit, numBits, toBuf, toBit) that will move bits from one stream, to the other.

Is it quicker?? maybe, i will leave it to you to find that out.

function createBitOrder(fromLeft, bits) {
    const bitMasks = [];
    var i = bits;
    while (i-- > 0) { bitMasks.push(fromLeft ? (1 << i) : (1 << (bits - 1 - i))) }
    return bitMasks;
}
function BitStream(mask) {
    var pos = 0, buf = [];
    const maskOut = mask.map(v => 0xFF ^ v);
    return {
        set pos(p) { pos = p },
        set buf(data) { buf = data },
        get bit() { return (buf[pos >> 3] & mask[pos++ % 8]) ? 1 : 0 },
        set bit(val) { 
            const byte = pos >> 3, bit = pos ++ % 8;
            buf[byte] = (buf[byte] & maskOut[bit]) + (val ? mask[bit] : 0);
        },
        writeTo(stream, bits) { while (bits-- > 0) { stream.bit = this.bit } },
        clear(bits) { while (bits-- > 0) { this.bit = 0 } },
    };
}

// replacement functions
function BitMovers() {
    const mask = createBitOrder(true, 8);  // high to low
    const read = BitStream(mask);
    const write = BitStream(mask);
    return {
        moveBits(fromBuf, fromBit, numBits, toBuf, toBit) {
            read.buf = fromBuf;
            write.buf = toBuf;
            read.pos = fromBit;
            write.pos = toBit;
            read.writeTo(write, numBits);
        },
        clearBits(buf, fromBit, numBits) {
            write.buf = buf;
            write.pos = fromBit;
            write.clear(numBits);
        },
    }
}

const movers = BitMovers();
const bufA = [255,0,255,0];
const bufB = [0,0,0,0];
movers.moveBits(bufA, 4, 8, bufB, 20);
movers.clearBits(bufB, 1, 6);
<code id="info"> </code>



UPDATE

As requested in your comment

"Can you describe how/why you got mask and maskOut? Why do they have the values they do? And what do you mean by 'create bit order' exactly? "

I have updated the answer with the following.

Please note this is a very quick draft of update, I will clean it up when i get time

Useful links.

Binary numbers The basics.

There are 10 types of people in the world, those that understand binaray and those that don't.

If you don't get the joke then maybe replacing 10 with 0b10 will help. In JS a number prefixed with 0b means a number is written in binary (using only 2 digits 0 and 1) From here on in I will use this notation.

BTW hex (base 16) is prefixed with 0x and octal (base 8) is prefixed with 0

The set of counting numbers 0 to 16 as defined in JS

  • in binary 0b0 - 0b10000
  • in octal 00 - 020
  • in decimal 0 - 16
  • in hex 0x0 - 0x10

 Base 2 Binary | Base 8 Octal | Base 10 | Base 16 Hexadecimal *1 
 ------------------------------------------------------------------
        0b0000 |           00 |       0 |               0x0 
        0b0001 |           01 |       1 |               0x1 
        0b0010 |           02 |       2 |               0x2 
        0b0011 |           03 |       3 |               0x3 
        0b0100 |           04 |       4 |               0x4 
        0b0101 |           05 |       5 |               0x5 
        0b0110 |           06 |       6 |               0x6 
        0b0111 |           07 |       7 |               0x7 
        0b1000 |          010 |       8 |               0x8 
        0b1001 |          011 |       9 |               0x9 
        0b1010 |          012 |      10 |               0xA 
        0b1011 |          013 |      11 |               0xB 
        0b1100 |          014 |      12 |               0xC 
        0b1101 |          015 |      13 |               0xD 
        0b1110 |          016 |      14 |               0xE 
        0b1111 |          017 |      15 |               0xF 
       0b10000 |          028 |      16 |               0x10

  • *1 Note Hex uses A - F to represent the 10th to 15th digits, they can also be lower case a - f

In Decimal we name the positions of digits from 1 up. for example 1000 (one thousand) the one is the 4th digit. The same applies with any numbering system. The binary number 0b1000 (ten) also has 1 as the 4th digit.

JavaScript indexes are 0 based so when determining a position we start a 0. Thus binary 0b1000 (ten) has the (zero indexed) digit 1 at bit position 3

Bit positions and indexes of a byte (8 bits long)

/*
   
 0b11111111
   87654321  // bit position 
   76543210  // bit index
   ^      ^
   |      Low bit (right bit)
   High bit (left bit
  */
  

Your question in comment

"... what do you mean by 'create bit order' exactly? "

In the question there is a mention of left to right and right to left. Also you are indexing bits from the left most bit. I was unsure if your code would requier indexing using high to low and low to high so I used arrays to create the masks need to read bits in any order.

Thus "create bit order" means create array that represents the order of bits

Examples of binary values used to order bits "high to low" and "low to high"

Pos | Bit | High to low  | Calculated from pos | Low to high  | Calculated from pos 
----------------------------------------------------------------------------------
  1 |   0 |  0b10000000  |          1 << 8 - 1 | 0b00000001   |         1 << 1 - 1  
  2 |   1 |  0b01000000  |          1 << 8 - 2 | 0b00000010   |         1 << 1 - 2  
  3 |   2 |  0b00100000  |          1 << 8 - 3 | 0b00000100   |         1 << 1 - 3  
  4 |   3 |  0b00010000  |          1 << 8 - 4 | 0b00001000   |         1 << 1 - 4  
  5 |   4 |  0b00001000  |          1 << 8 - 5 | 0b00010000   |         1 << 1 - 5  
  6 |   5 |  0b00000100  |          1 << 8 - 6 | 0b00100000   |         1 << 1 - 6  
  7 |   6 |  0b00000010  |          1 << 8 - 7 | 0b01000000   |         1 << 1 - 7  
  8 |   7 |  0b00000001  |          1 << 8 - 8 | 0b10000000   |         1 << 1 - 8 
  

Binary Operators

"Can you describe how/why you got mask and maskOut? Why do they have the values they do? "

Binary operators use bit logic to do binary math on numbers. As it is a length subject I will only describe what is relevant.

We use bitwise math to apply some abstract math on a number.

Masking

Masking uses bitwise logic to help find clear and set bits within a binary number

Masking to get a bit

We use masks to remove unwanted digits (set them to zero) and keep the wanted bits (zero or one) For example, say we want to know what the digit is at the 7th position in a binary binary number is(index 6 or bit 6)

/* a random number in binary decimal 237
bin      = 0b11101101  
idx      = 6           // The bit index

maskA    = 0b01000000  // The bit mask has a 1 at bit 6
maskB    = 0b1 << idx  // Can also create mask by shifting the first bit 6 positions left
maskC    = 64          // in decimal
//         0b11101101  0b11101101  0b11101101  0b11101101 
//       & 0b01000000  0b00100000  0b00010000  0b00001000  // Mask bit 6 to 3 using Bitwise AND
//       ------------------------------------------------
//       = 0b01000000  0b00100000  0b00000000  0b00001000

// as boolean
isBit6On = (bin & maskA) !== 0        // is true in this case. NOTE the () around bitwise AND operation 
isBit6On = (bin & maskB) !== 0        // using the calculated mask
isBit6On = (bin & 0b1 << idx) !== 0   // calculating the mask just in time
isBit6On = (bin & 1   << idx) !== 0   // Note 1 and 0b1 are equivilant

// as number 0 or 1
bitValue = 0b11101101 & 0b01000000 ? 1 : 0 // ternary
bitValue - (237 & 64) === 0 ? 0 : 1
bitValue = ~~(bin & maskA);                // Not Not operation  
*/

  • Note that bitwise operations have a lower Precedence than equality ==, === and inequality operators !=, !== and thus need the brackets ()

Mask to clear.

We use a mask to clear a bit by inverting the bits of the mask used to get a bit

/* 
bin       = 0b11101101            // random bit field
bit       = 6
bitMask   = 0b01000000            // bit 6
maskOut   = 0b10111111            // clear mask for bit 6
maskOut   = 191                   // Decimal 255 - 64
maskOut   = 0b11111111 ^ bitMask  // Calculating clear mask from bit mask using XOR
maskOut   = 1 << bit ^ 0b11111111 // calculated from bit index

//         0b11101101
//       & 0b10111111   // bitwize AND with clear mask
//       = 0b10101101   // bit 6 is now zero

bit6Cleared = bin & maskOut
bit6Cleared = bin & (bitMask ^ 0b11111111)  // calculate mask out from bit mask just in time
*/

Masks to set a bit

To set a bit we first clear the bit we want to set, then we set the bit the value we want by shifting the value to the correct bit position and ORing that value with the masked out bits.

/* 
bin       = 0b10101101            // random bit field
bit       = 6                     // bit to set
bitValue  = 1                     // Value to set bit to  can be 0 or 1
maskOut   = 0b10111111            // clear mask for bit 6

result    =  bin & maskOut | bitValue << bit               // remove bit 6 and add bit value using OR
result    =  bin & 1 << bit ^ 0b11111111 | bitValue << bit // Calculating masks just in time


//         0b11101101
//       & 0b10111111   // clear mask
//         ----------
//         0b10101101   // bit 6 is now zero
//
//                0b1   // value to set
//      <<          6 
//         0b00000010   // sifted 1    
//         0b00000100   // sifted 2    
//         0b00001000   // sifted 3    
//         0b00010000   // sifted 4    
//         0b00100000   // sifted 5   
//         0b01000000   // sifted 6
//
//         0b10101101   // Cleared bit 6
//       | 0b01000000   // OR with value shifted to bit pos
//       = 0b11101101   // result


*/

\$\endgroup\$
  • \$\begingroup\$ I am definitely not familiar with binary, I am learning it as I go haha :) \$\endgroup\$ – Lance Pollard Jan 14 at 7:59
  • \$\begingroup\$ Is for example looping through an integer to clear bits the best way to do it? Would some bit manipulation magic to clear a range of bits work better or no? \$\endgroup\$ – Lance Pollard Jan 14 at 8:07
  • 1
    \$\begingroup\$ @LancePollard It depends on how you read and write to the buffers. This is a general random access stream solution and assumes you are doing many small read and writes to random locations.. If you are doing a sequential read and write you would just buffer read and writes calls, only moving bytes (best uint32) when you get to byte boundaries. \$\endgroup\$ – Blindman67 Jan 14 at 8:18
  • \$\begingroup\$ Can you describe how/why you got mask and maskOut? Why do they have the values they do? And what do you mean by "create bit order" exactly? Where/when else would that function come in handy? \$\endgroup\$ – Lance Pollard Jan 15 at 7:47
  • \$\begingroup\$ @LancePollard I have updated answer with a draft version. I am short on time so will need to come back and edit it some time over the weekend if I can. \$\endgroup\$ – Blindman67 Jan 15 at 15:11
2
\$\begingroup\$

Helper Functions

I see that you've already asked a separate question for the helper functions here, and others have already done a fine job answering it, so I won't add anything to it here. The rewrite I came up with will use a variation of the helper functions that operate directly on the byte array as defined below - this isn't necessary, but I felt these versions helped in this particular scenario.

const createMask = (size, rightIndex = 0) => (1 << size) - 1 << rightIndex

const getBitsFromByte = (byteArray, bitIndex, count) => {
  const byteIndex = Math.floor(bitIndex / 8)
  const rightPad = 8 - count - bitIndex % 8
  const mask = createMask(count, rightPad)
  return (byteArray[byteIndex] & mask) >>> rightPad
}

const setBitsInByte = (byteArray, bitIndex, data, bitsInData) => {
  const byteIndex = Math.floor(bitIndex / 8)
  const rightPad = 8 - bitsInData - bitIndex % 8
  byteArray[byteIndex] &= ~createMask(bitsInData, rightPad)
  byteArray[byteIndex] |= data << rightPad
}

buf_set()

It looks like you still have some bugs to iron out with this function, some of which might stem from logical misunderstandings. buf_set() is supposed to take an unsigned byte as input and insert it into the buffer. Your current implementation doesn't allow me to set a byte with leading zeros. Lets take the byte 00011000 as an example, which is technically equal to 11000. Your implementation tries to count the number of bits in the byte by finding the left-most bit that is set. In this example, it would think that I'm only trying to pass in 5 bits. Then, it tries to right-fill the data with zeros to fill the byte, resulting in 11000000 getting set. The only proper way to implement this function is to assume that a full byte is being passed in every time. If someone passes in 0b11, they're really passing in 0b00000011, a full byte (0b11 === 0b00000011).

There's also a lot of logic repeated inside the if and outside. This function can be greatly simplified by refactoring out these common parts into a helper function. In fact - that's exactly why I chose to modify the helper functions a bit - the setBitsInByte() helper function is what you get after pulling out the common parts of buf_set(). The final solution is a lot cleaner:

function buf_set(byteArray, bitIndex, byteToWrite) {
  const byteOffset = bitIndex % 8
  setBitsInByte(byteArray, bitIndex, byteToWrite >>> byteOffset, 8 - byteOffset)
  if (byteOffset !== 0) {
    setBitsInByte(byteArray, bitIndex + (8 - byteOffset), byteToWrite & createMask(byteOffset), byteOffset)
  }
}

buf_get()

This function has some bugs in it too. This particular issue can be seen in your test case too, so at least one of us is not understanding the requirements to this function ...

const f7 = new Uint8Array(16)
f7[0] = 0b10111001
const f8 = new Uint8Array(16)
buf_get(f7, 2, 2, f8, 0)  // <-- This specifies that you are only going to override 2 bits at index 0 of f8
assertBuffer(f8, 0, '11') // <-- 11 is equivalent to 00000011, which means you wrote
                          //     to the last two bits instead (at index 6, not index 0).

Some general cleanup would be good too:

  • buf_get() is not a great name - what you're really doing is copying bits, not retrieving them, so maybe call it buf_copy().
  • Your i variable is unused.
  • You do not use var and let in a consistent way. It seems you prefer let, so change the var to let.
  • You'll notice a lot of your logic inside of the if (strange) condition is similar to what's out outside of it. If you're tactful, you can get rid of the if (strange) condition entirely and make the rest of the logic in the loop do both jobs.

Unless the byte boundaries between the src and dest buffers line up, you're not going to be able to copy any faster than half a byte at a time. i.e. byte 7's right half in the src array to byte 14's left half in the dest array, then byte 8's left half to byte 14's right half, then byte 8's right half to byte 15's left half, and so on. The following solution will copy in this fashion (as your original solution was doing too - I think).

function buf_copy(srcByteArray, srcBitIndex, bitsToCopy, destByteArray, destBitIndex) {
  const [smallerOffset, biggerOffset] = [srcBitIndex % 8, destBitIndex % 8].sort()
  const chunkSizeLookup = {
    0: 8 - (biggerOffset - smallerOffset),
    1: biggerOffset - smallerOffset || 8,
    initial: 8 - biggerOffset || 8
  }
  let bitsCopied = 0;
  for (let i = 0; bitsCopied < bitsToCopy; ++i) {
    const chunkSize = Math.min(chunkSizeLookup[i === 0 ? 'initial' : i % 2], bitsToCopy - bitsCopied)
    const data = getBitsFromByte(srcByteArray, srcBitIndex + bitsCopied, chunkSize)
    setBitsInByte(destByteArray, destBitIndex + bitsCopied, data, chunkSize)
    bitsCopied += chunkSize
  }
}

On the first iteration, we need to copy enough bits over to bring us to a byte boundary (the "initial" in the chunkSizeLookup is the initial number of bits being copied). From there on out we're just alternating between two different jump sizes to bring us from one byte-boundary to the next. The || 8 is used where the chunkSizeLookup logic is done to make sure we never try to do an iteration with a chunk-size of 0, a waste of time.

Optimization

While I tried to make these function performant, I didn't go overboard. I focused a little more on code quality and correctness. Further micro-optimizations can be done if those examples aren't fast enough, but some optimizations depend on what you're optimizing for. For example, in buf_copy(), are you expecting that it'll only get called a handful of times, but with the intention of copying large amounts of data? Then do what you can to move stuff out of the loop, even if it makes the code before the loop a little extra expensive to run. The opposite would be true if we're trying to optimize for lots of calls that only expect to copy one or two bytes.

Below are some general ideas of how you can micro-optimize it - but please don't actually do these things unless it's needed, as these suggestions can really ruin the readability of the code without making it a whole lot faster. It also isn't uncommon for someone to try to optimize something that the runtime was already optimizing in a better way, causing their code to be both slower and unreadable. This is one reason why it's always important to benchmark when trying to make performant code. This, among other reasons, is also why simply counting the number of operations isn't the best metric for how fast a function will run.

Potential micro-optimizations:

  • Math.floor(bitIndex / 8) can be replaced with bitIndex >>> 3.
  • Inline the helper functions. Function calls are actually relatively expensive, and there's a little bit of repeated logic going on inside the helper functions that can be optimized out if they are inlined.
  • Replace Math.min(a, b) with a < b ? a : b. The user of .sort() can have a similar optimization done.
  • Is it common for byte-boundaries to line up when calling buf_copy() (meaning srcBitIndex % 8 === destBitIndex % 8)? If you really want to, you could copy-paste the for loop, optimize it for this special case (there's a little logic in the loop that's not needed in this special case), and use this loop instead when the byte-boundaries do line up. But ... don't actually do this.
  • etc

All together

A complete example:

const createMask = (size, rightIndex = 0) => (1 << size) - 1 << rightIndex

const getBitsFromByte = (byteArray, bitIndex, count) => {
  const byteIndex = Math.floor(bitIndex / 8)
  const rightPad = 8 - count - bitIndex % 8
  const mask = createMask(count, rightPad)
  return (byteArray[byteIndex] & mask) >>> rightPad
}

const setBitsInByte = (byteArray, bitIndex, data, bitsInData) => {
  const byteIndex = Math.floor(bitIndex / 8)
  const rightPad = 8 - bitsInData - bitIndex % 8
  byteArray[byteIndex] &= ~createMask(bitsInData, rightPad)
  byteArray[byteIndex] |= data << rightPad
}

function buf_copy(srcByteArray, srcBitIndex, bitsToCopy, destByteArray, destBitIndex) {
  const [smallerOffset, biggerOffset] = [srcBitIndex % 8, destBitIndex % 8].sort()
  const chunkSizeLookup = {
    0: 8 - (biggerOffset - smallerOffset),
    1: biggerOffset - smallerOffset || 8,
    initial: 8 - biggerOffset || 8
  }
  let bitsCopied = 0;
  for (let i = 0; bitsCopied < bitsToCopy; ++i) {
    const chunkSize = Math.min(chunkSizeLookup[i === 0 ? 'initial' : i % 2], bitsToCopy - bitsCopied)
    const data = getBitsFromByte(srcByteArray, srcBitIndex + bitsCopied, chunkSize)
    setBitsInByte(destByteArray, destBitIndex + bitsCopied, data, chunkSize)
    bitsCopied += chunkSize
  }
}

function buf_set(byteArray, bitIndex, byteToWrite) {
  const byteOffset = bitIndex % 8
  setBitsInByte(byteArray, bitIndex, byteToWrite >>> byteOffset, 8 - byteOffset)
  if (byteOffset !== 0) {
    setBitsInByte(byteArray, bitIndex + (8 - byteOffset), byteToWrite & createMask(byteOffset), byteOffset)
  }
}

// EXAMPLE USAGE //

const format = byte => byte.toString(2).padStart(8, '0')
const buffer1 = new Uint8Array(16)
buffer1[0] = 0b00011000
buffer1[1] = 0b11100111
buf_set(buffer1, 4, 0b00110011)
console.log(format(buffer1[0])) // 00010011
console.log(format(buffer1[1])) // 00110111

const buffer2 = new Uint8Array(16)
buf_copy(buffer1, 4, 10, buffer2, 2)
console.log(format(buffer2[0])) // 00001100
console.log(format(buffer2[1])) // 11010000

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.