Что такое таблица прыжков?

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

In computer programming, a branch table (sometimes known as a jump table) is a term used to describe an efficient method of transferring program control (branching) to another part of a program (or a different program that may have been dynamically loaded) using a table of branch instructions. The branch table construction is commonly used when programming in assembly language but may also be generated by a compiler.

A branch table consists of a serial list of unconditional branch instructions that is branched into using an offset created by multiplying a sequential index by the instruction length (the number of bytes in memory occupied by each branch instruction). It makes use of the fact that machine code instructions for branching have a fixed length and can be executed extremely efficiently by most hardware, and is most useful when dealing with raw data values that may be easily converted to sequential index values. Given such data, a branch table can be extremely efficient; it usually consists of the following steps: optionally validating the input data to ensure it is acceptable; transforming the data into an offset into the branch table, this usually involves multiplying or shifting it to take into account the instruction length; and branching to an address made up of the base of the table and the generated offset: this often involves an addition of the offset onto the program counter register.

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

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

Википедия довольно хорошо резюмирует:

In computer programming, a branch table (sometimes known as a jump table) is a term used to describe an efficient method of transferring program control (branching) to another part of a program (or a different program that may have been dynamically loaded) using a table of branch instructions. The branch table construction is commonly used when programming in assembly language but may also be generated by a compiler.

... Use of branch tables and other raw data encoding was common in the early days of computing when memory was expensive, CPUs were slower and compact data representation and efficient choice of alternatives were important. Nowadays, they are commonly used in embedded programming and operating system development.

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

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

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

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

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

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

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

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

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

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

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

Вы можете думать о них как о выражении switch (или select), в котором заполнены все кейсы:

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

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

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

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

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

-Адам

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

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

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

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