Блог FX’а

Как я и обещал - продолжение рассказа о сдаче лабораторных по “Методам и средствам компьютерных информационных технологий”. Сегодня будет рассказ о [почти] последней лабораторной.

Для начала - сдавал я эту лабу полторы недели назад, просто все не было времени и/или желания писать об этом.  Пришел я на пару к параллельной группе, т.к. ждать своего урока у этого препода мне было влом. Пришел и офигел. Целая куча народу стоит над ним и ждет, пока он примет у кого-нибудь лабу и перейдет к следующему. А препод особо не спешил, сидел с каждым минут по 15-20 (это мне потом рассказали)… Ну я влез вместо кого-то и в итоге показал лабу 3-м из всего списка желающих. Показывал сначала на своих файлах (которые благополучно захватил из дома). Он посмотрел, посмотрел и говорит “а можешь поменять кое-что в проге и заново скомпилировать”… Я ему - “ну, если уж очень сильно нужно - то да, но мне тут долго настраивать нужно и т.д.”. В итоге препод сдался, но заставил меня создавать в Paint’е файлы и потом кодировать их туда-сюда. Моя программа благополучно все обработала и я со спокойной душой ушел домой. Правда перед этим препод пообещал дать еще одно задание, “вместо того, чтобы сдавать экзамен” - потому я и написал, что это была “почти последняя” лаба.

Теперь о самой лабе - кодирование в GIF я написал намного быстрее, чем раскодирование. Но самое главное - конвертация форматов сейчас реализуется через мой “графический формат”. Т.е. я сделал формат. который просто хранит нужные мне данные так, как мне удобно. Т. е. на самом деле GIF → BMP - это GIF → raw image (мой формат) → BMP. Raw-данные хранятся в оперативной памяти, и, хоть это и достаточно затратно по памяти, но дает дополнительные возможности. Например, можно подключить любой другой формат - нужно только дописать раскодирование этого формата в raw и кодирование из raw’а в этот формат. Собственно, таким образом я и добавил в программу формат BMP.

По просьбе читателей - я выложу все исходники GIF ↔ BMP, только предупреждаю - если вы захотите из этого сделать норм. конвертер - то все, написанное мной прийдется пересматривать и дорабатывать, причем достаточно сильно. Если действительно соберетесь делать что-то подобное - напишите мне - я помогу, и учавствовать в проекте буду, но только после того, как закончится семестр (а это будет после 10-го июня + экзамены).

Файлы: source, exe.

written by FX Poster \\ tags: BMP, gif, Алгоритмы

Такая вот у нас третья лаба по “Методам и средствам компьютерных информационных технологий”. :)

Как вы помните декодировщик gif’а уже готов, теперь вот надо это записать в bmp-файл + научиться кодировать в gif-формат (т.е. от кодирования данных пл методу LZW никуда не денешься). У меня вот такой вопрос к читателям - как вы думаете, как это красивее всего сделать? В теории может не только gif будет, вдруг мне что-то в голову взбредет. :) Поэтому напрашивается реализация в следующем виде:

(графический формат) ↔ (некоторый несжатый формат) ↔ (графический формат)

На практике вижу 2 минуса:

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

С первым смирится можно. А вот со вторым - стоит ли это делать? Не будет ли это слишком накладно в плане расхода памяти?

Вот с этими вопросами я и обращаюсь к вам. :) Жду комментов. И побольше.

written by FX Poster \\ tags: BMP, gif, Алгоритмы

Как и обещал, сегодня будет рассказ о том, как я сдавал свой ungif.

Началось все просто замечательно - я забыл что и на каком месте находится в хедере gif-файла. В итоге препод меня оставил (сказал - давай, готовься) и ушел к своей дипломнице. Я в это время всё выписал что мне нужно было в тетрадку и… Стал ждать… Причем ждал не я один, кроме меня сдать ему лабы хотело еще как минимум 3 человека. После десяти минут ожидания я все-таки напомнил преподу о себе, на что получил ответ “ну тут диплом… подожди еще 5 минут.”. Сколько эти 5 минут длились я скромно умолчу. Наконец он подсел ко мне и я быстренько ему рассказал, что, как и где в gif-файле находится и показал работоспособность моей проги. Далее я боялся только одного - что он меня спросит, как это всё кодируется. Потому что строить таблицу LZW алгоритма для gif-файла у меня желания не было никакого. Но у него в голове созрел другой коварный план: во время рассказа о структуре gif’ов я ему сказал, что там присутствуют некоторые блоки, которые я игнорировал (т.к. мне они действительно были не нужны). Во время разбора файла я ему показывал, что там должно было находится. И вот он решил потестить мою прогу - удалить кусок файла, который я “пропускал” и посмотреть, как заработает моя программа. После удаления этого куска прога зависла… :( И препод, сказав “трудись дальше”, ушел просматривать лабораторную одногрупника. А я полез в коды… При этом думая - где же я так мог лохануться. В общем, оказалось, что я ему неправильно истолковал один момент при считывании из файла (момент касался считывания таблицы цветов). После удаления из файла куска, который действительно можно было удалить, дело пошло лучше - файл открылся, и к тому же правильно.

Потом был рассказ небольшой на тему: какие именно файлы мой ungif обрабатывает неправильно и почему. В самом конце состоялся показ одного из моих комментариев в кодах:

// ToDo

И прозвучала моя фраза - “ну я это к третьей лабе доделаю, ок?”. После чего в блокноте препода была поставлена дата и моя фамилия, что свидетельствовало о том, что вторая лабораторная по КИТам сдана.

PS. Или это всем влом лабы делать, или это я такой шустрый. Но вторую лабу я тоже сдал первый из потока. :)

written by FX Poster \\ tags: gif, LZW, Алгоритмы

Вчера закончилась моя долгая борьба с форматом GIF. Как вы помните, это была вторая лабораторная работа по предмету “Компьютерные Информационные Технологии”.

Первая лабораторная работа (adaptive huffman) у меня делалась примерно 3 дня. На вторую ушло больше 4 недель. Правда две из них лаба спокойно пылилась у меня на винчестере, потому что никаких соображений по поводу того, что именно там было неправильно у меня не было. И вот после моего дня рождения меня пробило - я вьехал, что именно там было не так. Оказалось, что достаточно всего одного блока if-else, чтобы алгоритм стал хотя бы нормально завершаться.

До этого момента работа алгоритма проверялась по схеме пашет-не пашет и коды писались в консольном приложении. Как только он стал “пахать” - все быстро перенеслось на “окошки”. После чего я впал в ступор - алгоритм работал, но выдавал явно не то, что я от него хотел, т.е. на форму выводилось изображение, но не то, которое мне было нужно.

Все это происходило позавчера. Сдать я все хотел на следующий день - потому началась “погоня за ошибками”. В 4 ночи, после жесткого дебага всего алгоритма декодирования изображения в gif-файле (напомню, что в GIFе изображение кодируется с помощью алгоритма LZW), программа приняла относительно рабочий вид - изображение выводилось… Даже понять, что изображено на нем можно было (не на всех файлах, правда)… Но, выводилось оно все-таки немного неправильно. После некоторого момента часть изображения начинала смещаться в непонятном направлении. Обессиленный, я отправился спать, т.к. понять, почему это всё не работает я не мог.

Проснувшись утром, я все-таки решил пойти на практику по КИТам и показать преподу хотя бы то, что есть. Авось у него такие “гении” уже были и он подскажет, где может быть ошибка. Надежды, конечно были маленькие, но… Ну, в общем, им не суждено было сбыться - в универе алгоритм в тот день так и не заработал.

Пришел домой и сел все-таки доделывать этот мой декодировщик gif’а. Началось очень интересное попиксельное сравнение моего изображения с оригиналом. Была найдена точка, с которой начинались глюки. Далее начался дебаг кода. Оказалось, что блок if-else, который мной был добавлен с самого начала работал все-таки немного неправильно. Весь прикол в том, что этот блок к самому декодированию явно не относился. Он относился к чтению данных из файла. Изменил этот блок, запустил программу и… Увидел абсолютно правильное изображение. Ура, товарищи!

Осталось теперь это все сдать преподу. :) Но я уже доволен как слон - 4-х недельные муки закончились!

PS. Я вот сейчас часто ловить себя на мысли - “а если бы я не нашел этот баг…”. Мне страшно даже подумать, что бы со мной было.

Скачать UnGIF

written by FX Poster \\ tags: gif, LZW, Алгоритмы

В предыдущем посте я писал уже об алгоритме FGK. Сегодня (точнее уже вчера) я все-таки доделал и архивирование и разархивирование. Все работает, но пока не так быстро, как хотелось бы. Ничего, посплю, поздравлю девушку с 8 марта и вечерком засяду оптимизировать. Т.к. в пятницу (да, да, мы в эту пятницу учимся) буду показывать это все преподу. Может еще что-нибудь посоветует. И если совсем уж пробьет на программирование - на выходных сразу буду делать 2-ую лабу по этому предмету - раскодировать и вывести на экран изображение какого-нибудь формата. Я себе выбрал gif (построен на алгоритме LZW), так что работы мне на все выходные хватит.

Если кто знает, где можно почитать (и желательно взять реализацию) хеш-таблицы - киньте линк.

Кстати, сегодня пришел к классному выводу - компилятор VS2005 офигенно медленный по сравнению с MinGW (windows-сборка GCC). Это показали тесты моего архиватора. Файл размером ~2,5мб VS2005 (release-режим, оптимизации особого эффекта не дали) заархивировала за 100 секунд, а MinGW (со всеми оптимизациями) - за 48 секунд. Есть над чем задуматься… Нет, мою любимую студию я не брошу - эргономичность у нее просто супер. Но если нужна будет скорость - компилировать буду MinGW’шкой.

Архиватор (~300кб, MinGW)

written by FX Poster \\ tags: gif, Huffman, LZW, MinGW, Visual-Studio-2005, Алгоритмы