allbery@uunet.UU.NET (Brandon S. Allbery - comp.sources.misc) (05/01/89)
Posting-number: Volume 6, Issue 94
Submitted-by: agn@unh.cs.cmu.edu (Andreas Nowatzyk)
Archive-name: gspn
This code simulates timed generalized stochastic Petri nets
(GSPNs) that can be used to analyze the performance of parallel
systems (both hardware and software). An overview on how to
use GSPN can be found in "Performance Analysis Using Stochastic
Petri Nets", by Michael K. Molloy, IEEE Transactions on Computers,
Vol. C-31, #9, Sept. 1982.
The GSPN Simulator (GS) below accepts a symbolic description of a
GSPN and a set of performance expressions. GS simulates the network
and evaluates the given performance expressions. After execution,
the results are printed with an estimate of the expected simulation
error.
In addition to the symbolic network description (which can be prepared
with any text editor) an interface to the 'GreatSPN' GSPN package
by G. Chiola is provided, which has a nice graphical network editor.
GreatSPN is not PD code and GS does not contain any code from GreatSPN.
M---------------------- Cut here --------------------------
#
# type sh /usru1/agn/gspn/../gs.shar to unpack this archive.
#
echo extracting def2n.l...
cat >def2n.l <<'!E!O!F!'
/************************************************************************\
* *
* GS: A Generalized, stochastic petri net Simulator *
* V0.01 March 1989 Andreas Nowatzyk (agn@unh.cs.cmu.edu) *
* Carnegie-Mellon Univerity, School of Computer Science *
* Schenley Park, Pittsburgh, PA 15213 *
* *
\************************************************************************/
%%
[^%]*"%" ; /* skip header */
"|".*":" {int i; for (i = 1; i < yyleng; i++)
if (yytext[i] == ' ') {yytext[i] = 0; break;}
printf ("RESULT %s :", yytext + 1);}
(p|P)[ /t/n]*"{" printf ("Prob{");
(e|E)[ /t/n]*"{" printf ("Expt{");
"&" printf ("&&");
"=" printf ("==");
"/=" printf ("!=");
"~" printf ("!");
o/[ /n/t(~#] printf ("||"); /* that was real stupid to use an 'o' for OR */
^"|"$ ; /* ignore EOF */
%%
!E!O!F!
#
# type sh /usru1/agn/gspn/../gs.shar to unpack this archive.
#
echo extracting example.n...
cat >example.n <<'!E!O!F!'
/* variable load, 8x8 register file, async, fixed sized packets */
RESULT Throughput : 0.125 Prob{#O1b > 0} + 0.125 Prob{#O2b > 0} +
0.125 Prob{#O3b > 0} + 0.125 Prob{#O4b > 0} +
0.125 Prob{#O5b > 0} + 0.125 Prob{#O6b > 0} +
0.125 Prob{#O7b > 0} + 0.125 Prob{#O8b > 0} ;
RESULT Latency : Dwell{Input} +
0.125 Dwell{O1} + 0.125 Dwell{O2} + 0.125 Dwell{O3} + 0.125 Dwell{O4} +
0.125 Dwell{O5} + 0.125 Dwell{O6} + 0.125 Dwell{O7} + 0.125 Dwell{O8} ;
PARAM buff 8;
PARAM load 1.0;
PLACE Output #marks= 0;
PLACE Input #marks= 0;
PLACE Idle #marks= buff;
PLACE P28 #marks= 0;
PLACE O1 #marks= 0;
PLACE O1b #marks= 0;
PLACE O1i #marks= 0;
PLACE O2 #marks= 0;
PLACE O2b #marks= 0;
PLACE O2i #marks= 0;
PLACE O3 #marks= 0;
PLACE O3b #marks= 0;
PLACE O3i #marks= 0;
PLACE O4 #marks= 0;
PLACE O4b #marks= 0;
PLACE O4i #marks= 0;
PLACE O5 #marks= 0;
PLACE O5b #marks= 0;
PLACE O5i #marks= 0;
PLACE O6 #marks= 0;
PLACE O6b #marks= 0;
PLACE O6i #marks= 0;
PLACE O7 #marks= 0;
PLACE O7b #marks= 0;
PLACE O7i #marks= 0;
PLACE O8 #marks= 0;
PLACE O8b #marks= 0;
PLACE O8i #marks= 0;
PLACE Q1 #marks= 1;
PLACE Q2 #marks= 1;
PLACE Q3 #marks= 1;
PLACE Q4 #marks= 1;
PLACE Q5 #marks= 1;
PLACE Q6 #marks= 1;
PLACE Q7 #marks= 1;
PLACE Q8 #marks= 1;
TRANS source exp rate=load : --> Input;
TRANS enter imm : Input Idle --> P28;
TRANS drain imm : Output --> ;
TRANS x8 det rate= 1.000000e+00, dep= 1 : O8b --> O8i;
TRANS x7 det rate= 1.000000e+00, dep= 1 : O7b --> O7i;
TRANS x6 det rate= 1.000000e+00, dep= 1 : O6b --> O6i;
TRANS x5 det rate= 1.000000e+00, dep= 1 : O5b --> O5i;
TRANS x4 det rate= 1.000000e+00, dep= 1 : O4b --> O4i;
TRANS x3 det rate= 1.000000e+00, dep= 1 : O3b --> O3i;
TRANS x2 det rate= 1.000000e+00, dep= 1 : O2b --> O2i;
TRANS x1 det rate= 1.000000e+00, dep= 1 : O1b --> O1i;
TRANS q1 normal rate= 1.000000e+00, dep= 1 : Q1 --> O1i;
TRANS q2 normal rate= 1.000000e+00, dep= 1 : Q2 --> O2i;
TRANS q3 normal rate= 1.000000e+00, dep= 1 : Q3 --> O3i;
TRANS q4 normal rate= 1.000000e+00, dep= 1 : Q4 --> O4i;
TRANS q5 normal rate= 1.000000e+00, dep= 1 : Q5 --> O5i;
TRANS q6 normal rate= 1.000000e+00, dep= 1 : Q6 --> O6i;
TRANS q7 normal rate= 1.000000e+00, dep= 1 : Q7 --> O7i;
TRANS q8 normal rate= 1.000000e+00, dep= 1 : Q8 --> O8i;
TRANS s1 imm rate= 1.000000e+00, dep= 1 : P28 --> O1;
TRANS s2 imm rate= 1.000000e+00, dep= 1 : P28 --> O2;
TRANS s3 imm rate= 1.000000e+00, dep= 1 : P28 --> O3;
TRANS s4 imm rate= 1.000000e+00, dep= 1 : P28 --> O4;
TRANS s5 imm rate= 1.000000e+00, dep= 1 : P28 --> O5;
TRANS s6 imm rate= 1.000000e+00, dep= 1 : P28 --> O6;
TRANS s7 imm rate= 1.000000e+00, dep= 1 : P28 --> O7;
TRANS s8 imm rate= 1.000000e+00, dep= 1 : P28 --> O8;
TRANS o1 imm rate= 1.000000e+00, dep= 1 : O1i O1 --> O1b Output Idle;
TRANS o2 imm rate= 1.000000e+00, dep= 1 : O2i O2 --> O2b Output Idle;
TRANS o3 imm rate= 1.000000e+00, dep= 1 : O3i O3 --> O3b Output Idle;
TRANS o4 imm rate= 1.000000e+00, dep= 1 : O4i O4 --> O4b Output Idle;
TRANS o5 imm rate= 1.000000e+00, dep= 1 : O5i O5 --> O5b Output Idle;
TRANS o6 imm rate= 1.000000e+00, dep= 1 : O6i O6 --> O6b Output Idle;
TRANS o7 imm rate= 1.000000e+00, dep= 1 : O7i O7 --> O7b Output Idle;
TRANS o8 imm rate= 1.000000e+00, dep= 1 : O8i O8 --> O8b Output Idle;
#end
!E!O!F!
#
# type sh /usru1/agn/gspn/../gs.shar to unpack this archive.
#
echo extracting gs.1...
cat >gs.1 <<'!E!O!F!'
.TH GS 1 4/14/89
.CM 4
.SH NAME
gs \- Generalized Stochastic Petri-Net Simulator
.SH SYNOPSIS
mk_sim [net description file]
.SH DESCRIPTION
GS is a collection of programs and shell-scripts to generate fast
Generalized Stochastic Petri-Net (GSPN) Simulators. GS is closely
related to Giovanni Chiola's GreatSPN package, but can be used
independently.
mk_sim is a shell script that will produce an executable simulator
from a network description. If the sole argument to mk_sim is a file
name ending in ".n", that file is assumed to contain the symbolic
description of a GSPN. Otherwise, mk_sim is assuming that the argument
is a GreatSPN network name and tries to convert the corresponding
*.net and *.def files into an symbolic description file first.
The network description is converted into a C-data structure which is
subsequently compiled with a generic set of simulator routines into
an executable simulator.
Option switches supported by the simulator:
.TP
-a <n>
Alternative transition delay for bimodally timed transition
as a fraction of the nominal delay.
.br
.ns
.TP
-b <n>
Percentage of times a bimodally timed transition will use the
alternative delay: 0=never to 100=always
.br
.ns
.TP
-v,c,o
Verbose, comment and output file options are not really supported yet.
(there is always something left to do)
.br
.ns
.TP
-r <n>
# of generations. The network is reset to its initial state
before each generation. Nets with transient characteristics
will require more generations. The default is 5.
.br
.ns
.TP
-s <n>
Seed for the random number generator.
.br
.ns
.TP
-p <name> <value>
Change a network parameter to the given value. Network parameters
are specific to a particular net and are defined in the *.n file.
.br
.ns
.TP
-f <n>
.br
# of transition firing per generation (default = 10000).
.i0
.DT
.PP
.SH "NET-FILE FORMAT"
The original GreatSPN files (*.net and *.def files) are combined and converted
into a more readable description of the GSPN (*.n files).
This symbolic description
is subsequently processed with cpp (the C-language preprocessor) to allow the
use of macros and conditional compilation or to include libraries of sub-nets.
*.n files are an unordered sequence of statements plus optional comments and/or
cpp-directives.
The file is terminated by a "#end" - line.
4 types of statements are supported, starting with the keywords PLACE, TRANS, PARAM
and RESULT.
Each statement is terminated with a ";".
PLACE statements define places of the network and the number of initial tokens.
TRANS statements define transitions.
GS supports deterministic (det), immediate (imm),
exponentially (exp), normally (normal) and bimodally (bimodal) timed transitions.
The last 2 types are not supported by the GreatSPN package.
PARAM statements define a parameter with a defaults value that can be used instead
of a numeric value for marking and transition rate specification.
Parameters can
be changed at run-time while numeric values are compiled into the code.
RESULT statements define performance expressions that are evaluated and reported.
Expressions are composed out of 4 types of measures: Probabilities (Prob) report
the fraction of time a logical expression in terms of places and token-numbers is
true.
Expected token numbers (Expt) report the number of tokens in a place and can be condition
conditioned by a logic expression.
Firing rates are available with the Fire keyword.
Token dwell times are reported with the Dwell keyword.
The last 2 items are extensions
to GreatSPN.
GS makes sure that expressions don't mix items with incompatible
dimensions (such a probabilities and times).
Details of the file format can be deduced from the yacc-grammar or by inspection
of examples.
.SH FILES
mk_sim: shell script to assemble a simulator
.br
gs_pp: preprocessor to build the simulator data structure
.br
net2n: *.net to *.n file format converter
.br
def2n: *.def to *.n file format converter
.br
GS.o: generic simulator code (precompiled object)
.br
gs.h: include file for final assembly
.br
gs.c: compiles into network specific part
.SH "SEE ALSO"
GreatSPN User's Manual, Version 1.3, September 1987, Giovanni Chiola,
Dipartimento di Informatica, Universia` degli Studi di Torino,
corso Svizzera 185, 10149 Torino, Italy.
.SH EXAMPLE
"mk_sim foo" will create the simulator "foo" from "foo.net" and "foo.def".
"foo.n" is also created, which contains the symbolic description of the
network. Unlike "foo.net" and "foo.def", "foo.n" is almost human readable
and can be changed with a normal text editor. "foo" can be created from
"foo.n" with "mk_sim foo.n".
.SH BUGS
GS does not support nets with multiserver transitions.
The number of
enabling dependencies is assumed to be one.
This isn't hard to fix for
immediate and exponential transitions, but deterministically timed
transition would cause a substantial loss in speed.
Marking dependent transition rates are not supported (easily doable, but
I have yet to figure out a use for it).
The number of firing per generation is left to the user.
GreatSPN has a method
to figure out a lower bound on this number, but it does not always come up
with reasonable limits.
Since GS is much faster, picking a conservative estimate
appears easier.
.SH HISTORY
14-Apr-89 Andreas Nowatzyk (agn) at Carnegie-Mellon University
.br
Created Documentation (finally).
!E!O!F!
#
# type sh /usru1/agn/gspn/../gs.shar to unpack this archive.
#
echo extracting gs.c...
cat >gs.c <<'!E!O!F!'
/************************************************************************\
* *
* GS: A Generalized, stochastic petri net Simulator *
* V0.01 March 1989 Andreas Nowatzyk (agn@unh.cs.cmu.edu) *
* Carnegie-Mellon Univerity, School of Computer Science *
* Schenley Park, Pittsburgh, PA 15213 *
* *
\************************************************************************/
/* GSPN simulator, main part:
*
* This module has only the net-specific componnets:
* - the place-structures
* - the transition structures
* - the fire-functions
* - all statically allocated storrage
*
*/
#include <stdio.h>
#define mainpgm
#include "gs.h"
#include "sim.h"
unsigned long n_places = N_PLACES; /* pass size info to other modules */
unsigned long n_transitions = N_TRANSITIONS;
unsigned long n_results = N_RESULTS;
unsigned long n_parameters = N_PARAMETERS;
struct transition *TBUF[N_TRANSITIONS];
!E!O!F!
#
# type sh /usru1/agn/gspn/../gs.shar to unpack this archive.
#
echo extracting gs.h...
cat >gs.h <<'!E!O!F!'
/************************************************************************\
* *
* GS: A Generalized, stochastic petri net Simulator *
* V0.01 March 1989 Andreas Nowatzyk (agn@unh.cs.cmu.edu) *
* Carnegie-Mellon Univerity, School of Computer Science *
* Schenley Park, Pittsburgh, PA 15213 *
* *
\************************************************************************/
/*
* Parameters and other definitions
*
*/
#define INIT_H_SIZE 4 /* default histogram size */
#define TTY_IMM 0 /* transition types */
#define TTY_EXP 1
#define TTY_DET 2
#define TTY_NRM 3
#define TTY_BIM 4
#define EPSILON 1e-12 /* used in zero-tests for fp-numbers */
#ifdef mainpgm /* main program ? */
#define cdext /* define data struct. */
#define dinit(x) = x /* var initialize */
#else
#define cdext extern /* declare data struct. */
#define dinit(x) /* no var init */
#endif
#define _ ,
/******************** Data structure definitions ********************/
struct transition {
char *name; /* transition name */
unsigned type:2; /* transition type */
unsigned short ena_cnt; /* enable count = #of conditions NOT met to fire :
0: the transition can fire */
unsigned short ini_ena; /* initial enable count */
double delay; /* inverse of rate (saves some div's) */
long prob; /* rescaled probablility (for immediate transition only) */
unsigned long fire_cnt; /* # of times the transition fired */
unsigned long tot_fire_cnt; /* total # of times the transition fired */
struct transition *prev, *next; /* forw/backw pointer for event queue */
double t_fire; /* time scheduled to fire */
double sum, sum_sq; /* for rate computation */
void (*f_func)(); /* pointer to fire function */
};
struct hist { /* histogram element */
double prob; /* accumulated time within one generation */
double sum; /* sum (prob) */
double sum_sq; /* sum (prob^2) */
double sum_cr; /* sum (prob * t(gen)) */
};
struct place {
char *name; /* name of place */
unsigned short ini_mrk, cur_mrk; /* initial & current #of marks */
unsigned short max_mrk; /* max number of marks (for histogram size) */
double t_last; /* time of last change */
struct hist *H; /* histogram structure */
};
struct parameter { /* generic parameter */
char *name; /* name (to be accessed via command line) */
unsigned type:1; /* 0: int (marking), 1: double (rate) */
unsigned short n_used; /* #of incarnations */
unsigned short ind; /* index to pointer array */
double value; /* current value */
};
struct result {
char *name; /* name of result */
unsigned type:2; /* 0: dimensionless (E,P) 1: timed (D) 2: rate (F) */
double t_last; /* time of last change */
double cur; /* current value */
double acc; /* accumulator */
double sum; /* sum (prob) */
double sum_sq; /* sum (prob^2) */
double sum_cr; /* sum (prob * t(gen)) */
void (*upd_fnctn)(); /* update function */
};
/******************** Storage definitions ********************/
cdext double clock dinit(0.0); /* simulation time */
cdext double total_clock dinit(0.0); /* accumulated simulation time */
cdext double total_sq_clock dinit(0.0); /* accumulated simulation time^2 */
cdext struct transition *top dinit(0); /* top of fire queue */
cdext struct transition *i_top dinit(0); /* top of fire queue (immediate transitions) */
cdext long i_prob_acc dinit(0); /* total probability of immediate transitions */
/* bimodal distribution control: */
/*
* Transition delays alternate between the nominal delay (= same as for an deterministic transition)
* and an alternate delay. The ratio is globally controlled as is the alternate delay.
* The ratio may vary between 0 (= det. delay only) and 100 (= alt. delay only).
* The alternate delay is experessed relative to the det. delay: 0.5 takes half the time,
* 2.0 takes twice the nominal delay.
*/
cdext int bim_ratio dinit(50); /* %of times the alternate delay is used */
cdext double bim_alt dinit(0.5); /* alternate delay (the primary is 1.0) */
extern struct parameter PARAMETER[]; /* paramerter */
extern unsigned long n_parameters;
extern double *d_param[];
extern unsigned short *i_param[];
extern struct transition TRANSITION[]; /* transitions */
extern unsigned long n_transitions;
extern struct place PLACE[]; /* places */
extern unsigned long n_places;
extern struct result RESULT[]; /* results */
extern unsigned long n_results;
extern struct transition *TBUF[]; /* temporary list of all enabled transitions */
#define DEQUEUE_X_TR(x) {if (x.prev) x.prev->next = x.next; else top = x.next;\
if (x.next) x.next->prev = x.prev;}
#define DEQUEUE_I_TR(x) {if (x.prev) x.prev->next = x.next; else i_top = x.next;\
if (x.next) x.next->prev = x.prev;\
i_prob_acc -= x.prob;}
#define ENQUEUE_I_TR(x) {x.prev = 0;\
if (x.next = i_top) i_top->prev = &(x);\
i_top = &(x);\
i_prob_acc += x.prob;}
cdext FILE *dstf; /* output and results go here */
cdext FILE *yyin; /* for future use (standart get_opt feature) */
double acc_dwt(); /* accumulate dwell time */
/******************** Option processing (the usual chore) ********************/
cdext long n_fire dinit(10000); /* # of transition fireings */
cdext long n_rgen dinit(5); /* # of regenerations */
cdext long random_seed dinit(123); /* seed for random number generation */
cdext char *comment dinit(0); /* optional comment */
cdext char *out_file dinit(0); /* optional output file */
/* basics */
#define FIRE 0x0001 /* #of fireing per generation */
#define RGEN 0x0002 /* #of regeneration cycles */
/* control */
#define VERB 0x0010 /* verbose option */
#define BM_R 0x0020 /* bimodal ratio (0..100) */
#define BM_A 0x0040 /* bimodal alternate delay */
/* misc */
#define COM 0x0100 /* comment supplied */
#define OUTF 0x0200 /* output file supplied */
#define SEED 0x0400 /* seed for random number gen */
/* app-specific */
#define PARM 0x1000 /* load (user interpret) */
cdext unsigned long OPTV dinit (0); /* option vector */
struct options { /* list of program options */
char c; /* mnemonic character */
unsigned bc; /* bit code */
char ty; /* type: 0=option 1=var 2=string 3=parameter */
char **s; /* string destination */
long *x; /* variable destination */
unsigned cf; /* conflicting option */
double *d; /* floating point option */
} optv[]
#ifdef mainpgm
= {
{'b', BM_R, 1, 0, &bim_ratio, 0, 0},
{'a', BM_A, 6, 0, 0, 0, &bim_alt},
{'v', VERB, 0, 0, 0, 0, 0},
{'f', FIRE, 1, 0, &n_fire, 0, 0},
{'r', RGEN, 1, 0, &n_rgen, 0, 0},
{'s', SEED, 1, 0, &random_seed, 0, 0},
{'c', COM, 2, &comment, 0, 0, 0},
{'o', OUTF, 2, &out_file, 0, 0, 0},
{'p', PARM, 5, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0}}
#endif
;
#undef cdext
#undef dinit
#undef _
!E!O!F!
#
# type sh /usru1/agn/gspn/../gs.shar to unpack this archive.
#
echo extracting gs_main.c...
cat >gs_main.c <<'!E!O!F!'
/************************************************************************\
* *
* GS: A Generalized, stochastic petri net Simulator *
* V0.01 March 1989 Andreas Nowatzyk (agn@unh.cs.cmu.edu) *
* Carnegie-Mellon Univerity, School of Computer Science *
* Schenley Park, Pittsburgh, PA 15213 *
* *
\************************************************************************/
/* GSPN simulator, main part */
#include <stdio.h>
#include "gs.h"
main(argc, argv)
int argc;
char *argv[];
{
register int i, j;
get_opt(argc, argv); /* process comand line */
init(); /* initialize data structures */
if (n_rgen < 2 || n_fire < 1000)
err ("Bogus rgen/fire parameters\n");
for (i = 0; i < n_rgen; i++) {
reset_net();
fire(n_fire);
cleanup();
}
print_result();
exit(0); /* successful exit */
}
err(s)
char *s;
{
fprintf (stderr, "Error: %s\n", s);
exit(1);
}
init () /* initialize data structures */
/*
* 0. initialize random number generation
* 1. allocate histogram space (and zero it)
* 2. compute intergerized transition probabilities for
* immediate transitions. make sure that any additive combination
* of these un-normalized probablilities does not exceed +2^31,
* also insure that no probablility is == 0
*/
{
register int i, j;
register double s;
register struct place *p;
register struct hist *h;
register struct transition *t;
if (bim_ratio < 0 || bim_ratio > 100 || bim_alt < 0.0)
err ("bad -b or -a option");
rnd_init(random_seed);
for(i = n_places, p = PLACE; i--; p++) {
j = p->ini_mrk + 1;
if (j < INIT_H_SIZE) j = INIT_H_SIZE;
p->max_mrk = j;
p->H = h = (struct hist *) malloc (j * sizeof (struct hist));
while (j--) {
h->sum = 0.0;
h->sum_sq = 0.0;
h->sum_cr = 0.0;
h++;
}
}
s = 0.0;
for (i = n_transitions, t = TRANSITION, j = 0; i--; t++)
if (t->type == TTY_IMM) {
j++;
s += 1.0 / t->delay;
}
if (j) { /* worry about this only if there are imm transitions */
if (s < EPSILON)
err ("Unreasonable transition rates for immediate transitions");
s = 268435456.0 / s; /* scale */
for (i = n_transitions, t = TRANSITION; i--; t++)
if (t->type == TTY_IMM) {
t->prob = 0.5 + s / t->delay;
if (t->prob < 1)
t->prob = 1;
}
}
}
reset_net() /* reset net to initial state */
/*
* 1. reset places to original # of tokens
* 2. reset clock & queue
* 3. reset transition enable counts
* 4. initialize fire-queue
* 5. reset result accumulators & state
*/
{
register int i, j;
register struct place *p;
register struct hist *h;
register struct transition *t;
register struct result *r;
for (i = n_places, p = PLACE; i--; p++) {
p->cur_mrk = p->ini_mrk;
p->t_last = 0.0;
for (j = p->max_mrk, h = p->H; j--; h++)
h->prob = 0.0;
}
top = 0;
i_top = 0;
i_prob_acc = 0;
clock = 0.0;
for (i = n_transitions, t = TRANSITION; i--; t++) {
t->fire_cnt = 0;
if (!(t->ena_cnt = t->ini_ena)) {
switch (t->type) {
case TTY_IMM:
enqueue_i_tr(t);
break;
case TTY_EXP:
enqueue_e_tr(t);
break;
case TTY_DET:
enqueue_d_tr(t);
break;
case TTY_BIM:
enqueue_b_tr(t);
break;
case TTY_NRM:
enqueue_n_tr(t);
break;
}
}
}
for (i = n_results, r = RESULT; i--; r++) {
if (r->type)
continue;
r->t_last = 0.0;
r->acc = 0.0;
(*(r->upd_fnctn)) ();
}
}
add_H_space (p) /* increase the histogram size */
register struct place *p;
{
register int i;
register struct hist *h;
i = INIT_H_SIZE + p->max_mrk / 2;
p->H = h = (struct hist *) realloc (p->H, (p->max_mrk + i) * sizeof(struct hist));
h += p->max_mrk;
p->max_mrk += i;
while (i--) {
h->prob = 0.0;
h->sum = 0.0;
h->sum_sq = 0.0;
h->sum_cr = 0.0;
h++;
}
}
enqueue_i_tr (t) /* add an immediate transition to fire queue */
register struct transition *t;
{
t->prev = 0;
if (t->next = i_top)
i_top->prev = t;
i_top = t;
i_prob_acc += t->prob;
}
enqueue_d_tr (t) /* add an deterministic transition to fire queue */
register struct transition *t;
{
register double tf;
register struct transition *q;
t->t_fire = tf = clock + t->delay;
if (q = top) {
while (q->t_fire < tf) {
if (!q->next) { /* end of queue: append at end */
q->next = t;
t->prev = q;
t->next = 0;
return;
}
q = q->next;
}
t->next = q; /* insert before q */
if (!(t->prev = q->prev)) /* ... happen to be top */
top = t;
else
q->prev->next = t;
q->prev = t;
} else { /* virgin queue: insert at top */
top = t;
t->next = 0;
t->prev = 0;
}
}
enqueue_e_tr (t) /* add an deterministic transition to fire queue */
register struct transition *t;
{
register double tf;
double rnd_nedi();
register struct transition *q;
t->t_fire = tf = clock + rnd_nedi(t->delay);
if (q = top) {
while (q->t_fire < tf) {
if (!q->next) { /* end of queue: append at end */
q->next = t;
t->prev = q;
t->next = 0;
return;
}
q = q->next;
}
t->next = q; /* insert before q */
if (!(t->prev = q->prev)) /* ... happen to be top */
top = t;
else
q->prev->next = t;
q->prev = t;
} else { /* virgin queue: insert at top */
top = t;
t->next = 0;
t->prev = 0;
}
}
enqueue_b_tr (t) /* add a bimodal distr. transition to fire queue */
register struct transition *t;
{
register double tf;
register struct transition *q;
if (bim_ratio <= rnd_ri(100))
tf = clock + t->delay;
else
tf = clock + t->delay * bim_alt;
t->t_fire = tf;
if (q = top) {
while (q->t_fire < tf) {
if (!q->next) { /* end of queue: append at end */
q->next = t;
t->prev = q;
t->next = 0;
return;
}
q = q->next;
}
t->next = q; /* insert before q */
if (!(t->prev = q->prev)) /* ... happen to be top */
top = t;
else
q->prev->next = t;
q->prev = t;
} else { /* virgin queue: insert at top */
top = t;
t->next = 0;
t->prev = 0;
}
}
enqueue_n_tr (t) /* add a normal distr. transition to fire queue */
register struct transition *t;
{
register double tf;
double rnd_01d();
register struct transition *q;
t->t_fire = tf = clock + t->delay * rnd_01d();
if (q = top) {
while (q->t_fire < tf) {
if (!q->next) { /* end of queue: append at end */
q->next = t;
t->prev = q;
t->next = 0;
return;
}
q = q->next;
}
t->next = q; /* insert before q */
if (!(t->prev = q->prev)) /* ... happen to be top */
top = t;
else
q->prev->next = t;
q->prev = t;
} else { /* virgin queue: insert at top */
top = t;
t->next = 0;
t->prev = 0;
}
}
fire (n) /* fire n-times */
register unsigned long n;
{
register double tf;
register struct transition **q, *t;
register long i;
while (n--) { /* fire loop */
if (t = i_top) { /* at least one enabled i-transition */
if (!(t->next)) { /* only one! */
(*(t->f_func)) ();
continue; /* fire and done! */
}
/*
* Note: the i-trans selection method is moderately tricky, but correct and fast.
*/
i = rnd_ri(i_prob_acc); /* roll the dice! */
while (0 <= (i -= t->prob))
t = t->next;
(*(t->f_func)) (); /* fire the choosen one */
continue;
}
if (!(t = top))
dead_net(n);
clock = tf = t->t_fire; /* advance clock */
q = TBUF;
*q = t;
i = 1;
for (t = t->next; t && t->t_fire == tf; i++, t = t->next)
*(++q) = t; /* collect all enabled transitions */
if (i > 1) /* fire a random one if more than 1 is enabled */
(*(TBUF[rnd_ri(i)]->f_func))();
else
(*(TBUF[0]->f_func)) ();
}
}
dead_net(n) /* dead-locked, print final marking */
int n;
{
register int i;
register struct place *p;
printf ("No enabled transition: time=%.2f fire-count=%d/%d\n", clock, n_fire - n, n_fire);
for (i = n_places, p = PLACE; i--; p++)
printf("Place '%s': %d token\n", p->name, p->cur_mrk);
err("No enabled transition (deadlock)");
}
cleanup () /* terminate fire */
/*
* 1. accumulate total simulation time
* 2. update place-statistic to current time
* 3. add up fire counts and rates
* 4. update result statistic
*/
{
register int i, j;
register struct place *p;
register struct transition *tr;
register struct hist *h;
register struct result *r;
register double t, c, s;
total_clock += c = clock;
total_sq_clock += c * c;
if (c < EPSILON)
err("Simulation did not consume time");
s = 1.0 / c;
for (i = n_places, p = PLACE; i--; p++) {
h = p->H;
h[p->cur_mrk].prob += clock - p->t_last;
for (j = p->max_mrk; j--; h++) {
t = h->prob;
h->sum += t;
h->sum_sq += t * t;
h->sum_cr += t * c;
}
}
for(i = n_transitions, tr = TRANSITION; i--; tr++) {
tr->tot_fire_cnt += j = tr->fire_cnt;
t = j * s;
tr->sum += t;
tr->sum_sq += t * t;
}
for (i = n_results, r = RESULT; i--; r++) {
if (r->type) {
(*(r->upd_fnctn))();
} else {
t = r->acc + r->cur * (clock - r->t_last);
r->sum += t;
r->sum_sq += t * t;
r->sum_cr += t * c;
}
}
}
print_result () /* you guessed it */
{
register int i, j;
register struct place *p;
register struct transition *t;
register struct hist *h;
register struct result *rp;
register double x, c, q, r, s;
double sqrt(), stud_t995();
if (total_clock < EPSILON)
err ("No timed transitions fired");
q = stud_t995(n_rgen - 1);
r = n_rgen / (total_clock * total_clock * (n_rgen - 1));
s = 1.0 / total_clock;
for (i = n_places, p = PLACE; i--; p++) {
printf ("Place '%s':\n", p->name);
for(j = 0, h = p->H; j < p->max_mrk; h++, j++) {
if (h->sum < EPSILON)
continue;
/* the next is practically verbatim from Chiola's original */
x = h->sum * s;
c = h->sum_sq + x * (x * total_sq_clock - 2 * h->sum_cr);
c = q * sqrt(c * r);
printf ("\tP(%d) = %8.6f (+/- %8.6f)\n", j, x, c);
}
}
for (i = n_results, rp = RESULT; i--; rp++) {
if (rp->type) { /* dwell-time */
x = rp->sum / n_rgen;
c = rp->sum_sq - x * rp->sum;
c = q * sqrt(c / (n_rgen * (n_rgen - 1)));
printf ("%s = %8.6f (+/- %8.6f) [%s]\n", rp->name, x, c, (rp->type == 1) ? "time units" : "fireing / time unit");
} else { /* probabilities and expectations */
x = rp->sum * s;
c = rp->sum_sq + x * (x * total_sq_clock - 2 * rp->sum_cr);
c = q * sqrt(c * r);
printf ("%s = %8.6f (+/- %8.6f)\n", rp->name, x, c);
}
}
for(i = n_transitions, t = TRANSITION; i--; t++) {
x = t->sum / n_rgen;
c = t->sum_sq - x * t->sum;
c = q * sqrt(c / (n_rgen * (n_rgen - 1)));
printf("Transition %s : %8.6f (+/- %8.6f) [fireing / time-unit]\n", t->name, x, c);
}
}
/* #define INP_FILE 1 */ /* expect an input file */
get_opt (argc, argv) /* process arguments */
int argc;
char *argv[];
{
register int i, j, k, aty;
double d, *dbl;
int l;
struct parameter *pp;
long *var;
char opt, **str, fname[82];
char *infn = 0; /* input file name */
char *outfn = 0; /* output file name */
aty = 0; /* expect no sub argument */
for (i = 1; i < argc; i++) { /* scan arguments */
if (argv[i][0] == '-' && !aty) { /* got an option */
for (j = 1; argv[i][j]; j++) { /* scan option string */
opt = argv[i][j];
for (k = 0; optv[k].c; k++)
if (opt == optv[k].c) { /* found option */
if (OPTV & optv[k].cf) {
fprintf(stderr, "Option '%c' conflicts with earlier option\n", opt);
goto error;
}
OPTV |= optv[k].bc;
if (optv[k].ty) {
if (aty) {
fprintf(stderr, "Ambigious option/argument combination\n");
goto error;
}
aty = optv[k].ty;
str = optv[k].s;
var = optv[k].x;
dbl = optv[k].d;
}
break;
}
if (!optv[k].c) {
fprintf(stderr, "Unknown option\n");
goto error;
}
}
} else { /* got an argument */
switch (aty) {
case 6: /*** double ***/
if (1 != sscanf(argv[i], "%lf", dbl))
goto error;
aty = 0;
break;
case 5: /*** parameter ***/
for (j = n_parameters, pp = PARAMETER; j--; pp++)
if (!strcmp(argv[i], pp->name)) {
if(pp->type)
aty = 4; /* positive double param */
else
aty = 3; /* positive int param */
break;
}
if (j < 0) {
fprintf(stderr, "Undefined parameter\n");
goto error;
}
break;
case 4: /*** convert a double > 0 ***/
if (1 != sscanf(argv[i], "%lf", &d) || d < 0.0) {
fprintf(stderr, "Invalid value for '%s'\n", pp->name);
goto error;
}
if (d < EPSILON) d = 1e20; /* approximate infinite delay */
else d = 1.0 / d;
pp->value = d;
for (j = pp->ind, k = pp->n_used; k--; j++)
*d_param[j] = d;
aty = 0;
break;
case 3: /*** integer > 0 parameter ***/
if (1 != sscanf(argv[i], "%d", &l) || l < 0) {
fprintf(stderr, "Invalid value for '%s'\n", pp->name);
goto error;
}
j = pp->ind;
if ((!*i_param[j]) != (!l)) {
fprintf(stderr, "Can't switch between 0 and non-0 #of tokens\n");
goto error;
}
pp->value = l;
for (k = pp->n_used; k--; j++)
*i_param[j] = l;
aty = 0;
break;
case 2: /*** string sub-argument ***/
*str = argv[i];
aty = 0;
break;
case 1: /*** integer sub-argument ***/
if (1 != sscanf(argv[i], "%ld", var))
goto error;
aty = 0;
break;
default: /*** unspecified arg (filename) ***/
#ifdef INP_FILE
infn = argv[i];
i++;
#endif
if (i < argc) { /* output file name present ? */
if ('-' == argv[i][0] || (i + 1) < argc)
goto error;
outfn = argv[i];
}
}
}
}
if (infn) {
yyin = fopen(infn, "r");
if (!yyin) {
fprintf(stderr, "Could not open '%s' for read\n", infn);
exit(1);
}
} else
yyin = stdin;
if (outfn) {
dstf = fopen(outfn, "w");
if (!dstf) {
fprintf(stderr, "Could not open '%s' for write\n", outfn);
exit(1);
}
} else
dstf = stdout;
return; /* options are ok */
error: /* some trouble with the arguments */
fprintf(stderr, "gs [-");
for (i = 0; optv[i].c; i++)
fprintf(stderr, "%c", optv[i].c);
fprintf(stderr, "] [input-file] [output-file]\n");
exit(1);
}
double stud_t995 (n) /* approximation to Student's T-percentiles */
int n;
{
static double tab[30] = {
63.657, 9.925, 5.841, 4.604, 4.032, 3.707, 3.499, 3.355, 3.250, 3.169,
3.106, 3.055, 3.012, 2.977, 2.947, 2.921, 2.898, 2.878, 2.861, 2.845,
2.831, 2.819, 2.807, 2.797, 2.787, 2.779, 2.771, 2.763, 2.756, 2.750
};
if (n < 1)
err ("Student's T percentiles not defined for n < 1");
if (n <= 30)
return tab[n - 1];
if (n > 200)
return 2.576;
n -= 30;
if (n < 10)
return 2.750 - n * 0.0046;
n -= 10;
if (n < 20)
return 2.704 - n * 0.0022;
n -= 20;
if (n < 60)
return 2.660 - n * 0.0007;
n -= 60;
return 2.617 - n * 0.0005;
}
double acc_dwt(p) /* accumulate dwell time */
register struct place *p;
{
register double t = 0.0;
register struct hist *h = p->H + 1;
register int i;
for(i = 1; i < p->max_mrk; i++, h++)
t += i * h->prob;
return t;
}
!E!O!F!
#
# type sh /usru1/agn/gspn/../gs.shar to unpack this archive.
#
echo extracting gs_pp.c...
cat >gs_pp.c <<'!E!O!F!'
/* main part of gs-preprocessor */
static struct parameter *PR = 0; /* parameter structure */
static int n_PR = 0, max_PR = 0;
static struct place *PL = 0, *cur_PL; /* place structure */
static int n_PL = 0, max_PL = 0;
static struct transition *TR = 0, *cur_TR; /* transition structure */
static int n_TR = 0, max_TR = 0;
static struct result *RS = 0; /* result struture */
static int n_RS = 0, max_RS = 0;
static int error_cnt = 0; /* error counter */
static int result_type; /* result type */
#define EPS 1e-12 /* for FP-zero tests */
main ()
{
yyparse(); /* parse the input */
check(); /* sanity check */
if (error_cnt)
exit(1); /* exit in case of errors */
build_place(); /* emitt simulator structures */
build_trans();
build_param();
build_tfunc();
build_rslts();
build_ffunc();
exit(0); /* done! */
}
yyerror (s) /* error printer */
char *s;
{
error_cnt++;
fprintf (stderr, "%s, line %d: %s\n", src_file, yylineno, s);
}
struct parameter *find_param (s) /* find a parameter */
register char *s;
{
register int i;
register struct parameter *p;
for (i = n_PR, p = PR; i--; p++)
if (!strcmp(s, p->name)) {
free(s);
return p;
}
if (n_PR <= max_PR) { /* need more space */
max_PR += 20 + max_PR / 2;
if (PR)
PR = p = (struct parameter *) realloc (PR, max_PR * sizeof(struct parameter));
else
PR = p = (struct parameter *) malloc (max_PR * sizeof(struct parameter));
}
p += n_PR++;
p->name = s;
p->defined = 0;
p->used = 0;
p->max_used = 0;
p->ind = 0;
return p;
}
add_param (s, v) /* got a new parameter */
register char *s;
double v;
{
register struct parameter *p = find_param(s);
if(p->defined)
yyerror("Parameter allready defined");
p->defined = 1;
p->value = v;
}
struct place *find_place(s) /* locate a place */
register char *s;
{
register int i;
register struct place *p;
for (i = n_PL, p = PL; i--; p++) /* see if place is allready defined */
if (!strcmp(s, p->name)) {
free(s);
return p;
}
if (n_PL >= max_PL) { /* need more space */
max_PL += 50 + max_PL / 2;
if (PL)
PL = (struct place *) realloc(PL, sizeof(struct place) * max_PL);
else
PL = (struct place *) malloc(sizeof(struct place) * max_PL);
}
p = &PL[n_PL++];
p->name = s;
p->defined = 0;
p->input_ptr = 0;
p->inhib_ptr = 0;
p->result_ptr = 0;
p->n_input = 0;
p->n_output = 0;
return p;
}
add_place (s) /* got a new place */
register char *s;
{
register int i;
register struct place *p = find_place(s);
if (p->defined) {
yyerror("Place allready defined");
return;
}
cur_PL = p;
p->defined = 1;
p->mdef = 0;
p->marks = 0;
}
chg_marks (d) /* change number of marks in a place */
double d;
{
register int i = d + 0.5; /* round to an integer */
if (i < 0 || cur_PL->mdef)
yyerror ("illegal or multiple marking-specification");
else {
cur_PL->mdef = 1;
cur_PL->marks = i;
}
}
chg_p_marks (s) /* change number of marks in a place */
char *s;
{
register struct parameter *p = find_param(s); /* locate parameter */
if (cur_PL->mdef || (p->used && p->type))
yyerror ("Marking specification problem");
else {
if (p->used >= p->max_used) {
p->type = 0;
p->max_used += 10 + p->max_used / 2;
if (p->ind)
p->ind = (int *) realloc (p->ind, p->max_used * sizeof(int));
else
p->ind = (int *) malloc (p->max_used * sizeof(int));
}
cur_PL->mdef = 1;
p->ind[p->used++] = cur_PL - PL;
}
}
struct transition *find_transition(s)
register char *s;
{
register int i;
register struct transition *t;
for (i = n_TR, t = TR; i--; t++) /* see if transition is allready defined */
if (!strcmp(s, t->name)) {
free(s);
return t;
}
if (n_TR >= max_TR) { /* need more space */
max_TR += 50 + max_TR / 2;
if (TR)
TR = (struct transition *) realloc(TR, sizeof(struct transition) * max_TR);
else
TR = (struct transition *) malloc(sizeof(struct transition) * max_TR);
}
t = &TR[n_TR++];
t->name = s; /* set up default transition structure */
t->def = 0;
t->ddef = 0;
t->delay = 1.0;
t->depdef = 0;
t->depend = 1;
t->n_input = 0;
t->n_output = 0;
t->n_inhib = 0;
t->input_ptr = 0;
t->output_ptr = 0;
t->inhib_ptr = 0;
return t;
}
add_transition (s) /* got a new transition */
char *s;
{
register struct transition *t = find_transition(s);
if (t->def)
yyerror("Transition multiply defined");
t->def = 1;
cur_TR = t;
}
set_type (t) /* define the transition type */
int t;
{
cur_TR->type = t;
}
chg_depend (d) /* change the transition delay */
double d;
{
if (cur_TR->depdef || d < 0.0)
yyerror("dependency definition problem");
else {
cur_TR->depdef = 1;
cur_TR->depend = d;
if (cur_TR->depend != 1)
yyerror("Sorry, only depency = 1 supported");
}
}
chg_rate (d) /* change the transition rate */
double d;
{
if (cur_TR->ddef || d <= EPS)
yyerror("rate definition problem");
else {
cur_TR->ddef = 1;
cur_TR->delay = 1.0 / d;
}
}
chg_p_rate (s) /* change the transition rate parameter */
char *s;
{
register struct parameter *p = find_param(s); /* locate parameter */
if (cur_TR->ddef || (p->used && !p->type))
yyerror("rate definition problem");
else {
if (p->used >= p->max_used) {
p->type = 1;
p->max_used += 10 + p->max_used / 2;
if (p->ind)
p->ind = (int *) realloc (p->ind, p->max_used * sizeof(int));
else
p->ind = (int *) malloc (p->max_used * sizeof(int));
}
p->ind[p->used++] = cur_TR - TR;
cur_TR->ddef = 1;
}
}
add_input (s) /* add input to a transition */
char *s;
{
register struct list_item *t;
register struct place *p = find_place(s);
t = (struct list_item *) malloc(sizeof(struct list_item));
t->ind = p - PL;
t->next = cur_TR->input_ptr;
cur_TR->input_ptr = t;
cur_TR->n_input++;
t = (struct list_item *) malloc(sizeof(struct list_item));
t->ind = cur_TR - TR;
t->next = p->input_ptr;
p->input_ptr = t;
p->n_input++;
}
add_output (s) /* add output to a transition */
char *s;
{
register struct list_item *t;
register struct place *p = find_place(s);
t = (struct list_item *) malloc(sizeof(struct list_item));
p->n_output++;
t->ind = p - PL;
t->next = cur_TR->output_ptr;
cur_TR->output_ptr = t;
cur_TR->n_output++;
}
add_inhib (s) /* add inhib to a transition */
char *s;
{
register struct list_item *t;
register struct place *p = find_place(s);
t = (struct list_item *) malloc(sizeof(struct list_item));
t->ind = p - PL;
t->next = cur_TR->inhib_ptr;
cur_TR->inhib_ptr = t;
cur_TR->n_inhib++;
t = (struct list_item *) malloc(sizeof(struct list_item));
t->ind = cur_TR - TR;
t->next = p->inhib_ptr;
p->inhib_ptr = t;
}
check() /* sanity check */
/*
* Make sure that:
*
* 0. See that parameters are defined & used
* 1. All places are defined
* 2. All places have at least one in/out arc
* 3. All transitions have at least one input and one output
* (I can't think of any sensible transition lacking either)
* 4. Transition type matches given parameters
* (can't specify a reate for an immediate transition)
*/
{
register int i, j, k, *ip;
register double d;
register struct place *p;
register struct transition *t;
register struct parameter *pr;
char buf[80];
if (n_PL < 1 || n_TR < 1)
yyerror ("Need at least 1 place/transition");
for(i = n_PR, pr = PR; i--; pr++) { /* check parameters and insert values */
if (!pr->defined) {
sprintf(buf, "Undefined parameter '%s'", pr->name);
yyerror(buf);
}
if (pr->type) { /* rate-parameter */
d = pr->value;
if (d <= EPS)
yyerror ("Negative rate parameter");
else {
d = 1.0 / d;
for (j = pr->used, ip = pr->ind; j--; ip++)
TR[*ip].delay = d;
}
} else { /* marking parameter */
d = pr->value;
if (d <= -EPS)
yyerror ("Negative marking parameter");
else {
k = d + 0.5;
for (j = pr->used, ip = pr->ind; j--; ip++)
PL[*ip].marks = k;
}
}
}
for (i = n_PL, p = PL; i--; p++) {
if (!p->defined) {
sprintf(buf, "Undefined place '%s'", p->name);
yyerror(buf);
}
if (p->n_input < 1 || p->n_output < 1) {
sprintf(buf, "Warning: place '%s' has no input/output arc", p->name);
yyerror(buf);
error_cnt--;
}
}
for (i = n_TR, t = TR; i--; t++) {
if (t->n_input < 1 || t->n_output < 1) {
sprintf(buf, "Warning: transition '%s' has no input/output", t->name);
yyerror(buf);
error_cnt--;
}
}
}
build_place () /* produce place structures for simulator */
/*
* Note: the corresponding structure definition is supplied in "gs.h"
*
*/
{
register int i, j;
printf("#define N_PLACES %d\n\n", n_PL);
printf("struct place PLACE[N_PLACES] = {\n");
for (i = 0; i < n_PL; i++) {
if (i)
printf(",\n");
printf(" {\"%s\", %d, %d, 0, 0.0, 0}", PL[i].name, PL[i].marks, PL[i].marks);
}
printf("\n};\n\n");
}
build_tfunc () /* produce fire-to macros structures for simulator */
/*
* Note: the corresponding structure definition is supplied in "gs.h"
*
*/
{
register int i, j;
register struct list_item *t;
for (i = 0; i < n_PL; i++) {
printf("#define FIRE_TO%d ", i);
if (PL[i].n_input < 1)
printf("0.0\n");
else {
printf("(");
for(t = PL[i].input_ptr, j = 0; t; t = t->next)
printf("TRANSITION[%d].fire_cnt%s", t->ind, (t->next) ?
((!(++j % 3)) ? " +\\\n " : " + ") : ")\n");
}
}
printf("\n");
}
build_trans() /* build transition structure */
{
register int i, j;
register struct list_item *t;
printf("#define N_TRANSITIONS %d\n\n", n_TR);
for (i = 0; i < n_TR; i++)
printf ("void fire_T%d();\n", i);
printf("\nstruct transition TRANSITION[N_TRANSITIONS] = {\n");
for (i = 0; i < n_TR; i++) {
if (i)
printf(",\n");
j = 0; /* count # of conditions that prevent fire */
for (t = TR[i].input_ptr; t; t = t->next)
j += PL[t->ind].marks <= 0;
for (t = TR[i].inhib_ptr; t; t = t->next)
j += PL[t->ind].marks > 0;
printf(" {\"%s\", %d, %d, %d, %.12e, 0, 0, 0, 0, 0, 0.0, 0.0, 0.0, fire_T%d}",
TR[i].name, TR[i].type, j, j, TR[i].delay, i);
}
printf("\n};\n\n");
}
build_ffunc () /* build fire functions */
{
register int i, j;
register struct list_item *t, *q;
register struct result *r;
static char *eq_type[5] = {"ENQUEUE_I_TR(", "enqueue_e_tr(&", "enqueue_d_tr(&", "enqueue_n_tr(&", "enqueue_b_tr(&"};
for (i = 0; i < n_PL; i++) {
printf ("#define REMOVE_M_PL%d\tPLACE[%d].H[PLACE[%d].cur_mrk].prob += clock - PLACE[%d].t_last;\\\n", i, i, i, i);
printf ("\t\t\tPLACE[%d].t_last = clock;\\\n", i);
printf ("\t\t\tif (!(--PLACE[%d].cur_mrk)) {\\\n", i);
for (t = PL[i].input_ptr; t; t = t->next)
printf("\t\t\t if (!(TRANSITION[%d].ena_cnt++)) DEQUEUE_%c_TR(TRANSITION[%d]);\\\n", t->ind,
(TR[t->ind].type == TTY_IMM) ? 'I' : 'X', t->ind);
for (t = PL[i].inhib_ptr; t; t = t->next)
printf("\t\t\t if (!(--TRANSITION[%d].ena_cnt)) %sTRANSITION[%d]);\\\n", t->ind, eq_type[TR[t->ind].type], t->ind);
printf ("\t\t\t}\n");
printf ("#define ADD_M_PL%d\tPLACE[%d].H[PLACE[%d].cur_mrk].prob += clock - PLACE[%d].t_last;\\\n", i, i, i, i);
printf ("\t\t\tPLACE[%d].t_last = clock;\\\n", i);
printf ("\t\t\tif (!(PLACE[%d].cur_mrk++)) {\\\n", i);
for (t = PL[i].inhib_ptr; t; t = t->next)
printf("\t\t\t if (!(TRANSITION[%d].ena_cnt++)) DEQUEUE_%c_TR(TRANSITION[%d]);\\\n", t->ind,
(TR[t->ind].type == TTY_IMM) ? 'I' : 'X', t->ind);
for (t = PL[i].input_ptr; t; t = t->next)
printf("\t\t\t if (!(--TRANSITION[%d].ena_cnt)) %sTRANSITION[%d]);\\\n", t->ind, eq_type[TR[t->ind].type], t->ind);
printf ("\t\t\t}\\\n");
printf ("\t\t\tif (PLACE[%d].cur_mrk >= PLACE[%d].max_mrk) add_H_space (&PLACE[%d])\n\n", i, i, i);
}
for (i = 0; i < n_TR; i++) {
for (j = n_RS, r = RS; j--; r++)
r->flg = 0; /* default: assume result is not affected */
printf("void fire_T%d()\n{\n", i);
printf(" TRANSITION[%d].fire_cnt++;\n", i);
for (t = TR[i].input_ptr; t; t = t->next){
printf(" REMOVE_M_PL%d;\n", t->ind);
for (q = PL[t->ind].result_ptr; q; q = q->next)
RS[q->ind].flg = 1; /* mark results that depend on this place */
}
for (t = TR[i].output_ptr; t; t = t->next) {
printf(" ADD_M_PL%d;\n", t->ind);
for (q = PL[t->ind].result_ptr; q; q = q->next)
RS[q->ind].flg = 1; /* mark results that depend on this place */
}
for (j = 0; j < n_RS; j++)
if (RS[j].flg)
printf(" rs_func%d();\n", j);
if (TR[i].type != TTY_IMM) {
printf(" if(!TRANSITION[%d].ena_cnt) {\n", i);
printf("\tDEQUEUE_X_TR(TRANSITION[%d]);\n", i);
printf("\t%sTRANSITION[%d]);\n", eq_type[TR[i].type], i);
printf(" }\n");
}
printf("}\n\n");
}
for (i = 0; i < n_PL; i++)
printf("#undef REMOVE_M_PL%d\n#undef ADD_M_PL%d\n", i, i);
}
build_param() /* dump the parameter structure */
{
register int i, j, k, *ip, i_cnt, d_cnt;
register struct parameter *p;
printf("#define N_PARAMETERS %d\n\n", n_PR);
if (!n_PR) { /* no parameters, dump dummy to keep compiler happy */
printf("struct parameter PARAMETER[1];\n");
printf("double *d_param[1];\n");
printf("unsigned short *i_param[1];\n");
return;
}
printf("struct parameter PARAMETER[N_PARAMETERS] = {");
i_cnt = 0;
d_cnt = 0;
for (i = n_PR, p =PR; i--; p++) {
if (p->type) {
printf("\n {\"%s\", 1, %d, %d, %.10e}", p->name, p->used, d_cnt, p->value);
d_cnt += p->used;
} else {
printf("\n {\"%s\", 0, %d, %d, %.10e}", p->name, p->used, i_cnt, p->value);
i_cnt += p->used;
}
if(i)
printf (",");
}
printf("\n};\n");
if(d_cnt) {
printf("double *d_param[%d] = {\n ", d_cnt);
for (i = n_PR, p =PR, k = 0; i--; p++)
if (p->type) {
for (j = p->used, ip = p->ind; j--; ip++)
printf ("&(TRANSITION[%d].delay)%s", *ip,
(--d_cnt) ? ((++k & 3) ? ", " : ",\n ") : "};\n");
}
} else
printf("double *d_param[1];\n");
if(i_cnt) {
printf("unsigned short *i_param[%d] = {\n ", i_cnt);
for (i = n_PR, p =PR, k = 0; i--; p++)
if (!p->type) {
for (j = p->used, ip = p->ind; j--; ip++)
printf ("&(PLACE[%d].ini_mrk)%s", *ip,
(--i_cnt) ? ((++k & 3) ? ", " : ",\n ") : "};\n");
}
} else
printf("unsigned short *i_param[1];\n\n");
}
add_result (s, b) /* got a new result def */
register char *s, *b;
{
register int i;
register struct result *r;
for (i = n_RS, r = RS; i--; r++) /* see if result is allready defined */
if (!strcmp(s, r->name)) {
free(s);
free(b);
yyerror("Result multiply defined");
return;
}
if (n_RS >= max_RS) { /* need more space */
max_RS += 50 + max_RS / 2;
if (RS)
RS = (struct result *) realloc(RS, sizeof(struct result) * max_RS);
else
RS = (struct result *) malloc(sizeof(struct result) * max_RS);
}
r = &RS[n_RS++];
r->name = s; /* set up default transition structure */
r->body = b;
r->type = result_type;
}
char *concat (s1, s2)
char *s1, *s2;
{
register char *s;
s = (char *) malloc (6 + strlen(s1) + strlen(s2));
strcpy(s, s1);
strcat(s, s2);
free(s1);
free(s2);
return s;
}
ini_result() /* prepare for a result definition */
{
result_type = 0;
}
char *do_prob(d, s)
char *s, *d;
{
char *s1;
if (result_type && result_type != 1)
yyerror("Dimension mismatch");
result_type = 1;
s1 = (char *) malloc(strlen(s) + 50);
sprintf(s1, " if (%s) t %c= %s;\n", s, it_opr, d);
free(s);
free(d);
return s1;
}
char *do_exp(d, s)
char *s, *d;
{
char *s1;
if (result_type && result_type != 1)
yyerror("Dimension mismatch");
result_type = 1;
s1 = (char *) malloc(strlen(s) + 50);
sprintf(s1, " t %c= %s * %s;\n", it_opr, d, s);
free(s);
free(d);
return s1;
}
char *do_cexp(d, s, c)
char *s, *c, *d;
{
char *s1;
if (result_type && result_type != 1)
yyerror("Dimension mismatch");
result_type = 1;
s1 = (char *) malloc(strlen(s) + 50 + strlen(c));
sprintf(s1, " if (%s) t %c= %s * %s;\n", c, it_opr, d, s);
free(s);
free(c);
free(d);
return s1;
}
char *do_dwell(c, s)
char *c, *s;
{
char *s1;
int i;
if (result_type && result_type != 2)
yyerror("Dimension mismatch");
result_type = 2;
s1 = (char *) malloc (100);
i = find_place(s) - PL;
/* Note: that 10^-60 prevents div by 0 and nothing else */
sprintf(s1, " t %c= %s * acc_dwt(&PLACE[%d]) / (1e-60 + FIRE_TO%d);\n", it_opr, c, i, i);
free(c);
return s1;
}
char *do_fire(c, s)
char *c, *s;
{
char *s1;
int i;
if (result_type && result_type != 3)
yyerror("Dimension mismatch");
result_type = 3;
s1 = (char *) malloc (100);
i = find_transition(s) - TR;
sprintf(s1, " t %c= %s * TRANSITION[%d].fire_cnt;\n", it_opr, c, i);
free(c);
return s1;
}
char *get_val (d)
double d;
{
char *s;
double rint();
s = (char *) malloc(50);
if (d == rint(d))
sprintf(s, "%.1f", d);
else
sprintf(s, "%.10e", d);
return s;
}
char *get_para(s)
char *s;
{
char *s1;
s1 = (char *) malloc(50);
sprintf(s1, "PARAMETER[%d].value", find_param(s) - PR);
return s1;
}
char *get_place (s)
char *s;
{
register struct place *p = find_place(s);
register struct list_item *t = (struct list_item *) malloc (sizeof (struct list_item));
char *s1 = (char *) malloc (30);
sprintf (s1, "PLACE[%d].cur_mrk", (int) (p - PL));
t->ind = n_RS;
t->next = p->result_ptr;
p->result_ptr = t;
return s1;
}
char *c_negate (s)
char *s;
{
char *s1 = (char *) malloc (strlen(s) + 5);
sprintf (s1, "!(%s)", s);
free (s);
return s1;
}
char *do_paren (s)
char *s;
{
char *s1 = (char *) malloc (strlen(s) + 5);
sprintf (s1, "(%s)", s);
free (s);
return s1;
}
char *do_and (s1, s2)
char *s1, *s2;
{
char *s = (char *) malloc (strlen(s1) + 10 + strlen(s2));
sprintf (s, "(%s && %s)", s1, s2);
free (s1);
free (s2);
return s;
}
char *do_or (s1, s2)
char *s1, *s2;
{
char *s = (char *) malloc (strlen(s1) + 10 + strlen(s2));
sprintf (s, "(%s || %s)", s1, s2);
free (s1);
free (s2);
return s;
}
char *do_cmp (s1, s2, d)
char *s1, *s2;
double d;
{
char *s = (char *) malloc (strlen(s1) + 20 + strlen(s2));
sprintf (s, "(%s %s %d)", s1, s2, (int) (d + 0.5));
free (s1);
free (s2);
return s;
}
build_rslts () /* build result functions */
{
register struct result *r;
register int i;
printf("#define N_RESULTS %d\n\n", n_RS);
if (n_RS < 1) {
printf("struct result RESULT[1];\n\n"); /* dummy for compilier happiness */
return;
}
for (i = n_RS; i--;)
printf ("void rs_func%d();\n", i);
printf("struct result RESULT[N_RESULTS] = {\n");
for (i = 0, r = RS; i < n_RS; r++, i++)
printf (" {\"%s\", %d, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, rs_func%d}%s",
r->name, r->type - 1, i, (i + 1 >= n_RS) ? "\n};\n\n" : ",\n");
for (i = 0, r = RS; i < n_RS; r++, i++) {
if (r->type == 1) {
printf ("void rs_func%d()\n{\n register double t = 0.0;\n%s", i, r->body);
printf (" RESULT[%d].acc += RESULT[%d].cur * (clock - RESULT[%d].t_last);\n", i, i, i);
printf (" RESULT[%d].cur = t;\n", i);
printf (" RESULT[%d].t_last = clock;\n}\n\n", i);
} else if (r->type == 2) {
printf ("void rs_func%d()\n{\n register double t = 0.0;\n%s", i, r->body);
printf (" RESULT[%d].sum += t;\n", i);
printf (" RESULT[%d].sum_sq += t * t;\n}\n\n", i);
} else if (r->type == 3) {
printf ("void rs_func%d()\n{\n register double t = 0.0;\n%s", i, r->body);
printf (" RESULT[%d].sum += t /= clock;\n", i);
printf (" RESULT[%d].sum_sq += t * t;\n}\n\n", i);
}
}
}
!E!O!F!
#
# type sh /usru1/agn/gspn/../gs.shar to unpack this archive.
#
echo extracting gs_pp.h...
cat >gs_pp.h <<'!E!O!F!'
/* definitions for the gs-preprocessor */
/* transition types */
#define TTY_IMM 0
#define TTY_EXP 1
#define TTY_DET 2
#define TTY_NRM 3
#define TTY_BIM 4
struct list_item {
unsigned short ind;
struct list_item *next;
};
struct place { /* a place */
char *name;
unsigned defined:1;
unsigned mdef:1;
unsigned short marks;
unsigned short n_input;
unsigned short n_output;
struct list_item *input_ptr;
struct list_item *inhib_ptr;
struct list_item *result_ptr;
};
struct transition { /* a transition */
char *name;
unsigned type:3;
unsigned def:1;
unsigned ddef:1;
double delay;
unsigned depdef:1;
int depend; /* dependency parameter */
unsigned short n_input;
unsigned short n_output;
unsigned short n_inhib;
struct list_item *input_ptr;
struct list_item *output_ptr;
struct list_item *inhib_ptr;
};
struct parameter { /* a parameter definition */
char *name;
unsigned defined:1;
unsigned short used, max_used; /* # of places used in */
unsigned type:1; /* 0: marking, 1: rate */
int *ind; /* usage index */
double value;
};
struct result {
char *name; /* name of result variable */
char *body; /* function body */
unsigned flg:1;
unsigned type:2; /* 0: undef, 1:dimensionless, 2:a time verage */
};
char *get_place(), *do_paren(), *do_or(), *do_cexp(), *concat(), *c_negate(),
*do_prob(), *do_cmp(), *do_cmp(), *do_and(), *do_exp();
extern char it_opr; /* item (result) operator */
!E!O!F!
#
# type sh /usru1/agn/gspn/../gs.shar to unpack this archive.
#
echo extracting gs_pp_lex.l...
cat >gs_pp_lex.l <<'!E!O!F!'
/************************************************************************\
* *
* GS: A Generalized, stochastic petri net Simulator *
* V0.01 March 1989 Andreas Nowatzyk (agn@unh.cs.cmu.edu) *
* Carnegie-Mellon Univerity, School of Computer Science *
* Schenley Park, Pittsburgh, PA 15213 *
* *
\************************************************************************/
%%
[ \n\t]* ; /* ignore white space */
"/*".*"*/" ; /* skip comments (\n problem) */
^"#".*\n {if (2 != sscanf (&yytext[1],"%d%s", &yylineno, src_file))
yyerror ("malformed cpp-directive");
}
^"%end" {return END;}
rate[ \n\t]*"=" {return RATE;}
"#marks"[ \n\t]*"=" {return MARKS;}
dep[ \n\t]*"=" {return DEPEND;}
det|deterministic {return DET;}
imm|immediate {return IMM;}
exp|exponential {return EXP;}
normal {return NORM;}
bimodal {return BIMOD;}
TRANS {return TRANS;}
PLACE {return PLACE;}
RESULT {return RESULT;}
PARAM {return PARAM;}
Prob {return PROB;}
Expt {return EXP;}
Dwell {return DWT;}
Fire {return FIRE;}
[A-Za-z_][A-Za-z0-9_]* {yylval.SYM = (char *) malloc (yyleng + 1);
strncpy (yylval.SYM, yytext, yyleng);
yylval.SYM[yyleng] = 0;
return NAME;}
[-+.0-9edED]+ {if (1 != sscanf(yytext, "%lf", &(yylval.VALUE))) REJECT;
return VAL;}
"=="|"!="|">="|"<="|">"|"<" {yylval.SYM = (char *) malloc (yyleng + 1);
strncpy (yylval.SYM, yytext, yyleng);
yylval.SYM[yyleng] = 0;
return REL_OP;}
";" {return TERM;}
"," {return SEP;}
":" {return COL;}
"/" {return COND;}
"-->" {return NEXT;}
"!" {return NOT;}
"{" {return OP_BR;}
"}" {return CL_BR;}
"(" {return OP_PAR;}
")" {return CL_PAR;}
"&&" {return AND;}
"||" {return OR;}
"#" {return HASH;}
"+" {return PLUS;}
"-" {return MINUS;}
%%
!E!O!F!
#
# type sh /usru1/agn/gspn/../gs.shar to unpack this archive.
#
echo extracting gs_pp_par.y...
cat >gs_pp_par.y <<'!E!O!F!'
%{
/************************************************************************\
* *
* GS: A Generalized, stochastic petri net Simulator *
* V0.01 March 1989 Andreas Nowatzyk (agn@unh.cs.cmu.edu) *
* Carnegie-Mellon Univerity, School of Computer Science *
* Schenley Park, Pittsburgh, PA 15213 *
* *
\************************************************************************/
/*
* Grammar of the GSPN-Simuator input format.
*
* I know that this isn't compatible with GreatSPAN's files,
* but I want something that could be understood with an normal
* text editor as well as with a specialized graphic tool. A simple
* list of numbers isn't my style.
*
*/
#include <strings.h>
#include <stdio.h>
#include "gs_pp.h"
char src_file[80] = "<stdin>", it_opr;
%}
%start gspn /* Grammar entry */
%union ytoken { char *SYM; double VALUE;}
%type <SYM> sum item marking logic_cond compare opt_val
%token <SYM> NAME REL_OP
%token <VALUE> VAL
%token END TERM SEP COL NEXT NOT RATE MARKS DEPEND DET IMM EXP TRANS PLACE RESULT PARAM
%token PROB EXP OP_BR CL_BR OP_PAR CL_PAR COND AND OR HASH PLUS MINUS BIMOD NORM DWT FIRE
%left OR
%left AND
%left NOT
%%
gspn : body END
;
body : statement
| body statement
;
statement : place TERM
| transition TERM
| parameter TERM
| result TERM
| error TERM
;
parameter : PARAM NAME VAL {add_param($2, $3);}
;
place : PLACE NAME {add_place($2);}
pl_plist
;
pl_plist :
| pl_params
;
pl_params : pl_param
| pl_params SEP pl_param
;
pl_param : MARKS VAL {chg_marks($2);}
| MARKS NAME {chg_p_marks($2);}
;
transition : TRANS NAME {add_transition($2);}
type COL from NEXT to
;
type : DET tr_plist {set_type(TTY_DET);}
| IMM tr_plist {set_type(TTY_IMM);}
| EXP tr_plist {set_type(TTY_EXP);}
| BIMOD tr_plist {set_type(TTY_BIM);}
| NORM tr_plist {set_type(TTY_NRM);}
;
tr_plist :
| tr_params
;
tr_params : tr_param
| tr_params SEP tr_param
;
tr_param : RATE VAL {chg_rate($2);}
| RATE NAME {chg_p_rate($2);}
| DEPEND VAL {chg_depend($2);}
;
from :
| from NAME {add_input($2);}
| from NOT NAME {add_inhib($3);}
;
to :
| to NAME {add_output($2);}
;
result : RESULT {ini_result();}
NAME COL sum {add_result($3, $5);}
;
sum : {it_opr = '+';} item {$$ = $2;}
| sum PLUS {it_opr = '+';} item {$$ = concat ($1, $4);}
| sum MINUS {it_opr = '-';} item {$$ = concat ($1, $4);}
;
item : opt_val PROB OP_BR logic_cond CL_BR {$$ = do_prob ($1, $4);}
| opt_val EXP OP_BR marking CL_BR {$$ = do_exp ($1, $4);}
| opt_val EXP OP_BR marking COND logic_cond CL_BR {$$ = do_cexp ($1, $4, $6);}
| opt_val DWT OP_BR NAME CL_BR {$$ = do_dwell ($1, $4);}
| opt_val FIRE OP_BR NAME CL_BR {$$ = do_fire ($1, $4);}
;
opt_val : {$$ = get_val(1.0);}
| VAL {$$ = get_val($1);}
| NAME {$$ = get_para($1);}
;
marking : HASH NAME {$$ = get_place ($2);}
;
logic_cond : compare
| NOT logic_cond {$$ = c_negate ($2);}
| OP_PAR logic_cond CL_PAR {$$ = do_paren ($2);}
| logic_cond AND logic_cond {$$ = do_and ($1, $3);}
| logic_cond OR logic_cond {$$ = do_or ($1, $3);}
;
compare : marking REL_OP VAL {$$ = do_cmp ($1, $2, $3);}
;
%%
#include "gs_pp_lex.c"
#include "gs_pp.c"
!E!O!F!
#
# type sh /usru1/agn/gspn/../gs.shar to unpack this archive.
#
echo extracting makefile...
cat >makefile <<'!E!O!F!'
OBJ = xrand.o gs_main.o
CFLAGS = -O
LIBS = -ll -lm
CC = cc
#
# The BIN directory will contain all files necessary to build an simulator
#
BIN = /usr/agn/bin
#
# To install the stuff do a 'make install'
#
# The installed files are:
#
# gs_pp : preprocessor to convert net-descriptions (*.n) files to an
# include file (sim.h)
# net2n : converts GreatSPN *.net files to *.n files
# def2n : likewise, but deals with *.def files
# GS.o : precompiled simulator modules
# gs.h : include file to build the simulator
# gs.c : compiles into static simulator structures
# mk_sim : a shell-script to put it all together
#
all: gs_pp GS.o net2n def2n
net2n: net2n.c
$(CC) $(CFLAGS) -o net2n net2n.c
def2n: def2n.c
$(CC) $(CFLAGS) -o def2n def2n.c -ll
gs_pp: gs_pp.c gs_pp.h gs_pp_lex.c gs_pp_par.c
$(CC) $(CFLAGS) -o gs_pp gs_pp_par.c $(LIBS)
GS.o: gs.h gs.c $(OBJ)
ld -r -o GS.o $(OBJ) -lm
install:
cp def2n net2n GS.o gs.c gs.h gs_pp $(BIN)
sed 's+DISTR-DIR+$(BIN)+g' < mk_sim > $(BIN)/mk_sim
chmod 755 $(BIN)/mk_sim
#
# This is used only for debugging gs
#
test: sim.h gs.h gs_main.c xrand.o gs.c
cc -o test -g gs.c gs_main.c xrand.o -lm
sim.h: gs_pp q.n
gs_pp < q.n > sim.h
!E!O!F!
#
# type sh /usru1/agn/gspn/../gs.shar to unpack this archive.
#
echo extracting mk_sim...
cat >mk_sim <<'!E!O!F!'
# C-shell please!
if ($1:e != "n") then
set pn = $1.n
def2n < $1.def > $pn
net2n < $1.net >> $pn
if ($status) then
echo "Problem in $1.net encountered"
exit (1)
endif
else
set pn = $1
endif
/lib/cpp $pn | gs_pp > sim.h
if ($status) then
echo "Preprocessing unsuccessful"
exit (1)
endif
cc -O -o $pn:r -I. DISTR-DIR/gs.c DISTR-DIR/GS.o
if($status) then
echo "Ooops, something went wrong"
else
rm sim.h
endif
!E!O!F!
#
# type sh /usru1/agn/gspn/../gs.shar to unpack this archive.
#
echo extracting net2n.c...
cat >net2n.c <<'!E!O!F!'
/************************************************************************\
* *
* GS: A Generalized, stochastic petri net Simulator *
* V0.01 March 1989 Andreas Nowatzyk (agn@unh.cs.cmu.edu) *
* Carnegie-Mellon Univerity, School of Computer Science *
* Schenley Park, Pittsburgh, PA 15213 *
* *
\************************************************************************/
/* Converts GreatSPN's net-files into a more resonable format */
#include <stdio.h>
#define TTY_IMM 0 /* transition types */
#define TTY_EXP 1
#define TTY_DET 2
char *trns_types[3] = {"imm", "exp", "det"};
/******************** Data structures ********************/
struct place { /* A place is... */
char *name;
int tokens;
};
struct place_list { /* list of places */
struct place *pl;
struct place_list *next;
};
struct transition { /* A transition is... */
char *name;
unsigned char type;
double rate;
int dep; /* enabling dependency */
struct place_list *inpts;
struct place_list *outpts;
struct place_list *inhibs;
};
struct parameter { /* parameters */
char *name;
double deflt;
};
/******************** Net storage ********************/
struct place *PLACES;
int n_PL;
struct transition *TRANSITIONS;
int n_TR;
struct parameter *RATES, *MARKS;
int n_RT, n_MK;
main(argc, argv) /* boring stuff */
int argc;
char *argv[];
{
read_net();
print_net();
}
read_net () /* read a network */
{
register int i, j;
int n_GR, k, l, m;
register struct place_list *t;
char buf[1024], tmp[1024];
while (gets(buf)) /* skip preamble */
if (buf[0] == '|' && buf[1] == 0)
break;
if (!gets(buf) || 5 != sscanf(buf, "%*s%d%d%d%d%d", &n_MK, &n_PL, &n_RT, &n_TR, &n_GR) ||
n_MK < 0 || n_PL < 1 || n_RT < 0 || n_TR < 1 || n_GR < 0)
err("Bogus parameters");
/* allocate storrage */
if (n_MK) MARKS = (struct parameter *) malloc(n_MK * sizeof(struct parameter));
if (n_RT) RATES = (struct parameter *) malloc(n_RT * sizeof(struct parameter));
PLACES = (struct place *) malloc(n_PL * sizeof(struct place));
TRANSITIONS = (struct transition *) malloc(n_TR * sizeof(struct transition));
for (i = 0; i < n_MK; i++) { /* read mark-parameters */
if (!gets(buf)) err("Premature end of file");
if (2 != sscanf(buf, "%s%lf", tmp, &(MARKS[i].deflt)))
err("Param problem");
strcpy(MARKS[i].name = (char *) malloc(strlen(tmp) + 1), tmp);
}
for (i = 0; i < n_PL; i++) { /* read places */
if (!gets(buf)) err("Premature end of file");
if (2 != sscanf(buf, "%s%d", tmp, &(PLACES[i].tokens)))
err("Place def problem");
strcpy(PLACES[i].name = (char *) malloc(strlen(tmp) + 1), tmp);
}
for (i = 0; i < n_RT; i++) { /* read rate-parameters */
if (!gets(buf)) err("Premature end of file");
if (2 != sscanf(buf, "%s%lf", tmp, &(RATES[i].deflt)))
err("Param problem");
strcpy(RATES[i].name = (char *) malloc(strlen(tmp) + 1), tmp);
}
for (i = 0; i < n_GR; i++) /* skip groups */
if (!gets(buf)) err("Premature end of file");
for (i = 0; i < n_TR; i++) {/* read transitions */
if (!gets(buf)) err("Premature end of file");
if (5 != sscanf(buf, "%s%lf%d%d%d", tmp, &(TRANSITIONS[i].rate), &(TRANSITIONS[i].dep), &k, &l) || l < 1)
err("Transition def problem");
switch (k) {
case 0:
TRANSITIONS[i].type = TTY_EXP;
break;
case 1:
TRANSITIONS[i].type = TTY_IMM;
break;
case 127:
TRANSITIONS[i].type = TTY_DET;
if (TRANSITIONS[i].rate < 1e-10)
err("0-delay, deterministic transition");
TRANSITIONS[i].rate = 1.0 / TRANSITIONS[i].rate;
break;
default:
err("Unknown transition type");
}
strcpy(TRANSITIONS[i].name = (char *) malloc(strlen(tmp) + 1), tmp);
TRANSITIONS[i].inpts = 0;
TRANSITIONS[i].outpts = 0;
TRANSITIONS[i].inhibs = 0;
for (j = l; j--;) { /* read inputs */
if (!gets(buf)) err("Premature end of file");
if (3 != sscanf(buf, "%d%d%d", &k, &l, &m) || !k || --l < 0 || l >= n_PL || m < 0)
err("Transition input def problem");
if(k < 0) k = -k;
while (k--) {
t = (struct place_list *) malloc (sizeof(struct place_list));
t->pl = &PLACES[l];
t->next = TRANSITIONS[i].inpts;
TRANSITIONS[i].inpts = t;
}
while (m--) /* skip geo-info */
if (!gets(buf)) err("Premature end of file");
}
if (!gets(buf)) err("Premature end of file");
if (1 != sscanf (buf, "%d", &k) || k < 1) err("TR output problem");
for (j = k; j--;) { /* read outputs */
if (!gets(buf)) err("Premature end of file");
if (3 != sscanf(buf, "%d%d%d", &k, &l, &m) || !k || --l < 0 || l >= n_PL || m < 0)
err("Transition output def problem");
if(k < 0) k = -k;
while (k--) {
t = (struct place_list *) malloc (sizeof(struct place_list));
t->pl = &PLACES[l];
t->next = TRANSITIONS[i].outpts;
TRANSITIONS[i].outpts = t;
}
while (m--) /* skip geo-info */
if (!gets(buf)) err("Premature end of file");
}
if (!gets(buf)) err("Premature end of file");
if (1 != sscanf (buf, "%d", &k) || k < 0) err("TR inhibt problem");
for (j = k; j--;) { /* read inhibits */
if (!gets(buf)) err("Premature end of file");
if (3 != sscanf(buf, "%d%d%d", &k, &l, &m) || !k || --l < 0 || l >= n_PL || m < 0)
err("Transition inhibit def problem");
if (k) {
t = (struct place_list *) malloc (sizeof(struct place_list));
t->pl = &PLACES[l];
t->next = TRANSITIONS[i].inhibs;
TRANSITIONS[i].inhibs = t;
}
while (m--) /* skip geo-info */
if (!gets(buf)) err("Premature end of file");
}
}
}
err(s)
char *s;
{
fprintf (stderr, "%s\n", s);
exit(1);
}
print_net () /* print the garbage */
{
register int i, j;
register struct place_list *t;
for (i = 0; i < n_MK; i++)
printf ("PARAM %s %.10e;\n", MARKS[i].name, MARKS[i].deflt);
for (i = 0; i < n_RT; i++)
printf ("PARAM %s %.10e;\n", RATES[i].name, RATES[i].deflt);
for (i = 0; i < n_PL; i++) {
j = PLACES[i].tokens;
if (j < 0) {
j = -1 - j;
if (j >= n_MK)
err ("Marking parameter problem");
printf ("PLACE %s #marks= %s;\n", PLACES[i].name, MARKS[j].name);
} else
printf ("PLACE %s #marks= %d;\n", PLACES[i].name, j);
}
for (i = 0; i < n_TR; i++) {
if (TRANSITIONS[i].rate < 0) {
j = -0.5 - TRANSITIONS[i].rate;
if (j >= n_RT)
err ("Rate parameter problem");
printf ("TRANS %s %s rate= %s, dep= %d : ", TRANSITIONS[i].name,
trns_types[TRANSITIONS[i].type], RATES[j].name, TRANSITIONS[i].dep);
} else
printf ("TRANS %s %s rate= %e, dep= %d : ", TRANSITIONS[i].name,
trns_types[TRANSITIONS[i].type], TRANSITIONS[i].rate, TRANSITIONS[i].dep);
for (t = TRANSITIONS[i].inpts; t; t = t->next)
printf ("%s ", t->pl->name);
for (t = TRANSITIONS[i].inhibs; t; t = t->next)
printf ("!%s ", t->pl->name);
printf ("-->");
for (t = TRANSITIONS[i].outpts; t; t = t->next)
printf (" %s", t->pl->name);
printf(";\n");
}
printf("#end\n");
}
!E!O!F!
#
# type sh /usru1/agn/gspn/../gs.shar to unpack this archive.
#
echo extracting xrand.c...
cat >xrand.c <<'!E!O!F!'
#include <math.h>
/* Random number generators:
*
* rnd_init (unsigned seed)
* : initializes the generator
*
* rnd_i () : returns positive integers [0,0x7fffffff]
* rnd_u () : returns unsigned's [0,0xffffffff]
* rnd_ri (long n) : returns positive integers [0,n-1]
* rnd_01d () : returns doubles [0.0,1.0)
* Note: ")" is no typo - rnd_01d will not return a 1.0,
* but can return the next smaller FP number.
* rnd_ned (double lam): returns neg. exponential distributed doubles [0.0,+inf)
* rnd_nedi (double rt): same with lam = 1/rt - used to save divides
*
* Algorithm M as describes in Knuth's "Art of Computer Programming", Vol 2. 1969
* is used with a linear congruential generator (to get a good uniform
* distribution) that is permuted with a Fibonacci additive congruential
* generator to get good independence.
*
* Bit, byte, and word distributions were extensively tested and pass
* Chi-squared test near perfect scores (>7E8 numbers tested, Uniformity
* assumption holds with probability > 0.999)
*
* Run-up tests for on 7E8 numbers confirm independence with
* probability > 0.97.
*
* Plotting random points in 2d reveals no apparent structure.
*
* Autocorrelation on sequences of 5E5 numbers (A(i) = SUM X(n)*X(n-i), i=1..512)
* results in no obvious structure (A(i) ~ const).
*
* On a SUN 3/60, rnd_u() takes about 19.4 usec per call, which is about 44%
* slower than Berkeley's random() (13.5 usec/call).
*
* Except for speed and memory requirements, this generator outperforms
* random() for all tests. (random() scored rather low on uniformity tests,
* while independence test differences were less dramatic).
*
* Thanks to M.Mauldin, H.Walker, J.Saxe and M.Molloy for inspiration & help.
*
* (c) Copyright 1988 by A. Nowatzyk
*
*/
/* LC-parameter selection follows recommendations in
* "Handbook of Mathematical Functions" by Abramowitz & Stegun 10th, edi.
*/
#define LC_A 66049 /* = 251^2, ~= sqrt(2^32) */
#define LC_C 3907864577 /* result of a long trial & error series */
#define Xrnd(x) (x * LC_A + LC_C) /* the LC polynomial */
static unsigned long Fib[55]; /* will use X(n) = X(n-55) - X(n-24) */
static int Fib_ind; /* current index in circular buffer */
static unsigned long Xrnd_var; /* LCA - recurrence variable */
static unsigned long auxtab[256]; /* temporal permutation table */
static unsigned long prmtab[64] = { /* spatial permutation table */
0xffffffff, 0x00000000, 0x00000000, 0x00000000, /* 3210 */
0x0000ffff, 0x00ff0000, 0x00000000, 0xff000000, /* 2310 */
0xff0000ff, 0x0000ff00, 0x00000000, 0x00ff0000, /* 3120 */
0x00ff00ff, 0x00000000, 0xff00ff00, 0x00000000, /* 1230 */
0xffff0000, 0x000000ff, 0x00000000, 0x0000ff00, /* 3201 */
0x00000000, 0x00ff00ff, 0x00000000, 0xff00ff00, /* 2301 */
0xff000000, 0x00000000, 0x000000ff, 0x00ffff00, /* 3102 */
0x00000000, 0x00000000, 0x00000000, 0xffffffff, /* 2103 */
0xff00ff00, 0x00000000, 0x00ff00ff, 0x00000000, /* 3012 */
0x0000ff00, 0x00000000, 0x00ff0000, 0xff0000ff, /* 2013 */
0x00000000, 0x00000000, 0xffffffff, 0x00000000, /* 1032 */
0x00000000, 0x0000ff00, 0xffff0000, 0x000000ff, /* 1023 */
0x00000000, 0xffffffff, 0x00000000, 0x00000000, /* 0321 */
0x00ffff00, 0xff000000, 0x00000000, 0x000000ff, /* 0213 */
0x00000000, 0xff000000, 0x0000ffff, 0x00ff0000, /* 0132 */
0x00000000, 0xff00ff00, 0x00000000, 0x00ff00ff /* 0123 */
};
union hack { /* used to access doubles as unsigneds */
double d;
unsigned long u[2];
};
static union hack man; /* mantissa bit vector */
rnd_init (seed) /* modified: seed 0-31 use precomputed stuff */
unsigned seed;
{
register unsigned long u;
register int i;
double x, y;
union hack t;
static unsigned seed_tab[32] = {
0xbdcc47e5, 0x54aea45d, 0xec0df859, 0xda84637b,
0xc8c6cb4f, 0x35574b01, 0x28260b7d, 0x0d07fdbf,
0x9faaeeb0, 0x613dd169, 0x5ce2d818, 0x85b9e706,
0xab2469db, 0xda02b0dc, 0x45c60d6e, 0xffe49d10,
0x7224fea3, 0xf9684fc9, 0xfc7ee074, 0x326ce92a,
0x366d13b5, 0x17aaa731, 0xeb83a675, 0x7781cb32,
0x4ec7c92d, 0x7f187521, 0x2cf346b4, 0xad13310f,
0xb89cff2b, 0x12164de1, 0xa865168d, 0x32b56cdf };
if (seed < 32)
u = seed_tab[seed];
else
u = seed ^ seed_tab[seed & 31];
for (i = 55; i--;) /* set up Fibonacci additive congruential */
Fib[i] = u = Xrnd(u);
for (i = 256; i--;)
auxtab[i] = u = Xrnd(u);
Fib_ind = u % 55; /* select a starting point */
Xrnd_var = u;
if (sizeof(x) != 2 * sizeof(unsigned long)) {
x = 0.0;
y = 1.0;
y /= x; /*** intentional divide by 0: rnd_01d will
not work because a double doesn't fit
in 2 unsigned longs on your machine! ***/
};
x = 1.0;
y = 0.5;
do { /* find largest fp-number < 2.0 */
t.d = x;
x += y;
y *= 0.5;
} while (x != t.d && x < 2.0);
man.d = 1.0;
man.u[0] ^= t.u[0];
man.u[1] ^= t.u[1]; /* man is now 1 for each mantissa bit */
}
long rnd_i ()
/*
* returns a positive, uniformly distributed random number in [0,0x7fffffff]
*/
{
register unsigned long i, j, *t = Fib;
i = Fib_ind;
j = t[i]; /* = X(n-55) */
j -= (i >= 24) ? t[i - 24] : t[i + 21]; /* = X(n-24) */
t[i] = j;
if (++i >= 55) i = 0;
Fib_ind = i;
t = &auxtab[(j >> 24) & 0xff];
i = *t;
Xrnd_var = *t = Xrnd(Xrnd_var);
t = &prmtab[j & 0x3c];
j = *t++ & i;
j |= *t++ & ((i << 24) | ((i >> 8) & 0x00ffffff));
j |= *t++ & ((i << 16) | ((i >> 16) & 0x0000ffff));
j |= *t & ((i << 8) | ((i >> 24) & 0x000000ff));
return j & 0x7fffffff;
}
unsigned long rnd_u ()
/*
* same as rnd_i, but gives full 32 bit range
*/
{
register unsigned long i, j, *t = Fib;
i = Fib_ind;
j = t[i]; /* = X(n-55) */
j -= (i >= 24) ? t[i - 24] : t[i + 21]; /* = X(n-24) */
t[i] = j;
if (++i >= 55) i = 0;
Fib_ind = i;
t = &auxtab[(j >> 24) & 0xff];
i = *t;
Xrnd_var = *t = Xrnd(Xrnd_var);
t = &prmtab[j & 0x3c];
j = *t++ & i;
j |= *t++ & ((i << 24) | ((i >> 8) & 0x00ffffff));
j |= *t++ & ((i << 16) | ((i >> 16) & 0x0000ffff));
j |= *t & ((i << 8) | ((i >> 24) & 0x000000ff));
return j;
}
long rnd_ri (rng)
long rng;
/*
* randint: Return a random integer in a given Range [0..rng-1]
* Note: 0 < rng
*/
{
register unsigned long r, a;
do {
r = rnd_i();
a = (r / rng) + 1;
a *= rng;
} while (a >= 0x7fffffff);
a--;
return a - r;
}
double rnd_01d ()
/*
* returns a uniformly distributed double in the range of [0..1)
* or 0.0 <= rnd_01d() < 1.0 to be precise
*
* Note: this code assumes that 2 'unsigned long's can hold a 'double'
* (works on SUN-3's, SUN-4's, MIPS, VAXen, IBM RT's)
*/
{
union hack t;
t.d = 1.0;
t.u[0] |= rnd_u() & man.u[0]; /* munch in 1st part */
t.u[1] |= rnd_u() & man.u[1]; /* munch in 2nd part */
return t.d - 1.0;
}
double rnd_ned (lam)
double lam;
/*
* returns a neg. exponential distributed double in the range of [0..+infinity)
* or 0.0 <= rnd_neg() < +infinity to be precise
*
* Note: this code assumes that 2 'unsigned long's can hold a 'double'
* it also assumes that 'log()' behaves as advertised.
*
*/
{
union hack t;
t.d = 1.0;
t.u[0] |= rnd_u() & man.u[0]; /* munch in 1st part */
t.u[1] |= rnd_u() & man.u[1]; /* munch in 2nd part */
return -log(2.0 - t.d) / lam;
}
double rnd_nedi (lam)
double lam;
/*
* same as 'rnd_ned' called with 1/lam
*
* This is used to save a divide operation in some places
*
*/
{
union hack t;
t.d = 1.0;
t.u[0] |= rnd_u() & man.u[0]; /* munch in 1st part */
t.u[1] |= rnd_u() & man.u[1]; /* munch in 2nd part */
return -log(2.0 - t.d) * lam;
}
!E!O!F!
--
-- Andreas Nowatzyk (DC5ZV)
Carnegie-Mellon University agn@unh.cs.cmu.edu
Computer Science Department (412) 268-3617