1 files changed, 286 insertions, 0 deletions
diff --git a/src/lib/libcrypto/bn/bn_div.c b/src/lib/libcrypto/bn/bn_div.c
new file mode 100644
index 0000000000..2263bdc7da
--- /dev/null
+++ b/src/lib/libcrypto/bn/bn_div.c
@@ -0,0 +1,286 @@
+/* crypto/bn/bn_div.c */
+/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
+ * All rights reserved.
+ *
+ * This package is an SSL implementation written
+ * by Eric Young (eay@cryptsoft.com).
+ * The implementation was written so as to conform with Netscapes SSL.
+ * 
+ * This library is free for commercial and non-commercial use as long as
+ * the following conditions are aheared to.  The following conditions
+ * apply to all code found in this distribution, be it the RC4, RSA,
+ * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
+ * included with this distribution is covered by the same copyright terms
+ * except that the holder is Tim Hudson (tjh@cryptsoft.com).
+ * 
+ * Copyright remains Eric Young's, and as such any Copyright notices in
+ * the code are not to be removed.
+ * If this package is used in a product, Eric Young should be given attribution
+ * as the author of the parts of the library used.
+ * This can be in the form of a textual message at program startup or
+ * in documentation (online or textual) provided with the package.
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *    "This product includes cryptographic software written by
+ *     Eric Young (eay@cryptsoft.com)"
+ *    The word 'cryptographic' can be left out if the rouines from the library
+ *    being used are not cryptographic related :-).
+ * 4. If you include any Windows specific code (or a derivative thereof) from 
+ *    the apps directory (application code) you must include an acknowledgement:
+ *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
+ * 
+ * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ * 
+ * The licence and distribution terms for any publically available version or
+ * derivative of this code cannot be changed.  i.e. this code cannot simply be
+ * copied and put under another distribution licence
+ * [including the GNU Public Licence.]
+ */
+#include <stdio.h>
+#include "cryptlib.h"
+#include "bn_lcl.h"
+/* The old slow way */
+#if 0
+int BN_div(dv, rem, m, d,ctx)
+BIGNUM *dv;
+BIGNUM *rem;
+BIGNUM *m;
+BIGNUM *d;
+BN_CTX *ctx;
+        {
+        int i,nm,nd;
+        BIGNUM *D;
+        if (BN_is_zero(d))
+                {
+                BNerr(BN_F_BN_DIV,BN_R_DIV_BY_ZERO);
+                return(0);
+                }
+        if (BN_ucmp(m,d) < 0)
+                {
+                if (rem != NULL)
+                        { if (BN_copy(rem,m) == NULL) return(0); }
+                if (dv != NULL) BN_zero(dv);
+                return(1);
+                }
+        D=ctx->bn[ctx->tos];
+        if (dv == NULL) dv=ctx->bn[ctx->tos+1];
+        if (rem == NULL) rem=ctx->bn[ctx->tos+2];
+        nd=BN_num_bits(d);
+        nm=BN_num_bits(m);
+        if (BN_copy(D,d) == NULL) return(0);
+        if (BN_copy(rem,m) == NULL) return(0);
+        /* The next 2 are needed so we can do a dv->d[0]|=1 later
+         * since BN_lshift1 will only work once there is a value :-) */
+        BN_zero(dv);
+        dv->top=1;
+        if (!BN_lshift(D,D,nm-nd)) return(0);
+        for (i=nm-nd; i>=0; i--)
+                {
+                if (!BN_lshift1(dv,dv)) return(0);
+                if (BN_ucmp(rem,D) >= 0)
+                        {
+                        dv->d[0]|=1;
+                        bn_qsub(rem,rem,D);
+                        }
+/* CAN IMPROVE (and have now :=) */
+                if (!BN_rshift1(D,D)) return(0);
+                }
+        rem->neg=BN_is_zero(rem)?0:m->neg;
+        dv->neg=m->neg^d->neg;
+        return(1);
+        }
+#else
+int BN_div(dv, rm, num, divisor,ctx)
+BIGNUM *dv;
+BIGNUM *rm;
+BIGNUM *num;
+BIGNUM *divisor;
+BN_CTX *ctx;
+        {
+        int norm_shift,i,j,loop;
+        BIGNUM *tmp,wnum,*snum,*sdiv,*res;
+        BN_ULONG *resp,*wnump;
+        BN_ULONG d0,d1;
+        int num_n,div_n;
+        if (BN_is_zero(divisor))
+                {
+                BNerr(BN_F_BN_DIV,BN_R_DIV_BY_ZERO);
+                return(0);
+                }
+        if (BN_ucmp(num,divisor) < 0)
+                {
+                if (rm != NULL)
+                        { if (BN_copy(rm,num) == NULL) return(0); }
+                if (dv != NULL) BN_zero(dv);
+                return(1);
+                }
+        tmp=ctx->bn[ctx->tos]; 
+        tmp->neg=0;
+        snum=ctx->bn[ctx->tos+1];
+        sdiv=ctx->bn[ctx->tos+2];
+        if (dv == NULL)
+                res=ctx->bn[ctx->tos+3];
+        else    res=dv;
+        /* First we normalise the numbers */
+        norm_shift=BN_BITS2-((BN_num_bits(divisor))%BN_BITS2);
+        BN_lshift(sdiv,divisor,norm_shift);
+        sdiv->neg=0;
+        norm_shift+=BN_BITS2;
+        BN_lshift(snum,num,norm_shift);
+        snum->neg=0;
+        div_n=sdiv->top;
+        num_n=snum->top;
+        loop=num_n-div_n;
+        /* Lets setup a 'window' into snum
+         * This is the part that corresponds to the current
+         * 'area' being divided */
+        wnum.d=  &(snum->d[loop]);
+        wnum.top= div_n;
+        wnum.max= snum->max; /* a bit of a lie */
+        wnum.neg= 0;
+        /* Get the top 2 words of sdiv */
+        /* i=sdiv->top; */
+        d0=sdiv->d[div_n-1];
+        d1=(div_n == 1)?0:sdiv->d[div_n-2];
+        /* pointer to the 'top' of snum */
+        wnump= &(snum->d[num_n-1]);
+        /* Setup to 'res' */
+        res->neg= (num->neg^divisor->neg);
+        res->top=loop;
+        if (!bn_wexpand(res,(loop+1))) goto err;
+        resp= &(res->d[loop-1]);
+        /* space for temp */
+        if (!bn_wexpand(tmp,(div_n+1))) goto err;
+        if (BN_ucmp(&wnum,sdiv) >= 0)
+                {
+                bn_qsub(&wnum,&wnum,sdiv);
+                *resp=1;
+                res->d[res->top-1]=1;
+                }
+        else
+                res->top--;
+        resp--;
+        for (i=0; i<loop-1; i++)
+                {
+                BN_ULONG q,n0,n1;
+                BN_ULONG l0;
+                wnum.d--; wnum.top++;
+                n0=wnump[0];
+                n1=wnump[-1];
+                if (n0 == d0)
+                        q=BN_MASK2;
+                else
+                        q=bn_div64(n0,n1,d0);
+                {
+#ifdef BN_LLONG
+                BN_ULLONG t1,t2,rem;
+                t1=((BN_ULLONG)n0<<BN_BITS2)|n1;
+                for (;;)
+                        {
+                        t2=(BN_ULLONG)d1*q;
+                        rem=t1-(BN_ULLONG)q*d0;
+                        if ((rem>>BN_BITS2) ||
+                                (t2 <= ((BN_ULLONG)(rem<<BN_BITS2)+wnump[-2])))
+                                break;
+                        q--;
+                        }
+#else
+                BN_ULONG t1l,t1h,t2l,t2h,t3l,t3h,ql,qh,t3t;
+                t1h=n0;
+                t1l=n1;
+                for (;;)
+                        {
+                        t2l=LBITS(d1); t2h=HBITS(d1);
+                        ql =LBITS(q);  qh =HBITS(q);
+                        mul64(t2l,t2h,ql,qh); /* t2=(BN_ULLONG)d1*q; */
+                        t3t=LBITS(d0); t3h=HBITS(d0);
+                        mul64(t3t,t3h,ql,qh); /* t3=t1-(BN_ULLONG)q*d0; */
+                        t3l=(t1l-t3t)&BN_MASK2;
+                        if (t3l > t1l) t3h++;
+                        t3h=(t1h-t3h)&BN_MASK2;
+                        /*if ((t3>>BN_BITS2) ||
+                                (t2 <= ((t3<<BN_BITS2)+wnump[-2])))
+                                break; */
+                        if (t3h) break;
+                        if (t2h < t3l) break;
+                        if ((t2h == t3l) && (t2l <= wnump[-2])) break;
+                        q--;
+                        }
+#endif
+                }
+                l0=bn_mul_words(tmp->d,sdiv->d,div_n,q);
+                tmp->d[div_n]=l0;
+                for (j=div_n+1; j>0; j--)
+                        if (tmp->d[j-1]) break;
+                tmp->top=j;
+                j=wnum.top;
+                BN_sub(&wnum,&wnum,tmp);
+                snum->top=snum->top+wnum.top-j;
+                if (wnum.neg)
+                        {
+                        q--;
+                        j=wnum.top;
+                        BN_add(&wnum,&wnum,sdiv);
+                        snum->top+=wnum.top-j;
+                        }
+                *(resp--)=q;
+                wnump--;
+                }
+        if (rm != NULL)
+                {
+                BN_rshift(rm,snum,norm_shift);
+                rm->neg=num->neg;
+                }
+        return(1);
+err:
+        return(0);
+        }
+#endif

diff --git a/src/lib/libcrypto/bn/bn_div.c b/src/lib/libcrypto/bn/bn_div.c new file mode 100644 index 0000000000..2263bdc7da --- /dev/null +++ b/src/lib/libcrypto/bn/bn_div.c
@@ -0,0 +1,286 @@
	1	/* crypto/bn/bn_div.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	/* The old slow way */
	64	#if 0
	65	int BN_div(dv, rem, m, d,ctx)
	66	BIGNUM *dv;
	67	BIGNUM *rem;
	68	BIGNUM *m;
	69	BIGNUM *d;
	70	BN_CTX *ctx;
	71	{
	72	int i,nm,nd;
	73	BIGNUM *D;
	74
	75	if (BN_is_zero(d))
	76	{
	77	BNerr(BN_F_BN_DIV,BN_R_DIV_BY_ZERO);
	78	return(0);
	79	}
	80
	81	if (BN_ucmp(m,d) < 0)
	82	{
	83	if (rem != NULL)
	84	{ if (BN_copy(rem,m) == NULL) return(0); }
	85	if (dv != NULL) BN_zero(dv);
	86	return(1);
	87	}
	88
	89	D=ctx->bn[ctx->tos];
	90	if (dv == NULL) dv=ctx->bn[ctx->tos+1];
	91	if (rem == NULL) rem=ctx->bn[ctx->tos+2];
	92
	93	nd=BN_num_bits(d);
	94	nm=BN_num_bits(m);
	95	if (BN_copy(D,d) == NULL) return(0);
	96	if (BN_copy(rem,m) == NULL) return(0);
	97
	98	/* The next 2 are needed so we can do a dv->d[0]\|=1 later
	99	* since BN_lshift1 will only work once there is a value :-) */
	100	BN_zero(dv);
	101	dv->top=1;
	102
	103	if (!BN_lshift(D,D,nm-nd)) return(0);
	104	for (i=nm-nd; i>=0; i--)
	105	{
	106	if (!BN_lshift1(dv,dv)) return(0);
	107	if (BN_ucmp(rem,D) >= 0)
	108	{
	109	dv->d[0]\|=1;
	110	bn_qsub(rem,rem,D);
	111	}
	112	/* CAN IMPROVE (and have now :=) */
	113	if (!BN_rshift1(D,D)) return(0);
	114	}
	115	rem->neg=BN_is_zero(rem)?0:m->neg;
	116	dv->neg=m->neg^d->neg;
	117	return(1);
	118	}
	119
	120	#else
	121
	122	int BN_div(dv, rm, num, divisor,ctx)
	123	BIGNUM *dv;
	124	BIGNUM *rm;
	125	BIGNUM *num;
	126	BIGNUM *divisor;
	127	BN_CTX *ctx;
	128	{
	129	int norm_shift,i,j,loop;
	130	BIGNUM tmp,wnum,snum,sdiv,res;
	131	BN_ULONG resp,wnump;
	132	BN_ULONG d0,d1;
	133	int num_n,div_n;
	134
	135	if (BN_is_zero(divisor))
	136	{
	137	BNerr(BN_F_BN_DIV,BN_R_DIV_BY_ZERO);
	138	return(0);
	139	}
	140
	141	if (BN_ucmp(num,divisor) < 0)
	142	{
	143	if (rm != NULL)
	144	{ if (BN_copy(rm,num) == NULL) return(0); }
	145	if (dv != NULL) BN_zero(dv);
	146	return(1);
	147	}
	148
	149	tmp=ctx->bn[ctx->tos];
	150	tmp->neg=0;
	151	snum=ctx->bn[ctx->tos+1];
	152	sdiv=ctx->bn[ctx->tos+2];
	153	if (dv == NULL)
	154	res=ctx->bn[ctx->tos+3];
	155	else res=dv;
	156
	157	/* First we normalise the numbers */
	158	norm_shift=BN_BITS2-((BN_num_bits(divisor))%BN_BITS2);
	159	BN_lshift(sdiv,divisor,norm_shift);
	160	sdiv->neg=0;
	161	norm_shift+=BN_BITS2;
	162	BN_lshift(snum,num,norm_shift);
	163	snum->neg=0;
	164	div_n=sdiv->top;
	165	num_n=snum->top;
	166	loop=num_n-div_n;
	167
	168	/* Lets setup a 'window' into snum
	169	* This is the part that corresponds to the current
	170	* 'area' being divided */
	171	wnum.d= &(snum->d[loop]);
	172	wnum.top= div_n;
	173	wnum.max= snum->max; /* a bit of a lie */
	174	wnum.neg= 0;
	175
	176	/* Get the top 2 words of sdiv */
	177	/* i=sdiv->top; */
	178	d0=sdiv->d[div_n-1];
	179	d1=(div_n == 1)?0:sdiv->d[div_n-2];
	180
	181	/* pointer to the 'top' of snum */
	182	wnump= &(snum->d[num_n-1]);
	183
	184	/* Setup to 'res' */
	185	res->neg= (num->neg^divisor->neg);
	186	res->top=loop;
	187	if (!bn_wexpand(res,(loop+1))) goto err;
	188	resp= &(res->d[loop-1]);
	189
	190	/* space for temp */
	191	if (!bn_wexpand(tmp,(div_n+1))) goto err;
	192
	193	if (BN_ucmp(&wnum,sdiv) >= 0)
	194	{
	195	bn_qsub(&wnum,&wnum,sdiv);
	196	*resp=1;
	197	res->d[res->top-1]=1;
	198	}
	199	else
	200	res->top--;
	201	resp--;
	202
	203	for (i=0; i<loop-1; i++)
	204	{
	205	BN_ULONG q,n0,n1;
	206	BN_ULONG l0;
	207
	208	wnum.d--; wnum.top++;
	209	n0=wnump[0];
	210	n1=wnump[-1];
	211	if (n0 == d0)
	212	q=BN_MASK2;
	213	else
	214	q=bn_div64(n0,n1,d0);
	215	{
	216	#ifdef BN_LLONG
	217	BN_ULLONG t1,t2,rem;
	218	t1=((BN_ULLONG)n0<<BN_BITS2)\|n1;
	219	for (;;)
	220	{
	221	t2=(BN_ULLONG)d1*q;
	222	rem=t1-(BN_ULLONG)q*d0;
	223	if ((rem>>BN_BITS2) \|\|
	224	(t2 <= ((BN_ULLONG)(rem<<BN_BITS2)+wnump[-2])))
	225	break;
	226	q--;
	227	}
	228	#else
	229	BN_ULONG t1l,t1h,t2l,t2h,t3l,t3h,ql,qh,t3t;
	230	t1h=n0;
	231	t1l=n1;
	232	for (;;)
	233	{
	234	t2l=LBITS(d1); t2h=HBITS(d1);
	235	ql =LBITS(q); qh =HBITS(q);
	236	mul64(t2l,t2h,ql,qh); /* t2=(BN_ULLONG)d1q; /
	237
	238	t3t=LBITS(d0); t3h=HBITS(d0);
	239	mul64(t3t,t3h,ql,qh); /* t3=t1-(BN_ULLONG)qd0; /
	240	t3l=(t1l-t3t)&BN_MASK2;
	241	if (t3l > t1l) t3h++;
	242	t3h=(t1h-t3h)&BN_MASK2;
	243
	244	/*if ((t3>>BN_BITS2) \|\|
	245	(t2 <= ((t3<<BN_BITS2)+wnump[-2])))
	246	break; */
	247	if (t3h) break;
	248	if (t2h < t3l) break;
	249	if ((t2h == t3l) && (t2l <= wnump[-2])) break;
	250
	251	q--;
	252	}
	253	#endif
	254	}
	255	l0=bn_mul_words(tmp->d,sdiv->d,div_n,q);
	256	tmp->d[div_n]=l0;
	257	for (j=div_n+1; j>0; j--)
	258	if (tmp->d[j-1]) break;
	259	tmp->top=j;
	260
	261	j=wnum.top;
	262	BN_sub(&wnum,&wnum,tmp);
	263
	264	snum->top=snum->top+wnum.top-j;
	265
	266	if (wnum.neg)
	267	{
	268	q--;
	269	j=wnum.top;
	270	BN_add(&wnum,&wnum,sdiv);
	271	snum->top+=wnum.top-j;
	272	}
	273	*(resp--)=q;
	274	wnump--;
	275	}
	276	if (rm != NULL)
	277	{
	278	BN_rshift(rm,snum,norm_shift);
	279	rm->neg=num->neg;
	280	}
	281	return(1);
	282	err:
	283	return(0);
	284	}
	285
	286	#endif