Умножение это довольно распространенная операция. Данную операцию можно выполнить как отдельной командой ассемблера, например
MUL a,b
Так и с помощью простых операций сложения и смещения.
Конечно, использовать одну команду это удобно, но она не отражает саму механику процесса, не говоря уже о том, что не на всех микроконтроллерах, данная операция может вообще быть доступна. Также с помощью данного алгоритма можно умножать многобайтовые числа с помощью 8-битных операций.
Разберем процесс умножения двоичных чисел на примере двух 4-битных чисел
Для примера разберем умножение двух 4-битовых чисел. Очевидно, что при умножении битность увеличится в 2 раза и результат умножения будет уже 8-битное число.
Возьмем два числа: 1101 (13) и 1011 (11). Для умножения нужно дополнить 1й множитель нолями слева и привести к виду 00001101, то есть увеличить его разрядность в 2 раза (это нужно для цикла смещения). Затем выполнить 4 циклов вычислений. Алгоритм таков, смещаем 2й множитель вправо, если есть перенос (выбрасывается единичка), то выполняем сложение результата с 1й множителем, а сам первый множитель смещаем на бит влево. Если же переноса не было (выбрасывается нолик), то операция сложения пропускается.
Теперь по шагам:
1)
2й множитель сдвигаем вправо на бит: 1011>>1 = 101 (перенос есть, выполняем сложение результата с 1й множитель).
Результат 0 + 00001101 = 00001101. (начальный "результат" всегда равен нолю!)
1й множитель сдвигаем влево на бит: 00001101<<1 = 00011010.
2)
2й множитель сдвигаем вправо на бит: 101>>1 = 10 (перенос есть, выполняем сложение результата с 1й множитель).
Результат 00001101 + 00011010 = 00100111.
1й множитель сдвигаем влево на бит: 00011010<<1 = 00110100.
3)
2й множитель сдвигаем вправо на бит: 10>>1 = 1 (переноса нет, операция сложение не выполняется).
Результат 00100111.
1й множитель сдвигаем влево на бит: 00110100<<1 = 01101000.
4)
2й множитель сдвигаем вправо на бит: 1>>1 = 0 (перенос есть, выполняем сложение результата с 1й множитель).
Результат 00100111 + 01101000 = 10001111. (так как это последняя итерация цикла, данное значение и будет результатом умножения!)
Итак: 1101 * 1011 = 10001111 (или в десятичной системе 13 * 11 = 143).
Как видно все довольно просто, при увеличении разрядности нужно лишь выполнить больше циклов со смещением и сложением. (равное разрядности умножаемых чисел.)
Программа на Ассемблере для умножения двух 8-битных чисел на 8-битном МК
Итак, чтоб умножить два 8-битных числа на Ассемблере для AVR, понадобятся следующие команды:
LDI a,k - загрузка константы (a = k)
MOV a,b - копирование регистра (a = b)
CLR a - очистка регистра
LSR a - лог.сдвиг вправо
LSL a - лог.сдвиг влево
ROL a - лог.сдвиг влево через перенос
ADD a,b - сложение (a = a + b)
ADC a,b - сложение с переносом (a = a + b + c), где с = 0 или 1.
DEC a декремент (а = а - 1)
BRNE p - переход по адресу (р), если результат операции не равен 0
BRCC p - переход по адресу (р), если нет переноса
RCALL p - вызов подпрограммы по адресу (р)
RJMP p - безусловный переход по адресу (р)
Суть программы состоит в том, чтоб загрузить в регистры микроконтроллера два 8-битных числа (множителя) и получить 16 битный результат. Так как результат 8-битного умножения будет 16-битным, то для результата используется два 8-битных регистра.
Алгоритм тот же, как было в примере выше для умножения 4х битных чисел. В цикле c_1 смещается множитель-2 вправо. Если есть перенос (переполнение), то множитель-1 складывается с результатом, если переноса нет, сложение не выполняется. Затем множитель-1 сдвигается влево и цикл c_1 повторяется еще 7 раз. (всего 8 итераций.) В завершение результат умножения "накапливается" в регистрах r5 и r4.
В примере ниже приводится умножение 127 * 63 = 8001 (0х1F41).
Текст программы:
prog:
;загрузка множителя 1
ldi temp,127
mov r2,temp
clr r3
;загрузка множителя 2
ldi temp,63
mov r0,temp
rcall Umnozhen ;вызов подпрограммы умножения
rjmp prog ;результат получен, возврат к началу программы
;умножение (r2 * r0 = r5_r4)
Umnozhen:
;сброс результата
clr r5
clr r4
ldi temp,8 ;итерация
c_1:
lsr r0 ;сдвиг вправо множителя 2
brcc c_2 ;нет переполнения r0?
;если переполнение, сложение множителя 1 с результатом
add r4,r2
adc r5,r3
c_2:
lsl r2 ;сдвиг влево множителя 1
rol r3
dec temp ;счет итерации
brne c_1 ;итерация не завершена?
ret ;возврат из подпрограммы
Аналогично можно выполнить умножение 16, 32, 64 и более разрядных чисел, увеличив количество регистров умножаемых чисел.
Умножаем 16-бит
Теперь посмотрим, как изменится алгоритм для умножения чисел с большей разрядностью. Изменим программу для умножения 16-битных чисел. Результат при этом будет уже 32-битный, для чего использовано сразу 4 регистра (r9, r8, r7, r6).
prog:
;загрузка множителя 1
ldi temp,low(2550)
mov r2,temp
ldi temp,high(2550)
mov r3,temp
clr r4
clr r5
;загрузка множителя 2
ldi temp,low(9999)
mov r0,temp
ldi temp,high(9999)
mov r1,temp
rcall Umnozhen ;вызов подпрограммы умножения
rjmp prog ;результат получен, возврат к началу программы
;умножение (r3_r2 * r1_r0 = r9_r6)
Umnozhen:
;сброс результата
clr r6
clr r7
clr r8
clr r9
ldi temp,16 ;итерация
c_1:
lsr r1 ;сдвиг вправо множителя 2
ror r0
brcc c_2 ;нет переполнения r0?
;если переполнение, сложение множителя 1 с результатом
add r6,r2
adc r7,r3
adc r8,r4
adc r9,r5
c_2:
lsl r2 ;сдвиг влево множителя 1
rol r3
rol r4
rol r5
dec temp ;счет итерации
brne c_1 ;итерация не завершена?
ret ;возврат из подпрограммы
После выполнения операции умножения в 4х регистрах r9_r6 будет следующий результат 2550 * 9999 = 2549745. (0х1850F6A).
Спасибо за внимание.