Формат JPEG XL будет полным по Тьюрингу без ограничения 1024*1024 пикселей

В формате JPEG XL это изображение занимает 59 байт ^[1]

Оказывается, полным по Тьюрингу ^[2] может быть не только язык программирования, но и графический формат. В частности, таким потенциально является формат JPEG XL ^[3], если отменить в нём ограничение на максимальный размер группы обрабатываемых пикселей.

Новый свободный формат разработан для замены существующим форматам растровой графики (JPEG, PNG, WebP, HEIC, JPEG 2000 и проч.), может работать на сервере прозрачно, вместе с JPEG ^[4] (уменьшение размера JPEG на 20% без потери качества). Финальная версия стандарта зафиксирована 25 декабря 2020 года. Новый кодек основан на инновационных разработках Google PIK ^[5] и Cloudinary FUIF ^[6], но превосходит их. Самое главное, что он лишён недостатков тех графических форматов, которые основаны на видеокодеках: это WebP (основан на VP8), HEIC (HEVC) и AVIF (AV1).

Пример использования JPEG XL на сервере

Полнота по Тьюрингу ^[2] — фундаментальное понятие в информатике. В теории вычислимости означает возможность реализовать на данном вычислителе любую вычислимую функцию. То есть для каждой вычислимой функции существует вычисляющий её элемент, а все функции являются вычислимыми. Свойство названо по имени Алана Тьюринга, разработавшего первый абстрактный исполнитель — машину Тьюринга, способную имитировать всех исполнителей путём ряда достаточно элементарных шагов.

Дело в том, что в формат изображений JPEG XL включает в себя так называемые «предикторы» — небольшие программы, которые улучшают сжатие, выражая цвет пикселя в терминах цветов его соседей.

В формате JPEG XL это изображение занимает 55 байт ^[7], hex-дамп: ff 0a fa 1f 01 91 08 06 01 00 ac 00 4b 38 42 36 61 47 a9 65 f3 43 ee 2f 2a 0e 7c f9 fd 73 90 70 e0 14 0f e9 82 32 f4 64 10 32 c9 90 02 59 91 0a 01 45 06 00 60 02 00

Украинский математик и программист Даниил Богдан, бывший ведущий инженер Института математики НАН Украины первым показал ^[8], что в предикторах JPEG XL можно реализовать клеточный автомат под названием «Правило 110». ^[9]

Ранее было доказано ^[10], что клеточный автомат с правилом 110 является Тьюринг-полным и с его помощью может быть реализована любая вычислительная процедура. Возможно, что это самая простая система, полная по Тьюрингу.

Построение следующего поколения одномерного клеточного автомата с использованием правила 110, cormullion ^[11]

Но есть один нюанс.

Хотя правило 110 является полным по Тьюрингу, но предикторы JPEG XL не являются полными по Тьюрингу сами по себе. Чтобы обеспечить параллельное кодирование и декодирование, кодек JPEG XL работает с «группами» пикселей размером до 1024х1024. Таким образом, сам JPEG XL не является полным по Тьюрингу, но его версия без ограничения 1024*1024 пикселей была бы полной, пишет Богдан.

Даниил Богдан написал код ^[12] в формате для предикторов JXL, который можно загрузить и запустить ^[13] в песочнице JXL Art.

В ответ на критику с Reddit ^[14] математик поясняет: «Мы можем генерировать любое начальное состояние с условиями на x для y = 0 (на одно условие меньше, чем существует непрерывных последовательностей нулей и единиц). Мы эмулируем бесконечно повторяющиеся серии правил и тактовых импульсов ^[15] с помощью серий, достаточно длинных для вычислений. Начинаем с фиксированных размеров, генерируем серию и запускаем вычисления. Если система тегов не останавливается, мы удваиваем размер изображения и повторяем попытку, пока она не остановится или у нас не закончится память. Это так же близко к Тьюринг-полноте, как и другие виртуальные машины на физическом компьютере (если я не прав, исправления приветствуются ^[16]!)».

Архитектура кодека JPEG XL

Основные функции JPEG XL

• Улучшенная функциональность и эффективность по сравнению с JPEG, GIF и PNG, см. сравнение JPEG XL с другими кодеками ^[17];
• Перекодирование JPEG без потерь с уменьшением размера примерно на 20%;
• Размер изображения более миллиарда (2³⁰-1) пикселей с каждой стороны;
• До 4100 каналов, т.е. оттенков серого или RGB, опционально альфа-канал, и до 4096 «дополнительных» каналов;
• Транскодирование прогрессивных JPEG поддерживается форматом, но пока не реализовано в эталонном ПО;
• Кодирование без потерь и альфа-кодирование без потерь;
• Поддержка как фотографических, так и синтетических изображений;
  плавное снижение качества в широком диапазоне битрейтов;
• Оптимизированный для восприятия эталонный кодер;
• Поддержка широкой цветовой гаммы и HDR;
• Поддержка анимаций;
• JPEG XL кодируется и декодируется так же быстро, как старый JPEG с использованием libjpeg-turbo, и на порядок быстрее HEIC с x265. Он также поддаётся распараллеливанию.
• Формат совершенно свободный с эталонной реализацией и открытым исходным кодом.

По субъективной оценке качества, JPEG XL сжимает без визуальных потерь (синяя область) на тех же битрейтах, что HEVC-HM-Y444

P.S. Есть мнение, что полнота по Тьюрингу окружает нас повсюду ^[18]. Вообще трудно написать полезную систему, которая немедленно не обратится в полную по Тьюрингу. Оказывается, что даже небольшой контроль над входными данными и преобразованием их в результат, как правило, позволяет создать тьюринг-полную систему: «В обычном смартфоне или настольном компьютере будет от пятнадцати до нескольких тысяч компьютеров в смысле тьюринг-полных устройств. Каждое из них можно запрограммировать, оно обладает достаточной мощностью для запуска многих программ и может быть использовано злоумышленником для наблюдения, эксфильтрации или атак на остальную часть системы», — писал ^[19] в 2018 году американский исследователь Гверн Бранвен, приводя множество примеров:

«Наверное, в наше время многие не знают, что TrueType и многие шрифты — это программы PostScript на стековых машинах, похожие на метаданные ELF и отладочную информацию DWARF ^[19]. Или что некоторые музыкальные форматы ^[20] выходят за рамки MIDI ^[21], поддерживают скрипты и нуждаются в интерпретации. Если знать о тьюринг-полноте шрифтов, то уже не удивляет полнота по Тюрингу документов TeX, что естественно вызывает многие серьёзные и интересные уязвимости в безопасности шрифтов и медиа, такие как BLEND ^[22] или Linux-эксплоиты SNES ^[23] и NES ^[24].

Несмотря на полноту по Тьюрингу, похоже, декодер JPEG XL не представляет угрозы безопасности ^[25]: говорят, что вычисления ограничены отдельными пикселями и не позволят декодеру уйти в бесконечный цикл или нечто подобное.

Автор: ITSumma

Источник ^[26]