Сдвиговые операции в кодировании, язык Си Опции

[Янычар]

Прош мне помочь вот с чем: у меня есть коды фаффмана для каждого кодируемого символа. Так вот вопрос :
могли бы мне написать функцию которая бы упаковывала отдельные коды разной длины напрмер в переменную типа unsigned(2 байта). Здесб довольно тонкая работ со сдвиговыми операциями и у меня не получается.

[klem4]

коды фаффмана

Спасибо, поржал))

Ты бы пару примеров привел, было бы яснее, а коды наверное Хаффмана.

Сообщение отредактировано: klem4 - 29.05.2008 21:42

[Янычар]

Честно говоря сам поражл щас)))) А пример попытаюсь привести щас. Ну например у меня есть символы A,B,C,D.У каждого из них в кодовом дереве Tree у них есть соответствующие коды хаффмана. В таблице символов они идут в последовательности: D, C, B, A. А коды их находятся в кодово дереве(реализованном как массив деревьев) соответсвенно: Tree[i].code. Не буду перечислять коды этих символов. Ну вот и теперь мне надо записать их в выходной файл. Я так понял что надо все эти коды сгруппировать например в двухбайтовую переменную. Будет запущен цикл в котором при совпадении в таблице символов с символом считанным из файла будет поставлен в соответсвие код из дерева. Так вт проблма состоит в том что у меня не получается записать коды символов в переменную, чтобы потом при заполнении переменной все скинуть в файл и обнулить ее и опть начать заполнение ее и т.д. до конц файла аминь... Ну типа есть коды у символа А -110 а у B - 001 , то перед тем как отправить эти коды в файл надо их загнать в переменную и выглядеть она будет так: 00110001 - я взял 8-битный пример. То есть в тексе был сначал встречен символ А а затем уже B. Фууух надеюсь понятно стало и теперь кто нить может мне помочь) Заранее спасибо...

[klem4]

то есть каждый символ кодируется 3 битами, и ты хочешь запихивать в каждый байт информацию о двух символах ? Ну сделать можно, только выходит что в за каждый байт ты будешь терять по 2 бита, так и должно быть ? А вообще глянь вот эту тему: Помогите написать архиватор для текстовых файлов на паскале

Тут я примерно тоже самое реализовал на паскале. В общем если время будет и если я правильно понял что ты хочешь сделать, попробую на С++.

Сообщение отредактировано: klem4 - 29.05.2008 22:05

[Янычар]

Ну нет конечно. Я просто пример привел. Коды все разной длины и быть их может очень много. Просто когда считывание идет из файла в переменную определнную записываются последовательности кодов и кода больше в эту переменную не запсать уже ее надо скинуть в выходной файл, обнулить и опять продолжить.

Сообщение отредактировано: Янычар - 29.05.2008 22:15

[volvo]

Что-то я не понял твоей логики... Вот тут: метод Хаффмана ты пишешь, что сам уже нашел и объяснение, и ссылки на реализации на С. Теперь выясняется, что тебе это надо сделать. Собственно, чего бы не открыть исходник (ты ж его нашел, а найти на самом деле не проблема), и не посмотреть, как это делается там? Или то, что есть ТАМ не подходит тебе? Тогда расскажи, почему, и где гарантия того, что ЗДЕСЬ ты получишь то, что тебе подойдет?

[Янычар]

Ну там и вправду не совсем то что мне нужно) А здесь я хочу лишь разобраться в частном вопросе а не в целом алгоритме .

[volvo]

Ну, тогда смотри:

#include <stdio.h>
unsigned buffer, length_in_buff;

void pack_unsigned(unsigned value, unsigned len)
{
    unsigned can_add, copy;
    can_add = 8 * sizeof(unsigned) - length_in_buff;

    if(can_add >= len) {
        buffer <<= len;
        buffer |= value;

        length_in_buff += len;

        if(can_add == len) {
            printf("output buffer: %u\n", buffer); /* store buffer */
            buffer = length_in_buff = 0;
        }
    }
    else {
        copy = value;
        value >>= len - can_add;
        buffer <<= can_add;
        buffer |= value;

        printf("output buffer: %u\n", buffer); /* store buffer */
        copy <<= sizeof(unsigned) - (len - can_add);
        copy >>= sizeof(unsigned) - (len - can_add);
        buffer = copy;
        length_in_buff = len - can_add;
    }
}


int main() {
    printf("sizeof(unsigned) = %d\n", sizeof(unsigned));
    buffer = 0; length_in_buff = 0;

    pack_unsigned(3, 9); /* 000000011 */
    pack_unsigned(3, 9); /* 000000011 */
    pack_unsigned(2, 7); /* 0000010 */
    pack_unsigned(8, 7); /* 0001000 */
    pack_unsigned(1, 5); /* 00001 */
    printf("buffer = %u (should be 1)\n", buffer);
    return 0;
}

pack_unsigned пишет в buffer первый параметр, записанный в поле из стольки бит, сколько указано во втором параметре (закомментированы как раз битовые последовательности, добавляемые к буферу)... Когда буфер заполняется, он "сбрасывается" либо в файл, либо (как у меня в программе) на экран, и все начинается сначала...

Теперь о выводе. buffer имеет размер в 32-бита, следовательно после 4-х вызовов pack_unsigned он заполнится, и будет содержать
00000001100000001100000100001000 = 25215240₁₀
00001 - то, что остается в буфере после всех операций...

Что непонятно - спрашивай...

[Янычар]

Ну в принципе все понятно спасибо, но есть один вопрос. Вот допустим когда я запишу эту битовую последовательность в файл там окажутся все биты или только биты после первой значащей единицы? А то может получиться, как мне кажется, что вместо того чтобы записать в файл 00000001100000001100000100001000 , запишется только 1100000001100000100001000 а это будет неприемлимо для меня. ?

Сообщение отредактировано: Янычар - 1.06.2008 16:59

[volvo]

Ты не можешь записывать в файл информацию побитно, какие-то биты записать, а какие-то нет... Если пишешь содержимое переменной, то оно заносится в файл полностью. Содержимое области памяти размером в 4 байта (в случае unsigned) скопируется в файл.

[Янычар]

Спасибо понятно теперь. Хотя то что писать в файл побитно нельзя я знал и поэтому и заварил эту кашу)

[Янычар]

Вот один вопрос возник а зачем нужно 00001 - то, что остается в буфере после всех операций... И куда записывается эта последовательность? после каждого заполненного блока длиной unsiged или вобще после всех операций в переменную buffer? Просто тока ас заметил что при одном моем тестовом файле в конце не совсем прально записывает коды так может это как то с этим связано?

[volvo]

а зачем нужно 00001 - то, что остается в буфере после всех операций... И куда записывается эта последовательность? после каждого заполненного блока длиной unsiged или вобще после всех операций в переменную buffer?

Это то, что после всех операций (и, соответственно, сбросов заполненного буфера) остается в буфере. Как только ты закончил с вызовами pack_unsigned, надо сбросить содержимое, оставшееся в буфере, в файл (но перед этим его надо сдвинуть влево на (8 * sizeof(unsigned) - length_in_buff) бит, иначе у тебя после уже записанного и перед оставшимся появятся лишние нулевые биты, а это никому не нужно)...

[Янычар]

Спасибо так оно и есть)

Добавлено через 17 мин.
Если можно то задам еще один вопросик) Я вот придумал тут декодер и он нормально сработал с файлом состоящим из вот такого набора символов: "aaaaaaaaaaaaaaabbbbbbbbbbcccccddd". Но как создаю вот такй файл: "hhhfdrdfoegjoegiyuiwtoujugu" почему то глючит а именно на экране пролетает многократно символ h, потом еще несколько и заканчивается ошибкой. Коды для каждого отдельного символа генерируются правильно я все проверял. Могу тут написать тот цикл который отвечает за декодировку вот он:
while(i!=0){
while(Tree[k].leaf==NULL){
if(x==-1){
j+=1;
x=31;
}
code=masbuf[j]&(mask<<x);
x--;
if(code>0){
a=Tree[k].left;
k=a;
i--;
}
if(code==0)
{
a=Tree[k].right;
k=a;
i--;
}
}
printf("%c",Tree[k].leaf);
k=IndexLast-1;
a=0;
}
здесь переменная i содержит число битов вобще, j - отвечает за текущий блок из masbuf который содержит как раз те битовые последовательности.Tree[k].left - например содержит индекс для левого поддерева.В Tree.leaf - всегда содержится NULL если тока там нету символа и таким образом проход по дереву происходит пока не найдется симво. Судя по всему все слишком сложно и поэтому вылетает ошибка на более большом файле. Так что может есть идеи как сделать это более эффек5тивно? Щас напишу что имеется в наличии: массив masbuf - типа unsigned содержит все коды то есть значения buffer до сброса; переменная n-содержит полное число битов и массив деревьев Tree и IndexLast-1 - соответствует корню дерева в моем случае это индекс массива деревьев

Сообщение отредактировано: Янычар - 4.06.2008 16:30