zpoly.h

FIR2LIFT is a program to factor a wavelet FIR filter pair into lifting steps.

/*
FILE : ZPOLY.H

Routines to handle Laurent polynomials (in z). These differ from normal 
polynomials in that they can have negative exponents.

(C) C. Valens

Created     : 10/09/1999
Last update : 25/09/1999
*/

/*
IMPORTANT NOTES
===============
- Read the comments provided with the functions for more information.
- A zpoly should ALWAYS be ordered, increasing or decreasing in exponent.
  The ordering is NEVER checked and is thus always assumed to be correct.
- All coefficients are doubles. To compare them an error margin EPSILON is 
  used. Beware.
*/


#ifndef __ZPOLY_H__
#define __ZPOLY_H__


/*
 * Tolerated error, i.e. absolute values smaller than EPSILON are treated
 * as being equal to 0. This value is ALWAYS used when zpoly coefficients
 * are being compared.
 */
#define EPSILON  0.0000001


/*
 * Define a zpoly as a ordered linked list of zpoly elements, where
 * each element consists of a power (exponent) and a coefficient.
 */
typedef struct __zpoly_element {
  int    power;
  double coeff;
  struct __zpoly_element *next;
} zpoly;


/*
 * The zpoly_pair is used to hold quotients and remainders.
 */
typedef struct __zpoly_pair {
  zpoly *p1;
  zpoly *p2;
} zpoly_pair;


/*
 * Create one element of a zpoly.
 */
zpoly *zpoly_create(const int power, const double coeff);

/*
 * Destroy an entire zpoly.
 */
void zpoly_destroy(zpoly *poly);

/*
 * Write a zpoly to the output stream.
 */
void zpoly_write(zpoly *poly);

/*
 * Write a zpoly to the output stream, including a carriage return.
 * If show_degree==1 the degree of the zpoly is also written.
 */
void zpoly_writeln(zpoly *poly, const int show_degree);

/*
 * Create a copy of a zpoly.
 */
zpoly *zpoly_copy(zpoly *poly);

/*
 * Reverse the ordering of a zpoly.
 * If reverse_time==1 all powers will be negated.
 */
zpoly *zpoly_reverse(zpoly *poly, const int reverse_time);

/*
 * Create a reversed ordered copy of a zpoly.
 * If reverse_time==1 all powers will be negated.
 */
zpoly *zpoly_copy_reverse(zpoly *poly, const int reverse_time);

/*
 * Returns the degree of a zpoly:
 *
 *   degree = abs(highest_power-lowest_power).
 */
int zpoly_degree(zpoly *poly);

/*
 * Returns 1 if poly1 is identical to poly2, 0 if not.
 */
int zpoly_equal(zpoly *poly1, zpoly *poly2);

/*
 * Returns 1 if poly1 is equivalent with the zero zpoly, 0 if not.
 */
int zpoly_equals_zero(zpoly *poly);

/*
 * Create a zpoly that holds poly1+poly2
 */
zpoly *zpoly_add(zpoly *poly1, zpoly *poly2);

/*
 * Create a zpoly that holds poly1+poly2 and destroys poly1.
 * Usage:
 *
 *   poly1 = zpoly_add_to(poly1,poly2);
 */
zpoly *zpoly_add_to(zpoly *poly1, zpoly *poly2);

/*
 * Adds an element to polynomial poly.
 * usage : poly1 = polynomial_add_to(poly,exponent,coefficient);
 */
zpoly *zpoly_add_element_to(zpoly *poly, int power, double coeff);

/*
 * Create a zpoly that holds poly1-poly2
 */
zpoly *zpoly_sub(zpoly *poly1, zpoly *poly2);

/*
 * Create a zpoly that holds poly1-poly2 and destroys poly1.
 * Usage:
 *
 *   poly1 = zpoly_sub_from(poly1,poly2);
 */
zpoly *zpoly_sub_from(zpoly *poly1, zpoly *poly2);

/*
 * Multiply all coefficients of poly1 by a constant s.
 */
zpoly *zpoly_scale(zpoly *poly1, const double s);

/*
 * Create a zpoly that holds poly1zpoly *poly2
 */
zpoly *zpoly_mul(zpoly *poly1, zpoly *poly2);

/*
 * Create a zpoly that holds poly1zpoly *poly2 and destroys poly1.
 * Usage:
 *
 *   poly1 = zpoly_mul_by(poly1,poly2);
 */
zpoly *zpoly_mul_by(zpoly *poly1, zpoly *poly2);

/*
 * Create a zpoly pair that holds (poly1 DIV poly2) and (poly1 MOD poly2)
 * zpoly_pair.p1 holds the quotient (DIV),
 * zpoly_pair.p2 holds the remainder (MOD).
 *
 * If match==0 the first powers of poly1 are matched,
 * else the last powers of poly1 are matched.
 */
zpoly_pair zpoly_divmod(zpoly *poly1, zpoly *poly2, const int match);

/*
 * Create a zpoly pair that holds one step of (poly1 DIV poly2) and
 * (poly1 MOD poly2). The first power of poly1 is matched.
 * zpoly_pair.p1 holds the quotient (DIV),
 * zpoly_pair.p2 holds the remainder (MOD).
 *
 * This function is necessary for finding all possible divisions.
 */
zpoly_pair zpoly_divmod_fp_step(zpoly *poly1, zpoly *poly2);

/*
 * Create a zpoly pair that holds one step of (poly1 DIV poly2) and
 * (poly1 MOD poly2). The last power of poly1 is matched.
 * zpoly_pair.p1 holds the quotient (DIV),
 * zpoly_pair.p2 holds the remainder (MOD).
 *
 * This function is necessary for finding all possible divisions.
 */
zpoly_pair zpoly_divmod_lp_step(zpoly *poly1, zpoly *poly2);


#endif /* __ZPOLY_H__ */