Оптимизация декодера изображений для 6502 с 70 минут до одной

Когда я решил написать программу для простой цифровой фотосъёмки на Apple II, то думал использовать камеры Quicktake. Выбор казался очевидным, потому что это были камеры Apple, способный подключаться к компьютеру через последовательный порт.

Объём задачи немного расширился, когда мне удалось декодировать фотографии Quicktake 100: захотелось научиться декодировать фотографии Quicktake 150 и Quicktake 200. Из-за этого пришлось погрузиться в тему обработки изображений глубже, чем мне хотелось изначально. В этой статье я расскажу о том, как мне удалось заставить работать декодер Quicktake 150 с достаточно приемлемой скоростью на процессоре 6502 с частотой 1 МГц.

Формат Quicktake 150 проприетарный и не имеет документации, однако в проекте dcraw существуют свободные программные декодеры. Они стали моим фундаментом для создания первого декодера на Apple II. К сожалению, они написаны на C, крайне плохо задокументированы и чрезвычайно непонятны (для меня). Сжатие выполняется при помощи кода Хаффмана с переменной длиной (то есть используется битовый сдвиг), а для воссоздания изображения требуется большой объём 16-битных вычислений. Со всем этим 6502 справляется плохо.

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

Разумеется, процесс был не скорым. Первую свою реализацию я выпустил два года назад, в ноябре 2023 года. Кажется, для её создания мне потребовалось пять-шесть глубоких погружений в тему; при этом каждый раз это были одна-две недели борьбы с сотнями или тысячами отладочных printf(), gdb, сравнений переменных и смещений по вечерам и полным выходным.

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

Я заметил, что ручная оптимизация ассемблерного кода даёт хорошие результаты, однако обычно к гораздо более впечатляющему росту скорости приводит оптимизация самого алгоритма. Ускорение слишком большого количества операций не столь оптимально, как ускорение минимально необходимого. А исходный декодер Quicktake 150 совершенно точно выполнял бесполезные операции, особенно в моём случае, когда цвет не требовался, а изображение должно было иметь размер 256×192!

Я создал отдельный репозиторий для отслеживания этих изменений в алгоритме. Изначальная версия ^[1] (уже немного деобфусцированная по сравнению с dcraw ^[2]) содержала 301 миллионов команд x86_64.

Избавляемся от цвета

Мне не нужно было декодировать цвет, потому что я всё равно собирался от него избавиться. Я добавил флаг, позволяющий декодировать из фильтра Байера только зелёные пиксели, а остальные игнорировал ^[3]. 264 миллиона команд.

Разбираемся с буферами

Затем я решил разобраться, для чего используются различные временные буферы: чем больше буферов, тем больше промежуточных этапов и тем больше копирования и циклов. Мне нужно было избавиться от как можно большего их количества. Первым шагом стало развёртывание чередующихся циклов, работавших с y [1,2], x [col+1,col]. ^[4] 238 миллионов команд.

Я понял, что всё равно остаётся дополнительная обработка, которая мне не нужна, избавился от неё и от буфера ^[5] (а также от #ifdef COLOR, чтобы код был чище). 193 миллиона команд.

На этом этапе моя реализация выводила зелёные пиксели только в фильтре Байера в буфер 640×480, а затем интерполировала их. Это было бесполезно, поэтому я полностью от этого отказался ^[6]. 29 миллионов команд.

Половина пикселей в конечном буфере по-прежнему оставалась чёрной, поэтому я начал избавляться от них раньше, выводя изображения 320×240 только с релевантными пикселями ^[7]. 25 миллионов команд.

Теперь я уже смог разобраться, что из трёх buf_m[3] для воссоздания изображения использовался только buf_m[1] ^[8], что buf_m[2] нужен только для передачи данных в buf_m[0] в начале строки ^[9], что можно воссоздавать изображение из значений buf_m[1] «на лету» вместо выполнения дополнительного цикла ^[10] и что от этого тоже можно полностью отказаться ^[11]. Это позволило мне переименовать последний оставшийся буфер для большей понятности ^[12]. 22 миллиона команд.

Оптимизация делений

Итак, с буферами я разобрался. На этом этапе благодаря переделке кода стало очевидно, что каждый пиксель конечного изображения вычисляется делением 16-битных значений, вычисленных из данных изображения, на заданный коэффициент, и что этот коэффициент меняется с частотой максимум в две строки. Результат этого деления ограничивался интервалом [0-255]. Это позволило мне предварительно вычислять таблицу делений каждые две строки и сохранять окончательный результат в простой массив ^[13]. При этом снижалась точность вычислений, но это было незаметно. На x86_64 команд по-прежнему осталось 22 миллионов, но на 6502 прогресс получился существенным: 153600 делений превратились в менее, чем 2000.

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

Индексация вывода

Раньше мы записывали буфер вывода при помощи способа доступа buffer[y*ШИРИНА+x], который выполняется очень медленно на процессоре без поддержки умножения. Я заменил его на гораздо более простую построковую индексацию ^[14]. (Даже на x86_64 изменение было заметным: 20 миллионов команд).

Декодирование Хаффмана

Алгоритм инициализировал таблицы целиком, чтобы можно было получить код Хаффмана, просто взглянув на битовый буфер: например, для кода 10001 правильному значению соответствовали все коды от 10001000 до 10001111, после чего битовый буфер выполнял сдвиг <<5. Поначалу это казалось хорошей идеей, но не на 6502, потому что необходимы 16-битные битовые буферы, чтобы мы точно всегда рассматривали байт целиком. Я переписал этот код так, чтобы биты брались по одному ^[15]. Из-за этого реализация на x86_64 стала медленнее, но на 6502 она стала на двадцать секунд быстрее: на сдвиг битов стало тратиться 9 секунд вместо 29. Также это позволило мне более плотно упаковывать таблицы, освободив часть памяти для кэша.

Ассемблерный код

При компиляции cc65 этот алгоритм ^[16] всё равно имеет очень низкую производительность, но его гораздо проще транслировать в оптимизированный ассемблерный код 6502. В нём есть много ручных оптимизаций, например:

• У всех протестированных мной изображений коэффициент деления окончательных значений пикселя для пары строк в более 50% случаев равен 48. Поэтому в реализации для 6502 есть две таблицы поиска делений, и таблица для коэффициента 48 никогда не вычисляется повторно, а таблица для другого коэффициента по необходимости повторно вычисляется в начале пары строк.

• Инициализация строки умножает все 320 значений next_line на коэффициент, который в более чем 66% случаев равен 255. В этом случае, вместо умножения a = a*255 ассемблерная версия выполняет (a*256)-a, то есть (a<<8)-a, что намного быстрее.

• В основном цикле (таблице поиска, основанной на ассемблерной реализации) часто выполняется <<4. <<4 больше восьми битов, поэтому требуется две страницы, но это всё равно оправдывает использование лишней памяти.

• Половина кодов Хаффмана отбрасывается (они используются для синих и красных пикселей), поэтому в этом случае вызываются функции-«отбраковщики», которые лишь смещают битовый буфер, не получая значение.

• Доступ к буферам (next_line и выходному буферу) патчится в самомодифицирующемся коде, а не задействует указатели нулевой страницы; для этого требуется отслеживать и патчить примерно 54 метока на каждом пересечении страницы. Это ужасно некрасиво, однако требует примерно 50 тысяч тактов, позволяя освободить суммарно 9 миллионов тактов.

Окончательный код

Выше я ссылался на свой «тестовый» репозиторий, но если вам интересна сама реализация для 6502, её можно найти в моём репозитории: декодер ^[17] и битовый буфер ^[18].

Оставшиеся вопросы

В декодере dcraw по-прежнему остаются непонятные мне моменты, не затронутые моими упрощениями. Во-первых, мне интересно, как вообще автор dcraw Дэйв Коффин реализовал этот декодер? В нём как будто полно «магических» чисел и арифметических операций; не представляю, как можно посмотреть на изображения на уровне битов и понять хоть что-то о формате. Дэйв выполнил реверс-инжиниринг двоичного файла Apple? У него была документация? Это какой-то распространённый тип кодирования, который мне неизвестен?

Мне бы хотелось прочитать документацию по этому формату, возможно, я бы понял больше и смог усовершенствовать код.

Бонус: видео первой и текущей реализаций

Текущая реализация

Первая реализация (наберитесь терпения)