4
\$\begingroup\$

So, this is improved code from my previous attempt to implement the permutations algorithm in PicoBlaze assembly language.

You can see it live here:

;A very advanced example: Implementing the permutations algorithm in PicoBlaze assembly.
;For sorting, we will use the Bubble Sort algorithm. And we will use stack instead of recursion.

base_decimal

constant NDEBUG, 1
constant address_of_the_current_attempt, 8
constant digits_of_the_ordinal_number, 16
constant bottom_of_the_stack, 24

address 0

namereg sf, length_of_the_input

regbank a
call print_the_introduction_message
load length_of_the_input, 0
beginning_of_the_input_loop:
  call UART_RX
  compare s9, a'x ;The new-line character.
  jump z, end_of_the_input_loop
  store s9, (length_of_the_input)
  add length_of_the_input, 1
  jump beginning_of_the_input_loop
end_of_the_input_loop:
compare length_of_the_input, 0
jump z, 0

beginning_of_the_bubble_sort:
  load s4, 0 ;A boolean indicating
             ;whether a swap has been
             ;performed.
  load s0, 0
  inner_bubble_sort_loop:
    load s1, length_of_the_input
    sub s1, 1
    compare s0, s1
    jump nc, end_of_the_inner_bubble_sort_loop
    load s1, s0
    add s1, 1
    fetch s2, (s0)
    fetch s3, (s1)
    compare s3, s2
    jump nc, do_not_swap
      store s3, (s0)
      store s2, (s1)
      load s4, 1
    do_not_swap:
    add s0, 1
    jump inner_bubble_sort_loop
  end_of_the_inner_bubble_sort_loop:
  compare s4, 0
  jump nz, beginning_of_the_bubble_sort
end_of_the_bubble_sort_loop:

jump NDEBUG ? the_permutations_algorithm : printing_the_sorted_array
printing_the_sorted_array:
call print_the_sorted_array_message
load s0, 0
printing_the_sorted_array_loop:
  compare s0, length_of_the_input
  jump nc, end_of_the_printing_the_sorted_array_loop
  fetch s9, (s0)
  call UART_TX
  add s0, 1
  jump printing_the_sorted_array_loop
end_of_the_printing_the_sorted_array_loop:
load s9, a'x
call UART_TX

the_permutations_algorithm:

;Let's set all the digits of the ordinal number of permutations to "0"
regbank b
load s0, digits_of_the_ordinal_number
load s2, digits_of_the_ordinal_number ;End of the digits of the ordinal number.
reset_ordinal_numbers_loop:
  compare s0, bottom_of_the_stack
  jump nc, end_of_the_reset_ordinal_numbers_loop
  load s1, "0"
  store s1, (s0)
  add s0, 1
  jump reset_ordinal_numbers_loop
end_of_the_reset_ordinal_numbers_loop:
regbank a

namereg se, top_of_the_stack
load top_of_the_stack, bottom_of_the_stack
load s0, 0
store s0, (top_of_the_stack)
add top_of_the_stack, length_of_the_input
add top_of_the_stack, 1
beginning_of_the_permutations_loop:
  compare top_of_the_stack, bottom_of_the_stack
  jump z, end_of_the_permutations_loop
  sub top_of_the_stack, length_of_the_input
  sub top_of_the_stack, 1
  namereg sd, length_of_the_current_attempt
  fetch length_of_the_current_attempt, (top_of_the_stack)
  load s0, address_of_the_current_attempt
  store length_of_the_current_attempt, (s0)
  load s1, 0
  copying_the_current_attempt_from_the_stack_loop:
    compare s1, length_of_the_current_attempt
    jump nc, end_of_copying
    load s0, address_of_the_current_attempt
    add s0, s1
    add s0, 1
    load s3, top_of_the_stack
    add s3, s1
    add s3, 1
    fetch s4, (s3)
    store s4, (s0)
    add s1, 1
    jump copying_the_current_attempt_from_the_stack_loop
  end_of_copying:
  jump NDEBUG ? dont_print_the_current_attempt : print_the_current_attempt
  print_the_current_attempt:
  call print_the_length_of_the_current_attempt_message
  load s9, length_of_the_current_attempt
  add s9, "0"
  call UART_TX
  load s9, a'x
  call UART_TX
  call print_the_current_attempt_message
  load s0, address_of_the_current_attempt + 1
  printing_the_current_attempt_loop:
    load s1, address_of_the_current_attempt + 1
    add s1, length_of_the_current_attempt
    compare s0, s1
    jump nc, end_of_the_printing_the_current_attempt_loop
    fetch s9, (s0)
    call UART_TX
    add s0, 1
    jump printing_the_current_attempt_loop
  end_of_the_printing_the_current_attempt_loop:
  load s9, a'x
  call UART_TX
  dont_print_the_current_attempt:
  compare length_of_the_current_attempt, length_of_the_input
  jump c, current_attempt_is_not_a_solution
    call print_found_a_solution_message
    load s0, address_of_the_current_attempt + 1
    printing_the_solution_loop:
      load s1, address_of_the_current_attempt + 1
      add s1, length_of_the_current_attempt
      compare s0, s1
      jump nc, end_of_the_printing_the_solution_loop
      fetch s9, (s0)
      call UART_TX
      add s0, 1
      jump printing_the_solution_loop
    end_of_the_printing_the_solution_loop:
    load s9, a'x
    call UART_TX
    regbank b
    call print_the_ordinal_number_message
    load s1, digits_of_the_ordinal_number
    increasing_the_ordinal_number_loop:
      fetch s0, (s1)
      add s0, 1
      store s0, (s1)
      compare s0, "9" + 1
      jump nz, end_of_increasing_the_ordinal_number_loop
      load s0, "0"
      store s0, (s1)
      add s1, 1
      jump increasing_the_ordinal_number_loop
    end_of_increasing_the_ordinal_number_loop:
    compare s1, s2
    jump c, not_a_new_digit
      load s2, s1
    not_a_new_digit:
    load s1, s2
    printing_the_ordinal_number:
      fetch s9, (s1)
      call UART_TX
      sub s1, 1
      compare s1, digits_of_the_ordinal_number
      jump nc, printing_the_ordinal_number
    end_of_printing_the_ordinal_number:
    load s9, a'x
    call UART_TX
    regbank a
  jump end_of_the_branching
  current_attempt_is_not_a_solution:
    load s0, length_of_the_input
    sub s0, 1
    add_a_new_character_loop:
      compare s0, ff'x ;Overflow
      jump z, end_of_the_add_a_new_character_loop
      namereg sc, character_we_try_to_add
      fetch character_we_try_to_add, (s0)
      load s7, s0
      add s7, 1
      load s8, 0 ;Whether we already tried adding that character.
      check_if_we_already_tried_that_character_loop:
        compare s7, length_of_the_input
        jump nc, end_of_the_check_if_we_already_tried_that_character_loop
        fetch s6, (s7)
        compare s6, character_we_try_to_add
        jump nz, third_characters_are_not_equal_label
          load s8, 1
        third_characters_are_not_equal_label:
        add s7, 1
        jump check_if_we_already_tried_that_character_loop
      end_of_the_check_if_we_already_tried_that_character_loop:
      test s8, s8
      jump nz, dont_add_the_new_character
      jump NDEBUG ? dont_print_the_character_we_are_trying_to_add : print_the_character_we_are_trying_to_add
      print_the_character_we_are_trying_to_add:
        call print_we_are_trying_to_add_message
        load s9, character_we_try_to_add
        call UART_TX
        load s9, a'x
        call UART_TX
      dont_print_the_character_we_are_trying_to_add:
      load s2, 0 ; How many of the chosen character are present in the current attempt.
      load s1, address_of_the_current_attempt + 1
      count_in_the_current_attempt_loop:
        load s4, address_of_the_current_attempt + 1
        add s4, length_of_the_current_attempt
        compare s1, s4
        jump z, end_of_the_count_in_the_current_attempt_loop
        fetch s4, (s1)
        compare s4, character_we_try_to_add
        jump nz, first_the_characters_are_not_equal_label
          add s2, 1
        first_the_characters_are_not_equal_label:
        add s1, 1
        jump count_in_the_current_attempt_loop
      end_of_the_count_in_the_current_attempt_loop:
      jump NDEBUG ? dont_print_how_many_in_the_current_attempt : print_how_many_in_the_current_attempt
      print_how_many_in_the_current_attempt:
        call print_the_current_attempt_count_message
        load s9, s2
        add s9, "0"
        call UART_TX
        load s9, a'x
        call UART_TX
      dont_print_how_many_in_the_current_attempt:
      load s3, 0 ; How many of the chosen character are present in the input.
      load s1, 0
      count_in_the_input_loop:
        compare s1, length_of_the_input
        jump z, end_of_the_count_in_the_input_loop
        fetch s4, (s1)
        compare s4, character_we_try_to_add
        jump nz, second_the_characters_are_not_equal_label
          add s3, 1
        second_the_characters_are_not_equal_label:
        add s1, 1
        jump count_in_the_input_loop
      end_of_the_count_in_the_input_loop:
      jump NDEBUG ? dont_print_how_many_in_the_input : print_how_many_in_the_input
      print_how_many_in_the_input:
        call print_count_in_the_input_message
        load s9, s3
        add s9, "0"
        call UART_TX
        load s9, a'x
        call UART_TX
      dont_print_how_many_in_the_input:
      compare s2, s3
      jump nc, dont_add_the_new_character
        load s1, NDEBUG
        test s1, s1
        call z, print_the_we_are_adding_the_new_character_message
        load s1, top_of_the_stack
        load s2, length_of_the_current_attempt
        add s2, 1
        store s2, (s1)
        add s1, 1
        load s3, address_of_the_current_attempt + 1
        copying_the_new_attempt_loop:
          load s5, address_of_the_current_attempt + 1
          add s5, length_of_the_current_attempt
          compare s3, s5
          jump z, end_of_the_copying_the_new_attempt_loop
          fetch s4, (s3)
          store s4, (s1)
          add s3, 1
          add s1, 1
          jump copying_the_new_attempt_loop
        end_of_the_copying_the_new_attempt_loop:
        ;s1 now points to the location right after the copied attempt.
        store character_we_try_to_add, (s1)
        add top_of_the_stack, length_of_the_input
        add top_of_the_stack, 1
      dont_add_the_new_character:
      sub s0, 1
      jump add_a_new_character_loop
    end_of_the_add_a_new_character_loop:
  jump end_of_the_branching
  end_of_the_branching:
  jump beginning_of_the_permutations_loop
end_of_the_permutations_loop:
call print_the_end_message
jump 0

print_the_introduction_message:
  print_string "Enter a short string and press enter.", s9, UART_TX
  load s9, a'x
  call UART_TX
return

print_the_sorted_array_message:
  print_string "After the Bubble Sort algorithm, the input string looks like this: ", s9, UART_TX
return

print_the_current_attempt_message:
  print_string "The current attempt is: ", s9, UART_TX
return

print_we_are_trying_to_add_message:
  print_string "We are trying to add the character: ", s9, UART_TX
return

print_the_current_attempt_count_message:
  print_string "The count of that character in the current attempt is: ", s9, UART_TX
return

print_count_in_the_input_message:
  print_string "The count of that character in the input string is: ", s9, UART_TX
return

print_the_we_are_adding_the_new_character_message:
  print_string "We will try to add that character.", s9, UART_TX
  load s9, a'x
  call UART_TX
return

print_found_a_solution_message:
  print_string "Found a permutation: ", s9, UART_TX
return

print_the_end_message:
  print_string "The end!", s9, UART_TX
  load s9, a'x
  call UART_TX
return

print_the_length_of_the_current_attempt_message:
  print_string "The length of the current attempt is: ", s9, UART_TX
return

print_the_ordinal_number_message:
  print_string "That's the permutation #", s9, UART_TX
return

base_hexadecimal
;Now follows some boilerplate code
;we use in our Computer Architecture
;classes...
CONSTANT LED_PORT,         00
CONSTANT HEX1_PORT,        01
CONSTANT HEX2_PORT,        02
CONSTANT UART_TX_PORT,     03
CONSTANT UART_RESET_PORT,  04
CONSTANT SW_PORT,          00
CONSTANT BTN_PORT,         01
CONSTANT UART_STATUS_PORT, 02
CONSTANT UART_RX_PORT,     03
; Tx data_present
CONSTANT U_TX_D, 00000001'b
; Tx FIFO half_full
CONSTANT U_TX_H, 00000010'b
; TxFIFO full
CONSTANT U_TX_F, 00000100'b
; Rxdata_present
CONSTANT U_RX_D, 00001000'b
; RxFIFO half_full
CONSTANT U_RX_H, 00010000'b
; RxFIFO full
CONSTANT U_RX_F, 00100000'b

UART_RX:
  INPUT sA, UART_STATUS_PORT
  TEST  sA, U_RX_D
  JUMP  NZ, input_not_empty
  LOAD  s0, s0
  JUMP UART_RX
  input_not_empty:
  INPUT s9, UART_RX_PORT
RETURN

UART_TX:
  INPUT  sA, UART_STATUS_PORT
  TEST   sA, U_TX_F
  JUMP   NZ, UART_TX
  OUTPUT s9, UART_TX_PORT
RETURN

Compared to my previous attempt, I made a few modifications:

  • I've shortened the code for printing long strings by modifying the preprocessor of the assembler to have the support for the print_string preprocessor directive.
  • I've removed the redundant piece of code for setting the s1 to point to right after the copied attempt. Namely, it already does that after the loop is finished.
  • I've added the support for printing the ordinal number of permutations.
\$\endgroup\$

1 Answer 1

Reset to default
2
+50
\$\begingroup\$

I don't know too much about PicoBlaze (I just skimmed some PDF) but I do know a thing or two about BubbleSort.

I see your loop continuously runs over the whole array, where normally in a bubble sort at the end of the inner loop the last element will have been moved to its final place. So next runs of the inner loop should be shorter.
The code uses two different exits:

  • s4 an early exit for when the inner loop didn't have to perform any swap
  • s5 the usual exit for when the problem has been reduced to an array of but 1 element
beginning_of_the_bubble_sort:
    load    s5, length_of_the_input
  outer_bubble_sort_loop:
    sub     s5, 1
    jump    z, end_of_the_bubble_sort
    load    s4, 0 ; Indicates swap(s) performed.
    load    s1, 0
  inner_bubble_sort_loop:
    compare s1, s5
    jump    nc, end_of_the_inner_bubble_sort_loop
    load    s0, s1
    add     s1, 1
    fetch   s2, (s0)
    fetch   s3, (s1)
    compare s3, s2
    jump    nc, inner_bubble_sort_loop
    store   s3, (s0)
    store   s2, (s1)
    load    s4, 1
    jump    inner_bubble_sort_loop
  end_of_the_inner_bubble_sort_loop:
    test    s4, s4
    jump    nz, outer_bubble_sort_loop
end_of_the_bubble_sort:

I managed to make the algorithm more efficient with the help of just one extra register, and by restructuring the code I reduced the number of jumps.

I know it is a matter of taste, but I do prefer the nice tabular format that I have used in this code.

Avoid the unconditional jump

A repeat until <cond> loop is often better than a while <cond> wend loop because the latter has at its bottom an unconditional jump in order to return to the top of the loop. Make it count and put the condition below, especially when you know beforehand that on the very first iteration the condition is going to be true anyway. Take eg. the printing_the_sorted_array code: you know for a fact that length_of_the_input is at least 1 (one test below your input loop guarantees this), so you can write it as follows:

printing_the_sorted_array:
  call    print_the_sorted_array_message
  xor     s0, s0   ; -> s0 = 0
printing_the_sorted_array_loop:
  fetch   s9, (s0)
  call    UART_TX
  add     s0, 1
  compare s0, length_of_the_input
  jump    c, printing_the_sorted_array_loop

The benefit is threefold:

  • better readability since you no longer need the label end_of_the_printing_the_sorted_array_loop
  • you save on code size because no jump
  • you gain on execution speed because one instruction less to execute per iteration

You can optimize the reset_ordinal_numbers_loop in the same way.

And then there's the permutation code

I gave it a shot, but I could not penetrate what looks to me like a wall of code with little on no comments!

I would suggest that you

  • partition the program more by inserting blank lines between any two logical parts
  • delegate a number of sub tasks to subroutines, eg. copying_the_current_attempt_from_the_stack_loop could be such a subroutine
\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.