// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie // SPDX-License-Identifier: MIT //! Turning a byte-to-code-point table round. //! //! A single-byte encoding decodes with an array lookup and could encode with //! a scan of the same array, which is 128 or 256 comparisons for every //! character. Sorting the entries by code point at compile time makes it a //! binary search instead, and costs nothing at run time: the sort happens //! while the program is being built. const std = @import("std"); const codec = @import("codec.zig"); const Entry = struct { code_point: u16, byte: u8 }; /// A table sorted by code point. `capacity` is the size of the table it came /// from; `len` is how much of it is real, since a table with holes in it /// yields fewer entries than it has positions. pub fn Reversed(comptime capacity: usize) type { return struct { entries: [capacity]Entry, len: usize, const Self = @This(); /// The byte that spells this code point, or null if the encoding has /// no way to write it. pub fn byte(self: *const Self, code_point: u21) ?u8 { if (code_point > std.math.maxInt(u16)) return null; const needle: u16 = @intCast(code_point); const entries = self.entries[0..self.len]; // The lower bound rather than any match, because a code point can // appear more than once -- CP875 decodes seven different bytes to // U+001A -- and the lowest byte is the one to write back. const found = std.sort.lowerBound(Entry, entries, needle, compare); if (found >= entries.len or entries[found].code_point != needle) return null; return entries[found].byte; } fn compare(needle: u16, entry: Entry) std.math.Order { return std.math.order(needle, entry.code_point); } }; } /// Sorts a decode table by code point, dropping the positions that map to /// nothing so that a search for U+FFFD -- which is what a hole holds -- cannot /// match one. `first_byte` is the byte that entry zero stands for: 0x80 for /// the single-byte encodings, which store only their upper half, and 0x00 for /// EBCDIC, which shares nothing with ASCII and stores all of it. pub fn reverse(comptime table: anytype, comptime first_byte: u8) Reversed(table.len) { @setEvalBranchQuota(100_000); var result: Reversed(table.len) = .{ .entries = undefined, .len = 0 }; for (table, 0..) |code_point, offset| { if (code_point == codec.unmapped) continue; result.entries[result.len] = .{ .code_point = code_point, .byte = @intCast(offset + first_byte), }; result.len += 1; } // By code point, ties broken by byte, so that the lowest byte for a // repeated code point comes first and `byte` finds it. const lessThan = struct { fn lessThan(_: void, a: Entry, b: Entry) bool { if (a.code_point != b.code_point) return a.code_point < b.code_point; return a.byte < b.byte; } }.lessThan; std.mem.sort(Entry, result.entries[0..result.len], {}, lessThan); return result; } test "a table with holes reverses to only its real entries" { const table = [_]u16{ 0x00e9, codec.unmapped, 0x00e8 }; const reversed = comptime reverse(table, 0x80); try std.testing.expectEqual(@as(usize, 2), reversed.len); try std.testing.expectEqual(@as(?u8, 0x80), reversed.byte(0x00e9)); try std.testing.expectEqual(@as(?u8, 0x82), reversed.byte(0x00e8)); try std.testing.expectEqual(@as(?u8, null), reversed.byte(0xffff)); try std.testing.expectEqual(@as(?u8, null), reversed.byte(0x0041)); } test "a repeated code point comes back as its lowest byte" { // Which is the shape CP875 has: several unassigned positions all spelled // U+001A, and one real SUBSTITUTE that it has to encode back to. const table = [_]u16{ 0x001a, 0x0041, 0x001a, 0x001a }; const reversed = comptime reverse(table, 0x00); try std.testing.expectEqual(@as(?u8, 0x00), reversed.byte(0x001a)); try std.testing.expectEqual(@as(?u8, 0x01), reversed.byte(0x0041)); }