FILE : 03A0SOLN.txt NAME : SOLUTIONS, NoFrills HW# : 3 PROGRAM: A ================================================================================ Problem Statement: ================================================================================ Given exactly four random values stored on Cards #N through #(N+3), write a program that sorts those values into ascending order. The value of N will be such that all four cards will be located in upper memory (Cards #10 through #19). The program should be written such that the value of N can be changed by changing a single EQU directive. ================================================================================ Problem Solution: ================================================================================ There are many possible solutions to this problem. Considering how the problem might be solved by a child with a physical stack of cards to be sorted, we might search through the deck and find the largest card that is present. We would then remove that card from the deck and place it off to the side. With the original deck now containing one less card, we would repeat this process and remove the largest card remaining and place it on top of the first card we removed. We would continue this process until we ran out of cards. We could also make a series of passes through the deck and on each pass step from the first card to the last card. At each step we would enquire if the card we are looking at and the next card were in the proper order or not. If they were, we would move on. If they were not, we would swap them before moving on. At the end of the first pass, we would be guaranteed that the card that should be at the end of the list has migrated to that position. After the second pass we would be know that the card that should be next to last has made it to that position. After (N-1) passes, we would have a completely sorted list. This is known as a "bubble sort". The method we will take here is generally called a "selection sort". In some ways it is a combination of the two previous methods. We will search the list and find the location of the largest card in the list. We will then swap that card with whatever card is sitting where the identified card belongs. So after the first pass, we will swap the largest card with whatever card is at the end of the list. On the second pass we will swap the largest card (not including the last card) with whatever card is in the next to last position. On each pass, we will terminate our search one card earlier than the previous pass in recognition of the fact that our list of sorted cards is growing. When we reach the point that our search no longer involves at least two cards, we are done. ================================================================================ Hand Example: ================================================================================ Let's say we store the values {4,7,3,5} on starting on Card #10. Card: 10 11 12 13 Value: 4 7 6 3 At the beginning of the first pass, we know that we want to store the result in the last card, namely Card #13. We would then scan the values on the cards from #10 through #13 and identify Card #11 as having the largest value. After swapping the values on Cards #11 and #13, We would be left with: Card: 10 11 12 13 Value: 4 3 6 7 On the next pass We know we want to store the result on Card #12. We would scan the values on the cards from #10 through #12 and identify Card #12 as having the largest value. We could recognize that there is no need to swap anything, or we could simply swap the values on Card #12 with the value on Card #12 as long as no error results. Either way, after doing this we will still have the same order and will be ready to start the next pass. On this pass, We intend to store the result on Card #11 and identify Card #10 as the card with the highest value. After swapping them, We are left with: Card: 10 11 12 13 Value: 3 4 6 7 And on our next pass we would want to store the result on Card #10. But since this is also the first card in the list, there is no need to do so. We are done. ================================================================================ Algorithm Development: ================================================================================ TO show the development process, the following steps show the incremental nature of the Top-Down procedure: STEP #1: ========== PROBLEM: Sort Cards using a "Selection Sort" 1) TASK: Initialize "bookkeeping values" 2) TASK: Perform passes through the cards until sorting is complete. STEP #2: ========== 1) TASK: Initialize "bookkeeping values" 1.1) SET: FIRSTCARD = 10 // Or whatever value is appropriate 1.2) SET: CARDS = 4 // Number of Cards in list to be sorted. 1.3) SET: LASTCARD = (FIRSTCARD + CARDS - 1) 2) TASK: Perform passes through the cards until sorting is complete. 2.1) LOOP: While (LASTCARD > FIRSTCARD) 2.1.1) TASK: Identify Largest Card from FIRSTCARD to LASTCARD 2.1.2) TASK: Swap LARGESTCARD with LASTCARD 2.1.3) TASK: Decrement LASTCARD At this point, Task #1 is complete, unless further work reveals some piece of additional information that must be initialized. Task #2 is divided into four tasks (when we include implementing the loop test). Our next step will either solve these or break them down even further as necessary. STEP #3: ========== 1) TASK: Initialize "bookkeeping values" 1.1) SET: FIRSTCARD = 10 // Or whatever value is appropriate 1.2) SET: CARDS = 4 // Number of Cards in list to be sorted. 1.3) SET: LASTCARD = (FIRSTCARD + CARDS - 1) 2) TASK: Perform passes through the cards until sorting is complete. 2.1) LOOP: While (LASTCARD > FIRSTCARD) 2.1.1) TASK: Identify Largest Card from FIRSTCARD to LASTCARD 2.1.1.1) SET: LARGESTCARD = FIRSTCARD // Largest Card seen yet on this pass 2.1.1.2) SET: PRESENTCARD = FIRSTCARD + 1 // Always start with second card 2.1.1.3) LOOP: while (PRESENTCARD <= LASTCARD) 2.1.1.3.1) IF (*PRESENTCARD > *LARGESTCARD) 2.1.1.3.1.1) SET: LARGESTCARD = PRESENTCARD 2.1.1.3.2) SET: PRESENTCARD = PRESENTCARD + 1 2.1.2) TASK: Swap LARGESTCARD with LASTCARD 2.1.2.1) SET: TEMP = *LASTCARD 2.1.2.2) SET: LASTCARD = *LARGESTCARD 2.1.2.3) SET: LARGESTCARD = *TEMP 2.1.3) TASK: Decrement LASTCARD 2.1.3.1) SET: LASTCARD = *LASTCARD - 1 We are now left with specific instructions that lend themselves directly to our ACME-1021 instructions provided we can implement the two tests associated with the two looping structures and the test associated with the selection structure. To ensure that we can do this, we will go ahead and build the skeleton for these structures first: 2.1) LOOP: While (LASTCARD > FIRSTCARD) If the two values are equal, then we want to exit the loop. Using the SUB instruction, no borrow will be generated under these conditions which means that we need to structure our SKP statement such that we exit the loop if no borrow occurs and stay in the loop if a borrow does occur. Correspondingly, our SUB instruction must produce a borrow when we want to stay in the loop: SUB JUNK, FIRSTCARD, *LASTCARD // Borrow if LASTCARD > FIRSTCARD SKP BORROW JMP OUT_OF_LOOP // Exit loop if LASTCARD <= FIRSTCARD JMP STAY_IN_LOOP // Stay in loop if LASTCARD > FIRSTCARD Notice that our pseudocode did not distinquish whether FIRSTCARD was a literal constant or a card number where the number of the first card was stored. This is an implementation issue that must be dealt with at the time of implementation. 2.1.1.3) LOOP: while (PRESENTCARD <= LASTCARD) Here we have the opposite situation and we wish to stay in the loop if the two values are equal. Hence our SUB instruction must produce a borrow when we want to exit the loop and our SKP instruction must be set up to exit the loop under those conditions: SUB JUNK, *LASTCARD, *PRESENTCARD // Borrow if PRESENTCARD > LASTCARD SKP BORROW JMP STAY_IN_LOOP // Stay in loop if PRESENTCARD <= LASTCARD JMP OUT_OF_LOOP // Exit loop if PRESENTCARD > LASTCARD 2.1.1.3.1) IF (PRESENTCARD > LARGESTCARD) This is the same test type as the first loop, so our SUB/SKP statements are configured similarly: SUB JUNK, *LARGESTCARD, *PRESENTCARD // Borrow if *PRESENTCARD > *LARGESTCARD SKP BORROW JMP OVER_IF_CODE // Jump over if *PRESENTCARD <= *LARGESTCARD // IF_CODE HERE // IF_CODE goes here ================================================================================ ACME-1021 ASSEMBLY CODE DEVELOPMENT ================================================================================ In looking over the pseudocode, we see that FIRSTCARD and CARDS are constants while LASTCARD, PRESENTCARD, and LARGESTCARD change as the program runs. Therefore we can use the former values as EQU directives directly but we need to store the latter values on cards. EQU FIRSTCARD (10) // Actual number of the first card in the list EQU CARD (4) // Actual number of cards in the list EQU BORROW (1) // Card number where the borrow result is stored after a SUB EQU TEMP (2) // Card number where temporary results can be stored EQU LARGESTCARD (3) // Card number where the number of the largest card is stored EQU PRESENTCARD (4) // Card number where the number of the presen card is stored EQU LASTCARD (5) // Card number where the number of the last card is stored 1) TASK: Initialize "bookkeeping values" 1.1) SET: FIRSTCARD = 10 // Or whatever value is appropriate 1.2) SET: CARDS = 4 // Number of Cards in list to be sorted. 1.3) SET: LASTCARD = (FIRSTCARD + CARDS - 1) ======> SET LASTCARD, (FIRSTCARD + CARDS - 1) // Constant expression 2) TASK: Perform passes through the cards until sorting is complete. 2.1) LOOP: While (LASTCARD > FIRSTCARD) ====> LABEL OUTER_LOOP ======> SUB TEMP, FIRSTCARD, *LASTCARD // Borrow if LASTCARD > FIRSTCARD ======> SKP BORROW ======> JMP END_OF_OUTER_LOOP // Exit loop if LASTCARD <= FIRSTCARD ======> JMP OUTER_LOOP_CODE // Stay in loop if LASTCARD > FIRSTCARD ====> LABEL OUTER_LOOP_CODE 2.1.1) TASK: Identify Largest Card from FIRSTCARD to LASTCARD 2.1.1.1) SET: LARGESTCARD = FIRSTCARD // Largest Card seen yet on this pass 2.1.1.2) SET: PRESENTCARD = FIRSTCARD + 1 // Always start with second card ======> SET LARGESTCARD, FIRSTCARD ======> SET PRESENTCARD, (FIRSTCARD + 1) 2.1.1.3) LOOP: while (PRESENTCARD <= LASTCARD) ====> LABEL INNER_LOOP ======> SUB TEMP, *LASTCARD, *PRESENTCARD // Borrow if PRESENTCARD > LASTCARD ======> SKP BORROW ======> JMP INNER_LOOP_CODE // Stay in loop if PRESENTCARD <= LASTCARD ======> JMP END_OF_INNER_LOOP // Exit loop if PRESENTCARD > LASTCARD ====> LABEL INNER_LOOP_CODE 2.1.1.3.1) IF (*PRESENTCARD > *LARGESTCARD) 2.1.1.3.1.1) SET: LARGESTCARD = PRESENTCARD ======> SUB TEMP, *LARGESTCARD, *PRESENTCARD // Borrow if *PRESENTCARD > *LARGESTCARD ======> SKP BORROW ======> JMP END_IF_CODE // Jump over if *PRESENTCARD <= *LARGESTCARD ====> LABEL IF_CODE ======> SET LARGESTCARD, *PRESENTCARD // Update largest card seen so far ====> LABEL END_IF_CODE 2.1.1.3.2) SET: PRESENTCARD = PRESENTCARD + 1 ======> ADD PRESENTCARD, *PRESENTCARD, 1 ======> JMP INNER_LOOP ====> LABEL END_OF_INNER_LOOP 2.1.2) TASK: Swap LARGESTCARD with LASTCARD 2.1.2.1) SET: TEMP = *LASTCARD 2.1.2.2) SET: LASTCARD = *LARGESTCARD 2.1.2.3) SET: LARGESTCARD = *TEMP ======> SET TEMP, *LASTCARD ======> SET LASTCARD, *LARGESTCARD ======> SET LARGESTCARD, *TEMP 2.1.3) TASK: Decrement LASTCARD 2.1.3.1) SET: LASTCARD = *LASTCARD - 1 ======> SUB LASTCARD, *LASTCARD, 1 ======> JMP OUTER_LOOP ====> LABEL END_OF_OUTER_LOOP ================================================================================ ACME-1021 ASSEMBLY CODE ================================================================================ EQU PROGRAM_START (1) // Line number for first instruction EQU FIRSTCARD (10) // Actual number of the first card in the list EQU CARD (4) // Actual number of cards in the list EQU BORROW (1) // Card number where the borrow result is stored after a SUB EQU TEMP (2) // Card number where temporary results can be stored EQU LARGESTCARD (3) // Card number where the number of the largest card is stored EQU PRESENTCARD (4) // Card number where the number of the presen card is stored EQU LASTCARD (5) // Card number where the number of the last card is stored ORG PROGRAM_START SET LASTCARD, (FIRSTCARD + CARDS - 1) // Constant expression LABEL OUTER_LOOP SUB TEMP, FIRSTCARD, *LASTCARD // Borrow if LASTCARD > FIRSTCARD SKP BORROW JMP END_OF_OUTER_LOOP // Exit loop if LASTCARD <= FIRSTCARD // TASK: Identify Largest Card SET LARGESTCARD, FIRSTCARD // Largest Card seen yet on this pass SET PRESENTCARD, (FIRSTCARD + 1) // Always start with second card LABEL INNER_LOOP // Single Pass through cards SUB TEMP, *LASTCARD, *PRESENTCARD // Borrow if PRESENTCARD > LASTCARD SKP BORROW JMP INNER_LOOP_CODE // Stay in loop if PRESENTCARD <= LASTCARD JMP END_OF_INNER_LOOP // Exit loop if PRESENTCARD > LASTCARD LABEL INNER_LOOP_CODE SUB TEMP, **LARGESTCARD, **PRESENTCARD // Borrow if *PRESENTCARD > *LARGESTCARD SKP BORROW JMP END_IF_CODE // Jump over if *PRESENTCARD <= *LARGESTCARD LABEL IF_CODE SET LARGESTCARD, *PRESENTCARD // Update largest card see so far LABEL END_IF_CODE ADD PRESENTCARD, *PRESENTCARD, 1 // Move on to next card JMP INNER_LOOP LABEL END_OF_INNER_LOOP SET TEMP, **LASTCARD // Swap Largest Card with Last Card SET *LASTCARD, **LARGESTCARD SET *LARGESTCARD, *TEMP SUB LASTCARD, *LASTCARD, 1 // Remove last card from next search loop JMP OUTER_LOOP LABEL END_OF_OUTER_LOOP NOP // Just to have someplace to jump to ================================================================================ ACME-1021 INSTRUCTION DECK ================================================================================ The steps involved in translating the Assembly Code to an Instruction Deck are as follows: 1) Number each instruction line (do not number labels or comment lines) 2) Resolve the label statements (figure out the corresponding instruction number) 3) Replace the Label names in JMP instructions with the instruction numbers 4) Replace EQU constants with their equivalent values 5) Evaluate all constant expressions 6) Remove all ORG, EQU, and LABEL directives as well as all comments 1 SET 5, 13 2 SUB 2, 10, *5 3 SKP 1 4 JMP 22 5 SET 3, 10 6 SET 4, 11 7 SUB 2, *5, *4 8 SKP 1 9 JMP 11 10 JMP 17 11 SUB 2, **3, **4 12 SKP 1 13 JMP 15 14 SET 3, *4 15 ADD 4, *4, 1 16 JMP 7 17 SET 2, **5 18 SET *5, **3 19 SET *3, *2 20 SUB 5, *5, 1 21 JMP 2 22 NOP ================================================================================ EXAMPLE PROGRAM EXECUTION ================================================================================ Memory Set up: The program was translated based on there being 4 values starting at Card #10: Memory Map |00|01|02|03|04|05|06|07|08|09|10|11|12|13|14|15|16|17|18|19| |==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==| | | | | | | | | | | | 4| 7| 6| 3| | | | | | | | | 1|97|10|11|13| | | | | | | | | | | | | | | | | 0| 2|11|12| | | | | | | | | | | | | | | | | | 1|97| | | | | | | | | | | | | | | | | | | | 0| | | | | | | | | | | | | | | | | | | |==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==| INST 16 | | 0| 1| |13| | | | | | | | | | | | | | | | | | 0| 1| | | | | | | | | | | | | | | | | | | | 0| | | | | | | | | | | | | | | | | | | |==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==| INST 16 | | 0| 0| |14| | | | | | | | | | | | | | | | | | 0| 4| | | | | | | | | | | | | | | | | | | | 0| | | | | | | | | | | | | | | | | | | |==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==| INST 16 | | 1|99| | |12| | | | | | 3| | 7| | | | | | | | | 0| 3| | | | | | | | | | | | | | | | | | |==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==| INST 21 | | 1|98|10|11| | | | | | | | | | | | | | | | | | 0| 1| |12| | | | | | | | | | | | | | | | | | 0| 1| | | | | | | | | | | | | | | | | | | | 0| | | | | | | | | | | | | | | | | | | |==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==| INST 16 | | 0| 0|12|13| | | | | | | | | | | | | | | | | | 1|98| | | | | | | | | | | | | | | | | | | | 0| | | | | | | | | | | | | | | | | | | |==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==| INST 16 | | 1|99| | |11| | | | | | | 6| | | | | | | | | | 0| 6| | | | | | | | | | 6| | | | | | | | |==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==| INST 21 | | 1|99|10|11| | | | | | | | | | | | | | | | | | 0| 0| |12| | | | | | | | | | | | | | | | | | 0| 1| | | | | | | | | | | | | | | | | | | | 0| | | | | | | | | | | | | | | | | | | |==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==| INST 16 | | 1|99| | |10| | | | | 3| 4| | | | | | | | | | | 0| 3| | | | | | | | | | | | | | | | | | |==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==| INST 21 | | 0| 0| | | | | | | | | | | | | | | | | | |==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==|==| INST 22 | | | | | | | | | | | | | | | | | | | | | | | 0| 0|11|12|10| | | | | 3| 4| 6| 7| | | | | | | FINAL | | | | | | | | | | | | | | | | | | | | |