extern io_get_dec, io_print_dec, io_newline
section .data
MAX equ 31
memMAX dd MAX
section .bss
C resd (MAX * MAX)
n resd 1
k resd 1
i resd 1
j resd 1
tmp1 resd 1
tmp2 resd 1
tmp3 resd 1
sum resd 1
numLen resd 1
cntz resd 1
firstIter resd 1
section .text
global main
main:
call io_get_dec
mov dword [n], eax
call io_get_dec
mov dword [k], eax
; for (int i = 0; i < MAX; ++i) {
; C[0][i] = 1;
; }
xor ecx, ecx
initC:
mov dword [C + 4 * ecx], 1
inc ecx
cmp ecx, MAX
jl initC
; end initC
; for (int i = 1; i < MAX; ++i) {
; for (int j = 0; j < MAX; ++j) {
; if (i <= j) {
; C[i * MAX + j] = C[i * MAX + j - 1] + C[(i - 1) * MAX + j - 1];
; } else {
; C[i * MAX + j] = 0;
; }
; }
; }
mov dword [i], 1
mov dword [j], 0
fillCOuter:
fillCInner:
mov eax, dword [i]
mul dword [memMAX]
add eax, dword [j]
lea eax, [C + 4 * eax]
mov dword [eax], 0
mov dword [tmp3], eax
mov eax, dword [i]
mov ebx, dword [j]
cmp eax, ebx
jg invalidCell ; i > j continue
mov eax, dword [i]
mul dword [memMAX]
add eax, dword [j]
dec eax
lea eax, [C + 4 * eax]
mov eax, dword [eax]
mov dword [tmp1], eax ; tmp1 = C[i * MAX + j - 1]
mov eax, dword [i]
dec eax
mul dword [memMAX]
add eax, dword [j]
dec eax
lea eax, [C + 4 * eax]
mov eax, dword [eax]
mov dword [tmp2], eax ; tmp2 = C[(i - 1) * MAX + j - 1]
mov eax, dword [tmp3]
mov ebx, dword [tmp1]
add dword [eax], ebx
mov ebx, dword [tmp2]
add dword [eax], ebx
invalidCell:
mov ecx, dword [j]
inc ecx
mov dword [j], ecx
cmp ecx, MAX
jl fillCInner ; go to fillCInner
mov dword [j], 0
mov ecx, dword [i]
inc ecx
mov dword [i], ecx
cmp ecx, MAX
jl fillCOuter
; end fillCOuter
; int sum = 0;
mov dword [sum], 0
cmp dword [n], 0
je skip3
; int numLen = 32 - __builtin_clz(n);
mov dword [numLen], 32
mov eax, 0
lzcnt eax, dword [n]
sub dword [numLen], eax
; for (int i = 0; i < numLen - 1; ++i) {
; if (k > i) {
; continue;
; }
; sum += C[k * MAX + i];
; }
xor ecx, ecx
dec dword [numLen]
cmp dword [numLen], 0
jle skip4
forSmallerDigits:
cmp dword [k], ecx
jg skipIter1
; sum += C[k * MAX + i];
mov eax, dword [k]
mul dword [memMAX]
add eax, ecx
lea eax, [C + 4 * eax]
mov eax, dword [eax]
add dword [sum], eax
skipIter1:
inc ecx
cmp ecx, dword [numLen]
jl forSmallerDigits
skip4:
; inc dword [numLen]
;mov eax, dword [sum]
;call io_print_dec
;call io_newline
; int cntz = 0;
mov dword [cntz], 0
; int firstIter = 1;
mov dword [firstIter], 1
mov ecx, dword [numLen]
lastLoop:
mov eax, dword [n]
mov dword [tmp1], eax
shr dword [tmp1], cl
and dword [tmp1], 1
cmp dword [tmp1], 0
je incZ
cmp dword [firstIter], 1
je preFin
; k - cntz - 1 < 0 ; continue
mov eax, dword [k]
mov dword [tmp2], eax
mov eax, dword [cntz]
sub dword [tmp2], eax
dec dword [tmp2]
cmp dword [tmp2], 0
jl fin
; k - cntz - 1 - i > 0 ; continue
mov eax, ecx
sub dword [tmp2], eax
cmp dword [tmp2], 0
jg fin
mov eax, ecx
add dword [tmp2], eax
mov eax, dword [tmp2]
mul dword [memMAX]
add eax, ecx
lea eax, [C + 4 * eax]
mov eax, dword [eax]
add dword [sum], eax
jmp fin
incZ:
inc dword [cntz]
jmp fin
preFin:
mov dword [firstIter], 0
fin:
dec ecx
cmp ecx, 0
jge lastLoop
; eax = 32 - __builtin_clz(n)
mov eax, 32
lzcnt ebx, dword [n]
sub eax, ebx
; ebx = __builtin_popcount(n) + k
popcnt ebx, dword [n]
add ebx, dword [k]
cmp eax, ebx
jne skip3
cmp dword [n], 0
jle skip3
inc dword [sum]
skip3:
mov eax, dword [sum]
call io_print_dec
call io_newline
xor eax, eax
ret