stega.c

/**
 * Steganography
 * @file main.c
 * @author Tomáš Pažourek
 * 
 * @note To see various information on standard output,
 * compile with 'DEBUG' preprocessor definition.
 * (add '#define DEBUG' or compile with -DDEBUG flag)
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define MAX_MESSAGE_LENGTH 256
#define CHECKSUM_LENGTH 2
#define LENGTH_SIZE 2 // how many bytes are used to store the message length
#define MAX_DATA_LENGTH 260 // fixed size data-block (message is stored in image in these blocks)
#define MIN_REDUNDANCY 30 // minimal number of repeats before we increase spacing

// error codes
#define E_WRONG_ARGS 0
#define E_MESSAGE_LONG 1
#define E_INVALID_BMP 2
#define E_SMALL_IMG 3
#define E_OPENING_BMP 4
#define E_MALLOC 5
#define E_DECODING_FAIL 6

struct pixel { // single pixel, contains its number in image and 3 RGB channels
	unsigned char channel[3];
	unsigned long number;
};

struct bmp_header { // BMP header (both 14B file header and 40B info header)
	char bfType[3];
	unsigned long bfSize, bfOffset;
	unsigned short bfReserved1, bfReserved2;
	unsigned long biSize, biWidth, biHeight, biCompression, biSizeImage,
			biXPelsPerMeter, biYPelsPerMeter, biClrUsed, biClrImportant;
	unsigned short biPlanes, biBitCount;
};

struct byte_average { // used for message reconstruction in decoding
	// when we divide sum by count on each bit, we get a byte
	unsigned char bitsum[8]; // sum of values for each bit
	unsigned char bitcount[8]; // count of values for each bit
};

unsigned short adler16(const char* data, int length) {
	// simple modulo checksum using tmodification of Adler-32 algorithm
#define MOD_ADLER 65521
	unsigned short a = 1, b = 0;

	for (int i = 0; i < length; i++) {
		a = (a + (unsigned char) data[i]) % MOD_ADLER;
		b = (b + a) % MOD_ADLER;
	}
	// combine output to 16-bit integer
	return b | a;
}

void printError(int error) {
	switch (error) {
		case E_WRONG_ARGS:
			fprintf(stderr, "Wrong arguments. Usage:\nEncoding: ");
			fprintf(stderr, "./stega -e -i input_file.bmp -o output_file.bmp -m 'Message text'\n");
			fprintf(stderr, "(The -e flag can be omitted.)\n");
			fprintf(stderr, "Decoding: ./stega -d -i input_file.bmp\n");
			break;
		case E_MESSAGE_LONG:
			fprintf(stderr, "Message too long.\n");
			break;
		case E_INVALID_BMP:
			fprintf(stderr, "Invalid BMP data.\n");
			break;
		case E_SMALL_IMG:
			fprintf(stderr, "Supplied image too small.\n");
			break;
		case E_OPENING_BMP:
			fprintf(stderr, "Error opening BMP file.\n");
			break;
		case E_MALLOC:
			fprintf(stderr, "Memory allocation error.\n");
			break;
		case E_DECODING_FAIL:
			fprintf(stderr, "Decoding fail, no encoded message found.\n");
			break;
		default:
			fprintf(stderr, "Unidentified error.\n");
	}
}

void readSpace(FILE* inputFile, unsigned short bytes) {
	// reads specified number of bytes and throws them away
	fseek(inputFile, bytes, SEEK_CUR);
}

void writeSpace(FILE* outputFile, unsigned short bytes) {
	char foo = 0;
	// writes specified number of NULL bytes
	for (unsigned char i = 0; i < bytes; i++) fwrite(&foo, 1, 1, outputFile);
}

void readPixel(FILE* inputFile, struct pixel* pixel) {
	memset(pixel, 0, sizeof (pixel));
	for (unsigned char i = 0; i < 3; i++) fread(&(pixel->channel[i]), 1, 1, inputFile);
}

void writePixel(FILE* outputFile, struct pixel* pixel) {
	for (unsigned char i = 0; i < 3; i++) fwrite(&(pixel->channel[i]), 1, 1, outputFile);
}

void readLastBit(FILE* inputFile, unsigned char* destination) {
	// reads the least significant bit of a byte from file
	fread(destination, 1, 1, inputFile);
	// remove other 7 bits and leave the least significant
	*destination &= 0x01;
}

void readBmpHeader(FILE* inputFile, struct bmp_header* bmpHeader) {
	memset(bmpHeader, 0, sizeof (bmpHeader));
	fread(&(bmpHeader->bfType), 2, 1, inputFile);
	fread(&(bmpHeader->bfSize), 4, 1, inputFile);
	fread(&(bmpHeader->bfReserved1), 2, 1, inputFile);
	fread(&(bmpHeader->bfReserved2), 2, 1, inputFile);
	fread(&(bmpHeader->bfOffset), 4, 1, inputFile);

	fread(&(bmpHeader->biSize), 4, 1, inputFile);
	fread(&(bmpHeader->biWidth), 4, 1, inputFile);
	fread(&(bmpHeader->biHeight), 4, 1, inputFile);
	fread(&(bmpHeader->biPlanes), 2, 1, inputFile);
	fread(&(bmpHeader->biBitCount), 2, 1, inputFile);
	fread(&(bmpHeader->biCompression), 4, 1, inputFile);
	fread(&(bmpHeader->biSizeImage), 4, 1, inputFile);
	fread(&(bmpHeader->biXPelsPerMeter), 4, 1, inputFile);
	fread(&(bmpHeader->biYPelsPerMeter), 4, 1, inputFile);
	fread(&(bmpHeader->biClrUsed), 4, 1, inputFile);
	fread(&(bmpHeader->biClrImportant), 4, 1, inputFile);
}

void writeBmpHeader(FILE* outputFile, struct bmp_header* bmpHeader) {
	fwrite(&(bmpHeader->bfType), 2, 1, outputFile);
	fwrite(&(bmpHeader->bfSize), 4, 1, outputFile);
	fwrite(&(bmpHeader->bfReserved1), 2, 1, outputFile);
	fwrite(&(bmpHeader->bfReserved2), 2, 1, outputFile);
	fwrite(&(bmpHeader->bfOffset), 4, 1, outputFile);

	fwrite(&(bmpHeader->biSize), 4, 1, outputFile);
	fwrite(&(bmpHeader->biWidth), 4, 1, outputFile);
	fwrite(&(bmpHeader->biHeight), 4, 1, outputFile);
	fwrite(&(bmpHeader->biPlanes), 2, 1, outputFile);
	fwrite(&(bmpHeader->biBitCount), 2, 1, outputFile);
	fwrite(&(bmpHeader->biCompression), 4, 1, outputFile);
	fwrite(&(bmpHeader->biSizeImage), 4, 1, outputFile);
	fwrite(&(bmpHeader->biXPelsPerMeter), 4, 1, outputFile);
	fwrite(&(bmpHeader->biYPelsPerMeter), 4, 1, outputFile);
	fwrite(&(bmpHeader->biClrUsed), 4, 1, outputFile);
	fwrite(&(bmpHeader->biClrImportant), 4, 1, outputFile);
}

void processPixel(struct pixel* pixel, const unsigned char* data,
		unsigned long length, unsigned long pixelCount) {
	unsigned short redundancyRatio = (pixelCount * 3) / (MAX_DATA_LENGTH * 8);
	// minimal spacing is 1 (= use all bits), spacing 2 (every second bit), ...
	unsigned short spacing = redundancyRatio > MIN_REDUNDANCY ? (redundancyRatio / MIN_REDUNDANCY) : 1;

	for (unsigned char i = 0; i < 3; i++) {
		// will the current bit be changed? (not all bits are changed, depends on spacing)
		if (((pixel->number * 3 + i) % spacing) == 0) {
			// compute which bit from inserted data will we use
			unsigned short dataBitNumber = ((pixel->number * 3 + i) / spacing) % (MAX_DATA_LENGTH * 8);

			/* if the message is shorter then the maximum length,
			 * do not change the remaining bits in the block,
			 * leave the original pixels */
			if (dataBitNumber < length * 8) {
				// set the last bit of channel to 0
				pixel->channel[i] &= 0xFE;

				// find the inserted bit in the data and make it last bit of the channel
				pixel->channel[i] |= (data[dataBitNumber / 8] &
						(0x01 << (7 - dataBitNumber % 8))) >> (7 - dataBitNumber % 8);

#ifdef DEBUG /***** VARIOUS DEBUG OUTPUT (IGNORE) *****/
				if (((pixel->number * 3 + i) / spacing) / (MAX_DATA_LENGTH * 8) == 0) {
					printf("%01d", pixel->channel[i] & 0x01);
					if (dataBitNumber % 8 == 7) printf(" ");
					if (dataBitNumber % 64 == 63) printf("\n");
					if (dataBitNumber == length * 8 - 1) printf("\n");
				}
#endif
			}
		}
	}
}

FILE* inputBmpFile(const char* input, struct bmp_header* bmpHeader) {
	// open input file, load and parse header
	FILE* inputFile = NULL;
	inputFile = fopen(input, "rb");
	if (inputFile == NULL) {
		printError(E_OPENING_BMP);
		return NULL;
	}
	readBmpHeader(inputFile, bmpHeader);

	// check for invalid BMP header
	if (strcmp(bmpHeader->bfType, "BM") != 0 ||
			bmpHeader->bfReserved1 != 0 ||
			bmpHeader->bfReserved2 != 0 ||
			bmpHeader->biBitCount != 24 ||
			bmpHeader->biCompression != 0) {
		printError(E_INVALID_BMP);
		fclose(inputFile);
		return NULL;
	}

#ifdef DEBUG /***** VARIOUS DEBUG OUTPUT (IGNORE) *****/
	printf("\nBMP header:\nbfType: %s\nbfSize: %lu\nbfReserved1: %u\nbfReserved2: %u\nbfOffset: %lu\n",
			bmpHeader->bfType, bmpHeader->bfSize, bmpHeader->bfReserved1, bmpHeader->bfReserved2, bmpHeader->bfOffset);

	printf("\nBMP info:\nbiSize: %lu\nbiWidth: %lu\nbiHeight: %lu\nbiPlanes: %u\nbiBitCount: %u\nbiCompression: %lu\n",
			bmpHeader->biSize, bmpHeader->biWidth, bmpHeader->biHeight, bmpHeader->biPlanes,
			bmpHeader->biBitCount, bmpHeader->biCompression);
	printf("biSizeImage: %lu\nbiXPelsPerMeter: %lu\nbiYPelsPerMeter: %lu\nbiClrUsed: %lu\nbiClrImportant: %lu\n",
			bmpHeader->biSizeImage, bmpHeader->biXPelsPerMeter, bmpHeader->biYPelsPerMeter,
			bmpHeader->biClrUsed, bmpHeader->biClrImportant);
#
#endif

	return inputFile;
}

FILE* outputBmpFile(const char* output, struct bmp_header* bmpHeader) {
	// open output file, write header
	FILE* outputFile = NULL;
	outputFile = fopen(output, "wb");
	if (outputFile == NULL) {
		printError(E_OPENING_BMP);
		return NULL;
	}
	writeBmpHeader(outputFile, bmpHeader);
	return outputFile;
}

int encode(const char* input, const char* output, const char* message) {
	// allocate memory for bmp header
	struct bmp_header* bmpHeader = malloc(sizeof (struct bmp_header));
	if (bmpHeader == NULL) {
		printError(E_MALLOC);
		return EXIT_FAILURE;
	}

	// open input bmp file and load header
	FILE* inputFile = inputBmpFile(input, bmpHeader);
	if (inputFile == NULL) {
		free(bmpHeader);
		return EXIT_FAILURE;
	}

	// compute message length, compute checksum and overall data length
	unsigned short messageLength = strlen(message);
	unsigned short checksum = adler16(message, messageLength);
	unsigned short dataLength = messageLength + CHECKSUM_LENGTH + LENGTH_SIZE;

	// prepare the data for encoding (add message length and checksum)
	unsigned char data[dataLength];
	memset(data, 0, dataLength);
	memcpy(data, &checksum, CHECKSUM_LENGTH); // 2 bytes - message checksum
	memcpy(data + CHECKSUM_LENGTH, &messageLength, LENGTH_SIZE); // 2 bytes - message length
	strcat((char*) data + CHECKSUM_LENGTH + LENGTH_SIZE, message); // rest - message itself

	// open output file and write header
	FILE* outputFile = outputBmpFile(output, bmpHeader);
	if (outputFile == NULL) {
		fclose(inputFile);
		free(bmpHeader);
		return EXIT_FAILURE;
	}

	// size of image data
	unsigned long bmpSize = bmpHeader->bfSize - bmpHeader->bfOffset;
	// size of 1 line of pixels in bytes (including the null bytes at the end)
	unsigned long lineSize = (bmpHeader->biWidth * 3 + 4 - ((bmpHeader->biWidth * 3) % 4))
			- ((bmpHeader->biWidth * 3) % 4 == 0 ? 4 : 0);
	// number of null bytes at the end of each line
	unsigned long remainSize = lineSize - bmpHeader->biWidth * 3;
	// count of all image pixels
	unsigned long pixelCount = bmpHeader->biWidth * bmpHeader->biHeight;

	/* redundancy ratio means how much can we repeat single
	 * data block (260 bytes) in image
	 * when the ratio is greater than the MIN_REDUNDANCY,
	 * we may increase spacing (see processPixel function) */
	unsigned short redundancyRatio = (pixelCount * 3) / (MAX_DATA_LENGTH * 8);
	if (redundancyRatio < 1) {
		printError(E_SMALL_IMG);
		fclose(inputFile);
		fclose(outputFile);
		free(bmpHeader);
		return EXIT_FAILURE;
	}

#ifdef DEBUG /***** VARIOUS DEBUG OUTPUT (IGNORE) *****/
	printf("\nComputed checksum: %d\n", checksum);
	printf("Message length: %d\nData length: %d\nData block length: %d\nData block length in bits: %d\n",
			messageLength, dataLength, MAX_DATA_LENGTH, MAX_DATA_LENGTH * 8);
	unsigned short spacing = redundancyRatio > MIN_REDUNDANCY ? (redundancyRatio / MIN_REDUNDANCY) : 1;

	printf("Pixel count: %lu\nAvailable least significant bits in image: %lu\n",
			pixelCount, pixelCount * 3);
	printf("Redundancy ratio: %d\nMax redundancy: %d => spacing: %d bits\n",
			redundancyRatio, MIN_REDUNDANCY, spacing);

	printf("Data block repetition (due to spacing): %.2f times\n",
			((float) pixelCount * 3 / (float) spacing) / (MAX_DATA_LENGTH * 8));

	printf("Bits in image used: %.0f (%.2f%% of last bits, %.4f%% of all bits)\n",
			((float) pixelCount * 3 / (float) spacing) * ((float) dataLength / MAX_DATA_LENGTH),
			(((float) pixelCount * 3 / (float) spacing) *
			((float) dataLength / MAX_DATA_LENGTH)) * 100 / ((float) pixelCount * 3),
			(((float) pixelCount * 3 / (float) spacing) *
			((float) dataLength / MAX_DATA_LENGTH)) * 100 / ((float) pixelCount * 24));

	printf("\nData (%d bytes):\n", dataLength);
	for (unsigned long i = 0; i < dataLength; i++) {
		unsigned char c = data[i];
		printf("%02X", c);
		if (i % 8 == 7) printf("\n");
		else printf((i + 1 < dataLength) ? " " : "\n");
	}

	printf("\nData binary: \n");
#endif

	struct pixel pixel;
	pixel.number = 0;

	// go through all image data
	for (unsigned long pos = 0; pos < bmpSize;) {
		// read, process, write every pixel
		readPixel(inputFile, &pixel);
		pos += 3;
		processPixel(&pixel, data, dataLength, pixelCount);
		writePixel(outputFile, &pixel);
		pixel.number++;

		// read/write the redundant null bytes at the end of each line
		if (lineSize - (pos % lineSize) == remainSize) {
			readSpace(inputFile, remainSize);
			writeSpace(outputFile, remainSize);
			pos += remainSize;
		}
	}

	fclose(inputFile);
	fclose(outputFile);
	free(bmpHeader);
	return EXIT_SUCCESS;
}

int decode(const char* input) {
	// allocate memory for bmp header
	struct bmp_header* bmpHeader = malloc(sizeof (struct bmp_header));
	if (bmpHeader == NULL) {
		printError(E_MALLOC);
		return EXIT_FAILURE;
	}

	// open input bmp file and load header
	FILE* inputFile = inputBmpFile(input, bmpHeader);
	if (inputFile == NULL) {
		free(bmpHeader);
		return EXIT_FAILURE;
	}

	// size of image data
	unsigned long bmpSize = bmpHeader->bfSize - bmpHeader->bfOffset;
	// size of 1 line of pixels in bytes (including the null bytes at the end)
	unsigned long lineSize = (bmpHeader->biWidth * 3 + 4 - ((bmpHeader->biWidth * 3) % 4))
			- ((bmpHeader->biWidth * 3) % 4 == 0 ? 4 : 0);
	// number of null bytes at the end of each line
	unsigned long remainSize = lineSize - bmpHeader->biWidth * 3;
	// count of all image pixels
	unsigned long pixelCount = bmpHeader->biWidth * bmpHeader->biHeight;

	unsigned short redundancyRatio = (pixelCount * 3) / (MAX_DATA_LENGTH * 8);
	unsigned short spacing = redundancyRatio > MIN_REDUNDANCY ? (redundancyRatio / MIN_REDUNDANCY) : 1;

#ifdef DEBUG /***** VARIOUS DEBUG OUTPUT (IGNORE) *****/
	printf("\nPixel count: %lu\nAvailable least significant bits in image: %lu\n",
			pixelCount, pixelCount * 3);
	printf("Redundancy ratio: %d\nMax redundancy: %d => spacing: %d bits\n",
			redundancyRatio, MIN_REDUNDANCY, spacing);
#endif

	unsigned char oneBit = 0;
	unsigned long bitsRead = 0;

	// data reconstruction, prepare the special array that stores the information about read bits
	struct byte_average* dataR = malloc(MAX_DATA_LENGTH * sizeof (struct byte_average));
	for (int i = 0; i < MAX_DATA_LENGTH; i++) memset(dataR + i, 0, sizeof (struct byte_average));

	// go through the affected bytes (step by spacing)
	for (unsigned long pos = 0; pos < bmpSize;) {
		// read and store the last bit
		readLastBit(inputFile, &oneBit);
		dataR[(bitsRead % (MAX_DATA_LENGTH * 8)) / 8].bitsum[(bitsRead % (MAX_DATA_LENGTH * 8)) % 8] += oneBit;
		dataR[(bitsRead % (MAX_DATA_LENGTH * 8)) / 8].bitcount[(bitsRead % (MAX_DATA_LENGTH * 8)) % 8]++;
		bitsRead++;

		// when we need to step by spacing but null bytes are in the way
		if (lineSize - (pos % lineSize) < spacing) {
			readSpace(inputFile, remainSize);
			pos += remainSize;
		}
		if (spacing > 1) readSpace(inputFile, spacing - 1);
		pos += spacing;

		// read the null bytes at the end of the line
		if (lineSize - (pos % lineSize) == remainSize) {
			readSpace(inputFile, remainSize);
			pos += remainSize;
		}
	}

	// reconstruct data block (only part of it is message)
	unsigned char data[MAX_DATA_LENGTH];
	memset(data, 0, MAX_DATA_LENGTH);

	/* we can compute the average bit value from
	 * the special reconstruction array (dataR)
	 * and store it to data array */
	for (unsigned long i = 0; i < MAX_DATA_LENGTH * 8; i += 8) {
		unsigned char oneByte = 0;
		for (unsigned long j = i; j < i + 8; j++) {
			oneBit = dataR[j / 8].bitsum[j % 8] >= (float) dataR[j / 8].bitcount[j % 8] / 2;
			oneByte <<= 1;
			oneByte += oneBit;
		}
		memcpy(&(data[i / 8]), &oneByte, 1);
	}

#ifdef DEBUG /***** VARIOUS DEBUG OUTPUT (IGNORE) *****/
	printf("\nReconstructed data (%d bytes):\n", MAX_DATA_LENGTH);
	for (unsigned long i = 0; i < MAX_DATA_LENGTH; i++) {
		unsigned char c = data[i];
		printf("%02X", c);
		if (i % 8 == 7) printf("\n");
		else printf((i + 1 < MAX_DATA_LENGTH) ? " " : "\n");
	}
#endif

	// restore message length, restore checksum
	unsigned short checksum = 0;
	unsigned short messageLength = 0;

	memcpy(&checksum, data, CHECKSUM_LENGTH);
	memcpy(&messageLength, data + CHECKSUM_LENGTH, LENGTH_SIZE);

#ifdef DEBUG /***** VARIOUS DEBUG OUTPUT (IGNORE) *****/
	printf("\nReconstructed message length: %d\n", messageLength);
#endif

	// message length doesn't fit, 1st indicator, that no message's encoded
	if (messageLength > MAX_MESSAGE_LENGTH) {
		printError(E_DECODING_FAIL);
		fclose(inputFile);
		free(bmpHeader);
		free(dataR);
		return EXIT_FAILURE;
	}

	char message[messageLength + 1];
	memset(message, 0, messageLength + 1);
	memcpy(&message, data + CHECKSUM_LENGTH + LENGTH_SIZE, messageLength);

#ifdef DEBUG /***** VARIOUS DEBUG OUTPUT (IGNORE) *****/
	printf("Reconstructed checksum: %d\n", checksum);
	printf("Computed checksum: %d\n", adler16(message, messageLength));
	printf("Reconstructed message: %s\n", message);
#endif

	// checksums aren't equal, 2nd indicator, that no message's encoded
	if (checksum != adler16(message, messageLength)) {
		printError(E_DECODING_FAIL);
		fclose(inputFile);
		free(bmpHeader);
		free(dataR);
		return EXIT_FAILURE;
	}

#ifndef DEBUG /* when DEBUG flag is defined, the message's already on output */
	printf("%s\n", message);
#endif

	fclose(inputFile);
	free(bmpHeader);
	free(dataR);
	return EXIT_SUCCESS;
}

int main(int argc, char *argv[]) {
	bool encoding = true;
	char* input = NULL;
	char* output = NULL;
	char* message = NULL;

	// parse arguments
	for (int i = 0; i < argc; i++) {
		if (strcmp(argv[i], "-d") == 0) {
			encoding = false;
		} else if (strcmp(argv[i], "-e") == 0) {
			encoding = true;
		} else if (strcmp(argv[i], "-i") == 0) {
			// input
			if (++i >= argc) {
				printError(E_WRONG_ARGS);
				return EXIT_FAILURE;
			}
			input = argv[i];
		} else if (strcmp(argv[i], "-o") == 0) {
			// output
			if (++i >= argc) {
				printError(E_WRONG_ARGS);
				return EXIT_FAILURE;
			}
			output = argv[i];
		} else if (strcmp(argv[i], "-m") == 0) {
			// message
			if (++i >= argc) {
				printError(E_WRONG_ARGS);
				return EXIT_FAILURE;
			}
			message = argv[i];
			if (strlen(message) > MAX_MESSAGE_LENGTH) {
				printError(E_MESSAGE_LONG);
				return EXIT_FAILURE;
			}
		}
	}

	// check for wrong args
	if ((encoding && (message == NULL || input == NULL || output == NULL)) ||
			(!encoding && (input == NULL))) {
		printError(E_WRONG_ARGS);
		return EXIT_FAILURE;
	}

#ifdef DEBUG /***** VARIOUS DEBUG OUTPUT (IGNORE) *****/
	if (encoding)
		printf("Process: encoding\nInput: %s\nOutput: %s\nMessage: %s\n", input, output, message);
	else printf("Process: decoding\nInput: %s\n", input);
#endif

	if (encoding) return encode(input, output, message);
	else return decode(input);
}