1 /* This file is part of the gf2x library.
2
3 Copyright 2010, 2012, 2013, 2015
4 Richard Brent, Pierrick Gaudry, Emmanuel Thome', Paul Zimmermann
5
6 This program is free software; you can redistribute it and/or modify it
7 under the terms of either:
8 - If the archive contains a file named toom-gpl.c (not a trivial
9 placeholder), the GNU General Public License as published by the Free
10 Software Foundation; either version 3 of the License, or (at your
11 option) any later version.
12 - If the archive contains a file named toom-gpl.c which is a trivial
13 placeholder, the GNU Lesser General Public License as published by
14 the Free Software Foundation; either version 2.1 of the License, or
15 (at your option) any later version.
16
17 This program is distributed in the hope that it will be useful, but WITHOUT
18 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
19 FITNESS FOR A PARTICULAR PURPOSE. See the license text for more details.
20
21 You should have received a copy of the GNU General Public License as
22 well as the GNU Lesser General Public License along with this program;
23 see the files COPYING and COPYING.LIB. If not, write to the Free
24 Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
25 02110-1301, USA.
26 */
27
28 #ifndef GF2X_MUL3_H_
29 #define GF2X_MUL3_H_
30
31 #include "gf2x.h"
32 /* All gf2x source files for lowlevel functions must include gf2x-small.h
33 * This is mandatory for the tuning mechanism. */
34 #include "gf2x/gf2x-small.h"
35
36 #if GF2X_WORDSIZE != 64
37 #error "This code is for 64-bit only"
38 #endif
39
40 #ifndef GF2X_HAVE_PCLMUL_SUPPORT
41 #error "This code needs pclmul support"
42 #endif
43
44
45 /* XXX XXX XXX This is dangerous XXX XXX XXX
46 *
47 * we are here exposing gf2x_mul2b and gf2x_mul2c, with unprotected
48 * prefixes. If another source file happens to also define this functions
49 * with the same mechanism, both cannot coexist.
50 */
51 #undef GF2X_MUL2_H_
52 #define CARRY
53 #include "mul2cl.c"
54 #undef CARRY
55
56 #undef GF2X_MUL2_H_
57 #define BORROW
58 #include "mul2cl.c"
59 #undef BORROW
60
61 /* uses Montgomery's variant of Karatsuba for n=2k+1 odd,
62 with M(2k+1) = M(k) + 2M(k+1) - 1, see
63 Five, Six, and Seven-Term {K}aratsuba-Like Formulae,
64 IEEE Transactions on Computers, volume 54, number 3, pages 362-369, 2005 */
65 GF2X_STORAGE_CLASS_mul3 void
gf2x_mul3(unsigned long * c,const unsigned long * a,const unsigned long * b)66 gf2x_mul3 (unsigned long *c, const unsigned long *a, const unsigned long *b)
67 {
68 unsigned long d[2], aa[2], bb[2], p[4];
69
70 /* let A0 = {a, 2}, A1 = {a+2, 1}, B0 = {b, 2}, B1 = {b+2, 1} */
71
72 aa[0] = a[0] ^ a[2];
73 aa[1] = a[1];
74 bb[0] = b[0] ^ b[2];
75 bb[1] = b[1];
76
77 gf2x_mul2c (c, a, b, d);
78 /* {c, 4} = A0 * B0 and {d, 2} = {a+1, 1} * {b+1, 1} */
79
80 gf2x_mul2b (p, aa, bb, d);
81 /* {p, 4} = (A0 + A1) * (B0 + B1) */
82
83 gf2x_mul1 (c + 4, a[2], b[2]);
84
85 p[0] ^= c[0] ^ c[4];
86 p[1] ^= c[1] ^ c[5];
87
88 c[5] ^= p[3] ^ c[3];
89 c[4] ^= p[2] ^ c[2];
90 c[2] ^= p[0];
91 c[3] ^= p[1];
92 }
93
94 #endif /* GF2X_MUL3_H_ */
95