1 //
2 // Program to generate code for reduction modulo an irreducible trinomial or pentanomial
3 // over the field GF(2^m), m a prime
4 //
5 // cl /O2 /GX irp.cpp
6 //
7 // code is generated and can be cut-and-pasted into the function
8 // reduce2(.) in the MIRACL module mrgf2m.c
9 //
10 // To find a suitable irreducible polynomial, see the program findbase.cpp
11 //
12 
13 
14 #include <iostream>
15 
16 using namespace std;
17 
main(int argc,char * argv[])18 int main(int argc, char *argv[])
19 {
20     int i,j,W,M,A,B,C,k1,k2,k3,k4,rs1,rs2,rs3,rs4,ls1,ls2,ls3,ls4;
21     int ind[64],shift[64][8],xxor,nxor,nsh;
22 
23 	argc--; argv++;
24 
25     if (argc<3 || argc>5)
26     {
27         cout << "incorrect usage" << endl;
28         cout << "Program generates reduction code for given irreducible polynomial" << endl;
29         cout << "of the form x^M+x^A+1 or x^M+x^A+x^B+x^C+1 for odd M" << endl;
30         cout << "for a computer with wordlength W" << endl;
31         cout << "irp <W> <M> <A>" << endl;
32         cout << "OR" << endl;
33         cout << "irp <W> <M> <A> <B> <C>" << endl;
34         cout << "The code that is generated can be copied into the" << endl;
35         cout << "function reduce2 in the module mrgf2m.c" << endl;
36         return 0;
37     }
38 
39     A=B=C=0;
40     W=atoi(argv[0]);
41     M=atoi(argv[1]);
42 	A=atoi(argv[2]);
43     if (W<0 || W%8!=0 || A<1 || M-A < W) exit(0);
44 
45     if (argc==5)
46     {
47         B=atoi(argv[3]);
48         C=atoi(argv[4]);
49         if (B<1 || C<1 || B>A || C>B) exit(0);
50     }
51 
52     k1=1+M/W;
53 
54     rs1=M%W;
55     ls1=W-rs1;
56 
57     k2=1+(M-A)/W;
58 
59     rs2=(M-A)%W;
60     ls2=W-rs2;
61 
62     if (B)
63     {
64         k3=1+(M-B)/W;
65         rs3=(M-B)%W;
66         ls3=W-rs3;
67 
68         k4=1+(M-C)/W;
69         rs4=(M-C)%W;
70         ls4=W-rs4;
71     }
72 
73     for (i=0;i<64;i++) ind[i]=0;
74 
75     if (rs1==0)
76     {
77         shift[k1-1][ind[k1-1]]=0;
78         ind[k1-1]++;
79     }
80     else
81     {
82         shift[k1-1][ind[k1-1]]=rs1;
83         ind[k1-1]++;
84         shift[k1][ind[k1]]=-ls1;
85         ind[k1]++;
86     }
87 
88     if (rs2==0)
89     {
90         shift[k2-1][ind[k2-1]]=0;
91         ind[k2-1]++;
92     }
93     else
94     {
95         shift[k2-1][ind[k2-1]]=rs2;
96         ind[k2-1]++;
97         shift[k2][ind[k2]]=-ls2;
98         ind[k2]++;
99     }
100 
101     if (B)
102     {
103         if (rs3==0)
104         {
105             shift[k3-1][ind[k3-1]]=0;
106             ind[k3-1]++;
107         }
108         else
109         {
110             shift[k3-1][ind[k3-1]]=rs3;
111             ind[k3-1]++;
112             shift[k3][ind[k3]]=-ls3;
113             ind[k3]++;
114         }
115         if (rs4==0)
116         {
117             shift[k4-1][ind[k4-1]]=0;
118             ind[k4-1]++;
119         }
120         else
121         {
122             shift[k4-1][ind[k4-1]]=rs4;
123             ind[k4-1]++;
124             shift[k4][ind[k4]]=-ls4;
125             ind[k4]++;
126         }
127     }
128 
129     if (B) printf("    if (M==%d && A==%d && B==%d && C==%d)\n",M,A,B,C);
130     else   printf("    if (M==%d && A==%d)\n",M,A);
131 
132     printf("    {\n        for (i=xl-1;i>=%d;i--)\n        {\n",k1);
133     printf("            w=gx[i]; gx[i]=0;\n");
134 
135     nxor=0; nsh=0;
136     for (i=0;i<64;i++)
137     {
138         if (ind[i]==0) continue;
139         nxor++;
140         printf("            gx[i-%d]^=",i);
141         xxor=0;
142         for (j=0;j<ind[i];j++)
143         {
144             if (xxor) printf("^");
145             if (shift[i][j]==0) {printf("w"); xxor++;}
146             if (shift[i][j]>0) {printf("(w>>%d)",shift[i][j]); xxor++; nsh++; }
147             if (shift[i][j]<0) {printf("(w<<%d)",-shift[i][j]); xxor++; nsh++;}
148         }
149 
150         nxor+=(xxor-1);
151         printf(";\n");
152     }
153     printf("        }   /* XORs= %d shifts= %d */\n",nxor,nsh);
154     printf("        top=gx[%d]>>%d; ",k1-1,rs1);
155     printf("gx[0]^=top; ");
156     printf("top<<=%d;\n",rs1);
157 
158     for (i=0;i<64;i++) ind[i]=0;
159 
160     if (rs2==0)
161     {
162         shift[k1-k2][ind[k1-k2]]=0;
163         ind[k1-k2]++;
164     }
165     else
166     {
167         shift[k1-k2][ind[k1-k2]]=rs2;
168         ind[k1-k2]++;
169         if (k1>k2)
170         {
171             shift[k1-k2-1][ind[k1-k2-1]]=-ls2;
172             ind[k1-k2-1]++;
173         }
174     }
175 
176     if (B)
177     {
178         if (rs3==0)
179         {
180             shift[k1-k3][ind[k1-k3]]=0;
181             ind[k1-k3]++;
182         }
183         else
184         {
185             shift[k1-k3][ind[k1-k3]]=rs3;
186             ind[k1-k3]++;
187             if (k1>k3)
188             {
189                 shift[k1-k3-1][ind[k1-k3-1]]=-ls3;
190                 ind[k1-k3-1]++;
191             }
192         }
193         if (rs4==0)
194         {
195             shift[k1-k4][ind[k1-k4]]=0;
196             ind[k1-k4]++;
197         }
198         else
199         {
200             shift[k1-k4][ind[k1-k4]]=rs4;
201             ind[k1-k4]++;
202             if (k1>k4)
203             {
204                 shift[k1-k4-1][ind[k1-k4-1]]=-ls4;
205                 ind[k1-k4-1]++;
206             }
207         }
208     }
209 
210     for (i=0;i<64;i++)
211     {
212         if (ind[i]==0) continue;
213         printf("        gx[%d]^=",i);
214         xxor=0;
215         for (j=0;j<ind[i];j++)
216         {
217             if (xxor) printf("^");
218             if (shift[i][j]==0) {printf("top");  xxor++;}
219             if (shift[i][j]>0) {printf("(top>>%d)",shift[i][j]); xxor++;}
220             if (shift[i][j]<0) {printf("(top<<%d)",-shift[i][j]); xxor++;}
221         }
222         printf(";\n");
223     }
224 
225     printf("        gx[%d]^=top;\n",k1-1);
226     printf("        x->len=%d;\n",k1);
227     printf("        if (gx[%d]==0) mr_lzero(x);\n",k1-1);
228     printf("        return;\n    }\n");
229 	return 0;
230 }
231