#include "cc_labelling.cuh"

constexpr int connectivity = 4;

__global__ void initialization_step(const int* nn_list, int* residual_list, int* labels, int height, int width)
{
    int x = blockDim.x * blockIdx.x + threadIdx.x;
    int y = blockDim.y * blockIdx.y + threadIdx.y;

    if (x >= width || y >= height)
        return;

    int i = x + y * width;

    int label = i;

    for (int j = i * connectivity; (j - i * connectivity) < connectivity; ++j)
    {
        int nn = nn_list[j];
        if (nn == -1)
            continue;

        if (nn < label)
            label = nn;
    }

    int pos = i * connectivity;
    for (int j = i * connectivity; (j - i * connectivity) < connectivity; ++j)
    {
        int nn = nn_list[j];
        if (nn == -1)
            continue;

        if (nn < i && nn != label)
            residual_list[pos++] = nn;
    }

    // Assign label
    labels[i] = label;
}

__global__ void analysis_step(int* labels, int height, int width)
{
    int x = blockDim.x * blockIdx.x + threadIdx.x;
    int y = blockDim.y * blockIdx.y + threadIdx.y;

    if (x >= width || y >= height)
        return;

    int i = x + y * width;

    int last_label;
    do
    {
        last_label = labels[i];
        labels[i] = labels[labels[i]];
    } while (labels[i] != last_label);
}

__global__ void reduction_step(const int* residual_list, int* labels, int height, int width)
{
    int x = blockDim.x * blockIdx.x + threadIdx.x;
    int y = blockDim.y * blockIdx.y + threadIdx.y;

    if (x >= width || y >= height)
        return;

    int i = x + y * width;

    for (int j = i * connectivity; (j - i * connectivity) < connectivity && residual_list[j] != -1; ++j)
    {
        int label_1 = labels[i];
        while (label_1 != labels[label_1])
            label_1 = labels[label_1];

        int residual_element = residual_list[j];
        int label_2 = labels[residual_element];
        while (label_2 != labels[label_2])
            label_2 = labels[label_2];

        bool flag = label_1 == label_2;

        if (label_1 < label_2)
        {
            int tmp = label_1;
            label_1 = label_2;
            label_2 = tmp;
        }

        while (!flag)
        {
            int label_3 = atomicMin(&labels[label_1], label_2);
            if (label_3 == label_2)
                flag = true;
            else if (label_3 > label_2)
                label_1 = label_3;
            else if (label_3 < label_2)
            {
                label_1 = label_2;
                label_2 = label_3;
            }
        }
    }
}
	.file	"tmpxft_00249d6d_00000000-6_cc_labelling.cudafe1.cpp"
	.text
#APP

#NO_APP
	.type	_ZL26__cudaUnregisterBinaryUtilv, @function
_ZL26__cudaUnregisterBinaryUtilv:
.LFB2010:
	.cfi_startproc
	endbr64
	movq	_ZL20__cudaFatCubinHandle(%rip), %rdi
	jmp	__cudaUnregisterFatBinary@PLT
	.cfi_endproc
.LFE2010:
	.size	_ZL26__cudaUnregisterBinaryUtilv, .-_ZL26__cudaUnregisterBinaryUtilv
	.globl	_Z47__device_stub__Z19initialization_stepPKiPiS1_iiPKiPiS1_ii
	.type	_Z47__device_stub__Z19initialization_stepPKiPiS1_iiPKiPiS1_ii, @function
_Z47__device_stub__Z19initialization_stepPKiPiS1_iiPKiPiS1_ii:
.LFB2032:
	.cfi_startproc
	endbr64
	subq	$152, %rsp
	.cfi_def_cfa_offset 160
	movq	%rdi, 24(%rsp)
	leaq	48(%rsp), %rdi
	movq	%rsi, 16(%rsp)
	leaq	60(%rsp), %rsi
	movq	%rdx, 8(%rsp)
	leaq	32(%rsp), %rdx
	movl	%ecx, 4(%rsp)
	leaq	40(%rsp), %rcx
	movl	%r8d, (%rsp)
	movq	%fs:40, %rax
	movq	%rax, 136(%rsp)
	xorl	%eax, %eax
	leaq	24(%rsp), %rax
	movl	$1, 56(%rsp)
	movq	%rax, 96(%rsp)
	leaq	16(%rsp), %rax
	movq	%rax, 104(%rsp)
	leaq	8(%rsp), %rax
	movq	%rax, 112(%rsp)
	leaq	4(%rsp), %rax
	movq	%rax, 120(%rsp)
	movq	%rsp, %rax
	movq	%rax, 128(%rsp)
	movabsq	$4294967297, %rax
	movq	%rax, 48(%rsp)
	movq	%rax, 60(%rsp)
	movl	$1, 68(%rsp)
	call	__cudaPopCallConfiguration@PLT
	testl	%eax, %eax
	jne	.L2
	pushq	40(%rsp)
	.cfi_def_cfa_offset 168
	leaq	_Z19initialization_stepPKiPiS1_ii(%rip), %rdi
	pushq	40(%rsp)
	.cfi_def_cfa_offset 176
	movq	76(%rsp), %rcx
	movl	84(%rsp), %r8d
	movq	64(%rsp), %rsi
	movl	72(%rsp), %edx
	leaq	112(%rsp), %r9
	call	cudaLaunchKernel@PLT
	popq	%rax
	.cfi_def_cfa_offset 168
	popq	%rdx
	.cfi_def_cfa_offset 160
.L2:
	movq	136(%rsp), %rax
	subq	%fs:40, %rax
	je	.L4
	call	__stack_chk_fail@PLT
.L4:
	addq	$152, %rsp
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2032:
	.size	_Z47__device_stub__Z19initialization_stepPKiPiS1_iiPKiPiS1_ii, .-_Z47__device_stub__Z19initialization_stepPKiPiS1_iiPKiPiS1_ii
	.globl	_Z19initialization_stepPKiPiS1_ii
	.type	_Z19initialization_stepPKiPiS1_ii, @function
_Z19initialization_stepPKiPiS1_ii:
.LFB2033:
	.cfi_startproc
	endbr64
	jmp	_Z47__device_stub__Z19initialization_stepPKiPiS1_iiPKiPiS1_ii
	.cfi_endproc
.LFE2033:
	.size	_Z19initialization_stepPKiPiS1_ii, .-_Z19initialization_stepPKiPiS1_ii
	.globl	_Z35__device_stub__Z13analysis_stepPiiiPiii
	.type	_Z35__device_stub__Z13analysis_stepPiiiPiii, @function
_Z35__device_stub__Z13analysis_stepPiiiPiii:
.LFB2034:
	.cfi_startproc
	endbr64
	subq	$120, %rsp
	.cfi_def_cfa_offset 128
	movq	%rdi, 8(%rsp)
	leaq	24(%rsp), %rcx
	leaq	32(%rsp), %rdi
	movl	%esi, 4(%rsp)
	leaq	44(%rsp), %rsi
	movl	%edx, (%rsp)
	leaq	16(%rsp), %rdx
	movq	%fs:40, %rax
	movq	%rax, 104(%rsp)
	xorl	%eax, %eax
	leaq	8(%rsp), %rax
	movl	$1, 40(%rsp)
	movq	%rax, 80(%rsp)
	leaq	4(%rsp), %rax
	movq	%rax, 88(%rsp)
	movq	%rsp, %rax
	movq	%rax, 96(%rsp)
	movabsq	$4294967297, %rax
	movq	%rax, 32(%rsp)
	movq	%rax, 44(%rsp)
	movl	$1, 52(%rsp)
	call	__cudaPopCallConfiguration@PLT
	testl	%eax, %eax
	jne	.L8
	pushq	24(%rsp)
	.cfi_def_cfa_offset 136
	leaq	_Z13analysis_stepPiii(%rip), %rdi
	pushq	24(%rsp)
	.cfi_def_cfa_offset 144
	movq	60(%rsp), %rcx
	movl	68(%rsp), %r8d
	movq	48(%rsp), %rsi
	movl	56(%rsp), %edx
	leaq	96(%rsp), %r9
	call	cudaLaunchKernel@PLT
	popq	%rax
	.cfi_def_cfa_offset 136
	popq	%rdx
	.cfi_def_cfa_offset 128
.L8:
	movq	104(%rsp), %rax
	subq	%fs:40, %rax
	je	.L10
	call	__stack_chk_fail@PLT
.L10:
	addq	$120, %rsp
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2034:
	.size	_Z35__device_stub__Z13analysis_stepPiiiPiii, .-_Z35__device_stub__Z13analysis_stepPiiiPiii
	.globl	_Z13analysis_stepPiii
	.type	_Z13analysis_stepPiii, @function
_Z13analysis_stepPiii:
.LFB2035:
	.cfi_startproc
	endbr64
	jmp	_Z35__device_stub__Z13analysis_stepPiiiPiii
	.cfi_endproc
.LFE2035:
	.size	_Z13analysis_stepPiii, .-_Z13analysis_stepPiii
	.globl	_Z39__device_stub__Z14reduction_stepPKiPiiiPKiPiii
	.type	_Z39__device_stub__Z14reduction_stepPKiPiiiPKiPiii, @function
_Z39__device_stub__Z14reduction_stepPKiPiiiPKiPiii:
.LFB2036:
	.cfi_startproc
	endbr64
	subq	$152, %rsp
	.cfi_def_cfa_offset 160
	movq	%rdi, 24(%rsp)
	leaq	56(%rsp), %rdi
	movq	%rsi, 16(%rsp)
	leaq	68(%rsp), %rsi
	movl	%edx, 12(%rsp)
	leaq	40(%rsp), %rdx
	movl	%ecx, 8(%rsp)
	leaq	48(%rsp), %rcx
	movq	%fs:40, %rax
	movq	%rax, 136(%rsp)
	xorl	%eax, %eax
	leaq	24(%rsp), %rax
	movl	$1, 64(%rsp)
	movq	%rax, 104(%rsp)
	leaq	16(%rsp), %rax
	movq	%rax, 112(%rsp)
	leaq	12(%rsp), %rax
	movq	%rax, 120(%rsp)
	leaq	8(%rsp), %rax
	movq	%rax, 128(%rsp)
	movabsq	$4294967297, %rax
	movq	%rax, 56(%rsp)
	movq	%rax, 68(%rsp)
	movl	$1, 76(%rsp)
	call	__cudaPopCallConfiguration@PLT
	testl	%eax, %eax
	jne	.L13
	pushq	48(%rsp)
	.cfi_def_cfa_offset 168
	leaq	_Z14reduction_stepPKiPiii(%rip), %rdi
	pushq	48(%rsp)
	.cfi_def_cfa_offset 176
	movq	84(%rsp), %rcx
	movl	92(%rsp), %r8d
	movq	72(%rsp), %rsi
	movl	80(%rsp), %edx
	leaq	120(%rsp), %r9
	call	cudaLaunchKernel@PLT
	popq	%rax
	.cfi_def_cfa_offset 168
	popq	%rdx
	.cfi_def_cfa_offset 160
.L13:
	movq	136(%rsp), %rax
	subq	%fs:40, %rax
	je	.L15
	call	__stack_chk_fail@PLT
.L15:
	addq	$152, %rsp
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2036:
	.size	_Z39__device_stub__Z14reduction_stepPKiPiiiPKiPiii, .-_Z39__device_stub__Z14reduction_stepPKiPiiiPKiPiii
	.globl	_Z14reduction_stepPKiPiii
	.type	_Z14reduction_stepPKiPiii, @function
_Z14reduction_stepPKiPiii:
.LFB2037:
	.cfi_startproc
	endbr64
	jmp	_Z39__device_stub__Z14reduction_stepPKiPiiiPKiPiii
	.cfi_endproc
.LFE2037:
	.size	_Z14reduction_stepPKiPiii, .-_Z14reduction_stepPKiPiii
	.section	.rodata.str1.1,"aMS",@progbits,1
.LC0:
	.string	"_Z14reduction_stepPKiPiii"
.LC1:
	.string	"_Z13analysis_stepPiii"
.LC2:
	.string	"_Z19initialization_stepPKiPiS1_ii"
	.section	.text.startup,"ax",@progbits
	.type	_ZL24__sti____cudaRegisterAllv, @function
_ZL24__sti____cudaRegisterAllv:
.LFB2039:
	.cfi_startproc
	endbr64
	pushq	%rbx
	.cfi_def_cfa_offset 16
	.cfi_offset 3, -16
	leaq	_ZL15__fatDeviceText(%rip), %rdi
	call	__cudaRegisterFatBinary@PLT
	pushq	$0
	.cfi_def_cfa_offset 24
	xorl	%r9d, %r9d
	orl	$-1, %r8d
	pushq	$0
	.cfi_def_cfa_offset 32
	leaq	.LC0(%rip), %rdx
	movq	%rax, %rdi
	movq	%rax, %rbx
	pushq	$0
	.cfi_def_cfa_offset 40
	movq	%rdx, %rcx
	leaq	_Z14reduction_stepPKiPiii(%rip), %rsi
	pushq	$0
	.cfi_def_cfa_offset 48
	movq	%rax, _ZL20__cudaFatCubinHandle(%rip)
	call	__cudaRegisterFunction@PLT
	addq	$32, %rsp
	.cfi_def_cfa_offset 16
	movq	%rbx, %rdi
	xorl	%r9d, %r9d
	pushq	$0
	.cfi_def_cfa_offset 24
	leaq	.LC1(%rip), %rdx
	orl	$-1, %r8d
	leaq	_Z13analysis_stepPiii(%rip), %rsi
	pushq	$0
	.cfi_def_cfa_offset 32
	movq	%rdx, %rcx
	pushq	$0
	.cfi_def_cfa_offset 40
	pushq	$0
	.cfi_def_cfa_offset 48
	call	__cudaRegisterFunction@PLT
	addq	$32, %rsp
	.cfi_def_cfa_offset 16
	movq	%rbx, %rdi
	xorl	%r9d, %r9d
	pushq	$0
	.cfi_def_cfa_offset 24
	leaq	.LC2(%rip), %rdx
	orl	$-1, %r8d
	leaq	_Z19initialization_stepPKiPiS1_ii(%rip), %rsi
	pushq	$0
	.cfi_def_cfa_offset 32
	movq	%rdx, %rcx
	pushq	$0
	.cfi_def_cfa_offset 40
	pushq	$0
	.cfi_def_cfa_offset 48
	call	__cudaRegisterFunction@PLT
	movq	_ZL20__cudaFatCubinHandle(%rip), %rdi
	addq	$32, %rsp
	.cfi_def_cfa_offset 16
	call	__cudaRegisterFatBinaryEnd@PLT
	leaq	_ZL26__cudaUnregisterBinaryUtilv(%rip), %rdi
	popq	%rbx
	.cfi_def_cfa_offset 8
	jmp	atexit@PLT
	.cfi_endproc
.LFE2039:
	.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:

#pragma once

#include <hip/hip_runtime.h>

__global__ void initialization_step(const int* nn_list, int* residual_list, int* labels, int height, int width);

__global__ void analysis_step(int* labels, int height, int width);

__global__ void reduction_step(const int* residual_list, int* labels, int height, int width);
	.text
	.file	"cc_labelling.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
