AK: Replace UTF-8 string validation with a constexpr implementation

This will allow validating UTF-8 strings at compile time, such as from
String::from_utf8_short_string.

2 files changed, 91 insertions, 78 deletions

diff --git a/AK/Utf8View.cpp b/AK/Utf8View.cpp
index 27f44e0b26..bcc6171dfd 100644
--- a/AK/Utf8View.cpp
+++ b/AK/Utf8View.cpp
@@ -6,7 +6,6 @@
  */
 
 #include <AK/Assertions.h>
-#include <AK/CharacterTypes.h>
 #include <AK/Debug.h>
 #include <AK/Format.h>
 #include <AK/Utf8View.h>
@@ -71,68 +70,6 @@ Utf8View Utf8View::unicode_substring_view(size_t code_point_offset, size_t code_
     VERIFY_NOT_REACHED();
 }
 
-static inline bool decode_first_byte(
-    unsigned char byte,
-    size_t& out_code_point_length_in_bytes,
-    u32& out_value)
-{
-    if ((byte & 128) == 0) {
-        out_value = byte;
-        out_code_point_length_in_bytes = 1;
-        return true;
-    }
-    if ((byte & 64) == 0) {
-        return false;
-    }
-    if ((byte & 32) == 0) {
-        out_value = byte & 31;
-        out_code_point_length_in_bytes = 2;
-        return true;
-    }
-    if ((byte & 16) == 0) {
-        out_value = byte & 15;
-        out_code_point_length_in_bytes = 3;
-        return true;
-    }
-    if ((byte & 8) == 0) {
-        out_value = byte & 7;
-        out_code_point_length_in_bytes = 4;
-        return true;
-    }
-
-    return false;
-}
-
-bool Utf8View::validate(size_t& valid_bytes) const
-{
-    valid_bytes = 0;
-    for (auto ptr = begin_ptr(); ptr < end_ptr(); ptr++) {
-        size_t code_point_length_in_bytes = 0;
-        u32 code_point = 0;
-        bool first_byte_makes_sense = decode_first_byte(*ptr, code_point_length_in_bytes, code_point);
-        if (!first_byte_makes_sense)
-            return false;
-
-        for (size_t i = 1; i < code_point_length_in_bytes; i++) {
-            ptr++;
-            if (ptr >= end_ptr())
-                return false;
-            if (*ptr >> 6 != 2)
-                return false;
-
-            code_point <<= 6;
-            code_point |= *ptr & 63;
-        }
-
-        if (!is_unicode(code_point))
-            return false;
-
-        valid_bytes += code_point_length_in_bytes;
-    }
-
-    return true;
-}
-
 size_t Utf8View::calculate_length() const
 {
     size_t length = 0;
@@ -223,9 +160,7 @@ Utf8CodePointIterator& Utf8CodePointIterator::operator++()
 size_t Utf8CodePointIterator::underlying_code_point_length_in_bytes() const
 {
     VERIFY(m_length > 0);
-    size_t code_point_length_in_bytes = 0;
-    u32 value;
-    bool first_byte_makes_sense = decode_first_byte(*m_ptr, code_point_length_in_bytes, value);
+    auto [code_point_length_in_bytes, value, first_byte_makes_sense] = Utf8View::decode_leading_byte(*m_ptr);
 
     // If any of these tests fail, we will output a replacement character for this byte and treat it as a code point of size 1.
     if (!first_byte_makes_sense)
@@ -250,11 +185,7 @@ ReadonlyBytes Utf8CodePointIterator::underlying_code_point_bytes() const
 u32 Utf8CodePointIterator::operator*() const
 {
     VERIFY(m_length > 0);
-
-    u32 code_point_value_so_far = 0;
-    size_t code_point_length_in_bytes = 0;
-
-    bool first_byte_makes_sense = decode_first_byte(m_ptr[0], code_point_length_in_bytes, code_point_value_so_far);
+    auto [code_point_length_in_bytes, code_point_value_so_far, first_byte_makes_sense] = Utf8View::decode_leading_byte(*m_ptr);
 
     if (!first_byte_makes_sense) {
         // The first byte of the code point doesn't make sense: output a replacement character
diff --git a/AK/Utf8View.h b/AK/Utf8View.h
index e9f7e7635c..98a15bfc84 100644
--- a/AK/Utf8View.h
+++ b/AK/Utf8View.h
@@ -7,6 +7,7 @@
 
 #pragma once
 
+#include <AK/CharacterTypes.h>
 #include <AK/DeprecatedString.h>
 #include <AK/Format.h>
 #include <AK/StringView.h>
@@ -105,13 +106,6 @@ public:
         return byte_offset_of(it);
     }
 
-    bool validate(size_t& valid_bytes) const;
-    bool validate() const
-    {
-        size_t valid_bytes;
-        return validate(valid_bytes);
-    }
-
     size_t length() const
     {
         if (!m_have_length) {
@@ -121,11 +115,99 @@ public:
         return m_length;
     }
 
+    constexpr bool validate() const
+    {
+        size_t valid_bytes = 0;
+        return validate(valid_bytes);
+    }
+
+    constexpr bool validate(size_t& valid_bytes) const
+    {
+        valid_bytes = 0;
+
+        for (auto it = m_string.begin(); it != m_string.end(); ++it) {
+            auto [byte_length, code_point, is_valid] = decode_leading_byte(static_cast<u8>(*it));
+            if (!is_valid)
+                return false;
+
+            for (size_t i = 1; i < byte_length; ++i) {
+                if (++it == m_string.end())
+                    return false;
+
+                auto [code_point_bits, is_valid] = decode_continuation_byte(static_cast<u8>(*it));
+                if (!is_valid)
+                    return false;
+
+                code_point <<= 6;
+                code_point |= code_point_bits;
+            }
+
+            if (!is_unicode(code_point))
+                return false;
+
+            valid_bytes += byte_length;
+        }
+
+        return true;
+    }
+
 private:
+    friend class Utf8CodePointIterator;
+
     u8 const* begin_ptr() const { return (u8 const*)m_string.characters_without_null_termination(); }
     u8 const* end_ptr() const { return begin_ptr() + m_string.length(); }
     size_t calculate_length() const;
 
+    struct Utf8EncodedByteData {
+        size_t byte_length { 0 };
+        u8 encoding_bits { 0 };
+        u8 encoding_mask { 0 };
+    };
+
+    static constexpr Array<Utf8EncodedByteData, 4> utf8_encoded_byte_data { {
+        { 1, 0b0000'0000, 0b1000'0000 },
+        { 2, 0b1100'0000, 0b1110'0000 },
+        { 3, 0b1110'0000, 0b1111'0000 },
+        { 4, 0b1111'0000, 0b1111'1000 },
+    } };
+
+    struct LeadingByte {
+        size_t byte_length { 0 };
+        u32 code_point_bits { 0 };
+        bool is_valid { false };
+    };
+
+    static constexpr LeadingByte decode_leading_byte(u8 byte)
+    {
+        for (auto const& data : utf8_encoded_byte_data) {
+            if ((byte & data.encoding_mask) != data.encoding_bits)
+                continue;
+
+            byte &= ~data.encoding_mask;
+            return { data.byte_length, byte, true };
+        }
+
+        return { .is_valid = false };
+    }
+
+    struct ContinuationByte {
+        u32 code_point_bits { 0 };
+        bool is_valid { false };
+    };
+
+    static constexpr ContinuationByte decode_continuation_byte(u8 byte)
+    {
+        constexpr u8 continuation_byte_encoding_bits = 0b1000'0000;
+        constexpr u8 continuation_byte_encoding_mask = 0b1100'0000;
+
+        if ((byte & continuation_byte_encoding_mask) == continuation_byte_encoding_bits) {
+            byte &= ~continuation_byte_encoding_mask;
+            return { byte, true };
+        }
+
+        return { .is_valid = false };
+    }
+
     StringView m_string;
     mutable size_t m_length { 0 };
     mutable bool m_have_length { false };