p3_matrix/
bitrev.rs

1use p3_util::{log2_strict_usize, reverse_bits_len};
2
3use crate::dense::{DenseMatrix, DenseStorage, RowMajorMatrix};
4use crate::row_index_mapped::{RowIndexMap, RowIndexMappedView};
5use crate::util::reverse_matrix_index_bits;
6use crate::Matrix;
7
8/// A matrix that is possibly bit-reversed, and can easily switch
9/// between orderings. Pretty much just either `RowMajorMatrix` or
10/// `BitReversedMatrixView<RowMajorMatrix>`.
11pub trait BitReversableMatrix<T: Send + Sync>: Matrix<T> {
12    type BitRev: BitReversableMatrix<T>;
13    fn bit_reverse_rows(self) -> Self::BitRev;
14}
15
16#[derive(Debug)]
17pub struct BitReversalPerm {
18    log_height: usize,
19}
20
21impl BitReversalPerm {
22    pub fn new_view<T: Send + Sync, Inner: Matrix<T>>(
23        inner: Inner,
24    ) -> BitReversedMatrixView<Inner> {
25        RowIndexMappedView {
26            index_map: Self {
27                log_height: log2_strict_usize(inner.height()),
28            },
29            inner,
30        }
31    }
32}
33
34impl RowIndexMap for BitReversalPerm {
35    fn height(&self) -> usize {
36        1 << self.log_height
37    }
38    fn map_row_index(&self, r: usize) -> usize {
39        reverse_bits_len(r, self.log_height)
40    }
41    // This might not be more efficient than the lazy generic impl
42    // if we have a nested view.
43    fn to_row_major_matrix<T: Clone + Send + Sync, Inner: Matrix<T>>(
44        &self,
45        inner: Inner,
46    ) -> RowMajorMatrix<T> {
47        let mut inner = inner.to_row_major_matrix();
48        reverse_matrix_index_bits(&mut inner);
49        inner
50    }
51}
52
53pub type BitReversedMatrixView<Inner> = RowIndexMappedView<BitReversalPerm, Inner>;
54
55impl<T: Clone + Send + Sync, S: DenseStorage<T>> BitReversableMatrix<T>
56    for BitReversedMatrixView<DenseMatrix<T, S>>
57{
58    type BitRev = DenseMatrix<T, S>;
59    fn bit_reverse_rows(self) -> Self::BitRev {
60        self.inner
61    }
62}
63
64impl<T: Clone + Send + Sync, S: DenseStorage<T>> BitReversableMatrix<T> for DenseMatrix<T, S> {
65    type BitRev = BitReversedMatrixView<DenseMatrix<T, S>>;
66    fn bit_reverse_rows(self) -> Self::BitRev {
67        BitReversalPerm::new_view(self)
68    }
69}
p3_matrix/bitrev.rs

p3_matrix/
bitrev.rs
