1 /* This file is part of the gf2x library.
2
3 Copyright 2007, 2008, 2009, 2010, 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 /* Generates low-level multiplication routines over GF(2)[x]. */
29
30 #include <stdio.h>
31 #include <stdlib.h>
32 #include <stdint.h>
33
main(int argc,char * argv[])34 int main(int argc, char *argv[])
35 {
36 unsigned long i;
37 unsigned long w, K, CHOP, REM, fn;
38 unsigned long MASK, mask2;
39
40 if (argc != 3) {
41 fprintf(stderr, "Usage: %s <wordsize> k\n", argv[0]);
42 exit(1);
43 }
44
45 w = atoi(argv[1]);
46 K = atoi(argv[2]);
47
48 printf(
49 "/* This file is part of the gf2x library.\n"
50 "\n"
51 " Copyright 2007, 2008, 2009, 2010, 2011, 2012, 2013\n"
52 " Richard Brent, Pierrick Gaudry, Emmanuel Thome', Paul Zimmermann\n"
53 "\n"
54 " This program is free software; you can redistribute it and/or modify it\n"
55 " under the terms of either:\n"
56 " - If the archive contains a file named toom-gpl.c (not a trivial\n"
57 " placeholder), the GNU General Public License as published by the Free\n"
58 " Software Foundation; either version 3 of the License, or (at your\n"
59 " option) any later version.\n"
60 " - If the archive contains a file named toom-gpl.c which is a trivial\n"
61 " placeholder, the GNU Lesser General Public License as published by\n"
62 " the Free Software Foundation; either version 2.1 of the License, or\n"
63 " (at your option) any later version.\n"
64 "\n"
65 " This program is distributed in the hope that it will be useful, but WITHOUT\n"
66 " ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or\n"
67 " FITNESS FOR A PARTICULAR PURPOSE. See the license text for more details.\n"
68 "\n"
69 " You should have received a copy of the GNU General Public License as\n"
70 " well as the GNU Lesser General Public License along with this program;\n"
71 " see the files COPYING and COPYING.LIB. If not, write to the Free\n"
72 " Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA\n"
73 " 02110-1301, USA.\n"
74 "*/\n"
75 "\n");
76 printf("#ifndef GF2X_MUL1_H_\n");
77 printf("#define GF2X_MUL1_H_\n");
78 printf("\n");
79 printf("/* This file was generated automatically with\n");
80 printf(" %s %lu %lu. Don't edit it! */\n",
81 argv[0], w, K);
82 printf("\n");
83 printf(
84 "#include \"gf2x.h\"\n"
85 "/* All gf2x source files for lowlevel functions must include gf2x-small.h\n"
86 " * This is mandatory for the tuning mechanism. */\n"
87 "#include \"gf2x/gf2x-small.h\"\n"
88 "\n");
89
90 for (fn = 0; fn < 3; fn++) {
91 if (fn == 0) {
92 printf("GF2X_STORAGE_CLASS_mul1 void\n");
93 printf("gf2x_mul1 (unsigned long *c, unsigned long a, unsigned long b)\n");
94 } else if (fn == 1) {
95 // continue; /* mul_1_n is no longer used */
96 printf("GF2X_STORAGE_CLASS_mul_1_n unsigned long\n");
97 printf
98 ("gf2x_mul_1_n (unsigned long *cp, const unsigned long *bp, long sb, unsigned long a)\n");
99 } else if (fn == 2) {
100 printf("GF2X_STORAGE_CLASS_addmul_1_n unsigned long\n");
101 printf
102 ("gf2x_addmul_1_n (unsigned long *dp, const unsigned long *cp, const unsigned long* bp, long sb,\n");
103 printf(" unsigned long a)\n");
104 }
105 printf("{\n");
106 if (fn > 0) { /* Mul1/AddMul1 */
107 printf(" long i;\n");
108 printf(" unsigned long carry = 0, b;\n");
109 }
110 printf(" unsigned long hi, lo, tmp, A[%lu];\n", 1UL << K);
111 printf("\n");
112 printf(" A[0] = 0;\t\t");
113 /* do not truncate: fix non-considered bit products afterwards */
114 printf("A[1] = a;\n");
115 for (i = 2u; i < (1u << K); i++) {
116 if (i % 2 == 0)
117 printf(" A[%lu] = A[%lu] << 1;\t", i, i / 2);
118 else
119 printf("A[%lu] = A[%lu] ^ a;\n", i, i - 1);
120 }
121 printf("\n");
122
123 if (fn > 0) {
124 printf(" for (i = 0; i < sb; i++)\n");
125 printf(" {\n");
126 printf(" b = bp[i];\n");
127 }
128 REM = w - 2 * K;
129 MASK = (1UL << K) - 1UL;
130 for (CHOP = 0; CHOP + 2 * K < w; CHOP += 2 * K);
131 CHOP = w - CHOP;
132 /* now 1 <= CHOP <= 2 * K, with w - CHOP multiple of 2K */
133 if (CHOP <= K) /* one slice is enough for the upper part */
134 printf(" lo = A[b >> %lu];\n", w - CHOP);
135 else /* two slices for the upper part */
136 printf(" lo = (A[b >> %lu] << %lu) ^ A[(b >> %lu) & %lu];\n",
137 w - (CHOP - K), K,
138 w - CHOP, MASK);
139 printf(" hi = lo >> %lu;\n", w - 2 * K);
140 for (i = w - CHOP - 2 * K; i >= 2 * K; i -= 2 * K) {
141 printf
142 (" lo = (lo << %lu) ^ (A[(b >> %lu) & %lu] << %lu) ^ A[(b >> %lu) & %lu];\n",
143 2 * K, i + K, MASK, K, i, MASK);
144 printf(" hi = (hi << %lu) | (lo >> %lu);\n", 2 * K, REM);
145 }
146 /* special case for i=0 since a shift of 0 is undefined */
147 printf
148 (" lo = (lo << %lu) ^ (A[(b >> %lu) & %lu] << %lu) ^ A[b & %lu];\n",
149 2 * K, K, MASK, K, MASK);
150
151 /* now perform the repair step for 2*K */
152 MASK = 0;
153 for (i = 0; i < w; i += 2 * K)
154 MASK |= 1UL << i;
155 MASK = ~MASK;
156 mask2 = MASK;
157 printf("\n");
158 for (i = 1; i < 2 * K; i++) {
159 /* bit w-i from a was not considered in blocks of
160 K bits from b for index j >= i */
161 /* Gaudry's no-branching optimization */
162 printf(" tmp = -((a >> %lu) & 1);\n", w - i);
163 if (w == 32) {
164 mask2 = (unsigned long) (uint32_t) mask2;
165 }
166 printf(" tmp &= ((b & 0x%lx) >> %lu);\n", mask2, i);
167 printf(" hi = hi ^ tmp;\n");
168 mask2 = (mask2 << 1) & MASK;
169 }
170 printf("\n");
171 if (fn == 0) {
172 printf(" c[0] = lo;\n");
173 printf(" c[1] = hi;\n");
174 } else if (fn == 1) {
175 printf(" cp[i] = carry ^ lo;\n");
176 printf(" carry = hi;\n");
177 } else if (fn == 2) {
178 printf(" dp[i] = cp[i] ^ (carry ^ lo);\n");
179 printf(" carry = hi;\n");
180 }
181 if (fn > 0) {
182 printf(" }\n");
183 printf(" return carry;\n");
184 }
185 printf("}\n\n");
186 }
187
188 printf("#endif\t/* GF2X_MUL1_H_ */\n");
189
190 return 0;
191 }
192