summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn/bn_ctx.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libcrypto/bn/bn_ctx.c')
-rw-r--r--src/lib/libcrypto/bn/bn_ctx.c478
1 files changed, 0 insertions, 478 deletions
diff --git a/src/lib/libcrypto/bn/bn_ctx.c b/src/lib/libcrypto/bn/bn_ctx.c
deleted file mode 100644
index eb2d6a43b3..0000000000
--- a/src/lib/libcrypto/bn/bn_ctx.c
+++ /dev/null
@@ -1,478 +0,0 @@
1/* $OpenBSD: bn_ctx.c,v 1.14 2015/02/10 09:50:12 miod Exp $ */
2/* Written by Ulf Moeller for the OpenSSL project. */
3/* ====================================================================
4 * Copyright (c) 1998-2004 The OpenSSL Project. All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
16 * distribution.
17 *
18 * 3. All advertising materials mentioning features or use of this
19 * software must display the following acknowledgment:
20 * "This product includes software developed by the OpenSSL Project
21 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
22 *
23 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
24 * endorse or promote products derived from this software without
25 * prior written permission. For written permission, please contact
26 * openssl-core@openssl.org.
27 *
28 * 5. Products derived from this software may not be called "OpenSSL"
29 * nor may "OpenSSL" appear in their names without prior written
30 * permission of the OpenSSL Project.
31 *
32 * 6. Redistributions of any form whatsoever must retain the following
33 * acknowledgment:
34 * "This product includes software developed by the OpenSSL Project
35 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
36 *
37 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
38 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
39 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
40 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
41 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
42 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
43 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
44 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
45 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
46 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
47 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
48 * OF THE POSSIBILITY OF SUCH DAMAGE.
49 * ====================================================================
50 *
51 * This product includes cryptographic software written by Eric Young
52 * (eay@cryptsoft.com). This product includes software written by Tim
53 * Hudson (tjh@cryptsoft.com).
54 *
55 */
56
57#if !defined(BN_CTX_DEBUG) && !defined(BN_DEBUG)
58#ifndef NDEBUG
59#define NDEBUG
60#endif
61#endif
62
63#include <stdio.h>
64#include <string.h>
65
66#include <openssl/opensslconf.h>
67
68#include <openssl/err.h>
69
70#include "bn_lcl.h"
71
72/* TODO list
73 *
74 * 1. Check a bunch of "(words+1)" type hacks in various bignum functions and
75 * check they can be safely removed.
76 * - Check +1 and other ugliness in BN_from_montgomery()
77 *
78 * 2. Consider allowing a BN_new_ex() that, at least, lets you specify an
79 * appropriate 'block' size that will be honoured by bn_expand_internal() to
80 * prevent piddly little reallocations. OTOH, profiling bignum expansions in
81 * BN_CTX doesn't show this to be a big issue.
82 */
83
84/* How many bignums are in each "pool item"; */
85#define BN_CTX_POOL_SIZE 16
86/* The stack frame info is resizing, set a first-time expansion size; */
87#define BN_CTX_START_FRAMES 32
88
89/***********/
90/* BN_POOL */
91/***********/
92
93/* A bundle of bignums that can be linked with other bundles */
94typedef struct bignum_pool_item {
95 /* The bignum values */
96 BIGNUM vals[BN_CTX_POOL_SIZE];
97 /* Linked-list admin */
98 struct bignum_pool_item *prev, *next;
99} BN_POOL_ITEM;
100
101/* A linked-list of bignums grouped in bundles */
102typedef struct bignum_pool {
103 /* Linked-list admin */
104 BN_POOL_ITEM *head, *current, *tail;
105 /* Stack depth and allocation size */
106 unsigned used, size;
107} BN_POOL;
108
109static void BN_POOL_init(BN_POOL *);
110static void BN_POOL_finish(BN_POOL *);
111#ifndef OPENSSL_NO_DEPRECATED
112static void BN_POOL_reset(BN_POOL *);
113#endif
114static BIGNUM * BN_POOL_get(BN_POOL *);
115static void BN_POOL_release(BN_POOL *, unsigned int);
116
117/************/
118/* BN_STACK */
119/************/
120
121/* A wrapper to manage the "stack frames" */
122typedef struct bignum_ctx_stack {
123 /* Array of indexes into the bignum stack */
124 unsigned int *indexes;
125 /* Number of stack frames, and the size of the allocated array */
126 unsigned int depth, size;
127} BN_STACK;
128
129static void BN_STACK_init(BN_STACK *);
130static void BN_STACK_finish(BN_STACK *);
131#ifndef OPENSSL_NO_DEPRECATED
132static void BN_STACK_reset(BN_STACK *);
133#endif
134static int BN_STACK_push(BN_STACK *, unsigned int);
135static unsigned int BN_STACK_pop(BN_STACK *);
136
137/**********/
138/* BN_CTX */
139/**********/
140
141/* The opaque BN_CTX type */
142struct bignum_ctx {
143 /* The bignum bundles */
144 BN_POOL pool;
145 /* The "stack frames", if you will */
146 BN_STACK stack;
147 /* The number of bignums currently assigned */
148 unsigned int used;
149 /* Depth of stack overflow */
150 int err_stack;
151 /* Block "gets" until an "end" (compatibility behaviour) */
152 int too_many;
153};
154
155/* Enable this to find BN_CTX bugs */
156#ifdef BN_CTX_DEBUG
157static const char *ctxdbg_cur = NULL;
158
159static void
160ctxdbg(BN_CTX *ctx)
161{
162 unsigned int bnidx = 0, fpidx = 0;
163 BN_POOL_ITEM *item = ctx->pool.head;
164 BN_STACK *stack = &ctx->stack;
165
166 fprintf(stderr, "(%08x): ", (unsigned int)ctx);
167 while (bnidx < ctx->used) {
168 fprintf(stderr, "%03x ",
169 item->vals[bnidx++ % BN_CTX_POOL_SIZE].dmax);
170 if (!(bnidx % BN_CTX_POOL_SIZE))
171 item = item->next;
172 }
173 fprintf(stderr, "\n");
174 bnidx = 0;
175 fprintf(stderr, " : ");
176 while (fpidx < stack->depth) {
177 while (bnidx++ < stack->indexes[fpidx])
178 fprintf(stderr, " ");
179 fprintf(stderr, "^^^ ");
180 bnidx++;
181 fpidx++;
182 }
183 fprintf(stderr, "\n");
184}
185#define CTXDBG_ENTRY(str, ctx) \
186 do { \
187 ctxdbg_cur = (str); \
188 fprintf(stderr, "Starting %s\n", ctxdbg_cur); \
189 ctxdbg(ctx); \
190 } while(0)
191
192#define CTXDBG_EXIT(ctx) \
193 do { \
194 fprintf(stderr, "Ending %s\n", ctxdbg_cur); \
195 ctxdbg(ctx); \
196 } while(0)
197
198#define CTXDBG_RET(ctx,ret)
199#else
200#define CTXDBG_ENTRY(str, ctx)
201#define CTXDBG_EXIT(ctx)
202#define CTXDBG_RET(ctx,ret)
203#endif
204
205/* This function is an evil legacy and should not be used. This implementation
206 * is WYSIWYG, though I've done my best. */
207#ifndef OPENSSL_NO_DEPRECATED
208void
209BN_CTX_init(BN_CTX *ctx)
210{
211 /* Assume the caller obtained the context via BN_CTX_new() and so is
212 * trying to reset it for use. Nothing else makes sense, least of all
213 * binary compatibility from a time when they could declare a static
214 * variable. */
215 BN_POOL_reset(&ctx->pool);
216 BN_STACK_reset(&ctx->stack);
217 ctx->used = 0;
218 ctx->err_stack = 0;
219 ctx->too_many = 0;
220}
221#endif
222
223BN_CTX *
224BN_CTX_new(void)
225{
226 BN_CTX *ret = malloc(sizeof(BN_CTX));
227 if (!ret) {
228 BNerr(BN_F_BN_CTX_NEW, ERR_R_MALLOC_FAILURE);
229 return NULL;
230 }
231
232 /* Initialise the structure */
233 BN_POOL_init(&ret->pool);
234 BN_STACK_init(&ret->stack);
235 ret->used = 0;
236 ret->err_stack = 0;
237 ret->too_many = 0;
238 return ret;
239}
240
241void
242BN_CTX_free(BN_CTX *ctx)
243{
244 if (ctx == NULL)
245 return;
246#ifdef BN_CTX_DEBUG
247 {
248 BN_POOL_ITEM *pool = ctx->pool.head;
249 fprintf(stderr, "BN_CTX_free, stack-size=%d, pool-bignums=%d\n",
250 ctx->stack.size, ctx->pool.size);
251 fprintf(stderr, "dmaxs: ");
252 while (pool) {
253 unsigned loop = 0;
254 while (loop < BN_CTX_POOL_SIZE)
255 fprintf(stderr, "%02x ",
256 pool->vals[loop++].dmax);
257 pool = pool->next;
258 }
259 fprintf(stderr, "\n");
260 }
261#endif
262 BN_STACK_finish(&ctx->stack);
263 BN_POOL_finish(&ctx->pool);
264 free(ctx);
265}
266
267void
268BN_CTX_start(BN_CTX *ctx)
269{
270 CTXDBG_ENTRY("BN_CTX_start", ctx);
271
272 /* If we're already overflowing ... */
273 if (ctx->err_stack || ctx->too_many)
274 ctx->err_stack++;
275 /* (Try to) get a new frame pointer */
276 else if (!BN_STACK_push(&ctx->stack, ctx->used)) {
277 BNerr(BN_F_BN_CTX_START, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
278 ctx->err_stack++;
279 }
280 CTXDBG_EXIT(ctx);
281}
282
283void
284BN_CTX_end(BN_CTX *ctx)
285{
286 CTXDBG_ENTRY("BN_CTX_end", ctx);
287
288 if (ctx->err_stack)
289 ctx->err_stack--;
290 else {
291 unsigned int fp = BN_STACK_pop(&ctx->stack);
292 /* Does this stack frame have anything to release? */
293 if (fp < ctx->used)
294 BN_POOL_release(&ctx->pool, ctx->used - fp);
295 ctx->used = fp;
296 /* Unjam "too_many" in case "get" had failed */
297 ctx->too_many = 0;
298 }
299 CTXDBG_EXIT(ctx);
300}
301
302BIGNUM *
303BN_CTX_get(BN_CTX *ctx)
304{
305 BIGNUM *ret;
306
307 CTXDBG_ENTRY("BN_CTX_get", ctx);
308
309 if (ctx->err_stack || ctx->too_many)
310 return NULL;
311 if ((ret = BN_POOL_get(&ctx->pool)) == NULL) {
312 /* Setting too_many prevents repeated "get" attempts from
313 * cluttering the error stack. */
314 ctx->too_many = 1;
315 BNerr(BN_F_BN_CTX_GET, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
316 return NULL;
317 }
318 /* OK, make sure the returned bignum is "zero" */
319 BN_zero(ret);
320 ctx->used++;
321 CTXDBG_RET(ctx, ret);
322 return ret;
323}
324
325/************/
326/* BN_STACK */
327/************/
328
329static void
330BN_STACK_init(BN_STACK *st)
331{
332 st->indexes = NULL;
333 st->depth = st->size = 0;
334}
335
336static void
337BN_STACK_finish(BN_STACK *st)
338{
339 if (st->size)
340 free(st->indexes);
341}
342
343#ifndef OPENSSL_NO_DEPRECATED
344static void
345BN_STACK_reset(BN_STACK *st)
346{
347 st->depth = 0;
348}
349#endif
350
351static int
352BN_STACK_push(BN_STACK *st, unsigned int idx)
353{
354 if (st->depth == st->size)
355 /* Need to expand */
356 {
357 unsigned int newsize = (st->size ?
358 (st->size * 3 / 2) : BN_CTX_START_FRAMES);
359 unsigned int *newitems = reallocarray(NULL,
360 newsize, sizeof(unsigned int));
361 if (!newitems)
362 return 0;
363 if (st->depth)
364 memcpy(newitems, st->indexes, st->depth *
365 sizeof(unsigned int));
366 if (st->size)
367 free(st->indexes);
368 st->indexes = newitems;
369 st->size = newsize;
370 }
371 st->indexes[(st->depth)++] = idx;
372 return 1;
373}
374
375static unsigned int
376BN_STACK_pop(BN_STACK *st)
377{
378 return st->indexes[--(st->depth)];
379}
380
381/***********/
382/* BN_POOL */
383/***********/
384
385static void
386BN_POOL_init(BN_POOL *p)
387{
388 p->head = p->current = p->tail = NULL;
389 p->used = p->size = 0;
390}
391
392static void
393BN_POOL_finish(BN_POOL *p)
394{
395 while (p->head) {
396 unsigned int loop = 0;
397 BIGNUM *bn = p->head->vals;
398 while (loop++ < BN_CTX_POOL_SIZE) {
399 if (bn->d)
400 BN_clear_free(bn);
401 bn++;
402 }
403 p->current = p->head->next;
404 free(p->head);
405 p->head = p->current;
406 }
407}
408
409#ifndef OPENSSL_NO_DEPRECATED
410static void
411BN_POOL_reset(BN_POOL *p)
412{
413 BN_POOL_ITEM *item = p->head;
414 while (item) {
415 unsigned int loop = 0;
416 BIGNUM *bn = item->vals;
417 while (loop++ < BN_CTX_POOL_SIZE) {
418 if (bn->d)
419 BN_clear(bn);
420 bn++;
421 }
422 item = item->next;
423 }
424 p->current = p->head;
425 p->used = 0;
426}
427#endif
428
429static BIGNUM *
430BN_POOL_get(BN_POOL *p)
431{
432 if (p->used == p->size) {
433 BIGNUM *bn;
434 unsigned int loop = 0;
435 BN_POOL_ITEM *item = malloc(sizeof(BN_POOL_ITEM));
436 if (!item)
437 return NULL;
438 /* Initialise the structure */
439 bn = item->vals;
440 while (loop++ < BN_CTX_POOL_SIZE)
441 BN_init(bn++);
442 item->prev = p->tail;
443 item->next = NULL;
444 /* Link it in */
445 if (!p->head)
446 p->head = p->current = p->tail = item;
447 else {
448 p->tail->next = item;
449 p->tail = item;
450 p->current = item;
451 }
452 p->size += BN_CTX_POOL_SIZE;
453 p->used++;
454 /* Return the first bignum from the new pool */
455 return item->vals;
456 }
457 if (!p->used)
458 p->current = p->head;
459 else if ((p->used % BN_CTX_POOL_SIZE) == 0)
460 p->current = p->current->next;
461 return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE);
462}
463
464static void
465BN_POOL_release(BN_POOL *p, unsigned int num)
466{
467 unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE;
468
469 p->used -= num;
470 while (num--) {
471 bn_check_top(p->current->vals + offset);
472 if (!offset) {
473 offset = BN_CTX_POOL_SIZE - 1;
474 p->current = p->current->prev;
475 } else
476 offset--;
477 }
478}
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-05-08 00:30:18 +0000