Index of /~jfeise/Downloads/mkisofs

[ICO]NameLast modifiedSizeDescription

[TXT]mkisofs-2.01.01a04.diff2006-01-12 16:57 7.9K 
[TXT]mkisofs-2.01.01a04_a.diff2006-02-15 16:16 7.9K 
[TXT]mkisofs-2.01.01a06.diff2006-02-14 21:24 8.0K 
[TXT]mkisofs-2.01.01a29.diff2007-07-15 01:04 7.7K 
[TXT]mkisofs-2.01.01a37.diff2008-01-06 03:05 7.7K 
[TXT]mkisofs-2.01.01a58.diff2009-04-16 06:01 7.7K 
[TXT]mkisofs-2.01.01a67.diff2009-11-11 17:26 7.7K 
[TXT]mkisofs-2.01.01a75.diff2010-02-10 05:26 7.7K 
[TXT]mkisofs-2.01.diff2004-10-06 15:48 7.8K 
[TXT]mkisofs-3.01a06.diff2011-12-12 02:39 7.7K 
[TXT]mkisofs-latest.diff2011-12-12 02:39 7.7K 

This directory contains a patch to speed up the filename mapping in mkisofs.

Background:
mkisofs has to map filenames as they exist in the filesystem to shorter names as specified
by the ISO9660 specification.
Some example mappings:
* ABCDE000.EXT         => ABCDE000.EXT
* ABCDEFGH.EXT         => ABCDEFGH.EXT
* ABCDEFGHI.EXT        => ABCDE001.EXT
* ABCDEFGHIJ.EXT       => ABCDE002.EXT
* ABCDEFGHIJK.EXT      => ABCDE003.EXT
In mkisofs, this mapping is done with three nested for-loops.  Unfortunately, the
for-loops start at 0 each time around.
So, for the ABCDEFGHIJK.EXT example above, a mapping to ABCDE000.EXT is tried first, then
a mapping to ABCDE001.EXT, etc., until arriving at the available mapping to ABCDE003.EXT.
If these tests have to be done for thousands of files, the result is a significant
slowdown of the operation of mkisofs.

I have encountered this problem while trying to back up a Qmail mail directory in Maildir
format containing about 2GB of email files (Qmail stores each email in a separate file.)
Qmail saves the files with the inode number as filename. That results in lots of small
files with names like
1012499458.30538_100.abcd,S\=2001:2,S
1012499458.30538_101.abcd,S\=19968:2,S
1012499458.30538_102.abcd,S\=18643:2,S
etc.
mkisofs uses these names to create unique short names like  10124000.abc;1,
10124001.abc;1, ... for the iso fs.  The operation of the nested for-loops resulted in
mkisofs to run for over a day, at which time I aborted it and went to look for the reason
for the slowdown.

My patch saves the indexes from the last execution of the for-loops, and starts the next
run through the for-loops at these indexes, thereby saving the unneccessary check for
usable unique short names when it is known that this check failed in an earlier iteration.
An illustration, using the example from above:
The mapping ABCDEFGHIJ.EXT -> ABCDE002.EXT results in the "basename" ABCDE and the
indexes (0, 0, 2) being stored.
For the mapping of ABCDEFGHIJK.EXT the search for a unique filename starts at indexes
0, 0, 3, resulting in an immediate find of ADBCDE003.EXT without the wasted efforts of
checking ABCDE000.EXT to ABCDE002.EXT, which are already used by other files.

The running time in Big-O notation of the original mkisofs filemapping is O(n^2), whereas
the running time of my patch is O(n).

This patch has been submitted several years ago (Sep. 2004) to the mkisofs maintainer,
Joerg Schilling. Unfortunately, Mr. Schilling, not giving any reason, has not applied
it to the mkisofs codebase. He improved the nested for-loops a little bit, by moving
static code out of the inner loop and changing the hash function used. That of course
doesn't change the Big-O running time, so this patch continues to be a vast improvement
over the stock mkisofs code.

The latest version is always available as mkisofs-latest.diff

History:
	mkisofs-3.01a06.diff	Updated patch for the cdrtools-3.01a06 release
	mkisofs-2.01.01a75.diff	Updated patch for the cdrtools-2.01.01a75 release
	mkisofs-2.01.01a67.diff	Updated patch for the cdrtools-2.01.01a67 release
	mkisofs-2.01.01a58.diff	Updated patch for the cdrtools-2.01.01a58 release
	mkisofs-2.01.01a37.diff	Updated patch for the cdrtools-2.01.01a37 release
	mkisofs-2.01.01a29.diff	Updated patch for the cdrtools-2.01.01a29 release
	mkisofs-2.01.01a06.diff	Updated patch for the cdrtools-2.01.01a06 release
	mkisofs-2.01.01a04_a.diff  Corrected patch for the cdrtools-2.01.01a04 release
	mkisofs-2.01.01a04.diff	Patch for the cdrtools-2.01.01a04 release
	mkisofs-2.01.diff	Initial release