Working on major Par2 changes. Name?

[mdnahas]

Hi everyone,

I wrote the specification for Par2 a long time ago. I'm working on the code for a new version of Par. It will include:

1. Reed-Solomon encoding with James S. Plank's correction
2. Tornado Codes by Luby

I've spent a week learning the code. I've written unit tests for some of the existing code. The tests should allow me to modify the code without breaking it. The unit tests should be run as part of "make check" but I don't know how to add them. (I've never learned Automake). Can anyone explain how?

I also plan on writing a diff tool that can compare Par files to make sure the packets are bit-for-bit identical. I'll use this to make sure that my changes haven't affected the program's output for version 2 of the specification.

I plan on adding a "doc" directory, which will contain the old Par2 specification and the new specification.

The Tornado Codes will need a predictable pseudo-random number generator. I expect I will use a version of Linear Congruential Generator.

The big question I have is: what do we name the next version and do we want to add a new file extension? At this moment, I plan on keeping all of Par2's packets and just adding new recovery packets. This will mean that par2 clients will still be able to verify the file, but will not be able to fix it. Unfortunately, par2cmdline currently silently ignores any packet type it does not recognize. So, existing users won't know why they cannot fix it. I would normally call the new specification Par2.1 or Par3, except the name "Par3" has been used by the developer of MultiPar. Perhaps we should call it "Par4"?

When we decide on a new name, I'll push a new branch and everyone can take a look at the spec/code.

Mike

[animetosho]

Interesting!

You seem to be interested in retaining most of PAR2 - I presume, only changing the erasure coding used? What's the aim of your change? Just to improve encoding/decoding performance?

Have you looked at MultiPar's efforts and ideas with a PAR2 successor? https://www.livebusinesschat.com/smf/index.php?board=417.0
It seems like they're looking at a more substantial change to the format, rather than just an encoding change, but I wonder, wouldn't it be more worthwhile trying to do this instead of making a only-slightly-backwards-compatible PAR2 successor? Is there that much value in being able to verify data with an old PAR2 client?

As for your question, I feel a little uncomfortable with keeping the same extension. PAR2 is fairly old and well established, and as you've found, at least one client (possibly more) wouldn't handle such a change particularly well.

Thanks for your work nonetheless, I'm interested to see how it turns out.

[mdnahas]

I have two goals. The first is to fix the bug in the Reed-Solomon code that has existed since Par1. I tried to fix this in Par2 by using only certain base values. That lessened the problem, but didn't fix it.

My other goal is to start using low-density parity check (LDPC), which are no longer covered by patents in the USA. LDPC is much faster than Reed-Solomon, with a slightly increased chance of non-recovery. There are many forms of LDPC; Tornado Codes are simple ones. If I do the spec right, repair will work for many LDPC, not just Tornado codes. Then, people who implement the spec can play with multiple different encoding schemes.

One of my restrictions is that I want to do this change in about a week's worth of work. I have some free time, but not much. Having looked at the code, I really want to spend time cleaning up the code and making it work like a library, but don't have enough time to find all the bugs I would create by doing that. I think I can fix Reed-Solomon and add support for Tornado Codes in 40 hours.

I've tried to understand the author of MultiPar's efforts. But I haven't see a spec for their "Par3". I don't think they are devoted to open source code. I designed the Par2 file spec to be forward-compatible - it was designed to add features. I'm sure the Par2 spec could be improved by a redesign, but I don't see a huge win for it right now. Certainly not without a large number of people devoted to implementing it and checking the code.

[animetosho]

Thanks for the response and explanation!

So it seems like this is more of just an experiment for encoding schemes rather than some sort of end-user oriented, production-ready PAR2 successor?

Totally understand the lack of time. It's just that I don't think a PAR2 successor should really be rushed, particularly if the aim is to continue to support it for the next ~10 years or more. Parchive is often used for archival purposes (hence the name), so it's a format you generally don't want to be changing often, which is, unfortunately, often at odds with an experimental scheme.

Not trying to discourage change or contributions in any way, but I thought it should be pointed out nonetheless.
PAR2 does have quite a number of issues, some as you have noted, so addressing some them is certainly a welcome move.

But I haven't see a spec for their "Par3". I don't think they are devoted to open source code.

"PAR3" was never really a finalised spec, only a proposal at most. The MultiPar author was experimenting with some new ideas, and decided to call it "PAR3" and included it in MultiPar. Unfortunately, people actually started using it for non-experimental purposes, so he had to pull it.
If you're interested, here's the last version of the "PAR3" spec, last updated in 2010. I think the author did aim to have an open standard, but it didn't go anywhere. I think the new approach seems to be with more open discussion around it, hence the link I previously gave. At this stage, there hasn't been anything beyond ideas/discussion however.
In short, PAR3 was never more than some experimental implementation that didn't really go anywhere and had to be pulled. In some ways, it seems similar-ish to what you're proposing at the moment - e.g. if it's aim is more experimental, and if it's labelled as some PAR2 successor, end users may end up inadvertently relying on it, when they shouldn't be.

Regardless, I mention this as they seem to be the only people still looking into a PAR2 successor (as well as one of the few actively developed PAR2 implementations), so thought you/they may be interested in such a proposal that you're making. I'm not too sure if you'll get much of a response here, but if you put up your proposed specification, I can share a link to it over there to get some of their thoughts.

Again, I personally do appreciate the effort you've gone (and will go) to, and am interested to see what you come up with!

[mdnahas]

Thanks! I tried to keep tabs on the Par3 discussions back then, but I never saw a specification.

So their old proposed Par3 changed every packet. The changes include:

• uses Reed Solomon FFT codes
• drops MD5
• adds two different 64-bit CRCs (to correct small errors ... but not to replace MD5 (?))
• use 1 and 2 byte integers (some integer fields are variable length)
• packet types are numbers, not 16-char strings
• files are identified by integers, not MD5-16k hashes
• pack the ends of files (parts less than a full slice) together

I'm not a fan of the last 4 changes - it increases code without specific benefits. In fact, using packet numbers rather than strings means it is difficult to add custom extensions and to debug things.

Does anyone have an analysis of how much time par2cmdline (or another client) spends doing each task? E.g., how much time in CRCs, MD5s, inverting the matrix, etc.. If MD5 is taking up too much time, maybe we should replace it. Otherwise, it seems foolish to drop backwards compatibility for non-recovery packets.

Does anyone have the "noe" program or "libnoe" library for computing Reed-Solomon with FFT? Or perhaps another implementation? I'm not tied to Plank's corrected version. Fixing that problem is certainly something I'm in favor of.

As far as "an experiment" vs "end-user oriented, production-ready PAR2 successor", I do not want to stall all development for a successor just because people use PAR2. We need to experiment. We should work on fixing Reed-Solomon and we should work on adding support for LDPC. We do need to be careful communicating to users what is untrusted. We also don't want to break "par2cmdline" for Par2, which is why I'm (1) not changing much, (2) adding unit tests and (3) asked another developer to review my code before it is merged.

[animetosho]

using packet numbers rather than strings means it is difficult to add custom extensions and to debug things

Going out on a limb here (I haven't read the proposal), I would imagine that the typical approach here is to allocate ranges for custom extensions. I also imagine that ease of debugging was not goal of the proposal either.

it seems foolish to drop backwards compatibility for non-recovery packets

That's an interesting opinion. Personally, I don't see much benefit in retaining backwards compatibility just for non-recovery packets, seeing as the whole point of PAR2 is the recovery packets. I suppose there's some use with using it to perform hash verification, but I don't feel that this is the primary aim of PAR2, and imagine that other methods (e.g. just storing a hash) are more frequently used for cases where only verification is necessary. The ability to verify is also limited, because most PAR2 tools also check the recoverability if bad blocks are found, which obviously won't work if a new type of recovery block is introduced; I don't recall the PAR2 specification even allowing for new types of recovery blocks, so there's no reason or expectation for clients to handle such a change in an ideal manner either.

You do mention that you have limited time to work on this, and hence want to minimize changes, which is totally understandable, but I see this more as a constraint rather than a benefit for minimizing changes.

it increases code without specific benefits

This doesn't really address your concerns, but here's a list of issues the MultiPar author has with PAR2, written 5 years after the PAR3 proposal, that he'd like to resolve with a PAR2 successor. May give some ideas on the reasoning behind the proposed PAR3 (e.g. using numbers to maybe reduce the size of the PAR archive, further enhanced by compressing filenames?).

Does anyone have an analysis of how much time par2cmdline (or another client) spends doing each task?

I only have experience with implementing a PAR2 encoder, so haven't looked much into decoding (so not much knowledge/experience implementing matrix inversion), and what I'm about to say relates to encoding.

As RS coding is relatively slow, generally the time spent hashing is negligible. However, if you replace RS with something faster, hashing will become a larger part of the overall speed to create/repair PAR2.

As far as I'm aware, all PAR2 clients (other than ParPar) perform an initial hash pass to compute the MD5/CRC32 of each file/block, during which, you're probably limited by I/O rather than CPU. NMVe SSDs, which are gaining mainstream traction, likely tip things the other way, though running MD5 in multiple threads is probably sufficient to keep I/O being the bottleneck. Another possible trick is to use a multi-buffer (SIMD) MD5 implementation, but I think only ParPar is the only PAR2 client which implements that.
MD5 is reasonably fast for a cryptographic hash. For cryptographic purposes though, it's not recommended due to existing collision attacks against it. The use of a cryptographic hash function may be interesting if one can rely on it being secure - for example, you could use it to uniquely identify files and clients might be able to make certain assumptions around it, although I imagine the benefits may be limited.

CRC32 is generally very fast, and modern x86/ARM CPUs have acceleration for it. I think rolling the CRC and checking for matches, for finding misaligned blocks during recovery, can be somewhat slow though. Rolling can also be problematic if you have to re-compute the MD5 for every potential match, which can lead to a kind of DoS attack against a PAR2 client attempting recovery.

Here's a discussion around hashing in PAR2 and successors.

I/O can be a limitation when processing large amounts of data which cannot fit in memory, due to the need for certain seek patterns. This may become less of an issue with the dying use of rotating media for storage though.

Note that par2cmdline isn't particularly a performance oriented implementation of PAR2. For most of its history, it's been a single threaded, non-SIMD, no-ASM implementation. There have been various forks which have added these performance features (e.g. par2-tbb, phpar2). It's only more recently that par2cmdline-mt was merged in, adding multi-threading to par2cmdline (but still no SIMD). MultiPar is more performance oriented, so obviously the author is more concerned about such issues with a proposed successor.

For some rough performance figures on the fastest implementations I know of, off the top of my head. On one thread of a 4.3GHz Skylake-X CPU (supports 512-bit SIMD via AVX512):

• MD5: 800MB/s (OpenSSL ASM implementation)
• MD5 multi-buffer: 3GB/s (I think? can't remember exactly now) using 128-bit AVX512VL. A full 512-bit AVX512 implementation should be a bit under 4x that, so potentially >10GB/s
• CRC32: >25GB/s using the carry-less multiply PCLMULQDQ instruction (memory read bandwidth per core is around 17GB/s, so this will be limited by it for buffers which don't fit CPU cache). The more common "Sarwate" algorithm won't achieve that speed, but I'd guess is still at least 1-2GB/s.
• GF16 multiplication: 45GB/s using AVX512's 512-bit VPSHUFB instruction. I seem to be L2 cache bound at that speed, so there's potential further gains by processing multiple blocks at a time, rather than the simple "multiply" function I have in ParPar. Despite this speed though, RS coding obviously requires multiple multiplies, depending on how many recovery blocks are generated. Very roughly speaking, for 1000 recovery blocks, you're probably looking at 45MB/s per core, which is likely going to be your primary bottleneck if not reading from a harddisk
• NMVe SSD: around 3GB/s sequential read. 4K random QD32 is probably around 1GB/s
• harddisk: typically 100-200MB/s sequential read, 0.2-0.5MB/s 4K random

I do not want to stall all development for a successor just because people use PAR2. We need to experiment

Oh definitely! It's just that that wasn't clear from your first post, considering that this repository is more a user-facing tool rather than for experimentation, and the questions asked around the name (which sounds more like an issue if you're proposing an actual standard rather than experimentation) initially gave me the impression otherwise. Hence my asking and confirming.
I'd personally prefer to keep such changes out of the main par2cmdline branch until something more final, otherwise someone is bound to misuse it. Interested parties can grab the experimental fork to test changes :)

Thanks again for the reply!

[mdnahas]

I don't worry about intentional MD5 hash collisions or denial of service. We use MD5 for uniqueness, but I don't think our users rely on that. (Or, if they do, they probably know what MD5 is and its security issues!) I do worry about buffer overflow and writing system files.

If we want people to implement Par3, it's easiest if they can just reuse the code from Par2. Why recode the wheel?

I agree that par2cmdline should not be tweeked for performance. It should be a clear roadmap for how to implement the standard. I actually don't think it does a good job of that - par2repairer.cpp is 2750 lines. I guess it needs to be multi-threaded (or use fork?) because it is compute intensive and everyone has multi-cores now-a-days.

Is GF16 multiply 45GBps or 45MBps? If it's 45MBps, then it and I/O are our bottlenecks. Changing to LDPC might improve things.

I'm not sure what I'll work on now. Maybe I'll just spend the week cleaning up par2cmdline. I hate modifying a working program without enough tests, because I may break an untested feature. (There's a lot of commandline options to test!) But a cleaner version would make it easier for people to copy the code and then improve performance of pieces.

If I skip additions and just improve par2cmdline's code, there's things like:

• create a par2 library and have par2cmdline process commandline args and then call the library.
  (This is hard because the commandline class currently does things like look up the size of files!!)
• automatically handle the case when the bug in Plank's Reed-Solomon appears. (I didn't see code to handle this. Is it there?)
• print message if a packet is detected but type is not handled
• make CRC and MD5 have the same interface (they are both hashes, but the class interfaces are very different). I'd like to encapsulate the many ~0 that are currently in the code without any explanation.
• get rid of class variables for par2repairer and par2creator. Most are currently acting like global variables in a 2700 line program, rather than class vars. Because of this, it is hard to see where data is created and consumed.

As I said, these are huge changes and I'm loath to make them, because there's a good chance that I'll introduce bugs to a long-run tool.

[animetosho]

Is GF16 multiply 45GBps or 45MBps?

Multiplying a buffer by a constant can be done at 45GB/s using 512-bit SIMD. In other words, a single multiplication is 45GB/s. The implementation is based off Plank's "Screaming Fast Galois Field Arithmetic Using Intel SIMD Instructions" paper (you can find his implementation here). My (much less readable) implementation extends his 128-bit SIMD code to use 512-bit SIMD (available on the latest Intel server processors), and adds a few small performance tweaks on top, effectively achieving around 4x the speed of Plank's implementation on CPUs with AVX512.
I've also investigated an alternative GF16 multiply kernel which relies on JIT'ing XOR code for each multiply. My current implementation seems to generally outperform Plank's algorithm, at the expense of a significantly more complex implementation (perhaps ridiculously complex in fact). It currently doesn't scale as well to 512-bit SIMD though (around 40GB/s peak), as it is mostly stalled by L2 cache, though I believe it can be further tweaked, and has the potential to be much faster.

Here's a benchmark I performed with some GF16 multiply techniques. The "lh_lookup" value refers to the technique of splitting the 16-bit multiply into low/high 8-bit multiplies in a 512-entry lookup table (basically the same method used in par2cmdline) - this is the fastest, portable, pure-C technique I know of, but as it doesn't use SIMD, falls behind the other techniques on performance. "shuffle" refers to my implementation of Plank's method above, at 128/256/512 bit SIMD widths. "xor" is the technique of using JIT to generate XOR sequences linked to above, at 128/256/512-bit SIMD widths. "memcpy" is just the standard glibc implementation of memcpy - mostly useful as a reference to give an indication of cache/memory bandwidth.

(looks like I accidentally chopped off the X-axis label, which is the buffer size used; you'll find a similar graph in Plank's paper, but his implementation only uses 128-bit SIMD)

However, in reality, it's unlikely that users create PAR2 with only a single recovery block. Which means that more multiplications need to be performed, proportional to the number of blocks to be generated. The example I gave was with 1000 recovery blocks, which means 1000x region multiplies for each input block, hence giving the (very rough) 1000x overall speed decrease (=45MB/s per core).

Note that this speed was achieved on a very recent, high power Intel CPU with AVX512 running at a high clock rate. Most users do not have access to such powerful hardware, so the figures I'm giving are somewhat at the upper-end of the scale of what's possible on a CPU today (a more typical x86 processor today would probably get half that speed). At the other end of the scale, a low power ARM CPU (with NEON (SIMD) support), for example, may only achieve around 300MB/s using the above algorithm for a single multiply. CPUs without SIMD units may perform even worse.
(it's also worth pointing out that that computers with powerful CPUs are likely paired with fast drives, in which case, I/O is unlikely going to be a bottleneck in practice)

So despite the various tricks you can pull for a highly optimised/tuned implementation of GF16 multiplication, they come at a complexity cost, and there's still fundamental limitations, hence a faster erasure code is definitely welcome. Particularly, something that can grow at O(n log n) complexity, instead of O(n*n) would be useful, especially if we want to scale beyond 64k recovery blocks.

---

Just to make sure you're aware, I don't work on or maintain the par2cmdline codebase, so can't really comment much on your suggestions (hence I won't be able to do much regarding the comment you made in your latest pull request). I'm mostly just an interested 3rd party who works on my own PAR2 implementation (which has somewhat different aims to existing PAR2 implementations (e.g. one thing I wanted was to be able to process data from streams rather than be tied to on-disk files)). There isn't much development going on with par2cmdline these days though, so I would suspect that any contribution you're willing to make is valued. Your suggestions do sound like good changes nonetheless, and I appreciate you putting your time and effort into this.

there's a good chance that I'll introduce bugs to a long-run tool

All changes have such risk, but without changes there is no progress. You sound like you're fairly cautious already, so I wouldn't worry too much about it. All software has bugs - if one crops up, someone just needs to fix it.

---

Yutaka Sawada (MultiPar author) made a comment regarding your initial proposal. I've copy/pasted it below:

Thank you for notice. It's interesting, and I will help as possible as I can. MultiPar will support it, too.

Because I don't know about Tornado Codes, I cannot say it's good or not. But, "1.Reed-Solomon encoding with James S. Plank's correction" would be bad, because it requires inversion of matrix. When there are many blocks, inversion will become almost impossible. (from calculation speed and required memory size.) I prefer to use Cauchy Matric for quick calculation, which Mr. persicum suggested ago.

As I cannot explain the mathematics, I put some paper about the usage.

Filename: oninversionofcer00sche.pdf
"On the Inversion of Certain Matrices"
by Samuel Schechter, February 1, 1959
AEC Computin and Applied Mathematics Center
Institute of Mathematical Sciences
New York University

Filename: 0301097.pdf
"The Efficient Implementation of Reed-Solomon High Rate Erasure Resilient Codes"
by Jin Li
Microsoft Research, Communication and Collaboration

Another issue of PAR2 is order of input files. Because filename affects the order of input files in current PAR2, it's impossible to change filename later, even when contents of files aren't changed. Now, a user needs to recreate whole PAR2 files after renaming a source file. Some users requested a feature of renaming filenames over MultiPar. Though I include a tool to rename filename in MultiPar package, it's out of PAR2 spec. If new PAR spec (maybe PAR3) solves this problem, it will be convenient.

[Rhialto]

On Tue 30 Apr 2019 at 07:35:08 -0700, Michael Nahas wrote: - create a par2 library and have par2cmdline process commandline args and then call the library.

That would be quite useful! Currently there is a tool that I sometimes use (nget, an nntp downloader with automatic use of par2 files) which includes a copy of par2cmdline, but modified a bit. The tool is also abandoned, but I cloned it to gitlab: https://gitlab.com/Rhialto/nget . It would be great if I could modify it to use a proper library (eliminating the copy and the annoying modifications).

[mdnahas]

Thanks @animetosho for the GBps / MBps explanation. memcpy is a good reference for speed.

And thanks for forwarding the comment on "matrix inversion" from Yutaka Sawada. As part of a job, I've actually tried to invert large matrices and I found that doing more than a 400x400 was impossibly slow. I'm not sure we should use the term "Reed-Solomon" if we're not actually doing Reed-Solomon. I've been thinking of renaming the class to "reedsolomon_broken".

I find it interesting that people are changing filenames after creating Par2 files. That isn't something I anticipated when writing the spec! Currently, the spec says that clients shouldn't try to verify how the "recovery set ID" is calculated. We could amend it to say that they shouldn't try to verify how "file ids" are calculated. We did an informal amendment to a version "2.1" which allowed clients to use UTF-8 in filenames (instead of pure ASCII).

@animetosho The streaming idea is interesting. Are you using the optional packets that allow you to include slices of the input file?

[animetosho]

Yeah, there are all sorts of things people out there want to be able to do. Anothing thing is being able to add files or update a PAR2 archive. Currently this requires recomputing the whole thing due to the strict file ordering determining the coefficients used for computation.
Not being limited to 32k input blocks/files is also a nice thing to have.

When you get down to it, there's a lot of things that Parchive could be doing but currently can't in PAR2, which is why I personally think a major overhaul of the format is warranted.

Are you using the optional packets that allow you to include slices of the input file?

I am not including parts of the source file in the PAR2 archive. Streaming is more in the sense of being able to pipe data in from memory, as opposed to using PAR2 as some on-the-fly FEC for lossy network transmission or the like (though you could do that too).

For example @Rhialto gives the example of a usenet downloader. Currently these write all downloaded files to disk, including PAR2 files, then perform verification/repair. If those could be performed somewhat on-the-fly, whilst the download is occurring, you can save time over doing separate processes, whilst also reducing disk I/O (and even avoid writing PAR2 files to disk entirely). Unfortunately, existing PAR2 implementations are too closely tied to the notion of on-disk files to be able to do this.
I also had a request to be able to have stdin directly piped in for processing, which is interesting because you don't know the size of it in advance, in addition to it being a stream.

[mdnahas]

If you can collect the use cases that Par2 doesn't work well in, I can take a look at how the design might change.

I think we can handle renaming files by just not requiring clients to confirm the File ID.

If we want to handle single-byte changes in files, like the proposed Par3 spec you forwarded, that does require big changes.

Do people really want >32,000 blocks? Each block adds overhead (CRC32 and MD5 checksum). I mean, it's very doable, but I'd want to shift to something like LDPC, which has less computation per block.

Streaming is possible with minor changes. You need some initial information to initialize the state in the reader. That would be (1) input file descriptions, checksums, etc. and (2) the number of recovery buffers to allocate and their coefficients. Then, as data was downloaded, you need to identify what input slice it was, write it to the correct place in the file, and subtract its effect from each of the N recovery buffers. Lastly, when all the data had been downloaded, you need to identify the K slices that need recover. If K < N, download the recovery data for K slices, add it to the appropriate recovery buffer, solve the matrix, and write out the recovered data.

If you assume the initial information is the no-recovery-slice Par2 file, then the only thing we are missing is the number of recovery slices and their coefficients. An adventurous client could guess those from the names of Par2 files. Or we could put that data in the Par2 files. That is, a new packet that is a hint to the repair client about the number of buffers to allocate.

Streaming would use a lot of CPU and storage unnecessarily, but it would be cool to try. I like that the downloading program would know exactly where to put the data blocks and the client wouldn't need the logic to rewrite the data files.

[animetosho]

I'm not sure about collecting use cases, but some ideas are listed here.
I think all text fields should be defined as UTF-8 (edit: looks like you've already done this), which makes the "unicode" (presumably fixed-length UCS-2, though encoders would likely use variable length UTF-16 regardless) packets redundant. Actually, I'm always already using UTF-8 for the "ASCII packets" anyway - despite what the standard says, many clients just use whatever the default system codepage is for these. If you have non-ASCII characters, the filename will be barfed whatever you do, but UTF-8 is generally more "kind" in these situations, and if the system codepage is UTF-8, it could just work anyway.

Do people really want >32,000 blocks? Each block adds overhead (CRC32 and MD5 checksum).

The overhead is relatively small for larger blocks, e.g. 1MB blocks. However, even at 1MB blocks, 32k means you can't have more than 32GB in a Parchive without increasing block size. Though not common, it's not too unusual to have >32GB files today. And if we're thinking about a format which is to last the next 10-20 years, it can feel a little limiting.
I suppose how large blocks should be does become a bit of an open question, but I'd like to think that the block size should increase at a slower rate relative to the amount of data typically covered by Parchive.

Streaming is possible with minor changes.

As you alluded to, it's already possible (most of the time) without any change, though the decoder may need to be a little clever about it.

Knowing how many recovery blocks are available may actually not be necessary, and in fact, may be largely irrelevant (at least for the downloader use case).
To expand on that, in most cases, K (damaged blocks) is significantly smaller than N (available recovery blocks), so it's somewhat of a waste of resources to compute on N recovery blocks during download. Now in a pure streaming situation, you don't have much choice, but for the download situation, you can always go back and compute any additional recovery you need, if there was more damaged blocks than you initially guessed.
This greatly reduces CPU/RAM usage (vs computing all recovery), and seems to be a practical optimisation for the use case. Particularly since downloading is often network bandwidth limited, followed by I/O, whilst CPU is often fairly idle; it makes some sense to expend some idle CPU resources to potentially speed up the process. For example, a downloader may choose to always compute 32 recovery blocks during download, regardless of availability; as the download is network bound, this only increases CPU usage a little, but doesn't otherwise impact download speed. When the download is complete, if there are fewer than 32 damaged blocks, they can be repaired without re-reading the downloaded files off disk. If there are more than 32 bad blocks, you'll need to re-read the files to compute all the needed blocks, but in this case, the previously computed blocks can actually be re-used to reduce the amount of computation needed.

The remaining issue is the recovery coefficients. These could be guessed from the filenames, as you pointed out, though you could also just guess the first few coefficients typically used as there's generally little reason that an encoder wouldn't use those.
If the assumptions don't hold here (e.g. no index file present, or unexpected coefficients), the downloader can just fall back to existing less efficient techniques. This is for the downloader case though, where pure streaming isn't a requirement, rather, it's only an optimisation.

Encoding in a streaming fashion is a little easier than verify/repair, since the create tool has full control over the process. The primary limitation here is being able to fit all recovery blocks in memory.

(note that the ParPar project wasn't aimed at changing PAR2, rather, at working within its bounds)

---

Yutaka Sawada added another note:

Though this isn't serious problem, checksum in PAR2 (CRC-32 and MD5) would better be changed in the future version. For example, BLAKE2 is faster and safer than MD5. CRC-64 is faster and has less collision than CRC-32, but it requires additional 4-bytes. Because BLAKE2 has no disadvantage, there is no reason to avoid it. Using MD5 for a new specification may be obsolate. Because CRC-64 is double size than CRC-32, it gives slightly larger recovery files. For current max 32768 blocks (or files), CRC-32 is enough. If new spec supports more blocks, CRC-64 will be preferable. (It depends on how many blocks.)

I put some paper of BLAKE2, CRC-64, and MD5's collision.

Filename: blake2.pdf
"BLAKE2: simpler, smaller, fast as MD5"
by Jean-Philippe Aumasson, Samuel Neves, Zooko Wilcox-O'Heam, Christian Winnerlein

Filename: nguyen_Fast_CRC_2012.02.20.pdf
"Fast CRCs"
by Gam D. Nguyen
Naval Research Laboratory

Filename: md5_crc32_hack.zip
"How to Break MD5 and Other Hash Functions"
by Xiaoyun Wang and Hongbo Yu
(I include sample data and PAR files to test.)

[mdnahas]

My opinion was that UTF-8 support was discussed and approved by Peter B. Clements and a bunch of us and approved. I may add that to the "spec" section of the new webpage as a 2.0.1 spec.

The list of use cases include:

1. streaming = generate recovery data while input is in transmission; use the recovery data to fix missing slices after transmission finishes.
2. easier single-pass file recovery (which is very similar to streaming)
3. incremental operation = ability to add source files not recalculate the entire recovery file
4. changing names of source files
5. support for more blocks
   And, of course, faster encoding and decoding. And a fix to Plank's Reed-Solomon encoding.

I'll have to think about "repair Par2 files" as a use case. I understand the desire for it. If you're transmitting files, you want to restore them to the original state before re-transmitting them. If you've done a backup, you'd like to restore every damaged disk image to the original state before re-burning it. I've usually assumed clients have the freedom to determine how many times to repeat the un-recoverable packets (and their placement in the files). This can probably be accomplished by a "suggested file layout" without a strict requirement.

I don't know about fixing small errors, like adding/dropping/changing a byte. I'm just not sure how to do that - especially adds and drops. It feels like a separate file format should be used for that.

I've already discussed how to stream with Par2. It takes some guesses, but I think it would work in practice. The only change I could even suggest was a packet that hinted about the exponents of recovery packets and, even then, it would only be a hint.

The big stumbling block is the changing filenames and incremental changes. The easiest fix here is just to open up more freedom in the Par2 standard. Do not require (always) for the FileIDs to be listed in sorted order in the main packet. We can consider if we also want to allow FileIDs or the RecoverySetID to be something other than its current definition, but changing the main packet order is necessary and sufficient. Those changes can done by a "Par version 2.0.2" amendment. And we could include the suggested file layout with it too.

There are reasons to go to a "Par3": more blocks, fixing Reed-Solomon, and replacing MD5 with a faster/better-suited hash. I think adding LDPC is the easy way to get to more blocks. And it would keep the Reed-Solomon matrix small, if we used Plank's correction which requires sloooow Gaussian Elimination. (I don't understand the FFT version yet.)

But simple changes to Par2 might get us a few more use cases for people.

[animetosho]

Yeah, those small changes to PAR2 could definitely open things up a little, and there's a good chance that existing PAR2 clients would already be fully compatible with them anyway.

I found a page where someone else was investigating a PAR2 successor, which may have some ideas+thoughts (haven't really read through it).

Some ideas I just thought up for a "PAR3" (may not be a good idea, just mentioning them):

• filename compression: this probably will only be useful for those dealing with lots of small files, and probably not worth the complexity. But maybe if we have some directory structure, we can get a fair portion of the benefits of size reduction without much additional complexity (I recall that the full path needs to be specified for each file in PAR2, so by eliminating common path elements might be useful)
• define how empty (0-byte) files are handled? Some clients place them in the recovery section, others place them in the non-recovery section. For the sake of consistency, it may be worth making a decision on that in the spec?
• extensibility: I presume that this will be included anyway, but including algorithm indicators (like what erasure scheme is used, or what hash algorithm is used) can help extensibility. Another area may be allowing for optional fields, such as additional file properties or the like, should a use case ever come up, which can aid with new features and backwards compatibility
• removing files from a Parchive? I imagine this to be similar to adding files, but this does introduce the notion of "holes" (missing input slices) in the input, which I don't think the current PAR2 would handle well

User maosredbrook gives the interesting idea of a RAR-esque usage of storing input files in Parchive with optional encryption. PAR2 already supports embedding input slices, though I'm not sure how useful that feature is. Another option is that, since decoders have to scan for packet headers, one can embed (concatenate onto the end) a PAR2 archive into another file. This can be used to, say, tack on recovery information to an archive which doesn't support repair (e.g. 7z), and the file still remains usable (as long as the application doesn't make assumptions on what's at the end of the file). "Extracting" the file would just be like stripping off the PAR2 packets off the end.
This embedding also allows an application to use some existing encryption technique without Parchive needing to support it (I don't feel that encryption should be part of Parchive).
If it's not there already, do you think it'd be worthwhile mentioning something about embedding in the Parchive spec?

---

Yutaka Sawada writes:

By the way, PAR2 might try to solve the max 32768 blocks (or files) problem. They are optional "Packed Main packet" and "Packed Recovery Slice packet". If new spec merges such idea in standard packet, there will be no limit of blocks (or files). For example, "Main packets" includes "Subslice size" always, as if it was a packed one. It needs to consider how are slice and subslice relation and usage.

Small improvement is better than nothing. I could not solve a dilemma; fast speed vs recovery performance. (For example, LDPC is very fast, but requires more recovery data.) If someone knows a problem of current PAR2, or comes up with a good idea, he may post his thought on the par2cmdline page. I expect that Michael Nahas will realize our hope.

My understanding of the packed slices feature is that it doesn't increase the number of available slices in any way, rather, the only thing it does is allow input files to be more tightly packed, since they don't have to be padded to a full slice (only to a subslice). If my understanding is correct, one could always just set the subslice to 4 bytes and gain maximum efficiency with packing files, with little downside (other than some additional complexity in decoders?). Adding subslice hashes could make the feature more useful as smaller erasures can be identified, and actually gives a penalty for using tiny (i.e. 4 byte) subslices. It's not quite the same as enabling more slices overall however (which can be more useful in cases when you're encoding input of unknown length).

[mdnahas]

The comment about removing files (and leaving some coefficients missing) is a good note. I hadn't thought of that.

0-length files are within the spec. Clients can put them either in the recovery set or the non-recovery set. Either way of doing them is fine. The non-recovery set was only added for backwards compatibility, so I'd prefer including them in the recovery set. The only bad way of handling them is the way that par2cmdline does - which is not at all. They get ignored!

As for compression, encryption, permissions, many files, etc., I'm an old UNIX junkie, so I think there are many other programs that handle that better. gzip, gpg, tar, etc.. I'd rather have someone run many tools that do each thing well, rather than build it all into Par.

I really wished some client had implemented the "input slices" optional feature. Many large files are already compressed. Many posters on Usenet were using RAR to split up a file and not for compression/permissions/etc.. I was really hoping a Par client would eliminate the use of RAR. But, as before, I wouldn't include encryption. There are other programs that do that better. ... if you we do a Par3, what do you think of making that a required packet type?