СИ. Коды Хаффмана. Дерево Хаффмана.

[oleg_2]

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

(Оффтоп)

neerc.ifmo.ru/wiki/

Терминология: я условно листья называю листьями, а узлами называю те узлы, которые не являются листьями.

Используется синтаксис 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.

[Sonic86]

(Оффтоп)

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

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

[ScienceGO]

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

(Оффтоп)

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

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

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

[oleg_2]

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

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

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

[oleg_2]

Сразу не догадался. Можно и по-другому сделать обход дерева - от каждого листа к корню с подсчётом длины кода этого листа. Блок "обход дерева" получается компактней и понятней. Ниже функция, введен дополнительный массив 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);
}
 

[oleg_2]

Я написал программу оптимизации кодов Хаффмана в базовых (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

[oleg_2]

Есть два способа декодирования кодов Хаффмана.
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);
}
 

[oleg_2]

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

Описание ошибки.
В программе применен способ передачи информации о кодах как в 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);
}

 

[Pphantom]

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

[belalugoci]

Займёмся некропостингом.

oleg_2 в сообщении #1324268 писал(а):

Есть два способа декодирования кодов Хаффмана.
1. Взять из потока столько бит, какова максимальная длина кодов, и по таблице сразу получить символ. Это быстро, но таблица большая.
2. Наращивать код по одному биту и сравнивать с максимумом для текущей длины.
...
В статье назван третий способ. Короткие коды декодирует первым способом по небольшой таблице, а длинные - вторым способом.
...
Я написал пробные компрессор-декомпрессор Хаффмана этим третьим способом. Макросом декомпрессора MZ_FL можно переключать старую и новую функции декодирования. Быстрее в 1,5 - 2 раза.

Мне кажется по таблице Хаффмана будет видно (для текстового файла например это справедливо), что вероятности распределяются экспоненциально и самому частому символу соответствует самый короткий код, а значит выбирая например для кода от 3 до 10 бит сразу с места код в 8 бит вы себя лишаете очевидного использования знания о частотах, вы будете каждый раз делать лишнюю проверку на коды в 8 бит и будете регулярно это делать для заведомо частых кодов в 3 бита - и где тут эффективность?
Совсем другое дело - конкретная реализация работы с битами.
Как пример для моего случая:
001 : e : 22343
11111111 : в : 1
как мы видим, у меня всего один символ с кодом 8 и ~22000 символов с кодом 3, как-то очень сомнительно что проверка 8-7-6-5-4-3 эффективнее нежели сразу 3.

[oleg_2]

belalugoci в сообщении #1493383 писал(а):

а значит выбирая например для кода от 3 до 10 бит сразу с места код в 8 бит

Это не так. Я выбираю не код в 8 бит, а коды от 1 до 8 бит включительно, т. е.
1 <= bits <= 8
Вот этот кусок кода:

Используется синтаксис C

//------- 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);
    }
    ....
}
 

Из этого куска возвращаются все коды, длина которых не более 8 бит. Верхняя половина этого куска - это просто чтение байтов из входного потока; так или иначе все байты должны быть прочитаны и пройти через буфер битов s->ch. Нижняя половина этого куска - это собственно декодирование, там есть чтение массива, что плохо, но как иначе? В любом случае что-то читать потребуется для декодирования. Другая, не показанная, часть этой функции обрабатывает коды, которые длиннее 8-ми бит.

Я протестил эти кодер-декодер на своём компьютере. Надо сказать, что на моём компьютере большой разброс времени выполнения, а на малых файлах вообще трудно что-либо измерить, но на больших, много-мегабайтных файлах выигрыш времени есть очевидный, как я и написал, в 1,5 - 2 раза.

Если Вы запускали эти программы, то интересно, какие результаты времени Вы получили?

Я не знаю устройста компьютера и ассемблер, а поэтому применяю два эвристических, т. е. ничем не обоснованных, приёма микрооптимизации:
1. В критических кусках кода обходиться минимальным числом переменных. Тогда все или некоторые из этих переменных будут безвылазно сидеть в регистрах процессора во время выполнения этого куска.
2. В критических кусках кода, если некие переменные участвуют в нескольких операциях, то по возможности эти операции писать компактно, сразу друг за другом. Тогда эти переменные, попав в регистры процессора, посидят там безвылазно хотя бы для выполнения нескольких операций, а не одной-единственной, чтобы не дёргать память на каждый чих.

[B@R5uk]

Когда-то давным-давно на первом (или втором?) курсе универа я для лишней галочки у преподавателя проги делал алгоритм Хаффмана. Если мне не изменяет память, то источником знания для сего подвига у меня были википедия и здравый смысл (да, понимаю, взаимоисключающие понятия). У меня даже код сохранился с тех времён.

Из плюсов программа использует только операторы new и delete, чтобы не заморачиваться с гемморойными сишными malloc и free. На тот момент мои знания о структурах данных ограничивались односвязными и двухсвязными списками и деревьями, ни о каких очередях с приоритетом я не знал. Возможно, в википедии упоминалось что-то про эффективность, но на тот момент мне был интересен сам код Хаффмана для текста, а не оптимизация быстродействия, и мне хотелось по-быстрее написать что-нибудь простое и работоспособное. По этой причине поиск двух минимальных элементов для очередного узла дерева Хаффмана ведётся двумя простыми проходами по неотсортированному списку. (На самом деле даже список можно было организовать не как двусвязный список, а как обычный массив. Возможно я хотел параллельно с навыком работы с деревом потренировать навык работы со списком). Это даёт временную сложность $O(n^2)$. Если использовать продвинутые сортирующие структуры, типа очереди с приоритетом, то эту сложность можно сократить до $O(n\log n)$. На тот момент я, видимо, правильно рассудил, что для построения дерева с числом листов не более 256 (а реально — гораздо меньше) квадратичная сложность не так уж страшна, тем более, что продвинутый вариант требует продвинутых знаний и скиллов, которых на тот момент не имелось.

Код приведённый выше осуществляет не только упаковку/распаковку текста по заданному дереву (построенному, кстати, в соответствии с частотами, полученными из упаковываемого текста), но и упаковку/распаковку самого дерева Хаффмана. Восстановление строки текста ведётся простым чтением по одному биту упакованных данных и параллельным проходом по дереву, что для коротких символов тоже не является рациональным. Достоинство программы лишь в том, что она позволяет судить о степени сжимаемости текста с учётом того, что необходимо хранить и само дерево. И эта степень сжатия оказалась очень невелика (по сравнению с моими ожиданиями, во всяком случае). На тот момент я сделал вывод, что для полноценного сжатия текста коды Хаффмана должны кодировать не отдельные символы текста, а целые последовательности символов. А эта задача простым жадным алгоритмом не решается.

-- 08.01.2021, 22:56 --

oleg_2, а что является источником неоптимизированных JPEG'ов? Трудно поверить, что, например, фотошоп не умеет жать файлы как надо.

[StaticZero]

(Оффтоп)

B@R5uk в сообщении #1499772 писал(а):

чтобы не заморачиваться с гемморойными сишными malloc и free

А чего там кровоточит-то?

[B@R5uk]

(Оффтоп)

StaticZero, не помню, честно-честно! После си я долго прогал считал в Матлабе, а сейчас довольно долго уже только Java пользуюсь.

[oleg_2]

StaticZero в сообщении #1499778 писал(а):

У меня даже код сохранился с тех времён

Я Ваш код посмотрел.

Заявленную в статье сложность $O(n)$ я взял не ради быстродействия, а ради простоты кода и компактности. Я считаю своим достижением, что я догадался при построении дерева отбросить символы и сделать листья безымянными, не обременёнными символами. Длины кодов Хаффмана ограничены, в deflate 15 бит для данных и 7 бит для заголовков, а перестроить дерево с именными листьями не получается. А теперь я спокойно перестраиваю дерево, если вылезло за допустимую длину, а потом связываю листья и символы, вернее длины кодов и символы. А потом всё как при декодировании. Ведь в заголовке deflate-блока содержатся (в сжатом виде) длины кодов для всех символов, и больше ничего. А в deflate-протоколе прямо приведён алгоритм в виде Си-кода, как по длинам вычислять коды. И получилось так просто, что даже не верилось поначалу.

B@R5uk в сообщении #1499772 писал(а):

я сделал вывод, что для полноценного сжатия текста коды Хаффмана должны кодировать не отдельные символы текста, а целые последовательности символов

Тут ничего не скажу ни За, ни Против. Но приведу попавшееся мне одно высказывание по этой теме, что любой файл можно закодировать одним-единственным кодом Хаффмана, т. е. одним битом; весь файл сжимается в один бит, но к этому биту нужно приложить таблицу кодов Хаффмана, содержащую весь исходный файл. Это и есть Ваша идея, доведённая до крайности.
В deflate-сжатии (которое в PNG) применены отголоски Вашей идеи, там отдельные символы кодируются кодами Хаффмана, а где это возможно, даются ссылки на ранее встречавшиеся подстроки. Это близко к тому, что Вы предложили, только последовательности символов не требуется помещать в таблицу кодов, они есть в ранее декодированных данных, а коды Хаффмана привязаны не к последовательностям символов, а к ссылкам. Ссылка это длина-смещение. Эти ссылки на подстроки улучшают сжатие почти всегда.

B@R5uk в сообщении #1499772 писал(а):

oleg_2, а что является источником неоптимизированных JPEG'ов?

Подозреваю, что источником являются самые обычные приложения, вроде фотошопа, где в настройках отключена оптимизация. Толи она выключена по умолчанию, толи человек потыкал на удачу настройки, работает и ладно. Нормальные люди просто не заморачиваются такими пустяками. И ещё правильно ли Вы поняли мою распечатку, вот эту:

Используется синтаксис C

Compress=96.19 %

//Её надо понимать так:
//Compress = (длина оптимизированного файла)/(длина неоптимизированного файла)
 

Если любопытно, то посмотрите мои малофункциональные, простые PNG-кодер и PNG-декодер. Кодер сжимает хуже фирменных, но всёже сопоставим с ними по сжатию, сравнивал я так: брал файл из интернета, декодировал его моим декодером в BMP, а затем кодировал и сравнивал длину исходного и перекодированного. Только надо, чтобы исходный файл был закодирован по той же цветовой схеме:
Type=2; RGB; 24 bit/pixel
по которой только и умеет кодировать мой кодер, а то несравнимо. Декодер выдает цветовую схему исходного файла.

1. PNG-кодер (43 кб):
http://paste.org.ru/index.pl?eooaes

2. PNG-декодер (39 кб):
http://paste.org.ru/index.pl?1ld7cy

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