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