6queens/queens.asm

;
; queens app — by.avolver'11
; distributed under BEERWARE LICENSE
; 
; @todo   
;  - Реализовать многопоточность...
;    Fork работает, однако общее адресное пространство вносит долю хаоса в картину.
;    Для начала нужно решить проблему выделения памяти и давать каждому потоку свой массив.
;    Затем сохранить в регистре каждого потока адрес на его массив и параметры. Вероятно это будет r15. Счётчик же положить в память каждого потока.
;  - Динамеческое выделение памяти. sys_brk не хочет работать. (или -1 в rcx ничего не значит?) 
;    Файл: /usr/src/linux/arch/x86/kernel/entry_64.S, строка: 422
;  - Использовать нулевую ячейку массива ферзей, дабы немного сократить количество инструкций.
;  - Сделать проверку на разрешённый диапазон N [5..256] и введённые в параметры буквы. 
;  - Вывод в JSON
;  - Добавить функцию DumpDesk
;  - Вывод времени работы в мс.
;  - Порт под Windows. Используем команды препроцессора: IS_LINUX = 1; if IS_LINUX ... end if
;  - Отобразить примерное время завершения.

format    ELF64     executable at 0000000100000000h

segment   readable  executable
appStart:
          entry     $
          pop       rax                           ; В стеке лежат параметры командной строки. По восемь байт на адрес параметра. Первый — количество;
          cmp       rax, 1
          jbe       fShowUsage
          pop       rax                           ; Второй — название программы;
          pop       rsi                           ; Третий — первый аргумент;
          call      toDec
          cmp       rax, 0
          je        fShowUsage
          mov       [iTotalLayers], rax
          mov       r9, rax
          mov       rbx, rax
          mov       rax, 8
          mul       rbx       
         ;mov       rcx, rax
         ;mov       rax, 12                       ; Запрос на расширение памяти. Syscall 12 — sys_brk. В rdi — адрес на желаемую границу сегмента данных.
         ;xor       ebx, ebx
         ;syscall
         ;add       rax, rcx
         ;mov       rdi, rax
         ;xor       rdi, rdi
         ;syscall
         
          mov       r8, 1                         ; Текущий уровень
          mov       r15, 0                        ; Счётчик совпадений
         
mainLoop:
          lea       rsi, [aQueens]
          mov       rbx, r8
          mov       rax, 8
          mul       rbx
          add       rsi, rax
          mov       rax, [rsi]                    ; Получаем значение ферзя для текущего уровня
          cmp       rax, r9
          jbe       DoCheckPaths                  ; Если это значение больше максимального уровня
          lea       rsi, [aQueens]
          add       rsi, 8
          mov       rax, [rsi]
          mov       rbx, r9
          inc       rbx
          cmp       rax, rbx
          jne       DoCont                        ; и если позиция ферзя первого уровня не вылезла за грани максимального положения
          jmp       DoCheckPaths
DoCont:
          lea       rsi, [aQueens]
          mov       rbx, r8
          mov       rax, 8
          mul       rbx
          add       rsi, rax
          mov       rax, 1
          mov       [rsi], rax                    ; aQueens[iLevel] = 1 : Сбрасываем позицию текущего уровня в начальное положение
          dec       r8                            ; iLevel-- : Переходим на уровень ниже.
          sub       rsi, 8
          mov       rax, [rsi]
          inc       rax
          mov       [rsi], rax                    ; aQueens[iLevel]++ : На предыдущем уровне сдвигаемся направо 
          jmp       mainLoop
DoCheckPaths:
          call      CheckPaths
          cmp       rdx, 1                        ; Проверяем, свободны ли поля.
          je        IncLevel
          inc       r8
          cmp       r8, r9
          jbe       mainLoop
          lea       rsi, [aQueens]                ; Может это конец?
          add       rsi, 8
          mov       rax, [rsi]
          cmp       rax, r9
          ja        breakLoop                     ; Да? Брякаем цикл.
          inc       r15                           ; iCount++ : Ура, мы нашли решение!
          call      fDumpSolution                 ; Выводим решение
          dec       r8                            ; iLevel--
          lea       rsi, [aQueens]
          mov       rbx, r8
          mov       rax, 8
          mul       rbx
          add       rsi, rax
          mov       rax, [rsi]
          inc       rax
          mov       [rsi], rax                    ; aQueens[iLevel]++;
          jmp       mainLoop
IncLevel:
          lea       rsi, [aQueens]
          mov       rbx, r8
          mov       rax, 8
          mul       rbx
          add       rsi, rax
          mov       rax, [rsi]
          inc       rax
          mov       [rsi], rax
          jmp       mainLoop
breakLoop:
          lea       rsi, [sStatisticArea]
          mov       rax, r15
          call      fromDec
          mov       rdx, sStatisticArea - sStatistics
          add       rdx, rbx
          add       rsi, rbx
          mov       rcx, 0x0A
          mov       [rsi], rcx
          inc       rdx
          lea       rsi, [sStatistics]
          mov       edi, 1	
          mov       eax, 1	
          syscall
          
          xor       rax, rax
          xor       edi, edi                      ; Выходим из себя. Syscall 60 — sys_exit
          mov       eax, 60
          syscall
          
; Функция для проверки свободных путей.
; Возвращает: rdx = 1, если на пути встречается ферзь; либо rdx = 0, если дорога пуста.
; r10 — iTargetLayer; r11 — iVectorCenter; r12 — iVectorLeft; r13 — iVectorRight; r14 — iEnemyX
CheckPaths:
          cmp       r8, 1
          jne       ChPathsP1
          mov       rdx, 0
          ret
ChPathsP1:
          mov       r10, r8                       ; iTargetLayer = iLevel
          lea       rsi, [aQueens]
          mov       rbx, r8
          mov       rax, 8
          mul       rbx
          add       rsi, rax                      
          mov       r11, [rsi]                    ; iVectorCenter, iVectorLeft, iVectorRight = aQueens[iLevel]
          mov       r12, r11
          mov       r13, r11
ChPathsLoop:
          dec       r10
          cmp       r10, 0
          mov       rdx, 0
          jbe       ChPathsEnd
          lea       rsi, [aQueens]
          mov       rbx, r10
          mov       rax, 8
          mul       rbx
          add       rsi, rax
          mov       r14, [rsi]                    ; iEnemyX = aQueens[iTargetLevel]
          cmp       r11, r14                      ; Если iVectorCenter = iEnemyX, то сохраняем в rdx:1 и вываливаемся.
          jne       ChPathNoCenter
          mov       rdx, 1
          ret
ChPathNoCenter:
          cmp       r12, 0
          jbe       ChPathNoLeft
          dec       r12                           ; Уменьшаем iVectorLeft
          cmp       r12, r14                      ; Если iVectorLeft = iEnemyX, то сохраняем в rdx:1 и возвращаемся.
          jne       ChPathNoLeft
          mov       rdx, 1
          ret
ChPathNoLeft:
          cmp       r13, r9
          ja        ChPathsLoop
          inc       r13                           ; Увеличиваем iVectorRight
          cmp       r13, r14                      ; Если iVectorRight = iEnemyX, то сохраняем в rdx:1 и выпадаем.
          jne       ChPathsLoop
          mov       rdx, 1
          ret
ChPathsEnd:
          ret

; Функция вывода решения.
fDumpSolution:
          mov       r11, 1
          mov       r12, 1
          lea       rdx, [aQueens]
          lea       rsi, [tBackBuffer]
          mov       rax, r15
          call      fromDec
          add       rsi, rbx
          add       r12, rbx
          mov       rax, 0x03A
          mov       [rsi], rax
          inc       rsi
          inc       r12
          mov       rax, 0x020
          mov       [rsi], rax
          inc       rsi
          inc       r12
          mov       rcx, r9
fDSLoop:
          mov       rax, r11
          call      fromDec
          add       rsi, rbx
          add       r12, rbx
          mov       rax, 0x03A
          mov       [rsi], rax
          inc       rsi
          inc       r12
          add       rdx, 8
          mov       rax, [rdx]
          call      fromDec
          inc       r11
          add       rsi, rbx
          add       r12, rbx
          mov       rax, 0x02C
          mov       [rsi], rax
          inc       rsi
          inc       r12
          mov       rax, 0x020
          mov       [rsi], rax
          inc       rsi
          inc       r12
          loop      fDSLoop
          dec       rsi
          dec       rsi
          dec       r12
          dec       r12
          mov       rdx, 0x0A
          mov       [rsi], rdx
          mov       rdx, r12
          lea       rsi, [tBackBuffer]
          mov       edi, 1
          mov       eax, 1
          syscall
          ret

; Отображение сообщения об использовании.
fShowUsage:
          mov       edx, iUsageSize
          lea       rsi, [sUsage]
          mov       edi, 1
          mov       eax, 1                        ; Выводим сообщение об использовании. Syscall 1 — sys_write: rsi — адрес на строку, edx — длинна, edi — stdout.
          syscall
          xor       edi, edi                      ; Выходим из программы. Syscall 60 — sys_exit: edi — код возврата.
          mov       eax, 60
          syscall
          
fAllocationError:
          mov       edx, iAllProSize
          lea       rsi, [sAllocationProblem]
          mov       edi, 1
          mov       eax, 1
          syscall
          xor       edi, edi
          mov       eax, 60
          syscall

; Функция для перевода ASCII строки в число.
; rsi - адрес на строку
; rax - число результата
; Смотрим первую букву, если она — цифра — прибавляем её к rax. Если следующий байт не 0x0 — умножаем rax на десять и прибавляем следующую цифру.
toDec:
          xor       rax, rax 
          mov       cl, [rsi]
toDecEnt:
          sub       cl, 48
          jc        toDecInc
          cmp       cl, 10
          jae       toDecInc
          add       rax, rcx
toDecInc:
          inc       rsi
          mov       cl, [rsi]
          cmp       cl, 0
          je        toDecEnd
          mov       rbx, 10
          mul       rbx
          jmp       toDecEnt
toDecEnd:
          ret

; Функция для обратного перевода числа в ASCII строку.
; rsi - адрес на временную строку
; rax - число, которое необходимо преобразовать
; rbx - длина строки
; Делим исходное число на десять — остаток записываем в ASCII-цифру.
; Если исходное число становится меньше десяти, то добавляем его как ASCII-последнюю цифру в поток.
fromDec:
          push      rcx
          push      rdx
          push      rdi
          xor       rdi, rdi
          mov       rcx, 10
          push      rsi
          push      rsi
          lea       rsi, [sFromDecTemp]
          add       rsi, 10
fromDecEnt:
          inc       rdi
          cmp       rax, 10             ; Если rax < 10, то прыгнуть в конец
          jb        fromDecEnd
          xor       rdx, rdx            ; Очищаем регистр для частного
          div       rcx                 ; rcx = rax / rcx => rdx
          or        dl, 0x30
          mov       [rsi], dl
          dec       rsi
          jmp       fromDecEnt
fromDecEnd:
          or        al, 0x30
          mov       [rsi], al
          mov       rbx, rdi            ; Копируем строку на первый байт необходимого адреса.
          mov       rcx, rdi
          pop       rdi
          cld
          rep movsb 
          inc       rdi
          mov       ah, 0               ; Добавляя в конец нулевой стоп-символ
          mov       [rdi], ah
          pop       rsi
          pop       rdi
          pop       rdx
          pop       rcx
          ret
          
appEnd:

segment readable writeable
dataStart:

iTotalLayers        dq        ?
sTempPlaceForInt    db        11 dup('b')
sFromDecTemp        db        11 dup('a')

sUsage              db        'Queens application', 0x0A
                    db        'Finds a solution for the "eight queens puzzle"', 0x0A, 0x0A
                    db        'Usage: queens <depth level>', 0x0A
iUsageSize          = $ - sUsage

sStatistics         db        'Number of solutions: '
sStatisticArea      db        11 dup(0)

sAllocationProblem  db        'Memory allocation error, sorry...', 0x0A
iAllProSize         = $ - sAllocationProblem

aQueens:
times 256           dq        1         ; Массив, собственно, ферзей

tBackBuffer:
times 3             db        ?         ; Дельта размера, дабы забить остатки бинарника до 4096 байт.
times (4096 - (appEnd - appStart) - (tBackBuffer - dataStart) - 176) / 8 db '6dreams '   ; Great_&_be-e-e-eg backbuffer. (%