Skip to main content

transpose_square_blocks_array

binius_field::transpose

Function transpose_square_blocks_array 

Source 
pub fn transpose_square_blocks_array<P: PackedField, const LOG_N: usize, const S: usize>(
    elems: &mut [P; S],
)
Expand description

Transposes square blocks of scalars across a fixed-size array of packed elements, in place.

§Overview

The runtime-sized form in this module computes the same permutation. This form is for a caller whose block dimension and array length are both constants.

Constant sizes let the compiler unroll the butterfly. The whole array then stays in registers, which is what a caller in a hot loop wants.

§Algorithm

A butterfly network over LOG_N rounds, as in Hacker’s Delight, Section 7-3. Round i interleaves element pairs 2^(log_w + i) apart at block granularity 2^i.

§Preconditions

All three are checked at compile time, so a violating instantiation fails to build:

  • The array length must be a power of two.
  • The block dimension must not exceed the base-2 log of the array length.
  • The block dimension must not exceed the base-2 log of the packed width.