DEV Community: 이준김

Adaptive PNG filtering made my animations 2.4x bigger

이준김 — Mon, 24 Aug 2026 03:43:52 +0000

I added adaptive per-scanline filtering to an APNG encoder, because that is what
you are supposed to do. PNG lets every row pick one of five filters, the spec
suggests picking the one that minimises the sum of absolute differences, and
every PNG optimiser I have read does exactly that.

It made seven of eight real animations bigger. The worst went up 2.41x.

Here is the whole set. Same frames, same zlib level, same encoder; the only
difference is whether each scanline gets a filter chosen for it or is left at
filter None.

file	frames	canvas	None	adaptive	ratio
Cicada molting	51	320x512	6142.9 KB	14786.8 KB	2.41x
Zipper	15	320x320	278.9 KB	520.0 KB	1.86x
Foucault pendulum	288	180x240	5953.8 KB	10492.0 KB	1.76x
Universal joint	60	280x164	678.1 KB	1148.0 KB	1.69x
Lockstitch	18	419x500	197.3 KB	311.9 KB	1.58x
Gun turret	70	700x600	1108.6 KB	1590.2 KB	1.43x
Muybridge race horse	15	300x200	687.0 KB	731.9 KB	1.07x
Lunar libration	56	640x642	10939.2 KB	9129.3 KB	0.83x

Eight animations from Wikimedia, decoded to full-canvas RGBA and re-encoded as
APNG. One file got smaller. Seven got bigger, and Cicada molting went from
6 MB to 14.5 MB.

Three explanations that sound right

The first thing I did was write down why, which in hindsight was the mistake.
The story I wrote into the source comment was this: flat art has whole scanlines
that repeat, filter None leaves those repeats byte-identical so LZ77 can match
one row against another across the image, and mixing filter types per row
rewrites identical rows into different bytes and destroys the long matches.

It is a good story. It is also wrong, and it took one number to find out. I
measured the fraction of scanlines that are byte-identical to the row above
them:

file	repeated rows	ratio
Lockstitch	39.1%	1.58x
Gun turret	20.2%	1.43x
Lunar libration	11.2%	0.83x
Universal joint	4.8%	1.69x
Cicada molting	0.0%	2.41x
Foucault pendulum	0.0%	1.76x
Muybridge race horse	0.0%	1.07x
Zipper	0.0%	1.86x

The worst file in the set has no repeated scanlines at all. Across all 28 pairs
of files, "more repeated rows" predicted "worse adaptive result" in 6 of them —
a rule that explains nothing lands near 14.

Two more candidates went the same way. Palette size, on the theory that flat art
means few colours: 10 of 28 pairs, and the best and worst files sit at 190 and
183 colours. How much the heuristic switches filter type between adjacent rows,
on the theory that the thrashing is what costs: 14 of 28, which is exactly
chance.

At that point I had a real result and three dead explanations, which is a
reasonable place to stop guessing and run an experiment.

The experiment that settles it

If the damage comes from choosing differently per row, then holding one filter
constant for the whole image should be fine. If the damage comes from
differencing at all, then any fixed filter loses too.

So I forced each of the five filters on every scanline:

file	None	Sub	Up	Average	Paeth	heuristic
Cicada molting	1.00x	1.59x	1.83x	2.43x	2.22x	2.41x
Zipper	1.00x	1.48x	1.63x	2.08x	1.75x	1.86x
Foucault pendulum	1.00x	1.39x	1.72x	2.28x	1.74x	1.76x
Universal joint	1.00x	1.48x	1.74x	2.12x	1.79x	1.69x
Gun turret	1.00x	1.42x	1.37x	2.09x	1.46x	1.43x
Muybridge race horse	1.00x	1.07x	1.10x	1.07x	1.06x	1.07x
Lunar libration	1.00x	0.90x	0.86x	0.83x	0.86x	0.83x

Every fixed filter loses on the same seven files, by roughly as much as the
heuristic does. It is not the switching. It is the differencing.

And look at the last row. On Lunar libration — the one continuous-tone source in
the set — every single differencing filter wins. The textbook advice is not
wrong. It is right about a kind of image, and seven of these eight are the other
kind.

Why the heuristic cannot see this

Minimum sum of absolute differences scores byte magnitude. DEFLATE pays for
repetition. On these frames those two things point in opposite directions.

A run of identical pixels under filter None is a run of identical bytes, which
is the single thing LZ77 is best at. Under Sub it becomes a run of zeros, which
also compresses, but the moment the run ends the boundary value depends on
whatever came before, and across an image made of flat regions with hard edges
you end up with many small, varying values instead of a few long, identical
runs. Small varying bytes win on sum-of-absolute-differences. Long identical
runs win on file size.

The heuristic never finds out, because it is not measuring file size. Its
preference is visible in how often it leaves a row alone:

rows the heuristic assigned filter None: 0.0% to 0.2%

Zero to two rows in a thousand, on files where keeping every row at None is
2.4x smaller. The rule is not slightly miscalibrated. It essentially never
selects the winning option, because the winning option almost never has the
lowest sum of absolute differences.

The fix

One extra compression per animation. Encode frame 0 both ways, keep the
strategy that produced fewer bytes, use it for every frame:

const probe = frames[0];
const adaptive =
  compress(probe.data, width, height, level, true).length <
  compress(probe.data, width, height, level, false).length;

Not per frame. The frames of one animation are the same kind of picture, so the
winner on the first is the winner throughout, and paying double on every frame
to re-confirm that is the expensive way to learn nothing. Cost: one additional
compress of one frame.

This also keeps the win where the win is real. Lunar libration still gets its
0.83x, because the probe finds it.

The bug in the measurement, which is the part I would want to read

The forced-filter table above did not work the first time. It came out like
this:

every row forced to one filter:
  None 1.43x  Sub 1.43x  Up 1.43x  Average 1.43x  Paeth 1.43x

Five identical numbers. It would have been easy to squint at that and write
something about how the filter choice barely matters — except that the first
column cannot be 1.43x. Forcing filter None is the None encoder. That column
is 1.00x by definition, and any other value means the measurement is not
measuring what it says.

The cause: the harness builds each variant by copying the encoder to a temp file
with one line replaced, and all five forced variants were written to the same
filename. Node caches modules by URL, so the second import never sees the new
bytes. Every column was the same build.

The fix was a unique filename. The lesson was the assertion that now runs before
anything is printed:

if (Math.abs(fixed[0] / n - 1) > 0.001) {
  console.error(`forcing did not take: forced-None is ${fixed[0] / n}x of None`);
  process.exit(3);
}

A measurement harness should contain at least one case whose answer you already
know, and it should refuse to report anything if that case comes out wrong. This
one produced a plausible, publishable, completely fictitious result until it had
one.

What I would take from this

Three things, in order of how much they cost me:

A mechanism you have not measured is a guess with a diagram. I wrote the LZ77-across-identical-scanlines explanation into a source comment as fact. The worst file in the set has 0.0% identical scanlines. It sat there being confidently wrong until something made me check it.
When two explanations disagree, force each one and see. Three correlational metrics gave me nothing. One experiment — hold the filter constant — answered it in a single run.
Optimisation folklore is usually true about a specific input distribution and silent about which one. Adaptive PNG filtering is right for photographs and wrong for palette art, and nothing in the advice says so.

The encoder runs in the browser, in the GIF tools on
Image Machine — the measurements above come from
the GIF to APNG converter,
where a 6 MB upload coming back as 14.5 MB is the kind of thing a user notices
immediately. Nothing is uploaded; the whole pipeline is client side, which is
also why the encoder's own efficiency is the only lever there is.

A GIF re-encode made the file 4.5x bigger. Interframe differencing fixed it.

이준김 — Sun, 23 Aug 2026 19:42:38 +0000

Cropping a GIF should not make it bigger. Ours did, and not by a little: a
288-frame Foucault pendulum went from 1074 KB in to 4881 KB out, and a 70-frame
gun turret went 116 KB to 1232 KB. That is 455% and 1062%. The same thing
happened with no crop at all, which is the detail that gives the cause away.

If a pure re-encode inflates the file, the encoder is not losing to the
compressor. It is throwing away something the source already had.

What it was throwing away

GIF stores an animation as a sequence of image blocks, and each block carries a
disposal method and its own local palette. Nothing requires a block to cover the
whole canvas or to be a complete picture. A well-optimised animated GIF writes
frame 0 in full and then writes every later frame as only what changed,
leaving the rest transparent and setting disposal to "leave the previous frame
in place". For the pendulum, most of the canvas is a static rig and a dark
background; the swinging bob is a few percent of the pixels. The source spent
its bytes on the bob.

Our encoder wrote every frame as a full-canvas, fully opaque keyframe. Each
frame was individually correct and the animation played correctly, so nothing
looked wrong. It just re-paid the cost of the static background 287 more times
than it needed to.

The fix

For an opaque source, frames after the first are written as the previous frame
plus the changed pixels. Unchanged pixels get the transparent palette index,
and the frame's disposal is set to 1, "do not dispose". The decoder composites
it over what is already on the canvas.

function changedPixels(cur, prev) {
  const count = cur.length / 4;
  const mask = new Uint8Array(count);
  let changed = 0;
  for (let p = 0, i = 0; p < count; p++, i += 4) {
    if (cur[i] !== prev[i] || cur[i + 1] !== prev[i + 1] || cur[i + 2] !== prev[i + 2]) {
      mask[p] = 1;
      changed++;
    }
  }
  return { mask, changed };
}

RGB only, no alpha compare: this path runs on opaque sources, where every alpha
is already 255. Sources that carry real transparency keep the old keyframe path,
because the transparent index is then already spoken for.

One constraint shaped the implementation. We use gifenc, which
hard-codes the image descriptor to x=0, y=0, so a frame cannot be written as a
sub-rectangle at an offset the way most GIF encoders do it. Every frame stays
full-canvas, and the saving comes from LZW collapsing the long runs of the
repeated transparent index instead. That reaches the same redundancy. It just
spends a little more CPU to get there.

The heuristic that did not work

The obvious optimisation is a threshold: if more than some fraction of the
frame changed, a delta is not worth it, so write a keyframe. We implemented it
and then deleted it, because the measurements did not cooperate.

frame-to-frame change	result vs. keyframes
13% of pixels	74% of the size
26% of pixels	112% of the size

The file that changed twice as much was the one that should have used deltas,
and the file that changed less was the one that should not have. What decides it
is not how many pixels moved but how scattered the movement is, because LZW
pays for runs, not for pixels. A count of changed pixels cannot see that, and
neither can any threshold built on one.

So the encoder stops guessing. For each file it takes three sample frames,
encodes each one both ways, and keeps whichever mode won. Both candidates are
appended after the identical frame 0, so the header, the global palette and the
loop block cancel out and what is compared is that frame's cost alone.

The trap worth knowing about

The changed pixels have to be packed into a buffer of their own before being
quantized, and that buffer must be a fresh allocation, never a subarray view:

const out = new Uint8ClampedArray(changed * 4);

gifenc's quantize() and applyPalette() both do new Uint32Array(rgba.buffer).
On a view, .buffer is the whole underlying buffer, not the slice. Both
functions would read far past the region you meant to hand them and build the
palette from the wrong pixels, silently, with no error and a plausible-looking
result. This is a general hazard with any typed-array API that reaches for
.buffer, and it is worth checking for before you spend an afternoon on a
palette that is subtly wrong.

Results

Ten animated GIFs from Wikimedia Commons, including the pendulum and the turret
above, a Muybridge race horse, a cicada molting, lunar libration, a universal
joint and a constant-velocity joint.

Output is 15% to 100% of the previous encoder's, median 90%. Zero files got bigger.
The two worst cases are transformed: turret 1232 KB to 184 KB, pendulum 4881 KB to 1292 KB.
All ten are now smaller than the source they came from, in a 17% to 79% range.
Colour error is equal or better on all ten. Frame count, dimensions, per-frame delay, loop flag and transparency are all preserved.

The median matters as much as the wins: half of these files barely moved,
because half of them do not have a large static region to exploit. This is a
fix for a failure mode, not a general compression gain, and it is worth being
precise about which one you are shipping.

Checking it against something that is not us

A round-trip through our own decoder only proves the encoder and the decoder
agree with each other. So the test builds a synthetic animation of under 255
colours, encodes it, and decodes the result with Pillow, which implements
GIF disposal independently of anything we wrote. All 12 frames matched
pixel-for-pixel, and the delays matched too.

If you write an encoder for a format with compositing semantics, find a second
implementation and make it the judge. Disposal methods are exactly the kind of
thing two codebases can agree to get wrong together.

What it cost

Encoding takes longer, because deciding the mode means encoding three frames
twice. Worst measured case was +140 ms on a 22-frame file. On large files, where
the absolute time is what you would notice, it stayed within +7%.

The encoder runs in the browser, in the GIF tools on
Image Machine — the measurements above come from
the GIF cropper, where the
inflation showed up first. Nothing is uploaded; the whole pipeline is client
side, which is also why the encoder's own efficiency is the only lever there is.

Search Console found one 502. All 11 locales were broken, and no test could have caught it.

이준김 — Sat, 22 Aug 2026 16:16:15 +0000

Search Console showed one URL in the "Server error (5xx)" bucket. One. On a site
with about 1,700 pages, that reads like noise, and I nearly left it.

The URL was /th/opengraph-image — the Thai locale's OpenGraph image. So I
checked the other ten locales before closing the tab.

en/opengraph-image: 502
ko/opengraph-image: 502
th/opengraph-image: 502
ja/opengraph-image: 502
de/opengraph-image: 502

Every single one. The route had never worked, on any locale, and Search Console
knew about exactly one of them because it had only ever tried one.

Why nothing told me

This is the part worth internalising, because it generalises past OG images.

app/[locale]/opengraph-image.tsx is a Next.js file convention. You do not
import it, you do not link to it, and no page in your app renders it. Its entire
job is to make Next inject a <meta property="og:image"> tag pointing at a
route it generates for you.

So consider what could have caught this:

Not the browser. No page requests the image. You can click through the whole site and see nothing wrong.
Not the build. It compiles fine. The failure is at render time, per request.
Not the tests. Nobody writes a test for an image nobody imports.
Not the deploy checks. Mine fetch pages and grep for text. This route isn't a page.
Not a user report. The failure surface is a social preview card being blank on someone else's site.

The only witness was a crawler, and only because it stumbled across one locale.

The bug is a child count

next/og renders with Satori, which
implements a subset of CSS. One of its rules:

Expected <div> to have explicit "display: flex" or "display: none" if it has
more than one child node.

Now look at the line that broke it:

<div style={{ fontSize: 72, fontWeight: 800, maxWidth: 1000 }}>
  {TOOL_COUNT}+ Free Online Text Tools
</div>

Read it as a human and it is one sentence. Read it as JSX and it is two
children: the expression container {TOOL_COUNT}, and the text node
"+ Free Online Text Tools". The div has no display, so Satori throws.

The rest of the file was fine. Every other div either declared display: flex
or genuinely had one child. This one looked exactly like the others.

How a thrown renderer becomes a 502

Worth following, because the error you see is three layers away from the cause.

ImageResponse streams. By the time Satori throws, Next has already sent
response headers and started the body, so it cannot turn the failure into a 500
page — it closes the connection. Node logs:

Error: failed to pipe response
  [cause]: Error: Expected <div> to have explicit "display: flex" ...

nginx, waiting upstream, logs:

upstream prematurely closed connection while reading response header from upstream

and returns 502 to the client. So the outward symptom is a gateway error,
which is the vocabulary of infrastructure problems: you go and look at memory,
at the process, at the proxy config. The actual cause is a JSX child count.

The fix, and the one I did not choose

The error message asks for display: flex, and that works. I did something
smaller:

{`${TOOL_COUNT}+ Free Online Text Tools`}

One template literal is one text node, so the multi-child rule never applies.
The reason to prefer it: adding display: flex to a text div also makes the
text a flex item, which changes how it wraps against that maxWidth: 1000.
The template literal fixes the crash and changes nothing about the layout.

Result across all eleven locales, in production:

200  image/png  244560 bytes   (1200x630)

Three things I would do differently

1. Curl the route after touching it. It is the only check that exists.
Nothing in the normal loop covers a file that nothing imports.

2. Know which pages actually depend on it. This was the part that turned a
curiosity into a real bug. Pages that set openGraph.images explicitly override
the file convention and were fine. Pages that do not — my privacy policy and
terms pages, in all eleven locales — inherited it, and were publishing a 502 as
their og:image. I would not have guessed that split without checking:

curl -s https://example.com/en/privacy-policy \
  | grep -o '<meta property="og:image" content="[^"]*"'

That gets you the tag. To see the card a crawler would actually build from
it, an Open Graph previewer
will fetch the page and render the result.

3. Treat a count of one as a sample, not a total. Search Console reports
what it happened to crawl. One 5xx URL on a multi-locale route means "at least
one", and the cheapest possible follow-up — a for-loop over the locale list —
turned 1 into 11.

This happened on textmachine.org, a set of text
tools that do their work in the browser.

One last detail I find genuinely funny. There is a second OG route in the same
codebase, app/og/route.tsx, which has always worked. I counted its divs: 15,
of which 13 declare display: flex. The two that do not are
<div>TEXT MACHINE</div> and <div>textmachine.org</div> — single text nodes,
where the rule does not apply. That file follows Satori's constraint exactly,
including knowing when it is not needed.

So the knowledge existed in the repository. It just did not exist in the second
file, because nothing carries a rule from one file to another except the person
writing it — and a rule you can only violate in a route nobody renders is a rule
you will violate eventually.

Compressing an image to an exact file size, in the browser

이준김 — Sat, 22 Aug 2026 13:26:47 +0000

"Make this photo under 100 KB" is one of the most common things people need
from an image tool, and one of the few things almost no image editor exposes
directly. Photoshop gives you a quality slider. cwebp gives you -q. The
canvas API gives you a float between 0 and 1. None of them takes bytes.

The reason is that the mapping you want does not exist in the encoder. You ask
for a file size; the encoder only accepts a quality. So you have to search.

This is a writeup of how that search is implemented in a browser-only image
tool, including the parts that are less obvious than "do a binary search" —
what happens when the assumption behind binary search is false, why PNG needs a
completely different search space, and why the whole thing has to leave the
main thread.

The naive version, and why it is not good enough

The obvious loop:

let q = 90;
while (q > 1) {
  const blob = await encode(q);
  if (blob.size <= target) return blob;
  q -= 5;
}

It works. It is also up to 18 encodes, and every encode is a full pass over
every pixel. On a 12 MP phone photo that is a real amount of work, and the user
is watching a spinner the whole time.

Worse, it is biased. Stepping down from 90 finds the first quality that fits,
not the best quality that fits. If the target is generous you stop at 90 and
hand back a file far under the budget — which sounds harmless until you realise
the user asked for "under 100 KB" precisely because they want to spend all
100 KB, not 30.

Binary search over the quality space

The real requirement is: find the highest quality whose output fits under the
target. That is a textbook binary search, provided one assumption holds (more
on that in a moment).

let low = 1;
let high = 100;
let best = null;
let smallest = null;

for (let i = 0; i < 8 && low <= high; i++) {
  const mid = Math.floor((low + high) / 2);
  const r = await encodeAt(mid);

  if (!smallest || r.blob.size < smallest.blob.size) smallest = r;

  if (r.blob.size <= target) {
    best = r;        // fits — try to spend more
    low = mid + 1;
  } else {
    high = mid - 1;  // too big — back off
  }
}

const chosen = best ?? smallest;

Eight iterations is not an arbitrary cap. log2(100) ≈ 6.64, so seven
iterations are enough to collapse a 100-value range to a single candidate;
eight leaves a margin and still bounds the worst case at well under half the
linear scan. In exchange you get the best fitting quality rather than the
first one you tripped over.

Two details in that loop are worth more than the loop itself.

`best ?? smallest` — the failure path is a real path

If the target is smaller than the output at quality 1, nothing fits. best
stays null and a naive implementation throws.

That is the wrong behaviour, because the user's intent is still perfectly
clear. Someone who asks for a 5 KB thumbnail from a 20 MP photo is not helped
by an error dialog; they are helped by the smallest file the encoder can
produce, plus the honest information that it did not reach 5 KB.

So the loop tracks smallest on every iteration, independently of whether it
fits. Failing to hit the target degrades to "here is the closest we got"
instead of "no."

Monotonicity is an assumption, not a fact

Binary search over quality assumes that a higher quality always yields a larger
file. For JPEG that is nearly always true, and it is true enough that the
search converges on real photographs.

It is not a law. Quantization table changes across quality levels can, on
synthetic or heavily-banded images, produce a step where a higher quality
compresses marginally smaller. When that happens the search can walk into the
wrong half.

Tracking smallest separately covers this too, which is a nice property: the
same three lines that handle "target impossible" also handle "monotonicity
violated." You do not need to detect the violation, you just need to stop
trusting the search to have seen the smallest output.

PNG is a different problem entirely

Everything above assumes a quality parameter. PNG does not have one. PNG is
lossless; its compression level affects speed far more than size, and there is
no dial that trades fidelity for bytes.

To make a PNG meaningfully smaller you have to reduce the palette. That is
what "lossy PNG" tools like pngquant do: quantize 16.7 million possible colors
down to N, then let DEFLATE do far better on the smaller symbol set.

So the search space changes from quality to color count:

const cnum = lossless
  ? 0                                                  // 0 = full color
  : Math.min(256, Math.max(2, Math.round((quality / 100) * 256)));

UPNG.encode([buffer], width, height, cnum);

The binary search is structurally identical — it is still "find the highest
value that fits" — but the value being searched is a palette size from 2 to
256, and the perceptual cost of getting it wrong is completely different.
Dropping JPEG quality softens detail. Dropping PNG palette size produces
banding in gradients, which is far more visible and far less forgiving.

The part that actually breaks the page

canvas.toBlob() is asynchronous. It hands you a callback rather than
occupying the JS thread for the duration of the encode, so eight of them in a
row is eight callbacks and the page keeps painting between them.

UPNG.encode() is synchronous. It is a pako-backed DEFLATE running in
JavaScript, and on a large image it can occupy the main thread for several
seconds. Per call. And the target-size path calls it eight times.

That is not a slow spinner, that is a frozen tab. No spinner animates, no
button responds, and on a phone the browser may offer to kill the page.

The fix is a Web Worker, but the interesting part is what that forces on the
code structure. A worker has no DOM. It has no document, no
HTMLCanvasElement, no getImageData. So the encode logic cannot live in the
same module as the canvas code that produced the pixels.

The split ends up being:

compressEngine.ts   ← touches canvas/DOM, runs on the main thread
pngEncodeCore.ts    ← pure: (RGBA buffer, w, h, targetBytes) → ArrayBuffer
pngEncode.worker.ts ← thin wrapper that calls the core off-thread

pngEncodeCore takes raw RGBA bytes — exactly what
getImageData().data.buffer gives you — and returns an ArrayBuffer. It
imports nothing from the DOM, which is what makes it importable from both
sides. The binary search lives in the core, so the main thread and the worker
cannot drift apart in behaviour; there is one implementation, called two ways.

This is a generally useful shape for anything CPU-heavy in a browser:
separate the pure transform from the DOM plumbing, and the worker boundary
becomes a detail rather than a rewrite. The reason it is worth doing
deliberately is that the DOM dependency tends to creep in — one
document.createElement("canvas") inside the transform and the module can
never be imported by a worker again.

Transferables, and why this code deliberately does not use them

One more thing that matters at photo resolutions. A 12 MP image is
4032 × 3024 × 4 bytes of RGBA, about 48 MB. Passing that to a worker with a
structured clone copies all 48 MB.

ArrayBuffer is transferable, so the textbook fix is to post it with a
transfer list:

worker.postMessage({ buffer, width, height, targetBytes }, [buffer]);

That transfers ownership instead of copying, and the cost of handing the
pixels over drops to approximately nothing.

This implementation does not do that, on purpose, and the reason is worth more
than the optimization.

A worker can fail to exist. new Worker(new URL(...), { type: "module" })
throws in environments where module workers are unavailable or the bundler
emitted something the browser will not load, and even when construction
succeeds the worker can fire an error event before it does any useful work.
Both cases have to degrade to encoding on the main thread — slower and
blocking, but correct — rather than failing the user's compression.

Transferring detaches the buffer on the sending side. It becomes zero-length.
So the moment you add that transfer list, the main-thread fallback has nothing
left to encode, and a worker failure stops being a performance regression and
starts being a broken result.

There is a second, sharper reason here specifically. The buffer being sent is
imageData.data.buffer — it belongs to a live ImageData object obtained from
the canvas. Detaching it does not just cost you the fallback, it reaches back
into an object the rest of the function may still touch.

Both are avoidable, of course: encode a copy, or re-read the pixels from the
canvas in the fallback path. But getImageData on a 12 MP canvas is not free
either, and you would be paying it on the failure path — which is the path with
the least budget to spare, because it is about to run a multi-second
synchronous encode on the main thread.

So the trade taken is: pay one structured clone every time, to guarantee the
fallback always has valid pixels. The copy is a fixed, predictable cost on
the happy path. The alternative is a rare, hard-to-reproduce failure that
produces a wrong answer instead of a slow one.

That is generally the right way round. It is also the kind of decision worth
writing into a comment at the call site, because the next person to read
postMessage without a transfer list will assume it is an oversight and
"fix" it.

What this buys, and what it does not

The result is a tool where "compress to 100 KB" means what it says, runs
entirely on the user's machine, and does not freeze the tab while it works.
There is no upload, so there is no upload wait and no server-side size limit.

What it does not buy is magic. If a target is unreachable at the source
resolution, no search finds it, and the honest answer is to say so and offer
the closest result — or to resize first, which changes the pixel count and
therefore the whole curve. A search over quality cannot fix a budget that only
a smaller image can meet.

The implementation described here is from
Image Machine, a set of browser-side image tools:
compression to a target size, format conversion, resizing and effects. It has
no upload endpoint, so everything above runs on the machine you are sitting at.

You don't search for the key, you search for English: how cipher auto-solvers actually work

이준김 — Fri, 21 Aug 2026 21:53:08 +0000

You've figured out which cipher you're staring at — say a monoalphabetic cryptogram, or a Vigenère — but you don't have the key. No keyword, no shift, no crib. Manually, this is where people grind for hours. Automatically, a good solver recovers it in about a second. Here's how that actually works, so the tool isn't a black box.

The whole game rests on one idea: you don't search for the key, you search for English. A wrong key produces gibberish; the right key produces text that looks like a real language. So if you can score how English-like a candidate decryption is, breaking the cipher becomes an optimization problem — find the key that maximizes the score. Everything below is a variation on that theme.

The scoring function is the secret, and single letters aren't enough

The naive score is letter frequency: real English is ~12.7% E, ~9% T, and so on, so reward decryptions whose letter distribution matches. This is too weak. A decryption that's 95% correct can score as well as or better than the true plaintext on single-letter counts alone, because shuffling a few letters barely moves the histogram. The search then happily settles on a near-miss garble and calls it done.

The fix is n-grams — scoring sequences of letters, not single ones. English is far richer in some letter-pairs and triples (TH, HE, IN, ER; THE, AND, ING) than in others (QZ, JX, VKZ). Any decoding error injects rare, low-probability pairs and triples, which a bigram or trigram score punishes hard. So the fitness function is the sum of log-probabilities of every trigram in the candidate plaintext, using a frequency table built from a large English corpus. Truth scores strictly higher than any near-miss, which is exactly what you need to climb toward.

A useful diagnostic if you ever build one of these: if your solver lands on garbage, check whether score(true plaintext) > score(found). If truth scores higher, your fitness function is fine and your search is stuck — don't tune the scorer, fix the optimizer (next section). If truth scores lower, the scorer itself is too weak (you're probably on single letters — go to trigrams).

Cracking a monoalphabetic substitution (cryptogram)

A simple substitution maps each letter to another, fixed for the whole message. There are 26! ≈ 4×10²⁶ possible alphabets — brute force is hopeless. But the scoring trick makes it tractable:

Seed with frequency analysis. Count letters in the ciphertext; map the most common cipher letter to E, the next to T, and so on. This is usually 30–60% correct — a decent starting point, not the answer. (You can do this step by hand with a frequency analysis tool.)
Improve by local search. Swap two letters in the key, re-score, keep the swap if the score went up. Repeat. This is hill-climbing — and on its own it gets stuck in local optima: a key that's better than all its neighbors but still wrong.
Escape local optima with simulated annealing. The fix is to sometimes accept a worse swap, with a probability that starts high and "cools" toward zero. Early on the search roams freely and jumps out of bad valleys; late on it behaves like pure hill-climbing and locks onto the peak. Run a few random restarts and keep the best result. This reliably recovers normal English prose.

That's precisely what the substitution cipher solver does — frequency-seeded, then simulated annealing on trigram fitness — and it recovers both the message and the full cipher alphabet with no key or crib. Paste a cryptogram and it solves in well under a second.

Cracking a Vigenère without the keyword

Vigenère uses a repeating keyword, so it's polyalphabetic — letter frequencies are smeared flat and the substitution trick above doesn't directly apply. You break it in two stages:

Find the key length. Two classic methods. Kasiski examination looks for repeated sequences in the ciphertext and measures the distances between them — those distances tend to be multiples of the key length. The Index of Coincidence approach tries each candidate length and watches for the one where the slices look like natural (peaky) English. Run both, because they fail in different ways: Kasiski needs repeats, which short or repetitive text may not supply, while the IoC needs enough letters per column to be stable. When the two agree you almost certainly have the right length; when they disagree you do not have it yet.
Solve each column independently. Once you know the key length L, every L-th letter was enciphered with the same shift — so the ciphertext splits into L columns, and each column is just a Caesar cipher. Solve each one by frequency / chi-squared against English (only 26 shifts per column), and you've recovered the keyword letter by letter.

The robust way to drive this — and what the Vigenère solver does — is to solve at every plausible key length, then rank the resulting decryptions by English fitness and present the best, rather than committing to a single length guessed from a threshold (which fails on repetitive plaintext). A monoalphabetic message naturally collapses to a one-letter key, so the same tool degrades gracefully.

When automatic solving struggles

Auto-solvers are statistical, so they need enough text to be confident:

Too short. Under ~40–50 letters there often isn't enough signal; the trigram statistics are noisy. Get more ciphertext if you can.
Not English. The fitness table is language-specific. A French or German plaintext needs a French/German n-gram model.
Homophones, nulls, or padding. Homophonic substitution (several cipher symbols per plaintext letter) and inserted null characters break the one-to-one assumption — identify and strip those first.
It's not actually a simple substitution/Vigenère. If the solver can't find anything English-like at any setting, re-check the cipher type — start again with the cipher identifier.

The two-minute version

Identify the cipher (character set, IoC, structure) — or confirm it's a cryptogram / Vigenère.
Paste it into the matching auto-solver — substitution for cryptograms, Vigenère for keyword ciphers.
Read off the plaintext and the recovered key. If it stalls, check the message length and language, and re-confirm the cipher type.

No key, no problem — the statistics of English do the work for you. All of these run entirely in your browser; nothing you paste is uploaded.

I shipped a Kasiski calculator with 21 passing tests. It got 3 of 5 key lengths wrong.

이준김 — Fri, 21 Aug 2026 21:33:46 +0000

Kasiski examination is the oldest way to break a Vigenère cipher. Find sequences
that repeat in the ciphertext, measure the gaps between them, and factor the
gaps. Because the key repeats on a fixed cycle, a repeat that comes from the
same plaintext encrypted at the same key offset sits at a distance that is a
multiple of the key length. Factor enough of those distances and the key length
should fall out.

The standard procedure, in every textbook I have read and every implementation I
have written, ends like this: tally how many distances each candidate factor
divides, and take the factor with the biggest tally.

That last step is wrong. Not subtly wrong on adversarial input — wrong on
ordinary English prose, most of the time, in a way that a unit test suite will
cheerfully certify as correct.

The tests were green and the tool was broken

My implementation had 21 unit tests. All passing. Then I ran it on five
realistic ciphertexts, enciphered with five realistic keys, and read the number
the page prints in the largest font:

True key length	What it answered
5	5 ✅
6	3 ❌
7	7 ✅
9	3 ❌
13	2 ❌

Three of five. And look at the failures: 3 divides 6, 3 divides 9, 2 divides
13... no it does not. 2 divides nothing about 13. It just wins anyway.

Why the fixtures lied

Every fixture in those 21 tests was a hand-built string, and I built each one so
that its repeat distances were clean multiples of the key length. That is what
the method is supposed to produce, so it felt like the honest thing to test.

It is not. On real text, most repeated trigrams are coincidences. THE appears
everywhere; two occurrences of THE at unrelated key offsets encipher
differently, but plenty of other short sequences collide by accident and
contribute a distance that carries no information about the key at all.

A hand-built fixture has no coincidental repeats. So it never exercises the
one thing the ranking step exists to survive.

What each factor scores for nothing

Here is the arithmetic the tally step skips.

Take a set of distances with no signal in it whatsoever — pure noise. How many
does the factor 2 divide? Half of them. How many does 3 divide? A third.
How many does 13 divide? One in thirteen.

So the raw tally is not a measurement of evidence. It is a measurement of
evidence plus a free head start that shrinks as the factor grows. Ranking
small factors against large ones on that number is like ranking sprinters
against marathoners by how long they were on the track.

The fix is to divide the head start out. Call it lift:

lift(f) = f × (distances divisible by f) / (total distances)

lift = 1.0 means "exactly what chance would give you". lift = 3.2 means
"3.2× more than chance". Now every candidate is on the same scale.

Lift fixes half of it, and creates the other half

Let D be the total number of distances and p the fraction of them that are
genuine — actual multiples of the true key length L.

For a proper divisor d of L: every genuine distance is divisible by d
(since d | L | kL), and the noise contributes 1/d of the rest.

hits/D  = p + (1−p)/d
lift(d) = d × (p + (1−p)/d) = p·d + (1−p)

Since d < L, that is strictly less than lift(L) = p·L + (1−p). Divisors
solved. Lift demotes them automatically, with no special case.

For a multiple kL: a genuine distance mL is divisible by kL only when
k | m, so roughly p/k of them survive, and the noise contributes
(1−p)/(kL).

hits/D    = p/k + (1−p)/(kL)
lift(kL)  = kL × (p/k + (1−p)/(kL)) = p·L + (1−p)

That is lift(L). Exactly. Not approximately, not usually — the multiples
of the true key length tie with the true key length on lift, forever, at every
sample size. Lift cannot break that tie, because there is nothing left in it to
break the tie with.

The tie-breaker is the noise, not the signal

The two candidates have the same expected lift. What differs is how far each is
entitled to wander on its own.

A factor f divides a random distance with probability 1/f. Over D
distances that is a binomial, and after scaling by f the standard deviation of
the lift works out to sqrt((f−1)/D). Larger factors are noisier — of course
they are; they are estimating a rarer event from the same sample.

So measure each candidate in units of its own noise:

z(f) = (lift(f) − 1) / sqrt((f − 1) / D)

Substitute the two cases:

z(L)  = p·(L−1) / sqrt((L−1)/D)  = p·sqrt((L−1)·D)
z(kL) = p·(L−1) / sqrt((kL−1)/D) < z(L)      because kL − 1 > L − 1
z(d)  = p·(d−1) / sqrt((d−1)/D)  = p·sqrt((d−1)·D) < z(L)   because d < L

z(L) is strictly the maximum. Divisors lose because their lift is smaller;
multiples lose because their noise is larger. One formula, both failure
directions, and — the part I care about most — no tuned constants. The
previous version of this code had a hand-picked threshold and a "skip obvious
artefacts" list. Both are now gone, because the arithmetic does their job.

Results

Same engine, same prose, sweeping every key length from 2 to 16:

Sample	Exact hits
330 letters	12 / 15
698 letters	15 / 15
1,396 letters	15 / 15

The three misses at 330 letters are worth looking at, because of how they are
wrong. They are 5 answered as 15, 7 as 14, and 10 as 20 — every one a multiple
of the true length, never a divisor. That is the residue of the tie described
above: multiples match the true length exactly on lift, and at 330 letters there
is not enough data for the noise term to finish separating them. It is also the
benign direction to fail in. A multiple is consistent with the same distances
and splitting into 15 columns still recovers a 5-letter key, just with a third
of the data per column. A divisor is flatly wrong, and it no longer happens at
any sample size I have measured.

The one bug I would have shipped anyway

There was a second defect underneath, and it is worth naming because it is a
shape, not a fact about ciphers.

The old code ranked first, then walked the ranked list skipping artefacts. That
loop only ever demotes an artefact that appears after the real answer. So
whichever artefact happened to outrank the real answer got taken first, and the
rule that existed to catch exactly that never ran.

Reduce the field before you sort it, never during. I have now found this same
inverted-order bug in two separate tools in the same codebase.

Three things I would tell past me

Before ranking by a count, ask what each candidate scores for nothing, and divide it out. A leaderboard over quantities with different baselines is not a leaderboard.
Then ask how far that corrected figure wanders on its own, and divide that out too. Half the tie-breaks live in the variance, not the mean.
A hand-built fixture cannot test a statistic. Sweep the whole parameter range on real input. The arithmetic still deserves its unit test — just do not mistake that for a test of the statistic.

Try it

Both tools run entirely in the browser, no upload, no account:

Kasiski examination — shows the lift and the z-score for every factor, so you can see the ranking rather than trust it.
Index of coincidence calculator — the other route to key length, and a good cross-check. If Kasiski and the IC disagree, you have not found the key length yet.

Paste a Vigenère ciphertext into both. If they agree, split the text into that
many columns and each column is a plain Caesar shift, which
frequency analysis
finishes in a few seconds.

DEV Community: 이준김

Adaptive PNG filtering made my animations 2.4x bigger

Three explanations that sound right

The experiment that settles it

Why the heuristic cannot see this

The fix

The bug in the measurement, which is the part I would want to read

What I would take from this

A GIF re-encode made the file 4.5x bigger. Interframe differencing fixed it.

What it was throwing away

The fix

The heuristic that did not work

The trap worth knowing about

Results

Checking it against something that is not us

What it cost

Search Console found one 502. All 11 locales were broken, and no test could have caught it.

Why nothing told me

The bug is a child count

How a thrown renderer becomes a 502

The fix, and the one I did not choose

Three things I would do differently

Compressing an image to an exact file size, in the browser

The naive version, and why it is not good enough

Binary search over the quality space

best ?? smallest — the failure path is a real path

Monotonicity is an assumption, not a fact

PNG is a different problem entirely

The part that actually breaks the page

Transferables, and why this code deliberately does not use them

What this buys, and what it does not

You don't search for the key, you search for English: how cipher auto-solvers actually work

The scoring function is the secret, and single letters aren't enough

Cracking a monoalphabetic substitution (cryptogram)

Cracking a Vigenère without the keyword

When automatic solving struggles

The two-minute version

I shipped a Kasiski calculator with 21 passing tests. It got 3 of 5 key lengths wrong.

The tests were green and the tool was broken

Why the fixtures lied

What each factor scores for nothing

Lift fixes half of it, and creates the other half

The tie-breaker is the noise, not the signal

Results

The one bug I would have shipped anyway

Three things I would tell past me

Try it

`best ?? smallest` — the failure path is a real path