1 /******************************************************************************
2 *
3 * M4RI: Linear Algebra over GF(2)
4 *
5 * Copyright (C) 2008 Martin Albrecht <malb@informatik.uni-bremen.de>
6 *
7 * Distributed under the terms of the GNU General Public License (GPL)
8 * version 2 or higher.
9 *
10 * This code is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * General Public License for more details.
14 *
15 * The full text of the GPL is available at:
16 *
17 * http://www.gnu.org/licenses/
18 ******************************************************************************/
19
20 #ifdef HAVE_CONFIG_H
21 #include "config.h"
22 #endif
23
24 #include "mzp.h"
25 #include "mzd.h"
26
mzp_init(rci_t length)27 mzp_t *mzp_init(rci_t length) {
28 mzp_t *P = (mzp_t*)m4ri_mm_malloc(sizeof(mzp_t));
29 P->values = (rci_t*)m4ri_mm_malloc(sizeof(rci_t) * length);
30 P->length = length;
31 for (rci_t i = 0; i < length; ++i) {
32 P->values[i] = i;
33 }
34 return P;
35 }
36
mzp_free(mzp_t * P)37 void mzp_free(mzp_t *P) {
38 m4ri_mm_free(P->values);
39 m4ri_mm_free(P);
40 }
41
mzp_init_window(mzp_t * P,rci_t begin,rci_t end)42 mzp_t *mzp_init_window(mzp_t *P, rci_t begin, rci_t end){
43 mzp_t *window = (mzp_t *)m4ri_mm_malloc(sizeof(mzp_t));
44 window->values = P->values + begin;
45 window->length = end - begin;
46 __M4RI_DD_MZP(window);
47 return window;
48 }
49
mzp_free_window(mzp_t * condemned)50 void mzp_free_window(mzp_t *condemned){
51 m4ri_mm_free(condemned);
52 }
53
mzp_copy(mzp_t * P,const mzp_t * Q)54 mzp_t *mzp_copy(mzp_t *P, const mzp_t *Q) {
55 if(P == NULL)
56 P = mzp_init(Q->length);
57 for(rci_t i=0; i<Q->length; i++)
58 P->values[i] = Q->values[i];
59 return P;
60 }
61
mzp_set_ui(mzp_t * P,unsigned int value)62 void mzp_set_ui(mzp_t *P, unsigned int value) {
63 assert(value == 1);
64 for (rci_t i = 0; i < P->length; ++i) {
65 P->values[i] = i;
66 }
67 }
68
mzd_apply_p_left(mzd_t * A,mzp_t const * P)69 void mzd_apply_p_left(mzd_t *A, mzp_t const *P) {
70 if(A->ncols == 0)
71 return;
72 rci_t const length = MIN(P->length, A->nrows);
73 for (rci_t i = 0; i < length; ++i) {
74 assert(P->values[i] >= i);
75 mzd_row_swap(A, i, P->values[i]);
76 }
77 }
78
mzd_apply_p_left_trans(mzd_t * A,mzp_t const * P)79 void mzd_apply_p_left_trans(mzd_t *A, mzp_t const *P) {
80 if(A->ncols == 0)
81 return;
82 rci_t const length = MIN(P->length, A->nrows);
83 for (rci_t i = length - 1; i >= 0; --i) {
84 assert(P->values[i] >= i);
85 mzd_row_swap(A, i, P->values[i]);
86 }
87 }
88
89 /* optimised column swap operations */
90
mzd_write_col_to_rows_blockd(mzd_t * A,mzd_t const * B,rci_t const * permutation,word const * write_mask,rci_t const start_row,rci_t const stop_row,rci_t length)91 static inline void mzd_write_col_to_rows_blockd(mzd_t *A, mzd_t const *B, rci_t const *permutation, word const *write_mask, rci_t const start_row, rci_t const stop_row, rci_t length) {
92 for(rci_t i = 0; i < length; i += m4ri_radix) {
93 /* optimisation for identity permutations */
94 if (write_mask[i / m4ri_radix] == m4ri_ffff)
95 continue;
96 int const todo = MIN(m4ri_radix, length - i);
97 wi_t const a_word = i / m4ri_radix;
98 wi_t words[m4ri_radix];
99 int bits[m4ri_radix];
100 word bitmasks[m4ri_radix];
101
102 /* we pre-compute bit access in advance */
103 for(int k = 0; k < todo; ++k) {
104 rci_t const colb = permutation[i + k];
105 words[k] = colb / m4ri_radix;
106 bits[k] = colb % m4ri_radix;
107 bitmasks[k] = m4ri_one << bits[k];
108 }
109
110 for (rci_t r = start_row; r < stop_row; ++r) {
111 word const *Brow = B->rows[r-start_row];
112 word *Arow = A->rows[r];
113 register word value = 0;
114
115 /* we gather the bits in a register word */
116 switch(todo-1) {
117 case 63: value |= ((Brow[words[63]] & bitmasks[63]) >> bits[63]) << 63;
118 case 62: value |= ((Brow[words[62]] & bitmasks[62]) >> bits[62]) << 62;
119 case 61: value |= ((Brow[words[61]] & bitmasks[61]) >> bits[61]) << 61;
120 case 60: value |= ((Brow[words[60]] & bitmasks[60]) >> bits[60]) << 60;
121 case 59: value |= ((Brow[words[59]] & bitmasks[59]) >> bits[59]) << 59;
122 case 58: value |= ((Brow[words[58]] & bitmasks[58]) >> bits[58]) << 58;
123 case 57: value |= ((Brow[words[57]] & bitmasks[57]) >> bits[57]) << 57;
124 case 56: value |= ((Brow[words[56]] & bitmasks[56]) >> bits[56]) << 56;
125 case 55: value |= ((Brow[words[55]] & bitmasks[55]) >> bits[55]) << 55;
126 case 54: value |= ((Brow[words[54]] & bitmasks[54]) >> bits[54]) << 54;
127 case 53: value |= ((Brow[words[53]] & bitmasks[53]) >> bits[53]) << 53;
128 case 52: value |= ((Brow[words[52]] & bitmasks[52]) >> bits[52]) << 52;
129 case 51: value |= ((Brow[words[51]] & bitmasks[51]) >> bits[51]) << 51;
130 case 50: value |= ((Brow[words[50]] & bitmasks[50]) >> bits[50]) << 50;
131 case 49: value |= ((Brow[words[49]] & bitmasks[49]) >> bits[49]) << 49;
132 case 48: value |= ((Brow[words[48]] & bitmasks[48]) >> bits[48]) << 48;
133 case 47: value |= ((Brow[words[47]] & bitmasks[47]) >> bits[47]) << 47;
134 case 46: value |= ((Brow[words[46]] & bitmasks[46]) >> bits[46]) << 46;
135 case 45: value |= ((Brow[words[45]] & bitmasks[45]) >> bits[45]) << 45;
136 case 44: value |= ((Brow[words[44]] & bitmasks[44]) >> bits[44]) << 44;
137 case 43: value |= ((Brow[words[43]] & bitmasks[43]) >> bits[43]) << 43;
138 case 42: value |= ((Brow[words[42]] & bitmasks[42]) >> bits[42]) << 42;
139 case 41: value |= ((Brow[words[41]] & bitmasks[41]) >> bits[41]) << 41;
140 case 40: value |= ((Brow[words[40]] & bitmasks[40]) >> bits[40]) << 40;
141 case 39: value |= ((Brow[words[39]] & bitmasks[39]) >> bits[39]) << 39;
142 case 38: value |= ((Brow[words[38]] & bitmasks[38]) >> bits[38]) << 38;
143 case 37: value |= ((Brow[words[37]] & bitmasks[37]) >> bits[37]) << 37;
144 case 36: value |= ((Brow[words[36]] & bitmasks[36]) >> bits[36]) << 36;
145 case 35: value |= ((Brow[words[35]] & bitmasks[35]) >> bits[35]) << 35;
146 case 34: value |= ((Brow[words[34]] & bitmasks[34]) >> bits[34]) << 34;
147 case 33: value |= ((Brow[words[33]] & bitmasks[33]) >> bits[33]) << 33;
148 case 32: value |= ((Brow[words[32]] & bitmasks[32]) >> bits[32]) << 32;
149 case 31: value |= ((Brow[words[31]] & bitmasks[31]) >> bits[31]) << 31;
150 case 30: value |= ((Brow[words[30]] & bitmasks[30]) >> bits[30]) << 30;
151 case 29: value |= ((Brow[words[29]] & bitmasks[29]) >> bits[29]) << 29;
152 case 28: value |= ((Brow[words[28]] & bitmasks[28]) >> bits[28]) << 28;
153 case 27: value |= ((Brow[words[27]] & bitmasks[27]) >> bits[27]) << 27;
154 case 26: value |= ((Brow[words[26]] & bitmasks[26]) >> bits[26]) << 26;
155 case 25: value |= ((Brow[words[25]] & bitmasks[25]) >> bits[25]) << 25;
156 case 24: value |= ((Brow[words[24]] & bitmasks[24]) >> bits[24]) << 24;
157 case 23: value |= ((Brow[words[23]] & bitmasks[23]) >> bits[23]) << 23;
158 case 22: value |= ((Brow[words[22]] & bitmasks[22]) >> bits[22]) << 22;
159 case 21: value |= ((Brow[words[21]] & bitmasks[21]) >> bits[21]) << 21;
160 case 20: value |= ((Brow[words[20]] & bitmasks[20]) >> bits[20]) << 20;
161 case 19: value |= ((Brow[words[19]] & bitmasks[19]) >> bits[19]) << 19;
162 case 18: value |= ((Brow[words[18]] & bitmasks[18]) >> bits[18]) << 18;
163 case 17: value |= ((Brow[words[17]] & bitmasks[17]) >> bits[17]) << 17;
164 case 16: value |= ((Brow[words[16]] & bitmasks[16]) >> bits[16]) << 16;
165 case 15: value |= ((Brow[words[15]] & bitmasks[15]) >> bits[15]) << 15;
166 case 14: value |= ((Brow[words[14]] & bitmasks[14]) >> bits[14]) << 14;
167 case 13: value |= ((Brow[words[13]] & bitmasks[13]) >> bits[13]) << 13;
168 case 12: value |= ((Brow[words[12]] & bitmasks[12]) >> bits[12]) << 12;
169 case 11: value |= ((Brow[words[11]] & bitmasks[11]) >> bits[11]) << 11;
170 case 10: value |= ((Brow[words[10]] & bitmasks[10]) >> bits[10]) << 10;
171 case 9: value |= ((Brow[words[ 9]] & bitmasks[ 9]) >> bits[ 9]) << 9;
172 case 8: value |= ((Brow[words[ 8]] & bitmasks[ 8]) >> bits[ 8]) << 8;
173 case 7: value |= ((Brow[words[ 7]] & bitmasks[ 7]) >> bits[ 7]) << 7;
174 case 6: value |= ((Brow[words[ 6]] & bitmasks[ 6]) >> bits[ 6]) << 6;
175 case 5: value |= ((Brow[words[ 5]] & bitmasks[ 5]) >> bits[ 5]) << 5;
176 case 4: value |= ((Brow[words[ 4]] & bitmasks[ 4]) >> bits[ 4]) << 4;
177 case 3: value |= ((Brow[words[ 3]] & bitmasks[ 3]) >> bits[ 3]) << 3;
178 case 2: value |= ((Brow[words[ 2]] & bitmasks[ 2]) >> bits[ 2]) << 2;
179 case 1: value |= ((Brow[words[ 1]] & bitmasks[ 1]) >> bits[ 1]) << 1;
180 case 0: value |= ((Brow[words[ 0]] & bitmasks[ 0]) >> bits[ 0]) << 0;
181 default:
182 break;
183 }
184 /* for(int k = 0; k < todo; ++k) { */
185 /* value |= ((Brow[words[k]] & bitmasks[k]) << bits[k]) >> k; */
186 /* } */
187 /* and write the word once */
188 Arow[a_word] |= value;
189 }
190 }
191
192 __M4RI_DD_MZD(A);
193 }
194
195 /**
196 * Implements both apply_p_right and apply_p_right_trans.
197 */
_mzd_apply_p_right_even(mzd_t * A,mzp_t const * P,rci_t start_row,rci_t start_col,int notrans)198 void _mzd_apply_p_right_even(mzd_t *A, mzp_t const *P, rci_t start_row, rci_t start_col, int notrans) {
199 if(A->nrows - start_row == 0)
200 return;
201 rci_t const length = MIN(P->length, A->ncols);
202 wi_t const width = A->width;
203 int step_size = MIN(A->nrows - start_row, MAX((__M4RI_CPU_L1_CACHE >> 3) / A->width, 1));
204
205 /* our temporary where we store the columns we want to swap around */
206 mzd_t *B = mzd_init(step_size, A->ncols);
207 word *Arow;
208 word *Brow;
209
210 /* setup mathematical permutation */
211 rci_t *permutation = (rci_t*)m4ri_mm_calloc(A->ncols, sizeof(rci_t));
212 for(rci_t i = 0; i < A->ncols; ++i)
213 permutation[i] = i;
214
215 if (!notrans) {
216 for(rci_t i = start_col; i < length; ++i) {
217 rci_t t = permutation[i];
218 permutation[i] = permutation[P->values[i]];
219 permutation[P->values[i]] = t;
220 }
221 } else {
222 for(rci_t i = start_col; i < length; ++i) {
223 rci_t t = permutation[length - i - 1];
224 permutation[length - i - 1] = permutation[P->values[length - i - 1]];
225 permutation[P->values[length - i - 1]] = t;
226 }
227 }
228
229 /* we have a bitmask to encode where to write to */
230 word *write_mask = (word*)m4ri_mm_calloc(width, sizeof(word));
231 for(rci_t i = 0; i < A->ncols; i += m4ri_radix) {
232 int const todo = MIN(m4ri_radix, A->ncols - i);
233 for(int k = 0; k < todo; ++k) {
234 if(permutation[i + k] == i + k) {
235 write_mask[i / m4ri_radix] |= m4ri_one << k;
236 }
237 }
238 }
239 write_mask[width-1] |= ~A->high_bitmask;
240
241 for(rci_t i = start_row; i < A->nrows; i += step_size) {
242 step_size = MIN(step_size, A->nrows - i);
243 for(int k = 0; k < step_size; ++k) {
244 Arow = A->rows[i+k];
245 Brow = B->rows[k];
246
247 /*copy row & clear those values which will be overwritten */
248 for(wi_t j = 0; j < width; ++j) {
249 Brow[j] = Arow[j];
250 Arow[j] = Arow[j] & write_mask[j];
251 }
252 }
253 /* here we actually write out the permutation */
254 mzd_write_col_to_rows_blockd(A, B, permutation, write_mask, i, i + step_size, length);
255 }
256 m4ri_mm_free(permutation);
257 m4ri_mm_free(write_mask);
258 mzd_free(B);
259
260 __M4RI_DD_MZD(A);
261 }
262
_mzd_apply_p_right_trans(mzd_t * A,mzp_t const * P)263 void _mzd_apply_p_right_trans(mzd_t *A, mzp_t const *P) {
264 if(A->nrows == 0)
265 return;
266 rci_t const length = MIN(P->length, A->ncols);
267 int const step_size = MAX((__M4RI_CPU_L1_CACHE >> 3) / A->width, 1);
268 for(rci_t j = 0; j < A->nrows; j += step_size) {
269 rci_t stop_row = MIN(j + step_size, A->nrows);
270 for (rci_t i = 0; i < length; ++i) {
271 assert(P->values[i] >= i);
272 mzd_col_swap_in_rows(A, i, P->values[i], j, stop_row);
273 }
274 }
275 /* for (i=0; i<P->length; i++) { */
276 /* assert(P->values[i] >= i); */
277 /* mzd_col_swap(A, i, P->values[i]); */
278 /* } */
279
280 __M4RI_DD_MZD(A);
281 }
282
_mzd_apply_p_right(mzd_t * A,mzp_t const * P)283 void _mzd_apply_p_right(mzd_t *A, mzp_t const *P) {
284 if(A->nrows == 0)
285 return;
286 int const step_size = MAX((__M4RI_CPU_L1_CACHE >> 3) / A->width, 1);
287 for(rci_t j = 0; j < A->nrows; j += step_size) {
288 rci_t stop_row = MIN(j + step_size, A->nrows);
289 for (rci_t i = P->length - 1; i >= 0; --i) {
290 assert(P->values[i] >= i);
291 mzd_col_swap_in_rows(A, i, P->values[i], j, stop_row);
292 }
293 }
294 /* long i; */
295 /* for (i=P->length-1; i>=0; i--) { */
296 /* assert(P->values[i] >= i); */
297 /* mzd_col_swap(A, i, P->values[i]); */
298 /* } */
299
300 __M4RI_DD_MZD(A);
301 }
302
303
mzd_apply_p_right_trans(mzd_t * A,mzp_t const * P)304 void mzd_apply_p_right_trans(mzd_t *A, mzp_t const *P) {
305 if(!A->nrows)
306 return;
307 _mzd_apply_p_right_even(A, P, 0, 0, 0);
308 }
309
mzd_apply_p_right(mzd_t * A,mzp_t const * P)310 void mzd_apply_p_right(mzd_t *A, mzp_t const *P) {
311 if(!A->nrows)
312 return;
313 _mzd_apply_p_right_even(A, P, 0, 0, 1);
314 }
315
mzd_apply_p_right_trans_even_capped(mzd_t * A,mzp_t const * P,rci_t start_row,rci_t start_col)316 void mzd_apply_p_right_trans_even_capped(mzd_t *A, mzp_t const *P, rci_t start_row, rci_t start_col) {
317 if(!A->nrows)
318 return;
319 _mzd_apply_p_right_even(A, P, start_row, start_col, 0);
320 }
321
mzd_apply_p_right_even_capped(mzd_t * A,mzp_t const * P,rci_t start_row,rci_t start_col)322 void mzd_apply_p_right_even_capped(mzd_t *A, mzp_t const *P, rci_t start_row, rci_t start_col) {
323 if(!A->nrows)
324 return;
325 _mzd_apply_p_right_even(A, P, start_row, start_col, 1);
326 }
327
mzp_print(mzp_t const * P)328 void mzp_print(mzp_t const *P) {
329 printf("[ ");
330 for(rci_t i = 0; i < P->length; ++i) {
331 printf("%zd ", (size_t)P->values[i]);
332 }
333 printf("]");
334 }
335
mzd_apply_p_right_trans_tri(mzd_t * A,mzp_t const * P)336 void mzd_apply_p_right_trans_tri(mzd_t *A, mzp_t const *P) {
337 assert(P->length == A->ncols);
338 int const step_size = MAX((__M4RI_CPU_L1_CACHE >> 2) / A->width, 1);
339
340 for(rci_t r = 0; r < A->nrows; r += step_size) {
341 rci_t const row_bound = MIN(r + step_size, A->nrows);
342 for (rci_t i =0 ; i < A->ncols; ++i) {
343 assert(P->values[i] >= i);
344 mzd_col_swap_in_rows(A, i, P->values[i], r, MIN(row_bound, i));
345 }
346 }
347
348 __M4RI_DD_MZD(A);
349 }
350
_mzd_compress_l(mzd_t * A,rci_t r1,rci_t n1,rci_t r2)351 void _mzd_compress_l(mzd_t *A, rci_t r1, rci_t n1, rci_t r2) {
352 /**
353 * We are compressing this matrix
354 \verbatim
355 r1 n1
356 ------------------------------------------
357 | \ \____|___ | A01 |
358 | \ | \ | |
359 r1------------------------------------------
360 | | | | \ \_____ |
361 | L1| | | \ \________|
362 | | | | L2| |
363 ------------------------------------------
364 \endverbatim
365 *
366 * to this matrix
367 *
368 \verbatim
369 r1 n1
370 ------------------------------------------
371 | \ \____|___ | A01 |
372 | \ | \ | |
373 r1------------------------------------------
374 | \ | | \_____ |
375 | \ | | \________|
376 | | | | |
377 ------------------------------------------
378 \endverbatim
379 */
380
381 if (r1 == n1)
382 return;
383
384 #if 0
385
386 mzp_t *shift = mzp_init(A->ncols);
387 for (rci_t i=r1,j=n1;i<r1+r2;i++,j++){
388 mzd_col_swap_in_rows(A, i, j, i, r1+r2);
389 shift->values[i] = j;
390 }
391
392 mzd_apply_p_right_trans_even_capped(A, shift, r1+r2, 0);
393 mzp_free(shift);
394
395 #else
396
397 for (rci_t i = r1, j = n1; i < r1 + r2; ++i, ++j){
398 mzd_col_swap_in_rows(A, i, j, i, r1 + r2);
399 }
400
401 word tmp;
402 wi_t block;
403
404 for(rci_t i = r1 + r2; i < A->nrows; ++i) {
405
406 rci_t j = r1;
407
408 /* first we deal with the rest of the current word we need to
409 write */
410 int const rest = m4ri_radix - (j % m4ri_radix);
411
412 tmp = mzd_read_bits(A, i, n1, rest);
413 mzd_clear_bits(A, i, j, rest);
414 mzd_xor_bits(A, i, j, rest, tmp);
415
416 j += rest;
417
418 /* now each write is simply a word write */
419
420 block = (n1 + j - r1) / m4ri_radix;
421
422 if (rest % m4ri_radix == 0) {
423 for( ; j + m4ri_radix <= r1 + r2; j += m4ri_radix, ++block) {
424 tmp = A->rows[i][block];
425 A->rows[i][j / m4ri_radix] = tmp;
426 }
427 } else {
428 for(; j + m4ri_radix <= r1 + r2; j += m4ri_radix, ++block) {
429 tmp = (A->rows[i][block] >> rest) | ( A->rows[i][block + 1] << (m4ri_radix - rest));
430 A->rows[i][j / m4ri_radix] = tmp;
431 }
432 }
433
434 /* we deal with the remaining bits. While we could write past the
435 end of r1+r2 here, but we have no guarantee that we can read
436 past the end of n1+r2. */
437
438 if (j < r1 + r2) {
439 tmp = mzd_read_bits(A, i, n1 + j - r1, r1 + r2 - j);
440 A->rows[i][j / m4ri_radix] = tmp;
441 }
442
443 /* now clear the rest of L2 */
444 j = r1 + r2;
445 mzd_clear_bits(A, i, j, m4ri_radix - (j % m4ri_radix));
446
447 j += m4ri_radix - (j % m4ri_radix);
448
449 /* it's okay to write the full word, i.e. past n1+r2, because
450 everything is zero there anyway. Thus, we can omit the code
451 which deals with last few bits. */
452
453 for(; j < n1 + r2; j += m4ri_radix) {
454 A->rows[i][j / m4ri_radix] = 0;
455 }
456 }
457
458 #endif
459
460 __M4RI_DD_MZD(A);
461 }
462
463