排序算法實現在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