


/*!
 * Compute the next power of 2 which occurs after a number.
 *
 * @param n
 */
__device__
int nextPower2(int n)
{
    int pow2 = 2;
    while ( pow2 < n )
    {
        pow2 *= 2;
    }

    return pow2;
}



/*!
 * Swap two values
 *
 * @param a
 * @param b
 */
__device__
void swap(float *a, float *b)
{
    float c = *a;
    *a = *b;
    *b = c;
}



/*!
 * Sort an array using bitonic sort. The array should have a size which is a
 * power of two.
 *
 * @param array
 * @param size
 */
__device__
void bitonicSort(float *array, int size)
{
    int bsize = size / 2;
    int dir, a, b, t;

    for ( int ob = 2; ob <= size; ob *= 2 )
    {
        for ( int ib = ob; ib >= 2; ib /= 2 )
        {
            t = ib/2;
            for ( int i = 0; i < bsize; ++i )
            {
                dir = -((i/(ob/2)) & 0x1);
                a = (i/t) * ib + (i%t);
                b = a + t;
                if ( (!dir && (array[a] > array[b])) || (dir && (array[a] < array[b])) )
                {
                    swap(&array[a], &array[b]);
                }
            }
        }
    }
}



/*!
 * Sort an array using bitonic sort, while also applying the same swap operations
 * to a second array of the same size. The arrays should have a size which is a
 * power of two.
 *
 * @param size
 * @param array
 * @param extra
 */
__device__
void bitonicSortFF(int size, float *array, float *extra)
{
    int bsize = size / 2;
    int dir, a, b, t;

    for ( int ob = 2; ob <= size; ob *= 2 )
    {
        for ( int ib = ob; ib >= 2; ib /= 2 )
        {
            t = ib/2;
            for ( int i = 0; i < bsize; ++i )
            {
                dir = -((i/(ob/2)) & 0x1);
                a = (i/t) * ib + (i%t);
                b = a + t;
                if ( (!dir && (array[a] > array[b])) || (dir && (array[a] < array[b])) )
                {
                    swap(&array[a], &array[b]);
                    swap(&extra[a], &extra[b]);
                }
            }
        }
    }
}



/*!
 * Compute the rank of a sorted vector in place. In the event of ties,
 * the ranks are corrected using fractional ranking.
 *
 * @param array
 * @param n
 */
__device__
void computeRank(float *array, int n)
{
    int i = 0;

    while ( i < n - 1 )
    {
        float a_i = array[i];

        if ( a_i == array[i + 1] )
        {
            int j = i + 2;
            int k;
            float rank = 0;

            // we have detected a tie, find number of equal elements
            while ( j < n && a_i == array[j] )
            {
                ++j;
            }

            // compute rank
            for ( k = i; k < j; ++k )
            {
                rank += k;
            }

            // divide by number of ties
            rank /= (float) (j - i);

            for ( k = i; k < j; ++k )
            {
                array[k] = rank;
            }

            i = j;
        }
        else
        {
            // no tie - set rank to natural ordered position
            array[i] = i;
            ++i;
        }
    }

    if ( i == n - 1 )
    {
        array[n - 1] = (float) (n - 1);
    }
}

	.file	"tmpxft_0031f7fa_00000000-6_sort.cudafe1.cpp"
	.text
#APP

#NO_APP
	.type	_ZL26__cudaUnregisterBinaryUtilv, @function
_ZL26__cudaUnregisterBinaryUtilv:
.LFB2015:
	.cfi_startproc
	endbr64
	movq	_ZL20__cudaFatCubinHandle(%rip), %rdi
	jmp	__cudaUnregisterFatBinary@PLT
	.cfi_endproc
.LFE2015:
	.size	_ZL26__cudaUnregisterBinaryUtilv, .-_ZL26__cudaUnregisterBinaryUtilv
	.globl	_Z10nextPower2i
	.type	_Z10nextPower2i, @function
_Z10nextPower2i:
.LFB2008:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	popq	%rax
	.cfi_def_cfa_offset 8
	subq	$24, %rsp
	.cfi_def_cfa_offset 32
	movl	$1, 12(%rsp)
	movl	12(%rsp), %edi
	call	exit@PLT
	.cfi_endproc
.LFE2008:
	.size	_Z10nextPower2i, .-_Z10nextPower2i
	.globl	_Z4swapPfS_
	.type	_Z4swapPfS_, @function
_Z4swapPfS_:
.LFB2009:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	popq	%rax
	.cfi_def_cfa_offset 8
	subq	$24, %rsp
	.cfi_def_cfa_offset 32
	movl	$1, 12(%rsp)
	movl	12(%rsp), %edi
	call	exit@PLT
	.cfi_endproc
.LFE2009:
	.size	_Z4swapPfS_, .-_Z4swapPfS_
	.globl	_Z11bitonicSortPfi
	.type	_Z11bitonicSortPfi, @function
_Z11bitonicSortPfi:
.LFB2010:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	popq	%rax
	.cfi_def_cfa_offset 8
	subq	$24, %rsp
	.cfi_def_cfa_offset 32
	movl	$1, 12(%rsp)
	movl	12(%rsp), %edi
	call	exit@PLT
	.cfi_endproc
.LFE2010:
	.size	_Z11bitonicSortPfi, .-_Z11bitonicSortPfi
	.globl	_Z13bitonicSortFFiPfS_
	.type	_Z13bitonicSortFFiPfS_, @function
_Z13bitonicSortFFiPfS_:
.LFB2011:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	popq	%rax
	.cfi_def_cfa_offset 8
	subq	$24, %rsp
	.cfi_def_cfa_offset 32
	movl	$1, 12(%rsp)
	movl	12(%rsp), %edi
	call	exit@PLT
	.cfi_endproc
.LFE2011:
	.size	_Z13bitonicSortFFiPfS_, .-_Z13bitonicSortFFiPfS_
	.globl	_Z11computeRankPfi
	.type	_Z11computeRankPfi, @function
_Z11computeRankPfi:
.LFB2154:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	popq	%rax
	.cfi_def_cfa_offset 8
	pushq	%rax
	.cfi_def_cfa_offset 16
	call	_Z11bitonicSortPfi
	.cfi_endproc
.LFE2154:
	.size	_Z11computeRankPfi, .-_Z11computeRankPfi
	.section	.text.startup,"ax",@progbits
	.type	_ZL24__sti____cudaRegisterAllv, @function
_ZL24__sti____cudaRegisterAllv:
.LFB2038:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	leaq	_ZL15__fatDeviceText(%rip), %rdi
	call	__cudaRegisterFatBinary@PLT
	movq	%rax, %rdi
	movq	%rax, _ZL20__cudaFatCubinHandle(%rip)
	call	__cudaRegisterFatBinaryEnd@PLT
	leaq	_ZL26__cudaUnregisterBinaryUtilv(%rip), %rdi
	popq	%rdx
	.cfi_def_cfa_offset 8
	jmp	atexit@PLT
	.cfi_endproc
.LFE2038:
	.size	_ZL24__sti____cudaRegisterAllv, .-_ZL24__sti____cudaRegisterAllv
	.section	.init_array,"aw"
	.align 8
	.quad	_ZL24__sti____cudaRegisterAllv
	.section	.nvFatBinSegment,"aw"
	.align 8
	.type	_ZL15__fatDeviceText, @object
	.size	_ZL15__fatDeviceText, 24
_ZL15__fatDeviceText:
	.long	1180844977
	.long	1
	.quad	fatbinData
	.quad	0
	.local	_ZL20__cudaFatCubinHandle
	.comm	_ZL20__cudaFatCubinHandle,8,8
	.ident	"GCC: (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:


#include <hip/hip_runtime.h>



/*!
 * Compute the next power of 2 which occurs after a number.
 *
 * @param n
 */
__device__
int nextPower2(int n)
{
    int pow2 = 2;
    while ( pow2 < n )
    {
        pow2 *= 2;
    }

    return pow2;
}



/*!
 * Swap two values
 *
 * @param a
 * @param b
 */
__device__
void swap(float *a, float *b)
{
    float c = *a;
    *a = *b;
    *b = c;
}



/*!
 * Sort an array using bitonic sort. The array should have a size which is a
 * power of two.
 *
 * @param array
 * @param size
 */
__device__
void bitonicSort(float *array, int size)
{
    int bsize = size / 2;
    int dir, a, b, t;

    for ( int ob = 2; ob <= size; ob *= 2 )
    {
        for ( int ib = ob; ib >= 2; ib /= 2 )
        {
            t = ib/2;
            for ( int i = 0; i < bsize; ++i )
            {
                dir = -((i/(ob/2)) & 0x1);
                a = (i/t) * ib + (i%t);
                b = a + t;
                if ( (!dir && (array[a] > array[b])) || (dir && (array[a] < array[b])) )
                {
                    swap(&array[a], &array[b]);
                }
            }
        }
    }
}



/*!
 * Sort an array using bitonic sort, while also applying the same swap operations
 * to a second array of the same size. The arrays should have a size which is a
 * power of two.
 *
 * @param size
 * @param array
 * @param extra
 */
__device__
void bitonicSortFF(int size, float *array, float *extra)
{
    int bsize = size / 2;
    int dir, a, b, t;

    for ( int ob = 2; ob <= size; ob *= 2 )
    {
        for ( int ib = ob; ib >= 2; ib /= 2 )
        {
            t = ib/2;
            for ( int i = 0; i < bsize; ++i )
            {
                dir = -((i/(ob/2)) & 0x1);
                a = (i/t) * ib + (i%t);
                b = a + t;
                if ( (!dir && (array[a] > array[b])) || (dir && (array[a] < array[b])) )
                {
                    swap(&array[a], &array[b]);
                    swap(&extra[a], &extra[b]);
                }
            }
        }
    }
}



/*!
 * Compute the rank of a sorted vector in place. In the event of ties,
 * the ranks are corrected using fractional ranking.
 *
 * @param array
 * @param n
 */
__device__
void computeRank(float *array, int n)
{
    int i = 0;

    while ( i < n - 1 )
    {
        float a_i = array[i];

        if ( a_i == array[i + 1] )
        {
            int j = i + 2;
            int k;
            float rank = 0;

            // we have detected a tie, find number of equal elements
            while ( j < n && a_i == array[j] )
            {
                ++j;
            }

            // compute rank
            for ( k = i; k < j; ++k )
            {
                rank += k;
            }

            // divide by number of ties
            rank /= (float) (j - i);

            for ( k = i; k < j; ++k )
            {
                array[k] = rank;
            }

            i = j;
        }
        else
        {
            // no tie - set rank to natural ordered position
            array[i] = i;
            ++i;
        }
    }

    if ( i == n - 1 )
    {
        array[n - 1] = (float) (n - 1);
    }
}

	.text
	.file	"sort.hip"
	.type	__hip_cuid_,@object             # @__hip_cuid_
	.bss
	.globl	__hip_cuid_
__hip_cuid_:
	.byte	0                               # 0x0
	.size	__hip_cuid_, 1

	.ident	"AMD clang version 18.0.0git (https://github.com/RadeonOpenCompute/llvm-project roc-6.3.2 25012 e5bf7e55c91490b07c49d8960fa7983d864936c4)"
	.section	".note.GNU-stack","",@progbits
	.addrsig
	.addrsig_sym __hip_cuid_

	.text
	.p2alignl 7, 3214868480
	.fill 96, 4, 3214868480
	.type	__hip_cuid_,@object             ; @__hip_cuid_
	.section	.bss,"aw",@nobits
	.globl	__hip_cuid_
__hip_cuid_:
	.byte	0                               ; 0x0
	.size	__hip_cuid_, 1

	.ident	"AMD clang version 18.0.0git (https://github.com/RadeonOpenCompute/llvm-project roc-6.3.2 25012 e5bf7e55c91490b07c49d8960fa7983d864936c4)"
	.section	".note.GNU-stack","",@progbits
	.addrsig
	.addrsig_sym __hip_cuid_
	.amdgcn_target "amdgcn-amd-amdhsa--gfx1100"
	.amdgpu_metadata
---
amdhsa.kernels:  []
amdhsa.target:   amdgcn-amd-amdhsa--gfx1100
amdhsa.version:
  - 1
  - 2
...

	.end_amdgpu_metadata
