M4RIE 0.20111004
Loading...
Searching...
No Matches
mzd_slice.h
Go to the documentation of this file.
1
16#ifndef M4RIE_MZD_SLICE
17#define M4RIE_MZD_SLICE
18
19/******************************************************************************
20*
21* M4RIE: Linear Algebra over GF(2^e)
22*
23* Copyright (C) 2010,2011 Martin Albrecht <martinralbrecht@googlemail.com>
24*
25* Distributed under the terms of the GNU General Public License (GEL)
26* version 2 or higher.
27*
28* This code is distributed in the hope that it will be useful,
29* but WITHOUT ANY WARRANTY; without even the implied warranty of
30* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
31* General Public License for more details.
32*
33* The full text of the GPL is available at:
34*
35* http://www.gnu.org/licenses/
36******************************************************************************/
37
38#include <m4ri/m4ri.h>
39#include <m4rie/mzd_poly.h>
40#include <m4rie/mzed.h>
41#include <m4rie/blm.h>
42
56typedef struct {
57 mzd_t *x[16];
58 rci_t nrows;
59 rci_t ncols;
60 unsigned int depth;
64
65
78static inline mzd_slice_t *mzd_slice_init(const gf2e *ff, const rci_t m, const rci_t n) {
79 mzd_slice_t *A = (mzd_slice_t*)m4ri_mm_malloc(sizeof(mzd_slice_t));
80
81 A->finite_field = ff;
82 A->nrows = m;
83 A->ncols = n;
84 A->depth = ff->degree;
85
86 for(unsigned int i=0; i<A->depth; i++)
87 A->x[i] = mzd_init(m,n);
88 return A;
89}
90
103void mzd_slice_set_ui(mzd_slice_t *A, word value);
104
119static inline mzd_slice_t *_mzd_slice_adapt_depth(mzd_slice_t *A, const unsigned int new_depth) {
120 assert(A->finite_field->degree <= new_depth);
121
122 if (new_depth < A->depth) {
123 for(unsigned int i=new_depth; i<A->depth; i++) {
124 mzd_free(A->x[i]);
125 A->x[i] = NULL;
126 }
127 } else {
128 for(unsigned int i=A->depth; i<new_depth; i++) {
129 A->x[i] = mzd_init(A->nrows,A->ncols);
130 }
131 }
132 A->depth = new_depth;
133 return A;
134}
135
136
145static inline void mzd_slice_free(mzd_slice_t *A) {
146 for(unsigned int i=0; i<A->depth; i++)
147 mzd_free(A->x[i]);
148#if __M4RI_USE_MM_MALLOC
149 _mm_free(A);
150#else
151 free(A);
152#endif
153}
154
164static inline mzd_slice_t *mzd_slice_copy(mzd_slice_t *B, const mzd_slice_t *A) {
165 if(B == NULL)
166 B = mzd_slice_init(A->finite_field, A->nrows, A->ncols);
167
168 for(int i=0; i<A->depth; i++) {
169 mzd_copy(B->x[i],A->x[i]);
170 }
171 return B;
172}
173
186static inline word mzd_slice_read_elem(const mzd_slice_t *A, const rci_t row, const rci_t col) {
187 word ret = 0;
188 for(int i=0; i<A->depth; i++) {
189 ret |= mzd_read_bit(A->x[i], row, col)<<i;
190 }
191 return ret;
192}
193
207static inline void mzd_slice_add_elem(mzd_slice_t *A, const rci_t row, const rci_t col, word elem) {
208 for(int i=0; i<A->depth; i++) {
209 __mzd_xor_bits(A->x[i], row, col, 1, elem&1);
210 elem=elem>>1;
211 }
212}
213
227static inline void mzd_slice_write_elem(mzd_slice_t *A, const rci_t row, const rci_t col, word elem) {
228 for(int i=0; i<A->depth; i++) {
229 mzd_write_bit(A->x[i], row, col, elem&1);
230 elem=elem>>1;
231 }
232}
233
247static inline int mzd_slice_cmp(mzd_slice_t *A, mzd_slice_t *B) {
248 int r = 0;
249 if ((A->finite_field != B->finite_field) | (A->depth != B->depth) )
250 return -1;
251 for(int i=0; i<A->depth; i++)
252 r |= mzd_cmp(A->x[i],B->x[i]);
253 return r;
254}
255
264static inline int mzd_slice_is_zero(const mzd_slice_t *A) {
265 for(int i=0; i<A->depth; i++) {
266 if (!mzd_is_zero(A->x[i]))
267 return 0;
268 }
269 return 1;
270}
271
282static inline void mzd_slice_row_swap(mzd_slice_t *A, const rci_t rowa, const rci_t rowb) {
283 for(int i=0; i<A->depth; i++) {
284 mzd_row_swap(A->x[i], rowa, rowb);
285 }
286}
287
301static inline void mzd_slice_copy_row(mzd_slice_t* B, size_t i, const mzd_slice_t* A, size_t j) {
302 for(int ii=0; ii<A->depth; ii++)
303 mzd_copy_row(B->x[ii], i, A->x[ii], j);
304}
305
316static inline void mzd_slice_col_swap(mzd_slice_t *A, const rci_t cola, const rci_t colb) {
317 for(int i=0; i<A->depth; i++)
318 mzd_col_swap(A->x[i], cola, colb);
319}
320
331static inline 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) {
332 for(unsigned int e=0; e < A->finite_field->degree; e++) {
333 mzd_col_swap_in_rows(A->x[e], cola, colb, start_row, stop_row);
334 };
335}
336
350static inline void mzd_slice_row_add(mzd_slice_t *A, const rci_t sourcerow, const rci_t destrow) {
351 for(int i=0; i<A->depth; i++)
352 mzd_row_add(A->x[i], sourcerow, destrow);
353}
354
363void mzd_slice_print(const mzd_slice_t *A);
364
374static inline void _mzd_slice_compress_l(mzd_slice_t *A, const rci_t r1, const rci_t n1, const rci_t r2) {
375 for(int i=0; i<A->depth; i++)
376 _mzd_compress_l(A->x[i], r1, n1, r2);
377}
378
397static inline mzd_slice_t *mzd_slice_concat(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) {
398 if(C == NULL)
399 C = mzd_slice_init(A->finite_field, A->nrows, A->ncols + B->ncols);
400
401 for(unsigned int i=0; i<A->depth; i++) {
402 mzd_concat(C->x[i], A->x[i], B->x[i]);
403 }
404 return C;
405}
406
424static inline mzd_slice_t *mzd_slice_stack(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) {
425 if(C == NULL)
426 C = mzd_slice_init(A->finite_field, A->nrows + B->nrows, A->ncols);
427
428 for(unsigned int i=0; i<A->depth; i++) {
429 mzd_stack(C->x[i], A->x[i], B->x[i]);
430 }
431 return C;
432}
433
448 const size_t lowr, const size_t lowc, const size_t highr, const size_t highc) {
449 if(S==NULL)
450 S = mzd_slice_init(A->finite_field, highr - lowr, highc - lowc);
451
452 for(unsigned int i=0; i<A->depth; i++) {
453 mzd_submatrix(S->x[i], A->x[i], lowr, lowc, highr, highc);
454 }
455 return S;
456}
457
481 const size_t lowr, const size_t lowc,
482 const size_t highr, const size_t highc) {
483 mzd_slice_t *B = (mzd_slice_t *)m4ri_mm_malloc(sizeof(mzd_slice_t));
485 B->depth = A->depth;
486 B->nrows = highr - lowr;
487 B->ncols = highc - lowc;
488 for(unsigned int i=0; i<A->depth; i++) {
489 B->x[i] = mzd_init_window(A->x[i], lowr, lowc, highr, highc);
490 }
491 return B;
492}
493
502static inline void mzd_slice_free_window(mzd_slice_t *A) {
503 for(unsigned int i=0; i<A->depth; i++) {
504 mzd_free_window(A->x[i]);
505 }
506 m4ri_mm_free(A);
507}
508
519static inline mzd_slice_t *_mzd_slice_add(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) {
520 _mzd_ptr_add(C->x, (const mzd_t**)A->x, (const mzd_t**)B->x, A->depth);
521 return C;
522}
523
537static inline mzd_slice_t *mzd_slice_add(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) {
538 if ( (A->finite_field != B->finite_field) | (A->nrows != B->nrows) | (A->ncols != B->ncols) )
539 m4ri_die("mzd_slice_add: input matrices A (%d x %d) and B (%d x %d) do not match.\n",A->nrows,A->ncols, B->nrows,B->ncols);
540
541 if(C == NULL)
542 C = mzd_slice_init(A->finite_field, A->nrows, A->ncols);
543 else if ( (A->finite_field != C->finite_field) | (A->nrows != C->nrows) | (A->ncols != C->ncols) )
544 m4ri_die("mzd_slice_add: input matrix A (%d x %d) and output matrix (%d x %d) do not match.\n",A->nrows,A->ncols, C->nrows, C->ncols);
545
546 return _mzd_slice_add(C,A,B);
547}
548
562#define mzd_slice_sub mzd_slice_add
563
574#define _mzd_slice_sub _mzd_slice_add
575
587
625 if (C == NULL)
626 C = mzd_slice_init(A->finite_field, A->nrows, B->ncols);
627 switch(A->finite_field->degree) {
628 case 2: _mzd_ptr_addmul_karatsuba2(A->finite_field, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
629 case 3: _mzd_ptr_addmul_karatsuba3(A->finite_field, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
630 case 4: _mzd_ptr_addmul_karatsuba4(A->finite_field, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
631 case 5: _mzd_ptr_addmul_karatsuba5(A->finite_field, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
632 case 6: _mzd_ptr_addmul_karatsuba6(A->finite_field, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
633 case 7: _mzd_ptr_addmul_karatsuba7(A->finite_field, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
634 case 8: _mzd_ptr_addmul_karatsuba8(A->finite_field, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
635 case 9: _mzd_ptr_addmul_karatsuba9(A->finite_field, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
636 case 10: _mzd_ptr_addmul_karatsuba10(A->finite_field, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
637 case 11: _mzd_ptr_addmul_karatsuba11(A->finite_field, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
638 case 12: _mzd_ptr_addmul_karatsuba12(A->finite_field, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
639 case 13: _mzd_ptr_addmul_karatsuba13(A->finite_field, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
640 case 14: _mzd_ptr_addmul_karatsuba14(A->finite_field, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
641 case 15: _mzd_ptr_addmul_karatsuba15(A->finite_field, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
642 case 16: _mzd_ptr_addmul_karatsuba16(A->finite_field, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
643 default:
644 C = _mzd_slice_addmul_naive(C, A, B); break;
645 }
646 return C;
647}
648
662 if (A->ncols != B->nrows || A->finite_field != B->finite_field)
663 m4ri_die("mzd_slice_mul_karatsuba: rows, columns and fields must match.\n");
664 if (C != NULL) {
665 if (C->finite_field != A->finite_field || C->nrows != A->nrows || C->ncols != B->ncols)
666 m4ri_die("mzd_slice_mul_karatsuba: rows and columns of returned matrix must match.\n");
667 mzd_slice_set_ui(C,0);
668 }
669 return _mzd_slice_addmul_karatsuba(C, A, B);
670}
671
685 assert(C != NULL);
686 if (A->ncols != B->nrows || A->finite_field != B->finite_field)
687 m4ri_die("mzd_slice_addmul_karatsuba: rows, columns and fields must match.\n");
688 if (C->finite_field != A->finite_field || C->nrows != A->nrows || C->ncols != B->ncols)
689 m4ri_die("mzd_slice_addmul_karatsuba: rows and columns of returned matrix must match.\n");
690 return _mzd_slice_addmul_karatsuba(C, A, B);
691}
692
706static inline mzd_slice_t *_mzd_slice_mul_blm(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B, blm_t *f) {
707 if (C == NULL)
708 C = mzd_slice_init(A->finite_field, A->nrows, B->ncols);
709
710 int free_f = 0;
711
712 if (f == NULL) {
713 const deg_t d = C->finite_field->degree;
714 if (d > 16)
715 m4ri_die("degrees > 16 unsupported.\n");
716 int *p = (int *)m4ri_mm_calloc(M4RIE_MAX_DEGREE+1, sizeof(int));
717 p[d] = 1;
718 free_f = 1;
719 f = blm_init_crt(C->finite_field, d, d, p, 1);
720 m4ri_mm_free(p);
721 }
722
723 _mzd_ptr_apply_blm(C->x, (const mzd_t**)A->x, (const mzd_t**)B->x, f);
724
725 if (free_f)
726 blm_free(f);
727
728 return C;
729}
730
744static inline mzd_slice_t *mzd_slice_mul_blm(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B, blm_t *f) {
745 if (A->ncols != B->nrows || A->finite_field != B->finite_field)
746 m4ri_die("mzd_slice_mul_karatsuba: rows, columns and fields must match.\n");
747 if (C != NULL) {
748 if (C->finite_field != A->finite_field || C->nrows != A->nrows || C->ncols != B->ncols)
749 m4ri_die("mzd_slice_mul_karatsuba: rows and columns of returned matrix must match.\n");
750 mzd_slice_set_ui(C,0);
751 }
752 return _mzd_slice_mul_blm(C, A, B, f);
753}
754
768static inline mzd_slice_t *mzd_slice_addmul_blm(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B, blm_t *f) {
769 assert(C != NULL);
770 if (A->ncols != B->nrows || A->finite_field != B->finite_field)
771 m4ri_die("mzd_slice_addmul_karatsuba: rows, columns and fields must match.\n");
772 if (C->finite_field != A->finite_field || C->nrows != A->nrows || C->ncols != B->ncols)
773 m4ri_die("mzd_slice_addmul_karatsuba: rows and columns of returned matrix must match.\n");
774 mzd_slice_t *T = _mzd_slice_mul_blm(NULL, A, B, f);
775 mzd_slice_add(C, C, T);
777 return C;
778}
779
780
791mzd_slice_t *mzd_slice_mul_scalar(mzd_slice_t *C, const word a, const mzd_slice_t *B);
792
804
805
818static inline mzd_slice_t *mzd_slice_mul(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) {
819 return mzd_slice_mul_karatsuba(C,A,B);
820}
821
834static inline mzd_slice_t *mzd_slice_addmul(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) {
835 return mzd_slice_addmul_karatsuba(C,A,B);
836}
837
848static inline void mzd_slice_randomize(mzd_slice_t *A) {
849 for(unsigned int i=0; i<A->depth; i++)
850 mzd_randomize(A->x[i]);
851}
852
863#endif //M4RIE_MZD_SLICE
Bilinear Maps on Matrices over GF(2).
static void _mzd_ptr_apply_blm(mzd_t **X, const mzd_t **A, const mzd_t **B, const blm_t *f)
Apply f on A and B, writing to X.
Definition: blm.h:153
#define M4RIE_MAX_DEGREE
maximal supported degree
Definition: gf2e.h:50
int deg_t
Definition: gf2x.h:37
static mzd_slice_t * _mzd_slice_add(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B)
.
Definition: mzd_slice.h:519
static mzd_slice_t * mzd_slice_add(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B)
.
Definition: mzd_slice.h:537
static void mzd_slice_randomize(mzd_slice_t *A)
Fill matrix A with random elements.
Definition: mzd_slice.h:848
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.
Definition: mzd_slice.h:186
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.
Definition: mzd_slice.h:207
void mzd_slice_set_ui(mzd_slice_t *A, word value)
Return diagonal matrix with value on the diagonal.
Definition: mzd_slice.c:57
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.
Definition: mzd_slice.h:227
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.
Definition: mzd_slice.h:480
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.
Definition: mzd_slice.h:397
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.
Definition: mzd_slice.h:447
static mzd_slice_t * mzd_slice_copy(mzd_slice_t *B, const mzd_slice_t *A)
copy A to B
Definition: mzd_slice.h:164
static mzd_slice_t * mzd_slice_init(const gf2e *ff, const rci_t m, const rci_t n)
Create a new matrix of dimension over ff.
Definition: mzd_slice.h:78
static void mzd_slice_free(mzd_slice_t *A)
Free a matrix created with mzd_slice_init().
Definition: mzd_slice.h:145
static void mzd_slice_free_window(mzd_slice_t *A)
Free a matrix window created with mzd_slice_init_window().
Definition: mzd_slice.h:502
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.
Definition: mzd_slice.h:424
mzd_slice_t * mzd_slice_addmul_scalar(mzd_slice_t *C, const word a, const mzd_slice_t *B)
.
Definition: mzd_slice.c:43
void _mzd_ptr_addmul_karatsuba2(const gf2e *ff, mzd_t **X, const mzd_t **A, const mzd_t **B)
over using 3 multiplications over and 2 temporary matrices.
Definition: karatsuba.c:4
static mzd_slice_t * _mzd_slice_addmul_karatsuba(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B)
using Karatsuba multiplication of polynomials over matrices over .
Definition: mzd_slice.h:624
static mzd_slice_t * _mzd_slice_mul_blm(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B, blm_t *f)
using bilinear maps over matrices over .
Definition: mzd_slice.h:706
static mzd_slice_t * mzd_slice_mul(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B)
.
Definition: mzd_slice.h:818
static mzd_slice_t * mzd_slice_mul_karatsuba(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B)
using Karatsuba multiplication of polynomials over matrices over .
Definition: mzd_slice.h:661
static mzd_slice_t * mzd_slice_addmul_karatsuba(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B)
using Karatsuba multiplication of polynomials over matrices over .
Definition: mzd_slice.h:684
static mzd_slice_t * mzd_slice_addmul(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B)
.
Definition: mzd_slice.h:834
mzd_slice_t * mzd_slice_mul_scalar(mzd_slice_t *C, const word a, const mzd_slice_t *B)
.
Definition: mzd_slice.c:25
mzd_slice_t * _mzd_slice_addmul_naive(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B)
using quadratic polynomial multiplication with matrix coefficients.
Definition: mzd_slice.c:82
static mzd_slice_t * mzd_slice_addmul_blm(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B, blm_t *f)
using bilinear maps over matrices over .
Definition: mzd_slice.h:768
static mzd_slice_t * mzd_slice_mul_blm(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B, blm_t *f)
using bilinear maps over matrices over .
Definition: mzd_slice.h:744
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.
Definition: mzd_slice.h:282
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.
Definition: mzd_slice.h:316
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.
Definition: mzd_slice.h:350
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.
Definition: mzd_slice.h:301
void mzd_slice_print(const mzd_slice_t *A)
Print a matrix to stdout.
Definition: mzd_slice.c:63
Matrices over [x].
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.
Definition: mzd_slice.h:374
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.
Definition: mzd_slice.h:247
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.
Definition: mzd_slice.h:119
static int mzd_slice_is_zero(const mzd_slice_t *A)
Zero test for matrix.
Definition: mzd_slice.h:264
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.
Definition: mzd_slice.h:331
Dense matrices over represented as packed matrices.
Bilinear Maps on Matrices over GF(2).
Definition: blm.h:51
Definition: gf2e.h:62
deg_t degree
Definition: gf2e.h:63
Dense matrices over represented as slices of matrices over .
Definition: mzd_slice.h:56
rci_t nrows
Definition: mzd_slice.h:58
const gf2e * finite_field
Definition: mzd_slice.h:62
mzd_t * x[16]
Definition: mzd_slice.h:57
rci_t ncols
Definition: mzd_slice.h:59
unsigned int depth
Definition: mzd_slice.h:60