Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Общие вопросы > Побитовые сдвиги


Автор: MuToGeN 5.9.2003, 16:56
Такая ситуация... Есть "кусок фаила", в нем структура из N байт такого плана: первые 5 бит (именно бит) - кол-во бит, используемых для описания четырех остальных параметров, и дальше, собственно, эти самые 4 параметра. Т.е. к примеру:
user posted image
Здесь первые 5 бит - 00011, 3, тобишь, т.е. по 3 бита на остальные 4 параметра. То, что отмечено серым - не используется. У меня оно делается примерно так:
Код
bool SWF_File::loadRect(unsigned int startPosition,SWF_Rect* Rect)
{
       unsigned char rectValuesLenght;
       unsigned char numBytes,numBits;

       rectValuesLenght=fileBuffer[startPosition] >> 3; // получаем кол-во бит, используемое для кождого параметра
       numBits=5+rectValuesLenght*4; // суммарное кол-во битов для описания этой структуры
       numBytes=ceil(((double)numBits)/8.0); // суммарное кол-во байт для описания структуры
       unsigned char* rectBuffer=new unsigned char[numBytes]; // отдельный буффер под это дело
       for(i=0;i<numBytes;i++)
               rectBuffer[i]=fileBuffer[startPosition+i]; // копирование части fileBuffer'а в rectBuffer... может, это дело тоже можно
                                                      // сделать чуток по-иному? мне кажется, что мое решение - не лучшее...
       /*
       а вот как из rectBuffer вытащить значения под номерами 2, 3, 4 и 5 на картинке? полдня над этим бьюсь...
       */
       delete [] rectBuffer;
       return true;
}
Мдя, отвык я от C++ smile.gif

Автор: mr.DUDA 5.9.2003, 17:53
Если "buf" - буфер (массив) из 3-х байт, расположенных по приведенной схеме (т.е. buf[0] - самый левый, а buf[2] - самый правый), то вытянуть все 5 параметров и раскидать по переменным "param1...param5" можно вот так:
Код
unsigned char buf[3];
unsigned char  param1,param2,param3,param4,param5;

param1 = (buf[0] & 0xf8)>>3;
param2 = (buf[0] & 7);
param3 = (buf[1] & 0xe0)>>5;
param4 = (buf[1] & 0x1c)>>2;
param5 = ((buf[1] & 3)<<1) | ((buf[2] & 0x80)>>5;

Автор: MuToGeN 5.9.2003, 18:42
дык в том-то и дело, что первые 5 бит могут быть 11111, т.е. 31, тогда вся структура будет занимать 17 баит. Вариант, который я привел - один из самых простых

Автор: mr.DUDA 5.9.2003, 22:11
То есть я так понимаю, нужна функция типа "unsigned long GetBits(int istart, iend, char *buf)" confused.gif

Если да, то напишу завтра smile.gif т.к. сегодня уже ничего не соображаю smile.gif...

Автор: mr.DUDA 6.9.2003, 13:41
Вот и обещанный сорц:
Код
typedef unsigned char byte;
typedef unsigned long ulong;

// чтение потока битов из буфера "buf", результат - длинное целое (ulong)
// отсчет битов - слева направо
// отсчет байтов - слева направо (buf[0] - самый левый)
// правый бит из потока прижат к правой границе результата
ulong ReadBits(int iLeftBit, int nBitCount, byte *buf)
{
    ulong result = 0;

    int iRightBit = iLeftBit + nBitCount - 1;
    int leftBitInByte = iLeftBit % 8;
    int rightBitInByte = iRightBit % 8;
    byte leftMask = 0xff>>leftBitInByte;
    byte rightMask = 0xff<<(7 - rightBitInByte);
    int iLeftByte = iLeftBit>>3;
    int iRightByte = iRightBit>>3;

    // первый и последний биты - в пределах одного байта
    if(iLeftByte == iRightByte)
    {
         result = (result | buf[iLeftByte] & leftMask & rightMask)>>(7 - rightBitInByte);
    }
    else
    {
         result = buf[iLeftByte] & leftMask;
         for(int iByte = iLeftByte; iByte < (iRightByte-1); iByte++)
              result = (result<<8) | buf[iByte];
         result = (result<<(rightBitInByte+1)) | ((buf[iRightByte] & rightMask)>>(7-rightBitInByte));
    }

    return result;
}


// чтение 4-х параметров, возвращает дин. массив параметров типа ulong
ulong *ReadParams(byte *buf)
{
    int nEachParamLenght = ReadBits(0, 5, buf);
    int nBytesCnt = (5 + nEachParamLenght*4)>>3 + 1;
    ulong *params = new ulong[4];
    int iBit = 5;
    for(int iParam = 0; iParam < 4; iParam++, iBit += nEachParamLenght)
         params[iParam] = ReadBits(iBit, nEachParamLength, buf);
    return params;
}


// тестовый пример - взят с рисунка MuToGeN'а
int main(int argc, char* argv[])
{
    byte buf[] = {0x1d, 0xb9, 0x80};
    ulong *params = ReadParams(buf);

    // ...

    delete params;
    return 0;
}

ЗЫ, наверное ещё как-то можно через std::bitset, но я не знаю как.

Автор: MuToGeN 8.9.2003, 09:33
mr.DUDA, thnx, буду пробывать. У меня самого в пятницу после употребления литра пива алгоритм на PHP родился на эту тему. Только тормозить будет...

Автор: MuToGeN 8.9.2003, 10:11
mr.DUDA, с такой, например, вещью уже не катит...
user posted image
Т.е. если размер параметра больше 8 бит (т.е. занимает от 2 до 3 байт), то тут уже не получается...

Автор: mr.DUDA 8.9.2003, 11:07
Сорри, теперь всё работает Ok:
Код
#include <string>

typedef unsigned char byte;
typedef unsigned long ulong;

// Тестовый пример:
//
// Параметры длиной 17 бит (2 байта плюс 1 бит)
// 10001   10101010110011001   11111111111111111   00001111000011110
// HEX: {0x8d, 0x56, 0x67, 0xff, 0xfe, 0x1e, 0x1e}
// значения параметров: 87449, 131071, 7710 (HEX: 0x15599, 0x1ffff, 0x1e1e)



// чтение потока битов из буфера "buf", результат - длинное целое (ulong)
// отсчет битов - слева направо
// отсчет байтов - слева направо (buf[0] - самый левый)
// правый бит из потока прижат к правой границе результата
ulong ReadBits(int iLeftBit, int nBitCount, byte *buf)
{
   ulong result = 0;

   int iRightBit = iLeftBit + nBitCount - 1;
   int leftBitInByte = iLeftBit % 8;
   int rightBitInByte = iRightBit % 8;
   byte leftMask = 0xff>>leftBitInByte;
   byte rightMask = 0xff<<(7 - rightBitInByte);
   int iLeftByte = iLeftBit>>3;
   int iRightByte = iRightBit>>3;

   // первый и последний биты - в пределах одного байта
   if(iLeftByte == iRightByte)
   {
        result = (result | buf[iLeftByte] & leftMask & rightMask)>>(7 - rightBitInByte);
   }
   else
   {
        result = buf[iLeftByte] & leftMask;
        for(int iByte = iLeftByte+1; iByte < iRightByte; iByte++)
             result = (result<<8) | buf[iByte];
        result = (result<<(rightBitInByte+1)) | ((buf[iRightByte] & rightMask)>>(7 - rightBitInByte));
   }

   return result;
}


// чтение 4-х параметров, возвращает дин. массив параметров типа ulong
ulong *ReadParams(byte *buf)
{
   int nEachParamLength = ReadBits(0, 5, buf);
   int nBytesCnt = ((5 + nEachParamLength*3)>>3) + 1;
   ulong *params = new ulong[4];
   int iBit = 5;
   for(int iParam = 0; iParam < 4; iParam++, iBit += nEachParamLength)
        params[iParam] = ReadBits(iBit, nEachParamLength, buf);
   return params;
}


// тестовый пример
int main(int argc, char* argv[])
{
   byte buf[] = {0x8d, 0x56, 0x67, 0xff, 0xfe, 0x1e, 0x1e};
   ulong *params = ReadParams(buf);

   // ...

   delete params;
   return 0;
}

ЗЫ, ну и шрифт тут... Пришлось убрать из поста маркеры границ битов...

Автор: MuToGeN 8.9.2003, 11:24
Вот как я это сделал на PHP:
Код
function mswfLoadRect($swf,$startPosition){ // параметры: $swf - что-то типа Cшного char-буффера, работать с ним можно, как со строкой
$bitsPerParam=ord($swf[$startPosition]) >> 3; // кол-во битов на параметр
$numBits=$bitsPerParam*4+5; // общее кол-во бит
$numBytes=ceil($numBits/8); // общее кол-во байт
$rectStr=substr($swf,$startPosition,$numBytes); // выдергиваем то, что нас интересует
for($i=0;$i<$numBytes;$i++){
 $rectBinStr.=char2bin(ord($rectStr[$i])); // преобразовываем все в _строку_ вида 1010110001101110001110110011010...
}
$offset=5;
for($i=0;$i<4;$i++){
 $r[$i]=bin2signedInt(substr($rectBinStr,$offset,$bitsPerParam)); // преобразовываем "куски строки" $rectBinStr в signed int
 $offset+=$bitsPerParam;
}
return $r; // возвращаем массив с 4мя параметрами :)
}
Работает на ура. Остальные функции, которые тут использовал:
Код
// char => строка вида "10010110"
function char2bin($n){
$bin=Array(128,64,32,16,8,4,2,1);
for($i=0;$i<8;$i++){
 if($n-$bin[$i]>=0){
  $r.="1";
  $n-=$bin[$i];
 }else{
  $r.="0";
 }
}
return $r;
}
// строка вида "1001011011100110100011..." => int
function bin2int($n){
$q=1;
for($i=strlen($n)-1;$i>=0;$i--){
 if($n[$i]=="1"){
  $r+=$q;
 }
 $q*=2;
}
return $r;
}
// то же самое, только в signed int
function bin2signedInt($n){
$r=bin2int(substr($n,1));
$r*=($n[0]=="1"?-1:1);
return $r;
}

Автор: MuToGeN 8.9.2003, 11:26
mr.DUDA, огромное спасибо за помощь

Автор: mr.DUDA 8.9.2003, 11:31
Цитата
Вот как я это сделал на PHP

Хех, это напомнило мне, как я сделал деление в столбик с помощью строковых операций hehe.gif ... Там можно было получать любую точность результата (ограничиваясь только максимально допустимой длиной строки biggrin.gif)

Автор: MuToGeN 8.9.2003, 12:55
Цитата
signed int ReadBits(int iLeftBit, int nBitCount, byte *buf)
{
   signed int result = 0;

   int iRightBit = iLeftBit + nBitCount - 1;
   int leftBitInByte = iLeftBit % 8;
   int rightBitInByte = iRightBit % 8;
   byte signMask = 0x80 >> leftBitInByte;
   byte leftMask = 0xff>>leftBitInByte+1;
   byte rightMask = 0xff<<(7 - rightBitInByte);
   int iLeftByte = iLeftBit>>3;
   int iRightByte = iRightBit>>3;

   // первый и последний биты - в пределах одного байта
   if(iLeftByte == iRightByte)
   {
        result = ((buf[iLeftByte] & signMask) << leftBitInByte) | (result | buf[iLeftByte] & leftMask & rightMask)>>(7 - rightBitInByte);
   }
   else
   {
        result = buf[iLeftByte] & leftMask;
        for(int iByte = iLeftByte+1; iByte < iRightByte; iByte++)
             result = (result<<8) | buf[iByte];
        result = (result<<(rightBitInByte+1)) | ((buf[iRightByte] & rightMask)>>(7 - rightBitInByte));
   }

   return result;
}
Немного доработал функцию (добавил определение бита знака), оно там, оказывается, еще и signed smile.gif но только для ситуации, когда начало и конец - в одном байте. Для другой ситуации придумаю чуть позже. Пока делаю все это на PHP, но потом так и так придется переделывать на C++

Автор: MuToGeN 8.9.2003, 15:45
Все... дальше на PHP мучиться смысла нет... Пытаюсь более детально разобраться с алгоритмом на C++
Цитата
  if(iLeftByte == iRightByte)
  {
        result = (result | buf[iLeftByte] & leftMask & rightMask)>>(7 - rightBitInByte);
  }
Смысл этой строки, насколько я понял (mr.DUDA, пожалуйста, поправь меня, если ошибаюсь):
Есть где-то в буфере байт... Интересуют нас оттуда биты с 3 по 5 включительно, т.е. leftBitInByte = 3, rightBitInByte = 5...
Имеем:
leftMask = 00011111
rightMask = 11111100
left & right = 00011100
Пусть байт в буфере = 0xFF
Тогда result = 00011100 >> (7 - 5) = 00011100 >> 2 = 00000111

Автор: mr.DUDA 8.9.2003, 16:13
Ты всё понял правильно smile.gif

Отличия второго варианта (после else) состоят в том, что вначале в result записывается "кусок" от левого бита до края первого байта, затем идёт цикл добавления в результат "полных" байт (если таковые есть), и потом - "кусок" от края последнего байта до правого бита.

Автор: MuToGeN 8.9.2003, 16:42
Вопрос на ту же тему... Насчет бита знака... То, что написал тогда - пахать не хочет, отвык я от C++...
Для типа int - какой бит отвечает за знак? Насколько помню, самый верхний... А как грамотно его преобразовать из битовой последовательности?

Допусим, есть значения из пяти бит - 01101 - 13 в десятичной и 11101 - . Насколько понял, чтобы преобразовать его в signed int, надо "продублировать" верхний бит из пятибитовой последовательности, т.е.
01101 => 00000000 00000000 00000000 00001101
11101 => 11111111 11111111 11111111 11111101
Я прав?

Автор: mr.DUDA 8.9.2003, 19:37
Цитата
Насколько понял, чтобы преобразовать его в signed int, надо "продублировать" верхний бит из пятибитовой последовательности, т.е....

Ты прав. Вот тебе функция, преобразующая результат функции ReadParams в знаковое число, если бит знака находится в позиции iBitSign:
Код
long  MakeSigned(ulong value, int  iBitSign)
{      
      if(value & (0x80000000>>iBitSign))
            return value | ~(ulong(0xffffffff)>>iBitSign);
      else
            return value;
}

ЗЫ, отсчет битов по-прежнему идёт слева-направо.

ЗЫ(2), "int" то же самое что "long" (32-разрядное целое со знаком), но не обязательно и не на всех платформах. Я предпочёл бы юзать "long" (хотя, ты можешь делать как хочешь, или как удобнее - ничего от этого не изменится).

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)