Imported Upstream version 1.1.11upstream/1.1.11upstream

1 files changed, 404 insertions, 0 deletions

diff --git a/genisoimage/hash.c b/genisoimage/hash.c
new file mode 100644
index 0000000..054aea6
--- /dev/null
+++ b/genisoimage/hash.c
@@ -0,0 +1,404 @@
+/*
+ * This file has been modified for the cdrkit suite.
+ *
+ * The behaviour and appearence of the program code below can differ to a major
+ * extent from the version distributed by the original author(s).
+ *
+ * For details, see Changelog file distributed with the cdrkit package. If you
+ * received this file from another source then ask the distributing person for
+ * a log of modifications.
+ *
+ */
+
+/* @(#)hash.c	1.18 04/06/18 joerg */
+/* @(#)hash.c	1.23 06/10/04 joerg */
+/*
+ * File hash.c - generate hash tables for iso9660 filesystem.
+ *
+ * Written by Eric Youngdale (1993).
+ *
+ * Copyright 1993 Yggdrasil Computing, Incorporated
+ * Copyright (c) 1999,2000-2006 J. Schilling
+ *
+ * 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.
+ */
+
+/* APPLE_HYB James Pearson j.pearson@ge.ucl.ac.uk 23/2/2000 */
+
+/*
+ * From jb@danware.dk:
+ *
+ * Cygwin fakes inodes by hashing file info, actual collisions observed!
+ * This is documented in the cygwin source, look at winsup/cygwin/path.cc
+ * and search for the word 'Hash'.  On NT, cygwin ORs together the
+ * high and low 32 bits of the 64 bit genuine inode, look at fhandler.cc.
+ *
+ * Note:	Other operating systems which support the FAT filesystem may
+ *		have the same problem because FAT does not use the inode
+ *		concept.  For NTFS, genuine inode numbers exist, but they are
+ *		64 bits and available only through an open file handle.
+ *
+ * The solution is the new options -no-cache-inodes/-cache-inodes that
+ * allow to disable the genisoimage inode cache.
+ */
+
+#include <mconfig.h>
+#include "genisoimage.h"
+#include <schily.h>
+
+#define	NR_HASH	(16*1024)
+
+#define	HASH_FN(DEV, INO)	((DEV + INO  + (INO >> 8) + (INO << 16)) % NR_HASH)
+
+static struct file_hash *hash_table[NR_HASH];
+
+void		add_hash(struct directory_entry *spnt);
+struct file_hash *find_hash(dev_t dev, ino_t inode);
+void		flush_hash(void);
+void		add_directory_hash(dev_t dev, ino_t inode);
+struct file_hash *find_directory_hash(dev_t dev, ino_t inode);
+static	unsigned int	name_hash(const char *name);
+void		add_file_hash(struct directory_entry *de);
+struct directory_entry *find_file_hash(char *name);
+static	BOOL		isoname_endsok(char *name);
+int		delete_file_hash(struct directory_entry *de);
+void		flush_file_hash(void);
+
+void
+add_hash(struct directory_entry *spnt)
+{
+	struct file_hash *s_hash;
+	unsigned int    hash_number;
+
+	if (spnt->size == 0 || spnt->starting_block == 0)
+		if (spnt->size != 0 && spnt->starting_block == 0) {
+			comerrno(EX_BAD,
+			"Non zero-length file '%s' assigned zero extent.\n",
+							spnt->name);
+		};
+
+	if (!cache_inodes)
+		return;
+	if (spnt->dev == UNCACHED_DEVICE &&
+	    (spnt->inode == TABLE_INODE || spnt->inode == UNCACHED_INODE)) {
+		return;
+	}
+	hash_number = HASH_FN((unsigned int) spnt->dev,
+						(unsigned int) spnt->inode);
+
+#if 0
+	if (verbose > 1)
+		fprintf(stderr, "%s ", spnt->name);
+#endif
+	s_hash = (struct file_hash *) e_malloc(sizeof (struct file_hash));
+	s_hash->next = hash_table[hash_number];
+	s_hash->inode = spnt->inode;
+	s_hash->dev = spnt->dev;
+	s_hash->nlink = 0;
+	s_hash->starting_block = spnt->starting_block;
+	s_hash->size = spnt->size;
+#ifdef SORTING
+	s_hash->de = spnt;
+#endif /* SORTING */
+	hash_table[hash_number] = s_hash;
+}
+
+struct file_hash *
+find_hash(dev_t dev, ino_t inode)
+{
+	unsigned int    hash_number;
+	struct file_hash *spnt;
+
+	if (!cache_inodes)
+		return (NULL);
+	if (dev == UNCACHED_DEVICE &&
+	    (inode == TABLE_INODE || inode == UNCACHED_INODE))
+		return (NULL);
+
+	hash_number = HASH_FN((unsigned int) dev, (unsigned int) inode);
+	spnt = hash_table[hash_number];
+	while (spnt) {
+		if (spnt->inode == inode && spnt->dev == dev)
+			return (spnt);
+		spnt = spnt->next;
+	};
+	return (NULL);
+}
+
+/*
+ * based on flush_file_hash() below - needed as we want to re-use the
+ * file hash table.
+ */
+void
+flush_hash()
+{
+	struct file_hash	*fh;
+	struct file_hash	*fh1;
+	int			i;
+
+	for (i = 0; i < NR_HASH; i++) {
+		fh = hash_table[i];
+		while (fh) {
+			fh1 = fh->next;
+			free(fh);
+			fh = fh1;
+		}
+		hash_table[i] = NULL;
+	}
+}
+
+static struct file_hash *directory_hash_table[NR_HASH];
+
+void
+add_directory_hash(dev_t dev, ino_t inode)
+{
+	struct file_hash *s_hash;
+	unsigned int    hash_number;
+
+	if (!cache_inodes)
+		return;
+	if (dev == UNCACHED_DEVICE &&
+	    (inode == TABLE_INODE || inode == UNCACHED_INODE))
+		return;
+
+	hash_number = HASH_FN((unsigned int) dev, (unsigned int) inode);
+
+	s_hash = (struct file_hash *) e_malloc(sizeof (struct file_hash));
+	s_hash->next = directory_hash_table[hash_number];
+	s_hash->inode = inode;
+	s_hash->dev = dev;
+	s_hash->nlink = 0;
+	directory_hash_table[hash_number] = s_hash;
+}
+
+struct file_hash *
+find_directory_hash(dev_t dev, ino_t inode)
+{
+	unsigned int    hash_number;
+	struct file_hash *spnt;
+
+	if (!cache_inodes)
+		return (NULL);
+	if (dev == UNCACHED_DEVICE &&
+	    (inode == TABLE_INODE || inode == UNCACHED_INODE))
+		return (NULL);
+
+	hash_number = HASH_FN((unsigned int) dev, (unsigned int) inode);
+	spnt = directory_hash_table[hash_number];
+	while (spnt) {
+		if (spnt->inode == inode && spnt->dev == dev)
+			return (spnt);
+		spnt = spnt->next;
+	};
+	return (NULL);
+}
+
+struct name_hash {
+	struct name_hash *next;
+	struct directory_entry *de;
+	int	sum;
+};
+
+#define	NR_NAME_HASH	(256*1024)
+
+static struct name_hash *name_hash_table[NR_NAME_HASH] = {0, };
+
+/*
+ * Find the hash bucket for this name.
+ */
+static unsigned int
+name_hash(const char *name)
+{
+	unsigned int	hash = 0;
+	const char	*p;
+
+	p = name;
+
+	while (*p) {
+		/*
+		 * Don't hash the  iso9660 version number.
+		 * This way we can detect duplicates in cases where we have
+		 * directories (i.e. foo) and non-directories (i.e. foo;1).
+		 */
+		if (*p == ';') {
+			break;
+		}
+		hash = (hash << 15) + (hash << 3) + (hash >> 3) + (*p++ & 0xFF);
+	}
+	return (hash % NR_NAME_HASH);
+}
+
+void
+add_file_hash(struct directory_entry *de)
+{
+	struct name_hash	*new;
+	int			hash;
+	Uchar			*p;
+	int			sum = 0;
+
+	new = (struct name_hash *) e_malloc(sizeof (struct name_hash));
+	new->de = de;
+	new->next = NULL;
+	for (p = (Uchar *)de->isorec.name; *p; p++) {
+		if (*p == ';')
+			break;
+		sum += *p & 0xFF;
+	}
+	new->sum = sum;
+	hash = name_hash(de->isorec.name);
+
+	/* Now insert into the hash table */
+	new->next = name_hash_table[hash];
+	name_hash_table[hash] = new;
+}
+
+struct directory_entry *
+find_file_hash(register char *name)
+{
+	register char			*p1;
+	register char			*p2;
+	register struct name_hash	*nh;
+	register int			sum = 0;
+
+	if (debug > 1)
+		fprintf(stderr, "find_hash('%s')\n", name);
+
+	for (p1 = name; *p1; p1++) {
+		if (*p1 == ';')
+			break;
+		sum += *p1 & 0xFF;
+	}
+
+	for (nh = name_hash_table[name_hash(name)]; nh; nh = nh->next) {
+		if (nh->sum != sum)
+			continue;
+
+		p1 = name;
+		p2 = nh->de->isorec.name;
+		if (debug > 1)
+			fprintf(stderr, "Checking name '%s' isorec.name '%s'\n", p1, p2);
+
+		/* Look for end of string, or a mismatch. */
+		while (1 == 1) {
+			if ((*p1 == '\0' || *p1 == ';') ||
+			    (*p2 == '\0' || *p2 == ';') ||
+			    (*p1 != *p2)) {
+				break;
+			}
+			p1++;
+			p2++;
+		}
+		if (!isoname_endsok(p1) || !isoname_endsok(p2)) {
+			if (debug > 1) {
+				if (!isoname_endsok(p1))
+					fprintf(stderr, "'%s' does NOT END OK\n", p1);
+				if (!isoname_endsok(p2))
+					fprintf(stderr, "'%s' does NOT END OK\n", p2);
+			}
+			/*
+			 * If one file does not end with a valid version number
+			 * and the other name ends here, we found a miss match.
+			 */
+			if (*p1 == '\0' || *p2 == '\0')
+				continue;
+
+			if (*p1 == ';' && *p2 == ';') {
+				p1++;
+				p2++;
+				continue;
+			}
+		}
+
+		/*
+		 * If we are at the end of both strings, then we have a match.
+		 */
+		if ((*p1 == '\0' || *p1 == ';') &&
+		    (*p2 == '\0' || *p2 == ';')) {
+			return (nh->de);
+		}
+	}
+	return (NULL);
+}
+
+/*
+ * The macro 'eo' is just an idea on how one might speed up isoname_endsok()
+ */
+#define	eo(p)	(((p)[0] == '\0') || \
+		((p)[0] == ';' && (p)[1] == '1' && (p)[2] == '\0') || \
+		isoname_endsok(p))
+
+static BOOL
+isoname_endsok(char *name)
+{
+	int	i;
+	char	*p;
+
+	if (*name == '\0')
+		return (TRUE);
+	if (*name != ';')
+		return (FALSE);
+
+	for (p = ++name, i = 0; *p && i < 5; p++, i++) {
+		if (*p < '0' || *p > '9')
+			return (FALSE);
+	}
+	i = atoi(name);
+	if (i < 1 || i > 32767)
+		return (FALSE);
+	return (TRUE);
+}
+
+int
+delete_file_hash(struct directory_entry *de)
+{
+	struct name_hash	*nh;
+	struct name_hash	*prev;
+	int			hash;
+
+	prev = NULL;
+	hash = name_hash(de->isorec.name);
+	for (nh = name_hash_table[hash]; nh; nh = nh->next) {
+		if (nh->de == de)
+			break;
+		prev = nh;
+	}
+	if (!nh)
+		return (1);
+	if (!prev)
+		name_hash_table[hash] = nh->next;
+	else
+		prev->next = nh->next;
+	free(nh);
+	return (0);
+}
+
+void
+flush_file_hash()
+{
+	struct name_hash	*nh;
+	struct name_hash	*nh1;
+	int			i;
+
+	for (i = 0; i < NR_NAME_HASH; i++) {
+		nh = name_hash_table[i];
+		while (nh) {
+			nh1 = nh->next;
+			free(nh);
+			nh = nh1;
+		}
+		name_hash_table[i] = NULL;
+
+	}
+}