An idea worth considering (error detection and correction in MATROSKA)

[fatso485]

An idea worth considering (error detection and correction on matroksa)


The worse thing that bugs me when dealing with AVI files is errors and how to deal with them. I really want matroksa to have significantly better error handling mechanisms.

Here is how it should work: a small info (text) (should be around 15-20Kbytes) is multiplexed with the video, audio, subtitles ..etc. this file will contain the name of the file, size, FPS, resolution …etc and a CRC table with N number of entries.

Where N = movie size / block size

So if the block size = 256k (the block size should be standardized. But I think 16 or 32k is good ) the number of entries of the CRC table will be 700mb / .25mb = 2800 entries. Now that we have divided the movie to 2800 “virtual” parts its time to get the CRC number for each part and put it in the corresponding entry in the table. Now we have a table with 2800 CRC numbers that correspond to each part of the movie.

Now lets suppose that you download the files from whatever source. To check if the file has errors. A small utility will generate a new CRC table identical to the one that was created when everything was multiplexed together. If there is no error, then all the entries in the table will be the same. If an error occurs one or more enties will have different CRC values. To fix the file all you have to do is to send this created file to someone who has the original file. At the recievers end (the one with the error-free file) the utility will automatically extract the parts that have different CRC numbers. After the extracted parts are sent to the original guy, the utility can can remux everything with the new correct file. Or if the user is too lazy, the matroska filter could load these Patches to memory first, and when the movie plays, the video and audio in these patches get decoded instead of the one in the main file.

this idea needs to be polished quite a bit. But what do you think?


Sami

[ChristianHJW]

well, relax and lean back .... we have put quite some time into thinking how to make error correction and detection in matroska, as well as making it attractive for p2p apps ...

[mf]

Originally posted by ChristianHJW
well, relax and lean back .... we have put quite some time into thinking how to make error correction and detection in matroska, as well as making it attractive for p2p apps ...
You mean, seperate in 9MB chunks each with their own MD5 hash (so eDonkey/eMule/mldonkey won't have to compute them), and make a file with chunks missing in the middle playable? :D

[unmei]

Bittorrent does exactly that . well i know its not exactly 'filesharing', but you could talk to its developer making it easier to serve files with it and you had what you want. IMHO this more belongs to the sharing universe than the production/playback universe (dont blame the video if your P2P application is too stupid)

[Atamido]

@mf: What you are talking about it what is currently used to distribute large files on newsgroups. The file is broken into several smaller RAR files of the same size. Then a utility is used to create a Parchive (http://parchive.sourceforge.net/). A Parchive is basicaly a set of files, the same size as the files in the set, that can be used to recreate missing or damaged files much like a RAID5 set up would for hardrives. (Touch the link for more information.) Unfortunately this isn't terribly useful in the design of Matroska. This recovery method is more useful outside of the original files. (PAR2.0 would be more practical for this, but there is not yet a full implementation of it.)

@fatso485: I think the original intent of CRC/ECC was retrieving the data from a damaged medium, so I will comment on that.

First, a basic understanding of the structure of a Matroska file is necessary. The whole file is called a Segment. Within the Segment, there are usually several Clusters. And within a Cluster, there are usually several Blocks. Each block contains one Video frame, or one audio frame. Each block also contains the exact time that that frame should be displayed/played, and the track number that it belongs to. It would looka something like this:

(*************Segment*************)
(**Cluster***)(******Cluster******)
(Block)(Block)(Block)(Block)(Block)

The number of blocks and the size of each cluster is variable. The limit set by whatever application is writing the file, and is based on the total size of the cluster and the total length of time the cluster covers. Currently I think the applications have this limit at 5MB or 3 seconds per cluster(Maybe ~100 blocks in a cluster?). In theory you could have several hours worth of Blocks in a cluster. But, breaking it into more clusters helps to localize errors, and helps with seeking.

Okay, back to the error recovery. It would be very feasible to have several ECC elements in the cluster. These would basicaly act the same as the Parchive files mentioned above where having several ECC elements in a cluster would allow you to recover several damaged blocks. It would be more effiecient to have these for the whole file, but this would not be practical during playback as it has to read from every valid data chunk to recreate the damaged ones.

However, if done on the cluster level, it would be a small matter for a modern computer to buffer 5MB of clusters in RAM and recreate the damaged Blocks on the fly. (Again, this would be much more practicaly with the PAR2.0 approach)

[mf]

Originally posted by Pamel
@mf: What you are talking about it what is currently used to distribute large files on newsgroups. The file is broken into several smaller RAR files of the same size. Then a utility is used to create a Parchive (http://parchive.sourceforge.net/). A Parchive is basicaly a set of files, the same size as the files in the set, that can be used to recreate missing or damaged files much like a RAID5 set up would for hardrives. (Touch the link for more information.) Unfortunately this isn't terribly useful in the design of Matroska. This recovery method is more useful outside of the original files. (PAR2.0 would be more practical for this, but there is not yet a full implementation of it.)
That's not what I meant. The eDonkey protocol chops files up in 9MB chunks, which are each assigned an MD5 hash. AVI Files are not previewable if you don't have the chunk at the end, and the chunk at the beginning, and you cannot just play the file without problems if there's gaps in the middle. So fixing that would make it attractive for p2p, that's what I meant.

[Atamido]

I understand what you meant, it just wasn't very practicle. Because of the design of EBML, adding the parity information within the file would change the structure of the file, negating the parity information. Also, this would increase the size of every file sent by a certain percent. Lets say 10% just for giggles. That means for a 700MB file, you would have to download 770MB, whether or not you were going to have a problem with the file. This issue is more of a problem with the p2p application than the file structure themselves. The only reason that you should be missing those missing those chunks of data is if the machines you are downloading from go offline, in which case you would still have to much information missing to do anything about it. Example: You are downloading a 700MB file, but all of the machines you are downloading from go offline, leaving you with a 670MB file. Had you been downloading the same file with parity, it would be (for this example) a 770MB file, but you still would have only gotten 670MB of it, not enough to recover any of it.

If the p2p application only downloads a corrupted data chunk of 9MB and does not redownload that same chunk, then that would be poor design on the part of the p2p application. If it downloaded a corrupted data chunk and kept it, then the error recovery that I was refering to could recover those blocks at the cluster level (assuming the data corruption was localized and not to large).

[fatso485]

thanks guys very good information keep it going . but i still want to know your thoughts if something like what i'm saying worth including in the container.

i think worth it because the overhead is very little + if you have a feature like that that comes as a standard with the matroska filter (and not just a feature in an application that is not even known) this would significantly increase its usage in the comunity.

[robUx4]

OK, let's see what kind of errors are possible in a multimedia file : media error (damaged CD), incomplete download (the end is missing), partial download (some parts are missing in the file), streaming errors (idem to partial download).

For the first one (mode 2 form 2 CD) the playback will still work as long as you have the Tracks element not damaged. The damaged parts will be detected and skipped (by checking incoherent values).
That means we have to protect the Tracks entry (with a good ECC) and maybe some EDC info in the Clusters. If you want close to 100% chances to always play your files, then you will need some more ECC to cover the whole file. Paranoid people should use some PAR files like described by Pamel. But this is impossible for Mode 2 Form 2 where everything has to be contained in one file (am I right ?).

For an incomplete download, no problem the file will play until the end of the downloaded part. No need for extra EDC or ECC.

For parts missing in the file, if the Tracks entry is not fully downloaded, you won't be able to play the file (it may crash your application). Otherwise you will be able to read the file the same way as for a CD (incoherent parts will be skipped). So it's really equivalent.

And streaming errors (over UDP) is also equivalent to a damaged CD (well there are other problems involved too).

Conclusion : the most sensitive case is Mode 2 Form 2 CDs. We need to protect the Tracks entry with ECC in this case. And that may also be a good general behaviour. Otherwise there should be EDC possible to detect errors in a Cluster (but then what ? you don't play the Cluster ? Or you try it anyway ?)

We were already aware of these problem and also have some ideas to correct that. It's not fully documented and not implemented yet.

[mf]

Originally posted by Pamel
I understand what you meant, it just wasn't very practicle.

Nope, you didn't. You still don't.
If the p2p application only downloads a corrupted data chunk of 9MB and does not redownload that same chunk, then that would be poor design on the part of the p2p application. If it downloaded a corrupted data chunk and kept it, then the error recovery that I was refering to could recover those blocks at the cluster level (assuming the data corruption was localized and not to large).
That's still not what I meant. eDonkey automatically redownloads corrupted chunks. What I meant was:

Originally posted by robUx4
For parts missing in the file, if the Tracks entry is not fully downloaded, you won't be able to play the file (it may crash your application). Otherwise you will be able to read the file the same way as for a CD (incoherent parts will be skipped). So it's really equivalent.
That's what I meant. Contain everything within 9MB chunks, so that your file structure is always intact if 9MB chunks are missing. And that missing parts will just be skipped. But my first post in this thread was really more of a joke than anything serious, as I don't think p2p support in-format is really useful.