Task: regex_match
Category: Spatial--temporal algorithms
Difficulty: 3
Tags: NFA,state_propagation,bitmask,multi_string,CSR
Source: Google RE2 (Thompson-NFA reference): https://github.com/google/re2
Description: Thompson-NFA regular-expression simulation over a batch of input strings.

Prompt template (YAML):
# NFA-based Regular Expression Matching -- Prompt Template

task_description: |
  Given a compiled NFA (Non-deterministic Finite Automaton) and N input strings,
  determine whether each string is accepted (full match) by the NFA.

  The NFA is represented as:
  - A set of states (0 to num_states-1), with a designated start state
  - A transition table in CSR format: for each (state, symbol) pair, a list of target states
  - An epsilon transition table in CSR format: for each state, a list of states reachable via ε-moves
  - A boolean `is_accept` array marking which states are accept states

  The matching algorithm (Thompson NFA simulation):
  1. Start with the ε-closure of {start_state}
  2. For each character in the string:
     - For each active state, follow transitions on that character
     - Compute ε-closure of the resulting state set
  3. If any accept state is active after processing all characters → match (1), else no match (0)

  The N input strings are packed as a flat array with offsets.
  Each string's characters are symbol IDs (0-indexed integers, 0 to num_symbols-1).

interface: |
  ```c
  // Single end-to-end call. Do H2D + kernel + D2H and synchronize before returning.
  // Called multiple times (warmup + timed); must be idempotent.
  extern "C" void solution_compute(
      int num_states,
      int num_symbols,
      int start_state,
      int num_strings,
      int total_chars,
      const int* trans_offsets,
      const int* trans_targets,
      const int* eps_offsets,
      const int* eps_targets,
      const int* is_accept,
      const int* str_offsets,
      const int* str_data,
      int* results
  );
  ```

input_size_notes: |
  - **small**: 1,000 strings, avg length 100, 32 NFA states
  - **medium**: 100,000 strings, avg length 200, 64 NFA states
  - **large**: 1,000,000 strings, avg length 500, 128 NFA states
  - Alphabet is 26 symbols (0-25, representing a-z)
  - Transition table CSR: `trans_offsets[s * num_symbols + c]` to `trans_offsets[s * num_symbols + c + 1]`
    gives the range of target states in `trans_targets` for state `s` on symbol `c`
  - Epsilon transitions: `eps_offsets[s]` to `eps_offsets[s+1]` gives ε-reachable states from `s`

output_contract: |
  - `results[i]` = 1 if string `i` is accepted by the NFA, 0 otherwise
  - The match must be **exact**: the NFA must accept after processing all characters
  - Results must match the CPU reference exactly (no tolerance)
  - `solution_compute` must be **idempotent** and **synchronize** before returning

# -- L1 only: algorithm background --

algorithm_background: |
  **Thompson NFA Simulation** processes strings in O(n × m) time where n = string length
  and m = number of NFA states. The key data structure is the **active state set**:

  - After processing each character, we maintain a set of all NFA states that could be
    active given the input so far.
  - Transitions: for each active state and the current character, follow all transitions
    to get the next state set.
  - Epsilon closure: after each step, expand the state set to include all states reachable
    via ε-transitions (BFS/DFS).

  **GPU parallel opportunities:**
  - **Outer parallelism**: N strings are completely independent → one thread per string
  - **State set as bitmask**: If num_states ≤ 32, use `uint32_t`; ≤ 64, use `uint64_t`;
    ≤ 128, use `uint64_t[2]`. State transitions become bitwise OR operations.
  - **Pre-compute transition bitmasks**: For each (state, symbol), pre-compute a bitmask
    of target states. Then transition = OR of bitmasks for all active states.

# -- Hints by level --

hints_l2: |
  - Copy NFA data to GPU **once** inside `solution_compute`; keep state local to each call
  - Each thread processes one string independently (embarrassingly parallel)
  - Represent the active state set as a bitmask (uint32/uint64) for fast set operations
  - Pre-compute a transition bitmask table: `trans_bitmask[state][symbol]` = bitmask of targets

hints_l1: |
  ### 1. Persistent GPU Data
  Copy `trans_offsets`, `trans_targets`, `eps_offsets`, `eps_targets`, `is_accept`,
  `str_offsets`, `str_data` to device memory inside `solution_compute`. Pre-allocate output buffer.

  ### 2. One Thread Per String
  Launch N threads. Each thread processes its string independently using Thompson NFA simulation.
  No inter-thread communication needed.

  ### 3. Bitmask State Set
  For num_states ≤ 64: represent the active state set as a `uint64_t`.
  - Set union = bitwise OR: `states |= new_states`
  - Check accept = `states & accept_mask`
  - Empty check = `states == 0`

  For num_states ≤ 128: use `uint64_t[2]` (two 64-bit words).

  ### 4. Pre-compute Transition Bitmask Table
  In `solution_compute` setup phase, build a table `trans_bitmask[state * num_symbols + symbol]`
  where each entry is a bitmask of target states. Store in device memory.

  Then each transition step becomes:
  ```cuda
  uint64_t next = 0;
  while (current) {
      int s = __ffsll(current) - 1;  // find lowest set bit
      current &= current - 1;        // clear it
      next |= trans_bitmask[s * num_symbols + c];
  }
  ```

  ### 5. Epsilon Closure via Bitmask Fixpoint
  Pre-compute `eps_bitmask[state]` = bitmask of states reachable via one ε-step.
  Then epsilon closure = iterate until fixpoint:
  ```cuda
  uint64_t prev;
  do {
      prev = states;
      uint64_t tmp = states;
      while (tmp) {
          int s = __ffsll(tmp) - 1;
          tmp &= tmp - 1;
          states |= eps_bitmask[s];
      }
  } while (states != prev);
  ```

  ### 6. Shared Memory for Transition Table
  If the transition bitmask table fits in shared memory
  (num_states × num_symbols × sizeof(bitmask)):
  - 32 states × 26 symbols × 4 bytes = 3.3 KB → easily fits
  - 64 states × 26 symbols × 8 bytes = 13.3 KB → fits
  - 128 states × 26 symbols × 16 bytes = 53 KB → tight, may need partial loading


CPU reference implementation (C):
// cpu_reference.c -- regex_match CPU baseline (Thompson NFA simulation)
//
// For each input string, simulates the NFA by maintaining a set of active
// states (as a bitmask for states <= 128, or an array otherwise), processing
// one character at a time, and checking if any accept state is reached.
//
// NO file I/O here. All I/O is handled by task_io_cpu.c.

#include <stdlib.h>
#include <string.h>

// Maximum NFA states we support (use array-based state set)
#define MAX_STATES 256

// ===== Module-level state =====
static int g_num_states;
static int g_num_symbols;
static int g_start_state;
static int g_num_strings;
static int g_total_chars;

static const int* g_trans_offsets;   // [num_states * num_symbols + 1]
static const int* g_trans_targets;   // [num_trans]
static const int* g_eps_offsets;     // [num_states + 1]
static const int* g_eps_targets;     // [num_eps]
static const int* g_is_accept;       // [num_states]
static const int* g_str_offsets;     // [num_strings + 1]
static const int* g_str_data;        // [total_chars]

static void _orbench_old_init(int num_states, int num_symbols, int start_state,
                   int num_strings, int total_chars,
                   const int* trans_offsets, const int* trans_targets,
                   const int* eps_offsets, const int* eps_targets,
                   const int* is_accept,
                   const int* str_offsets, const int* str_data) {
    g_num_states = num_states;
    g_num_symbols = num_symbols;
    g_start_state = start_state;
    g_num_strings = num_strings;
    g_total_chars = total_chars;
    g_trans_offsets = trans_offsets;
    g_trans_targets = trans_targets;
    g_eps_offsets = eps_offsets;
    g_eps_targets = eps_targets;
    g_is_accept = is_accept;
    g_str_offsets = str_offsets;
    g_str_data = str_data;
}

// ===== Epsilon closure via BFS =====
// active[s] = 1 if state s is in the set
// Uses a queue for BFS
static void epsilon_closure(const int* eps_offsets, const int* eps_targets,
                            int num_states, char* active) {
    int queue[MAX_STATES];
    int qhead = 0, qtail = 0;

    // Initialize queue with all currently active states
    for (int s = 0; s < num_states; s++) {
        if (active[s]) {
            queue[qtail++] = s;
        }
    }

    // BFS
    while (qhead < qtail) {
        int s = queue[qhead++];
        int start = eps_offsets[s];
        int end = eps_offsets[s + 1];
        for (int i = start; i < end; i++) {
            int t = eps_targets[i];
            if (!active[t]) {
                active[t] = 1;
                queue[qtail++] = t;
            }
        }
    }
}

// ===== Match a single string =====
static int nfa_match_one(const int* str, int str_len) {
    char current[MAX_STATES];
    char next[MAX_STATES];

    int ns = g_num_states;
    int nsym = g_num_symbols;

    // Start: epsilon closure of {start_state}
    memset(current, 0, (size_t)ns);
    current[g_start_state] = 1;
    epsilon_closure(g_eps_offsets, g_eps_targets, ns, current);

    // Process each character
    for (int pos = 0; pos < str_len; pos++) {
        int c = str[pos];
        if (c < 0 || c >= nsym) {
            // Invalid symbol -> dead
            return 0;
        }

        memset(next, 0, (size_t)ns);

        // For each active state, follow transitions on symbol c
        for (int s = 0; s < ns; s++) {
            if (!current[s]) continue;
            int idx = s * nsym + c;
            int start = g_trans_offsets[idx];
            int end = g_trans_offsets[idx + 1];
            for (int i = start; i < end; i++) {
                next[g_trans_targets[i]] = 1;
            }
        }

        // Epsilon closure of next states
        epsilon_closure(g_eps_offsets, g_eps_targets, ns, next);

        // Swap
        memcpy(current, next, (size_t)ns);

        // Early termination: no active states
        int any_active = 0;
        for (int s = 0; s < ns; s++) {
            if (current[s]) { any_active = 1; break; }
        }
        if (!any_active) return 0;
    }

    // Check if any accept state is active
    for (int s = 0; s < ns; s++) {
        if (current[s] && g_is_accept[s]) return 1;
    }
    return 0;
}

// ===== solution_compute: match all strings =====
static void _orbench_old_compute(int num_strings, int* results) {
    for (int i = 0; i < num_strings; i++) {
        int offset = g_str_offsets[i];
        int len = g_str_offsets[i + 1] - offset;
        results[i] = nfa_match_one(&g_str_data[offset], len);
    }
}

// ── Unified compute_only wrapper (auto-migrated) ──
void solution_compute(int num_states, int num_symbols, int start_state, int num_strings, int total_chars, const int* trans_offsets, const int* trans_targets, const int* eps_offsets, const int* eps_targets, const int* is_accept, const int* str_offsets, const int* str_data, int* results) {
    _orbench_old_init(num_states, num_symbols, start_state, num_strings, total_chars, trans_offsets, trans_targets, eps_offsets, eps_targets, is_accept, str_offsets, str_data);
    _orbench_old_compute(num_strings, results);
}