RT2163: Remove some unneeded #include's
[openssl.git] / crypto / bn / bn_ctx.c
1 /* crypto/bn/bn_ctx.c */
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 #define OPENSSL_FIPSAPI
64
65 #include <assert.h>
66
67 #include "cryptlib.h"
68 #include "bn_lcl.h"
69
70 /* TODO list
71  *
72  * 1. Check a bunch of "(words+1)" type hacks in various bignum functions and
73  * check they can be safely removed.
74  *  - Check +1 and other ugliness in BN_from_montgomery()
75  *
76  * 2. Consider allowing a BN_new_ex() that, at least, lets you specify an
77  * appropriate 'block' size that will be honoured by bn_expand_internal() to
78  * prevent piddly little reallocations. OTOH, profiling bignum expansions in
79  * BN_CTX doesn't show this to be a big issue.
80  */
81
82 /* How many bignums are in each "pool item"; */
83 #define BN_CTX_POOL_SIZE        16
84 /* The stack frame info is resizing, set a first-time expansion size; */
85 #define BN_CTX_START_FRAMES     32
86
87 /***********/
88 /* BN_POOL */
89 /***********/
90
91 /* A bundle of bignums that can be linked with other bundles */
92 typedef struct bignum_pool_item
93         {
94         /* The bignum values */
95         BIGNUM vals[BN_CTX_POOL_SIZE];
96         /* Linked-list admin */
97         struct bignum_pool_item *prev, *next;
98         } BN_POOL_ITEM;
99 /* A linked-list of bignums grouped in bundles */
100 typedef struct bignum_pool
101         {
102         /* Linked-list admin */
103         BN_POOL_ITEM *head, *current, *tail;
104         /* Stack depth and allocation size */
105         unsigned used, size;
106         } BN_POOL;
107 static void             BN_POOL_init(BN_POOL *);
108 static void             BN_POOL_finish(BN_POOL *);
109 #ifndef OPENSSL_NO_DEPRECATED
110 static void             BN_POOL_reset(BN_POOL *);
111 #endif
112 static BIGNUM *         BN_POOL_get(BN_POOL *);
113 static void             BN_POOL_release(BN_POOL *, unsigned int);
114
115 /************/
116 /* BN_STACK */
117 /************/
118
119 /* A wrapper to manage the "stack frames" */
120 typedef struct bignum_ctx_stack
121         {
122         /* Array of indexes into the bignum stack */
123         unsigned int *indexes;
124         /* Number of stack frames, and the size of the allocated array */
125         unsigned int depth, size;
126         } BN_STACK;
127 static void             BN_STACK_init(BN_STACK *);
128 static void             BN_STACK_finish(BN_STACK *);
129 #ifndef OPENSSL_NO_DEPRECATED
130 static void             BN_STACK_reset(BN_STACK *);
131 #endif
132 static int              BN_STACK_push(BN_STACK *, unsigned int);
133 static unsigned int     BN_STACK_pop(BN_STACK *);
134
135 /**********/
136 /* BN_CTX */
137 /**********/
138
139 /* The opaque BN_CTX type */
140 struct bignum_ctx
141         {
142         /* The bignum bundles */
143         BN_POOL pool;
144         /* The "stack frames", if you will */
145         BN_STACK stack;
146         /* The number of bignums currently assigned */
147         unsigned int used;
148         /* Depth of stack overflow */
149         int err_stack;
150         /* Block "gets" until an "end" (compatibility behaviour) */
151         int too_many;
152         };
153
154 /* Enable this to find BN_CTX bugs */
155 #ifdef BN_CTX_DEBUG
156 static const char *ctxdbg_cur = NULL;
157 static void ctxdbg(BN_CTX *ctx)
158         {
159         unsigned int bnidx = 0, fpidx = 0;
160         BN_POOL_ITEM *item = ctx->pool.head;
161         BN_STACK *stack = &ctx->stack;
162         fprintf(stderr,"(%08x): ", (unsigned int)ctx);
163         while(bnidx < ctx->used)
164                 {
165                 fprintf(stderr,"%03x ", item->vals[bnidx++ % BN_CTX_POOL_SIZE].dmax);
166                 if(!(bnidx % BN_CTX_POOL_SIZE))
167                         item = item->next;
168                 }
169         fprintf(stderr,"\n");
170         bnidx = 0;
171         fprintf(stderr,"          : ");
172         while(fpidx < stack->depth)
173                 {
174                 while(bnidx++ < stack->indexes[fpidx])
175                         fprintf(stderr,"    ");
176                 fprintf(stderr,"^^^ ");
177                 bnidx++;
178                 fpidx++;
179                 }
180         fprintf(stderr,"\n");
181         }
182 #define CTXDBG_ENTRY(str, ctx)  do { \
183                                 ctxdbg_cur = (str); \
184                                 fprintf(stderr,"Starting %s\n", ctxdbg_cur); \
185                                 ctxdbg(ctx); \
186                                 } while(0)
187 #define CTXDBG_EXIT(ctx)        do { \
188                                 fprintf(stderr,"Ending %s\n", ctxdbg_cur); \
189                                 ctxdbg(ctx); \
190                                 } while(0)
191 #define CTXDBG_RET(ctx,ret)
192 #else
193 #define CTXDBG_ENTRY(str, ctx)
194 #define CTXDBG_EXIT(ctx)
195 #define CTXDBG_RET(ctx,ret)
196 #endif
197
198 /* This function is an evil legacy and should not be used. This implementation
199  * is WYSIWYG, though I've done my best. */
200 #ifndef OPENSSL_NO_DEPRECATED
201 void BN_CTX_init(BN_CTX *ctx)
202         {
203         /* Assume the caller obtained the context via BN_CTX_new() and so is
204          * trying to reset it for use. Nothing else makes sense, least of all
205          * binary compatibility from a time when they could declare a static
206          * variable. */
207         BN_POOL_reset(&ctx->pool);
208         BN_STACK_reset(&ctx->stack);
209         ctx->used = 0;
210         ctx->err_stack = 0;
211         ctx->too_many = 0;
212         }
213 #endif
214
215 BN_CTX *BN_CTX_new(void)
216         {
217         BN_CTX *ret = OPENSSL_malloc(sizeof(BN_CTX));
218         if(!ret)
219                 {
220                 BNerr(BN_F_BN_CTX_NEW,ERR_R_MALLOC_FAILURE);
221                 return NULL;
222                 }
223         /* Initialise the structure */
224         BN_POOL_init(&ret->pool);
225         BN_STACK_init(&ret->stack);
226         ret->used = 0;
227         ret->err_stack = 0;
228         ret->too_many = 0;
229         return ret;
230         }
231
232 void BN_CTX_free(BN_CTX *ctx)
233         {
234         if (ctx == NULL)
235                 return;
236 #ifdef BN_CTX_DEBUG
237         {
238         BN_POOL_ITEM *pool = ctx->pool.head;
239         fprintf(stderr,"BN_CTX_free, stack-size=%d, pool-bignums=%d\n",
240                 ctx->stack.size, ctx->pool.size);
241         fprintf(stderr,"dmaxs: ");
242         while(pool) {
243                 unsigned loop = 0;
244                 while(loop < BN_CTX_POOL_SIZE)
245                         fprintf(stderr,"%02x ", pool->vals[loop++].dmax);
246                 pool = pool->next;
247         }
248         fprintf(stderr,"\n");
249         }
250 #endif
251         BN_STACK_finish(&ctx->stack);
252         BN_POOL_finish(&ctx->pool);
253         OPENSSL_free(ctx);
254         }
255
256 void BN_CTX_start(BN_CTX *ctx)
257         {
258         CTXDBG_ENTRY("BN_CTX_start", ctx);
259         /* If we're already overflowing ... */
260         if(ctx->err_stack || ctx->too_many)
261                 ctx->err_stack++;
262         /* (Try to) get a new frame pointer */
263         else if(!BN_STACK_push(&ctx->stack, ctx->used))
264                 {
265                 BNerr(BN_F_BN_CTX_START,BN_R_TOO_MANY_TEMPORARY_VARIABLES);
266                 ctx->err_stack++;
267                 }
268         CTXDBG_EXIT(ctx);
269         }
270
271 void BN_CTX_end(BN_CTX *ctx)
272         {
273         CTXDBG_ENTRY("BN_CTX_end", ctx);
274         if(ctx->err_stack)
275                 ctx->err_stack--;
276         else
277                 {
278                 unsigned int fp = BN_STACK_pop(&ctx->stack);
279                 /* Does this stack frame have anything to release? */
280                 if(fp < ctx->used)
281                         BN_POOL_release(&ctx->pool, ctx->used - fp);
282                 ctx->used = fp;
283                 /* Unjam "too_many" in case "get" had failed */
284                 ctx->too_many = 0;
285                 }
286         CTXDBG_EXIT(ctx);
287         }
288
289 BIGNUM *BN_CTX_get(BN_CTX *ctx)
290         {
291         BIGNUM *ret;
292         CTXDBG_ENTRY("BN_CTX_get", ctx);
293         if(ctx->err_stack || ctx->too_many) return NULL;
294         if((ret = BN_POOL_get(&ctx->pool)) == NULL)
295                 {
296                 /* Setting too_many prevents repeated "get" attempts from
297                  * cluttering the error stack. */
298                 ctx->too_many = 1;
299                 BNerr(BN_F_BN_CTX_GET,BN_R_TOO_MANY_TEMPORARY_VARIABLES);
300                 return NULL;
301                 }
302         /* OK, make sure the returned bignum is "zero" */
303         BN_zero(ret);
304         ctx->used++;
305         CTXDBG_RET(ctx, ret);
306         return ret;
307         }
308
309 /************/
310 /* BN_STACK */
311 /************/
312
313 static void BN_STACK_init(BN_STACK *st)
314         {
315         st->indexes = NULL;
316         st->depth = st->size = 0;
317         }
318
319 static void BN_STACK_finish(BN_STACK *st)
320         {
321         if(st->size) OPENSSL_free(st->indexes);
322         }
323
324 #ifndef OPENSSL_NO_DEPRECATED
325 static void BN_STACK_reset(BN_STACK *st)
326         {
327         st->depth = 0;
328         }
329 #endif
330
331 static int BN_STACK_push(BN_STACK *st, unsigned int idx)
332         {
333         if(st->depth == st->size)
334                 /* Need to expand */
335                 {
336                 unsigned int newsize = (st->size ?
337                                 (st->size * 3 / 2) : BN_CTX_START_FRAMES);
338                 unsigned int *newitems = OPENSSL_malloc(newsize *
339                                                 sizeof(unsigned int));
340                 if(!newitems) return 0;
341                 if(st->depth)
342                         memcpy(newitems, st->indexes, st->depth *
343                                                 sizeof(unsigned int));
344                 if(st->size) OPENSSL_free(st->indexes);
345                 st->indexes = newitems;
346                 st->size = newsize;
347                 }
348         st->indexes[(st->depth)++] = idx;
349         return 1;
350         }
351
352 static unsigned int BN_STACK_pop(BN_STACK *st)
353         {
354         return st->indexes[--(st->depth)];
355         }
356
357 /***********/
358 /* BN_POOL */
359 /***********/
360
361 static void BN_POOL_init(BN_POOL *p)
362         {
363         p->head = p->current = p->tail = NULL;
364         p->used = p->size = 0;
365         }
366
367 static void BN_POOL_finish(BN_POOL *p)
368         {
369         while(p->head)
370                 {
371                 unsigned int loop = 0;
372                 BIGNUM *bn = p->head->vals;
373                 while(loop++ < BN_CTX_POOL_SIZE)
374                         {
375                         if(bn->d) BN_clear_free(bn);
376                         bn++;
377                         }
378                 p->current = p->head->next;
379                 OPENSSL_free(p->head);
380                 p->head = p->current;
381                 }
382         }
383
384 #ifndef OPENSSL_NO_DEPRECATED
385 static void BN_POOL_reset(BN_POOL *p)
386         {
387         BN_POOL_ITEM *item = p->head;
388         while(item)
389                 {
390                 unsigned int loop = 0;
391                 BIGNUM *bn = item->vals;
392                 while(loop++ < BN_CTX_POOL_SIZE)
393                         {
394                         if(bn->d) BN_clear(bn);
395                         bn++;
396                         }
397                 item = item->next;
398                 }
399         p->current = p->head;
400         p->used = 0;
401         }
402 #endif
403
404 static BIGNUM *BN_POOL_get(BN_POOL *p)
405         {
406         if(p->used == p->size)
407                 {
408                 BIGNUM *bn;
409                 unsigned int loop = 0;
410                 BN_POOL_ITEM *item = OPENSSL_malloc(sizeof(BN_POOL_ITEM));
411                 if(!item) return NULL;
412                 /* Initialise the structure */
413                 bn = item->vals;
414                 while(loop++ < BN_CTX_POOL_SIZE)
415                         BN_init(bn++);
416                 item->prev = p->tail;
417                 item->next = NULL;
418                 /* Link it in */
419                 if(!p->head)
420                         p->head = p->current = p->tail = item;
421                 else
422                         {
423                         p->tail->next = item;
424                         p->tail = item;
425                         p->current = item;
426                         }
427                 p->size += BN_CTX_POOL_SIZE;
428                 p->used++;
429                 /* Return the first bignum from the new pool */
430                 return item->vals;
431                 }
432         if(!p->used)
433                 p->current = p->head;
434         else if((p->used % BN_CTX_POOL_SIZE) == 0)
435                 p->current = p->current->next;
436         return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE);
437         }
438
439 static void BN_POOL_release(BN_POOL *p, unsigned int num)
440         {
441         unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE;
442         p->used -= num;
443         while(num--)
444                 {
445                 bn_check_top(p->current->vals + offset);
446                 if(!offset)
447                         {
448                         offset = BN_CTX_POOL_SIZE - 1;
449                         p->current = p->current->prev;
450                         }
451                 else
452                         offset--;
453                 }
454         }
455