| 1 |
|
| 2 |
use strength_reduce::StrengthReducedUsize; |
| 3 |
use num_integer; |
| 4 |
|
| 5 |
fn multiplicative_inverse(a: usize, n: usize) -> usize { |
| 6 |
// we're going to use a modified version extended euclidean algorithm |
| 7 |
// we only need half the output |
| 8 |
|
| 9 |
let mut t = 0; |
| 10 |
let mut t_new = 1; |
| 11 |
|
| 12 |
let mut r = n; |
| 13 |
let mut r_new = a; |
| 14 |
|
| 15 |
while r_new > 0 { |
| 16 |
let quotient = r / r_new; |
| 17 |
|
| 18 |
r = r - quotient * r_new; |
| 19 |
core::mem::swap(&mut r, &mut r_new); |
| 20 |
|
| 21 |
// t might go negative here, so we have to do a checked subtract |
| 22 |
// if it underflows, wrap it around to the other end of the modulo |
| 23 |
// IE, 3 - 4 mod 5 = -1 mod 5 = 4 |
| 24 |
let t_subtract = quotient * t_new; |
| 25 |
t = if t_subtract < t { |
| 26 |
t - t_subtract |
| 27 |
} else { |
| 28 |
n - (t_subtract - t) % n |
| 29 |
}; |
| 30 |
core::mem::swap(&mut t, &mut t_new); |
| 31 |
} |
| 32 |
|
| 33 |
t |
| 34 |
} |
| 35 |
|
| 36 |
/// Transpose the input array in-place. |
| 37 |
/// |
| 38 |
/// Given an input array of size input_width * input_height, representing flattened 2D data stored in row-major order, |
| 39 |
/// transpose the rows and columns of that input array, in-place. |
| 40 |
/// |
| 41 |
/// Despite being in-place, this algorithm requires max(width, height) in scratch space. |
| 42 |
/// |
| 43 |
/// ``` |
| 44 |
/// // row-major order: the rows of our 2D array are contiguous, |
| 45 |
/// // and the columns are strided |
| 46 |
/// let original_array = vec![ 1, 2, 3, |
| 47 |
/// 4, 5, 6]; |
| 48 |
/// let mut input_array = original_array.clone(); |
| 49 |
/// |
| 50 |
/// // Treat our 6-element array as a 2D 3x2 array, and transpose it to a 2x3 array |
| 51 |
/// // transpose_inplace requires max(width, height) scratch space, which is in this case 3 |
| 52 |
/// let mut scratch = vec![0; 3]; |
| 53 |
/// transpose::transpose_inplace(&mut input_array, &mut scratch, 3, 2); |
| 54 |
/// |
| 55 |
/// // The rows have become the columns, and the columns have become the rows |
| 56 |
/// let expected_array = vec![ 1, 4, |
| 57 |
/// 2, 5, |
| 58 |
/// 3, 6]; |
| 59 |
/// assert_eq!(input_array, expected_array); |
| 60 |
/// |
| 61 |
/// // If we transpose it again, we should get our original data back. |
| 62 |
/// transpose::transpose_inplace(&mut input_array, &mut scratch, 2, 3); |
| 63 |
/// assert_eq!(original_array, input_array); |
| 64 |
/// ``` |
| 65 |
/// |
| 66 |
/// # Panics |
| 67 |
/// |
| 68 |
/// Panics if `input.len() != input_width * input_height` or if `scratch.len() != max(width, height)` |
| 69 |
pub fn transpose_inplace<T: Copy>(buffer: &mut [T], scratch: &mut [T], width: usize, height: usize) { |
| 70 |
assert_eq!(width.checked_mul(height), Some(buffer.len())); |
| 71 |
assert_eq!(core::cmp::max(width, height), scratch.len()); |
| 72 |
|
| 73 |
let gcd = StrengthReducedUsize::new(num_integer::gcd(width, height)); |
| 74 |
let a = StrengthReducedUsize::new(height / gcd); |
| 75 |
let b = StrengthReducedUsize::new(width / gcd); |
| 76 |
let a_inverse = multiplicative_inverse(a.get(), b.get()); |
| 77 |
let strength_reduced_height = StrengthReducedUsize::new(height); |
| 78 |
|
| 79 |
let index_fn = |x, y| x + y * width; |
| 80 |
|
| 81 |
if gcd.get() > 1 { |
| 82 |
for x in 0..width { |
| 83 |
let column_offset = (x / b) % strength_reduced_height; |
| 84 |
let wrapping_point = height - column_offset; |
| 85 |
|
| 86 |
// wrapped rotation -- do the "right half" of the array, then the "left half" |
| 87 |
for y in 0..wrapping_point { |
| 88 |
scratch[y] = buffer[index_fn(x, y + column_offset)]; |
| 89 |
} |
| 90 |
for y in wrapping_point..height { |
| 91 |
scratch[y] = buffer[index_fn(x, y + column_offset - height)]; |
| 92 |
} |
| 93 |
|
| 94 |
// copy the data back into the column |
| 95 |
for y in 0..height { |
| 96 |
buffer[index_fn(x, y)] = scratch[y]; |
| 97 |
} |
| 98 |
} |
| 99 |
} |
| 100 |
|
| 101 |
// Permute the rows |
| 102 |
{ |
| 103 |
let row_scratch = &mut scratch[0..width]; |
| 104 |
|
| 105 |
for (y, row) in buffer.chunks_exact_mut(width).enumerate() { |
| 106 |
for x in 0..width { |
| 107 |
let helper_val = if y <= height + x%gcd - gcd.get() { x + y*(width-1) } else { x + y*(width-1) + height }; |
| 108 |
let (helper_div, helper_mod) = StrengthReducedUsize::div_rem(helper_val, gcd); |
| 109 |
|
| 110 |
let gather_x = (a_inverse * helper_div)%b + b.get()*helper_mod; |
| 111 |
row_scratch[x] = row[gather_x]; |
| 112 |
} |
| 113 |
|
| 114 |
row.copy_from_slice(row_scratch); |
| 115 |
} |
| 116 |
} |
| 117 |
|
| 118 |
// Permute the columns |
| 119 |
for x in 0..width { |
| 120 |
let column_offset = x % strength_reduced_height; |
| 121 |
let wrapping_point = height - column_offset; |
| 122 |
|
| 123 |
// wrapped rotation -- do the "right half" of the array, then the "left half" |
| 124 |
for y in 0..wrapping_point { |
| 125 |
scratch[y] = buffer[index_fn(x, y + column_offset)]; |
| 126 |
} |
| 127 |
for y in wrapping_point..height { |
| 128 |
scratch[y] = buffer[index_fn(x, y + column_offset - height)]; |
| 129 |
} |
| 130 |
|
| 131 |
// Copy the data back to the buffer, but shuffle it as we do so |
| 132 |
for y in 0..height { |
| 133 |
let shuffled_y = (y * width - (y / a)) % strength_reduced_height; |
| 134 |
buffer[index_fn(x, y)] = scratch[shuffled_y]; |
| 135 |
} |
| 136 |
} |
| 137 |
} |