M4RI  20140914
parity.h
Go to the documentation of this file.
1 #ifndef M4RI_PARITY_H
2 #define M4RI_PARITY_H
3 
4 /*******************************************************************
5 *
6 * M4RI: Linear Algebra over GF(2)
7 *
8 * Copyright (C) 2008 David Harvey <dmharvey@cims.nyu.edu>
9 *
10 * Distributed under the terms of the GNU General Public License (GPL)
11 * version 2 or higher.
12 *
13 * This code is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * General Public License for more details.
17 *
18 * The full text of the GPL is available at:
19 *
20 * http://www.gnu.org/licenses/
21 *
22 ********************************************************************/
23 
32 #include <m4ri/misc.h>
33 
38 #define __M4RI_MIX32(a, b) (((((a) >> 32) ^ (a)) << 32) | \
39  ((((b) << 32) ^ (b)) >> 32))
40 
45 #define __M4RI_MIX16(a, b) (((((a) << 16) ^ (a)) & __M4RI_CONVERT_TO_WORD(0xFFFF0000FFFF0000ull)) | \
46  ((((b) >> 16) ^ (b)) & __M4RI_CONVERT_TO_WORD(0x0000FFFF0000FFFFull)));
47 
51 #define __M4RI_MIX8(a, b) (((((a) << 8) ^ (a)) & __M4RI_CONVERT_TO_WORD(0xFF00FF00FF00FF00ull)) | \
52  ((((b) >> 8) ^ (b)) & __M4RI_CONVERT_TO_WORD(0x00FF00FF00FF00FFull)));
53 
57 #define __M4RI_MIX4(a, b) (((((a) << 4) ^ (a)) & __M4RI_CONVERT_TO_WORD(0xF0F0F0F0F0F0F0F0ull)) | \
58  ((((b) >> 4) ^ (b)) & __M4RI_CONVERT_TO_WORD(0x0F0F0F0F0F0F0F0Full)));
59 
63 #define __M4RI_MIX2(a, b) (((((a) << 2) ^ (a)) & __M4RI_CONVERT_TO_WORD(0xCCCCCCCCCCCCCCCCull)) | \
64  ((((b) >> 2) ^ (b)) & __M4RI_CONVERT_TO_WORD(0x3333333333333333ull)));
65 
69 #define __M4RI_MIX1(a, b) (((((a) << 1) ^ (a)) & __M4RI_CONVERT_TO_WORD(0xAAAAAAAAAAAAAAAAull)) | \
70  ((((b) >> 1) ^ (b)) & __M4RI_CONVERT_TO_WORD(0x5555555555555555ull)));
71 
72 
77 static inline word m4ri_parity64_helper(word *buf)
78 {
79  word a0, a1, b0, b1, c0, c1;
80 
81  a0 = __M4RI_MIX32(buf[0x20], buf[0x00]);
82  a1 = __M4RI_MIX32(buf[0x30], buf[0x10]);
83  b0 = __M4RI_MIX16(a1, a0);
84 
85  a0 = __M4RI_MIX32(buf[0x28], buf[0x08]);
86  a1 = __M4RI_MIX32(buf[0x38], buf[0x18]);
87  b1 = __M4RI_MIX16(a1, a0);
88 
89  c0 = __M4RI_MIX8(b1, b0);
90 
91  a0 = __M4RI_MIX32(buf[0x24], buf[0x04]);
92  a1 = __M4RI_MIX32(buf[0x34], buf[0x14]);
93  b0 = __M4RI_MIX16(a1, a0);
94 
95  a0 = __M4RI_MIX32(buf[0x2C], buf[0x0C]);
96  a1 = __M4RI_MIX32(buf[0x3C], buf[0x1C]);
97  b1 = __M4RI_MIX16(a1, a0);
98 
99  c1 = __M4RI_MIX8(b1, b0);
100 
101  return __M4RI_MIX4(c1, c0);
102 }
103 
104 
112 static inline word m4ri_parity64(word *buf)
113 {
114  word d0, d1, e0, e1;
115 
116  d0 = m4ri_parity64_helper(buf);
117  d1 = m4ri_parity64_helper(buf + 2);
118  e0 = __M4RI_MIX2(d1, d0);
119 
120  d0 = m4ri_parity64_helper(buf + 1);
121  d1 = m4ri_parity64_helper(buf + 3);
122  e1 = __M4RI_MIX2(d1, d0);
123 
124  return __M4RI_MIX1(e1, e0);
125 }
126 
127 #endif // M4RI_PARITY_H
static word m4ri_parity64_helper(word *buf)
See parity64.
Definition: parity.h:77
#define __M4RI_MIX4(a, b)
Step for mixing two 64-bit words to compute their parity.
Definition: parity.h:57
static word m4ri_parity64(word *buf)
Computes parity of each of buf[0], buf[1], ..., buf[63]. Returns single word whose bits are the parit...
Definition: parity.h:112
#define __M4RI_MIX32(a, b)
Step for mixing two 64-bit words to compute their parity.
Definition: parity.h:38
#define __M4RI_MIX8(a, b)
Step for mixing two 64-bit words to compute their parity.
Definition: parity.h:51
#define __M4RI_MIX16(a, b)
Step for mixing two 64-bit words to compute their parity.
Definition: parity.h:45
#define __M4RI_MIX2(a, b)
Step for mixing two 64-bit words to compute their parity.
Definition: parity.h:63
#define __M4RI_MIX1(a, b)
Step for mixing two 64-bit words to compute their parity.
Definition: parity.h:69
uint64_t word
A word is the typical packed data structure to represent packed bits.
Definition: misc.h:87