Parallelized hash calculations

diff --git a/trunk/Pithos.Network/Signature.cs b/trunk/Pithos.Network/Signature.cs
index df69a7b..e12fb74 100644 (file)
--- a/trunk/Pithos.Network/Signature.cs
+++ b/trunk/Pithos.Network/Signature.cs
@@ -159,42 +159,83 @@ namespace Pithos.Network
                 return finalHash;
             }
         }*/
-        
-        public static byte[] CalculateTopHash(IEnumerable<byte[]> hashMap, string algorithm)
+
+        public static byte[] CalculateTopHash(IList<byte[]> hashMap, string algorithm)
         {
             if (hashMap == null)
                 throw new ArgumentNullException("hashMap");
             if (String.IsNullOrWhiteSpace(algorithm))
                 throw new ArgumentNullException("algorithm");
-            Contract.EndContractBlock();
+            Contract.EndContractBlock();            
 
-            var hashCount = hashMap.Count();
+            var hashCount = hashMap.Count;
+            //The tophash of an empty hashmap is an empty array
             if (hashCount == 0)
-                return null;
+                return new byte[0];
+            //The tophash of a one-item hashmap is the hash itself
             if (hashCount == 1)
-                return hashMap.First();
+                return hashMap[0];
 
-            var newHashes=new List<byte[]>();
+            //Calculate the required number of leaf nodes
             var leafs =(int)Math.Pow(2, Math.Ceiling(Math.Log(hashCount,2)));
-            for (int i = 0; i < leafs;i+=2 )
-            {
-                using (var hasher = HashAlgorithm.Create(algorithm))
+            //The size of all nodes is the same and equal to the size of the input hashes
+            var hashSize = hashMap[0].Length;
+
+            //If the hashmap containes fewer nodes than the required leaf count, we need to fill
+            //the rest with empty blocks
+            byte[] empty=null;            
+            if (hashCount < leafs)
+                empty = new byte[hashSize];
+
+            //New hashes will be stored in a dictionary keyed by their step to preserve order
+            var newHashes=new ConcurrentDictionary<int, byte[]>();            
+            
+            Parallel.For(0, leafs/2,
+                (step, state) =>
                 {
-                    var block1 = i >hashCount - 1 ? new byte[hashMap.First().Length] : hashMap.ElementAt(i);
-                    var block2 = i>hashCount-2 ? new byte[block1.Length] : hashMap.ElementAt(i+1);
-                    
+                    using (var hasher = HashAlgorithm.Create(algorithm))
+                    {
+                        var i = step*2;
+                        var block1 = i <= hashCount - 1 ? hashMap[i] : empty;
+                        var block2 = i <= hashCount - 2 ? hashMap[i + 1] : empty;
+
+                        hasher.TransformBlock(block1, 0, block1.Length, null, 0);
+                        hasher.TransformFinalBlock(block2, 0, block2.Length);
+
+                        var finalHash = hasher.Hash;
+                        //Store the final value in its proper place
+                        newHashes[step] = finalHash;
+                    }
+                });
+/*
+            Parallel.For(0, leafs/2,
+                () => HashAlgorithm.Create(algorithm),
+                (step, state, hasher) =>
+                {
+                                 
+                    var i = step*2;
+                    var block1 = i <= hashCount - 1 ? hashMap[i]: empty;
+                    var block2 = i <= hashCount - 2 ? hashMap[i + 1] : empty;
+
                     hasher.TransformBlock(block1, 0, block1.Length, null, 0);
-                    hasher.TransformFinalBlock(block2, 0, block2.Length);                        
+                    hasher.TransformFinalBlock(block2, 0, block2.Length);
+                    
                     var finalHash = hasher.Hash;
-                    newHashes.Add(finalHash);
-                }                    
-            }
-            return CalculateTopHash(newHashes, algorithm);                   
+                    //Store the final value in its proper place
+                    newHashes[step] = finalHash;
+                                        
+                    return hasher;
+                },
+                hasher => hasher.Dispose());
+*/
+            //Extract the hashes to a list ordered by their step 
+            var hashes = newHashes.OrderBy(pair => pair.Key).Select(pair => pair.Value).ToList();
+            return CalculateTopHash(hashes, algorithm);                   
         }
 
         
 
-        public static string CalculateTopHash(string hashString, string algorithm)
+      /*  public static string CalculateTopHash(string hashString, string algorithm)
         {
             if (String.IsNullOrWhiteSpace(algorithm))
                 throw new ArgumentNullException("algorithm");
@@ -208,7 +249,7 @@ namespace Pithos.Network
                 var hash=hasher.ComputeHash(bytes);
                 return hash.ToHashString();
             }
-        }
+        }*/
 
         private static Task<ConcurrentDictionary<int, byte[]>> CalculateBlockHashesAsync(FileStream stream, int blockSize, string algorithm, ConcurrentDictionary<int, byte[]> hashes, int index = 0)
         {

diff --git a/trunk/Pithos.Network/TreeHash.cs b/trunk/Pithos.Network/TreeHash.cs
index 6d80476..e35b399 100644 (file)
--- a/trunk/Pithos.Network/TreeHash.cs
+++ b/trunk/Pithos.Network/TreeHash.cs
@@ -43,18 +43,14 @@ namespace Pithos.Network
 
         public TreeHash(string algorithm)
         {
-            BlockHash = algorithm;
-            _topHash = new Lazy<byte[]>(() => Signature.CalculateTopHash(_hashes, BlockHash));
-
-            _topHash2 = new Lazy<string>(() =>
-                                             {
-                                                 var hashString = _hashes.Select(hash => hash.ToHashString())
-                                                     .Aggregate(new StringBuilder(),
-                                                                (builder, hash) => builder.Append(hash),
-                                                                builder => builder.ToString());
-
-                                                 return Signature.CalculateTopHash(hashString, BlockHash);
-                                             });
+            BlockHash = algorithm;            
+            _topHash = new Lazy<byte[]>(() =>
+            {
+                //
+                //Cast the hashes to an IList or create a new list out of the hashes
+                var hashMap = (_hashes as IList<byte[]>)??_hashes.ToList();
+                return Signature.CalculateTopHash(hashMap, BlockHash);
+            });
         }
 
         //Returns a Json representation of the hashes, as required by Pithos