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.
uint8_*
functions. \$\endgroup\$ – FreezePhoenix Sep 25 '20 at 12:35