AVXCopyGather{T}

A permutation backend which uses AVX-512 intrisics to perform a permutation on 16-, 32-, or 64-bit long integers. The input data is copied several times to fill an AVX register, and then a special operation extracts data from it using a mask. Internally, it stores precomputed masks for the forward and backward permutation.

AbstractBitPermutation{T,A}

Abstract bit permutation supertype.

AdjointBitPermutation{T,P}

Represents the adjoint permutation of type P, where the regular and inverse permutation are swapped.

BenesNetwork{T}

Represents a Beneš network, which is a series of deltaswap operations with specified shifts and masks.

BitPermutation{T,B}

Represents a bit permutation of type T, performed with a PermutationBackend of type B.

BitPermutation{T}([backend_type], p::AbstractVector{Int}; [...])

Construct a BitPermutation{T} from permutation vector p. The backend that actually performs the permutation can be optionally specified by providing a backend_type (<:PermutationBackend). It defaults to the following:

• if AVX-512 instrinsics are available, AVXCopyGather is chosen for T<:Union{UInt16,UInt32,UInt64};
• if BMI2 instrinsics are available, GRPNetwork is chosen for T<:Union{UInt32,UInt64};
• In all other cases, BenesNetwork is used.

Extra keyword arguments get passed to the backend.

See also: BenesNetwork, GRPNetwork, AVXCopyGather.

Bits{T} <: AbstractArray{Bool,1}

A mutable, statically-sized bit vector encoded in the bits in an element of type T <: Integer.

A Bits should behave similarly to a BitVector, but it is slightly faster as the size is known at compile-time to be bitsize(T).

Bits(input::Integer)
Bits{T}(input::Integer)
Bits{T}(input)

Construct a Bits from the bits in input, passed either as a Integer or from an array, or any other generic iterable. It is basically a view into the bits of input, which can then be manipulated using vector-like syntax.

Cycles

Iterator over the cycles of a permutation vector.

GRPNetwork{T}

Represents a GRP network, which is a series of grpswap operations with specified shifts and masks.

PermutationBackend{T}

Abstract type for all bit-permutation backends.

iseven(P::AbstractBitPermutation)

Returns a Bool corresponding to whether or not the parity of the permutation is even.

See also isodd.

isodd(P::AbstractBitPermutation)

Returns a Bool corresponding to whether or not the parity of the permutation is odd.

See also iseven.

sign(P::AbstractBitPermutation)

Returns the sign of the permutation P, +1 (-1) if it is of even (odd) parity.

See also isodd, iseven.

avx_bit_shuffle(x::T, mask::Vec{W,UInt8})

Perform a bit-shuffle of the bits in x using AVX instructions. The mask mask stores the zero-based indices of the locations of each bit in the permuted vector.

bitpermute!(x::AbstractArray{T}, P::AbstractBitPermutation{T})

Perform the permutation of the bits in each element of x using an AbstractBitPermutation in place, i.e. by mutating the array x.

See also bitpermute.

bitpermute(x::Number, p::AbstractBitPermutation)
bitpermute(x::Number, backend::PermutationBackend)
bitpermute(x::AbstractArray{T}, p::AbstractBitPermutation{T})

Perform a permutation the bits in x using an AbstractBitPermutation, using the permutation specified in p. The syntax p(x) can be used as well. Internally, the permutation operations are stored as a PermutationBackend, so the permutation can be called using the backend directly. If the input is an AbstractArray subtype, the permutation is performed element-wise. This can be called as well with p.(x) or bitpermute.(x, p). For cases in which the input array is not needed afterwards, the in-place version bitpermute! is preferred.

See also invbitpermute, bitpermute!.

bitsize(::Type{T})
bitsize(obj::T)

Number of bits in the binary representations of any primitive type T.

cycles(P::AbstractBitPermutation)

Returns an iterator over the cycles of the permutation P.

deltaswap(x::T, m::T, shift::Integer)
deltaswap(x::AbstractVector, m::AbstractVector{Bool}, shift::Integer)

Swaps bits in x selected by mask m with ones to the left by an amount specifield by shift. The AbstractArray version is not optimized to be fast.

grpswap(x::T, m::T, [shift::Integer], [m̄::T])
grpswap(x::AbstractVector, m::AbstractVector{Bool})

Moves the bits in x selected by the mask m to the left, the rest get moved to the right. The shift (number of 0s in m) and inverse mask m̄ can be provided so they don't have to be recomputed. The AbstractArray version is not optimized to be fast.

See also invgrpswap.

invbitpermute!(x::AbstractArray{T}, P::AbstractBitPermutation{T})

Perform the inverse permutation of the bits in each element of x using an AbstractBitPermutation in place, i.e. by mutating the array x.

See also invbitpermute.

invbitpermute(x::Number, p::AbstractBitPermutation)
invbitpermute(x::Number, backend::PermutationBackend)
invbitpermute(x::AbstractArray{T}, P::AbstractBitPermutation{T})

Perform the inverse permutation of the bits in x using an AbstractBitPermutation, using the inverse of the permutation specified in p. The syntax p'(x) can be used as well. Internally, the permutation operations are stored as a PermutationBackend, so the permutation can be called using the backend directly. If the input is an AbstractArray subtype, the inverse permutation is performed element-wise. This can be called as well with p'.(x) or invbitpermute.(x, p). For cases in which the input array is not needed afterwards, the in-place version invbitpermute! is preferred.

See also bitpermute, invbitpermute!.

invgrpswap(x::T, m::T, [shift::Integer], [m̄::T])
invgrpswap(x::AbstractVector, m::AbstractVector{Bool})

Performs the inverse operation of grpswap.

See also grpswap.

order(P::AbstractBitPermutation)

Return the order of the permutation P, i.e. the amount of times you have to apply the permutation to obtain the trivial permutation.

See also isodd, iseven to compute the parity.

pdep(x::T, m::T)

Place first bits of x at locations specified by m in the return value. Opposite operation of pdep.

See also pext.

pext(x::T, m::T)

Select bits of x with m and place them at the beginning of the return value. Opposite operation of pdep.

See also pdep.

shift_safe(::Type{T}, s::Integer)

Changes the shifting amount for bitshifts to guarantee to the compiler that the shift amount will not exceed bitsize(T). Because bit shifting behaves slighly differently in Julia vs. LLVM, this help the compiler emit less code.

See also: https://github.com/JuliaLang/julia/issues/30674.

use_avx512()

Used to set USE_AVX512 flag at precompilation.

use_bmi2()

Used to set USE_BMI2 flag at precompilation.