Сдержать LZMA2 сжатие

11

Цель

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

Цели

Методы сжатия

  • Ubuntu / связанные: xz -kz5 <infile>
  • Окна: 7z.exe a -txz -mx5 <outfile> <infile>
  • Другое: Используйте компрессор LZMA2 с уровнем сжатия 5, который сжимает произведения Шекспира до 1570550 байт ± 100 байт.

Подсчет очков; сумма (все в байтах, ls -lили dirэто):

  • Размер программы (ов) (все, что нужно, чтобы обратимо «сломать» / исправить файл)
  • Разница в размере (абсолютная) между:
    • Сырые собранные произведения Шекспира и ваша модифицированная (несжатая) копия.
    • Необработанное фото и ваша измененная (несжатая) копия.
  • Разница в размере или 0, в зависимости от того, что больше между:
    • Необработанные произведения Шекспира без вашей модифицированной сжатой копии LZMA2.
    • Необработанное фото без вашей модифицированной сжатой копии LZMA2.

пример

Плохо выигрывающий, лениво играющий в гольф, но совместимый пример Python 2.x:

import sys
x = 7919 if sys.argv[1] == 'b' else -7919
i = bytearray(open(sys.argv[2], 'rb').read())
for n in range(len(i)):
    i[n] = (i[n] + x*n) % 256
o = open(sys.argv[2]+'~', 'wb').write(i)

Бег...

$ python break.py b pg100.txt 
$ python break.py f pg100.txt~ 
$ diff -s pg100.txt pg100.txt~~
Files pg100.txt and pg100.txt~~ are identical
$ python break.py b Glühwendel_brennt_durch.jpg 
$ python break.py f Glühwendel_brennt_durch.jpg~
$ diff -s Glühwendel_brennt_durch.jpg Glühwendel_brennt_durch.jpg~~
Files Glühwendel_brennt_durch.jpg and Glühwendel_brennt_durch.jpg~~ are identical
$ xz -kz5 pg100.txt~
$ xz -kz5 Glühwendel_brennt_durch.jpg~
$ ls -ln
-rw-rw-r-- 1 2092 2092     194 May 23 17:37 break.py
-rw-rw-r-- 1 2092 2092 1659874 May 23 16:20 Glühwendel_brennt_durch.jpg
-rw-rw-r-- 1 2092 2092 1659874 May 23 17:39 Glühwendel_brennt_durch.jpg~
-rw-rw-r-- 1 2092 2092 1659874 May 23 17:39 Glühwendel_brennt_durch.jpg~~
-rw-rw-r-- 1 2092 2092 1646556 May 23 17:39 Glühwendel_brennt_durch.jpg~.xz
-rw-rw-r-- 1 2092 2092 5589891 May 23 17:24 pg100.txt
-rw-rw-r-- 1 2092 2092 5589891 May 23 17:39 pg100.txt~
-rw-rw-r-- 1 2092 2092 5589891 May 23 17:39 pg100.txt~~
-rw-rw-r-- 1 2092 2092 3014136 May 23 17:39 pg100.txt~.xz

Гол

  • = 194 + абс (5589891 - 5589891) + макс (5589891 - 3014136, 0) + абс (1659874 - 1659874) + макс (1659874 - 1646556, 0)
  • = 194 + 0 + 2575755 + 0 + 13318
  • 2 589 267 байт. Плохо, но ничего не делая с файлами, получается оценка 4 635 153 байта.

осветление

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

  • исходный код
  • Разница между несжатым измененным файлом и исходным файлом (например, если вы измените его, добавив триллион 0 в конце, ваш счет увеличится на триллион байт)
  • Разница между сжатым измененным файлом и исходным файлом (например, чем более несжимаемыми становятся файлы, тем выше ваша оценка). Совершенно несжимаемый файл, который немного увеличивается или не увеличивается вообще, получит 0.
code-challenge compression Ник Т
источник
2
Ответ троллинга: Шаг 1 - определите, сколько у вас свободного дискового пространства, затем разделите его на размер файла, чтобы получить N. Шаг 2 - добавьте файл к себе N раз и добавьте число N. Шаг 3 - поймите, что есть нет места для сжатия файла, но в итоге получается абсолютная разница в размерах файлов в несколько терабайт (или больше) .... [Чтобы перевернуть, прочитайте N с конца файла и сократите файл до 1 / Nth размера. ]
MT0
@ Mt0: А я думаю , что решение различие должно не быть абсолютным. Если ваш измененный файл больше, это должно вычесть очки.
Клаудиу
@ MT0, если вы измените файл так, чтобы он стал больше терабайта, тогда ваш счет будет 1 терабайт ... очень плохо, когда вы пытаетесь играть в гольф.
Ник Т
@ MT0 Я добавил пояснение к посту, это помогает?
Ник Т
2
Один обман. Компрессор может создать файл большего размера, если t особенно несжимаем. В этом случае вы должны быть вознаграждены, а не наказаны, нет?
Клавдиу

Ответы:

8

Python, оценка = 120

import sys,hashlib
i=0
for c in sys.stdin.read():sys.stdout.write(chr(ord(c)^ord(hashlib.md5(str(i)).digest()[0])));i+=1

Делает одноразовый пэд с использованием md5 в режиме счетчика . xors файл с этим. Преимущество заключается в том, что исходные и поврежденные файлы имеют одинаковый размер, а средства для разрушения и исправления - это одна и та же программа.

Сжатые испорченные файлы больше оригиналов.

Кит Рэндалл
источник
Я настроил оценку так, что если заархивированные файлы больше, чем их исходные копии, вы не будете оштрафованы, и они просто наберут 0. Не уверены, какова разница между вашими файлами, но вы можете обновить счет
Ник Т
@NickT: обновлено.
Кит Рэндалл
8

С 51 = 51 + 0 + 0 + 0 + 0

main(c){for(;c=~getchar();putchar(~c^rand()>>23));}

Под трюками игры в гольф эта программа зацикливается на каждый байт в стандартном вводе и делает эксклюзив - или с бесконечным пэдом из rand (). Я проверял это с помощью rand () в libc OpenBSD 5.5.

Использование:

./scramble <orig >scrambled
./scramble <scrambled >orig.copy

Чтобы протестировать свою программу, я написал сценарий оболочки test.sh (57 строк), чтобы скомпилировать мою программу и вычислить мой счет.

$ sh test.sh
[1/4] Compiling scramble...
/tmp//ccbcB43x.o(.text+0x6): In function `main':
: warning: rand() isn't random; consider using arc4random()
[2/4] Scrambling files...
[3/4] Compressing scrambled files...
[4/4] Checking descrambler...
SCORE: 51=51+0+0+0+0
You may wish to rm -rf tmp.9Tjw89dgCs
$ ls -l tmp.9Tjw89dgCs/
total 43032
-rw-r--r--  1 kernigh  kernigh  1659874 May 28 17:23 filament.jpg.cp
-rw-r--r--  1 kernigh  kernigh  1659874 May 28 17:23 filament.jpg.sc
-rw-r--r--  1 kernigh  kernigh  1660016 May 28 17:23 filament.jpg.sc.xz
-rw-r--r--  1 kernigh  kernigh  5589891 May 28 17:23 pg100.txt.cp
-rw-r--r--  1 kernigh  kernigh  5589891 May 28 17:23 pg100.txt.sc
-rw-r--r--  1 kernigh  kernigh  5590232 May 28 17:23 pg100.txt.sc.xz
-rwxr-xr-x  1 kernigh  kernigh     8564 May 28 17:23 scramble

Заметки о rand () и смещении вправо

Ни один алгоритм сжатия не может сжимать случайные данные. Я могу замаскировать pg100.txt и filament.jpg как случайные данные, если зашифрую их потоковым шифром .

Моя первая идея заключалась в том, чтобы создать зашифрованный текст с использованием исключительного или открытого текста с помощью pad , а затем сохранить шифрованный текст и pad в зашифрованном файле. Это увеличит размер файла и увеличит мою оценку. Очевидный выбор - использовать одну и ту же панель для каждого файла и хранить только зашифрованный текст в зашифрованном файле. Если я просто вызываю rand (), он использует начальное значение по умолчанию 1 и каждый раз делает один и тот же пэд .

OpenBSD 5.5 определяет rand () в stdlib.h и rand.c :

/* from stdlib.h */
#define RAND_MAX    0x7fffffff

/* from rand.c */
static u_int next = 1;

int
rand_r(u_int *seed)
{
    *seed = *seed * 1103515245 + 12345;
    return (*seed % ((u_int)RAND_MAX + 1));
}

int
rand(void)
{
    return (rand_r(&next));
}

Это линейный конгруэнтный генератор . Большой недостаток в том, что у младших битов короткие периоды. 1-й бит имеет период 2: если вы подбрасываете монету rand()&1, то это будут головы, хвосты, головы, хвосты и так далее. N-й бит имеет период 2 n . Есть 31 бит, поэтому вся последовательность имеет период 2 31 .

LZMA2 может находить паттерны за короткие промежутки времени и сжимать их. Самый короткий код ~c^rand()занимает младшие 8 бит и не препятствует сжатию. Правильный сдвиг ~c^rand()>>9помогает, но недостаточно. Я использую ~c^rand()>>23.

  • ~c СЧЕТ: 4227957 = 40 + 0 + 0 + 4019391 + 208526
  • ~c^rand() СЧЕТ: 2474616 = 47 + 0 + 0 + 2463735 + 10834
  • ~c^rand()>>9 СЧЕТ: 350717 = 50 + 0 + 0 + 350667 + 0
  • ~c^rand()>>23 СЧЕТ: 51 = 51 + 0 + 0 + 0 + 0
kernigh
источник
5

BrainFuck : 129 (129 + 0 + 0 + 0 + 0) *

random.bf (перевод строки добавлен для удобства чтения)

,+[->>>>++[<++++++++[<[<++>-]>>[>>]+>>+[-[->>+<<<[<[<<]<
+>]>[>[>>]]]<[>>[-]]>[>[-<<]>[<+<]]+<<]<[>+<-]>>-]<[-<<+
>>]<<.,+[->]>>>]]

Для создания unrandom.bfнужно поменять последний + во второй строке.

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

* Я протестировал байты, которые он обработал до сих пор 212992 (обработано через 12 часов), и оба файла превращаются в сжатый файл 213064. Я думаю, что это может быть сделано к концу недели, чтобы знать наверняка, но я не хочу ждать с публикацией. Я обновлю счет, если это не так, но оставлю решение, так как Правило 30 рулит!

Общая информация: Правило 30 было открыто Стивеном Вольфрамом в 1983 году и, согласно Википедии, оно используется для получения случайных целых чисел в Mathematica.

Компиляция и запуск:

Он использует экспоненциальное время и пространство (итерирует более 32 ячеек на обработанный символ), поэтому ему требуется среда выполнения BrainFuck, которая имеет не менее 178 876 517 ячеек для кодирования файла Shakespear, не обрабатывает non ascii как юникод, имеет более широкие ячейки, чем 8 бит, и использует -1 как eof (для различия между 255 и -1). Я обычно использую переводчиков других людей, но на этот раз я должен быть подключен и продвигать свои собственные:

jitbf --eof -1 -b 16 -c 200000000 random.bf < pg100.txt > pg100.txt.ran
jitbf --eof -1 -b 16 -c 200000000 random.bf < Glühwendel_brennt_durch.jpg > Glühwendel_brennt_durch.jpg.ran

jitfb компилирует BrainFuck для оптимизированного C и использует Perl Inline :: C для его запуска. Это в комплекте с моим расширенным компилятором BrainFuck . С размером и шириной ячейки в аргументе он выделит около 400 МБ.

Сильвестер
источник
3

CJam, 22 байта

G,~q{5$H$+255%_@^o}/];

При этом используется генератор с запаздыванием Фибоначчи с рекуррентным соотношением s n = (s n-5 + s n-16 )% 255 (который я выбрал по ошибке, но он все же работает) и тривиальное начальное число для генерации псевдослучайного потока байтов , который затем XOR с входом.

Я протестировал свой код с CJam 0.6 , который был опубликован 1 мая 2014 года.

Как это работает

G,~                    e# Dump 0, 1, ... and 15 on the stack.
   q                   e# Read from STDIN.
    {             }/   e# For each character in the input.
     5$H$              e# Copy the sixth and 19th element from the stack.
         +255%         e# Push their sum modulo 255.
              _@       e# Duplicate and rotate the character on top.
                ^o     e# XOR and print.
                    ]; e# Clear the stack.

Гол

$ LANG=en_US
$ alias cjam='java -jar /usr/local/share/cjam/cjam-0.6.jar'
$ cjam thwart.cjam < pg100.txt > pg100.txt~
$ cjam thwart.cjam < pg100.txt~ > pg100.txt~~
$ diff -s pg100.txt pg100.txt~~
Files pg100.txt and pg100.txt~~ are identical
$ cjam thwart.cjam < Gluehwendel_brennt_durch.jpg > Gluehwendel_brennt_durch.jpg~
$ cjam thwart.cjam < Gluehwendel_brennt_durch.jpg~ > Gluehwendel_brennt_durch.jpg~~
$ diff -s Gluehwendel_brennt_durch.jpg Gluehwendel_brennt_durch.jpg~~
Files Gluehwendel_brennt_durch.jpg and Gluehwendel_brennt_durch.jpg~~ are identical
$ xz -kz5 pg100.txt~ Gluehwendel_brennt_durch.jpg~
$ wc -c thwart.cjam pg100.txt* Gluehwendel_brennt_durch.jpg*
      22 thwart.cjam
 5589889 pg100.txt
 5589889 pg100.txt~
 5589889 pg100.txt~~
 5590232 pg100.txt~.xz
 1659874 Gluehwendel_brennt_durch.jpg
 1659874 Gluehwendel_brennt_durch.jpg~
 1659874 Gluehwendel_brennt_durch.jpg~~
 1660016 Gluehwendel_brennt_durch.jpg~.xz
28999559 total
Деннис
источник
3

PHP, 117 + 0 + 0 + 0 + 0 = 117

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

<?=substr(gmp_export(gmp_invert(2*gmp_import($s=stream_get_contents(STDIN))+1,$m=2*gmp_pow(256,strlen($s)))/2+$m),1);

В то время как все другие решения основаны на «безопасных» конструкциях, таких как «генераторы случайных чисел» или «криптография военного уровня», это решение просто интерпретирует строки как представляющие нечетные числа по модулю 2⋅256 ^ длина и вычисляет их модульные обратные значения .

Демо-версия:

$ php thwart.php < 100.txt.utf-8 > 100.txt.utf-8~
$ php thwart.php < 100.txt.utf-8~ > 100.txt.utf-8~~
$ diff -s 100.txt.utf-8 100.txt.utf-8~~
Files 100.txt.utf-8 and 100.txt.utf-8~~ are identical
$ php thwart.php < Glühwendel_brennt_durch.jpg > Glühwendel_brennt_durch.jpg~
$ php thwart.php < Glühwendel_brennt_durch.jpg~ > Glühwendel_brennt_durch.jpg~~
$ diff -s Glühwendel_brennt_durch.jpg Glühwendel_brennt_durch.jpg~~
Files Glühwendel_brennt_durch.jpg and Glühwendel_brennt_durch.jpg~~ are identical
$ xz -kz5 100.txt.utf-8~ Glühwendel_brennt_durch.jpg~
$ wc -c *
 5589889 100.txt.utf-8
 5589889 100.txt.utf-8~
 5590232 100.txt.utf-8~.xz
 5589889 100.txt.utf-8~~
 1659874 Glühwendel_brennt_durch.jpg
 1659874 Glühwendel_brennt_durch.jpg~
 1660016 Glühwendel_brennt_durch.jpg~.xz
 1659874 Glühwendel_brennt_durch.jpg~~
     117 thwart.php
28999654 total
Андерс Касеорг
источник
2

сценарий оболочки, 203

id|gpg --batch --passphrase-fd 0 --personal-compress-preferences Uncompressed $1 $2

Запуск это:

% sh break.sh -c pg100.txt                       
% sh break.sh -d pg100.txt.gpg > pg100.txt-original
gpg: CAST5 encrypted data
gpg: encrypted with 1 passphrase
gpg: WARNING: message was not integrity protected
% diff -s pg100.txt pg100.txt-original
Files pg100.txt and pg100.txt-original are identical
% sh break.sh -c Glühwendel_brennt_durch.jpg
% sh break.sh -d Glühwendel_brennt_durch.jpg.gpg > Glühwendel_brennt_durch.jpg-original
gpg: CAST5 encrypted data
gpg: encrypted with 1 passphrase
gpg: WARNING: message was not integrity protected
% diff -s Glühwendel_brennt_durch.jpg Glühwendel_brennt_durch.jpg-original
Files Glühwendel_brennt_durch.jpg and Glühwendel_brennt_durch.jpg-original are identical
% xz -kz5 Glühwendel_brennt_durch.jpg.gpg 
% xz -kz5 pg100.txt.gpg 
% ls -ln
total 28340
-rw-r--r-- 1 1000 1000      84 May 24 04:33 break.sh
-rw-r--r-- 1 1000 1000 1659874 Jan 19 17:22 Glühwendel_brennt_durch.jpg
-rw-r--r-- 1 1000 1000 1659943 May 24 04:46 Glühwendel_brennt_durch.jpg.gpg
-rw-r--r-- 1 1000 1000 1660084 May 24 04:46 Glühwendel_brennt_durch.jpg.gpg.xz
-rw-r--r-- 1 1000 1000 1659874 May 24 04:46 Glühwendel_brennt_durch.jpg-original
-rw-r--r-- 1 1000 1000 5589891 May 24 03:55 pg100.txt
-rw-r--r-- 1 1000 1000 5589941 May 24 04:43 pg100.txt.gpg
-rw-r--r-- 1 1000 1000 5590284 May 24 04:43 pg100.txt.gpg.xz
-rw-r--r-- 1 1000 1000 5589891 May 24 04:43 pg100.txt-original

Не очень переносимый, но может быть сделан за пару байтов. Требуется PGP (возможна также реализация с OpenSSL). Разница ~ 50 байтов между закодированным файлом и оригиналом, вероятно, может быть сохранена.

Подсчет очков:

84 + абс (1659874 - 1659943) + макс (1659874 - 1660084, 0) + абс (5589891 - 5589941) + макс (5589891 - 5590284, 0) = 203

копия
источник
1

Python, счет = 183 + 7 + 6 + 0 + 0 = 196

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

import sys
from random import randint as J,seed
x=sys.stdin.read()
seed(ord(x[1]))
n=int(2362*J(1,2)**2.359)
sys.stdout.write(x[:n]+''.join(chr(ord(c)^J(0,255))for c in x[n:]))

Результат:

Laxori@Laxori-PC /cygdrive/f/Programming/lzkill
$ cat photo.jpg | python break.py > photo.jpg~; cat photo.jpg~ | python break.py > photo.jpg~~; diff photo.jpg photo.jpg~~; xz -kz5 photo.jpg~

Laxori@Laxori-PC /cygdrive/f/Programming/lzkill
$ cat pg100.txt | python break.py > pg100.txt~; cat pg100.txt~ | python break.py > pg100.txt~~; diff pg100.txt pg100.txt~~; xz -kz5 pg100.txt~

Laxori@Laxori-PC /cygdrive/f/Programming/lzkill
$ ls -l
total 28337
----------+ 1 Laxori mkpasswd     183 2014-05-24 13:43 break.py
----------+ 1 Laxori mkpasswd 5589891 2014-05-23 19:19 pg100.txt
-rw-r--r--+ 1 Laxori mkpasswd 5589891 2014-05-24 13:45 pg100.txt~
-rw-r--r--+ 1 Laxori mkpasswd 5589884 2014-05-24 13:45 pg100.txt~.xz
-rw-r--r--+ 1 Laxori mkpasswd 5589891 2014-05-24 13:45 pg100.txt~~
----------+ 1 Laxori mkpasswd 1659874 2014-05-23 19:19 photo.jpg
-rw-r--r--+ 1 Laxori mkpasswd 1659874 2014-05-24 13:44 photo.jpg~
-rw-r--r--+ 1 Laxori mkpasswd 1659880 2014-05-24 13:44 photo.jpg~.xz
-rw-r--r--+ 1 Laxori mkpasswd 1659874 2014-05-24 13:44 photo.jpg~~

Laxori@Laxori-PC /cygdrive/f/Programming/lzkill
$ python
Python 2.5.2 (r252:60911, Dec  2 2008, 09:26:14)
[GCC 3.4.4 (cygming special, gdc 0.12, using dmd 0.125)] on cygwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 183 + abs(5589891-5589884) + abs(1659874-1659880)
196
Клаудиу
источник
С текущими правилами, нет никакого штрафа за сжатый файл, являющийся большим. Изменились ли правила? Если так, то такое изменение было несправедливо по отношению к этой программе.
кернинг
@kernigh: Да, они изменились после того, как я опубликовал это. Поистине, они должны были быть такими, какие они есть сейчас с самого начала.
Клаудиу