/*
 * Copyright 2019 Advanced Micro Devices, Inc.
 *
 * 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, sub license, 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 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 NON-INFRINGEMENT. IN NO EVENT SHALL
 * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS 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.
 *
 * The above copyright notice and this permission notice (including the
 * next paragraph) shall be included in all copies or substantial portions
 * of the Software.
 *
 */

#include "ac_llvm_cull.h"

#include <llvm-c/Core.h>

struct ac_position_w_info {
   /* If a primitive intersects the W=0 plane, it causes a reflection
    * of the determinant used for face culling. Every vertex behind
    * the W=0 plane negates the determinant, so having 2 vertices behind
    * the plane has no effect. This is i1 true if the determinant should be
    * negated.
    */
   LLVMValueRef w_reflection;

   /* If we simplify the "-w <= p <= w" view culling equation, we get
    * "-w <= w", which can't be satisfied when w is negative.
    * In perspective projection, a negative W means that the primitive
    * is behind the viewer, but the equation is independent of the type
    * of projection.
    *
    * w_accepted is false when all W are negative and therefore
    * the primitive is invisible.
    */
   LLVMValueRef w_accepted;

   /* The bounding box culling doesn't work and should be skipped when this is true. */
   LLVMValueRef any_w_negative;
};

static void ac_analyze_position_w(struct ac_llvm_context *ctx, LLVMValueRef pos[3][4],
                                  struct ac_position_w_info *w, unsigned num_vertices)
{
   LLVMBuilderRef builder = ctx->builder;
   LLVMValueRef all_w_negative = ctx->i1true;

   w->w_reflection = ctx->i1false;
   w->any_w_negative = ctx->i1false;

   for (unsigned i = 0; i < num_vertices; i++) {
      LLVMValueRef neg_w;

      neg_w = LLVMBuildFCmp(builder, LLVMRealOLT, pos[i][3], ctx->f32_0, "");
      /* If neg_w is true, negate w_reflection. */
      w->w_reflection = LLVMBuildXor(builder, w->w_reflection, neg_w, "");
      w->any_w_negative = LLVMBuildOr(builder, w->any_w_negative, neg_w, "");
      all_w_negative = LLVMBuildAnd(builder, all_w_negative, neg_w, "");
   }
   w->w_accepted = LLVMBuildNot(builder, all_w_negative, "");
}

/* Perform front/back face culling and return true if the primitive is accepted. */
static LLVMValueRef ac_cull_face(struct ac_llvm_context *ctx, LLVMValueRef pos[3][4],
                                 struct ac_position_w_info *w, bool cull_front, bool cull_back,
                                 bool cull_zero_area)
{
   LLVMBuilderRef builder = ctx->builder;

   if (cull_front && cull_back)
      return ctx->i1false;

   if (!cull_front && !cull_back && !cull_zero_area)
      return ctx->i1true;

   /* Front/back face culling. Also if the determinant == 0, the triangle
    * area is 0.
    */
   LLVMValueRef det_t0 = LLVMBuildFSub(builder, pos[2][0], pos[0][0], "");
   LLVMValueRef det_t1 = LLVMBuildFSub(builder, pos[1][1], pos[0][1], "");
   LLVMValueRef det_t2 = LLVMBuildFSub(builder, pos[0][0], pos[1][0], "");
   LLVMValueRef det_t3 = LLVMBuildFSub(builder, pos[0][1], pos[2][1], "");
   /* t0 * t1 - t2 * t3  =  t2 * -t3 + t0 * t1  =  fma(t2, -t3, t0 * t1) */
   LLVMValueRef det = ac_build_fmad(ctx, det_t2, LLVMBuildFNeg(builder, det_t3, ""),
                                    LLVMBuildFMul(builder, det_t0, det_t1, ""));

   /* Negative W negates the determinant. */
   det = LLVMBuildSelect(builder, w->w_reflection, LLVMBuildFNeg(builder, det, ""), det, "");

   LLVMValueRef accepted = NULL;
   if (cull_front) {
      LLVMRealPredicate cond = cull_zero_area ? LLVMRealOGT : LLVMRealOGE;
      accepted = LLVMBuildFCmp(builder, cond, det, ctx->f32_0, "");
   } else if (cull_back) {
      LLVMRealPredicate cond = cull_zero_area ? LLVMRealOLT : LLVMRealOLE;
      accepted = LLVMBuildFCmp(builder, cond, det, ctx->f32_0, "");
   } else if (cull_zero_area) {
      accepted = LLVMBuildFCmp(builder, LLVMRealONE, det, ctx->f32_0, "");
   }

   if (accepted) {
      /* Don't reject NaN and +/-infinity, these are tricky.
       * Just trust fixed-function HW to handle these cases correctly.
       */
      accepted = LLVMBuildOr(builder, accepted, ac_build_is_inf_or_nan(ctx, det), "");
   }

   return accepted;
}

static void rotate_45degrees(struct ac_llvm_context *ctx, LLVMValueRef v[2])
{
   /* sin(45) == cos(45) */
   LLVMValueRef sincos45 = LLVMConstReal(ctx->f32, 0.707106781);

   /* x2  =  x*cos45 - y*sin45  =  x*sincos45 - y*sincos45
    * y2  =  x*sin45 + y*cos45  =  x*sincos45 + y*sincos45
    */
   LLVMValueRef first = LLVMBuildFMul(ctx->builder, v[0], sincos45, "");

   /* Doing 2x ffma while duplicating the multiplication is 33% faster than fmul+fadd+fadd. */
   LLVMValueRef result[2] = {
      ac_build_fmad(ctx, LLVMBuildFNeg(ctx->builder, v[1], ""), sincos45, first),
      ac_build_fmad(ctx, v[1], sincos45, first),
   };

   memcpy(v, result, sizeof(result));
}

/* Perform view culling and small primitive elimination and return true
 * if the primitive is accepted and initially_accepted == true. */
static void cull_bbox(struct ac_llvm_context *ctx, LLVMValueRef pos[3][4],
                      LLVMValueRef initially_accepted, struct ac_position_w_info *w,
                      LLVMValueRef vp_scale[2], LLVMValueRef vp_translate[2],
                      LLVMValueRef small_prim_precision,
                      LLVMValueRef clip_half_line_width[2],
                      struct ac_cull_options *options,
                      ac_cull_accept_func accept_func, void *userdata)
{
   LLVMBuilderRef builder = ctx->builder;

   if (!options->cull_view_xy && !options->cull_view_near_z && !options->cull_view_far_z &&
       !options->cull_small_prims) {
      if (accept_func)
         accept_func(ctx, initially_accepted, userdata);
      return;
   }

   ac_build_ifcc(ctx, initially_accepted, 10000000);
   {
      LLVMValueRef bbox_min[3], bbox_max[3];
      LLVMValueRef accepted = ctx->i1true;

      /* Compute the primitive bounding box for easy culling. */
      for (unsigned chan = 0; chan < (options->cull_view_near_z ||
                                      options->cull_view_far_z ? 3 : 2); chan++) {
         assert(options->num_vertices >= 2);
         bbox_min[chan] = ac_build_fmin(ctx, pos[0][chan], pos[1][chan]);
         bbox_max[chan] = ac_build_fmax(ctx, pos[0][chan], pos[1][chan]);

         if (options->num_vertices == 3) {
            bbox_min[chan] = ac_build_fmin(ctx, bbox_min[chan], pos[2][chan]);
            bbox_max[chan] = ac_build_fmax(ctx, bbox_max[chan], pos[2][chan]);
         }

         if (clip_half_line_width[chan]) {
            bbox_min[chan] = LLVMBuildFSub(builder, bbox_min[chan], clip_half_line_width[chan], "");
            bbox_max[chan] = LLVMBuildFAdd(builder, bbox_max[chan], clip_half_line_width[chan], "");
         }
      }

      /* View culling. */
      if (options->cull_view_xy || options->cull_view_near_z || options->cull_view_far_z) {
         for (unsigned chan = 0; chan < 3; chan++) {
            LLVMValueRef visible;

            if ((options->cull_view_xy && chan <= 1) || (options->cull_view_near_z && chan == 2)) {
               float t = chan == 2 && options->use_halfz_clip_space ? 0 : -1;
               visible = LLVMBuildFCmp(builder, LLVMRealOGE, bbox_max[chan],
                                       LLVMConstReal(ctx->f32, t), "");
               accepted = LLVMBuildAnd(builder, accepted, visible, "");
            }

            if ((options->cull_view_xy && chan <= 1) || (options->cull_view_far_z && chan == 2)) {
               visible = LLVMBuildFCmp(builder, LLVMRealOLE, bbox_min[chan], ctx->f32_1, "");
               accepted = LLVMBuildAnd(builder, accepted, visible, "");
            }
         }
      }

      /* Small primitive culling - triangles. */
      if (options->cull_small_prims && options->num_vertices == 3) {
         /* Assuming a sample position at (0.5, 0.5), if we round
          * the bounding box min/max extents and the results of
          * the rounding are equal in either the X or Y direction,
          * the bounding box does not intersect the sample.
          *
          * See these GDC slides for pictures:
          * https://frostbite-wp-prd.s3.amazonaws.com/wp-content/uploads/2016/03/29204330/GDC_2016_Compute.pdf
          */
         LLVMValueRef min, max, not_equal[2], visible;

         for (unsigned chan = 0; chan < 2; chan++) {
            /* Convert the position to screen-space coordinates. */
            min = ac_build_fmad(ctx, bbox_min[chan], vp_scale[chan], vp_translate[chan]);
            max = ac_build_fmad(ctx, bbox_max[chan], vp_scale[chan], vp_translate[chan]);
            /* Scale the bounding box according to the precision of
             * the rasterizer and the number of MSAA samples. */
            min = LLVMBuildFSub(builder, min, small_prim_precision, "");
            max = LLVMBuildFAdd(builder, max, small_prim_precision, "");

            /* Determine if the bbox intersects the sample point.
             * It also works for MSAA, but vp_scale, vp_translate,
             * and small_prim_precision are computed differently.
             */
            min = ac_build_round(ctx, min);
            max = ac_build_round(ctx, max);
            not_equal[chan] = LLVMBuildFCmp(builder, LLVMRealONE, min, max, "");
         }
         visible = LLVMBuildAnd(builder, not_equal[0], not_equal[1], "");
         accepted = LLVMBuildAnd(builder, accepted, visible, "");
      }

      /* Small primitive culling - lines. */
      if (options->cull_small_prims && options->num_vertices == 2) {
         /* This only works with lines without perpendicular end caps (lines with perpendicular
          * end caps are rasterized as quads and thus can't be culled as small prims in 99% of
          * cases because line_width >= 1).
          *
          * This takes advantage of the diamont exit rule, which says that every pixel
          * has a diamond inside it touching the pixel boundary and only if a line exits
          * the diamond, that pixel is filled. If a line enters the diamond or stays
          * outside the diamond, the pixel isn't filled.
          *
          * This algorithm is a little simpler than that. The space outside all diamonds also
          * has the same diamond shape, which we'll call corner diamonds.
          *
          * The idea is to cull all lines that are entirely inside a diamond, including
          * corner diamonds. If a line is entirely inside a diamond, it can be culled because
          * it doesn't exit it. If a line is entirely inside a corner diamond, it can be culled
          * because it doesn't enter any diamond and thus can't exit any diamond.
          *
          * The viewport is rotated by 45 degress to turn diamonds into squares, and a bounding
          * box test is used to determine whether a line is entirely inside any square (diamond).
          *
          * The line width doesn't matter. Wide lines only duplicate filled pixels in either X or
          * Y direction from the filled pixels. MSAA also doesn't matter. MSAA should ideally use
          * perpendicular end caps that enable quad rasterization for lines. Thus, this should
          * always use non-MSAA viewport transformation and non-MSAA small prim precision.
          *
          * A good test is piglit/lineloop because it draws 10k subpixel lines in a circle.
          * It should contain no holes if this matches hw behavior.
          */
         LLVMValueRef v0[2], v1[2];

         /* Get vertex positions in pixels. */
         for (unsigned chan = 0; chan < 2; chan++) {
            v0[chan] = ac_build_fmad(ctx, pos[0][chan], vp_scale[chan], vp_translate[chan]);
            v1[chan] = ac_build_fmad(ctx, pos[1][chan], vp_scale[chan], vp_translate[chan]);
         }

         /* Rotate the viewport by 45 degress, so that diamonds become squares. */
         rotate_45degrees(ctx, v0);
         rotate_45degrees(ctx, v1);

         LLVMValueRef not_equal[2];

         for (unsigned chan = 0; chan < 2; chan++) {
            /* The width of each square is sqrt(0.5), so scale it to 1 because we want
             * round() to give us the position of the closest center of a square (diamond).
             */
            v0[chan] = LLVMBuildFMul(builder, v0[chan], LLVMConstReal(ctx->f32, 1.414213562), "");
            v1[chan] = LLVMBuildFMul(builder, v1[chan], LLVMConstReal(ctx->f32, 1.414213562), "");

            /* Compute the bounding box around both vertices. We do this because we must
             * enlarge the line area by the precision of the rasterizer.
             */
            LLVMValueRef min = ac_build_fmin(ctx, v0[chan], v1[chan]);
            LLVMValueRef max = ac_build_fmax(ctx, v0[chan], v1[chan]);

            /* Enlarge the bounding box by the precision of the rasterizer. */
            min = LLVMBuildFSub(builder, min, small_prim_precision, "");
            max = LLVMBuildFAdd(builder, max, small_prim_precision, "");

            /* Round the bounding box corners. If both rounded corners are equal,
             * the bounding box is entirely inside a square (diamond).
             */
            min = ac_build_round(ctx, min);
            max = ac_build_round(ctx, max);
            not_equal[chan] = LLVMBuildFCmp(builder, LLVMRealONE, min, max, "");
         }

         accepted = LLVMBuildAnd(builder, accepted,
                                 LLVMBuildOr(builder, not_equal[0], not_equal[1], ""), "");
      }

      /* Disregard the bounding box culling if any W is negative because the code
       * doesn't work with that.
       */
      accepted = LLVMBuildOr(builder, accepted, w->any_w_negative, "");

      if (accept_func)
         accept_func(ctx, accepted, userdata);
   }
   ac_build_endif(ctx, 10000000);
}

/**
 * Return i1 true if the primitive is accepted (not culled).
 *
 * \param pos                   Vertex positions 3x vec4
 * \param initially_accepted    AND'ed with the result. Some computations can be
 *                              skipped if this is false.
 * \param vp_scale              Viewport scale XY.
 *                              For MSAA, multiply them by the number of samples.
 * \param vp_translate          Viewport translation XY.
 *                              For MSAA, multiply them by the number of samples.
 * \param small_prim_precision  Precision of small primitive culling. This should
 *                              be the same as or greater than the precision of
 *                              the rasterizer. Set to num_samples / 2^subpixel_bits.
 *                              subpixel_bits are defined by the quantization mode.
 * \param options               See ac_cull_options.
 * \param accept_func           Callback invoked in the inner-most branch where the primitive is accepted.
 */
void ac_cull_primitive(struct ac_llvm_context *ctx, LLVMValueRef pos[3][4],
                       LLVMValueRef initially_accepted, LLVMValueRef vp_scale[2],
                       LLVMValueRef vp_translate[2], LLVMValueRef small_prim_precision,
                       LLVMValueRef clip_half_line_width[2], struct ac_cull_options *options,
                       ac_cull_accept_func accept_func, void *userdata)
{
   struct ac_position_w_info w;
   ac_analyze_position_w(ctx, pos, &w, options->num_vertices);

   /* W culling. */
   LLVMValueRef accepted = options->cull_w ? w.w_accepted : ctx->i1true;
   accepted = LLVMBuildAnd(ctx->builder, accepted, initially_accepted, "");

   /* Face culling. */
   accepted = LLVMBuildAnd(
      ctx->builder, accepted,
      ac_cull_face(ctx, pos, &w, options->cull_front, options->cull_back, options->cull_zero_area),
      "");

   /* View culling and small primitive elimination. */
   cull_bbox(ctx, pos, accepted, &w, vp_scale, vp_translate, small_prim_precision,
             clip_half_line_width, options, accept_func, userdata);
}