.text .globl main ## int f(int i, int c) { ## if (i == N) ## return 0; ## int key = c << L | i; ## int r = memo[key]; ## if (r != 0) ## return r; ## int s = 0, j = 0; ## for (j = 0; j < N; j++) { ## int col = 1 << j; ## if ((c & col) == 0) ## continue; ## int x = m[i][j] + f(i + 1, c - col); ## if (x > s) s = x; ## } ## memo[key] = s; ## return s; ## } .set N, 15 ### i %rdi / c %rsi / key %rdx / j %rcx / s %rax / x,col %r8 f: xorq %rax, %rax # s = 0 cmpq $N, %rdi # i == N ? je exit movq %rsi, %rdx # key = c << L | i salq $4, %rdx orq %rdi, %rdx movl memo(,%rdx,4), %eax testq %rax, %rax jnz exit # r != 0 ? xorq %rcx, %rcx # j = 0 jmp test loop: movq $1, %r8 salq %cl, %r8 # col = 1 << j testq %rsi, %r8 # c & col == 0 ? jz continue pushq %rax # sauvegarde s, i, c, key, j pushq %rdi pushq %rsi pushq %rdx pushq %rcx incq %rdi # i + 1 subq %r8, %rsi # c - col call f movq %rax, %r8 popq %rcx # restauration j, key, c, i, s popq %rdx popq %rsi popq %rdi popq %rax movq %rdi, %r9 # m[i][j] imulq $N, %r9 addq %rcx, %r9 movl m(,%r9,4), %r9d addq %r9, %r8 # x = m[i][j] + f(...) cmpq %rax, %r8 # x > s ? cmovg %r8, %rax continue: incq %rcx # j++ test: cmpq $N, %rcx # j < N ? jl loop movl %eax, memo(,%rdx,4) exit: ret ## int main() { ## printf("solution = %d\n", f(0, (1 << N) - 1)); ## return 0; ## } main: subq $8, %rsp # alignement movq $0, %rdi movq $1, %rsi salq $N, %rsi decq %rsi call f movq $format, %rdi # premier argument (format) movq %rax, %rsi # deuxième argument (f(...)) xorq %rax, %rax # %rax = 0 = pas de registres vecteurs call printf xorq %rax, %rax # code de sortie 0 addq $8, %rsp ret .data format: .string "solution = %d\n" m: .long 7 .long 53 .long 183 .long 439 .long 863 .long 497 .long 383 .long 563 .long 79 .long 973 .long 287 .long 63 .long 343 .long 169 .long 583 .long 627 .long 343 .long 773 .long 959 .long 943 .long 767 .long 473 .long 103 .long 699 .long 303 .long 957 .long 703 .long 583 .long 639 .long 913 .long 447 .long 283 .long 463 .long 29 .long 23 .long 487 .long 463 .long 993 .long 119 .long 883 .long 327 .long 493 .long 423 .long 159 .long 743 .long 217 .long 623 .long 3 .long 399 .long 853 .long 407 .long 103 .long 983 .long 89 .long 463 .long 290 .long 516 .long 212 .long 462 .long 350 .long 960 .long 376 .long 682 .long 962 .long 300 .long 780 .long 486 .long 502 .long 912 .long 800 .long 250 .long 346 .long 172 .long 812 .long 350 .long 870 .long 456 .long 192 .long 162 .long 593 .long 473 .long 915 .long 45 .long 989 .long 873 .long 823 .long 965 .long 425 .long 329 .long 803 .long 973 .long 965 .long 905 .long 919 .long 133 .long 673 .long 665 .long 235 .long 509 .long 613 .long 673 .long 815 .long 165 .long 992 .long 326 .long 322 .long 148 .long 972 .long 962 .long 286 .long 255 .long 941 .long 541 .long 265 .long 323 .long 925 .long 281 .long 601 .long 95 .long 973 .long 445 .long 721 .long 11 .long 525 .long 473 .long 65 .long 511 .long 164 .long 138 .long 672 .long 18 .long 428 .long 154 .long 448 .long 848 .long 414 .long 456 .long 310 .long 312 .long 798 .long 104 .long 566 .long 520 .long 302 .long 248 .long 694 .long 976 .long 430 .long 392 .long 198 .long 184 .long 829 .long 373 .long 181 .long 631 .long 101 .long 969 .long 613 .long 840 .long 740 .long 778 .long 458 .long 284 .long 760 .long 390 .long 821 .long 461 .long 843 .long 513 .long 17 .long 901 .long 711 .long 993 .long 293 .long 157 .long 274 .long 94 .long 192 .long 156 .long 574 .long 34 .long 124 .long 4 .long 878 .long 450 .long 476 .long 712 .long 914 .long 838 .long 669 .long 875 .long 299 .long 823 .long 329 .long 699 .long 815 .long 559 .long 813 .long 459 .long 522 .long 788 .long 168 .long 586 .long 966 .long 232 .long 308 .long 833 .long 251 .long 631 .long 107 .long 813 .long 883 .long 451 .long 509 .long 615 .long 77 .long 281 .long 613 .long 459 .long 205 .long 380 .long 274 .long 302 .long 35 .long 805 .bss memo: .space 2097152