Case Folding and Normalization

sz_normal_form_nfkc_casefold_k gives the keys search engines match on: NFKC with full case folding and without default-ignorable codepoints, the Unicode toNFKC_Casefold.

On the CPU every string is normalized once, into blocks of the call's own from allocator: a payload starting at the total input length, grown through reallocate when the allocator has one, and fitted to its exact size at the end. That needs an allocator even when tape holds blocks of exactly the final sizes, which are then filled rather than replaced. Like every collection verb it is atomic. GPUs measure first and read only tapes, a string to a thread.

Case folding normalizes text for uncased comparisons by mapping uppercase letters to their lowercase equivalents and handling special expansions defined in Unicode CaseFolding.txt.

Buffer Sizing

The target buffer must be at least source_length * 3 bytes to guarantee sufficient space for worst-case expansion. The maximum expansion ratio is 3:1, which occurs with Greek characters that expand to three codepoints under case folding. For example, 'ΐ' (U+0390, CE 90) folds to "ΐ" (U+03B9 U+0308 U+0301, CE B9 CC 88 CC 81), so 2 bytes → 6 bytes, and a string of N such characters expands from 2N to 6N bytes.

Malformed UTF-8 is handled losslessly: any byte that does not begin a well-formed codepoint is copied through unchanged (it folds to itself) and folding resyncs at the next byte. Valid UTF-8 folds as usual. Basic usage:

char const *source = "HELLO";
char target[15]; // 5 * 3, a safe overestimate
sz_capability_t capabilities;
sz_capabilities_enabled_cpu(&capabilities);
sz_size_t target_length;
sz_utf8_uncased_fold_best(source, 5, target, &target_length, capabilities, NULL);
// target now contains "hello", target_length = 5

On CUDA, ROCm and Metal, folding queues on stream, which names the device: the source, the target and the length slot must all be memory that device reaches, and the length lands once stream is joined, the call itself allocating nothing and joining nothing.

Picks the per-script search kernel and the probe positions it matches on, so that sz_utf8_uncased_search_best never re-analyses the needle. The prepared needle points at needle rather than copying it, so the needle must outlive it:

sz_utf8_uncased_needle_t prepared;
sz_utf8_uncased_needle_init_best("STRASSE", 7, &prepared, capabilities, STRINGZILLA_NULL);
sz_cptr_t match;
sz_size_t match_length;
sz_utf8_uncased_search_best("die Straße", 11, &prepared, &match, &match_length, capabilities,
                            STRINGZILLA_NULL);
// match points at "Straße", match_length == 7

In applications where the haystack remains largely static and memory/storage is cheap, it is recommended to pre-process the haystack into a case-folded version using Unicode Case Folding (e.g., via the ICU library) and subsequently use the simpler sz_find_best function for repeated searches, which avoids performing the full folding logic during every search.

This function applies full Unicode Case Folding as defined in the Unicode Standard (UAX #21 and CaseFolding.txt), covering all bicameral scripts, all offset-based one-to-one folds, all table-based one-to-one folds, and all normative one-to-many expansions. It doesn't however perform any normalization, like NFKC or NFC, so combining marks are treated as-is. StringZilla is intentionally locale-independent: case folding produces identical results regardless of runtime locale settings, ensuring deterministic behavior across platforms and simplifying use in multi-threaded and distributed systems.

The following character mappings are supported:

• ASCII Latin letters A–Z (U+0041–U+005A) are folded to a–z (U+0061–U+007A) using a trivial +32 offset.
• Fullwidth Latin letters Ａ–Ｚ (U+FF21–U+FF3A) are folded to ａ–ｚ (U+FF41–U+FF5A) with the same +32 offset.
• Cyrillic uppercase А–Я (U+0410–U+042F) are folded to а–я (U+0430–U+044F) using a +32 offset.
• Armenian uppercase Ա–Ֆ (U+0531–U+0556) are folded to ա–ֆ (U+0561–U+0586) using a +48 offset.
• Georgian Mtavruli letters Ა-Ჿ (U+1C90–U+1CBF, excluding 2) are folded to their Mkhedruli equivalents (U+10D0–U+10FF) using a fixed linear translation defined by the Unicode Standard.
• Greek uppercase Α–Ω (U+0391–U+03A9) are folded to α–ω (U+03B1–U+03C9) via a +32 offset. Both Σ (U+03A3) and ς (U+03C2, final sigma) fold to σ (U+03C3) for consistent matching.

• Latin Extended characters include numerous one-to-one folds, mixed-case digraphs and trigraphs normalized to lowercase sequences, and one-to-many expansions like:

  • 'ß' (U+00DF, C3 9F) → "ss" (U+0073 U+0073, 73 73)
  • 'ẞ' (U+1E9E, E1 BA 9E) → "ss" (U+0073 U+0073, 73 73)

• Turkic dotted/dotless-I characters are handled per Unicode Case Folding (not locale-specific):

  • 'İ' (U+0130, C4 B0) → "i̇" (U+0069 U+0307, 69 CC 87) — Full case folding with combining dot
  • 'I' (U+0049, 49) → 'i' (U+0069, 69) — Standard folding (not Turkic 'I' (U+0049, 49) → 'ı' (U+0131, C4 B1))
  • 'ı' (U+0131, C4 B1) → 'ı' (U+0131, C4 B1) — Already lowercase, unchanged
• Lithuanian accented I/J characters with combining dots are processed as multi-codepoint expansions per CaseFolding.txt.
• Additional bicameral scripts, Cherokee, Deseret, Osage, Warang Citi, and Adlam, use their normative one-to-one uppercase-to-lowercase mappings defined in CaseFolding.txt.

Folding is applied during matching without rewriting the entire haystack. Multi-codepoint expansions, contextual folds, and combining-mark adjustments are handled at comparison time.

Algorithmic Considerations

Uncased search with full Unicode case folding is fundamentally harder than byte-level search because one-to-many expansions (e.g., 'ß' (U+00DF, C3 9F) → "ss" (U+0073 U+0073, 73 73)) break core assumptions of fast string algorithms:

• Boyer-Moore/Horspool skip tables assume 1:1 character mapping
• Two-Way critical factorization assumes fixed pattern length
• Rabin-Karp rolling hash assumes fixed character widths
• Volnitsky bigram hashing assumes consistent byte patterns

Industry approaches vary:

• ICU abandoned Boyer-Moore for Unicode, reverting to linear search for correctness
• ClickHouse uses Volnitsky with fallback to naive search for problematic characters
• RipGrep uses simple case folding only (no expansion handling) leveraging the Rust RegEx engine

StringZilla implements several algorithms. Most importantly it first locates the longest expansion-free slice of the needle to locate against.

The references below cover ICU's abandonment of Boyer-Moore for Unicode, ClickHouse's hash-based Volnitsky search with UTF-8 case folding, glibc's O(n) time and O(1) space Two-Way matcher, and the uncased search of the uni-algo Unicode algorithms library.

Malformed UTF-8 is handled losslessly: any byte that does not begin a well-formed codepoint is matched byte-for-byte as a single literal byte (never as a Unicode codepoint) and processing resyncs at the next byte, so a search over invalid input is well-defined and identical across all backends.

Compares strings using Unicode case folding rules, producing consistent ordering regardless of letter case. Implements the same full Unicode Case Folding as sz_utf8_uncased_fold_best, including all one-to-many expansions (e.g. 'ß' (U+00DF, C3 9F) → "ss" (U+0073 U+0073, 73 73)) and bicameral script mappings.

Unlike simple byte comparison, this function correctly handles multi-byte UTF-8 sequences and expansion characters. Comparison is performed codepoint-by-codepoint after folding, not byte-by-byte, ensuring linguistically correct results.

Malformed UTF-8 is handled losslessly: any byte that does not begin a well-formed codepoint is treated as a single literal byte (folded to itself and compared byte-for-byte, never as a Unicode codepoint), and processing resyncs at the next byte. All uncased operations - find, order, and violation - share this contract, so results on invalid input are well-defined and consistent across backends. Basic usage:

sz_capability_t capabilities;
sz_capabilities_enabled_cpu(&capabilities);
sz_ordering_t ordering;
sz_utf8_uncased_order_best("Hello", 5, "HELLO", 5, &ordering, capabilities, STRINGZILLA_NULL);
// ordering == sz_equal_k

sz_utf8_uncased_order_best("straße", 7, "STRASSE", 7, &ordering, capabilities, STRINGZILLA_NULL);
// ordering == sz_equal_k ('ß' (U+00DF, C3 9F) → "ss" (U+0073 U+0073, 73 73))

A codepoint is case-agnostic, or caseless, if all three conditions are true:

1. Self-folding: case folding produces exactly the original codepoint.
2. Not bicameral: it does not belong to any script with case distinctions.
3. Not an expansion target: it appears in no multi-rune case fold expansion.

The third condition is subtle but critical. Consider 'ʾ' (U+02BE, CA BE):

• It has no case variant and folds to itself.
• However, 'ẚ' (U+1E9A, E1 BA 9A) → "aʾ" (U+0061 U+02BE, 61 CA BE).
• A needle containing 'ʾ' must match at position 1 of the folded expansion of 'ẚ'.
• Binary search cannot handle this, so 'ʾ' must not be case-agnostic.

Case-agnostic scripts include: CJK ideographs, Hangul, digits, punctuation, most symbols, Hebrew, Arabic, Thai, Hindi (Devanagari), and many other scripts without case distinctions.

The function is conservative: it reports any codepoint that participates in case folding, even if the specific instance wouldn't change. For example, lowercase 'a' is reported because it's a case-folding target.

Use Case

This function enables an important optimization: if both haystack and needle are fully case-agnostic, then sz_find_best can be used directly instead of the slower sz_utf8_uncased_search_best. This is particularly valuable for:

• CJK text (Chinese, Japanese, Korean) - always caseless
• Numeric data and punctuation-heavy content
• Middle Eastern scripts (Arabic, Hebrew, Persian)
• South/Southeast Asian scripts (Thai, Hindi, Vietnamese without Latin)

The optimization pattern:

sz_cptr_t haystack = "价格：¥1234";  // Chinese + punctuation + digits
sz_cptr_t needle = "¥1234";
sz_cptr_t haystack_cased, needle_cased, match;
sz_utf8_find_cased_best(haystack, haystack_length, &haystack_cased, capabilities, STRINGZILLA_NULL);
sz_utf8_find_cased_best(needle, needle_length, &needle_cased, capabilities, STRINGZILLA_NULL);

if (!haystack_cased && !needle_cased) {
    // Fast path: both strings are fully caseless, so use binary search
    sz_find_best(haystack, haystack_length, needle, needle_length, &match, capabilities, STRINGZILLA_NULL);
} else {
    // Slow path: full uncased search
    sz_utf8_uncased_needle_t prepared;
    sz_size_t match_length;
    sz_utf8_uncased_needle_init_best(needle, needle_length, &prepared, capabilities, STRINGZILLA_NULL);
    sz_utf8_uncased_search_best(haystack, haystack_length, &prepared, &match, &match_length, capabilities,
                                STRINGZILLA_NULL);
}

Buffer Sizing

Decomposition forms (NFD, NFKD) can expand the input; the target must hold up to source_length * 18 bytes for the worst single-codepoint compatibility decomposition. The composing forms (NFC, NFKC) never exceed the decomposed length, so the same bound is safe. NFKC_Casefold grows a byte into 11 at most, for U+FDFA, within the same bound.

Malformed UTF-8 is handled losslessly: any byte that does not begin a well-formed codepoint is an opaque 1-byte barrier - it is passed through unchanged, does not decompose, compose, or take part in canonical ordering, and processing resyncs at the next byte. NFKC_Casefold keeps the default ignorable right after such a byte, which erased would let it fuse with the bytes beyond.

On CUDA, ROCm and Metal normalization is enqueued on stream, which names the device: the source, target and length slot must be memory that device reaches, and the length lands once stream is joined. Calls allocate no output or scratch and join nothing. CUDA and ROCm copy the shared normalization tables to the device ahead of the kernel; Metal embeds them in its compiled library and requires buffers from sz_allocator_init_unified_metal.

Malformed UTF-8 is treated losslessly: any byte that does not begin a well-formed codepoint is an opaque, inert 1-byte barrier (never a violation), and the scan resyncs at the next byte.