/*
	GnomeSort.cpp
*/

#include "stdafx.h"
#include "GnomeSort.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 DWORD __stdcall GnomeSortAR(SortRecStruct* pArray, size_t pTop, size_t pBtm, bool* pAbort)
{
	size_t	sztPtr, sztGurd;

	if( pTop < pBtm )
	{
		sztGurd = sztPtr = pTop + 1;
		do
		{
			if( pArray[ sztPtr - 1 ].Key <= pArray[ sztPtr ].Key )
			{
				sztPtr++;
			}
			else
			{
				SwapUU( &pArray[ sztPtr - 1 ], &pArray[ sztPtr ] );
				if( sztPtr > sztGurd )
					sztPtr--;
				else
				{
					sztPtr++;
					if( *pAbort ) return 1223;
				}
			}
		}
		while( sztPtr <= pBtm );
	}
	return 0;
}

DWORD __stdcall GnomeSortA(SortRecStruct* pArray, size_t pRecordCount, bool* pAbort)
{
	return GnomeSortAR( pArray, 0, pRecordCount - 1, pAbort );
}

static DWORD __stdcall GnomeSortBR(SortRecStruct* pTop, SortRecStruct* pBtm, bool* pAbort)
{

	SortRecStruct	*RecPtr, *RecGurd;

	if( pTop < pBtm )
	{
		RecGurd = RecPtr = pTop + 1;
		do
		{
			if( ( RecPtr - 1 )->Key <= RecPtr->Key )
			{
				RecPtr++;
			}
			else
			{
				SwapUU( RecPtr - 1, RecPtr );
				if( RecPtr > RecGurd )
					RecPtr--;
				else
				{
					RecPtr++;
					if( *pAbort ) return 1223;
				}
			}
		}
		while( RecPtr <= pBtm );
	}
	return 0;
}

DWORD __stdcall GnomeSortB(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
	return GnomeSortBR( pArray, &pArray[ pRecCount - 1 ], pAbort );
}

static DWORD __stdcall GnomeSortCR(SortRecStruct* pArray, size_t pTop, size_t pBtm, bool* pAbort)
{
	size_t	sztTeleportPtr, sztPtr, sztGurd;

	if( pTop < pBtm )
	{
		sztTeleportPtr = pTop; sztGurd = sztPtr = pTop + 1;
		do
		{
			if( pArray[ sztPtr - 1 ].Key <= pArray[ sztPtr ].Key )
			{
				if( sztTeleportPtr != pTop )
				{
					if( *pAbort ) return 1223;
					sztPtr = sztTeleportPtr; sztTeleportPtr = pTop;
				}
				sztPtr++;
			}
			else
			{
				SwapUU( &pArray[ sztPtr - 1 ], &pArray[ sztPtr ] );
				if( sztPtr > sztGurd )
				{
					if( sztTeleportPtr == pTop )
						sztTeleportPtr = sztPtr;
					sztPtr--;
				}
				else
				{
					sztPtr++;
				}
			}
		}
		while( sztPtr <= pBtm );
	}
	return 0;
}

DWORD __stdcall GnomeSortC(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
	return GnomeSortCR( pArray, 0, pRecCount - 1, pAbort );
}

static DWORD __stdcall GnomeSortDR(SortRecStruct* pTop, SortRecStruct* pBtm, bool* pAbort)
{
	SortRecStruct	*RecTeleportPtr, *RecPtr, *RecGurd;

	if( pTop < pBtm )
	{
		RecTeleportPtr = pTop; RecGurd = RecPtr = pTop + 1;
		do
		{
			if( ( RecPtr - 1 )->Key <= RecPtr->Key )
			{
				if( RecTeleportPtr != pTop )
				{
					if( *pAbort ) return 1223;
					RecPtr = RecTeleportPtr; RecTeleportPtr = pTop;
				}
				RecPtr++;
			}
			else
			{
				SwapUU( RecPtr - 1, RecPtr );
				if( RecPtr > RecGurd )
				{
					if( RecTeleportPtr == pTop )
						RecTeleportPtr = RecPtr;
					RecPtr--;
				}
				else
				{
					RecPtr++;
				}
			}
		}
		while( RecPtr <= pBtm );
	}
	return 0;
}

DWORD __stdcall GnomeSortD(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
	return GnomeSortDR( pArray, &pArray[ pRecCount - 1 ], pAbort );
}