브랜치 테이블

Branch table

컴퓨터 프로그래밍에서 분기 테이블 또는 점프 테이블은 분기 또는 점프 명령을 사용하여 프로그램의 다른 부분(또는 동적으로 로드되었을 수 있는 다른 프로그램)으로 프로그램 제어(분기)를 전송하는 방법입니다.이것은 멀티웨이 브런치의 한 형태입니다.분기 테이블 구조는 어셈블리 언어로 프로그래밍할 때 일반적으로 사용되지만 컴파일러에 의해 생성될 수도 있습니다.특히 값이 [1]밀집되어 있는 최적화된 스위치 문을 구현하는 경우에는 더욱 그렇습니다.

표준 구현

분기 테이블은 무조건 분기 명령의 시리얼 리스트로 구성됩니다.이 시리얼 리스트는 순차 인덱스에 명령 길이(각 분기 명령이 차지하는 메모리 내의 바이트 수)를 곱한 오프셋을 사용하여 분기됩니다.분기용 기계 코드 명령이 고정 길이를 가지며 대부분의 하드웨어에서 매우 효율적으로 실행될 수 있다는 사실에 의존하며, 순차 인덱스 값으로 쉽게 변환할 수 있는 원시 데이터 값을 처리할 때 가장 유용합니다.이러한 데이터가 주어지면 분기 테이블은 매우 효율적일 수 있습니다.보통 다음 3단계로 구성됩니다.

  1. 선택적으로 입력 데이터를 검증하여 허용 가능한지 확인합니다(입력 값이 1바이트이고 256바이트 변환 테이블을 사용하여 아래 오프셋을 직접 얻는 경우 다음 단계의 일부로 비용 없이 수행될 수 있습니다).또, 입력의 값에 의문의 여지가 없는 경우는, 이 스텝을 생략할 수 있다.
  2. 데이터를 분기 테이블로 오프셋으로 변환합니다.여기에는 일반적으로 명령 길이를 고려하기 위해 곱하거나 이동(실효적으로 2의 거듭제곱)하는 작업이 포함됩니다.정적 변환 테이블을 사용하는 경우 실행 시간 비용 없이 수동으로 또는 컴파일러에 의해 이 곱셈을 수행할 수 있습니다.
  3. 분기 테이블의 기본 주소와 방금 생성된 오프셋으로 구성된 주소로 분기합니다.여기에는 때때로 프로그램 카운터 레지스터에 오프셋이 추가됩니다(일부 명령 집합에서 분기 명령이 추가 인덱스 레지스터를 허용하지 않는 한).이 최종 주소는 보통 일련의 무조건 분기 명령 또는 바로 뒤의 명령 중 하나를 가리킵니다(테이블에 1개의 엔트리를 저장).

다음 의사 코드는 이 개념을 나타내고 있습니다.

 ... 입증하다 x                    /* 값에 따라 x를 0(표준) 또는 1,2,3으로 변환합니다.*/        y = x * 4;                  /*에 분기 명령 길이를 곱합니다(예: 4 ) */        에 가다 다음 분. + y;              /* 분기 명령의 '테이블'에 분기 */  /* 브랜치 테이블의 시작 */  다음 분.: 에 가다 코드 불량;               /* x = 0 (표준) */        에 가다 코드원;               /* x = 1 * /        에 가다 코드;               /* x = 2 * /  ... 쉬다 의 분점 테이블  코드 불량:                          /* 무효 입력 처리 */

주소를 사용한 대체 구현

분기 테이블을 구현하는 또 다른 방법은 필요한 함수의 주소를 검색하는 포인터의 배열을 사용하는 것입니다.이 방법은 최근에는 "디스패치 테이블" 또는 "가상 메서드 테이블"과 같은 다른 이름으로도 알려져 있지만 기본적으로는 동일한 목적을 수행합니다.이 포인터 함수 방식은 하나의 기계 명령을 저장할 수 있으며 분기 명령 중 하나로 간접 점프하는 것을 방지합니다.

함수에 대한 포인터 목록은 직접 스레드 코드와 거의 동일하며 개념적으로 제어 테이블과 유사합니다.

브랜치 테이블을 실장하기 위해서 실제로 사용되는 방법은, 통상은 다음과 같습니다.

  • 코드가 실행되는 프로세서의 아키텍처,
  • 컴파일된 언어인지 통역된 언어인지에 관계없이
  • 지연 바인딩이 포함되어 있는지 여부를 확인합니다.

역사

메모리가 비싸고 CPU가 느리고 콤팩트한 데이터 표현과 효율적인 대체 선택이 중요했던 컴퓨팅 초기에는 브랜치 테이블 및 기타 원시 데이터 인코딩을 사용하는 것이 일반적이었습니다.오늘날에도 일반적으로 다음과 같은 용도로 사용됩니다.

이점

브랜치 테이블의 장점은 다음과 같습니다.

  • 콤팩트 코드 구조(반복 분기 연산 코드 제외)
  • reduced source 스테이트먼트(반복적)If스테이트먼트)
  • 리턴 코드를 개별적으로 테스트하는 요건 감소(콜 사이트에서 후속 프로그램 흐름을 결정하는 데 사용되는 경우)
  • 알고리즘과 코드 효율(데이터는 1회만 부호화하면 되고 브랜치테이블 코드는 보통 콤팩트)과 높은 데이터 압축률을 달성할 수 있는 가능성.예를 들어, 국가 이름을 국가 코드로 압축할 때, "중앙 아프리카 공화국"과 같은 문자열을 단일 인덱스로 압축할 수 있으므로, 특히 문자열이 여러 번 표시될 때 큰 절약 효과를 얻을 수 있습니다.또한 이와 동일한 인덱스를 사용하여 별도의 테이블에 있는 관련 데이터에 액세스할 수 있으므로 스토리지 요구사항이 더욱 줄어듭니다.

라이브러리 함수의 경우 정수로 참조할 수 있습니다.

  • 후속 소프트웨어 버전과의 호환성을 향상시킵니다.함수의 코드와 해당 진입점의 주소가 변경되면 분기 테이블의 분기 명령만 조정하면 됩니다. 라이브러리 또는 운영 체제에 대해 컴파일된 애플리케이션 소프트웨어는 수정할 필요가 없습니다.

또, 통상의 애플리케이션 프로그래밍에서는, 번호에 의한 콜 함수(테이블에의 인덱스)가 도움이 되는 경우가 있습니다.

단점들

  • 간접 참조의 보통 작은 공연을 발생한 여분의 수준,.
  • 일부 프로그래밍 언어에서 제한, 비록 보통 멀티 웨이 분기의 기본 개념을 구현하는 대체 방법이 있다.

예

는 8비트 부호 있는 Microchip 영상 처리 컴퓨터 언어를 어셈블리에 분기표의 간단한 예로 사용: 있다.

     movf    INDEX,W     ;이동은 지수 값은 W( 일하는)레지스터에 메모리에서.      addwf   적극 발사 통제,F       ;프로그램 카운터에 넣어라.각각의 영상 처리 컴퓨터 명령 하나의 바이트.                          ;그래서 필요가 없는 곱셈을 하는 것이다.                           ;대부분의 구조들 어떤 면에서 전에 지수를 변화시킬 것이다.                          ;프로그램 카운터에 추가하는.   테이블                   ;분기표 여기 이 레이블과 함께 시작한다.      에 가다    index_zero  ;각각의 이러한 goto의 명령어들은 아무런 조건이 없는 분야이다.      에 가다    인덱스_1   ;의 코드입니다.      에 가다    인덱스_2      에 가다    인덱스_3   index_zero      ; INDEX = 0일 때 필요한 모든 작업을 수행하기 위해 코드가 여기에 추가됩니다.      돌아가다   인덱스_1  ...

주의: 이 코드는 PCL < (표 + index_last)인 경우에만 작동합니다.이 조건을 확실히 하기 위해서, 「org」지령을 사용할 수 있습니다.GOTO(예를 들어 PIC18F)가 2바이트일 경우 테이블엔트리의 수는 128 이하로 제한됩니다.

C의 점프 테이블 예시

또 다른 간단한 예로, 이번에는 단순한 분기 테이블이 아닌 점프 테이블을 시연합니다.이를 통해 현재 활성 프로시저/기능 이외의 프로그램 블록을 다음과 같이 호출할 수 있습니다.

#실패하다 <stdio.h> #실패하다 <stdlib.h>  유형화된 무효 (*핸들러)(무효);    /* 핸들러 함수에 대한 포인터 */  /* 함수 */ 무효 기능하다 (무효) { 인쇄물( "3\n" ); } 무효 기능하다 (무효) { 인쇄물( "2\n" ); } 무효 기능 1 (무효) { 인쇄물( "1\n" ); } 무효 기능하다 (무효) { 인쇄물( "0\n" ); }  핸들러 점프 테이블[4] = {기능하다, 기능 1, 기능하다, 기능하다};  인트 주된 (인트 argc, 차 **argv) {     인트 가치;      /* 첫 번째 인수를 0-3 정수(계수)로 변환 */     가치 = 아토이(argv[1]) % 4;      /* 적절한 함수(func0 ~ func3)를 호출합니다.* /     점프 테이블[가치]();      돌아가다 0; }

PL/I에서의 점프 테이블 예시

PL/I는 레이블 변수의 배열로 점프 테이블을 구현합니다.이것들은, 첨자가 붙은 문 라벨을 사용해 비정상적으로 초기화할 수 있습니다.PL/I 레이블 변수는 단순히 문의 주소가 아니라 일반적으로 해당 변수가 속한 코드 블록 상태에 대한 추가 정보를 포함합니다.비정상적인 초기화가 없으면 콜 및 일련의 엔트리 변수를 사용하여 코드화할 수도 있습니다. 

declarate lab (10) label; declarate x fixed binary; goto lab (x); lab (1) : /* code for choice 1 * / ; ... lab (2) : /* code for choose 2 * / ; ...

컴파일러가 생성한 분기 테이블

프로그래머들은 종종 컴파일러가 알려진 검색 키에서 올바른 선택을 완벽하게 할 수 있다고 믿고 분기 테이블을 만들 것인지의 결정을 컴파일러에게 맡깁니다.이는 검색 키의 범위가 제한된 비교적 단순한 경우에 컴파일러를 최적화하는 데 해당될 수 있습니다.그러나 컴파일러는 인간만큼 지능적이지 않고 '콘텍스트'에 대한 깊은 지식이 없기 때문에 1, 2, 4, 6, 7, 20, 23, 40, 42, 50 및 1000과 같은 가능한 검색 키 정수 값의 범위가 매우 많은 빈 엔트리(900+)를 가진 분기 테이블을 생성할 수 있다고 믿습니다.최적화를 잘하는 컴파일러는 값을 미리 정렬하고 바이너리 찹 검색을 위한 코드를 생성할 수 있습니다.실제로, 애플리케이션의 「시간 크리티컬」이 매우 높고, 메모리 요건은 전혀 문제가 되지 [2]않는 경우가 있습니다.

단, 약간의 '상식'만 있으면 이 특정 케이스와 다른 많은 유사한 케이스가 매우 큰 비용 절감을 가능하게 하는 단순한 2단계 프로세스로 전환될 수 있습니다.결국 최종 선택은 컴파일러에게 맡겨지지만 '결정 사항'은 상당히 커집니다.

  • 먼저 검색 키=1000을 테스트하고 적절한 분기를 수행합니다.
  • 컴파일러가 나머지 검색 키(1-50)에 분기 테이블을 생성하도록 합니다.

유사한 라인에 따른 변동은 범위 간 간격이 큰 짧은 범위 세트가 두 개 있는 경우에 사용할 수 있습니다.

계산 이동

이 기술은 현재 '분기 테이블'로 알려져 있지만 초기 컴파일러 사용자들은 Fortran 시리즈의 [3][4]컴파일러에서 볼 수 있는 명령을 참조하여 구현을 '계산된 GoTo'라고 불렀다.이 명령어는 결국 Fortran 90에서 폐지되었습니다(소스 [5]레벨에서 SELECT & CASE 문장에 찬성).

분기 테이블에 대한 인덱스 작성

분기 테이블에 사용할 수 있는 명확한 정수 값이 없는 경우, 검색 키(또는 검색 키의 일부)에서 산술 변환을 통해 작성할 수도 있고, 단순히 데이터베이스의 행 번호 또는 키의 초기 검증 중에 발견된 검색 키를 포함하는 배열 내의 엔트리 번호일 수도 있습니다.

경우에 따라서는 인덱스를 형성하기 위해 해시 테이블이 필요할 수 있습니다.단, A-Z(또는 긴 키의 첫 번째 바이트)와 같은 단일 바이트 입력 값에 대해서는 바이트 자체의 내용(로우 데이터)을 2단계의 "삼차 해시 함수" 프로세스로 사용하여 공백이 0인 분기 테이블의 최종 인덱스를 얻을 수 있다.

  1. 원시 데이터 문자를 해당 수치로 변환합니다(예: ASCII 'A' ==> 65진수, 0x41 16진수).
  2. 숫자 정수 값을 256바이트 배열의 인덱스로 사용하여 두 번째 인덱스(유효하지 않은 항목 0, 간격을 나타냄, 그렇지 않으면 1, 2, 3 등)를 얻습니다.

어레이는 (256 x 2)바이트 이하입니다.가능한 모든 16비트 부호 없는 (짧은) 정수를 유지합니다.검증이 필요하지 않고 대문자만 사용하는 경우 어레이 크기는 (26 x 2) = 52바이트 정도로 작을 수 있습니다.

기타 기술 사용

브랜치 테이블을 사용한 브랜치 기법은 프로그램 플로우의 변경(무조건 브랜치)만을 목적으로 하는 경우가 가장 많지만, 같은 기법은 다른 목적으로도 사용할 수 있습니다.예를 들어 드롭 스루가 표준이고 의도적인 일련의 반복 명령에서 시작점을 선택하는 데 사용할 수 있습니다.예를 들어 컴파일러 또는 JIT 컴파일러를 루프 언롤링으로 최적화하여 사용할 수 있습니다.

「 」를 참조해 주세요.

  • 지연 바인딩에 사용되는 다른 이름으로 분기 테이블을 디스패치합니다.
  • 분기 테이블에서 사용되는 대로 작동하는 주소의 함수 포인터 배열
  • 간접 분기
  • 일치하는 항목의 배열 룩업 테이블(경우에 따라 사전 계산된 결과를 포함)
  • 분기 테이블을 생성할 수 있는 고급 언어 조건문 전환
  • 디스패치를 위한 포인터가 동적으로 할당된 다른 이름으로 브랜치 테이블을 테이블로 하는 가상 메서드(디스패치 테이블 참조)

레퍼런스

  1. ^ Page, Daniel (2009). A Practical Introduction to Computer Architecture. Springer Science & Business Media. p. 479. ISBN 9781848822559.
  2. ^ Jones, Nigel (1 May 1999). "How to Create Jump Tables via Function Pointer Arrays in C and C++". Archived from the original on 12 February 2012. Retrieved 12 July 2008.
  3. ^ "Alternate Entry Points (ENTRY)". Using and Porting GNU Fortran. Free Software Foundation. 2001-06-07. Retrieved 2016-11-25.
  4. ^ Thomas, R.E. (1976-04-29). "FORTRAN Compilers and Loaders". ACD: Engineering Paper No 42. ACD. Retrieved 2009-04-10.
  5. ^ "A Brief Introduction to Fortran 90". Decremental/Deprecated/Redundant Features. Retrieved 2009-04-10.

외부 링크

Wikimedia Commons에는 Branch 테이블과 관련된 미디어가 있습니다.
  • [1] IBM S/360용 Wikibooks 분기 테이블의 예
  • [2] C/C++의 함수 포인터 배열을 통한 점프 테이블의 예와 인수
  • [3] IF/ELSE가 아닌 C의 'Switch/Case' 브랜치테이블에 의해 생성되는 코드 예.
  • [4] 구조 크기를 2의 거듭제곱으로 나눌 수 있는 경우 배열 인덱싱을 위해 생성되는 코드 예제입니다.
  • [5] Nigel Jones의 "기능에 대한 포인터"