# Fingerprints > StringZilla for C `#include ` `#include ` ## sz_kernel_overlap_engine_init_t Signature of every [`sz_overlap_engine_init`](#sz_overlap_engine_init) kernel. ```c typedef sz_status_t(*) sz_kernel_overlap_engine_init_t(struct sz_overlap_engine_t *, sz_strings_view_t const *, sz_size_t const *, sz_size_t, sz_size_t, sz_allocator_t *, sz_stream_t); ``` ## sz_kernel_overlap_scores_t Signature of every [`sz_overlap_scores`](#sz_overlap_scores) kernel. ```c typedef sz_status_t(*) sz_kernel_overlap_scores_t(struct sz_overlap_engine_t *, sz_strings_view_t const *, sz_f32_t, sz_u32_t *, sz_size_t, sz_size_t, sz_stream_t); ``` ## sz_overlap_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_overlap_engine_init( sz_overlap_engine_t *engine, sz_strings_view_t const *queries, sz_size_t const *window_widths, sz_size_t window_widths_count, sz_size_t candidates_budget, sz_capability_t capabilities, sz_allocator_t *allocator, sz_stream_t stream); ``` - `sz_overlap_engine_init` backends: serial, haswell, skylake, neon, cuda, blackwell, rocm, metal Every width's window hashes of one query share that query's B-tree, so its sort runs once per batch rather than once per round, and the probe depth grows only logarithmically as widths are added to the batch. - `engine` (out): Left untouched unless the call succeeds. - `queries` (in): The texts whose windows are sorted into the forest; read on the host. - `window_widths` (in): Window widths in bytes; a width past a text scores zero for its pairs. - `window_widths_count` (in): Number of widths, which is the last axis of every output. - `candidates_budget` (in): Candidates one round may carry, for a backend whose rounds keep state per candidate, zero asking for its default; one that keeps none ignores it. - `capabilities` (in): One device's capabilities, like `sz_capabilities_enabled_cpu` or [`sz_capabilities_enabled_metal`](https://www.unum.cloud/docs/stringzilla/c/runtime-dispatch.md#sz_capabilities_enabled_metal) report; its group picks the CPU or a GPU vendor. - `allocator` (in): Source of the forest's block, 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`; stored by value, so [sz_overlap_engine_free](#sz_overlap_engine_free) needs no allocator of its own. - `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) Zero widths. - [`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` it cannot use. ## sz_overlap_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_overlap_engine_free( sz_overlap_engine_t *engine, sz_stream_t stream); ``` ## sz_overlap_scores Window overlap of every prepared query with every candidate, at every width of the batch, by the kernel of the capability `engine` was prepared for, exact within `radius`. ```c sz_status_t sz_overlap_scores( sz_overlap_engine_t *engine, sz_strings_view_t const *candidates, sz_f32_t radius, sz_u32_t *matches, sz_size_t matches_query_stride, sz_size_t matches_candidate_stride, sz_stream_t stream); ``` - `sz_overlap_scores` backends: serial, haswell, skylake, neon, cuda, blackwell, rocm, metal A batch of queries prepared once scores any number of candidate batches, and a host round block only grows, so a batch within the longest seen allocates nothing. A width's count is the candidate's windows the query also holds. A pair's misses are the longer side's windows the other leaves unmatched, summed over every width, and its distance is those misses over the longer side's windows in all. A pair within `radius` is counted exactly; a pair past it counts zero at every width, on every backend, or exactly when within rounding of the share, less than 2⁻²⁴ past it. A pair is dropped once its misses provably pass that share of its longer side, often from the two lengths alone, before a byte is read. The count of query q, candidate c and width w sits at: ``` * matches[q * matches_query_stride + c * matches_candidate_stride + w] * ``` - `engine` (in): The prepared forest; a host round block grows here and is never shrunk. A device engine keeps no stream, so on CUDA any number of streams may score it at once; on Metal its one round block orders the rounds on the device's one queue. - `candidates` (in): The texts whose windows are probed against the forest's, on the residency the 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. - `radius` (in): The share of its longer side's windows a pair may miss, in [0, 1]; 1 or more keeps every count exact. - `matches` (out): Counts with a unit-strided width axis, laid out as shown below. - `matches_query_stride` (in): Entries from one query's plane to the next, at least the candidates times `matches_candidate_stride`. - `matches_candidate_stride` (in): Entries between candidate rows, at least the widths the engine was prepared at. - `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: Asymmetric: a candidate's window occurrences count against a query's distinct windows, so swapping sides changes the count when either repeats a window. Notes: Never joins, so the caller joins `stream` before reading `matches`. Statuses: - [`sz_unexpected_dimensions_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_unexpected_dimensions_k) Either stride is under the axis it spans. - [`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_overlap_engine_init_serial Prepares `queries` into one block from `allocator`, for the serial kernels. ```c sz_status_t sz_overlap_engine_init_serial( sz_overlap_engine_t *engine, sz_strings_view_t const *queries, sz_size_t const *window_widths, sz_size_t window_widths_count, sz_size_t candidates_budget, sz_allocator_t *allocator, sz_stream_t stream); ``` - `sz_overlap_engine_init` backends: serial, haswell, skylake, neon, cuda, blackwell, rocm, metal - `engine` (out): Left untouched unless the call succeeds. - `queries` (in): The texts whose windows are sorted into the forest; read on the host. - `window_widths` (in): Window widths in bytes; a width past a text scores zero for its pairs. - `window_widths_count` (in): Number of widths, which is the last axis of every output. - `candidates_budget` (in): Candidates one round may carry; the serial rounds keep no state per candidate and ignore it. - `allocator` (in): Source of the forest's block, or [`STRINGZILLA_NULL`](https://www.unum.cloud/docs/stringzilla/c/types.md#STRINGZILLA_NULL) for `sz_allocator_init_unified_serial`; stored by value, so [sz_overlap_engine_free](#sz_overlap_engine_free) needs no allocator of its own. - `stream` (in): Null on the CPU. Statuses: - [`sz_unexpected_dimensions_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_unexpected_dimensions_k) Zero widths. ## sz_overlap_scores_serial Window overlap of every prepared query with every candidate, at every width of the batch, by the kernel of the capability `engine` was prepared for, exact within `radius`. ```c sz_status_t sz_overlap_scores_serial( sz_overlap_engine_t *engine, sz_strings_view_t const *candidates, sz_f32_t radius, sz_u32_t *matches, sz_size_t matches_query_stride, sz_size_t matches_candidate_stride, sz_stream_t stream); ``` - `sz_overlap_scores` backends: serial, haswell, skylake, neon, cuda, blackwell, rocm, metal A batch of queries prepared once scores any number of candidate batches, and a host round block only grows, so a batch within the longest seen allocates nothing. A width's count is the candidate's windows the query also holds. A pair's misses are the longer side's windows the other leaves unmatched, summed over every width, and its distance is those misses over the longer side's windows in all. A pair within `radius` is counted exactly; a pair past it counts zero at every width, on every backend, or exactly when within rounding of the share, less than 2⁻²⁴ past it. A pair is dropped once its misses provably pass that share of its longer side, often from the two lengths alone, before a byte is read. The count of query q, candidate c and width w sits at: ``` * matches[q * matches_query_stride + c * matches_candidate_stride + w] * ``` - `engine` (in): The prepared forest; a host round block grows here and is never shrunk. A device engine keeps no stream, so on CUDA any number of streams may score it at once; on Metal its one round block orders the rounds on the device's one queue. - `candidates` (in): The texts whose windows are probed against the forest's, on the residency the 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. - `radius` (in): The share of its longer side's windows a pair may miss, in [0, 1]; 1 or more keeps every count exact. - `matches` (out): Counts with a unit-strided width axis, laid out as shown below. - `matches_query_stride` (in): Entries from one query's plane to the next, at least the candidates times `matches_candidate_stride`. - `matches_candidate_stride` (in): Entries between candidate rows, at least the widths the engine was prepared at. - `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: Asymmetric: a candidate's window occurrences count against a query's distinct windows, so swapping sides changes the count when either repeats a window. Notes: Never joins, so the caller joins `stream` before reading `matches`. Statuses: - [`sz_unexpected_dimensions_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_unexpected_dimensions_k) Either stride is under the axis it spans. - [`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_overlap_find_kernel Finds the overlap kernel of `kind`, from the best of `capabilities`. ```c sz_status_t sz_overlap_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. ## Public API - [sz_overlap_engine_init](#sz_overlap_engine_init) → prepares a batch of queries for the best capability of a mask, on the host or on one device; - [sz_overlap_scores](#sz_overlap_scores) → the ____[queries,candidates,widths] match counts of one round, on the capability its engine was prepared for; - [sz_overlap_engine_free](#sz_overlap_engine_free) → returns both of the engine's blocks; - [sz_overlap_find_kernel](#sz_overlap_find_kernel) → the kernel either would run, for a caller that keeps it. Every register-level step behind these - the prefix chain, the window hashing, the key sort and the B-tree probe - is public per backend in `overlap/serial.h` and its SIMD backends, named by positions per step, such as `sz_overlap_f64x4_prefix_hash_step_haswell`, so a caller driving its own loops binds those steps and skips these verbs entirely. The tree layout is the same on every backend, so any of them may probe it. ## Overview A window is a fixed-width byte n-gram, and the overlap of two texts at that width is the count of one's windows that occur in the other, over whichever of the two has more. Every query is hashed once into one B-tree over every width's window hashes, and every candidate then streams through the forest, hashing its own windows and probing. Nothing is stored per candidate, so the candidates may change round to round while the queries and the widths stay. Window hashes come from a prefix difference, H(i, w) = P(i + w) − P(i) × bʷ mod p, which costs one modular multiply-add at any width and any offset; widths need not form a doubling chain. The modulus is a 32-bit prime chosen for collision weight, so a window hash is full-width.