aboutsummaryrefslogtreecommitdiff
path: root/gen
diff options
context:
space:
mode:
authorThomas Voss <mail@thomasvoss.com> 2024-04-28 09:21:44 +0200
committerThomas Voss <mail@thomasvoss.com> 2024-04-28 09:21:44 +0200
commitb0a33e153973a1db86fe1d6aa2fbba53cee374a2 (patch)
treeca538814eaa5e14bb2646c8ce4a0e10b0f84bc4a /gen
parent5b4c1d02ce9108be74e60e9993254a71c5fa9318 (diff)
Use a 2-stage lookup table for uprop_get_gc()
Diffstat (limited to 'gen')
-rwxr-xr-xgen/prop/gc161
-rw-r--r--gen/prop/lib.py7
2 files changed, 101 insertions, 67 deletions
diff --git a/gen/prop/gc b/gen/prop/gc
index 3535102..4f95242 100755
--- a/gen/prop/gc
+++ b/gen/prop/gc
@@ -1,67 +1,94 @@
-#!/bin/sh
-
-set -e
-cd "${0%/*}/../.."
-exec >lib/unicode/prop/uprop_get_gc.c
-
-gawk '
-BEGIN {
- FS = ";"
-
- print "/* This file is autogenerated by gen/prop/gc; DO NOT EDIT. */"
- print ""
- print "#include \"_bsearch.h\""
- print "#include \"macros.h\""
- print "#include \"rune.h\""
- print "#include \"unicode/prop.h\""
- print ""
-}
-
-{
- s = "GC_" toupper($3)
- lo = strtonum("0X" $1)
-
- if ($2 ~ /First/) {
- getline
- hi = strtonum("0X" $1)
- } else
- hi = lo
-
- for (i = lo; i <= hi; i++)
- props[i] = s
-}
-
-END {
- print "static constexpr enum uprop_gc lookup_lat1[] = {"
- for (i = 0; i < 0x100; i++) {
- if (i % 8 == 0)
- printf "\t"
- printf "%5s,%s", props[i], i % 8 == 7 ? "\n" : " "
- }
- print "};"
- print ""
- print "static const struct {"
- print "\trune lo, hi;"
- print "\tenum uprop_gc val;"
- print "} lookup[] = {"
-
- for (i = 0x100; i <= 0x10FFFF; i++) {
- if (!props[i])
- continue
- lo = i
- while (props[lo] == props[i + 1])
- i++
- printf "\t{RUNE_C(0x%06X), RUNE_C(0x%06X), %s},\n", lo, i, props[lo]
- }
-
- print "};"
- print ""
- print "_MLIB_DEFINE_BSEARCH(enum uprop_gc, lookup, GC_CN)"
- print ""
- print "enum uprop_gc"
- print "uprop_get_gc(rune ch)"
- print "{"
- print "\treturn ch < lengthof(lookup_lat1) ? lookup_lat1[ch] : mlib_lookup(ch);"
- print "}"
-}
-' data/UnicodeData
+#!/usr/bin/python3
+
+import math
+
+from lib import *
+
+
+def parse(file: str) -> list[bool]:
+ xs = ['GC_CN'] * 0x110000
+ with open(file, 'r') as f:
+ for line in f.readlines():
+ parts = line.split(';')
+ parts[0] = int(parts[0], 16)
+ if 'First' in parts[1]:
+ lo = parts[0]
+ elif 'Last' in parts[1]:
+ hi = parts[0]
+ for i in range(lo, hi + 1):
+ xs[i] = f'GC_{parts[2].upper()}'
+ else:
+ xs[parts[0]] = f'GC_{parts[2].upper()}'
+ return xs
+
+def genfile(cs: list[tuple[bool, ...]], blksize: int) -> None:
+ Cs = cs
+ cs = list(dict.fromkeys(Cs))
+
+ print('''\
+/* This file is autogenerated by gen/prop/gc; DO NOT EDIT. */
+
+#include "unicode/prop.h"
+''')
+
+ print(f'static constexpr {typename(len(cs) - 1)} stage1[] = {{')
+ for i, c in enumerate(Cs):
+ print(f'%c%{len(str(len(cs) - 1))}d,' % ('\t' if i % 16 == 0 else ' ', cs.index(c)), end='')
+ if i % 16 == 15:
+ print()
+ print('};')
+
+ print()
+
+ ppc = columns(blksize)
+ print(f'static constexpr enum uprop_gc stage2[][{blksize}] = {{')
+ for c in cs:
+ for i in range(blksize // ppc):
+ print('\t{' if i == 0 else '\t ', end='')
+ for j in range(ppc):
+ print(c[i*ppc + j], end='')
+ if i < blksize // ppc - 1 or j < ppc - 1:
+ print(',', end='')
+ if j < ppc - 1:
+ print(' ', end='')
+ if i < blksize // ppc - 1:
+ print()
+ print('},')
+ print('};')
+
+ print()
+
+ print(f'''\
+enum uprop_gc
+uprop_get_gc(rune ch)
+{{
+ return stage2[stage1[ch / {blksize}]][ch % {blksize}];
+}}''')
+
+def main() -> None:
+ cwd_init()
+ sys.stdout = open('lib/unicode/prop/uprop_get_gc.c', 'w')
+ xs = parse('data/UnicodeData')
+
+ blksize = -1
+ smallest = math.inf
+
+ for bs in powers_of_2():
+ if bs > len(xs):
+ break
+ Cs = [tuple(x) for x in chunks(xs, bs)]
+ cs = list(dict.fromkeys(Cs))
+
+ sz_s1 = len(Cs) * isize(len(cs) - 1)
+ sz_s2 = len(cs) * bs * 4
+ sz = sz_s1 + sz_s2
+
+ if sz < smallest:
+ smallest = sz
+ blksize = bs
+
+ Cs = [tuple(x) for x in chunks(xs, blksize)]
+ genfile(Cs, blksize)
+
+if __name__ == '__main__':
+ main()
diff --git a/gen/prop/lib.py b/gen/prop/lib.py
index b4c7e1e..0912208 100644
--- a/gen/prop/lib.py
+++ b/gen/prop/lib.py
@@ -1,4 +1,7 @@
import functools
+import os
+import sys
+from pathlib import Path
from typing import Generator
def chunks[T](xs: list[T], n: int) -> Generator[list[T], None, None]:
@@ -45,3 +48,7 @@ def typename(x: int) -> str:
if x < 18446744073709551615:
return "uint64_t"
raise ValueError
+
+def cwd_init() -> None:
+ dir = Path(os.path.dirname(sys.argv[0]))
+ os.chdir(dir / '..' / '..')