Умножение

У микроконтроллеров AVR, по сути, имеется два пути реализации умножения, разница между которыми заключается в форме представления произведения и, соответственно, в различии выполняемых арифметических операций. Первый оптимизирован для использования с командой однобайтового умножения, второй – использует только сложение и сдвиговые операции. Для произведения n-разрядного множимого и m-разрядного множителя необходимо отводить n+m разрядов.

Помимо этого существует особый случай умножения на целую степень 2. Всё дело в том, что 2 является основанием двоичной системы, а в любой позиционной системе операция умножения числа на основание системы приводит к увеличению веса каждого его разряда на порядок:
2*X = 2*(x_n-1*2^n-1 + x_n-2*2^n-2 + … + x₁*2¹ + x₀*2⁰) = x_n-1*2ⁿ + x_n-2*2^n-1 + … + x₁*2² + x₀*2^1­­.

Как видно, коэффициенты xn числа X переместились на один разряд влево (x₀ стал при 2¹, x₁ стал при 2² и т.д.). Итак, для умножения двоичного числа на 2ⁿ необходимо просто сдвинуть его на n разрядов влево. Так можно осуществить умножение на 2 двухбайтового числа в регистрах R17:R16 посредством сдвиговых операций:

     lsl   R16  ;R16 <- R16 << 1 (LSB <- 0, флаг С <- MSB)  
     rol   R17  ;R17 <- R17 << 1 (LSB <- флаг С, флаг С <- MSB)                            

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

     add   R16, R16      
     adc   R17, R17                                  

Благодаря тому, что операции сдвига и сложения выполняются за одинаковое время (1 машинный цикл) оба примера равноценны.

Иногда встречаются операции умножения на число, которое близко к степени 2. В таких случаях намного проще заменить его суммой двух слагаемых, одно из которых кратно 2ⁿ, и использовать только операции сдвига и сложения (вычитания):
63*X = (2⁶-1)*X = 2⁶*X - X = X<<6 – X,
33*X = (2⁵+1)*X = 2⁵*X + X = X<<5 + X,
130*X = (2⁷+2)*X = 2⁷*X + 2*X = X<<7 + X<<2.

Для умножения 2-байтовых чисел (обозначим их как XH:XL = 28*XH + XL и YH:YL = 28*YH + YL) применяется следующая вычислительная схема:

XH:XL * YH:YL = (2⁸*XH + XL)*(28*YH + YL) = 2¹⁶*XH*YH + 2⁸*(XH*YL + YH*XL) + XL*YL.

Рис.1 Вычислительная схема для умножения двухбайтовых чисел с использованием инструкции умножения

Отыскание 32-разрядного результата сводится к последовательности операций однобайтовых умножений и последующего сложения всех произведений с учётом сдвига слагаемых XH*YL, XL*YH на 1 байт и XH*YH на 2 байта, как показано на рис.1. Подпрограмма, реализующая эти действия, приведена ниже. Напомним, что произведение двух однобайтовых множителей, полученное в результате выполнения команды mul Rd,Rr или любой другой команды умножения, всегда заносится в регистровую пару R1:R0.

; R23:R22:R21:R20 = R17:R16 * R19:R18
; R23:R22:R21:R20 - произведение
; R17:R16 – множимое
; R19:R18 – множитель
; R1,R0 – вспомогательные регистры

mul16_16:
     mul   R16,R18  ;находим XL*YL = R16*R18 и заносим его в
     movw  R20,R0   ;младшие байты произведения R21:R20
     mul   R17,R19  ;находим XH*YH = R17*R19 и заносим его в
     movw  R22,R0   ;старшие байты произведения R23:R22
     mul   R17,R18  ;находим XH*YL = R17*R18 и прибавляем его к
     clr   R17      ;байтам R23:R22:R21 произведения
     add   R21,R0   
     adc   R22,R1      
     adc   R23,R17   
     mul   R16,R19  ;находим YH*XL = R19*R16 и прибавляем его к 
     add   R21,R0   ;байтам R23:R22:R21 произведения 
     adc   R22,R1
     adc   R23,R17  
     ret                                 

Возвести двухбайтовое число в квадрат еще проще:   
XH:XL * XH:XL = (2⁸*XH + XL)*(2⁸*XH + XL) = 2¹⁶*XH*XH  + 2⁸*2*XH*XL + XL*XL.

Подпрограмма возведения в квадрат приведена ниже. Она является хорошим примером того, где может пригодиться инструкция fmul Rd,Rr, которая одним действием производит умножение двух однобайтовых чисел и сдвиг произведения на 1 разряд влево.

; R21:R20:R19:R18 = R17:R16 * R17:R16
; R17:R16 – число, возводимое в квадрат
; R21:R20:R19:R18 – произведение
; R1,R0 – вспомогательные регистры
     
sqr16_16: 
    mul   R16,R16  ;находим XL*XL = R16*R16 и заносим его в
	movw  R18,R0   ;младшие байты произведения R19:R18
	mul   R17,R17  ;находим XH*XH = R17*R17 и заносим его в
	movw  R20,R0   ;старшие байты произведения R21:R20
	fmul  R17,R16  ;находим 2*XH*YL = R17*R18 и прибавляем его 
	clr   R17      ;к байтам R21:R20:R19 произведения
	rol   R17
    add   R19,R0
	adc   R20,R1
	adc   R21,R17
	ret                                 

Во многих случаях команда fmul Rd,Rr позволяет использовать  аппаратный умножитель 8x8 фактически как умножитель 9x8 с получением 17-разрядного результата (MSB произведения размещается в C). Это бывает очень полезно, когда возникает необходимость умножить переменную на постоянный числовой коэффициент, который немного выходит за пределы 8-разрядной сетки. Так, допустим, можно умножить число из R16 на 500

    ldi   R17,250  ;R1:R0 <- (250<<1)*R16 = 500*R16
    fmul  R17,R16  ; флаг С <- MSB                               

или на 1000:

    ldi   R17,250  ;R1:R0 <- (250<<2)*R16 = 1000*R16
    fmul  R17,R16  ;флаг С <- MSB
    lsl   R0
    rol   R1                             

Ниже показан другой практически важный пример умножения, когда один из множителей (множитель X) однобайтовый. В основе подпрограммы лежит следующая вычислительная схема:
X * YH:YL = X*(2⁸*YH + YL) = 2⁸*X*YH + X*YL

; R21:R20:R19 = R18 * R17:R16
; R21:R20:R19 - произведение 
; R18 – множимое
; R17:R16 – множитель
; R1,R0 – вспомогательные регистры

mul8_16:
     mul   R18,R17  ;находим X*YH = R18*R17 и заносим его в   
     movw  R20,R0   ;старшие байты произведения R21:R20   
     mul   R18,R16  ;находим X*YL = R18*R16   
     clr   R18       
     add   R19,R0   ;и прибавляем его  
     add   R20,R1   ;к произведению R21:R20:R19  
     adc   R21,R18     
     ret                           

Точно также могут быть разложены числа и с большей разрядностью. Однако с ростом их величины начинают резко возрастать и затраты ресурсов процессора. Так для умножения трёхбайтовых чисел понадобится по 9 операций однобайтовых умножений и двухбайтовых сложений; для четырёхбайтовых уже по 16 операций и т.д.

В подобных случаях необходимо использовать другой, наиболее общий алгоритм, который не использует команду mul Rd,Rr. А для микроконтроллеров семейства ATtiny, (а также для устаревшей линейки моделей Classic), у которых отсутствует аппаратный умножитель, он вообще является единственно возможным.

Для пояснения алгоритма, перепишем произведение Z двух произвольных двоичных чисел

Произведение X*y_j называется частичным произведением (X*y_j = X при y_j =1 и X*y_j = 0 при y_j =0), а произведение (X*y_j)*2^j  есть не что иное, как частичное произведение, сдвинутое на j разрядов влево. Итак, нахождение произведение X*Y сводится к нахождению суммы частичных произведений X*y_j, каждое из которых в свою очередь сдвинуто на j разрядов влево соответственно. На этом принципе основан школьный метод умножения в столбик. Рассмотрим пример умножения двух 4-разрядных чисел:

Как видим, для получения результата используются только операции сложения и сдвига. При этом в тех разрядах Y, где y_j=0 и X*y_j=0. И если предварительно анализировать значения y_{j/, то можно пропускать пустое сложение с 0 в соответствующих итерациях. Ниже приведена подпрограмма умножения двух трёхбайтовых чисел. В ней для получения суммы частичных произведений, сдвинутых каждое на j разрядов влево, производится сдвиг накопителя произведений m=24 раза вправо, а для экономии памяти младшие 3 байта произведения заносятся в те же регистры, где находился множитель.}

; R24:R23:R22:R21:R20:R19 = R18:R17:R16 * R21:R20:R19 
; R24:R23:R22:R21:R20:R19 – произведение
; R18:R17:R16 – множимое
; R21:R20:R19 – множитель
; R25,R1,R0 – вспомогательный регистр
 
mul24_24:
     clr   R22     ;очищаем регистры R22,R23,R24 
     clr   R23     ;при входе в подпрограмму
     clr   R24
     ldi   R25,24  ;инициализируем счётчик циклов сложения 
     clc           ;сдвинутых частичных произведений
ml1: sbrs  R19,0   ;если младший бит множителя 1, то
     rjmp  ml2  
	 add   R22,R16 ;добавляем к накопителю очередное  
	 adc   R23,R17 ;частичное произведение R18:R17:R16 
	 adc   R24,R18         
ml2: ror   R24     ;байтам R24:R23:R22 накопителя произведения 
	 ror   R23     ;в ином случае пропускаем это действие
	 ror   R22     ;и переходим к очередному сдвигу множителя
	 ror   R21     
	 ror   R20
	 ror   R19
     clc
     dec   R25     ;повторяем m=24 раз цикл сложения
	 brne  ml1     ;сдвинутых частичных произведений
	 ret                     

Перейти к следующей части: Деление

Теги:

• AVR
• Микроконтроллер