open-standards/wai/live-conformance/browser_sink_verify.py

#!/usr/bin/env python3
"""Independent verifier of the browser-sink corpus (extensions/browser-sink.md).

Written from the extension's text. It shares no code with wai-rs, which generates the
corpus, and never runs it. It reads from the texts themselves the tables it works from:
the user agent's decoders (§4.1), the WebCodecs Codec Registry's rows (§4.2), the reasons
(§11), and the parameter register of capability-constraints §3.1. A capability's kind,
status and replicate class come from the registry export, registry/capabilities.json. It
hashes with ../claim-conformance/_blake3.py and checks Ed25519 signatures with
../claim-conformance/_ed25519.py, WAI's strict rule (SPEC §7 *Signatures*), both written
from their specifications with the standard library.

For every case of vectors.json it recomputes, from the text:

- `routes`: the report read or refused (§3), and each object's route, reason, legs,
  `asked`, tier and energy entry (§4, §6);
- `choices`: the choice table of §4.7, each choice's alternatives in SPEC §4's energy
  order and the one chosen;
- `constraints`: §5's outcome and reason;
- `bindings`: §7.1's reading and canonical form; `frame_tiers`: §7.2's tier;
- `chain`: each group receipt's signature (jwp-receipts §2.3, legacy form), its root and
  each object's inclusion (§2.2), its canonical bytes and link hash (§3 step 3), the
  second group's link to the first, whether each object verifies, and the binding a page
  writes for it on the wasm route;
- `frames`: §10's state; `tables`: §9.2's side table over each sequence.

It requires every reason of §11 to appear in the corpus and §11 to list exactly the codes
it knows. Then it mutates copies of the corpus, one defect each, and requires every copy to
fail; and it changes the answers the corpus gives for codec strings no registry row lists,
and requires the corpus still to pass, since those answers are never read (§4.2).

    python3 -I browser_sink_verify.py <live-conformance/browser> [<platform-decode-conformance>]

With the second directory it also reads platform-decode.md §2 and recomputes, from each
payload of its queries.json, the query a sink asks the platform (every codec string, size,
rate, bit rate and description) and the chunks of §2.3, with its own readers of SPEC §5's AV1
framing, IVF, Annex B, Ogg, FLAC and ADTS; then it mutates copies of those vectors and
requires every copy to fail.

Exit status 0 only if every check holds and every mutated copy fails. Python 3.8 or later;
standard library only.
"""
import copy
import json
import math
import os
import re
import struct
import sys

HERE = os.path.dirname(os.path.abspath(__file__))
WAI = os.path.normpath(os.path.join(HERE, ".."))
sys.path.insert(0, os.path.join(WAI, "claim-conformance"))
import _blake3 as B3  # noqa: E402
import _ed25519 as ED  # noqa: E402

TIERS = ["none", "entropy-consistency", "decode-equivalence"]
ALG = "jwp-object-1"
MAX_SAFE = 2 ** 53 - 1
CLASSES = ["CalibratedInstrument", "OnChipCounter", "ModelBased", "Estimator"]
# The registry export's labels of the replicate classes §2's table names.
CLASS_LABEL = {"StandardDefined": "standard-defined", "NeuralIntegerExact": "neural-int-exact",
               "NeuralEntropyExact": "neural-entropy-exact"}


def read(p):
    with open(p, encoding="utf-8") as f:
        return f.read()


def section(text, heading, stop):
    i = text.index(heading)
    j = text.index(stop, i + len(heading))
    return text[i:j]


def ticks(s):
    return re.findall(r"`([^`]*)`", s)


# ───────────────────────────── the texts' tables ─────────────────────────────

SPEC = read(os.path.join(WAI, "extensions", "browser-sink.md"))
CC = read(os.path.join(WAI, "extensions", "capability-constraints.md"))


def ua_rows():
    rows = []
    for line in section(SPEC, "### 4.1 ", "### 4.2 ").splitlines():
        if not line.startswith("| `"):
            continue
        cells = [c.strip() for c in line.strip().strip("|").split("|")]
        caps, decoder, forms, tier = ticks(cells[0]), ticks(cells[1])[0], ticks(cells[2]), ticks(cells[3])[0]
        rows.append({"caps": caps, "decoder": decoder, "forms": forms, "prefix": "and more" in cells[2], "tier": tier})
    assert rows, "§4.1 has no rows"
    return rows


def registry_rows():
    rows = []
    for line in section(SPEC, "### 4.2 ", "### 4.3 ").splitlines():
        if line.startswith("| video |") or line.startswith("| audio |"):
            rows += ticks(line)
    assert rows, "§4.2 has no rows"
    return rows


def reasons():
    out = []
    for line in section(SPEC, "## 11. Reasons", "## 12. ").splitlines():
        if line.startswith("| `"):
            out.append(ticks(line)[0])
    return out


def register():
    return [ticks(line)[0] for line in section(CC, "### 3.1 ", "\n## 4.").splitlines() if line.startswith("| `")]


def tier_by_class():
    out = {}
    for line in section(SPEC, "**Registered tier**", "`StandardDefined` is read").splitlines():
        line = line.strip()
        if line.startswith("| `") and "every other class" not in line:
            cells = line.strip().strip("|").split("|")
            for c in ticks(cells[0]):
                out[CLASS_LABEL[c]] = ticks(cells[1])[0]
    return out


UA_ROWS = ua_rows()
REGISTRY_ROWS = registry_rows()
REASONS = reasons()
REGISTER = register()
TIER_BY_CLASS = tier_by_class()
CAPS = {c["capability"]: c for c in json.loads(read(os.path.join(WAI, "registry", "capabilities.json")))["capabilities"]}


def rank(t):
    return TIERS.index(t) if t in TIERS else 0


def read_tier(t):
    return t if t in TIERS else "none"


def registered_tier(cap):
    c = CAPS.get(cap)
    return TIER_BY_CLASS.get(c["replicate"], "none") if c else "none"


def dispatchable(cap):
    c = CAPS.get(cap)
    if c is None:
        return True  # a string this revision does not register (SPEC §4)
    return c["kind"] == "payload" and c["status"] != "candidate"


def row_matches(row, s):
    if row.endswith("*"):
        p = row[:-1]
        return len(s) > len(p) and s.startswith(p)
    return s == row


def gate(codec):
    return any(row_matches(r, codec) for r in REGISTRY_ROWS)


def ua_row(cap):
    for r in UA_ROWS:
        if cap in r["caps"]:
            return r
    return None


def form_ok(row, codec):
    for f in row["forms"]:
        if row["prefix"] and f.endswith("."):
            if len(codec) > len(f) and codec.startswith(f):
                return True
        elif codec == f:
            return True
    return False


# ─────────────────────────────── §5 ───────────────────────────────

def integer(v):
    return v if isinstance(v, int) and not isinstance(v, bool) and -MAX_SAFE <= v <= MAX_SAFE else None


def is_value(v):
    return isinstance(v, str) or integer(v) is not None


def constraint_ok(c):
    if not isinstance(c, dict) or not c or any(k not in ("enum", "minimum", "maximum") for k in c):
        return False
    if "enum" in c and not (isinstance(c["enum"], list) and c["enum"] and all(is_value(x) for x in c["enum"])):
        return False
    for k in ("minimum", "maximum"):
        if k in c and integer(c[k]) is None:
            return False
    if "minimum" in c and "maximum" in c and c["minimum"] > c["maximum"]:
        return False
    return True


def meets(c, v):
    if v is None or not is_value(v):
        return False
    if "enum" in c:
        hit = False
        for x in c["enum"]:
            if isinstance(x, str) and isinstance(v, str) and x == v:
                hit = True
            if integer(x) is not None and integer(v) is not None and x == v:
                hit = True
        if not hit:
            return False
    if "minimum" in c and (integer(v) is None or v < c["minimum"]):
        return False
    if "maximum" in c and (integer(v) is None or v > c["maximum"]):
        return False
    return True


def evaluate(sets, params):
    """(outcome, reason)."""
    if sets is None:
        return "unconstrained", None
    if not isinstance(sets, list) or not sets:
        return "unevaluable", "constraint_malformed"
    for s in sets:
        if not isinstance(s, dict) or not all(constraint_ok(c) for c in s.values()):
            return "unevaluable", "constraint_malformed"
    for s in sets:
        if any(k not in REGISTER for k in s):
            return "unevaluable", "parameter_unregistered"
    params = params if isinstance(params, dict) else {}
    for s in sets:
        if all(meets(c, params.get(k)) for k, c in s.items()):
            return "satisfied", None
    return "unsatisfied", "constraints_unmet"


# ─────────────────────────────── §3, §4, §6 ───────────────────────────────

def is_bool_or_null(v):
    return v is None or isinstance(v, bool)


def report_reads(r):
    if not isinstance(r, dict):
        return False
    v = r.get("browser_sink")
    if isinstance(v, bool) or v != 1 or not isinstance(v, int):
        return False
    ua = r.get("ua")
    if not isinstance(ua, dict):
        return False
    for a in ua.values():
        if not (isinstance(a, dict) and isinstance(a.get("supported"), bool) and "smooth" in a and is_bool_or_null(a["smooth"])
                and "power_efficient" in a and is_bool_or_null(a["power_efficient"]) and a.get("probe") in ("match", "mismatch", "not_run")):
            return False
    if not (isinstance(r.get("host"), dict) and all(isinstance(x, str) for x in r["host"].values())):
        return False
    if not (isinstance(r.get("wasm"), list) and all(isinstance(x, str) for x in r["wasm"])):
        return False
    if not isinstance(r.get("constraints"), dict):
        return False
    if not (isinstance(r.get("energy"), dict) and all(isinstance(x, dict) for x in r["energy"].values())):
        return False
    objs = r.get("objects")
    if not isinstance(objs, list):
        return False
    for o in objs:
        if not (isinstance(o, dict) and isinstance(o.get("name"), str) and isinstance(o.get("capability"), str)
                and "codec" in o and (o["codec"] is None or isinstance(o["codec"], str))
                and isinstance(o.get("need"), str) and isinstance(o.get("params"), dict)):
            return False
        if "choice" in o and not (isinstance(o["choice"], str) and o["choice"]):
            return False
    return True


def positive(v):
    i = integer(v)
    return i is not None and i > 0


def read_measurement(m):
    cls = m.get("class")
    if cls not in CLASSES:
        return None, "energy_class_invalid"
    if integer(m.get("joules_micro")) == 0:
        return None, "unmetered_as_zero"
    if not all(positive(m.get(k)) for k in ("joules_micro", "decodes", "window_us")):
        return None, "energy_count_invalid"
    if cls in ("CalibratedInstrument", "OnChipCounter") and not positive(m.get("relative_ppm")):
        return None, "energy_evidence_missing"
    if cls == "OnChipCounter" and m.get("filtering") not in ("On", "Off", "Unknown"):
        return None, "energy_evidence_missing"
    if cls == "CalibratedInstrument" and not (isinstance(m.get("calibration_ref"), str) and m["calibration_ref"]):
        return None, "energy_evidence_missing"
    if m.get("coverage") not in ("Whole", "Partial"):
        return None, "energy_evidence_missing"
    f = m.get("fabrics")
    if not (isinstance(f, list) and f and all(isinstance(x, str) for x in f) and len(set(f)) == len(f)):
        return None, "energy_evidence_missing"
    out = dict(m)
    out["per_decode_micro"] = m["joules_micro"] // m["decodes"]
    return out, None


def energy_entry(r, cap, codec, route):
    pe = None
    if route == "ua" and codec in r["ua"]:
        pe = r["ua"][codec]["power_efficient"]
    figure, reason = None, None
    if route != "none":
        m = r["energy"].get(cap + " " + route)
        if m is not None:
            figure, reason = read_measurement(m)
    return {"power_efficient": pe, "figure": figure, "reason": reason}


def route_object(r, o):
    cap, codec, need = o["capability"], o["codec"], read_tier(o["need"])
    reg = registered_tier(cap)
    nr = "not_reached"

    def decided(reason):
        return {"name": o["name"], "route": "none", "reason": reason, "legs": {"ua": nr, "host": nr, "wasm": nr},
                "asked": False, "tier": "none", "energy": energy_entry(r, cap, codec, "none")}

    if not dispatchable(cap):
        return decided("not_dispatchable")
    if rank(need) > rank(reg):
        return decided("tier_exceeds_class")
    outcome, _ = evaluate(r["constraints"].get(cap), o["params"])
    if outcome == "unevaluable":
        return decided("constraints_unevaluable")
    if outcome == "unsatisfied":
        return decided("constraints_unmet")

    asked = False
    ua, ua_tier = None, None
    row = ua_row(cap)
    if codec is None:
        ua = "no_ua_mapping"
    elif not gate(codec):
        ua = "codec_unregistered"
    elif row is None:
        ua = "no_ua_mapping"
    elif not form_ok(row, codec):
        ua = "codec_mismatch"
    else:
        asked = True
        a = r["ua"].get(codec)
        if a is None:
            ua = "ua_not_asked"
        elif a["supported"] is not True:
            ua = "ua_unsupported"
        elif rank(need) > rank(row["tier"]):
            ua = "ua_inexact"
        elif need == "decode-equivalence" and a["probe"] != "match":
            ua = "ua_probe_mismatch" if a["probe"] == "mismatch" else "ua_unprobed"
        else:
            t = row["tier"] if a["probe"] == "match" else "none"
            ua_tier = TIERS[min(rank(t), rank(reg))]
    host, host_tier = None, None
    if cap not in r["host"]:
        host = "no_host"
    elif rank(read_tier(r["host"][cap])) < rank(need):
        host = "host_inexact"
    else:
        host_tier = TIERS[min(rank(read_tier(r["host"][cap])), rank(reg))]
    wasm, wasm_tier = None, None
    if cap in r["wasm"]:
        wasm_tier = reg
    else:
        wasm = "no_wasm"

    if ua_tier is not None:
        route, tier, legs = "ua", ua_tier, {"ua": "taken", "host": nr, "wasm": nr}
    elif host_tier is not None:
        route, tier, legs = "host", host_tier, {"ua": ua, "host": "taken", "wasm": nr}
    elif wasm_tier is not None:
        route, tier, legs = "wasm", wasm_tier, {"ua": ua, "host": host, "wasm": "taken"}
    else:
        route, tier, legs = "none", "none", {"ua": ua, "host": host, "wasm": wasm}
    return {"name": o["name"], "route": route, "reason": "no_decoder" if route == "none" else None, "legs": legs,
            "asked": asked, "tier": tier, "energy": energy_entry(r, cap, codec, route)}


def route_report(r):
    if not report_reads(r):
        return None, "report_malformed"
    return [route_object(r, o) for o in r["objects"]], None


# ─────────────────────────────── §7 ───────────────────────────────

# SPEC §4, *Energy order*: a learned capability is one whose registry class is not one of the
# three standard classes, or a string this revision does not register.
STANDARD = ("standard-defined", "standard-tolerance", "standard-unclassified")
RANKS = ["first", "smooth", "classical", "learned-without-budget"]


def learned(cap):
    c = CAPS.get(cap)
    return c is None or c["replicate"] not in STANDARD


def choose_report(r):
    """§4.7: (choice table, None) or (None, reason)."""
    table, reason = route_report(r)
    if reason is not None:
        return None, reason
    groups = []
    for i, o in enumerate(r["objects"]):
        if "choice" not in o:
            continue
        for g in groups:
            if g[0] == o["choice"]:
                g[1].append(i)
                break
        else:
            groups.append((o["choice"], [i]))

    def rank(i):
        e, o = table[i], r["objects"][i]
        if e["route"] == "none":
            return None
        cap = o["capability"]
        if learned(cap):
            # A sink-metered figure of its decode under its route's key (§6) that reads, with a
            # hardware class and coverage Whole; its value is not read.
            m = r["energy"].get("%s %s" % (cap, e["route"]))
            ok = m is not None and read_measurement(m)[1] is None and m.get("class") in ("OnChipCounter", "CalibratedInstrument") and m.get("coverage") == "Whole"
            return "classical" if ok else "learned-without-budget"
        if e["route"] == "ua":
            a = r["ua"].get(o["codec"]) or {}
            if a.get("supported") is True and a.get("smooth") is True and a.get("power_efficient") is True:
                return "first"
            if a.get("smooth") is True:
                return "smooth"
        return "classical"

    out = []
    for choice, members in groups:
        ranked = [(rank(i), i) for i in members]
        order = sorted(ranked, key=lambda x: (RANKS.index(x[0]) if x[0] is not None else len(RANKS), x[1]))
        chosen = next((i for rk, i in order if rk is not None), None)
        out.append({"choice": choice, "order": [r["objects"][i]["name"] for _, i in order],
                    "ranks": [rk for rk, _ in order],
                    "chosen": None if chosen is None else r["objects"][chosen]["name"],
                    "reason": None if chosen is not None else "no_alternative"})
    return out, None


def hex32(s):
    return isinstance(s, str) and re.fullmatch(r"[0-9a-f]{64}", s) is not None


def read_binding(v):
    """(binding dict in member order, None) or (None, reason)."""
    if not isinstance(v, dict):
        return None, "binding_malformed"
    for k in ("alg", "digest", "tier"):
        if not isinstance(v.get(k), str):
            return None, "binding_malformed"
    if not hex32(v["digest"]):
        return None, "binding_malformed"
    if "receipt" in v and not hex32(v["receipt"]):
        return None, "binding_malformed"
    if v["alg"] != ALG:
        return None, "binding_alg_unknown"
    b = {"alg": ALG, "digest": v["digest"]}
    if "receipt" in v:
        b["receipt"] = v["receipt"]
    b["tier"] = read_tier(v["tier"])
    return b, None


def canonical(b):
    return json.dumps(b, separators=(",", ":"), ensure_ascii=False)


def frame_tier(route, route_tier, format_null, altered):
    if altered or (route == "ua" and format_null):
        return "none"
    return route_tier


def frame_state(binding, obj, chain, prov):
    b, reason = (None, None) if binding is None else read_binding(binding)
    if b is None:
        return {"state": "unbound", "reason": reason, "tier": None, "digest": None, "receipt": None}
    if "refused" in (obj, chain, prov):
        s = "refused"
    elif obj == "unverified" or chain == "held" or prov == "missing":
        s = "pending"
    else:
        s = "verified"
    return {"state": s, "reason": None, "tier": b["tier"], "digest": b["digest"], "receipt": b.get("receipt")}


# ─────────────────────────────── §9.2 ───────────────────────────────

def run_table(bound, ops):
    pending, frames, refusals, struck = {}, {}, [], 0
    STRUCK = object()
    for i, op in enumerate(ops):
        k = op["op"]
        if k == "chunk":
            q = pending.setdefault(op["decoder"], [])
            b = None
            if op.get("binding") is not None:
                b, why = read_binding(op["binding"])
                if b is None:
                    raise ValueError("op %d: binding %s" % (i, why))
            hit = [e for e in q if e[0] == op["timestamp"]]
            if hit:
                if hit[0][1] is not STRUCK:
                    refusals.append({"at": i, "reason": "binding_ambiguous"})
                hit[0][1] = STRUCK
            else:
                q.append([op["timestamp"], b])
                if len(q) > bound:
                    q.pop(0)
                    struck += 1
        elif k == "output":
            q = pending.setdefault(op["decoder"], [])
            b = None
            for j, e in enumerate(q):
                if e[0] == op["timestamp"]:
                    q.pop(j)
                    b = None if e[1] is STRUCK else e[1]
                    break
            frames[op["frame"]] = b
        elif k == "clone":
            frames[op["frame"]] = frames[op["from"]]
        elif k == "transfer":
            b = frames.pop(op["from"])
            frames[op["frame"]] = b if op.get("with_binding") is True else None
        elif k == "close":
            frames.pop(op["frame"], None)
        elif k in ("reset", "flush"):
            struck += len(pending.pop(op["decoder"], []))
        else:
            raise ValueError("op %d: %r" % (i, k))
    return {"frames": {f: (canonical(b) if b is not None else None) for f, b in frames.items()},
            "refusals": refusals, "struck": struck}


# ─────────────────────────────── the chain ───────────────────────────────

_HASHES = {}


def b3(data):
    data = bytes(data)
    h = _HASHES.get(data)
    if h is None:
        h = _HASHES[data] = B3.blake3(data)
    return h


def u64(n):
    return n.to_bytes(8, "big")


def lp(s):
    b = s.encode("utf-8")
    return len(b).to_bytes(4, "big") + b


def check_chain(chain, load, fails):
    prev_link = None
    for gi, g in enumerate(chain["groups"]):
        r = g["receipt"]
        pk, sig = bytes.fromhex(r["signer_pubkey"]), bytes.fromhex(r["sig"])
        payload = (b"moq-jwp:group-sign\x01" + u64(r["track_alias"]) + u64(r["group_id"]) + bytes.fromhex(r["root_hash"])
                   + u64(r["leaf_count"]) + u64(r["joules_total"]) + lp(r["group_start"]) + lp(r["group_end"]) + pk + lp(r["signer_id"]))
        if ED.verify(pk, payload, sig) is not None:
            fails.append("chain group %d: the signature does not verify" % gi)
        if r["signer_pubkey"] != chain["signer_pubkey"]:
            fails.append("chain group %d: another key" % gi)
        can = payload + sig
        if can.hex() != g["canonical"]:
            fails.append("chain group %d: canonical bytes" % gi)
        link = b3(b"moq-jwp:receipt-link\x01" + can)
        if link.hex() != g["link_hash"]:
            fails.append("chain group %d: link hash" % gi)
        want_parent = prev_link.hex() if prev_link is not None else None
        if r["parent_receipt_hash"] != want_parent:
            fails.append("chain group %d: parent link" % gi)
        prev_link = link
        for o in g["objects"]:
            env = load(o["envelope"]["file"]) if isinstance(o["envelope"], dict) else bytes.fromhex(o["envelope"])
            orc = o["receipt"]
            ch = b3(b"moq-jwp:object\x01" + env)
            ok = ch.hex() == orc["content_hash"]
            if (orc["track_alias"], orc["group_id"]) != (r["track_alias"], r["group_id"]) or orc["merkle_proof"]["leaf_index"] != orc["object_id"]:
                ok = False
            h = b3(b"moq-jwp:merkle-leaf\x01" + bytes.fromhex(orc["content_hash"]))
            bits = orc["merkle_proof"]["direction_bits"]
            for i, s in enumerate(orc["merkle_proof"]["siblings"]):
                s = bytes.fromhex(s)
                h = b3(b"moq-jwp:merkle-node\x01" + (s + h if (bits >> i) & 1 else h + s))
            if h.hex() != r["root_hash"]:
                ok = False
            want = "verified" if ok else "refused"
            if o["outcome"] != want:
                fails.append("chain %s: %s, the corpus says %s" % (o["name"], want, o["outcome"]))
            if ok:
                tier = frame_tier(chain["route"], registered_tier(chain["capability"]), False, False)
                b = canonical({"alg": ALG, "digest": ch.hex(), "receipt": link.hex(), "tier": tier})
                if o["binding"] != b:
                    fails.append("chain %s: binding %s" % (o["name"], o["binding"]))
            elif o["binding"] is not None:
                fails.append("chain %s: a binding for an object that does not verify" % o["name"])


# ─────────────────────────────── the corpus ───────────────────────────────

def verify(doc, load):
    fails = []
    seen = set()

    def take(x):
        if isinstance(x, str):
            seen.add(x)

    for c in doc["routes"]:
        table, reason = route_report(c["report"])
        if reason is not None:
            if c["outcome"] != "refused" or c["reason"] != reason or c["table"] is not None:
                fails.append("route %s: refused %s" % (c["name"], reason))
        elif c["outcome"] != "routed" or c["reason"] is not None or c["table"] != table:
            got = {e["name"]: (e["route"], e["reason"]) for e in table}
            fails.append("route %s: %s" % (c["name"], json.dumps(got)[:300]))
        take(c["reason"])
        for e in c["table"] or []:
            take(e["reason"])
            take(e["energy"]["reason"])
            for leg in e["legs"].values():
                take(leg)
    for c in doc["choices"]:
        got, reason = choose_report(c["report"])
        table = route_report(c["report"])[0] if reason is None else None
        want = ("refused", reason, None, None) if reason is not None else ("chosen", None, table, got)
        if want != (c["outcome"], c["reason"], c["table"], c["choices"]):
            fails.append("choice %s: %s" % (c["name"], json.dumps(got if got is not None else reason)[:300]))
        take(c["reason"])
        for g in c["choices"] or []:
            take(g["reason"])
    for c in doc["constraints"]:
        o, r = evaluate(c["sets"], c["params"])
        if (o, r) != (c["outcome"], c["reason"]):
            fails.append("constraints %s: %s %s" % (c["name"], o, r))
        take(r)
    for c in doc["bindings"]:
        b, r = read_binding(c["value"])
        got = ("read", None, canonical(b), b["tier"]) if b else ("refused", r, None, None)
        if got != (c["outcome"], c["reason"], c["canonical"], c["tier"]):
            fails.append("binding %s: %s" % (c["name"], got))
        take(r)
    for c in doc["frame_tiers"]:
        if frame_tier(c["route"], c["route_tier"], c["format_null"], c["altered"]) != c["tier"]:
            fails.append("frame tier %s" % c)
    check_chain(doc["chain"], load, fails)
    for g in doc["chain"]["groups"]:
        for o in g["objects"]:
            if o["outcome"] == "refused":
                seen.add("binding_unverified_reference")
    for c in doc["frames"]:
        s = frame_state(c["binding"], c["object"], c["chain"], c["provenance"])
        if s != c["result"]:
            fails.append("frame %s: %s" % (c["name"], s))
    for c in doc["tables"]:
        try:
            r = run_table(c["bound"], c["ops"])
        except (KeyError, ValueError) as e:
            fails.append("table %s: %s" % (c["name"], e))
            continue
        if r != c["result"]:
            fails.append("table %s: %s" % (c["name"], r))
        for x in r["refusals"]:
            take(x["reason"])
    for code in REASONS:
        if code not in seen:
            fails.append("nothing in the corpus gives %s" % code)
    return fails


# ─────────────────── platform-decode §2: the query read from a payload ───────────────────
#
# A second reading of the queries of platform-decode.md §2, from its text: every codec string,
# size, rate, bit rate and description, and the chunks of §2.3, recomputed from each payload of
# platform-decode-conformance/queries.json. It reads §2.1's VP9 level and colour tables from the
# text.

PD = read(os.path.join(WAI, "extensions", "platform-decode.md"))


class Refused(Exception):
    pass


def need(cond, why):
    if not cond:
        raise Refused(why)


def vp9_levels():
    out = []
    for line in section(PD, "**VP9 levels.**", "**VP9 colour.**").splitlines():
        if line.startswith("| `"):
            cells = [c.strip().strip("`").replace(" ", "") for c in line.strip().strip("|").split("|")]
            out.append((int(cells[0]), int(cells[1]), int(cells[2]), int(cells[3])))
    need(len(out) == 14, "platform-decode §2.1 lists %d VP9 levels" % len(out))
    return out


def vp9_matrix():
    out = {}
    for line in section(PD, "**VP9 colour.**", "### 2.2").splitlines():
        cells = [c.strip() for c in line.strip().strip("|").split("|")]
        if line.startswith("| `") and ticks(cells[0])[0].isdigit():
            out[int(ticks(cells[0])[0])] = ticks(cells[2])[0]
    return out


class BitReader:
    def __init__(self, b):
        self.b, self.at = b, 0

    def f(self, n):
        v = 0
        for _ in range(n):
            need(self.at < 8 * len(self.b), "a header runs past its data")
            v = (v << 1) | ((self.b[self.at >> 3] >> (7 - (self.at & 7))) & 1)
            self.at += 1
        return v

    def ue(self):
        z = 0
        while self.f(1) == 0:
            z += 1
            need(z <= 31, "an exp-Golomb code too long")
        return (1 << z) - 1 + self.f(z)

    def uvlc(self):
        z = 0
        while self.f(1) == 0:
            z += 1
            need(z <= 32, "a uvlc() too long")
        return 0xFFFFFFFF if z >= 32 else (1 << z) - 1 + self.f(z)


def leb128(b, at):
    v = 0
    for i in range(8):
        need(at + i < len(b), "an OBU size runs past its unit")
        v |= (b[at + i] & 0x7F) << (7 * i)
        if not b[at + i] & 0x80:
            return v, i + 1
    raise Refused("an OBU size longer than eight bytes")


def ceil_div(a, b):
    return -(-a // b)


def bitrate(nbytes, frames, rate):
    if rate is None or frames == 0:
        return None
    return ceil_div(nbytes * 8 * rate[0], frames * rate[1])


def unescape(nal, header):
    out, zeros = bytearray(), 0
    for x in nal[header:]:
        if zeros >= 2 and x == 3:
            zeros = 0
            continue
        zeros = zeros + 1 if x == 0 else 0
        out.append(x)
    return bytes(out)


# AV1: SPEC §5's framing and the sequence header (AV1 §5.5).

def av1_sequence(body):
    r = BitReader(body)
    prof = r.f(3)
    need(prof <= 2, "seq_profile %d" % prof)
    r.f(1)
    reduced = r.f(1)
    lvl = tier = 0
    if reduced:
        lvl = r.f(5)
    else:
        timing = r.f(1)
        dmi, bdl = 0, 0
        if timing:
            r.f(64)
            if r.f(1):
                r.uvlc()
            dmi = r.f(1)
            if dmi:
                bdl = r.f(5) + 1
                r.f(42)
        idp = r.f(1)
        for i in range(r.f(5) + 1):
            r.f(12)
            lv = r.f(5)
            ti = r.f(1) if lv > 7 else 0
            if dmi and r.f(1):
                r.f(2 * bdl + 1)
            if idp and r.f(1):
                r.f(4)
            if i == 0:
                lvl, tier = lv, ti
    wb, hb = r.f(4) + 1, r.f(4) + 1
    r.f(wb + hb)
    if not reduced and r.f(1):
        r.f(7)
    r.f(3)
    if not reduced:
        r.f(4)
        oh = r.f(1)
        if oh:
            r.f(2)
        sct = 2 if r.f(1) else r.f(1)
        if sct > 0 and not r.f(1):
            r.f(1)
        if oh:
            r.f(3)
    r.f(3)
    hbd = r.f(1)
    depth = 12 if (prof == 2 and hbd and r.f(1)) else (10 if hbd else 8)
    mono = r.f(1) if prof != 1 else 0
    desc = (r.f(8), r.f(8), r.f(8)) if r.f(1) else None
    if mono:
        rng, sx, sy, csp = r.f(1), 1, 1, 0
    elif desc == (1, 13, 0):
        rng, sx, sy, csp = 1, 0, 0, 0
    else:
        rng = r.f(1)
        if prof == 0:
            sx, sy = 1, 1
        elif prof == 1:
            sx, sy = 0, 0
        elif depth == 12:
            sx = r.f(1)
            sy = r.f(1) if sx else 0
        else:
            sx, sy = 1, 0
        csp = r.f(2) if sx and sy else 0
    cp, tc, mc = desc or (1, 1, 1)
    head = "av01.%d.%02d%s.%02d" % (prof, lvl, "H" if tier else "M", depth)
    tail = ".%d.%d%d%d.%02d.%02d.%02d.%d" % (mono, sx, sy, csp if sx and sy else 0, cp, tc, mc, rng)
    return {"codec": head if tail == ".0.110.01.01.01.0" else head + tail, "depth": depth, "reduced": reduced}


def av1_obus(tu):
    at = 0
    while at < len(tu):
        h = tu[at]
        need(not h & 0x80, "an OBU whose forbidden bit is set")
        need(h & 2, "an OBU without its size field")
        hl = 2 if h & 4 else 1
        size, sl = leb128(tu, at + hl)
        st = at + hl + sl
        need(st + size <= len(tu), "an OBU runs past its unit")
        yield (h >> 3) & 15, tu[st:st + size]
        at = st + size


def av1_units(p):
    need(len(p) >= 20, "short AV1 framing")
    n, h, w, fn, fd = struct.unpack_from("<5I", p, 0)
    need(n and h and w, "no frames or a zero size")
    units, at = [], 20
    while at < len(p):
        need(at + 4 <= len(p), "a unit length runs past")
        ln = struct.unpack_from("<I", p, at)[0]
        need(ln > 0 and at + 4 + ln <= len(p), "a unit runs past, or is empty")
        units.append(p[at + 4:at + 4 + ln])
        at += 4 + ln
    need(len(units) == n, "%d units where the framing says %d" % (len(units), n))
    return n, h, w, fn, fd, units


def av1_query(p):
    n, h, w, fn, fd, units = av1_units(p)
    seq = None
    for t, body in av1_obus(units[0]):
        if t == 1:
            seq = av1_sequence(body)
            break
    need(seq, "no sequence header in the first unit")
    rate = (fn, fd) if fn and fd else None
    return {"media": "video", "codec": seq["codec"], "width": w, "height": h, "codedWidth": w, "codedHeight": h,
            "framerate": list(rate) if rate else None, "bitrate": bitrate(len(p), n, rate), "bitDepth": seq["depth"]}


def av1_chunks(p):
    units = av1_units(p)[5]
    out, reduced = [], None
    for tu in units:
        key = None
        for t, body in av1_obus(tu):
            if t == 1:
                reduced = av1_sequence(body)["reduced"]
            elif t in (3, 6) and key is None:
                need(reduced is not None, "a frame header before a sequence header")
                r = BitReader(body)
                key = True if reduced else (r.f(1) == 0 and r.f(2) == 0)
        need(key is not None, "a unit with no frame header")
        out.append((tu, key, None))
    return None, out


# Annex B (H.264, H.265).

def nal_units(s):
    starts, i = [], 0
    while i + 3 <= len(s):
        if s[i] == 0 and s[i + 1] == 0 and s[i + 2] == 1:
            starts.append((i - 1 if i > 0 and s[i - 1] == 0 else i, i + 3))
            i += 3
        else:
            i += 1
    out = []
    for k, (sc, st) in enumerate(starts):
        end = starts[k + 1][0] if k + 1 < len(starts) else len(s)
        while end > st and s[end - 1] == 0:
            end -= 1
        out.append((sc, s[st:end]))
    return out


def hevc_sps(nal):
    need(len(nal) >= 3 and (nal[0] >> 1) & 63 == 33, "not an SPS")
    r = BitReader(unescape(nal, 2))
    r.f(4)
    subs = r.f(3)
    r.f(1)
    space, tier, idc = r.f(2), r.f(1), r.f(5)
    compat = 0
    for j in range(32):
        compat |= r.f(1) << j
    cons = [r.f(8) for _ in range(6)]
    level = r.f(8)
    flags = [(r.f(1), r.f(1)) for _ in range(subs)]
    if subs:
        r.f(2 * (8 - subs))
    for pr, lv in flags:
        r.f(88 if pr else 0)
        r.f(8 if lv else 0)
    r.ue()
    chroma = r.ue()
    need(chroma <= 3, "chroma_format_idc")
    sep = r.f(1) if chroma == 3 else 0
    w, h = r.ue(), r.ue()
    cw, ch = w, h
    if r.f(1):
        l, rt, t, b = r.ue(), r.ue(), r.ue(), r.ue()
        sw, sh = {1: (2, 2), 2: (2, 1)}.get(chroma, (1, 1))
        cw, ch = w - sw * (l + rt), h - sh * (t + b)
        need(cw >= 0 and ch >= 0, "a window larger than the picture")
    depth = r.ue() + 8
    codec = "hev1.%s%d.%X.%s%d" % (["", "A", "B", "C"][space], idc, compat, "H" if tier else "L", level)
    last = max([i for i, c in enumerate(cons) if c] or [-1])
    codec += "".join(".%X" % c for c in cons[:last + 1])
    return {"codec": codec, "width": cw, "height": ch, "codedWidth": w, "codedHeight": h, "bitDepth": depth}


AVC_HIGH = (100, 110, 122, 244, 44, 83, 86, 118, 128, 138, 139, 134, 135)


def avc_sps(nal):
    need(len(nal) >= 4 and nal[0] & 0x1F == 7 and not nal[0] & 0x80, "not an SPS")
    r = BitReader(unescape(nal, 1))
    prof, cons, level = r.f(8), r.f(8), r.f(8)
    r.ue()
    chroma, sep, depth = 1, 0, 8
    if prof in AVC_HIGH:
        chroma = r.ue()
        need(chroma <= 3, "chroma_format_idc")
        if chroma == 3:
            sep = r.f(1)
        depth = r.ue() + 8
        r.ue()
        r.f(1)
        if r.f(1):
            for i in range(8 if chroma != 3 else 12):
                if r.f(1):
                    last = nxt = 8
                    for _ in range(16 if i < 6 else 64):
                        if nxt:
                            c = r.ue()
                            nxt = (last + ((c + 1) // 2 if c % 2 else -(c // 2))) % 256
                        last = nxt or last
    need(depth <= 14, "bit depth")
    r.ue()
    poc = r.ue()
    if poc == 0:
        r.ue()
    elif poc == 1:
        r.f(1)
        r.ue()
        r.ue()
        k = r.ue()
        need(k <= 255, "a long POC cycle")
        for _ in range(k):
            r.ue()
    else:
        need(poc == 2, "pic_order_cnt_type")
    r.ue()
    r.f(1)
    wm, hu = r.ue() + 1, r.ue() + 1
    fmo = r.f(1)
    if not fmo:
        r.f(1)
    r.f(1)
    l = rt = t = b = 0
    if r.f(1):
        l, rt, t, b = r.ue(), r.ue(), r.ue(), r.ue()
    arr = 0 if sep else chroma
    sw, sh = {1: (2, 2), 2: (2, 1)}.get(arr, (1, 1))
    fld = 1 if fmo else 2
    cx, cy = (1, fld) if arr == 0 else (sw, sh * fld)
    w, h = wm * 16, hu * 16 * fld
    cw, ch = w - cx * (l + rt), h - cy * (t + b)
    need(cw > 0 and ch > 0, "a cropping rectangle that leaves no picture")
    return {"codec": "avc1.%02X%02X%02X" % (prof, cons, level), "width": cw, "height": ch, "codedWidth": w, "codedHeight": h,
            "bitDepth": depth}


def first_slice(nal, avc):
    if avc:
        return len(nal) >= 2 and nal[0] & 0x1F in (1, 5) and nal[1] & 0x80
    return len(nal) >= 3 and (nal[0] >> 1) & 63 <= 31 and nal[2] & 0x80


def annexb_query(p, rate, avc):
    nals = nal_units(p)
    sps = [n for _, n in nals if n and (n[0] & 0x1F == 7 if avc else len(n) >= 2 and (n[0] >> 1) & 63 == 33)]
    need(sps, "no SPS")
    q = (avc_sps if avc else hevc_sps)(sps[0])
    pics = sum(1 for _, n in nals if first_slice(n, avc))
    q.update(media="video", framerate=list(rate) if rate else None, bitrate=bitrate(len(p), pics, rate))
    return q


def annexb_chunks(p, avc):
    units = []
    for sc, n in nal_units(p):
        if not n:
            continue
        t = n[0] & 0x1F if avc else (n[0] >> 1) & 63
        vcl = t in (1, 5) if avc else t <= 31
        starts = t in (6, 7, 8, 9, 14, 15, 16, 17, 18) if avc else t in (32, 33, 34, 35, 39, 41, 42, 43, 44) or 48 <= t <= 55
        if not units or (units[-1][1] and (starts or first_slice(n, avc))):
            units.append([sc, False, False])
        if vcl:
            units[-1][1] = True
            units[-1][2] |= (t == 5) if avc else 16 <= t <= 23
    if len(units) > 1 and not units[-1][1]:
        units.pop()
    need(any(u[1] for u in units), "no VCL unit")
    out = []
    for k, (st, _, key) in enumerate(units):
        end = units[k + 1][0] if k + 1 < len(units) else len(p)
        out.append((p[st:end], key, None))
    need(out[0][1], "the first access unit is not a key one")
    return None, out


# IVF (VP9, VP8).

def ivf(p, fourcc):
    need(len(p) >= 32 and p[:4] == b"DKIF", "not IVF")
    ver, hl = struct.unpack_from("<HH", p, 4)
    need(ver == 0 and 32 <= hl <= len(p), "IVF header")
    need(p[8:12] == fourcc, "IVF FourCC")
    den, num = struct.unpack_from("<II", p, 16)
    frames, at = [], hl
    while at < len(p):
        need(at + 12 <= len(p), "a frame header runs past")
        n, pts = struct.unpack_from("<IQ", p, at)
        need(n > 0 and at + 12 + n <= len(p), "a frame runs past, or is empty")
        frames.append((pts, p[at + 12:at + 12 + n]))
        at += 12 + n
    need(frames, "no frames")
    rate = None
    k = len(frames)
    if k >= 2 and den and num and frames[-1][0] > frames[0][0]:
        a, b = (k - 1) * den, (frames[-1][0] - frames[0][0]) * num
        g = math.gcd(a, b)
        if a // g < 2 ** 32 and b // g < 2 ** 32:
            rate = (a // g, b // g)
    return frames, rate


def vp9_key(f):
    r = BitReader(f)
    need(r.f(2) == 2, "frame_marker")
    lo = r.f(1)
    prof = (r.f(1) << 1) | lo
    if prof == 3:
        need(r.f(1) == 0, "reserved_zero")
    if r.f(1):
        return None
    ft = r.f(1)
    r.f(2)
    if ft:
        return None
    need(r.f(24) == 0x498342, "frame_sync_code")
    depth = (12 if r.f(1) else 10) if prof >= 2 else 8
    cs = r.f(3)
    if cs != 7:
        rng = r.f(1)
        if prof in (1, 3):
            sx, sy = r.f(1), r.f(1)
            r.f(1)
        else:
            sx = sy = 1
    else:
        need(prof in (1, 3), "RGB in profile 0 or 2")
        rng, sx, sy = 1, 0, 0
        r.f(1)
    need(cs != 6, "the reserved colour space")
    return {"profile": prof, "depth": depth, "cs": cs, "range": rng, "sx": sx, "sy": sy, "w": r.f(16) + 1, "h": r.f(16) + 1}


def vp9_query(p, given):
    frames, rate = ivf(p, b"VP90")
    k = vp9_key(frames[0][1])
    need(k, "the first frame is not a key frame")
    rate = rate or given
    w, h = k["w"], k["h"]
    lvl = None
    for value, max_rate, max_size, breadth in vp9_levels():
        if w * h <= max_size and max(w, h) <= breadth and (rate is None or w * h * rate[0] <= max_rate * rate[1]):
            lvl = value
            break
    need(lvl is not None, "past every level")
    sub = {(1, 1): "01", (1, 0): "02", (0, 0): "03"}.get((k["sx"], k["sy"]))
    need(sub, "4:4:0")
    head = "vp09.%02d.%02d.%02d" % (k["profile"], lvl, k["depth"])
    tail = ".%s.01.01.%s.%02d" % (sub, vp9_matrix()[k["cs"]], k["range"])
    return {"media": "video", "codec": head if tail == ".01.01.01.01.00" else head + tail, "width": w, "height": h,
            "codedWidth": w, "codedHeight": h, "framerate": list(rate) if rate else None,
            "bitrate": bitrate(len(p), len(frames), rate), "bitDepth": k["depth"]}


def vp8_key(f):
    need(len(f) >= 3, "a short frame")
    tag = f[0] | f[1] << 8 | f[2] << 16
    need((tag >> 1) & 7 <= 3, "a VP8 version past 3")
    if tag & 1:
        return None
    need(len(f) >= 10 and f[3:6] == b"\x9d\x01\x2a", "the key frame start code")
    w, h = struct.unpack_from("<HH", f, 6)
    need(w & 0x3FFF and h & 0x3FFF, "a zero size")
    return w & 0x3FFF, h & 0x3FFF


def vp8_query(p, given):
    frames, rate = ivf(p, b"VP80")
    k = vp8_key(frames[0][1])
    need(k, "the first frame is not a key frame")
    rate = rate or given
    return {"media": "video", "codec": "vp8", "width": k[0], "height": k[1], "codedWidth": k[0], "codedHeight": k[1],
            "framerate": list(rate) if rate else None, "bitrate": bitrate(len(p), len(frames), rate), "bitDepth": 8}


def ivf_chunks(p, fourcc):
    frames, _ = ivf(p, fourcc)
    out = [(f, (vp9_key(f) if fourcc == b"VP90" else vp8_key(f)) is not None, None) for _, f in frames]
    need(out[0][1], "the first frame is not a key frame")
    return None, out


# Audio.

def audio(codec, rate, ch, br, depth, desc):
    q = {"media": "audio", "codec": codec, "sampleRate": rate, "numberOfChannels": ch, "bitrate": br, "bitDepth": depth,
         "description": desc.hex() if desc is not None else None}
    a = {"contentType": 'audio/mp4; codecs="%s"' % codec, "channels": str(ch), "samplerate": rate}
    if br is not None:
        a["bitrate"] = br
    q["decodingConfiguration"] = {"type": "media-source", "audio": a}
    q["decoderConfig"] = {"codec": codec, "sampleRate": rate, "numberOfChannels": ch}
    return q


def rate_over(nbytes, samples, rate):
    return ceil_div(nbytes * 8 * rate, samples) if samples > 0 else None


def crc32_ogg(page):
    c = 0
    for i, x in enumerate(page):
        c ^= (0 if 22 <= i < 26 else x) << 24
        for _ in range(8):
            c = ((c << 1) ^ 0x104C11DB7) if c & 0x80000000 else c << 1
    return c & 0xFFFFFFFF


def ogg(p):
    pkts, cur, at, serial, seq, gran = [], None, 0, None, None, None
    while at < len(p):
        need(at + 27 <= len(p) and p[at:at + 4] == b"OggS" and p[at + 4] == 0, "an Ogg page header")
        flags = p[at + 5]
        g, s, n, crc = struct.unpack_from("<QIII", p, at + 6)
        nseg = p[at + 26]
        lace = p[at + 27:at + 27 + nseg]
        end = at + 27 + nseg + sum(lace)
        need(len(lace) == nseg and end <= len(p), "an Ogg page runs past")
        need(crc32_ogg(p[at:end]) == crc, "an Ogg CRC")
        if serial is None:
            need(flags & 2, "the first page does not begin the stream")
            serial = s
        else:
            need(s == serial and not flags & 2, "a multiplexed or chained stream")
            need(n == (seq + 1) & 0xFFFFFFFF, "a page out of sequence")
        seq = n
        need(bool(flags & 1) == (cur is not None), "a continuation flag")
        o = at + 27 + nseg
        for x in lace:
            cur = (cur or b"") + p[o:o + x]
            o += x
            if x < 255:
                pkts.append(cur)
                cur = None
        if g != 0xFFFFFFFFFFFFFFFF:
            gran = g
        at = end
    need(cur is None and serial is not None, "a packet runs past the last page")
    return pkts, gran


def opus_samples(pk):
    need(len(pk) >= 1, "an empty packet")
    cfg = pk[0] >> 3
    frame = (480, 960, 1920, 2880)[cfg % 4] if cfg < 12 else ((480, 960)[cfg % 2] if cfg < 16 else (120, 240, 480, 960)[cfg % 4])
    code = pk[0] & 3
    if code == 0:
        cnt = 1
    elif code in (1, 2):
        cnt = 2
    else:
        need(len(pk) >= 2 and pk[1] & 0x3F, "a code 3 packet with no count")
        cnt = pk[1] & 0x3F
    need(frame * cnt <= 5760, "more than 120 ms")
    return frame * cnt


def ogg_opus(p):
    pkts, gran = ogg(p)
    need(pkts and len(pkts[0]) >= 19 and pkts[0][:8] == b"OpusHead" and pkts[0][8] >> 4 == 0, "OpusHead")
    head = pkts[0]
    ch, fam = head[9], head[18]
    need(ch >= 1 and not (fam == 0 and ch > 2), "channels")
    if fam:
        need(len(head) >= 21 + ch and head[19] >= 1 and head[20] <= head[19], "a channel mapping table")
    need(len(pkts) >= 3 and pkts[1][:8] == b"OpusTags", "OpusTags and an audio packet")
    for a in pkts[2:]:
        opus_samples(a)
    return pkts, gran, ch, struct.unpack_from("<H", head, 10)[0]


def opus_query(p):
    pkts, gran, ch, skip = ogg_opus(p)
    br = rate_over(len(p), gran - skip, 48000) if gran is not None and gran >= skip else None
    return audio("opus", 48000, ch, br, None, pkts[0])


def opus_chunks(p):
    pkts = ogg_opus(p)[0]
    return pkts[0], [(a, True, opus_samples(a)) for a in pkts[2:]]


def packet_query(p):
    n = opus_samples(p)
    return audio("opus", 48000, 2 if p[0] & 4 else 1, rate_over(len(p), n, 48000), None, None)


def flac_meta(p):
    need(p[:4] == b"fLaC", "fLaC")
    at, info = 4, None
    while True:
        need(at + 4 <= len(p), "a block header runs past")
        last, kind = p[at] >> 7, p[at] & 0x7F
        ln = int.from_bytes(p[at + 1:at + 4], "big")
        need(at + 4 + ln <= len(p) and kind != 127, "a metadata block")
        if info is None:
            need(kind == 0 and ln == 34, "STREAMINFO first")
            b = p[at + 4:at + 38]
            v = int.from_bytes(b[10:18], "big")
            info = {"min": int.from_bytes(b[0:2], "big"), "max": int.from_bytes(b[2:4], "big"), "rate": v >> 44,
                    "ch": ((v >> 41) & 7) + 1, "bps": ((v >> 36) & 31) + 1, "total": v & 0xFFFFFFFFF}
            need(info["rate"] and info["bps"] >= 4 and 16 <= info["min"] <= info["max"], "STREAMINFO values")
        else:
            need(kind != 0, "a second STREAMINFO")
        at += 4 + ln
        if last:
            return info, at


def crc8(b):
    c = 0
    for x in b:
        c ^= x
        for _ in range(8):
            c = ((c << 1) ^ 0x07) & 0xFF if c & 0x80 else (c << 1) & 0xFF
    return c


def crc16(c, x):
    c ^= x << 8
    for _ in range(8):
        c = ((c << 1) ^ 0x8005) & 0xFFFF if c & 0x8000 else (c << 1) & 0xFFFF
    return c


def flac_header(p, at):
    b = p[at:at + 32]
    if len(b) < 6 or b[0] != 0xFF or b[1] & 0xFE != 0xF8:
        return None
    bs, sr, ch, dp = b[2] >> 4, b[2] & 15, b[3] >> 4, (b[3] >> 1) & 7
    if bs == 0 or sr == 15 or ch > 10 or dp == 3 or b[3] & 1:
        return None
    ones = 0
    while ones < 8 and b[4] & (0x80 >> ones):
        ones += 1
    if ones == 1 or ones == 8:
        return None
    o = 5
    for _ in range(max(ones - 1, 0)):
        if o >= len(b) or b[o] & 0xC0 != 0x80:
            return None
        o += 1
    if bs == 1:
        blk = 192
    elif bs <= 5:
        blk = 576 << (bs - 2)
    elif bs == 6:
        if o >= len(b):
            return None
        blk, o = b[o] + 1, o + 1
    elif bs == 7:
        if o + 1 >= len(b):
            return None
        blk, o = (b[o] << 8 | b[o + 1]) + 1, o + 2
    else:
        blk = 256 << (bs - 8)
    o += {12: 1, 13: 2, 14: 2}.get(sr, 0)
    if o >= len(b) or crc8(b[:o]) != b[o]:
        return None
    return o + 1, blk


def flac_query(p):
    info, first = flac_meta(p)
    return audio("flac", info["rate"], info["ch"], rate_over(len(p), info["total"], info["rate"]), info["bps"], p[:first])


def flac_chunks(p):
    _, first = flac_meta(p)
    out, st = [], first
    while st < len(p):
        hd = flac_header(p, st)
        need(hd, "a frame header that does not read")
        c = 0
        for x in p[st:st + hd[0]]:
            c = crc16(c, x)
        i = st + hd[0]
        while True:
            if i >= len(p):
                need(c == 0, "a frame whose CRC-16 never matches")
                break
            if c == 0 and i >= st + hd[0] + 2 and p[i] == 0xFF and flac_header(p, i):
                break
            c = crc16(c, p[i])
            i += 1
        out.append((p[st:i], True, hd[1]))
        st = i
    need(out, "no frame")
    return p[:first], out


AAC_RATES = (96000, 88200, 64000, 48000, 44100, 32000, 24000, 22050, 16000, 12000, 11025, 8000, 7350)


def adts(p):
    out, at, first = [], 0, None
    while at < len(p):
        b = p[at:at + 7]
        need(len(b) == 7 and b[0] == 0xFF and b[1] >> 4 == 15 and (b[1] >> 1) & 3 == 0, "an ADTS sync word or layer")
        cfg = ((b[1] >> 3) & 1, b[2] >> 6, (b[2] >> 2) & 15, (b[2] & 1) << 2 | b[3] >> 6)
        ln = (b[3] & 3) << 11 | b[4] << 3 | b[5] >> 5
        need(cfg[2] <= 12 and cfg[3] != 0 and not (cfg[0] == 1 and cfg[1] == 3), "an ADTS configuration")
        need(ln >= (7 if b[1] & 1 else 9) and at + ln <= len(p), "an ADTS frame length")
        first = first or cfg
        need(cfg == first, "another configuration")
        out.append((p[at:at + ln], True, 1024 * ((b[6] & 3) + 1)))
        at += ln
    need(out, "no frame")
    return first, out


def aac_query(p):
    (iid, prof, sf, chc), frames = adts(p)
    codec = "mp4a.40.%d" % (prof + 1) if iid == 0 else "mp4a.%02x" % (0x66 + prof)
    rate = AAC_RATES[sf]
    return audio(codec, rate, 8 if chc == 7 else chc, rate_over(len(p), sum(f[2] for f in frames), rate), None, None)


def video_configs(q):
    if q["media"] != "video":
        return q
    v = {"contentType": 'video/mp4; codecs="%s"' % q["codec"], "width": q["width"], "height": q["height"],
         "bitrate": q["bitrate"], "framerate": q["framerate"][0] / q["framerate"][1] if q["framerate"] else None}
    q["decodingConfiguration"] = {"type": "media-source", "video": v} if q["framerate"] and q["bitrate"] is not None else None
    for k, hw in (("decoderConfigPreferHardware", "prefer-hardware"), ("decoderConfigNoPreference", "no-preference")):
        q[k] = {"codec": q["codec"], "codedWidth": q["codedWidth"], "codedHeight": q["codedHeight"], "hardwareAcceleration": hw}
    return q


QUERY = {
    "wai.video.av1": lambda p, r: av1_query(p), "wai.video.av1.lossless": lambda p, r: av1_query(p),
    "wai.video.hevc": lambda p, r: annexb_query(p, r, False), "wai.video.avc": lambda p, r: annexb_query(p, r, True),
    "wai.video.vp9": vp9_query, "wai.video.vp8": vp8_query,
    "wai.audio.opus": lambda p, r: opus_query(p), "wai.audio.opus.packet": lambda p, r: packet_query(p),
    "wai.audio.flac": lambda p, r: flac_query(p), "wai.audio.aac": lambda p, r: aac_query(p),
}
CHUNKS = {
    "wai.video.av1": av1_chunks, "wai.video.av1.lossless": av1_chunks,
    "wai.video.hevc": lambda p: annexb_chunks(p, False), "wai.video.avc": lambda p: annexb_chunks(p, True),
    "wai.video.vp9": lambda p: ivf_chunks(p, b"VP90"), "wai.video.vp8": lambda p: ivf_chunks(p, b"VP80"),
    "wai.audio.opus": opus_chunks, "wai.audio.opus.packet": lambda p: (None, [(p, True, opus_samples(p))]),
    "wai.audio.flac": flac_chunks, "wai.audio.aac": lambda p: (None, adts(p)[1]),
}


def mapped_caps():
    """The capabilities platform-decode §2's tables map, read from the text."""
    out = []
    for head, stop in (("### 2.1 ", "**VP9 levels.**"), ("### 2.2 ", "### 2.3 ")):
        for line in section(PD, head, stop).splitlines():
            if line.startswith("| `wai."):
                out += [c for c in ticks(line.split("|")[1]) if c.startswith("wai.")]
    return out


def envelope_payload(b):
    need(b[:4] == b"WAI1", "not a WAI1 envelope")
    ml = struct.unpack_from("<I", b, 4)[0]
    cap = json.loads(b[8:8 + ml])["model_requirement"]["capability"]
    pl = struct.unpack_from("<I", b, 8 + ml)[0]
    return cap, b[12 + ml:12 + ml + pl]


def chunk_summary(desc, chunks):
    samples = [c[2] for c in chunks]
    return {"chunks": len(chunks), "keys": sum(1 for c in chunks if c[1]), "firstKey": chunks[0][1] if chunks else None,
            "bytes": sum(len(c[0]) for c in chunks), "samples": None if None in samples else sum(samples),
            "descriptionBytes": None if desc is None else len(desc)}


def verify_queries(qdoc, root):
    fails, n = [], 0
    caps = mapped_caps()
    if sorted(caps) != sorted(QUERY):
        fails.append("platform-decode §2 maps %s, this verifier reads %s" % (sorted(caps), sorted(QUERY)))
    for c in qdoc["cases"]:
        cid, cap = c["id"], c["capability"]
        try:
            if "sps_hex" in c:
                got = hevc_sps(bytes.fromhex(c["sps_hex"]))
                summary = None
            else:
                b = open(os.path.join(root, c.get("payload_file") or c["payload_raw"]), "rb").read()
                if "payload_file" in c:
                    ecap, b = envelope_payload(b)
                    need(ecap == cap, "the envelope's capability")
                for at, x in c.get("mutate", []):
                    b = b[:at] + bytes([b[at] ^ x]) + b[at + 1:]
                rate = tuple(c["rate"]) if c.get("rate") else None
                got = video_configs(QUERY[cap](b, rate))
                d, ch = CHUNKS[cap](b)
                summary = chunk_summary(d, ch)
            if c.get("refused"):
                fails.append("query %s: read where the case says it is refused" % cid)
                continue
            for k, want in c["expect"].items():
                if got.get(k, "absent") != want:
                    fails.append("query %s: %s is %s, the case says %s" % (cid, k, json.dumps(got.get(k, "absent")), json.dumps(want)))
            for k, want in (c.get("chunks") or {}).items():
                if summary is None or summary.get(k, "absent") != want:
                    fails.append("query %s: chunks %s is %s, the case says %s" % (cid, k, summary and summary.get(k), want))
        except Refused as e:
            if not c.get("refused"):
                fails.append("query %s: refused (%s)" % (cid, e))
        n += 1
    return fails, n


def query_mutations(qdoc):
    """Copies of the query vectors, one defect each, every one of which must fail."""
    out = []

    def case(d, cid):
        return next(c for c in d["cases"] if c["id"] == cid)

    for c in qdoc["cases"]:
        cid = c["id"]
        if c.get("refused"):
            out.append(("%s read" % cid, lambda d, cid=cid: case(d, cid).update(refused=False, expect={"codec": "?"})))
            continue
        out.append(("%s's codec string changed" % cid, lambda d, cid=cid: case(d, cid)["expect"].update(codec=case(d, cid)["expect"]["codec"] + "0")))
        for k in ("bitrate", "width", "sampleRate", "numberOfChannels"):
            if isinstance(c["expect"].get(k), int):
                out.append(("%s's %s moved" % (cid, k), lambda d, cid=cid, k=k: case(d, cid)["expect"].update({k: case(d, cid)["expect"][k] + 1})))
        if isinstance((c.get("chunks") or {}).get("chunks"), int):
            out.append(("%s's chunk count moved" % cid, lambda d, cid=cid: case(d, cid)["chunks"].update(chunks=case(d, cid)["chunks"]["chunks"] + 1)))
            out.append(("%s's key count moved" % cid, lambda d, cid=cid: case(d, cid)["chunks"].update(keys=case(d, cid)["chunks"]["keys"] - 1)))
        if c.get("payload_raw") and not c.get("mutate"):
            out.append(("%s's payload cut" % cid, lambda d, cid=cid: case(d, cid).update(mutate=[[0, 0xFF]])))
    return out


KNOWN = ["report_malformed", "not_dispatchable", "tier_exceeds_class", "constraints_unevaluable", "constraints_unmet",
         "no_ua_mapping", "codec_mismatch", "codec_unregistered", "ua_not_asked", "ua_unsupported", "ua_inexact",
         "ua_unprobed", "ua_probe_mismatch", "no_host", "host_inexact", "no_wasm", "no_decoder", "no_alternative",
         "constraint_malformed",
         "parameter_unregistered", "energy_class_invalid", "unmetered_as_zero", "energy_count_invalid",
         "energy_evidence_missing", "binding_malformed", "binding_alg_unknown", "binding_unverified_reference",
         "binding_ambiguous"]


def find(doc, family, name):
    for c in doc[family]:
        if c["name"] == name:
            return c
    raise KeyError(name)


def entry(doc, case, obj):
    for e in find(doc, "routes", case)["table"]:
        if e["name"] == obj:
            return e
    raise KeyError(obj)


def mutations(doc):
    """(name, change to a copy of the document, change to the files or None)."""
    def m(f):
        return f

    def flip_hex(s, i=0):
        return s[:i] + ("0" if s[i] != "0" else "1") + s[i + 1:]

    out = []
    out.append(("a route changed", m(lambda d: entry(d, "room_tracks", "wai.video.vp9").update(route="wasm")), None))
    out.append(("a supported answer withdrawn", m(lambda d: find(d, "routes", "room_tracks")["report"]["ua"]["vp09.00.10.08"].update(supported=False)), None))
    out.append(("a probe matched", m(lambda d: find(d, "routes", "need_decode_equivalence")["report"]["ua"]["vp09.00.10.08"].update(probe="match")), None))
    out.append(("the registry gate ignored", m(lambda d: entry(d, "unregistered_codecs", "av2").update(asked=True)), None))
    out.append(("a leg's reason changed", m(lambda d: entry(d, "fallbacks", "int_motion")["legs"].update(host="no_host")), None))
    out.append(("a figure's floor changed", m(lambda d: entry(d, "room_tracks", "wai.video.vp9")["energy"]["figure"].update(per_decode_micro=3051)), None))
    out.append(("powerEfficient stated off the ua route", m(lambda d: entry(d, "energy", "estimator_wasm")["energy"].update(power_efficient=True)), None))
    out.append(("powerEfficient inverted", m(lambda d: find(d, "routes", "room_tracks")["report"]["ua"]["vp09.00.10.08"].update(power_efficient=False)), None))
    out.append(("a zero read as a figure", m(lambda d: entry(d, "energy", "zero_with_class")["energy"].update(reason=None)), None))
    out.append(("a learned alternative chosen above a classical one", m(lambda d: find(d, "choices", "classical_before_learned")["choices"][0].update(order=["int_hyper", "int_motion"], chosen="int_hyper")), None))
    out.append(("the power-efficient answer withdrawn", m(lambda d: find(d, "choices", "hardware_first")["report"]["ua"]["av01.0.04M.08"].update(power_efficient=False)), None))
    out.append(("no answer read as power-efficient", m(lambda d: find(d, "choices", "power_efficient_not_stated")["report"]["ua"]["avc1.64001f"].update(power_efficient=True)), None))
    out.append(("an alternative routed none chosen", m(lambda d: find(d, "choices", "no_alternative")["choices"][0].update(chosen="hevc", reason=None)), None))
    out.append(("an empty choice read", m(lambda d: find(d, "choices", "empty_choice")["report"]["objects"][0].update(choice="clip")), None))
    out.append(("a partial figure read as qualifying", m(lambda d: find(d, "choices", "learned_with_a_partial_measurement")["report"]["energy"]["wai.video.int_hyper wasm"].update(coverage="Whole")), None))
    out.append(("a modelled figure read as qualifying", m(lambda d: find(d, "choices", "learned_with_a_modelled_figure")["choices"][0].update(order=["int_hyper", "int_motion"], ranks=["classical", "classical"], chosen="int_hyper")), None))
    out.append(("a host-routed decode ranked on the user agent's answer", m(lambda d: find(d, "choices", "power_efficient_answer_for_a_host_routed_decode")["choices"][0].update(order=["hevc", "av1"], ranks=["first", "smooth"], chosen="hevc")), None))
    out.append(("a power-efficient answer that is not smooth put first", m(lambda d: find(d, "choices", "smooth_before_power_efficient_but_not_smooth")["choices"][0].update(order=["hevc", "av1"], ranks=["first", "smooth"], chosen="hevc")), None))
    out.append(("a rank renamed", m(lambda d: find(d, "choices", "hardware_first")["choices"][0]["ranks"].__setitem__(1, "classical")), None))
    out.append(("a route of none ranked before a learned alternative", m(lambda d: find(d, "choices", "learned_when_nothing_else_routes")["choices"][0].update(order=["hevc", "int_hyper"], ranks=[None, "learned-without-budget"])), None))
    out.append(("a constraint bound moved", m(lambda d: find(d, "constraints", "bounds_inclusive")["sets"][0]["wai:frame_height"].update(minimum=1081)), None))
    out.append(("an unregistered parameter registered", m(lambda d: find(d, "constraints", "unregistered").update(outcome="unsatisfied", reason="constraints_unmet")), None))
    out.append(("a digest upper-cased", m(lambda d: find(d, "bindings", "canonical")["value"].update(digest="1F" * 32)), None))
    out.append(("an unknown tier kept", m(lambda d: find(d, "bindings", "unknown_tier").update(tier="bit-exact")), None))
    out.append(("a frame tier kept through an alteration", m(lambda d: [c.update(tier=c["route_tier"]) for c in d["frame_tiers"] if c["altered"]]), None))
    out.append(("a group signature changed", m(lambda d: d["chain"]["groups"][0]["receipt"].update(sig=flip_hex(d["chain"]["groups"][0]["receipt"]["sig"], 3))), None))
    out.append(("an object's bytes changed", m(lambda d: d["chain"]["groups"][0]["objects"].__setitem__(1, dict(d["chain"]["groups"][0]["objects"][1], envelope=flip_hex(d["chain"]["groups"][0]["objects"][1]["envelope"], 40)))), None))
    out.append(("a link hash changed", m(lambda d: d["chain"]["groups"][0].update(link_hash=flip_hex(d["chain"]["groups"][0]["link_hash"]))), None))
    out.append(("a binding names another receipt", m(lambda d: d["chain"]["groups"][1]["objects"][0].update(binding=d["chain"]["groups"][0]["objects"][0]["binding"])), None))
    out.append(("a changed object bound", m(lambda d: d["chain"]["groups"][0]["objects"][2].update(binding=d["chain"]["groups"][0]["objects"][1]["binding"], outcome="verified")), None))
    out.append(("the second group unlinked", m(lambda d: d["chain"]["groups"][1]["receipt"].update(parent_receipt_hash=None)), None))

    def forged(d):
        # The last group's signature changed, and everything derived from it made to agree:
        # its canonical bytes, its link hash, and the binding of its object. Only the
        # signature check can catch it.
        g = d["chain"]["groups"][-1]
        sig = flip_hex(g["receipt"]["sig"], 5)
        g["receipt"]["sig"] = sig
        can = bytes.fromhex(g["canonical"][:-128] + sig)
        g["canonical"] = can.hex()
        link = b3(b"moq-jwp:receipt-link\x01" + can).hex()
        g["link_hash"] = link
        for o in g["objects"]:
            if o["binding"]:
                b = json.loads(o["binding"])
                b["receipt"] = link
                o["binding"] = canonical(b)
    out.append(("a signature forged, everything derived from it agreeing", forged, None))
    out.append(("the envelope file changed", None, lambda name, b: b[:-1] + bytes([b[-1] ^ 1]) if name == "int_motion.wai" else b))
    out.append(("refused provenance shown verified", m(lambda d: find(d, "frames", "cmaf_provenance_refused")["result"].update(state="verified")), None))
    out.append(("a held chain shown verified", m(lambda d: find(d, "frames", "chain_held").update(chain="linked")), None))
    out.append(("an ambiguous timestamp bound", m(lambda d: find(d, "tables", "same_timestamp").update(ops=find(d, "tables", "same_timestamp")["ops"][:1] + find(d, "tables", "same_timestamp")["ops"][3:])), None))
    out.append(("a clone without its binding", m(lambda d: find(d, "tables", "clone_and_close")["result"]["frames"].update(f0c=None)), None))
    out.append(("a bound raised", m(lambda d: find(d, "tables", "bound").update(bound=3)), None))
    out.append(("a reason's only case removed", m(lambda d: d["tables"].remove(find(d, "tables", "same_timestamp"))), None))
    return out


def never_read(doc):
    """Answers the corpus gives for codec strings no registry row lists, changed every way."""
    out = []
    for flip in ({"supported": False}, {"probe": "mismatch"}, {"power_efficient": False, "smooth": False}):
        d = copy.deepcopy(doc)
        for c in d["routes"]:
            ua = c["report"].get("ua") if isinstance(c["report"], dict) else None
            for k, a in (ua or {}).items():
                if not gate(k):
                    a.update(flip)
        out.append((json.dumps(flip), d))
    return out


def main():
    if len(sys.argv) not in (2, 3):
        print(__doc__)
        return 2
    d = sys.argv[1]
    with open(os.path.join(d, "vectors.json"), encoding="utf-8") as f:
        doc = json.load(f)
    files = {}

    def loader(change=None):
        def load(name):
            if name not in files:
                with open(os.path.join(d, name), "rb") as f:
                    files[name] = f.read()
            b = files[name]
            return change(name, b) if change else b
        return load

    bad = 0
    if sorted(REASONS) != sorted(KNOWN) or len(REASONS) != len(set(REASONS)):
        print("FAIL §11 lists %s, this verifier knows %s" % (sorted(set(REASONS) ^ set(KNOWN)), len(KNOWN)))
        bad += 1
    fails = verify(doc, loader())
    for f in fails:
        print("FAIL " + f)
    n = sum(len(doc[k]) for k in ("routes", "choices", "constraints", "bindings", "frame_tiers", "frames", "tables"))
    n += sum(len(g["objects"]) for g in doc["chain"]["groups"])
    print("%s every case gets the outcome the corpus states (%d cases; every reason of §11 given)" % ("PASS" if not fails else "FAIL", n))
    bad += bool(fails)
    for flip, d2 in never_read(doc):
        f2 = verify(d2, loader())
        print("%s answers for unregistered codec strings changed (%s) are never read" % ("PASS" if not f2 else "FAIL", flip))
        bad += bool(f2)
    caught = 0
    muts = mutations(doc)
    for name, change, file_change in muts:
        d2 = copy.deepcopy(doc)
        # A mutation may change the registry export as read; each is undone after its run.
        saved = copy.deepcopy(CAPS)
        if change:
            change(d2)
        f2 = verify(d2, loader(file_change))
        CAPS.clear()
        CAPS.update(saved)
        if f2:
            caught += 1
        else:
            print("FAIL the mutation '%s' is not caught" % name)
    print("%s %d of %d mutated copies fail" % ("PASS" if caught == len(muts) else "FAIL", caught, len(muts)))
    bad += caught != len(muts)
    if len(sys.argv) == 3:
        bad += main_queries(sys.argv[2])
    return 1 if bad else 0


def main_queries(qdir):
    """platform-decode §2 over <platform-decode-conformance>/queries.json: every case's query
    and chunks recomputed, and every mutated copy of the vectors failing."""
    with open(os.path.join(qdir, "queries.json"), encoding="utf-8") as f:
        qdoc = json.load(f)
    bad = 0
    fails, n = verify_queries(qdoc, WAI)
    for f in fails:
        print("FAIL " + f)
    print("%s every query and its chunks are the ones the vectors state (%d cases)" % ("PASS" if not fails else "FAIL", n))
    bad += bool(fails)
    muts = query_mutations(qdoc)
    caught = 0
    for name, change in muts:
        d2 = copy.deepcopy(qdoc)
        change(d2)
        if verify_queries(d2, WAI)[0]:
            caught += 1
        else:
            print("FAIL the mutation '%s' of the query vectors is not caught" % name)
    print("%s %d of %d mutated copies of the query vectors fail" % ("PASS" if caught == len(muts) else "FAIL", caught, len(muts)))
    bad += caught != len(muts)
    return bad


if __name__ == "__main__":
    sys.exit(main())