Upstream tarball 9882
[amule.git] / src / SHAHashSet.cpp
blob5653aa01200342e13925347a86ac23194f4f751c
1 //
2 // This file is part of the aMule Project.
3 //
4 // Copyright (c) 2004-2008 Angel Vidal ( kry@amule.org )
5 // Copyright (c) 2003-2008 aMule Team ( admin@amule.org / http://www.amule.org )
6 // Copyright (c) 2002-2008 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.
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.
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
27 #include <wx/file.h>
29 #include "SHAHashSet.h"
30 #include "amule.h"
31 #include "MemFile.h"
32 #include "Preferences.h"
33 #include "SHA.h"
34 #include "updownclient.h"
35 #include "DownloadQueue.h"
36 #include "PartFile.h"
37 #include "Logger.h"
38 #include <common/Format.h>
42 // for this version the limits are set very high, they might be lowered later
43 // to make a hash trustworthy, at least 10 unique Ips (255.255.128.0) must have sent it
44 // and if we have received more than one hash for the file, one hash has to be sent by more than 95% of all unique IPs
45 #define MINUNIQUEIPS_TOTRUST 10 // how many unique IPs have to send us a hash to make it trustworthy
46 #define MINPERCENTAGE_TOTRUST 92 // how many percentage of clients have to send the same hash to make it trustworthy
48 CAICHRequestedDataList CAICHHashSet::m_liRequestedData;
50 /////////////////////////////////////////////////////////////////////////////////////////
51 ///CAICHHash
52 wxString CAICHHash::GetString() const
54 return EncodeBase32(m_abyBuffer, HASHSIZE);
58 void CAICHHash::Read(CFileDataIO* file)
60 file->Read(m_abyBuffer,HASHSIZE);
64 void CAICHHash::Write(CFileDataIO* file) const
66 file->Write(m_abyBuffer,HASHSIZE);
69 unsigned int CAICHHash::DecodeBase32(const wxString &base32)
71 return ::DecodeBase32(base32, HASHSIZE, m_abyBuffer);
75 /////////////////////////////////////////////////////////////////////////////////////////
76 ///CAICHHashTree
78 CAICHHashTree::CAICHHashTree(uint64 nDataSize, bool bLeftBranch, uint64 nBaseSize)
80 m_nDataSize = nDataSize;
81 m_nBaseSize = nBaseSize;
82 m_bIsLeftBranch = bLeftBranch;
83 m_pLeftTree = NULL;
84 m_pRightTree = NULL;
85 m_bHashValid = false;
89 CAICHHashTree::~CAICHHashTree()
91 delete m_pLeftTree;
92 delete m_pRightTree;
96 // recursive
97 CAICHHashTree* CAICHHashTree::FindHash(uint64 nStartPos, uint64 nSize, uint8* nLevel)
99 (*nLevel)++;
101 wxCHECK(*nLevel <= 22, NULL);
102 wxCHECK(nStartPos + nSize <= m_nDataSize, NULL);
103 wxCHECK(nSize <= m_nDataSize, NULL);
105 if (nStartPos == 0 && nSize == m_nDataSize) {
106 // this is the searched hash
107 return this;
108 } else if (m_nDataSize <= m_nBaseSize) { // sanity
109 // this is already the last level, cant go deeper
110 wxFAIL;
111 return NULL;
112 } else {
113 uint64 nBlocks = m_nDataSize / m_nBaseSize + ((m_nDataSize % m_nBaseSize != 0 )? 1:0);
114 uint64 nLeft = (((m_bIsLeftBranch) ? nBlocks+1:nBlocks) / 2)* m_nBaseSize;
115 uint64 nRight = m_nDataSize - nLeft;
116 if (nStartPos < nLeft) {
117 if (nStartPos + nSize > nLeft) { // sanity
118 wxFAIL;
119 return NULL;
122 if (m_pLeftTree == NULL) {
123 m_pLeftTree = new CAICHHashTree(nLeft, true, (nLeft <= PARTSIZE) ? EMBLOCKSIZE : PARTSIZE);
124 } else {
125 wxASSERT( m_pLeftTree->m_nDataSize == nLeft );
128 return m_pLeftTree->FindHash(nStartPos, nSize, nLevel);
129 } else {
130 nStartPos -= nLeft;
131 if (nStartPos + nSize > nRight) { // sanity
132 wxFAIL;
133 return NULL;
136 if (m_pRightTree == NULL) {
137 m_pRightTree = new CAICHHashTree(nRight, false, (nRight <= PARTSIZE) ? EMBLOCKSIZE : PARTSIZE);
138 } else {
139 wxASSERT( m_pRightTree->m_nDataSize == nRight );
142 return m_pRightTree->FindHash(nStartPos, nSize, nLevel);
148 // recursive
149 // calculates missing hash fromt he existing ones
150 // overwrites existing hashs
151 // fails if no hash is found for any branch
152 bool CAICHHashTree::ReCalculateHash(CAICHHashAlgo* hashalg, bool bDontReplace)
154 wxASSERT ( !( (m_pLeftTree != NULL) ^ (m_pRightTree != NULL)) );
155 if (m_pLeftTree && m_pRightTree) {
156 if ( !m_pLeftTree->ReCalculateHash(hashalg, bDontReplace) || !m_pRightTree->ReCalculateHash(hashalg, bDontReplace) ) {
157 return false;
159 if (bDontReplace && m_bHashValid) {
160 return true;
162 if (m_pRightTree->m_bHashValid && m_pLeftTree->m_bHashValid) {
163 hashalg->Reset();
164 hashalg->Add(m_pLeftTree->m_Hash.GetRawHash(), HASHSIZE);
165 hashalg->Add(m_pRightTree->m_Hash.GetRawHash(), HASHSIZE);
166 hashalg->Finish(m_Hash);
167 m_bHashValid = true;
168 return true;
169 } else {
170 return m_bHashValid;
172 } else {
173 return true;
177 bool CAICHHashTree::VerifyHashTree(CAICHHashAlgo* hashalg, bool bDeleteBadTrees)
179 if (!m_bHashValid) {
180 wxFAIL;
181 if (bDeleteBadTrees) {
182 if (m_pLeftTree) {
183 delete m_pLeftTree;
184 m_pLeftTree = NULL;
186 if (m_pRightTree) {
187 delete m_pRightTree;
188 m_pRightTree = NULL;
191 AddDebugLogLineM( false, logSHAHashSet, wxT("VerifyHashTree - No masterhash available"));
192 return false;
195 // calculated missing hashs without overwriting anything
196 if (m_pLeftTree && !m_pLeftTree->m_bHashValid) {
197 m_pLeftTree->ReCalculateHash(hashalg, true);
199 if (m_pRightTree && !m_pRightTree->m_bHashValid) {
200 m_pRightTree->ReCalculateHash(hashalg, true);
203 if ((m_pRightTree && m_pRightTree->m_bHashValid) ^ (m_pLeftTree && m_pLeftTree->m_bHashValid)) {
204 // one branch can never be verified
205 if (bDeleteBadTrees) {
206 if (m_pLeftTree) {
207 delete m_pLeftTree;
208 m_pLeftTree = NULL;
210 if (m_pRightTree) {
211 delete m_pRightTree;
212 m_pRightTree = NULL;
215 AddDebugLogLineM( false, logSHAHashSet, wxT("VerifyHashSet failed - Hashtree incomplete"));
216 return false;
218 if ((m_pRightTree && m_pRightTree->m_bHashValid) && (m_pLeftTree && m_pLeftTree->m_bHashValid)) {
219 // check verify the hashs of both child nodes against my hash
221 CAICHHash CmpHash;
222 hashalg->Reset();
223 hashalg->Add(m_pLeftTree->m_Hash.GetRawHash(), HASHSIZE);
224 hashalg->Add(m_pRightTree->m_Hash.GetRawHash(), HASHSIZE);
225 hashalg->Finish(CmpHash);
227 if (m_Hash != CmpHash) {
228 if (bDeleteBadTrees) {
229 if (m_pLeftTree) {
230 delete m_pLeftTree;
231 m_pLeftTree = NULL;
233 if (m_pRightTree) {
234 delete m_pRightTree;
235 m_pRightTree = NULL;
238 return false;
240 return m_pLeftTree->VerifyHashTree(hashalg, bDeleteBadTrees) && m_pRightTree->VerifyHashTree(hashalg, bDeleteBadTrees);
241 } else {
242 // last hash in branch - nothing below to verify
243 return true;
248 void CAICHHashTree::SetBlockHash(uint64 nSize, uint64 nStartPos, CAICHHashAlgo* pHashAlg)
250 wxASSERT ( nSize <= EMBLOCKSIZE );
251 CAICHHashTree* pToInsert = FindHash(nStartPos, nSize);
252 if (pToInsert == NULL) { // sanity
253 wxFAIL;
254 AddDebugLogLineM( false, logSHAHashSet, wxT("Critical Error: Failed to Insert SHA-HashBlock, FindHash() failed!"));
255 return;
258 //sanity
259 if (pToInsert->m_nBaseSize != EMBLOCKSIZE || pToInsert->m_nDataSize != nSize) {
260 wxFAIL;
261 AddDebugLogLineM( false, logSHAHashSet, wxT("Critical Error: Logical error on values in SetBlockHashFromData"));
262 return;
265 pHashAlg->Finish(pToInsert->m_Hash);
266 pToInsert->m_bHashValid = true;
270 bool CAICHHashTree::CreatePartRecoveryData(uint64 nStartPos, uint64 nSize, CFileDataIO* fileDataOut, uint32 wHashIdent, bool b32BitIdent)
272 wxCHECK(nStartPos + nSize <= m_nDataSize, false);
273 wxCHECK(nSize <= m_nDataSize, false);
275 if (nStartPos == 0 && nSize == m_nDataSize) {
276 // this is the searched part, now write all blocks of this part
277 // hashident for this level will be adjsuted by WriteLowestLevelHash
278 return WriteLowestLevelHashs(fileDataOut, wHashIdent, false, b32BitIdent);
279 } else if (m_nDataSize <= m_nBaseSize) { // sanity
280 // this is already the last level, cant go deeper
281 wxFAIL;
282 return false;
283 } else {
284 wHashIdent <<= 1;
285 wHashIdent |= (m_bIsLeftBranch) ? 1: 0;
287 uint64 nBlocks = m_nDataSize / m_nBaseSize + ((m_nDataSize % m_nBaseSize != 0 )? 1:0);
288 uint64 nLeft = ( ((m_bIsLeftBranch) ? nBlocks+1:nBlocks) / 2)* m_nBaseSize;
289 uint64 nRight = m_nDataSize - nLeft;
290 if (m_pLeftTree == NULL || m_pRightTree == NULL) {
291 wxFAIL;
292 return false;
294 if (nStartPos < nLeft) {
295 if (nStartPos + nSize > nLeft || !m_pRightTree->m_bHashValid) { // sanity
296 wxFAIL;
297 return false;
299 m_pRightTree->WriteHash(fileDataOut, wHashIdent, b32BitIdent);
300 return m_pLeftTree->CreatePartRecoveryData(nStartPos, nSize, fileDataOut, wHashIdent, b32BitIdent);
301 } else {
302 nStartPos -= nLeft;
303 if (nStartPos + nSize > nRight || !m_pLeftTree->m_bHashValid) { // sanity
304 wxFAIL;
305 return false;
307 m_pLeftTree->WriteHash(fileDataOut, wHashIdent, b32BitIdent);
308 return m_pRightTree->CreatePartRecoveryData(nStartPos, nSize, fileDataOut, wHashIdent, b32BitIdent);
315 void CAICHHashTree::WriteHash(CFileDataIO* fileDataOut, uint32 wHashIdent, bool b32BitIdent) const
317 wxASSERT( m_bHashValid );
318 wHashIdent <<= 1;
319 wHashIdent |= (m_bIsLeftBranch) ? 1: 0;
321 if (!b32BitIdent) {
322 wxASSERT( wHashIdent <= 0xFFFF );
323 fileDataOut->WriteUInt16((uint16)wHashIdent);
324 } else {
325 fileDataOut->WriteUInt32(wHashIdent);
328 m_Hash.Write(fileDataOut);
332 // write lowest level hashs into file, ordered from left to right optional without identifier
333 bool CAICHHashTree::WriteLowestLevelHashs(CFileDataIO* fileDataOut, uint32 wHashIdent, bool bNoIdent, bool b32BitIdent) const
335 wHashIdent <<= 1;
336 wHashIdent |= (m_bIsLeftBranch) ? 1: 0;
337 if (m_pLeftTree == NULL && m_pRightTree == NULL) {
338 if (m_nDataSize <= m_nBaseSize && m_bHashValid ) {
339 if (!bNoIdent && !b32BitIdent) {
340 wxASSERT( wHashIdent <= 0xFFFF );
341 fileDataOut->WriteUInt16((uint16)wHashIdent);
342 } else if (!bNoIdent && b32BitIdent) {
343 fileDataOut->WriteUInt32(wHashIdent);
346 m_Hash.Write(fileDataOut);
347 return true;
348 } else {
349 wxFAIL;
350 return false;
352 } else if (m_pLeftTree == NULL || m_pRightTree == NULL) {
353 wxFAIL;
354 return false;
355 } else {
356 return m_pLeftTree->WriteLowestLevelHashs(fileDataOut, wHashIdent, bNoIdent, b32BitIdent)
357 && m_pRightTree->WriteLowestLevelHashs(fileDataOut, wHashIdent, bNoIdent, b32BitIdent);
361 // recover all low level hashs from given data. hashs are assumed to be ordered in left to right - no identifier used
362 bool CAICHHashTree::LoadLowestLevelHashs(CFileDataIO* fileInput)
364 if (m_nDataSize <= m_nBaseSize) { // sanity
365 // lowest level, read hash
366 m_Hash.Read(fileInput);
367 m_bHashValid = true;
368 return true;
369 } else {
370 uint64 nBlocks = m_nDataSize / m_nBaseSize + ((m_nDataSize % m_nBaseSize != 0 )? 1:0);
371 uint64 nLeft = ( ((m_bIsLeftBranch) ? nBlocks+1:nBlocks) / 2)* m_nBaseSize;
372 uint64 nRight = m_nDataSize - nLeft;
373 if (m_pLeftTree == NULL) {
374 m_pLeftTree = new CAICHHashTree(nLeft, true, (nLeft <= PARTSIZE) ? EMBLOCKSIZE : PARTSIZE);
375 } else {
376 wxASSERT( m_pLeftTree->m_nDataSize == nLeft );
378 if (m_pRightTree == NULL) {
379 m_pRightTree = new CAICHHashTree(nRight, false, (nRight <= PARTSIZE) ? EMBLOCKSIZE : PARTSIZE);
380 } else {
381 wxASSERT( m_pRightTree->m_nDataSize == nRight );
383 return m_pLeftTree->LoadLowestLevelHashs(fileInput)
384 && m_pRightTree->LoadLowestLevelHashs(fileInput);
389 // write the hash, specified by wHashIdent, with Data from fileInput.
390 bool CAICHHashTree::SetHash(CFileDataIO* fileInput, uint32 wHashIdent, sint8 nLevel, bool bAllowOverwrite)
392 if (nLevel == (-1)) {
393 // first call, check how many level we need to go
394 uint8 i = 0;
395 for (; i != 32 && (wHashIdent & 0x80000000) == 0; ++i) {
396 wHashIdent <<= 1;
398 if (i > 31) {
399 AddDebugLogLineM( false, logSHAHashSet, wxT("CAICHHashTree::SetHash - found invalid HashIdent (0)"));
400 return false;
401 } else {
402 nLevel = 31 - i;
405 if (nLevel == 0) {
406 // this is the searched hash
407 if (m_bHashValid && !bAllowOverwrite) {
408 // not allowed to overwrite this hash, however move the filepointer by reading a hash
409 CAICHHash(file);
410 return true;
412 m_Hash.Read(fileInput);
413 m_bHashValid = true;
414 return true;
415 } else if (m_nDataSize <= m_nBaseSize) { // sanity
416 // this is already the last level, cant go deeper
417 wxFAIL;
418 return false;
419 } else {
420 // adjust ident to point the path to the next node
421 wHashIdent <<= 1;
422 nLevel--;
423 uint64 nBlocks = m_nDataSize / m_nBaseSize + ((m_nDataSize % m_nBaseSize != 0 )? 1:0);
424 uint64 nLeft = ( ((m_bIsLeftBranch) ? nBlocks+1:nBlocks) / 2)* m_nBaseSize;
425 uint64 nRight = m_nDataSize - nLeft;
426 if ((wHashIdent & 0x80000000) > 0) {
427 if (m_pLeftTree == NULL) {
428 m_pLeftTree = new CAICHHashTree(nLeft, true, (nLeft <= PARTSIZE) ? EMBLOCKSIZE : PARTSIZE);
429 } else {
430 wxASSERT( m_pLeftTree->m_nDataSize == nLeft );
432 return m_pLeftTree->SetHash(fileInput, wHashIdent, nLevel);
433 } else {
434 if (m_pRightTree == NULL) {
435 m_pRightTree = new CAICHHashTree(nRight, false, (nRight <= PARTSIZE) ? EMBLOCKSIZE : PARTSIZE);
436 } else {
437 wxASSERT( m_pRightTree->m_nDataSize == nRight );
439 return m_pRightTree->SetHash(fileInput, wHashIdent, nLevel);
445 /////////////////////////////////////////////////////////////////////////////////////////
446 ///CAICHUntrustedHash
447 bool CAICHUntrustedHash::AddSigningIP(uint32 dwIP)
449 dwIP &= 0x00F0FFFF; // we use only the 20 most significant bytes for unique IPs
450 return m_adwIpsSigning.insert(dwIP).second;
455 /////////////////////////////////////////////////////////////////////////////////////////
456 ///CAICHHashSet
457 CAICHHashSet::CAICHHashSet(CKnownFile* pOwner)
458 : m_pHashTree(0, true, PARTSIZE)
460 m_eStatus = AICH_EMPTY;
461 m_pOwner = pOwner;
464 CAICHHashSet::~CAICHHashSet(void)
466 FreeHashSet();
469 bool CAICHHashSet::CreatePartRecoveryData(uint64 nPartStartPos, CFileDataIO* fileDataOut, bool bDbgDontLoad)
471 wxASSERT( m_pOwner );
472 if (m_pOwner->IsPartFile() || m_eStatus != AICH_HASHSETCOMPLETE) {
473 wxFAIL;
474 return false;
476 if (m_pHashTree.m_nDataSize <= EMBLOCKSIZE) {
477 wxFAIL;
478 return false;
480 if (!bDbgDontLoad) {
481 if (!LoadHashSet()) {
482 AddDebugLogLineM(false, logSHAHashSet,
483 CFormat(wxT("Created RecoveryData error: failed to load hashset. File: %s")) % m_pOwner->GetFileName());
484 SetStatus(AICH_ERROR);
485 return false;
488 bool bResult;
489 uint8 nLevel = 0;
490 uint32 nPartSize = min<uint64>(PARTSIZE, m_pOwner->GetFileSize()-nPartStartPos);
491 m_pHashTree.FindHash(nPartStartPos, nPartSize,&nLevel);
492 uint16 nHashsToWrite = (nLevel-1) + nPartSize/EMBLOCKSIZE + ((nPartSize % EMBLOCKSIZE != 0 )? 1:0);
493 const bool bUse32BitIdentifier = m_pOwner->IsLargeFile();
495 if (bUse32BitIdentifier) {
496 fileDataOut->WriteUInt16(0); // no 16bit hashs to write
499 fileDataOut->WriteUInt16(nHashsToWrite);
500 uint64 nCheckFilePos = fileDataOut->GetPosition();
501 if (m_pHashTree.CreatePartRecoveryData(nPartStartPos, nPartSize, fileDataOut, 0, bUse32BitIdentifier)) {
502 if (nHashsToWrite*(HASHSIZE+(bUse32BitIdentifier? 4u:2u)) != fileDataOut->GetPosition() - nCheckFilePos) {
503 wxFAIL;
504 AddDebugLogLineM( false, logSHAHashSet,
505 CFormat(wxT("Created RecoveryData has wrong length. File: %s")) % m_pOwner->GetFileName() );
506 bResult = false;
507 SetStatus(AICH_ERROR);
508 } else {
509 bResult = true;
511 } else {
512 AddDebugLogLineM(false, logSHAHashSet,
513 CFormat(wxT("Failed to create RecoveryData for '%s'")) % m_pOwner->GetFileName());
514 bResult = false;
515 SetStatus(AICH_ERROR);
517 if (!bUse32BitIdentifier) {
518 fileDataOut->WriteUInt16(0); // no 32bit hashs to write
521 if (!bDbgDontLoad) {
522 FreeHashSet();
524 return bResult;
527 bool CAICHHashSet::ReadRecoveryData(uint64 nPartStartPos, CMemFile* fileDataIn)
529 if (/*eMule TODO !m_pOwner->IsPartFile() ||*/ !(m_eStatus == AICH_VERIFIED || m_eStatus == AICH_TRUSTED) ) {
530 wxFAIL;
531 return false;
534 /* V2 AICH Hash Packet:
535 <count1 uint16> 16bit-hashs-to-read
536 (<identifier uint16><hash HASHSIZE>)[count1] AICH hashs
537 <count2 uint16> 32bit-hashs-to-read
538 (<identifier uint32><hash HASHSIZE>)[count2] AICH hashs
541 // at this time we check the recoverydata for the correct ammounts of hashs only
542 // all hash are then taken into the tree, depending on there hashidentifier (except the masterhash)
544 uint8 nLevel = 0;
545 uint32 nPartSize = min<uint64>(PARTSIZE, m_pOwner->GetFileSize()-nPartStartPos);
546 m_pHashTree.FindHash(nPartStartPos, nPartSize,&nLevel);
547 uint16 nHashsToRead = (nLevel-1) + nPartSize/EMBLOCKSIZE + ((nPartSize % EMBLOCKSIZE != 0 )? 1:0);
549 // read hashs with 16 bit identifier
550 uint16 nHashsAvailable = fileDataIn->ReadUInt16();
551 if (fileDataIn->GetLength()-fileDataIn->GetPosition() < nHashsToRead*(HASHSIZE+2u) || (nHashsToRead != nHashsAvailable && nHashsAvailable != 0)) {
552 // this check is redunant, CSafememfile would catch such an error too
553 AddDebugLogLineM( false, logSHAHashSet,
554 CFormat(wxT("Failed to read RecoveryData for '%s' - Received datasize/amounts of hashs was invalid"))
555 % m_pOwner->GetFileName());
556 return false;
558 for (uint32 i = 0; i != nHashsAvailable; i++) {
559 uint16 wHashIdent = fileDataIn->ReadUInt16();
560 if (wHashIdent == 1 /*never allow masterhash to be overwritten*/
561 || !m_pHashTree.SetHash(fileDataIn, wHashIdent,(-1), false))
563 AddDebugLogLineM( false, logSHAHashSet,
564 CFormat(wxT("Failed to read RecoveryData for '%s' - Error when trying to read hash into tree"))
565 % m_pOwner->GetFileName());
566 VerifyHashTree(true); // remove invalid hashs which we have already written
567 return false;
572 // read hashs with 32bit identifier
573 if (nHashsAvailable == 0 && fileDataIn->GetLength() - fileDataIn->GetPosition() >= 2) {
574 nHashsAvailable = fileDataIn->ReadUInt16();
575 if (fileDataIn->GetLength()-fileDataIn->GetPosition() < nHashsToRead*(HASHSIZE+4u) || (nHashsToRead != nHashsAvailable && nHashsAvailable != 0)) {
576 // this check is redunant, CSafememfile would catch such an error too
577 // TODO: theApp->QueueDebugLogLine(/*DLP_VERYHIGH,*/ false, _T("Failed to read RecoveryData for %s - Received datasize/amounts of hashs was invalid (2)"), m_pOwner->GetFileName() );
578 return false;
581 // TODO: DEBUG_ONLY( theApp->QueueDebugLogLine(/*DLP_VERYHIGH,*/ false, _T("read RecoveryData for %s - Received packet with %u 32bit hash identifiers)"), m_pOwner->GetFileName(), nHashsAvailable ) );
582 for (uint32 i = 0; i != nHashsToRead; i++) {
583 uint32 wHashIdent = fileDataIn->ReadUInt32();
584 if (wHashIdent == 1 /*never allow masterhash to be overwritten*/
585 || wHashIdent > 0x400000
586 || !m_pHashTree.SetHash(fileDataIn, wHashIdent,(-1), false))
588 // TODO: theApp->QueueDebugLogLine(/*DLP_VERYHIGH,*/ false, _T("Failed to read RecoveryData for %s - Error when trying to read hash into tree (2)"), m_pOwner->GetFileName() );
589 VerifyHashTree(true); // remove invalid hashs which we have already written
590 return false;
595 if (nHashsAvailable == 0) {
596 // TODO: theApp->QueueDebugLogLine(/*DLP_VERYHIGH,*/ false, _T("Failed to read RecoveryData for %s - Packet didn't contained any hashs"), m_pOwner->GetFileName() );
597 return false;
601 if (VerifyHashTree(true)) {
602 // some final check if all hashs we wanted are there
603 for (uint32 nPartPos = 0; nPartPos < nPartSize; nPartPos += EMBLOCKSIZE) {
604 CAICHHashTree* phtToCheck = m_pHashTree.FindHash(nPartStartPos+nPartPos, min<uint64>(EMBLOCKSIZE, nPartSize-nPartPos));
605 if (phtToCheck == NULL || !phtToCheck->m_bHashValid) {
606 AddDebugLogLineM( false, logSHAHashSet,
607 CFormat(wxT("Failed to read RecoveryData for '%s' - Error while verifying presence of all lowest level hashs"))
608 % m_pOwner->GetFileName());
609 return false;
612 // all done
613 return true;
614 } else {
615 AddDebugLogLineM(false, logSHAHashSet,
616 CFormat(wxT("Failed to read RecoveryData for '%s' - Verifying received hashtree failed"))
617 % m_pOwner->GetFileName());
618 return false;
622 // this function is only allowed to be called right after successfully calculating the hashset (!)
623 // will delete the hashset, after saving to free the memory
624 bool CAICHHashSet::SaveHashSet()
626 if (m_eStatus != AICH_HASHSETCOMPLETE) {
627 wxFAIL;
628 return false;
630 if ( !m_pHashTree.m_bHashValid || m_pHashTree.m_nDataSize != m_pOwner->GetFileSize()) {
631 wxFAIL;
632 return false;
636 try {
637 const wxString fullpath = theApp->ConfigDir + KNOWN2_MET_FILENAME;
638 const bool exists = wxFile::Exists(fullpath);
640 CFile file(fullpath, exists ? CFile::read_write : CFile::write);
641 if (!file.IsOpened()) {
642 AddDebugLogLineM( true, logSHAHashSet, wxT("Failed to save HashSet: opening met file failed!"));
643 return false;
646 uint64 nExistingSize = file.GetLength();
647 if (nExistingSize) {
648 uint8 header = file.ReadUInt8();
649 if (header != KNOWN2_MET_VERSION) {
650 AddDebugLogLineM( true, logSHAHashSet, wxT("Saving failed: Current file is not a met-file!"));
651 return false;
654 AddDebugLogLineM( false, logSHAHashSet, wxString::Format(wxT("Met file is version 0x%2.2x."),header));
655 } else {
656 file.WriteUInt8(KNOWN2_MET_VERSION);
657 // Update the recorded size, in order for the sanity check below to work.
658 nExistingSize += 1;
661 // first we check if the hashset we want to write is already stored
662 CAICHHash CurrentHash;
663 while (file.GetPosition() < nExistingSize) {
664 CurrentHash.Read(&file);
665 if (m_pHashTree.m_Hash == CurrentHash) {
666 // this hashset if already available, no need to save it again
667 return true;
669 uint32 nHashCount = file.ReadUInt32();
670 if (file.GetPosition() + nHashCount*HASHSIZE > nExistingSize) {
671 AddDebugLogLineM( true, logSHAHashSet, wxT("Saving failed: File contains fewer entries than specified!"));
672 return false;
674 // skip the rest of this hashset
675 file.Seek(nHashCount*HASHSIZE, wxFromCurrent);
678 // write hashset
679 m_pHashTree.m_Hash.Write(&file);
680 uint32 nHashCount = (PARTSIZE/EMBLOCKSIZE + ((PARTSIZE % EMBLOCKSIZE != 0)? 1 : 0)) * (m_pHashTree.m_nDataSize/PARTSIZE);
681 if (m_pHashTree.m_nDataSize % PARTSIZE != 0) {
682 nHashCount += (m_pHashTree.m_nDataSize % PARTSIZE)/EMBLOCKSIZE + (((m_pHashTree.m_nDataSize % PARTSIZE) % EMBLOCKSIZE != 0)? 1 : 0);
684 file.WriteUInt32(nHashCount);
685 if (!m_pHashTree.WriteLowestLevelHashs(&file, 0, true, true)) {
686 // thats bad... really
687 file.SetLength(nExistingSize);
688 AddDebugLogLineM( true, logSHAHashSet, wxT("Failed to save HashSet: WriteLowestLevelHashs() failed!"));
689 return false;
691 if (file.GetLength() != nExistingSize + (nHashCount+1)*HASHSIZE + 4) {
692 // thats even worse
693 file.SetLength(nExistingSize);
694 AddDebugLogLineM( true, logSHAHashSet, wxT("Failed to save HashSet: Calculated and real size of hashset differ!"));
695 return false;
697 AddDebugLogLineM( false, logSHAHashSet, wxString::Format(wxT("Sucessfully saved eMuleAC Hashset, %u Hashs + 1 Masterhash written"), nHashCount));
698 } catch (const CSafeIOException& e) {
699 AddDebugLogLineM(true, logSHAHashSet, wxT("IO error while saving AICH HashSet: ") + e.what());
700 return false;
703 FreeHashSet();
704 return true;
708 bool CAICHHashSet::LoadHashSet()
710 if (m_eStatus != AICH_HASHSETCOMPLETE) {
711 wxFAIL;
712 return false;
714 if ( !m_pHashTree.m_bHashValid || m_pHashTree.m_nDataSize != m_pOwner->GetFileSize() || m_pHashTree.m_nDataSize == 0) {
715 wxFAIL;
716 return false;
718 wxString fullpath = theApp->ConfigDir + KNOWN2_MET_FILENAME;
719 CFile file(fullpath, CFile::read);
720 if (!file.IsOpened()) {
721 if (wxFileExists(fullpath)) {
722 wxString strError(wxT("Failed to load ") KNOWN2_MET_FILENAME wxT(" file"));
723 AddDebugLogLineM( true, logSHAHashSet, strError);
725 return false;
728 try {
729 uint8 header = file.ReadUInt8();
730 if (header != KNOWN2_MET_VERSION) {
731 AddDebugLogLineM( true, logSHAHashSet, wxT("Loading failed: Current file is not a met-file!"));
732 return false;
735 CAICHHash CurrentHash;
736 uint64 nExistingSize = file.GetLength();
737 uint32 nHashCount;
738 while (file.GetPosition() < nExistingSize) {
739 CurrentHash.Read(&file);
740 if (m_pHashTree.m_Hash == CurrentHash) {
741 // found Hashset
742 uint32 nExpectedCount = (PARTSIZE/EMBLOCKSIZE + ((PARTSIZE % EMBLOCKSIZE != 0)? 1 : 0)) * (m_pHashTree.m_nDataSize/PARTSIZE);
743 if (m_pHashTree.m_nDataSize % PARTSIZE != 0) {
744 nExpectedCount += (m_pHashTree.m_nDataSize % PARTSIZE)/EMBLOCKSIZE + (((m_pHashTree.m_nDataSize % PARTSIZE) % EMBLOCKSIZE != 0)? 1 : 0);
746 nHashCount = file.ReadUInt32();
747 if (nHashCount != nExpectedCount) {
748 AddDebugLogLineM( true, logSHAHashSet, wxT("Failed to load HashSet: Available Hashs and expected hashcount differ!"));
749 return false;
751 if (!m_pHashTree.LoadLowestLevelHashs(&file)) {
752 AddDebugLogLineM( true, logSHAHashSet, wxT("Failed to load HashSet: LoadLowestLevelHashs failed!"));
753 return false;
755 if (!ReCalculateHash(false)) {
756 AddDebugLogLineM( true, logSHAHashSet, wxT("Failed to load HashSet: Calculating loaded hashs failed!"));
757 return false;
759 if (CurrentHash != m_pHashTree.m_Hash) {
760 AddDebugLogLineM( true, logSHAHashSet, wxT("Failed to load HashSet: Calculated Masterhash differs from given Masterhash - hashset corrupt!"));
761 return false;
763 return true;
765 nHashCount = file.ReadUInt32();
766 if (file.GetPosition() + nHashCount*HASHSIZE > nExistingSize) {
767 AddDebugLogLineM( true, logSHAHashSet, wxT("Saving failed: File contains fewer entries than specified!"));
768 return false;
770 // skip the rest of this hashset
771 file.Seek(nHashCount*HASHSIZE, wxFromCurrent);
773 AddDebugLogLineM( true, logSHAHashSet, wxT("Failed to load HashSet: HashSet not found!"));
774 } catch (const CSafeIOException& e) {
775 AddDebugLogLineM(true, logSHAHashSet, wxT("IO error while loading AICH HashSet: ") + e.what());
778 return false;
781 // delete the hashset except the masterhash (we dont keep aich hashsets in memory to save ressources)
782 void CAICHHashSet::FreeHashSet()
784 if (m_pHashTree.m_pLeftTree) {
785 delete m_pHashTree.m_pLeftTree;
786 m_pHashTree.m_pLeftTree = NULL;
788 if (m_pHashTree.m_pRightTree) {
789 delete m_pHashTree.m_pRightTree;
790 m_pHashTree.m_pRightTree = NULL;
794 void CAICHHashSet::SetMasterHash(const CAICHHash& Hash, EAICHStatus eNewStatus)
796 m_pHashTree.m_Hash = Hash;
797 m_pHashTree.m_bHashValid = true;
798 SetStatus(eNewStatus);
801 CAICHHashAlgo* CAICHHashSet::GetNewHashAlgo()
803 return new CSHA();
806 bool CAICHHashSet::ReCalculateHash(bool bDontReplace)
808 CAICHHashAlgo* hashalg = GetNewHashAlgo();
809 bool bResult = m_pHashTree.ReCalculateHash(hashalg, bDontReplace);
810 delete hashalg;
811 return bResult;
814 bool CAICHHashSet::VerifyHashTree(bool bDeleteBadTrees)
816 CAICHHashAlgo* hashalg = GetNewHashAlgo();
817 bool bResult = m_pHashTree.VerifyHashTree(hashalg, bDeleteBadTrees);
818 delete hashalg;
819 return bResult;
823 void CAICHHashSet::SetFileSize(uint64 nSize)
825 m_pHashTree.m_nDataSize = nSize;
826 m_pHashTree.m_nBaseSize = (nSize <= PARTSIZE) ? EMBLOCKSIZE : PARTSIZE;
830 void CAICHHashSet::UntrustedHashReceived(const CAICHHash& Hash, uint32 dwFromIP)
832 switch(GetStatus()) {
833 case AICH_EMPTY:
834 case AICH_UNTRUSTED:
835 case AICH_TRUSTED:
836 break;
837 default:
838 return;
840 bool bFound = false;
841 bool bAdded = false;
842 for (uint32 i = 0; i < m_aUntrustedHashs.size(); ++i) {
843 if (m_aUntrustedHashs[i].m_Hash == Hash) {
844 bAdded = m_aUntrustedHashs[i].AddSigningIP(dwFromIP);
845 bFound = true;
846 break;
849 if (!bFound) {
850 bAdded = true;
851 CAICHUntrustedHash uhToAdd;
852 uhToAdd.m_Hash = Hash;
853 uhToAdd.AddSigningIP(dwFromIP);
854 m_aUntrustedHashs.push_back(uhToAdd);
857 uint32 nSigningIPsTotal = 0; // unique clients who send us a hash
858 int nMostTrustedPos = (-1); // the hash which most clients send us
859 uint32 nMostTrustedIPs = 0;
860 for (uint32 i = 0; i < (uint32)m_aUntrustedHashs.size(); ++i) {
861 nSigningIPsTotal += m_aUntrustedHashs[i].m_adwIpsSigning.size();
862 if ((uint32)m_aUntrustedHashs[i].m_adwIpsSigning.size() > nMostTrustedIPs) {
863 nMostTrustedIPs = m_aUntrustedHashs[i].m_adwIpsSigning.size();
864 nMostTrustedPos = i;
867 if (nMostTrustedPos == (-1) || nSigningIPsTotal == 0) {
868 wxFAIL;
869 return;
871 // the check if we trust any hash
872 if ( thePrefs::IsTrustingEveryHash() ||
873 (nMostTrustedIPs >= MINUNIQUEIPS_TOTRUST && (100 * nMostTrustedIPs)/nSigningIPsTotal >= MINPERCENTAGE_TOTRUST)) {
874 //trusted
875 AddDebugLogLineM(false, logSHAHashSet,
876 CFormat(wxT("AICH Hash received (%sadded), We have now %u hash(es) from %u unique IP(s). ")
877 wxT("We trust the Hash %s from %u client(s) (%u%%). File: %s"))
878 % (bAdded ? wxT("") : wxT("not "))
879 % m_aUntrustedHashs.size()
880 % nSigningIPsTotal
881 % m_aUntrustedHashs[nMostTrustedPos].m_Hash.GetString()
882 % nMostTrustedIPs
883 % ((100 * nMostTrustedIPs) / nSigningIPsTotal)
884 % m_pOwner->GetFileName());
886 SetStatus(AICH_TRUSTED);
887 if (!HasValidMasterHash() || GetMasterHash() != m_aUntrustedHashs[nMostTrustedPos].m_Hash) {
888 SetMasterHash(m_aUntrustedHashs[nMostTrustedPos].m_Hash, AICH_TRUSTED);
889 FreeHashSet();
891 } else {
892 // untrusted
893 AddDebugLogLineM(false, logSHAHashSet,
894 CFormat(wxT("AICH Hash received (%sadded), We have now %u hash(es) from %u unique IP(s). ")
895 wxT("Best Hash %s from %u clients (%u%%) - but we dont trust it yet. File: %s"))
896 % (bAdded ? wxT(""): wxT("not "))
897 % m_aUntrustedHashs.size()
898 % nSigningIPsTotal
899 % m_aUntrustedHashs[nMostTrustedPos].m_Hash.GetString()
900 % nMostTrustedIPs
901 % ((100 * nMostTrustedIPs) / nSigningIPsTotal)
902 % m_pOwner->GetFileName());
904 SetStatus(AICH_UNTRUSTED);
905 if (!HasValidMasterHash() || GetMasterHash() != m_aUntrustedHashs[nMostTrustedPos].m_Hash) {
906 SetMasterHash(m_aUntrustedHashs[nMostTrustedPos].m_Hash, AICH_UNTRUSTED);
907 FreeHashSet();
912 #ifndef CLIENT_GUI
914 void CAICHHashSet::ClientAICHRequestFailed(CUpDownClient* pClient)
916 pClient->SetReqFileAICHHash(NULL);
917 CAICHRequestedData data = GetAICHReqDetails(pClient);
918 RemoveClientAICHRequest(pClient);
919 if (data.m_pClient != pClient) {
920 return;
922 if( theApp->downloadqueue->IsPartFile(data.m_pPartFile)) {
923 AddDebugLogLineM(false, logSHAHashSet,
924 CFormat(wxT("AICH Request failed, Trying to ask another client (File: '%s', Part: %u, Client '%s'"))
925 % data.m_pPartFile->GetFileName() % data.m_nPart % pClient->GetClientFullInfo());
926 data.m_pPartFile->RequestAICHRecovery(data.m_nPart);
930 #endif
932 void CAICHHashSet::RemoveClientAICHRequest(const CUpDownClient* pClient)
934 for (CAICHRequestedDataList::iterator it = m_liRequestedData.begin();it != m_liRequestedData.end(); ++it) {
935 if (it->m_pClient == pClient) {
936 m_liRequestedData.erase(it);
937 return;
940 wxFAIL;
943 bool CAICHHashSet::IsClientRequestPending(const CPartFile* pForFile, uint16 nPart)
945 for (CAICHRequestedDataList::iterator it = m_liRequestedData.begin();it != m_liRequestedData.end(); ++it) {
946 if (it->m_pPartFile == pForFile && it->m_nPart == nPart) {
947 return true;
950 return false;
953 CAICHRequestedData CAICHHashSet::GetAICHReqDetails(const CUpDownClient* pClient)
955 for (CAICHRequestedDataList::iterator it = m_liRequestedData.begin();it != m_liRequestedData.end(); ++it) {
956 if (it->m_pClient == pClient) {
957 return *(it);
960 wxFAIL;
961 CAICHRequestedData empty;
962 return empty;
965 bool CAICHHashSet::IsPartDataAvailable(uint64 nPartStartPos)
967 if (!(m_eStatus == AICH_VERIFIED || m_eStatus == AICH_TRUSTED || m_eStatus == AICH_HASHSETCOMPLETE) ) {
968 wxFAIL;
969 return false;
971 uint64 nPartSize = min<uint64>(PARTSIZE, m_pOwner->GetFileSize()-nPartStartPos);
972 for (uint64 nPartPos = 0; nPartPos < nPartSize; nPartPos += EMBLOCKSIZE) {
973 CAICHHashTree* phtToCheck = m_pHashTree.FindHash(nPartStartPos+nPartPos, min<uint64>(EMBLOCKSIZE, nPartSize-nPartPos));
974 if (phtToCheck == NULL || !phtToCheck->m_bHashValid) {
975 return false;
978 return true;
981 // VC++ defines Assert as ASSERT. VC++ also defines VERIFY MACRO, which is the equivalent of ASSERT but also works in Released builds.
983 #define VERIFY(x) wxASSERT(x)
985 void CAICHHashSet::DbgTest()
987 #ifdef _DEBUG
988 //define TESTSIZE 4294567295
989 uint8 maxLevel = 0;
990 uint32 cHash = 1;
991 uint8 curLevel = 0;
992 //uint32 cParts = 0;
993 maxLevel = 0;
994 /* CAICHHashTree* pTest = new CAICHHashTree(TESTSIZE, true, 9728000);
995 for (uint64 i = 0; i+9728000 < TESTSIZE; i += 9728000) {
996 CAICHHashTree* pTest2 = new CAICHHashTree(9728000, true, EMBLOCKSIZE);
997 pTest->ReplaceHashTree(i, 9728000, &pTest2);
998 cParts++;
1000 CAICHHashTree* pTest2 = new CAICHHashTree(TESTSIZE-i, true, EMBLOCKSIZE);
1001 pTest->ReplaceHashTree(i, (TESTSIZE-i), &pTest2);
1002 cParts++;
1004 #define TESTSIZE m_pHashTree.m_nDataSize
1005 if (m_pHashTree.m_nDataSize <= EMBLOCKSIZE) {
1006 return;
1008 CAICHHashSet TestHashSet(m_pOwner);
1009 TestHashSet.SetFileSize(m_pOwner->GetFileSize());
1010 TestHashSet.SetMasterHash(GetMasterHash(), AICH_VERIFIED);
1011 CMemFile file;
1012 uint64 i;
1013 for (i = 0; i+9728000 < TESTSIZE; i += 9728000) {
1014 VERIFY( CreatePartRecoveryData(i, &file) );
1016 /*uint32 nRandomCorruption = (rand() * rand()) % (file.GetLength()-4);
1017 file.Seek(nRandomCorruption, CFile::begin);
1018 file.Write(&nRandomCorruption, 4);*/
1020 file.Seek(0,wxFromStart);
1021 VERIFY( TestHashSet.ReadRecoveryData(i, &file) );
1022 file.Seek(0,wxFromStart);
1023 TestHashSet.FreeHashSet();
1024 uint32 j;
1025 for (j = 0; j+EMBLOCKSIZE < 9728000; j += EMBLOCKSIZE) {
1026 VERIFY( m_pHashTree.FindHash(i+j, EMBLOCKSIZE, &curLevel) );
1027 //TRACE(wxT("%u - %s\r\n"), cHash, m_pHashTree.FindHash(i+j, EMBLOCKSIZE, &curLevel)->m_Hash.GetString());
1028 maxLevel = max(curLevel, maxLevel);
1029 curLevel = 0;
1030 cHash++;
1032 VERIFY( m_pHashTree.FindHash(i+j, 9728000-j, &curLevel) );
1033 //TRACE(wxT("%u - %s\r\n"), cHash, m_pHashTree.FindHash(i+j, 9728000-j, &curLevel)->m_Hash.GetString());
1034 maxLevel = max(curLevel, maxLevel);
1035 curLevel = 0;
1036 cHash++;
1039 VERIFY( CreatePartRecoveryData(i, &file) );
1040 file.Seek(0,wxFromStart);
1041 VERIFY( TestHashSet.ReadRecoveryData(i, &file) );
1042 file.Seek(0,wxFromStart);
1043 TestHashSet.FreeHashSet();
1044 for (uint64 j = 0; j+EMBLOCKSIZE < TESTSIZE-i; j += EMBLOCKSIZE) {
1045 VERIFY( m_pHashTree.FindHash(i+j, EMBLOCKSIZE, &curLevel) );
1046 //TRACE(wxT("%u - %s\r\n"), cHash,m_pHashTree.FindHash(i+j, EMBLOCKSIZE, &curLevel)->m_Hash.GetString());
1047 maxLevel = max(curLevel, maxLevel);
1048 curLevel = 0;
1049 cHash++;
1051 //VERIFY( m_pHashTree.FindHash(i+j, (TESTSIZE-i)-j, &curLevel) );
1052 //TRACE(wxT("%u - %s\r\n"), cHash,m_pHashTree.FindHash(i+j, (TESTSIZE-i)-j, &curLevel)->m_Hash.GetString());
1053 maxLevel = max(curLevel, maxLevel);
1054 #endif
1056 // File_checked_for_headers