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
38Example 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 /     \         /     \          \
47X(4,75) X(4,57) X(4,57) X(4,57)    X(4,75)
48[...............]
49X(180KB)   X(180KB)  [...] X(140KB) | X(180KB) X(180KB) [...]	BlockHashs
50                                    v
51                                    Border between first and second Part (9.28MB)
52
53HashsIdentifier:
54When sending hashes, they are sent with a 16bit identifier which specifies its position in the
55tree (so StartPosition + HashDataSize would lead to the same hash)
56The identifier basically describes the way from the top of the tree to the hash. a set bit (1)
57means follow the left branch, a 0 means follow the right. The highest bit which is set is seen as the start-
58position (since the first node is always seen as left).
59
60Example
61
62    x                   0000000000000001
63   / \
64  x   \			0000000000000011
65 / \   \
66x  _X_  x 	        0000000000000110
67
68
69Version 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
86enum EAICHStatus {
87	AICH_ERROR = 0,
88	AICH_EMPTY,
89	AICH_UNTRUSTED,
90	AICH_TRUSTED,
91	AICH_VERIFIED,
92	AICH_HASHSETCOMPLETE
93};
94
95class CFileDataIO;
96class CKnownFile;
97class CMemFile;
98class CPartFile;
99class CUpDownClient;
100
101
102/////////////////////////////////////////////////////////////////////////////////////////
103///CAICHHash
104class CAICHHash
105{
106private:
107	byte m_abyBuffer[HASHSIZE];
108
109public:
110	CAICHHash() 				{ memset(m_abyBuffer, 0, HASHSIZE); }
111	CAICHHash(CFileDataIO* file)		{ Read(file); }
112	CAICHHash(byte* 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(byte* data)			{ memcpy(m_abyBuffer, data, HASHSIZE); }
128	wxString GetString() const;
129	byte* GetRawHash()			{ return m_abyBuffer; }
130	static uint32 GetHashSize()		{ return HASHSIZE;}
131	unsigned int DecodeBase32(const wxString &base32);
132};
133
134/////////////////////////////////////////////////////////////////////////////////////////
135///CAICHHashAlgo
136class CAICHHashAlgo
137{
138public:
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
148class CAICHHashTree
149{
150	friend class CAICHHashSet;
151private:
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
160public:
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
179protected:
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
192class CAICHUntrustedHash {
193public:
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
208class CAICHRequestedData {
209public:
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
228using namespace std;
229
230typedef std::list<CAICHRequestedData> CAICHRequestedDataList;
231
232/////////////////////////////////////////////////////////////////////////////////////////
233///CAICHHashSet
234class CAICHHashSet
235{
236private:
237	CKnownFile* m_pOwner;
238	EAICHStatus m_eStatus;
239	deque<CAICHUntrustedHash> m_aUntrustedHashs;
240
241public:
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
279