/*
	InsertionSort.cpp

*/

#include "stdafx.h"
#include "InsertionSort.h"
#include <emmintrin.h>

#pragma optimize( "t", on )

static void __stdcall SwapUU(void* p1, void* p2)
{
	char	*c1 = ( char* ) p1, *c2 = ( char* ) p2, cdata;
	size_t	sztRecLength = sizeof( SortRecStruct );
	__m128i	XmmTemp;
	DWORD	dwTemp;

	while( sztRecLength >= 16 )
	{
		XmmTemp = _mm_loadu_si128( ( __m128i* ) c1 );
		_mm_storeu_si128( ( __m128i* ) c1, _mm_loadu_si128( ( __m128i* ) c2 ) );
		_mm_storeu_si128( ( __m128i* ) c2, XmmTemp );
		c1 += 16; c2 += 16; sztRecLength -= 16;
	}
	if( sztRecLength >= 8 )
	{
		XmmTemp = _mm_loadl_epi64( ( __m128i* ) c1 );
		_mm_storel_epi64( ( __m128i* ) c1, _mm_loadl_epi64( ( __m128i* ) c2 ) );
		_mm_storel_epi64( ( __m128i* ) c2, XmmTemp );
		c1 += 8; c2 += 8; sztRecLength -= 8;
	}
	if( sztRecLength >= 4 )
	{
		dwTemp = *( ( DWORD* ) c1 );
		*( ( int* ) c1 ) = *( ( DWORD* ) c2 );
		*( ( DWORD* ) c2 ) = dwTemp;
		c1 += 4; c2 += 4; sztRecLength -=4;
	}
	while( sztRecLength-- )
	{
		cdata = *c1; *c1++ = *c2; *c2++ = cdata;
	}
}

static void __stdcall CopyRec(void* pDest, void* pSrc)
{
	char	*cDest = ( char* ) pDest, *cSrc = ( char* ) pSrc, cdata;
	size_t	sztRecLength = sizeof( SortRecStruct );

	while( sztRecLength >= 16 )
	{
		_mm_storeu_si128( ( __m128i* ) cDest, _mm_loadu_si128( ( __m128i* ) cSrc ) );
		cDest += 16; cSrc += 16; sztRecLength -= 16;
	}
	if( sztRecLength >= 8 )
	{
		_mm_storel_epi64( ( __m128i* ) cDest, _mm_loadl_epi64( ( __m128i* ) cSrc ) );
		cDest += 8; cSrc += 8; sztRecLength -= 8;
	}
	if( sztRecLength >= 4 )
	{
		*( ( int* ) cDest ) = *( ( DWORD* ) cSrc );
		cDest += 4; cSrc += 4; sztRecLength -= 4;
	}
	while( sztRecLength-- )
	{
		cdata = *cDest; *cDest++ = *cSrc; *cSrc++ = cdata;
	}
}

static DWORD __stdcall InsertionSortAP(SortRecStruct* pTop, SortRecStruct* pBtm, bool* pAbort)
{
	SortRecStruct	*ScanPtr, *CopyPtr;

	ScanPtr = pTop + 1;
	while( ScanPtr <= pBtm )
	{
		CopyPtr = ScanPtr;
		while( ( CopyPtr > pTop ) && ( CopyPtr - 1 )->Key > CopyPtr->Key )
		{
			SwapUU( CopyPtr, CopyPtr - 1 ); CopyPtr--;
		}
		if( *pAbort ) return 1223;
		ScanPtr++;
	}
	return 0;
}

DWORD __stdcall InsertionSortA(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
	DWORD	dwResult = 0;

	if( pRecCount > 1 )
		dwResult = InsertionSortAP( pArray, &pArray[ pRecCount - 1 ], pAbort );
	return dwResult;
}

static DWORD __stdcall InsertionSortBP(SortRecStruct* pTop, SortRecStruct* pBtm, bool* pAbort)
{
	SortRecStruct	*ScanPtr, *CopyPtr;

	ScanPtr = pBtm - 1;
	while( ScanPtr >= pTop )
	{
		CopyPtr = ScanPtr;
		while( ( CopyPtr < pBtm ) && ( CopyPtr + 1 )->Key < CopyPtr->Key )
		{
			SwapUU( CopyPtr, CopyPtr + 1 ); CopyPtr++;
		}
		if( *pAbort ) return 1223;
		ScanPtr--;
	}
	return 0;
}

DWORD __stdcall InsertionSortB(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
	DWORD	dwResult = 0;

	if( pRecCount > 1 )
		dwResult = InsertionSortBP( pArray, &pArray[ pRecCount - 1 ], pAbort );
	return dwResult;
}

static DWORD __stdcall InsertionSortCP(SortRecStruct* pTop, SortRecStruct* pBtm, bool* pAbort)
{
	SortRecStruct	TempData;
	SortRecStruct	*ScanPtr, *CopyPtr;

	ScanPtr = pTop + 1;
	while( ScanPtr <= pBtm )
	{
		if( ( ScanPtr - 1 )->Key > ScanPtr->Key )
		{
			CopyRec( &TempData, ScanPtr ); CopyPtr = ScanPtr;
			do
			{
				CopyRec( CopyPtr, CopyPtr - 1 ); CopyPtr--;
			}
			while( ( CopyPtr > pTop ) && ( ( CopyPtr - 1 )->Key > TempData.Key ) );
			CopyRec( CopyPtr, &TempData );
			if( *pAbort ) return 1223;
		}
		ScanPtr++;
	}
	return 0;
}

DWORD __stdcall InsertionSortC(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
	DWORD	dwResult = 0;

	if( pRecCount > 1 )
		dwResult = InsertionSortCP( pArray, &pArray[ pRecCount - 1 ], pAbort );
	return dwResult;
}

static DWORD __stdcall InsertionSortDP(SortRecStruct* pTop, SortRecStruct* pBtm, bool* pAbort)
{
	SortRecStruct	TempData;
	SortRecStruct	*ScanPtr, *CopyPtr;

	ScanPtr = pBtm - 1;
	while( ScanPtr >= pTop )
	{
		if( ( ScanPtr + 1 )->Key < ScanPtr->Key )
		{
			CopyRec( &TempData, ScanPtr ); CopyPtr = ScanPtr;
			do
			{
				CopyRec( CopyPtr, CopyPtr + 1 ); CopyPtr++;
			}
			while( ( CopyPtr < pBtm ) && ( ( CopyPtr + 1 )->Key < TempData.Key ) );
			CopyRec( CopyPtr, &TempData );
			if( *pAbort ) return 1223;
		}
		ScanPtr--;
	}
	return 0;
}

DWORD __stdcall InsertionSortD(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
	DWORD	dwResult = 0;

	if( pRecCount > 1 )
		dwResult = InsertionSortDP( pArray, &pArray[ pRecCount - 1 ], pAbort );
	return dwResult;
}