Here you can find the files found in the recovered compressed file.
The ogg file is distorted, maybe somebody with better audio editing skills can figure out something. The pictures and filenames already tell enough for me though.
A shorter wrap-up of all the findings that lead to the result can be read here, but I also kept the original post with updates for those who are interested in the complete history of the discoveries.
I promised to share all the code I've written to solve this puzzle. I've cleaned them a little bit, and made them available here (zip, ~30.5kB).
The corners for positioning, the alignment bits around them and two extra white pixels in the middle are at the very same positions for the tiles of all three raven tilesets. If we rotate the tiles on the two-page document 180 degrees, they have all these bits in the very same positions too.
The pixels should be converted to a bitstream, using boustrophedon traversing: rows by two, alternating between left-to-right and right-to-left, inside those always column first, top to bottom. See the red arrows on the picture below for clarification. White pixels should be converted to 0, black ones to 1.
The forementioned two white pixels actually work as a separator between the header and body part of the bitstream. The header is 378 bits long, while the body consists of 2040 bits.
The header should be read as 63 6-bit units. It uses a Reed-Solomon code with a message length of 15 units, and 67 as the primitve polynomial - just as it was given as a parameter for gfPow on the printout. If you don't know Reed-Solomon codes, you can think of it as a clever version of parity bits. The high redundancy it introduces allows us to recover the important 15-unit long main part of the header even if any 24 units (out of the 63) were corrupted. This 24 comes from an important parameter of the code, 2x24+1=49 is the so-called distance of the error correction, meaning that any two encoded words differ in at least 49 units. It is also not a coincidence, that 49=63-15+1, that is it is one larger than the difference of the block length and the message length. So the first 15 6-bit units are the important part of the header, the rest was there to make it possible to recover this first 15 if they are read imperfectly.
Even after the solution, most of these 15 6-bit units' meaning remained unknown, but we know that the last 4 is a counter. Each tile has a unique index, starting from zero, with an increment of one. The tiles were ordered according to this index in the raven-none and raven-ordered tilesets, but they were in a randomized order in the raven-random tileset and for the pages in the focus of the puzzle. For this latter, the largest index found was 2408 - suggesting there were at least 2409 tiles in this tileset, but only 2182 remained intact and were given in the tiles.zip provided by the official hint.
The only other 6-bit unit understood was the very first one. Its value serves as a parameter for how the body should be read - this was 16 for all the raven tilesets, but 20 for the last one.
The body uses Reed-Solomon error correcting codes as well, but with different parameters than the header. Here, units are 8 bits = 1 byte, and the block length is 255 bytes. The primitive polynomial is 301 for these (just as it was for rsgentest on the printout), the distance is 33 for the raven tilesets, and 41 for the tileset on the burnt paper. 33=2x16+1 and 41=2x20+1, so the first number in the header is the maximum number of errors that can be corrected in the message.
If a tile is successfully decoded, we're left with 223 correct bytes per tile in the raven tilesets, 215 in the document. But for some tilesets not all the tiles can be successfully decoded: raven-ordered suffered a spilled out coffee, and the two-page document got burnt. It is still possible to recover these, because of a second layer of Reed-Solomon codes. The raven tilesets use 223 bytes block length and 191 bytes message length, the two page document uses 215 bytes block length and 175 bytes message length. All the other parameters are the same they were in the first encoding.
For the raven-none tileset there is no interleaving, so the second layer is just another encoding on a single tile. But for all the other tilesets this second layer uses a diagonal structure: for example on the mysterious document the 617th block starts with the 1st byte of the 617th tile's , then the 2nd byte of the 618th tile's message follows, and so on, the last one in this block is the 215th byte of the 831st tile's message. Wherever it is needed, the indices wrap around, so the 2nd byte of the 2409th block is coming from the 2nd byte of the 1st tile's message (assuming that there are actually 2409 tiles in total, and not more).
A last problem was, that some of these blocks miss more than 20 bytes. However, in this case, the position of these wrong bytes are known (using coding theory terminology, in this case they are called erasures, not errors), and because of this, twice as many can be corrected. It is possible to recover all these blocks, extract the messages inside them, and you just have to concatenate them to get the original file. It is a bz2 file, containing a tar file, containing the three images and the audio file listed on the link above.
Original post (April 28)
Just some ideas which might lead someone somewhere:
@ffao's answer already suggested the use of polynomials over finite fields. Might it be, that the 'rs' in the filenames means Reed-Solomon, which is a type of error-correcting codes, just as QR codes are? I don't see the maths matching, however.
And I think the last page contains
three examples, what the encoding (with different parameters) produces on a sample text, probably Edgar Allan Poe's The Raven. At least that's what that filename suggests for me.
Update #1 (July 6)
I finally decided to digitalize the images.
You can find the output as a zip of text files here (~1.9MB).
I used the numbered, cut out and aligned tiles from @2012rcampion's answer with hints. 1s represent whites, and 0s represent blacks. There are some errors in the conversion, as the blacks and whites weren't perfect, but hey, if it's QR, it should be prone to errors :).
An even more cropped version can be found here (~1.6MB).
The difference from the above one is that 4 bits are removed in every direction, so there is no overlap between two tiles, and the aligment bits are cut in quarters in this conversion.
Feel free to use them!
Update #2 (July 7)
Sorry, I just realized that the cropped images were cropped too much (missing 4 important rows on the right and the bottom). I've corrected them, the link above now points to the corrected version.
I also changed the threshold used to distinguish black and white cells. It's still not perfect, but seemed to be better then the previous one.
Update #3 (July 7)
Using again the official hint answer,
this time the averaged pictures (for which the original idea comes from @WesleySitu). It seems that the alignment bits of the raven-* documents look like the bluish parts of this (png, ~2.6kB).
the mysterious document's alignment bits do not match, until you rotate them 180 degrees, upside down. So I'm pretty sure @LeppyR64's observation about rotating them upside down before further processing is correct.
Update #4 (July 11)
Traversing the pixels in the order that @WesleySitu suggested, the raven-* codes turn into these (zip, ~61.2kB) strings of 0s and 1s. If it is needed, I can convert the pages of the mysterious document too, but I think we should understand first what raven.txt went under.
For clarification, the order in which the pixels are read goes to the following pattern:
Neglect the alignment bits.
The rest is processed in rows of two, alternating from left to right, column first, from the top.
Update #5 (July 12)
As @2012rcampion pointed out, there was a bug in my code which was responsible for the order in which the pixels were read in. I've corrected it, and replaced the zip above.
Update #6 (July 26)
I tried to run the lines (which I got with the method above) through a Reed-Solomon decoder with the standard parameters (n=255, k=223). The bytestream I got is not human readable. Either this is not the next step that should be done, the parameters are not-standard, or I messed up something. I tried it with white cells as 1s and blacks as 0s and vice versa as well.
Update #7 (July 28)
I'm not yet sure how I did it, and the data seems to be dirty, but
just as I guessed in my original post, the raven-* documents are the encoded version of Edgar Allen Poe's The Raven.
I will be back after I manage to come up with a cleaner output.
Update #8 (July 28)
So here's what I've found earlier today. It is still work in progress, but seems like I've managed to identify some parts of the tiles:
What makes me to think this?
I was parsing the files I linked above as the digitized versions of the raven-none tiles, and playing with different Reed-Solomon parameters and bit offsets. Some parts of the resulting bytestreams started to make sense for the human eye, and 'BANG!' I immediately recognized parts of the poem I first mentioned in this post exactly three months ago.
Decoding the 'actual message' part as bytes and converting them to the corresponding ASCII characters, the raven-* documents hold these messages.
I did not check, but I think the raven-ordered and raven-random messages are some permutations of the characters in raven-none message.
The numbers (191+32+32 bytes) match too nicely not to be some kind of Reed-Solomon codes (my other first impression in my original post), but I didn't yet manage to build those parts together in a way that it makes sense.
As the raven-none tiles don't have any black pixels in the last 32 bytes, I think those bits cannot be a part of the error correcting bits. My first idea was that they are also part of the actual message and have to be used to reorder the characters to get back the original message, but did not manage to get anywhere with this so far.
So our idea about how to traverse the bits is confirmed.
And if you are using my files, you have to invert 0s and 1s as it seems black pixels represent 1s, white pixels represent 0s.
Update #9 (July 29)
A correction again - there was a mistake in the bit cluster picture above.
Update #10 (July 29)
I also figured out what to do with the ordered interleaving.
Rows represent tiles (in order, so tile0000 is in the first row), and the columns are the bytes extracted with the same method I used for raven-none. Newlines and other special characters are replaced by '+'.
Another new observation is, that
the tiles in the raven-random image are the very same tiles as the ones in the raven-ordered image, the only difference being their order (ordered tile0000 is random tile0011, ordered tile0001 is random tile0003, and so on).
The name suggests their order is random, but maybe with the help of the interleaving bits they can be somehow sorted, and once they are ordered, the previous method can be used to get the content of the message.
Preparing for the worst, I suppose
the mysterious document's pages are encoded with random interleaving, which means some characters (of the burnt tiles) will be missing every now and then from the message. Also those don't seem to have alphabetical characters, at least that's what their average's uniform gray color suggests. We will see soon.
Update #11 (July 31)
I was working on turning the mysterious pages into bits when I read @TusanHomichi's results, and his suggestion to redigitize the tiles.
I tried to do my best, played a lot with ImageMagick commands, and although it's still not 100%, I managed to
get a new version of the raven-* tiles, which gives an almost perfect bitstream - even before the error correcting is done. Of course I still converted the mysterious document as well. White pixels are decoded as 0 this time. You can find all these files here (zip, ~1.5MB).
Using these, and @TusanHomichi's observations about
the header, I managed to come up with the correct order of 2055 tiles of the mysterious document (txt, ~25.2kB). 'l' and 'r' stands for left and right page, the 4-digit number is the index of the tile as it was given in the zip provided by @2012rcampion. There are some holes in the sequence, but not that much. I estimate the missing number of tiles around 350-360.
Update #12 (July 31)
After these findings, I returned to work on
the message parts of the now ordered tiles. As @TusanHomichi noted earlier, the error correcting codes do not work in most of the cases, I managed to decode only 507 tiles.
So I tried to brute force some parameters, namely I replaced the modulus of 301 with all the possible irreducible 7-degree polynomials over GF(2). None of those helped to decode, not even a single tile.
Thus it seems, the modulus 301 is hardcoded in the encoding procedure, and this makes sense, as it wasn't given in the command line during the raven encodings.
there is another parameter, which was: '-t 16'. I've also noticed that the first and the seventh 6-bit chunk of the header of the raven tiles has the value of 16. For the mysterious document, the seventh is also 16, but the first one is 20. So maybe it was encoded with '-t 20'. But what that t means is still unclear. As another '--t=4' appears in the arguments of the run of rsgentest, I suspect it is worth looking for in that direction.
As a less serious sidenote,
another command line parameter of the encoding was '-s 6x6'. Probably it was for the shape. And what could be the shape parameter for the mysterious document's command?
It definitely has 30 columns and at least 40 rows, that's 2400 tiles on the two pages altogether. We also know, that the pages were upside down, and the last row is full, suggesting, that the number of tiles printed on those two pages is divisible by 30. Furthermore, in the headers we've seen indices in the range between 0 and 2408. So we have at least 2409 tiles, maybe a little bit more, if the ones with the largest indices are among the burnt ones. But it is very unlikely that there are 21 in a row lost, which would complete a full row. So probably there was another page with the last 9 or slightly more tiles in the office.
Haven't you found anything like that, @2012rcampion? Maybe at that time you didn't happen to realize it is the last part of this document, but you still picked it up with all the other papers. Not that we need some more tiles that much, but maybe there is some other important information (a.k.a. hint) on that piece of paper...
Update #13 (August 1)
Further optimizing my digitizing process, I managed to
get the counter in the header for all the tiles provided. I had to do the last 14 manually, but hopefully there aren't any errors. The file I linked yesterday about the correct order of the tiles is now updated. Of course the burnt tiles are missing, so are the ones which did not fit on the pages.
The message parts can be decoded with my current method for about 1700 out of 2182. I will publish those soon.
Update #14 (August 1)
I started publishing
the message bytestreams of the tiles (now ordered according to the counters inside them). You can find all the encoded messages and the succesfully decoded ones
here [EDIT: link removed with update #16]. The set of the latter is continuously updated.
Update #15 (August 1)
Here [EDIT: outdated, see update #18] you can find my current best attempt as the target file's reconstruction. Some assumptions I used:
I assumed that the tile index 2408 what we saw is the actual largest, so there are 2409 tiles in total.
Wherever the decoding was successful, I used its outcome. If the decoding failed, I used the corresponding byte of the encoded version. If the whole tile was missing, I used the byte 0xff, as a simple frequency analysis showed there are more black pixels than white ones.
If anyone can open it with something, let me know. I guess it still has too many corrupted bits to be opened.
Update #16 (August 2)
For some tiles the main problem was
a one pixel translation into x or y direction. Identifying these tiles and realigning them before processing allowed me to encode further 174 of them. Now there are 1910 which can be perfectly decoded. The link above to the reconstructed file is updated.
I removed the link from update #14 to the decoded and encoded versions of the tiles, as they are not that helpful.
Here is a zip of undecoded tiles instead [EDIT: no more tiles left unsolved].
Update #17 (August 2)
Further finetuning of
parameters in my ImageMagick scripts allowed me to decode all but 5 tiles. The reconstructed file and the 5 problematic tiles are now available on the links above.
These tiles seem to be tricky, probably they need manual corrections, but it's getting late here, and I just cannot focus with my eyes any more today. Maybe someone else is more fresh to do that.
I still don't know what to do with the restored file. Maybe it needs the last 5 tiles. Maybe even with those a good enough reconstruction is impossible.
Update #18 (August 3)
I'm done with
manually correcting the last 5 tiles. I've updated the reconstructed file. My system automatically detects it as a .bz2 file, but still cannot open it. Maybe it has some error correcting structure, or it can be restored with some data restoring software.
It is available in 2 versions: supposing there are 2409 tiles in total, or 2410.
Update 19 (August 3)
I've found some
short description about what kind of error correction is used for .bz2 files, and managed to use the recovering tool mentioned there on the 2409-tile version above (it fails on the other one). This is the result, but I still cannot open it.
Update #20 (August 6)
I realised, that
there is another layer of Reed-Solomon encoding inside the encoded versions of the tiles, with block length of 215 bytes, and message length of 175 bytes. The blocks go across tiles, so it might be possible to restore the missing tiles and thus the missing parts of the file, but so far I've only managed to recover only about half of the blocks. The file remains corrupted.
Update #21 (August 7)
As a second tought, I'm not sure about
the message length being 175 bytes. Do you remember the number 16 in one of the 6-bit chunks in the header? Maybe it means the maximal distance for the error correction, and then the message should be 183 bytes.
Anyway, it seems the only direction going forwards is to decode some more tiles, which weren't provided in the post with the official hints. There aren't too many, but maybe just enough to get inside the maximal distance, and have a successful decoding for all of the blocks.
Update #22 (August 8)
I'm now working on
extracting some more tiles from the original pictures. There are about 116 partial tiles, here are the rotated versions of some which give some hope to be recovered.
Update #23 (August 10)
It seems like
the message length is 175 bytes, at least I manage to decode more parts with this parameter. This means that the 215 byte block can have 20 bytes wrong. Because of the diagonal structure, a part of the bz2 file can be recovered if we have at least 215-20=195 tiles of every consecutively indexed sequence of tiles - that is, the first part needs at least 195 tiles from tiles indexed between 0 and 214, the second part needs at least 195 tiles from tiles indexed between 1 and 215, and so on.
Well, the original tiles.zip does not contain enough tiles to cover all these sequences sufficiently: for example, we have only 185 tiles with indices in the range [165, 379], so I don't see how the corresponding part of the file can be recovered without knowing some more tiles with indices in that range.
So I'm now hunting more tiles. Some more which I managed to decode successfully are the ones marked with blue here:
The first few were possible to extract without manual work, but the task is getting more and more tricky. It obviously offers only a limited number of tiles to be recovered. Probably not even enough to recover the missing parts of the file.
The method worked very well with the raven-ordered file where some tiles were too badly corrupted themselves, but the diagonal error coding made it possible to recover them.
However, maybe there is another direction which we should go for these pages, as we don't have enough tiles for the diagonal decoding. I'll still keep hunting for tiles for a while though.
Update 24 (August 11)
Finally here is the recovered file.
It is a bz2, extracting it you get a tar, extracting that you get 3 pictures and an audio file. I'm still having troubles playing the audio, but the pictures suggest I shouldn't even tell anybody I've ever seen them or heard the message on the audio.