tigertree.cpp

p2p软件

//
// TigerTree.cpp
//
// Copyright (c) Shareaza Development Team, 2002-2004.
// This file is part of SHAREAZA (www.shareaza.com)
//
// Shareaza 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.
//
// Shareaza 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 Shareaza; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//

#include "StdAfx.h"
#include "Shareaza.h"
#include "TigerTree.h"
#include "TigerBoxes.h"

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

#define BLOCK_SIZE		1024
#define STACK_SIZE		64
#define TIGER_SIZE		24

#define NEW_TIGER_ALG	// New "more secure" padded node combination


//////////////////////////////////////////////////////////////////////
// CTigerTree construction

CTigerTree::CTigerTree()
{
	m_nHeight		= 0;
	m_pNode			= NULL;
	m_nNodeCount	= 0;

	m_pStackBase	= NULL;
	m_pStackTop		= NULL;
}

CTigerTree::~CTigerTree()
{
	Clear();

	if ( m_pStackBase != NULL ) delete [] m_pStackBase;
}

//////////////////////////////////////////////////////////////////////
// CTigerTree setup tree

void CTigerTree::SetupAndAllocate(DWORD nHeight, QWORD nLength)
{
	Clear();
	
	QWORD nCount = (DWORD)( nLength / BLOCK_SIZE );
	if ( nLength % BLOCK_SIZE ) nCount++;
	
	DWORD nActualHeight = 1;
	
	for ( DWORD nStep = 1 ; nStep < nCount ; nStep *= 2 ) nActualHeight++;
	
	m_nHeight = min( nActualHeight, nHeight );
	
	m_nBlockCount	= 1;
	m_nBlockPos		= 0;
	
	if ( nActualHeight > nHeight )
	{
		for ( nStep = nActualHeight - nHeight ; nStep ; nStep-- ) m_nBlockCount *= 2;
	}
	
	m_nNodeCount = 1;
	
	for ( nStep = m_nHeight ; nStep ; nStep-- ) m_nNodeCount *= 2;
	
	m_nNodeBase	= ( m_nNodeCount / 2 );
	m_nBaseUsed	= (DWORD)( nCount / m_nBlockCount );
	if ( nCount % m_nBlockCount ) m_nBaseUsed++;
	
	m_pNode		= new CTigerNode[ --m_nNodeCount ];
	m_nNodePos	= 0;
}

void CTigerTree::SetupParameters(QWORD nLength)
{
	QWORD nCount = nLength / BLOCK_SIZE;
	if ( nLength % BLOCK_SIZE ) nCount++;
	
	DWORD nActualHeight = 1;
	for ( DWORD nStep = 1 ; nStep < nCount ; nStep *= 2 ) nActualHeight++;
	
	m_nBlockCount	= 1;
	m_nBlockPos		= 0;
	
	if ( nActualHeight > m_nHeight )
	{
		for ( nStep = nActualHeight - m_nHeight ; nStep ; nStep-- ) m_nBlockCount *= 2;
	}
	
	m_nNodeCount = 1;
	for ( nStep = m_nHeight ; nStep ; nStep-- ) m_nNodeCount *= 2;
	
	m_nNodeBase = ( m_nNodeCount-- / 2 );
	
	m_nBaseUsed	= (DWORD)( nCount / m_nBlockCount );
	if ( nCount % m_nBlockCount ) m_nBaseUsed++;
}

//////////////////////////////////////////////////////////////////////
// CTigerTree clear

void CTigerTree::Clear()
{
	if ( m_pNode != NULL ) delete [] m_pNode;
	
	m_nHeight		= 0;
	m_pNode			= NULL;
	m_nNodeCount	= 0;
}

//////////////////////////////////////////////////////////////////////
// CTigerTree serialize

void CTigerTree::Serialize(CArchive& ar)
{
	CTigerNode* pNode;
	DWORD nStep;
	
	if ( ar.IsStoring() )
	{
		ar << m_nHeight;
		
		if ( m_nHeight == 0 ) return;
		ASSERT( m_pNode != NULL );
		
		pNode = m_pNode;
		
		for ( nStep = m_nNodeCount ; nStep ; nStep--, pNode++ )
		{
			ar.Write( pNode->value, TIGER_SIZE );
			ar << pNode->bValid;
		}
	}
	else
	{
		Clear();
		
		ar >> m_nHeight;
		if ( m_nHeight == 0 ) return;
		
		m_nNodeCount = 1;
		for ( nStep = m_nHeight ; nStep ; nStep-- ) m_nNodeCount *= 2;
		m_nNodeCount --;
		
		m_pNode = pNode = new CTigerNode[ m_nNodeCount ];
		
		for ( nStep = m_nNodeCount ; nStep ; nStep--, pNode++ )
		{
			ar.Read( pNode->value, TIGER_SIZE );
			ar >> pNode->bValid;
		}
	}
}

DWORD CTigerTree::GetSerialSize() const
{
	return 4 + m_nNodeCount * ( TIGER_SIZE + 1 );
}

//////////////////////////////////////////////////////////////////////
// CTigerTree root output

BOOL CTigerTree::GetRoot(TIGEROOT* pTiger) const
{
	if ( m_pNode == NULL ) return FALSE;
	ASSERT( sizeof(TIGEROOT) == TIGER_SIZE );
	CopyMemory( pTiger, &m_pNode->value, TIGER_SIZE );
	return TRUE;
}

//////////////////////////////////////////////////////////////////////
// CTigerTree string output

CString CTigerTree::RootToString() const
{
	CString str;
	if ( m_pNode != NULL ) str = m_pNode->ToString();
	return str;
}

//////////////////////////////////////////////////////////////////////
// CTigerTree assume

void CTigerTree::Assume(CTigerTree* pSource)
{
	Clear();
	if ( pSource->m_pNode == NULL ) return;

	m_nHeight		= pSource->m_nHeight;
	m_nNodeCount	= pSource->m_nNodeCount;
	m_pNode			= pSource->m_pNode;

	pSource->m_nHeight		= 0;
	pSource->m_nNodeCount	= 0;
	pSource->m_pNode		= NULL;
}

//////////////////////////////////////////////////////////////////////
// CTigerTree create from file

void CTigerTree::BeginFile(DWORD nHeight, QWORD nLength)
{
	ASSERT( ! IsAvailable() );
	
	SetupAndAllocate( nHeight, nLength );
	
	if ( m_pStackBase == NULL ) m_pStackBase = new CTigerNode[ STACK_SIZE ];
	m_pStackTop	= m_pStackBase;
	m_nBlockPos = 0;
}

//////////////////////////////////////////////////////////////////////
// CTigerTree add data to the file

void CTigerTree::AddToFile(LPCVOID pInput, DWORD nLength)
{
	ASSERT( m_pNode != NULL );
	
	LPBYTE pBlock = (LPBYTE)pInput;
	
	while ( nLength > 0 )
	{
		DWORD nBlock = min( nLength, BLOCK_SIZE );
		
		Tiger( pBlock, (WORD64)nBlock, m_pStackTop->value );
		m_pStackTop ++;

		DWORD nCollapse = ++m_nBlockPos;

		while ( ! ( nCollapse & 1 ) )
		{
			Collapse();
			nCollapse >>= 1;
		}

		if ( m_nBlockPos >= m_nBlockCount )
		{
			BlocksToNode();
		}

		pBlock += nBlock;
		nLength -= nBlock;
	}
}

//////////////////////////////////////////////////////////////////////
// CTigerTree finish file

BOOL CTigerTree::FinishFile()
{
	if ( m_pStackTop == NULL ) return FALSE;
	
	BlocksToNode();
	
	if ( m_nNodePos > m_nNodeBase ) return FALSE;
	
	if ( m_pStackBase != NULL ) delete [] m_pStackBase;
	
	m_pStackBase	= NULL;
	m_pStackTop		= NULL;
	
	CTigerNode* pBase = m_pNode + m_nNodeCount - m_nNodeBase;
	
	for ( DWORD nCombine = m_nNodeBase ; nCombine > 1 ; nCombine /= 2 )
	{
		CTigerNode* pIn		= pBase;
		CTigerNode* pOut	= pBase - nCombine / 2;
		
		for ( DWORD nIterate = nCombine / 2 ; nIterate ; nIterate--, pIn += 2, pOut++ )
		{
			if ( pIn[0].bValid && pIn[1].bValid )
			{
				Tiger( NULL, TIGER_SIZE * 2, pOut->value, pIn[0].value, pIn[1].value );
				pOut->bValid = TRUE;
			}
			else if ( pIn[0].bValid )
			{
				*pOut = *pIn;
			}
		}
		
		pBase -= nCombine / 2;
	}
	
	return TRUE;
}

//////////////////////////////////////////////////////////////////////
// CTigerTree begin a block test

void CTigerTree::BeginBlockTest()
{
	ASSERT( m_pNode != NULL );
	
	if ( m_pStackBase == NULL ) m_pStackBase = new CTigerNode[ STACK_SIZE ];
	m_pStackTop	= m_pStackBase;
	m_nBlockPos = 0;
}

//////////////////////////////////////////////////////////////////////
// CTigerTree add data to a block test

void CTigerTree::AddToTest(LPCVOID pInput, DWORD nLength)
{
	ASSERT( m_pNode != NULL );
	
	LPBYTE pBlock = (LPBYTE)pInput;
	
	while ( nLength > 0 )
	{
		DWORD nBlock = min( nLength, BLOCK_SIZE );
		
		Tiger( pBlock, (WORD64)nBlock, m_pStackTop->value );
		m_pStackTop ++;
		
		ASSERT( m_nBlockPos < m_nBlockCount );
		
		DWORD nCollapse = ++m_nBlockPos;
		
		while ( ! ( nCollapse & 1 ) )
		{
			Collapse();
			nCollapse >>= 1;
		}
		
		pBlock += nBlock;
		nLength -= nBlock;
	}
}

//////////////////////////////////////////////////////////////////////
// CTigerTree block test finish and compare

BOOL CTigerTree::FinishBlockTest(DWORD nBlock)
{
	ASSERT( nBlock < m_nBaseUsed );
	if ( nBlock >= m_nBaseUsed ) return FALSE;
	
	while ( m_pStackTop - 1 > m_pStackBase ) Collapse();
	
	CTigerNode* pNode = m_pNode + m_nNodeCount - m_nNodeBase + nBlock;
	
	if ( pNode->v1 != m_pStackBase->v1 ) return FALSE;
	if ( pNode->v2 != m_pStackBase->v2 ) return FALSE;
	if ( pNode->v3 != m_pStackBase->v3 ) return FALSE;
	
	return TRUE;
}

//////////////////////////////////////////////////////////////////////
// CTigerTree breadth-first serialize

BOOL CTigerTree::ToBytes(BYTE** pOutput, DWORD* pnOutput, DWORD nHeight)
{
	if ( m_pNode == NULL ) return FALSE;
	
	if ( nHeight < 1 || nHeight > m_nHeight ) nHeight = m_nHeight;
	
	DWORD nNodeCount = 1;
	while ( nHeight-- ) nNodeCount *= 2;
	nNodeCount --;
	
	nNodeCount	= min( nNodeCount, m_nNodeCount );
	*pnOutput	= nNodeCount * TIGER_SIZE;
	*pOutput	= new BYTE[ *pnOutput ];
	
	CTigerNode* pNode = m_pNode;
	BYTE* pOut = *pOutput;
	
	for ( DWORD nNode = 0 ; nNode < nNodeCount ; nNode++, pNode++ )
	{
		if ( pNode->bValid )
		{
			CopyMemory( pOut, pNode->value, TIGER_SIZE );
			pOut += TIGER_SIZE;
		}
		else
		{
			*pnOutput -= TIGER_SIZE;
		}
	}
	
	return TRUE;
}

//////////////////////////////////////////////////////////////////////
// CTigerTree breadth-first serialize

BOOL CTigerTree::FromBytes(BYTE* pInput, DWORD nInput, DWORD nHeight, QWORD nLength)
{
	SetupAndAllocate( nHeight, nLength );
	
	CTigerNode* pBase = m_pNode + m_nNodeCount - m_nNodeBase;
	
	for ( DWORD nStep = m_nBaseUsed ; nStep ; nStep-- )
	{
		pBase[ nStep - 1 ].bValid = TRUE;
	}
	
	for ( DWORD nCombine = m_nNodeBase ; nCombine > 1 ; nCombine /= 2 )
	{
		CTigerNode* pIn		= pBase;
		CTigerNode* pOut	= pBase - nCombine / 2;
		
		for ( DWORD nIterate = nCombine / 2 ; nIterate ; nIterate--, pIn += 2, pOut++ )
		{
			if ( pIn[0].bValid ) pOut->bValid = TRUE;
		}
		
		pBase -= nCombine / 2;
	}
	
	TIGEROOT* pTiger = (TIGEROOT*)pInput;
	nInput /= TIGER_SIZE;
	
	DWORD nRowPos = 0, nRowCount = 1;
	m_nHeight = 0;
	
	for ( nStep = 0 ; nStep < m_nNodeCount && nInput > 0 ; nStep++ )
	{
		if ( m_pNode[ nStep ].bValid )
		{
			CopyMemory( m_pNode[ nStep ].value, pTiger->w, TIGER_SIZE );
			pTiger ++; nInput --;
		}

		if ( nRowPos == 0 ) m_nHeight ++;

		if ( ++nRowPos == nRowCount )
		{