[u/mdw/catacomb] / math / mp-mem.c

/* -*-c-*-
 *
 * Memory management for multiprecision numbers
 *
 * (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.
 */

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

#include <mLib/sub.h>


#include "mp.h"

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

/* --- @mp_new@ --- *
 *
 * Arguments:	@size_t sz@ = size of vector required
 *		@unsigned f@ = flags to set
 *
 * Returns:	Pointer to a new MP structure.
 *
 * Use:		Allocates a new multiprecision integer.  The data space is
 *		allocated from either the standard global or secret arena,
 *		depending on the initial flags requested.
 */

mp *mp_new(size_t sz, unsigned f)
{
  mp *m = CREATE(mp);
  m->a = (f & MP_BURN) ? MPARENA_SECURE : MPARENA_GLOBAL;
  m->v = mpalloc(m->a, sz);
  m->vl = m->v + sz;
  m->sz = sz;
  m->f = f & ~(MP_CONST | MP_DESTROYED);
  m->ref = 1;
  return (m);
}

/* --- @mp_create@ --- *
 *
 * Arguments:	@size_t sz@ = size of vector required
 *
 * Returns:	Pointer to pristine new MP structure with enough memory
 *		bolted onto it.
 *
 * Use:		Creates a new multiprecision integer, initially zero.  The
 *		integer has a single reference.
 */

mp *mp_create(size_t sz)
{
  mp *m = CREATE(mp);
  m->v = mpalloc(MPARENA_GLOBAL, sz);
  m->vl = m->v + sz;
  m->sz = sz;
  m->a = MPARENA_GLOBAL;
  m->f = MP_UNDEF;
  m->ref = 1;
  return (m);
}

/* --- @mp_createsecure@ --- *
 *
 * Arguments:	@size_t sz@ = size of vector required
 *
 * Returns:	Pointer to pristine new MP structure with enough memory
 *		bolted onto it.
 *
 * Use:		Creates a new multiprecision integer with indeterminate
 *		contents.  The integer has a single reference.  The integer's
 *		data space is allocated from the secure arena.  Its burn flag
 *		is set.
 */

mp *mp_createsecure(size_t sz)
{
  mp *m = CREATE(mp);
  m->v = mpalloc(MPARENA_SECURE, sz);
  m->vl = m->v + sz;
  m->sz = sz;
  m->a = MPARENA_SECURE;
  m->f = MP_UNDEF | MP_BURN;
  m->ref = 1;
  return (m);
}

/* --- @mp_build@ --- *
 *
 * Arguments:	@mp *m@ = pointer to an MP block to fill in
 *		@mpw *v@ = pointer to a word array
 *		@mpw *vl@ = pointer just past end of array
 *
 * Returns:	---
 *
 * Use:		Creates a multiprecision integer representing some smallish
 *		number.  You must provide storage for the number and dispose
 *		of it when you've finished with it.  The number is marked as
 *		constant while it exists.
 */

void mp_build(mp *m, mpw *v, mpw *vl)
{
  m->v = v;
  m->vl = vl;
  m->sz = vl - v;
  m->a = MPARENA_GLOBAL;
  m->f = MP_CONST;
  m->ref = 1;
}

/* --- @mp_destroy@ --- *
 *
 * Arguments:	@mp *m@ = pointer to a multiprecision integer
 *
 * Returns:	---
 *
 * Use:		Destroys a multiprecision integer. The reference count isn't
 *		checked.  Don't use this function if you don't know what
 *		you're doing: use @mp_drop@ instead.
 */

void mp_destroy(mp *m)
{
  assert(((void)"Destroying a free integer", !(m->f & MP_DESTROYED)));
  assert(((void)"Attempted to destroy a constant", !(m->f & MP_CONST)));
  if (m->f & MP_BURN)
    memset(m->v, 0, MPWS(m->sz));
  mpfree(m->a, m->v);
  m->f |= MP_DESTROYED;
  DESTROY(m);
}

/* --- @mp_copy@ --- *
 *
 * Arguments:	@mp *m@ = pointer to a multiprecision integer
 *
 * Returns:	A copy of the given multiprecision integer.
 *
 * Use:		Copies the given integer.  In fact you just get another
 *		reference to the same old one again.
 */

mp *mp_copy(mp *m) { return MP_COPY(m); }

/* --- @mp_drop@ --- *
 *
 * Arguments:	@mp *m@ = pointer to a multiprecision integer
 *
 * Returns:	---
 *
 * Use:		Drops a reference to an integer which isn't wanted any more.
 *		If there are no more references, the integer is destroyed.
 */

void mp_drop(mp *m) { if (m) MP_DROP(m); }

/* --- @mp_split@ --- *
 *
 * Arguments:	@mp *m@ = pointer to a multiprecision integer
 *
 * Returns:	A reference to the same integer, possibly with a different
 *		address.
 *
 * Use:		Splits off a modifiable version of the integer referred to.
 */

mp *mp_split(mp *m) { MP_SPLIT(m); return (m); }

/* --- @mp_resize@ --- *
 *
 * Arguments:	@mp *m@ = pointer to a multiprecision integer
 *		@size_t sz@ = new size
 *
 * Returns:	---
 *
 * Use:		Changes an integer's size.  The length and value are not
 *		changed.  It is an error to
 */

void mp_resize(mp *m, size_t sz) { MP_RESIZE(m, sz); }

/* --- @mp_ensure@ --- *
 *
 * Arguments:	@mp *m@ = pointer to a multiprecision integer
 *		@size_t sz@ = required length
 *
 * Returns:	---
 *
 * Use:		Changes an integer's length.  If there is not enough space
 *		allocated for the new length then the size is increased.  It
 */

void mp_ensure(mp *m, size_t sz) { MP_ENSURE(m, sz); }

/* --- @mp_dest@ --- *
 *
 * Arguments:	@mp *m@ = a suggested destination integer
 *		@size_t sz@ = size required for result, in digits
 *		@unsigned f@ = various flags
 *
 * Returns:	A pointer to an appropriate destination.
 *
 * Use:		Converts a suggested destination into a real destination with
 *		the required properties.  If the real destination is @d@,
 *		then the following properties will hold:
 *
 *		  * @d@ will have exactly one reference.
 *
 *		  * If @m@ is not @MP_NEW@, then the contents of @m@ will not
 *		    change, unless @f@ has the @MP_UNDEF@ flag set.
 *
 *		  * If @m@ is not @MP_NEW@, then he reference count of @m@ on
 *		    entry is equal to the sum of the counts of @d@ and @m@ on
 *		    exit.
 *
 *		  * The size of @d@ will be at least @sz@.
 *
 *		  * If @f@ has the @MP_BURN@ flag set, then @d@ will be
 *		    allocated from @MPARENA_SECURE@.
 *
 *		Understanding this function is crucial to using Catacomb's
 *		multiprecision integer library effectively.
 */

mp *mp_dest(mp *m, size_t sz, unsigned f)
{
  /* --- If no destination, make one --- */

  if (m == MP_NEWSEC)
    m = mp_new(sz, f | MP_UNDEF | MP_BURN);
  else if (m == MP_NEW)
    m = mp_new(sz, f | MP_UNDEF);
  else {
    size_t len = MP_LEN(m);
    unsigned undef = (m->f | f) & MP_UNDEF;

    /* --- If the value must be preserved, the block can't shrink --- */

    if (!undef && sz < len)
      sz = len;

    /* --- Otherwise check whether the destination is suitable --- */

    if (m->ref > 1 || (m->f & MP_CONST) ||
	sz > m->sz || ((f & ~m->f) & MP_BURN)) {

      /* --- No -- allocate a new buffer --- *
       *
       * The buffer must be secure if (a) the caller requested a secure
       * buffer, or (b) the old buffer is secure and I'm not allowed to
       * discard the old contents.
       */

      mparena *a;
      mpw *v;

      if ((f & MP_BURN) || (!undef && (m->f & MP_BURN)))
	a = MPARENA_SECURE;
      else
	a = MPARENA_GLOBAL;
      v = mpalloc(a, sz);

      /* --- Copy the data over --- */

      if (!undef) {
	memcpy(v, m->v, MPWS(len));
	if (sz - len > 0)
	  memset(v + len, 0, MPWS(sz - len));
      }

      /* --- If @m@ has other references, make a new node --- *
       *
       * Otherwise dispose of the old buffer.
       */

      if (!(m->f & MP_CONST) && m->ref == 1) {
	if (m->f & MP_BURN)
	  memset(m->v, 0, MPWS(m->sz));
	mpfree(m->a, m->v);
      } else {
	mp *mm = CREATE(mp);
	mm->ref = 1;
	mm->f = m->f;
	m->ref--;
	m = mm;
      }

      /* --- Fix up the node --- */

      m->v = v;
      m->vl = v + sz;
      m->sz = sz;
      m->f = ((m->f & ~(MP_CONST | MP_BURN)) |
	      (f & (MP_BURN | MP_UNDEF)));
      m->a = a;
    }

    /* --- If the number is growing in its buffer, fix it up --- */

    else if (sz > len) {
      if (!undef)
	memset(m->vl, 0, MPWS(sz - len));
      m->vl = m->v + sz;
    }
  }

  /* --- Done --- */

  return (m);
}

/*----- That's all, folks -------------------------------------------------*/
Commit	Line	Data
d3409d5e	1	/* --c--
d3409d5e	2	*
d3409d5e	3	* Memory management for multiprecision numbers
	4	*
	5	* (c) 1999 Straylight/Edgeware
	6	*/
	7
45c0fd36	8	/----- Licensing notice --------------------------------------------------
d3409d5e	9	*
	10	* This file is part of Catacomb.
	11	*
	12	* Catacomb is free software; you can redistribute it and/or modify
	13	* it under the terms of the GNU Library General Public License as
	14	* published by the Free Software Foundation; either version 2 of the
	15	* License, or (at your option) any later version.
45c0fd36	16	*
d3409d5e	17	* Catacomb is distributed in the hope that it will be useful,
	18	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	19	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	20	* GNU Library General Public License for more details.
45c0fd36	21	*
d3409d5e	22	* You should have received a copy of the GNU Library General Public
	23	* License along with Catacomb; if not, write to the Free
	24	* Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
	25	* MA 02111-1307, USA.
	26	*/
	27
d3409d5e	28	/----- Header files ------------------------------------------------------/
d3409d5e	29
d34decd2	30	#include <mLib/sub.h>
	31
	32
d3409d5e	33	#include "mp.h"
	34
	35	/----- Main code ---------------------------------------------------------/
	36
d34decd2	37	/* --- @mp_new@ --- *
	38	*
	39	* Arguments: @size_t sz@ = size of vector required
	40	* @unsigned f@ = flags to set
	41	*
	42	* Returns: Pointer to a new MP structure.
	43	*
	44	* Use: Allocates a new multiprecision integer. The data space is
	45	* allocated from either the standard global or secret arena,
	46	* depending on the initial flags requested.
	47	*/
	48
	49	mp *mp_new(size_t sz, unsigned f)
	50	{
	51	mp *m = CREATE(mp);
	52	m->a = (f & MP_BURN) ? MPARENA_SECURE : MPARENA_GLOBAL;
	53	m->v = mpalloc(m->a, sz);
	54	m->vl = m->v + sz;
	55	m->sz = sz;
	56	m->f = f & ~(MP_CONST \| MP_DESTROYED);
	57	m->ref = 1;
	58	return (m);
	59	}
	60
d3409d5e	61	/* --- @mp_create@ --- *
	62	*
	63	* Arguments: @size_t sz@ = size of vector required
	64	*
	65	* Returns: Pointer to pristine new MP structure with enough memory
	66	* bolted onto it.
	67	*
	68	* Use: Creates a new multiprecision integer, initially zero. The
	69	* integer has a single reference.
	70	*/
	71
	72	mp *mp_create(size_t sz)
	73	{
	74	mp *m = CREATE(mp);
d34decd2	75	m->v = mpalloc(MPARENA_GLOBAL, sz);
d3409d5e	76	m->vl = m->v + sz;
d3409d5e	77	m->sz = sz;
d34decd2	78	m->a = MPARENA_GLOBAL;
d3409d5e	79	m->f = MP_UNDEF;
	80	m->ref = 1;
	81	return (m);
	82	}
	83
d34decd2	84	/* --- @mp_createsecure@ --- *
	85	*
	86	* Arguments: @size_t sz@ = size of vector required
	87	*
	88	* Returns: Pointer to pristine new MP structure with enough memory
	89	* bolted onto it.
	90	*
	91	* Use: Creates a new multiprecision integer with indeterminate
	92	* contents. The integer has a single reference. The integer's
	93	* data space is allocated from the secure arena. Its burn flag
	94	* is set.
	95	*/
	96
	97	mp *mp_createsecure(size_t sz)
	98	{
45c0fd36	99	mp *m = CREATE(mp);
d34decd2	100	m->v = mpalloc(MPARENA_SECURE, sz);
	101	m->vl = m->v + sz;
	102	m->sz = sz;
	103	m->a = MPARENA_SECURE;
	104	m->f = MP_UNDEF \| MP_BURN;
	105	m->ref = 1;
	106	return (m);
	107	}
	108
d3409d5e	109	/* --- @mp_build@ --- *
	110	*
	111	* Arguments: @mp *m@ = pointer to an MP block to fill in
	112	* @mpw *v@ = pointer to a word array
	113	* @mpw *vl@ = pointer just past end of array
	114	*
	115	* Returns: ---
	116	*
	117	* Use: Creates a multiprecision integer representing some smallish
	118	* number. You must provide storage for the number and dispose
	119	* of it when you've finished with it. The number is marked as
	120	* constant while it exists.
	121	*/
	122
	123	void mp_build(mp m, mpw v, mpw *vl)
	124	{
	125	m->v = v;
	126	m->vl = vl;
	127	m->sz = vl - v;
78ec50fa	128	m->a = MPARENA_GLOBAL;
d3409d5e	129	m->f = MP_CONST;
	130	m->ref = 1;
	131	}
	132
	133	/* --- @mp_destroy@ --- *
	134	*
	135	* Arguments: @mp *m@ = pointer to a multiprecision integer
	136	*
	137	* Returns: ---
	138	*
	139	* Use: Destroys a multiprecision integer. The reference count isn't
	140	* checked. Don't use this function if you don't know what
	141	* you're doing: use @mp_drop@ instead.
	142	*/
	143
	144	void mp_destroy(mp *m)
	145	{
0e895689	146	assert(((void)"Destroying a free integer", !(m->f & MP_DESTROYED)));
0e895689	147	assert(((void)"Attempted to destroy a constant", !(m->f & MP_CONST)));
d3409d5e	148	if (m->f & MP_BURN)
d3409d5e	149	memset(m->v, 0, MPWS(m->sz));
d34decd2	150	mpfree(m->a, m->v);
0e895689	151	m->f \|= MP_DESTROYED;
d3409d5e	152	DESTROY(m);
	153	}
	154
	155	/* --- @mp_copy@ --- *
	156	*
	157	* Arguments: @mp *m@ = pointer to a multiprecision integer
	158	*
	159	* Returns: A copy of the given multiprecision integer.
	160	*
	161	* Use: Copies the given integer. In fact you just get another
	162	* reference to the same old one again.
	163	*/
	164
	165	mp mp_copy(mp m) { return MP_COPY(m); }
	166
	167	/* --- @mp_drop@ --- *
	168	*
	169	* Arguments: @mp *m@ = pointer to a multiprecision integer
	170	*
	171	* Returns: ---
	172	*
	173	* Use: Drops a reference to an integer which isn't wanted any more.
	174	* If there are no more references, the integer is destroyed.
	175	*/
	176
f1140c41	177	void mp_drop(mp *m) { if (m) MP_DROP(m); }
d3409d5e	178
	179	/* --- @mp_split@ --- *
	180	*
	181	* Arguments: @mp *m@ = pointer to a multiprecision integer
	182	*
	183	* Returns: A reference to the same integer, possibly with a different
	184	* address.
	185	*
	186	* Use: Splits off a modifiable version of the integer referred to.
	187	*/
	188
24521163	189	mp mp_split(mp m) { MP_SPLIT(m); return (m); }
d3409d5e	190
	191	/* --- @mp_resize@ --- *
	192	*
	193	* Arguments: @mp *m@ = pointer to a multiprecision integer
	194	* @size_t sz@ = new size
	195	*
	196	* Returns: ---
	197	*
d34decd2	198	* Use: Changes an integer's size. The length and value are not
45c0fd36	199	* changed. It is an error to
d3409d5e	200	*/
d3409d5e	201
24521163	202	void mp_resize(mp *m, size_t sz) { MP_RESIZE(m, sz); }
d3409d5e	203
	204	/* --- @mp_ensure@ --- *
	205	*
	206	* Arguments: @mp *m@ = pointer to a multiprecision integer
d34decd2	207	* @size_t sz@ = required length
d3409d5e	208	*
	209	* Returns: ---
	210	*
d34decd2	211	* Use: Changes an integer's length. If there is not enough space
d34decd2	212	* allocated for the new length then the size is increased. It
d3409d5e	213	*/
d3409d5e	214
24521163	215	void mp_ensure(mp *m, size_t sz) { MP_ENSURE(m, sz); }
d3409d5e	216
d34decd2	217	/* --- @mp_dest@ --- *
d3409d5e	218	*
d34decd2	219	* Arguments: @mp *m@ = a suggested destination integer
	220	* @size_t sz@ = size required for result, in digits
	221	* @unsigned f@ = various flags
	222	*
	223	* Returns: A pointer to an appropriate destination.
	224	*
	225	* Use: Converts a suggested destination into a real destination with
	226	* the required properties. If the real destination is @d@,
	227	* then the following properties will hold:
d3409d5e	228	*
d34decd2	229	* * @d@ will have exactly one reference.
d3409d5e	230	*
d34decd2	231	* * If @m@ is not @MP_NEW@, then the contents of @m@ will not
	232	* change, unless @f@ has the @MP_UNDEF@ flag set.
	233	*
	234	* * If @m@ is not @MP_NEW@, then he reference count of @m@ on
	235	* entry is equal to the sum of the counts of @d@ and @m@ on
	236	* exit.
	237	*
	238	* * The size of @d@ will be at least @sz@.
	239	*
	240	* * If @f@ has the @MP_BURN@ flag set, then @d@ will be
	241	* allocated from @MPARENA_SECURE@.
	242	*
	243	* Understanding this function is crucial to using Catacomb's
	244	* multiprecision integer library effectively.
d3409d5e	245	*/
d3409d5e	246
d34decd2	247	mp mp_dest(mp m, size_t sz, unsigned f)
	248	{
	249	/* --- If no destination, make one --- */
	250
	251	if (m == MP_NEWSEC)
	252	m = mp_new(sz, f \| MP_UNDEF \| MP_BURN);
	253	else if (m == MP_NEW)
	254	m = mp_new(sz, f \| MP_UNDEF);
	255	else {
	256	size_t len = MP_LEN(m);
	257	unsigned undef = (m->f \| f) & MP_UNDEF;
	258
	259	/* --- If the value must be preserved, the block can't shrink --- */
	260
	261	if (!undef && sz < len)
	262	sz = len;
	263
	264	/* --- Otherwise check whether the destination is suitable --- */
	265
	266	if (m->ref > 1 \|\| (m->f & MP_CONST) \|\|
53cbeae3	267	sz > m->sz \|\| ((f & ~m->f) & MP_BURN)) {
d34decd2	268
	269	/* --- No -- allocate a new buffer --- *
	270	*
	271	* The buffer must be secure if (a) the caller requested a secure
	272	* buffer, or (b) the old buffer is secure and I'm not allowed to
	273	* discard the old contents.
	274	*/
45c0fd36	275
d34decd2	276	mparena *a;
	277	mpw *v;
	278
	279	if ((f & MP_BURN) \|\| (!undef && (m->f & MP_BURN)))
	280	a = MPARENA_SECURE;
	281	else
	282	a = MPARENA_GLOBAL;
	283	v = mpalloc(a, sz);
	284
	285	/* --- Copy the data over --- */
	286
	287	if (!undef) {
	288	memcpy(v, m->v, MPWS(len));
	289	if (sz - len > 0)
	290	memset(v + len, 0, MPWS(sz - len));
	291	}
	292
	293	/* --- If @m@ has other references, make a new node --- *
	294	*
	295	* Otherwise dispose of the old buffer.
	296	*/
	297
	298	if (!(m->f & MP_CONST) && m->ref == 1) {
	299	if (m->f & MP_BURN)
	300	memset(m->v, 0, MPWS(m->sz));
	301	mpfree(m->a, m->v);
	302	} else {
	303	mp *mm = CREATE(mp);
	304	mm->ref = 1;
	305	mm->f = m->f;
	306	m->ref--;
	307	m = mm;
	308	}
	309
	310	/* --- Fix up the node --- */
	311
	312	m->v = v;
	313	m->vl = v + sz;
	314	m->sz = sz;
	315	m->f = ((m->f & ~(MP_CONST \| MP_BURN)) \|
	316	(f & (MP_BURN \| MP_UNDEF)));
	317	m->a = a;
	318	}
	319
	320	/* --- If the number is growing in its buffer, fix it up --- */
	321
	322	else if (sz > len) {
	323	if (!undef)
	324	memset(m->vl, 0, MPWS(sz - len));
	325	m->vl = m->v + sz;
	326	}
	327	}
	328
	329	/* --- Done --- */
	330
	331	return (m);
	332	}
d3409d5e	333
d3409d5e	334	/----- That's all, folks -------------------------------------------------/