"""Bishop and Bishop (2024), Chapter 20: Diffusion Models.

Reproduces the figures of Chapter 20 of C. M. Bishop and H. Bishop, Deep Learning: Foundations and
Concepts (Springer, 2024), pp. 581-607, written from scratch with numpy, scipy, PyTorch (CPU, one
thread) and matplotlib, and supplies the trained network and the reference numbers of the three
browser demonstrations. Every algorithm is a short function meant to be read next to the lecture
notes (ch20-diffusion-models.html):

* Section 20.1, the forward encoder: the noise schedule {beta_t} and alpha_t (20.7) (schedule), the
  Markov chain (20.3) run step by step (forward_chain) and the diffusion kernel (20.6)/(20.8) in one
  shot (forward_closed), the reverse conditional q(z_{t-1} | z_t, x) of (20.15)-(20.17)
  (posterior_mean_var) and, for a one-dimensional mixture, the exact reverse distribution
  q(z_{t-1} | z_t) of (20.11) on a grid (reverse_1d).
* Section 20.2, the reverse decoder: a three-arm spiral data density that is a Gaussian mixture, so
  that every noised marginal q(z_t | c) and its score are exact (Spiral, mix_score); the exact
  minimiser of the noise-prediction loss E[eps | z_t] (eps_star); a small multilayer perceptron
  g(z, t, c) trained with Algorithm 20.1 and a null class for classifier-free guidance (Denoiser,
  train_denoiser, cached in cache/ch20_denoiser.pt and exported to ../data/ch20-denoiser.json); its
  numpy forward pass (np_denoiser); the per-step weights of the ELBO (20.37) (elbo_weights); and
  the samplers: Algorithm 20.2 (sample_alg202) and the DDIM family with stochasticity eta
  (sample_ddim), both on any sub-sequence of the T steps.
* Section 20.3, score matching: explicit and denoising score-matching losses (20.43), (20.49)-(20.51)
  for a linear score model (esm_dsm_losses); Langevin sampling (14.61) and annealed Langevin
  dynamics over a sequence of noise levels (langevin, annealed_langevin); the variance-preserving
  SDE (20.70), its reverse-time SDE (20.56) and the probability-flow ODE (20.57) with the exact
  mixture score (sde_reverse, ode_flow).
* Section 20.4, guidance: classifier guidance (20.59) and classifier-free guidance (20.60), both in
  noise-prediction form (guided_eps), with the exact noisy classifier p(c | z_t) of the mixture.
* A 14 x 14 MNIST denoiser (a small convolutional U-net with time and class inputs, trained in a few
  minutes on one CPU thread, cached in cache/ch20_mnist.pt) used only for the small-scale
  reproductions of Figures 20.7 (guidance), 20.8 (super-resolution) and 20.9 (inpainting).
* JSRandom: the seeded generator DK.rng of the browser demos (mulberry32 uniforms and Box-Muller
  normals). The demo samplers draw their noise from it in a fixed order, so
  diffusion-sampling-demo.html and diffusion-guidance-demo.html reproduce sample_ddim and
  sample_alg202 number for number.

Figures reproduced: 20.1 (an MNIST digit noised by our schedule instead of the book's photograph),
20.3 and 20.4 (computed from an explicit three-component mixture), 20.5 and 20.6 (computed from an
explicit two-dimensional mixture), and, as small-scale reproductions of phenomena that the book
shows with large published models, 20.7 (classifier-free guidance, on the two-dimensional spiral and
on 14 x 14 MNIST digits), 20.8 (super-resolution of 7 x 7 digits to 14 x 14) and 20.9 (inpainting
of 14 x 14 digits). Skipped: Figure 20.2 (a hand-drawn graphical model of the forward and reverse
chains; it has no data).

Supplementary figures (our own, numbered 20.S1-20.S8 in the order they appear in the notes):
20.S1 the forward process on two-dimensional data: step-by-step chain against the closed form, and
the schedule; 20.S2 the reverse conditional q(z_{t-1} | z_t, x), and the small-beta expansion of
q(z_{t-1} | z_t) (Exercise 20.7); 20.S3 the ELBO weights and the trained network's loss per step
against the exact optimum; 20.S4 samples from the trained denoiser for several samplers and step
counts; 20.S5 denoising and explicit score matching differ by a constant; 20.S6 annealed Langevin
dynamics fixes the mixing proportions that plain Langevin gets wrong (Exercise 20.18); 20.S7 the
reverse SDE and the probability-flow ODE share their marginals; 20.S8 guidance strength against
class agreement and diversity.

Run `python3 ch20_diffusion_models.py --list`, `python3 ch20_diffusion_models.py` (all figures; about
eight minutes on one CPU thread when the two networks have to be trained, about two minutes from the
cache) or `python3 ch20_diffusion_models.py --fig 20.5 20.S4`. Files go to ../img/ch20/.
"""
import json
import math
import os

for _v in ("OPENBLAS_NUM_THREADS", "MKL_NUM_THREADS", "OMP_NUM_THREADS"):
    os.environ.setdefault(_v, "1")

import numpy as np  # noqa: E402
import matplotlib.pyplot as plt  # noqa: E402

import common  # noqa: E402
from common import savefig, run  # noqa: E402

HERE = os.path.dirname(os.path.abspath(__file__))
WEB_DATA = os.path.normpath(os.path.join(HERE, "..", "data"))
CACHE_DIR = os.path.join(HERE, "cache")
CH = 20
M32 = 0xFFFFFFFF


# =========================================================================== the demos' generator
def _imul(a, b):
    return (a * b) & M32


class JSRandom:
    """The seeded random numbers of the browser demos (DK.rng in courses/demo-kit.js).

    Uniforms come from the mulberry32 generator and normals from the Box-Muller transform, the
    second normal of each pair being cached, exactly as in JavaScript.
    """

    def __init__(self, seed):
        self.a = int(seed) & M32
        self.spare = None

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

    def _pos(self):
        x = 0.0
        while x == 0.0:
            x = self.u()
        return x

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

    def normals(self, n, d=2):
        """n x d standard normals, row by row (the order used by the demos)."""
        return np.array([[self.norm() for _ in range(d)] for _ in range(n)])


# =========================================================================== 20.1 forward encoder
T_STEPS = 200          # number of steps of the two-dimensional model and of the demos
BETA_1, BETA_T = 1e-3, 0.05


def schedule(T=T_STEPS, b1=BETA_1, bT=BETA_T, kind="linear"):
    """beta_1..beta_T and alpha_t = prod_{tau <= t}(1 - beta_tau) (20.7), as arrays indexed 0..T-1.

    kind = 'linear' (beta rises linearly from b1 to bT, the schedule of Ho et al. 2020) or 'cosine'
    (alpha_t = f(t)/f(0) with f(t) = cos^2((t/T + s)/(1 + s) pi/2), s = 0.008, Nichol and Dhariwal 2021).
    """
    if kind == "linear":
        beta = np.linspace(b1, bT, T)
    elif kind == "cosine":
        s = 0.008
        f = np.cos((np.arange(T + 1) / T + s) / (1 + s) * np.pi / 2) ** 2
        ab = f / f[0]
        beta = np.clip(1 - ab[1:] / ab[:-1], 1e-5, 0.999)
    elif kind == "constant":
        beta = np.full(T, b1)
    else:
        raise ValueError(kind)
    return beta, np.cumprod(1 - beta)


def forward_chain(x, beta, rng, keep=None):
    """Run the Markov chain (20.3) z_t = sqrt(1 - beta_t) z_{t-1} + sqrt(beta_t) eps_t from z_0 = x.

    Returns the list of z_t for t in keep (1-based; default: every step)."""
    z = np.array(x, dtype=float)
    out = {}
    keep = set(range(1, len(beta) + 1)) if keep is None else set(keep)
    for t, b in enumerate(beta, start=1):
        z = math.sqrt(1 - b) * z + math.sqrt(b) * rng.standard_normal(z.shape)
        if t in keep:
            out[t] = z.copy()
    return out


def forward_closed(x, alpha_t, eps):
    """The diffusion kernel (20.8): z_t = sqrt(alpha_t) x + sqrt(1 - alpha_t) eps."""
    return math.sqrt(alpha_t) * np.asarray(x) + math.sqrt(1 - alpha_t) * np.asarray(eps)


def posterior_mean_var(x, z, t, beta, alpha):
    """Mean m_t(x, z_t) (20.16) and variance sigma_t^2 (20.17) of q(z_{t-1} | z_t, x); t is 1-based, t >= 2."""
    b, a, ap = beta[t - 1], alpha[t - 1], alpha[t - 2]
    m = ((1 - ap) * math.sqrt(1 - b) * np.asarray(z) + math.sqrt(ap) * b * np.asarray(x)) / (1 - a)
    return m, b * (1 - ap) / (1 - a)


def mix1d_pdf(x, w, mu, sd):
    x = np.asarray(x, dtype=float)[..., None]
    return (np.asarray(w) * np.exp(-0.5 * ((x - mu) / sd) ** 2) / (np.sqrt(2 * np.pi) * np.asarray(sd))).sum(-1)


# the one-dimensional marginal q(z_{t-1}) of Figures 20.3 and 20.4
MIX1D = dict(w=np.array([0.3, 0.45, 0.25]), mu=np.array([-2.0, 0.3, 2.4]), sd=np.array([0.45, 0.5, 0.4]))


def reverse_1d(zt, beta, grid, mix=MIX1D):
    """The exact reverse density q(z_{t-1} | z_t) of (20.11) on a grid, for the 1-D mixture q(z_{t-1})."""
    prior = mix1d_pdf(grid, mix["w"], mix["mu"], mix["sd"])
    lik = np.exp(-0.5 * (zt - math.sqrt(1 - beta) * grid) ** 2 / beta)
    post = prior * lik
    return post / np.trapz(post, grid), prior


def reverse_1d_moments(zt, beta, mix=MIX1D):
    """Exact mean and variance of q(z_{t-1} | z_t) for the mixture q(z_{t-1}) (Gaussian conjugacy per component)."""
    w, mu, sd = mix["w"], mix["mu"], mix["sd"]
    c = math.sqrt(1 - beta)
    # z_t | component k ~ N(c mu_k, c^2 sd_k^2 + beta)
    v = c * c * sd ** 2 + beta
    lw = np.log(w) - 0.5 * np.log(v) - 0.5 * (zt - c * mu) ** 2 / v
    r = np.exp(lw - lw.max())
    r /= r.sum()
    prec = 1 / sd ** 2 + c * c / beta
    pm = (mu / sd ** 2 + c * zt / beta) / prec
    mean = (r * pm).sum()
    var = (r * (1 / prec + pm ** 2)).sum() - mean ** 2
    return mean, var


def mix1d_score_hess(z, mix=MIX1D):
    """d/dz ln q and d^2/dz^2 ln q of the 1-D mixture at z."""
    w, mu, sd = mix["w"], mix["mu"], mix["sd"]
    lw = np.log(w) - np.log(sd) - 0.5 * ((z - mu) / sd) ** 2
    r = np.exp(lw - lw.max())
    r /= r.sum()
    g = -(z - mu) / sd ** 2
    s = (r * g).sum()
    h = (r * (g * g - 1 / sd ** 2)).sum() - s * s
    return s, h


# =========================================================================== 2-D data: the three-arm spiral
class Spiral:
    """A three-class density on the plane, each class an arm of a spiral.

    Class c (c = 0, 1, 2) is an equal mixture of M isotropic Gaussians with standard deviation SD whose
    centres lie on the curve r (cos theta, sin theta), theta = 2 pi c / 3 + KAPPA r, r from R0 to R1.
    The classes have equal weight. Because every density here is a Gaussian mixture, the noised
    marginals q(z_t | c) and q(z_t) are Gaussian mixtures too, with exact scores.
    """
    M, SD, KAPPA, R0, R1, K = 24, 0.11, 1.35, 0.3, 2.0, 3

    def __init__(self):
        r = np.linspace(self.R0, self.R1, self.M)
        mus, cls = [], []
        for c in range(self.K):
            th = 2 * np.pi * c / self.K + self.KAPPA * r
            mus.append(np.stack([r * np.cos(th), r * np.sin(th)], 1))
            cls += [c] * self.M
        self.mu = np.concatenate(mus)
        self.cls = np.array(cls)
        self.w = np.full(len(self.mu), 1.0 / len(self.mu))

    def sample(self, n, rng, c=None):
        """n points (and their classes) from p(x) or, if c is given, from p(x | c)."""
        if c is None:
            k = rng.integers(0, len(self.mu), n)
        else:
            k = c * self.M + rng.integers(0, self.M, n)
        return self.mu[k] + self.SD * rng.standard_normal((n, 2)), self.cls[k]

    def comps(self, c=None):
        """(weights, means) of p(x) or p(x | c); c may be None (all classes)."""
        if c is None or c < 0 or c >= self.K:
            return self.w, self.mu
        sel = self.cls == c
        return self.w[sel] / self.w[sel].sum(), self.mu[sel]


SPIRAL = Spiral()


def mix_logpdf_score(z, w, mu, var):
    """ln q(z) and its score for the isotropic 2-D mixture sum_k w_k N(z | mu_k, var I); z is (n, 2)."""
    z = np.atleast_2d(z)
    d2 = ((z[:, None, :] - mu[None]) ** 2).sum(-1)
    lw = np.log(w)[None] - 0.5 * d2 / var - np.log(2 * np.pi * var)
    m = lw.max(1, keepdims=True)
    e = np.exp(lw - m)
    s = e.sum(1, keepdims=True)
    lp = (m + np.log(s))[:, 0]
    r = e / s
    score = -(z - r @ mu) / var
    return lp, score, r


def noised_mixture(alpha_t, c=None, data=SPIRAL):
    """(weights, means, variance) of q(z_t | c) = sum_k w_k N(sqrt(alpha_t) mu_k, (alpha_t SD^2 + 1 - alpha_t) I)."""
    w, mu = data.comps(c)
    return w, math.sqrt(alpha_t) * mu, alpha_t * data.SD ** 2 + 1 - alpha_t


def eps_star(z, alpha_t, c=None, data=SPIRAL):
    """The exact minimiser of the noise-prediction loss: E[eps | z_t] = -sqrt(1 - alpha_t) grad ln q(z_t | c)."""
    w, mu, var = noised_mixture(alpha_t, c, data)
    return -math.sqrt(1 - alpha_t) * mix_logpdf_score(z, w, mu, var)[1]


def class_posterior(z, alpha_t, data=SPIRAL):
    """The exact noisy classifier p(c | z_t) for the spiral (n x K)."""
    w, mu, var = noised_mixture(alpha_t, None, data)
    _, _, r = mix_logpdf_score(z, w, mu, var)
    return np.stack([r[:, data.cls == c].sum(1) for c in range(data.K)], 1)


def elbo_weights(beta, alpha):
    """The weights beta_t / (2 (1 - alpha_t)(1 - beta_t)) of (20.37) (t = 1 gives 1/(2(1 - beta_1)), (20.39))."""
    return beta / (2 * (1 - alpha) * (1 - beta))


# =========================================================================== the denoising network
N_FREQ = 8
FREQS = np.exp(np.linspace(0.0, math.log(60.0), N_FREQ))   # time-embedding frequencies
HIDDEN, LAYERS = 64, 3
NULL = 3                                                    # the null class used for p(x) (Section 20.4.2)


def time_features(t, T=T_STEPS):
    """Sinusoidal features of the step index: [sin(f_k t/T), cos(f_k t/T)], k = 1..8 (t may be an array)."""
    tau = np.asarray(t, dtype=float)[..., None] / T
    return np.concatenate([np.sin(FREQS * tau), np.cos(FREQS * tau)], -1)


def net_inputs(z, t, c, T=T_STEPS):
    """Input rows [z (2), time features (16), one-hot class (4, the last one the null class)]."""
    z = np.atleast_2d(z)
    n = len(z)
    tf = np.broadcast_to(time_features(t, T), (n, 2 * N_FREQ)) if np.ndim(t) == 0 else time_features(t, T)
    oh = np.zeros((n, 4))
    oh[np.arange(n), np.broadcast_to(np.asarray(c), (n,))] = 1.0
    return np.concatenate([z, tf, oh], 1)


def silu(a):
    return a / (1.0 + np.exp(-a))


def np_denoiser(params, z, t, c, T=T_STEPS):
    """Numpy forward pass of g(z, w, t, c): an MLP with SiLU units; params is the list [(W, b), ...]."""
    h = net_inputs(z, t, c, T)
    for i, (W, b) in enumerate(params):
        h = h @ W.T + b
        if i < len(params) - 1:
            h = silu(h)
    return h


def _torch_mlp(torch, n_in=2 + 2 * N_FREQ + 4, hidden=HIDDEN, layers=LAYERS):
    nn = torch.nn
    mods, d = [], n_in
    for _ in range(layers):
        mods += [nn.Linear(d, hidden), nn.SiLU()]
        d = hidden
    mods.append(nn.Linear(d, 2))
    return nn.Sequential(*mods).double()


def train_denoiser(iters=24000, batch=512, lr=2e-3, p_null=0.2, seed=0, verbose=True):
    """Algorithm 20.1 on the spiral, with the class replaced by the null class with probability p_null.

    Returns (params as numpy arrays, loss history every 200 iterations). Adam, cosine learning-rate decay,
    and an exponential moving average of the weights (decay 0.999) that is the returned network.
    """
    torch = common.torch_setup(seed, threads=1)
    beta, alpha = schedule()
    net = _torch_mlp(torch)
    ema = _torch_mlp(torch)
    ema.load_state_dict(net.state_dict())
    opt = torch.optim.Adam(net.parameters(), lr=lr)
    sched = torch.optim.lr_scheduler.CosineAnnealingLR(opt, iters, eta_min=lr * 0.02)
    rng = np.random.default_rng(seed)
    sqa, sq1a = np.sqrt(alpha), np.sqrt(1 - alpha)
    hist, run_l = [], 0.0
    for it in range(1, iters + 1):
        x, c = SPIRAL.sample(batch, rng)
        c = np.where(rng.random(batch) < p_null, NULL, c)
        t = rng.integers(1, T_STEPS + 1, batch)
        eps = rng.standard_normal((batch, 2))
        z = sqa[t - 1, None] * x + sq1a[t - 1, None] * eps
        inp = torch.from_numpy(net_inputs(z, t, c))
        loss = ((net(inp) - torch.from_numpy(eps)) ** 2).sum(1).mean()
        opt.zero_grad()
        loss.backward()
        opt.step()
        sched.step()
        with torch.no_grad():
            for pe, pn in zip(ema.parameters(), net.parameters()):
                pe.mul_(0.999).add_(pn, alpha=0.001)
        run_l += loss.item()
        if it % 200 == 0:
            hist.append(run_l / 200)
            if verbose and it % 4000 == 0:
                print("  iteration %d, loss %.4f" % (it, hist[-1]))
            run_l = 0.0
    lin = [m for m in ema if isinstance(m, torch.nn.Linear)]
    params = [(m.weight.detach().numpy().copy(), m.bias.detach().numpy().copy()) for m in lin]
    return params, np.array(hist)


def _round_params(params, sig=7):
    r = lambda a: np.array([float("%.*g" % (sig, v)) for v in np.ravel(a)]).reshape(np.shape(a))  # noqa: E731
    return [(r(W), r(b)) for W, b in params]


DENOISER_CACHE = os.path.join(CACHE_DIR, "ch20_denoiser.npz")


def denoiser(retrain=False):
    """The trained 2-D denoiser (weights rounded to 7 significant digits, exactly as exported to the demos)."""
    if os.path.exists(DENOISER_CACHE) and not retrain:
        d = np.load(DENOISER_CACHE)
        n = len([k for k in d.files if k.startswith("W")])
        return [(d["W%d" % i], d["b%d" % i]) for i in range(n)], d["hist"]
    print("training the two-dimensional denoiser (about two minutes on one thread) ...")
    params, hist = train_denoiser()
    params = _round_params(params)
    os.makedirs(CACHE_DIR, exist_ok=True)
    kw = {}
    for i, (W, b) in enumerate(params):
        kw["W%d" % i], kw["b%d" % i] = W, b
    np.savez(DENOISER_CACHE, hist=hist, **kw)
    return params, hist


# =========================================================================== samplers
def timesteps(S, T=T_STEPS):
    """S steps tau_S > ... > tau_1 = 1, evenly spread over 1..T (S = T gives every step)."""
    return np.unique(np.round(np.linspace(1, T, S)).astype(int))[::-1]


def make_eps_fn(kind="net", c=NULL, lam=1.0, params=None):
    """A function eps(z, t) -> predicted noise.

    kind: 'net' (the trained network, class c; with lam != 1 and c != NULL, classifier-free guidance (20.60)),
    'exact' (the exact E[eps | z_t] of the mixture; with c and lam, the exactly guided score),
    'classifier' (classifier guidance (20.59) with the exact unconditional score and the exact p(c | z_t)).
    """
    beta, alpha = schedule()
    if kind == "net":
        def f(z, t):
            gc = np_denoiser(params, z, t, c)
            if c == NULL or lam == 1.0:
                return gc
            gu = np_denoiser(params, z, t, NULL)
            return lam * gc + (1 - lam) * gu
        return f
    if kind == "exact":
        def f(z, t):
            a = alpha[t - 1]
            cc = None if c == NULL else c
            gc = eps_star(z, a, cc)
            if cc is None or lam == 1.0:
                return gc
            return lam * gc + (1 - lam) * eps_star(z, a, None)
        return f
    if kind == "classifier":
        def f(z, t):
            a = alpha[t - 1]
            gu = eps_star(z, a, None)
            return gu - lam * math.sqrt(1 - a) * classifier_grad(z, a, c)
        return f
    raise ValueError(kind)


def classifier_grad(z, alpha_t, c, data=SPIRAL):
    """grad_z ln p(c | z_t) for the exact noisy classifier of the spiral."""
    w, mu, var = noised_mixture(alpha_t, None, data)
    _, s_all, _ = mix_logpdf_score(z, w, mu, var)
    wc, muc, _ = noised_mixture(alpha_t, c, data)
    _, s_c, _ = mix_logpdf_score(z, wc, muc, var)
    return s_c - s_all     # grad ln p(c|z) = grad ln p(z|c) - grad ln p(z)


def sample_ddim(eps_fn, zT, S, eta, noise, T=T_STEPS, keep_path=False):
    """The DDIM family on S steps (Song, Meng and Ermon 2020): eta = 0 deterministic, eta = 1 stochastic.

    noise is an array of shape (S - 1, n, 2) of standard normals (one per step that adds noise).
    z_prev = sqrt(a_prev) x0_hat + sqrt(1 - a_prev - s^2) g + s eps,  x0_hat = (z - sqrt(1 - a) g)/sqrt(a),
    s = eta sqrt((1 - a_prev)/(1 - a)) sqrt(1 - a/a_prev). The last step returns x0_hat (no noise).
    """
    beta, alpha = schedule(T)
    ts = timesteps(S, T)
    z = np.array(zT, dtype=float)
    path = [z.copy()]
    for i, t in enumerate(ts):
        a = alpha[t - 1]
        g = eps_fn(z, t)
        x0 = (z - math.sqrt(1 - a) * g) / math.sqrt(a)
        if i == len(ts) - 1:
            z = x0
        else:
            ap = alpha[ts[i + 1] - 1]
            s = eta * math.sqrt((1 - ap) / (1 - a)) * math.sqrt(1 - a / ap)
            z = math.sqrt(ap) * x0 + math.sqrt(max(1 - ap - s * s, 0.0)) * g + s * noise[i]
        if keep_path:
            path.append(z.copy())
    return (z, np.array(path)) if keep_path else z


def sample_alg202(eps_fn, zT, S, noise, T=T_STEPS, keep_path=False):
    """Algorithm 20.2 on S steps: z_prev = (z - b/sqrt(1 - a) g)/sqrt(1 - b) + sqrt(b) eps, b = 1 - a/a_prev.

    With S = T this is exactly Algorithm 20.2 (b = beta_t); the last step is the noise-free x of the book.
    """
    beta, alpha = schedule(T)
    ts = timesteps(S, T)
    z = np.array(zT, dtype=float)
    path = [z.copy()]
    for i, t in enumerate(ts):
        a = alpha[t - 1]
        ap = alpha[ts[i + 1] - 1] if i < len(ts) - 1 else 1.0
        b = 1 - a / ap
        g = eps_fn(z, t)
        mu = (z - b / math.sqrt(1 - a) * g) / math.sqrt(1 - b)
        z = mu + math.sqrt(b) * noise[i] if i < len(ts) - 1 else mu
        if keep_path:
            path.append(z.copy())
    return (z, np.array(path)) if keep_path else z


def demo_noise(seed, n, S):
    """The demos' random numbers: z_T (n x 2) then, for each of the S - 1 noisy steps, n x 2 normals."""
    r = JSRandom(seed)
    zT = r.normals(n)
    noise = np.array([r.normals(n) for _ in range(max(S - 1, 0))]).reshape(max(S - 1, 0), n, 2)
    return zT, noise


def demo_sample(params, sampler="ddim", S=50, eta=0.0, n=400, seed=1, kind="net", c=NULL, lam=1.0, keep_path=False):
    """Exactly what diffusion-sampling-demo.html and diffusion-guidance-demo.html compute."""
    zT, noise = demo_noise(seed, n, S)
    f = make_eps_fn(kind, c, lam, params)
    if sampler == "alg202":
        return sample_alg202(f, zT, S, noise, keep_path=keep_path)
    return sample_ddim(f, zT, S, eta, noise, keep_path=keep_path)


def export_denoiser_json(path=None):
    """Write ../data/ch20-denoiser.json: the network, the schedule and the spiral of the two sampling demos."""
    params, hist = denoiser()
    beta, alpha = schedule()
    d = {"T": T_STEPS, "beta1": BETA_1, "betaT": BETA_T, "freqs": [float("%.17g" % f) for f in FREQS],
         "layers": [{"W": W.tolist(), "b": b.tolist()} for W, b in params],
         "spiral": {"mu": np.round(SPIRAL.mu, 12).tolist(), "cls": SPIRAL.cls.tolist(), "sd": SPIRAL.SD},
         "loss": np.round(hist, 5).tolist()}
    path = path or os.path.join(WEB_DATA, "ch20-denoiser.json")
    os.makedirs(os.path.dirname(path), exist_ok=True)
    with open(path, "w") as f:
        json.dump(d, f, separators=(",", ":"))
    print("wrote", os.path.relpath(path), "(%.0f kB)" % (os.path.getsize(path) / 1e3))
    return path


def spiral_sample_js(n, seed, data=SPIRAL):
    """n points of the spiral drawn with the demos' generator: component floor(72 u), then SD * two normals."""
    r = JSRandom(seed)
    X, C = [], []
    for _ in range(n):
        k = min(int(r.u() * len(data.mu)), len(data.mu) - 1)
        e1, e2 = r.norm(), r.norm()
        X.append([data.mu[k, 0] + data.SD * e1, data.mu[k, 1] + data.SD * e2])
        C.append(int(data.cls[k]))
    return np.array(X), np.array(C), r


def forward_demo_run(n=300, seed=7, T=T_STEPS, b1=BETA_1, bT=BETA_T, kind="linear", t_show=50):
    """What diffusion-forward-demo.html computes: n spiral points, then (i) the chain (20.3) run to t_show with
    the generator's normals, and (ii) the closed form (20.8) at t_show with fresh normals."""
    X, C, r = spiral_sample_js(n, seed)
    beta, alpha = schedule(T, b1, bT, kind)
    Z = X.copy()
    for t in range(1, t_show + 1):
        E = r.normals(n)
        Z = math.sqrt(1 - beta[t - 1]) * Z + math.sqrt(beta[t - 1]) * E
    E = r.normals(n)
    a = alpha[t_show - 1] if t_show else 1.0
    Zc = math.sqrt(a) * X + math.sqrt(1 - a) * E
    return X, Z, Zc


# =========================================================================== 20.3 score matching
# the two-dimensional mixture of Figures 20.5 and 20.6
MIX2D = dict(w=np.array([0.45, 0.35, 0.2]),
             mu=np.array([[-1.3, -0.7], [1.4, -0.3], [0.1, 1.5]]),
             cov=np.array([[[0.35, 0.15], [0.15, 0.25]], [[0.25, -0.12], [-0.12, 0.4]], [[0.3, 0.0], [0.0, 0.15]]]))


def mix2d_logpdf_score(z, mix=MIX2D):
    """ln p and grad ln p of a full-covariance 2-D Gaussian mixture at the rows of z."""
    z = np.atleast_2d(z)
    lws, grads = [], []
    for w, mu, S in zip(mix["w"], mix["mu"], mix["cov"]):
        P = np.linalg.inv(S)
        d = z - mu
        lws.append(math.log(w) - 0.5 * np.einsum("ni,ij,nj->n", d, P, d) - 0.5 * math.log(np.linalg.det(2 * np.pi * S)))
        grads.append(-d @ P)
    L = np.stack(lws, 1)
    m = L.max(1, keepdims=True)
    r = np.exp(L - m)
    s = r.sum(1, keepdims=True)
    r /= s
    return (m + np.log(s))[:, 0], np.einsum("nk,kni->ni", r, np.stack(grads))


def langevin(score, x0, eta, steps, rng, keep_path=False):
    """Langevin dynamics (14.61): x <- x + eta score(x) + sqrt(2 eta) eps."""
    x = np.array(x0, dtype=float)
    path = [x.copy()]
    for _ in range(steps):
        x = x + eta * score(x) + math.sqrt(2 * eta) * rng.standard_normal(x.shape)
        if keep_path:
            path.append(x.copy())
    return (x, np.array(path)) if keep_path else x


def annealed_langevin(score_sigma, x0, sigmas, steps, eps, rng):
    """Annealed Langevin dynamics (Song and Ermon 2019): for each noise level sigma (largest first), run `steps`
    Langevin steps with eta = eps sigma^2 on the smoothed density q_sigma (scores score_sigma(x, sigma)).

    The step proportional to sigma^2 keeps the number of steps needed to cross q_sigma about the same at every level."""
    x = np.array(x0, dtype=float)
    for s in sigmas:
        eta = eps * s * s
        for _ in range(steps):
            x = x + eta * score_sigma(x, s) + math.sqrt(2 * eta) * rng.standard_normal(x.shape)
    return x


def mix1d_smoothed(sigma, mix=MIX1D):
    """The Parzen-smoothed density q_sigma (20.47) of the 1-D mixture: the variances grow by sigma^2."""
    return dict(w=mix["w"], mu=mix["mu"], sd=np.sqrt(mix["sd"] ** 2 + sigma ** 2))


def rbf_features(z, centres, width):
    return np.exp(-0.5 * ((np.asarray(z)[..., None] - centres) / width) ** 2)


def esm_dsm_losses(W, sigma, centres, width, mix=MIX1D, n_grid=4001):
    """Explicit score matching (20.49) and denoising score matching (20.50) for the linear score model
    s(z, w) = sum_k w_k phi_k(z) on the 1-D mixture, both by quadrature (W is a list of weight vectors).

    Uses: z | x ~ N(x, sigma^2); E[x | z] for the mixture is available in closed form, and
    J_DSM = 1/2 E_z[s^2] - E_z[s(z) (E[x|z] - z)/sigma^2] + 1/2 E[(z - x)^2]/sigma^4.
    Returns (J_ESM, J_DSM) as arrays.
    """
    qs = mix1d_smoothed(sigma, mix)
    lo, hi = qs["mu"].min() - 8 * qs["sd"].max(), qs["mu"].max() + 8 * qs["sd"].max()
    z = np.linspace(lo, hi, n_grid)
    q = mix1d_pdf(z, qs["w"], qs["mu"], qs["sd"])
    # true score of q_sigma, and the posterior mean E[x | z]
    comp = qs["w"] * np.exp(-0.5 * ((z[:, None] - qs["mu"]) / qs["sd"]) ** 2) / (np.sqrt(2 * np.pi) * qs["sd"])
    r = comp / comp.sum(1, keepdims=True)
    score = (r * (-(z[:, None] - qs["mu"]) / qs["sd"] ** 2)).sum(1)
    sd2 = mix["sd"] ** 2
    post_mean_k = (sigma ** 2 * mix["mu"] + sd2 * z[:, None]) / (sd2 + sigma ** 2)
    Ex = (r * post_mean_k).sum(1)
    Phi = rbf_features(z, centres, width)
    J1, J2 = [], []
    for w in W:
        s = Phi @ w
        J1.append(0.5 * np.trapz((s - score) ** 2 * q, z))
        J2.append(0.5 * np.trapz(s * s * q, z) - np.trapz(s * (Ex - z) / sigma ** 2 * q, z) + 0.5 / sigma ** 2)
    return np.array(J1), np.array(J2)


def esm_dsm_constant(sigma, mix=MIX1D, n_grid=4001):
    """J_DSM - J_ESM = 1/2 (1/sigma^2 - E_q[(d/dz ln q_sigma)^2]) for D = 1."""
    qs = mix1d_smoothed(sigma, mix)
    lo, hi = qs["mu"].min() - 8 * qs["sd"].max(), qs["mu"].max() + 8 * qs["sd"].max()
    z = np.linspace(lo, hi, n_grid)
    q = mix1d_pdf(z, qs["w"], qs["mu"], qs["sd"])
    comp = qs["w"] * np.exp(-0.5 * ((z[:, None] - qs["mu"]) / qs["sd"]) ** 2) / (np.sqrt(2 * np.pi) * qs["sd"])
    r = comp / comp.sum(1, keepdims=True)
    score = (r * (-(z[:, None] - qs["mu"]) / qs["sd"] ** 2)).sum(1)
    return 0.5 * (1 / sigma ** 2 - np.trapz(score ** 2 * q, z))


# --------------------------------------------------------------------------- continuous time (Section 20.3.4)
BMIN, BMAX = T_STEPS * BETA_1, T_STEPS * BETA_T     # beta(s) on s in [0, 1]: the T -> infinity limit of our schedule


def vp_alpha(s):
    """alpha(s) = exp(-int_0^s beta(u) du) for beta(s) = BMIN + s (BMAX - BMIN) (the limit of (20.7))."""
    return np.exp(-(BMIN * s + 0.5 * (BMAX - BMIN) * s * s))


def vp_beta(s):
    return BMIN + s * (BMAX - BMIN)


def mix1d_noised(s, mix=MIX1D):
    """The marginal p_s of the VP SDE (20.70) started from the 1-D mixture."""
    a = vp_alpha(s)
    return dict(w=mix["w"], mu=math.sqrt(a) * mix["mu"], sd=np.sqrt(a * mix["sd"] ** 2 + 1 - a))


def mix1d_score_at(z, mix):
    z = np.asarray(z, dtype=float)
    lw = np.log(mix["w"]) - np.log(mix["sd"]) - 0.5 * ((z[..., None] - mix["mu"]) / mix["sd"]) ** 2
    r = np.exp(lw - lw.max(-1, keepdims=True))
    r /= r.sum(-1, keepdims=True)
    g = -(z[..., None] - mix["mu"]) / mix["sd"] ** 2
    s = (r * g).sum(-1)
    h = (r * (g * g - 1 / mix["sd"] ** 2)).sum(-1) - s * s
    return s, h


def sde_reverse(z1, n_steps, rng, mix=MIX1D, keep_path=True):
    """Euler-Maruyama for the reverse SDE (20.56) of dz = -beta z/2 ds + sqrt(beta) dv, from s = 1 to 0."""
    ds = 1.0 / n_steps
    z = np.array(z1, dtype=float)
    path = [z.copy()]
    for i in range(n_steps, 0, -1):
        s = i * ds
        b = vp_beta(s)
        sc, _ = mix1d_score_at(z, mix1d_noised(s, mix))
        z = z + (0.5 * b * z + b * sc) * ds + math.sqrt(b * ds) * rng.standard_normal(z.shape)
        path.append(z.copy())
    return np.array(path) if keep_path else z


def ode_flow(z1, n_steps, mix=MIX1D, with_logdet=False):
    """The probability-flow ODE (20.57) dz/ds = -beta z/2 - beta score/2, integrated from s = 1 to 0 with RK4.

    With with_logdet, also integrates d/ds ln p_s(z(s)) = -div f~ = beta/2 + beta h/2 (the instantaneous change of
    variables), so that ln p_0(z(0)) = ln p_1(z(1)) + the integral (Chen et al. 2018; Song et al. 2020)."""
    def f(z, s):
        b = vp_beta(s)
        sc, h = mix1d_score_at(z, mix1d_noised(s, mix))
        return -0.5 * b * z - 0.5 * b * sc, -(-0.5 * b - 0.5 * b * h)   # (drift, d ln p / ds along the path)
    ds = -1.0 / n_steps
    z = np.array(z1, dtype=float)
    lp = np.zeros_like(z)
    path = [z.copy()]
    s = 1.0
    for _ in range(n_steps):
        k1, l1 = f(z, s)
        k2, l2 = f(z + 0.5 * ds * k1, s + 0.5 * ds)
        k3, l3 = f(z + 0.5 * ds * k2, s + 0.5 * ds)
        k4, l4 = f(z + ds * k3, s + ds)
        z = z + ds / 6 * (k1 + 2 * k2 + 2 * k3 + k4)
        lp = lp + ds / 6 * (l1 + 2 * l2 + 2 * l3 + l4)
        s += ds
        path.append(z.copy())
    return (np.array(path), lp) if with_logdet else np.array(path)


# =========================================================================== figures
def _square(ax, lim=2.6):
    ax.set_xlim(-lim, lim)
    ax.set_ylim(-lim, lim)
    ax.set_aspect("equal")
    ax.set_xticks([])
    ax.set_yticks([])


def fig_20_1(out_dir=None):
    """An MNIST digit corrupted by the forward chain (20.3) (a small-scale version of the book's photograph)."""
    X, y = common.mnist(False)
    x = X[np.where(y == 3)[0][0]].reshape(28, 28) * 2 - 1
    beta, alpha = schedule()
    show = [0, 5, 15, 30, 60, 100, 200]
    rng = np.random.default_rng(1)
    Z = forward_chain(x, beta, rng, keep=show[1:])
    Z[0] = x
    fig, axes = plt.subplots(1, len(show), figsize=(1.45 * len(show), 1.9))
    for ax, t in zip(axes, show):
        ax.imshow(Z[t], cmap="gray", vmin=-2.2, vmax=2.2)
        ax.set_xticks([])
        ax.set_yticks([])
        lab = r"$\mathbf{x}$" if t == 0 else r"$\mathbf{z}_{%d}$" % t
        ax.set_title(lab, fontsize=10)
        if t:
            ax.set_xlabel(r"$\sqrt{\alpha_t}=%.2f$" % math.sqrt(alpha[t - 1]), fontsize=8)
    fig.tight_layout(w_pad=0.3)
    return savefig(fig, CH, "fig20-1", out_dir)


def _fig_reverse(beta, zt, name, out_dir, approx=False):
    grid = np.linspace(-4.5, 4.5, 3001)
    post, prior = reverse_1d(zt, beta, grid)
    fig, axes = plt.subplots(1, 2, figsize=(7.6, 2.7))
    ax = axes[0]
    zprev = 0.6
    zz = np.linspace(-4.5, 4.5, 800)
    ax.plot(zz, np.exp(-0.5 * (zz - math.sqrt(1 - beta) * zprev) ** 2 / beta) / math.sqrt(2 * np.pi * beta), color=common.BLUE)
    ax.axvline(zprev, color=common.GREY, lw=0.8, ls=":")
    ax.text(zprev, ax.get_ylim()[1] * 0.97, r" $z_{t-1}$", va="top", fontsize=9, color=common.GREY)
    ax.set_xlabel(r"$z_t$")
    ax.set_title(r"$q(z_t\,|\,z_{t-1})$, $\beta_t=%g$" % beta)
    ax.set_yticks([])
    ax = axes[1]
    ax.plot(grid, prior / prior.max(), color=common.RED, label=r"$q(z_{t-1})$")
    ax.plot(grid, post / post.max(), color=common.BLUE, label=r"$q(z_{t-1}\,|\,z_t)$")
    if approx:
        s, h = mix1d_score_hess(zt)
        m_ = zt + beta * (0.5 * zt + s)
        v_ = beta + beta ** 2 * (1 + h)
        g = np.exp(-0.5 * (grid - m_) ** 2 / v_)
        ax.plot(grid, g, color="k", ls="--", lw=1, label="Gaussian, Ex. 20.7")
    ax.axvline(zt, color=common.GREY, lw=0.8, ls=":")
    ax.text(zt, 1.08, r"$z_t$", ha="center", fontsize=9, color=common.GREY)
    ax.set_ylim(0, 1.15)
    ax.set_yticks([])
    ax.set_xlabel(r"$z_{t-1}$")
    ax.legend(fontsize=8, frameon=False, loc="upper left")
    fig.tight_layout()
    return savefig(fig, CH, name, out_dir)


def fig_20_3(out_dir=None):
    """The reverse distribution q(z_{t-1} | z_t) by Bayes' theorem (20.11) for a large beta_t: multimodal."""
    return _fig_reverse(0.6, 0.55, "fig20-3", out_dir)


def fig_20_4(out_dir=None):
    """As Figure 20.3 with a small beta_t: the reverse distribution is nearly Gaussian with variance about beta_t."""
    return _fig_reverse(0.02, 0.55, "fig20-4", out_dir, approx=True)


def _mix2d_grid(lim=3.0, n=200):
    g = np.linspace(-lim, lim, n)
    XX, YY = np.meshgrid(g, g)
    lp, _ = mix2d_logpdf_score(np.stack([XX.ravel(), YY.ravel()], 1))
    return XX, YY, np.exp(lp).reshape(XX.shape)


def fig_20_5(out_dir=None):
    """A 2-D Gaussian mixture as a heat map and its score function (20.42) as arrows on a grid."""
    XX, YY, P = _mix2d_grid()
    fig, ax = plt.subplots(figsize=(4.2, 4.0))
    ax.imshow(P, extent=(-3, 3, -3, 3), origin="lower", cmap="magma")
    g = np.linspace(-2.75, 2.75, 16)
    GX, GY = np.meshgrid(g, g)
    _, S = mix2d_logpdf_score(np.stack([GX.ravel(), GY.ravel()], 1))
    L = np.linalg.norm(S, axis=1, keepdims=True)
    Sn = S / np.maximum(L, 1e-9) * np.minimum(L, 4.0) ** 0.5     # compress long arrows, keep the direction
    ax.quiver(GX.ravel(), GY.ravel(), Sn[:, 0], Sn[:, 1], color="white", scale=40, width=0.004)
    ax.set_xticks([])
    ax.set_yticks([])
    fig.tight_layout()
    return savefig(fig, CH, "fig20-5", out_dir)


def fig_20_6(out_dir=None):
    """Three Langevin trajectories (14.61) on the density of Figure 20.5, all starting at the centre."""
    XX, YY, P = _mix2d_grid()
    fig, ax = plt.subplots(figsize=(4.2, 4.0))
    ax.imshow(P, extent=(-3, 3, -3, 3), origin="lower", cmap="magma")
    rng = np.random.default_rng(4)
    score = lambda x: mix2d_logpdf_score(x)[1]  # noqa: E731
    for col in ("white", common.CYAN, "#9be36f"):
        _, path = langevin(score, np.zeros((1, 2)), 0.01, 600, rng, keep_path=True)
        ax.plot(path[:, 0, 0], path[:, 0, 1], color=col, lw=0.8)
        ax.plot(path[-1, 0, 0], path[-1, 0, 1], "o", color=col, ms=4)
    ax.plot(0, 0, "s", color="white", ms=5)
    ax.set_xlim(-3, 3)
    ax.set_ylim(-3, 3)
    ax.set_xticks([])
    ax.set_yticks([])
    fig.tight_layout()
    return savefig(fig, CH, "fig20-6", out_dir)


def fig_20_s1(out_dir=None):
    """Forward process on the spiral: the chain (20.3) step by step against the closed form (20.8), and the schedule."""
    rng = np.random.default_rng(2)
    x, _ = SPIRAL.sample(1500, rng)
    beta, alpha = schedule()
    show = [10, 40, 100, 200]
    Zc = forward_chain(x, beta, rng, keep=show)
    fig = plt.figure(figsize=(12.4, 2.75))
    gs = fig.add_gridspec(1, 6, width_ratios=[1, 1, 1, 1, 1, 1.35])
    ax = fig.add_subplot(gs[0])
    ax.scatter(x[:, 0], x[:, 1], s=1.5, color="k", rasterized=True)
    ax.set_title(r"data $\mathbf{x}$")
    _square(ax, 3.2)
    for j, t in enumerate(show):
        ax = fig.add_subplot(gs[j + 1])
        Zo = forward_closed(x, alpha[t - 1], rng.standard_normal(x.shape))
        ax.scatter(Zc[t][:, 0], Zc[t][:, 1], s=1.2, color=common.BLUE, alpha=0.6, label="chain (20.3)", rasterized=True)
        ax.scatter(Zo[:, 0], Zo[:, 1], s=1.2, color=common.ORANGE, alpha=0.6, label="closed form (20.8)", rasterized=True)
        ax.set_title(r"$t=%d$, $\alpha_t=%.3f$" % (t, alpha[t - 1]), fontsize=9.5)
        _square(ax, 3.2)
        if j == 0:
            ax.legend(fontsize=7, markerscale=4, frameon=False, loc="lower left")
    ax = fig.add_subplot(gs[5])
    tt = np.arange(1, T_STEPS + 1)
    ax.plot(tt, np.sqrt(alpha), color=common.BLUE, label=r"$\sqrt{\alpha_t}$ (signal)")
    ax.plot(tt, np.sqrt(1 - alpha), color=common.RED, label=r"$\sqrt{1-\alpha_t}$ (noise)")
    ax.plot(tt, beta / beta.max(), color=common.GREY, ls="--", label=r"$\beta_t/\beta_T$")
    _, ac = schedule(kind="cosine")
    ax.plot(tt, np.sqrt(ac), color=common.BLUE, ls=":", label=r"$\sqrt{\alpha_t}$, cosine")
    ax.set_xlabel("step $t$")
    ax.legend(fontsize=7, frameon=False)
    fig.tight_layout()
    return savefig(fig, CH, "fig20-s1", out_dir)


def fig_20_s2(out_dir=None):
    """(a) q(z_{t-1}|z_t,x) as a product of two Gaussians in z_{t-1}; (b) Exercise 20.7: error orders in beta."""
    beta, alpha = schedule()
    t, x, zt = 40, 1.5, 0.4
    grid = np.linspace(-2.5, 3.0, 2001)
    ap = alpha[t - 2]
    prior = np.exp(-0.5 * (grid - math.sqrt(ap) * x) ** 2 / (1 - ap))
    lik = np.exp(-0.5 * (zt - math.sqrt(1 - beta[t - 1]) * grid) ** 2 / beta[t - 1])
    prod = prior * lik
    prod /= np.trapz(prod, grid)
    m, v = posterior_mean_var(x, zt, t, beta, alpha)
    fig, axes = plt.subplots(1, 2, figsize=(9.6, 3.0))
    ax = axes[0]
    ax.plot(grid, prior / prior.max(), color=common.RED, label=r"$q(z_{t-1}\,|\,x)$ (20.6)")
    ax.plot(grid, lik / lik.max(), color=common.GREEN, label=r"$q(z_t\,|\,z_{t-1})$ as a function of $z_{t-1}$")
    ax.plot(grid, prod / prod.max(), color=common.BLUE, lw=2.4, label="normalised product")
    ax.plot(grid, np.exp(-0.5 * (grid - m) ** 2 / v), color="k", ls="--", lw=1, label=r"$\mathcal{N}(m_t,\sigma_t^2)$ (20.15)")
    ax.set_xlabel(r"$z_{t-1}$")
    ax.set_yticks([])
    ax.set_ylim(0, 1.5)
    ax.set_title(r"$t=%d$, $x=%g$, $z_t=%g$" % (t, x, zt), fontsize=9.5)
    ax.legend(fontsize=7, frameon=False, loc="upper left", ncol=2)
    ax = axes[1]
    bs = np.logspace(-4, -0.7, 25)
    z0 = 0.55
    s, h = mix1d_score_hess(z0)
    e0m, e1m, e0v, e1v = [], [], [], []
    for b in bs:
        mean, var = reverse_1d_moments(z0, b)
        e0m.append(abs(mean - z0))
        e1m.append(abs(mean - z0 - b * (0.5 * z0 + s)))
        e0v.append(abs(var - b))
        e1v.append(abs(var - b - b * b * (1 + h)))
    ax.loglog(bs, e0m, color=common.BLUE, label=r"mean: $|m-z_t|$  ($\propto\beta$)")
    ax.loglog(bs, e1m, color=common.BLUE, ls="--", label=r"mean, first-order corrected ($\propto\beta^2$)")
    ax.loglog(bs, e0v, color=common.RED, label=r"variance: $|v-\beta|$  ($\propto\beta^2$)")
    ax.loglog(bs, e1v, color=common.RED, ls="--", label=r"variance, corrected ($\propto\beta^3$)")
    ax.set_xlabel(r"$\beta_t$")
    ax.set_title(r"exact moments of $q(z_{t-1}\,|\,z_t)$ against Exercise 20.7", fontsize=9.5)
    ax.legend(fontsize=7, frameon=False)
    fig.tight_layout()
    return savefig(fig, CH, "fig20-s2", out_dir)


def per_step_losses(params, ts, n=4000, seed=11, c=NULL):
    """E||g(z_t, t) - eps||^2 for the network and for the exact optimum E[eps | z_t], at the steps ts."""
    rng = np.random.default_rng(seed)
    beta, alpha = schedule()
    net_l, opt_l = [], []
    for t in ts:
        x, _ = SPIRAL.sample(n, rng, None if c == NULL else c)
        e = rng.standard_normal((n, 2))
        z = forward_closed(x, alpha[t - 1], e)
        net_l.append(((np_denoiser(params, z, t, c) - e) ** 2).sum(1).mean())
        opt_l.append(((eps_star(z, alpha[t - 1], None if c == NULL else c) - e) ** 2).sum(1).mean())
    return np.array(net_l), np.array(opt_l)


def fig_20_s3(out_dir=None):
    """ELBO weights (20.37), per-step loss of the trained network against the exact optimum, and training curve."""
    params, hist = denoiser()
    beta, alpha = schedule()
    tt = np.arange(1, T_STEPS + 1)
    fig, axes = plt.subplots(1, 3, figsize=(12.0, 3.0))
    ax = axes[0]
    w = elbo_weights(beta, alpha)
    ax.semilogy(tt, w, color=common.BLUE, label=r"ELBO weight $\beta_t/2(1-\alpha_t)(1-\beta_t)$")
    ax.semilogy(tt, np.full_like(w, 1.0), color=common.RED, ls="--", label="simplified loss (20.40): 1")
    ax.set_xlabel("step $t$")
    ax.legend(fontsize=7.5, frameon=False)
    ax.set_title("weight of each step in the loss", fontsize=9.5)
    ax = axes[1]
    ts = np.array([1, 2, 4, 7, 10, 15, 20, 30, 45, 60, 80, 100, 130, 160, 200])
    nl, ol = per_step_losses(params, ts)
    ax.plot(ts, nl, "o-", color=common.BLUE, ms=3, label=r"trained $g(\mathbf{z}_t,\mathbf{w},t)$")
    ax.plot(ts, ol, "s--", color="k", ms=3, lw=1, label=r"exact optimum $\mathbb{E}[\boldsymbol{\epsilon}\,|\,\mathbf{z}_t]$")
    ax.set_xscale("log")
    ax.set_xlabel("step $t$")
    ax.set_ylabel(r"$\mathbb{E}\,\|g-\boldsymbol{\epsilon}\|^2$")
    ax.set_title("unconditional loss per step (D = 2)", fontsize=9.5)
    ax.legend(fontsize=7.5, frameon=False)
    ax = axes[2]
    ax.plot(np.arange(1, len(hist) + 1) * 200, hist, color=common.BLUE, lw=1)
    ax.set_xlabel("iteration")
    ax.set_ylabel("training loss (200-iteration mean)")
    ax.set_title("Algorithm 20.1 (with 20% null class)", fontsize=9.5)
    fig.tight_layout()
    return savefig(fig, CH, "fig20-s3", out_dir)


def sample_quality(X, c=None):
    """Mean of ln p(x) (or ln p(x | c)) of samples under the true spiral density: higher is better."""
    w, mu = SPIRAL.comps(c)
    return mix_logpdf_score(X, w, mu, SPIRAL.SD ** 2)[0].mean()


def fig_20_s4(out_dir=None):
    """Samples from the trained denoiser and from the exact E[eps | z_t], for several samplers and step counts."""
    params, _ = denoiser()
    cols = [("alg202", 200, 0, "Algorithm 20.2, 200 steps"), ("ddim", 200, 0.0, r"DDIM $\eta=0$, 200 steps"),
            ("alg202", 20, 0, "Algorithm 20.2, 20 steps"), ("ddim", 20, 0.0, r"DDIM $\eta=0$, 20 steps"),
            ("ddim", 5, 0.0, r"DDIM $\eta=0$, 5 steps")]
    fig, axes = plt.subplots(2, 5, figsize=(12.5, 5.4))
    for i, kind in enumerate(("net", "exact")):
        for j, (smp, S, eta, title) in enumerate(cols):
            X, path = demo_sample(params, smp, S, eta, n=1200, seed=3, kind=kind, keep_path=True)
            ax = axes[i, j]
            ax.scatter(X[:, 0], X[:, 1], s=1.2, color=common.BLUE if kind == "net" else common.GREEN, rasterized=True)
            for k in range(3):
                ax.plot(path[:, k, 0], path[:, k, 1], color=common.RED, lw=0.6, alpha=0.8)
            _square(ax, 2.7)
            ax.set_title(title + "\n" + (r"mean $\ln p$: %.2f" % sample_quality(X)), fontsize=8.5)
            if j == 0:
                ax.set_ylabel("trained network" if kind == "net" else r"exact $\mathbb{E}[\boldsymbol{\epsilon}|\mathbf{z}_t]$")
    fig.tight_layout()
    return savefig(fig, CH, "fig20-s4", out_dir)


def fig_20_s5(out_dir=None):
    """Explicit (20.49) and denoising (20.50) score matching differ by a constant for every score model."""
    centres = np.linspace(-4, 4, 17)
    width = 0.6
    rng = np.random.default_rng(3)
    w0 = rng.normal(0, 1, len(centres))
    d = rng.normal(0, 1, len(centres))
    ts = np.linspace(-2.5, 2.5, 41)
    fig, axes = plt.subplots(1, 3, figsize=(12.0, 3.0))
    ax = axes[0]
    for sigma, col in ((0.3, common.BLUE), (0.8, common.RED)):
        W = [w0 + t * d for t in ts]
        J1, J2 = esm_dsm_losses(W, sigma, centres, width)
        ax.plot(ts, J1, color=col, label=r"$J_{\rm ESM}$, $\sigma=%g$" % sigma)
        ax.plot(ts, J2, color=col, ls="--", label=r"$J_{\rm DSM}$, $\sigma=%g$" % sigma)
    ax.set_xlabel(r"position along a line in $\mathbf{w}$-space")
    ax.set_title("the two losses along a random line", fontsize=9.5)
    ax.legend(fontsize=7, frameon=False)
    ax = axes[1]
    sig = np.linspace(0.15, 1.5, 30)
    for k, col in zip(range(3), (common.BLUE, common.RED, common.GREEN)):
        Wk = [rng.normal(0, 1, len(centres))]
        diff = [np.subtract(*esm_dsm_losses(Wk, s_, centres, width)[::-1])[0] for s_ in sig]
        ax.plot(sig, diff, "o", color=col, ms=3, label="random $\\mathbf{w}$ no. %d" % (k + 1))
    ax.plot(sig, [esm_dsm_constant(s_) for s_ in sig], color="k", lw=1, label=r"$\frac{1}{2}(\sigma^{-2}-\mathbb{E}_{q_\sigma}[(\ln q_\sigma)'^{\,2}])$")
    ax.set_yscale("log")
    ax.set_xlabel(r"$\sigma$")
    ax.set_title(r"$J_{\rm DSM}-J_{\rm ESM}$ does not depend on $\mathbf{w}$", fontsize=9.5)
    ax.legend(fontsize=7, frameon=False)
    ax = axes[2]
    sigma = 0.3
    qs = mix1d_smoothed(sigma)
    zz = np.linspace(-4, 4, 800)
    Phi = rbf_features(zz, centres, width)
    # minimise DSM by least squares (it is quadratic in w): solve the normal equations on the quadrature grid
    zq = np.linspace(-6, 6, 6001)
    q = mix1d_pdf(zq, qs["w"], qs["mu"], qs["sd"])
    comp = qs["w"] * np.exp(-0.5 * ((zq[:, None] - qs["mu"]) / qs["sd"]) ** 2) / (np.sqrt(2 * np.pi) * qs["sd"])
    r = comp / comp.sum(1, keepdims=True)
    sd2 = MIX1D["sd"] ** 2
    Ex = (r * (sigma ** 2 * MIX1D["mu"] + sd2 * zq[:, None]) / (sd2 + sigma ** 2)).sum(1)
    Pq = rbf_features(zq, centres, width)
    A = (Pq * q[:, None]).T @ Pq
    bvec = (Pq * (q * (Ex - zq) / sigma ** 2)[:, None]).sum(0)
    w_dsm = np.linalg.solve(A + 1e-10 * np.eye(len(centres)), bvec)
    s_true, _ = mix1d_score_at(zz, qs)
    ax.plot(zz, s_true, color="k", lw=2.2, label=r"true score of $q_\sigma$")
    ax.plot(zz, Phi @ w_dsm, color=common.ORANGE, ls="--", label="DSM minimiser")
    ax2 = ax.twinx()
    ax2.fill_between(zz, mix1d_pdf(zz, qs["w"], qs["mu"], qs["sd"]), color=common.GREY, alpha=0.2)
    ax2.set_yticks([])
    ax.set_xlabel("$z$")
    ax.set_title(r"the denoising minimiser recovers $\nabla\ln q_\sigma$ ($\sigma=0.3$)", fontsize=9.5)
    ax.legend(fontsize=7, frameon=False, loc="lower left")
    fig.tight_layout()
    return savefig(fig, CH, "fig20-s5", out_dir)


# the two separated wells of Figure 20.S6 and Exercise 20.18
WELLS = dict(w=np.array([0.8, 0.2]), mu=np.array([-3.0, 3.0]), sd=np.array([0.5, 0.5]))


def wells_experiment(n=2000, seed=6):
    """Fraction of samples in the right well (target 0.2): plain Langevin on p, and annealed Langevin."""
    rng = np.random.default_rng(seed)
    x0 = rng.uniform(-8, 8, n)
    score_p = lambda x: mix1d_score_at(x, WELLS)[0]  # noqa: E731
    plain = langevin(score_p, x0, 0.01, 3000, rng)
    sigmas = np.geomspace(6.0, 0.1, 15)
    score_s = lambda x, s: mix1d_score_at(x, mix1d_smoothed(s, WELLS))[0]  # noqa: E731
    ann = annealed_langevin(score_s, x0, sigmas, 200, 0.1, rng)
    return x0, plain, ann, sigmas


def fig_20_s6(out_dir=None):
    """Exercise 20.18: plain Langevin keeps the starting proportions; annealing over noise levels fixes them."""
    x0, plain, ann, sigmas = wells_experiment()
    zz = np.linspace(-6, 6, 600)
    fig, axes = plt.subplots(1, 3, figsize=(12.0, 2.9))
    ax = axes[0]
    for s, col in ((sigmas[0], common.GREY), (1.0, common.ORANGE), (0.3, common.BLUE), (0.0, "k")):
        m = mix1d_smoothed(s, WELLS)
        ax.plot(zz, mix1d_pdf(zz, m["w"], m["mu"], m["sd"]), color=col, label=r"$q_\sigma$, $\sigma=%.2g$" % s)
    ax.set_title("the target and its smoothed versions", fontsize=9.5)
    ax.legend(fontsize=7, frameon=False)
    ax.set_xlabel("$x$")
    for ax, X, title in ((axes[1], plain, "Langevin on $p$ (3000 steps)"), (axes[2], ann, "annealed Langevin (15 levels)")):
        ax.hist(X, bins=np.linspace(-6, 6, 80), density=True, color=common.BLUE, alpha=0.6)
        ax.plot(zz, mix1d_pdf(zz, WELLS["w"], WELLS["mu"], WELLS["sd"]), color="k", lw=1.2)
        ax.set_title("%s: right well %.2f (target 0.20)" % (title, np.mean(X > 0)), fontsize=9.5)
        ax.set_xlabel("$x$")
    fig.tight_layout()
    return savefig(fig, CH, "fig20-s6", out_dir)


def fig_20_s7(out_dir=None):
    """The reverse SDE (20.56) and the probability-flow ODE (20.57) on a 1-D mixture: same marginals."""
    rng = np.random.default_rng(8)
    n_paths = 4000
    z1 = rng.standard_normal(n_paths)
    P_sde = sde_reverse(z1, 1000, rng)
    P_ode = ode_flow(z1, 200)
    s_grid = np.linspace(0, 1, 201)
    zg = np.linspace(-3.5, 3.5, 300)
    dens = np.array([mix1d_pdf(zg, **{k: v for k, v in mix1d_noised(s).items()}) for s in s_grid]).T
    fig, axes = plt.subplots(1, 3, figsize=(12.4, 3.1), gridspec_kw=dict(width_ratios=[1.3, 1.3, 1]))
    for ax, P, n_st, title in ((axes[0], P_sde, 1000, "reverse SDE (Euler-Maruyama, 1000 steps)"),
                               (axes[1], P_ode, 200, "probability-flow ODE (RK4, 200 steps)")):
        ax.imshow(dens, extent=(0, 1, -3.5, 3.5), origin="lower", aspect="auto", cmap="Greys", vmax=dens.max() * 0.9)
        ss = np.linspace(1, 0, n_st + 1)
        for k in range(14):
            ax.plot(ss, P[:, k], lw=0.7, color=plt.cm.viridis(k / 13))
        ax.set_xlim(1, 0)
        ax.set_xlabel("time $s$ (runs from 1 to 0)")
        ax.set_ylabel("$z$")
        ax.set_title(title, fontsize=9.5)
    ax = axes[2]
    bins = np.linspace(-3.5, 3.5, 70)
    ax.hist(P_sde[-1], bins=bins, density=True, histtype="step", color=common.RED, label="SDE")
    ax.hist(P_ode[-1], bins=bins, density=True, histtype="step", color=common.BLUE, label="ODE")
    ax.plot(zg, mix1d_pdf(zg, MIX1D["w"], MIX1D["mu"], MIX1D["sd"]), color="k", lw=1, label="data density")
    ax.set_title("samples at $s=0$ (4000 paths)", fontsize=9.5)
    ax.legend(fontsize=7.5, frameon=False)
    fig.tight_layout()
    return savefig(fig, CH, "fig20-s7", out_dir)


def tilted_logpdf(X, c, lam):
    """ln of p(x | c)^lam p(x)^(1 - lam), unnormalised: the 'guided' target at t = 0."""
    var = SPIRAL.SD ** 2
    wc, muc = SPIRAL.comps(c)
    w, mu = SPIRAL.comps(None)
    return lam * mix_logpdf_score(X, wc, muc, var)[0] + (1 - lam) * mix_logpdf_score(X, w, mu, var)[0]


def tilted_radius_density(c, lam, rb, n_grid=500, lim=3.0):
    """Density of ||x|| under the normalised tilted density p(x | c)^lam p(x)^(1 - lam), by quadrature on a grid."""
    g = np.linspace(-lim, lim, n_grid)
    GX, GY = np.meshgrid(g, g)
    P = np.stack([GX.ravel(), GY.ravel()], 1)
    L = tilted_logpdf(P, c, lam)
    w = np.exp(L - L.max())
    w /= w.sum()
    r = np.linalg.norm(P, axis=1)
    h, _ = np.histogram(r, bins=rb, weights=w)
    mid = 0.5 * (rb[1:] + rb[:-1])
    return mid, h / np.diff(rb)


def guidance_metrics(X, c):
    """(mean p(c | x) under the exact clean classifier, spread = sqrt of the trace of the sample covariance)."""
    pc = class_posterior(X, 1.0)[:, c]
    return pc.mean(), math.sqrt(np.trace(np.cov(X.T)))


def fig_20_7(out_dir=None):
    """Classifier-free guidance, reproduced at small scale: the 2-D spiral and 14 x 14 MNIST digits."""
    params, _ = denoiser()
    lams = [0.0, 1.0, 4.0]
    fig = plt.figure(figsize=(12.6, 3.3))
    gs = fig.add_gridspec(1, 5, width_ratios=[1, 1, 1, 1.25, 1.25])
    for j, lam in enumerate(lams):
        ax = fig.add_subplot(gs[j])
        X = demo_sample(params, "ddim", 100, 1.0, n=1000, seed=5, kind="net", c=0, lam=lam)
        _, mu = SPIRAL.comps(None)
        ax.scatter(mu[:, 0], mu[:, 1], s=4, color="#dddddd")
        ax.scatter(X[:, 0], X[:, 1], s=1.2, color=common.BLUE, rasterized=True)
        pc, spread = guidance_metrics(X, 0)
        ax.set_title(r"$\lambda=%g$: $\bar p(c|\mathbf{x})=%.3f$, spread %.2f" % (lam, pc, spread), fontsize=8.5)
        _square(ax, 2.6)
    mn = mnist_model()
    for j, lam in enumerate((1.0, 4.0)):
        ax = fig.add_subplot(gs[3 + j])
        imgs = mnist_sample(mn, labels=np.tile([2, 3, 5, 8], 6), lam=lam, seed=4)
        ax.imshow(tile(imgs, 4), cmap="gray", vmin=-1, vmax=1)
        ax.set_xticks([])
        ax.set_yticks([])
        ax.set_title(r"MNIST 14$\times$14, digits 2, 3, 5, 8, $\lambda=%g$" % lam, fontsize=8.5)
    fig.tight_layout()
    return savefig(fig, CH, "fig20-7", out_dir)


def fig_20_s8(out_dir=None):
    """Guidance strength against class agreement and diversity; guided samples against the tilted target."""
    params, _ = denoiser()
    lams = [0, 0.5, 1, 1.5, 2, 3, 4, 6, 8]
    res = {k: [] for k in ("net", "exact")}
    for kind in res:
        for lam in lams:
            X = demo_sample(params, "ddim", 100, 1.0, n=800, seed=9, kind=kind, c=0, lam=lam)
            res[kind].append(guidance_metrics(X, 0))
    res = {k: np.array(v) for k, v in res.items()}
    fig, axes = plt.subplots(1, 3, figsize=(12.0, 3.1))
    ax = axes[0]
    ax.plot(lams, res["net"][:, 0], "o-", color=common.BLUE, ms=3, label="trained network (CFG)")
    ax.plot(lams, res["exact"][:, 0], "s--", color="k", ms=3, lw=1, label="exact guided score")
    ax.set_xlabel(r"guidance scale $\lambda$")
    ax.set_ylabel(r"mean $p(c\,|\,\mathbf{x})$ of samples")
    ax.legend(fontsize=7.5, frameon=False)
    ax.set_title("agreement with the class", fontsize=9.5)
    ax = axes[1]
    ax.plot(lams, res["net"][:, 1], "o-", color=common.BLUE, ms=3, label="trained network (CFG)")
    ax.plot(lams, res["exact"][:, 1], "s--", color="k", ms=3, lw=1, label="exact guided score")
    ax.set_xlabel(r"guidance scale $\lambda$")
    ax.set_ylabel("spread of the samples")
    ax.set_title("diversity", fontsize=9.5)
    ax.legend(fontsize=7.5, frameon=False)
    ax = axes[2]
    lam = 4.0
    rb = np.linspace(0, 2.6, 53)
    for lm, col, lab in ((1.0, common.GREY, r"$\lambda=1$ samples"), (lam, common.BLUE, r"$\lambda=4$ samples")):
        X = demo_sample(params, "ddim", 100, 1.0, n=3000, seed=9, kind="exact", c=0, lam=lm)
        ax.hist(np.linalg.norm(X, axis=1), bins=rb, density=True, histtype="step", color=col, lw=1.4, label=lab)
    r_t, d_t = tilted_radius_density(0, lam, rb)
    ax.plot(r_t, d_t, color=common.RED, lw=1.6, label=r"$p(\mathbf{x}|c)^{4}p(\mathbf{x})^{-3}$")
    ax.set_xlabel(r"distance from the centre $\|\mathbf{x}\|$")
    ax.set_title("guided samples are not samples of the tilted density", fontsize=9.5)
    ax.legend(fontsize=7.5, frameon=False)
    fig.tight_layout()
    return savefig(fig, CH, "fig20-s8", out_dir)


# =========================================================================== 14 x 14 MNIST (Figures 20.7-20.9)
MNIST_CACHE = os.path.join(CACHE_DIR, "ch20_mnist.pt")
MN_HIDDEN, MN_NULL = 768, 10


def _mnist_net(torch):
    nn = torch.nn

    class MnistDenoiser(nn.Module):
        """g(z, w, t, c) for 14 x 14 digits: a residual MLP; time features and a one-hot class (10 = null) enter
        every block. (A convolutional U-net would be the usual choice, but it is too slow to train on one CPU thread.)"""

        def __init__(self, H=MN_HIDDEN):
            super().__init__()
            self.inp = nn.Linear(196 + 32 + 11, H)
            self.h = nn.ModuleList([nn.Linear(H, H) for _ in range(3)])
            self.e = nn.ModuleList([nn.Linear(32 + 11, H) for _ in range(3)])
            self.out = nn.Linear(H, 196)

        def forward(self, z, t, c):
            f = torch.exp(torch.linspace(0, math.log(200.0), 16))
            tt = t[:, None].float() / T_STEPS
            e = torch.cat([torch.sin(f * tt), torch.cos(f * tt), nn.functional.one_hot(c, 11).float()], 1)
            h = nn.functional.silu(self.inp(torch.cat([z, e], 1)))
            for lin, el in zip(self.h, self.e):
                h = h + nn.functional.silu(lin(h) + el(e))
            return self.out(h)

    return MnistDenoiser()


def mnist14(train=True):
    """MNIST at 14 x 14 (2 x 2 average pooling), scaled to [-1, 1], as (N, 196) and labels."""
    X, y = common.mnist(train)
    return X.reshape(-1, 14, 2, 14, 2).mean((2, 4)).reshape(-1, 196) * 2 - 1, y


def mnist_model(retrain=False, iters=6000, seed=0):
    """The 14 x 14 MNIST denoiser: Algorithm 20.1 with a 15% null class, Adam, about four minutes on one thread."""
    torch = common.torch_setup(seed, threads=1)
    net = _mnist_net(torch)
    if os.path.exists(MNIST_CACHE) and not retrain:
        net.load_state_dict(torch.load(MNIST_CACHE))
        net.eval()
        return net
    print("training the 14 x 14 MNIST denoiser (about four minutes on one thread) ...")
    X, y = mnist14(True)
    beta, alpha = schedule()
    sqa = torch.tensor(np.sqrt(alpha), dtype=torch.float32)
    sq1 = torch.tensor(np.sqrt(1 - alpha), dtype=torch.float32)
    opt = torch.optim.Adam(net.parameters(), lr=1e-3)
    sch = torch.optim.lr_scheduler.OneCycleLR(opt, 1e-3, total_steps=iters, pct_start=0.05)
    Xt, yt = torch.tensor(X, dtype=torch.float32), torch.tensor(y)
    rng = np.random.default_rng(seed)
    run_l = 0.0
    for it in range(1, iters + 1):
        idx = torch.from_numpy(rng.integers(0, len(Xt), 256))
        x, c = Xt[idx], yt[idx].clone()
        c[torch.from_numpy(rng.random(256) < 0.15)] = MN_NULL
        t = torch.from_numpy(rng.integers(1, T_STEPS + 1, 256))
        e = torch.randn_like(x)
        z = sqa[t - 1, None] * x + sq1[t - 1, None] * e
        loss = ((net(z, t, c) - e) ** 2).mean()
        opt.zero_grad()
        loss.backward()
        opt.step()
        sch.step()
        run_l += loss.item()
        if it % 1000 == 0:
            print("  iteration %d, loss per pixel %.4f" % (it, run_l / 1000))
            run_l = 0.0
    os.makedirs(CACHE_DIR, exist_ok=True)
    torch.save(net.state_dict(), MNIST_CACHE)
    net.eval()
    return net


def mnist_sample(net, labels, lam=1.0, seed=0, project=None, var="beta"):
    """Algorithm 20.2 for the MNIST denoiser with classifier-free guidance (20.60) of scale lam.

    labels: one class per sample (MN_NULL for unconditional). project(z, t_prev, gen) may overwrite part of
    z_{t-1} after every step (used for inpainting and super-resolution); it receives the torch generator.
    var = 'beta' adds noise of variance beta_t as in Algorithm 20.2; var = 'posterior' uses sigma_t^2 of (20.17)."""
    import torch
    beta, alpha = schedule()
    gen = torch.Generator().manual_seed(seed)
    n = len(labels)
    c = torch.tensor(np.asarray(labels))
    cu = torch.full((n,), MN_NULL)
    z = torch.randn(n, 196, generator=gen)
    with torch.no_grad():
        for t in range(T_STEPS, 0, -1):
            tt = torch.full((n,), t)
            g = net(z, tt, c)
            if lam != 1.0:
                g = lam * g + (1 - lam) * net(z, tt, cu)
            b, a = beta[t - 1], alpha[t - 1]
            z = (z - b / math.sqrt(1 - a) * g) / math.sqrt(1 - b)
            if t > 1:
                v = b if var == "beta" else b * (1 - alpha[t - 2]) / (1 - a)
                z = z + math.sqrt(v) * torch.randn(z.shape, generator=gen)
            if project is not None:
                z = project(z, t - 1, gen)
    return z.numpy().reshape(-1, 14, 14)


def tile(imgs, ncol, pad=1, val=-1.0):
    """Arrange images (n, h, w) in a grid with ncol columns."""
    n, h, w = imgs.shape
    nrow = int(math.ceil(n / ncol))
    out = np.full((nrow * (h + pad) + pad, ncol * (w + pad) + pad), val)
    for i in range(n):
        r, c = divmod(i, ncol)
        out[pad + r * (h + pad):pad + r * (h + pad) + h, pad + c * (w + pad):pad + c * (w + pad) + w] = imgs[i]
    return out


def _noised_known(x_known, t, gen):
    """sqrt(alpha_t) x + sqrt(1 - alpha_t) eps (t = 0 returns x): the known part brought to noise level t."""
    import torch
    if t == 0:
        return x_known
    a = schedule()[1][t - 1]
    return math.sqrt(a) * x_known + math.sqrt(1 - a) * torch.randn(x_known.shape, generator=gen)


def down2(z):
    """2 x 2 average pooling of 14 x 14 images stored as rows of 196 (torch)."""
    return z.reshape(-1, 7, 2, 7, 2).mean((2, 4))


def up2(lo):
    return lo.repeat_interleave(2, 1).repeat_interleave(2, 2).reshape(-1, 196)


def mnist_superres(net, x_hi, n_samples=3, seed=0):
    """Super-resolution of the 7 x 7 average-pooled image of x_hi by iterative low-pass replacement (ILVR,
    Choi et al. 2021): after each step the 7 x 7 average of z_{t-1} is replaced by that of the noised low-res input."""
    import torch
    xk = torch.tensor(np.repeat(x_hi.reshape(1, 196), n_samples, 0), dtype=torch.float32)

    def project(z, t, gen):
        ref = _noised_known(xk, t, gen)
        return z - up2(down2(z)) + up2(down2(ref))
    return mnist_sample(net, [MN_NULL] * n_samples, seed=seed, project=project)


def mnist_inpaint(net, x, mask, n_samples=3, seed=0):
    """Inpainting by replacement: after each step the known pixels (mask = 1) are reset to the noised original."""
    import torch
    xk = torch.tensor(np.repeat(x.reshape(1, 196), n_samples, 0), dtype=torch.float32)
    m = torch.tensor(mask.reshape(1, 196), dtype=torch.float32)

    def project(z, t, gen):
        return m * _noised_known(xk, t, gen) + (1 - m) * z
    return mnist_sample(net, [MN_NULL] * n_samples, seed=seed, project=project)


def fig_20_8(out_dir=None):
    """Super-resolution, reproduced at small scale: 7 x 7 inputs, three 14 x 14 outputs each, and the original."""
    net = mnist_model()
    X, y = mnist14(False)
    picks = [np.where(y == d)[0][1] for d in (2, 4, 7)]
    fig, axes = plt.subplots(len(picks), 5, figsize=(6.4, 1.45 * len(picks) + 0.3))
    for r, i in enumerate(picks):
        lo = X[i].reshape(7, 2, 7, 2).mean((1, 3))
        outs = mnist_superres(net, X[i], 3, seed=r)
        panels = [lo, outs[0], outs[1], outs[2], X[i].reshape(14, 14)]
        for c_, (ax, im) in enumerate(zip(axes[r], panels)):
            ax.imshow(im, cmap="gray", vmin=-1, vmax=1)
            ax.set_xticks([])
            ax.set_yticks([])
            if r == 0:
                ax.set_title(["input 7$\\times$7", "output 1", "output 2", "output 3", "original"][c_], fontsize=9)
    fig.tight_layout(h_pad=0.4, w_pad=0.3)
    return savefig(fig, CH, "fig20-8", out_dir)


def fig_20_9(out_dir=None):
    """Inpainting, reproduced at small scale: the original, the masked image, and three completions."""
    net = mnist_model()
    X, y = mnist14(False)
    picks = [np.where(y == d)[0][2] for d in (0, 5, 9)]
    masks = []
    m1 = np.ones((14, 14)); m1[4:10, 4:10] = 0
    m2 = np.ones((14, 14)); m2[7:, :] = 0
    m3 = np.ones((14, 14)); m3[:, :7] = 0
    masks = [m1, m2, m3]
    fig, axes = plt.subplots(len(picks), 5, figsize=(6.4, 1.45 * len(picks) + 0.3))
    for r, (i, mk) in enumerate(zip(picks, masks)):
        outs = mnist_inpaint(net, X[i], mk, 3, seed=10 + r)
        masked = np.where(mk > 0, X[i].reshape(14, 14), np.nan)
        panels = [X[i].reshape(14, 14), masked, outs[0], outs[1], outs[2]]
        for c_, (ax, im) in enumerate(zip(axes[r], panels)):
            ax.set_facecolor("#c0392b")
            ax.imshow(im, cmap="gray", vmin=-1, vmax=1)
            ax.set_xticks([])
            ax.set_yticks([])
            if r == 0:
                ax.set_title(["original", "masked", "completion 1", "completion 2", "completion 3"][c_], fontsize=9)
    fig.tight_layout(h_pad=0.4, w_pad=0.3)
    return savefig(fig, CH, "fig20-9", out_dir)


def fig_data(out_dir=None):
    """Data file for diffusion-sampling-demo.html and diffusion-guidance-demo.html (no figure)."""
    export_denoiser_json()


FIGURES = {"20.1": fig_20_1, "20.3": fig_20_3, "20.4": fig_20_4, "20.5": fig_20_5, "20.6": fig_20_6,
           "20.7": fig_20_7, "20.8": fig_20_8, "20.9": fig_20_9,
           "20.S1": fig_20_s1, "20.S2": fig_20_s2, "20.S3": fig_20_s3, "20.S4": fig_20_s4, "20.S5": fig_20_s5,
           "20.S6": fig_20_s6, "20.S7": fig_20_s7, "20.S8": fig_20_s8, "data": fig_data}


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