[빡공팟 4기] 6주차 과제: 어셈블리어로 구구단 구현하기/c로 더블 링크드 리스트 구현하기
#1 어셈블리어로 구구단 구현하기
1. 컴파일 과정
1)전처리-hello.c->hello.i
필요한 헤더파일들을 불러옴
2)컴파일-hello.i->hello.s
고급 언어를 저급언어로 바꿈
3)어셈블-hello.s->hello.o
어셈블리어를 기계어로 바꾸어 오브젝트 파일 생성
4)링크-hello.0->hello.exe
여러 오브젝트 파일들끼리, 오브젝트 파일과 라이브러리를 합침
2. 파일 생성
nano 파일명.s
vi 파일명.s3. 목적파일로 만들고 링킹하기
nasm -f elf54 -o 파일명.o 파일명.s
gcc -o 파일명 파일명.o4. memory segment 구조
1) stack: 지역변수를 포함한 함수에 대한 정보들을 포함한다. 여기서 취약점이 제일 많이 나온다. 버퍼오버플로우같ㅇ느 공격을 시도해볼 수 있다.
2) heap: 여기는 동적으로 할당된 변수가 저장
3) bss: 프로그램에서 사용될 변수들이 실제로 위치하는 영역이고, 그 변수들은 초기화되지 않음
4) data: 초기화된 변수
5) test: 시스템이 알아듣는 기계어로 변환된 소스코드
*main함수 실행했을 때 스택 프레임
| 버퍼 |
| 변수 c |
| RBP(base pointer) 여기서부터 스택이 쌓일 것이다. |
| RET(return 주소) |
5. 구현하기
global main, _start
section .bss
buffer: resb 128 ;입력받은 값 저장할 변수
res: resb 10 ;곱 결과를 저장할 변수
increase: resb 10 ;입력 값에 곱하는 증가 값을 저장할 변수
section .data ;출력할 문자 초기화
fmt: db '%d', 0
equal: db '=',0
mul: db '*', 0
end: db 10, 0
section .text ;실행할 코드 저장되는 영역
extern printf ;c의 표준 라이브러리 함수 사용
extern scanf
extern exitglobal main: gcc -o~~할 때 링커에게 보여질 수 있게 하는 부분
exetern:c 표준 라이브러리 호출
multi:
push rbp
mov rbp,rsp
xor rax, rax ;rax=0
xor rbx, rbx ;rbx=0
inc rax ;rax++
inc rbx ;rbx++
_loop: ;반복문 구성하기
mov rcx, 9 ;rcx에 9 전달
cmp rbx, rcx ;rbx랑 9랑 비교
jg _end ;rbx가 더 크면 _end로
mov rax, rbx ;rax에 rbx값전달
mov rdi,[buffer] ;rdi포인터에 입력받은 값
mul rdi ;rax*rdi
mov [increase],rbx ;increase에 rbx값 저장
mov [res], rax ;res에 rax값 저장
call print_line
inc rbx ;rbx+1
jmp _loop ;_loop로 이동
_end:
leave
ret
print_line:
push rbp
mov rbp, rsp
mov rsi, [buffer]
mov rdi, fmt
mov rax, 0
call printf ;printf("%d", buffer)
mov rdi, mul
mov rax, 0
call printf ;printf("*")
mov rsi, [increase]
mov rdi, fmt
mov rax, 0
call printf ;printf("%d", increase)
mov rdi, equal
mov rax,0
call printf ;printf("=")
mov rsi, [res]
mov rdi, fmt
mov rax, 0
call printf ;printf("%d", res)
mov rdi, end
mov rax,0
call printf ;printf("\n")
leave
ret
main:
_start:
push rbp
mov rsi, buffer ;rsi에 buffer주소값 rsi->buffer
mov rdi, fmt ;rdi에 fmt("%d") 주소값
mov rax, 0 ;system call
call scanf ;입력 받기
call multi ;multi 함수 호출
call exit ;exit 함수 호출
pop rbp
retpush a:스택에 a값을 넣음
pop a:스택에 있는 a값을 뺌
mov a,b: b값을 a에 넣음
lea a,[b]: b주소를 a에 넣음
add,sub:더하기 빼기, 더하고 빼는 숫자를 정할 수 있음
inc,dec: 1더하기 빼기
mul:곱하기
cmp:compare 값 비교하기
jmp:jump 특정위치로 건너 뛰기
call:함수 호출
*system call table
https://chromium.googlesource.com/chromiumos/docs/+/master/constants/syscalls.md
#2. c언어로 더블 링크드 리스트 구현하기
1. 더블 링크드 리스트란
기존은 싱글 링크드 리스트의 단점을 보완하여 포인터가 양방향으로 있는 자료구조. 탐색할 때 용이하다.
예를 들어 탐색 시 100개의 노드 중 99번째에 찾는 노드가 있을 때 싱글 링크드 리스트는 맨 처음부터 99번째까지 거쳐야하는데 더블 링크드 리스트는 100번째부터 거꾸로 찾을 수 있어서 시간 단축이 된다.
2. 구현 절차
1) 다음 노드를 가리키는 포인터, 이전 노드를 가리키는 포인터
2) 맨 앞, 맨 뒤에 노드 추가하기
3) 중간에 노드 끼워넣기
4) 노드 삭제하기
-구체적으로
//노드 추가
//current->new, new->next/ current<-new, new<-next 포인터를 만드는 과정임
Current->Next->Prev=newNode; //new<-next
newNode->Prev=Current; //current<-new
newNode->Next=Current->Next; //new->next
Current->Next=newNode; //current->new
//노드 삭제
//맨 앞에 있을 때
if(*head==remove){ //
*head=remove->Next; //head를 next로 바꿈
}
//리무브가 다음 링크가 있을 때
if(remove->Next !=NULL){
remove->Next->Prev =remove->Prev;
}
//리무브가 전 링크가 있을 때
if(remove->Prev!=NULL){
remove->Prev->Next =remove->Next;
}
deleteNode(remove);
}
3. 구현하기
#include <stdio.h>
#include <stdlib.h>
typedef struct listNode{
int Data;
struct listNode* Next;
struct listNode* Prev;
}Node;
//노드 생성
Node* createNode(int data){ //노드 만들기
Node* newNode =(Node*)malloc(sizeof(Node)); //노드만큼의 메모리
newNode->Data=data; //변수들 초기화
newNode->Next=NULL; //새 노드의 다음 노드는 비어있음.
newNode->Prev=NULL; //새 노드의 이전 노드는 비어있음.
return newNode;
}
//노드 소멸
void deleteNode(Node* Node){ //노드 삭제하기
free(Node); //메모리에서 없앰
}
Node* getNodeAt(Node* head, int index){ //몇 번째 인덱스의 노드를 가져옴
Node*horse= head;
int count=0;
while(horse!=NULL){ //다음 노드가 없을 때까지, 마지막 노드까지
if(count++ ==index){
return horse;
}
horse = horse->Next; //못찾으면 그냥 다음
}
reutrn NULL;//못찾으면 null
}
int countNode(Node* head){ //리스트에 노드 몇개인지
int count=0;
Node* horse=head;//시작점으로
while(horse!=NULL){
horse=horse->Next;
count++;
}
return count;
}
//맨 앞, 맨 뒤에 노드 추가
void addNode(Node** head, Node* newNode){ //끝에 노드 추가
//리스트가 없을 때
if (*head == NULL){
*head =newNode;
}
//리스트가 있을 때
else{
Node* horse=(*head);
while(horse->Next !=NULL){
horse=horse->Next; //맨 마지막 노드 찾는중
}
horse->Next = newNode;//새노드 생성
newNode->Prev=horse;// 전 노드랑 연결
}
}
//중간에 노드 끼워넣기
void insertNode(Node* Current, Node* newNode){
//맨 앞
if(Current->Prev ==NULL &&Current->Next == NULL){
Current->Next =newNode;
newNode->Prev=Current;
} //맨 앞 아님
//맨 뒤
if(Current->Next ==NULL){
Current->Next =newNode; //노드 생성
newNode->Prev =Current; //노드 이전거랑 연결
}
//꼬리 아님=>중간 2개
else{//current->new, new->next/ current<-new, new<-next 포인터를 만드는 과정임
Current->Next->Prev=newNode;//노드 생성
newNode->Prev=Current;//이전 거랑 연결
newNode->Next=Current->Next; // 이후 거랑 연결
Current->Next=newNode;//
}
}
//노드 삭제
void removeNode (Node** head,Node* remove){ //노드 추가
//맨 앞에 있을 때
if(*head==remove){ //
*head=remove->Next; //head를 next로 바꿈
}
//리무브가 다음 링크가 있을 때
if(remove->Next !=NULL){
remove->Next->Prev =remove->Prev;//노드1->노드2->노드2이전=노드1->노드1이전
}
//리무브가 전 링크가 있을 때
if(remove->Prev!=NULL){
remove->Prev->Next =remove->Next;
}
deleteNode(remove);
}
참고
더블 링크드 리스트 다함께 C언어로 코딩 해봐요 - by Gunny (Korean Ver.) - YouTube
[C] 더블 링크드 리스트, 이중 연결 (Do.. : 네이버블로그 (naver.com)
시스템 해킹 강좌 1강 - 칼리 리눅스(Kali Linux) 실습 환경 구축하기 (System Hacking Tutorial 2017 #1) - YouTube
어셈블리로 구구단 짜기(nasm) (tistory.com)