Synnefo

# Copyright 2011-2012 GRNET S.A. All rights reserved.

#

# Redistribution and use in source and binary forms, with or

# without modification, are permitted provided that the following

# conditions are met:

#

#   1. Redistributions of source code must retain the above

#      copyright notice, this list of conditions and the following

#      disclaimer.

#

#   2. Redistributions in binary form must reproduce the above

#      copyright notice, this list of conditions and the following

#      disclaimer in the documentation and/or other materials

#      provided with the distribution.

#

# THIS SOFTWARE IS PROVIDED BY GRNET S.A. ``AS IS'' AND ANY EXPRESS

# OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED

# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR

# PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL GRNET S.A OR

# CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF

# USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED

# AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT

# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN

# ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE

# POSSIBILITY OF SUCH DAMAGE.

#

# The views and conclusions contained in the software and

# documentation are those of the authors and should not be

# interpreted as representing official policies, either expressed

# or implied, of GRNET S.A.

import hashlib

from binascii import hexlify

from StringIO import StringIO

def file_read_iterator(fp, size=1024):

    while True:

        data = fp.read(size)

        if not data:

            break

        yield data

class HashMap(list):

    def __init__(self, blocksize, blockhash):

        super(HashMap, self).__init__()

        self.blocksize = blocksize

        self.blockhash = blockhash

    def _hash_raw(self, v):

        h = hashlib.new(self.blockhash)

        h.update(v)

        return h.digest()

    def _hash_block(self, v):

        return self._hash_raw(v.rstrip('\x00'))

    def hash(self):

        if len(self) == 0:

            return self._hash_raw('')

        if len(self) == 1:

            return self.__getitem__(0)

        h = list(self)

        s = 2

        while s < len(h):

            s = s * 2

        h += [('\x00' * len(h[0]))] * (s - len(h))

        while len(h) > 1:

            h = [self._hash_raw(h[x] + h[x + 1]) for x in range(0, len(h), 2)]

        return h[0]

    def load(self, data):

        self.size = 0

        fp = StringIO(data)

        for block in file_read_iterator(fp, self.blocksize):

            self.append(self._hash_block(block))

            self.size += len(block)

def merkle(data, blocksize=4194304, blockhash='sha256'):

    hashes = HashMap(blocksize, blockhash)

    hashes.load(data)

    return hexlify(hashes.hash())