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

    Я пишу мультипротокольный (но не мультиплатформенный, увы, сейчас только 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 пикселя.

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

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

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

    Комментарии 21

      +4
      Я просто положу это здесь:

        –1
        В практической компьютерной графике просто огромное количество упрощений, и в видео рассказано лишь об одном из. Никакой Америки они не открыли.
          0
          Причем здесь Америка? Они рассказывают о конкретной проблеме, которой не существовало бы, если бы преобразование цветов делали по правилам и фактически по определению (про которое забыли).
            0
            Потому что это не баг, а сознательное упрощение.
            Кодирование-декодирование гаммы — это два возведения в степень, несколько умножений и сложений, причем в вещественных числах. На каждый пиксель. Даже сегодня это выглядит заметной нагрузкой, а лет 20 назад это был анриал полный.
            На это пошли сознательно, принеся в жертву немного качества в пользу колоссального ускорения. И, как я уже говорил, это далеко не еднственное подобное упрощение. Потому что если копать глубже, даже смешивание с учетом гаммы (как они описывают) тоже не вполне корректно, там нужно еще очень сильно наворачивать формулы. Настолько сильно, что в реалтайме не справятся даже современные компьютеры.
        0
        Я взялся за написание своей реализации AlphaBlend функции не веря в то, что смогу победить ребят из майкрософта. Это был просто спортивный интерес, который, тем не менее, дал результат.
        А вот это вы зря. «Ребята из майкрософта» (Apple, Google, Intel'а — выберите себе компанию по вкусу) могут, конечно, сделать версию, которая будет супер-пупер быстрой и классной — но у них уйдёт на это немало времени. А когда у вас есть тысячи других задач и десятки (или уже сотни?) миллионов строк кода, то до всего руки просто не доходят.

        Оптимизированы «до упора» только функции, которые нужны реально очень-очень большому проценту разработчиков и которые вызывают проблемы в реальных программах. Я думаю 90% (если не 99%) функций в Windows (Android, iOS — далее по вкусу) можно серьёзно ускорить.
          0
          Но ведь не на всех поддерживаемых Windows платформах есть SSE инструкции?
          Да и AlphaBlend вроде бы аппаратно ускорена… Не помню уже, BitBlt точно, имеются ввиду последние версии ОС.
            0
            В последних версиях ОС как раз всё тухло. Лет примерно 20 назад — да, всё выполнялось аппаратно. Cirrus Logic, S3 и прочие всякие Tridentы рулили. А потом — настала эпоха 3D, а на 2D разработчики малость подзабили потому как CPU стали достаточно быстрыми чтобы это не было проблемой. А код ведь старый, писался ещё до того, как MMX (не то, что SSE) появился — и таким он, скорее всего, и остался, так как никого особо не трогал (даже современные браузеры все свои эффекты не через GDI, а через DirectX рисуют!).
              0
              Не на всех. Там где нет ssse3, используется обычная c/c++ реализация. Вот только ssse3 появилась как минимум в Core 2 duo, т.е. охват этой ssse3 оптимизации по железу довольно неплох (если не сказать, 100%-й)
              > Да и AlphaBlend вроде бы аппаратно ускорена
              Возможно она ускорена, если работает с видеопамятью. При работе с обычным Memory DC — максимум mmx, и то не факт.
            0
            Ассемблер это очень замечательно, но рекомендую переписать с использованием интринсиков если хотите другие платформы и/или битность (x64 например).
            Кстати, иногда компилятор умудряется замечательно заоптимизировать интринсик-код давая фору даже «ручному» коду.
              0
              image
              Но как же… а начать с упрощения самой формулы?

              NewColor = DstColor * (1 - SrcAlpha) + SrcColor * SrcAlpha;
              NewColor = DstColor - DstColor * SrcAlpha + SrcColor * SrcAlpha;
              NewColor = DstColor + SrcAlpha * (SrcColor - DstColor);
              //после деления на 255:
              NewColor = (DC/255 + SA/255 * (SC/255 - DC/255))*255
              NewColor = (SC - DC) * SA/255 + DC
              

                0
                Это вы к тому, что можно работать с нормальным, не premultiplied цветом не увеличивая количество умножений? Да, это неплохой вариант. Но я не стал его рассматривать по трем причинам (3-я — основная):
                1. AlphaBlend меня уже приучил к premultiplied. Менять привычки бывает непросто.
                2. В сокращенной формуле, хоть и такое же количество умножений, как и при работе с premultiplied, однако, есть дополнительная операция вычитания, которая, к тому же, порождает отрицательные значения. Это требует дополнительных усилий.
                3. Путь оптимизации, предполагающий переход на premultiplied, затмил мой разум и я просто упустил этот момент из виду.

                Зато, если у меня возникнет необходимость написать AlphaBlend на нормальных пикселях, без предумножения, я сразу вспомню об этом упрощении и сделаю все как надо. За что вам спасибо.
                0
                Рекомендую посмотреть в сторону intrinsic-ов: это почти прямое отражение mmx, sse и avx инструкций на «сишные функции». В итоге компилятор занимается подбором регистров, упорядочиванием и выравниванием команд, а программист говорит, что именно делать. В качестве бонуса получается некая «переносимость», т. к. intrinsics, в отличие от inline assembler'а, в различных компиляторах.
                У Intel есть замечательный гайд: https://software.intel.com/sites/landingpage/IntrinsicsGuide/
                  0
                  Гайд прекрасный! Но вы не внимательны: в статье есть ссылка на этот гайд. Собственно, по нему я все и делал.
                  Что же касается использования интринсиков вместо голого асма — я не отвергаю интрисики — штука крайне полезная. Просто ассемблер… ну это как первая любовь. Неравнодушен я к нему. Я же и оптимизировал в основном из спортивного интереса. Несомненно, как только появится свободное время, я перепишу часть кода на интринсики. Да я в любом случае это сделаю, т.к. у меня в планах перейти на 64 бита.
                  С другой стороны, перенимая опыт разработчиков кодека VPx: там 64 битный код написан на интринсиках или вообще на C, а 32-битный — на ассемблере. Думаю поступить также.
                  –1
                  Пост хороший с точки зрения теории смешивания цветов. Но не могу не спросить, под какой Windows вы программируете, что там до сих пор есть необходимость работать с GDI? О_о
                    0
                    Хм… В любой?
                    Нативный(не wpf) интерфейс весь GDI рисуется, и если необходимо создать свой контрол, либо изменить проприсовку у стандартного необходимо использовать GDI.
                      0
                      Вы правильно заметили («если не WPF»), но вопрос не поняли. Если у вас Windows 7+ какой смысл в нативном интерфейсе и WinAPI, если есть WPF, есть C++/CLI (если не устраивает C#). Для меня единственной осмысленной причиной этого может быть поддержка Windows XP и ниже. Отсюда и вопрос.
                        0
                        Кстати да, XP я поддерживаю, причем приходится прилагать определенные усилия к этому. Например, первая версия с поддержкой видеозвонков не видела камеру под XP. Два дня убил, чтобы найти причину.
                        А вот qTox, кажется, отказался от поддержки XP. Не проверял, может и ошибаюсь, но что-то такое на эту тему видел в чате разработчиков Tox'а.
                          0
                          Смысл нативного интерфейса — в его нативности, WPF не всегда на 100% выглядит нативным, и к сожалению бывает привередлив к видеокартам, что приводит к тому что словить глюки отрисовки, и как не странно тормоза, в программах на древнем win32 GUI можно реже чем на WPF. В конце концов GDI потребляет меньше памяти.
                          Опять же большенство приложений, в том числе и системные, базируется на GDI-шной отрисовке.
                          Все технологии имеют свои недостатки, но часто отрисовка GDI бывает оправдана.
                        0
                        Я понимаю ваш вопрос. Действительно, существует огромное количество средств создать графический интерфейс у своего приложения, не работая с GDI напрямую. Однако вы должны понимать, что все эти средства так или иначе основаны на GDI, исключая, возможно, какие-то специальные разработки майкрософта, а также интерфейс, на основе 3D графики (в играх, например).
                        Так что я, сознательно отказавшись от всех этих средств (почему — отдельный вопрос), встал перед выбором: либо GDI, либо Direct3D (или OpenGL). Как показала практика, GDI вполне себе быстр и нет необходимости прибегать к мощностям GPU. Во всяком случае, решение этого вопроса я отложил на неопределенный срок.
                          0
                          Спасибо за ответ
                        +1
                        Решал эту задачу для разных платформ. Если интересно, есть исходники на GitHub для различных SIMD расширений: AVX2, SSE2, SSSE3, NEON (ARM) и Altivec (PowerPC).

                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                        Самое читаемое