M4RI 20250128
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) | ((((b) << 32) ^ (b)) >> 32))
39
44#define __M4RI_MIX16(a, b) \
45 (((((a) << 16) ^ (a)) & __M4RI_CONVERT_TO_WORD(0xFFFF0000FFFF0000ull)) | \
46 ((((b) >> 16) ^ (b)) & __M4RI_CONVERT_TO_WORD(0x0000FFFF0000FFFFull)));
51#define __M4RI_MIX8(a, b) \
52 (((((a) << 8) ^ (a)) & __M4RI_CONVERT_TO_WORD(0xFF00FF00FF00FF00ull)) | \
53 ((((b) >> 8) ^ (b)) & __M4RI_CONVERT_TO_WORD(0x00FF00FF00FF00FFull)));
58#define __M4RI_MIX4(a, b) \
59 (((((a) << 4) ^ (a)) & __M4RI_CONVERT_TO_WORD(0xF0F0F0F0F0F0F0F0ull)) | \
60 ((((b) >> 4) ^ (b)) & __M4RI_CONVERT_TO_WORD(0x0F0F0F0F0F0F0F0Full)));
65#define __M4RI_MIX2(a, b) \
66 (((((a) << 2) ^ (a)) & __M4RI_CONVERT_TO_WORD(0xCCCCCCCCCCCCCCCCull)) | \
67 ((((b) >> 2) ^ (b)) & __M4RI_CONVERT_TO_WORD(0x3333333333333333ull)));
72#define __M4RI_MIX1(a, b) \
73 (((((a) << 1) ^ (a)) & __M4RI_CONVERT_TO_WORD(0xAAAAAAAAAAAAAAAAull)) | \
74 ((((b) >> 1) ^ (b)) & __M4RI_CONVERT_TO_WORD(0x5555555555555555ull)));
75
80static inline word m4ri_parity64_helper(word *buf) {
81 word a0, a1, b0, b1, c0, c1;
82
83 a0 = __M4RI_MIX32(buf[0x20], buf[0x00]);
84 a1 = __M4RI_MIX32(buf[0x30], buf[0x10]);
85 b0 = __M4RI_MIX16(a1, a0);
86
87 a0 = __M4RI_MIX32(buf[0x28], buf[0x08]);
88 a1 = __M4RI_MIX32(buf[0x38], buf[0x18]);
89 b1 = __M4RI_MIX16(a1, a0);
90
91 c0 = __M4RI_MIX8(b1, b0);
92
93 a0 = __M4RI_MIX32(buf[0x24], buf[0x04]);
94 a1 = __M4RI_MIX32(buf[0x34], buf[0x14]);
95 b0 = __M4RI_MIX16(a1, a0);
96
97 a0 = __M4RI_MIX32(buf[0x2C], buf[0x0C]);
98 a1 = __M4RI_MIX32(buf[0x3C], buf[0x1C]);
99 b1 = __M4RI_MIX16(a1, a0);
100
101 c1 = __M4RI_MIX8(b1, b0);
102
103 return __M4RI_MIX4(c1, c0);
104}
105
113static inline word m4ri_parity64(word *buf) {
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:44
static word m4ri_parity64_helper(word *buf)
See parity64.
Definition parity.h:80
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:113
#define __M4RI_MIX2(a, b)
Step for mixing two 64-bit words to compute their parity.
Definition parity.h:65
#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:58
#define __M4RI_MIX1(a, b)
Step for mixing two 64-bit words to compute their parity.
Definition parity.h:72