head 1.1;
access;
symbols;
locks; strict;
comment @# @;
1.1
date 2008.10.27.17.01.52; author kfleming; state Exp;
branches;
next ;
commitid 5d1a4905f3e64567;
desc
@@
1.1
log
@initial checkin, may not work
@
text
@# 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