1

I'm interested in this block of code, from https://github.com/delucas/sudoku-project/blob/master/sudoku-assembler-mips/sudokiller.s#L158

# 3x3-Box check
div     $t0, $a1, 3           # $t0 = row / 3
mul     $t0, $t0, 27          # Offset of the row  ->>> Where does the 27 come from?
div     $t1, $a2, 3           # $t1 = col / 3
mul     $t1, $t1, 3           # Offset of the column
add     $t1, $t0, $t1         # Offset of the first cell in the box

I'm trying to understand what we're doing here, but I'm confused on what the significance of the number 27 is.

Talen Kylon
  • 1,908
  • 7
  • 32
  • 60
  • You can divide by 3 [with a multiply and a right-shift](http://stackoverflow.com/a/171369/224132). That will faster than `div` on most machines. – Peter Cordes Dec 01 '15 at 07:40
  • @PeterCordes At the expense of some readability, of course – qwr Dec 01 '15 at 07:52
  • @qwr: you should be able to wrap it into an assembler macro, for readability. Besides, that's what comments are for in asm. – Peter Cordes Dec 01 '15 at 07:54

1 Answers1

2

The board is a two-dimensional array, so for example board[2][2] gets translated to board[2*9+2]. The code for row is equivalent to (t0/3)*27 which aligns the row number to (the first number of) its box and then effectively multiplies by 9, indexing the row properly.

qwr
  • 9,525
  • 5
  • 58
  • 102
  • How would this differ if we were checking a box of size 3x2 (2 rows, 3 cols). For a 6x6 board. – Talen Kylon Dec 01 '15 at 03:39
  • @TalenKylon Well first, assuming it's numbered row by row, you align to the corner of the box (there are 2 boxes) and then multiply to get the board size `(t0/2)*12` – qwr Dec 01 '15 at 03:44