# Sorting and Sets > StringZilla for C These operate on a read-only `sz_strings_view_t` in any layout and never reorder the underlying data — they fill an `order` permutation array instead. Sorting is __stable__, so equal elements keep their input order, supports descending order via a `reverse` flag, and supports partial / top-K sorting via `top_count` — pass `0` to sort everything. Every allocation these kernels need is routed through the `sz_allocator_t` you supply — pass `NULL` for the default `malloc`-based one — so, unlike `std::sort` or `thrust::sort`, no scratch memory is ever allocated behind your back. The C API fills a caller-owned `order` array and reports success through a `sz_status_t`: ```c sz_status_t sz_sort_order_best( sz_strings_view_t const *strings, sz_size_t top_count, sz_bool_t reverse, sz_allocator_t *allocator, sz_size_t *order, sz_capability_t capabilities, sz_stream_t stream); sz_status_t sz_sort_uncased_order_best( sz_strings_view_t const *strings, sz_size_t top_count, sz_bool_t reverse, sz_allocator_t *allocator, sz_size_t *order, sz_capability_t capabilities, sz_stream_t stream); ``` `sz_sort_order_best` orders byte-lexicographically; `sz_sort_uncased_order_best` orders under Unicode case-folding, folding small chunks on the fly, and malformed UTF-8 sorts by raw byte value so the order stays total and deterministic. The `allocator` argument may be `NULL` to use the default allocator. ```c #include int main(void) { sz_capability_t capabilities = sz_cap_serial_k; sz_capabilities_enabled_cpu(&capabilities); char const *fruits[] = {"banana", "apple", "cherry"}; sz_strings_view_t strings; sz_strings_from_null_terminated_strings(fruits, 3, &strings); sz_size_t order[3]; sz_status_t status = sz_sort_order_best(&strings, /*top_count*/ 0, sz_false_k, NULL, order, capabilities, NULL); assert(status == sz_success_k); assert(order[0] == 1 && order[1] == 0 && order[2] == 2); // apple, banana, cherry return 0; } ``` ### Set Intersection `sz_intersect_best` computes the intersection of two __deduplicated__ binary string collections using a hash table, writing matched positions from each side and leaving unmatched slots as `STRINGZILLA_SIZE_MAX`: ```c sz_status_t sz_intersect_best( sz_strings_view_t const *first_strings, sz_strings_view_t const *second_strings, sz_allocator_t *allocator, sz_u64_t seed, sz_size_t *intersection_count, sz_size_t *first_positions, sz_size_t *second_positions, sz_capability_t capabilities, sz_stream_t stream); ``` The `seed` randomizes the hash table to resist adversarial inputs; the position arrays must each fit at least `min(first->count, second->count)` entries. The companion `sz_join_semantics_t` enum documents the SQL-style JOIN modes the family is designed around, namely `sz_join_inner_strict_k`, `sz_join_inner_k`, `sz_join_left_outer_k`, `sz_join_right_outer_k`, `sz_join_full_outer_k`, and `sz_join_cross_k`. ```c char const *first[] = {"banana", "apple", "cherry"}; char const *second[] = {"cherry", "orange", "pineapple", "banana"}; sz_strings_view_t a, b; sz_strings_from_null_terminated_strings(first, 3, &a); sz_strings_from_null_terminated_strings(second, 4, &b); sz_size_t intersection_count; sz_size_t a_positions[3], b_positions[3]; // sized to the smaller collection sz_status_t status = sz_intersect_best(&a, &b, NULL, /*seed*/ 0, &intersection_count, a_positions, b_positions, capabilities, NULL); assert(intersection_count == 2); // "banana" and "cherry" ``` ### String Collections and Containers Collections are read through `sz_strings_view_t` in one of three layouts: an Apache Arrow `String` tape with 32-bit offsets, a `LargeString` tape with 64-bit offsets, or an accessor that writes the views of up to 64 strings per call. Accessors describe arrays of views, NUL-terminated pointers, struct members, record pointers and NUL-padded rows without copying a byte, while tapes are what Arrow and the GPU kernels read directly. Every conversion takes a view, an optional array of indices that reorders, samples or repeats it, and a count, and writes a writable `sz_strings_span_t` tape: ```c sz_status_t sz_strings_to_tape_best(sz_strings_view_t const *strings, sz_size_t const *order, sz_size_t count, sz_allocator_t *allocator, sz_strings_span_t *tape, sz_capability_t capabilities, sz_stream_t stream); sz_status_t sz_strings_escape_best(sz_strings_view_t const *strings, sz_size_t const *order, sz_size_t count, sz_escape_kind_t kind, sz_allocator_t *allocator, sz_strings_span_t *tape, sz_capability_t capabilities, sz_stream_t stream); sz_status_t sz_strings_unescape_best(sz_strings_view_t const *strings, sz_size_t const *order, sz_size_t count, sz_escape_kind_t kind, sz_allocator_t *allocator, sz_strings_span_t *tape, sz_size_t *malformed_index, sz_capability_t capabilities, sz_stream_t stream); sz_status_t sz_strings_normalize_best(sz_strings_view_t const *strings, sz_size_t const *order, sz_size_t count, sz_normal_form_t form, sz_allocator_t *allocator, sz_strings_span_t *tape, sz_capability_t capabilities, sz_stream_t stream); sz_status_t sz_strings_lookup_best(sz_strings_view_t const *strings, sz_size_t const *order, sz_size_t count, char const lut[256], sz_allocator_t *allocator, sz_strings_span_t *tape, sz_capability_t capabilities, sz_stream_t stream); sz_status_t sz_strings_to_rows_best(sz_strings_view_t const *strings, sz_size_t const *order, sz_size_t count, sz_strings_rows_t const *rows, sz_size_t *longest, sz_capability_t capabilities, sz_stream_t stream); ``` Every conversion is atomic: it succeeds with the whole result in the tape, or fails and leaves the tape, its blocks and their bytes exactly as they were, whether an allocation was refused or a string was malformed. A zeroed span receives fresh blocks from the allocator, blocks that already have the result's sizes are written in place, and any other span's old blocks go back only once the result is written. The allocator's `reallocate` is an optional fast path; without it, a block that must change size moves through `allocate`, `memcpy` and `free`. Escaping covers JSON, JSON in ASCII the way Python's `json.dumps` writes it, RFC 4180 CSV, hexadecimal, HTML, URL percent-encoding, and terminal-safe logs, and unescaping reports the first malformed string. Normalization brings every string into NFC, NFD, NFKC, NFKD or NFKC_Casefold, and NUL-padded rows serve NumPy `S` arrays and fixed-width record fields. A single buffer is a tape of one string, so lowercasing in place looks like this: ```c #include int main(void) { sz_capability_t capabilities = sz_cap_serial_k; sz_capabilities_enabled_cpu(&capabilities); char to_lower[256]; sz_strings_lookup_init_lower(to_lower); char buffer[3] = {'A', 'B', 'C'}; sz_u32_t offsets[2] = {0, 3}; sz_strings_span_t tape; tape.layout = sz_strings_u32_tape_k, tape.count = 1; tape.data.u32_tape.data = buffer, tape.data.u32_tape.offsets = offsets; sz_strings_view_t strings; sz_strings_from_span(&tape, &strings); sz_strings_lookup_best(&strings, NULL, 1, to_lower, NULL, &tape, capabilities, NULL); assert(buffer[0] == 'a' && buffer[1] == 'b' && buffer[2] == 'c'); // "abc" return 0; } ``` #### The `sz_string_t` SSO Container `sz_string_t` is a tiny memory-owning string with Small-String-Optimization: short strings, up to 22 bytes plus the terminator on 64-bit, live inline with no heap allocation, while longer strings spill to the heap. Its length can be read branchlessly, and many length changes avoid branches entirely. Every mutating call takes an explicit `sz_allocator_t *`. Lifecycle and read-only access: ```c void sz_string_init(sz_string_t *string); sz_ptr_t sz_string_init_length(sz_string_t *string, sz_size_t length, sz_allocator_t *allocator); sz_bool_t sz_string_is_on_stack(sz_string_t const *string); void sz_string_unpack(sz_string_t const *string, sz_ptr_t *start, sz_size_t *length, sz_size_t *space, sz_bool_t *is_external); void sz_string_range(sz_string_t const *string, sz_ptr_t *start, sz_size_t *length); sz_size_t sz_string_length(sz_string_t const *string); sz_bool_t sz_string_equal(sz_string_t const *a, sz_string_t const *b); sz_ordering_t sz_string_order(sz_string_t const *a, sz_string_t const *b); ``` Growth and mutation, where all but `sz_string_erase` may allocate and return `STRINGZILLA_NULL_CHAR` on failure: ```c sz_ptr_t sz_string_reserve(sz_string_t *string, sz_size_t new_capacity, sz_allocator_t *allocator); sz_ptr_t sz_string_expand(sz_string_t *string, sz_size_t offset, sz_size_t added_length, sz_allocator_t *allocator); sz_size_t sz_string_erase(sz_string_t *string, sz_size_t offset, sz_size_t length); sz_ptr_t sz_string_shrink_to_fit(sz_string_t *string, sz_allocator_t *allocator); void sz_string_free(sz_string_t *string, sz_allocator_t *allocator); ``` `sz_string_expand` opens an uninitialized gap of `added_length` at `offset` that you then populate, often via `memcpy`; `sz_string_erase` removes a range without ever allocating and cannot fail. ```c #include #include int main(void) { sz_allocator_t allocator; if (sz_allocator_init_heap(&allocator) != sz_success_k) return 1; sz_string_t s; sz_string_init(&s); sz_ptr_t room = sz_string_expand(&s, 0, 5, &allocator); // 5-byte gap at offset 0 if (!room) return 1; memcpy(room, "hello", 5); sz_ptr_t start; sz_size_t length; sz_string_range(&s, &start, &length); assert(length == 5); sz_string_free(&s, &allocator); return 0; } ``` `#include ` `#include ` `#include ` `#include ` `#include ` `#include ` ## sz_strings_crecords_t Where every record of an array keeps its string, the handle of [`sz_strings_from_records`](#sz_strings_from_records) and [`sz_strings_from_record_pointers`](#sz_strings_from_record_pointers). ```c struct sz_strings_crecords_t ``` - `records` `void const *`: The first record, or the first pointer to a record. - `stride` `sz_size_t`: Bytes between consecutive records, or between consecutive record pointers. - `start_member` `sz_size_t`: Byte offset of the `sz_cptr_t` member pointing at the string inside a record. - `length_member` `sz_size_t`: Byte offset of the `[sz_size_t](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_size_t)` member holding the string length inside a record. ## sz_strings_crows_t Read-only NUL-padded rows, like NumPy `S` arrays or `char` fields of structs, each string ending before its row's trailing NUL bytes. ```c struct sz_strings_crows_t ``` - `data` `sz_cptr_t`: The first row. - `stride` `sz_size_t`: Bytes between the starts of consecutive rows, at least `width`. - `width` `sz_size_t`: Bytes in every row. ## sz_strings_rows_t Writable NUL-padded rows, laid out like `[sz_strings_crows_t](#sz_strings_crows_t)`. ```c struct sz_strings_rows_t ``` - `data` `sz_ptr_t`: The first row. - `stride` `sz_size_t`: Bytes between the starts of consecutive rows, at least `width`. - `width` `sz_size_t`: Bytes in every row. ## sz_kernel_fill_random_t Signature of the [`sz_fill_random_best`](#sz_fill_random_best) kernels. ```c typedef sz_status_t(*) sz_kernel_fill_random_t(sz_ptr_t, sz_size_t, sz_u64_t, sz_stream_t); ``` ## sz_kernel_strings_to_tape_t Signature of the [`sz_strings_to_tape_best`](#sz_strings_to_tape_best) kernels. ```c typedef sz_status_t(*) sz_kernel_strings_to_tape_t(sz_strings_view_t const *, sz_size_t const *, sz_size_t, sz_allocator_t *, sz_strings_span_t *, sz_stream_t); ``` ## sz_kernel_strings_to_rows_t Signature of the [`sz_strings_to_rows_best`](#sz_strings_to_rows_best) kernels. ```c typedef sz_status_t(*) sz_kernel_strings_to_rows_t(sz_strings_view_t const *, sz_size_t const *, sz_size_t, sz_strings_rows_t const *, sz_size_t *, sz_stream_t); ``` ## sz_kernel_sort_order_t Signature of the [`sz_sort_order_best`](#sz_sort_order_best) and [`sz_sort_uncased_order_best`](#sz_sort_uncased_order_best) kernels. ```c typedef sz_status_t(*) sz_kernel_sort_order_t(sz_strings_view_t const *, sz_size_t, sz_bool_t, sz_allocator_t *, sz_size_t *, sz_stream_t); ``` ## sz_kernel_intersect_t Signature of the [`sz_intersect_best`](#sz_intersect_best) kernels. ```c typedef sz_status_t(*) sz_kernel_intersect_t(sz_strings_view_t const *, sz_strings_view_t const *, sz_allocator_t *, sz_u64_t, sz_size_t *, sz_size_t *, sz_size_t *, sz_stream_t); ``` ## sz_escape_kind_t The text formats that the escape and unescape families convert strings to and from. ```c enum sz_escape_kind_t ``` - `sz_escape_json_k` = `0`: RFC 8259 string bodies: `\"`, `\\`, short forms like `\n`, and `\u00XX` for other bytes below 0x20. - `sz_escape_hex_k` = `1`: Two lowercase hexadecimal digits per byte, decoding either case. - `sz_escape_html_k` = `2`: HTML and XML text and attribute values: `&`, `<`, `>`, `"` and `'`. - `sz_escape_url_k` = `3`: RFC 3986 percent-encoding of every byte outside `A-Z a-z 0-9 - _ ~` and the dot. - `sz_escape_console_k` = `4`: Terminal-safe logs: short forms like `\n`, `\\` and `\"`, `\xHH` for other C0 control bytes, DEL and ill-formed UTF-8, and `\uXXXX` for C1 controls and the bidirectional overrides U+202A to U+202E and U+2066 to U+2069, which reorder what a reader sees. - `sz_escape_csv_k` = `5`: RFC 4180 fields, quoted only when holding a comma, a quote, CR or LF, with every inner quote doubled. - `sz_escape_json_ascii_k` = `6`: RFC 8259 string bodies in ASCII alone, as Python's `json.dumps` writes them by default: every codepoint outside printable ASCII without a short form, DEL included, becomes `\uXXXX`, a surrogate pair beyond the Basic Multilingual Plane, and every ill-formed byte becomes the escape of U+FFFD. ## sz_kernel_strings_escape_t Signature of the [`sz_strings_escape_best`](#sz_strings_escape_best) kernels, kept beside the enum it takes. ```c typedef sz_status_t(*) sz_kernel_strings_escape_t(sz_strings_view_t const *, sz_size_t const *, sz_size_t, sz_escape_kind_t, sz_allocator_t *, sz_strings_span_t *, sz_stream_t); ``` ## sz_kernel_strings_unescape_t Signature of the [`sz_strings_unescape_best`](#sz_strings_unescape_best) kernels, kept beside the enum it takes. ```c typedef sz_status_t(*) sz_kernel_strings_unescape_t(sz_strings_view_t const *, sz_size_t const *, sz_size_t, sz_escape_kind_t, sz_allocator_t *, sz_strings_span_t *, sz_size_t *, sz_stream_t); ``` ## sz_join_semantics_t Defines various JOIN semantics for string collections, including handling of duplicates. ```c enum sz_join_semantics_t ``` - `sz_join_inner_strict_k` = `0`: Strict inner join with uniqueness enforcement. - `sz_join_inner_k` = `1`: Conventional inner join allowing duplicate entries. - `sz_join_left_outer_k` = `2`: Left outer join preserving all entries from the first sequence. - `sz_join_right_outer_k` = `3`: Right outer join preserving all entries from the second sequence. - `sz_join_full_outer_k` = `4`: Full outer join combining all entries from both sequences. - `sz_join_cross_k` = `5`: Cross join (Cartesian product) of two sequences. See also: [sz_join_inner_strict_k](#sz_join_inner_strict_k), [sz_join_inner_k](#sz_join_inner_k), [sz_join_left_outer_k](#sz_join_left_outer_k), [sz_join_right_outer_k](#sz_join_right_outer_k), [sz_join_full_outer_k](#sz_join_full_outer_k), [sz_join_cross_k](#sz_join_cross_k) ## sz_strings_from_records Describes the string members of fixed-stride records, like an array of structs that each hold a pointer and a length. ```c void sz_strings_from_records( sz_strings_crecords_t const *records, sz_size_t count, sz_strings_view_t *strings); ``` - `records` (in): Where the members sit, which must outlive `strings`. - `count` (in): Number of records. - `strings` (out): The accessor-backed collection to initialize. ## sz_strings_from_record_pointers Describes the string members of records reached through an array of pointers, like the nodes a query over a parsed tree returns. ```c void sz_strings_from_record_pointers( sz_strings_crecords_t const *records, sz_size_t count, sz_strings_view_t *strings); ``` - `records` (in): Where the pointers and members sit, which must outlive `strings`. - `count` (in): Number of record pointers. - `strings` (out): The accessor-backed collection to initialize. ## sz_strings_from_rows Describes NUL-padded rows, trimming the trailing NUL bytes of every row. ```c void sz_strings_from_rows( sz_strings_crows_t const *rows, sz_size_t count, sz_strings_view_t *strings); ``` - `rows` (in): Where the rows sit, which must outlive `strings`. - `count` (in): Number of rows. - `strings` (out): The accessor-backed collection to initialize. ## sz_strings_permute Reorders `strings` by the order [`sz_sort_order_best`](#sz_sort_order_best) emits, copying no bytes. ```c void sz_strings_permute( sz_strings_view_t const *strings, sz_size_t const *order, sz_size_t count, sz_string_view_t *views, sz_strings_view_t *permuted); ``` - `strings` (in): The collection to reorder, which must outlive `permuted`. - `order` (in): Indices into `strings`, possibly fewer than all of them. - `count` (in): Number of indices in `order`. - `views` (out): Receives the view of `strings[order[i]]` for each index. - `permuted` (out): Points its accessor at `views`. ## sz_strings_to_tape_best Gathers `strings[order[i]]`, or the first `count` strings without `order`, into a tape. ```c sz_status_t sz_strings_to_tape_best( sz_strings_view_t const *strings, sz_size_t const *order, sz_size_t count, sz_allocator_t *allocator, sz_strings_span_t *tape, sz_capability_t capabilities, sz_stream_t stream); ``` - `sz_strings_to_tape` backends: serial, haswell, icelake, neon, sve, rvv, v128, v128relaxed, loongsonasx, powervsx, cuda, rocm, metal Reads any layout, so it turns accessor-backed strings, slices and permutations into a tape that GPU kernels and Apache Arrow read directly. The payload and the offsets are two blocks, exactly as large as they must be, with 32-bit offsets while the payload fits in 4 GiB and 64-bit beyond. Every collection verb is atomic: it succeeds and leaves `tape` holding the whole result, or it fails and leaves `tape`, its blocks and their bytes as they were. Blocks of exactly the sizes the result needs are written in place, so a borrowed span of the right sizes needs no allocator; any other `tape` receives fresh blocks from `allocator`, and its old ones go back only once the result is written. A whole tape gathered onto itself is left as it is. - `strings` (in): The strings to gather, in any layout. - `order` (in): Indices into `strings`, possibly repeated, or null for the first `count`. - `count` (in): Number of strings to write. - `allocator` (in): Where the blocks of `tape` come from and return to. - `tape` (inout): A zeroed span, one an earlier call produced, or the one `strings` views. - `capabilities` (in): One device's capabilities, like `sz_capabilities_enabled_cpu` reports. - `stream` (in): Null on the CPU, or the GPU stream of that device to queue on. Notes: A GPU call reads the payload size back before allocating, synchronizing `stream` once. ## sz_strings_to_rows_best Writes `strings[order[i]]`, or the first `count` strings, into NUL-padded rows. ```c sz_status_t sz_strings_to_rows_best( sz_strings_view_t const *strings, sz_size_t const *order, sz_size_t count, sz_strings_rows_t const *rows, sz_size_t *longest, sz_capability_t capabilities, sz_stream_t stream); ``` - `sz_strings_to_rows` backends: serial, haswell, icelake, neon, sve, rvv, v128, v128relaxed, loongsonasx, powervsx, cuda, rocm, metal - `strings` (in): The strings to write, in any layout. - `order` (in): Indices into `strings`, possibly repeated, or null for the first `count`. - `count` (in): Number of rows to write. - `rows` (in): Room for `count` rows, each truncating a longer string at its width. - `longest` (out): Length of the longest string, to retry with wider rows. - `capabilities` (in): One device's capabilities, like `sz_capabilities_enabled_cpu` reports. - `stream` (in): Null on the CPU, or the GPU stream of that device to queue on. Statuses: - [`sz_missing_kernel_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_missing_kernel_k) No capability in `capabilities` has it. ## sz_strings_escape_best Escapes `strings[order[i]]`, or the first `count` strings, for `kind` into a tape. ```c sz_status_t sz_strings_escape_best( sz_strings_view_t const *strings, sz_size_t const *order, sz_size_t count, sz_escape_kind_t kind, sz_allocator_t *allocator, sz_strings_span_t *tape, sz_capability_t capabilities, sz_stream_t stream); ``` - `sz_strings_escape` backends: serial, haswell, icelake, neon, sve, rvv, v128, v128relaxed, loongsonasx, powervsx, cuda, rocm, metal Allocates and reuses `tape` like [`sz_strings_to_tape_best`](#sz_strings_to_tape_best). When `strings` views all of `tape`, its payload block grows first, through `reallocate` when the allocator has one, then its bytes move to the end and escape front to back, the writer never overtaking unread bytes. - `strings` (in): The strings to escape, in any layout. - `order` (in): Indices into `strings`, possibly repeated, or null for the first `count`. - `count` (in): Number of strings to write. - `kind` (in): The format to escape for. - `allocator` (in): Where the blocks of `tape` come from and return to. - `tape` (inout): A zeroed span, one an earlier call produced, or the one `strings` views. - `capabilities` (in): One device's capabilities, like `sz_capabilities_enabled_cpu` reports. - `stream` (in): Null on the CPU, or the GPU stream of that device to queue on. ## sz_strings_unescape_best Unescapes `strings[order[i]]`, or the first `count` strings, from `kind` into a tape. ```c sz_status_t sz_strings_unescape_best( sz_strings_view_t const *strings, sz_size_t const *order, sz_size_t count, sz_escape_kind_t kind, sz_allocator_t *allocator, sz_strings_span_t *tape, sz_size_t *malformed_index, sz_capability_t capabilities, sz_stream_t stream); ``` - `sz_strings_unescape` backends: serial, haswell, icelake, neon, sve, rvv, v128, v128relaxed, loongsonasx, powervsx, cuda, rocm, metal Allocates and reuses `tape` like [`sz_strings_to_tape_best`](#sz_strings_to_tape_best). Every string is checked before anything is written, so one malformed string leaves `tape` as it was. - `strings` (in): The strings to unescape, in any layout. - `order` (in): Indices into `strings`, possibly repeated, or null for the first `count`. - `count` (in): Number of strings to write. - `kind` (in): The format to unescape from. - `allocator` (in): Where the blocks of `tape` come from and return to. - `tape` (inout): A zeroed span, one an earlier call produced, or the one `strings` views. - `malformed_index` (out): The first string holding a malformed sequence, on failure. - `capabilities` (in): One device's capabilities, like `sz_capabilities_enabled_cpu` reports. - `stream` (in): Null on the CPU, or the GPU stream of that device to queue on. Statuses: - [`sz_invalid_utf8_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_invalid_utf8_k) A malformed sequence. ## sz_strings_find_kernel Finds the strings kernel of `kind`, from the best of `capabilities`. ```c sz_status_t sz_strings_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. ## sz_fill_random_best A Pseudorandom Number Generator (PRNG), inspired by the AES-CTR-128 algorithm, but using only one round of AES mixing as opposed to "NIST SP 800-90A". ```c sz_status_t sz_fill_random_best( sz_ptr_t target, sz_size_t length, sz_u64_t nonce, sz_capability_t capabilities, sz_stream_t stream); ``` - `sz_fill_random` backends: serial, westmere, skylake, icelake, neonaes, sve2aes, rvv, rvvcrypto, v128, v128relaxed, loongsonasx, powervsx CTR_DRBG (CounTeR mode Deterministic Random Bit Generator) appears secure and indistinguishable from a true random source when AES is used as the underlying block cipher and 112 bits are taken from this PRNG. When AES is used as the underlying block cipher and 128 bits are taken from each instantiation, the required security level is delivered with the caveat that a 128-bit cipher's output in counter mode can be distinguished from a true RNG. In this case, it doesn't apply, as we only use one round of AES mixing. We also don't expose a separate "key", only a "nonce", to keep the API simple, but we mix it with 512 bits of Pi constants to increase randomness. Filling two buffers under the same nonce: ``` #include int main() { sz_capability_t capabilities; char first_buffer[5], second_buffer[5]; sz_u64_t first_checksum, second_checksum; sz_capabilities_enabled_cpu(&capabilities); sz_fill_random_best(first_buffer, 5, 0, capabilities, NULL); sz_fill_random_best(second_buffer, 5, 0, capabilities, NULL); // ? Same nonce, same output sz_bytesum_best(first_buffer, 5, &first_checksum, capabilities, NULL); sz_bytesum_best(second_buffer, 5, &second_checksum, capabilities, NULL); return first_checksum == second_checksum ? 0 : 1; } ``` - `target` (out): Output string buffer to be populated. - `length` (in): Number of bytes in the string. - `nonce` (in): "Number used once" to ensure uniqueness of produced blocks. - `capabilities` (in): One device's capabilities, like `sz_capabilities_enabled_cpu` reports. - `stream` (in): Null on the CPU, or the GPU stream of that device to queue on. See also: sz_fill_random_serial, sz_fill_random_westmere, sz_fill_random_skylake, sz_fill_random_icelake, sz_fill_random_neonaes, sz_fill_random_sve2aes, sz_fill_random_rvv, sz_fill_random_rvvcrypto, sz_fill_random_v128, sz_fill_random_v128relaxed, sz_fill_random_loongsonasx, sz_fill_random_powervsx Statuses: - [`sz_missing_kernel_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_missing_kernel_k) No capability in `capabilities` has it. ## sz_sort_order_best Faster __stable__ arg-sort for an arbitrary __string__ collection, using QuickSort. ```c sz_status_t sz_sort_order_best( sz_strings_view_t const *strings, sz_size_t top_count, sz_bool_t reverse, sz_allocator_t *allocator, sz_size_t *order, sz_capability_t capabilities, sz_stream_t stream); ``` - `sz_sort_order` backends: serial, haswell, skylake, sve, neon, rvv Outputs the `order` of elements in the immutable `strings`, that would sort them. For example, sorting three fruit names: ``` #include int main() { char const *fruits[] = {"banana", "apple", "cherry"}; sz_strings_view_t strings; sz_strings_from_null_terminated_strings(fruits, 3, &strings); sz_capability_t capabilities; sz_capabilities_enabled_cpu(&capabilities); sz_size_t order[3]; sz_status_t status = sz_sort_order_best(&strings, 0, sz_false_k, NULL, order, capabilities, NULL); return status == sz_success_k && order[0] == 1 && order[1] == 0 && order[2] == 2 ? 0 : 1; } ``` - `strings` (in): Immutable collection of strings to sort, in any layout. - `top_count` (in): Number of leading elements to fully order, or 0 to sort all of them. - `reverse` (in): Whether to sort in descending order. - `allocator` (in): Optional memory allocator for temporary storage. - `order` (out): Output permutation that sorts the elements. - `capabilities` (in): One device's capabilities, like `sz_capabilities_enabled_cpu` reports. - `stream` (in): Null on the CPU, or the GPU stream of that device to queue on. Preconditions: The `order` array must fit at least as many integers as `strings` holds. Postconditions: The `order` array will contain a valid permutation of all indices of `strings`. Postconditions: If `top_count` is non-zero and smaller than the count, only the first `top_count` entries are sorted; the rest are an arbitrary permutation of the leftover indices. Notes: Takes linear memory, quadratic worst-case and log-linear average time. See also: Quicksort: [https://en.wikipedia.org/wiki/Quicksort](https://en.wikipedia.org/wiki/Quicksort) Notes: This algorithm is __stable:__ equal elements keep their relative order, ascending by index. See also: sz_sort_order_serial, sz_sort_order_haswell, sz_sort_order_skylake, sz_sort_order_neon, sz_sort_order_sve, sz_sort_order_rvv See also: [sz_sort_uncased_order_best](#sz_sort_uncased_order_best) Statuses: - [`sz_missing_kernel_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_missing_kernel_k) No capability in `capabilities` has it. ## sz_sort_uncased_order_best Faster __stable__ __uncased__ arg-sort for a UTF-8 __string__ collection, using QuickSort. ```c sz_status_t sz_sort_uncased_order_best( sz_strings_view_t const *strings, sz_size_t top_count, sz_bool_t reverse, sz_allocator_t *allocator, sz_size_t *order, sz_capability_t capabilities, sz_stream_t stream); ``` - `sz_sort_uncased_order` backends: serial, haswell, skylake, sve, neon, rvv Orders strings under Unicode case-folding, equivalent to folding every string and sorting the folded bytes lexicographically - but folding only small chunks on the fly, never materializing a fully pre-folded copy of the collection. Malformed UTF-8 is handled losslessly: any byte that does not begin a well-formed codepoint is compared and sorted by its raw byte value as a single one-byte unit, and decoding resyncs at the next byte. The result stays a total, deterministic order; valid input sorts byte-identically. - `strings` (in): Immutable collection of UTF-8 strings to sort, in any layout. - `top_count` (in): Number of leading elements to fully order, or 0 to sort all of them. - `reverse` (in): Whether to sort in descending order. - `allocator` (in): Optional memory allocator for temporary storage. - `order` (out): Output permutation that sorts the elements. - `capabilities` (in): One device's capabilities, like `sz_capabilities_enabled_cpu` reports. - `stream` (in): Null on the CPU, or the GPU stream of that device to queue on. Preconditions: The `order` array must fit at least as many integers as `strings` holds. Postconditions: The `order` array will contain a valid permutation of all indices of `strings`. Notes: This algorithm is __stable:__ case-folded-equal elements keep their input order. See also: sz_utf8_uncased_fold, sz_utf8_uncased_order See also: sz_sort_uncased_order_serial Statuses: - [`sz_missing_kernel_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_missing_kernel_k) No capability in `capabilities` has it. ## sz_sort_find_kernel Finds the sorting kernel of `kind`, from the best of `capabilities`. ```c sz_status_t sz_sort_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. ## sz_intersect_best Intersects two binary __string__ collections, using a hash table. ```c sz_status_t sz_intersect_best( sz_strings_view_t const *first_strings, sz_strings_view_t const *second_strings, sz_allocator_t *allocator, sz_u64_t seed, sz_size_t *intersection_count, sz_size_t *first_positions, sz_size_t *second_positions, sz_capability_t capabilities, sz_stream_t stream); ``` - `sz_intersect` backends: serial, westmere, icelake, neonaes Outputs the `first_positions` from the `first_strings` and `second_positions` from the `second_strings`, that contain matched strings. Missing matches are represented as `STRINGZILLA_SIZE_MAX`. Tolerates duplicate strings within either collection: each distinct shared value is emitted exactly once, a distinct-set intersection, so `intersection_count` never exceeds the smaller of the two counts and can't overflow the output arrays. For example, intersecting two small collections of fruit names: ``` #include int main() { char const *first[] = {"banana", "apple", "cherry"}; char const *second[] = {"cherry", "orange", "pineapple", "banana"}; sz_strings_view_t first_strings, second_strings; sz_strings_from_null_terminated_strings(first, 3, &first_strings); sz_strings_from_null_terminated_strings(second, 4, &second_strings); sz_capability_t capabilities; sz_capabilities_enabled_cpu(&capabilities); sz_size_t intersection_count; sz_size_t first_positions[3], second_positions[3]; //? The smaller collection's size sz_status_t status = sz_intersect_best(&first_strings, &second_strings, NULL, 0, &intersection_count, first_positions, second_positions, capabilities, NULL); return status == sz_success_k && intersection_count == 2 ? 0 : 1; } ``` - `first_strings` (in): First immutable collection of strings to intersect, in any layout. - `second_strings` (in): Second immutable collection of strings to intersect, in any layout. - `allocator` (in): Optional memory allocator for temporary storage. - `seed` (in): Optional seed for the hash table to avoid attacks. - `intersection_count` (out): Number of matching strings in both collections. - `first_positions` (out): Offset positions of the matching strings from the `first_strings`. - `second_positions` (out): Offset positions of the matching strings from `second_strings`. - `capabilities` (in): One device's capabilities, like `sz_capabilities_enabled_cpu` reports. - `stream` (in): Null on the CPU, or the GPU stream of that device to queue on. Preconditions: The `first_positions` array must fit as many items as the smaller collection holds. Preconditions: The `second_positions` array must fit as many items as the smaller collection holds. Notes: The algorithm has linear memory complexity and linear time complexity. See also: SQL joins: [https://en.wikipedia.org/wiki/Join_(SQL)](https://en.wikipedia.org/wiki/Join_(SQL)) See also: sz_intersect_serial, sz_intersect_westmere, sz_intersect_icelake, sz_intersect_neonaes Statuses: - [`sz_missing_kernel_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_missing_kernel_k) No capability in `capabilities` has it. ## sz_intersect_find_kernel Finds the intersection kernel of `kind`, from the best of `capabilities`. ```c sz_status_t sz_intersect_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.