OpenCoverage

bn_recp.c

Absolute File Name:/home/opencoverage/opencoverage/guest-scripts/libressl/src/crypto/bn/bn_recp.c
Source codeSwitch to Preprocessed file
LineSourceCount
1/* $OpenBSD: bn_recp.c,v 1.15 2017/01/29 17:49:22 beck Exp $ */-
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-
61#include <openssl/err.h>-
62-
63#include "bn_lcl.h"-
64-
65void-
66BN_RECP_CTX_init(BN_RECP_CTX *recp)-
67{-
68 BN_init(&(recp->N));-
69 BN_init(&(recp->Nr));-
70 recp->num_bits = 0;-
71 recp->flags = 0;-
72}
executed 304 times by 2 tests: end of block
Executed by:
  • bntest
  • exptest
304
73-
74BN_RECP_CTX *-
75BN_RECP_CTX_new(void)-
76{-
77 BN_RECP_CTX *ret;-
78-
79 if ((ret = malloc(sizeof(BN_RECP_CTX))) == NULL)
(ret = malloc(...== ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
80 return (NULL);
never executed: return ( ((void *)0) );
0
81-
82 BN_RECP_CTX_init(ret);-
83 ret->flags = BN_FLG_MALLOCED;-
84 return (ret);
never executed: return (ret);
0
85}-
86-
87void-
88BN_RECP_CTX_free(BN_RECP_CTX *recp)-
89{-
90 if (recp == NULL)
recp == ((void *)0)Description
TRUEevaluated 1 time by 1 test
Evaluated by:
  • freenull
FALSEevaluated 304 times by 2 tests
Evaluated by:
  • bntest
  • exptest
1-304
91 return;
executed 1 time by 1 test: return;
Executed by:
  • freenull
1
92-
93 BN_free(&(recp->N));-
94 BN_free(&(recp->Nr));-
95 if (recp->flags & BN_FLG_MALLOCED)
recp->flags & 0x01Description
TRUEnever evaluated
FALSEevaluated 304 times by 2 tests
Evaluated by:
  • bntest
  • exptest
0-304
96 free(recp);
never executed: free(recp);
0
97}
executed 304 times by 2 tests: end of block
Executed by:
  • bntest
  • exptest
304
98-
99int-
100BN_RECP_CTX_set(BN_RECP_CTX *recp, const BIGNUM *d, BN_CTX *ctx)-
101{-
102 if (!BN_copy(&(recp->N), d))
!BN_copy(&(recp->N), d)Description
TRUEnever evaluated
FALSEevaluated 453 times by 2 tests
Evaluated by:
  • bntest
  • exptest
0-453
103 return 0;
never executed: return 0;
0
104 BN_zero(&(recp->Nr));-
105 recp->num_bits = BN_num_bits(d);-
106 recp->shift = 0;-
107 return (1);
executed 453 times by 2 tests: return (1);
Executed by:
  • bntest
  • exptest
453
108}-
109-
110int-
111BN_mod_mul_reciprocal(BIGNUM *r, const BIGNUM *x, const BIGNUM *y,-
112 BN_RECP_CTX *recp, BN_CTX *ctx)-
113{-
114 int ret = 0;-
115 BIGNUM *a;-
116 const BIGNUM *ca;-
117-
118 BN_CTX_start(ctx);-
119 if ((a = BN_CTX_get(ctx)) == NULL)
(a = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 138216 times by 2 tests
Evaluated by:
  • bntest
  • exptest
0-138216
120 goto err;
never executed: goto err;
0
121 if (y != NULL) {
y != ((void *)0)Description
TRUEevaluated 138216 times by 2 tests
Evaluated by:
  • bntest
  • exptest
FALSEnever evaluated
0-138216
122 if (x == y) {
x == yDescription
TRUEevaluated 114484 times by 2 tests
Evaluated by:
  • bntest
  • exptest
FALSEevaluated 23732 times by 2 tests
Evaluated by:
  • bntest
  • exptest
23732-114484
123 if (!BN_sqr(a, x, ctx))
!BN_sqr(a, x, ctx)Description
TRUEnever evaluated
FALSEevaluated 114484 times by 2 tests
Evaluated by:
  • bntest
  • exptest
0-114484
124 goto err;
never executed: goto err;
0
125 } else {
executed 114484 times by 2 tests: end of block
Executed by:
  • bntest
  • exptest
114484
126 if (!BN_mul(a, x, y, ctx))
!BN_mul(a, x, y, ctx)Description
TRUEnever evaluated
FALSEevaluated 23732 times by 2 tests
Evaluated by:
  • bntest
  • exptest
0-23732
127 goto err;
never executed: goto err;
0
128 }
executed 23732 times by 2 tests: end of block
Executed by:
  • bntest
  • exptest
23732
129 ca = a;-
130 } else
executed 138216 times by 2 tests: end of block
Executed by:
  • bntest
  • exptest
138216
131 ca = x; /* Just do the mod */
never executed: ca = x;
0
132-
133 ret = BN_div_recp(NULL, r, ca, recp, ctx);-
134-
135err:
code before this statement executed 138216 times by 2 tests: err:
Executed by:
  • bntest
  • exptest
138216
136 BN_CTX_end(ctx);-
137 bn_check_top(r);-
138 return (ret);
executed 138216 times by 2 tests: return (ret);
Executed by:
  • bntest
  • exptest
138216
139}-
140-
141int-
142BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, BN_RECP_CTX *recp,-
143 BN_CTX *ctx)-
144{-
145 int i, j, ret = 0;-
146 BIGNUM *a, *b, *d, *r;-
147-
148 BN_CTX_start(ctx);-
149 a = BN_CTX_get(ctx);-
150 b = BN_CTX_get(ctx);-
151 if (dv != NULL)
dv != ((void *)0)Description
TRUEevaluated 150 times by 1 test
Evaluated by:
  • bntest
FALSEevaluated 138216 times by 2 tests
Evaluated by:
  • bntest
  • exptest
150-138216
152 d = dv;
executed 150 times by 1 test: d = dv;
Executed by:
  • bntest
150
153 else-
154 d = BN_CTX_get(ctx);
executed 138216 times by 2 tests: d = BN_CTX_get(ctx);
Executed by:
  • bntest
  • exptest
138216
155 if (rem != NULL)
rem != ((void *)0)Description
TRUEevaluated 138366 times by 2 tests
Evaluated by:
  • bntest
  • exptest
FALSEnever evaluated
0-138366
156 r = rem;
executed 138366 times by 2 tests: r = rem;
Executed by:
  • bntest
  • exptest
138366
157 else-
158 r = BN_CTX_get(ctx);
never executed: r = BN_CTX_get(ctx);
0
159 if (a == NULL || b == NULL || d == NULL || r == NULL)
a == ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 138366 times by 2 tests
Evaluated by:
  • bntest
  • exptest
b == ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 138366 times by 2 tests
Evaluated by:
  • bntest
  • exptest
d == ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 138366 times by 2 tests
Evaluated by:
  • bntest
  • exptest
r == ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 138366 times by 2 tests
Evaluated by:
  • bntest
  • exptest
0-138366
160 goto err;
never executed: goto err;
0
161-
162 if (BN_ucmp(m, &(recp->N)) < 0) {
BN_ucmp(m, &(recp->N)) < 0Description
TRUEevaluated 343 times by 2 tests
Evaluated by:
  • bntest
  • exptest
FALSEevaluated 138023 times by 2 tests
Evaluated by:
  • bntest
  • exptest
343-138023
163 BN_zero(d);-
164 if (!BN_copy(r, m)) {
!BN_copy(r, m)Description
TRUEnever evaluated
FALSEevaluated 343 times by 2 tests
Evaluated by:
  • bntest
  • exptest
0-343
165 BN_CTX_end(ctx);-
166 return 0;
never executed: return 0;
0
167 }-
168 BN_CTX_end(ctx);-
169 return (1);
executed 343 times by 2 tests: return (1);
Executed by:
  • bntest
  • exptest
343
170 }-
171-
172 /* We want the remainder-
173 * Given input of ABCDEF / ab-
174 * we need multiply ABCDEF by 3 digests of the reciprocal of ab-
175 *-
176 */-
177-
178 /* i := max(BN_num_bits(m), 2*BN_num_bits(N)) */-
179 i = BN_num_bits(m);-
180 j = recp->num_bits << 1;-
181 if (j > i)
j > iDescription
TRUEevaluated 121962 times by 2 tests
Evaluated by:
  • bntest
  • exptest
FALSEevaluated 16061 times by 2 tests
Evaluated by:
  • bntest
  • exptest
16061-121962
182 i = j;
executed 121962 times by 2 tests: i = j;
Executed by:
  • bntest
  • exptest
121962
183-
184 /* Nr := round(2^i / N) */-
185 if (i != recp->shift)
i != recp->shiftDescription
TRUEevaluated 450 times by 2 tests
Evaluated by:
  • bntest
  • exptest
FALSEevaluated 137573 times by 2 tests
Evaluated by:
  • bntest
  • exptest
450-137573
186 recp->shift = BN_reciprocal(&(recp->Nr), &(recp->N), i, ctx);
executed 450 times by 2 tests: recp->shift = BN_reciprocal(&(recp->Nr), &(recp->N), i, ctx);
Executed by:
  • bntest
  • exptest
450
187-
188 /* BN_reciprocal returns i, or -1 for an error */-
189 if (recp->shift == -1)
recp->shift == -1Description
TRUEnever evaluated
FALSEevaluated 138023 times by 2 tests
Evaluated by:
  • bntest
  • exptest
0-138023
190 goto err;
never executed: goto err;
0
191-
192 /* d := |round(round(m / 2^BN_num_bits(N)) * recp->Nr / 2^(i - BN_num_bits(N)))|-
193 * = |round(round(m / 2^BN_num_bits(N)) * round(2^i / N) / 2^(i - BN_num_bits(N)))|-
194 * <= |(m / 2^BN_num_bits(N)) * (2^i / N) * (2^BN_num_bits(N) / 2^i)|-
195 * = |m/N|-
196 */-
197 if (!BN_rshift(a, m, recp->num_bits))
!BN_rshift(a, ...ecp->num_bits)Description
TRUEnever evaluated
FALSEevaluated 138023 times by 2 tests
Evaluated by:
  • bntest
  • exptest
0-138023
198 goto err;
never executed: goto err;
0
199 if (!BN_mul(b, a,&(recp->Nr), ctx))
!BN_mul(b, a,&(recp->Nr), ctx)Description
TRUEnever evaluated
FALSEevaluated 138023 times by 2 tests
Evaluated by:
  • bntest
  • exptest
0-138023
200 goto err;
never executed: goto err;
0
201 if (!BN_rshift(d, b, i - recp->num_bits))
!BN_rshift(d, ...ecp->num_bits)Description
TRUEnever evaluated
FALSEevaluated 138023 times by 2 tests
Evaluated by:
  • bntest
  • exptest
0-138023
202 goto err;
never executed: goto err;
0
203 d->neg = 0;-
204-
205 if (!BN_mul(b, &(recp->N), d, ctx))
!BN_mul(b, &(recp->N), d, ctx)Description
TRUEnever evaluated
FALSEevaluated 138023 times by 2 tests
Evaluated by:
  • bntest
  • exptest
0-138023
206 goto err;
never executed: goto err;
0
207 if (!BN_usub(r, m, b))
!BN_usub(r, m, b)Description
TRUEnever evaluated
FALSEevaluated 138023 times by 2 tests
Evaluated by:
  • bntest
  • exptest
0-138023
208 goto err;
never executed: goto err;
0
209 r->neg = 0;-
210-
211#if 1-
212 j = 0;-
213 while (BN_ucmp(r, &(recp->N)) >= 0) {
BN_ucmp(r, &(recp->N)) >= 0Description
TRUEevaluated 97174 times by 2 tests
Evaluated by:
  • bntest
  • exptest
FALSEevaluated 138023 times by 2 tests
Evaluated by:
  • bntest
  • exptest
97174-138023
214 if (j++ > 2) {
j++ > 2Description
TRUEnever evaluated
FALSEevaluated 97174 times by 2 tests
Evaluated by:
  • bntest
  • exptest
0-97174
215 BNerror(BN_R_BAD_RECIPROCAL);-
216 goto err;
never executed: goto err;
0
217 }-
218 if (!BN_usub(r, r, &(recp->N)))
!BN_usub(r, r, &(recp->N))Description
TRUEnever evaluated
FALSEevaluated 97174 times by 2 tests
Evaluated by:
  • bntest
  • exptest
0-97174
219 goto err;
never executed: goto err;
0
220 if (!BN_add_word(d, 1))
!BN_add_word(d, 1)Description
TRUEnever evaluated
FALSEevaluated 97174 times by 2 tests
Evaluated by:
  • bntest
  • exptest
0-97174
221 goto err;
never executed: goto err;
0
222 }
executed 97174 times by 2 tests: end of block
Executed by:
  • bntest
  • exptest
97174
223#endif-
224-
225 r->neg = BN_is_zero(r) ? 0 : m->neg;
((r)->top == 0)Description
TRUEevaluated 1 time by 1 test
Evaluated by:
  • bntest
FALSEevaluated 138022 times by 2 tests
Evaluated by:
  • bntest
  • exptest
1-138022
226 d->neg = m->neg^recp->N.neg;-
227 ret = 1;-
228-
229err:
code before this statement executed 138023 times by 2 tests: err:
Executed by:
  • bntest
  • exptest
138023
230 BN_CTX_end(ctx);-
231 bn_check_top(dv);-
232 bn_check_top(rem);-
233 return (ret);
executed 138023 times by 2 tests: return (ret);
Executed by:
  • bntest
  • exptest
138023
234}-
235-
236/* len is the expected size of the result-
237 * We actually calculate with an extra word of precision, so-
238 * we can do faster division if the remainder is not required.-
239 */-
240/* r := 2^len / m */-
241int-
242BN_reciprocal(BIGNUM *r, const BIGNUM *m, int len, BN_CTX *ctx)-
243{-
244 int ret = -1;-
245 BIGNUM *t;-
246-
247 BN_CTX_start(ctx);-
248 if ((t = BN_CTX_get(ctx)) == NULL)
(t = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 450 times by 2 tests
Evaluated by:
  • bntest
  • exptest
0-450
249 goto err;
never executed: goto err;
0
250-
251 if (!BN_set_bit(t, len))
!BN_set_bit(t, len)Description
TRUEnever evaluated
FALSEevaluated 450 times by 2 tests
Evaluated by:
  • bntest
  • exptest
0-450
252 goto err;
never executed: goto err;
0
253-
254 if (!BN_div_ct(r, NULL, t,m, ctx))
!BN_div_ct(r, ...0) , t,m, ctx)Description
TRUEnever evaluated
FALSEevaluated 450 times by 2 tests
Evaluated by:
  • bntest
  • exptest
0-450
255 goto err;
never executed: goto err;
0
256-
257 ret = len;-
258-
259err:
code before this statement executed 450 times by 2 tests: err:
Executed by:
  • bntest
  • exptest
450
260 bn_check_top(r);-
261 BN_CTX_end(ctx);-
262 return (ret);
executed 450 times by 2 tests: return (ret);
Executed by:
  • bntest
  • exptest
450
263}-
Source codeSwitch to Preprocessed file
Generated by Squish Coco 4.2.2