Таблица переходов

Таблица переходов состоит из последовательности безусловных команд перехода, к одной из которых осуществляется переход по смещению, вычисляемому как индекс, умноженный на длину инструкции. Такой подход опирается на то, что машинные инструкции перехода имеют фиксированную длину и могут выполняться очень эффективно аппаратно; он особенно полезен при работе с «сырыми» значениями данных, которые можно напрямую преобразовать в индексы последовательности. Обычно процесс включает три шага:

1. При необходимости проверка входных данных. Этот шаг может быть пропущен, если значения полностью контролируются.
2. Преобразование входных данных в смещение в таблице переходов — посредством умножения или сдвига с учётом длины инструкции. При постоянных данных это действие может быть выполнено статически компилятором или вручную — без издержек исполнения.
3. Переход по адресу, полученному сложением базового адреса таблицы переходов и рассчитанного смещения. Обычно это реализуется как прибавление смещения к регистру счётчика команд, если соответствующая команда перехода не поддерживает работу с индекс-регистром. Итоговый адрес обычно указывает на одну из безусловных команд перехода или на инструкцию сразу за ними.

Пример на псевдокоде:

 // валидация x (например, преобразование к значениям 0 (некорректно), 1, 2, 3)
 y = x * 4;                  // умножение на длину инструкции перехода (например, 4 байта)
 goto next + y;              // переход в "таблицу" переходов
 // начало таблицы переходов
 next: goto codebad;         // x=0 (некорректно)
       goto codeone;         // x=1
       goto codetwo;         // x=2
 // остальная часть таблицы переходов
 codebad:                    // обработка некорректного ввода

Другой способ реализовать таблицу переходов — использовать массив указателей, из которого извлекается адрес нужной функции. Изначально эта техника называлась вектор передачи, а позднее — «таблица диспетчеризации» или «виртуальная таблица методов», но все термины обозначают одну и ту же идею. Использование массива указателей может сэкономить одну машинную инструкцию и избежать косвенного перехода.

Получившийся массив указателей на функции практически идентичен прямому «нитевидному коду» и концептуально схож с таблицей управления.

Выбор метода зависит от:

• архитектуры процессора, на котором выполняется код,
• особенностей компилируемого или интерпретируемого языка,
• необходимости позднего связывания.

Программисты часто возлагают принятие решения о необходимости создания таблицы переходов на компилятор, считая, что он сможет оптимально обработать известные значения ключей поиска. Это справедливо для оптимизирующих компиляторов в простых случаях с небольшим диапазоном значений. Однако компилятор не может иметь глубокого понимания контекста задачи и, например, диапазон ключей поиска 1, 2, 4, 6, 7, 20, 23, 40, 42, 50 и 1000 приведёт к созданию слишком большой разрежённой таблицы (>900 пустых ячеек) при незначительном выигрыше. В таких случаях хороший компилятор может отсортировать значения и сгенерировать код для бинарного поиска как альтернативу. Однако если приложение критично к быстродействию и объём памяти не очень ограничен, это не всегда лучшее решение^[2].

Тем не менее, небольшая модификация может свести задачу к двухэтапному решению:

• Сначала проверить ключ поиска на равенство 1000 и выполнить соответствующий переход.
• Дать компилятору «выбор» — сгенерировать таблицу переходов по ключам из диапазона 1–50.

Аналогичные приёмы применяют и для нескольких сжатых диапазонов ключей с большим разрывом между ними.

Хотя сейчас приём известен как таблица переходов, ранние компиляторы называли этот механизм «вычисляемым GoTo», по аналогии с соответствующей командой в компиляторах Fortran^[3][4]. Данная конструкция была впоследствии признана устаревшей в Fortran 90^[5].

Если нет очевидного целочисленного значения для использования в таблице переходов, индекс всё равно можно получить из ключа поиска арифметическими преобразованиями или, например, использовать номер строки базы данных либо позицию в массиве, найденную на этапе валидации.

В некоторых случаях для формирования индекса требуется хеш-таблица. Для однобайтовых входных значений можно использовать числовое значение байта («сырые данные») в двумерной схеме получения окончательного индекса без «дырок»:

1. Преобразовать символ в его числовой эквивалент (например, ASCII 'A' = 65 десятично, 0x41 шестнадцатерично)
2. Использовать полученное число как индекс в массиве из 256 двухбайтовых чисел, чтобы получить второй индекс (некорректные значения — 0, остальные — уникальные индексы)

Максимальный размер такого массива: (256 × 2) байта для 16-разрядных целых чисел. Если проверка не требуется и используются только заглавные буквы, это всего (26 × 2) = 52 байта.

Хотя таблицы переходов чаще всего используют только для изменения хода выполнения — перехода к определённой метке программы, эта техника может использоваться и в других целях. Например, её применяют для выбора точки входа в последовательности повторяющихся инструкций (при оптимизации циклов компиляторами или JIT-компиляторами, например, при разворачивании цикла).

Использование таблиц переходов и других методов кодирования «сырых» данных было распространено в ранней истории вычислительной техники, когда оперативная память была дорогой, процессоры — медленными, а значение имело компактное представление информации и эффективный выбор альтернатив. В наше время таблицы переходов по-прежнему используются:

• в программировании встраиваемых систем
• при разработке операционных систем: во многих ОС системные вызовы и функции библиотек ссылаются по целочисленному индексу в таблице переходов.
• в некоторых архитектурах ЭВМ, например IBM/360, для обработки прерываний

Пример использования таблицы переходов на ассемблере 8-битных микроконтроллеров Microchip PIC:

     movf    INDEX,W     ; загрузить значение индекса в рабочий регистр (W) из памяти
     addwf   PCL,F       ; прибавить это значение к счётчику команд. Каждая инструкция — 1 байт,
                         ; поэтому дополнительное умножение не нужно. 
                         ; В большинстве архитектур индекс предварительно преобразуют, прежде чем 
                         ; прибавить его к PC.

 table                   ; начало таблицы переходов
     goto    index_zero  ; все эти goto — безусловные переходы к реальному коду
     goto    index_one   
     goto    index_two
     goto    index_three

 index_zero
     ; Здесь код для случая, когда INDEX = 0
     return

 index_one
 ...

Примечание: этот код будет работать только если PCL < (table + index_last). Для этого часто используют директиву org. Если команда GOTO, как в PIC18F, занимает 2 байта, это ограничивает максимальное число записей < 128.

Другой пример, на этот раз демонстрирующий таблицу переходов именно как массив указателей, что позволяет обращаться к функциям вне текущей области видимости:

#include <stdio.h>
#include <stdlib.h>

typedef void (*Handler)(void);    /* указатель на функцию-обработчик */

/* Функции */
void func3 (void) { printf( "3\n" ); }
void func2 (void) { printf( "2\n" ); }
void func1 (void) { printf( "1\n" ); }
void func0 (void) { printf( "0\n" ); }

Handler jump_table[4] = {func0, func1, func2, func3};

int main (int argc, char **argv) {
    int value;

    /* Преобразовать первый аргумент в целое 0–3 (по модулю 4) */
    value = atoi(argv[1]) % 4;

    /* Вызвать соответствующую функцию (func0 — func3) */
    jump_table[value]();

    return 0;
}

В PL/I таблица переходов реализуется как массив меточных переменных. Их можно инициализировать необычным образом — с помощью индексируемых меток. Меточные переменные в PL/I это не только адрес инструкции, обычно они также хранят состояние блока кода. Если не использовать специальную инициализацию, аналогичное поведение можно смоделировать с помощью вызовов и массива «entry» переменных.

    declare lab (10) label;
    declare x fixed binary;
    goto lab(x);
  lab(1): /* код для варианта 1 */ ;
    ...
  lab(2): /* код для варианта 2 */ ;
    ...