#version 430 core
////////////////////////////////////////////////////////////////////////////////
// <copyright>
// Copyright (c) 2015 Hue AS. All rights reserved.
//
// All rights are reserved. Reproduction or transmission in whole or in part, in
// any form or by any means, electronic, mechanical or otherwise, is prohibited
// without the prior written permission of the copyright owner.
// </copyright>
////////////////////////////////////////////////////////////////////////////////

#define F $REDUCE_FACTOR$
#define W $COMPUTE_WIDTH$
#define HALF_H $HALF_COMPUTE_HEIGHT$
#define W_F (W / F)
#define H_F (2 * HALF_H / F)

layout(binding=0) uniform usampler2D counts;
layout(binding=0) writeonly uniform uimage2D maxima;
shared uint acc[W * HALF_H];

#define NUM_BANKS 16
uint shuffle(uint index)
{
  return (index & ~(NUM_BANKS - 1)) | ((index + index / NUM_BANKS) & (NUM_BANKS - 1));
}

layout(local_size_x = W, local_size_y = HALF_H) in;

void main()
{
    ivec2 texSize = textureSize(counts, 0);
    ivec2 texPos1 = ivec2(gl_GlobalInvocationID.x, gl_WorkGroupID.y * 2 * HALF_H + 2 * gl_LocalInvocationID.y);
    ivec2 texPos2 = ivec2(texPos1.x, texPos1.y + 1);
    uint acc1 = all(lessThan(texPos1, texSize)) ? texelFetch(counts, texPos1, 0).x : 0u;
    uint acc2 = all(lessThan(texPos2, texSize)) ? texelFetch(counts, texPos2, 0).x : 0u;
    acc1 = max(acc1, acc2);
    uint minorIndex = gl_LocalInvocationID.x / F + gl_LocalInvocationID.y / (F / 2) * W_F;
    uint majorIndex = gl_LocalInvocationID.x % F + gl_LocalInvocationID.y % (F / 2) * F;
    uint shuffleIndex = minorIndex + majorIndex * W_F * H_F;
    acc[shuffle(shuffleIndex)] = acc1;
    barrier();
    acc1 = acc[shuffle(gl_LocalInvocationIndex)];
    for (uint d = W * HALF_H / 2; d >= uint(W_F * H_F); d >>= 1u)
    {
        barrier();
        if (gl_LocalInvocationIndex < d)
        {
            uint index = gl_LocalInvocationIndex + d;
            acc2 = acc[shuffle(index)];
            acc1 = max(acc1, acc2);
            acc[shuffle(gl_LocalInvocationIndex)] = acc1;
        }
    }
    if (gl_LocalInvocationIndex < W_F * H_F)
    {
        uvec2 pos = uvec2(gl_LocalInvocationIndex % W_F, gl_LocalInvocationIndex / W_F);
        imageStore(maxima, ivec2(pos + gl_WorkGroupID.xy * uvec2(W_F, H_F)), uvec4(acc1));
    }
}
