The specimen is yours · pattern

The Palette Your GIF Was Given

Give a photograph 256 colours and watch every compromise become a byte. Your image stays in this browser while median cut and fixed-point refinement build its palette, CIEDE2000 measures the changed pixels, and a real GIF encoder exposes its LZW dictionary and exact file size. The concession is visible beside the result: lower per-pixel error need not look better, and these bytes belong to this encoder rather than the smallest GIF possible.

A GIF does not remember the millions of colours a camera can hand it. For each image block it points every pixel at a table with no more than 256 entries. Choosing that table loses colour. LZW comes later and loses nothing: it codes the chosen table indices as repeated phrases.

First, make the standard answer

Before this page accepts an image, a deterministic 24,000-index fixture crosses every GIF code-width boundary. The independently written decoder has to return every index. These values come from Appendix F of CompuServe's 31 July 1990 GIF89a programming reference.

...Clear code
...EOI code
...first free
...starting bits
...largest code used

m = 8. Clear = 2m = 256. EOI = Clear + 1 = 257. First free = Clear + 2 = 258. Initial width = m + 1 = 9 bits. The 12-bit ceiling is 212 - 1 = 4095 = 0xFFF.

transitionencoder boundarytrace position

running

Each trace token is code/width. The stream starts with Clear 256, ends with EOI 257, packs least-significant bits first, splits payload into blocks of at most 255 bytes, adds a zero block, then trailer 0x3B.

The fixture alternates high-entropy stretches with runs, on purpose. A stream of pure noise crosses every width boundary but never once reaches the case Welch describes on page 16 of his 1984 paper, where a code equals the decoder's own next free code. That branch is the only place a decoder built on the literal reading of Appendix F diverges, so a fixture that misses it can be passed by a wrong decoder. This one reaches it ... times and fills and clears the full 12-bit table ... times.

The file stays here

This is inspectable evidence, not a cryptographic proof that page code is kind. The inline Content Security Policy sets connect-src 'none', forms and workers are disabled, all program and font files are same-origin, and the instrument has no request API path. Open your browser's Network panel if you want the stronger view. form-action 'none' is deliberately absolute, which has a visible cost: the search box in the site banner above cannot submit from this page. Use Ask the Wasteland directly.

...HTTP(S) resource entries since navigation

...new entries after baseline

loadlast measured action

Measuring load baseline

Give it pixels it has never seen

Drop one PNG, JPEG, WebP, BMP, GIF87a, or GIF89a. Within the displayed byte cap, the complete File is read into memory. Non-GIF files go through this browser's image decoder. GIF bytes also go through this page's bounded parser, including local tables, interlace passes, transparency, disposal, and every image block within the displayed animation caps.

Or drop one file here. Nothing is posted.

Preparing the shipped fallback specimen...

fallback......

Safety caps: 268,435,456 file bytes in memory, then 4096 × 4096 = 16,777,216 decoded pixels. Files above either are not called invalid. This instrument declines them before the corresponding large allocation.

The palette, then the bill

Median cut begins with a 15-bit histogram, five high bits from each sRGB byte, and splits occupied boxes at weighted medians. The middle view is that raw heuristic. The right view alternates nearest-centre assignment and centroid updates, the fixed-point step Heckbert describes. No dithering is used.

browser-decoded original

raw median cut

after fixed-point refinement

...palette entries
...mean CIEDE2000
...95th percentile
...complete GIF
...LZW payload

... pixels included, ... excluded as transparent, ... occupied 15-bit histogram bins.

... active palette entries. If the image cannot split into K occupied boxes, remaining table entries are deterministic black padding and are marked as padding in their swatch titles.

CIEDE2000 error map

browser decodes emitted GIF

The generated GIF decoded through the browser's own image pipeline

independent index decoder

...

The decoder does not share dictionary mutation code with the encoder. The browser rendering is visible corroboration, not this check.

Save this generated GIF

CIEDE2000 is a per-pixel difference formula. It misses contouring, spatial structure, viewing size, and preference. A lower mean does not guarantee a better-looking image. The map and 95th percentile stay beside the mean so one average cannot hide the tail.

A heuristic can still keep an account

Heckbert does not call median cut optimal. The refinement reaches a fixed point, which can be only a local minimum. What it can promise here is narrower: for each accepted step, squared byte-RGB distortion D does not rise.

Raw median cut

D
...
mean CIEDE2000
...
GIF bytes
...

Refined, ... step(s)

D
...
mean CIEDE2000
...
GIF bytes
...
iterationDchange

A centroid may stay where it was if its cluster empties. Real-valued centres set assignment and D; emitted palette triplets are rounded to bytes. Stable assignments or 20 accepted iterations stop the process.

The promise is about D and nothing else, and the shipped fallback shows why that matters. At K = 4 the refinement lowers D from 1,821,097,567 to 1,651,870,986, which is what it guarantees, and in the same step the mean CIEDE2000 gets worse, from 19.942 to 19.989, while the file gets smaller, from 11,119 to 10,459 bytes. Squared byte-RGB distance and a perceptual difference formula are two different objectives, and moving one is not moving the other. Run the sweep on your own file and read the two columns separately.

Colour error is not file size

Run eight complete encodes of the same pixels. More colours can lower per-pixel error while making the index stream less repetitive and the LZW payload larger. That is a possibility, not a law. The curve below belongs to your specimen and this deterministic encoder.

Run the sweep to draw the measured frontier.

Kmean error95th percentilecomplete GIFLZW payload

Every byte has a drawer

Re-encoded file ledger

classbytes

LZW stream facts

Widths observed: ...

Sub-blocks: ...

Final EOI width: ...

Self-referential codes in your stream: ...

Round trip: see the independent decoder above

The encoder emits Clear when its 12-bit table is full. Deferred clearing is legal, but is not this encoder's policy. The image is not interlaced. Palette padding is black and deterministic.

The dictionary it built

These are the entries the independently written decoder created while reading your file's compressed stream, not a diagram of LZW. Each row is one dictionary entry: an existing code, one appended palette index, and the phrase that entry now stands for. ...

codeprefix code+ indexphrase lengthphrase, as palette indices

Codes 0 through ... are the literal palette indices and are not dictionary entries. Clear and End of Information sit immediately above them, and the first entry a stream can create is the code after those two.

Apparatus, choices, and limits

Every free choice

  • Input pixels. Measurements describe the 8-bit sRGB-like RGBA pixels returned by this browser. ICC profiles, EXIF orientation, HDR transfer functions, and wide-gamut conversion may differ between browsers.
  • Prequantization. Five high bits of R, G, and B make 32,768 histogram bins. Box axis ties use R, then G, then B. Splittable boxes are chosen by greatest population, then range, then oldest creation order. This schedule is an implementation choice where the paper does not fully prescribe one.
  • Distance and refinement. Assignment minimizes squared byte-RGB distance. Empty clusters retain their old centre. A step is accepted only if D does not increase. Stable assignments or 20 steps stop it. This is local improvement, not a global optimum.
  • Perceptual metric. Browser sRGB bytes are inverse-companded to XYZ D65 and CIELAB. CIEDE2000 uses kL = kC = kH = 1. The 95th percentile uses the nearest-rank rule. The formula is separately checked against all 34 published Sharma, Wu, and Dalal rows with a chosen tolerance of 0.0001.
  • Alpha. Default alpha is composited onto an explicitly white matte and included in metrics. One-bit mode reserves index 0, excludes alpha below the visible threshold from metrics, and defaults to 128. GIF has no continuous alpha.
  • GIF policy. Global palette, deterministic black padding, no interlace, no dithering, Clear when the dictionary is full, sub-blocks up to 255 bytes, and one complete non-animated re-encode. Palette order, clear timing, interlace, extensions, frame differencing, and animation strategy can all change another encoder's byte count.
  • Safety. Input-file limit 268,435,456 bytes, then decoded raster limit 4096 × 4096. Uploaded GIF inspection also stops at 128 frames or 33,554,432 stored composite pixels. These are memory policies, not statements that a larger image or animation is malformed.
  • Degenerate specimens. If every included pixel lands on one palette entry, or already sits exactly on an entry, the raw-against-refined and error comparisons compare a quantity with itself. The page says so above the numbers instead of reporting a zero as a finding.
  • One decoder rule was changed after measurement, on 9 August 2026. When the final data code is the one that pushes the decoder's own counter onto a power of two, the decoder widens by a bit but encoders do not follow it there. Measured on the same index streams: this page's encoder and gifsicle 1.94 produce byte-identical payloads on 440 of 440 streams compared, including all 40 that land on that boundary, and both write End of Information at the narrower width; ImageMagick 6.9.12 writes the same bytes plus one zero pad byte. The original decoder refused the narrower ending, which meant refusing files gifsicle itself writes, so it now retries once at the previous width and accepts only End of Information there. Truncated payloads are still refused: 8,966 deliberately shortened streams, none accepted.

What this does not prove

  • It does not prove that this palette looks best, that its GIF is the smallest possible, or that median cut recovers colours once present in a source.
  • It does not identify which program made an uploaded GIF. Original-stream facts and this page's re-encoded facts remain in separate ledgers.
  • It says nothing about authorship, authenticity, editing history, or whether GIF is suitable for preservation.
  • The privacy panel shows policy and observed browser activity. It cannot prove benevolence against malicious page code, extensions, or a compromised browser.
  • No dithering verdict is offered. Dithering can exchange local pixel error for spatially averaged appearance and often changes index repetition. The Grey That Isn't There owns that instrument.

Fallback specimen

palette-stress-test.png is a 512 by 512 raster generated from first principles by generate-fallback.mjs. It contains a smooth hue field, neutral ramp, hard flat regions, a repeated tile, one-pixel detail, and an alpha ramp. Artificial Wasteland dedicates both the image and generator to the public domain under CC0-1.0. No external picture or author is inside it.

Primary sources

  1. CompuServe Incorporated, Graphics Interchange Format Version 89a, Programming Reference, document date 31 July 1990. Sections 15 through 22 and Appendix F supply the byte layout, sub-block rule, interlace passes, and LZW anchor.
  2. Paul S. Heckbert, Color Image Quantization for Frame Buffer Display, SIGGRAPH 1982, Computer Graphics 16(3), pages 297 to 307. This supplies the 15-bit histogram, median cut, squared-RGB D, and fixed-point refinement.
  3. Gaurav Sharma, Wencheng Wu, and Edul N. Dalal, The CIEDE2000 Color-Difference Formula: Implementation Notes, Supplementary Test Data, and Mathematical Observations, Color Research and Application 30(1), 2005, pages 21 to 30. The visible check uses all 34 rows of the authors' companion test file.

Offline mirror: node research/the-palette-your-gif-was-given/verify-the-palette-your-gif-was-given.mjs. It recomputes the anchor, fixture, fallback palettes, metrics, GIF byte ledger, every sweep point, the published CIEDE2000 test, Welch's own 1984 worked example code for code and entry for entry, and the byte offset as well as the code of every refusal path this parser can raise. It reads the swept palette sizes out of the control above rather than restating them, recomputes the fixed-point distortion pixel by pixel instead of rereading the list the loop already filtered, and enumerates the refusal codes in the source so a new one cannot be added without a fixture.