From a09e66da5af348dc25e3b372ec9f518d3532f863 Mon Sep 17 00:00:00 2001
From: Eelco Dolstra <e.dolstra@tudelft.nl>
Date: Mon, 16 Jun 2003 14:19:32 +0000
Subject: * Description of path hashing algorithm.

---
 src/hash.cc |  8 --------
 src/hash.hh | 53 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 53 insertions(+), 8 deletions(-)

diff --git a/src/hash.cc b/src/hash.cc
index bb25c5168f5d..9451ac8d80e4 100644
--- a/src/hash.cc
+++ b/src/hash.cc
@@ -6,14 +6,12 @@ extern "C" {
 #include <iostream>
 
 
-/* Create a zeroed hash object. */
 Hash::Hash()
 {
     memset(hash, 0, sizeof(hash));
 }
 
 
-/* Check whether two hash are equal. */
 bool Hash::operator == (Hash & h2)
 {
     for (unsigned int i = 0; i < hashSize; i++)
@@ -22,14 +20,12 @@ bool Hash::operator == (Hash & h2)
 }
 
 
-/* Check whether two hash are not equal. */
 bool Hash::operator != (Hash & h2)
 {
     return !(*this == h2);
 }
 
 
-/* Convert a hash code into a hexadecimal representation. */
 Hash::operator string() const
 {
     ostringstream str;
@@ -42,7 +38,6 @@ Hash::operator string() const
 }
 
     
-/* Parse a hexadecimal representation of a hash code. */
 Hash parseHash(const string & s)
 {
     Hash hash;
@@ -61,7 +56,6 @@ Hash parseHash(const string & s)
 }
 
 
-/* Verify that a reference is valid (that is, is a MD5 hash code). */
 bool isHash(const string & s)
 {
     if (s.length() != 32) return false;
@@ -75,7 +69,6 @@ bool isHash(const string & s)
 }
 
 
-/* Compute the MD5 hash of a file. */
 Hash hashString(const string & s)
 {
     Hash hash;
@@ -84,7 +77,6 @@ Hash hashString(const string & s)
 }
 
 
-/* Compute the MD5 hash of a file. */
 Hash hashFile(const string & fileName)
 {
     Hash hash;
diff --git a/src/hash.hh b/src/hash.hh
index 6e20b3cbc193..9d72e66dbdea 100644
--- a/src/hash.hh
+++ b/src/hash.hh
@@ -13,9 +13,16 @@ struct Hash
     static const unsigned int hashSize = 16;
     unsigned char hash[hashSize];
 
+    /* Create a zeroed hash object. */
     Hash();
+
+    /* Check whether two hash are equal. */
     bool operator == (Hash & h2);
+
+    /* Check whether two hash are not equal. */
     bool operator != (Hash & h2);
+
+    /* Convert a hash code into a hexadecimal representation. */
     operator string() const;
 };
 
@@ -27,9 +34,55 @@ public:
 };
 
 
+/* Parse a hexadecimal representation of a hash code. */
 Hash parseHash(const string & s);
+
+/* Verify that the given string is a valid hash code. */
 bool isHash(const string & s);
+
+/* Compute the hash of the given string. */
 Hash hashString(const string & s);
+
+/* Compute the hash of the given file. */
 Hash hashFile(const string & fileName);
 
+/* Compute the hash of the given path.  The hash is defined as
+   follows:
+
+   hash(path) = md5(dump(path))
+
+   IF path points to a REGULAR FILE:
+     dump(path) = attrs(
+       [ ("type", "regular")
+       , ("contents", contents(path))
+       ])
+
+   IF path points to a DIRECTORY:
+     dump(path) = attrs(
+       [ ("type", "directory")
+       , ("entries", concat(map(f, entries(path))))
+       ])
+       where f(fn) = attrs(
+         [ ("name", fn)
+         , ("file", dump(path + "/" + fn))
+         ])
+
+   where:
+
+     attrs(as) = concat(map(attr, as)) + encN(0) 
+     attrs((a, b)) = encS(a) + encS(b)
+
+     encS(s) = encN(len(s)) + s
+
+     encN(n) = 64-bit little-endian encoding of n.
+
+     contents(path) = the contents of a regular file.
+
+     entries(path) = the entries of a directory, without `.' and
+     `..'.
+
+     `+' denotes string concatenation. */
+Hash hashPath(const string & path);
+
+
 #endif /* !__HASH_H */
-- 
cgit 1.4.1