/*
	ShellSort.cpp
*/

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

#pragma optimize( "t", on )

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;
	}
}

#ifdef	_M_X64
static	size_t	sztGapBtm = 41;
static size_t	sztGap[ 41 ] =
{
	1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161, 2391484, 7174453
	, 21523360, 64570081, 193710244, 581130733, 1743392200, 5230176601, 15690529804, 47071589413
	, 141214768240, 423644304721, 1270932914164, 3812798742493, 11438396227480, 34315188682441
	, 102945566047324, 308836698141973, 926510094425920, 2779530283277761, 8338590849833284
	, 25015772549499852, 75047317648499552, 225141952945498690, 675425858836496000, 2026277576509488100
	, 6078832729528464400, 18236498188585394000
};
#else
static	size_t	sztGapBtm = 20;
static size_t	sztGap[ 20 ] =
{
	1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161, 2391484, 7174453
	, 21523360, 64570081, 193710244, 581130733, 1743392200
};
#endif

size_t	GetGapPtr(size_t pGap)
{
	size_t	sztTop = 0, sztBtm = sztGapBtm, sztMid;

	for( ; ; )
	{
		sztMid = ( sztBtm - sztTop ) / 2 + sztTop;
		if( sztGap[ sztMid ] > pGap )
		{
			sztBtm = sztMid; continue;
		}
		else if( sztGap[ sztMid ] < pGap )
		{
			if( ( sztTop + 1 ) == sztBtm )
			{
				if( sztGap[ sztBtm ] == pGap )
					return sztBtm;
				else
					return sztTop;
			}
			else
				sztTop = sztMid; continue;
		}
		else
			return sztMid;
	}
}

static DWORD __stdcall ShellSortAR(SortRecStruct* pTop, SortRecStruct* pBtm, bool* pAbort)
{
	SortRecStruct		TempRec, *NewTbl;
	size_t	sztPtr, sztChkPtr, sztSpan, sztCount, sztGapPtr;

	NewTbl = pTop; sztCount = pBtm - pTop + 1;
	sztGapPtr = GetGapPtr( pBtm - pTop + 1 ); sztSpan = sztGap[ sztGapPtr ];
	while( sztSpan > 0 )
	{
		for( sztPtr = 0; sztPtr < sztCount; sztPtr++ )
		{
			sztChkPtr = sztPtr; CopyRec( &TempRec, &NewTbl[ sztPtr ] );
			while( ( sztChkPtr >= sztSpan ) && ( NewTbl[ sztChkPtr - sztSpan ].Key > TempRec.Key ) )
			{
				NewTbl[ sztChkPtr ] = NewTbl[ sztChkPtr - sztSpan ]; sztChkPtr -= sztSpan;
			}
			CopyRec( &NewTbl[ sztChkPtr ], &TempRec );
		}
		if( *pAbort ) return 1223;
		if( sztSpan != 1 )
			sztSpan = sztGap[ --sztGapPtr ];
		else
			sztSpan = 0;	// = return
	}
	return 0;
}

DWORD __stdcall ShellSortA(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
	if( pRecCount > 1 )
		return ShellSortAR( pArray, &pArray[ pRecCount - 1 ], pAbort );
	else
		return 0;
}