From e821d617802ebbfff756844e4d9720342fc78a4e Mon Sep 17 00:00:00 2001 From: "Claudius \"keldu\" Holeksa" Date: Fri, 13 Nov 2026 14:12:49 +0100 Subject: Swarm POC --- modules/core/c++/abstract/encode.hpp | 19 ++ modules/core/c++/abstract/forst.hpp | 615 +++++++++++++++++++++++++++++++++++ 2 files changed, 634 insertions(+) create mode 100644 modules/core/c++/abstract/forst.hpp (limited to 'modules/core/c++/abstract') diff --git a/modules/core/c++/abstract/encode.hpp b/modules/core/c++/abstract/encode.hpp index 571722a..1593656 100644 --- a/modules/core/c++/abstract/encode.hpp +++ b/modules/core/c++/abstract/encode.hpp @@ -25,8 +25,27 @@ struct NativeRaw { struct Json { static constexpr string_literal name = "enc::Json"; }; + +/** + * A packed little endian binary layout. See abstract/forst.hpp. + * + * Every value sits at a computable byte offset, so reading one member costs no + * decoding of the members before it. Fixed size schemas are inline; variable + * length ones spend their slot on dimensions plus an offset and put their bytes + * in a single dynamic layer after the static section. + */ +struct Forst { + static constexpr string_literal name = "enc::Forst"; +}; } // namespace enc +/** + * Declared here rather than in any one codec header so that an encoding does + * not have to include an unrelated one to specialise it. json.hpp and + * forst.hpp are siblings; neither should need the other. + */ +template class codec; + #ifndef KEL_LBM_DEFAULT_DATA_ENCODING #define KEL_LBM_DEFAULT_DATA_ENCODING ::kel::lbm::enc::Native #endif diff --git a/modules/core/c++/abstract/forst.hpp b/modules/core/c++/abstract/forst.hpp new file mode 100644 index 0000000..878ad58 --- /dev/null +++ b/modules/core/c++/abstract/forst.hpp @@ -0,0 +1,615 @@ +#pragma once + +#include "data.hpp" +#include "encode.hpp" +#include "schema.hpp" +#include "templates.hpp" + +#include +#include +#include +#include +#include +#include +#include +#include + +/** + * A packed little endian binary encoding for the schema system. + * + * Every value sits at a computable byte offset, so reading one member costs no + * decoding of the members before it. A value is a static section followed by a + * single dynamic layer. Little endian, byte packed, no alignment and no + * padding. Fixed size members sit inline; a variable length member spends its + * static slot on its dimensions as UInt64 each and then an offset, and its + * bytes live in the dynamic layer. + * + * An offset is measured from the byte just past the offset field that holds + * it, so resolving one is a single add with no layer base to track. + * + * This is forstio's Forst format reimplemented against lbm's own schema types + * (lbm's abstract/ is a private reimplementation of forstio's data/codec, so + * the two schema vocabularies are distinct C++ types and nothing could be + * shared), and deliberately cut down to **one dynamic layer**. That makes + * `String` and `Array` expressible while `Array` and + * `Array>` are not -- a static_assert says so rather than letting a + * nested dynamic value mis-encode. + * + * Chunk is not handled here: abstract/ sits below chunk.hpp and must not reach + * up into it. The Chunk layout lives in forst_chunk.hpp, which is what a result + * writer includes. + * + * One limitation shared with enc::Json: a bare `data, enc::Forst>` + * is ambiguous, because chunk.hpp already specialises + * `data, Encode>` for any encoding and neither specialisation is + * more specialised than the other. Wrap the chunk in a Struct, which is what a + * field always is in practice. + * + * Why it is worth having: a `Struct,Key>...>` is entirely + * fixed size, so its encoding *is* the packed field data, byte for byte, with + * no framing overhead and no serialisation pass. Results are written as ASCII + * VTK today, which measures 4-5x larger. + */ +namespace kel { +namespace lbm { + +namespace err { +/// The buffer ended before a value that the layout said was there. +struct forst_truncated { + static constexpr std::string_view description = "Truncated Forst buffer"; + static constexpr bool is_critical = false; +}; + +/// A length or offset in the buffer does not agree with the buffer itself. +struct forst_malformed { + static constexpr std::string_view description = "Malformed Forst buffer"; + static constexpr bool is_critical = false; +}; +} // namespace err + +namespace impl { + +/** + * The layout of a schema. + * + * `layers` is dynamicity depth: 0 for something wholly fixed size, and one + * more for each level of variable length nesting. `static_size` is the bytes + * the schema occupies in a static section -- for a variable length schema that + * is the size of its dimensions plus its offset, not of its contents. + */ +template struct forst_info { + static_assert(always_false, "This schema has no Forst layout"); +}; + +template <> struct forst_info { + static constexpr uint64_t layers = 0u; + static constexpr uint64_t static_size = 0u; +}; + +template <> struct forst_info { + static constexpr uint64_t layers = 0u; + static constexpr uint64_t static_size = 1u; +}; + +template struct forst_info> { + static constexpr uint64_t layers = 0u; + static constexpr uint64_t static_size = N; +}; + +/** + * Stored as its storage type, not its interface type. The whole point of a + * mixed precision member is that the narrow form is what occupies space. + */ +template +struct forst_info> { + static constexpr uint64_t layers = forst_info::layers; + static constexpr uint64_t static_size = forst_info::static_size; +}; + +/// Length, then offset. +template <> struct forst_info { + static constexpr uint64_t layers = 1u; + static constexpr uint64_t static_size = 16u; +}; + +template struct forst_info> { + static constexpr uint64_t layers = forst_info::layers; + static constexpr uint64_t static_size = + ct_multiply::value * forst_info::static_size; +}; + +template struct forst_info> { + static constexpr uint64_t layers = forst_info::layers; + static constexpr uint64_t static_size = + ct_multiply::value * forst_info::static_size; +}; + +/// One UInt64 per dimension, then the offset. +template struct forst_info> { + static constexpr uint64_t layers = 1u + forst_info::layers; + static constexpr uint64_t static_size = 8u * Dim + 8u; +}; + +template struct forst_info> { + template static constexpr uint64_t max_layers(){ + if constexpr (i < sizeof...(T)){ + using Ti = typename parameter_pack_type::type; + const uint64_t here = forst_info::layers; + const uint64_t rest = max_layers(); + return (here > rest) ? here : rest; + } + return 0u; + } + + template static constexpr uint64_t sum_static(){ + if constexpr (i < sizeof...(T)){ + using Ti = typename parameter_pack_type::type; + return forst_info::static_size + sum_static(); + } + return 0u; + } + + static constexpr uint64_t layers = max_layers<0u>(); + static constexpr uint64_t static_size = sum_static<0u>(); + + /// Byte offset of member i within the static section. + template static constexpr uint64_t offset_of(){ + if constexpr (i == 0u){ + return 0u; + } else { + using Prev = typename parameter_pack_type::type; + return offset_of() + forst_info::static_size; + } + } +}; + +template +struct forst_info...>> { + using AsTuple = sch::Tuple; + + static constexpr uint64_t layers = forst_info::layers; + static constexpr uint64_t static_size = forst_info::static_size; + + template static constexpr uint64_t offset_of(){ + return forst_info::template offset_of(); + } +}; + +} // namespace impl + +/** + * The encoded bytes. + * + * Holds its own buffer and copies deeply, like enc::Native. Binary rather than + * text, so unlike data this is a byte vector. + */ +template class data final { +public: + using SchemaType = Schema; + +private: + std::vector value_; + +public: + data() = default; + + explicit data(std::vector value__) : value_{std::move(value__)} {} + + void set(std::vector value__) { value_ = std::move(value__); } + + const std::vector &bytes() const { return value_; } + std::vector &bytes() { return value_; } + + const uint8_t *raw() const { return value_.empty() ? nullptr : value_.data(); } + uint8_t *raw() { return value_.empty() ? nullptr : value_.data(); } + + data size() const { return {value_.size()}; } +}; + +namespace impl { + +/** + * Little endian is assumed, never converted. + * + * wasm is little endian by specification and every host this runs on is too. + * A big endian target should fail to build rather than silently produce + * byte-swapped field data that looks almost plausible. + */ +static_assert(std::endian::native == std::endian::little, + "Forst assumes a little endian host"); + +/** + * Bytes a value needs in the dynamic layer. Zero for anything fixed size. + * + * With one layer the contents of a dynamic member are themselves always fixed + * size, so this never has to recurse into a dynamic child's own dynamic part. + */ +template struct forst_dynamic_size { + static uint64_t apply(const data &){ return 0u; } +}; + +template <> struct forst_dynamic_size { + static uint64_t apply(const data &from){ + return from.size().get(); + } +}; + +template struct forst_dynamic_size> { + static uint64_t apply(const data, enc::Native> &from){ + uint64_t count = 1u; + for(uint64_t i = 0u; i < Dim; ++i){ + count *= from.meta().flat_at(i).get(); + } + return count * forst_info::static_size; + } +}; + +template +struct forst_dynamic_size> { + static uint64_t apply(const data, enc::Native> &from){ + if constexpr (forst_info::layers == 0u){ + return 0u; + } else { + uint64_t total = 0u; + constexpr uint64_t count = ct_multiply::value; + for(uint64_t i = 0u; i < count; ++i){ + total += forst_dynamic_size::apply(from.flat_at(i)); + } + return total; + } + } +}; + +template +struct forst_dynamic_size...>> { + using Schema = sch::Struct...>; + + template + static uint64_t step(const data &from){ + if constexpr (i < sizeof...(T)){ + using Ti = typename parameter_pack_type::type; + return forst_dynamic_size::apply(from.template get_at_index()) + + step(from); + } + return 0u; + } + + static uint64_t apply(const data &from){ + return step<0u>(from); + } +}; + +/// Writes a value's static bytes at `at`, appending any contents at `dyn`. +template struct forst_write; + +template struct forst_write> { + static void apply(const data, enc::Native> &from, + uint8_t *base, uint64_t at, uint64_t &){ + auto value = from.get(); + static_assert(sizeof(value) == N, "Primitive storage must be its width"); + std::memcpy(base + at, &value, N); + } +}; + +template <> struct forst_write { + static void apply(const data &from, uint8_t *base, + uint64_t at, uint64_t &){ + base[at] = from.get() ? 1u : 0u; + } +}; + +template <> struct forst_write { + static void apply(const data &, uint8_t *, uint64_t, + uint64_t &){} +}; + +template <> struct forst_write { + static void apply(const data &from, uint8_t *base, + uint64_t at, uint64_t &dyn){ + const uint64_t length = from.size().get(); + std::memcpy(base + at, &length, 8u); + + // Measured from just past the offset field, so resolving it is one add. + const uint64_t offset = dyn - (at + 16u); + std::memcpy(base + at + 8u, &offset, 8u); + + if(length > 0u){ + std::memcpy(base + dyn, from.stl_view().data(), length); + } + dyn += length; + } +}; + +template struct forst_write> { + static void apply(const data, enc::Native> &from, + uint8_t *base, uint64_t at, uint64_t &dyn){ + static_assert(forst_info::layers == 0u, + "One dynamic layer only: an Array element must be fixed size. " + "Array and Array> need a second layer."); + + uint64_t count = 1u; + for(uint64_t i = 0u; i < Dim; ++i){ + const uint64_t extent = from.meta().flat_at(i).get(); + std::memcpy(base + at + 8u * i, &extent, 8u); + count *= extent; + } + + const uint64_t offset = dyn - (at + forst_info>::static_size); + std::memcpy(base + at + 8u * Dim, &offset, 8u); + + // Elements are fixed size, so they go straight into the layer with no + // dynamic part of their own. + uint64_t unused = 0u; + const uint64_t stride = forst_info::static_size; + for(uint64_t i = 0u; i < count; ++i){ + forst_write::apply(from.flat_at(i), base, dyn + i * stride, unused); + } + dyn += count * stride; + } +}; + +template struct forst_write> { + static void apply(const data, enc::Native> &from, + uint8_t *base, uint64_t at, uint64_t &dyn){ + constexpr uint64_t count = ct_multiply::value; + constexpr uint64_t stride = forst_info::static_size; + for(uint64_t i = 0u; i < count; ++i){ + forst_write::apply(from.flat_at(i), base, at + i * stride, dyn); + } + } +}; + +template struct forst_write> { + static void apply(const data, enc::Native> &from, + uint8_t *base, uint64_t at, uint64_t &dyn){ + constexpr uint64_t count = ct_multiply::value; + constexpr uint64_t stride = forst_info::static_size; + for(uint64_t i = 0u; i < count; ++i){ + forst_write::apply(from.flat_at(i), base, at + i * stride, dyn); + } + } +}; +template +struct forst_write...>> { + using Schema = sch::Struct...>; + using Info = forst_info; + + template + static void step(const data &from, uint8_t *base, + uint64_t at, uint64_t &dyn){ + if constexpr (i < sizeof...(T)){ + using Ti = typename parameter_pack_type::type; + forst_write::apply(from.template get_at_index(), base, + at + Info::template offset_of(), dyn); + step(from, base, at, dyn); + } + } + + static void apply(const data &from, uint8_t *base, + uint64_t at, uint64_t &dyn){ + step<0u>(from, base, at, dyn); + } +}; + + +/** + * Reads a value's static bytes at `at`. + * + * Every read is bounds checked against the buffer rather than trusted: the + * bytes may have come off a network from a peer that is older, newer, or + * hostile, and a bad offset would otherwise be an out of bounds read. + */ +template struct forst_read; + +template struct forst_read> { + static error_or apply(const uint8_t *base, uint64_t size, uint64_t at, + data, enc::Native> &to){ + if(at + N > size){ + return make_error(); + } + typename native_data_type>::type value{}; + std::memcpy(&value, base + at, N); + to.set(value); + return make_void(); + } +}; + +template <> struct forst_read { + static error_or apply(const uint8_t *base, uint64_t size, uint64_t at, + data &to){ + if(at + 1u > size){ + return make_error(); + } + to.set(base[at] != 0u); + return make_void(); + } +}; + +template <> struct forst_read { + static error_or apply(const uint8_t *, uint64_t, uint64_t, + data &){ + return make_void(); + } +}; + +template <> struct forst_read { + static error_or apply(const uint8_t *base, uint64_t size, uint64_t at, + data &to){ + if(at + 16u > size){ + return make_error(); + } + + uint64_t length = 0u; + uint64_t offset = 0u; + std::memcpy(&length, base + at, 8u); + std::memcpy(&offset, base + at + 8u, 8u); + + const uint64_t start = at + 16u + offset; + // Checked as a sum that cannot wrap, so a hostile length plus a + // hostile offset cannot alias back into the static section. + if(start > size or length > size - start){ + return make_error(); + } + + to.set(std::string{reinterpret_cast(base + start), + static_cast(length)}); + return make_void(); + } +}; + +template struct forst_read> { + static error_or apply(const uint8_t *base, uint64_t size, uint64_t at, + data, enc::Native> &to){ + static_assert(forst_info::layers == 0u, + "One dynamic layer only: an Array element must be fixed size."); + + constexpr uint64_t slot = forst_info>::static_size; + if(at + slot > size){ + return make_error(); + } + + index_data extents; + uint64_t count = 1u; + for(uint64_t i = 0u; i < Dim; ++i){ + uint64_t extent = 0u; + std::memcpy(&extent, base + at + 8u * i, 8u); + extents.flat_at(i).set(extent); + + // Reject an extent product that would overflow before it is used + // to size an allocation. + if(extent != 0u and count > (~uint64_t{0u}) / extent){ + return make_error(); + } + count *= extent; + } + + uint64_t offset = 0u; + std::memcpy(&offset, base + at + 8u * Dim, 8u); + + constexpr uint64_t stride = forst_info::static_size; + const uint64_t start = at + slot + offset; + if(start > size or (stride != 0u and count > (size - start) / stride)){ + return make_error(); + } + + to = data, enc::Native>{extents}; + for(uint64_t i = 0u; i < count; ++i){ + auto eov = forst_read::apply(base, size, start + i * stride, + to.flat_at(i)); + if(eov.is_error()){ + return eov; + } + } + return make_void(); + } +}; + +template struct forst_read> { + static error_or apply(const uint8_t *base, uint64_t size, uint64_t at, + data, enc::Native> &to){ + constexpr uint64_t count = ct_multiply::value; + constexpr uint64_t stride = forst_info::static_size; + for(uint64_t i = 0u; i < count; ++i){ + auto eov = forst_read::apply(base, size, at + i * stride, + to.flat_at(i)); + if(eov.is_error()){ + return eov; + } + } + return make_void(); + } +}; + +template struct forst_read> { + static error_or apply(const uint8_t *base, uint64_t size, uint64_t at, + data, enc::Native> &to){ + constexpr uint64_t count = ct_multiply::value; + constexpr uint64_t stride = forst_info::static_size; + for(uint64_t i = 0u; i < count; ++i){ + auto eov = forst_read::apply(base, size, at + i * stride, + to.flat_at(i)); + if(eov.is_error()){ + return eov; + } + } + return make_void(); + } +}; + +template +struct forst_read...>> { + using Schema = sch::Struct...>; + using Info = forst_info; + + template + static error_or step(const uint8_t *base, uint64_t size, uint64_t at, + data &to){ + if constexpr (i < sizeof...(T)){ + using Ti = typename parameter_pack_type::type; + auto eov = forst_read::apply( + base, size, at + Info::template offset_of(), + to.template get_at_index()); + if(eov.is_error()){ + return eov; + } + return step(base, size, at, to); + } + return make_void(); + } + + static error_or apply(const uint8_t *base, uint64_t size, uint64_t at, + data &to){ + return step<0u>(base, size, at, to); + } +}; + +} // namespace impl + +/** + * Translates between a native value and its Forst bytes. + */ +template class codec final { +public: + static_assert(impl::forst_info::layers <= 1u, + "Forst here carries exactly one dynamic layer. A schema needing more " + "-- Array, Array> -- has to be flattened."); + + codec() = default; + + KEL_FORBID_COPY(codec); + KEL_DEFAULT_MOVE(codec); + + error_or encode(const data &from, + data &to){ + constexpr uint64_t static_size = impl::forst_info::static_size; + const uint64_t dynamic_size = impl::forst_dynamic_size::apply(from); + + std::vector buffer; + try { + buffer.resize(static_cast(static_size + dynamic_size)); + } catch (const std::exception &e){ + (void) e; + return make_error(); + } + + uint64_t dyn = static_size; + if(not buffer.empty()){ + impl::forst_write::apply(from, buffer.data(), 0u, dyn); + } + + to.set(std::move(buffer)); + return make_void(); + } + + error_or decode(const data &from, + data &to){ + const uint64_t size = from.size().get(); + if(size < impl::forst_info::static_size){ + return make_error(); + } + return impl::forst_read::apply(from.raw(), size, 0u, to); + } +}; + +} // namespace lbm +} // namespace kel -- cgit v1.3.1