// Barker codes (c) 2000
// Larry Deering, PO Box 275, Bellport NY 11713-0275
// http://www.qsl.net/w2gl/
// w2gl@qsl.net

/*	This program builds from MS Visual C++ 4.1 
 *	My first Barker code program was for either an original IBM PC 
 *	or a 286 clone, in assembly language, around 1986. Recently, I 
 *	found one on the web by:

// Barker code search routine
//
// Written by Clay S. Turner (in Atlanta 770-641-8293)
//
//            Main Office
//            Wireless Systems Engineering, Inc.
//            Satellite Beach, Florida.
//            (321) 777-7881

 *	Clay emailed his version of his Barker code program, remnants of 
 *	which will always remain in mine.
 *
 *	I've always been interested in Barker codes and have a current
 *	need, but couldn't find my old work. So, I contacted Clay,
 *	and used his work as a framework for a new program. With some
 *	work, it runs a lot faster. (I am a bit-pusher by nature!)
 *	This program finds codes with the lowest peak error
 *	for bit lengths from 3-32 bits. It's faster than most programs
 *	for three reasons. It looks up 16 bits at a time in the 
 *	autocorrelation routine. The test routine terminates when a greater 
 *	than lowest lobe is detected. A third speedup is only checking
 *	one of the four related codes. These four are the code, the one's
 *	complement of the code, the bit reversed code, and the one's 
 *	complement of the reversed code. The lowest binary value of the
 *	four is the only one tested. Thus, the number of codes found is 
 *	less by a factor of four than an exhaustive check. Not to worry,
 *	the missing codes are generated for the file created.

 *	One final note: Classic Barker codes have an output stream of 
 *	0, +1, -1, and N when all bits compare. This program reports the 
 *	absolute value of the the max error, and reports the best codes found.
 *	If the error is greater than 1, the code isn't a true Barker code,
 *	though most engineers won't make that distinction.
*/
													
#include <stdio.h>
#include <time.h>
#include <conio.h>
#define max_file_codes (1800)
FILE *fptr;
unsigned int code_mask[33];		//code bit mask
unsigned short int ones_cnt[65536];	//word to 1's count lookup table
unsigned short int reverse[65536];	//used to reverse bits

//	Prototypes:
int test(unsigned long int tcode, int code_length, int best);
void init(void);
int main(void);
void file_work(unsigned long code, int length);

main()
{
struct two_x {
unsigned short int lo;
unsigned short int hi;	};
union rev_work	{
	unsigned long int rev;
	struct two_x rcode;	} xcode, rcode;
double elapsed_f;
time_t start, stop;
int count, elapsed, i, length, test_lobe, low_lobe;
unsigned int codes[max_file_codes];
unsigned int last_code, code;
const int maxcodes=8;  // The maximum number of displayed Barker codes per bit length

if ((fptr=fopen("barkcode.txt", "w"))==NULL)	//make sure file can be opened
		{   printf("\nERROR creating BARKCODE.TXT\n");
            return(0); }
else {			//print a header
	fprintf(fptr, "\tBarker Code Search Program\n\t(c) 2000\n");
	fprintf(fptr, "\tLarry Deering\n\tPO Box 275\n\tBellport NY 11713-0275\n");
	fprintf(fptr, "\n\thttp://www.qsl.net/w2gl\n\tw2gl@qsl.net\n");
	fclose(fptr);	}
init();									//setup lookup tables
for (length=3; length<33; length++) {
	time(&start);	
	last_code=1+(code_mask[length]>>1);	//search only lower half of codes
	low_lobe=5;				//a value > lowest expected
	for (code=0; code<last_code; code++)	{
		xcode.rev=code;					//now work on testing only the lowest reverse code
		rcode.rcode.lo=reverse[xcode.rcode.hi];	//reverse hi and low code ints
 		rcode.rcode.hi=reverse[xcode.rcode.lo];	//reverse lo and hi code ints
		rcode.rev=(rcode.rev>>(32-length));		//shift right so code and reversed code align
		rcode.rev&=code_mask[length];			//mask off extra high bits
		if ((code<rcode.rev) && (code<(~rcode.rev & code_mask[length])))	{
			//above statement finds if code is < reversed code and it's complement
			//and tests code if it is
			test_lobe=test(code, length, low_lobe);
			if (test_lobe<low_lobe) {			//starts saving anew
				count=0;
				codes[count++]=code;
				low_lobe=test_lobe;
				}
			else if (test_lobe==low_lobe) {		//saves code if equal to best
			if (count<max_file_codes)
				codes[count++]=code;
			else
				count++;						//or counts if array is full
		}	}	}
	time(&stop);
	elapsed_f=difftime(stop, start);
	elapsed=(unsigned long)elapsed_f;
	if (!(fptr=fopen("barkcode.txt","a+")))
		printf("/nERROR opening BARKCODE.TXT/n");
	else	fprintf(fptr, "\n%2d bit codes \terror floor =%2d \t%5ld codes found in %ld seconds\n",length,low_lobe,count, elapsed);
	if (elapsed<=1)	{
		printf("%2d bit codes \terror floor =%2d \t%5ld codes found\n",length,low_lobe,count);
		}
	else	{
		printf("%2d bit codes \terror floor =%2d \t%5ld codes found in %ld seconds\n",length,low_lobe,count, elapsed);
		}
	for (i=0;i<count && i<maxcodes;i++)	 {
		printf("%X ",codes[i]);
		}
	printf("\n\n");
	for (i=0; i<count; i++)	{
		file_work(codes[i], length);
		}
	fclose(fptr);
	}
printf("Press any key to exit\n");
getch();
return(0);
}

void file_work(unsigned long locode, int length)	{		//converts locode to ones complement, and reverse codes
int total_1, total_0;	//see note below about ones/zero count
unsigned long int comp_code;
struct outx {
unsigned short int lo;
unsigned short int hi;	};
union rev_out	{
	unsigned long int rever;
	struct outx rcode;	} wcode, rvcode;
comp_code=~locode&code_mask[length];			//complement of code
wcode.rever=locode;			//work code=code
rvcode.rcode.lo=reverse[wcode.rcode.hi];	//reverse hi and low code ints
rvcode.rcode.hi=reverse[wcode.rcode.lo];	//reverse lo and hi code ints
rvcode.rever=(rvcode.rever>>(32-length));	//shift right so code and reversed code align
rvcode.rever&=code_mask[length];			//mask off extra high bits
wcode.rever=((~rvcode.rever)&code_mask[length]);
if (rvcode.rever<wcode.rever)
	fprintf(fptr,"%X\t%X\t%X\t%X", comp_code, locode,  wcode.rever, rvcode.rever);
else
	fprintf(fptr,"%X\t%X\t%X\t%X", comp_code, locode,  rvcode.rever, wcode.rever);
// This is an add-on to count ones/zeros in the code. 
//	/*
wcode.rever=comp_code;
total_1=ones_cnt[wcode.rcode.lo]+ones_cnt[wcode.rcode.hi];
wcode.rever=((~comp_code)&code_mask[length]);
total_0=ones_cnt[wcode.rcode.lo]+ones_cnt[wcode.rcode.hi];
fprintf(fptr,"\t%d/%d  ones/zeros\n", total_1, total_0);
//	*/
//fprintf(fptr,"\n");	//If you decide never to use the ones/zeros, add 
					//the \n to the previous two fprintf statements 
					//and delete this line.
}

void init()
{
long i;
int j, k, cnt;
for (i=0; i<65536; i++)	{	//this will count 1's of each word
	cnt=0;					//start each count at zero
	k=i;					//k is word to be converted
	for (j=0; j<16; j++){	//bit counter
		cnt+=(k&1);
		k=(k>>1);
		}
	ones_cnt[i]=cnt;		//ones_cnt now has 1's count of i
	}
i=0;
for (j=1; j<33; j++){			
	i=(i<<1);
	i++;
	code_mask[j]=i;			//code mask will cover unwanted bits
	}
for (i=0; i<65536; i++)	{	//This is for a lookup table
	cnt=0;					//that yields a word with bits 
	k=i;					//reversed from the index
	for (j=0; j<15; j++){	//so, reverse[number] yields number in reverse bit order
		cnt|=(k&1);
		cnt=(cnt<<1);
		k=(k>>1);
		}
	reverse[i]=cnt;		//reverses bit order
}	}

int test(unsigned long int tcode, int code_length, int best)
{
struct two_int	{
unsigned short int lo;
unsigned short int hi;
				};
union union_work	{		//We need to put in a 32 bit code, and beat on
	unsigned long int raw;	//16 bits at a time
	struct two_int results;
					} work;
// unsigned long int int_mask=code_mask[16];
unsigned long int shift_code=tcode;
int peak_error=0;				//lobe errors (cleared to start)
int i;
int lobe=0;
for (i=code_length; i>0; i--) {
	shift_code=shift_code>>1;					//shift right, then xor and mask in next op
	work.raw=((shift_code^tcode)&code_mask[i-1]);//mask off unwanted bits
	lobe=ones_cnt[work.results.hi];				//count ones in the hi int
	lobe+=ones_cnt[work.results.lo];			//and in the lo int
	work.raw=(~work.raw&code_mask[i-1]);		//count zeros by inverting the code w/mask
	lobe-= ones_cnt[work.results.hi];			//and counting ones in hi and lo
	lobe-= ones_cnt[work.results.lo];
	if (lobe<0)
		lobe=-lobe;								//need the absolute value
	if (lobe>best)
		return(lobe);							//bomb out if lobe is high
	if (lobe>peak_error)						//this is a peak detector
		peak_error=lobe;
	}
return(peak_error);								//returns peak after 
}

/* ********* BONEYARD FOR OLD CODE *************

*/