Tabelas de Consulta (LUTs): Acesso Rápido a Dados via Pré-Computação
Uma **Tabela de Consulta (LUT)** é uma estrutura de dados que substitui **computação em tempo de execução** por **acesso à memória**. Ela mapeia chaves de entrada para valores de saída pré-computados, trocando armazenamento por velocidade e determinismo.
Conceito Central
Entrada (Chave) ──► [ Memória LUT ] ──► Saída (Valor) Índice Array Dados
- Complexidade Tempo: O(1) — Leitura única memória (índice array) ou busca hash.
- Complexidade Espaço: O(N) — N entradas armazenadas.
- Determinismo: Latência fixa (crítico para tempo real / RTOS hard).
Formas de Implementação
| Forma | Estrutura | Caso Uso |
|---|
| Array / Vetor 1D | saida = tabela[entrada] | Mapeamento direto: Sen(x), Correção Gama, Linearização Termopar, CRC8. |
| Array 2D / Multi-D | saida = tabela[x][y] | Interpolação bilinear, Máquinas estados, Tabelas verdade (portas lógicas). |
| Hash Map / Dicionário | saida = dict[chave] | Chaves esparsas, Chaves não-inteiras (strings, enums), Tabelas dinâmicas. |
| Bloco RAM FPGA/ASIC | Blocos memória hardware | DSP: Sen/Cos, CORDIC, Coeficientes FIR, Conversão espaço cor (RGB→YUV). Latência zero. |
| Memória Textura (GPU) | Texturas 1D/2D/3D cacheadas | Gráficos: Filtragem, Mipmaps. Computação: LUTs interpoladas. |
Aplicações Clássicas
- Transcendentes: sen, cos, log, exp, sqrt — onde instrução HW ausente ou lenta (MCU 8-bit, soft-core FPGA).
- Linearização: Termopar (Tipo K, J, T), RTD (Callendar-Van Dusen), Sensor pressão polinomial.
- Cor / Gama: sRGB ↔ Linear, CMYK ↔ RGB, LUTs 3D (Color Grading, cubos 17×17×17).
- Comunicações Digitais: Mapeamento modulação (constelação QAM), Métricas ramo decodificador Viterbi, CRC (table-driven).
- Sistemas Controle: Agendamento ganho (válvula não-linear → linearizada), Perfis came.
- Criptografia: S-Boxes (AES SubBytes), Constantes Montgomery pré-computadas.
- Desenvolvimento Jogos: Lightmaps, Shadow maps, GI pré-assado, Curvas animação.
Considerações de Projeto
- Resolução vs Tamanho: Entrada 8-bit = 256 entradas. 16-bit = 65.536 entradas. Interpolação (linear/cúbica) reduz entradas necessárias.
- Custo Inicialização: Computar uma vez na inicialização / tempo compilação (constexpr). Incorporar no binário.
- Localidade Cache: LUTs pequenas cabem em cache L1. LUTs grandes → cache misses → mais lento que computar.
- Precisão: Erro quantização (arredondamento índice entrada) + Precisão saída. Interpolação reduz erro.
- Volatilidade: Estática (ROM/Flash) vs Dinâmica (RAM, atualizada runtime — ex: equalizador adaptativo).
Exemplo Interpolação (1D Linear)
float lut_interp(const float* tabela, int n, float x, float x_min, float x_max) { float idx = (x - x_min) * (n - 1) / (x_max - x_min); int i = (int)floorf(idx); float frac = idx - i; i = clamp(i, 0, n - 2); return tabela[i] * (1 - frac) + tabela[i + 1] * frac; }
Quando NÃO Usar LUT
- Função é simples e rápida (ex:
y = 2*x + 1). Computar vence.
- Faixa entrada enorme / precisão alta contínua (ex: float 32-bit → 4B entradas impossível).
- Memória severamente restrita (MCU minúsculo, 2KB RAM) e função computável em < 10 ciclos.
- Dados mudam todo ciclo (sem reuso).
Conclusão: LUTs são uma **técnica fundamental de otimização** — "Espaço por Tempo". Ubíquas em embarcados, DSP, gráficos, cripto e computação científica. Perfile primeiro: meça ciclos computação vs largura banda/latência memória.
