/* -*- mode: c++; c-basic-offset: 4; indent-tabs-mode: nil -*- */
// Copyright (c) 2004-2005 Lutz Latta
//
// Permission is hereby granted, free of charge, to any person obtaining
// a copy of this software and associated documentation files (the "Software"),
// to deal in the Software without restriction, including without limitation
// the rights to use, copy, modify, merge, publish, distribute, sublicense,
// and/or sell copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included
// in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
// OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
// DEALINGS IN THE SOFTWARE.

// Odd-even merge sort, implemented via parallel sorting network.
#define USE_RGB_FORMAT

#ifndef USE_RGB_FORMAT
float2 
#else
float3
#endif
mergeSortEnd(float2 current : TEXCOORD0,
             uniform samplerRECT sortData : register(s0),
             uniform int2 size,
             uniform int step) : COLOR
{
#ifndef USE_RGB_FORMAT
    float2 currentSample = texRECT(sortData, (float2)current).xy;
#else
    float3 currentSample = texRECT(sortData, (float2)current).xyz;
#endif

    float i = (current.y - 0.5) * size.x + current.x;
    //float i = current.y * size.x + current.x;

    // swap direction
    float b = (fmod(i / step, 2.0) < 1.0 ? 1.0 : -1.0);

	
    float otherI = i + (b * step);
    float2 otherPos = float2(fmod(otherI, size.x), floor(otherI / size.x) + 0.5);
    //float2 otherPos = float2(fmod(otherI, size.x), floor(otherI / size.x));
#ifndef USE_RGB_FORMAT
    float2 otherSample = texRECT(sortData, otherPos).xy;
#else
    float3 otherSample = texRECT(sortData, otherPos).xyz;
#endif
    if (b >= 0) {
        return currentSample.x > otherSample.x ? currentSample : otherSample;
    } else {
        return currentSample.x < otherSample.x ? currentSample : otherSample;
    }
}
#ifndef USE_RGB_FORMAT
float2 
#else
float3
#endif
mergeSortRecursion(float2 _Current : TEXCOORD0,
                   uniform samplerRECT _SortData : register(s0),
                   uniform int2 _Size,
                   uniform int _Step,
                   uniform int _Count) : COLOR
{
#ifndef USE_RGB_FORMAT
    float2 currentSample = texRECT(_SortData, (float2)_Current).xy;
#else
    float3 currentSample = texRECT(_SortData, (float2)_Current).xyz;
#endif
    float i = (_Current.y - 0.5) * _Size.x + _Current.x;
    //float i = _Current.y * _Size.x + _Current.x;

    float iMod = fmod((float)(i / _Step), (float)_Count);

    if (iMod >= 1.0 && iMod < _Count - 1.0) {
        float b = (fmod((float)iMod, 2.0) > 1.0 ? 1.0 : -1.0);

        float otherI = i + (b * _Step);
        float2 otherPos = float2(fmod(otherI, _Size.x), floor(otherI / _Size.x) + 0.5);
        //float2 otherPos = float2(fmod(otherI, _Size.x), floor(otherI / _Size.x));

#ifndef USE_RGB_FORMAT	
        float2 otherSample = texRECT(_SortData, otherPos).xy;
#else
        float3 otherSample = texRECT(_SortData, otherPos).xyz;
#endif
        if (b >= 0) {
            return currentSample.x > otherSample.x ? currentSample : otherSample;
        } else {
            return currentSample.x < otherSample.x ? currentSample : otherSample;
        }
    } else
        return currentSample;
}