Трюки от Крыса

Крис Касперски

Хакер, номер #096, стр. 096-144-2

.text:00000020 mov eax, [esp+arg_0]

.text:00000024 test eax, eax

.text:00000026 jnz short locret_34

.text:00000028 mov ecx, [esp+arg_4]

.text:0000002C test ecx, ecx

.text:0000002E jnz short locret_34

.text:00000030 mov ecx, [esp+arg_8]

Что мы видим?! Условные переходы. То есть, ветвления. А процессоры с конвейерной архитектурой (типа Pentium Pro+) условных переходов не любят, особенно если они выполняются в цикле. Как следствие — вместо обещанного выигрыша мы получаем падение производительности.

Результат дизассемблирования foo(int a,int b,int c){if (a | b | c ) return a;}

.text:00000000 mov eax, [esp+arg_0]

.text:00000004 mov edx, [esp+arg_4]

.text:00000008 mov ecx, eax

.text:0000000A or ecx, edx

.text:0000000C mov edx, [esp+arg_8]

.text:00000010 or ecx, edx

.text:00000012 retn

А вот в выражении "(a | b | c)" никаких условных переходов нет и оно выполняется предельно быстро! Поэтому, используй "(a || … || x)" только при большом количеств элементов (намного больше трех) и только если одна или несколько переменных гораздо чаще равны TRUE, чем FALSE (при этом они должны стоять первыми слева). Тоже самое относится и к "&&", лишь с той оговоркой, что переменные, преимущественно равные FLASE следует выдвигать вперед.

Трюк 3: оценка качества генератора случайных чисел

Генератор случайных чисел используется не только в криптоалгоритмах, но и в более "приземленных" программах. Например, в играх. И очень часто нам важно знать, насколько случаен выдаваемый им результат (допустим, мы моделируем казино в поисках беспроигрышной стратегии).

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

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

#define N 10000

unsigned int buf[sizeof(int)*8];

main()

{

int x=0;

unsigned int a, l;

srand((unsigned)time(NULL));

for (l = 0; l < sizeof(int)*8; l++)

{

for (a = 0,x = 0; a < N; a++)

{

buf[l] += ((rand()>>l) & 1);

}

}

for (a = 0; a < sizeof(int)*8; a++)

printf("%02d:%02d.%02d\t",a,10000*buf[a]/N/100,10000*buf[a]/N%100);

printf("\n");

}

Результат прогона на MS VC 6 показывает, что биты от 0 до 14 генерируются довольно-таки качественно (с вероятностью 50/50 и погрешностью порядка 1%), а вот начиная с 15 бита мы имеем сплошной облом!!! То есть, по сути, rand() возвращает 14 битный результат, не дотягивающий даже до WORD!

00:50.24 01:50.23 02:49.84 03:49.22 04:49.81 05:49.58 06:49.84 07:49.77 08:50.24 09:50.43 10:50.62 11:50.10 12:49.89 13:49.49 14:50.90 15:00.00 16:00.00 17:00.00 18:00.00 19:00.00 20:00.00 21:00.00 22:00.00 23:00.00 24:00.00 25:00.00 26:00.00 27:00.00 28:00.00 29:00.00 30:00.00 31:00.00

А вот gcc 3.3.4 (другие версии не тестировались) дает совсем другой результат, задействовав 31 бит, и на десятые доли процента обогнав MS VC по качеству. В некоторых приложениях эта разница оказывается более чем критична! Так что gcc рулит!