>From bbccb4588414742773b0faebf56e0ff4b8c619a5 Mon Sep 17 00:00:00 2001 From: Rich Felker Date: Fri, 18 Sep 2026 12:08:29 -0400 Subject: [PATCH 15/18] add collation implementation --- src/internal/ccc_slots.h | 18 ++++ src/internal/collate.h | 54 +++++++++++ src/internal/locale_impl.h | 3 + src/locale/collate.c | 180 +++++++++++++++++++++++++++++++++++++ src/locale/locale_map.c | 9 ++ src/locale/strcoll.c | 116 +++++++++++++++++++++++- src/locale/strxfrm.c | 93 ++++++++++++++++++- src/locale/wcscoll.c | 10 ++- src/locale/wcsxfrm.c | 28 ++++-- 9 files changed, 495 insertions(+), 16 deletions(-) create mode 100644 src/internal/ccc_slots.h create mode 100644 src/internal/collate.h create mode 100644 src/locale/collate.c diff --git a/src/internal/ccc_slots.h b/src/internal/ccc_slots.h new file mode 100644 index 00000000..1b40fc80 --- /dev/null +++ b/src/internal/ccc_slots.h @@ -0,0 +1,18 @@ +#define CCC_COUNT 56 +#define CCC_SLOTS \ +0, 6, 0, 0, 0, 0, 54, 38, 52, 39, 12, 13, 14, 15, 16, 17, \ +18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 53, 31, 32, 33, 28, 29, \ +30, 34, 35, 36, 37, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, \ +0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, \ +0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, \ +0, 0, 0, 0, 40, 0, 0, 0, 0, 0, 0, 41, 0, 0, 0, 0, \ +0, 0, 0, 0, 0, 0, 0, 42, 0, 0, 0, 43, 0, 0, 0, 0, \ +0, 0, 0, 0, 0, 0, 44, 0, 0, 0, 45, 0, 0, 0, 0, 0, \ +0, 46, 47, 0, 48, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, \ +0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, \ +0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, \ +0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, \ +0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, \ +0, 0, 0, 0, 0, 0, 49, 0, 4, 0, 50, 0, 3, 0, 10, 0, \ +51, 0, 55, 0, 11, 0, 1, 0, 2, 8, 9, 0, 0, 0, 0, 0, \ +7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, diff --git a/src/internal/collate.h b/src/internal/collate.h new file mode 100644 index 00000000..b3cc5b76 --- /dev/null +++ b/src/internal/collate.h @@ -0,0 +1,54 @@ +#ifndef COLLATE_H +#define COLLATE_H + +#include + +#include "nfd.h" +#include "ccc_slots.h" + +#define MAX_LEVELS 10 +#define PREFIX_MAX 8 + +// header byte FD, one length for each weight level, up to 3 fractional levels +// before data, 3 bytes of data, one byte for each non-primary weight +#define IMPLICIT_MAX (1+MAX_LEVELS+3+3+MAX_LEVELS-1) + +struct cm_iterator { + struct nfd_iterator ni; + uint32_t pending_ch; + const unsigned char *cm_root; + const unsigned char *implicit_rules; + wchar_t context_buf[PREFIX_MAX]; + int context_pos; + unsigned char implicit_buf[IMPLICIT_MAX]; + size_t nskip[CCC_COUNT]; +}; + +struct ce_iterator { + struct cm_iterator mi; + const unsigned char *ce; + const unsigned char *hd; + const unsigned char *flags; + int nlevels; + int rem; +}; + +struct collation { + const unsigned char *levels; + const unsigned char *mappings_root; + const unsigned char *header_dict; + const unsigned char *implicit_rules; +}; + +#define ce_iterate __ce_iterate +#define ce_iterator_start __ce_iterator_start +#define collation_init __collation_init + +hidden const unsigned char *ce_iterate(struct ce_iterator *); +hidden void ce_iterator_start(struct ce_iterator *, const void *, int, const struct collation *); +hidden int collation_init(struct collation *, const unsigned char *); + +size_t __strxfrm_core(char *restrict, const void *restrict, size_t, int, const struct collation *); +int __strcoll_core(const void *, const void *, int, const struct collation *); + +#endif diff --git a/src/internal/locale_impl.h b/src/internal/locale_impl.h index 98f7ab0f..65e3d245 100644 --- a/src/internal/locale_impl.h +++ b/src/internal/locale_impl.h @@ -5,6 +5,7 @@ #include #include "libc.h" #include "pthread_impl.h" +#include "collate.h" #define LOCALE_NAME_MAX 23 @@ -22,6 +23,7 @@ struct __locale_map { const unsigned char *table_root; const unsigned char *langinfo; const unsigned char *errors; + struct collation collate; }; extern hidden volatile int __locale_lock[1]; @@ -38,6 +40,7 @@ hidden char *__gettextdomain(void); #define LOC_MAP_FAILED ((const struct __locale_map *)-1) +#define LMPTR(l,c,m) ((l) && (l)->cat[(c)] ? &(l)->cat[(c)]->m : 0) #define LMEMB(l,c,m) ((l) && (l)->cat[(c)] ? (l)->cat[(c)]->m : 0) #define LPATH(...) { sizeof((int[]){__VA_ARGS__})/sizeof(int), __VA_ARGS__ } diff --git a/src/locale/collate.c b/src/locale/collate.c new file mode 100644 index 00000000..909e4446 --- /dev/null +++ b/src/locale/collate.c @@ -0,0 +1,180 @@ +#include +#include +#include "collate.h" +#include "ikmlt.h" + +static const unsigned char ccc_slot[] = { CCC_SLOTS }; + +static void buffer_wc(struct cm_iterator *mi, wchar_t wc) +{ + mi->context_buf[mi->context_pos] = wc; + if (mi->context_pos == PREFIX_MAX-1) mi->context_pos = 0; + else mi->context_pos++; +} + +static int load_uni(const unsigned char *p) +{ + return ((unsigned)p[0]<<24 | p[1]<<16 | p[2]<<8 | p[3]) & 0xffffff; +} + +static unsigned char *implicit_ce(struct cm_iterator *mi, wchar_t wc) +{ + unsigned char *buf = mi->implicit_buf; + const unsigned char *ir; + for (int i=0; (ir=ikmlt_lookup(mi->implicit_rules, i)); i++) { + int start = load_uni(ir+0); + int end = load_uni(ir+4); + if (wc < start || wc > end) continue; + int base = load_uni(ir+8); + wc -= base; + if (ir[12] != 1) continue; + int blb = ir[13]; + int po = ir[14], so = ir[16]; + int pl = ir[15], sl = ir[17]; + if (pl+sl+3 > IMPLICIT_MAX) continue; + memcpy(buf, ir+po, pl); + memcpy(buf+pl+3, ir+so, sl); + buf[pl+0] = blb + (wc>>13); + buf[pl+1] = 0x80 + ((wc>>6) & 0x7f); + buf[pl+2] = 0x80 + (wc & 0x3f) * 2; + return buf; + } + /* As a last resort, emit a fully-ignorable */ + buf[0] = 0xfd; + for (int i=0; ini); + int ccc = ch>>24; + if (!ccc || !mi->nskip[ccc_slot[ccc]]) + return ch; + mi->nskip[ccc_slot[ccc]]--; + } +} + +static const unsigned char *match_discontig(struct cm_iterator *mi, const unsigned char *cm, int prev_ccc) +{ + struct nfd_iterator ni = mi->ni; + + int mismatch_in_class = 1; + size_t cnt_in_class = 0; + + while (*cm == 0 || *cm == 255) { + uint32_t ch = nfd_iterate_ccc(&ni); + int ccc = ch>>24; + if (!ccc) + return ikmlt_lookup(cm, 0); + if (ccc != prev_ccc) { + cnt_in_class = 0; + mismatch_in_class = 0; + } + prev_ccc = ccc; + cnt_in_class++; + if (mismatch_in_class) + continue; + if (cnt_in_class <= mi->nskip[ccc_slot[ccc]]) + continue; + const unsigned char *tmp = ikmlt_lookup(cm, ch & 0xffffff); + if (tmp) { + buffer_wc(mi, ch & 0xffffff); + mi->nskip[ccc_slot[ccc]]++; + cm = tmp; + } else { + mismatch_in_class = 1; + } + } + return cm; +} + +static const unsigned char *cm_iterate(struct cm_iterator *mi) +{ + uint32_t ch = mi->pending_ch; + mi->pending_ch = 0; + if (!ch) ch = next_ch(mi); + if (!ch) return 0; + const unsigned char *tmp, *cm = ikmlt_lookup(mi->cm_root, ch & 0xffffff); + + if (!cm) cm = implicit_ce(mi, ch & 0xffffff); + + int i = mi->context_pos; + while (*cm == 255) { + if (i) i--; + else i=PREFIX_MAX-1; + tmp = ikmlt_lookup(cm, -(int)mi->context_buf[i]); + if (!tmp) break; + cm = tmp; + } + buffer_wc(mi, ch & 0xffffff); + while (*cm == 0 || *cm == 255) { + ch = next_ch(mi); + tmp = ikmlt_lookup(cm, ch & 0xffffff); + if (!tmp) { + mi->pending_ch = ch; + if (ch>>24) cm = match_discontig(mi, cm, ch>>24); + else cm = ikmlt_lookup(cm, 0); + break; + } + buffer_wc(mi, ch & 0xffffff); + cm = tmp; + } + return cm; +} + +static void cm_iterator_start(struct cm_iterator *mi, const void *src, int wide, const struct collation *col) +{ + *mi = (struct cm_iterator){0}; + nfd_iterator_start(&mi->ni, src, wide); + mi->cm_root = col->mappings_root; + mi->implicit_rules = col->implicit_rules; +} + +const unsigned char *ce_iterate(struct ce_iterator *ci) +{ + const unsigned char *ce = ci->ce; + if (!ce) { + ce = cm_iterate(&ci->mi); + if (!ce || *ce != 0xfe) return ce; + ci->rem = ce[1]; // fixme: handle bogus 0? + ce += 2; + } + if (--ci->rem) { + const unsigned char *h = ikmlt_lookup(ci->hd, *ce); + if (h) ci->ce = ce + 1 + h[1]; + else ci->ce = ce + 4 + ce[ci->nlevels]; + } else { + ci->rem = 0; + ci->ce = 0; + } + return ce; +} + +void ce_iterator_start(struct ce_iterator *ci, const void *src, int wide, const struct collation *col) +{ + *ci = (struct ce_iterator){0}; + cm_iterator_start(&ci->mi, src, wide, col); + ci->hd = col->header_dict; + ci->flags = col->levels; + ci->nlevels = *ci->flags++; +} + +int collation_init(struct collation *col, const unsigned char *collation_root) +{ + const unsigned char *l, *m, *h, *i; + l = ikmlt_lookup(collation_root, 0); + m = ikmlt_lookup(collation_root, 1); + h = ikmlt_lookup(collation_root, 2); + i = ikmlt_lookup(collation_root, 3); + if (!l || !h || !m || !i) { + *col = (struct collation){0}; + return -1; + } + col->levels = l; + col->mappings_root = m; + col->header_dict = h; + col->implicit_rules = i; + return 0; +} diff --git a/src/locale/locale_map.c b/src/locale/locale_map.c index f4ecad28..153606cb 100644 --- a/src/locale/locale_map.c +++ b/src/locale/locale_map.c @@ -31,6 +31,13 @@ static const char envvars[][12] = { volatile int __locale_lock[1]; volatile int *const __locale_lockptr = __locale_lock; +static int dummy_collation_init(struct collation *col, const unsigned char *collation_root) +{ + return 0; +} + +weak_alias(dummy_collation_init, __collation_init); + static int load_locale(struct __locale_map *l, const unsigned char *lm) { const unsigned char *root; @@ -47,6 +54,8 @@ static int load_locale(struct __locale_map *l, const unsigned char *lm) /* strerror, etc. strings */ l->errors = ikmlt_lookup(root, K_ERRORS); + collation_init(&l->collate, ikmlt_lookup(root, K_COLLATION)); + return 0; } diff --git a/src/locale/strcoll.c b/src/locale/strcoll.c index dd3cbc48..60be5607 100644 --- a/src/locale/strcoll.c +++ b/src/locale/strcoll.c @@ -1,10 +1,124 @@ #include #include #include "locale_impl.h" +#include "ikmlt.h" + +static int is_ignorable(const unsigned char *ce, const unsigned char *h, int level) +{ + if (h) return !(h[2+4*level+1] + h[2+4*level+3]); + else return !(level ? ce[1+level]-ce[level] : ce[1]); +} + +static int decode_ce(char *d, const unsigned char *ce, const unsigned char *h, int level, int nlevels) +{ + if (h) { + const unsigned char *k = h + 2+4*level; + memcpy(d, h+k[2], k[3]); + memcpy(d+k[3], ce+1+k[0], k[1]); + return k[3] + k[1]; + } else { + int o = level ? ce[level] : 0; + memcpy(d, ce+1+nlevels+o, ce[1+level] - o); + return ce[1+level] - o; + } +} + +/* dir must be 1 or -1 */ +static void ctr_step(size_t ctr[2], int dir) +{ + size_t old = ctr[0]; + ctr[0] += dir; + if ((old^ctr[0]) / (SIZE_MAX/2+1)) + ctr[1] += dir; +} + +static int ctr_sign(const size_t ctr[2]) +{ + if (ctr[1] / (SIZE_MAX/2+1)) return -1; + if (ctr[1] || ctr[0]) return 1; + return 0; +} + +int __strcoll_core(const void *l, const void *r, int wide, const struct collation *col) +{ + struct ce_iterator ci[2], ci0[2]; + ce_iterator_start(&ci[0], l, wide, col); + ce_iterator_start(&ci[1], r, wide, col); + ci0[0] = ci[0]; + ci0[1] = ci[1]; + + const unsigned char *flags = col->levels; + const unsigned char *hd = col->header_dict; + int nlevels = *flags++; + int need_next_cnt = (nlevels > 1 && (flags[1] & 1)); + size_t next_cnt[2] = { 0 }; + const unsigned char *ce[2], *h[2]; + int level = 0; + int latest_diff = 0; + int reverse = 0; + + for (;;) { + for (int i=0; i<2; i++) do { + ce[i] = ce_iterate(&ci[i]); + if (!ce[i]) break; + h[i] = ikmlt_lookup(hd, *ce[i]); + if (need_next_cnt && level+1 < nlevels && + !is_ignorable(ce[i], h[i], level+1)) + ctr_step(next_cnt, 1-2*i); + } while (is_ignorable(ce[i], h[i], level)); + + if (!ce[0] != !ce[1]) return !ce[1] - !ce[0]; + + if (!ce[0]) { + if (latest_diff) return latest_diff; + latest_diff = 0; + + level++; + if (level == nlevels) return 0; + for (int i=0; i<2; i++) ci[i] = ci0[i]; + reverse = 0; + + if (need_next_cnt) { + reverse = 1; + latest_diff = ctr_sign(next_cnt); + /* Skip CEs from the longer sequence to align + * their ends for reverse-order comparison. */ + int i = (1-latest_diff) >> 1; + while (ctr_sign(next_cnt)) { + ce[i] = ce_iterate(&ci[i]); + if (!ce[i]) break; + h[i] = ikmlt_lookup(hd, *ce[i]); + if (!is_ignorable(ce[i], h[i], level)) + ctr_step(next_cnt,-latest_diff); + } + } + next_cnt[0] = next_cnt[1] = 0; + need_next_cnt = (level+1 < nlevels && (flags[level+1] & 1)); + continue; + } + + char buf[2][10]; // FIXME: 10? + for (int i=0; i<2; i++) { + int l = decode_ce(buf[i], ce[i], h[i], level, nlevels); + buf[i][l] = 0; + } + + int diff = strcmp(buf[0], buf[1]); + if (diff) { + if (!reverse) return diff; + latest_diff = diff; + } + } +} int __strcoll_l(const char *l, const char *r, locale_t loc) { - return strcmp(l, r); + const struct collation *col = LMPTR(loc, LC_COLLATE, collate); + + /* In absence of collation rules, strcoll behaves as strcmp. */ + if (!col || !col->levels) return strcmp(l, r); + + return __strcoll_core(l, r, 0, col); } int strcoll(const char *l, const char *r) diff --git a/src/locale/strxfrm.c b/src/locale/strxfrm.c index c66c6203..1e8c3714 100644 --- a/src/locale/strxfrm.c +++ b/src/locale/strxfrm.c @@ -1,13 +1,98 @@ #include #include #include "locale_impl.h" +#include "ikmlt.h" + +size_t __strxfrm_core(char *restrict dest, const void *restrict src, size_t n, int wide, const struct collation *col) +{ + char *d = dest; + int level = 0; + int reverse = 0; + size_t cur_len = 0, next_len = 0; + const unsigned char *flags = col->levels; + const unsigned char *hd = col->header_dict; + int nlevels = *flags++; + int need_next_len = (nlevels > 1 && (flags[1] & 1)); + size_t total_len = nlevels-1; + + struct ce_iterator ci, ci0; + ce_iterator_start(&ci, src, wide, col); + ci0 = ci; + + for (;;) { + const unsigned char *ce = ce_iterate(&ci); + if (!ce) { + /* no need for more passes if we can't store output */ + if (!d) return total_len; + if (reverse) { + d += cur_len; + reverse = 0; + } + /* use 0x01 byte as hard-coded level separator since + * it is the least possible nonzero weight byte. */ + if (level+1 < nlevels) *d++ = 0x01; + if (level+1 < nlevels && (flags[level+1] & 1)) { + reverse = 1; + if (d) d += next_len; + } + level++; + if (level == nlevels) break; + ci = ci0; + cur_len = next_len; + next_len = 0; + need_next_len = (level+1 < nlevels && (flags[level+1] & 1)); + continue; + } + const unsigned char *h = ikmlt_lookup(hd, *ce & 0x7f); + if (h) { + if (!level) { + total_len += h[0]; + if (total_len > SIZE_MAX/2) return SIZE_MAX; + if (total_len >= n) d = 0; + } + if (need_next_len) + next_len += h[2+4*(level+1)+1] + h[2+4*(level+1)+3]; + const unsigned char *k = h + 2+4*level; + int l = k[1]+k[3]; + if (d) { + if (reverse) d -= l; + memcpy(d, h+k[2], k[3]); + memcpy(d+k[3], ce+1+k[0], k[1]); + if (!reverse) d += l; + } + } else { + if (!level) { + total_len += ce[nlevels]; + if (total_len > SIZE_MAX/2) return SIZE_MAX; + if (total_len >= n) d = 0; + } + if (need_next_len) + next_len += ce[1+level+1]-ce[1+level]; + int o = level ? ce[level] : 0; + int l = ce[1+level] - o; + if (d) { + if (reverse) d -= l; + memcpy(d, ce+1+nlevels+o, l); + if (!reverse) d += l; + } + } + } + *d++ = 0; + return total_len; +} -/* collate only by code points */ size_t __strxfrm_l(char *restrict dest, const char *restrict src, size_t n, locale_t loc) { - size_t l = strlen(src); - if (n > l) strcpy(dest, src); - return l; + const struct collation *col = LMPTR(loc, LC_COLLATE, collate); + + /* In absence of collation rules, strxfrm behaves as identity. */ + if (!col || !col->levels) { + size_t l = strlen(src); + if (l < n) memcpy(dest, src, l+1); + return l; + } + + return __strxfrm_core(dest, src, n, 0, col); } size_t strxfrm(char *restrict dest, const char *restrict src, size_t n) diff --git a/src/locale/wcscoll.c b/src/locale/wcscoll.c index ad2cc691..f1916246 100644 --- a/src/locale/wcscoll.c +++ b/src/locale/wcscoll.c @@ -2,10 +2,14 @@ #include #include "locale_impl.h" -/* FIXME: stub */ -int __wcscoll_l(const wchar_t *l, const wchar_t *r, locale_t locale) +int __wcscoll_l(const wchar_t *l, const wchar_t *r, locale_t loc) { - return wcscmp(l, r); + const struct collation *col = LMPTR(loc, LC_COLLATE, collate); + + /* In absence of collation rules, wcscoll behaves as wcscmp. */ + if (!col || !col->levels) return wcscmp(l, r); + + return __strcoll_core(l, r, 1, col); } int wcscoll(const wchar_t *l, const wchar_t *r) diff --git a/src/locale/wcsxfrm.c b/src/locale/wcsxfrm.c index 05e3e115..df83b10c 100644 --- a/src/locale/wcsxfrm.c +++ b/src/locale/wcsxfrm.c @@ -2,17 +2,29 @@ #include #include "locale_impl.h" -/* collate only by code points */ size_t __wcsxfrm_l(wchar_t *restrict dest, const wchar_t *restrict src, size_t n, locale_t loc) { - size_t l = wcslen(src); - if (l < n) { - wmemcpy(dest, src, l+1); - } else if (n) { - wmemcpy(dest, src, n-1); - dest[n-1] = 0; + const struct collation *col = LMPTR(loc, LC_COLLATE, collate); + + /* In absence of collation rules, strxfrm behaves as identity. */ + if (!col || !col->levels) { + size_t l = wcslen(src); + if (l < n) wmemcpy(dest, src, l+1); + return l; } - return l; + + /* Transform into second half of the dest wchar_t buffer as if it were + * a char buffer, then expand pairs of chars into wchar_t slots. */ + size_t h = n*sizeof(wchar_t)/2; + unsigned char *t = (unsigned char *)dest + h; + size_t l = __strxfrm_core((char *)t, src, h, 1, col); + size_t wl = (l+1)/2; + if (wl >= n) return wl; + + for (size_t i=0; i < wl; i++) + dest[i] = 0xF0000 + t[2*i]*256 + t[2*i+1]; + dest[wl] = 0; + return wl; } size_t wcsxfrm(wchar_t *restrict dest, const wchar_t *restrict src, size_t n) -- 2.21.0