Line data    Source code

       1             : #include "fd_wbmtree.h"
       2             : 
       3             : // Merkle tree of 3 nodes
       4             : //
       5             : // A . B . C
       6             : //
       7             : // root =
       8             : //      sha256([0x1] +
       9             : //        sha256([0x1] + sha256([0x0] + A) + sha256([0x0] + B)) |
      10             : //        sha256([0x1] + sha256([0x0] + C) + sha256([0x0] + C))
      11             : //      )
      12             : //
      13             : 
      14             : fd_wbmtree32_t*
      15             : fd_wbmtree32_init      ( void * mem, ulong leaf_cnt )
      16           0 : {
      17           0 :   if( FD_UNLIKELY( !mem ) ) {
      18           0 :     FD_LOG_WARNING(( "NULL mem" ));
      19           0 :     return NULL;
      20           0 :   }
      21             : 
      22           0 :   if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)mem, fd_wbmtree32_align() ) ) ) {
      23           0 :     FD_LOG_WARNING(( "misaligned mem" ));
      24           0 :     return NULL;
      25           0 :   }
      26             : 
      27           0 :   fd_memset(mem, 0, fd_wbmtree32_footprint(leaf_cnt));
      28           0 :   fd_wbmtree32_t* hdr = (fd_wbmtree32_t*) mem;
      29           0 :   hdr->leaf_cnt_max = leaf_cnt;
      30           0 :   hdr->leaf_cnt = 0;
      31             : 
      32           0 :   fd_sha256_batch_init(&hdr->sha256_batch);
      33             : 
      34           0 :   return mem;
      35           0 : }
      36             : 
      37             : void
      38             : fd_wbmtree32_append    ( fd_wbmtree32_t * bmt, fd_wbmtree32_leaf_t const * leaf, ulong leaf_cnt, uchar *mbuf  )
      39           0 : {
      40           0 :   FD_TEST ((bmt->leaf_cnt + leaf_cnt) <= bmt->leaf_cnt_max);
      41             : 
      42           0 :   fd_wbmtree32_node_t *n = &((fd_wbmtree32_node_t *)bmt->data)[bmt->leaf_cnt];
      43           0 :   for (ulong i = 0; i < leaf_cnt; i++) {
      44           0 :     mbuf[0] = (uchar) 0;
      45           0 :     fd_memcpy(&mbuf[1], leaf->data, leaf->data_len);
      46           0 :     fd_sha256_batch_add(&bmt->sha256_batch, mbuf, leaf->data_len + 1, &n->hash[(i & 1) ? 0 : 1]);
      47           0 :     mbuf += leaf->data_len + 1;
      48           0 :     n++;
      49           0 :     leaf++;
      50           0 :   }
      51           0 :   fd_sha256_batch_fini(&bmt->sha256_batch);
      52           0 :   bmt->leaf_cnt += leaf_cnt;
      53             : 
      54           0 :   FD_TEST (leaf_cnt <= bmt->leaf_cnt_max);
      55           0 : }
      56             : 
      57             : uchar *
      58             : fd_wbmtree32_fini      ( fd_wbmtree32_t * bmt)
      59           0 : {
      60           0 :   FD_TEST ( bmt->leaf_cnt <= bmt->leaf_cnt_max );
      61             : 
      62           0 :   fd_wbmtree32_node_t *this = (fd_wbmtree32_node_t *)bmt->data;
      63           0 :   fd_wbmtree32_node_t *that = &((fd_wbmtree32_node_t *)bmt->data)[bmt->leaf_cnt + (bmt->leaf_cnt & 1)];
      64             : 
      65           0 :   while (bmt->leaf_cnt > 1) {
      66             :     // If the tree is uneven, we duplicate the last hash
      67           0 :     if (bmt->leaf_cnt & 1) {
      68             :       // In the source data, the bytes are offset by 1 to give us room
      69             :       // for the 1 byte... in the target, it is not offset by one..
      70           0 :       fd_memcpy(this[bmt->leaf_cnt].hash, &this[bmt->leaf_cnt - 1].hash[1], 32);
      71           0 :       bmt->leaf_cnt++;
      72           0 :     }
      73           0 :     for (ulong i = 0; i < bmt->leaf_cnt; i += 2) {
      74           0 :       uchar *d = this[i].hash;
      75           0 :       d[0] = (uchar) 1;
      76           0 :       ulong hi = i / 2; // Half of i .. ie, where is this going?
      77           0 :       fd_sha256_batch_add(&bmt->sha256_batch, d, 65, &that[hi].hash[(hi & 1) ? 0 : 1]);
      78           0 :     }
      79             :     // This leaves the batch object unusable...
      80           0 :     fd_sha256_batch_fini(&bmt->sha256_batch);
      81           0 :     bmt->leaf_cnt /= 2;
      82             : 
      83             :     // start over
      84           0 :     FD_TEST (fd_sha256_batch_init(&bmt->sha256_batch) == &bmt->sha256_batch);;
      85             : 
      86           0 :     fd_wbmtree32_node_t * a = that;
      87           0 :     that = this;
      88           0 :     this = a;
      89           0 :   }
      90             : 
      91           0 :   return &this[0].hash[1];
      92           0 : }
      93             : 
      94           0 : ulong            fd_wbmtree32_align     ( void ) { return alignof(fd_wbmtree32_t); }
      95             : 
      96           0 : ulong            fd_wbmtree32_footprint ( ulong leaf_cnt ) {
      97           0 :   if (leaf_cnt & 1)
      98           0 :     leaf_cnt++;  // Round up to even numbers...
      99           0 :   return sizeof(fd_wbmtree32_t) + sizeof(fd_wbmtree32_node_t) * (leaf_cnt + (leaf_cnt / 2));
     100           0 : }