Помогите с оптимизацией критичного (по времени выполнения) участка кода. Преамбула: функция смешивает цвета по формуле RGB1 * k + RGB2 * (1 - k), где k - коэффициент преобладания одного цвета над другим, значением от 0 до 1. Чтобы избежать операций с плавающей запятой я умножил все части на 10000H. Вот код: На входе - 24bitcolor, Src и Dst, Shade - коэффициент преобладания от 0 до 255 Код (Text): MixColors proc Dst:DWORD, Src:DWORD, Shade:DWORD mov edx, Shade cmp dl, 0 jne m1 mov eax, Dst jmp ExitEntry m1: cmp dl, 0ffh jne m2 mov eax, Src jmp ExitEntry m2: push ebx push esi push edi xor edi, edi xor ecx, ecx mov ebx, 00010000h mov ch, dl ;ecx = k sub ebx, ecx ;ebx = (1-k) ;R mov eax, Src and eax, 0ffh mul ecx mov esi, eax mov eax, Dst and eax, 0ffh mul ebx add eax, esi shr eax, 16 and eax, 0ffh or edi, eax ;G mov eax, Src shr eax, 8 and eax, 0ffh mul ecx mov esi, eax mov eax, Dst shr eax, 8 and eax, 0ffh mul ebx add eax, esi shr eax, 8 and eax, 0ff00h or edi, eax ;B mov eax, Src shr eax, 16 and eax, 0ffh mul ecx mov esi, eax mov eax, Dst shr eax, 16 and eax, 0ffh mul ebx add eax, esi and eax, 0ff0000h or edi, eax mov eax, edi pop edi pop esi pop ebx ExitEntry: ret MixColors endp Учитывая, что размеры обеих картинок большие (1024х768) - код выполняется очень долго. Возможно, я сделал алгоритмическую ошибку (может есть более быстрый алгоритм?) или с оптимизацией что-то (но, как тут блин, оптимизировать? Все получается выполнение в одной трубе, так как следующая операция зависит от результата предыдущей). Асы, помогите!!
Немного оклимавшись после праздников улучшил алгоритм. Скорость должна возрасти в 3-4 раза (в основном, за счет отказа от умножения на 10000h). Все удобно перемножается в двух регистрах, процентов 80 кода нормально распаривается в пнях. Завтра покажу результат.
Откуда эта функция вызывается? Если ты вызываешь ее для каждой точки изображения, то выгоднее перейти на MMX/SSE2 и обрабатывать по 2-4 точки сразу. Вместо mov ch, dl желательно использовать сдвиг влево на 8 разрядов. Насчект алгоритмов: почитай ftp://ftp.alvyray.com/Acrobat/4_Comp.pdf по поводу premultiplied alpha. Для твоего случая: Код (Text): RGB1 * k + RGB2 * (1 - k) = RGB1 * k + RGB2 - RGB2 * k = (RGB1 - RGB2) * k - RGB2 Так можно сократить количество умножений с двух до одного.
Вот обещанная переделка алгоритма: Код (Text): MixColors proc Dst:DWORD, Src:DWORD, Shade:DWORD ;Algorithm: MixColors = RGB1 * k + RGB2 * (1-k) mov edx, Shade cmp dl, 0 jne m1 mov eax, Dst jmp ExitEntry m1: cmp dl, 0ffh jne m2 mov eax, Src jmp ExitEntry m2: push ebx push esi push edi mov esi, Src ; UV mov edi, Dst ; UV mov ebx, esi ; UV mov ecx, edi ; UV and esi, 0FF00FFh ; UV and edi, 0FF00FFh ; UV and ebx, 0FF00h ; UV and ecx, 0FF00h ; UV shr ebx, 8 ; hbz. pairs in UV? shr ecx, 8 ; hbz. pairs in UV? ;Reminder: edx consists Shade value mov eax, ebx ; UV mul dl ; NP, 11c mov ebx, eax ; UV neg dl ; NP, 1c mov eax, ecx ; UV mul dl ; NP, 11c add ebx, eax ;ebx consits G colors mix mov ecx, Shade ; UV mov eax, esi ; UV mul ecx ; NP, 10c mov esi, eax ; UV neg cl ; NP, 1c mov eax, edi ; UV mul ecx ; NP, 10c add eax, esi ; UV shr eax, 8 ; hbz mov ah, bh ; UV pop edi pop esi pop ebx ExitEntry: ret MixColors endp Скорость возросла, но не на столько, как хотелось бы... Походу, еще не паханное поле для оптимизации. Для SDragon - спасибо, комрад, я тоже подумываю в сторону MMX, SSE, вот только я вернулся к асму после 15-ти летнего перерыва, и все что знаю - команды 8080 (гыгг). Придется почитать и про эти новые таинственные фичи... На AMD они поддерживаются?
cresta wrote: Щас скажу: 1024*768 = 786432 раз Но это в "упрощенном" режиме, там, где задан всего лишь один коэффициент прозрачности. А если функция вызывается по маске прозрачности - там (особенно, если включен градиент по х и у) может быть для каждого пикселя разное значение.
Athlon XP поддерживает SSE2, а более ранние AMD'шные процессоры поддерживают MMX. Впрочем функцию, не использующую MMX/SSE, все равно придется писать - для старых процессоров. Тогда нужно инлайнить ее. Вызывать функцию 780 тыс. раз в цикле крайне невыгодно. Плюс воспользуйся той формулой, которую я дал выше.
За счет открытия для себя инструкции imul (гыгы) удалось еще больше оптимизировать код. Теперь спаривание еще больше и количество спасенных тактов около 8 (без учета спаривания). И это только после 20 страниц чтения интеловского Instruction set reference (vol.2)! Хочу еще больше длинных выходных! Код (Text): m2: align 4 push ebx push esi push edi mov esi, Src ; UV mov edi, Dst ; UV mov ebx, esi ; UV mov ecx, edi ; UV and ebx, 0FF00h ; UV and ecx, 0FF00h ; UV shr ebx, 8 ; U and esi, 0FF00FFh ; UV and edi, 0FF00FFh ; UV shr ecx, 8 ; U ;Reminder: edx consists Shade value imul ebx, edx imul esi, edx xor edx, 000000FFh mov eax, edi imul ecx, edx imul eax, edx add eax, esi ; eax consists R and B colors mixes add ebx, ecx ; ebx consits G colors mix shr eax, 8 and ebx, 0000FF00h and eax, 00FF00FFh pop edi or eax, ebx pop esi pop ebx ExitEntry: ret
Так можно избавится от edi, esi, ebx Код (Text): m2: mov eax,Src and eax,0x00ff00ff imul eax,Shade mov edx,0xff xor edx,Shade mov ecx,Dst and ecx,0x00ff00ff imul ecx,edx add eax,ecx shr eax,8 and eax,0xff00ff mov ecx,Dst and ecx,0xff00 shr ecx,8 imul ecx,edx mov edx,Src and edx,0xff00 shr edx,8 imul edx,Shade add ecx,edx and ecx,0xff00 or eax,ecx
Что-то мне трудно оценить, что будет быстрее выполняться... Не, на самом деле не знаю. Потестить бы... Код вроде неплохо выглядит, но в глаза бросилось, что большинство кода выполняется в одной трубе, большее число операций с памятью (а что и как будет лежать в кеше на момент обращения для меня - темный лес). Я старался держать значения из памяти в регистрах до последнего, т.е. пока они не будут убиты результатом какой-то операции или не потребуется высвободить регистр.
Радуюсь, как 16 лет назад, когда написал свою первую программу (как щас помню): 10 PRINT "X{censored}" 20 GOTO 10 Уряяя!! ) Заработала!! Привожу теперь код полностью, может кому-то понадобится, или кого из асов покоробит чудовищность моей оптимизации и родится вариант еще шустрее ) Код (Text): AlphaBlend proc DstDC:DWORD, DstX:DWORD, DstY:DWORD, DstW:DWORD, DstH:DWORD, SrcDC:DWORD, SrcX:DWORD, SrcY:DWORD, Alpha:DWORD, TransColor:DWORD LOCAL TmpDC:HANDLE, TmpBmp:HANDLE, TmpObj:HANDLE LOCAL Sr2DC:HANDLE, Sr2Bmp:HANDLE, Sr2Obj:HANDLE LOCAL MemData1:DWORD, MemData2:DWORD, MemSize:DWORD LOCAL Info:BITMAPINFO invoke GetTickCount push eax push ebx push ecx push edx push esi push edi mov TmpDC, FUNC(CreateCompatibleDC, SrcDC) mov Sr2DC, FUNC(CreateCompatibleDC, SrcDC) mov TmpBmp, FUNC(CreateCompatibleBitmap, DstDC, DstW, DstH) mov Sr2Bmp, FUNC(CreateCompatibleBitmap, DstDC, DstW, DstH) mov TmpObj, FUNC(SelectObject, TmpDC, TmpBmp) mov Sr2Obj, FUNC(SelectObject, Sr2DC, Sr2Bmp) mov eax, DstW imul eax, DstH shl eax, 2 mov MemSize, eax mov MemData1, FUNC(VirtualAlloc, NULL, MemSize, MEM_COMMIT, PAGE_READWRITE) mov MemData2, FUNC(VirtualAlloc, NULL, MemSize, MEM_COMMIT, PAGE_READWRITE) mov Info.bmiHeader.biSize, 40 mov eax, DstW mov Info.bmiHeader.biWidth, eax mov eax, DstH mov Info.bmiHeader.biHeight, eax mov Info.bmiHeader.biPlanes, 1 mov Info.bmiHeader.biBitCount, 32 mov Info.bmiHeader.biCompression, 0 invoke BitBlt, TmpDC, 0, 0, DstW, DstH, DstDC, DstX, DstY, SRCCOPY invoke BitBlt, Sr2DC, 0, 0, DstW, DstH, SrcDC, SrcX, SrcY, SRCCOPY invoke GetDIBits, TmpDC, TmpBmp, 0, DstH, MemData1, ADDR Info, 0 invoke GetDIBits, Sr2DC, Sr2Bmp, 0, DstH, MemData2, ADDR Info, 0 ;int 3 mov esi, MemData1 mov edi, MemData2 mov ecx, MemSize shr ecx, 2 ; ecx consists counter add ecx, 1 next: sub ecx, 1 jz done ; if counter == 0 then apply the DIB to device and exit mov edx, Alpha and edx, edx ; if Alpha == 0 the nothing to do (reserved for a mask usage). jz next mov eax, [edi + ecx*4] cmp TransColor, eax ; if sourcecolor == transparent color then don't touch the destcolor je next cmp edx, 000000FFh ; if Alpha == FF then mov destcolor, srccolor, else -> mix the colors je WriteToDst MixColors: push ecx push esi push edi ;Reminder: eax consists Src value mov edi, [esi + ecx*4] mov esi, eax ;(Src) ; UV mov ebx, eax ; UV mov ecx, edi ; UV and ebx, 0000FF00h ; UV and ecx, 0000FF00h ; UV shr ebx, 8 ; U and esi, 00FF00FFh ; UV and edi, 00FF00FFh ; UV shr ecx, 8 ; U ;Reminder: edx consists Alpha value imul ebx, edx imul esi, edx xor edx, 000000FFh mov eax, edi imul ecx, edx imul eax, edx add eax, esi ; eax consists R and B colors mixes add ebx, ecx ; ebx consits G colors mix shr eax, 8 and ebx, 0000FF00h and eax, 00FF00FFh or eax, ebx pop edi pop esi pop ecx WriteToDst: mov [esi + ecx*4], eax jmp next done: invoke SetDIBitsToDevice, DstDC, DstX, DstY, DstW, DstH, 0, 0, 0, DstH, MemData1, ADDR Info, 0 invoke VirtualFree, MemData1, 0, MEM_RELEASE invoke VirtualFree, MemData2, 0, MEM_RELEASE invoke DeleteObject, FUNC(SelectObject, TmpDC, TmpObj) invoke DeleteObject, FUNC(SelectObject, Sr2DC, Sr2Obj) invoke DeleteDC, TmpDC invoke DeleteDC, Sr2DC pop edi pop esi pop edx pop ecx pop ebx pop eax sub FUNC(GetTickCount), eax ret AlphaBlend endp
вход в цикл next можно сделать так: Код (Text): jmp _jmp_in next: mov edx, Alpha and edx, edx ;;;; ;;;; ;;;; WriteToDest: mov [esi+ecx*4],eax _jmp_in: sub ecx, 1 jnz next ; if counter != 0 then repeat done: это сэкономит на jmp next, кроме того переход and edx,edx jz next можно будет поменять на переход вперед (что предпочтительней чем назад) : and edx,edx jz _jmp_in Можно сделать процедуру без пролога/эпилога и сэкономить один регистр : ebp, и пустить его за счетчик вместо ecx, и можно будет сэкономить на push ecx/pop ecx и задержки не будет для mov [esi+ecx*4],eax. Только параметры процедуры и локальные надо будет адресовать через esp.
короче может не совсем в тему, но я делал такое на ммх пример - 2 картинки - одна фон, другая с альфой (дырки типа). На сколько помню кран 16 битный 565, картинка 1 16 бит, другая 32бит, толь просто буффер только с альфой - не помню чё-то уже (лет 7-8 прошло). А во - спрайт там чё-то типа другого может быть размера нежли фон или чё-то типа того Код (Text): ; копировка в позицию с альфой с проверкой выхода за экран ShowPosS_Alpha_: ;align 16 push ebp push edx ;alpha mov edi,ebx mov esi,eax ;graphxSprite mov eax,[esi].nWidth mov ebx,[esi].nHeight mov [actual_width],eax mov [actual_height],ebx xor eax,eax mov [actual_start_spr_x],eax mov [actual_start_spr_y],eax ; проверка на X xor ecx,ecx mov ebx,[esi].nPosX cmp ebx,_width jge showpossa_exit ; if nPosX >= _width mov [actual_start_x],ebx test ebx,1000000000000000b jz showpossa_x1 ; >0 mov ecx,ebx xor ebx,-1 inc ebx cmp ebx,[esi].nWidth ; if nPosX >= nWidth jge showpossa_exit mov[actual_start_spr_x],ebx xor ebx,ebx mov [actual_start_x],ebx showpossa_x1: add ebx,[esi].nWidth ; actual_start_x + nWidth cmp ebx,_width jle showpossa_x2 ; =<_width push ebx sub ebx,_width push ebx pop eax pop ebx sub ebx,eax showpossa_x2: sub ebx,[actual_start_x] add ebx,ecx mov [actual_width],ebx ; ; проверка на Y xor ecx,ecx mov ebx,[esi].nPosY cmp ebx,_height jge showpossa_exit ; if nPosY >= _height mov [actual_start_y],ebx test ebx,1000000000000000b jz showpossa_y1 ; >0 mov ecx,ebx xor ebx,-1 inc ebx cmp ebx,[esi].nHeight ; if nPosY >= nHeight jge showpossa_exit mov[actual_start_spr_y],ebx xor ebx,ebx mov [actual_start_y],ebx showpossa_y1: add ebx,[esi].nHeight ; actual_start_y + nHeight cmp ebx,_height jle showpossa_y2 ; =<_height push ebx sub ebx,_height push ebx pop eax pop ebx sub ebx,eax showpossa_y2: sub ebx,[actual_start_y] add ebx,ecx mov [actual_height],ebx ; draw mov ebp,[actual_width] or ebp,ebp jz showpossa_exit mov ebx,[actual_height] mov eax,[actual_start_x] mov ecx,[actual_start_y] shl eax,1 imul ecx,_width*2 add edi,ecx add edi,eax mov eax,[actual_start_spr_x] shl eax,1 add eax,[esi].lpBitmap push ebx mov ebx,[esi].nWidth shl ebx,1 mov edx,ebx imul ebx,[actual_start_spr_y] add eax,ebx mov esi,eax pop ebx pop eax ; alpha ; eax - lpAlpha ; esi - In1 ; edi - In2 showpossa_draw2: xor ecx,ecx push ebp showpossa_draw1: movd mm0,[esi+ecx] ; 00 00 00 00 xx xx yy yy movd mm1,[edi+ecx] ; 00 00 00 00 aa aa bb bb push ebx xor ebx,ebx mov bl,[eax+ecx] movd mm2,ebx ; 00 00 00 00 00 00 aa aa not bl movd mm3,ebx ; 00 00 00 00 00 00 -aa -aa pop ebx ; expand 565 to 888 movq mm4,mm0 movq mm5,mm0 movq mm6,mm0 pand mm4,maskR pand mm5,maskG pand mm6,maskB psllq mm5,3 psllq mm6,5 ; mm4 - RR ; mm5 - GG ; mm6 - BB por mm5,mm6 por mm4,mm5 movq mm0,mm4 ;mm0 - RRGGBB RRGGBB ; expand 565 to 888 movq mm4,mm1 movq mm5,mm1 movq mm6,mm1 pand mm4,maskR pand mm5,maskG pand mm6,maskB psllq mm5,3 psllq mm6,5 ; mm4 - RR ; mm5 - GG ; mm6 - BB por mm5,mm6 por mm4,mm5 movq mm1,mm4 ;mm1 - RRGGBB RRGGBB ; -------------------------- ;int 3 punpcklwd mm2,mm2 punpcklwd mm2,mm2 punpcklwd mm3,mm3 punpcklwd mm3,mm3 pxor mm4,mm4 punpcklbw mm0,mm4 punpcklbw mm1,mm4 psubw mm0,mm1 pmullw mm0,mm2 psllw mm1,8 paddw mm1,round paddw mm0,mm1 psrlw mm0,8 packuswb mm0,mm0 ; -------------------------- ; pack mm0 888 to 565 ; mm0 - 00 00 00 00 00 RR GG BB movq mm1,mm0 movq mm2,mm0 movq mm3,mm0 pand mm1,mask1 pand mm2,mask2 pand mm3,mask3 pxor mm4,mm4 punpcklbw mm1,mm4 punpcklbw mm2,mm4 psrld mm2,11 psrld mm3,5 paddw mm1,mm2 paddw mm1,mm3 push eax movd eax,mm1 mov [edi+ecx],ax pop eax add ecx,2 dec ebp jnz showpossa_draw1 pop ebp add edi,_width*2 add esi,edx add eax,edx dec ebx jnz showpossa_draw2 pop ebp showpossa_exit: emms ret
потерял сёрс чё-то где просто 2 картинки 32bit одного размера с заданным вручную коэф-том накладываются. если очень надо дома пороюсь на дисках.
Diman, увы, оптимизация основного цикла (т.е. собственно "смешения") практически не дает прироста производительности. Как показал прогон под CodeAnalyst, 94% времени выполнения твоей функции приходится на вызовы GetDIBits: Код (Text): invoke GetDIBits, TmpDC, TmpBmp, 0, DstH, MemData1, ADDR Info, 0 invoke GetDIBits, Sr2DC, Sr2Bmp, 0, DstH, MemData2, ADDR Info, 0 Этот же вывод подтверждается экспериментально: закомментируй хотя бы один из этих вызовов, и скорость работы функции возрастёт почти вдвое. Но вот даже полное удаление цикла, который ты так тщательно оптимизировал(всего фрагмента next:/done, не даёт ощутимого прироста скорости. К сожалению, процесс "захвата" битового образа из контекста в WinGDI абсолютно неоптимизирован. Поэтому для ускорения работы в функцию нужно передавать не контексты, а указатели на байты изображения. А вот как обеспечить необходимую скорость "захвата" - даже и не знаю... Разве что DirectX использовать (там-то уж есть достаточно быстрые функции, да и в OpenGL тоже).
Спасибо откликнувшимся - многое из вышеприведенного проверил, взяв лучшее. Alexey2005: На самом деле, в WinAPI жуткие тормоза. Переделал алгоритм на MMX - разницы почти никакой (imxo даже на пару миллисекунд (пень2 - 260МГц) медленнее кода на основных регистрах). Но пара миллисекунд это незначительная потеря по сравнению с потерей в ВинАПИ. Закомментил код, оставив только ret: экспериментировал на картинке 400х300, так вот только снапшот десктопа под окном складывался в DIB буфер Data2 около 20мс... Тут что еще заморочлся - посмотрел пару туториалов по написанию на ММХ - вроде все хорошо, почерпнул оттуда несколько команд. Вот только в отладчике прокопался два дня (гыгыгы) - все никак не мог понять, а что это у меня обертка (которой проверяю дллку) вылетает на первой же команде с плавающей запятой? Первая мысль была - надо бы состояние mm регистров сохранить, потом - вернуть. Нифига! НУ ХОТЬ БЫ В ОДНОМ ТУТОРИАЛЕ ВСТРЕТИЛАСЬ БЫ ИНСТРУКЦИЯ emms (!!!). Блин!! С такой фигней прокопался 2 дня!! Ну ладно. Вот что получилось: Код (Text): mov eax, edx shl eax, 8 or edx, eax shl eax, 8 or edx, eax ; edx = 00.Alpha.Alpha.Alpha pxor mm0, mm0 ; mm0 = 0 movd mm3, edx ; mm3 = Alpha xor edx, 00FFFFFFh ; edx = (256 - Alpha) movd mm4, edx ; mm4 = (256 - Alpha) punpcklbw mm3, mm0 ; mm3 = 00.00.00.Alpha.00.Alpha.00.Alpha punpcklbw mm4, mm0 ; mm4 = 00.00.00.(256-Alpha).00.(256-Alpha).00.(256-Alpha) mov edx, ebx @next: sub ecx, 1 jc @done mov ebx, [edi + ecx * 4] ; Data2 mov eax, [esi + ecx * 4] ; Data1 and ebx, 00FFFFFFh and eax, 00FFFFFFh cmp ebx, edx ; If Data2 == TransparentColor then skip blending je @next ;int 3 movd mm1, eax ; Data1 movd mm2, ebx ; Data2 punpcklbw mm1, mm0 ; mm1 = 00.00.00.B1.00.G1.00.R1 punpcklbw mm2, mm0 ; mm2 = 00.00.00.B2.00.G2.00.R2 pmullw mm1, mm3 ; mm1 = RGB1 * Alpha pmullw mm2, mm4 ; mm2 = RGB2 * (256 - Alpha) paddw mm1, mm2 ; mm1 = RGB1 * Alpha + RGB2 * (256 - Alpha) psrlw mm1, 8 ; mm1 = (RGB1 * Alpha + RGB2 * (256 - Alpha)) / 256 packuswb mm1, mm0 ; pack to RRGGBB movd [esi + ecx * 4], mm1 jmp @next @done: emms ; zero MMX state ret А вот дальше хотелось бы научиться еще и с SSE работать. Но тут выскочили проблемы: Интеловский мануал пишет, что нужно сперва инициализировать ССЕ стэйт через регистры CR0 & CR4. Фигасе! А как к ним пробраться из ring4? Да и ML из девятого пакета масма стал ругаться на команду test CR0, 0xFFFFFFFF (так, для эксперимента поставил). Может у кого туториал есть, как писать SSE под виндой?
Как писать SSE-код под Windows? Просто брать и писать! Всю необходимую инициализацию cr0 (если она действительно нужна) ОС выполняет ещё на этапе загрузки. Так что в любой момент можно использовать SSE-команды и они будут работать. Правда, тут есть одно НО: SSE-расширение впервые ввели только в Pentium-III. Соответственно, на младших моделях Pentium такой код работать не будет. Определить, поддерживает ли процессор SSE-команды, можно с помощью CPUID: Код (Text): xor eax,eax inc eax cpuid and edx,1000000h jnz SSEPresent Кстати, отладка SSE-кода довольно сложна, т.к. далеко не все отладчики могут показывать содержимое SSE-регистров.
