1 #include <stdio.h>
2 #include <string.h>
3 #include <math.h>
4
5 #include "sbignum.h"
6
7 static char *cset = "0123456789abcdefghijklmnopqrstuvwxyz";
8
9 static void gen_cset(int hdr);
10 static void gen_rcset(int hdr);
11 static void gen_bitstable(int hdr);
12 static void gen_basetable(int hdr);
13 static void _gen_basetable(int bytes, double base);
14 static void gen_basepowtable(int hdr);
15 static void _gen_basepowtable(int bytes, double base);
16 static unsigned long lexp(unsigned long b, int e);
17 static int nbits(unsigned char x);
18 static double logbn(double base, double n);
19
20 #define EFL 16 /* elements for line */
21
main(int argc,char ** argv)22 int main(int argc, char **argv)
23 {
24 int hdr = argc-1;
25 argv = argv;
26
27 if (hdr) {
28 printf( "#ifndef _SBN_TABLES_H\n"
29 "#define _SBN_TABLES_H\n"
30 "\n"
31 "#include <sys/types.h>\n\n");
32 } else {
33 printf( "#include \"tables.h\"\n"
34 "#include \"sbignum.h\"\n\n");
35 }
36 gen_cset(hdr);
37 gen_rcset(hdr);
38 gen_bitstable(hdr);
39 gen_basetable(hdr);
40 gen_basepowtable(hdr);
41 if (hdr) {
42 printf("\n#endif /* _SBN_TABLES_H */\n");
43 }
44 return 0;
45 }
46
gen_cset(int hdr)47 void gen_cset(int hdr)
48 {
49 if (hdr) {
50 printf("extern char *cset;\n");
51 return;
52 }
53 printf("/* maps a number to a char */\n");
54 printf("char *cset = \"%s\";\n\n", cset);
55 }
56
gen_rcset(int hdr)57 void gen_rcset(int hdr)
58 {
59 int i;
60
61 if (hdr) {
62 printf("extern int8_t r_cset[256];\n");
63 return;
64 }
65 printf("/* maps a char to a number */\n");
66 printf("int8_t r_cset[256] = {\n");
67 for (i = 0; i < 256; i++) {
68 char *p;
69 p = strchr(cset, i);
70 if (!(i%EFL))
71 printf("\t");
72 if (!p || !i) {
73 printf("-1, ");
74 } else {
75 printf("%2d, ", p-cset);
76 }
77 if (!((i+1) % EFL))
78 printf("\n");
79 }
80 printf("};\n\n");
81 }
82
nbits(unsigned char x)83 int nbits(unsigned char x)
84 {
85 int i = 8;
86 int bits = 0;
87 do {
88 bits += x & 1;
89 x >>= 1;
90 } while(--i);
91 return bits;
92 }
93
gen_bitstable(int hdr)94 void gen_bitstable(int hdr)
95 {
96 int i;
97
98 if (hdr) {
99 printf("extern int8_t bitstable[256];\n");
100 return;
101 }
102 printf("/* bitstable[n] is the number of set bits\n"
103 " * in the number 'n' */\n");
104 printf("int8_t bitstable[256] = {\n");
105 for (i = 0; i < 256; i++) {
106 if (!(i%EFL))
107 printf("\t");
108 printf("%d, ", nbits(i));
109 if (!((i+1) % EFL))
110 printf("\n");
111 }
112 printf("};\n\n");
113 }
114
logbn(double base,double n)115 double logbn(double base, double n)
116 {
117 return log(n)/log(base);
118 }
119
_gen_basetable(int bytes,double base)120 void _gen_basetable(int bytes, double base)
121 {
122 int i;
123
124 printf("#if ATOMBYTES == %d\n", bytes);
125 printf("double basetable[%d] = {\n", SBN_MAXBASE+1);
126 for (i = 0; i <= SBN_MAXBASE; i++) {
127 if (i < 2) {
128 printf("\t0, /* unused */\n");
129 continue;
130 }
131 printf("\t%f, /* (log of %d in base %.0f) */\n",
132 logbn(i, base), i, base);
133 }
134 printf("};\n#endif\n\n");
135 }
136
137 #define BT_8BITBASE 256U
138 #define BT_16BITBASE 65536U
139 #define BT_32BITBASE 4294967296U
140
gen_basetable(int hdr)141 void gen_basetable(int hdr)
142 {
143 if (hdr) {
144 printf("extern double basetable[%d];\n", SBN_MAXBASE+1);
145 return;
146 }
147 printf("/* basetable[b] = number of digits needed to convert\n"
148 " * an mpz atom in base 'b' */\n");
149 _gen_basetable(1, BT_8BITBASE);
150 _gen_basetable(2, BT_16BITBASE);
151 _gen_basetable(4, BT_32BITBASE);
152 }
153
154 /* return b^e */
lexp(unsigned long b,int e)155 unsigned long lexp(unsigned long b, int e)
156 {
157 unsigned long p = b;
158 if (!e) return 1;
159 while(--e)
160 p *= b;
161 return p;
162 }
163
_gen_basepowtable(int bytes,double base)164 void _gen_basepowtable(int bytes, double base)
165 {
166 int i;
167
168 base--;
169 printf("#if ATOMBYTES == %d\n", bytes);
170 printf("struct sbn_basepow basepowtable[%d] = {\n", SBN_MAXBASE+1);
171 for (i = 0; i <= SBN_MAXBASE; i++) {
172 unsigned long bexp;
173 unsigned long bpow;
174 if (i < 2) {
175 printf("\t{0,0}, /* unused */\n");
176 continue;
177 }
178 bexp = (unsigned long) floor(logbn(i, base));
179 bpow = lexp(i, bexp);
180 printf("\t{%luU, %luU}, /* floor(log of %d in base %.0f) */\n",
181 bpow, bexp, i, base);
182 }
183 printf("};\n#endif\n\n");
184 }
185
gen_basepowtable(int hdr)186 void gen_basepowtable(int hdr)
187 {
188 if (hdr) {
189 printf( "struct sbn_basepow {\n"
190 " unsigned long maxpow;\n"
191 " unsigned long maxexp;\n"
192 "};\n");
193 printf("extern struct sbn_basepow basepowtable[%d];\n",
194 SBN_MAXBASE+1);
195 return;
196 }
197 printf(
198 "/* basepowtable[b] = the first column is the biggest power of 'b'\n"
199 " * that fits in mpz_atom_t, the second column is the exponent\n"
200 " * 'e' so that b^e = the value of the first column */\n");
201 _gen_basepowtable(1, BT_8BITBASE);
202 _gen_basepowtable(2, BT_16BITBASE);
203 _gen_basepowtable(4, BT_32BITBASE);
204 }
205