M4RI 1.0.1
parity.h
Go to the documentation of this file.
00001 #ifndef PARITY_H
00002 #define PARITY_H
00003 /*******************************************************************
00004 *
00005 *                 M4RI: Linear Algebra over GF(2)
00006 *
00007 *    Copyright (C) 2008 David Harvey <dmharvey@cims.nyu.edu>
00008 *
00009 *  Distributed under the terms of the GNU General Public License (GPL)
00010 *  version 2 or higher.
00011 *
00012 *    This code is distributed in the hope that it will be useful,
00013 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00015 *    General Public License for more details.
00016 *
00017 *  The full text of the GPL is available at:
00018 *
00019 *                  http://www.gnu.org/licenses/
00020 *
00021 ********************************************************************/
00022 
00035 #define MIX32(a, b) (((((a) << 32) ^ (a)) >> 32) + \
00036                      ((((b) >> 32) ^ (b)) << 32))
00037 
00042 #define MIX16(a, b) (((((a) >> 16) ^ (a)) & 0x0000FFFF0000FFFFll) +     \
00043                      ((((b) << 16) ^ (b)) & 0xFFFF0000FFFF0000ll));
00044 
00048 #define MIX8(a, b) (((((a) >> 8) ^ (a)) & 0x00FF00FF00FF00FFll) + \
00049                     ((((b) << 8) ^ (b)) & 0xFF00FF00FF00FF00ll));
00050 
00054 #define MIX4(a, b) (((((a) >> 4) ^ (a)) & 0x0F0F0F0F0F0F0F0Fll) + \
00055                     ((((b) << 4) ^ (b)) & 0xF0F0F0F0F0F0F0F0ll));
00056 
00060 #define MIX2(a, b) (((((a) >> 2) ^ (a)) & 0x3333333333333333ll) + \
00061                     ((((b) << 2) ^ (b)) & 0xCCCCCCCCCCCCCCCCll));
00062 
00066 #define MIX1(a, b) (((((a) >> 1) ^ (a)) & 0x5555555555555555ll) + \
00067                     ((((b) << 1) ^ (b)) & 0xAAAAAAAAAAAAAAAAll));
00068 
00069 
00074 static inline word _parity64_helper(word* buf)
00075 {
00076    word a0, a1, b0, b1, c0, c1;
00077 
00078    a0 = MIX32(buf[0x20], buf[0x00]);
00079    a1 = MIX32(buf[0x30], buf[0x10]);
00080    b0 = MIX16(a1, a0);
00081 
00082    a0 = MIX32(buf[0x28], buf[0x08]);
00083    a1 = MIX32(buf[0x38], buf[0x18]);
00084    b1 = MIX16(a1, a0);
00085 
00086    c0 = MIX8(b1, b0);
00087 
00088    a0 = MIX32(buf[0x24], buf[0x04]);
00089    a1 = MIX32(buf[0x34], buf[0x14]);
00090    b0 = MIX16(a1, a0);
00091 
00092    a0 = MIX32(buf[0x2C], buf[0x0C]);
00093    a1 = MIX32(buf[0x3C], buf[0x1C]);
00094    b1 = MIX16(a1, a0);
00095 
00096    c1 = MIX8(b1, b0);
00097 
00098    return MIX4(c1, c0);
00099 }
00100 
00101 
00109 static inline word parity64(word* buf)
00110 {
00111    word d0, d1, e0, e1;
00112 
00113    d0 = _parity64_helper(buf);
00114    d1 = _parity64_helper(buf + 2);
00115    e0 = MIX2(d1, d0);
00116 
00117    d0 = _parity64_helper(buf + 1);
00118    d1 = _parity64_helper(buf + 3);
00119    e1 = MIX2(d1, d0);
00120 
00121    return MIX1(e1, e0);
00122 }
00123 
00124 #endif