Skip to main content

utz_encode/
encode.rs

1//! The self-describing container serializer.
2//!
3//! The layout is as follows (all little-endian):
4//! ```text
5//! prologue: magic "uTZ1" | version u8 | 3 reserved bytes — format identity,
6//!           the only layout frozen across versions
7//! header:   one fixed [`PayloadHeader`] record (utz_common), PLAINTEXT —
8//!           codec, decompressed size, every section offset and count; the
9//!           encoder Pwrites it, the reader Preads it (before decompressing
10//!           anything), so the field list IS the wire layout
11//! sections (compressed per the header's codec):
12//!   zone table: str_offsets u16[n_features+1] | tzid pool bytes   (zone i = feature i)
13//!   arc store:  arc_offsets u32[n_arcs+1] (relative to arc data)
14//!               | per arc: varint vcount | first vertex i{16,24,32}×2
15//!               | zigzag-varint deltas
16//!   ring index: parent u16[n_polys] + poly_offsets u32[n_polys+1]
17//!   (relative to ring data) — grid candidates are polys
18//!               | per feature: npolys u16; per poly: bbox i{16,24,32}×4
19//!               | nrings u16; per ring: varint nrefs | varint signed arc refs
20//!               (id<<1|rev)
21//!   grid:       primary u16[ncols*nrows]
22//!               | list_offsets u16[uniq+1] | list_ids u16[Σ]
23//!   release:    the TZBB release string bytes (the payload tail)
24//! ```
25//! The header records every knob, so the runtime decoder stays generic.
26//! The grid and bboxes are derived from the QUANTIZED geometry, so what the
27//! runtime PIPs is exactly what the grid indexed.
28
29use scroll::{LE, Pread, Pwrite};
30use utz_common::{CellTag, NO_ZONE, PayloadHeader};
31pub use utz_common::{Dataset, MAGIC, PAYLOAD_HEADER_LEN, PROLOGUE_LEN, VERSION};
32
33use crate::error::ensure;
34use crate::grid::{self, Order};
35use crate::topo::{put_varint, zigzag};
36use crate::{Arc, Error, Feat, clean, dq_lat, dq_lon, q_lat, q_lon, qmax_for, topo};
37/// Checked narrowing for serializer counts and offsets: the format stores
38/// these at fixed width and a wrap would silently corrupt the container, so
39/// the helpers panic.
40/// Data-dependent limits (feature count, tzid pool, CSR tables) are
41/// `ensure!`-guarded with [`Error::FormatLimit`] before these run.
42fn c32(value: usize) -> u32 {
43    u32::try_from(value).expect("exceeds u32 format width")
44}
45fn c16(value: usize) -> u16 {
46    u16::try_from(value).expect("exceeds u16 format width")
47}
48
49pub use utz_common::{Codec, GeomEncoding, QuantBits, SimplifyAlgorithm};
50
51/// Builds the ε-driven `Simplify` for the topology builder: ε is a max
52/// deviation in degrees for RDP and Imai–Iri, and Visvalingam's area
53/// threshold is derived as ε². The viewer uses the same convention, so
54/// parameters found in the viewer plug straight into build scripts.
55#[must_use]
56pub fn to_simplify(algorithm: SimplifyAlgorithm, epsilon_deg: f64) -> utz_simplify::Simplify {
57    match algorithm {
58        SimplifyAlgorithm::None => utz_simplify::Simplify::None,
59        SimplifyAlgorithm::Rdp => utz_simplify::Simplify::Rdp {
60            epsilon: epsilon_deg,
61        },
62        SimplifyAlgorithm::ImaiIri => utz_simplify::Simplify::ImaiIri {
63            epsilon: epsilon_deg,
64        },
65        SimplifyAlgorithm::Visvalingam => utz_simplify::Simplify::Visvalingam {
66            min_area: epsilon_deg * epsilon_deg,
67        },
68    }
69}
70
71/// The parameters of one encode run: they carry the recipe knobs plus the
72/// provenance recorded in the asset's header.
73#[derive(Clone, Copy)]
74pub struct Params<'a> {
75    /// The dataset the features came from, recorded in the header as
76    /// provenance.
77    pub dataset: Dataset,
78    /// The TZBB release tag recorded in the header (the rules snapshot and
79    /// cache key).
80    pub tzbb_release: &'a str,
81    pub epsilon_m: f64,
82    /// The quantization bit width: 16, 24, or 32.
83    pub quant_bits: u32,
84    /// The grid cell size in degrees, within 0.1–45; fractional values
85    /// (0.5, 4/3, …) are allowed.
86    pub grid_deg: f64,
87    pub codec: Codec,
88    /// The simplification algorithm, applied by [`build_payload()`] and
89    /// recorded in the header either way.
90    pub simplify: SimplifyAlgorithm,
91    /// The arc-store encoding, delta+varint (the default) or fixed-width.
92    pub geom: GeomEncoding,
93    /// The population-density weight floor, recorded in the header as
94    /// provenance (`None` means unweighted). The weighting itself is
95    /// applied by the caller's simplification pass (`utz_build`'s
96    /// `encode_weighted()`); this field only stamps the knob.
97    pub density_weight_floor: Option<f64>,
98}
99
100/// The byte size of each payload section plus post-simplification geometry
101/// counts: these are the viewer's "delta+varint" stage stats.
102#[derive(Clone, Copy, Default, Debug)]
103pub struct PayloadStats {
104    pub header: u32,
105    pub zones: u32,
106    pub arcs: u32,
107    pub rings: u32,
108    pub grid: u32,
109    pub n_arcs: u32,
110    /// The number of vertices actually stored (post-simplify,
111    /// post-quantize-clean).
112    pub n_verts: u32,
113    /// The tallies of what the post-quantization cleanup removed (see
114    /// clean.rs).
115    pub clean: clean::CleanStats,
116}
117
118/// Runs the full uniform-ε pipeline: topology → RDP → quantize → grid →
119/// serialize → compress. Spatially varying tolerance (population weighting)
120/// is a simplification concern, not a serialization one: build the topology
121/// yourself (`topo::build_topology_weighted()`) and use
122/// [`payload_from_topology()`] and [`finish()`] (see `utz_build`'s wrapper).
123///
124/// # Errors
125///
126/// The errors are the same as [`build_payload()`]'s.
127pub fn encode(feats: &[Feat], params: &Params) -> crate::Result<Vec<u8>> {
128    finish(&build_payload(feats, params)?, params.codec)
129}
130
131/// Builds everything but the outer header and compression, so size sweeps
132/// can compress one payload with several codecs.
133///
134/// # Errors
135///
136/// The errors are those of [`payload_from_topology()`].
137pub fn build_payload(feats: &[Feat], params: &Params) -> crate::Result<Vec<u8>> {
138    let algorithm = to_simplify(params.simplify, params.epsilon_m / crate::METERS_PER_DEG);
139    let topology = topo::build_topology_algorithm(feats, algorithm);
140    Ok(payload_from_topology(&topology, &topology.arc_coords, feats, params)?.0)
141}
142
143/// The header's fixed-point (1e-4) density-weight floor. A real floor
144/// never stamps 0 (which means "unweighted"), and `floor >= 1.0` means
145/// weighting off, which callers express as `None`.
146///
147/// # Errors
148/// Returns [`Error::DensityWeightFloor`] for a non-finite floor or one
149/// outside (0, 1).
150fn density_weight_floor_e4(floor: Option<f64>) -> crate::Result<u16> {
151    match floor {
152        None => Ok(0),
153        Some(floor) => {
154            ensure!(
155                floor.is_finite() && floor > 0.0 && floor < 1.0,
156                Error::DensityWeightFloor { floor }
157            );
158            #[expect(
159                clippy::cast_possible_truncation,
160                clippy::cast_sign_loss,
161                reason = "validated into (0, 1) above, so the product is in (0, 10_000)"
162            )]
163            Ok(((floor * 1e4).round() as u16).max(1))
164        }
165    }
166}
167
168/// Serializes an already-simplified topology: quantize → grid → sections.
169/// `arc_coords` may differ from `topology.arc_coords` (the wasm viewer
170/// simplifies per-arc itself); `feats` supplies only per-feature metadata
171/// (tzid, offset). Geometry comes from the arcs. `params.epsilon_m` is recorded
172/// in the header, not applied.
173///
174/// # Errors
175///
176/// The call errors on out-of-range params (`quant_bits` not 16/24/32,
177/// `grid_deg` outside 0.1–45, `tzbb_release` ≥ 256 bytes) or format-limit
178/// overflows (feature/polygon counts past 15-bit zone ids, CSR list tables
179/// past their 15-bit/u16 space, eager coordinate count past u32).
180///
181/// # Panics
182/// Panics if a serialized section outgrows its u16/u32 format width where
183/// no [`Error::FormatLimit`] guard applies (a payload over 4 GiB,
184/// unreachable for real datasets).
185pub fn payload_from_topology(
186    topology: &topo::Topology,
187    arc_coords: &[Arc],
188    feats: &[Feat],
189    params: &Params,
190) -> crate::Result<(Vec<u8>, PayloadStats)> {
191    // validate the raw knob once; everything downstream carries the enum
192    let quant_bits = u8::try_from(params.quant_bits)
193        .ok()
194        .and_then(QuantBits::from_byte)
195        .ok_or(Error::QuantBits {
196            bits: params.quant_bits,
197        })?;
198    ensure!(
199        (0.1..=45.0).contains(&params.grid_deg),
200        Error::GridDeg {
201            deg: params.grid_deg
202        }
203    );
204    let density_weight_floor_e4 = density_weight_floor_e4(params.density_weight_floor)?;
205    ensure!(
206        feats.len() < usize::from(NO_ZONE),
207        Error::FormatLimit {
208            what: "feature count (15-bit zone ids)",
209            n: feats.len(),
210            max: usize::from(NO_ZONE) - 1
211        }
212    );
213    let qmax = qmax_for(quant_bits.bits());
214    let clean_geom = quantize_clean(topology, arc_coords, qmax);
215    let (cell_grid, csr, parent) = poly_grid(&clean_geom, feats, params, qmax)?;
216    let full_rings = (params.geom == GeomEncoding::FullRings)
217        .then(|| flatten_full_rings(&clean_geom, feats.len()));
218
219    let mut stats = PayloadStats {
220        n_arcs: c32(clean_geom.arcs_q.len()),
221        n_verts: clean_geom.arcs_q.iter().map(|arc| c32(arc.len())).sum(),
222        clean: clean_geom.stats,
223        ..Default::default()
224    };
225    let counts = eager_counts(
226        full_rings.as_ref(),
227        &clean_geom,
228        feats.len(),
229        parent.len(),
230        params.geom,
231    );
232    ensure_header_limits(params, counts, parent.len())?;
233    let (eager_coords, eager_rings, eager_polys) = counts;
234    // header space reserved up front (plaintext; finish() compresses only
235    // the sections after it); stored offsets are relative to the sections
236    let mut out = vec![0u8; PAYLOAD_HEADER_LEN];
237    stats.header = c32(out.len());
238    write_zone_table(&mut out, feats)?;
239    let (arcs_off, rings_off) = write_geometry_sections(
240        &mut out,
241        params,
242        quant_bits,
243        &clean_geom,
244        full_rings.as_ref(),
245        &parent,
246        &mut stats,
247    );
248
249    let grid_off = c32(out.len());
250    stats.rings = grid_off - rings_off;
251    write_grid(&mut out, &csr);
252    stats.grid = c32(out.len()) - grid_off;
253
254    let release_off = c32(out.len());
255    out.extend_from_slice(params.tzbb_release.as_bytes());
256
257    #[expect(clippy::cast_possible_truncation, reason = "f32 header fields")]
258    let (grid_deg, epsilon_m) = (params.grid_deg as f32, params.epsilon_m as f32);
259    let header_len = c32(PAYLOAD_HEADER_LEN);
260    let header = PayloadHeader {
261        arcs_off: arcs_off - header_len,
262        rings_off: rings_off - header_len,
263        grid_off: grid_off - header_len,
264        release_off: release_off - header_len,
265        eager_coords: u32::try_from(eager_coords).expect("guarded by ensure_header_limits"),
266        eager_rings,
267        eager_polys,
268        // no arc store outside the arc-encoded geometries
269        n_arcs: match params.geom {
270            GeomEncoding::VarintArcs | GeomEncoding::FixedWidthArcs => stats.n_arcs,
271            GeomEncoding::FullRings | GeomEncoding::Coarse => 0,
272        },
273        raw_len: c32(out.len() - PAYLOAD_HEADER_LEN),
274        grid_deg,
275        epsilon_m,
276        n_features: c16(feats.len()),
277        ncols: c16(cell_grid.ncols()),
278        nrows: c16(cell_grid.nrows()),
279        uniq: c16(csr.uniq_lists),
280        release_len: c16(params.tzbb_release.len()),
281        flags: 0, // reserved
282        dataset: params.dataset,
283        quant_bits,
284        simplify_algorithm: params.simplify,
285        geom: params.geom,
286        codec: Codec::Uncompressed, // finish() records the actual codec
287        density_weight_floor_e4,
288        reserved: 0,
289    };
290    out.pwrite_with(header, 0, LE)
291        .expect("header buffer reserved at PAYLOAD_HEADER_LEN");
292    Ok((out, stats))
293}
294
295/// The cleaned, quantized geometry, made of the topology whose rings and
296/// structure survived the degenerate-drop plus the quantized shared arcs
297/// they reference.
298struct CleanGeom {
299    /// `arc_coords` is empty; the geometry lives in `arcs_q`.
300    topology: topo::Topology,
301    arcs_q: Vec<Arc<i32>>,
302    stats: clean::CleanStats,
303}
304
305/// Quantizes arcs at `qmax`, then cleans the snapping artifacts per shared
306/// arc (dups, zero-area spikes, collinear pass-throughs) and drops rings
307/// that collapsed to zero area (see clean.rs). Junction endpoints stay put,
308/// so neighbouring zones remain stitched.
309fn quantize_clean(topology: &topo::Topology, arc_coords: &[Arc], qmax: f64) -> CleanGeom {
310    let mut stats = clean::CleanStats::default();
311    let arcs_q: Vec<Arc<i32>> = arc_coords
312        .iter()
313        .map(|arc| {
314            let mut quantized: Arc<i32> = arc
315                .iter()
316                .map(|&(lon, lat)| (q_lon(lon, qmax), q_lat(lat, qmax)))
317                .collect();
318            let closed = arc.len() > 1 && arc.first() == arc.last();
319            clean::clean_arc(&mut quantized, closed, &mut stats);
320            quantized
321        })
322        .collect();
323    let (ring_refs, structure, arcs_q) =
324        clean::drop_degenerate_rings(&topology.ring_refs, &topology.structure, arcs_q, &mut stats);
325    CleanGeom {
326        topology: topo::Topology {
327            arc_coords: Vec::new(),
328            ring_refs,
329            structure,
330        },
331        arcs_q,
332        stats,
333    }
334}
335
336/// Builds the grid over the snapped (dequantized) geometry, which is
337/// exactly what the runtime sees. Rasterization runs per POLYGON, not per
338/// feature: border-cell candidate
339/// lists carry poly ids, so lookups jump straight to the ~2 polys whose rings
340/// touch the cell instead of bbox-scanning every poly of every candidate
341/// feature (in the `polygrid_probe` bench, parsed polys fell from 20-24 to
342/// 2.1, per-poly bboxes became redundant, and CSR growth ≈ the dropped
343/// bbox bytes). Returns the cell grid, the
344/// interned CSR (interior cells rewritten to FEATURE ids: coarse answers
345/// need no parent hop; border lists keep poly ids), and the poly→feature
346/// parent table.
347fn poly_grid(
348    clean_geom: &CleanGeom,
349    feats: &[Feat],
350    params: &Params,
351    qmax: f64,
352) -> crate::Result<(grid::CellGrid, grid::Csr, Vec<u16>)> {
353    let arcs_snapped: Vec<Arc> = clean_geom
354        .arcs_q
355        .iter()
356        .map(|arc| {
357            arc.iter()
358                .map(|&(x, y)| (dq_lon(f64::from(x), qmax), dq_lat(f64::from(y), qmax)))
359                .collect()
360        })
361        .collect();
362    let snapped = clean_geom.topology.reconstruct(feats, &arcs_snapped);
363    let mut poly_feats: Vec<Feat> = Vec::new();
364    let mut parent: Vec<u16> = Vec::new(); // poly id -> feature id
365    for (feature_index, snapped_feature) in snapped.iter().enumerate() {
366        for poly in &snapped_feature.polys {
367            poly_feats.push(Feat {
368                offset: 0.0,
369                tzid: None,
370                polys: vec![poly.clone()],
371            });
372            parent.push(c16(feature_index));
373        }
374    }
375    ensure!(
376        poly_feats.len() < usize::from(NO_ZONE),
377        Error::FormatLimit {
378            what: "polygon count (15-bit ids)",
379            n: poly_feats.len(),
380            max: usize::from(NO_ZONE) - 1
381        }
382    );
383    let cell_grid = grid::build(&poly_feats, params.grid_deg, 8);
384    let areas = grid::feat_areas(&poly_feats);
385    let mut csr = grid::intern_csr(&cell_grid, Order::CellDominantFirst, &areas);
386    for cell in &mut csr.primary {
387        if let CellTag::Zone(poly) = CellTag::from_cell(*cell) {
388            *cell = parent[usize::from(poly)];
389        }
390    }
391    // the format's CSR tables are u16: border-cell tags carry a 15-bit
392    // list index, and list_offsets index into list_ids as u16 — a fine grid
393    // on a dense dataset can overflow both. Fail loudly instead of the `as
394    // u16` wrap silently corrupting the tables.
395    ensure!(
396        csr.uniq_lists < usize::from(NO_ZONE),
397        Error::GridLists {
398            deg: params.grid_deg,
399            n: csr.uniq_lists
400        }
401    );
402    ensure!(
403        u16::try_from(csr.list_ids.len()).is_ok(),
404        Error::GridListIds {
405            deg: params.grid_deg,
406            n: csr.list_ids.len()
407        }
408    );
409    Ok((cell_grid, csr, parent))
410}
411
412/// The flattened preload-cache shape (geom=2): per-ring coordinate runs
413/// plus the ring/poly index tables. It is built before the header so the
414/// eager counts are exact and serialization just copies.
415struct FullRingsSections {
416    coords: Vec<(i32, i32)>,
417    ring_ends: Vec<u32>,
418    /// One entry per poly: the bbox plus the `ring_ends` index one past
419    /// its last ring.
420    polys: Vec<([i32; 4], u32)>,
421}
422
423/// Assembles the [`FullRingsSections`]. Junction dedup stays within a
424/// ring.
425fn flatten_full_rings(clean_geom: &CleanGeom, n_features: usize) -> FullRingsSections {
426    let (mut coords, mut ring_ends, mut polys) = (Vec::new(), Vec::new(), Vec::new());
427    for feature_index in 0..n_features {
428        for poly in &clean_geom.topology.structure[feature_index] {
429            let mut bbox = [i32::MAX, i32::MAX, i32::MIN, i32::MIN];
430            for &ring_index in poly {
431                let ring_start = coords.len();
432                for &arc_ref in &clean_geom.topology.ring_refs[ring_index] {
433                    let (id, reversed) = ((arc_ref >> 1) as usize, (arc_ref & 1) == 1);
434                    let arc_start = coords.len();
435                    let arc = &clean_geom.arcs_q[id];
436                    if reversed {
437                        coords.extend(arc.iter().rev());
438                    } else {
439                        coords.extend(arc.iter());
440                    }
441                    // drop the duplicated junction vertex between arcs
442                    if arc_start > ring_start && coords.get(arc_start - 1) == coords.get(arc_start)
443                    {
444                        coords.remove(arc_start);
445                    }
446                }
447                // drop the duplicated ring-closure vertex (ring_hit wraps)
448                if coords.len() > ring_start + 1 && coords.last() == coords.get(ring_start) {
449                    coords.pop();
450                }
451                for &(x, y) in &coords[ring_start..] {
452                    bbox = [
453                        bbox[0].min(x),
454                        bbox[1].min(y),
455                        bbox[2].max(x),
456                        bbox[3].max(y),
457                    ];
458                }
459                ring_ends.push(c32(coords.len()));
460            }
461            polys.push((bbox, c32(ring_ends.len())));
462        }
463    }
464    FullRingsSections {
465        coords,
466        ring_ends,
467        polys,
468    }
469}
470
471/// Eager-cache counts the header advertises: what preload will hold.
472/// Exact for `FullRingsSections` (they locate the sections) and `Coarse`; for the
473/// arc-store geoms a reservation: coords as Σ referenced-arc vcounts
474/// (junction dedup at decode shrinks it a hair; a reservation may only
475/// over-estimate).
476fn eager_counts(
477    full_rings: Option<&FullRingsSections>,
478    clean_geom: &CleanGeom,
479    n_features: usize,
480    n_parent: usize,
481    geom: GeomEncoding,
482) -> (u64, u32, u32) {
483    match full_rings {
484        Some(rings) => (
485            rings.coords.len() as u64,
486            c32(rings.ring_ends.len()),
487            c32(rings.polys.len()),
488        ),
489        // coarse: no geometry — polys counts the parent table entries
490        None if geom == GeomEncoding::Coarse => (0, 0, c32(n_parent)),
491        None => {
492            let mut coords: u64 = 0;
493            let (mut rings, mut polys) = (0u32, 0u32);
494            for feature_index in 0..n_features {
495                for poly in &clean_geom.topology.structure[feature_index] {
496                    polys += 1;
497                    for &ring_index in poly {
498                        rings += 1;
499                        coords += clean_geom.topology.ring_refs[ring_index]
500                            .iter()
501                            .map(|&arc_ref| clean_geom.arcs_q[(arc_ref >> 1) as usize].len() as u64)
502                            .sum::<u64>();
503                    }
504                }
505            }
506            (coords, rings, polys)
507        }
508    }
509}
510
511/// The geometry-dependent sections between the zone table and the grid;
512/// returns `(arcs_off, rings_off)`.
513fn write_geometry_sections(
514    out: &mut Vec<u8>,
515    params: &Params,
516    quant_bits: QuantBits,
517    clean_geom: &CleanGeom,
518    full_rings: Option<&FullRingsSections>,
519    parent: &[u16],
520    stats: &mut PayloadStats,
521) -> (u32, u32) {
522    let (arcs_off, rings_off);
523    if params.geom == GeomEncoding::Coarse {
524        // ---- coarse (geom=3): no geometry sections, just the parent table
525        // (border-cell candidate poly ids still resolve to features) ----
526        arcs_off = c32(out.len());
527        stats.zones = arcs_off - stats.header;
528        rings_off = c32(out.len());
529        for &parent_feature in parent {
530            out.extend_from_slice(&parent_feature.to_le_bytes());
531        }
532    } else if let Some(rings) = full_rings {
533        // ---- full-rings geometry (geom=2): coords 4-aligned within the
534        // payload (the 12-byte outer header keeps it 4-aligned in flash) ----
535        while !out.len().is_multiple_of(4) {
536            out.push(0);
537        }
538        arcs_off = c32(out.len());
539        stats.zones = arcs_off - stats.header;
540        write_full_rings(out, rings, quant_bits);
541        // ---- ring index reduces to the parent table ----
542        rings_off = c32(out.len());
543        stats.arcs = rings_off - arcs_off;
544        for &parent_feature in parent {
545            out.extend_from_slice(&parent_feature.to_le_bytes());
546        }
547    } else {
548        arcs_off = c32(out.len());
549        stats.zones = arcs_off - stats.header;
550        write_arc_store(out, &clean_geom.arcs_q, params.geom, quant_bits);
551        rings_off = c32(out.len());
552        stats.arcs = rings_off - arcs_off;
553        for &parent_feature in parent {
554            out.extend_from_slice(&parent_feature.to_le_bytes());
555        }
556        write_ring_index(out, clean_geom, parent.len(), quant_bits);
557    }
558    (arcs_off, rings_off)
559}
560
561/// Format-limit guards for the header fields (the header itself is written
562/// by `Pwrite` at the end of `payload_from_topology`, once offsets exist).
563fn ensure_header_limits(
564    params: &Params,
565    counts: (u64, u32, u32),
566    n_parent: usize,
567) -> crate::Result<()> {
568    let (eager_coords, _, eager_polys) = counts;
569    ensure!(
570        u32::try_from(eager_coords).is_ok(),
571        Error::FormatLimit {
572            what: "eager_coords",
573            n: usize::try_from(eager_coords).unwrap_or(usize::MAX),
574            max: u32::MAX as usize
575        }
576    );
577    ensure!(
578        eager_polys as usize == n_parent,
579        Error::FormatLimit {
580            what: "eager_polys (must equal parent count)",
581            n: eager_polys as usize,
582            max: n_parent
583        }
584    );
585    ensure!(
586        u16::try_from(params.tzbb_release.len()).is_ok(),
587        Error::FormatLimit {
588            what: "tzbb_release bytes",
589            n: params.tzbb_release.len(),
590            max: u16::MAX as usize
591        }
592    );
593    Ok(())
594}
595
596/// Zone table: `str_offsets u16[n+1]` + tzid pool (zone i = feature i).
597fn write_zone_table(out: &mut Vec<u8>, feats: &[Feat]) -> crate::Result<()> {
598    // the offsets are u16 on disk — fail loudly instead of the `as u16`
599    // wrap silently corrupting the table (same policy as the CSR guards)
600    let total_pool: usize = feats
601        .iter()
602        .map(|feature| feature.tzid.as_deref().unwrap_or("").len())
603        .sum();
604    ensure!(
605        u16::try_from(total_pool).is_ok(),
606        Error::FormatLimit {
607            what: "tzid pool bytes (u16 offsets)",
608            n: total_pool,
609            max: u16::MAX as usize
610        }
611    );
612    let mut str_offsets: Vec<u16> = Vec::with_capacity(feats.len() + 1);
613    let mut pool: Vec<u8> = Vec::new();
614    for feature in feats {
615        str_offsets.push(c16(pool.len()));
616        pool.extend_from_slice(feature.tzid.as_deref().unwrap_or("").as_bytes());
617    }
618    str_offsets.push(c16(pool.len()));
619    for offset in &str_offsets {
620        out.extend_from_slice(&offset.to_le_bytes());
621    }
622    out.extend_from_slice(&pool);
623    Ok(())
624}
625
626/// Appends one fixed-width coordinate at the quant width: the value's low
627/// 2, 3, or 4 little-endian bytes for i16, i24, and i32 quantization.
628/// Public so the runtime crate's coordinate-unpacking tests can round-trip
629/// against the encoder's real byte layout instead of a mirror copy.
630pub fn push_fixed(out: &mut Vec<u8>, value: i32, quant_bits: QuantBits) {
631    out.extend_from_slice(&value.to_le_bytes()[0..quant_bits.bytes()]);
632}
633
634/// Full-rings sections: `[coords][ring_ends u32][polys bbox 4×i32 + rend
635/// u32]`, with coords at quant width (i16 4 B/vertex, i24 packed 6 B,
636/// i32 8 B).
637fn write_full_rings(out: &mut Vec<u8>, rings: &FullRingsSections, quant_bits: QuantBits) {
638    for &(x, y) in &rings.coords {
639        push_fixed(out, x, quant_bits);
640        push_fixed(out, y, quant_bits);
641    }
642    for ring_end in &rings.ring_ends {
643        out.extend_from_slice(&ring_end.to_le_bytes());
644    }
645    for &(bbox, rings_end) in &rings.polys {
646        for value in bbox {
647            out.extend_from_slice(&value.to_le_bytes());
648        }
649        out.extend_from_slice(&rings_end.to_le_bytes());
650    }
651}
652
653/// Arc store: `arc_offsets u32[n_arcs+1] | per arc: varint vcount |
654/// first vertex fixed | zigzag-varint deltas` (or all-fixed for
655/// `GeomEncoding::FixedWidthArcs`); `n_arcs` lives in the payload header.
656fn write_arc_store(
657    out: &mut Vec<u8>,
658    arcs_q: &[Arc<i32>],
659    geom: GeomEncoding,
660    quant_bits: QuantBits,
661) {
662    let mut arc_data = Vec::new();
663    let mut arc_offsets: Vec<u32> = Vec::with_capacity(arcs_q.len() + 1);
664    for arc in arcs_q {
665        arc_offsets.push(c32(arc_data.len()));
666        put_varint(&mut arc_data, arc.len() as u64);
667        match geom {
668            GeomEncoding::VarintArcs => {
669                let (mut previous_x, mut previous_y) = (0i64, 0i64);
670                for (i, &(x, y)) in arc.iter().enumerate() {
671                    if i == 0 {
672                        push_fixed(&mut arc_data, x, quant_bits);
673                        push_fixed(&mut arc_data, y, quant_bits);
674                    } else {
675                        put_varint(&mut arc_data, zigzag(i64::from(x) - previous_x));
676                        put_varint(&mut arc_data, zigzag(i64::from(y) - previous_y));
677                    }
678                    (previous_x, previous_y) = (i64::from(x), i64::from(y));
679                }
680            }
681            GeomEncoding::FixedWidthArcs => {
682                for &(x, y) in arc {
683                    push_fixed(&mut arc_data, x, quant_bits);
684                    push_fixed(&mut arc_data, y, quant_bits);
685                }
686            }
687            GeomEncoding::FullRings | GeomEncoding::Coarse => {
688                unreachable!("handled by the caller")
689            }
690        }
691    }
692    arc_offsets.push(c32(arc_data.len()));
693    for offset in &arc_offsets {
694        out.extend_from_slice(&offset.to_le_bytes());
695    }
696    out.extend_from_slice(&arc_data);
697}
698
699/// Ring index (per-poly records: grid candidates are polys; the parent
700/// table maps them to features): `poly_offsets u32[n+1] | per poly: bbox
701/// fixed×4 | nrings u16 | per ring: varint nrefs + signed arc refs`.
702fn write_ring_index(
703    out: &mut Vec<u8>,
704    clean_geom: &CleanGeom,
705    n_polys: usize,
706    quant_bits: QuantBits,
707) {
708    let mut ring_data = Vec::new();
709    let mut poly_offsets: Vec<u32> = Vec::with_capacity(n_polys + 1);
710    // structure is one entry per feature, in zone-table order
711    for feature_polys in &clean_geom.topology.structure {
712        for poly in feature_polys {
713            poly_offsets.push(c32(ring_data.len()));
714            // per-poly bbox: the point-granular gate — a streaming
715            // miss returns before touching any arc, preload reads instead
716            // of recomputing. Rejects ~5% of poly-grid candidates for 4
717            // compares — ~20x above the check's break-even.
718            let mut bbox = (i32::MAX, i32::MAX, i32::MIN, i32::MIN);
719            for &ring_index in poly {
720                for &arc_ref in &clean_geom.topology.ring_refs[ring_index] {
721                    for &(x, y) in &clean_geom.arcs_q[(arc_ref >> 1) as usize] {
722                        bbox = (bbox.0.min(x), bbox.1.min(y), bbox.2.max(x), bbox.3.max(y));
723                    }
724                }
725            }
726            for value in [bbox.0, bbox.1, bbox.2, bbox.3] {
727                push_fixed(&mut ring_data, value, quant_bits);
728            }
729            ring_data.extend_from_slice(&c16(poly.len()).to_le_bytes());
730            for &ring_index in poly {
731                put_varint(
732                    &mut ring_data,
733                    clean_geom.topology.ring_refs[ring_index].len() as u64,
734                );
735                for &arc_ref in &clean_geom.topology.ring_refs[ring_index] {
736                    put_varint(&mut ring_data, u64::from(arc_ref));
737                }
738            }
739        }
740    }
741    poly_offsets.push(c32(ring_data.len()));
742    for offset in &poly_offsets {
743        out.extend_from_slice(&offset.to_le_bytes());
744    }
745    out.extend_from_slice(&ring_data);
746}
747
748/// Grid tables: `primary u16[ncols*nrows] | list_offsets u16[uniq+1] |
749/// list_ids u16[Σ]`; the dimensions and `uniq` live in the payload header.
750fn write_grid(out: &mut Vec<u8>, csr: &grid::Csr) {
751    for cell in &csr.primary {
752        out.extend_from_slice(&cell.to_le_bytes());
753    }
754    for offset in &csr.list_offsets {
755        out.extend_from_slice(&offset.to_le_bytes());
756    }
757    for id in &csr.list_ids {
758        out.extend_from_slice(&id.to_le_bytes());
759    }
760}
761
762/// Prepend the outer header, compressing the payload with `codec`.
763///
764/// # Errors
765///
766/// As [`compress`].
767///
768/// # Panics
769/// If `payload` is shorter than the header record or its header bytes are
770/// invalid: `payload` must come from [`build_payload`] /
771/// [`payload_from_topology`].
772pub fn finish(payload: &[u8], codec: Codec) -> crate::Result<Vec<u8>> {
773    // the header stays plaintext; only the sections after it compress
774    let (header_bytes, sections) = payload.split_at(PAYLOAD_HEADER_LEN);
775    let mut header: PayloadHeader = header_bytes
776        .pread_with(0, LE)
777        .expect("build_payload wrote a valid header");
778    header.codec = codec;
779    let body = compress(sections, codec)?;
780    let mut out = Vec::with_capacity(PROLOGUE_LEN + PAYLOAD_HEADER_LEN + body.len());
781    out.extend_from_slice(&MAGIC);
782    out.push(VERSION);
783    out.extend_from_slice(&[0u8; 3]); // reserved; pads the header start to +8
784    out.resize(PROLOGUE_LEN + PAYLOAD_HEADER_LEN, 0);
785    out.pwrite_with(header, PROLOGUE_LEN, LE)
786        .expect("header space reserved");
787    out.extend_from_slice(&body);
788    Ok(out)
789}
790
791/// Compress `raw` with `codec` (body only, no outer header).
792///
793/// # Errors
794///
795/// [`Error::ZstdNotCompiled`] on `Codec::Zstd` when `utz_encode` was built
796/// without the `zstd` feature; [`Error::Compress`]/[`Error::Xz`] if the
797/// underlying compressor fails (not expected when writing to memory).
798pub fn compress(raw: &[u8], codec: Codec) -> crate::Result<Vec<u8>> {
799    let xz_err = |error| Error::Xz(format!("{error:?}"));
800    Ok(match codec {
801        Codec::Uncompressed => raw.to_vec(),
802        Codec::Gzip => miniz_oxide::deflate::compress_to_vec_zlib(raw, 10),
803        #[cfg(feature = "zstd")]
804        Codec::Zstd => {
805            use std::io::Write as _;
806            // Never declare a window larger than the content (decoders
807            // allocate the declared window), and cap at 2^26: ruzstd
808            // (utz's pure-Rust backend) refuses frames declaring over
809            // 100 MB. encode_all would let level 22 default to 2^27.
810            let window_log = raw.len().next_power_of_two().trailing_zeros().clamp(10, 26);
811            let mut encoder = zstd::stream::write::Encoder::new(Vec::new(), 22)?;
812            encoder.set_pledged_src_size(Some(raw.len() as u64))?;
813            encoder.window_log(window_log)?;
814            encoder.write_all(raw)?;
815            encoder.finish()?
816        }
817        #[cfg(not(feature = "zstd"))]
818        Codec::Zstd => return Err(Error::ZstdNotCompiled),
819        Codec::Brotli => {
820            let mut out = Vec::new();
821            let params = brotli::enc::BrotliEncoderParams {
822                quality: 11,
823                lgwin: 24,
824                ..Default::default()
825            };
826            brotli::BrotliCompress(&mut &raw[..], &mut out, &params)?;
827            out
828        }
829        Codec::Xz => {
830            use lzma_rust2::Write as _; // no_std lzma-rust2 (see utz/Cargo.toml)
831            let bits = (usize::BITS - (raw.len().max(1) - 1).leading_zeros()).clamp(12, 26);
832            let mut options = lzma_rust2::XzOptions::with_preset(9);
833            options.lzma_options.dict_size = 1u32 << bits;
834            // lzma-rust2 has no -9e helper; this is liblzma's extreme delta
835            options.lzma_options.nice_len = 273;
836            options.lzma_options.depth_limit = 512;
837            let mut writer = lzma_rust2::XzWriter::new(Vec::new(), options).map_err(xz_err)?;
838            writer.write_all(raw).map_err(xz_err)?;
839            writer.finish().map_err(xz_err)?
840        }
841    })
842}