10
$\begingroup$

A long time ago in a basement far far away I created my own operating system. Unfortunately I made a foolish mistake when designing the file system. I choose a single byte for representing file sizes. Since that means that no file can be bigger than 255 bytes I was forced to also invent my own compression algorithm. Just now I came across such an old file called "message" compressed with said algorithm, unfortunately I don't remember how to decompress it.

Can you help me?

Here is a hexdump of the file:

> hexdump -C message
00000000  5f 20 5c 5f 2f 20 7c 0a  2a 2a 22 22 22 2a 22 23  |_ \_/ |.**"""*"#|
00000010  22 0a 29 22 22 22 22 22  09 23 22 23 22 22 22 89  |".)""""".#"#""".|
00000020  30 32 64 64 32 43 41 12  24 42 42 42 42 22 12 24  |02dd2CA.$BBBB".$|
00000030  42 62 32 64 64 42 83 2c  7c 46 7e 24 30 66 7e 39  |Bb2ddB.,|F~$0f~9|
00000040  66 62 7e 46 0a c1 0a 09  29 23 22 22 22 22 2a 22  |fb~F....)#""""*"|
00000050  29 8a 40 63 42 41 12 64  64 32 43 63 c1 49 42 42  |).@cBA.dd2Cc.IBB|
00000060  24 30 46 46 7e 69 24                              |$0FF~i$|

Since I never got around to adding any other encoding I am pretty sure the original file was a ASCII encoded "plain" text.

Hint 1:

I remember the first eight bytes to be somehow special.

Hint 2:

The original file contains English text; it however uses none of the following ASCII characters: abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ.

$\endgroup$
8
  • $\begingroup$ From the back of your memory: can it be assumed that ‚message‘ was an ascii encoded plain text? $\endgroup$ – BmyGuest Dec 2 '17 at 7:52
  • $\begingroup$ ( and welcome to the site! Yes, we love such puzzles — the quality can often only be judged once it is solved. Best check out some high and some low-voted examples to understand the reasons. And don‘t take negative votes personally, if they hit you. ) $\endgroup$ – BmyGuest Dec 2 '17 at 7:58
  • $\begingroup$ Good question thank you. Yes that can be assumed. I will add that to the description. $\endgroup$ – raggy Dec 2 '17 at 13:19
  • 3
    $\begingroup$ It is hard to believe, that this is indeed some kind of compression, since the entropy is so low... Are you sure it is not more a kind of encoding or cipher? $\endgroup$ – Ctx Dec 3 '17 at 9:23
  • 2
    $\begingroup$ Your statement that "the original file contains English text it however use none of the following ASCII characters..." and then lists the entire English alphabet seems to compromise your claim that this example file is the result of compression. Even if it is compression there are so many possibilities that it would take an extensive brute force effort to find it...especially if the original file is not "sensible English text". $\endgroup$ – Dr t Dec 3 '17 at 18:37
6
$\begingroup$

I am not there yet, but I have the strong suspicion, that

when outputting the file in binary coding, i.e. " " for 0 and "#" for 1, and being correctly wrapped somehow, there will be some text written with those two characters (space and #).

See for example:

Is this something?

However, if this is right, then

I do not consider this a compression, since it may be true, that the resulting file has more bytes, but "compression" is related to the information content per byte, so the compressed file does contain very few information per byte as opposed to simple ascii plaintext.

EDIT: Solved it ;) (stanri's comment helped here, thanks!)

The first 8 bytes are the charset: { "", " ", "\", "", "/", " ", "|", "\n" }. Then, for each byte, print char 0 from the charset, if the 0th bit is set, char 1 if the 1st bit is set, char 2 ...

This results in

Congrats

Is it a compression or not?

Honestly, I am not sure... I tend to say, it is indeed, regarding the ascii art. But not regarding the message itself.

$\endgroup$
8
  • $\begingroup$ I agree that this would not be compression. While the algorithm in question is a encoding it does do compression. I hope you can solve it! I am curious for your verdict. Let me know if you want more tips. $\endgroup$ – raggy Dec 3 '17 at 23:29
  • $\begingroup$ @raggy Hm, some hint on how close my suspicions in this answer are would be helpful ;) $\endgroup$ – Ctx Dec 4 '17 at 12:07
  • $\begingroup$ You are not entirely on the wrong track looking at individual bits. However i said no guessing and you guessed two characters and some wrapping. Maybe read hint 1 again. $\endgroup$ – raggy Dec 4 '17 at 14:07
  • $\begingroup$ My guess is something like this patorjk.com/software/taag/… and the first 8 bytes specify the size of the width/height, and the characters to use for the writing. $\endgroup$ – stanri Dec 4 '17 at 15:25
  • $\begingroup$ @stanri You put me on the right track, thanks ;) $\endgroup$ – Ctx Dec 4 '17 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.