1/* Generate Fibonacci table data. 2 3Copyright 2001, 2002, 2004 Free Software Foundation, Inc. 4 5This file is part of the GNU MP Library. 6 7The GNU MP Library is free software; you can redistribute it and/or modify 8it under the terms of the GNU Lesser General Public License as published by 9the Free Software Foundation; either version 3 of the License, or (at your 10option) any later version. 11 12The GNU MP Library is distributed in the hope that it will be useful, but 13WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 14or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 15License for more details. 16 17You should have received a copy of the GNU Lesser General Public License 18along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */ 19 20#include <stdio.h> 21#include "dumbmp.c" 22 23mpz_t *f; 24int fnum, fib_limit, luc_limit; 25 26void 27generate (int numb_bits) 28{ 29 mpz_t limit, l; 30 int falloc, i; 31 32 mpz_init_set_ui (limit, 1L); 33 mpz_mul_2exp (limit, limit, numb_bits); 34 35 /* fib(2n) > 2^n, so use 2n as a limit for the table size */ 36 falloc = 2 * numb_bits; 37 f = (mpz_t *) xmalloc (falloc * sizeof (*f)); 38 39 mpz_init_set_ui (f[0], 1L); /* F[-1] */ 40 mpz_init_set_ui (f[1], 0L); /* F[0] */ 41 42 mpz_init (l); 43 44 for (i = 2; ; i++) 45 { 46 ASSERT (i < falloc); 47 48 /* F[i] = F[i-1] + F[i-2] */ 49 mpz_init (f[i]); 50 mpz_add (f[i], f[i-1], f[i-2]); 51 if (mpz_cmp (f[i], limit) >= 0) 52 break; 53 54 fnum = i+1; 55 fib_limit = i-1; 56 57 /* L[i] = F[i]+2*F[i-1] */ 58 mpz_add (l, f[i], f[i-1]); 59 mpz_add (l, l, f[i-1]); 60 61 if (mpz_cmp (l, limit) < 0) 62 luc_limit = i-1; 63 } 64 65 mpz_clear (limit); 66} 67 68 69void 70header (int numb_bits) 71{ 72 printf ("/* This file generated by gen-fib.c - DO NOT EDIT. */\n"); 73 printf ("\n"); 74 printf ("#if GMP_NUMB_BITS != %d\n", numb_bits); 75 printf ("Error, error, this data is for %d bits\n", numb_bits); 76 printf ("#endif\n"); 77 printf ("\n"); 78 printf ("#define FIB_TABLE_LIMIT %d\n", fib_limit); 79 printf ("#define FIB_TABLE_LUCNUM_LIMIT %d\n", luc_limit); 80} 81 82void 83table (int numb_bits) 84{ 85 int i; 86 87 printf ("/* This file generated by gen-fib.c - DO NOT EDIT. */\n"); 88 printf ("\n"); 89 printf ("#include \"gmp.h\"\n"); 90 printf ("#include \"gmp-impl.h\"\n"); 91 printf ("\n"); 92 printf ("#if GMP_NUMB_BITS != %d\n", numb_bits); 93 printf ("Error, error, this data is for %d bits\n", numb_bits); 94 printf ("#endif\n"); 95 printf ("\n"); 96 printf ("const mp_limb_t\n"); 97 printf ("__gmp_fib_table[FIB_TABLE_LIMIT+2] = {\n"); 98 99 for (i = 0; i < fnum; i++) 100 { 101 printf (" CNST_LIMB (0x"); 102 mpz_out_str (stdout, 16, f[i]); 103 printf ("), /* %d */\n", i-1); 104 } 105 printf ("};\n"); 106} 107 108int 109main (int argc, char *argv[]) 110{ 111 int limb_bits, nail_bits, numb_bits; 112 113 if (argc != 4) 114 { 115 fprintf (stderr, "Usage: gen-bases <header|table> <limbbits> <nailbits>\n"); 116 exit (1); 117 } 118 119 limb_bits = atoi (argv[2]); 120 nail_bits = atoi (argv[3]); 121 122 if (limb_bits <= 0 123 || nail_bits < 0 124 || nail_bits >= limb_bits) 125 { 126 fprintf (stderr, "Invalid limb/nail bits: %d %d\n", 127 limb_bits, nail_bits); 128 exit (1); 129 } 130 numb_bits = limb_bits - nail_bits; 131 132 generate (numb_bits); 133 134 if (strcmp (argv[1], "header") == 0) 135 header (numb_bits); 136 else if (strcmp (argv[1], "table") == 0) 137 table (numb_bits); 138 else 139 { 140 fprintf (stderr, "Invalid header/table choice: %s\n", argv[1]); 141 exit (1); 142 } 143 144 return 0; 145} 146