Ada 4.1.1
Fast spec-compliant URL parser
Loading...
Searching...
No Matches
table_store.hpp
Go to the documentation of this file.
1// Runtime store for compressed Unicode/IDNA tables.
2// Large tables are DEFLATE-compressed (read-only) and expanded once on first
3// use into a heap buffer so the working set does not bloat the on-disk binary.
4// Hot-path lookups use the same O(1) multi-stage layout as the pre-compression
5// code; compression only affects on-disk size and one-time init.
6//
7// Thread-safe without mutex: atomic CAS + spin-wait. ensure_tables() returns
8// false if initialization fails. A corrupt blob stays failed for the process.
9// An allocation failure is not latched: a later call tries again. Callers
10// must treat a false return as a hard error and not touch table pointers.
11#pragma once
12
13#include "raw_inflate.hpp"
14#include "table_blob.inc"
15
16#include <atomic>
17#include <bit>
18#include <cstdint>
19#include <cstddef>
20#include <new>
21
22namespace ada::idna {
23
24// table_blob.inc is packed little-endian (see scripts/pack_tables.py). After
25// inflate the multi-byte sections must be converted to host endianness so
26// big-endian platforms (s390x) can load uint16_t/uint32_t/uint64_t natively.
27// CRC is checked on the raw little-endian payload before any conversion.
28namespace detail {
29
30template <typename T>
31inline void bswap_inplace(T* data, size_t count) noexcept {
32 if constexpr (std::endian::native == std::endian::little) {
33 (void)data;
34 (void)count;
35 return;
36 }
37 for (size_t i = 0; i < count; ++i) {
38 if constexpr (sizeof(T) == 2) {
39#if defined(__GNUC__) || defined(__clang__)
40 data[i] =
41 static_cast<T>(__builtin_bswap16(static_cast<uint16_t>(data[i])));
42#else
43 const auto v = static_cast<uint16_t>(data[i]);
44 data[i] = static_cast<T>(static_cast<uint16_t>((v >> 8) | (v << 8)));
45#endif
46 } else if constexpr (sizeof(T) == 4) {
47#if defined(__GNUC__) || defined(__clang__)
48 data[i] =
49 static_cast<T>(__builtin_bswap32(static_cast<uint32_t>(data[i])));
50#else
51 auto v = static_cast<uint32_t>(data[i]);
52 v = ((v & 0x000000FFu) << 24) | ((v & 0x0000FF00u) << 8) |
53 ((v & 0x00FF0000u) >> 8) | ((v & 0xFF000000u) >> 24);
54 data[i] = static_cast<T>(v);
55#endif
56 } else if constexpr (sizeof(T) == 8) {
57#if defined(__GNUC__) || defined(__clang__)
58 data[i] =
59 static_cast<T>(__builtin_bswap64(static_cast<uint64_t>(data[i])));
60#else
61 auto v = static_cast<uint64_t>(data[i]);
62 v = ((v & 0x00000000000000FFull) << 56) |
63 ((v & 0x000000000000FF00ull) << 40) |
64 ((v & 0x0000000000FF0000ull) << 24) |
65 ((v & 0x00000000FF000000ull) << 8) |
66 ((v & 0x000000FF00000000ull) >> 8) |
67 ((v & 0x0000FF0000000000ull) >> 24) |
68 ((v & 0x00FF000000000000ull) >> 40) |
69 ((v & 0xFF00000000000000ull) >> 56);
70 data[i] = static_cast<T>(v);
71#endif
72 } else {
73 static_assert(sizeof(T) == 2 || sizeof(T) == 4 || sizeof(T) == 8);
74 }
75 }
76}
77
78// Convert every multi-byte section of the inflated little-endian blob to host
79// order. Single-byte sections are left unchanged. Safe no-op on little-endian.
80inline void convert_table_blob_to_host_endian(uint8_t* buffer) noexcept {
81 if constexpr (std::endian::native == std::endian::little) {
82 (void)buffer;
83 return;
84 }
85 auto u16 = [&](size_t off, size_t count) {
86 bswap_inplace(reinterpret_cast<uint16_t*>(buffer + off), count);
87 };
88 auto u32 = [&](size_t off, size_t count) {
89 bswap_inplace(reinterpret_cast<uint32_t*>(buffer + off), count);
90 };
91 auto u64 = [&](size_t off, size_t count) {
92 bswap_inplace(reinterpret_cast<uint64_t*>(buffer + off), count);
93 };
94
110}
111
112} // namespace detail
113
114// --- Blob layout invariants --------------------------------------------------
115static_assert(table_blob::count_decomposition_index == 4352);
116static_assert(table_blob::count_ccc_index == 4352);
117static_assert(table_blob::count_composition_index == 4352);
121static_assert(table_blob::count_ccc_block ==
129static_assert(
135static_assert(table_blob::count_id_start_flat ==
139static_assert(table_blob::off_idna_stage1 % alignof(uint16_t) == 0);
140static_assert(table_blob::off_idna_stage2 % alignof(uint16_t) == 0);
141static_assert(table_blob::off_idna_bool_blocks % alignof(uint64_t) == 0);
142static_assert(table_blob::off_decomposition_block % alignof(uint16_t) == 0);
143static_assert(table_blob::off_decomposition_data % alignof(char32_t) == 0);
144static_assert(table_blob::off_composition_block % alignof(uint16_t) == 0);
145static_assert(table_blob::off_composition_data % alignof(char32_t) == 0);
146static_assert(table_blob::off_id_continue_flat % alignof(uint32_t) == 0);
147static_assert(table_blob::off_id_start_flat % alignof(uint32_t) == 0);
148static_assert(table_blob::off_dir_start % alignof(uint32_t) == 0);
149static_assert(table_blob::off_dir_final % alignof(uint32_t) == 0);
150static_assert(table_blob::off_combining_flat % alignof(uint32_t) == 0);
151static_assert(table_blob::off_joining_start % alignof(uint32_t) == 0);
152static_assert(table_blob::off_joining_final % alignof(uint32_t) == 0);
154
155// Every section must lie entirely inside the uncompressed buffer.
156#define ADA_IDNA_SECTION_IN_BOUNDS(off, count, width) \
157 static_assert((off) + (count) * (width) <= table_blob::uncompressed_size, \
158 #off " overflows uncompressed buffer")
201#undef ADA_IDNA_SECTION_IN_BOUNDS
202
203// --- Mapping -----------------------------------------------------------------
204inline const uint16_t* idna_stage1 = nullptr;
205inline const uint16_t* idna_stage2 = nullptr;
206inline const uint64_t* idna_bool_blocks = nullptr;
207inline const uint8_t* idna_utf8_mappings = nullptr;
208
209// --- Normalization (O(1) multi-stage) ----------------------------------------
210inline const uint8_t* decomposition_index = nullptr;
211inline const uint16_t* decomposition_block_flat = nullptr;
212inline const char32_t* decomposition_data = nullptr;
213inline const uint8_t* ccc_index = nullptr;
214inline const uint8_t* ccc_block_flat = nullptr;
215inline const uint8_t* composition_index = nullptr;
216inline const uint16_t* composition_block_flat = nullptr;
217inline const char32_t* composition_data = nullptr;
218
219// --- Identifier --------------------------------------------------------------
220// Pointer-to-array alias. CF17 vs CF22 disagree on spacing inside (*)[2].
221// clang-format off
222using range_pair_ptr = const uint32_t(*)[2];
223// clang-format on
224inline range_pair_ptr id_continue = nullptr;
225inline range_pair_ptr id_start = nullptr;
226
227// --- Validity (const SoA) ----------------------------------------------------
228inline const uint32_t* dir_start = nullptr;
229inline const uint32_t* dir_final = nullptr;
230inline const uint8_t* dir_value = nullptr;
231inline range_pair_ptr combining_ranges = nullptr;
232inline const uint32_t* joining_start = nullptr;
233inline const uint32_t* joining_final = nullptr;
234inline const uint8_t* joining_value = nullptr;
235
236inline constexpr size_t id_continue_count = table_blob::id_continue_count;
237inline constexpr size_t id_start_count = table_blob::id_start_count;
238inline constexpr size_t dir_table_count = table_blob::dir_table_count;
240inline constexpr size_t combining_range_count =
242inline constexpr size_t idna_utf8_mappings_size =
244inline constexpr size_t decomposition_data_size =
246inline constexpr size_t composition_data_size =
248
249inline constexpr size_t kDecompBlockCols =
251inline constexpr size_t kCccBlockCols = table_blob::ccc_block_cols; // 256
252inline constexpr size_t kCompBlockCols =
255inline constexpr size_t kCccBlockRows = table_blob::ccc_block_rows;
256inline constexpr size_t kCompBlockRows = table_blob::composition_block_rows;
257
258// Init state: 0=uninit, 1=in progress, 2=ready, 3=failed.
259inline constexpr uint8_t kTablesUninit = 0;
260inline constexpr uint8_t kTablesInProgress = 1;
261inline constexpr uint8_t kTablesReady = 2;
262inline constexpr uint8_t kTablesFailed = 3;
263
264inline std::atomic<uint8_t> tables_init_state{kTablesUninit};
265// Process-lifetime allocation published only by the winning init thread.
266// Never freed: shared read-only data for the process. Do not dlclose a DSO
267// that owns this buffer while other code may still call into ada::idna.
268inline uint8_t* tables_buffer = nullptr;
269
270// Cap spin-wait so a stuck peer cannot hang the process forever.
271inline constexpr uint64_t kTablesSpinLimit = 1'000'000'000ull;
272
273// ISO HDLC / zlib CRC-32 of the uncompressed table payload.
274[[nodiscard]] inline uint32_t crc32_ieee(const uint8_t* data,
275 size_t len) noexcept {
276 uint32_t c = 0xFFFFFFFFu;
277 for (size_t i = 0; i < len; ++i) {
278 c ^= data[i];
279 for (int k = 0; k < 8; ++k) {
280 const uint32_t mask = 0u - (c & 1u);
281 c = (c >> 1) ^ (0xEDB88320u & mask);
282 }
283 }
284 return ~c;
285}
286
287[[nodiscard]] inline bool tables_are_ready() noexcept {
288 return tables_init_state.load(std::memory_order_acquire) == kTablesReady;
289}
290
291// Returns true only when all table pointers are safe to use.
292[[nodiscard]] inline bool ensure_tables() noexcept {
293 uint8_t state = tables_init_state.load(std::memory_order_acquire);
294 if (state == kTablesReady) {
295 return true;
296 }
297 if (state == kTablesFailed) {
298 return false;
299 }
300
301 uint8_t expected = kTablesUninit;
302 if (tables_init_state.compare_exchange_strong(expected, kTablesInProgress,
303 std::memory_order_acq_rel,
304 std::memory_order_acquire)) {
305 uint8_t* buffer = new (std::nothrow) uint8_t[table_blob::uncompressed_size];
306 if (buffer == nullptr) {
307 // Leave the state uninitialized so a later call can retry. A corrupt
308 // blob (below) is permanent; running out of memory may not be.
309 // LCOV_EXCL_START
310 tables_init_state.store(kTablesUninit, std::memory_order_release);
311 return false;
312 // LCOV_EXCL_STOP
313 }
314
320 delete[] buffer;
321 tables_init_state.store(kTablesFailed, std::memory_order_release);
322 return false;
323 }
324
325 // LE payload verified; convert multi-byte fields for big-endian hosts.
327
328 auto at = [&](size_t off) noexcept -> const uint8_t* {
329 return buffer + off;
330 };
331
332 // Publish all non-atomic pointers before READY. Waiters synchronize via
333 // acquire on tables_init_state and then observe these writes.
335 reinterpret_cast<const uint16_t*>(at(table_blob::off_idna_stage1));
337 reinterpret_cast<const uint16_t*>(at(table_blob::off_idna_stage2));
339 reinterpret_cast<const uint64_t*>(at(table_blob::off_idna_bool_blocks));
341
343 decomposition_block_flat = reinterpret_cast<const uint16_t*>(
345 decomposition_data = reinterpret_cast<const char32_t*>(
350 composition_block_flat = reinterpret_cast<const uint16_t*>(
353 reinterpret_cast<const char32_t*>(at(table_blob::off_composition_data));
354
357 id_start =
358 reinterpret_cast<range_pair_ptr>(at(table_blob::off_id_start_flat));
359
360 dir_start =
361 reinterpret_cast<const uint32_t*>(at(table_blob::off_dir_start));
362 dir_final =
363 reinterpret_cast<const uint32_t*>(at(table_blob::off_dir_final));
366 reinterpret_cast<range_pair_ptr>(at(table_blob::off_combining_flat));
368 reinterpret_cast<const uint32_t*>(at(table_blob::off_joining_start));
370 reinterpret_cast<const uint32_t*>(at(table_blob::off_joining_final));
372
373 tables_buffer = buffer;
374 tables_init_state.store(kTablesReady, std::memory_order_release);
375 return true;
376 }
377
378 // Another thread owns init (or finished between our loads).
379 for (uint64_t spins = 0; spins < kTablesSpinLimit; ++spins) {
380 state = tables_init_state.load(std::memory_order_acquire);
381 if (state == kTablesReady) {
382 return true;
383 }
384 // Failed is permanent. Uninit means the peer gave up after a failed
385 // allocation: do not spin, the next call can take the init slot. One
386 // comparison, same shape as the old Failed check, so this wait loop does
387 // not grow the unity translation unit.
388 // LCOV_EXCL_START
389 if (state != kTablesInProgress) {
390 return false;
391 }
392 // LCOV_EXCL_STOP
393#if defined(__x86_64__) || defined(_M_X64) || defined(__i386__) || \
394 defined(_M_IX86)
395#if defined(__GNUC__) || defined(__clang__)
396 __builtin_ia32_pause();
397#endif
398#elif defined(__aarch64__) || defined(_M_ARM64)
399#if defined(__GNUC__) || defined(__clang__)
400 asm volatile("yield" ::: "memory");
401#endif
402#endif
403 }
404 // Timed out waiting for a peer - treat as failure rather than hang.
405 return false;
406}
407
408// O(1) multi-stage accessors. Block indices from the tables are uint8_t and
409// theoretically can be out of range if the blob is corrupt; clamp to a valid
410// empty/default row (index 0) instead of reading OOB.
411inline const uint16_t* decomposition_block_row(uint8_t bi) noexcept {
412 if (bi >= kDecompBlockRows) {
413 bi = 0;
414 }
415 return decomposition_block_flat + static_cast<size_t>(bi) * kDecompBlockCols;
416}
417
418inline const uint8_t* ccc_block_row(uint8_t bi) noexcept {
419 if (bi >= kCccBlockRows) {
420 bi = 0;
421 }
422 return ccc_block_flat + static_cast<size_t>(bi) * kCccBlockCols;
423}
424
425inline const uint16_t* composition_block_row(uint8_t bi) noexcept {
426 if (bi >= kCompBlockRows) {
427 bi = 0;
428 }
429 return composition_block_flat + static_cast<size_t>(bi) * kCompBlockCols;
430}
431
432} // namespace ada::idna
uint64_t u64
uint16_t u16
uint32_t u32
#define ADA_IDNA_SECTION_IN_BOUNDS(off, count, width)
size_t inflate_raw(const uint8_t *src, size_t src_len, uint8_t *dst, size_t dst_cap)
Definition ada_idna.cpp:395
void bswap_inplace(T *data, size_t count) noexcept
void convert_table_blob_to_host_endian(uint8_t *buffer) noexcept
constexpr size_t off_decomposition_data
Definition ada_idna.cpp:560
constexpr size_t count_decomposition_index
Definition ada_idna.cpp:557
constexpr size_t combining_range_count
Definition ada_idna.cpp:545
constexpr size_t count_composition_block
Definition ada_idna.cpp:569
constexpr size_t off_joining_final
Definition ada_idna.cpp:586
constexpr size_t off_joining_value
Definition ada_idna.cpp:588
constexpr size_t count_dir_start
Definition ada_idna.cpp:577
constexpr size_t id_continue_count
Definition ada_idna.cpp:542
constexpr size_t decomposition_block_rows
Definition ada_idna.cpp:536
constexpr size_t count_composition_index
Definition ada_idna.cpp:567
constexpr size_t count_decomposition_data
Definition ada_idna.cpp:561
constexpr size_t count_dir_final
Definition ada_idna.cpp:579
constexpr size_t id_start_count
Definition ada_idna.cpp:543
constexpr size_t count_joining_start
Definition ada_idna.cpp:585
constexpr size_t composition_block_cols
Definition ada_idna.cpp:541
constexpr size_t off_dir_value
Definition ada_idna.cpp:580
constexpr size_t count_idna_bool_blocks
Definition ada_idna.cpp:553
constexpr size_t off_dir_final
Definition ada_idna.cpp:578
constexpr size_t off_composition_block
Definition ada_idna.cpp:568
constexpr size_t count_id_continue_flat
Definition ada_idna.cpp:573
constexpr size_t count_joining_value
Definition ada_idna.cpp:589
constexpr size_t off_decomposition_block
Definition ada_idna.cpp:558
constexpr size_t off_ccc_block
Definition ada_idna.cpp:564
constexpr size_t joining_table_count
Definition ada_idna.cpp:546
constexpr size_t count_combining_flat
Definition ada_idna.cpp:583
constexpr size_t off_combining_flat
Definition ada_idna.cpp:582
constexpr size_t off_ccc_index
Definition ada_idna.cpp:562
constexpr size_t count_decomposition_block
Definition ada_idna.cpp:559
constexpr size_t count_idna_utf8_mappings
Definition ada_idna.cpp:555
constexpr size_t ccc_block_rows
Definition ada_idna.cpp:538
constexpr size_t decomposition_block_cols
Definition ada_idna.cpp:537
constexpr size_t off_id_continue_flat
Definition ada_idna.cpp:572
constexpr size_t off_composition_data
Definition ada_idna.cpp:570
constexpr size_t off_idna_utf8_mappings
Definition ada_idna.cpp:554
constexpr size_t off_idna_bool_blocks
Definition ada_idna.cpp:552
constexpr size_t count_joining_final
Definition ada_idna.cpp:587
constexpr size_t count_dir_value
Definition ada_idna.cpp:581
constexpr size_t off_idna_stage1
Definition ada_idna.cpp:548
constexpr size_t count_id_start_flat
Definition ada_idna.cpp:575
constexpr size_t compressed_size
Definition ada_idna.cpp:534
constexpr size_t off_decomposition_index
Definition ada_idna.cpp:556
constexpr uint8_t compressed[]
Definition ada_idna.cpp:590
constexpr size_t ccc_block_cols
Definition ada_idna.cpp:539
constexpr size_t off_joining_start
Definition ada_idna.cpp:584
constexpr size_t count_composition_data
Definition ada_idna.cpp:571
constexpr size_t off_idna_stage2
Definition ada_idna.cpp:550
constexpr size_t off_dir_start
Definition ada_idna.cpp:576
constexpr uint32_t uncompressed_crc32
Definition ada_idna.cpp:535
constexpr size_t dir_table_count
Definition ada_idna.cpp:544
constexpr size_t count_idna_stage2
Definition ada_idna.cpp:551
constexpr size_t composition_block_rows
Definition ada_idna.cpp:540
constexpr size_t count_ccc_index
Definition ada_idna.cpp:563
constexpr size_t off_composition_index
Definition ada_idna.cpp:566
constexpr size_t off_id_start_flat
Definition ada_idna.cpp:574
constexpr size_t uncompressed_size
Definition ada_idna.cpp:533
constexpr size_t count_idna_stage1
Definition ada_idna.cpp:549
constexpr size_t count_ccc_block
Definition ada_idna.cpp:565
bool tables_are_ready() noexcept
constexpr size_t kCccBlockRows
constexpr uint64_t kTablesSpinLimit
constexpr uint8_t kTablesUninit
constexpr size_t kCompBlockRows
constexpr size_t id_continue_count
const uint8_t * ccc_block_row(uint8_t bi) noexcept
constexpr size_t kDecompBlockCols
const uint8_t * ccc_index
const uint8_t * dir_value
const char32_t * decomposition_data
const uint32_t * joining_final
const uint8_t * decomposition_index
const uint16_t * composition_block_flat
range_pair_ptr id_continue
const uint16_t * idna_stage2
const uint8_t * joining_value
const uint32_t * joining_start
constexpr uint8_t kTablesFailed
constexpr size_t combining_range_count
const uint8_t * ccc_block_flat
range_pair_ptr combining_ranges
constexpr size_t kCompBlockCols
constexpr size_t joining_table_count
const uint16_t * decomposition_block_flat
const uint16_t * idna_stage1
const char32_t * composition_data
const uint32_t(*)[2] range_pair_ptr
bool ensure_tables() noexcept
range_pair_ptr id_start
constexpr size_t dir_table_count
const uint8_t * composition_index
constexpr size_t kCccBlockCols
constexpr size_t decomposition_data_size
const uint16_t * decomposition_block_row(uint8_t bi) noexcept
uint32_t crc32_ieee(const uint8_t *data, size_t len) noexcept
const uint32_t * dir_final
uint8_t * tables_buffer
std::atomic< uint8_t > tables_init_state
constexpr size_t idna_utf8_mappings_size
const uint8_t * idna_utf8_mappings
const uint16_t * composition_block_row(uint8_t bi) noexcept
const uint64_t * idna_bool_blocks
constexpr uint8_t kTablesReady
const uint32_t * dir_start
constexpr size_t id_start_count
constexpr size_t composition_data_size
constexpr size_t kDecompBlockRows
constexpr uint8_t kTablesInProgress
state
States in the URL parsing state machine.
Definition state.h:27