1 #include "sbignum-tables.h" 2 #include "sbignum.h" 3 4 /* maps a number to a char */ 5 char *cset = "0123456789abcdefghijklmnopqrstuvwxyz"; 6 7 /* maps a char to a number */ 8 int8_t r_cset[256] = { 9 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 10 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 11 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 12 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1, 13 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 14 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 15 -1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 16 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, -1, -1, -1, -1, -1, 17 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 18 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 19 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 20 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 21 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 22 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 23 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 24 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 25 }; 26 27 /* bitstable[n] is the number of set bits 28 * in the number 'n' */ 29 int8_t bitstable[256] = { 30 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 31 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 32 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 33 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 34 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 35 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 36 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 37 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 38 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 39 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 40 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 41 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 42 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 43 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 44 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 45 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 46 }; 47 48 /* basetable[b] = number of digits needed to convert 49 * an mpz atom in base 'b' */ 50 #if ATOMBYTES == 1 51 double basetable[37] = { 52 0, /* unused */ 53 0, /* unused */ 54 8.000000, /* (log of 2 in base 256) */ 55 5.047438, /* (log of 3 in base 256) */ 56 4.000000, /* (log of 4 in base 256) */ 57 3.445412, /* (log of 5 in base 256) */ 58 3.094822, /* (log of 6 in base 256) */ 59 2.849657, /* (log of 7 in base 256) */ 60 2.666667, /* (log of 8 in base 256) */ 61 2.523719, /* (log of 9 in base 256) */ 62 2.408240, /* (log of 10 in base 256) */ 63 2.312519, /* (log of 11 in base 256) */ 64 2.231544, /* (log of 12 in base 256) */ 65 2.161905, /* (log of 13 in base 256) */ 66 2.101196, /* (log of 14 in base 256) */ 67 2.047664, /* (log of 15 in base 256) */ 68 2.000000, /* (log of 16 in base 256) */ 69 1.957204, /* (log of 17 in base 256) */ 70 1.918500, /* (log of 18 in base 256) */ 71 1.883271, /* (log of 19 in base 256) */ 72 1.851026, /* (log of 20 in base 256) */ 73 1.821362, /* (log of 21 in base 256) */ 74 1.793951, /* (log of 22 in base 256) */ 75 1.768518, /* (log of 23 in base 256) */ 76 1.744834, /* (log of 24 in base 256) */ 77 1.722706, /* (log of 25 in base 256) */ 78 1.701968, /* (log of 26 in base 256) */ 79 1.682479, /* (log of 27 in base 256) */ 80 1.664117, /* (log of 28 in base 256) */ 81 1.646775, /* (log of 29 in base 256) */ 82 1.630360, /* (log of 30 in base 256) */ 83 1.614793, /* (log of 31 in base 256) */ 84 1.600000, /* (log of 32 in base 256) */ 85 1.585919, /* (log of 33 in base 256) */ 86 1.572493, /* (log of 34 in base 256) */ 87 1.559672, /* (log of 35 in base 256) */ 88 1.547411, /* (log of 36 in base 256) */ 89 }; 90 #endif 91 92 #if ATOMBYTES == 2 93 double basetable[37] = { 94 0, /* unused */ 95 0, /* unused */ 96 16.000000, /* (log of 2 in base 65536) */ 97 10.094876, /* (log of 3 in base 65536) */ 98 8.000000, /* (log of 4 in base 65536) */ 99 6.890825, /* (log of 5 in base 65536) */ 100 6.189645, /* (log of 6 in base 65536) */ 101 5.699315, /* (log of 7 in base 65536) */ 102 5.333333, /* (log of 8 in base 65536) */ 103 5.047438, /* (log of 9 in base 65536) */ 104 4.816480, /* (log of 10 in base 65536) */ 105 4.625037, /* (log of 11 in base 65536) */ 106 4.463087, /* (log of 12 in base 65536) */ 107 4.323810, /* (log of 13 in base 65536) */ 108 4.202393, /* (log of 14 in base 65536) */ 109 4.095328, /* (log of 15 in base 65536) */ 110 4.000000, /* (log of 16 in base 65536) */ 111 3.914409, /* (log of 17 in base 65536) */ 112 3.836999, /* (log of 18 in base 65536) */ 113 3.766543, /* (log of 19 in base 65536) */ 114 3.702051, /* (log of 20 in base 65536) */ 115 3.642724, /* (log of 21 in base 65536) */ 116 3.587901, /* (log of 22 in base 65536) */ 117 3.537036, /* (log of 23 in base 65536) */ 118 3.489669, /* (log of 24 in base 65536) */ 119 3.445412, /* (log of 25 in base 65536) */ 120 3.403937, /* (log of 26 in base 65536) */ 121 3.364959, /* (log of 27 in base 65536) */ 122 3.328234, /* (log of 28 in base 65536) */ 123 3.293549, /* (log of 29 in base 65536) */ 124 3.260721, /* (log of 30 in base 65536) */ 125 3.229585, /* (log of 31 in base 65536) */ 126 3.200000, /* (log of 32 in base 65536) */ 127 3.171838, /* (log of 33 in base 65536) */ 128 3.144986, /* (log of 34 in base 65536) */ 129 3.119344, /* (log of 35 in base 65536) */ 130 3.094822, /* (log of 36 in base 65536) */ 131 }; 132 #endif 133 134 #if ATOMBYTES == 4 135 double basetable[37] = { 136 0, /* unused */ 137 0, /* unused */ 138 32.000000, /* (log of 2 in base 4294967296) */ 139 20.189752, /* (log of 3 in base 4294967296) */ 140 16.000000, /* (log of 4 in base 4294967296) */ 141 13.781650, /* (log of 5 in base 4294967296) */ 142 12.379290, /* (log of 6 in base 4294967296) */ 143 11.398630, /* (log of 7 in base 4294967296) */ 144 10.666667, /* (log of 8 in base 4294967296) */ 145 10.094876, /* (log of 9 in base 4294967296) */ 146 9.632960, /* (log of 10 in base 4294967296) */ 147 9.250074, /* (log of 11 in base 4294967296) */ 148 8.926174, /* (log of 12 in base 4294967296) */ 149 8.647621, /* (log of 13 in base 4294967296) */ 150 8.404785, /* (log of 14 in base 4294967296) */ 151 8.190657, /* (log of 15 in base 4294967296) */ 152 8.000000, /* (log of 16 in base 4294967296) */ 153 7.828817, /* (log of 17 in base 4294967296) */ 154 7.673999, /* (log of 18 in base 4294967296) */ 155 7.533085, /* (log of 19 in base 4294967296) */ 156 7.404103, /* (log of 20 in base 4294967296) */ 157 7.285448, /* (log of 21 in base 4294967296) */ 158 7.175802, /* (log of 22 in base 4294967296) */ 159 7.074071, /* (log of 23 in base 4294967296) */ 160 6.979337, /* (log of 24 in base 4294967296) */ 161 6.890825, /* (log of 25 in base 4294967296) */ 162 6.807874, /* (log of 26 in base 4294967296) */ 163 6.729917, /* (log of 27 in base 4294967296) */ 164 6.656467, /* (log of 28 in base 4294967296) */ 165 6.587099, /* (log of 29 in base 4294967296) */ 166 6.521442, /* (log of 30 in base 4294967296) */ 167 6.459171, /* (log of 31 in base 4294967296) */ 168 6.400000, /* (log of 32 in base 4294967296) */ 169 6.343676, /* (log of 33 in base 4294967296) */ 170 6.289972, /* (log of 34 in base 4294967296) */ 171 6.238689, /* (log of 35 in base 4294967296) */ 172 6.189645, /* (log of 36 in base 4294967296) */ 173 }; 174 #endif 175 176 /* basepowtable[b] = the first column is the biggest power of 'b' 177 * that fits in mpz_atom_t, the second column is the exponent 178 * 'e' so that b^e = the value of the first column */ 179 #if ATOMBYTES == 1 180 struct sbn_basepow basepowtable[37] = { 181 {0,0}, /* unused */ 182 {0,0}, /* unused */ 183 {128U, 7U}, /* floor(log of 2 in base 255) */ 184 {243U, 5U}, /* floor(log of 3 in base 255) */ 185 {64U, 3U}, /* floor(log of 4 in base 255) */ 186 {125U, 3U}, /* floor(log of 5 in base 255) */ 187 {216U, 3U}, /* floor(log of 6 in base 255) */ 188 {49U, 2U}, /* floor(log of 7 in base 255) */ 189 {64U, 2U}, /* floor(log of 8 in base 255) */ 190 {81U, 2U}, /* floor(log of 9 in base 255) */ 191 {100U, 2U}, /* floor(log of 10 in base 255) */ 192 {121U, 2U}, /* floor(log of 11 in base 255) */ 193 {144U, 2U}, /* floor(log of 12 in base 255) */ 194 {169U, 2U}, /* floor(log of 13 in base 255) */ 195 {196U, 2U}, /* floor(log of 14 in base 255) */ 196 {225U, 2U}, /* floor(log of 15 in base 255) */ 197 {16U, 1U}, /* floor(log of 16 in base 255) */ 198 {17U, 1U}, /* floor(log of 17 in base 255) */ 199 {18U, 1U}, /* floor(log of 18 in base 255) */ 200 {19U, 1U}, /* floor(log of 19 in base 255) */ 201 {20U, 1U}, /* floor(log of 20 in base 255) */ 202 {21U, 1U}, /* floor(log of 21 in base 255) */ 203 {22U, 1U}, /* floor(log of 22 in base 255) */ 204 {23U, 1U}, /* floor(log of 23 in base 255) */ 205 {24U, 1U}, /* floor(log of 24 in base 255) */ 206 {25U, 1U}, /* floor(log of 25 in base 255) */ 207 {26U, 1U}, /* floor(log of 26 in base 255) */ 208 {27U, 1U}, /* floor(log of 27 in base 255) */ 209 {28U, 1U}, /* floor(log of 28 in base 255) */ 210 {29U, 1U}, /* floor(log of 29 in base 255) */ 211 {30U, 1U}, /* floor(log of 30 in base 255) */ 212 {31U, 1U}, /* floor(log of 31 in base 255) */ 213 {32U, 1U}, /* floor(log of 32 in base 255) */ 214 {33U, 1U}, /* floor(log of 33 in base 255) */ 215 {34U, 1U}, /* floor(log of 34 in base 255) */ 216 {35U, 1U}, /* floor(log of 35 in base 255) */ 217 {36U, 1U}, /* floor(log of 36 in base 255) */ 218 }; 219 #endif 220 221 #if ATOMBYTES == 2 222 struct sbn_basepow basepowtable[37] = { 223 {0,0}, /* unused */ 224 {0,0}, /* unused */ 225 {32768U, 15U}, /* floor(log of 2 in base 65535) */ 226 {59049U, 10U}, /* floor(log of 3 in base 65535) */ 227 {16384U, 7U}, /* floor(log of 4 in base 65535) */ 228 {15625U, 6U}, /* floor(log of 5 in base 65535) */ 229 {46656U, 6U}, /* floor(log of 6 in base 65535) */ 230 {16807U, 5U}, /* floor(log of 7 in base 65535) */ 231 {32768U, 5U}, /* floor(log of 8 in base 65535) */ 232 {59049U, 5U}, /* floor(log of 9 in base 65535) */ 233 {10000U, 4U}, /* floor(log of 10 in base 65535) */ 234 {14641U, 4U}, /* floor(log of 11 in base 65535) */ 235 {20736U, 4U}, /* floor(log of 12 in base 65535) */ 236 {28561U, 4U}, /* floor(log of 13 in base 65535) */ 237 {38416U, 4U}, /* floor(log of 14 in base 65535) */ 238 {50625U, 4U}, /* floor(log of 15 in base 65535) */ 239 {4096U, 3U}, /* floor(log of 16 in base 65535) */ 240 {4913U, 3U}, /* floor(log of 17 in base 65535) */ 241 {5832U, 3U}, /* floor(log of 18 in base 65535) */ 242 {6859U, 3U}, /* floor(log of 19 in base 65535) */ 243 {8000U, 3U}, /* floor(log of 20 in base 65535) */ 244 {9261U, 3U}, /* floor(log of 21 in base 65535) */ 245 {10648U, 3U}, /* floor(log of 22 in base 65535) */ 246 {12167U, 3U}, /* floor(log of 23 in base 65535) */ 247 {13824U, 3U}, /* floor(log of 24 in base 65535) */ 248 {15625U, 3U}, /* floor(log of 25 in base 65535) */ 249 {17576U, 3U}, /* floor(log of 26 in base 65535) */ 250 {19683U, 3U}, /* floor(log of 27 in base 65535) */ 251 {21952U, 3U}, /* floor(log of 28 in base 65535) */ 252 {24389U, 3U}, /* floor(log of 29 in base 65535) */ 253 {27000U, 3U}, /* floor(log of 30 in base 65535) */ 254 {29791U, 3U}, /* floor(log of 31 in base 65535) */ 255 {32768U, 3U}, /* floor(log of 32 in base 65535) */ 256 {35937U, 3U}, /* floor(log of 33 in base 65535) */ 257 {39304U, 3U}, /* floor(log of 34 in base 65535) */ 258 {42875U, 3U}, /* floor(log of 35 in base 65535) */ 259 {46656U, 3U}, /* floor(log of 36 in base 65535) */ 260 }; 261 #endif 262 263 #if ATOMBYTES == 4 264 struct sbn_basepow basepowtable[37] = { 265 {0,0}, /* unused */ 266 {0,0}, /* unused */ 267 {2147483648U, 31U}, /* floor(log of 2 in base 4294967295) */ 268 {3486784401U, 20U}, /* floor(log of 3 in base 4294967295) */ 269 {1073741824U, 15U}, /* floor(log of 4 in base 4294967295) */ 270 {1220703125U, 13U}, /* floor(log of 5 in base 4294967295) */ 271 {2176782336U, 12U}, /* floor(log of 6 in base 4294967295) */ 272 {1977326743U, 11U}, /* floor(log of 7 in base 4294967295) */ 273 {1073741824U, 10U}, /* floor(log of 8 in base 4294967295) */ 274 {3486784401U, 10U}, /* floor(log of 9 in base 4294967295) */ 275 {1000000000U, 9U}, /* floor(log of 10 in base 4294967295) */ 276 {2357947691U, 9U}, /* floor(log of 11 in base 4294967295) */ 277 {429981696U, 8U}, /* floor(log of 12 in base 4294967295) */ 278 {815730721U, 8U}, /* floor(log of 13 in base 4294967295) */ 279 {1475789056U, 8U}, /* floor(log of 14 in base 4294967295) */ 280 {2562890625U, 8U}, /* floor(log of 15 in base 4294967295) */ 281 {268435456U, 7U}, /* floor(log of 16 in base 4294967295) */ 282 {410338673U, 7U}, /* floor(log of 17 in base 4294967295) */ 283 {612220032U, 7U}, /* floor(log of 18 in base 4294967295) */ 284 {893871739U, 7U}, /* floor(log of 19 in base 4294967295) */ 285 {1280000000U, 7U}, /* floor(log of 20 in base 4294967295) */ 286 {1801088541U, 7U}, /* floor(log of 21 in base 4294967295) */ 287 {2494357888U, 7U}, /* floor(log of 22 in base 4294967295) */ 288 {3404825447U, 7U}, /* floor(log of 23 in base 4294967295) */ 289 {191102976U, 6U}, /* floor(log of 24 in base 4294967295) */ 290 {244140625U, 6U}, /* floor(log of 25 in base 4294967295) */ 291 {308915776U, 6U}, /* floor(log of 26 in base 4294967295) */ 292 {387420489U, 6U}, /* floor(log of 27 in base 4294967295) */ 293 {481890304U, 6U}, /* floor(log of 28 in base 4294967295) */ 294 {594823321U, 6U}, /* floor(log of 29 in base 4294967295) */ 295 {729000000U, 6U}, /* floor(log of 30 in base 4294967295) */ 296 {887503681U, 6U}, /* floor(log of 31 in base 4294967295) */ 297 {1073741824U, 6U}, /* floor(log of 32 in base 4294967295) */ 298 {1291467969U, 6U}, /* floor(log of 33 in base 4294967295) */ 299 {1544804416U, 6U}, /* floor(log of 34 in base 4294967295) */ 300 {1838265625U, 6U}, /* floor(log of 35 in base 4294967295) */ 301 {2176782336U, 6U}, /* floor(log of 36 in base 4294967295) */ 302 }; 303 #endif 304 305