1 /* 2 * Copyright (c) 2002 by The XFree86 Project, Inc. 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining a 5 * copy of this software and associated documentation files (the "Software"), 6 * to deal in the Software without restriction, including without limitation 7 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8 * and/or sell copies of the Software, and to permit persons to whom the 9 * Software is furnished to do so, subject to the following conditions: 10 * 11 * The above copyright notice and this permission notice shall be included in 12 * all copies or substantial portions of the Software. 13 * 14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 17 * THE XFREE86 PROJECT BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 18 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF 19 * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 20 * SOFTWARE. 21 * 22 * Except as contained in this notice, the name of the XFree86 Project shall 23 * not be used in advertising or otherwise to promote the sale, use or other 24 * dealings in this Software without prior written authorization from the 25 * XFree86 Project. 26 * 27 * Author: Paulo Csar Pereira de Andrade 28 */ 29 30 /* $XFree86: xc/programs/xedit/lisp/mp/mp.h,v 1.5tsi Exp $ */ 31 32 #include <stdio.h> 33 #include <math.h> 34 #ifdef sun 35 #include <ieeefp.h> 36 #endif 37 #include <float.h> 38 #include <stdlib.h> 39 #include <limits.h> 40 #include <ctype.h> 41 #include <string.h> 42 43 #ifndef __mp_h_ 44 #define __mp_h_ 45 46 /* relies on autoconf's AC_C_INLINE to #define inline if needed */ 47 #define INLINE inline 48 49 /* this normally is better for multiplication and also 50 * simplify addition loops putting the larger value first */ 51 #define MP_SWAP(op1, op2, len1, len2) { \ 52 BNS *top = op1; \ 53 BNI tlen = len1; \ 54 \ 55 op1 = op2; \ 56 len1 = len2; \ 57 op2 = top; \ 58 len2 = tlen; \ 59 } 60 61 /* 62 * At least this length to use Karatsuba multiplication method 63 */ 64 #define KARATSUBA 32 65 66 /* 67 * At least this length to use Toom multiplication method 68 */ 69 #define TOOM 128 70 71 #if ULONG_MAX > 4294967295UL 72 /* sizeof(long) == 8 and sizeof(int) == 4 */ 73 # define BNI unsigned long 74 # define BNS unsigned int 75 # define MINSLONG 0x8000000000000000UL 76 # define MAXSLONG 0x7fffffffffffffffUL 77 # define CARRY 0x100000000 78 # define LMASK 0xffffffff00000000UL 79 # define SMASK 0x00000000ffffffffUL 80 # define BNIBITS 64 81 # define BNSBITS 32 82 # ifndef LONG64 83 # define LONG64 84 # endif 85 #else 86 /* sizeof(long) == 4 and sizeof(short) == 2 */ 87 # define BNI unsigned long 88 # define BNS unsigned short 89 # define MINSLONG 0x80000000UL 90 # define MAXSLONG 0x7fffffffUL 91 # define CARRY 0x10000 92 # define LMASK 0xffff0000UL 93 # define SMASK 0x0000ffffUL 94 # define BNIBITS 32 95 # define BNSBITS 16 96 #endif 97 98 #ifdef MAX 99 #undef MAX 100 #endif 101 #define MAX(a, b) ((a) > (b) ? (a) : (b)) 102 103 #ifdef MIN 104 #undef MIN 105 #endif 106 #define MIN(a, b) ((a) < (b) ? (a) : (b)) 107 108 /* 109 * Types 110 */ 111 typedef struct _mpi { 112 unsigned int size : 31; 113 unsigned int sign : 1; 114 BNI alloc; 115 BNS *digs; /* LSF format */ 116 } mpi; 117 118 typedef struct _mpr { 119 mpi num; 120 mpi den; 121 } mpr; 122 123 typedef void *(*mp_malloc_fun)(size_t); 124 typedef void *(*mp_calloc_fun)(size_t, size_t); 125 typedef void *(*mp_realloc_fun)(void*, size_t); 126 typedef void (*mp_free_fun)(void*); 127 128 /* 129 * Prototypes 130 */ 131 /* GENERIC FUNCTIONS */ 132 /* memory allocation wrappers */ 133 void *mp_malloc(size_t size); 134 void *mp_calloc(size_t nmemb, size_t size); 135 void *mp_realloc(void *pointer, size_t size); 136 void mp_free(void *pointer); 137 mp_malloc_fun mp_set_malloc(mp_malloc_fun); 138 mp_calloc_fun mp_set_calloc(mp_calloc_fun); 139 mp_realloc_fun mp_set_realloc(mp_realloc_fun); 140 mp_free_fun mp_set_free(mp_free_fun); 141 142 /* adds op1 and op2, stores result in rop 143 * rop must pointer to at least len1 + len2 + 1 elements 144 * rop can be either op1 or op2 */ 145 long mp_add(BNS *rop, BNS *op1, BNS *op2, BNI len1, BNI len2); 146 147 /* subtracts op2 from op1, stores result in rop 148 * rop must pointer to at least len1 + len2 elements 149 * op1 must be >= op2 150 * rop can be either op1 or op2 */ 151 long mp_sub(BNS *rop, BNS *op1, BNS *op2, BNI len1, BNI len2); 152 153 /* shift op to the left shift bits 154 * rop must have enough storage for result 155 * rop can be op */ 156 long mp_lshift(BNS *rop, BNS *op, BNI len, long shift); 157 158 /* shift op to the right shift bits 159 * shift must be positive 160 * rop can be op */ 161 long mp_rshift(BNS *rop, BNS *op, BNI len, long shift); 162 163 /* use simple generic multiplication method 164 * rop cannot be the same as op1 or op2 165 * rop must be zeroed 166 * op1 can be op2 */ 167 long mp_base_mul(BNS *rop, BNS *op1, BNS *op2, BNI len1, BNI len2); 168 169 /* use Karatsuba method 170 * MIN(len1, len2) must be larger than (MAX(len1, len2) + 1) >> 1 171 * MAX(len1, len2) should be at least 2 172 * rop cannot be the same as op1 or op2 173 * rop must be zeroed 174 * op1 can be op2 */ 175 long mp_karatsuba_mul(BNS *rop, BNS *op1, BNS *op2, BNI len1, BNI len2); 176 177 /* use Toom method 178 * len1 / 3 should be equal to len2 / 3 179 * len1 / 3 should be at least 1 180 * rop cannot be the same as op1 or op2 181 * rop must be zeroed 182 * op1 can be op2 */ 183 long mp_toom_mul(BNS *rop, BNS *op1, BNS *op2, BNI len1, BNI len2); 184 185 /* chooses the available multiplication methods based on it's input 186 * rop must be a pointer to len1 + len2 elements 187 * rop cannot be the same as op1 or op2 188 * rop must be zeroed 189 * op1 can be op2 */ 190 long mp_mul(BNS *rop, BNS *op1, BNS *op2, BNI len1, BNI len2); 191 192 /* INTEGER FUNCTIONS */ 193 /* initialize op and set it to 0 */ 194 void mpi_init(mpi *op); 195 196 /* clear memory associated to op */ 197 void mpi_clear(mpi *op); 198 199 /* set rop to the value of op */ 200 void mpi_set(mpi *rop, mpi *op); 201 202 /* set rop to the value of si */ 203 void mpi_seti(mpi *rop, long si); 204 205 /* set rop to the floor(fabs(d)) */ 206 void mpi_setd(mpi *rop, double d); 207 208 /* initialize rop to number representation in str in the given base. 209 * leading zeros are skipped. 210 * if sign present, it is processed. 211 * base must be in the range 2 to 36. */ 212 void mpi_setstr(mpi *rop, char *str, int base); 213 214 /* adds two mp integers */ 215 void mpi_add(mpi *rop, mpi *op1, mpi *op2); 216 217 /* adds op1 and op2 */ 218 void mpi_addi(mpi *rop, mpi *op1, long op2); 219 220 /* subtracts two mp integers */ 221 void mpi_sub(mpi *rop, mpi *op1, mpi *op2); 222 223 /* subtracts op2 from op1 */ 224 void mpi_subi(mpi *rop, mpi *op1, long op2); 225 226 /* multiply two mp integers */ 227 void mpi_mul(mpi *rop, mpi *op1, mpi *op2); 228 229 /* multiply op1 by op2 */ 230 void mpi_muli(mpi *rop, mpi *op1, long op2); 231 232 /* divides num by den and sets rop to result */ 233 void mpi_div(mpi *rop, mpi *num, mpi *den); 234 235 /* divides num by den and sets rop to the remainder */ 236 void mpi_rem(mpi *rop, mpi *num, mpi *den); 237 238 /* divides num by den, sets quotient to qrop and remainder to rrop 239 * qrop is truncated towards zero. 240 * qrop and rrop are optional 241 * qrop and rrop cannot be the same variable */ 242 void mpi_divqr(mpi *qrop, mpi *rrop, mpi *num, mpi *den); 243 244 /* divides num by then and stores result in rop */ 245 void mpi_divi(mpi *rop, mpi *num, long den); 246 247 /* divides num by den and returns remainder */ 248 long mpi_remi(mpi *num, long den); 249 250 /* divides num by den 251 * stores quotient in qrop and returns remainder */ 252 long mpi_divqri(mpi *qrop, mpi *num, long den); 253 254 /* sets rop to num modulo den */ 255 void mpi_mod(mpi *rop, mpi *num, mpi *den); 256 257 /* returns num modulo den */ 258 long mpi_modi(mpi *num, long den); 259 260 /* sets rop to the greatest common divisor of num and den 261 * result is always positive */ 262 void mpi_gcd(mpi *rop, mpi *num, mpi *den); 263 264 /* sets rop to the least common multiple of num and den 265 * result is always positive */ 266 void mpi_lcm(mpi *rop, mpi *num, mpi *den); 267 268 /* sets rop to op raised to exp */ 269 void mpi_pow(mpi *rop, mpi *op, unsigned long exp); 270 271 /* sets rop to the integer part of the nth root of op. 272 * returns 1 if result is exact, 0 otherwise */ 273 int mpi_root(mpi *rop, mpi *op, unsigned long nth); 274 275 /* sets rop to the integer part of the square root of op. 276 * returns 1 if result is exact, 0 otherwise */ 277 int mpi_sqrt(mpi *rop, mpi *op); 278 279 /* bit shift, left if shift positive, right if negative 280 * a fast way to multiply and divide by powers of two */ 281 void mpi_ash(mpi *rop, mpi *op, long shift); 282 283 /* sets rop to op1 logand op2 */ 284 void mpi_and(mpi *rop, mpi *op1, mpi *op2); 285 286 /* sets rop to op1 logior op2 */ 287 void mpi_ior(mpi *rop, mpi *op1, mpi *op2); 288 289 /* sets rop to op1 logxor op2 */ 290 void mpi_xor(mpi *rop, mpi *op1, mpi *op2); 291 292 /* sets rop to one's complement of op */ 293 void mpi_com(mpi *rop, mpi *op); 294 295 /* sets rop to -op */ 296 void mpi_neg(mpi *rop, mpi *op); 297 298 /* sets rop to the absolute value of op */ 299 void mpi_abs(mpi *rop, mpi *op); 300 301 /* compares op1 and op2 302 * returns >0 if op1 > op2, 0 if op1 = op2, and <0 if op1 < op2 */ 303 int mpi_cmp(mpi *op1, mpi *op2); 304 305 /* mpi_cmp with a long integer operand */ 306 int mpi_cmpi(mpi *op1, long op2); 307 308 /* compares absolute value of op1 and op2 309 * returns >0 if abs(op1) > abs(op2), 0 if abs(op1) = abs(op2), 310 * and <0 if abs(op1) < abs(op2) */ 311 int mpi_cmpabs(mpi *op1, mpi *op2); 312 313 /* mpi_cmpabs with a long integer operand */ 314 int mpi_cmpabsi(mpi *op1, long op2); 315 316 /* returns 1 if op1 > 0, 0 if op1 = 0, and -1 if op1 < 0 */ 317 int mpi_sgn(mpi *op); 318 319 /* fastly swaps contents of op1 and op2 */ 320 void mpi_swap(mpi *op1, mpi *op2); 321 322 /* returns 1 if op fits in a signed long int, 0 otherwise */ 323 int mpi_fiti(mpi *op); 324 325 /* converts mp integer to long int 326 * to know if the value will fit, call mpi_fiti */ 327 long mpi_geti(mpi *op); 328 329 /* convert mp integer to double */ 330 double mpi_getd(mpi *op); 331 332 /* returns exact number of characters to represent mp integer 333 * in given base, excluding sign and ending null character. 334 * base must be in the range 2 to 36 */ 335 unsigned long mpi_getsize(mpi *op, int base); 336 337 /* returns pointer to string with representation of mp integer 338 * if str is not NULL, it must have enough space to store integer 339 * representation, if NULL a newly allocated string is returned. 340 * base must be in the range 2 to 36 */ 341 char *mpi_getstr(char *str, mpi *op, int base); 342 343 /* RATIO FUNCTIONS */ 344 #define mpr_num(op) (&((op)->num)) 345 #define mpr_den(op) (&((op)->den)) 346 347 /* initialize op and set it to 0/1 */ 348 void mpr_init(mpr *op); 349 350 /* clear memory associated to op */ 351 void mpr_clear(mpr *op); 352 353 /* set rop to the value of op */ 354 void mpr_set(mpr *rop, mpr *op); 355 356 /* set rop to num/den */ 357 void mpr_seti(mpr *rop, long num, long den); 358 359 /* set rop to the value of d */ 360 void mpr_setd(mpr *rop, double d); 361 362 /* initialize rop to number representation in str in the given base. 363 * leading zeros are skipped. 364 * if sign present, it is processed. 365 * base must be in the range 2 to 36. */ 366 void mpr_setstr(mpr *rop, char *str, int base); 367 368 /* remove common factors of op */ 369 void mpr_canonicalize(mpr *op); 370 371 /* adds two mp rationals */ 372 void mpr_add(mpr *rop, mpr *op1, mpr *op2); 373 374 /* adds op1 and op2 */ 375 void mpr_addi(mpr *rop, mpr *op1, long op2); 376 377 /* subtracts two mp rationals */ 378 void mpr_sub(mpr *rop, mpr *op1, mpr *op2); 379 380 /* subtracts op2 from op1 */ 381 void mpr_subi(mpr *rop, mpr *op1, long op2); 382 383 /* multiply two mp rationals */ 384 void mpr_mul(mpr *rop, mpr *op1, mpr *op2); 385 386 /* multiply op1 by op2 */ 387 void mpr_muli(mpr *rop, mpr *op1, long op2); 388 389 /* divide two mp rationals */ 390 void mpr_div(mpr *rop, mpr *op1, mpr *op2); 391 392 /* divides op1 by op2 */ 393 void mpr_divi(mpr *rop, mpr *op1, long op2); 394 395 /* sets rop to 1/op */ 396 void mpr_inv(mpr *rop, mpr *op); 397 398 /* sets rop to -op */ 399 void mpr_neg(mpr *rop, mpr *op); 400 401 /* sets rop to the absolute value of op */ 402 void mpr_abs(mpr *rop, mpr *op); 403 404 /* compares op1 and op2 405 * returns >0 if op1 > op2, 0 if op1 = op2, and <0 if op1 < op2 */ 406 int mpr_cmp(mpr *op1, mpr *op2); 407 408 /* mpr_cmp with a long integer operand */ 409 int mpr_cmpi(mpr *op1, long op2); 410 411 /* compares absolute value of op1 and op2 412 * returns >0 if abs(op1) > abs(op2), 0 if abs(op1) = abs(op2), 413 * and <0 if abs(op1) < abs(op2) */ 414 int mpr_cmpabs(mpr *op1, mpr *op2); 415 416 /* mpr_cmpabs with a long integer operand */ 417 int mpr_cmpabsi(mpr *op1, long op2); 418 419 /* fastly swaps contents of op1 and op2 */ 420 void mpr_swap(mpr *op1, mpr *op2); 421 422 /* returns 1 if op fits in a signed long int, 0 otherwise */ 423 int mpr_fiti(mpr *op); 424 425 /* convert mp rational to double */ 426 double mpr_getd(mpr *op); 427 428 /* returns pointer to string with representation of mp rational 429 * if str is not NULL, it must have enough space to store rational 430 * representation, if NULL a newly allocated string is returned. 431 * base must be in the range 2 to 36 */ 432 char *mpr_getstr(char *str, mpr *op, int base); 433 434 #endif /* __mp_h_ */ 435
Indexes created Wed Jul 01 00:25:26 UTC 2026