[9fans] OT: puzzle

[9fans] OT: puzzle

[Nigel Roles]

I've been struggling with this one for a bit, so I
thought I'd consult the combined brains of the 9fans list.

Imagine I want to reverse engineer the disk format used
by a hardware raid 5 controller. I plug 3 disks into
a controller, build the array, and then write a test
pattern to the logical file system. I then remove the
raid controller, plug the disks direct into the motherboard
and examine the layout on each disk.

Because of the way raid 5 works (in theory), I expect to
see a mixture of plaintext blocks, blocks which are
xors of the other pairs of blocks, and management blocks
containing proprietary stuff I may well not decipher.

What pattern should I write to each block so that I can
tell

1) whether a block is an xor, plaintext, or management block
2) for plaintext ones, which logical block it holds
3) for xor ones, which two plaintext blocks it is the xor of

1) seems easy as if there is a fixed pattern in every block,
it will appear as nulls in any xor block. So long as the
pattern is reasonably long, it is unlikely to accidentally
match a management block.

2) is simply a matter of writing a block number into the
block as well as the fixed pattern

3) has me stumped.

All suggestions welcome, including "you can't do it".

Nigel

Re: [9fans] OT: puzzle

[Russ Cox]

You can do it.  

When I say number-chunk, I mean the 16 bytes you
get for sprint(buf, "X%15d", n).  When I say zero-chunk
I mean 16 NUL bytes.

In the first half of each block, write the fixed pattern and
the block number.

Use the first half to classify the block as management, plain, or xor.

Treat the second half as a sequence of m 16-byte chunks.
Assuming m > 2*log2(n), you can treat each chunk as representing
a single bit in the block number.  When the chunk should represent
a 1 bit, set it to the number-chunk for n.  When the chunk should
represent a 0 bit, set it to the zero-chunk.  Then do the same trick
to encode the complement of the block number.  So if you are encoding
block 10 and you've decided to use 6-bit block numbers, the
second half looks like

  zero-chunk zero-chunk <10>-chunk zero-chunk <10>-chunk zero-chunk
  <10>-chunk <10>-chunk zero-chunk <10>-chunk zero-chunk <10>-chunk

When two number-chunks get xor'ed together, they lose the leading X,
so you know to ignore them.  

When you get an xor'ed block, scan the second half for intact
number-chunks (those that still have the leading X).  You'll find
at least one intact number-chunk from each of the two blocks
that got xor'ed, so just atoi() them to get your answer.

(This works because any two different numbers have to differ in their
binary representation somewhere - you'll get one block's 
pristine number-chunk at that bit position in the normal binary
encoding and the other block's pristine number-chunk at that position
in the complement.)

Russ