How to read bits from bytes efficiently?

Question

I am working on a project that includes WebSockets, and the data between the server (Node.js) and the client (Chrome) is sent using a custom (very simple) data exchange format that I configured.

I send data in pieces of 3 bits, because I send elements that have 8 possibilities. The data format is as follows:

0 1 bit index 01234567 8901... item aaabbbcc cddd... 

I am currently parsing elements from bytes as follows:

 var itemA = bytes[0] >> 5; var itemB = (bytes[0] >> 2) & 7; var itemC = (bytes[0] & 3) << 1 | bytes[1] >> 7; var itemD = (bytes[1] >> 4) & 7; 

Personally, this seems too complicated. The problem is that it is complex, because I get data in bytes that are multiples of 8. To parse elements from 3 bits, I need to perform a bit shift by performing AND operations and because 8 is not divisible by 3 I sometimes you even have to combine parts of two bytes, for example, for itemC .

It would be much more efficient to read this data as groups of 3 bits instead of groups of 8 bits.

What I came up with is converting all bytes to bits into a string using .toString(2) and then using .substring to get a substring of length 3 and converting back to a number using parseInt(bitString, 2) , but I suppose this is not a way to do this, as string manipulation is slow, and I am not actually doing anything related to the string.

Is it possible to read bits in groups, for example. 3 instead of parsing them from bytes? Or is there a more efficient way to read bits from bytes?

Answer 1

Binary AND operations and bit offsets are the fastest way to do this. They translate well to machine code instructions. The only way to speed it up is to sacrifice bandwidth for speed, for example, just not using more than 3 bits per byte, but judging by your question, you probably already considered and rejected this compromise.

Answer 2

 function byte2bits(a) { var tmp = ""; for(var i = 128; i >= 1; i /= 2) tmp += a&i?'1':'0'; return tmp; } function split2Bits(a, n) { var buff = ""; var b = []; for(var i = 0; i < a.length; i++) { buff += byte2bits(a[i]); while(buff.length >= n) { b.push(buff.substr(0, n)); buff = buff.substr(n); } } return [b, buff]; } var a, b, r; a = [227, 142]; [b, r] = split2Bits(a, 3); //b = ["111", "000", "111", "000", "111"]; //r = '0'; //rest of bits 

Answer 3

If endian-ness takes care, you can access it as an int or long int array. There is another possibility not to use bit 3 and bit 7

Answer 4

We can get the value we need by getting the corresponding 16-bit integer, and then lower it.

Clearly, to get the i-th value, we need to get a 16-bit integer with an offset in bytes that matches (bits * (i + 1) - 16)/8 <= offset <= (bits * i)/8 .

Take M=bits*i/8 , so we have M + bits/8 - 2<= offset <= M Then we get the minimum offset as ceil(M + bits/8 - 2) and calculate the position of the i-th value at the 16-bit integer offset. I just wrote the following function

 function getDataFromStream(buffer, bitsPerValue, endianness) { var valuesCount = Math.floor(buffer.length * 8 / bitsPerValue); var ret = new Buffer(valuesCount); if (valuesCount > 0) { for (var i = 0; i < valuesCount; i++) { var offsetMin = Math.ceil(bitsPerValue * i / 8. + bitsPerValue / 8. - 2); if (offsetMin < 0) { offsetMin = 0; } if(endianness == 'BE') var wordWithValue = buffer.readUInt16BE(offsetMin, true); else var wordWithValue = buffer.readUInt16LE(offsetMin, true); var offsetInWord = bitsPerValue * i - offsetMin * 8; var leftInWord = 16 - bitsPerValue - offsetInWord; // then get value in the word by shifting and then remove other bits by "%" ret[i] = (wordWithValue >> (endianness == 'BE' ? leftInWord : offsetInWord )) % Math.pow(2, bitsPerValue); } } return ret; } 

And the following example to read 8 5-bit values ​​from a buffer with a length of 5 bytes.

 // buffer with 5 bytes var xx = new Buffer(5); xx[0] = 255; xx[1] = 255; xx[2] = 255; xx[3] = 255; xx[4] = 250; // get data, 5bits per value. var yy = getDataFromStream(xx, 5, 'BE'); console.log('got buffer with length='+ yy.length); for(i = 0; i < yy.length; i++){ console.log(i+'-'+yy[i]); } 

When I run node test.js, I got

 got buffer with length=8 0-31 1-31 2-31 3-31 4-31 5-31 6-31 7-26