How do I convert bubblesort to y86

Question

0.00/5 (No votes)

See more:

I am trying to convert a bubble sort program from assembly to Y86. I started with this C code and then converted it to assembly:

void bubbleSort2(long arr[], long len) {
        long i;         // inner loop index
        long tmp;       // temp for swapping
        long *arr_curr; // pointer to element in arr
        long *arr_next; // pointer to next element in arr
    
        while (len > 1) {
            arr_curr = arr; // begin at the start of arr
            i = 0;
            while (i < len-1) {
                arr_next = arr_curr + 1;  // set next pointer
                if (*arr_curr > *arr_next) {
                    // Swap the two elements
                    // to bubble up the larger value
                    tmp = *arr_curr;
                    *arr_curr = *arr_next;
                    *arr_next = tmp;
                }
                i++;
                arr_curr = arr_next;  // move to the next element 
            }
            len--;
        }
    }

What I have tried:

So far I've come up with this:  


    # Execution begins at address 0 
        .pos 0 
        irmovq stack, %rsp   # Set up stack pointer  
        call main            # Execute main program
        halt                 # Terminate program 
    
    # Array
        .align 8
    arr:
        .quad 0x64
        .quad 0x34
        .quad 0x40
        .quad 0x25
        .quad 0x12
        .quad 0x22
        .quad 0x11
        .quad 0x90
        .quad 0x55
        .quad 0x42
    
    main:
        irmovq arr, %rdi    
        irmovq $10, %rsi
        call bubble
        ret 
    
    # start bubble
    bubble:
       irmovq $1, %rax
    outer_loop:
       rrmovq %rsi, %r8
       subq %rax, %r8
       irmovq $1, %r9
       irmovq $0, %rcx
    inner_loop:
       rrmovq %rdi, %r10
       addq %rcx, %r10
       mrmovq (%r10), %r11
       mrmovq 8(%r10), %r12
       subq %r12, %r11
       jle no_swap
       subq %r11, %r12
       je no_swap
       jg swap
    swap:
       mrmovq (%r10), %r11
       mrmovq 8(%r10), %r12
       rmmovq %r11, 8(%r10)
       rmmovq %r12, (%r10)
    no_swap:
       irmovq $8, %r13
       addq %r13, %rcx
       subq %rax, %r8
       jg inner_loop
       rrmovq %rdi, %r10
       subq %rax, %r8
       jg outer_loop
       ret
    # end bubble
    # The stack starts here and grows to lower addresses
        .pos 0x200      
    stack:
    

I keep getting this:

    Changes to memory:
    0x0018:	0x0000000000000064	0x0000000000000034
    0x0020:	0x0000000000000034	0x0000000000000040
    0x0028:	0x0000000000000040	0x0000000000000025
    0x0030:	0x0000000000000025	0x0000000000000012
    0x0038:	0x0000000000000012	0x0000000000000022
    0x0040:	0x0000000000000022	0x0000000000000011
    0x0048:	0x0000000000000011	0x0000000000000064
    0x0050:	0x0000000000000090	0x0000000000000055
    0x0058:	0x0000000000000055	0x0000000000000042
    0x0060:	0x0000000000000042	0x0000000000000090
    0x01f0:	0x0000000000000000	0x0000000000000085
    0x01f8:	0x0000000000000000	0x0000000000000013
    
    When I try with less than 5 elements, it's sorted but when I do 10, it's never sorted. I don't know what the issue is. Please help!

Posted 22-Apr-23 20:00pm

Chronkilo

Updated 23-Apr-23 14:07pm

Add a Solution

Comments

Patrice T 23-Apr-23 5:34am

Probably time to learn Debugger.

Richard MacCutchan 23-Apr-23 6:54am

You need a flag which you set ate the start of each loop to keep track of swaps. If it indicates there were no swaps at the end of the loop then the sort should be complete.

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Richard MacCutchan · Answer 1 · 2023-04-23T01:22:00

Solution 2

See Bubble sort - Wikipedia[^].

Posted 23-Apr-23 1:22am

Richard MacCutchan

OriginalGriff · Answer 2 · 2023-04-23T00:56:00

Assembling without errors does not mean your code is right! :laugh:
Think of the development process as writing an email: compiling successfully means that you wrote the email in the right language - English, rather than German for example - not that the email contained the message you wanted to send.

So now you enter the second stage of development (in reality it's the fourth or fifth, but you'll come to the earlier stages later): Testing and Debugging.

Start by looking at what it does do, and how that differs from what you wanted. This is important, because it give you information as to why it's doing it. For example, if a program is intended to let the user enter a number and it doubles it and prints the answer, then if the input / output was like this:

Input   Expected output    Actual output
  1            2                 1
  2            4                 4
  3            6                 9
  4            8                16

Then it's fairly obvious that the problem is with the bit which doubles it - it's not adding itself to itself, or multiplying it by 2, it's multiplying it by itself and returning the square of the input.
So with that, you can look at the code and it's obvious that it's somewhere here:

C#

private int Double(int value)
   {
   return value * value;
   }

Once you have an idea what might be going wrong, start using the debugger to find out why. Put a breakpoint on the first line of the method, and run your app. When it reaches the breakpoint, the debugger will stop, and hand control over to you. You can now run your code line-by-line (called "single stepping") and look at (or even change) variable contents as necessary (heck, you can even change the code and try again if you need to).
Think about what each line in the code should do before you execute it, and compare that to what it actually did when you use the "Step over" button to execute each line in turn. Did it do what you expect? If so, move on to the next line.
If not, why not? How does it differ?
Hopefully, that should help you locate which part of that code has a problem, and what the problem is.
This is a skill, and it's one which is well worth developing as it helps you in the real world as well as in development. And like all skills, it only improves by use!

merano99 · Answer 3 · 2023-04-23T14:07:00

Unfortunately I don't speak Y86 assembler, so I asked the AI to write an optimized version of the bubblesort in Y86 assembler.

ASM

# BubbleSort in Y86 Assembler

# Input:
#   %rdi = address of array
#   %rsi = array size

.globl bubbleSort
bubbleSort:
    pushq %rbp
    movq %rsp, %rbp
    subq $8, %rsp      # Reserve space for temp variable

    movq %rdi, %r10    # r10 = array_start
    addq %rsi, %r10    # r10 = array_end
    decq %r10          # Decrement array_end to point to the last element

outer_loop:
    movq %rdi, %r11    # r11 = array_start
    cmpq %r11, %r10    # Compare r10 (array_end) and r11 (array_start)
    je end_sort        # If r10 == r11, we're done

    xorl %eax, %eax    # Clear swapped flag
    movq %rdi, %r12    # r12 = p1

inner_loop:
    cmpq %r12, %r10    # Compare r10 (array_end) and r12 (p1)
    jbe outer_loop     # If p1 has reached array_end, break inner loop

    movq %r11, %rbx    # r11 (array_start) is our counter, so copy it to rbx
    addq $8, %rbx      # Increment rbx to point to the next element

    cmpq %rbx, %r10    # Compare rbx and r10 (array_end)
    jbe end_inner_loop # If we've reached array_end, break inner loop

    movq (%r11), %rdx  # Load *p2 into rdx
    movq (%rbx), %rcx  # Load *(p2 + 1) into rcx
    cmpq %rdx, %rcx    # Compare *p2 and *(p2 + 1)

    jle not_swapped    # If *p2 <= *(p2 + 1), no swap needed

    movq %rdx, (%rbx)  # Store *p2 at *(p2 + 1)
    movq %rcx, (%r11)  # Store *(p2 + 1) at *p2
    movl $1, %eax      # Set swapped flag

not_swapped:
    addq $8, %r11      # Increment p2
    jmp inner_loop     # Jump to the start of the inner loop

end_inner_loop:
    cmpq $0, %eax      # Check if swapped flag is zero
    jne outer_loop     # If not, jump to the start of the outer loop

end_sort:
    addq $8, %rsp      # Deallocate space for temp variable
    popq %rbp
    ret

The pointer to the end of the array is in register %r10.
The pointers of the two loops p1 and p2 are in registers %r11 and %rbx

How do I convert bubblesort to y86

3 solutions

Solution 2

Solution 1

Solution 3

Add your solution here

Preview 0