aboutsummaryrefslogtreecommitdiff log msg author committer range
path: root/crypto.c
diff options
 context: 12345678910152025303540 space: includeignore mode: unifiedssdiffstat only
Diffstat (limited to 'crypto.c')
-rw-r--r--crypto.c33
1 files changed, 30 insertions, 3 deletions
 diff --git a/crypto.c b/crypto.cindex e8759d5..ce88d0f 100644--- a/crypto.c+++ b/crypto.c@@ -113,6 +113,18 @@ hash_t merkle_compute(hash_t node, const hash_t *comp, const int *orders, size_t return parent; } +/* Given a node's index, return the index of the parent in an array+ * representation of a binary tree. */+int bintree_parent(int idx)+{+ return (idx - ((idx & 1) ? 1 : 2)) / 2;+}++int bintree_sibling(int idx)+{+ return idx + ((idx & 1) ? 1 : -1);+}+ /* Calculate the indicies of the complementary nodes to a * leaf. `leafidx' is 0 for the rightmost leaf node. This function * will return an array with a length equal to the number of levels in@@ -137,18 +149,33 @@ int *merkle_complement(int leafidx, int logleaves, int **orders) for(int i = 0; i < logleaves; ++i) { /* output index of sibling node */- comp[i] = idx + ((idx & 1) ? 1 : -1);+ comp[i] = bintree_sibling(idx); + /* we really don't need the orders array */ if(orders)- (*orders)[i] = ((idx&1) ? 1 : 0);+ (*orders)[i] = idx & 1; /* find parent index and loop */- idx = (idx - ((idx & 1) ? 1 : 2)) / 2;+ idx = bintree_parent(idx); } return comp; } +int *merkle_dependents(int leafidx, int logleaves)+{+ int *dep = calloc(logleaves, sizeof(int));++ int idx = (1 << logleaves) - 1 + leafidx;+ for(int i = 0; i < logleaves; ++i)+ {+ idx = bintree_parent(idx);+ dep[i] = idx;+ }++ return dep;+}+ /* Shim to get only the orders */ int *merkle_complement_orders(int leafidx, int logleaves) {