src/SHAHashSet.h

   1 //
   2 // This file is part of the aMule Project.
   3 //
   4 // Copyright (c) 2003-2008 Angel Vidal (Kry) ( kry@amule.org )
   5 // Copyright (c) 2003-2008 aMule Team ( admin@amule.org / http://www.amule.org )
   6 // Copyright (c) 2002 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
  80 #define HASHSIZE                        20
  81 #define KNOWN2_MET_FILENAME             wxT("known2_64.met")
  82 #define OLD_KNOWN2_MET_FILENAME         wxT("known2.met")
  83 #define KNOWN2_MET_VERSION              0x02
  84
  85 enum EAICHStatus {
  86         AICH_ERROR = 0,
  87         AICH_EMPTY,
  88         AICH_UNTRUSTED,
  89         AICH_TRUSTED,
  90         AICH_VERIFIED,
  91         AICH_HASHSETCOMPLETE
  92 };
  93
  94 class CFileDataIO;
  95 class CKnownFile;
  96 class CMemFile;
  97 class CPartFile;
  98 class CUpDownClient;
  99
 100
 101 /////////////////////////////////////////////////////////////////////////////////////////
 102 ///CAICHHash
 103 class CAICHHash
 104 {
 105 private:
 106         byte m_abyBuffer[HASHSIZE];
 107
 108 public:
 109         CAICHHash()                             { memset(m_abyBuffer, 0, HASHSIZE); }
 110         CAICHHash(CFileDataIO* file)            { Read(file); }
 111         CAICHHash(byte* data)                   { Read(data); }
 112         CAICHHash(const CAICHHash& k1)          { *this = k1; }
 113         ~CAICHHash() {}
 114         CAICHHash& operator=(const CAICHHash& k1)
 115         {
 116                 memcpy(m_abyBuffer, k1.m_abyBuffer, HASHSIZE);
 117                 return *this;
 118         }
 119         friend bool operator==(const CAICHHash& k1,const CAICHHash& k2)
 120         {
 121                 return memcmp(k1.m_abyBuffer, k2.m_abyBuffer, HASHSIZE) == 0;
 122         }
 123         friend bool operator!=(const CAICHHash& k1,const CAICHHash& k2) { return !(k1 == k2); }
 124         void Read(CFileDataIO* file);
 125         void Write(CFileDataIO* file) const;
 126         void Read(byte* data)                   { memcpy(m_abyBuffer, data, HASHSIZE); }
 127         wxString GetString() const;
 128         byte* GetRawHash()                      { return m_abyBuffer; }
 129         static uint32 GetHashSize()             { return HASHSIZE;}
 130         unsigned int DecodeBase32(const wxString &base32);
 131 };
 132
 133 /////////////////////////////////////////////////////////////////////////////////////////
 134 ///CAICHHashAlgo
 135 class CAICHHashAlgo
 136 {
 137 public:
 138         virtual ~CAICHHashAlgo() {};
 139         virtual void Reset() = 0;
 140         virtual void Add(const void* pData, uint32 nLength) = 0;
 141         virtual void Finish(CAICHHash& Hash) = 0;
 142         virtual void GetHash(CAICHHash& Hash) = 0;
 143 };
 144
 145 /////////////////////////////////////////////////////////////////////////////////////////
 146 ///CAICHHashTree
 147 class CAICHHashTree
 148 {
 149         friend class CAICHHashSet;
 150 private:
 151         CAICHHash m_Hash;
 152         uint64 m_nDataSize;     // size of data which is covered by this hash
 153         uint64 m_nBaseSize;     // blocksize on which the lowest hash is based on
 154         bool m_bIsLeftBranch;   // left or right branch of the tree
 155         bool m_bHashValid;      // the hash is valid and not empty
 156         CAICHHashTree* m_pLeftTree;
 157         CAICHHashTree* m_pRightTree;
 158
 159 public:
 160         CAICHHashTree(uint64 nDataSize, bool bLeftBranch, uint64 nBaseSize);
 161         ~CAICHHashTree();
 162
 163         const CAICHHash &GetHash() const        { return m_Hash; }
 164         uint64 GetNDataSize() const             { return m_nDataSize; }
 165         uint64 GetNBaseSize() const             { return m_nBaseSize; }
 166         bool GetIsLeftBranch() const            { return m_bIsLeftBranch; }
 167         bool GetHashValid() const               { return m_bHashValid; }
 168
 169         void SetBlockHash(uint64 nSize, uint64 nStartPos, CAICHHashAlgo* pHashAlg);
 170         bool ReCalculateHash(CAICHHashAlgo* hashalg, bool bDontReplace );
 171         bool VerifyHashTree(CAICHHashAlgo* hashalg, bool bDeleteBadTrees);
 172         CAICHHashTree* FindHash(uint64 nStartPos, uint64 nSize)
 173         {
 174                 uint8 buffer = 0;
 175                 return FindHash(nStartPos, nSize, &buffer);
 176         }
 177
 178 protected:
 179         CAICHHashTree* FindHash(uint64 nStartPos, uint64 nSize, uint8* nLevel);
 180         bool CreatePartRecoveryData(uint64 nStartPos, uint64 nSize,
 181                 CFileDataIO* fileDataOut, uint32 wHashIdent, bool b32BitIdent);
 182         void WriteHash(CFileDataIO* fileDataOut, uint32 wHashIdent, bool b32BitIdent) const;
 183         bool WriteLowestLevelHashs(CFileDataIO* fileDataOut,
 184                 uint32 wHashIdent, bool bNoIdent, bool b32BitIdent) const;
 185         bool LoadLowestLevelHashs(CFileDataIO* fileInput);
 186         bool SetHash(CFileDataIO* fileInput, uint32 wHashIdent, sint8 nLevel = (-1), bool bAllowOverwrite = true);
 187 };
 188
 189 /////////////////////////////////////////////////////////////////////////////////////////
 190 ///CAICHUntrustedHashs
 191 class CAICHUntrustedHash {
 192 public:
 193         CAICHUntrustedHash& operator=(const CAICHUntrustedHash& k1)
 194         {
 195                 m_adwIpsSigning = k1.m_adwIpsSigning;
 196                 m_Hash = k1.m_Hash ;
 197                 return *this;
 198         }
 199         bool AddSigningIP(uint32 dwIP);
 200
 201         CAICHHash m_Hash;
 202         std::set<uint32> m_adwIpsSigning;
 203 };
 204
 205 /////////////////////////////////////////////////////////////////////////////////////////
 206 ///CAICHUntrustedHashs
 207 class CAICHRequestedData {
 208 public:
 209         CAICHRequestedData()
 210         {
 211                 m_nPart = 0;
 212                 m_pPartFile = NULL;
 213                 m_pClient= 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         CUpDownClient* 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