Модераторы: Daevaorn

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Побитовые сдвиги 
:(
    Опции темы
MuToGeN
Дата 5.9.2003, 16:56 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Лесник
****


Профиль
Группа: Модератор
Сообщений: 4379
Регистрация: 15.8.2002
Где: Москва

Репутация: нет
Всего: 32
Такая ситуация... Есть "кусок фаила", в нем структура из 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


--------------------
Three pings for the token rings,
Five pings for the UNIX machines,
Hundred pings for the broken links,
One special ping to check them all
Through Simple Network Management Protocol!
PM MAIL ICQ   Вверх
mr.DUDA
Дата 5.9.2003, 17:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


3D-маньяк
****


Профиль
Группа: Экс. модератор
Сообщений: 8244
Регистрация: 27.7.2003
Где: город-герой Минск

Репутация: 25
Всего: 232
Если "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;


Это сообщение отредактировал(а) mr.DUDA - 5.9.2003, 17:58


--------------------
user posted image
PM MAIL WWW   Вверх
MuToGeN
Дата 5.9.2003, 18:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Лесник
****


Профиль
Группа: Модератор
Сообщений: 4379
Регистрация: 15.8.2002
Где: Москва

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


--------------------
Three pings for the token rings,
Five pings for the UNIX machines,
Hundred pings for the broken links,
One special ping to check them all
Through Simple Network Management Protocol!
PM MAIL ICQ   Вверх
mr.DUDA
Дата 5.9.2003, 22:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


3D-маньяк
****


Профиль
Группа: Экс. модератор
Сообщений: 8244
Регистрация: 27.7.2003
Где: город-герой Минск

Репутация: 25
Всего: 232
То есть я так понимаю, нужна функция типа "unsigned long GetBits(int istart, iend, char *buf)" confused.gif

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


--------------------
user posted image
PM MAIL WWW   Вверх
mr.DUDA
Дата 6.9.2003, 13:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


3D-маньяк
****


Профиль
Группа: Экс. модератор
Сообщений: 8244
Регистрация: 27.7.2003
Где: город-герой Минск

Репутация: 25
Всего: 232
Вот и обещанный сорц:
Код
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, но я не знаю как.


--------------------
user posted image
PM MAIL WWW   Вверх
MuToGeN
Дата 8.9.2003, 09:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Лесник
****


Профиль
Группа: Модератор
Сообщений: 4379
Регистрация: 15.8.2002
Где: Москва

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


--------------------
Three pings for the token rings,
Five pings for the UNIX machines,
Hundred pings for the broken links,
One special ping to check them all
Through Simple Network Management Protocol!
PM MAIL ICQ   Вверх
MuToGeN
Дата 8.9.2003, 10:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Лесник
****


Профиль
Группа: Модератор
Сообщений: 4379
Регистрация: 15.8.2002
Где: Москва

Репутация: нет
Всего: 32
mr.DUDA, с такой, например, вещью уже не катит...
user posted image
Т.е. если размер параметра больше 8 бит (т.е. занимает от 2 до 3 байт), то тут уже не получается...


--------------------
Three pings for the token rings,
Five pings for the UNIX machines,
Hundred pings for the broken links,
One special ping to check them all
Through Simple Network Management Protocol!
PM MAIL ICQ   Вверх
mr.DUDA
Дата 8.9.2003, 11:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


3D-маньяк
****


Профиль
Группа: Экс. модератор
Сообщений: 8244
Регистрация: 27.7.2003
Где: город-герой Минск

Репутация: 25
Всего: 232
Сорри, теперь всё работает 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;
}

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

Это сообщение отредактировал(а) mr.DUDA - 8.9.2003, 11:17


--------------------
user posted image
PM MAIL WWW   Вверх
MuToGeN
Дата 8.9.2003, 11:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Лесник
****


Профиль
Группа: Модератор
Сообщений: 4379
Регистрация: 15.8.2002
Где: Москва

Репутация: нет
Всего: 32
Вот как я это сделал на 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;
}



--------------------
Three pings for the token rings,
Five pings for the UNIX machines,
Hundred pings for the broken links,
One special ping to check them all
Through Simple Network Management Protocol!
PM MAIL ICQ   Вверх
MuToGeN
Дата 8.9.2003, 11:26 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Лесник
****


Профиль
Группа: Модератор
Сообщений: 4379
Регистрация: 15.8.2002
Где: Москва

Репутация: нет
Всего: 32
mr.DUDA, огромное спасибо за помощь


--------------------
Three pings for the token rings,
Five pings for the UNIX machines,
Hundred pings for the broken links,
One special ping to check them all
Through Simple Network Management Protocol!
PM MAIL ICQ   Вверх
mr.DUDA
  Дата 8.9.2003, 11:31 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


3D-маньяк
****


Профиль
Группа: Экс. модератор
Сообщений: 8244
Регистрация: 27.7.2003
Где: город-герой Минск

Репутация: 25
Всего: 232
Цитата
Вот как я это сделал на PHP

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


--------------------
user posted image
PM MAIL WWW   Вверх
MuToGeN
Дата 8.9.2003, 12:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Лесник
****


Профиль
Группа: Модератор
Сообщений: 4379
Регистрация: 15.8.2002
Где: Москва

Репутация: нет
Всего: 32
Цитата
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++


--------------------
Three pings for the token rings,
Five pings for the UNIX machines,
Hundred pings for the broken links,
One special ping to check them all
Through Simple Network Management Protocol!
PM MAIL ICQ   Вверх
MuToGeN
Дата 8.9.2003, 15:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Лесник
****


Профиль
Группа: Модератор
Сообщений: 4379
Регистрация: 15.8.2002
Где: Москва

Репутация: нет
Всего: 32
Все... дальше на 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


--------------------
Three pings for the token rings,
Five pings for the UNIX machines,
Hundred pings for the broken links,
One special ping to check them all
Through Simple Network Management Protocol!
PM MAIL ICQ   Вверх
mr.DUDA
Дата 8.9.2003, 16:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


3D-маньяк
****


Профиль
Группа: Экс. модератор
Сообщений: 8244
Регистрация: 27.7.2003
Где: город-герой Минск

Репутация: 25
Всего: 232
Ты всё понял правильно smile.gif

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


--------------------
user posted image
PM MAIL WWW   Вверх
MuToGeN
Дата 8.9.2003, 16:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Лесник
****


Профиль
Группа: Модератор
Сообщений: 4379
Регистрация: 15.8.2002
Где: Москва

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

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


--------------------
Three pings for the token rings,
Five pings for the UNIX machines,
Hundred pings for the broken links,
One special ping to check them all
Through Simple Network Management Protocol!
PM MAIL ICQ   Вверх
mr.DUDA
Дата 8.9.2003, 19:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


3D-маньяк
****


Профиль
Группа: Экс. модератор
Сообщений: 8244
Регистрация: 27.7.2003
Где: город-герой Минск

Репутация: 25
Всего: 232
Цитата
Насколько понял, чтобы преобразовать его в 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" (хотя, ты можешь делать как хочешь, или как удобнее - ничего от этого не изменится).

Это сообщение отредактировал(а) mr.DUDA - 8.9.2003, 20:31


--------------------
user posted image
PM MAIL WWW   Вверх
Страницы: (2) [Все] 1 2 
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0854 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.