Replace CodePoint Decoding with Hörhmann Method

This still needs a small barrage of tests to confirm that it correctly
performs substitution of maximal subparts (Unicode 16.0.0 §3.9.6).

I'm pretty sure this edition is 'overly maximal' actually, the name of
the algorithm is somewhat misleading as to what it actually does.

1 files changed, 204 insertions, 59 deletions

diff --git a/src/code_point.zig b/src/code_point.zig
index e402554..d589413 100644
--- a/src/code_point.zig
+++ b/src/code_point.zig
@@ -1,3 +1,9 @@
+//! Unicode Code Point module
+//!
+//! Provides a decoder and iterator over a UTF-8 encoded string.
+//! Represents invalid data according to the Replacement of Maximal
+//! Subparts algorithm.
+
 /// `CodePoint` represents a Unicode code point by its code,
 /// length, and offset in the source bytes.
 pub const CodePoint = struct {
@@ -6,67 +12,144 @@ pub const CodePoint = struct {
     offset: u32,
 };
 
-/// given a small slice of a string, decode the corresponding codepoint
+/// This function is deprecated and will be removed in a later release.
+/// Use `decodeAtIndex` or `decodeAtCursor`.
 pub fn decode(bytes: []const u8, offset: u32) ?CodePoint {
-    // EOS fast path
-    if (bytes.len == 0) {
-        return null;
+    var off: u32 = 0;
+    var maybe_code = decodeAtCursor(bytes, &off);
+    if (maybe_code) |*code| {
+        code.offset = offset;
+        return code.*;
     }
+    return null;
+}
 
-    // ASCII fast path
-    if (bytes[0] < 128) {
-        return .{
-            .code = bytes[0],
-            .len = 1,
-            .offset = offset,
-        };
-    }
+/// Decode the CodePoint, if any, at `bytes[idx]`.
+pub fn decodeAtIndex(bytes: []const u8, idx: u32) ?CodePoint {
+    var off = idx;
+    return decodeAtCursor(bytes, &off);
+}
+
+/// Decode the CodePoint, if any, at `bytes[cursor.*]`.  After, the
+/// cursor will point at the next potential codepoint index.
+pub fn decodeAtCursor(bytes: []const u8, cursor: *u32) ?CodePoint {
+    // EOS
+    if (cursor.* >= bytes.len) return null;
 
-    var cp = CodePoint{
-        .code = undefined,
-        .len = switch (bytes[0]) {
-            0b1100_0000...0b1101_1111 => 2,
-            0b1110_0000...0b1110_1111 => 3,
-            0b1111_0000...0b1111_0111 => 4,
-            else => {
-                // unicode replacement code point.
-                return .{
-                    .code = 0xfffd,
-                    .len = 1,
-                    .offset = offset,
-                };
-            },
-        },
-        .offset = offset,
+    const this_off = cursor.*;
+    cursor.* += 1;
+
+    // ASCII
+    var byte = bytes[this_off];
+    if (byte < 0x80) return .{
+        .code = byte,
+        .offset = this_off,
+        .len = 1,
     };
+    // Multibyte
 
-    // Return replacement if we don' have a complete codepoint remaining. Consumes only one byte
-    if (cp.len > bytes.len) {
-        // Unicode replacement code point.
+    // Second:
+    var class: u4 = @intCast(u8dfa[byte]);
+    var st: u32 = state_dfa[class];
+    if (st == RUNE_REJECT or cursor.* == bytes.len) {
+        @branchHint(.cold);
+        // First one is never a truncation
         return .{
             .code = 0xfffd,
             .len = 1,
-            .offset = offset,
+            .offset = this_off,
         };
     }
-
-    const cp_bytes = bytes[0..cp.len];
-    cp.code = switch (cp.len) {
-        2 => (@as(u21, (cp_bytes[0] & 0b00011111)) << 6) | (cp_bytes[1] & 0b00111111),
-
-        3 => (((@as(u21, (cp_bytes[0] & 0b00001111)) << 6) |
-            (cp_bytes[1] & 0b00111111)) << 6) |
-            (cp_bytes[2] & 0b00111111),
-
-        4 => (((((@as(u21, (cp_bytes[0] & 0b00000111)) << 6) |
-            (cp_bytes[1] & 0b00111111)) << 6) |
-            (cp_bytes[2] & 0b00111111)) << 6) |
-            (cp_bytes[3] & 0b00111111),
-
-        else => @panic("CodePointIterator.next invalid code point length."),
+    var rune: u32 = byte & class_mask[class];
+    byte = bytes[cursor.*];
+    class = @intCast(u8dfa[byte]);
+    st = state_dfa[st + class];
+    rune = (byte & 0x3f) | (rune << 6);
+    cursor.* += 1;
+    if (st == RUNE_ACCEPT) {
+        return .{
+            .code = @intCast(rune),
+            .len = 2,
+            .offset = this_off,
+        };
+    }
+    if (st == RUNE_REJECT or cursor.* == bytes.len) {
+        @branchHint(.cold);
+        // Check for valid start at cursor:
+        if (state_dfa[@intCast(u8dfa[byte])] == RUNE_REJECT) {
+            return .{
+                .code = 0xfffd,
+                .len = 2,
+                .offset = this_off,
+            };
+        } else {
+            // Truncation.
+            cursor.* -= 1;
+            return .{
+                .code = 0xfffe,
+                .len = 1,
+                .offset = this_off,
+            };
+        }
+    }
+    // Third
+    byte = bytes[cursor.*];
+    class = @intCast(u8dfa[byte]);
+    st = state_dfa[st + class];
+    rune = (byte & 0x3f) | (rune << 6);
+    cursor.* += 1;
+    if (st == RUNE_ACCEPT) {
+        return .{
+            .code = @intCast(rune),
+            .len = 3,
+            .offset = this_off,
+        };
+    }
+    if (st == RUNE_REJECT or cursor.* == bytes.len) {
+        @branchHint(.cold);
+        if (state_dfa[@intCast(u8dfa[byte])] == RUNE_REJECT) {
+            return .{
+                .code = 0xfffd,
+                .len = 3,
+                .offset = this_off,
+            };
+        } else {
+            cursor.* -= 1;
+            return .{
+                .code = 0xfffd,
+                .len = 2,
+                .offset = this_off,
+            };
+        }
+    }
+    byte = bytes[cursor.*];
+    class = @intCast(u8dfa[byte]);
+    st = state_dfa[st + class];
+    rune = (byte & 0x3f) | (rune << 6);
+    cursor.* += 1;
+    if (st == RUNE_REJECT) {
+        @branchHint(.cold);
+        if (state_dfa[@intCast(u8dfa[byte])] == RUNE_REJECT) {
+            return .{
+                .code = 0xfffd,
+                .len = 4,
+                .offset = this_off,
+            };
+        } else {
+            cursor.* -= 1;
+            return .{
+                .code = 0xfffd,
+                .len = 3,
+                .offset = this_off,
+            };
+        }
+    }
+    assert(st == RUNE_ACCEPT);
+    return .{
+        .code = @intCast(rune),
+        .len = 4,
+        .offset = this_off,
     };
-
-    return cp;
 }
 
 /// `Iterator` iterates a string one `CodePoint` at-a-time.
@@ -75,14 +158,7 @@ pub const Iterator = struct {
     i: u32 = 0,
 
     pub fn next(self: *Iterator) ?CodePoint {
-        if (self.i >= self.bytes.len) return null;
-
-        const res = decode(self.bytes[self.i..], self.i);
-        if (res) |cp| {
-            self.i += cp.len;
-        }
-
-        return res;
+        return decodeAtCursor(self.bytes, &self.i);
     }
 
     pub fn peek(self: *Iterator) ?CodePoint {
@@ -92,6 +168,74 @@ pub const Iterator = struct {
     }
 };
 
+// A fast DFA decoder for UTF-8
+//
+// The algorithm used aims to be optimal, without involving SIMD, this
+// strikes a balance between portability and efficiency.  That is done
+// by using a DFA, represented as a few lookup tables, to track state,
+// encoding valid transitions between bytes, arriving at 0 each time a
+// codepoint is decoded.  In the process it builds up the value of the
+// codepoint in question.
+//
+// The virtue of such an approach is low branching factor, achieved at
+// a modest cost of storing the tables.  An embedded system might want
+// to use a more familiar decision graph based on switches, but modern
+// hosted environments can well afford the space, and may appreciate a
+// speed increase in exchange.
+//
+// Credit for the algorithm goes to Björn Höhrmann, who wrote it up at
+// https://bjoern.hoehrmann.de/utf-8/decoder/dfa/ .  The original
+// license may be found in the ./credits folder.
+//
+
+/// Successful codepoint parse
+const RUNE_ACCEPT = 0;
+
+/// Error state
+const RUNE_REJECT = 12;
+
+/// Byte transitions: value to class
+const u8dfa: [256]u8 = .{
+    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 00..1f
+    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 20..3f
+    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 40..5f
+    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 60..7f
+    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, // 80..9f
+    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // a0..bf
+    8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, // c0..df
+    0xa, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x4, 0x3, 0x3, // e0..ef
+    0xb, 0x6, 0x6, 0x6, 0x5, 0x8, 0x8, 0x8, 0x8, 0x8, 0x8, 0x8, 0x8, 0x8, 0x8, 0x8, // f0..ff
+};
+
+/// State transition: state + class = new state
+const state_dfa: [108]u8 = .{
+    0, 12, 24, 36, 60, 96, 84, 12, 12, 12, 48, 72, // 0  (RUNE_ACCEPT)
+    12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, // 12 (RUNE_REJECT)
+    12, 0, 12, 12, 12, 12, 12, 0, 12, 0, 12, 12, // 24
+    12, 24, 12, 12, 12, 12, 12, 24, 12, 24, 12, 12, // 32
+    12, 12, 12, 12, 12, 12, 12, 24, 12, 12, 12, 12, // 48
+    12, 24, 12, 12, 12, 12, 12, 12, 12, 24, 12, 12, // 60
+    12, 12, 12, 12, 12, 12, 12, 36, 12, 36, 12, 12, // 72
+    12, 36, 12, 12, 12, 12, 12, 36, 12, 36, 12, 12, // 84
+    12, 36, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, // 96
+};
+
+/// State masks
+const class_mask: [12]u8 = .{
+    0xff,
+    0,
+    0b0011_1111,
+    0b0001_1111,
+    0b0000_1111,
+    0b0000_0111,
+    0b0000_0011,
+    0,
+    0,
+    0,
+    0,
+    0,
+};
+
 test "decode" {
     const bytes = "🌩️";
     const res = decode(bytes, 0);
@@ -120,8 +264,8 @@ test "overlongs" {
     const bytes = "\xC0\xAF";
     const res = decode(bytes, 0);
     if (res) |cp| {
-        try testing.expectEqual(@as(u21, '/'), cp.code);
-        try testing.expectEqual(2, cp.len);
+        try testing.expectEqual(0xfffd, cp.code);
+        try testing.expectEqual(1, cp.len);
     } else {
         try testing.expect(false);
     }
@@ -129,3 +273,4 @@ test "overlongs" {
 
 const std = @import("std");
 const testing = std.testing;
+const assert = std.debug.assert;