* 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.)

7 files changed, 108 insertions, 36 deletions

diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index 59b85a6d6233..b59232f2cea3 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -39,7 +39,7 @@ static Hash hashDerivation(EvalState & state, StoreExpr ne)
             DrvHashes::iterator j = state.drvHashes.find(*i);
             if (j == state.drvHashes.end())
                 throw Error(format("don't know expression `%1%'") % (string) *i);
-            inputs2.insert(j->second);
+            inputs2.insert(printHash(j->second));
         }
 	ne.derivation.inputs = inputs2;
     }
@@ -60,7 +60,7 @@ static Path copyAtom(EvalState & state, const Path & srcPath)
 
     Hash drvHash = hashDerivation(state, ne);
     Path drvPath = writeTerm(unparseStoreExpr(ne), "c");
-    state.drvHashes.insert(make_pair(drvPath, drvHash));
+    state.drvHashes[drvPath] = drvHash;
 
     state.drvRoots[drvPath] = ne.closure.roots;
 
@@ -111,14 +111,14 @@ static void processBinding(EvalState & state, Expr e, StoreExpr & ne,
 
             a = queryAttr(e, "drvHash");
             if (!a) throw Error("derivation hash missing");
-            Hash drvHash = parseHash(evalString(state, a));
+            Hash drvHash = parseHash(htMD5, evalString(state, a));
 
             a = queryAttr(e, "outPath");
             if (!a) throw Error("output path missing");
             PathSet drvRoots;
             drvRoots.insert(evalPath(state, a));
             
-            state.drvHashes.insert(make_pair(drvPath, drvHash));
+            state.drvHashes[drvPath] = drvHash;
             state.drvRoots[drvPath] = drvRoots;
 
             ss.push_back(addInput(state, drvPath, ne));
@@ -188,7 +188,7 @@ static Expr primDerivation(EvalState & state, const ATermVector & _args)
     ne.type = StoreExpr::neDerivation;
 
     string drvName;
-    Hash outHash(htMD5);
+    Hash outHash;
     bool outHashGiven = false;
 
     for (ATermIterator i(attrs.keys()); i; ++i) {
@@ -223,7 +223,7 @@ static Expr primDerivation(EvalState & state, const ATermVector & _args)
             else if (key == "system") ne.derivation.platform = s;
             else if (key == "name") drvName = s;
             else if (key == "id") { 
-                outHash = parseHash(s);
+                outHash = parseHash(htMD5, s);
                 outHashGiven = true;
             }
         }
@@ -273,7 +273,7 @@ static Expr primDerivation(EvalState & state, const ATermVector & _args)
 
     /* Write the resulting term into the Nix store directory. */
     Hash drvHash = outHashGiven
-        ? hashString((string) outHash + outPath, htMD5)
+        ? hashString(printHash(outHash) + outPath, htMD5)
         : hashDerivation(state, ne);
     Path drvPath = writeTerm(unparseStoreExpr(ne), "d-" + drvName);
 
@@ -283,7 +283,7 @@ static Expr primDerivation(EvalState & state, const ATermVector & _args)
     attrs.set("outPath", makeAttrRHS(makePath(toATerm(outPath)), makeNoPos()));
     attrs.set("drvPath", makeAttrRHS(makePath(toATerm(drvPath)), makeNoPos()));
     attrs.set("drvHash",
-        makeAttrRHS(makeStr(toATerm((string) drvHash)), makeNoPos()));
+        makeAttrRHS(makeStr(toATerm(printHash(drvHash))), makeNoPos()));
     attrs.set("type", makeAttrRHS(makeStr(toATerm("derivation")), makeNoPos()));
 
     return makeAttrs(attrs);
diff --git a/src/libstore/references.cc b/src/libstore/references.cc
index 9b20b980a1b2..5ceae6427617 100644
--- a/src/libstore/references.cc
+++ b/src/libstore/references.cc
@@ -81,8 +81,12 @@ Strings filterReferences(const string & path, const Strings & paths)
     for (Strings::const_iterator i = paths.begin();
          i != paths.end(); i++)
     {
-        string s = string(baseNameOf(*i), 0, 32);
-        parseHash(s);
+        string baseName = baseNameOf(*i);
+        unsigned int pos = baseName.find('-');
+        if (pos == string::npos)
+            throw Error(format("bad reference `%1%'") % *i);
+        string s = string(baseName, 0, pos);
+        // parseHash(htSHA256, s);
         ids.push_back(s);
         backMap[s] = *i;
     }
diff --git a/src/libstore/store.cc b/src/libstore/store.cc
index 3a76618a5a39..e490bf258195 100644
--- a/src/libstore/store.cc
+++ b/src/libstore/store.cc
@@ -415,14 +415,12 @@ Path makeStorePath(const string & type,
     Hash & hash, const string & suffix)
 {
     /* e.g., "source:sha256:1abc...:/nix/store:foo.tar.gz" */
-    string s = type + ":sha256:" + (string) hash + ":"
+    string s = type + ":sha256:" + printHash(hash) + ":"
         + nixStore + ":" + suffix;
 
-    Hash nameHash = hashString(s, htSHA256);
-
-    printMsg(lvlError, format("name input: %1% -> %2%") % s % (string) nameHash);
-
-    return nixStore + "/" + (string) nameHash + "-" + suffix;
+    return nixStore + "/"
+        + printHash32(compressHash(hashString(s, htSHA256), 20))
+        + "-" + suffix;
 }
 
 
@@ -461,7 +459,7 @@ Path addToStore(const Path & _srcPath)
             Hash h2 = hashPath(dstPath, htSHA256);
             if (h != h2)
                 throw Error(format("contents of `%1%' changed while copying it to `%2%' (%3% -> %4%)")
-                    % srcPath % dstPath % (string) h % (string) h2);
+                    % srcPath % dstPath % printHash(h) % printHash(h2));
 
             makePathReadOnly(dstPath);
             
diff --git a/src/libutil/hash.cc b/src/libutil/hash.cc
index cd7043090ec7..324e2bf7f4c2 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;
+}
diff --git a/src/libutil/hash.hh b/src/libutil/hash.hh
index 4490d2ff7ace..0c9d7b9cb936 100644
--- a/src/libutil/hash.hh
+++ b/src/libutil/hash.hh
@@ -8,7 +8,7 @@
 using namespace std;
 
 
-typedef enum { htMD5, htSHA1, htSHA256 } HashType;
+typedef enum { htUnknown, htMD5, htSHA1, htSHA256 } HashType;
 
 
 const int md5HashSize = 16;
@@ -24,7 +24,10 @@ struct Hash
 
     HashType type;
 
-    /* Create a zeroed hash object. */
+    /* Create an unusable hash object. */
+    Hash();
+
+    /* Create a zero-filled hash object. */
     Hash(HashType type);
 
     /* Check whether two hash are equal. */
@@ -36,13 +39,20 @@ struct Hash
     /* For sorting. */
     bool operator < (const Hash & h) const;
 
-    /* Convert a hash code into a hexadecimal representation. */
-    operator string() const;
 };
 
 
+/* Convert a hash to a hexadecimal representation. */
+string printHash(const Hash & hash);
+
 /* Parse a hexadecimal representation of a hash code. */
-Hash parseHash(const string & s);
+Hash parseHash(HashType ht, const string & s);
+
+/* Convert a hash to a base-32 representation. */
+string printHash32(const Hash & hash);
+
+/* Parse a base-32 representation of a hash code. */
+Hash parseHash32(HashType ht, const string & s);
 
 /* Verify that the given string is a valid hash code. */
 bool isHash(const string & s);
@@ -57,5 +67,9 @@ Hash hashFile(const Path & path, HashType ht);
    md5(dump(path)). */
 Hash hashPath(const Path & path, HashType ht);
 
+/* Compress a hash to the specified number of bytes by cyclically
+   XORing bytes together. */
+Hash compressHash(const Hash & hash, unsigned int newSize);
+
 
 #endif /* !__HASH_H */
diff --git a/src/nix-env/main.cc b/src/nix-env/main.cc
index fc65dcfc3b60..0143c1d24e44 100644
--- a/src/nix-env/main.cc
+++ b/src/nix-env/main.cc
@@ -34,10 +34,6 @@ struct DrvInfo
     Path drvPath;
     Path outPath;
     Hash drvHash;
-
-    DrvInfo() : drvHash(htMD5)
-    {
-    }
 };
 
 typedef map<Path, DrvInfo> DrvInfos;
@@ -74,7 +70,7 @@ bool parseDerivation(EvalState & state, Expr e, DrvInfo & drv)
 
     a = queryAttr(e, "drvHash");
     if (!a) throw badTerm("derivation hash missing", e);
-    drv.drvHash = parseHash(evalString(state, a));
+    drv.drvHash = parseHash(htMD5, evalString(state, a));
 
     a = queryAttr(e, "outPath");
     if (!a) throw badTerm("output path missing", e);
@@ -205,7 +201,7 @@ void createUserEnv(EvalState & state, const DrvInfos & drvs,
             makeBind(toATerm("drvPath"),
                 makePath(toATerm(i->second.drvPath)), makeNoPos()),
             makeBind(toATerm("drvHash"),
-                makeStr(toATerm((string) i->second.drvHash)), makeNoPos()),
+                makeStr(toATerm(printHash(i->second.drvHash))), makeNoPos()),
             makeBind(toATerm("outPath"),
                 makePath(toATerm(i->second.outPath)), makeNoPos())
             ));
diff --git a/src/nix-hash/nix-hash.cc b/src/nix-hash/nix-hash.cc
index 360e07960b0e..2cef7818e857 100644
--- a/src/nix-hash/nix-hash.cc
+++ b/src/nix-hash/nix-hash.cc
@@ -29,8 +29,8 @@ void run(Strings args)
             else throw UsageError(format("unknown hash type `%1%'") % *i);
         }
         else
-            cout << format("%1%\n") % (string)
-                (flat ? hashFile(*i, ht) : hashPath(*i, ht));
+            cout << format("%1%\n") % printHash(
+                (flat ? hashFile(*i, ht) : hashPath(*i, ht)));
     }
 }