1 /* Generate mp_bases data. 2 3 Copyright 1991, 1993, 1994, 1996, 2000, 2002, 2004, 2011, 2012 Free Software 4 Foundation, Inc. 5 6 This file is part of the GNU MP Library. 7 8 The GNU MP Library is free software; you can redistribute it and/or modify 9 it under the terms of either: 10 11 * the GNU Lesser General Public License as published by the Free 12 Software Foundation; either version 3 of the License, or (at your 13 option) any later version. 14 15 or 16 17 * the GNU General Public License as published by the Free Software 18 Foundation; either version 2 of the License, or (at your option) any 19 later version. 20 21 or both in parallel, as here. 22 23 The GNU MP Library is distributed in the hope that it will be useful, but 24 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 25 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 26 for more details. 27 28 You should have received copies of the GNU General Public License and the 29 GNU Lesser General Public License along with the GNU MP Library. If not, 30 see https://www.gnu.org/licenses/. */ 31 32 #include "bootstrap.c" 33 34 35 int chars_per_limb; 36 mpz_t big_base; 37 int normalization_steps; 38 mpz_t big_base_inverted; 39 40 mpz_t t; 41 42 #define POW2_P(n) (((n) & ((n) - 1)) == 0) 43 44 unsigned int 45 ulog2 (unsigned int x) 46 { 47 unsigned int i; 48 for (i = 0; x != 0; i++) 49 x >>= 1; 50 return i; 51 } 52 53 void 54 generate (int limb_bits, int nail_bits, int base) 55 { 56 int numb_bits = limb_bits - nail_bits; 57 58 mpz_set_ui (t, 1L); 59 mpz_mul_2exp (t, t, numb_bits); 60 mpz_set_ui (big_base, 1L); 61 chars_per_limb = 0; 62 for (;;) 63 { 64 mpz_mul_ui (big_base, big_base, (long) base); 65 if (mpz_cmp (big_base, t) > 0) 66 break; 67 chars_per_limb++; 68 } 69 70 mpz_ui_pow_ui (big_base, (long) base, (long) chars_per_limb); 71 72 normalization_steps = limb_bits - mpz_sizeinbase (big_base, 2); 73 74 mpz_set_ui (t, 1L); 75 mpz_mul_2exp (t, t, 2*limb_bits - normalization_steps); 76 mpz_tdiv_q (big_base_inverted, t, big_base); 77 mpz_set_ui (t, 1L); 78 mpz_mul_2exp (t, t, limb_bits); 79 mpz_sub (big_base_inverted, big_base_inverted, t); 80 } 81 82 void 83 header (int limb_bits, int nail_bits) 84 { 85 int numb_bits = limb_bits - nail_bits; 86 87 generate (limb_bits, nail_bits, 10); 88 89 printf ("/* This file generated by gen-bases.c - DO NOT EDIT. */\n"); 90 printf ("\n"); 91 printf ("#if GMP_NUMB_BITS != %d\n", numb_bits); 92 printf ("Error, error, this data is for %d bits\n", numb_bits); 93 printf ("#endif\n"); 94 printf ("\n"); 95 printf ("/* mp_bases[10] data, as literal values */\n"); 96 printf ("#define MP_BASES_CHARS_PER_LIMB_10 %d\n", chars_per_limb); 97 printf ("#define MP_BASES_BIG_BASE_10 CNST_LIMB(0x"); 98 mpz_out_str (stdout, 16, big_base); 99 printf (")\n"); 100 printf ("#define MP_BASES_BIG_BASE_INVERTED_10 CNST_LIMB(0x"); 101 mpz_out_str (stdout, 16, big_base_inverted); 102 printf (")\n"); 103 printf ("#define MP_BASES_NORMALIZATION_STEPS_10 %d\n", normalization_steps); 104 } 105 106 107 #define EXTRA 16 108 109 /* Compute log(2)/log(b) as a fixnum. */ 110 void 111 mp_2logb (mpz_t r, int bi, int prec) 112 { 113 mpz_t t, t2, two, b; 114 int i; 115 116 mpz_init_set_ui (t, 1); 117 mpz_mul_2exp (t, t, prec+EXTRA); 118 119 mpz_init (t2); 120 121 mpz_init_set_ui (two, 2); 122 mpz_mul_2exp (two, two, prec+EXTRA); 123 124 mpz_set_ui (r, 0); 125 126 mpz_init_set_ui (b, bi); 127 mpz_mul_2exp (b, b, prec+EXTRA); 128 129 for (i = prec-1; i >= 0; i--) 130 { 131 mpz_mul_2exp (b, b, prec+EXTRA); 132 mpz_sqrt (b, b); 133 134 mpz_mul (t2, t, b); 135 mpz_tdiv_q_2exp (t2, t2, prec+EXTRA); 136 137 if (mpz_cmp (t2, two) < 0) /* not too large? */ 138 { 139 mpz_setbit (r, i); /* set next less significant bit */ 140 mpz_set (t, t2); /* new value acceptable */ 141 } 142 } 143 144 mpz_clear (t); 145 mpz_clear (t2); 146 mpz_clear (two); 147 mpz_clear (b); 148 } 149 150 void 151 table (int limb_bits, int nail_bits) 152 { 153 int numb_bits = limb_bits - nail_bits; 154 int base; 155 mpz_t r, t, logb2, log2b; 156 157 mpz_init (r); 158 mpz_init (t); 159 mpz_init (logb2); 160 mpz_init (log2b); 161 162 printf ("/* This file generated by gen-bases.c - DO NOT EDIT. */\n"); 163 printf ("\n"); 164 printf ("#include \"gmp.h\"\n"); 165 printf ("#include \"gmp-impl.h\"\n"); 166 printf ("\n"); 167 printf ("#if GMP_NUMB_BITS != %d\n", numb_bits); 168 printf ("Error, error, this data is for %d bits\n", numb_bits); 169 printf ("#endif\n"); 170 printf ("\n"); 171 puts ("const struct bases mp_bases[257] =\n{"); 172 puts (" /* 0 */ { 0, 0, 0, 0, 0 },"); 173 puts (" /* 1 */ { 0, 0, 0, 0, 0 },"); 174 for (base = 2; base <= 256; base++) 175 { 176 generate (limb_bits, nail_bits, base); 177 mp_2logb (r, base, limb_bits + 8); 178 mpz_tdiv_q_2exp (logb2, r, 8); 179 mpz_set_ui (t, 1); 180 mpz_mul_2exp (t, t, 2*limb_bits + 5); 181 mpz_sub_ui (t, t, 1); 182 mpz_add_ui (r, r, 1); 183 mpz_tdiv_q (log2b, t, r); 184 185 printf (" /* %3u */ { ", base); 186 if (POW2_P (base)) 187 { 188 mpz_set_ui (big_base, ulog2 (base) - 1); 189 mpz_set_ui (big_base_inverted, 0); 190 } 191 192 printf ("%u,", chars_per_limb); 193 printf (" CNST_LIMB(0x"); 194 mpz_out_str (stdout, 16, logb2); 195 printf ("), CNST_LIMB(0x"); 196 mpz_out_str (stdout, 16, log2b); 197 printf ("), CNST_LIMB(0x"); 198 mpz_out_str (stdout, 16, big_base); 199 printf ("), CNST_LIMB(0x"); 200 mpz_out_str (stdout, 16, big_base_inverted); 201 printf (") },\n"); 202 } 203 204 puts ("};"); 205 206 mpz_clear (r); 207 mpz_clear (t); 208 mpz_clear (logb2); 209 mpz_clear (log2b); 210 211 } 212 213 int 214 main (int argc, char **argv) 215 { 216 int limb_bits, nail_bits; 217 218 mpz_init (big_base); 219 mpz_init (big_base_inverted); 220 mpz_init (t); 221 222 if (argc != 4) 223 { 224 fprintf (stderr, "Usage: gen-bases <header|table> <limbbits> <nailbits>\n"); 225 exit (1); 226 } 227 228 limb_bits = atoi (argv[2]); 229 nail_bits = atoi (argv[3]); 230 231 if (limb_bits <= 0 232 || nail_bits < 0 233 || nail_bits >= limb_bits) 234 { 235 fprintf (stderr, "Invalid limb/nail bits: %d %d\n", 236 limb_bits, nail_bits); 237 exit (1); 238 } 239 240 if (strcmp (argv[1], "header") == 0) 241 header (limb_bits, nail_bits); 242 else if (strcmp (argv[1], "table") == 0) 243 table (limb_bits, nail_bits); 244 else 245 { 246 fprintf (stderr, "Invalid header/table choice: %s\n", argv[1]); 247 exit (1); 248 } 249 250 return 0; 251 } 252