Impedir a compressão LZMA2

11

Objetivo

Crie um programa ou par de programas que, coletivamente, interrompem e corrigem arquivos com o objetivo de impedir que o LZMA2 funcione efetivamente. As rotinas de interrupção e correção devem ser recíprocas, para que você possa recuperar exatamente o arquivo original.

Metas

Métodos de compressão

  • Ubuntu / relacionados: xz -kz5 <infile>
  • Janelas: 7z.exe a -txz -mx5 <outfile> <infile>
  • Outros: use um compressor LZMA2 com nível de compressão 5 que comprime os trabalhos de Shakespeare para 1570550 bytes ± 100 bytes.

Pontuação; soma de (tudo está em bytes, ls -lou direle):

  • Tamanho do programa (o que for necessário para coletivamente "quebrar" / corrigir o arquivo)
  • Diferença no tamanho (absoluto) entre:
    • Trabalhos coletados brutos de Shakespeare e sua cópia modificada (não compactada).
    • Foto não processada e sua cópia modificada (não compactada).
  • Diferença de tamanho ou 0, o que for maior entre:
    • Obras coletadas em bruto de Shakespeare menos sua cópia compactada e modificada do LZMA2.
    • Foto não processada menos sua cópia compactada LZMA2 modificada.

Exemplo

Exemplo de Python 2.x com pontuação baixa, golfe lento, mas compatível com:

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)

Corrida...

$ 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

Ponto

  • = 194 + abs (5589891 - 5589891) + max (5589891 - 3014136, 0) + abs (1659874 - 1659874) + max (1659874 - 1646556, 0)
  • = 194 + 0 + 2575755 + 0 + 13318
  • 2.589.267 bytes. Ruim, mas não fazer nada nos arquivos gera uma pontuação de 4.635.153 bytes.

Esclarecimento

Isso é golfe, então você está tentando minimizar sua pontuação. Não tenho certeza se os comentários apontam um buraco legítimo na minha pontuação ou se são porque eu o tornei muito complicado. De qualquer forma, você deseja o MAIS PEQUENO :

  • Código fonte
  • diferença entre o arquivo modificado não compactado e o arquivo original (por exemplo, se você o modificar anexando um trilhão de zeros no final, sua pontuação aumentou um trilhão de bytes)
  • diferença entre o arquivo modificado compactado e o arquivo original (por exemplo, quanto mais incompressíveis os arquivos se tornarem, maior será sua pontuação). Um arquivo perfeitamente incompressível que cresça um pouco ou não pontuará 0.
code-challenge compression Nick T
fonte
2
A resposta correta: Etapa 1 - calcule quanto espaço livre em disco você dividiria pelo tamanho do arquivo para obter N. Etapa 2 - adicione o arquivo a si mesmo N vezes e o número N. Etapa 3 - perceba que há não há espaço para compactar o arquivo, mas acaba com uma diferença absoluta no tamanho dos arquivos de vários terrabytes (ou mais) .... [Para reverter, leia N no final do arquivo e reduza-o para 1/5 do tamanho. ]
MT0
@ MT0: Ah, eu acho que a solução é que as diferenças não devem ser absolutas. Se o seu arquivo modificado for maior, isso deve subtrair pontos.
Claudiu
@ MT0 se você modificar o arquivo para torná-lo um terabyte grande, sua pontuação será de 1 terabyte ... muito ruim quando você estiver tentando jogar golfe.
Nick T
@ MT0 Adicionei um esclarecimento à postagem, isso ajuda?
Nick T
2
Uma queixa. O compressor pode criar um arquivo maior se t for especialmente incompressível. Nesse caso, você deve ser recompensado, não punido, não?
Claudiu

Respostas:

8

Python, pontuação = 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

Faz um bloco único usando md5 no modo contador . contém o arquivo com ele. Isso tem a vantagem de que os arquivos originais e interrompidos são do mesmo tamanho e que o disruptor e o fixador são o mesmo programa.

Os arquivos interrompidos compactados são maiores que os originais.

Keith Randall
fonte
Ajustei marcando assim se os arquivos zipados são maiores do que suas contrapartes originais que não são penalizados e eles simplesmente marque 0. Não tenho certeza qual o caminho a diferença foi para seus arquivos mas você pode desejar para atualizar a pontuação
Nick T
@ NickT: atualizado.
Keith Randall
8

C, 51 = 51 + 0 + 0 + 0 + 0

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

Sob os truques de golfe , esse programa faz loops para cada byte na entrada padrão e é exclusivo - ou com um bloco infinito de rand (). Eu testei isso com rand () na libc do OpenBSD 5.5.

Uso:

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

Para testar meu programa, escrevi um shell script test.sh (57 linhas) para compilar meu programa e calcular minha pontuação.

$ 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

Notas sobre rand () e o deslocamento certo

Qualquer algoritmo de compactação não pode compactar dados aleatórios. Eu posso disfarçar pg100.txt e filament.jpg como dados aleatórios se eu os embaralhar com uma cifra de fluxo .

Minha primeira idéia foi exclusiva ou texto simples com pad para criar texto cifrado e depois armazenar texto cifrado e pad no arquivo codificado. Isso aumentaria o tamanho do arquivo e aumentaria minha pontuação. A escolha óbvia é usar o mesmo bloco para cada arquivo e armazenar apenas o texto cifrado no arquivo codificado. Se eu chamar rand (), ele usa uma semente padrão de 1 e cria o mesmo bloco todas as vezes.

Openbsd 5.5 define rand () em stdlib.h e 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));
}

Este é um gerador congruencial linear . A grande falha é que bits baixos têm períodos curtos. O 1º bit tem um período de 2: se você jogar uma moeda rand()&1, ela vai cara, coroa, cara, coroa e assim por diante. O enésimo bit tem um período de 2 n . Existem 31 bits, portanto, toda a sequência tem um período de 2 31 .

O LZMA2 pode encontrar padrões em curtos períodos e compactá-los. O código mais curto ~c^rand()pega os 8 bits baixos e não impede a compactação. A mudança certa ~c^rand()>>9ajuda, mas não o suficiente. Eu uso ~c^rand()>>23.

  • ~c PONTUAÇÃO: 4227957 = 40 + 0 + 0 + 4019391 + 208526
  • ~c^rand() PONTUAÇÃO: 2474616 = 47 + 0 + 0 + 2463735 + 10834
  • ~c^rand()>>9 PONTUAÇÃO: 350717 = 50 + 0 + 0 + 350667 + 0
  • ~c^rand()>>23 PONTUAÇÃO: 51 = 51 + 0 + 0 + 0 + 0
Kernigh
fonte
5

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

random.bf (feeds de linha adicionados para facilitar a leitura)

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

Para criar, unrandom.bfvocê precisa alterar o último + na segunda linha.

A maior parte do código é baseada no gerador de números aleatórios baseado em Rule30 de Daniel B Cristofani, adaptado para adicionar o número a cada entrada e terminar quando não houver mais entrada.

* Testei os bytes processados ​​até o momento 212992 (processados ​​após 12 horas) e os dois arquivos se transformam em um arquivo compactado 213064. Eu acho que isso pode ser feito até o final da semana, com certeza, mas eu não quero esperar com a postagem. Atualizo a pontuação se estiver errado, mas mantenha a solução, já que a Rule30 é excelente!

Curiosidades: A regra 30 foi descoberta por Stephen Wolfram em 1983 e, segundo a Wikipedia, é usada para produzir números inteiros aleatórios no Mathematica.

Compilação e execução:

Ele usa tempo e espaço exponenciais (itera mais de 32 células por caractere processado), portanto, requer um tempo de execução do BrainFuck que tenha pelo menos 178.876.517 células para codificar o arquivo Shakespear, não trate não ascii como unicode, tenha mais de 8 bits e use -1 como eof (para diferir entre 255 e -1). Eu costumo usar intérpretes de outras pessoas, mas desta vez eu preciso ser um plug e promover o meu:

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

O jitfb compila o BrainFuck para C otimizado e abusa do perl Inline :: C para executá-lo. Está incluído no meu compilador Extended BrainFuck . Com o tamanho e a largura da célula no argumento, ele alocará cerca de 400 MB.

Sylwester
fonte
3

CJam, 22 bytes

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

Isso usa um gerador de Fibonacci atrasado com relação de recorrência s n = (s n-5 + s n-16 )% 255 (que eu selecionei por engano, mas funciona mesmo assim) e uma semente trivial para gerar um fluxo pseudo-aleatório de bytes , que então XORs com a entrada.

Testei meu código com o CJam 0.6 , publicado em 1 de maio de 2014.

Como funciona

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.

Ponto

$ 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
Dennis
fonte
3

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

Porque você realmente confiaria a tarefa de manipular seus dados além do reconhecimento para qualquer outro idioma?

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

Enquanto todas as outras soluções são baseadas em construções "seguras", como "geradores de números aleatórios" ou "criptografia de nível militar", esta simplesmente interpreta as strings como representando números ímpares com comprimento de módulo de ⋅256 ^ e calcula seu inverso modular .

Demo:

$ 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
Anders Kaseorg
fonte
2

shell script, 203

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

Executando:

% 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

Não é muito portátil, mas pode ser fabricado à custa de alguns bytes. Requer PGP (uma implementação com OpenSSL também seria possível). A diferença de ~ 50 bytes entre o arquivo codificado e o original provavelmente pode ser salva.

Pontuação:

84 + abs (1659874 - 1659943) + max (1659874 - 1660084, 0) + abs (5589891 - 5589941) + max (5589891 - 5590284, 0) = 203

cópia de
fonte
1

Python, pontuação = 183 + 7 + 6 + 0 + 0 = 196

A pontuação o penaliza por tornar o arquivo completamente descompactável, desde então o arquivo compactado é maior do que a sobrecarga da compactação. Assim, meu programa os torna um pouco menos do que totalmente descompactáveis:

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:]))

Resultado:

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
Claudiu
fonte
Com as regras atuais, não há penalidade para um arquivo compactado ser maior. As regras mudaram? Nesse caso, essa mudança foi injusta com este programa.
kernigh 28/05
@ kernigh: Sim, eles mudaram depois que eu publiquei. Na verdade, eles deveriam ter sido do jeito que são agora desde o início.
Claudiu 28/05