분기 테이블

컴퓨터 프로그래밍에서 분기 테이블() 또는 점프 테이블()은 분기나 점프 명령어들을 이용해서, 프로그램의 제어를 프로그램의 다른 부분으로 옮기는 방법이다. 이것은 다방향 분기의 형태이다. 분기 테이블 구조는 주로 Switch 문을 구현하는, 컴파일러에 의해 생성된 어셈블리어 프로그램에 사용된다.
전형적인 구현.
분기 테이블은 명령어 길이와 연속된 인덱스를 곱함으로써 생성된 오프셋을 사용함으로써 분기된, 무조건적 분기 명령어들의 연속적인 리스트로 이루어져 있다. 이것은 분기를 위한 기계어 명령어가 고정된 길이를 갖고 있으며, 대부분의 하드웨어에 의해 매우 효율적으로 실행되고, 쉽게 연속적 지수 값으로 전환될 수 있는 원시 자료 값을 다루는데 매우 유용하다. 이러한 주어진 값으로, 분기 테이블은 매우 효과적이 될 수 있다. 이것은 보통 3단계로 이루어진다.
아래의 가상 코드는 개념을 설명한다.
 ... validate x /* transform x to 0 (invalid) or 1,2,3, according to value..) */
 y = x*4; /* multiply by branch instruction length (e.g. 4 ) */
 goto next(y); /* branch into 'table' of branch instructions */
 /* start of branch table */
 next: goto codebad; /* x= 0 (invalid) */
 goto codeone; /* x= 1 */
 goto codetwo; /* x= 2 */
 ... rest of branch table
 codebad: /* deal with invalid input */
주소들을 사용한 대체 구현.
분기 테이블을 구현하는 다른 방법으로, 요구되는 검색된 함수의 주소들에서의 포인터들의 정렬로 가능하다. 이 방법은 또한 최근들어 "디스패치 테이블" 또는 "가상 메소드 테이블"로 불리기도 하지만 어쨌든 같은 행돌을 수행한다. 이 포인터 함수 방식은 하나의 기계어를 줄일 수 있으며, 간접 점프를 피할 수 있다.
함수들을 가리키는 포인터들의 결과 리스트는 직접적인 스레디드 코드와 거의 비슷하며, 제어 테이블과도 개념적으로 비슷하다.
분기 테이블을 구현하는데 사용되는 실제 방식은 아래에 기반한다.
역사.
분기 테이블과 원시 자료의 사용은 메모리가 비싸고 CPU가 느리며, 압축된 데이터 표현과 대안의 효율적인 선택이 중요했던, 컴퓨터의 초기 시절에는 흔했다. 요즘은 이것들이 보통 다음과 같이 사용된다.
장점.
분기 테이블의 장점은 아래와 같다.
정수에 의해 참조되는 라이브러리 함수들
게다가, 평범한 애플리케이션 프로그래밍 시 번호(테이블의 인덱스)에 의한 함수 호출이 유용할 때가 있다.
예시.
8비트 PIC 마이크로컨트롤러 어셈블리어에서의 사용
 movf INDEX,W ; move the index value into the W (working) register from memory
 addwf PCL,F ; add it to the program counter. each PIC instruction is one byte
 ; so there is no need to perform any multiplication.
 ; Most architectures will transform the index in some way before
 ; adding it to the program counter
 table ; the branch table begins here with this label
 goto index_zero ; each of these goto instructions is an unconditional branch
 goto index_one ; of code
 goto index_two
 goto index_three
 index_zero
 ; code is added here to perform whatever action is required when INDEX = zero
 return
 index_one
C에서의 점프 테이블 예시.
아래는 단지 분기 테이블이 아니라 점프 테이블을 보여준다. 이것은 프로그램이 현재의 프로시저/함수 외부에서 호출되는 것을 막는다.
typedef void (*Handler)(void); /* A pointer to a handler function */
/* The functions */
Handler jump_table[4] = {func0, func1, func2, func3};
int main (int argc, char **argv) {
 int value;
 /* Convert first argument to 0-3 integer (modulus) */
 value = ((atoi(argv[1]) % 4) + 4) % 4;
 /* Call appropriate function (func0 thru func3) */
 jump_table[value]();
 return 0;
컴파일러에 의해 생성된 분기 테이블.
프로그래머들은 흔히 컴파일러가 검색 키들을 통해 정확한 선택을 할 수 있다고 믿으며, 분기 테이블을 만들어야 할지를 컴파일러에게 맡긴다. 이것은 검색키의 범위가 제한되어 있을 때 최적화하는 컴파일러에게 쉬운 일이라는 점에서 사실이다. 그러나 컴파일러는 인간만큼 똑똑하지 않으며, 문맥에 대한 깊은 지식이 없다. 예를 들면, 검색키 정수 값이 1, 2, 4, 6, 7, 20, 23, 40, 42, 50 &amp; 1000일 경우에 생성되는 분기 테이블은 900개 이상의 빈 엔트리가 포함된 매우 큰고 이점이 사라진 형태가 된다. 물론 이 애플리케이션이 매우 시간 중시적이고 메모리 요구에는 관심이 없을 수 있다.
그러나 작은 상식이 이러한 상황을 바꿔줄 수 있다. 결정을 아래와 같이 지원하는 것이다. (물론 궁극적인 선택은 컴파일러가 한다.)
위와 비슷한 형식으로 차이가 큰 범위에 사용할 수 있다.
분기 테이블을 위한 인덱스 생성.
분기 테이블에서의 사용 가능한 명확한 정수 값이 있는 것은 아니지만, 검색키는 몇몇 산술 변환이나 간단히 데이터베이스의 원시 번호 또는 검색키들을 포함하는 배열의 엔트리 번호 등으로 생성된다.
해시 테이블도 몇몇 경우에 사용되기도 한다.
기법의 다른 사용들.
비록 분기 테이블을 사용하는 분기 기법은 단지 프로그램 흐름 변경을 위해 사용되지만, 이 기법은 다른 목적으로 사용될 수도 있다. 예를 들면 컴파일러 최적화나 루프 풀기에 대한 JIT 컴파일러에서 사용되기도 한다.