Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > биты в байты и обратно %)

Автор: boostcoder 26.5.2012, 23:30

всем привет!

снова мне повстречалась задача с битами smile

прошу помощи.

имеем класс, описывающий битовое множество(http://qt-project.org/doc/qt-4.8/qbitarray.html)
нужно это дело поместить в массив байт, и обратно.

я не очень-то понимаю как мне итерироваться по битам каждого байта массива.

спасибо.

Автор: boostcoder 26.5.2012, 23:48

в общем, нагуглил два решения:
http://stackoverflow.com/questions/8776261/qbitarray-to-qbytearray
http://stackoverflow.com/questions/5251403/binary-serialization-of-stdbitset

и сразу понял как реализовать задачу smile

(еще бы)))

но решение для QBitArray что-то мне кажется дико оверхедным...
у кого-то есть предложения по оптимизации?

Автор: volatile 27.5.2012, 00:15

Цитата(boostcoder @ 26.5.2012, 23:48

)

но решение для QBitArray что-то мне кажется дико оверхедным...

Если бы знать внутреннее устройство QBitArray, то вероятно было бы оптимальное решение. (возможно даже memcpy)
Но, увы мы так делать не имеем право, так что кардинально там несоптимизируешь.
Так по мелочи, конечно можно, но это не даст заметного ускорения.

А вот исправить баг, в первом линке, не помешает

Цитата

bytes.resize(bits.count()/8);

Если кол-во битов не кратно 8, то программка сильно обломится.
нужно как-то так:

Цитата

bytes.resize((bits.count() + 7)/8);

Автор: boostcoder 27.5.2012, 00:22

Цитата(volatile @ 27.5.2012, 00:15

)

А вот исправить баг, в первом линке, не помешает

о, спасибо smile

ладно, вопрос закрываю.

Автор: volatile 27.5.2012, 00:29

Кстати там ниже, это испривили, (только что посмотрел)

Цитата

bytes.resize(bits.count()/8+1);

Но все равно, мой вариант, более точный:

Цитата(volatile @ 27.5.2012, 00:15

)

bytes.resize((bits.count() + 7)/8);

Автор: mes 27.5.2012, 00:52

Цитата(boostcoder @ 26.5.2012, 22:48

)

у кого-то есть предложения по оптимизации?

написать Qt, зато что лишила доступа к внутренней прослойке smile

ведь могла б возвращать data (), как ByteArray...

Автор: boostcoder 27.5.2012, 01:04

mes, а ведь в стандартной реализации этого тоже нет: http://en.cppreference.com/w/cpp/utility/bitset

Добавлено через 2 минуты и 50 секунд
и в http://www.boost.org/doc/libs/1_49_0/libs/dynamic_bitset/dynamic_bitset.html этого тоже нет, почему-то.

Автор: mes 27.5.2012, 09:02

Цитата(boostcoder @ 27.5.2012, 00:04

)

этого тоже нет: http://en.cppreference.com/w/cpp/utility/bitset

ага, там ограничились u(l)long'ом... сам не так давно возмущался их поведением smile

Добавлено через 3 минуты и 20 секунд

Цитата(boostcoder @ 27.5.2012, 00:04

)

и в boost.dynamic_bitset этого тоже нет, почему-то.

там хоть to_block_range есть smile

Автор: boostcoder 27.5.2012, 12:19

Цитата(mes @ 27.5.2012, 09:02

)

там хоть to_block_range есть

да, точно

Цитата(mes @ 27.5.2012, 09:02

)

там ограничились u(l)long

Вы про то, что внутреннее хранилище состоит из массива long`ов?

Автор: mes 27.5.2012, 12:45

Цитата(boostcoder @ 27.5.2012, 11:19

)

Вы про то, что внутреннее хранилище состоит из массива long`ов?

про возвращение набора битов как u(l)long, размера которого увы не всегда хватает..а о массиве они почему то не подумали..

Автор: boostcoder 27.5.2012, 13:00

ааа, ну да.
но раз уж все известные мне реализации поступают так же, возможно есть на то причина?

Автор: mes 27.5.2012, 13:24

Цитата(boostcoder @ 27.5.2012, 12:00

)

но раз уж все известные мне реализации поступают так же, возможно есть на то причина?

как выяснили не все.. а причина думаю только одна, непонятка зачем при работе с битами массив байтов хранилища.. smile

Автор: boostcoder 27.5.2012, 13:27

ясно)

Автор: borisbn 27.5.2012, 13:56

у всех этих "стандартных" битсетов (что std, что boost, что Qt) есть один недостаток: они складывают биты в байте начиная с младшего.
Например, последовательность 10101100 будет равна 0x35, а многие библиотеки (да почти все) требуют, чтобы биты складывались, начиная со старшего бита. Т.о. приведённая последовательность должна быть равна 0xAC, а не 0x35.
Так что советую реализовать свой битсет (можно без блекджека))). Тем более, что это - совсем нетрудно

Автор: hawk3500 29.5.2012, 16:45

Занимаюсь ЦОС. На ПК более быстрого и прозрачного решения чем ниже описанное не нашёл.
Да не экономично по отношению к памяти , зато быстро и прозрачно.

Код


//Класс для распаковки битов
bool BIN_GO2[256][8];
int GetBitFromBuff(char buff,int n)
{
    return (buff&(1<<((n%8))))!=0;
}
clsBlock::clsBlock(void ) 
{
    // Подготовка к работе, инициализация переменных
char V;
for(int i=0;i<256;i++)
{
    V=char(i);
    BIN_GO2[i][0]=bool(GetBitFromBuff(V,0));
    BIN_GO2[i][1]=bool(GetBitFromBuff(V,1));
    BIN_GO2[i][2]=bool(GetBitFromBuff(V,2));
    BIN_GO2[i][3]=bool(GetBitFromBuff(V,3));
    BIN_GO2[i][4]=bool(GetBitFromBuff(V,4));
    BIN_GO2[i][5]=bool(GetBitFromBuff(V,5));
    BIN_GO2[i][6]=bool(GetBitFromBuff(V,6));
    BIN_GO2[i][7]=bool(GetBitFromBuff(V,7));
}
}

void clsBlock::CharToBit(unsigned char *IN_MASS,bool *OUT_MASS,int In_Mass_Lenght)
{
    int next_position=0;
    int current_byte=0;
    int tmp=0;
    int byte_size=8*sizeof(bool);
    memset(OUT_MASS,0,In_Mass_Lenght*sizeof(bool));
    while(current_byte<In_Mass_Lenght)
    {
        tmp=int(IN_MASS[current_byte]);
        memcpy(&OUT_MASS[next_position],&BIN_GO2[tmp][0],byte_size);
        next_position+=8;
        current_byte++;
    }
return;
}







//класс для упаковки

bool BIN_GO2[256][8];
char PARSE[2][2][2][2][2][2][2][2];
int GetBitFromBuff(char buff,int n)
{
    return (buff&(1<<((n%8))))!=0;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////
// Конструктор класса
clsBlock::clsBlock(void )
    // Подготовка к работе, инициализация переменных

char V;
for(int i=0;i<256;i++)
{
    V=char(i);
    BIN_GO2[i][0]=bool(GetBitFromBuff(V,0));
    BIN_GO2[i][1]=bool(GetBitFromBuff(V,1));
    BIN_GO2[i][2]=bool(GetBitFromBuff(V,2));
    BIN_GO2[i][3]=bool(GetBitFromBuff(V,3));
    BIN_GO2[i][4]=bool(GetBitFromBuff(V,4));
    BIN_GO2[i][5]=bool(GetBitFromBuff(V,5));
    BIN_GO2[i][6]=bool(GetBitFromBuff(V,6));
    BIN_GO2[i][7]=bool(GetBitFromBuff(V,7));
}

for(int j=0;j<256;j++)
{
    PARSE[!!BIN_GO2[j][0]][!!BIN_GO2[j][1]][!!BIN_GO2[j][2]][!!BIN_GO2[j][3]][!!BIN_GO2[j][4]][!!BIN_GO2[j][5]][!!BIN_GO2[j][6]][!!BIN_GO2[j][7]]=char(j);
}

}


void clsBlock::BitToChar(bool *IN_MASS,char *OUT_MASS,int In_Mass_Lenght)
{
    int OUT_POS=0;
    int loacl_lenght=In_Mass_Lenght/8;
    for(int i=0;i<loacl_lenght;i++)
    {
        OUT_MASS[i]=PARSE[!!IN_MASS[OUT_POS]][!!IN_MASS[OUT_POS+1]][!!IN_MASS[OUT_POS+2]][!!IN_MASS[OUT_POS+3]][!!IN_MASS[OUT_POS+4]][!!IN_MASS[OUT_POS+5]][!!IN_MASS[OUT_POS+6]][!!IN_MASS[OUT_POS+7]];
        OUT_POS+=8;
    }
return;    
}

Автор: borisbn 29.5.2012, 17:27

ох, не думаю, что такая адресация

Цитата(hawk3500 @ 29.5.2012, 16:45

)

char PARSE[2][2][2][2][2][2][2][2];

это

Цитата(hawk3500 @ 29.5.2012, 16:45

)

зато быстро

думаю, эффективней будет сделать один линейный массив и вычислять индекс как-нибудь так
IN_MASS[OUT_POS] * 8 + 0 + IN_MASS[OUT_POS+1] * 8 + 1 и т.д.

Автор: hawk3500 29.5.2012, 18:47

Надо попробовать и протестировать.Завтра посмотрю на скорость.
Ну вообще мне не совсем ясно почему такая многомерная выборка будет медленнее чем Ваш пример.
Надо подумать...если получится что нибудь побыстрее будет весьма хорошо.

Автор: hawk3500 30.5.2012, 12:22

Проверил несколько вариантов, в том числе и приведённый Вами вариант...но пока описанный мной выше вариант быстрей остальных...так что проблем с таким чтением из памяти я не увидел.

Автор: borisbn 30.5.2012, 13:01

hawk3500, ну... я и не утверждал категорично. Просто где-то читал, что двойная и тем более 8-ная индексация гораздо дольше линейной. В Вашем примере я вижу несколько моментов
- компилятор мог соптимизировать , убрав двойную индексацию
- Ваш пример - вообще не то, о чём я читал. Вот если бы это был указатель на указатель ( int ********PARSE; ), то тогда, возможно, моё замечание и имело бы смысл.

Я рад, тому, что Ваш вариант самый быстрый, а также тому, что его можно нахаляву взять в этой теме (я ж надеюсь у Вас не GPL, а MIT smile

)

Автор: hawk3500 1.6.2012, 12:46

Да, компилятор и вправду у меня оптимизирует.