package pdf

import "core:mem"

// Image XObjects and inline images (ISO 32000-2, 8.9).
//
// An Image is the image dictionary read once -- dimensions, bit depth, colour
// space, /Decode and the three masking mechanisms -- with its samples left
// undecoded. `image_decode` turns it into pixels the first time somebody
// actually paints it, and caches the result.
//
// WHAT COMES OUT
//
//   * An ordinary image decodes to STRAIGHT-alpha RGBA8 (`Bitmap.n == 4`).
//     Straight, not premultiplied, because that is what `blend_span_rgba8`
//     documents itself as taking and what a caller uploading a texture wants.
//   * An /ImageMask decodes to a single-channel coverage plane
//     (`Bitmap.n == 1`), 255 where the stencil paints and 0 where it does not.
//     There is no colour in it: the device paints it in the fill colour.
//
// THE PIPELINE, and where each step's classic bug lives
//
//   1. `stream_image_data` walks the byte filters and stops at the image
//      filter, so a JPEG is decoded straight to pixels here instead of through
//      an intermediate byte buffer.
//   2. Samples are unpacked MSB-first at 1, 2, 4, 8 or 16 bits per component,
//      with each ROW padded out to a whole byte. Forgetting the row padding at
//      a width that is not a multiple of 8/bpc shears the image diagonally.
//   3. /Decode maps each raw sample onto the colour space's component range.
//      Indexed and Lab have defaults that are not 0..1, which is the usual
//      source of an image that comes out inverted or wildly coloured;
//      `colorspace_default_decode` knows them.
//   4. Alpha comes from /SMask, from a stencil /Mask, or from a colour-key
//      /Mask array. A colour-key range is in SOURCE SAMPLE values, so it is
//      compared before /Decode is applied, not after.
//
// EVERY FAILURE DEGRADES. A stream that will not decode, a JPEG 2000 or JBIG2
// codestream this library does not implement, an /SMask that is itself broken:
// each of those yields a fully transparent image of the right size and a
// Repair on the Document. `image_decode` returns an Error only when the caller
// passed something nil.

// ---------------------------------------------------------------------------
// Limits
//
// Every one of these bounds a quantity that came out of the file.
// ---------------------------------------------------------------------------

// The widest or tallest image that will be decoded. A 600 dpi scan of a sheet
// of A0 is about 20000 pixels on its long side; 65536 is far beyond any of
// them and keeps `width * height` well inside an int on every target.
@(private)
MAX_IMAGE_DIM :: 1 << 16
// Total pixels in one decoded image: 64 megapixels, which is 256 MiB at RGBA8.
// Deliberately tighter than MAX_BITMAP_PIXELS, which bounds the page raster --
// a page can legitimately be huge, whereas an image that claims to be is a
// fuzzer or a corrupt /Width.
@(private)
MAX_IMAGE_PIXELS :: 1 << 26
// Depth of /SMask and /Mask chains followed. A mask never legitimately has a
// mask of its own; this only stops a file whose /SMask points back at the
// image that owns it from recursing.
@(private)
MAX_IMAGE_NESTING :: 4

// How much bigger an image's samples may be than the stream bytes they come
// out of, and the size below which the ratio is not looked at at all.
//
// Nothing in ISO 32000-2 relates /Width and /Height to the sample data, so a
// hundred-byte dictionary can ask for a quarter of a gigabyte of pixels and a
// full colour conversion over every one of them; the rule this library is
// written to is that a length out of a file is checked against the file before
// it is allocated for. This is that check, and it is deliberately loose,
// because streams really do decompress enormously: a blank page under CCITT G4
// codes a whole row in a handful of bits, and a flat image under Flate with a
// predictor is a run of zeroes, so both reach a thousandfold and neither is a
// broken file. What is left over is the shape that has no honest reading -- a
// few hundred bytes claiming tens of megabytes of samples.
//
// The floor keeps every ordinary image out of the test entirely: under a
// mebibyte of samples the decoded bitmap is at most 4 MiB whatever the stream
// says, which is not worth refusing a picture over.
@(private)
MAX_IMAGE_EXPANSION :: 4096
@(private)
IMAGE_EXPANSION_FLOOR :: 1 << 20

// IMAGE_CACHE_BUDGET is the total size of decoded pixels one Document holds.
//
// 64 MiB is a handful of full-page photographs, which is what a reader
// scrolling a brochure re-paints; a 300-page catalogue that would otherwise
// end up holding every photograph at once instead evicts the pages it has
// scrolled past. Eviction is least-recently-used and never touches the image
// currently being decoded.
@(private)
IMAGE_CACHE_BUDGET :: 64 << 20

// ---------------------------------------------------------------------------
// The image
// ---------------------------------------------------------------------------

Image :: struct {
    width:  int,
    height: int,
    // Bits per component: 1, 2, 4, 8 or 16. Always 1 when is_mask.
    bpc:    int,
    cs:     ^Colorspace,

    // An /ImageMask is a 1-bit stencil painted in the current fill colour
    // rather than an image with colours of its own.
    is_mask:     bool,
    interpolate: bool,
    // /Decode, 2*cs.n entries, or empty for the colour space's default.
    decode:      []f64,

    // /SMask: a greyscale image supplying alpha.
    smask: ^Image,
    // /Mask as a stencil image.
    mask:  ^Image,
    // /Mask as a colour-key range: 2*cs.n integers in source sample values.
    color_key:     []int,
    has_color_key: bool,

    // /Matte, on an /SMask whose owner's colour was pre-blended against it
    // (ISO 32000-2, 11.6.5.3). Components are in the OWNER's colour space, so
    // it is converted when the owner decodes, not when the mask loads.
    matte:     []f64,
    has_matte: bool,

    // The stream the samples come from, decoded lazily.
    stream: ^Stream,
    // True for a BI/ID/EI image, which is not shared and so is not entered in
    // the Document's by-stream table.
    is_inline: bool,

    // Cache filled in by `image_decode`: straight-alpha RGBA8, or a 1-byte
    // coverage plane when is_mask.
    rgba:    Bitmap,
    decoded: bool,
    failed:  bool,
    // Cache clock reading at the last `image_decode`, for LRU eviction.
    last_use: u64,
}

// image_size is the decoded pixel size. It is not the size the image is drawn
// at: an image always covers the unit square of the current transform.
image_size :: proc(img: ^Image) -> (w, h: int) {
    if img == nil {
        return 0, 0
    }
    return img.width, img.height
}

// ---------------------------------------------------------------------------
// The decoded-image cache
//
// Two caches, with different lifetimes on purpose:
//
//   * `by_stream` maps an image XObject's stream to its Image, so a logo drawn
//     on all 300 pages is parsed once. Images are arena memory and cost a few
//     hundred bytes each, so nothing is ever evicted from it. The key carries
//     the ROLE as well as the stream, because a stream a /Mask points at is
//     read as a 1-bit stencil while the same stream drawn by `Do` is read as
//     a picture: two Images, and one cannot be both.
//   * `live` holds the Images whose pixels are currently decoded. Those are
//     megabytes each and come from a real allocator, so they are evicted
//     least-recently-used once `bytes` exceeds `budget`.
// ---------------------------------------------------------------------------

// Img_Key is a stream and the way it is being read. `stencil` is true for the
// second reading a /Mask entry forces on a stream that is not an /ImageMask.
@(private)
Img_Key :: struct {
    stream:  uintptr,
    stencil: bool,
}

@(private)
Image_Cache :: struct {
    by_stream: map[Img_Key]^Image,
    live:      [dynamic]^Image,
    bytes:     int,
    // Zero means IMAGE_CACHE_BUDGET; a caller (or a test) may set it lower.
    budget:    int,
    clock:     u64,
}

// img_pixel_allocator is where decoded pixels come from. NOT the Document
// arena: the arena cannot free an individual allocation, so an image cached in
// it could never be evicted and the budget would be a fiction. `close` calls
// `image_cache_release`, which is what keeps this leak-free.
@(private)
img_pixel_allocator :: proc(doc: ^Document) -> mem.Allocator {
    if doc != nil && doc.backing.procedure != nil {
        return doc.backing
    }
    return context.allocator
}

// image_cache_release frees every decoded image. Called by `close`.
@(private)
image_cache_release :: proc(doc: ^Document) {
    if doc == nil {
        return
    }
    c := &doc.img_cache
    for img in c.live {
        if img == nil {
            continue
        }
        bitmap_destroy(&img.rgba)
        img.decoded = false
    }
    delete(c.live)
    c.live = nil
    c.bytes = 0
}

@(private)
img_cache_touch :: proc(doc: ^Document, img: ^Image) {
    if doc == nil || img == nil {
        return
    }
    doc.img_cache.clock += 1
    img.last_use = doc.img_cache.clock
}

@(private)
img_cache_admit :: proc(doc: ^Document, img: ^Image) {
    c := &doc.img_cache
    if c.budget <= 0 {
        c.budget = IMAGE_CACHE_BUDGET
    }
    if c.live == nil {
        c.live = make([dynamic]^Image, 0, 16, img_pixel_allocator(doc))
    }
    append(&c.live, img)
    c.bytes += len(img.rgba.pixels)
    img_cache_touch(doc, img)
    img_cache_evict(doc, img)
}

// img_cache_evict drops least-recently-used images until the budget is met.
// `keep` is never evicted, which is what makes the Bitmap `image_decode` just
// returned safe to use: the pointer stays valid until the next decode of a
// *different* image on this Document.
@(private)
img_cache_evict :: proc(doc: ^Document, keep: ^Image) {
    c := &doc.img_cache
    for c.bytes > c.budget {
        victim := -1
        oldest := max(u64)
        for img, i in c.live {
            if img == nil || img == keep {
                continue
            }
            if img.last_use <= oldest {
                oldest = img.last_use
                victim = i
            }
        }
        if victim < 0 {
            // Nothing left but `keep`. A single image larger than the whole
            // budget is held until the next decode rather than thrown away
            // before its caller has drawn it.
            return
        }
        v := c.live[victim]
        c.bytes -= len(v.rgba.pixels)
        bitmap_destroy(&v.rgba)
        v.decoded = false
        v.failed = false
        unordered_remove(&c.live, victim)
    }
}

// ---------------------------------------------------------------------------
// Loading
// ---------------------------------------------------------------------------

// image_load reads an image XObject's dictionary.
//
// The Image is owned by the Document and must not be freed. The same stream
// read the same way always yields the same Image, so a picture placed on every
// page is read once and -- until the cache evicts it -- decoded once. A stream
// that is also named by some other image's /Mask has a second Image for that
// reading, because a stencil and a picture are not the same pixels.
image_load :: proc(doc: ^Document, stm: ^Stream, res: ^Dict) -> (^Image, Error) {
    return img_load(doc, stm, res, 0)
}

// image_load_inline reads a BI/ID/EI inline image (ISO 32000-2, 8.9.7).
//
// `d` is the dictionary between BI and ID, which uses the abbreviated keys
// /W /H /BPC /CS /F /D /DP /IM, and `data` is the still-encoded bytes between
// ID and EI. `data` is copied, so it need not outlive the call. `res` is the
// page's /Resources, where a colour space name that is not one of the
// abbreviations is looked up.
//
// The Image is owned by the Document. Inline images are not shared, so unlike
// an XObject they are not cached by stream: each BI builds a new one.
image_load_inline :: proc(doc: ^Document, d: ^Dict, data: []byte, res: ^Dict) -> (img: ^Image, err: Error) {
    if doc == nil || d == nil {
        return nil, .Invalid_Argument
    }
    // Copied rather than borrowed: the caller's buffer is a window onto a
    // content stream that a per-page arena may reset, and an inline image is
    // required to be small (8.9.7 recommends 4 KiB), so the copy is cheap.
    payload: []byte
    if len(data) > 0 {
        buf, aerr := make([]byte, len(data), doc.allocator)
        if aerr != nil {
            return nil, .Out_Of_Memory
        }
        copy(buf, data)
        payload = buf
    }
    stm := new_stream(d, payload, doc.allocator)
    img = img_build(doc, stm, res, 0) or_return
    img.is_inline = true
    return img, .None
}

@(private)
img_load :: proc(doc: ^Document, stm: ^Stream, res: ^Dict, depth: int) -> (img: ^Image, err: Error) {
    if doc == nil || stm == nil {
        return nil, .Invalid_Argument
    }
    if depth > MAX_IMAGE_NESTING {
        add_repair(doc, .Recursion_Limit_Hit, 0, stm.ref)
        return nil, .Recursion_Limit
    }

    key := Img_Key{uintptr(rawptr(stm)), false}
    if cached, ok := doc.img_cache.by_stream[key]; ok {
        return cached, .None
    }

    img = img_build(doc, stm, res, depth) or_return
    img_cache_put(doc, key, img)
    return img, .None
}

@(private)
img_cache_put :: proc(doc: ^Document, key: Img_Key, img: ^Image) {
    if doc.img_cache.by_stream == nil {
        doc.img_cache.by_stream = make(map[Img_Key]^Image, 16, doc.allocator)
    }
    doc.img_cache.by_stream[key] = img
}

// img_load_stencil reads a stream the way a /Mask entry means it: as a 1-bit
// stencil. 8.9.6.4 requires that stream to be an /ImageMask, and when it is
// this is exactly img_load.
//
// Producers that write a 1-bit (or 8-bit) /DeviceGray image instead mean the
// same thing -- the sample values are identical -- so it is read as a stencil
// anyway. What it must NOT do is write that decision back onto the Image the
// by-stream cache holds: that Image is what every other reference to the same
// stream gets, including a plain `Do` of it as a picture, and setting is_mask
// on it turns the picture into a one-channel stencil too. So the stencil
// reading is a second Image over the same stream, under its own key.
@(private)
img_load_stencil :: proc(doc: ^Document, stm: ^Stream, res: ^Dict, depth: int) ->
                   (img: ^Image, err: Error) {
    m := img_load(doc, stm, res, depth) or_return
    if m.is_mask {
        return m, .None
    }
    key := Img_Key{uintptr(rawptr(stm)), true}
    if cached, ok := doc.img_cache.by_stream[key]; ok {
        return cached, .None
    }
    // Recorded once, where the second reading is built, and not again for
    // every image that goes on to reference the same stencil.
    add_repair(doc, .Bad_Resource, 0, stm.ref)
    s := img_build(doc, stm, res, depth) or_return
    s.is_mask = true
    s.bpc = 1
    img_cache_put(doc, key, s)
    return s, .None
}

// img_samples_are_plausible reports whether a stream could hold the samples the
// dictionary claims. See MAX_IMAGE_EXPANSION. `n` and `bpc` are the component
// count and depth the samples will be read at; understating them only makes
// the test more permissive, which is the safe direction for a colour space
// that would not load.
@(private)
img_samples_are_plausible :: proc(stm: ^Stream, w, h, n, bpc: int) -> bool {
    row := (w * max(n, 1) * max(bpc, 1) + 7) / 8
    if row <= 0 || h <= 0 {
        return false
    }
    need := row * h
    if need <= IMAGE_EXPANSION_FLOOR {
        return true
    }
    return need / MAX_IMAGE_EXPANSION <= len(stm.raw)
}

@(private)
img_build :: proc(doc: ^Document, stm: ^Stream, res: ^Dict, depth: int) -> (^Image, Error) {
    d := stm.dict
    if d == nil {
        return nil, .Bad_Image
    }

    w := img_dim(doc, d, "Width", "W")
    h := img_dim(doc, d, "Height", "H")
    if w <= 0 || h <= 0 || w > MAX_IMAGE_DIM || h > MAX_IMAGE_DIM || w > MAX_IMAGE_PIXELS / h {
        // Nothing here can be rendered and nothing can be guessed: an image
        // with no dimensions is not a repairable image, it is not an image.
        add_repair(doc, .Bad_Resource, 0, stm.ref)
        return nil, .Bad_Image
    }

    img := new(Image, doc.allocator)
    img.width = w
    img.height = h
    img.stream = stm
    img.interpolate = img_flag(doc, d, "Interpolate", "I", false)
    img.is_mask = img_flag(doc, d, "ImageMask", "IM", false)

    if img.is_mask {
        // 8.9.6.2: a stencil mask has no colour space and /BitsPerComponent,
        // if present at all, shall be 1. Files write 8 anyway; the format is
        // unambiguous, so the dictionary loses.
        img.bpc = 1
        if !img_samples_are_plausible(stm, w, h, 1, 1) {
            add_repair(doc, .Bad_Resource, 0, stm.ref)
            return nil, .Bad_Image
        }
        img.decode = img_decode_array(doc, d, 1, stm.ref)
        return img, .None
    }

    img.bpc = int(img_number(doc, d, "BitsPerComponent", "BPC", 8))
    switch img.bpc {
    case 1, 2, 4, 8, 16:
    case:
        // A DCT or JPX image often omits /BitsPerComponent entirely, and 8 is
        // the only depth either can hand back here.
        img.bpc = 8
    }

    cs, cs_err := colorspace_load(doc, dict_get_alt(doc, d, "ColorSpace", "CS"), res)
    if cs_err != .None || cs == nil {
        // Left nil deliberately. A DCTDecode image whose /ColorSpace is broken
        // still says how many components it has in its own frame header, and
        // `img_fetch` picks the device space of that width; anything else
        // falls back to the width implied by the sample count.
        if dict_has(d, "ColorSpace") || dict_has(d, "CS") {
            add_repair(doc, .Bad_Resource, 0, stm.ref)
        }
    } else {
        img.cs = cs
    }

    n := img.cs != nil ? min(img.cs.n, MAX_COLOR_COMPONENTS) : 0
    if !img_samples_are_plausible(stm, w, h, n, img.bpc) {
        add_repair(doc, .Bad_Resource, 0, stm.ref)
        return nil, .Bad_Image
    }
    img.decode = img_decode_array(doc, d, n, stm.ref)

    img_load_smask(doc, img, d, res, depth)
    img_load_mask(doc, img, d, res, depth, n)
    return img, .None
}

@(private)
img_load_smask :: proc(doc: ^Document, img: ^Image, d: ^Dict, res: ^Dict, depth: int) {
    sm := dict_stream(doc, d, "SMask")
    if sm == nil {
        return
    }
    m, err := img_load(doc, sm, res, depth + 1)
    if err != .None || m == nil || m == img {
        add_repair(doc, .Bad_Resource, 0, img.stream.ref)
        return
    }
    // /Matte lives in the soft mask's dictionary but its components are in the
    // *owner's* colour space (11.6.5.3), which is why it is read here.
    if mt := dict_array(doc, sm.dict, "Matte"); mt != nil && img.cs != nil {
        want := min(img.cs.n, MAX_COLOR_COMPONENTS)
        if array_len(mt) >= want && want > 0 {
            vals := array_numbers(doc, mt, doc.allocator)
            if len(vals) >= want && img_all_finite(vals[:want]) {
                m.matte = vals[:want]
                m.has_matte = true
            }
        }
    }
    img.smask = m
}

@(private)
img_load_mask :: proc(doc: ^Document, img: ^Image, d: ^Dict, res: ^Dict, depth, n: int) {
    o := dict_get(doc, d, "Mask")
    #partial switch v in o {
    case ^Stream:
        m, err := img_load_stencil(doc, v, res, depth + 1)
        if err != .None || m == nil || m == img {
            add_repair(doc, .Bad_Resource, 0, img.stream.ref)
            return
        }
        img.mask = m

    case ^Array:
        // 2*n integers, and they are SOURCE SAMPLE values -- indices into the
        // raw sample range, not colours. Comparing them after /Decode has been
        // applied is the classic way to get colour-key masking wrong.
        want := 2 * n
        if want <= 0 || array_len(v) < want {
            add_repair(doc, .Bad_Resource, 0, img.stream.ref)
            return
        }
        keys, aerr := make([]int, want, doc.allocator)
        if aerr != nil {
            return
        }
        maxv := (int(1) << uint(clamp(img.bpc, 1, 16))) - 1
        for i in 0 ..< want {
            keys[i] = clamp(int(array_int(doc, v, i, 0)), 0, maxv)
        }
        img.color_key = keys
        img.has_color_key = true
    }
}

// img_decode_array reads /Decode (or its inline /D spelling). A wrong-length
// or non-finite array is dropped rather than honoured: the colour space's
// default is always a sane array, and half an applied /Decode is not.
@(private)
img_decode_array :: proc(doc: ^Document, d: ^Dict, n: int, ref: Ref) -> []f64 {
    a, is_array := to_array(dict_get_alt(doc, d, "Decode", "D"))
    if !is_array || a == nil {
        return nil
    }
    if n <= 0 || array_len(a) < 2 * n {
        add_repair(doc, .Bad_Resource, 0, ref)
        return nil
    }
    vals := array_numbers(doc, a, doc.allocator)
    if len(vals) < 2 * n || !img_all_finite(vals[:2 * n]) {
        add_repair(doc, .Bad_Resource, 0, ref)
        return nil
    }
    return vals[:2 * n]
}

@(private)
img_all_finite :: proc(vals: []f64) -> bool {
    for v in vals {
        if !is_finite(v) {
            return false
        }
    }
    return true
}

// img_dim reads /Width or /Height, which real files write as reals often
// enough ("/Width 612.0") that a plain integer read would reject them.
@(private)
img_dim :: proc(doc: ^Document, d: ^Dict, key, alt: string) -> int {
    return int(img_number(doc, d, key, alt, 0))
}

@(private)
img_number :: proc(doc: ^Document, d: ^Dict, key, alt: string, def: f64) -> f64 {
    v, ok := to_number(dict_get_alt(doc, d, key, alt))
    if !ok || !is_finite(v) {
        return def
    }
    // Clamped before it is ever narrowed to an int: converting a f64 far
    // outside the integer range is undefined, and /Width 1e300 is exactly the
    // kind of thing a fuzzer writes.
    return clamp(v, -1e9, 1e9)
}

@(private)
img_flag :: proc(doc: ^Document, d: ^Dict, key, alt: string, def: bool) -> bool {
    if v, ok := to_bool(dict_get_alt(doc, d, key, alt)); ok {
        return v
    }
    return def
}

// ---------------------------------------------------------------------------
// Samples
// ---------------------------------------------------------------------------

// Image_Samples is a rectangle of unpacked-but-not-yet-interpreted samples.
// `row_bytes` is carried separately because it is not always
// `(w*n*bpc + 7)/8`: CCITTFaxDecode lays its rows out at /Columns, which is
// allowed to disagree with /Width.
@(private)
Image_Samples :: struct {
    data:      []byte,
    w, h:      int,
    n:         int,
    bpc:       int,
    row_bytes: int,
}

// Image_Data is everything one decode needs, plus the scratch buffers it must
// give back. Release it with `img_release`.
@(private)
Image_Data :: struct {
    s:      Image_Samples,
    cs:     ^Colorspace,
    // Effective /Decode: the dictionary's if it was usable, the colour space's
    // default otherwise. Always 2*s.n entries.
    dec:    []f64,
    raw:    []byte,   // from stream_image_data
    conv:   []byte,   // from jpeg_decode or ccitt_decode
    decbuf: []f64,    // from colorspace_default_decode
}

@(private)
img_release :: proc(id: ^Image_Data, scratch: mem.Allocator) {
    delete(id.raw, scratch)
    delete(id.conv, scratch)
    delete(id.decbuf, scratch)
    id^ = {}
}

@(private)
img_row :: proc(s: Image_Samples, y: int) -> []byte {
    if s.row_bytes <= 0 || y < 0 {
        return nil
    }
    start := y * s.row_bytes
    if start >= len(s.data) {
        return nil
    }
    return s.data[start:min(start + s.row_bytes, len(s.data))]
}

// img_sample reads component `index` of a row, MSB first. A row shorter than
// the image claims reads as zeroes rather than as a fault: a truncated image
// stream is common and must still draw what arrived.
@(private)
img_sample :: proc(row: []byte, index, bpc: int) -> u32 {
    switch bpc {
    case 8:
        return index < len(row) ? u32(row[index]) : 0
    case 16:
        i := index * 2
        hi := i < len(row) ? u32(row[i]) : 0
        lo := i + 1 < len(row) ? u32(row[i + 1]) : 0
        return hi << 8 | lo
    case 1, 2, 4:
        bit := index * bpc
        byi := bit >> 3
        if byi >= len(row) {
            return 0
        }
        shift := uint(8 - bpc - (bit & 7))
        return (u32(row[byi]) >> shift) & u32((1 << uint(bpc)) - 1)
    }
    return 0
}

// img_fetch runs the filter chain and hands back samples ready to unpack.
@(private)
img_fetch :: proc(doc: ^Document, img: ^Image, scratch: mem.Allocator) -> (id: Image_Data, err: Error) {
    data, fname, parms, derr := stream_image_data(doc, img.stream, scratch)
    if derr != .None {
        delete(data, scratch)
        add_repair(doc, .Bad_Filter_Data, 0, img.stream.ref)
        return {}, derr
    }
    id.raw = data

    switch fname {
    case "":
        img_fetch_plain(doc, img, &id)
    case "DCTDecode":
        img_fetch_dct(doc, img, &id, scratch) or_return
    case "CCITTFaxDecode":
        img_fetch_ccitt(doc, img, &id, parms, scratch) or_return
    case "JPXDecode", "JBIG2Decode":
        // Neither codec is implemented. This is not an error that may kill a
        // page: the caller turns it into a transparent placeholder.
        return id, .Unsupported_Image
    case:
        return id, .Unsupported_Image
    }

    id.dec = img_effective_decode(img, id.cs, id.s.bpc, id.s.n, scratch, &id.decbuf)
    return id, .None
}

@(private)
img_fetch_plain :: proc(doc: ^Document, img: ^Image, id: ^Image_Data) {
    n := img.is_mask ? 1 : img_component_count(doc, img, len(id.raw))
    bpc := img.is_mask ? 1 : img.bpc
    id.cs = img.is_mask ? nil : img_effective_cs(img, n)
    id.s = Image_Samples{
        data      = id.raw,
        w         = img.width,
        h         = img.height,
        n         = n,
        bpc       = bpc,
        row_bytes = (img.width * n * bpc + 7) / 8,
    }
}

@(private)
img_fetch_dct :: proc(doc: ^Document, img: ^Image, id: ^Image_Data, scratch: mem.Allocator) -> Error {
    j, jerr := jpeg_decode(id.raw, scratch)
    if jerr != .None {
        add_repair(doc, .Bad_Filter_Data, 0, img.stream.ref)
        return jerr
    }
    id.conv = j.data
    if j.width <= 0 || j.height <= 0 || j.components <= 0 ||
       j.width > MAX_IMAGE_DIM || j.height > MAX_IMAGE_DIM ||
       j.width > MAX_IMAGE_PIXELS / j.height {
        return .Bad_Image
    }
    if j.width != img.width || j.height != img.height {
        // The frame header is the authority: it is what the samples are laid
        // out to. An image always covers the unit square of the CTM, so taking
        // the JPEG's size changes the resolution drawn, never the placement.
        add_repair(doc, .Bad_Resource, 0, img.stream.ref)
        img.width = j.width
        img.height = j.height
    }

    // The Adobe APP14 transform (`j.adobe_transform`) has already been undone
    // by the decoder: a 3-component YCbCr scan arrives as RGB and a
    // 4-component YCCK scan as CMYK. What is deliberately NOT undone there is
    // the sample inversion Adobe applies to the CMYK JPEGs it embeds in PDFs.
    // That inversion is expressed in this dictionary's /Decode array --
    // [1 0 1 0 1 0 1 0] -- and is applied below like any other /Decode.
    // Inverting here as well would double-apply it and turn every photograph
    // into its own negative.
    id.cs = img.cs
    if id.cs == nil || min(id.cs.n, MAX_COLOR_COMPONENTS) != j.components {
        id.cs = colorspace_device_n(j.components)
    }
    id.s = Image_Samples{
        data      = j.data,
        w         = j.width,
        h         = j.height,
        n         = j.components,
        bpc       = 8,
        row_bytes = j.width * j.components,
    }
    return .None
}

@(private)
img_fetch_ccitt :: proc(doc: ^Document, img: ^Image, id: ^Image_Data, parms: ^Dict,
                        scratch: mem.Allocator) -> Error {
    p := filter_ccitt_params(doc, parms)
    if !dict_has(parms, "Columns") {
        // /Columns defaults to 1728 because that is the width of a fax page,
        // but inside a PDF the two are required to agree and a producer that
        // omits it meant /Width. Taking 1728 for a 2544-pixel scan would shear
        // every row.
        p.columns = img.width
    } else if p.columns != ccitt_columns(p) {
        // Present, but not a width `ccitt_decode` will honour as written: it
        // substitutes 1728 for a non-positive /Columns and clamps anything
        // past MAX_CCITT_COLUMNS, and would then lay its rows out at that
        // stride while this side read them back at another. /Width is the only
        // other statement of the width in the file, and using it for both
        // decodes the picture instead of merely agreeing about where the
        // garbage starts.
        add_repair(doc, .Bad_Resource, 0, img.stream.ref)
        p.columns = img.width
    }
    if p.rows <= 0 {
        p.rows = img.height
    }
    if p.columns != img.width {
        add_repair(doc, .Bad_Resource, 0, img.stream.ref)
    }

    out, cerr := ccitt_decode(id.raw, p, scratch)
    if cerr != .None {
        delete(out, scratch)
        add_repair(doc, .Bad_Filter_Data, 0, img.stream.ref)
        return cerr
    }
    id.conv = out

    // ccitt_decode emits exactly the 1-bit sample array an image expects: with
    // /BlackIs1 false (the default) a black pixel is a 0 bit, which DeviceGray
    // maps to 0.0, i.e. black. /BlackIs1 true exchanges the two in the sample
    // data, and it is then the image's /Decode -- not this filter -- that says
    // what the samples mean. So nothing is inverted here.
    // CCITT is bi-level, so there is exactly one component whatever the
    // dictionary's colour space claims.
    id.cs = img.is_mask ? nil : img_effective_cs(img, 1)
    id.s = Image_Samples{
        data      = out,
        w         = img.width,
        h         = img.height,
        n         = 1,
        bpc       = 1,
        // Asked of the filter rather than recomputed: `p.columns` is now a
        // width it honours verbatim, and going through the same procedure it
        // does is what keeps the two from ever drifting apart again.
        row_bytes = ccitt_row_bytes(p),
    }
    return .None
}

// img_effective_cs is the colour space to interpret `n` components in. A
// missing or unloadable /ColorSpace falls back to the device space of that
// width, which is what 8.6.5.5 says an ICCBased with no alternate does and the
// only guess available for an inline image with no /CS at all.
@(private)
img_effective_cs :: proc(img: ^Image, n: int) -> ^Colorspace {
    if img.cs != nil && min(img.cs.n, MAX_COLOR_COMPONENTS) == n {
        return img.cs
    }
    return colorspace_device_n(n)
}

// img_component_count is how many components a row holds. Normally the colour
// space says; when it could not be loaded the sample count is divided by the
// pixel count, which recovers the common "/ColorSpace is an unresolvable
// reference" case exactly.
@(private)
img_component_count :: proc(doc: ^Document, img: ^Image, nbytes: int) -> int {
    if img.cs != nil {
        return max(1, min(img.cs.n, MAX_COLOR_COMPONENTS))
    }
    for n in 1 ..= 4 {
        need := ((img.width * n * img.bpc + 7) / 8) * img.height
        if need == nbytes {
            return n
        }
    }
    return 1
}

// img_effective_decode returns 2*n decode entries: the dictionary's if it had
// the right shape, the colour space's default otherwise. Indexed and Lab are
// exactly why the default cannot be assumed to be [0 1 0 1 ...].
@(private)
img_effective_decode :: proc(img: ^Image, cs: ^Colorspace, bpc, n: int,
                             scratch: mem.Allocator, owned: ^[]f64) -> []f64 {
    if len(img.decode) >= 2 * n && n > 0 {
        return img.decode[:2 * n]
    }
    if img.is_mask || cs == nil {
        // A stencil's one component defaults to [0 1]: sample 0 paints.
        buf, err := make([]f64, 2 * max(n, 1), scratch)
        if err != nil {
            return nil
        }
        for i in 0 ..< max(n, 1) {
            buf[2 * i], buf[2 * i + 1] = 0, 1
        }
        owned^ = buf
        return buf
    }
    d := colorspace_default_decode(cs, bpc, scratch)
    if len(d) < 2 * n {
        delete(d, scratch)
        return nil
    }
    owned^ = d
    return d[:2 * n]
}

// ---------------------------------------------------------------------------
// Decoding to pixels
// ---------------------------------------------------------------------------

// image_decode decodes the image to pixels, caching the result on the Image.
//
// The result is straight-alpha RGBA8, or a one-channel coverage plane when
// `img.is_mask`. It belongs to the Document and must not be freed.
//
// LIFETIME: the pixels stay valid until the next `image_decode` of a
// *different* image on this Document, or until `close`. The cache evicts
// least-recently-used images to stay inside its byte budget, and never evicts
// the one it has just been asked for, so the ordinary
// "decode, draw, decode the next" loop is safe; holding one image's pixels
// across another's decode is not. The pointer itself never dangles -- it is
// into the Image, which lives as long as the Document -- so a caller that
// does hold one too long reads an empty Bitmap rather than freed memory.
//
// An image that cannot be decoded at all -- a broken stream, a JPEG 2000 or
// JBIG2 codestream -- comes back as a fully transparent image of the right
// size with a Repair on the Document. The Error return is for a nil argument.
image_decode :: proc(doc: ^Document, img: ^Image) -> (^Bitmap, Error) {
    if doc == nil || img == nil {
        return nil, .Invalid_Argument
    }
    if img.decoded {
        img_cache_touch(doc, img)
        return &img.rgba, .None
    }

    bmp, err := img_decode_uncached(doc, img)
    if err != .None {
        add_repair(doc, .Bad_Filter_Data, 0, img.stream != nil ? img.stream.ref : Ref{})
        ph, perr := img_placeholder(doc, img)
        if perr != .None {
            return nil, perr
        }
        bmp = ph
        img.failed = true
    }

    img.rgba = bmp
    img.decoded = true
    img_cache_admit(doc, img)
    return &img.rgba, .None
}

// img_placeholder is a fully transparent image (or an empty stencil) of the
// right size, so a page whose picture will not decode still lays out.
@(private)
img_placeholder :: proc(doc: ^Document, img: ^Image) -> (Bitmap, Error) {
    n := img.is_mask ? 1 : 4
    w := clamp(img.width, 1, MAX_IMAGE_DIM)
    h := clamp(img.height, 1, MAX_IMAGE_DIM)
    if w > MAX_IMAGE_PIXELS / h {
        w, h = 1, 1
    }
    return bitmap_make(w, h, n, img_pixel_allocator(doc))
}

@(private)
img_decode_uncached :: proc(doc: ^Document, img: ^Image) -> (bmp: Bitmap, err: Error) {
    scratch := context.allocator
    id, ferr := img_fetch(doc, img, scratch)
    defer img_release(&id, scratch)
    if ferr != .None {
        return {}, ferr
    }
    if id.s.n <= 0 || len(id.dec) < 2 * id.s.n {
        return {}, .Bad_Image
    }
    if img.width <= 0 || img.height <= 0 || img.width > MAX_IMAGE_PIXELS / img.height {
        return {}, .Bad_Image
    }

    if img.is_mask {
        stencil := bitmap_make(img.width, img.height, 1, img_pixel_allocator(doc)) or_return
        img_unpack_stencil(id.s, id.dec, &stencil)
        return stencil, .None
    }

    out := bitmap_make(img.width, img.height, 4, img_pixel_allocator(doc)) or_return
    img_unpack_rgba(id.s, id.cs, id.dec, img.has_color_key ? img.color_key : nil, &out)
    img_apply_alpha(doc, img, &out, scratch)
    return out, .None
}

// img_unpack_stencil fills a one-byte coverage plane: 255 where the stencil
// paints. Sample 0 paints under the default /Decode [0 1]; /Decode [1 0]
// exchanges the two (8.9.6.2).
@(private)
img_unpack_stencil :: proc(s: Image_Samples, dec: []f64, out: ^Bitmap) {
    d0 := len(dec) >= 2 ? dec[0] : 0
    d1 := len(dec) >= 2 ? dec[1] : 1
    for y in 0 ..< out.height {
        row := img_row(s, y)
        dst := bitmap_row(out, y)
        if dst == nil {
            continue
        }
        for x in 0 ..< min(out.width, len(dst)) {
            v := img_sample(row, x, 1) == 0 ? d0 : d1
            dst[x] = v < 0.5 ? 255 : 0
        }
    }
}

// img_cs_is_identity_rgb reports whether the space maps a three-component
// value straight onto RGB. That is true of /DeviceRGB and of most of the
// ICCBased spaces that 24% of the corpus uses, which render through a
// DeviceRGB alternate. It is answered by PROBING the space rather than by
// pattern-matching its kind, so the fast path below is taken only where it
// provably agrees with the general one.
@(private)
img_cs_is_identity_rgb :: proc(cs: ^Colorspace) -> bool {
    if cs == nil || min(cs.n, MAX_COLOR_COMPONENTS) != 3 {
        return false
    }
    if cs.kind == .Device_RGB {
        return true
    }
    #partial switch cs.kind {
    case .Cal_RGB, .ICC_Based:
    case:
        return false
    }
    probes := [?][3]f64{
        {0, 0, 0}, {1, 1, 1}, {1, 0, 0}, {0, 1, 0}, {0, 0, 1},
        {0.25, 0.5, 0.75}, {0.5, 0.2, 0.9},
    }
    for p in probes {
        got := colorspace_to_rgb(cs, color_make(p[0], p[1], p[2]))
        for i in 0 ..< 3 {
            if abs(got[i] - p[i]) > 1.0 / 512.0 {
                return false
            }
        }
    }
    return true
}

@(private)
img_is_default_decode :: proc(dec: []f64, n: int) -> bool {
    if len(dec) < 2 * n {
        return false
    }
    for i in 0 ..< n {
        if dec[2 * i] != 0 || dec[2 * i + 1] != 1 {
            return false
        }
    }
    return true
}

@(private)
img_unpack_rgba :: proc(s: Image_Samples, cs: ^Colorspace, dec: []f64, color_key: []int,
                        out: ^Bitmap) {
    n := s.n
    if n <= 0 || n > MAX_COLOR_COMPONENTS {
        return
    }
    bpc := s.bpc
    maxv := f64((int(1) << uint(clamp(bpc, 1, 16))) - 1)
    if maxv <= 0 {
        maxv = 1
    }

    // One component and at most 8 bits: 256 entries cover every possible
    // sample, so the whole colour conversion -- an Indexed palette lookup, a
    // Separation tint transform, a CalGray gamma -- is done at most 256 times
    // instead of once per pixel.
    lut: [256][3]u8
    use_lut := n == 1 && bpc <= 8
    if use_lut {
        comp: Color
        comp.n = 1
        for i in 0 ..< (1 << uint(bpc)) {
            comp.v[0] = dec[0] + f64(i) * (dec[1] - dec[0]) / maxv
            f := colorspace_to_rgb(cs, comp)
            lut[i] = {blend_quantize(f[0]), blend_quantize(f[1]), blend_quantize(f[2])}
        }
    }
    direct_rgb := n == 3 && bpc == 8 && img_is_default_decode(dec, 3) && img_cs_is_identity_rgb(cs)

    ck := len(color_key) >= 2 * n ? color_key : nil

    comp: Color
    comp.n = min(n, MAX_COLOR_COMPONENTS)
    raws: [MAX_COLOR_COMPONENTS]u32

    // A row the sample data does not reach at all reads as zeroes, so it is
    // one colour from end to end -- and a declared /Height the stream comes
    // nowhere near is the ordinary shape both of a truncated scan and of a
    // dictionary written to make a reader work. Computing that colour once
    // turns those rows into a fill instead of a colour conversion per pixel,
    // which for a 32-colorant /DeviceN at 16 bits is the difference between a
    // memory-speed loop and a minute of arithmetic. The bytes written are the
    // same ones the general path would have written.
    pad: [4]u8
    {
        rgb: [3]u8
        switch {
        case use_lut:
            rgb = lut[0]
        case direct_rgb:
        case:
            for c in 0 ..< comp.n {
                // lo + 0 * (hi - lo) / maxv.
                comp.v[c] = dec[2 * c]
            }
            f := colorspace_to_rgb(cs, comp)
            rgb = {blend_quantize(f[0]), blend_quantize(f[1]), blend_quantize(f[2])}
        }
        alpha: u8 = 255
        if ck != nil {
            masked := true
            for c in 0 ..< n {
                if ck[2 * c] > 0 || ck[2 * c + 1] < 0 {
                    masked = false
                    break
                }
            }
            if masked {
                alpha = 0
            }
        }
        pad = {rgb[0], rgb[1], rgb[2], alpha}
    }

    for y in 0 ..< out.height {
        row := img_row(s, y)
        dst := bitmap_row(out, y)
        if dst == nil {
            continue
        }
        if row == nil {
            for x in 0 ..< out.width {
                di := x * 4
                if di + 4 > len(dst) {
                    break
                }
                copy(dst[di:di + 4], pad[:])
            }
            continue
        }
        for x in 0 ..< out.width {
            di := x * 4
            if di + 4 > len(dst) {
                break
            }
            base := x * n

            rgb: [3]u8
            if use_lut {
                v := img_sample(row, base, bpc)
                raws[0] = v
                rgb = lut[v & 0xff]
            } else if direct_rgb {
                raws[0] = img_sample(row, base, 8)
                raws[1] = img_sample(row, base + 1, 8)
                raws[2] = img_sample(row, base + 2, 8)
                rgb = {u8(raws[0]), u8(raws[1]), u8(raws[2])}
            } else {
                for c in 0 ..< comp.n {
                    raws[c] = img_sample(row, base + c, bpc)
                    lo, hi := dec[2 * c], dec[2 * c + 1]
                    comp.v[c] = lo + f64(raws[c]) * (hi - lo) / maxv
                }
                f := colorspace_to_rgb(cs, comp)
                rgb = {blend_quantize(f[0]), blend_quantize(f[1]), blend_quantize(f[2])}
            }

            alpha: u8 = 255
            if ck != nil {
                // Compared against the RAW samples, before /Decode: the ranges
                // are sample values (8.9.6.4), not colour values.
                masked := true
                for c in 0 ..< n {
                    r := int(raws[c])
                    if r < ck[2 * c] || r > ck[2 * c + 1] {
                        masked = false
                        break
                    }
                }
                if masked {
                    alpha = 0
                }
            }

            dst[di] = rgb[0]
            dst[di + 1] = rgb[1]
            dst[di + 2] = rgb[2]
            dst[di + 3] = alpha
        }
    }
}

// ---------------------------------------------------------------------------
// Transparency: /SMask and a stencil /Mask
// ---------------------------------------------------------------------------

@(private)
img_apply_alpha :: proc(doc: ^Document, img: ^Image, out: ^Bitmap, scratch: mem.Allocator) {
    m := img.smask
    is_stencil := false
    if m == nil {
        m = img.mask
        is_stencil = true
    }
    if m == nil {
        return
    }

    plane, err := img_alpha_plane(doc, m, is_stencil, out.width, out.height, scratch)
    defer delete(plane, scratch)
    if err != .None || len(plane) < out.width * out.height {
        // A broken mask must not take the image with it: an opaque picture is
        // a far better answer than a blank page.
        add_repair(doc, .Bad_Resource, 0, img.stream.ref)
        return
    }

    matte: [3]f64
    unblend := false
    if !is_stencil && m.has_matte && img.cs != nil {
        c := color_make()
        c.n = min(len(m.matte), MAX_COLOR_COMPONENTS)
        for i in 0 ..< c.n {
            c.v[i] = m.matte[i]
        }
        matte = colorspace_to_rgb(img.cs, c)
        unblend = true
    }

    for y in 0 ..< out.height {
        dst := bitmap_row(out, y)
        prow := plane[y * out.width:]
        for x in 0 ..< out.width {
            di := x * 4
            if di + 4 > len(dst) || x >= len(prow) {
                break
            }
            a := prow[x]
            // Both mechanisms multiply into whatever alpha colour-key masking
            // already produced, rather than replacing it.
            dst[di + 3] = u8((int(dst[di + 3]) * int(a) + 127) / 255)
            if unblend && a != 0 && a != 255 {
                // /Matte says the colour was stored pre-blended against the
                // matte: c' = m + a*(c - m). Undo it (11.6.5.3). Done in RGB
                // rather than in the image's own components, which is exact
                // for the device spaces and a close approximation elsewhere.
                for k in 0 ..< 3 {
                    mk := matte[k] * 255
                    v := mk + (f64(dst[di + k]) - mk) * 255 / f64(a)
                    dst[di + k] = blend_quantize(v / 255)
                }
            }
        }
    }
}

// img_alpha_plane decodes a mask to one byte of alpha per pixel, resampled to
// `w` x `h`. The result is allocated with `scratch` and belongs to the caller.
//
// Resampling is nearest-neighbour. An /SMask at a different resolution to its
// image is ordinary -- a photograph at 300 dpi with a 72 dpi cut-out mask, say
// -- and interpolating the mask would soften an edge the producer drew hard.
@(private)
img_alpha_plane :: proc(doc: ^Document, m: ^Image, is_stencil: bool, w, h: int,
                        scratch: mem.Allocator) -> ([]u8, Error) {
    if m == nil || w <= 0 || h <= 0 || w > MAX_IMAGE_PIXELS / h {
        return nil, .Invalid_Argument
    }
    id, err := img_fetch(doc, m, scratch)
    defer img_release(&id, scratch)
    if err != .None || id.s.n <= 0 || len(id.dec) < 2 * id.s.n {
        return nil, err == .None ? .Bad_Image : err
    }
    if m.width <= 0 || m.height <= 0 || m.width > MAX_IMAGE_PIXELS / m.height {
        return nil, .Bad_Image
    }

    src, aerr := make([]u8, m.width * m.height, scratch)
    if aerr != nil {
        return nil, .Out_Of_Memory
    }

    maxv := f64((int(1) << uint(clamp(id.s.bpc, 1, 16))) - 1)
    if maxv <= 0 {
        maxv = 1
    }
    stencil := is_stencil || m.is_mask
    for y in 0 ..< m.height {
        row := img_row(id.s, y)
        for x in 0 ..< m.width {
            v := f64(img_sample(row, x * id.s.n, id.s.bpc))
            v = id.dec[0] + v * (id.dec[1] - id.dec[0]) / maxv
            if stencil {
                // A stencil /Mask marks what is masked OUT: sample 0 (decoded
                // value 0) paints the base image, 1 hides it (8.9.6.4). That
                // is the same polarity an /ImageMask uses.
                src[y * m.width + x] = v < 0.5 ? 255 : 0
            } else {
                // An /SMask is DeviceGray by definition (11.6.5.2), so the
                // decoded component is the alpha; no colour conversion.
                src[y * m.width + x] = blend_quantize(v)
            }
        }
    }

    if m.width == w && m.height == h {
        return src, .None
    }
    defer delete(src, scratch)

    out, oerr := make([]u8, w * h, scratch)
    if oerr != nil {
        return nil, .Out_Of_Memory
    }
    for y in 0 ..< h {
        sy := clamp(y * m.height / h, 0, m.height - 1)
        for x in 0 ..< w {
            sx := clamp(x * m.width / w, 0, m.width - 1)
            out[y * w + x] = src[sy * m.width + sx]
        }
    }
    return out, .None
}