M4RIE  0.20120415
 All Data Structures Files Functions Variables Defines
mzd_slice.h
Go to the documentation of this file.
00001 
00016 #ifndef M4RIE_MZD_SLICE
00017 #define M4RIE_MZD_SLICE
00018 
00019 /******************************************************************************
00020 *
00021 *            M4RIE: Linear Algebra over GF(2^e)
00022 *
00023 *    Copyright (C) 2010,2011 Martin Albrecht <martinralbrecht@googlemail.com>
00024 *
00025 *  Distributed under the terms of the GNU General Public License (GEL)
00026 *  version 2 or higher.
00027 *
00028 *    This code is distributed in the hope that it will be useful,
00029 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
00030 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00031 *    General Public License for more details.
00032 *
00033 *  The full text of the GPL is available at:
00034 *
00035 *                  http://www.gnu.org/licenses/
00036 ******************************************************************************/
00037 
00038 #include <m4ri/m4ri.h>
00039 #include "mzd_poly.h"
00040 #include "mzed.h"
00041 
00047 #define __M4RIE_MAX_KARATSUBA_DEGREE 8
00048 
00062 typedef struct {
00063   mzd_t *x[16]; 
00064   rci_t nrows; 
00065   rci_t ncols; 
00066   unsigned int depth;   
00068   const gf2e *finite_field; 
00069 } mzd_slice_t;
00070 
00071 
00084 static inline mzd_slice_t *mzd_slice_init(const gf2e *ff, const rci_t m, const rci_t n) {
00085   mzd_slice_t *A = (mzd_slice_t*)m4ri_mm_malloc(sizeof(mzd_slice_t));
00086 
00087   A->finite_field = ff;
00088   A->nrows = m;
00089   A->ncols = n;
00090   A->depth = ff->degree;
00091 
00092   for(unsigned int i=0; i<A->depth; i++)
00093     A->x[i] = mzd_init(m,n);
00094   return A;
00095 }
00096 
00109 void mzd_slice_set_ui(mzd_slice_t *A, word value);
00110 
00125 static inline mzd_slice_t *_mzd_slice_adapt_depth(mzd_slice_t *A, const unsigned int new_depth) {
00126   assert(A->finite_field->degree <= new_depth);
00127 
00128   if (new_depth < A->depth) {
00129     for(unsigned int i=new_depth; i<A->depth; i++) {
00130       mzd_free(A->x[i]);
00131       A->x[i] = NULL;
00132     }
00133   } else {
00134     for(unsigned int i=A->depth; i<new_depth; i++) {
00135       A->x[i] = mzd_init(A->nrows,A->ncols);
00136     }
00137   }
00138   A->depth = new_depth;
00139   return A;
00140 }
00141 
00142 
00151 static inline void mzd_slice_free(mzd_slice_t *A) {
00152   for(unsigned int i=0; i<A->depth; i++)
00153    mzd_free(A->x[i]);
00154 #if __M4RI_USE_MM_MALLOC
00155   _mm_free(A);
00156 #else
00157   free(A);
00158 #endif
00159 }
00160 
00179 static inline mzd_slice_t *mzd_slice_concat(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) {
00180   if(C == NULL)
00181     C = mzd_slice_init(A->finite_field, A->nrows, A->ncols + B->ncols);
00182 
00183   for(unsigned int i=0; i<A->depth; i++) {
00184     mzd_concat(C->x[i], A->x[i], B->x[i]);
00185   }
00186   return C;
00187 }
00188 
00206 static inline mzd_slice_t *mzd_slice_stack(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) {
00207   if(C == NULL)
00208     C = mzd_slice_init(A->finite_field, A->nrows + B->nrows, A->ncols);
00209 
00210   for(unsigned int i=0; i<A->depth; i++) {
00211     mzd_stack(C->x[i], A->x[i], B->x[i]);
00212   }
00213   return C;
00214 }
00215 
00229 static inline mzd_slice_t *mzd_slice_submatrix(mzd_slice_t *S, const mzd_slice_t *A,
00230                                                const size_t lowr, const size_t lowc, const size_t highr, const size_t highc) {
00231   if(S==NULL)
00232     S = mzd_slice_init(A->finite_field, highr - lowr, highc - lowc);
00233 
00234   for(unsigned int i=0; i<A->depth; i++) {
00235     mzd_submatrix(S->x[i], A->x[i], lowr, lowc, highr, highc);
00236   }
00237   return S;
00238 }
00239 
00262 static inline mzd_slice_t *mzd_slice_init_window(const mzd_slice_t *A,
00263                                                  const size_t lowr, const size_t lowc,
00264                                                  const size_t highr, const size_t highc) {
00265   mzd_slice_t *B = (mzd_slice_t *)m4ri_mm_malloc(sizeof(mzd_slice_t));
00266   B->finite_field = A->finite_field;
00267   B->depth = A->depth;
00268   B->nrows = highr - lowr;
00269   B->ncols = highc - lowc;
00270   for(unsigned int i=0; i<A->depth; i++) {
00271     B->x[i] = mzd_init_window(A->x[i], lowr, lowc, highr, highc);
00272   }
00273   return B;
00274 }
00275 
00284 static inline void mzd_slice_free_window(mzd_slice_t *A) {
00285   for(unsigned int i=0; i<A->depth; i++) {
00286     mzd_free_window(A->x[i]);
00287   }
00288   m4ri_mm_free(A);
00289 }
00290 
00301 static inline mzd_slice_t *_mzd_slice_add(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) {
00302   _poly_add(C->x, (const mzd_t**)A->x, (const mzd_t**)B->x, A->depth);
00303   return C;
00304 }
00305 
00319 static inline mzd_slice_t *mzd_slice_add(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) {
00320   if ( (A->finite_field != B->finite_field) | (A->nrows != B->nrows) | (A->ncols != B->ncols) ) 
00321     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);
00322 
00323   if(C == NULL)
00324     mzd_slice_init(A->finite_field, A->nrows, A->ncols);
00325   else if ( (A->finite_field != C->finite_field) | (A->nrows != C->nrows) | (A->ncols != C->ncols) )
00326     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);
00327 
00328   return _mzd_slice_add(C,A,B);
00329 }
00330 
00344 #define mzd_slice_sub mzd_slice_add
00345 
00356 #define _mzd_slice_sub _mzd_slice_add
00357 
00368 mzd_slice_t *_mzd_slice_mul_naive(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B);
00369 
00381 mzd_slice_t *_mzd_slice_mul_karatsuba2(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B);
00382 
00399 mzd_slice_t *_mzd_slice_mul_karatsuba3(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B);
00400 
00413 mzd_slice_t *_mzd_slice_mul_karatsuba4(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B);
00414 
00431 mzd_slice_t *_mzd_slice_mul_karatsuba5(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B);
00432 
00449 mzd_slice_t *_mzd_slice_mul_karatsuba6(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B);
00450 
00467 mzd_slice_t *_mzd_slice_mul_karatsuba7(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B);
00468 
00481 mzd_slice_t *_mzd_slice_mul_karatsuba8(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B);
00482 
00519 static inline mzd_slice_t *_mzd_slice_mul_karatsuba(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) {
00520   switch(A->finite_field->degree) {
00521   case  2: C = _mzd_slice_mul_karatsuba2(C, A, B); break;
00522   case  3: C = _mzd_slice_mul_karatsuba3(C, A, B); break;
00523   case  4: C = _mzd_slice_mul_karatsuba4(C, A, B); break;
00524   case  5: C = _mzd_slice_mul_karatsuba5(C, A, B); break;
00525   case  6: C = _mzd_slice_mul_karatsuba6(C, A, B); break;
00526   case  7: C = _mzd_slice_mul_karatsuba7(C, A, B); break;
00527   case  8: C = _mzd_slice_mul_karatsuba8(C, A, B); break;
00528   case  9: C = _mzd_slice_mul_naive(C, A, B); break;
00529   case 10: C = _mzd_slice_mul_naive(C, A, B); break;
00530   default:
00531     m4ri_die("_mzd_slice_mul_karatsuba: only implemented for GF(2^e) with e <= 4");
00532   }
00533   return C;
00534 }
00535 
00548 static inline mzd_slice_t *mzd_slice_mul_karatsuba(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) {
00549   if (A->ncols != B->nrows || A->finite_field != B->finite_field)
00550     m4ri_die("mzd_slice_mul_karatsuba: rows, columns and fields must match.\n");
00551   if (C != NULL) {
00552     if (C->finite_field != A->finite_field || C->nrows != A->nrows || C->ncols != B->ncols)
00553       m4ri_die("mzd_slice_mul_karatsuba: rows and columns of returned matrix must match.\n");
00554     mzd_slice_set_ui(C,0);
00555   }
00556   return _mzd_slice_mul_karatsuba(C, A, B);
00557 }
00558 
00571 static inline mzd_slice_t *mzd_slice_addmul_karatsuba(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) {
00572   assert(C != NULL);
00573   if (A->ncols != B->nrows || A->finite_field != B->finite_field)
00574     m4ri_die("mzd_slice_addmul_karatsuba: rows, columns and fields must match.\n");
00575   if (C->finite_field != A->finite_field || C->nrows != A->nrows || C->ncols != B->ncols)
00576     m4ri_die("mzd_slice_addmul_karatsuba: rows and columns of returned matrix must match.\n");
00577   return _mzd_slice_mul_karatsuba(C, A, B);
00578 }
00579 
00590 mzd_slice_t *mzd_slice_mul_scalar(mzd_slice_t *C, const word a, const mzd_slice_t *B);
00591 
00602 mzd_slice_t *mzd_slice_addmul_scalar(mzd_slice_t *C, const word a, const mzd_slice_t *B);
00603 
00604 
00617 static inline mzd_slice_t *mzd_slice_mul(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) {
00618   return mzd_slice_mul_karatsuba(C,A,B);
00619 }
00620 
00633 static inline mzd_slice_t *mzd_slice_addmul(mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B) {
00634   return mzd_slice_addmul_karatsuba(C,A,B);
00635 }
00636 
00647 static inline void mzd_slice_randomize(mzd_slice_t *A) {
00648   switch(A->depth) {
00649   case 10: mzd_randomize(A->x[9]);
00650   case  9: mzd_randomize(A->x[8]);
00651   case  8: mzd_randomize(A->x[7]);
00652   case  7: mzd_randomize(A->x[6]);
00653   case  6: mzd_randomize(A->x[5]);
00654   case  5: mzd_randomize(A->x[4]);
00655   case  4: mzd_randomize(A->x[3]);
00656   case  3: mzd_randomize(A->x[2]);
00657   case  2: mzd_randomize(A->x[1]);
00658   case  1: mzd_randomize(A->x[0]); break;
00659   default:
00660     m4ri_die("impossible");
00661   }
00662 }
00663 
00673 static inline mzd_slice_t *mzd_slice_copy(mzd_slice_t *B, const mzd_slice_t *A) {
00674   if(B == NULL)
00675     B = mzd_slice_init(A->finite_field, A->nrows, A->ncols);
00676 
00677   for(unsigned int i=0; i<A->depth; i++) {
00678     mzd_copy(B->x[i],A->x[i]);
00679   }
00680   return B;
00681 }
00682 
00695 static inline word mzd_slice_read_elem(const mzd_slice_t *A, const rci_t row, const rci_t col) {
00696   word ret = 0;
00697   for(unsigned int i=0; i<A->depth; i++) {
00698     ret |= mzd_read_bit(A->x[i], row, col)<<i;
00699   }
00700   return ret;
00701 }
00702 
00716 static inline void mzd_slice_add_elem(mzd_slice_t *A, const rci_t row, const rci_t col, word elem) {
00717   for(unsigned int i=0; i<A->depth; i++) {
00718     __mzd_xor_bits(A->x[i], row, col, 1, elem&1);
00719     elem=elem>>1;
00720   }
00721 }
00722 
00736 static inline void mzd_slice_write_elem(mzd_slice_t *A, const rci_t row, const rci_t col, word elem) {
00737   for(unsigned int i=0; i<A->depth; i++) {
00738     mzd_write_bit(A->x[i], row, col, elem&1);
00739     elem=elem>>1;
00740   }
00741 }
00742 
00756 static inline int mzd_slice_cmp(mzd_slice_t *A, mzd_slice_t *B) {
00757   int r = 0;
00758   if ((A->finite_field != B->finite_field) | (A->depth != B->depth) )
00759     return -1;
00760   for(unsigned int i=0; i<A->depth; i++)
00761     r |= mzd_cmp(A->x[i],B->x[i]);
00762   return r;
00763 }
00764 
00773 static inline int mzd_slice_is_zero(const mzd_slice_t *A) {
00774   for(unsigned int i=0; i<A->depth; i++) {
00775     if (!mzd_is_zero(A->x[i]))
00776       return 0;
00777   }
00778   return 1;
00779 }
00780 
00791 static inline void mzd_slice_row_swap(mzd_slice_t *A, const rci_t rowa, const rci_t rowb) {
00792   for(unsigned int i=0; i<A->depth; i++) {
00793     mzd_row_swap(A->x[i], rowa, rowb);
00794   }
00795 }
00796 
00811 static inline void mzd_slice_copy_row(mzd_slice_t* B, size_t i, const mzd_slice_t* A, size_t j) {
00812   for(unsigned int ii=0; ii<A->depth; ii++)
00813     mzd_copy_row(B->x[ii], i, A->x[ii], j);
00814 }
00815 
00826 static inline void mzd_slice_col_swap(mzd_slice_t *A, const rci_t cola, const rci_t colb) {
00827   for(unsigned int i=0; i<A->depth; i++)
00828     mzd_col_swap(A->x[i], cola, colb);
00829 }
00830 
00841 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) {
00842   for(unsigned int e=0; e < A->finite_field->degree; e++) {
00843     mzd_col_swap_in_rows(A->x[e], cola, colb, start_row, stop_row);
00844   };
00845 }
00846 
00860 static inline void mzd_slice_row_add(mzd_slice_t *A, const rci_t sourcerow, const rci_t destrow) {
00861   for(unsigned int i=0; i<A->depth; i++)
00862     mzd_row_add(A->x[i], sourcerow, destrow);
00863 }
00864 
00875 static inline void mzd_slice_row_clear_offset(mzd_slice_t *A, const rci_t row, const rci_t coloffset) {
00876   for(unsigned int i=0; i<A->depth; i++)
00877     mzd_row_clear_offset(A->x[i], row, coloffset);
00878 }
00879 
00888 void mzd_slice_print(const mzd_slice_t *A);
00889 
00899 static inline void _mzd_slice_compress_l(mzd_slice_t *A, const rci_t r1, const rci_t n1, const rci_t r2) {
00900   switch(A->finite_field->degree) {
00901   case 10: _mzd_compress_l(A->x[9], r1, n1, r2);
00902   case  9: _mzd_compress_l(A->x[8], r1, n1, r2);
00903   case  8: _mzd_compress_l(A->x[7], r1, n1, r2);
00904   case  7: _mzd_compress_l(A->x[6], r1, n1, r2);
00905   case  6: _mzd_compress_l(A->x[5], r1, n1, r2);
00906   case  5: _mzd_compress_l(A->x[4], r1, n1, r2);
00907   case  4: _mzd_compress_l(A->x[3], r1, n1, r2);
00908   case  3: _mzd_compress_l(A->x[2], r1, n1, r2);
00909   case  2: _mzd_compress_l(A->x[1], r1, n1, r2);
00910   case  1: _mzd_compress_l(A->x[0], r1, n1, r2); break;
00911   default:
00912     m4ri_die("impossible");
00913   };
00914 }
00915 
00916 #endif //M4RIE_MZD_SLICE