Из Википедии, бесплатной энциклопедии
  (Перенаправлено из таблицы переходов )
Перейти к навигации Перейти к поиску

В компьютерном программировании , таблица ветви или таблица скачка представляет собой способ передачи управления программы ( ветвление ) в другую часть программы (или другой программы , которые могут быть динамически загружаемой) с использованием таблицы ветвления или прыгать инструкции . Это форма разветвленной ветки . Конструкция таблицы переходов обычно используется при программировании на языке ассемблера, но также может создаваться компиляторами , особенно при реализации оптимизированных операторов переключения , значения которых плотно упакованы вместе. [1]

Типовая реализация [ править ]

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

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

Следующий псевдокод иллюстрирует концепцию

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

Альтернативная реализация с использованием адресов [ править ]

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

Результирующий список указателей на функции почти идентичен прямому многопоточному коду и концептуально аналогичен управляющей таблице .

Фактический метод, используемый для реализации таблицы переходов, обычно основан на:

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

История [ править ]

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

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

Преимущества [ править ]

К преимуществам отраслевых таблиц можно отнести:

  • компактная структура кода (несмотря на повторяющиеся коды операций ветвления)
  • сокращенные исходные заявления (по сравнению с повторяющимися Ifзаявлениями)
  • снижение требований к индивидуальному тестированию кодов возврата (если используется на месте вызова для определения последующего выполнения программы )
  • Алгоритмическая эффективность и эффективность кода (данные необходимо кодировать только один раз, а код таблицы переходов обычно компактный), а также возможность достижения высоких степеней сжатия данных . Например, при сжатии названий стран в коды стран строка, такая как «Центральноафриканская Республика», может быть сжата до единого индекса, что дает значительную экономию, особенно когда строка встречается много раз. Кроме того, этот же индекс можно использовать для доступа к связанным данным в отдельных таблицах, что дополнительно снижает требования к хранению.

Для библиотечных функций, где на них можно ссылаться целым числом :

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

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

Недостатки [ править ]

  • Дополнительный уровень косвенности , который обычно незначительно снижает производительность.
  • Ограничения в некоторых языках программирования, хотя обычно существуют альтернативные способы реализации базовой концепции многостороннего ветвления.

Пример [ править ]

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

 movf  INDEX , W  ; Переместите значение индекса в регистр W (рабочий) из памяти  addwf  PCL , F  ; добавить его в счетчик программы. Каждая инструкция PIC - это один байт  ; поэтому нет необходимости производить какое-либо умножение.  ; Большинство архитектур раньше каким-либо образом преобразуют индекс  ; добавляя его к счетчику программы. стол  ; Таблица  переходов  начинается здесь с этой метки goto index_zero  ; каждая из этих инструкций goto является безусловным  переходом goto  index_one  ; кода.  goto  index_two  goto  index_three index_zero  ; Сюда добавляется код для выполнения любых действий, которые требуются, когда INDEX = нулевой  возврат. index_one  ...

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

Пример таблицы переходов на C [ править ]

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

#include  <stdio.h>#include  <stdlib.h>typedef  void  ( * Обработчик ) ( void );  / * Указатель на функцию-обработчик * // * Функции * / void  func3  ( void )  {  printf (  "3 \ n "  );  } void  func2  ( void )  {  printf (  "2 \ п "  );  } void  func1  ( void )  {  printf (  "1 \ п "  );  } void  func0  ( void )  {  printf (  "0 \ п "  );  }Обработчик  jump_table [ 4 ]  =  { func0 ,  func1 ,  func2 ,  func3 };int  main  ( int  argc ,  char  ** argv )  {  значение int  ; / * Преобразование первого аргумента в целое число от 0 до 3 (модуль) * /  value  =  atoi ( argv [ 1 ])  %  4 ; / * Вызов соответствующей функции (func0 thru func3) * /  jump_table [ value ] (); возврат  0 ; }

Пример таблицы переходов в PL / I [ править ]

PL / I реализует таблицу переходов как массив переменных-меток . Они могут быть инициализированы необычным способом с помощью подписанной метки оператора. Переменные метки PL / I - это не просто адрес оператора, но обычно содержат дополнительную информацию о состоянии блока кода, которому они принадлежат. Без необычной инициализации это также можно было бы закодировать с помощью вызовов и массива входных переменных.

 объявить ярлык lab (10); объявить фиксированный двоичный файл x; goto lab (x); lab (1): / * код для выбора 1 * /; ... lab (2): / * код для варианта 2 * /; ...

Сгенерированные компилятором таблицы ветвлений [ править ]

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

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

  • Сначала проверьте ключ поиска = 1000 и выполните соответствующую ветвь.
  • Позвольте компилятору «выбирать» для создания таблицы ветвлений по оставшимся ключам поиска (1-50).

Вариации по аналогичным направлениям могут использоваться в случаях, когда есть два набора коротких диапазонов с большим промежутком между диапазонами.

Вычисленный GoTo [ править ]

Хотя этот метод сейчас известен как «таблицы ветвлений», первые пользователи компиляторов называли реализацию « вычисленным GoTo », ссылаясь на инструкцию, содержащуюся в компиляторах серии Fortran. [3] [4] В конце концов инструкция была объявлена ​​устаревшей в Fortran 90 (в пользу операторов SELECT и CASE на уровне исходного кода). [5]

Создание индекса для таблицы ветвей [ править ]

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

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

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

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

Другое использование техники [ править ]

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

См. Также [ править ]

  • Таблица отправки - таблица ветвей с другим именем, используемым для позднего связывания.
  • Массивы указателей на функции адресов к функциям, используемые в таблицах переходов
  • Косвенная ветвь
  • Таблица поиска - массив элементов для сопоставления, иногда содержащий предварительно рассчитанные результаты.
  • Оператор переключения - условный оператор на языке высокого уровня, который может создавать таблицу ветвлений.
  • Таблица виртуальных методов - таблица ветвей с другим именем с динамически назначаемыми указателями для диспетчеризации (см. Таблицу диспетчеризации)

Ссылки [ править ]

  1. ^ Пейдж, Дэниел (2009). Практическое введение в компьютерную архитектуру . Springer Science & Business Media. п. 479. ISBN 9781848822559.
  2. ↑ Джонс, Найджел (1 мая 1999 г.). «Как создавать таблицы переходов с помощью массивов указателей функций в C и C ++» . Архивировано из оригинального 12 февраля 2012 года . Проверено 12 июля 2008 года .
  3. ^ «Альтернативные точки входа (ВХОД)» . Использование и перенос GNU Fortran . Фонд свободного программного обеспечения. 2001-06-07 . Проверено 25 ноября 2016 .
  4. ^ Thomas, RE (1976-04-29). "Компиляторы и загрузчики FORTRAN" . ACD: Технический документ № 42 . ACD . Проверено 10 апреля 2009 .
  5. ^ «Краткое введение в Fortran 90» . Уменьшенные / устаревшие / избыточные функции . Проверено 10 апреля 2009 .

Внешние ссылки [ править ]

  • [1] Пример таблицы переходов в Викиучебнике для IBM S / 360
  • [2] Примеры и аргументы для таблиц перехода через массивы указателей функций в C / C ++
  • [3] Пример кода, сгенерированный таблицей ветвления 'Switch / Case' в C, по сравнению с IF / ELSE.
  • [4] Пример кода, созданного для индексации массива, если размер структуры делится на степень 2 или иначе.
  • [5] «Массивы указателей на функции» Найджела Джонса.