Fix bug dividing small things by large ones.

[u/mdw/catacomb] / field.h

/* -*-c-*-
 *
 * $Id: field.h,v 1.3 2002/01/13 13:48:44 mdw Exp $
 *
 * Definitions for field arithmetic
 *
 * (c) 2000 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: field.h,v $
 * Revision 1.3  2002/01/13 13:48:44  mdw
 * Further progress.
 *
 * Revision 1.2  2001/05/07 17:30:13  mdw
 * Add an internal-representation no-op function.
 *
 * Revision 1.1  2001/04/29 18:12:33  mdw
 * Prototype version.
 *
 */

#ifndef CATACOMB_FIELD_H
#define CATACOMB_FIELD_H

#ifdef __cplusplus
  extern "C" {
#endif

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

#ifndef CATACOMB_MP_H
#  include "mp.h"
#endif

/*----- Data structures ---------------------------------------------------*/

typedef struct field {
  const struct field_ops *ops;		/* Field operations */
  mp *zero, *one;			/* Identities in the field */
} field;

typedef struct field_ops {

  /* --- Universal operations --- */

  void (*destroy)(field */*f*/);

  mp *(*in)(field */*f*/, mp */*d*/, mp */*x*/);
  mp *(*out)(field */*f*/, mp */*d*/, mp */*x*/);

  mp *(*neg)(field */*f*/, mp */*d*/, mp */*x*/);
  mp *(*add)(field */*f*/, mp */*d*/, mp */*x*/, mp */*y*/);
  mp *(*sub)(field */*f*/, mp */*d*/, mp */*x*/, mp */*y*/);
  mp *(*mul)(field */*f*/, mp */*d*/, mp */*x*/, mp */*y*/);
  mp *(*sqr)(field */*f*/, mp */*d*/, mp */*x*/);
  mp *(*inv)(field */*f*/, mp */*d*/, mp */*x*/);
  mp *(*reduce)(field */*f*/, mp */*d*/, mp */*x*/);

  /* --- Operations for prime fields only --- */

  mp *(*dbl)(field */*f*/, mp */*d*/, mp */*x*/);
  mp *(*tpl)(field */*f*/, mp */*d*/, mp */*x*/);
  mp *(*sqrt)(field */*f*/, mp */*d*/, mp */*x*/);

} field_ops;

#define F_DESTROY(f)		(f)->ops->destroy((f))

#define F_IN(f, d, x)		(f)->ops->in((f), (d), (x))
#define F_OUT(f, d, x)		(f)->ops->out((f), (d), (x))
#define F_NEG(f, d, x)		(f)->ops->neg((f), (d), (x))
#define F_ADD(f, d, x, y)	(f)->ops->add((f), (d), (x), (y))
#define F_SUB(f, d, x, y)	(f)->ops->sub((f), (d), (x), (y))
#define F_MUL(f, d, x, y)	(f)->ops->mul((f), (d), (x), (y))
#define F_SQR(f, d, x)		(f)->ops->sqr((f), (d), (x))
#define F_INV(f, d, x)		(f)->ops->inv((f), (d), (x))
#define F_REDUCE(f, d, x)	(f)->ops->reduce((f), (d), (x))

#define F_DBL(f, d, x)		(f)->ops->dbl((f), (d), (x))
#define F_TPL(f, d, x)		(f)->ops->tpl((f), (d), (x))
#define F_SQRT(f, d, x)		(f)->ops->sqrt((f), (d), (x))

/*----- Helpful field operations ------------------------------------------*/

/* --- @field_id@ --- *
 *
 * Arguments:	@field *f@ = pointer to a field
 *		@mp *d@ = a destination element
 *		@mp *x@ = a source element
 *
 * Returns:	The result element.
 *
 * Use:		An identity operation which can be used if your field has no
 *		internal representation.
 */

extern mp *field_id(field */*f*/, mp */*d*/, mp */*x*/);

/*----- Creating fields ---------------------------------------------------*/

/* --- @field_prime@ --- *
 *
 * Arguments:	@mp *p@ = the characteristic of the field
 *
 * Returns:	A pointer to the field.
 *
 * Use:		Creates a field structure for a prime field of size %$p$%,
 *		using Montgomery reduction for arithmetic.
 */

extern field *field_prime(mp */*p*/);

/* --- @field_binpoly@ --- *
 *
 * Arguments:	@mp *p@ = an irreducible polynomial over %$\gf{2}$%
 *
 * Returns:	A pointer to the field.
 *
 * Use:		Creates a field structure for a binary field using naive
 *		arithmetic.
 */

extern field *field_binpoly(mp */*p*/);

/* --- @field_binsparsepoly@ --- *
 *
 * Arguments:	@unsigned deg@ = the degree of the field polynomial
 *		@const unsigned *c@ = degrees of nonzero coefficients
 *
 * Returns:	A pointer to the field.
 *
 * Use:		Creates a field structure for a binary field taking advantage
 *		of the sparseness of the given polynomial to improve
 *		reduction performance.
 */

extern field *field_binsparsepoly(unsigned /*deg*/, const unsigned */*c*/);

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

#ifdef __cplusplus
  }
#endif

#endif