M4RIE
0.20120415
|
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