What integer does this program print with arguments 266134863 and 1592237099? File: chall.S Flag format: picoCTF{XXXXXXXX} -> (hex, lowercase, no 0x, and 32 bits. ex. 5614267 would be picoCTF{0055aabb})

[WRITEUP]

파일을 다운받고

file chall.S
chall.S: assembler source, ASCII text

확인해보면 어떤 어셈블리 소스코드임을 확인할 수 잇다.

cat chall.S

로 내용을 출력해보면

cat chall.S          
    .arch armv8-a
    .file    "chall.c"
    .text
    .align    2
    .global    func1
    .type    func1, %function
func1:
    sub    sp, sp, #16
    str    w0, [sp, 12]
    str    w1, [sp, 8]
    ldr    w1, [sp, 12]
    ldr    w0, [sp, 8]
    cmp    w1, w0
    bls    .L2
    ldr    w0, [sp, 12]
    b    .L3
.L2:
    ldr    w0, [sp, 8]
.L3:
    add    sp, sp, 16
    ret
    .size    func1, .-func1
    .section    .rodata
    .align    3
.LC0:
    .string    "Result: %ld\n"
    .text
    .align    2
    .global    main
    .type    main, %function
main:
    stp    x29, x30, [sp, -48]!
    add    x29, sp, 0
    str    x19, [sp, 16]
    str    w0, [x29, 44]
    str    x1, [x29, 32]
    ldr    x0, [x29, 32]
    add    x0, x0, 8
    ldr    x0, [x0]
    bl    atoi
    mov    w19, w0
    ldr    x0, [x29, 32]
    add    x0, x0, 16
    ldr    x0, [x0]
    bl    atoi
    mov    w1, w0
    mov    w0, w19
    bl    func1
    mov    w1, w0
    adrp    x0, .LC0
    add    x0, x0, :lo12:.LC0
    bl    printf
    mov    w0, 0
    ldr    x19, [sp, 16]
    ldp    x29, x30, [sp], 48
    ret
    .size    main, .-main
    .ident    "GCC: (Ubuntu/Linaro 7.5.0-3ubuntu1~18.04) 7.5.0"
    .section    .note.GNU-stack,"",@progbits

와 같이 나오는 것을 볼 수 있다. (코드가 짧아서 전체를 집어넣었다.)

func1 함수

func1:
    sub    sp, sp, #16
    str    w0, [sp, 12]
    str    w1, [sp, 8]
    ldr    w1, [sp, 12]
    ldr    w0, [sp, 8]
    cmp    w1, w0
    bls    .L2
    ldr    w0, [sp, 12]
    b    .L3

위에서 핵심은 cmp w1, w0이다.
w0이 w1보다 작으면 L2로 분기한다고 한다.

L2, L3

.L2:
    ldr    w0, [sp, 8]
.L3:
    add    sp, sp, 16
    ret
    .size    func1, .-func1
    .section    .rodata
    .align    3
.LC0:
    .string    "Result: %ld\n"
    .text
    .align    2
    .global    main
    .type    main, %function

main

main:
    stp    x29, x30, [sp, -48]!
    add    x29, sp, 0
    str    x19, [sp, 16]
    str    w0, [x29, 44]
    str    x1, [x29, 32]
    ldr    x0, [x29, 32]
    add    x0, x0, 8
    ldr    x0, [x0]
    bl    atoi
    mov    w19, w0 
    ldr    x0, [x29, 32]
    add    x0, x0, 16
    ldr    x0, [x0]
    bl    atoi 
    mov    w1, w0
    mov    w0, w19
    bl    func1 ; func1호출
    mov    w1, w0 
    adrp    x0, .LC0
    add    x0, x0, :lo12:.LC0
    bl    printf
    mov    w0, 0
    ldr    x19, [sp, 16]
    ldp    x29, x30, [sp], 48
    ret
    .size    main, .-main
    .ident    "GCC: (Ubuntu/Linaro 7.5.0-3ubuntu1~18.04) 7.5.0"
    .section    .note.GNU-stack,"",@progbits

결과적으로 들어오는 인자 중 더 큰 값이 반환된다.
따라서 위 인풋에서 들어오는 값 중 더 큰 것은 1592237099 이므로,
플래그 형식에 맞게 32비트 16진수로 바꾼 플래그는
picoCTF{5ee79c2b}

1. 헤더파일이란?

• 헤더파일: c프로그램에서 .h가 붙는 파일들로, 여러 소스코드 파일에 공통적으로 필요한 것을 저장하는 파일이다.

• #include를 통해 .c파일에서 헤더파일의 내용을 가져다 쓸 수 있다.

• 헤더파일의 필요성: 유지보수와 재사용에 용이하다. 겹치는 내용은 한 번 적어서 include해서 공통적으로 쓸 수 있고, 유지보수할 때도 보기 편하다.

• 컴파일 시 헤더파일을 따로 처리할 필요는 없으며 .c파일을 처리하면서 처리된다.

2. 코드 살펴보기

hacker.h

//hacker.h  
#pragma once  
#include <string.h>  
#include <stdio.h>  
#include <unistd.h>  
#include <stdlib.h>  

//hacker 구조체 정의  
typedef struct hacker{  
    char name[50];  
    unsigned int age;  
    char** skill_list;  
    int skill_num;  
    int level;  
}hacker;  

int input_name(hacker*);  
int input_age(hacker*);  
int input_new_skill(hacker*);  

//new_hacker함수  
hacker* new_hacker() {  
    hacker* new_ptr = (hacker*)malloc(sizeof(hacker));  

    memset(new_ptr->name, '\0', sizeof(new_ptr->name));  
    new_ptr->skill_num = 0;  
    new_ptr->level = 1;  

    new_ptr->skill_list = (char**)malloc(sizeof(char*));  

    input_name(new_ptr);  
    input_age(new_ptr);  
    input_new_skill(new_ptr);  

    return new_ptr;  
}  

//input_name함수  
int input_name(hacker* ptr){  
    write(1,"Input the name : ",17);  
    return scanf("%s",ptr->name);  
}  

int input_age(hacker* ptr){  
    printf("Input the age : ");  
    return scanf("%u",&ptr->age);  
}  

void increase_size(char***);  
int input_new_skill(hacker* ptr){  
    write(1, "Input new Skill : ", 18);  

    char buf[50] = {0,};  
    scanf("%s",buf);  

    char* tmp = (char*)malloc(strlen(buf)+1);  
    strcpy(tmp,buf);  

    ptr->skill_num++;  
    increase_size(&(ptr->skill_list));  


    ptr->skill_list[ptr->skill_num-1] = tmp;  
    return ptr->skill_num;  
}  

void increase_size(char*** skill_list) {  
    if (*skill_list == NULL) {  
        *skill_list = (char**)malloc(sizeof(char*));  
        (*skill_list)[0] = NULL;  
        return;  
    }  
    int org_size = sizeof(*skill_list) / sizeof(char*);  

    char** new_ptr = (char**)malloc(sizeof(char*) * (org_size + 1));  

    for (int i = 0; i < org_size; i++) {  
        new_ptr[i] = (*skill_list)[i];  
    }  
    free(*skill_list);  
    *skill_list = new_ptr;  
}

헤더파일 hacker.h의 전체 코드는 위와 같다.

저 부분들을 하나하나 떼어서 보자면

header files

#pragma once
#include <string.h>
#include <stdio.h> 
#include <unistd.h> 
#include <stdlib.h>

• #pragma once: 컴파일러에게 해당 헤더파일이 한번만 빌드되도록 하는 역할. 여러 곳에서 include되면 정의가 추가되어 중첩될 수 있는데 이를 방지한다.

hacker 구조체

typedef struct hacker{
    char name[50];
    unsigned int age;
    char** skill_list;
    int skill_num;
    int level;
}hacker;

new_hacker 함수

//new_hacker함수  
hacker* new_hacker() {  
    hacker* new_ptr = (hacker*)malloc(sizeof(hacker));  
    // 해커 구조체 크기만큼 메모리 동적 할당
    memset(new_ptr->name, '\0', sizeof(new_ptr->name));  
    //new_ptr->name배열의 모든 바이트를 널로 초기화 
    new_ptr->skill_num = 0;  
    new_ptr->level = 1;  

    new_ptr->skill_list = (char**)malloc(sizeof(char*)); 
    // 스킬 목록을 저장할 포인터 배열을 동적 할당, 초기에는 스킬이 없으므로 char* 

    input_name(new_ptr);  
    input_age(new_ptr);  
    input_new_skill(new_ptr);  
  // input함수들을 통해 사용자의 정보 입력
    return new_ptr;  
    // 초기화된 해커 구조체 포인터를 반환
} 

입력 함수들

hacekr 구조체 포인터를 받아 스킬 입력

• input_name

• input_age

• input_new_skill

int input_new_skill(hacker* ptr){
    write(1, "Input new Skill : ", 18);
    // write함수를 사용해 위 메시지를 표준출력
    char buf[50] = {0,};
    // 임시 저장 버퍼를 50바이트 크기로 선언, 모든 바이트를 0으로 초기화
    scanf("%s",buf);
    // 입력을 버퍼에 저장

    char* tmp = (char*)malloc(strlen(buf)+1);
    // 입력받은 기술명의 길이만큼 메모리 동적 할당
    strcpy(tmp,buf);
    // buf에 저장된 기술명을 동적 할당된 메모리 공간 tmp에 복사

    ptr->skill_num++;
    // 기술 개수 증가
    increase_size(&(ptr->skill_list));
    // 함수 호출, 하단에 있음
    ptr->skill_list[ptr->skill_num-1] = tmp;
    // 새로운 기술명을 기술 목록 배열의 마지막 위치에 추가
    return ptr->skill_num;
    // 기술 개수 반환
}

increase_size 함수

void increase_size(char*** skill_list) {
    if (*skill_list == NULL) {
        *skill_list = (char**)malloc(sizeof(char*));
        (*skill_list)[0] = NULL;
        return;
    }

    int org_size = sizeof(*skill_list) / sizeof(char*);

    char** new_ptr = (char**)malloc(sizeof(char*) * (org_size + 1));

    for (int i = 0; i < org_size; i++) {
        new_ptr[i] = (*skill_list)[i];
    }

    free(*skill_list);
    *skill_list = new_ptr;
}

위 헤더파일의 내용을 받아서 쓰면

//다음과 같은 코드를 이해하고, 작성해봅시다.
//main.c
#include "hacker.h"

int main(){
    hacker* qwertyou = new_hacker();
    printf("%s's age is %d\n",qwertyou->name, qwertyou->age);
    printf("%s's level is %d\n",qwertyou->name, qwertyou->level);


    printf("\n\n-----qwertyou's skill list-----\n");
    for(int i=0;i<qwertyou->skill_num;i++){
        printf("%s's skill%d : %s\n",qwertyou->name, i, qwertyou->skill_list[i]);
    }
}

메인함수에 위 함수들과 다른 헤더파일들도 따로 더 적을 필요가 없다.

• 트리의 개념
• 트리의 순회 방법
• 이진 트리, 완전 이진 트리
• 이진 탐색 트리

1. 트리의 개념

• 나무를 닮은 자료구조

1-1. 트리의 구성 요소

트리의 구성 요소: 뿌리, 가지, 잎 모두 똑같은 노드이나 위치에 따라 명칭이 다르다.

구성 요소

• 뿌리(Root): 가장 위에 있는 노드
• 가지(Branch): 뿌리와 잎 사이
• 잎(Leaf): 끝에 있음(단말:terminal)이라고 하기도 함.

• 부모(parents): A는 B,C,D의 부모
• 자식(Children): B,C,D는 A의 자식
• 형제(Sibling): B,C,D는 형제

경로

• 경로: 한 노드에서 다른 한 노드까지 이르는 길 사이에 있는 노드들의 순서
  example) A에서 K까지의 경로: A,B,E,K
• 경로의 길이(length): 출발 노드에서 목적 노드까지 거쳐야 하는 노드의 개수
  ex) A-K: 3
• 깊이(Depth): 뿌리 노드에서 해당 노드까지 이르는 경로의 길이
  ex) K: 3
• 레벨(level): 깊이가 같은 노드의 집합
  ex) level 3: K, L, M
• 높이(height): 가장 깊은 곳에 있는 잎 노드까지의 깊이
  ex) 3
• 차수(Degree): 노드의 차수->그 노드의 자식 노드 개수, 트리의 차수->트리 내에 있는 노드들 가운데 자식 노드가 가장 많은 노드의 차수

2. 트리의 기본 연산

2-2. 노드 선언

Left Child, Right Sibling 형태 표현법(LCRS)에서
노드 구조체는

typedef char ElementType;
typedef struct tagLCRSNode {
  struct tagLCRSNode *LeftChild;
  struct tagLCRSNode *RightSibling;
  ElementType Data;
} LCRSNode;

와 같이 데이터 필드와 Left Child, Right Sibling 두 개 포인터로 구성된다.

2-3. 노드 생성/소멸

//노드 생성
LCRSNode *LCRS_CreateNode(ElementType NewData) {
  LCRSNode *NewNode = (LCRSNode *)malloc(sizeof(LCRSNode));
  NewNode->LeftChild = NULL;
  NewNode->RightSibling = NULL;
  return NewNode;
}
//노드 소멸
void LCRS_DestroyNode(LCRSNode *Node) { free(Node); }

• 노드 생성: 자유 저장소에 LCRSNode 구조체의 크기만큼 메모리를 할당하고 매개변수 NewData를 Data에 저장한 후 노드 메모리 주소 반환
• 노드 소멸: 자유 저장소에서 할당했던 메모리만 해제하면 됨

2-4. 자식 노드 연결

void LCRS_AddChildNode(LCRSNode *Parent, LCRSNode *Child) {
//자식 노드가 있는지 검사
  if (Parent->LeftChild == NULL)
  //자식 노드가 없으면 왼쪽노드에 바로 저장
    Parent->LeftChild = Child;
  else {
  //자식 노드가 있는 경우
    LCRSNode *TempNode = Parent->LeftChild;
    while (TempNode->RightSibling != NULL)
    //RightSibling을 이용해 가장 오른쪽의 자식 노드를 찾고 Child를 가장 오른쪽 자식 노드의 RightSibling노드에 대입
      TempNode = TempNode->RightSibling;
    TempNode->RightSibling = Child;
  }
}

위 함수 과정을 통해 부모 노드는 자식을 하나 추가한다.

2-5. 트리 출력

void LCRS_PrintTree(LCRSNode *Node, int Depth) {
//들여쓰기
  for (int i = 0; i < Depth - 1; i++) {
    printf("   ");
    if (Depth > 0) //자식 노드 여부
      printf("+--");
      //노드 데이터 출력
    printf("%c\n", Node->Data);
    if (Node->LeftChild != NULL)
      LCRS_PrintTree(Node->LeftChild, Depth + 1);
    if (Node->RightSibling != NULL)
      LCRS_PrintTree(Node->RightSibling, Depth);
  }
}

구성된 트리를 출력하는 코드

3. 이진 트리

앞쪽 코드에서 구현한 트리는 노드의 자식 노드 개수에 제한이 없었으나 이진트리는 하나의 노드가 자식 노드를 2개까지만 가질 수 있다.

3-1. 이진 트리의 종류

• 포화 이진 트리
• 완전 이진 트리
• 이진 탐색 트리

포화 이진 트리

위 사진처럼 잎 노드를 제외한 모든 노드가 자식을 2개씩 갖고 있으면 포화 이진 트리라고 한다.

완전 이진 트리

모든 노드가 자식 2개를 갖고 있진 않아도 잎 노드들이 왼쪽부터 차곡차곡 채워져있으면 완전 이진 트리라고 한다.
B처럼 중간에 노드가 빈 트리는 완전 이진 트리가 아니다.

높이 균형 트리

뿌리 노드를 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 2이상 차이 나지 않는 이진 트리

완전 높이 균형 트리

왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 완전히 같은 이진 트리

• 트리의 성능과 모양: 가능한 완전한 모습으로 유지해야 높은 성능을 낼 수 있다. 이진 트리는 컴파일러나 검색과 같은 알고리즘의 뼈대가 되는 특별한 자료구조이므로, 이러한 모양이 중요하다.

3-4. 이진 탐색 트리

• 한마디로 탐색을 위한 이진 트리(이진 탐색)

이진 탐색은 배열에만 사용 가능하기 때문에 링크드 리스트에서 탐색을 위해서 이진 탐색 트리를 쓸 수 있다.

이진 탐색 트리의 특징

• 부모 노드 입장에서 왼쪽 자식 노드는 나보다 작고 오른쪽 자식 노드는 나보다 크다.

위와 같은 특징을 통해 탐색이 작동한다.
중앙 요소를 찾아 좌우의 대소르 비교하여 탐색 범위를 정하고 다시 중앙 요소를 찾아 좌우의 요소를 비교하는 것을 반복하여 탐색한다.

예시) 위 트리에서 5를 찾는다고 해보자.
5는 8보다 작으니 왼쪽 노드로, 다시 5는 3보다 크니 오른쪽 노드로 이동하는 것이다.