### code x86-64 pour résoudre le problème des N reines
### lit N sur l'entrée standard
###
### compilation manuelle du code C suivant
###
### int t(int a, int b, int c) {
###   int f = 1;
###   if (a) {
###     int d, e = a & ~b & ~c;
###     f = 0;
###     while (d = e & -e) {
###       f += t(a - d, (b + d) * 2, (c + d) / 2);
###       e -= d;
###     }
###   }
###   return f;
### }
###
### main() {
###   int n;
###   scanf("%d", &n);
###   printf("queens(%d) = %d\n", n, t(~(~0 << n), 0, 0));
### }

        .text
	.globl	main
main:
        pushq   %rbp
        movq    %rsp, %rbp
        movq    $input, %rdi    # premier argument de scanf = format
        movq    $q, %rsi        # second argument de scanf = adresse pour n
        xorq    %rax, %rax      # pas d'autres arguments
        call    scanf

        xorq    %rdi, %rdi      # a = ~(~0 << n)
        notq    %rdi
        movq    (q), %rcx
        salq    %cl, %rdi       # un décalage calculé doit utiliser %cl
        notq    %rdi
        xorq    %rsi, %rsi      # b = 0
        xorq    %rdx, %rdx      # c = 0
        call    t

	movq	$msg, %rdi      # premier argument de printf = format
        movq    (q), %rsi      # deuxième argument = n
        movq    %rax, %rdx      # troisième argument = résultat
        xorq    %rax, %rax      # pas d'autres arguments
	call	printf
        xorq    %rax, %rax      # code de sortie 0 pour exit
        popq    %rbp
	ret

        ##  t(a:rdi, b:rsi, c:rdx)
        ##     e:rcx, d:r8, f:rax
t:
        movq    $1, %rax        # f <- 1
        testq   %rdi, %rdi      # a = 0 ?
        jz      t_return
        pushq   %rbp
        movq    %rsp, %rbp
        subq    $48, %rsp       # allouer 6 mots sur la pile
        xorq    %rax, %rax      # f <- 0
        movq    %rdi, %rcx      # e <- a & ~b & ~c
        movq    %rsi, %r9
        notq    %r9
        andq    %r9, %rcx
        movq    %rdx, %r9
        notq    %r9
        andq    %r9, %rcx
        ## note : on peut remplacer les six dernières instructions par
        ## andn %rcx, %rsi, %rcx (Logical AND NOT)
        ## andn %rcx, %rdx, %rcx
        jmp     loop_test
loop_body:
        movq    %rdi,  0(%rsp) # sauver a
        movq    %rsi,  8(%rsp) # sauver b
        movq    %rdx, 16(%rsp) # sauver c
        movq    %r8,  24(%rsp) # sauver d
        movq    %rcx, 32(%rsp) # sauver e
        movq    %rax, 40(%rsp) # sauver f
        subq    %r8, %rdi      # a <- a-d
        addq    %r8, %rsi      # b <- (b+d)<<1
        salq    $1, %rsi
        addq    %r8, %rdx      # c <- (c+d)>>1
        shrq    $1, %rdx
        call    t              # t(a-d, (b+d)<<1, (c+d)>>1)
        addq    40(%rsp), %rax  # f += t(...)
        movq    32(%rsp), %rcx # restaurer e
        subq    24(%rsp), %rcx #  -= d
        movq    16(%rsp), %rdx # restaurer c
        movq     8(%rsp), %rsi # restaurer b
        movq     0(%rsp), %rdi # restaurer a
loop_test:
        movq    %rcx, %r8      # d <- e & -e
        movq    %rcx, %r9
        negq    %r9
        andq    %r9, %r8
        ## note : on peut remplacer les quatre dernières instructions par
        ## blsi    %rcx, %r8 (Extract Lowest Set Isolated Bit)
        jnz     loop_body
        addq    $48, %rsp
        popq    %rbp
t_return:
        ret

        .data
msg:
	.string	"queens(%d) = %d\n"
input:
        .string "%d"
q:
        .quad   0

## Local Variables:
## compile-command: "gcc queens.s -o queens"
## End: