排序算法实现在MIPS

Question

我写了一个MIPS相当于下面的C快速排序程序

while(L<=R){ 
    if(A[M] < n) 
    L=M+1; 
    else if(A[M]==n){ 
     printf("%d found in %d\n",n,M); 
     break; 
    } 
    else 
     R=M-1; 
    M=(L+R)/2; 
} 

其中我写了MIPS等同，我有检查程序用于任何其他错误，但它没有表现出一个

# $t0 is index of Leftmost entry of array considered 
# $t3 is index of Rightmost entry of array considered 
# $t1 is index of MIddle entry of array considered 
# $t2 is the adderess of middle entry (i.e. $t1*4) 
# myArray is an array I took as input , with $s1 elements 
     addi $t0, $zero, 0 # $t0 stores left 
    add $t1, $s1, $t0 
    srl $t1, $t1, 1 #stores mid 
    sll $t2, $t1, 2 
    add $t3, $s1, $zero 

    BinSearch: 
    bge $t0, $t3 , exit 
    lw $t6, myArray($t2) 

    blt $t6, $s2, leftindex  # if(A[mid]<k) goto left 
    beq $t6, $s2, found 
    bgt $t6, $t2, rightindex 


    leftindex: 
    addi $t0, $t1, 1  # left index leftindex= mid + 1 
    add $t1, $t3, $t0  # mid = left + right 
    srl $t1, $t1, 1 
    sll $t2, $t1, 2 
    j BinSearch    #goback to Binary Search 

    found: 
    li $v0, 1 
    add $a0, $t1, $zero 
    syscall 
    j exit     #exit programme 

    rightindex:    
    addi $t3, $t1, -1 #rightindex = mid -1 
    add $t1, $t3, $t0 #mid = left+right 
    srl $t1, $t1, 1 
    sll $t2, $t1, 2 #mid/2 
    j BinSearch   #goback to binarysearch 

我已经检查过，如果我把数组作为输入或如果我犯了其他愚蠢的错误的错误。

所以我的问题是，是否有一些错误，我在执行算法在MIPS中犯了错误？或者我做了什么其他错误？ 预先感谢您。

Answer 1

我觉得有一些错误。

首先，设置R（即$t3）时，它被设定为所述阵列计数，但它应被设置为计数 - 1

其次，基于C代码，所述bge for循环出口应该bgt

三，跟踪C代码，该bgt到rightIndex应该b（即无条件分支）

我创建你的代码的两个版本。一个注释一个，修正错误和一些简化[请原谅无偿风格的清理]。

这里的注解之一：

# $s1 is count of array 
# $t0 is index of Leftmost entry of array considered 
# $t3 is index of Rightmost entry of array considered 
# $t1 is index of Middle entry of array considered 
# $t2 is the address of middle entry (i.e. $t1*4) 
# myArray is an array I took as input , with $s1 elements 
    addi $t0,$zero,0    # $t0 stores left 
    add  $t1,$s1,$t0 
    srl  $t1,$t1,1    # stores mid 
    sll  $t2,$t1,2 

# NOTE/BUG: if C were the array count, this sets R = C, but we need R = C - 1 
# so change this as follows: 
    ###add  $t3,$s1,$zero 
    addi  $t3,$s1,-1 

# NOTE/BUG: based on the C code, the bge should be bgt 
BinSearch: 
    ###bge  $t0,$t3,exit 
    bgt  $t0,$t3,exit 
    lw  $t6,myArray($t2) 

    blt  $t6,$s2,leftindex  # if(A[mid]<k) goto left 
    beq  $t6,$s2,found 

# NOTE/BUG: to track the C code, this should be uncondition 
    ###bgt  $t6,$t2,rightindex 
    b  rightindex 

leftindex: 
    addi $t0,$t1,1    # left index leftindex= mid + 1 
    add  $t1,$t3,$t0    # mid = left + right 
    srl  $t1,$t1,1 
    sll  $t2,$t1,2 
    j  BinSearch    # goback to Binary Search 

found: 
    li  $v0,1 
    add  $a0,$t1,$zero 
    syscall 
    j  exit     # exit programme 

rightindex: 
    addi $t3,$t1,-1    # rightindex = mid -1 
    add  $t1,$t3,$t0    # mid = left+right 
    srl  $t1,$t1,1 
    sll  $t2,$t1,2    # mid/2 
    j  BinSearch    # goback to binarysearch 

---

这里的清理和简化的一个：

# $s1 is count of array 
# $t0 is index of Leftmost entry of array considered 
# $t3 is index of Rightmost entry of array considered 
# $t1 is index of Middle entry of array considered 
# $t2 is the address of middle entry (i.e. $t1*4) 
# myArray is an array I took as input , with $s1 elements 
    li  $t0,0     # $t0 stores left 
    addi $t3,$s1,-1    # $t3 stores right 

BinSearch: 
    bgt  $t0,$t3,exit   # L<=R (i.e. L>R) ? if no, we're done 

    add  $t1,$t3,$t0    # mid = left + right 
    srl  $t1,$t1,1    # mid /= 2 

    sll  $t2,$t1,2 
    lw  $t6,myArray($t2) 

    blt  $t6,$s2,leftindex  # if(A[mid]<k) goto left 
    beq  $t6,$s2,found 
    b  rightindex 

leftindex: 
    addi $t0,$t1,1    # leftindex = mid + 1 
    j  BinSearch    # goback to Binary Search 

rightindex: 
    addi $t3,$t1,-1    # rightindex = mid - 1 
    j  BinSearch    # goback to binarysearch 

found: 
    li  $v0,1 
    add  $a0,$t1,$zero 
    syscall 
    j  exit     # exit programme