M4RI  20140914
ple_russian_template.h
1 #include <m4ri/misc.h>
2 
3 void __M4RI_TEMPLATE_NAME(_mzd_process_rows_ple)(mzd_t *M, rci_t startrow, rci_t stoprow, rci_t startcol, int const k[N], const ple_table_t *table[N]) {
4  assert(1 <= N && N <= 8);
5 
6  const mzd_t *T[N];
7  const rci_t *E[N];
8  const word *B[N];
9  word bm[N];
10  int sh[N];
11  int x[N];
12  const word * t[N];
13 
14  switch(N) { /* we rely on the compiler to optimise this switch away, it reads nicer than #if */
15  case 8: T[7] = table[7]->T; E[7] = table[7]->E; B[7] = table[7]->B; bm[7] = __M4RI_LEFT_BITMASK(k[7]); sh[7] = k[0] + k[1] + k[2] + k[3] + k[4] + k[5] + k[6];
16  case 7: T[6] = table[6]->T; E[6] = table[6]->E; B[6] = table[6]->B; bm[6] = __M4RI_LEFT_BITMASK(k[6]); sh[6] = k[0] + k[1] + k[2] + k[3] + k[4] + k[5];
17  case 6: T[5] = table[5]->T; E[5] = table[5]->E; B[5] = table[5]->B; bm[5] = __M4RI_LEFT_BITMASK(k[5]); sh[5] = k[0] + k[1] + k[2] + k[3] + k[4];
18  case 5: T[4] = table[4]->T; E[4] = table[4]->E; B[4] = table[4]->B; bm[4] = __M4RI_LEFT_BITMASK(k[4]); sh[4] = k[0] + k[1] + k[2] + k[3];
19  case 4: T[3] = table[3]->T; E[3] = table[3]->E; B[3] = table[3]->B; bm[3] = __M4RI_LEFT_BITMASK(k[3]); sh[3] = k[0] + k[1] + k[2];
20  case 3: T[2] = table[2]->T; E[2] = table[2]->E; B[2] = table[2]->B; bm[2] = __M4RI_LEFT_BITMASK(k[2]); sh[2] = k[0] + k[1];
21  case 2: T[1] = table[1]->T; E[1] = table[1]->E; B[1] = table[1]->B; bm[1] = __M4RI_LEFT_BITMASK(k[1]); sh[1] = k[0];
22  case 1: T[0] = table[0]->T; E[0] = table[0]->E; B[0] = table[0]->B; bm[0] = __M4RI_LEFT_BITMASK(k[0]); sh[0] = 0;
23  }
24 
25  wi_t const block = startcol / m4ri_radix;
26  wi_t const wide = M->width - block;
27 
28  for(rci_t r = startrow; r < stoprow; ++r) {
29  word bits = mzd_read_bits(M, r, startcol, sh[N-1] + k[N-1]);
30  word *m = M->rows[r] + block;
31 
32  switch(N) { /* we rely on the compiler to optimise this switch away, it reads nicer than #if */
33  case 8: x[ N-8 ] = E[ N-8 ][ (bits>> sh[ N-8 ]) & bm[ N-8 ] ]; bits ^= B[ N-8 ][x[ N-8 ]]; t[ N-8 ] = T[ N-8 ]->rows[x[ N-8 ]] + block;
34  case 7: x[ N-7 ] = E[ N-7 ][ (bits>> sh[ N-7 ]) & bm[ N-7 ] ]; bits ^= B[ N-7 ][x[ N-7 ]]; t[ N-7 ] = T[ N-7 ]->rows[x[ N-7 ]] + block;
35  case 6: x[ N-6 ] = E[ N-6 ][ (bits>> sh[ N-6 ]) & bm[ N-6 ] ]; bits ^= B[ N-6 ][x[ N-6 ]]; t[ N-6 ] = T[ N-6 ]->rows[x[ N-6 ]] + block;
36  case 5: x[ N-5 ] = E[ N-5 ][ (bits>> sh[ N-5 ]) & bm[ N-5 ] ]; bits ^= B[ N-5 ][x[ N-5 ]]; t[ N-5 ] = T[ N-5 ]->rows[x[ N-5 ]] + block;
37  case 4: x[ N-4 ] = E[ N-4 ][ (bits>> sh[ N-4 ]) & bm[ N-4 ] ]; bits ^= B[ N-4 ][x[ N-4 ]]; t[ N-4 ] = T[ N-4 ]->rows[x[ N-4 ]] + block;
38  case 3: x[ N-3 ] = E[ N-3 ][ (bits>> sh[ N-3 ]) & bm[ N-3 ] ]; bits ^= B[ N-3 ][x[ N-3 ]]; t[ N-3 ] = T[ N-3 ]->rows[x[ N-3 ]] + block;
39  case 2: x[ N-2 ] = E[ N-2 ][ (bits>> sh[ N-2 ]) & bm[ N-2 ] ]; bits ^= B[ N-2 ][x[ N-2 ]]; t[ N-2 ] = T[ N-2 ]->rows[x[ N-2 ]] + block;
40  case 1: x[ N-1 ] = E[ N-1 ][ (bits>> sh[ N-1 ]) & bm[ N-1 ] ]; bits ^= B[ N-1 ][x[ N-1 ]]; t[ N-1 ] = T[ N-1 ]->rows[x[ N-1 ]] + block;
41  }
42 
43  __M4RI_TEMPLATE_NAME(_mzd_combine)(m, t, wide);
44  }
45 
46  __M4RI_DD_MZD(M);
47 }
48 
49 void __M4RI_TEMPLATE_NAME(_mzd_ple_a11)(mzd_t *A,
50  rci_t const start_row, rci_t const stop_row, rci_t const start_col, wi_t const block,
51  int const k[N], ple_table_t const *table[N]) {
52 
53  wi_t const wide = A->width - block;
54 
55  if(wide <= 0)
56  return;
57 
58  const mzd_t *T[N];
59  const rci_t *M[N];
60  word bm[N];
61  int sh[N];
62  int x[N];
63  const word * t[N];
64 
65  switch(N) { /* we rely on the compiler to optimise this switch away, it reads nicer than #if */
66  case 8: T[7] = table[7]->T; M[7] = table[7]->M; bm[7] = __M4RI_LEFT_BITMASK(k[7]); sh[7] = k[0] + k[1] + k[2] + k[3] + k[4] + k[5] + k[6];
67  case 7: T[6] = table[6]->T; M[6] = table[6]->M; bm[6] = __M4RI_LEFT_BITMASK(k[6]); sh[6] = k[0] + k[1] + k[2] + k[3] + k[4] + k[5];
68  case 6: T[5] = table[5]->T; M[5] = table[5]->M; bm[5] = __M4RI_LEFT_BITMASK(k[5]); sh[5] = k[0] + k[1] + k[2] + k[3] + k[4];
69  case 5: T[4] = table[4]->T; M[4] = table[4]->M; bm[4] = __M4RI_LEFT_BITMASK(k[4]); sh[4] = k[0] + k[1] + k[2] + k[3];
70  case 4: T[3] = table[3]->T; M[3] = table[3]->M; bm[3] = __M4RI_LEFT_BITMASK(k[3]); sh[3] = k[0] + k[1] + k[2];
71  case 3: T[2] = table[2]->T; M[2] = table[2]->M; bm[2] = __M4RI_LEFT_BITMASK(k[2]); sh[2] = k[0] + k[1];
72  case 2: T[1] = table[1]->T; M[1] = table[1]->M; bm[1] = __M4RI_LEFT_BITMASK(k[1]); sh[1] = k[0];
73  case 1: T[0] = table[0]->T; M[0] = table[0]->M; bm[0] = __M4RI_LEFT_BITMASK(k[0]); sh[0] = 0;
74  };
75 
76  const rci_t bits_to_read = sh[N-1] + k[N-1];
77 
78  for(rci_t i = start_row; i < stop_row; ++i) {
79  const word bits = mzd_read_bits(A, i, start_col, bits_to_read);
80  word *m = A->rows[i] + block;
81 
82  switch(N) { /* we rely on the compiler to optimise this switch away, it reads nicer than #if */
83  case 8: x[ N-8 ] = M[ N-8 ][ (bits>> sh[ N-8 ]) & bm[ N-8 ] ]; t[ N-8 ] = T[ N-8 ]->rows[ x[ N-8 ] ] + block;
84  case 7: x[ N-7 ] = M[ N-7 ][ (bits>> sh[ N-7 ]) & bm[ N-7 ] ]; t[ N-7 ] = T[ N-7 ]->rows[ x[ N-7 ] ] + block;
85  case 6: x[ N-6 ] = M[ N-6 ][ (bits>> sh[ N-6 ]) & bm[ N-6 ] ]; t[ N-6 ] = T[ N-6 ]->rows[ x[ N-6 ] ] + block;
86  case 5: x[ N-5 ] = M[ N-5 ][ (bits>> sh[ N-5 ]) & bm[ N-5 ] ]; t[ N-5 ] = T[ N-5 ]->rows[ x[ N-5 ] ] + block;
87  case 4: x[ N-4 ] = M[ N-4 ][ (bits>> sh[ N-4 ]) & bm[ N-4 ] ]; t[ N-4 ] = T[ N-4 ]->rows[ x[ N-4 ] ] + block;
88  case 3: x[ N-3 ] = M[ N-3 ][ (bits>> sh[ N-3 ]) & bm[ N-3 ] ]; t[ N-3 ] = T[ N-3 ]->rows[ x[ N-3 ] ] + block;
89  case 2: x[ N-2 ] = M[ N-2 ][ (bits>> sh[ N-2 ]) & bm[ N-2 ] ]; t[ N-2 ] = T[ N-2 ]->rows[ x[ N-2 ] ] + block;
90  case 1: x[ N-1 ] = M[ N-1 ][ (bits>> sh[ N-1 ]) & bm[ N-1 ] ]; t[ N-1 ] = T[ N-1 ]->rows[ x[ N-1 ] ] + block;
91  }
92  __M4RI_TEMPLATE_NAME(_mzd_combine)(m, t, wide);
93  }
94  __M4RI_DD_MZD(A);
95 }
96 
static word mzd_read_bits(mzd_t const *M, rci_t const x, rci_t const y, int const n)
Definition: mzd.h:1002
static int const m4ri_radix
The number of bits in a word.
Definition: misc.h:141
Dense matrices over GF(2).
Definition: mzd.h:86
int rci_t
Type of row and column indexes.
Definition: misc.h:72
PLE Elimination Tables.
Definition: ple_russian.h:39
word ** rows
Definition: mzd.h:138
#define __M4RI_LEFT_BITMASK(n)
create a bit mask to zero out all but the (n - 1) % m4ri_radix + 1 leftmost bits. ...
Definition: misc.h:271
uint64_t word
A word is the typical packed data structure to represent packed bits.
Definition: misc.h:87
int wi_t
Type of word indexes.
Definition: misc.h:80