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