Tabla de saltos

En programación, se denomina tabla de saltos a un método eficiente de transferencia de control de programas saltando a otra parte del código mediante una tabla de instrucciones de salto. Este sistema es utilizado normalmente en la programación en ensamblador aunque estas tablas también pueden ser generadas por un compilador.

Una tabla de saltos consiste en una lista de instrucciones de salto incondicional que se ejecutan utilizando un offset creado mediante la multiplicación de un índice secuencial por la longitud de la instrucción (los bytes que ocupa en memoria cada instrucción). Se basa en el hecho de que las instrucciones de salto en código máquina tienen una longitud fija y pueden ser ejecutadas de forma extremadamente eficiente por la mayoría del hardware, además de ser más útil cuando se trabaja con datos sin formato fácilmente convertibles a valores secuenciales de índice. Dados estos datos, una tabla de saltos suele ser bastante eficiente, siguiendo normalmente estos pasos: validación opcional de los datos de entrada, transformación de los mismos en un offset dentro de la tabla de saltos (esto suele necesitar multiplicarlos o desplazarlos para su longitud coincida con las instrucciones de salto) y salto a una dirección obtenida a partir de la base de la tabla y el offset generado (esta operación suele incluir la suma del offset al registro del contador de programa).

Otro método de implementación de las tablas de saltos consiste en un array de direcciones desde las cuales es capturada la dirección necesaria para saltar. Este método suele implicar un menor tamaño del código y evita los saltos indirectos. Normalmente el método empleado para construir la tabla de saltos suele venir determinada por la arquitectura del procesador en el cual va a ser ejecutado el código.

Las tablas de saltos suelen usarse en el desarrollo de sistemas operativos. Tanto las llamadas al sistema como las funciones de biblioteca pueden ser referenciadas mediante un índice entero de una tabla de saltos. Con esto se consigue una mejora de la compatibilidad con las versiones siguientes: si el código de una función y la dirección de su destino de salto son modificados, solamente hará falta reajustar la instrucción de salto en la tabla, de este modo todas las aplicaciones compiladas utilizando código de la biblioteca y/o sistema operativo en cuestión no necesitan modificación alguna. Además, las llamadas a funciones por su número (el índice en la tabla) pueden ser útiles en ciertos programas.

Ejemplo

Un ejemplo simple del uso de tablas de saltos en ensamblador del microcontrolador PIC de 8 bits es:

    movf    INDEX, W     ; mover el valor de índice al registro W (registro de trabajo) desde la dirección de memoria INDEX
    addwf   PCL, F       ; sumarlo al registro de contador de programa (PCL). Cada instrucción PIC ocupa 1 byte
                        ; de modo que no es necesario realizar ninguna multiplicación. La mayoría de las arquitecturas transformarían
                        ; el índice de alguna manera antes de sumarlo al contador de programa

table                   ; esta etiqueta marca el comienzo de la tabla de salto
    goto    index_zero  ; cada una de estas instrucciones goto es un salto incondicional a diferentes secciones
    goto    index_one   ; del código
    goto    index_two
    goto    index_three

index_zero
    ; en esta parte se añadiría el código necesario para realizar cualquier acción que requiera que el valor de INDEX sea igual a cero
    return

index_one
...

Historia

El uso de las tablas de saltos y de la representación de los datos sin formato mediante índices era común en los inicios de la informática cuando las memorias eran caras y los procesadores lentos, siendo la representación compacta de los datos y la elección eficiente de las alternativas de almacenamiento dos factores importantes. También se ven con frecuencia en los sistemas empotrados modernos, donde suele hacer falta que el código quepa en espacios realmente mínimos y que a la vez opere de manera eficiente. La principal ventaja de tal conversión es que una vez que un valor ha sido convertido a un índice, puede ser utilizado para saltar o para recuperar algún dato de una tabla de búsqueda de forma eficiente y en cualquier momento sin necesidad de ser convertido de nuevo. Por ejemplo, se podría decir que, relativamente, hay pocos países en el mundo; de forma que éstos podrían ser representados de manera sencilla mediante un código de país en lugar de por una cadena de texto. Esto evita almacenamientos masivos de datos y por consiguientes grandes tiempos de procesado. Las comparaciones numéricas son significativamente más rápidas que las de cadenas de texto, y las búsquedas indexadas son también notablemente más rápidas que las de cadenas. Sin embargo, entre las desventajas se incluye la aparición de un nivel más de indirección. Esto es de poca importancia para los ordenadores, pero supone mayor complejidad de código y de datos para el programador. Además, tal y como se pudo ver en el Efecto 2000, esta aproximación al problema puede llevar posteriormente a problemas si los requisitos de espacio para el índice o la representación superan a los reservados para la tarea.

Enlaces externos

• HOWTO sobre la implementación de tablas de saltos en C (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última).

• Datos: Q495298
• Multimedia: Branch table / Q495298