159191Skris/* crypto/bn/bn_ctx.c */
259191Skris/* Written by Ulf Moeller for the OpenSSL project. */
359191Skris/* ====================================================================
4160814Ssimon * Copyright (c) 1998-2004 The OpenSSL Project.  All rights reserved.
559191Skris *
659191Skris * Redistribution and use in source and binary forms, with or without
759191Skris * modification, are permitted provided that the following conditions
859191Skris * are met:
959191Skris *
1059191Skris * 1. Redistributions of source code must retain the above copyright
11280304Sjkim *    notice, this list of conditions and the following disclaimer.
1259191Skris *
1359191Skris * 2. Redistributions in binary form must reproduce the above copyright
1459191Skris *    notice, this list of conditions and the following disclaimer in
1559191Skris *    the documentation and/or other materials provided with the
1659191Skris *    distribution.
1759191Skris *
1859191Skris * 3. All advertising materials mentioning features or use of this
1959191Skris *    software must display the following acknowledgment:
2059191Skris *    "This product includes software developed by the OpenSSL Project
2159191Skris *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
2259191Skris *
2359191Skris * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
2459191Skris *    endorse or promote products derived from this software without
2559191Skris *    prior written permission. For written permission, please contact
2659191Skris *    openssl-core@openssl.org.
2759191Skris *
2859191Skris * 5. Products derived from this software may not be called "OpenSSL"
2959191Skris *    nor may "OpenSSL" appear in their names without prior written
3059191Skris *    permission of the OpenSSL Project.
3159191Skris *
3259191Skris * 6. Redistributions of any form whatsoever must retain the following
3359191Skris *    acknowledgment:
3459191Skris *    "This product includes software developed by the OpenSSL Project
3559191Skris *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
3659191Skris *
3759191Skris * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
3859191Skris * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
3959191Skris * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
4059191Skris * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
4159191Skris * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
4259191Skris * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
4359191Skris * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
4459191Skris * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
4559191Skris * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
4659191Skris * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
4759191Skris * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
4859191Skris * OF THE POSSIBILITY OF SUCH DAMAGE.
4959191Skris * ====================================================================
5059191Skris *
5159191Skris * This product includes cryptographic software written by Eric Young
5259191Skris * (eay@cryptsoft.com).  This product includes software written by Tim
5359191Skris * Hudson (tjh@cryptsoft.com).
5459191Skris *
5559191Skris */
5659191Skris
57160814Ssimon#if !defined(BN_CTX_DEBUG) && !defined(BN_DEBUG)
58280304Sjkim# ifndef NDEBUG
59280304Sjkim#  define NDEBUG
60280304Sjkim# endif
6159191Skris#endif
6259191Skris
6359191Skris#include <stdio.h>
6459191Skris#include <assert.h>
65109998Smarkm
6659191Skris#include "cryptlib.h"
67109998Smarkm#include "bn_lcl.h"
6859191Skris
69280304Sjkim/*-
70280304Sjkim * TODO list
71160814Ssimon *
72160814Ssimon * 1. Check a bunch of "(words+1)" type hacks in various bignum functions and
73160814Ssimon * check they can be safely removed.
74160814Ssimon *  - Check +1 and other ugliness in BN_from_montgomery()
75160814Ssimon *
76160814Ssimon * 2. Consider allowing a BN_new_ex() that, at least, lets you specify an
77160814Ssimon * appropriate 'block' size that will be honoured by bn_expand_internal() to
78160814Ssimon * prevent piddly little reallocations. OTOH, profiling bignum expansions in
79160814Ssimon * BN_CTX doesn't show this to be a big issue.
80160814Ssimon */
8159191Skris
82160814Ssimon/* How many bignums are in each "pool item"; */
83280304Sjkim#define BN_CTX_POOL_SIZE        16
84160814Ssimon/* The stack frame info is resizing, set a first-time expansion size; */
85280304Sjkim#define BN_CTX_START_FRAMES     32
86160814Ssimon
87160814Ssimon/***********/
88160814Ssimon/* BN_POOL */
89160814Ssimon/***********/
90160814Ssimon
91160814Ssimon/* A bundle of bignums that can be linked with other bundles */
92280304Sjkimtypedef struct bignum_pool_item {
93280304Sjkim    /* The bignum values */
94280304Sjkim    BIGNUM vals[BN_CTX_POOL_SIZE];
95280304Sjkim    /* Linked-list admin */
96280304Sjkim    struct bignum_pool_item *prev, *next;
97280304Sjkim} BN_POOL_ITEM;
98160814Ssimon/* A linked-list of bignums grouped in bundles */
99280304Sjkimtypedef struct bignum_pool {
100280304Sjkim    /* Linked-list admin */
101280304Sjkim    BN_POOL_ITEM *head, *current, *tail;
102280304Sjkim    /* Stack depth and allocation size */
103280304Sjkim    unsigned used, size;
104280304Sjkim} BN_POOL;
105280304Sjkimstatic void BN_POOL_init(BN_POOL *);
106280304Sjkimstatic void BN_POOL_finish(BN_POOL *);
107160814Ssimon#ifndef OPENSSL_NO_DEPRECATED
108280304Sjkimstatic void BN_POOL_reset(BN_POOL *);
109160814Ssimon#endif
110280304Sjkimstatic BIGNUM *BN_POOL_get(BN_POOL *);
111280304Sjkimstatic void BN_POOL_release(BN_POOL *, unsigned int);
11259191Skris
113160814Ssimon/************/
114160814Ssimon/* BN_STACK */
115160814Ssimon/************/
116160814Ssimon
117160814Ssimon/* A wrapper to manage the "stack frames" */
118280304Sjkimtypedef struct bignum_ctx_stack {
119280304Sjkim    /* Array of indexes into the bignum stack */
120280304Sjkim    unsigned int *indexes;
121280304Sjkim    /* Number of stack frames, and the size of the allocated array */
122280304Sjkim    unsigned int depth, size;
123280304Sjkim} BN_STACK;
124280304Sjkimstatic void BN_STACK_init(BN_STACK *);
125280304Sjkimstatic void BN_STACK_finish(BN_STACK *);
126160814Ssimon#ifndef OPENSSL_NO_DEPRECATED
127280304Sjkimstatic void BN_STACK_reset(BN_STACK *);
128160814Ssimon#endif
129280304Sjkimstatic int BN_STACK_push(BN_STACK *, unsigned int);
130280304Sjkimstatic unsigned int BN_STACK_pop(BN_STACK *);
131160814Ssimon
132160814Ssimon/**********/
133160814Ssimon/* BN_CTX */
134160814Ssimon/**********/
135160814Ssimon
136160814Ssimon/* The opaque BN_CTX type */
137280304Sjkimstruct bignum_ctx {
138280304Sjkim    /* The bignum bundles */
139280304Sjkim    BN_POOL pool;
140280304Sjkim    /* The "stack frames", if you will */
141280304Sjkim    BN_STACK stack;
142280304Sjkim    /* The number of bignums currently assigned */
143280304Sjkim    unsigned int used;
144280304Sjkim    /* Depth of stack overflow */
145280304Sjkim    int err_stack;
146280304Sjkim    /* Block "gets" until an "end" (compatibility behaviour) */
147280304Sjkim    int too_many;
148280304Sjkim};
149160814Ssimon
150160814Ssimon/* Enable this to find BN_CTX bugs */
151160814Ssimon#ifdef BN_CTX_DEBUG
152160814Ssimonstatic const char *ctxdbg_cur = NULL;
153160814Ssimonstatic void ctxdbg(BN_CTX *ctx)
154280304Sjkim{
155280304Sjkim    unsigned int bnidx = 0, fpidx = 0;
156280304Sjkim    BN_POOL_ITEM *item = ctx->pool.head;
157280304Sjkim    BN_STACK *stack = &ctx->stack;
158280304Sjkim    fprintf(stderr, "(%16p): ", ctx);
159280304Sjkim    while (bnidx < ctx->used) {
160280304Sjkim        fprintf(stderr, "%03x ", item->vals[bnidx++ % BN_CTX_POOL_SIZE].dmax);
161280304Sjkim        if (!(bnidx % BN_CTX_POOL_SIZE))
162280304Sjkim            item = item->next;
163280304Sjkim    }
164280304Sjkim    fprintf(stderr, "\n");
165280304Sjkim    bnidx = 0;
166280304Sjkim    fprintf(stderr, "          : ");
167280304Sjkim    while (fpidx < stack->depth) {
168280304Sjkim        while (bnidx++ < stack->indexes[fpidx])
169280304Sjkim            fprintf(stderr, "    ");
170280304Sjkim        fprintf(stderr, "^^^ ");
171280304Sjkim        bnidx++;
172280304Sjkim        fpidx++;
173280304Sjkim    }
174280304Sjkim    fprintf(stderr, "\n");
175280304Sjkim}
176280304Sjkim
177280304Sjkim# define CTXDBG_ENTRY(str, ctx)  do { \
178280304Sjkim                                ctxdbg_cur = (str); \
179280304Sjkim                                fprintf(stderr,"Starting %s\n", ctxdbg_cur); \
180280304Sjkim                                ctxdbg(ctx); \
181280304Sjkim                                } while(0)
182280304Sjkim# define CTXDBG_EXIT(ctx)        do { \
183280304Sjkim                                fprintf(stderr,"Ending %s\n", ctxdbg_cur); \
184280304Sjkim                                ctxdbg(ctx); \
185280304Sjkim                                } while(0)
186280304Sjkim# define CTXDBG_RET(ctx,ret)
187160814Ssimon#else
188280304Sjkim# define CTXDBG_ENTRY(str, ctx)
189280304Sjkim# define CTXDBG_EXIT(ctx)
190280304Sjkim# define CTXDBG_RET(ctx,ret)
191160814Ssimon#endif
19259191Skris
193280304Sjkim/*
194280304Sjkim * This function is an evil legacy and should not be used. This
195280304Sjkim * implementation is WYSIWYG, though I've done my best.
196280304Sjkim */
197160814Ssimon#ifndef OPENSSL_NO_DEPRECATED
19859191Skrisvoid BN_CTX_init(BN_CTX *ctx)
199280304Sjkim{
200280304Sjkim    /*
201280304Sjkim     * Assume the caller obtained the context via BN_CTX_new() and so is
202280304Sjkim     * trying to reset it for use. Nothing else makes sense, least of all
203280304Sjkim     * binary compatibility from a time when they could declare a static
204280304Sjkim     * variable.
205280304Sjkim     */
206280304Sjkim    BN_POOL_reset(&ctx->pool);
207280304Sjkim    BN_STACK_reset(&ctx->stack);
208280304Sjkim    ctx->used = 0;
209280304Sjkim    ctx->err_stack = 0;
210280304Sjkim    ctx->too_many = 0;
211280304Sjkim}
212109998Smarkm#endif
213160814Ssimon
214160814SsimonBN_CTX *BN_CTX_new(void)
215280304Sjkim{
216280304Sjkim    BN_CTX *ret = OPENSSL_malloc(sizeof(BN_CTX));
217280304Sjkim    if (!ret) {
218280304Sjkim        BNerr(BN_F_BN_CTX_NEW, ERR_R_MALLOC_FAILURE);
219280304Sjkim        return NULL;
220280304Sjkim    }
221280304Sjkim    /* Initialise the structure */
222280304Sjkim    BN_POOL_init(&ret->pool);
223280304Sjkim    BN_STACK_init(&ret->stack);
224280304Sjkim    ret->used = 0;
225280304Sjkim    ret->err_stack = 0;
226280304Sjkim    ret->too_many = 0;
227280304Sjkim    return ret;
228280304Sjkim}
22959191Skris
23059191Skrisvoid BN_CTX_free(BN_CTX *ctx)
231280304Sjkim{
232280304Sjkim    if (ctx == NULL)
233280304Sjkim        return;
234160814Ssimon#ifdef BN_CTX_DEBUG
235280304Sjkim    {
236280304Sjkim        BN_POOL_ITEM *pool = ctx->pool.head;
237280304Sjkim        fprintf(stderr, "BN_CTX_free, stack-size=%d, pool-bignums=%d\n",
238280304Sjkim                ctx->stack.size, ctx->pool.size);
239280304Sjkim        fprintf(stderr, "dmaxs: ");
240280304Sjkim        while (pool) {
241280304Sjkim            unsigned loop = 0;
242280304Sjkim            while (loop < BN_CTX_POOL_SIZE)
243280304Sjkim                fprintf(stderr, "%02x ", pool->vals[loop++].dmax);
244280304Sjkim            pool = pool->next;
245280304Sjkim        }
246280304Sjkim        fprintf(stderr, "\n");
247280304Sjkim    }
248160814Ssimon#endif
249280304Sjkim    BN_STACK_finish(&ctx->stack);
250280304Sjkim    BN_POOL_finish(&ctx->pool);
251280304Sjkim    OPENSSL_free(ctx);
252280304Sjkim}
25359191Skris
25459191Skrisvoid BN_CTX_start(BN_CTX *ctx)
255280304Sjkim{
256280304Sjkim    CTXDBG_ENTRY("BN_CTX_start", ctx);
257280304Sjkim    /* If we're already overflowing ... */
258280304Sjkim    if (ctx->err_stack || ctx->too_many)
259280304Sjkim        ctx->err_stack++;
260280304Sjkim    /* (Try to) get a new frame pointer */
261280304Sjkim    else if (!BN_STACK_push(&ctx->stack, ctx->used)) {
262280304Sjkim        BNerr(BN_F_BN_CTX_START, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
263280304Sjkim        ctx->err_stack++;
264280304Sjkim    }
265280304Sjkim    CTXDBG_EXIT(ctx);
266280304Sjkim}
26759191Skris
268160814Ssimonvoid BN_CTX_end(BN_CTX *ctx)
269280304Sjkim{
270280304Sjkim    CTXDBG_ENTRY("BN_CTX_end", ctx);
271280304Sjkim    if (ctx->err_stack)
272280304Sjkim        ctx->err_stack--;
273280304Sjkim    else {
274280304Sjkim        unsigned int fp = BN_STACK_pop(&ctx->stack);
275280304Sjkim        /* Does this stack frame have anything to release? */
276280304Sjkim        if (fp < ctx->used)
277280304Sjkim            BN_POOL_release(&ctx->pool, ctx->used - fp);
278280304Sjkim        ctx->used = fp;
279280304Sjkim        /* Unjam "too_many" in case "get" had failed */
280280304Sjkim        ctx->too_many = 0;
281280304Sjkim    }
282280304Sjkim    CTXDBG_EXIT(ctx);
283280304Sjkim}
284109998Smarkm
28559191SkrisBIGNUM *BN_CTX_get(BN_CTX *ctx)
286280304Sjkim{
287280304Sjkim    BIGNUM *ret;
288280304Sjkim    CTXDBG_ENTRY("BN_CTX_get", ctx);
289280304Sjkim    if (ctx->err_stack || ctx->too_many)
290280304Sjkim        return NULL;
291280304Sjkim    if ((ret = BN_POOL_get(&ctx->pool)) == NULL) {
292280304Sjkim        /*
293280304Sjkim         * Setting too_many prevents repeated "get" attempts from cluttering
294280304Sjkim         * the error stack.
295280304Sjkim         */
296280304Sjkim        ctx->too_many = 1;
297280304Sjkim        BNerr(BN_F_BN_CTX_GET, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
298280304Sjkim        return NULL;
299280304Sjkim    }
300280304Sjkim    /* OK, make sure the returned bignum is "zero" */
301280304Sjkim    BN_zero(ret);
302280304Sjkim    ctx->used++;
303280304Sjkim    CTXDBG_RET(ctx, ret);
304280304Sjkim    return ret;
305280304Sjkim}
306160814Ssimon
307160814Ssimon/************/
308160814Ssimon/* BN_STACK */
309160814Ssimon/************/
310160814Ssimon
311160814Ssimonstatic void BN_STACK_init(BN_STACK *st)
312280304Sjkim{
313280304Sjkim    st->indexes = NULL;
314280304Sjkim    st->depth = st->size = 0;
315280304Sjkim}
316160814Ssimon
317160814Ssimonstatic void BN_STACK_finish(BN_STACK *st)
318280304Sjkim{
319280304Sjkim    if (st->size)
320280304Sjkim        OPENSSL_free(st->indexes);
321280304Sjkim}
322160814Ssimon
323160814Ssimon#ifndef OPENSSL_NO_DEPRECATED
324160814Ssimonstatic void BN_STACK_reset(BN_STACK *st)
325280304Sjkim{
326280304Sjkim    st->depth = 0;
327280304Sjkim}
328160814Ssimon#endif
329160814Ssimon
330160814Ssimonstatic int BN_STACK_push(BN_STACK *st, unsigned int idx)
331280304Sjkim{
332280304Sjkim    if (st->depth == st->size)
333280304Sjkim        /* Need to expand */
334280304Sjkim    {
335280304Sjkim        unsigned int newsize = (st->size ?
336280304Sjkim                                (st->size * 3 / 2) : BN_CTX_START_FRAMES);
337280304Sjkim        unsigned int *newitems = OPENSSL_malloc(newsize *
338280304Sjkim                                                sizeof(unsigned int));
339280304Sjkim        if (!newitems)
340280304Sjkim            return 0;
341280304Sjkim        if (st->depth)
342280304Sjkim            memcpy(newitems, st->indexes, st->depth * sizeof(unsigned int));
343280304Sjkim        if (st->size)
344280304Sjkim            OPENSSL_free(st->indexes);
345280304Sjkim        st->indexes = newitems;
346280304Sjkim        st->size = newsize;
347280304Sjkim    }
348280304Sjkim    st->indexes[(st->depth)++] = idx;
349280304Sjkim    return 1;
350280304Sjkim}
351160814Ssimon
352160814Ssimonstatic unsigned int BN_STACK_pop(BN_STACK *st)
353280304Sjkim{
354280304Sjkim    return st->indexes[--(st->depth)];
355280304Sjkim}
356160814Ssimon
357160814Ssimon/***********/
358160814Ssimon/* BN_POOL */
359160814Ssimon/***********/
360160814Ssimon
361160814Ssimonstatic void BN_POOL_init(BN_POOL *p)
362280304Sjkim{
363280304Sjkim    p->head = p->current = p->tail = NULL;
364280304Sjkim    p->used = p->size = 0;
365280304Sjkim}
366160814Ssimon
367160814Ssimonstatic void BN_POOL_finish(BN_POOL *p)
368280304Sjkim{
369280304Sjkim    while (p->head) {
370280304Sjkim        unsigned int loop = 0;
371280304Sjkim        BIGNUM *bn = p->head->vals;
372280304Sjkim        while (loop++ < BN_CTX_POOL_SIZE) {
373280304Sjkim            if (bn->d)
374280304Sjkim                BN_clear_free(bn);
375280304Sjkim            bn++;
376280304Sjkim        }
377280304Sjkim        p->current = p->head->next;
378280304Sjkim        OPENSSL_free(p->head);
379280304Sjkim        p->head = p->current;
380280304Sjkim    }
381280304Sjkim}
38259191Skris
383160814Ssimon#ifndef OPENSSL_NO_DEPRECATED
384160814Ssimonstatic void BN_POOL_reset(BN_POOL *p)
385280304Sjkim{
386280304Sjkim    BN_POOL_ITEM *item = p->head;
387280304Sjkim    while (item) {
388280304Sjkim        unsigned int loop = 0;
389280304Sjkim        BIGNUM *bn = item->vals;
390280304Sjkim        while (loop++ < BN_CTX_POOL_SIZE) {
391280304Sjkim            if (bn->d)
392280304Sjkim                BN_clear(bn);
393280304Sjkim            bn++;
394280304Sjkim        }
395280304Sjkim        item = item->next;
396280304Sjkim    }
397280304Sjkim    p->current = p->head;
398280304Sjkim    p->used = 0;
399280304Sjkim}
400160814Ssimon#endif
40159191Skris
402160814Ssimonstatic BIGNUM *BN_POOL_get(BN_POOL *p)
403280304Sjkim{
404280304Sjkim    if (p->used == p->size) {
405280304Sjkim        BIGNUM *bn;
406280304Sjkim        unsigned int loop = 0;
407280304Sjkim        BN_POOL_ITEM *item = OPENSSL_malloc(sizeof(BN_POOL_ITEM));
408280304Sjkim        if (!item)
409280304Sjkim            return NULL;
410280304Sjkim        /* Initialise the structure */
411280304Sjkim        bn = item->vals;
412280304Sjkim        while (loop++ < BN_CTX_POOL_SIZE)
413280304Sjkim            BN_init(bn++);
414280304Sjkim        item->prev = p->tail;
415280304Sjkim        item->next = NULL;
416280304Sjkim        /* Link it in */
417280304Sjkim        if (!p->head)
418280304Sjkim            p->head = p->current = p->tail = item;
419280304Sjkim        else {
420280304Sjkim            p->tail->next = item;
421280304Sjkim            p->tail = item;
422280304Sjkim            p->current = item;
423280304Sjkim        }
424280304Sjkim        p->size += BN_CTX_POOL_SIZE;
425280304Sjkim        p->used++;
426280304Sjkim        /* Return the first bignum from the new pool */
427280304Sjkim        return item->vals;
428280304Sjkim    }
429280304Sjkim    if (!p->used)
430280304Sjkim        p->current = p->head;
431280304Sjkim    else if ((p->used % BN_CTX_POOL_SIZE) == 0)
432280304Sjkim        p->current = p->current->next;
433280304Sjkim    return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE);
434280304Sjkim}
435160814Ssimon
436160814Ssimonstatic void BN_POOL_release(BN_POOL *p, unsigned int num)
437280304Sjkim{
438280304Sjkim    unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE;
439280304Sjkim    p->used -= num;
440280304Sjkim    while (num--) {
441280304Sjkim        bn_check_top(p->current->vals + offset);
442280304Sjkim        if (!offset) {
443280304Sjkim            offset = BN_CTX_POOL_SIZE - 1;
444280304Sjkim            p->current = p->current->prev;
445280304Sjkim        } else
446280304Sjkim            offset--;
447280304Sjkim    }
448280304Sjkim}
449