// Cyclic modulo 2 library
// (C)2006 by Faisal Nasim (faisal.nasim@gmail.com)
// CS-37, Batch 2002-2003
// NED University of Engineering and Technology

#include <stdio.h>
#include "cyclic.h"

int G 	[K] = { 1 , 1 , 0 , 1 };

void emptyvector (int v[], int size)
{
	for ( int i = 0 ; i < size ; i++ ) v[i] = 0;
}

int getmax (int a[])
{
	int max = -1;
	for ( int i = 0 ; i < N ; i++ )
		if ( a[i] > 0 ) max = i;
	return max;
}

void binaryvector (int D[], int num)
{
	int x = K-1;
	while ( num > 0 )
	{
		D[x--] = num % 2;
		num /= 2;
	}
	while (x>=0) D[x--] = 0;
}

void printvector ( const char* str, int vec[] , int size )
{
	printf ( "%s: " , str );
	for ( int i = 0 ; i < size ; i++ )
		printf ( "%d" , vec[i] );
}

int multiply ( int a[] , int b[] , int res[] )
{
	for ( int i = 0 ; i < K ; i++ )
		for ( int j = 0 ; j < K ; j++ )
			res [i+j] = ( res [i+j] + ( a[j] * b[i] ) ) % 2;
	return 0;
}

int multiply ( int a[] , int j , int res[] )
{
	for ( int i = 0 ; i < K ; i++ )
		res [i+j] = a[i];
	return 0;
}

int add ( int a[] , int b[] )
{
	for ( int i = 0 ; i < N ; i++ )
		a[i] = ( a[i] + b[i] ) % 2; // module-2 arithmetic
	return 0;
}

// saves the remainder in r[]
int division ( int r[] , int g[] )
{
	const int maxg = MAXG;
	int sub [N] = {0};
	int tmp, i, j, maxr = getmax(r);

	while (maxr >= maxg) // while we have remainder power greater than G[]
	{
		// empty subtraction vector
		emptyvector (sub,N); 
		
		// multiplying and generating subtraction elements
		multiply ( g , maxr - maxg , sub ); 
		
		// modulo two subtraction (same as addition)
		add (r,sub); 
		maxr = getmax(r);
	}
	return 0;
}

void calcdirect (int D[], int RES[])
{
	emptyvector (RES,N);
	multiply(G,D,RES);
}

void calcsystem (int D[], int RES[])
{
	int REM	[N] = {0};
	emptyvector (RES,N);
	multiply (D, N-K, RES); // get the base x^(n-k) * D(x) for final result
	multiply (D, N-K, REM); // get the base x^(n-k) * D(x) for remainder calc
	division ( REM , G );		// perform the repeated division
	add (RES, REM);					// add the remainder to obtain V(x) in RES
}