[GNUnet-SVN] r25651 - gnunet-update/src/gnunet_update

[gnunet]

Author: harsha
Date: 2012-12-26 10:08:00 +0100 (Wed, 26 Dec 2012)
New Revision: 25651

Added:
   gnunet-update/src/gnunet_update/hashtree.py
Log:
- hash tree

Added: gnunet-update/src/gnunet_update/hashtree.py
===================================================================
--- gnunet-update/src/gnunet_update/hashtree.py                         (rev 0)
+++ gnunet-update/src/gnunet_update/hashtree.py 2012-12-26 09:08:00 UTC (rev 
25651)
@@ -0,0 +1,174 @@
+# This file is part of GNUnet.
+# (C) 2011 Christian Grothoff (and other contributing authors)
+#
+# GNUnet 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.
+#
+# GNUnet 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 GNUnet; see the file COPYING.  If not, write to the
+# Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+# Boston, MA 02111-1307, USA.
+# 
+# File:    gnunet_update/hashtree.py
+# Author:  Sree Harsha Totakura
+
+from hashlib import sha512
+from Crypto.Cipher import AES
+import logging
+
+# Defaults
+DBLOCK_SIZE = (32 * 1024)   # Data block size
+
+# Pick a multiple of 2 here to achive 8-byte alignment!  We also
+# probably want DBlocks to have (roughly) the same size as IBlocks.
+# With SHA-512, the optimal value is 32768 byte / 128 byte = 256 (128
+# byte = 2 * 512 bits).  DO NOT CHANGE!
+CHK_PER_INODE = 256
+
+class Chk:
+    key = None
+    query = None
+
+    def __init__(self, key, query):
+        self.key = key
+        self.query = query
+
+def compute_depth_(size):
+    """Computes the depth of the tree.
+    
+    size: the size of the file whose tree's depth has to be computed
+    Returns the depth of the tree. Always > 0.
+    """
+    depth = 1
+    fl = DBLOCK_SIZE
+    while (fl < size):
+        depth += 1
+        if ((fl * CHK_PER_INODE) < fl):
+            return depth
+        fl = fl * CHK_PER_INODE
+    return depth
+
+def compute_tree_size_(depth):
+    """Calculate how many bytes of payload a block tree of the given depth MAY
+     correspond to at most (this function ignores the fact that some blocks 
will
+     only be present partially due to the total file size cutting some blocks
+     off at the end).
+
+     depth: depth of the block.  depth==0 is a DBLOCK.
+     Returns the number of bytes of payload a subtree of this depth may
+     correspond to.
+     """
+    rsize = DBLOCK_SIZE
+    for cnt in range(0, depth):
+        rsize *= CHK_PER_INODE
+    return rsize
+
+def compute_chk_offset_(depth, end_offset):
+    """Compute the offset of the CHK for the current block in the IBlock
+    above
+    
+    depth: depth of the IBlock in the tree (aka overall number of tree levels
+             minus depth); 0 == DBLOCK
+    end_offset: current offset in the overall file, at the *beginning* of the
+                  block for DBLOCK (depth == 0), otherwise at the *end* of the
+                  block (exclusive)
+    Returns the offset in the list of CHKs in the above IBlock
+    """
+    bds = compute_tree_size_(depth)
+    if (depth > 0):
+        end_offset -= 1
+    ret = end_ofset / bds
+    return ret % CHK_PER_INODE
+
+def compute_iblock_size_(depth, offset):
+    """Compute the size of the current IBLOCK.  The encoder is triggering the
+    calculation of the size of an IBLOCK at the *end* (hence end_offset) of its
+    construction.  The IBLOCK maybe a full or a partial IBLOCK, and this
+    function is to calculate how long it should be.
+    
+    depth: depth of the IBlock in the tree, 0 would be a DBLOCK, must be > 0
+             (this function is for IBLOCKs only!)
+    offset: current offset in the payload (!) of the overall file, must be > 0
+              (since this function is called at the end of a block).
+    Returns the number of elements to be in the corresponding IBlock
+    """
+    assert (depth > 0)
+    assert (offset > 0)
+    bds = compute_tree_size_ (depth)
+    mod = offset % bds
+    if mod is 0:
+        ret = CHK_PER_INODE
+    else:
+        bds /= CHK_PER_INODE
+        ret = mode / bds
+        if (mod % bds) is not 0:
+            ret += 1
+    return ret
+
+def sha512_hash (data):
+    """ Returns the sha512 digest of the given string
+    
+    data: the string whose hash has to be computed
+    """
+    sh = sha512()
+    sh.update (data)
+    return sh.digest()
+
+def compute_rootchk(readin, size):
+    """Returns the content hash key after generating the hash tree for the 
given
+    input stream.
+
+    readin: the stream where to read data from
+    size: the size of data to be read
+    """
+    depth = compute_depth_(size);
+    current_depth = 0
+    chks = list(depth * CHK_PER_INODE)
+    read_offset = 0
+    logging.debug("Begining to calculate tree hash with depth: " + depth)
+    while True:
+        if depth is current_depth:
+            off = CHK_PER_INODE * (depth - 1)
+            logging.debug("Encoding done, reading CHK `%s' from %u\n",
+                          chks[off].query, off)
+            uri_chk = chks[off]
+            return uri_chk
+        if current_depth is 0:
+            pt_size = min(DBLOCK_SIZE, size - read_offset);
+            try:
+                pt_block = readin.read(pt_size)
+            except IOError:
+                logging.warning ("Error reading input file stream")
+                return None
+        else:
+            pt_size = compute_iblock_size_(current_depth, read_offset)
+            pt_block = bytearray()
+            reduce ((lambda chk, ba:
+                         ba += chk.hash + chk.key),
+                    chks[(current_depth - 1) * CHK_PER_INODE:][:pt_size],
+                    pt_block)
+        off = compute_chk_offset_ (current_depth, read_offset)
+        logging.debug ("Encoding data at offset %u and depth %u with block " \
+                           "size %u and target CHK offset %u",
+                       read_offset, current_depth, pt_size, 
+                       (current_depth * CHK_PER_INODE) + off)
+        chk = Chk()
+        chk.hash = sha512_hash (pt_block)
+        
+        if current_depth is 0:
+            read_offset += pt_size
+            if (read_offset is size) or (read_offset % (CHK_PER_INODE * \
+                                                        DBLOCK_SIZE)) is 0:
+                current_depth += 1
+        else:
+            if (off is CHK_PER_INODE) or (read_offset is size):
+                current_depth++
+            else:
+                current_depth = 0