토요일, 8월 02, 2014

[B급 프로그래머] 이 세상에서 가장 큰 압축 파일은?

직전에 소개한 폴리글랏 프로그래밍의 '폴리글랏'을 소개하기 위해 위키피디아를 참조하다 The Polyglot List이라는 페이지를 방문하게 되었다. 여기서 퀸(Quine, /kwi:n/)이라는 단어가 나와서 GEB가 생각나고 말았다. 퀸은 출력 결과로 자신의 소스 코드와 완벽하게 동일한 텍스트를 만들어내는 프로그램이다. 잠시 예제를 볼까?

char*f="char*f=%c%s%c;main(){printf(f,34,f,34,10);}%c";main(){printf(f,34,f,34,10);}

이런 예제도 흥미롭지만, Quora를 읽다 더욱 흥미로운 질문을 발견했다. 바로 이 세상에서 가장 큰 압축 파일은 무엇일까?

정답은 42.zip이라는 ZIP 폭탄인데, 압축되면 42.374 bytes에 불과한 파일이 압축을 푸는 순간 4.503.599.626.321.920 bytes (4,5 petabytes)로 변신한다. 혹시라도 호승심에서 이 파일을 구해 압축을 푸는 순간 여러분 컴퓨터의 하드디스크가 꽉 차버린다는 사실에 주의하자. 42.zip 파일은 16개 압축된 파일로 구성되어 있으며, 각각은 다시 16개 압축된 파일로 구성되어 있으며, 다시 한번 각각은 16개 압축된 파일로 구성되어 있으며, 또 다시 한번 각각은 16개 압축된 파일로 구성되어 있으며, 또또 다시 한번 각각은 16개 압축된 파일로 구성되어 있으며, 최종적으로 4.3기가 바이트짜리 파일 하나를 포함한다. 헉헉 설명 한번 힘들다.

한 술 더 떠 Droste라는 파일은 무한히 자신을 증식하는 특성이 있다. 어떻게 이런 일이 가능할까? 바쁜 독자 여러분을 위해 미리 답을 드리자면, 퀸을 사용해 허프만 코딩에 따라오는 LZ77 명령을 복제하는 방법을 사용한다. Zip Files All The Way Down라는 글에 나온 LZ77 퀸 코드를 살펴보자.

눈치빠른 독자분들께서는 이미 짐작했을테지만, No-op을 사용해 일단 자기 자신을 그대로 복제하는 코드 작성에 성공했으므로, 여기서 앞뒤로 접두어와 접미어를 붙이는 방법만 찾아내면 경기는 끝난다. 무한히 자신의 코드를 실행하며 계속 크기를 늘일 수 있기 때문이다.

뱀다리: 이런 유형의 해킹은 재미도 있지만 함수형 언어(응?)에 대한 관심을 유도하기도 한다. Scheme을 사용해 퀸을 만들면 어떻게 될까?

((lambda (x) `(,x ',x))
'(lambda (x) `(,x ',x)))

아무리 봐도 정말 멋지다!

EOB

댓글 없음:

댓글 쓰기