O que é uma mesa de salto?

StackOverflow https://stackoverflow.com/questions/48017

  •  09-06-2019
  •  | 
  •  

Pergunta

Alguém pode explicar a mecânica de uma tabela de salto e por que ela seria necessária em sistemas embarcados?

Foi útil?

Solução

Uma tabela de salto pode ser uma matriz de ponteiros para funções ou uma matriz de instruções de salto em código de máquina.Se você tiver um conjunto relativamente estático de funções (como chamadas de sistema ou funções virtuais para uma classe), poderá criar esta tabela uma vez e chamar as funções usando um índice simples no array.Isso significaria recuperar o ponteiro e chamar uma função ou pular para o código de máquina dependendo do tipo de tabela usada.

Os benefícios de fazer isso na programação embarcada são:

  1. Os índices são mais eficientes em termos de memória do que códigos de máquina ou ponteiros, portanto, há potencial para economia de memória em ambientes restritos.
  2. Para qualquer função específica, o índice permanecerá estável e a alteração da função requer apenas a troca do ponteiro da função.

Isso custa um pouco de desempenho para acessar a tabela, mas não é pior do que qualquer outra chamada de função virtual.

Outras dicas

Uma tabela de salto, também conhecida como tabela de ramificação, é uma série de instruções, todas ramificando incondicionalmente para outro ponto no código.

Você pode pensar neles como uma instrução switch (ou select) onde todos os casos são preenchidos:

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

Observe que não há retorno - o código para o qual ele salta executará o retorno e retornará para onde quer que myjump tenha sido chamado.

Isso é útil para máquinas de estado onde você executa determinado código com base na variável de estado.Existem muitos, muitos outros usos, mas este é um dos principais usos.

É usado onde você não quer perder tempo mexendo na pilha e quer economizar espaço de código.É especialmente útil em manipuladores de interrupção onde a velocidade é extremamente importante e o periférico que causou a interrupção é conhecido apenas por uma única variável.Isto é semelhante à tabela vetorial em processadores com controladores de interrupção.

Um uso seria pegar um microcontrolador de US$ 0,60 e gerar um sinal composto (TV) para aplicações de vídeo.o micro não é poderoso - na verdade, é rápido o suficiente para escrever cada linha de varredura.Uma tabela de salto seria usada para desenhar caracteres, porque demoraria muito para carregar um bitmap da memória e usar um loop for() para remover o bitmap.Em vez disso, há um salto separado para a letra e a linha de varredura e, em seguida, cerca de 8 instruções que realmente gravam os dados diretamente na porta.

-Adão

Uma tabela de salto é descrita aqui, mas resumidamente, é uma série de endereços para os quais a CPU deve saltar com base em certas condições.Por exemplo, uma instrução switch C é frequentemente implementada como uma tabela de salto onde cada entrada de salto irá para um rótulo "caso" específico.

Em sistemas embarcados, onde o uso de memória é escasso, muitas construções são melhor atendidas usando uma tabela de salto em vez de métodos que consomem mais memória (como um enorme if-else-if).

Wikipédia resume muito bem:

Na programação de computadores, uma tabela de ramificação (às vezes conhecida como tabela de salto) é um termo usado para descrever um método eficiente de transferir o controle do programa (ramificação) para outra parte de um programa (ou um programa diferente que pode ter sido carregado dinamicamente) usando uma tabela de instruções de ramificação.A construção da tabela de filiais é comumente usada ao programar na linguagem de montagem, mas também pode ser gerada por um compilador.

...O uso de tabelas de filiais e outros dados brutos da codificação era comum nos primeiros dias da computação, quando a memória era cara, as CPUs eram mais lentas e a representação de dados compacta e a escolha eficiente de alternativas foram importantes.Atualmente, eles são comumente usados ​​no desenvolvimento de programação e sistema operacional incorporado.

Em outras palavras, é uma construção útil para usar quando seu sistema é extremamente limitado em memória e/ou CPU, como geralmente acontece em uma plataforma embarcada.

Da Wikipédia:

Na programação de computadores, uma tabela de ramificação (às vezes conhecida como tabela de salto) é um termo usado para descrever um método eficiente de transferir o controle do programa (ramificação) para outra parte de um programa (ou um programa diferente que pode ter sido carregado dinamicamente) usando uma tabela de instruções de ramificação.A construção da tabela de filiais é comumente usada ao programar na linguagem de montagem, mas também pode ser gerada por um compilador.

Uma tabela de ramificação consiste em uma lista serial de instruções incondicionais de ramificação que é ramificada para usar um deslocamento criado multiplicando um índice seqüencial pelo comprimento da instrução (o número de bytes na memória ocupado por cada instrução de ramificação).Ele utiliza o fato de que as instruções do código da máquina para ramificação têm um comprimento fixo e podem ser executadas extremamente eficientemente pela maioria dos hardware e é mais útil ao lidar com valores de dados brutos que podem ser facilmente convertidos em valores de índice seqüencial.Dados esses dados, uma tabela de ramificação pode ser extremamente eficiente;Geralmente consiste nas seguintes etapas:Opcionalmente validando os dados de entrada para garantir que sejam aceitáveis;Transformando os dados em um deslocamento na tabela de ramificação, isso geralmente envolve multiplicar ou mudar para levar em consideração o comprimento da instrução;e ramificação para um endereço composto pela base da tabela e do deslocamento gerado:Isso geralmente envolve uma adição do deslocamento no balcão do programa.

As tabelas de salto, mais conhecidas como tabela de ramificação, geralmente são usadas apenas pela máquina.

O compilador cria uma lista de todos os rótulos em um programa assembly e vincula todos os rótulos a um local de memória.Uma tabela de salto é praticamente um cartão de referência para onde uma função ou variável ou qualquer que seja o rótulo, está armazenado na memória.

Assim, à medida que uma função é executada, ao terminar, ela retorna ao local de memória anterior ou salta para a próxima função, etc.

E se você está falando sobre o que penso que é, você não precisa deles apenas em sistemas embarcados, mas em qualquer tipo de ambiente compilado/interpretado.

Brian Gianforcaro

Tabelas de salto são comumente (mas não exclusivamente) usadas em máquinas de estados finitos para torná-los orientados por dados.

Em vez de switch/case aninhado 

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

você pode criar um array 2D ou ponteiros de função e apenas chamar handleEvent[state][event]

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top