OpenCoverage

bn_kron.c

Absolute File Name:/home/opencoverage/opencoverage/guest-scripts/libressl/src/crypto/bn/bn_kron.c
Source codeSwitch to Preprocessed file
LineSourceCount
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. */-
62int-
63BN_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 BN_CTX_start(ctx);-
82 if ((A = BN_CTX_get(ctx)) == NULL)
(A = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 140 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-140
83 goto end;
never executed: goto end;
0
84 if ((B = BN_CTX_get(ctx)) == NULL)
(B = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 140 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-140
85 goto end;
never executed: goto end;
0
86-
87 err = !BN_copy(A, a);-
88 if (err)
errDescription
TRUEnever evaluated
FALSEevaluated 140 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-140
89 goto end;
never executed: goto end;
0
90 err = !BN_copy(B, b);-
91 if (err)
errDescription
TRUEnever evaluated
FALSEevaluated 140 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-140
92 goto end;
never executed: goto end;
0
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 if (BN_is_zero(B)) {
((B)->top == 0)Description
TRUEnever evaluated
FALSEevaluated 140 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-140
103 ret = BN_abs_is_word(A, 1);
((A)->top == 1)Description
TRUEnever evaluated
FALSEnever evaluated
((A)->d[0] == ...gned long)(1))Description
TRUEnever evaluated
FALSEnever evaluated
((1) == 0)Description
TRUEnever evaluated
FALSEnever evaluated
((A)->top == 0)Description
TRUEnever evaluated
FALSEnever evaluated
0
104 goto end;
never executed: goto end;
0
105 }-
106-
107 /* Cohen's step 2: */-
108-
109 if (!BN_is_odd(A) && !BN_is_odd(B)) {
((A)->top > 0)Description
TRUEevaluated 140 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEnever evaluated
((A)->d[0] & 1)Description
TRUEevaluated 69 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEevaluated 71 times by 2 tests
Evaluated by:
  • bntest
  • ectest
((B)->top > 0)Description
TRUEevaluated 71 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEnever evaluated
((B)->d[0] & 1)Description
TRUEevaluated 71 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEnever evaluated
0-140
110 ret = 0;-
111 goto end;
never executed: goto end;
0
112 }-
113-
114 /* now B is non-zero */-
115 i = 0;-
116 while (!BN_is_bit_set(B, i))
!BN_is_bit_set(B, i)Description
TRUEnever evaluated
FALSEevaluated 140 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-140
117 i++;
never executed: i++;
0
118 err = !BN_rshift(B, B, i);-
119 if (err)
errDescription
TRUEnever evaluated
FALSEevaluated 140 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-140
120 goto end;
never executed: goto end;
0
121 if (i & 1) {
i & 1Description
TRUEnever evaluated
FALSEevaluated 140 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-140
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 {
never executed: end of block
0
128 /* i is even */-
129 ret = 1;-
130 }
executed 140 times by 2 tests: end of block
Executed by:
  • bntest
  • ectest
140
131-
132 if (B->neg) {
B->negDescription
TRUEevaluated 100 times by 1 test
Evaluated by:
  • bntest
FALSEevaluated 40 times by 2 tests
Evaluated by:
  • bntest
  • ectest
40-100
133 B->neg = 0;-
134 if (A->neg)
A->negDescription
TRUEevaluated 50 times by 1 test
Evaluated by:
  • bntest
FALSEevaluated 50 times by 1 test
Evaluated by:
  • bntest
50
135 ret = -ret;
executed 50 times by 1 test: ret = -ret;
Executed by:
  • bntest
50
136 }
executed 100 times by 1 test: end of block
Executed by:
  • bntest
100
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 while (1) {-
142 /* Cohen's step 3: */-
143-
144 /* B is positive and odd */-
145-
146 if (BN_is_zero(A)) {
((A)->top == 0)Description
TRUEevaluated 140 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEevaluated 18638 times by 2 tests
Evaluated by:
  • bntest
  • ectest
140-18638
147 ret = BN_is_one(B) ? ret : 0;
(((B))->top == 1)Description
TRUEevaluated 140 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEnever evaluated
(((B))->d[0] =...gned long)(1))Description
TRUEevaluated 140 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEnever evaluated
((1) == 0)Description
TRUEnever evaluated
FALSEnever evaluated
(((B))->top == 0)Description
TRUEnever evaluated
FALSEnever evaluated
!(B)->negDescription
TRUEevaluated 140 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEnever evaluated
0-140
148 goto end;
executed 140 times by 2 tests: goto end;
Executed by:
  • bntest
  • ectest
140
149 }-
150-
151 /* now A is non-zero */-
152 i = 0;-
153 while (!BN_is_bit_set(A, i))
!BN_is_bit_set(A, i)Description
TRUEevaluated 21111 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEevaluated 18638 times by 2 tests
Evaluated by:
  • bntest
  • ectest
18638-21111
154 i++;
executed 21111 times by 2 tests: i++;
Executed by:
  • bntest
  • ectest
21111
155 err = !BN_rshift(A, A, i);-
156 if (err)
errDescription
TRUEnever evaluated
FALSEevaluated 18638 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-18638
157 goto end;
never executed: goto end;
0
158 if (i & 1) {
i & 1Description
TRUEevaluated 6769 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEevaluated 11869 times by 2 tests
Evaluated by:
  • bntest
  • ectest
6769-11869
159 /* i is odd */-
160 /* multiply 'ret' by $(-1)^{(B^2-1)/8}$ */-
161 ret = ret * tab[BN_lsw(B) & 7];-
162 }
executed 6769 times by 2 tests: end of block
Executed by:
  • bntest
  • ectest
6769
163-
164 /* Cohen's step 4: */-
165 /* multiply 'ret' by $(-1)^{(A-1)(B-1)/4}$ */-
166 if ((A->neg ? ~BN_lsw(A) : BN_lsw(A)) & BN_lsw(B) & 2)
(A->neg ? ~(((...(B)->d[0]) & 2Description
TRUEevaluated 4646 times by 1 test
Evaluated by:
  • bntest
FALSEevaluated 13992 times by 2 tests
Evaluated by:
  • bntest
  • ectest
A->negDescription
TRUEevaluated 50 times by 1 test
Evaluated by:
  • bntest
FALSEevaluated 18588 times by 2 tests
Evaluated by:
  • bntest
  • ectest
((A)->top == 0)Description
TRUEnever evaluated
FALSEevaluated 18588 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-18588
167 ret = -ret;
executed 4646 times by 1 test: ret = -ret;
Executed by:
  • bntest
4646
168-
169 /* (A, B) := (B mod |A|, |A|) */-
170 err = !BN_nnmod(B, B, A, ctx);-
171 if (err)
errDescription
TRUEnever evaluated
FALSEevaluated 18638 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-18638
172 goto end;
never executed: goto end;
0
173 tmp = A;-
174 A = B;-
175 B = tmp;-
176 tmp->neg = 0;-
177 }
executed 18638 times by 2 tests: end of block
Executed by:
  • bntest
  • ectest
18638
178-
179end:
code before this statement never executed: end:
0
180 BN_CTX_end(ctx);-
181 if (err)
errDescription
TRUEnever evaluated
FALSEevaluated 140 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-140
182 return -2;
never executed: return -2;
0
183 else-
184 return ret;
executed 140 times by 2 tests: return ret;
Executed by:
  • bntest
  • ectest
140
185}-
Source codeSwitch to Preprocessed file
Generated by Squish Coco 4.2.2