Нахождение K-го отдельного элемента в массиве MIPS

Я пытаюсь написать MIPS-эквивалент приведенного ниже кода C.

int arrayData[5] = { 1,2,1,3,4 };
int K = 3;
int KCtr = 0;
int result;
bool isUnique;
for (int o = 1; o < 5; o++)
{
    isUnique = true;
    for (int i = 0; i < o; i++)
    {
        if (arrayData[o] == arrayData[i])
        {
            isUnique = false;
            break; // goto outer loop 
        }
    }
    if (isUnique)
    {
        KCtr++;
    }
    if (KCtr==K)
    {
        result = arrayData[o];
    }
}

Я хочу сохранить результат в $s1 с кодом ниже.

.data
Array: .word 1, 2, 4, 8, 16, 32, 64, 128
sze  : .word 8
K    : .word 3
.text
.globl main

main: lw $s0,K($0) # K 
      addi $t0,$zero,0 # index for outer loop
      addi $t1,$zero,0 # index for inner loop
      lw   $t2,sze($0)
      lw   $s1,Array($0)
      addi $t6,$zero,0
      #addi $t7,$zero,1
      #t3 for array[o] 
      #t4 for array[i]
      #t5 for unique flag
      #t6 for counter to reach K
      #t7 for storing 1
outerloop:
    beq $t0,$t2,finish
    lw $t3,Array($t0)
    addi $t5,$zero,0 
innerloop:
    lw $t4,Array($t1)    
    bne $t3,$t4,else
    addi $t5,$zero,1
else:

checkifunique:
    beq $t5,$t7,isnotuniquebypass
    addi $t6,$zero,1
isnotuniquebypass:
    addi $t1,$t1,4
    blt $t1,$t0,innerloop

    bne $t6,$s0,notreachedKbypass
    lw $s1,Array($t0)

notreachedKbypass:

    addi $t0,$t0,4
    b outerloop  


finish:
      li $v0,10
      syscall

Пока я ожидаю увидеть 8 в регистре $s1, я получаю 1. Что не так с моим ассемблерным кодом?

Muhammet Ali Asan 30.10.2016 источник

Ответы (1)

arrow_upward
2
arrow_downward

Несколько вещей были неправильными.

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

Вы не правильно настроили некоторые регистры.

Вы также сравнивали смещения массива (ваши переменные итерации, которые были увеличены на 4) с индексом/количеством массива, поэтому сравнение не работало.

Вы устанавливали регистр для KCtr в 1 вместо того, чтобы делать ассемблерный эквивалент KCtr++

Я создал три примера: исправленный код C, аннотированную версию вашего ассемблера, показывающую некоторые/большинство ошибок. И очищенная, рефакторинговая и рабочая версия.

Вот код 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

ОБНОВЛЕНИЕ:

Ваш код, кажется, работает в spim. Но я не понял "ArrayEnd". Для него не установлено значение, но оно работает. Как ?

ArrEnd - это своего рода "трюк". Это адрес последнего элемента Array + 1. То есть в C, если у нас есть int Array[5], то ArrEnd это &Array[5].

Как и в C, мы можем выбирать, как перебирать массивы. Мы можем использовать индекс и сделать: Array[i]. Или мы можем использовать указатели int *. В ассемблере мы можем использовать смещения от начала массива (то есть index << 2).

Давайте перекодируем программу C, чтобы только использовать указатели [а не индексы] для итерации по массиву. Это не так часто используется в коде C, но это удобно для ассемблера. Ниже приведено более точное представление кода C того, что сделал мой второй пример asm:

#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

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

Чтобы увидеть, как легко ArrEnd делает вещи, закомментируйте больший массив и добавьте более короткий массив из кода C. Трюк с ArrEnd автоматически настраивает все без необходимости вручную подсчитывать количество элементов в Array

ОБНОВЛЕНИЕ №2:

Я могу ошибаться в этом, но при дальнейшем размышлении, чтобы соответствовать требованиям заголовка вопроса, код C [и, следовательно, asm], возможно, потребуется изменить.

Я думаю, что внутренний цикл должен сканировать весь массив [пропуская элемент, где i == o] при поиске дубликатов. В противном случае это может привести к ложному срабатыванию.

Кроме того, похоже, что оригинал никогда не считает элемент с индексом 0 уникальным, даже если это так. Это потому, что цикл o начался с индекса 1.

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

Вот тестовая программа:

#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.

Вот соответствующий ассемблерный код:

    .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

Craig Estey 30.10.2016

Нахождение K-го отдельного элемента в массиве MIPS

Ответы (1)

Вопросы по теме