LordOS — a free, fast and secure GNU/Linux distribution based on Debian, with its own desktop environment: display server and Wayland compositor in C, a React UI engine on QuickJS, and private native apps.
C cdebiandesktop-environmentebpffirewalllandlocklinuxlinux-distributionopen-sourceprivacyquickjsraspberry-pi-5reactsecuritywaylandwayland-compositor
/* thbrk.c — Thai word breaking, like libthai (brk-maximal.c) but without linking it:
* reads the libthai-data dictionary (/usr/share/libthai/thbrk.tri, a libdatrie double-array
* trie) with our own reader and looks for the segmentation by "maximal matching": among the
* possible paths of dictionary words, the one that reaches farthest with the fewest characters
* outside words and the fewest breaks. If the dictionary is not there, it breaks where a
* syllable can start (the same hints libthai uses).
*
* The file comes from the system, but everything is still validated: sizes, signatures and indices. */
#include "thbrk.h"
#include <fcntl.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <unistd.h>
#define DICT_PATH "/usr/share/libthai/thbrk.tri"
#define MAX_FILE (32u << 20)
typedef struct { int32_t base, check; } Cell;
typedef struct { int32_t data; uint8_t *suffix; } TailBlock; /* suffix ends in 0 */
static struct {
int state; /* 0 not loaded, 1 loaded, -1 absent */
uint32_t alpha_begin, alpha_end;
int32_t *alpha_to_trie; /* -1 = not in the alphabet */
Cell *cells;
int32_t ncells;
TailBlock *tails;
int32_t ntails;
uint8_t *tail_mem;
} D;
static uint32_t rd32(const uint8_t *p) { return (uint32_t)p[0] << 24 | (uint32_t)p[1] << 16 | (uint32_t)p[2] << 8 | p[3]; }
static int load(void) {
int fd = open(DICT_PATH, O_RDONLY | O_CLOEXEC);
if (fd < 0) return -1;
struct stat st;
uint8_t *f = NULL;
size_t n = 0;
if (!fstat(fd, &st) && st.st_size > 0 && (uint64_t)st.st_size <= MAX_FILE) {
n = (size_t)st.st_size;
f = malloc(n);
size_t got = 0;
while (f && got < n) { ssize_t r = read(fd, f + got, n - got); if (r <= 0) break; got += (size_t)r; }
if (got != n) { free(f); f = NULL; }
}
close(fd);
if (!f) return -1;
size_t p = 0;
#define NEED(k) do { if (n - p < (size_t)(k)) goto bad; } while (0)
/* alphabet: character ranges → trie characters (1, 2, …; 0 is end of word) */
NEED(8);
if (rd32(f) != 0xD9FCD9FCu) goto bad;
uint32_t nranges = rd32(f + 4);
p = 8;
if (nranges == 0 || nranges > 1024) goto bad;
NEED((size_t)nranges * 8);
uint32_t lo = 0xffffffffu, hi = 0;
for (uint32_t i = 0; i < nranges; i++) {
uint32_t b = rd32(f + p + 8 * i), e = rd32(f + p + 8 * i + 4);
if (b > e || e > 0x10FFFF) goto bad;
if (b < lo) lo = b;
if (e > hi) hi = e;
}
if (hi - lo > 0xFFFF) goto bad;
D.alpha_begin = lo;
D.alpha_end = hi;
D.alpha_to_trie = malloc(sizeof *D.alpha_to_trie * (hi - lo + 1));
if (!D.alpha_to_trie) goto bad;
for (uint32_t c = 0; c <= hi - lo; c++) D.alpha_to_trie[c] = -1;
int32_t tc = 0;
for (uint32_t i = 0; i < nranges; i++) { /* in file order, like libdatrie */
uint32_t b = rd32(f + p + 8 * i), e = rd32(f + p + 8 * i + 4);
for (uint32_t a = b; a <= e; a++) {
if (tc == 0) tc++;
if (D.alpha_to_trie[a - lo] < 0) D.alpha_to_trie[a - lo] = tc++;
}
}
p += (size_t)nranges * 8;
/* double array: cell 0 = signature and number of cells; the root is cell 2 */
NEED(8);
if (rd32(f + p) != 0xDAFCDAFCu) goto bad;
D.ncells = (int32_t)rd32(f + p + 4);
p += 8;
if (D.ncells < 3 || D.ncells > (int32_t)(MAX_FILE / 8)) goto bad;
NEED((size_t)(D.ncells - 1) * 8);
D.cells = malloc(sizeof *D.cells * (size_t)D.ncells);
if (!D.cells) goto bad;
D.cells[0].base = D.cells[0].check = 0;
for (int32_t i = 1; i < D.ncells; i++) {
D.cells[i].base = (int32_t)rd32(f + p);
D.cells[i].check = (int32_t)rd32(f + p + 4);
p += 8;
}
/* tails: the rest of each word once it no longer branches */
NEED(12);
if (rd32(f + p) != 0xDFFCDFFCu) goto bad;
D.ntails = (int32_t)rd32(f + p + 8);
p += 12;
if (D.ntails < 0 || D.ntails > (int32_t)(MAX_FILE / 10)) goto bad;
D.tails = calloc((size_t)D.ntails + 1, sizeof *D.tails);
D.tail_mem = malloc(n - p + (size_t)D.ntails + 1);
if (!D.tails || !D.tail_mem) goto bad;
size_t m = 0;
for (int32_t i = 0; i < D.ntails; i++) {
NEED(10);
D.tails[i].data = (int32_t)rd32(f + p + 4);
int len = (int16_t)((f[p + 8] << 8) | f[p + 9]);
p += 10;
if (len < 0) goto bad;
NEED(len);
D.tails[i].suffix = D.tail_mem + m;
memcpy(D.tail_mem + m, f + p, (size_t)len);
m += (size_t)len;
D.tail_mem[m++] = 0;
p += (size_t)len;
}
#undef NEED
free(f);
return 0;
bad:
free(f);
free(D.alpha_to_trie); free(D.cells); free(D.tails); free(D.tail_mem);
memset(&D, 0, sizeof D);
return -1;
}
int thbrk_available(void) {
if (!D.state) D.state = load() ? -1 : 1;
return D.state > 0;
}
/* ---- trie traversal (libdatrie's trie_state_*) ---- */
typedef struct { int32_t index; int16_t suffix_idx; uint8_t is_suffix; } TState;
static int32_t trie_char(uint32_t c) {
if (!c) return 0;
return c >= D.alpha_begin && c <= D.alpha_end ? D.alpha_to_trie[c - D.alpha_begin] : -1;
}
static int32_t base_of(int32_t s) { return s >= 0 && s < D.ncells ? D.cells[s].base : 0; }
static int32_t check_of(int32_t s) { return s >= 0 && s < D.ncells ? D.cells[s].check : -1; }
static const uint8_t *suffix_of(int32_t t) { t -= 1; return t >= 0 && t < D.ntails ? D.tails[t].suffix : NULL; }
static int walk(TState *s, uint32_t c) {
int32_t tc = trie_char(c);
if (tc < 0) return 0;
if (!s->is_suffix) {
int32_t next = base_of(s->index) + tc;
if (check_of(next) != s->index) return 0;
s->index = next;
if (base_of(next) < 0) { s->index = -base_of(next); s->suffix_idx = 0; s->is_suffix = 1; }
return 1;
}
const uint8_t *suf = suffix_of(s->index);
if (!suf || suf[s->suffix_idx] != tc) return 0;
if (tc) s->suffix_idx++;
return 1;
}
static int terminal(const TState *s) {
if (!s->is_suffix) return check_of(base_of(s->index) + 0) == s->index;
const uint8_t *suf = suffix_of(s->index);
return suf && suf[s->suffix_idx] == 0;
}
static TState root(void) { return (TState){ 2, 0, 0 }; }
/* ---- hints: where a syllable can start (libthai's brk_brkpos_hints) ---- */
enum { KO_KAI = 0x0E01, RU = 0x0E24, LU = 0x0E26, WO_WAEN = 0x0E27, O_ANG = 0x0E2D, SARA_A = 0x0E30, MAI_HAN_AKAT = 0x0E31,
SARA_AA = 0x0E32, SARA_UEE = 0x0E37, SARA_E = 0x0E40, SARA_AE = 0x0E41, MAITAIKHU = 0x0E47, THANTHAKHAT = 0x0E4C };
static int is_cons(uint32_t c) { return c >= 0x0E01 && c <= 0x0E2E && c != RU && c != LU; }
static int is_tone(uint32_t c) { return c >= 0x0E48 && c <= 0x0E4B; }
static int is_upvowel(uint32_t c) { return c == 0x0E31 || (c >= 0x0E34 && c <= 0x0E37); }
static int is_ldvowel(uint32_t c) { return c >= 0x0E40 && c <= 0x0E44; }
static void hints(const uint32_t *s, int len, char *h) {
memset(h, 0, (size_t)len);
for (int i = 0; i < len;) {
if (is_cons(s[i])) {
if (i + 1 < len && s[i + 1] == THANTHAKHAT) i += 2;
else if (i + 2 < len && s[i + 2] == THANTHAKHAT) i += 3;
else if (i + 2 < len && s[i] != KO_KAI && s[i + 1] == MAITAIKHU && (s[i + 2] == O_ANG || s[i + 2] == WO_WAEN)) { h[i] = 1; i += 4; }
else if ((i > 0 && (s[i - 1] == MAI_HAN_AKAT || s[i - 1] == SARA_UEE)) ||
(i > 1 && is_tone(s[i - 1]) && (s[i - 2] == MAI_HAN_AKAT || s[i - 2] == SARA_UEE))) i++;
else h[i++] = 1;
} else if (s[i] == SARA_E || s[i] == SARA_AE) {
h[i] = 1;
i += 2;
if (i >= len) break;
if (s[i] == MAITAIKHU) i += 2;
else if (is_upvowel(s[i])) {
i++;
if (i < len && is_tone(s[i])) i++;
i++;
} else if (i + 2 < len && ((s[i + 1] == SARA_AA && s[i + 2] == SARA_A) ||
(s[i] != KO_KAI && s[i + 1] == MAITAIKHU && s[i + 2] != O_ANG && s[i + 2] != WO_WAEN)))
i += 3;
} else if (is_ldvowel(s[i])) { h[i] = 1; i += 2; }
else if (s[i] == RU || s[i] == LU) h[i++] = 1;
else i++;
}
}
/* ---- maximal matching (libthai's brk_maximal_do_impl) ---- */
typedef struct Shot {
struct Shot *next;
TState st;
int str_pos, cur, penalty;
int *brk;
} Shot;
typedef struct { int nbrk; Shot *free_list; int fail; } Env;
static Shot *shot_new(Env *e, const Shot *src) {
Shot *n = e->free_list;
if (n) e->free_list = n->next;
else {
n = malloc(sizeof *n);
if (!n) { e->fail = 1; return NULL; }
n->brk = malloc(sizeof *n->brk * (size_t)(e->nbrk + 1));
if (!n->brk) { free(n); e->fail = 1; return NULL; }
}
n->st = src->st;
n->str_pos = src->str_pos;
n->cur = src->cur;
n->penalty = src->penalty;
if (src->brk && src->cur) memcpy(n->brk, src->brk, sizeof *n->brk * (size_t)src->cur);
n->next = NULL;
return n;
}
static void shot_free(Env *e, Shot *s) { s->next = e->free_list; e->free_list = s; }
static void env_free(Env *e) { while (e->free_list) { Shot *n = e->free_list->next; free(e->free_list->brk); free(e->free_list); e->free_list = n; } }
static Shot *pool_delete(Env *e, Shot *pool, Shot *node) {
if (pool == node) pool = pool->next;
else { Shot *p = pool; while (p && p->next != node) p = p->next; if (p) p->next = node->next; }
shot_free(e, node);
return pool;
}
static void pool_free(Env *e, Shot *pool) { while (pool) { Shot *n = pool->next; shot_free(e, pool); pool = n; } }
static Shot *pool_get(Shot *pool) { /* the one that advanced least */
Shot *chosen = NULL;
int min = 0x7fffffff;
for (; pool; pool = pool->next) {
if (!pool->cur) return pool;
int p = pool->brk[pool->cur - 1];
if (p < min) { min = p; chosen = pool; }
}
return chosen;
}
static Shot *pool_match(Shot *pool, const Shot *node) { /* another one that broke at the same place */
for (; pool; pool = pool->next) {
if (pool == node) continue;
if (!node->cur ? !pool->cur : pool->cur > 0 && pool->brk[pool->cur - 1] == node->brk[node->cur - 1]) return pool;
}
return NULL;
}
static Shot *root_pool(Env *e, int nbrk) {
Shot r = { NULL, root(), 0, 0, 0, NULL };
e->nbrk = nbrk;
return shot_new(e, &r);
}
#define RECOVERED_WORDS 3
static int recover_try(const uint32_t *ws, int len, const char *h, int words, int *last, Env *e) {
Env sub = { 0, NULL, 0 };
Shot *pool = root_pool(&sub, words), *node;
int ret = 0;
while (!sub.fail && (node = pool_get(pool))) {
int keep = 1, term = 0;
for (;;) {
do {
if (!walk(&node->st, ws[node->str_pos++])) { keep = 0; break; }
term = terminal(&node->st);
if (node->str_pos >= len) { if (!term) keep = 0; break; }
} while (!(term && h[node->str_pos]));
if (!keep) { pool = pool_delete(&sub, pool, node); break; }
if (node->str_pos < len && !node->st.is_suffix) {
Shot *nn = shot_new(&sub, node);
if (nn) { nn->next = pool; pool = nn; node = nn; }
}
node->st = root();
node->brk[node->cur++] = node->str_pos;
if (node->str_pos == len || node->cur == words) {
if (node->cur > ret) { ret = node->cur; *last = node->brk[ret - 1]; }
pool = pool_delete(&sub, pool, node);
if (ret == words) goto done;
break;
}
Shot *tail = pool, *m;
while ((m = pool_match(tail, node))) { Shot *nx = m->next; pool = pool_delete(&sub, pool, m); tail = nx; }
}
}
done:
pool_free(&sub, pool);
env_free(&sub);
(void)e;
return ret;
}
typedef struct { int pos, recov; } Hist;
/* From where words can be recognized again (RECOVERED_WORDS in a row) after a
* run that is not in the dictionary. */
static int recover(const uint32_t *ws, int len, int pos, const char *h, Hist *rh, Env *e) {
int last = 0;
while (pos < len && !h[pos]) pos++;
if (rh->pos == pos) return rh->recov;
for (int p = pos; p < len; p++)
if (h[p]) {
int n = recover_try(ws + p, len - p, h + p, RECOVERED_WORDS, &last, e);
/* libthai compares ws[last] (last is relative to p) with the end of the text: we keep that */
if (n == RECOVERED_WORDS || (n > 0 && last >= len)) { rh->pos = pos; rh->recov = p; return p; }
}
return -1;
}
int thbrk_chunk(const uint32_t *ws, int len, int *out, int max) {
if (len <= 1 || max <= 0) return 0;
char *h = malloc((size_t)len + 1);
if (!h) return 0;
hints(ws, len, h);
if (!thbrk_available()) { /* without a dictionary: syllable starts */
int k = 0;
for (int i = 1; i < len && k < max; i++) if (h[i]) out[k++] = i;
free(h);
return k;
}
Env e = { 0, NULL, 0 };
Shot *pool = root_pool(&e, len + 1), *node;
int *best = malloc(sizeof *best * (size_t)(len + 1)), nbest = 0, best_pos = 0, best_pen = 0;
Hist rh = { -1, -1 };
while (best && !e.fail && (node = pool_get(pool))) {
int keep = 1, term = 0, recovered = 0, sp = node->str_pos;
do {
if (!walk(&node->st, ws[sp++])) {
term = 0;
int r = recover(ws, len, node->str_pos + 1, h, &rh, &e);
if (r != -1) {
node->penalty += r;
if (node->cur > 0) node->penalty -= node->brk[node->cur - 1];
sp = r;
recovered = 1;
} else {
node->penalty += len;
if (node->cur > 0) node->penalty -= node->brk[node->cur - 1];
node->brk[node->cur++] = sp = len;
keep = 0;
}
break;
}
term = terminal(&node->st);
if (sp >= len) {
if (!term) {
node->penalty += len;
if (node->cur > 0) node->penalty -= node->brk[node->cur - 1];
node->brk[node->cur++] = len;
keep = 0;
}
break;
}
} while (!(term && h[sp]));
node->str_pos = sp;
if (keep && (term || recovered)) {
if (node->str_pos < len && term && !node->st.is_suffix) {
Shot *nn = shot_new(&e, node); /* also the path that follows the longest word */
if (nn) { nn->next = pool; pool = nn; node = nn; }
}
node->st = root();
node->brk[node->cur++] = node->str_pos;
}
if (!keep || node->str_pos == len || node->cur >= len + 1) {
if (node->str_pos > best_pos || (node->str_pos == best_pos && (node->penalty < best_pen ||
(node->penalty == best_pen && node->cur <= nbest)))) {
memcpy(best, node->brk, sizeof *best * (size_t)node->cur);
nbest = node->cur;
best_pos = node->str_pos;
best_pen = node->penalty;
}
pool = pool_delete(&e, pool, node);
} else {
Shot *tail = pool, *m;
while ((m = pool_match(tail, node))) {
Shot *nx = m->next, *del;
if (m->penalty < node->penalty || (m->penalty == node->penalty && m->cur < node->cur)) {
del = node;
if (nx == node) nx = node->next;
node = m;
} else del = m;
pool = pool_delete(&e, pool, del);
tail = nx;
}
}
}
pool_free(&e, pool);
env_free(&e);
int k = 0;
for (int i = 0; best && i < nbest && k < max; i++) if (best[i] > 0 && best[i] < len) out[k++] = best[i];
free(best);
free(h);
return k;
}
/* libthai's break classes (brk-ctype.c) for the Thai block: only letters and marks
* (THAI) go to the dictionary; ๆ and ฯ are not separated from what precedes them; digits and ฿ follow the
* number rules. */
enum { C_THAI, C_ALPHA, C_NUM, C_NBB, C_NUM_CUR, C_TERM, C_OTHER };
static int th_class(uint32_t c) {
if (c == 0x0E2F || c == 0x0E46) return C_NBB;
if (c == 0x0E3F) return C_NUM_CUR;
if (c == 0x0E4F) return C_ALPHA;
if (c >= 0x0E50 && c <= 0x0E59) return C_NUM;
if (c == 0x0E5A || c == 0x0E5B) return C_TERM;
if ((c >= 0x0E01 && c <= 0x0E3A) || (c >= 0x0E40 && c <= 0x0E4E)) return C_THAI;
return C_OTHER;
}
int thbrk_is_thai(uint32_t c) { return th_class(c) == C_THAI; }
int thbrk_pair(uint32_t a, uint32_t b) {
int x = th_class(a), y = th_class(b);
if (x == C_OTHER || y == C_OTHER) return -1;
/* libthai's _break_table, only these rows and columns (I = indirect: without a space, no) */
static const uint8_t t[6][6] = {
/* THAI ALPHA NUM NBB NUM_CUR TERM */
/* THAI */ { 0, 1, 0, 0, 1, 0 },
/* ALPHA */ { 1, 0, 0, 0, 0, 0 },
/* NUM */ { 1, 0, 0, 0, 0, 0 },
/* NBB */ { 1, 1, 1, 0, 1, 0 },
/* NUM_CUR */ { 1, 0, 0, 0, 0, 0 },
/* TERM */ { 1, 1, 1, 0, 1, 0 },
};
return t[x][y];
}
#define MAX_ACRONYM_FRAG 3
static void chunk_breaks(const uint32_t *s, int a, int b, uint8_t *bk) {
int len = b - a;
for (int k = a + 1; k < b; k++) bk[k] = 2;
int *pos = len > 1 ? malloc(sizeof *pos * (size_t)len) : NULL;
int m = pos ? thbrk_chunk(s + a, len, pos, len) : 0;
for (int k = 0; k < m; k++) bk[a + pos[k]] = 1;
free(pos);
}
void thbrk_text(const uint32_t *s, int n, uint8_t *bk) {
/* between letters and ๆ, digits or ฿: libthai's table */
for (int i = 1; i < n; i++) {
int pr = thbrk_pair(s[i - 1], s[i]);
if (pr >= 0 && !(thbrk_is_thai(s[i - 1]) && thbrk_is_thai(s[i]))) bk[i] = pr ? 1 : 2;
}
for (int i = 0; i < n;) {
if (!thbrk_is_thai(s[i])) { i++; continue; }
/* abbreviations like libthai: up to 3 letters followed by a period ("พ.ศ.", "กอ.รมน.") are not broken */
int chunk = i, ae = i, p = i;
while (p < n) {
if (thbrk_is_thai(s[p])) {
if (ae > chunk && p - ae > MAX_ACRONYM_FRAG) break;
p++;
} else if (s[p] == '.' && p - ae <= MAX_ACRONYM_FRAG) ae = ++p;
else break;
}
if (ae > chunk) {
for (int k = chunk + 1; k < ae; k++) bk[k] = 2;
if (ae < n && thbrk_is_thai(s[ae])) bk[ae] = 1; /* after the period it can break */
i = ae;
continue;
}
chunk_breaks(s, chunk, p, bk);
i = p;
}
}