Вычитание Mips из 64-битных чисел

Меня попросили реализовать вычитание 64-битных чисел в Mips, при этом числа задаются в дополнении до 2, а младшие/верхние 32 бита хранятся в разных регистрах. Мои мысли: сначала вычитаем нижние части, а потом верхние. Проблемная ситуация возникает, если младший номер части первого числа меньше, чем у второго числа, т.е. при рассмотрении небольшого примера, где у нас есть только 4-битные регистры.

 0110 0011 
-0010 1000

Итак, сначала нижняя часть

 0000 0011    0000 0011
-0000 1000 = +1111 1000 = 1111 1011

а потом верхняя часть

 0110 0000    0110 0000
-0010 0000 = +1110 0000 = 0100 0000

а затем сложить две части вместе

 0100 0000
+1111 1011 = 0011 1011

Тогда моя реализация Mips будет выглядеть примерно так (для простоты регистры 1-8):

// A-B
lw  $1, 0($8) // upper part of A
lw  $2, 4($8) // lower part of A
lw  $3, 8($8) // upper part of B
lw  $4, 12($8) // lower part of B

subu $5, $2, $4
stlu $6, $2, $4 // if lower part of A < lower part of B we need to add 1111 0000 i.e. 
                // subtract 1 from upper part result
subu $7, $1, $3
subu $7, $7, $6

// Now the upper part of the result is stored in $7$ and the lower part in $5

Моя мысль кажется правильной?


subtraction bigint assembly mips
person Herkules Ol    schedule 21.07.2021    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Сравните, что делают GCC и clang для вычитания uint64_t на 32-битных MIPS: https://godbolt.org/z/eGY3aWoKq .

Да, sltu для генерации вывода заимствования из нижней половины, плюс 3x subu - правильное сочетание инструкций. Сделайте младшую половину вычитания, вычтите старшую половину и займите.

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

На ISA с флагом переноса/заимствования (например, x86 или ARM https://godbolt.org/z/sfG5PzsPW), вы бы сделали

     subs    r0, r0, r2      # sub low half and set flags
     sbc     r1, r1, r3      # sub-with-carry does high half including borrow

ARM и x86 устанавливают свой флаг переноса напротив друг друга для вычитания (!заимствовать или заимствовать), но оба предназначены для цепочки от младшего к старшему в порядке переноса-распространения, поэтому это всего 2 инструкции.

# clang -O3 -m32 -mregparm=3   first uint64_t passed in EDX:EAX, second in mem
     sub     eax, dword ptr [esp + 4]
     sbb     edx, dword ptr [esp + 8]    # x86 sub-with-borrow

Поскольку MIPS не имеет флагов, вам нужно вручную обрабатывать распространение переноса/заимствования, но это все, что вы делаете.

Это становится более неудобным для более широких целых чисел, когда вам нужно обрабатывать заимствование и вывода, потому что эмуляция sbb, включая вывод переноса, требует проверки переноса после вычитания заимствования и после вычитания целочисленных операндов. Так же, как для эмуляции adc

person Peter Cordes    schedule 21.07.2021
comment
Правильно ли мое объяснение с примером 4-битного регистра? Я изо всех сил пытался немного понять значение заимствования здесь. - person Herkules Ol; 21.07.2021
comment
@HerkulesOl: когда двоичное вычитание выполняет 0 - 1, оно создает заимствование, которое распространяется на следующий более значащий бит. Через границу между регистрами это результат заимствования 32-битной операции sub. Точно так же, как сложение производит перенос из полного сумматора (en.wikipedia. org/wiki/Adder_(electronics)#Full_adder). Без выхода FLAGS из ALU вы выполняете carry = (a+b) < a беззнаковое сравнение для сложения, но для вычитания результат заимствования из a-b равен просто borrow = a<b. С точки зрения дополнения до двух с бесконечными ведущими нулями, заимствование переворачивает их все. - person Peter Cordes; 21.07.2021
comment
@HerkulesOl: Так что ваш способ, безусловно, слишком сложен: как я уже сказал, вам не нужно превращать его в дополнение. И, кроме того, большинство способов сделать это неправильно сохраняют вывод переноса/заимствования sub для каждого возможного ввода (или для MIPS неправильно воспроизводят результат sltu). В Арифметические тождества и EFLAGS обсуждается попытка эмулировать вывод заимствования реальной инструкции x86 sub, что эквивалентно эмуляции результата MIPS sltu. - person Peter Cordes; 21.07.2021
comment
но разве вычитание дополнительных чисел 2 просто не преобразуется в сложение? - person Herkules Ol; 22.07.2021
comment
и можете ли вы порекомендовать какой-либо ресурс, где я могу больше узнать о заимствовании при выполнении вычитания? - person Herkules Ol; 22.07.2021
comment
@HerkulesOl: Однако аппаратное ALU реализует вычитание внутри, оно должно выдавать правильный вывод во флаге переноса. (Если только это не ISA, например MIPS, без регистра флагов.) Но обратите внимание, что выполнение x - y как x + (~x + 1) включает две операции сложения. Добавление константы 1 все еще может переносить все биты, хотя я думаю, вы могли бы упростить от полных сумматоров до просто вентилей xor для распространения переноса. Я не уверен, как вычитание обычно выполняется в современных ALU, но я думаю, что обычно оно не требует отдельного шага для фактического создания -y в первую очередь. - person Peter Cordes; 22.07.2021
comment
@HerkulesOl: Re: заимствование. В двоичном формате это работает так же, как и в начальной школе для десятичного числа, например. smartick.com/blog/math/learning-resources/subtract-заимствование . Очевидно, что в базе 2 заимствование равно либо 0, либо 1 из любой заданной битовой позиции. - person Peter Cordes; 22.07.2021