/*
  AUTHOR: Jordi Saludes <saludes@grec.upc.es>
  DATE:   12/9/1996
  FILE:   knd.c

	kndecode - Decoder of knapsack tests answers.
	
	SYNOPSIS
	
		kndecode [-i] [-apSGI] filename1 [filename2]
		
	DESCRIPTION

	kndecode decodes page totals for knapsack tests. kndecode
        reads first the exam description, then the students identifiers and
        answers and returns grades, decoded answers and other information.
	When filename2 is given, filename1 contains the exam
	description (usually a .ans file) and filename2 contains
	the students data and answers. When only one file name is given,
        filename1 contains first the exam description and then, after a blank
	line, the students data.
        filename2 can be `-', namely the standard input.
	Exam description
	 The exam description is usally written by the TeX run of
         exam file into a .ans file. Lines of such desciption are
           \opts  q p r:   Question number q has p options. Option number r
                           is the right one.
           \pagebot q:     Question q is the last one in current page.
           \Key k d:       k is the key for the test and  d is the
                           detection factor.
	Data lines
         Each line contains identifier, page totals (and possibly version
         number) of a student.
         Fields are separated by spaces. First field must be the
         identifier (long int) of student, next ones are
         the consecutive page totals. However if one of these fields
         f is negative, it is assumed that it represents a new
         version number instead of a page total. Version number is -f 
         from now on.
         
         If no options are given the student identifier is not expected.
		
	OPTIONS
	  
		i      Read incidences. Second field must be an octal
		       number standing for incidences ocurred in the
                       pre-processing of the exam data file.
		a      Return answers of exam, separated by tabs.
		p      Return plain (decoded) page totals,
                       for archiving purposes.
		S      Return the number of right, wrong and null answers.
		G      Return grade. Right answer means +1, null answer
                       means 0, value of wrong answers are adjusted 
		       to have 0 expectation when questions are answered
                       picking answers randomly.
                       Modify routine "qualifica" to change grading.
		I      Output incidences. Input incidences from
                       pre-processing  (when i option is given) are
                       OR-ed with incidences generated by kndecode and
                       returned.
		None   All information returned by the a, p, S or G
                       options is displayed in more human-readable form.
		       No student identifier is expected as first field.

        EXAMPLES

	 kndecode foo.ans -
         -38353  17942344
(Version number) (Page 1 total)

        kndecode -G foo.ans -  (Only grade)
        1001 -38353  17942344  674532
(IDentifier)   (V)     (P1)    (P2)

        kndecode -i -GI foo.ans - (Grade and output incidences)
        1001 2      -38353  17942344  674532
       (ID) (Incid.) (V)      (P1)     (P2)

*/

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define NSDF     1      /* Page total is  not a multiple of df */
#define BVER     2      /* Bad version number: Not inversible */
#define BCNT     4      /* Bad control number. From pre-processing */
#define DUPR     8      /* Duplicated record. From pre-processing */
#define BDEC    16      /* Bad decoding */

#define MQNS 100	/* Max number of questions */
#define MPAGS 10	/* Max number of pages in a test */

#define GRADE 1
#define PLAIN 2
#define STAT  4
#define ANSW  8
#define IIND 16
#define OIND 32

#define NSDF_str "%s: %ld is not a multiple of %hd\n"
#define BVER_str "%s: %ld has no inverse\n"
#define BDEC_str "%s: Bad decoding for %ld\n"
#define BFMT_str "%s: Bad format file\n"
#define UNKO_str "%s: Unknown  option\n"


typedef struct {short int nopt,marca,ref; long int w;} question;

question qn[MQNS];
short int	npag,df,nq;
short int	pb[MPAGS];
/* ref[MQNS],nopt[MQNS],marca[MQNS],pb[MPAGS]; */
long  int	key;
/* w[MQNS]; */

int    	getOptions(int argc, char *argv[], FILE **dataF, short *opts);
int	aplana(long *pla, long a, long s, long modul);
int	inverteix(long *in, long b, long key);
int     deco(long v, long s, question r[],short n,long *pla);
float   qualifica(short *n,short *b, short *m);

int     main(argc, argv)
int     argc;
char    *argv[];
{       FILE    	*dataF;
	int 		errs;
	short int       i,j,incid,opts;
	short int	bons,mals,nuls;
	long int	dni,suma,versio=1L,spla;
	float		nota;
	int		c;
	
	if(getOptions(argc,argv,&dataF,&opts)==0)
	  return(1);
	while(1) {
	  incid=0;
	  bons=mals=nuls=0;
	  nota=0.0;
	 if(opts) {
	    if(fscanf(dataF,"%ld",&dni)==EOF) break;
	    if (opts&IIND && fscanf(dataF,"%ho",&incid)==EOF) break;
	    printf("%ld",dni);
	}
	for(i=0;i<npag;) {
	    if (fscanf(dataF,"%ld",&suma)==EOF) goto sortir;
	    if (suma<0) {
	      inverteix(&versio,-suma,key);
	      continue;
	    }
	    if (suma%df!=0) {
	      fprintf(stderr,NSDF_str,argv[0],suma,df);
	      incid|=NSDF;
	      goto aborta;
	    }
	    i++;
	    if(deco(versio, suma/df,qn+pb[i-1],pb[i]-pb[i-1],&spla)) {
	      fprintf(stderr,BDEC_str,argv[0],suma/df);
	      incid|=BDEC;
	      goto aborta;
	    }
	if(!opts) {
#define LOOP for (j=pb[i-1];j<pb[i];j++)
	  printf("\n\nPg. %d\t",i); LOOP printf("%2d ",j+1);
	  printf("\n\t"); LOOP printf("---");
	  printf("\n\t"); LOOP printf("%2hd ",qn[j].ref);
	  printf("\n\t"); LOOP printf("%2hd ",qn[j].marca);
	  printf("\n\t"); LOOP
	   printf(" %c ", qn[j].marca==0? ' ':(qn[j].marca==qn[j].ref? 'B':'M'));
	}
	    if(opts&PLAIN)
	      printf("\t%ld",spla);
	    if (opts&ANSW)
	      LOOP printf("\t%hd",qn[j].marca);
	  }
 /* Now summaries */
	nota=qualifica(&nuls,&bons,&mals);
	if(!opts) {
	  printf("\n\nRight\tWrong\tNo answ\t\tGrade");
	  printf("\n%d\t%d\t%d\t\t%4.2f\n\n\n",bons,mals,nuls,nota);
	}
  	if (opts&GRADE)
	    printf("\t%4.2f", nota);
	  if(opts&STAT)
	    printf("\t%hd\t%hd\t%hd", bons,mals,nuls);
aborta:	if (opts&OIND) printf("\t%ho",incid);
	  printf("\n");
	}
sortir:
	fclose(dataF);
	return 0;
}


/** Get the multiplicative inverse of b modulo key
 ** Return in in.
 ** Uses algorith Y in Knuth
 **
 **/
int	inverteix(long *in, long b, long key)
{ 	long 	u1=1,u2=0,u3,v1,v2,v3,t1,t2,t3;
	long    u=b,v=key;
	int	k;
	if (b<=0) return 1;
	for (k=0; (u&1)==0 && (v&1)==0; k++) {u/=2; v/=2;}
	u3=u; v1=v; v2=1-u; v3=v;
	if ((u&1)==1) {
		t1=0; t2= -1; t3= -v;
		goto y4;
	} else {
		t1=1; t2=0; t3=u;
	}
y3:	if( (t1&1)==0 && (t2&1)==0) {
		t1/=2; t2/=2; t3/=2;
	} else {
		t1=(t1+v)/2; t2=(t2-u)/2; t3/=2;
	}
y4:	if((t3&1)==0) goto y3;
	if(t3>0) {
		u1=t1; u2=t2; u3=t3;
	} else {
		v1= v-t1; v2= -u-t2; v3= -t3;
	}
	t1=u1-v1; t2=u2-v2; t3=u3-v3;
	if (t1<0) { t1+=v; t2-=u;}
	if (t3!=0) goto y3;
	*in= u1;
	return 0;
}




/** Return grade. Give also the nuwer of
 ** right, wrong and null answers.
 **/
float   qualifica(short *n,short *b,short *m)
{       short int i;
		float nota=0.0;
	(*n)= (*b)= (*m)= 0;
	for(i=0; i<nq; i++) {
		if(qn[i].marca==0)
			(*n)++;
		else
			if(qn[i].marca==qn[i].ref) {
				(*b)++; nota++;
			} else {
				(*m)++; nota-=1.0/(qn[i].nopt-1);
			}
	}
	return (nota*10.0)/nq;
}




/** Given the plain total sp, obtain n answers in res
 **
 **/
int	deco(long int v, long int s, question res[], short n,long *pla)
{       long int    	sp;
	short int       i;

	if(s<0) return(1);
	s= s%key;
	for (sp=0;v;s=(s+s)%key,v>>=1)
	  if(v&1) sp=(sp+s)%key;
	*pla=sp;
	for (i=n-1; i>=0; i--) {
		if ((res[i].marca=sp/res[i].w)>res[i].nopt) return(1);
		sp= sp%res[i].w;
	}
	return(0);
}




/** Get the options in the command line
 **
 **/
int	getOptions(int argc, char *argv[], FILE **dataF, short int *opts)
{       short int	k,i,j,na,cref;
	long  int	m=1;
	int	errs, rcs;
	char opt, rec[50];
	*dataF=NULL;

	if (argc<=1) return(0);
	*opts=0;
	for (k=1;k<argc;k++) {
	  if (argv[k][0]!='-') break; /* File names */
	  switch(argv[k][1]) {
	  case 'i': (*opts)|=IIND;
	    break; /* No incidences */
	  default:
	    for(i=1;(opt=argv[k][i])!=0;i++)
	      switch(opt) {
	      case 'G': /* Give grade */
		(*opts)|=GRADE; break;
	      case 'p': /* Give plain total */
		(*opts)|=PLAIN; break;
	      case 'S': /* statistics */
		(*opts)|=STAT; break;
	      case 'a': /* Give answers */
		(*opts)|=ANSW; break;
	      case 'I': /* Output incidences */
	       (*opts)|=OIND; break;
	      default:
		fprintf(stderr, UNKO_str,argv[0]);
		return(0);
	      }
	  }
	}
	*dataF= fopen(argv[k++],"r");
	if(!(*dataF)) return(0);
	/* Read the file header*/
	nq=0; pb[0]=0; npag=0;
	do {
	 	if(!fgets(rec,50,*dataF)) break;
		rcs=sscanf(rec, "\\Key %ld %hd\n",&key, &df);
       if(sscanf(rec, "\\opts %hd %hd %hd",&i, &na,&cref)) {
	       rcs++;
	       qn[i-1].ref=cref;
	       qn[i-1].nopt=na;
       }
       if(sscanf(rec, "\\pagebot %hd\n",&i)) {
       	rcs++;
       	pb[++npag]=i;
       	nq= nq<i? i: nq;
       }
    } while (rcs>0);
    for(j=0,i=1; i<=npag; i++)
	for(m=1; j<pb[i]; j++) {
		qn[j].w= m;  /* printf("%ld ",m); */
		m*=(qn[j].nopt+1);
	}
	fprintf(stderr,
		"\nReading header\nkey= %ld, df= %hd, nq=%hd\n",key,df,nq);
	if(argc<=k) return(1); /* Use the same file */
	fclose(*dataF);
	if(argv[k][0]=='-')
	  *dataF= stdin;
	else {
	  *dataF= fopen(argv[k],"r");
	  if(!(*dataF)) return(0);
	}
	return(1);
}