1 /*
2 * bignum.h
3 * GlowWorm
4 *
5 * Created by Curtis Jones on 2006.06.28.
6 * Copyright 2006 __MyCompanyName__. All rights reserved.
7 *
8 */
9
10 #ifndef __BIGNUM_H__
11 #define __BIGNUM_H__
12
13 #include <stdio.h>
14 #include <errno.h>
15 #include <stdlib.h>
16 #include <string.h>
17 #include <strings.h>
18 #include <unistd.h>
19 #include <sys/types.h>
20
21 #ifndef TRUE
22 #define TRUE 1
23 #endif
24
25 #ifndef FALSE
26 #define FALSE 0
27 #endif
28
29 #define BIGNUM_BASE_TYPE u_int32_t
30
31 //#define BIGNUM_SOFB_08 1
32 //#define BIGNUM_SOFB_16 2
33 #define BIGNUM_SOFB_32 3
34 //#define BIGNUM_SOFB_64 4
35 //#define BIGNUM_SOFB_128 5
36
37 #define BIGNUM_POSITIVE 1
38 #define BIGNUM_NEGATIVE 2
39
40 #define BIGNUM_MAX_ORDERS 100000
41
42 #define BIGNUM_MAX(a,b) ((a) > (b) ? (a) : (b))
43 #define BIGNUM_MIN(a,b) ((a) < (b) ? (a) : (b))
44
45 struct bignum
46 {
47 u_int8_t sign; // BIGNUM_POSITIVE or BIGNUM_NEGATIVE
48 u_int64_t oofm; // orders of magnitude
49 u_int64_t sofb; // size of base ... sizeof(u_int8_t)
50 u_int64_t size; // storage capacity for number ... numb[size]
51 u_int64_t base; // base of storage system
52 BIGNUM_BASE_TYPE * numb; // number storage
53 };
54 typedef struct bignum bignum_t;
55
56
57
58
59
60 bignum_t * bignum_alloc ();
61 void bignum_free (bignum_t *num);
62 void bignum_init ();
63
64 bignum_t * bignum_rnd_mag (bignum_t *num, u_int64_t size);
65 bignum_t * bignum_rnd_max (bignum_t *num, bignum_t *max);
66
67 bignum_t * bignum_set (bignum_t *, u_int64_t val);
68 bignum_t * bignum_set_ui8 (bignum_t *, u_int64_t cnt, BIGNUM_BASE_TYPE val[]);
69 bignum_t * bignum_set_bn (bignum_t *, bignum_t *);
70 bignum_t * bignum_set_str (bignum_t *, unsigned int radix, const char *);
71 void bignum_print (bignum_t *);
72 int bignum_cstr (bignum_t *, int len, char *str);
73 int bignum_cstr_base (bignum_t *, int str_len, char *str, int base);
74 char * bignum_cstr_base2 (bignum_t *, int precision, int base);
75 unsigned char * bignum_getbytes(bignum_t *, unsigned char *);
76 bignum_t * bignum_setbytes (bignum_t *, unsigned char *, int len);
77
78 u_int32_t bignum_get_uint32 (bignum_t *num);
79
80 bignum_t * bignum_rshift (bignum_t *num, u_int64_t cnt);
81 int bignum_isbitset (bignum_t *num, u_int64_t bit);
82 u_int64_t bignum_lowest_set_bit (bignum_t *num);
83 u_int64_t bignum_bitlen (bignum_t *num);
84 u_int64_t bignum_bytelen (bignum_t *num);
85
86 bignum_t * bignum_add (bignum_t *sum, bignum_t *num1, bignum_t *num2);
87 bignum_t * bignum_sub (bignum_t *dif, bignum_t *min, bignum_t *sub);
88 bignum_t * bignum_mul (bignum_t *prod, bignum_t *fac1, bignum_t *fac2);
89 bignum_t * bignum_div_aux (bignum_t *quot, bignum_t *rmdr, bignum_t *divd, bignum_t *divs);
90 bignum_t * bignum_div (bignum_t *quot, bignum_t *rmdr, bignum_t *divd, bignum_t *divs);
91 bignum_t * bignum_mod (bignum_t *rmdr, bignum_t *divd, bignum_t *divs);
92 bignum_t * bignum_modpow (bignum_t *res, bignum_t *num, bignum_t *exp, bignum_t *mod);
93 bignum_t * bignum_modinv (bignum_t *res_d, bignum_t *res_x, bignum_t *res_y, bignum_t *num, bignum_t *mod);
94 bignum_t * bignum_gcd (bignum_t *res, bignum_t *num1, bignum_t *num2);
95 bignum_t * bignum_pow (bignum_t *Y, bignum_t *num, bignum_t *exp);
96
97 bignum_t * bignum_factorial (bignum_t *total, bignum_t *num);
98 bignum_t * bignum_factorial_poor (bignum_t *total, bignum_t *num);
99
100 inline int bignum_cmp (bignum_t *num1, bignum_t *num2);
101 inline int bignum_eq (bignum_t *num1, bignum_t *num2);
102 inline int bignum_gt (bignum_t *num1, bignum_t *num2);
103 inline int bignum_lt (bignum_t *num1, bignum_t *num2);
104 inline int bignum_iszero (bignum_t *num);
105
106 inline BIGNUM_BASE_TYPE __bignum_get (bignum_t *num, u_int64_t pos);
107 inline void __bignum_set (bignum_t *num, u_int64_t pos, BIGNUM_BASE_TYPE val);
108
109 void __bignum_grow (bignum_t *num, u_int64_t size);
110 void __bignum_zero (bignum_t *num);
111 void __bignum_trim (bignum_t *num);
112
113 bignum_t * bignum_zero ();
114 bignum_t * bignum_one ();
115 bignum_t * bignum_two ();
116 bignum_t * bignum_three ();
117 bignum_t * bignum_four ();
118 bignum_t * bignum_five ();
119 bignum_t * bignum_six ();
120 bignum_t * bignum_seven ();
121 bignum_t * bignum_eight ();
122 bignum_t * bignum_nine ();
123 bignum_t * bignum_ten ();
124 bignum_t * bignum_eleven ();
125 bignum_t * bignum_twelve ();
126 bignum_t * bignum_thirteen ();
127 bignum_t * bignum_fourteen ();
128 bignum_t * bignum_fifteen ();
129 bignum_t * bignum_sixteen ();
130 bignum_t * bignum_seventeen ();
131 bignum_t * bignum_eighteen ();
132 bignum_t * bignum_nineteen ();
133 bignum_t * bignum_twenty ();
134 bignum_t * bignum_thirty_two ();
135 bignum_t * bignum_one_hundred ();
136
137 #endif /* __BIGNUM_H__ */
syntax highlighted by Code2HTML, v. 0.9.1