[Dvd-devel] mkisofs patch

[Joe Feise]

Hi guys,

A recent discussion on LWN pointed me to here...
I have an mkisofs patch that can dramatically speed up ISO fs creation if there
are lots of files with similar names (e.g., a qmail Maildir directory.)
I had sent this patch to Joerg Schilling 2 years ago, but he still hasn't put it
in the source.
Some more background is here: http://www.feise.com/~jfeise/download/mkisofs/

I had to modify the patch a bit for the different build system, but other than
that, it seems to work fine.

Cheers,
-Joe

diff -urN trunk/mkisofs.orig/Makefile.am trunk/mkisofs/Makefile.am
--- trunk/mkisofs.orig/Makefile.am      2006-08-13 13:20:20.000000000 -0700
+++ trunk/mkisofs/Makefile.am   2006-08-13 13:21:06.000000000 -0700
@@ -10,7 +10,7 @@
 
 mkisofs_SOURCES = mkisofs.c tree.c write.c hash.c rock.c udf.c multi.c \
                joliet.c match.c name.c fnmatch.c eltorito.c boot.c \
-               getopt.c getopt1.c \
+               getopt.c getopt1.c nameconflict.c \
                scsi.c \
                ../dvdrecord/scsi_cdr.c ../dvdrecord/cd_misc.c \
                ../dvdrecord/modes.c \
diff -urN trunk/mkisofs.orig/mkisofs.h trunk/mkisofs/mkisofs.h
--- trunk/mkisofs.orig/mkisofs.h        2006-08-13 13:20:20.000000000 -0700
+++ trunk/mkisofs/mkisofs.h     2006-08-13 13:21:06.000000000 -0700
@@ -564,6 +564,10 @@
 
 #endif
 
+extern char    *find_good_file (char *);
+extern void    flush_file_list (void);
+
+
 #ifdef APPLE_HYB
 /* volume.c */
 extern int make_mac_volume (struct directory * dpnt, int start_extent);
diff -urN trunk/mkisofs.orig/nameconflict.c trunk/mkisofs/nameconflict.c
--- trunk/mkisofs.orig/nameconflict.c   1969-12-31 16:00:00.000000000 -0800
+++ trunk/mkisofs/nameconflict.c        2006-08-13 13:21:28.000000000 -0700
@@ -0,0 +1,132 @@
+/*
+ * File nameconflict.c - resolve name conflicts for iso9660 names
+ *
+ * Implements a simple linear list of basenames and the last substitute
+ * name used for each basename.
+ * This speeds up finding substitute names in cases with lots of
+ * conflicts.
+ * Example:
+ * Qmail Maildir directories can contain 1000s of files which map to
+ * the same 8.3 iso9660 name, like the following:
+ * 1041126815.10257_18134.pv182069,S=224616:2,S
+ * 1041126815.10257_18135.pv182069,S=1546:2,S
+ * 1041126815.10257_18136.pv182069,S=6036:2,S
+ * 1041126815.10257_18137.pv182069,S=1635:2,S
+ * 1041126815.10257_18139.pv182069,S=2090:2,S
+ * 1041126815.10257_18140.pv182069,S=2966:2,S
+ * 1041126815.10257_18141.pv182069,S=1867:2,FRS
+ * These files all map to 10411268.pv1
+ *
+ * Copyright (C) 2004 J. Joe Feise <jfeise at feise dot com>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2, or (at your option)
+ * any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ */
+
+#include <mconfig.h>
+#include "mkisofs.h"
+
+typedef struct file_node_struct
+{
+       struct file_node_struct *next;
+       char basename[MAX_ISONAME+1];
+       char substitution[MAX_ISONAME+1];
+       int d1;
+       int d2;
+       int d3;
+} file_node;
+
+static file_node *file_list = (file_node*)NULL;
+
+
+char *add_good_file(file_node *entry, char *basename)
+{
+       char substitution[MAX_ISONAME+1];
+
+       if (!entry)
+               return (NULL);  /* trouble */
+       entry->next = NULL;
+       strncpy(entry->basename, basename, MAX_ISONAME-3);
+       entry->basename[MAX_ISONAME-3] = '\0';  /* guard against overflow */
+
+       entry->d1 = entry->d2 = entry->d3 = 0;
+       sprintf(substitution, "%s%c%c%c", basename,
+               (entry->d1 <= 9 ? '0' + entry->d1 : 'A' + entry->d1 - 10),
+               (entry->d2 <= 9 ? '0' + entry->d2 : 'A' + entry->d2 - 10),
+               (entry->d3 <= 9 ? '0' + entry->d3 : 'A' + entry->d3 - 10));
+       strncpy(entry->substitution, substitution, MAX_ISONAME+1);
+       return (entry->substitution);
+}
+
+
+char *inc_substitution(file_node *entry)
+{
+       char substitution[MAX_ISONAME+1];
+
+       entry->d3++;
+       if (entry->d3 == 36) {
+               entry->d3 = 0;
+               entry->d2++;
+               if (entry->d2 == 36) {
+                       entry->d2 = 0;
+                       entry->d1++;
+                       if (entry->d1 == 36)
+                               return (NULL);  /* trouble */
+               }
+       }
+       sprintf(substitution, "%s%c%c%c", entry->basename,
+               (entry->d1 <= 9 ? '0' + entry->d1 : 'A' + entry->d1 - 10),
+               (entry->d2 <= 9 ? '0' + entry->d2 : 'A' + entry->d2 - 10),
+               (entry->d3 <= 9 ? '0' + entry->d3 : 'A' + entry->d3 - 10));
+       strncpy(entry->substitution, substitution, MAX_ISONAME+1);
+       return (entry->substitution);
+}
+
+
+char *find_good_file(char *basename)
+{
+       file_node *entry = file_list;
+       file_node *next;
+
+       if (!file_list) {
+               file_list = e_malloc(sizeof (file_node));
+               return (add_good_file(file_list, basename));
+       } else {
+               next = entry;
+               do {
+                       entry = next;
+                       if (strncmp(entry->basename, basename, MAX_ISONAME) == 
0) {
+                               return (inc_substitution(entry));
+                       }
+                       next = entry->next;
+               } while (next);
+               entry->next = e_malloc(sizeof (file_node));
+               entry = entry->next;
+               return (add_good_file(entry, basename));
+       }
+}
+
+
+void flush_file_list()
+{
+       file_node *entry = file_list;
+       file_node *next;
+
+       while (entry) {
+               next = entry->next;
+               free(entry);
+               entry = next;
+       }
+       file_list = (file_node*)NULL;
+}
diff -urN trunk/mkisofs.orig/tree.c trunk/mkisofs/tree.c
--- trunk/mkisofs.orig/tree.c   2006-08-13 13:20:20.000000000 -0700
+++ trunk/mkisofs/tree.c        2006-08-13 13:21:06.000000000 -0700
@@ -267,6 +267,7 @@
        char            newname[MAX_ISONAME+1];
        char            rootname[MAX_ISONAME+1];
        char            extname[MAX_ISONAME+1];
+       char            *newentry;
 
        /*
         * Here we can take the opportunity to toss duplicate entries from the
@@ -290,6 +291,7 @@
                attach_dot_entries(this_dir, &fstatbuf);
        }
        flush_file_hash();
+       flush_file_list();
        s_entry = this_dir->contents;
        while (s_entry) {
                /* ignore if it's hidden */
@@ -370,35 +372,49 @@
                        if (d1 > 5)
                                rootname[5] = 0;
                }
-               for (d1 = 0; d1 < 36; d1++) {
-                       for (d2 = 0; d2 < 36; d2++) {
-                               for (d3 = 0; d3 < 36; d3++) {
-                                       sprintf(newname, "%s%c%c%c%s%s",
-                                       rootname,
-                                       (d1 <= 9 ? '0' + d1 : 'A' + d1 - 10),
-                                       (d2 <= 9 ? '0' + d2 : 'A' + d2 - 10),
-                                       (d3 <= 9 ? '0' + d3 : 'A' + d3 - 10),
-                                       extname,
-                                       ((s_entry->isorec.flags[0] & 
ISO_DIRECTORY) ||
-                                       omit_version_number ? "" : ";1"));
 
-#ifdef VMS
-                               /* Sigh.  VAXCRTL seems to be broken here */
-                                       {
-                                               int     ijk = 0;
-
-                                               while (newname[ijk]) {
-                                                       if (newname[ijk] == ' ')
-                                                               newname[ijk] = 
'0';
-                                                       ijk++;
-                                               }
-                                       }
-#endif
+               /*
+                * Filename substitution always starts at 000.
+                * It can happen that an intended substitution already exists.
+                * For example, assume there is a file named ABCDE002.EXT.
+                * If ABCDEFGHIJK.EXT would map to ABCDE002.EXT, we have
+                * to find another substitution, e.g., to ABCDE003.EXT.
+                * Example mappings:
+                * ABCDE002.EXT         -> ABCDE002.EXT
+                * ABCDEFGH.EXT         -> ABCDEFGH.EXT
+                * ABCDEFGHI.EXT        -> ABCDE000.EXT
+                * ABCDEFGHIJ.EXT       -> ABCDE001.EXT
+                * ABCDEFGHIJK.EXT      -> ABCDE003.EXT
+                */
 
-                                       if (!find_file_hash(newname))
-                                               goto got_valid_name;
+               newentry = find_good_file(rootname);
+               while (newentry) {
+                       sprintf(newname, "%s%s%s",
+                               newentry,
+                               extname,
+                               ((s_entry->isorec.flags[0] & ISO_DIRECTORY) ||
+                               omit_version_number ? "" : ";1"));
+                       if (debug)
+                               error("NEW name '%s'\n", newname);
+
+#ifdef VMS
+                       /* Sigh.  VAXCRTL seems to be broken here */
+                       {
+                               int     ijk = 0;
+
+                               while (newname[ijk]) {
+                                       if (newname[ijk] == ' ')
+                                               newname[ijk] = '0';
+                                       ijk++;
                                }
                        }
+#endif
+
+                       if (!find_file_hash(newname))
+                               goto got_valid_name;
+
+                       /* the filename was already used for some other file */
+                       newentry = find_good_file(rootname);
                }
 
                /* If we fell off the bottom here, we were in real trouble. */