// Copyright 2019 Google LLC
//
// This source code is licensed under the BSD-style license found in the
// LICENSE file in the root directory of this source tree.

$assert MR % 4 == 0
$assert NR % 4 == 0
$ABC = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#include <assert.h>

#include <arm_neon.h>

#include <xnnpack/common.h>
#include <xnnpack/ppmm.h>


void xnn_f32_ppmm_minmax_ukernel_${MR}x${NR}__${"neonfma" if FMA else "neon"}(
  size_t mr,
  size_t nc,
  size_t kc,
  const float*restrict a,
  const float*restrict w,
  float*restrict c,
  size_t cm_stride,
  size_t cn_stride,
  const union xnn_f32_minmax_params params[restrict XNN_MIN_ELEMENTS(1)])
{
  assert(mr != 0);
  assert(mr <= ${MR});
  assert(nc != 0);
  assert(kc != 0);
  assert(kc % sizeof(float) == 0);

  float* c0 = c;
  $for M in range(1, MR):
    float* c${M} = (float*) ((uintptr_t) c${M-1} + cm_stride);
    $if M % 2 == 0:
      if XNN_UNPREDICTABLE(mr <= ${M}) {
        c${M} = c${M-1};
      }
    $elif M + 1 == MR:
      if XNN_UNPREDICTABLE(mr != ${M+1}) {
        c${M} = c${M-1};
      }
    $else:
      if XNN_UNPREDICTABLE(mr < ${M+1}) {
        c${M} = c${M-1};
      }

  do {
    $for N in range(0, NR, 4):
      float32x4_t vacc0x${ABC[N:N+4]} = vld1q_f32(w); w += 4;
    $for M in range(1, MR):
      $for N in range(0, NR, 4):
        float32x4_t vacc${M}x${ABC[N:N+4]} = vacc0x${ABC[N:N+4]};

    size_t k = kc;
    do {
      $for M in range(0, MR, 4):
        const float32x4_t va${ABC[M:M+4]} = vld1q_f32(a); a += 4;

      $for N in range(0, NR, 4):
        const float32x4_t vb${ABC[N:N+4]} = vld1q_f32(w); w += 4;

      $if FMA:
        #if XNN_ARCH_ARM64
          $for N in range(0, NR, 4):
            $for M in range(MR):
              vacc${M}x${ABC[N:N+4]} = vfmaq_laneq_f32(vacc${M}x${ABC[N:N+4]}, vb${ABC[N:N+4]}, va${ABC[M&-4:4+M&-4]}, ${M % 4});
        #else
          $for M in range(MR):
            $VGET_PART_F32 = "vget_low_f32" if M % 4 < 2 else "vget_high_f32"
            $MMMM = str(M) * 4
            const float32x4_t va${MMMM} = vdupq_lane_f32(${VGET_PART_F32}(va${ABC[M&-4:4+M&-4]}), ${M % 2});

          $for N in range(0, NR, 4):
            $for M in range(MR):
              $MMMM = str(M) * 4
              vacc${M}x${ABC[N:N+4]} = vfmaq_f32(vacc${M}x${ABC[N:N+4]}, va${MMMM}, vb${ABC[N:N+4]});
        #endif
      $else:
        $for N in range(0, NR, 4):
          $for M in range(MR):
            $VGET_PART_F32 = "vget_low_f32" if M % 4 < 2 else "vget_high_f32"
            vacc${M}x${ABC[N:N+4]} = vmlaq_lane_f32(vacc${M}x${ABC[N:N+4]}, vb${ABC[N:N+4]}, ${VGET_PART_F32}(va${ABC[M&-4:4+M&-4]}), ${M % 2});

      k -= sizeof(float);
    } while (k != 0);

    const float32x4_t vmax = vld1q_dup_f32(&params->scalar.max);
    $for N in range(0, NR, 4):
      $for M in range(MR):
        vacc${M}x${ABC[N:N+4]} = vminq_f32(vacc${M}x${ABC[N:N+4]}, vmax);

    const float32x4_t vmin = vld1q_dup_f32(&params->scalar.min);
    $for N in range(0, NR, 4):
      $for M in range(MR):
        vacc${M}x${ABC[N:N+4]} = vmaxq_f32(vacc${M}x${ABC[N:N+4]}, vmin);

    if XNN_LIKELY(nc >= ${NR}) {
      $for M in reversed(range(MR)):
        vst1q_f32(c${M}, vacc${M}x${ABC[0:4]});
        $for N in range(4, NR, 4):
          vst1q_f32(c${M} + ${N}, vacc${M}x${ABC[N:N+4]});
        c${M} = (float*) ((uintptr_t) c${M} + cn_stride);

      a = (const float*) ((uintptr_t) a - kc * ${MR});

      nc -= ${NR};
    } else {
      $for LOG2N in reversed(range(NR.bit_length())):
        $if NR != 1 << LOG2N:
          $if LOG2N == 1:
            $for M in reversed(range(MR)):
              float32x2_t vacc${M}x01 = vget_low_f32(vacc${M}x0123);
          if (nc & ${1 << LOG2N}) {
            $if LOG2N >= 2:
              $for M in reversed(range(MR)):
                $for N in range(0, 1 << LOG2N, 4):
                  vst1q_f32(c${M}, vacc${M}x${ABC[N:N+4]}); c${M} += 4;

              $for M in reversed(range(MR)):
                $for N in range(0, 1 << (LOG2N - 1), 4):
                  vacc${M}x${ABC[N:N+4]} = vacc${M}x${ABC[N + (1 << LOG2N):N + (1 << LOG2N)+4]};
            $elif LOG2N == 1:
              $for M in reversed(range(MR)):
                vst1_f32(c${M}, vacc${M}x01); c${M} += 2;

              $for M in reversed(range(MR)):
                vacc${M}x01 = vget_high_f32(vacc${M}x0123);
            $elif LOG2N == 0:
              $for M in reversed(range(MR)):
                vst1_lane_f32(c${M}, vacc${M}x01, 0);
          }

      nc = 0;
    }
  } while (nc != 0);
}
