"""Murphy (2023), Chapter 25: Diffusion models.

Companion code for Chapter 25 of K. P. Murphy, Probabilistic Machine Learning: Advanced Topics
(MIT Press, 2023; December 2025 draft), pp. 867-891. (The supplement's Chapter 25 is a title page
with no content.) Written from scratch with numpy, matplotlib and PyTorch (CPU only), to be read next
to the lecture notes (../ch25-diffusion-models.html).

Scale. Everything runs on one CPU thread. Where a figure needs the true score of a noised data
distribution, the data distribution is a Gaussian mixture, whose noised marginals and scores are
known in closed form: the samplers then run with a "perfectly trained" score network, so what the
pictures show is the sampler and not the network. Trained networks are small multilayer
perceptrons: a score network on the Swiss roll (Figure 25.5), noise-prediction networks on the 8 x 8
scikit-learn digits (stand-in for EMNIST, Figures 25.4, 25.8, 25.9) and a categorical denoiser for
the quantised Swiss roll (Figure 25.16), each trained in under a minute and cached in
cache/ch25/.

Methods
* Section 25.2: the variance-preserving forward chain and its marginal (25.3), the posterior
  (25.6)-(25.8), the noise parameterisation (25.21)-(25.22), the weight lambda_t of (25.23),
  Algorithm 25.1 (train_eps_model) and Algorithm 25.2 / ancestral sampling (reverse_sample with
  method "ddpm"), the noise schedules (linear, cosine) and the signal-to-noise ratio of Section 25.2.4.
* Section 25.3: basic (implicit) score matching on the Swiss roll and Langevin sampling (Figure 25.5),
  annealed Langevin over noise scales (Section 25.3.2).
* Section 25.4: the VP SDE in continuous time (beta(t) linear from 0.1 to 20), Euler-Maruyama for the
  forward SDE (25.44) and the reverse SDE (25.53), the probability-flow ODE with Euler (25.56) and
  Heun steps, flow matching with the linear interpolant (flow_matching_velocity).
* Section 25.5: the DDIM sampler (25.58)-(25.59) with eta, the progressive-distillation target of
  Algorithm 25.4 (distill_target).
* Section 25.6: classifier guidance (25.62) and classifier-free guidance (25.66), in the class-
  conditional digit model and with exact scores in the guidance demo.
* Section 25.7: D3PM transition matrices (uniform, absorbing, discretised Gaussian), the t-step
  marginal (25.69), the posterior (25.70), the closed forms (25.72)-(25.74), the x0-parameterised
  reverse step (25.76), the noise schedules of Section 25.7.4.
* The samplers use the same seeded generator (mulberry32 with Box-Muller) as the browser demos, so
  the demos reproduce these numbers.

Figures reproduced: 25.2, 25.5, 25.6, 25.7, 25.11 (exact one-dimensional computation in place of the
image slide), 25.16; stand-ins on the 8 x 8 digits for 25.4 (EMNIST), 25.8 (CIFAR-100) and 25.9.
Own figures (not in the book): x25.a (noise schedules), x25.b (sampler accuracy against the number of
steps).

Skipped figures, with reasons: 25.1, 25.3, 25.12, 25.13, 25.14 and 25.17 are diagrams or schematics
(the forward and reverse chains, the U-net, progressive distillation, latent diffusion, the cascaded
Imagen model, MaskGIT decoding); 25.10 shows faces from a large score model trained on CelebA-HQ at
256 x 256 (GPU scale); 25.15 is an illustration of multinomial diffusion on segmentation maps taken
from a paper (no computation to reproduce).

Data: the Swiss roll (scikit-learn make_swiss_roll), the 8 x 8 handwritten digits (scikit-learn
load_digits, stand-in for EMNIST), Gaussian mixtures and simulation.
"""
import json
import math
import os
import sys
import time

import numpy as np

HERE = os.path.dirname(os.path.abspath(__file__))
sys.path.insert(0, HERE)
import common  # noqa: E402
from common import BLUE, GREEN, GREY, ORANGE, PURPLE, RED, MAGENTA, plt, savefig, panel_label  # noqa: E402

CH = 25
CACHE_DIR = os.path.join(HERE, "cache", "ch25")
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
os.makedirs(CACHE_DIR, exist_ok=True)


# =========================================================================== random numbers
class Mulberry:
    """The seeded generator of the browser demos (mulberry32 uniforms, Box-Muller normals).

    Using it here lets a demo page reproduce a Python run number for number."""

    def __init__(self, seed):
        self.a = seed & 0xFFFFFFFF
        self.spare = None

    def u(self):
        a = (self.a + 0x6D2B79F5) & 0xFFFFFFFF
        self.a = a
        t = ((a ^ (a >> 15)) * (1 | a)) & 0xFFFFFFFF
        t = ((t + (((t ^ (t >> 7)) * (61 | t)) & 0xFFFFFFFF)) & 0xFFFFFFFF) ^ t
        return ((t ^ (t >> 14)) & 0xFFFFFFFF) / 4294967296.0

    def norm(self):
        if self.spare is not None:
            s, self.spare = self.spare, None
            return s
        x = 0.0
        while x == 0.0:
            x = self.u()
        r = math.sqrt(-2.0 * math.log(x))
        th = 2.0 * math.pi * self.u()
        self.spare = r * math.sin(th)
        return r * math.cos(th)

    def normals(self, *shape):
        n = int(np.prod(shape))
        return np.array([self.norm() for _ in range(n)]).reshape(shape)


class NumpyNormals:
    """Fast stand-in with the same interface (for the figures, where matching the browser demos number for number is not needed)."""

    def __init__(self, seed):
        self.g = np.random.default_rng(seed)

    def normals(self, *shape):
        return self.g.standard_normal(shape)


# =========================================================================== schedules
BMIN, BMAX = 0.1, 20.0   # linear beta(t) of the VP SDE, t in [0, 1]


def vp_beta(t):
    return BMIN + (BMAX - BMIN) * np.asarray(t, float)


def vp_int_beta(t):
    t = np.asarray(t, float)
    return BMIN * t + 0.5 * (BMAX - BMIN) * t ** 2


def vp_alpha_sigma(t):
    """Signal scale alpha(t) = sqrt(alphabar) and noise sd sigma(t) of the VP SDE (Section 25.4.1)."""
    a = np.exp(-0.5 * vp_int_beta(t))
    return a, np.sqrt(-np.expm1(-vp_int_beta(t)))


def ddpm_linear_betas(T=1000, b1=1e-4, bT=0.02):
    """The linear schedule of the original DDPM, beta_1 .. beta_T."""
    return np.linspace(b1, bT, T)


def cosine_alphabar(T, s=0.008):
    """Cosine schedule as defined by Nichol and Dhariwal (2021): alphabar_t = f(t)/f(0),
    f(t) = cos^2(((t/T + s)/(1 + s)) pi/2), t = 0..T (returns T + 1 values, alphabar_0 = 1)."""
    t = np.arange(T + 1)
    f = np.cos((t / T + s) / (1 + s) * np.pi / 2) ** 2
    return f / f[0]


def book_literal_cosine_alphabar(T, s=0.008):
    """The schedule as printed in Section 25.7.4: per-step alpha_t = cos(((t/T + s)/(1 + s)) pi/2)
    for t = 1..T and alphabar_t its running product (returns T + 1 values with alphabar_0 = 1)."""
    t = np.arange(1, T + 1)
    a = np.cos((t / T + s) / (1 + s) * np.pi / 2)
    return np.concatenate([[1.0], np.cumprod(a)])


def alphabar_from_betas(betas):
    return np.concatenate([[1.0], np.cumprod(1 - betas)])


# =========================================================================== DDPM Gaussian algebra
def ddpm_posterior(x0, xt, beta_t, abar_t, abar_prev):
    """Mean and variance of q(x_{t-1} | x_t, x_0), Equations (25.6)-(25.8)."""
    alpha_t = 1 - beta_t
    mean = (np.sqrt(abar_prev) * beta_t / (1 - abar_t)) * x0 + (np.sqrt(alpha_t) * (1 - abar_prev) / (1 - abar_t)) * xt
    var = (1 - abar_prev) / (1 - abar_t) * beta_t
    return mean, var


def mean_from_eps(xt, eps, beta_t, abar_t):
    """Equation (25.21)/(25.22): the posterior mean written with the noise."""
    return (xt - beta_t / np.sqrt(1 - abar_t) * eps) / np.sqrt(1 - beta_t)


def lambda_weight(beta_t, sigma2_t, abar_t):
    """The weight lambda_t of Equation (25.23)."""
    return beta_t ** 2 / (2 * sigma2_t * (1 - beta_t) * (1 - abar_t))


# =========================================================================== Gaussian mixtures
class GMM:
    """A Gaussian mixture in D dimensions with full covariances. Its VP-noised marginal
    q_t = sum_k w_k N(alpha m_k, alpha^2 S_k + sigma^2 I) is again a mixture, so the noisy score
    and the denoiser E[x0 | x_t] are exact."""

    def __init__(self, w, m, S):
        self.w = np.asarray(w, float)
        self.m = np.atleast_2d(np.asarray(m, float))
        self.S = np.asarray(S, float)
        self.K, self.D = self.m.shape

    def noisy(self, alpha, sigma):
        return GMM(self.w, alpha * self.m, alpha ** 2 * self.S + sigma ** 2 * np.eye(self.D)[None])

    def _comp(self, X):
        """log w_k N(x | m_k, S_k) (n, K) and precision-times-residual (n, K, D)."""
        X = np.atleast_2d(X)
        P = np.linalg.inv(self.S)
        _, logdet = np.linalg.slogdet(self.S)
        R = X[:, None, :] - self.m[None]
        PR = np.einsum("kij,nkj->nki", P, R)
        quad = np.einsum("nki,nki->nk", R, PR)
        logc = np.log(self.w)[None] - 0.5 * (self.D * np.log(2 * np.pi) + logdet[None] + quad)
        return logc, PR

    def logpdf(self, X):
        logc, _ = self._comp(X)
        return common.logsumexp(logc, axis=1)

    def resp(self, X):
        logc, _ = self._comp(X)
        return np.exp(logc - common.logsumexp(logc, axis=1)[:, None])

    def score(self, X):
        logc, PR = self._comp(X)
        r = np.exp(logc - common.logsumexp(logc, axis=1)[:, None])
        return -np.einsum("nk,nki->ni", r, PR)

    def sample(self, n, rng):
        g = rng if isinstance(rng, np.random.Generator) else np.random.default_rng(rng)
        k = g.choice(self.K, size=n, p=self.w)
        L = np.linalg.cholesky(self.S)
        z = g.standard_normal((n, self.D))
        return self.m[k] + np.einsum("nij,nj->ni", L[k], z), k


def gmm_score_t(gmm, X, t):
    a, s = vp_alpha_sigma(t)
    return gmm.noisy(a, s).score(X)


def gmm_denoise(gmm, X, t):
    """E[x0 | x_t] for a mixture (Tweedie's formula: (x + sigma^2 score)/alpha)."""
    a, s = vp_alpha_sigma(t)
    return (X + s ** 2 * gmm.noisy(a, s).score(X)) / a


# =========================================================================== samplers
TMIN = 1e-3


def time_grid(N, tmin=TMIN):
    return np.linspace(1.0, tmin, N + 1)


def reverse_sample(score_fn, xT, N, method, rng, eta=0.0, tmin=TMIN, keep=False):
    """Integrate the reverse process from t = 1 to t = tmin in N steps.

    score_fn(x, t) returns the score of q_t. method is one of
    'ddpm'  ancestral sampling, Algorithm 25.2, with sigma_t^2 = beta-tilde (posterior variance);
    'sde'   Euler-Maruyama on the reverse SDE, Equation (25.53);
    'ode'   Euler on the probability-flow ODE, Equation (25.56);
    'heun'  Heun's second-order method on the same ODE;
    'ddim'  the DDIM step (25.59) with sigma-tilde = eta * sqrt(beta-tilde) (eta = 0: deterministic).
    rng supplies normals(n, D). With keep=True the whole path is returned too.
    """
    x = np.array(xT, float)
    ts = time_grid(N, tmin)
    path = [x.copy()] if keep else None
    for i in range(N):
        t, s = ts[i], ts[i + 1]
        dt = t - s
        sc = score_fn(x, t)
        if method in ("ddpm", "ddim"):
            at, st = vp_alpha_sigma(t)
            as_, ss = vp_alpha_sigma(s)
            abar_t, abar_s = at ** 2, as_ ** 2
            x0 = (x + st ** 2 * sc) / at
            eps = -st * sc
            beta = 1 - abar_t / abar_s
            btil = (1 - abar_s) / (1 - abar_t) * beta
            if method == "ddpm":
                mean = (np.sqrt(abar_s) * beta / (1 - abar_t)) * x0 + (np.sqrt(1 - beta) * (1 - abar_s) / (1 - abar_t)) * x
                x = mean + np.sqrt(btil) * rng.normals(*x.shape)
            else:
                sig = eta * np.sqrt(btil)
                x = as_ * x0 + np.sqrt(max(1 - abar_s - sig ** 2, 0.0)) * eps
                if eta > 0:
                    x = x + sig * rng.normals(*x.shape)
        elif method == "sde":
            b = vp_beta(t)
            x = x + 0.5 * b * (x + 2 * sc) * dt + np.sqrt(b * dt) * rng.normals(*x.shape)
        elif method == "ode":
            b = vp_beta(t)
            x = x + 0.5 * b * (x + sc) * dt
        elif method == "heun":
            b = vp_beta(t)
            d1 = 0.5 * b * (x + sc)
            xe = x + d1 * dt
            b2 = vp_beta(s)
            d2 = 0.5 * b2 * (xe + score_fn(xe, s))
            x = x + 0.5 * (d1 + d2) * dt
        else:
            raise ValueError(method)
        if keep:
            path.append(x.copy())
    return (x, np.array(path)) if keep else x


def langevin(score_fn, x, n_steps, step, rng, t=TMIN):
    """Unadjusted Langevin x <- x + (step/2) score + sqrt(step) z at a single noise level t."""
    x = np.array(x, float)
    for _ in range(n_steps):
        x = x + 0.5 * step * score_fn(x, t) + np.sqrt(step) * rng.normals(*x.shape)
    return x


def annealed_langevin(score_fn, x, levels, n_per, step0, rng):
    """Annealed Langevin dynamics (Song and Ermon 2019) over the VP noise levels `levels`
    (decreasing t); the step at level t is step0 * sigma(t)^2 / sigma(tmin)^2 capped at 0.05."""
    x = np.array(x, float)
    _, smin = vp_alpha_sigma(levels[-1])
    for t in levels:
        _, st = vp_alpha_sigma(t)
        eps = min(step0 * (st / smin) ** 2, 0.05)
        for _ in range(n_per):
            x = x + 0.5 * eps * score_fn(x, t) + np.sqrt(eps) * rng.normals(*x.shape)
    return x


def forward_em_paths(x0, n_steps, rng):
    """Euler-Maruyama paths of the forward VP SDE (25.45), Equation (25.44); returns (n_steps+1, n)."""
    x = np.array(x0, float)
    dt = 1.0 / n_steps
    out = [x.copy()]
    for i in range(n_steps):
        t = i * dt
        b = vp_beta(t)
        x = x - 0.5 * b * x * dt + np.sqrt(b * dt) * rng.normals(*x.shape)
        out.append(x.copy())
    return np.array(out)


def distill_target(z_t, x_teacher_t, x_teacher_mid, a_t, s_t, a_mid, s_mid, a_end, s_end):
    """Algorithm 25.4, lines 9-11: two deterministic DDIM teacher steps t -> t' -> t'' and the
    student target x-tilde that makes ONE DDIM step t -> t'' land on the same z_t''.
    x_teacher_t, x_teacher_mid are the teacher's predictions at z_t and z_t'."""
    z_mid = a_mid * x_teacher_t + s_mid / s_t * (z_t - a_t * x_teacher_t)
    z_end = a_end * x_teacher_mid + s_end / s_mid * (z_mid - a_mid * x_teacher_mid)
    x_tilde = (z_end - (s_end / s_t) * z_t) / (a_end - (s_end / s_t) * a_t)
    return z_mid, z_end, x_tilde


def flow_matching_velocity(gmm, X, t):
    """Exact marginal velocity v(x, t) = E[x1 - x0 | x_t = x] for the linear interpolant
    x_t = (1 - t) x0 + t x1 with x0 ~ N(0, I) (source) and x1 ~ gmm (target), Section 25.4.7.
    Given x_t = x, component k: x1 | x, k is Gaussian; x0 = (x - t x1)/(1 - t)."""
    X = np.atleast_2d(X)
    noisy = GMM(gmm.w, t * gmm.m, t ** 2 * gmm.S + (1 - t) ** 2 * np.eye(gmm.D)[None])
    r = noisy.resp(X)
    v = np.zeros_like(X)
    for k in range(gmm.K):
        C = t ** 2 * gmm.S[k] + (1 - t) ** 2 * np.eye(gmm.D)
        G = t * gmm.S[k] @ np.linalg.inv(C)           # cov(x1, x_t) cov(x_t)^-1
        Ex1 = gmm.m[k] + (X - t * gmm.m[k]) @ G.T
        Ex0 = (X - t * Ex1) / (1 - t)
        v += r[:, [k]] * (Ex1 - Ex0)
    return v


# =========================================================================== toy data sets
def toy1d():
    """One-dimensional three-component mixture used for Figures 25.2, 25.6, 25.7, 25.11."""
    w = [0.3, 0.4, 0.3]
    m = [[-1.6], [0.1], [1.5]]
    S = np.array([[[0.18 ** 2]], [[0.28 ** 2]], [[0.16 ** 2]]])
    return GMM(w, m, S)


def swiss_roll(n, seed=0, noise=0.5):
    from sklearn.datasets import make_swiss_roll
    X, _ = make_swiss_roll(n, noise=noise, random_state=seed)
    return X[:, [0, 2]] / 5.0


def swiss_roll_gmm(K=20):
    """A K-component full-covariance mixture fitted to 20 000 Swiss-roll points: a data distribution
    with the Swiss-roll shape whose noised scores are exact (cached)."""
    path = os.path.join(CACHE_DIR, "swissroll_gmm%d.npz" % K)
    if os.path.exists(path):
        z = np.load(path)
        return GMM(z["w"], z["m"], z["S"])
    from sklearn.mixture import GaussianMixture
    X = swiss_roll(20000, seed=1)
    gm = GaussianMixture(K, covariance_type="full", random_state=0, n_init=2, max_iter=500).fit(X)
    order = np.argsort(np.arctan2(gm.means_[:, 1], gm.means_[:, 0]))
    w, m, S = gm.weights_[order], gm.means_[order], gm.covariances_[order]
    w = np.round(w, 6); w = w / w.sum()
    m = np.round(m, 6); S = np.round(S, 6)
    np.savez(path, w=w, m=m, S=S)
    return GMM(w, m, S)


def two_blobs():
    """Two well separated blobs with weights 0.8 and 0.2: the case of Equation (25.30)."""
    return GMM([0.8, 0.2], [[-1.5, 0.0], [1.5, 0.0]], np.array([np.eye(2) * 0.04, np.eye(2) * 0.04]))


def cfg_classes():
    """Three overlapping classes in 2-D, each a two-component mixture (guidance demo)."""
    I = np.eye(2)
    comps = {
        0: ([0.5, 0.5], [[-1.2, 0.9], [-0.3, 1.5]], [I * 0.12, I * 0.10]),
        1: ([0.6, 0.4], [[0.9, 0.9], [0.3, 0.2]], [I * 0.15, I * 0.12]),
        2: ([0.5, 0.5], [[-0.6, -0.9], [0.8, -1.0]], [np.array([[0.20, 0.05], [0.05, 0.10]]), I * 0.12]),
    }
    prior = np.array([1 / 3, 1 / 3, 1 / 3])
    cond = {c: GMM(w, m, np.array(S)) for c, (w, m, S) in comps.items()}
    W = np.concatenate([prior[c] * cond[c].w for c in range(3)])
    M = np.concatenate([cond[c].m for c in range(3)])
    SS = np.concatenate([cond[c].S for c in range(3)])
    return cond, GMM(W, M, SS), prior


def guided_score(cond, uncond, X, t, c, w):
    """Classifier-free guidance (25.66) with exact scores: (1 + w) s(x | c) - w s(x)."""
    a, s = vp_alpha_sigma(t)
    return (1 + w) * cond[c].noisy(a, s).score(X) - w * uncond.noisy(a, s).score(X)


def classifier_prob(cond, prior, X, t=0.0):
    """Exact p_t(c | x) for the class-conditional mixtures."""
    a, s = (1.0, 0.0) if t == 0 else vp_alpha_sigma(t)
    L = np.stack([np.log(prior[c]) + (cond[c].noisy(a, s).logpdf(X) if t else cond[c].logpdf(X)) for c in range(len(cond))], 1)
    return np.exp(L - common.logsumexp(L, axis=1)[:, None])


# =========================================================================== D3PM (Section 25.7)
def q_uniform(beta, K):
    """Uniform kernel (25.71): (1 - beta) I + beta 11^T / K."""
    return (1 - beta) * np.eye(K) + beta / K


def q_absorbing(beta, K):
    """Absorbing kernel (25.75) on K + 1 states, the last one being MASK."""
    Q = (1 - beta) * np.eye(K + 1)
    Q[:, K] += beta
    Q[K, K] = 1.0
    return Q


def q_discretized_gaussian(beta, K):
    """Discretised Gaussian kernel of Austin et al. (2021), Appendix A.2.2: off-diagonal entries
    proportional to exp(-4 (i - j)^2 / ((K - 1)^2 beta)), normalised over all offsets, diagonal
    chosen so rows sum to 1. Symmetric, hence doubly stochastic."""
    n = np.arange(-(K - 1), K)
    norm = np.exp(-4.0 * n ** 2 / ((K - 1) ** 2 * beta)).sum()
    i = np.arange(K)
    Q = np.exp(-4.0 * (i[:, None] - i[None]) ** 2 / ((K - 1) ** 2 * beta)) / norm
    np.fill_diagonal(Q, 0.0)
    np.fill_diagonal(Q, 1 - Q.sum(1))
    return Q


def d3pm_schedule(kind, T):
    """Per-step betas for the three kernels (Section 25.7.4)."""
    t = np.arange(1, T + 1)
    if kind == "uniform":
        abar = cosine_alphabar(T)
        return 1 - abar[1:] / abar[:-1]
    if kind == "absorbing":
        return 1.0 / (T - t + 1)
    if kind == "gaussian":
        return np.linspace(0.0002, 0.05, T)
    raise ValueError(kind)


def d3pm_matrices(kind, K, T):
    betas = d3pm_schedule(kind, T)
    make = {"uniform": q_uniform, "absorbing": q_absorbing, "gaussian": q_discretized_gaussian}[kind]
    Qs = [make(b, K) for b in betas]
    Qbar = [np.eye(Qs[0].shape[0])]
    for Q in Qs:
        Qbar.append(Qbar[-1] @ Q)
    return Qs, Qbar


def d3pm_posterior(xt, x0, Qs, Qbar, t):
    """Equation (25.70): q(x_{t-1} | x_t, x_0) for one-hot (or probability) row vectors.
    Qs[t-1] is Q_t, Qbar[t] is Q_1 ... Q_t."""
    num = (xt @ Qs[t - 1].T) * (x0 @ Qbar[t - 1])
    return num / num.sum(-1, keepdims=True)


# =========================================================================== small torch models
def _torch():
    return common.torch_setup(0)


def time_features(t, n=16):
    import torch
    f = torch.exp(torch.linspace(0, math.log(200.0), n // 2))
    a = t[:, None] * f[None]
    return torch.cat([torch.sin(a), torch.cos(a)], 1)


def make_mlp(din, dout, width, depth, seed, act="silu"):
    torch = _torch()
    torch.manual_seed(seed)
    nn = torch.nn
    layers, d = [], din
    for _ in range(depth):
        layers += [nn.Linear(d, width), nn.SiLU() if act == "silu" else nn.Softplus()]
        d = width
    layers.append(nn.Linear(d, dout))
    return nn.Sequential(*layers)


class EpsNet:
    """Noise predictor eps(x_t, t, c) for the 8 x 8 digits (64 inputs); class c in 0..9, 10 = none."""

    def __init__(self, width, depth, seed, ncls=11):
        torch = _torch()
        self.ncls = ncls
        self.net = make_mlp(64 + 16 + ncls, 64, width, depth, seed)
        self.torch = torch

    def __call__(self, x, t, c):
        torch = self.torch
        oh = torch.nn.functional.one_hot(c, self.ncls).float()
        return self.net(torch.cat([x, time_features(t), oh], 1))


def digits_data():
    from sklearn.datasets import load_digits
    d = load_digits()
    return (2 * d.data / 16.0 - 1).astype(np.float32), d.target


def train_eps_model(width=256, depth=3, seed=0, steps=12000, p_uncond=0.15, conditional=True, tag="A"):
    """Algorithm 25.1 in continuous time: t ~ U(tmin, 1), x_t = alpha x0 + sigma eps, loss ||eps - eps_hat||^2.
    With conditional=True the class label is dropped (set to 'none') with probability p_uncond, so one
    network gives both p(x | c) and p(x) (classifier-free guidance). Cached."""
    torch = _torch()
    path = os.path.join(CACHE_DIR, "digits_eps_%s.pt" % tag)
    model = EpsNet(width, depth, seed)
    if os.path.exists(path):
        model.net.load_state_dict(torch.load(path))
        return model
    X, y = digits_data()
    Xt, yt = torch.tensor(X), torch.tensor(y)
    opt = torch.optim.Adam(model.net.parameters(), lr=2e-3)
    sched = torch.optim.lr_scheduler.CosineAnnealingLR(opt, steps)
    g = torch.Generator().manual_seed(seed)
    t0 = time.time()
    for it in range(steps):
        idx = torch.randint(0, len(X), (256,), generator=g)
        x0, c = Xt[idx], yt[idx].clone()
        if conditional:
            drop = torch.rand(256, generator=g) < p_uncond
            c[drop] = 10
        else:
            c[:] = 10
        t = TMIN + (1 - TMIN) * torch.rand(256, generator=g)
        ib = BMIN * t + 0.5 * (BMAX - BMIN) * t ** 2
        a = torch.exp(-0.5 * ib)[:, None]
        s = torch.sqrt(-torch.expm1(-ib))[:, None]
        eps = torch.randn(x0.shape, generator=g)
        loss = ((model(a * x0 + s * eps, t, c) - eps) ** 2).sum(1).mean()
        opt.zero_grad()
        loss.backward()
        opt.step()
        sched.step()
    print("  trained digits model %s in %.0f s (final loss %.2f)" % (tag, time.time() - t0, loss.item()))
    torch.save(model.net.state_dict(), path)
    return model


def eps_score_fn(model, c, w=0.0, clip=True):
    """Score function score(x, t) = -eps_hat / sigma from a digits model, with optional
    classifier-free guidance weight w (25.66) and clipping of the implied x0 to [-1, 1]."""
    torch = model.torch

    def f(x, t):
        n = x.shape[0]
        with torch.no_grad():
            xt = torch.tensor(x, dtype=torch.float32)
            tt = torch.full((n,), float(t))
            cc = torch.full((n,), int(c), dtype=torch.long) if np.isscalar(c) else torch.tensor(c)
            e = model(xt, tt, cc)
            if w != 0.0:
                eu = model(xt, tt, torch.full((n,), 10, dtype=torch.long))
                e = (1 + w) * e - w * eu
            e = e.double().numpy()
        a, s = vp_alpha_sigma(t)
        if clip:
            x0 = np.clip((x - s * e) / a, -1, 1)
            e = (x - a * x0) / s
        return -e / s
    return f


def digits_classifier():
    from sklearn.linear_model import LogisticRegression
    X, y = digits_data()
    return LogisticRegression(max_iter=3000, C=1.0).fit(X, y)


# =========================================================================== plotting helpers
def _heat(ax, gmm1d, xs, ts, cmap="magma"):
    dens = np.array([np.exp(gmm1d.noisy(*vp_alpha_sigma(t)).logpdf(xs[:, None])) for t in ts]).T
    ax.imshow(np.sqrt(dens), origin="lower", aspect="auto", extent=[ts[0], ts[-1], xs[0], xs[-1]], cmap=cmap)


def _side_density(ax, gmm1d, xs, t, color):
    a, s = vp_alpha_sigma(t) if t > 0 else (1.0, 0.0)
    d = np.exp(gmm1d.noisy(a, s).logpdf(xs[:, None])) if t > 0 else np.exp(gmm1d.logpdf(xs[:, None]))
    ax.fill_betweenx(xs, 0, d, color=color, alpha=0.35)
    ax.plot(d, xs, color=color)
    ax.set_xticks([])
    ax.set_ylim(xs[0], xs[-1])


# =========================================================================== figures
def fig_25_2(out=None):
    """Marginals q(x_t) of the forward diffusion of a 1-D mixture."""
    g = toy1d()
    xs = np.linspace(-3.2, 3.2, 600)
    ts = [0.0, 0.05, 0.1, 0.2, 0.35, 1.0]
    fig, axes = plt.subplots(1, 6, figsize=(8.4, 2.8), sharey=True)
    for ax, t in zip(axes, ts):
        a, s = (1.0, 0.0) if t == 0 else vp_alpha_sigma(t)
        d = np.exp(g.logpdf(xs[:, None])) if t == 0 else np.exp(g.noisy(a, s).logpdf(xs[:, None]))
        ax.plot(d, xs, color=BLUE)
        ax.fill_betweenx(xs, 0, d, color=BLUE, alpha=0.15)
        ax.set_xticks([])
        ax.set_title("$q(x_0)$" if t == 0 else ("$q(x_1)=\\mathcal{N}(0,1)$" if t == 1 else "$q(x_t)$, $t=%.2f$" % t), fontsize=9)
        ax.set_xlabel(r"$\bar\alpha=%.3f$" % (a ** 2), fontsize=8.5)
    axes[0].set_ylabel("$x$")
    fig.suptitle("Forward diffusion of a three-component mixture (VP SDE): data $\\rightarrow$ noise", fontsize=10)
    fig.tight_layout()
    return savefig(fig, CH, "fig25-2", out)


def fig_25_6(out=None):
    """Forward SDE paths over the exact marginal density of a 1-D mixture."""
    g = toy1d()
    xs = np.linspace(-3.2, 3.2, 300)
    ts = np.linspace(0, 1, 300)
    rng = np.random.default_rng(3)
    x0, _ = g.sample(8, rng)
    paths = forward_em_paths(x0[:, 0], 1000, NumpyNormals(4))
    fig = plt.figure(figsize=(8.4, 2.9))
    gs = fig.add_gridspec(1, 3, width_ratios=[1, 6, 1], wspace=0.05)
    a0, a1, a2 = fig.add_subplot(gs[0]), fig.add_subplot(gs[1]), fig.add_subplot(gs[2])
    _side_density(a0, g, xs, 0.0, MAGENTA)
    a0.invert_xaxis()
    a0.set_ylabel("$x$")
    a0.set_title("$q(x_0)$", fontsize=9)
    _heat(a1, g, xs, ts)
    tt = np.linspace(0, 1, 1001)
    for p in paths.T:
        a1.plot(tt, p, color="#c8f560", lw=0.8)
    a1.set_yticks([])
    a1.set_ylim(xs[0], xs[-1])
    a1.set_xlabel("$t$ (forward diffusion, fixed)")
    _side_density(a2, g, xs, 1.0, ORANGE)
    a2.set_yticks([])
    a2.set_title("$q(x_1)$", fontsize=9)
    return savefig(fig, CH, "fig25-6", out)


def fig_25_7(out=None):
    """Reverse SDE paths and probability-flow ODE trajectories with the exact score."""
    g = toy1d()
    xs = np.linspace(-3.2, 3.2, 300)
    ts = np.linspace(0, 1, 300)
    sfn = lambda x, t: gmm_score_t(g, x, t)  # noqa: E731
    N = 1000
    xT = NumpyNormals(5).normals(10, 1)
    _, P_sde = reverse_sample(sfn, xT, N, "sde", NumpyNormals(6), keep=True)
    xT2 = np.linspace(-2.4, 2.4, 15)[:, None]
    _, P_ode = reverse_sample(sfn, xT2, N, "heun", None, keep=True)
    tg = time_grid(N)
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 2.9))
    for ax, P, lab, col in ((axes[0], P_sde, "(a) reverse SDE (25.53)", "#c8f560"), (axes[1], P_ode, "(b) probability-flow ODE (Heun)", "#c8f560")):
        _heat(ax, g, xs, ts)
        for p in P[:, :, 0].T:
            ax.plot(tg, p, color=col, lw=0.8)
        ax.set_xlim(1, 0)
        ax.set_ylim(xs[0], xs[-1])
        ax.set_xlabel("$t$ (generation runs from $t=1$ to $t=0$)")
        ax.set_title(lab, fontsize=10)
    axes[0].set_ylabel("$x$")
    fig.tight_layout()
    return savefig(fig, CH, "fig25-7", out)


def reverse_conditional_1d(g, xt, t, s, xs):
    """Exact density of q(x_s | x_t) for the 1-D mixture (s < t), and its mean and variance."""
    at, _ = vp_alpha_sigma(t)
    as_, ss = (1.0, 0.0) if s == 0 else vp_alpha_sigma(s)
    r = at / as_                       # x_t = r x_s + sqrt(1 - r^2) eps
    v_ts = 1 - r ** 2
    logw, means, vars_ = [], [], []
    for k in range(g.K):
        mk, vk = as_ * g.m[k, 0], as_ ** 2 * g.S[k, 0, 0] + ss ** 2   # x_s | k
        mt, vt = r * mk, r ** 2 * vk + v_ts                            # x_t | k
        logw.append(np.log(g.w[k]) - 0.5 * np.log(2 * np.pi * vt) - 0.5 * (xt - mt) ** 2 / vt)
        gain = vk * r / vt
        means.append(mk + gain * (xt - mt))
        vars_.append(vk - gain * r * vk)
    logw = np.array(logw)
    w = np.exp(logw - common.logsumexp(logw))
    means, vars_ = np.array(means), np.array(vars_)
    dens = sum(w[k] * np.exp(-0.5 * (xs - means[k]) ** 2 / vars_[k]) / np.sqrt(2 * np.pi * vars_[k]) for k in range(g.K))
    mu = (w * means).sum()
    var = (w * (vars_ + means ** 2)).sum() - mu ** 2
    return dens, mu, var


def fig_25_11(out=None):
    """One small reverse step has a near-Gaussian conditional; a large one is multimodal."""
    g = toy1d()
    xs = np.linspace(-2.6, 2.6, 800)
    t, xt = 0.3, 0.25
    cases = [(0.29, "small step: $t=0.30\\to0.29$"), (0.15, "medium step: $t=0.30\\to0.15$"), (0.0, "one big step: $t=0.30\\to0$")]
    fig, axes = plt.subplots(1, 3, figsize=(8.6, 2.6))
    for ax, (s, lab) in zip(axes, cases):
        d, mu, var = reverse_conditional_1d(g, xt, t, s, xs)
        ax.plot(xs, d, color=BLUE, label="exact $q(x_s\\mid x_t)$")
        ax.plot(xs, np.exp(-0.5 * (xs - mu) ** 2 / var) / np.sqrt(2 * np.pi * var), color=RED, ls="--", label="best Gaussian")
        ax.set_title(lab, fontsize=9.5)
        ax.set_xlabel("$x_s$")
        ax.set_yticks([])
    axes[0].legend(fontsize=8, loc="upper left")
    fig.tight_layout()
    return savefig(fig, CH, "fig25-11", out)


# ===== Figure 25.5: basic score matching
def ism_loss(net, x):
    """Basic (implicit) score matching loss E[0.5 ||s(x)||^2 + tr(ds/dx)] (Hyvarinen 2005), in 2-D."""
    import torch
    x = x.clone().requires_grad_(True)
    s = net(x)
    tr = 0.0
    for d in range(2):
        tr = tr + torch.autograd.grad(s[:, d].sum(), x, create_graph=True)[0][:, d]
    return (0.5 * (s ** 2).sum(1) + tr).mean()


SR_NOISE = 1.0   # thickness of the Swiss roll used for Figure 25.5


def train_swissroll_score(steps=5000, seed=0):
    """MLP with two hidden layers of 128 softplus units fitted by basic score matching on 10 000
    Swiss-roll points. The loss is unbounded below for a finite sample (a network can put ever larger
    negative divergence at the data points), so training keeps the weights with the best loss on
    4 000 held-out points, checked every 250 steps. Cached."""
    torch = _torch()
    net = make_mlp(2, 2, 128, 2, seed, act="softplus")
    path = os.path.join(CACHE_DIR, "swissroll_ism.pt")
    if os.path.exists(path):
        net.load_state_dict(torch.load(path))
        return net
    X = torch.tensor(swiss_roll(10000, seed=0, noise=SR_NOISE), dtype=torch.float32)
    V = torch.tensor(swiss_roll(4000, seed=9, noise=SR_NOISE), dtype=torch.float32)
    opt = torch.optim.Adam(net.parameters(), lr=1e-3)
    g = torch.Generator().manual_seed(seed)
    t0, best, best_state = time.time(), np.inf, None
    for it in range(steps + 1):
        loss = ism_loss(net, X[torch.randint(0, len(X), (512,), generator=g)])
        opt.zero_grad()
        loss.backward()
        opt.step()
        if it % 250 == 0:
            v = ism_loss(net, V).item()
            if v < best:
                best, best_state = v, {k: w.clone() for k, w in net.state_dict().items()}
    net.load_state_dict(best_state)
    print("  trained Swiss-roll score network in %.0f s (best held-out loss %.3f)" % (time.time() - t0, best))
    torch.save(net.state_dict(), path)
    return net


def fig_25_5(out=None):
    """Basic score matching on the Swiss roll and Langevin sampling."""
    torch = _torch()
    net = train_swissroll_score()
    X = swiss_roll(10000, seed=0, noise=SR_NOISE)
    lim = 3.0
    gx = np.linspace(-lim, lim, 25)
    GX, GY = np.meshgrid(gx, gx)
    G = np.stack([GX.ravel(), GY.ravel()], 1)
    with torch.no_grad():
        S = net(torch.tensor(G, dtype=torch.float32)).numpy()
    nrm = np.linalg.norm(S, axis=1, keepdims=True)
    Su = S / np.maximum(nrm, 1e-9) * np.minimum(nrm, 4) / 4   # length grows with |s| up to a cap
    fig, axes = plt.subplots(2, 2, figsize=(7.2, 7.0))
    ax = axes[0, 0]
    ax.scatter(X[:, 0], X[:, 1], s=1, alpha=0.15, color=BLUE)
    ax = axes[0, 1]
    ax.quiver(G[:, 0], G[:, 1], Su[:, 0], Su[:, 1], color=GREEN, angles="xy", scale=8, width=0.004)
    ax = axes[1, 0]
    H, xe, ye = np.histogram2d(X[:, 0], X[:, 1], bins=70, range=[[-lim, lim], [-lim, lim]])
    ax.imshow(H.T, origin="lower", extent=[-lim, lim, -lim, lim], cmap="Blues", alpha=0.9)
    ax.quiver(G[:, 0], G[:, 1], Su[:, 0], Su[:, 1], color=GREEN, angles="xy", scale=8, width=0.004)
    ax = axes[1, 1]
    ax.imshow(H.T, origin="lower", extent=[-lim, lim, -lim, lim], cmap="Blues", alpha=0.5)
    ax.quiver(G[:, 0], G[:, 1], Su[:, 0], Su[:, 1], color=GREEN, angles="xy", scale=8, width=0.003, alpha=0.5)
    rng = np.random.default_rng(7)
    eps = 0.01
    for k, x in enumerate(np.array([[-2.5, -2.5], [0.0, 0.6], [2.6, 0.5]])):
        path = [x.copy()]
        for _ in range(25):
            with torch.no_grad():
                s = net(torch.tensor(x[None], dtype=torch.float32)).numpy()[0]
            x = x + 0.5 * eps * s + np.sqrt(eps) * rng.standard_normal(2)
            path.append(x.copy())
        P = np.array(path)
        ax.plot(P[:, 0], P[:, 1], "-", color=ORANGE, lw=1.0)
        ax.plot(P[:, 0], P[:, 1], ".", color=RED, ms=3)
    for a, lab in zip(axes.ravel(), "abcd"):
        a.set_xlim(-lim, lim)
        a.set_ylim(-lim, lim)
        a.set_aspect("equal")
        a.set_xticks([])
        a.set_yticks([])
        panel_label(a, lab)
    fig.tight_layout()
    return savefig(fig, CH, "fig25-5", out)


# ===== digits: Figures 25.4, 25.8, 25.9
def digits_models():
    A = train_eps_model(width=256, depth=3, seed=0, steps=12000, conditional=True, tag="A")
    return A


def _grid_img(ax, X, nrow, ncol):
    img = np.ones((nrow * 9 - 1, ncol * 9 - 1))
    for i in range(min(len(X), nrow * ncol)):
        r, c = divmod(i, ncol)
        img[r * 9:r * 9 + 8, c * 9:c * 9 + 8] = (X[i].reshape(8, 8) + 1) / 2
    ax.imshow(img, cmap="gray_r", vmin=0, vmax=1, interpolation="nearest")
    ax.set_xticks([])
    ax.set_yticks([])


def sample_digits(model, labels, w, N=200, seed=0):
    sfn_cache = {}
    x = NumpyNormals(seed).normals(len(labels), 64)
    labels = np.asarray(labels)
    out = np.zeros_like(x)
    for c in np.unique(labels):
        idx = labels == c
        f = eps_score_fn(model, int(c), w)
        out[idx] = reverse_sample(f, x[idx], N, "ddpm", NumpyNormals(seed + 1 + int(c)))
    return np.clip(out, -1, 1)


def digits_figure_numbers():
    """Accuracy of a logistic-regression digit classifier on generated samples (cached)."""
    path = os.path.join(CACHE_DIR, "digits_numbers.json")
    if os.path.exists(path):
        return json.load(open(path))
    model = digits_models()
    clf = digits_classifier()
    lab = np.repeat(np.arange(10), 20)
    res = {}
    for name, w in (("cond", 0.0), ("cfg2", 2.0)):
        Xs = sample_digits(model, lab, w, seed=11)
        p = clf.predict_proba(Xs)
        res[name] = {"acc": float((p.argmax(1) == lab).mean()), "conf": float(p.max(1).mean()),
                     "sd": float(np.mean([Xs[lab == c].std(0).mean() for c in range(10)]))}
    Xu = sample_digits(model, np.full(200, 10), 0.0, seed=11)
    pu = clf.predict_proba(Xu)
    res["uncond"] = {"conf": float(pu.max(1).mean()), "classes": np.bincount(pu.argmax(1), minlength=10).tolist()}
    json.dump(res, open(path, "w"))
    return res


def fig_25_4(out=None):
    """Digits stand-in for Figure 25.4: unconditional, class-conditional and guided samples."""
    model = digits_models()
    fig, axes = plt.subplots(1, 3, figsize=(9.0, 3.3))
    lab = np.repeat(np.arange(10), 6)
    Xu = sample_digits(model, np.full(60, 10), 0.0, seed=1)
    Xc = sample_digits(model, lab, 0.0, seed=1)
    Xg = sample_digits(model, lab, 2.0, seed=1)
    order = lambda X: X.reshape(10, 6, 64).transpose(1, 0, 2).reshape(60, 64)  # noqa: E731
    _grid_img(axes[0], Xu, 6, 10)
    _grid_img(axes[1], order(Xc), 6, 10)
    _grid_img(axes[2], order(Xg), 6, 10)
    for ax, lab_ in zip(axes, ["(a) unconditional", "(b) conditioned on the class", "(c) classifier-free guidance, $w=2$"]):
        ax.set_title(lab_, fontsize=9.5)
    digits_figure_numbers()
    fig.tight_layout()
    return savefig(fig, CH, "fig25-4", out)


def encode_ode(score_fn, x0, N=200, tmin=TMIN):
    """Run the probability-flow ODE forwards (Heun) from t = tmin to t = 1: the latent code."""
    x = np.array(x0, float)
    ts = np.linspace(tmin, 1.0, N + 1)
    for i in range(N):
        t, s = ts[i], ts[i + 1]
        dt = s - t
        d1 = -0.5 * vp_beta(t) * (x + score_fn(x, t))
        xe = x + d1 * dt
        d2 = -0.5 * vp_beta(s) * (xe + score_fn(xe, s))
        x = x + 0.5 * (d1 + d2) * dt
    return x


def digits_model_B():
    return train_eps_model(width=384, depth=2, seed=7, steps=12000, conditional=False, tag="B")


def latent_agreement():
    """Encode digits with two separately trained models; correlation of the codes (cached)."""
    path = os.path.join(CACHE_DIR, "latents.npz")
    if os.path.exists(path):
        z = np.load(path)
        return z["zA"], z["zB"], z["zR"]
    A, B = digits_models(), digits_model_B()
    X, _ = digits_data()
    x0 = X[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]].astype(float)
    zA = encode_ode(eps_score_fn(A, 10, 0.0, clip=False), x0)
    zB = encode_ode(eps_score_fn(B, 10, 0.0, clip=False), x0)
    zR = NumpyNormals(99).normals(*zA.shape)
    np.savez(path, zA=zA, zB=zB, zR=zR)
    return zA, zB, zR


def fig_25_8(out=None):
    """Digits stand-in for Figure 25.8: the probability-flow ODE codes of two different networks."""
    zA, zB, _ = latent_agreement()
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 2.7), gridspec_kw={"width_ratios": [3, 1.2]})
    ax = axes[0]
    ax.plot(np.arange(64), zA[0], "-o", ms=3, color=BLUE, label="model A (3 x 256, conditional)")
    ax.plot(np.arange(64), zB[0], "-s", ms=3, color=ORANGE, label="model B (2 x 384, unconditional)", alpha=0.85)
    ax.set_xlabel("latent dimension")
    ax.set_ylabel("$x_1$")
    ax.legend(fontsize=8, loc="lower left", ncol=2)
    ax.set_title("code of the first digit", fontsize=10)
    ax = axes[1]
    ax.scatter(zA.ravel(), zB.ravel(), s=4, color=PURPLE, alpha=0.6)
    lim = np.abs(np.concatenate([zA.ravel(), zB.ravel()])).max() * 1.05
    ax.plot([-lim, lim], [-lim, lim], color=GREY, lw=0.8)
    r = np.corrcoef(zA.ravel(), zB.ravel())[0, 1]
    ax.set_title("10 digits: corr = %.3f" % r, fontsize=10)
    ax.set_xlabel("model A code")
    ax.set_ylabel("model B code")
    ax.set_aspect("equal")
    fig.tight_layout()
    return savefig(fig, CH, "fig25-8", out)


def few_step_samples(model, labels, n_steps=4, churn=0.0, seed=3, w=1.0):
    """DDIM with n_steps; with churn > 0 each step first adds noise to move from t up to
    t_hat = min(1, t (1 + churn)) (the stochastic step of Karras et al. 2022, in VP form).
    Returns the states x_t after each step (n_steps, n, 64) and the times reached."""
    rng = NumpyNormals(seed)
    labels = np.asarray(labels)
    x = rng.normals(len(labels), 64)
    ts = np.linspace(1.0, TMIN, n_steps + 1)
    preds = []
    fns = {int(c): eps_score_fn(model, int(c), w) for c in np.unique(labels)}

    def score(x, t):
        out = np.zeros_like(x)
        for c, f in fns.items():
            idx = labels == c
            out[idx] = f(x[idx], t)
        return out
    for i in range(n_steps):
        t, s = ts[i], ts[i + 1]
        if churn > 0 and i > 0:
            th = min(1.0, t * (1 + churn))
            at, _ = vp_alpha_sigma(t)
            ah, _ = vp_alpha_sigma(th)
            r2 = (ah / at) ** 2                      # x_th = (ah/at) x_t + sqrt(1 - r2) z
            x = np.sqrt(r2) * x + np.sqrt(1 - r2) * rng.normals(*x.shape)
            t = th
        at, st = vp_alpha_sigma(t)
        as_, ss = vp_alpha_sigma(s)
        sc = score(x, t)
        x0 = np.clip((x + st ** 2 * sc) / at, -1, 1)
        eps = (x - at * x0) / st
        x = as_ * x0 + ss * eps
        preds.append(x.copy())
    return np.array(preds), ts[1:]


def fig_25_9(out=None):
    """Digits stand-in for Figure 25.9: four-step generation, deterministic and stochastic."""
    model = digits_models()
    lab = np.arange(10)
    Pd, ts = few_step_samples(model, lab, 4, churn=0.0, seed=3)
    Ps, _ = few_step_samples(model, lab, 4, churn=0.3, seed=3)
    fig, axes = plt.subplots(2, 1, figsize=(6.4, 5.6))
    for ax, P, ttl in ((axes[0], Pd, "deterministic (DDIM, 4 steps)"), (axes[1], Ps, "the same, with fresh noise added before steps 2 to 4")):
        _grid_img(ax, np.clip(P.reshape(-1, 64), -1, 1), 4, 10)
        ax.set_title(ttl, fontsize=9.5)
        for r, t in enumerate(ts):
            ax.text(-1.5, r * 9 + 4, "$t=%.2f$" % t if t > 0.01 else "$t=0.001$", ha="right", va="center", fontsize=8.5)
    fig.tight_layout()
    return savefig(fig, CH, "fig25-9", out)


# ===== Figure 25.16: D3PM on a quantised Swiss roll
D3PM_K, D3PM_T = 32, 50


def quantise(X, K=D3PM_K, lo=-2.6, hi=2.6):
    return np.clip(np.round((X - lo) / (hi - lo) * (K - 1)), 0, K - 1).astype(int)


def train_d3pm(steps=4000, seed=0):
    """x0-parameterised reverse model for the discretised-Gaussian D3PM (Section 25.7.3): an MLP maps
    (x_t scaled to [-1, 1], time features) to K logits per coordinate, trained by cross-entropy
    on x0 (the auxiliary loss of Austin et al. 2021). Cached."""
    torch = _torch()
    K, T = D3PM_K, D3PM_T
    net = make_mlp(2 + 16, 2 * K, 256, 3, seed)
    path = os.path.join(CACHE_DIR, "d3pm.pt")
    if os.path.exists(path):
        net.load_state_dict(torch.load(path))
        return net
    _, Qbar = d3pm_matrices("gaussian", K, T)
    Qb = torch.tensor(np.array(Qbar), dtype=torch.float32)
    X0 = torch.tensor(quantise(swiss_roll(10000, seed=0)))
    opt = torch.optim.Adam(net.parameters(), lr=1e-3)
    g = torch.Generator().manual_seed(seed)
    t0 = time.time()
    for it in range(steps):
        x0 = X0[torch.randint(0, len(X0), (512,), generator=g)]
        t = torch.randint(1, T + 1, (512,), generator=g)
        probs = Qb[t[:, None], x0]                         # (512, 2, K): rows of Qbar_t
        xt = torch.multinomial(probs.reshape(-1, K), 1, generator=g).reshape(512, 2)
        inp = torch.cat([2 * xt.float() / (K - 1) - 1, time_features(t.float() / T)], 1)
        logits = net(inp).reshape(512, 2, K)
        loss = torch.nn.functional.cross_entropy(logits.reshape(-1, K), x0.reshape(-1))
        opt.zero_grad()
        loss.backward()
        opt.step()
    print("  trained D3PM denoiser in %.0f s (final cross-entropy %.3f)" % (time.time() - t0, loss.item()))
    torch.save(net.state_dict(), path)
    return net


def d3pm_reverse(net, n, seed=0, keep=(0, 12, 25, 37, 50)):
    """Ancestral sampling with (25.76): p(x_{t-1} | x_t) = sum_x0 q(x_{t-1} | x_t, x0) p(x0 | x_t)."""
    torch = _torch()
    K, T = D3PM_K, D3PM_T
    Qs, Qbar = d3pm_matrices("gaussian", K, T)
    rng = np.random.default_rng(seed)
    x = rng.integers(0, K, size=(n, 2))              # the stationary distribution is uniform
    snaps = {T: x.copy()}
    for t in range(T, 0, -1):
        inp = torch.tensor(np.concatenate([2 * x / (K - 1) - 1, np.zeros((n, 16))], 1), dtype=torch.float32)
        inp[:, 2:] = time_features(torch.full((n,), t / T))
        with torch.no_grad():
            p0 = torch.softmax(net(inp).reshape(n, 2, K), -1).double().numpy()
        # q(x_{t-1} = j | x_t, x0 = i) for all i: rows of (Q_t^T[x_t] * Qbar_{t-1}) normalised
        A = Qs[t - 1][:, x].transpose(1, 2, 0)            # (n, 2, K): [Q_t]_{j, x_t} over j
        post = A[:, :, None, :] * Qbar[t - 1][None, None]  # (n, 2, i, j)
        tot = post.sum(-1, keepdims=True)
        post = np.divide(post, tot, out=np.zeros_like(post), where=tot > 0)   # unreachable x0: weight 0
        p = np.einsum("ndi,ndij->ndj", p0, post)
        p /= p.sum(-1, keepdims=True)
        cum = p.cumsum(-1)
        u = rng.random((n, 2, 1))
        x = (u > cum).sum(-1).clip(0, K - 1)
        if t - 1 in keep:
            snaps[t - 1] = x.copy()
    return snaps


def fig_25_16(out=None):
    """D3PM forward (three kernels) and learned reverse process on a quantised Swiss roll."""
    K, T = D3PM_K, D3PM_T
    X0 = quantise(swiss_roll(2000, seed=3))
    rng = np.random.default_rng(0)
    fig, axes = plt.subplots(2, 4, figsize=(9.6, 5.0))
    axes[0, 0].scatter(X0[:, 0], X0[:, 1], s=4, color=PURPLE, alpha=0.5)
    axes[0, 0].set_title("data at $t=0$", fontsize=9.5)
    for j, kind in enumerate(["uniform", "gaussian", "absorbing"]):
        Qs, Qbar = d3pm_matrices(kind, K, T)
        P = Qbar[T // 2]
        Kk = P.shape[0]
        Xt = np.zeros_like(X0)
        for d in range(2):
            cum = P[X0[:, d]].cumsum(1)
            Xt[:, d] = (rng.random((len(X0), 1)) > cum).sum(1)
        keep = (Xt < K).all(1)
        ax = axes[0, j + 1]
        ax.scatter(Xt[keep, 0], Xt[keep, 1], s=4, color=PURPLE, alpha=0.5)
        name = {"uniform": "uniform", "gaussian": "discretised Gaussian", "absorbing": "absorbing"}[kind]
        extra = "" if kind != "absorbing" else "\n(%.0f%% of points have a MASK coordinate)" % (100 * (1 - keep.mean()))
        ax.set_title("%s, $t=T/2$%s" % (name, extra), fontsize=9)
        ins = ax.inset_axes([0.0, 0.0, 0.28, 0.28])
        ins.imshow(Qs[T // 2 - 1] ** 0.35, cmap="magma")
        ins.set_xticks([])
        ins.set_yticks([])
    net = train_d3pm()
    snaps = d3pm_reverse(net, 2000, seed=1)
    for ax, t in zip(axes[1], [T, T // 2, T // 4, 0]):
        tt = min(snaps, key=lambda s: abs(s - t))
        S = snaps[tt]
        ax.scatter(S[:, 0], S[:, 1], s=4, color=MAGENTA if tt == 0 else PURPLE, alpha=0.5)
        ax.set_title(("generated at $t=0$" if tt == 0 else "$t=%d$" % tt + (" (stationary)" if tt == T else "")), fontsize=9.5)
    for ax in axes.ravel():
        ax.set_xlim(-1, K)
        ax.set_ylim(-1, K)
        ax.set_aspect("equal")
        ax.set_xticks([])
        ax.set_yticks([])
    axes[0, 0].set_ylabel("forward $q(x_t\\mid x_{t-1})$", fontsize=9)
    axes[1, 0].set_ylabel("learned reverse $p_\\theta(x_{t-1}\\mid x_t)$", fontsize=9)
    fig.tight_layout()
    return savefig(fig, CH, "fig25-16", out)


# ===== own figures
def fig_x25_a(out=None):
    """Noise schedules: linear DDPM, the cosine schedule, the book's literal cosine formula, VP SDE."""
    T = 1000
    ab_lin = alphabar_from_betas(ddpm_linear_betas(T))
    ab_cos = cosine_alphabar(T)
    ab_book = book_literal_cosine_alphabar(T)
    tt = np.arange(T + 1) / T
    a, s = vp_alpha_sigma(tt)
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.0))
    for ab, lab, col, ls in ((ab_lin, "linear $\\beta$ (DDPM)", BLUE, "-"), (ab_cos, "cosine (Nichol-Dhariwal)", GREEN, "-"),
                             (ab_book, "Section 25.7.4 as printed", RED, "--"), (a ** 2, "VP SDE, $\\beta(t)$ 0.1 to 20", PURPLE, ":")):
        axes[0].plot(tt, ab, color=col, ls=ls, label=lab)
        with np.errstate(divide="ignore"):
            axes[1].plot(tt[1:-1], np.log(ab[1:-1] / (1 - ab[1:-1])), color=col, ls=ls)
    axes[0].set_xlabel("$t/T$")
    axes[0].set_ylabel(r"$\bar\alpha_t$")
    axes[0].legend(fontsize=8)
    axes[1].set_xlabel("$t/T$")
    axes[1].set_ylabel(r"log SNR $=\log\bar\alpha_t/(1-\bar\alpha_t)$")
    axes[1].set_ylim(-25, 12)
    fig.tight_layout()
    return savefig(fig, CH, "figx25-a", out)


def sampler_metrics(gmm, X, ref_logq):
    """Mean log q0 of the samples and the fraction inside the true 95% highest-density region."""
    lq = gmm.logpdf(X)
    return float(lq.mean()), float((lq >= ref_logq).mean())


def hdr_threshold(gmm, n=200000, seed=0, level=0.05):
    X, _ = gmm.sample(n, seed)
    lq = gmm.logpdf(X)
    return float(np.quantile(lq, level)), float(lq.mean())


def fig_x25_b(out=None):
    """Accuracy of five samplers against the number of steps, exact scores, Swiss-roll mixture."""
    g = swiss_roll_gmm()
    thr, Elq = hdr_threshold(g)
    sfn = lambda x, t: gmm_score_t(g, x, t)  # noqa: E731
    Ns = [2, 4, 8, 16, 32, 64, 128, 256]
    meths = [("ddpm", "ancestral (Alg. 25.2)", BLUE, "o"), ("sde", "reverse SDE, Euler-Maruyama", ORANGE, "s"),
             ("ode", "probability-flow ODE, Euler", RED, "^"), ("heun", "probability-flow ODE, Heun", GREEN, "v"),
             ("ddim", "DDIM ($\\eta=0$)", PURPLE, "D")]
    res = {}
    for m, *_ in meths:
        cov = []
        for N in Ns:
            xT = NumpyNormals(10).normals(2000, 2)
            X = reverse_sample(sfn, xT, N, m, NumpyNormals(11))
            cov.append(sampler_metrics(g, X, thr)[1])
        res[m] = cov
    fig, ax = plt.subplots(figsize=(5.4, 3.3))
    for m, lab, col, mk in meths:
        ax.plot(Ns, res[m], "-", marker=mk, ms=4, color=col, label=lab)
    ax.axhline(0.95, color=GREY, ls="--", lw=0.8)
    ax.text(2.1, 0.955, "exact sampler: 0.95", fontsize=8, color=GREY, va="bottom")
    ax.set_xscale("log", base=2)
    ax.set_xlabel("number of steps $N$")
    ax.set_ylabel("fraction in the 95% HDR")
    ax.set_ylim(0, 1.0)
    ax.legend(fontsize=7.5, loc="lower right")
    fig.tight_layout()
    json.dump({"Ns": Ns, "res": res}, open(os.path.join(CACHE_DIR, "sampler_steps.json"), "w"))
    return savefig(fig, CH, "figx25-b", out)


# =========================================================================== the demos' computations
DEMO_NS = [2, 4, 8, 16, 32, 64, 128, 256, 512, 1000]


def run_sampler_demo(data="swiss", method="ddpm", N=256, n=2000):
    """What reverse-diffusion-demo.html computes: x_T from generator seed 10, step noise from seed 11
    (mulberry32), exact mixture scores; returns the share in the 95% HDR, the mean log q0 and the share
    with x > 0 (the small blob)."""
    g = swiss_roll_gmm() if data == "swiss" else two_blobs()
    thr, _ = hdr_threshold(g)
    rx, rz = Mulberry(10), Mulberry(11)
    X = rx.normals(n, 2)
    sfn = lambda x, t: gmm_score_t(g, x, t)  # noqa: E731
    if method == "langevin":
        X = langevin(sfn, X, N, 0.002, rz, TMIN)
    elif method == "annealed":
        X = annealed_langevin(sfn, X, np.linspace(1.0, TMIN, 10), max(1, N // 10), 0.002, rz)
    else:
        X = reverse_sample(sfn, X, N, method, rz)
    lq = g.logpdf(X)
    return {"hdr": float((lq >= thr).mean()), "mean": float(lq.mean()), "right": float((X[:, 0] > 0).mean()), "X": X}


def run_guidance_demo(c=0, w=0.0, method="ddpm", n=1000):
    """What classifier-free-guidance-demo.html computes (seeds 20 and 21): guided samples of class c
    and their mean exact p(c | x), share with p(c | x) > 0.9 and spread."""
    cond, unc, prior = cfg_classes()
    rx, rz = Mulberry(20), Mulberry(21)
    X = rx.normals(n, 2)
    sfn = lambda x, t: guided_score(cond, unc, x, t, c, w)  # noqa: E731
    X = reverse_sample(sfn, X, 100 if method == "ddpm" else 50, method, rz)
    p = classifier_prob(cond, prior, X)[:, c]
    sd = math.sqrt(np.trace(np.cov(X.T)))
    return {"pc": float(p.mean()), "hi": float((p > 0.9).mean()), "sd": sd, "X": X}


def guidance_target(c=0, w=0.0, G=200, lo=-3.0, hi=3.0):
    """The tilted target p(x | c)^(1+w) p(x)^(-w) on a G x G grid of cell centres: its mean p(c | x),
    mass with p(c | x) > 0.9 and spread."""
    cond, unc, prior = cfg_classes()
    h = (hi - lo) / G
    u = lo + (np.arange(G) + 0.5) * h
    XX, YY = np.meshgrid(u, u)
    P = np.stack([XX.ravel(), YY.ravel()], 1)
    L = (1 + w) * cond[c].logpdf(P) - w * unc.logpdf(P)
    q = np.exp(L - L.max())
    q /= q.sum()
    pc = classifier_prob(cond, prior, P)[:, c]
    m = q @ P
    sd = math.sqrt(max(q @ (P ** 2).sum(1) - m @ m, 0.0))
    return {"pc": float(q @ pc), "hi": float(q[pc > 0.9].sum()), "sd": sd}


def run_discrete_demo(kind="uniform", T=50, t=25, i=7, j=9):
    """What discrete-diffusion-demo.html computes for the 20-level data distribution."""
    d = json.load(open(os.path.join(DATA_OUT, "ch25-discrete.json")))
    K, p0 = d["K"], np.array(d["p0"])
    Qs, Qbar = d3pm_matrices(kind, K, T)
    S = Qbar[0].shape[0]
    p0 = np.concatenate([p0, np.zeros(S - K)])
    pi = np.zeros(S)
    if kind == "absorbing":
        pi[K] = 1.0
    else:
        pi[:K] = 1.0 / K
    q = p0 @ Qbar[t]
    tv = 0.5 * np.abs(q - pi).sum()
    H = -(q[q > 0] * np.log(q[q > 0])).sum()
    prior = 0.0
    for a in range(K):
        if p0[a] > 0:
            row = Qbar[T][a]
            nz = row > 0
            prior += p0[a] * (row[nz] * np.log(row[nz] / pi[nz])).sum()
    abar = float(np.prod(1 - d3pm_schedule(kind, T)[:t]))
    post = None
    if t >= 1:
        xt, x0 = np.eye(S)[j], np.eye(S)[i]
        num = (xt @ Qs[t - 1].T) * (x0 @ Qbar[t - 1])
        if num.sum() > 0:
            post = float(num[i] / num.sum())
    return {"tv": float(tv), "H": float(H), "prior": float(prior), "abar": abar,
            "mask": float(q[K]) if kind == "absorbing" else None, "post": post}


# =========================================================================== demo data
def export_demo_data():
    os.makedirs(DATA_OUT, exist_ok=True)
    g = swiss_roll_gmm()
    thr, Elq = hdr_threshold(g)
    b = two_blobs()
    thr_b, Elq_b = hdr_threshold(b)
    pts = swiss_roll(400, seed=5)
    d1 = {"bmin": BMIN, "bmax": BMAX, "tmin": TMIN,
          "swiss": {"w": g.w.tolist(), "m": g.m.tolist(), "S": g.S.tolist(), "hdr": thr, "Elogq": Elq,
                    "points": np.round(pts, 3).tolist()},
          "blobs": {"w": b.w.tolist(), "m": b.m.tolist(), "S": b.S.tolist(), "hdr": thr_b, "Elogq": Elq_b}}
    json.dump(d1, open(os.path.join(DATA_OUT, "ch25-samplers.json"), "w"))
    cond, unc, prior = cfg_classes()
    d2 = {"bmin": BMIN, "bmax": BMAX, "tmin": TMIN, "prior": prior.tolist(),
          "classes": [{"w": cond[c].w.tolist(), "m": cond[c].m.tolist(), "S": cond[c].S.tolist()} for c in range(3)]}
    json.dump(d2, open(os.path.join(DATA_OUT, "ch25-guidance.json"), "w"))
    K = 20
    q = quantise(swiss_roll(10000, seed=0), K=K)[:, 0]
    p0 = np.bincount(q, minlength=K) / len(q)
    d3 = {"K": K, "p0": np.round(p0, 6).tolist()}
    json.dump(d3, open(os.path.join(DATA_OUT, "ch25-discrete.json"), "w"))
    print("wrote", "data/ch25-samplers.json, ch25-guidance.json, ch25-discrete.json")


def export_figure(out=None):
    """(not a book figure) export the JSON files used by the demos"""
    export_demo_data()


FIGURES = {
    "25.2": fig_25_2,
    "25.4": fig_25_4,
    "25.5": fig_25_5,
    "25.6": fig_25_6,
    "25.7": fig_25_7,
    "25.8": fig_25_8,
    "25.9": fig_25_9,
    "25.11": fig_25_11,
    "25.16": fig_25_16,
    "x25.a": fig_x25_a,
    "x25.b": fig_x25_b,
    "data": export_figure,
}

if __name__ == "__main__":
    common.run(FIGURES, CH)
