%macro r1_push 0 ; push registers except rax
push rbx
push rcx
push rdx
push r8
push r9
push r10
push r11
%endmacro
%macro r1_pop 0 ; pop registers except rax
pop r11
pop r10
pop r9
pop r8
pop rdx
pop rcx
pop rbx
%endmacro
%macro r_push 0 ; push registers including rax
push rax
r1_push
%endmacro
%macro r_pop 0 ; pop registers including rax
r1_pop
pop rax
%endmacro
%define IBUFSZ 1048576
%define OBUFSZ 100
%define L 17
%define P 131072
section .bss
ibuf resb IBUFSZ
obuf resb OBUFSZ
sprmin resq L * P
sprmax resq L * P
N resq 1
K resq 1
section .text
global _start
_start:
; read ibuf
xor rax, rax
xor rdi, rdi
mov rsi, ibuf
mov rdx, IBUFSZ
syscall
mov rsi, ibuf
mov rdi, obuf
call stoi
mov r9, rax
mov [N], rax
call stoi
mov [K], rax
xor rcx, rcx
.s1:
call stoi
mov qword [sprmin + rcx * 8], rax
mov qword [sprmax + rcx * 8], rax
inc rcx
cmp rcx, r9
jl .s1
cmp qword [N], 1
je .s3
mov r10, 1
mov r11, 1
mov r12, 2
.s2:
mov r13, [N]
inc r13
sub r13, r12
xor r14, r14
.s4:
lea rax, [r10 - 1]
imul rax, P
mov rbx, rax
add rax, r14
mov rax, [sprmin + rax * 8]
add rbx, r11
add rbx, r14
mov rbx, [sprmin + rbx * 8]
cmp rbx, rax
cmovbe rax, rbx
mov rbx, r10
imul rbx, P
add rbx, r14
mov [sprmin + rbx * 8], rax
inc r14
cmp r14, r13
jl .s4
shl r11, 1
shl r12, 1
inc r10
cmp r12, [N]
jle .s2
mov r10, 1
mov r11, 1
mov r12, 2
.s5:
mov r13, [N]
inc r13
sub r13, r12
xor r14, r14
.s6:
lea rax, [r10 - 1]
imul rax, P
mov rbx, rax
add rax, r14
mov rax, [sprmax + rax * 8]
add rbx, r11
add rbx, r14
mov rbx, [sprmax + rbx * 8]
cmp rax, rbx
cmovbe rax, rbx
mov rbx, r10
imul rbx, P
add rbx, r14
mov [sprmax + rbx * 8], rax
inc r14
cmp r14, r13
jl .s6
shl r11, 1
shl r12, 1
inc r10
cmp r12, [N]
jle .s5
.s3:
mov r10, [K]
; r9 = n, r10 = k
xor r11, r11
xor r12, r12
.s7:
mov r13, r11
sub r13, r12
inc r13
bsr r13, r13
xor r13, 31
mov r14, 31
sub r14, r13
mov rcx, r14
mov r13, 1
sal r13, cl
imul r14, P
; r14 = d
; r13 = 1 << d
mov rax, r14
add rax, r12
mov rax, [sprmax + rax * 8]
mov rbx, r14
add rbx, r11
sub rbx, r13
inc rbx
mov rbx, [sprmax + rbx * 8]
cmp rax, rbx
cmovbe rax, rbx
mov rbx, r14
add rbx, r12
mov rbx, [sprmin + rbx * 8]
mov rcx, r14
add rcx, r11
sub rcx, r13
inc rcx
mov rcx, [sprmin + rcx * 8]
cmp rcx, rbx
cmovbe rbx, rcx
sub rax, rbx
cmp rax, r10
jle .s8
inc r12
jmp .s7
.s8:
mov rax, r11
sub rax, r12
inc rax
add r15, rax
inc r11
cmp r11, r9
jl .s7
mov rax, r15
call printi
mov rax, 0xa
stosb
; output obuf
sub rdi, obuf
mov rdx, rdi
mov rdi, 1
mov rax, 1
mov rsi, obuf
syscall
; exit syscall
mov rax, 0x3c
xor rdi, rdi
syscall
stoi: ; reads in integer from rsi s buffer and outputs it to rax
r1_push
xor r8,r8
mov r9, 1
.a_stoi:
xor rax, rax
lodsb
cmp al, 45
jne .b_stoi
mov r9, -1
jmp .a_stoi
.b_stoi:
cmp al, 32
je .c_stoi
cmp al, 10
je .c_stoi
cmp al, 0
je .c_stoi
sub al, 48
mov rdx, 10
imul r8, rdx
add r8, rax
jmp .a_stoi
.c_stoi:
mov rax, r8
imul rax, r9
r1_pop
ret
printi: ; outputs an integer rdi s buffer
push rax
r1_push
xor rbx, rbx
cmp rax, 0
jnl .a_printi
imul rax, -1
push rax
mov rax, 45
stosb
pop rax
.a_printi:
xor rdx, rdx
mov rcx, 10
idiv rcx
add rdx, 48
push rdx
inc rbx
cmp rax, 0
jne .a_printi
mov rcx, rbx
.b_printi:
pop rax
stosb
loop .b_printi
mov rax, rdi
r1_pop
mov rdi, rax
pop rax
ret
