Текущий архив: 2005.08.14;
Скачать: CL | DM;

Вниз

Обратить байт - соревнование :)   Найти похожие ветки 

← →
Igorek ©   (2005-07-23 09:59) [0]

Исходные данные: байт.
Требуется: переставить биты (младшие биты становятся старшими и наоборот).
Исполнение: процедура, принимающая байт и возвращающая обращенный байт.
Оценивание по двум номинациям:
1) скорость работы
2) обьем дополнительной памяти
Призы: всеобщее уважение и чувство выполненого долга

приветствуются спонсоры.. :)

---

← →
Kerk ©   (2005-07-23 10:07) [1]

что-то такое

 mov cl,8
 xor al,al
@@:
 rcr ah
 rcl al
 dec cl
 jmp @b

---

← →
Kerk ©   (2005-07-23 10:12) [2]

так лучше:

 xor ah,ah
@@:
 rcr al,1
 rcl ah,1
 test al,al
 jnz @b
 mov al,ah
на входе в al - исходный байт
на выходе в al - перевернутый байт

если что не судите строго - не проснулся истчо :)

---

← →
Kerk ©   (2005-07-23 10:12) [3]

а. ну и clc в начале забыл блин.

---

← →
Kerk ©   (2005-07-23 10:16) [4]

конечная версия:
SwapIt proc
 clc
 xor ah,ah
@@:
 rcr al,1
 rcl ah,1
 test al,al
 jnz @b
 mov al,ah
 ret
SwapIt endp

---

← →
3DxFantastika ©   (2005-07-23 10:42) [5]

Если байт уже представлен в строковом виде, например 11100001 то функция будет:
Function mySYSswap(st:string):string;
 Var i:integer;
Begin
Result:="";
   if length(st)<>8 then exit; //ошиблись на входе?  .. выходим
For i:=8 DownTo 1 do Result:=Result+st[i]; // :)
End;

Пример использования:
Edit2.Text:= mySYSswap(Edit1.Text);

Для получения представления байта в строковом виде может быть использована функция:

function IntToBin(Value: integer; Digits: integer): string;
var
i: integer; p:string;
begin
p:= "";
for i := 0 to Digits - 1 do
 if Value and (1 shl i) > 0 then
  p:= "1" +p
 else
  p := "0" + p;
  IntToBin:=p;
end;


пример её использования:

-----
For simvol:=1 to length(st) do
  Begin
s_result:=s_result+IntToBin(Ord(st[simvol]),8)+" ";
  End;
-----


---

← →
Kerk ©   (2005-07-23 10:44) [6]

3DxFantastika ©   (23.07.05 10:42) [5]

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

---

← →
Alx2 ©   (2005-07-23 10:50) [7]

>Kerk ©   (23.07.05 10:44) [6]
Экстремальный случай, когда все искомые значения просто сидят в таблице, не рассматриваем? :)

---

← →
Kerk ©   (2005-07-23 10:53) [8]

Alx2 ©   (23.07.05 10:50) [7]

Ну почему же? Вроде самый быстрый способ. Но памяти жрет больше всего.

---

← →
Verg ©   (2005-07-23 10:53) [9]

1. Табличный. no comments...

2.
unsigned char swapbits(unsigned char n)
{
  n = ((n >>  1) & 0x55) | ((n <<  1) & 0xaa);
  n = ((n >>  2) & 0x33) | ((n <<  2) & 0xcc);
  n = ((n >>  4) & 0x0f) | ((n <<  4) & 0xf0);
  return n;
}

3. 64-бит умножение
 a) n = (n * 0x0202020202ULL & 0x010884422010ULL) % 1023;
 b) n = ((n * 0x80200802ULL) & 0x0884422110ULL) * 0x0101010101ULL >> 32;

4. Просто умножение
n = ((n * 0x0802LU & 0x22110LU) | (n * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16

---

← →
Alx2 ©   (2005-07-23 10:55) [10]

Эх, не успел :)
Тоже хотел номер 2 из поста [9] привести.

---

← →
Kerk ©   (2005-07-23 11:02) [11]

блинн.... ну ужос... все.. последний вариант.. обещаю :)
SwapIt proc
clc
xor ah,ah
mov cl,8
@@:
rcr al,1
rcl ah,1
dec cl
jnz @b
mov al,ah
ret
SwapIt endp

---

← →
Verg ©   (2005-07-23 11:04) [12]

> Kerk ©   (23.07.05 11:02) [11]



> все.. последний вариант.. обещаю


Эт вряд ли....

---

← →
Alx2 ©   (2005-07-23 11:20) [13]

Реализация 2-го варианта поста [9] на asm.

function SwapBits(_byte:Byte):Byte;
asm
       movzx     ecx, al
       lea       edx, [ecx+ecx]
       and       edx, $AA
       shr       ecx, 1
       and       ecx, $55
       or        ecx, edx
       mov       eax, ecx
       shr       eax, 2
       and       eax, $33
       shl       ecx, 2
       and       ecx, $CC
       or        eax, ecx
       mov       edx, eax
       shr       edx, 4
       and       edx, $F
       shl       eax, 4
       and       eax, $F0
       or        edx, eax
       movzx     eax, dl
end;


---

← →
Alx2 ©   (2005-07-23 11:21) [14]

Заголовок поправлю:
function SwapBits(_byte:Byte):Byte; register;

---

← →
raidan ©   (2005-07-23 11:26) [15]

>Kerk ©   (23.07.05 10:44) [6]
>3DxFantastika ©   (23.07.05 10:42) [5]

>Девушка, Вы определенно зря пропустили нашу ветку про >изврашения. Многому можете нас научить.

Ты зачем так жестоко? :)

---

← →
Alx2 ©   (2005-07-23 11:36) [16]

Две лишних команды выкинул:

function SwapBits(_byte:Byte):Byte; register;
asm
       movzx     ecx, al
       lea       edx, [ecx+ecx]
       and       edx, $AA
       shr       ecx, 1
       and       ecx, $55
       or        ecx, edx
       mov       eax, ecx
       shr       eax, 2
       and       eax, $33
       shl       ecx, 2
       and       ecx, $CC
       or        eax, ecx
       mov       edx, eax
       shr       edx, 4
       shl       eax, 4
       or        edx, eax
       movzx     eax, dl
end;


---

← →
Alx2 ©   (2005-07-23 11:50) [17]

Посмотрел особенности кода, генерируемого Delphi после возврата из функций типа byte и выкинул еще одну команду:


function SwapBits(_byte:Byte):Byte; register;
asm
       movzx     ecx, al
       lea       edx, [ecx+ecx]
       and       edx, $AA
       shr       ecx, 1
       and       ecx, $55
       or        ecx, edx
       mov       eax, ecx
       shr       eax, 2
       and       eax, $33
       shl       ecx, 2
       and       ecx, $CC
       or        eax, ecx
       mov       edx, eax
       shr       edx, 4
       shl       eax, 4
       or        eax, edx
end;


---

← →
begin...end ©   (2005-07-23 11:52) [18]

> Alx2 ©   (23.07.05 11:21) [14]
> Заголовок поправлю: ...

Зачем?

---

← →
Alx2 ©   (2005-07-23 11:55) [19]

>begin...end ©   (23.07.05 11:52) [18]

Ну, паранойя у меня :)

Особенно обострилась после разговора с тобой о передаче со спецификатором const :)

---

← →
Sha ©   (2005-07-23 12:00) [20]

На работе много разных вариантов, написанных посетителями delphimaster. В понедельник поищу.

Помню, одно из самых красивых, достаточно быстрых и коротких (25 байт) решений было что-то вроде этого (идея заимствована):


function ReverseBits(b: byte): byte;
asm
    test al, 81h
    jp   @1
    xor  al, 81h
@1:
    test al, 42h
    jp   @2
    xor  al, 42h
@2:
    test al, 24h
    jp   @3
    xor  al, 24h
@3:
    test al, 18h
    jp   @4
    xor  al, 18h
@4:
end;

---

← →
Sha ©   (2005-07-23 12:04) [21]

> Alx2 ©   (23.07.05 11:50) [17]

У меня было похожее решение, но если не ошибаюсь, обошелся то ли тремя, то ли двумя сдвигами :)

---

← →
Sha ©   (2005-07-23 12:09) [22]

> 3DxFantastika ©   (23.07.05 10:42) [5]

Мы тут пишем функцию:

function ReverseBits(b: byte): byte;

Хотите поучаствовать?

> Kerk ©   (23.07.05 10:44) [6]

С девушками повежливей надо.

---

← →
Alx2 ©   (2005-07-23 12:10) [23]

>Sha ©   (23.07.05 12:04) [21]

Помню что-то такое.
А я, собственно, только "перекомпилировал" вручную и какое-то ощущение незавершенности присутствует...

PS
[20] - класс!!!

---

← →
ssk ©   (2005-07-23 12:20) [24]

снова меряемся пиписками? :-D

---

← →
Alx2 ©   (2005-07-23 12:22) [25]

>ssk ©   (23.07.05 12:20) [24]

"С какой целью интересуетесь?" (с)

:))

---

← →
Anatoly Podgoretsky ©   (2005-07-23 13:48) [26]

raidan ©   (23.07.05 11:26) [15]
Вот сделает ему Анка реверс в изврашеной форме, тогдп посмотрим как он заговорит.

---

← →
Alx2 ©   (2005-07-23 18:59) [27]

>Sha ©   (23.07.05 12:04)
После рисования на бумажке получилось с тремя сдвигами:

 function SwapBits(_byte: Byte): Byte; register;
 asm
       mov     ah,al
       mov     ecx,eax
       and     eax,$330
       and     ecx,$CC0
       shr     ecx,2
       lea     eax,[4*eax+ecx]
       mov     ecx,eax
       and     eax,$550
       and     ecx,$AA0
       shr     eax,3
       shr     ecx,5
       or      eax,ecx
 end;


---

← →
Kerk ©   (2005-07-23 19:07) [28]

Anatoly Podgoretsky ©   (23.07.05 13:48) [26]

Думаете понравится?

---

← →
Alx2 ©   (2005-07-23 19:18) [29]

Вдогонку [27]:
Торможу. Забыл провести то же самое с другой парой сдвигов.

 function SwapBits(_byte: Byte): Byte; register;
 asm
       mov     ah,al
       mov     ecx,eax
       and     eax,$330
       and     ecx,$CC0
       shr     ecx,2
       lea     eax,[4*eax+ecx]
       mov     ecx,eax
       and     eax,$550
       and     ecx,$AA0
       lea     eax,[4*eax+ecx]
       shr     eax,5
 end;


Итого, два явных сдвига.

---

← →
KilkennyCat ©   (2005-07-23 21:11) [30]

> Итого, два явных сдвига.


где? ;)

---

← →
Alx2 ©   (2005-07-23 21:12) [31]

>KilkennyCat ©   (23.07.05 21:11) [30]

У меня, наверное :)

---

← →
Sha ©   (2005-07-23 22:16) [32]

>Alx2 ©   (23.07.05 19:18) [29]

На одну команду больше, но на 1 сдвиг меньше и поэтому, думаю, быстрее:


function ReverseBitsSha1Shift(b: byte): byte;
asm
 mov  edx, eax         //........76543210
 and  eax, $00AA       //........7.5.3.1.
 and  edx, $0055       //.........6.4.2.0
 lea  eax, [4*edx+eax] //.......67452301.
 lea  edx, [eax+eax]   //......67452301..
 and  eax, $0198       //.......67..23...
 and  edx, $00CC       //........45..01..
 lea  eax, [8*edx+eax] //.....45670123...
 lea  edx, [eax+eax]   //....45670123....
 shr  eax, 7           //............4567
 and  edx, $00F0       //........0123....
 add  eax, edx         //........01234567
end;

---

← →
ssk ©   (2005-07-24 17:41) [33]

>>Alx2 ©   (23.07.05 12:22) [25]
С какой целью интересуетесь?

уж больно частенько такого рода "конкурсы" стали здесь появляться ;-)

---

← →
Knight ©   (2005-07-24 18:48) [34]

Вот блин... тему прочитал, идею замутил, а оно уже в [20] выложено :(

---

← →
Knight ©   (2005-07-24 18:50) [35]

Ладно... хоть асм по ходу написания немного вспомнил :)

---

← →
Alx2 ©   (2005-07-25 08:20) [36]

Результаты замеров (профайлер VTune 7.0).

Мнемоника названия метода: m_<автор>_<номер поста>
Тест:

Const
 Count = 1000000;
Var
 k: Cardinal;
 b: Byte;
Begin
 For k := 1 To Count Do
   For b := 0 To $FF Do
     m_Sha_20(b);

 For k := 1 To Count Do
   For b := 0 To $FF Do
     m_Alx2_29(b);

 For k := 1 To Count Do
   For b := 0 To $FF Do
     m_Sha_32(b);

 For k := 1 To Count Do
   For b := 0 To $FF Do
     m_Kerk_11(b);
End;


Результаты

Size Function Clockticks Samples
41 m_Alx2_29 1193
45 m_Sha_32 1602
25 m_Sha_20 4797
16 m_Kerk_11 6928


---

← →
Kerk ©   (2005-07-25 09:21) [37]

ssk ©   (23.07.05 12:20) [24]
снова меряемся пиписками? :-D

Alx2 ©   (25.07.05 8:20) [36]

Size Function Clockticks Samples
41 m_Alx2_29 1193
45 m_Sha_32 1602
25 m_Sha_20 4797
16 m_Kerk_11 6928

Во! У меня самая длинная :D

---

← →
Sha ©   (2005-07-25 10:11) [38]

> Alx2 ©   (25.07.05 08:20) [36]
> Результаты замеров (профайлер VTune 7.0).

Кто ж им мерит? Им профилировать надо. А в попугаях я длиннее :)

Результаты в тиках CPU на моем рабочем P4:
000  Dummy
000  ReverseBitsSha0
008  ReverseBitsSha3
012  nikkie
012  nikkie2
012  nikkie_tbl
012  ReverseBitsSha1
012  ReverseBitsSha5
012  SwapBitsAlx2
016  BitSwapPierre
016  ReverseBitsSha2
016  ReverseBitsSha6
016  SwapBits2
020  Default2
020  ReverseBitsSha4
024  Achtung
024  CombSwapAsm
028  CombSwap
040  SwapBits_Verg
084  SwapBitsKerk
096  Default
168  SwapBits_APP
176  Guav
208  ReverseBits
216  Jack128

Далее функции в порядке поступления:
function Default(B: Byte): Byte;
asm

     PUSH   EBX
     MOV    EDX, 1
     XOR    EBX, EBX
     MOV    ECX, 8
@@Loop:
     DEC    ECX
     SHR    AL, 1
     JNC    @@Go
     SHL    EDX, CL
     OR     EBX, EDX
     SHR    EDX, CL
@@Go:
     TEST   ECX, ECX
     JNZ    @@Loop
     MOV    AL, BL
     POP    EBX
end;

function GuAV(b: byte): byte;
asm
 MOV ECX,8
 SUB AH,AH
 @@1:
 MOV DH,80h
 SHR DH,CL
 SUB DL,DL
 TEST AL,DH
 JZ @@2
 INC DL
 @@2:
 SHL DL,CL
 ADD AH,DL
 LOOP @@1
 TEST AL,80h
 JZ @@3
 INC AH
 @@3:
 MOV AL,AH
end;

function Jack128(b: byte): byte;

function GetBit(b: byte; Index: Integer): boolean;
begin
Result := (b and (1 shl Index)) <> 0;
end;

procedure SetBit(var b: byte; Index: Integer; Value: boolean);
begin
if not value then
 b := b and not (1 shl Index)
else
 b := b or (1 shl Index);
end;

var
i: integer;
Temp: boolean;
begin
Result := b;
for i := 0 to 3 do
begin
  Temp := GetBit(Result, i);
  SetBit(Result, i, GetBit(Result, 7 - i));
  SetBit(Result, 7 - i, Temp);
end;
end;

function SwapBits_APP(Value: Byte): Byte;
asm
 MOV ECX,8
 MOV AH, AL
@1:
 RCL AH, 1
 RCR AL, 1
 DEC ECX
 JNZ @1
end;

function nikkie(B: Byte): Byte;
begin
Result :=
  ((B and $01) shl 7) xor
  ((B and $02) shl 5) xor
  ((B and $04) shl 3) xor
  ((B and $08) shl 1) xor
  ((B and $10) shr 1) xor
  ((B and $20) shr 3) xor
  ((B and $40) shr 5) xor
  ((B and $80) shr 7);
end;

function SwapBits_Verg(B: byte): byte;
asm
 mov  edx, eax
 shr edx,1
 rcl eax,1
 shr edx,1
 rcl eax,1
 shr edx,1
 rcl eax,1
 shr edx,1
 rcl eax,1
 shr edx,1
 rcl eax,1
 shr edx,1
 rcl eax,1
 shr edx,1
 rcl eax,1
 shr edx,1
 rcl eax,1
 and eax,$FF
end;

function SwapBits2(B: byte): byte;
asm
 xor edx,edx;   test al,  1;   setnz dl;   xor ecx,ecx;
 add edx,edx;   test al,  2;   setnz cl;   add edx,ecx;
 add edx,edx;   test al,  4;   setnz cl;   add edx,ecx;
 add edx,edx;   test al,  8;   setnz cl;   add edx,ecx;
 add edx,edx;   test al, 16;   setnz cl;   add edx,ecx;
 add edx,edx;   test al, 32;   setnz cl;   add edx,ecx;
 add edx,edx;   test al, 64;   setnz cl;   add edx,ecx;
 add edx,edx;   test al,128;   setnz cl;   add edx,ecx;
 mov eax,edx;
end;

function CombSwap(x: byte): byte;
begin
 x:=((x and $55) shl 1) or ((x shr 1) and $55);
 x:=((x and $33) shl 2) or ((x shr 2) and $33);
 Result:=((x and $F) shl 4) or ((x shr 4) and $0F);
end;

function ReverseBitsSha1(b: byte): byte;
asm
    mov   edx, eax
    shl   eax, 8
    and   edx, $00F0
    or    eax, edx

    mov   edx, eax
    shl   eax, 4
    and   edx, $0CC0
    and   eax, $3300
    or    eax, edx

    mov   edx, eax
    shl   eax, 2
    and   edx, $2A80
    and   eax, $5500
    or    eax, edx

    shr   eax, 7
end;

function BitSwapPierre(AByte: byte): byte;
asm
 mov cl, al
 rol cl, 6
 rol al, 2
 and cl, 11001100b
 and al, 00110011b
 or al, cl
 lea ecx, [eax + eax]
 ror al, 1
 and cl, 10101010b
 and al, 01010101b
 or al, cl
end;

function ReverseBitsSha2(b: byte): byte;
asm
    mov   dl, al
    xor   ecx, ecx
    rol   al, 4
    and   dl, $CC
    and   al, $33
    or    al, dl

    mov   dl, al
    rol   al, 2
    and   dl, $AA
    and   al, $55
    or    al, dl

    rol   al, 1
end;

function ReverseBitsSha3(b: byte): byte;
asm
    rol   al, 1

    mov   dl, al
    rol   al, 2
    and   dl, $55
    and   al, $AA
    or    al, dl

    mov   dl, al
    rol   al, 4
    and   dl, $33
    and   al, $CC
    or    al, dl
end;

function ReverseBitsSha4(B: Byte): Byte;
asm
    test al, 81h
    jp   @1
    xor  eax, 81h
@1:
    test al, 42h
    jp   @2
    xor  eax, 42h
@2:
    test al, 24h
    jp   @3
    xor  eax, 24h
@3:
    test al, 18h
    jp   @4
    xor  eax, 18h
@4:
end;

function ReverseBitsSha5(B: Byte): Byte;
asm
    mov   dl, al
    rol   al, 2
    and   dl, $AA
    and   al, $55
    or    dl, al

    add   dl, dl
    setc  al
    or    al, dl
    and   dl, $CC

    rol   dl, 4
    and   al, $33
    or    al, dl
end;

function nikkie2(B: Byte): Byte;
begin
B := (B and $F0) shr 4 xor
     (B and $0F) shl 4;
Result := (B and $88) shr 3 xor
     (B and $44) shr 1 xor
     (B and $22) shl 1 xor
     (B and $11) shl 3;
end;

function nikkie_tbl(B: Byte): Byte;
const a:array[0..15] of Byte=
($00,$80,$40,$C0,$20,$A0,$60,$E0,$10,$90,$50,$D0,$30,$B0,$70,$F0);
begin
Result := a[B and $0F] xor (a[(B and $F0) shr 4] shr 4);
end;

function Achtung(input: byte): byte;
asm
  mov dl, al
  mov al, 0
  mov cl , dl
  and cl, 10001000B
  rol cl, 1
  or al, cl

  mov cl, dl
  and cl, 00010001B
  ror cl, 1
  or al, cl

  mov cl, dl
  and cl, 00100010B
  ror cl, 3
  or al, cl

  mov cl, dl
  and cl, 01000100B
  rol cl, 3
  or al, cl
end;

function CombSwapAsm(x: byte): byte;
asm
mov edx,eax
and eax,$55
shr edx,1
shl eax,1
and edx,$55
or eax,edx
mov edx,eax
and eax,$33
shr edx,2
shl eax,2
and edx,$33
or eax,edx
mov edx,eax
and eax,$F
shr edx,4
shl eax,4
and edx,$F
or eax,edx
end;


---

← →
Sha ©   (2005-07-25 10:12) [39]

Продолжение:
Function ReverseBits(source:Byte):byte;overload;
Var
i:shortint;
Begin
Result:=0;
For i:=(SizeOf(Result)shl 3)-1 downto 0 do
Begin
  Result:=Result shl 1;
  Result:=Result or (source and 1);
  source:=source shr 1;
End;
End;

function ReverseBitsSha0(B: Byte): Byte;
const a:array[byte] of Byte=
($00,$80,$40,$C0,$20,$A0,$60,$E0,$10,$90,$50,$D0,$30,$B0,$70,$F0,
$08,$88,$48,$C8,$28,$A8,$68,$E8,$18,$98,$58,$D8,$38,$B8,$78,$F8,
$04,$84,$44,$C4,$24,$A4,$64,$E4,$14,$94,$54,$D4,$34,$B4,$74,$F4,
$0C,$8C,$4C,$CC,$2C,$AC,$6C,$EC,$1C,$9C,$5C,$DC,$3C,$BC,$7C,$FC,
$02,$82,$42,$C2,$22,$A2,$62,$E2,$12,$92,$52,$D2,$32,$B2,$72,$F2,
$0A,$8A,$4A,$CA,$2A,$AA,$6A,$EA,$1A,$9A,$5A,$DA,$3A,$BA,$7A,$FA,
$06,$86,$46,$C6,$26,$A6,$66,$E6,$16,$96,$56,$D6,$36,$B6,$76,$F6,
$0E,$8E,$4E,$CE,$2E,$AE,$6E,$EE,$1E,$9E,$5E,$DE,$3E,$BE,$7E,$FE,
$01,$81,$41,$C1,$21,$A1,$61,$E1,$11,$91,$51,$D1,$31,$B1,$71,$F1,
$09,$89,$49,$C9,$29,$A9,$69,$E9,$19,$99,$59,$D9,$39,$B9,$79,$F9,
$05,$85,$45,$C5,$25,$A5,$65,$E5,$15,$95,$55,$D5,$35,$B5,$75,$F5,
$0D,$8D,$4D,$CD,$2D,$AD,$6D,$ED,$1D,$9D,$5D,$DD,$3D,$BD,$7D,$FD,
$03,$83,$43,$C3,$23,$A3,$63,$E3,$13,$93,$53,$D3,$33,$B3,$73,$F3,
$0B,$8B,$4B,$CB,$2B,$AB,$6B,$EB,$1B,$9B,$5B,$DB,$3B,$BB,$7B,$FB,
$07,$87,$47,$C7,$27,$A7,$67,$E7,$17,$97,$57,$D7,$37,$B7,$77,$F7,
$0F,$8F,$4F,$CF,$2F,$AF,$6F,$EF,$1F,$9F,$5F,$DF,$3F,$BF,$7F,$FF);
begin
Result := (a[B]);
end;

function Default2(B: Byte): Byte;
asm

    MOVZX   EAX, AL

    MOV     EDX, EAX
    AND     EDX, 81H
    JZ      @@Go1
    XOR     EDX, 81H
    JZ      @@Go1
    XOR     EAX, 81H
@@Go1:
    MOV     EDX, EAX
    AND     EDX, 42H
    JZ      @@Go2
    XOR     EDX, 42H
    JZ      @@Go2
    XOR     EAX, 42H
@@Go2:
    MOV     EDX, EAX
    AND     EDX, 24H
    JZ      @@Go3
    XOR     EDX, 24H
    JZ      @@Go3
    XOR     EAX, 24H
@@Go3:
    MOV     EDX, EAX
    AND     EDX, 18H
    JZ      @@Go4
    XOR     EDX, 18H
    JZ      @@Go4
    XOR     EAX, 18H
@@Go4:

end;

function SwapBitsKerk(b: Byte): Byte;
asm
clc
xor ah,ah
mov cl,8
@b:
rcr al,1
rcl ah,1
dec cl
jnz @b
mov al,ah
end;

function SwapBitsAlx2(_byte: Byte): Byte;
asm
      mov     ah,al
      mov     ecx,eax
      and     eax,$330
      and     ecx,$CC0
      shr     ecx,2
      lea     eax,[4*eax+ecx]
      mov     ecx,eax
      and     eax,$550
      and     ecx,$AA0
      lea     eax,[4*eax+ecx]
      shr     eax,5
end;

function ReverseBitsSha6(b: byte): byte;
asm
mov  edx, eax         //........76543210
and  eax, $00AA       //........7.5.3.1.
and  edx, $0055       //.........6.4.2.0
lea  eax, [4*edx+eax] //.......67452301.
lea  edx, [eax+eax]   //......67452301..
and  eax, $0198       //.......67..23...
and  edx, $00CC       //........45..01..
lea  eax, [8*edx+eax] //.....45670123...
lea  edx, [eax+eax]   //....45670123....
shr  eax, 7           //............4567
and  edx, $00F0       //........0123....
add  eax, edx         //........01234567
end;

//----------------------------

function Dummy(Prm: byte): byte;
asm
 nop
 nop
 nop
 end;

function GetCPUTick: int64;
asm
 push ebx
 xor eax, eax
 cpuid
 pop ebx
 rdtsc
 cld
 nop; nop; nop; nop;
 nop; nop; nop; nop;
 end;

type
 TFun= function(Prm: byte): byte;

function Measure(Prm: byte; Fun: TFun): integer;
const
 Skip= 1024;
 LoopCount= 1024;
var
 i, j, Tick: integer;
begin;
 Result:=MaxInt;
 for i:=0 to Skip+LoopCount-1 do begin;
   Tick:=GetCPUTick;
{$IFDEF LOOP}
   for j:=1 to 10 do Fun(Prm);
{$ELSE}
   Fun(Prm);
{$ENDIF}
   Tick:=GetCPUTick-Tick;
   if (Result>Tick) and (i>=Skip) then Result:=Tick;
   end;
 end;

const
 MaxCount= 32;
type
 TName= string[15];
 TData= record
   Tick: integer;
   Name: TName;
   end;
 TDataArray= array[0..MaxCount-1] of TData;

function CompareFunc(List: TStringList; Index1, Index2: integer): integer;
var
 i1, i2: integer;
 s1, s2: string;
begin;
 s1:=List[Index1];
 s2:=List[Index2];
 i1:=StrToIntDef(Copy(s1,1,Pos(" ",s1)-1),0);
 i2:=StrToIntDef(Copy(s2,1,Pos(" ",s2)-1),0);
 if i1<i2 then Result:=-1
 else if i1>i2 then Result:=1
 else Result:=CompareText(s1,s2);
 end;

procedure TForm1.SpeedButton1Click(Sender: TObject);
var
 Count: integer;
 Data: TDataArray;

procedure CollectData(Name: TName; Fun: TFun);
const
 Prm= 255;
begin;
 if Count<MaxCount then begin;
   Data[Count].Name:=Name;
   Data[Count].Tick:=Measure(Prm, Fun);
   inc(Count);
   end;
 end;

var
 sl: TStringList;
begin;
 SpeedButton1.Enabled:=false;
 //Memo1.Lines.Clear;

 Application.ProcessMessages;
 sleep(1000);
 Application.ProcessMessages;

 Count:=0;
 CollectData("Dummy", @Dummy);
 CollectData("ReverseBitsSha0", @ReverseBitsSha0);
 CollectData("nikkie_tbl", @nikkie_tbl);
 CollectData("ReverseBitsSha1", @ReverseBitsSha1);
 CollectData("ReverseBitsSha2", @ReverseBitsSha2);
 CollectData("ReverseBitsSha3", @ReverseBitsSha3);
 CollectData("ReverseBitsSha4", @ReverseBitsSha4);
 CollectData("ReverseBitsSha5", @ReverseBitsSha5);
 CollectData("nikkie2", @nikkie2);
 CollectData("nikkie", @nikkie);
 CollectData("CombSwapAsm", @CombSwapAsm);
 CollectData("CombSwap", @CombSwap);
 CollectData("SwapBits2", @SwapBits2);
 CollectData("Achtung", @Achtung);
 CollectData("SwapBits_Verg", @SwapBits_Verg);
 CollectData("Default", @Default);
 CollectData("Default2", @Default2);
 CollectData("SwapBits_APP", @SwapBits_APP);
 CollectData("ReverseBits", @ReverseBits);
 CollectData("Guav", @Guav);
 CollectData("Jack128", @Jack128);
 CollectData("BitSwapPierre", @BitSwapPierre);
 CollectData("SwapBitsKerk",@SwapBitsKerk);
 CollectData("SwapBitsAlx2",@SwapBitsAlx2);
 CollectData("ReverseBitsSha6",@ReverseBitsSha6);
 sl:=TStringList.Create;
 while Count>0 do begin;
   dec(Count);
   sl.Add(Format("%.3d  %s",[Data[Count].Tick-Data[0].Tick,Data[Count].Name]));
   end;
 sl.CustomSort(CompareFunc);
 Memo1.Lines.Assign(sl);
 sl.Free;

 SpeedButton1.Enabled:=true;
 end;


---

← →
Alx2 ©   (2005-07-25 10:52) [40]

Sha ©   (25.07.05 10:11) [38]

>Кто ж им мерит? Им профилировать надо. А в попугаях я длиннее :)

Почему же нельзя мерить им?

Погонял твой тест на своей машине (тоже P4).
Есть довольно сильная неустойчиовсть (например, Default2 скачет от 8 тиков до 16). Потом, аргумент всегда равен 255. Несколько некорректно.

---

← →
Sha ©   (2005-07-25 11:09) [41]

> Alx2 ©   (25.07.05 10:52) [40]
> Почему же нельзя мерить им?

Потому, что не для этого он.

> Погонял твой тест на своей машине (тоже P4).
> Есть довольно сильная неустойчиовсть (например, Default2
> скачет от 8 тиков до 16).

Так уж Intel переходы предсказывает :)

> Потом, аргумент всегда равен 255. Несколько некорректно.

Сделано специально. Этим я создаю тепличные условия для функций,
содержащих условные переходы.
Если хочешь, можешь заменить Fun(Prm); на Fun(i);
Это ни на что не влияет для самых быстрых функций, т.к. в них нет условных переходов, а результаты медленных только ухудшит.

---

← →
Sha ©   (2005-07-25 11:18) [42]

Вот еще неплохая функция (на 8 тиков больше Dummy)

function ReverseBitsSha7(b: byte): byte;
asm
mov  edx, eax         //........76543210
and  eax, $0055       //.........6.4.2.0
and  edx, $00AA       //........7.5.3.1.
add  eax, eax         //........6.4.2.0.
add  eax, eax         //.......6.4.2.0..
add  eax, edx         //.......67452301.
mov  edx, eax
add  eax, eax         //......67452301..
and  edx, $0198       //.......67..23...
and  eax, $00CC       //........45..01..
lea  eax, [8*eax+edx] //.....45670123...
mov  edx, eax
shr  eax, 7           //............4567
add  edx, edx         //....45670123....
and  edx, $00F0       //........0123....
add  eax, edx         //........01234567
end;

---

← →
Alx2 ©   (2005-07-25 11:56) [43]

Sha ©   (25.07.05 11:18) [42]

>Так уж Intel переходы предсказывает :)

Тогда данные, полученные этим тестом не актуальны.

Что касается Intel® VTune™ Performance Analyzer:  не понимаю почему нельзя использовать его данные по растактовке команд с учетом ветвлений, коллизий и прочая, если уж таковые он предоставляет как на основании реальных прогонов программы, так и на основе статического анализа? (правда последний, скорее, несет академический интерес). К тому же результаты его анализа много устойчивее.

PS
Вот последние результаты (VTune. Способ тестирования описан в [36]):

Size        Function        Clockticks Samples
4        Dummy        80
12        ReverseBitsSha0        109
29        ReverseBitsSha2        157
41        SwapBitsAlx2        171
30        ReverseBitsSha5        175
42        nikkie_tbl        187
28        BitSwapPierre        195
27        ReverseBitsSha3        195
53        ReverseBitsSha1        196
45        ReverseBitsSha6        205
47        CombSwapAsm        214
51        ReverseBitsSha7        221
65        CombSwap        243
71        nikkie2        254
40        SwapBits_Verg        308
99        nikkie        313
43        Achtung        331
75        SwapBits2        365
31        ReverseBitsSha4        405
72        Default2        519
16        SwapBitsKerk        703
15        SwapBits_APP        713
20        GetBit        1273
29        SetBit        1983
44        ReverseBitsBtnClick        2049
86        Jack128        2193
34        ReverseBits        2245
32        Default        2948
34        GuAV        4908


Вот последние результаты (Sha):
000  Dummy
000  ReverseBitsSha0
008  Default2
008  nikkie_tbl
008  ReverseBitsSha2
008  ReverseBitsSha3
008  ReverseBitsSha5
008  ReverseBitsSha6
008  ReverseBitsSha7
012  BitSwapPierre
012  nikkie
012  nikkie2
012  SwapBitsAlx2
016  CombSwapAsm
016  ReverseBitsSha1
016  ReverseBitsSha4
020  CombSwap
020  SwapBits2
024  Achtung
040  SwapBits_Verg
076  SwapBits_APP
080  SwapBitsKerk
088  Default
148  ReverseBits
168  Guav
252  Jack128

Конкретные цифры, конечно, здесь мало говорят. Но в порядке следования ощутимая разница.

Чему доверять?

---

← →
Alx2 ©   (2005-07-25 11:57) [44]

Сорри за неаккуратность в табличке

---

← →
Alx2 ©   (2005-07-25 12:03) [45]

GetBit и SetBit - артефакт.

---

← →
Sha ©   (2005-07-25 12:33) [46]

>>Так уж Intel переходы предсказывает :)
> Тогда данные, полученные этим тестом не актуальны.

Как раз актуальны, потому, что все как реальной программе.

> Что касается Intel® VTune™ Performance Analyzer:  не понимаю
> почему нельзя использовать его данные по растактовке команд с
> учетом ветвлений, коллизий и прочая, если уж таковые он
> предоставляет как на основании реальных прогонов программы,
> так и на основе статического анализа?

Любые данные, полученные на основе реальных прогонов будут искажены измерителем. Нельзя измерить, не изменяя состояние железа. Причем размер искажений зависит как от "размера измерителя", так и от свойств программы, процессора и ОС.

VTune предназначен для поиска горячих мест в коде. С этим он успешно справляется.
Для пользователя же важно время от старта до финиша, а не таблица (одна или другая).

> К тому же результаты его анализа много устойчивее

В реальной программе, где цикл не такой короткий, ты получишь большую устойчивость. Но только в среднем. Слишком много составлящих (аппаратных и программных) влияют на каждый прогон.
Ты можешь и сам усреднить, вынося измерения из цикла, но это опять на даст тебе представления о поведении реальной программы в жизни, т.к. это будут средние результаты в данном тесте.

---

← →
Alx2 ©   (2005-07-25 13:15) [47]

>Sha ©   (25.07.05 12:33) [46]

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

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

Вот мне и интересны такие статистически достоверные данные. От старта до финиша. С оценками разброса, достоверностью и прочее (на всякий случай: я ничего ни от кого не требую - тут уж мои проблемы, тем более необходимые знания имеются).  Но позиционировать же как общий результат частные случаи "из реальной жизни"  - нет смысла.

Попробую в ближайшее время все это посчитать. Надеюсь, результат будет согласовываться с анализом VTune (пока расцениваю VTune в своем арсенале как некоторый эталон измерительной системы :)

---

← →
Sha ©   (2005-07-25 13:20) [48]

>Alx2 ©   (25.07.05 13:15) [47]
>пока расцениваю VTune в своем арсенале как некоторый эталон измерительной системы :)

Ключевое слово здесь - "пока" :)

---

← →
Alx2 ©   (2005-07-25 13:21) [49]

Sha ©   (25.07.05 13:20) [48]

>Ключевое слово здесь - "пока" :)

Да. Ты меня очень заинтриговал. Хочу убедиться.

---

← →
Igorek ©   (2005-07-25 14:24) [50]

ого сколько вариантов.. жаль тема не новая..

---

Страницы: 1 2 вся ветка

Текущий архив: 2005.08.14;
Скачать: CL | DM;

Наверх

Память: 0.66 MB
Время: 0.229 c