Приветствую Вас Гость | RSS

Reversing and Code

Среда, 13.12.2017, 04:47
Главная » 2011 » Сентябрь » 13 » Оптимизируя - оптимизируй
20:53
Оптимизируя - оптимизируй
На днях, переписывая один крипто компонент для Delphi, столкнулся со странной оптимизацией кода и алгоритма. В одном месте я увидел манипуляции с массивами, которые, если упростить, выглядели следующим образом:

a := a xor b;
b := b xor a;
a := a xor b;

Если при манипуляции с xor переменная встречается несколько раз, значит алгоритм подразумевает получение переменной в ее начальном состоянии. Для чего тут это нужно. Зная логику работы xor можно составить следующие выражения:

b := b xor (a xor b); что дает нам a
a := (a xor b) xor a; что дает нам b

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

var
  a, b: array [0..9] of Byte;
  i : Byte;
begin
  for i := 0 to 9 do
  begin
    a[i] := i;
    b[i] := 9 - i;
  end;
  for i := 0 to 9 do
  begin
    if a[i] <> a[b[i]] then
    begin
      a[i] := a[i] xor a[b[i]];
      a[b[i]] := a[b[i]] xor a[i];
      a[i] := a[i] xor a[b[i]];
    end;
  end;

Теперь посмотрим как выглядит цикл с обменом в скомпилированном виде:
MOVZX EBX,BYTE PTR DS:[EDX]
MOVZX EBX,BYTE PTR DS:[EBX+ESI]
CMP BL,BYTE PTR DS:[EAX] // if a[i] <> a[b[i]]
JE SHORT 0040C200
MOVZX EBX,BYTE PTR DS:[EDX]
MOVZX EBX,BYTE PTR DS:[EBX+ESI]
XOR BYTE PTR DS:[EAX],BL
MOVZX EBX,BYTE PTR DS:[EAX]
MOVZX EDI,BYTE PTR DS:[EDX]
XOR BYTE PTR DS:[EDI+ESI],BL
MOVZX EBX,BYTE PTR DS:[EDX]
MOVZX EBX,BYTE PTR DS:[EBX+ESI]
XOR BYTE PTR DS:[EAX],BL
INC EDX
INC EAX
DEC CL
JNE SHORT 0040C1DA

Как много бесполезного кода, а в оригинале еще больше. Предположим автор не знал о дизассемблере и замерим скорость работы кода в несколько проходов. У меня получилось ~470 msec. Теперь заведем переменную для нормального обмена переменных (тем более в оригинальном коде она есть, используется при следующих вычислениях) и перепишем код:

for i := 0 to 9 do
begin
  if a[i] <> a[b[i]] then
  begin
    tmp := a[i];
    a[b[i]] := a[i];
    a[i] := tmp;
  end;
end;

Что получилось в скомпилированном виде:
MOVZX ECX,BYTE PTR DS:[EAX]
MOVZX EBX,BYTE PTR DS:[ESI]
CMP CL,BYTE PTR DS:[EBX+412D8C]
JE SHORT 0040C201
MOV BYTE PTR DS:[412DA2],CL
MOVZX EBX,BYTE PTR DS:[ESI]
MOV BYTE PTR DS:[EBX+412D8C],CL
MOVZX ECX,BYTE PTR DS:[412DA2]
MOV BYTE PTR DS:[EAX],CL
INC ESI
INC EAX
DEC DL
JNE SHORT 0040C1DB

Уже лучше. Замерим скорость выполнения. У меня вышло ~240 msec. Теперь выбросим сравнение if a[i] <> a[b[i]] и сделаем замер скорости. У меня вышло ~225 msec. В оригинале же, после такого изменения кода, размер скомпилированного кода уменьшился в ~6 раз, а скорость обработки увеличилась в ~4 раза. Даже не залезая в дизассемблер только замерами времени можно было убедиться, что выпендреж с алгоритмом без использования дополнительной переменной затормозил весь алгоритм шифрования.

Ну а теперь немного об эстетике. Далее в коде мне встретилась работа с переменной типа Integer как с 4 байтовым массивом. Чтобы не использовать сдвиги автор описал свои типы данных и сделал преобразование типов:

type
  TDWordVar = packed record
    Lo, Hi: Word;
  end;
  TWordVar = packed record
    Lo, Hi: Byte;
  end;
var
  a: DWord;
  b: Byte;
begin
  b := TWordVar(TDWordVar(a).Hi).Hi +
       TWordVar(TDWordVar(a).Hi).Lo +
       TWordVar(TDWordVar(a).Lo).Hi +
       TWordVar(TDWordVar(a).Lo).Lo ;
end;

Тут конечно на вкус и цвет товарищей нет, но лично мне такая запись просто выедает глаза и я переписал всё следующим образом:

type
  TKeyArray = packed record
    A1, A2, A3, A4: Byte;
  end;
var
  a: DWord;
  b: Byte;
begin
  b := TKeyArray(a).A4 +
       TKeyArray(a).A3 +
       TKeyArray(a).A2 +
       TKeyArray(a).A1 ;
end;

Вышло тоже самое, только теперь постороннему человеку, да и самому при правке кода, легко будет понять что делается с данной переменной.
Категория: Программирование в Delphi | Просмотров: 1692 | Добавил: PE_Kill | Рейтинг: 3.0/1
Всего комментариев: 2
2  
в примере со свопом теряется значение a[b[i]]

1  
можно было еще через директиву absolute упростить запись:
a: dword;
x: TKeyArray absolute a;
b: byte;
begin
b:= x.A1+x.A2+x.A3+x.A4;
end;

Имя *:
Email *:
Код *: