M4RI  1.0.1
parity.h
Go to the documentation of this file.
00001 #ifndef M4RI_PARITY_H
00002 #define M4RI_PARITY_H
00003 
00004 /*******************************************************************
00005 *
00006 *                 M4RI: Linear Algebra over GF(2)
00007 *
00008 *    Copyright (C) 2008 David Harvey <dmharvey@cims.nyu.edu>
00009 *
00010 *  Distributed under the terms of the GNU General Public License (GPL)
00011 *  version 2 or higher.
00012 *
00013 *    This code is distributed in the hope that it will be useful,
00014 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
00015 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00016 *    General Public License for more details.
00017 *
00018 *  The full text of the GPL is available at:
00019 *
00020 *                  http://www.gnu.org/licenses/
00021 *
00022 ********************************************************************/
00023 
00032 #include "misc.h"
00033 
00038 #define __M4RI_MIX32(a, b) (((((a) >> 32) ^ (a)) << 32) | \
00039                             ((((b) << 32) ^ (b)) >> 32))
00040 
00045 #define __M4RI_MIX16(a, b) (((((a) << 16) ^ (a)) & __M4RI_CONVERT_TO_WORD(0xFFFF0000FFFF0000ull)) | \
00046                             ((((b) >> 16) ^ (b)) & __M4RI_CONVERT_TO_WORD(0x0000FFFF0000FFFFull)));
00047 
00051 #define __M4RI_MIX8(a, b) (((((a) << 8) ^ (a)) & __M4RI_CONVERT_TO_WORD(0xFF00FF00FF00FF00ull)) | \
00052                            ((((b) >> 8) ^ (b)) & __M4RI_CONVERT_TO_WORD(0x00FF00FF00FF00FFull)));
00053 
00057 #define __M4RI_MIX4(a, b) (((((a) << 4) ^ (a)) & __M4RI_CONVERT_TO_WORD(0xF0F0F0F0F0F0F0F0ull)) | \
00058                            ((((b) >> 4) ^ (b)) & __M4RI_CONVERT_TO_WORD(0x0F0F0F0F0F0F0F0Full)));
00059 
00063 #define __M4RI_MIX2(a, b) (((((a) << 2) ^ (a)) & __M4RI_CONVERT_TO_WORD(0xCCCCCCCCCCCCCCCCull)) | \
00064                            ((((b) >> 2) ^ (b)) & __M4RI_CONVERT_TO_WORD(0x3333333333333333ull)));
00065 
00069 #define __M4RI_MIX1(a, b) (((((a) << 1) ^ (a)) & __M4RI_CONVERT_TO_WORD(0xAAAAAAAAAAAAAAAAull)) | \
00070                            ((((b) >> 1) ^ (b)) & __M4RI_CONVERT_TO_WORD(0x5555555555555555ull)));
00071 
00072 
00077 static inline word m4ri_parity64_helper(word *buf)
00078 {
00079    word a0, a1, b0, b1, c0, c1;
00080 
00081    a0 = __M4RI_MIX32(buf[0x20], buf[0x00]);
00082    a1 = __M4RI_MIX32(buf[0x30], buf[0x10]);
00083    b0 = __M4RI_MIX16(a1, a0);
00084 
00085    a0 = __M4RI_MIX32(buf[0x28], buf[0x08]);
00086    a1 = __M4RI_MIX32(buf[0x38], buf[0x18]);
00087    b1 = __M4RI_MIX16(a1, a0);
00088 
00089    c0 = __M4RI_MIX8(b1, b0);
00090 
00091    a0 = __M4RI_MIX32(buf[0x24], buf[0x04]);
00092    a1 = __M4RI_MIX32(buf[0x34], buf[0x14]);
00093    b0 = __M4RI_MIX16(a1, a0);
00094 
00095    a0 = __M4RI_MIX32(buf[0x2C], buf[0x0C]);
00096    a1 = __M4RI_MIX32(buf[0x3C], buf[0x1C]);
00097    b1 = __M4RI_MIX16(a1, a0);
00098 
00099    c1 = __M4RI_MIX8(b1, b0);
00100 
00101    return __M4RI_MIX4(c1, c0);
00102 }
00103 
00104 
00112 static inline word m4ri_parity64(word *buf)
00113 {
00114    word d0, d1, e0, e1;
00115 
00116    d0 = m4ri_parity64_helper(buf);
00117    d1 = m4ri_parity64_helper(buf + 2);
00118    e0 = __M4RI_MIX2(d1, d0);
00119 
00120    d0 = m4ri_parity64_helper(buf + 1);
00121    d1 = m4ri_parity64_helper(buf + 3);
00122    e1 = __M4RI_MIX2(d1, d0);
00123 
00124    return __M4RI_MIX1(e1, e0);
00125 }
00126 
00127 #endif // M4RI_PARITY_H