/****************************************************************************
 * CODEC for the Real-time BBC Codec/Modem                                  *
 ****************************************************************************
 * William L. Bahn                                                          *
 * Academy Center for Information Security                                  *
 * Department of Computer Science                                           *
 * United States Air Force Academy                                          *
 * USAFA, CO 80840                                                          *
 ****************************************************************************
 * FILE:............ codec.c                                                *
 * DATE CREATED:.... 06 SEP 07                                              *
 * DATE MODIFIED:... 06 SEP 07                                              *
 ****************************************************************************
 *
 * REVISION HISTORY
 *
 ****************************************************************************
 *
 * DESCRIPTION
 *
 * The codec and its public interface are described in codec.h
 *
 ****************************************************************************
 */

//------------------------------------------------------------------------
// REQUIRED INCLUDES
//------------------------------------------------------------------------

#include <stdlib.h> // free(), malloc()

#include "codec.h"
#include "sha1.h"

//------------------------------------------------------------------------
// STRUCTURE DEFINITIONS
//------------------------------------------------------------------------

// NOTE: Normally the structure definition would be in the *.c file to make 
// the structure members inaccessible to outside functions except through
// public function calls. But for the real-time code it has been decided 
// to make the structure members directly visible to the functions that
// manipulate them.

//------------------------------------------------------------------------
// PRIVATE FUNCTION DEFINITIONS
//------------------------------------------------------------------------

#define SHA1_HASH_DWORDS (5)

void ExportMessage(CONFIG *c, CODEC *codec, SINK *sink)
{
	DWORD i;
	DWORD bit;
	DWORD index, offset;

	BYTE *message;

	// Create pointer to next element in sink memory
	message = sink->v + (sink->samples * sink->sample_size_bytes);

	// Discard leading random bits
	for (bit = 0, i = 0; i < c->codec_random_bits; i++, bit++)
	{
		while (codec->checkbit[bit])
			bit++;
	}

	// Extract message bits and pack into byte string
	for (i = 0; i < c->codec_message_bits; i++, bit++)
	{
		while (codec->checkbit[bit])
			bit++;
		index  = i >> 3;
		offset = i & 0x00000007;
		message[index] &= ~c->bitmask[7-offset];
		if (codec->msg[bit])
			message[index] |= c->bitmask[7-offset];
	}

	// Zero pad remainder of last byte if necessary
	while (7 != offset)
	{
		i++;
		offset = i & 0x00000007;
		message[index] &= ~c->bitmask[7-offset];
	}

	// NUL terminate byte string
	index++;
	message[index] = '\0';

	// Advance sink memory pointer
	sink->samples++;
}

//------------------------------------------------------------------------
// PUBLIC FUNCTION DEFINITIONS
//------------------------------------------------------------------------

CODEC *CODEC_Del(CODEC *p)
{
	if (p)
	{
		if (p->state)     { free(p->state);     p->state = NULL;     }
		if (p->digest)    { free(p->digest);    p->digest = NULL;    }
		if (p->hashstate) { free(p->hashstate); p->hashstate = NULL; }
		if (p->msg)       { free(p->msg);       p->msg = NULL;       }
		if (p->checkbit)  { free(p->checkbit);  p->checkbit = NULL;  }
	}
	return NULL;
}

CODEC *CODEC_New(CONFIG *c, DWORD *errcode)
{
	CODEC *p;
	DWORD err;
	DWORD check;
	DWORD i, run;
	err = 0;

	p = (CODEC *) malloc(sizeof(CODEC));
	if (!p)
		err = 1 << 0;

	if (!err)
	{
		// State information
		p->state  = (SHA1Context *) malloc(sizeof(SHA1Context));
		p->digest = (SHA1Context *) malloc(sizeof(SHA1Context));

		// Decode Buffer
		p->msg       = (BYTE *) malloc(c->padded_message_bits);
		p->checkbit  = (BYTE *) malloc(c->padded_message_bits);
		p->hashstate = (SHA1Context *) malloc(c->padded_message_bits*sizeof(SHA1Context));

		// Verify successful memory allocation
		if (!(p->state))      err |= 1 << 1;
		if (!(p->digest))     err |= 1 << 2;
		if (!(p->msg))        err |= 1 << 3;
		if (!(p->checkbit))   err |= 1 << 4;
		if (!(p->hashstate))  err |= 1 << 5;
	}

	if (!err)
	{
		// Initialize checkbit markers
		for (check = TRUE, run = 0, i = 0; i < (c->padded_message_bits - c->codec_stop_bits); i++)
		{
			switch (check)
			{
				case TRUE:
					if (run >= c->codec_clamp_bits)
					{
						check = FALSE;
						run = 0;
					}
					break;
				case FALSE:
					if (run >= c->codec_fragment_bits)
					{
						check = TRUE;
						run = 0;
					}
					break;
			}
			p->checkbit[i] = check;
			run++;
		}

		for (i = 0; i < c->codec_stop_bits; i++)
			p->checkbit[c->padded_message_bits - c->codec_stop_bits + i] = TRUE;

	}

	if (c->diagnostics)
	{
		// Diagnostic Report
		printf("------------------------------------------\n");
		printf("CODEC\n");
		printf("  Creation:............... %s\n", ((err)? "FAILED":"SUCCEEDED"));
		printf("  Location:............... %p\n", (void *) p);
		printf("  Message bits:........... %li\n", (unsigned long) c->codec_message_bits);
		printf("  Random bits:............ %li\n", (unsigned long) c->codec_random_bits);
		printf("  Clamp bits:............. %li\n", (unsigned long) c->codec_clamp_bits);
		printf("  Fragment bits:.......... %li\n", (unsigned long) c->codec_fragment_bits);
		printf("  Stop bits:.............. %li\n", (unsigned long) c->codec_stop_bits);
		printf("  Padded message length:.. %li\n", (unsigned long) c->padded_message_bits);
		printf("  Packet expansion:....... %li\n", (unsigned long) c->codec_expansion);
		printf("  Packet load:............ %li messages\n", (unsigned long) c->codec_packet_load);
		printf("  Decode limit:........... %li messages\n", (unsigned long) c->codec_decode_limit);
		printf("  Message buffer at:...... %p\n", p->msg);
		printf("  Checksum buffer at:..... %p\n", p->checkbit);
		printf("  Hash buffer at:......... %p\n", p->hashstate);
		printf("  State buffer at:........ %p\n", p->state);
		printf("  Digest buffer at:....... %p\n", p->digest);
		printf("------------------------------------------\n");
	}

	if (err)
		p = CODEC_Del(p);

	*errcode = err;
	return p;
}

/* DECODER
 * 
 * The decoder decodes all eight of the packets that start with each of the
 * eight bits in the byte located at the present "read" location of the buffer.
 * 
 * The value of the variable "originbit" determines which of the eight offsets
 * from the beginning of the byte the present packet starts at. The variable
 * "location" refers to the location of the bit in question relative to the
 * beginning of the packet. Therefore, relative to the beginning of the byte
 * where the packet starts, the location is simply "origin + location". This
 * combined location must then be turned into an index and and offset. The 
 * "index" refers to which byte within the buffer contains the bit of interest
 * while the "offset" identifies the bit within that byte. The "index" value
 * must further account for the fact that the first byte in the packet is 
 * located at the "read" point within the index and that the buffer is circular.
 * The "offset" value must be used to mask the byte being examined so that only
 * the bit of interest is considered. For speed purposes, this mask is provided
 * by a lookup table "bitmask".
 *
 * Taking all of this into account, the following steps will check if a 
 * particular packet bit is set:
 *
 * index  = {read + floor[(location + originbit)/8]} mod bufferlength
 * offset = (location + originbit) mod 8
 * status = buffer[index] & bitmask[offset]
 *
 * Since the buffer length is exactly 2^n long, the residue of the index can
 * be taken by simply retaining only the lower n bits. Similarly, the residue
 * of the offset modulo-8 can be taken by only retaining the lower 3 bits. Both
 * of these can be done by performing a bitwise-AND with an appropriate mask.
 * Finally, the division of the effective location within the packet can be 
 * performed by right-shifting the sum by 3 bits. Hence we have the following
 * equations:
 *
 * index = (read + ((location + originbit) >> 3)) & buffermask;
 * offset = (location + originbit) & 0x00000007;
 * status = buffer[index] & bitmask[offset]
 *
 * The most challenging part of the decoding algorithm is the backtracking that
 * must take place when the present partial message is finished, either because
 * it was found to be a dead end or because it resulted in an actual message.
 * The basic task is to traverse the decoding tree backwards until the last
 * partial message bit that was a zero is found. Then that bit is changed to a one
 * and decoding moves forward again. Two special cases have to be taken into 
 * account. First, if there are no message bits that are zero, then the decoding
 * of that packet is finished. Second, checksum bits are always zero and the 
 * decoder must skip over them without turning them to ones.
 * index   0123456789....
 * check   1001001001....
 * msg     0010110110....
 *
 */

//------------------------------------------------------------------------

/*
 * The encoding function can be implemented in a more compact, efficient
 * way. The method used here is intended to mirror the decode operation
 * as closely as possible. This is reasonable because the encoding 
 * operation requires constant time regardless of message and is therefore
 * well constrained.
 *
 */

void Encode(CONFIG *c, SOURCE *source, CODEC *codec, BUFFER *buffer)
{
	DWORD location, msg_bit, pmsg_bit, r, i, index, offset;
	int bit_value;
	BYTE *msg;
	DWORD message_stop;
	clock_t ticks;
	DWORD marks;
	
	ticks = clock();

	marks = 0;
	message_stop = source->sample + c->codec_packet_load;
	if (message_stop > source->samples)
		message_stop = source->samples;

	// Place bookend marks
	location = 0;
	index = (buffer->write + (location >> 3)) & buffer->buffermask;
	offset  = location & 0x00000007;
	if (buffer->buffer[index] & c->bitmask[offset])
		marks--;
	buffer->buffer[index] |= c->bitmask[offset];
	marks++;

	location = c->last_packet_bit;
	index = (buffer->write + (location >> 3)) & buffer->buffermask;
	offset  = location & 0x00000007;
	if (buffer->buffer[index] & c->bitmask[offset])
		marks--;
	buffer->buffer[index] |= c->bitmask[offset];
	marks++;

	while (source->sample < message_stop)
	{
		if (c->diagnostics)
			printf("Encoding message #%lu\n", source->sample);
		// Compute pointer to beginning of present message in source buffer
		msg = (BYTE *) source->v + source->sample * source->sample_size_bytes;

		// Initialize Hash Function state to the Initial Vector
		SHA1Reset(codec->state);

		// Load message into the codec's message buffer
		for (pmsg_bit = 0, r = 0, msg_bit = 0 ; pmsg_bit < c->padded_message_bits; pmsg_bit++)
		{
			if (codec->checkbit[pmsg_bit])
				bit_value = 0;
			else
			{
				if (r < c->codec_random_bits)
				{
					bit_value = rand() < (RAND_MAX >> 1);
					r++;
				}
				else
				{
					index = msg_bit >> 3;
					offset = msg_bit & 0x00000007;
					bit_value = (msg[index] & c->bitmask[7-offset])? 1 : 0;
					msg_bit++;
				}
			}
			SHA1Input(codec->state, c->bitptr + bit_value, 1);

			// Compute hash result for present prefix
			*(codec->digest) = *(codec->state);
			SHA1Result(codec->digest);

			// Generate mark location for present prefix
			location = 0;
			for (i = 0; i < SHA1_HASH_DWORDS; i++)
				location += ((codec->digest)->Message_Digest[i])<<i;
			location %= c->packet_bits;

			// Place mark for present prefix
			index = (buffer->write + (location >> 3)) & buffer->buffermask;
			offset  = location & 0x00000007;
			if (buffer->buffer[index] & c->bitmask[offset])
				marks--;
			buffer->buffer[index] |= c->bitmask[offset];
			marks++;
		}
		source->sample++;
	}

	if (source->sample >= source->samples)
	{
		// Last packet has been encoded. Advance buffer past last packet.
		source->streaming = FALSE;
		c->buffer_advance = c->bufferbytes_per_packet;
	}

	// Advance buffer write pointer to next packet write location.
	buffer->write = (buffer->write + c->buffer_advance) & buffer->buffermask;
	buffer->margin -= c->buffer_advance;
	buffer->ready += c->buffer_advance;

	c->dec_ticks += clock() - ticks;
}

void Decode(CONFIG *c, BUFFER *buf, CODEC *codec, SINK *sink)
{
	SDWORD i, bit;
	DWORD location, index, offset, originbit;
	clock_t ticks;
	DWORD limit;

	ticks = clock();

	// Process all 8 packets that begin within the byte at the front of the buffer
	for (originbit = 0; originbit < 8; originbit++)
	{
		if ((sink->sample_limit - sink->samples) > c->codec_decode_limit)
			limit = (sink->sample_limit - sink->samples);
		else
			limit = c->codec_decode_limit;

		// Check for bookend marks
		index = (buf->read + (originbit >> 3)) & buf->buffermask;
		offset  = (originbit) & 0x00000007;
		if ( !(buf->buffer[index] & c->bitmask[offset]) )
			break;

		index = (buf->read + ((originbit + c->last_packet_bit) >> 3)) & buf->buffermask;
		offset  = (originbit + c->last_packet_bit) & 0x00000007;
		if ( !(buf->buffer[index] & c->bitmask[offset]) )
			break;

		// Initialize Hash Function state to the Initial Vector
		SHA1Reset(codec->state);
		bit = 0;
		codec->msg[bit] = 0;

		while (TRUE) // Loop will terminate with a "break" call
		{
			// Update the hash state for the new message bit
			SHA1Input(codec->state, c->bitptr + codec->msg[bit], 1);
			
			// Compute the packet bit location corresponding to the hash
			*(codec->digest) = *(codec->state);
			SHA1Result(codec->digest);
			location = 0;
			for (i = 0; i < SHA1_HASH_DWORDS; i++)
				location += ((codec->digest)->Message_Digest[i])<<i;
			location %= c->packet_bits;

			// Check for mark at calculated location
			index = (buf->read + ((originbit + location) >> 3)) & buf->buffermask;
			offset  = (originbit + location) & 0x00000007;
			if(buf->buffer[index] & c->bitmask[offset])
			{
				// Update hash state for present partial message
				codec->hashstate[bit] = *(codec->state);
				bit++;
				// IF a complete message hasn't been decoded yet
				if ((DWORD) bit < c->padded_message_bits)
				{
					// Start with 0 for next bit in partial message
					codec->msg[bit] = 0;
					continue;
				}
				// ELSE a complete message has been found
				c->message_count++;
				ExportMessage(c, codec, sink);
				bit--;
				limit--;
				if (0 == limit)
					break;
			}
			
			// Backtrack to last message bit that is a zero
			while ( (bit >= 0) && (codec->checkbit[bit] || codec->msg[bit]) )
				bit--;
			
			// If no bits are zero, then decoding is finished
			if (bit < 0)
				break;
			
			// Change last zero bit to a one
			codec->msg[bit] = 1;

			// Reset hash state
			if (0 == bit) // to initial vector 
				SHA1Reset(codec->state);
			else          // to vector of previous partial message
				*(codec->state) = codec->hashstate[bit-1];
		}
	}
	buf->read = (buf->read + 1) & buf->buffermask;
	buf->empty++;
	buf->margin--;

	c->dec_ticks += clock() - ticks;
}

//------------------------------------------------------------------------