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

enum {
    BYTES_PER_SAMPLE = 2
};

enum {
    MAX_SAMPLE = (~(~0 << (8*BYTES_PER_SAMPLE-1)))
};

typedef struct {
    unsigned int width;
    unsigned int height;
    unsigned char* data;
} Image;

typedef struct Beat Beat;

struct Beat {
    double volume;
    unsigned int end;
    Image* img;
    Beat* prev;
    Beat* next;
};

static int
readPGM( Image* pgm, FILE* fp )
{
    int headerNumbersRead = 0;
    int inNumber = 0;
    int number = 0;
    int inHeader = 1;
    int ch;

    if ( fp == 0 ) {
	return __LINE__;
    }

    if ( ( ch = fgetc( fp ) ) != 'P' || ( ch = fgetc( fp ) ) != '5' ) {
	fprintf( stderr, "Not a valid raw pgm file\n" );
	return __LINE__;
    }

    while ( inHeader && ( ch = fgetc( fp ) ) != EOF ) {
	if ( isdigit( ch ) ) {
	    if ( !inNumber ) {
		number = 0;
		inNumber = 1;
	    }

	    number *= 10;
	    number += ( ch - '0' );
	} else {
	    if ( inNumber ) {
		switch ( ++headerNumbersRead ) {
		case 1:
		    pgm->width = number;
		    break;
		case 2:
		    pgm->height = number;
		    break;
		case 3:
		    inHeader = 0;
		    break;
		}
		inNumber = 0;
	    }

	    if ( ch == '#' ) {
		while ( ( ch = fgetc( fp ) ) != EOF && ch != '\n' ) {
		    /* do nothing */;
		}
	    } else if ( !isspace( ch ) ) {
		fprintf( stderr, "Illegal header character <%c>\n", ch );
	    }
	}
    }

    if ( ch != '\n' ) {
	while ( ( ch = fgetc( fp ) ) != EOF && ch != '\n' ) {
	    /* do nothing */;
	}
    }

    if ( pgm->width == 0 || pgm->height == 0 ) {
	fprintf( stderr, "Invalid width or height\n" );
	fclose( fp );
	return __LINE__;
    }

    pgm->data = (unsigned char*)malloc( pgm->width * pgm->height );
    if ( pgm->data == 0 ) {
	fprintf( stderr, "Out of memory\n" );
	fclose( fp );
	return __LINE__;
    }

    fread( pgm->data, 1, pgm->width * pgm->height, fp );

    return 0;
}

static int
readWidth( unsigned int* width, FILE* fp )
{
    int headerNumbersRead = 0;
    int inNumber = 0;
    int number = 0;
    int inHeader = 1;
    int ch;

    if ( fp == 0 ) {
	return __LINE__;
    }

    while ( inHeader && ( ch = fgetc( fp ) ) != EOF ) {
	if ( isdigit( ch ) ) {
	    if ( !inNumber ) {
		number = 0;
		inNumber = 1;
	    }

	    number *= 10;
	    number += ( ch - '0' );
	} else {
	    if ( inNumber ) {
		switch ( ++headerNumbersRead ) {
		case 1:
		    *width = number;
		    inHeader = 0;
		    break;
		}
		inNumber = 0;
	    }

	    if ( ch == '#' ) {
		while ( ( ch = fgetc( fp ) ) != EOF && ch != '\n' ) {
		    /* do nothing */;
		}
	    } else if ( !isspace( ch ) ) {
		fprintf( stderr, "Illegal header character <%c>\n", ch );
	    }
	}
    }

    if ( ch != '\n' ) {
	while ( ( ch = fgetc( fp ) ) != EOF && ch != '\n' ) {
	    /* do nothing */;
	}
    }

    if ( *width == 0 ) {
	fprintf( stderr, "Invalid width\n" );
	fclose( fp );
	return __LINE__;
    }

    return 0;
}

static unsigned int
addBeat( Beat** beats, double volume, unsigned int line, Image* img )
{
    Beat* nn = (Beat*)malloc( sizeof(Beat) );

    if ( nn == 0 ) {
	return __LINE__;
    }

    nn->volume = volume;
    nn->end = line + img->height;
    nn->img = img;

    nn->prev = 0;
    nn->next = *beats;

    if ( nn->next ) {
	nn->next->prev = nn;
    }

    *beats = nn;

    return 0;
}

static void
removeBeat( Beat** list, Beat* cur )
{
    if ( cur == *list ) {
	*list = cur->next;
    }

    if ( cur->prev ) {
	cur->prev->next = cur->next;
    }

    if ( cur->next ) {
	cur->next->prev = cur->prev;
    }

    free( cur );
}

int
main( int argc, const char* argv[] )
{
    unsigned int help = 0;
    const char* fileName = 0;
    unsigned int streamWidth = 0;
    unsigned int linesPerBeat = 128;
    double thresh = 0.01;
    double gain = 1.0;
    unsigned char* inBuf;
    double* outBuf;
    Beat* beats = 0;
    FILE* fp;
    unsigned int ii;
    Image pgm;

    for ( ii=1; ii < argc; ++ii ) {
	if ( !strcmp( argv[ ii ], "-file" ) ) {
	    fileName = argv[ ++ii ];
	} else if ( !strcmp( argv[ ii ], "-lpb" ) ) {
	    linesPerBeat = strtol( argv[ ++ii ], 0, 0 );
	} else if ( !strcmp( argv[ ii ], "-thresh" ) ) {
	    thresh = strtod( argv[ ++ii ], 0 );
	} else if ( !strcmp( argv[ ii ], "-gain" ) ) {
	    gain = strtod( argv[ ++ii ], 0 );
	} else {
	    help = 1;
	}
    }

    if ( fileName == 0 || ( fp = fopen( fileName, "rb" ) ) == 0 ) {
	fprintf( stderr, "Needs filename\n" );
	help = 1;
    }

    if ( linesPerBeat < 1 ) {
	fprintf( stderr, "Bad parameters\n" );
	help = 1;
    }

    if ( help ) {
	fprintf( stderr, "Usage: %s\n", argv[0] );
	fprintf( stderr, "\t-file fileName\n" );
	fprintf( stderr, "\t[-lpb linesPerBeat]\n" );
	fprintf( stderr, "\t[-thresh threshold]\n" );
	fprintf( stderr, "\t[-gain gain]\n" );
	fprintf( stderr, "\t[-help]\n" );
	return __LINE__;
    }

    if ( readPGM( &pgm, fp ) != 0 ) {
	fprintf( stderr, "Couldn't read pgm: %s\n", fileName );
	fclose( fp );
	return __LINE__;
    }

    fclose( fp );

    if ( readWidth( &streamWidth, stdin ) != 0 ) {
	fprintf( stderr, "Couldn't get width of input stream\n" );
	free( pgm.data );
	return __LINE__;
    }

    outBuf = (double*)malloc( pgm.width * sizeof( double ) );
    if ( outBuf == 0 ) {
	fprintf( stderr, "Unable to allocate <%d> doubles\n", pgm.width );
	return __LINE__;
    }

    inBuf = (unsigned char*)malloc( streamWidth );
    if ( inBuf == 0 ) {
	fprintf( stderr, "Unable to allocate <%d> bytes\n", streamWidth );
	free( outBuf );
	free( pgm.data );
	return __LINE__;
    }

    gain /= (double)pgm.width;

    fprintf( stdout, "%d # %s\n", pgm.width, argv[0] );

    for ( ii=0; !feof( stdin ) || beats != 0; ++ii ) {
	unsigned int jj;
	Beat* ptr;

	if ( fread( inBuf, 1, streamWidth, stdin ) == streamWidth ) {
	    double avg = 0.0;

	    for ( jj=0; jj < streamWidth; ++jj ) {
		avg += (double) inBuf[ jj ] / (double)( 255 * streamWidth );
	    }

	    if ( avg >= thresh ) {
		unsigned char maxValue = inBuf[ 0 ];
		unsigned int maxIndex = 0;
		unsigned int rate;

		for ( jj=1; jj < streamWidth; ++jj ) {
		    if ( inBuf[ jj ] > maxValue ) {
			maxValue = inBuf[ jj ];
			maxIndex = jj;
		    }
		}

		rate = ( 1U << maxIndex );

		if ( ( ( rate * ii ) % linesPerBeat ) == 0 ) {
		    addBeat( &beats, avg / 255.0, ii, &pgm );
		}
	    }
	}

	for ( jj=0; jj < pgm.width; ++jj ) {
	    outBuf[ jj ] = 0.0;
	}

	ptr = beats;

	while ( ptr != 0 ) {
	    Beat* cur = ptr;
	    unsigned int line;
	    unsigned char* pix;

	    ptr = ptr->next;

	    if ( ii >= cur->end ) {
		removeBeat( &beats, cur );
		continue;
	    }

	    line = ( ( ii + cur->end ) % cur->img->height );
	    pix = &cur->img->data[ line * cur->img->width ];

	    for ( jj=0; jj < pgm.width; ++jj ) {
		outBuf[ jj ] += cur->volume * (double)*pix++;
	    }
	}

	for ( jj=0; jj < pgm.width; ++jj ) {
	    int val = (int)( 255 * gain * outBuf[ jj ] );

	    if ( val < 0 ) {
		val = 0;
	    } else if ( val > 255 ) {
		val = 255;
	    }

	    fputc( ( val >> 0 ) & 0xFF, stdout );
	}
    }

    free( inBuf );
    free( outBuf );
    free( pgm.data );

    return 0;
}