Архив за ‘Кодинг’ категория

Кодирование Хаффмана.

Апрель 16th, 2009

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

Тем не менее, статьи у меня остались, и две я уже выложил у себя на вики в разделе «Статьи». Третью всё пока не соберусь перевести из html в wiki-формат.

Тем не менее, мой сервер регулярно штурмуют вопросами вроде «Пример реализации алгоритма Хаффмана на языке C++». Что ж, мне приятно, что труд мой не пропал для кого-то даром. Тем не менее, также берёт обида за то, что такие вещи можно и самостоятельно реализовать, благо алгоритм кодирования/декодирования очень прост.

Для холивара.

Апрель 13th, 2009

Надо сказать, что в предыдущей заметке про inline-ассемблер было написано не всё, а также допущена масса грубых ошибок, которые были выявлены и исправлены в процессе компиляции исходников при помощи GNU C++.

Об этом я расскажу чуть позже. Сейчас же, после очень большой проделанной работы (кстати, ещё не до конца) по созданию универсального способа разделять один и тот же ассемблерный код между разными компиляторами, позволю себе похоливарить.

Я не доверяю коду, который сгенерировал компилятор, до тех пор, пока не посмотрю его листинг. В Open Watcom листинг объектного файла можно получить при помощи утилиты wdis:
Листинг 1

Inline assembly: GCC + Watcom.

Апрель 8th, 2009

Задумался о кросс-компиляции моего ядрышка GCC (сейчас пока компилируется только Watcom’ом).

Первый большой и краеугольный камень — это, конечно, ассемблерные вставки. Поэтому был придуман механизм, чтобы минимизировать писанину и дублирование ассемблерного кода для обоих компиляторов. С этой целью я сделал некий заголовочный файл, в котором объявил:

Хитрый код…

Hand-made синхронизация репозиториев Subversion

Март 29th, 2009

Несмотря на то, что репозиторий ОС XSystem мигрировал ко мне на домашний сервер, всё же хорошо было бы хранить бэкапы на каком-нибудь удалённом сервере.
Для этого я решил воспользоваться уже имеющимся репозиторием subversion на http://sourceforge.net/.

Идея работы такая: раз в сутки мой репозиторий должен синхронизироваться с удалённым репозиторием. При этом, все изменения в одном репозитории должны однозначно отражаться на другом. С версии subversion 1.4 появилась такая тулза, как svnsync, но она для моего случая не подходит: оба репозитория не предоставляют прямого доступа к svnroot.

Поэтому, немного порывшись в гугле, решил прибегнуть к собственному механизму синхронизации. Идея простая: раз в сутки сливается содержимое первого и второго (будем называть source и destination) репозитория. После этого сверяем содержимое source-репозитория с содержимым destination-репозитория: создаём несуществующие каталоги и копируем несуществующие файлы. Файлы, имеющие различные контрольные суммы md5, также перезаписываем. Но это не всё. После того, как мы влили новое файло в локальное дерево destination-репозитория, мы должны удалить из него те файлы, которых уже нет в source-репозитории. Для этого осуществляем обратную сверку снимка destination-репозитория с source-репозиторием и удаляем из него лишние файлы.

В результате всё это было сведено к скрипту на PERL.

#!/usr/bin/perl

use strict;

my @blacklist   =
(
    qr(^\.svn|\/\.svn$),
    qr(^\.{1,2}$|\/\.{1,2}$)
);

my $src_path  = 'xsystem';
my $dst_path  = 'xskernel-sync';
my $svn_user  = '';
my $svn_pass  = '';

# Update repositories
`svn update $src_path`;
`svn update $dst_path`;

# now search files in src_path and compare to dst_path

add_files();
remove_files();

`svn commit $dst_path -m "Synchronization commit" --username $svn_user --password $svn_pass`;

Как видно, работа скрипта достаточно примитивна. Для его работы нужно иметь два рабочих снимка репозитория: source и destination. У меня source-репозиторий находится в каталоге xsystem, а destination — в каталоге dst_path.
Скрипт сначала обновляет снимки репозиториев, затем осуществляет вливание новых файлов в destination-репозиторий при помощи функции add_files(). После этого удаляются устаревшие файлы и каталоги из destination-репозитория функцией remove_files() и производится коммит изменений в destination-репозиторий.

Дело осталось за малым — разобрать функции добавления и удаления файлов и каталогов. Для этого сначала напишем функцию, которая получает md5sum файла:

sub md5sum
{
    my $fname = shift;
    if (open PIPE, "md5sum $fname |")
    {
        my $line =
;
        close PIPE;
        my ($sum) = ($line =~ /^(\w+)\s+/o);
        return $sum;
    }
    return undef;
}

В принципе, ничего нового. Вызывается утилита md5sum и анализируется её вывод.

Также необходимо игнорировать каталоги ".svn", "." и "..", для чего вводится массив @blacklist и пишется функция банинга файлов:

sub ban_file
{
    my $src_file = shift;
    foreach (@blacklist)
    {
        ($src_file =~ $_) and
            return 1;
    }
    return undef;
}

После этого можно спокойно разобрать функцию add_files():


sub add_files
{
    my @directories = ();
    my $curr_dir = '';

    do
    {
        # Открываем каталог
        if (opendir DIRHDL, "$src_path$curr_dir")
        {
            CYCLE: # Читаем содержимое каталога
            while (my $fname = readdir DIRHDL)
            {
                # Баним ненужные файлы
                my $src_file = "$src_path$curr_dir/$fname";
                (ban_file($src_file)) and
                    next CYCLE;

                my $dst_short = "$curr_dir/$fname";
                my $dst_file  = "$dst_path$dst_short";

                # Файл является каталогом?
                if (-d $src_file)
                {
                    # необходимо проверить, что он есть в destination-репозитории
                    unless (-d $dst_file)
                    {
                        # если каталога нет - его нужно создать
                        print "mkdir   $dst_short\n";
                        `mkdir -p $dst_file`;
                        `svn add $dst_file`;
                    }

                    # Запомним каталог для того, чтобы в будущем его просмотреть
                    push @directories, $dst_short;
                }
                else
                {
                    # проверяем, существует ли файл в destination-репозитории
                    unless (-e $dst_file)
                    {
                        # файл не существует, его нужно скопировать и добавить
                        print "add     $dst_short\n";
                        `cp -f $src_file $dst_file`;
                        `svn add $dst_file`;
                    }
                    else
                    {
                        # файл существует, вычисляем md5sum обоих файлов
                        my $sum1 = md5sum($src_file);
                        my $sum2 = md5sum($dst_file);

                        # если суммы не совпадают - заменяем файл новым
                        if ($sum1 ne $sum2)
                        {
                            print "replace $dst_short\n";
                            `cp -f $src_file $dst_file`;
                        }
                    }
                }
            }
        }
        else
        {
            print "Can't open dir $src_path$curr_dir\n";
        }

        # закрываем каталог и получаем следующий каталог, который следует обработать
        closedir DIRHDL;
        $curr_dir = shift @directories;
    }
    while (defined $curr_dir); # крутимся, пока в списке присутствуют обрабатываемые каталоги.
}

При удалении функция будет очень похожа, только теперь надо осуществлять поиск файлов в destination-репозитории и смотреть, есть ли они в source-репозитории:

sub remove_files
{
    my @directories = ();
    my $curr_dir = '';

    do
    {
        # опять же, открываем каталог destination-репозитория
        if (opendir DIRHDL, "$dst_path$curr_dir")
        {
            CYCLE: # читаем файлы
            while (my $fname = readdir DIRHDL)
            {
                # баним недопустимые diren'ы
                my $src_file = "$dst_path$curr_dir/$fname";
                (ban_file($src_file))
                    and next CYCLE;

                my $src_short = "$curr_dir/$fname";
                my $dst_file  = "$src_path$src_short";

                # проверяем, является ли это каталогом
                if (-d $src_file)
                {
                    # проверяем, существует ли этот каталог в source-репозитории
                    unless (-d $dst_file)
                    {
                        # каталога нет - удаляем его из destination-репозитория
                        print "rmdir   $src_short\n";
                        `svn delete $src_file`;
                    }
                    else
                    {
                        # каталог существует, запоминаем его для дальнейшей обработки
                        push @directories, $src_short;
                    }
                }
                else
                {
                    # Это обычный файл, проверяем, есть ли он в source-репозитории
                    unless (-e $dst_file)
                    {
                        # Файла нет, удаляем его из destination-репозитория
                        print "unlink  $src_short\n";
                        `svn delete $src_file`;
                    }
                }
            }
        }
        else
        {
            print "Can't open dir $dst_path$curr_dir\n";
        }

        # Закрываем каталог, получаем следующий
        closedir DIRHDL;
        $curr_dir = shift @directories;
    }
    while (defined $curr_dir);
}

Недостаток этой тулзы один: если файл был перемещён, то он будет распознан как новый файл. Хотя, я не думаю, что файлы и каталоги так часто перемещаются в логически корректно построенном дереве проекта.

Статистика.

Январь 11th, 2009

Стремление товарища mar1ner  наблюдать за поисковыми запросами также сподвигло меня на идею написания скрипта, который составлял бы суточную статистику переходов по поисковым запросам на мой сервер. Скрипт запускается в час ночи по локальному времени (cron) и собирает информацию за прошедшие сутки. Запуск в час ночи сделал с поправкой на переход с летнего времени на зимнее и обратно ;) , на всякий пожарный.

Собственно, сам скрипт выглядит так:
Пара страничек кода…

И снова негодование!

Ноябрь 3rd, 2008

Вот решил тут небольшую «фенечку» к ядру прицепить:
FREQ на форуме

При конвертации BMP -> C++ обнаружил то, что MS хранит BMP-файлы в перевёрнутом виде. То есть, если бы нулевые координаты располагались в левом нижнем углу экрана (как принято в геометрии), а не в левом верхнем (как принято в компьютерной графике).

Зачем это сделано? MS опять выпендривается?

А развитие идёт дальше…

Ноябрь 3rd, 2008

Выпущен новый релиз ОС XSystem — October 2008 Fishes: Carp.
Основные нововведения:
- Из дерева проекта удалены утилиты ‘xarch’ и ‘fontcut’.
- Полностью переписан планировщик (теперь более быстрый и надёжный).
- Блочный распределитель памяти теперь выделяет блоки с адресом, кратным 8 байтам.
- Исправлены ошибки в контроллере клавиатуры (теперь работает в Bochs).
- Оптимизации реализации библиотеки <string.h>.
- Частично перенесён код Watcom C++ Runtime Library, необходимый для использования C++ — конструкций.
- Изменены сборочные скрипты.
- Кодовые страницы перемещены в ‘media/share/codepages’.
- Изменён метод ‘for_file’ в утилите ‘xsmake’.
- Большинство архитектурно-зависимого кода вынесено в ветку ‘include/arch’ ядра.
- Написан прототип будущего механизма подкачки виртуальной памяти.
- Добавлена поддержка записи конфигурационного пространства шины PCI (экспериментальное).
- Реализована поддержка загрузки/сохранения контекстов FPU/MMX/SSE при переключении задач.
- Добавлена защита от ошибочного прерывания со стороны PIC.
- Доступна загрузка с USB Flash Drive.
- Первичный загрузчик (‘bootload’) полностью переписан для поддержки файловых систем FAT12 и FAT16.
- Вторичный загрузчик ‘xload’ переписан на C++.
- Добавлены функции ‘unlink’, ‘cp’ в утилите ‘xsmake’.
- Добавлена условная конструкция ‘if-else’ в утилиту ‘xsmake’.
- Добавлена проверка зависимостей в OMF-файлах утилитой ‘xsmake’.
- Переписана утилита ‘rawmake’ (поддержка создания образов FAT12 и FAT16-дисков).
- Утилиты ‘xsmake’, ‘exe2bin’ и ‘rawmake’ теперь также можно собрать с помощью GNU GCC под Linux.

Странно…

Октябрь 5th, 2008

Уже где-то вторую или третью неделю непроизвольно соблюдаю правило «ни дня без коммита».

Хм… К чему бы это? Наверное, к новому релизу…

Написал статейку на WIKI про планировщик потоков:

http://wiki.xskernel.org/doku.php/xskernel/ipc/scheduler

Новый планировщик пофиксил много неприятных багов и корявостей в ядре. И (о чудо!), казалось бы, для более сложной реализации планировщика новая версия работает на порядок быстрее старой.

А программер ли ты?

Сентябрь 28th, 2008

Вот такая незатейливая игрушка на логику. Прошёл её за 181 команду. Говорят, можно меньше. Но сама идея понравилась очень.

http://www.poparcade.net/swf/light-bot-2205.swf

Первый патч в Open Source-проекте.

Сентябрь 10th, 2008

Сделал первый патч для проекта OpenWatcom.
Пофиксил баги в утилите exe2bin, без которой дальше не мог писать вторичный загрузчик. Ну, заодно, и добавил пару нужных лично мне фич. Баг был серьёзный — buffer overflow, связан с тем, что линкер помещает в relocation table записи в неотсортированном порядке.

Целый день потратил на поиск ошибки. Открыл баг, выложил патч, жду подтверждения…

Баг + патч