microsoft/qdk
Publicmirrored fromhttps://github.com/microsoft/qdkAvailable
source/paulimer/src/bits/tiny_matrix.rs
116lines · modecode
| 1 | // Copyright (c) Microsoft Corporation. |
| 2 | // Licensed under the MIT License. |
| 3 | |
| 4 | // Tiny bitmatrix with RREF, not heap allocation, compile-time known sizes |
| 5 | |
| 6 | use super::BitMatrix; |
| 7 | |
| 8 | #[must_use] |
| 9 | pub fn tiny_matrix_from_bitmatrix<const ROW_COUNT: usize>(matrix: &BitMatrix) -> [u64; ROW_COUNT] { |
| 10 | let mut tiny_matrix = [0u64; ROW_COUNT]; |
| 11 | let column_count = matrix.columncount(); |
| 12 | for row_id in 0..ROW_COUNT { |
| 13 | for column_id in 0..column_count { |
| 14 | if matrix[(row_id, column_id)] { |
| 15 | tiny_matrix[row_id] ^= 1 << column_id; |
| 16 | } |
| 17 | } |
| 18 | } |
| 19 | tiny_matrix |
| 20 | } |
| 21 | |
| 22 | pub fn xor_tiny_column<const NUM_ROWS: usize>( |
| 23 | tiny_matrix: &mut [u64; NUM_ROWS], |
| 24 | column_index: usize, |
| 25 | column: u64, |
| 26 | ) { |
| 27 | let mask = 1 << column_index; |
| 28 | for (row_id, row) in tiny_matrix.iter_mut().enumerate() { |
| 29 | if column & (1 << row_id) != 0 { |
| 30 | *row ^= mask; |
| 31 | } |
| 32 | } |
| 33 | } |
| 34 | |
| 35 | #[must_use] |
| 36 | pub fn get_tiny_column<const NUM_ROWS: usize>( |
| 37 | tiny_matrix: &[u64; NUM_ROWS], |
| 38 | column_index: usize, |
| 39 | ) -> u64 { |
| 40 | let mask = 1 << column_index; |
| 41 | let mut column = 0u64; |
| 42 | for (row_id, row) in tiny_matrix.iter().enumerate() { |
| 43 | if *row & mask != 0 { |
| 44 | column ^= 1u64 << row_id; |
| 45 | } |
| 46 | } |
| 47 | column |
| 48 | } |
| 49 | |
| 50 | fn tiny_pivot_row<const NUM_ROWS: usize>( |
| 51 | tiny_matrix: &mut [u64; NUM_ROWS], |
| 52 | column_id: usize, |
| 53 | start_row: usize, |
| 54 | ) -> usize { |
| 55 | let column_mask = 1u64 << column_id; |
| 56 | for (row_id, row) in tiny_matrix.iter().enumerate().skip(start_row) { |
| 57 | if *row & column_mask != 0 { |
| 58 | return row_id; |
| 59 | } |
| 60 | } |
| 61 | NUM_ROWS |
| 62 | } |
| 63 | |
| 64 | fn tiny_reduce_forward<const NUM_ROWS: usize>( |
| 65 | tiny_matrix: &mut [u64; NUM_ROWS], |
| 66 | column_id: usize, |
| 67 | start_row: usize, |
| 68 | ) -> usize { |
| 69 | let column_mask = 1u64 << column_id; |
| 70 | let reducing_row = tiny_matrix[start_row]; |
| 71 | for row in tiny_matrix.iter_mut().skip(start_row + 1) { |
| 72 | if *row & column_mask != 0 { |
| 73 | *row ^= reducing_row; |
| 74 | } |
| 75 | } |
| 76 | NUM_ROWS |
| 77 | } |
| 78 | |
| 79 | fn tiny_reduce_backward<const NUM_ROWS: usize>( |
| 80 | tiny_matrix: &mut [u64; NUM_ROWS], |
| 81 | column_id: usize, |
| 82 | end_row: usize, |
| 83 | ) -> usize { |
| 84 | let column_mask = 1u64 << column_id; |
| 85 | let reducing_row = tiny_matrix[end_row]; |
| 86 | for row in tiny_matrix.iter_mut().take(end_row) { |
| 87 | if *row & column_mask != 0 { |
| 88 | *row ^= reducing_row; |
| 89 | } |
| 90 | } |
| 91 | NUM_ROWS |
| 92 | } |
| 93 | |
| 94 | pub fn tiny_matrix_rref<const NUM_ROWS: usize, const NUM_COLUMNS: usize>( |
| 95 | tiny_matrix: &mut [u64; NUM_ROWS], |
| 96 | ) -> usize { |
| 97 | let mut rank_profile = [0usize; 64]; |
| 98 | let mut column_id = 0; |
| 99 | let mut current_row_id = 0; |
| 100 | let mut rank = 0; |
| 101 | while column_id < NUM_COLUMNS { |
| 102 | let pivot_row = tiny_pivot_row(tiny_matrix, column_id, current_row_id); |
| 103 | if pivot_row != NUM_ROWS { |
| 104 | tiny_matrix.swap(current_row_id, pivot_row); |
| 105 | tiny_reduce_forward(tiny_matrix, column_id, current_row_id); |
| 106 | rank_profile[current_row_id] = column_id; |
| 107 | current_row_id += 1; |
| 108 | rank += 1; |
| 109 | } |
| 110 | column_id += 1; |
| 111 | } |
| 112 | for (row_id, column_id) in rank_profile.iter().enumerate().take(rank) { |
| 113 | tiny_reduce_backward(tiny_matrix, *column_id, row_id); |
| 114 | } |
| 115 | rank |
| 116 | } |
| 117 | |