## Josephus Problem

```;name: josephusproblem.asm
;
;description: In computer science and mathematics, the Josephus problem
;             (or Josephus permutation) is a theoretical problem related
;             to a certain counting-out game.
;             This program is a (not 'the') solution to this problem.
;             because I program on 64 bits, I've decided to extend the existing
;             examples to 64 bits. (In case someone wants to know where to stand when
;             the entire world population is counted-out this way).
;             It makes use ot rotate-n-bits-left for small numbers in large registers
;             to skip the leading zeros, since they don't matter in for the value.
;             Just because the skipping of leading zeros, I use number of leading zeros
;             routine from Hacker's Delight to count the leading zeros.
;source:      https://en.wikipedia.org/wiki/Josephus_problem
;             book: Hackers's Delight

bits 64

%include "josephusproblem.inc"

global _start

section .bss
buffer:     resb    20
.end:
.length:	equ     \$-buffer

section .data
msgusage:	db	"use josephusproblem x , x=unsigned integer (max.10 digits)",10
.length:	equ	\$-msgusage
output:	db	"last man standing is on position: "
.length:	equ	\$-output

section .text

_start:
pop	    rdi					    ;argc
cmp     rdi,2
jne	    usage
pop	    rdi					    ;programname from stack
pop	    rdi					    ;argument from stack
call    strlen
cmp	    rax,10				    ;maximum 10 digits
jg	    usage
call    asciiztohex				    ;convert asciiz in rdi to hexadecimal in rax
jc	    usage				    ;if carryflag is set then syntax error

;rax has the hexadecimal value of the asciiz string, now rotate it once left.
mov	    rdi,rax
call    RotateBitsLeft
;the result (in rax) is the solution to our problem
mov     rdi,rax
call    hextoasciiz				    ;convert hexadecimal in rdi to asciiz
mov	    byte[buffer+rax],10
inc	    rax
push    rax
syscall write,stdout,output,output.length
pop	    rax
syscall write,stdout,buffer,rax
syscall exit,0
usage:
syscall write,stdout,msgusage,msgusage.length
syscall exit,0

;*********************************************************************************************************
;RotateNbits: rotate msbit in a bitword to the least significant position ignoring leading zeros.
;
;in :    decimal number in rdi
;out :   most significant bit of value in RDI becomes least significant bit.
;        result in rax
;remark: Used registers must be saved by caller
;*********************************************************************************************************
RotateBitsLeft:
;rdi contains binary unsigned integer
call    nlz			    ;get the number of leading zeros, these must be skipped
mov     rcx,rax		    ;value of leading zero bits in RCX for rotation count
mov     rax,rdi		    ;value in rax
rol     rax,cl		    ;move all bits until most significant bit is in position 63 in RAX
rcl     rax,1		    ;move most signifant bit in carry flag
inc     rcx			    ;add one to shift count (one bit is moved into carry)
pushfq			    ;store flags (especially carry flag)
ror     rax,cl		    ;shift all bits back in place
popfq			    ;restore flags
rcl     rax,1		    ;move carry flag into position 0 of rax
ret

;*********************************************************************************************************
;
;in :  rdi : number to check
;out : rax : number of leading zeros
;*********************************************************************************************************
nlz:
and	    rdi,rdi
jnz     .count
mov     rax,64		    ;if rdi = 0 then we have 64 zero bits
ret
.count:
mov     rax,rdi		    ;binary number in rax
xor     rbx,rbx		    ;storage for number of zero bits
mov     rcx,32		    ;initialize shift counter
.repeat:
test    rax,rdx		    ;compare number with mask non-destructive
jnz     .nextgroup		    ;if not all bits zero check with next mask
shl     rax,cl		    ;prepare next group bits for check
.nextgroup:
shr     rcx,1		    ;divide shift counter by two
and     rcx,rcx		    ;if shift counter is zero then stop
jnz     .repeat		    ;count next group of bits
mov     rax,rbx		    ;result in rax
ret

;*********************************************************************************************************
;
;in :  rdi : pointer to asciiz string of unsigned integer
;out : if C-Flag = 0, rax = hexadecimal value
;      if C-Flag = 1, rax = invalid value, must be ignored
;*********************************************************************************************************
asciiztohex:
push    rsi
mov	    rsi,rdi		    ;pointer in rsi
.repeat:
and	    al,al		    ;zero means we can exit
jz	    .done
cmp	    al,'9'		    ;if above 9 then exit with carry=1
ja	    .exiterror
cmp	    al,'0'		    ;if below 0 then exit with carry=1
jb	    .exiterror
;only the lowest nibble of al counts, we rotate the low nibble
;into the high nibble of al
rol	    al,4		    ;to high nibble of al
;rotate the nibble in place by rotating rax 4 bits to the left
rol	    rax,4		    ;in the right position in rax
;go for next byte in asciiz string
jmp	    .repeat
.done:
;we are at the end of our string and al contains 0x00
;rotate all digits in place in rax
ror	    rax,8		    ;all digits in place
;store rax as packed decimal in buffer
mov	    qword[buffer],rax	    ;store packed bcd in buffer
;to use the buffer we must be sure to have 0x00 in all ten buffer bytes
;otherwise next operation will fail. Because the program runs once and
;the buffer is initialized with zero bytes this shouldn't be a problem.
;If problems occurs, check this code first, probably this will be the reason.
fbld    [buffer]		    ;load packed bcd value in st0
fistp   qword[buffer]           ;store packed bcd as hexadecimal in buffer
mov	    rax,qword[buffer]	    ;load hexdecimal in buffer in rax
pop	    rsi
clc
ret
.exiterror:
pop	    rsi
stc				    ;set carry flag
xor	    rax,rax		    ;clear rax
ret

hextoasciiz:
push    rdi
push    rsi
push    rdx
push    rcx
mov	    qword[buffer],rdi	    ;store the hexadecimal value in the buffer
fild    qword[buffer]	    ;load the value in st0
fbstp   tword[buffer]	    ;and store as bcd in buffer
;because the input isn't larger than 10 digits the result is also max 10 digits
;which means that the 6 highest nibbles are zero, if the buffer was properly
;initialized with zeros.
;first get the length of the bcd value
mov	    rdi,buffer
call    strlen
mov	    rdx,rax		    ;save the length to return
shl	    rdx,1		    ;n bytes are 2n nibbles
mov	    rbx,rax		    ;save length to calculate with
;shift left rax with 6 nibbles and 10 - length of the bcd value
mov	    rax,10		    ;max 10 digits
shl	    rbx,1		    ;multiply length by 2 to get number of digits
sub	    rax,rbx		    ;numbers of unused digits (0x00)
;we check if high nibble of result are zeros, if yes then weskip them too
mov	    rcx,rbx		    ;total number of nibbles in result in rcx
mov	    rbx,0x0F		    ;prepare mask for highest 4 nibbles
dec	    rcx			    ;prepare rcx to shift maskbits in right place
shl	    rcx,2
shl	    rax,2		    ;4 bits in one digit
mov	    rcx,rax		    ;put in rcx
mov	    rax,qword[buffer]	    ;get the result
and	    rbx,rax		    ;if highest nibbles aren't zero then
jnz	    .convert		    ;start convertion
add	    rcx,4		    ;else skip four bits more
dec	    rdx			    ;one byte less in ascii result
.convert:
shl	    rax,cl		    ;shift highest bcd digit in highest nibble of rax
mov	    rsi,buffer
.nextnibble:
xor	    al,al
rol	    rax,4		    ;nibble in al
or	    al,0x30		    ;make ascii
stosb			    ;store al in buffer at rsi
inc	    rsi			    ;next position in buffer
cmp	    rcx,64		    ;if 64 processed then we're done
jne	    .nextnibble		    ;process next nibble
mov	    rax,rdx		    ;length of result in rax
pop	    rcx			    ;restore used registers
pop	    rdx
pop	    rsi
pop	    rdi
ret

;*********************************************************************************************************
;Get the length of an asciiz string. Length is without trailing zero.
;
;in :  rdi : pointer to asciiz string
;out : rax : length of the asciiz string
;*********************************************************************************************************
strlen:
push    rdi
push    rcx
xor	    rcx,rcx
not     rcx
xor     rax,rax
cld
repnz   scasb
neg     rcx
sub     rcx,2		    ;minus2 for trailing zero and the place behind
mov     rax,rcx
pop	    rcx
pop	    rdi
ret

```