Parent Directory | Revision Log

Revision **56** -
(**show annotations**)
(**download**)

*Sat Oct 29 01:53:01 2016 UTC*
(7 years, 9 months ago)
by *dashley*

File MIME type: text/plain

File size: 36585 byte(s)

File MIME type: text/plain

File size: 36585 byte(s)

License and property (keyword) changes.

1 | //$Header$ |

2 | //------------------------------------------------------------------------------------------------- |

3 | //This file is part of "David T. Ashley's Shared Source Code", a set of shared components |

4 | //integrated into many of David T. Ashley's projects. |

5 | //------------------------------------------------------------------------------------------------- |

6 | //This source code and any program in which it is compiled/used is provided under the MIT License, |

7 | //reproduced below. |

8 | //------------------------------------------------------------------------------------------------- |

9 | //Permission is hereby granted, free of charge, to any person obtaining a copy of |

10 | //this software and associated documentation files(the "Software"), to deal in the |

11 | //Software without restriction, including without limitation the rights to use, |

12 | //copy, modify, merge, publish, distribute, sublicense, and / or sell copies of the |

13 | //Software, and to permit persons to whom the Software is furnished to do so, |

14 | //subject to the following conditions : |

15 | // |

16 | //The above copyright notice and this permission notice shall be included in all |

17 | //copies or substantial portions of the Software. |

18 | // |

19 | //THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |

20 | //IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |

21 | //FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE |

22 | //AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |

23 | //LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, |

24 | //OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE |

25 | //SOFTWARE. |

26 | //------------------------------------------------------------------------------------------------- |

27 | /* |

28 | This software module is a careful adaptation of the integer functions |

29 | in the GNU MP library. |

30 | |

31 | By "adaptation" I mean the following: |

32 | |

33 | o Many of the macros and other constructs that affect readability |

34 | have been removed. This has been done for simplicity. |

35 | |

36 | o Only the needed functions (large integer and rational number |

37 | functions) have been included. This is for use in Dave Ashley's |

38 | set of tools. |

39 | |

40 | o The number of source modules has been dramatically reduced. |

41 | |

42 | o Assembly-language has been removed. Instead, at the lowest |

43 | level, the core is generic 'C' provided by GNU (this is |

44 | selected if processor=none is the processor chosen). This |

45 | certainly has an effect on speed, but I would rather sacrifice |

46 | quite a bit of speed and keep it simple (in one module). |

47 | |

48 | o The GNU MP library has been specifically ported for Microsoft |

49 | Visual C++ 6.0. In other words, its portability has been |

50 | deliberately destroyed. Do NOT try to use this on another |

51 | platform (or at least certainly do NOT contact me if you have |

52 | problems with this). |

53 | |

54 | o Certain other stylistic changes have been made. |

55 | */ |

56 | #ifndef GMP_INTS_H_INCLUDED |

57 | #define GMP_INTS_H_INCLUDED |

58 | |

59 | #ifdef MODULE_GMP_INTS |

60 | #define DECMOD_GMP_INTS |

61 | #else |

62 | #define DECMOD_GMP_INTS extern |

63 | #endif |

64 | |

65 | typedef unsigned long int GMP_INTS_limb_t; |

66 | //The fundamental data type for representing integers in binary |

67 | //form. For MSVC++, this is a 32-bit type. This data type |

68 | //is not normally needed publicly. |

69 | #define GMP_INTS_BITS_PER_LIMB (32) |

70 | //This is the number of bits that each limb is assumed to hold. |

71 | //There is an explicit function in the interface to check this, |

72 | //in case anything changes with future versions of MSVC++. |

73 | //This software module is NOT meant to be portable, or even |

74 | //particularly quick. It is meant to be verifiable and |

75 | //testable instead. |

76 | typedef long int GMP_INTS_limb_signed_t; |

77 | //Signed version of above. |

78 | typedef GMP_INTS_limb_t * GMP_INTS_limb_ptr; |

79 | //Pointer to a limb (or, more characteristically, to an array |

80 | //of limbs). |

81 | typedef const GMP_INTS_limb_t * GMP_INTS_limb_srcptr; |

82 | //Constant pointer used as the source pointer for copies |

83 | //and other operations. |

84 | typedef long int GMP_INTS_size_t; |

85 | //Used for representing the size of things to this module |

86 | typedef long int GMP_INTS_exp_t; |

87 | //Used for representing exponent. Assumed to be large enough |

88 | //for this. |

89 | |

90 | //Below is fundamental structure which holds an arbitrary-size |

91 | //integer. |

92 | typedef struct |

93 | { |

94 | int flags; |

95 | //Bit-flags as to the condition of the |

96 | //integer. The bitflags defined so far |

97 | //are designed to be mutually exclusive, |

98 | //and are listed below. At the same time, |

99 | //we need to define the "official" strings |

100 | //for these bit flags. |

101 | #define GMP_INTS_EF_INTOVF_POS (1) |

102 | #define GMP_INTS_EF_INTOVF_POS_STRING \ |

103 | "GMP_INTS_EF_INTOVF_POS" |

104 | //The integer has become too large |

105 | //growing in a positive direction. |

106 | //No further arithmetic will be |

107 | //performed on it. |

108 | #define GMP_INTS_EF_INTOVF_NEG (2) |

109 | #define GMP_INTS_EF_INTOVF_NEG_STRING \ |

110 | "GMP_INTS_EF_INTOVF_NEG" |

111 | //The integer has become too large |

112 | //growing in a negative direction. |

113 | //No further arithmetic will be |

114 | //performed on it. |

115 | #define GMP_INTS_EF_INTOVF_TAINT_POS (4) |

116 | #define GMP_INTS_EF_INTOVF_TAINT_POS_STRING \ |

117 | "GMP_INTS_EF_INTOVF_TAINT_POS" |

118 | //The integer has been arithmetically |

119 | //combined with an integer that has |

120 | //overflowed in the positive direction. |

121 | //This integer is thus considered tainted |

122 | //and no further arithmetic will be |

123 | //performed on it. |

124 | #define GMP_INTS_EF_INTOVF_TAINT_NEG (8) |

125 | #define GMP_INTS_EF_INTOVF_TAINT_NEG_STRING \ |

126 | "GMP_INTS_EF_INTOVF_TAINT_NEG" |

127 | //The integer has been arithmetically |

128 | //combined with an integer that has |

129 | //overflowed in the negative direction. |

130 | //This integer is thus considered tainted |

131 | //and no further arithmetic will be |

132 | //performed on it. |

133 | //The flags above will prevent arithmetic |

134 | //on an integer and will taint any integer |

135 | //that comes into contact with it as the |

136 | //result of an operation. These flags are |

137 | //cleared only by an assignment operation |

138 | //of any kind. |

139 | // |

140 | //The next logical questions are: |

141 | // o Why do we want to make a size |

142 | // limit on integers, anyway? |

143 | // o How big is too big? |

144 | // |

145 | //We want a limit because this software module |

146 | //will be used in programs that should be |

147 | //reliable. Allowing arbitrarily large results |

148 | //would invite users to break the software. |

149 | //It would also make testing impossible, because |

150 | //the module could not be tested out to its |

151 | //limits. Assigning limits means that testing |

152 | //can be performed to the limits. Also, there |

153 | //are certain constructs in the software that |

154 | //may break at high limits, such as _alloca(). |

155 | // |

156 | //The question of how large is too large is a |

157 | //harder question. Arbitrarily, let's decide |

158 | //that we want the equivalent of integers with |

159 | //100,000 decimal digits, which is about |

160 | //332,224 bits, or 10,382 limbs. (By the way |

161 | //this limit can always be raised later, but |

162 | //the important point is that it exists and |

163 | //is tested to). Any integer with more limbs |

164 | //than this is considered illegal. |

165 | #define GMP_INTS_MAXIMUM_LIMBS_PER_INT (10382) |

166 | int n_allocd; /* Number of limbs allocated and pointed |

167 | to by the limbs field. This gives the |

168 | number allocated (i.e. physically |

169 | allocated), but the next field tells how |

170 | many are used. Memory is never shrunk |

171 | automatically by this software module |

172 | (per the wise GNU MP design), so this |

173 | number does not ever automatically |

174 | decrease. */ |

175 | int size; /* abs(size) is the number of limbs the |

176 | last field points to. If _mp_size is |

177 | negative this is a negative number. This |

178 | will be zero if the integer is zero. */ |

179 | GMP_INTS_limb_t *limbs; |

180 | /* Pointer to the limbs. The first field |

181 | of the structure (above) tells how many |

182 | spots are allocated, and the second |

183 | field (above) tells how many are used. |

184 | Numbers are stored least-significant |

185 | limbs first. */ |

186 | } GMP_INTS_mpz_struct; |

187 | |

188 | |

189 | /* Wrappers for non-stack memory allocation function to be used |

190 | ** by integer, rational number, and integer and rational number |

191 | ** algorithm functions. These must be public because they are |

192 | ** used by the other modules that deal with integers and rational |

193 | ** numbers. |

194 | */ |

195 | DECMOD_GMP_INTS void *GMP_INTS_malloc( size_t size ); |

196 | DECMOD_GMP_INTS void *GMP_INTS_calloc( size_t num, size_t size ); |

197 | DECMOD_GMP_INTS void *GMP_INTS_realloc( void *memblock, size_t size ); |

198 | DECMOD_GMP_INTS void *GMP_INTS_realloc_w_size( void *memblock, |

199 | size_t old_size, |

200 | size_t size ); |

201 | DECMOD_GMP_INTS void GMP_INTS_free( void *memblock ); |

202 | DECMOD_GMP_INTS void GMP_INTS_free_w_size( void *memblock, size_t size ); |

203 | |

204 | /******************************************************************/ |

205 | /*** PORTABILITY CHECK FUNCTIONS *******************************/ |

206 | /******************************************************************/ |

207 | //Because there is the risk that Microsoft Visual C++ might |

208 | //change in the future, the following function can be called |

209 | //to see if the assumptions about data sizes are valid. This |

210 | //function returns TRUE if there is a problem, or FALSE |

211 | //otherwise. |

212 | DECMOD_GMP_INTS int GMP_INTS_data_sizes_are_wrong(void); |

213 | |

214 | |

215 | /******************************************************************/ |

216 | /*** ERROR STRING IDENTIFICATION AND PROCESSING FUNCTIONS *******/ |

217 | /******************************************************************/ |

218 | //These functions are provided because some clients may deal |

219 | //only with symbolic representations (Tcl/Tk, for example). |

220 | // |

221 | //Attempts to identify the passed string as one of the error |

222 | //strings sanctioned by this module. Returns -1 if not a match |

223 | //or else the following values. |

224 | // 0: GMP_INTS_EF_INTOVF_POS |

225 | // 1: GMP_INTS_EF_INTOVF_NEG |

226 | // 2: GMP_INTS_EF_INTOVF_TAINT_POS |

227 | // 3: GMP_INTS_EF_INTOVF_TAINT_NEG |

228 | DECMOD_GMP_INTS |

229 | int GMP_INTS_identify_nan_string(const char *s); |

230 | |

231 | //Returns the sanctioned string for the nan value indicated. |

232 | //Integers that may be passed are the same as the |

233 | //indices above. No parameter except 0-3 is allowed. |

234 | DECMOD_GMP_INTS |

235 | const char *GMP_INTS_supply_nan_string(int idx); |

236 | |

237 | /******************************************************************/ |

238 | /*** DEBUG PRINTING FUNCTIONS **********************************/ |

239 | /******************************************************************/ |

240 | //These functions are for printing out integers and limbs |

241 | //and groups of limbs for unit testing and debugging. |

242 | // |

243 | //Prints out a group of limbs, preceded by a description. |

244 | //n may be 0 and/or the lg pointer supplied may be NULL. |

245 | DECMOD_GMP_INTS |

246 | void GMP_INTS_print_limb_group(FILE *stream, |

247 | GMP_INTS_limb_srcptr lg, |

248 | GMP_INTS_size_t n, |

249 | char *desc); |

250 | //Prints an entire integer for diagnosis. |

251 | DECMOD_GMP_INTS |

252 | void GMP_INTS_mpz_print_int(FILE *stream, |

253 | const GMP_INTS_mpz_struct *arg, |

254 | char *desc); |

255 | |

256 | /****************************************************************/ |

257 | /*** MACRO REPLACEMENTS *************************************/ |

258 | /****************************************************************/ |

259 | //The functions here are macros that have been replaced and |

260 | //made functions for clarity. Speed was sacrificed for clarity. |

261 | DECMOD_GMP_INTS |

262 | int GMP_INTS_mpz_get_flags(const GMP_INTS_mpz_struct *arg); |

263 | //Allows a caller to obtain the flags of an integer. |

264 | //A non-zero value indicates trouble. To figure out which |

265 | //trouble, compare against the bit constants defined |

266 | //with the "flags" field of the structure type, above. |

267 | DECMOD_GMP_INTS GMP_INTS_size_t GMP_INTS_abs_of_size_t(GMP_INTS_size_t arg); |

268 | //Returns the absolute value of one of the size arguments used |

269 | //to indicate number of limbs. This function is useful |

270 | //because integers natively stored with a negative size |

271 | //for negative arguments, so the absolute value gives the |

272 | //number of limbs consumed. |

273 | DECMOD_GMP_INTS int GMP_INTS_mpz_sgn(const GMP_INTS_mpz_struct *arg); |

274 | //Returns -1 if integer is negative, 0 if it is zero, |

275 | //or 1 if it is positive. |

276 | DECMOD_GMP_INTS int GMP_INTS_mpz_is_neg(const GMP_INTS_mpz_struct *arg); |

277 | DECMOD_GMP_INTS int GMP_INTS_mpz_is_zero(const GMP_INTS_mpz_struct *arg); |

278 | DECMOD_GMP_INTS int GMP_INTS_mpz_is_pos(const GMP_INTS_mpz_struct *arg); |

279 | //These functions return 1 if the condition is met, or 0 |

280 | //otherwise. |

281 | DECMOD_GMP_INTS int GMP_INTS_mpz_is_odd(const GMP_INTS_mpz_struct *arg); |

282 | //Returns 1 if the integer is odd, or 0 if it is even. |

283 | DECMOD_GMP_INTS int GMP_INTS_mpz_is_even(const GMP_INTS_mpz_struct *arg); |

284 | //Returns 1 if the integer is even, or 0 if it is odd. |

285 | DECMOD_GMP_INTS void GMP_INTS_mpz_negate(GMP_INTS_mpz_struct *arg); |

286 | //Negates the number (changes the sign). |

287 | DECMOD_GMP_INTS |

288 | void GMP_INTS_mpn_normalize(GMP_INTS_limb_ptr limb_array, |

289 | GMP_INTS_size_t *idx); |

290 | //Adjusts an index downward to bypass any most significant |

291 | //zero limbs. This was a macro in the GNU implementation. |

292 | //This is for when the size of a result is overestimated |

293 | //(the most pessimistic estimates must be made when |

294 | //allocating memory before an operation). |

295 | DECMOD_GMP_INTS |

296 | void GMP_INTS_mpn_copy_limbs(GMP_INTS_limb_ptr dest, |

297 | GMP_INTS_limb_srcptr src, |

298 | GMP_INTS_size_t n); |

299 | //Copies limbs from source to destination. This |

300 | //function replaces a macro that was present in the |

301 | //GNU code. Again, clarity over speed. |

302 | /****************************************************************/ |

303 | /*** LOW-LEVEL ARITHMETIC FUNCTIONS *************************/ |

304 | /****************************************************************/ |

305 | //Gives the flags of a result integer as a function of the |

306 | //flags of its two operands. If the function requires only |

307 | //one operand, just use zero as the second parameter and the |

308 | //result will be correct. Handles tainting. |

309 | DECMOD_GMP_INTS |

310 | int GMP_INTS_two_op_flags_map(int flags1, int flags2); |

311 | |

312 | //Adds the single limb s2_limb to the array of limbs s1, |

313 | //processing carries, and copies the result to the location |

314 | //res_ptr. res_ptr is assumed to be [at least] the same size |

315 | //as s1. From the design, s1 and res_ptr may be the |

316 | //same set of locations. The |

317 | //result is 1 if there was a carry out of the final limb or |

318 | //0 otherwise. |

319 | DECMOD_GMP_INTS |

320 | GMP_INTS_limb_t GMP_INTS_mpn_add_1 (GMP_INTS_limb_ptr res_ptr, |

321 | GMP_INTS_limb_srcptr s1_ptr, |

322 | GMP_INTS_size_t s1_size, |

323 | GMP_INTS_limb_t s2_limb); |

324 | |

325 | //Very similar to the addition function. Counts on the single |

326 | //limb that is being subtracted being not enough to roll over the |

327 | //integer that is being subtracted from. No harm if this is done |

328 | //(it just obeys 2-s complement rules) but this was probably not |

329 | //the intent. From the design, s1 and res_ptr may |

330 | //be the same set of locations. The |

331 | //result is 1 if there was a borrow out of the final limb or |

332 | //0 otherwise. |

333 | DECMOD_GMP_INTS |

334 | GMP_INTS_limb_t GMP_INTS_mpn_sub_1(GMP_INTS_limb_ptr res_ptr, |

335 | GMP_INTS_limb_srcptr s1_ptr, |

336 | GMP_INTS_size_t s1_size, |

337 | GMP_INTS_limb_t s2_limb); |

338 | |

339 | //Multiplies a limb by a group of limbs. The return value is |

340 | //the unsigned overflow out of the "top", which may be up to |

341 | //one limb large (i.e. it is more than just a carry, it has |

342 | //a value besides 0 and 1). |

343 | DECMOD_GMP_INTS |

344 | GMP_INTS_limb_t GMP_INTS_mpn_mul_1(GMP_INTS_limb_ptr res_ptr, |

345 | GMP_INTS_limb_srcptr s1_ptr, |

346 | GMP_INTS_size_t s1_size, |

347 | GMP_INTS_limb_t s2_limb); |

348 | |

349 | //Adds together two groups of limbs of same size. The result |

350 | //may be the same location as one or both of the two |

351 | //operands. |

352 | DECMOD_GMP_INTS |

353 | GMP_INTS_limb_t GMP_INTS_mpn_add_n(GMP_INTS_limb_ptr res_ptr, |

354 | GMP_INTS_limb_srcptr s1_ptr, |

355 | GMP_INTS_limb_srcptr s2_ptr, |

356 | GMP_INTS_size_t size); |

357 | |

358 | //This function makes the mapping: |

359 | // res_ptr = res_ptr + s2_limb * s1_ptr |

360 | //From the design, it appears that it is alright if |

361 | //res_ptr and s1_ptr are the same area. The return |

362 | //value is the excess that that should exist one limb |

363 | //above the MSL of res_ptr (i.e. it is more than a carry, it |

364 | //may be larger than one). |

365 | DECMOD_GMP_INTS |

366 | GMP_INTS_limb_t GMP_INTS_mpn_addmul_1(GMP_INTS_limb_ptr res_ptr, |

367 | GMP_INTS_limb_srcptr s1_ptr, |

368 | GMP_INTS_size_t s1_size, |

369 | GMP_INTS_limb_t s2_limb); |

370 | |

371 | //This function adds in general two natural numbers. Numbers must |

372 | //be arranged so that S2 takes no more limbs than S1, i.e. |

373 | //LIMBS(s1) >= LIMBS(s2). Memory must be allocated, and there must |

374 | //be space for the result. Not clear from the design if memory |

375 | //areas can be coincident, but suspect can. |

376 | DECMOD_GMP_INTS |

377 | GMP_INTS_limb_t GMP_INTS_mpn_add(GMP_INTS_limb_ptr res_ptr, |

378 | GMP_INTS_limb_srcptr s1_ptr, |

379 | GMP_INTS_size_t s1_size, |

380 | GMP_INTS_limb_srcptr s2_ptr, |

381 | GMP_INTS_size_t s2_size); |

382 | |

383 | //Subtracts two same-size operands. They may be coincident in |

384 | //memory. |

385 | DECMOD_GMP_INTS |

386 | GMP_INTS_limb_t GMP_INTS_mpn_sub_n(GMP_INTS_limb_ptr res_ptr, |

387 | GMP_INTS_limb_srcptr s1_ptr, |

388 | GMP_INTS_limb_srcptr s2_ptr, |

389 | GMP_INTS_size_t size); |

390 | |

391 | //This function subtracts in general two natural numbers. Numbers must |

392 | //be arranged so that S2 takes no more limbs than S1, i.e. |

393 | //LIMBS(s1) >= LIMBS(s2). Memory must be allocated, and there must |

394 | //be space for the result. Not clear from the design if memory |

395 | //areas can be coincident. Result is S1-S2. |

396 | DECMOD_GMP_INTS |

397 | GMP_INTS_limb_t GMP_INTS_mpn_sub (GMP_INTS_limb_ptr res_ptr, |

398 | GMP_INTS_limb_srcptr s1_ptr, |

399 | GMP_INTS_size_t s1_size, |

400 | GMP_INTS_limb_srcptr s2_ptr, |

401 | GMP_INTS_size_t s2_size); |

402 | |

403 | //Shifts UP of size USIZE left by CNT. CNT must be less than the number |

404 | //of bits per limb, which is at this time 32. "wp" and "up" may be |

405 | //coincident. Zero count is not allowed. Value returned is the bits shifted |

406 | //out the left. |

407 | DECMOD_GMP_INTS |

408 | GMP_INTS_limb_t GMP_INTS_mpn_lshift(GMP_INTS_limb_ptr wp, |

409 | GMP_INTS_limb_srcptr up, |

410 | GMP_INTS_size_t usize, |

411 | unsigned int cnt); |

412 | |

413 | //Shifts UP of size USIZE right by CNT. CNT must be less than the number |

414 | //of bits per limb, which is at this time 32. "wp" and "up" may be |

415 | //coincident. Zero count is not allowed. Value returned is the bits shifted |

416 | //out the right. |

417 | DECMOD_GMP_INTS |

418 | GMP_INTS_limb_t GMP_INTS_mpn_rshift (GMP_INTS_limb_ptr wp, |

419 | GMP_INTS_limb_srcptr up, |

420 | GMP_INTS_size_t usize, |

421 | unsigned int cnt); |

422 | |

423 | //Compares two natural numbers of same size and returns the expected |

424 | //1 iff op1 > op2, -1 if op1 < op2, or 0 if they are equal. Leading |

425 | //zero limbs are alright and do not affect the result. |

426 | DECMOD_GMP_INTS |

427 | int GMP_INTS_mpn_cmp (GMP_INTS_limb_srcptr op1_ptr, |

428 | GMP_INTS_limb_srcptr op2_ptr, |

429 | GMP_INTS_size_t size); |

430 | |

431 | //This is the basic multiplication of two natural numbers, each of |

432 | //which may occuply many limbs. In the |

433 | //original GNU MP code, there were several algorithms which could |

434 | //be selected, depending on the size of the operands and other |

435 | //factors. This was the most basic case--the basic longhand |

436 | //multiplication. The code has been pared so that this is the |

437 | //only case. |

438 | DECMOD_GMP_INTS |

439 | void GMP_INTS_mpn_mul_basecase (GMP_INTS_limb_ptr prodp, |

440 | GMP_INTS_limb_srcptr up, |

441 | GMP_INTS_size_t usize, |

442 | GMP_INTS_limb_srcptr vp, |

443 | GMP_INTS_size_t vsize); |

444 | |

445 | //This is the basic multiplication of two natural numbers. In the old |

446 | //GNU MP code, one of several algorithms would be selected. The code |

447 | //has been pared down so that this is just a passthrough to |

448 | //GMP_INTS_mpn_mul_basecase(). Only the simplest multiplication |

449 | //algorithm is used at this point. |

450 | DECMOD_GMP_INTS |

451 | void GMP_INTS_mpn_mul_n (GMP_INTS_limb_ptr p, |

452 | GMP_INTS_limb_srcptr a, |

453 | GMP_INTS_limb_srcptr b, |

454 | GMP_INTS_size_t n); |

455 | //Multiplication of two natural numbers. Value returned is the most |

456 | //significant limb of the array of predicted size un+vn, rather than |

457 | //the spillover (this is unlike most functions). |

458 | DECMOD_GMP_INTS |

459 | GMP_INTS_limb_t GMP_INTS_mpn_mul(GMP_INTS_limb_ptr prodp, |

460 | GMP_INTS_limb_srcptr up, |

461 | GMP_INTS_size_t un, |

462 | GMP_INTS_limb_srcptr vp, |

463 | GMP_INTS_size_t vn); |

464 | |

465 | /******************************************************************/ |

466 | /*** LIMB SPACE REALLOCATION FUNCTIONS *************************/ |

467 | /******************************************************************/ |

468 | DECMOD_GMP_INTS |

469 | void *GMP_INTS_mpz_realloc (GMP_INTS_mpz_struct *m, |

470 | GMP_INTS_size_t new_size); |

471 | //Changes the number of limbs allocated. |

472 | |

473 | /******************************************************************/ |

474 | /*** PUBLIC INITIALIZATION AND MEMORY MANAGEMENT FUNCTIONS *****/ |

475 | /******************************************************************/ |

476 | //Allocate space for an integer and sets it to zero. |

477 | //This must be the first call made. |

478 | DECMOD_GMP_INTS |

479 | void GMP_INTS_mpz_init (GMP_INTS_mpz_struct *x); |

480 | |

481 | //Deallocates space for an integer. This must be the |

482 | //final call made. |

483 | DECMOD_GMP_INTS |

484 | void GMP_INTS_mpz_clear (GMP_INTS_mpz_struct *x); |

485 | |

486 | |

487 | /******************************************************************/ |

488 | /*** PUBLIC ASSIGNMENT FUNCTIONS *******************************/ |

489 | /******************************************************************/ |

490 | //Copies from one integer to another. Must both be allocated and \ |

491 | //not be the same variable. |

492 | DECMOD_GMP_INTS |

493 | void GMP_INTS_mpz_copy( GMP_INTS_mpz_struct *dst, |

494 | const GMP_INTS_mpz_struct *src); |

495 | |

496 | //Assigns the integer to be the value of an unsigned long. |

497 | DECMOD_GMP_INTS |

498 | void GMP_INTS_mpz_set_ui (GMP_INTS_mpz_struct *dest, |

499 | unsigned long int val); |

500 | |

501 | //Assigns the integer to be the value of a signed long. |

502 | DECMOD_GMP_INTS |

503 | void GMP_INTS_mpz_set_si (GMP_INTS_mpz_struct *dest, |

504 | signed long int val); |

505 | //Assigns the integer to be the value of a simple string |

506 | //(simple = no E notation). Only form handled is |

507 | // [-]digits. |

508 | //Other forms will not cause catastrophic failure but might |

509 | //not behave as expected. |

510 | DECMOD_GMP_INTS |

511 | void GMP_INTS_mpz_set_simple_char_str(GMP_INTS_mpz_struct *z, |

512 | const char *s); |

513 | //Assigns an arbitary integer to be a number with E notation. |

514 | //*failure set non-zero if can't parse or set. Number must |

515 | //be pure integer--no lost precison when scientific notation |

516 | //is processed. |

517 | void GMP_INTS_mpz_set_sci_not_num(GMP_INTS_mpz_struct *z, |

518 | int *failure, |

519 | const char *s); |

520 | |

521 | //Attempts to parse an integer using the following three |

522 | //formats: a)simple integer, b)simple integer with commas, |

523 | //c)integer in scientific notation. Returns the value of |

524 | //the integer if parse successful, or 0 and a failure flag |

525 | //otherwise. |

526 | void GMP_INTS_mpz_set_general_int(GMP_INTS_mpz_struct *z, |

527 | int *failure, |

528 | const char *s); |

529 | |

530 | //Attempts to parse an integer as either a simple integer, |

531 | //an integer with commas, or a number in scientific notation |

532 | //into a UINT32. If the number cannot be parsed into that, |

533 | //the result is zero and failure is true. |

534 | void GMP_INTS_mpz_parse_into_uint32(unsigned *result, |

535 | int *failure, |

536 | char *s); |

537 | |

538 | //Swaps a and b. What this does is a swap of the area |

539 | //pointed to (i.e. the control block). Pointers held in |

540 | //these blocks are therefore automatically swapped. |

541 | DECMOD_GMP_INTS |

542 | void GMP_INTS_mpz_swap(GMP_INTS_mpz_struct *a, |

543 | GMP_INTS_mpz_struct *b); |

544 | |

545 | /****************************************************************/ |

546 | /*** PUBLIC INTEGER ARITHMETIC FUNCTIONS ********************/ |

547 | /****************************************************************/ |

548 | //Adds two arbitrary integers to produce an arbitrary result. |

549 | //The result space must be initialized already. |

550 | DECMOD_GMP_INTS |

551 | void GMP_INTS_mpz_add ( GMP_INTS_mpz_struct *w, |

552 | const GMP_INTS_mpz_struct *u, |

553 | const GMP_INTS_mpz_struct *v); |

554 | |

555 | //Adds the integer v to u and produces w. u and w must be |

556 | //be created already. |

557 | void GMP_INTS_mpz_add_ui ( GMP_INTS_mpz_struct *w, |

558 | const GMP_INTS_mpz_struct *u, |

559 | unsigned long int v); |

560 | |

561 | //Subtracts two aribtrary integers to produce an arbitrary |

562 | //result. The result space must be initialized already. |

563 | DECMOD_GMP_INTS |

564 | void GMP_INTS_mpz_sub ( GMP_INTS_mpz_struct *w, |

565 | const GMP_INTS_mpz_struct *u, |

566 | const GMP_INTS_mpz_struct *v); |

567 | |

568 | //Subtracts the integer v from u to produce w. u and w must |

569 | //be created already. |

570 | void GMP_INTS_mpz_sub_ui ( GMP_INTS_mpz_struct *w, |

571 | const GMP_INTS_mpz_struct *u, |

572 | unsigned long int v); |

573 | |

574 | //Multiplies two arbitrary integers to produce an arbitrary |

575 | //result. The result space must be initialized already. |

576 | DECMOD_GMP_INTS |

577 | void GMP_INTS_mpz_mul ( GMP_INTS_mpz_struct *w, |

578 | const GMP_INTS_mpz_struct *u, |

579 | const GMP_INTS_mpz_struct *v); |

580 | |

581 | //Multiplies the arbitrary integer by a C-native signed |

582 | //long. |

583 | DECMOD_GMP_INTS |

584 | void GMP_INTS_mpz_mul_si ( GMP_INTS_mpz_struct *w, |

585 | const GMP_INTS_mpz_struct *u, |

586 | long int v); |

587 | //Multiplies the arbitrary integer by a C-native unsigned |

588 | //long. |

589 | DECMOD_GMP_INTS |

590 | void GMP_INTS_mpz_mul_ui ( GMP_INTS_mpz_struct *w, |

591 | const GMP_INTS_mpz_struct *u, |

592 | unsigned long int v); |

593 | |

594 | //Divides integers. |

595 | DECMOD_GMP_INTS |

596 | void GMP_INTS_mpz_tdiv_qr ( GMP_INTS_mpz_struct *quot, |

597 | GMP_INTS_mpz_struct *rem, |

598 | const GMP_INTS_mpz_struct *num, |

599 | const GMP_INTS_mpz_struct *den); |

600 | |

601 | //Calculates the factorial. All values <=1 result in a |

602 | //value of 1. |

603 | DECMOD_GMP_INTS |

604 | void GMP_INTS_mpz_fac_ui(GMP_INTS_mpz_struct *result, |

605 | unsigned long int n); |

606 | |

607 | //Exponentiates a base to an exponent. 0^0=1, N^0=1. The algorithm |

608 | //used is successive squaring and multiplying. Not the MOST efficient, |

609 | //but OK. The result and the base must be different variables. |

610 | DECMOD_GMP_INTS |

611 | void GMP_INTS_mpz_pow_ui( GMP_INTS_mpz_struct *result, |

612 | const GMP_INTS_mpz_struct *base, |

613 | unsigned exponent); |

614 | |

615 | //Takes the absolute value of the arbitrary integer passed. |

616 | DECMOD_GMP_INTS |

617 | void GMP_INTS_mpz_abs(GMP_INTS_mpz_struct *arg); |

618 | |

619 | //Calculates the gcd() of the two arguments. If either argument is zero, the |

620 | //result is automatically 1. If either argument is negative, its absolute |

621 | //value is used. The two input pointers may not be the same, because doing |

622 | //that is senseless--it would become a copy operation, because gcd(x,x) = x. |

623 | //However, the result may be the same as either of the two inputs. |

624 | DECMOD_GMP_INTS |

625 | void GMP_INTS_mpz_gcd(GMP_INTS_mpz_struct *result, |

626 | const GMP_INTS_mpz_struct *arg1, |

627 | const GMP_INTS_mpz_struct *arg2); |

628 | |

629 | |

630 | /******************************************************************/ |

631 | /*** PUBLIC CONVERSION AND OUTPUT FUNCTIONS ********************/ |

632 | /******************************************************************/ |

633 | |

634 | //Get an upper bound on the number of characters required for |

635 | //representing an integer, including minus sign and commas, |

636 | //Terminating zero, etc. This is just a little wasteful, but |

637 | //will always reserve enough memory. |

638 | DECMOD_GMP_INTS |

639 | int GMP_INTS_mpz_size_in_base_10(const GMP_INTS_mpz_struct *arg); |

640 | |

641 | //Convert from integer to string. Commas must be |

642 | //added separately, and there is enough space reserved for |

643 | //them. This function is only warrantied not to overflow |

644 | //a buffer allocated using the function above as a sizing |

645 | //guide. |

646 | DECMOD_GMP_INTS |

647 | void GMP_INTS_mpz_to_string(char *out, |

648 | const GMP_INTS_mpz_struct *in); |

649 | |

650 | //Prints the integer passed to the stream in a long-hand |

651 | //format. |

652 | DECMOD_GMP_INTS |

653 | void GMP_INTS_mpz_long_int_format_to_stream(FILE *s, |

654 | const GMP_INTS_mpz_struct *i, |

655 | const char *desc); |

656 | |

657 | //Prints the integer raw to a stream--just digits, no extra chars. |

658 | DECMOD_GMP_INTS |

659 | void GMP_INTS_mpz_arb_int_raw_to_stream(FILE *s, |

660 | const GMP_INTS_mpz_struct *i); |

661 | |

662 | /******************************************************************/ |

663 | /*** COMPARISON AND SIZING FUNCTIONS ***************************/ |

664 | /******************************************************************/ |

665 | //Returns 1 if arbitrary integer will fit in an unsigned integer, |

666 | //or 0 otherwise. |

667 | DECMOD_GMP_INTS |

668 | int GMP_INTS_mpz_fits_uint_p (const GMP_INTS_mpz_struct *src); |

669 | |

670 | //Returns 1 if arbitrary integer will fit in a signed integer, |

671 | //or 0 otherwise. |

672 | DECMOD_GMP_INTS |

673 | int GMP_INTS_mpz_fits_sint_p (const GMP_INTS_mpz_struct *src); |

674 | |

675 | //Retrieves an unsigned version of limb zero from the number, |

676 | //or will return zero if the number is zero. This is the |

677 | //officially sanctioned way to get the value if it fits in |

678 | //an unsigned. |

679 | DECMOD_GMP_INTS |

680 | unsigned GMP_INTS_mpz_get_limb_zero(const GMP_INTS_mpz_struct *src); |

681 | |

682 | //Returnes neg value if u<v, 0 if u==v, and 1 if u>v. |

683 | DECMOD_GMP_INTS |

684 | int GMP_INTS_mpz_cmp (const GMP_INTS_mpz_struct *u, |

685 | const GMP_INTS_mpz_struct *v); |

686 | |

687 | //Compares an arbitrary integer to an unsigned long |

688 | //and returns relative ordering, <0 if u < v, 0 if u==v, |

689 | //and >0 if u > v. |

690 | DECMOD_GMP_INTS |

691 | int GMP_INTS_mpz_cmp_ui (const GMP_INTS_mpz_struct *u, |

692 | unsigned long int v_digit); |

693 | //Compares arbitrary integer to a signed long |

694 | //and returns relative ordering, <0 if u<v, 0 if u==v, |

695 | //and >0 if u>v. |

696 | DECMOD_GMP_INTS |

697 | int GMP_INTS_mpz_cmp_si (const GMP_INTS_mpz_struct *u, |

698 | signed long int v_digit); |

699 | |

700 | //Compares the absolute value of two arbitrary integers. |

701 | DECMOD_GMP_INTS |

702 | int GMP_INTS_mpz_cmpabs (const GMP_INTS_mpz_struct *u, |

703 | const GMP_INTS_mpz_struct *v); |

704 | //Compares the absolute value of an arbitrary integer and |

705 | //an unsigned long. |

706 | DECMOD_GMP_INTS |

707 | int GMP_INTS_mpz_cmpabs_ui(const GMP_INTS_mpz_struct *u, |

708 | unsigned long int v_digit); |

709 | |

710 | /****************************************************************/ |

711 | /*** VERSION CONTROL REPORTING FUNCTIONS ********************/ |

712 | /****************************************************************/ |

713 | DECMOD_GMP_INTS const char *GMP_INTS_cvcinfo(void); |

714 | DECMOD_GMP_INTS const char *GMP_INTS_hvcinfo(void); |

715 | |

716 | /* Preprocessor string to allow the H-file version to be |

717 | ** compiled into the C-file. |

718 | */ |

719 | #define GMP_INTS_H_VERSION ("$Header$") |

720 | |

721 | #endif /* GMP_INTS_H_INCLUDED */ |

722 | |

723 | // End of gmp_ints.h. |

Name | Value |
---|---|

svn:keywords |
Header |

dashley@gmail.com | ViewVC Help |

Powered by ViewVC 1.1.25 |