M4RI 20200125
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)));
51#define __M4RI_MIX8(a, b) (((((a) << 8) ^ (a)) & __M4RI_CONVERT_TO_WORD(0xFF00FF00FF00FF00ull)) | \
52 ((((b) >> 8) ^ (b)) & __M4RI_CONVERT_TO_WORD(0x00FF00FF00FF00FFull)));
57#define __M4RI_MIX4(a, b) (((((a) << 4) ^ (a)) & __M4RI_CONVERT_TO_WORD(0xF0F0F0F0F0F0F0F0ull)) | \
58 ((((b) >> 4) ^ (b)) & __M4RI_CONVERT_TO_WORD(0x0F0F0F0F0F0F0F0Full)));
63#define __M4RI_MIX2(a, b) (((((a) << 2) ^ (a)) & __M4RI_CONVERT_TO_WORD(0xCCCCCCCCCCCCCCCCull)) | \
64 ((((b) >> 2) ^ (b)) & __M4RI_CONVERT_TO_WORD(0x3333333333333333ull)));
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
77static 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
112static 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
Helper functions.
uint64_t word
A word is the typical packed data structure to represent packed bits.
Definition: misc.h:87
#define __M4RI_MIX16(a, b)
Step for mixing two 64-bit words to compute their parity.
Definition: parity.h:45
static word m4ri_parity64_helper(word *buf)
See parity64.
Definition: parity.h:77
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_MIX2(a, b)
Step for mixing two 64-bit words to compute their parity.
Definition: parity.h:63
#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_MIX4(a, b)
Step for mixing two 64-bit words to compute their parity.
Definition: parity.h:57
#define __M4RI_MIX1(a, b)
Step for mixing two 64-bit words to compute their parity.
Definition: parity.h:69