Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	lib/libcrypto/bn/bn_kron.c	Lines:	37	44	84.1 %
Date:	2017-11-07	Branches:	36	62	58.1 %


/* $OpenBSD: bn_kron.c,v 1.6 2015/02/09 15:49:22 jsing Exp $ */
/* ====================================================================
 * Copyright (c) 1998-2000 The OpenSSL Project.  All rights reserved.
 *
 * 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 above 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 acknowledgment:
 *    "This product includes software developed by the OpenSSL Project
 *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
 *
 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
 *    endorse or promote products derived from this software without
 *    prior written permission. For written permission, please contact
 *    openssl-core@openssl.org.
 *
 * 5. Products derived from this software may not be called "OpenSSL"
 *    nor may "OpenSSL" appear in their names without prior written
 *    permission of the OpenSSL Project.
 *
 * 6. Redistributions of any form whatsoever must retain the following
 *    acknowledgment:
 *    "This product includes software developed by the OpenSSL Project
 *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
 *
 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
 * EXPRESSED 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 OpenSSL PROJECT OR
 * ITS 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.
 * ====================================================================
 *
 * This product includes cryptographic software written by Eric Young
 * (eay@cryptsoft.com).  This product includes software written by Tim
 * Hudson (tjh@cryptsoft.com).
 *
 */

#include "bn_lcl.h"

/* least significant word */
#define BN_lsw(n) (((n)->top == 0) ? (BN_ULONG) 0 : (n)->d[0])

/* Returns -2 for errors because both -1 and 0 are valid results. */
int
BN_kronecker(const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
{
	int i;
	int ret = -2; /* avoid 'uninitialized' warning */
	int err = 0;
	BIGNUM *A, *B, *tmp;

	/* In 'tab', only odd-indexed entries are relevant:
	 * For any odd BIGNUM n,
	 *     tab[BN_lsw(n) & 7]
	 * is $(-1)^{(n^2-1)/8}$ (using TeX notation).
	 * Note that the sign of n does not matter.
	 */
	static const int tab[8] = {0, 1, 0, -1, 0, -1, 0, 1};

	bn_check_top(a);
	bn_check_top(b);

	BN_CTX_start(ctx);
	if ((A = BN_CTX_get(ctx)) == NULL)
		goto end;
	if ((B = BN_CTX_get(ctx)) == NULL)
		goto end;

	err = !BN_copy(A, a);
	if (err)
		goto end;
	err = !BN_copy(B, b);
	if (err)
		goto end;

	/*
	 * Kronecker symbol, imlemented according to Henri Cohen,
	 * "A Course in Computational Algebraic Number Theory"
	 * (algorithm 1.4.10).
	 */

	/* Cohen's step 1: */

	if (BN_is_zero(B)) {
		ret = BN_abs_is_word(A, 1);
		goto end;
	}

	/* Cohen's step 2: */

	if (!BN_is_odd(A) && !BN_is_odd(B)) {
		ret = 0;
		goto end;
	}

	/* now  B  is non-zero */
	i = 0;
	while (!BN_is_bit_set(B, i))
		i++;
	err = !BN_rshift(B, B, i);
	if (err)
		goto end;
	if (i & 1) {
		/* i is odd */
		/* (thus  B  was even, thus  A  must be odd!)  */

		/* set 'ret' to $(-1)^{(A^2-1)/8}$ */
		ret = tab[BN_lsw(A) & 7];
	} else {
		/* i is even */
		ret = 1;
	}

	if (B->neg) {
		B->neg = 0;
		if (A->neg)
			ret = -ret;
	}

	/* now  B  is positive and odd, so what remains to be done is
	 * to compute the Jacobi symbol  (A/B)  and multiply it by 'ret' */

	while (1) {
		/* Cohen's step 3: */

		/*  B  is positive and odd */

		if (BN_is_zero(A)) {
			ret = BN_is_one(B) ? ret : 0;
			goto end;
		}

		/* now  A  is non-zero */
		i = 0;
		while (!BN_is_bit_set(A, i))
			i++;
		err = !BN_rshift(A, A, i);
		if (err)
			goto end;
		if (i & 1) {
			/* i is odd */
			/* multiply 'ret' by  $(-1)^{(B^2-1)/8}$ */
			ret = ret * tab[BN_lsw(B) & 7];
		}

		/* Cohen's step 4: */
		/* multiply 'ret' by  $(-1)^{(A-1)(B-1)/4}$ */
		if ((A->neg ? ~BN_lsw(A) : BN_lsw(A)) & BN_lsw(B) & 2)
			ret = -ret;

		/* (A, B) := (B mod |A|, |A|) */
		err = !BN_nnmod(B, B, A, ctx);
		if (err)
			goto end;
		tmp = A;
		A = B;
		B = tmp;
		tmp->neg = 0;
	}

end:
	BN_CTX_end(ctx);
	if (err)
		return -2;
	else
		return ret;
}


Generated by: GCOVR (Version 3.3)

Line	Branch	Exec	Source
1			/* $OpenBSD: bn_kron.c,v 1.6 2015/02/09 15:49:22 jsing Exp $ */
2			/* ====================================================================
3			* Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved.
4			*
5			* Redistribution and use in source and binary forms, with or without
6			* modification, are permitted provided that the following conditions
7			* are met:
8			*
9			* 1. Redistributions of source code must retain the above copyright
10			* notice, this list of conditions and the following disclaimer.
11			*
12			* 2. Redistributions in binary form must reproduce the above copyright
13			* notice, this list of conditions and the following disclaimer in
14			* the documentation and/or other materials provided with the
15			* distribution.
16			*
17			* 3. All advertising materials mentioning features or use of this
18			* software must display the following acknowledgment:
19			* "This product includes software developed by the OpenSSL Project
20			* for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
21			*
22			* 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
23			* endorse or promote products derived from this software without
24			* prior written permission. For written permission, please contact
25			* openssl-core@openssl.org.
26			*
27			* 5. Products derived from this software may not be called "OpenSSL"
28			* nor may "OpenSSL" appear in their names without prior written
29			* permission of the OpenSSL Project.
30			*
31			* 6. Redistributions of any form whatsoever must retain the following
32			* acknowledgment:
33			* "This product includes software developed by the OpenSSL Project
34			* for use in the OpenSSL Toolkit (http://www.openssl.org/)"
35			*
36			* THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
37			* EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
38			* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
39			* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
40			* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
41			* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
42			* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
43			* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
44			* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
45			* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
46			* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
47			* OF THE POSSIBILITY OF SUCH DAMAGE.
48			* ====================================================================
49			*
50			* This product includes cryptographic software written by Eric Young
51			* (eay@cryptsoft.com). This product includes software written by Tim
52			* Hudson (tjh@cryptsoft.com).
53			*
54			*/
55
56			#include "bn_lcl.h"
57
58			/* least significant word */
59			#define BN_lsw(n) (((n)->top == 0) ? (BN_ULONG) 0 : (n)->d[0])
60
61			/* Returns -2 for errors because both -1 and 0 are valid results. */
62			int
63			BN_kronecker(const BIGNUM a, const BIGNUM b, BN_CTX *ctx)
64			{
65			int i;
66			int ret = -2; /* avoid 'uninitialized' warning */
67			int err = 0;
68			BIGNUM A, B, *tmp;
69
70			/* In 'tab', only odd-indexed entries are relevant:
71			* For any odd BIGNUM n,
72			* tab[BN_lsw(n) & 7]
73			* is $(-1)^{(n^2-1)/8}$ (using TeX notation).
74			* Note that the sign of n does not matter.
75			*/
76			static const int tab[8] = {0, 1, 0, -1, 0, -1, 0, 1};
77
78			bn_check_top(a);
79			bn_check_top(b);
80
81		1784	BN_CTX_start(ctx);
82	✓✗	892	if ((A = BN_CTX_get(ctx)) == NULL)
83			goto end;
84	✓✗	892	if ((B = BN_CTX_get(ctx)) == NULL)
85			goto end;
86
87		892	err = !BN_copy(A, a);
88	✓✗	892	if (err)
89			goto end;
90		892	err = !BN_copy(B, b);
91	✓✗	892	if (err)
92			goto end;
93
94			/*
95			* Kronecker symbol, imlemented according to Henri Cohen,
96			* "A Course in Computational Algebraic Number Theory"
97			* (algorithm 1.4.10).
98			*/
99
100			/* Cohen's step 1: */
101
102	✗✓	892	if (BN_is_zero(B)) {
103			ret = BN_abs_is_word(A, 1);
104			goto end;
105			}
106
107			/* Cohen's step 2: */
108
109	✓✗✓✓ ✓✗✗✓	2682	if (!BN_is_odd(A) && !BN_is_odd(B)) {
110			ret = 0;
111			goto end;
112			}
113
114			/* now B is non-zero */
115			i = 0;
116	✗✓	1784	while (!BN_is_bit_set(B, i))
117			i++;
118		892	err = !BN_rshift(B, B, i);
119	✓✗	892	if (err)
120			goto end;
121	✗✓	892	if (i & 1) {
122			/* i is odd */
123			/* (thus B was even, thus A must be odd!) */
124
125			/* set 'ret' to $(-1)^{(A^2-1)/8}$ */
126			ret = tab[BN_lsw(A) & 7];
127			} else {
128			/* i is even */
129			ret = 1;
130			}
131
132	✓✓	892	if (B->neg) {
133		600	B->neg = 0;
134	✓✓	600	if (A->neg)
135		300	ret = -ret;
136			}
137
138			/* now B is positive and odd, so what remains to be done is
139			* to compute the Jacobi symbol (A/B) and multiply it by 'ret' */
140
141		111614	while (1) {
142			/* Cohen's step 3: */
143
144			/* B is positive and odd */
145
146	✓✓	112506	if (BN_is_zero(A)) {
147	✓✗✓✗	3568	ret = BN_is_one(B) ? ret : 0;
148		892	goto end;
149			}
150
151			/* now A is non-zero */
152			i = 0;
153	✓✓	474942	while (!BN_is_bit_set(A, i))
154		125857	i++;
155		111614	err = !BN_rshift(A, A, i);
156	✓✗	111614	if (err)
157			goto end;
158	✓✓	111614	if (i & 1) {
159			/* i is odd */
160			/* multiply 'ret' by $(-1)^{(B^2-1)/8}$ */
161	✓✗	121713	ret = ret * tab[BN_lsw(B) & 7];
162		40571	}
163
164			/* Cohen's step 4: */
165			/* multiply 'ret' by $(-1)^{(A-1)(B-1)/4}$ */
166	✓✓✓✗ ✓✗✓✗ ✓✓	669984	if ((A->neg ? ~BN_lsw(A) : BN_lsw(A)) & BN_lsw(B) & 2)
167		27652	ret = -ret;
168
169			/* (A, B) := (B mod \|A\|, \|A\|) */
170		111614	err = !BN_nnmod(B, B, A, ctx);
171	✓✗	111614	if (err)
172			goto end;
173			tmp = A;
174			A = B;
175			B = tmp;
176		111614	tmp->neg = 0;
177			}
178
179			end:
180		892	BN_CTX_end(ctx);
181	✗✓	892	if (err)
182			return -2;
183			else
184		892	return ret;
185		892	}