Я хочу, чтобы посетители моего сайта наслаждались им, так что я забочусь об accessibility и проверяю, что даже без JavaScript тут есть, на что смотреть. Я забочусь о том, насколько быстро грузятся страницы, ведь на некоторых из них есть большие иллюстрации, поэтому я минифицирую HTML.

Вот только есть один нюанс, который ставит мне палки в колёса и не даёт сделать блог лёгким как пёрышко.

Палка

Наиболее сильно уменьшает трафик (а значит и latency на мобильных устройствах!) не минификация, а сжатие. HTTP поддерживает gzip и Brotli через заголовок Content-Encoding. Сжатие отнимает ресурсы сервера, поэтому оно не всегда применяется, ведь отправка несжатых данных банально может быть быстрее.

Как правило, Brotli лучше, чем gzip, а gzip лучше, чем ничего. gzip настолько малозатратен, что он на серверах по умолчанию включен, а вот Brotli на порядок медленнее.

К несчастью, мой блог хостится на GitHub pages, который не поддерживает Brotli. Из-за этого Recovering garbled Bitcoin addresses, самый длинный пост у меня на сайте, занимает 92 килобайта вместо 37.

Лишний трафик, в 2.5 раза больше, чем нужно.

Неохота думать...

Нет причины, по которой GitHub не может поддерживать Brotli. Даже если сжатие файлов на лету не самое быстрое, GitHub мог бы дать владельцам репозиториев возможность заливать предварительно сжатые данные и их использовать.

GitHub, конечно же, этого не делает, но заранее сжатые данные можно просто положить в репу. Другое дело, что придётся руками разжимать их JS-ом на клиенте.

Как крутая разработчица, первым делом я пошла за решением проблемы в гугл. Быстрым поиском выловился brotli-dec-wasm — декомпрессор на WASM, укладывающийся в 200 килобайт. tiny-brotli-dec-wasm почти втрое меньше: 71 килобайт.

Ага, то есть имеем 92 килобайта с gzip против 37 + 71 килобайт с Brotli. Ну такоооооее....

Те же грабли

Так, а с чего это WASM вообще нужен? В браузере же должен быть декодер Brotli в HTTP-стеке. Неужели никакой APIшки нет?

Конечно же есть — Compression Streams API. Например, конструктор DecompressionStream принимает аргумент format, задокументированный как:

One of the following compression formats:

• "gzip"

  Decompress the stream using the GZIP format.

• "deflate"

  Decompress the stream using the DEFLATE algorithm in ZLIB Compressed Data Format. The ZLIB format includes a header with information about the compression method and the uncompressed size of the data, and a trailing checksum for verifying the integrity of the data

• "deflate-raw"

  Decompress the stream using the DEFLATE algorithm without a header and trailing checksum.

Хорошо, а где Brotli? А, его просто не добавили. Надеюсь, что вскоре с мёртвой точки сдвинутся, но все мы знаем, с какой медлительностью продвигаются такие вещи.

У меня в голове промелькнула мысль использовать gzip, но предварительное сжатие более эффективной библиотекой Zopfli выдаёт файл весом 86 килобайт, что всё ещё заметно хуже Brotli.

Во все тяжкие

У меня уже начали опускаться руки, но внезапно меня озарила демосценерская мудрость.

Браузеры умеют декодить картинки. Если положить данные в картинку и забрать их через Canvas API, и если сжатие без потерь и достаточно эффективное, будет профит.

Надеюсь, вы понимаете, к чему я тут клоню, и орёте "Да ты совсем рехнулась!" в монитор.

Простейший формат изображений со сжатием без потерь — GIF. GIF сканирует картинку по строкам и применяет к полученным данным LZW — алгоритм, которому сто лет в обед (1984). DEFLATE, используемый в gzip, придумали как раз на замену LZW, так что гифки тут не к месту.

PNG тоже использует DEFLATE, но, что важно, перед этим прогоняет данные через дополнительное преобразование. DEFLATE применяется не к сырым пикселям, а к разнице между соседними пикселями, например, к [a, b-a, c-b, d-c] вместо [a, b, c, d]. (Есть ещё другие, более изощрённые преобразования.) Это делает PNG предиктивным форматом: вместо сырых данных хранится разница от предсказания ("ошибка"), которая во многих случаях достаточно мала (ура, асимметричные вероятности, Хаффману заходит).

Ну только не это!

Победитель тут, несомненно, WebP, формат, который половина фанатиков нарекает исчадием ада, а другая — даром свыше. У WebP есть два варианта: с потерями и без, — использующие сильно отличающиеся алгоритмы. Речь тут пойдёт о VP8L, формате без потерь.

VP8L похож на PNG: он тоже использует предиктивное преобразование (чуть покруче, чем в PNG), но куда важнее то, что Google заменил DEFLATE на похожий самопальный формат.

DEFLATE позволяет нарезать файл на куски и использовать отдельные деревья Хаффмана для каждого куска. Оно и понятно: обычно данные не однородны, и у разных частей данных разные частоты встречаемости символов и ссылок на прошлые пиксели. Таким образом, JavaScript, SVG и разметка в одном HTML файле, скорее всего, будут использовать разные деревья.

В VP8L это тоже поддерживается, но со своей изюминкой: WebP позволяет заранее объявить сколько угодно различных деревьев Хаффмана и использовать своё дерево для каждого блока пикселей 16x16. Это важно, потому что позволяет переиспользовать деревья. То есть пока DEFLATE кодирует последовательность "JavaScript, CSS, потом опять JavaScript" тремя деревьями, хотя первое и третье из них очень похожи, VP8L спокойно обходится двумя. А ещё это улучшает локальность, потому что часто переключать деревья так дешевле.

Больше прекрасностей

Ещё одна крутая фича VP8L — "color cache". Вот наглядная демонстрация похожей техники:

Представьте, что вы разрабатываете очень тупое сжатие JSON. Вы хотите эффективно кодировать специльные символы: ", [, ], {, }, и прочие. Часто сказать "этот символ — маркер" достаточно, чтобы однозначно его восстановить. Например, в "s<MARKER> маркер совершенно точно ", а в [1, 2, 3<MARKER> это, очевидно, ].

Тут похожая идея: иногда вместо того, чтобы хранить весь пиксель, достаточно запомнить, что нам нужна копия последнего встреченного пикселя с определённым свойством (например, шестибитным хешом).

Поехали крышей!

В качестве бенчмарка я пока что возьму статью Recovering garbled Bitcoin addresses.

$ curl https://purplesyringa.moe/blog/recovering-garbled-bitcoin-addresses/ -o test.html

$ wc -c test.html
439478 test.html

$ gzip --best <test.html | wc -c
94683

Ок. Теперь по-быстрому протестим сжатие крейтом webp.

$ cargo add webp

fn main() {
    let binary_data = include_bytes!("../test.html");

    // Эээ... 1xN?
    let width = binary_data.len() as u32;
    let height = 1;

    // Перевод в оттенки серого
    let mut image_data: Vec<u8> = binary_data.iter().flat_map(|&b| [b, b, b]).collect();

    // Без потерь, качество 100 (лучшее сжатие)
    let compressed = webp::Encoder::from_rgb(&image_data, width, height)
        .encode_simple(true, 100.0)
        .expect("encoding failed");

    println!("Data length: {}", compressed.len());
    std::fs::write("compressed.webp", compressed.as_ref()).expect("failed to write");
}

Почему чёрно-белая картинка? WebP поддерживает преобразование "subtract green", при котором перед кодированием битмапов значение зелёного канала вычитается из красного и синего. В чёрно-белых изображениях это фактически обнуляет каналы R и B. WebP кодирует разные каналы разными деревьями Хаффмана, поэтому на однотонные каналы тратится места.

$ cargo run
thread 'main' panicked at src/main.rs:13:100:
encoding failed: VP8_ENC_ERROR_BAD_DIMENSION
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Ой... кажется, WebP умеет только в картинки до 16383x16383. Дадим ему такую.

fn main() {
    let binary_data = include_bytes!("../test.html");

    // Эээ... 16383xN?
    let width = 16383;
    let height = (binary_data.len() as u32).div_ceil(width);

    // Перевод в оттенки серого, дополняя данные до размера картинки
    let mut image_data: Vec<u8> = binary_data.iter().flat_map(|&b| [b, b, b]).collect();
    image_data.resize((width * height * 3) as usize, 0);

    // Без потерь, качество 100 (лучшее сжатие)
    let compressed = webp::Encoder::from_rgb(&image_data, width, height)
        .encode_simple(true, 100.0)
        .expect("encoding failed");

    println!("Data length: {}", compressed.len());
    std::fs::write("compressed.webp", &*compressed).expect("failed to write");
}

$ cargo run
Data length: 45604

Неплохо. Это уже в два раза меньше чем gzip, и даже круче bzip2 (49764 байт)!

Подгоны

Но мы можем сделать ещё лучше, если воспользуемся особенностями конкретно формата WebP.

Например, при использовании широкой картинки с порядком "по строкам" в блоках 16x16 оказываются байты, лежащие в файле далеко друг от друга: первые 16 пикселей берутся из первых 16 килобайт, вторые — из следующих, и так далее. Как насчёт высокой картинки?

// Эээ... Nx16383?
let height = 16383;
let width = (binary_data.len() as u32).div_ceil(height);
println!("Using {width}x{height}");

$ cargo run
Using 27x16383
Data length: 43232

Библиотека cwebp позволяет влиять на эффективность сжатия не только за счёт качества, но и заменой "метода". Пробуем:

// Без потерь, качество 100
let mut config = webp::WebPConfig::new().unwrap();
config.lossless = 1;
config.quality = 100.0;

for method in 0..=6 {
    // Пробуем разные "методы" (4 -- значение по умолчанию)
    config.method = method;
    let compressed = webp::Encoder::from_rgb(&image_data, width, height)
        .encode_advanced(&config)
        .expect("encoding failed");

    println!("Method {method}, data length: {}", compressed.len());
}

$ cargo run
Method 0, data length: 48902
Method 1, data length: 43546
Method 2, data length: 43442
Method 3, data length: 43292
Method 4, data length: 43232
Method 5, data length: 43182
Method 6, data length: 43182

Возьмём метод 5: он, кажется, не хуже чем 6, но быстрее.

Мы уже в 2.2 раза круче gzip, и всего в 1.2 раза хуже Brotli — для наших условий очень даже неплохо.

Бенчмарки

Давайте чисто по приколу протестируем наш формат на разных файлах. Я буду использовать тестовые данные snappy, Canterbury Corpus и Large Corpus, и две больших SVG-шки.

Для начала перепишу скрипт, чтобы его можно было засунуть в пайплайн:

use std::io::{Read, Write};

fn main() {
    let mut binary_data = Vec::new();
    std::io::stdin().read_to_end(&mut binary_data).expect("failed to read stdin");

    let width = (binary_data.len() as u32).div_ceil(16383);
    let height = (binary_data.len() as u32).div_ceil(width);

    // Перевод в оттенки серого, дополняя данные до размера картинки
    let mut image_data: Vec<u8> = binary_data.iter().flat_map(|&b| [b, b, b]).collect();
    image_data.resize((width * height * 3) as usize, 0);

    // Без потерь, качество 100, метод 5
    let mut config = webp::WebPConfig::new().unwrap();
    config.lossless = 1;
    config.quality = 100.0;
    config.method = 5;
    let compressed = webp::Encoder::from_rgb(&image_data, width, height)
        .encode_advanced(&config)
        .expect("encoding failed");

    std::io::stdout().write_all(&compressed).expect("failed to write to stdout");
}

(Ещё я слегка поменяла расчёт длины, чтобы он работал с разными размерами файлов.)

А теперь пришло время сравнить gzip, bzip2, brotli и webp на нашем корпусе:

#!/usr/bin/env bash
cd corpus

printf "%24s%8s%8s%8s%8s%8s\n" File Raw gzip brotli bzip2 webp
for file in *; do
    printf \
        "%24s%8d%8d%8d%8d%8d\n" \
        "$file" \
        $(<"$file" wc -c) \
        $(gzip --best <"$file" | wc -c) \
        $(brotli --best <"$file" | wc -c) \
        $(bzip2 --best <"$file" | wc -c) \
        $(../compressor/target/release/compressor <"$file" | wc -c)
done

Страшная таблица. Наглядно:

Сразу видно, что WebP почти всегда лучше gzip, кроме очень маленьких файлов (grammar.lsp и xargs.1), и ещё вот этих двух:

paper-100k.pdf — практически шум (в файле 19 килобайт XML, после чего куча уже сжатых данных, так что по факту мы тут уже измеряем сжатие маленьких файлов).

Сложно сказать, что не так с kennedy.xls. Ещё на этом файле очень странные относительные скорости у Brotli и bzip2. Я думаю, это потому, что в этом файле идёт подряд много разнородной информации, что оказывается слишком сложным для алгоритмов сжатия.

WebP работает в среднем чуть хуже bzip2: он обгоняет его в нескольких отдельных случаях и сливается в куче других. Оно и неудивительно: используются сильно разные алгоритмы, дающие разные результаты на разных данных.

Также ожидаемо, что WebP оказывается всегда хуже Brotli (кроме файла fireworks.jpeg с белым шумом, где звёзды решили сойтись). Тем не менее, WebP заметно лучше gzip на больших массивах текста, в том числе на SVG-шках, и больше всего на html_x_4, где он выдаёт степень сжатия 3.3% (хуже чем Brotli с его 2.8%, но куда лучше 13% от gzip).

В целом, кажется, WebP — неплохое решение для Веба.

JavaScript

С теорией разобрались, перейдём к "практическим" аспектам кодирования и декодирования.

WebP можно без особых проблем раскодировать через Canvas API:

<script type="module">
// Загружаем файл WebP
const result = await fetch("compressor/compressed.webp");
const blob = await result.blob();

// Раскодируем в RGBA
const bitmap = await createImageBitmap(blob);
const context = new OffscreenCanvas(bitmap.width, bitmap.height).getContext("2d");
context.drawImage(bitmap, 0, 0);
const pixels = context.getImageData(0, 0, bitmap.width, bitmap.height).data;

// Достаём из красного канала сырые байты HTML
const bytes = new Uint8Array(bitmap.width * bitmap.height);
for (let i = 0; i < bytes.length; i++) {
    bytes[i] = pixels[i * 4];
}

// Осталось декодировать UTF-8
const html = new TextDecoder().decode(bytes);

document.documentElement.innerHTML = html;
</script>

...в параллельной вселенной. Canvas API — ходовой инструмент фингерпринтинга, поэтому браузеры подложили нам свинью и гадят мусором в данные, которые возвращает getImageData.

Эти изменения почти незаметны. Если пройти по этой ссылке в Firefox со включённой "строгой" защитой от отслеживания, можно заметить, что заменяется меньше 1% пикселей. На практике это выглядит как опечатки в HTML, и я сначала подумала, что они настоящие.

Я презираю эту "защиту приватности". Мало того, что она ломает реальные юзкейсы (декодирование WebP никак не может зависеть от устройства), но оно ещё и бесполезно, поскольку добавление характерного (!) шума увеличивает, а не уменьшает уникальность отпечатков.

Я не понимаю почему, но если использовать WebGL, всё работает:

const bitmap = await createImageBitmap(blob);
const context = new OffscreenCanvas(bitmap.width, bitmap.height).getContext("webgl");
const texture = context.createTexture();
context.bindTexture(context.TEXTURE_2D, texture);
context.texImage2D(context.TEXTURE_2D, 0, context.RGBA, context.RGBA, context.UNSIGNED_BYTE, bitmap);
context.bindFramebuffer(context.FRAMEBUFFER, context.createFramebuffer());
context.framebufferTexture2D(context.FRAMEBUFFER, context.COLOR_ATTACHMENT0, context.TEXTURE_2D, texture, 0);
const pixels = new Uint8Array(bitmap.width * bitmap.height * 4);
context.readPixels(0, 0, bitmap.width, bitmap.height, context.RGBA, context.UNSIGNED_BYTE, pixels);
// Смотрите, никакого шума!

Нет, я не знаю, отчего readPixels не подвержен такому же анти-фингерпринтингу. Но он не создаёт по всей странице едва заметные опечатки, так что будем считать что это работает.

WebGL гарантированно поддерживает только текстуры до 2048x2048, так что некоторые ограничения придётся обновить.

В минифицированном виде этот код занимает где-то 550 байт. Вместе с самой картинкой WebP получается размер в 44 килобайта (Для сравнения: gzip сжал бы в 92 килобайта, а Brotli в 37).

Выдраивание

Вот чем мне не нравится это решение — так это долбаным мерцанием.

Поскольку await автоматически транслируется в код на промисах, браузер считает работу скрипта оконченной до того, как WebP загрузился. В DOM пока ничего нет, так что браузер ничтоже сумняшеся рисует пустую белую страницу.

Через сотню-другую миллисекунд, когда WebP таки подгружается, происходит парсинг HTML, загрузка CSS и вычисление стилей, правильный DOM отрисовывается на экране, заменяя собой пустоту.

Это можно очень просто исправить: достаточно положить стили и верхнюю часть страницы (примерно 8 килобайт в сжатом виде) в gzip'нутый HTML и сжимать через WebP только то, что находится за границей viewport'а. Перезагрузка страницы где-то внизу всё равно будет выглядеть по-наркомански, но этим хотя бы можно пользоваться.

Ещё одна неприятность есть с прокруткой. Обычно при обновлении страницы состояние скролла сохраняется, но теперь, если вы находитесь на Y = 5000px и обновите страницу, браузер загрузит страницу высотой 0px и позиция собьётся. Это можно исправить, если временно добавить очень высокий <div>. При этом важно использовать именно document.documentElement.innerHtml, а не document.write, потому что так можно обновить текущий документ, а не заменить его новым.

Встраивание

Наконец, попробуем ещё немного уменьшить задержку. Для этого встроим WebP прямо в HTML.

Самый простой способ это сделать — использовать data URL в формате base64. Но разве это не увеличит размер файла на треть? Да, увеличит, но gzip это увеличение практически полностью скомпенсирует:

$ wc -c compressed.webp 
43182 compressed.webp

$ base64 -w0 compressed.webp | wc -c
57576

$ base64 -w0 compressed.webp | gzip --best | wc -c
43519

Почему? Ну, поскольку WebP — сжатый файл, его можно считать белым шумом, и это свойство сохраняется после прогона base64, переводящего восемь бит в шесть. Дерево Хаффмана, полученное при применении gzip на белом шуме, фактически производит обратное преобразование из шестибитного формата в восьмибитный.

Можно было бы использовать Unicode и UTF-16 вместо base64, но иногда правильное решение приходит в голову первым.

Пример

(Прим. пер.: речь идёт об оригинальной статье на английском. Хабр не поддерживает выполнение JavaScript в статьях, поэтому этот перевод через WebP не закодирован. А жаль.)

Реальная веб-страница, сжатая через WebP? Как насчёт той, которую вы читаете прямо сейчас? Если только у вас не старый браузер или отключён JavaScript, всё содержимое, начиная с раздела "Те же грабли", было сжато через WebP. Если вы этого не заметили, значит мой трюк работает :-)

А, кстати, хотите посмотреть на этот WebP? Вот квадратный WebP с содержимым этой страницы:

На самом деле в коде используется высокое и узкое изображение, но на эту картинку смотреть приятнее.

Светлая часть вверху и в самом низу — текст и код. Полосатая часть на 20% по высоте — диаграмма. Тёмная часть, занимающая больше всего места — текст на диаграмме (да, там не используется шрифт).

Несколько ярких пикселей среди текста? Это символы Юникода, в основном знаки препинания вроде апострофа и троеточия.

На самом деле, сэкономили мы тут только на спичках: исходная версия, сжатая через gzip, занимает 88 килобайт, а версия, сжатая через WebP и gzip — 83 килобайта. При этом Brotli выдал бы 69 килобайт. Всё лучше чем ничего.

Ну и блин, прикольно же. Мне нравится прикалываться!

Ссылки

Код на Rust, корпус и некоторые другие файлы доступны на GitHub.
Если хотите, можете присоединиться к обсуждению на Reddit или на Hacker News.