Математический вопрос, Программирование на ассемблере Опции

[d7d1cd]

Привет всем. Я программирую на ассемблере. В моей программе все числа хранятся в 32-х разрядах. Соответственно, математические операции (умножение, деление и прочие), реализованы с помощью функций, которые так же работают с 32-х разрядными числами.
Сейчас возникла такая проблема. Мне необходимо сделать вычисления по следующей формуле: X = A * B / C. Числа A, B, C, X - 32-х разрядные. Результат в Х точно поместится в 32 разряда, но при выполнении операции А*В может получится 64-х разрядное число. Подскажите, возможно ли, не прибегая к использованию 64-х разрядных функций и чисел, выполнить вычисления по формуле?

P.S. Функция деления возвращает 2 результата: частное и остаток. Все числа исключительно положительные.

[Xenia]

... но при выполнении операции А*В может получится 64-х разрядное число. Подскажите, возможно ли, не прибегая к использованию 64-х разрядных функций и чисел, выполнить вычисления по формуле?

Откуда такое ограничение? Чем, собственно, плохо 64-разрядное число в качестве промежуточного результата?

[d7d1cd]

Откуда такое ограничение? Чем, собственно, плохо 64-разрядное число в качестве промежуточного результата?

Для этого надо писать функцию умножения с получением 64-х разрядного результата, а так же функцию деления 64-х разрядного числа. Я не случайно пишу на асме: у меня места под мою программу очень мало и лишние функции это не айс. Если бы в моем распоряжении была вся память, то я бы писал на С и не задавал таких вопросов.

[lekintr]

Результат в Х точно поместится в 32 разряда, но при выполнении операции А*В может получится 64-х разрядное число.
P.S. Функция деления возвращает 2 результата: частное и остаток. Все числа исключительно положительные.

Если два числа умноженные друг на друга дают 32 разрядное число, значит сами эти числа можно уместить в 16 разрядов. Ну так преобразуйте множители в 16 разрядов и умножайте хоть до посинения...

Сообщение отредактировал lekintr - Dec 21 2013, 17:15

[d7d1cd]

Ну вообще то под словами "результат в Х" понимается результат от А*В/С. Два числа (А и В), умноженные друг на друга, как раз могут и не поместиться в 32 разряда.

[kovigor]

Ну вообще то под словами "результат в Х" понимается результат от А*В/С. Два числа (А и В), умноженные друг на друга, как раз могут и не поместиться в 32 разряда.

А что мешает "A" разделить на "C" и полученный результат умножить на "B" ?

И вообще, если вы не делаете достаточно крупную серию, возьмите более подходящий МК и пишите на Си. Есть, конечно, исключения, но в общем случае выбор для проекта такого МК, который подходит "впритык", есть признак дурного тона. А если завтра потребуется простейшая модернизация ПО, что вы станете делать ?

[Егоров]

Хм.. так 32 разряда - точность. Умножайте спокойно и 32 младших разряда отбрасывайте.
Иначе, при 64-разрядном процессоре Вы тоже встанете в тупик - куда девать результат в 128 разрядов? И так без конца.
На 8-битных процессорах почему-то таких проблем не возникало раньше. Считали с любой требуемой точностью.
Как мы в столбик считаем до 1% или 0.1% ? Младшие разряды отбрасываем, или округляем.

[d7d1cd]

А что мешает "A" разделить на "C" и полученный результат умножить на "B" ?

Ничего не мешает. Разве только потеря точности. Ведь деление то целочисленное. Или как то можно остаток использовать?

И вообще, если вы не делаете достаточно крупную серию, возьмите более подходящий МК и пишите на Си. Есть, конечно, исключения, но в общем случае выбор для проекта такого МК, который подходит "впритык", есть признак дурного тона. А если завтра потребуется простейшая модернизация ПО, что вы станете делать ?

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

Хм.. так 32 разряда - точность. Умножайте спокойно и 32 младших разряда отбрасывайте.
Иначе, при 64-разрядном процессоре Вы тоже встанете в тупик - куда девать результат в 128 разрядов? И так без конца.
На 8-битных процессорах почему-то таких проблем не возникало раньше. Считали с любой требуемой точностью.
Как мы в столбик считаем до 1% или 0.1% ? Младшие разряды отбрасываем, или округляем.

Представьте такую ситуацию в моей программе: A=0x3B8B87C0, B=0x34EDCE00, C=0x2E501440. Если выполнить целочисленную арифметику по моей формуле (с использованием любого количества разрядов), то результат будет: X = 0x440D2D6D. Такой результат должна выдавать моя программа.
Теперь по Вашему совету:
1. A*B = 0x3B8B87C0 * 0x34EDCE00 = 0xC4FA7A9F3FC8000
2. Отбрасываем младшие 32 разряда: 0xC4FA7A9F
3. Выполняем деление: 0xC4FA7A9F / 0x2E501440 = 0х00000004
4. Как я понимаю, возвращаем "утраченные" разряды: 0х40000000

Видно, что 0x440D2D6D и 0х40000000 даже приблизительно не равны. Или я чего не правильно сделал???

[PRidon]

Ну есть один вариант. Делал похожее умножение на 8ми битке.
Пусть XY и AB - исходные числа. (каждая буква - 16 бит)
XY*AB= CDEF
где CD = X*A + 'старшие 16 бит'(A*Y+B*X),
EF = 'младшие 16 бит'(A*Y+B*X) + Y*B,
т.е. получаем 2 числа по 32 бита. Причем получаем оперируя только 32х битными числами.
Деление выполняется так же.
Единственный минус: на 3 больше умножений и на 2 больше делений. Ну а если уже написанная функция возвращает и остаток, и результат деления, то проблем быть не должно.

[d7d1cd]

Ну есть один вариант. Делал похожее умножение на 8ми битке.
Пусть XY и AB - исходные числа. (каждая буква - 16 бит)
XY*AB= CDEF
где CD = X*A + 'старшие 16 бит'(A*Y+B*X),
EF = 'младшие 16 бит'(A*Y+B*X) + Y*B,
т.е. получаем 2 числа по 32 бита. Причем получаем оперируя только 32х битными числами.
Деление выполняется так же.
Единственный минус: на 3 больше умножений и на 2 больше делений. Ну а если уже написанная функция возвращает и остаток, и результат деления, то проблем быть не должно.

Спасибо за совет. Вот сейчас именно то, что надо. Но я тоже долго размышлял над задачей и подумал, что мне лучше переписать функции умножения и деления. То есть, функция деления должна делить 64-х битное число на 32-х битное и возвращать 32-х битное, а функция умножения должна перемножать 32-х битные числа и возвращать 64-х битное.
Функцию деления, я думаю, переписать смогу, а вот с функцией умножения загвоздка. Я хочу применить аппаратный умножитель, но не совсем разбираюсь в его регистрах. Функция умножения 32-х битных чисел и возвращения 32-х битного результата выглядит так:

Код

mov.w   R12,&MPY
mov.w   R14,&OP2
mov.w   R12,&MAC
mov.w   &RESLO,R12
mov.w   &RESHI,&RESLO
mov.w   R15,&OP2
mov.w   R13,&MAC
mov.w   R14,&OP2
mov.w   &RESLO,R13

В этой функции R12 и R13 - это первый множитель (R12 - младшее слово), R14 и R15 - второй множитель (R14 младшее слово). Результат я получаю в регистрах R12 и R13 (R12 - младшее слово). Подскажите, как мне получить 64-х битный результат умножения (в регистрах R12-R15)?

[PRidon]

Процессор та какой?
Если умножитель аппаратный, то либо 16х16=32, либо 32х32=64. А 32х32=32 - смысла особого не имеет.

Код

mov.w   R15,&MPY;загружаем 1е операнды (15х13)
mov.w   R13,&OP2
; 3 такта ждать
mov.w   &RESHI,R15; результат
mov.w   &RESLO,&RESHI
mov.w   &MPY ,&MAC;загружаем 2е операнды с суммированием результата (15х12) Если такая форма сработает - все получится. Если нет, готовь еще 4 регистра.
mov.w   R12,&OP2
; 3 такта ждать
add.w    &SUMEXT,R15; учитываем переполнение
mov.w   R14,&MAC;загружаем 3е операнды с суммированием результата (14х13)
mov.w   R13,&OP2
; 3 такта ждать
add.w    &SUMEXT,R15; учитываем переполнение
mov.w   &RESHI,R14   ; записываем результат
mov.w   &RESLO,&RESHI
mov.w   R12,&OP2      ; загружаем 4е операнды с суммированием результата (14х12)
; 3 такта ждать
add.w    &SUMEXT,R14; учитываем переполнение
; тут надо проверить переполнение через SR. И если флаг стоит - inc R15
mov.w   &RESHI,R13  ; опять же результат
mov.w   &RESLO,R12  ; и последний результат

Проверить возможности нет. Но мысля что будет работать.
Сработает если после чтения регистров RESLO и RESHI они обнуляются, в UG про это ничего не написано. Так же не очень понятно по какому принципу будет определяться 1й операнд. Если по последней записи, то должно работать.
зы: и да, на умножение нужно 3 такта. Не стоит забывать про это, особенно на асе.

[d7d1cd]

Пусть XY и AB - исходные числа. (каждая буква - 16 бит)
XY*AB= CDEF
где CD = X*A + 'старшие 16 бит'(A*Y+B*X),
EF = 'младшие 16 бит'(A*Y+B*X) + Y*B,
т.е. получаем 2 числа по 32 бита. Причем получаем оперируя только 32х битными числами.

Кстати тут есть вопрос. Если выполнить A*Y+B*X, когда А=B=Y=X=0xFFFF, то получится 0х1FFFC0002, то есть число размером большее, чем 32 бита. Уже оперируем не 32-х битными значениями. Как из этого значения получить 'младшие 16 бит' понятно - это 0002. А как из этого числа получить 'старшие 16 бит' непонятно. По всей логике - это 0001. Что скажите?

[PRidon]

Это обычное умножение столбиком. Что переполняется - увеличение старших разрядов. В приведенном мной коде это тоже учитывается. В частности в MSP430 есть статусный регистр, а в нем флаг переполнения. Да и в HM есть свой похожий регистр - SUMEXT, который я и использую.

[d7d1cd]

Итак, умножению иною реализовано. Вот код:

Код

//***** БЕЗЗНАКОВОЕ УМНОЖЕНИЕ 32-Х РАЗРЯДНОГО ЧИСЛА НА 32-Х РАЗРЯДНОЕ С ПОЛУЧЕНИЕМ 64-Х РАЗРЯДНОГО РЕЗУЛЬТАТА
;       R12, R13 - первый множитель. R12 - младшее слово
;       R14, R15 - второй множитель. R14 - младшее слово
Mul32u32uTo64u:                            
        MOV     R12, &MPY
        MOV     R14, &OP2
        MOV     R12, &MAC
        MOV     &RESLO, R12
        MOV     &RESHI, &RESLO
        CLR     &RESHI
        MOV     R15, &OP2
        MOV     R13, &MAC
        MOV     R14, &OP2
        MOV     R13, &MAC
        MOV     &RESLO, R13
        MOV     &RESHI, &RESLO
        MOV     &SUMEXT, &RESHI
        MOV     R15, &OP2
        MOV     &RESLO, R14
        MOV     &RESHI, R15
        RET
;       R12, R13, R14, R15 - произведение. R12 - младшее слово

Я думал, что с делением проблем не будет. Но оказалось, что будет... Сейчас думаю. Вопросов пока задавать не буду...

[PRidon]

как разберешься с делением - выложи результат. Полезная вещь.

[demiurg_spb]

Я бы, прежде чем изобретать велосипед, ознакомился с исходниками компилятора.
Либо просто написал на Си умножение-деление, собрал проект и посмотрел листинг дизассемблера.

http://sourceforge.net/projects/mspgcc/

[d7d1cd]

как разберешься с делением - выложи результат. Полезная вещь.

Разобрался. А попутно подправил функцию умножения. Привожу код.

CODE

//БЕЗЗНАКОВОЕ УМНОЖЕНИЕ 32-Х РАЗРЯДНОГО ЧИСЛА НА 32-Х РАЗРЯДНОЕ С ПОЛУЧЕНИЕМ 64-Х РАЗРЯДНОГО РЕЗУЛЬТАТА
; R12, R13 - первый множитель. R12 - младшее слово
; R14, R15 - второй множитель. R14 - младшее слово
Mul32u32uTo64u:
DINT
NOP
MOV R12, &MPY
MOV R14, &OP2
MOV R12, &MAC
MOV &RESLO, R12
MOV &RESHI, &RESLO
CLR &RESHI
MOV R15, &OP2
MOV R13, &MAC
MOV R14, &OP2
MOV &RESLO, R13
MOV &RESHI, &RESLO
MOV &SUMEXT, &RESHI
MOV R15, &OP2
MOV &RESLO, R14
MOV &RESHI, R15
EINT
RET
; R12, R13, R14, R15 - произведение. R12 - младшее слово

CODE

//БЕЗЗНАКОВОЕ ДЕЛЕНИЕ 64-Х РАЗРЯДНОГО ЧИСЛА НА 32-Х РАЗРЯДНОЕ С ПОЛУЧЕНИЕМ 64-Х РАЗРЯДНОГО ЧАСТНОГО И 32-Х РАЗРЯДНОГО ОСТАТКА
; R12, R13, R14, R15 - делимое. R12 - младшее слово
; R10, R11 - делитель. R10 - младшее слово
Div64u32uTo64u:
PUSH R6
PUSH R7
PUSH R8
PUSH R9
CLR R7
CLR R8
CLR R9
MOV #64, R6

Div64u32uTo64u_MainLoop:
RLA R12
RLC R13
RLC R14
RLC R15
RLC R7
RLC R8
RLC R9
SUB R10, R7
SUBC R11, R8
SUBC #0, R9
JNC Div64u32uTo64u_AddBalance
BIS #1, R12

Div64u32uTo64u_DecCounter:
DEC R6
JNZ Div64u32uTo64u_MainLoop
JMP Div64u32uTo64u_Exit

Div64u32uTo64u_AddBalance:
ADD R10, R7
ADDC R11, R8
ADDC #0, R9
JMP Div64u32uTo64u_DecCounter

Div64u32uTo64u_Exit:
MOV R7, R10
MOV R8, R11
POP R9
POP R8
POP R7
POP R6
RET
; R12, R13, R14, R15 - частное. R12 - младшее слово
; R10, R11 - остаток. R10 - младшее слово

Я бы, прежде чем изобретать велосипед, ознакомился с исходниками компилятора.
Либо просто написал на Си умножение-деление, собрал проект и посмотрел листинг дизассемблера.

http://sourceforge.net/projects/mspgcc/

Безусловно, я так и делал. Однако пришлось немного пересобрать велосипед под свои нужды, так как компилятор собирает слишком большой велосипед. Для наглядности привожу код функций деления и умножения. Сразу видно, что он гораздо больше моего кода. Но, конечно, он более универсален.

CODE

_Mul64iHw:
push.w SR
dint
nop
push.w R6
push.w R7
sub.w #0x4,SP
mov.w R12,&MPY
mov.w R11,&OP2
mov.w R13,&MAC
mov.w R10,&OP2
mov.w R14,&MAC
mov.w R9,&OP2
mov.w R15,&MAC
mov.w R8,&OP2
mov.w &RESLO,0x2(SP)
mov.w R12,&MPY
mov.w R10,&OP2
mov.w R13,&MAC
mov.w R9,&OP2
mov.w R14,&MAC
mov.w R8,&OP2
mov.w &RESLO,0x0(SP)
mov.w &RESHI,R7
mov.w R12,&MPY
mov.w R9,&OP2
mov.w R13,&MAC
mov.w R8,&OP2
mov.w &RESLO,R10
mov.w &RESHI,R9
mov.w &SUMEXT,R11
mov.w R12,&MPY
mov.w R8,&OP2
mov.w &RESLO,R8
mov.w &RESHI,R15
push.w R11
push.w R9
push.w R10
push.w #0x0
mov.w R15,R9
pop.w R12
pop.w R13
pop.w R14
pop.w R15
add.w R8,R12
addc.w R9,R13
adc.w R14
adc.w R15
mov.w @SP,R6
mov.w 0x2(SP),R11
add.w R11,R7
add.w R6,R14
addc.w R7,R15
add.w #0x4,SP
pop.w R7
pop.w R6
reti

_Div64u:
push.w R6
push.w R11
push.w R10
push.w R9
push.w R8
sub.w #0x10,SP
mov.w R12,0x8(SP)
mov.w R13,0xA(SP)
mov.w R14,0xC(SP)
mov.w R15,0xE(SP)
clr.w 0x0(SP)
clr.w 0x2(SP)
clr.w 0x4(SP)
clr.w 0x6(SP)
clr.w R8
clr.w R9
clr.w R10
clr.w R11
mov.b #0x40,R6
call #Mul2
bit.w #0x8000,0xE(SP)
subc.w R12,R12
inc.w R12
rla.w R8
rlc.w R9
rlc.w R10
rlc.w R11
bis.w R12,R8
rla.w 0x8(SP)
rlc.w 0xA(SP)
rlc.w 0xC(SP)
rlc.w 0xE(SP)
cmp.w 0x16(SP),R11
jnc 0x11A8
jne 0x1194
cmp.w 0x14(SP),R10
jnc 0x11A8
jne 0x1194
cmp.w 0x12(SP),R9
jnc 0x11A8
jne 0x1194
cmp.w 0x10(SP),R8
jnc 0x11A8
sub.w 0x10(SP),R8
subc.w 0x12(SP),R9
subc.w 0x14(SP),R10
subc.w 0x16(SP),R11
bis.w #0x1,0x0(SP)
add.b #0xFF,R6
jne 0x1146
mov.w @SP,R12
mov.w 0x2(SP),R13
mov.w 0x4(SP),R14
mov.w 0x6(SP),R15
add.w #0x18,SP
pop.w R6
ret

Mul2:
rla.w 0x2(SP)
rlc.w 0x4(SP)
rlc.w 0x6(SP)
rlc.w 0x8(SP)
ret

Сообщение отредактировал d7d1cd - Dec 26 2013, 10:58