// Copyright 2008 Dolphin Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#include "VideoCommon/VertexLoaderManager.h"

#include <algorithm>
#include <iterator>
#include <memory>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>

#include <retro_atomic.h>

#include "Common/CommonTypes.h"
#include "Common/EnumMap.h"
#include "Common/Logging/Log.h"

#include "Core/HW/Memmap.h"
#include "Core/System.h"

#include "VideoCommon/AbstractGfx.h"
#include "VideoCommon/BPMemory.h"
#include "VideoCommon/CPMemory.h"
#include "VideoCommon/DataReader.h"
#include "VideoCommon/NativeVertexFormat.h"
#include "VideoCommon/UidTable.h"
#include "VideoCommon/VertexLoaderBase.h"
#include "VideoCommon/VertexManagerBase.h"
#include "VideoCommon/VertexShaderManager.h"
#include "VideoCommon/VideoConfig.h"
#include "VideoCommon/XFMemory.h"

namespace VertexLoaderManager
{
// Used by zfreeze
std::array<u32, 3> position_matrix_index_cache;
// 3 vertices, 4 floats each to allow SIMD overwrite
alignas(sizeof(std::array<float, 4>)) std::array<std::array<float, 4>, 3> position_cache;
alignas(sizeof(std::array<float, 4>)) std::array<float, 4> normal_cache;
alignas(sizeof(std::array<float, 4>)) std::array<float, 4> tangent_cache;
alignas(sizeof(std::array<float, 4>)) std::array<float, 4> binormal_cache;

/* each PortableVertexDeclaration's NativeVertexFormat, owned here */
static uid_table s_native_vertex_map;
static NativeVertexFormat* s_current_vtx_fmt;
u32 g_current_components;

// Every loader made so far, shared by the main and the preprocessing thread. Entries are only
// ever added while both run, so each bucket is a list pushed at its head with a CAS and read
// without a lock; Clear frees it all once neither thread is decoding.
// A loader is its own list node (m_next_loader).
constexpr size_t LOADER_BUCKETS = 1024;
static retro_atomic_ptr_t s_vertex_loaders[LOADER_BUCKETS];

static VertexLoaderBase* FindLoader(VertexLoaderBase* loader, const VertexLoaderBase* stop,
                                    const VertexLoaderUID& uid)
{
  for (; loader != stop; loader = loader->m_next_loader)
  {
    if (loader->m_uid == uid)
      return loader;
  }
  return nullptr;
}

// The loader for uid, made from desc and attr if this is the first time it is seen.
static VertexLoaderBase* GetOrAddLoader(const VertexLoaderUID& uid, const TVtxDesc& desc,
                                        const VAT& attr)
{
  retro_atomic_ptr_t* bucket = &s_vertex_loaders[uid.GetHash() % LOADER_BUCKETS];
  auto* head = static_cast<VertexLoaderBase*>(retro_atomic_load_acquire_ptr(bucket));
  if (VertexLoaderBase* found = FindLoader(head, nullptr, uid))
    return found;

  VertexLoaderBase* const loader = VertexLoaderBase::CreateVertexLoader(desc, attr);
  loader->m_uid = uid;
  loader->m_next_loader = head;
  while (!retro_atomic_cas_ptr(bucket, loader->m_next_loader, loader))
  {
    // Someone else pushed meanwhile: it may be the same loader, made on the other thread.
    auto* newer = static_cast<VertexLoaderBase*>(retro_atomic_load_acquire_ptr(bucket));
    if (VertexLoaderBase* found = FindLoader(newer, loader->m_next_loader, uid))
    {
      VertexLoaderDelete(loader);
      return found;
    }
    loader->m_next_loader = newer;
  }
  return loader;
}

Common::EnumMap<u8*, CPArray::TexCoord7> cached_arraybases;

BitSet8 g_main_vat_dirty;
BitSet8 g_preprocess_vat_dirty;
bool g_bases_dirty;  // Main only
std::array<VertexLoaderBase*, CP_NUM_VAT_REG> g_main_vertex_loaders;
std::array<VertexLoaderBase*, CP_NUM_VAT_REG> g_preprocess_vertex_loaders;
bool g_needs_cp_xf_consistency_check;

void Init()
{
  MarkAllDirty();
  g_main_vertex_loaders.fill(nullptr);
  g_preprocess_vertex_loaders.fill(nullptr);
  VertexLoaderPoolsCreate();
}

void Clear()
{
  for (auto& bucket : s_vertex_loaders)
  {
    auto* loader = static_cast<VertexLoaderBase*>(retro_atomic_exchange_ptr(&bucket, nullptr));
    while (loader)
    {
      VertexLoaderBase* next = loader->m_next_loader;
      VertexLoaderDelete(loader);
      loader = next;
    }
  }
  VertexLoaderPoolsDestroy();
  size_t cursor = 0;
  const void* key;
  uid_table_value* value;
  while ((value = uid_table_next(&s_native_vertex_map, &cursor, &key)))
    NativeVertexFormatDelete(static_cast<NativeVertexFormat*>(value->object));
  uid_table_free(&s_native_vertex_map);
}

void UpdateVertexArrayPointers()
{
  // Anything to update?
  if (!g_bases_dirty) [[likely]]
    return;

  auto& system = Core::System::GetInstance();
  auto& memory = system.GetMemory();

  // Some games such as Burnout 2 can put invalid addresses into
  // the array base registers. (see issue 8591)
  // But the vertex arrays with invalid addresses aren't actually enabled.
  // Note: Only array bases 0 through 11 are used by the Vertex loaders.
  //       12 through 15 are used for loading data into xfmem.
  // We also only update the array base if the vertex description states we are going to use it.
  if (IsIndexed(g_main_cp_state.vtx_desc.low.Position))
  {
    u8* const base_pointer =
        memory.GetPointerForRange(g_main_cp_state.array_bases[CPArray::Position], sizeof(u32));
    if (base_pointer != nullptr)
      cached_arraybases[CPArray::Position] = base_pointer;
  }

  if (IsIndexed(g_main_cp_state.vtx_desc.low.Normal))
  {
    u8* const base_pointer =
        memory.GetPointerForRange(g_main_cp_state.array_bases[CPArray::Normal], sizeof(u32));
    if (base_pointer != nullptr)
      cached_arraybases[CPArray::Normal] = base_pointer;
  }

  for (u8 i = 0; i < g_main_cp_state.vtx_desc.low.Color.Size(); i++)
  {
    if (IsIndexed(g_main_cp_state.vtx_desc.low.Color[i]))
    {
      u8* const base_pointer =
          memory.GetPointerForRange(g_main_cp_state.array_bases[CPArray::Color0 + i], sizeof(u32));
      if (base_pointer != nullptr)
        cached_arraybases[CPArray::Color0 + i] = base_pointer;
    }
  }

  for (u8 i = 0; i < g_main_cp_state.vtx_desc.high.TexCoord.Size(); i++)
  {
    if (IsIndexed(g_main_cp_state.vtx_desc.high.TexCoord[i]))
    {
      u8* const base_pointer = memory.GetPointerForRange(
          g_main_cp_state.array_bases[CPArray::TexCoord0 + i], sizeof(u32));
      if (base_pointer != nullptr)
        cached_arraybases[CPArray::TexCoord0 + i] = base_pointer;
    }
  }

  g_bases_dirty = false;
}

void MarkAllDirty()
{
  g_bases_dirty = true;
  g_main_vat_dirty = BitSet8::AllTrue(8);
  g_preprocess_vat_dirty = BitSet8::AllTrue(8);
  g_needs_cp_xf_consistency_check = true;
}

NativeVertexFormat* GetOrCreateMatchingFormat(const PortableVertexDeclaration& decl)
{
  uid_table_value* value;
  if (!s_native_vertex_map.key_size)
    uid_table_init(&s_native_vertex_map, sizeof(PortableVertexDeclaration));
  value = uid_table_get(&s_native_vertex_map, &decl);
  if (!value)
    return nullptr;
  /* made once: one that failed stays without */
  if (!value->object && !value->pending)
  {
    value->object = g_gfx->CreateNativeVertexFormat(decl);
    value->pending = 1;
  }
  return static_cast<NativeVertexFormat*>(value->object);
}

NativeVertexFormat* GetUberVertexFormat(const PortableVertexDeclaration& decl)
{
  // The padding in the structs can cause the memcmp() in the map to create duplicates.
  // Avoid this by initializing the padding to zero.
  PortableVertexDeclaration new_decl;
  static_assert(std::is_trivially_copyable_v<PortableVertexDeclaration>);
  std::memset(static_cast<void*>(&new_decl), 0, sizeof(new_decl));
  new_decl.stride = decl.stride;

  auto MakeDummyAttribute = [](AttributeFormat& attr, ComponentFormat type, int components,
                               bool integer) {
    attr.type = type;
    attr.components = components;
    attr.offset = 0;
    attr.enable = true;
    attr.integer = integer;
  };
  auto CopyAttribute = [](AttributeFormat& attr, const AttributeFormat& src) {
    attr.type = src.type;
    attr.components = src.components;
    attr.offset = src.offset;
    attr.enable = src.enable;
    attr.integer = src.integer;
  };

  if (decl.position.enable)
    CopyAttribute(new_decl.position, decl.position);
  else
    MakeDummyAttribute(new_decl.position, ComponentFormat::Float, 1, false);
  for (size_t i = 0; i < std::size(new_decl.normals); i++)
  {
    if (decl.normals[i].enable)
      CopyAttribute(new_decl.normals[i], decl.normals[i]);
    else
      MakeDummyAttribute(new_decl.normals[i], ComponentFormat::Float, 1, false);
  }
  for (size_t i = 0; i < std::size(new_decl.colors); i++)
  {
    if (decl.colors[i].enable)
      CopyAttribute(new_decl.colors[i], decl.colors[i]);
    else
      MakeDummyAttribute(new_decl.colors[i], ComponentFormat::UByte, 4, false);
  }
  for (size_t i = 0; i < std::size(new_decl.texcoords); i++)
  {
    if (decl.texcoords[i].enable)
      CopyAttribute(new_decl.texcoords[i], decl.texcoords[i]);
    else
      MakeDummyAttribute(new_decl.texcoords[i], ComponentFormat::Float, 1, false);
  }
  if (decl.posmtx.enable)
    CopyAttribute(new_decl.posmtx, decl.posmtx);
  else
    MakeDummyAttribute(new_decl.posmtx, ComponentFormat::UByte, 1, true);

  return GetOrCreateMatchingFormat(new_decl);
}

namespace detail
{
template <bool IsPreprocess>
VertexLoaderBase* GetOrCreateLoader(int vtx_attr_group)
{
  constexpr CPState* state = IsPreprocess ? &g_preprocess_cp_state : &g_main_cp_state;
  constexpr BitSet8& attr_dirty = IsPreprocess ? g_preprocess_vat_dirty : g_main_vat_dirty;
  constexpr auto& vertex_loaders =
      IsPreprocess ? g_preprocess_vertex_loaders : g_main_vertex_loaders;

  VertexLoaderBase* loader;

  // We are not allowed to create a native vertex format on preprocessing as this is on the wrong
  // thread
  bool check_for_native_format = !IsPreprocess;

  VertexLoaderUID uid(state->vtx_desc, state->vtx_attr[vtx_attr_group]);
  loader = GetOrAddLoader(uid, state->vtx_desc, state->vtx_attr[vtx_attr_group]);
  // Only the main thread sets the native format, so it alone reads it.
  check_for_native_format &= !loader->m_native_vertex_format;
  if (check_for_native_format)
  {
    // search for a cached native vertex format
    loader->m_native_vertex_format = GetOrCreateMatchingFormat(loader->m_native_vtx_decl);
  }
  vertex_loaders[vtx_attr_group] = loader;
  attr_dirty[vtx_attr_group] = false;
  return loader;
}
}  // namespace detail

static void CheckCPConfiguration(int vtx_attr_group)
{
  // Validate that the XF input configuration matches the CP configuration
  u32 num_cp_colors = std::count_if(
      g_main_cp_state.vtx_desc.low.Color.begin(), g_main_cp_state.vtx_desc.low.Color.end(),
      [](auto format) { return format != VertexComponentFormat::NotPresent; });
  u32 num_cp_tex_coords = std::count_if(
      g_main_cp_state.vtx_desc.high.TexCoord.begin(), g_main_cp_state.vtx_desc.high.TexCoord.end(),
      [](auto format) { return format != VertexComponentFormat::NotPresent; });

  u32 num_cp_normals;
  if (g_main_cp_state.vtx_desc.low.Normal == VertexComponentFormat::NotPresent)
    num_cp_normals = 0;
  else if (g_main_cp_state.vtx_attr[vtx_attr_group].g0.NormalElements == NormalComponentCount::NTB)
    num_cp_normals = 3;
  else
    num_cp_normals = 1;

  std::optional<u32> num_xf_normals;
  switch (xfmem.invtxspec.numnormals)
  {
  case NormalCount::None:
    num_xf_normals = 0;
    break;
  case NormalCount::Normal:
    num_xf_normals = 1;
    break;
  case NormalCount::NormalTangentBinormal:
  case NormalCount::Invalid:  // see https://bugs.dolphin-emu.org/issues/13070
    num_xf_normals = 3;
    break;
  }

  if (num_cp_colors != xfmem.invtxspec.numcolors || num_cp_normals != num_xf_normals ||
      num_cp_tex_coords != xfmem.invtxspec.numtextures) [[unlikely]]
  {
    PanicAlertFmt("Mismatched configuration between CP and XF stages - {}/{} colors, {}/{} "
                  "normals, {}/{} texture coordinates. Please report on the issue tracker.\n\n"
                  "VCD: {:08x} {:08x}\nVAT {}: {:08x} {:08x} {:08x}\nXF vertex spec: {:08x}",
                  num_cp_colors, xfmem.invtxspec.numcolors, num_cp_normals,
                  num_xf_normals.has_value() ? fmt::to_string(num_xf_normals.value()) : "invalid",
                  num_cp_tex_coords, xfmem.invtxspec.numtextures, g_main_cp_state.vtx_desc.low.Hex,
                  g_main_cp_state.vtx_desc.high.Hex, vtx_attr_group,
                  g_main_cp_state.vtx_attr[vtx_attr_group].g0.Hex,
                  g_main_cp_state.vtx_attr[vtx_attr_group].g1.Hex,
                  g_main_cp_state.vtx_attr[vtx_attr_group].g2.Hex, xfmem.invtxspec.hex);

    // Don't bail out, though; we can still render something successfully
    // (real hardware seems to hang in this case, though)
  }

  if (g_main_cp_state.matrix_index_a.Hex != xfmem.MatrixIndexA.Hex ||
      g_main_cp_state.matrix_index_b.Hex != xfmem.MatrixIndexB.Hex) [[unlikely]]
  {
    WARN_LOG_FMT(VIDEO,
                 "Mismatched matrix index configuration between CP and XF stages - "
                 "index A: {:08x}/{:08x}, index B {:08x}/{:08x}.",
                 g_main_cp_state.matrix_index_a.Hex, xfmem.MatrixIndexA.Hex,
                 g_main_cp_state.matrix_index_b.Hex, xfmem.MatrixIndexB.Hex);
  }

  if (g_main_cp_state.vtx_attr[vtx_attr_group].g0.PosFormat >= ComponentFormat::InvalidFloat5)
  {
    WARN_LOG_FMT(VIDEO, "Invalid position format {} for VAT {} - {:08x} {:08x} {:08x}",
                 g_main_cp_state.vtx_attr[vtx_attr_group].g0.PosFormat, vtx_attr_group,
                 g_main_cp_state.vtx_attr[vtx_attr_group].g0.Hex,
                 g_main_cp_state.vtx_attr[vtx_attr_group].g1.Hex,
                 g_main_cp_state.vtx_attr[vtx_attr_group].g2.Hex);
  }
  if (g_main_cp_state.vtx_attr[vtx_attr_group].g0.NormalFormat >= ComponentFormat::InvalidFloat5)
  {
    WARN_LOG_FMT(VIDEO, "Invalid normal format {} for VAT {} - {:08x} {:08x} {:08x}",
                 g_main_cp_state.vtx_attr[vtx_attr_group].g0.NormalFormat, vtx_attr_group,
                 g_main_cp_state.vtx_attr[vtx_attr_group].g0.Hex,
                 g_main_cp_state.vtx_attr[vtx_attr_group].g1.Hex,
                 g_main_cp_state.vtx_attr[vtx_attr_group].g2.Hex);
  }
  for (size_t i = 0; i < 8; i++)
  {
    if (g_main_cp_state.vtx_attr[vtx_attr_group].GetTexFormat(i) >= ComponentFormat::InvalidFloat5)
    {
      WARN_LOG_FMT(VIDEO,
                   "Invalid texture coordinate {} format {} for VAT {} - {:08x} {:08x} {:08x}", i,
                   g_main_cp_state.vtx_attr[vtx_attr_group].GetTexFormat(i), vtx_attr_group,
                   g_main_cp_state.vtx_attr[vtx_attr_group].g0.Hex,
                   g_main_cp_state.vtx_attr[vtx_attr_group].g1.Hex,
                   g_main_cp_state.vtx_attr[vtx_attr_group].g2.Hex);
    }
  }
  for (size_t i = 0; i < 2; i++)
  {
    if (g_main_cp_state.vtx_attr[vtx_attr_group].GetColorFormat(i) > ColorFormat::RGBA8888)
    {
      WARN_LOG_FMT(VIDEO, "Invalid color {} format {} for VAT {} - {:08x} {:08x} {:08x}", i,
                   g_main_cp_state.vtx_attr[vtx_attr_group].GetColorFormat(i), vtx_attr_group,
                   g_main_cp_state.vtx_attr[vtx_attr_group].g0.Hex,
                   g_main_cp_state.vtx_attr[vtx_attr_group].g1.Hex,
                   g_main_cp_state.vtx_attr[vtx_attr_group].g2.Hex);
    }
  }
}

static bool CanSplit(OpcodeDecoder::Primitive primitive)
{
  // Splitting is currently only implemented for the easy cases (individual lines/points/triangles)
  switch (primitive)
  {
  case OpcodeDecoder::Primitive::GX_DRAW_QUADS:
  case OpcodeDecoder::Primitive::GX_DRAW_QUADS_2:
  case OpcodeDecoder::Primitive::GX_DRAW_TRIANGLES:
  case OpcodeDecoder::Primitive::GX_DRAW_LINES:
  case OpcodeDecoder::Primitive::GX_DRAW_POINTS:
    return true;
  default:
    return false;
  }
}

template <bool IsPreprocess>
int RunVertices(int vtx_attr_group, OpcodeDecoder::Primitive primitive, int count, const u8* src)
{
  if (count == 0) [[unlikely]]
    return 0;
  ASSERT(count > 0);

  VertexLoaderBase* loader = RefreshLoader<IsPreprocess>(vtx_attr_group);

  int size = count * loader->m_vertex_size;

  if constexpr (!IsPreprocess)
  {
    // Doing early return for the opposite case would be cleaner
    // but triggers a false unreachable code warning in MSVC debug builds.

    if (g_needs_cp_xf_consistency_check) [[unlikely]]
    {
      CheckCPConfiguration(vtx_attr_group);
      g_needs_cp_xf_consistency_check = false;
    }

    // If the native vertex format changed, force a flush.
    if (loader->m_native_vertex_format != s_current_vtx_fmt ||
        loader->m_native_components != g_current_components) [[unlikely]]
    {
      g_vertex_manager->Flush();

      s_current_vtx_fmt = loader->m_native_vertex_format;
      g_current_components = loader->m_native_components;
      auto& system = Core::System::GetInstance();
      auto& vertex_shader_manager = system.GetVertexShaderManager();
      vertex_shader_manager.SetVertexFormat(loader->m_native_components,
                                            loader->m_native_vertex_format->GetVertexDeclaration());
    }

    // CPUCull's performance increase comes from encoding fewer GPU commands, not sending less data
    // Therefore it's only useful to check if culling could remove a flush
    bool can_cpu_cull = g_ActiveConfig.bCPUCull &&
                        primitive < OpcodeDecoder::Primitive::GX_DRAW_LINES &&
                        !g_vertex_manager->HasSendableVertices();

    // if cull mode is CULL_ALL, tell VertexManager to skip triangles and quads.
    // They still need to go through vertex loading, because we need to calculate a zfreeze
    // reference slope.
    const bool cullall = (bpmem.genMode.cull_mode == CullMode::All &&
                          primitive < OpcodeDecoder::Primitive::GX_DRAW_LINES);

    const int stride = loader->m_native_vtx_decl.stride;
    do
    {
      const int max_vertices = 16380;  // Max is 16383, but 16380 is divisible by both 4 and 3
      const int run = CanSplit(primitive) && count > max_vertices ? max_vertices : count;
      count -= run;
      DataReader dst = g_vertex_manager->PrepareForAdditionalData(primitive, run, stride,
                                                                  cullall || can_cpu_cull);

      const int num_loaded = loader->RunVertices(src, dst.GetPointer(), run);
      src += loader->m_vertex_size * max_vertices;

      if (can_cpu_cull && !cullall)
      {
        const bool all_culled =
            g_vertex_manager->AreAllVerticesCulled(loader, primitive, dst.GetPointer(), num_loaded);
        if (!all_culled)
        {
          DataReader new_dst = g_vertex_manager->DisableCullAll(stride);
          memmove(new_dst.GetPointer(), dst.GetPointer(), num_loaded * stride);
          can_cpu_cull = false;
        }
      }

      g_vertex_manager->AddIndices(primitive, num_loaded);
      g_vertex_manager->FlushData(num_loaded, stride);
    } while (count);
  }
  return size;
}

template int RunVertices<false>(int vtx_attr_group, OpcodeDecoder::Primitive primitive, int count,
                                const u8* src);
template int RunVertices<true>(int vtx_attr_group, OpcodeDecoder::Primitive primitive, int count,
                               const u8* src);

NativeVertexFormat* GetCurrentVertexFormat()
{
  return s_current_vtx_fmt;
}
}  // namespace VertexLoaderManager