//Created by Paul at Existor Ltd as part of a neural networks tutorial 1/9/2015
//See http://www.existor.com/en/news-rnn.html

//To compile and run on Linux or Mac: gcc rnn.c -o rnn.out -lm -lcblas; ./rnn.out
//To compile in Windows using Visual Studio: File > New > Project > CLR Console Application
//Remove the file they create automatically for you
//On right: Source Files > Add > Existing Item > rnn.c
//Then right click on rnn.c > Properties > C/C++ > Common Language RunTime Support > change to No CLR
//In same place click C/C++ > Precompiled Headers > Precompiled Header > change to Not Using

//Libraries needed
#include <stdio.h> //for printf
#include <stdlib.h> //for rand
#include <string.h> //for memcpy
#include <math.h> //for tanh
#include "cblas.h" //include CBLAS library, uncomment this line to use CBLAS which is about 5x faster


////////////////////////////////// Timing code //////////////////////////////////
//The timer on Windows and Linux/Mac
#ifdef _WIN32 //this is defined in VisualStudio
#include <Windows.h> //for FILETIME
#include <time.h> //for GetSystemTimeAsFileTime
long long GetTimeNow() {FILETIME t; GetSystemTimeAsFileTime (&t); return ((long long)t.dwLowDateTime + ((long long)(t.dwHighDateTime) << 32LL)) / 10000;}
#else
#include <sys/time.h> //for gettimeofday
long long GetTimeNow() {struct timeval tv; struct timezone tz; gettimeofday (&tv, &tz); return tv.tv_sec * 1000 + (int) (tv.tv_usec / 1000);}
#endif
//Pass in 0 to reset the timer, 1 for total time elapsed, 2 for time since last time
int GetTime (int type) {
	static long long TIMERSTART=0, TIMERLAST=0;
	long long timerlast;
	if (!TIMERSTART || type==0) TIMERSTART = TIMERLAST = GetTimeNow(); //reset the timer
	timerlast = TIMERLAST; //backup this variable
	TIMERLAST = GetTimeNow(); //set the time now
	return TIMERLAST - (type==2 ? timerlast : TIMERSTART);
}


////////////////////////////////// Print a matrix //////////////////////////////////
//Print a matrix as an Octave/Matlab variable. Also puts an Octave comment with a number to indicate a time step or some other looping variable.
void PrintMatrix (const char *label, int step, float *matrix, int numrows, int numcols) {
	int r, c; //for looping through the vectors and the dimensions
	char varname[21]; sscanf (label, "%20s", varname); //get the first word from the variable
	printf ("%%-----------------------%s %d [%dx%d]-----------------------\n%s = [", label, step, numrows, numcols, varname); //a separator
	for (r=0; r<numrows; r++) { //for each vector
 		if (numrows>1) printf ("%s\n\t", r?";":""); //if this is multi-dimensional
		for (c=0; c<numcols; c++) printf (" %11.8f", matrix[r*numcols+c]); //print a float
	}
	printf ("];\n"); //integers or multi-dimensional
}


////////////////////////////////// Multiply a matrix //////////////////////////////////
//Multipy two vectors or matrices. Pass in the two matrices to multiply, the rows of the first,
//cols of first / rows of second, the columns of second, whether to add to the results (0=reset)
//and then the results. This will use CBLAS if available.
void MatrixMultiply (float *A, float *B, int arows, int acolsbrows, int bcols, int addtoc, float *C) {
	#ifdef CBLAS_H //if the CBLAS library is included
	//The CBLAS matrix multiplication function is complicated with lots of arguments. First it specifies whether
	//the matrices are in row or column major order (most computers use row major order). Then whether the matrices
	//are transposed (CblasNoTrans is a CBLAS constant), followed by the rows of A, columns of B, and inner dimensions
	//(the things which get multiplied, eg cols of A, rows of B). The next number is a constant to multiply each 
	//element of A by, then A itself. I haven't fully understand the next argument but got there by trial and error.
	//Then B, then another one I haven't fully understand. Then something to multiply C by before adding the results
	//of the matrix multiplication (0 for resetting, 1 for just adding). And another misunderstood argument.
	cblas_sgemm (CblasRowMajor, CblasNoTrans, CblasNoTrans, arows, bcols, acolsbrows,
		1, A, acolsbrows, B, bcols, addtoc ? 1 : 0, C, bcols);
	#else //or else multiply normally
	int r, c, d;
	if (!addtoc) memset (C, 0, arows * bcols * sizeof (float)); //initialse C to all zeros
	//This block of code goes down the rows of A and along the columns of B, computing each result
	//in C completely before moving onto the next one. Eg it does row 1 of A and col 1 of B to get result C[1,1].
	/*for (r=0; r<arows; r++) { //for the rth row of A
		for (c=0; c<bcols; c++) { //for the cth column of B
			for (d=0; d<acolsbrows; d++) {
				//printf ("%d:%d: %f * %f = %f\n", r, c, A[r * acolsbrows + d], B[d * bcols + c], C[r * bcols + c]);
				C[r * bcols + c] += A[r * acolsbrows + d] * B[d * bcols + c];	
			}
			printf ("Row %3d of %3d, col %3d of %3d = %10.7f\n", r, arows, c, bcols, C[r * bcols + c]);
		} //cth column of 
	} //for the rth row of A*/
	//This is more efficient when the first matrix is mostly zeros, which happens for the inputs. They are vectors like
	//[1 0 1 0 0 0...] for the letter A. This loops through every element in A, and multiplies it by every element in
	//the corresponding column in B, to slowly build up the result in C. Eg it does A[1,1] * B[1,1] and adds it to C[1,1].
	//Then it does A[1,1] * B[1,2] and adds it to C[1,2]. This allows it to skip a whole set of multiplications if
	//A[r,d] is 0, whereas the loop above can not (the check would have to be in the innermost loop and so actually 
	//takes longer). This makes the whole RNN about 20-25% faster.
	for (r=0; r<arows; r++) { //for every row of A
		for (d=0; d<acolsbrows; d++) { //for every column of A
			if (A[r * acolsbrows + d] == 0) continue;
			for (c=0; c<bcols; c++) { //for every row of B
				//printf ("%d:%d: %f * %f = %f\n", r, c, A[r * acolsbrows + d], B[d * bcols + c], C[r * bcols + c]);
				C[r * bcols + c] += A[r * acolsbrows + d] * B[d * bcols + c];	
			}
		} //cth column of 
	} //for the rth row of A
	#endif
}


////////////////////////////////// Random number functions //////////////////////////////////
//Get a random number from 0 to 1
float GetRandom() {return (float)rand() / (double)RAND_MAX;}
//Get a random number from -1 to +1 with an approximately normal distribution by summing many random numbers.
//The loop will add up eg 10 random numbers from 0 to 1 to get a number from 0 to 10. If this produces 4 
//then it will return (4*2-10)/10 = -2/10 = -0.2.
//https://en.wikipedia.org/wiki/Central_limit_theorem
float GetRandomNormal() {float r=0; int i; for (i=0; i<10; i++) r += GetRandom(); return (r*2-i)/(float)i;}


//Run the RNN, which is a simplified version of the function above.
float RunRNN (int rnnattr, int *inputdata, int numdata, int numinputs, int numhidden, int numgenerate, float *Wxh, float *Whh, float *Why, float *hidden, int *icmap, int debug) {
	////////////////////////////////// Declare variables //////////////////////////////////
	char c; int i, t, x, h, y, p, pos=0, numtimesteps; float sum, tempr=0;
	float *inputs=NULL, *probs=NULL, *outputs=NULL;
	float *outputerror=NULL, *hiddenerror=NULL, *hiddentemp=NULL;
	int numinputswb=numinputs+1, numhiddenwb=numhidden+1, numoutputs=numinputs; //node numbers
	int *outputbuffer=NULL; //pointer to the output buffer
	if (numgenerate < numdata) numgenerate = numdata; //we at least have to generate this many

	////////////////////////////////// Allocate memory //////////////////////////////////
	inputs = (float*) calloc (numinputswb, sizeof (float)); //space for the inputs
	if (!hidden) hidden = (float*) calloc (numhiddenwb, sizeof (float)); //space for hidden activation values, these should be passed in
	hiddentemp = (float*) calloc (numhiddenwb, sizeof (float)); //space for hidden activation values
	probs = (float*) calloc (numoutputs, sizeof (float)); //space for output probabilities
	outputbuffer = (int*) calloc (numgenerate + 10, sizeof (int)); //create space if there isn't already

	////////////////////////////////// Generate text //////////////////////////////////
	//Loop through the inputs and then continue to generate characters
	for (t=0; t<numgenerate; t++) { //for each character to generate
		////////////////////////////////// Fill the inputs //////////////////////////////////
		memset (inputs, 0, numinputswb * sizeof (float)); //set all the inputs to zero
		inputs[0] = 1; //set the first input to 1, this is the bias
		if (t<numdata) inputs[inputdata[t] + 1] = 1; //set one of the other inputs to 1, eg the 3rd one for C, 5th for E
		else if (t>0) inputs[outputbuffer[t-1] + 1] = 1; //use the last output generated as the input this time
		////////////////////////////////// Forward pass //////////////////////////////////
		//Multiply the inputs times the input-to-hidden weights
		MatrixMultiply (inputs, Wxh, 1, numinputswb, numhidden, 0, &hidden[1]); //zh = sum (x * Wxh)
		if (debug>=10) PrintMatrix ("Generating inputs at", t, inputs, 1, numinputswb); //show the inputs
		//Now add in the hidden node activation values from previous time step, stored in hiddentemp
		//Skip this step if rnnattr=0 and then it becomes a feed forward neural network.
		if (rnnattr>0 && t>0) MatrixMultiply (hiddentemp, Whh, 1, numhiddenwb, numhidden, 1, &hidden[1]); //zh += sum (h * Whh)
		//Compute activation values of hidden nodes
		hidden[0] = 1; //this is the hidden bias, always set to 1
		for (h=1; h<numhiddenwb; h++) hidden[h] = tanh (hidden[h]); //h = tanh(zh)
		if (debug>=10) PrintMatrix ("hidden at", t, hidden, 1, numhiddenwb); //show the hidden
		memcpy (hiddentemp, hidden, numhiddenwb * sizeof (float)); //copy hidden values to temporary array for next time
		//Multiply hidden times hidden-to-output weights
		MatrixMultiply (hidden, Why, 1, numhiddenwb, numoutputs, 0, probs); //zy = sum (h * Why)
		//Compute the output probabilities using softmax.
		for (sum=0, y=0; y<numoutputs; y++) {probs[y] = exp (probs[y]); sum += probs[y];}
		if (sum>0) for (y=0; y<numoutputs; y++) probs[y] /= sum; //p = softmax (zy)
		if (debug>=10) PrintMatrix ("probs at", t, probs, 1, numoutputs); //show the outputs
		////////////////////////////////// Generate output //////////////////////////////////
		//Find the most probable output and store in variable i. This will produce repeated patterns but I used
		//it to verify that this code ran the same as the Python code
		//for (tempr=0, i=0, y=0; y<numoutputs; y++) if (probs[y] > tempr) {tempr= probs[y]; i=y;}
		//outputbuffer[t] = y; //save this character
		//Instead use the probabilities as probabilities for choosing each character. Eg if we have 3 characters A, B and C
		//with A=50%, B=30% and C=20%, then we want to choose a character with those chances. So we generate a random number
		//from 0 to 1, eg 0.6 and then use this to pick a number, in this case 0-0.5=>A, 0.5-0.8=>B, 0.8-1=>C and so 0.6
		//would select B.
		for (tempr=GetRandom(), y=0; y<numoutputs && tempr>=0; y++) tempr -= probs[y]; //get output with this probability
		outputbuffer[t] = y-1; //save this character
	}
	if (icmap) {
		for (i=0; i<numdata; i++) printf ("%c", icmap[inputdata[i]]); //output the passed in inputs
		for (i=0; i<numgenerate; i++) printf ("%c", icmap[outputbuffer[i]]); //and the generated characters
	}
	free (inputs); free (probs); free (outputbuffer); free (hiddentemp);
	return tempr; //return the probability of the last character generated
}




////////////////////////////////// RNN functions //////////////////////////////////
//Train the RNN. This accepts the first rnnattr argument which is 0=NN, 1=RNN. Then the input and output data as integers
//which are converted into 1-of-k representations, followed by the number used to indicate the end of a sequence and
//the maximum sequence length. Then the number of hidden nodes and epochs, the learning rate and pointers
//to the three sets of weights. This function can run on either characters numbers or vocabulary indexes.
float TrainRNN (int rnnattr, int *inputdata, int *outputdata, int numdata, int stopchar, int maxtimesteps, 
		int numinputs, int numhidden, int numepochs, float learningrate, float **Wxhp, float **Whhp, float **Whyp, int *icmap, int numgenerate, int debug) {
	////////////////////////////////// Declare variables //////////////////////////////////
	char c; int e, i, t, lastt, x, h, y, p, pos=0, numiterations, numtimesteps;
	float sum, loss=0, smoothloss = -log (1 / (float)numinputs); //smooth loss computed as in Python
	int timeread=0, timeforward=0, timeback=0; //time spent reading data and in forward and back propogation
	float *inputs=NULL, *hidden=NULL, *probs=NULL, *outputs=NULL;
	float *outputerror=NULL, *hiddenerror=NULL, *hiddentemp=NULL;
	float *Wxh=(Wxhp ? *Wxhp : NULL), *Whh=(Whhp ? *Whhp : NULL), *Why=(Whyp ? *Whyp : NULL); //weights can be passed in
	float *dWxh=NULL, *dWhh=NULL, *dWhy=NULL;
	float *mWxh=NULL, *mWhh=NULL, *mWhy=NULL;
	int numinputswb=numinputs+1, numhiddenwb=numhidden+1, numoutputs=numinputs; //node numbers
	int *outputbuffer=NULL; //for the output buffer

	////////////////////////////////// Allocate memory //////////////////////////////////
	//Now we now how many inputs and outputs we can allocate memory
	inputs = (float*) calloc (maxtimesteps * numinputswb, sizeof (float)); //space for the inputs at each time step
	hidden = (float*) calloc (maxtimesteps * numhiddenwb, sizeof (float)); //space for hidden activation values at each time step
	probs = (float*) calloc (maxtimesteps * numoutputs, sizeof (float)); //space for output probabilities at each time step
	outputs = (float*) calloc (maxtimesteps * numoutputs, sizeof (float)); //space for output values at each time step
	outputerror = (float*) calloc (maxtimesteps * numoutputs, sizeof (float)); //space for output error
	hiddenerror = (float*) calloc (maxtimesteps * numhiddenwb, sizeof (float)); //space for hidden error
	hiddentemp = (float*) calloc (maxtimesteps * numhiddenwb, sizeof (float)); //temporary variable
	if (!Wxh) { //if the weights weren't passed in already, then allocate the space and give it small random values from -0.1 to +0.1
		Wxh = (float*) calloc (numinputswb * numhidden, sizeof (float)); //weights between inputs and hidden
		for (i=0; i<numinputswb * numhidden; i++) Wxh[i] = GetRandomNormal() * 0.01; //initial random values in normal distribution
		//To verify this code worked exactly the same as the Python, I temporarily initialised the weights to fixed values while testing
		//and did the same in Python. I did this for all three sets of weights.
		//for (i=1; i<numinputswb; i++) for (h=0; h<numhidden; h++) Wxh[i*numhidden+h] = ((i-1) * 0.113 - h * 0.164) * 0.01; //to compare with Python
		if (debug>=11) PrintMatrix ("Initial Wxh", 0, Wxh, numinputswb, numhidden); //show the input weights
	}
	if (!Whh) { //save for hidden-hidden weights
		Whh = (float*) calloc (numhiddenwb * numhidden, sizeof (float)); //weights between hidden and hidden
		for (i=0; i<numhiddenwb * numhidden; i++) Whh[i] = GetRandomNormal() * 0.01; //initial random values in normal distribution
		if (debug>=11) PrintMatrix ("Initial Whh", 0, Whh, numhiddenwb, numhidden); //show hidden-to-hidden weights
	}
	if (!Why) { //and hidden-output weights
		Why = (float*) calloc (numhiddenwb * numoutputs, sizeof (float)); //weights between hidden and output
		for (i=0; i<numhiddenwb * numoutputs; i++) Why[i] = GetRandomNormal() * 0.01; //initial random values in normal distribution
		if (debug>=11) PrintMatrix ("Initial Why", 0, Why, numhiddenwb, numoutputs); //show hidden-to-output weights
	}
	dWxh = (float*) calloc (numinputswb * numhidden, sizeof (float)); //change to weights between inputs and hidden
	dWhh = (float*) calloc (numhiddenwb * numhidden, sizeof (float)); //change to weights between hidden and hidden
	dWhy = (float*) calloc (numhiddenwb * numoutputs, sizeof (float)); //change to weights between hidden and output
	if (rnnattr >= 3) { //if using Adagrad learning
		mWxh = (float*) calloc (numinputswb * numhidden, sizeof (float)); //memory of gradient
		mWhh = (float*) calloc (numhiddenwb * numhidden, sizeof (float)); //memory of gradient
		mWhy = (float*) calloc (numhiddenwb * numoutputs, sizeof (float)); //memory of gradient
	}

	////////////////////////////////// Iterations over the whole data set //////////////////////////////////
	GetTime (0); //reset the timer
	for (i=0, e=0; e<numepochs; e++) { //iterations over the whole data set
		lastt=-1; i=0; pos=0; //start at the beginning of the file
		while (pos < numdata) { //while we are not finished with the file
			////////////////////////////////// Genreate some text //////////////////////////////////
			//Output the results based on the current hidden nodes and next input char
			if (debug>=1 && numgenerate>0 && i%100 == 0) {
				printf ("Epoch %5d, iteration %5d (%10d inputs) in %8dms, loss: %9.7f, smoothed: %9.7f, smoothed*seq: %11.7f\n",
					e, i, pos, GetTime(1), loss, smoothloss, smoothloss * maxtimesteps);
				if ((debug>=2 && i==0) || debug>=3) {
					printf ("Time spent reading %8dms, forward pass %8dms, back prop %8dms, in total %8dms\n", timeread, timeforward, timeback, GetTime(1));
					printf ("--------------------------\n");
					RunRNN (rnnattr, &inputdata[pos], 1, numinputs, numhidden, numgenerate, Wxh, Whh, Why, &hidden[lastt>0?lastt-1:0], icmap, debug);
					printf ("\n--------------------------\n");
				}
			}
			////////////////////////////////// Fill the inputs and outputs //////////////////////////////////
			memset (inputs, 0, maxtimesteps * numinputswb * sizeof (float)); //set all the inputs to zero
			memset (outputs, 0, maxtimesteps * numoutputs * sizeof (float)); //set all the outputs to zero
			//The input for each time step has numinputs entries. We read a character from the data and convert it into
			//a number between 0 and numinputs-1. Only that input is set to 1. So if the input is A (ASCII value 65), then
			//input number 65%32=1 is set to 1. The inputs for that time step are then 01000000000000000000000000000000.
			//Except not quite as there is a bias node always set to 1 at the start so it's 1010000...
			//Similarly the outputs are based on the next letter. So if the file had AB then the first output is the B
			//converted into 0010000000000000000000000000000. This loops runs at least once (so it will start with
			//the stopchar as the first input) until it reaches the next stopchar or finishes the sequence of runs
			//out of data.
			for (t=0; t<maxtimesteps && (t==0 || inputdata[pos]!=stopchar) && pos<numdata; t++, pos++) {
				inputs[t * numinputswb] = 1; //set the first input to 1, this is the bias
				inputs[t * numinputswb + inputdata[pos] + 1] = 1; //set one of other inputs to 1, eg the 3rd one for C
				outputs[t * numoutputs + outputdata[pos]] = 1; //do the same for the output nodes
				//printf ("At position %6d of %6d, step %6d, input: %3d (%c), Output %3d (%c)\n", pos, numdata, t, 
				//	inputdata[pos], inputdata[pos], outputdata[pos], outputdata[pos]);
			}
			numtimesteps = t; //how many time steps we have this iteration (between 1 and 100)
			if (debug>=6) printf ("Read data for %d of maximum %d time steps\n", numtimesteps, maxtimesteps);
			timeread += GetTime (2); //add to the time spent reading

			////////////////////////////////// Forward pass //////////////////////////////////
			for (loss=0, t=0; t<numtimesteps; t++) { //for each element in the sequence
				if (debug>=10) PrintMatrix ("inputs for time step", t, &inputs[t * numinputswb], 1, numinputswb); //show the input weights
				//The Python code doesn't have an input bias for some reason, so to make this code operate the same, set the
				//input bias weights to zero.
				//memset (Wxh, 0, numhidden * sizeof (float)); //Python code doesn't have an input bias
				//The inputs are a vector with numinputs+1 entries going across [1 x numinputs+1]. The weights are a matrix with
				//numinputs+1 rows and numhidden colums [numinputs+1 x numhidden]. The hidden values are a vector with numhidden+1
				//entries [1 x numhidden+1]. The next line multiplies the inputs x times the input-to-hidden weights Wxh and leaves
				//the result in the hidden nodes. Note that because the inputs are 1-of-k we could just add up the bias and a single
				//column from the weights, but doing the MatrixMultiply is clearer (and in any case the matrix function can efficiently
				//skip the zero inputs).
				MatrixMultiply (&inputs[t * numinputswb], Wxh, 1, numinputswb, numhidden, 0, &hidden[t * numhiddenwb + 1]); //zh = sum (x * Wxh)
				//Now add in the hidden node activation values from previous time step times the hidden-to-hidden weights Whh.
				//Skip this step if rnnattr=0 and then it becomes a feed forward neural network. //zh += sum (h * Whh)
				//When there is no stopchar, we should carry over the hidden node values from the previous learned sequence,
				//which is what the (t>0?(t-1):(lastt-1)) does.
				if (rnnattr>0 && (t>0 || lastt>0)) MatrixMultiply (&hidden[(t>0?(t-1):(lastt-1)) * numhiddenwb], Whh, 1, numhiddenwb, numhidden, 1, &hidden[t * numhiddenwb + 1]);
    				//All of this is equivalent to the Python step: hs[t] = np.tanh(np.dot(Wxh, xs[t]) + np.dot(Whh, hs[t-1]) + bh)
				if (debug>=10) PrintMatrix ("hidden sums in at", t, &hidden[t * numhiddenwb], 1, numhiddenwb); //show the input weights
				//Now we have to run the activation function on the hidden nodes. This starts from 1 because it is not run on the
				//first bias node, which remains a 1.
				hidden[t * numhiddenwb] = 1; //this is the hidden bias, always set to 1
				for (h=1; h<numhiddenwb; h++) hidden[t * numhiddenwb + h] = tanh (hidden[t * numhiddenwb + h]); //h = tanh(zh)
				if (debug>=10) PrintMatrix ("hidden activation values at", t, &hidden[t * numhiddenwb], 1, numhiddenwb);
				//Now we have to compute the weighted sums for the output layer. This is done by multiplying the hidden
				//activation values [1 x numhidden+1] times the hidden-to-output weights Why [numhidden+1 x numoutputs].
    				//This is like the Python step: ys[t] = np.dot(Why, hs[t]) + by
				MatrixMultiply (&hidden[t * numhiddenwb], Why, 1, numhiddenwb, numoutputs, 0, &probs[t * numoutputs]); //zy = sum (h * Why)
				if (debug>=11) PrintMatrix ("Why", t, Why, numhiddenwb, numoutputs); //show the input weights
				if (debug>=10) PrintMatrix ("output activation", t, &probs[t * numoutputs], 1, numoutputs);
				//And now we run softmax over all these outputs to get the probabilties for this time step. We can
				//save this into the outputs. Compute the exponent of each while adding up the sum. Then divide each
				//output by the sum to get the softmax probability.
				for (sum=0, y=0; y<numoutputs; y++) {probs[t * numoutputs + y] = exp (probs[t * numoutputs + y]); sum += probs[t * numoutputs + y];}
				if (sum>0) for (y=0; y<numoutputs; y++) probs[t * numoutputs + y] /= sum; //p = softmax (zy)
				if (debug>=10) PrintMatrix ("expected outputs", t, &outputs[t * numoutputs], 1, numoutputs);
				if (debug>=10) PrintMatrix ("output probabilities", t, &probs[t * numoutputs], 1, numoutputs);
				//Now add up the loss which is the log of the probability for the single correct letter, and the (1 - log)
				//of all the other ones. Note I added in a very small positive value to prevent the probability going
				//to zero as log (0) is -infinite.
				for (y=0; y<numoutputs; y++) loss -= outputs[t * numoutputs + y] * log (probs[t * numoutputs + y] + 1e-10);
				if (debug>=6) printf ("Loss after time step %5d: %12.6f\n", t, loss);
			} //for each time step
			if (numtimesteps>0) loss /= numtimesteps; //divide loss by number of time steps as they may change if there is a stopchar
			smoothloss = smoothloss * 0.999 + loss * 0.001; //smooth out the loss
			timeforward += GetTime (2); //add to the time spent in forward propagation

			////////////////////////////////// Backward pass //////////////////////////////////
			memset (dWxh, 0, numinputswb * numhidden * sizeof (float)); //set changes in weights to all zeros
			memset (dWhh, 0, numhiddenwb * numhidden * sizeof (float));
			memset (dWhy, 0, numhiddenwb * numoutputs * sizeof (float));
			memset (hiddenerror, 0, numhiddenwb * sizeof (float));
			for (t=numtimesteps-1; t>=0; t--) { //now go backward through time
				//The first step in computing the partial derivatives is to compute the error, which is the difference between
				//the expected output y and the computed probabilities. We'll keep this in the variable outputerror.
				//This is the Python lines: dy = np.copy(ps[t]); dy[targets[t]] -= 1
				for (y=0; y<numoutputs; y++) outputerror[t * numoutputs + y] = probs[t * numoutputs + y] - outputs[t * numoutputs + y]; //ey = p - y
				//Now we multiply this error times the activation values of the hidden nodes to get the changes
				//(partial derivatives) of the hidden-to-output weights dWhy which is size [numhidden+1 x numoutputs].
				//If the inputs are vectors, then MatrixMultiply doesn't really care if they are row or column vectors.
				//So the multiplication below will multiply every hidden value by every error value and add it to dWhy.
				//Note that because the first (bias) value of 'hidden' is set to 1, the first row of dWhy will be the
				//same as (p-y). The Python code keeps this separate and adds dby + dy.
				//In Python this is: dWhy += np.dot(dy, hs[t].T); dby += dy
				MatrixMultiply (&hidden[t * numhiddenwb], &outputerror[t * numoutputs], numhiddenwb, 1, numoutputs, 1, dWhy); //dWhy += ey * h'
				if (debug>=10) PrintMatrix ("error values at ", t, &outputerror[t * numoutputs], 1, numoutputs);
				if (debug>=10) PrintMatrix ("hidden values at ", t, &hidden[t * numhiddenwb], 1, numhiddenwb);
				if (debug>=11) PrintMatrix ("dWhy at", t, dWhy, numhiddenwb, numoutputs);
				//Now we back propogate the output error by multiplying by the hidden-to-output weights. The output
				//error is [1 x numoutputs] and the weights are [numhidden+1 x numoutputs] and so need to be 
				//transposed. But we can transpose the output error instead and then transpose the result, as
				//MatrixMultiply makes no difference between row and column vectors. Eg instead of
				//hiddenerror = Why' * outputerror. We'll do: hiddenerror' = Why * outputerror'
				//[numhidden+1 x 1] = [numhidden+1 x numoutputs] * [numoutputs x 1]
				//The 2nd to last argument to MatrixMultiply is 1 here indicating that the result of the multiplication
				//is added to the existing value of hiddenerror. hiddenerror starts as 0 but then stores the
				//backward propagated hidden error (and is the same as the dhnext variable in Python).
    				//In Python: dh = np.dot(Why.T, dy) + dhnext # backprop into h
				MatrixMultiply (Why, &outputerror[t * numoutputs], numhiddenwb, numoutputs, 1, 1, hiddenerror); //eh = Why' * ey
				if (debug>=11) PrintMatrix ("hidden error at", t, hiddenerror, 1, numhiddenwb);
				//Now we need to backprop through the tanh. Since h = tanh(z), and we need to find (1-tanh^2(z)), we can
				//just compute (1-h^2). This is then multiplied by eh and stored as it will be useful later.
				//So now the hiddenerror variable will equal eh * (1-h^2)
    				//This is like the Python: dhraw = (1 - hs[t] * hs[t]) * dh # backprop through tanh nonlinearity
				for (h=1; h<numhiddenwb; h++) hiddenerror[h] *= 1 - hidden[t * numhiddenwb + h] * hidden[t * numhiddenwb + h];
				//And now we compute the changes to the input-to-hidden weights which is: dWxh += eh * (1-h^2) * x.
				//We already have eh * (1-h^2) in the hiddenerror vector [1 x numhidden]. We mutiply this by the
				//inputs [1 x numinputs+1] to get a [numinputs+1 x numhidden] matrix of changes to Wxh.
				//Note that we ignore the bias term here in the hiddenerror as the bias is always 1.
				//Since all but 2 inputs are 0 (the bias and the letter in question) the matrix dWxh will 
				//only fill up slowly with changes.
    				//This is like the Python: dWxh += np.dot(dhraw, xs[t].T)
				MatrixMultiply (&inputs[t * numinputswb], &hiddenerror[1], numinputswb, 1, numhidden, 1, dWxh); //dWxh += eh * (1-h^2) * x
				if (debug>=11) PrintMatrix ("dWxh at", t, dWxh, numinputswb, numhidden);
				//Then we do the same for the hidden-to-hidden weights. We multiply the hidden activation values from the
				//previous tim step [1 x numhidden+1] times the eh * (1-h^2) [1 x numhidden] to get a 
				//[numhidden+1 x numhidden] size result.
    				//This is like the Python: dWhh += np.dot(dhraw, hs[t-1].T)
				if (t>0) MatrixMultiply (&hidden[(t-1) * numhiddenwb], &hiddenerror[1], numhiddenwb, 1, numhidden, 1, dWhh); //dWhh += eh * (1-h^2) * h[t-1]
				//I thought the next line was needed to be like the Python but a numerical gradient check showed me it wasn't, maybe issue in Python code?
				//else for (h=0; h<numhidden; h++) dWhh[h] += hiddenerror[h+1]; //just add the bias the last time round as hidden[-1] is all zeros
				//Finally we back propagate the eh * (1-h^2) through the hidden weights to be used next time
				//The eh * (1-h^2) is [1 x numhidden] and the weights are [numhidden+1 x numhidden]. The result
				//is [numhidden+1 x numhidden] * [numhidden x 1] = [numhidden+1] x 1. I save it in a temporary
				//variable and then copy back into hiddenerror as I don't think the CBLAS library guarantees
				//working if the input and output point to the same place.
    				//In Python: dhnext = np.dot(Whh.T, dhraw)
				//This step is skipped when rnnattr=0 which is a normal feed foward neural network.
				if (rnnattr>0) MatrixMultiply (Whh, &hiddenerror[1], numhiddenwb, numhidden, 1, 0, hiddentemp); //eh[t-1] = Whh' * eh * (1 - h^2)
				memcpy (hiddenerror, hiddentemp, numhiddenwb * sizeof (float));
				if (debug>=11) PrintMatrix ("back propagated hidden error at", t, hiddenerror, 1, numhiddenwb);
			}
			if (debug>=11) PrintMatrix ("dWhh after back prop", 0, dWhh, numhiddenwb, numhidden);
			//Clip the changes to the weights to prevent exploding gradients
			if (rnnattr >= 2) {
				for (x=0; x<numinputswb * numhidden;  x++) if (dWxh[x]<-1) dWxh[x]=-1; else if (dWxh[x]>1) dWxh[x]=1;
				for (h=0; h<numhiddenwb * numhidden;  h++) if (dWhh[h]<-1) dWhh[h]=-1; else if (dWhh[h]>1) dWhh[h]=1;
				for (y=0; y<numhiddenwb * numoutputs; y++) if (dWhy[y]<-1) dWhy[y]=-1; else if (dWhy[y]>1) dWhy[y]=1;
				if (debug>=11) PrintMatrix ("dWhh after clipping", 0, dWhh, numhiddenwb, numhidden);
			}
			//Use Adagrad learning where the rate changes depending on how fast each weight changes
			if (rnnattr >= 3) { 
				for (x=0; x<numinputswb * numhidden;  x++) {mWxh[x] += dWxh[x] * dWxh[x]; Wxh[x] -= learningrate * dWxh[x] / sqrt (mWxh[x] + 1e-8);}
				for (h=0; h<numhiddenwb * numhidden;  h++) {mWhh[h] += dWhh[h] * dWhh[h]; Whh[h] -= learningrate * dWhh[h] / sqrt (mWhh[h] + 1e-8);}
				for (y=0; y<numhiddenwb * numoutputs; y++) {mWhy[y] += dWhy[y] * dWhy[y]; Why[y] -= learningrate * dWhy[y] / sqrt (mWhy[y] + 1e-8);}
				if (debug>=11) PrintMatrix ("dWhh after Adagrad", 0, dWhh, numhiddenwb, numhidden);
			} else {
				for (x=0; x<numinputswb * numhidden;  x++) Wxh[x] -= learningrate * dWxh[x];
				for (h=0; h<numhiddenwb * numhidden;  h++) Whh[h] -= learningrate * dWhh[h];
				for (y=0; y<numhiddenwb * numoutputs; y++) Why[y] -= learningrate * dWhy[y];
				if (debug>=11) PrintMatrix ("dWhh after learning", 0, dWhh, numhiddenwb, numhidden);
			}
			timeback += GetTime (2); //add to the time spent in  back propagation
			i++; //we have done another iteration
			if (!stopchar || numtimesteps==maxtimesteps) lastt = numtimesteps; //carry over the hidden state
		}
	}

	////////////////////////////////// Free memory //////////////////////////////////
	if (Wxhp) *Wxhp = Wxh; else if (Wxh) free (Wxh); //send the weights back
	if (Whhp) *Whhp = Whh; else if (Whh) free (Whh);
	if (Whyp) *Whyp = Why; else if (Why) free (Why);
	if (inputs) free (inputs); //free all the othe rmemory used
	if (hidden) free (hidden);
	if (probs) free (probs);
	if (outputs) free (outputs);
	if (outputerror) free (outputerror);
	if (hiddenerror) free (hiddenerror);
	if (hiddentemp) free (hiddentemp);
	if (dWxh) free (dWxh);
	if (dWhh) free (dWhh);
	if (dWhy) free (dWhy);
	if (mWxh) free (mWxh);
	if (mWhh) free (mWhh);
	if (mWhy) free (mWhy);
	return smoothloss; //return the last computed loss
}
	





////////////////////////////////// Main function //////////////////////////////////
int main (int argc, char **argv) {
	////////////////////////////////// Variables //////////////////////////////////
	int stopchar=10, maxsequence=100, numepochs=10, numhidden=10, numgenerate=100, rnnattr=2, debug=0;
	int numinputs = 0; //this will store the number of inputs
	float learningrate = 0.01; //learning rate
	float *Wxh=NULL, *Whh=NULL, *Why=NULL, loss, mostprob; //for the weights
	FILE *infp=NULL; //input file pointer and log file (or else use stdout)
	int i, j, outeri; //looping variables
	char ch, teststring[100]=""; int testints[100]; //the test string as characters and integers
	int *outputbuffer=NULL; //for the output buffer
	int numdata, *inputdata; //declare all variables first so it compiles in Visual Studio in C mode
	int charstoinputs[256]; memset (charstoinputs, 0, sizeof (charstoinputs)); //maps characters like A to an input number like 1
	int inputstochars[256]; memset (inputstochars, 0, sizeof (inputstochars)); //maps input number 1 to character A

	////////////////////////////////// Usage //////////////////////////////////
	if (argc < 3) {
		printf ("Usage: %s\n", argv[0]);
		printf ("  --input input-file.txt: text file to train with (required)\n");
		printf ("  --stop ##: the ASCII value or actual character used to end sequences, 0=disabled, 10=newline (defaults to %d)\n", stopchar);
		printf ("  --maxsequence ##: the maximum length of a sequence if no stop char found (default %d)\n", maxsequence);
		printf ("  --epochs ##: number of epochs over the whole input file (default %d)\n", numepochs);
		printf ("  --hidden ##: number of hidden nodes (default %d)\n", numhidden);
		printf ("  --learningrate 0.##: constant learing rate (default %f)\n", learningrate);
		printf ("  --generate ##: num characters to generate after training (default %d)\n", numgenerate);
		printf ("  --attributes #: 0=feed forward network, 1=RNN, 2=with clipping, 3=with Adagrad (default %d)\n", rnnattr);
		printf ("  --debug #: debug level, 0=results only, 1=timing and loss, 2=generate after epochs, 3=generate while training, 10=inputs/outputs, 11=weights (default %d)\n", debug);
		printf ("\n");
		return 0;
	}

	////////////////////////////////// Loop through arguments //////////////////////////////////
	for (i=1; i<argc-1; i++) { //from 1st argument to 2nd to last one
		     if (!strcmp (argv[i], "--input")) infp = fopen (argv[i+1], "r"); //open the input ile
		else if (!strcmp (argv[i], "--stop")) stopchar = atoi (argv[i+1]); //stop character, 0 to disable
		else if (!strcmp (argv[i], "--maxsequence")) maxsequence = atoi (argv[i+1]); 
		else if (!strcmp (argv[i], "--epochs")) numepochs = atoi (argv[i+1]);
		else if (!strcmp (argv[i], "--hidden")) numhidden = atoi (argv[i+1]);
		else if (!strcmp (argv[i], "--learningrate")) learningrate = atof (argv[i+1]);
		else if (!strcmp (argv[i], "--generate")) numgenerate = atoi (argv[i+1]);
		else if (!strcmp (argv[i], "--attributes")) rnnattr = atoi (argv[i+1]);
		else if (!strcmp (argv[i], "--debug")) debug = atoi (argv[i+1]);
	}
	if (!infp) {printf ("Input file is required\n"); return -1;}

	////////////////////////////////// Read the input file //////////////////////////////////
	//This section of code reads an input file into a memory buffer called 'data'
	fseek (infp, 0L, SEEK_END); //go to the end of the ifle
	numdata = ftell (infp); //get the file size
	fseek (infp, 0L, SEEK_SET); //go back to the beginning of the file
	inputdata = (int*) calloc (numdata + 10, sizeof (int)); //create space for the data as integers
	numdata = 0; //reset to zero as we'll now count actual characters
	//First read the input file and create to arrays charstoinputs and inputstochars. Our only RNN only needs as many inputs as
	//there are characters. For example if we only ever process the letters P, Q, R, then our network only needs 3 inputs. The next
	//code reads the file into the inputdata array and uses charstoinputs to remember all the letters it has seen
	//(eg ...N=0, O=0, P=1, Q=1, R=1, S=0...). Then it maps those letters to numbers in the inputstochars array
	//(eg P=0, Q=1, R=2) and maps the opposite direction in charstoinputs array (0=P, 1=Q, 2=R). Then it converts
	//all the inputdata to use the mapping. These are like the char_to_ix and ix_to_char in Python.
	//Don't use just feof http://stackoverflow.com/questions/5431941/why-is-while-feof-file-always-wrong
	while (!feof (infp) && (ch = fgetc (infp)) >= 0) {inputdata[numdata++] = (int)ch; charstoinputs[(int)ch]=1;} //record that we found this character
	fclose (infp); //close the file
	for (numinputs=0, i=0; i<256; i++) if (charstoinputs[i]) {charstoinputs[i] = numinputs; inputstochars[numinputs++] = i;}
	if (stopchar>0 && inputdata[numdata-1] != stopchar) inputdata[numdata++] = stopchar; //always end on a stopchar if provided
	for (i=0; i<numdata; i++) inputdata[i] = charstoinputs[inputdata[i]]; //convert all the data into input numbers
	stopchar = stopchar>0 ? charstoinputs[stopchar] : -1; //convert the stop char into the vocabulary
	printf ("Read %d bytes, hidden: %d, epochs: %d, learning rate: %0.5f\n", numdata, numhidden, numepochs, learningrate); fflush (stdout);

	////////////////////////////////// Run the RNN //////////////////////////////////
	loss = TrainRNN (rnnattr, inputdata, &inputdata[1], numdata-1, stopchar, maxsequence, numinputs, numhidden, numepochs, learningrate,
		&Wxh, &Whh, &Why, inputstochars, numgenerate, debug);
	if (numgenerate>0) {
		printf ("After %d epochs in %dms, loss was %0.5f, generated text:\n", numepochs, GetTime (1), loss);
		RunRNN (rnnattr, inputdata, 1, numinputs, numhidden, numgenerate, Wxh, Whh, Why, NULL, inputstochars, debug);
		printf ("\n\n");
	}

	////////////////////////////////// Finish up //////////////////////////////////
	if (Wxh) free (Wxh); if (Whh) free (Whh); if (Why) free (Why);
	if (outputbuffer) free (outputbuffer);
	return 0;
}



