M4RIE  0.20120613
 All Data Structures Files Functions Variables Macros Groups Pages
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 
47 #define __M4RIE_MAX_KARATSUBA_DEGREE 8
48 
62 typedef struct {
63  mzd_t *x[16];
64  rci_t nrows;
65  rci_t ncols;
66  unsigned int depth;
68  const gf2e *finite_field;
69 } mzd_slice_t;
70 
71 
84 static inline mzd_slice_t *mzd_slice_init(const gf2e *ff, const rci_t m, const rci_t n) {
85  mzd_slice_t *A = (mzd_slice_t*)m4ri_mm_malloc(sizeof(mzd_slice_t));
86 
87  A->finite_field = ff;
88  A->nrows = m;
89  A->ncols = n;
90  A->depth = ff->degree;
91 
92  for(unsigned int i=0; i<A->depth; i++)
93  A->x[i] = mzd_init(m,n);
94  return A;
95 }
96 
109 void mzd_slice_set_ui(mzd_slice_t *A, word value);
110 
125 static inline mzd_slice_t *_mzd_slice_adapt_depth(mzd_slice_t *A, const unsigned int new_depth) {
126  assert(A->finite_field->degree <= new_depth);
127 
128  if (new_depth < A->depth) {
129  for(unsigned int i=new_depth; i<A->depth; i++) {
130  mzd_free(A->x[i]);
131  A->x[i] = NULL;
132  }
133  } else {
134  for(unsigned int i=A->depth; i<new_depth; i++) {
135  A->x[i] = mzd_init(A->nrows,A->ncols);
136  }
137  }
138  A->depth = new_depth;
139  return A;
140 }
141 
142 
151 static inline void mzd_slice_free(mzd_slice_t *A) {
152  for(unsigned int i=0; i<A->depth; i++)
153  mzd_free(A->x[i]);
154 #if __M4RI_USE_MM_MALLOC
155  _mm_free(A);
156 #else
157  free(A);
158 #endif
159 }
160 
179 static inline mzd_slice_t *mzd_slice_concat(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) {
180  if(C == NULL)
181  C = mzd_slice_init(A->finite_field, A->nrows, A->ncols + B->ncols);
182 
183  for(unsigned int i=0; i<A->depth; i++) {
184  mzd_concat(C->x[i], A->x[i], B->x[i]);
185  }
186  return C;
187 }
188 
206 static inline mzd_slice_t *mzd_slice_stack(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) {
207  if(C == NULL)
208  C = mzd_slice_init(A->finite_field, A->nrows + B->nrows, A->ncols);
209 
210  for(unsigned int i=0; i<A->depth; i++) {
211  mzd_stack(C->x[i], A->x[i], B->x[i]);
212  }
213  return C;
214 }
215 
230  const size_t lowr, const size_t lowc, const size_t highr, const size_t highc) {
231  if(S==NULL)
232  S = mzd_slice_init(A->finite_field, highr - lowr, highc - lowc);
233 
234  for(unsigned int i=0; i<A->depth; i++) {
235  mzd_submatrix(S->x[i], A->x[i], lowr, lowc, highr, highc);
236  }
237  return S;
238 }
239 
263  const size_t lowr, const size_t lowc,
264  const size_t highr, const size_t highc) {
265  mzd_slice_t *B = (mzd_slice_t *)m4ri_mm_malloc(sizeof(mzd_slice_t));
266  B->finite_field = A->finite_field;
267  B->depth = A->depth;
268  B->nrows = highr - lowr;
269  B->ncols = highc - lowc;
270  for(unsigned int i=0; i<A->depth; i++) {
271  B->x[i] = mzd_init_window(A->x[i], lowr, lowc, highr, highc);
272  }
273  return B;
274 }
275 
284 static inline void mzd_slice_free_window(mzd_slice_t *A) {
285  for(unsigned int i=0; i<A->depth; i++) {
286  mzd_free_window(A->x[i]);
287  }
288  m4ri_mm_free(A);
289 }
290 
301 static inline mzd_slice_t *_mzd_slice_add(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) {
302  _poly_add(C->x, (const mzd_t**)A->x, (const mzd_t**)B->x, A->depth);
303  return C;
304 }
305 
319 static inline mzd_slice_t *mzd_slice_add(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) {
320  if ( (A->finite_field != B->finite_field) | (A->nrows != B->nrows) | (A->ncols != B->ncols) )
321  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);
322 
323  if(C == NULL)
325  else if ( (A->finite_field != C->finite_field) | (A->nrows != C->nrows) | (A->ncols != C->ncols) )
326  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);
327 
328  return _mzd_slice_add(C,A,B);
329 }
330 
344 #define mzd_slice_sub mzd_slice_add
345 
356 #define _mzd_slice_sub _mzd_slice_add
357 
369 
382 
400 
414 
432 
450 
468 
482 
520  switch(A->finite_field->degree) {
521  case 2: C = _mzd_slice_mul_karatsuba2(C, A, B); break;
522  case 3: C = _mzd_slice_mul_karatsuba3(C, A, B); break;
523  case 4: C = _mzd_slice_mul_karatsuba4(C, A, B); break;
524  case 5: C = _mzd_slice_mul_karatsuba5(C, A, B); break;
525  case 6: C = _mzd_slice_mul_karatsuba6(C, A, B); break;
526  case 7: C = _mzd_slice_mul_karatsuba7(C, A, B); break;
527  case 8: C = _mzd_slice_mul_karatsuba8(C, A, B); break;
528  case 9: C = _mzd_slice_mul_naive(C, A, B); break;
529  case 10: C = _mzd_slice_mul_naive(C, A, B); break;
530  default:
531  m4ri_die("_mzd_slice_mul_karatsuba: only implemented for GF(2^e) with e <= 4");
532  }
533  return C;
534 }
535 
549  if (A->ncols != B->nrows || A->finite_field != B->finite_field)
550  m4ri_die("mzd_slice_mul_karatsuba: rows, columns and fields must match.\n");
551  if (C != NULL) {
552  if (C->finite_field != A->finite_field || C->nrows != A->nrows || C->ncols != B->ncols)
553  m4ri_die("mzd_slice_mul_karatsuba: rows and columns of returned matrix must match.\n");
554  mzd_slice_set_ui(C,0);
555  }
556  return _mzd_slice_mul_karatsuba(C, A, B);
557 }
558 
572  assert(C != NULL);
573  if (A->ncols != B->nrows || A->finite_field != B->finite_field)
574  m4ri_die("mzd_slice_addmul_karatsuba: rows, columns and fields must match.\n");
575  if (C->finite_field != A->finite_field || C->nrows != A->nrows || C->ncols != B->ncols)
576  m4ri_die("mzd_slice_addmul_karatsuba: rows and columns of returned matrix must match.\n");
577  return _mzd_slice_mul_karatsuba(C, A, B);
578 }
579 
590 mzd_slice_t *mzd_slice_mul_scalar(mzd_slice_t *C, const word a, const mzd_slice_t *B);
591 
602 mzd_slice_t *mzd_slice_addmul_scalar(mzd_slice_t *C, const word a, const mzd_slice_t *B);
603 
604 
617 static inline mzd_slice_t *mzd_slice_mul(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) {
618  return mzd_slice_mul_karatsuba(C,A,B);
619 }
620 
633 static inline mzd_slice_t *mzd_slice_addmul(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) {
634  return mzd_slice_addmul_karatsuba(C,A,B);
635 }
636 
647 static inline void mzd_slice_randomize(mzd_slice_t *A) {
648  switch(A->depth) {
649  case 10: mzd_randomize(A->x[9]);
650  case 9: mzd_randomize(A->x[8]);
651  case 8: mzd_randomize(A->x[7]);
652  case 7: mzd_randomize(A->x[6]);
653  case 6: mzd_randomize(A->x[5]);
654  case 5: mzd_randomize(A->x[4]);
655  case 4: mzd_randomize(A->x[3]);
656  case 3: mzd_randomize(A->x[2]);
657  case 2: mzd_randomize(A->x[1]);
658  case 1: mzd_randomize(A->x[0]); break;
659  default:
660  m4ri_die("impossible");
661  }
662 }
663 
673 static inline mzd_slice_t *mzd_slice_copy(mzd_slice_t *B, const mzd_slice_t *A) {
674  if(B == NULL)
675  B = mzd_slice_init(A->finite_field, A->nrows, A->ncols);
676 
677  for(unsigned int i=0; i<A->depth; i++) {
678  mzd_copy(B->x[i],A->x[i]);
679  }
680  return B;
681 }
682 
695 static inline word mzd_slice_read_elem(const mzd_slice_t *A, const rci_t row, const rci_t col) {
696  word ret = 0;
697  for(unsigned int i=0; i<A->depth; i++) {
698  ret |= mzd_read_bit(A->x[i], row, col)<<i;
699  }
700  return ret;
701 }
702 
716 static inline void mzd_slice_add_elem(mzd_slice_t *A, const rci_t row, const rci_t col, word elem) {
717  for(unsigned int i=0; i<A->depth; i++) {
718  __mzd_xor_bits(A->x[i], row, col, 1, elem&1);
719  elem=elem>>1;
720  }
721 }
722 
736 static inline void mzd_slice_write_elem(mzd_slice_t *A, const rci_t row, const rci_t col, word elem) {
737  for(unsigned int i=0; i<A->depth; i++) {
738  mzd_write_bit(A->x[i], row, col, elem&1);
739  elem=elem>>1;
740  }
741 }
742 
756 static inline int mzd_slice_cmp(mzd_slice_t *A, mzd_slice_t *B) {
757  int r = 0;
758  if ((A->finite_field != B->finite_field) | (A->depth != B->depth) )
759  return -1;
760  for(unsigned int i=0; i<A->depth; i++)
761  r |= mzd_cmp(A->x[i],B->x[i]);
762  return r;
763 }
764 
773 static inline int mzd_slice_is_zero(const mzd_slice_t *A) {
774  for(unsigned int i=0; i<A->depth; i++) {
775  if (!mzd_is_zero(A->x[i]))
776  return 0;
777  }
778  return 1;
779 }
780 
791 static inline void mzd_slice_row_swap(mzd_slice_t *A, const rci_t rowa, const rci_t rowb) {
792  for(unsigned int i=0; i<A->depth; i++) {
793  mzd_row_swap(A->x[i], rowa, rowb);
794  }
795 }
796 
811 static inline void mzd_slice_copy_row(mzd_slice_t* B, size_t i, const mzd_slice_t* A, size_t j) {
812  for(unsigned int ii=0; ii<A->depth; ii++)
813  mzd_copy_row(B->x[ii], i, A->x[ii], j);
814 }
815 
826 static inline void mzd_slice_col_swap(mzd_slice_t *A, const rci_t cola, const rci_t colb) {
827  for(unsigned int i=0; i<A->depth; i++)
828  mzd_col_swap(A->x[i], cola, colb);
829 }
830 
841 static 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) {
842  for(unsigned int e=0; e < A->finite_field->degree; e++) {
843  mzd_col_swap_in_rows(A->x[e], cola, colb, start_row, stop_row);
844  };
845 }
846 
860 static inline void mzd_slice_row_add(mzd_slice_t *A, const rci_t sourcerow, const rci_t destrow) {
861  for(unsigned int i=0; i<A->depth; i++)
862  mzd_row_add(A->x[i], sourcerow, destrow);
863 }
864 
875 static inline void mzd_slice_row_clear_offset(mzd_slice_t *A, const rci_t row, const rci_t coloffset) {
876  for(unsigned int i=0; i<A->depth; i++)
877  mzd_row_clear_offset(A->x[i], row, coloffset);
878 }
879 
888 void mzd_slice_print(const mzd_slice_t *A);
889 
899 static inline void _mzd_slice_compress_l(mzd_slice_t *A, const rci_t r1, const rci_t n1, const rci_t r2) {
900  switch(A->finite_field->degree) {
901  case 10: _mzd_compress_l(A->x[9], r1, n1, r2);
902  case 9: _mzd_compress_l(A->x[8], r1, n1, r2);
903  case 8: _mzd_compress_l(A->x[7], r1, n1, r2);
904  case 7: _mzd_compress_l(A->x[6], r1, n1, r2);
905  case 6: _mzd_compress_l(A->x[5], r1, n1, r2);
906  case 5: _mzd_compress_l(A->x[4], r1, n1, r2);
907  case 4: _mzd_compress_l(A->x[3], r1, n1, r2);
908  case 3: _mzd_compress_l(A->x[2], r1, n1, r2);
909  case 2: _mzd_compress_l(A->x[1], r1, n1, r2);
910  case 1: _mzd_compress_l(A->x[0], r1, n1, r2); break;
911  default:
912  m4ri_die("impossible");
913  };
914 }
915 
916 #endif //M4RIE_MZD_SLICE