Смешиваем цвета правильно или оптимизируем AlphaBlend

Скорее всего вы знаете эту теорию, поэтому я не буду расписывать ее подробно, отмечу только основные моменты.

Итак, у нас есть 2 пикселя — исходный и пиксель назначения. Их нужно смешать и получить новый пиксель назначения. Каждый пиксель представлен 4-мя байтами A,R,G,B, где A — значение (не)прозрачности пикселя (0 — полностью прозрачный, 255 — полностью непрозрачный), RGB — цветовые компоненты. Классическая формула смешивания такова:

Важный момент! Единица — это в формуле. В жизни у нас за единицу выступает значение 255. Т.е. чтобы применять формулу, мы должны предварительно разделить значение каждого байта на 255. Как не трудно заметить, 255 и 256 — довольно близкие значения, а деление на 256 — это всего лишь сдвиг вправо на 8 бит. Поэтому часто встречается такое упрощение: вместо операции

делают следующее: Это работает неплохо (а главное, значительно быстрее честного деления), но, в случае альфа смешивания результат не вполне корректный, а именно, результирующий пиксель получается немного темнее. Далее, я покажу, как можно выполнить вычисления точно и без потери в скорости работы.

Другой важный момент! Посмотрите на формулу. Во второй части есть SRC_COLOR * SRC_ALPHA. Такое умножение 3D акселераторы выполняют миллионами и даже миллиардами, не моргнув глазом. Но мы то пытаемся решить задачу, используя центральный процессор, и лишнее умножение (точнее 4 лишних умножения) на каждый пиксель — это не очень хорошо. Почему лишнее? Да потому что это умножение можно сделать заранее, преобразовав исходную картинку. У таких изображений даже название есть: premultiplied. Я не знаю термина в русском языке, но переведя дословно получим «предумноженные». И точно, GDI функция AlphaBlend требует в качестве исходного изображения строго premultiplied. Это разумно.

Что ж, с теорией закончили. На практике будем работать с 32-битным цветом. Один пиксель представлен 32-битным числом, в котором 4 байта, начиная с младшего, означают: B(lue), G(reen), R(ed), A(lpha). Поехали.

Моя первая реализация была такой:

Согласен, выглядит не очень. 4 вещественных (точнее 5) умножения и 4 округления на каждый пиксель — это чересчур. Неудивительно, что по скорости этот монстр проигрывал AlphaBlend'у примерно в 7 раз.

Попробуем улучшить. Избавимся от вещественных умножений.

Здесь функции BLUEx256, GREENx256, и т.п. возвращают соответствующую компоненту, сдвинутую влево на 8 бит, т.е. умноженную на 256.

Эта функция примечательна тем, что в ней имеется компенсация замены деления на 255 сдвигом на 8 бит вправо. Заметили? Если нет, потерпите, ниже я опишу этот момент подробнее.

По скорости эта реализация уступает AlphaBlend'у примерно в 3 раза. Уже лучше, но все еще очень далеко от идеала.

Как можно улучшить предыдущую функцию? Кажется, мы сделали все что можно. Однако, у меня получилось улучшить эту функцию способом, который стал для меня сюрпризом. Я и попробовал его просто чтобы убедиться, что ничего не получится. Однако, получилось. Что если вынести операцию умножения байта на байт в таблицу. Получится не очень много — всего 65536 байт. Копейки.

Заводим такую табличку:

Удивительно, но эта функция работала в полтора раза быстрее предыдущей реализации. Правда есть одна тонкость — компилятор (в моем случае это был msvc 2013) очень грамотно сработал в операциях работы с памятью. Когда я попытался написать эту функцию на голом ассемблере, сделав, как мне казалось, все гораздо лучше оптимизатора, я получил функцию, которая работала в два раза медленнее этой. Это был провал. Я не стал разбираться, в чем конкретно я ошибся — очевидно мне не удалось грамотно распараллелить все операции — я просто оставил эту функцию на откуп оптимизатору.

Итак. Тут больше нечего оптимизировать. Мне не приходит в голову больше ничего. Но AlphaBlend все еще быстрее, раза в два. Как они этого добились? Кажется, пора на пенсию?

Есть много способов быстрого деления на 255. Мне встречался такой:

Это неплохо. Это быстрее честного деления на 255. Но это все еще слишком громоздко. Я долго думал, как быстро разделить на 255 и не потерять ни в качестве ни в скорости. Как компенсировать деградацию цвета при использовании сдвига?

Допустим, у нас есть цветовая компонента, равная 0xff (255) и у нас есть другая компонента, тоже равная 0xff (255). Перемножая их, мы получаем:

0xff * 0xff = 0xfe01. Сдвинув на 8 бит вправо, получим 0xfe — яркость компоненты уменьшена. Плохо. А что, если мы одну из компонент увеличим на 1 перед умножением? 0xff * 0x100 = 0xff00. Хм, кажется это оно. Проверим случай, когда одна из компонент равна 0: 0xff * 1 = 0x00ff, сдвигаем вправо на 8 бит, получаем 0. Вуаля! При других значених компонент результат также будет верным. Теперь легко найти место компенсации во второй функции: uint not_a = 256 — ALPHA(src); Не 255 — A, а 256 — A, т.е. +1 к компоненте перед умножением. Для табличного метода умножения компенсация не требуется, т.к. в таблице все значения и так посчитаны как нужно.

Пора задуматься об оптимизации с использованием simd. Говорят, компилятор Intel умеет это делать и без участия человека. Возможно. Но гложат меня сомнения, что Intel совладает с AlphaBlend'ом. Ну максимум — сравняется с ней. Но мне то нужно сделать быстрее. Открываем справочник и вперед.

Первый вопрос, которым следует задаться — под какие инструкции делать оптимизации? У меня есть подозрение, что AlphaBlend оптимизирована под MMX, иначе я не могу объяснить ее превосходства над чистой x86 реализацией. MMX — это хорошо, но это прошлый век. Сейчас трудно найти компьютер, где бы не было поддержки SSE4. А под SSE вообще можно оптимизировать, даже не утруждая себя проверкой на наличие поддержки этих инструкций — вероятность, что твоя программа будет запущена на чем-то ниже Pentium 3 близка к нулю. Я, конечно же, веду речь о desktop приложениях. Экзотика вне рамок этой статьи.

Я остановил свой выбор на SSSE3. Этот набор инструкций достаточно распространен, чтобы заморочиться оптимизацией именно под него, учитывая наличие в нем очень очень удобных инструкций.

Самая же полезная инструкция, которая и ляжет в основу всех оптимизаций — это pshufb (интринсик _mm_shuffle_epi8). Именно ради нее и выбран SSSE3. В чем же ее сила? В том, что эта инструкция позволяет раскидать байты исходного 16-байтового регистра в любом произвольном порядке или вообще выкинуть эти байты за ненадобностью. Т.е. я могу с помощью этой инструкции в одно движение подготавливать всё необходимое для нужных расчетов. Другая важная инструкция — pmulhuw (интринсик _mm_mulhi_epu16) — это 8 умножений и 8 сдвигов вправо на 16 бит. Как будто специально для операции альфа смешивания. Т.е. одной этой командой я фактически вычисляю сразу 2 пикселя.

Ну чтож, поехали:

Как видно, simd реализация смешивает сразу 4 исходных пикселя с 4-мя пикселями назначения. Ну на то она и simd. За кадром рамками этой статьи оставлю описание решения проблемы, когда требуется смешать не кратное 4-м количество пикселей. Лично я применяю для этого «однопиксельные» вызовы c++ реализации.

В итоге данная ssse3 реализация работает почти в 4 раза быстрее (в 3.78 на моем железе), чем функция AlphaBlend. Это весьма неплохой результат. Многие программисты (и я в том числе) скептически относятся к подобным «велосипедам». Как правило, результат получается заведомо хуже, чем труд коллектива высококлассных специалистов. Я взялся за написание своей реализации AlphaBlend функции не веря в то, что смогу победить ребят из майкрософта. Это был просто спортивный интерес, который, тем не менее, дал результат.

Но и это не всё. Дело в том, что в этой статье я привел код простого случая — когда исходная картинка смешивается с результирующей как есть. Но если вы читали документацию к функции AlphaBlend, то могли заметить, что эта функция умеет делать дополнительное умножение на константную альфу (передается через параметры). Я написал ssse3 реализацию и для этого случая. Интересен результат: AlphaBlend работает почти в 2 раза медленнее, если константная альфа не равна 255, т.е. требуется дополнительное умножение цвета. Моя же реализация деградирует в скорости всего на 4%, что тоже выгодно отличает ее от творения майкрософта.

Код в статье приведен только для ознакомления с самим принципом ssse3 оптимизации. Я не стал тут приводить значение используемых констант. Если вы захотите использовать оптимизированный AlphaBlend в своем проекте, вам придется добыть рабочий код непосредственно из исходных текстов Isotoxin'а (так называется моя разработка).

Репозиторий Isotoxin'а на гитхабе. Непосредственно файл, в котором находится нужная функция тут.

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