The binary-search size cap, explained.

2026-04-22 · by alain

The problem.

Every GIF encoder hands you a quality slider, usually zero to one hundred. What the slider actually does varies by encoder — palette refinement passes, dither intensity, motion threshold — but the headline result is the same: higher number means bigger file.

The trouble is that the mapping from quality number to file size is not a constant. Quality 60 on a five-second static loop might produce a 400 KB GIF. Quality 60 on a thirty-second screen recording of a browser panning across a high-contrast dashboard might produce a 38 MB GIF. Same slider, same setting, two orders of magnitude of output. The slider doesn't know anything about your source, so it can't promise you anything about your output.

This is a real problem when your delivery constraint is a hard number. Slack caps free-tier uploads at 1 GB per file but rejects a lot of workplaces' custom limits much lower. GitHub PR comments top out at 10 MB per attachment. A README's "embedded demo GIF" budget is usually 5 MB before the repo starts feeling heavy. Your marketing team tells you "under 2 MB for the landing page." None of those numbers have anything to do with a quality slider. They're bytes — and you need the encoder to deliver bytes.

What most tools do.

Slider-and-pray. You pick a quality, you encode, you check the file size, you guess a new quality, you encode again. A 30-second 1080p clip might take 15–30 seconds per encode on a modern laptop, so three iterations is a minute and a half of babysitting just to get a GIF under a Slack attachment limit. Do that for ten clips and you've lost the afternoon.

The more sophisticated version is "encode, measure, rescale." You get a file, it's too big, you drop the resolution or frame rate and try again. This is the correct final move — gifcap does it too — but it's usually the first move in the typical workflow, which means you're throwing away resolution or frames before you've even found the best quality your source can hit under the cap.

What gifcap does.

gifcap binary-searches the quality axis. You type a target file size — 2 MB, 5 MB, 10 MB, whatever fits your constraint — and gifcap converges on the highest quality that lands under it. The algorithm is what you'd write on a whiteboard in ninety seconds:

lo = 1
hi = 100
best = None
while hi - lo > 1:
    mid = (lo + hi) // 2
    size = encode(mid)
    if size <= target:
        best = mid       # this quality fits — try higher
        lo = mid
    else:
        hi = mid         # this quality overshoots — try lower
return best

That's it. Log₂(100) is under seven, so seven iterations worst-case. In practice it's five to six, because file size versus quality is monotonic-enough that the search converges fast — bigger number means bigger file, so each probe at mid meaningfully halves the remaining search space.

The key property is that the function encode(q) → size is deterministic and (modulo a small amount of noise from threading) monotonic. Given the same source, the same fps, and the same scale, gifski's quality parameter maps reliably to file size. So binary search works. You don't need a gradient, you don't need gradient descent, you just need to probe the midpoint and decide which half to keep.

A linear scan over quality 1..100 would work too, but every probe is a full encode. Binary search gets you there in 6 probes instead of 50. On a 30-second clip that encodes in 12 seconds, that's 72 seconds instead of 600. Big difference.

A note on the monotonicity assumption. gifski quality does not produce strictly monotonic file sizes — quality 43 might produce 9.0 MB and quality 44 might produce 8.97 MB, because NeuQuant's color-quantization pass is sensitive to threshold numerics. The noise is tiny (under 1% in practice), and the search tolerates it fine: if probe N+1 comes in slightly under probe N, the algorithm still makes the right call about which half to keep. For the guarantee to hold, we just need encode(q1) < encode(q2) + epsilon for q1 < q2, not perfect monotonicity.

A worked example.

Say you have a 30-second screen recording at 1080p, 30 fps. You want it under 10 MB so it can go in a GitHub PR comment. gifcap starts with lo=1, hi=100.

• Probe 1: mid=50. Encode at quality 50. Result: 12 MB. Too big. hi=50.
• Probe 2: mid=25. Encode at quality 25. Result: 4 MB. Fits. lo=25, best=25.
• Probe 3: mid=37. Encode at quality 37. Result: 9 MB. Fits. lo=37, best=37.
• Probe 4: mid=43. Encode at quality 43. Result: 9.7 MB. Fits. lo=43, best=43.
• Probe 5: mid=46. Encode at quality 46. Result: 10.4 MB. Over. hi=46.
• Probe 6: mid=44. Encode at quality 44. Result: 9.9 MB. Fits. lo=44, best=44. Loop exits.

Six encodes, answer: quality 44 produces a 9.9 MB GIF. You never had to guess. The whole search took under two minutes on a laptop, and the output is as close to the 10 MB cap as gifski can get without going over. That's the same loop that runs when you use the "under 10 MB" preset, "under 5 MB", or "under 2 MB" — different targets, same algorithm.

Edge cases.

Even quality 1 overshoots. Some sources are too dense to fit under the cap at any quality — a two-minute 4K screen recording targeting 1 MB, for example. When gifcap hits encode(1) > target, quality has nothing left to give. gifcap falls back to scaling the other two knobs: drop the fps first (30 → 24 → 15 has a roughly linear effect on size), then drop the resolution (720p → 540p → 480p). Each step runs the binary search again at the new parameters until either the cap is met or the source is visibly degraded enough that gifcap surfaces a warning instead of silently shipping a bad GIF.

Absurdly small targets. 50 KB for a 30-second 4K clip isn't going to happen at a quality that looks like anything. gifcap surfaces that tradeoff in a preview before running the full search — "to hit 50 KB we'd need to drop to 240p, 10 fps, and quality 1, producing a GIF that will look rough." You can proceed anyway, or adjust the target. The point is that the tool tells you the constraint is the problem, not the encoder.

Sources that don't compress. High-entropy content (noise, film grain, random game footage) compresses poorly by nature. The binary search still finds the best quality that fits, but the output at that quality may dither heavily. Per the other post, gifski handles this better than single-palette ffmpeg because it can pick fresh colors per frame — but no encoder beats physics. If your source is noise, your GIF will have noise.

Ties and near-ties. Sometimes the binary search converges to two adjacent quality values with outputs a few kilobytes apart — say quality 43 at 9.6 MB and quality 44 at 10.2 MB for a 10 MB target. The loop picks 43 (the highest quality that fits) and stops. You can argue that 44 at 10.2 MB is "close enough" and maybe worth it, but the contract is "under the cap," not "close to the cap." Shipping 10.2 MB when you promised 10 MB is a bug. Shipping 9.6 MB when you promised under 10 MB is the feature.

Why this matters.

Determinism. Same source + same cap = same output, every time. That matters because GIF delivery constraints are almost always hard numbers — Slack's upload limit, an email attachment cap, a GitHub PR comment's 10 MB ceiling, a README budget, a marketing size brief. "My GIF fits under 10 MB" is a contract, not a vibe. The binary-search cap turns that contract into a guarantee.

Batch workflows. If you're running a batch of 50 MP4s that all need to land under one cap, the slider-and-pray loop is untenable — you'd hand-tune every clip. With a cap, you point gifcap at the folder, set the target, walk away. Every output lands under the cap or the tool tells you exactly which clip couldn't be compressed that far and why. The whole idea of compressing GIFs on Windows stops being a babysitting task and starts being a button.

Presets matter too. gifcap ships with 1 MB, 2 MB, and 5 MB defaults because those are the three numbers people actually hit — a tight social-post budget, a standard PR-comment limit, and a comfortable README cap. The binary search runs the same way regardless; the presets just name the targets so you don't have to. If your constraint is weirder (say, strictly under 2 MB for an in-app asset, or a custom number from a brief), type it directly and the algorithm takes the number as truth.

Try it.

gifcap is free to use. Drop a video, set a cap, get a GIF. Pro ($29 lifetime) adds scene detection — useful when the 30-second source is actually five different clips that each want their own GIF.