xref: /illumos-gate/usr/src/common/bignum/bignum.h (revision 6ea3c060)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 
22 /*
23  * Copyright (c) 2003, 2010, Oracle and/or its affiliates. All rights reserved.
24  */
25 
26 #ifndef _BIGNUM_H
27 #define	_BIGNUM_H
28 
29 #ifdef	__cplusplus
30 extern "C" {
31 #endif
32 
33 #include <sys/types.h>
34 
35 #if defined(__sparcv9) || defined(__amd64) /* 64-bit chunk size */
36 #ifndef UMUL64
37 #define	UMUL64	/* 64-bit multiplication results are supported */
38 #endif
39 #else
40 #define	BIGNUM_CHUNK_32
41 #endif
42 
43 
44 #define	BITSINBYTE	8
45 
46 /* Bignum "digits" (aka "chunks" or "words") are either 32- or 64-bits */
47 #ifdef BIGNUM_CHUNK_32
48 #define	BIG_CHUNK_SIZE		32
49 #define	BIG_CHUNK_TYPE		uint32_t
50 #define	BIG_CHUNK_TYPE_SIGNED	int32_t
51 #define	BIG_CHUNK_HIGHBIT	0x80000000
52 #define	BIG_CHUNK_ALLBITS	0xffffffff
53 #define	BIG_CHUNK_LOWHALFBITS	0xffff
54 #define	BIG_CHUNK_HALF_HIGHBIT	0x8000
55 
56 #else
57 #define	BIG_CHUNK_SIZE		64
58 #define	BIG_CHUNK_TYPE		uint64_t
59 #define	BIG_CHUNK_TYPE_SIGNED	int64_t
60 #define	BIG_CHUNK_HIGHBIT	0x8000000000000000ULL
61 #define	BIG_CHUNK_ALLBITS	0xffffffffffffffffULL
62 #define	BIG_CHUNK_LOWHALFBITS	0xffffffffULL
63 #define	BIG_CHUNK_HALF_HIGHBIT	0x80000000ULL
64 #endif
65 
66 #define	BITLEN2BIGNUMLEN(x)	((x) > 0 ? \
67 				((((x) - 1) / BIG_CHUNK_SIZE) + 1) : 0)
68 #define	CHARLEN2BIGNUMLEN(x)	((x) > 0 ? \
69 				((((x) - 1) / sizeof (BIG_CHUNK_TYPE)) + 1) : 0)
70 
71 #define	BIGNUM_WORDSIZE	(BIG_CHUNK_SIZE / BITSINBYTE)  /* word size in bytes */
72 #define	BIG_CHUNKS_FOR_160BITS	BITLEN2BIGNUMLEN(160)
73 
74 
75 /*
76  * leading 0's are permitted
77  * 0 should be represented by size>=1, size>=len>=1, sign=1,
78  * value[i]=0 for 0<i<len
79  */
80 typedef struct {
81 	/* size and len in units of BIG_CHUNK_TYPE words  */
82 	uint32_t	size;	/* size of memory allocated for value  */
83 	uint32_t	len;	/* number of valid data words in value */
84 	int		sign;	/* 1 for nonnegative, -1 for negative  */
85 	int		malloced; /* 1 if value was malloced, 0 if not */
86 	BIG_CHUNK_TYPE *value;
87 } BIGNUM;
88 
89 #define	BIGTMPSIZE 65
90 
91 #define	BIG_TRUE 1
92 #define	BIG_FALSE 0
93 
94 typedef int BIG_ERR_CODE;
95 
96 /* error codes */
97 #define	BIG_OK 0
98 #define	BIG_NO_MEM -1
99 #define	BIG_INVALID_ARGS -2
100 #define	BIG_DIV_BY_0 -3
101 #define	BIG_NO_RANDOM -4
102 #define	BIG_GENERAL_ERR	-5
103 #define	BIG_TEST_FAILED -6
104 #define	BIG_BUFFER_TOO_SMALL -7
105 
106 
107 #define	arraysize(x) (sizeof (x) / sizeof (x[0]))
108 
109 typedef BIG_ERR_CODE (*big_modexp_ncp_func_ptr)(BIGNUM *result,
110     BIGNUM *ma, BIGNUM *e, BIGNUM *n,
111     BIGNUM *tmp, BIG_CHUNK_TYPE n0, void *ncp, void *req);
112 
113 typedef struct {
114 	big_modexp_ncp_func_ptr	func;
115 	void			*ncp;
116 	void 			*reqp;
117 } big_modexp_ncp_info_t;
118 
119 
120 #ifdef USE_FLOATING_POINT
121 void conv_d16_to_i32(uint32_t *i32, double *d16, int64_t *tmp, int ilen);
122 void conv_i32_to_d32(double *d32, uint32_t *i32, int len);
123 void conv_i32_to_d16(double *d16, uint32_t *i32, int len);
124 void conv_i32_to_d32_and_d16(double *d32, double *d16,
125     uint32_t *i32, int len);
126 void mont_mulf_noconv(uint32_t *result, double *dm1, double *dm2, double *dt,
127     double *dn, uint32_t *nint, int nlen, double dn0);
128 #endif /* USE_FLOATING_POINT */
129 
130 extern BIGNUM big_One;
131 extern BIGNUM big_Two;
132 
133 void printbignum(char *aname, BIGNUM *a);
134 
135 BIG_ERR_CODE big_init(BIGNUM *number, int size);
136 BIG_ERR_CODE big_extend(BIGNUM *number, int size);
137 void big_finish(BIGNUM *number);
138 void bytestring2bignum(BIGNUM *bn, uchar_t *kn, size_t len);
139 void bignum2bytestring(uchar_t *kn, BIGNUM *bn, size_t len);
140 BIG_ERR_CODE big_mont_rr(BIGNUM *result, BIGNUM *n);
141 BIG_ERR_CODE big_modexp(BIGNUM *result, BIGNUM *a, BIGNUM *e,
142     BIGNUM *n, BIGNUM *n_rr);
143 BIG_ERR_CODE big_modexp_ext(BIGNUM *result, BIGNUM *a, BIGNUM *e,
144     BIGNUM *n, BIGNUM *n_rr, big_modexp_ncp_info_t *info);
145 BIG_ERR_CODE big_modexp_crt(BIGNUM *result, BIGNUM *a, BIGNUM *dmodpminus1,
146     BIGNUM *dmodqminus1, BIGNUM *p, BIGNUM *q, BIGNUM *pinvmodq,
147     BIGNUM *p_rr, BIGNUM *q_rr);
148 BIG_ERR_CODE big_modexp_crt_ext(BIGNUM *result, BIGNUM *a, BIGNUM *dmodpminus1,
149     BIGNUM *dmodqminus1, BIGNUM *p, BIGNUM *q, BIGNUM *pinvmodq,
150     BIGNUM *p_rr, BIGNUM *q_rr, big_modexp_ncp_info_t *info);
151 int big_cmp_abs(BIGNUM *a, BIGNUM *b);
152 BIG_ERR_CODE big_random(BIGNUM *r, size_t length, int (*rfunc)(void *, size_t));
153 BIG_ERR_CODE big_div_pos(BIGNUM *result, BIGNUM *remainder,
154     BIGNUM *aa, BIGNUM *bb);
155 BIG_ERR_CODE big_ext_gcd_pos(BIGNUM *gcd, BIGNUM *cm, BIGNUM *ce,
156     BIGNUM *m, BIGNUM *e);
157 BIG_ERR_CODE big_add(BIGNUM *result, BIGNUM *aa, BIGNUM *bb);
158 BIG_ERR_CODE big_add_abs(BIGNUM *result, BIGNUM *aa, BIGNUM *bb);
159 BIG_ERR_CODE big_mul(BIGNUM *result, BIGNUM *aa, BIGNUM *bb);
160 void big_shiftright(BIGNUM *result, BIGNUM *aa, int offs);
161 BIG_ERR_CODE big_nextprime_pos(BIGNUM *result, BIGNUM *n);
162 BIG_ERR_CODE big_nextprime_pos_ext(BIGNUM *result, BIGNUM *n,
163     big_modexp_ncp_info_t *info);
164 BIG_ERR_CODE big_sub_pos(BIGNUM *result, BIGNUM *aa, BIGNUM *bb);
165 BIG_ERR_CODE big_copy(BIGNUM *dest, BIGNUM *src);
166 BIG_ERR_CODE big_sub(BIGNUM *result, BIGNUM *aa, BIGNUM *bb);
167 int big_bitlength(BIGNUM *n);
168 BIG_ERR_CODE big_init1(BIGNUM *number, int size,
169     BIG_CHUNK_TYPE *buf, int bufsize);
170 BIG_ERR_CODE big_mont_mul(BIGNUM *ret,
171     BIGNUM *a, BIGNUM *b, BIGNUM *n, BIG_CHUNK_TYPE n0);
172 int big_is_zero(BIGNUM *n);
173 BIG_CHUNK_TYPE big_n0(BIG_CHUNK_TYPE n);
174 
175 
176 #if defined(HWCAP)
177 
178 #if (BIG_CHUNK_SIZE != 32)
179 #error HWCAP works only with 32-bit bignum chunks
180 #endif
181 
182 #define	BIG_MUL_SET_VEC(r, a, len, digit) \
183 	(*big_mul_set_vec_impl)(r, a, len, digit)
184 #define	BIG_MUL_ADD_VEC(r, a, len, digit) \
185 	(*big_mul_add_vec_impl)(r, a, len, digit)
186 #define	BIG_MUL_VEC(r, a, alen, b, blen) \
187 	(*big_mul_vec_impl)(r, a, alen, b, blen)
188 #define	BIG_SQR_VEC(r, a, len) \
189 	(*big_sqr_vec_impl)(r, a, len)
190 
191 extern BIG_CHUNK_TYPE (*big_mul_set_vec_impl)
192 	(BIG_CHUNK_TYPE *r, BIG_CHUNK_TYPE *a, int len, BIG_CHUNK_TYPE digit);
193 extern BIG_CHUNK_TYPE (*big_mul_add_vec_impl)
194 	(BIG_CHUNK_TYPE *r, BIG_CHUNK_TYPE *a, int len, BIG_CHUNK_TYPE digit);
195 extern void (*big_mul_vec_impl)
196 	(BIG_CHUNK_TYPE *r, BIG_CHUNK_TYPE *a, int alen, BIG_CHUNK_TYPE *b,
197 	    int blen);
198 extern void (*big_sqr_vec_impl)
199 	(BIG_CHUNK_TYPE *r, BIG_CHUNK_TYPE *a, int len);
200 
201 #else /* ! HWCAP */
202 
203 #define	BIG_MUL_SET_VEC(r, a, len, digit) big_mul_set_vec(r, a, len, digit)
204 #define	BIG_MUL_ADD_VEC(r, a, len, digit) big_mul_add_vec(r, a, len, digit)
205 #define	BIG_MUL_VEC(r, a, alen, b, blen) big_mul_vec(r, a, alen, b, blen)
206 #define	BIG_SQR_VEC(r, a, len) big_sqr_vec(r, a, len)
207 
208 extern BIG_CHUNK_TYPE big_mul_set_vec(BIG_CHUNK_TYPE *r, BIG_CHUNK_TYPE *a,
209     int len, BIG_CHUNK_TYPE d);
210 extern BIG_CHUNK_TYPE big_mul_add_vec(BIG_CHUNK_TYPE *r,
211     BIG_CHUNK_TYPE *a, int len, BIG_CHUNK_TYPE d);
212 extern void big_mul_vec(BIG_CHUNK_TYPE *r, BIG_CHUNK_TYPE *a, int alen,
213     BIG_CHUNK_TYPE *b, int blen);
214 extern void big_sqr_vec(BIG_CHUNK_TYPE *r, BIG_CHUNK_TYPE *a, int len);
215 
216 #endif /* HWCAP */
217 
218 #ifdef	__cplusplus
219 }
220 #endif
221 
222 #endif	/* _BIGNUM_H */
223