Вопрос про быстрое вычитание 32-хбайтных чисел.

Господа, делаю реализацию криптографического алгоритма, возник вопрос, связанный с быстродействием моей процедуры вычитания двух 32-х байтных чисел. (по условию число А всегда больше числа В, результат пишется в С).
ТТХ рабочего компьютера: Процессор P4 2,4 ГГц, оперативки - 1 Гбайт, ОС - WindowsXP.

моя реализация:

Код (Text):

1. #define ONE_SUB(i) \
2. _asm    sbb eax,[esi+i] \
3. _asm    mov [edi+i],eax \
4. _asm    mov eax, [edx+i+4]
5.  
6. ...
7.  
8. int _declspec(naked) Substracting(void *a, void *b,void *c)
9. {
10.     _asm
11.     {
12.         push ebp;
13.         mov ebp,esp;
14.         pushad;
15.         mov edx,[ebp+8];
16.         mov edi,[ebp+16];
17.         mov esi,[ebp+12];
18.         clc;
19.         mov eax,[edx];
20.         sbb eax,[esi];
21.         mov [edi],eax;
22.         mov eax,[edx+4];
23.         ONE_SUB(4);
24.         ONE_SUB(8);
25.         ONE_SUB(12);
26.         ONE_SUB(16);
27.         ONE_SUB(20);
28.         ONE_SUB(24);
29.         sbb eax,[esi+28];
30.         mov [edi+28],eax;
31.         popad;
32.         pop ebp;
33.         ret;
34.     };

 

popad с закомментированным pushad - гарантия сегфолта.

 

Что то мне подсказывает, что в алгоритмах криптографии, где используется "длинная" арифметика, уж никак не процедура вычитания будет bottleneckом...

 

Пардон, поясняю: привел отдельную функцию, которую использую для тестирования быстродействия. Разумеется в реализации алгоритма так не делаю.

По поводу pushad и popad - случайно оставленный коммент на pushad.

 

"push ebp...pushad" и дальше "popad pop ebp"

Наверное, я чего-то в этой жизни не понимаю, но если ТАК хочется использовать pushad/popad, зачем ЕЩЁ РАЗ сохранять/восстанавливать ebp?

 

Так, а по какому адресу мне тогда обращаться к параметрам, если уберу push ebp?

 

Moul, я про то, что когда делаешь pushad, ты УЖЕ сохраняешь ebp и писать по привычке стандартный пролог не надо. Достаточно:

pushad
mov ebp,esp
...
popad
ret

 

Moul
_declspec(naked) ... ret
Ты точно понимаешь, что делаешь? Например, изменится соглашение о вызове, кто будет отвечать за выталкивание аргументов из стека?

imho тут вообще не нужны push/pop, достаточно использовать eax, ecx и edx. До аргументов можно добраться через esp.

 

mov eax,[esi];
mov ecx,[esi+4];

sub eax,[ebx];
mov edx,[esi+8];

sbb ecx,[ebx+4];
mov [edi],eax;

sbb edx,[ebx+8];
mov [edi+4],ecx;

mov [edi+8],edx;
mov eax,[esi+12];

mov ecx,[esi+16];
sub eax,[ebx+12];

mov edx,[esi+20];
sbb ecx,[ebx+16];

mov [edi+12],eax;
sbb edx,[ebx+20];

mov [edi+16],ecx;
mov eax,[esi+24];

mov ecx,[esi+28];
sub eax,[ebx+24];

mov [edi+20],edx;
sbb ecx,[ebx+28];

mov [edi+24],eax;
mov [edi+28],ecx;

 

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

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

Код (Text):

1. _asm
2. {
3.     ...
4.     lea  edx,a;  
5.     lea  esi, b;
6.     lea  edi, c;
7.     mov     eax,[edx];      // Берем разряд A
8.     sub     eax,[esi];      // Вычитаем разряд В
9.     mov     [edi],eax;      // Записываем на место в С
10.     mov     eax,[edx+4];        // и т.д. - всего 8 раз
11.     sbb     eax,[esi+4];
12.     mov     [edi+4],eax;
13.     ...
14.     mov     eax,[edx+28];
15.     sbb     eax,[esi+28];
16.     mov     [edi+28],eax;                
17.    
18. }

 

Пардон, а на месте выделенных фрагментов не должно быть sbb?

 

Moul

Зачем тебе тестировать на скорость функцию вычитания? Это не та функция, за производительность которой надо беспокоиться в первую очередь.

 

Кстати, привел оценку скоростей на машине P4 2.4 ГГц:

Мой вариант: 39183.67K операций/с
Вариант akkort в том виде, в котором он есть (при вставке его в программу получилась ошибка вычисления и проверки ЭЦП) 48004.22K операций/с
Вариант akkort, если второй и третий sub заменять на sbb: 36226.41 операций/с.

 

Кажется понял о чем вы.
Ладно, поясню: делаю собственную реализацию вычисления и проверки ЭЦП по алгоритму ГОСТ 34.10-2001.

До представлении чисел в Монтгомери, избавлений от инверсии по модулю (насколько возможно) и модификаций схемы Горнера при вычислении кратной точки, и.т.д... уже добрался, остается причесать элементарные операции, вот тут мне явно не хватает опыта.

 

Moul

Тебе говорят о том, что ты занимаешься преждевременной оптимизацией. В реальной задаче той производительности, что есть сейчас, не хватает?

 

К сожалению не хватает (но это определяю не я лично)

 

И ты занимался профилированием алгоритма, которое выявило hot-spot в этом месте?

 

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

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

 

Так ты использовал профайлер для определения "некоторых косяков" в производительности или нет?

 

Moul
такой вариант:

mov eax,[esi];
mov ecx,[esi+4];

sub eax,[ebx];
mov edx,[esi+8];

sbb ecx,[ebx+4];
mov [edi],eax;

sbb edx,[ebx+8];
mov [edi+4],ecx;

mov eax,[esi+12];
mov [edi+8],edx;

sbb eax,[ebx+12];
mov ecx,[esi+16];

sbb ecx,[ebx+16];
mov edx,[esi+20];

sbb edx,[ebx+20];
mov [edi+12],eax;

mov [edi+16],ecx;
mov eax,[esi+24];

sbb eax,[ebx+24];
mov ecx,[esi+28];

sbb ecx,[ebx+28];
mov [edi+20],edx;

mov [edi+24],eax;
mov [edi+28],ecx;

плюс надо проверить этот же код, но с nop перед первым mov