Сначала немного не по теме.

Все файлы на виртуалку я переношу через образ дискеты и перво-наперво несколько слов о том как создать образ дискеты на «Маке». Мне необходимо куда-то записать эту информацию, иначе она у меня постоянно теряется. Из командной строки это делается так:

dd if=/dev/zero of=floppy.img bs=1024 count=1440
diskutil eraseVolume MS-DOS VOLUME `hdiutil attach -nomount floppy.img`
hdiutil attach floppy.img

Последняя команда смонтирует получившийся образ, после чего можно записать туда любые файлы.

Как справедливо напомнили читатели в комментариях к моему эксперименту c ARJ, в 90-е чемпионом по сжатию был архиватор HA (с алгоритмом PPM). Он был очень медленным по тем временам (помню DOOM сжимался за часы) и поэтому не слишком распространённым, но я с ним сталкивался.

Успехи архиватора HA — 23,7% исходного объёма

Для тестирования я выбрал форк архиватора, с которым сталкивался во времена интереса к языку программирования Си-​-. Форк быстрее оригинала в 1,5 раза, впрочем, как оказалось, сейчас это вряд ли имеет значение — сжатие файла из вчерашнего теста заняло малозаметное время.

214962-байтный файл сжался в 51088 байт, это 23,8% от исходного объёма. Это лучше современного xz с его 25,4 процентами, но по-прежнему хуже архиватора Compressia с его космическими 20,6%!

Что-то меня потянуло на разную околокомпьютерную древность.

Пока экспериментировал с арифметическим кодированием, как-то сами собой вспомнились различные архиваторы времён ДОСа, но больше всего почему-то ARJ, который в «Иркеннефти», где я иногда в летние каникулы работал в детстве, называли «а-эр-йот».

Один из рассказов Анджея Земянского, сжатый «а-эр-йодом» в экране «Волкова Коммандера»

Захотелось его сравнить с чем-нибудь современным.

Скачал виртуальную машину с MS-DOS 6.22, установил туда ARJ 2.21 (это версия сентября 1991 года) и попробовал посмотреть насколько уменьшится один из рассказов Анджея Земянского — первый попавшийся текстовый файл, который был у меня на компьютере.

В итоге файл размером 214962 байт ужался до 67634, это 31,5% исходного объёма. Современный архиватор xz 5.4.2 на максималках (использует алгоритмы LZMA и LZMA2) ужал тот же файл до 54648 байт, это 25,4% исходного объёма. Вроде неплохой прогресс.

Архиватор 2003-го года уделывает современный xz, как Тузик грелку

Но потом я вспомнил, что где-то в сети существует таблица сравнения архиваторов за 2002-й год. Победителя нагуглить не удалось, зато архиватор «Compressia», который находится строчкой ниже, нашёлся на «ВебАрхиве». Он смог сжать тот же файл до 44361 байт, что составляет 20,6% исходного файла. А это архиватор 2003-го года (я скачал последнюю версию — 1.0b)!

Всё как обычно — есть популярные продукты, а есть почти неизвестные программы, которые в тёмном углу пилят какие-то одиночки. Любопытно — как обстоят дела в этом пыльном углу в этом году, каких успехов добились такие малоизвестные архиваторы?

Редактор «ГИМП» умеет открывать джейпеги с арифметическим кодированием

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

Производители то ли осторожничают, то ли так и не сделали внутри своих продуктов некие абстракции, которые бы позволили быстро внедрять любые декодеры форматов.

WebP едва появился в большинстве браузеров, а уже предлагается добавить поддержку BPG и FLIF. На фоне этой всей движухи неясно почему почти никто не обращает внимание на арифметическое кодирование в старом-добром джейпеге.

Этот метод кодирования изначально был защищён патентами компании «АйБиЭм» и поэтому декодеры его не реализовывали, но несколько лет назад патенты истекли и теперь вполне можно было бы добавить его в браузеры, жаль, что пока никто этого не сделал.

Эксперимент по использованию различных оптимизаторов джейпега

Меня привлекают в арифметическом кодировании две вещи: почти моментальная скорость преобразования без потерь из «традиционного» джейпега и бо́льшая эффективность кодирования.

Для эксперимента я взял первый попавшийся джейпег, который лежал у меня в папке «Загрузки» и попробовал сравнить результат арифметического кодирования и другие методы оптимизации в различных сочетаниях. На скриншоте выше example0 — исходный файл, example1 и example2 — результаты арифметического кодирования, остальные файлы применением других оптимизаций.

В эксперименте использовались даже те оптимизаторы, которые работают минутами, они давали превосходные результаты относительно исходного образца, но арифметическое кодирование так и не побили.

Несколько лет назад программа «айТерм2» (iTerm2, терминал для «Мака») обзавелась поддержкой графики в командной строке. Сильной необходимости в ней нет, но иногда это удобно — можно посмотреть картинку на удалённом сервере, не выкачивая её себе.

Вообще уже очень давно существует формат «Сиксел», рождённый в незапамятные времена компанией «ДЭК» (DEC), его даже поддерживают некоторые терминалы, но он значительно сложнее придуманного авторами «айТерма2».

Я это знаю, так как когда-то разобрался в обоих форматах и даже побаловался с тем, что придумали в «айТерме2» — написал программу на «баше», где нарисованный глаз следил за курсором мыши в терминале.

Картинку с надписью «HELLO» видно сразу и в графической среде, и в терминале

В общем виде тот и другой форматы представляют собой управляющие последовательности, после которых передаётся закодированная картинка.

Мне тут подумалось, что было бы интересно попробовать вставить внутрь настоящей картинки её закодированную копию, чтобы при попытке вывода её в консоль в виде текста, в терминал попадали управляющие коды и на экран выводился не бинарный мусор, а картинка.

Для этого я нарисовал небольшой ГИФ и вставил закодированную картинку после изображения следующей командой:

cat test.gif \
    <(echo -ne "\033[3F\033[J\033]1337;File=inline=1:") \
    <(base64 test.gif) \
    <(printf "\a")\
> test2.gif

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

В данном случае я сначала двигаю курсор на три строки вверх (столько занимает бинарный мусор на экране), потом произвожу очистку от курсора до конца экрана.

Теперь буду пугать наших системных администраторов картинкой, которую видно сразу и в терминале, при выводе командой cat, и в графическом интерфейсе.

68. DC — программа для арифметических вычислений с произвольной точностью в Юникс-системах, это одна из старейших программ, старше языка «Си». Представляет собой стековый калькулятор с обратной польской записью.

Поддерживаются 256 стековых регистров и основной стек программы. На стеках могут размещаться числа и строки, последние могут исполняться, как подпрограммы. Команды однобуквенные, некоторые имеют операнд; числа записываются как есть, строки — между квадратными скобками.

Компактно «песню о пиве» можно записать таким кодом:

[n10P]su[[s]P]ss[[No bottles]Plon2+Q]sn
[d0=ndn[ bottle]n1!=slon]sb[ of beer]so
[ddlbx[ on the wall, ]nlbx[.]lux
[Take one down and pass it around,]lux
1-dlbx[ on the wall.]lux[]luxd0!=B]sB
99lBx
[No more bottles of beer on the wall, no more bottles of beer.
Go to the store and buy some more, 99 bottles of beer on the wall.
] n

А вот вариант с комментариями (которые, правда, не делают программу уж сильно понятнее):

# beer.dc
# Степанищев Е. В. bolknote.ru

# Печать с переводом строки, мне не нравится помещать
# его в строку символом — ломаются отступы
[
	n 10 P
] su

# Печатаем «s»
[
	[s] P
] ss

# Печатаем «No bottles of beer», убираем (сложением) ноль со стека,
# прерываем выполнение родителя (выходим из двух уровней)
[
	[No bottles] P lon
	2+Q
] sn

# Вывод кол-ва бутылок с «bottle(s) of beer»
[
	d 0 =n
	d n [ bottle] n 1 !=s lon
] sb

# « of beer» — в регистр «о», будем использовать
# для вывода части фразы
[ of beer] so

# основной цикл программы (вызывается рекурсивно)
[
	d

	d lbx [ on the wall, ] n lbx [.] lux
	[Take one down and pass it around,] lux

	1-
	d lbx [ on the wall.] lux [] lux

	d 0 !=B
] sB

99 lBx

[No more bottles of beer on the wall, no more bottles of beer.
Go to the store and buy some more, 99 bottles of beer on the wall.
] n

Версия 7.4 интерпретатора ПХП, которая должна появиться осенью, смотрится очень привлекательно. Одни только стрелочные функции чего стоят — код будет выглядеть куда компактнее.

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

$f = 'magic';
($f = fn() => var_dump($f))();

Я ожидал, что в данном случае функция выведет своё представление, но на самом деле выводится слово «magic». Определённая логика тут есть конечно, — сначала создаётся тело функции, вместе с замыканием всех используемых переменных в локальной зоне видимости, и только потом получившееся присваивается переменной.

Впрочем, после непродолжительных экспериментов обнаружилось, что функцию внутри себя можно получить, если передать её как параметр. Не очень изящно, но работает:

$f = 'magic';
($f = fn($f) => var_dump($f))($f);

Вот практическое использование рекурсии со стрелочными функциями на примере программы, генерирующей SBox для ГОСТовых алгоритмов:

$k=fn($i)=>ord('@`rFTDVbpPBvdtfR@¬p?â>4¦é{zãq5§è'[$i]);$p=fn($x)=>($f=fn($x,$f,$l=256)=>
--$l*$x^$l?$f($x+$x^($x>>7)*285,$f,$l):($l%17?$k($l%17)^$k(17+$l/17)^17:$k($l/17)^188))($x,$f);

Кстати, неделю назад началось соревнование по написанию самой короткой версии такой программы, рекорд на настоящий момент — 58 символов. У меня получилось 183, но за размером я не гнался, ПХП чересчур многословен для такого, было интересно сам синтаксис погонять.

67. Юᓂ곧⎔ — эзотерический язык программирования, кратко описанный в пятничном посте в блоге кандидата математических наук Дэвида Мадора. Основная идея — придумать язык, обфусцированный ресурсами Юникода.

Недавно появился транслятор из «Юᓂ곧⎔» в Си, благодаря чему можно писать и запускать программы на этом необычном языке.

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

Несмотря на это, писать не особо сложно — можно быстренько накидать требуемое в Си, а потом перевести программу в «Юᓂ곧⎔», подсмотрев правила в трансляторе. Из-за этого можно мухлевать, например я разбил длинные строки слешами, потому что так позволяется делать в Си, в который в конечном счёте превратится программа.

Интересно как смотрится программа под разными операционными системами. «МакОС», насколько я могу судить, отображает всё корректно.

❝99.⎔❞
ℤбутылок «ℤぶ»
☹
	¿«ぶ ⇔ ☰» писать «“⁌☱☵☶⁍⁌☱☵☷⁍⁌☴☰⁍”»।
	¬писать «“﹪ℤ⁌☴☰⁍” ¦ ぶ»।

	писать «“⁌☱☴☲⁍⁌☱☵☷⁍⁌☱☶☴⁍⁌☱☶☴⁍⁌☱☵☴⁍⁌☱☴☵⁍”»।

	¿«ぶ ⇔ ☱»।¬писать «“⁌☱☶☳⁍”»।
☺

⌂ «»
☹
	∀«ቁምፊ 工 ← ᠙᠙। 工 ≩ ☰। ∇工»
	☹
		бутылок «工»।
		писать «“⁌☴☰⁍⁌☱☵☷⁍⁌☱☴☶⁍⁌☴☰⁍⁌☱☴☲⁍⁌☱☴☵⁍⁌☱☴☵⁍⁌☱☶☲⁍⁌☴☰⁍\
⁌☱☵☷⁍⁌☱☵☶⁍⁌☴☰⁍⁌☱☶☴⁍⁌☱☵☰⁍⁌☱☴☵⁍⁌☴☰⁍⁌☱☶☷⁍⁌☱☴☱⁍⁌☱☵☴⁍⁌☱☵☴⁍⁌☵☴⁍⁌☴☰⁍”»।
		бутылок «工»।
		писать «“⁌☴☰⁍⁌☱☵☷⁍⁌☱☴☶⁍⁌☴☰⁍⁌☱☴☲⁍⁌☱☴☵⁍⁌☱☴☵⁍⁌☱☶☲⁍⁌☵☶⁍␊”»।
		писать «“⁌☱☲☴⁍⁌☱☴☱⁍⁌☱☵☳⁍⁌☱☴☵⁍⁌☴☰⁍⁌☱☵☷⁍⁌☱☵☶⁍⁌☱☴☵⁍⁌☴☰⁍\
⁌☱☴☴⁍⁌☱☵☷⁍⁌☱☶☷⁍⁌☱☵☶⁍⁌☴☰⁍⁌☱☴☱⁍⁌☱☵☶⁍⁌☱☴☴⁍⁌☴☰⁍⁌☱☶☰⁍⁌☱☴☱⁍⁌☱☶☳⁍\
⁌☱☶☳⁍⁌☴☰⁍⁌☱☵☱⁍⁌☱☶☴⁍⁌☴☰⁍⁌☱☴☱⁍⁌☱☶☲⁍⁌☱☵☷⁍⁌☱☶☵⁍⁌☱☵☶⁍⁌☱☴☴⁍⁌☵☴⁍⁌☴☰⁍”»।
		бутылок «工−᠑»।
		писать «“⁌☴☰⁍⁌☱☵☷⁍⁌☱☴☶⁍⁌☴☰⁍⁌☱☴☲⁍⁌☱☴☵⁍⁌☱☴☵⁍⁌☱☶☲⁍⁌☴☰⁍\
⁌☱☵☷⁍⁌☱☵☶⁍⁌☴☰⁍⁌☱☶☴⁍⁌☱☵☰⁍⁌☱☴☵⁍⁌☴☰⁍⁌☱☶☷⁍⁌☱☴☱⁍⁌☱☵☴⁍⁌☱☵☴⁍⁌☵☶⁍␊␊”»।
	☺

	писать «“⁌☱☱☶⁍⁌☱☵☷⁍⁌☴☰⁍⁌☱☵☵⁍⁌☱☵☷⁍⁌☱☶☲⁍⁌☱☴☵⁍⁌☴☰⁍⁌☱☴☲⁍⁌☱☵☷⁍\
⁌☱☶☴⁍⁌☱☶☴⁍⁌☱☵☴⁍⁌☱☴☵⁍⁌☱☶☳⁍⁌☴☰⁍⁌☱☵☷⁍⁌☱☴☶⁍⁌☴☰⁍⁌☱☴☲⁍⁌☱☴☵⁍⁌☱☴☵⁍\
⁌☱☶☲⁍⁌☴☰⁍⁌☱☵☷⁍⁌☱☵☶⁍⁌☴☰⁍⁌☱☶☴⁍⁌☱☵☰⁍⁌☱☴☵⁍⁌☴☰⁍⁌☱☶☷⁍⁌☱☴☱⁍⁌☱☵☴⁍⁌☱☵☴⁍\
⁌☵☴⁍⁌☴☰⁍⁌☱☵☶⁍⁌☱☵☷⁍⁌☴☰⁍⁌☱☵☵⁍⁌☱☵☷⁍⁌☱☶☲⁍⁌☱☴☵⁍⁌☴☰⁍⁌☱☴☲⁍⁌☱☵☷⁍⁌☱☶☴⁍\
⁌☱☶☴⁍⁌☱☵☴⁍⁌☱☴☵⁍⁌☱☶☳⁍⁌☴☰⁍⁌☱☵☷⁍⁌☱☴☶⁍⁌☴☰⁍⁌☱☴☲⁍⁌☱☴☵⁍⁌☱☴☵⁍⁌☱☶☲⁍⁌☵☶⁍␊”»।
	писать «“⁌☱☰☷⁍⁌☱☵☷⁍⁌☴☰⁍⁌☱☶☴⁍⁌☱☵☷⁍⁌☴☰⁍⁌☱☶☴⁍⁌☱☵☰⁍⁌☱☴☵⁍⁌☴☰⁍⁌☱☶☳⁍\
⁌☱☶☴⁍⁌☱☵☷⁍⁌☱☶☲⁍⁌☱☴☵⁍⁌☴☰⁍⁌☱☴☱⁍⁌☱☵☶⁍⁌☱☴☴⁍⁌☴☰⁍⁌☱☴☲⁍⁌☱☶☵⁍⁌☱☷☱⁍⁌☴☰⁍\
⁌☱☶☳⁍⁌☱☵☷⁍⁌☱☵☵⁍⁌☱☴☵⁍⁌☴☰⁍⁌☱☵☵⁍⁌☱☵☷⁍⁌☱☶☲⁍⁌☱☴☵⁍⁌☵☴⁍⁌☴☰⁍⁌☷☱⁍⁌☷☱⁍⁌☴☰⁍\
⁌☱☴☲⁍⁌☱☵☷⁍⁌☱☶☴⁍⁌☱☶☴⁍⁌☱☵☴⁍⁌☱☴☵⁍⁌☱☶☳⁍⁌☴☰⁍⁌☱☵☷⁍⁌☱☴☶⁍⁌☴☰⁍⁌☱☴☲⁍⁌☱☴☵⁍\
⁌☱☴☵⁍⁌☱☶☲⁍⁌☴☰⁍⁌☱☵☷⁍⁌☱☵☶⁍⁌☴☰⁍⁌☱☶☴⁍⁌☱☵☰⁍⁌☱☴☵⁍⁌☴☰⁍⁌☱☶☷⁍⁌☱☴☱⁍⁌☱☵☴⁍⁌☱☵☴⁍⁌☵☶⁍”»।
☺

По случаю получил доступ к оборудованию на процессорах POWER8 и, в качестве домашнего проекта, попробовал развернуть там один из наших продуктов. Оказалось, для этого требуется немалое количество стороннего софта, до этого момента я даже не представлял себе насколько немалое. В стандартных репозиториях кое-что нашлось, но всё равно пришлось собирать собственные пакеты, более сотни штук.

Хорошо, что для бо́льшей части существуют SRPM, но несколько десятков пакетов всё же пришлось собрать полностью вручную — разбираться что они должны содержать, компилировать необходимое, писать спецификацию.

В последнем случае меня несколько раз выручил придуманный по ходу дела трюк.

Если пакет существует для другой архитектуры, то черновую спецификацию для него можно получить через утилитку rpmrebuild. Она предназначена для создания RPM из уже установленного пакета и умеет создавать спецификации автоматически.

Требуемый пакет нужно сначала установить на машину с той архитектурой, для которой он существует, а потом вытянуть из rpmrebuild сгенерированную спецификацию. Пример для пакета php-pecl-imagick:

echo|EDITOR=cat rpmrebuild -e php-pecl-imagick 2>&- > /tmp/php-pecl-imagick.spec

Для того, чтобы достать спецификацию, приходится вызвать её на редактирование с заменой редактора на команду cat. Более простого способа я не обнаружил.

Потом остаётся только скомпилировать нужный софт на POWER8, поменять внутри спецификации платформу, выкинуть мусор и подсунуть её утилите rpmbuild; по сообщениям об ошибках можно понять куда и что из скомпилированного требуется положить.

При желании это можно было бы даже автоматизировать, но я на это силы тратить не стал, не терпелось увидеть результат. В итоге, функциональное тестирование показало, что всё работает без ошибок.

Мы с коллегами сейчас проходим курс по машинному обучению, организованный для нас университетом Иннополиса. Курс рассчитан на два месяца, к настоящему моменту мы бегло пробежались по высшей математике и начали изучать Пайтон — один из языков, популярных в машинном обучении.

По Пайтону соскучился — он мне нравится, а я всерьёз не программировал на нём несколько лет. С удовольствием смотрю что наворотили в третьей версии, которую я почти не трогал. Бо́льшая часть языка легко и почти сразу вспоминается, но долгое отсутствие практики всё же сказывается.

Решали сегодня задачки из «Проекта Эйлер», в частности 67-ю задачу. Суть её такова, вкратце. Дан треугольник чисел, нужно найти в нём максимальную сумму, из всех, что получаются, если двигаться сверху по соседям ниже. Посмотрите задачу, там картинка есть, всё понятно.

from functools import reduce

def read():
    with open('p067_triangle.txt') as f:
        for line in f.readlines()[::-1]:
            yield tuple(int(x) for x in line.strip().split(' '))

reduce(lambda cur, prv: [max(cur[pos:pos+2])+v for pos, v in enumerate(prv)], read())

Пока решали, преподаватель упомянул, что задачу можно решить через фолдинг. Я загорелся идеей — настолько не умею обращаться с фолдингом, что ни разу не сумел его где-то приспособить.

Результат мозговых усилий выше. Код сократился до одной строки (функция над ней — просто чтение данных).

Наверное хорошо бы порешать подобные задачи — которые гарантированно изящно решаются через фолдинг, чтобы плотнее уложить концепцию на извилины, но не знаю где такие задачки можно было бы взять. Впрочем есть и другой путь — начать всё-таки изучать Хаскель, там, по слухам, подобные вещи в ходу.

На закуску вот вам фолдинг на «Баше», взятый из комментария со «Стека Оверфлоу»:

foldl() {
    echo $(($(</dev/stdin)$2))
} < <(tr '\n' "$1" <$3)

# Sum 20 random ints from 0-999
foldl + 0 <(while ((n=RANDOM%999,x++<20)); do echo $n; done)

Тут суммируются двадцать псевдослучайных чисел из диапазона 0—999.