Разбор программы "Архиватор"

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

Вложения

HUFFMAN.zip (6.3 Кб, 68 просмотров)

0

В этом примере на C++ вовсю используется арифметика с плавающей точкой.
С точки зрения математика, наверное, код замечателен своими алгоритмами.
С точки зрения низкоуровнего программиста код - тихий ужас, потому как
плавающая точка применена там, где можно все считать в целых числах.

0

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

Если писать на асме сам алгоритм сжатия,то для расчета префиксных кодов по сути нужны только частоты встречаемости.Это уже целочисленные.

Добавлено через 9 минут
Притом,кто мешает использовать FPU,а дальше параллельно использовать АЛУ или подготовить данные пересылкой,что бы не было простоя во время работы FPU?

0

Сообщение от Thread Вероятность вхождения символа-целочисленное значение?

Именно.

unsigned long данных_символов, всего_символов, вероятность ;
...
вероятность = 1000 * данных_символов / всего_символов ;
printf("вероятность = 0.%03i\n", вероятность) ;

0

ЭЭммм,по ходуу с теореей вероятномти у вас проблемы.
Сумма вероятностей всех элем ентов = 1.
Подскажите в какую сторону мне округлять

0

Вероятность есть вещественное число не большее единицы. Но в программе для ее вычисления не требуется плавающая точка. Вероятность преспокойно считается в целых числах. Как - показано выше. Что тут непонятно ?
Синусы, косинусы, тангенсы, котангенсы тоже преспокойно считаются в целых числах. Иначе игрушки типа Doom/Quake при обсчете картинки вида из глаз тормозили бы по черному. В игрушках с обсчетом вида из глаз значения тригонометрических функций выгребаются из готовых таблиц, НО в виде целочисленных значений и именно в этом целочисленном виде используются.

0

Вы так и не поняли до сих пор,что я подшучиваю?
Вот мой код.На асме легко решаеться взятием целой части и остатка.
Что вы сказали лучше забудьте.
Единственная проблема у С++ это работы с флагами.А так вполне для системного программирования Си подходит,но доверия к компилятору не питаю.Лично писал дрова на Си.

int size_fr[256]={0};//частота встречаемости
int count=0; //сумма частот встречаемости

symbols[i].prob = (float)size_fr[i] / count;

Добавлено через 16 минут
Я всего то хотел сказать,что код на асме через структуры будет более читабельней,а не возиться с адресами.По мне со структурами с деревьями проще работать.Начал на FASMе писать но так за ночь и не успел,чтобы показать.На сортировке остановился.
Впрочем парень обявил константы и к ним обращался.


p.s.Забудьтьте.у меня сейчас не лучшее время для разговоров.
Сегодня по бабушке было 40 дней,а уже придеться переезжать в отчий дом.Брата здесь оставлю.

Добавлено через 24 минуты
Впрочем,зачем меня слушать.Я ЛОХ в программировании.Поэтому забудем спор,и никпгда не используйте структур для сложных алгоритмов.

Добавлено через 8 минут
Тот код что я выкинул написал за 4 час,поэтому не придирайтесь.

0

Thread,
на compression.graphicon.ru достаточно много ссылок посвященных конкретно методу Хаффмана. На что из предложенного Вы бы посоветовали обратить внимание?

1

на этом форуме я давно зарегистрирован ,мой последний пост http://forum.compression.ru/vi... 47a6e76a45

Советую начать с
Ватолин Д., Ратушняк А., Смирнов М., Юкин В.
Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео

Сейчас изчаю PPMd,сделал распечатку.

Добавлено через 45 минут

Сообщение от Ethereal Синусы, косинусы, тангенсы, котангенсы тоже преспокойно считаются в целых числах

Мало кто знает,но в FPU эти таблицы встроены для быстрого расчета.

1

Сообщение от Thread Мало кто знает,но в FPU эти таблицы встроены для быстрого расчета.

Хорошо бы ссылку на источник...

0

Извини Mikl___,но это по памяти вспомнилось.Где-то наткнулся,почитал,запомнил.
Но дело в том,что трансцедентные функции без таблиц FPU так быстро не смог бы обработать.
Более сложные(по скорости)из них это корни и логорифмы.Сейчас потихому перехожу на SSE4.Но там не трансцедентных.

P.s.Впрочем,ты ведь знаешь почему.На CUDA еще успееться,а мне для проверки результата и скорости.Почитайте про приз Хаттера.

Добавлено через 12 минут
Впрочем взять любой даташит по FPU и почитать,вроде там натыкался.Но у Зубкова в книге эти вопросы точно не разбираються.

P.s.Всем остальным совет,изучайте ассемблер по книгам.На хорушую книгу и денег не жалко.

0

Сообщение от Thread Более сложные(по скорости)из них это корни и логарифмы

1. Самый известный целочисленный алгоритм для вычисления квадратного корня из числа поражает своей простотой

   C
   1 2 3 4 5 6     unsigned sqrt_cpu_int(usigned X)     {    unsigned div = 1, result = 0;         while (X > 0)         {    X -= div;  div += 2; result += X < 0 ? 0 : 1;     }         return result;     }

   Недостаток данного алгоритма - количество итераций будет увеличиваться с ростом Х
2. вычисление квадратного корня по разложению в ряд Тейлора.
   Пусть Х - любое число; f(X) - некоторая функция, зависящая от X; a - известное число, близкое к Х; f(a) - известное значение функции.
   Разложим f(X) в ряд Тейлора:
   f(X)=f(a)+(X-a)f '(a)+((X-a)² *f" (a))/2! + ... + ((X-a)ⁿ *f ⁿ (a))/n!
   Пусть X - число, из которого нужно извлечь корень. Тогда f(X)=; a - известное число близкое к X; f(a)= - известное число близкое к , и f(X)= +(X-a)/(2)+...=(2a+X-a)/(2)=(a+X)/(2)
   Величина может быть найдена, если задаться величиной и затем вычислить f(X). f(X)² можно сравнить с исходным числом Х. Если точность окажется недостаточной, тогда число а заменяется на f(X)², на f(X) и вычисление повторяется
3. поиск целочисленного квадратного корня методом Ньютона начинается с некоторого значения g₀, которое является начальной оценкой . Затем выполняется серия уточнений значения квадратного корня по формуле g_n+1=(g_n+X/g_n)/2. Для уменьшения количество итераций можно на первом этапе более точно подобрать начальное значения для переменной g₀

   C

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 { usigned x1;   int a, g0, g1;   if ( x <= 1 ) return x;   a = 1;   x1 = x - 1;   if (x1 > 65535) {a = a + 8; x1 = x1 >> 16;}   if (x1 > 255)   {a = a + 4; x1 = x1 >> 8;}   if (x1 > 15)    {a = a + 2; x1 = x1 >> 4;}   if (x1 > 3)     {a = a + 1;}   g0 = 1 << a; // g0 = 2^a   g1 = (g0 + (x >> a)) >> 1;   while (g1 < g0) // повторяем, пока приближения строго уменьшаются   { g0 = g1; g1 = (g0 + (x/g0)) >> 1} }

4. Так как деление достаточно медленная операция, можно от нее отказаться. Для вычисления квадратного корня используем умножение. 32-разрядное число Х будет иметь 16-разрядный квадратный корень. На каждом шаге происходит уточнение 1 бита значения корня. Для ускорения сделано "безбранчевое" вычисление прибавить или отнять значение в соответствующем разряде

   Assembler

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15     mov ebx,4000h     mov ecx,8000h     mov eax,40000000h @@: cmp eax,X     je @f; преждевременный выход из цикла     sbb edx,edx; если CF=1 тогда edx=0FFFFFFFFh иначе edx=0     sub ecx,ebx     and edx,ebx; если CF=1 тогда edx=ebx иначе edx=0     lea ecx,[ecx+edx*2]; если CF=1 тогда ecx=ecx+ebx иначе ecx=ecx-ebx     shr ebx,1; переходим к следующему разряду     mov eax,ecx     mul eax; получаем "eax в квадрате"     test ebx,ebx     jnz @b @@: mov eax,ecx; eax:=sqrt(X)

5. вот метод, который меня "убил"

   C
   1 2 3 4 5 6 7 8 9 10 11 12 int isqrt4(unsigned x) { // Hardware algorithm [GLS]    unsigned m, y, b;    m = 0x40000000;    y = 0;    while(m != 0) {              // Do 16 times.       b = y | m;       y = y >> 1;       if (x >= b) { x = x - b;  y = y | m; }       m = m >> 2;    }    return y; }

   то же на ассемблере

   Assembler
   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18     mov ebp,X         inc ebp     bsr ecx,ebp     and ecx,-2     mov ebx,1     shl ebx,cl;для уменьшения количества итераций         xor eax,eax @@: lea ecx,[eax+ebx]     shr eax,1     cmp ecx,ebp     sbb edx,edx     mov edi,edx     and edx,ecx     sub ebp,edx     and edi,ebx     or eax,edi     shr ebx,2     jnz @b

   Не понятно как, ни деления, ни умножения, но работает! Причем алгоритм был описан аж в 1945 в Von Neumann J. "First Draft of a Reaport on the EDVAC"

0

Эммм,я так и не понял что Вы хотели сказать.

вычисление логорифма занимает 128 тактиков
вот ссылочка на возведение в дробну степень(оно же корень,то что мне и надо)
http://delphiworld.narod.ru/base/sqr_number.html

Я ведь пытался обьяснить,что на CUDA хочу эти процессы расспаралелить.Возможно не говорил,это у меня в уме.

0

Thread,
я пытался поделится целочисленными способами получения квадратного корня (и по аналогии корней других степеней), а определение целочисленного значения lg(X) можно сделать без всяких fyl2x простым целочисленным умножением на магическую целочисленную константу 4D10h = lg(2) * 65536

0

Ой,ой.
Я понял решение,но я ведь горю не о квадратах.Это степенные функции c вещенственным показателем.

Кстати ,я уже модель придумал.Возможно перейду на PPMd

Добавлено через 8 минут

Сообщение от Mikl___ а определение целочисленного значения lg(X) можно сделать без всяких fyl2x простым целочисленным умножением

Можно константу определить.
Честно говоря,я всю таблицу Брадиса перебрал в поисках альтернативы Шеннону.

0

Сообщение от Thread Впрочем,зачем меня слушать.Я ЛОХ в программировании.Поэтому забудем спор

Я такого не говорил.
Просто, в ассемблере, как нигде, важен не столько сам алгоритм, сколько его лаконичная реализация
в кодах процессора. Если Вы хотели показать всем мастер-класс сжатия данных, то на каком-нибудь
другом форуме можно было бы порассуждать об оптимальном алгоритме, но на этом лучше показать
как Вы сумели этот оптимальный алгоритм реализовать. Примеры на C++ здесь не впечатлят.

Добавлено через 10 минут

Сообщение от Thread Извини Mikl___,но это по памяти вспомнилось.Где-то наткнулся,почитал,запомнил. Но дело в том,что трансцедентные функции без таблиц FPU так быстро не смог бы обработать.

Трудно в такое поверить. Схемотехнически выгребание значений из таблиц реализуется легко, по той схеме, что у любого ПЗУ. НО, количество возможных вариантов аргумента для тригонометрических функций у FPU таково, что ПЗУ выйдет запредельных размеров. Поэтому такого не может быть.

0

Про FPU так пока и не нашел.Вот немного о ALU.Думаю этого достаточно,чтобы мне поверить.
Устройство FPU поищите сами.Мне пока не до этого.


Блок целочисленных операций

Первый и основной блок процессора. Хотя, правильнее сказать не блок, а блоки, так как их в процессорах несколько. Грубо говоря, на заре развития, кроме этого блока в процессоре практически ничего и не было. Основная задача ALU, начиная с самых первых моделей и заканчивая современными монстрами, не изменилась. Он все также работает с простыми (целыми) числами, производя операции сложения, вычитания, сравнения, преобразования чисел; выполняет простейшие логические операции, а также битовые сдвиги.

Заметьте, что на ALU не возложены задачи умножения и деления, а все потому, что данные типы вычислений встречаются довольно редко, и как следствие для них выделили собственный блок – “целочисленный умножитель”, благодаря которому удалось поднять производительность ALU, избавив его от нестандартных задач. Операции деления также возложены на умножитель, и выполняются с помощью специальной таблицы констант. Вот такой, весьма простой блок, производительность которого напрямую влияет на производительность процессора во многих задачах, например офисных приложениях, многочисленных специфических программах для расчетов и.т.д.

http://testlabs.kz/processors/... i-fpu.html

0

Сообщение от Thread Про FPU так пока и не нашел.Вот немного о ALU.Думаю этого достаточно,чтобы мне поверить.

Не достаточно.
Умножитель - это умножитель. Если в него вставить готовую таблицу произведений байт на байт (всего 256*256 значений, а это приемлемо), то для умножения 16/32-разрядных чисел останется делать только сдвиги и сложения, а это перепутанные провода и простые логические вентили. Это быстро. Но умножение - не есть вычисление синуса. С синусом, как бы, совсем другое дело. Там так просто от необходимости вычисления итерациями не отделаешся.

0

Таблица синусов до 90 градусов 90 значения типа float.Выше 90 в обратную сторону идут.Дальше теже значения только отрицательные.
Косинус это смещение по фазе на четверть от синуса.С остальным хз.
Примерно так наверно.

0

deleted

0

синус на ассемблере

0