- Generated by
1.9.8
|
dasmig-core 1.2.0
Shared random engine, distributions and data tiers for the dasmig generator libraries
|
This guide covers every part of dasmig-core and specifies its random algorithms exactly. For a quick overview, see the README. For the API reference, run doxygen Doxyfile from the repository root and open doc/api/html/index.html.
Everything below that turns a seed into values is part of the contract: for a given core major version, a seed gives the same bits on every supported compiler, standard library and platform. Changing any algorithm, constant or the number of engine values a function consumes is a major version change.
Each library copies dasmig/core.hpp and dasmig/core/ next to its own header and checks the version in use:
When two libraries are included in one translation unit, the include guards keep only the first copy of the core. DASMIG_CORE_REQUIRE turns a silent mismatch into a compile error.
The dasmig::dataset enum (lite, full) lives in the core. The core also defines DASMIG_DATASET_DEFINED, so library headers released before the core skip their own copy.
dasmig::sex (male, female) lives in the core, so every library that takes or returns a sex uses one type. core::sex_name(sex) gives the lower-case name used in data files and JSON ("male", "female"), and core::parse_sex(text) reads it back, returning an empty optional for anything else. Matching is exact: "Male" and "m" are rejected. Both are constexpr.
Like dataset, the enum sits behind a guard (DASMIG_SEX_DEFINED), so library headers released before core 1.2 skip their own identical copy when included together.
core::is_alpha2(text) is true for exactly two capital ASCII letters ("BR", not "br" or "BRA"). It checks the shape only, not whether the code is assigned or whether a library has data for it. core::unknown_country_error(code) returns the std::invalid_argument libraries throw for a code they have no data for; its message is Unknown country code: <code>.
dasmig::core::rng is xoshiro256** (Blackman and Vigna, 2018) with 256 bits of state.
rng{seed} and seed(s) fill the four state words with four consecutive outputs of SplitMix64 started at s. Every 64-bit seed is valid.result = rotl(s1 * 5, 7) * 9, then the standard xoshiro256 state update.seed()** returns the seed the engine was last seeded with; constructing an engine from it replays the sequence.unseed()** and rng::from_entropy() take a seed from std::random_device. Use them only for the instance engine behind non-seeded calls; anything that must replay takes a seed.rng satisfies std::uniform_random_bit_generator, but use the core's distributions with it: the std:: ones differ between standard libraries.
split(label) and split(index) derive a child engine from the parent's seed (not its current state), so the stream a part of a generator receives does not change when another part draws more or fewer values.
| Call | Child seed |
|---|---|
split(label) | mix(seed ^ mix(fnv1a64(label))) |
split(index) | mix(seed ^ mix(index ^ 0x6a09e667f3bcc909)) |
mix is the SplitMix64 output function. fnv1a64 hashes the label's bytes: pass UTF-8, because a std::wstring has different bytes on Windows (UTF-16) and elsewhere (UTF-32). child_seed(...) returns the seed without building the engine, for storing in a result's replay signature.
Each function takes the engine by reference. Unless noted, it consumes exactly the number of engine values given.
| Function | Algorithm | Values consumed |
|---|---|---|
bounded(r, n) | Lemire 2019: x = r(); if low64(x * n) < n, redraw while low64(x * n) < (2^64 - n) mod n; return high64(x * n) | 1, rarely more |
uniform_int(r, lo, hi) | lo + bounded(r, hi - lo + 1) in 64-bit unsigned arithmetic; the full 64-bit range returns r() | 1, rarely more |
uniform01(r) | (r() >> 11) * 2^-53, in [0, 1) | 1 |
uniform_real(r, lo, hi) | lo + (hi - lo) * uniform01(r); if that rounds to hi, the largest double below hi; lo when lo == hi | 1 |
bernoulli(r, p) | uniform01(r) < p | 1 |
normal(r, mean, sd) | Marsaglia polar: u = 2 * uniform01(r) - 1, v likewise, until s = u*u + v*v is in (0, 1); return mean + sd * (u * sqrt((-2 * log(s)) / s)). The variate from v is discarded | 2 per attempt (2.55 on average) |
lognormal(r, mu, sigma) | exp(normal(r, mu, sigma)) | as normal |
discrete{weights}(r) | Cumulative sums added left to right; the first index whose sum exceeds uniform01(r) * total; zero weights are never chosen | 1 |
shuffle(r, range) | Fisher-Yates from the end: for i = n-1 down to 1, swap i with bounded(r, i + 1) | n - 1, rarely more |
sample_indices(r, n, k) | Partial Fisher-Yates from the front over 0..n-1: for i = 0 to k-1, swap i with i + bounded(r, n - i); the first k | k, rarely more |
pick(r, range) | range[bounded(r, size)]; returns a reference | 1, rarely more |
log and exp above are the core's own (next section).
std::exp and std::log are not required to be correctly rounded, and glibc, the MSVC runtime, Apple's libm and Emscripten's musl differ in the last bit for some inputs. core::math::exp and core::math::log use only +, -, *, /, sqrt, floor, frexp and ldexp, which IEEE 754 defines exactly, so they give the same bits everywhere.
k = floor(x * log2(e) + 0.5), r = (x - k * ln2_hi) - k * ln2_lo, a degree-13 Taylor polynomial in r by Horner's rule, scaled by 2^k. Measured within 1 ulp of the Windows C runtime; the tests allow 2 against any platform libm.x = m * 2^e with m in [sqrt(1/2), sqrt(2)), s = (m - 1) / (m + 1), log(m) = s * (2 + 2/3 s^2 + ... + 2/19 s^18) by Horner's rule in s^2, plus e * ln2_hi + e * ln2_lo. Measured within 3 ulp of the Windows C runtime; the tests allow 4.They are accurate enough for sampling. They are not general replacements for <cmath>.
Bit-identical results also need every operation rounded on its own:
a * b + c into one instruction (GCC in GNU mode, clang with -ffp-contract=fast, ARM64 targets). Pragmas do not stop this reliably, so each product that feeds an addition in the core passes through core::math::fenced(), an empty optimization barrier. Use it the same way in library code that computes with doubles before a result is stored.-ffast-math, /fp:fast and /fp:contract are refused at compile time.FLT_EVAL_METHOD must be 0 (SSE2 on 32-bit x86)./fp:precise contracted.The tests pass bit for bit at -O0, -O2 and -O3 -march=native -ffp-contract=fast with clang, and with MSVC at /O2 and /O2 /arch:AVX2.
Every library's resources/ and every extension layer use one TSV format, read by core::tsv_document:
parse or load.# are skipped.get<T> accepts integers, doubles (finite, decimal or scientific, parsed exactly so every platform gets the same bits), bool (1, 0, true, false), std::string and std::string_view. Errors are core::tsv_error, whose message reads ‘file:line: column 'name’: problem;source(),line()andcolumn()` give the parts.
content_hash() hashes the parsed columns and cells, not the bytes, so the same data checked out with LF or CRLF line ends, with or without a BOM or comments, hashes the same.
Rows are light views. They stay valid while the document, or any copy of it, is alive.
core::layered_table assembles a table from a base layer and extension layers in the same TSV format, so users can add to the shipped data, change it or replace it without touching it.
| Mode | Effect |
|---|---|
add | New keys only; a key already loaded is an error |
override (default) | A row replaces the loaded row with the same key, in its position; new keys are appended |
replace | The layer replaces every row loaded before it |
disabled set to 1 removes its key (override and replace modes).disabled. Columns the table does not know are ignored and listed in the layer's warnings.disabled values, add-mode clashes, and the library's own row check passed as the third argument to extend. If anything fails, the table is unchanged and tsv_error says where.layers() lists each layer's source, mode, row counts (added, replaced, removed) and warnings. data_hash() combines the layers' content hashes and modes, in order. A replace layer starts the record again, since nothing before it affects the data: reloading the same base gives the same hash.A library typically keeps one layered table per data file, validates rows with the same code that reads them, and rebuilds its typed data from rows() after each extend.
A library's data lives in resources/lite/ and resources/full/. The core finds it on disk, or reads it from the program itself when it was compiled in.
On disk. core::find_resources(library, marker) returns the first of these directories (relative to the working directory, or to a base you pass) that contains the marker file:
resources../resources<library>/resources../<library>/resourcesThese cover running from the repository, from its build/ directory, and from a parent directory holding several libraries side by side. The marker (for example lite/biodata.tsv) keeps one library from picking up another's resources/.
Compiled in. scripts/embed.py turns a tier into a header:
The header defines dasmig::embedded::biodatagen::files. It is plain ASCII C++: bytes outside printable ASCII are octal escapes, so it compiles the same with or without /utf-8. Content is split into chunks below MSVC's string-literal limits, and CRLF is written as LF, so the header is the same from any checkout. City-generator's 3.1 MB lite tier becomes a 4 MB header that clang compiles in about 3 s and MSVC in about 7 s.
Loading. core::load_resource(path, embedded, root) reads the embedded copy when there is one, otherwise root / path, otherwise returns empty:
The embedded and on-disk copies have the same content_hash(), so a WebAssembly build with compiled-in data replays the same seeds as a native build that reads files.
core::weighted_table<T> holds values with weights. A pick uses the same algorithm as discrete and consumes one engine value.
try_pick returns nullptr when every adjusted weight is 0; it still consumes one value, so later draws do not shift.pick_distinct_indices(r, k[, adjust]) draws k times without repeating an entry. It consumes exactly k values and returns fewer than k entries when fewer are eligible.core::json_writer builds one compact JSON document. It places commas itself and throws std::logic_error on misuse (a value without a key in an object, unbalanced ends, a second top-level value).
Numbers are written with std::to_chars, the shortest text that reads back to the same double, so the JSON is identical on every platform. NaN and infinity are rejected. Strings must be UTF-8 and are escaped as RFC 8259 requires.
JavaScript numbers are doubles, so integers above 2^53 lose precision there. Write 64-bit values such as seeds as strings.
A batch is count results from one batch seed. Item i is exactly what the single-call getter returns for core::item_seed(batch_seed, i), which is rng{batch_seed}.split(i).seed(). So an item replays on its own, a range is computed directly (first = 1000 starts at item 1000), two batches of 1,000 equal one of 2,000, and the result does not depend on how the work is divided.
core::batch_options has count, first (default 0), threads (default 1; 0 means the hardware count) and unique. The make callable runs on several threads, so it must be callable concurrently; the libraries' const seeded getters are. If a call throws, the exception for the lowest failing index is rethrown, whatever the thread count. Without threads (Emscripten without -pthread) the batch runs serially with the same result.
core::for_each_batch(options, batch_seed, make, sink) calls sink(index, item) in index order on the calling thread and keeps only a few thousand items per thread alive, so a batch of millions does not have to fit in memory. index includes first.
Items are generated, then checked in index order. An item whose key was already produced earlier in the call is generated again with core::attempt_seed(batch_seed, i, k) (attempt 0 is the plain item seed, so items that do not collide equal the single call; attempt k > 0 is item_seed(item_seed(batch_seed, i), k)) until it is new. If max_attempts run out, the call throws std::runtime_error naming the item, instead of looping. The result is the same for any thread count. Uniqueness holds within one call, not across two concatenated batches. The rule is checked against the item type and rejected with std::invalid_argument if it was made for another.
Both are sinks for results that have to_json(). csv_writer flattens each result's JSON into dotted columns (birth.date, city.name) with core::flatten_json: strings are unescaped, null is an empty cell, and an array (or an empty nested object) is one cell holding its JSON text. The header comes from the first record; later records are matched to it by column name (a missing column is empty, an extra one is dropped). Fields with a comma, quote or line break are quoted, and rows end with \n.
core::seed_signature is what a result records so it can be generated again: the call seed and the hash of the data it came from.
A seed reproduces a result only with the same data. When data differs from the data loaded now, a library can report the mismatch instead of returning a different result silently. parse also accepts a lone 16-digit seed (data 0, meaning "not recorded").
The core works in UTF-8. Libraries with a std::wstring API convert at the boundary with core::to_utf8 and core::from_utf8. They handle UTF-16 wchar_t (Windows) and UTF-32 (elsewhere), so the bytes are the same everywhere; that matters for split labels and for hashes. core::is_utf8 and core::utf8_invalid_offset check input.
The pattern every library follows:
Splitting per field keeps a result's other fields unchanged when one field's algorithm changes or a field is added.
tests/kat_vectors.hpp is generated by scripts/reference.py (make kat), an independent Python implementation of every algorithm. Python floats are IEEE doubles without fused operations, so agreement is bit for bit. The script first checks its engine against the published SplitMix64 and xoshiro256** vectors.exp and log against the platform libm.| Call | Throws | When |
|---|---|---|
bounded | std::invalid_argument | n == 0 |
uniform_int | std::invalid_argument | lo > hi |
uniform_real | std::invalid_argument | a bound is not finite, lo > hi, or hi - lo overflows |
bernoulli | std::invalid_argument | p not in [0, 1] or NaN |
normal, lognormal | std::invalid_argument | mean or sd not finite, or sd negative |
discrete | std::invalid_argument | no weights, a weight negative or not finite, sum 0 or not finite |
discrete::probability | std::out_of_range | index out of range |
sample_indices | std::invalid_argument | k > n |
pick | std::invalid_argument | empty range |
weighted_table::add, pick, try_pick | std::invalid_argument | a weight (base or adjusted) negative or not finite; pick when nothing is eligible |
tsv_document::parse, load | core::tsv_error | unreadable file, invalid UTF-8, no header, an unnamed or repeated column, a row with too many cells |
tsv_row::get | core::tsv_error | no such column, empty cell, text that is not a valid value |
layered_table::extend | core::tsv_error | see Extending Data above; the table is unchanged |
json_writer | std::logic_error / std::invalid_argument | misuse / NaN, infinity or invalid UTF-8 |
seed_signature::parse | std::invalid_argument | not <16 hex> or <16 hex>-<16 hex> |
from_utf8, to_utf8 | std::invalid_argument | malformed UTF-8 / unpaired surrogate |
unknown_country_error | returns std::invalid_argument | the caller throws it for a country code with no data |
1.9.8