From 904fa4d94f30825bec490133ff402c6350f45e26 Mon Sep 17 00:00:00 2001 From: Sam Atman Date: Wed, 4 Feb 2026 21:21:14 -0500 Subject: Teasing out canonicalization After coping with a spuriously broken autohash for awhile, I got the one remaining hash table moved into memory, so there's no further reason to put up with allocation of basic structures. So that's nice. --- codegen/canon.zig | 182 +++++++++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 159 insertions(+), 23 deletions(-) (limited to 'codegen/canon.zig') diff --git a/codegen/canon.zig b/codegen/canon.zig index d95a905..e92be5d 100644 --- a/codegen/canon.zig +++ b/codegen/canon.zig @@ -1,12 +1,38 @@ const std = @import("std"); const builtin = @import("builtin"); +const block_size = 256; +const Block = [block_size]Canonicalization; + +const Canonicalization = struct { + len: u3 = 0, + cps: [2]u21 = [_]u21{0} ** 2, +}; + +const BlockMap = std.HashMap( + Block, + u16, + struct { + pub fn hash(_: @This(), k: Block) u64 { + var hasher = std.hash.Wyhash.init(0); + std.hash.autoHashStrat(&hasher, k, .DeepRecursive); + return hasher.final(); + } + + pub fn eql(_: @This(), aBlock: Block, bBlock: Block) bool { + return for (aBlock, bBlock) |a, b| { + if (a.len != b.len or a.cps[0] != b.cps[0] or a.cps[1] != b.cps[1]) return false; + } else true; + } + }, + std.hash_map.default_max_load_percentage, +); + pub fn main() anyerror!void { var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator); defer arena.deinit(); const allocator = arena.allocator(); - var write_buf: [4096]u8 = undefined; // Process UnicodeData.txt var in_reader = std.io.Reader.fixed(@embedFile("UnicodeData.txt")); var args_iter = try std.process.argsWithAllocator(allocator); @@ -14,53 +40,163 @@ pub fn main() anyerror!void { _ = args_iter.skip(); const output_path = args_iter.next() orelse @panic("No output file arg!"); - var out_file = try std.fs.cwd().createFile(output_path, .{}); - defer out_file.close(); - var file_writer = out_file.writer(&write_buf); - var writer = &file_writer.interface; - const endian = builtin.cpu.arch.endian(); + var canon_map = std.AutoHashMap(u21, Canonicalization).init(allocator); + defer canon_map.deinit(); + + var composite_set = std.AutoArrayHashMap(u21, [2]u21).init(allocator); - lines: while (in_reader.takeDelimiterInclusive('\n')) |took| { - const line = std.mem.trimRight(u8, took, "\n"); + while (in_reader.takeDelimiterInclusive('\n')) |line| { if (line.len == 0) continue; var field_iter = std.mem.splitScalar(u8, line, ';'); - var cps: [3]u24 = undefined; - var len: u8 = 2; + var cp: u21 = undefined; var i: usize = 0; while (field_iter.next()) |field| : (i += 1) { + if (field.len == 0) continue; + switch (i) { - 0 => cps[0] = try std.fmt.parseInt(u24, field, 16), + 0 => cp = try std.fmt.parseInt(u21, field, 16), 5 => { // Not canonical. - if (field.len == 0 or field[0] == '<') continue :lines; + if (field[0] == '<') continue; + if (std.mem.indexOfScalar(u8, field, ' ')) |space| { // Canonical - len = 3; - cps[1] = try std.fmt.parseInt(u24, field[0..space], 16); - cps[2] = try std.fmt.parseInt(u24, field[space + 1 ..], 16); + const c0, const c1 = .{ + try std.fmt.parseInt(u21, field[0..space], 16), + try std.fmt.parseInt(u21, field[space + 1 ..], 16), + }; + try canon_map.put(cp, Canonicalization{ + .len = 2, + .cps = [_]u21{ c0, c1 }, + }); + try composite_set.put(cp, [_]u21{ c0, c1 }); } else { // Singleton - cps[1] = try std.fmt.parseInt(u24, field, 16); + try canon_map.put(cp, Canonicalization{ + .len = 1, + .cps = [_]u21{ + try std.fmt.parseInt(u21, field, 16), + 0, + }, + }); } }, - 2 => if (line[0] == '<') continue :lines, - else => {}, } } - - try writer.writeInt(u8, @intCast(len), endian); - for (cps[0..len]) |cp| try writer.writeInt(u24, cp, endian); } else |err| switch (err) { error.EndOfStream => {}, else => { return err; }, } - try writer.writeInt(u16, 0, endian); - try writer.flush(); + + // Build multi-tiered lookup tables for decompositions + var blocks_map = BlockMap.init(allocator); + defer blocks_map.deinit(); + + var stage1 = std.array_list.Managed(u16).init(allocator); + defer stage1.deinit(); + + var stage2 = std.array_list.Managed(Canonicalization).init(allocator); + defer stage2.deinit(); + + var block: Block = [_]Canonicalization{.{}} ** block_size; + var block_len: u16 = 0; + + for (0..0x110000) |i| { + const cp: u21 = @intCast(i); + + const canon: Canonicalization = canon_map.get(cp) orelse .{}; + + block[block_len] = canon; + block_len += 1; + + if (block_len < block_size and cp != 0x10ffff) continue; + + const gop = try blocks_map.getOrPut(block); + if (!gop.found_existing) { + gop.value_ptr.* = @intCast(stage2.items.len); + try stage2.appendSlice(&block); + } + + try stage1.append(gop.value_ptr.*); + block_len = 0; + } + + var write_buf: [4096]u8 = undefined; + var out_file = try std.fs.cwd().createFile(output_path, .{}); + defer out_file.close(); + var writer = out_file.writer(&write_buf); + + try writer.interface.print( + \\//! This file is auto-generated. Do not edit. + \\ + \\pub const Canonicalization = struct {{ + \\ len: u3, + \\ cps: [2]u21, + \\}}; + \\ + \\pub const s1: [{}]u16 = .{{ + , .{stage1.items.len}); + for (stage1.items) |entry| try writer.interface.print("{}, ", .{entry}); + + try writer.interface.print( + \\ + \\}}; + \\ + \\pub const s2: [{}]Canonicalization = .{{ + , .{stage2.items.len}); + for (stage2.items) |entry| { + try writer.interface.print(".{{ .len = {}, .cps = .{{ {}, {} }} }}, ", .{ + entry.len, + entry.cps[0], + entry.cps[1], + }); + } + + const composite = composite_set.keys(); + // TODO: cut + try writer.interface.print( + \\ + \\}}; + \\ + \\pub const composite: [{}]u21 = .{{ + , .{composite.len}); + for (composite) |entry| try writer.interface.print("{}, ", .{entry}); + + try writer.interface.writeAll( + \\}; + ); + + try writer.interface.print( + \\ + \\ pub const c_map: [{}]struct {{ [2]u21, u21 }} = .{{ + , .{composite.len}); + for (composite) |comp| { + const canon = canon_map.get(comp).?; + std.debug.assert(canon.len == 2); + try writer.interface.print( + \\ .{{ .{{{}, {}}}, {}}}, + , + .{ canon.cps[0], canon.cps[1], comp }, + ); + } + // var c_entries = composite_set.iterator(); + // while (c_entries.next()) |entry| { + // try writer.interface.print( + // \\ .{{ .{{{}, {}}}, {}}}, + // , + // .{ entry.value_ptr[0], entry.value_ptr[1], entry.key_ptr.* }, + // ); + // } + try writer.interface.writeAll( + \\}; + ); + + try writer.interface.flush(); } -- cgit v1.2.3