Pollard's rho algorithm for computing discrete logs.

[u/mdw/catacomb] / mparena.c

/* -*-c-*-
 *
 * $Id: mparena.c,v 1.5 2000/06/17 11:35:48 mdw Exp $
 *
 * Allocation and freeing of MP buffers
 *
 * (c) 1999 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------* 
 *
 * This file is part of Catacomb.
 *
 * Catacomb is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Library General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 * 
 * Catacomb is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Library General Public License for more details.
 * 
 * You should have received a copy of the GNU Library General Public
 * License along with Catacomb; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, USA.
 */

/*----- Revision history --------------------------------------------------* 
 *
 * $Log: mparena.c,v $
 * Revision 1.5  2000/06/17 11:35:48  mdw
 * Overhaul to use mLib's arena system underneath.
 *
 * Revision 1.4  1999/12/10 23:28:52  mdw
 * Memory allocation counting.
 *
 * Revision 1.3  1999/11/22 13:58:00  mdw
 * Document the tweakables.
 *
 * Revision 1.2  1999/11/21 22:14:19  mdw
 * Fix bug.  Improve diagnostic capabilities.
 *
 * Revision 1.1  1999/11/17 18:02:16  mdw
 * New multiprecision integer arithmetic suite.
 *
 */

/*----- Header files ------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <mLib/arena.h>
#include <mLib/exc.h>
#include <mLib/sub.h>

#include "mparena.h"

/*----- Tweakables --------------------------------------------------------*/

/* --- @MPARENA_TRIVIAL@ --- *
 *
 * Make the allocator a passthrough.  It immediately calls the underlying
 * allocation functions rather than attempting to keep track of blocks
 * itself.
 */

/* #define MPARENA_TRIVIAL */

/* --- @MPARENA_DEBUG@ --- *
 *
 * The name of an output trace file to which logging information about the
 * state of arena trees should be written.  If unset, no logging is done.
 */

/* #define MPARENA_DEBUG "mparena.out" */

/*----- Static variables --------------------------------------------------*/

#ifdef MPARENA_DEBUG
  static FILE *debugfp = 0;

#  define MPARENA_OPENFILE do {						\
    if (!debugfp) {							\
      if ((debugfp = fopen(MPARENA_DEBUG, "w")) == 0) {			\
	fprintf(stderr, "couldn't open debug output file\n");		\
	exit(EXIT_FAILURE);						\
      }									\
    }									\
  } while (0)

#endif

/*----- Standard arenas ---------------------------------------------------*/

mparena mparena_global = MPARENA_INIT;
mparena mparena_secure = MPARENA_INIT;

/*----- Main code ---------------------------------------------------------*/

/* --- @tdump@ --- *
 *
 * Arguments:	@mparena_node *n@ = pointer to tree node to dump
 *
 * Returns:	---
 *
 * Use:		Recursively dumps out the allocation tree.
 */

#ifdef MPARENA_DEBUG

static void tdump(mparena_node *n)
{
  if (!n)
    putc('*', debugfp);
  else {
    putc('(', debugfp);
    tdump(n->left);
    fprintf(debugfp, ", %u, ", n->v[0]);
    tdump(n->right);
    putc(')', debugfp);
  }
}

#endif

/* --- @mparena_create@ --- *
 *
 * Arguments:	@mparena *a@ = pointer to arena block
 *
 * Returns:	---
 *
 * Use:		Initializes an MP arena so that blocks can be allocated from
 *		it.
 */

void mparena_create(mparena *a)
{
  a->root = 0;
  a->n = 0;
  a->a = &arena_stdlib;
}

/* --- @mparena_setarena@ --- *
 *
 * Arguments:	@mparena *a@ = pointer to MP arena block
 *		@arena *aa@ = pointer to arena
 *
 * Returns:	---
 *
 * Use:		Sets the underlying arena for an MP arena.
 */

extern void mparena_setarena(mparena *a, arena *aa) { a->a = aa; }

/* --- @mparena_destroy@ --- *
 *
 * Arguments:	@mparena *a@ = pointer to arena block
 *
 * Returns:	---
 *
 * Use:		Frees an MP arena, and all the vectors held within it.  The
 *		blocks which are currently allocated can be freed into some
 *		other arena.
 */

static void tfree(mparena *a, mparena_node *n)
{
  A_FREE(a->a, n->v);
  if (n->left)
    tfree(a, n->left);
  if (n->right)
    tfree(a, n->right);
  DESTROY(n);
}

void mparena_destroy(mparena *a)
{
  tfree(a, a->root);
  a->root = 0;
}

/* --- @mparena_count@ --- *
 *
 * Arguments:	@mparena *a@ = pointer to arena block
 *
 * Returns:	Number of allocated blocks from this arena.
 *
 * Use:		Reports the number of blocks allocated from the arena and not
 *		yet freed.
 */

unsigned mparena_count(mparena *a)
{
  return (a->n);
} 

/* --- @mpalloc@ --- *
 *
 * Arguments:	@mparena *a@ = pointer to arena block
 *		@size_t sz@ = number of digits required
 *
 * Returns:	Pointer to a suitably sized block.
 *
 * Use:		Allocates a lump of data suitable for use as an array of MP
 *		digits.
 */

#ifdef MPARENA_TRIVIAL

mpw *mpalloc(mparena *a, size_t sz)
{
  mpw *v;
  v = A_ALLOC(a->a, MPWS(sz));
  if (!v)
    THROW(EXC_NOMEM);
  return (v);
}

#else

mpw *mpalloc(mparena *a, size_t sz)
{
  mparena_node **nn, *n;
  mpw *v;

  nn = &a->root;

#ifdef MPARENA_DEBUG
  MPARENA_OPENFILE;
  fprintf(debugfp, "alloc %u\n  before: ", sz);
  tdump(a->root); putc('\n', debugfp);
#endif

  /* --- First, find a block which is big enough --- */

again:
  n = *nn;
  if (!n) {
#ifdef MPARENA_DEBUG
    fputs("  failed\n", debugfp);
#endif
    if ((v = A_ALLOC(a->a, MPWS(sz + 1))) == 0)
      THROW(EXC_NOMEM);
    v[0] = sz;
    a->n++;
    return (v + 1);
  }
  if (n->v[0] < sz) {
    nn = &n->right;
    goto again;
  }

  /* --- Now try to find a smaller block which is suitable --- */

  while (n->left && n->left->v[0] >= sz) {
    nn = &n->left;
    n = *nn;
  }

  /* --- If the block we've got is still too large, start digging --- */

  if (n->v[0] > sz * 2) {
    nn = &n->left;
    goto again;
  }

  /* --- I've now found a suitable block --- */

  v = n->v;

  /* --- Remove this node from the tree --- */

  if (!n->left)
    *nn = n->right;
  else if (!n->right)
    *nn = n->left;
  else {
    mparena_node *left = n->left;
    mparena_node *p = *nn = n->right;
    while (p->left)
      p = p->left;
    p->left = left;
  }

#ifdef MPARENA_DEBUG
  fputs("  after: ", debugfp);
  tdump(a->root); putc('\n', debugfp);
#endif

  /* --- Get rid of this node now --- */

  DESTROY(n);
  a->n++;
  return (v + 1);
}

#endif

/* --- @mpfree@ --- *
 *
 * Arguments:	@mparena *a@ = pointer to arena block
 *		@mpw *v@ = pointer to allocated vector
 *
 * Returns:	---
 *
 * Use:		Returns an MP vector to an arena.
 */

#ifdef MPARENA_TRIVIAL

void mpfree(mparena *a, mpw *v)
{
  A_FREE(a->a, v);
}

#else

void mpfree(mparena *a, mpw *v)
{
  mparena_node **nn, *n;
  size_t sz = *--v;

#ifdef MPARENA_DEBUG
  MPARENA_OPENFILE;
  fprintf(debugfp, "free %u\n  before: ", sz);
  tdump(a->root); putc('\n', debugfp);
#endif

  nn = &a->root;
  while (*nn) {
    n = *nn;
    if (n->v[0] > sz)
      nn = &n->left;
    else
      nn = &n->right;
  }

  n = CREATE(mparena_node);
  n->left = n->right = 0;
  n->v = v;
  *nn = n;
  a->n--;

#ifdef MPARENA_DEBUG
  fputs("  after: ", debugfp);
  tdump(a->root); putc('\n', debugfp);
#endif
}

#endif

/*----- That's all, folks -------------------------------------------------*/