이제 지금까지 배운 내용을 응용해보자 어떤 세 점이 주어질 때, 그 세 점을 삼각형으로 하는 평면을 결정할 수 있다. 임의 지점에서부터 주어진 방향으로 광선을 쏘았을 때, 그 광선이 삼각형에 맞았는지 어떻게 알 수 있을까? 이는 아래와 같은 방법으로 계산할 수 있다. 1. 평면식을 구한다. (세 점으로부터 둘레 벡터 구하고, 둘레벡터의 외적과 세 점중 하나로 평면식 결정) 2. 광선의 직선식을 구한다. 3. 광선의 직선식과 평면식의 교점을 구한다. 4. 교점이 삼각형 내부에 있는지 체크한다. (각 삼각형 선분마다, 그 선분을 포함하고 삼각형평면에 수직인 평면식을 짜고, 그 평면식 위의 임의 점 A 에서 평면식의 법선벡터를 내적했을 때 양수임이 모든 선분에서 확인되면 내부에 있다고 볼 수 있다.) 내적의 ..
지난 글에서는 연결리스트를 이용해 스택과 큐를 구현하였다. 이번 글에서는 연결리스트를 이용하는 과정에서 new(), free() 기능을 사용했는데, 이 기능을 직접 구현해본다. 사실 직접 구현이라고 해서 나도 처음엔 메모리를 직접 다루는 거창한 걸 기대했는데, 그런건 아니다. 그냥 배열을 이용해서 전체 memory pool 을 세팅해두고, 그 세팅된 pool 내 메모리를 주고 받고 하는 방식이다. 메모리 풀은 연결리스트 노드의 데이터 형태로 배열에 세팅해두고, 이를 스택처럼 활용하여 메모리를 주고 받는다. 메모리 풀은 이런 구조로 존재한다. 만약 new 함수로 메모리 공간을 요청하면 top이 가리키는 노드를 제공해준다. 제공을 마친 모습이다. 제공된 메모리는 연결리스트에서 자유롭게 Item 부분에도 값을..
지난 글에서는 분기 최적화에 대해 정리하였다. 분기 최적화를 하는 방법에는 from before, from after, annulled branch 3가지가 있었다. from before 은 분기 명령어 이전에 실행되는 명령어를 가져오는 것으로, 보통 mov 명령어를 이용한 레지스터 값 세팅을 가져올 수 있다. from after 은 분기 명령어 이후에 실행되는 명령어를 가져오는 것으로, 보통 분기 이후 실행되는 명령어 중, 분기 여부에 상관없이 반드시 실행되는 명령어를 당겨올 수 있었다. annulled branch 는 분기를 할 때는 delay slot 명령어를 실행하고, 분기를 하지 않을 때는 delay slot 명령어를 실행하지 않는 분기 명령어로서, 반드시 분기 후 첫 명령어를 delay slo..
지난 글에서는 직선과 점, 직선과 직선, 점과 평면 사이 최단 거리를 구하는 방법을 정리하였다. 직선과 점에서는 직선의 법선벡터를 방향벡터로 하고, 직선밖의 점을 지나는 새로운 직선식을 세운다음, 기존 직선과 교점을 구해 거리를 구하거나, 점의 위치를 원점으로 평행이동시키고, 이동된 직선의 방정식의 법선벡터를 정규화하여 최단 거리를 구할 수도 있었다. 직선과 직선의 경우, 두 직선의 외적을 이용해 한 직선을 지나는 평면식을 세우고, 그 평면식과 다른 직선 위 임의점 사이 최단 거리를 구하였다. 점과 평면사이 최단거리의 경우, 점의 위치를 원점으로 옮기고, 이동된 평면의 방정식의 법선벡터를 정규화하여 최단거리를 구하였다. 이번 글에서는 특정 평면으로 입사된 벡터의 반사벡터를 구하는 방법을 정리하고자 한다...
지난 글에서 Linked List 의 개념과 그 구현에 대해 정리하였다. 이번에는 Array 로 구현했던 Stack 과 Queue를 Linked List 로 구현하는 과정을 살펴보고자 한다. Stack With Linked List 스택을 연결리스트로 구현해보자. 연결리스트에서 데이터를 중간에 삽입할 때는 이전 노드의 주소를 알아야 하기 때문에 아주 복잡했다. 데이터를 맨 처음에 삽입하는 것이 아주 간단하기 때문에, 스택의 데이터 삽입과 삭제가 빈번히 일어나는 top 을 연결리스트의 첫 head로 설정하자. 그림으로 나타내면 이렇게 나타난다. 스택에 데이터를 추가하면 추가된 데이터를 top 이 가리키고, 추가된 데이터가 기존 데이터를 가리키는 방식으로 구현하면 된다. 스택에서 데이터를 뺄 때는 top 의..
지난 글에서는 Branch Delay Slot 이 발생하는 이유를 파이프라이닝 과정을 따라가보며 살펴보았다. 요약해보면, Branching 여부는 E 단계에서 결정되기 때문에, E 단계에서 분기를 하더라도, E 단계 시점의 F 단계에 있던 명령어가 파이프라인에 남아 계속 실행되는 문제 때문에 이를 비워둠으로써 Delay Slot 이 발생하였다. 이번 글에서는 이렇게 Delay Slot 을 비워두지 않고, 다른 명령어로 채워 활용하는 방법. Delay Slot Optimization 에 대해 정리해보고자 한다. 최적화 개요 그렇다면 어떻게 분기 명령어를 쓴 직후, nop 를 넣지 않고 최적화를 할 수 있을까? nop 대신 분기에 (전체 코드 실행에) 영향을 주지 않는 다른 명령어를 넣으면 된다. 즉, de..
지난 글에서는 분기 명령어의 종류와 사용 방법, 그리고 예제들을 살펴보았다. 간단하게 정리하면 분기 명령어 중 조건 분기와 무조건 분기는 CC 코드를 이용해 분기 명령어에 적힌 조건을 파악하기 때문에, 명령어를 실행시키기 전에 반드시 조건식의 CC 코드를 발생시켜 두어야 했다. 그리고 분기 명령어의 실행 직후에는 Branch Delay Slot 이 반드시 발생하였다. 이번 글에서는 Branch Delay Slot 이 발생하는 이유를 실제 명령어의 실행 파이프라인을 따라가보며 정리해보고자 한다. 다음과 같은 명령어를 순차적으로 실행시킨다고 하자. ble next_r - A add R1, R2, R3 - B mov 130, R4 - C ... next_r: - D add R3, R4, R1 set str, ..
지난 글까지 산술 명령어, 논리 명령어, 비트 명령어를 정리하였다. 이번 글부터는 분기 명령어에 대해 정리하고자 한다. Flow Control In Assembly 흐름제어는 한다면 코드가 위에서부터 아래로 한 줄씩 실행되는 것이 아니라, 특정 위치로 건너가 실행하도록 설정하는 것을 의미한다. C언어에서 흐름 제어 키워드를 생각을 해보면 아래와 같은 키워드가 있다. 반복 : for, while, do while 분기 : switch, if, else 기타 : goto, 함수 그리고 강제로 이동하는 goto 문을 제외하면, 건너 뛸지 말지 여부를 결정하기 위한 '조건 체크'가 반드시 필요하다. 조건 체크는 비교 연산자를 사용한다. (!=, ==, , ...등등) 어셈블리의 관점에서 흐름 제어도 마찬가지이다..
지난 글에서는 논리연산 명령어에 대해 정리하였다. 논리 연산 명령어에는 and, or, xor 과 andn orn xnor 이 있었고, 각 명령어마다 cc 를 생성하는 명령어가 따로 있었다. 논리 연산에서 CC 는 N, V 만 사용한다. 합성 명령어로는 not, clr, tst, mov 와 같은 명령어가 있었다. not A = xnor A, %g0, A 로서 특정 비트와 1 의 xor 연산을 통해 0을 1로 1을 0으로 바꾸어 주었다. clr 은 0 과 and 연산을 함으로서 모든 비트를 0으로 초기화 시키고, tst 는 0과 orcc 를 한 값을 %g0 에 저장시키므로서 연산 결과를 버리고 cc 만을 보는 명령어였다. mov A, B 는 or %g0, A, B 연산으로 대체되어 A 를 그대로 B 에 넣..
지난 글까지 직선과 평면의 방정식을 내적과 외적을 이용해 구하는 과정을 정리하였다. 이번 글에서는 직선과 점 사이 최단거리, 직선과 직선 사이 최단거리, 점과 평면사이 최단거리를 구하는 방법을 정리한다. (직선과 평면의 경우, 최단거리가 존재하려면 반드시 직선과 평면이 평행해야하는데, 그 경우 직선 위 임의 점에서 평면과 최단거리를 구하면 되기 때문에 점과 평면사이 최단거리를 구하는 것과 같다.) 직선과 점 사이 최단 거리 우선 2차원에서 직선과 점 사이 최단 거리를 구하는 방법을 생각해보자 직선 밖의 점과 직선 사이의 최단 거리는 그 점에서 직선으로 수선의 발을 내렸을 때, 수선의 발과 해당 점 사이의 거리이다. 직선의 방정식을 내적을 이용하여 표현하면, 직선의 법선벡터를 쉽게 구할 수 있다. 이를 이..
