Умножение и деление

К сожалению, деление и умножение чисел в дополнительном коде существенно отличаются от подобных действий над беззнаковыми числами. Существуют различные алгоритмы, но все они значительно сложнее и не слишком хорошо подходят для системы команд AVR. Поэтому на практике чаще всего прибегают к действиям над модулями чисел. Для этого, в первую очередь, анализируют и запоминают знаки чисел, затем изменяют знак у отрицательных чисел (преобразуют в равные по модулю положительные числа) и используют беззнаковые операции умножения и деления над их модулями. Полученный результат (беззнаковое число), корректируют с учетом знаков исходных множителей (делимого и делителя) по известным законам алгебры: при одинаковых знаках произведение (частное) остается без изменений, при разных знаках - знак результата должен быть изменен на противоположный.

Рассмотрим пример знакового деления 2-разредного делимого (размещается в регистрах R17:R16) на 1-байтовый делитель (в регистре R20) с помощью подпрограммы беззнакового деления  div16_8.

Для изменения знака 16-разрядных чисел на противоположный, можно использовать следующую подпрограмму:

  neg16:  
     com   R16         ;R17:R16 = 0xFFFF - R17:R16 + 1
     com   R17 
     subi  R16,low(-1)
     sbci  R17,high(-1)
     ret

Вначале необходимо определить знак будущего частного. Для этого удобно произвести операцию “Исключающее ИЛИ” между знаковыми разрядами обеих чисел и скопировать результат во флаг пользователя T. Если исходные знаки делимого и делителя одинаковые (T=0), то частное – будет неотрицательным числом. В ином случае (T=1) частное отрицательное число, которое нужно будет скорректировать после беззнакового деления:

     eor   R17,R20 ;сравниваем знаковые биты 
     bst   R17,7   ;запоминаем во флаге T знак будущего частного
     eor   R17,R20  ;восстанавливаем R17 

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

	sbrc  R20,7    ;если делитель R20 < 0,
    neg   R20      ;то изменяем знак R20 
	sbrc  R17,7    ;если делимое R17:R16 < 0,
	rcall neg16    ;то изменяем знак R17:R16

Теперь в регистрах R17:R16 и R20 находятся два неотрицательных числа и можно использовать беззнаковое деление. После этого, в случае необходимости, нужно учесть целочисленный остаток (на выходе из подпрограммы деления он находится в R18) и округлить частное до ближайшего целого числа:

     rcall div16_8  ;вызываем подпрограмму беззнакового деления
     lsr   R20      ;если целочисленный остаток от деления 
	 cpc   R18,R20  ;больше половины делителя (R18 > R20),
     brcs  ncr
	 subi  R16,low(-1)  ;то округляем частное в большую 
     sbci  R17,high(-1)  ;сторону, добавляя к нему 1

Полученное частное в регистрах  R17:R16 нужно скорректировать с учетом его истинного знака:

ncr: brtc  nxt      ;если T=1 (частное R17:R16 < 0),   
     rcall neg16    ;то изменяем его знак на противоположный
nxt:.

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

В первую очередь это относится к умножению. У AVR имеются специально разработанные для знаковых операций команды muls Rd,Rr, mulsu Rd,Rr. Это дает возможность эффективно использовать вычислительную схему подобную той, которая используется для умножения беззнаковых чисел. Например, для двух 16-разрядных чисел (индексом S - Sign отмечены знаковые числа, а индексом U - Unsign беззнаковые) (XH:XL)S = 2⁸*XHS + XLU и (YH:YL)S = 2⁸*YHS + YLU она будет иметь вид:

(XH:XL)_S*(YH:YL)_S = (2⁸*XH_S + XL_U)*(2⁸*YH_S + YL_U) = 2¹⁶*XH_S*YH_S + 2⁸*(XH_S*YL_U + YH_S*XL_U) + XL_U*YL_U.

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

На рис.1 показано, в какой последовательности происходит отыскание произведения. Для умножения XL_U*YL_U надо использовать команду mul Rd,Rr, для XH_S*YH_S инструкцию muls Rd,Rr, а для XH_S*YL_U и YH_S*XL_U - mulsu Rd,Rr (на месте Rd должен обязательно находится знаковый множитель!). Подпрограмма такого знакового умножения:

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

muls16_16:
     mul   R16,R18  ;находим XLU*YLU = R16*R18 и заносим его в
     movw  R20,R0   ;младшие байты произведения R21:R20
     muls  R17,R19  ;находим XHS*YHS = R17*R19 и заносим его в
     movw  R22,R0   ;старшие байты произведения R23:R22
     mulsu R17,R18  ;находим XHs*YLU = R17*R18 и прибавляем его к
     clr   R17      ;байтам R23:R22:R21 произведения
     sbci  R17,0
     add   R21,R0   
     adc   R22,R1    
     adc   R23,R17   
     mulsu R19,R16  ;находим YHS*XLU = R19*R16 и прибавляем его к 
     clr   R17
     sbci  R17,0
     add   R21,R0   ;байтам R23:R22:R21 произведения 
     adc   R22,R1
     adc   R23,R17  
     ret 

Еще проще найти произведение однобайтового числа X_S на 2-байтовое (YH:YL)_S:
X_S*(YH:YL)_S = X_S*(28*YH_S + YL_U) = 28*X_S*YH_S + X_S*YL_U.

Подпрограмма знакового умножения 8x16:

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

muls8_16:
     mul   R18,R17  ;находим XS*YHS = R18*R17 и заносим его в   
     movw  R20,R0   ;старшие байты произведения R21:R20   
     mulsu R18,R16  ;находим XS*YLU = R18*R16 
     clr   R18      
     sbci  R18,0         
     add   R19,R0   ;и прибавляем его  
     add   R20,R1   ;к произведению R21:R20:R19  
     adc   R21,R18     
     ret

Деление и умножение на целую степень 2 в дополнительном коде, как и в случае с беззнаковыми числами, равносильно сдвигу числа на один разряд вправо или в лево соответственно. Но здесь существует и одно различие: знаковый разряд числа должен оставаться неизменным. Сдвиг чисел в дополнительном коде иногда называют арифметическим сдвигом. Так выглядит арифметический сдвиг влево (умножение на 2)
(-46)*2 = 0b11010010 << 1 = 0b10100100 = -92
и арифметический сдвиг вправо (деление на 2)
(-46)/2 = 0b11010010 >> 1 = 0b11101001 = -23 .

Последнее действие выполняется командой asr Rd.

При округлении отрицательных чисел нужно придерживаться следующего правила. Если после знакового деления
X_S/Y_S = Z_S + R_S
образовался целочисленный остаток |R_S| ≥ 0,5*|Y_S|, то к частному
Z_S нужно добавить единицу; в противном случае Z_S остается без изменений. Например,
X_S = -23 = 0b11101001, Y_S = 2,
X_S/Y_S = Z_S + R_S = [-12] + {1},
Z_S ≈ (-12) + 1 = -11 = 0b11110101.

Подобие алгоритмов деления на целую степень 2 у беззнаковых и знаковых чисел, позволяет очень просто реализовать важный частный случай деления на 3 (см. рис.8,  Беззнаковые числа) на основе того же ряда
X_S/3 = X_S/2 - X_S/4 + X_S/8 - X_S/16 + X_S/32 - …

Подпрограмма деления 2-байтового знакового числа:

; R19:R18 = R17:R16/3
; R19:R18 – знаковое частное
; R17:R16 – знаковое делимое
; R20 – вспомогательный регистр
 
divs16to3:
    clr   R18      ;очищаем вспомогательные регистры R18,R19
    clr   R19      ;при входе в подпрограмму   
ds1: rcall ashft_right
	brcc  PC+2     ;если C=1, 
    ret            ;то завершаем деление
    add   R18,R16  ;в ином случае добавляем к накопителю
	adc   R19,R17  ;очередной нечётный член ряда
	rcall shift_right
	brcc  PC+2     ;если C=1,
	ret            ;то завершаем деление
    sub   R18,R16  ;в ином случае вычитаем из накопителя
	sbc   R19,R17  ;очередной чётный член ряда
    rjmp  ds1

ashft_right: 
    asr   R17      ;производим знаковое деление R17:R16 / 2,
	ror   R16      ;получая очередной член ряда
	clr   R20      ;если R20 = R17:R16 + С = 0x10000
	adc   R20,R16  ;( т.е. знаковое число R17:R16 = 0),
	clr   R20      ;то выходим из подпрограммы с флагом С=1
 	adc   R20,R17
	ret

Перейти к следующей части: Преобразование чисел - Изменение масштаба числовых величин

Теги:

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