Subversion Repositories bluespec_md6

# treewalk.py

# Ronald L. Rivest

# 9/14/07

# Compute hash of sequence D[0..n-1]

# by first applying leaf_hash to each D[i]

# and then applying combine_hash(x,y) to each

# pair to reduce number of values by two, repeatedly

# until only one value is left. (Complicated way of

# saying that we are computing up a binary tree....)

# Hash of an empty subtree (no leaves) is zero by definition.

def H(i,k):

    """

    Compute level-k hash function on D[i..i+(2**k)-1]

    k = level of hash; k = 0 for leaf, parent has level = 1 + level(child)

    k = Infinity for initial call.

    Assume X(i) == True iff D[i] exists (i.e. i is not past EOF).

    In sequential implementation, X called on non-decreasing values for i.

    """

    if not X(i):

        return 0                     # empty subtree

    if k == 0:

        return leaf_hash(D[i])       # leaf

    if k != Infinity:

        # CILK spawn:

        L = H(i,k-1)                 # left subtree

        # CILK spawn:

        R = H(i+2**(k-1),k-1)        # right subtree

        # CILK sync:

        return combine_hash(L,R)     # combine them

    else:

        # determine correct level k dynamically

        k = 0

        L = H(i,k)

        while X(i+2**k):

            # now L = hash on D[i..i+2**k-1]

            R = H(i+2**k,k)

            L = combine_hash(L,R)

            k += 1

        return L

def leaf_hash(D):

    """ Dummy leaf_hash just returns input """

    return D

def combine_hash(L,R):

    """ Dummy combine_hash just returns sum of inputs """

    return L+R

# Global variable array D is input to be hashed

D = range(20)

def X(i):

    """ Test if D[i] exists """

    print "X",i

    return i<len(D)

Infinity = 1000

# Test call

print H(0,Infinity)