Aufgabe 1

Aufgabe 1 (a)
=============

> Wie kann man einen Addierer als Subtrahierer verwenden?

Ein Addierer kann als Subtrahierer verwendet werden, indem  das zweite Argument
negiert wird.
$a - b = a + (-b)$

Im Zweierkomplement können wir eine Zahl negieren, indem wir alle ihre Bits
einzeln negieren, und dann 1 addieren. D.h., im Addierer verbinded wir alle
Eingänge, die vorher mit den Bits der Zahl b verbunden waren, mit den Bits von
~b, und setzen das eingehende Carry des ersten Volladdierers auf 1.

Aufgabe 1 (b)
=============

> Was ist eine “hidden one”?

Gleitkommazahlen werden gewöhnlich binär im IEEE-Format gespeichert. Da – nach
Konvention – vor dem Komma nie eine Null stehen sollte, und im Binärformat also
automatisch eine eins vorliegen muss, spart das IEEE-Format sich diese
Eins im Speicher, und sie wird erst bei der Konvertierung in andere Formate
hinzugefügt.

D.h., eine “hidden one” ist eine Eins, die die einzige Vorkommastelle einer
Gleitkommazahl ist, aber im Speicher nicht dargestellt wird.

(Eine Ausnahme sind die Subnormalen Zahlen, bei welchen diese Konvention
gebrochen wird, um die Darstellung von der Null zu ermöglichen).

Aufgabe 2

// Smallest common multiple
// ------------------------
//
// Takes two numbers a, b and returns the smallest common multiple of a and b
//
// input:  mem1000
//         mem1004
// output: mem1008
//
// vars:   R1, R3   work variable #1 (and local copies of it)
//         R2, R4   work variable #2 (and local copies of it)
//         R5       flags for comparisons

start:
    LW   R1, 1000(R0)   // load parameter 1 (from now on initial_x)
    LW   R2, 1004(R0)   // load parameter 2 (from now on initial_y)
    XOR  R3, R1, R0     // copy initial_x from R1 into R3 (from now on work_x)
    XOR  R4, R2, R0     // copy initial_y from R1 into R3 (from now on work_y)


// We want to increment the smaller of both numbers until it surpasses the
// other larger number, we do this by checking in each step which number is the
// smaller one, and then adding its initial value one time to it

// this is equivalent to the following C code:

//     int initial_x, work_x;
//     int initial_y, work_y;
//     work_x = initial_x;
//     work_y = initial_y;
//
//     while (true) {
//       if (x < y) {
//          work_x += initial_x;
//       } else if (y < y) {
//          work_y += initial_y;
//       } else {
//          break;
//       }
//     }

loop:
if<:
    SLT  R5, R3, R4     // if x < y:
    BEQZ R5, if>        // (otherwise go to if>)
    
    ADD  R3, R3, R1     // increment work_x by x
    
    J    loop           // go back to the loop head
if>:
    SLT  R5, R4, R3     // if y < x:
    BEQZ R5, else       // (otherwise go to else)
    
    ADD  R4, R4, R2     // increment work_y by y
    
    J    loop           // go back to the loop head
else:
    SW   1008(R0), R3   // if (x < y) is false, and (y < x) is false, then
                        // x = y therefore we are finished here and can just
                        // write the result back into memory
    HALT

Aufgabe 3

start:
    ADD  R2, R0, R0     // Initialize r2 with 0
    ADD  R3, R1, R0     // copy parameter r1 into work register r3
    ADDI R4, R0, #32    // Initialize loop counter r4 with 32
    ADD  R5, R4, R0     // Initialize r5 with r2 (by copying r4 into r5)
loop:
    ANDI R6, R3, #1     // set r6 to r3 modulo 2
                            // This sets r6 to 1 if the last bit of r3 is one,
                            // otherwise r6 is set to 0
    ADD  R2, R2, R6     // add r6 to r2
                            // This (plus the line above) essentially
                            // increments r2 every time r3’s last bit is 1
    SRLI R3, R3, #1     // shift r3 one to the right
    SUBI R4, R4, #1     // decrement the loop counter r4
    BNEZ R4, loop       // if the loop counter is larger than 0, loop again
end:
    SUB  R2, R5, R2     // caculate 32 (size of a word) minus r2
                        // (which at this point contains the amount of bits
                        // in r1 that are set to 1)
                            // This – total amount of bits in r3 minus amount
                            // of bits that are set to 1 in r3 – results in r2
                            // holding the amount of bits in r3 that are set to
                            // zero
    HALT                // end the program

The program counts the bits with value zero in r1

Aufgabe 4

// Multiplication Modulo 4
// -----------------------
//
// Takes two numbers a, b and return a*b modulo 4
// WARNING: This function uses the mathematical modulo, where the sign of the
// input and the output are always equal.
// (Compared to the always-positive modulo that common in some other languages)
//
// input:  mem1000
//         mem1004
// output: mem1008
//
// vars:   R1, R3   work variable #1 (and local copies of it)
//         R2, R4   work variable #2 (and local copies of it)
//         R5       sign variable (stores the sign difference)
start:
    LW   R1, 1000(R0)   // load r1 from memory
    LW   R2, 1004(R0)   // load r2 from memory

sign:
    XOR  R3, R1, R0     // copy r1 into r3
    XOR  R4, R2, R0     // copy r2 into r4
    SRLI R3, R3, #31    // set r3 to the first bit of r3
    SRLI R4, R4, #31    // set r4 to the first bit of r4
    
    XOR  R5, R3, R4     // set r5 to 1 if r3 and r4 (the signs of r1 and r2)
                        // are  different

mul:
    ANDI R3, R1, #3     // copy the last two bits from r1 into r3
    ANDI R4, R2, #1     // copy the last bit from r2 into r4
    SUB  R4, R0, R4     // set r4 to 0xFFFF whenever r4 is 1, otherwise 0x0000
    AND  R3, R3, R4     // and r4 and r3, store the result in r3
                            // This takes the last two bits from r3 and the
                            // last bit from r4 and "multiplies" them with the
                            // algorithm known from the lecture
    ANDI R3, R3, #3     // truncate this value to [0,4]
                        // essentially sign-less modulo 4
    
    SLLI R1, R1, #1     // shift r1 one to the left
                            // We do this because we are finished with
                            // calculating the values for the last bit of the
                            // result, and only need to calculate the values
                            // for the remaining bits from now on, so we can
                            // move our offset by one
                            
    SRLI R2, R2, #1     // shift r2 one to the right
                            // as we already multiplied r1 with the last bit of
                            // r2, we can shift to let this last bit fall off
                            // and additionally prepare for the next
                            // multiplication step
    
    
    ANDI R1, R1, #3     // apply the same algorithm as above
    ANDI R2, R2, #1
    SUB  R2, R0, R2
    AND  R2, R1, R2
    
    ADD  R3, R3, R2     // add the differences     
    ANDI R3, R3, #3     // remove all bits but the last 2 (abs version of mod4)


    ADD  R3, R3, R5     // add r3 and r5 (the sign variable, so if r3 should be
                        // negative, we add 1)
                        
    SUB  R5, R0, R5     // put 0xFFFF into r5 if the signs of the original r1
                        // and r2 are different, otherwise 0x0000
                        
    XOR  R3, R3, R5     // xor r3 with this value, this essentially flips r3
                        // whenever the signs of the original r1 and r2 are
                        // different
end:
    SW   1008(R0), R3   // store r3 in memory
    HALT