Home | History | Annotate | Download | only in bn 
      1 /* crypto/bn/bn_word.c */
      2 /* Copyright (C) 1995-1998 Eric Young (eay (at) cryptsoft.com)
      3  * All rights reserved.
      4  *
      5  * This package is an SSL implementation written
      6  * by Eric Young (eay (at) cryptsoft.com).
      7  * The implementation was written so as to conform with Netscapes SSL.
      8  *
      9  * This library is free for commercial and non-commercial use as long as
     10  * the following conditions are aheared to.  The following conditions
     11  * apply to all code found in this distribution, be it the RC4, RSA,
     12  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
     13  * included with this distribution is covered by the same copyright terms
     14  * except that the holder is Tim Hudson (tjh (at) cryptsoft.com).
     15  *
     16  * Copyright remains Eric Young's, and as such any Copyright notices in
     17  * the code are not to be removed.
     18  * If this package is used in a product, Eric Young should be given attribution
     19  * as the author of the parts of the library used.
     20  * This can be in the form of a textual message at program startup or
     21  * in documentation (online or textual) provided with the package.
     22  *
     23  * Redistribution and use in source and binary forms, with or without
     24  * modification, are permitted provided that the following conditions
     25  * are met:
     26  * 1. Redistributions of source code must retain the copyright
     27  *    notice, this list of conditions and the following disclaimer.
     28  * 2. Redistributions in binary form must reproduce the above copyright
     29  *    notice, this list of conditions and the following disclaimer in the
     30  *    documentation and/or other materials provided with the distribution.
     31  * 3. All advertising materials mentioning features or use of this software
     32  *    must display the following acknowledgement:
     33  *    "This product includes cryptographic software written by
     34  *     Eric Young (eay (at) cryptsoft.com)"
     35  *    The word 'cryptographic' can be left out if the rouines from the library
     36  *    being used are not cryptographic related :-).
     37  * 4. If you include any Windows specific code (or a derivative thereof) from
     38  *    the apps directory (application code) you must include an acknowledgement:
     39  *    "This product includes software written by Tim Hudson (tjh (at) cryptsoft.com)"
     40  *
     41  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
     42  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     43  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     44  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
     45  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     46  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     47  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     48  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     49  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     50  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     51  * SUCH DAMAGE.
     52  *
     53  * The licence and distribution terms for any publically available version or
     54  * derivative of this code cannot be changed.  i.e. this code cannot simply be
     55  * copied and put under another distribution licence
     56  * [including the GNU Public Licence.]
     57  */
     58 
     59 #include <stdio.h>
     60 #include "cryptlib.h"
     61 #include "bn_lcl.h"
     62 
     63 BN_ULONG BN_mod_word(const BIGNUM *a, BN_ULONG w)
     64 	{
     65 #ifndef BN_LLONG
     66 	BN_ULONG ret=0;
     67 #else
     68 	BN_ULLONG ret=0;
     69 #endif
     70 	int i;
     71 
     72 	if (w == 0)
     73 		return (BN_ULONG)-1;
     74 
     75 	bn_check_top(a);
     76 	w&=BN_MASK2;
     77 	for (i=a->top-1; i>=0; i--)
     78 		{
     79 #ifndef BN_LLONG
     80 		ret=((ret<<BN_BITS4)|((a->d[i]>>BN_BITS4)&BN_MASK2l))%w;
     81 		ret=((ret<<BN_BITS4)|(a->d[i]&BN_MASK2l))%w;
     82 #else
     83 		ret=(BN_ULLONG)(((ret<<(BN_ULLONG)BN_BITS2)|a->d[i])%
     84 			(BN_ULLONG)w);
     85 #endif
     86 		}
     87 	return((BN_ULONG)ret);
     88 	}
     89 
     90 BN_ULONG BN_div_word(BIGNUM *a, BN_ULONG w)
     91 	{
     92 	BN_ULONG ret = 0;
     93 	int i, j;
     94 
     95 	bn_check_top(a);
     96 	w &= BN_MASK2;
     97 
     98 	if (!w)
     99 		/* actually this an error (division by zero) */
    100 		return (BN_ULONG)-1;
    101 	if (a->top == 0)
    102 		return 0;
    103 
    104 	/* normalize input (so bn_div_words doesn't complain) */
    105 	j = BN_BITS2 - BN_num_bits_word(w);
    106 	w <<= j;
    107 	if (!BN_lshift(a, a, j))
    108 		return (BN_ULONG)-1;
    109 
    110 	for (i=a->top-1; i>=0; i--)
    111 		{
    112 		BN_ULONG l,d;
    113 
    114 		l=a->d[i];
    115 		d=bn_div_words(ret,l,w);
    116 		ret=(l-((d*w)&BN_MASK2))&BN_MASK2;
    117 		a->d[i]=d;
    118 		}
    119 	if ((a->top > 0) && (a->d[a->top-1] == 0))
    120 		a->top--;
    121 	ret >>= j;
    122 	bn_check_top(a);
    123 	return(ret);
    124 	}
    125 
    126 int BN_add_word(BIGNUM *a, BN_ULONG w)
    127 	{
    128 	BN_ULONG l;
    129 	int i;
    130 
    131 	bn_check_top(a);
    132 	w &= BN_MASK2;
    133 
    134 	/* degenerate case: w is zero */
    135 	if (!w) return 1;
    136 	/* degenerate case: a is zero */
    137 	if(BN_is_zero(a)) return BN_set_word(a, w);
    138 	/* handle 'a' when negative */
    139 	if (a->neg)
    140 		{
    141 		a->neg=0;
    142 		i=BN_sub_word(a,w);
    143 		if (!BN_is_zero(a))
    144 			a->neg=!(a->neg);
    145 		return(i);
    146 		}
    147 	for (i=0;w!=0 && i<a->top;i++)
    148 		{
    149 		a->d[i] = l = (a->d[i]+w)&BN_MASK2;
    150 		w = (w>l)?1:0;
    151 		}
    152 	if (w && i==a->top)
    153 		{
    154 		if (bn_wexpand(a,a->top+1) == NULL) return 0;
    155 		a->top++;
    156 		a->d[i]=w;
    157 		}
    158 	bn_check_top(a);
    159 	return(1);
    160 	}
    161 
    162 int BN_sub_word(BIGNUM *a, BN_ULONG w)
    163 	{
    164 	int i;
    165 
    166 	bn_check_top(a);
    167 	w &= BN_MASK2;
    168 
    169 	/* degenerate case: w is zero */
    170 	if (!w) return 1;
    171 	/* degenerate case: a is zero */
    172 	if(BN_is_zero(a))
    173 		{
    174 		i = BN_set_word(a,w);
    175 		if (i != 0)
    176 			BN_set_negative(a, 1);
    177 		return i;
    178 		}
    179 	/* handle 'a' when negative */
    180 	if (a->neg)
    181 		{
    182 		a->neg=0;
    183 		i=BN_add_word(a,w);
    184 		a->neg=1;
    185 		return(i);
    186 		}
    187 
    188 	if ((a->top == 1) && (a->d[0] < w))
    189 		{
    190 		a->d[0]=w-a->d[0];
    191 		a->neg=1;
    192 		return(1);
    193 		}
    194 	i=0;
    195 	for (;;)
    196 		{
    197 		if (a->d[i] >= w)
    198 			{
    199 			a->d[i]-=w;
    200 			break;
    201 			}
    202 		else
    203 			{
    204 			a->d[i]=(a->d[i]-w)&BN_MASK2;
    205 			i++;
    206 			w=1;
    207 			}
    208 		}
    209 	if ((a->d[i] == 0) && (i == (a->top-1)))
    210 		a->top--;
    211 	bn_check_top(a);
    212 	return(1);
    213 	}
    214 
    215 int BN_mul_word(BIGNUM *a, BN_ULONG w)
    216 	{
    217 	BN_ULONG ll;
    218 
    219 	bn_check_top(a);
    220 	w&=BN_MASK2;
    221 	if (a->top)
    222 		{
    223 		if (w == 0)
    224 			BN_zero(a);
    225 		else
    226 			{
    227 			ll=bn_mul_words(a->d,a->d,a->top,w);
    228 			if (ll)
    229 				{
    230 				if (bn_wexpand(a,a->top+1) == NULL) return(0);
    231 				a->d[a->top++]=ll;
    232 				}
    233 			}
    234 		}
    235 	bn_check_top(a);
    236 	return(1);
    237 	}
    238 
    239