src/SHAHashSet.h

   1 //
   2 // This file is part of the aMule Project.
   3 //
   4 // Copyright (c) 2004-2011 Angel Vidal ( kry@amule.org )
   5 // Copyright (c) 2003-2011 aMule Team ( admin@amule.org / http://www.amule.org )
   6 // Copyright (c) 2002-2011 Merkur ( devs@emule-project.net / http://www.emule-project.net )
   7 //
   8 // Any parts of this program derived from the xMule, lMule or eMule project,
   9 // or contributed by third-party developers are copyrighted by their
  10 // respective authors.
  11 //
  12 // This program is free software; you can redistribute it and/or modify
  13 // it under the terms of the GNU General Public License as published by
  14 // the Free Software Foundation; either version 2 of the License, or
  15 // (at your option) any later version.
  16 //
  17 // This program is distributed in the hope that it will be useful,
  18 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  19 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20 // GNU General Public License for more details.
  21 //
  22 // You should have received a copy of the GNU General Public License
  23 // along with this program; if not, write to the Free Software
  24 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301, USA
  25 //
  26
  27 /*
  28  SHA hashset basically exists of 1 Tree for all Parts (9.28MB) + n Trees
  29  for all blocks (180KB) while n is the number of Parts.
  30  This means it is NOT a complete hashtree, since the 9.28MB is a given level, in order
  31  to be able to create a hashset format similar to the MD4 one.
  32
  33  If the number of elements for the next level are odd (for example 21 blocks to spread into 2 hashs)
  34  the majority of elements will go into the left branch if the parent node was a left branch
  35  and into the right branch if the parent node was a right branch. The first node is always
  36  taken as a left branch.
  37
  38 Example tree:
  39         FileSize: 19506000 Bytes = 18,6 MB
  40
  41               X(18,6 MB)                                                MasterHash
  42              /          \
  43           X(18,55)       \
  44          /        \       \
  45   X(9,28)         X(9,28)  X(0,05MB)                            PartHashs
  46  /     \         /     \          \
  47 X(4,75) X(4,57) X(4,57) X(4,57)    X(4,75)
  48 [...............]
  49 X(180KB)   X(180KB)  [...] X(140KB) | X(180KB) X(180KB) [...]   BlockHashs
  50                                     v
  51                                     Border between first and second Part (9.28MB)
  52
  53 HashsIdentifier:
  54 When sending hashes, they are sent with a 16bit identifier which specifies its position in the
  55 tree (so StartPosition + HashDataSize would lead to the same hash)
  56 The identifier basically describes the way from the top of the tree to the hash. a set bit (1)
  57 means follow the left branch, a 0 means follow the right. The highest bit which is set is seen as the start-
  58 position (since the first node is always seen as left).
  59
  60 Example
  61
  62     x                   0000000000000001
  63    / \
  64   x   \                 0000000000000011
  65  / \   \
  66 x  _X_  x               0000000000000110
  67
  68
  69 Version 2 of AICH also supports 32bit identifiers to support large files, check CAICHHashSet::CreatePartRecoveryData
  70 */
  71
  72 #ifndef __SHAHAHSET_H__
  73 #define __SHAHAHSET_H__
  74
  75 #include <deque>
  76 #include <set>
  77
  78 #include "Types.h"
  79 #include "ClientRef.h"
  80
  81 #define HASHSIZE                        20
  82 #define KNOWN2_MET_FILENAME             wxT("known2_64.met")
  83 #define OLD_KNOWN2_MET_FILENAME         wxT("known2.met")
  84 #define KNOWN2_MET_VERSION              0x02
  85
  86 enum EAICHStatus {
  87         AICH_ERROR = 0,
  88         AICH_EMPTY,
  89         AICH_UNTRUSTED,
  90         AICH_TRUSTED,
  91         AICH_VERIFIED,
  92         AICH_HASHSETCOMPLETE
  93 };
  94
  95 class CFileDataIO;
  96 class CKnownFile;
  97 class CMemFile;
  98 class CPartFile;
  99 class CUpDownClient;
 100
 101
 102 /////////////////////////////////////////////////////////////////////////////////////////
 103 ///CAICHHash
 104 class CAICHHash
 105 {
 106 private:
 107         uint8_t m_abyBuffer[HASHSIZE];
 108
 109 public:
 110         CAICHHash()                             { memset(m_abyBuffer, 0, HASHSIZE); }
 111         CAICHHash(CFileDataIO* file)            { Read(file); }
 112         CAICHHash(uint8_t* data)                { Read(data); }
 113         CAICHHash(const CAICHHash& k1)          { *this = k1; }
 114         ~CAICHHash() {}
 115         CAICHHash& operator=(const CAICHHash& k1)
 116         {
 117                 memcpy(m_abyBuffer, k1.m_abyBuffer, HASHSIZE);
 118                 return *this;
 119         }
 120         friend bool operator==(const CAICHHash& k1,const CAICHHash& k2)
 121         {
 122                 return memcmp(k1.m_abyBuffer, k2.m_abyBuffer, HASHSIZE) == 0;
 123         }
 124         friend bool operator!=(const CAICHHash& k1,const CAICHHash& k2) { return !(k1 == k2); }
 125         void Read(CFileDataIO* file);
 126         void Write(CFileDataIO* file) const;
 127         void Read(uint8_t* data)                { memcpy(m_abyBuffer, data, HASHSIZE); }
 128         wxString GetString() const;
 129         uint8_t* GetRawHash()                   { return m_abyBuffer; }
 130         static uint32 GetHashSize()             { return HASHSIZE;}
 131         unsigned int DecodeBase32(const wxString &base32);
 132 };
 133
 134 /////////////////////////////////////////////////////////////////////////////////////////
 135 ///CAICHHashAlgo
 136 class CAICHHashAlgo
 137 {
 138 public:
 139         virtual ~CAICHHashAlgo() {};
 140         virtual void Reset() = 0;
 141         virtual void Add(const void* pData, uint32 nLength) = 0;
 142         virtual void Finish(CAICHHash& Hash) = 0;
 143         virtual void GetHash(CAICHHash& Hash) = 0;
 144 };
 145
 146 /////////////////////////////////////////////////////////////////////////////////////////
 147 ///CAICHHashTree
 148 class CAICHHashTree
 149 {
 150         friend class CAICHHashSet;
 151 private:
 152         CAICHHash m_Hash;
 153         uint64 m_nDataSize;     // size of data which is covered by this hash
 154         uint64 m_nBaseSize;     // blocksize on which the lowest hash is based on
 155         bool m_bIsLeftBranch;   // left or right branch of the tree
 156         bool m_bHashValid;      // the hash is valid and not empty
 157         CAICHHashTree* m_pLeftTree;
 158         CAICHHashTree* m_pRightTree;
 159
 160 public:
 161         CAICHHashTree(uint64 nDataSize, bool bLeftBranch, uint64 nBaseSize);
 162         ~CAICHHashTree();
 163
 164         const CAICHHash &GetHash() const        { return m_Hash; }
 165         uint64 GetNDataSize() const             { return m_nDataSize; }
 166         uint64 GetNBaseSize() const             { return m_nBaseSize; }
 167         bool GetIsLeftBranch() const            { return m_bIsLeftBranch; }
 168         bool GetHashValid() const               { return m_bHashValid; }
 169
 170         void SetBlockHash(uint64 nSize, uint64 nStartPos, CAICHHashAlgo* pHashAlg);
 171         bool ReCalculateHash(CAICHHashAlgo* hashalg, bool bDontReplace );
 172         bool VerifyHashTree(CAICHHashAlgo* hashalg, bool bDeleteBadTrees);
 173         CAICHHashTree* FindHash(uint64 nStartPos, uint64 nSize)
 174         {
 175                 uint8 buffer = 0;
 176                 return FindHash(nStartPos, nSize, &buffer);
 177         }
 178
 179 protected:
 180         CAICHHashTree* FindHash(uint64 nStartPos, uint64 nSize, uint8* nLevel);
 181         bool CreatePartRecoveryData(uint64 nStartPos, uint64 nSize,
 182                 CFileDataIO* fileDataOut, uint32 wHashIdent, bool b32BitIdent);
 183         void WriteHash(CFileDataIO* fileDataOut, uint32 wHashIdent, bool b32BitIdent) const;
 184         bool WriteLowestLevelHashs(CFileDataIO* fileDataOut,
 185                 uint32 wHashIdent, bool bNoIdent, bool b32BitIdent) const;
 186         bool LoadLowestLevelHashs(CFileDataIO* fileInput);
 187         bool SetHash(CFileDataIO* fileInput, uint32 wHashIdent, sint8 nLevel = (-1), bool bAllowOverwrite = true);
 188 };
 189
 190 /////////////////////////////////////////////////////////////////////////////////////////
 191 ///CAICHUntrustedHashs
 192 class CAICHUntrustedHash {
 193 public:
 194         CAICHUntrustedHash& operator=(const CAICHUntrustedHash& k1)
 195         {
 196                 m_adwIpsSigning = k1.m_adwIpsSigning;
 197                 m_Hash = k1.m_Hash ;
 198                 return *this;
 199         }
 200         bool AddSigningIP(uint32 dwIP);
 201
 202         CAICHHash m_Hash;
 203         std::set<uint32> m_adwIpsSigning;
 204 };
 205
 206 /////////////////////////////////////////////////////////////////////////////////////////
 207 ///CAICHUntrustedHashs
 208 class CAICHRequestedData {
 209 public:
 210         CAICHRequestedData()
 211         {
 212                 m_nPart = 0;
 213                 m_pPartFile = NULL;
 214         }
 215         CAICHRequestedData& operator=(const CAICHRequestedData& k1)
 216         {
 217                 m_nPart = k1.m_nPart;
 218                 m_pPartFile = k1.m_pPartFile;
 219                 m_pClient = k1.m_pClient;
 220                 return *this;
 221         }
 222         uint16 m_nPart;
 223         CPartFile* m_pPartFile;
 224         CClientRef m_pClient;
 225 };
 226
 227
 228 using namespace std;
 229
 230 typedef std::list<CAICHRequestedData> CAICHRequestedDataList;
 231
 232 /////////////////////////////////////////////////////////////////////////////////////////
 233 ///CAICHHashSet
 234 class CAICHHashSet
 235 {
 236 private:
 237         CKnownFile* m_pOwner;
 238         EAICHStatus m_eStatus;
 239         deque<CAICHUntrustedHash> m_aUntrustedHashs;
 240
 241 public:
 242         static CAICHRequestedDataList m_liRequestedData;
 243         CAICHHashTree m_pHashTree;
 244
 245         CAICHHashSet(CKnownFile* pOwner);
 246         ~CAICHHashSet(void);
 247         bool CreatePartRecoveryData(uint64 nPartStartPos, CFileDataIO* fileDataOut, bool bDbgDontLoad = false);
 248         bool ReadRecoveryData(uint64 nPartStartPos, CMemFile* fileDataIn);
 249         bool ReCalculateHash(bool bDontReplace = false);
 250         bool VerifyHashTree(bool bDeleteBadTrees);
 251         void UntrustedHashReceived(const CAICHHash& Hash, uint32 dwFromIP);
 252         bool IsPartDataAvailable(uint64 nPartStartPos);
 253         void SetStatus(EAICHStatus bNewValue)   { m_eStatus = bNewValue; }
 254         EAICHStatus GetStatus() const           { return m_eStatus; }
 255
 256         void FreeHashSet();
 257         void SetFileSize(uint64 nSize);
 258
 259         CAICHHash& GetMasterHash()              { return m_pHashTree.m_Hash; }
 260         void SetMasterHash(const CAICHHash& Hash, EAICHStatus eNewStatus);
 261         bool HasValidMasterHash()               { return m_pHashTree.m_bHashValid; }
 262
 263         bool SaveHashSet();
 264         bool LoadHashSet(); // only call directly when debugging
 265
 266         static CAICHHashAlgo* GetNewHashAlgo();
 267         static void ClientAICHRequestFailed(CUpDownClient* pClient);
 268         static void RemoveClientAICHRequest(const CUpDownClient* pClient);
 269         static bool IsClientRequestPending(const CPartFile* pForFile, uint16 nPart);
 270         static CAICHRequestedData GetAICHReqDetails(const  CUpDownClient* pClient);
 271         void DbgTest();
 272
 273         void SetOwner(CKnownFile* owner)        { m_pOwner = owner; }
 274 };
 275
 276 #endif  //__SHAHAHSET_H__
 277
 278 // File_checked_for_headers