OSDev.org

Lo,

I was wondering how a tool like Quickpar (*.par2 files) (or the algorithm behind it) is able to recover any data-block from the source file whit 1 recovery block. (Any data block, means that only 1 data may be bad, if more data block are bad u will need more par2 recovery blocks).

I have been looking on the internet and found lots of stuf. just not anything about the algorithm behind a tool like Quickpar2...

Might any one here know where some of the algorithm used in data recovery are explaned in detail?


Not sure if this well put in the os-dev section, but i didnt think it would fit in general rambling or the general coding section. Also this might be use-full for os-dev'ers.

Regards
PyroMathic

Maybe this:

http://en.wikipedia.org/wiki/Par2

Look specially near the end for the External Link that says Parchive project - full specifications and math behind it

The workings of forward error correction is relatively simple. given a set of data and a parity, we can solve for the missing piece, since data1 op data2 op ??? = parity.
The exclusive or is the common operator for being symmetric, but addition modulo x will do; in fact everything for which (a op b) = (b op a) and a op x = c always has one unique solution is usable.

given the set of bytes:
0xca
0xfe
0xba
0xbe
if we xor them together we get
ca xor fe xor ba xor be =
0x30

now suppose we are missing one entry:
0xca
??
0xba
0xbe
----
0x30

then the original can be reconstructed by xoring the bytes we do have
ca xor ba xor be xor 30 =
0xfe

and voilá, we have the missing piece

The case of N+1 is obviously trivial. You don't even need (a op b)=(b op a), as long as (a op x1)=c and (x2 op b)=c both have unique solutions (for unknown x1, x2) which can be found.

For the case of N+R then (where R is the number of redundant blocks) you simply need to find such set of relations, for which you have an unique solution, when any R components are missing.

mystran wrote:The case of N+1 is obviously trivial. You don't even need (a op b)=(b op a), as long as (a op x1)=c and (x2 op b)=c both have unique solutions (for unknown x1, x2) which can be found.

For the case of N+R then (where R is the number of redundant blocks) you simply need to find such set of relations, for which you have an unique solution, when any R components are missing.

The first is called Parity or a special case of the second.

The second is called Reed-Solomon coding: http://en.wikipedia.org/wiki/Reed-Solom ... correction

Thx for the replies. Am currrently trying to write a small program which is capable of fixing some data, whit a couple of recovery blocks. To see if i really get it .

Regards
PyroMathic

PyroMathic wrote:Thx for the replies. Am currrently trying to write a small program which is capable of fixing some data, whit a couple of recovery blocks. To see if i really get it .

If/When you finish it, would you release it under an open license so the people here can toy with it to understand it too?

Thanks in advance.

Candy wrote:

PyroMathic wrote:Thx for the replies. Am currrently trying to write a small program which is capable of fixing some data, whit a couple of recovery blocks. To see if i really get it .

If/When you finish it, would you release it under an open license so the people here can toy with it to understand it too?

Thanks in advance.

If i get it working, then ill post it here. Not sure how to release something under open source lisence, but i geusse that aint really going to be a problem.

It just might take a while for me to finish it .

Regards
PyroMathic