Чёрно-белой растр.

← →
Б (2009-12-20 00:58) [0]

Здрасти!

Появилась необходимость вывести черно-белый bmp, да по-быстрее.
Нашёл свой старых исходник, немного подравил.

Procedure XGrayBmp(var B: TBitmap); // 24 bit. Type TRGBTripleArray = array [0..0] of TRGBTriple; Var x, y: LongWord; Line: ^TRGBTripleArray; begin For y:= 0 to B.Height - 1 do begin Line:= B.ScanLine[y]; For x:= 0 to B.Width - 1 do With Line[x] do begin rgbtRed := (rgbtRed + rgbtGreen + rgbtBlue) div 3; rgbtGreen:= rgbtRed; rgbtBlue := rgbtRed; end; end; End;

Как бы её оптимизировать малехо?

← →
antonn © (2009-12-20 01:25) [1]

такие вещи в мультимедии обычно спрашивают :)
procedure Greyscale_24_32(bt:tbitmap); var i,ii,k:integer; p:pointer; incr:integer; Section:TDIBSECTION; begin bt.HandleType:=bmDIB; GetObject(bt.Handle,sizeof(TDIBSECTION),@Section); i:=bt.Width; p:=Section.dsBm.bmBits; incr:=((Section.dsBmih.biBitCount * Section.dsBmih.biWidth + 31) shr 3) and $FFFFFFFC; ii:=bt.height; k:=Section.dsBmih.biBitCount shr 3; asm push ebx push edi push esi xor ebx, ebx xor edx, edx @outer_loop: mov esi, p mov ecx, i @inner_loop: xor eax, eax xor ebx, ebx xor edi, edi xor edx, edx mov al, byte ptr [esi] mov bl, byte ptr [esi+1] mov dl, byte ptr [esi+2] mov edi, eax shl ebx, 2 add edi, edx add edi, ebx shl edx, 1 add edi, edx shr edi, 3 mov eax, edi mov byte ptr [esi], al mov byte ptr [esi+1], al mov byte ptr [esi+2], al add esi, k dec ecx jnz @inner_loop mov ecx, incr add p, ecx dec ii jnz @outer_loop pop esi pop edi pop ebx end; end;
код слегка вырезан из spriteutils, на моем проце в 3 раза быстрее твоей

← →
Игорь Шевченко © (2009-12-20 01:48) [2]

antonn © (20.12.09 01:25) [1]

> xor ebx, ebx
> xor edx, edx
> @outer_loop:
>
> @inner_loop:
> xor ebx, ebx
> xor edx, edx

это типа оптимизация такая, или в первый раз может не очиститься ? :)

> mov edi, eax
> shl ebx, 2
> add edi, edx
> add edi, ebx
> shl edx, 1
> add edi, edx
> shr edi, 3
> mov eax, edi

А если так:

mov al, byte ptr [esi] mov bl, byte ptr [esi+1] mov dl, byte ptr [esi+2] lea eax,[eax+ebx*4] lea eax,[eax+edx*2] add eax, edx shr eax, 3 ...

Не быстрее получится ? (Я может глупость сказал ?)

> Procedure XGrayBmp(var B: TBitmap); // 24 bit.

Автор, а нафига var ?

← →
antonn © (2009-12-20 02:10) [3]

как хорошо что я пометил о "вырезке" =)

> Автор, а нафига var ?

чтобы враг не пролез

← →
Омлет © (2009-12-20 02:29) [4]

procedure BWThreshold24Bit(Bmp: TBitmap); var P : PByteArray; X, Y, N, XR, XG, XB, BytesInScanLine : Integer; DIB : TDIBSection; begin if (Bmp.PixelFormat = pf24Bit) and (GetObject(Bmp.Handle, SizeOf(DIB), @DIB) = SizeOf(DIB)) and (DIB.dsBmih.biHeight > 0) then begin BytesInScanLine := (((DIB.dsBmih.biWidth * DIB.dsBmih.biBitCount) + 31) and not 31) div 8; P := DIB.dsBm.bmBits; for Y := DIB.dsBmih.biHeight - 1 downto 0 do begin XB := 0; XG := 1; XR := 2; for X := 0 to DIB.dsBmih.biWidth - 1 do begin N := (28*P[XB] + 151*P[XG] + 77*P[XR]) shr 8; { Это по правильной формуле серого 0.299*Red + 0.587*Green + 0.114*Blue } P[XB] := N; P[XG] := N; P[XR] := N; Inc(XB, 3); Inc(XG, 3); Inc(XR, 3); end; Integer(P) := Integer(P) + BytesInScanLine; end; end; end;

← →
Омлет © (2009-12-20 02:30) [5]

> BWThreshold24Bit

Название сменить только надо

← →
antonn © (2009-12-20 09:38) [6]

> Омлет © (20.12.09 02:29) [4]

разве битмап не одним куском идет?
один цикл, только вычислить где находится начало последней строки и с нее начинать:
for i:=0 to DIB.dsBmih.biHeight*DIB.dsBmih.biWidth-1 do
в каждом шаге увеличение XB/Xg/Xr

← →
Anatoly Podgoretsky © (2009-12-20 12:57) [7]

> Б (20.12.2009 00:58:00) [0]

Во первых черно-белый это когда 1 бит на пиксель, а во вторых если речь идет о шкале черного, то простое сложение и деление на три дает очень плохой вариант, складывать надо по формуле и кроме того это должен быть 8 битный формат, а не 24 битный.

← →
Б (2009-12-20 13:05) [8]

> Автор, а нафига var ?

Тогда out. ;)

> простое сложение и деление на три дает очень плохой вариант

Буду делать по стандарту YCbCr.

> Во первых черно-белый это когда 1 бит на пиксель

Старые фотографии называют чёрно-белыми, а не в шкале чёрного.

← →
Омлет © (2009-12-20 14:30) [9]

> [6] antonn © (20.12.09 09:38)
> разве битмап не одним куском идет?
> один цикл, только вычислить где находится начало последней
> строки и с нее начинать:
> for i:=0 to DIB.dsBmih.biHeight*DIB.dsBmih.biWidth-1 do
> в каждом шаге увеличение XB/Xg/Xr

Ты забываешь про выравнивание. Это же 24bit, а не 32bit.

← →
Омлет © (2009-12-20 15:06) [10]

Можно еще оптимизировать мой вариант - избавиться от умножения.
Для этого нужно заранее проициализировать 3 массива с уже умноженными значениями:

var ArrXB, ArrXG, ArrXR: array[Byte] of Integer; ... for I := 0 to 255 do begin ArrXB[I] := I * 28; ArrXG[I] := I * 151; ArrXR[I] := I * 77; end;

А потом использовать

N := (ArrXB[P[XB]] + ArrXG[P[XG]] + ArrXR[P[XR]]) shr 8;

← →
Sapersky (2009-12-20 18:43) [11]

antonn © (20.12.09 01:25) [1]

Ох уж эти маньяки-ассемблерщики... ровно то же самое на Паскале процентов на 10-15 быстрее, несмотря на "ляпы" компилятора (которых есть):
Procedure XGrayBmp(B: TBitmap); Type PFColor = ^TFColor; TFColor = record b,g,r: Byte; end; Var x, y, h, Gap, dBpp : Integer; pc : PFColor; begin h := B.Height-1; If (h < 0) or (not (B.PixelFormat in [pf24bit, pf32bit])) then Exit; If B.PixelFormat = pf24bit then dBpp := 3 else dBpp := 4; pc := B.ScanLine[h]; If h > 0 then Gap := (Integer(B.ScanLine[h-1]) - Integer(pc)) - B.Width * dBpp; For y:= 0 to h do begin For x:= 0 to B.Width - 1 do begin With pc^ do begin b := (b + g * 4 + r * 3) shr 3; g := b; r := b; end; Inc(PByte(pc), dBpp); end; Inc(PByte(pc), Gap); end; End;
Если уж маньячить по полной - то movzx eax быстрее mov al. Иногда компилятор использует movzx, но в данном случае почему-то нет.

← →
0x00FF00 (2009-12-20 21:06) [12]

Небольшой комментарий к коду antonn:

push ebx push edi push esi MOV EBX, 5556h; // (2^16)+3 div 3 @outer_loop: mov esi, p mov ecx, i @inner_loop: MOV EDX, DWORD PTR [ESI]; // экономим два обращения к памяти MOVZX EAX, DL; SHR EDX, 8; MOVZX EDI, DL; MOVZX EDX, DH; ADD EAX, EDX; ADD EAX, EDI; // всё складываем (при этом сумма не вылезает за WORD) MUL BX; // и делим на 3 (в итоге имеем результат не более 0FFh, влезающий в DL) IMUL EDX, 010101; // затем размножаем на 3 байта то, что получилось MOV DWORD PTR [ESI], EDX; // записываем всё разом add esi, k dec ecx jnz @inner_loop mov ecx, incr add p, ecx dec ii jnz @outer_loop pop esi pop edi pop ebx

Мои вставки выделены КАПСОМ.
По-моему, так будет быстрее.

← →
0x00FF00 (2009-12-20 21:16) [13]

Ах да. Складывается всё без коэффициентов.
Если необходимы коэффициенты, то следует:
MOV BX, 5556h;
сменить на
MOV BX, 2001h;
а
ADD EAX, EDX;
на
LEA EDI, [EDI*4+EDX]; LEA EDI, [EDI+EDX*2];
вроде так.

← →
Игорь Шевченко © (2009-12-20 21:37) [14]

> dec ecx
> jnz @inner_loop

мой комментарий:

loop @inner_loop

> По-моему, так будет быстрее.

Неочевидно. Команды умножения выполняются дольше команд сложения или вычисления адреса.

Вообще-то практика - критерий истины, хотелось бы поиметь эталонную картинку, желательно большого размера, ну и

FlushInstructionCache;
rdtsc
код_1
rdtsc
FlushInstructionCache;
rdtsc
код_2
rdtsc
...

← →
Anatoly Podgoretsky © (2009-12-20 21:42) [15]

> Игорь Шевченко (20.12.2009 21:37:14) [14]

Команда LOOP очень медленная, пара команд dec ecx/jnz @inner_loop значительно быстрее.

← →
0x00FF00 (2009-12-20 22:25) [16]

> Неочевидно. Команды умножения выполняются дольше команд
> сложения или вычисления адреса.

Согласен.
Поэтому, при "коэффициентном" варианте возможна дальнейшая оптимизация:

MOV EBX, 010101h; ... @inner_loop: MOV EDX, DWORD PTR [ESI]; MOVZX EAX, DL; SHR EDX, 8; MOVZX EDI, DL; MOVZX EDX, DH; LEA EDI, [EDI*4+EDX]; LEA EDI, [EDI+EDX*2]; ADD EAX, EDI; IMUL EAX, EBX; // выполняется быстрее, чем 3 команды пересылки однобайтных регистров MOV DWORD PTR [ESI], EAX; add esi, k dec ecx jnz @inner_loop

← →
0x00FF00 (2009-12-20 22:28) [17]

мм.. стоп, лучше беззнаковое:

MUL EBX
вместо
IMUL EAX, EBX

звиняюсь.

PS.
Кстати, в самом деле, стоит просить у автора "эталонную" картинку.

← →
0x00FF00 (2009-12-20 22:43) [18]

Ах да.
Совсем заработался уже... =(
На место второго умножения нужно вставить SHR EAX, 3.

SHR EAX, 3
MUL EBX

← →
Игорь Шевченко © (2009-12-20 22:53) [19]

> Команда LOOP очень медленная, пара команд dec ecx/jnz @inner_loop
> значительно быстрее.

Я конечно верю, но искал в доке Интела, не нашел, среди 70 советов по написанию кода на ассемблере ("248966_Optimization Reference Manual.pdf")

Не затруднит место указать, где можно подробнее глянуть ?

← →
Anatoly Podgoretsky © (2009-12-20 23:26) [20]

> Игорь Шевченко (20.12.2009 22:53:19) [19]

Информацией из групп Борланда и сообственными экспериментами десятилетней давности. Я даже не уверен, что это актуально с последними процессорами. Но с более старыми все аггрегатные функции работали медленно, что то с очередью связаное, какое то пеналти там происходит с ними.
Эксперименты проводил именно с графикой, до этого я тоже был уверен, что LOOP быстрее, оказалось на оборот.

← →
oxffff © (2009-12-20 23:33) [21]

> Игорь Шевченко © (20.12.09 22:53) [19]

Приветствую. Такое действительно имеет место быть.

40546 Software Optimization Guide for AMD Family 10h Processors
Publication # 40546 Revision: 3.00
стр. 106

6.7Avoiding the LOOP InstructionOptimization
Avoid using the LOOP instruction.Application
This optimization applies to:
•32-bit software
•64-bit software
Rationale
The LOOP instruction has a latency of at least 8 cycles.
ExampleAvoid code like this, which uses the LOOP instruction:
label: ... loop label
Instead, replace the loop instruction with a DEC and a JNZ:
label: ...
dec rcx
jnz label

← →
Игорь Шевченко © (2009-12-20 23:34) [22]

Anatoly Podgoretsky © (20.12.09 23:26) [20]

Я почему верю - у меня есть книжка R-Style "Мискропроцессор i486, архитектура и программирование", В.Л.Григорьева, там в описании команд (похоже, прямой перевод с интеловской документации), написано, что команда loop выполняется медленнее, чем dec [e]cx; jnz ...

Но не написано, почему :)

← →
oxffff © (2009-12-20 23:35) [23]

Автор найди готовую реализацию в интернете.

← →
Игорь Шевченко © (2009-12-20 23:38) [24]

oxffff © (20.12.09 23:33) [21]

Вечер добрый.

> The LOOP instruction has a latency of at least 8 cycles.

У Intel в документации тоже написано, что 8 циклов для LOOP. Но там же написано, что на время задержки не всегда можно полагаться.

В общем, поверю на слово обоим.

Я к чему в ассемблер полез - периодически смотрю, какие коды генерируют разлиные компиляторы, так LOOP сейчас действительно не используется, но вместо сложения с регистром, умноженным на что-то, очень часто применяется инструкция LEA, если, разумеется, множитель попадает в диапазон, допустимый в SIB

← →
Anatoly Podgoretsky © (2009-12-20 23:42) [25]

> Игорь Шевченко (20.12.2009 23:34:22) [22]

Действительно, это уже в 486 процессорах было, а на пентиумах ухудшилась. Но мои данные основаны не на книгах или на оффициальных справочниках, а на личном опыте, форумах и на измерениях.
У меня была тестовая программка, на основе LOOP - заполнение прямоугольника 256*256 шкалой серого, когда я прочитал, что это медленная команда, я переписал на пару dec/jnz, то быстродействие возросло в несколько раз.
После этого я прочитал про сброс очереди. Латентность конечно большая, но это никак не объясняло падение скорости.

← →
Sapersky (2009-12-20 23:46) [26]

0x00FF00 (20.12.09 21:06) [12]

Первый вариант, без коэфф. - не работает (в результате пустая картинка) и раза в 2 медленнее.
С коэфф. - лень было собирать по строчкам, но по скорости наверное то же самое.

И кстати, в качестве эталонного лучше брать вариант из [10]. [11] - это я исключительно для сравнения с [1].

хотелось бы поиметь эталонную картинку, желательно большого размера

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

The LOOP instruction has a latency of at least 8 cycles.

Агнер Фог ещё пишет, что LOOP не спаривается и генерирует больше (по сравнению с DEC/JNZ) микроопераций.

> но вместо сложения с регистром, умноженным на что-то, очень
> часто применяется инструкция LEA, если, разумеется, множитель
> попадает в диапазон, допустимый в SIB

Это используется по причине того, что занимает меньше места.
Например сравните размер для

imul eax,4;
add eax,ebx;
и

lea eax,[eax*4+ebx];

> Это используется по причине того, что занимает меньше места.
>
> Например сравните размер для

ну и получается экономия операций, а не только места?

> Агнер Фог ещё пишет, что LOOP не спаривается и генерирует
> больше (по сравнению с DEC/JNZ) микроопераций.

:)
Это есть в мануале.

The following abbreviations are used in the Pairing column of the integer table in this
appendix:

NP — Not pairable, executes in U-pipe

LOOP — Loop Count NP

Following is the table of macro-instructions and the number of μops decoded from each instruction.

LOOP rel8 4 μops

← →
0x00FF00 (2009-12-20 23:56) [30]

> Первый вариант, без коэфф. - не работает (в результате пустая
> картинка) и раза в 2 медленнее.С коэфф. - лень было собирать
> по строчкам, но по скорости наверное то же самое.

Прошу прощения =)
У себя пока не тестировал.
Вообще говоря, я и сам планирую написать для проекта подобную функцию, поэтому в скором времени возьмусь за это серьёзно.

Но то, что умножение оказалось медленным — обескуражило.
В FastCode"овских функциях частенько используется схожий трюк.
Видимо, напутал где-то с выравниванием...

> ну и получается экономия операций, а не только места?

Операции разбиваются на микрооперации.
Поэтому с точки зрения количества тактов может быть идентично у этих вариантов.

ну по крайней мере на моем проце код с lea быстрее почти на 20% (чем не правленный из [1])

> Sapersky (20.12.09 23:46) [26]

There is an almost invisible war going on between Intel and AMD. It"s the game of who is defining the new additions to the x86 instruction set. This war has been going on behind the scenes for years without being noticed by the majority IT professionals

http://www.agner.org/optimize/blog/read.php?i=25

Я не читал. И не знаю буду ли. :)

← →
Sapersky (2009-12-21 00:40) [34]

Я не блог читал, а это:
http://www.wasm.ru/series.php?sid=11
LEA, кстати, он хвалит:
http://www.wasm.ru/article.php?article=1010028
хотя по этой же статье видно, что информация несколько устаревшая (рассматриваются максимум P3):
"Целочисленные операции в большинстве своем быстрее, чем инструкции плавающей запятой, поэтому зачастую выгоднее использовать их для осуществления простых операций плавающей запятой. Наиболее очевидное применение - это перемещение данных."
...тогда как в FastCode, который затачивали в основном под P4, применяется прямо противоположный подход.

До Интеловских/Амдэшных мануалов руки так и не дошли, это да.

Sapersky (21.12.09 00:40) [34]

> Я не блог читал, а это:
> http://www.wasm.ru/series.php?sid=11

Странно.
В http://www.wasm.ru/article.php?article=1010027
написано:

"Строковые инструкции без префикса повторения слишком медленны, и их следует заменить более простыми инструкциями. То же самое относится к LOOP на всех процессорах и к JECXZ на PPlain и PMMX. "

Код, генерируемый сишным компилятором Visual Studio для очистки небольших (10-20 байт) структур на стеке использует примерно такую последовательность команд:

xor eax,eax
mov dword ptr foo+0, eax
lea edi,foo+4
stosd
stosd
...

от двух до 5 раз stosd, если размер структуры не кратен 4, то добавляются stosw и/или stosb

Насколько я знаю, MS-овский компилятор генерирует довольно оптимальный по скорости код, поэтому непонятно, кто же прав :)

> Игорь Шевченко (21.12.2009 01:16:35) [35]

МС маст дай.
В принципе это не важно, если это не в цикле и без префикса.

← →
Sapersky (2009-12-21 13:09) [37]

Код, генерируемый сишным компилятором Visual Studio для очистки небольших (10-20 байт) структур на стеке

А это не debug-режим какой-нибудь, в котором на производительность никто особо внимания не обращает?
Или может включена оптимизация по размеру кода? Единственное преимущество stosd перед mov - в байтах она короче (1 vs 2-3). А по скорости (сейчас проверил) раза в 3 медленнее.

Чёрно-белой растр. Найти похожие ветки