Когда я решил написать программу для простой цифровой фотосъёмки на 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!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

При компиляции cc65 этот алгоритм всё равно имеет очень низкую производительность, но его гораздо проще транслировать в оптимизированный ассемблерный код 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, её можно найти в моём репозитории: декодер и битовый буфер.

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

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

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

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

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

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