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             : fd_wbmtree32_t*
      38             : fd_wbmtree32_join      ( void * mem )
      39           0 : {
      40           0 :   if( FD_UNLIKELY( !mem ) ) {
      41           0 :     FD_LOG_WARNING(( "NULL mem" ));
      42           0 :     return NULL;
      43           0 :   }
      44             : 
      45           0 :   if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)mem, fd_wbmtree32_align() ) ) ) {
      46           0 :     FD_LOG_WARNING(( "misaligned mem" ));
      47           0 :     return NULL;
      48           0 :   }
      49           0 :   fd_wbmtree32_t* hdr = (fd_wbmtree32_t*) mem;
      50           0 :   return hdr;
      51           0 : }
      52             : 
      53             : void *
      54           0 : fd_wbmtree32_leave      ( fd_wbmtree32_t* hdr ) {
      55           0 :   if( FD_UNLIKELY( !hdr ) ) {
      56           0 :     FD_LOG_WARNING(( "NULL mem" ));
      57           0 :     return NULL;
      58           0 :   }
      59           0 :   return (void *) hdr;
      60           0 : }
      61             : 
      62             : void
      63             : fd_wbmtree32_append    ( fd_wbmtree32_t * bmt, fd_wbmtree32_leaf_t const * leaf, ulong leaf_cnt, uchar *mbuf  )
      64           0 : {
      65           0 :   FD_TEST ((bmt->leaf_cnt + leaf_cnt) <= bmt->leaf_cnt_max);
      66             : 
      67           0 :   fd_wbmtree32_node_t *n = &((fd_wbmtree32_node_t *)bmt->data)[bmt->leaf_cnt];
      68           0 :   for (ulong i = 0; i < leaf_cnt; i++) {
      69           0 :     mbuf[0] = (uchar) 0;
      70           0 :     fd_memcpy(&mbuf[1], leaf->data, leaf->data_len);
      71           0 :     fd_sha256_batch_add(&bmt->sha256_batch, mbuf, leaf->data_len + 1, &n->hash[(i & 1) ? 0 : 1]);
      72           0 :     mbuf += leaf->data_len + 1;
      73           0 :     n++;
      74           0 :     leaf++;
      75           0 :   }
      76           0 :   fd_sha256_batch_fini(&bmt->sha256_batch);
      77           0 :   bmt->leaf_cnt += leaf_cnt;
      78             : 
      79           0 :   FD_TEST (leaf_cnt <= bmt->leaf_cnt_max);
      80           0 : }
      81             : 
      82             : uchar *
      83             : fd_wbmtree32_fini      ( fd_wbmtree32_t * bmt)
      84           0 : {
      85           0 :   FD_TEST ( bmt->leaf_cnt <= bmt->leaf_cnt_max );
      86             : 
      87           0 :   fd_wbmtree32_node_t *this = (fd_wbmtree32_node_t *)bmt->data;
      88           0 :   fd_wbmtree32_node_t *that = &((fd_wbmtree32_node_t *)bmt->data)[bmt->leaf_cnt + (bmt->leaf_cnt & 1)];
      89             : 
      90           0 :   while (bmt->leaf_cnt > 1) {
      91             :     // If the tree is uneven, we duplicate the last hash
      92           0 :     if (bmt->leaf_cnt & 1) {
      93             :       // In the source data, the bytes are offset by 1 to give us room
      94             :       // for the 1 byte... in the target, it is not offset by one..
      95           0 :       fd_memcpy(this[bmt->leaf_cnt].hash, &this[bmt->leaf_cnt - 1].hash[1], 32);
      96           0 :       bmt->leaf_cnt++;
      97           0 :     }
      98           0 :     for (ulong i = 0; i < bmt->leaf_cnt; i += 2) {
      99           0 :       uchar *d = this[i].hash;
     100           0 :       d[0] = (uchar) 1;
     101           0 :       ulong hi = i / 2; // Half of i .. ie, where is this going?
     102           0 :       fd_sha256_batch_add(&bmt->sha256_batch, d, 65, &that[hi].hash[(hi & 1) ? 0 : 1]);
     103           0 :     }
     104             :     // This leaves the batch object unusable...
     105           0 :     fd_sha256_batch_fini(&bmt->sha256_batch);
     106           0 :     bmt->leaf_cnt /= 2;
     107             : 
     108             :     // start over
     109           0 :     FD_TEST (fd_sha256_batch_init(&bmt->sha256_batch) == &bmt->sha256_batch);;
     110             : 
     111           0 :     fd_wbmtree32_node_t * a = that;
     112           0 :     that = this;
     113           0 :     this = a;
     114           0 :   }
     115             : 
     116           0 :   return &this[0].hash[1];
     117           0 : }
     118             : 
     119             : void *
     120           0 : fd_wbmtree32_delete( void * shblock ) {
     121           0 :   if( FD_UNLIKELY( !shblock ) ) {
     122           0 :     FD_LOG_WARNING(( "NULL shblock" ));
     123           0 :     return NULL;
     124           0 :   }
     125             : 
     126           0 :   if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shblock, fd_wbmtree32_align() ) ) ) {
     127           0 :     FD_LOG_WARNING(( "misaligned shblock" ));
     128           0 :     return NULL;
     129           0 :   }
     130             : 
     131           0 :   return shblock;
     132           0 : }
     133             : 
     134           0 : ulong            fd_wbmtree32_align     ( void ) { return alignof(fd_wbmtree32_t); }
     135             : 
     136           0 : ulong            fd_wbmtree32_footprint ( ulong leaf_cnt ) {
     137           0 :   if (leaf_cnt & 1)
     138           0 :     leaf_cnt++;  // Round up to even numbers...
     139           0 :   return sizeof(fd_wbmtree32_t) + sizeof(fd_wbmtree32_node_t) * (leaf_cnt + (leaf_cnt / 2));
     140           0 : }