Парсинг метаданных файлов MO3 на Ассемблере

Нашел тут в закромах еще один формат трекерной музыки - MO3 (MOdule with MP3) за авторством известного Ian Luck, написавшего музыкальную библиотеку BASS. Вроде бы логично было добавить его в общий список трекерной музыки. Но в процессе исследования выяснились некоторые подробности, которые, я считаю, достойны отдельной статьи. Дело в том, что все данные, в том числе и заголовок, в котором содержится название композиции, упакованы по алгоритму LZ (Lempel-Ziv). Соответственно, чтобы их получить, требуется сперва этот заголовок распаковать. Вот этим и займемся.

Читать статью целиком »

Эффект пламени на Ассемблере

Классический эффект горящего пламени используется в различных интро и демонстрашках еще со времен MS-DOS, а может быть и раньше. Алгоритм достаточно простой, но при этом выглядит очень красиво. Суть его заключается в следующем. Сперва создается палитра, в ней должны быть только оттенки белого, желтого, красного и черный цвет. Далее создается массив, который соответствует размеру изображения и содержит значения цветов его пикселов. По нижней строчке записываются в случайном порядке пикселы или пропуски, после этого по таймеру запускается основной цикл обработки.

Читать статью целиком »

Парсинг метаданных файлов MPEG-4 на Ассемблере

Формат MPEG-4 появился еще в 1998 году и включает в себя группу стандартов сжатия цифрового аудио и видео. Это могут быть аудиофайлы M4A и ALAC, видеоролики MP4 и M4V, видео с YouTube M4S, рингтоны для гейфонов M4R, защищенные аудиозаписи iTunes M4P, аудиокниги M4B и, возможно, другие. За счет контейнерной структуры этот формат позволяет хранить внутри файлов не только аудио- и видео-потоки, но и шрифты, 3D-объекты, субтитры, статичные изображения и т.п. Сегодня разберем, как можно извлечь из этих файлов метаданные.

Читать статью целиком »

Поиск подстроки в строке по алгоритму Кнута-Морриса-Пратта

Алгоритм Кнута-Морриса-Пратта, он же классический "КМП-алгоритм" - один из самых эффективных алгоритмов поиска подстроки в строке. Оптимизация достигается за счет того, что при возникновении несоответствия само искомое слово содержит достаточно информации, чтобы определить, где может начаться следующее совпадение, минуя лишние проверки. Скорость работы алгоритма линейно зависит от объема входных данных, то есть невозможно разработать более эффективный алгоритм с точки зрения вычислительной сложности.

Читать статью целиком »

Сортировка перемешиванием на Ассемблере

Сортировка перемешиванием, она же шейкерная или двунаправленная сортировка - оптимизированная разновидность алгоритма пузырьковой сортировки. В процессе сортировки выполняется многократный проход по массиву, соседние элементы сравниваются и, в случае необходимости, меняются местами. Массив просматривается поочередно справа налево и слева направо, из-за этого алгоритм получил свое название. В результате каждого прогона крупные и мелкие элементы массива поочередно перемещаются в конец и начало массива соответственно. Границы рабочей части массива, то есть той части массива, где происходит движение, устанавливаются в месте последнего обмена на каждой итерации.Как и с любыми другими разновидностями пузырьковой сортировки, время выполнения сильно зависит от упорядоченности исходного массива и от количества элементов в нем. Но в любом случае при сортировке перемешиванием сумма сравнений одинакова с пузырьковой сортировкой, а сумма обменов меньше.

Читать статью целиком »