unicode_nfc.h

Go to the documentation of this file.

#pragma once
// Unicode Normalization Form C (UAX #15) for the Qwen2.5/Qwen3 tokeniser (chat_tokenizer.h), whose
// tokenizer.json normalises with NFC before pre-tokenisation. Table-driven: unicode_nfc_tables.h is
// generated by tools/gen_nfc_tables.py from Python's unicodedata, filtered to the older Unicode tables
// of HF tokenizers' NFC (the reference ember's Qwen ids are gated against). Hangul syllables are
// decomposed and composed arithmetically (UAX #15 / Unicode chapter 3.12).
//
// nfc_utf8 decodes as llama3_tokenizer.h's cpts_from_utf8 does (an invalid byte becomes U+FFFD, as the
// pre-tokeniser would make it anyway) and returns the input bytes unchanged when NFC changes no code
// point, so text that is already NFC tokenises exactly as before.
#include <algorithm>
#include <cstdint>
#include <string>
#include <vector>
 
#include "llama3_tokenizer.h"
#include "unicode_nfc_tables.h"
 
namespace ember {
namespace nfc {
 
inline constexpr uint32_t kSBase = 0xAC00, kLBase = 0x1100, kVBase = 0x1161, kTBase = 0x11A7;
inline constexpr uint32_t kLCount = 19, kVCount = 21, kTCount = 28, kNCount = kVCount * kTCount,
                          kSCount = kLCount * kNCount;
 
inline uint8_t ccc(uint32_t c) {
    if (c < tables::kCccCp[0]) return 0;
    const uint32_t* end = tables::kCccCp + tables::kCccCount;
    const uint32_t* it = std::lower_bound(tables::kCccCp, end, c);
    return it != end && *it == c ? tables::kCccVal[it - tables::kCccCp] : 0;
}
 
// Appends c's full canonical decomposition to out.
inline void decompose(uint32_t c, std::vector<uint32_t>& out) {
    if (c >= kSBase && c < kSBase + kSCount) {
        const uint32_t s = c - kSBase;
        out.push_back(kLBase + s / kNCount);
        out.push_back(kVBase + (s % kNCount) / kTCount);
        if (s % kTCount) out.push_back(kTBase + s % kTCount);
        return;
    }
    if (c >= tables::kDecompCp[0]) {
        const uint32_t* end = tables::kDecompCp + tables::kDecompCount;
        const uint32_t* it = std::lower_bound(tables::kDecompCp, end, c);
        if (it != end && *it == c) {
            const size_t i = static_cast<size_t>(it - tables::kDecompCp);
            out.insert(out.end(), tables::kDecompData + tables::kDecompOff[i],
                       tables::kDecompData + tables::kDecompOff[i] + tables::kDecompLen[i]);
            return;
        }
    }
    out.push_back(c);
}
 
// The primary composite of (a, b), or 0.
inline uint32_t compose(uint32_t a, uint32_t b) {
    if (a >= kLBase && a < kLBase + kLCount && b >= kVBase && b < kVBase + kVCount)
        return kSBase + ((a - kLBase) * kVCount + (b - kVBase)) * kTCount;
    if (a >= kSBase && a < kSBase + kSCount && (a - kSBase) % kTCount == 0 && b > kTBase && b < kTBase + kTCount)
        return a + (b - kTBase);
    const uint64_t key = (static_cast<uint64_t>(a) << 32) | b;
    const uint64_t* end = tables::kCompKey + tables::kCompCount;
    const uint64_t* it = std::lower_bound(tables::kCompKey, end, key);
    return it != end && *it == key ? tables::kCompVal[it - tables::kCompKey] : 0;
}
 
// NFC of a code point sequence: canonical decomposition, canonical ordering, canonical composition.
inline std::vector<uint32_t> nfc(const std::vector<uint32_t>& in) {
    std::vector<uint32_t> d;
    d.reserve(in.size() + 8);
    for (uint32_t c : in) decompose(c, d);
    // Canonical ordering: each run of non-starters stably sorted by class.
    for (size_t i = 0; i < d.size();) {
        if (ccc(d[i]) == 0) {
            ++i;
            continue;
        }
        size_t j = i;
        while (j < d.size() && ccc(d[j]) != 0) ++j;
        std::stable_sort(d.begin() + static_cast<std::ptrdiff_t>(i), d.begin() + static_cast<std::ptrdiff_t>(j),
                         [](uint32_t a, uint32_t b) { return ccc(a) < ccc(b); });
        i = j;
    }
    // Canonical composition: c joins the last starter unless blocked (a character between them of
    // class 0 or of class >= c's).
    std::vector<uint32_t> out;
    out.reserve(d.size());
    size_t starter = 0;
    bool have_starter = false;
    int last = 0;  // class of out.back()
    for (uint32_t c : d) {
        const int cc = ccc(c);
        if (have_starter) {
            const bool adjacent = out.size() == starter + 1;
            if (adjacent || (last != 0 && last < cc)) {
                if (const uint32_t p = compose(out[starter], c)) {
                    out[starter] = p;
                    continue;
                }
            }
        }
        if (cc == 0) {
            starter = out.size();
            have_starter = true;
        }
        last = cc;
        out.push_back(c);
    }
    return out;
}
 
// NFC of UTF-8 text; the input itself when NFC changes no code point (always for ASCII).
inline std::string nfc_utf8(const std::string& text) {
    bool ascii = true;
    for (unsigned char b : text)
        if (b >= 0x80) {
            ascii = false;
            break;
        }
    if (ascii) return text;
    const std::vector<uint32_t> cp = microtorch::llama3::cpts_from_utf8(text);
    const std::vector<uint32_t> n = nfc(cp);
    if (n == cp) return text;
    std::string out;
    out.reserve(text.size() + 4);
    for (uint32_t c : n) microtorch::llama3::append_utf8(c, out);
    return out;
}
 
}  // namespace nfc
}  // namespace ember