Introduction

In this lab, students will build a fully functional two-player checkers game using the RARS MMIO simulator. Students will use keyboard interrupts and write their own handler to allow real time player input. Students will represent the game state using efficient 32-bit bitboards to track the positions of pieces, generate legal moves, and enforce game rules such as jumps and promotions.

By the end of this lab, students will:

• Understand and implement asynchronous execution through interrupt and exception handling.
• Understand Memory-Mapped I/O (MMIO).
• Develop practical skills in bitwise operations and data representation using bitboards.
• Deepen their understanding of programming in RISC-V.
• Create a fun, playable, classic board game from scratch.

Background

Checkers Game

Checkers is a two player strategy board game, the name checkers comes from the checkered chess board the game is played on. Below is a quick reference list of the terminology used for this lab.

Board

Refers to the 8x8 checkered board that the game is played on. The board is made up of 64 squares.

Square

The basic unit of the board, each square can have a piece or be empty. There are 64 squares on the board, but only 32, the dark squares, are game squares.

Rank

The rank of a square is the row number from the players perspective, the rank ranges from 8 -> 1 starting from the top of the board. The rank of a row is shown on the left and right sides of the board, and describes the row of a square in a consistent, human readable way.

The row index, or row number of a row is the index of the row in the internal representation of the board, the index ranges from 0 -> 7 starting from the top of the board.

File

The file of a square is the column number from the players perspective, the file ranges from a -> h starting from the left side of the board. The file of a column is shown on the top and bottom sides of the board, and describes the column of a square in a consistent, human readable way.

The column index, or column number of a column is the index of the column in the internal representation of the board, the column index ranges from 0 -> 7 starting from the left side of the board.

Game Squares

The game squares are the 32 dark squares on the board that the game is actually played on. The game squares are the only squares on the board that can have pieces on them.

Piece

A piece means a man or king piece.

Slide Move

A slide move is a single square diagonal move of a piece to an unoccupied game square.

Jump Move (Capture)

A jump move is a two square diagonal move of a piece jumping over an opponent's piece to an unoccupied game square. The opponents piece is removed from the board and considered 'captured'.

Jump (capture) moves are forced, meaning that if there are valid jump moves, the player must make a jump move.

If a piece has an opportunity to make another jump move after it has made a jump move, a player can and must chain multiple jump moves in a single turn.

If there are multiple jump moves then the player may choose any of them.

Man

The man is the basic piece of the game, each player starts with 12 man pieces on their side of the board. Man pieces are only allowed to make forward slide and jump moves. Forward moves are moves that move the piece towards the opposing side of the board.

King

When a man piece reaches the opposing end of the board, it is promoted to a king piece. King pieces are identical to man pieces, except they are able to move both forward and backwards.

Color (Red or Black)

One player is assigned the black pieces, and the other player is assigned the red pieces. Black pieces move first.

Board Setup and Play

This is how the board is setup at the start of the game, red and black men are represented by 'r' and 'b' respectively, and red and black kings as 'R' and 'B'. The dark squares (game squares) are represented by '-', and light squares (non-game squares) are represented by a blank. The rank and file are shown on the sides of the board.

    a   b   c   d   e   f   g   h
  +---+---+---+---+---+---+---+---+
8 |   | b |   | b |   | b |   | b | 8
  +---+---+---+---+---+---+---+---+
7 | b |   | b |   | b |   | b |   | 7
  +---+---+---+---+---+---+---+---+
6 |   | b |   | b |   | b |   | b | 6
  +---+---+---+---+---+---+---+---+
5 | - |   | - |   | - |   | - |   | 5
  +---+---+---+---+---+---+---+---+
4 |   | - |   | - |   | - |   | - | 4
  +---+---+---+---+---+---+---+---+
3 | r |   | r |   | r |   | r |   | 3
  +---+---+---+---+---+---+---+---+
2 |   | r |   | r |   | r |   | r | 2
  +---+---+---+---+---+---+---+---+
1 | r |   | r |   | r |   | r |   | 1
  +---+---+---+---+---+---+---+---+
    a   b   c   d   e   f   g   h

The game is played by two players, one player is assigned the black pieces, and the other player is assigned the red pieces. The player assigned the black pieces always moves first. The players take turns moving a single piece.

If a player has the opportunity to make a jump move, they must do so. If a player has multiple jump moves available, they may choose any of them. A player must chain multiple jump moves with a single piece together in a single turn, as long as each jump is a valid move.

Otherwise, the player may make a slide move. You win the game when your opponent has no moves left, this is most commonly achieved by capturing all of your opponent's pieces. If a man piece reaches the opposing end of the board, it is promoted to a king piece immediately. Meaning a piece can be promoted after a jump move, and then immediately jump backwards again in the same turn.

Board Representation

Bitboards

Although the board is made up of 64 squares, only 32 of them have any impact on the game. Thus, the solution only needs to store information about 32 squares. This information can be stored in three 32-bit RISC-V words, where each bit in the word represents a game square on the board. Each one of these words is called a bitboard:

• BLACK: A set bit represents a black piece on the board.
• RED: A set bit represents a red piece on the board.
• KINGS: A set bit represents a king piece on the board. The KINGS bitboard stores the positions of both red and black kings at the same time.

In addition to the three bitboards, the solution will also use the provided TURN global variable to keep track of which player's turn it is. TURN is a 32-bit word that is either:

• 0: The next move is made by BLACK.
• 1: The next move is made by RED.

Square Mapping Conventions

This lab use the following mapping conventions to map the squares to the bit positions in a bitboard.

The Least Significant Bit is bit 0, and the Most Significant Bit is bit 31. The indexes of the squares correspond to the index of the bits in the bitboard (word).

The mapping of game squares to bitboard indexes follows a Rank-File order, meaning that every file (a -> h) is indexed in a rank before moving to the next rank (8 -> 1). A visual representation of the mapping is shown below.

Rank 8 .. Rank 1 -> Row 0 .. Row 7
A-File .. H-File -> Column 0 .. Column 7

The mapping of the squares to indexes is shown below, an easy way to remember the mapping conventions is the index increases from left -> right, top -> bottom. This is the order in which the page of a book is read in English.

For example Black's starting bitboard in different formats:

• Binary: 00000000 00000000 00001111 11111111
• Hexadecimal: 0x00000FFF

Move Generation

Bitboard Manipulation

The solution for this lab uses bitwise operations on bitboards in order to generate moves, capture and promote pieces, manipulate the game state, and more.

A bitwise logical shift changes the index of all the squares in a bitboard. For example, shifting a bitboard left by four is equivalent to moving all the pieces in the bitboard from their original square_index to square_index + 4.

A bitwise logical left shift is said to be a shift down, because it moves the pieces down the board, and a bitwise logical right shift is said to be a shift up, because it moves the pieces up the board.

Bitwise AND (&) and OR (|) on bitboards work as expected:

• The bitwise AND of two bitboards results in a bitboard of squares that are in both sources. The bitwise AND is useful with boards such as NOCC, taking the bitwise AND with any other bitboard to filter only the unoccupied squares.
• The bitwise OR of two bitboards results in a bitboard of squares that are in either of the two sources. Taking the bitwise OR is useful for combining two bitboards into one, this will be essential for generating moves, as the bitboards produced from each of the different shifts need to be combined into a single bitboard that contains all the moves.

In an array representation board, where shifting a square could be represented as board[index + 4] = board[index], the programmer has to consider out of bounds array indexes. Out of bounds indexing is not something that needs to be considered with this labs bitboard representation.

Useful Bitboards

It might be useful for the solution to maintain, or compute, additional bitboards. Here are some examples:

• NOCC: A set bit indicates that a square of the board is not occupied. NOCC = ~(BLACK | RED)
• (RED/BLACK)_KINGS: A set bit indicates a king piece of a specified color. (RED/BLACK)_KINGS = (RED/BLACK) & KINGS
• ZERO_BB: All bits are zero. This bitboard is useful for returning an empty or invalid result from a function. ZERO_BB = 0x00000000

Generating Slide Moves

A slide move is a single square diagonal move of a piece to an unoccupied game square.

The generation of slide moves requires an algorithm that transforms a source bitboard of any number and position of pieces, to a bitboard of all possible slide moves from those pieces. One such algorithm generates the slide moves down, and slide moves up. The color of the pieces in the source bitboard (which is the same as the current TURN) determines which direction (up or down) is forward (MAN and KING slides) and which direction is backward (KING slides only).

The algorithm uses bitwise shifts and operations to generate the slide moves. However not all squares need to be shifted the same number of spaces to generate the slide moves. This issue can be solved by using masks to isolate squares that need to be shifted by a certain value.

The diagram below illustrates which shifts generate which slide move for some example squares. The small numbers in the squares represent the index of in the square in the bitboard. The large numbers show the change in index from the source of the arrow to the destination of the arrow. A negative number indicates a right shift, and a positive number indicates a left shift.

For instance, for downward moves, every square has at most two downward slide moves, any square can be left shifted by four to generate the first downward slide move. In the case that the source square is in the bottom row (row 7, rank 1), shifting left to generate the slide moves will shift the set bits off the end of the bitboard, thus meaning that no move is contributed to the slide moves bitboard. This is not an issue, as there are no valid downward slide moves for squares in the bottom row (row 7 | rank 1), so every square can be left shifted by 4 without issue.

Some squares have a second possible move, it falls into one of two cases:

• The square needs to be left shifted by three to generate the second downward slide move. This is the case when the square is an odd row (rows 1,3,5,7 | ranks 7,5,3,1), and the square is not in file 'a' or 'h' (columns 0,7). A visual representation of the squares this applies to is below.
• The square needs to be left shifted by five to generate the second downward slide move. This is the case when the square is an even row (rows 0,2,4,6 | ranks 8,6,4,2), and the square is not in file 'a' or 'h' (columns 0,7). A visual representation of the squares this applies to is below.

To handle the different shifts for different squares, the solution will use four masks to isolate the squares that need to be shifted down three, up three, down five, up five. Conveniently, the squares that need to be shifted down by three are the same squares that need to be shifted up by five, and the squares that need to be shifted down by five are the same squares that need to be shifted up by three.

The algorithm for generating upward and downward slide moves are nearly identical. To generate upward slide moves, shift right instead of left, and use the THREE_U and FIVE_U masks instead of the THREE_D and FIVE_D masks.

The masks to isolate the squares that need to be shifted by 3 or 5 are as follows

THREE_D = 0xE0E0E0E0 = FIVE_U

THREE_D = 0xE0E0 E0E0

FIVE_U = 0xE0E0 E0E0

FIVE_D = 0x07070707 = THREE_U

FIVE_D = 0x0707 0707

THREE_U = 0x0707 0707

The algorithm below generates slide moves for a SRC bitboard of black pieces. The algorithm can be easily adapted to generate slide moves for red pieces by swapping the directions of the King and Man/King slides. The algorithm below preforms no checks, and assumes that the source bitboard SRC contains only black pieces.

S_KINGS = SRC & KINGS
NOCC = ~(BLACK | RED)

# Upward Slides (Man and King slides for black)
MOVES = (SRC << 4)
MOVES |= ((SRC & THREE_D) << 3)
MOVES |= ((SRC & FIVE_D) << 5)

# Downward Slides (King slides for black)
MOVES |= (S_KINGS >> 4)
MOVES |= ((S_KINGS & THREE_U) >> 3)
MOVES |= ((S_KINGS & FIVE_U) >> 5)

MOVES &= NOCC

• SRC bitboard may contain any number of pieces in any positions.
• Passing an entire color as SRC is useful for checking win condition.
• The same algorithm can be applied to get the slide moves for red, just swap the shift directions for man and king slides.
• If SRC or S_KINGS is a ZERO_BB, then the move gen algorithm will produce a ZERO_BB for that section of the move generation.
• MOVES is a bitboard consisting of all squares reachable by slide move from the pieces in SRC. There is no way to tell which piece in SRC slides to which square in MOVES, unless the SRC bitboard has only a single set bit.

Generating Jump Moves

A jump move is a two square diagonal move of a piece jumping over an opposing piece to an unoccupied square.

To generate any possible jump move, the algorithm needs a way to transform a bitboard of any piece, to the bitboard that represents the four diagonal jump moves.

To generate jump moves, first start with generating the slide moves, then instead of finding the unoccupied squares, find the squares that are occupied by an opposing piece, and then shift those squares to the square that is two squares diagonally away from the the source piece.

There is a pattern that the bitboard indices follow for determining the jump move targets. If the first shift to determine where an opposing piece might be is a shift by four, then the second shift to determine the jump move target is a shift by three or five. Vice versa: if the first shift to determine where an opposing piece might be is a shift by three or five, then the second shift to determine the jump move target is a shift by four.

The masks to isolate the squares that need to be shifted by 3 or 5 are as follows (identical to previous masks):

• THREE_D = 0xE0E0E0E0 = FIVE_U
• FIVE_D = 0x07070707 = THREE_U

Assuming the SRC bitboard only contains red pieces, we can apply the following bitboard transformations to obtain a bitboard of all jump moves from pieces in SRC

S_KINGS = SRC & KINGS
NOCC = ~(BLACK | RED)

# Upward Jumps (Man jumps for red)
ADJ_OPP = (SRC >> 4) & BLACK        # Adjacent Opponent Pieces

MOVES = ((ADJ_OPP & THREE_U) >> 3)
MOVES |= ((ADJ_OPP & FIVE_U) >> 5)

ADJ_OPP = ((SRC & THREE_U) >> 3)
ADJ_OPP |= ((SRC & FIVE_U) >> 5)
ADJ_OPP &= BLACK                    # Adjacent Opponent Pieces

MOVES |= ADJ_OPP >> 4


# Downward Jumps (Man and King jumps for red)
ADJ_OPP = (S_KINGS << 4) & BLACK    # Adjacent Opponent Pieces

MOVES |= ((ADJ_OPP & THREE_D) << 3)
MOVES |= ((ADJ_OPP & FIVE_D) << 5)

ADJ_OPP = ((S_KINGS & THREE_D) << 3)
ADJ_OPP |= ((S_KINGS & FIVE_D) << 5)
ADJ_OPP &= BLACK                    # Adjacent Opponent Pieces

MOVES |= ADJ_OPP << 4

MOVES &= NOCC

• SRC bitboard can contain multiple pieces
• Passing an entire color as SRC is useful for checking win condition.
• The same transformation can be applied to generate jump moves for black, just swap the shift directions for man and king jumps, and ensure you are checking for opposing pieces to jump over.
• If SRC or S_KINGS is a ZERO_BB, then the move gen algorithm will produce a ZERO_BB for that section of the move generation.
• MOVES is a bitboard consisting of all squares reachable by jump move from the pieces in SRC. There is no way to tell which piece jumps to which square, unless the SRC bitboard has only a single set bit.

Interrupts

Exceptions and interrupts are two types of events that can disrupt a RISC-V program's execution. An exception is directly caused by the instructions a program is executing, such as an address out of range error. Interrupts are triggered by external sources and can occur at any point during program execution, such as a timer interrupt. When an interrupt or exception occurs, the normal flow of the program is paused, and control is transferred to an interrupt handler.

A handler will perform any actions required by the interrupt or exception. After the handler completes its task, if it hasn't terminated the program (as handlers often do in response to exceptions), the program's execution usually resumes at the instruction that was about to be executed when the interrupt or exception occurred.

In some cases, control cannot safely be returned to the interrupted code after an exception. In such cases, the program is terminated. This lab is only concerned with handling keyboard interrupts, all exceptions and other interrupts should terminate the program by jumping to handlerTerminate.

Control and Status Registers

This lab uses external interrupts from hardware. The role of the following CSRs (Control and Status Registers) are important for the use of interrupts:

• ustatus (User Status Register, CSR#0) is a 32-bit register that controls and manages user-level interrupts. To enable user-level interrupts set the 0th bit of this register to 1.


• uie (User-Interrupt Enable Register, CSR#4) is a 32-bit register that controls the types of user-level interrupts that are enabled using a bitmask. To enable user-level external keyboard interrupts set the 8th bit of this register to 1.


• utvec (User Trap-Vector Base-Address Register, CSR#5) is a 32-bit register that controls where interrupts are handled. The register holds the address of the interrupt handler that should be called when an interrupt or exception occurs. The address of the handler can be stored in utvec with the following instructions la t0, handler and csrw t0, 5


• ucause (User Trap Cause Register, CSR#66) is a 32-bit register that identifies the type of interrupt that is being handled. After an exception or an interrupt, this register holds the interrupt/exception code to help identify its cause using the code table. An exception code is stored in the first 31 bits of ucause and the MSB indicates that it is an interrupt when set 1, and an exception when unset 0.


• uscratch (Temporary register to be used freely in the user trap handler, CSR#64) is described below.

These CSRs can be set by using the CSR instructions. For example, to enable user-level interrupts in ustatus use "CSR Read/Write Immediate" instruction: csrrwi zero, 0, 0x1. Or use pseudo-instructions to read and write to the CSR registers. For example:

csrr    t0, 4     # read from CSR #4 to t0
csrw    t0, 6     # write from t0 to CSR #6
csrwi   0, 0x4    # write 0x4 to CSR #0

Saving Registers in the Interrupt Handler

When an interrupt or exception is raised, the program is paused and control is transferred to the interrupt handler. The utvec CSR holds the address of the interrupt handler that should be called when an interrupt or exception occurs. An interrupt handler is analogous to a normal function but there are some key differences. An interrupt can occur at any time, therefore the handler must guarantee that:

• All registers are restored to their original values after the handler finishes. Thus, the handler must save all registers that it uses (not just the s registers) and the handler must restore the original values to these registers before returning.
• The instruction uret must be used to leave the interrupt handler instead of the jalr or ret instructions that are used to return from a normal function.
• Functions exterior to the handler should not be called from within the handler.

To ensure that the program can safely resume execution after returning from the handler, the registers used by the handler must be saved upon entering the interrupt handler and restored before returning. The registers cannot be saved using the stack pointer because the stack pointer may be corrupted. Therefore, in common.s we have allocated memory labelled DATA_TRAP where the handler may save registers. In common.s the address of DATA_TRAP has been loaded into the uscratch register. The csrrw instruction can be used to swap the contents of uscratch and a register, then use the address from uscratch to save the registers that the handler will use.

The first and last instructions executed in the handler should be csrrw a0, 64, a0, where a0 is chosen by convention. Here is some sample code that saves two registers in the interrupt data trap:

handler:

# swap a0 and uscratch
csrrw   a0, 64, a0     # a0 <- Addr[DATA_TRAP], uscratch <- PROGRAMa0

# save all used registers except a0
sw      t0, 0(a0)         # save PROGRAMt0
sw      s0, 4(a0)         # save PROGRAMs0

...

# restore all used registers except a0
lw    t0, 0(a0)           # restore PROGRAMt0
lw    s0, 4(a0)           # restore PROGRAMs0

# restore a0
csrrw	a0, 64, a0        # a0 <- PROGRAMa0, uscratch <- Addr[DATA_TRAP]

uret                      # return from the interrupt handler using uret

Non-re-entrant handler: If you allocate a specific address to save a given register --- for example, register s0 is always saved in Addr[DATA_TRAP]+4 --- then the handler is not re-entrant. Interruptions cannot be enabled while handling an interruption, because doing so could cause the first saved value of s0 to be overwritten.

This lab will handle implementing a non-re-entrant handler. It is important to remember that interrupts are automatically disabled when control is transferred to the handler, and automatically re-enabled when returning from the handler, so the solution does not need to enable or disable interrupts in the handler.

The solution will still need to enable interrupts at the beginning of the program by setting the 0th bit of ustatus to 1 to enable user interrupts, and the 8th bit of uie to 1 to enable keyboard interrupts.

Handler Considerations

The solution cannot use reading or printing system calls (ecall) for this assignment. Instead, the program must use the MMIO and interrupts to interact with the keyboard and the display.

When executing a program in RARS using the custom handler, runtime errors won't be shown in RARS as usual. Instead, a provided section of the handler labelled handlerTerminate can be used to print the line where the error occurred, and the error code, before terminating the program. For example, the following exception happened at the instruction at address 0x00400f70 and was caused by a load access fault.

Error: Unhandled interrupt with exception code: 0x00000005
Originating from the instruction at address: 0x00400f70

Use the tables below to identify errors.

Make sure the handler does not call any functions. This is because the handler is not a function and hence it must restore every register that it uses, even the temporary t and a registers. On the other hand, functions are not required to preserve t and a registers, only the s registers.

Memory-Mapped I/O

Memory-mapped IO allows interaction with external devices through an interface pretending to be system memory. This mapping allows the processor to communicate with these devices using the load-word and store-word instructions.

Keyboard & Display

This lab uses the Keyboard and Display MMIO Simulator, available under the Tools menu in RARS, to interact with the simulator. The contents of the terminal are shown in the display section, and keys are typed in the keyboard section. Be sure to click Connect To Program after assembling the program and before running it. If you resize the window, click the Reset button to propagate the size change.

Generally, devices have two registers associated with them, a control, and a data register. The control register relays information about the device's state, and the data register relays data to or from a device. A description of the control and data registers for the keyboard and display can be found below.

A separate keyboard interrupt occurs for every key pressed when keyboard interrupts are enabled. Therefore, the user program receives input one character at a time.

Assignment

Gameplay Behaviour Details

The implementation details below are important because if the solution does not follow them, the game may function as expected but fail the unit tests that the lab uses to mark the functions. Strict adherence ensures that the solution meets both functional and assessment requirements.

Inputs

The solution receives keyboard user inputs through the PENDING_KEY global variable. The handler function is responsible for processing keyboard interrupts, and storing the pressed key in PENDING_KEY. When a key that does not correspond to a valid input is pressed, the key should be stored in PENDING_KEY and checkers should handle the key (do nothing) and reset PENDING_KEY to zero.

Inputs [a->h,1->8]

When inputting a move, the player must input the file then the rank of the desired square. When the rank is inputted, the program should ensure that the square is game square, if the square is a game square, print an x to the MMIO terminal to indicate the square is selected, and add the bitboard containing the square to the end of MOVES_ARRAY. If the square is not a game square, or if MOVES_ARRAY is full (128 bitboards), discard input, don't add to MOVES_ARRAY and wait for next input.

Inputs [q]

If at any point q is inputted, MOVES_ARRAY should be emptied, the game should be re-displayed to remove any x marks, and any partially inputted moves should be discarded.

Inputs [SPACE]

If at any point 'SPACE' is inputted, the game should discard any partially inputted moves, store a sentinel value at the end of MOVES_ARRAY, and doTurn should be called to process the moves in MOVES_ARRAY. MOVES_ARRAY should be reset after doTurn and the game state should be re-displayed. Depending on the outcome of doTurn:

• If the turn was successful (doTurn returned one), the game should be re-displayed with the new game state, the TURN global variable should be updated. As well as check if the turn won the game.

  • If the turn won the game, print the corresponding message for the winner from RED_WIN_MSG or BLACK_WIN_MSG global variables using printStr, starting at position (0,20), and then return from checkers.

  • If the turn did not win the game, the game should continue, and input should be accepted for the next turn.

• If the turn was unsuccessful (doTurn returned zero), the game should be re-displayed to get rid of x selected squares (the game state should be the same as before attempting the turn), the TURN global variable should remain the same. The game should continue, and input should be accepted for the same players next attempt at a valid turn.

King Promotions

When a piece reaches the opposite end of the board, it should be promoted to a King. The makeMove function will promote all pieces of the color of the current TURN (the same color that makeMove moves) that are on the opposite end of the board.

Primary Gameplay Loop

The primary gameplay loop in checkers should continue until a player wins the game. The loop should wait until a key is stored in PENDING_KEY by the handler, then the loop should process the key, update the game state as necessary and store zero back into PENDING_KEY to indicate that the program is ready to handle another key.

Data Structures

The solution uses several global variables to represent the game state, store moves, and pass input to the program. Additional variables are defined in common.s, these include the ASCII representation of all the characters used in the solution, the address of the MMIO registers used for interacting with the RARS MMIO terminal, and the masks for shifting bitboards. Looking at, and understanding the definitions of the variables at the top of common.s may be helpful for understanding how the solution works.

Additional global variables may be added as needed in the checkers.s file for the solution. The common.s file should not be modified.

Functions to Complete

The solution must implement the following functions:

• checkers
• displayGame
• genSlideMoves
• genJumpMoves
• makeMove
• doTurn
• handler

These functions are described in detail below.

When implementing these functions, to get full marks, remember to complete the register usage section in their header comments to describe the usage of the t and s registers in the function.

The solution must use the implemented functions, as well as the RED, BLACK, KINGS, TURN, MOVES_ARRAY, and PENDING_KEY global variables provided at the top of common.s. These global variables and data structures are described in detail in the data structures section.

Additionally, helper functions are provided that may be useful when producing the solution, these helper functions are detailed in the helper functions section.

checkers
  Entry point for checkers game, handles the main game logic.
    NOTE: The initial game state is not setup for you

  Arguments
    a0: Pointer to head of MOVES_ARRAY

  Returns
    N/A

displayGame
  This function displays the game state on the board in the RARS MMIO
    interface. The skeleton of the game board can be displayed using
    the 'displayBoard' helper function. This function only displays
    the game squares, and should NOT display the non-game squares.
      - 'b' for black man pieces
      - 'B' for black king pieces
      - 'r' for red man pieces
      - 'R' for red king pieces
      - '-' for empty game squares

    NOTE: Use the 'printChar' helper function to print characters
      to the MMIO interface

  Arguments
    N/A

  Returns
    N/A

genSlideMoves
  This function checks that the source bitboard contains only squares
    that are the color of the current player's turn. It then generates
    a bitboard of all the valid slide moves from the source squares.
    If any of the source squares are invalid, it returns a ZERO_BB.

    NOTE: This function works with multiple src squares, as long
           as they are all valid

  Arguments
    a0: Bitboard of source squares

  Returns
    a0: Bitboard of all valid slide moves from source squares

genJumpMoves
  This function checks that the source bitboard contains only squares
    that are the color of the current player's turn. It then generates a
    bitboard of all the valid jump moves from the source squares.
    If any of the source squares are invalid, it returns a ZERO_BB.

    NOTE: This function works with multiple src squares, as long
           as they are all valid

  Arguments
    a0: Bitboard of source squares

  Returns
    a0: Bitboard of all valid jump moves from source squares

doTurn
  Validates and executes every move in MOVES_ARRAY, if all the moves are
    valid, they should all be made, the global game state should be
    updated, and the function should return 1. If any of the moves are invalid,
    the game state should be restored to its state before the turn, and return 0.

    NOTE: Assumes MOVES_ARRAY is terminated with a sentinel value of (-1)

    NOTE: Remember that a player MUST make a jump move if
            possible, and MUST continue chaining jump moves together

  Arguments
    a0: Pointer to head of MOVES_ARRAY

  Returns
    a0: 1 if turn is successful, 0 if turn is unsuccessful

makeMove
  Updates the global bitboards with the move of the piece specified
    by a0, to the square specified by a1. This function performs no
    validation checks, it assumes that a0 -> a1 is a single valid
    move for the current player's turn, and that a0 and a1 only have
    a single set bit.

  Arguments
    a0: Bitboard with a single source square
    a1: Bitboard with a single destination square

  Returns
    N/A

handler
  The handler function is responsible for handling all interrupts and
    exceptions. This function should save and restore all registers that
    it uses, including t registers. The handler should
    not call functions exterior to the handler, and should return from
    the function using the uret instruction. If the handler is handling
    an exception or unexpected interrupt, it should jump to the
    'handlerTerminate' label, which will print the error code and the
    address of the instruction that raised the exception.

  Arguments
    N/A

  Returns
    N/A

Helper Functions

We have provided you with a set of helper functions that may be useful when implementing the solution. Do not modify these functions, they are used by the test cases to validate the solution.

The following helper functions are provided:

• displayBoard prints the game board skeleton to the RARS MMIO terminal
• bitsToIndex takes a bitboard with a single set bit and returns the index of that bit
• cordsToBits takes a row and column and returns a bitboard representing the square at the given coordinates
• printChar prints a single character to the RARS MMIO terminal
• printStr prints a null terminated string to the RARS MMIO terminal
• waitForDisplayReady executes a busy wait loop that checks if the RARS MMIO terminal is ready to print to

These functions are described in detail below.

If you would like to see how these helper functions are implemented, you can look at their definitions in common.s. Do not modify common.s.

displayBoard
  This function displays the empty game board in the RARS MMIO
    interface. This function should be called once at the start of
    the game to display the empty game board template.

  Arguments
    N/A

  Returns
    N/A

bitsToIndex
  Takes a bitboard with a single bit set and return the numerical
    index of the set bit.

  Arguments
    a0: Bitboard with a single set bit

  Returns
    a0: The index of the set bit

cordsToBits
  Takes a row and column index (NOT rank and file) as coordinates and
    returns the bitboard of the square that corresponds to the row and
    column. If the square specified by the row and column is not
    a game square, returns a ZERO_BB.

  Arguments
    a0: Index of the row (0-7)
    a1: Index of the column (0-7)

  Returns
    a0: Bitboard representing game square, or 0 for an invalid square

printChar
  Prints a single character to the Keyboard and Display MMIO Simulator
    terminal at the given coordinates.

  Arguments
    a0: The x coordinate of the point to print to
    a1: The y coordinate of the point to print to
    a2: The ASCII representation of the character to print

  Returns
    N/A

  Reference: This function is a modified version of a printChar
    function made by Zachary Selk, 2019

printStr
  Prints a null-terminated string to the Keyboard and Display MMIO
    Simulator terminal at the given coordinates

  Arguments
    a0: The x coordinate of the starting position to print the string
    a1: The y coordinate of the starting position to print the string
    a2: The address of the null-terminated string to print

  Returns
    N/A

  Reference: This function is a modified version of a printStr
    function made by Zachary Selk, 2019

waitForDisplayReady
  A method that will check if the Keyboard and Display MMIO Simulator
    terminal can be written to, busy-waiting until it can.

  Arguments
    N/A

  Returns
    N/A

Understanding printChar, printStr, and waitForDisplayReady

The MMIO display is not always ready to print a new character. Thus, whenever the printChar function is called, it must wait for the MMIO display to be ready before it can print. printChar calls the function waitForDisplayReady which executes a busy wait loop that checks the status of the Display Control Register. This register acts as a flag that signals if the display is ready. The address of this register is in the global variable DISPLAY_CONTROL provided to you. If the value in the Display Control Register is set to one, then the busy wait loop exits and the character/string can be printed to the MMIO display. Otherwise, the loop will continue periodically checking the register.

This flag/idle loop mechanism is necessary because the MMIO simulator temporarily clears the Display Control register while printing a character to the display and then re-enables it once printing is complete. The sequence followed during this process is as follows:

1. When data is written to the Display Data register, the simulator is notified.
2. The Display Control register is cleared by the simulator.
3. The character is read from the Display Data register.
4. The ASCII character is echoed to the display.
5. A delay is introduced to simulate the processing time required by an actual display unit.
6. Finally, the simulator re-enables the Display Control register.

printStr simply calls printChar in a loop until it reaches a null character.

Testing

Make sure to thouroughly test the solution to ensure that all the functions work as expected, and that the game plays as described in the instructions.

Bitboard Generation Tool

A python tool bb-generator.py is provided to assist with producing gamestate bitboards for manual testing. This tool can be found in the Code/bb-generatory-tool/ directory. Instructions on how to use this tool can be found upon startup of the tool. To run the tool, you will need to have python installed on your computer, and run the command python3 bb-generator.py in a terminal in the Code/bb-generatory-tool/ directory.

Check My Lab

This lab is supported in CheckMyLab. To get started, navigate to the Checkers lab in CheckMyLab found in the dashboard. From there, students can upload test cases in the 'My test cases table'. Test cases are text files which follow the format described below. Additionally, students can upload their checkers.s file in the My solutions table, which will then be tested against all other valid test cases.

The format of the {test}.txt file is as follows: (test number) (arguments)

The test number is an integer number 1-4 representing the function to be tested.

1. genSlideMoves
2. genJumpMoves
3. makeMove
4. doTurn

The arguments are specific to the test being preformed, they must be in the order described, separated by a space. Bitboard arguments and outputs (BLACK, RED, KINGS, SRC, DEST, and moves bitboards) are always in the form 0x1234ABCD. Non-bitboard arguments and outputs such as TURN and output of doTurn are either 0 or 1. The arguments and their order for each of the testable functions is described below.

1. genSlideMoves
   1. BLACK bitboard
   2. RED bitboard
   3. KINGS bitboard
   4. TURN (0 or 1)
   5. SRC bitboard


2. genJumpMoves
   1. BLACK bitboard
   2. RED bitboard
   3. KINGS bitboard
   4. TURN (0 or 1)
   5. SRC bitboard


3. makeMove
   1. SRC bitboard
   2. DEST bitboard
   3. BLACK bitboard
   4. RED bitboard
   5. KINGS bitboard
   6. TURN (0 or 1)


4. doTurn
   1. BLACK bitboard
   2. RED bitboard
   3. KINGS bitboard
   4. TURN (0 or 1)
   5. Move bitboards separated by spaces. Make sure that the last moves bitboard is the sentinel value 0xFFFFFFFF to properly mark the end of MOVES_ARRAY.

CheckMyLab only checks that the test number is valid, and that there is the correct number of arguments for the test. This means that uploaded test cases may result in undefined behavior if not properly constructed, for example since makeMove is only ever called by the solution with a valid move, if the arguments for testing makeMove do not describe a valid move, different implementations of makeMove may have different results causing the test to fail, even though both makeMove implementations function correctly.

Assumptions, Notes, and Hints

• Prolonged use of the MMIO simulator and the timer tool in RARS can cause them to slow down over time --- this is likely a performance bug in the implementation of RARS. The MMIO simulator may respond slowly to inputs. Restarting RARS should fix these issues.
• Before connecting the MMIO terminal to the program, make sure to resize the MMIO terminal window to at least 40x22 and press reset, this ensures there is space for the full board and the win message to be properly displayed.
• Global variables can be loaded in a single instruction: lw t0, LABEL, as opposed to doing la t0, LABEL and lw t1, 0(t0)

Resources

• Slides used for the lab presentation: (.pdf)
• Marksheet used to mark the lab (.txt)

Marking Guide

Assignments too short to be adequately judged for code quality will be given a zero for that portion of the evaluation.

• 5% for correctly implementing genSlideMoves
• 5% for correctly implementing genJumpMoves
• 10% for correctly implementing makeMove
• 20% for correctly implementing doTurn
• 40% for proper gameplay behaviour
• 20% for code cleanliness, readability, and comments

Submission

There is a single file to be submitted for this lab (checkers.s) and it should contain the implementation of the solution functions.

• Do not add a main label to this file.
• Do not modify the function names.
• Do not remove the CMPUT 229 Student Submission License at the top of the file containing your solution and remember include your name in the appropriate section of this text.
• Do not modify the line .include "common.s".
• Do not modify the common.s file.
• Keep the files in the Code folder of the git repository.
• Push your repository to GitHub before the deadline. Just committing will not upload your code. Check online to ensure your solution is submitted.