"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.
Top comments (0)