M4RIE 0.20111004
Loading...
Searching...
No Matches
conversion.h
Go to the documentation of this file.
1
9#ifndef M4RIE_CONVERSION_H
10#define M4RIE_CONVERSION_H
11
12/******************************************************************************
13*
14* M4RIE: Linear Algebra over GF(2^e)
15*
16* Copyright (C) 2011 Martin Albrecht <martinralbrecht@googlemail.com>
17*
18* Distributed under the terms of the GNU General Public License (GEL)
19* version 2 or higher.
20*
21* This code is distributed in the hope that it will be useful,
22* but WITHOUT ANY WARRANTY; without even the implied warranty of
23* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
24* General Public License for more details.
25*
26* The full text of the GPL is available at:
27*
28* http://www.gnu.org/licenses/
29******************************************************************************/
30
31#include <m4ri/m4ri.h>
32#include <m4rie/mzed.h>
33#include <m4rie/mzd_slice.h>
34
44mzed_t *mzed_cling(mzed_t *A, const mzd_slice_t *Z);
45
56
69
78
87
96
109
110
119
128
137
148static inline mzed_t *_mzed_addmul_karatsuba(mzed_t *C, const mzed_t *A, const mzed_t *B) {
149 mzd_slice_t *As,*Bs,*Cs;
150 if(C)
151 Cs = mzed_slice(NULL,C);
152 else
153 Cs = NULL;
154 As = mzed_slice(NULL,A);
155 Bs = mzed_slice(NULL,B);
156
157 Cs = _mzd_slice_addmul_karatsuba(Cs, As, Bs);
158
159 C = mzed_cling(C, Cs);
160
161 mzd_slice_free(As);
162 mzd_slice_free(Bs);
163 mzd_slice_free(Cs);
164 return C;
165}
166
177static inline mzed_t *mzed_mul_karatsuba(mzed_t *C, const mzed_t *A, const mzed_t *B) {
178 if (A->ncols != B->nrows || A->finite_field != B->finite_field)
179 m4ri_die("mzed_mul_karatsuba: rows, columns and fields must match.\n");
180 if (C != NULL) {
181 if (C->finite_field != A->finite_field || C->nrows != A->nrows || C->ncols != B->ncols)
182 m4ri_die("mzed_mul_karatsuba: rows and columns of returned matrix must match.\n");
183 mzed_set_ui(C,0);
184 }
185 return _mzed_addmul_karatsuba(C, A, B);
186}
187
196static inline mzed_t *mzed_addmul_karatsuba(mzed_t *C, const mzed_t *A, const mzed_t *B) {
197 assert(C != NULL);
198 if (A->ncols != B->nrows || A->finite_field != B->finite_field)
199 m4ri_die("mzed_addmul_karatsuba: rows, columns and fields must match.\n");
200 if (C->finite_field != A->finite_field || C->nrows != A->nrows || C->ncols != B->ncols)
201 m4ri_die("mzed_addmul_karatsuba: rows and columns of returned matrix must match.\n");
202 return _mzed_addmul_karatsuba(C, A, B);
203}
204
215static inline mzed_t *_mzed_addmul_blm(mzed_t *C, const mzed_t *A, const mzed_t *B) {
216 mzd_slice_t *As,*Bs;
217 As = mzed_slice(NULL,A);
218 Bs = mzed_slice(NULL,B);
219
220 mzd_slice_t *Ts = _mzd_slice_mul_blm(NULL, As, Bs, NULL);
221 mzed_t *T = mzed_cling(NULL, Ts);
222 mzd_slice_free(Ts);
223
224 if (C) {
225 C = mzed_add(C, C, T);
226 mzed_free(T);
227 } else {
228 C = T;
229 }
230
231 mzd_slice_free(As);
232 mzd_slice_free(Bs);
233 return C;
234}
235
246static inline mzed_t *mzed_mul_blm(mzed_t *C, const mzed_t *A, const mzed_t *B) {
247 if (A->ncols != B->nrows || A->finite_field != B->finite_field)
248 m4ri_die("mzed_mul_blm: rows, columns and fields must match.\n");
249 if (C != NULL) {
250 if (C->finite_field != A->finite_field || C->nrows != A->nrows || C->ncols != B->ncols)
251 m4ri_die("mzed_mul_blm: rows and columns of returned matrix must match.\n");
252 mzed_set_ui(C,0);
253 }
254 return _mzed_addmul_blm(C, A, B);
255}
256
265static inline mzed_t *mzed_addmul_blm(mzed_t *C, const mzed_t *A, const mzed_t *B) {
266 assert(C != NULL);
267 if (A->ncols != B->nrows || A->finite_field != B->finite_field)
268 m4ri_die("mzed_addmul_blm: rows, columns and fields must match.\n");
269 if (C->finite_field != A->finite_field || C->nrows != A->nrows || C->ncols != B->ncols)
270 m4ri_die("mzed_addmul_blm: rows and columns of returned matrix must match.\n");
271 return _mzed_addmul_blm(C, A, B);
272}
273
274
286static inline void mzd_slice_rescale_row(mzd_slice_t *A, rci_t r, rci_t c, word x) {
287 mzd_slice_t *A_w = mzd_slice_init_window(A, r, 0, r+1, A->ncols);
288 mzed_t *A_we = mzed_cling(NULL, A_w);
289
290 mzed_rescale_row(A_we, r, c, x);
291
292 mzed_slice(A_w, A_we);
293 mzed_free(A_we);
295}
296
298
299/*
300 * a bunch of constants to make code more readable
301 */
302
303static const word x80008000 = 0x8000800080008000ULL;
304static const word x80808080 = 0x8080808080808080ULL;
305static const word x88888888 = 0x8888888888888888ULL;
306static const word xaaaaaaaa = 0xaaaaaaaaaaaaaaaaULL;
307static const word xcccccccc = 0xccccccccccccccccULL;
308static const word xc0c0c0c0 = 0xc0c0c0c0c0c0c0c0ULL;
309static const word xf0f0f0f0 = 0xf0f0f0f0f0f0f0f0ULL;
310static const word xff00ff00 = 0xff00ff00ff00ff00ULL;
311static const word xffff0000 = 0xffff0000ffff0000ULL;
312static const word xffffffff = 0xffffffff00000000ULL;
313static const word x__left04 = 0xf000000000000000ULL;
314static const word x__left08 = 0xff00000000000000ULL;
315static const word x__left16 = 0xffff000000000000ULL;
316static const word x__left32 = 0xffffffff00000000ULL;
317
319
320#endif //M4RIE_CONVERSION_H
mzed_t * _mzed_cling16(mzed_t *A, const mzd_slice_t *Z)
Pack a bitslice matrix into a classical represenation over for 8 < e <= 16.
Definition conversion_cling16.c:28
mzd_slice_t * _mzed_slice4(mzd_slice_t *A, const mzed_t *Z)
Unpack the matrix Z over into bitslice representation.
Definition conversion.c:214
mzed_t * _mzed_cling4(mzed_t *A, const mzd_slice_t *Z)
Pack a bitslice matrix into a classical represenation over for 2 < e <= 4.
Definition conversion.c:320
static mzed_t * _mzed_addmul_blm(mzed_t *C, const mzed_t *A, const mzed_t *B)
Compute C += A*B using Bilinear Maps over GF(2).
Definition conversion.h:215
mzed_t * _mzed_cling8(mzed_t *A, const mzd_slice_t *Z)
Pack a bitslice matrix into a classical represenation over for 4 < e <= 8.
Definition conversion_cling8.c:29
static mzed_t * mzed_mul_karatsuba(mzed_t *C, const mzed_t *A, const mzed_t *B)
Compute C = A*B.
Definition conversion.h:177
static mzed_t * mzed_addmul_blm(mzed_t *C, const mzed_t *A, const mzed_t *B)
Compute C += A*B.
Definition conversion.h:265
static mzed_t * mzed_addmul_karatsuba(mzed_t *C, const mzed_t *A, const mzed_t *B)
Compute C += A*B.
Definition conversion.h:196
static mzed_t * _mzed_addmul_karatsuba(mzed_t *C, const mzed_t *A, const mzed_t *B)
Compute C += A*B using Karatsuba multiplication of polynomials over GF(2).
Definition conversion.h:148
static mzed_t * mzed_mul_blm(mzed_t *C, const mzed_t *A, const mzed_t *B)
Compute C = A*B.
Definition conversion.h:246
mzed_t * _mzed_cling2(mzed_t *A, const mzd_slice_t *Z)
Pack a bitslice matrix into a classical represenation over GF(2^2).
Definition conversion.c:181
mzd_slice_t * _mzed_slice16(mzd_slice_t *A, const mzed_t *Z)
Unpack the matrix Z over into bitslice representation.
Definition conversion_slice16.c:50
mzd_slice_t * _mzed_slice2(mzd_slice_t *A, const mzed_t *Z)
Unpack the matrix Z over GF(2^2) into bitslice representation.
Definition conversion.c:121
mzd_slice_t * _mzed_slice8(mzd_slice_t *A, const mzed_t *Z)
Unpack the matrix Z over into bitslice representation.
Definition conversion_slice8.c:29
mzed_t * mzed_add(mzed_t *C, const mzed_t *A, const mzed_t *B)
.
Definition mzed.c:53
void mzed_set_ui(mzed_t *A, word value)
Return diagonal matrix with value on the diagonal.
Definition mzed.c:245
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
mzed_t * mzed_cling(mzed_t *A, const mzd_slice_t *Z)
Pack a bitslice matrix into a packed represenation.
Definition conversion.c:88
static void mzd_slice_free(mzd_slice_t *A)
Free a matrix created with mzd_slice_init().
Definition mzd_slice.h:145
mzd_slice_t * mzed_slice(mzd_slice_t *A, const mzed_t *Z)
Unpack the matrix Z into bitslice representation.
Definition conversion.c:56
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
void mzed_free(mzed_t *A)
Free a matrix created with mzed_init().
Definition mzed.c:39
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 void mzed_rescale_row(mzed_t *A, rci_t r, rci_t start_col, const word x)
Rescale the row r in A by X starting c.
Definition mzed.h:549
static void mzd_slice_rescale_row(mzd_slice_t *A, rci_t r, rci_t c, word x)
Recale the row r in A by X starting c.
Definition conversion.h:286
Matrices using a bitsliced representation.
Dense matrices over represented as packed matrices.
Dense matrices over represented as slices of matrices over .
Definition mzd_slice.h:56
rci_t ncols
Definition mzd_slice.h:59
Dense matrices over represented as packed matrices.
Definition mzed.h:59
const gf2e * finite_field
Definition mzed.h:61
rci_t nrows
Definition mzed.h:62
rci_t ncols
Definition mzed.h:63