#[inline] pub fn transpose8x8_u64(n: u64) -> u64 { let m = (n ^ (n >> 7)) & 0x00aa00aa00aa00aa; let n = n ^ m ^ (m << 7); let m = (n ^ (n >> 14)) & 0x0000cccc0000cccc; let n = n ^ m ^ (m << 14); let m = (n ^ (n >> 28)) & 0x00000000f0f0f0f0; n ^ m ^ (m << 28) } pub fn transpose8x8(mut a: [u8; 8]) -> [u8; 8] { let mut j: usize = 4; let mut k; let mut m: u8 = 0x0F; let mut t: u8; while j != 0 { k = 0; while k < 8 { t = (a[k] ^ (a[k | j] >> j)) & m; a[k] ^= t; a[k | j] ^= t << j; k = ((k | j) + 1) & !j; } j >>= 1; m ^= m << j; } a } pub fn transpose16x16(mut a: [u16; 16]) -> [u16; 16] { let mut j: usize = 8; let mut k; let mut m: u16 = 0x00FF; let mut t: u16; while j != 0 { k = 0; while k < 16 { t = (a[k] ^ (a[k | j] >> j)) & m; a[k] ^= t; a[k | j] ^= t << j; k = ((k | j) + 1) & !j; } j >>= 1; m ^= m << j; } a } pub fn transpose32x32(mut a: [u32; 32]) -> [u32; 32] { let mut j: usize = 16; let mut k; let mut m: u32 = 0x0000FFFF; let mut t: u32; while j != 0 { k = 0; while k < 32 { t = (a[k] ^ (a[k | j] >> j)) & m; a[k] ^= t; a[k | j] ^= t << j; k = ((k | j) + 1) & !j; } j >>= 1; m ^= m << j; } a } pub fn transpose64x64(mut a: [u64; 64]) -> [u64; 64] { let mut j: usize = 32; let mut k; let mut m: u64 = 0x00000000FFFFFFFF; let mut t: u64; while j != 0 { k = 0; while k < 64 { t = (a[k] ^ (a[k | j] >> j)) & m; a[k] ^= t; a[k | j] ^= t << j; k = ((k | j) + 1) & !j; } j >>= 1; m ^= m << j; } a } pub fn transpose128x128(mut a: [u128; 128]) -> [u128; 128] { let mut j: usize = 64; let mut k; let mut m: u128 = 0x0000000000000000FFFFFFFFFFFFFFFF; let mut t: u128; while j != 0 { k = 0; while k < 128 { t = (a[k] ^ (a[k | j] >> j)) & m; a[k] ^= t; a[k | j] ^= t << j; k = ((k | j) + 1) & !j; } j >>= 1; m ^= m << j; } a } #[test] fn test_transpose8x8_u64() { assert_eq!( transpose8x8_u64(0x123456789abcdef0_u64), 0x0f3355ff1e66aa00_u64 ); } #[test] fn test_transpose8x8() { let a: [u8; 8] = [ 0b00001000, // 0b10001000, // 0b10111110, // 0b10001000, // 0b10001000, // 0b11001000, // 0b10001000, // 0b00010000, // ]; let b: [u8; 8] = [ 0b01111110, // 0b00000100, // 0b00100000, // 0b00100001, // 0b11111110, // 0b00100000, // 0b00100000, // 0b00000000, // ]; assert_eq!(transpose8x8(a), b); } #[test] fn test_transpose16x16() { let a: [u16; 16] = [ 0b0000100000001000, // 0b1000100010001000, // 0b1011111010111110, // 0b1000100010001000, // 0b1000100010001000, // 0b1100100011001000, // 0b1000100010001000, // 0b0001000000010000, // 0b0000100000001000, // 0b1000100010001000, // 0b1011111010111110, // 0b1000100010001000, // 0b1000100010001000, // 0b1100100011001000, // 0b1000100010001000, // 0b0001000000010000, // ]; assert_ne!(transpose16x16(a), a); assert_eq!(transpose16x16(transpose16x16(a)), a); } #[test] fn test_transpose32x32() { let a: [u32; 32] = [ 0b00001000000010000000100000001000, // 0b10001000100010001000100010001000, // 0b10111110101111101011111010111110, // 0b10001000100010001000100010001000, // 0b10001000100010001000100010001000, // 0b11001000110010001100100011001000, // 0b10001000100010001000100010001000, // 0b00010000000100000001000000010000, // 0b00001000000010000000100000001000, // 0b10001000100010001000100010001000, // 0b10111110101111101011111010111110, // 0b10001000100010001000100010001000, // 0b10001000100010001000100010001000, // 0b11001000110010001100100011001000, // 0b10001000100010001000100010001000, // 0b00010000000100000001000000010000, // 0b00001000000010000000100000001000, // 0b10001000100010001000100010001000, // 0b10111110101111101011111010111110, // 0b10001000100010001000100010001000, // 0b10001000100010001000100010001000, // 0b11001000110010001100100011001000, // 0b10001000100010001000100010001000, // 0b00010000000100000001000000010000, // 0b00001000000010000000100000001000, // 0b10001000100010001000100010001000, // 0b10111110101111101011111010111110, // 0b10001000100010001000100010001000, // 0b10001000100010001000100010001000, // 0b11001000110010001100100011001000, // 0b10001000100010001000100010001000, // 0b00010000000100000001000000010000, // ]; assert_ne!(transpose32x32(a), a); assert_eq!(transpose32x32(transpose32x32(a)), a); } #[test] fn test_transpose64x64() { let a: [u64; 64] = [ 0b0000100000001000000010000000100000001000000010000000100000001000, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b1011111010111110101111101011111010111110101111101011111010111110, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b1100100011001000110010001100100011001000110010001100100011001000, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b0001000000010000000100000001000000010000000100000001000000010000, // 0b0000100000001000000010000000100000001000000010000000100000001000, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b1011111010111110101111101011111010111110101111101011111010111110, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b1100100011001000110010001100100011001000110010001100100011001000, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b0001000000010000000100000001000000010000000100000001000000010000, // 0b0000100000001000000010000000100000001000000010000000100000001000, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b1011111010111110101111101011111010111110101111101011111010111110, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b1100100011001000110010001100100011001000110010001100100011001000, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b0001000000010000000100000001000000010000000100000001000000010000, // 0b0000100000001000000010000000100000001000000010000000100000001000, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b1011111010111110101111101011111010111110101111101011111010111110, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b1100100011001000110010001100100011001000110010001100100011001000, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b0001000000010000000100000001000000010000000100000001000000010000, // 0b0000100000001000000010000000100000001000000010000000100000001000, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b1011111010111110101111101011111010111110101111101011111010111110, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b1100100011001000110010001100100011001000110010001100100011001000, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b0001000000010000000100000001000000010000000100000001000000010000, // 0b0000100000001000000010000000100000001000000010000000100000001000, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b1011111010111110101111101011111010111110101111101011111010111110, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b1100100011001000110010001100100011001000110010001100100011001000, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b0001000000010000000100000001000000010000000100000001000000010000, // 0b0000100000001000000010000000100000001000000010000000100000001000, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b1011111010111110101111101011111010111110101111101011111010111110, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b1100100011001000110010001100100011001000110010001100100011001000, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b0001000000010000000100000001000000010000000100000001000000010000, // 0b0000100000001000000010000000100000001000000010000000100000001000, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b1011111010111110101111101011111010111110101111101011111010111110, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b1100100011001000110010001100100011001000110010001100100011001000, // 0b1000100010001000100010001000100010001000100010001000100010001000, // 0b0001000000010000000100000001000000010000000100000001000000010000, // ]; assert_ne!(transpose64x64(a), a); assert_eq!(transpose64x64(transpose64x64(a)), a); } #[test] fn test_transpose128x128() { let a: [u128; 128] = [ 0b00001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b11001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b00010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000, 0b00001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b11001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b00010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000, 0b00001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b11001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b00010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000, 0b00001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b11001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b00010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000, 0b00001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b11001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b00010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000, 0b00001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b11001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b00010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000, 0b00001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b11001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b00010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000, 0b00001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b11001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b00010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000, 0b00001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b11001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b00010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000, 0b00001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b11001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b00010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000, 0b00001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b11001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b00010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000, 0b00001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b11001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b00010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000, 0b00001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b11001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b00010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000, 0b00001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b11001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b00010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000, 0b00001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b11001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b00010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000, 0b00001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110101111101011111010111110, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b11001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000110010001100100011001000, 0b10001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000, 0b00010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000, ]; assert_ne!(transpose128x128(a), a); assert_eq!(transpose128x128(transpose128x128(a)), a); }