/*
	OddEvenSort.cpp
*/

#include "stdafx.h"
#include "OddEvenSort.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 OddEvenSortAR(SortRecStruct* pArray, size_t pTop, size_t pBtm, bool* pAbort)
{	// reverse scan
	size_t	sztPtr;
	bool	bRefresh;

	do
	{
		bRefresh = false;
		// section A
		for( sztPtr = pBtm; sztPtr > pTop; sztPtr-- )
		{
			if( pArray[ sztPtr - 1 ].Key > pArray[ sztPtr ].Key )
			{
				SwapUU( &pArray[ sztPtr - 1 ], &pArray[ sztPtr ] ); bRefresh = true;
			}
			// sztPtr を２回にわけてデクリメントしている理由を考えてね。
			sztPtr--; if( sztPtr <= pTop ) break;
		}
		// section B
		for( sztPtr = pBtm - 1; sztPtr > pTop; sztPtr-- )
		{
			if( pArray[ sztPtr - 1 ].Key > pArray[ sztPtr ].Key )
			{
				SwapUU( &pArray[ sztPtr - 1 ], &pArray[ sztPtr ] ); bRefresh = true;
			}
			// sztPtr を２回にわけてデクリメントしている理由を考えてね。
			sztPtr--; if( sztPtr <= pTop ) break;
		}
		if( *pAbort ) return 1223;
	}
	while( bRefresh );
	return 0;
}

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

static DWORD __stdcall OddEvenSortBR(SortRecStruct* pArray, size_t pTop, size_t pBtm, bool* pAbort)
{	// forward scan
	size_t	sztPtr;
	bool	bRefresh;

	do
	{
		bRefresh = false;
		// section A
		for( sztPtr = pTop; sztPtr < pBtm; sztPtr++ )
		{
			if( pArray[ sztPtr + 1 ].Key < pArray[ sztPtr ].Key )
			{
				SwapUU( &pArray[ sztPtr + 1 ], &pArray[ sztPtr ] ); bRefresh = true;
			}
			// sztPtr を２回にわけてインクリメントしている理由を考えてね。
			sztPtr++; if( sztPtr >= pBtm ) break;
		}
		// section B
		for( sztPtr = pTop + 1; sztPtr < pBtm; sztPtr++ )
		{
			if( pArray[ sztPtr + 1 ].Key < pArray[ sztPtr ].Key )
			{
				SwapUU( &pArray[ sztPtr + 1 ], &pArray[ sztPtr ] ); bRefresh = true;
			}
			// sztPtr を２回にわけてインクリメントしている理由を考えてね。
			sztPtr++; if( sztPtr >= pBtm ) break;
		}
		if( *pAbort ) return 1223;
	}
	while( bRefresh );
	return 0;
}

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

static DWORD __stdcall OddEvenSortCR(SortRecStruct* pTop, SortRecStruct *pBtm, bool* pAbort)
{	// reverse scan
	SortRecStruct	*RecPtr;
	bool	bRefresh;

	do
	{
		bRefresh = false;
		// section A
		for( RecPtr = pBtm; RecPtr > pTop; RecPtr -= 2 )
		{
			if( ( RecPtr - 1 )->Key > RecPtr->Key )
			{
				SwapUU( RecPtr - 1, RecPtr ); bRefresh = true;
			}
		}
		// section B
		for( RecPtr = pBtm - 1; RecPtr > pTop; RecPtr -= 2 )
		{
			if( ( RecPtr - 1 )->Key > RecPtr->Key )
			{
				SwapUU( RecPtr - 1, RecPtr ); bRefresh = true;
			}
		}
		if( *pAbort ) return 1223;
	}
	while( bRefresh );
	return 0;
}

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

static DWORD __stdcall OddEvenSortDR(SortRecStruct* pTop, SortRecStruct *pBtm, bool* pAbort)
{	// forward scan
	SortRecStruct	*RecPtr;
	bool	bRefresh;

	do
	{
		bRefresh = false;
		// section A
		for( RecPtr = pTop; RecPtr < pBtm; RecPtr += 2 )
		{
			if( ( RecPtr + 1 )->Key < RecPtr->Key )
			{
				SwapUU( RecPtr + 1, RecPtr ); bRefresh = true;
			}
		}
		// section B
		for( RecPtr = pTop + 1; RecPtr < pBtm; RecPtr += 2 )
		{
			if( ( RecPtr + 1 )->Key < RecPtr->Key )
			{
				SwapUU( RecPtr + 1, RecPtr ); bRefresh = true;
			}
		}
		if( *pAbort ) return 1223;
	}
	while( bRefresh );
	return 0;
}

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