bit reversal permutation function for power-of-two FFTs More...

#include <MHO_BitReversalPermutation.hh>

Public Member Functions
	MHO_BitReversalPermutation ()

virtual	~MHO_BitReversalPermutation ()

Static Public Member Functions
static void	ComputeBitReversedIndicesBaseTwo (unsigned int N, unsigned int *index_arr)
	Computes bit-reversed indices using Buneman algorithm for input N, must have N = 2^P, with P an integer. More...

static bool	IsPowerOfBase (unsigned int N, unsigned int B)
	Checks if an unsigned integer N is a perfect power of another unsigned integer B. More...

static bool	IsPowerOfTwo (unsigned int N)
	Checks if an unsigned integer is a power of two. More...

static unsigned int	LogBaseB (unsigned int N, unsigned int B)
	Calculates the logarithm base B of N, assuming N is a perfect power of B. More...

static unsigned int	LogBaseTwo (unsigned int N)
	Calculates the logarithm base two of an unsigned integer N using bitwise operations. More...

static unsigned int	NextLowestPowerOfTwo (unsigned int N)
	Calculates the next lowest power of two for a given unsigned integer. More...

template<typename DataType >
static void	PermuteArray (unsigned int N, const unsigned int permutation_index_arr, DataType arr)
	Permutes an array using a given permutation index array (non-strided data access pattern). More...

template<typename DataType >
static void	PermuteArray (unsigned int N, const unsigned int permutation_index_arr, DataType arr, unsigned int stride)
	Permutes a DataType array using an index permutation (strided data access version) More...

template<typename DataType >
static void	PermuteArrayBranchFree (unsigned int N, const unsigned int permutation_index_arr, DataType arr)
	Function PermuteArrayBranchFree non-strided data access pattern branch free (this is actually slower on CPU, but we preserve it here for comparison as this method is used on GPU) More...

template<typename DataType >
static void	PermuteArrayBranchFree (unsigned int N, const unsigned int permutation_index_arr, DataType arr, unsigned int stride)
	Function PermuteArrayBranchFree strided data access version branch free (this is actually slower on CPU, but we preserve it here for comparison as this method is used on GPU) More...

static unsigned int	RaiseBaseToThePower (unsigned int B, unsigned int N)
	Calculates B raised to the power N. More...

static unsigned int	ReverseIndexBits (unsigned int nbits, unsigned int x)
	Reverses the bit indices of a given unsigned integer. More...

static unsigned int	TwoToThePowerOf (unsigned int N)
	Calculates 2 raised to the power of N using bit shifting. More...

Detailed Description

bit reversal permutation function for power-of-two FFTs

Date: Fri Oct 23 12:02:01 2020 -0400

Author: J. Barrett - barre.nosp@m.ttj@.nosp@m.mit.e.nosp@m.du

Constructor & Destructor Documentation

◆ MHO_BitReversalPermutation()

hops::MHO_BitReversalPermutation::MHO_BitReversalPermutation ( )

inline

◆ ~MHO_BitReversalPermutation()

virtual hops::MHO_BitReversalPermutation::~MHO_BitReversalPermutation ( )

inlinevirtual

Member Function Documentation

◆ ComputeBitReversedIndicesBaseTwo()

void hops::MHO_BitReversalPermutation::ComputeBitReversedIndicesBaseTwo	(	unsigned int	N,
		unsigned int *	index_arr
	)

static

Computes bit-reversed indices using Buneman algorithm for input N, must have N = 2^P, with P an integer.

Parameters

N	Input size, must be a power of two
index_arr	Output array to store permutated indices

Note: This is a static function.

◆ IsPowerOfBase()

bool hops::MHO_BitReversalPermutation::IsPowerOfBase	(	unsigned int	N,
		unsigned int	B
	)

static

Checks if an unsigned integer N is a perfect power of another unsigned integer B.

Parameters

N	Input number to check for being a perfect power
B	Base number against which N is checked

Returns: True if N is a perfect power of B, false otherwise

Note: This is a static function.

◆ IsPowerOfTwo()

bool hops::MHO_BitReversalPermutation::IsPowerOfTwo ( unsigned int N )

static

Checks if an unsigned integer is a power of two.

Parameters

N	Input unsigned integer to check.

Returns: True if N is a power of two, false otherwise.

Note: This is a static function.

◆ LogBaseB()

unsigned int hops::MHO_BitReversalPermutation::LogBaseB	(	unsigned int	N,
		unsigned int	B
	)

static

Calculates the logarithm base B of N, assuming N is a perfect power of B.

Parameters

N	Input number for which to calculate the logarithm
B	Base of the logarithm

Returns: Leading power of B that divides N

Note: This is a static function.

◆ LogBaseTwo()

unsigned int hops::MHO_BitReversalPermutation::LogBaseTwo ( unsigned int N )

static

Calculates the logarithm base two of an unsigned integer N using bitwise operations.

Parameters

N	Input unsigned integer for which to calculate the logarithm base two.

Returns: The logarithm base two of N as an unsigned integer.

Note: This is a static function.

◆ NextLowestPowerOfTwo()

unsigned int hops::MHO_BitReversalPermutation::NextLowestPowerOfTwo ( unsigned int N )

static

Calculates the next lowest power of two for a given unsigned integer.

Parameters

N	Input unsigned integer.

Returns: Next lowest power of two as an unsigned integer.

Note: This is a static function.

◆ PermuteArray() [1/2]

template<typename DataType >

static void hops::MHO_BitReversalPermutation::PermuteArray	(	unsigned int	N,
		const unsigned int *	permutation_index_arr,
		DataType *	arr
	)

inlinestatic

Permutes an array using a given permutation index array (non-strided data access pattern).

Template Parameters

DataType Template parameter DataType

Parameters

N	Size of the array and permutation index array.
permutation_index_arr	Array containing permutation indices.
arr	(DataType*)

Note: This is a static function.

◆ PermuteArray() [2/2]

template<typename DataType >

static void hops::MHO_BitReversalPermutation::PermuteArray	(	unsigned int	N,
		const unsigned int *	permutation_index_arr,
		DataType *	arr,
		unsigned int	stride
	)

inlinestatic

Permutes a DataType array using an index permutation (strided data access version)

Template Parameters

DataType Template parameter DataType

Parameters

N	Size of the array and permutation index array.
permutation_index_arr	Array containing the permutation indices.
arr	DataType array to be permuted.
stride	(unsigned int), memory stride between adjacent elements in the array

Note: This is a static function.

◆ PermuteArrayBranchFree() [1/2]

template<typename DataType >

static void hops::MHO_BitReversalPermutation::PermuteArrayBranchFree	(	unsigned int	N,
		const unsigned int *	permutation_index_arr,
		DataType *	arr
	)

inlinestatic

Function PermuteArrayBranchFree non-strided data access pattern branch free (this is actually slower on CPU, but we preserve it here for comparison as this method is used on GPU)

Template Parameters

DataType Template parameter DataType

Parameters

N	(unsigned int)
permutation_index_arr	(const unsigned int*)
arr	(DataType*)

Note: This is a static function.

◆ PermuteArrayBranchFree() [2/2]

template<typename DataType >

static void hops::MHO_BitReversalPermutation::PermuteArrayBranchFree	(	unsigned int	N,
		const unsigned int *	permutation_index_arr,
		DataType *	arr,
		unsigned int	stride
	)

inlinestatic

Function PermuteArrayBranchFree strided data access version branch free (this is actually slower on CPU, but we preserve it here for comparison as this method is used on GPU)

Template Parameters

DataType Template parameter DataType

Parameters

N	(unsigned int)
permutation_index_arr	(const unsigned int*)
arr	(DataType*)
stride	(unsigned int), memory stride between adjacent elements in the array

Note: This is a static function.

◆ RaiseBaseToThePower()

unsigned int hops::MHO_BitReversalPermutation::RaiseBaseToThePower	(	unsigned int	B,
		unsigned int	N
	)

static

Calculates B raised to the power N.

Parameters

B	Base number to be raised
N	Power to which base is raised (N must be >= 0)

Returns: Result of B^N

Note: This is a static function.

◆ ReverseIndexBits()

unsigned int hops::MHO_BitReversalPermutation::ReverseIndexBits	(	unsigned int	nbits,
		unsigned int	x
	)

static

Reverses the bit indices of a given unsigned integer.

Parameters

nbits	Number of bits to consider for reversal.
x	Input unsigned integer whose bit indices are to be reversed.

Returns: The unsigned integer with its bit indices reversed.

Note: This is a static function.

◆ TwoToThePowerOf()

unsigned int hops::MHO_BitReversalPermutation::TwoToThePowerOf ( unsigned int N )

static

Calculates 2 raised to the power of N using bit shifting.

Parameters

N	Input exponent for the calculation (N must be >= 0 and <=31)

Returns: Result of 2^N as an unsigned integer.

Note: This is a static function.

The documentation for this class was generated from the following files:

Public Member Functions

Static Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ MHO_BitReversalPermutation()

◆ ~MHO_BitReversalPermutation()

Member Function Documentation

◆ ComputeBitReversedIndicesBaseTwo()

◆ IsPowerOfBase()

◆ IsPowerOfTwo()

◆ LogBaseB()

◆ LogBaseTwo()

◆ NextLowestPowerOfTwo()

◆ PermuteArray() [1/2]

◆ PermuteArray() [2/2]

◆ PermuteArrayBranchFree() [1/2]

◆ PermuteArrayBranchFree() [2/2]

◆ RaiseBaseToThePower()

◆ ReverseIndexBits()

◆ TwoToThePowerOf()