Finding Kth distinct element in an array MIPS

Question

I am trying to write MIPS equivalent of the C code below.

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];
    }
}

I want to store the result in $s1 with the code below.

.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

While I am expecting to see 8 in $s1 register, I am getting 1. What is wrong my assembly code ?

Answer 1

A few things were wrong.

Your C code was incomplete. By examining your asm code, I was able to add the missing stuff to the C code.

You didn't set up some registers correctly.

You were also comparing array offsets (your iteration variables that were incremented by 4) against an array index/count, so the compares wouldn't work.

You were setting the register for KCtr to 1, instead of doing the asm equivalent of KCtr++

I created three examples: the fixed C code, An annotated version of your asm showing some/most of the bugs. And, a cleaned up, refactored, and working version.

---

Here's the C code:

#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;
}

---

Here's the annotated version:

    .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

---

Here's the refactored version. It's somewhat different than yours because in order to get it to work, I simplified it a bit. It also uses pointers instead of indexes or offsets for array access. Also note that once KCtr == K, there is no need to continue the loop.

    .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

---

UPDATE:

Your code seems to be working in spim. But I didn't understand "ArrayEnd". There is no value set for it,but it works. How ?

ArrEnd is a "trick" of sorts. It is the address of the last element of Array + 1. That is, in C, if we have int Array[5], then ArrEnd is &Array[5].

Just like in C, we can choose how to iterate over arrays. We can use an index and do: Array[i]. Or, we can use int * pointers. In asm, we can use offsets from the start of the array (i.e. an index << 2).

Let's recode the C program to only use pointers [and not indexes] to iterate across the array. This isn't used as often in C code, but it comes in handy for asm. The following is actually a more accurate C code representation of what my second asm example did:

#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;
}

Here are some idiomatic uses for 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

Now that we have these values, we can iterate through the array by any of the above three methods. Using the offset version or the pointer version can usually be more efficient.

To see how easy ArrEnd makes things, comment out the larger array and add the shorter array from the C code. The ArrEnd trick will adjust things automatically without needing to manually count the number of elements in Array

---

UPDATE #2:

I may be wrong about this, but upon further reflection, to meet the requirements of the question title, the C code [and hence the asm] may need to be changed.

I think the inner loop has to scan the entire array [skipping the element where i == o] when looking for duplicates. Otherwise, it may hit a false positive.

Also, it appears that the original never thinks the index 0 element is unique, even if it is. This is because the o loop started with index 1.

I've created two algorithms. The original as above. And one that does the full scan. I've also added some more test cases to illustrate the issue I'm thinking of.

Here's the test program:

#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;
}

Here is the program output:

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

The simplest tests that illustrate both issues are Array5 and Array6

Here's the corresponding asm code:

    .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