sprint.c

牛顿插值方法求解多项式的系数

/*
 * (c) Copyright 1992, 1993 by Panagiotis Tsirigotis
 * All rights reserved.  The file named COPYRIGHT specifies the terms
 * and conditions for redistribution.
 */


#include "config.h"
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#include "sio.h"
#include "impl.h"
#include "libportable.h"

typedef long long 			wide_int ;
typedef unsigned long long 		u_wide_int ;
typedef int 				bool_int ;

static char *conv_10( wide_int num, bool_int is_unsigned, bool_int *is_negative, char *buf_end, int *len );

#define S_NULL_LEN 			6
static char S_NULL[S_NULL_LEN+1] = "(null)";

#define FLOAT_DIGITS			6
#define MAX_FLOAT_DIGITS		17
#define EXPONENT_LENGTH			10

/*
 * NUM_BUF_SIZE is the size of the buffer used for arithmetic conversions
 *
 * XXX: this is a magic number; do not decrease it
 */
#define NUM_BUF_SIZE			512

/*
 * The INS_CHAR macro inserts a character in the buffer and writes
 * the buffer back to disk if necessary
 * It uses the char pointers sp and bep:
 * 	sp points to the next available character in the buffer
 * 	bep points to the end-of-buffer+1
 * While using this macro, note that the nextb pointer is NOT updated.
 *
 * No I/O is performed if fd is not positive. Negative fd values imply
 * conversion with the output directed to a string. Excess characters
 * are discarded if the string overflows.
 *
 * NOTE: Evaluation of the c argument should not have any side-effects
 */
#define INS_CHAR( c, sp, bep, odp, cc, fd )			\
{								\
	if ( sp < bep )						\
	{							\
		*sp++ = c ;					\
		cc++ ;						\
	}							\
	else							\
	{							\
		if ( fd >= 0 )					\
		{						\
			odp->nextb = sp ;			\
			if ( __sio_writef( odp, fd ) != bep - odp->start ) \
				return( ( cc != 0 ) ? cc : SIO_ERR ) ;	\
			sp = odp->nextb ;			\
			*sp++ = c ;				\
			cc++ ;					\
		}						\
	}							\
	if ( __SIO_MUST_FLUSH( *odp, c ) && fd >= 0 )		\
	{							\
		int b_in_buffer = sp - odp->start ;		\
								\
		odp->nextb = sp ;				\
		if ( __sio_writef( odp, fd ) != b_in_buffer )	\
			return( cc ) ;				\
		sp = odp->nextb ;				\
	}							\
}



#define NUM( c )			( c - '0' )

#define STR_TO_DEC( str, num )						\
	num = NUM( *str++ ) ;						\
	while ( isdigit( *str ) )					\
	{								\
		num *= 10 ;						\
		num += NUM( *str++ ) ;					\
	}

/*
 * This macro does zero padding so that the precision
 * requirement is satisfied. The padding is done by
 * adding '0's to the left of the string that is going
 * to be printed.
 */
#define FIX_PRECISION( adjust, precision, s, s_len )			\
	if ( adjust )							\
		while ( s_len < precision && s_len < NUM_BUF_SIZE - 2 )	\
		{							\
			*--s = '0' ;					\
			s_len++ ;					\
		}

/*
 * Macro that does padding. The padding is done by printing
 * the character ch.
 */
#define PAD( width, len, ch )						\
	do								\
	{								\
		INS_CHAR( ch, sp, bep, odp, cc, fd ) ;			\
		width-- ;						\
	} while ( width > len )

/*
 * Sprint is the equivalent of printf for SIO.
 * It returns the # of chars written
 * Assumptions:
 *     - all floating point arguments are passed as doubles
 */
/* VARARGS2 */
int Sprint( int fd, const char *fmt, ...) 
{
	__sio_descriptor_t *dp ;
	__sio_od_t *odp ;
	int cc ;
	va_list ap ;

	if( sio_setup( fd, &dp, __SIO_OUTPUT_STREAM ) == SIO_ERR )
		return( SIO_ERR );
	odp = ODP( dp ) ;

	va_start( ap, fmt ) ;
	cc = __sio_converter( odp, fd, fmt, ap ) ;
	va_end( ap ) ;
	return( cc ) ;
}


/*
 * This is the equivalent of vfprintf for SIO
 */
int Sprintv( int fd, const char *fmt, va_list ap)
{
	__sio_descriptor_t *dp ;
	__sio_od_t *odp ;

	if( sio_setup( fd, &dp, __SIO_OUTPUT_STREAM ) == SIO_ERR )
		return( SIO_ERR );
	odp = ODP( dp ) ;
	return( __sio_converter( odp, fd, fmt, ap ) ) ;
}


/*
 * Convert a floating point number to a string formats 'f', 'e' or 'E'.
 * The result is placed in buf, and len denotes the length of the string
 * The sign is returned in the is_negative argument (and is not placed
 * in buf).
 */
static char *conv_fp( char format, double num, boolean_e add_dp, 
   int precision, bool_int *is_negative, char buf[], int *len )
	/* always add decimal point if YES */
{
	char *s = buf ;
	char *p = NULL ;
	int decimal_point ;
		
	if ( precision > MAX_FLOAT_DIGITS )
		precision = MAX_FLOAT_DIGITS ;

	if ( format == 'f' )
		p = (char *)fcvt( num, precision, &decimal_point, is_negative ) ;
	else /* either e or E format */
		p = (char *)ecvt( num, precision+1, &decimal_point, is_negative ) ;

	/*
	 * Check for Infinity and NaN
	 */
	if ( isalpha( *p ) )
	{
		*len = strlen( strcpy( buf, p ) ) ;
		*is_negative = FALSE ;
		return( buf ) ;
	}
	
	if ( format == 'f' )
		if ( decimal_point <= 0 )
		{
			*s++ = '0' ;
			if ( precision > 0 )
			{
				*s++ = '.' ;
				while ( decimal_point++ < 0 )
					*s++ = '0' ;
			}
			else if ( add_dp )
				*s++ = '.' ;
		}
		else
		{
			while ( decimal_point-- > 0 )
				*s++ = *p++ ;
			if ( precision > 0 || add_dp ) *s++ = '.' ;
		}
	else
	{
		*s++ = *p++ ;
		if ( precision > 0 || add_dp ) *s++ = '.' ;
	}

	/*
	 * copy the rest of p, the NUL is NOT copied
	 */
	while ( *p ) *s++ = *p++ ;			
	
	if ( format != 'f' )
	{
		char temp[ EXPONENT_LENGTH ] ;		/* for exponent conversion */
		int t_len ;
		bool_int exponent_is_negative ;

		*s++ = format ;		/* either e or E */
		decimal_point-- ;
		if ( decimal_point != 0 )
		{
			p = conv_10( (wide_int)decimal_point, FALSE, &exponent_is_negative,
					&temp[ EXPONENT_LENGTH ], &t_len ) ;
			*s++ = exponent_is_negative ? '-' : '+' ;
			
			/*
			 * Make sure the exponent has at least 2 digits
			 */
			if ( t_len == 1 )
				*s++ = '0' ;
			while ( t_len-- ) *s++ = *p++ ;
		}
		else
		{
			*s++ = '+' ;
			*s++ = '0' ;
			*s++ = '0' ;
		}
	}

	*len = s - buf ;
	return( buf ) ;
}


/*
 * Convert num to a base X number where X is a power of 2. nbits determines X.
 * For example, if nbits is 3, we do base 8 conversion
 * Return value:
 *			a pointer to a string containing the number
 *
 * The caller provides a buffer for the string: that is the buf_end argument
 * which is a pointer to the END of the buffer + 1 (i.e. if the buffer
 * is declared as buf[ 100 ], buf_end should be &buf[ 100 ])
 */
static char *conv_p2( u_wide_int num, int nbits, char format, char *buf_end, int *len )
{
	int mask = ( 1 << nbits ) - 1 ;
	char *p = buf_end ;
	static const char low_digits[] = "0123456789abcdef" ;
	static const char upper_digits[] = "0123456789ABCDEF" ;
	const char *digits = ( format == 'X' ) ? upper_digits : low_digits ;

	do
	{
		*--p = digits[ num & mask ] ;
		num >>= nbits ;
	}
	while( num ) ;

	*len = buf_end - p ;
	return( p ) ;
}

/*
 * Convert num to its decimal format.
 * Return value:
 *      - a pointer to a string containing the number (no sign)
 *	- len contains the length of the string
 *	- is_negative is set to TRUE or FALSE depending on the sign
 *		  of the number (always set to FALSE if is_unsigned is TRUE)
 *
 * The caller provides a buffer for the string: that is the buf_end argument
 * which is a pointer to the END of the buffer + 1 (i.e. if the buffer
 * is declared as buf[ 100 ], buf_end should be &buf[ 100 ])
 */
static char *conv_10( wide_int num, bool_int is_unsigned, bool_int *is_negative, char *buf_end, int *len )
{
	char *p = buf_end ;
	u_wide_int magnitude ;

	if ( is_unsigned )
	{
		magnitude = (u_wide_int) num ;
		*is_negative = FALSE ;
	}
	else
	{
		*is_negative = ( num < 0 ) ;

		/*
		 * On a 2's complement machine, negating the most negative integer 
		 * results in a number that cannot be represented as a signed integer.
		 * Here is what we do to obtain the number's magnitude:
		 *		a. add 1 to the number
		 *		b. negate it (becomes positive)
		 *		c. convert it to unsigned
		 *		d. add 1
		 */
		if ( *is_negative )
		{
			wide_int t = num + 1 ;

			magnitude = ( (u_wide_int) -t ) + 1 ;
		}
		else
			magnitude = (u_wide_int) num ;
	}

	/*
	 * We use a do-while loop so that we write at least 1 digit 
	 */
	do
	{
		u_wide_int new_magnitude = magnitude / 10 ;

		*--p = magnitude - new_magnitude*10 + '0' ;
		magnitude = new_magnitude ;
	}
	while ( magnitude ) ;
	
	*len = buf_end - p ;
	return( p ) ;
}


/*
 * Do format conversion placing the output in odp.
 * Note: we do not support %n for security reasons.
 */
int __sio_converter( __sio_od_t *odp, int fd, const char *fmt, va_list ap )
{
	char *sp = NULL;
	char *bep = NULL;
	int cc = 0 ;
	int i ;

	char *s = NULL;
	char *q = NULL;
	int s_len ;

	int min_width = 0 ;
	int precision = 0 ;
	enum { LEFT, RIGHT } adjust ;
	char pad_char ;
	char prefix_char ;

	double fp_num ;
	wide_int i_num = 0 ;
	u_wide_int ui_num ;

	char num_buf[ NUM_BUF_SIZE ] ;
	char char_buf[ 2 ] ;		/* for printing %% and %<unknown> */