usr/src/common/bignum/bignum.h

   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 */