Как эффективно читать биты из байтов? - PullRequest
Новая
       33

Как эффективно читать биты из байтов?

9 голосов
/ 22 октября 2011

Я работаю над проектом, который включает WebSockets, и данные между сервером (Node.js) и клиентом (Chrome) отправляются в настраиваемом (очень простом) формате для обмена данными, который я настроил.

Я отправляю данные по 3 бита, потому что я отправляю элементы, которые имеют 8 возможностей. Формат данных выглядит следующим образом: 

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

В настоящее время я разбираю элементы из байтов так: 

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;

Лично это кажется слишком сложным. Проблема в том, что это только сложно, потому что я получаю данные в байтах, кратных 8. Чтобы разобрать элементы из 3 бит, мне нужно сдвинуть биты, выполняя операции AND, и потому что 8 не делится на 3 I иногда даже приходится объединять части двух байтов, например, для itemC.

Было бы гораздо эффективнее читать эти данные как группы по 3 бита, а не как группы из 8 бит.

То, что я придумал, - это преобразовать все байты в биты в строку, используя .toString(2), затем используя .substring, чтобы получить подстроку длиной 3, и преобразовав обратно в число с parseInt(bitString, 2), но я думаю, это не тот способ, так как манипуляции со строками медленные, и я на самом деле ничего не делаю со строками.

Можно ли читать биты в группах, например, 3 вместо разбора их из байтов? Или есть более эффективный способ чтения битов из байтов?

Ответы [ 4 ]

6 голосов
/ 22 октября 2011

Операции двоичного И и сдвига битов - самый быстрый способ сделать это.Они хорошо переводят в инструкции машинного кода.Единственный способ еще больше ускорить это - пожертвовать пропускной способностью ради скорости, например, просто не используя более 3 бит на байт, но, исходя из вашего вопроса, вы, вероятно, уже рассмотрели и отклонили этот компромисс.

4 голосов
/ 15 ноября 2011 
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
0 голосов
/ 04 апреля 2014

Мы можем получить нужное нам значение, получив соответствующее 16-разрядное целое число, а затем сдвинуть его.

Понятно, что для получения значения i-th мы должны получить 16-битное целое число со смещением в байтах, которое соответствует (bits * (i + 1) - 16)/8 <= offset <= (bits * i)/8.

Давайте возьмем M=bits*i/8, поэтому у нас есть M + bits/8 - 2<= offset <= M. Затем мы получаем минимальное смещение как ceil(M + bits/8 - 2) и вычисляем позицию i-го значения в 16-битном целом числе по смещению. Я только что написал следующую функцию 

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;
}

И следующий пример для чтения 8 5-битных значений из буфера длиной 5 байтов. 

// 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]);
}

Когда я запускаю узел test.js, я получаю 

got buffer with length=8
0-31
1-31
2-31
3-31
4-31
5-31
6-31
7-26
0 голосов
/ 22 октября 2011

если заботится о порядке байтов, вы можете обращаться к нему как к массиву int или long int.Существует еще одна возможность не использовать бит 3 и бит 7

...