mmo-ref/tinymux
1
0
Fork 0
mirror of https://github.com/brazilofmux/tinymux synced 2026-08-13 00:23:11 -04:00
Code Issues Projects Releases Packages Wiki Activity
tinymux/mux/lib/utf8_collate.cpp
Stephen Dennis 665ac71c6e Fix UTF-8 property DFA readers to stop at the first accepting state 
The generated tables (utf/integers) prune any state whose paths all lead
to a single accepting value into that accepting state directly, so the
DFA can accept before a code point's final byte.  Readers that consumed
all bytes and then checked the final state transitioned back out of the
accepting state into an unrelated one -- e.g. strlen(CJK CJK) returned 1
because a CJK ideograph (Other) was misread as Extend and attached to the
previous cluster.

Stop at the first accepting state, the way ConsoleWidth already did, in
RunIntegerDFA_GCB and IsExtPict (utf8_grapheme.cpp), GetDUCET
(utf8_collate.cpp), and run_dfa (color_ops.rl, used on both host and the
rv64 JIT).  The committed tables are valid pruned DFAs; no regeneration
is required.

Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>
2026-06-04 12:11:00 -05:00

1447 lines
42 KiB
C++
Raw Permalink Blame History

/*! \file utf8_collate.cpp
* \brief Unicode Collation Algorithm (UCA) implementation per UTS #10.
*
* Provides linguistically correct string comparison using the Default
* Unicode Collation Element Table (DUCET) from Unicode 16.0.
*
* All lookups use DFA state machines generated by integers.exe and
* pairs.exe. Implicit weights for CJK and unassigned code points
* are computed algorithmically per UCA Section 10.1.
*
* Performance optimizations:
* - Latin CE cache for U+0000..U+017F (single table lookup per char)
* - FastLatinCmp/FastLatinCmpCI for Latin-only strings
* - ASCII byte-skip loop in FastLatinCmp
* - CJK inline implicit weights in CollectCEsBounded
* - Bounded CE collection with streaming overflow fallback
* - memcmp equality check at top of cmp functions
*/
#include "copyright.h"
#include "autoconf.h"
#include "config.h"
#include "core.h"
#include <atomic>
#include <cstring>
#include "ducet_cetable.h"
// ---------------------------------------------------------------------------
// CE weight unpacking from uint32_t.
//
// Packed format:
// Bit 31: variable flag
// Bits 30-16: primary weight (15 bits)
// Bits 15-5: secondary weight (11 bits)
// Bits 4-0: tertiary weight (5 bits)
// ---------------------------------------------------------------------------
#define CE_PRIMARY(w) (((w) >> 16) & 0x7FFF)
#define CE_SECONDARY(w) (((w) >> 5) & 0x07FF)
#define CE_TERTIARY(w) ((w) & 0x1F)
#define CE_VARIABLE(w) (((w) >> 31) & 1)
// Per-code-point CE scratch space.
// DUCET mappings are short; comparison and sortkey generation stream the
// input and only need to hold the current character's CE sequence.
//
#define MAX_CHAR_CES 64
#define MAX_CMP_CES 256
#define MAX_SORTKEY_CES 4096
// ---------------------------------------------------------------------------
// DFA lookup: single code point -> CE index.
// Returns 0 if not in DUCET (use implicit weights).
// ---------------------------------------------------------------------------
static int GetDUCET(const UTF8 *p, const UTF8 *pEnd)
{
int iState = TR_DUCET_START_STATE;
// Stop at the first accepting state: the pruned table can accept before
// the final byte of a code point, and reading on would transition into an
// unrelated state, yielding a wrong collation weight.
//
while (p < pEnd && iState < TR_DUCET_ACCEPTING_STATES_START)
{
unsigned char ch = *p++;
int iColumn = tr_ducet_itt[ch];
int iOffset = tr_ducet_sot[iState];
for (;;)
{
int y = tr_ducet_sbt[iOffset];
if (y < 128)
{
// RUN phrase.
if (iColumn < y)
{
iState = tr_ducet_sbt[iOffset + 1];
break;
}
iColumn -= y;
iOffset += 2;
}
else
{
// COPY phrase.
y = 256 - y;
if (iColumn < y)
{
iState = tr_ducet_sbt[iOffset + iColumn + 1];
break;
}
iColumn -= y;
iOffset += y + 1;
}
}
}
return (iState >= TR_DUCET_ACCEPTING_STATES_START)
? iState - TR_DUCET_ACCEPTING_STATES_START : 0;
}
// ---------------------------------------------------------------------------
// DFA lookup: two-code-point contraction -> CE index.
// Returns 0 if no contraction match.
// ---------------------------------------------------------------------------
static int GetContraction(const UTF8 *p1, const UTF8 *p1End,
const UTF8 *p2, const UTF8 *p2End)
{
int iState = TR_DUCET_CONTRACT_START_STATE;
// Feed first code point's bytes.
//
while (p1 < p1End && iState < TR_DUCET_CONTRACT_ACCEPTING_STATES_START)
{
unsigned char ch = *p1++;
int iColumn = tr_ducet_contract_itt[ch];
int iOffset = tr_ducet_contract_sot[iState];
for (;;)
{
int y = tr_ducet_contract_sbt[iOffset];
if (y < 128)
{
if (iColumn < y)
{
iState = tr_ducet_contract_sbt[iOffset + 1];
break;
}
iColumn -= y;
iOffset += 2;
}
else
{
y = 256 - y;
if (iColumn < y)
{
iState = tr_ducet_contract_sbt[iOffset + iColumn + 1];
break;
}
iColumn -= y;
iOffset += y + 1;
}
}
}
// Feed second code point's bytes.
//
while (p2 < p2End && iState < TR_DUCET_CONTRACT_ACCEPTING_STATES_START)
{
unsigned char ch = *p2++;
int iColumn = tr_ducet_contract_itt[ch];
int iOffset = tr_ducet_contract_sot[iState];
for (;;)
{
int y = tr_ducet_contract_sbt[iOffset];
if (y < 128)
{
if (iColumn < y)
{
iState = tr_ducet_contract_sbt[iOffset + 1];
break;
}
iColumn -= y;
iOffset += 2;
}
else
{
y = 256 - y;
if (iColumn < y)
{
iState = tr_ducet_contract_sbt[iOffset + iColumn + 1];
break;
}
iColumn -= y;
iOffset += y + 1;
}
}
}
if (iState >= TR_DUCET_CONTRACT_ACCEPTING_STATES_START)
{
int idx = iState - TR_DUCET_CONTRACT_ACCEPTING_STATES_START;
if (0 != idx)
{
return static_cast<int>(tr_ducet_contract_nfc_compose_result[idx]);
}
}
return 0;
}
// ---------------------------------------------------------------------------
// Advance one UTF-8 code point and return the pointer past it.
// ---------------------------------------------------------------------------
static const UTF8 *utf8_advance_collate(const UTF8 *p, const UTF8 *pEnd)
{
if (p >= pEnd)
{
return p;
}
int n = utf8_FirstByte[*p];
if (n < 1 || n >= UTF8_CONTINUE)
{
return p + 1;
}
for (int i = 1; i < n; i++)
{
if ( p + i >= pEnd
|| UTF8_CONTINUE != utf8_FirstByte[p[i]])
{
return p + 1;
}
}
UTF32 cp = utf8_decode_raw(p, n);
if (!utf8_is_valid_scalar(cp, n))
{
return p + 1;
}
const UTF8 *pNext = p + n;
return (pNext <= pEnd) ? pNext : pEnd;
}
// ---------------------------------------------------------------------------
// Decode one UTF-8 code point from [p, pEnd). Returns UNI_EOF on error.
// ---------------------------------------------------------------------------
static UTF32 utf8_decode_collate(const UTF8 *p, const UTF8 *pEnd)
{
if (p >= pEnd)
{
return UNI_EOF;
}
int n = utf8_FirstByte[*p];
if (n < 1 || n >= UTF8_CONTINUE)
{
return UNI_EOF;
}
if (p + n > pEnd)
{
return UNI_EOF;
}
for (int i = 1; i < n; i++)
{
if (UTF8_CONTINUE != utf8_FirstByte[p[i]])
{
return UNI_EOF;
}
}
UTF32 cp = utf8_decode_raw(p, n);
if (!utf8_is_valid_scalar(cp, n))
{
return UNI_EOF;
}
return cp;
}
// ---------------------------------------------------------------------------
// Implicit weight computation (UCA Section 10.1).
//
// Code points not in DUCET get synthetic collation elements derived
// from their code point value. The primary weight is split into
// a base and an offset within a designated range.
//
// For CJK unified ideographs (and extensions), the base depends on
// the block. For all other unassigned code points, a default base
// is used.
// ---------------------------------------------------------------------------
// CJK Unified Ideographs ranges and their DUCET bases.
//
struct ImplicitRange
{
UTF32 start;
UTF32 end;
unsigned short base;
};
static const ImplicitRange s_ImplicitRanges[] =
{
// CJK Unified Ideographs.
{ 0x4E00, 0x9FFF, 0xFB40 },
// CJK Compatibility Ideographs.
{ 0xF900, 0xFAFF, 0xFB40 },
// CJK Unified Ideographs Extension A.
{ 0x3400, 0x4DBF, 0xFB80 },
// CJK Unified Ideographs Extension B.
{ 0x20000, 0x2A6DF, 0xFB80 },
// CJK Unified Ideographs Extension C.
{ 0x2A700, 0x2B73F, 0xFB80 },
// CJK Unified Ideographs Extension D.
{ 0x2B740, 0x2B81F, 0xFB80 },
// CJK Unified Ideographs Extension E.
{ 0x2B820, 0x2CEAF, 0xFB80 },
// CJK Unified Ideographs Extension F.
{ 0x2CEB0, 0x2EBEF, 0xFB80 },
// CJK Unified Ideographs Extension G.
{ 0x30000, 0x3134F, 0xFB80 },
// CJK Unified Ideographs Extension H.
{ 0x31350, 0x323AF, 0xFB80 },
// CJK Unified Ideographs Extension I.
{ 0x2EBF0, 0x2F7FF, 0xFB80 },
// Tangut and Tangut Supplement (@implicitweights).
{ 0x17000, 0x18AFF, 0xFB00 },
{ 0x18D00, 0x18D7F, 0xFB00 },
// Nushu (@implicitweights).
{ 0x1B170, 0x1B2FF, 0xFB01 },
// Khitan Small Script (@implicitweights).
{ 0x18B00, 0x18CFF, 0xFB02 },
};
static const int s_nImplicitRanges =
static_cast<int>(sizeof(s_ImplicitRanges) / sizeof(s_ImplicitRanges[0]));
// Compute the implicit primary weight for a code point.
// Returns AAAA (high 16 bits) and BBBB (low 16 bits) as a pair.
// The full implicit CE is [.AAAA.0020.0002][.BBBB.0000.0000].
//
static void ImplicitWeight(UTF32 cp, unsigned short &aaaa, unsigned short &bbbb)
{
unsigned short base = 0xFBC0; // Default for unassigned.
for (int i = 0; i < s_nImplicitRanges; i++)
{
if (cp >= s_ImplicitRanges[i].start && cp <= s_ImplicitRanges[i].end)
{
base = s_ImplicitRanges[i].base;
break;
}
}
aaaa = base + static_cast<unsigned short>(cp >> 15);
bbbb = static_cast<unsigned short>((cp & 0x7FFF) | 0x8000);
}
// ---------------------------------------------------------------------------
// Per-codepoint CE extraction.
//
// Extract CEs for the next code point (or contraction) at *pp.
// Advances *pp past the consumed input bytes.
// Returns number of CEs written to ces[].
// ---------------------------------------------------------------------------
static int ExtractCEs(const UTF8 **pp, const UTF8 *pEnd,
uint32_t *ces, int maxCEs)
{
const UTF8 *p = *pp;
int nCEs = 0;
// ASCII fast path: no contractions, single-byte DUCET lookup.
//
if (*p < 0x80)
{
int ceIndex = GetDUCET(p, p + 1);
if (0 != ceIndex)
{
int start = ducet_ce_offset[ceIndex];
int end = ducet_ce_offset[ceIndex + 1];
for (int i = start; i < end && nCEs < maxCEs; i++)
{
ces[nCEs++] = ducet_ce_weights[i];
}
}
else
{
unsigned short aaaa, bbbb;
ImplicitWeight(static_cast<UTF32>(*p), aaaa, bbbb);
if (nCEs < maxCEs)
{
ces[nCEs++] = (static_cast<uint32_t>(aaaa) << 16)
| (static_cast<uint32_t>(0x0020) << 5) | 0x0002;
}
if (nCEs < maxCEs)
{
ces[nCEs++] = static_cast<uint32_t>(bbbb) << 16;
}
}
*pp = p + 1;
return nCEs;
}
// Non-ASCII: advance, try contraction, then single-cp DUCET.
//
const UTF8 *pNext = utf8_advance_collate(p, pEnd);
int ceIndex = 0;
const UTF8 *pConsumed = pNext;
// Contraction check: only if the lead byte maps to a non-default
// column in the contraction DFA. Column 0 is the default and can
// never reach an accepting state, so skip the DFA entirely.
//
if (tr_ducet_contract_itt[*p] != 0 && pNext < pEnd)
{
const UTF8 *pNext2 = utf8_advance_collate(pNext, pEnd);
ceIndex = GetContraction(p, pNext, pNext, pNext2);
if (0 != ceIndex)
{
pConsumed = pNext2;
}
}
if (0 == ceIndex)
{
ceIndex = GetDUCET(p, pNext);
}
if (0 != ceIndex)
{
int start = ducet_ce_offset[ceIndex];
int end = ducet_ce_offset[ceIndex + 1];
for (int i = start; i < end && nCEs < maxCEs; i++)
{
ces[nCEs++] = ducet_ce_weights[i];
}
}
else
{
UTF32 cp = utf8_decode_collate(p, pNext);
if (UNI_EOF != cp)
{
unsigned short aaaa, bbbb;
ImplicitWeight(cp, aaaa, bbbb);
if (nCEs < maxCEs)
{
ces[nCEs++] = (static_cast<uint32_t>(aaaa) << 16)
| (static_cast<uint32_t>(0x0020) << 5) | 0x0002;
}
if (nCEs < maxCEs)
{
ces[nCEs++] = static_cast<uint32_t>(bbbb) << 16;
}
}
}
*pp = pConsumed;
return nCEs;
}
// ---------------------------------------------------------------------------
// Latin CE cache.
//
// Precomputed CE for U+0000..U+017F (Basic Latin + Latin-1 Supplement +
// Latin Extended-A). Most characters in this range have exactly one CE
// in DUCET. A value of 0 means "use slow path" (multi-CE or unmapped).
//
// This is the key fast path: Latin text skips DFA traversal, contraction
// checks, and UTF-8 validation entirely -- one table lookup per character.
// ---------------------------------------------------------------------------
#define LATIN_CE_LIMIT 0x180
static uint32_t s_latin_ce[LATIN_CE_LIMIT];
static std::atomic<int> s_latin_ce_state{0};
static void InitLatinCache()
{
for (int cp = 0; cp < LATIN_CE_LIMIT; cp++)
{
UTF8 buf[2];
int n;
if (cp < 0x80)
{
buf[0] = static_cast<UTF8>(cp);
n = 1;
}
else
{
buf[0] = static_cast<UTF8>(0xC0 | (cp >> 6));
buf[1] = static_cast<UTF8>(0x80 | (cp & 0x3F));
n = 2;
}
int idx = GetDUCET(buf, buf + n);
if (0 != idx)
{
int start = ducet_ce_offset[idx];
int end = ducet_ce_offset[idx + 1];
if (end - start == 1)
{
s_latin_ce[cp] = ducet_ce_weights[start];
continue;
}
}
s_latin_ce[cp] = 0;
}
}
static void EnsureLatinCache()
{
int state = s_latin_ce_state.load(std::memory_order_acquire);
if (2 == state)
{
return;
}
int expected = 0;
if (s_latin_ce_state.compare_exchange_strong(
expected, 1,
std::memory_order_acq_rel, std::memory_order_acquire))
{
InitLatinCache();
s_latin_ce_state.store(2, std::memory_order_release);
return;
}
for (;;)
{
state = s_latin_ce_state.load(std::memory_order_acquire);
if (2 == state)
{
return;
}
}
}
// ---------------------------------------------------------------------------
// CE collection (bounded fast path).
//
// Walks the string code-point by code-point with fast paths for ASCII,
// Latin (U+0080..U+017F), and CJK (U+4E00..U+9FFF). Falls back to
// ExtractCEs for everything else.
//
// Returns the number of CEs collected. Sets *pOverflow if the buffer
// was too small, signalling the caller to use the streaming path.
// ---------------------------------------------------------------------------
static int CollectCEsBounded(const UTF8 *src, size_t nSrc,
uint32_t *ces, int maxCEs, int *pOverflow)
{
EnsureLatinCache();
const UTF8 *p = src;
const UTF8 *pEnd = src + nSrc;
int nCEs = 0;
*pOverflow = 0;
while (p < pEnd)
{
if (nCEs >= maxCEs)
{
*pOverflow = 1;
break;
}
// ASCII fast path: single table lookup, no DFA.
//
if (*p < 0x80)
{
uint32_t ce = s_latin_ce[*p];
if (0 != ce)
{
ces[nCEs++] = ce;
p++;
continue;
}
}
// Latin 2-byte fast path: U+0080..U+017F (lead bytes 0xC2..0xC5).
//
else if (static_cast<unsigned>(*p - 0xC2) <= (0xC5 - 0xC2)
&& p + 1 < pEnd && (p[1] & 0xC0) == 0x80)
{
UTF32 cp = static_cast<UTF32>((*p & 0x1F) << 6) | (p[1] & 0x3F);
uint32_t ce = s_latin_ce[cp];
if (0 != ce)
{
ces[nCEs++] = ce;
p += 2;
continue;
}
}
// CJK Unified Ideographs fast path: U+4E00..U+9FFF.
//
else if (*p >= 0xE4 && *p <= 0xE9
&& p + 2 < pEnd
&& (p[1] & 0xC0) == 0x80 && (p[2] & 0xC0) == 0x80)
{
UTF32 cp = (static_cast<UTF32>(*p & 0x0F) << 12)
| (static_cast<UTF32>(p[1] & 0x3F) << 6)
| static_cast<UTF32>(p[2] & 0x3F);
if (cp >= 0x4E00 && cp <= 0x9FFF)
{
if (nCEs + 2 > maxCEs)
{
*pOverflow = 1;
break;
}
ces[nCEs++] = (static_cast<uint32_t>(0xFB40 + static_cast<unsigned short>(cp >> 15)) << 16)
| (static_cast<uint32_t>(0x0020) << 5) | 0x0002;
ces[nCEs++] = static_cast<uint32_t>((cp & 0x7FFF) | 0x8000) << 16;
p += 3;
continue;
}
}
// General path: use ExtractCEs with overflow guard.
//
if (maxCEs - nCEs < MAX_CHAR_CES)
{
const UTF8 *probe = p;
uint32_t tmp[MAX_CHAR_CES];
int nProbe = ExtractCEs(&probe, pEnd, tmp, MAX_CHAR_CES);
if (nCEs + nProbe > maxCEs)
{
*pOverflow = 1;
break;
}
memcpy(ces + nCEs, tmp, static_cast<size_t>(nProbe) * sizeof(tmp[0]));
nCEs += nProbe;
p = probe;
}
else
{
nCEs += ExtractCEs(&p, pEnd, ces + nCEs, maxCEs - nCEs);
}
}
return nCEs;
}
// ---------------------------------------------------------------------------
// CE Iterator: streaming comparison for overflow path.
//
// When the bounded CE buffer overflows, we re-scan the string one code
// point at a time, extracting CEs on-demand. This avoids allocating
// unbounded memory for pathological strings.
// ---------------------------------------------------------------------------
struct CEIterator
{
const UTF8 *p;
const UTF8 *pEnd;
uint32_t ces[MAX_CHAR_CES];
int iCE;
int nCEs;
};
static void CEIteratorInit(CEIterator *it, const UTF8 *src, size_t nSrc)
{
it->p = src;
it->pEnd = src + nSrc;
it->iCE = 0;
it->nCEs = 0;
}
static unsigned int CEWeightForLevel(uint32_t ce, int level)
{
if (1 == level)
{
return CE_PRIMARY(ce);
}
if (2 == level)
{
return CE_SECONDARY(ce);
}
return CE_TERTIARY(ce);
}
static int CEIteratorNextWeight(CEIterator *it, int level, unsigned int *pWeight)
{
for (;;)
{
while (it->iCE < it->nCEs)
{
unsigned int weight = CEWeightForLevel(it->ces[it->iCE++], level);
if (0 != weight)
{
*pWeight = weight;
return 1;
}
}
if (it->p >= it->pEnd)
{
return 0;
}
it->nCEs = ExtractCEs(&it->p, it->pEnd, it->ces, MAX_CHAR_CES);
it->iCE = 0;
}
}
// ---------------------------------------------------------------------------
// Streaming level comparison (overflow fallback).
// ---------------------------------------------------------------------------
static int CompareLevel(const UTF8 *a, size_t nA,
const UTF8 *b, size_t nB,
int level)
{
CEIterator itA, itB;
CEIteratorInit(&itA, a, nA);
CEIteratorInit(&itB, b, nB);
for (;;)
{
unsigned int wA, wB;
int hasA = CEIteratorNextWeight(&itA, level, &wA);
int hasB = CEIteratorNextWeight(&itB, level, &wB);
if (!hasA || !hasB)
{
if (hasA) return 1;
if (hasB) return -1;
return 0;
}
if (wA < wB) return -1;
if (wA > wB) return 1;
}
}
// ---------------------------------------------------------------------------
// Buffered level comparisons.
//
// Used when CollectCEsBounded succeeds (no overflow). These operate on
// pre-collected CE arrays for better cache locality.
// ---------------------------------------------------------------------------
static int ComparePrimaryBuffered(const uint32_t *cesA, int nCEsA,
const uint32_t *cesB, int nCEsB)
{
int iA = 0, iB = 0;
for (;;)
{
while (iA < nCEsA && 0 == CE_PRIMARY(cesA[iA])) iA++;
while (iB < nCEsB && 0 == CE_PRIMARY(cesB[iB])) iB++;
if (iA >= nCEsA || iB >= nCEsB) break;
unsigned int wA = CE_PRIMARY(cesA[iA]);
unsigned int wB = CE_PRIMARY(cesB[iB]);
if (wA < wB) return -1;
if (wA > wB) return 1;
iA++;
iB++;
}
while (iA < nCEsA && 0 == CE_PRIMARY(cesA[iA])) iA++;
while (iB < nCEsB && 0 == CE_PRIMARY(cesB[iB])) iB++;
if (iA < nCEsA) return 1;
if (iB < nCEsB) return -1;
return 0;
}
static int CompareSecondaryBuffered(const uint32_t *cesA, int nCEsA,
const uint32_t *cesB, int nCEsB)
{
int iA = 0, iB = 0;
for (;;)
{
while (iA < nCEsA && 0 == CE_SECONDARY(cesA[iA])) iA++;
while (iB < nCEsB && 0 == CE_SECONDARY(cesB[iB])) iB++;
if (iA >= nCEsA || iB >= nCEsB) break;
unsigned int wA = CE_SECONDARY(cesA[iA]);
unsigned int wB = CE_SECONDARY(cesB[iB]);
if (wA < wB) return -1;
if (wA > wB) return 1;
iA++;
iB++;
}
while (iA < nCEsA && 0 == CE_SECONDARY(cesA[iA])) iA++;
while (iB < nCEsB && 0 == CE_SECONDARY(cesB[iB])) iB++;
if (iA < nCEsA) return 1;
if (iB < nCEsB) return -1;
return 0;
}
static int CompareTertiaryBuffered(const uint32_t *cesA, int nCEsA,
const uint32_t *cesB, int nCEsB)
{
int iA = 0, iB = 0;
for (;;)
{
while (iA < nCEsA && 0 == CE_TERTIARY(cesA[iA])) iA++;
while (iB < nCEsB && 0 == CE_TERTIARY(cesB[iB])) iB++;
if (iA >= nCEsA || iB >= nCEsB) break;
unsigned int wA = CE_TERTIARY(cesA[iA]);
unsigned int wB = CE_TERTIARY(cesB[iB]);
if (wA < wB) return -1;
if (wA > wB) return 1;
iA++;
iB++;
}
while (iA < nCEsA && 0 == CE_TERTIARY(cesA[iA])) iA++;
while (iB < nCEsB && 0 == CE_TERTIARY(cesB[iB])) iB++;
if (iA < nCEsA) return 1;
if (iB < nCEsB) return -1;
return 0;
}
// ---------------------------------------------------------------------------
// NFC tiebreaker helpers.
// ---------------------------------------------------------------------------
static size_t GetNFCBytes(const UTF8 *src, size_t nSrc,
UTF8 *buf, size_t nBuf,
const UTF8 **ppOut)
{
if (utf8_is_nfc(src, nSrc))
{
*ppOut = src;
return nSrc;
}
utf8_normalize_nfc(src, nSrc, buf, nBuf, &nSrc);
*ppOut = buf;
return nSrc;
}
static int CompareNFCTiebreak(const UTF8 *a, size_t nA,
const UTF8 *b, size_t nB)
{
UTF8 nfcBufA[LBUF_SIZE];
UTF8 nfcBufB[LBUF_SIZE];
const UTF8 *tieA;
const UTF8 *tieB;
size_t tieNA = GetNFCBytes(a, nA, nfcBufA, sizeof(nfcBufA), &tieA);
size_t tieNB = GetNFCBytes(b, nB, nfcBufB, sizeof(nfcBufB), &tieB);
size_t nMin = (tieNA < tieNB) ? tieNA : tieNB;
int cmp = memcmp(tieA, tieB, nMin);
if (0 != cmp) return cmp;
if (tieNA < tieNB) return -1;
if (tieNA > tieNB) return 1;
return 0;
}
// ---------------------------------------------------------------------------
// Sort key helpers.
// ---------------------------------------------------------------------------
static void AppendBE16(UTF8 *key, size_t nKeyMax, size_t *pPos,
unsigned int value)
{
if (*pPos + 2 <= nKeyMax)
{
key[*pPos] = static_cast<UTF8>(value >> 8);
key[*pPos + 1] = static_cast<UTF8>(value & 0xFF);
}
*pPos += 2;
}
static void AppendByte(UTF8 *key, size_t nKeyMax, size_t *pPos,
UTF8 value)
{
if (*pPos < nKeyMax)
{
key[*pPos] = value;
}
(*pPos)++;
}
static void AppendLevelSortKey(const UTF8 *src, size_t nSrc,
UTF8 *key, size_t nKeyMax,
size_t *pPos, int level)
{
CEIterator it;
CEIteratorInit(&it, src, nSrc);
for (;;)
{
unsigned int weight;
if (!CEIteratorNextWeight(&it, level, &weight))
{
break;
}
if (level < 3)
{
AppendBE16(key, nKeyMax, pPos, weight);
}
else
{
AppendByte(key, nKeyMax, pPos, static_cast<UTF8>(weight));
}
}
}
static void AppendNFCTiebreak(const UTF8 *src, size_t nSrc,
UTF8 *key, size_t nKeyMax,
size_t *pPos)
{
UTF8 nfcBuf[LBUF_SIZE];
const UTF8 *norm;
size_t nNorm = GetNFCBytes(src, nSrc, nfcBuf, sizeof(nfcBuf), &norm);
AppendByte(key, nKeyMax, pPos, 0);
for (size_t i = 0; i < nNorm; i++)
{
AppendByte(key, nKeyMax, pPos, norm[i]);
}
}
// ---------------------------------------------------------------------------
// Latin fast-path comparison.
//
// Decode next Latin codepoint and return its cached CE.
// Returns 0 if the byte is non-Latin or has no single-CE cache entry.
// ---------------------------------------------------------------------------
static inline uint32_t NextLatinCE(const UTF8 **pp, const UTF8 *pEnd)
{
const UTF8 *p = *pp;
if (*p < 0x80)
{
uint32_t ce = s_latin_ce[*p];
if (0 != ce)
{
*pp = p + 1;
return ce;
}
return 0;
}
if (static_cast<unsigned>(*p - 0xC2) <= (0xC5 - 0xC2)
&& p + 1 < pEnd && (p[1] & 0xC0) == 0x80)
{
UTF32 cp = static_cast<UTF32>((*p & 0x1F) << 6) | (p[1] & 0x3F);
uint32_t ce = s_latin_ce[cp];
if (0 != ce)
{
*pp = p + 2;
return ce;
}
}
return 0;
}
// ---------------------------------------------------------------------------
// FastLatinCmp: Try fast Latin comparison.
//
// If both strings are entirely Latin with single-CE characters, compare
// inline without collecting CE arrays. Returns 1 if the fast path
// handled it (result in *pResult), 0 if the caller must fall back to
// the full UCA path.
//
// For single-CE Latin, all three weight levels are non-zero, so UCA's
// three-pass comparison reduces to a single element-by-element pass
// with recorded secondary/tertiary differences.
// ---------------------------------------------------------------------------
static int FastLatinCmp(const UTF8 *a, size_t nA,
const UTF8 *b, size_t nB,
int *pResult)
{
EnsureLatinCache();
const UTF8 *pa = a, *paEnd = a + nA;
const UTF8 *pb = b, *pbEnd = b + nB;
int secDiff = 0, tertDiff = 0;
while (pa < paEnd && pb < pbEnd)
{
// ASCII byte-skip: identical ASCII bytes produce identical CEs.
//
while (pa < paEnd && pb < pbEnd && *pa < 0x80 && *pa == *pb)
{
pa++;
pb++;
}
if (pa >= paEnd || pb >= pbEnd)
{
break;
}
uint32_t ceA = NextLatinCE(&pa, paEnd);
if (0 == ceA) return 0;
uint32_t ceB = NextLatinCE(&pb, pbEnd);
if (0 == ceB) return 0;
unsigned short pA = static_cast<unsigned short>(CE_PRIMARY(ceA));
unsigned short pB = static_cast<unsigned short>(CE_PRIMARY(ceB));
if (pA != pB)
{
*pResult = (pA < pB) ? -1 : 1;
return 1;
}
if (0 == secDiff)
{
unsigned short sA = static_cast<unsigned short>(CE_SECONDARY(ceA));
unsigned short sB = static_cast<unsigned short>(CE_SECONDARY(ceB));
if (sA != sB)
{
secDiff = (sA < sB) ? -1 : 1;
}
else if (0 == tertDiff)
{
unsigned char tA = static_cast<unsigned char>(CE_TERTIARY(ceA));
unsigned char tB = static_cast<unsigned char>(CE_TERTIARY(ceB));
if (tA != tB)
{
tertDiff = (tA < tB) ? -1 : 1;
}
}
}
}
// One or both strings exhausted at level 1.
// Any remaining characters have non-zero primary (Latin guarantee).
//
if (pa < paEnd)
{
if (0 == NextLatinCE(&pa, paEnd)) return 0;
*pResult = 1;
return 1;
}
if (pb < pbEnd)
{
if (0 == NextLatinCE(&pb, pbEnd)) return 0;
*pResult = -1;
return 1;
}
if (0 != secDiff)
{
*pResult = secDiff;
return 1;
}
if (0 != tertDiff)
{
*pResult = tertDiff;
return 1;
}
*pResult = 0;
return 1;
}
// ---------------------------------------------------------------------------
// FastLatinCmpCI: Case-insensitive Latin fast path.
//
// Same structure as FastLatinCmp but only compares primary and secondary
// weights (skips tertiary/case).
// ---------------------------------------------------------------------------
static int FastLatinCmpCI(const UTF8 *a, size_t nA,
const UTF8 *b, size_t nB,
int *pResult)
{
EnsureLatinCache();
const UTF8 *pa = a, *paEnd = a + nA;
const UTF8 *pb = b, *pbEnd = b + nB;
while (pa < paEnd && pb < pbEnd)
{
// ASCII byte-skip.
//
while (pa < paEnd && pb < pbEnd && *pa < 0x80 && *pa == *pb)
{
pa++;
pb++;
}
if (pa >= paEnd || pb >= pbEnd)
{
break;
}
uint32_t ceA = NextLatinCE(&pa, paEnd);
if (0 == ceA) return 0;
uint32_t ceB = NextLatinCE(&pb, pbEnd);
if (0 == ceB) return 0;
unsigned short pA = static_cast<unsigned short>(CE_PRIMARY(ceA));
unsigned short pB = static_cast<unsigned short>(CE_PRIMARY(ceB));
if (pA != pB)
{
*pResult = (pA < pB) ? -1 : 1;
return 1;
}
unsigned short sA = static_cast<unsigned short>(CE_SECONDARY(ceA));
unsigned short sB = static_cast<unsigned short>(CE_SECONDARY(ceB));
if (sA != sB)
{
*pResult = (sA < sB) ? -1 : 1;
return 1;
}
}
if (pa < paEnd)
{
if (0 == NextLatinCE(&pa, paEnd)) return 0;
*pResult = 1;
return 1;
}
if (pb < pbEnd)
{
if (0 == NextLatinCE(&pb, pbEnd)) return 0;
*pResult = -1;
return 1;
}
*pResult = 0;
return 1;
}
// ---------------------------------------------------------------------------
// FastLatinSortKey: Latin-only sort key generation.
//
// If the entire string is Latin with single-CE characters, build the
// sort key directly from the cache without collecting into a CE array.
// Returns 1 on success, 0 if the caller must fall back.
// ---------------------------------------------------------------------------
static int FastLatinSortKey(const UTF8 *src, size_t nSrc,
UTF8 *key, size_t nKeyMax,
size_t *pPos, int bCaseSensitive)
{
EnsureLatinCache();
size_t startPos = *pPos;
const UTF8 *p = src;
const UTF8 *pEnd = src + nSrc;
// Level 1: primary weights.
//
while (p < pEnd)
{
uint32_t ce = NextLatinCE(&p, pEnd);
if (0 == ce)
{
*pPos = startPos;
return 0;
}
AppendBE16(key, nKeyMax, pPos, CE_PRIMARY(ce));
}
AppendBE16(key, nKeyMax, pPos, 0);
// Level 2: secondary weights.
//
p = src;
while (p < pEnd)
{
uint32_t ce = NextLatinCE(&p, pEnd);
AppendBE16(key, nKeyMax, pPos, CE_SECONDARY(ce));
}
if (bCaseSensitive)
{
// Level 3: tertiary weights.
//
AppendBE16(key, nKeyMax, pPos, 0);
p = src;
while (p < pEnd)
{
uint32_t ce = NextLatinCE(&p, pEnd);
if (0 == ce)
{
*pPos = startPos;
return 0;
}
AppendByte(key, nKeyMax, pPos, static_cast<UTF8>(CE_TERTIARY(ce)));
}
// NFC tiebreaker: append raw bytes (Latin is already NFC).
//
AppendByte(key, nKeyMax, pPos, 0);
for (size_t i = 0; i < nSrc; i++)
{
AppendByte(key, nKeyMax, pPos, src[i]);
}
}
return 1;
}
// ---------------------------------------------------------------------------
// FastASCIISortKeyCI: Pure-ASCII case-insensitive sort key.
//
// Even faster path for ASCII-only strings: validate all bytes are ASCII
// with cached CEs, then emit primary and secondary weights directly.
// ---------------------------------------------------------------------------
static int FastASCIISortKeyCI(const UTF8 *src, size_t nSrc,
UTF8 *key, size_t nKeyMax,
size_t *pPos)
{
EnsureLatinCache();
for (size_t i = 0; i < nSrc; i++)
{
if (src[i] >= 0x80 || 0 == s_latin_ce[src[i]])
{
return 0;
}
}
for (size_t i = 0; i < nSrc; i++)
{
AppendBE16(key, nKeyMax, pPos, CE_PRIMARY(s_latin_ce[src[i]]));
}
AppendBE16(key, nKeyMax, pPos, 0);
for (size_t i = 0; i < nSrc; i++)
{
AppendBE16(key, nKeyMax, pPos, CE_SECONDARY(s_latin_ce[src[i]]));
}
return 1;
}
// ---------------------------------------------------------------------------
// mux_collate_cmp: Compare two UTF-8 strings using UCA.
//
// Returns negative if a < b, 0 if equal, positive if a > b.
//
// Implements the multi-level comparison:
// Level 1: primary weights (base character identity)
// Level 2: secondary weights (accents)
// Level 3: tertiary weights (case)
// Tiebreaker: code-point order (NFC-normalized)
//
// Optimizations:
// 1. memcmp equality check (identical strings are common)
// 2. FastLatinCmp for Latin-only strings
// 3. Bounded CE collection with streaming overflow fallback
// ---------------------------------------------------------------------------
int mux_collate_cmp(const UTF8 *a, size_t nA, const UTF8 *b, size_t nB)
{
// Fast identity check.
//
if (nA == nB && (a == b || 0 == memcmp(a, b, nA)))
{
return 0;
}
// Fast path: Latin-only strings compared inline.
//
int fastResult;
if (FastLatinCmp(a, nA, b, nB, &fastResult))
{
return fastResult;
}
// Bounded CE collection path.
//
{
uint32_t cesA[MAX_CMP_CES], cesB[MAX_CMP_CES];
int overflowA, overflowB;
int nCEsA = CollectCEsBounded(a, nA, cesA, MAX_CMP_CES, &overflowA);
int nCEsB = CollectCEsBounded(b, nB, cesB, MAX_CMP_CES, &overflowB);
if (!overflowA && !overflowB)
{
int cmp = ComparePrimaryBuffered(cesA, nCEsA, cesB, nCEsB);
if (0 != cmp) return cmp;
cmp = CompareSecondaryBuffered(cesA, nCEsA, cesB, nCEsB);
if (0 != cmp) return cmp;
cmp = CompareTertiaryBuffered(cesA, nCEsA, cesB, nCEsB);
if (0 != cmp) return cmp;
return CompareNFCTiebreak(a, nA, b, nB);
}
}
// Streaming overflow fallback.
//
int cmp = CompareLevel(a, nA, b, nB, 1);
if (0 != cmp) return cmp;
cmp = CompareLevel(a, nA, b, nB, 2);
if (0 != cmp) return cmp;
cmp = CompareLevel(a, nA, b, nB, 3);
if (0 != cmp) return cmp;
// Tiebreaker: binary comparison of NFC-normalized forms.
//
return CompareNFCTiebreak(a, nA, b, nB);
}
// ---------------------------------------------------------------------------
// mux_collate_cmp_ci: Case-insensitive UCA comparison.
//
// Same as mux_collate_cmp but uses only Level 1 (primary) and Level 2
// (secondary) weights, skipping Level 3 (tertiary/case). This gives
// natural case-insensitive ordering per UCA.
// ---------------------------------------------------------------------------
int mux_collate_cmp_ci(const UTF8 *a, size_t nA, const UTF8 *b, size_t nB)
{
// Fast identity check.
//
if (nA == nB && (a == b || 0 == memcmp(a, b, nA)))
{
return 0;
}
// Fast path: Latin-only strings compared inline.
//
{
int fastResult;
if (FastLatinCmpCI(a, nA, b, nB, &fastResult))
{
return fastResult;
}
}
// Bounded CE collection path.
//
{
uint32_t cesA[MAX_CMP_CES], cesB[MAX_CMP_CES];
int overflowA, overflowB;
int nCEsA = CollectCEsBounded(a, nA, cesA, MAX_CMP_CES, &overflowA);
int nCEsB = CollectCEsBounded(b, nB, cesB, MAX_CMP_CES, &overflowB);
if (!overflowA && !overflowB)
{
int cmp = ComparePrimaryBuffered(cesA, nCEsA, cesB, nCEsB);
if (0 != cmp) return cmp;
return CompareSecondaryBuffered(cesA, nCEsA, cesB, nCEsB);
}
}
// Streaming overflow fallback.
//
int cmp = CompareLevel(a, nA, b, nB, 1);
if (0 != cmp) return cmp;
return CompareLevel(a, nA, b, nB, 2);
}
// ---------------------------------------------------------------------------
// mux_collate_sortkey: Generate a binary sort key for UCA comparison.
//
// The sort key can be compared with memcmp to get the same ordering
// as mux_collate_cmp.
//
// Format:
// [primary weights, big-endian 16-bit] 0x0000
// [secondary weights, big-endian 16-bit] 0x0000
// [tertiary weights, 8-bit] 0x00
// [NFC-normalized bytes]
//
// Returns the number of bytes written to key.
// ---------------------------------------------------------------------------
size_t mux_collate_sortkey(const UTF8 *src, size_t nSrc,
UTF8 *key, size_t nKeyMax)
{
size_t pos = 0;
// Fast path: Latin-only sort key.
//
if (FastLatinSortKey(src, nSrc, key, nKeyMax, &pos, 1))
{
return (pos < nKeyMax) ? pos : nKeyMax;
}
// Bounded CE collection path.
//
uint32_t ces[MAX_SORTKEY_CES];
int overflow;
int nCEs = CollectCEsBounded(src, nSrc, ces, MAX_SORTKEY_CES, &overflow);
if (!overflow)
{
// Level 1: primary weights (16-bit big-endian).
//
for (int i = 0; i < nCEs; i++)
{
unsigned short p = static_cast<unsigned short>(CE_PRIMARY(ces[i]));
if (0 != p) AppendBE16(key, nKeyMax, &pos, p);
}
AppendBE16(key, nKeyMax, &pos, 0);
// Level 2: secondary weights (16-bit big-endian).
//
for (int i = 0; i < nCEs; i++)
{
unsigned short s = static_cast<unsigned short>(CE_SECONDARY(ces[i]));
if (0 != s) AppendBE16(key, nKeyMax, &pos, s);
}
AppendBE16(key, nKeyMax, &pos, 0);
// Level 3: tertiary weights (8-bit).
//
for (int i = 0; i < nCEs; i++)
{
unsigned char t = static_cast<unsigned char>(CE_TERTIARY(ces[i]));
if (0 != t) AppendByte(key, nKeyMax, &pos, t);
}
// NFC tiebreaker.
//
AppendNFCTiebreak(src, nSrc, key, nKeyMax, &pos);
return (pos < nKeyMax) ? pos : nKeyMax;
}
// Streaming overflow fallback.
//
AppendLevelSortKey(src, nSrc, key, nKeyMax, &pos, 1);
AppendBE16(key, nKeyMax, &pos, 0);
AppendLevelSortKey(src, nSrc, key, nKeyMax, &pos, 2);
AppendBE16(key, nKeyMax, &pos, 0);
AppendLevelSortKey(src, nSrc, key, nKeyMax, &pos, 3);
AppendNFCTiebreak(src, nSrc, key, nKeyMax, &pos);
return (pos < nKeyMax) ? pos : nKeyMax;
}
// ---------------------------------------------------------------------------
// mux_collate_sortkey_ci: Case-insensitive sort key generation.
//
// Same as mux_collate_sortkey but omits Level 3 (tertiary/case) weights
// and the NFC tiebreaker. Sort keys compare equal for strings that
// differ only in case.
// ---------------------------------------------------------------------------
size_t mux_collate_sortkey_ci(const UTF8 *src, size_t nSrc,
UTF8 *key, size_t nKeyMax)
{
size_t pos = 0;
// Fast path: ASCII-only case-insensitive sort key.
//
if (FastASCIISortKeyCI(src, nSrc, key, nKeyMax, &pos))
{
return (pos < nKeyMax) ? pos : nKeyMax;
}
// Bounded CE collection path.
//
uint32_t ces[MAX_SORTKEY_CES];
int overflow;
int nCEs = CollectCEsBounded(src, nSrc, ces, MAX_SORTKEY_CES, &overflow);
if (!overflow)
{
// Level 1: primary weights (16-bit big-endian).
//
for (int i = 0; i < nCEs; i++)
{
unsigned short p = static_cast<unsigned short>(CE_PRIMARY(ces[i]));
if (0 != p) AppendBE16(key, nKeyMax, &pos, p);
}
AppendBE16(key, nKeyMax, &pos, 0);
// Level 2: secondary weights (16-bit big-endian).
//
for (int i = 0; i < nCEs; i++)
{
unsigned short s = static_cast<unsigned short>(CE_SECONDARY(ces[i]));
if (0 != s) AppendBE16(key, nKeyMax, &pos, s);
}
return (pos < nKeyMax) ? pos : nKeyMax;
}
// Streaming overflow fallback.
//
AppendLevelSortKey(src, nSrc, key, nKeyMax, &pos, 1);
AppendBE16(key, nKeyMax, &pos, 0);
AppendLevelSortKey(src, nSrc, key, nKeyMax, &pos, 2);
return (pos < nKeyMax) ? pos : nKeyMax;
}
Reference in a new issue View git blame Copy permalink