# Edit Distances > StringZilla for C `#include ` `#include ` `#include ` ## sz_similarity_locality_t Describes the alignment scope for string similarity algorithms. ```c enum sz_similarity_locality_t ``` - `sz_similarity_global_k` = `0` - `sz_similarity_local_k` = `1` See also: sz_similarity_global_k, sz_similarity_local_k ## sz_similarity_objective_t Describes the alignment objective for string similarity algorithms. ```c enum sz_similarity_objective_t ``` - `sz_minimize_distance_k` = `0` - `sz_maximize_score_k` = `1` See also: sz_minimize_distance_k, sz_maximize_score_k ## sz_similarity_packing_t Describes how a similarity kernel packs work across SIMD lanes or a GPU warp's threads. ```c enum sz_similarity_packing_t ``` __one_pair_per_walk_k__ vectorizes within a single (query, candidate) pair, in anti-diagonal lanes — the intra-sequence form, used for one-off pairs and the ragged tail of a cross-product. __candidates_across_lanes_k__ vectorizes across many candidates of one shared query, one candidate per lane — the inter-sequence form that keeps every lane busy regardless of string length, the cross-product workhorse. - `sz_packing_one_pair_per_walk_k` = `0` - `sz_packing_candidates_across_lanes_k` = `1` See also: sz_packing_one_pair_per_walk_k, sz_packing_candidates_across_lanes_k ## sz_similarity_gaps_t Describes the cost model for gap opening vs extension in string similarity algorithms. ```c enum sz_similarity_gaps_t ``` - `sz_gaps_linear_k` = `1`: Linear costs require us to build only 1 DP matrix. - `sz_gaps_affine_k` = `3`: Affine costs require us to build 3 DP matrices. See also: [sz_gaps_linear_k](#sz_gaps_linear_k), [sz_gaps_affine_k](#sz_gaps_affine_k) ## sz_levenshtein_symbol_t Which symbols a batch counts, as the alphabet picks the transpose and the mask layout alike. ```c enum sz_levenshtein_symbol_t ``` - `sz_levenshtein_bytes_k` = `0`: Every byte is its own symbol, and a distance counts bytes. - `sz_levenshtein_runes_k` = `1`: Every UTF-8 rune is one symbol, each maximal ill-formed subpart decoding to one U+FFFD. ## sz_kernel_levenshtein_engine_init_t Signature of every [`sz_levenshtein_engine_init`](#sz_levenshtein_engine_init) kernel. ```c typedef sz_status_t(*) sz_kernel_levenshtein_engine_init_t(struct sz_levenshtein_engine_t *, sz_strings_view_t const *, sz_levenshtein_symbol_t, sz_allocator_t *, sz_stream_t); ``` ## sz_kernel_levenshtein_distances_t Signature of every [`sz_levenshtein_distances`](#sz_levenshtein_distances) kernel, at either alphabet. ```c typedef sz_status_t(*) sz_kernel_levenshtein_distances_t(struct sz_levenshtein_engine_t *, sz_strings_view_t const *, sz_size_t const *, sz_size_t const *, sz_size_t, sz_size_t *, sz_size_t, sz_stream_t); ``` ## sz_levenshtein_engine_init Prepares `queries` into one block from `allocator`, for the best capability of `capabilities` that has an init kernel. ```c sz_status_t sz_levenshtein_engine_init( sz_levenshtein_engine_t *engine, sz_strings_view_t const *queries, sz_levenshtein_symbol_t symbol, sz_capability_t capabilities, sz_allocator_t *allocator, sz_stream_t stream); ``` - `sz_levenshtein_engine_init` backends: serial, haswell, skylake, icelake, neon, cuda, blackwell, rocm, metal - `engine` (out): Untouched unless the call succeeds; [sz_levenshtein_engine_free](#sz_levenshtein_engine_free) frees it. - `queries` (in): The patterns every candidate is scored against, in any layout over host-readable texts, whose symbols and classes size the block. - `symbol` (in): Whether a distance counts bytes or UTF-8 runes. - `capabilities` (in): One device's capabilities, like `sz_capabilities_enabled_cpu` or [`sz_capabilities_enabled_cuda`](https://www.unum.cloud/docs/stringzilla/c/runtime-dispatch.md#sz_capabilities_enabled_cuda) report; its group picks the CPU or a GPU vendor. - `allocator` (in): Source of the engine's blocks, or [`STRINGZILLA_NULL`](https://www.unum.cloud/docs/stringzilla/c/types.md#STRINGZILLA_NULL) for [sz_allocator_init_unified_best](https://www.unum.cloud/docs/stringzilla/c/memory-operations.md#sz_allocator_init_unified_best) of `capabilities`. - `stream` (in): Null on the CPU. On a GPU, the stream to queue on, also naming the device: a `cudaStream_t`, a `hipStream_t`, or an `id`; null for the default. Notes: May join `stream`; no scoring verb ever does. Statuses: - [`sz_missing_kernel_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_missing_kernel_k) No capability of the mask has an init. - [`sz_unexpected_dimensions_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_unexpected_dimensions_k) On a device, an unrepresentable query length. - [`sz_device_memory_mismatch_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_device_memory_mismatch_k) On a device, memory or a `stream` the device cannot use. ## sz_levenshtein_engine_free Returns both of `engine` 's blocks to the allocator that built them, once the work queued on `stream` is done with them, and leaves it empty. ```c void sz_levenshtein_engine_free( sz_levenshtein_engine_t *engine, sz_stream_t stream); ``` ## sz_levenshtein_distances Edit distances from every prepared query to every candidate, by the kernel of the capability `engine` was prepared for, exact up to `bound`. ```c sz_status_t sz_levenshtein_distances( sz_levenshtein_engine_t *engine, sz_strings_view_t const *candidates, sz_size_t const *symbol_counts, sz_size_t const *order, sz_size_t bound, sz_size_t *distances, sz_size_t distances_stride, sz_stream_t stream); ``` - `sz_levenshtein_distances` backends: serial, haswell, skylake, icelake, neon, cuda, blackwell, rocm, metal A query prepared once scores any number of candidate batches: the engine's scratch only grows, so batches no larger than an earlier one allocate nothing. A host sweep advances a few candidates together and costs as long as the longest of them, so an `order` grouping similar lengths keeps it short, and it stops early once every candidate it holds is past `bound`. - `engine` (in): The prepared batch; its round scratch may grow. It keeps no stream and no round state on a device, so any number of that device's streams may score it at once. - `candidates` (in): The texts, on the residency `engine` was built for: any layout on the CPU, and on a device a tape [sz_strings_to_tape_best](https://www.unum.cloud/docs/stringzilla/c/sorting-and-sets.md#sz_strings_to_tape_best) wrote into a unified allocator. - `symbol_counts` (in): Each candidate's length in the engine's symbols by candidate index, as sz_levenshtein_utf8_runes counts runes, or null to count them as the sweep goes. - `order` (in): The visiting order, a permutation of the candidate indices, or null for the engine's own. Neither it nor `symbol_counts` changes a distance, and a device engine, which orders and counts candidates itself, reads neither. - `bound` (in): The largest distance reported exactly; a candidate past it reports `bound` + 1 on every backend. `STRINGZILLA_SIZE_MAX` keeps every distance exact. - `distances` (out): The ____[count, candidates] distances, query `q` at `distances[q * stride + c]`, device-reachable on a device. - `distances_stride` (in): Entries from one query's row to the next, at least the count. - `stream` (in): Null on the CPU. On a GPU, the stream to queue on, which also names the device the round runs on; null for the default. Notes: Grows the engine's host scratch when a round needs more than the last one did; never joins, so the caller joins `stream` before reading `distances`. Statuses: - [`sz_unexpected_dimensions_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_unexpected_dimensions_k) `distances_stride` is under the candidate count. - [`sz_missing_kernel_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_missing_kernel_k) An empty engine. - [`sz_device_memory_mismatch_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_device_memory_mismatch_k) On a device, an engine, an output, an accessor, a tape or a stream the device of `stream` cannot use. ## sz_levenshtein_engine_init_serial Prepares `queries` into one block from `allocator`, for the serial kernels. ```c sz_status_t sz_levenshtein_engine_init_serial( sz_levenshtein_engine_t *engine, sz_strings_view_t const *queries, sz_levenshtein_symbol_t symbol, sz_allocator_t *allocator, sz_stream_t stream); ``` - `sz_levenshtein_engine_init` backends: serial, haswell, skylake, icelake, neon, cuda, blackwell, rocm, metal - `engine` (out): Untouched unless the call succeeds; [sz_levenshtein_engine_free](#sz_levenshtein_engine_free) frees it. - `queries` (in): The patterns every candidate is scored against, in any layout over host-readable texts, whose symbols and classes size the block. - `symbol` (in): Whether a distance counts bytes or UTF-8 runes. - `allocator` (in): Source of the engine's blocks, or [`STRINGZILLA_NULL`](https://www.unum.cloud/docs/stringzilla/c/types.md#STRINGZILLA_NULL) for `sz_allocator_init_unified_serial`. - `stream` (in): Null on the CPU. Statuses: - [`sz_unexpected_dimensions_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_unexpected_dimensions_k) An unrepresentable query length. ## sz_levenshtein_distances_serial Edit distances from every prepared query to every candidate, by the kernel of the capability `engine` was prepared for, exact up to `bound`. ```c sz_status_t sz_levenshtein_distances_serial( sz_levenshtein_engine_t *engine, sz_strings_view_t const *candidates, sz_size_t const *symbol_counts, sz_size_t const *order, sz_size_t bound, sz_size_t *distances, sz_size_t distances_stride, sz_stream_t stream); ``` - `sz_levenshtein_distances` backends: serial, haswell, skylake, icelake, neon, cuda, blackwell, rocm, metal A query prepared once scores any number of candidate batches: the engine's scratch only grows, so batches no larger than an earlier one allocate nothing. A host sweep advances a few candidates together and costs as long as the longest of them, so an `order` grouping similar lengths keeps it short, and it stops early once every candidate it holds is past `bound`. - `engine` (in): The prepared batch; its round scratch may grow. It keeps no stream and no round state on a device, so any number of that device's streams may score it at once. - `candidates` (in): The texts, on the residency `engine` was built for: any layout on the CPU, and on a device a tape [sz_strings_to_tape_best](https://www.unum.cloud/docs/stringzilla/c/sorting-and-sets.md#sz_strings_to_tape_best) wrote into a unified allocator. - `symbol_counts` (in): Each candidate's length in the engine's symbols by candidate index, as sz_levenshtein_utf8_runes counts runes, or null to count them as the sweep goes. - `order` (in): The visiting order, a permutation of the candidate indices, or null for the engine's own. Neither it nor `symbol_counts` changes a distance, and a device engine, which orders and counts candidates itself, reads neither. - `bound` (in): The largest distance reported exactly; a candidate past it reports `bound` + 1 on every backend. `STRINGZILLA_SIZE_MAX` keeps every distance exact. - `distances` (out): The ____[count, candidates] distances, query `q` at `distances[q * stride + c]`, device-reachable on a device. - `distances_stride` (in): Entries from one query's row to the next, at least the count. - `stream` (in): Null on the CPU. On a GPU, the stream to queue on, which also names the device the round runs on; null for the default. Notes: Grows the engine's host scratch when a round needs more than the last one did; never joins, so the caller joins `stream` before reading `distances`. Statuses: - [`sz_unexpected_dimensions_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_unexpected_dimensions_k) `distances_stride` is under the candidate count. - [`sz_missing_kernel_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_missing_kernel_k) An empty engine. - [`sz_device_memory_mismatch_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_device_memory_mismatch_k) On a device, an engine, an output, an accessor, a tape or a stream the device of `stream` cannot use. ## sz_levenshtein_find_kernel Finds the Levenshtein kernel of `kind`, from the best of `capabilities`. ```c sz_status_t sz_levenshtein_find_kernel( sz_kernel_kind_t kind, sz_capability_t capabilities, sz_kernel_punned_t *kernel, sz_capability_t *capability); ``` - `kind` (in): The verb whose kernel to find. - `capabilities` (in): The mask to pick the best capability from. - `kernel` (out): The kernel, or null when none of `capabilities` has it. - `capability` (out): The capability the kernel belongs to, or zero. Statuses: - [`sz_missing_kernel_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_missing_kernel_k) - [`sz_missing_library_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_missing_library_k) Header-only. ## Overview Includes core APIs with hardware-specific backends: - [`sz_levenshtein_engine_init`](#sz_levenshtein_engine_init) - prepares a batch of queries for the best capability of a mask, on the host or on one device. - [`sz_levenshtein_engine_free`](#sz_levenshtein_engine_free) - returns an engine's blocks to the allocator that built them. - [`sz_levenshtein_distances`](#sz_levenshtein_distances) - the ____[queries, candidates] edit distances of one batch, on the capability its engine was prepared for. - [`sz_levenshtein_find_kernel`](#sz_levenshtein_find_kernel) - the kernel any of them would run, for a caller that keeps it.Myers' bit-parallel algorithm treats every query as a pattern, packed 64 symbols per machine word, and every candidate streams one symbol per step. An engine prepares the whole batch's match masks once and advances several candidates per step - one per scalar state, four per YMM, eight per ZMM, one per thread on a device - so the tables are built once per batch rather than once per pair. A byte is its own mask class, while a rune takes the class its query assigned it or class zero when the query lacks it, which [sz_levenshtein_symbol_t](#sz_levenshtein_symbol_t) picks between. Strings of any length are accepted on either side; device queries are bounded by their length index. Long byte pairs on a device use an internal tiled wavefront for intra-pair parallelism. The building blocks are public as well, for callers that own the loop nest: the query preparation and the transposes on the query side, and per backend a state, a vertical, and the init, step, any-active and score verbs over them, named by candidates per step, such as `sz_levenshtein_u64x4_step_haswell`. Scoring itself has one entry point per backend, such as `sz_levenshtein_distances_haswell`, which takes the caller's order and a bound past which a distance need not be exact.