본문 바로가기
자료구조, 알고리즘/x64 assembly

백준 1157 단어 공부

lok2h4rd 2021. 11. 11. 13:03

 

problem

문자열(대소문자 알파벳)을 입력하고 가장 많이 사용된 알파벳을 대문자로 출력해주는 코드를 작성하면 됩니다

이때 A, a를 따로 구분 짓지 않고 동일하게 봅니다 여기서 만약 가장 많이 사용된 횟수가 동일한 알파벳이 존재한다면 ?를 출력하면 됩니다

예제 입출력

예제 입력에 따른 출력을 보면 다음과 같습니다 우선 코드를 보기 전에 결론부터 말하면....

실행 결과

.....이게 조금 그런 게 제 환경에서 질문 올라오는 반례들도 다 돌려봐도 올바르게 나왔는데 런타임 에러가 나왔습니다

런타임 에러..

정확히는 모르지만 처음 런타임 에러가 나온건 .data영역에 문자열을 입력받아서 그렇지 않을까 싶어 .bss영역으로도 옮겨보고 이것저것 해봤는데

결국 C언어로 다른 분들이 문제 푼 코드를 보고 아... 스택에 넣으면 되겠구나 싶어서 바꿨는데!!

 런타임 에러.. 물론 맞지는 않았지만 그래도 복기할 겸 다시 정리해보는 것도 좋을 것 같아서 써봅니다

global main
extern scanf
extern printf


section .text
	find_big:
		push rbp
		mov rbp, rsp
		sub rsp, 0x20
		xor rax, rax
		mov [rbp-0x8], rax	; index
		mov [rbp-0x10], rax 	; biggest let
		mov [rbp-0x18], rax 	; biggest let index
		mov [rbp-0x20], rax	; check if there's two same case
	find_loop:
		mov rax, [rbp-0x8]
		cmp rax, 0x1b			; loop until 0x1a
		je check_same
		mov rax, [alpha + rax * 8]	
		cmp rax, qword[rbp-0x10]	; cmp the number of letter
		jl next_find			; if it less than the prev letter then jump to the next loop
		je two_case
		mov [rbp-0x10], rax		; case if it's big
		mov rax, [rbp-0x8]
		mov [rbp-0x18], rax
		xor rax, rax
		mov [rbp-0x20], rax
		jmp next_find
	two_case:
		inc qword[rbp-0x20]		; if there's same number of letter than inc				
	next_find:
		inc qword[rbp-0x8]		; increase index
		jmp find_loop

	check_same:
		mov rax, [rbp-0x20]
		cmp rax, 1
		jge exit_none
		mov rax, [rbp-0x18]
		add rax, 0x40
		jmp exit_func
	exit_none:
		mov rax, 0x3f
	exit_func:
		add rsp, 0x20
		leave
		ret
	main:
		push rbp
		mov rbp, rsp
		sub rsp, 0xf4250
		xor rax, rax 
		mov [rbp-0x8], rax	; index
		mov [rbp-0x10], rax
	
		mov rdi, input 
		lea rsi, [rbp-0xf4250]
		call scanf
	
	loop:
		mov rax, [rbp-0x8]
		mov al, byte[rbp-0xf4250 + rax]
		test rax, rax
		je print_res


		cmp rax, 0x60
		jl cap_let
		sub rax, 0x60
		jmp next_loop
		
	cap_let:
		sub rax, 0x40	
	next_loop:
		inc qword[alpha + rax * 8]
		inc qword[rbp-0x8]
		jmp loop
	print_res:
		call find_big
		mov rdi, output
		mov rsi, rax
		call printf
		xor rax, rax
		leave
		ret


section .data
alpha: TIMES 0x1b dq 0
input: db "%s",00
output: db "%c",10,00

 

코드를 어떤 식을 작성해야될지 생각해보면 문자열을 입력받아야 하고 문자열들의 각 문자를 대소문자 구분하지 않고 등장하는 횟수를 카운팅 해야 합니다

그리고 가장 많이 카운팅 된 문자 중 동일한 문자가 있는지 확인하고 있다면 그거에 맞는 처리를 해줘야겠죠

 

 그래서 해당 코드는 문자열을 입력받고 각 문자의 횟수를 카운팅 해주는 main함수가 있고 main함수 내부에서 find_big함수를 call 하게 됩니다 find_big함수는 가장 많이 카운팅 된 알파벳을 선별하고 또한 가장 많이 카운팅 된 알파벳이 단일인지 검사하게 됩니다

 

	main:
		push rbp
		mov rbp, rsp
		sub rsp, 0xf4250
		xor rax, rax 
		mov [rbp-0x8], rax	; index
		mov [rbp-0x10], rax
	
		mov rdi, input 
		lea rsi, [rbp-0xf4250]
		call scanf

main함수에서 사용할 스택 + 문자열 길이만큼 rsp를 빼주고 scanf함수로 입력을 받습니다

 

	
	loop:
		mov rax, [rbp-0x8]
		mov al, byte[rbp-0xf4250 + rax]
		test rax, rax
		je print_res


		cmp rax, 0x60
		jl cap_let
		sub rax, 0x60
		jmp next_loop
		
	cap_let:
		sub rax, 0x40	
	next_loop:
		inc qword[alpha + rax * 8]
		inc qword[rbp-0x8]
		jmp loop

 scanf로 문자열을 입력받은 뒤에 loop를 돌게 되는데 여기서는 입력받는 문자열을 한 문자씩 받아들여 대문자인지, 소문자 인지 검사하게 됩니다(cmp rax, 0x60) 만약 0x60보다 작으면 cap_let으로 점프하게 되는데 대문자이면 점프하고 소문자이면 0x60을 빼준뒤 next_loop으로 점프하게 됩니다

 

대문자는 0x40을 소문자는 0x60을 빼주기 때문에 수의 범위가 1 ~ 26까지가 되어 대소문자 구분 없이 alpha배열을 증가시킴으로써 각 문자의 횟수를 카운팅 합니다

[rbp-0x8]은 검사한 다음 문자열의 index를 위해 1 증가시킨 뒤 loop로 다시 점프하게 됩니다

 

여담이지만 여기서 만약 문자열이 입력되었을 때 문자열 마지막에 다른 데이터가 들어가 있거나 어떤 데이터 값을 overwrite 하게 되면 그 데이터를 포함하여 0x00이 나올 때까지 검사를 수행하게 될 때 문제가 발생할 것을 보입니다

strlen을 사용해도 결국 널 바이트까지의 길이를 판별하는 거라 달라지는 건 없어 보이고.... scanf함수를 구현해보면 해결될 듯합니다

 

print_res:
		call find_big
		mov rdi, output
		mov rsi, rax
		call printf
		xor rax, rax
		leave
		ret

문자열의 각 문자의 횟수 체크가 되면 print_res로 점프하게 됩니다 여기서는 바로 find_big함수로 점프하게 되고 

find_big함수의 반환 값(rax)을 인자로 넣고 출력시켜 줍니다

 

 

find_big:
		push rbp
		mov rbp, rsp
		sub rsp, 0x20
		xor rax, rax
		mov [rbp-0x8], rax	; index
		mov [rbp-0x10], rax 	; biggest let
		mov [rbp-0x18], rax 	; biggest let index
		mov [rbp-0x20], rax	; check if there's two same case
	find_loop:
		mov rax, [rbp-0x8]
		cmp rax, 0x1b			; loop until 0x1a
		je check_same
		mov rax, [alpha + rax * 8]	
		cmp rax, qword[rbp-0x10]	; cmp the number of letter
		jl next_find			; if it less than the prev letter then jump to the next loop
		je two_case
		mov [rbp-0x10], rax		; case if it's big
		mov rax, [rbp-0x8]
		mov [rbp-0x18], rax
		xor rax, rax
		mov [rbp-0x20], rax
		jmp next_find
	two_case:
		inc qword[rbp-0x20]		; if there's same number of letter than inc				
	next_find:
		inc qword[rbp-0x8]		; increase index
		jmp find_loop

	check_same:
		mov rax, [rbp-0x20]
		cmp rax, 1
		jge exit_none
		mov rax, [rbp-0x18]
		add rax, 0x40
		jmp exit_func
	exit_none:
		mov rax, 0x3f
	exit_func:
		add rsp, 0x20
		leave
		ret

find_big함수에서는 가장 카운팅이 된 알파벳을 찾고 만약 가장 많이 카운팅 된 알파벳이 한 개 이상이면 '?'를 출력시키도록 해주어야 합니다

 

find_big:
		push rbp
		mov rbp, rsp
		sub rsp, 0x20
		xor rax, rax
		mov [rbp-0x8], rax	; index
		mov [rbp-0x10], rax 	; biggest let
		mov [rbp-0x18], rax 	; biggest let index
		mov [rbp-0x20], rax	; check if there's two same case

사용되는 레지스터에 대한 주석을 적어놨습니다 사실 제가 잘 안 읽혀서 적었음다

[rbp-0x8]은 alpha배열의 index를 검사하기 위해 1 증가됩니다

for(int i = 0; i < N; i++){
	rax = alpha[i];
}

위의 for문에서 i의 역할을 [rbp-0x8]이 수행하게 됩니다

여기서 잠깐 짚고 넘어갈게 alpha에는 각 알파벳이 등장한 횟수를 저장하고 있습니다

이 값을 꺼내서 값을 확인하고 가장 크다면 index에 0x40을 더해주면 해당 알파벳의 대문자가 될 것입니다

 

그래서 [rbp-0x10]은 현재까지 검사한 index 중 가장 많은 횟수를 저장하고 있으며 [rbp-0x18]에는 그에 대한 index가 저장합니다 

마지막으로 [rbp-0x20]에는 가장 많이 카운팅 된 알파벳이 몇 개인지 체크하게 됩니다 단일일 시에는 0이고 둘 이상이 되면 1 이상으로 증가하게 됩니다

	find_loop:
		mov rax, [rbp-0x8]
		cmp rax, 0x1b			; loop until 0x1a
		je check_same
		mov rax, [alpha + rax * 8]	
		cmp rax, qword[rbp-0x10]	; cmp the number of letter
		jl next_find			; if it less than the prev letter then jump to the next loop
		je two_case
		mov [rbp-0x10], rax		; case if it's big
		mov rax, [rbp-0x8]
		mov [rbp-0x18], rax
		xor rax, rax
		mov [rbp-0x20], rax
		jmp next_find
	two_case:
		inc qword[rbp-0x20]		; if there's same number of letter than inc				
	next_find:
		inc qword[rbp-0x8]		; increase index
		jmp find_loop

가장 먼저 find_loop이 등장합니다 find_loop에서는 [rbp-0x10]과 현재 인덱스의 횟수를 검사합니다

그리고 현재 인덱스의 횟수가 작게 되면 next_find로 점프하여 [rbp-0x8]를 1 증가시킨 뒤 find_loop로 점프하게 됩니다

만약 같다면 two_case로 점프하게 되는데 여기서는 단순히 [rbp-0x20]을 증가시킵니다

 

만약 현재 인덱스의 저장된 횟수가 [rbp-0x10]보다 작지도 같지도 즉 더 크게 되면 현재 횟수를 [rbp-0x10]에 저장하고 현재 인덱스(rbp-0x8)를 [rbp-0x18]에 저장하고 [rbp-0x20]을 0으로 초기화시킵니다 그 후 next_find로 점프하여 다음 루프를 준비합니다 

 

이 루프는 0x1a(26)만큼 수행하고 check_same으로 점프하게 됩니다

	check_same:
		mov rax, [rbp-0x20]
		cmp rax, 1
		jge exit_none
		mov rax, [rbp-0x18]
		add rax, 0x40
		jmp exit_func
	exit_none:
		mov rax, 0x3f
	exit_func:
		add rsp, 0x20
		leave
		ret

check_same은 [rbp-0x20]을 검사함으로써 단일인지 다수인지 검사하게 됩니다

단일이면 해당 해당 인덱스를 0x40과 더해주어 대문자로 만들고 exit_func으로 가서 스택을 정리하고 함수를 종료시킵니다

만약 단일이 아니게 되면 exit_none으로 점프하여 rax에 '?'의 아스키코드인 0x3f를 넣어주고 함수를 종료시킵니다

	print_res:
		call find_big
		mov rdi, output
		mov rsi, rax
		call printf
		xor rax, rax
		leave
		ret

이후에 printf를 통해 find_big 함수로부터 반환된 값을 출력시키게 됩니다

 

 

 

 

** 마무리 생각해도 문자열 입력받을 때 문제인 것 같습니다..

'자료구조, 알고리즘 > x64 assembly' 카테고리의 다른 글

쌩 어셈블리로 두수 더하기  (0) 2021.12.28
백준 2675 문자열 반복  (0) 2021.11.08
백준 25577번 숫자의 개수  (0) 2021.10.31
백준 2741 N 찍기  (0) 2021.10.30

'자료구조, 알고리즘/x64 assembly' Related Articles

티스토리툴바