- Alpha blending
- Источники и инструменты
- Благодарности
Смешение двух картинок: на фон наклаывается изображение с учётом его прозрачности
Несколько слов об этом формате (только важные для нас пункты):
- В начале находятся две структуры данных:
BITMAPFILEHEADER:type- сигнатура (должно быть "BM")size- размер всего файлаoffset- смещение массива пикселей от начала файла
BITMAPINFOHEADER:width- ширина картинки в пикселяхheight- высота картинки в пикселяхbit_count- количество бит на один пиксель (должно быть 32)compression- тип сжатия (без сжатия -0или3)
- После них могут лежать палитры цветов, их мы рассматривать не будем
- Массив пикселей начинается со смещения
offset - Гарантируется выравнивание каждой строки изображения по 4 байтам
Тестовые данные:
- две картинки разрешением
1020x720пикселей в форматеbmp. Каждый пиксель - 4 байтаbgra - за один запуск рассчитываются 1000 кадров
Параметры тестовой машины:
- Компилятор:
g++ (GCC) 13.2.1 20230801 - Уровень оптимизации:
O2 - Процессор:
Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz SkyLake - ОС:
Arch Linux, Kernel:6.6.22-1-lts (64-bit) - Профилировщик:
valgrind-3.22.0
Расчёт для одного пикселя:
for (...) {
uint8_t alpha = fore_pixel->a;
uint8_t rev_alpha = 255 - alpha;
back_pixel->b = (uint8_t)((fore_pixel->b * alpha + back_pixel->b * rev_alpha) / 255);
back_pixel->g = (uint8_t)((fore_pixel->g * alpha + back_pixel->g * rev_alpha) / 255);
back_pixel->r = (uint8_t)((fore_pixel->r * alpha + back_pixel->r * rev_alpha) / 255);
}
Расчёт двумя векторами по 4 пикселя (всего 8 за одну итерацию цикла):
for (...) {
// load pixels as 8-bit and extend them to 16-bit
__m256i fore1 = _mm256_cvtepu8_epi16(_mm_loadu_si128((__m128i*)(fore_pixel + 0)));
__m256i fore2 = _mm256_cvtepu8_epi16(_mm_loadu_si128((__m128i*)(fore_pixel + 4)));
__m256i back1 = _mm256_cvtepu8_epi16(_mm_loadu_si128((__m128i*)(back_pixel + 0)));
__m256i back2 = _mm256_cvtepu8_epi16(_mm_loadu_si128((__m128i*)(back_pixel + 4)));
// set alpha channel vector
__m256i alpha1 =
_mm256_set_epi16(0xFFFFu, (fore_pixel + 3)->a, (fore_pixel + 3)->a, (fore_pixel + 3)->a,
0xFFFFu, (fore_pixel + 2)->a, (fore_pixel + 2)->a, (fore_pixel + 2)->a,
0xFFFFu, (fore_pixel + 1)->a, (fore_pixel + 1)->a, (fore_pixel + 1)->a,
0xFFFFu, (fore_pixel + 0)->a, (fore_pixel + 0)->a, (fore_pixel + 0)->a);
__m256i alpha2 =
_mm256_set_epi16(0xFFFFu, (fore_pixel + 7)->a, (fore_pixel + 7)->a, (fore_pixel + 7)->a,
0xFFFFu, (fore_pixel + 6)->a, (fore_pixel + 6)->a, (fore_pixel + 6)->a,
0xFFFFu, (fore_pixel + 5)->a, (fore_pixel + 5)->a, (fore_pixel + 5)->a,
0xFFFFu, (fore_pixel + 4)->a, (fore_pixel + 4)->a, (fore_pixel + 4)->a);
// rev_alpha1 = 255 - alpha1
__m256i rev_alpha1 = _mm256_sub_epi16(_mm256_set1_epi16(255), alpha1);
__m256i rev_alpha2 = _mm256_sub_epi16(_mm256_set1_epi16(255), alpha2);
// sum1 = (fore1 * alpha1 + back1 * rev_alpha1)
__m256i sum1 = _mm256_add_epi16(_mm256_mullo_epi16(fore1, alpha1),
_mm256_mullo_epi16(back1, rev_alpha1));
__m256i sum2 = _mm256_add_epi16(_mm256_mullo_epi16(fore2, alpha2),
_mm256_mullo_epi16(back2, rev_alpha2));
// result1 = (fore1 * alpha1 + back1 * rev_alpha1) / 255
__m256i result1 = _mm256_div255_epi16(sum1);
__m256i result2 = _mm256_div255_epi16(sum2);
// result = {result1[left_half], result2[left_half], result1[right_half], result2[right_half]}
__m256i result = _mm256_packus_epi16(result1, result2);
// result = {result1, result2}
result = _mm256_permute4x64_epi64(result, 0b11'01'10'00);
_mm256_storeu_si256((__m256i*)back_pixel, result);
}
inline static __m256i _mm256_div255_epi16(__m256i a) {
// x / 255 = (x + 1 + (x >> 8)) >> 8
return _mm256_srli_epi16(_mm256_add_epi16(_mm256_add_epi16 (a, _mm256_set1_epi16(1)),
_mm256_srli_epi16(a, 8)),
8);
}
Интринсики _mm_load_si128 и _mm256_store_si256 быстрее _mm_loadu_si128 и _mm256_storeu_si256, но принимают только указатели с выравниваем по 32 байтам. Формат bmp его не гарантирует.
Выполним выравнивание при помощи memmove и сравним время выполнения.
uint32_t old_offset = file_header->offset;
file_header->offset += 32 - (uint32_t)(((size_t)file_buffer + file_header->offset) % 32);
memmove(file_buffer + file_header->offset, file_buffer + old_offset, size - old_offset);
Деление в точности на 255 требует 5 инструкций. А при помощи битового сдвига можно разделить на 256 всего за 1 инструкцию. Потеря точности незначительна при однократной обработке изображения и человек вряд ли заметит на глаз такое изменение цвета.
inline static __m256i _mm256_div255_epi16(__m256i a) {
// x / 256 = x >> 8
return _mm256_srli_epi16(a, 8);
}
| Оптимизация | Вся программа | Функция рендеринга | ||||
|---|---|---|---|---|---|---|
| Ir * 10^3 | % от base | % от предыдущего | Ir * 10^3 | % от base | % от предыдущего | |
| base | 24 981 149 | 100% | 24 981 133 | 100% | ||
| vector | 7 436 830 | 30% | 30% | 7 436 814 | 30% | 30% |
| vector + aligning | 7 436 382 | 30% | 100% | 7 435 813 | 30% | 100% |
| vector + aligning + inacc. div. | 6 885 582 | 28% | 93% | 6 885 014 | 28% | 93% |
Наиболее значительное ускорение произошло из-за векторизации. Остальные оптимизации гораздо менее значительны. Можно сказать, что стоило остановиться на векторизации, так как влияние выравнивания находится в пределах погрешности, а неточное деление влияет на качество обработки.
- Computer Systems: A Programmer's Perspective 3rd Edition by Randal Bryant, David O'Hallaron
- Compiler explorer - godbolt.com
- Valgrind - valgrind.org
- Mirror of Intel Intrinsics Guide - laurence.com/sse
- Jupyter Notebook - jupyter.org
- Python Matplotlib - matplotlib.org
- Ilya Dedinsky aka Ded as prepod
- Aleksei Durnov as mentor
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent