CodepointWidthDetector.cpp

// Copyright (c) Microsoft Corporation.
// Licensed under the MIT license.

#include "precomp.h"
#include "inc/CodepointWidthDetector.hpp"

// I was trying to minimize dependencies in this code so that it's easier to port to other terminal applications.
// That's why it doesn't use any of the GSL helpers and makes minimal use of the STL.
#pragma warning(disable : 26446) // Prefer to use gsl::at() instead of unchecked subscript operator (bounds.4).
#pragma warning(disable : 26472) // Don't use a static_cast for arithmetic conversions. Use brace initialization, gsl::narrow_cast or gsl::narrow (type.1).

// On top of that, this code is optimized for processing input as fast as possible, so it's a little low-level.
#pragma warning(disable : 26438) // Avoid 'goto' (es.76).
#pragma warning(disable : 26481) // Don't use pointer arithmetic. Use span instead (bounds.1).
#pragma warning(disable : 26482) // Only index into arrays using constant expressions (bounds.2).

// s_stage1/2/3/4 represents a multi-stage table, aka trie.
// The highest bits of the codepoint are an index into s_stage1, which selects a row in s_stage2.
// The next couple bits of the codepoint then select the column in that row.
// This continues until the last stage which contains the final value.
//
// Fundamentally, the trie is generated by taking all 1114112 codepoints and their assigned values and deduplicating
// chunks of e.g. 16 values each. Each deduplicated chunk is assigned its offset in the list of all deduplicated chunks.
// This results in two lists: 1114112/16=7132 IDs and however many deduplicated chunks you have accumulated.
// This is often called a two-stage table.
//
// If you want to look up the value now, you'll first find the deduplicated chunk offset via `offsets[codepoint / 16]`.
// This gives you the location of your chunk. Now you just look up the value with `values[offset + (codepoint & 15)]`.
//
// Since the 7132 offsets take up a lot more space than the deduplicated values (at least in case of the Unicode database),
// this process can be repeated by compressing the offset array the exact same way the values got compressed and so on.

// s_joinRules represents the UAX #29 extended grapheme cluster rules, however slightly modified to fit our needs.
// Specifically, UAX #29 states:
// > Note: Testing two adjacent characters is insufficient for determining a boundary.
//
// I completely agree, but I really hate it. So this code trades off correctness for simplicity
// by using a simple lookup table anyway. Under most circumstances users won't notice,
// because as far as I can see this only behaves different for degenerate ("invalid") Unicode.
// It reduces our code complexity significantly and is way *way* faster.
//
// This is a great reference for the s_joinRules table:
//   https://www.unicode.org/Public/UCD/latest/ucd/auxiliary/GraphemeBreakTest.html

// Generated by GraphemeTableGen
// on 2024-12-04T15:47:45Z, from Unicode 16.0.0, 9224 bytes
// clang-format off
static constexpr uint16_t s_stage0[] = {
    0x0000, 0x0020, 0x0040, 0x0060, 0x0080, 0x009f, 0x00bf, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca,
    0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00d8, 0x00f8, 0x010a, 0x010e, 0x010b, 0x0108, 0x0113, 0x0133, 0x0153, 0x0153, 0x0153, 0x016f,
    0x018f, 0x01a7, 0x01c7, 0x01e7, 0x0133, 0x0133, 0x0205, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0221, 0x0236, 0x00ca, 0x00ca,
    0x0256, 0x0276, 0x0133, 0x0133, 0x0133, 0x028b, 0x02ab, 0x02b9, 0x0133, 0x02cc, 0x02ea, 0x0302, 0x0322, 0x033f, 0x035f, 0x037f,
    0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca,
    0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x039f,
    0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca,
    0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x00ca, 0x039f,
    0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133,
    0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133,
    0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133,
    0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133,
    0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133,
    0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133,
    0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133,
    0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133,
    0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133,
    0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133,
    0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133,
    0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133,
    0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133,
    0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133,
    0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133,
    0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133,
    0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133,
    0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133,
    0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133,
    0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133,
    0x03bf, 0x03c7, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133,
    0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133, 0x0133,
    0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153,
    0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x03e7,
    0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153,
    0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x0153, 0x03e7,
};
static constexpr uint16_t s_stage1[] = {
    0x0000, 0x0004, 0x000c, 0x0014, 0x001c, 0x0024, 0x002a, 0x0031, 0x002a, 0x0037, 0x002a, 0x003f, 0x0047, 0x0049, 0x004f, 0x0057, 0x005f, 0x0065, 0x006d, 0x002a, 0x002a, 0x002a, 0x0073, 0x007b, 0x0083, 0x008a, 0x002a, 0x0091, 0x0098, 0x009f, 0x00a3, 0x00aa,
    0x00b2, 0x00b8, 0x00be, 0x00c5, 0x00cd, 0x00d5, 0x00dd, 0x00e5, 0x00ed, 0x00f5, 0x00fd, 0x0105, 0x010d, 0x0115, 0x011d, 0x0125, 0x012d, 0x0135, 0x013d, 0x0145, 0x014d, 0x0155, 0x015d, 0x0164, 0x016b, 0x0173, 0x0175, 0x017d, 0x0182, 0x018a, 0x0192, 0x019a,
    0x019d, 0x01a5, 0x01ad, 0x002a, 0x01b5, 0x01b9, 0x01bd, 0x01c2, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x01ca, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x01d0, 0x01d7, 0x01de, 0x01e6,
    0x01ed, 0x002a, 0x01f5, 0x002a, 0x01fb, 0x002a, 0x002a, 0x002a, 0x0203, 0x0209, 0x0211, 0x0218, 0x0220, 0x0228, 0x0230, 0x0236, 0x023d, 0x002a, 0x002a, 0x0244, 0x002a, 0x002a, 0x002a, 0x0047, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a,
    0x024c, 0x0254, 0x025c, 0x0262, 0x026a, 0x0272, 0x027a, 0x0282, 0x028a, 0x0292, 0x029a, 0x002a, 0x02a2, 0x002a, 0x02a9, 0x02b0, 0x002a, 0x02b8, 0x02bc, 0x02c4, 0x002a, 0x002a, 0x02cc, 0x02d4, 0x02dc, 0x02e4, 0x02ec, 0x02f4, 0x02fc, 0x0304, 0x030c, 0x002a,
    0x002a, 0x002a, 0x002a, 0x0314, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x031c, 0x0322, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x0326, 0x002a, 0x032d, 0x002a, 0x0043, 0x002a, 0x002a, 0x0335, 0x0339, 0x0341, 0x0341, 0x0341, 0x0347, 0x034d,
    0x0355, 0x035b, 0x0341, 0x0363, 0x0341, 0x036a, 0x036e, 0x0374, 0x037b, 0x0381, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341,
    0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0388, 0x0390, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x0393, 0x039b, 0x017f, 0x002a, 0x002a, 0x002a, 0x002a, 0x03a3, 0x002a, 0x03ab, 0x03b3, 0x03bb, 0x03c3, 0x03cb, 0x03d3,
    0x03d8, 0x03e0, 0x03e8, 0x03f0, 0x002a, 0x002a, 0x002a, 0x03f7, 0x03ff, 0x0400, 0x0401, 0x0402, 0x0403, 0x0404, 0x0405, 0x03ff, 0x0400, 0x0401, 0x0402, 0x0403, 0x0404, 0x0405, 0x03ff, 0x0400, 0x0401, 0x0402, 0x0403, 0x0404, 0x0405, 0x03ff, 0x0400, 0x0401,
    0x0402, 0x0403, 0x0404, 0x0405, 0x03ff, 0x0400, 0x0401, 0x0402, 0x0403, 0x0404, 0x0405, 0x03ff, 0x0400, 0x0401, 0x0402, 0x0403, 0x0404, 0x040c, 0x0414, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a,
    0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc,
    0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x041c, 0x002a, 0x002a, 0x002a, 0x002a,
    0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x0424, 0x042a, 0x002a, 0x032d, 0x0355, 0x0432, 0x0437, 0x043b, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x0443, 0x002a, 0x002a, 0x002a, 0x044b, 0x002a, 0x0450, 0x002a, 0x002a, 0x002a,
    0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x0458, 0x002a, 0x002a, 0x01f1, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x0460, 0x0465, 0x002a, 0x002a, 0x002a,
    0x002a, 0x046b, 0x0471, 0x002a, 0x00a7, 0x0479, 0x002a, 0x0481, 0x0489, 0x0491, 0x0499, 0x04a1, 0x04a9, 0x04b1, 0x04b9, 0x04bc, 0x04c4, 0x002a, 0x04c9, 0x04d1, 0x04d9, 0x04e0, 0x04e8, 0x04ed, 0x04f5, 0x04f9, 0x0501, 0x002a, 0x002a, 0x0504, 0x050c, 0x0510,
    0x0518, 0x051b, 0x002a, 0x0522, 0x002a, 0x002a, 0x002a, 0x0528, 0x002a, 0x002a, 0x002a, 0x0530, 0x0538, 0x002a, 0x053e, 0x0546, 0x054e, 0x0556, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x055a, 0x002a, 0x0562, 0x002a, 0x0569, 0x0571, 0x0578, 0x002a, 0x002a,
    0x002a, 0x002a, 0x057b, 0x0583, 0x058b, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x0211, 0x0593, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a,
    0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x0598, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a,
    0x002a, 0x059e, 0x05a5, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x05ac, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x05b3, 0x05ba, 0x05be, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341,
    0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x05c6, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341,
    0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x05ce, 0x05d6, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a,
    0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x05d8, 0x0341, 0x0341, 0x0341, 0x0341, 0x05e0, 0x05e7, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x05ed, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a,
    0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x05f5, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a,
    0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x05fd, 0x0605, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x0609, 0x0611, 0x002a, 0x002a, 0x0619, 0x002a, 0x002a, 0x0341, 0x0621, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a,
    0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x0629, 0x0631, 0x0639, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a,
    0x002a, 0x002a, 0x0641, 0x002a, 0x0648, 0x002a, 0x05a5, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x064b, 0x0651, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x0651, 0x002a, 0x002a, 0x002a, 0x0657, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a,
    0x002a, 0x002a, 0x065d, 0x002a, 0x0665, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x002a, 0x066d,
    0x066e, 0x066e, 0x0675, 0x067d, 0x0683, 0x068b, 0x0691, 0x0699, 0x06a1, 0x066e, 0x066e, 0x06a9, 0x06b0, 0x06b8, 0x06bf, 0x06c7, 0x06cf, 0x06d0, 0x06d1, 0x06d9, 0x06e1, 0x06e9, 0x06ee, 0x06d0, 0x06f6, 0x06d0, 0x06fe, 0x002a, 0x0706, 0x002a, 0x070e, 0x0716,
    0x071d, 0x0724, 0x066e, 0x072c, 0x0734, 0x06d0, 0x06d0, 0x066e, 0x073c, 0x0744, 0x074c, 0x002a, 0x002a, 0x002a, 0x002a, 0x066e, 0x066e, 0x066e, 0x066e, 0x066e, 0x066e, 0x066e, 0x066e, 0x066e, 0x066e, 0x066e, 0x066e, 0x066e, 0x066e, 0x066e, 0x0754, 0x0341,
    0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0341, 0x0342, 0x075c,
    0x0047, 0x0764, 0x0764, 0x0047, 0x0047, 0x0047, 0x076c, 0x0764, 0x0764, 0x0764, 0x0764, 0x0764, 0x0764, 0x0764, 0x0764, 0x0764, 0x0764, 0x0764, 0x0764, 0x0764, 0x0764, 0x0764, 0x0764, 0x0764, 0x0764, 0x0764, 0x0764, 0x0764, 0x0764, 0x0764, 0x0764, 0x0764,
    0x0764, 0x0764, 0x0764, 0x0764, 0x0764, 0x0764, 0x0764, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc,
    0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x02bc, 0x0774,
};
static constexpr uint16_t s_stage2[] = {
    0x0000, 0x0000, 0x0000, 0x0000, 0x0008, 0x0008, 0x0008, 0x0008,
    0x0008, 0x0008, 0x0008, 0x0009, 0x0000, 0x0000, 0x0000, 0x0000,
    0x0011, 0x0018, 0x0020, 0x0022, 0x002a, 0x0008, 0x0029, 0x0030,
    0x0036, 0x003e, 0x0040, 0x0047, 0x004c, 0x0008, 0x004a, 0x002d,
    0x004e, 0x002d, 0x0053, 0x0029, 0x005b, 0x0063, 0x0034, 0x0008,
    0x004e, 0x002d, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008,
    0x0008, 0x0008, 0x002a, 0x006b, 0x0049, 0x0008, 0x0008, 0x0008,
    0x0008, 0x004c, 0x0008, 0x004c, 0x0008, 0x0008, 0x0008, 0x0072,
    0x005a, 0x0079, 0x0081, 0x0008, 0x0008, 0x0008, 0x0008, 0x0089,
    0x0089, 0x0089, 0x0089, 0x0089, 0x0089, 0x0089, 0x0089, 0x0008,
    0x0008, 0x0091, 0x0092, 0x0098, 0x0028, 0x0091, 0x0092, 0x0098,
    0x0028, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x004c,
    0x0008, 0x0092, 0x0092, 0x0092, 0x0092, 0x0092, 0x0092, 0x004c,
    0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x00a0, 0x00a6, 0x0008,
    0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x00ad, 0x0089, 0x0089,
    0x0089, 0x0089, 0x00af, 0x00b5, 0x0008, 0x0008, 0x0008, 0x0008,
    0x0008, 0x0008, 0x0008, 0x00bd, 0x0008, 0x0089, 0x00c5, 0x0008,
    0x0008, 0x0008, 0x0008, 0x00a0, 0x0089, 0x0089, 0x0008, 0x0008,
    0x00c9, 0x0008, 0x0008, 0x00a8, 0x00d1, 0x00d8, 0x00df, 0x0008,
    0x0008, 0x00e5, 0x00c8, 0x0008, 0x0008, 0x0008, 0x0089, 0x0089,
    0x00a5, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x00a8,
    0x0089, 0x00c9, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x00a0,
    0x00a4, 0x00ed, 0x0008, 0x0008, 0x00a8, 0x00f5, 0x00f9, 0x00a2,
    0x0008, 0x0008, 0x0008, 0x00fd, 0x0008, 0x0008, 0x0008, 0x0008,
    0x0105, 0x0089, 0x0008, 0x0008, 0x0008, 0x0008, 0x00ac, 0x0089,
    0x0089, 0x010c, 0x0089, 0x0089, 0x0089, 0x0111, 0x0008, 0x0115,
    0x011a, 0x011a, 0x011a, 0x011a, 0x0120, 0x0127, 0x012e, 0x00ad,
    0x011a, 0x0136, 0x0008, 0x0008, 0x011a, 0x013d, 0x0008, 0x0115,
    0x011a, 0x011a, 0x0145, 0x014c, 0x0152, 0x0159, 0x0160, 0x0166,
    0x016e, 0x0136, 0x0008, 0x0175, 0x0177, 0x017e, 0x0008, 0x0008,
    0x0008, 0x0008, 0x0008, 0x0008, 0x0182, 0x0189, 0x0190, 0x00c8,
    0x0008, 0x0008, 0x0008, 0x0194, 0x0008, 0x017e, 0x0008, 0x0115,
    0x011a, 0x011a, 0x0145, 0x019c, 0x0152, 0x01a4, 0x01ab, 0x0008,
    0x0008, 0x0136, 0x0008, 0x0008, 0x01b2, 0x013d, 0x0008, 0x0115,
    0x011a, 0x011a, 0x0145, 0x019c, 0x01ba, 0x0159, 0x0160, 0x01c2,
    0x016e, 0x0136, 0x0008, 0x01ca, 0x0008, 0x01d0, 0x0008, 0x0008,
    0x0008, 0x0008, 0x0008, 0x0008, 0x01d3, 0x01db, 0x01e2, 0x0166,
    0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x01ea, 0x0008, 0x0115,
    0x011a, 0x011a, 0x0145, 0x011a, 0x01f2, 0x01f9, 0x0200, 0x0206,
    0x020e, 0x0136, 0x0008, 0x0008, 0x0008, 0x013d, 0x0008, 0x0008,
    0x0008, 0x0008, 0x0008, 0x0008, 0x0212, 0x021a, 0x0221, 0x0227,
    0x0008, 0x0136, 0x0008, 0x016a, 0x0008, 0x022f, 0x0008, 0x0115,
    0x011a, 0x011a, 0x011a, 0x011a, 0x0237, 0x023e, 0x0245, 0x0166,
    0x0008, 0x0136, 0x0008, 0x0008, 0x0008, 0x013d, 0x0008, 0x0008,
    0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x024c, 0x0253, 0x025b,
    0x0008, 0x0008, 0x0263, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008,
    0x0008, 0x026a, 0x00a5, 0x00ca, 0x008a, 0x0008, 0x0008, 0x0008,
    0x0008, 0x0008, 0x0008, 0x026a, 0x00a3, 0x0008, 0x008a, 0x0008,
    0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x00a6, 0x0008, 0x0008,
    0x0178, 0x024d, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008,
    0x00ad, 0x0128, 0x00b0, 0x00a9, 0x0089, 0x00ad, 0x0089, 0x0089,
    0x0089, 0x00a3, 0x0177, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008,
    0x0008, 0x0008, 0x00a9, 0x0271, 0x0279, 0x0008, 0x0008, 0x01d3,
    0x027e, 0x00c9, 0x0008, 0x00e0, 0x0008, 0x0286, 0x00ed, 0x0008,
    0x00ed, 0x0008, 0x0008, 0x0008, 0x0008, 0x028e, 0x028e, 0x028e,
    0x028e, 0x028e, 0x028e, 0x028e, 0x028e, 0x0296, 0x0296, 0x0296,
    0x0296, 0x0296, 0x029e, 0x029e, 0x029e, 0x029e, 0x029e, 0x029e,
    0x029e, 0x029e, 0x0008, 0x0008, 0x0008, 0x00a9, 0x0008, 0x0008,
    0x0008, 0x0008, 0x02a6, 0x0008, 0x0008, 0x0008, 0x02ac, 0x0008,
    0x0008, 0x0136, 0x0008, 0x0008, 0x0008, 0x0136, 0x0008, 0x0008,
    0x0008, 0x0008, 0x0008, 0x0008, 0x02b1, 0x0129, 0x02b9, 0x0127,
    0x00a4, 0x00ed, 0x0008, 0x0008, 0x0008, 0x0008, 0x00a0, 0x0008,
    0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0206, 0x0008, 0x0008,
    0x0008, 0x0008, 0x00c8, 0x0008, 0x0008, 0x0008, 0x0008, 0x02c1,
    0x02c8, 0x02d0, 0x02d7, 0x0008, 0x0008, 0x00ca, 0x02df, 0x0008,
    0x0008, 0x0008, 0x0008, 0x02e3, 0x008a, 0x02eb, 0x012a, 0x02f3,
    0x00d8, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0089,
    0x0089, 0x008a, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008,
    0x0110, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x02fb, 0x0301,
    0x01d9, 0x0008, 0x0008, 0x0008, 0x0008, 0x00a0, 0x00a4, 0x0008,
    0x0112, 0x0008, 0x0008, 0x0008, 0x0309, 0x0311, 0x0008, 0x0008,
    0x0008, 0x0008, 0x0317, 0x031f, 0x022f, 0x0008, 0x0008, 0x0008,
    0x0008, 0x0327, 0x032b, 0x030b, 0x0008, 0x0008, 0x0330, 0x0089,
    0x0271, 0x018b, 0x0338, 0x00a6, 0x0008, 0x0340, 0x0348, 0x034d,
    0x0022, 0x0355, 0x035d, 0x0363, 0x0008, 0x036a, 0x0008, 0x0008,
    0x0372, 0x0089, 0x002c, 0x007a, 0x0025, 0x0008, 0x0008, 0x0008,
    0x0008, 0x002c, 0x0008, 0x0008, 0x0089, 0x0089, 0x0089, 0x0089,
    0x00c9, 0x0008, 0x037a, 0x004c, 0x0073, 0x0008, 0x0381, 0x002d,
    0x0008, 0x036a, 0x0008, 0x0008, 0x0033, 0x0060, 0x0092, 0x0026,
    0x0092, 0x0028, 0x0008, 0x004c, 0x0389, 0x038f, 0x0008, 0x0396,
    0x0008, 0x0028, 0x0008, 0x0008, 0x039c, 0x0008, 0x007a, 0x0008,
    0x0008, 0x0008, 0x0040, 0x03a4, 0x039f, 0x03a9, 0x0068, 0x03ae,
    0x007d, 0x0032, 0x0008, 0x03b4, 0x002e, 0x0008, 0x03bc, 0x03ba,
    0x0008, 0x0008, 0x03ba, 0x0008, 0x002b, 0x004c, 0x002b, 0x0008,
    0x0008, 0x007a, 0x0008, 0x0008, 0x002e, 0x03c4, 0x0008, 0x03cc,
    0x0008, 0x0008, 0x03d4, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008,
    0x0008, 0x03d5, 0x0008, 0x0008, 0x0008, 0x03dd, 0x03e5, 0x03ed,
    0x0008, 0x0008, 0x0008, 0x0008, 0x0092, 0x0092, 0x0092, 0x0092,
    0x0092, 0x0092, 0x0092, 0x0092, 0x03f5, 0x0092, 0x0092, 0x0092,
    0x0092, 0x0098, 0x0092, 0x0092, 0x0008, 0x0008, 0x0008, 0x0008,
    0x0098, 0x03fb, 0x0401, 0x0032, 0x0407, 0x040e, 0x0028, 0x0008,
    0x0349, 0x007a, 0x0008, 0x0416, 0x041e, 0x0425, 0x042d, 0x0433,
    0x043a, 0x043a, 0x0442, 0x043a, 0x0437, 0x0442, 0x0446, 0x043a,
    0x044e, 0x0451, 0x043a, 0x043b, 0x0459, 0x045f, 0x0467, 0x046b,
    0x0469, 0x0473, 0x043a, 0x0477, 0x0478, 0x047e, 0x0480, 0x0485,
    0x0455, 0x0482, 0x048b, 0x0491, 0x0499, 0x0473, 0x04a1, 0x03cf,
    0x036a, 0x04a9, 0x0394, 0x002b, 0x04ad, 0x04b5, 0x04bc, 0x0008,
    0x04c4, 0x0008, 0x004e, 0x0092, 0x0008, 0x0008, 0x04cc, 0x0008,
    0x036a, 0x0008, 0x04a9, 0x04d4, 0x0008, 0x0008, 0x0008, 0x0008,
    0x0008, 0x0008, 0x0393, 0x0008, 0x04dc, 0x0008, 0x0008, 0x04e4,
    0x0008, 0x0008, 0x0008, 0x0008, 0x04e8, 0x0028, 0x0008, 0x0008,
    0x0008, 0x0008, 0x0008, 0x00ca, 0x00a6, 0x0008, 0x0008, 0x0008,
    0x0008, 0x0008, 0x0008, 0x0008, 0x00ca, 0x04f0, 0x04f0, 0x04f0,
    0x04f6, 0x04f0, 0x04f0, 0x04f0, 0x04f0, 0x04f0, 0x04f0, 0x04fa,
    0x0008, 0x04f0, 0x04f0, 0x04f0, 0x04f0, 0x04f0, 0x04f0, 0x04f0,
    0x04f0, 0x0502, 0x0008, 0x0008, 0x0008, 0x04f0, 0x04f0, 0x04f0,
    0x04f0, 0x04f0, 0x050a, 0x0512, 0x0515, 0x051c, 0x04f0, 0x04f0,
    0x04f0, 0x04f0, 0x04f0, 0x04f0, 0x04f0, 0x04f1, 0x0524, 0x04f0,
    0x04f0, 0x04f0, 0x04f0, 0x052c, 0x04f0, 0x04f0, 0x04f0, 0x04f0,
    0x04f0, 0x051c, 0x04f0, 0x04f1, 0x04f0, 0x04f0, 0x04f0, 0x04f0,
    0x04f0, 0x04f0, 0x0502, 0x0534, 0x04f0, 0x04f0, 0x04f0, 0x04f1,
    0x04f0, 0x04f0, 0x04f0, 0x04f0, 0x0092, 0x04f0, 0x04f0, 0x04f0,
    0x04f0, 0x04f0, 0x04f0, 0x0513, 0x053b, 0x04f0, 0x04f0, 0x04f0,
    0x04f0, 0x04f9, 0x04f0, 0x04f0, 0x04f0, 0x04f0, 0x04f0, 0x04f0,
    0x04f1, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008,
    0x00ca, 0x0330, 0x0543, 0x0008, 0x0008, 0x0008, 0x00a8, 0x0008,
    0x0008, 0x0008, 0x0008, 0x0549, 0x01cf, 0x0008, 0x0008, 0x0550,
    0x01ce, 0x0008, 0x0008, 0x0557, 0x0008, 0x0008, 0x0008, 0x0008,
    0x0008, 0x0327, 0x025b, 0x055f, 0x0008, 0x0008, 0x0008, 0x0089,
    0x0089, 0x00a6, 0x00ca, 0x0008, 0x0008, 0x0008, 0x0008, 0x00a8,
    0x0543, 0x0008, 0x0008, 0x00ca, 0x0089, 0x022f, 0x0008, 0x028e,
    0x028e, 0x028e, 0x0567, 0x0111, 0x0008, 0x0008, 0x0008, 0x0008,
    0x0008, 0x056c, 0x0572, 0x0579, 0x0008, 0x0008, 0x0008, 0x00ed,
    0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0580, 0x0587, 0x0008,
    0x01cf, 0x058e, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x01ce,
    0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0596, 0x01c1,
    0x00c8, 0x0008, 0x0008, 0x0008, 0x0008, 0x059e, 0x05a6, 0x0008,
    0x0008, 0x0008, 0x0008, 0x01d6, 0x05ae, 0x0008, 0x0008, 0x05b6,
    0x05b7, 0x05b7, 0x05bb, 0x05b7, 0x05b7, 0x05b7, 0x05b6, 0x05b7,
    0x05b7, 0x05bb, 0x05b7, 0x05b7, 0x05b7, 0x05b6, 0x05b7, 0x05b7,
    0x05c0, 0x0008, 0x0296, 0x0296, 0x05c8, 0x05cf, 0x029e, 0x029e,
    0x029e, 0x029e, 0x029e, 0x05d3, 0x0008, 0x0008, 0x0008, 0x0177,
    0x0008, 0x0008, 0x0008, 0x0008, 0x0089, 0x0089, 0x04f0, 0x0532,
    0x0089, 0x0089, 0x04f0, 0x04f0, 0x04f5, 0x04f0, 0x04f1, 0x04fa,
    0x0008, 0x0008, 0x04f0, 0x04f0, 0x04f0, 0x04f0, 0x0533, 0x0008,
    0x0008, 0x0008, 0x01d3, 0x0008, 0x0008, 0x0008, 0x0008, 0x04f1,
    0x0008, 0x0000, 0x05db, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008,
    0x0008, 0x0008, 0x00ed, 0x0008, 0x0008, 0x0008, 0x0008, 0x00c9,
    0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x00a8, 0x00a5,
    0x05e2, 0x00aa, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x02d8,
    0x0008, 0x0008, 0x0008, 0x0008, 0x00aa, 0x0008, 0x0008, 0x0008,
    0x0008, 0x0008, 0x00a2, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008,
    0x05e9, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008,
    0x00aa, 0x05ef, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008,
    0x0008, 0x05f7, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008,
    0x0089, 0x008a, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x05ff,
    0x00ca, 0x0112, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0607,
    0x060e, 0x01d0, 0x00e7, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008,
    0x0008, 0x00a5, 0x0008, 0x0008, 0x0008, 0x00ca, 0x026e, 0x00a3,
    0x0008, 0x0227, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x01cf,
    0x0008, 0x0112, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0604,
    0x0128, 0x0616, 0x061d, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008,
    0x0008, 0x0625, 0x062c, 0x0177, 0x00c8, 0x0008, 0x0008, 0x0008,
    0x0008, 0x0008, 0x0008, 0x0008, 0x00ca, 0x02f3, 0x00a5, 0x0008,
    0x0008, 0x022f, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008,
    0x0634, 0x063c, 0x0640, 0x0166, 0x0008, 0x0646, 0x00a3, 0x00a3,
    0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x02f3,
    0x064d, 0x0654, 0x065c, 0x0008, 0x0663, 0x0008, 0x0008, 0x0008,
    0x0008, 0x0008, 0x0008, 0x055a, 0x0089, 0x066b, 0x0008, 0x0008,
    0x0177, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x02f3,
    0x0673, 0x067a, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008,
    0x0008, 0x0166, 0x0158, 0x0682, 0x00c9, 0x0008, 0x0008, 0x0280,
    0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x02f3, 0x0689,
    0x00c9, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008,
    0x0691, 0x0581, 0x0008, 0x0008, 0x0008, 0x0318, 0x0699, 0x00a4,
    0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0625, 0x0089, 0x0224,
    0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x06a1, 0x06a8,
    0x06b0, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008,
    0x0606, 0x06b6, 0x06be, 0x0008, 0x0008, 0x0008, 0x00ad, 0x00a5,
    0x0008, 0x0008, 0x0008, 0x0008, 0x00a0, 0x06c6, 0x00ca, 0x0008,
    0x0580, 0x02d7, 0x0008, 0x0008, 0x0008, 0x0008, 0x06cd, 0x06d3,
    0x0128, 0x00a6, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0166,
    0x008a, 0x0581, 0x0008, 0x0008, 0x00ac, 0x0089, 0x0089, 0x06db,
    0x06e2, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x06e9,
    0x06f0, 0x06f7, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008,
    0x0008, 0x06ff, 0x0707, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008,
    0x0008, 0x070f, 0x0008, 0x0717, 0x0008, 0x0008, 0x0008, 0x0008,
    0x0008, 0x024f, 0x071f, 0x0727, 0x0008, 0x0008, 0x01d0, 0x0008,
    0x0008, 0x0008, 0x0008, 0x00a7, 0x0089, 0x0543, 0x0008, 0x0008,
    0x0008, 0x0008, 0x0008, 0x00a8, 0x0089, 0x02f1, 0x0008, 0x0008,
    0x0008, 0x0008, 0x0008, 0x0008, 0x00a3, 0x0008, 0x0008, 0x0008,
    0x0008, 0x0008, 0x0008, 0x008a, 0x0008, 0x0008, 0x0008, 0x0008,
    0x072c, 0x0733, 0x0008, 0x0008, 0x00ca, 0x025a, 0x025b, 0x025b,
    0x025b, 0x025b, 0x025b, 0x00ca, 0x00a5, 0x0008, 0x0008, 0x0008,
    0x0008, 0x0008, 0x073b, 0x0008, 0x0743, 0x0008, 0x04f0, 0x04f0,
    0x04f0, 0x04f0, 0x04f0, 0x04f0, 0x04f0, 0x0008, 0x04f0, 0x04f0,
    0x0502, 0x0008, 0x0008, 0x0008, 0x0008, 0x0534, 0x04f0, 0x0533,
    0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x04f4, 0x074b,
    0x04f0, 0x04f0, 0x04f0, 0x04f0, 0x0529, 0x0008, 0x0752, 0x0008,
    0x0008, 0x075a, 0x0008, 0x04fe, 0x0008, 0x04f0, 0x04f0, 0x04f0,
    0x04f0, 0x04f0, 0x04f0, 0x04f0, 0x04fa, 0x0008, 0x0008, 0x0008,
    0x0206, 0x00a4, 0x0008, 0x0008, 0x0008, 0x0089, 0x0089, 0x0089,
    0x0089, 0x0089, 0x0543, 0x0089, 0x0089, 0x008a, 0x0008, 0x0008,
    0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x01d4, 0x0602, 0x02f3,
    0x0089, 0x0762, 0x00a4, 0x0008, 0x0008, 0x0008, 0x05ef, 0x0008,
    0x0008, 0x0191, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008,
    0x0008, 0x04f0, 0x04f0, 0x04f1, 0x0008, 0x04f0, 0x04f0, 0x04f1,
    0x0008, 0x0089, 0x0089, 0x0089, 0x0089, 0x0089, 0x0089, 0x008a,
    0x00a0, 0x0089, 0x0089, 0x0089, 0x0089, 0x0089, 0x00a3, 0x00ed,
    0x0008, 0x01ce, 0x0008, 0x0008, 0x00a0, 0x00ad, 0x0089, 0x0008,
    0x0008, 0x008a, 0x0089, 0x0089, 0x0764, 0x00b3, 0x00a5, 0x0008,
    0x0008, 0x00ca, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008,
    0x0177, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x00aa, 0x0008,
    0x0008, 0x0008, 0x0008, 0x0008, 0x00a8, 0x0008, 0x0008, 0x008a,
    0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x00aa, 0x00a5, 0x0008,
    0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x076c, 0x043a, 0x043a,
    0x043a, 0x043a, 0x043a, 0x043a, 0x043a, 0x043a, 0x043b, 0x043a,
    0x043a, 0x043a, 0x043a, 0x043a, 0x043a, 0x0092, 0x0774, 0x0092,
    0x0092, 0x0092, 0x077c, 0x0092, 0x0092, 0x0092, 0x0092, 0x0092,
    0x0784, 0x078c, 0x078e, 0x0092, 0x0796, 0x079d, 0x07a2, 0x0092,
    0x07a5, 0x043a, 0x043a, 0x043a, 0x043a, 0x07aa, 0x07b0, 0x07b0,
    0x07b0, 0x07b8, 0x043a, 0x04f0, 0x07c0, 0x04f0, 0x0513, 0x07c6,
    0x07cb, 0x04f0, 0x07ce, 0x07d6, 0x043a, 0x0444, 0x043a, 0x043a,
    0x043a, 0x0442, 0x0442, 0x0442, 0x0442, 0x07d7, 0x043d, 0x07df,
    0x0442, 0x0442, 0x0442, 0x0442, 0x0442, 0x0442, 0x0442, 0x07e0,
    0x0442, 0x0442, 0x0446, 0x043a, 0x0442, 0x0442, 0x0442, 0x0442,
    0x07e6, 0x0446, 0x043a, 0x0442, 0x0442, 0x07ed, 0x07f5, 0x0442,
    0x0442, 0x0442, 0x0442, 0x0442, 0x0442, 0x0442, 0x0443, 0x07fd,
    0x0442, 0x0442, 0x0442, 0x0442, 0x0442, 0x0442, 0x0442, 0x0442,
    0x0800, 0x0442, 0x0442, 0x0442, 0x0442, 0x0442, 0x0442, 0x0442,
    0x0807, 0x0391, 0x080f, 0x0442, 0x0442, 0x0442, 0x043a, 0x043a,
    0x0468, 0x043a, 0x043a, 0x07d1, 0x043a, 0x076c, 0x043a, 0x043a,
    0x043a, 0x043a, 0x043a, 0x043a, 0x043a, 0x043f, 0x0442, 0x0442,
    0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0444, 0x076c,
    0x0802, 0x043e, 0x043a, 0x07d3, 0x043e, 0x0445, 0x0008, 0x0008,
    0x0008, 0x0008, 0x0008, 0x0008, 0x0817, 0x043a, 0x0008, 0x0008,
    0x04dc, 0x043a, 0x0442, 0x0446, 0x07d7, 0x043a, 0x0008, 0x0817,
    0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x0008, 0x043a, 0x0008,
    0x0819, 0x0008, 0x0008, 0x0008, 0x0008, 0x043a, 0x0008, 0x0008,
    0x0008, 0x0391, 0x043a, 0x043a, 0x0008, 0x0821, 0x0442, 0x0442,
    0x0442, 0x0442, 0x0442, 0x0826, 0x082a, 0x0442, 0x0442, 0x0442,
    0x0442, 0x0442, 0x0442, 0x0442, 0x043a, 0x043a, 0x043a, 0x043a,
    0x043a, 0x043a, 0x0442, 0x0445, 0x0442, 0x0475, 0x0442, 0x0442,
    0x0442, 0x0442, 0x0442, 0x0442, 0x0443, 0x043c, 0x0442, 0x0800,
    0x0442, 0x07d6, 0x0442, 0x07d7, 0x043a, 0x043a, 0x043a, 0x043a,
    0x043a, 0x043a, 0x043a, 0x0459, 0x0832, 0x0000, 0x0000, 0x0000,
    0x0089, 0x0089, 0x0089, 0x0089, 0x0000, 0x0000, 0x0000, 0x0000,
    0x0000, 0x0000, 0x0000, 0x0000, 0x0089, 0x0089, 0x0089, 0x0089,
    0x0089, 0x0089, 0x0000, 0x0000, 0x0092, 0x0092, 0x0092, 0x0092,
    0x0092, 0x0092, 0x0092, 0x083a,
};
static constexpr uint8_t s_stage3[] = {
    0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41,
    0x40, 0x40, 0x40, 0x40, 0x40, 0x40, 0x40, 0x40,
    0x41, 0x40, 0xc0, 0x40, 0x40, 0xc0, 0x40, 0x40,
    0xc0, 0x4c, 0xc0, 0x40, 0x40, 0x41, 0xcc, 0x40,
    0xc0, 0xc0, 0xc0, 0xc0, 0xc0, 0x40, 0xc0, 0xc0,
    0xc0, 0xc0, 0x40, 0x40, 0x40, 0x40, 0x40, 0x40,
    0xc0, 0x40, 0x40, 0x40, 0x40, 0x40, 0xc0, 0xc0,
    0x40, 0x40, 0x40, 0x40, 0xc0, 0x40, 0xc0, 0xc0,
    0xc0, 0x40, 0xc0, 0xc0, 0x40, 0x40, 0x40, 0xc0,
    0xc0, 0xc0, 0x40, 0xc0, 0x40, 0xc0, 0x40, 0x40,
    0x40, 0x40, 0x40, 0x40, 0xc0, 0xc0, 0xc0, 0x40,
    0x40, 0x40, 0x40, 0xc0, 0xc0, 0xc0, 0x40, 0xc0,
    0x40, 0x40, 0x40, 0xc0, 0xc0, 0xc0, 0xc0, 0x40,
    0xc0, 0x40, 0x40, 0xc0, 0x40, 0xc0, 0x40, 0xc0,
    0x40, 0xc0, 0x40, 0x40, 0x40, 0x40, 0xc0, 0x40,
    0x40, 0xc0, 0x40, 0x40, 0x40, 0x40, 0x40, 0x40,
    0x40, 0xc0, 0xc0, 0xc0, 0xc0, 0x40, 0xc0, 0x40,
    0xc0, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
    0x02, 0x40, 0xc0, 0xc0, 0xc0, 0xc0, 0xc0, 0xc0,
    0xc0, 0xc0, 0x40, 0xc0, 0xc0, 0xc0, 0xc0, 0xc0,
    0x40, 0x40, 0x40, 0x02, 0x02, 0x02, 0x02, 0x02,
    0x40, 0x40, 0x40, 0x40, 0x40, 0x40, 0x02, 0x02,
    0x02, 0x02, 0x02, 0x02, 0x02, 0x40, 0x02, 0x02,
    0x40, 0x02, 0x02, 0x40, 0x02, 0x04, 0x04, 0x04,
    0x04, 0x04, 0x04, 0x40, 0x40, 0x02, 0x02, 0x02,
    0x40, 0x02, 0x40, 0x40, 0x40, 0x40, 0x40, 0x40,
    0x40, 0x02, 0x02, 0x02, 0x02, 0x02, 0x04, 0x40,
    0x02, 0x02, 0x02, 0x02, 0x02, 0x40, 0x40, 0x02,
    0x40, 0x02, 0x02, 0x02, 0x02, 0x40, 0x40, 0x40,
    0x40, 0x40, 0x40, 0x40, 0x04, 0x40, 0x40, 0x40,
    0x40, 0x40, 0x02, 0x40, 0x40, 0x02, 0x02, 0x40,
    0x02, 0x02, 0x02, 0x02, 0x02, 0x40, 0x02, 0x02,
    0x02, 0x40, 0x40, 0x40, 0x40, 0x04, 0x04, 0x40,
    0x40, 0x40, 0x40, 0x40, 0x02, 0x02, 0x04, 0x02,
    0x02, 0x02, 0x02, 0x02, 0x42, 0x40, 0x40, 0x40,
    0x40, 0x40, 0x4b, 0x4b, 0x4b, 0x4b, 0x4b, 0x4b,
    0x4b, 0x4b, 0x02, 0x42, 0x02, 0x40, 0x42, 0x42,
    0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x42,
    0x42, 0x42, 0x42, 0x0a, 0x42, 0x42, 0x40, 0x40,
    0x02, 0x02, 0x40, 0x40, 0x40, 0x40, 0x02, 0x42,
    0x42, 0x40, 0x40, 0x40, 0x40, 0x4b, 0x40, 0x4b,
    0x4b, 0x4b, 0x4b, 0x4b, 0x4b, 0x40, 0x4b, 0x40,
    0x40, 0x40, 0x4b, 0x4b, 0x40, 0x40, 0x02, 0x40,
    0x42, 0x42, 0x02, 0x02, 0x02, 0x02, 0x40, 0x40,
    0x42, 0x40, 0x40, 0x42, 0x42, 0x0a, 0x40, 0x40,
    0x40, 0x40, 0x40, 0x40, 0x40, 0x42, 0x40, 0x40,
    0x40, 0x40, 0x4b, 0x4b, 0x40, 0x4b, 0x4b, 0x40,
    0x40, 0x40, 0x40, 0x40, 0x40, 0x02, 0x40, 0x02,
    0x02, 0x42, 0x40, 0x40, 0x40, 0x40, 0x02, 0x40,
    0x42, 0x42, 0x02, 0x02, 0x40, 0x40, 0x40, 0x40,
    0x02, 0x40, 0x40, 0x02, 0x02, 0x02, 0x40, 0x40,
    0x40, 0x02, 0x40, 0x40, 0x4b, 0x40, 0x4b, 0x4b,
    0x40, 0x4b, 0x4b, 0x4b, 0x42, 0x02, 0x02, 0x02,
    0x02, 0x02, 0x40, 0x02, 0x42, 0x40, 0x42, 0x42,
    0x0a, 0x40, 0x40, 0x4b, 0x02, 0x02, 0x02, 0x02,
    0x02, 0x02, 0x4b, 0x4b, 0x40, 0x40, 0x02, 0x40,
    0x42, 0x02, 0x40, 0x40, 0x40, 0x40, 0x40, 0x02,
    0x02, 0x42, 0x40, 0x4b, 0x40, 0x40, 0x40, 0x40,
    0x40, 0x40, 0x02, 0x40, 0x40, 0x40, 0x40, 0x40,
    0x40, 0x42, 0x42, 0x02, 0x42, 0x42, 0x40, 0x40,
    0x40, 0x42, 0x42, 0x40, 0x42, 0x42, 0x42, 0x02,
    0x40, 0x40, 0x02, 0x42, 0x42, 0x42, 0x02, 0x40,
    0x40, 0x40, 0x4b, 0x4b, 0x40, 0x40, 0x02, 0x40,
    0x02, 0x02, 0x42, 0x42, 0x42, 0x42, 0x40, 0x02,
    0x02, 0x40, 0x02, 0x02, 0x02, 0x0a, 0x40, 0x40,
    0x40, 0x40, 0x40, 0x02, 0x02, 0x40, 0x4b, 0x4b,
    0x4b, 0x40, 0x40, 0x40, 0x40, 0x40, 0x02, 0x40,
    0x42, 0x02, 0x42, 0x42, 0x42, 0x42, 0x42, 0x40,
    0x02, 0x42, 0x40, 0x42, 0x42, 0x02, 0x02, 0x40,
    0x40, 0x40, 0x40, 0x40, 0x42, 0x42, 0x40, 0x02,
    0x02, 0x42, 0x42, 0x40, 0x40, 0x40, 0x40, 0x4b,
    0x4b, 0x4b, 0x02, 0x02, 0x40, 0x42, 0x42, 0x02,
    0x02, 0x02, 0x02, 0x40, 0x42, 0x42, 0x40, 0x42,
    0x42, 0x42, 0x0a, 0x44, 0x40, 0x40, 0x02, 0x40,
    0x40, 0x40, 0x40, 0x42, 0x42, 0x02, 0x02, 0x02,
    0x40, 0x02, 0x40, 0x42, 0x42, 0x42, 0x42, 0x42,
    0x42, 0x42, 0x42, 0x40, 0x40, 0x42, 0x42, 0x40,
    0x40, 0x40, 0x40, 0x02, 0x40, 0x42, 0x02, 0x02,
    0x02, 0x02, 0x42, 0x02, 0x02, 0x02, 0x02, 0x02,
    0x02, 0x40, 0x02, 0x02, 0x42, 0x42, 0x02, 0x02,
    0x40, 0x40, 0x40, 0x40, 0x02, 0x02, 0x40, 0x40,
    0x02, 0x40, 0x42, 0x02, 0x02, 0x40, 0x85, 0x85,
    0x85, 0x85, 0x85, 0x85, 0x85, 0x85, 0x46, 0x46,
    0x46, 0x46, 0x46, 0x46, 0x46, 0x46, 0x47, 0x47,
    0x47, 0x47, 0x47, 0x47, 0x47, 0x47, 0x40, 0x40,
    0x02, 0x02, 0x02, 0x42, 0x40, 0x40, 0x02, 0x02,
    0x42, 0x40, 0x40, 0x40, 0x40, 0x02, 0x02, 0x42,
    0x02, 0x42, 0x42, 0x42, 0x42, 0x42, 0x42, 0x02,
    0x42, 0x02, 0x02, 0x02, 0x42, 0x42, 0x42, 0x42,
    0x02, 0x42, 0x42, 0x42, 0x40, 0x40, 0x40, 0x40,
    0x42, 0x42, 0x02, 0x42, 0x42, 0x42, 0x42, 0x42,
    0x02, 0x02, 0x02, 0x40, 0x40, 0x40, 0x40, 0x02,
    0x42, 0x42, 0x02, 0x40, 0x40, 0x40, 0x40, 0x40,
    0x42, 0x02, 0x42, 0x02, 0x40, 0x02, 0x40, 0x40,
    0x02, 0x02, 0x02, 0x42, 0x42, 0x42, 0x02, 0x02,
    0x02, 0x02, 0x02, 0x40, 0x40, 0x40, 0x40, 0x02,
    0x42, 0x02, 0x02, 0x02, 0x42, 0x02, 0x42, 0x42,
    0x42, 0x40, 0x42, 0x02, 0x02, 0x02, 0x02, 0x42,
    0x42, 0x02, 0x02, 0x42, 0x02, 0x02, 0x02, 0x40,
    0x40, 0x40, 0x40, 0x40, 0x40, 0x02, 0x42, 0x02,
    0x02, 0x42, 0x42, 0x42, 0x02, 0x42, 0x02, 0x40,
    0x40, 0x40, 0x40, 0x42, 0x42, 0x42, 0x42, 0x02,
    0x02, 0x02, 0x02, 0x40, 0x02, 0x02, 0x02, 0x02,
    0x40, 0x40, 0x40, 0x40, 0x02, 0x40, 0x40, 0x42,
    0x40, 0x40, 0x40, 0x02, 0x02, 0x0d, 0x02, 0x02,
    0xc0, 0x40, 0x40, 0xc0, 0xc0, 0xc0, 0xc0, 0x40,
    0x40, 0xc0, 0xc0, 0x40, 0x40, 0x41, 0x41, 0x02,
    0x02, 0x02, 0x02, 0x02, 0x40, 0xc0, 0x40, 0xc0,
    0xc0, 0x40, 0xc0, 0x40, 0x40, 0x40, 0xc0, 0x4c,
    0x40, 0xc0, 0x40, 0x4c, 0x40, 0x40, 0x40, 0x40,
    0x40, 0x40, 0x02, 0x02, 0x02, 0x02, 0x02, 0x41,
    0x02, 0x02, 0x40, 0x40, 0x40, 0xc0, 0x40, 0xc0,
    0x40, 0x40, 0xc0, 0xcc, 0x40, 0x40, 0x40, 0xc0,
    0x40, 0xc0, 0xc0, 0xc0, 0xc0, 0xcc, 0xcc, 0xcc,
    0xcc, 0x40, 0x40, 0x40, 0x40, 0x40, 0x40, 0x4c,
    0x4c, 0x40, 0x40, 0x40, 0x40, 0x40, 0xc0, 0x40,
    0xc0, 0x40, 0x40, 0x40, 0xc0, 0x40, 0x40, 0xc0,
    0x40, 0x40, 0x40, 0xc0, 0x40, 0x40, 0xc0, 0xc0,
    0xc0, 0xc0, 0xc0, 0x40, 0xc0, 0x40, 0x40, 0x40,
    0xc0, 0x40, 0x40, 0x40, 0xc0, 0xc0, 0x40, 0x40,
    0xc0, 0xc0, 0xc0, 0xc0, 0x40, 0x40, 0x8c, 0x8c,
    0x40, 0x40, 0x40, 0x40, 0x4c, 0x80, 0x80, 0x40,
    0x40, 0x40, 0x40, 0x40, 0x4c, 0x40, 0x40, 0x40,
    0x40, 0x40, 0x40, 0x40, 0x4c, 0x40, 0x8c, 0x8c,
    0x8c, 0x8c, 0x4c, 0x4c, 0x4c, 0x8c, 0x4c, 0x4c,
    0x8c, 0x40, 0x40, 0x40, 0x40, 0x4c, 0x4c, 0x4c,
    0x40, 0x40, 0x40, 0x40, 0x40, 0xc0, 0xc0, 0xcc,
    0xc0, 0xc0, 0xc0, 0xc0, 0xc0, 0x4c, 0x4c, 0x40,
    0x40, 0x40, 0x40, 0xc0, 0xc0, 0x40, 0x40, 0xcc,
    0xc0, 0x40, 0x40, 0x40, 0x40, 0xc0, 0xc0, 0x40,
    0x40, 0xc0, 0x40, 0x40, 0xc0, 0xc0, 0x40, 0x40,
    0x40, 0x4c, 0x4c, 0x8c, 0x8c, 0x40, 0x4c, 0x4c,
    0x4c, 0x4c, 0x4c, 0xcc, 0xc0, 0x4c, 0xcc, 0x4c,
    0x4c, 0x4c, 0x4c, 0xcc, 0xcc, 0x4c, 0x4c, 0x4c,
    0x40, 0x8c, 0x8c, 0x4c, 0x4c, 0x4c, 0x4c, 0xcc,
    0x4c, 0xcc, 0x4c, 0x4c, 0x4c, 0x4c, 0x4c, 0x4c,
    0x4c, 0x4c, 0x8c, 0x8c, 0x8c, 0x8c, 0x8c, 0x8c,
    0x8c, 0x8c, 0x4c, 0x4c, 0x4c, 0x4c, 0xcc, 0xcc,
    0x4c, 0xcc, 0xcc, 0xcc, 0x4c, 0xcc, 0xcc, 0x4c,
    0xcc, 0x4c, 0x4c, 0x4c, 0x4c, 0x4c, 0x4c, 0x40,
    0x40, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x4c,
    0x4c, 0x4c, 0x8c, 0x4c, 0x4c, 0x4c, 0x4c, 0x4c,
    0x4c, 0xcc, 0xcc, 0x4c, 0x4c, 0x8c, 0x8c, 0x4c,
    0x4c, 0x4c, 0x4c, 0x4c, 0x8c, 0x8c, 0xcc, 0xcc,
    0xcc, 0xcc, 0xcc, 0xcc, 0x8c, 0xcc, 0xcc, 0xcc,
    0xcc, 0xcc, 0xcc, 0xcc, 0xcc, 0x8c, 0x8c, 0xcc,
    0x8c, 0xcc, 0xcc, 0x8c, 0xcc, 0xcc, 0x8c, 0xcc,
    0xcc, 0x4c, 0x4c, 0x4c, 0x4c, 0x4c, 0x8c, 0x40,
    0x40, 0x4c, 0x4c, 0x4c, 0x40, 0x4c, 0x40, 0x4c,
    0x40, 0x8c, 0x40, 0x40, 0x40, 0x40, 0x40, 0x40,
    0x40, 0x4c, 0x40, 0x40, 0x4c, 0x40, 0x40, 0x40,
    0x40, 0x8c, 0x40, 0x8c, 0x40, 0x40, 0x40, 0x8c,
    0x8c, 0x8c, 0x40, 0x8c, 0x40, 0x40, 0x40, 0x4c,
    0x4c, 0x4c, 0x4c, 0x4c, 0x40, 0x40, 0x40, 0x40,
    0x40, 0x8c, 0x8c, 0x8c, 0x40, 0x40, 0x40, 0x40,
    0x40, 0x40, 0x40, 0x8c, 0x40, 0x40, 0x40, 0x40,
    0x40, 0x4c, 0x4c, 0x4c, 0x40, 0x40, 0x40, 0x8c,
    0x8c, 0x40, 0x40, 0x40, 0x40, 0x8c, 0xc0, 0xc0,
    0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
    0x40, 0x80, 0x80, 0x80, 0x80, 0x80, 0x40, 0x40,
    0x40, 0x40, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
    0x40, 0x40, 0x80, 0x80, 0x02, 0x02, 0x02, 0x02,
    0x82, 0x82, 0x8c, 0x80, 0x80, 0x80, 0x80, 0x80,
    0x80, 0x80, 0x8c, 0x80, 0x40, 0x80, 0x80, 0x80,
    0x80, 0x80, 0x80, 0x80, 0x40, 0x02, 0x02, 0x80,
    0x80, 0x80, 0x80, 0x80, 0x40, 0x40, 0x40, 0x40,
    0x40, 0x80, 0x80, 0x80, 0x40, 0x40, 0x40, 0x40,
    0x40, 0x40, 0x40, 0x80, 0x8c, 0x80, 0x80, 0x80,
    0x80, 0x80, 0x80, 0x02, 0x02, 0x02, 0x02, 0x02,
    0x02, 0x40, 0x40, 0x02, 0x40, 0x40, 0x40, 0x02,
    0x40, 0x40, 0x40, 0x42, 0x42, 0x02, 0x02, 0x42,
    0x42, 0x40, 0x40, 0x40, 0x40, 0x40, 0x40, 0x42,
    0x42, 0x42, 0x42, 0x02, 0x02, 0x40, 0x40, 0x85,
    0x85, 0x85, 0x85, 0x85, 0x40, 0x40, 0x40, 0x02,
    0x42, 0x42, 0x02, 0x02, 0x42, 0x42, 0x02, 0x02,
    0x42, 0x42, 0x40, 0x40, 0x40, 0x40, 0x40, 0x40,
    0x40, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x42,
    0x02, 0x02, 0x42, 0x42, 0x02, 0x02, 0x40, 0x40,
    0x40, 0x40, 0x02, 0x42, 0x40, 0x40, 0x02, 0x40,
    0x02, 0x02, 0x02, 0x40, 0x40, 0x02, 0x40, 0x40,
    0x40, 0x42, 0x02, 0x02, 0x42, 0x42, 0x40, 0x40,
    0x40, 0x40, 0x40, 0x42, 0x02, 0x40, 0x02, 0x42,
    0x42, 0x40, 0x42, 0x02, 0x40, 0x40, 0x88, 0x89,
    0x89, 0x89, 0x89, 0x89, 0x89, 0x89, 0x89, 0x88,
    0x89, 0x89, 0x89, 0x89, 0x40, 0x40, 0x40, 0x40,
    0x46, 0x46, 0x46, 0x46, 0x46, 0x46, 0x46, 0x40,
    0x40, 0x40, 0x47, 0x47, 0x47, 0x47, 0x47, 0x40,
    0x40, 0x40, 0x40, 0x41, 0x02, 0x02, 0x02, 0x40,
    0xc0, 0x40, 0x40, 0x02, 0x02, 0x02, 0x40, 0x02,
    0x02, 0x40, 0x40, 0x40, 0x02, 0x02, 0x40, 0x40,
    0x40, 0x02, 0x02, 0x02, 0x02, 0x40, 0x40, 0x42,
    0x02, 0x42, 0x40, 0x40, 0x40, 0x40, 0x40, 0x02,
    0x40, 0x40, 0x02, 0x02, 0x40, 0x40, 0x40, 0x42,
    0x42, 0x42, 0x02, 0x02, 0x02, 0x02, 0x42, 0x02,
    0x02, 0x40, 0x40, 0x04, 0x40, 0x40, 0x42, 0x40,
    0x44, 0x44, 0x40, 0x40, 0x40, 0x40, 0x02, 0x02,
    0x02, 0x02, 0x40, 0x42, 0x02, 0x40, 0x40, 0x40,
    0x40, 0x42, 0x42, 0x42, 0x02, 0x02, 0x42, 0x42,
    0x02, 0x42, 0x02, 0x02, 0x40, 0x40, 0x40, 0x02,
    0x02, 0x40, 0x42, 0x42, 0x02, 0x42, 0x42, 0x42,
    0x42, 0x40, 0x40, 0x42, 0x42, 0x42, 0x40, 0x40,
    0x42, 0x42, 0x40, 0x40, 0x02, 0x02, 0x40, 0x42,
    0x40, 0x40, 0x42, 0x40, 0x42, 0x42, 0x42, 0x40,
    0x42, 0x42, 0x02, 0x42, 0x02, 0x44, 0x02, 0x40,
    0x40, 0x40, 0x40, 0x40, 0x02, 0x02, 0x40, 0x40,
    0x40, 0x40, 0x40, 0x42, 0x42, 0x02, 0x02, 0x02,
    0x42, 0x02, 0x40, 0x02, 0x42, 0x02, 0x42, 0x42,
    0x42, 0x42, 0x02, 0x42, 0x02, 0x02, 0x40, 0x40,
    0x40, 0x40, 0x42, 0x42, 0x42, 0x42, 0x02, 0x02,
    0x42, 0x02, 0x02, 0x02, 0x42, 0x42, 0x02, 0x42,
    0x02, 0x40, 0x40, 0x40, 0x02, 0x42, 0x02, 0x42,
    0x42, 0x40, 0x40, 0x02, 0x02, 0x02, 0x02, 0x42,
    0x02, 0x42, 0x42, 0x42, 0x42, 0x42, 0x42, 0x40,
    0x42, 0x40, 0x40, 0x02, 0x02, 0x42, 0x02, 0x44,
    0x42, 0x44, 0x42, 0x02, 0x40, 0x40, 0x40, 0x40,
    0x02, 0x02, 0x42, 0x42, 0x42, 0x42, 0x02, 0x40,
    0x40, 0x40, 0x42, 0x40, 0x40, 0x40, 0x02, 0x42,
    0x44, 0x02, 0x02, 0x02, 0x02, 0x40, 0x40, 0x40,
    0x40, 0x44, 0x44, 0x44, 0x44, 0x02, 0x02, 0x02,
    0x02, 0x02, 0x02, 0x40, 0x42, 0x02, 0x02, 0x02,
    0x02, 0x02, 0x02, 0x42, 0x02, 0x02, 0x42, 0x02,
    0x02, 0x40, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
    0x40, 0x40, 0x02, 0x40, 0x02, 0x02, 0x40, 0x02,
    0x02, 0x02, 0x02, 0x02, 0x02, 0x44, 0x02, 0x40,
    0x40, 0x42, 0x42, 0x42, 0x42, 0x42, 0x40, 0x02,
    0x02, 0x40, 0x42, 0x42, 0x02, 0x42, 0x02, 0x40,
    0x40, 0x40, 0x02, 0x02, 0x42, 0x42, 0x40, 0x02,
    0x02, 0x44, 0x42, 0x40, 0x40, 0x40, 0x40, 0x02,
    0x02, 0x02, 0x40, 0x40, 0x40, 0x42, 0x42, 0x02,
    0x42, 0x02, 0x40, 0x40, 0x40, 0x40, 0x40, 0x46,
    0x40, 0x40, 0x40, 0x46, 0x46, 0x46, 0x40, 0x40,
    0x40, 0x40, 0x40, 0x80, 0x80, 0x80, 0x80, 0x02,
    0x40, 0x40, 0x40, 0x82, 0x82, 0x40, 0x40, 0x40,
    0x40, 0x40, 0x40, 0x80, 0x80, 0x80, 0x80, 0x40,
    0x80, 0x80, 0x40, 0x40, 0x80, 0x40, 0x40, 0x40,
    0x40, 0x40, 0x80, 0x80, 0x80, 0x40, 0x40, 0x80,
    0x40, 0x40, 0x02, 0x02, 0x02, 0x40, 0x40, 0x02,
    0x02, 0x02, 0x02, 0x02, 0x4c, 0x4c, 0x4c, 0x4c,
    0x8c, 0x4c, 0x4c, 0x4c, 0xc0, 0xc0, 0xc0, 0x40,
    0x40, 0x4c, 0x4c, 0x4c, 0xc0, 0xc0, 0xc0, 0xc0,
    0xc0, 0xc0, 0x40, 0x4c, 0xc0, 0xc0, 0x40, 0x40,
    0x4c, 0x4c, 0x4c, 0x4c, 0xcc, 0xcc, 0xc0, 0xc0,
    0xc0, 0xc0, 0xc0, 0xc0, 0xcc, 0xcc, 0xc0, 0xc0,
    0xc0, 0xc0, 0xc0, 0xc0, 0x8c, 0xc0, 0x8c, 0x8c,
    0x8c, 0x8c, 0x8c, 0x8c, 0x8c, 0xc0, 0xc0, 0xc0,
    0xc0, 0xc0, 0x4c, 0x4c, 0x4c, 0x4c, 0x4c, 0x4c,
    0x43, 0x43, 0x43, 0x43, 0x43, 0x43, 0x43, 0x43,
    0x80, 0x8c, 0x8c, 0x4c, 0x4c, 0x4c, 0x4c, 0x4c,
    0x80, 0x80, 0x8c, 0x80, 0x80, 0x80, 0x80, 0x80,
    0x8c, 0x8c, 0x8c, 0x8c, 0x8c, 0x8c, 0x80, 0x4c,
    0x4c, 0x4c, 0x4c, 0x4c, 0x4c, 0x4c, 0x8c, 0x8c,
    0x4c, 0x4c, 0x4c, 0x4c, 0x4c, 0x4c, 0x4c, 0x8c,
    0x8c, 0x8c, 0x8c, 0x8c, 0x8c, 0x4c, 0x8c, 0x8c,
    0x8c, 0x4c, 0x4c, 0x4c, 0x4c, 0x8c, 0x4c, 0x4c,
    0x4c, 0x8c, 0x4c, 0x4c, 0x4c, 0x8c, 0x8c, 0x8c,
    0x82, 0x82, 0x82, 0x82, 0x82, 0x8c, 0x4c, 0x8c,
    0x8c, 0x8c, 0x8c, 0x8c, 0x8c, 0x4c, 0x4c, 0x8c,
    0x8c, 0x8c, 0x8c, 0x8c, 0x8c, 0x40, 0x40, 0x4c,
    0x4c, 0x4c, 0x8c, 0x8c, 0x8c, 0x8c, 0x4c, 0x40,
    0x40, 0x40, 0x40, 0x4c, 0x4c, 0x4c, 0x4c, 0x4c,
    0x4c, 0x40, 0x40, 0x40, 0x40, 0x8c, 0x8c, 0x8c,
    0x8c, 0x40, 0x8c, 0x8c, 0x8c, 0x8c, 0x8c, 0x8c,
    0x40, 0x8c, 0x41, 0x02, 0x41, 0x41, 0x41, 0x41,
    0x41, 0x41, 0xc0, 0xc0, 0xc0, 0xc0, 0xc0, 0xc0,
    0x40, 0x40,
};
static constexpr uint32_t s_joinRules[2][16] = {
    {
        0b00000011110011111111111111001111,
        0b00001111111111111111111111111111,
        0b00000011110011111111111111001111,
        0b00000011110011111111111101001111,
        0b00000000000000000000000000001100,
        0b00000011110000001100001111001111,
        0b00000011110011110000111111001111,
        0b00000011110011110011111111001111,
        0b00000011110011110000111111001111,
        0b00000011110011110011111111001111,
        0b00000011000011111111111111001111,
        0b00000011110011111111111111001111,
        0b00000011110011111111111111001111,
        0b00000000110011111111111111001111,
        0b00000000000000000000000000000000,
        0b00000000000000000000000000000000,
    },
    {
        0b00000011110011111111111111001111,
        0b00001111111111111111111111111111,
        0b00000011110011111111111111001111,
        0b00000011110011111111111111001111,
        0b00000000000000000000000000001100,
        0b00000011110000001100001111001111,
        0b00000011110011110000111111001111,
        0b00000011110011110011111111001111,
        0b00000011110011110000111111001111,
        0b00000011110011110011111111001111,
        0b00000011000011111111111111001111,
        0b00000011110011111111111111001111,
        0b00000011110011111111111111001111,
        0b00000000110011111111111111001111,
        0b00000000000000000000000000000000,
        0b00000000000000000000000000000000,
    },
};
constexpr int ucdLookup(const char32_t cp) noexcept
{
    const auto s0 = s_stage0[cp >> 11];
    const auto s1 = s_stage1[s0 + ((cp >> 6) & 31)];
    const auto s2 = s_stage2[s1 + ((cp >> 3) & 7)];
    const auto s3 = s_stage3[s2 + ((cp >> 0) & 7)];
    return s3;
}
constexpr int ucdGraphemeJoins(const int state, const int lead, const int trail) noexcept
{
    const auto l = lead & 15;
    const auto t = trail & 15;
    return (s_joinRules[state][l] >> (t * 2)) & 3;
}
constexpr bool ucdGraphemeDone(const int state) noexcept
{
    return state == 3;
}
constexpr int ucdToCharacterWidth(const int val) noexcept
{
    return val >> 6;
}
// clang-format on

// Decodes the next codepoint from the given UTF-16 string.
// Returns the start of the next codepoint. Assumes `it < end`.
[[msvc::forceinline]] constexpr const wchar_t* utf16NextOrFFFD(const wchar_t* it, const wchar_t* end, char32_t& out)
{
    __assume(it != nullptr);
    __assume(end != nullptr);

    char32_t c = *it++;

    // Is any surrogate?
    if ((c & 0xF800) == 0xD800)
    {
        const char32_t c1 = c;
        c = 0xfffd;

        // Is leading surrogate and not at end?
        if ((c1 & 0x400) == 0 && it != end)
        {
            const char32_t c2 = *it;
            // Is also trailing surrogate!
            if ((c2 & 0xFC00) == 0xDC00)
            {
                c = (c1 << 10) - 0x35FDC00 + c2;
                ++it;
            }
        }
    }

    out = c;
    return it;
}

// Decodes the preceding codepoint from the given UTF-16 string.
// Returns the start of the preceding codepoint. Assumes `it > beg`.
[[msvc::forceinline]] constexpr const wchar_t* utf16PrevOrFFFD(const wchar_t* it, const wchar_t* beg, char32_t& out)
{
    __assume(it != nullptr);
    __assume(beg != nullptr);

    char32_t c = *--it;

    // Is any surrogate?
    if ((c & 0xF800) == 0xD800)
    {
        const char32_t c2 = c;
        c = 0xfffd;

        // Is trailing surrogate and not at begin?
        if ((c2 & 0x400) != 0 && it != beg)
        {
            const char32_t c1 = it[-1];
            // Is also leading surrogate!
            if ((c1 & 0xFC00) == 0xD800)
            {
                c = (c1 << 10) - 0x35FDC00 + c2;
                --it;
            }
        }
    }

    out = c;
    return it;
}

// Returns `reset` if `ptr` is outside the range [beg, end). Otherwise, it returns `ptr` unmodified.
constexpr const wchar_t* resetIfOutOfRange(const wchar_t* beg, const wchar_t* end, const wchar_t* reset, const wchar_t* ptr)
{
    auto ret = ptr;
    // This uses individual if-assignments to get the compiler to emit conditional moves.
    if (ptr < beg)
    {
        ret = reset;
    }
    if (ptr > end)
    {
        ret = reset;
    }
    return ret;
}

static CodepointWidthDetector s_codepointWidthDetector;

CodepointWidthDetector& CodepointWidthDetector::Singleton() noexcept
{
    return s_codepointWidthDetector;
}

bool CodepointWidthDetector::GraphemeNext(GraphemeState& s, const std::wstring_view& str) noexcept
{
    if (_mode == TextMeasurementMode::Graphemes)
    {
        return _graphemeNext(s, str);
    }
    if (_mode == TextMeasurementMode::Wcswidth)
    {
        return _graphemeNextWcswidth(s, str);
    }
    return _graphemeNextConsole(s, str);
}

bool CodepointWidthDetector::GraphemePrev(GraphemeState& s, const std::wstring_view& str) noexcept
{
    if (_mode == TextMeasurementMode::Graphemes)
    {
        return _graphemePrev(s, str);
    }
    if (_mode == TextMeasurementMode::Wcswidth)
    {
        return _graphemePrevWcswidth(s, str);
    }
    return _graphemePrevConsole(s, str);
}

// Parses the next grapheme cluster from the given string. The algorithm largely follows "UAX #29: Unicode Text Segmentation",
// but takes some mild liberties. Returns false if the end of the string was reached. Updates `s` with the cluster.
bool CodepointWidthDetector::_graphemeNext(GraphemeState& s, const std::wstring_view& str) const noexcept
{
    const auto beg = str.data();
    const auto end = beg + str.size();
    auto clusterBeg = s.beg + s.len;
    auto width = s.width;
    auto state = s._state;
    auto lead = s._last;

    // If it's a new string argument, we'll restart at the new string's beginning.
    clusterBeg = resetIfOutOfRange(beg, end, beg, clusterBeg);

    auto clusterEnd = clusterBeg;

    // Skip if we're already at the end.
    if (clusterEnd < end)
    {
        char32_t cp;

        // If a previous parsing of a grapheme cluster got interrupted because we reached the end of the string,
        // we'll have stored the parser state in `s._state` so that we can continue parsing within the new string.
        // The problem is that a `state` of zero is also a valid state parameter for `ucdGraphemeJoins`.
        // Thus, we're storing `s._state` bit-flipped so that we can differentiate between it being unset (0) and
        // storing a previous state of 0 (0xffff...).
        const auto gotState = state != 0;
        state = ~state;
        if (gotState)
        {
            goto fetchNext;
        }

        clusterEnd = utf16NextOrFFFD(clusterEnd, end, cp);
        lead = ucdLookup(cp);
        width = 0;
        state = 0;

        for (;;)
        {
            {
                auto w = ucdToCharacterWidth(lead);
                if (w == 3)
                {
                    w = _ambiguousWidth;
                }

                // U+FE0F Variation Selector-16 is used to turn unqualified Emojis into qualified ones.
                // By convention, this turns them from being ambiguous width (= narrow) into wide ones.
                // We achieve this here by explicitly giving this codepoint a wide width.
                // Later down below we'll clamp width back to <= 2.
                if (cp == 0xFE0F)
                {
                    w = 2;
                }

                width += w;
            }

            // If we're at the end of the string, we'll break out of the loop, but leave
            // `state` and `lead` as-is, so that we can continue parsing in the next string.
            if (clusterEnd >= end)
            {
                break;
            }

        fetchNext:
            const auto clusterEndNext = utf16NextOrFFFD(clusterEnd, end, cp);
            const auto trail = ucdLookup(cp);

            state = ucdGraphemeJoins(state, lead, trail);
            if (ucdGraphemeDone(state))
            {
                // We'll later do `state = ~state` which will result in `state == 0`.
                state = ~0;
                lead = 0;
                break;
            }

            clusterEnd = clusterEndNext;
            lead = trail;
        }

        state = ~state;
        width = width > 2 ? 2 : width;

        s.beg = clusterBeg;
        s.len = static_cast<int>(clusterEnd - clusterBeg);
        s.width = width;
        s._state = state;
        s._last = lead;
    }

    return clusterEnd < end;
}

// Parses the preceding grapheme cluster from the given string. The algorithm largely follows "UAX #29: Unicode Text Segmentation",
// but takes some mild liberties. Returns false if the end of the string was reached. Updates `s` with the cluster.
// This code is identical to _graphemeNext() but with the order of operations reversed since we're iterating backwards.
bool CodepointWidthDetector::_graphemePrev(GraphemeState& s, const std::wstring_view& str) const noexcept
{
    const auto beg = str.data();
    const auto end = beg + str.size();
    auto clusterEnd = s.beg;
    auto width = s.width;
    auto state = s._state;
    auto trail = s._last;

    // If it's a new string argument, we'll restart at the new string's beginning.
    clusterEnd = resetIfOutOfRange(beg, end, end, clusterEnd);

    auto clusterBeg = clusterEnd;

    // Skip if we're already at the end.
    if (clusterEnd > beg)
    {
        char32_t cp;

        // If a previous parsing of a grapheme cluster got interrupted because we reached the end of the string,
        // we'll have stored the parser state in `s._state` so that we can continue parsing within the new string.
        // The problem is that a `state` of zero is also a valid state parameter for `ucdGraphemeJoins`.
        // Thus, we're storing `s._state` bit-flipped so that we can differentiate between it being unset (0) and
        // storing a previous state of 0 (0xffff...).
        const auto gotState = state != 0;
        state = ~state;
        if (gotState)
        {
            goto fetchNext;
        }

        clusterBeg = utf16PrevOrFFFD(clusterBeg, beg, cp);
        trail = ucdLookup(cp);
        width = 0;
        state = 0;

        for (;;)
        {
            {
                auto w = ucdToCharacterWidth(trail);
                if (w == 3)
                {
                    w = _ambiguousWidth;
                }

                // U+FE0F Variation Selector-16 is used to turn unqualified Emojis into qualified ones.
                // By convention, this turns them from being ambiguous width (= narrow) into wide ones.
                // We achieve this here by explicitly giving this codepoint a wide width.
                // Later down below we'll clamp width back to <= 2.
                if (cp == 0xFE0F)
                {
                    w = 2;
                }

                width += w;
            }

            // If we're at the end of the string, we'll break out of the loop, but leave
            // `state` and `lead` as-is, so that we can continue parsing in the next string.
            if (clusterBeg <= beg)
            {
                break;
            }

        fetchNext:
            const auto clusterBegNext = utf16PrevOrFFFD(clusterBeg, beg, cp);
            const auto lead = ucdLookup(cp);

            state = ucdGraphemeJoins(state, lead, trail);
            if (ucdGraphemeDone(state))
            {
                // We'll later do `state = ~state` which will result in `state == 0`.
                state = ~0;
                trail = 0;
                break;
            }

            clusterBeg = clusterBegNext;
            trail = lead;
        }

        state = ~state;
        width = width > 2 ? 2 : width;

        s.beg = clusterBeg;
        s.len = static_cast<int>(clusterEnd - clusterBeg);
        s.width = width;
        s._state = state;
        s._last = trail;
    }

    return clusterBeg > beg;
}

// Implements a clustering algorithm that behaves similar to terminals and applications based on `wcswidth`.
// Such terminals have no actual notion of graphemes or joining characters, but do know zero-width characters.
// During cursor navigation they'll skip over such zero-width characters to reach the target column.
// In effect this means, that a non-zero-width character gets clustered with any number of following zero-width characters.
bool CodepointWidthDetector::_graphemeNextWcswidth(GraphemeState& s, const std::wstring_view& str) const noexcept
{
    const auto beg = str.data();
    const auto end = beg + str.size();
    auto clusterBeg = s.beg + s.len;
    auto width = s.width;
    auto state = s._state;

    // If it's a new string argument, we'll restart at the new string's beginning.
    clusterBeg = resetIfOutOfRange(beg, end, beg, clusterBeg);

    if (clusterBeg >= end)
    {
        return false;
    }

    auto clusterEnd = clusterBeg;

    // Normally we could just append any zero-width characters to the current cluster,
    // but theoretically we could have a zero-width character itself as the lead character.
    // Because of that we don't use `s.width` to track the state but rather flag
    // whether we've encountered our "lead" character in `s._state` (1 if we had one).
    if (state == 0)
    {
        width = 0;
    }

    for (;;)
    {
        char32_t cp;
        const auto clusterEndNext = utf16NextOrFFFD(clusterEnd, end, cp);
        const auto val = ucdLookup(cp);

        auto w = ucdToCharacterWidth(val);
        if (w == 3)
        {
            w = _ambiguousWidth;
        }

        if (state != 0 && w != 0)
        {
            state = 0;
            break;
        }

        width += w;
        state = 1;
        clusterEnd = clusterEndNext;

        if (clusterEnd >= end)
        {
            break;
        }
    }

    s.beg = clusterBeg;
    s.len = static_cast<int>(clusterEnd - clusterBeg);
    s.width = width;
    s._state = state;
    return clusterEnd < end;
}

// Implements a clustering algorithm that behaves similar to terminals and applications based on `wcswidth`.
// Such terminals have no actual notion of graphemes or joining characters, but do know zero-width characters.
// During cursor navigation they'll skip over such zero-width characters to reach the target column.
// In effect this means, that a non-zero-width character gets clustered with any number of following zero-width characters.
bool CodepointWidthDetector::_graphemePrevWcswidth(GraphemeState& s, const std::wstring_view& str) const noexcept
{
    const auto beg = str.data();
    const auto end = beg + str.size();
    auto clusterEnd = s.beg;

    // If it's a new string argument, we'll restart at the new string's beginning.
    clusterEnd = resetIfOutOfRange(beg, end, end, clusterEnd);

    if (clusterEnd <= beg)
    {
        return false;
    }

    auto clusterBeg = clusterEnd;
    auto width = s.width;
    int delayedCompletion = 0;

    // In order to conform to the behavior of _graphemePrev(), we need to pretend as if we don't know
    // whether the cluster is complete yet (with graphemes there may be prepended concatenation marks).
    // As such, we flag `delayedCompletion` to true which gets stored as `s._state = 1` and return false.
    // Then, when we get called again with the next input string, we'll finally return false with a `s.len` of 0.
    if (s._state == 0)
    {
        width = 0;

        for (;;)
        {
            char32_t cp;
            clusterBeg = utf16PrevOrFFFD(clusterBeg, beg, cp);
            const auto val = ucdLookup(cp);

            auto w = ucdToCharacterWidth(val);
            if (w == 3)
            {
                w = _ambiguousWidth;
            }

            width += w;

            const auto hasWidth = width != 0;
            const auto atEnd = clusterBeg <= beg;

            if (hasWidth || atEnd)
            {
                delayedCompletion = hasWidth && atEnd;
                break;
            }
        }
    }

    s.beg = clusterBeg;
    s.len = static_cast<int>(clusterEnd - clusterBeg);
    s.width = width;
    s._state = delayedCompletion;
    return clusterBeg > beg;
}

// Implements a clustering algorithm that behaves similar to the old conhost.
// It even asks the text renderer how wide ambiguous width characters are instead of defaulting to 1 (or 2).
bool CodepointWidthDetector::_graphemeNextConsole(GraphemeState& s, const std::wstring_view& str) noexcept
{
    const auto beg = str.data();
    const auto end = beg + str.size();
    auto clusterBeg = s.beg + s.len;

    // If it's a new string argument, we'll restart at the new string's beginning.
    clusterBeg = resetIfOutOfRange(beg, end, beg, clusterBeg);

    if (clusterBeg >= end)
    {
        return false;
    }

    auto clusterEnd = clusterBeg;
    auto width = s.width;
    int delayedCompletion = 0;

    // In order to conform to the behavior of _graphemeNext(), we need to pretend as if we don't know
    // whether the cluster is complete yet (with graphemes there may be combining marks, etc.).
    // As such, we flag `delayedCompletion` to true which gets stored as `s._state = 1` and return false.
    // Then, when we get called again with the next input string, we'll finally return false with a `s.len` of 0.
    if (s._state == 0)
    {
        char32_t cp;
        clusterEnd = utf16NextOrFFFD(clusterEnd, end, cp);

        const auto val = ucdLookup(cp);
        width = ucdToCharacterWidth(val);
        if (width == 3)
        {
            width = _checkFallbackViaCache(cp);
        }

        delayedCompletion = clusterEnd >= end;
    }

    s.beg = clusterBeg;
    s.len = static_cast<int>(clusterEnd - clusterBeg);
    s.width = width;
    s._state = delayedCompletion;
    return delayedCompletion == 0;
}

// Implements a clustering algorithm that behaves similar to the old conhost.
// It even asks the text renderer how wide ambiguous width characters are instead of defaulting to 1 (or 2).
bool CodepointWidthDetector::_graphemePrevConsole(GraphemeState& s, const std::wstring_view& str) noexcept
{
    const auto beg = str.data();
    const auto end = beg + str.size();
    auto clusterEnd = s.beg;

    // If it's a new string argument, we'll restart at the new string's beginning.
    clusterEnd = resetIfOutOfRange(beg, end, end, clusterEnd);

    if (clusterEnd <= beg)
    {
        return false;
    }

    auto clusterBeg = clusterEnd;
    auto width = s.width;
    int delayedCompletion = 0;

    // In order to conform to the behavior of _graphemePrev(), we need to pretend as if we don't know
    // whether the cluster is complete yet (with graphemes there may be prepended concatenation marks).
    // As such, we flag `delayedCompletion` to true which gets stored as `s._state = 1` and return false.
    // Then, when we get called again with the next input string, we'll finally return false with a `s.len` of 0.
    if (s._state == 0)
    {
        char32_t cp;
        clusterBeg = utf16PrevOrFFFD(clusterEnd, beg, cp);

        const auto val = ucdLookup(cp);
        width = ucdToCharacterWidth(val);
        if (width == 3)
        {
            width = _checkFallbackViaCache(cp);
        }

        delayedCompletion = clusterBeg <= beg;
    }

    s.beg = clusterBeg;
    s.len = static_cast<int>(clusterEnd - clusterBeg);
    s.width = width;
    s._state = delayedCompletion;
    return delayedCompletion == 0;
}

// Call the function specified via SetFallbackMethod() to turn ambiguous (width = 3) into narrow/wide.
// Caches the results in _fallbackCache.
int CodepointWidthDetector::_checkFallbackViaCache(const char32_t codepoint) noexcept
try
{
    // Ambiguous glyphs are considered narrow by default. See microsoft/terminal#2066 for more info.
    if (!_pfnFallbackMethod)
    {
        return 1;
    }

    if (const auto it = _fallbackCache.find(codepoint); it != _fallbackCache.end())
    {
        return it->second;
    }

    wchar_t buf[2];
    size_t len;
    if (codepoint <= 0xffff)
    {
        buf[0] = static_cast<wchar_t>(codepoint);
        len = 1;
    }
    else
    {
        buf[0] = static_cast<wchar_t>((codepoint >> 10) + 0xD7C0);
        buf[1] = static_cast<wchar_t>((codepoint & 0x3ff) | 0xDC00);
        len = 2;
    }

    const int width = _pfnFallbackMethod({ &buf[0], len }) ? 2 : 1;
    _fallbackCache.insert_or_assign(codepoint, width);
    return width;
}
catch (...)
{
    LOG_CAUGHT_EXCEPTION();
    return 1;
}

TextMeasurementMode CodepointWidthDetector::GetMode() const noexcept
{
    return _mode;
}

// Method Description:
// - Sets a function that should be used as the fallback mechanism for
//      determining a particular glyph's width, should the glyph be an ambiguous
//      width.
//   A Terminal could hook in a Renderer's IsGlyphWideByFont method as the
//      fallback to ask the renderer for the glyph's width (for example).
// Arguments:
// - pfnFallback - the function to use as the fallback method.
// Return Value:
// - <none>
void CodepointWidthDetector::SetFallbackMethod(std::function<bool(const std::wstring_view&)> pfnFallback) noexcept
{
    _pfnFallbackMethod = std::move(pfnFallback);
}

void CodepointWidthDetector::Reset(const TextMeasurementMode mode) noexcept
{
    _mode = mode;
    _fallbackCache.clear();
}