Setting up Sudoku Board

Question

Basically, using ARM assembly code, I'm suppose to load a text file that has the board pattern. Here is what the text file looks like:

704006390
000701500
000090027
002610053
400207008
610039400
930060000
006308000
048900206

(The zeros are blank spaces in a real sudoku puzzle). I have no problem loading the text file. I'm already given the C code on how to check row and columns.

For example, this is to check if the row is okay in C but I have to translate it to arm.

int rowOK(int board[9][9], int row) {
  int index;
  int count[10];

  for (index=0; index<10; index++)
    count[index] = 0;

  for (index=0; index<9; index++)
    count[board[row][index]]++;

  for (index=1; index<10; index++)
    if (count[index] > 1)
      return 0;

  return 1;
}

What I really need help on is on how to approach this. In the ARM language, how do I set up the board so I can start checking and testing? How do I store these numbers from the text file onto memory? Should the numbers be in string format or integers?

int board[9][9]

This code looks like some sort of array. I'm guessing I'm suppose to make an array, but how do I do this in ARM? Any suggestions are appreciated.

Answer 1

The text file is in ascii format. The following program will read the text file into memory, put each byte in different register for one row. It can be printed in character format. To change ascii to integer the 'Linux atoi' can do that. The first printed line is from a variable in the program. The second line is from the file red in, indexed to the last line.

/* sudoku.s */

@ sudoku.file
@ 704006390
@ 000701500
@ 000090027
@ 002610053
@ 400207008
@ 610039400
@ 930060000
@ 006308000
@ 048900206

@ ------------------

.data

@ See /usr/include/arm-linux-gnueabihf/asm/unistd.h
@ See /usr/include/arm-linux-gnueabihf/bits/fcntl-linux.h

    .equ create,     8
         .equ Mode, 0644       @ -rw-r--r--
    .equ open,       5
         .equ Rd,   00
         .equ Wr,   01
         .equ RdWr, 02
         .equ Apnd, 02000
    .equ read,       3
    .equ write,      4
    .equ close,      6
    .equ sync,       36
    .equ exit,       1
    .equ sfile,      187

.balign 4
dir_file:
    .asciz "sudoku.file"

.balign 4
Open:
    .word dir_file, Rd, open

.balign 4
Read:
    .word Buf, 91, read

.balign 4
Buf:
    .space 100

.balign 4
Row1:
    .asciz "704006390"

.balign 4
Row2:
    .asciz "000701500"

.balign 4
format:
    .asciz "  | %c  %c  %c | %c  %c  %c | %c  %c  %c |   (num %d )\n"

.balign 4
dec_num:
    .word 0

@ ------------------

.text

.global main

@ -- Subroutine -- Load registers to print --

Load_row:
    ldrb  r1,  [r0], #1
    ldrb  r2,  [r0], #1
    ldrb  r3,  [r0], #1
    ldrb  r4,  [r0], #1
    ldrb  r5,  [r0], #1
    ldrb  r6,  [r0], #1
    ldrb  r7,  [r0], #1
    ldrb  r8,  [r0], #1
    ldrb  r9,  [r0], #1
    @ ldr   r0,  =dec_num    @ The numbers are
    @ str   r1,  [r0]        @   in ascii format. 
    @ push  {r1-r9, lr}      @   This part 
    @ bl    atoi             @   converts ascii
    @ pop   {r1-r9, lr}      @   to integer.
    mov   r10, r0            @ ---- OR ----
    sub   r10, r1, #0x30     @ Under 10, sub hex 30
    mov   pc,  lr

@ -- Subroutine -- Print to stdout --

Prt:
    push  {r0, lr}
    push  {r4-r10}         @ The printf prints
    ldr   r0,  =format     @   r1-r3 and the
    bl    printf           @   rest from
    pop   {r4-r10}         @   the stack.
    pop   {r0, pc}

@ -- Subroutine -- Open, Read file into memory --

Rd_file:
    push  {r0-r12, lr}
    ldr   r3,  =Open
    ldm   r3,  {r0, r1, r7}
    svc   #0
    mov   r4,  r0

    ldr   r3,  =Read
    ldm   r3,  {r1, r2, r7}
    svc   #0

    mov   r0,  r4
    ldr   r7,  =close
    svc   #0
    pop   {r0-r12, lr}
    mov   pc, lr

@ ---- The main program starts here ----

main:

    push  {r4-r10, lr}

@ ---- This is when each row is declared
@      in the .data section ----

    ldr   r0,  =Row1
    bl    Load_row
    bl    Prt

@ ---- This is when reading the file ----

    bl    Rd_file
    ldr   r0,  =Buf
    add   r0,  #80    @ last row
    bl    Load_row
    bl    Prt

End:
    pop   {r4-r10, lr}
    mov   r0,  #0
    bx    lr

.end

Output:

./sudoku; echo $?
  | 7  0  4 | 0  0  6 | 3  9  0 |   (num 7 )
  | 0  4  8 | 9  0  0 | 2  0  6 |   (num 0 )
0

Answer 2

ARM has nothing to do with it. Either you understand how something like that is arranged in memory or you dont. Once you know how it is arranged then the assembly language is easy.

Looks like your C code is fed an two dimentional array of ints so 32 bits per item. 81 words.

Think about a string

char s[]="hello world";

when you step through items in that string

for(i=0;s[i];s++)

you are generating addresses the base address of the string s, and the an offset which is the index number times the size of each item. So the "e" in hello is at index 1, so base address of s + (offset*size) = s_base + (1*1). and you simply do a byte based load or store at that address (ldrb/strb).

For an array of ints, 32 bits per (one word per) 9x9 is 81 words. like the string the last array value moves by one item at a time [a][b]. incrementing b moves you one word at a time (4 bytes) incrementing a moves you the number of the last allocation times the size of each so int board[d][c] where d and c are numbers each increment of d in C, means c*4 bytes of offset.

basically for your board, using variables board[a][b] board_base_address + (a*(9*4)) + (b*4)

4 being a power of two it gets a little easier board_base_address + ((a*9)<<4) + (b<<2)

9 = 8+1  so a*9 = a*(8+1), distribute = (a*8) + (a*1) = (a<<3) + a

so board_base_address + (a<<7) + (a<<4) + (b<<2) unless I made a typo/mistake somewhere and that is only if you need to calculate random access to the board, for a loop like the one you have you dont need to do that.

implementing the ldr or str is trivial once you have computed the address. If you are comfortable with C you can simply take that C code and continue to break it into smaller parts, get rid of the two dimensional array and make it a single board[81], you are dealing with word addresses not byte so the asm has to add a times 4. (or do the whole thing in bytes if you are allowed, you only need to count to 9).

Hopefully you will see that the problem is the same no matter what architecture, x86, arm, mips, etc. The trick is computing the addresses, the computing of addresses is trivial you just look up the instruction for adding or anding or shifting, etc. And the load and stores are trivial you just look up the instruction for a simple load or store.

basically before you even use the words assembly language do something like this in head or actually implement it

int rowOK(int board[81], int row) {
  int index;
  int count[10];
  int boffset;
  int offset;
  int value;
  int temp;

  index=0;
  do
  {
    count[index]=0;
    index++;
  }
  while(index<10}

  offset = row * 9;
  index=0;
  do
  {
      value=board[offset];
      temp=count[value];
      temp++;
      count[value]=temp;
      offset++;
      index++;
  }
  while(index<9)

  index=1l
  do
  {
      temp=count[index];
      if(temp>1) return(0);
  }
  while(index<10)

  return 1;
}

any and all bugs and typos are intentional...

then it is much easier to just bang out the assembly language directly. Programming has at least two problems to solve, one is the algorithm, two is implementing it. In this case in C but you could use java or pascal or python or whatever and then do the asm as the last step which ever asm you want or need. just keep breaking the problem into smaller individual steps until they resemble things that can be done in one or a few simple instructions.

Of course there is this thing called a compiler you can simply compile the C and the output is assembly language...(much easier to read IMO if you compile to an object then disassemble)...

arm-none-eabi-gcc -O2 -c myfun.c -o myfun.o
arm-none-eabi-objdump -D myfun.o

00000000 <rowOK>:
   0:   27bdffd8    addiu   sp,sp,-40
   4:   03a01021    move    v0,sp
   8:   27a60028    addiu   a2,sp,40
   c:   ac400000    sw  zero,0(v0)
  10:   24420004    addiu   v0,v0,4
  14:   1446fffd    bne v0,a2,c <rowOK+0xc>
  18:   00000000    nop
  1c:   00051080    sll v0,a1,0x2
  20:   00052940    sll a1,a1,0x5
  24:   00452821    addu    a1,v0,a1
  28:   00852021    addu    a0,a0,a1
  2c:   24850024    addiu   a1,a0,36
  30:   8c820000    lw  v0,0(a0)
  34:   24840004    addiu   a0,a0,4
  38:   00021080    sll v0,v0,0x2
  3c:   03a21021    addu    v0,sp,v0
  40:   8c430000    lw  v1,0(v0)
  44:   00000000    nop
  48:   24630001    addiu   v1,v1,1
  4c:   1485fff8    bne a0,a1,30 <rowOK+0x30>
  50:   ac430000    sw  v1,0(v0)
  54:   27a20004    addiu   v0,sp,4
  58:   8c430000    lw  v1,0(v0)
  5c:   00000000    nop
  60:   28630002    slti    v1,v1,2
  64:   10600006    beqz    v1,80 <rowOK+0x80>
  68:   24420004    addiu   v0,v0,4
  6c:   1446fffa    bne v0,a2,58 <rowOK+0x58>
  70:   00000000    nop
  74:   24020001    li  v0,1
  78:   03e00008    jr  ra
  7c:   27bd0028    addiu   sp,sp,40
  80:   00001021    move    v0,zero
  84:   03e00008    jr  ra
  88:   27bd0028    addiu   sp,sp,40

Of course I am not going to give you arm assembly, this is mips...and of course you shouldnt turn in compiler output as your assignment, but it should give you a feel for the instructions you should be looking up in the arm documentation and a feel of how to use them. The compiler is optimizing in this case dont use optimization for at least part of the program to resemble something you should be writing, probably with less stack interaction than unoptimized code is going to generate.

You didnt define if you needed to link this with C or just write some untested code, etc.