23070084244

Committed 13 Mar 2026 08:53PM UTC coverage: 81.296% (+0.08%) from 81.216%

Build # 23070084244

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #1791 from eynhaender/feature/replace-icu

[RFC] Replace ICU dependency with embedded Unicode tables

Coverage Stats

147 of 159 new or added lines in 1 file covered. (92.45%)

10992 of 13521 relevant lines covered (81.3%)

3505037.43 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

94.12

/src/unicode/normalization.cpp

/**
 * Copyright (c) 2011-2026 libbitcoin developers (see AUTHORS)
 *
 * This file is part of libbitcoin.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Affero General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Affero General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
#include <bitcoin/system/unicode/normalization.hpp>

#include <algorithm>
#include <bitcoin/system/data/data.hpp>
#include <bitcoin/system/math/math.hpp>
#include <bitcoin/system/unicode/ascii.hpp>
#include <bitcoin/system/unicode/code_points.hpp>
#include <bitcoin/system/unicode/conversion.hpp>
#include <bitcoin/system/unicode/unicode_tables.hpp>

namespace libbitcoin {
namespace system {

// Local helpers.
// ----------------------------------------------------------------------------

constexpr bool is_contained(char32_t value,
    const char32_interval& interval) NOEXCEPT
{
    return interval.first <= value && value <= interval.second;
}

constexpr char32_t unicode_max_code_point = 0x10ffffu;

// Hangul syllable constants (algorithmic decomposition/composition).
// unicode.org/reports/tr15/#Hangul
constexpr char32_t hangul_syllable_base  = 0xac00u;
constexpr char32_t hangul_leading_base   = 0x1100u;
constexpr char32_t hangul_vowel_base     = 0x1161u;
constexpr char32_t hangul_trailing_base  = 0x11a7u;
constexpr uint32_t hangul_leading_count  = 19;
constexpr uint32_t hangul_vowel_count    = 21;
constexpr uint32_t hangul_trailing_count = 28;
constexpr uint32_t hangul_nucleus_count  = hangul_vowel_count * hangul_trailing_count; // 588
constexpr uint32_t hangul_syllable_count = hangul_leading_count * hangul_nucleus_count; // 11172

// Unicode normalization helpers.
// ----------------------------------------------------------------------------

// Get canonical combining class (0 = starter).
static uint8_t get_ccc(char32_t point) NOEXCEPT
{
    if (point > unicode_max_code_point)
        return 0;
    // Two-level trie: level-1 selects the 128-entry block, level-2 resolves the entry.
    const auto data1 = unicode_data1[shift_right(point, 7)];
    const auto data2 = unicode_data2[shift_left(possible_wide_cast<size_t>(data1), 7)
        + bit_and(point, unmask_right<char32_t>(7))];
    return combining_index[data2];
}

// Decompose one code point into out (recursive, single-step per table entry).
static void decompose_one(std::u32string& out, char32_t point,
    bool compatible) NOEXCEPT
{
    // Hangul: algorithmic decomposition (same for NFD and NFKD).
    if (point >= hangul_syllable_base && point < hangul_syllable_base + hangul_syllable_count)
    {
        const auto syllable_index = possible_narrow_cast<uint32_t>(point - hangul_syllable_base);
        out.push_back(hangul_leading_base + syllable_index / hangul_nucleus_count);
        out.push_back(hangul_vowel_base + (syllable_index % hangul_nucleus_count) / hangul_trailing_count);
        const auto trailing_index = syllable_index % hangul_trailing_count;
        if (is_nonzero(trailing_index))
            out.push_back(hangul_trailing_base + trailing_index);
        return;
    }

    // Two-level trie lookup.
    if (point > unicode_max_code_point)
    {
        out.push_back(point);
        return;
    }
    // Two-level trie: level-1 selects the block, level-2 resolves the entry.
    const auto block = decomp_index1[shift_right(point, decomp_shift)];
    const auto index = decomp_index2[
        shift_left(possible_wide_cast<size_t>(block), decomp_shift)
        + bit_and(point, unmask_right<char32_t>(decomp_shift))];

    if (is_zero(index))
    {
        out.push_back(point);
        return;
    }

    const auto header        = decomp_pool[index];
    // Most significant bit flags a compatibility-only (NFKD) mapping.
    const auto is_compatible = get_left(header);
    // Bits 24-30: number of decomposition components (max 127).
    const auto count = bit_and(shift_right(header, 24), unmask_right<uint32_t>(7));

    // In NFD mode skip compatibility-only mappings.
    if (is_compatible && !compatible)
    {
        out.push_back(point);
        return;
    }

    // Recurse into each component.
    for (size_t component{}; component < count; ++component)
        decompose_one(out, possible_narrow_cast<char32_t>(decomp_pool[add1(index) + component]),
            compatible);
}

// Apply canonical ordering (UAX #15 section 3.11):
// Within each "combining sequence" (runs of CCC > 0), sort by CCC, stable.
static void canonical_order(std::u32string& sequence) NOEXCEPT
{
    const auto size = sequence.size();
    if (size < 2u)
        return;

    // Identify runs of combining characters and stable-sort each.
    size_t run_start{};
    while (run_start < size)
    {
        // Skip starters.
        while (run_start < size && is_zero(get_ccc(sequence[run_start])))
            ++run_start;

        // Find end of this combining run.
        size_t run_end = run_start;
        while (run_end < size && is_nonzero(get_ccc(sequence[run_end])))
            ++run_end;

        if (run_end > run_start + 1u)
        {
            std::stable_sort(sequence.begin() + run_start, sequence.begin() + run_end,
                [](char32_t a, char32_t b) NOEXCEPT
                {
                    return get_ccc(a) < get_ccc(b);
                });
        }
        run_start = run_end;
    }
}

// Canonical composition lookup (returns 0 if no composition found).
static char32_t comp_lookup(char32_t a, char32_t b) NOEXCEPT
{
    // Hangul L + V → LV
    if (a >= hangul_leading_base && a < hangul_leading_base + hangul_leading_count &&
        b >= hangul_vowel_base && b < hangul_vowel_base + hangul_vowel_count)
    {
        return hangul_syllable_base
            + (a - hangul_leading_base) * hangul_nucleus_count
            + (b - hangul_vowel_base) * hangul_trailing_count;
    }

    // Hangul LV + T → LVT
    if (a >= hangul_syllable_base && a < hangul_syllable_base + hangul_syllable_count &&
        is_zero((a - hangul_syllable_base) % hangul_trailing_count) &&
        b >  hangul_trailing_base  && b < hangul_trailing_base + hangul_trailing_count)
    {
        return a + (b - hangul_trailing_base);
    }

    // Binary search in comp_pairs (sorted by [a, b]).
    size_t lo{}, hi = comp_pairs_count;
    while (lo < hi)
    {
        const size_t mid  = (lo + hi) / 2u;
        const size_t base = mid * 3u;
        const auto   ca   = comp_pairs[base];
        const auto   cb   = comp_pairs[base + 1u];
        if (ca < a || (ca == a && cb < b))
            lo = mid + 1u;
        else if (ca > a || (ca == a && cb > b))
            hi = mid;
        else
            return possible_narrow_cast<char32_t>(comp_pairs[base + 2u]);
    }
    return 0u;
}

// Apply canonical composition pass (UAX #15 canonical composition algorithm).
static void compose(std::u32string& sequence) NOEXCEPT
{
    const size_t size = sequence.size();
    if (size < 2u)
        return;

    // We scan for each starter and try to compose with following combiners.
    size_t index{};
    while (index < sequence.size())
    {
        if (is_nonzero(get_ccc(sequence[index])))
        {
            ++index;
            continue;
        }

        // sequence[index] is a starter; scan forward for composable characters.
        uint8_t last_ccc{};
        size_t inner = add1(index);
        while (inner < sequence.size())
        {
            const uint8_t ccc = get_ccc(sequence[inner]);

            // A combining character is "blocked" if a character with equal or
            // higher CCC appeared between the starter and this character.
            const bool blocked = (last_ccc > 0u && last_ccc >= ccc);

            if (is_zero(ccc))
            {
                // sequence[inner] is also a starter. Try composition (e.g. Hangul L+V,
                // LV+T); if they compose, continue scanning; otherwise stop.
                if (!blocked)
                {
                    const char32_t c = comp_lookup(sequence[index], sequence[inner]);
                    if (is_nonzero(c))
                    {
                        sequence[index] = c;
                        sequence.erase(sequence.begin() + sign_cast<std::ptrdiff_t>(inner));
                        last_ccc = 0;
                        continue;
                    }
                }
                break; // Next starter that won't compose — stop.
            }

            if (!blocked)
            {
                const char32_t c = comp_lookup(sequence[index], sequence[inner]);
                if (is_nonzero(c))
                {
                    sequence[index] = c;
                    sequence.erase(sequence.begin() + sign_cast<std::ptrdiff_t>(inner));
                    last_ccc = 0; // Restart scan from just after new starter.
                    continue;
                }
            }

            last_ccc = ccc;
            ++inner;
        }
        ++index;
    }
}

// Full normalization (decompose → order → optionally compose).
static bool normal_form(std::string& value, bool compatible,
    bool recompose) NOEXCEPT
{
    const auto u32 = to_utf32(value);
    std::u32string out;
    out.reserve(u32.size() * 2u); // Most decompositions are small.

    for (const char32_t point : u32)
        decompose_one(out, point, compatible);

    canonical_order(out);

    if (recompose)
        compose(out);

    value = to_utf8(out);
    return true;
}

// Case folding helpers.
// ----------------------------------------------------------------------------

// Binary search in case_fold_pairs (sorted by from_cp).
// Returns folded code points written into out[], returns count (1-3).
static uint32_t fold_lower_one(char32_t point, char32_t out[3]) NOEXCEPT
{
    size_t lo{}, hi = case_fold_pairs_count;
    while (lo < hi)
    {
        const size_t mid  = (lo + hi) / 2u;
        const size_t base = mid * 5u;
        const auto   from = case_fold_pairs[base];
        if (from < possible_narrow_cast<uint32_t>(point))
            lo = mid + 1u;
        else if (from > possible_narrow_cast<uint32_t>(point))
            hi = mid;
        else
        {
            const uint32_t count = case_fold_pairs[base + 1u];
            out[0] = possible_narrow_cast<char32_t>(case_fold_pairs[base + 2u]);
            out[1] = possible_narrow_cast<char32_t>(case_fold_pairs[base + 3u]);
            out[2] = possible_narrow_cast<char32_t>(case_fold_pairs[base + 4u]);
            return count;
        }
    }
    out[0] = point;
    return 1u; // Identity (already lowercase or caseless).
}

static uint32_t fold_upper_one(char32_t point, char32_t out[3]) NOEXCEPT
{
    size_t lo{}, hi = upper_pairs_count;
    while (lo < hi)
    {
        const size_t mid  = (lo + hi) / 2u;
        const size_t base = mid * 5u;
        const auto   from = upper_pairs[base];
        if (from < possible_narrow_cast<uint32_t>(point))
            lo = mid + 1u;
        else if (from > possible_narrow_cast<uint32_t>(point))
            hi = mid;
        else
        {
            const uint32_t count = upper_pairs[base + 1u];
            out[0] = possible_narrow_cast<char32_t>(upper_pairs[base + 2u]);
            out[1] = possible_narrow_cast<char32_t>(upper_pairs[base + 3u]);
            out[2] = possible_narrow_cast<char32_t>(upper_pairs[base + 4u]);
            return count;
        }
    }
    out[0] = point;
    return 1u;
}

static bool apply_case(std::string& out, const std::string& in,
    bool lower) NOEXCEPT
{
    const auto u32 = to_utf32(in);
    std::u32string result;
    result.reserve(u32.size());

    char32_t buf[3]{};
    for (const char32_t point : u32)
    {
        const uint32_t count = lower ? fold_lower_one(point, buf)
                                     : fold_upper_one(point, buf);
        for (size_t index{}; index < count; ++index)
            result.push_back(buf[index]);
    }

    out = to_utf8(result);
    return true;
}

// Unicode case folding (embedded tables).
// ----------------------------------------------------------------------------

bool to_lower(std::string& value) NOEXCEPT
{
    if (is_ascii(value))
    {
        value = ascii_to_lower(value);
        return true;
    }

    return apply_case(value, value, true);
}

bool to_upper(std::string& value) NOEXCEPT
{
    if (is_ascii(value))
    {
        value = ascii_to_upper(value);
        return true;
    }

    return apply_case(value, value, false);
}

bool to_canonical_composition(std::string& value) NOEXCEPT
{
    return is_ascii(value) || normal_form(value, false, true);
}

bool to_canonical_decomposition(std::string& value) NOEXCEPT
{
    return is_ascii(value) || normal_form(value, false, false);
}

bool to_compatibility_composition(std::string& value) NOEXCEPT
{
    return is_ascii(value) || normal_form(value, true, true);
}

bool to_compatibility_decomposition(std::string& value) NOEXCEPT
{
    return is_ascii(value) || normal_form(value, true, false);
}

// No ICU dependency.
// ----------------------------------------------------------------------------

bool is_unicode(char32_t point) NOEXCEPT
{
    return point <= unicode_max_code_point;
}

bool is_separator(char32_t point) NOEXCEPT
{
    if (!is_unicode(point))
        return false;

    for (size_t index{}; index < char32_separators_count; ++index)
        if (point == char32_separators[index])
            return true;

    return false;
}

bool is_whitespace(char32_t point) NOEXCEPT
{
    if (!is_unicode(point))
        return false;

    for (size_t index{}; index < char32_whitespace_count; ++index)
        if (point == char32_whitespace[index])
            return true;

    return false;
}

bool is_combining(char32_t point) NOEXCEPT
{
    if (!is_unicode(point))
        return false;

    // github.com/python/cpython/blob/main/Modules/unicodedata.c
    // Two-level trie: level-1 selects the 128-entry block, level-2 resolves the entry.
    const auto data1 = unicode_data1[shift_right(point, 7)];
    const auto data2 = unicode_data2[shift_left(possible_wide_cast<size_t>(data1), 7)
        + bit_and(point, unmask_right<char32_t>(7))];
    return !is_zero(combining_index[data2]);
}

bool is_diacritic(char32_t point) NOEXCEPT
{
    if (!is_unicode(point))
        return false;

    for (size_t index{}; index < char32_diacritics_count; ++index)
        if (is_contained(point, char32_diacritics[index]))
            return true;

    return false;
}

bool is_chinese_japanese_or_korean(char32_t point) NOEXCEPT
{
    if (!is_unicode(point))
        return false;

    for (size_t index{}; index < char32_chinese_japanese_korean_count; ++index)
        if (is_contained(point, char32_chinese_japanese_korean[index]))
            return true;

    return false;
}

bool has_whitespace(const std::string& value) NOEXCEPT
{
    if (value.empty())
        return false;

    const auto points = to_utf32(value);
    return std::any_of(points.begin(), points.end(), [](char32_t character)
    {
        return is_whitespace(character);
    });
}

std::string to_non_combining_form(const std::string& value) NOEXCEPT
{
    if (value.empty())
        return value;

    // utf32 ensures each word is a single unicode character.
    auto points = to_utf32(value);
    std::erase_if(points, is_combining);
    return to_utf8(points);
}

std::string to_non_diacritic_form(const std::string& value) NOEXCEPT
{
    if (value.empty())
        return value;

    // utf32 ensures each word is a single unicode character.
    auto points = to_utf32(value);
    std::erase_if(points, is_diacritic);
    return to_utf8(points);
}

// Compress ascii whitespace and remove ascii spaces between cjk characters.
std::string to_compressed_form(const std::string& value) NOEXCEPT
{
    // Compress ascii whitespace to a single 0x20 between each utf32 token.
    const auto normalized = system::join(system::split(value));

    // utf32 ensures each word is a single unicode character.
    const auto points = to_utf32(normalized);

    // A character cannot be between two others if there aren't at least three.
    if (points.size() < 3u)
        return normalized;

    // Copy the first character to output.
    std::u32string compressed{ points.front() };

    // Remove a single ascii whitespace between CJK characters.
    // Front and back cannot be between two characters, so skip them.
    for (size_t point = 1; point < sub1(points.size()); point++)
    {
        if (!(is_ascii_whitespace(points[point]) &&
            is_chinese_japanese_or_korean(points[sub1(point)]) &&
            is_chinese_japanese_or_korean(points[add1(point)])))
        {
            compressed += points[point];
        }
    }

    // Copy the last character to output.
    compressed += points.back();
    return to_utf8(compressed);
}

} // namespace system
} // namespace libbitcoin

1	/**
2	* Copyright (c) 2011-2026 libbitcoin developers (see AUTHORS)
3	*
4	* This file is part of libbitcoin.
5	*
6	* This program is free software: you can redistribute it and/or modify
7	* it under the terms of the GNU Affero General Public License as published by
8	* the Free Software Foundation, either version 3 of the License, or
9	* (at your option) any later version.
10	*
11	* This program is distributed in the hope that it will be useful,
12	* but WITHOUT ANY WARRANTY; without even the implied warranty of
13	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14	* GNU Affero General Public License for more details.
15	*
16	* You should have received a copy of the GNU Affero General Public License
17	* along with this program. If not, see <http://www.gnu.org/licenses/>.
18	*/
19	#include <bitcoin/system/unicode/normalization.hpp>
20
21	#include <algorithm>
22	#include <bitcoin/system/data/data.hpp>
23	#include <bitcoin/system/math/math.hpp>
24	#include <bitcoin/system/unicode/ascii.hpp>
25	#include <bitcoin/system/unicode/code_points.hpp>
26	#include <bitcoin/system/unicode/conversion.hpp>
27	#include <bitcoin/system/unicode/unicode_tables.hpp>
28
29	namespace libbitcoin {
30	namespace system {
31
32	// Local helpers.
33	// ----------------------------------------------------------------------------
34
35	constexpr bool is_contained(char32_t value,	473,784,252✔
36	const char32_interval& interval) NOEXCEPT
37	{
38	return interval.first <= value && value <= interval.second;	473,784,252✔
39	}
40
41	constexpr char32_t unicode_max_code_point = 0x10ffffu;
42
43	// Hangul syllable constants (algorithmic decomposition/composition).
44	// unicode.org/reports/tr15/#Hangul
45	constexpr char32_t hangul_syllable_base = 0xac00u;
46	constexpr char32_t hangul_leading_base = 0x1100u;
47	constexpr char32_t hangul_vowel_base = 0x1161u;
48	constexpr char32_t hangul_trailing_base = 0x11a7u;
49	constexpr uint32_t hangul_leading_count = 19;
50	constexpr uint32_t hangul_vowel_count = 21;
51	constexpr uint32_t hangul_trailing_count = 28;
52	constexpr uint32_t hangul_nucleus_count = hangul_vowel_count * hangul_trailing_count; // 588
53	constexpr uint32_t hangul_syllable_count = hangul_leading_count * hangul_nucleus_count; // 11172
54
55	// Unicode normalization helpers.
56	// ----------------------------------------------------------------------------
57
58	// Get canonical combining class (0 = starter).
59	static uint8_t get_ccc(char32_t point) NOEXCEPT	45,287✔
60	{
61	if (point > unicode_max_code_point)	45,287✔
62	return 0;
63	// Two-level trie: level-1 selects the 128-entry block, level-2 resolves the entry.
64	const auto data1 = unicode_data1[shift_right(point, 7)];	45,287✔
65	const auto data2 = unicode_data2[shift_left(possible_wide_cast<size_t>(data1), 7)	45,287✔
66	+ bit_and(point, unmask_right<char32_t>(7))];	45,287✔
67	return combining_index[data2];	45,287✔
68	}
69
70	// Decompose one code point into out (recursive, single-step per table entry).
71	static void decompose_one(std::u32string& out, char32_t point,	41,306✔
72	bool compatible) NOEXCEPT
73	{
74	// Hangul: algorithmic decomposition (same for NFD and NFKD).
75	if (point >= hangul_syllable_base && point < hangul_syllable_base + hangul_syllable_count)	41,306✔
76	{
77	const auto syllable_index = possible_narrow_cast<uint32_t>(point - hangul_syllable_base);	5✔
78	out.push_back(hangul_leading_base + syllable_index / hangul_nucleus_count);	5✔
79	out.push_back(hangul_vowel_base + (syllable_index % hangul_nucleus_count) / hangul_trailing_count);	5✔
80	const auto trailing_index = syllable_index % hangul_trailing_count;	5✔
81	if (is_nonzero(trailing_index))	5✔
82	out.push_back(hangul_trailing_base + trailing_index);	2✔
83	return;	5✔
84	}
85
86	// Two-level trie lookup.
87	if (point > unicode_max_code_point)	41,301✔
88	{
NEW 89	out.push_back(point);	×
NEW 90	return;	×
91	}
92	// Two-level trie: level-1 selects the block, level-2 resolves the entry.
93	const auto block = decomp_index1[shift_right(point, decomp_shift)];	41,301✔
94	const auto index = decomp_index2[	41,301✔
95	shift_left(possible_wide_cast<size_t>(block), decomp_shift)
96	+ bit_and(point, unmask_right<char32_t>(decomp_shift))];	41,301✔
97
98	if (is_zero(index))	41,301✔
99	{
100	out.push_back(point);	39,076✔
101	return;	39,076✔
102	}
103
104	const auto header = decomp_pool[index];	2,225✔
105	// Most significant bit flags a compatibility-only (NFKD) mapping.
106	const auto is_compatible = get_left(header);	2,225✔
107	// Bits 24-30: number of decomposition components (max 127).
108	const auto count = bit_and(shift_right(header, 24), unmask_right<uint32_t>(7));	2,225✔
109
110	// In NFD mode skip compatibility-only mappings.
111	if (is_compatible && !compatible)	2,225✔
112	{
113	out.push_back(point);	2✔
114	return;	2✔
115	}
116
117	// Recurse into each component.
118	for (size_t component{}; component < count; ++component)	6,762✔
119	decompose_one(out, possible_narrow_cast<char32_t>(decomp_pool[add1(index) + component]),	4,539✔
120	compatible);
121	}
122
123	// Apply canonical ordering (UAX #15 section 3.11):
124	// Within each "combining sequence" (runs of CCC > 0), sort by CCC, stable.
125	static void canonical_order(std::u32string& sequence) NOEXCEPT	6,647✔
126	{
127	const auto size = sequence.size();	6,647✔
128	if (size < 2u)	6,647✔
129	return;
130
131	// Identify runs of combining characters and stable-sort each.
132	size_t run_start{};
133	while (run_start < size)	15,058✔
134	{
135	// Skip starters.
136	while (run_start < size && is_zero(get_ccc(sequence[run_start])))	43,859✔
137	++run_start;	34,740✔
138
139	// Find end of this combining run.
140	size_t run_end = run_start;	9,119✔
141	while (run_end < size && is_nonzero(get_ccc(sequence[run_end])))	12,761✔
142	++run_end;	3,642✔
143
144	if (run_end > run_start + 1u)	9,119✔
145	{
146	std::stable_sort(sequence.begin() + run_start, sequence.begin() + run_end,	27✔
147	[](char32_t a, char32_t b) NOEXCEPT	40✔
148	{
149	return get_ccc(a) < get_ccc(b);	40✔
150	});
151	}
152	run_start = run_end;
153	}
154	}
155
156	// Canonical composition lookup (returns 0 if no composition found).
157	static char32_t comp_lookup(char32_t a, char32_t b) NOEXCEPT	21✔
158	{
159	// Hangul L + V → LV
160	if (a >= hangul_leading_base && a < hangul_leading_base + hangul_leading_count &&	21✔
161	b >= hangul_vowel_base && b < hangul_vowel_base + hangul_vowel_count)	4✔
162	{
163	return hangul_syllable_base	4✔
164	+ (a - hangul_leading_base) * hangul_nucleus_count
165	+ (b - hangul_vowel_base) * hangul_trailing_count;	4✔
166	}
167
168	// Hangul LV + T → LVT
169	if (a >= hangul_syllable_base && a < hangul_syllable_base + hangul_syllable_count &&	20✔
170	is_zero((a - hangul_syllable_base) % hangul_trailing_count) &&	3✔
171	b > hangul_trailing_base && b < hangul_trailing_base + hangul_trailing_count)	20✔
172	{
173	return a + (b - hangul_trailing_base);	2✔
174	}
175
176	// Binary search in comp_pairs (sorted by [a, b]).
177	size_t lo{}, hi = comp_pairs_count;
178	while (lo < hi)	156✔
179	{
180	const size_t mid = (lo + hi) / 2u;	147✔
181	const size_t base = mid * 3u;	147✔
182	const auto ca = comp_pairs[base];	147✔
183	const auto cb = comp_pairs[base + 1u];	147✔
184	if (ca < a \|\| (ca == a && cb < b))	147✔
185	lo = mid + 1u;	62✔
186	else if (ca > a \|\| (ca == a && cb > b))	85✔
187	hi = mid;
188	else
189	return possible_narrow_cast<char32_t>(comp_pairs[base + 2u]);	6✔
190	}
191	return 0u;
192	}
193
194	// Apply canonical composition pass (UAX #15 canonical composition algorithm).
195	static void compose(std::u32string& sequence) NOEXCEPT	7✔
196	{
197	const size_t size = sequence.size();	7✔
198	if (size < 2u)	7✔
199	return;
200
201	// We scan for each starter and try to compose with following combiners.
202	size_t index{};
203	while (index < sequence.size())	23✔
204	{
205	if (is_nonzero(get_ccc(sequence[index])))	16✔
206	{
NEW 207	++index;	×
NEW 208	continue;	×
209	}
210
211	// sequence[index] is a starter; scan forward for composable characters.
212	uint8_t last_ccc{};	16✔
213	size_t inner = add1(index);	16✔
214	while (inner < sequence.size())	28✔
215	{
216	const uint8_t ccc = get_ccc(sequence[inner]);	21✔
217
218	// A combining character is "blocked" if a character with equal or
219	// higher CCC appeared between the starter and this character.
220	const bool blocked = (last_ccc > 0u && last_ccc >= ccc);	21✔
221
222	if (is_zero(ccc))	21✔
223	{
224	// sequence[inner] is also a starter. Try composition (e.g. Hangul L+V,
225	// LV+T); if they compose, continue scanning; otherwise stop.
226	if (!blocked)	15✔
227	{
228	const char32_t c = comp_lookup(sequence[index], sequence[inner]);	15✔
229	if (is_nonzero(c))	15✔
230	{
231	sequence[index] = c;	6✔
232	sequence.erase(sequence.begin() + sign_cast<std::ptrdiff_t>(inner));	6✔
233	last_ccc = 0;	6✔
234	continue;	6✔
235	}
236	}
237	break; // Next starter that won't compose — stop.
238	}
239
240	if (!blocked)	6✔
241	{
242	const char32_t c = comp_lookup(sequence[index], sequence[inner]);	6✔
243	if (is_nonzero(c))	6✔
244	{
245	sequence[index] = c;	6✔
246	sequence.erase(sequence.begin() + sign_cast<std::ptrdiff_t>(inner));	6✔
247	last_ccc = 0; // Restart scan from just after new starter.	6✔
248	continue;	6✔
249	}
250	}
251
NEW 252	last_ccc = ccc;	×
NEW 253	++inner;	×
254	}
255	++index;
256	}
257	}
258
259	// Full normalization (decompose → order → optionally compose).
260	static bool normal_form(std::string& value, bool compatible,	6,647✔
261	bool recompose) NOEXCEPT
262	{
263	const auto u32 = to_utf32(value);	6,647✔
264	std::u32string out;	6,647✔
265	out.reserve(u32.size() * 2u); // Most decompositions are small.	6,647✔
266
267	for (const char32_t point : u32)	43,414✔
268	decompose_one(out, point, compatible);	36,767✔
269
270	canonical_order(out);	6,647✔
271
272	if (recompose)	6,647✔
273	compose(out);	7✔
274
275	value = to_utf8(out);	6,647✔
276	return true;	6,647✔
277	}
278
279	// Case folding helpers.
280	// ----------------------------------------------------------------------------
281
282	// Binary search in case_fold_pairs (sorted by from_cp).
283	// Returns folded code points written into out[], returns count (1-3).
284	static uint32_t fold_lower_one(char32_t point, char32_t out[3]) NOEXCEPT	37,771✔
285	{
286	size_t lo{}, hi = case_fold_pairs_count;	37,771✔
287	while (lo < hi)	418,678✔
288	{
289	const size_t mid = (lo + hi) / 2u;	380,917✔
290	const size_t base = mid * 5u;	380,917✔
291	const auto from = case_fold_pairs[base];	380,917✔
292	if (from < possible_narrow_cast<uint32_t>(point))	380,917✔
293	lo = mid + 1u;	216,935✔
294	else if (from > possible_narrow_cast<uint32_t>(point))	163,982✔
295	hi = mid;
296	else
297	{
298	const uint32_t count = case_fold_pairs[base + 1u];	10✔
299	out[0] = possible_narrow_cast<char32_t>(case_fold_pairs[base + 2u]);	10✔
300	out[1] = possible_narrow_cast<char32_t>(case_fold_pairs[base + 3u]);	10✔
301	out[2] = possible_narrow_cast<char32_t>(case_fold_pairs[base + 4u]);	10✔
302	return count;	10✔
303	}
304	}
305	out[0] = point;	37,761✔
306	return 1u; // Identity (already lowercase or caseless).	37,761✔
307	}
308
309	static uint32_t fold_upper_one(char32_t point, char32_t out[3]) NOEXCEPT	1✔
310	{
311	size_t lo{}, hi = upper_pairs_count;	1✔
312	while (lo < hi)	12✔
313	{
314	const size_t mid = (lo + hi) / 2u;	11✔
315	const size_t base = mid * 5u;	11✔
316	const auto from = upper_pairs[base];	11✔
317	if (from < possible_narrow_cast<uint32_t>(point))	11✔
318	lo = mid + 1u;	4✔
319	else if (from > possible_narrow_cast<uint32_t>(point))	7✔
320	hi = mid;
321	else
322	{
NEW 323	const uint32_t count = upper_pairs[base + 1u];	×
NEW 324	out[0] = possible_narrow_cast<char32_t>(upper_pairs[base + 2u]);	×
NEW 325	out[1] = possible_narrow_cast<char32_t>(upper_pairs[base + 3u]);	×
NEW 326	out[2] = possible_narrow_cast<char32_t>(upper_pairs[base + 4u]);	×
NEW 327	return count;	×
328	}
329	}
330	out[0] = point;	1✔
331	return 1u;	1✔
332	}
333
334	static bool apply_case(std::string& out, const std::string& in,	6,583✔
335	bool lower) NOEXCEPT
336	{
337	const auto u32 = to_utf32(in);	6,583✔
338	std::u32string result;	6,583✔
339	result.reserve(u32.size());	6,583✔
340
341	char32_t buf[3]{};	6,583✔
342	for (const char32_t point : u32)	44,355✔
343	{
344	const uint32_t count = lower ? fold_lower_one(point, buf)	37,772✔
345	: fold_upper_one(point, buf);	1✔
346	for (size_t index{}; index < count; ++index)	75,545✔
347	result.push_back(buf[index]);	37,773✔
348	}
349
350	out = to_utf8(result);	6,583✔
351	return true;	6,583✔
352	}
353
354	// Unicode case folding (embedded tables).
355	// ----------------------------------------------------------------------------
356
357	bool to_lower(std::string& value) NOEXCEPT	14,258✔
358	{
359	if (is_ascii(value))	14,258✔
360	{
361	value = ascii_to_lower(value);	7,676✔
362	return true;	7,676✔
363	}
364
365	return apply_case(value, value, true);	6,582✔
366	}
367
368	bool to_upper(std::string& value) NOEXCEPT	5✔
369	{
370	if (is_ascii(value))	5✔
371	{
372	value = ascii_to_upper(value);	4✔
373	return true;	4✔
374	}
375
376	return apply_case(value, value, false);	1✔
377	}
378
379	bool to_canonical_composition(std::string& value) NOEXCEPT	8✔
380	{
381	return is_ascii(value) \|\| normal_form(value, false, true);	8✔
382	}
383
384	bool to_canonical_decomposition(std::string& value) NOEXCEPT	12✔
385	{
386	return is_ascii(value) \|\| normal_form(value, false, false);	12✔
387	}
388
389	bool to_compatibility_composition(std::string& value) NOEXCEPT	3✔
390	{
391	return is_ascii(value) \|\| normal_form(value, true, true);	3✔
392	}
393
394	bool to_compatibility_decomposition(std::string& value) NOEXCEPT	14,355✔
395	{
396	return is_ascii(value) \|\| normal_form(value, true, false);	14,355✔
397	}
398
399	// No ICU dependency.
400	// ----------------------------------------------------------------------------
401
402	bool is_unicode(char32_t point) NOEXCEPT	×
403	{
NEW 404	return point <= unicode_max_code_point;	×
405	}
406
407	bool is_separator(char32_t point) NOEXCEPT	1,114,130✔
408	{
409	if (!is_unicode(point))	1,114,130✔
410	return false;
411
412	for (size_t index{}; index < char32_separators_count; ++index)	20,054,034✔
413	if (point == char32_separators[index])	18,939,939✔
414	return true;
415
416	return false;
417	}
418
419	bool is_whitespace(char32_t point) NOEXCEPT	1,114,157✔
420	{
421	if (!is_unicode(point))	1,114,157✔
422	return false;
423
424	for (size_t index{}; index < char32_whitespace_count; ++index)	28,967,273✔
425	if (point == char32_whitespace[index])	27,853,171✔
426	return true;
427
428	return false;
429	}
430
431	bool is_combining(char32_t point) NOEXCEPT	3,465,057✔
432	{
433	if (!is_unicode(point))	3,465,057✔
434	return false;
435
436	// github.com/python/cpython/blob/main/Modules/unicodedata.c
437	// Two-level trie: level-1 selects the 128-entry block, level-2 resolves the entry.
438	const auto data1 = unicode_data1[shift_right(point, 7)];	3,465,057✔
439	const auto data2 = unicode_data2[shift_left(possible_wide_cast<size_t>(data1), 7)	3,465,057✔
440	+ bit_and(point, unmask_right<char32_t>(7))];	3,465,057✔
441	return !is_zero(combining_index[data2]);	3,465,057✔
442	}
443
444	bool is_diacritic(char32_t point) NOEXCEPT	2,228,240✔
445	{
446	if (!is_unicode(point))	2,228,240✔
447	return false;
448
449	for (size_t index{}; index < char32_diacritics_count; ++index)	440,993,141✔
450	if (is_contained(point, char32_diacritics[index]))	438,766,584✔
451	return true;
452
453	return false;
454	}
455
456	bool is_chinese_japanese_or_korean(char32_t point) NOEXCEPT	1,287,868✔
457	{
458	if (!is_unicode(point))	1,287,868✔
459	return false;
460
461	for (size_t index{}; index < char32_chinese_japanese_korean_count; ++index)	36,207,775✔
462	if (is_contained(point, char32_chinese_japanese_korean[index]))	35,017,668✔
463	return true;
464
465	return false;
466	}
467
468	bool has_whitespace(const std::string& value) NOEXCEPT	11✔
469	{
470	if (value.empty())	11✔
471	return false;
472
473	const auto points = to_utf32(value);	10✔
474	return std::any_of(points.begin(), points.end(), [](char32_t character)	10✔
475	{
476	return is_whitespace(character);	14✔
477	});
478	}
479
480	std::string to_non_combining_form(const std::string& value) NOEXCEPT	31,875✔
481	{
482	if (value.empty())	31,875✔
483	return value;	8✔
484
485	// utf32 ensures each word is a single unicode character.
486	auto points = to_utf32(value);	31,867✔
487	std::erase_if(points, is_combining);	31,867✔
488	return to_utf8(points);	31,867✔
489	}
490
491	std::string to_non_diacritic_form(const std::string& value) NOEXCEPT	6✔
492	{
493	if (value.empty())	6✔
494	return value;	1✔
495
496	// utf32 ensures each word is a single unicode character.
497	auto points = to_utf32(value);	5✔
498	std::erase_if(points, is_diacritic);	5✔
499	return to_utf8(points);	5✔
500	}
501
502	// Compress ascii whitespace and remove ascii spaces between cjk characters.
503	std::string to_compressed_form(const std::string& value) NOEXCEPT	31,881✔
504	{
505	// Compress ascii whitespace to a single 0x20 between each utf32 token.
506	const auto normalized = system::join(system::split(value));	31,881✔
507
508	// utf32 ensures each word is a single unicode character.
509	const auto points = to_utf32(normalized);	31,881✔
510
511	// A character cannot be between two others if there aren't at least three.
512	if (points.size() < 3u)	31,881✔
513	return normalized;	4,108✔
514
515	// Copy the first character to output.
516	std::u32string compressed{ points.front() };	27,773✔
517
518	// Remove a single ascii whitespace between CJK characters.
519	// Front and back cannot be between two characters, so skip them.
520	for (size_t point = 1; point < sub1(points.size()); point++)	1,204,622✔
521	{
522	if (!(is_ascii_whitespace(points[point]) &&	1,176,849✔
523	is_chinese_japanese_or_korean(points[sub1(point)]) &&	170,019✔
524	is_chinese_japanese_or_korean(points[add1(point)])))	3,738✔
525	{
526	compressed += points[point];	1,173,112✔
527	}
528	}
529
530	// Copy the last character to output.
531	compressed += points.back();	27,773✔
532	return to_utf8(compressed);	27,773✔
533	}
534
535	} // namespace system
536	} // namespace libbitcoin

libbitcoin / libbitcoin-system / 23070084244

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous