Что такое прыжковый стол?

Question

Может кто-нибудь объяснить механику таблицы переходов и зачем она нужна во встроенных системах?

Answer 1

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

Преимущества выполнения этого во встроенном программировании:

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

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

Answer 2

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

Вы можете рассматривать их как оператор переключения (или выбора), в котором заполняются все дела:

MyJump(int c)
{
   switch(state)
   {
      case 0:
         goto func0label;
      case 1:
         goto func1label;
      case 2:
         goto func2label;
   }
}

Обратите внимание, что возврата нет - код, на который он переходит, выполнит возврат и вернется туда, куда был вызван myjump.

Это полезно для конечных автоматов, где вы выполняете определенный код на основе переменной состояния. Есть много, много других применений, но это одно из основных применений.

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

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

-Adam

Answer 3

Википедия довольно хорошо подводит итог:

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

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

Другими словами, это полезная конструкция для использования, когда ваша система сильно ограничена в памяти и / или ЦП, как это часто бывает во встроенной платформе.

Answer 4

Таблица переходов описана здесь , но вкратце, это массив адресов, к которым ЦП должен переходить в зависимости от определенных условий. Например, оператор C switch часто реализуется как таблица переходов, где каждая запись перехода будет идти к определенной метке «case».

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

Answer 5

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

Вместо вложенного переключателя / корпуса

  switch (state)
     case A:
       switch (event):
         case e1: ....
         case e2: ....
     case B:
       switch (event):
         case e3: ....
         case e1: ....

вы можете создать 2d массив или указатели на функции и просто вызвать handleEvent[state][event]

Answer 6

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

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

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

И если вы говорите о том, кем я вас считаю, они вам нужны не только во встроенных системах, но и в любой компилированной / интерпретируемой среде.

Брайан Джанфоркаро

Answer 7

Из Википедии :

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

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