* Shorten SHA-256 hashes used in store path name generation to 160

  bits, then encode them in a radix-32 representation (using digits
  and letters except e, o, u, and t).  This produces store paths like
  /nix/store/4i0zb0z7f88mwghjirkz702a71dcfivn-aterm-2.3.1.  The nice
  thing about this is that the hash part of the file name is still 32
  characters, as before with MD5.

  (Of course, shortening SHA-256 to 160 bits makes it no better than
  SHA-160 in theory, but hopefully it's a bit more resistant to
  attacks; it's certainly a lot slower.)

1 files changed, 66 insertions, 6 deletions

diff --git a/src/libutil/hash.cc b/src/libutil/hash.cc
index cd7043090e..324e2bf7f4 100644
--- a/src/libutil/hash.cc
+++ b/src/libutil/hash.cc
@@ -15,6 +15,14 @@ extern "C" {
 
 
 
+Hash::Hash()
+{
+    type = htUnknown;
+    hashSize = 0;
+    memset(hash, 0, maxHashSize);
+}
+
+
 Hash::Hash(HashType type)
 {
     this->type = type;
@@ -23,7 +31,7 @@ Hash::Hash(HashType type)
     else if (type == htSHA256) hashSize = sha256HashSize;
     else throw Error("unknown hash type");
     assert(hashSize <= maxHashSize);
-    memset(hash, 0, hashSize);
+    memset(hash, 0, maxHashSize);
 }
 
 
@@ -52,21 +60,21 @@ bool Hash::operator < (const Hash & h) const
 }
 
 
-Hash::operator string() const
+string printHash(const Hash & hash)
 {
     ostringstream str;
-    for (unsigned int i = 0; i < hashSize; i++) {
+    for (unsigned int i = 0; i < hash.hashSize; i++) {
         str.fill('0');
         str.width(2);
-        str << hex << (int) hash[i];
+        str << hex << (int) hash.hash[i];
     }
     return str.str();
 }
 
     
-Hash parseHash(const string & s)
+Hash parseHash(HashType ht, const string & s)
 {
-    Hash hash(htMD5);
+    Hash hash(ht);
     if (s.length() != hash.hashSize * 2)
         throw Error(format("invalid hash `%1%'") % s);
     for (unsigned int i = 0; i < hash.hashSize; i++) {
@@ -82,6 +90,48 @@ Hash parseHash(const string & s)
 }
 
 
+static unsigned short divMod(uint16_t * words, unsigned short y)
+{
+    unsigned int borrow = 0;
+
+    int pos = (Hash::maxHashSize / 2) - 1;
+    while (pos >= 0 && !words[pos]) --pos;
+
+    for ( ; pos >= 0; --pos) {
+        unsigned int s = words[pos] + (borrow << 16);
+        unsigned int d = s / y;
+        borrow = s % y;
+        words[pos] = d;
+    }
+
+    return borrow;
+}
+
+
+// omitted: E O U T
+char chars[] = "0123456789abcdfghijklmnpqrsvwxyz";
+
+
+string printHash32(const Hash & hash)
+{
+    Hash hash2(hash);
+    unsigned int len = (hash.hashSize * 8 - 1) / 5 + 1;
+    
+    string s(len, '0');
+
+    int pos = len - 1;
+    while (pos >= 0) {
+        unsigned short digit = divMod((uint16_t *) hash2.hash, 32);
+        s[pos--] = chars[digit];
+    }
+
+    for (unsigned int i = 0; i < hash2.maxHashSize; ++i)
+        assert(hash2.hash[i] == 0);
+
+    return s;
+}
+
+
 bool isHash(const string & s)
 {
     if (s.length() != 32) return false;
@@ -186,3 +236,13 @@ Hash hashPath(const Path & path, HashType ht)
     finish(ht, sink.ctx, hash.hash);
     return hash;
 }
+
+
+Hash compressHash(const Hash & hash, unsigned int newSize)
+{
+    Hash h;
+    h.hashSize = newSize;
+    for (unsigned int i = 0; i < hash.hashSize; ++i)
+        h.hash[i % newSize] ^= hash.hash[i];
+    return h;
+}