Category: Josephus Problem
Star InactiveStar InactiveStar InactiveStar InactiveStar Inactive
;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.
;    [Numberphile]
;             book: Hackers's Delight

bits 64

%include ""

global _start

section .bss
    buffer:     resb    20
    .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

    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
    ;convert the hexadecimal to asciiz
    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
    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
    ;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    
;Number of Leading Zeros
;in :  rdi : number to check
;out : rax : number of leading zeros
    and	    rdi,rdi
    jnz     .count
    mov     rax,64		    ;if rdi = 0 then we have 64 zero bits
    mov     rax,rdi		    ;binary number in rax
    xor     rbx,rbx		    ;storage for number of zero bits
    mov     rcx,32		    ;initialize shift counter
    mov     rdx,0xFFFFFFFF00000000  ;initialize mask
    test    rax,rdx		    ;compare number with mask non-destructive
    jnz     .nextgroup		    ;if not all bits zero check with next mask
    add     rbx,rcx		    ;count already counted zeros to result
    shl     rax,cl		    ;prepare next group bits for check
    shr     rcx,1		    ;divide shift counter by two
    shl     rdx,cl		    ;adjust bitmask
    and     rcx,rcx		    ;if shift counter is zero then stop
    jnz     .repeat		    ;count next group of bits
    mov     rax,rbx		    ;result in rax

;Convert ASCIIZ string to hexadecimal
;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
    push    rsi
    mov	    rsi,rdi		    ;pointer in rsi
    lodsb			    ;load ascii byte
    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
    ;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
    pop	    rsi
    stc				    ;set carry flag
    xor	    rax,rax		    ;clear rax
    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
    ;ascii all digits and store in buffer, start with highest nibbles
    ;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	    rbx,cl		    ;make mask
    shl	    rax,2		    ;4 bits in one digit
    add	    rax,24		    ;add 24 unused bits (highest bits in rax)
    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
    shl	    rax,cl		    ;shift highest bcd digit in highest nibble of rax
    mov	    rsi,buffer
    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
    add	    rcx,4		    ;4 bits processed
    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

;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
    push    rdi
    push    rcx
    xor	    rcx,rcx
    not     rcx
    xor     rax,rax
    repnz   scasb
    neg     rcx
    sub     rcx,2		    ;minus2 for trailing zero and the place behind
    mov     rax,rcx
    pop	    rcx
    pop	    rdi