hashtree.cpp

   1 /*
   2  *  hashtree.cpp
   3  *  serp++
   4  *
   5  *  Created by Victor Grishchenko on 3/6/09.
   6  *  Copyright 2009 Delft Technical University. All rights reserved.
   7  *
   8  */
   9
  10 #include "hashtree.h"
  11 #include <openssl/sha.h>
  12 #include <string.h>
  13 #include <sys/mman.h>
  14 #include <sys/stat.h>
  15 #include <stdlib.h>
  16 #include <fcntl.h>
  17
  18 using namespace std;
  19
  20 #define HASHSZ 20
  21 const size_t Sha1Hash::SIZE = HASHSZ;
  22 const Sha1Hash Sha1Hash::ZERO = Sha1Hash();
  23
  24 Sha1Hash::Sha1Hash(const Sha1Hash& left, const Sha1Hash& right) {
  25         uint8_t data[HASHSZ*2];
  26         memcpy(data,left.bits,SIZE);
  27         memcpy(data+SIZE,right.bits,SIZE);
  28         SHA1(data,SIZE*2,bits);
  29 }
  30
  31 Sha1Hash::Sha1Hash(const uint8_t* data, size_t length) {
  32         SHA1(data,length,bits);
  33 }
  34
  35 Sha1Hash::Sha1Hash(const char* str) {
  36         SHA1((const unsigned char*)str,strlen(str),bits);
  37 }
  38
  39 Sha1Hash::Sha1Hash(bool hex, const char* hash) {
  40         assert(!hex);
  41         memcpy(bits,hash,SIZE);
  42 }
  43
  44 string  Sha1Hash::hex() const {
  45         char hex[HASHSZ*2+1];
  46         for(int i=0; i<HASHSZ; i++)
  47                 sprintf(hex+i*2, "%02x", bits[i]);
  48         return string(hex,HASHSZ*2);
  49 }
  50
  51
  52
  53 /*void  HashTree::expand (bin tolen) {
  54         if (bits)
  55                 munmap(bits,length*HASHSZ);
  56         length = tolen;
  57         status.resize(length);
  58         bits = (Sha1Hash*) mmap(NULL,length*HASHSZ,PROT_READ|PROT_WRITE,MAP_SHARED,fd,0);
  59 }*/
  60
  61
  62 /*Sha1Hash HashTree::deriveRoot () {
  63         int i = peaks.size()-1;
  64         bin p = peaks[i].first;
  65         Sha1Hash hash = peaks[i].second;
  66         i--;
  67         while (p<bin::ALL) {
  68                 if (p.is_left()) {
  69                         p = p.parent();
  70                         hash = Sha1Hash(hash,Sha1Hash::ZERO);
  71                 } else {
  72                         if (i<0 || peaks[i].first!=p.sibling())
  73                                 return Sha1Hash::ZERO;
  74                         hash = Sha1Hash(peaks[i].second,hash);
  75                         p = p.parent();
  76                         i--;
  77                 }
  78         }
  79         return hash;
  80 }
  81
  82 HashTree::HashTree (int fd)  {
  83         //fd = open(filename,O_RDWR|O_CREAT,S_IRUSR|S_IWUSR|S_IRGRP|S_IROTH);
  84         if (fd<0) return;
  85         struct stat st;
  86         fstat(fd, &st);
  87         length = (st.st_size>>10) + (st.st_size%1024 ? 1 : 0);
  88         mass = bin::lenpeak(length); // incorrect
  89         bits.resize(mass+1);
  90         status.resize(mass+1);
  91         uint8_t buf[1024];
  92         for(bin i=1; i<=mass; i++)
  93                 if (i.layer()) {
  94                         bits[i] = Sha1Hash(bits[i.left()],bits[i.right()]);
  95                 } else {
  96                         int len = pread(fd,buf,1024,i.offset()<<10);
  97                         bits[i] = Sha1Hash(buf,len);
  98                 }
  99         //close(fd);
 100         bin::vec p = bin::peaks(length);
 101         while(p.size()) {
 102                 peaks.push_back(binhash(p.front(),bits[p.front()]));
 103                 p.pop_front();
 104         }
 105         root = deriveRoot();
 106 }
 107
 108 HashTree::HashTree (const Sha1Hash& with_root) : root(with_root), length(0), mass(0) {
 109         // recover the partially filled hash file
 110         // first, size
 111         // then, peaks
 112         // works? then offer the rest
 113 }
 114
 115 HashTree::~HashTree () {
 116         close(fd);
 117 }
 118
 119 HashTree::hashres_t     HashTree::offerPeak (bin pos, Sha1Hash hash) {
 120         if (bin(pos+1).layer())
 121                 return REJECT;
 122         if (bin::all1(pos))
 123                 peaks.clear();
 124         peaks.push_back(binhash(pos,hash));
 125         if (deriveRoot()==root) { // bingo
 126                 mass = peaks.back().first;
 127                 length = mass.length();
 128                 status.resize(mass+1);
 129                 bits.resize(mass+1);
 130                 for(int i=0; i<peaks.size(); i++) {
 131                         bits[peaks[i].first] = peaks[i].second;
 132                         status[peaks[i].first] = true;
 133                 }
 134                 return PEAK_ACCEPT;
 135         } else
 136                 return pos.layer() ? DUNNO : REJECT;
 137 }
 138
 139 HashTree::hashres_t     HashTree::offer (bin pos, const Sha1Hash& hash) {
 140         if (!length)  // only peak hashes are accepted at this point
 141                 return offerPeak(pos,hash);
 142         if (pos>mass)
 143                 return REJECT;
 144         if (status[pos])
 145                 return bits[pos]==hash ? ACCEPT : REJECT;
 146         bits[pos] = hash;
 147         // walk to the nearest proven hash
 148         if (bits[pos.sibling()]==Sha1Hash::ZERO)
 149                 return DUNNO;
 150         bin p = pos.parent();
 151         while (!status[p]) {
 152                 bits[p] = Sha1Hash(bits[p.left()],bits[p.right()]);
 153                 p = p.parent();
 154         }
 155         if ( bits[p] == Sha1Hash(bits[p.left()],bits[p.right()]) ) {
 156                 for(bin i=pos; i<p; i=i.parent())
 157                         status[i] = status[i.sibling()] = true;
 158                 return ACCEPT;
 159         } else
 160                 return REJECT;
 161
 162 }
 163
 164 */