Matrices using a bitsliced representation. More...
Go to the source code of this file.
Data Structures | |
struct | mzd_slice_t |
Dense matrices over \(\mathbb{F}_{2^e}\) represented as slices of matrices over \(\mathbb{F}_2\). More... | |
Defines | |
#define | __M4RIE_MAX_KARATSUBA_DEGREE 8 |
#define | mzd_slice_sub mzd_slice_add |
\( C = A + B\). | |
#define | _mzd_slice_sub _mzd_slice_add |
\( C = A + B\). | |
Functions | |
static mzd_slice_t * | mzd_slice_init (const gf2e *ff, const rci_t m, const rci_t n) |
Create a new matrix of dimension \( m \times n\) over ff. | |
void | mzd_slice_set_ui (mzd_slice_t *A, word value) |
Return diagonal matrix with value on the diagonal. | |
static mzd_slice_t * | _mzd_slice_adapt_depth (mzd_slice_t *A, const unsigned int new_depth) |
Extend or truncate the depth of A to depth new_depth. | |
static void | mzd_slice_free (mzd_slice_t *A) |
Free a matrix created with mzd_slice_init(). | |
static mzd_slice_t * | mzd_slice_concat (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) |
Concatenate B to A and write the result to C. | |
static mzd_slice_t * | mzd_slice_stack (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) |
Stack A on top of B and write the result to C. | |
static mzd_slice_t * | mzd_slice_submatrix (mzd_slice_t *S, const mzd_slice_t *A, const size_t lowr, const size_t lowc, const size_t highr, const size_t highc) |
Copy a submatrix. | |
static mzd_slice_t * | mzd_slice_init_window (const mzd_slice_t *A, const size_t lowr, const size_t lowc, const size_t highr, const size_t highc) |
Create a window/view into the matrix M. | |
static void | mzd_slice_free_window (mzd_slice_t *A) |
Free a matrix window created with mzd_slice_init_window(). | |
static mzd_slice_t * | _mzd_slice_add (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) |
\( C = A + B\). | |
static mzd_slice_t * | mzd_slice_add (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) |
\( C = A + B\). | |
mzd_slice_t * | _mzd_slice_mul_naive (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) |
\( C = A \cdot B \) using quadratic polynomial multiplication with matrix coefficients. | |
mzd_slice_t * | _mzd_slice_mul_karatsuba2 (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) |
\( C = A \cdot B \) over \(\mathbb{F}_{2^2}\) using 3 multiplications over \(\mathbb{F}_2\) and 2 temporary \(\mathbb{F}_2\) matrices.. | |
mzd_slice_t * | _mzd_slice_mul_karatsuba3 (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) |
\( C = A \cdot B \) over \(\mathbb{F}_{2^3}\) using 6 multiplications over \(\mathbb{F}_2\) and 3 temporary \(\mathbb{F}_2\) matrices.. | |
mzd_slice_t * | _mzd_slice_mul_karatsuba4 (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) |
\( C = A \cdot B \) over \(\mathbb{F}_{2^4}\) using 9 multiplications over \(\mathbb{F}_2\) and 3 temporary \(\mathbb{F}_2\) matrices.. | |
mzd_slice_t * | _mzd_slice_mul_karatsuba5 (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) |
\( C = A \cdot B \) over \(\mathbb{F}_{2^5}\) using 13 multiplications over \(\mathbb{F}_2\) and 3 temporary \(\mathbb{F}_2\) matrices.. | |
mzd_slice_t * | _mzd_slice_mul_karatsuba6 (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) |
\( C = A \cdot B \) over \(\mathbb{F}_{2^6}\) using 17 multiplications over \(\mathbb{F}_2\) and 3 temporary \(\mathbb{F}_2\) matrices. | |
mzd_slice_t * | _mzd_slice_mul_karatsuba7 (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) |
\( C = A \cdot B \) over \(\mathbb{F}_{2^7}\) using 22 multiplications over \(\mathbb{F}_2\) and 3 temporary \(\mathbb{F}_2\) matrices. | |
mzd_slice_t * | _mzd_slice_mul_karatsuba8 (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) |
\( C = A \cdot B \) over \(\mathbb{F}_{2^8}\) using 27 multiplications over \(\mathbb{F}_2\) and 15 temporary \(\mathbb{F}_2\) matrices. | |
static mzd_slice_t * | _mzd_slice_mul_karatsuba (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) |
\( C = C + A \cdot B \) using Karatsuba multiplication of polynomials over matrices over \(\mathbb{F}_2\). | |
static mzd_slice_t * | mzd_slice_mul_karatsuba (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) |
\( C = A \cdot B \) using Karatsuba multiplication of polynomials over matrices over \(\mathbb{F}_2\). | |
static mzd_slice_t * | mzd_slice_addmul_karatsuba (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) |
\( C = C + A \cdot B\) using Karatsuba multiplication of polynomials over matrices over \(\mathbb{F}_2\). | |
mzd_slice_t * | mzd_slice_mul_scalar (mzd_slice_t *C, const word a, const mzd_slice_t *B) |
\( C = a \cdot B \). | |
mzd_slice_t * | mzd_slice_addmul_scalar (mzd_slice_t *C, const word a, const mzd_slice_t *B) |
\( C += a \cdot B \). | |
static mzd_slice_t * | mzd_slice_mul (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) |
\( C = A \cdot B \). | |
static mzd_slice_t * | mzd_slice_addmul (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) |
\( C = C + A \cdot B \). | |
static void | mzd_slice_randomize (mzd_slice_t *A) |
Fill matrix A with random elements. | |
static mzd_slice_t * | mzd_slice_copy (mzd_slice_t *B, const mzd_slice_t *A) |
Copy matrix A to B. | |
static word | mzd_slice_read_elem (const mzd_slice_t *A, const rci_t row, const rci_t col) |
Get the element at position (row,col) from the matrix A. | |
static void | mzd_slice_add_elem (mzd_slice_t *A, const rci_t row, const rci_t col, word elem) |
At the element elem to the element at position (row,col) in the matrix A. | |
static void | mzd_slice_write_elem (mzd_slice_t *A, const rci_t row, const rci_t col, word elem) |
Write the element elem to the position (row,col) in the matrix A. | |
static int | mzd_slice_cmp (mzd_slice_t *A, mzd_slice_t *B) |
Return -1,0,1 if if A < B, A == B or A > B respectively. | |
static int | mzd_slice_is_zero (const mzd_slice_t *A) |
Zero test for matrix. | |
static void | mzd_slice_row_swap (mzd_slice_t *A, const rci_t rowa, const rci_t rowb) |
Swap the two rows rowa and rowb. | |
static void | mzd_slice_copy_row (mzd_slice_t *B, size_t i, const mzd_slice_t *A, size_t j) |
copy row j from A to row i from B. | |
static void | mzd_slice_col_swap (mzd_slice_t *A, const rci_t cola, const rci_t colb) |
Swap the two columns cola and colb. | |
static void | mzd_slice_col_swap_in_rows (mzd_slice_t *A, const rci_t cola, const rci_t colb, const rci_t start_row, rci_t stop_row) |
Swap the two columns cola and colb but only between start_row and stop_row. | |
static void | mzd_slice_row_add (mzd_slice_t *A, const rci_t sourcerow, const rci_t destrow) |
Add the rows sourcerow and destrow and stores the total in the row destrow. | |
static void | mzd_slice_row_clear_offset (mzd_slice_t *A, const rci_t row, const rci_t coloffset) |
Clear the given row, but only begins at the column coloffset. | |
void | mzd_slice_print (const mzd_slice_t *A) |
Print a matrix to stdout. | |
static void | _mzd_slice_compress_l (mzd_slice_t *A, const rci_t r1, const rci_t n1, const rci_t r2) |
Move the submatrix L of rank r2 starting at column n1 to the left to column r1. |
Matrices using a bitsliced representation.
Matrices over \(\mathbb{F}_{2^e}\) can be represented as polynomials with matrix coefficients where the matrices are in \(\mathbb{F}_2\).
In this file, matrices over \(\mathbb{F}_{2^e}\) are implemented as \(e\) slices of matrices over \(\mathbb{F}_2\) where each slice holds the coefficients of one degree when viewing elements of \(\mathbb{F}_{2^e}\) as polynomials over \(\mathbb{F}_2\).
#define __M4RIE_MAX_KARATSUBA_DEGREE 8 |
Degree up to which Karatsuba multiplication and slicing/cling is implemented.
static mzd_slice_t* _mzd_slice_adapt_depth | ( | mzd_slice_t * | A, |
const unsigned int | new_depth | ||
) | [inline, static] |
Extend or truncate the depth of A to depth new_depth.
We may think of mzd_slice_t as polynomials over matrices over \(\mathbb{F}_2\). This function then truncates/extends these polynomials to degree new_depth-1. In case of extension, all newly created coefficients are zero, hence the mathematical content of A is not changed. In case of truncation higher degree terms are simply deleted and A's mathematical content modified.
A | Matrix, modifed in place. |
new_depth | Integer >= mzd_slice_t::finite_field::degree. |
static void _mzd_slice_compress_l | ( | mzd_slice_t * | A, |
const rci_t | r1, | ||
const rci_t | n1, | ||
const rci_t | r2 | ||
) | [inline, static] |
Move the submatrix L of rank r2 starting at column n1 to the left to column r1.
A | Matrix |
r1 | Integer < n1 |
n1 | Integer > r1 |
r2 | Integer <= A->ncols - n1 |
static int mzd_slice_cmp | ( | mzd_slice_t * | A, |
mzd_slice_t * | B | ||
) | [inline, static] |
Return -1,0,1 if if A < B, A == B or A > B respectively.
A | Matrix. |
B | Matrix. |
static void mzd_slice_col_swap_in_rows | ( | mzd_slice_t * | A, |
const rci_t | cola, | ||
const rci_t | colb, | ||
const rci_t | start_row, | ||
rci_t | stop_row | ||
) | [inline, static] |
Swap the two columns cola and colb but only between start_row and stop_row.
A | Matrix. |
cola | Column index. |
colb | Column index. |
start_row | Row index. |
stop_row | Row index (exclusive). |
static int mzd_slice_is_zero | ( | const mzd_slice_t * | A | ) | [inline, static] |
Zero test for matrix.
A | Input matrix. |