hfs_unicode.cpp

Go to the documentation of this file.

// hfs_unicode.cpp -- UTF-16BE decoding + best-effort NFD -> NFC.
//
// We decode UTF-16BE into a std::vector<uint32_t> of Unicode code points,
// run the NFC compositor over THAT (so we don't need to parse multi-byte
// UTF-8 sequences), and finally encode to UTF-8 for output.
//
// The composition table is finite -- see comments in the file. It covers
// the practical European-language cases. Out-of-table sequences pass
// through unchanged.
 
#include "hfs_unicode.hpp"
 
#include <algorithm>
#include <cstdint>
#include <cstring>
#include <string>
#include <unordered_map>
#include <vector>
 
namespace hfs {
 
namespace {
 
// ----- UTF-16BE -> code-point vector -----
 
std::vector<uint32_t> utf16be_to_codepoints(const unsigned char* src,
                                              size_t code_units) {
    std::vector<uint32_t> out;
    out.reserve(code_units);
    for (size_t i = 0; i < code_units; ++i) {
        const unsigned char* p = src + i * 2;
        const uint16_t u = static_cast<uint16_t>((p[0] << 8) | p[1]);
        if (u >= 0xD800 && u <= 0xDBFF) {
            // High surrogate, expect a low surrogate next
            if (i + 1 < code_units) {
                const unsigned char* q = src + (i + 1) * 2;
                const uint16_t v = static_cast<uint16_t>((q[0] << 8) | q[1]);
                if (v >= 0xDC00 && v <= 0xDFFF) {
                    const uint32_t cp = 0x10000u
                        + ((static_cast<uint32_t>(u - 0xD800) << 10)
                          | (v - 0xDC00));
                    out.push_back(cp);
                    ++i;
                    continue;
                }
            }
            out.push_back(0xFFFD);  // lone high surrogate
        } else if (u >= 0xDC00 && u <= 0xDFFF) {
            out.push_back(0xFFFD);  // unexpected low surrogate
        } else {
            out.push_back(u);
        }
    }
    return out;
}
 
// ----- Code-point vector -> UTF-8 -----
 
void append_utf8(std::string& out, uint32_t cp) {
    if (cp < 0x80) {
        out.push_back(static_cast<char>(cp));
    } else if (cp < 0x800) {
        out.push_back(static_cast<char>(0xC0 | (cp >> 6)));
        out.push_back(static_cast<char>(0x80 | (cp & 0x3F)));
    } else if (cp < 0x10000) {
        out.push_back(static_cast<char>(0xE0 |  (cp >> 12)));
        out.push_back(static_cast<char>(0x80 | ((cp >> 6) & 0x3F)));
        out.push_back(static_cast<char>(0x80 |  (cp & 0x3F)));
    } else if (cp < 0x110000) {
        out.push_back(static_cast<char>(0xF0 |  (cp >> 18)));
        out.push_back(static_cast<char>(0x80 | ((cp >> 12) & 0x3F)));
        out.push_back(static_cast<char>(0x80 | ((cp >> 6) & 0x3F)));
        out.push_back(static_cast<char>(0x80 |  (cp & 0x3F)));
    } else {
        // Out of Unicode range -- replace with U+FFFD
        out.push_back(static_cast<char>(0xEF));
        out.push_back(static_cast<char>(0xBF));
        out.push_back(static_cast<char>(0xBD));
    }
}
 
std::string codepoints_to_utf8(const std::vector<uint32_t>& cps) {
    std::string out;
    out.reserve(cps.size() * 2);
    for (uint32_t cp : cps) append_utf8(out, cp);
    return out;
}
 
// ----- NFC composition table -----
//
// Key: (base << 32) | combining_mark
// Value: precomposed code point
//
// We populate the table lazily on first call. Coverage:
//   * Latin-1 vowels with grave/acute/circumflex/diaeresis/tilde/ring
//   * c-cedilla, n-tilde
//   * y-acute, y-diaeresis
//   * Latin Extended-A pairs (most accented characters used in
//     Italian, French, Spanish, German, Portuguese, Polish, Czech,
//     Hungarian, Nordic)
//   * Greek tonos (single accent over alpha/epsilon/eta/iota/...)
//
// Out-of-table sequences just stay decomposed.
 
uint64_t make_key(uint32_t base, uint32_t mark) {
    return (static_cast<uint64_t>(base) << 32) | mark;
}
 
const std::unordered_map<uint64_t, uint32_t>& nfc_table() {
    static const std::unordered_map<uint64_t, uint32_t> t = {
        // ---- COMBINING GRAVE ACCENT (U+0300) ----
        { make_key('A', 0x0300), 0x00C0 }, { make_key('a', 0x0300), 0x00E0 },
        { make_key('E', 0x0300), 0x00C8 }, { make_key('e', 0x0300), 0x00E8 },
        { make_key('I', 0x0300), 0x00CC }, { make_key('i', 0x0300), 0x00EC },
        { make_key('O', 0x0300), 0x00D2 }, { make_key('o', 0x0300), 0x00F2 },
        { make_key('U', 0x0300), 0x00D9 }, { make_key('u', 0x0300), 0x00F9 },
 
        // ---- COMBINING ACUTE ACCENT (U+0301) ----
        { make_key('A', 0x0301), 0x00C1 }, { make_key('a', 0x0301), 0x00E1 },
        { make_key('E', 0x0301), 0x00C9 }, { make_key('e', 0x0301), 0x00E9 },
        { make_key('I', 0x0301), 0x00CD }, { make_key('i', 0x0301), 0x00ED },
        { make_key('O', 0x0301), 0x00D3 }, { make_key('o', 0x0301), 0x00F3 },
        { make_key('U', 0x0301), 0x00DA }, { make_key('u', 0x0301), 0x00FA },
        { make_key('Y', 0x0301), 0x00DD }, { make_key('y', 0x0301), 0x00FD },
        { make_key('C', 0x0301), 0x0106 }, { make_key('c', 0x0301), 0x0107 },
        { make_key('L', 0x0301), 0x0139 }, { make_key('l', 0x0301), 0x013A },
        { make_key('N', 0x0301), 0x0143 }, { make_key('n', 0x0301), 0x0144 },
        { make_key('R', 0x0301), 0x0154 }, { make_key('r', 0x0301), 0x0155 },
        { make_key('S', 0x0301), 0x015A }, { make_key('s', 0x0301), 0x015B },
        { make_key('Z', 0x0301), 0x0179 }, { make_key('z', 0x0301), 0x017A },
 
        // ---- COMBINING CIRCUMFLEX (U+0302) ----
        { make_key('A', 0x0302), 0x00C2 }, { make_key('a', 0x0302), 0x00E2 },
        { make_key('E', 0x0302), 0x00CA }, { make_key('e', 0x0302), 0x00EA },
        { make_key('I', 0x0302), 0x00CE }, { make_key('i', 0x0302), 0x00EE },
        { make_key('O', 0x0302), 0x00D4 }, { make_key('o', 0x0302), 0x00F4 },
        { make_key('U', 0x0302), 0x00DB }, { make_key('u', 0x0302), 0x00FB },
        { make_key('C', 0x0302), 0x0108 }, { make_key('c', 0x0302), 0x0109 },
        { make_key('G', 0x0302), 0x011C }, { make_key('g', 0x0302), 0x011D },
        { make_key('H', 0x0302), 0x0124 }, { make_key('h', 0x0302), 0x0125 },
        { make_key('J', 0x0302), 0x0134 }, { make_key('j', 0x0302), 0x0135 },
        { make_key('S', 0x0302), 0x015C }, { make_key('s', 0x0302), 0x015D },
        { make_key('W', 0x0302), 0x0174 }, { make_key('w', 0x0302), 0x0175 },
        { make_key('Y', 0x0302), 0x0176 }, { make_key('y', 0x0302), 0x0177 },
 
        // ---- COMBINING TILDE (U+0303) ----
        { make_key('A', 0x0303), 0x00C3 }, { make_key('a', 0x0303), 0x00E3 },
        { make_key('N', 0x0303), 0x00D1 }, { make_key('n', 0x0303), 0x00F1 },
        { make_key('O', 0x0303), 0x00D5 }, { make_key('o', 0x0303), 0x00F5 },
        { make_key('I', 0x0303), 0x0128 }, { make_key('i', 0x0303), 0x0129 },
        { make_key('U', 0x0303), 0x0168 }, { make_key('u', 0x0303), 0x0169 },
 
        // ---- COMBINING DIAERESIS (U+0308) ----
        { make_key('A', 0x0308), 0x00C4 }, { make_key('a', 0x0308), 0x00E4 },
        { make_key('E', 0x0308), 0x00CB }, { make_key('e', 0x0308), 0x00EB },
        { make_key('I', 0x0308), 0x00CF }, { make_key('i', 0x0308), 0x00EF },
        { make_key('O', 0x0308), 0x00D6 }, { make_key('o', 0x0308), 0x00F6 },
        { make_key('U', 0x0308), 0x00DC }, { make_key('u', 0x0308), 0x00FC },
        { make_key('Y', 0x0308), 0x0178 }, { make_key('y', 0x0308), 0x00FF },
 
        // ---- COMBINING RING ABOVE (U+030A) ----
        { make_key('A', 0x030A), 0x00C5 }, { make_key('a', 0x030A), 0x00E5 },
        { make_key('U', 0x030A), 0x016E }, { make_key('u', 0x030A), 0x016F },
 
        // ---- COMBINING CEDILLA (U+0327) ----
        { make_key('C', 0x0327), 0x00C7 }, { make_key('c', 0x0327), 0x00E7 },
        { make_key('G', 0x0327), 0x0122 }, { make_key('g', 0x0327), 0x0123 },
        { make_key('K', 0x0327), 0x0136 }, { make_key('k', 0x0327), 0x0137 },
        { make_key('L', 0x0327), 0x013B }, { make_key('l', 0x0327), 0x013C },
        { make_key('N', 0x0327), 0x0145 }, { make_key('n', 0x0327), 0x0146 },
        { make_key('R', 0x0327), 0x0156 }, { make_key('r', 0x0327), 0x0157 },
        { make_key('S', 0x0327), 0x015E }, { make_key('s', 0x0327), 0x015F },
        { make_key('T', 0x0327), 0x0162 }, { make_key('t', 0x0327), 0x0163 },
 
        // ---- COMBINING MACRON (U+0304) ----
        { make_key('A', 0x0304), 0x0100 }, { make_key('a', 0x0304), 0x0101 },
        { make_key('E', 0x0304), 0x0112 }, { make_key('e', 0x0304), 0x0113 },
        { make_key('I', 0x0304), 0x012A }, { make_key('i', 0x0304), 0x012B },
        { make_key('O', 0x0304), 0x014C }, { make_key('o', 0x0304), 0x014D },
        { make_key('U', 0x0304), 0x016A }, { make_key('u', 0x0304), 0x016B },
 
        // ---- COMBINING CARON (U+030C, hacek) ----
        { make_key('C', 0x030C), 0x010C }, { make_key('c', 0x030C), 0x010D },
        { make_key('D', 0x030C), 0x010E }, { make_key('d', 0x030C), 0x010F },
        { make_key('E', 0x030C), 0x011A }, { make_key('e', 0x030C), 0x011B },
        { make_key('L', 0x030C), 0x013D }, { make_key('l', 0x030C), 0x013E },
        { make_key('N', 0x030C), 0x0147 }, { make_key('n', 0x030C), 0x0148 },
        { make_key('R', 0x030C), 0x0158 }, { make_key('r', 0x030C), 0x0159 },
        { make_key('S', 0x030C), 0x0160 }, { make_key('s', 0x030C), 0x0161 },
        { make_key('T', 0x030C), 0x0164 }, { make_key('t', 0x030C), 0x0165 },
        { make_key('Z', 0x030C), 0x017D }, { make_key('z', 0x030C), 0x017E },
 
        // ---- COMBINING OGONEK (U+0328) ----
        { make_key('A', 0x0328), 0x0104 }, { make_key('a', 0x0328), 0x0105 },
        { make_key('E', 0x0328), 0x0118 }, { make_key('e', 0x0328), 0x0119 },
        { make_key('I', 0x0328), 0x012E }, { make_key('i', 0x0328), 0x012F },
        { make_key('U', 0x0328), 0x0172 }, { make_key('u', 0x0328), 0x0173 },
 
        // ---- COMBINING DOUBLE ACUTE (U+030B), Hungarian ----
        { make_key('O', 0x030B), 0x0150 }, { make_key('o', 0x030B), 0x0151 },
        { make_key('U', 0x030B), 0x0170 }, { make_key('u', 0x030B), 0x0171 },
 
        // ---- COMBINING DOT ABOVE (U+0307) ----
        { make_key('Z', 0x0307), 0x017B }, { make_key('z', 0x0307), 0x017C },
    };
    return t;
}
 
bool is_combining_mark(uint32_t cp) {
    // Range of combining diacritical marks (U+0300 .. U+036F) covers
    // every accent in our table. We don't need the full Unicode
    // combining-class machinery for this.
    return cp >= 0x0300 && cp <= 0x036F;
}
 
std::vector<uint32_t> compose_nfc(const std::vector<uint32_t>& nfd) {
    std::vector<uint32_t> out;
    out.reserve(nfd.size());
 
    const auto& tbl = nfc_table();
    size_t i = 0;
    while (i < nfd.size()) {
        const uint32_t base = nfd[i];
        // Look for a single combining mark following.
        if (i + 1 < nfd.size() && is_combining_mark(nfd[i + 1])) {
            const uint32_t mark = nfd[i + 1];
            auto it = tbl.find(make_key(base, mark));
            if (it != tbl.end()) {
                out.push_back(it->second);
                i += 2;
                // Try to fold any further combining marks if they
                // recompose with the new precomposed character.
                while (i < nfd.size() && is_combining_mark(nfd[i])) {
                    auto it2 = tbl.find(make_key(out.back(), nfd[i]));
                    if (it2 == tbl.end()) {
                        out.push_back(nfd[i]);
                        ++i;
                    } else {
                        out.back() = it2->second;
                        ++i;
                    }
                }
                continue;
            }
        }
        out.push_back(base);
        ++i;
    }
    return out;
}
 
} // anonymous namespace
 
std::string utf16be_to_utf8(const unsigned char* src, size_t code_units) {
    if (src == nullptr || code_units == 0) return {};
    auto cps = utf16be_to_codepoints(src, code_units);
    return codepoints_to_utf8(cps);
}
 
std::string nfd_to_nfc(const std::string& utf8) {
    // Decode UTF-8 -> code points (we assume well-formed UTF-8 since
    // it came from utf16be_to_utf8 above).
    std::vector<uint32_t> cps;
    cps.reserve(utf8.size());
    size_t i = 0;
    while (i < utf8.size()) {
        const unsigned char b = static_cast<unsigned char>(utf8[i]);
        uint32_t cp = 0;
        size_t len = 0;
        if (b < 0x80) { cp = b; len = 1; }
        else if ((b & 0xE0) == 0xC0) { cp = b & 0x1F; len = 2; }
        else if ((b & 0xF0) == 0xE0) { cp = b & 0x0F; len = 3; }
        else if ((b & 0xF8) == 0xF0) { cp = b & 0x07; len = 4; }
        else { cp = 0xFFFD; len = 1; }
        if (i + len > utf8.size()) { cps.push_back(0xFFFD); break; }
        for (size_t j = 1; j < len; ++j) {
            cp = (cp << 6) | (static_cast<unsigned char>(utf8[i + j]) & 0x3F);
        }
        cps.push_back(cp);
        i += len;
    }
    return codepoints_to_utf8(compose_nfc(cps));
}
 
std::string hfs_filename_to_host(const unsigned char* src, size_t code_units) {
    auto cps = utf16be_to_codepoints(src, code_units);
    cps = compose_nfc(cps);
    std::string raw = codepoints_to_utf8(cps);
 
    // Sanitise for host filesystem: replace NUL and '/' with '_'.
    // (We don't apply Windows-specific stripping here; the project's
    // text_utils helpers handle that elsewhere. We just produce a
    // string safe for posix paths.)
    std::string out;
    out.reserve(raw.size());
    for (char c : raw) {
        unsigned char uc = static_cast<unsigned char>(c);
        if (uc == 0 || uc == '/') out.push_back('_');
        else out.push_back(c);
    }
    if (out.empty()) out = "_";
    return out;
}
 
} // namespace hfs