use std::sync::LazyLock;
use vyre::ir::{BufferAccess, BufferDecl, DataType, Expr, Node, Program};
use vyre_driver::{DispatchConfig, VyreBackend};
use vyre_libs::region::wrap_anonymous;
use vyre_primitives::wire::{pack_u32_slice, unpack_u32_slice_into};
use crate::pretokenize::{SplitPattern, pretokens};
use crate::{ExatokError, trap_program};
pub const BOUNDARIES_OP_ID: &str = "exatok::gpu_pretokenize::boundaries";
pub const WORKGROUP_WIDTH: u32 = 256;
pub const MAX_INPUT_BYTES: u32 = 1 << 20;
pub const CLASS_LETTER: u32 = 1;
pub const CLASS_NUMBER: u32 = 2;
pub const CLASS_SPACE: u32 = 4;
const CLASS_ANY: u32 = CLASS_LETTER | CLASS_NUMBER | CLASS_SPACE;
pub const BYTES_BUFFER: &str = "exatok_pretok_bytes";
pub const ASCII_CLASS_BUFFER: &str = "exatok_pretok_ascii_class";
pub const RANGE_CLASS_BUFFER: &str = "exatok_pretok_range_class";
pub const OFFSETS_BUFFER: &str = "exatok_pretok_offsets";
const UNITS_BUFFER: &str = "exatok_pretok_units";
const CHASE_A_BUFFER: &str = "exatok_pretok_chase_a";
const CHASE_B_BUFFER: &str = "exatok_pretok_chase_b";
const CHAIN_A_BUFFER: &str = "exatok_pretok_chain_a";
const CHAIN_B_BUFFER: &str = "exatok_pretok_chain_b";
const BYTE_PAD: u32 = 4;
const UNIT_LEN: u32 = 0;
const UNIT_CLASS: u32 = 1;
const UNIT_PLANES: u32 = 2;
const PLANE_LETTER: u32 = 0;
const PLANE_OTHER: u32 = 1;
const PLANE_SPACE: u32 = 2;
const PLANE_LAST_SPACE: u32 = 3;
const PLANE_BREAK: u32 = 4;
const PLANE_LAST_BREAK: u32 = 5;
const CHASE_PLANES: u32 = 6;
const APOSTROPHE: u32 = 0x27;
const SPACE: u32 = 0x20;
const CR: u32 = 0x0D;
const LF: u32 = 0x0A;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct BoundaryShape {
input_len: u32,
}
impl BoundaryShape {
#[must_use]
pub const fn new(input_len: u32) -> Self {
Self { input_len }
}
#[must_use]
pub const fn input_len(self) -> u32 {
self.input_len
}
#[must_use]
pub const fn positions(self) -> u32 {
self.input_len + 1
}
#[must_use]
pub fn rounds(self) -> u32 {
let target = u64::from(self.positions());
let mut rounds = 1;
let mut reach = 2u64;
while reach < target {
reach *= 2;
rounds += 1;
}
rounds
}
#[must_use]
pub fn chunks(self) -> u32 {
self.positions().div_ceil(WORKGROUP_WIDTH)
}
fn rejection(self) -> Option<String> {
(self.input_len > MAX_INPUT_BYTES).then(|| {
format!(
"gpu_pretokenize boundary shape has {} input bytes, past the {MAX_INPUT_BYTES} \
byte ceiling. Fix: split the text ON A PRETOKEN BOUNDARY and dispatch each \
piece, then rebase each piece's offsets by adding its start. Take the boundary \
from a dispatch of the first {MAX_INPUT_BYTES} bytes rather than cutting at a \
fixed offset: a cut inside a pretoken makes the end-of-input alternatives fire \
there and invents a boundary the whole text does not have.",
self.input_len
)
})
}
}
#[derive(Debug)]
pub struct ClassTable {
ascii: [u32; 128],
ranges: Vec<u32>,
}
impl ClassTable {
#[must_use]
pub fn ascii(&self) -> &[u32; 128] {
&self.ascii
}
#[must_use]
pub fn ranges(&self) -> &[u32] {
&self.ranges
}
#[must_use]
pub fn range_count(&self) -> u32 {
(self.ranges.len() / 3) as u32
}
#[must_use]
pub fn class_of(&self, scalar: u32) -> u32 {
if let Some(bits) = usize::try_from(scalar)
.ok()
.and_then(|index| self.ascii.get(index))
{
return *bits;
}
let mut low = 0usize;
let mut high = self.ranges.len() / 3;
while low < high {
let mid = low + (high - low) / 2;
match self.ranges.get(mid * 3) {
Some(&start) if start <= scalar => low = mid + 1,
_ => high = mid,
}
}
if low == 0 {
return 0;
}
match (self.ranges.get((low - 1) * 3 + 1), self.ranges.get((low - 1) * 3 + 2)) {
(Some(&end), Some(&bits)) if scalar <= end => bits,
_ => 0,
}
}
}
pub fn class_table() -> &'static ClassTable {
&CLASS_TABLE
}
static CLASS_TABLE: LazyLock<ClassTable> = LazyLock::new(build_class_table);
fn derive_class(scalar: u32) -> u32 {
let Some(character) = char::from_u32(scalar) else {
return 0;
};
let mut encoded = [0u8; 4];
let bytes = character.encode_utf8(&mut encoded).as_bytes();
let width = bytes.len();
let mut wrapped = [0u8; 6];
wrapped[0] = b'.';
wrapped[1..=width].copy_from_slice(bytes);
wrapped[width + 1] = b'.';
let mut spans = pretokens(SplitPattern::Cl100kBase, &wrapped[..width + 2]);
spans.next();
if spans.next().is_none() {
return 0;
}
let mut suffixed = [0u8; 5];
suffixed[0] = b'a';
suffixed[1..=width].copy_from_slice(bytes);
if pretokens(SplitPattern::Cl100kBase, &suffixed[..=width])
.next()
.is_some_and(|span| span.end == 1 + width)
{
return CLASS_LETTER;
}
let mut repeated = [0u8; 16];
for copy in 0..4 {
repeated[copy * width..(copy + 1) * width].copy_from_slice(bytes);
}
if pretokens(SplitPattern::Cl100kBase, &repeated[..4 * width])
.next()
.is_some_and(|span| span.end == 3 * width)
{
return CLASS_NUMBER;
}
CLASS_SPACE
}
fn build_class_table() -> ClassTable {
let mut ascii = [0u32; 128];
for (scalar, slot) in ascii.iter_mut().enumerate() {
*slot = derive_class(scalar as u32);
}
let mut ranges = Vec::new();
let mut run_start = 0x80u32;
let mut run_bits = derive_class(0x80);
for scalar in 0x81..=0x0010_FFFFu32 {
let bits = derive_class(scalar);
if bits == run_bits {
continue;
}
if run_bits != 0 {
ranges.extend_from_slice(&[run_start, scalar - 1, run_bits]);
}
run_start = scalar;
run_bits = bits;
}
if run_bits != 0 {
ranges.extend_from_slice(&[run_start, 0x0010_FFFF, run_bits]);
}
ClassTable { ascii, ranges }
}
fn lift_levels(count: u32) -> u32 {
let mut levels = 0;
let mut reach = 1u64;
while reach - 1 < u64::from(count) {
reach *= 2;
levels += 1;
}
levels
}
fn range_slots(levels: u32) -> u32 {
((1u64 << levels) - 1).max(1) as u32
}
#[must_use]
pub fn boundary_program(shape: BoundaryShape) -> Program {
if let Some(message) = shape.rejection() {
return trap_program(BOUNDARIES_OP_ID, OFFSETS_BUFFER, DataType::U32, message);
}
if shape.input_len() == 0 {
return empty_program();
}
let table = class_table();
let levels = lift_levels(table.range_count());
let slots = range_slots(levels);
let len = shape.input_len();
let positions = shape.positions();
let rounds = shape.rounds();
let mut body = vec![Node::let_bind("local", Expr::LocalId { axis: 0 })];
body.push(stage(shape, decode_body(len, positions, levels)));
body.push(Node::barrier());
body.push(stage(shape, chase_init_body(positions)));
body.push(Node::barrier());
for round in 0..rounds {
let (source, target) = chase_pair(round);
body.push(stage(shape, chase_round_body(positions, source, target)));
body.push(Node::barrier());
}
let settled = settled_chase(rounds);
body.push(stage(shape, next_body(len, positions, settled)));
body.push(Node::barrier());
for round in 0..rounds {
let (source, target) = chain_pair(round);
let carry = (round + 1 < rounds).then_some(target);
body.push(stage(shape, chain_round_body(round, source, carry)));
if round + 1 < rounds {
body.push(Node::barrier());
}
}
let chase_words = CHASE_PLANES * positions;
Program::wrapped(
vec![
BufferDecl::storage(BYTES_BUFFER, 0, BufferAccess::ReadOnly, DataType::U32)
.with_count(len + BYTE_PAD),
BufferDecl::storage(ASCII_CLASS_BUFFER, 1, BufferAccess::ReadOnly, DataType::U32)
.with_count(128),
BufferDecl::storage(RANGE_CLASS_BUFFER, 2, BufferAccess::ReadOnly, DataType::U32)
.with_count(slots * 3),
BufferDecl::storage(UNITS_BUFFER, 3, BufferAccess::ReadWrite, DataType::U32)
.with_count(UNIT_PLANES * positions),
BufferDecl::storage(CHASE_A_BUFFER, 4, BufferAccess::ReadWrite, DataType::U32)
.with_count(chase_words),
BufferDecl::storage(CHASE_B_BUFFER, 5, BufferAccess::ReadWrite, DataType::U32)
.with_count(chase_words),
BufferDecl::storage(CHAIN_A_BUFFER, 6, BufferAccess::ReadWrite, DataType::U32)
.with_count(positions),
BufferDecl::storage(CHAIN_B_BUFFER, 7, BufferAccess::ReadWrite, DataType::U32)
.with_count(positions),
BufferDecl::storage(OFFSETS_BUFFER, 8, BufferAccess::ReadWrite, DataType::U32)
.with_count(positions),
],
[WORKGROUP_WIDTH, 1, 1],
vec![wrap_anonymous(BOUNDARIES_OP_ID, body)],
)
}
fn empty_program() -> Program {
Program::wrapped(
vec![
BufferDecl::storage(OFFSETS_BUFFER, 0, BufferAccess::ReadWrite, DataType::U32)
.with_count(1),
],
[1, 1, 1],
vec![wrap_anonymous(
BOUNDARIES_OP_ID,
vec![Node::if_then(
Expr::eq(Expr::gid_x(), Expr::u32(0)),
vec![Node::store(OFFSETS_BUFFER, Expr::u32(0), Expr::u32(0))],
)],
)],
)
}
fn stage(shape: BoundaryShape, body: Vec<Node>) -> Node {
Node::loop_for(
"chunk",
Expr::u32(0),
Expr::u32(shape.chunks()),
vec![
Node::let_bind(
"p",
Expr::add(
Expr::var("local"),
Expr::mul(Expr::var("chunk"), Expr::u32(WORKGROUP_WIDTH)),
),
),
Node::if_then(
Expr::lt(Expr::var("p"), Expr::u32(shape.positions())),
body,
),
],
)
}
fn at() -> Expr {
Expr::var("p")
}
fn plane_at(positions: u32, plane: u32, index: Expr) -> Expr {
Expr::add(Expr::u32(plane * positions), index)
}
fn unit_load(positions: u32, plane: u32, index: Expr) -> Expr {
Expr::load(UNITS_BUFFER, plane_at(positions, plane, index))
}
fn chase_load(buffer: &str, positions: u32, plane: u32, index: Expr) -> Expr {
Expr::load(buffer, plane_at(positions, plane, index))
}
fn chase_store(buffer: &str, positions: u32, plane: u32, index: Expr, value: Expr) -> Node {
Node::store(buffer, plane_at(positions, plane, index), value)
}
fn chase_pair(round: u32) -> (&'static str, &'static str) {
if round % 2 == 0 {
(CHASE_A_BUFFER, CHASE_B_BUFFER)
} else {
(CHASE_B_BUFFER, CHASE_A_BUFFER)
}
}
fn settled_chase(rounds: u32) -> &'static str {
if rounds % 2 == 1 {
CHASE_B_BUFFER
} else {
CHASE_A_BUFFER
}
}
fn chain_pair(round: u32) -> (&'static str, &'static str) {
if round % 2 == 0 {
(CHAIN_A_BUFFER, CHAIN_B_BUFFER)
} else {
(CHAIN_B_BUFFER, CHAIN_A_BUFFER)
}
}
fn decode_body(len: u32, positions: u32, levels: u32) -> Vec<Node> {
let var = |name: &str| Expr::var(name);
let byte = |offset: u32| Expr::load(BYTES_BUFFER, Expr::add(at(), Expr::u32(offset)));
let mut nodes = vec![
Node::let_bind("lead", byte(0)),
Node::let_bind(
"two_byte",
Expr::and(
Expr::ge(var("lead"), Expr::u32(0xC2)),
Expr::le(var("lead"), Expr::u32(0xDF)),
),
),
Node::let_bind(
"three_byte",
Expr::and(
Expr::ge(var("lead"), Expr::u32(0xE0)),
Expr::le(var("lead"), Expr::u32(0xEF)),
),
),
Node::let_bind(
"four_byte",
Expr::and(
Expr::ge(var("lead"), Expr::u32(0xF0)),
Expr::le(var("lead"), Expr::u32(0xF4)),
),
),
Node::let_bind(
"continuations",
Expr::select(
var("two_byte"),
Expr::u32(1),
Expr::select(
var("three_byte"),
Expr::u32(2),
Expr::select(var("four_byte"), Expr::u32(3), Expr::u32(0)),
),
),
),
Node::let_bind(
"low",
Expr::select(
Expr::eq(var("lead"), Expr::u32(0xE0)),
Expr::u32(0xA0),
Expr::select(
Expr::eq(var("lead"), Expr::u32(0xF0)),
Expr::u32(0x90),
Expr::u32(0x80),
),
),
),
Node::let_bind(
"high",
Expr::select(
Expr::eq(var("lead"), Expr::u32(0xED)),
Expr::u32(0x9F),
Expr::select(
Expr::eq(var("lead"), Expr::u32(0xF4)),
Expr::u32(0x8F),
Expr::u32(0xBF),
),
),
),
Node::let_bind(
"lead_mask",
Expr::select(
var("two_byte"),
Expr::u32(0x1F),
Expr::select(var("three_byte"), Expr::u32(0x0F), Expr::u32(0x07)),
),
),
Node::let_bind("byte1", byte(1)),
Node::let_bind("byte2", byte(2)),
Node::let_bind("byte3", byte(3)),
Node::let_bind(
"decoded",
Expr::and(
Expr::and(
Expr::ne(var("continuations"), Expr::u32(0)),
Expr::and(
Expr::ge(var("byte1"), var("low")),
Expr::le(var("byte1"), var("high")),
),
),
Expr::and(
Expr::or(
Expr::lt(var("continuations"), Expr::u32(2)),
Expr::and(
Expr::ge(var("byte2"), Expr::u32(0x80)),
Expr::le(var("byte2"), Expr::u32(0xBF)),
),
),
Expr::or(
Expr::lt(var("continuations"), Expr::u32(3)),
Expr::and(
Expr::ge(var("byte3"), Expr::u32(0x80)),
Expr::le(var("byte3"), Expr::u32(0xBF)),
),
),
),
),
),
Node::let_bind(
"scalar1",
Expr::bitor(
Expr::shl(Expr::bitand(var("lead"), var("lead_mask")), Expr::u32(6)),
Expr::bitand(var("byte1"), Expr::u32(0x3F)),
),
),
Node::let_bind(
"scalar2",
Expr::select(
Expr::ge(var("continuations"), Expr::u32(2)),
Expr::bitor(
Expr::shl(var("scalar1"), Expr::u32(6)),
Expr::bitand(var("byte2"), Expr::u32(0x3F)),
),
var("scalar1"),
),
),
Node::let_bind(
"scalar",
Expr::select(
Expr::ge(var("continuations"), Expr::u32(3)),
Expr::bitor(
Expr::shl(var("scalar2"), Expr::u32(6)),
Expr::bitand(var("byte3"), Expr::u32(0x3F)),
),
var("scalar2"),
),
),
];
nodes.extend(range_bits(levels));
nodes.push(Node::let_bind(
"ascii_bits",
Expr::load(
ASCII_CLASS_BUFFER,
Expr::bitand(var("lead"), Expr::u32(0x7F)),
),
));
nodes.push(Node::let_bind(
"is_ascii",
Expr::lt(var("lead"), Expr::u32(0x80)),
));
nodes.push(Node::let_bind("at_end", Expr::eq(at(), Expr::u32(len))));
nodes.push(Node::store(
UNITS_BUFFER,
plane_at(positions, UNIT_LEN, at()),
Expr::select(
var("at_end"),
Expr::u32(0),
Expr::select(
var("is_ascii"),
Expr::u32(1),
Expr::select(
var("decoded"),
Expr::add(var("continuations"), Expr::u32(1)),
Expr::u32(1),
),
),
),
));
nodes.push(Node::store(
UNITS_BUFFER,
plane_at(positions, UNIT_CLASS, at()),
Expr::select(
var("at_end"),
Expr::u32(0),
Expr::select(
var("is_ascii"),
var("ascii_bits"),
Expr::select(var("decoded"), var("range_bits"), Expr::u32(0)),
),
),
));
nodes
}
fn range_bits(levels: u32) -> Vec<Node> {
let var = |name: &str| Expr::var(name);
let mut nodes = vec![Node::let_bind("slot0", Expr::u32(0))];
let mut settled = "slot0".to_owned();
for (step, level) in (0..levels).rev().enumerate() {
let probed = format!("slot{}", step + 1);
let probe = Expr::add(var(&settled), Expr::u32(1u32 << level));
nodes.push(Node::let_bind(
probed.clone(),
Expr::select(
Expr::le(
Expr::load(
RANGE_CLASS_BUFFER,
Expr::mul(Expr::sub(probe.clone(), Expr::u32(1)), Expr::u32(3)),
),
var("scalar"),
),
probe,
var(&settled),
),
));
settled = probed;
}
nodes.push(Node::let_bind(
"range_base",
Expr::mul(
Expr::sub(Expr::max(var(&settled), Expr::u32(1)), Expr::u32(1)),
Expr::u32(3),
),
));
nodes.push(Node::let_bind(
"range_bits",
Expr::select(
Expr::and(
Expr::ne(var(&settled), Expr::u32(0)),
Expr::le(
var("scalar"),
Expr::load(
RANGE_CLASS_BUFFER,
Expr::add(var("range_base"), Expr::u32(1)),
),
),
),
Expr::load(
RANGE_CLASS_BUFFER,
Expr::add(var("range_base"), Expr::u32(2)),
),
Expr::u32(0),
),
));
nodes
}
fn chase_init_body(positions: u32) -> Vec<Node> {
let var = |name: &str| Expr::var(name);
let mut nodes = vec![
Node::let_bind("ulen", unit_load(positions, UNIT_LEN, at())),
Node::let_bind("cls", unit_load(positions, UNIT_CLASS, at())),
Node::let_bind("live", Expr::ne(var("ulen"), Expr::u32(0))),
Node::let_bind("step", Expr::add(at(), var("ulen"))),
Node::let_bind(
"is_space",
Expr::and(
var("live"),
Expr::ne(
Expr::bitand(var("cls"), Expr::u32(CLASS_SPACE)),
Expr::u32(0),
),
),
),
Node::let_bind("next_len", unit_load(positions, UNIT_LEN, var("step"))),
Node::let_bind("next_cls", unit_load(positions, UNIT_CLASS, var("step"))),
Node::let_bind(
"next_space",
Expr::and(
Expr::ne(var("next_len"), Expr::u32(0)),
Expr::ne(
Expr::bitand(var("next_cls"), Expr::u32(CLASS_SPACE)),
Expr::u32(0),
),
),
),
Node::let_bind("byte", Expr::load(BYTES_BUFFER, at())),
Node::let_bind(
"is_break",
Expr::or(
Expr::eq(var("byte"), Expr::u32(CR)),
Expr::eq(var("byte"), Expr::u32(LF)),
),
),
];
nodes.push(seed_plane(
positions,
PLANE_LETTER,
Expr::and(
var("live"),
Expr::ne(
Expr::bitand(var("cls"), Expr::u32(CLASS_LETTER)),
Expr::u32(0),
),
),
var("step"),
));
nodes.push(seed_plane(
positions,
PLANE_OTHER,
Expr::and(
var("live"),
Expr::eq(
Expr::bitand(var("cls"), Expr::u32(CLASS_ANY)),
Expr::u32(0),
),
),
var("step"),
));
nodes.push(seed_plane(
positions,
PLANE_SPACE,
var("is_space"),
var("step"),
));
nodes.push(seed_plane(
positions,
PLANE_LAST_SPACE,
Expr::and(var("is_space"), var("next_space")),
var("step"),
));
nodes.push(seed_plane(
positions,
PLANE_BREAK,
var("is_break"),
Expr::add(at(), Expr::u32(1)),
));
nodes.push(chase_store(
CHASE_A_BUFFER,
positions,
PLANE_LAST_BREAK,
at(),
Expr::select(
Expr::and(var("is_space"), var("is_break")),
Expr::add(at(), Expr::u32(1)),
Expr::u32(0),
),
));
nodes
}
fn seed_plane(positions: u32, plane: u32, taken: Expr, target: Expr) -> Node {
chase_store(
CHASE_A_BUFFER,
positions,
plane,
at(),
Expr::select(taken, target, at()),
)
}
fn chase_round_body(positions: u32, source: &str, target: &str) -> Vec<Node> {
let var = |name: &str| Expr::var(name);
let mut nodes = Vec::new();
for plane in [
PLANE_LETTER,
PLANE_OTHER,
PLANE_SPACE,
PLANE_LAST_SPACE,
PLANE_BREAK,
] {
nodes.push(chase_store(
target,
positions,
plane,
at(),
chase_load(
source,
positions,
plane,
chase_load(source, positions, plane, at()),
),
));
}
nodes.push(Node::let_bind(
"half",
chase_load(source, positions, PLANE_SPACE, at()),
));
nodes.push(Node::let_bind(
"far",
chase_load(source, positions, PLANE_LAST_BREAK, var("half")),
));
nodes.push(chase_store(
target,
positions,
PLANE_LAST_BREAK,
at(),
Expr::select(
Expr::ne(var("far"), Expr::u32(0)),
var("far"),
chase_load(source, positions, PLANE_LAST_BREAK, at()),
),
));
nodes
}
fn next_body(len: u32, positions: u32, chase: &str) -> Vec<Node> {
let var = |name: &str| Expr::var(name);
let after = || Expr::add(at(), Expr::u32(1));
let mut nodes = vec![
Node::let_bind("ulen", unit_load(positions, UNIT_LEN, at())),
Node::let_bind("cls", unit_load(positions, UNIT_CLASS, at())),
Node::let_bind("lead", Expr::load(BYTES_BUFFER, at())),
];
for letter in [b's', b'd', b'm', b't'] {
nodes.push(Node::let_bind(
format!("solo_{}", letter as char),
folded_letter(after(), letter),
));
}
nodes.push(Node::let_bind(
"solo",
Expr::max(
Expr::max(var("solo_s"), var("solo_d")),
Expr::max(var("solo_m"), var("solo_t")),
),
));
for [first, second] in [[b'l', b'l'], [b'v', b'e'], [b'r', b'e']] {
let head = format!("head_{}{}", first as char, second as char);
let tail = format!("tail_{}{}", first as char, second as char);
let pair = format!("pair_{}{}", first as char, second as char);
nodes.push(Node::let_bind(head.clone(), folded_letter(after(), first)));
nodes.push(Node::let_bind(
tail.clone(),
folded_letter(Expr::add(after(), var(&head)), second),
));
nodes.push(Node::let_bind(
pair,
Expr::select(
Expr::and(
Expr::ne(var(&head), Expr::u32(0)),
Expr::ne(var(&tail), Expr::u32(0)),
),
Expr::add(Expr::add(after(), var(&head)), var(&tail)),
Expr::u32(0),
),
));
}
nodes.push(Node::let_bind(
"solo_end",
Expr::select(
Expr::ne(var("solo"), Expr::u32(0)),
Expr::add(after(), var("solo")),
Expr::u32(0),
),
));
nodes.push(Node::let_bind(
"pairs_end",
Expr::max(var("pair_ll"), Expr::max(var("pair_ve"), var("pair_re"))),
));
nodes.push(Node::let_bind(
"alt_contraction",
Expr::select(
Expr::eq(var("lead"), Expr::u32(APOSTROPHE)),
Expr::select(
Expr::ne(var("solo_end"), Expr::u32(0)),
var("solo_end"),
var("pairs_end"),
),
Expr::u32(0),
),
));
nodes.push(Node::let_bind(
"lead_ok",
Expr::and(
Expr::and(
Expr::ne(var("ulen"), Expr::u32(0)),
Expr::eq(
Expr::bitand(var("cls"), Expr::u32(CLASS_LETTER | CLASS_NUMBER)),
Expr::u32(0),
),
),
Expr::and(
Expr::ne(var("lead"), Expr::u32(CR)),
Expr::ne(var("lead"), Expr::u32(LF)),
),
),
));
nodes.push(Node::let_bind(
"word_start",
Expr::select(var("lead_ok"), Expr::add(at(), var("ulen")), at()),
));
nodes.push(Node::let_bind(
"word_end",
chase_load(chase, positions, PLANE_LETTER, var("word_start")),
));
nodes.push(Node::let_bind(
"alt_word",
Expr::select(
Expr::ne(var("word_end"), var("word_start")),
var("word_end"),
Expr::u32(0),
),
));
nodes.push(Node::let_bind("digit_at0", at()));
for step in 0..3u32 {
let position = format!("digit_at{step}");
let advanced = format!("digit_at{}", step + 1);
let length = format!("digit_len{step}");
let taken = format!("digit_ok{step}");
nodes.push(Node::let_bind(
length.clone(),
unit_load(positions, UNIT_LEN, var(&position)),
));
let here = Expr::and(
Expr::ne(var(&length), Expr::u32(0)),
Expr::ne(
Expr::bitand(
unit_load(positions, UNIT_CLASS, var(&position)),
Expr::u32(CLASS_NUMBER),
),
Expr::u32(0),
),
);
nodes.push(Node::let_bind(
taken.clone(),
if step == 0 {
here
} else {
Expr::and(var(&format!("digit_ok{}", step - 1)), here)
},
));
nodes.push(Node::let_bind(
advanced,
Expr::select(
var(&taken),
Expr::add(var(&position), var(&length)),
var(&position),
),
));
}
nodes.push(Node::let_bind(
"alt_digits",
Expr::select(var("digit_ok0"), var("digit_at3"), Expr::u32(0)),
));
nodes.push(Node::let_bind(
"punct_start",
Expr::select(Expr::eq(var("lead"), Expr::u32(SPACE)), after(), at()),
));
nodes.push(Node::let_bind(
"punct_end",
chase_load(chase, positions, PLANE_OTHER, var("punct_start")),
));
nodes.push(Node::let_bind(
"alt_punct",
Expr::select(
Expr::ne(var("punct_end"), var("punct_start")),
chase_load(chase, positions, PLANE_BREAK, var("punct_end")),
Expr::u32(0),
),
));
nodes.push(Node::let_bind(
"space_end",
chase_load(chase, positions, PLANE_SPACE, at()),
));
nodes.push(Node::let_bind(
"alt_space_to_end",
Expr::select(
Expr::and(
Expr::ne(var("space_end"), at()),
Expr::eq(var("space_end"), Expr::u32(len)),
),
var("space_end"),
Expr::u32(0),
),
));
nodes.push(Node::let_bind(
"alt_last_break",
chase_load(chase, positions, PLANE_LAST_BREAK, at()),
));
nodes.push(Node::let_bind(
"last_space",
chase_load(chase, positions, PLANE_LAST_SPACE, at()),
));
nodes.push(Node::let_bind(
"alt_space_before",
Expr::select(
Expr::and(
Expr::ne(var("space_end"), at()),
Expr::ne(var("last_space"), at()),
),
var("last_space"),
Expr::u32(0),
),
));
nodes.push(Node::let_bind(
"alt_one_unit",
Expr::add(at(), Expr::max(var("ulen"), Expr::u32(1))),
));
let pick = |candidate: &str, rest: Expr| {
Expr::select(
Expr::ne(Expr::var(candidate), Expr::u32(0)),
Expr::var(candidate),
rest,
)
};
let matched = pick(
"alt_contraction",
pick(
"alt_word",
pick(
"alt_digits",
pick(
"alt_punct",
pick(
"alt_space_to_end",
pick(
"alt_last_break",
pick("alt_space_before", var("alt_one_unit")),
),
),
),
),
),
);
nodes.push(Node::let_bind(
"end",
Expr::select(Expr::eq(at(), Expr::u32(len)), Expr::u32(len), matched),
));
nodes.push(Node::store(CHAIN_A_BUFFER, at(), var("end")));
nodes.push(Node::store(OFFSETS_BUFFER, at(), Expr::u32(0)));
nodes
}
fn folded_letter(index: Expr, letter: u8) -> Expr {
let matched = Expr::eq(
Expr::bitor(Expr::load(BYTES_BUFFER, index.clone()), Expr::u32(SPACE)),
Expr::u32(u32::from(letter)),
);
if letter == b's' {
Expr::select(
matched,
Expr::u32(1),
Expr::select(
Expr::and(
Expr::eq(Expr::load(BYTES_BUFFER, index.clone()), Expr::u32(0xC5)),
Expr::eq(
Expr::load(BYTES_BUFFER, Expr::add(index, Expr::u32(1))),
Expr::u32(0xBF),
),
),
Expr::u32(2),
Expr::u32(0),
),
)
} else {
Expr::select(matched, Expr::u32(1), Expr::u32(0))
}
}
fn chain_round_body(round: u32, source: &str, carry: Option<&str>) -> Vec<Node> {
let var = |name: &str| Expr::var(name);
let mut nodes = vec![
Node::let_bind("cursor", Expr::load(OFFSETS_BUFFER, at())),
Node::store(
OFFSETS_BUFFER,
at(),
Expr::select(
Expr::ne(Expr::bitand(at(), Expr::u32(1u32 << round)), Expr::u32(0)),
Expr::load(source, var("cursor")),
var("cursor"),
),
),
];
if let Some(target) = carry {
nodes.push(Node::store(
target,
at(),
Expr::load(source, Expr::load(source, at())),
));
}
nodes
}
fn supplies_input(decl: &BufferDecl) -> bool {
decl.access() != BufferAccess::Workgroup && !decl.is_backend_allocated_output()
}
fn returns_output(decl: &BufferDecl) -> bool {
decl.is_backend_allocated_output() || decl.access() == BufferAccess::ReadWrite
}
fn output_slot(program: &Program, name: &str) -> Option<usize> {
program
.buffers()
.iter()
.filter(|decl| returns_output(decl))
.position(|decl| decl.name() == name)
}
fn seed_inputs(program: &Program, input: &[u8]) -> Vec<Vec<u8>> {
let table = class_table();
program
.buffers()
.iter()
.filter(|decl| supplies_input(decl))
.map(|decl| {
let count = decl.count() as usize;
let mut words = vec![0u32; count];
match decl.name() {
BYTES_BUFFER => {
for (slot, byte) in words.iter_mut().zip(input) {
*slot = u32::from(*byte);
}
}
ASCII_CLASS_BUFFER => {
for (slot, bits) in words.iter_mut().zip(table.ascii()) {
*slot = *bits;
}
}
RANGE_CLASS_BUFFER => {
for triple in words.chunks_exact_mut(3) {
if let Some(low) = triple.first_mut() {
*low = u32::MAX;
}
}
for (slot, value) in words.iter_mut().zip(table.ranges()) {
*slot = *value;
}
}
_ => {}
}
pack_u32_slice(&words)
})
.collect()
}
pub fn run_boundaries(backend: &dyn VyreBackend, input: &[u8]) -> Result<Vec<u32>, ExatokError> {
let len = u32::try_from(input.len())
.ok()
.filter(|len| *len <= MAX_INPUT_BYTES)
.ok_or_else(|| {
ExatokError::Backend(format!(
"gpu_pretokenize input is {} bytes, past the {MAX_INPUT_BYTES} byte ceiling. \
Fix: split the text ON A PRETOKEN BOUNDARY, dispatch each piece, and rebase \
each piece's offsets by adding its start. Cutting at a fixed offset instead \
invents a boundary at the cut, because the end-of-input alternatives fire \
there.",
input.len()
))
})?;
let shape = BoundaryShape::new(len);
let program = boundary_program(shape);
let inputs = seed_inputs(&program, input);
let workgroup = program.workgroup_size();
let lanes = workgroup[0].max(1) * workgroup[1].max(1) * workgroup[2].max(1);
let mut config = DispatchConfig::default();
config.dispatch_elements = Some(lanes);
config.grid_override = Some([1, 1, 1]);
config.workgroup_override = Some(workgroup);
config.label = Some(BOUNDARIES_OP_ID.to_owned());
let outputs = backend
.dispatch(&program, &inputs, &config)
.map_err(|error| {
ExatokError::Backend(format!("gpu_pretokenize dispatch failed: {error}"))
})?;
let slot = output_slot(&program, OFFSETS_BUFFER).ok_or_else(|| {
ExatokError::Backend(format!(
"gpu_pretokenize program declares no returned `{OFFSETS_BUFFER}` buffer. \
Fix: keep it ReadWrite so the backend hands it back."
))
})?;
let bytes = outputs.get(slot).ok_or_else(|| {
ExatokError::Backend(format!(
"gpu_pretokenize dispatch returned {} buffer(s), needs slot {slot} for \
`{OFFSETS_BUFFER}`. Fix: check the backend honours ReadWrite readback.",
outputs.len()
))
})?;
let mut offsets = Vec::new();
unpack_u32_slice_into(
bytes,
shape.positions() as usize,
OFFSETS_BUFFER,
&mut offsets,
)
.map_err(ExatokError::Backend)?;
let end = offsets.iter().position(|offset| *offset == len).ok_or_else(|| {
ExatokError::Backend(format!(
"gpu_pretokenize produced no {len}-byte terminator in {} offsets. Fix: the chain \
stage did not converge, check the doubling round count.",
offsets.len()
))
})?;
offsets.truncate(end + 1);
Ok(offsets)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn derived_classes_match_host_splits() {
for scalar in [
u32::from(b'a'),
u32::from(b'Z'),
u32::from(b'7'),
u32::from(b' '),
u32::from(b'\n'),
u32::from(b'\r'),
u32::from(b'\''),
u32::from(b'.'),
0x00A0, 0x00B2, 0x017F, 0x0301, 0x2028, 0x3042, 0x4E2D, 0x1F600, 0x1D7CE, ] {
assert_eq!(
class_table().class_of(scalar),
derive_class(scalar),
"class table disagrees with the probe at U+{scalar:04X}"
);
}
assert_eq!(class_table().class_of(u32::from(b'a')), CLASS_LETTER);
assert_eq!(class_table().class_of(u32::from(b'7')), CLASS_NUMBER);
assert_eq!(class_table().class_of(u32::from(b' ')), CLASS_SPACE);
assert_eq!(class_table().class_of(u32::from(b'\'')), 0);
assert_eq!(class_table().class_of(0x00A0), CLASS_SPACE);
assert_eq!(class_table().class_of(0x0301), 0);
assert_eq!(class_table().class_of(0x1F600), 0);
assert_eq!(class_table().class_of(0x1D7CE), CLASS_NUMBER);
assert_eq!(class_table().class_of(0x4E2D), CLASS_LETTER);
}
#[test]
fn range_table_is_sorted_and_disjoint() {
let table = class_table();
let triples = table.ranges().chunks_exact(3);
assert_eq!(triples.len(), table.range_count() as usize);
let mut previous_end = 0x7Fu32;
for triple in triples {
let (low, high, bits) = (triple[0], triple[1], triple[2]);
assert!(low > previous_end, "range {low:#X} overlaps {previous_end:#X}");
assert!(low <= high, "range {low:#X}..{high:#X} is inverted");
assert_ne!(bits, 0, "range {low:#X}..{high:#X} stores an empty class");
assert!(bits <= CLASS_ANY, "range {low:#X}..{high:#X} has unknown bits");
previous_end = high;
}
assert!(previous_end <= 0x0010_FFFF);
}
#[test]
fn rounds_cover_every_position() {
for len in [0u32, 1, 2, 3, 255, 256, 257, 1023, 1024, 65_535] {
let shape = BoundaryShape::new(len);
let reach = 1u64 << shape.rounds();
assert!(
reach >= u64::from(shape.positions()),
"{} rounds reach {reach}, short of {} positions",
shape.rounds(),
shape.positions()
);
assert!(
(1u64 << (shape.rounds() - 1)) < u64::from(shape.positions()).max(2),
"{} rounds is one more than needed for {len} bytes",
shape.rounds()
);
}
}
#[test]
fn lift_never_probes_past_the_padded_table() {
for count in [1u32, 2, 3, 7, 8, 9, 1000, 2358] {
let levels = lift_levels(count);
let slots = range_slots(levels);
assert!(slots >= count, "{levels} levels give {slots} slots for {count} ranges");
let mut highest = 0u32;
for level in (0..levels).rev() {
highest += 1u32 << level;
}
assert_eq!(highest, slots, "the lift can reach slot {highest} of {slots}");
}
}
#[test]
fn oversized_shape_lowers_to_a_trap() {
let program = boundary_program(BoundaryShape::new(MAX_INPUT_BYTES + 1));
assert!(
program.buffers().iter().any(|decl| decl.name() == OFFSETS_BUFFER),
"the trap must still declare the offsets buffer so callers bind the same slot"
);
assert!(
output_slot(&program, OFFSETS_BUFFER).is_some(),
"the trap's offsets buffer must be readable back"
);
}
}