More 2-stage lookup tables

1 files changed, 102 insertions, 45 deletions

diff --git a/gen/prop/stc b/gen/prop/stc
index eb65d07..3df2004 100755
--- a/gen/prop/stc
+++ b/gen/prop/stc
@@ -1,45 +1,102 @@
-#!/bin/sh
-
-set -e
-cd "${0%/*}/../.."
-exec >lib/unicode/prop/uprop_get_stc.c
-
-gawk '
-BEGIN {
-	FS = ";"
-
-	print "/* This file is autogenerated by gen/prop/stc; DO NOT EDIT. */"
-	print ""
-	print "#include \"_bsearch.h\""
-	print "#include \"macros.h\""
-	print "#include \"rune.h\""
-	print "#include \"unicode/prop.h\""
-	print ""
-}
-
-length($15) > 0 && $13 != $15 && $1 != $15 {
-	map[strtonum("0X" $1)] = strtonum("0X" $15)
-}
-
-END {
-	print "static const struct {"
-	print "\trune k, v;"
-	print "} lookup[] = {"
-
-	for (i = 0x100; i <= 0x10FFFF; i++) {
-		if (!map[i])
-			continue
-		printf "\t{RUNE_C(0x%06X), RUNE_C(0x%06X)},\n", i, map[i]
-	}
-
-	print "};"
-	print ""
-	print "_MLIB_DEFINE_BSEARCH_KV(rune, lookup, uprop_get_suc(ch))"
-	print ""
-	print "rune"
-	print "uprop_get_stc(rune ch)"
-	print "{"
-	print "\treturn mlib_lookup_kv(ch);"
-	print "}"
-}
-' data/UnicodeData
+#!/usr/bin/python3
+
+import math
+
+from lib import *
+
+
+longest = 0
+
+def parse(file: str) -> list[bool]:
+	global longest
+
+	xs = ['0'] * 0x110000
+	with open(file, 'r') as f:
+		for line in f.readlines():
+			if len(line.strip()) == 0 or line[0] == '#':
+				continue
+
+			parts = line.split(';')
+			parts[14] = parts[14].strip()
+			if (
+				parts[14] == '' or
+				parts[12] == parts[14] or
+				parts[00] == parts[14]
+			):
+				continue
+			n = int(parts[0], 16)
+			xs[n] = f'RUNE_C(0x{parts[14]})'
+			longest = max(longest, len(xs[n]))
+	return xs
+
+def genfile(cs: list[tuple[bool, ...]], blksize: int) -> None:
+	Cs = cs
+	cs = list(dict.fromkeys(Cs))
+
+	assert len(cs) == 2, f'{len(cs)=}, need a 2-stage lookup'
+
+	print('''\
+/* This file is autogenerated by gen/prop/stc; DO NOT EDIT. */
+
+#include <stdint.h>
+
+#include "rune.h"
+#include "unicode/prop.h"
+''')
+
+	ppc = columns(blksize, longest + 1)
+	print(f'static constexpr rune lookup[][{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(' ' * (longest + 1 - len(c[i*ppc + j])), end='')
+			if i < blksize // ppc - 1:
+				print()
+		print('},')
+	print('};')
+
+	print()
+
+	print(f'''\
+rune
+uprop_get_stc(rune ch)
+{{
+	rune hc = lookup[ch / {blksize} != 0][ch % {blksize}];
+	return hc == 0 ? uprop_get_suc(ch) : hc;
+}}''')
+
+def main() -> None:
+	cwd_init()
+	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 = set(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)]
+	with open('lib/unicode/prop/uprop_get_stc.c', 'w') as f:
+		sys.stdout = f
+		genfile(Cs, blksize)
+
+	report_size(len(xs), smallest)
+
+if __name__ == '__main__':
+	main()