blob: 1512588003580b8c39ddfcd36e7c8196548db323 [file] [log] [blame]
// Copyright 2021 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef SRC_GRAPHICS_LIB_COMPUTE_RADIX_SORT_PLATFORMS_VK_INCLUDE_RADIX_SORT_PLATFORMS_VK_RADIX_SORT_VK_H_
#define SRC_GRAPHICS_LIB_COMPUTE_RADIX_SORT_PLATFORMS_VK_INCLUDE_RADIX_SORT_PLATFORMS_VK_RADIX_SORT_VK_H_
//
//
//
#include <vulkan/vulkan_core.h>
//
//
//
#include <stdbool.h>
#include <stdint.h>
//
// Radix Sort Vk is a high-performance sorting library for Vulkan 1.2.
//
// The sorting function is both directly and indirectly dispatchable.
//
#ifdef __cplusplus
extern "C" {
#endif
//
// Get a Radix Sort target's Vulkan requirements.
//
// A Radix Sort target is a binary image containing configuration parameters and
// a bundle of SPIR-V modules.
//
// Targets are prebuilt and specific to a particular device vendor, architecture
// and key-val configuration.
//
// A Radix Sort instance can only be created with a VkDevice that is initialized
// with all of the target's required extensions and features.
//
// The `radix_sort_vk_target_get_requirements()` function yields the extensions
// and initialized feature flags required by a Radix Sort target.
//
// These requirements can be merged with other Vulkan library requirements
// before VkDevice creation.
//
// If `.ext_names` is NULL, the `.ext_name_count` member will be initialized
// with the number of extension names required by the target.
//
// Returns `false` if:
//
// * `.ext_names` is NULL and the number of required extensions is
// greater than zero.
// * `.ext_name_count` is less than the number of required extensions.
// * Any of the .pdf, .pdf11 or .pdf12 members are NULL.
//
// Otherwise, returns true.
//
// Acquiring a target's requirements typically requires calling
// `radix_sort_vk_target_get_requirements()` twice:
//
// 1. Discover `.ext_name_count` by invoking with `.ext_names` set to NULL.
// 2. Allocate and/or set the `.ext_names` array member.
// 3. Acquire all requirements by invoking again with `.ext_name_count set to
// the length of the `.ext_names` array.
//
typedef struct radix_sort_vk_target radix_sort_vk_target_t;
typedef struct radix_sort_vk_target_requirements
{
uint32_t ext_name_count;
char const ** ext_names;
VkPhysicalDeviceFeatures * pdf;
VkPhysicalDeviceVulkan11Features * pdf11;
VkPhysicalDeviceVulkan12Features * pdf12;
} radix_sort_vk_target_requirements_t;
bool
radix_sort_vk_target_get_requirements(radix_sort_vk_target_t const * target,
radix_sort_vk_target_requirements_t * requirements);
//
// Create a Radix Sort instance for a target.
//
// Keyval size is implicitly determined by the target.
//
// Returns NULL on failure.
//
typedef struct radix_sort_vk radix_sort_vk_t;
radix_sort_vk_t *
radix_sort_vk_create(VkDevice device,
VkAllocationCallbacks const * ac,
VkPipelineCache pc,
radix_sort_vk_target_t const * target);
//
// Destroy the Radix Sort instance using the same device and allocator used at
// creation.
//
void
radix_sort_vk_destroy(radix_sort_vk_t * rs, //
VkDevice d,
VkAllocationCallbacks const * ac);
//
// Returns the buffer size and alignment requirements when `.count` is the
// maximum expected number of keyvals.
//
// The radix sort implementation is not an in-place sorting algorithm so two
// non-overlapping keyval buffers are required that are at least
// `.keyvals_size`.
//
// The radix sort instance also requires an internal buffer during sorting.
//
// If the indirect dispatch sorting function is used, then an indirect buffer is
// also required.
//
// The alignment requirements for the keyval, internal, and indirect buffers
// must be honored. All alignments are power of 2.
//
// Input:
// count : Maximum number of keyvals
//
// Outputs:
// keyval_size : Size of a single keyval
//
// keyvals_size : Minimum size of the even and odd keyval buffers
// keyvals_alignment : Alignment of each keyval buffer
//
// internal_size : Minimum size of internal buffer
// internal_aligment : Alignment of the internal buffer
//
// indirect_size : Minimum size of indirect buffer
// indirect_aligment : Alignment of the indirect buffer
//
// .keyvals_even/odd
// -----------------
// VK_BUFFER_USAGE_STORAGE_BUFFER_BIT
// VK_BUFFER_USAGE_SHADER_DEVICE_ADDRESS_BIT
//
// .internal
// ---------
// VK_BUFFER_USAGE_STORAGE_BUFFER_BIT
// VK_BUFFER_USAGE_SHADER_DEVICE_ADDRESS_BIT
// VK_BUFFER_USAGE_TRANSFER_DST_BIT ("direct" mode only)
//
// .indirect
// ---------
// VK_BUFFER_USAGE_STORAGE_BUFFER_BIT
// VK_BUFFER_USAGE_SHADER_DEVICE_ADDRESS_BIT
// VK_BUFFER_USAGE_INDIRECT_BUFFER_BIT
//
typedef struct radix_sort_vk_memory_requirements
{
VkDeviceSize keyval_size;
VkDeviceSize keyvals_size;
VkDeviceSize keyvals_alignment;
VkDeviceSize internal_size;
VkDeviceSize internal_alignment;
VkDeviceSize indirect_size;
VkDeviceSize indirect_alignment;
} radix_sort_vk_memory_requirements_t;
void
radix_sort_vk_get_memory_requirements(radix_sort_vk_t const * rs,
uint32_t count,
radix_sort_vk_memory_requirements_t * mr);
//
// Direct dispatch sorting
// -----------------------
//
// Using a key size of `.key_bits`, sort `.count` keyvals found in the
// `.keyvals_even` buffer.
//
// Each internal sorting pass copies the keyvals from one keyvals buffer to the
// other.
//
// If `.count` is <= 1 or `.key_bits` is zero then `radix_sort_vk_sort()`
// immediately returns.
//
// Otherwise, the number of internal sorting passes is determined by
// `.key_bits`.
//
// If an even number of internal sorting passes is required, the sorted keyvals
// will be found in the "even" keyvals buffer. Otherwise, the sorted keyvals
// will be found in the "odd" keyvals buffer.
//
// Which buffer has the sorted keyvals is returned in `keyvals_sorted`.
//
// A keyval's `.key_bits` are the most significant bits of a keyval.
//
// The maximum number of key bits is determined by the keyval size.
//
// The keyval count must be less than (1 << 30) as well as be less than or equal
// to the count used to obtain the the memory requirements.
//
// The info struct's `ext` member must be NULL.
//
// This function appends push constants, dispatch commands, and barriers.
//
// Pipeline barriers should be applied as necessary, both before and after
// invoking this function.
//
// The sort begins with either a TRANSFER/WRITE or a COMPUTE/READ to the
// `.internal` and `.keyvals_even` buffers.
//
// The sort ends with a COMPUTE/WRITE to the `.internal` and `.keyvals_sorted`
// buffers.
//
//
// Direct dispatch sorting using VkDescriptorBufferInfo structures
// ---------------------------------------------------------------
//
typedef struct radix_sort_vk_sort_info
{
void * ext;
uint32_t key_bits;
uint32_t count;
VkDescriptorBufferInfo keyvals_even;
VkDescriptorBufferInfo keyvals_odd;
VkDescriptorBufferInfo internal;
} radix_sort_vk_sort_info_t;
void
radix_sort_vk_sort(radix_sort_vk_t const * rs,
radix_sort_vk_sort_info_t const * info,
VkDevice device,
VkCommandBuffer cb,
VkDescriptorBufferInfo * keyvals_sorted);
//
// Indirect dispatch sorting
// -------------------------
//
// Using a key size of `.key_bits`, at pipeline execution time, load the keyval
// count from `count` buffer and sorts the keyvals in `.keyvals_even` buffer.
//
// Each internal sorting pass copies the keyvals from one keyvals buffer to the
// other.
//
// If `.key_bits` is zero then `radix_sort_vk_sort()` immediately returns.
//
// Otherwise, the number of internal sorting passes is determined by
// `.key_bits`.
//
// If an even number of internal sorting passes is required, the sorted keyvals
// will be found in the "even" keyvals buffer. Otherwise, the sorted keyvals
// will be found in the "odd" keyvals buffer.
//
// Which buffer has the sorted keyvals is returned in `keyvals_sorted`.
//
// A keyval's `.key_bits` are the most significant bits of a keyval.
//
// The keyval count must be less than (1 << 30) as well as be less than or equal
// to the count used to obtain the the memory requirements.
//
// The info struct's `ext` member must be NULL.
//
// This function appends push constants, dispatch commands, and barriers.
//
// Pipeline barriers should be applied as necessary, both before and after
// invoking this function.
//
// The indirect radix sort begins with a COMPUTE/READ from the `count` buffer
// and ends with a COMPUTE/WRITE to the `.internal` and the `.keyvals_sorted`
// buffers.
//
// The `.indirect` buffer must support USAGE_INDIRECT.
//
// The `.count` buffer must be at least 4 bytes and 4-byte aligned.
//
//
// Indirect dispatch sorting using VkDescriptorBufferInfo structures
// -----------------------------------------------------------------
//
typedef struct radix_sort_vk_sort_indirect_info
{
void * ext;
uint32_t key_bits;
VkDescriptorBufferInfo count;
VkDescriptorBufferInfo keyvals_even;
VkDescriptorBufferInfo keyvals_odd;
VkDescriptorBufferInfo internal;
VkDescriptorBufferInfo indirect;
} radix_sort_vk_sort_indirect_info_t;
void
radix_sort_vk_sort_indirect(radix_sort_vk_t const * rs,
radix_sort_vk_sort_indirect_info_t const * info,
VkDevice device,
VkCommandBuffer cb,
VkDescriptorBufferInfo * keyvals_sorted);
//
//
//
#ifdef __cplusplus
}
#endif
//
//
//
#endif // SRC_GRAPHICS_LIB_COMPUTE_RADIX_SORT_PLATFORMS_VK_INCLUDE_RADIX_SORT_PLATFORMS_VK_RADIX_SORT_VK_H_