1 /* crypto/bn/bn_shift.c */

     2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)

     3  * All rights reserved.

     4  *

     5  * This package is an SSL implementation written

     6  * by Eric Young (eay@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@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@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@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 EXPORT_C int BN_lshift1(BIGNUM *r, const BIGNUM *a)

    64 	{

    65 	register BN_ULONG *ap,*rp,t,c;

    66 	int i;

    67 

    68 	bn_check_top(r);

    69 	bn_check_top(a);

    70 

    71 	if (r != a)

    72 		{

    73 		r->neg=a->neg;

    74 		if (bn_wexpand(r,a->top+1) == NULL) return(0);

    75 		r->top=a->top;

    76 		}

    77 	else

    78 		{

    79 		if (bn_wexpand(r,a->top+1) == NULL) return(0);

    80 		}

    81 	ap=a->d;

    82 	rp=r->d;

    83 	c=0;

    84 	for (i=0; i<a->top; i++)

    85 		{

    86 		t= *(ap++);

    87 		*(rp++)=((t<<1)|c)&BN_MASK2;

    88 		c=(t & BN_TBIT)?1:0;

    89 		}

    90 	if (c)

    91 		{

    92 		*rp=1;

    93 		r->top++;

    94 		}

    95 	bn_check_top(r);

    96 	return(1);

    97 	}

    98 

    99 EXPORT_C int BN_rshift1(BIGNUM *r, const BIGNUM *a)

   100 	{

   101 	BN_ULONG *ap,*rp,t,c;

   102 	int i;

   103 

   104 	bn_check_top(r);

   105 	bn_check_top(a);

   106 

   107 	if (BN_is_zero(a))

   108 		{

   109 		BN_zero(r);

   110 		return(1);

   111 		}

   112 	if (a != r)

   113 		{

   114 		if (bn_wexpand(r,a->top) == NULL) return(0);

   115 		r->top=a->top;

   116 		r->neg=a->neg;

   117 		}

   118 	ap=a->d;

   119 	rp=r->d;

   120 	c=0;

   121 	for (i=a->top-1; i>=0; i--)

   122 		{

   123 		t=ap[i];

   124 		rp[i]=((t>>1)&BN_MASK2)|c;

   125 		c=(t&1)?BN_TBIT:0;

   126 		}

   127 	bn_correct_top(r);

   128 	bn_check_top(r);

   129 	return(1);

   130 	}

   131 

   132 EXPORT_C int BN_lshift(BIGNUM *r, const BIGNUM *a, int n)

   133 	{

   134 	int i,nw,lb,rb;

   135 	BN_ULONG *t,*f;

   136 	BN_ULONG l;

   137 

   138 	bn_check_top(r);

   139 	bn_check_top(a);

   140 

   141 	r->neg=a->neg;

   142 	nw=n/BN_BITS2;

   143 	if (bn_wexpand(r,a->top+nw+1) == NULL) return(0);

   144 	lb=n%BN_BITS2;

   145 	rb=BN_BITS2-lb;

   146 	f=a->d;

   147 	t=r->d;

   148 	t[a->top+nw]=0;

   149 	if (lb == 0)

   150 		for (i=a->top-1; i>=0; i--)

   151 			t[nw+i]=f[i];

   152 	else

   153 		for (i=a->top-1; i>=0; i--)

   154 			{

   155 			l=f[i];

   156 			t[nw+i+1]|=(l>>rb)&BN_MASK2;

   157 			t[nw+i]=(l<<lb)&BN_MASK2;

   158 			}

   159 	memset(t,0,nw*sizeof(t[0]));

   160 /*	for (i=0; i<nw; i++)

   161 		t[i]=0;*/

   162 	r->top=a->top+nw+1;

   163 	bn_correct_top(r);

   164 	bn_check_top(r);

   165 	return(1);

   166 	}

   167 

   168 EXPORT_C int BN_rshift(BIGNUM *r, const BIGNUM *a, int n)

   169 	{

   170 	int i,j,nw,lb,rb;

   171 	BN_ULONG *t,*f;

   172 	BN_ULONG l,tmp;

   173 

   174 	bn_check_top(r);

   175 	bn_check_top(a);

   176 

   177 	nw=n/BN_BITS2;

   178 	rb=n%BN_BITS2;

   179 	lb=BN_BITS2-rb;

   180 	if (nw > a->top || a->top == 0)

   181 		{

   182 		BN_zero(r);

   183 		return(1);

   184 		}

   185 	if (r != a)

   186 		{

   187 		r->neg=a->neg;

   188 		if (bn_wexpand(r,a->top-nw+1) == NULL) return(0);

   189 		}

   190 	else

   191 		{

   192 		if (n == 0)

   193 			return 1; /* or the copying loop will go berserk */

   194 		}

   195 

   196 	f= &(a->d[nw]);

   197 	t=r->d;

   198 	j=a->top-nw;

   199 	r->top=j;

   200 

   201 	if (rb == 0)

   202 		{

   203 		for (i=j; i != 0; i--)

   204 			*(t++)= *(f++);

   205 		}

   206 	else

   207 		{

   208 		l= *(f++);

   209 		for (i=j-1; i != 0; i--)

   210 			{

   211 			tmp =(l>>rb)&BN_MASK2;

   212 			l= *(f++);

   213 			*(t++) =(tmp|(l<<lb))&BN_MASK2;

   214 			}

   215 		*(t++) =(l>>rb)&BN_MASK2;

   216 		}

   217 	bn_correct_top(r);

   218 	bn_check_top(r);

   219 	return(1);

   220 	}