xref: /illumos-gate/usr/src/common/bignum/bignum.h (revision 6ea3c060)
17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate  * CDDL HEADER START
37c478bd9Sstevel@tonic-gate  *
47c478bd9Sstevel@tonic-gate  * The contents of this file are subject to the terms of the
5b60f2a0bSfr  * Common Development and Distribution License (the "License").
6b60f2a0bSfr  * You may not use this file except in compliance with the License.
77c478bd9Sstevel@tonic-gate  *
87c478bd9Sstevel@tonic-gate  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
97c478bd9Sstevel@tonic-gate  * or http://www.opensolaris.org/os/licensing.
107c478bd9Sstevel@tonic-gate  * See the License for the specific language governing permissions
117c478bd9Sstevel@tonic-gate  * and limitations under the License.
127c478bd9Sstevel@tonic-gate  *
137c478bd9Sstevel@tonic-gate  * When distributing Covered Code, include this CDDL HEADER in each
147c478bd9Sstevel@tonic-gate  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
157c478bd9Sstevel@tonic-gate  * If applicable, add the following below this CDDL HEADER, with the
167c478bd9Sstevel@tonic-gate  * fields enclosed by brackets "[]" replaced with your own identifying
177c478bd9Sstevel@tonic-gate  * information: Portions Copyright [yyyy] [name of copyright owner]
187c478bd9Sstevel@tonic-gate  *
197c478bd9Sstevel@tonic-gate  * CDDL HEADER END
207c478bd9Sstevel@tonic-gate  */
21*726fad2aSDina K Nimeh 
227c478bd9Sstevel@tonic-gate /*
23*726fad2aSDina K Nimeh  * Copyright (c) 2003, 2010, Oracle and/or its affiliates. All rights reserved.
247c478bd9Sstevel@tonic-gate  */
257c478bd9Sstevel@tonic-gate 
267c478bd9Sstevel@tonic-gate #ifndef _BIGNUM_H
277c478bd9Sstevel@tonic-gate #define	_BIGNUM_H
287c478bd9Sstevel@tonic-gate 
297c478bd9Sstevel@tonic-gate #ifdef	__cplusplus
307c478bd9Sstevel@tonic-gate extern "C" {
317c478bd9Sstevel@tonic-gate #endif
327c478bd9Sstevel@tonic-gate 
337c478bd9Sstevel@tonic-gate #include <sys/types.h>
347c478bd9Sstevel@tonic-gate 
358475e043SDan OpenSolaris Anderson #if defined(__sparcv9) || defined(__amd64) /* 64-bit chunk size */
36b60f2a0bSfr #ifndef UMUL64
378475e043SDan OpenSolaris Anderson #define	UMUL64	/* 64-bit multiplication results are supported */
38b60f2a0bSfr #endif
398475e043SDan OpenSolaris Anderson #else
408475e043SDan OpenSolaris Anderson #define	BIGNUM_CHUNK_32
41b60f2a0bSfr #endif
42b60f2a0bSfr 
43b60f2a0bSfr 
44b60f2a0bSfr #define	BITSINBYTE	8
45b60f2a0bSfr 
468475e043SDan OpenSolaris Anderson /* Bignum "digits" (aka "chunks" or "words") are either 32- or 64-bits */
47b60f2a0bSfr #ifdef BIGNUM_CHUNK_32
48b60f2a0bSfr #define	BIG_CHUNK_SIZE		32
49b60f2a0bSfr #define	BIG_CHUNK_TYPE		uint32_t
50b60f2a0bSfr #define	BIG_CHUNK_TYPE_SIGNED	int32_t
51b60f2a0bSfr #define	BIG_CHUNK_HIGHBIT	0x80000000
52b60f2a0bSfr #define	BIG_CHUNK_ALLBITS	0xffffffff
53b60f2a0bSfr #define	BIG_CHUNK_LOWHALFBITS	0xffff
54b60f2a0bSfr #define	BIG_CHUNK_HALF_HIGHBIT	0x8000
558475e043SDan OpenSolaris Anderson 
56b60f2a0bSfr #else
57b60f2a0bSfr #define	BIG_CHUNK_SIZE		64
58b60f2a0bSfr #define	BIG_CHUNK_TYPE		uint64_t
59b60f2a0bSfr #define	BIG_CHUNK_TYPE_SIGNED	int64_t
60b60f2a0bSfr #define	BIG_CHUNK_HIGHBIT	0x8000000000000000ULL
61b60f2a0bSfr #define	BIG_CHUNK_ALLBITS	0xffffffffffffffffULL
62b60f2a0bSfr #define	BIG_CHUNK_LOWHALFBITS	0xffffffffULL
63b60f2a0bSfr #define	BIG_CHUNK_HALF_HIGHBIT	0x80000000ULL
64b60f2a0bSfr #endif
65b60f2a0bSfr 
66*726fad2aSDina K Nimeh #define	BITLEN2BIGNUMLEN(x)	((x) > 0 ? \
67*726fad2aSDina K Nimeh 				((((x) - 1) / BIG_CHUNK_SIZE) + 1) : 0)
68*726fad2aSDina K Nimeh #define	CHARLEN2BIGNUMLEN(x)	((x) > 0 ? \
69*726fad2aSDina K Nimeh 				((((x) - 1) / sizeof (BIG_CHUNK_TYPE)) + 1) : 0)
70b60f2a0bSfr 
71b60f2a0bSfr #define	BIGNUM_WORDSIZE	(BIG_CHUNK_SIZE / BITSINBYTE)  /* word size in bytes */
72*726fad2aSDina K Nimeh #define	BIG_CHUNKS_FOR_160BITS	BITLEN2BIGNUMLEN(160)
737c478bd9Sstevel@tonic-gate 
747c478bd9Sstevel@tonic-gate 
757c478bd9Sstevel@tonic-gate /*
767c478bd9Sstevel@tonic-gate  * leading 0's are permitted
777c478bd9Sstevel@tonic-gate  * 0 should be represented by size>=1, size>=len>=1, sign=1,
787c478bd9Sstevel@tonic-gate  * value[i]=0 for 0<i<len
797c478bd9Sstevel@tonic-gate  */
807c478bd9Sstevel@tonic-gate typedef struct {
81b60f2a0bSfr 	/* size and len in units of BIG_CHUNK_TYPE words  */
828475e043SDan OpenSolaris Anderson 	uint32_t	size;	/* size of memory allocated for value  */
838475e043SDan OpenSolaris Anderson 	uint32_t	len;	/* number of valid data words in value */
848475e043SDan OpenSolaris Anderson 	int		sign;	/* 1 for nonnegative, -1 for negative  */
858475e043SDan OpenSolaris Anderson 	int		malloced; /* 1 if value was malloced, 0 if not */
86b60f2a0bSfr 	BIG_CHUNK_TYPE *value;
877c478bd9Sstevel@tonic-gate } BIGNUM;
887c478bd9Sstevel@tonic-gate 
897c478bd9Sstevel@tonic-gate #define	BIGTMPSIZE 65
907c478bd9Sstevel@tonic-gate 
917c478bd9Sstevel@tonic-gate #define	BIG_TRUE 1
927c478bd9Sstevel@tonic-gate #define	BIG_FALSE 0
937c478bd9Sstevel@tonic-gate 
94b60f2a0bSfr typedef int BIG_ERR_CODE;
95b60f2a0bSfr 
967c478bd9Sstevel@tonic-gate /* error codes */
977c478bd9Sstevel@tonic-gate #define	BIG_OK 0
987c478bd9Sstevel@tonic-gate #define	BIG_NO_MEM -1
997c478bd9Sstevel@tonic-gate #define	BIG_INVALID_ARGS -2
1007c478bd9Sstevel@tonic-gate #define	BIG_DIV_BY_0 -3
1017c478bd9Sstevel@tonic-gate #define	BIG_NO_RANDOM -4
1027c478bd9Sstevel@tonic-gate #define	BIG_GENERAL_ERR	-5
103b60f2a0bSfr #define	BIG_TEST_FAILED -6
104b60f2a0bSfr #define	BIG_BUFFER_TOO_SMALL -7
105b60f2a0bSfr 
1067c478bd9Sstevel@tonic-gate 
1077c478bd9Sstevel@tonic-gate #define	arraysize(x) (sizeof (x) / sizeof (x[0]))
1087c478bd9Sstevel@tonic-gate 
109b60f2a0bSfr typedef BIG_ERR_CODE (*big_modexp_ncp_func_ptr)(BIGNUM *result,
110b60f2a0bSfr     BIGNUM *ma, BIGNUM *e, BIGNUM *n,
111b60f2a0bSfr     BIGNUM *tmp, BIG_CHUNK_TYPE n0, void *ncp, void *req);
112b60f2a0bSfr 
113b60f2a0bSfr typedef struct {
114b60f2a0bSfr 	big_modexp_ncp_func_ptr	func;
115b60f2a0bSfr 	void			*ncp;
116b60f2a0bSfr 	void 			*reqp;
117b60f2a0bSfr } big_modexp_ncp_info_t;
118b60f2a0bSfr 
119b60f2a0bSfr 
1207c478bd9Sstevel@tonic-gate #ifdef USE_FLOATING_POINT
1217c478bd9Sstevel@tonic-gate void conv_d16_to_i32(uint32_t *i32, double *d16, int64_t *tmp, int ilen);
1227c478bd9Sstevel@tonic-gate void conv_i32_to_d32(double *d32, uint32_t *i32, int len);
1237c478bd9Sstevel@tonic-gate void conv_i32_to_d16(double *d16, uint32_t *i32, int len);
1247c478bd9Sstevel@tonic-gate void conv_i32_to_d32_and_d16(double *d32, double *d16,
1257c478bd9Sstevel@tonic-gate     uint32_t *i32, int len);
1267c478bd9Sstevel@tonic-gate void mont_mulf_noconv(uint32_t *result, double *dm1, double *dm2, double *dt,
1277c478bd9Sstevel@tonic-gate     double *dn, uint32_t *nint, int nlen, double dn0);
1287c478bd9Sstevel@tonic-gate #endif /* USE_FLOATING_POINT */
1297c478bd9Sstevel@tonic-gate 
130b60f2a0bSfr extern BIGNUM big_One;
131b60f2a0bSfr extern BIGNUM big_Two;
132b60f2a0bSfr 
1337c478bd9Sstevel@tonic-gate void printbignum(char *aname, BIGNUM *a);
1347c478bd9Sstevel@tonic-gate 
1357c478bd9Sstevel@tonic-gate BIG_ERR_CODE big_init(BIGNUM *number, int size);
1367c478bd9Sstevel@tonic-gate BIG_ERR_CODE big_extend(BIGNUM *number, int size);
1377c478bd9Sstevel@tonic-gate void big_finish(BIGNUM *number);
1387c478bd9Sstevel@tonic-gate void bytestring2bignum(BIGNUM *bn, uchar_t *kn, size_t len);
1397c478bd9Sstevel@tonic-gate void bignum2bytestring(uchar_t *kn, BIGNUM *bn, size_t len);
1407c478bd9Sstevel@tonic-gate BIG_ERR_CODE big_mont_rr(BIGNUM *result, BIGNUM *n);
1417c478bd9Sstevel@tonic-gate BIG_ERR_CODE big_modexp(BIGNUM *result, BIGNUM *a, BIGNUM *e,
1427c478bd9Sstevel@tonic-gate     BIGNUM *n, BIGNUM *n_rr);
143b60f2a0bSfr BIG_ERR_CODE big_modexp_ext(BIGNUM *result, BIGNUM *a, BIGNUM *e,
144b60f2a0bSfr     BIGNUM *n, BIGNUM *n_rr, big_modexp_ncp_info_t *info);
1457c478bd9Sstevel@tonic-gate BIG_ERR_CODE big_modexp_crt(BIGNUM *result, BIGNUM *a, BIGNUM *dmodpminus1,
1467c478bd9Sstevel@tonic-gate     BIGNUM *dmodqminus1, BIGNUM *p, BIGNUM *q, BIGNUM *pinvmodq,
1477c478bd9Sstevel@tonic-gate     BIGNUM *p_rr, BIGNUM *q_rr);
148b60f2a0bSfr BIG_ERR_CODE big_modexp_crt_ext(BIGNUM *result, BIGNUM *a, BIGNUM *dmodpminus1,
149b60f2a0bSfr     BIGNUM *dmodqminus1, BIGNUM *p, BIGNUM *q, BIGNUM *pinvmodq,
150b60f2a0bSfr     BIGNUM *p_rr, BIGNUM *q_rr, big_modexp_ncp_info_t *info);
1517c478bd9Sstevel@tonic-gate int big_cmp_abs(BIGNUM *a, BIGNUM *b);
152*726fad2aSDina K Nimeh BIG_ERR_CODE big_random(BIGNUM *r, size_t length, int (*rfunc)(void *, size_t));
1537c478bd9Sstevel@tonic-gate BIG_ERR_CODE big_div_pos(BIGNUM *result, BIGNUM *remainder,
1547c478bd9Sstevel@tonic-gate     BIGNUM *aa, BIGNUM *bb);
1557c478bd9Sstevel@tonic-gate BIG_ERR_CODE big_ext_gcd_pos(BIGNUM *gcd, BIGNUM *cm, BIGNUM *ce,
1567c478bd9Sstevel@tonic-gate     BIGNUM *m, BIGNUM *e);
1577c478bd9Sstevel@tonic-gate BIG_ERR_CODE big_add(BIGNUM *result, BIGNUM *aa, BIGNUM *bb);
158b60f2a0bSfr BIG_ERR_CODE big_add_abs(BIGNUM *result, BIGNUM *aa, BIGNUM *bb);
1597c478bd9Sstevel@tonic-gate BIG_ERR_CODE big_mul(BIGNUM *result, BIGNUM *aa, BIGNUM *bb);
160b60f2a0bSfr void big_shiftright(BIGNUM *result, BIGNUM *aa, int offs);
1617c478bd9Sstevel@tonic-gate BIG_ERR_CODE big_nextprime_pos(BIGNUM *result, BIGNUM *n);
162b60f2a0bSfr BIG_ERR_CODE big_nextprime_pos_ext(BIGNUM *result, BIGNUM *n,
163b60f2a0bSfr     big_modexp_ncp_info_t *info);
1647c478bd9Sstevel@tonic-gate BIG_ERR_CODE big_sub_pos(BIGNUM *result, BIGNUM *aa, BIGNUM *bb);
1657c478bd9Sstevel@tonic-gate BIG_ERR_CODE big_copy(BIGNUM *dest, BIGNUM *src);
1667c478bd9Sstevel@tonic-gate BIG_ERR_CODE big_sub(BIGNUM *result, BIGNUM *aa, BIGNUM *bb);
1677c478bd9Sstevel@tonic-gate int big_bitlength(BIGNUM *n);
168b60f2a0bSfr BIG_ERR_CODE big_init1(BIGNUM *number, int size,
169b60f2a0bSfr     BIG_CHUNK_TYPE *buf, int bufsize);
170b60f2a0bSfr BIG_ERR_CODE big_mont_mul(BIGNUM *ret,
171b60f2a0bSfr     BIGNUM *a, BIGNUM *b, BIGNUM *n, BIG_CHUNK_TYPE n0);
172b60f2a0bSfr int big_is_zero(BIGNUM *n);
173b60f2a0bSfr BIG_CHUNK_TYPE big_n0(BIG_CHUNK_TYPE n);
174b60f2a0bSfr 
1757c478bd9Sstevel@tonic-gate 
1767c478bd9Sstevel@tonic-gate #if defined(HWCAP)
1777c478bd9Sstevel@tonic-gate 
178b60f2a0bSfr #if (BIG_CHUNK_SIZE != 32)
179b60f2a0bSfr #error HWCAP works only with 32-bit bignum chunks
180b60f2a0bSfr #endif
181b60f2a0bSfr 
1827c478bd9Sstevel@tonic-gate #define	BIG_MUL_SET_VEC(r, a, len, digit) \
1837c478bd9Sstevel@tonic-gate 	(*big_mul_set_vec_impl)(r, a, len, digit)
1847c478bd9Sstevel@tonic-gate #define	BIG_MUL_ADD_VEC(r, a, len, digit) \
1857c478bd9Sstevel@tonic-gate 	(*big_mul_add_vec_impl)(r, a, len, digit)
1867c478bd9Sstevel@tonic-gate #define	BIG_MUL_VEC(r, a, alen, b, blen) \
1877c478bd9Sstevel@tonic-gate 	(*big_mul_vec_impl)(r, a, alen, b, blen)
1887c478bd9Sstevel@tonic-gate #define	BIG_SQR_VEC(r, a, len) \
1897c478bd9Sstevel@tonic-gate 	(*big_sqr_vec_impl)(r, a, len)
1907c478bd9Sstevel@tonic-gate 
191b60f2a0bSfr extern BIG_CHUNK_TYPE (*big_mul_set_vec_impl)
192b60f2a0bSfr 	(BIG_CHUNK_TYPE *r, BIG_CHUNK_TYPE *a, int len, BIG_CHUNK_TYPE digit);
193b60f2a0bSfr extern BIG_CHUNK_TYPE (*big_mul_add_vec_impl)
194b60f2a0bSfr 	(BIG_CHUNK_TYPE *r, BIG_CHUNK_TYPE *a, int len, BIG_CHUNK_TYPE digit);
1957c478bd9Sstevel@tonic-gate extern void (*big_mul_vec_impl)
196b60f2a0bSfr 	(BIG_CHUNK_TYPE *r, BIG_CHUNK_TYPE *a, int alen, BIG_CHUNK_TYPE *b,
197b60f2a0bSfr 	    int blen);
1987c478bd9Sstevel@tonic-gate extern void (*big_sqr_vec_impl)
199b60f2a0bSfr 	(BIG_CHUNK_TYPE *r, BIG_CHUNK_TYPE *a, int len);
2007c478bd9Sstevel@tonic-gate 
2017c478bd9Sstevel@tonic-gate #else /* ! HWCAP */
2027c478bd9Sstevel@tonic-gate 
2037c478bd9Sstevel@tonic-gate #define	BIG_MUL_SET_VEC(r, a, len, digit) big_mul_set_vec(r, a, len, digit)
2047c478bd9Sstevel@tonic-gate #define	BIG_MUL_ADD_VEC(r, a, len, digit) big_mul_add_vec(r, a, len, digit)
2057c478bd9Sstevel@tonic-gate #define	BIG_MUL_VEC(r, a, alen, b, blen) big_mul_vec(r, a, alen, b, blen)
2067c478bd9Sstevel@tonic-gate #define	BIG_SQR_VEC(r, a, len) big_sqr_vec(r, a, len)
2077c478bd9Sstevel@tonic-gate 
208b60f2a0bSfr extern BIG_CHUNK_TYPE big_mul_set_vec(BIG_CHUNK_TYPE *r, BIG_CHUNK_TYPE *a,
209b60f2a0bSfr     int len, BIG_CHUNK_TYPE d);
210b60f2a0bSfr extern BIG_CHUNK_TYPE big_mul_add_vec(BIG_CHUNK_TYPE *r,
211b60f2a0bSfr     BIG_CHUNK_TYPE *a, int len, BIG_CHUNK_TYPE d);
212b60f2a0bSfr extern void big_mul_vec(BIG_CHUNK_TYPE *r, BIG_CHUNK_TYPE *a, int alen,
213b60f2a0bSfr     BIG_CHUNK_TYPE *b, int blen);
214b60f2a0bSfr extern void big_sqr_vec(BIG_CHUNK_TYPE *r, BIG_CHUNK_TYPE *a, int len);
2157c478bd9Sstevel@tonic-gate 
2167c478bd9Sstevel@tonic-gate #endif /* HWCAP */
2177c478bd9Sstevel@tonic-gate 
2187c478bd9Sstevel@tonic-gate #ifdef	__cplusplus
2197c478bd9Sstevel@tonic-gate }
2207c478bd9Sstevel@tonic-gate #endif
2217c478bd9Sstevel@tonic-gate 
2227c478bd9Sstevel@tonic-gate #endif	/* _BIGNUM_H */
223