Quiz 2 of Computer Architecture (2024 Fall)

General Information

• You are allowed to read lecture materials and run RISC-V code inside the Ripes simulator.

  That is, an open book exam.

• We are using the honor system during this quiz, and would like you to accept the following:
  1. You will not share the quiz with anyone.
  2. You will not discuss the material on the quiz with anyone until after solutions are released.
• Download the PDF document at the bottom of this page, which contains the problem set for Quiz 2. You will be prompted to enter a password. Ensure that you have read the notice at the end of this page.
• Each answer has 4 points.
• You must answer in valid numeric representation and/or English alphabet except your formal name.
• Always provide your answer in the shortest form. For example, use ptr->member instead of (*ptr).member.
• Assume that each C program already includes the headers <stdint.h>, <stdbool.h>, <stddef.h>, <stdlib.h>, and <stdio.h>.
• The C standard referenced in this quiz is C99, officially known as ISO/IEC 9899:2018.
• Message the instructor via Facebook if you found something wrong.
• 10:30 ~ 11:59AM on Oct 1, 2024
• Submit via Google Form.

Problem set for Quiz 2

$\to$ The password for the PDF document is the answer to the question below.

Imagine you are playing the Bulls and Cows game, where "A" indicates a digit is in the correct position and "B" signifies a digit is present but in the wrong position. For example, if your secret number is 4545 and your opponent guesses 5122, the response would be 0A1B. This means that no digits are correctly placed and one digit is correct but misplaced. Then, we can construct a hexadecimal integer literal based on the answer, 0x0A1B.

As you continue playing the Bulls and Cows game, pay close attention to the secret number provided by the instructor. For example, if your opponent guesses 1224, you should retain the hexadecimal integer literal derived from a response of ?A?B.

In the context of RISC-V assembly, assume that register x10 holds the value constructed from the Bulls and Cows game, which includes the secret number provided by the instructor and the opponent's guess of 1224. What will be the value in register x12 after executing the following instructions?

slli x12, x10, 0x12
srli x12, x12, 0x6
and  x12, x12, x10

Enter the password in all lowercase when inputting it into the PDF document. The value must be represented as a hexadecimal integer literal, starting with 0x and always in its shortest form. That is, use 0x42 rather than 0x0042.

Hint: The password is 6 characters long.

Errata

For clarity, the C program referenced in Problem C is reproduced below:

static void print_move(int disk, char from, char to) {
    printf("Move Disk %d from '%c' to '%c'\n", disk, from, to);
}

int main() {
    int n_disks = 3; /* Number of disks */

    int total_moves = (1 << n_disks) - 1;
    const char pegs[3] = {'A', 'B', 'C'}; /* Peg labels */
    int pos[n_disks]; /* Disk positions: 0-A, 1-B, 2-C */

    /* Initialize all disks to peg A */
    for (int i = 0; i < n_disks; i++)
        pos[i] = 0;

    /* Set direction based on parity of number of disks */
    int direction = (n_disks & 1) ? -1 /* counter-clockwise */
                                    : 1; /* clockwise */

    /* Predefined packed mapping arrays */
    const uint8_t peg_map[3] = {
        #C01, /* Peg A: {CCW -> C (2), CW -> B (1)} */
        #C02, /* Peg B: {CCW -> A (0), CW -> C (2)} */
        #C03  /* Peg C: {CCW -> B (1), CW -> A (0)} */
    };

    /* Calculate direction index: -1 -> 0 (CCW), 1 ->1 (CW) */
    int direction_index = (direction + 1) / 2;

    for (int n_moves = 1; n_moves <= total_moves; n_moves++) {
        int curr_gray = n_moves ^ (n_moves >> 1);
        int prev_gray = (n_moves - 1) ^ ((n_moves - 1) >> 1);
        int changed_bit = curr_gray ^ prev_gray;

        /* Identify the disk to move (0-indexed) */
        int disk = __builtin_popcount(#C04);

        /* Current peg of the disk */
        int curr_peg = pos[disk];
        int new_peg;

        if (disk == 0) {
            /* Calculate shift: direction_index=0 (CCW) -> shift2,
             * direction_index=1 (CW) -> shift0
             */
            int shift = (1 - direction_index) << 1;
            new_peg = (peg_map[curr_peg] >> shift) & C05;
        } else {
            bool found_new_peg = false;
            for (int p = 0; p < 3 && !found_new_peg; p++) {
                if (p == curr_peg)
                    continue;

                bool has_smaller = false;
                for (int d = 0; d < disk; d++) {
                    if (pos[d] == p) {
                        has_smaller = true;
                        break;
                    }
                }

                if (!has_smaller) {
                    new_peg = p;
                    found_new_peg = true;
                }
            }
        }

        print_move(disk + 1, pegs[curr_peg], pegs[new_peg]);
        pos[disk] = new_peg;
    }

    return 0;
}