From aff5e31c80f1b256a42d184ce76cd2cdd83065d0 Mon Sep 17 00:00:00 2001 From: Cedric Bastoul Date: Wed, 22 Jan 2003 13:53:40 +0100 Subject: [PATCH] piplib 1.2 --- Makefile.in | 55 +-- README | 19 +- configure.in | 9 +- doc/pip.ps | 232 ++++++------- example/Makefile | 6 +- example/example.c | 1 - include/piplib/funcall.h | 12 + include/piplib/piplib.h | 21 +- include/piplib/piplib32.h | 12 + include/piplib/piplib64.h | 12 + include/piplib/piplibMP.h | 12 + include/piplib/sol.h | 36 +- include/piplib/tab.h | 12 + include/piplib/type.h | 13 +- source/integrer.c | 190 ++++++++++- source/integrerMP.c | 345 ------------------- source/maind.c | 110 +++--- source/maindMP.c | 250 -------------- source/piplib.c | 168 ++++++++- source/piplibMP.c | 573 ------------------------------- source/sol.c | 206 +++++++++++- source/solMP.c | 692 -------------------------------------- source/tab.c | 146 +++++++- source/tabMP.c | 301 ----------------- source/{traiterMP.c => traiter.c} | 496 +++++++++++++++++++++------ test/boulet.dat | 3 +- test/makefile | 3 +- 27 files changed, 1378 insertions(+), 2557 deletions(-) delete mode 100644 source/integrerMP.c delete mode 100644 source/maindMP.c delete mode 100644 source/piplibMP.c delete mode 100644 source/solMP.c delete mode 100644 source/tabMP.c rename source/{traiterMP.c => traiter.c} (54%) diff --git a/Makefile.in b/Makefile.in index a655fb8..8e85112 100644 --- a/Makefile.in +++ b/Makefile.in @@ -93,19 +93,29 @@ CFLAGS = -c $(INCFLAGS) -fomit-frame-pointer -O2 $(EXTRA_FLAGS) $(DFLAGS) # *****************************************************************************/ -OBJ = $(PIPLIB_OBJ)/maind.o $(PIPLIB_OBJ)/piplib.o $(PIPLIB_OBJ)/integrer.o \ - $(PIPLIB_OBJ)/tab.o $(PIPLIB_OBJ)/traiter.o $(PIPLIB_OBJ)/sol.o +# objects for libraries making +OBJL = $(PIPLIB_OBJ)/piplib.o $(PIPLIB_OBJ)/integrer.o $(PIPLIB_OBJ)/tab.o \ + $(PIPLIB_OBJ)/traiter.o $(PIPLIB_OBJ)/sol.o + +# objects for software making +OBJ = $(PIPLIB_OBJ)/maind.o $(OBJL) all : $(TO_BUILD:%=%all) $(INT_BITS)all : + @echo "-----" + @echo "Making all for" $(INT_BITS) "bits version." $(MAKE) "BITS=$(INT_BITS)" "DFLAGS=$(INT_DFLAGS)" tobuild $(LONG_BITS)all : + @echo "-----" + @echo "Making all for" $(LONG_BITS) "bits version." $(MAKE) "BITS=$(LONG_BITS)" "DFLAGS=$(LONG_DFLAGS)" tobuild $(MP_BITS)all : - $(MAKE) "BITS=$(MP_BITS)" "DFLAGS=$(MP_DFLAGS)" "MP_SUF=MP" tobuild + @echo "-----" + @echo "Making all for" $(MP_BITS) "version." + $(MAKE) "BITS=$(MP_BITS)" "DFLAGS=$(MP_DFLAGS)" tobuild tobuild : $(PACKAGES) @@ -119,7 +129,7 @@ piplibshared : $(PIPLIB_OBJ) $(OBJ) @echo " /*-----------------------------------------------*" @echo " * MAKING PipLib (shared) *" @echo " *-----------------------------------------------*/" - $(LD) $(OBJ) -o $(PIPLIB_OBJ)/libpiplib$(BITS).$(SHEXT).$(VERSION) \ + $(LD) $(OBJL) -o $(PIPLIB_OBJ)/libpiplib$(BITS).$(SHEXT).$(VERSION) \ -lc -shared -fPIC $(LDFLAGS) $(LDCONFIG) @@ -127,35 +137,32 @@ piplibstatic: $(PIPLIB_OBJ) $(OBJ) @echo " /*-----------------------------------------------*" @echo " * MAKING PipLib (static lib) *" @echo " *-----------------------------------------------*/" - $(AR) q $(PIPLIB_OBJ)/libpiplib$(BITS).a.$(VERSION) $(OBJ) + $(AR) q $(PIPLIB_OBJ)/libpiplib$(BITS).a.$(VERSION) $(OBJL) $(RANLIB) $(PIPLIB_OBJ)/libpiplib$(BITS).a.$(VERSION) -$(PIPLIB_OBJ)/piplib.o : $(PIPLIB_SRC)/piplib$(MP_SUF).c \ - $(PIPLIB_INC)/piplib/piplib.h - $(CC) $(CFLAGS) $(PIPLIB_SRC)/piplib$(MP_SUF).c \ +$(PIPLIB_OBJ)/piplib.o : $(PIPLIB_SRC)/piplib.c $(PIPLIB_INC)/piplib/piplib.h + $(CC) $(CFLAGS) $(PIPLIB_SRC)/piplib.c \ -o $(PIPLIB_OBJ)/piplib.o -$(PIPLIB_OBJ)/integrer.o : $(PIPLIB_SRC)/integrer$(MP_SUF).c \ +$(PIPLIB_OBJ)/integrer.o : $(PIPLIB_SRC)/integrer.c \ $(PIPLIB_INC)/piplib/piplib.h - $(CC) $(CFLAGS) $(PIPLIB_SRC)/integrer$(MP_SUF).c \ + $(CC) $(CFLAGS) $(PIPLIB_SRC)/integrer.c \ -o $(PIPLIB_OBJ)/integrer.o -$(PIPLIB_OBJ)/maind.o : $(PIPLIB_SRC)/maind$(MP_SUF).c \ - $(PIPLIB_INC)/piplib/piplib.h - $(CC) $(CFLAGS) $(PIPLIB_SRC)/maind$(MP_SUF).c \ +$(PIPLIB_OBJ)/maind.o : $(PIPLIB_SRC)/maind.c $(PIPLIB_INC)/piplib/piplib.h + $(CC) $(CFLAGS) $(PIPLIB_SRC)/maind.c \ -o $(PIPLIB_OBJ)/maind.o -$(PIPLIB_OBJ)/tab.o : $(PIPLIB_SRC)/tab$(MP_SUF).c $(PIPLIB_INC)/piplib/piplib.h - $(CC) $(CFLAGS) $(PIPLIB_SRC)/tab$(MP_SUF).c \ +$(PIPLIB_OBJ)/tab.o : $(PIPLIB_SRC)/tab.c $(PIPLIB_INC)/piplib/piplib.h + $(CC) $(CFLAGS) $(PIPLIB_SRC)/tab.c \ -o $(PIPLIB_OBJ)/tab.o -$(PIPLIB_OBJ)/traiter.o : $(PIPLIB_SRC)/traiter$(MP_SUF).c \ - $(PIPLIB_INC)/piplib/piplib.h - $(CC) $(CFLAGS) $(PIPLIB_SRC)/traiter$(MP_SUF).c \ +$(PIPLIB_OBJ)/traiter.o : $(PIPLIB_SRC)/traiter.c $(PIPLIB_INC)/piplib/piplib.h + $(CC) $(CFLAGS) $(PIPLIB_SRC)/traiter.c \ -o $(PIPLIB_OBJ)/traiter.o -$(PIPLIB_OBJ)/sol.o : $(PIPLIB_SRC)/sol$(MP_SUF).c $(PIPLIB_INC)/piplib/piplib.h - $(CC) $(CFLAGS) $(PIPLIB_SRC)/sol$(MP_SUF).c \ +$(PIPLIB_OBJ)/sol.o : $(PIPLIB_SRC)/sol.c $(PIPLIB_INC)/piplib/piplib.h + $(CC) $(CFLAGS) $(PIPLIB_SRC)/sol.c \ -o $(PIPLIB_OBJ)/sol.o @@ -179,13 +186,19 @@ distclean: clean install:: $(TO_BUILD:%=%install) $(INT_BITS)install : + @echo "-----" + @echo "Installing all for" $(INT_BITS) "bits version." $(MAKE) "BITS=$(INT_BITS)" "DFLAGS=$(INT_DFLAGS)" toinstall $(LONG_BITS)install : + @echo "-----" + @echo "Installing all for" $(LONG_BITS) "bits version." $(MAKE) "BITS=$(LONG_BITS)" "DFLAGS=$(LONG_DFLAGS)" toinstall $(MP_BITS)install : - $(MAKE) "BITS=$(MP_BITS)" "DFLAGS=$(MP_DFLAGS)" "MP_SUF=MP" toinstall + @echo "-----" + @echo "Installing all for" $(MP_BITS) "version." + $(MAKE) "BITS=$(MP_BITS)" "DFLAGS=$(MP_DFLAGS)" toinstall toinstall : $(TO_INSTALL) diff --git a/README b/README index d29f16e..f5424c1 100644 --- a/README +++ b/README @@ -76,22 +76,13 @@ compilation and installation of PIP. By giving configure the option --without-lib you disable the compilation and installation of the PipLib. By default, both int (32 bits) and long long int (64 bits) versions are -built. Multiple precision is built too if the GMP library is found. -By giving configure the option --enable-int you ask for int -version only. By giving configure the option --enable-llint you -ask for long long int version only. By giving configure the -option --enable-gmp you ask for GMP version only. - -By default, PIP looks for the GMP library in the standard path -/usr/ or /usr/local/. If the multiple precision Pip construction -is needed and if the GMP library was installed elsewhere, you must must give -to the configure shell script the option --with-gmp=PATH, where -PATH is the GMP library installation path. +built. By giving configure the option --enable-int you ask for int +version only and by giving configure the option --enable-llint you +ask for long long int version only. # **-------------------------------------------------------------------** # ** IV Running PIP ** # **-------------------------------------------------------------------**/ -To run PIP, simply type 'pip32', 'pip64' or 'pipMP', optionally followed by the -name of an input file. For more informations, please check the ./doc -subdirectory. +To run PIP, simply type 'pip32' ou 'pip64', optionally followed by the name +of an input file. For more informations, please check the ./doc subdirectory. diff --git a/configure.in b/configure.in index f6592ba..b1aa15b 100644 --- a/configure.in +++ b/configure.in @@ -12,7 +12,7 @@ dnl Input file for autoconf to build a configuration shellscript. AC_PREREQ(2.13) AC_INIT(./source/piplib.c) -VERSION="1.1" +VERSION="1.2" TO_BUILD_32="32" TO_BUILD_64="64" @@ -110,7 +110,7 @@ AC_ARG_WITH(lib, fi ]) AC_ARG_WITH(gmp, - [ --with-gmp DIR where the gmp library is installed], + [ --with-gmp=DIR DIR where the gmp library is installed], [ echo "Package gmp : $withval" && gmp_package=$withval && NEED_MP="yes"]) @@ -247,5 +247,6 @@ echo " /*-----------------------------------------------*" echo " * PIP/PipLib configuration is OK *" echo " *-----------------------------------------------*/" echo "It appears that your system is OK to start PIP/PipLib compilation. You" -echo "need now to type \"make\" to buid the program, then \"make install\" to" -echo "install it on your system." +echo "need now to type \"make\" to buid the program. Next, if your are" +echo "upgrading an old version, then type \"make uninstall\". Lastly type" +echo "\"make install\" to install it on your system." diff --git a/doc/pip.ps b/doc/pip.ps index 989ca8f..d06b2f4 100644 --- a/doc/pip.ps +++ b/doc/pip.ps @@ -8,7 +8,7 @@ %DVIPSWebPage: (www.radicaleye.com) %DVIPSCommandLine: dvips -o pip.ps pip.dvi %DVIPSParameters: dpi=600, compressed -%DVIPSSource: TeX output 2002.11.25:2355 +%DVIPSSource: TeX output 2003.01.17:0003 %%BeginProcSet: texc.pro %! /TeXDict 300 dict def TeXDict begin/N{def}def/B{bind def}N/S{exch}N/X{S @@ -1805,8 +1805,8 @@ E013FF9038F803FE90B55A15F0D8F87F13C026E00FFEC7FC222B7DA929>II E %EndDVIPSBitmapFont -%DVIPSBitmapFont: Fr cmr12 14.4 34 -/Fr 34 122 df19 D24 D<120FEA3FC0EA7FE012FF13F0A213F8A3127F123FEA0F381200A513 @@ -1823,107 +1823,106 @@ EB1FFCD803E06D7E4848EB03FF48486D138090C813C0001E16E0001C157F003CED3FF012 380078ED1FF81270A2B4ED0FFC13C07FA66C5A6C5A000EC8FCC9EA1FF8A317F0163FA2EE 7FE017C016FF17804B1300A24B5A4B5A5E4B5A4B5A4B5A5E4BC7FC15FE4A5A4A5A4A5A4A 5A5D4A5A4AC8FC147E5C4948141CEB03E0495A4948143891C8FC131E5B5B491578485A48 -481570484815F048B7FCA25A5A5AB812E0A42E4F7ACE3B>I<000316C001C0140301F814 -1F903AFFC003FF8091B612005E5E5E16E016804BC7FC019F13F8018113800180C9FCB0EC -0FF0ECFFFE01836D7E903987F01FE090399F0007F801BE6D7E01F86D7E496D7E49EC7F80 -5BEE3FC04915E0C9121F17F0A317F8160FA317FCA5120EEA3F80487E12FF7FA217F85B16 -1F5B48C813F012700078ED3FE0A26C16C0167F6CEDFF80001F16006C6C495A6C6C13036C -6CEB07F8D801F8EB1FF06CB4EB7FE06DB51280011F49C7FC010713F8010013C02E517ACE -3B>53 D65 DII70 D<49B612FEA490C7003F138092380FFE001507B3B3B3A21206EA3FC0487E487E -A44B5AA25B007F5D0180131F0078C75B6C143F003E4A5A6C5D6C6C495A2707E003FEC7FC -3901FC07FC6CB512F0013F13C0D907FCC8FC2F547BD13C>74 D78 D80 -D86 D97 DII<17FF4BB5FCA4ED000716 -0182B3A6EC0FF8EC7FFF49B512E0903907FC03F090391FE0007C49487F49C7120F01FE80 -484880485A000781484880A2485AA2485AA2127FA35B12FFAB127FA27FA2123FA27F121F -A26C6C5C00075D7F6C6C5C6C6C5C6C6C021E7F6D6C017C13E0D91FC049EBFF8090390FF8 -07E00103B512800100495ADA1FF091C7FC39547CD241>II104 D<1378EA01FE487E487FA66C90C7 -FC6C5AEA007890C8FCB0EB7F80B5FCA41203C6FC137FB3B3A43801FFE0B61280A419507C -CF21>I108 -D<01FFD907FEEC03FFB590261FFFC0010F13E0037F01F0013F13F8912701F80FFC9038FC -07FE913D03C003FE01E001FF000390260700019038038000C6010E6D6C48C76C7E6D48DA -7F8E6E7E4A159CA24ADA3FF86E7E02605D14E04A5DA34A5DB3AD2601FFE0DAFFF0EC7FF8 -B6D8C07F9026FFE03FB512F0A45C347CB363>I<01FFEB07FCB590383FFF8092B512E091 -3901F00FF8913903C007FC000349C66C7EC6010E13016D486D7E5C143002706E7E146014 -E05CA35CB3AD2601FFE0903801FFE0B600C0B612C0A43A347CB341>II<01FFEB1F80B5EB7FF0913801FFF8913803E1FC91380783FE0003EB0F07C6 -131EEB7F1C1438143091387003FC91386000F0160014E05CA45CB3AA8048487EB612F0A4 -27347DB32E>114 D -IIII121 -D E +481570484815F048B7FCA25A5A5AB812E0A42E4F7ACE3B>II54 D65 DII70 D<49B612FEA490C7003F +138092380FFE001507B3B3B3A21206EA3FC0487E487EA44B5AA25B007F5D0180131F0078 +C75B6C143F003E4A5A6C5D6C6C495A2707E003FEC7FC3901FC07FC6CB512F0013F13C0D9 +07FCC8FC2F547BD13C>74 D80 D86 D97 +DII<17FF4BB5FCA4ED0007160182B3A6EC0FF8EC7FFF49B512E0903907FC +03F090391FE0007C49487F49C7120F01FE80484880485A000781484880A2485AA2485AA2 +127FA35B12FFAB127FA27FA2123FA27F121FA26C6C5C00075D7F6C6C5C6C6C5C6C6C021E +7F6D6C017C13E0D91FC049EBFF8090390FF807E00103B512800100495ADA1FF091C7FC39 +547CD241>II104 D<1378EA01FE487E487FA66C90C7FC6C5AEA007890C8FCB0EB7F80B5FCA41203 +C6FC137FB3B3A43801FFE0B61280A419507CCF21>I108 D<01FFEB07FCB590383FFF8092B512E09139 +01F00FF8913903C007FC000349C66C7EC6010E13016D486D7E5C143002706E7E146014E0 +5CA35CB3AD2601FFE0903801FFE0B600C0B612C0A43A347CB341>110 +DI<01FFEB1F80B5EB7FF0913801FFF8913803E1FC913807 +83FE0003EB0F07C6131EEB7F1C1438143091387003FC91386000F0160014E05CA45CB3AA +8048487EB612F0A427347DB32E>114 DIIII +121 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fs cmr17 20.74 29 /Fs 29 122 df)p Fn(.)44 b(Otherwise,)33 b(the)g(solution)e(is)h Fk(<)c(m)22 b Fm(\000)h Fk(k)s(;)17 b(m)27 b(>)p Fn(.)404 4994 y(T)-8 b(o)32 b(sum)h(things)f(up,)h(the)g(lexicographical)d(minim)m(um)f(of)j Fm(D)2671 5009 y Fe(2)2743 4994 y Fn(is:)462 5198 y Fl(if)52 -b(m-k)g(>=)g(0)g(then)g(<0,)g(k>)g(else)g(.)257 +b(m-k)g(>=)g(0)g(then)g(<0,)g(k>)g(else)g(.)257 5401 y Fn(Hence)34 b(the)f(lo)m(w)m(er)g(b)s(ound)g(on)f(the)h(\014rst) g(co)s(ordinate:)462 5604 y Fl(if)52 b(m-k)g(>=)g(0)g(then)g(0)f(else)i -(m-k)p eop +(k-m)p eop %%Page: 8 8 8 7 bop 257 266 a Fj(2)98 b(USING)32 b(THE)i(PIP)f(SOFTW)-11 b(ARE)1879 b Fn(8)257 573 y Fg(2.3.2)113 b(Simplifying)34 @@ -3439,10 +3438,11 @@ b(can)g(easily)f(remo)m(v)m(e)h(PIP)g(and)g(the)g(PipLib)e(from)h(y)m (our)h(system)h(b)m(y)f(t)m(yping)f Fl(make)257 4729 y(uninstall)p Fn(.)404 4967 y(Rep)s(ort)32 b(all)e(bugs,)k(problems,)e (inaccuracies)g(in)g(the)h(do)s(cumen)m(tation)e(to:)404 -5088 y Fl(Paul.Feautrier@prism.uvsq.)q(fr)404 5208 y -Fn(Praise)h(is)g(also)g(appreciated.)404 5328 y(Let)g(the)h(p)s(o)m(w)m -(er)h(of)e(parametric)f(in)m(teger)i(programming)c(b)s(e)k(with)f(y)m -(ou.)p eop +5088 y Fl(Paul.Feautrier@ens-lyon.fr)404 5208 y +(Cedric.Bastoul@prism.uvsq.)q(fr)404 5328 y Fn(Praise)h(is)g(also)g +(appreciated.)404 5449 y(Let)g(the)h(p)s(o)m(w)m(er)h(of)e(parametric)f +(in)m(teger)i(programming)c(b)s(e)k(with)f(y)m(ou.)p +eop %%Page: 24 24 24 23 bop 257 266 a Fj(REFERENCES)2659 b Fn(24)257 573 y Fo(References)257 792 y Fn([1])49 b(P)m(aul)67 b(F)-8 diff --git a/example/Makefile b/example/Makefile index 92bd9cd..1a2b6a9 100644 --- a/example/Makefile +++ b/example/Makefile @@ -1,10 +1,10 @@ # Please enter here the locations for PipLib include and libraries if they # aren't the default values (/usr/lib and /usr/include). -#PIPLIB_INC = $(HOME)/progs/linux/include -#PIPLIB_LIB = $(HOME)/progs/linux/lib +PIPLIB_INC = $(HOME)/progs/linux/include +PIPLIB_LIB = $(HOME)/progs/linux/lib CC = gcc -LDLIBS= -lpiplibMP #-lgmp +LDLIBS= -lpiplib32 CFLAGS= -I $(PIPLIB_INC) -L $(PIPLIB_LIB) diff --git a/example/example.c b/example/example.c index ee48514..632fd13 100644 --- a/example/example.c +++ b/example/example.c @@ -5,7 +5,6 @@ */ # include -/*# include */ # include int main() diff --git a/include/piplib/funcall.h b/include/piplib/funcall.h index 4346383..97fb251 100644 --- a/include/piplib/funcall.h +++ b/include/piplib/funcall.h @@ -24,6 +24,13 @@ * * ******************************************************************************/ +#ifndef FUNCALL_H +#define FUNCALL_H +#if defined(__cplusplus) +extern "C" + { +#endif + #if defined(LINEAR_VALUE_IS_MP) void traiter(Tableau *, Tableau *, int, int, int, int, int, int); int integrer(Tableau **, Tableau **, int *, int *, int *, int *); @@ -55,3 +62,8 @@ void tab_display(Tableau *, FILE *); Tableau * expanser(Tableau *, int, int, int, int, int, int); void sol_new(int); void sol_div(void); + +#if defined(__cplusplus) + } +#endif +#endif /* define _H */ diff --git a/include/piplib/piplib.h b/include/piplib/piplib.h index e72258c..13fea48 100644 --- a/include/piplib/piplib.h +++ b/include/piplib/piplib.h @@ -26,6 +26,12 @@ /* Premiere version du 18 septembre 2002. */ +#ifndef PIPLIB_H +#define PIPLIB_H +#if defined(__cplusplus) +extern "C" + { +#endif #if !defined(LINEAR_VALUE_IS_LONGLONG) && !defined(LINEAR_VALUE_IS_INT) #if !defined(LINEAR_VALUE_IS_MP) @@ -36,17 +42,17 @@ #if defined(LINEAR_VALUE_IS_LONGLONG) # define Entier long long # define FORMAT "%lld" -# define UN 1LL -# define ZERO 0LL +# define VAL_UN 1LL +# define VAL_ZERO 0LL #elif defined(LINEAR_VALUE_IS_INT) # define Entier long int # define FORMAT "%ld" -# define UN 1L -# define ZERO 0L +# define VAL_UN 1L +# define VAL_ZERO 0L #elif defined(LINEAR_VALUE_IS_MP) # include # define Entier mpz_t -# define FORMAT "%lld" +# define FORMAT "%d" #endif # include @@ -163,3 +169,8 @@ PipQuast * pip_solve(PipMatrix *, PipMatrix *, int, int, int, int, int) ; /* Ced : ajouts specifiques a la PipLib pour funcall. */ Tableau * tab_Matrix2Tableau(PipMatrix *, int, int, int) ; PipQuast * sol_quast_edit(int *, PipQuast *) ; + +#if defined(__cplusplus) + } +#endif +#endif /* define PIPLIB_H */ diff --git a/include/piplib/piplib32.h b/include/piplib/piplib32.h index 11bd611..f395f57 100644 --- a/include/piplib/piplib32.h +++ b/include/piplib/piplib32.h @@ -28,5 +28,17 @@ * utilisateurs de la PipLib. Premiere version du 29 juillet 2001. */ +#ifndef PIPLIB32_H +#define PIPLIB32_H +#if defined(__cplusplus) +extern "C" + { +#endif + # define LINEAR_VALUE_IS_INT # include + +#if defined(__cplusplus) + } +#endif +#endif /* define _H */ diff --git a/include/piplib/piplib64.h b/include/piplib/piplib64.h index 5476e7d..f627ea5 100644 --- a/include/piplib/piplib64.h +++ b/include/piplib/piplib64.h @@ -28,5 +28,17 @@ * utilisateurs de la PipLib. Premiere version du 29 juillet 2001. */ +#ifndef PIPLIB64_H +#define PIPLIB64_H +#if defined(__cplusplus) +extern "C" + { +#endif + # define LINEAR_VALUE_IS_LONGLONG # include + +#if defined(__cplusplus) + } +#endif +#endif /* define _H */ diff --git a/include/piplib/piplibMP.h b/include/piplib/piplibMP.h index fa1ab1e..7e134a4 100644 --- a/include/piplib/piplibMP.h +++ b/include/piplib/piplibMP.h @@ -28,5 +28,17 @@ * utilisateurs de la PipLib. Premiere version du 29 juillet 2001. */ +#ifndef PIPLIBMP_H +#define PIPLIBMP_H +#if defined(__cplusplus) +extern "C" + { +#endif + # define LINEAR_VALUE_IS_MP # include + +#if defined(__cplusplus) + } +#endif +#endif /* define _H */ diff --git a/include/piplib/sol.h b/include/piplib/sol.h index b8bc9b7..ee58a05 100644 --- a/include/piplib/sol.h +++ b/include/piplib/sol.h @@ -24,16 +24,28 @@ * * ******************************************************************************/ +#ifndef SOL_H +#define SOL_H +#if defined(__cplusplus) +extern "C" + { +#endif -void sol_init(); -int sol_hwm(); -void sol_reset(); -void sol_nil(); -void sol_if(); -void sol_list(); -void sol_form(); -void sol_new(); -void sol_div(); -void sol_val(); -int sol_edit(); -int is_not_Nil(); +void sol_init(void); +int sol_hwm(void); +void sol_reset(int); +void sol_nil(void); +void sol_if(void); +void sol_list(int); +void sol_form(int); +void sol_new(int); +void sol_div(void); +void sol_val(Entier, Entier); +int sol_edit(FILE *, int); +int is_not_Nil(int); +void sol_simplify(int); + +#if defined(__cplusplus) + } +#endif +#endif /* define _H */ diff --git a/include/piplib/tab.h b/include/piplib/tab.h index 55f1eac..99e4e8a 100644 --- a/include/piplib/tab.h +++ b/include/piplib/tab.h @@ -24,6 +24,13 @@ * * ******************************************************************************/ +#ifndef TAB_H +#define TAB_H +#if defined(__cplusplus) +extern "C" + { +#endif + struct A {struct A *precedent; char *bout; @@ -74,3 +81,8 @@ struct T typedef struct T Tableau; +#if defined(__cplusplus) + } +#endif +#endif /* define _H */ + diff --git a/include/piplib/type.h b/include/piplib/type.h index 21748ae..dc2153a 100644 --- a/include/piplib/type.h +++ b/include/piplib/type.h @@ -24,12 +24,17 @@ * * ******************************************************************************/ +#ifndef TYPE_H +#define TYPE_H +#if defined(__cplusplus) +extern "C" + { +#endif + #define SOL_SIZE 4096 -#if defined(LINEAR_VALUE_IS_MP) extern Entier UN; extern Entier ZERO; -#endif #define True 1 #define False 0 @@ -44,3 +49,7 @@ extern Entier ZERO; #define MAXCOL 512 #define MAXPARM 50 +#if defined(__cplusplus) + } +#endif +#endif /* define _H */ diff --git a/source/integrer.c b/source/integrer.c index dab2f72..5315f02 100644 --- a/source/integrer.c +++ b/source/integrer.c @@ -38,8 +38,9 @@ extern FILE * dump; /* mod(x,y) computes the remainder of x when divided by y. The difference with x%y is that the result is guaranteed to be positive, which is not - always true for x%y */ + always true for x%y. This function is replaced by mpz_fdiv_r for MP. */ +#if !defined(LINEAR_VALUE_IS_MP) Entier mod(x, y) Entier x, y; {Entier r; @@ -47,6 +48,7 @@ Entier x, y; if(r<0) r += y; return(r); } +#endif /* this routine is useless at present */ @@ -77,10 +79,16 @@ Tableau *expanser(); nc increases by 2. */ +#if defined(LINEAR_VALUE_IS_MP) +int integrer(ptp, pcontext, pnvar, pnparm, pni, pnc) +Tableau **ptp, **pcontext; +int *pnvar, *pnparm, *pni, *pnc; +#else int integrer(ptp, pcontext, D, pnvar, pnparm, pni, pnc) Tableau **ptp, **pcontext; int *pnvar, *pnparm, *pni, *pnc; Entier D; +#endif {int ncol = *pnvar+*pnparm+1; int nligne = *pnvar + *pni; int nparm = *pnparm; @@ -93,6 +101,22 @@ Entier D; int ok_var, ok_const, ok_parm; Entier discrp[MAXPARM], discrm[MAXPARM]; int llog(); + #if defined(LINEAR_VALUE_IS_MP) + Entier D; + #endif + + #if defined(LINEAR_VALUE_IS_MP) + for(i=0; i<=ncol; i++) + mpz_init(coupure[i]); + + for(i=0; i<=nparm+1; i++){ + mpz_init(discrp[i]); + mpz_init(discrm[i]); + } + + mpz_init(x); mpz_init(d); mpz_init(D); + #endif + if(ncol+1 >= MAXCOL) { fprintf(stderr, "Too much variables : %d\n", ncol); @@ -101,8 +125,13 @@ Entier D; /* search for a non-integral row */ for(i = 0; i 0) ok_var = True; } /* Done for the coefficient of the variables. */ + #if defined(LINEAR_VALUE_IS_MP) + mpz_neg(x, Index(*ptp, i, nvar)); + mpz_fdiv_r(x, x, D); + mpz_neg(x, x); + mpz_set(coupure[nvar], x); + ok_const = mpz_cmp_ui(x, 0); + #else x = coupure[nvar] = - mod(-Index(*ptp, i, nvar), D); ok_const = (x != 0); + #endif /* This is the constant term */ ok_parm = False; for(j = nvar+1; j= (*ptp)->height) { int d, dth, dtw; + #if defined(LINEAR_VALUE_IS_MP) + d = mpz_sizeinbase(D, 2); + #else d = llog(D); + #endif dth = d; *ptp = expanser(*ptp, nvar, ni, ncol, 0, dth, 0); } /* The cut has a negative <> part */ Flag(*ptp, nligne) = Minus; + #if defined(LINEAR_VALUE_IS_MP) + mpz_set(Denom(*ptp, nligne), D); + #else Denom(*ptp, nligne) = D; + #endif /* Insert the cut */ for(j = 0; j (*pcontext)->height || nparm+1 > (*pcontext)->width) { int dcw, dch; + #if defined(LINEAR_VALUE_IS_MP) + dcw = mpz_sizeinbase(D, 2); + #else dcw = llog(D); + #endif dch = 2 * dcw + *pni; *pcontext = expanser(*pcontext, 0, nc, nparm+1, 0, dch, dcw); } @@ -223,27 +327,50 @@ ok_var ok_parm ok_const right and a zero has to be inserted in all rows of the old context */ for(k = 0; k < nc; k++) { + #if defined(LINEAR_VALUE_IS_MP) + mpz_set(Index(*pcontext, k, nparm+1), Index(*pcontext, k, nparm)); + mpz_set_ui(Index(*pcontext, k, nparm), 0); + #else Index(*pcontext, k, nparm+1) = Index(*pcontext, k, nparm); Index(*pcontext, k, nparm) = 0; + #endif } /* Now, insert the new rows */ for(j = 0; j <= nparm+1; j++) { + #if defined(LINEAR_VALUE_IS_MP) + mpz_set(Index(*pcontext, nc, j), discrp[j]); + mpz_set(Index(*pcontext, nc+1, j), discrm[j]); + #else Index(*pcontext, nc, j) = discrp[j]; Index(*pcontext, nc+1, j) = discrm[j]; + #endif } Flag(*pcontext, nc) = Unknown; /* A */ - Denom(*pcontext, nc) = UN; Flag(*pcontext, nc+1) = Unknown; + #if defined(LINEAR_VALUE_IS_MP) + mpz_set(Denom(*pcontext, nc), UN); + mpz_set(Denom(*pcontext, nc+1), UN); + #else + Denom(*pcontext, nc) = UN; Denom(*pcontext, nc+1) = UN; + #endif (*pnparm)++; (*pnc) += 2; + if(verbose > 0){ + fprintf(dump, "enlarged context %d x %d\n", *pnparm, *pnc); + fflush(dump); + } /* end of the construction of the new parameter */ if(ok_var) { /* case (e) */ if(nligne >= (*ptp)->height || ncol >= (*ptp)->width) { int d, dth, dtw; - d = llog(D); + #if defined(LINEAR_VALUE_IS_MP) + d = mpz_sizeinbase(D, 2); + #else + d = llog(D); + #endif dth = d + ni; dtw = d; *ptp = expanser(*ptp, nvar, ni, ncol, 0, dth, dtw); @@ -253,13 +380,25 @@ ok_var ok_parm ok_const /* The cut has a negative <> part */ Flag(*ptp, nligne) = Minus; + #if defined(LINEAR_VALUE_IS_MP) + mpz_set(Denom(*ptp, nligne), D); + #else Denom(*ptp, nligne) = D; + #endif /* Insert the cut */ for(j = 0; j= (*ptp)-> width) { int dtw; + #if defined(LINEAR_VALUE_IS_MP) + dtw = mpz_sizeinbase(D, 2); + #else dtw = llog(D); + #endif *ptp = expanser(*ptp, *pnvar, *pni, ncol, 0, 0, dtw); } /* The new column is zeroed out by <> */ @@ -284,12 +432,30 @@ ok_var ok_parm ok_const divisible by D. */ for (j = 0; j <= nparm; j++) + #if defined(LINEAR_VALUE_IS_MP) + mpz_add(Index(*ptp, i, j + nvar + 1), + Index(*ptp, i, j + nvar + 1), discrp[j]); + #else Index(*ptp, i, j + nvar + 1) += discrp[j]; + #endif tab_display(*ptp, stderr); exit(0); continue; } /* The solution is integral. */ + #if defined(LINEAR_VALUE_IS_MP) + nligne = 0; + clear : + for(i=0; i <= ncol; i++) + mpz_clear(coupure[i]); + for(i=0; i <= nparm+1; i++){ + mpz_clear(discrp[i]); + mpz_clear(discrm[i]); + } + mpz_clear(x); mpz_clear(d); mpz_clear(D); + return(nligne); + #else return 0; + #endif } diff --git a/source/integrerMP.c b/source/integrerMP.c deleted file mode 100644 index e3cfa24..0000000 --- a/source/integrerMP.c +++ /dev/null @@ -1,345 +0,0 @@ -/********************************************************/ -/* Part of MultiPrecision PIP port by Zbigniew Chamski */ -/* and Paul Feautrier. */ -/* Based on straight PIP E.1 version by Paul Feautrier */ -/* */ -/* */ -/* and a previous port (C) Zbigniew CHAMSKI, 1993. */ -/* */ -/* */ -/* Copying subject to the terms and conditions of the */ -/* GNU General Public License. */ -/* */ -/* Send questions, bug reports and fixes to: */ -/* */ -/********************************************************/ - -#include -#include - -#include - -/* The routines in this file are used to build a Gomory cut from - a non-integral row of the problem tableau */ - -extern long int cross_product, limit; -extern int verbose; -extern FILE * dump; - -/* mod(x,y) computes the remainder of x when divided by y. The difference - with x%y is that the result is guaranteed to be positive, which is not - always true for x%y - -This function is replaced by mpz_fdiv_r. -*/ - - -Tableau *expanser(); - -/* integrer(.....) add a cut to the problem tableau, or return 0 when an - integral solution has been found, or -1 when no integral solution - exists. - - Since integrer may add rows and columns to the problem tableau, its - arguments are pointers rather than values. If a cut is constructed, - ni increases by 1. If the cut is parametric, nparm increases by 1 and - nc increases by 2. - */ - -int integrer(ptp, pcontext, pnvar, pnparm, pni, pnc) -Tableau **ptp, **pcontext; -int *pnvar, *pnparm, *pni, *pnc; - -{int ncol = *pnvar+*pnparm+1; - int nligne = *pnvar + *pni; - int nparm = *pnparm; - int nvar = *pnvar; - int ni = *pni; - int nc = *pnc; - Entier coupure[MAXCOL]; - int i, j, k, ff; - Entier x, d, D; - int ok_var, ok_const, ok_parm; - Entier discrp[MAXPARM], discrm[MAXPARM]; - - - for(i=0; i<=ncol; i++) - mpz_init(coupure[i]); - - for(i=0; i<=nparm+1; i++){ - mpz_init(discrp[i]); - mpz_init(discrm[i]); - } - - mpz_init(x); mpz_init(d); mpz_init(D); - - if(ncol+1 >= MAXCOL) { - fprintf(stdout, "Too much variables : %d\n", ncol); - exit(3); - } - -/* search for a non-integral row */ - - for(i = 0; i 0) ok_var = True; - } -/* Done for the coefficient of the variables. */ - - /* x = coupure[nvar] = - mod(-Index(*ptp, i, nvar), D); */ - mpz_neg(x, Index(*ptp, i, nvar)); - mpz_fdiv_r(x, x, D); - mpz_neg(x, x); - mpz_set(coupure[nvar], x); - /* ok_const = (x != 0); */ - ok_const = mpz_cmp_ui(x, 0); -/* This is the constant term */ - ok_parm = False; - for(j = nvar+1; j> part is not divisible - by D then bottom else .... - F T T - T F F (a) continue, integral row - T F T (d) constant cut - T T F - (e) parametric cut - T T T - - case (a) */ - - if(!ok_parm && !ok_const) continue; - if(!ok_parm) - if(ok_var) { /* case (d) */ - if(nligne >= (*ptp)->height) { - int d, dth, dtw; - d = mpz_sizeinbase(D, 2); - dth = d; - *ptp = expanser(*ptp, nvar, ni, ncol, 0, dth, 0); - } - /* The cut has a negative <> part */ - Flag(*ptp, nligne) = Minus; - /* Denom(*ptp, nligne) = D; */ - mpz_set(Denom(*ptp, nligne), D); - /* Insert the cut */ - for(j = 0; j= 0. */ - - - if(nparm >= MAXPARM) { - fprintf(stdout, "Too much parameters : %d\n", *pnparm); - exit(4); - } -/* Build the definition of the new parameter into the solution : - p_{nparm} = -(sum_{j=0}^{nparm-1} c_{nvar + 1 + j} p_j - + c_{nvar})/D (3) - The minus sign is there to compensate the one in (1) */ - - - sol_new(nparm); - sol_div(); - sol_forme(nparm+1); - for(j = 0; j0) fflush(dump); - -/* The value of the new parameter is specified by applying the definition of - Euclidean division to (3) : - - 0<= - sum_{j=0}^{nparm-1} c_{nvar+1+j} p_j - c_{nvar} - D * p_{nparm} < D (4) - - This formula gives two inequalities which are stored in the context */ - - for(j = 0; j 0){ - fprintf(dump, "Take care %d %d\n", nparm, nvar); - fflush(dump); - } - /* discrp[(nparm)+1] = -x; */ - mpz_neg(discrp[nparm+1], x); - /* discrm[(nparm)+1] = x + D -1; */ - mpz_sub_ui(x, x, 1); - mpz_add(discrm[nparm+1], x, D); - - if(nc+2 > (*pcontext)->height || nparm+1 > (*pcontext)->width) { - int dcw, dch; - dcw = mpz_sizeinbase(D, 2); - dch = 2 * dcw + *pni; - *pcontext = expanser(*pcontext, 0, nc, nparm+1, 0, dch, dcw); - } - /* Flag(*pcontext, *pnc) = 0; Probably useless see line A */ -/* Since a new parameter is to be added, the constant term has to be moved - right and a zero has to be inserted in all rows of the old context */ - - for(k = 0; k < nc; k++) { - /* Index(*pcontext, k, nparm+1) = Index(*pcontext, k, nparm); */ - mpz_set(Index(*pcontext, k, nparm+1), Index(*pcontext, k, nparm)); - /* Index(*pcontext, k, nparm) = 0; */ - mpz_set_ui(Index(*pcontext, k, nparm), 0); - } -/* Now, insert the new rows */ - - for(j = 0; j <= nparm+1; j++) { - /* Index(*pcontext, nc, j) = discrp[j]; */ - mpz_set(Index(*pcontext, nc, j), discrp[j]); - /* Index(*pcontext, nc+1, j) = discrm[j]; */ - mpz_set(Index(*pcontext, nc+1, j), discrm[j]); - } - Flag(*pcontext, nc) = Unknown; /* A */ - /* Denom(*pcontext, nc) = UN; */ - mpz_set(Denom(*pcontext, nc), UN); - Flag(*pcontext, nc+1) = Unknown; - /* Denom(*pcontext, nc+1) = UN; */ - mpz_set(Denom(*pcontext, nc+1), UN); - (*pnparm)++; - (*pnc) += 2; - if(verbose > 0){ - fprintf(dump, "enlarged context %d x %d\n", *pnparm, *pnc); - fflush(dump); - } - /* end of the construction of the new parameter */ - - if(ok_var) { /* case (e) */ - if(nligne >= (*ptp)->height || ncol >= (*ptp)->width) { - int d, dth, dtw; - d = mpz_sizeinbase(D, 2); - dth = d + ni; - dtw = d; - *ptp = expanser(*ptp, nvar, ni, ncol, 0, dth, dtw); - } - /* Zeroing out the new column seems to be useless - since <> does it anyway */ - - /* The cut has a negative <> part */ - Flag(*ptp, nligne) = Minus; - /* Denom(*ptp, nligne) = D; */ - mpz_set(Denom(*ptp, nligne), D); - /* Insert the cut */ - for(j = 0; j= (*ptp)-> width) { - int dtw; - dtw = mpz_sizeinbase(D, 2); - *ptp = expanser(*ptp, *pnvar, *pni, ncol, 0, 0, dtw); - } - /* The new column is zeroed out by <> */ -/* Let c be the coefficient of parameter p in the i row. In <>, - this parameter has coefficient - mod(-c, D). In <>, this same - parameter has coefficient mod(-c, D). The sum c + mod(-c, D) is obviously - divisible by D. */ - - for (j = 0; j <= nparm; j++) - /* Index(*ptp, i, j + nvar + 1) += discrp[j]; */ - mpz_add(Index(*ptp, i, j + nvar + 1), - Index(*ptp, i, j + nvar + 1), discrp[j]); - continue; - } - /* The solution is integral. */ - /* return 0; */ - nligne = 0; -clear : - for(i=0; i <= ncol; i++) - mpz_clear(coupure[i]); - for(i=0; i <= nparm+1; i++){ - mpz_clear(discrp[i]); - mpz_clear(discrm[i]); - } - mpz_clear(x); mpz_clear(d); mpz_clear(D); - return(nligne); -} - diff --git a/source/maind.c b/source/maind.c index 4e90f32..99bc389 100644 --- a/source/maind.c +++ b/source/maind.c @@ -43,61 +43,13 @@ struct tms chrono; char version[]="Version E.2 $Revision: 1.3 $\n"; -long int cross_product, limit; -int allocation, comptage; -int verbose = 0; -int profondeur = 0; -int compa_count; -FILE *dump = NULL; -char dump_name[] = "PipXXXXXX"; +extern long int cross_product, limit ; +extern int allocation, comptage, verbose ; +extern FILE * dump ; +extern int compa_count ; +extern char dump_name[] ; -#define INLENGTH 1024 - -char inbuff[INLENGTH]; -int inptr = 256; -int proviso = 0; - - -int dgetc(FILE *foo) -{ - char *p; - if(inptr >= proviso) - {p = fgets(inbuff, INLENGTH, foo); - if(p == NULL) return EOF; - proviso = min(INLENGTH, strlen(inbuff)); - inptr = 0; - if(verbose > 0) fprintf(dump, "-- %s", inbuff); - } - return inbuff[inptr++]; -} - -int dscanf(FILE *foo, char *format, Entier *val) -{ - char * p; - int c; - for(;inptr < proviso; inptr++) - if(inbuff[inptr] != ' ' && inbuff[inptr] != '\n' && inbuff[inptr] != '\t') - break; - while(inptr >= proviso) - {p = fgets(inbuff, 256, foo); - if(p == NULL) return EOF; - proviso = strlen(inbuff); - if(verbose > 0) { - fprintf(dump, ".. %s", inbuff); - fflush(dump); - } - for(inptr = 0; inptr < proviso; inptr++) - if(inbuff[inptr] != ' ' - && inbuff[inptr] != '\n' - && inbuff[inptr] != '\t') break; - } - if(sscanf(inbuff+inptr, FORMAT, val) != 1) return -1; - - for(; inptr < proviso; inptr++) - if((c = inbuff[inptr]) != '-' && !isdigit(c)) break; - return 0; -} void balance(FILE *foo, FILE *bar) { @@ -140,7 +92,19 @@ int main(int argc, char *argv[]) int p, q, xq; long temps; char *date; + #if defined(LINEAR_VALUE_IS_MP) + int x ; + #else Entier D, x; + #endif + + #if defined(LINEAR_VALUE_IS_MP) + mpz_init_set_si(UN, 1); + mpz_init_set_si(ZERO, 0); + #else + UN = VAL_UN ; + ZERO = VAL_ZERO ; + #endif in = stdin; out = stdout; p = 1; @@ -196,18 +160,24 @@ int main(int argc, char *argv[]) {if(c != '(') continue; fprintf(out, "("); balance(in, out); - if(dscanf(in, FORMAT, &x) < 0){escape(in, out, 1); continue;} - else nvar = (int) x; - if(dscanf(in, FORMAT, &x) < 0){escape(in, out, 1); continue; } - else nparm = (int) x; - if(dscanf(in, FORMAT, &x) < 0){escape(in, out, 1); continue; } - else ni = (int) x; - if(dscanf(in, FORMAT, &x) < 0){escape(in, out, 1); continue; } - else nc = (int) x; - if(dscanf(in, FORMAT, &x) < 0){escape(in, out, 1); continue; } - else bigparm = (int) x; - if(dscanf(in, FORMAT, &x) < 0){escape(in, out, 1); continue; } - else nq = (int) x; + if(dscanf(in, &x) < 0){escape(in, out, 1); continue;} + else + nvar = (int) x; + if(dscanf(in, &x) < 0){escape(in, out, 1); continue; } + else + nparm = (int) x; + if(dscanf(in, &x) < 0){escape(in, out, 1); continue; } + else + ni = (int) x; + if(dscanf(in, &x) < 0){escape(in, out, 1); continue; } + else + nc = (int) x; + if(dscanf(in, &x) < 0){escape(in, out, 1); continue; } + else + bigparm = (int) x; + if(dscanf(in, &x) < 0){escape(in, out, 1); continue; } + else + nq = (int) x; if(verbose > 0) {fprintf(dump, "%d %d %d %d %d %d\n",nvar, nparm, ni, nc, bigparm, nq); fflush(dump); @@ -225,16 +195,26 @@ int main(int argc, char *argv[]) /* verification de la non-vacuite' du contexte */ if(nc) {ctxt = expanser(context, nparm, nc, nparm+1, nparm, 0, 0); + #if defined(LINEAR_VALUE_IS_MP) + traiter(ctxt, NULL, True, nparm, 0, nc, 0, -1); + #else traiter(ctxt, NULL, True, UN, nparm, 0, nc, 0, -1); + #endif non_vide = is_not_Nil(p); sol_reset(p); } else non_vide = True; if(non_vide) { compa_count = 0; + #if defined(LINEAR_VALUE_IS_MP) + traiter(ineq, context, nq, nvar, nparm, ni, nc, bigparm); + putc(' ',out); + mpz_out_str(out, 10, ineq->determinant); + #else D = traiter(ineq, context, nq, UN, nvar, nparm, ni, nc, bigparm); putc(' ',out); fprintf(out, FORMAT, D); + #endif fputs(" )",out); if(simple) sol_simplify(xq); q = sol_hwm(); diff --git a/source/maindMP.c b/source/maindMP.c deleted file mode 100644 index 03304f8..0000000 --- a/source/maindMP.c +++ /dev/null @@ -1,250 +0,0 @@ -/********************************************************/ -/* Part of MultiPrecision PIP port by Zbigniew Chamski */ -/* and Paul Feautrier. */ -/* Based on straight PIP E.1 version by Paul Feautrier */ -/* */ -/* */ -/* and a previous port (C) Zbigniew CHAMSKI, 1993. */ -/* */ -/* */ -/* Copying subject to the terms and conditions of the */ -/* GNU General Public License. */ -/* */ -/* Send questions, bug reports and fixes to: */ -/* */ -/********************************************************/ - -#include -#include -#include -#include -#include - - -#define min(x,y) ((x) < (y)? (x) : (y)) - -#include - -#include -struct tms chrono; - -long int cross_product, limit; -int allocation, comptage; -int verbose = 0; -int profondeur = 0; -float the_clock = 0.0; -int compa_count; - -FILE *dump = NULL; -char dump_name[] = "PipXXXXXX"; - -#define INLENGTH 1024 - -char inbuff[INLENGTH]; -int inptr = 256; -int proviso = 0; - -Entier UN; -Entier ZERO; - -char version[] = "Version MP.1\n"; - -int dgetc(FILE *foo) -{ - char *p; - if(inptr >= proviso) - {p = fgets(inbuff, INLENGTH, foo); - if(p == NULL) return EOF; - proviso = min(INLENGTH, strlen(inbuff)); - inptr = 0; - if(verbose > 0) fprintf(dump, "-- %s", inbuff); - } - return inbuff[inptr++]; -} - -int dscanf(FILE *foo, char *format, int *val) -{ - char * p; - int c; - for(;inptr < proviso; inptr++) - if(inbuff[inptr] != ' ' && inbuff[inptr] != '\n' && inbuff[inptr] != '\t') - break; - while(inptr >= proviso) - {p = fgets(inbuff, 256, foo); - if(p == NULL) return EOF; - proviso = strlen(inbuff); - if(verbose > 0) { - fprintf(dump, ".. %s", inbuff); - fflush(dump); - } - for(inptr = 0; inptr < proviso; inptr++) - if(inbuff[inptr] != ' ' - && inbuff[inptr] != '\n' - && inbuff[inptr] != '\t') break; - } - if(sscanf(inbuff+inptr, FORMAT, val) != 1) return -1; - - for(; inptr < proviso; inptr++) - if((c = inbuff[inptr]) != '-' && !isdigit(c)) break; - return 0; -} - -void balance(FILE *foo, FILE *bar) -{ - int level = 0; - int c; - while((c = dgetc(foo)) != EOF) - { - switch(c) - {case '(' : level++; break; - case ')' : if(--level == 0) return; - } - putc(c, bar); - } -} - -void escape(FILE *foo, FILE *bar, int level) -{int c; - while((c = dgetc(foo)) != EOF) - switch(c) - {case '(' : level ++; break; - case ')' : if(--level == 0) - { fprintf(bar, "\nSyntax error\n)\n"); - return; - } - } -} - -int main(int argc, char *argv[]) - -{ - FILE *in, *out; - Tableau *ineq, *context, *ctxt; - int nvar, nparm, ni, nc, bigparm; - int nq; char * g; - int simple = 0; - struct high_water_mark hq; - int c, non_vide; - int p, q, xq; - long temps; - char *date; - int x; - mpz_init_set_si(UN, 1); - mpz_init_set_si(ZERO, 0); - - in = stdin; out = stdout; - p = 1; - if(argc > 1) - if(strcmp(argv[1], "-s") == 0) - {verbose = -1; - p = 2; - } - else if(strcmp(argv[1], "-v") == 0) - {verbose = 1; - p = 2; - g = getenv("DEBUG"); - if(g && *g) - {dump = fopen(g, "w"); - if(dump == NULL) - {fprintf(stdout, "%s unaccessible\n", g); - verbose = 0; - } - } - else - { - mkstemp(dump_name); - dump = fopen(dump_name, "w"); - } - } - if(verbose >= 0) fprintf(stdout, version); - if(argc > p) - if(strcmp(argv[p], "-z") == 0) { - simple = 1; - p++; - } - if(argc>p) - {in = fopen(argv[p], "r"); - if(in == NULL) - {fprintf(stdout, "%s unaccessible\n", argv[p]); - exit(1); - } - } - p++; - if(argc>p) - {out = fopen(argv[p], "w"); - if(out == NULL) - {fprintf(stdout, "%s unaccessible\n", argv[p]); - exit(2); - } - } - limit = 0L; - p++; - if(argc > p) limit = atol(argv[p]); - sol_init(); - tab_init(); - while((c = dgetc(in)) != EOF) - {if(c != '(') continue; - fprintf(out, "("); - balance(in, out); - if(dscanf(in, "d", &x) < 0){escape(in, out, 1); continue;} - else nvar = x; - if(dscanf(in, "d", &x) < 0){escape(in, out, 1); continue; } - else nparm = x; - if(dscanf(in, "d", &x) < 0){escape(in, out, 1); continue; } - else ni = x; - if(dscanf(in, "d", &x) < 0){escape(in, out, 1); continue; } - else nc = x; - if(dscanf(in, "d", &x) < 0){escape(in, out, 1); continue; } - else bigparm = x; - if(dscanf(in, "d", &x) < 0){escape(in, out, 1); continue; } - else nq = x; - if(verbose > 0) {fprintf(dump, "%d %d %d %d %d %d\n",nvar, nparm, ni, nc, - bigparm, nq); - fflush(dump); - } - cross_product = 0; - hq = tab_hwm(); - if(verbose > 0) {fprintf(dump, "hwm %x\n", g); - fflush(dump); - } - ineq = tab_get(in, ni, nvar+nparm+1, nvar); - if(ineq == NULL){escape(in, out, 2); continue;} - context = tab_get(in, nc, nparm+1, 0); - if(ineq == NULL){escape(in, out, 2); continue;} - xq = p = sol_hwm(); -/* verification de la non-vacuite' du contexte */ - if(nc) - {ctxt = expanser(context, nparm, nc, nparm+1, nparm, 0, 0); - traiter(ctxt, NULL, True, nparm, 0, nc, 0, -1); - non_vide = is_not_Nil(p); - sol_reset(p); - } - else non_vide = True; - if(non_vide) { - compa_count = 0; - traiter(ineq, context, nq, nvar, nparm, ni, nc, bigparm); - putc(' ',out); - mpz_out_str(out, 10, ineq->determinant); - fputs(" )",out); - if(simple) sol_simplify(xq); - q = sol_hwm(); - while((xq = sol_edit(out, xq)) != q); - sol_reset(p); - } - else fprintf(out, "void\n"); - tab_reset(hq); - if(verbose > 0) fflush(dump); - fprintf(out, ")\n"); - fflush(out); - if(verbose >= 0)fprintf(stdout,"cross : %ld, alloc : %d, compa : %d\n\r", - cross_product, allocation, compa_count); - comptage++; - } - if(verbose >= 0){ - times(& chrono); - fprintf(stdout, "n %d u %d''' s %d'''\r\n", - comptage, chrono.tms_utime, chrono.tms_stime); - } - exit(0); -} - diff --git a/source/piplib.c b/source/piplib.c index 1a9331f..06de8f6 100644 --- a/source/piplib.c +++ b/source/piplib.c @@ -31,14 +31,80 @@ # include #include +#define min(x,y) ((x) < (y)? (x) : (y)) + +Entier UN; +Entier ZERO; + +long int cross_product, limit; +int allocation, comptage; +int verbose = 0; +int profondeur = 0; +int compa_count; + +FILE *dump = NULL; +char dump_name[] = "PipXXXXXX"; + +#define INLENGTH 1024 + +char inbuff[INLENGTH]; +int inptr = 256; +int proviso = 0; + + +/****************************************************************************** + * Fonctions d'acquisition de données (ex-maind.c) * + ******************************************************************************/ + + +int dgetc(FILE *foo) +{ + char *p; + if(inptr >= proviso) + {p = fgets(inbuff, INLENGTH, foo); + if(p == NULL) return EOF; + proviso = min(INLENGTH, strlen(inbuff)); + inptr = 0; + if(verbose > 0) fprintf(dump, "-- %s", inbuff); + } + return inbuff[inptr++]; +} + + +#if defined(LINEAR_VALUE_IS_MP) +int dscanf(FILE *foo, int *val) +#else +int dscanf(FILE *foo, Entier *val) +#endif +{ + char * p; + int c; + + for(;inptr < proviso; inptr++) + if(inbuff[inptr] != ' ' && inbuff[inptr] != '\n' && inbuff[inptr] != '\t') + break; + while(inptr >= proviso) + {p = fgets(inbuff, 256, foo); + if(p == NULL) return EOF; + proviso = strlen(inbuff); + if(verbose > 0) { + fprintf(dump, ".. %s", inbuff); + fflush(dump); + } + for(inptr = 0; inptr < proviso; inptr++) + if(inbuff[inptr] != ' ' + && inbuff[inptr] != '\n' + && inbuff[inptr] != '\t') break; + } + if(sscanf(inbuff+inptr, FORMAT, val) != 1) + return -1; + + for(; inptr < proviso; inptr++) + if((c = inbuff[inptr]) != '-' && !isdigit(c)) break; + return 0; +} + -extern long int cross_product, limit ; -extern int verbose ; -extern FILE * dump ; -extern int compa_count ; -extern char dump_name[] ; - - /****************************************************************************** * Fonctions d'affichage des structures * ******************************************************************************/ @@ -58,7 +124,13 @@ void pip_matrix_print(FILE * foo, PipMatrix * Mat) for (i=0;ip+i) ; for (j=0;jnb_elements;i++) { fprintf(foo," ") ; + #if defined(LINEAR_VALUE_IS_MP) + mpz_out_str(foo,10,vector->the_vector[i]) ; + if (mpz_cmp(vector->the_deno[i],UN) != 0) + #else fprintf(foo,FORMAT,vector->the_vector[i]) ; if (vector->the_deno[i] != UN) + #endif { fprintf(foo,"/") ; + #if defined(LINEAR_VALUE_IS_MP) + mpz_out_str(foo,10,vector->the_deno[i]) ; + #else fprintf(foo,FORMAT,vector->the_deno[i]) ; + #endif } } fprintf(foo,"]") ; @@ -106,7 +187,11 @@ void pip_newparm_print(FILE * foo, PipNewparm * newparm, int indent) fprintf(foo," (div ") ; pip_vector_print(foo,newparm->vector) ; fprintf(foo," ") ; + #if defined(LINEAR_VALUE_IS_MP) + mpz_out_str(foo,10,newparm->deno) ; + #else fprintf(foo,FORMAT,newparm->deno) ; + #endif fprintf(foo,"))\n") ; } while ((newparm = newparm->next) != NULL) ; @@ -196,7 +281,18 @@ void pip_quast_print(FILE * foo, PipQuast * solution, int indent) * Premiere version : Ced. 29 juillet 2001. */ void pip_matrix_free(PipMatrix * matrix) -{ if (matrix != NULL) +{ + #if defined(LINEAR_VALUE_IS_MP) + int i, j ; + Entier * p ; + + p = matrix->p_Init ; + for (i=0;iNbRows;i++) + for (j=0;jNbColumns;j++) + mpz_clear(*p++) ; + #endif + + if (matrix != NULL) { free(matrix->p_Init) ; free(matrix->p) ; free(matrix) ; @@ -211,7 +307,17 @@ void pip_matrix_free(PipMatrix * matrix) * 18 octobre 2001 : simplification suite a l'eclatement de PipVector. */ void pip_vector_free(PipVector * vector) -{ free(vector->the_vector) ; +{ + #if defined(LINEAR_VALUE_IS_MP) + int i ; + + for (i=0;inb_elements;i++) + { mpz_clear(vector->the_vector[i]); + mpz_clear(vector->the_deno[i]); + } + #endif + + free(vector->the_vector) ; free(vector->the_deno) ; free(vector) ; } @@ -228,6 +334,9 @@ void pip_newparm_free(PipNewparm * newparm) while (newparm != NULL) { next = newparm->next ; + #if defined(LINEAR_VALUE_IS_MP) + mpz_clear(newparm->deno); + #endif pip_vector_free(newparm->vector) ; free(newparm) ; newparm = next ; @@ -304,7 +413,7 @@ PipMatrix * pip_matrix_alloc(unsigned NbRows, unsigned NbColumns) matrix->NbColumns = NbColumns ; if (NbRows == 0) { matrix->p = NULL ; - matrix->p_Init= NULL ; + matrix->p_Init = NULL ; } else { if (NbColumns == 0) @@ -327,7 +436,11 @@ PipMatrix * pip_matrix_alloc(unsigned NbRows, unsigned NbColumns) for (i=0;i -# include -# include - -#include - -extern long int cross_product, limit ; -extern int verbose ; -extern FILE * dump ; -extern int compa_count ; -extern char dump_name[] ; - - -/****************************************************************************** - * Fonctions d'affichage des structures * - ******************************************************************************/ - - -/* Fonction pip_matrix_print : - * Cette fonction se charge d'imprimer sur le flux 'foo' les informations - * que contient la structure de type PipMatrix qu'elle recoit en parametre. - * Premiere version : Ced. 29 juillet 2001. - * 24 octobre 2002 : premiere version MP. - */ -void pip_matrix_print(FILE * foo, PipMatrix * Mat) -{ Entier * p; - int i, j ; - unsigned NbRows, NbColumns ; - - fprintf(foo,"%d %d\n", NbRows=Mat->NbRows, NbColumns=Mat->NbColumns) ; - for (i=0;ip+i) ; - for (j=0;jnb_elements;i++) - { fprintf(foo," ") ; - mpz_out_str(foo,10,vector->the_vector[i]) ; - if (mpz_cmp(vector->the_deno[i],UN) != 0) - { fprintf(foo,"/") ; - mpz_out_str(foo,10,vector->the_deno[i]) ; - } - } - fprintf(foo,"]") ; - } -} - - -/* Fonction pip_newparm_print : - * Cette fonction se charge d'imprimer sur le flux 'foo' les informations - * que contient la structure de type PipNewparm qu'elle recoit en parametre. - * Le parametre indent est le nombre d'espaces blancs en debut de chaque - * ligne avant indentation. Une valeur negative de indent signifie qu'on ne - * desire pas d'indentation. - * Premiere version : Ced. 18 octobre 2001. - * 24 octobre 2002 : premiere version MP. - */ -void pip_newparm_print(FILE * foo, PipNewparm * newparm, int indent) -{ int i ; - - if (newparm != NULL) - { do - { for (i=0;irank) ; - fprintf(foo," (div ") ; - pip_vector_print(foo,newparm->vector) ; - fprintf(foo," ") ; - mpz_out_str(foo,10,newparm->deno) ; - fprintf(foo,"))\n") ; - } - while ((newparm = newparm->next) != NULL) ; - } -} - - -/* Fonction pip_list_print : - * Cette fonction se charge d'imprimer sur le flux 'foo' les informations - * que contient la structure de type PipList qu'elle recoit en parametre. - * Le parametre indent est le nombre d'espaces blancs en debut de chaque - * ligne avant indentation. Une valeur negative de indent signifie qu'on ne - * desire pas d'indentation. - * Premiere version : Ced. 18 octobre 2001. - */ -void pip_list_print(FILE * foo, PipList * list, int indent) -{ int i ; - - if (list == NULL) - { for (i=0;ivector) ; - fprintf(foo,"\n") ; - } - while ((list = list->next) != NULL) ; - for (i=0;inewparm,indent) ; - if (solution->condition == NULL) - pip_list_print(foo,solution->list,indent) ; - else - { for (i=0;icondition) ; - fprintf(foo,"\n") ; - if (indent>=0) /* Indent. */ - { pip_quast_print(foo,solution->next_then,indent+1) ; - pip_quast_print(foo,solution->next_else,indent+1) ; - } - else - { pip_quast_print(foo,solution->next_then,indent) ; - pip_quast_print(foo,solution->next_else,indent) ; - } - for (i=0;ip_Init ; - for (i=0;iNbRows;i++) - for (j=0;jNbColumns;j++) - mpz_clear(*p++) ; - - if (matrix != NULL) - { free(matrix->p_Init) ; - free(matrix->p) ; - free(matrix) ; - } -} - - -/* Fonction pip_vector_free : - * Cette fonction libere la memoire reservee a la structure de type PipVector - * que pointe son parametre. - * 20 juillet 2001 : Premiere version, Ced. - * 18 octobre 2001 : simplification suite a l'eclatement de PipVector. - * 24 octobre 2002 : premiere version MP. - */ -void pip_vector_free(PipVector * vector) -{ int i ; - - for (i=0;inb_elements;i++) - { mpz_clear(vector->the_vector[i]); - mpz_clear(vector->the_deno[i]); - } - free(vector->the_vector) ; - free(vector->the_deno) ; - free(vector) ; -} - - -/* Fonction pip_newparm_free : - * Cette fonction libere la memoire reservee a la structure de type PipNewparm - * que pointe son parametre. Sont liberes aussi tous les elements de la - * liste chainee dont il pouvait etre le depart. - * Premiere version : Ced. 18 octobre 2001. - * 24 octobre 2002 : premiere version MP. - */ -void pip_newparm_free(PipNewparm * newparm) -{ PipNewparm * next ; - - while (newparm != NULL) - { next = newparm->next ; - mpz_clear(newparm->deno); - pip_vector_free(newparm->vector) ; - free(newparm) ; - newparm = next ; - } -} - - -/* Fonction pip_list_free : - * Cette fonction libere la memoire reservee a la structure de type PipList - * que pointe son parametre. Sont liberes aussi tous les elements de la - * liste chainee dont il pouvait etre le depart. - * Premiere version : Ced. 18 octobre 2001. - */ -void pip_list_free(PipList * list) -{ PipList * next ; - - while (list != NULL) - { next = list->next ; - pip_vector_free(list->vector) ; - free(list) ; - list = next ; - } -} - - -/* Fonction pip_quast_free : - * Cette fonction libere la memoire reservee a la structure de type - * PipSolution que pointe son parametre. Sont liberees aussi toutes les - * differentes listes chainees qui pouvaient en partir. - * 20 juillet 2001 : Premiere version, Ced. - * 18 octobre 2001 : simplification suite a l'eclatement de PipVector. - */ -void pip_quast_free(PipQuast * solution) -{ if (solution != NULL) - { if (solution->newparm != NULL) - pip_newparm_free(solution->newparm) ; - - if (solution->list != NULL) - pip_list_free(solution->list) ; - - if (solution->condition != NULL) - { pip_vector_free(solution->condition) ; - pip_quast_free(solution->next_then) ; - pip_quast_free(solution->next_else) ; - } - free(solution) ; - } -} - - -/****************************************************************************** - * Fonctions d'acquisition de matrices * - ******************************************************************************/ - - -/* Fonction pip_matrix_alloc : - * Fonction (tres) modifiee de Matrix_Alloc de la polylib. Elle alloue l'espace - * memoire necessaire pour recevoir le contenu d'une matrice de NbRows lignes - * et de NbColumns colonnes, et initialise les valeurs a 0. Elle retourne un - * pointeur sur l'espace memoire alloue. - * Premiere version : Ced. 18 octobre 2001. - * 24 octobre 2002 : premiere version MP. - */ -PipMatrix * pip_matrix_alloc(unsigned NbRows, unsigned NbColumns) -{ PipMatrix * matrix ; - Entier ** p, * q ; - int i, j ; - - matrix = (PipMatrix *)malloc(sizeof(PipMatrix)) ; - if (matrix == NULL) - { fprintf(stderr, "Memory Overflow.\n") ; - exit(1) ; - } - matrix->NbRows = NbRows ; - matrix->NbColumns = NbColumns ; - if (NbRows == 0) - { matrix->p = NULL ; - matrix->p_Init = NULL ; - } - else - { if (NbColumns == 0) - { matrix->p = NULL ; - matrix->p_Init = NULL ; - } - else - { p = (Entier **)malloc(NbRows*sizeof(Entier *)) ; - if (p == NULL) - { fprintf(stderr, "Memory Overflow.\n") ; - exit(1) ; - } - q = (Entier *)malloc(NbRows * NbColumns * sizeof(Entier)) ; - if (q == NULL) - { fprintf(stderr, "Memory Overflow.\n") ; - exit(1) ; - } - matrix->p = p ; - matrix->p_Init = q ; - for (i=0;ip_Init ; - for (i=0;iNbRows;i++) - { do - { c = fgets(s,1024,foo) ; - while (isspace(*c) && (*c != '\n')) - c++ ; - } - while (c != NULL && (*c == '#' || *c == '\n')); - - if (c == NULL) - { fprintf(stderr, "Not enough rows.\n") ; - exit(1) ; - } - for (j=0;jNbColumns;j++) - { if (c == NULL || *c == '#' || *c == '\n') - { fprintf(stderr, "Not enough columns.\n") ; - exit(1) ; - } - /* NdCed : Dans le n ca met strlen(str). */ - if (sscanf(c,"%s%n",str,&n) == 0) - { fprintf(stderr, "Not enough rows.\n") ; - exit(1) ; - } - sscanf(str,FORMAT,&val) ; - mpz_init_set_si(*p++,val) ; - c += n ; - } - } - return matrix ; -} - - -/****************************************************************************** - * Fonction de resolution * - ******************************************************************************/ - - -/* Fonction pip_solve : - * Cette fonction fait un appel a Pip pour la resolution d'un probleme. Le - * probleme est fourni dans les arguments. Deux matrices de la forme de celles - * utilisees dans la Polylib forment les systemes d'equations/inequations : - * un pour les inconnues, l'autre pour les parametres. Bg est le 'bignum', Nq - * est un booleen renseignant si on cherche une solution entiere (vrai=1) ou - * non (faux=0). Verbose est un booleen permettant de rendre Pip bavard - * (Verbose a vrai=1), il imprimera alors la plupart de ses traitements dans le - * fichier dont le nom est dans la variable d'environnement DEBUG, ou si DEBUG - * n'est pas placee, dans un nouveau fichier de nom genere par mkstemp, si - * Verbose est a faux=0, Pip restera muet. Simplify est un booleen permettant - * de demander a Pip de simplifier sa solution (en eliminant les formes de type - * 'if #[...] () ()') quand il est a vrai=1, ou non quand il est a faux=0. Max - * n'est pas encore utilise et doit etre mis a 0. Cette fonction retourne la - * solution sous la forme d'un arbre de structures PipQuast. - * 30 juillet 2001 : Premiere version, Ced. - * 18 octobre 2001 : suppression de l'argument Np, le nombre de parametres. Il - * est a present deduit de ineqpar. Si ineqpar vaut NULL, - * c'est que Np vaut 0. S'il y a des parametres mais pas de - * contraintes dessus, ineqpar sera une matrice de 0 lignes - * mais du bon nombre de colonnes (Np + 2). - * 24 octobre 2002 : premiere version MP. - */ -PipQuast * pip_solve(inequnk, ineqpar, Bg, Nq, Verbose, Simplify, Max) -PipMatrix * inequnk, * ineqpar ; -int Bg, Nq, Verbose, Simplify, Max ; -{ Tableau * ineq, * context, * ctxt ; - int i, Np, Nn, Nl, Nm, p, q, xq, non_vide ; - char * g ; - struct high_water_mark hq ; - PipQuast * solution ; - - mpz_init_set_si(UN, 1); - mpz_init_set_si(ZERO, 0); - - /* initialisations diverses : - * - la valeur de Verbose est placee dans sa variable globale. Dans le cas - * ou on doit etre en mode verbose, on ouvre le fichier dans lequel - * ecrire les tracages. Si la variable d'environnement DEBUG est placee, - * on ecrira dans le nom de fichier correspondant, sinon, dans un nouveau - * fichier de nom genere par mkstemp, - * - limit est mis au 0 long int (sa valeur par defaut dans Pip original), - * - on lance les initialisations pour tab et sol (autres mises en place - * de variables globales). - */ - verbose = Verbose ; - if (verbose) - { g = getenv("DEBUG") ; - if(g && *g) - { dump = fopen(g, "w") ; - if(dump == NULL) - { fprintf(stderr,"%s unaccessible\n",g) ; - verbose = 0 ; - } - } - else - { mkstemp(dump_name) ; - dump = fopen(dump_name, "w") ; - } - } - limit = 0LL ; - sol_init() ; - tab_init() ; - - /* Si inequnk est NULL, la solution est automatiquement void (NULL). */ - if (inequnk != NULL) - { /* Np vaut 0 si ineqpar vaut NULL, ineqpar->NbColumns - 2 sinon (on a -1 - * pour la constante et -1 pour le marqueur d'egalite/inegalite = -2). - */ - Np = (ineqpar == NULL) ? 0 : ineqpar->NbColumns - 2 ; - /* Calcul du nombre d'inconnues du probleme. Comme les matrices d'entree - * sont sous la forme de la polylib. - */ - Nn = inequnk->NbColumns - Np - 2 ; - /* Calcul du nombre d'inequations du probleme. Le format de matrice de la - * polylib permet les egalites, on doit donc les compter double quand il - * y en a. - */ - Nl = inequnk->NbRows ; - for (i=0;iNbRows;i++) - if (**(inequnk->p + i) == 0) - Nl ++ ; - - /* On prend les 'marques' de debut de traitement. */ - cross_product = 0 ; - hq = tab_hwm() ; - xq = p = sol_hwm(); - - /* On s'assure d'abord que le systeme pour le contexte n'est pas vide - * avant de commencer le traitement. Si c'est le cas, la solution est - * void (NULL). - */ - if (ineqpar != NULL) - { Nm = ineqpar->NbRows ; - for (i=0;iNbRows;i++) - if (**(ineqpar->p + i) == 0) - Nm ++ ; - context = tab_Matrix2Tableau(ineqpar,Nm,Np,0) ; - if (Nm) - { /* Traduction du format de matrice de la polylib vers celui de - * traitement de Pip. Puis traitement proprement dit. - */ - ctxt = expanser(context, Np, Nm, Np+1, Np, 0, 0) ; - traiter(ctxt, NULL, True, Np, 0, Nm, 0, -1) ; - non_vide = is_not_Nil(p) ; - sol_reset(p) ; - } - else - non_vide = True ; - } - else - { Nm = 0 ; - context = NULL ; /* ATTENTION, en toute rigueur on devrait faire un - * tab_Matrix2Tableau d'une matrice 0*0. - */ - non_vide = True ; - } - - if (verbose) - fprintf(dump, "%d %d %d %d %d %d\n",Nn, Np, Nl, Nm, Bg, Nq) ; - - /* S'il est possible de trouver une solution, on passe au traitement. */ - if (non_vide) - { ineq = tab_Matrix2Tableau(inequnk,Nl,Nn,Nn) ; - compa_count = 0 ; - traiter(ineq, context, Nq, Nn, Np, Nl, Nm, Bg) ; - - if (Simplify) - sol_simplify(xq) ; - q = sol_hwm() ; - /* On traduit la solution du format de solution de Pip vers un arbre - * de structures de type PipQuast. - */ - solution = sol_quast_edit(&xq,NULL) ; - sol_reset(p) ; - } - else - return NULL ; - tab_reset(hq) ; - } - else - return NULL ; - - return(solution) ; -} diff --git a/source/sol.c b/source/sol.c index b43710c..10779c8 100644 --- a/source/sol.c +++ b/source/sol.c @@ -52,6 +52,7 @@ struct S struct S sol_space[SOL_SIZE]; static int sol_free; +#if !defined(LINEAR_VALUE_IS_MP) Entier mod(Entier, Entier); Entier pgcd(Entier x, Entier y) @@ -63,6 +64,7 @@ Entier pgcd(Entier x, Entier y) } return(x>= 0? x : -x); } +#endif void sol_init(void) { @@ -76,11 +78,17 @@ int sol_hwm() void sol_reset(p) int p; -{ +{int i; if(p<0 || p>=SOL_SIZE) {fprintf(stderr, "Syserr : sol_reset : Memory allocation error\n"); exit(40); } + #if defined(LINEAR_VALUE_IS_MP) + for(i=p; iflags = Free; + #if defined(LINEAR_VALUE_IS_MP) + mpz_init_set_si(r->param1,0); + mpz_init_set_si(r->param2,0); + #else r->param1 = r->param2 = 0; + #endif sol_free++; if(sol_free >= SOL_SIZE) {fprintf(stderr, "The solution is too complex! : sol\n"); @@ -113,7 +126,11 @@ void sol_error(int c) struct S *r; r = sol_alloc(); r->flags = Nil; + #if defined(LINEAR_VALUE_IS_MP) + mpz_set_si(r->param1, c); + #else r->param1 = c; + #endif if(verbose > 0) { fprintf(dump, "Erreur %d\n", c); fflush(dump); @@ -142,7 +159,11 @@ int n; {struct S * r; r = sol_alloc(); r->flags = List; + #if defined(LINEAR_VALUE_IS_MP) + mpz_set_si(r->param1, n); + #else r->param1 = n; + #endif if(verbose > 0) { fprintf(dump, "\nList %d ", n); fflush(dump); @@ -155,7 +176,11 @@ int l; struct S *r; r = sol_alloc(); r -> flags = Form; + #if defined(LINEAR_VALUE_IS_MP) + mpz_set_ui(r -> param1, l); + #else r -> param1 = l; + #endif if(verbose > 0) { fprintf(dump, "\nForme %d ", l); fflush(dump); @@ -168,7 +193,11 @@ int k; struct S *r; r = sol_alloc(); r -> flags = New; + #if defined(LINEAR_VALUE_IS_MP) + mpz_set_ui(r -> param1, k); + #else r -> param1 = k; + #endif if(verbose > 0) { fprintf(dump, "New %d ", k); fflush(dump); @@ -192,13 +221,24 @@ Entier n, d; struct S *r; r = sol_alloc(); r -> flags = Val; + #if defined(LINEAR_VALUE_IS_MP) + mpz_set(r -> param1, n); + mpz_set(r -> param2, d); + #else r -> param1 = n; r -> param2 = d; + #endif if(verbose > 0) { fprintf(dump, "val("); + #if defined(LINEAR_VALUE_IS_MP) + mpz_out_str(dump, 10, n); + fprintf(dump, "/"); + mpz_out_str(dump, 10, d); + #else fprintf(dump, FORMAT, n); fprintf(dump, "/"); fprintf(dump, FORMAT, d); + #endif fprintf(dump, ") "); fflush(dump); } @@ -229,7 +269,12 @@ int skip (int i) case If : i = skip(i+1); /* sauter le pre'dicat */ i = skip(i); /* sauter le vrai */ i = skip(i); break; /* sauter le faux */ - case List : case Form : n = sol_space[i].param1; + case List : case Form : + #if defined(LINEAR_VALUE_IS_MP) + n = mpz_get_si(sol_space[i].param1); + #else + n = sol_space[i].param1; + #endif i++; while(n--) i = skip(i); break; @@ -247,8 +292,8 @@ int skip (int i) void sol_simplify(int i) {int j, k, l; if(sol_space[i].flags == If) { - j = skip(i+1); /* j : de'but de la partie vraie */ - k = skip(j); /* k : d‚but de la partie fausse */ + j = skip(i+1); /* j : debut de la partie vraie */ + k = skip(j); /* k : debut de la partie fausse */ sol_simplify(k); sol_simplify(j); if(sol_space[j].flags == Nil && sol_space[k].flags == Nil) { @@ -265,6 +310,12 @@ int sol_edit(FILE *foo, int i) {int j, n; struct S *p; Entier N, D, d; + #if defined(LINEAR_VALUE_IS_MP) + mpz_init(N); + mpz_init(D); + mpz_init(d); + #endif + p = sol_space + i; for(;;) { if(p->flags == Free) { @@ -273,7 +324,11 @@ int sol_edit(FILE *foo, int i) continue; } if(p->flags == New) { + #if defined(LINEAR_VALUE_IS_MP) + n = mpz_get_si(p->param1); + #else n = p->param1; + #endif fprintf(foo, "(newparm %d ", n); if(verbose>0)fprintf(dump, "(newparm %d ", n); i = sol_edit(foo, ++i); @@ -288,8 +343,16 @@ int sol_edit(FILE *foo, int i) case Nil : fprintf(foo, "()\n"); if(verbose>0)fprintf(dump, "()\n"); i++; break; - case Error : fprintf(foo, "Error %d\n", p->param1); - if(verbose>0)fprintf(dump, "Error %d\n", p->param1); + case Error : + #if defined(LINEAR_VALUE_IS_MP) + fprintf(foo, "Error %d\n", mpz_get_si(p->param1)); + if(verbose>0) + fprintf(dump, "Error %d\n", mpz_get_si(p->param1)); + #else + fprintf(foo, "Error %d\n", p->param1); + if(verbose>0) + fprintf(dump, "Error %d\n", p->param1); + #endif i++; break; case If : fprintf(foo, "(if "); if(verbose>0)fprintf(dump, "(if "); @@ -301,7 +364,11 @@ int sol_edit(FILE *foo, int i) break; case List: fprintf(foo, "(list "); if(verbose>0)fprintf(dump, "(list "); + #if defined(LINEAR_VALUE_IS_MP) + n = mpz_get_si(p->param1); + #else n = p->param1; + #endif i++; while(n--) i = sol_edit(foo, i); fprintf(foo, ")\n"); @@ -309,9 +376,40 @@ int sol_edit(FILE *foo, int i) break; case Form: fprintf(foo, "#["); if(verbose>0)fprintf(dump, "#["); + #if defined(LINEAR_VALUE_IS_MP) + n = mpz_get_si(p->param1); + #else n = p->param1; + #endif for(j = 0; jparam1); mpz_set(D, p->param2); + mpz_gcd(d, N, D); + if(mpz_cmp(d, D) == 0){ + putc(' ', foo); + mpz_divexact(N, N, d); + mpz_out_str(foo, 10, N); + if(verbose>0){ + putc(' ', dump); + mpz_out_str(dump, 10, N); + } + } + else{ + mpz_divexact(N, N, d); + mpz_divexact(D, D, d); + putc(' ', foo); + mpz_out_str(foo, 10, N); + putc('/', foo); + mpz_out_str(foo, 10, D); + if(verbose>0){ + putc(' ', dump); + mpz_out_str(dump, 10, N); + putc('/', dump); + mpz_out_str(dump, 10, D); + } + } + #else N = p->param1; D = p->param2; d = pgcd(N, D); if(d == D){ @@ -334,6 +432,7 @@ int sol_edit(FILE *foo, int i) fprintf(dump,FORMAT, D/d); } } + #endif } fprintf(foo, "]\n"); if(verbose>0)fprintf(dump, "]\n"); @@ -346,7 +445,35 @@ int sol_edit(FILE *foo, int i) fprintf(foo, ")\n"); if(verbose>0)fprintf(dump, ")\n"); break; - case Val : N = p->param1; D = p->param2; + case Val : + #if defined(LINEAR_VALUE_IS_MP) + mpz_set(N, p->param1); mpz_set(D, p->param2); + mpz_gcd(d, N, D); + if(mpz_cmp(d, D) == 0){ + mpz_divexact(N, N, d); + putc(' ', foo); + mpz_out_str(foo, 10, N); + if(verbose>0){ + putc(' ', dump); + mpz_out_str(dump, 10, N); + } + } + else{ + mpz_divexact(N, N, d); + mpz_divexact(D, D, d); + putc(' ', foo); + mpz_out_str(foo, 10, N); + fprintf(foo, "/"); + mpz_out_str(foo, 10, D); + if(verbose>0){ + putc(' ', dump); + mpz_out_str(dump, 10, N); + fprintf(dump, "/"); + mpz_out_str(dump, 10, D); + } + } + #else + N = p->param1; D = p->param2; d = pgcd(N, D); if(d == D){putc(' ', foo); fprintf(foo, FORMAT, N/d); @@ -366,11 +493,17 @@ int sol_edit(FILE *foo, int i) fprintf(dump, FORMAT, D/d); } } + #endif i++; break; default : fprintf(foo, "Inconnu : sol\n"); if(verbose>0)fprintf(dump, "Inconnu : sol\n"); } + #if defined(LINEAR_VALUE_IS_MP) + mpz_clear(d); + mpz_clear(D); + mpz_clear(N); + #endif return(i); } @@ -389,6 +522,12 @@ PipVector * sol_vector_edit(int * i) struct S *p ; Entier N, D, d ; PipVector * vector ; + + #if defined(LINEAR_VALUE_IS_MP) + mpz_init(N) ; + mpz_init(D) ; + mpz_init(d) ; + #endif vector = (PipVector *)malloc(sizeof(PipVector)) ; if (vector == NULL) @@ -396,7 +535,11 @@ PipVector * sol_vector_edit(int * i) exit(1) ; } p = sol_space + (*i) ; + #if defined(LINEAR_VALUE_IS_MP) + n = mpz_get_si(p->param1) ; + #else n = p->param1 ; + #endif vector->nb_elements = n ; vector->the_vector = (Entier *)malloc(sizeof(Entier)*n) ; if (vector->the_vector == NULL) @@ -412,18 +555,36 @@ PipVector * sol_vector_edit(int * i) for (j=0;jparam1) ; + mpz_set(D,p->param2) ; + mpz_gcd(d, N, D); + mpz_init(vector->the_vector[j]) ; + mpz_divexact(vector->the_vector[j],N,d) ; + mpz_init(vector->the_deno[j]) ; + if (mpz_cmp(d, D) == 0) + mpz_set(vector->the_deno[j],UN) ; + else + mpz_divexact(vector->the_deno[j],D,d) ; + #else N = p->param1 ; D = p->param2 ; d = pgcd(N, D) ; - vector->the_vector[j] = N/d ; if (d == D) vector->the_deno[j] = UN ; else vector->the_deno[j] = D/d ; + #endif } (*i)++ ; + #if defined(LINEAR_VALUE_IS_MP) + mpz_clear(d); + mpz_clear(D); + mpz_clear(N); + #endif + return(vector) ; } @@ -452,10 +613,16 @@ PipNewparm * sol_newparm_edit(int * i) exit(1) ; } newparm->vector = sol_vector_edit(i) ; - newparm->rank = p->param1 ; + #if defined(LINEAR_VALUE_IS_MP) + newparm->rank = mpz_get_si(p->param1) ; /* On met p a jour pour lire le denominateur (un Val de param2 UN). */ p = sol_space + (*i) ; + mpz_init_set(newparm->deno,p->param1) ; + #else + newparm->rank = p->param1 ; + p = sol_space + (*i) ; newparm->deno = p->param1 ; + #endif newparm->next = NULL ; newparm_now = newparm ; @@ -465,7 +632,11 @@ PipNewparm * sol_newparm_edit(int * i) fprintf(dump," (div ") ; pip_vector_print(dump,newparm->vector) ; fprintf(dump," ") ; + #if defined(LINEAR_VALUE_IS_MP) + mpz_out_str(dump,10,newparm->deno) ; + #else fprintf(dump,FORMAT,newparm->deno) ; + #endif fprintf(dump,"))") ; } @@ -480,9 +651,15 @@ PipNewparm * sol_newparm_edit(int * i) exit(1) ; } newparm_new->vector = sol_vector_edit(i) ; + #if defined(LINEAR_VALUE_IS_MP) + newparm_new->rank = mpz_get_si(p->param1) ; + p = sol_space + (*i) ; + mpz_init_set(newparm_new->deno,p->param1) ; + #else newparm_new->rank = p->param1 ; p = sol_space + (*i) ; newparm_new->deno = p->param1 ; + #endif newparm_new->next = NULL ; newparm_now->next = newparm_new ; @@ -493,7 +670,11 @@ PipNewparm * sol_newparm_edit(int * i) fprintf(dump," (div ") ; pip_vector_print(dump,newparm_new->vector) ; fprintf(dump," ") ; + #if defined(LINEAR_VALUE_IS_MP) + mpz_out_str(dump,10,newparm_new->deno) ; + #else fprintf(dump,FORMAT,newparm_new->deno) ; + #endif fprintf(dump,"))") ; } (*i) ++ ; @@ -614,7 +795,12 @@ PipQuast * sol_quast_edit(int * i, PipQuast * father) /* ...ensuite soit par une liste (vide ou non) soit par un if. */ (*i)++ ; /* Factorise de List, Nil et If. */ switch (p->flags) - { case List : if ((nb_elements = p->param1) != 0) + { case List : + #if defined(LINEAR_VALUE_IS_MP) + if ((nb_elements = mpz_get_si(p->param1)) != 0) + #else + if ((nb_elements = p->param1) != 0) + #endif solution->list = sol_list_edit(i,nb_elements) ; break ; case Nil : if (verbose) diff --git a/source/solMP.c b/source/solMP.c deleted file mode 100644 index b00002c..0000000 --- a/source/solMP.c +++ /dev/null @@ -1,692 +0,0 @@ -/********************************************************/ -/* Part of MultiPrecision PIP port (C) Zbigniew Chamski */ -/* and Paul Feautrier. */ -/* Based on straight PIP version E.1 by Paul Feautrier */ -/* () */ -/* */ -/* and a previous port (C) Zbigniew CHAMSKI, 1993. */ -/* (Zbigniew.Chamski@philips.com) */ -/* */ -/* Copying subject to the terms and conditions of the */ -/* GNU General Public License. */ -/* */ -/* Send questions, bug reports and fixes to: */ -/* */ -/********************************************************/ - -#include -#include -#include - -#include - -extern long int cross_product, limit; -extern int verbose; -extern FILE *dump; - -struct S - {int flags; - Entier param1, param2; - }; - -/* In some cases, param1 and param2 are used to store small integers. - These integers are nevertheless converted to bignums in the - interest of simplicity. Since the handling of the solution is - a negligible part of the algorithm, the corresponding overhead is - deemed negligible. -*/ - - -#define Free 0 -#define Nil 1 -#define If 2 -#define List 3 -#define Form 4 -#define New 5 -#define Div 6 -#define Val 7 -#define Error 8 - -struct S sol_space[SOL_SIZE]; -static int sol_free; - -/* pgcd has been removed and replaced by mpz_gcd - */ - -void sol_init(void) -{ - sol_free = 0; -} - -int sol_hwm() -{ - return(sol_free); -} - -void sol_reset(p) -int p; -{int i; - if(p<0 || p>=SOL_SIZE) - {fprintf(stdout, "Syserr : sol_reset : Memory allocation error\n"); - exit(40); - } - for(i=p; iflags = Free; - mpz_init(r->param1); - mpz_init(r->param2); - sol_free++; - if(sol_free >= SOL_SIZE) - {fprintf(stdout, "The solution is too complex! : sol\n"); - exit(26); - } - return(r); -} - -void sol_nil(void) -{ - struct S * r; - r = sol_alloc(); - r -> flags = Nil; - if(verbose > 0) - {fprintf(dump, "\nNil"); - fflush(dump); - } -} - -void sol_error(int c) -{ - struct S *r; - r = sol_alloc(); - r->flags = Nil; - mpz_set_si(r->param1, c); - if(verbose > 0) { - fprintf(dump, "Erreur %d\n", c); - fflush(dump); - } -} - -int is_not_Nil(p) -int p; -{ - return(sol_space[p].flags != Nil); -} - -void sol_if(void) -{ - struct S *r; - r = sol_alloc(); - r -> flags = If; - if(verbose > 0) { - fprintf(dump, "\nIf "); - fflush(dump); - } -} - -void sol_list(n) -int n; -{struct S * r; - r = sol_alloc(); - r->flags = List; - mpz_set_si(r->param1, n); - if(verbose > 0) { - fprintf(dump, "\nList %d ", n); - fflush(dump); -} -} - -void sol_forme(l) -int l; -{ - struct S *r; - r = sol_alloc(); - r -> flags = Form; - mpz_set_ui(r -> param1, l); - if(verbose > 0) { - fprintf(dump, "\nForme %d ", l); - fflush(dump); - } -} - -void sol_new(k) -int k; -{ - struct S *r; - if(verbose > 0) { - fprintf(dump, "New %d ", k); - fflush(dump); - } - r = sol_alloc(); - r -> flags = New; - mpz_set_ui(r -> param1, k); -} - -void sol_div() -{ - struct S *r; - r = sol_alloc(); - r -> flags = Div; - if(verbose > 0) { - fprintf(dump, "Div "); - fflush(dump); - } -} - -void sol_val(n, d) -Entier n, d; -{ - struct S *r; - - r = sol_alloc(); - r -> flags = Val; - mpz_set(r -> param1, n); - mpz_set(r -> param2, d); - if(verbose > 0) { - fputs("val(", dump); - mpz_out_str(dump, 10, n); - putc('/', dump); - mpz_out_str(dump, 10, d); - fputs(") ", dump); - } -} - -int skip(int); - -/* a` partir d'un point de la solution, sauter un objet -bien forme' ainsi qu'un e'ventuel New et pointer sur l'objet -suivant */ - -int skip_New (int i) -{ - if(sol_space[i].flags != New) return i; - i = skip(i+1); /* sauter le Div */ - return i; -} -/* au lancement, i indexe une cellule qui est la te^te d'un objet. - la valeur retourne'e est la te^te de l'objet qui suit. Les - objets de type New sont e'limine's */ - -int skip (int i) -{int n, f; - while((f = sol_space[i].flags) == Free || f == Error) i++; - switch (sol_space[i].flags) { - case Nil : case Val : i++; break; - case New : i = skip_New(i); break; - case If : i = skip(i+1); /* sauter le pre'dicat */ - i = skip(i); /* sauter le vrai */ - i = skip(i); break; /* sauter le faux */ - case List : case Form : n = mpz_get_si(sol_space[i].param1); - i++; - while(n--) i = skip(i); - break; - case Div : i = skip(i+1); /* sauter la forme */ - i = skip(i); /* sauter le diviseur */ - break; - default : fprintf(stdout, - "Syserr : skip : unknown %d\n", sol_space[i].flags); - } - return skip_New(i); -} -/* simplification de la solution : e'limination des constructions - (if p () ()). N'est en service qu'en pre'sence de l'option -z */ - -void sol_simplify(int i) -{int j, k, l; - if(sol_space[i].flags == If) { - j = skip(i+1); /* j : de'but de la partie vraie */ - k = skip(j); /* k : de'but de la partie fausse */ - sol_simplify(k); - sol_simplify(j); - if(sol_space[j].flags == Nil && sol_space[k].flags == Nil) { - sol_space[i].flags = Nil; - if(k >= sol_free - 1) sol_free = i+1; - else for(l = i+1; l<=k; l++) sol_space[l].flags = Free; - } - } - -} -/* e'dition de la solution */ - -int sol_edit(FILE *foo, int i) -{int j, n; - struct S *p; - Entier N, D, d; - mpz_init(N); - mpz_init(D); - mpz_init(d); - p = sol_space + i; - for(;;) { - if(p->flags == Free) { - p++; - i++; - continue; - } - if(p->flags == New) { - n = mpz_get_si(p->param1); - fprintf(foo, "(newparm %d ", n); - if(verbose>0)fprintf(dump, "(newparm %d ", n); - i = sol_edit(foo, ++i); - p = sol_space +i; - fprintf(foo, ")\n"); - if(verbose>0)fprintf(dump, ")\n"); - continue; - } - break; - } - switch(p->flags) - { - case Nil : fprintf(foo, "()\n"); - if(verbose>0)fprintf(dump, "()\n"); - i++; break; - case Error : n = mpz_get_si(p->param1); - fprintf(foo, "Error %d\n", n); - if(verbose>0)fprintf(dump, "Error %d\n", n); - i++; break; - case If : fprintf(foo, "(if "); - if(verbose>0)fprintf(dump, "(if "); - i = sol_edit(foo, ++i); - i = sol_edit(foo, i); - i = sol_edit(foo, i); - fprintf(foo, ")\n"); - if(verbose>0)fprintf(dump, ")\n"); - break; - case List: fprintf(foo, "(list "); - if(verbose>0)fprintf(dump, "(list "); - n = mpz_get_si(p->param1); - i++; - while(n--) i = sol_edit(foo, i); - fprintf(foo, ")\n"); - if(verbose>0)fprintf(dump, ")\n"); - break; - case Form: fprintf(foo, "#["); - if(verbose>0)fprintf(dump, "#["); - n = mpz_get_si(p->param1); - for(j = 0; jparam1); mpz_set(D, p->param2); - mpz_gcd(d, N, D); - if(mpz_cmp(d, D) == 0){ - putc(' ', foo); - mpz_divexact(N, N, d); - mpz_out_str(foo, 10, N); - if(verbose>0){ - putc(' ', dump); - mpz_out_str(dump, 10, N); - } - } - else{ - mpz_divexact(N, N, d); - mpz_divexact(D, D, d); - putc(' ', foo); - mpz_out_str(foo, 10, N); - putc('/', foo); - mpz_out_str(foo, 10, D); - if(verbose>0){ - putc(' ', dump); - mpz_out_str(dump, 10, N); - putc('/', dump); - mpz_out_str(dump, 10, D); - } - } - } - fprintf(foo, "]\n"); - if(verbose>0) - fputs("]\n", dump); - i++; - break; - case Div : fprintf(foo, "(div "); - if(verbose>0)fprintf(dump, "(div "); - i = sol_edit(foo, ++i); - i = sol_edit(foo, i); - fprintf(foo, ")\n"); - if(verbose>0)fprintf(dump, ")\n"); - break; - case Val : mpz_set(N, p->param1); mpz_set(D, p->param2); - mpz_gcd(d, N, D); - if(mpz_cmp(d, D) == 0){ - mpz_divexact(N, N, d); - putc(' ', foo); - mpz_out_str(foo, 10, N); - if(verbose>0){ - putc(' ', dump); - mpz_out_str(dump, 10, N); - } - } - else{ - mpz_divexact(N, N, d); - mpz_divexact(D, D, d); - putc(' ', foo); - mpz_out_str(foo, 10, N); - fprintf(foo, "/"); - mpz_out_str(foo, 10, D); - if(verbose>0){ - putc(' ', dump); - mpz_out_str(dump, 10, N); - fprintf(dump, "/"); - mpz_out_str(dump, 10, D); - } - } - i++; - break; - default : fprintf(foo, "Inconnu : sol\n"); - if(verbose>0)fprintf(dump, "Inconnu : sol\n"); - } - mpz_clear(d); - mpz_clear(D); - mpz_clear(N); - return(i); -} - - - - - -/* Fonction sol_vector_edit : - * Cette fonction a pour but de placer les informations correspondant - * a un Vector dans la grammaire dans une structure de type PipVector. Elle - * prend en parametre un pointeur vers une case memoire contenant le - * numero de cellule du tableau sol_space a partir de laquelle on doit - * commencer la lecture des informations. Elle retourne un pointeur vers - * une structure de type PipVector contenant les informations de ce Vector. - * Premiere version : Ced. 20 juillet 2001. - * 24 octobre 2002 : Premiere version MP. - */ -PipVector * sol_vector_edit(int * i) -{ int j, n ; - struct S *p ; - Entier N, D, d ; - PipVector * vector ; - - mpz_init(N) ; - mpz_init(D) ; - mpz_init(d) ; - - vector = (PipVector *)malloc(sizeof(PipVector)) ; - if (vector == NULL) - { fprintf(stderr, "Memory Overflow.\n") ; - exit(1) ; - } - p = sol_space + (*i) ; - n = mpz_get_si(p->param1) ; - vector->nb_elements = n ; - vector->the_vector = (Entier *)malloc(sizeof(Entier)*n) ; - if (vector->the_vector == NULL) - { fprintf(stderr, "Memory Overflow.\n") ; - exit(1) ; - } - vector->the_deno = (Entier *)malloc(sizeof(Entier)*n) ; - if (vector->the_deno == NULL) - { fprintf(stderr, "Memory Overflow.\n") ; - exit(1) ; - } - - for (j=0;jparam1) ; - mpz_set(D,p->param2) ; - mpz_gcd(d, N, D); - - mpz_init(vector->the_vector[j]) ; - mpz_divexact(vector->the_vector[j],N,d) ; - - mpz_init(vector->the_deno[j]) ; - if (mpz_cmp(d, D) == 0) - mpz_set(vector->the_deno[j],UN) ; - else - mpz_divexact(vector->the_deno[j],D,d) ; - } - (*i)++ ; - - mpz_clear(d); - mpz_clear(D); - mpz_clear(N); - return(vector) ; -} - - -/* Fonction sol_newparm_edit : - * Cette fonction a pour but de placer les informations correspondant - * a un Newparm dans la grammaire dans une structure de type PipNewparm. Elle - * prend en parametre un pointeur vers une case memoire contenant le - * numero de cellule du tableau sol_space a partir de laquelle on doit - * commencer la lecture des informations. Elle retourne un pointeur vers - * une structure de type PipNewparm contenant les informations de ce Newparm. - * Premiere version : Ced. 18 octobre 2001. - * 24 octobre 2002 : Premiere version MP. - */ -PipNewparm * sol_newparm_edit(int * i) -{ struct S * p ; - PipNewparm * newparm, * newparm_new, * newparm_now ; - - /* On place p au lieu de lecture. */ - p = sol_space + (*i) ; - /* On passe le New et le Div pour aller a Form et lire le VECTOR. */ - (*i) += 2 ; - - newparm = (PipNewparm *)malloc(sizeof(PipNewparm)) ; - if (newparm == NULL) - { fprintf(stderr, "Memory Overflow.\n") ; - exit(1) ; - } - newparm->vector = sol_vector_edit(i) ; - newparm->rank = mpz_get_si(p->param1) ; - /* On met p a jour pour lire le denominateur (un Val de param2 UN). */ - p = sol_space + (*i) ; - mpz_init_set(newparm->deno,p->param1) ; - newparm->next = NULL ; - - newparm_now = newparm ; - if (verbose) - { fprintf(dump,"\n(newparm ") ; - fprintf(dump,"%d",newparm->rank) ; - fprintf(dump," (div ") ; - pip_vector_print(dump,newparm->vector) ; - fprintf(dump," ") ; - mpz_out_str(dump,10,newparm->deno) ; - fprintf(dump,"))") ; - } - - /* On passe aux elements suivants. */ - (*i) ++ ; - p = sol_space + (*i) ; - while (p->flags == New) - { (*i) += 2 ; - newparm_new = (PipNewparm *)malloc(sizeof(PipNewparm)) ; - if (newparm_new == NULL) - { fprintf(stderr, "Memory Overflow.\n") ; - exit(1) ; - } - newparm_new->vector = sol_vector_edit(i) ; - newparm_new->rank = mpz_get_si(p->param1) ; - p = sol_space + (*i) ; - mpz_init_set(newparm_new->deno,p->param1) ; - newparm_new->next = NULL ; - - newparm_now->next = newparm_new ; - newparm_now = newparm_now->next ; - if (verbose) - { fprintf(dump,"\n(newparm ") ; - fprintf(dump,"%d",newparm_new->rank) ; - fprintf(dump," (div ") ; - pip_vector_print(dump,newparm_new->vector) ; - fprintf(dump," ") ; - mpz_out_str(dump,10,newparm_new->deno) ; - fprintf(dump,"))") ; - } - (*i) ++ ; - p = sol_space + (*i) ; - } - return(newparm) ; -} - - -/* Fonction sol_list_edit : - * Cette fonction a pour but de placer les informations correspondant - * a une List dans la grammaire dans une structure de type PipList. Elle - * prend en parametre un pointeur vers une case memoire contenant le - * numero de cellule du tableau sol_space a partir de laquelle on doit - * commencer la lecture des informations. Elle retourne un pointeur vers - * une structure de type PipList contenant les informations de cette List. - * Premiere version : Ced. 18 octobre 2001. - */ -PipList * sol_list_edit(int * i, int nb_elements) -{ PipList * list, * list_new, * list_now ; - - /* Pour le premier element. */ - list = (PipList *)malloc(sizeof(PipList)) ; - if (list == NULL) - { fprintf(stderr, "Memory Overflow.\n") ; - exit(1) ; - } - list->vector = sol_vector_edit(i) ; - list->next = NULL ; - - list_now = list ; - if (verbose) - { fprintf(dump,"\n(list ") ; - pip_vector_print(dump,list->vector) ; - } - nb_elements-- ; - - /* Pour les elements suivants. */ - while (nb_elements--) - { list_new = (PipList *)malloc(sizeof(PipList)) ; - if (list_new == NULL) - { fprintf(stderr, "Memory Overflow.\n") ; - exit(1) ; - } - list_new->vector = sol_vector_edit(i) ; - list_new->next = NULL ; - - if (verbose) - { fprintf(dump,"\n") ; - pip_vector_print(dump,list_new->vector) ; - } - list_now->next = list_new ; - list_now = list_now->next ; - } - if (verbose) - fprintf(dump,"\n)") ; - - return(list) ; -} - - -/* Fonction sol_quast_edit : - * Cette fonction a pour but de placer les informations de la solution - * (qui sont contenues dans le tableau sol_space) dans une structure de - * type PipQuast en vue d'une utilisation directe de la solution par une - * application exterieure. Elle prend en parametre un pointeur vers une - * case memoire contenant le numero de cellule du tableau sol_space - * a partir de laquelle on doit commencer la lecture des informations. Elle - * recoit aussi l'adresse du PipQuast qui l'a appelle (pour le champ father). - * Elle retourne un pointeur vers une structure de type PipQuast qui - * contient toutes les informations sur la solution (sous forme d'arbre). - * Remarques : cette fonction lit les informations comme elles doivent - * se presenter a la fin du traitement. Elle respecte scrupuleusement - * la grammaire attendue et n'accepte de passer des cellules a Free - * qu'entre une des trois grandes formes (if, list ou suite de newparm). - * 20 juillet 2001 : Premiere version, Ced. - * 31 juillet 2001 : Ajout du traitement de l'option verbose = code*2 :0( - * 18 octobre 2001 : Grands changements dus a l'eclatement de la structure - * PipVector en PipVector, PipNewparm et PipList, et - * eclatement de la fonction avec sol_newparm_edit et - * sol_list_edit. - * 24 octobre 2002 : Premiere version MP. - */ -PipQuast * sol_quast_edit(int * i, PipQuast * father) -{ int nb_elements ; - struct S * p ; - PipQuast * solution ; - PipList * list_new, * list_now ; - PipNewparm * newparm_new, * newparm_now ; - - /* On place p au lieu de lecture. */ - p = sol_space + (*i) ; - /* En cas d'utilisation de l'option de simplification, une plage de - * structures S peut avoir les flags a Free. On doit alors les passer. - */ - while (p->flags == Free) - { p ++ ; - (*i) ++ ; - } - - solution = (PipQuast *)malloc(sizeof(PipQuast)) ; - if (solution == NULL) - { fprintf(stderr, "Memory Overflow.\n") ; - exit(1) ; - } - solution->newparm = NULL ; - solution->list = NULL ; - solution->condition = NULL ; - solution->next_then = NULL ; - solution->next_else = NULL ; - solution->father = father ; - - /* On peut commencer par une chaine de nouveaux parametres... */ - if (p->flags == New) - { solution->newparm = sol_newparm_edit(i) ; - p = sol_space + (*i) ; - } - - /* ...ensuite soit par une liste (vide ou non) soit par un if. */ - (*i)++ ; /* Factorise de List, Nil et If. */ - switch (p->flags) - { case List : if ((nb_elements = mpz_get_si(p->param1)) != 0) - solution->list = sol_list_edit(i,nb_elements) ; - break ; - case Nil : if (verbose) - fprintf(dump,"\n()") ; - break ; - case If : solution->condition = sol_vector_edit(i) ; - if (verbose) - { fprintf(dump,"\n(if ") ; - pip_vector_print(dump,solution->condition) ; - } - solution->next_then = sol_quast_edit(i,solution) ; - solution->next_else = sol_quast_edit(i,solution) ; - if (verbose) - fprintf(dump,"\n)") ; - break ; - default : fprintf(stderr,"\nAie !!! Flag %d inattendu.\n",p->flags) ; - if (verbose) - fprintf(dump,"\nAie !!! Flag %d inattendu.\n",p->flags) ; - exit(1) ; - } - - return(solution) ; -} - - - - - - - - - - - - - - - - - - - - - - - - - diff --git a/source/tab.c b/source/tab.c index f449790..6b115c4 100644 --- a/source/tab.c +++ b/source/tab.c @@ -40,7 +40,11 @@ extern long int cross_product, limit; static int chunk_count; int dgetc(FILE *); -int dscanf(FILE *, char *, Entier *); +#if defined(LINEAR_VALUE_IS_MP) +int dscanf(FILE *, int *); +#else +int dscanf(FILE *, Entier *); +#endif extern FILE * dump; @@ -67,18 +71,57 @@ struct high_water_mark tab_hwm(void) return p; } -void tab_reset(struct high_water_mark p) + +#if defined(LINEAR_VALUE_IS_MP) +/* the clear_tab routine clears the GMP objects which may be referenced + in the given Tableau. +*/ +void tab_clear(Tableau *tp) +{ + int i, j; + /* clear the determinant */ + mpz_clear(tp->determinant); + + for(i=0; iheight; i++){ + /* clear the denominator */ + mpz_clear(Denom(tp, i)); + if((Flag(tp, i) & Unit) == 0) + for(j=0; jwidth; j++) + mpz_clear(Index(tp,i,j)); + } +} +#endif + +void tab_reset(struct high_water_mark by_the_mark) {struct A *g; - while(chunk_count > p.chunk) + char *p; + while(chunk_count > by_the_mark.chunk) { g = tab_base->precedent; + + #if defined(LINEAR_VALUE_IS_MP) + /* Before actually freeing the memory, one has to clear the + * included Tableaux. If this is not done, the GMP objects + * referenced in the Tableaux will be orphaned. + */ + + /* Enumerate the included tableaux. */ + p = (char *)tab_base + sizeof(struct A); + while(p < tab_free){ + Tableau *pt; + pt = (Tableau *) p; + tab_clear(pt); + p += pt->taille; + } + #endif + free(tab_base); tab_base = g; tab_top = tab_base->bout; chunk_count--; } - if(chunk_count > 0) tab_free = p.top; + if(chunk_count > 0) tab_free = by_the_mark.top; else { fprintf(stderr, "Syserr: tab_reset : error in memory allocation\n"); exit(1); @@ -119,20 +162,38 @@ Tableau * tab_alloc(int h, int w, int n) tab_free += taille; tp = (Tableau *)p; q = (Entier *)(p + sizeof(struct T) + (h+n-1) * sizeof (struct L)); + #if defined(LINEAR_VALUE_IS_MP) + mpz_init_set_ui(tp->determinant,1); + #else tp->determinant[0] = (Entier) 1; tp->l_determinant = 1; + #endif for(i = 0; irow[i].flags = Unit; tp->row[i].objet.unit = i; + #if defined(LINEAR_VALUE_IS_MP) + mpz_init_set_ui(Denom(tp, i), 1); + #else Denom(tp, i) = UN ; + #endif } for(i = n; i < (h+n); i++){ tp->row[i].flags = 0; tp->row[i].objet.val = q; - for(j = 0; j < w; j++) *q++ = 0; + for(j = 0; j < w; j++) + #if defined(LINEAR_VALUE_IS_MP) + mpz_init_set_ui(*q++, 0); /* loop body. */ + mpz_init_set_ui(Denom(tp, i), 0); + #else + *q++ = 0; /* loop body. */ Denom(tp, i) = ZERO ; + #endif } tp->height = h + n; tp->width = w; + #if defined(LINEAR_VALUE_IS_MP) + tp->taille = taille ; + #endif + return(tp); } @@ -142,23 +203,37 @@ int h, w, n; { Tableau *p; int i, j, c; + #if defined(LINEAR_VALUE_IS_MP) + int x ; + #else Entier x; + #endif + p = tab_alloc(h, w, n); while((c = dgetc(foo)) != EOF) if(c == '(')break; for(i = n; irow[i].flags = Unknown; + #if defined(LINEAR_VALUE_IS_MP) + mpz_set_ui(Denom(p, i), 1); + #else Denom(p, i) = UN; + #endif while((c = dgetc(foo)) != EOF)if(c == '[')break; for(j = 0; jrow[i].objet.val[j] = x; + else + #if defined(LINEAR_VALUE_IS_MP) + mpz_set_si(p->row[i].objet.val[j], x); + #else + p->row[i].objet.val[j] = x; + #endif } + } while((c = dgetc(foo)) != EOF)if(c == ']')break; - } - while((c = dgetc(foo)) != EOF)if(c == ')')break; - return((Tableau *) p); + + return(p); } @@ -185,6 +260,9 @@ Tableau * tab_Matrix2Tableau(PipMatrix * matrix, int Nineq, int Nv, int n) unsigned i, j, end, current, new, nb_columns, decal=0 ; Entier * entier, inequality ; + #if defined(LINEAR_VALUE_IS_MP) + mpz_init(inequality) ; + #endif nb_columns = matrix->NbColumns - 1 ; p = tab_alloc(Nineq,nb_columns,n) ; @@ -195,10 +273,18 @@ Tableau * tab_Matrix2Tableau(PipMatrix * matrix, int Nineq, int Nv, int n) for (i=n;ip + i - n) ; /* Pour passer l'indicateur d'egalite/inegalite. */ + #if defined(LINEAR_VALUE_IS_MP) + mpz_set(inequality,*entier) ; + #else inequality = *entier ; + #endif entier ++ ; /* Dans le format de la polylib, l'element constant est place en @@ -207,22 +293,42 @@ Tableau * tab_Matrix2Tableau(PipMatrix * matrix, int Nineq, int Nv, int n) * choses dans l'ordre de Pip. Ici pour p(x) >= 0. */ for (j=0;jrow[current].objet.val + j),*entier++) ; + #else *(p->row[current].objet.val + j) = *entier++ ; + #endif for (j=Nv+1;jrow[current].objet.val + j),*entier++) ; + mpz_set(*(p->row[current].objet.val + Nv),*entier) ; + #else *(p->row[current].objet.val + j) = *entier++ ; *(p->row[current].objet.val + Nv) = *entier ; + #endif /* Et ici lors de l'ajout de -p(x) >= 0 quand on traite une egalite. */ if (!inequality) { decal ++ ; new = current + 1 ; Flag(p,new)= Unknown ; + #if defined(LINEAR_VALUE_IS_MP) + mpz_set(Denom(p,new),UN) ; + #else Denom(p,new) = UN ; + #endif for (j=0;jrow[new].objet.val + j),*(p->row[current].objet.val + j)) ; + #else *(p->row[new].objet.val + j) = -(*(p->row[current].objet.val + j)) ; + #endif } } + #if defined(LINEAR_VALUE_IS_MP) + mpz_clear(inequality); + #endif return(p); } @@ -236,11 +342,19 @@ Tableau *p; int i, j, ff, fff, n; Entier x, d; + #if defined(LINEAR_VALUE_IS_MP) + mpz_init(d); + #endif + fprintf(foo, "%ld/[%d * %d]\n", cross_product, p->height, p->width); for(i = 0; iheight; i++){ fff = ff = p->row[i].flags; /* if(fff ==0) continue; */ + #if defined(LINEAR_VALUE_IS_MP) + mpz_set(d, Denom(p, i)); + #else d = Denom(p, i); + #endif n = 0; while(fff){ if(fff & 1) fprintf(foo, "%s ",Attr[n]); @@ -252,12 +366,24 @@ Tableau *p; fprintf(foo, " /%d/",(j == p->row[i].objet.unit)? 1: 0); else for(j = 0; jwidth; j++){ + #if defined(LINEAR_VALUE_IS_MP) + mpz_out_str(foo, 10, Index(p, i, j)); + putc(' ', foo); + #else x = Index(p,i,j); fprintf(foo, FORMAT, x); fprintf(foo, " "); + #endif } fprintf(foo, "]/"); + #if defined(LINEAR_VALUE_IS_MP) + mpz_out_str(foo, 10, d); + #else fprintf(foo, "%d", (int)d); + #endif putc('\n', foo); } + #if defined(LINEAR_VALUE_IS_MP) + mpz_clear(d); + #endif } diff --git a/source/tabMP.c b/source/tabMP.c deleted file mode 100644 index b5ee0c0..0000000 --- a/source/tabMP.c +++ /dev/null @@ -1,301 +0,0 @@ -/********************************************************/ -/* Part of MultiPrecision PIP port (C) Zbigniew Chamski */ -/* and Paul Feautrier, 2001. */ -/* Based on straight PIP E.1 version by Paul Feautrier */ -/* */ -/* */ -/* and a previous port (C) Zbigniew CHAMSKI, 1993. */ -/* */ -/* */ -/* Copying subject to the terms and conditions of the */ -/* GNU General Public License. */ -/* */ -/* Send questions, bug reports and fixes to: */ -/* */ -/********************************************************/ - - -#include -#include - -#include - -#define TAB_CHUNK 4096*sizeof(Entier) - -static char *tab_free, *tab_top; -static struct A *tab_base; - -extern int allocation; -extern long int cross_product, limit; -static int chunk_count; - -extern FILE * dump; - -/* Structure of the heap after execution of tab_init. - - tab_base tab_free tab_top - | | | - | | | - V | | - struct A { V | -NULL <---- precedent; . <-------------. - bout; - } -*/ - -void tab_init(void) -{ - tab_free = malloc(sizeof (struct A)); - if(tab_free == NULL) - {fprintf(stdout, "Your computer doesn't have memory\n"); - exit(1); - } - allocation = 1; - tab_top = tab_free + sizeof (struct A); - tab_base = (struct A *)tab_free; - tab_free += sizeof(struct A); - tab_base->precedent = NULL; - tab_base->bout = tab_top; - chunk_count = 1; -} - -struct high_water_mark tab_hwm(void) -{struct high_water_mark p; - p.chunk = chunk_count; - p.top = tab_free; - return p; -} - -/* the clear_tab routine clears the GMP objects which may be referenced - in the given Tableau. -*/ - -void tab_clear(Tableau *tp) -{ - int i, j; - /* clear the determinant */ - mpz_clear(tp->determinant); - - for(i=0; iheight; i++){ - /* clear the denominator */ - mpz_clear(Denom(tp, i)); - if((Flag(tp, i) & Unit) == 0) - for(j=0; jwidth; j++) - mpz_clear(Index(tp,i,j)); - } -} - -void tab_reset(struct high_water_mark by_the_mark) - -{struct A *g; - char *p; - while(chunk_count > by_the_mark.chunk) - { - g = tab_base->precedent; -/* Before actually freeing the memory, one has to clear the included Tableaux. - If this is not done, the GMP objects referenced in the Tableaux will be - orphaned. -*/ - -/* Enumerate the included tableaux. - */ - p = (char *)tab_base + sizeof(struct A); - while(p < tab_free){ - Tableau *pt; - pt = (Tableau *) p; - tab_clear(pt); - p += pt->taille; - } - free(tab_base); - tab_base = g; - tab_free = tab_base->bout; - chunk_count--; - } - if(chunk_count > 0) tab_free = by_the_mark.top; - else { - fprintf(stdout, "Syserr: tab_reset : error in memory allocation\n"); - exit(1); - } -} - -Tableau * tab_alloc(int h, int w, int n) - -/* h : le nombre de ligne reelles; - n : le nombre de lignes virtuelles -*/ -{ - char *p; Tableau *tp; - Entier *q; - unsigned long the_taille; - int i, j; - the_taille = sizeof(struct T) + (h+n-1) * sizeof (struct L) - + h * w * sizeof (Entier); - if(tab_free + the_taille >= tab_top) - {struct A * g; - unsigned long d; - d = the_taille + sizeof(struct A); - if(d < TAB_CHUNK) d = TAB_CHUNK; - tab_free = malloc(d); - if(tab_free == NULL) - {printf("Memory overflow\n"); - exit(23); - } - chunk_count++; - g = (struct A *)tab_free; - g->precedent = tab_base; - tab_top = tab_free + d; - tab_free += sizeof(struct A); - tab_base = g; - g->bout = tab_top; - } - p = tab_free; - tab_free += the_taille; - tp = (Tableau *)p; - q = (Entier *)(p + sizeof(struct T) + (h+n-1) * sizeof (struct L)); - mpz_init_set_ui(tp->determinant, 1); - for(i = 0; irow[i].flags = Unit; - tp->row[i].objet.unit = i; - mpz_init_set_ui(Denom(tp, i), 1); - } - for(i = n; i < (h+n); i++){ - tp->row[i].flags = 0; - tp->row[i].objet.val = q; - for(j = 0; j < w; j++) - mpz_init_set_ui(*q++, 0); - mpz_init_set_ui(Denom(tp, i), 0); - } - tp->height = h + n; tp->width = w; tp->taille = the_taille; - return(tp); -} - -Tableau * tab_get(foo, h, w, n) -FILE * foo; -int h, w, n; -{ - Tableau *p; - int i, j, c; - int x; - p = tab_alloc(h, w, n); - while((c = dgetc(foo)) != EOF) - if(c == '(')break; - for(i = n; irow[i].flags = Unknown; - mpz_set_ui(Denom(p, i), 1); - while((c = dgetc(foo)) != EOF)if(c == '[')break; - for(j = 0; jrow[i].objet.val[j], x); - } - } - while((c = dgetc(foo)) != EOF)if(c == ']')break; - - return(p); -} - - -char *Attr[] = {"Unit", "+", "-", "0", "*", "?"}; - -void tab_display(p, foo) -FILE *foo; -Tableau *p; -{ - - int i, j, ff, fff, n; - Entier d; - mpz_init(d); - fprintf(foo, "%ld/[%d * %d]\n", cross_product, p->height, p->width); - for(i = 0; iheight; i++){ - fff = ff = p->row[i].flags; - if(fff == 0) continue; - mpz_set(d, Denom(p, i)); - n = 0; - while(fff){ - if(fff & 1) fprintf(foo, "%s ",Attr[n]); - n++; fff >>= 1; - } - fprintf(foo, "%f #[", p->row[i].size); - if(ff & Unit) - for(j = 0; jwidth; j++) - fprintf(foo, " /%d/",(j == p->row[i].objet.unit)? 1: 0); - else - for(j = 0; jwidth; j++){ - mpz_out_str(foo, 10, Index(p, i, j)); - putc(' ', foo); - } - fprintf(foo, "]/"); - mpz_out_str(foo, 10, d); - putc('\n', foo); - } - mpz_clear(d); -} - - -/* Fonction tab_Matrix2Tableau : - * Cette fonction effectue la conversion du format de matrice de la polylib - * vers le format de traitement de Pip. matrix est la matrice a convertir. - * Nineq est le nombre d'inequations necessaires (dans le format de la - * polylib, le premier element d'une ligne indique si l'equation decrite - * est une inequation ou une egalite. Pip ne gere que les inequations. On - * compte donc le nombre d'inequations total pour reserver la place - * necessaire, et on scinde toute egalite p(x)=0 en p(x)>=0 et -p(x)>=0). - * Nv est le nombre de variables dans la premiere serie de variables (c'est - * a dire que si les premiers coefficients dans les lignes de la matrice - * sont ceux des inconnues, Nv est le nombre d'inconnues, resp. parametres). - * n est le nombre de lignes 'virtuelles' contenues dans la matrice (c'est - * a dire en fait le nombre d'inconnues). - * 27 juillet 2001 : Premiere version, Ced. - * 30 juillet 2001 : Nombreuses modifications. Le calcul du nombre total - * d'inequations (Nineq) se fait a present a l'exterieur. - * 3 octobre 2001 : Pas mal d'ameliorations. - * 24 octobre 2002 : Premiere version MP. - */ -Tableau * tab_Matrix2Tableau(PipMatrix * matrix, int Nineq, int Nv, int n) -{ Tableau * p ; - unsigned i, j, end, current, new, nb_columns, decal=0 ; - Entier * entier, inequality ; - - mpz_init(inequality) ; - nb_columns = matrix->NbColumns - 1 ; - p = tab_alloc(Nineq,nb_columns,n) ; - - /* La variable decal sert a prendre en compte les lignes supplementaires - * issues des egalites. - */ - end = matrix->NbRows + n ; - for (i=n;ip + i - n) ; - /* Pour passer l'indicateur d'egalite/inegalite. */ - mpz_set(inequality,*entier) ; - entier ++ ; - - /* Dans le format de la polylib, l'element constant est place en - * dernier. Dans le format de Pip, il se trouve apres la premiere - * serie de variables (inconnues ou parametres). On remet donc les - * choses dans l'ordre de Pip. Ici pour p(x) >= 0. - */ - for (j=0;jrow[current].objet.val + j),*entier++) ; - for (j=Nv+1;jrow[current].objet.val + j),*entier++) ; - mpz_set(*(p->row[current].objet.val + Nv),*entier) ; - - /* Et ici lors de l'ajout de -p(x) >= 0 quand on traite une egalite. */ - if (!inequality) - { decal ++ ; - new = current + 1 ; - Flag(p,new)= Unknown ; - mpz_set(Denom(p,new),UN) ; - - for (j=0;jrow[new].objet.val + j),*(p->row[current].objet.val + j)) ; - } - } - mpz_clear(inequality); - return(p); -} - diff --git a/source/traiterMP.c b/source/traiter.c similarity index 54% rename from source/traiterMP.c rename to source/traiter.c index 26cad8f..60f71e6 100644 --- a/source/traiterMP.c +++ b/source/traiter.c @@ -1,18 +1,28 @@ -/********************************************************/ -/* Part of MultiPrecision PIP port by Zbigniew Chamski */ -/* and Paul Feautrier. */ -/* Based on straight PIP E.1 version by Paul Feautrier */ -/* */ -/* */ -/* and a previous port (C) Zbigniew CHAMSKI, 1993. */ -/* */ -/* */ -/* Copying subject to the terms and conditions of the */ -/* GNU General Public License. */ -/* */ -/* Send questions, bug reports and fixes to: */ -/* */ -/********************************************************/ +/****************************************************************************** + * PIP : Parametric Integer Programming * + ****************************************************************************** + * traiter.c * + ****************************************************************************** + * * + * Copyright Paul Feautrier, 1988, 1993, 1994, 1996, 2002 * + * * + * This is free software; you can redistribute it and/or modify it under the * + * terms of the GNU General Public License as published by the Free Software * + * Foundation; either version 2 of the License, or (at your option) any later * + * version. * + * * + * This software 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 General Public License * + * for more details. * + * * + * You should have received a copy of the GNU General Public License along * + * with software; if not, write to the Free Software Foundation, Inc., * + * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA * + * * + * Written by Paul Feautrier * + * * + ******************************************************************************/ #include #include @@ -25,10 +35,17 @@ extern long int cross_product, limit; extern int verbose; extern FILE *dump; extern int profondeur; -extern float clock; extern int compa_count; -/* The function llog is replaced by mpz_sizeinbase. */ +#if !defined(LINEAR_VALUE_IS_MP) +int llog(Entier x) +{int n = 0; +/* x must be positive, you dummy */ + if(x<0) x=-x; + while(x) x >>= 1, n++; + return(n); +} +#endif int chercher(Tableau *p, int masque, int n) {int i; @@ -39,8 +56,7 @@ int chercher(Tableau *p, int masque, int n) /* il est convenu que traiter ne doit modifier ni le tableau, ni le contexte; le tableau peut grandir en cas de coupure (+1 en hauteur et +1 en largeur - si nparm != 0) et en cas de partage (+1 en hauteur) - (seulement si nparm != 0). + si nparm != 0) et en cas de partage (+1 en hauteur)(seulement si nparm != 0). le contexte peut grandir en cas de coupure (+2 en hauteur et +1 en largeur) (seulement si nparm !=0) et en cas de partage (+1 en hauteur)(nparm !=0). On estime le nombre de coupures a llog(D) et le nombre de partages a @@ -57,80 +73,115 @@ Tableau *expanser(Tableau *tp, int virt, int reel, int ncol, if(tp == NULL) return(NULL); rp = tab_alloc(reel+dh, ncol+dw, virt); + #if defined(LINEAR_VALUE_IS_MP) mpz_set(rp->determinant, tp->determinant); + #else + rp->l_determinant = tp->l_determinant; + for(i=0; il_determinant; i++) + rp->determinant[i] = tp->determinant[i]; + #endif pq = (Entier *) & (rp->row[virt+reel+dh]); for(i = off; irow[i].objet.unit = tp->row[i-off].objet.unit; else { rp->row[i].objet.val = pq; pq +=(ncol + dw); pp = tp->row[i-off].objet.val; qq = rp->row[i].objet.val; - for(j = 0; jheight; i++) {ff = Flag(tp,i); if(ff == 0) break; - if(ff == Unknown) - {if(bigparm >= 0){ - x = mpz_sgn(Index(tp,i, bigparm)); - if(x<0){ - Flag(tp, i) = Minus; - return(i); - } - else if(x>0) - Flag(tp, i) = Plus; - continue; - } - ff = Zero; - p = &(tp->row[i].objet.val[nvar+1]); - for(j = nvar+1; j0) fff = Plus; - else fff = Zero; - if(fff != Zero && fff != ff) - if(ff == Zero) ff = fff; - else {ff = Unknown; - break; - } - } + if(ff == Unknown) { + #if defined(LINEAR_VALUE_IS_MP) + if(bigparm >= 0){ + x = mpz_sgn(Index(tp,i, bigparm)); + #else + if(bigparm >= 0 && (x = Index(tp,i, bigparm))) { + #endif + if(x<0) { + Flag(tp, i) = Minus; + return(i); + } + else + #if defined(LINEAR_VALUE_IS_MP) + if(x>0) + #endif + Flag(tp, i) = Plus; + continue; + } + ff = Zero; + p = &(tp->row[i].objet.val[nvar+1]); + for(j = nvar+1; j0) fff = Plus; + else fff = Zero; + if(fff != Zero && fff != ff) + if(ff == Zero) ff = fff; + else {ff = Unknown; + break; + } + } /* bug de'tecte' par [paf], 16/2/93 ! Si tous les coefficients des parame`tres sont ne'gatifs et si le terme constant est nul, le signe est inconnu!! On traite donc spe'cialement le terme constant. */ - x = mpz_sgn(Index(tp, i, nvar)); - if(x<0) fff = Minus; - else if(x>0) fff = Plus; - else fff = Zero; + #if defined(LINEAR_VALUE_IS_MP) + x = mpz_sgn(Index(tp, i, nvar)); + #else + x = Index(tp, i, nvar); + #endif + if(x<0) fff = Minus; + else if(x>0) fff = Plus; + else fff = Zero; /* ici on a le signe du terme constant */ - switch(ff){ + switch(ff){ /* le signe est inconnu si les coefficients sont positifs et le terme constant ne'gatif */ - case Plus: if(fff == Minus) ff = Unknown; break; + case Plus: if(fff == Minus) ff = Unknown; break; /* si les coefficients sont tous nuls, le signe est celui du terme constant */ - case Zero: ff = fff; break; + case Zero: ff = fff; break; /* le signe est inconnu si les coefficients sont ne'gatifs, - sauf si le terme constant est ‚galement n‚gatif. */ - case Minus: if(fff != Minus) ff = Unknown; break; + sauf si le terme constant est egalement negatif. */ + case Minus: if(fff != Minus) ff = Unknown; break; /* enfin, il n'y a rien a` dire si le signe des coefficients est inconnu */ + } + Flag(tp, i) = ff; + if(ff == Minus) return(i); } - Flag(tp, i) = ff; - if(ff == Minus) return(i); - } - } + } return(i); } @@ -145,33 +196,59 @@ void compa_test(Tableau *tp, Tableau *context, Tableau *tPlus, *tMinus; int p; struct high_water_mark q; + if(nparm == 0) return; if(nparm >= MAXPARM) { - fprintf(stdout, "Too much parameters : %d\n", nparm); + fprintf(stderr, "Too much parameters : %d\n", nparm); exit(1); } q = tab_hwm(); + #if defined(LINEAR_VALUE_IS_MP) for(i=0; i<=nparm; i++) mpz_init(discr[i]); - + #endif + for(i = 0; i 0) + for(j = 0; j 0) + #else + if(Index(tp, i, j) > 0) + #endif {isCritic = False; break; } compa_count++; - for(j = 0; j0){ fprintf(dump, "\nThe positive case has been found "); @@ -180,19 +257,33 @@ void compa_test(Tableau *tp, Tableau *context, } sol_reset(p); - for(j = 0; j0){ fprintf(dump, "\nThe negative case has been found "); fprintf(dump, cMinus? "possible\n": "impossible\n"); fflush(dump); } + sol_reset(p); if (cPlus && cMinus) { Flag(tp,i) = isCritic ? Critic : Unknown; @@ -208,9 +299,11 @@ void compa_test(Tableau *tp, Tableau *context, } tab_reset(q); + #if defined(LINEAR_VALUE_IS_MP) for(i=0; i<=nparm; i++) mpz_clear(discr[i]); - + #endif + return; } @@ -224,7 +317,6 @@ Entier *valeur(Tableau *tp, int i, int j) void solution(Tableau *tp, int nvar, int nparm) {int i, j; int ncol = nvar + nparm + 1; - Entier *denom; sol_list(nvar); for(i = 0; i= MAXCOL) { fprintf(stdout, "Too much variables\n"); @@ -300,6 +424,7 @@ int pivoter(Tableau *tp, int pivi, int nvar, exit(1); } + #if defined(LINEAR_VALUE_IS_MP) mpz_init(x); mpz_init(y); mpz_init(d); mpz_init(gcd); mpz_init(u); mpz_init(dpiv); mpz_init(lpiv); mpz_init(pivot); mpz_init(foo); @@ -313,67 +438,140 @@ int pivoter(Tableau *tp, int pivi, int nvar, mpz_gcd(d, pivot, dpiv); mpz_divexact(ppivot, pivot, d); mpz_divexact(dppiv, dpiv, d); + #else + pivot = Index(tp, pivi, pivj); + dpiv = Denom(tp, pivi); + d = pgcd(pivot, dpiv); + ppivot = pivot/d; + dppiv = dpiv/d; + #endif + if(verbose>0){ + #if defined(LINEAR_VALUE_IS_MP) fprintf(dump, "Pivot "); mpz_out_str(dump, 10, ppivot); putc('/', dump); mpz_out_str(dump, 10, dppiv); putc('\n', dump); + #else + fprintf(dump, format_format, ppivot, dppiv); + #endif fprintf(dump, "%d x %d\n", pivi, pivj); } + + #if defined(LINEAR_VALUE_IS_MP) mpz_fdiv_qr(x, y, tp->determinant, dppiv); + #else + for(i=0; i< tp->l_determinant; i++){ + d=pgcd(tp->determinant[i], dppiv); + tp->determinant[i] /= d; + dppiv /= d; + } + #endif + #if defined(LINEAR_VALUE_IS_MP) if(mpz_sgn(y) != 0){ fprintf(stdout, "Computation error\n"); + #else + if(dppiv != 1) { + fprintf(stderr, "Integer overflow : %d\n", D); + #endif if(verbose>0) fflush(dump); exit(1); } + + #if defined(LINEAR_VALUE_IS_MP) mpz_mul(tp->determinant, x, ppivot); + #else + for(i=0; il_determinant; i++) + if(llog(tp->determinant[i]) + llog(ppivot) < 8*sizeof(Entier)){ + tp->determinant[i] *= ppivot; + break; + } + if(i >= tp->l_determinant){ + tp->l_determinant++; + if(tp->l_determinant >= MAX_DETERMINANT){ + fprintf(stderr, "Integer overflow : %d\n", tp->l_determinant); + exit(1); + } + tp->determinant[i] = ppivot; + } + #endif if(verbose>0){ fprintf(dump, "determinant "); + #if defined(LINEAR_VALUE_IS_MP) mpz_out_str(dump, 10, tp->determinant); + #else + for(i=0; il_determinant; i++) + fprintf(dump, FORMAT, tp->determinant[i]); + #endif fprintf(dump, "\n"); } for(j = 0; jrow[k].objet.val; q = tp->row[pivi].objet.val; for(j = 0; jrow[k].objet.val; for(j = 0; jrow[k].objet.val; + for(j = 0; jrow[pivi].objet.val; for(k = 0; krow[k].objet.val = p; for(j = 0; jrow[pivi].objet.unit = pivj; for(k = 0; kdeterminant, 2); + #else + dcw = llog(D); + #endif dch = 2 * dcw + 1; x = tab_hwm(); nligne = nvar+ni; @@ -460,11 +692,19 @@ int iq, nvar, nparm, ni, nc, bigparm; for(i=nvar; irow[i].size = s; smax = max(s, smax); } @@ -495,6 +735,11 @@ int iq, nvar, nparm, ni, nc, bigparm; } for(;;) { + if(verbose>0){ + fprintf(dump, "debut for\n"); + tab_display(tp, dump); + fflush(dump); + } nligne = nvar+ni; ncol = nvar+nparm+1; if(nligne > tp->height || ncol > tp->width) { fprintf(stdout, "Syserr : traiter : tableau too small\n"); @@ -531,7 +776,11 @@ int iq, nvar, nparm, ni, nc, bigparm; Entier com_dem; struct high_water_mark q; if(nc >= context->height) { + #if defined(LINEAR_VALUE_IS_MP) dcw = mpz_sizeinbase(context->determinant,2); + #else + dcw = llog(D); + #endif dch = 2 * dcw + 1; context = expanser(context, 0, nc, nparm+1, 0, dch, dcw); } @@ -546,6 +795,7 @@ int iq, nvar, nparm, ni, nc, bigparm; fflush(stdout); sol_if(); sol_forme(nparm+1); + #if defined(LINEAR_VALUE_IS_MP) mpz_init_set_ui(com_dem, 0); for(j = 0; j 0) fflush(dump); + #if defined(LINEAR_VALUE_IS_MP) traiter(ntp, context, iq, nvar, nparm, ni, nc+1, bigparm); profondeur--; tab_reset(q); @@ -576,6 +843,18 @@ int iq, nvar, nparm, ni, nc, bigparm; mpz_neg(Index(context, nc, nparm), Index(context, nc, nparm)); Flag(tp, pivi) = Minus; mpz_set(Denom(context, nc), UN); + #else + traiter(ntp, context, iq, D, nvar, nparm, ni, nc+1, bigparm); + profondeur--; + tab_reset(q); + if(verbose>0) + fprintf(stderr, "descente %d %lx\n", profondeur, tab_hwm().top); + for(j = 0; j 0) goto pirouette; /* A cut has been inserted and is always negative */ /* Here, either there is an integral solution, */ @@ -598,21 +881,22 @@ int iq, nvar, nparm, ni, nc, bigparm; a pivoting step */ pirouette : + #if defined(LINEAR_VALUE_IS_MP) if(pivoter(tp, pivi, nvar, nparm, ni, iq) < 0) { + #else + if((D = pivoter(tp, pivi, D, nvar, nparm, ni, iq)) < 0) { + #endif sol_nil(); break; } } /* Danger : a premature return would induce memory leaks */ tab_reset(x); + #if defined(LINEAR_VALUE_IS_MP) for(i=0; i xyz ;\ + $(ROOT)/obj$(BITS)_$(TARGET)/pip$(BITS)$(EXEC_SUFFIX) -z < $$x > xyz ;\ diff -w xyz `basename $$x .dat`.ll ; \ result=$$?; \ if [ "$$result" -eq "1" ]; then \ -- 2.11.4.GIT