2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 СИ. Коды Хаффмана. Дерево Хаффмана.
Сообщение07.02.2017, 20:19 


02/10/12
211
Я написал программу для вычисления кодов Хаффмана, вроде бы работает. Предназначена для deflate-сжатия. Алгоритм построения дерева Хаффмана и заготовка кода взяты из статьи, скрин в офтопе.

(Оффтоп)


Терминология: я условно листья называю листьями, а узлами называю те узлы, которые не являются листьями.
код: [ скачать ] [ спрятать ]
Используется синтаксис C
//   gcc hfm_tree.c -o hfm_tree.cgi -Wall -Werror -O3
//   ./hfm_tree.cgi



#include <stdio.h>
#include <string.h>
#include <stdlib.h>


// структура для построения дерева Хаффмана
struct s_zipc_hfm{
    int a[288];
    int b[288];
    int pl[288];
    int pr[288];
    int pp[288];
    int p[288];
    int bl_count[288];
};

// структура кодов Хаффмана
struct s_zipc_sym {
    int   freq; // частота символа
    int   hcod; // код Хаффмана
    int   bits; // длина кода Хаффмана
};


//-------------- zipc_haffman_code --------------------
// расчет кодов Хаффмана
int zipc_haffman_code(struct s_zipc_hfm *tree, struct s_zipc_sym *sym,
                      int Max_sym, int Max_bits)
{
    int i, j, k, k1, k2, n, t1, t2, fl, cod, bits, len, aa, ab, bb;
    int *a  = tree->a;  // частоты листьев отсортированы по нарастанию
    int *b  = tree->b;  // частоты узлов
    int *pl = tree->pl; // левый потомок узла
    int *pr = tree->pr; // правый потомок узла
    int *pp = tree->pp; // родительский узел
    int *p  = tree->p;  // номер символа, его значение
    int *bl_count = tree->bl_count; // счетчики числа кодов для разных длин
    int next_code[20];  // счетчики значений кодов для разных длин (из deflate)

    // зарядка исходных массивов
    memset(tree, 0, sizeof(struct s_zipc_hfm));
    for(i = 0, n=0; i < Max_sym; i++){
        if(sym[i].freq > 0){
            a[n] = sym[i].freq;
            p[n] = i;
            n++;
        }
    }
    if(n==0) return(0); // n -число используемых символов алфавита
    if(n > (1 << Max_bits)) return(-1);
    if(n==1){ bl_count[1]++; goto RET;}

    // сортировка по возрастанию частоты символов
    for(i=0; i<n; i++){
        for(j=n-1; j>i; j--){
            if(a[j] < a[j-1]){
                t1     = a[j];      t2     = p[j];
                a[j]   = a[j-1];    p[j]   = p[j-1];
                a[j-1] = t1;        p[j-1] = t2;
            }
        }
    }

    // создание дерева
    // aa, ab, bb -суммы частот двух текущих узлов или листьев
    // k -индекс вновь создаваемого узла
    // i -индекс текущего листа
    // j -индекс текущего узла
    for(k=0, i=0, j=0; k<(n-1); k++){
        if(i<(n-1))    aa = a[i] + a[i+1]; else aa = 1000000;
        if(i<n && j<k) ab = a[i] + b[j];   else ab = 1000000;
        if(j<(k-1))    bb = b[j] + b[j+1]; else bb = 1000000;

        if(aa <= ab && aa <= bb){
            b[k] = aa;
            pl[k] = pr[k] = -1; // оба потомка листья, -1 -признак листа
            i += 2;
        }
        else if(ab <= aa && ab <= bb){
            b[k] = ab;
            pl[k] = j;  // левый потомок
            pr[k] = -1; // правый потомок это лист, -1 -признак листа
            pp[j] = k;  // родительский узел в левом потомке
            i++;
            j++;
        }
        else{
            b[k] = bb;
            pl[k] = j;   // левый потомок
            pr[k] = j+1; // правый потомок
            pp[j] = pp[j+1] = k; // родительский узел в потомках
            j += 2;
        }
    }

    // обход дерева
    for(k--, len=0, fl=0, i=0; i<(2*n); i++){ // k -индекс корневого узла
        if(fl==0){ // вниз по дереву
            len++;
            k1 = pl[k]; k2 = pr[k];
            if(k2<0) bl_count[len]++;
            if(k1<0){ bl_count[len]++; fl=1;} // если слева лист, то вверх
            else k=k1; // в левую ветвь.
        }
        if(fl==1){ // вверх по дереву
            len--;
            if(len<=0) break;
            k = k1 = pp[k];  // k, k1 -индекс родителя
            if(pr[k1] >= 0){ // если правая ветвь не пройдена, то туда
                k = pr[k1];  // k -индекс правой ветви родителя
                pr[k1] = -1; // отмечаем правую ветвь как пройденную
                fl=0;
            }
        }
    }

    // уменьшение длин кодов
    for(i=n-1; i>Max_bits; i--){
        for(; bl_count[i]>0;){
            for(j=i-2; j>0 && bl_count[j]<=0; j--);
            bl_count[i] -= 2;
            bl_count[i-1]++;
            bl_count[j]--;
            bl_count[j+1] += 2;
        }
    }

RET:

    // зарядка выходного массива
    for(cod=0, i=n-1, bits=1; bits <= Max_bits; bits++){
        if(bl_count[bits] > 0){
            for(j=0; j < bl_count[bits]; j++){
                sym[p[i--]].bits = bits;
            }
        }
    }

    for(bits = 1; bits <= Max_bits; bits++){
        cod = (cod + bl_count[bits-1]) << 1;
        next_code[bits] = cod;
    }
    for(i = 0;  i < Max_sym; i++){
        len = sym[i].bits;
        if(len != 0){
            sym[i].hcod = next_code[len];
            next_code[len]++;
        }
    }
    return(n);
}




//============= Тестовая обертка ==================


// Запустить программу. Для выбора одного из тестовых массивов частот, которые
// есть в функции main (по умолчанию - первый массив), ввести:
// --> arr 2  (или другой номер массива от 1 до 6)
// Для изменения частот символов и для введения новых символов ввести:
// --> A 510  (A -это старый или вновь введенный символ, 510 -его частота)
// Для изменения максимальной длины кодов (по умолчанию 15) ввести:
// --> max 4  (4 -максимальная длина кодов)
// Для запуска вычисления кодов ввести пустую строку.
// Настройки arr и max держатся до явной их смены. Введённые символы и частоты
// держатся до смены массива.

//-------------- print_bits ----------------
// Распечатать число в двоичном виде. len -длина(бит).
int print_bits(int val, int len)
{
    int i, maska = 1 << (len - 1);
    if((val >> len) != 0) printf("Error: val=%d; len=%d; ", val, len);
    for(i=0; i<len; i++){
        if((val & maska) != 0) printf("1");
        else printf("0");
        maska = maska >> 1;
    }
    return(0);
}

//---------------- main -----------------------
//printf("\n");
int main()
{

    int x1[]={
        'A', 900,
        'B', 370,
        'C', 350,
        'D', 79,
        'E', 57,
        'F', 54,
        'G', 9,
        'H', 7,
        'I', 1,
    };

    int x2[]={
        'A', 900,
        'B', 370,
        'C', 350,
        'D', 350,
        'E', 350,
        'F', 350,
        'G', 350,
        'H', 350,
        'I', 350,
        'J', 350,
        'K', 350,
        'L', 350,
        'M', 1,
    };

    int x3[]={
        'A', 5200,
        'B', 1100,
        'C', 1000,
        'D', 900,
        'E', 800,
        'F', 700,
        'G', 600,
        'H', 500,
        'I', 400,
        'J', 300,
        'K', 200,
        'L', 100,
        'M', 1,
        'N', 1,
        'O', 1,
        'P', 1,
    };

    int x4[]={
        'A', 5200,
    };

    int x5[]={
        'A',  500,
        'B', 1200,
        'C',   34,
        'D',  800,
        'E',   67,
        'F', 1009,
        'G',  654,
    };

    int x6[]={
        'A',  5,
        'B',  4,
        'C',  3,
        'D',  2,
        'E',  1,
    };

    char *ptr, buf[100];
    unsigned char ch;
    int i, k, fr, len, S, S0, arrnum, Nsym;
    struct s_zipc_hfm tree[1];
    struct s_zipc_sym sym[286];
    int Max_sym = 286;
    int Max_bits = 15;
    int a1[2*286];

    Nsym = (sizeof(sym)/sizeof(struct s_zipc_sym)); // число элементов sym

    memset(sym, 0, sizeof(sym));
    for(k=0; k<(int)(sizeof(x1)/(sizeof(x1[0]))); k=k+2){
        sym[x1[k]].freq = x1[k+1];
    }

START:

    // ввод данных
    printf("-----------------\n");
    while(1){
        printf("--> "); fflush(stdout);
        ptr = fgets(buf, sizeof(buf), stdin);
        if(ptr==NULL) exit(0);
        k = strlen(buf);
        if(k>0 && buf[k-1]=='\n') buf[--k]=0;
        if(k==0) break;
        if(strncmp(buf, "max", 3)==0){
            Max_bits = atoi(buf+3);
            printf("Max_bits=%d\n", Max_bits);
        }
        else if(strncmp(buf, "arr", 3)==0){
            arrnum = atoi(buf+3);
            printf("arrnum=%d\n", arrnum);
            memset(a1, 0, sizeof(a1));
            if(arrnum == 1) memmove(a1, x1, sizeof(x1));
            else if(arrnum == 2) memmove(a1, x2, sizeof(x2));
            else if(arrnum == 3) memmove(a1, x3, sizeof(x3));
            else if(arrnum == 4) memmove(a1, x4, sizeof(x4));
            else if(arrnum == 5) memmove(a1, x5, sizeof(x5));
            else if(arrnum == 6) memmove(a1, x6, sizeof(x6));
            else{ printf("Error\n"); continue;}
            memset(sym, 0, sizeof(sym));
            for(k=0; k<(int)(sizeof(a1)/(sizeof(a1[0]))); k=k+2){
                sym[a1[k]].freq = a1[k+1];
            }
        }
        else{
            k=sscanf(buf, "%c %d", &ch, &fr);
            if(k!=2){ printf("Error\n"); continue;}
            sym[(int)ch].freq = fr;
        }
    }

    for(i=0; i<Nsym; i++){ //обнулить
        sym[i].bits = 0;
        sym[i].hcod = 0;
    }

    k = zipc_haffman_code(tree, sym, Max_sym, Max_bits); // рассчет кодов
    printf("k = zipc_haffman_code()=%d\n", k);

    // распечатка кодов Хаффмана
    S=0; S0=0; len=0;
    for(i=0, k=1; i<Max_sym; i++){
        if(sym[i].freq > 0){
            printf("%2d. %c  len=%2d  freq=%5d  ",
                   k++, i, sym[i].bits, sym[i].freq);
            print_bits(sym[i].hcod, sym[i].bits);
            printf("\n");
            if(len < sym[i].bits) len = sym[i].bits;
            S = S + (sym[i].bits * sym[i].freq);
            S0 = S0 + 8 * sym[i].freq;
        }
    }
    printf("S =%d\n", S);
    printf("S0=%d\n", S0);
    printf("L =%0.3f  bit/symbol; max_len=%d\n", 8.0 * S / S0, len);

    goto START;
}
 

Рассмотрим блок "создание дерева" на конкретном примере (n -число используемых символов алфавита).
код: [ скачать ] [ спрятать ]
Используется синтаксис C
    // int a[] -содержит частоты символов, отсортированные по возрастанию
    // int b[] -сюда заносятся частоты узлов
    // pl[] -левый потомок.
    // pr[] -правый потомок.
    // pp[] -родительский узел.

    // создание дерева
    // aa, ab, bb -суммы частот двух текущих узлов или листьев
    // k -индекс вновь создаваемого узла
    // i -индекс текущего листа
    // j -индекс текущего узла
    for(k=0, i=0, j=0; k<(n-1); k++){
        if(i<(n-1))    aa = a[i] + a[i+1]; else aa = 1000000;
        if(i<n && j<k) ab = a[i] + b[j];   else ab = 1000000;
        if(j<(k-1))    bb = b[j] + b[j+1]; else bb = 1000000;

        if(aa <= ab && aa <= bb){
            b[k] = aa;
            pl[k] = pr[k] = -1; // оба потомка листья, -1 -признак листа
            i += 2;
        }
        else if(ab <= aa && ab <= bb){
            b[k] = ab;
            pl[k] = j;  // левый потомок
            pr[k] = -1; // правый потомок это лист, -1 -признак листа
            pp[j] = k;  // родительский узел в левом потомке
            i++;
            j++;
        }
        else{
            b[k] = bb;
            pl[k] = j;   // левый потомок
            pr[k] = j+1; // правый потомок
            pp[j] = pp[j+1] = k; // родительский узел в потомках
            j += 2;
        }
    }

 

Пусть используются пять символов с частотами 1, 2, 3, 4, 5. В массиве a эти частоты отсортированы по возрастанию, на рисунке этот массив синий. В массив b заносятся частоты узлов, на рисунке он оранжевый.
Изображение
В блоке "создание дерева" есть три больших if-а, можно заметить, что возможны следующие комбинации узлов и листьев (узлы оранжевые, листья синие):
Изображение
Листья не имеют индексов: где потомок узла это лист, там индекс потомка отмечен как минус единица. Получившееся дерево есть ниже на рисунке.

Рассмотрим блок "обход дерева". Задача этого блока - заполнить массив bl_count[len], в нем каждый элемент должен содержать число кодов длины len.
код: [ скачать ] [ спрятать ]
Используется синтаксис C
    // обход дерева
    for(k--, len=0, fl=0, i=0; i<(2*n); i++){ // k -индекс корневого узла
        if(fl==0){ // вниз по дереву
            len++;
            k1 = pl[k]; k2 = pr[k];
            if(k2<0) bl_count[len]++;
            if(k1<0){ bl_count[len]++; fl=1;} // если слева лист, то вверх
            else k=k1; // в левую ветвь.
        }
        if(fl==1){ // вверх по дереву
            len--;
            if(len<=0) break;
            k = k1 = pp[k];  // k, k1 -индекс родителя
            if(pr[k1] >= 0){ // если правая ветвь не пройдена, то туда
                k = pr[k1];  // k -индекс правой ветви родителя
                pr[k1] = -1; // отмечаем правую ветвь как пройденную
                fl=0;
            }
        }
    }

k -индекс текущего узла.
len -текущая длина кодов.
pl[k] -левый потомок.
pr[k] -правый потомок.
pp[k] -родительский узел.
Рассмотрим на конкретном дереве из примера выше. В узлах дерева на рисунке указаны индексы этих узлов в массиве b и в сопряженных массивах pl, pr, pp. Если на текущем шаге лист посчитан счетчиком bl_count[len], то на рисунке цвет его меняется с синего на голубой. Красные стрелки показывают пройденный путь от узла к узлу. Красными кружками отмечены if-ы, выполняющиеся на текущем шаге.
Изображение
Можно сказать, что блок (fl==0) всегда идет вниз по дереву нехожеными тропами, попутно считая встретившиеся листья. Блок (fl==1) наоборот, идет хожеными тропами, за исключением случая перехода на соседнего потомка (как на шаге-5).

Рассмотрим блок "уменьшение длин кодов". На рисунке показан один шаг модификации дерева, листья, подлежащие переносу, выделены яркими цветами
Изображение
Используется синтаксис C
    // уменьшение длин кодов
    for(i=n-1; i>Max_bits; i--){
        for(; bl_count[i]>0;){
            for(j=i-2; j>0 && bl_count[j]<=0; j--);
            bl_count[i] -= 2;
            bl_count[i-1]++;
            bl_count[j]--;
            bl_count[j+1] += 2;
        }
    }

Внешний цикл выискивает коды, вылезшие за максимально-допустимую длину. Вернее, не сами коды, а счетчики числа кодов больших длин. Вложенный цикл крутится до обнуления счетчика этой большой длины. Самый глубоко вложенный маленький цикл выискивает, куда бы приткнуть лишние листья. bl_count[i] это счетчики, но за ними всегда подразумеваются листья.

До метки RET: счетчики отвязаны от символов алфавита и кодов. Обратная привязка ниже метки RET:, там в первом цикле длины привязываются к символам в порядке частот этих символов, а два нижних цикла окончательно присваивают символам их коды Хаффмана по правилу, прямо записанному в протоколе deflate.

 Профиль  
                  
 
 Re: СИ. Коды Хаффмана. Дерево Хаффмана.
Сообщение07.02.2017, 21:32 
Заслуженный участник


08/04/08
8459

(Оффтоп)

О! Я когда-то тоже так писал: и -1 и 1000000 и никаких сишных извращений. Приятно вспомнить :-) Хотя тут извращения имеются.

А в чем вопрос-то?

 Профиль  
                  
 
 Re: СИ. Коды Хаффмана. Дерево Хаффмана.
Сообщение07.02.2017, 21:36 


04/02/17

47
Sonic86 в сообщении #1190584 писал(а):

(Оффтоп)

О! Я когда-то тоже так писал: и -1 и 1000000 и никаких сишных извращений. Приятно вспомнить :-) Хотя тут извращения имеются.

А в чем вопрос-то?


Проблема в создании программы.

 Профиль  
                  
 
 Re: СИ. Коды Хаффмана. Дерево Хаффмана.
Сообщение07.02.2017, 22:54 


02/10/12
211
Sonic86 в сообщении #1190584 писал(а):
А в чем вопрос-то?

Первый вопрос, можно ли это сделать проще? Декодировать коды Хаффмана намного проще. В статье приведен код, и сразу получается число бит для кодирования всего сообщения. Можно ли вычислить сразу коды или их длины без обхода дерева? В статье об этом не написано. Обход я сам придумал.
Второй вопрос. Если проще нельзя, если обход дерева неизбежен, то вопрос. Цикл обхода выглядит непривычно, в нем в явном виде нет ни проверки на выход за края массива, ни устойчивости на зацикливание. Счетчик я на всякий случай поставил, но по замыслу его там не должно быть. Работа этого цикла без сбоев по замыслу должна быть за счет правильного дерева, и чтоб написано без ошибок. В общем, я боюсь этого цикла, непривычно. Поэтому по шагам расписал, а страх-то остался. Я написал большую программу сжатия (32 кб СИ-кода), аналог gzip, там применил эту функцию вычисления кодов, протестил на трёх файлах - видео, bmp-рисунок и текстовой файл. Работает. Короче, и уверенности нет, и не удалось получить сбой. Сбой это падение, порча памяти, как-нибудь проявившаяся, или зацикливание.
Если укажете имеющиеся извращения, тоже бы хорошо. Может не сразу, но всё равно на пользу пойдёт.

 Профиль  
                  
 
 Re: СИ. Коды Хаффмана. Дерево Хаффмана.
Сообщение12.02.2017, 07:46 


02/10/12
211
Сразу не догадался. Можно и по-другому сделать обход дерева - от каждого листа к корню с подсчётом длины кода этого листа. Блок "обход дерева" получается компактней и понятней. Ниже функция, введен дополнительный массив pa -родители листьев. А массивы потомков pl, pr не нужны, т. к. обход только вверх, от листа к корню.
код: [ скачать ] [ спрятать ]
Используется синтаксис C
// структура для построения дерева Хаффмана
struct s_zipc_hfm{
    int a[288];
    int b[288];
    int pa[288];
    int pp[288];
    int p[288];
    int bl_count[288];
};

// структура кодов Хаффмана
struct s_zipc_sym {
    int   freq; // частота символа
    int   hcod; // код Хаффмана
    int   bits; // длина кода Хаффмана
};


//-------------- zipc_haffman_code --------------------
// рассчет кодов Хаффмана
int zipc_haffman_code(struct s_zipc_hfm *tree, struct s_zipc_sym *sym,
                      int Max_sym, int Max_bits)
{
    int i, j, k, n, t1, t2, cod, bits, len, aa, ab, bb;
    int *a  = tree->a;  // частоты листьев отсортированы по нарастанию
    int *b  = tree->b;  // частоты узлов
    int *pa = tree->pa; // родительский узел листа
    int *pp = tree->pp; // родительский узел узла
    int *p  = tree->p;  // номер символа, его значение
    int *bl_count = tree->bl_count; // счетчики числа кодов для разных длин
    int next_code[20];  // счетчики значений кодов для разных длин (из deflate)

    // зарядка исходных массивов
    memset(tree, 0, sizeof(struct s_zipc_hfm));
    for(i = 0, n=0; i < Max_sym; i++){
        if(sym[i].freq > 0){
            a[n] = sym[i].freq;
            p[n] = i;
            n++;
        }
    }
    if(n==0) return(0); // n -число используемых символов алфавита
    if(n > (1 << Max_bits)) return(-1);
    if(n==1){ bl_count[1]++; goto RET;}

    // сортировка по возрастанию частоты символов
    for(i=0; i<n; i++){
        for(j=n-1; j>i; j--){
            if(a[j] < a[j-1]){
                t1     = a[j];      t2     = p[j];
                a[j]   = a[j-1];    p[j]   = p[j-1];
                a[j-1] = t1;        p[j-1] = t2;
            }
        }
    }

    // создание дерева
    // aa, ab, bb -суммы частот двух текущих узлов или листьев
    // k -индекс вновь создаваемого узла
    // i -индекс текущего листа
    // j -индекс текущего узла
    for(k=0, i=0, j=0; k<(n-1); k++){
        if(i<(n-1))    aa = a[i] + a[i+1]; else aa = 1000000;
        if(i<n && j<k) ab = a[i] + b[j];   else ab = 1000000;
        if(j<(k-1))    bb = b[j] + b[j+1]; else bb = 1000000;

        if(aa <= ab && aa <= bb){
            b[k] = aa;
            pa[i] = pa[i+1] = k; // родительский узел
            i += 2;
        }
        else if(ab <= aa && ab <= bb){
            b[k] = ab;
            pa[i] = pp[j] = k; // родительский узел
            i++;
            j++;
        }
        else{
            b[k] = bb;
            pp[j] = pp[j+1] = k; // родительский узел
            j += 2;
        }
    }

    // обход дерева
    for(--k, i=0; i<n; i++){ // k -индекс корневого узла
        for(len=1, j=pa[i]; j<k; j=pp[j], len++);
        bl_count[len]++;
    }

    // уменьшение длин кодов
    for(i=n-1; i>Max_bits; i--){
        for(; bl_count[i]>0;){
            for(j=i-2; j>0 && bl_count[j]<=0; j--);
            bl_count[i] -= 2;
            bl_count[i-1]++;
            bl_count[j]--;
            bl_count[j+1] += 2;
        }
    }

RET:

    // зарядка выходного массива
    for(cod=0, i=n-1, bits=1; bits<(Max_bits+1); bits++){
        for(j=0; j < bl_count[bits]; j++){
            sym[p[i--]].bits = bits;
        }
    }

    for(bits = 1; bits <= Max_bits; bits++){
        cod = (cod + bl_count[bits-1]) << 1;
        next_code[bits] = cod;
    }
    for(i = 0;  i < Max_sym; i++){
        len = sym[i].bits;
        if(len != 0){
            sym[i].hcod = next_code[len]++;
        }
    }
    return(n);
}
 

 Профиль  
                  
 
 Re: СИ. Коды Хаффмана. Дерево Хаффмана.
Сообщение11.04.2018, 15:20 


02/10/12
211
Я написал программу оптимизации кодов Хаффмана в базовых (baseline) JPEG-файлах (ссылка внизу). В программе применена функция отимизации кодов, приведенная в предыдущем сообщении, с небольшими изменениями. Программа пробная, я предполагал встроить оптимизацию в JPEG-кодер, который я написал ранее без оптимизации, но сжатие невелико, и польза оптимизации неочевидна. А с другой стороны, многие файлы, которые брал в интернете, оптимизированы.

В офтопе о JPEG-файле.

(Оффтоп)

JPEG-файл состоит из сегментов. Каждый сегмент начинается с маркера - комбинация двух байт, первый 0xFF, второй отличен от 0x00 и 0xFF и обозначает назначение сегмента. За маркером идут два байта - длина сегмента. Нас интересует сегмент "скан" - это блок сжатых данных рисунка.
Код:
Формат скана:
|маркер |  len  |заголовок|      скан      |
|FF |DA |   |   |.........|................|
        |<------ len ---->|
Краткое описание кодирования.
Квадратики пикселей 8х8 заменяются матрицами 8х8, содержащими частотные коэффициенты - целые числа. Скан состоит из пар: код Хаффмана плюс экстра-биты. Код Хаффмана (декодированный) - это байт, его старший и младший полубайты (HB, LB) имеют такое значение:
HB -столько коэффициентов матрицы оставить нулевыми.
LB -столько экстра-битов надо прочитать, они дают значение коээфициента матрицы.
Например, код (декодированный) равен 0x34, - оставить три коэффициента нулевыми, прочитать четыре экстра-бита и присвоить это значение следующему коэффициенту. Пусть прочитаны экстра-биты |1|0|0|1|=9, тогда получится такой кусочек матрицы: |0|0|0|9|.
Код:
Схема:
|--кусочек входа-|     |-------|<--кусочек матрицы
|код 0x34|1|0|0|1| ==> |0|0|0|9|
Из таких кусочков набирается вся матрица 8x8. Особое значение имеют коды (декодированные):
0xF0 -оставить 16 коэффициентов нулевыми, экстра-битов нет, перейти к следующей паре.
0x00 -оставить все оставшиеся коэффициенты матрицы нулевыми, перейти к следующей матрице.

Биты входного потока сгруппированы в байты. Байты 0xFF имеют особое значение, если при кодировании получается байт 0xFF, то в поток вставляется комбинация двух байт 0xFF00, такая комбинация читается как один байт 0xFF.
Коды Хаффмана для JPEG не могут состоять из одних только единичных битов, последовательность единичных битов может быть только префиксом. Максимальная длина кодов Хаффмана 16 бит.
Программа частично декодирует JPEG-файл. При первом проходе подсчитывает частоты кодов, оптимизирует коды, а при втором проходе заменяет таблицы Хаффмана и коды на новые, оптимизированные. JPEG это сжатие с потерями, но все потери уже есть в исходном файле, новых потерь при оптимизации нет.
Для наглядности привожу фрагмент программы - функцию взятия пары: код Хаффмана и значение коэффициента
код: [ скачать ] [ спрятать ]
Используется синтаксис C
//--- таблицы Хаффмана (кодирование) ---
// вынесены в отдельную структуру, чтоб не обнулялись
// на второй проход.

// структура кодов Хаффмана
struct s_fjp_sym {
    unsigned int   freq; // частота символа
    int   hcod; // код Хаффмана
    int   bits; // длина кода Хаффмана
};

// обобщенная структура для кодирования Хаффмана
struct s_fjp1 {
      ....
    struct {
        struct s_fjp_sym sym[256];
        int n;
        char buf[16+256]; // таблицы для файла JPEG
    } fsym[8];
};

//--- обобщенная структура ---
struct s_fjp {
      ....
    struct s_fjp1  *s1; // структура вынесена, чтоб не обнулялась вместе с этой
    int fl;             // 0 -первый проход; 1 -второй
}

// fjp_get_h_cod()  -взять код Хаффмана. id -номер таблцы Хаффмана
// fjp_get_n_bits() -взять n бит
// fjp_put_bits()   -положить в выходной поток bits бит.

//--------------- fjp_get_cod --------------------
// взять код Хаффмана и значение коэффициента
int fjp_get_cod(struct s_fjp *s, int id)
{
    int hcod, bits, k;
    struct s_fjp_sym  *sym = s->s1->fsym[id].sym;

    hcod = k = fjp_get_h_cod(s, id);
    if(k < 0) return(-1);
    if(s->fl > 0){
        if(fjp_put_bits(sym[k].hcod, sym[k].bits, s) < 0) return(-1);
    }
    else sym[k].freq++;
    bits = k & 15;
    if(bits==0) return(hcod);
    k = fjp_get_n_bits(s, bits);
    if(k < 0) return(-1);
    if(s->fl > 0){
        if(fjp_put_bits(k, bits, s) < 0) return(-1);
    }
    return(hcod);
}
Пример распечатки с пояснениями. Картинка http://komotoz.ru/photo/porody_koshek/p ... ata_03.jpg
со страницы http://komotoz.ru/photo/porody_koshek/p ... _porod.php
код: [ скачать ] [ спрятать ]
Используется синтаксис C
-------------
mark=0xD8  // встретившиеся маркеры, первый проход
mark=0xE0
mark=0xFE
mark=0xDB
mark=0xDB
mark=0xC0
mark=0xC4
mark=0xC4
mark=0xC4
mark=0xC4
mark=0xDA
mark=0xD9
-----maxlen=17; AC[0] // длина кодов до уменьшения, AC-таблица и её номер
----------            // AC -переменная составляющая, DC -постоянная
mark=0xD8  // встретившиеся маркеры, второй проход
mark=0xE0
mark=0xFE
mark=0xDB
mark=0xDB
mark=0xC0
mark=0xC4
T4: dl1= 29; dl2= 26; n1= 12; n2=  9; DC[0] // таблицы Хаффмана:
mark=0xC4                                   // dl1   -длина во входном файле
T4: dl1=179; dl2= 65; n1=162; n2= 48; AC[0] // dl2   -длина в выходном файле
mark=0xC4                                   // n1    -число кодов во входном
T4: dl1= 29; dl2= 24; n1= 12; n2=  7; DC[1] // n2    -число кодов в выходном
mark=0xC4                                   // DC[0] -DC-таблица и её номер
T4: dl1=179; dl2= 41; n1=162; n2= 24; AC[1] // AC[0] -AC-таблица и её номер
mark=0xDA
mark=0xD9
-------------
dl2 = fjp_opt_hfm()=91011; err=0;
w=1280; h=1003
t=0.043 sec
dl1=94613     // длина входного файла
dl2=91011     // длина выходного файла
n1_FF=85      // число встретившихся в скане байт 0xFF во входном.
n2_FF=260     // тоже в выходном (они заменяются двумя байтами 0xFF00).
delta_FF=-175 // выигрыш от меньшего числа байт 0xFF (тут проигрыш)
d1_DA=93927   // чистая длина скана во входном файле (без заголовка)
d2_DA=90585   // чистая длина скана в выходном файле (без заголовка)
delta_DA=3342 // выигрыш от сжатия скана
delta_C4=260  // выигрыш от меньших таблиц Хаффмана
delta_dl=3602 // общий выигрыш длины файла
Compress=96.19 %
-------------
Этот файл не оптимизирован, признаком является n1 больше n2, в неоптимизированных файлах таблицы содержат все символы, а в оптимизированных - только используемые.

Функция оптимизации. Отличается от прежней подставным символом a[0] с частотой 1. Этот подставной получает код, состоящий только из единичных битов (такие коды в JPEG недопустимы). В блоке "зарядка выходного массива" он удаляется. Блок "зарядка выходного массива" тоже отличается, т. к. в JPEG другое правило: в deflate в группе кодов одной длины большему лексическому значению символа должен соответствовать больший код Хаффмана, а в JPEG этого не требуется, но требуется список символов в порядке возрастания их кодов Хаффмана.
код: [ скачать ] [ спрятать ]
Используется синтаксис C
//   gcc jpc_hfm.c -o jpc_hfm.cgi -Wall -Werror -O3
//   ./jpc_hfm.cgi


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>


int fl=0;
int Maxlen=0;

//--- таблицы Хаффмана (кодирование) ---

// структура для построения дерева Хаффмана
struct s_fjp_tree {
    unsigned int a[257];
    unsigned int b[257];
    int pa[257];
    int pp[257];
    int p[257];
    int bl_count[257];
};

// структура кодов Хаффмана
struct s_fjp_sym {
    unsigned int   freq; // частота символа
    int   hcod; // код Хаффмана
    int   bits; // длина кода Хаффмана
};

// обобщенная структура для кодирования Хаффмана
struct s_fjp1 {
    struct s_fjp_tree  tree[1];

    struct {
        struct s_fjp_sym sym[256];
        int n;
        char buf[16+256]; // таблицы для файла JPEG
    } fsym[8];
};



//-------------- fjp_hfm_code --------------------
// расчет кодов Хаффмана
// buf -сюда заряжает таблицу кодов для файла JPEG
int fjp_hfm_code(struct s_fjp_tree *tree, struct s_fjp_sym *sym, char *buf)
{
    int i, j, k, n, cod, bits, len;
    unsigned int t, aa, ab, bb;
    unsigned int *a  = tree->a;  // частоты листьев
    unsigned int *b  = tree->b;  // частоты узлов
    int *pa = tree->pa; // родительский узел листа
    int *pp = tree->pp; // родительский узел узла
    int *p  = tree->p;  // номер символа, его значение
    int *bl_count = tree->bl_count; // счетчики числа кодов для разных длин

    // зарядка исходных массивов (a[0] -подставной символ)
    memset(tree, 0, sizeof(struct s_fjp_tree));
    for(a[0]=1, i=0, n=1; i < 256; i++){
        if(sym[i].freq > 0){
            a[n]   = sym[i].freq;
            p[n++] = i;
        }
    }
    memset(buf, 0, 16+n-1);
    if(n==1) return(0); // n -число используемых символов алфавита + 1
    if(n==2){ bl_count[1] += 2; goto RET;}

    // сортировка по возрастанию частоты символов
    for(i=1; i<n; i++){
        for(j=n-1; j>i; j--){
            if(a[j] < a[j-1]){
                t = a[j]; a[j] = a[j-1]; a[j-1] = t;
                t = p[j]; p[j] = p[j-1]; p[j-1] = t;
            }
        }
    }

    // создание дерева
    for(k=0, i=0, j=0; k<(n-1); k++){
        if(i<(n-1))    aa = a[i] + a[i+1]; else aa = UINT_MAX;
        if(i<n && j<k) ab = a[i] + b[j];   else ab = UINT_MAX;
        if(j<(k-1))    bb = b[j] + b[j+1]; else bb = UINT_MAX;

        if(aa <= ab && aa <= bb){
            b[k] = aa;
            pa[i++] = k; pa[i++] = k; // родительский узел
        }
        else if(ab <= aa && ab <= bb){
            b[k] = ab;
            pa[i++] = k; pp[j++] = k; // родительский узел
        }
        else{
            b[k] = bb;
            pp[j++] = k; pp[j++] = k; // родительский узел
        }
    }

    // обход дерева
    for(--k, i=0; i<n; i++){ // k -индекс корневого узла
        for(len=1, j=pa[i]; j<k; j=pp[j], len++);
        bl_count[len]++;
    }

    // уменьшение длин кодов
    for(i=n-1; i>16; i--){
        for(; bl_count[i]>0;){

            if(fl==0){
                fl=1;
                Maxlen = i; //---------------------------отладочная-----
            }

            for(j=i-2; j>0 && bl_count[j]<=0; j--);
            bl_count[i] -= 2;
            bl_count[i-1]++;
            bl_count[j]--;
            bl_count[j+1] += 2;
        }
    }

RET:

    // зарядка выходного массива
    for(k=16; k>0 && bl_count[k]==0; k--);
    bl_count[k]--; // удаление подставного символа
    for(i=1; i<=16; i++) *buf++ = bl_count[i];
    for(cod=0, i=n-1, bits=1; bits <= k; bits++){
        for(j=0; j < bl_count[bits]; j++){
            *buf++ = t = p[i--];
            sym[t].bits = bits;
            sym[t].hcod = cod++;
        }
        cod = cod << 1;
    }
    return(n-1);
}


//============= Тестовая обертка ==================


// Запустить программу. Для выбора одного из тестовых массивов частот, которые
// есть в функции main (по умолчанию - первый массив), ввести:
// --> arr 2  (или другой номер массива от 1 до 4)
// Для изменения частот символов и для введения новых символов ввести:
// --> A 510  (A -это старый или вновь введенный символ, 510 -его частота)
// Для запуска вычисления кодов ввести пустую строку.
// Настройки arr и max держатся до явной их смены. Введённые символы и частоты
// держатся до смены массива.
// В распечатке внизу есть распечатка буфера buf, это таблица Хаффмана в том
// виде, как это нужно для JPEG-файла. Верхняя строка таблицы 16 байт - это
// число символов для разных длин кодов от 1 до 16, а ниже сами символы в
// порядке возрастания кодов Хаффмана.

#include <sys/time.h>

//------------------- gettime_dt_mks ----------------------
// разность в микросекундах
int gettime_dt_mks(struct timeval *tv1, struct timeval *tv2)
{
    return((tv2->tv_sec - tv1->tv_sec)*1000000 +
           (tv2->tv_usec - tv1->tv_usec));
}

//-------------- print_bits ----------------
// Распечатать число в двоичном виде. len -длина(бит).
int print_bits(int val, int len)
{
    int i, maska = 1 << (len - 1);
    if((val >> len) != 0) printf("Error: val=%d; len=%d; ", val, len);
    for(i=0; i<len; i++){
        if((val & maska) != 0) printf("1");
        else printf("0");
        maska = maska >> 1;
    }
    return(0);
}

//---------------- main -----------------------
//printf("\n");
int main()
{
    int x1[]={
        'A', 900,
        'B', 370,
        'C', 350,
        'D', 350,
        'E', 350,
        'F', 350,
        'G', 350,
        'H', 350,
        'I', 350,
        'J', 350,
        'K', 350,
        'L', 350,
        'M', 1,
    };

    int x2[256*2]; //заряжается автоматически

    int x3[]={
        'A', 10,
        'B', 10,
        'C', 10,
        'D', 10,
        'E', 10,
        'F', 10,
        'G', 10,
        'H', 10,
    };

    int x4[]={ // Фибоначчи
        'A', 196418,
        'B', 121393,
        'C',  75025,
        'D',  46368,
        'E',  28657,
        'F',  17711,
        'G',  10946,
        'H',   6765,
        'I',   4181,
        'J',   2584,
        'K',   1597,
        'L',    987,
        'M',    610,
        'N',    377,
        'O',    233,
        'P',    144,
        'Q',     89,
        'R',     55,
        'S',     34,
        'T',     21,
        'U',     13,
        'V',      8,
        'W',      5,
        'X',      3,
        'Y',      2,
        'Z',      1,
    };

    char *ptr, buf[100];
    unsigned char ch;
    int i, j, k, n, fr, len, S, S0;
    struct s_fjp1  s[1];
    struct s_fjp_sym  *sym = s->fsym[0].sym;
    int Max_sym = 256;
    int Nsym = 256;
    int *a1;
    struct timeval tv1, tv2;
    int t;

    for(i=0, j=0; i<(int)(sizeof(x2)/sizeof(x2[0])/2); i++, j+=2){
        x2[j] = i;
        x2[j+1] = 10;
        //x2[j+1] = (i+1)*(i+1);
        //x2[j+1] = (256-i)*(256-i);
    }

    memset(s, 0, sizeof(struct s_fjp1));
    n = sizeof(x1)/sizeof(x1[0]);
    for(k=0; k<n; k=k+2){
        sym[x1[k]].freq = x1[k+1];
    }

START:

    // ввод данных
    printf("-----------------\n");
    while(1){
        printf("--> "); fflush(stdout);
        ptr = fgets(buf, sizeof(buf), stdin);
        if(ptr==NULL) exit(0);
        k = strlen(buf);
        if(k>0 && buf[k-1]=='\n') buf[--k]=0;
        if(k==0) break;
        if(strncmp(buf, "arr", 3)==0){
            k = atoi(buf+3);
            printf("arrnum=%d\n", k);
            if(k == 1){ a1=x1; n = sizeof(x1)/sizeof(x1[0]);}
            else if(k == 2){ a1=x2; n = sizeof(x2)/sizeof(x2[0]);}
            else if(k == 3){ a1=x3; n = sizeof(x3)/sizeof(x3[0]);}
            else if(k == 4){ a1=x4; n = sizeof(x4)/sizeof(x4[0]);}
            else{ printf("Error\n"); continue;}
            memset(sym, 0, sizeof(s->fsym[0].sym));
            for(k=0; k<n; k=k+2){
                sym[a1[k]].freq = a1[k+1];
            }
        }
        else{
            k=sscanf(buf, "%c %d", &ch, &fr);
            if(k!=2){ printf("Error\n"); continue;}
            sym[(int)ch].freq = fr;
        }
    }

    //обнулить
    for(i=0; i<Nsym; i++){
        sym[i].bits = 0;
        sym[i].hcod = 0;
    }

    // расчет кодов
    gettimeofday(&tv1, NULL);
    n = fjp_hfm_code(s->tree, sym, s->fsym[0].buf);
    printf("n = fjp_hfm_code()=%d\n", n);
    gettimeofday(&tv2, NULL);
    t = gettime_dt_mks(&tv1, &tv2);

    // распечатка кодов Хаффмана
    S=0; S0=0; len=0;
    for(i=0, k=1; i<Max_sym; i++){
        if(sym[i].freq > 0){
            printf("%3d. %02X", k++, i);
            if(i>32 && i<127) printf(" (%c) ", i);
            else printf("     ");
            printf("len=%2d  freq=%5d  ", sym[i].bits, sym[i].freq);
            print_bits(sym[i].hcod, sym[i].bits);
            printf("\n");
            if(len < sym[i].bits) len = sym[i].bits;
            S = S + (sym[i].bits * sym[i].freq);
            S0 = S0 + 8 * sym[i].freq;
        }
    }
    printf("n = fjp_hfm_code()=%d\n", n);
    printf("Maxlen=%d\n", Maxlen); Maxlen = 0; fl=0; //--------отладочная-----
    printf("S =%d\n", S);
    printf("S0=%d\n", S0);
    if(S0>0) printf("L =%0.3f  bit/symbol; max_len=%d\n", 8.0 * S / S0, len);
    printf("t=%d mksek\n", t);

    // распечатка массива buf
    for(i=0; i<16; i++) printf("%d, ", s->fsym[0].buf[i] & 255);
    printf("\n");
    for(j=0; j<n; j++, i++){
        printf("%02X, ", s->fsym[0].buf[i] & 255);
        if(((j+1)&15)==0) printf("\n");
    }
    printf("\n");
    goto START;
}


1. Оптимизатор JPEG-файлов (34 кб), он самодостаточный и может сжимать сторонние файлы (базовые).
https://pastebin.com/J2aHcGFr

2. JPEG-кодер (42 кб). К нему подключен файл отимизатора, в оптимизаторе нужно отключить тестовую обертку (макрос в строке 920), и можно установить макрос FJP_FL_TEST в ноль для уменьшения выдачи (строка 34). На вход нужен BMP-файл.
https://pastebin.com/Ppe2NdsD

Несколько ссылок на рисунки с сайта
http://cpp.mazurok.com/huffman_coding/
которые получше сжимаются:
1. http://cpp.mazurok.com/wp-content/galle ... %D0%B9.jpg
2. http://cpp.mazurok.com/wp-content/galle ... %D1%86.jpg
3. http://cpp.mazurok.com/wp-content/galle ... %D0%B0.jpg

 Профиль  
                  
 
 Re: СИ. Коды Хаффмана. Дерево Хаффмана.
Сообщение04.07.2018, 02:42 


02/10/12
211
Есть два способа декодирования кодов Хаффмана.
1. Взять из потока столько бит, какова максимальная длина кодов, и по таблице сразу получить символ. Это быстро, но таблица большая.
2. Наращивать код по одному биту и сравнивать с максимумом для текущей длины. Пример:
Код:
A  0
B  10
C  1100
D  1101
E  11100
F  11101
G  11110
H  11111
Коды длины 1 меньше 1.
Коды длины 2 меньше 11 (двоич).
Коды длины 4 меньше 1110. И т. д.
В статье назван третий способ. Короткие коды декодирует первым способом по небольшой таблице, а длинные - вторым способом.
https://zxpress.ru/article.php?id=8661
Изображение

Я написал пробные компрессор-декомпрессор Хаффмана этим третьим способом. Макросом декомпрессора MZ_FL можно переключать старую и новую функции декодирования. Быстрее в 1,5 - 2 раза.
код: [ скачать ] [ спрятать ]
Используется синтаксис C

//   gcc mzc.c -o mzc.cgi -Wall -Werror -O3
//   ./mzc.cgi

// Компрессор. Аргументы: вх. и вых. файлы.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <sys/time.h>

#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>

#define MZC_ERR_RD_FILE  1
#define MZC_ERR_SYNTAX   2
#define MZC_ERR_MEMORY   3
#define MZC_ERR_CODE     4
#define MZC_ERR_WR_FILE  5

/*
Формат файла:
 |-- блок --|.....|-- блок --|0|0|0|0|

Формат блока:
 |<->|------- dl1 -длина таблицы Хаффмана
 |   |<->|--- dl2 -длина несжатых данных
 |   |   |
 | | | | |таблица Хаффмана|сжатые данные|
         |<---- dl1 ----->|

Формат таблицы Хаффмана:
|счетчики кодов для длин 1...16|список символов|
|<------------ 16 ------------>|
*/


struct s_mzc_tree {
    unsigned int a[256];
    unsigned int b[256];
    int pa[256];
    int pp[256];
    int p[256];
    int bl_count[256];
};

struct s_mzc_sym {
    int   hcod; // код
    int   bits; // длина
};

struct s_mzc{
    char buf[32768]; // промежуточный буфер
    FILE *fp2;       // вых. файл
    int sizefile;    // длина выхо. файла
    int   bit_count; // счетчик битов
    unsigned int ch; // буфер битов

    unsigned int freq[256];     // частоты символов
    struct s_mzc_tree  tree[1]; // дерево
    struct s_mzc_sym  sym[256]; // таблица кодов
    char bufh[16+256]; // таблица для заголовка блока
    int err;
};


//-------- mzc_hfm_code ------------
// расчет кодов
int mzc_hfm_code(struct s_mzc_tree *tree, struct s_mzc_sym *sym, char *buf,
                 unsigned int *freq)
{
    int i, j, k, n, cod, bits, len;
    unsigned int t, aa, ab, bb;
    unsigned int *a  = tree->a;  // частоты листьев
    unsigned int *b  = tree->b;  // частоты узлов
    int *pa = tree->pa; // родительский узел листа
    int *pp = tree->pp; // родительский узел узла
    int *p  = tree->p;  // номер символа, его значение
    int *bl_count = tree->bl_count; // счетчики числа кодов для разных длин

    // зарядка исходных массивов
    memset(buf, 0, 16+256);
    memset(tree, 0, sizeof(struct s_mzc_tree));
    memset(sym, 0, 256 * sizeof(struct s_mzc_sym));
    for(i=0, n=0; i < 256; i++){
        if(freq[i] > 0){
            a[n]   = freq[i];
            p[n++] = i;
        }
    }
    memset(freq, 0, 256 * sizeof(unsigned int));
    if(n==0) return(0); // n -число используемых символов алфавита
    if(n==1){ bl_count[1] = 1; goto RET;}

    // сортировка по возрастанию частоты символов
    for(i=0; i<n; i++){
        for(j=n-1; j>i; j--){
            if(a[j] < a[j-1]){
                t = a[j]; a[j] = a[j-1]; a[j-1] = t;
                t = p[j]; p[j] = p[j-1]; p[j-1] = t;
            }
        }
    }

    // создание дерева
    for(k=0, i=0, j=0; k<(n-1); k++){
        if(i<(n-1))    aa = a[i] + a[i+1]; else aa = UINT_MAX;
        if(i<n && j<k) ab = a[i] + b[j];   else ab = UINT_MAX;
        if(j<(k-1))    bb = b[j] + b[j+1]; else bb = UINT_MAX;

        if(aa <= ab && aa <= bb){
            b[k] = aa;
            pa[i++] = k; pa[i++] = k; // родительский узел
        }
        else if(ab <= aa && ab <= bb){
            b[k] = ab;
            pa[i++] = k; pp[j++] = k; // родительский узел
        }
        else{
            b[k] = bb;
            pp[j++] = k; pp[j++] = k; // родительский узел
        }
    }

    // обход дерева
    for(--k, i=0; i<n; i++){ // k -индекс корневого узла
        for(len=1, j=pa[i]; j<k; j=pp[j], len++);
        bl_count[len]++;
    }

    // уменьшение длин кодов
    for(i=n-1; i>16; i--){
        for(; bl_count[i]>0;){
            for(j=i-2; j>0 && bl_count[j]<=0; j--);
            bl_count[i] -= 2;
            bl_count[i-1]++;
            bl_count[j]--;
            bl_count[j+1] += 2;
        }
    }

RET:

    // зарядка выходного массива
    for(i=1; i<=16; i++) *buf++ = bl_count[i];
    for(cod=0, i=n-1, bits=1; bits <= 16; bits++){
        for(j=0; j < bl_count[bits]; j++){
            *buf++ = t = p[i--];
            sym[t].bits = bits;
            sym[t].hcod = cod++;
        }
        cod = cod << 1;
    }
    return(n);
}

//-------- mzc_putc_fp -------

int mzc_putc_fp(int ch, struct s_mzc *s)
{
    int k=fputc(ch, s->fp2);
    if(k<0){ s->err = MZC_ERR_WR_FILE; return(-1);}
    s->sizefile++;
    return(k);
}

//-------- mzc_fwrite_fp -------

int mzc_fwrite_fp(const char *buf, int n, struct s_mzc *s)
{
    int k = fwrite(buf, 1, n, s->fp2);
    if(k != n){ s->err = MZC_ERR_WR_FILE; return(-1);}
    s->sizefile += n;
    return(n);
}

//-------- mzc_put_bits -------
// записать bits бит
int mzc_put_bits(int cod, int bits, struct s_mzc *s)
{
    int val;

    s->ch = (s->ch << bits) + (((1 << bits) - 1) & cod);
    s->bit_count += bits;
    while(s->bit_count >= 8){
        s->bit_count -= 8;
        val=(s->ch >> s->bit_count) & 255;
        if(mzc_putc_fp(val, s) < 0) return(-1);
    }
    return(0);
}

//------- mzc_flush_bits -------
// сбросить биты
int mzc_flush_bits(struct s_mzc *s)
{
    int val, bits;

    bits = s->bit_count;
    if(bits > 0){
        val = s->ch << (8-bits);
        if(mzc_putc_fp(val, s) < 0) return(-1);
    }
    s->bit_count = s->ch = 0;
    return(0);
}

//-------- mzc_put_hdr ----------
// заголовок блока
int mzc_put_hdr(struct s_mzc *s, int dl1, int dl2)
{
    char buf[4];
    buf[0]=((dl1)>>8)&255; buf[1]=(dl1)&255;
    buf[2]=((dl2)>>8)&255; buf[3]=(dl2)&255;
    if(mzc_fwrite_fp(buf, 4, s) < 0) return(-1);
    if(mzc_fwrite_fp(s->bufh, dl1, s) < 0) return(-1);
    return(0);
}

//-------- mzc_put_blok --------
// кодирует блок
int mzc_put_blok(struct s_mzc *s, int len)
{
    char *p1, *p2;
    unsigned int *freq = s->freq;
    struct s_mzc_sym  *sym = s->sym;
    int k;

    for(p1=s->buf, p2=p1+len; p1<p2; p1++){
        freq[*p1 & 255]++;
    }
    k = mzc_hfm_code(s->tree, sym, s->bufh, freq);

    if(mzc_put_hdr(s, k+16, len) < 0) return(-1);
    for(p1=s->buf, p2=p1+len; p1<p2; p1++){
        k = *p1 & 255;
        if(mzc_put_bits(sym[k].hcod, sym[k].bits, s) < 0) return(-1);
    }
    if(mzc_flush_bits(s) < 0) return(-1);
    return(0);
}

//------- mzc_coder ----------

int mzc_coder(const char *f1, const char *f2, int *err)
{
    FILE *fp1=NULL, *fp2=NULL;
    int k, len, err0=0;
    struct s_mzc  *s=NULL;

    fp1=fopen(f1, "r");
    if(fp1==NULL){ err0 = MZC_ERR_RD_FILE; goto ERR;}
    fp2=fopen(f2, "w");
    if(fp2==NULL){ err0 = MZC_ERR_WR_FILE; goto ERR;}

    s = (struct s_mzc*)malloc(sizeof(struct s_mzc));
    if(s==NULL){ err0 = MZC_ERR_MEMORY; goto ERR;}
    memset(s, 0, sizeof(struct s_mzc));
    s->fp2 = fp2;

    while(1){
        len = fread(s->buf, 1, sizeof(s->buf), fp1);
        if(len != sizeof(s->buf)){
            if(feof(fp1)==0){ err0 = MZC_ERR_RD_FILE; goto ERR;}
        }
        if(len==0) break;
        if(mzc_put_blok(s, len) < 0){ err0 = s->err; goto ERR;}
    }
    if(mzc_fwrite_fp("\0\0\0\0", 4, s) < 0) goto ERR;
    k = s->sizefile;
    fclose(fp1);
    fclose(fp2);
    free(s);
    *err=0;
    return(k);

ERR:

    if(fp1 != NULL) fclose(fp1);
    if(fp2 != NULL) fclose(fp2);
    if(s != NULL) free(s);
    *err = err0;
    return(-1);
}

//------- mzc_strerror --------

const char *mzc_strerror(int err)
{
    switch(err){
        case MZC_ERR_RD_FILE : return("MZC_ERR_RD_FILE");
        case MZC_ERR_SYNTAX  : return("MZC_ERR_SYNTAX");
        case MZC_ERR_MEMORY  : return("MZC_ERR_MEMORY");
        case MZC_ERR_CODE    : return("MZC_ERR_CODE");
        case MZC_ERR_WR_FILE : return("MZC_ERR_WR_FILE");
    }
    return("MZC: Unknow error");
}

//------- gettime_dt_msek ----------
// разность в миллисекундах
int gettime_dt_msek(struct timeval *tv1, struct timeval *tv2)
{
    return((tv2->tv_sec - tv1->tv_sec)*1000 +
           (tv2->tv_usec - tv1->tv_usec + 500)/1000);
}

//-------- get_sizefile ---------

int get_sizefile(const char *f)
{
    struct stat st;
    if(stat(f, &st) < 0) return(-1);
    return(st.st_size);
}

//-------- main -------

int main(int argc, char  const **argv)
{
    int dl1, dl2, t, err;
    struct timeval tv1, tv2;

    if(argc < 3){ printf("Err-arg\n"); exit(0);}

    dl1 = get_sizefile(argv[1]);

    gettimeofday(&tv1, NULL);
    dl2 = mzc_coder(argv[1], argv[2], &err);
    gettimeofday(&tv2, NULL);
    t = gettime_dt_msek(&tv1, &tv2);

    printf("dl2=mzc_coder()=%d; err=%d", dl2, err);
    if(dl2<0) printf("; %s", mzc_strerror(err));
    printf("\n");
    printf("dl1=%d\n", dl1);
    printf("dl2=%d\n", dl2);
    printf("t=%d.%03d sec\n", t/1000, t%1000);
    if(dl1>0 && dl2>0) printf("compress %0.02f %%\n", 100.0*dl2/dl1);
    exit(0);
}
 

код: [ скачать ] [ спрятать ]
Используется синтаксис C

//   gcc mzd.c -o mzd.cgi -Wall -Werror -O3
//   ./mzd.cgi

// Декомпрессор. Аргументы: вх. и вых. файлы.

#define MZ_FL  1 // 0 -медленная функция; 1 -быстрая.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <sys/time.h>

#define MZ_ERR_RD_FILE  1
#define MZ_ERR_SYNTAX   2
#define MZ_ERR_MEMORY   3
#define MZ_ERR_DECODE   4
#define MZ_ERR_WR_FILE  5

struct s_mz{
    const char  *p1; // текущая позиция буфера чтения
    const char  *p2; // за край данных буфера чтения
    char  buf_rd[512]; // буфер чтения
    char  buf[4096];   // промежуточный буфер
    int   bit_count;   // счетчик битов
    unsigned int  ch;  // буфер битов
    FILE  *fp1;   // вх. файл
    FILE  *fp2;   // вых. файл
    int sizefile; // длина вых. файла
    int err;

    // таблица Хаффмана
    struct{
        char sym[256]; // список символов в порядке возрастания кода
        int n;         // число символов в алфавите
        int max[17];   // Все коды длины len меньше max[len]
        int idx[17];   // Если код Хаффмана прибавить к элементу этого массива
                       // для соответствующей длины кода, то получится индекс
                       // массива sym, по которому лежит нужный символ
                       // i = idx[len] + cod; sym = sym[i];

        int arr[256];  // массив быстрого декодирования
    } shfm;
};

//------- mz_fgetc --------

int mz_fgetc(struct s_mz *s)
{
    int k;
    if(s->p1 >= s->p2){
        k=fread(s->buf_rd, 1, sizeof(s->buf_rd), s->fp1);
        if(k <= 0){ s->err = MZ_ERR_RD_FILE; return(-1);}
        s->p1 = s->buf_rd;
        s->p2 = s->buf_rd + k;
    }
    return((*s->p1++)&255);
}

//------- mz_fread ---------

int mz_fread(char *buf, int n, struct s_mz *s)
{
    int k, dl1=0;

    k=s->p2 - s->p1;
    if(k>0){
        if(k > n) k=n;
        memmove(buf, s->p1, k);
        dl1 += k;
        s->p1 += k;
    }
    if(dl1 < n){
        k=fread(buf + dl1, 1, n-dl1, s->fp1);
        if(k != (n-dl1)){ s->err = MZ_ERR_RD_FILE; return(-1);}
    }
    return(0);
}

//--------- mz_make_h_tree -------
// построение таблицы Хаффмана
int mz_make_h_tree(const char *buf, int Lbuf, struct s_mz *s)
{
    int i, j, k, k1, k2, n, n1, cod, len, ch;
    int *arr = s->shfm.arr;

    if(Lbuf < 16){ s->err = MZ_ERR_SYNTAX; return(-1);}
    for(i=0, n=0; i<16; i++) n = n + (buf[i]&255); // подсчёт символов
    if(n==0 || n>256 || (n+16)>Lbuf){ s->err = MZ_ERR_SYNTAX; return(-1);}

    memset(&s->shfm, 0, sizeof(s->shfm));
    memmove(s->shfm.sym, buf + 16, n); // символы
    s->shfm.n = n;

    // таблица медленного декодирования
    for(len = 1, cod = 0, i=0; len <= 16; len++){
        k = buf[len-1] & 255; // число кодов текущей длины
        if(k > 0){
            s->shfm.idx[len] = i - cod;
            i += k;
            cod += k;
            if((i<n && cod > ((1 << len) - 1)) ||
               (i==n && (cod - 1) > ((1 << len) - 1)))
            {
                s->err = MZ_ERR_SYNTAX; return(-1);
            }
            s->shfm.max[len] = cod; // максимальный код текущей длины + 1
        }
        cod <<= 1;
    }
    // таблица быстрого декодирования
    for(len = 1, cod = 0, i=16; len <= 8; len++){
        k = buf[len-1] & 255;
        if(k > 0){
            for(; k>0; k--){
                ch = buf[i++] & 255;
                n1 = (1 << (8 - len)) - 1;
                k1 = (ch << 4) + len;
                k2 = (cod << (8-len));
                for(j=0; j<=n1; j++){
                    arr[k2+j] = k1;
                }
                cod++;
            }
        }
        cod <<= 1;
    }
    return(n);
}
# if MZ_FL == 1
//------- mz_get_h_cod ---------
// взять код Хаффмана

// Формат массива arr
// |      MSB      |      LSB      |
// |0|0|0|0|x|x|x|x|x|x|x|x|x|x|x|x|
//         |<-- symbol --->|<-bits>|

int mz_get_h_cod(struct s_mz *s)
{
    int *max, cod, len, k, bits, a;
    int *arr = s->shfm.arr;

    if(s->bit_count < 8){
        k = mz_fgetc(s);
        if(k < 0) return(-1);
        s->ch = (s->ch << 8) | k;
        s->bit_count += 8;
    }
    cod = (s->ch >> (s->bit_count - 8)) & 255;
    a = arr[cod];
    bits = a & 15;
    if(bits > 0){
        s->bit_count -= bits;
        return(a >> 4);
    }
    max = s->shfm.max; // массив максимальных кодов для разных длин
    s->bit_count -= 8; // 8-битный префикс у нас уже есть (cod)
    for(len=9; len<=16; len++){
        if(s->bit_count <= 0){
            k = mz_fgetc(s);
            if(k < 0) return(-1);
            s->ch = k;
            s->bit_count = 8;
        }
        cod = (cod << 1) | ((s->ch >> (--(s->bit_count))) & 1);
        if(cod < max[len]){
            k = s->shfm.idx[len] + cod;
            return(s->shfm.sym[k] & 255);
        }
    }
    s->err = MZ_ERR_DECODE;
    return(-1);
}
#else
//------- mz_get_h_cod -----
// взять код Хаффмана
int mz_get_h_cod(struct s_mz *s)
{
    int *max, cod, len, k;

    max = s->shfm.max; // массив максимальных кодов для разных длин
    for(cod=0, len=1; len<=16; len++){
        if(s->bit_count <= 0){
            k = mz_fgetc(s);
            if(k < 0) return(-1);
            s->ch = k;
            s->bit_count = 8;
        }
        cod = (cod << 1) | ((s->ch >> (--(s->bit_count))) & 1);
        if(cod < max[len]){
            k = s->shfm.idx[len] + cod;
            return(s->shfm.sym[k] & 255);
        }
    }
    s->err = MZ_ERR_DECODE;
    return(-1);
}
#endif
//----- mz_ret_bytes_ch ------
// возврат байта из буфера битов
int mz_ret_byte_ch(struct s_mz *s, int *k1)
{
    if(s->bit_count < 8){ s->bit_count = 0; return(0);}
    *k1 = s->ch & 255;
    s->bit_count = 0;
    return(1);
}

//------- mz_get_hdr -------
// заголовок блока
int mz_get_hdr(struct s_mz *s)
{
    int k, k1, len1, len2;
    char buf[16+256];

    k = mz_ret_byte_ch(s, &k1);
    if(k==0){ k1 = mz_fgetc(s); if(k1<0) return(-1);}
    buf[0] = k1;
    if(mz_fread(buf+1, 3, s) < 0) return(-1);

    len1 = ((buf[0] & 255) << 8) + (buf[1] & 255);
    if(len1==0) return(0);
    len2 = ((buf[2] & 255) << 8) + (buf[3] & 255);
    if(len1 > (16+256)){ s->err = MZ_ERR_SYNTAX; return(-1);}

    if(mz_fread(buf, len1, s) < 0) return(-1);
    if(mz_make_h_tree(buf, len1, s) < 0) return(-1);
    return(len2);
}

//------ mz_fun -----
// декодировать файл
int mz_fun(struct s_mz *s)
{
    int k, n, len=0, Sbuf=sizeof(s->buf);
    char *p1, *p2, *buf = s->buf;

    while(1){
        if(len==0){
            len = mz_get_hdr(s);
            if(len < 0) return(-1);
            if(len==0) break;
        }
        if(len > Sbuf) n=Sbuf;
        else n=len;
        for(p1=buf, p2=p1+n; p1<p2; p1++){
            k = mz_get_h_cod(s);
            if(k<0) return(-1);
            *p1 = k;
        }
        len -= n;
        s->sizefile += n;
        k = fwrite(buf, 1, n, s->fp2);
        if(k != n){ s->err = MZ_ERR_WR_FILE; return(-1);}
    }
    return(s->sizefile);
}

//----- mz_decoder -------

int mz_decoder(const char *f1, const char *f2, int *err)
{
    struct s_mz  *s=NULL;
    FILE *fp1=NULL, *fp2=NULL;
    int err0, k;

    fp1 = fopen(f1, "r");
    if(fp1==NULL){ err0 = MZ_ERR_RD_FILE; goto ERR;}

    fp2 = fopen(f2, "w");
    if(fp2==NULL){ err0 = MZ_ERR_WR_FILE; goto ERR;}

    s = (struct s_mz*)malloc(sizeof(struct s_mz));
    if(s==NULL){ err0 = MZ_ERR_MEMORY; goto ERR;}
    memset(s, 0, sizeof(struct s_mz));
    s->fp1 = fp1;
    s->fp2 = fp2;
    s->p1 = s->p2 = s->buf_rd;

    k = mz_fun(s);
    if(k<0){ err0 = s->err; goto ERR;}

    fclose(fp1);
    fclose(fp2);
    free(s);
    *err=0;
    return(k);

ERR:
    if(fp1 != NULL) fclose(fp1);
    if(fp2 != NULL) fclose(fp2);
    if(s != NULL) free(s);
    *err=err0;
    return(-1);
}

//---- mz_strerror ------

const char *mz_strerror(int err)
{
    switch(err){
        case MZ_ERR_RD_FILE : return("MZ_ERR_RD_FILE");
        case MZ_ERR_SYNTAX  : return("MZ_ERR_SYNTAX");
        case MZ_ERR_MEMORY  : return("MZ_ERR_MEMORY");
        case MZ_ERR_DECODE  : return("MZ_ERR_DECODE");
        case MZ_ERR_WR_FILE : return("MZ_ERR_WR_FILE");
    }
    return("MZ: Unknow error");
}


//------ gettime_dt_mks --------
// разность в миллисекундах
int gettime_dt_msek(struct timeval *tv1, struct timeval *tv2)
{
    return((tv2->tv_sec - tv1->tv_sec)*1000 +
           (tv2->tv_usec - tv1->tv_usec + 500)/1000);
}

//------ main -------

int main(int argc, char const **argv)
{
    int dl1, t, err;
    struct timeval tv1, tv2;

    if(argc < 3){ printf("Err-arg\n"); exit(0);}

    gettimeofday(&tv1, NULL);
    dl1 = mz_decoder(argv[1], argv[2], &err);
    gettimeofday(&tv2, NULL);
    t = gettime_dt_msek(&tv1, &tv2);

    printf("dl1=mz_decoder()=%d; err=%d", dl1, err);
    if(dl1<0) printf("; %s", mz_strerror(err));
    printf("\n");
    printf("t=%d.%03d sec\n", t/1000, t%1000);

    exit(0);
}
 

 Профиль  
                  
 
 Re: СИ. Коды Хаффмана. Дерево Хаффмана.
Сообщение18.07.2018, 22:04 


02/10/12
211
Программа в предыдущем сообщении (компрессор-декомпрессор) содержит ошибку. Ниже исправленный компрессор, а декомпрессору исправлений не требуется.

Описание ошибки.
В программе применен способ передачи информации о кодах как в JPEG-файлах, потому что этот способ очень простой. В заголовке блока сначала идут 16 байт - это счетчики кодов разных длин от 1 до 16. За ними идет список символов в порядке возрастания их кодов Хаффмана. Всё бы хорошо, но попался файл, PNG-рисунок, в котором все коды получились одинаковой длины 8 бит, и кодов этих 256. Т. е. используются все символы алфавита, да еще и примерно с одинаковой частотой. Невероятно, но случилось. Так в нескольких блоках, файл большой, 3 Мб. Для такого блока счетчики кодов должны бы выглядеть так:
0, 0, 0, 0, 0, 0, 0, 256, 0, 0, 0, 0, 0, 0, 0, 0.
Но счетчики одно-байтовые, 256=0. Файл, понятно, не сжимается, "сжатый" файл больше исходного, но он еще и не разжимается декомпрессором, ошибку выдает.

Как это работает в JPEG? Там запрещены коды Хаффмана, состоящие из одних только единичных битов. Поэтому если бы это случилось в JPEG, то было бы 255 кодов длины 8 бит от 0x00 до 0xFE; и еще 1 код длины 9 бит 0x1FE. И счетчики кодов:
0, 0, 0, 0, 0, 0, 0, 255, 1, 0, 0, 0, 0, 0, 0, 0.
Я не подумав отключил в компрессоре отсеивание запрещенных кодов, не сообразил, и вот.

Ошибку можно воспроизвести. Для этого нужен тестовый файл, длиной 256 байт, содержащий все символы алфавита. Вот программа создания такого файла:
код: [ скачать ] [ спрятать ]
Используется синтаксис C
//   gcc tmp.c -o tmp.cgi -Wall -Werror -O3
//   ./tmp.cgi


#include <stdio.h>
#include <string.h>
#include <stdlib.h>


//----------- main ----------

int main()
{
    FILE *fp1=NULL;
    const char *f1="test_256";
    int i;

    fp1 = fopen(f1, "w");
    if(fp1==NULL){ printf("fp1 = fopen()=NULL\n"); exit(0);}

    for(i=0; i<256; i++){
        fputc(i, fp1);
    }
    exit(0);
}
 

Ошибку я исправил так: в функции mzc_hfm_code ввел строку (отмечена восклицанием), и этот описанный выше предельный случай теперь обрабатывается как в JPEG, а остальное без изменений:
Используется синтаксис C
    // зарядка выходного массива
    if(bl_count[8]==256){ bl_count[8] = 255; bl_count[9] = 1;} //--- !!!
    for(i=1; i<=16; i++) *buf++ = bl_count[i];
    for(cod=0, i=n-1, bits=1; bits <= 16; bits++){
        for(j=0; j < bl_count[bits]; j++){
            *buf++ = t = p[i--];
            sym[t].bits = bits;
            sym[t].hcod = cod++;
        }
        cod = cod << 1;
    }

Еще одну мелкую ошибку нашел визуально в компрессоре, в функции mzc_coder:
Используется синтаксис C
//Было
    if(mzc_fwrite_fp("\0\0\0\0", 4, s) < 0) goto ERR;

//Стало
    if(mzc_fwrite_fp("\0\0\0\0", 4, s) < 0){ err0 = s->err; goto ERR;}
 

В офтопе о JPEG

(Оффтоп)

Для чего в JPEG запрещены коды, состоящие из одних только единиц? Как я понимаю, вот для чего. В скане среди сжатых данных могут встретиться маркеры рестарта или конца файла. Маркеры узнаваемы, они состоят из двух байт, первый 0xFF, второй отличен от 0xFF и от 0x00 и обозначает назначение маркера. Если при кодировании получается байт 0xFF, то он заменяется комбинацией двух байт 0xFF00. Поэтому маркеры внутри скана ни с чем не спутать. Остаток текущего байта перед маркером заполняется единицами.
Код:
|               |               |               |
| | | | | | | | |0|1|1|1|1|1|1|1| | | | | | | | |
|--рабочая часть->|< заполнение>|<----маркер--->|
Если символов мало, то коды короткие, например не более 3 бит. Если декодер дошел до заполнения, и если бы не было запрета на единичные коды, то он мог бы заполнение принять за код, а это сбой.


Исправленный компрессор:
код: [ скачать ] [ спрятать ]
Используется синтаксис C
//   gcc mzc.c -o mzc.cgi -Wall -Werror -O3
//   ./mzc.cgi

// Компрессор. Аргументы: вх. и вых. файлы.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <sys/time.h>

#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>

#define MZC_ERR_RD_FILE  1
#define MZC_ERR_SYNTAX   2
#define MZC_ERR_MEMORY   3
#define MZC_ERR_CODE     4
#define MZC_ERR_WR_FILE  5

/*
Формат файла:
 |-- блок --|.....|-- блок --|0|0|0|0|

Формат блока:
 |<->|------- dl1 -длина таблицы Хаффмана
 |   |<->|--- dl2 -длина несжатых данных
 |   |   |
 | | | | |таблица Хаффмана|сжатые данные|
         |<---- dl1 ----->|

Формат таблицы Хаффмана:
|счетчики кодов для длин 1...16|список символов|
|<------------ 16 ------------>|
*/


struct s_mzc_tree {
    unsigned int a[256];
    unsigned int b[256];
    int pa[256];
    int pp[256];
    int p[256];
    int bl_count[256];
};

struct s_mzc_sym {
    int   hcod; // код
    int   bits; // длина
};

struct s_mzc{
    char buf[32768]; // промежуточный буфер
    FILE *fp2;       // вых. файл
    int sizefile;    // длина выхо. файла
    int   bit_count; // счетчик битов
    unsigned int ch; // буфер битов

    unsigned int freq[256];     // частоты символов
    struct s_mzc_tree  tree[1]; // дерево
    struct s_mzc_sym  sym[256]; // таблица кодов
    char bufh[16+256]; // таблица для заголовка блока
    int err;
};


//-------- mzc_hfm_code ------------
// расчет кодов
int mzc_hfm_code(struct s_mzc_tree *tree, struct s_mzc_sym *sym, char *buf,
                 unsigned int *freq)
{
    int i, j, k, n, cod, bits, len;
    unsigned int t, aa, ab, bb;
    unsigned int *a  = tree->a;  // частоты листьев
    unsigned int *b  = tree->b;  // частоты узлов
    int *pa = tree->pa; // родительский узел листа
    int *pp = tree->pp; // родительский узел узла
    int *p  = tree->p;  // номер символа, его значение
    int *bl_count = tree->bl_count; // счетчики числа кодов для разных длин

    // зарядка исходных массивов
    memset(buf, 0, 16+256);
    memset(tree, 0, sizeof(struct s_mzc_tree));
    memset(sym, 0, 256 * sizeof(struct s_mzc_sym));
    for(i=0, n=0; i < 256; i++){
        if(freq[i] > 0){
            a[n]   = freq[i];
            p[n++] = i;
        }
    }
    memset(freq, 0, 256 * sizeof(unsigned int));
    if(n==0) return(0); // n -число используемых символов алфавита
    if(n==1){ bl_count[1] = 1; goto RET;}

    // сортировка по возрастанию частоты символов
    for(i=0; i<n; i++){
        for(j=n-1; j>i; j--){
            if(a[j] < a[j-1]){
                t = a[j]; a[j] = a[j-1]; a[j-1] = t;
                t = p[j]; p[j] = p[j-1]; p[j-1] = t;
            }
        }
    }

    // создание дерева
    for(k=0, i=0, j=0; k<(n-1); k++){
        if(i<(n-1))    aa = a[i] + a[i+1]; else aa = UINT_MAX;
        if(i<n && j<k) ab = a[i] + b[j];   else ab = UINT_MAX;
        if(j<(k-1))    bb = b[j] + b[j+1]; else bb = UINT_MAX;

        if(aa <= ab && aa <= bb){
            b[k] = aa;
            pa[i++] = k; pa[i++] = k; // родительский узел
        }
        else if(ab <= aa && ab <= bb){
            b[k] = ab;
            pa[i++] = k; pp[j++] = k; // родительский узел
        }
        else{
            b[k] = bb;
            pp[j++] = k; pp[j++] = k; // родительский узел
        }
    }

    // обход дерева
    for(--k, i=0; i<n; i++){ // k -индекс корневого узла
        for(len=1, j=pa[i]; j<k; j=pp[j], len++);
        bl_count[len]++;
    }

    // уменьшение длин кодов
    for(i=n-1; i>16; i--){
        for(; bl_count[i]>0;){
            for(j=i-2; j>0 && bl_count[j]<=0; j--);
            bl_count[i] -= 2;
            bl_count[i-1]++;
            bl_count[j]--;
            bl_count[j+1] += 2;
        }
    }

RET:

    // зарядка выходного массива
    if(bl_count[8]==256){ bl_count[8] = 255; bl_count[9] = 1;}
    for(i=1; i<=16; i++) *buf++ = bl_count[i];
    for(cod=0, i=n-1, bits=1; bits <= 16; bits++){
        for(j=0; j < bl_count[bits]; j++){
            *buf++ = t = p[i--];
            sym[t].bits = bits;
            sym[t].hcod = cod++;
        }
        cod = cod << 1;
    }
    return(n);
}

//-------- mzc_putc_fp -------

int mzc_putc_fp(int ch, struct s_mzc *s)
{
    int k=fputc(ch, s->fp2);
    if(k<0){ s->err = MZC_ERR_WR_FILE; return(-1);}
    s->sizefile++;
    return(k);
}

//-------- mzc_fwrite_fp -------

int mzc_fwrite_fp(const char *buf, int n, struct s_mzc *s)
{
    int k = fwrite(buf, 1, n, s->fp2);
    if(k != n){ s->err = MZC_ERR_WR_FILE; return(-1);}
    s->sizefile += n;
    return(n);
}

//-------- mzc_put_bits -------
// записать bits бит
int mzc_put_bits(int cod, int bits, struct s_mzc *s)
{
    int val;

    s->ch = (s->ch << bits) + (((1 << bits) - 1) & cod);
    s->bit_count += bits;
    while(s->bit_count >= 8){
        s->bit_count -= 8;
        val=(s->ch >> s->bit_count) & 255;
        if(mzc_putc_fp(val, s) < 0) return(-1);
    }
    return(0);
}

//------- mzc_flush_bits -------
// сбросить биты
int mzc_flush_bits(struct s_mzc *s)
{
    int val, bits;

    bits = s->bit_count;
    if(bits > 0){
        val = s->ch << (8-bits);
        if(mzc_putc_fp(val, s) < 0) return(-1);
    }
    s->bit_count = s->ch = 0;
    return(0);
}

//-------- mzc_put_hdr ----------
// заголовок блока
int mzc_put_hdr(struct s_mzc *s, int dl1, int dl2)
{
    char buf[4];
    buf[0]=((dl1)>>8)&255; buf[1]=(dl1)&255;
    buf[2]=((dl2)>>8)&255; buf[3]=(dl2)&255;
    if(mzc_fwrite_fp(buf, 4, s) < 0) return(-1);
    if(mzc_fwrite_fp(s->bufh, dl1, s) < 0) return(-1);
    return(0);
}

//-------- mzc_put_blok --------
// кодирует блок
int mzc_put_blok(struct s_mzc *s, int len)
{
    char *p1, *p2;
    unsigned int *freq = s->freq;
    struct s_mzc_sym  *sym = s->sym;
    int k;

    for(p1=s->buf, p2=p1+len; p1<p2; p1++){
        freq[*p1 & 255]++;
    }
    k = mzc_hfm_code(s->tree, sym, s->bufh, freq);

    if(mzc_put_hdr(s, k+16, len) < 0) return(-1);
    for(p1=s->buf, p2=p1+len; p1<p2; p1++){
        k = *p1 & 255;
        if(mzc_put_bits(sym[k].hcod, sym[k].bits, s) < 0) return(-1);
    }
    if(mzc_flush_bits(s) < 0) return(-1);
    return(0);
}

//------- mzc_coder ----------

int mzc_coder(const char *f1, const char *f2, int *err)
{
    FILE *fp1=NULL, *fp2=NULL;
    int k, len, err0=0;
    struct s_mzc  *s=NULL;

    fp1=fopen(f1, "r");
    if(fp1==NULL){ err0 = MZC_ERR_RD_FILE; goto ERR;}
    fp2=fopen(f2, "w");
    if(fp2==NULL){ err0 = MZC_ERR_WR_FILE; goto ERR;}

    s = (struct s_mzc*)malloc(sizeof(struct s_mzc));
    if(s==NULL){ err0 = MZC_ERR_MEMORY; goto ERR;}
    memset(s, 0, sizeof(struct s_mzc));
    s->fp2 = fp2;

    while(1){
        len = fread(s->buf, 1, sizeof(s->buf), fp1);
        if(len != sizeof(s->buf)){
            if(feof(fp1)==0){ err0 = MZC_ERR_RD_FILE; goto ERR;}
        }
        if(len==0) break;
        if(mzc_put_blok(s, len) < 0){ err0 = s->err; goto ERR;}
    }
    if(mzc_fwrite_fp("\0\0\0\0", 4, s) < 0){ err0 = s->err; goto ERR;}
    k = s->sizefile;
    fclose(fp1);
    fclose(fp2);
    free(s);
    *err=0;
    return(k);

ERR:

    if(fp1 != NULL) fclose(fp1);
    if(fp2 != NULL) fclose(fp2);
    if(s != NULL) free(s);
    *err = err0;
    return(-1);
}

//------- mzc_strerror --------

const char *mzc_strerror(int err)
{
    switch(err){
        case MZC_ERR_RD_FILE : return("MZC_ERR_RD_FILE");
        case MZC_ERR_SYNTAX  : return("MZC_ERR_SYNTAX");
        case MZC_ERR_MEMORY  : return("MZC_ERR_MEMORY");
        case MZC_ERR_CODE    : return("MZC_ERR_CODE");
        case MZC_ERR_WR_FILE : return("MZC_ERR_WR_FILE");
    }
    return("MZC: Unknow error");
}

//------- gettime_dt_msek ----------
// разность в миллисекундах
int gettime_dt_msek(struct timeval *tv1, struct timeval *tv2)
{
    return((tv2->tv_sec - tv1->tv_sec)*1000 +
           (tv2->tv_usec - tv1->tv_usec + 500)/1000);
}

//-------- get_sizefile ---------

int get_sizefile(const char *f)
{
    struct stat st;
    if(stat(f, &st) < 0) return(-1);
    return(st.st_size);
}

//-------- main -------

int main(int argc, char  const **argv)
{
    int dl1, dl2, t, err;
    struct timeval tv1, tv2;

    if(argc < 3){ printf("Err-arg\n"); exit(0);}

    dl1 = get_sizefile(argv[1]);

    gettimeofday(&tv1, NULL);
    dl2 = mzc_coder(argv[1], argv[2], &err);
    gettimeofday(&tv2, NULL);
    t = gettime_dt_msek(&tv1, &tv2);

    printf("dl2=mzc_coder()=%d; err=%d", dl2, err);
    if(dl2<0) printf("; %s", mzc_strerror(err));
    printf("\n");
    printf("dl1=%d\n", dl1);
    printf("dl2=%d\n", dl2);
    printf("t=%d.%03d sec\n", t/1000, t%1000);
    if(dl1>0 && dl2>0) printf("compress %0.02f %%\n", 100.0*dl2/dl1);
    exit(0);
}

 

 Профиль  
                  
 
 Re: СИ. Коды Хаффмана. Дерево Хаффмана.
Сообщение18.07.2018, 22:59 
Супермодератор
Аватара пользователя


09/05/12
17338
Кронштадт
 !  oleg_2, все-таки не стоит превращать форум в личный блог. На пять Ваших последних сообщений никто не ответил (да и ответы на первое трудно рассматривать всерьез), по-видимому, из этого следует сделать вывод об отсутствии интереса к обсуждению.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Toucan, maxal, PAV, Karan, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group