Оптимизация кода

AssemblerIA64
На вопрос можно ли сделать умножение еще быстрее -- отвечаю можно
Извините AMD64 нет, написано под IA32, умножаем байт на байт, но так нагляднее
Дело в том что вы анализируете два последних бита множимого Х и каждый раз сдвигаете Х на 1 разряд
X(i) X(i-1)
0 0 - делаем сдвиг Х на 1 разряд влево
0 1 - складываем Х с частичным произведением и делаем сдвиг Х на 1 разряд влево
1 0 - вычитаем Х из частичного произведения и делаем сдвиг Х на 1 разряд влево
1 1 - делаем сдвиг Х на 1 разряд влево
При использовании алгоритма Бута операции сложения и вычитания требуются только когда во множимом не совпадают значения в соседних разрядах, то есть, имеется переход от 0 к 1 или от 1 к 0.
можно уменьшить время умножения в два раза если анализировать по три разряда и сдвигать множимое на два разряда. Обозначим вычитание S, сложение -A, сдвиг на 1 разряд влево - L
X(i+1)|X(i)| X(i-1)| действие| коментарий
0 | 0 | 0 | LL | сдвиг Х на 2 разряда влево
0 | 0 | 1 | ALL | переход в 0-ом разряде из 1 в 0, что соответствует +1
0 | 1 | 0 | ALL | переход в 0-ом разряде из 0 в 1, что соответствует -1 и переход в 1-ом разряде из 1 в 0, что соответствует +2, итого +2-1=+1
0 | 1 | 1 | LAL | переход в 1-ом разряде из 1 в 0, что соответствует +2
1 | 0 | 0 | LSL | переход в 1-ом разряде из 0 в 1, что соответствует -2
1 | 0 | 1 | SLL | переход в 0-ом разряде из 1 в 0, что соответствует +1 и переход в 1-ом разряде из 0 в 1, что соответствует -2, итого -2+1=-1
1 | 1 | 0 | SLL | переход в 0-ом разряде из 0 в 1, что соответствует -1
1 | 1 | 1 | LL | делаем сдвиг Х на 2 разряда влево

Код (Text):

1.     xor ebx,ebx     ;очистить место под индекс
2.     xor eax,eax ;очистить старшую часть множителя
3.     cdq             ;и место под результат
4.     mov dl,Y    ;занести множитель в регистр DL
5.     test edx,edx    ;Y=0?
6.     jz a2           ;если да -- выходим
7.     mov ecx,5;установить счетчик числа разрядов - за один раз обрабатываем 2 разряда
8.         shl X,1         ;умножаем X на 2, чтобы получить младший бит X(-1)=0
9. a0: mov bx,X        ;формируем индекс в таблице переходов
10.     and bx,7        ;по маске выбираем X(i-1), X(i) и X(i+1)
11.     shr X,2         ;переходим к 2 следующим разрядам
12.     jmp table[ebx*4];ищем переход в таблице
13. sll:    sub eax,edx     ;вычесть множимое
14.     jmp ll          ;и сделать двойной сдвиг влево
15. lsl:    shl edx,1       ;сделать одинарный сдвиг влево
16.         sub eax,edx     ;вычесть множимое
17.         jmp a1 ;сделать еще один одинарный сдвиг влево и переход в начало цикла
18. lal:    shl edx,1       ;сделать одинарный сдвиг влево
19.         add eax,edx     ;прибавить множимое
20. a1:     shl edx,1   ;и сделать еще один одинарный сдвиг влево
21.     jmp a3      ;пока не обработаем все 9 разрядов
22. all:    add eax,edx     ;прибавить множимое
23. ll: shl edx,2       ;делаем двойной сдвиг влево
24. a3: sub ecx,1
25.              jnz a0 ;переход в начало цикла, пока не обработаем все 9 разрядов
26. a2: push eax    ;результат 248*255=63240
27.     push offset format
28.         push offset buffer
29.     call _imp__wsprintfA
30.     pop ecx;корректируем стек
31.     pop ecx
32.     pop ecx
33.     push 0 
34.     push offset caption;заголовок 
35.     push offset buffer;текст  
36.     push 0 
37.     call _imp__MessageBoxA@16  
38.     retn
39. X   dw 255          ;множимое
40. Y   db 248      ;множитель
41. table   dd ll,all,all,lal,lsl,sll,sll,ll
42. format  db '%08u',0
43. buffer  db 25 dup (0)
44. caption db 'Booth',0
45. end start
46. ;X(i+1) X(i)    X(i-1)
47. ;0  0   0           L,L
48. ;0  0   1   +1      A,L,L
49. ;0  1   0   +1=+2-1 A,L,L
50. ;0  1   1   +2      L,A,L
51. ;1  0   0   -2      L,S,L
52. ;1  0   1   -1=-2+1 S,L,L
53. ;1  1   0   -1      S,L,L
54. ;1  1   1           L,L

to be continue

 

А теперь обрабатываем по 3 разряда и уменьшаем время обработки в 1,5 раза

Код (Text):

1.     xor ebx,ebx     ;очистить место под индекс
2.     xor eax,eax ;очистить старшую часть множителя
3.     cdq             ;и место под результат
4.     mov dl,Y    ;занести множитель в регистр DL
5.     test edx,edx    ;Y=0?
6.     jz a2           ;если да -- выходим
7.     mov ecx,3;установить счетчик числа разрядов - за один раз обрабатываем 3 разряда
8.         shl X,1         ;умножаем X на 2, чтобы получить младший бит X(-1)=0
9. a0: mov bx,X        ;формируем индекс в таблице переходов
10.     and bx,0Fh      ;по маске выбираем X(i+2),X(i+1),X(i) и X(i-1)
11.     shr X,3         ;переходим к 3 следующим разрядам
12.     jmp table[ebx*4];ищем переход в таблице
13. llsl:   shl edx,2
14.     sub eax,edx
15.     jmp a4
16. llal:   shl edx,2
17.     add eax,edx
18. a4: shl edx,1
19.     jmp a1
20. aall:   add eax,edx
21.     shl edx,1
22.         add eax,edx
23.     jmp a1
24. ssll:   sub eax,edx
25.     shl edx,1
26.         sub eax,edx
27.     jmp a1
28. slll:   sub eax,edx     ;вычесть множимое
29.     jmp lll         ;и сделать тройной сдвиг влево
30. lsll:   shl edx,1       ;сделать одинарный сдвиг влево
31.         sub eax,edx     ;вычесть множимое
32.         jmp a1
33. lall:   shl edx,1
34.         add eax,edx
35. a1:     shl edx,2
36.     jmp a3
37. alll:   add eax,edx    
38. lll:    shl edx,3      
39. a3: sub ecx,1
40.     jnz a0 ;переход в начало цикла, пока не обработаем все 9 разрядов
41. a2:;    в eax  результат 248*255=63240
42.              . . . .
43. X   dw 255          ;множимое
44. Y   db 248      ;множитель
45. table   dd lll,alll,alll,lall,lall,aall,aall,llal,llsl,ssll,ssll,lsll,lsll,slll,slll,lll
46. ;X(i+2) X(i+1)  X(i)    X(i-1)
47. ;0  0   0   0             L,L,L
48. ;0  0   0   1   +1        A,L,L,L
49. ;0  0   1   0   +1=+2-1   A,L,L,L
50. ;0  0   1   1   +2        L,A,L,L
51. ;0  1   0   0   +2=+4-2   L,A,L,L
52. ;0  1   0   1   +3=+4-2+1 A,A,L,L
53. ;0  1   1   0   +3=+4-1   A,A,L,L
54. ;0  1   1   1   +4        L,L,A,L
55. ;1  0   0   0   -4        L,L,S,L
56. ;1  0   0   1   -3=-4+1   S,S,L,L
57. ;1  0   1   0   -3=-4+2-1 S,S,L,L
58. ;1  0   1   1   -2=-4-2   L,S,L,L
59. ;1  1   0   0   -2        L,S,L,L
60. ;1  1   0   1   -1=-2+1   S,L,L,L
61. ;1  1   1   0   -1        S,L,L,L
62. ;1  1   1   1             L,L,L

если далее по аналогии 4, 5 и т.д. наблюдаем раздувание таблицы переходов -- теоретический предел это умножение по таблице
Ссылки на алгоритм Booth
Booth's multiplication algorithm
Radix-4 Booth Encoding
Radix-8 Booth Encoding
to be continue

 

C целью уменьшения времени можно отказаться от переходов по таблице (обращение к памяти)
Если внимательно посмотреть на таблицу, видно, что она симметрична
;X(i+2)|X(i+1)|X(i)|X(i-1)|действие
;0 0 0 0 L,L,L
;0 0 0 1 +1 A,L,L,L
;0 0 1 0 +1=+2-1 A,L,L,L
;0 0 1 1 +2 L,A,L,L
;0 1 0 0 +2=+4-2 L,A,L,L
;0 1 0 1 +3=+4-2+1 A,A,L,L
;0 1 1 0 +3=+4-1 A,A,L,L
;0 1 1 1 +4 L,L,A,L
;----------------ось симметрии-----------------------------
;1 0 0 0 -4 L,L,S,L
;1 0 0 1 -3=-4+1 S,S,L,L
;1 0 1 0 -3=-4+2-1 S,S,L,L
;1 0 1 1 -2=-4-2 L,S,L,L
;1 1 0 0 -2 L,S,L,L
;1 1 0 1 -1=-2+1 S,L,L,L
;1 1 1 0 -1 S,L,L,L
;1 1 1 1 L,L,L
там где X(i+2)=1 заменяем вычитание на сложение, а X(i+1), X(i) и X(i-1) инверируем
;X(i+1)|X(i)|X(i-1)|действие|ebx|(ebx+1)/2
;0 0 0 0 0 0
;0 0 1 +1 1 1
;0 1 0 +1 2 1
;0 1 1 +2 3 2
;1 0 0 +2 4 2
;1 0 1 +3 5 3
;1 1 0 +3 6 3
;1 1 1 +4 7 4
видно, что коэффициент равен (ebx+1)/2

Код (Text):

1.     xor ebx,ebx     ;очистить место под индекс
2.     xor eax,eax ;очистить место под результат
3.     cdq             ;и старшую часть множителя
4.     mov dl,Y    ;занести множитель в регистр DL
5.     test edx,edx    ;Y=0?
6.     jz a2           ;если да -- выходим
7.     mov ecx,3;установить счетчик числа разрядов - за один раз обрабатываем 3 разряда
8.         shl X,1         ;умножаем X на 2, чтобы получить младший бит X(-1)=0
9. a0: mov bx,X        ;формируем индекс для переходов
10.     mov esi,edx
11.     shl edx,3       ;переходим к 3 следующим разрядам
12.     test ebx,1000b  ;узнаем в какой половине таблицы находимся
13.     jz a1       ;если X(i+2) равно 1
14.     neg esi     ;заменим вычитание на сложение
15.     not ebx     ;используем симметричность таблицы
16. a1: and ebx,111b    ;по маске выбираем X(i+1),X(i) и X(i-1)
17.     shr X,3         ;переходим к 3 следующим разрядам
18.     test ebx,ebx    ; либо все единицы, либо все нули
19.     jz a3
20.     add ebx,1
21.     shr ebx,1
22.     cmp ebx,2   ;сравниваем с серединой диаппазона
23.     jb a5       ;ebx=1
24.     jz a4       ;ebx=2
25.     cmp ebx,3
26.     jnz a6      ;ebx=4
27.     add eax,esi
28. a4: add esi,esi
29.     jmp a5
30. a6: shl esi,2
31. a5:     add eax,esi
32. a3: sub ecx,1
33.     jnz a0 ;переход в начало цикла, пока не обработаем все 9 разрядов
34. a2: ;результат в eax 248*255=63240
35.    . . . .
36. X   dw 255     ;множимое
37. Y   db 248    ;множитель

В зависимости от задачи можно выбрать оптимальное количество разрядов X(i+n),...,X(i-1) а цикл развернуть.

 

t00x
мелкое замечание -- если результат в eax -- тогда X и Y максимум -- dw, либо X -- 3 байта тогда Y db, а CMOVcc, если мне не изменяет память были уже в Pentium Pro. А за подсказку спасибо!
И всетаки, если коэффицент = 4 мне придется делать четыре сравнения и четыре сложения -- в моем варианте было два сравнения и один сдиг