shahashset.cpp

VeryCD版的电驴源程序

//this file is part of eMule
//Copyright (C)2002-2004 Merkur ( [e-mail] / http://www.emule-project.net )
//
//This program is free software; you can redistribute it and/or
//modify it under the terms of the GNU General Public License
//as published by the Free Software Foundation; either
//version 2 of the License, or (at your option) any later version.
//
//This program is distributed in the hope that it will be useful,
//but WITHOUT ANY WARRANTY; without even the implied warranty of
//MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	See the
//GNU General Public License for more details.
//
//You should have received a copy of the GNU General Public License
//along with this program; if not, write to the Free Software
//Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

#include "StdAfx.h"
#include "shahashset.h"
#include "opcodes.h"
#include "otherfunctions.h"
#include "emule.h"
#include "safefile.h"
#include "knownfile.h"
#include "preferences.h"
#include "sha.h"
#include "updownclient.h"
#include "DownloadQueue.h"
#include "partfile.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

// for this version the limits are set very high, they might be lowered later
// to make a hash trustworthy, at least 10 unique Ips (255.255.128.0) must have send it
// and if we have received more than one hash  for the file, one hash has to be send by more than 95% of all unique IPs
#define MINUNIQUEIPS_TOTRUST		10	// how many unique IPs most have send us a hash to make it trustworthy
#define	MINPERCENTAGE_TOTRUST		92  // how many percentage of clients most have sent the same hash to make it trustworthy

CList<CAICHRequestedData, CAICHRequestedData&> CAICHHashSet::m_liRequestedData;

/////////////////////////////////////////////////////////////////////////////////////////
///CAICHHash
CString CAICHHash::GetString() const{
	return EncodeBase32(m_abyBuffer, HASHSIZE);
}

void CAICHHash::Read(CFileDataIO* file)	{ 
	file->Read(m_abyBuffer,HASHSIZE);
}

void CAICHHash::Write(CFileDataIO* file) const{ 
	file->Write(m_abyBuffer,HASHSIZE);
}
/////////////////////////////////////////////////////////////////////////////////////////
///CAICHHashTree

CAICHHashTree::CAICHHashTree(uint32 nDataSize, bool bLeftBranch, uint32 nBaseSize){
	m_nDataSize = nDataSize;
	m_nBaseSize = nBaseSize;
	m_bIsLeftBranch = bLeftBranch;
	m_pLeftTree = NULL;
	m_pRightTree = NULL;
	m_bHashValid = false;
}

CAICHHashTree::~CAICHHashTree(){
	if (m_pLeftTree)
		delete m_pLeftTree;
	if (m_pRightTree)
		delete m_pRightTree;
}

// recursive
CAICHHashTree* CAICHHashTree::FindHash(uint32 nStartPos, uint32 nSize, uint8* nLevel){
	(*nLevel)++;
	if (*nLevel > 16){ // sanity
		ASSERT( false );
		return false;
	}
	if (nStartPos + nSize > m_nDataSize){ // sanity
		ASSERT ( false );
		return NULL;
	}
	if (nSize > m_nDataSize){ // sanity
		ASSERT ( false );
		return NULL;
	}

	if (nStartPos == 0 && nSize == m_nDataSize){
		// this is the searched hash
		return this;
	}
	else if (m_nDataSize <= m_nBaseSize){ // sanity
		// this is already the last level, cant go deeper
		ASSERT( false );
		return NULL;
	}
	else{
		uint32 nBlocks = m_nDataSize / m_nBaseSize + ((m_nDataSize % m_nBaseSize != 0 )? 1:0); 
		uint32 nLeft = ( ((m_bIsLeftBranch) ? nBlocks+1:nBlocks) / 2)* m_nBaseSize;
		uint32 nRight = m_nDataSize - nLeft;
		if (nStartPos < nLeft){
			if (nStartPos + nSize > nLeft){ // sanity
				ASSERT ( false );
				return NULL;
			}
			if (m_pLeftTree == NULL)
				m_pLeftTree = new CAICHHashTree(nLeft, true, (nLeft <= PARTSIZE) ? EMBLOCKSIZE : PARTSIZE);
			else{
				ASSERT( m_pLeftTree->m_nDataSize == nLeft );
			}
			return m_pLeftTree->FindHash(nStartPos, nSize, nLevel);
		}
		else{
			nStartPos -= nLeft;
			if (nStartPos + nSize > nRight){ // sanity
				ASSERT ( false );
				return NULL;
			}
			if (m_pRightTree == NULL)
				m_pRightTree = new CAICHHashTree(nRight, false, (nRight <= PARTSIZE) ? EMBLOCKSIZE : PARTSIZE);
			else{
				ASSERT( m_pRightTree->m_nDataSize == nRight ); 
			}
			return m_pRightTree->FindHash(nStartPos, nSize, nLevel);
		}
	}
}

// recursive
// calculates missing hash fromt he existing ones
// overwrites existing hashs
// fails if no hash is found for any branch
bool CAICHHashTree::ReCalculateHash(CAICHHashAlgo* hashalg, bool bDontReplace){
	ASSERT ( !( (m_pLeftTree != NULL) ^ (m_pRightTree != NULL)) ); 
	if (m_pLeftTree && m_pRightTree){
		if ( !m_pLeftTree->ReCalculateHash(hashalg, bDontReplace) || !m_pRightTree->ReCalculateHash(hashalg, bDontReplace) )
			return false;
		if (bDontReplace && m_bHashValid)
			return true;
		if (m_pRightTree->m_bHashValid && m_pLeftTree->m_bHashValid){
			hashalg->Reset();
			hashalg->Add(m_pLeftTree->m_Hash.GetRawHash(), HASHSIZE);
			hashalg->Add(m_pRightTree->m_Hash.GetRawHash(), HASHSIZE);
			hashalg->Finish(m_Hash);
			m_bHashValid = true;
			return true;
		}
		else
			return m_bHashValid;
	}
	else
		return true;
}

bool CAICHHashTree::VerifyHashTree(CAICHHashAlgo* hashalg, bool bDeleteBadTrees){
	if (!m_bHashValid){
		ASSERT ( false );
		if (bDeleteBadTrees){
			if (m_pLeftTree){
				delete m_pLeftTree;
				m_pLeftTree = NULL;
			}
			if (m_pRightTree){
				delete m_pRightTree;
				m_pRightTree = NULL;
			}
		}
		theApp.QueueDebugLogLine(/*DLP_HIGH,*/ false, _T("VerifyHashTree - No masterhash available"));
		return false;
	}
	
		// calculated missing hashs without overwriting anything
		if (m_pLeftTree && !m_pLeftTree->m_bHashValid)
			m_pLeftTree->ReCalculateHash(hashalg, true);
		if (m_pRightTree && !m_pRightTree->m_bHashValid)
			m_pRightTree->ReCalculateHash(hashalg, true);
		
		if ((m_pRightTree && m_pRightTree->m_bHashValid) ^ (m_pLeftTree && m_pLeftTree->m_bHashValid)){
			// one branch can never be verified
			if (bDeleteBadTrees){
				if (m_pLeftTree){
					delete m_pLeftTree;
					m_pLeftTree = NULL;
				}
				if (m_pRightTree){
					delete m_pRightTree;
					m_pRightTree = NULL;
				}
			}
			theApp.QueueDebugLogLine(/*DLP_HIGH,*/ false, _T("VerifyHashSet failed - Hashtree incomplete"));
			return false;
		}
	if ((m_pRightTree && m_pRightTree->m_bHashValid) && (m_pLeftTree && m_pLeftTree->m_bHashValid)){			
	    // check verify the hashs of both child nodes against my hash 
	
		CAICHHash CmpHash;
		hashalg->Reset();
		hashalg->Add(m_pLeftTree->m_Hash.GetRawHash(), HASHSIZE);
		hashalg->Add(m_pRightTree->m_Hash.GetRawHash(), HASHSIZE);
		hashalg->Finish(CmpHash);
		
		if (m_Hash != CmpHash){
			if (bDeleteBadTrees){
				if (m_pLeftTree){
					delete m_pLeftTree;
					m_pLeftTree = NULL;
				}
				if (m_pRightTree){
					delete m_pRightTree;
					m_pRightTree = NULL;
				}
			}
			return false;
		}
		return m_pLeftTree->VerifyHashTree(hashalg, bDeleteBadTrees) && m_pRightTree->VerifyHashTree(hashalg, bDeleteBadTrees);
	}
	else
		// last hash in branch - nothing below to verify
		return true;

}

void CAICHHashTree::SetBlockHash(uint32 nSize, uint32 nStartPos, CAICHHashAlgo* pHashAlg){
	ASSERT ( nSize <= EMBLOCKSIZE );
	CAICHHashTree* pToInsert = FindHash(nStartPos, nSize);
	if (pToInsert == NULL){ // sanity
		ASSERT ( false );
		theApp.QueueDebugLogLine(/*DLP_VERYHIGH,*/ false, _T("Critical Error: Failed to Insert SHA-HashBlock, FindHash() failed!"));
		return;
	}
	
	//sanity
	if (pToInsert->m_nBaseSize != EMBLOCKSIZE || pToInsert->m_nDataSize != nSize){
		ASSERT ( false );
		theApp.QueueDebugLogLine(/*DLP_VERYHIGH,*/ false, _T("Critical Error: Logical error on values in SetBlockHashFromData"));
		return;
	}

	pHashAlg->Finish(pToInsert->m_Hash);
	pToInsert->m_bHashValid = true;
	//DEBUG_ONLY(theApp.QueueDebugLogLine(/*DLP_VERYLOW,*/ false, _T("Set ShaHash for block %u - %u (%u Bytes) to %s"), nStartPos, nStartPos + nSize, nSize, pToInsert->m_Hash.GetString()) );
	
}

bool CAICHHashTree::CreatePartRecoveryData(uint32 nStartPos, uint32 nSize, CFileDataIO* fileDataOut, uint16 wHashIdent){
	if (nStartPos + nSize > m_nDataSize){ // sanity
		ASSERT ( false );
		return false;
	}
	if (nSize > m_nDataSize){ // sanity
		ASSERT ( false );
		return false;
	}

	if (nStartPos == 0 && nSize == m_nDataSize){
		// this is the searched part, now write all blocks of this part
		// hashident for this level will be adjsuted by WriteLowestLevelHash
		return WriteLowestLevelHashs(fileDataOut, wHashIdent);
	}
	else if (m_nDataSize <= m_nBaseSize){ // sanity
		// this is already the last level, cant go deeper
		ASSERT( false );
		return false;
	}
	else{
		wHashIdent <<= 1;
		wHashIdent |= (m_bIsLeftBranch) ? 1: 0;
		
		uint32 nBlocks = m_nDataSize / m_nBaseSize + ((m_nDataSize % m_nBaseSize != 0 )? 1:0); 
		uint32 nLeft = ( ((m_bIsLeftBranch) ? nBlocks+1:nBlocks) / 2)* m_nBaseSize;
		uint32 nRight = m_nDataSize - nLeft;
		if (m_pLeftTree == NULL || m_pRightTree == NULL){
			ASSERT( false );
			return false;
		}
		if (nStartPos < nLeft){
			if (nStartPos + nSize > nLeft || !m_pRightTree->m_bHashValid){ // sanity
				ASSERT ( false );
				return false;
			}
			m_pRightTree->WriteHash(fileDataOut, wHashIdent);
			return m_pLeftTree->CreatePartRecoveryData(nStartPos, nSize, fileDataOut, wHashIdent);
		}
		else{
			nStartPos -= nLeft;
			if (nStartPos + nSize > nRight || !m_pLeftTree->m_bHashValid){ // sanity
				ASSERT ( false );
				return false;
			}
			m_pLeftTree->WriteHash(fileDataOut, wHashIdent);
			return m_pRightTree->CreatePartRecoveryData(nStartPos, nSize, fileDataOut, wHashIdent);

		}
	}
}

void CAICHHashTree::WriteHash(CFileDataIO* fileDataOut, uint16 wHashIdent) const{
	ASSERT( m_bHashValid );
	wHashIdent <<= 1;
	wHashIdent |= (m_bIsLeftBranch) ? 1: 0;
	fileDataOut->WriteUInt16(wHashIdent);
	m_Hash.Write(fileDataOut);
}

// write lowest level hashs into file, ordered from left to right optional without identifier
bool CAICHHashTree::WriteLowestLevelHashs(CFileDataIO* fileDataOut, uint16 wHashIdent, bool bNoIdent) const{
	wHashIdent <<= 1;
	wHashIdent |= (m_bIsLeftBranch) ? 1: 0;
	if (m_pLeftTree == NULL && m_pRightTree == NULL){