いくつか間違っていました。
あなたの C コードは不完全でした。あなたの asm コードを調べることで、欠落しているものを C コードに追加することができました。
一部のレジスタが正しく設定されていません。
また、配列のオフセット (4 ずつインクリメントされた反復変数) を配列のインデックス/カウントと比較していたため、比較は機能しませんでした。
KCtrasmに相当するのではなく、レジスタを1に設定していましたKCtr++
私は 3 つの例を作成しました: 修正された C コード、いくつか/ほとんどのバグを示す注釈付きバージョンの asm。そして、クリーンアップされ、リファクタリングされ、動作するバージョン。
Cコードは次のとおりです。
#include <stdio.h>
#if 0
int Array[] = { 1, 2, 1, 3, 4 };
#else
int Array[] = { 1, 2, 4, 8, 16, 32, 64, 128 };
#endif
int
main(void)
{
int result;
int K = 3;
int KCtr = 0;
int count = sizeof(Array) / sizeof(Array[0]);
int uniqflg;
result = -1;
for (int o = 1; o < count; o++) {
uniqflg = 1;
for (int i = 0; i < o; i++) {
if (Array[o] == Array[i]) {
uniqflg = 0;
break;
}
}
if (! uniqflg)
continue;
KCtr++;
if (KCtr == K) {
result = Array[o];
}
}
printf("result=%d\n",result);
return result;
}
注釈付きのバージョンは次のとおりです。
.data
Array: .word 1,2,4,8,16,32,64,128
sze :
K :
.text
.globl main
# s1 for result
# t0 for o
# t1 for i
# t2 for array count
# t3 for array[o]
# t4 for array[i]
# t5 for unique flag
# t6 for counter to reach K (i.e. KCtr?)
# t7 for storing 1
main:
lw $s0,K($0) # K
addi $t0,$zero,0 # index for outer loop
# NOTE/BUG: this is misplaced it needs to be moved to just above innerloop
addi $t1,$zero,0 # index for inner loop
lw $t2,sze($0) # get array count
lw $s1,Array($0) # result = Array[0]
addi $t6,$zero,0 # KCtr = 0
# NOTE/BUG: this was commented out:
addi $t7,$zero,1
outerloop:
# NOTE/BUG: based on the increment by 4 to $t0 below, this is comparing an
# offset against a count
beq $t0,$t2,finish # o < count? if no, fly
lw $t3,Array($t0) # get Array[o]
addi $t5,$zero,0 # uniqflg = 0
innerloop:
lw $t4,Array($t1) # get Array[i]
bne $t3,$t4,inner_neq # Array[o] == Array[i]? if no, fly
# NOTE/BUG: this is just setting one (i.e. KCtr = 1 instead of KCtr++)
addi $t5,$zero,1 # uniqflg = 1
inner_neq:
checkifunique:
beq $t5,$t7,notuniq # ???
addi $t6,$zero,1
notuniq:
addi $t1,$t1,4 # advance array offset
# NOTE/BUG: this compares an array offset against an index
blt $t1,$t0,innerloop # at end? if no, loop
bne $t6,$s0,inner_next # KCtr == K? if no, interate
lw $s1,Array($t0) # get better result
inner_next:
addi $t0,$t0,4 # advance o [as offset]
b outerloop
finish:
li $v0,10
syscall
リファクタリングしたバージョンはこちら。それを機能させるために、少し単純化したため、あなたのものとは多少異なります。また、配列アクセスにインデックスやオフセットの代わりにポインターを使用します。KCtr == Kまた、一度ループを続ける必要はないことに注意してください。
.data
Array: .word 1,2,4,8,16,32,64,128
ArrEnd:
K: .word 3
.text
.globl main
# s0 for K
# s1 for result
# t0 for o (as pointer)
# t1 for i (as pointer)
# t2 for array count
# t3 for array[o]
# t4 for array[i]
# t6 for counter to reach K (i.e. KCtr?)
main:
lw $s0,K # K
li $t6,0 # KCtr = 0
la $t2,ArrEnd # point to end of array
la $t0,Array # o = &Array[0]
lw $s1,0($t0) # result = Array[0]
outerloop:
addiu $t0,$t0,4 # advance o [as pointer]
bgeu $t0,$t2,finish # o < ArrEnd? if no, fly
lw $t3,0($t0) # get Array[o]
la $t1,Array # i = &Array[0]
innerloop:
lw $t4,0($t1) # get Array[i]
beq $t3,$t4,outerloop # Array[o] == Array[i]? if yes, not unique
addiu $t1,$t1,4 # advance array pointer for i
bltu $t1,$t0,innerloop # at end? if no, loop
# current array value is unique
addi $t6,$t6,1 # KCtr++
bne $t6,$s0,outerloop # KCtr == K? if no, wait for next unique
lw $s1,0($t0) # get better result -- no need to loop more
finish:
li $v0,1
move $a0,$s1
syscall
li $v0,10
syscall
アップデート：
あなたのコードはスピムで動作しているようです。しかし、「ArrayEnd」がわかりませんでした。値は設定されていませんが、機能します。どのように ？
ArrEnd一種の「トリック」です。+ 1の最後の要素のアドレスですArray。つまり、C では、 がある場合int Array[5]、ArrEndは です&Array[5]。
C と同じように、配列を反復処理する方法を選択できます。インデックスを使用して、次のことを行うことができますArray[i]。または、int *ポインタを使用できます。asm では、配列の先頭からのオフセット (つまり an index << 2) を使用できます。
配列全体を反復処理するために [インデックスではなく] ポインターのみを使用するように C プログラムを再コーディングしましょう。これは C コードではあまり使用されませんが、asm では便利です。以下は、実際には、2 番目の asm の例で行ったことをより正確に C コードで表したものです。
#include <stdio.h>
#if 0
int Array[] = { 1, 2, 1, 3, 4 };
#else
int Array[] = { 1, 2, 4, 8, 16, 32, 64, 128 };
#endif
int
main(void)
{
int result;
int K = 3;
int KCtr = 0;
int *ArrEnd = &Array[sizeof(Array) / sizeof(Array[0])];
int uniqflg;
result = -1;
for (int *o = &Array[1]; o < ArrEnd; o++) {
uniqflg = 1;
for (int *i = &Array[0]; i < o; i++) {
if (*o == *i) {
uniqflg = 0;
break;
}
}
if (! uniqflg)
continue;
KCtr++;
if (KCtr == K) {
result = *o;
break;
}
}
printf("result=%d\n",result);
return result;
}
のいくつかの慣用的な使用法を次に示しますArrEnd。
la $s0,Array # get array address
la $s1,ArrEnd # address of array end [one past last]
subu $s2,$s1,$s0 # get byte length of array
srl $s3,$s2,2 # get array count
これらの値を取得したので、上記の 3 つの方法のいずれかで配列を反復処理できます。通常は、オフセット バージョンまたはポインター バージョンを使用する方が効率的です。
物事がいかに簡単かを確認するにArrEndは、大きい方の配列をコメント アウトし、C コードから短い方の配列を追加します。トリックは、要素の数を手動でカウントする必要なく、ArrEnd自動的に調整しますArray
更新＃2：
私はこれについて間違っているかもしれませんが、さらに考えてみると、質問のタイトルの要件を満たすために、C コード [したがって asm] を変更する必要があるかもしれません。
重複を探すとき、内部ループは配列全体をスキャンする必要があると思います[要素をスキップします]。i == oそうしないと、誤検出が発生する可能性があります。
また、インデックス 0 要素が一意であっても、元の要素は一意であるとは決して考えていないようです。これは、oループがインデックス 1 で開始されたためです。
2 つのアルゴリズムを作成しました。オリジナルは上記の通り。そして、フルスキャンを行うもの。また、考えている問題を説明するために、さらにいくつかのテスト ケースを追加しました。
テストプログラムは次のとおりです。
#include <stdio.h>
int Array0[] = { 1, 2, 1, 3, 4 };
int Array1[] = { 1, 2, 4, 8, 16, 32, 64, 128 };
int Array2[] = { 1, 2, 4, 4, 8, 16, 32, 64, 128 };
int Array3[] = { 1, 2, 4, 8, 16, 32, 64, 128, 2 };
int Array4[] = { 1, 2, 4, 8, 16, 32, 64, 128, 2, 4 };
int Array5[] = { 1, 2, 3, 4, 5, 6 };
int Array6[] = { 1, 2, 3, 4, 5, 6, 1, 3 };
int K = 3;
int sepflg;
int tstno;
int
orig(int *Array,int *ArrEnd)
{
int result;
long residx;
int KCtr = 0;
int uniqflg;
result = -1;
residx = -1;
for (int *o = &Array[1]; o < ArrEnd; o++) {
uniqflg = 1;
for (int *i = &Array[0]; i < o; i++) {
if (*o == *i) {
uniqflg = 0;
break;
}
}
if (! uniqflg)
continue;
printf(" orig: MATCH value=%d index=%ld\n",*o,o - Array);
KCtr++;
if (KCtr == K) {
result = *o;
residx = o - Array;
break;
}
}
printf(" orig: FINAL result=%d residx=%ld\n",result,residx);
return result;
}
int
full(int *Array,int *ArrEnd)
{
int result;
long residx;
int KCtr = 0;
int uniqflg;
result = -1;
residx = -1;
for (int *o = &Array[0]; o < ArrEnd; o++) {
uniqflg = 1;
for (int *i = &Array[0]; i < ArrEnd; i++) {
if (o == i)
continue;
if (*o == *i) {
uniqflg = 0;
break;
}
}
if (! uniqflg)
continue;
printf(" full: MATCH value=%d index=%ld\n",*o,o - Array);
KCtr++;
if (KCtr == K) {
result = *o;
residx = o - Array;
break;
}
}
printf(" full: FINAL result=%d residx=%ld\n",result,residx);
return result;
}
void
test(int *Array,long siz)
{
int *ArrEnd = &Array[siz / sizeof(int)];
int oval;
int fval;
if (sepflg)
printf("\n");
sepflg = 1;
printf("Array%d:",tstno);
for (int *ptr = Array; ptr < ArrEnd; ++ptr)
printf(" %4d",*ptr);
printf("\n");
oval = orig(Array,ArrEnd);
printf("\n");
fval = full(Array,ArrEnd);
printf("\n");
printf(" test: %s orig=%d full=%d\n",
(oval == fval) ? "PASS" : "FAIL",oval,fval);
++tstno;
}
int
main(void)
{
test(Array0,sizeof(Array0));
test(Array1,sizeof(Array1));
test(Array2,sizeof(Array2));
test(Array3,sizeof(Array3));
test(Array4,sizeof(Array4));
test(Array5,sizeof(Array5));
test(Array6,sizeof(Array6));
return 0;
}
プログラムの出力は次のとおりです。
Array0: 1 2 1 3 4
orig: MATCH value=2 index=1
orig: MATCH value=3 index=3
orig: MATCH value=4 index=4
orig: FINAL result=4 residx=4
full: MATCH value=2 index=1
full: MATCH value=3 index=3
full: MATCH value=4 index=4
full: FINAL result=4 residx=4
test: PASS orig=4 full=4
Array1: 1 2 4 8 16 32 64 128
orig: MATCH value=2 index=1
orig: MATCH value=4 index=2
orig: MATCH value=8 index=3
orig: FINAL result=8 residx=3
full: MATCH value=1 index=0
full: MATCH value=2 index=1
full: MATCH value=4 index=2
full: FINAL result=4 residx=2
test: FAIL orig=8 full=4
Array2: 1 2 4 4 8 16 32 64 128
orig: MATCH value=2 index=1
orig: MATCH value=4 index=2
orig: MATCH value=8 index=4
orig: FINAL result=8 residx=4
full: MATCH value=1 index=0
full: MATCH value=2 index=1
full: MATCH value=8 index=4
full: FINAL result=8 residx=4
test: PASS orig=8 full=8
Array3: 1 2 4 8 16 32 64 128 2
orig: MATCH value=2 index=1
orig: MATCH value=4 index=2
orig: MATCH value=8 index=3
orig: FINAL result=8 residx=3
full: MATCH value=1 index=0
full: MATCH value=4 index=2
full: MATCH value=8 index=3
full: FINAL result=8 residx=3
test: PASS orig=8 full=8
Array4: 1 2 4 8 16 32 64 128 2 4
orig: MATCH value=2 index=1
orig: MATCH value=4 index=2
orig: MATCH value=8 index=3
orig: FINAL result=8 residx=3
full: MATCH value=1 index=0
full: MATCH value=8 index=3
full: MATCH value=16 index=4
full: FINAL result=16 residx=4
test: FAIL orig=8 full=16
Array5: 1 2 3 4 5 6
orig: MATCH value=2 index=1
orig: MATCH value=3 index=2
orig: MATCH value=4 index=3
orig: FINAL result=4 residx=3
full: MATCH value=1 index=0
full: MATCH value=2 index=1
full: MATCH value=3 index=2
full: FINAL result=3 residx=2
test: FAIL orig=4 full=3
Array6: 1 2 3 4 5 6 1 3
orig: MATCH value=2 index=1
orig: MATCH value=3 index=2
orig: MATCH value=4 index=3
orig: FINAL result=4 residx=3
full: MATCH value=2 index=1
full: MATCH value=4 index=3
full: MATCH value=5 index=4
full: FINAL result=5 residx=4
test: FAIL orig=4 full=5
両方の問題を説明する最も簡単なテストはArray5、Array6
対応する asm コードは次のとおりです。
.data
Array: .word 1, 2, 3, 4, 5, 6, 1, 3
ArrEnd:
K: .word 3
.text
.globl main
# s0 for K
# s1 for result
# t0 for o (as pointer)
# t1 for i (as pointer)
# t2 for array count
# t3 for array[o]
# t4 for array[i]
# t6 for counter to reach K (i.e. KCtr?)
main:
lw $s0,K # K
li $t6,0 # KCtr = 0
la $t2,ArrEnd # point to end of array
la $t0,Array # o = &Array[0]
li $s1,-1 # get fail value
b outstart
outerloop:
addiu $t0,$t0,4 # advance o [as pointer]
outstart:
bgeu $t0,$t2,finish # o < ArrEnd? if no, fly
lw $t3,0($t0) # get Array[o]
la $t1,Array # i = &Array[0]
innerloop:
lw $t4,0($t1) # get Array[i]
beq $t1,$t0,innernext # o == i? if yes, skip test
beq $t3,$t4,outerloop # Array[o] == Array[i]? if yes, not unique
innernext:
addiu $t1,$t1,4 # advance array pointer for i
bltu $t1,$t2,innerloop # at end? if no, loop
# current array value is unique
addi $t6,$t6,1 # KCtr++
bne $t6,$s0,outerloop # KCtr == K? if no, wait for next unique
lw $s1,0($t0) # get better result -- no need to loop more
finish:
li $v0,1
move $a0,$s1
syscall
li $v0,10
syscall