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