extern io_get_dec, io_print_dec
section .bss
k resd 1
comb resd 31*32
; comb[n][r] = C из n по r
; comb[n][r] = comb[ (n * 32 + r) * 4 ]
; ebp = n
section .text
global main
main:
call io_get_dec
mov ebp, eax
call io_get_dec
mov [k], eax
cmp dword [k], 29
jg print_zero
; 1000000000 = 111011100110101100101000000000
xor ecx, ecx
build_rows:
cmp ecx, 31
jge build_done
; offset: n * 32 * 4 = n * 128 = 2 ^ 7
mov edx, ecx
shl edx, 7
; comb[n][0] = 1
mov dword [comb + edx], 1
; comb[n][n] = 1
lea eax, [edx + ecx*4]
mov dword [comb + eax], 1
; C[n][r] = C[n-1][r-1] + C[n-1][r]
mov esi, 1
build_inner:
cmp esi, ecx
jge next_row
mov eax, edx
sub eax, 128
mov ebx, [comb + eax + esi*4 - 4]
add ebx, [comb + eax + esi*4]
mov dword [comb + edx + esi*4], ebx
inc esi
jmp build_inner
next_row:
inc ecx
jmp build_rows
build_done:
xor edi, edi
bsr edx, ebp
xor ecx, ecx
count_shorter:
cmp ecx, edx
jge shorter_done
mov eax, [k]
cmp eax, ecx
jg shorter_skip
mov ebx, ecx
shl ebx, 7
add edi, [comb + ebx + eax*4]
shorter_skip:
inc ecx
jmp count_shorter
shorter_done:
xor esi, esi
dec edx
same_len_loop:
cmp edx, -1
je same_len_finish
bt ebp, edx
jnc bit_is_zero
mov eax, [k]
sub eax, esi
dec eax
cmp eax, 0
jl after_branch_add
cmp eax, edx
jg after_branch_add
mov ebx, edx
shl ebx, 7
add edi, [comb + ebx + eax*4]
after_branch_add:
dec edx
jmp same_len_loop
bit_is_zero:
inc esi
cmp esi, [k]
jg done_counting
dec edx
jmp same_len_loop
same_len_finish:
cmp esi, [k]
jne done_counting
inc edi
done_counting:
mov eax, edi
call io_print_dec
xor eax, eax
ret
print_zero:
xor eax, eax
call io_print_dec
xor eax, eax
ret