/* 
 * Copyright (C) 2005, Robert Geist, Jacob Hicks, Mark Smotherman, James Westall
 * All rights reserved.
 *
 * cg_petri_pb2.c: Cg/OpenGL program to simulate non-timed Petri nets (or timed
 * nets where all firing times are fixed to a single constant) using floating
 * point pbuffers. 
 *
 * gcc -L/usr/lib -L/usr/X11R6/lib cg_petri_pb2.c -lpthread -lglut -lGLU -lGL 
 *     -lCg -lCgGL -lXmu -lXi -lXext -lX11 -o cg_petri_pb2
 *
 * cg_petri_pb2 whatever.dat 2> catch_err
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <GL/gl.h>
#include <GL/glx.h>
#include <GL/glext.h>
#include <Cg/cg.h>
#include <Cg/cgGL.h>
#include "cg_petri_pb2.h"

/* 
 * texture storage and codes therein:
 *
 * place texture:  token count
 * reservation texture:  token reservation count (per place)
 * transition texture: enabled or not
 *              
 * incidence textures (2D):
 * 		   height     width
 *	t_inputp[transition][iplace]: for each transition, a list of
 *		input places
 *
 *	p_inputt[place][itransition]: for each place, a list of
 *		input transitions
 *
 *	p_outputt[place][otransition]: for each place, a list of
 *		output transitions
 */
float t_inputp[TRANSITIONS*MAX_T_IN_DEGREE];
float p_inputt[PLACES*MAX_P_IN_DEGREE];
float p_outputt[PLACES*MAX_P_OUT_DEGREE];

/*
 * the top index in each of these is used for a dummy node to 
 * rectangularize the tests in the Cg part and thereby avoid
 * conditionals; the dummy place (index PLACES-1) will have a 
 * large supply of tokens so that it will never be over-subscribed
 * and never interfere with any enabling ; the dummy transition 
 * (index TRANSITIONS-1) will never be enabled
 *
 * the only catch here is to remember to declare (in .h) 1 more
 * than you need; there is no longer any power-of-2 restriction
 */
float places[PLACES];
float reservations[PLACES];
float transitions[TRANSITIONS];

void set_token_count(int place,int count)
{
places[place] = (float)(count);
}

void init_places()
{
int i;
for(i=0;i<PLACES;i++){
	places[i] = 0.0;
	reservations[i] = 0.0;
	}
/* dump a full supply of tokens into the dummy place */
set_token_count(PLACES-1,TRANSITIONS-1);
}

void init_incidence()
{
int i,j;
for(i=0;i<TRANSITIONS;i++){
	for(j=0;j<MAX_T_IN_DEGREE;j++){
		/* start with all input arcs from the dummy place */
		t_inputp[MAX_T_IN_DEGREE*i+j] = (float)(PLACES-1);
		}
	}
for(i=0;i<PLACES;i++){
	/* start with all input and output arcs to the dummy transition */
	for(j=0;j<MAX_P_IN_DEGREE;j++){
		p_inputt[MAX_P_IN_DEGREE*i+j] = (float)(TRANSITIONS-1);
		}
	for(j=0;j<MAX_P_OUT_DEGREE;j++){
		p_outputt[MAX_P_OUT_DEGREE*i+j] = (float)(TRANSITIONS-1);
		}
	}
}

void init_transitions()
{
int i;
for(i=0;i<TRANSITIONS;i++) transitions[i] = 0.0;
}

void set_input_arc(int place, int transition)
{
int j;
/* arc from place to transition must be stored twice */

/* find first free slot among the list of input places (to this transition) */
for(j=0;t_inputp[MAX_T_IN_DEGREE*transition+j]!=((float)(PLACES-1));j++);
t_inputp[MAX_T_IN_DEGREE*transition+j]=(float)(place);

/* find first free slot among the output transitions (from this place) */
for(j=0;p_outputt[MAX_P_OUT_DEGREE*place+j]!=((float)(TRANSITIONS-1));j++);
p_outputt[MAX_P_OUT_DEGREE*place+j]=(float)(transition);
}

void set_output_arc(int transition, int place)
{
int j;
/* arc from transition to place is stored just once */

/* find first free slot among the list of input transitions (to this place) */
for(j=0;p_inputt[MAX_P_IN_DEGREE*place+j]!=((float)(TRANSITIONS-1));j++);
p_inputt[MAX_P_IN_DEGREE*place+j]=((float)(transition));
}

/* 
 * get the next line of real data; snarf all the comments or blank lines;
 * return 1 on success, 0 on EOF
 */
int nextline(FILE *fptr, unsigned char *lbuffer)
{
do{
	if(!fgets(lbuffer,512,fptr)) return(0);
	} while(lbuffer[0]=='#' || lbuffer[0]==' ' || lbuffer[0]=='\n');
return(1);
}

/*
 * trivial parser
 */
void load_geometry(char *filename)
{
FILE  *fptr;
unsigned char buf[512], *parse;
int place_index, transition_index, place_count;

fptr=fopen(filename,"r");

while(nextline(fptr,buf)){ 
	parse = strtok(buf," \t");
	if(strcmp(parse,"place_tokens")==0){
		parse = strtok(NULL," \t");
		place_index = atoi(parse);
		parse = strtok(NULL," \t\n");
		place_count = atoi(parse);
		set_token_count(place_index,place_count);
		}
	if(strcmp(parse,"input_arc")==0){
		parse = strtok(NULL," \t");
		place_index = atoi(parse);
		parse = strtok(NULL," \t\n");
		transition_index = atoi(parse);
		set_input_arc(place_index,transition_index);
		}
	if(strcmp(parse,"output_arc")==0){
		parse = strtok(NULL," \t");
		transition_index = atoi(parse);
		parse = strtok(NULL," \t\n");
		place_index = atoi(parse);
		set_output_arc(transition_index,place_index);
		} 
	} 
fclose(fptr);
}

void init_textures(char *filename)
{
int i,j;
init_places();
init_transitions();
init_incidence();
load_geometry(filename);
}

CGprogram	fp[3];
char *fpname[3] = {
	"enable",
	"count_reservations",
	"fire"
	};

/* 6 textures (5 read by Cg) potentially available to each of 3 programs */
CGparameter	texture_places[3], texture_transitions[3], texture_tip[3], 
		texture_pit[3], texture_pot[3];

void load_textures_onto_card()
{
glBindTexture(GL_TEXTURE_RECTANGLE_NV,1);
glTexImage2D(GL_TEXTURE_RECTANGLE_NV,0,GL_FLOAT_R_NV,MAX_T_IN_DEGREE,
		TRANSITIONS,0,GL_RED,GL_FLOAT,t_inputp);

glBindTexture(GL_TEXTURE_RECTANGLE_NV,2);
glTexImage2D(GL_TEXTURE_RECTANGLE_NV,0,GL_FLOAT_R_NV,MAX_P_IN_DEGREE,
		PLACES,0,GL_RED,GL_FLOAT,p_inputt);

glBindTexture(GL_TEXTURE_RECTANGLE_NV,3);
glTexImage2D(GL_TEXTURE_RECTANGLE_NV,0,GL_FLOAT_R_NV,MAX_P_OUT_DEGREE,
		PLACES,0,GL_RED,GL_FLOAT,p_outputt);

/* places contain token counts; must use PLACESx1 rectangle */
glBindTexture(GL_TEXTURE_RECTANGLE_NV,4);
glTexImage2D(GL_TEXTURE_RECTANGLE_NV,0,GL_FLOAT_R_NV,PLACES,1,0,GL_RED,
		GL_FLOAT,places);

glBindTexture(GL_TEXTURE_RECTANGLE_NV,5);
glTexImage2D(GL_TEXTURE_RECTANGLE_NV,0,GL_FLOAT_R_NV,PLACES,1,0,GL_RED,
		GL_FLOAT,reservations);

/* transitions contain enabled or not */
glBindTexture(GL_TEXTURE_RECTANGLE_NV,6);
glTexImage2D(GL_TEXTURE_RECTANGLE_NV,0,GL_FLOAT_R_NV,TRANSITIONS,1,0,GL_RED,
		GL_FLOAT,transitions);

/*
 * We don't want to have to pass all textures to all Cg functions, so
 * link just those needed, per program, here.  The indices are:
 * ENABLE: write_transitions
 * COUNT_RES: write_reservations
 * FIRE: write_places
 * Note that texture number 5, reservations, is not read by Cg
 */
texture_tip[ENABLE]=cgGetNamedParameter(fp[ENABLE],"tex_tip");
texture_places[ENABLE]=cgGetNamedParameter(fp[ENABLE],"tex_p");
cgGLSetTextureParameter(texture_tip[ENABLE],1);
cgGLSetTextureParameter(texture_places[ENABLE],4);

texture_pot[COUNT_RES]=cgGetNamedParameter(fp[COUNT_RES],"tex_pot");
texture_transitions[COUNT_RES]=cgGetNamedParameter(fp[COUNT_RES],"tex_t");
cgGLSetTextureParameter(texture_pot[COUNT_RES],3);
cgGLSetTextureParameter(texture_transitions[COUNT_RES],6);

texture_pit[FIRE]=cgGetNamedParameter(fp[FIRE],"tex_pit");
texture_pot[FIRE]=cgGetNamedParameter(fp[FIRE],"tex_pot");
texture_places[FIRE]=cgGetNamedParameter(fp[FIRE],"tex_p");
texture_transitions[FIRE]=cgGetNamedParameter(fp[FIRE],"tex_t");
cgGLSetTextureParameter(texture_pit[FIRE],2);
cgGLSetTextureParameter(texture_pot[FIRE],3);
cgGLSetTextureParameter(texture_places[FIRE],4);
cgGLSetTextureParameter(texture_transitions[FIRE],6);
}

/* 
 * all-purpose target for glReadPixels(); row 0 gets transitions, row 1
 * gets reservations, row 2 gets places 
 */
#define rowT 0
#define rowR 1
#define rowP 2

float pixels[3*MAX_TRANSITIONS_PLACES];

/* 
 * We reset the default window with glOrtho to go from 0 to 
 * MAX_TRANSITIONS_PLACES.  Note that integer indices are located 
 * at the edges, not centers, of the pixels.  Also note that if
 * we write the dummy transition, it will try to enable itself 
 * and succeed, so don't do that.
 */
void write_transitions(int debug)
{
int i;

cgGLBindProgram(fp[ENABLE]);
/* 
 * This is critical.  You must enable all that you attempt to access on
 * the Cg side. 
 */

cgGLEnableTextureParameter(texture_tip[ENABLE]);
cgGLEnableTextureParameter(texture_places[ENABLE]);

glBegin(GL_QUADS);
/* first coordinate is upper left corner of 1-pixel-high strip */
glTexCoord2i(0,0);
glVertex2i(0,rowT+1);
/* now lower left corner of same strip */
glTexCoord2i(0,1);
glVertex2i(0,rowT);
/* now go to far edge of the bottom of the strip, but leave off dummy */
glTexCoord2i(TRANSITIONS-1,1);
glVertex2i(TRANSITIONS-1,rowT);
/* and finally up 1 */
glTexCoord2i(TRANSITIONS-1,0);
glVertex2i(TRANSITIONS-1,rowT+1);
glEnd();
glFlush();
/* 
 * This is also critical.  Commands like glCopyTexSubImage() need 
 * glBindTexture() to declare which is the "current" texture, and
 * the Cg bindings won't suffice.
 */
glBindTexture(GL_TEXTURE_RECTANGLE_NV,6);
glCopyTexSubImage2D(GL_TEXTURE_RECTANGLE_NV,0,0,0,0,rowT,TRANSITIONS-1,1);

if(debug){
	/* and there's no need to read the extra ones either */
	glReadPixels(0,rowT,TRANSITIONS-1,1,GL_RED,GL_FLOAT,pixels);
	for(i=0;i<TRANSITIONS-1;i++){
		fprintf(stderr,"transition %d: %f\n",i,pixels[i]);
		}
	}
}

void write_places(int debug)
{
int i,j;
float texture_dim;

/*
fprintf(stderr,"fire\n");
*/
cgGLBindProgram(fp[FIRE]);

cgGLEnableTextureParameter(texture_pit[FIRE]);
cgGLEnableTextureParameter(texture_pot[FIRE]);
cgGLEnableTextureParameter(texture_transitions[FIRE]);
cgGLEnableTextureParameter(texture_places[FIRE]);

glBegin(GL_QUADS);
glTexCoord2i(0,0);
glVertex2i(0,rowP+1);
glTexCoord2i(0,1);
glVertex2i(0,rowP);
glTexCoord2i(PLACES-1,1);
glVertex2i(PLACES-1,rowP);
glTexCoord2i(PLACES-1,0);
glVertex2i(PLACES-1,rowP+1);
glEnd();
glFlush();
glBindTexture(GL_TEXTURE_RECTANGLE_NV,4);
glCopyTexSubImage2D(GL_TEXTURE_RECTANGLE_NV,0,0,0,0,rowP,PLACES-1,1);

if(debug){
	glReadPixels(0,rowP,PLACES-1,1,GL_RED,GL_FLOAT,pixels);
	for(i=0;i<PLACES-1;i++){
		fprintf(stderr,"place %d: %f\n",i,pixels[i]);
		}
	}
}

void write_reservations(int debug)
{
int i,j;
float texture_dim;

cgGLBindProgram(fp[COUNT_RES]);

cgGLEnableTextureParameter(texture_pot[COUNT_RES]);
cgGLEnableTextureParameter(texture_transitions[COUNT_RES]);

glBegin(GL_QUADS);
glTexCoord2i(0,0);
glVertex2i(0,rowR+1);
glTexCoord2i(0,1);
glVertex2i(0,rowR);
glTexCoord2i(PLACES-1,1);
glVertex2i(PLACES-1,rowR);
glTexCoord2i(PLACES-1,0);
glVertex2i(PLACES-1,rowR+1);
glEnd();
glFlush();
glBindTexture(GL_TEXTURE_RECTANGLE_NV,5);
glCopyTexSubImage2D(GL_TEXTURE_RECTANGLE_NV,0,0,0,0,rowR,PLACES-1,1);

if(debug){
	glReadPixels(0,rowR,PLACES-1,1,GL_RED,GL_FLOAT,pixels);
	for(i=0;i<PLACES-1;i++){
		fprintf(stderr,"reservation %d: %f\n",i,pixels[i]);
		}
	}
}

double genrand()
{
static int flag = 1;
if(flag){
	srandom(123456789);
	flag=0;
	}
return(((double)(random())+1.0)/((double)(RAND_MAX)+2.0));
}


void draw()
{
int i,j,k;
int loop;
int scratch_ct[MAX_P_OUT_DEGREE];
int scratch_op[PLACES-1];
int sc, ti, pi;
int disable;
int sffl, zap;
int over_sub, new_over_sub;
int sopi;
int osip_count, top_count, npi;


glEnable(GL_TEXTURE_RECTANGLE_NV);
glClearColor(0.8,0.7,0.6,0.0);
glOrtho(0.0,(float)(MAX_TRANSITIONS_PLACES),0.0,3.0,-1.0,1.0);
glClear(GL_COLOR_BUFFER_BIT);

for(loop=0;loop<MAXLOOPS;loop++){
	write_transitions(1);
	write_reservations(1);
	glReadPixels(0,1,PLACES-1,1,GL_RED,GL_FLOAT,reservations);
	/*
	 * we want a fast exit when there are no conflicts, but we
	 * have to walk the list once anyway, so we might as well 
	 * save the offending places
	 */
	over_sub=0;
	for(i=0;i<PLACES-1;i++){
		disable = (int)(reservations[i]) - (int)(places[i]);
		/*
		fprintf(stderr,"place %d oversub is %d\n",i,disable);
		*/
		if(disable>0) scratch_op[over_sub++] = i;
		}
	if(over_sub){
		/* 
		 * we have conflicts, and resolution isn't easy; first,
		 * we'll need the list of enabled transitions
		 */
		glReadPixels(0,0,TRANSITIONS-1,1,GL_RED,GL_FLOAT,transitions);
		do {
			/* select at random from over-subcribed place list */
			sopi = (int)(over_sub*genrand());
			pi = scratch_op[sopi];

			/* 
			 * build scratch list of enabled transitions that want 
			 * tokens from this place; but, we only want those
			 * enabled transitions that carry a maximal number of 
			 * over-subscribed input places, so that disabling one 
			 * will give us the largest possible reduction in 
			 * over-subscriptions; so, restart the list whenever 
			 * we find a larger value 
			 */
			sc=0;
			top_count=0;
			for(j=0;j<MAX_P_OUT_DEGREE;j++){
				ti = (int)p_outputt[pi*MAX_P_OUT_DEGREE+j];
				if(transitions[ti]){ 
					/* count its over-subscribed inputs */
					osip_count=0;
					for(k=0;k<MAX_T_IN_DEGREE;k++){
						npi = (int)(t_inputp[ti*
							MAX_T_IN_DEGREE+k]);
						if(reservations[npi]>
							places[npi]){ 
							osip_count++;
							}
						}
					if(osip_count<top_count) continue;
					if(osip_count>top_count){
						top_count=osip_count;
						sc=0;
						}
					scratch_ct[sc++] = ti;
					}
				}
			/* zap excess entries from this scratch list */
			disable = (int)(reservations[pi]) - (int)(places[pi]);
			while(disable--){
				zap = (int)(sc*genrand());
				ti = scratch_ct[zap];
				transitions[ti] = 0;
				for(sffl=zap+1;sffl<sc;sffl++){
					scratch_ct[sffl-1] = scratch_ct[sffl];
					}
				sc--;
				/* 
				 * for this transition that we just zapped,
				 * we must decrement the reservation count
				 * in all its input places so that other
				 * transitions won't still be in conflict
				 */
				for(k=0;k<MAX_T_IN_DEGREE;k++){
					pi = (int)(t_inputp[ti*MAX_T_IN_DEGREE
						+k]);
					if(pi<PLACES-1) reservations[pi]--;
					}
				}
			/* rebuild the over-sub list from the scratch list */
			new_over_sub=0;
			for(i=0;i<over_sub;i++){
				pi = scratch_op[i];
				disable = (int)(reservations[pi]) - 
					(int)(places[pi]);
				if(disable>0) scratch_op[new_over_sub++] = pi;
				}
			} while(over_sub=new_over_sub);
		/* changed those enabled, so write it back out */
		glBindTexture(GL_TEXTURE_RECTANGLE_NV,6);
		glTexSubImage2D(GL_TEXTURE_RECTANGLE_NV,0,0,0,
			TRANSITIONS,1,GL_RED,GL_FLOAT,transitions);
		}
	write_places(1);
	/* reload the dummy place for next pass */
	set_token_count(PLACES-1,TRANSITIONS-1);
	/* 
	 * readback places here, instead of the top of the loop,
	 * because they're written during FIRE, and so, on the
	 * first pass, the array versions are correct but the pixel
	 * versions are not (still (0.8,0.7,0.6))
	 */
	glReadPixels(0,2,PLACES-1,1,GL_RED,GL_FLOAT,places);
	}
}

void MyError(CGcontext mycontext)
{
int lastError = cgGetError();
if(lastError){
	printf("%s\n",cgGetErrorString(lastError));
	printf("%s\n", cgGetLastListing(mycontext));
        exit(0);
	}
}

void do_cg()
{
CGcontext	context;
CGprofile	fragment_profile;
int i;

context = cgCreateContext();
if(cgGLIsProfileSupported(CG_PROFILE_FP30)) {
	fragment_profile=CG_PROFILE_FP30;
	fprintf(stderr, "Cg fragment profile fp30 supported.\n");
	}
else {
	fprintf(stderr,"No soup for you!\n");
	exit(1);
	}
for(i=0;i<3;i++){
	fp[i] = cgCreateProgramFromFile(context,CG_SOURCE,"cg_petri_pb2.cg",
		fragment_profile,fpname[i],NULL);
	MyError(context);
	cgGLLoadProgram(fp[i]);
	}
cgGLEnableProfile(fragment_profile);
}

struct timeval stampS, stampE;

void start_timer()
{
gettimeofday(&stampS, NULL);
}

void end_timer()
{
gettimeofday(&stampE, NULL);
printf("seconds: %d\n",stampE.tv_sec - stampS.tv_sec);
}

int vattrib[] = {
GLX_DRAWABLE_TYPE_SGIX,GLX_PBUFFER_BIT_SGIX, 
GLX_RENDER_TYPE_SGIX,GLX_RGBA_BIT_SGIX, 
GLX_RED_SIZE,32,
GLX_BUFFER_SIZE,32,  
GLX_X_RENDERABLE_SGIX,False,
None};

int pbattrib[] = {
GLX_PRESERVED_CONTENTS_SGIX, 
GLX_LARGEST_PBUFFER_SGIX,
None};

int main(int argc, char **argv)
{
Display *display;
int screen;
int count;

GLXFBConfigSGIX *config;
GLXPbuffer glx_pbuffer;
GLXContext pb_ctx;

if((display=XOpenDisplay(NULL))==NULL){
	fprintf(stderr,"can't open\n");
	exit(1);
	}

screen = DefaultScreen(display);
config = (GLXFBConfigSGIX *)glXChooseFBConfigSGIX(display,screen,
		vattrib,&count);
glx_pbuffer = glXCreateGLXPbufferSGIX(display,*config,MAX_TRANSITIONS_PLACES,
		3,pbattrib);
pb_ctx = (GLXContext)glXCreateContextWithConfigSGIX(display,*config,
		GLX_RGBA_TYPE_SGIX,NULL,True); 
glXMakeCurrent(display,glx_pbuffer,pb_ctx);
start_timer();
init_textures(argv[1]);
do_cg();
load_textures_onto_card();
draw();
end_timer();
}