779 Fundamental

779-const-lookup-table — Const Lookup Table

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "779-const-lookup-table — Const Lookup Table" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. Lookup tables trade memory for computation: instead of calculating `sin(x)` at runtime, you pre-compute 256 values and index into the table with a single array access. Key difference from OCaml: 1. **Compile vs runtime**: Rust embeds the table in the binary at compile time (zero startup cost); OCaml computes the table during module initialization (milliseconds on first use).

Tutorial

The Problem

Lookup tables trade memory for computation: instead of calculating sin(x) at runtime, you pre-compute 256 values and index into the table with a single array access. Pre-computing these tables at compile time with const fn means zero startup overhead — the table is embedded in the binary's read-only data segment. This technique is used in audio DSP (wavetable synthesis), graphics (gamma correction curves), and cryptography (S-boxes in AES, CRC32 tables).

🎯 Learning Outcomes

• Generate a 256-entry sine lookup table at compile time using const fn

• Generate a 256-entry CRC32 lookup table using the standard polynomial 0xEDB88320

• Use Taylor series approximations for sin in const fn (standard f64::sin is not const)

• Access the tables at runtime with O(1) array indexing

• Understand how to validate compile-time generated tables against runtime computations

Code Example

pub const fn generate_crc32_table() -> [u32; 256] {
    let mut table = [0u32; 256];
    let mut i = 0;
    while i < 256 {
        // compute CRC entry...
        i += 1;
    }
    table
}

// Generated at compile time, embedded in binary
pub const CRC32_TABLE: [u32; 256] = generate_crc32_table();

(* Generated at runtime, module initialization *)
let crc32_table =
  Array.init 256 (fun i ->
    let rec loop crc j =
      if j = 8 then crc
      else if crc land 1 <> 0 then
        loop ((crc lsr 1) lxor 0xEDB88320) (j + 1)
      else
        loop (crc lsr 1) (j + 1)
    in
    loop i 0
  )

Key Differences

Compile vs runtime: Rust embeds the table in the binary at compile time (zero startup cost); OCaml computes the table during module initialization (milliseconds on first use).

Float restrictions: const fn in Rust cannot use f64::sin (not stable const); Taylor series approximation is required; OCaml uses Float.sin at runtime initialization freely.

Binary size: Rust's compile-time tables are in the .rodata segment, counted in binary size; OCaml's are heap-allocated at runtime.

Validation: Both can test generated tables against known values; Rust does this via const_assert! or tests; OCaml uses Alcotest.

OCaml Approach

OCaml generates lookup tables at module initialization using Array.init with a computation function. For CRC32, let crc32_table = Array.init 256 compute_entry. Since OCaml doesn't have compile-time evaluation, these initialize on first module load (fast but not truly compile-time). For embedded targets, OCaml uses code generation scripts to produce hardcoded array literals.

Full Source

#![allow(clippy::all)]
//! # Const Lookup Table
//!
//! Pre-computed lookup tables at compile time.

/// Sine lookup table (256 entries, 0-2π)
pub const fn generate_sin_table() -> [i16; 256] {
    let mut table = [0i16; 256];
    let mut i = 0;
    while i < 256 {
        // Approximate sin using Taylor series
        let angle = (i as f64) * std::f64::consts::PI * 2.0 / 256.0;
        let sin_val = const_sin(angle);
        table[i] = (sin_val * 32767.0) as i16;
        i += 1;
    }
    table
}

/// Approximate sin at compile time using Taylor series
const fn const_sin(x: f64) -> f64 {
    // Normalize to -π to π
    let mut x = x;
    while x > std::f64::consts::PI {
        x -= 2.0 * std::f64::consts::PI;
    }
    while x < -std::f64::consts::PI {
        x += 2.0 * std::f64::consts::PI;
    }

    // Taylor: sin(x) ≈ x - x³/3! + x⁵/5! - x⁷/7! + ...
    let x2 = x * x;
    let x3 = x2 * x;
    let x5 = x3 * x2;
    let x7 = x5 * x2;

    x - x3 / 6.0 + x5 / 120.0 - x7 / 5040.0
}

/// CRC32 lookup table
pub const fn generate_crc32_table() -> [u32; 256] {
    let mut table = [0u32; 256];
    let mut i = 0;
    while i < 256 {
        let mut crc = i as u32;
        let mut j = 0;
        while j < 8 {
            if crc & 1 != 0 {
                crc = (crc >> 1) ^ 0xEDB88320;
            } else {
                crc >>= 1;
            }
            j += 1;
        }
        table[i] = crc;
        i += 1;
    }
    table
}

/// Powers of 2 lookup
pub const fn generate_pow2_table() -> [u64; 64] {
    let mut table = [0u64; 64];
    let mut i = 0;
    while i < 64 {
        table[i] = 1u64 << i;
        i += 1;
    }
    table
}

/// Factorial lookup (up to 20!)
pub const fn generate_factorial_table() -> [u64; 21] {
    let mut table = [1u64; 21];
    let mut i = 1;
    while i <= 20 {
        table[i] = table[i - 1] * (i as u64);
        i += 1;
    }
    table
}

// Pre-computed lookup tables
pub const CRC32_TABLE: [u32; 256] = generate_crc32_table();
pub const POW2_TABLE: [u64; 64] = generate_pow2_table();
pub const FACTORIAL_TABLE: [u64; 21] = generate_factorial_table();

/// Fast CRC32 using lookup table
pub fn crc32(data: &[u8]) -> u32 {
    let mut crc = 0xFFFFFFFF;
    for &byte in data {
        let index = ((crc ^ byte as u32) & 0xFF) as usize;
        crc = (crc >> 8) ^ CRC32_TABLE[index];
    }
    !crc
}

/// Fast factorial using lookup
pub const fn factorial_lookup(n: usize) -> Option<u64> {
    if n <= 20 {
        Some(FACTORIAL_TABLE[n])
    } else {
        None
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_pow2_table() {
        assert_eq!(POW2_TABLE[0], 1);
        assert_eq!(POW2_TABLE[10], 1024);
        assert_eq!(POW2_TABLE[20], 1048576);
    }

    #[test]
    fn test_factorial_table() {
        assert_eq!(FACTORIAL_TABLE[0], 1);
        assert_eq!(FACTORIAL_TABLE[5], 120);
        assert_eq!(FACTORIAL_TABLE[10], 3628800);
        assert_eq!(FACTORIAL_TABLE[20], 2432902008176640000);
    }

    #[test]
    fn test_crc32() {
        let data = b"hello";
        let crc = crc32(data);
        assert_eq!(crc, 0x3610A686);
    }

    #[test]
    fn test_factorial_lookup() {
        assert_eq!(factorial_lookup(5), Some(120));
        assert_eq!(factorial_lookup(21), None);
    }

    // Compile-time verification
    const _: () = assert!(POW2_TABLE[10] == 1024);
    const _: () = assert!(FACTORIAL_TABLE[5] == 120);
}

(* Compile-time lookup tables in OCaml — computed at module load *)

(* CRC-32 table *)
let crc32_table =
  Array.init 256 (fun i ->
    let crc = ref (Int32.of_int i) in
    for _ = 0 to 7 do
      if Int32.logand !crc 1l = 1l then
        crc := Int32.logxor (Int32.shift_right_logical !crc 1) 0xEDB88320l
      else
        crc := Int32.shift_right_logical !crc 1
    done;
    !crc)

let crc32 data =
  let crc = ref 0xFFFFFFFFl in
  String.iter (fun c ->
    let idx = Int32.to_int (Int32.logand
      (Int32.logxor !crc (Int32.of_int (Char.code c))) 0xFFl) in
    crc := Int32.logxor
      (Int32.shift_right_logical !crc 8)
      crc32_table.(idx)
  ) data;
  Int32.logxor !crc 0xFFFFFFFFl

(* ASCII upper-case table *)
let ascii_upper =
  Array.init 256 (fun i ->
    if i >= Char.code 'a' && i <= Char.code 'z'
    then Char.chr (i - 32)
    else Char.chr i)

let uppercase s =
  String.init (String.length s)
    (fun i -> ascii_upper.(Char.code s.[i]))

let () =
  Printf.printf "CRC32(\"hello\") = %08lX\n" (crc32 "hello");
  Printf.printf "uppercase(%S)  = %S\n" "Hello, World!" (uppercase "Hello, World!")

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_pow2_table() {
        assert_eq!(POW2_TABLE[0], 1);
        assert_eq!(POW2_TABLE[10], 1024);
        assert_eq!(POW2_TABLE[20], 1048576);
    }

    #[test]
    fn test_factorial_table() {
        assert_eq!(FACTORIAL_TABLE[0], 1);
        assert_eq!(FACTORIAL_TABLE[5], 120);
        assert_eq!(FACTORIAL_TABLE[10], 3628800);
        assert_eq!(FACTORIAL_TABLE[20], 2432902008176640000);
    }

    #[test]
    fn test_crc32() {
        let data = b"hello";
        let crc = crc32(data);
        assert_eq!(crc, 0x3610A686);
    }

    #[test]
    fn test_factorial_lookup() {
        assert_eq!(factorial_lookup(5), Some(120));
        assert_eq!(factorial_lookup(21), None);
    }

    // Compile-time verification
    const _: () = assert!(POW2_TABLE[10] == 1024);
    const _: () = assert!(FACTORIAL_TABLE[5] == 120);
}

Deep Comparison

OCaml vs Rust: Const Lookup Table

Compile-Time Table Generation

Rust

pub const fn generate_crc32_table() -> [u32; 256] {
    let mut table = [0u32; 256];
    let mut i = 0;
    while i < 256 {
        // compute CRC entry...
        i += 1;
    }
    table
}

// Generated at compile time, embedded in binary
pub const CRC32_TABLE: [u32; 256] = generate_crc32_table();

OCaml

(* Generated at runtime, module initialization *)
let crc32_table =
  Array.init 256 (fun i ->
    let rec loop crc j =
      if j = 8 then crc
      else if crc land 1 <> 0 then
        loop ((crc lsr 1) lxor 0xEDB88320) (j + 1)
      else
        loop (crc lsr 1) (j + 1)
    in
    loop i 0
  )

Using Lookup Tables

Rust

pub fn crc32(data: &[u8]) -> u32 {
    let mut crc = 0xFFFFFFFF;
    for &byte in data {
        let idx = ((crc ^ byte as u32) & 0xFF) as usize;
        crc = (crc >> 8) ^ CRC32_TABLE[idx];
    }
    !crc
}

Key Differences

Aspect	OCaml	Rust
Table generation	Runtime	Compile time
Binary size	Code only	Code + table data
Startup time	Table computed	Zero (embedded)
Optimization	JIT possible	Inline possible

Exercises

Add a generate_cos_table() -> [i16; 256] and implement fast_cos(angle_256: u8) -> f32 using the sine table with a 64-entry phase offset.

Implement crc32_bytes(data: &[u8]) -> u32 that uses the generated table for CRC32/ISO-HDLC as used in Ethernet, ZIP, and PNG.

Generate a gamma correction lookup table for 8-bit image processing: const GAMMA_TABLE: [u8; 256] where table[i] = (255 * (i/255)^2.2) as u8.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust