恢复Risc V中的除法算法

Question

我想用RISCV汇编语言实现恢复除法算法（不使用div操作）。

我必须实现的算法如下 .

我实现了这个，但它不起作用（考虑

a0

注册股息和

a1

注册除数）。

.data
a: .word 3
b: .word 7
stringa_overflow: .string "Overflow nella divisone"
stringa_div_0: .string "Divisione per 0"


.text
lw a1 a #loading the divisor 
lw a0 b #loading the dividend

jal div
end:
li a7 10
ecall

div:
    addi sp sp -4 #stack for return address
    sw ra 0(sp) #saving the return addrest
    add a2 zero a0 #remainder initially set as the dividend
    addi a3 zero 0 #Quotient initially set as the remainder
    addi t6 t6 32
    jal controllo_segno_div
    loop:
    sub a2 a2 a1
    bge a2 zero resto_mag0
    add a2 a2 a1
    slli a3 a3 1
    andi t4 a3 1
    beq t4 zero fine_div
    addi t5 a3 -1
    and a3 a3 t5
    j fine_div
    resto_mag0:
    slli a3 a3 1
    andi t4 a3 1 #LSB quotient
    bne t4 zero fine_div
    addi t5 a3 1
    or a3 a3 t5
    fine_div:
    srli a1 a1 1
    addi t6 t6 -1
    bne t6 zero loop
    
    lw ra 0(sp)
    jr ra

#This procedure changes the sign of the operands so that they are both #positive
controllo_segno_div:
    beq a1 zero divide_0 #this gives an error if we are dividing by 0
    bge a0 zero secondo_controllo
    sub a0 zero a0
    addi t2 t2 1
    secondo_controllo:
    bge a1 zero fine_controllo 
    sub a1 zero a1
    addi t3 t3 1
    fine_controllo:
    jr ra
    
    divide_0:
    la a0 stringa_div_0
    li a7 4
    ecall
    j end
    
    
 

我知道除数应该（在第一步）放在 64 位块的左侧部分（我们考虑 32 位无符号整数），但我不知道该怎么做。 如果可能的话，写一些汇编代码，因为英语不是我的母语。 教授给出的其他信息（关于如何初始化变量）是这个 谢谢你

Answer 1

这里最大的障碍似乎是问题顶部的流程图要么不完整，要么完全不正确。起初，我对流程图中显示的除数右移感到困惑，因为大多数逐位除法算法保持除数不变，而是对部分余数和商的串联应用左移。然后我想起 Niklaus Wirth 在他的书系统编程中提出了这样一种移位除数方法。

Wirth 的方法是我们在小学学到的十进制长手除法的二进制模拟，它要求我们将除数的最高有效位与被除数的最高有效位对齐，然后开始进行减法迭代以确定商位。同样，Wirth 算法要求我们“标准化”除数，以便除数和被除数的最高有效 1 位位于相同的位位置。流程图中缺少的正是这个准备步骤。通过简单地右移除数，除数的低位就被一一丢失。问题底部的硬件图同样值得怀疑，因为 32 位除法不需要 64 位 ALU，也不需要 64 位除数和余数寄存器。最多需要 64 位移一能力。

Wirth给出的归一化方法在有限精度无符号整数运算中由于中间计算的溢出而不正确。除数归一化的正确规范方法是计算两个操作数的前导零，其差异表明除数需要左移多少位。各种处理器架构都有专门的指令，通常称为

CLZ

，但基本 RISC-V 没有这样的指令。操作可以模拟，有点繁琐。在 2008 年的研究报告中，Rodeheffer 给出了一种修改后的结构，它避免了溢出问题，并且不需要计数前导零原语。

由于我不熟悉 RISC-V 汇编语言，因此我在下面显示了 ISO-C99 代码，该代码应 1:1 转换为 32 位 RISC-V 的汇编代码。我展示的是直接基于 Wirth 算法的变体以及基于 Rodeheffer 修改的变体。

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

#define USE_WIRTH (1)
#define NUM_TESTS (10000000000ULL)

#if USE_WIRTH
/* Based on N. Wirth, "Systematic Programming", 1973, section 7.3 */

/* count leading zeros */
int clz (uint32_t a)
{
    uint32_t b;
    int n = 32;
    if ((b = (a >> 16))) { n -= 16;  a = b; }
    if ((b = (a >>  8))) { n -=  8;  a = b; }
    if ((b = (a >>  4))) { n -=  4;  a = b; }
    if ((b = (a >>  2))) { n -=  2;  a = b; }
    if ((    (a >>  1))) return n - 2;
    return n - (int)a;
}

uint32_t udiv (uint32_t x, uint32_t y)
{
    uint32_t remainder = x;
    uint32_t quotient = 0;
    uint32_t divisor = y;
    int reps;
    if (x >= y) {
        reps = clz (divisor) - clz (remainder); // bits in quotient
        divisor = divisor << reps;              // normalize divisor
        do {
            remainder = remainder - divisor;    // preliminary partial remainder
            if ((int32_t)remainder >= 0) {      // partial remainder non-negative
                quotient = quotient << 1 | 1;   // record quotient bit: 1
            } else {
                remainder = remainder + divisor;// restore remainder
                quotient = quotient << 1 | 0;   // record quotient bit: 0
            }
            divisor = divisor >> 1;             // halve divisor
            reps = reps - 1;
        } while (reps >= 0);                    // until all quotient bits done
    }
    return quotient; 
}
#else // !USE_WIRTH
/* Based on Thomas L. Rodeheffer, "Software Integer Division". 
   Microsoft Research Report, Apr. 2008, fig. 2 
*/
uint32_t udiv (uint32_t x, uint32_t y)
{
    uint32_t remainder = x;
    uint32_t quotient = 0;
    uint32_t divisor = y;
    if (x >= divisor) {
        x = x - divisor;
        while (x >= divisor) {                  // normalize divisor
            x = x - divisor;
            divisor = divisor << 1;
        }
        do {
            remainder = remainder - divisor;    // preliminary partial remainder
            if ((int32_t)remainder >= 0) {      // partial remainder non-negative
                quotient = (quotient << 1) | 1; // record quotient bit: 1
            } else {
                remainder = remainder + divisor;// restore remainder
                quotient = (quotient << 1) | 0; // record quotient bit: 0
            }
            if (divisor == y) break;
            divisor = divisor >> 1;             // halve divisor
        } while (1);
    }
    return quotient;
}
#endif // USE_WIRTH

// George Marsaglia's KISS PRNG, period 2**123. Newsgroup sci.math, 21 Jan 1999
// Bug fix: Greg Rose, "KISS: A Bit Too Simple" http://eprint.iacr.org/2011/007
static uint32_t kiss_z=362436069, kiss_w=521288629;
static uint32_t kiss_jsr=123456789, kiss_jcong=380116160;
#define znew (kiss_z=36969*(kiss_z&65535)+(kiss_z>>16))
#define wnew (kiss_w=18000*(kiss_w&65535)+(kiss_w>>16))
#define MWC  ((znew<<16)+wnew )
#define SHR3 (kiss_jsr^=(kiss_jsr<<13),kiss_jsr^=(kiss_jsr>>17), \
              kiss_jsr^=(kiss_jsr<<5))
#define CONG (kiss_jcong=69069*kiss_jcong+1234567)
#define KISS ((MWC^CONG)+SHR3)

int main (void)
{
    unsigned long long int count = 0;
    uint32_t dividend, divisor, res, ref;
    do {
        dividend = KISS;
        do {
            divisor = KISS;
        } while (divisor == 0);
        ref = dividend / divisor;
        res = udiv (dividend, divisor);
        if (res != ref) {
            printf ("dividend=%08x divisor=%08x res=%08x ref=%08x\n", dividend, divisor, res, ref);
            return EXIT_FAILURE;
        }
        count++;
        if ((count & 0xffffff) == 0) printf ("\rcount=%llu", count);
    } while (count < NUM_TESTS);
    return EXIT_SUCCESS;
}

我后来注意到问题中的流程图和硬件图来自 Patterson 和 Hennessy，“计算机组织与设计：硬件/软件接口”，1994 年，第 4.7 节。因此，它似乎代表了一个说教而不是一个现实生活中的例子。我可以完成所描述的工作的唯一方法是通过模拟带有进位的减法来指示减法后部分余数是否为负：

/* Use SPARC semantics: For a subtraction, carry is set to 1 if the subtraction 
   produced a borrow and to 0 otherwise. 
*/
/* subtraction with carry-out */
#define SUBcc(a,b,cy,t0,t1) \
    (t0=(b), t1=(a), cy=t1<t0, t1-t0)

uint32_t udiv (uint32_t x, uint32_t y)
{
    uint64_t divisor = ((uint64_t)y) << 32;
    uint64_t remainder = x;
    uint64_t t0, t1;
    uint32_t cy, quotient = 0;
    int reps = 0;
    do {
        remainder = SUBcc (remainder, divisor, cy, t0, t1); // new remainder
        if (cy == 0) {                      // remainder non-negative
            quotient = quotient << 1 | 1;   // record quotient bit: 1
        } else {
            remainder = remainder + divisor;// restore old remainder
            quotient = quotient << 1 | 0;   // record quotient bit: 0
        }
        divisor = divisor >> 1;             // halve divisor
        reps = reps + 1;
    } while (reps < 33);
    return quotient; 
}

在 32 位 RISC-V 平台上，必须模拟所有 64 位操作。