Я пишу мультипротокольный (но не мультиплатформенный, увы, сейчас только windows) мессенджер, который пока что поддерживает только протокол TOX. Но речь не о мессенджере, а о его интерфейсе, а если точнее, об основной его функции — AlphaBlend. Да, я решил написать свой велосипед GUI. Ну а какой современный GUI без полупрозрачных элементов и плавных закруглений? Поэтому остро встала необходимость смешивать изображения с учетом полупрозрачности, т.е. альфа-смешивание или alpha blending. К счастью, в windows GDI такая функция имеется — AlphaBlend. Работает как надо, делает то что нужно. Но я тот еще строитель велосипедов, и мне стало интересно, смогу ли я написать такую же функцию, но более быструю. Результат моих трудов под катом.

Теория альфа смешивания

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

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

TGT_COLOR = TGT_COLOR * (1 - SRC_ALPHA) + SRC_COLOR * SRC_ALPHA

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

(X) * (A/255.0)

делают следующее:

 (X * A) >> 8

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

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

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

Первая реализация

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

uint32 ALPHABLEND_PM(uint32 dst, uint32 src)
{
    uint8 ba = ALPHA(src);				// функция ALPHA возвращает старший байт 32-битного числа
    if (ba == 0) return dst;				// альфа == 0, значит другие компоненты тоже == 0, значит делать ничего не надо
    float a = (float)((double)(ba)* (1.0 / 255.0));	// просто я люблю все делать в даблах :)
    float not_a = 1.0f - a;				// но иногда признаю: флоатов достаточно

    uint B = lround(float(BLUE(dst)) * not_a) + BLUE(src);	// функция BLUE возвращает 0-й байт 32-битного числа
    uint G = lround(float(GREEN(dst)) * not_a) + GREEN(src);	// функция GREEN возвращает 1-й байт 32-битного числа
    uint R = lround(float(RED(dst)) * not_a) + RED(src);	// функция RED возвращает 2-й байт 32-битного числа
    uint A = lround(float(ALPHA(dst)) * not_a) + ALPHA(src);

    return B | (G << 8) | (R << 16) | (A << 24);	// собрали 32-битный пиксель из запчастей
}

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

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

uint32 ALPHABLEND_PM(uint32 dst, uint32 src)
{
    uint not_a = 256 - ALPHA(src);
    return = src + (((not_a * BLUEx256(dst))>>16) |
                   (((not_a * GREENx256(dst))>>8) & 0xff00) |
                   (((not_a * REDx256(dst))) & 0xff0000) |
                   (((not_a * ALPHAx256(dst))<<8) & 0xff000000));
}

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

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

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

Неожиданный результат

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

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

uint8 __declspec(align(256)) multbl[256][256];

Заполняем:

for (int i = 0; i < 256; ++i)
    for (int j = 0; j < 256; ++j) {
        int k = i * j / 255;
        multbl[i][j] = (uint8)k;
    }

Пробуем:

uint32 ALPHABLEND_PM(uint32 dst, uint32 src)
{
    uint8 not_a = 255 - ALPHA(src);
    return src + ((multbl[not_a][dst & 0xff]) |
                (((uint)multbl[not_a][(dst >> 8) & 0xff]) << 8) |
                (((uint)multbl[not_a][(dst >> 16) & 0xff]) << 16) |
                (((uint)multbl[not_a][(dst >> 24) & 0xff]) << 24));
}

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

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

О компенсации замены деления на 255 сдвигом

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

X/255 == (X+1+(X>>8)) >> 8

Это неплохо. Это быстрее честного деления на 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 к компоненте перед умножением. Для табличного метода умножения компенсация не требуется, т.к. в таблице все значения и так посчитаны как нужно.

Тяжелая артилерия — инструкции SSSE3

Пора задуматься об оптимизации с использованием 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'а на гитхабе.
Непосредственно файл, в котором находится нужная функция тут.

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