Я пишу мультипротокольный (но не мультиплатформенный, увы, сейчас только 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 пикселя.
Ну чтож, поехали:
lddqu xmm5, [eax] ; загрузим в xmm5 16 байт, или 4 пикселя накладываемой premultiplied картинки
movdqa xmm6, xmm5 ; сохраним в xmm6 для работы со старшими 2-мя пикселями
; первый шаг: поготовка
; просто расширяем все компоненты входных пикселей до 16 бит на компоненту
pshufb xmm5, preparesrcs_1
pshufb xmm6, preparesrcs_2
; готово
; xmm5 содержит первые 2 пикселя, где каждой компоненте отведено 16 бит
; xmm6 содержит тоже для следующих 2 пикселей
; второй шаг: обработаем 2 из 4 пикселей
; но сначала нам нужно получить 8 16-битных значений (256-A)
; получим их в xmm7
movdqa xmm2, xmm5 ; скопируем первые 2 пикселя в xmm2
pshufb xmm2, preparealphas ; этой командой мы поставим альфа компоненты в нужные позиции: A0 A0 A0 A0 A1 A1 A1 A1
movdqa xmm7, sub256 ; в xmm7 загрузим 8 16-битных значений 256
psubw xmm7, xmm2 ; вычтем альфа компоненты
movdqu xmm0, [edx] ; 4 пикселя назначения
movdqa xmm1, xmm0 ; скопируем в xmm1 для шага 3
pshufb xmm0, preparetgtc_1 ; тут получаем 2 пикселя с 16-битными компонентами, сдвинутыми влево на 8
pmulhuw xmm0, xmm7 ; умножаем и получаем готовые 2 пикселя с 16-битными компонентами
paddw xmm0, xmm5 ; осталось добавить к ним предумноженный цвет исходного пикселя
pshufb xmm0, packcback_1 ; и упаковать в младшие 8 байт xmm0
; шаг три - тоже самое, что и шаг 2, но для следующих двух пикселей
movdqa xmm2, xmm6
pshufb xmm2, xmm3
movdqa xmm7, xmm4
psubw xmm7, xmm2
pshufb xmm1, preparetgtc_2
pmulhuw xmm1, xmm7
paddw xmm1, xmm6
pshufb xmm1, packcback_2
por xmm0, xmm1 ; итого в xmm0 4 готовых пикселя
movdqu [edx], xmm0 ; которые мы просто кладем обратно в память
Как видно, simd реализация смешивает сразу 4 исходных пикселя с 4-мя пикселями назначения. Ну на то она и simd. За кадром рамками этой статьи оставлю описание решения проблемы, когда требуется смешать не кратное 4-м количество пикселей. Лично я применяю для этого «однопиксельные» вызовы c++ реализации.
Итоги
В итоге данная ssse3 реализация работает почти в 4 раза быстрее (в 3.78 на моем железе), чем функция AlphaBlend. Это весьма неплохой результат. Многие программисты (и я в том числе) скептически относятся к подобным «велосипедам». Как правило, результат получается заведомо хуже, чем труд коллектива высококлассных специалистов. Я взялся за написание своей реализации AlphaBlend функции не веря в то, что смогу победить ребят из майкрософта. Это был просто спортивный интерес, который, тем не менее, дал результат.
Но и это не всё. Дело в том, что в этой статье я привел код простого случая — когда исходная картинка смешивается с результирующей как есть. Но если вы читали документацию к функции AlphaBlend, то могли заметить, что эта функция умеет делать дополнительное умножение на константную альфу (передается через параметры). Я написал ssse3 реализацию и для этого случая. Интересен результат: AlphaBlend работает почти в 2 раза медленнее, если константная альфа не равна 255, т.е. требуется дополнительное умножение цвета. Моя же реализация деградирует в скорости всего на 4%, что тоже выгодно отличает ее от творения майкрософта.
Ссылки
Код в статье приведен только для ознакомления с самим принципом ssse3 оптимизации. Я не стал тут приводить значение используемых констант. Если вы захотите использовать оптимизированный AlphaBlend в своем проекте, вам придется добыть рабочий код непосредственно из исходных текстов Isotoxin'а (так называется моя разработка).
Репозиторий Isotoxin'а на гитхабе.
Непосредственно файл, в котором находится нужная функция тут.
Прошу прощения, что не подготовил рабочие примеры и не вынес всё в отдельную библиотеку. Если вам действительно нужна эта функция, и вы испытываете затруднения в том, чтобы самостоятельно достать ее из моих исходников, напишите мне личное сообщение и я подробно расскажу вам, как это сделать.
Автор: isotoxin
