/*
	CombSort.cpp

*/

#include "stdafx.h"
#include "CombSort.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 CombSortAR(SortRecStruct* pArray, size_t pTop, size_t pBtm, bool* pAbort)
{
	SortRecStruct	*NewTbl;
	size_t	sztPtr, sztCount, sztGap, sztChkPtr;
	bool	bNeedRefresh = false;

	NewTbl = &pArray[ pTop ]; sztCount = sztGap = pBtm - pTop + 1;
	while( ( sztGap > 1 ) || bNeedRefresh )
	{
		if( sztGap > 1 )
		{
			sztGap = ( size_t ) ( ( double ) sztGap / 1.247330950103979 );
		}
		bNeedRefresh = false; sztChkPtr = sztGap;
		for( sztPtr = 0; sztChkPtr < sztCount; sztChkPtr++, sztPtr++ )
		{
			if( NewTbl[ sztPtr ].Key > NewTbl[ sztChkPtr ].Key )
			{
				SwapUU( &NewTbl[ sztPtr ], &NewTbl[ sztChkPtr ] );
				bNeedRefresh = true;
			}
		}
		if( *pAbort ) return 1223;
	}
	return 0;
}

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

static DWORD __stdcall CombSortBR(SortRecStruct* pArray, size_t pTop, size_t pBtm, bool* pAbort)
{
	SortRecStruct	*NewTbl;
	size_t	sztPtr, sztCount, sztGap, sztChkPtr;
	bool	bNeedRefresh = false;

	NewTbl = &pArray[ pTop ]; sztCount = sztGap = pBtm - pTop + 1;
	while( ( sztGap > 1 ) || bNeedRefresh )
	{
		if( sztGap > 1 )
		{
			//sztGap = ( size_t ) ( ( double ) sztGap / 1.247330950103979 );
			sztGap = sztGap * 10 / 13;
		}
		bNeedRefresh = false; sztChkPtr = sztGap;
		for( sztPtr = 0; sztChkPtr < sztCount; sztChkPtr++, sztPtr++ )
		{
			if( NewTbl[ sztPtr ].Key > NewTbl[ sztChkPtr ].Key )
			{
				SwapUU( &NewTbl[ sztPtr ], &NewTbl[ sztChkPtr ] );
				bNeedRefresh = true;
			}
		}
		if( *pAbort ) return 1223;
	}
	return 0;
}

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

static DWORD __stdcall CombSortCR(SortRecStruct* pArray, size_t pTop, size_t pBtm, bool* pAbort)
{
	SortRecStruct	*NewTbl;
	size_t	sztPtr, sztCount, sztGap, sztChkPtr;
	bool	bNeedRefresh = false;

	NewTbl = &pArray[ pTop ]; sztCount = sztGap = pBtm - pTop + 1;
	while( ( sztGap > 1 ) || bNeedRefresh )
	{
		if( sztGap > 1 )
		{
			//sztGap = ( size_t ) ( ( double ) sztGap / 1.247330950103979 );
			sztGap = sztGap * 10 / 13;
			if( sztGap == 9 && sztGap == 10 )
				sztGap = 11;
		}
		bNeedRefresh = false; sztChkPtr = sztGap;
		for( sztPtr = 0; sztChkPtr < sztCount; sztChkPtr++, sztPtr++ )
		{
			if( NewTbl[ sztPtr ].Key > NewTbl[ sztChkPtr ].Key )
			{
				SwapUU( &NewTbl[ sztPtr ], &NewTbl[ sztChkPtr ] );
				bNeedRefresh = true;
			}
		}
		if( *pAbort ) return 1223;
	}
	return 0;
}

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