Извините. Застрял на двойном обращении к памяти в двух последовательных инструкциях и решил немного отдохнуть перед правкой. До сих пор отдыхаю. Займусь фиксом на новогодних праздниках.
Пока лишь могу показать исходный код задачи N-ферзей. К сожалению до исправления ошибки в схематике он не рабочий. Можно было бы чуть изменить этот код (вставить NOP), чтобы обойти ошибку, но этот вариант мне не понравился.
;; N-queens solver
; ------ Register name conversion -------
assign r0 sol_num ;
assign r1 ind ;
assign r2 bit_mask ;
assign r3 I ;
assign r4 J ;
assign r5 next_row_ptr ;
assign r6 row_ptr ;
assign r7 cell_ptr ;
assign r8 local_array_dat ;
assign r9 local_array_ptr ;
assign r10 array_ptr ;
assign r13 tmp_reg ;
assign r15 return_address ;
; ------ Constant --------------
;$board_size equ 3
; Programm entry point
function main
push return_address ;
lea r1, $into_str ;
call _puts
load r10, 8
load r12, 1
main_loop:
push r10
call solver
pop r10
inc r12
dec r10
jnz main_loop
pop return_address ;
return ;
end
function solver
push return_address ;
lea r1, $header_str ;
call _puts
mov r0, r12 ; $board_size ;
call _print_dec
; jmp skip
; clear board
load sol_num, 0x0 ;
lea array_ptr, $array ;
load ind, 8
a_loop:
mov (array_ptr), sol_num
inc array_ptr, 4
dec ind
jnz a_loop
load sol_num, 0x0 ;
lea array_ptr, $board_line_0 ;
load ind, 72
clear_loop: ;
mov (array_ptr), sol_num
inc array_ptr, 4
dec ind
jnz clear_loop
skip:
lea array_ptr, $array ;
load sol_num, 0x0 ;
load ind, 0x0 ;
call dfs ; N-queen solver
push r0
lea r1, $body_str ;
call _puts
pop r0 ;
call _print_dec
call _newline
pop return_address ;
return ;
end
$into_str db 'N-queen solver',0xd,0xa,0
$header_str db 'N = ',0
$body_str db ' Result = ',0
; Define static array
$array dq 0,0,0,0,0,0,0,0
; Define board memory in some simple way
$board_line_0 dq 0,0,0,0,0,0,0,0
$board_line_1 dq 0,0,0,0,0,0,0,0
$board_line_2 dq 0,0,0,0,0,0,0,0
$board_line_3 dq 0,0,0,0,0,0,0,0
$board_line_4 dq 0,0,0,0,0,0,0,0
$board_line_5 dq 0,0,0,0,0,0,0,0
$board_line_6 dq 0,0,0,0,0,0,0,0
$board_line_7 dq 0,0,0,0,0,0,0,0
$board_line_8 dq 0,0,0,0,0,0,0,0
;$sol_num dq 0
; --- Store ro local function space ------------------------
$var_row_ptr equ 0 ; Source pointer holder
$var_r1 equ 1 ; Store R1
$var_r2 equ 2 ; Store R2
$var_r3 equ 3 ; Store R3
$line_size equ 32 ; 8 cells x 4 bytes
$line_words equ 8 ; 8 cells
assign r6 src
assign r1 dst
assign r2 counter
assign r3 value
; ------ Move array rows ------
; Imput:
; R0 - pointer to source line
function shift_array
dec r14, 16
mov r14.var_row_ptr, src
mov r14.var_r1, dst
mov r14.var_r2, counter
mov r14.var_r3, value
load dst, $line_size
addc dst, src
load counter, $line_words
shift_array_loop:
mov value, (src)
mov (dst), value
inc src, 4
inc dst, 4
dec counter
jne shift_array_loop
mov value, r14.var_r3
mov counter, r14.var_r2
mov dst, r14.var_r1
mov src, r14.var_row_ptr
inc r14, 16
return
end
; ------ N-queen solver ------
; Imput:
; R0 - must be zero
; R1 - index argument
; Output:
; R0 - number of solutions
function dfs
cmp ind, r12 ; $board_size
jc start_loop
inc sol_num
return
start_loop:
push return_address
lea local_array_ptr, $array
shl ind, 2
addc local_array_ptr, ind
shr ind, 2
mov (local_array_ptr), 0x0
dfs_main_loop:
mov local_array_dat, (local_array_ptr)
cmp local_array_dat, r12 ;$board_size
jc do_main_loop
pop return_address
return
do_main_loop:
mov row_ptr, ind
shl row_ptr, 5 ; this is 8 elements of 32bit
lea tmp_reg, $board_line_0
addc row_ptr, tmp_reg
mov cell_ptr, ind
shl cell_ptr, 2
addc cell_ptr, row_ptr
load bit_mask, 1
shl bit_mask, local_array_dat
and bit_mask, (cell_ptr)
jnz next_iteration
;debug
push r8
push r11
lea r8, $array
lea r11, $board_line_0
call show_queens
pop r11
pop r8
; debug
debug
call shift_array
; debug
enable
push r8
push r11
lea r8, $array
lea r11, $board_line_0
call show_queens
pop r11
pop r8
done
; debug
mov next_row_ptr, row_ptr
load tmp_reg, 32 ; $row_size
addc next_row_ptr, tmp_reg
mov I, ind
mov J, local_array_dat
first_internal_loop:
mov tmp_reg, r12 ; $board_size
cmp I, tmp_reg
jnc finish_internal_loop
cmp J, tmp_reg
jnc finish_internal_loop
load bit_mask, 1
shl bit_mask, J
mov cell_ptr, I
shl cell_ptr, 2
addc cell_ptr, next_row_ptr
or (cell_ptr), bit_mask
inc I
inc J
jmp first_internal_loop
finish_internal_loop:
mov I, ind
mov J, local_array_dat
second_internal_loop:
cmp I, r12 ; $board_size
jz finish_second_loop
; load tmp_reg, 0
; cmp tmp_reg, J
; jl finish_second_loop
load tmp_reg, 0x80000000
and tmp_reg, J
jnz finish_second_loop
load bit_mask, 1
shl bit_mask, J
mov cell_ptr, I
shl cell_ptr, 2
addc cell_ptr, next_row_ptr
or (cell_ptr), bit_mask
inc I
dec J
jmp second_internal_loop
finish_second_loop:
mov I, ind
shl I, 2
addc I, next_row_ptr
mov (I), 0x0000ffff
mov I, ind
third_internal_loop:
cmp I, r12 ; $board_size
jnc finish_thord_loop
load bit_mask, 1
shl bit_mask, local_array_dat
mov cell_ptr, I
shl cell_ptr, 2
addc cell_ptr, next_row_ptr
or (cell_ptr), bit_mask
inc I
jmp third_internal_loop
finish_thord_loop:
push local_array_dat
push local_array_ptr
push ind
inc ind
call dfs
pop ind
pop local_array_ptr
pop local_array_dat
next_iteration:
inc local_array_dat
mov (local_array_ptr), local_array_dat
jmp dfs_main_loop
end
include ../lib/tty.asm
include ../lib/print_dec.asm
include ../lib/div.asm
include show_queens.asm
