Answer To: This assignment is written in C language. You need to compress a bmp file using Huffman code and...
Sandeep Kumar answered on May 04 2021
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#pragma pack(push,1)
typedef unsigned short WORD;
typedef unsigned int DWORD;
typedef unsigned int LONG;
typedef struct tagBITMAPFILEHEADER {
WORD bfType;
DWORD bfSize;
WORD bfReserved1;
WORD bfReserved2;
DWORD bfOffBits;
} tagBITMAPFILEHEADER;
#pragma pack(pop)
#pragma pack(push,1)
typedef struct tagBITMAPINFOHEADER {
DWORD biSize;
LONG biWidth;
LONG biHeight;
WORD biPlanes;
WORD biBitCount;
DWORD biCompression;
DWORD biSizeImage;
LONG biXPelsPerMeter;
LONG biYPelsPerMeter;
DWORD biC1rUsed;
DWORD biC1rImportant;
} tagBITMAPINFOHEADER;
#pragma pack(pop)
typedef struct Headers {
tagBITMAPFILEHEADER* fileHeader;
tagBITMAPINFOHEADER* infoHeader;
unsigned char* bitmapData;
} Headers;
class Stack {
private:
char* array;
int size;
public:
Stack() {
array = new char[100];
size = 0;
}
void push(char code) {
array[size] = code;
size++;
}
char pop() {
if (size > 0) {
char code = array[size-1];
size--;
return code;
}
return ' ';
}
string getCode() {
string code = "";
for (int i = 0; i < size; i++) {
code += array[i];
}
return code;
}
int getSize() {
return size;
}
~Stack() {
//delete[] array;
}
};
typedef struct Node {
int value;
int freq;
struct Node* left;
struct Node* right;
string code;
} Node;
class LeafNodes {
private:
Node** array; // array of addresses of Node
int size;
public:
LeafNodes(int initialSize) {
array = new Node*[initialSize];
size = 0;
}
void append(int value, int freq, Node* left, Node* right) {
Node* newNode = new Node;
newNode->value = value;
newNode->freq = freq;
newNode->right = right;
newNode->left = left;
newNode->code = "";
array[size] = newNode;
size++;
sortNodes();
}
void appendNode(Node* node) {
array[size] = node;
size++;
sortNodes();
}
Node* pop() {
if (size > 0) {
Node* smallestFreq = (Node*)array[size-1];
size--;
return smallestFreq;
}
return NULL;
}
Node* getNodeAt(int index) {
if (size > 0 && index < size && index >= 0) {
Node* node = (Node*)array[index];
return node;
}
return NULL;
}
void sortNodes() { // sort the array based on their freqs, descending order (last one has the smallest freq)
if (size > 0) {
Node* temp;
for (int i = 0; i < size-1; i++) {
for (int j = 0; j < size-i-1; j++) {
if (array[j]->freq < array[j+1]->freq) {
temp = array[j+1];
array[j+1] = array[j];
array[j] = temp;
}
else if (array[j]->freq == array[j+1]->freq) {
if (array[j]->value < array[j+1]->value) {
temp = array[j+1];
array[j+1] = array[j];
array[j] = temp;
}
}
}
}
}
}
void printArray() {
cout << "Size: " << size << endl;
for (int i = 0; i < size; i++) {
Node* current = (Node*)array[i];
cout << "Value: " << current->value << " Freq: " << current->freq;
cout << " Code: " << current->code << endl;
}
}
int getSize() {
return size;
}
string getValueCode(int value) {
for (int i = 0; i < size; i++) {
if (value == array[i]->value) {
return array[i]->code;
}
}
return "";
}
~LeafNodes() {
delete[] array;
}
};
unsigned char* loadBMPFile(char* filename, tagBITMAPINFOHEADER* bitmapInfoHeader, tagBITMAPFILEHEADER* bitmapFileHeader);
string loadHBMPFile(char* filename, tagBITMAPINFOHEADER* bitmapInfoHeader, tagBITMAPFILEHEADER* bitmapFileHeader);
void writeBMPFile(char* filename,tagBITMAPINFOHEADER* bitmapInfoHeader,tagBITMAPFILEHEADER* bitmapFileHeader,unsigned char* bitmapBits);
void writeHBMPFile(char* filename,Headers header,LeafNodes* leafNodesUNMOD,string passwordBits,string flag);
unsigned char getRed(int index,unsigned char* bitmapBits);
unsigned char getGreen(int index,unsigned char* bitmapBits);
unsigned char getBlue(int index,unsigned char* bitmapBits);
unsigned char* colorImage(unsigned char* bitmapBits, unsigned char* dest, tagBITMAPINFOHEADER* bitmapInfoHeader, string flag, int lowerBound, int upperBound);
int bmpFileIsValid(char* filename);
int hbmpFileIsValid(char* filename);
int flagIsValid(char* flag);
LeafNodes* createHuffmanCode(unsigned char* bitmapBits, int bitmapSize);
void traverseTree(Node* root, Stack stack); // traverse the Huffman tree to get the code for each value
void printTree(Node* root);
int toDecimal(long long n);
unsigned long toULLDecimal(unsigned long n);
string toBinary(int n, int numOfBits); // convert an integer into its binary and automatically adds padding
string getBytes(string &bits, int numOfBytes); // reads numOfBytes bytes of a string
LeafNodes* extractInfo(string& info, char* password, string* flag);
Node* createHuffmanTree(LeafNodes* leafNodes);
unsigned char* createBitmap(Node* root, string info, tagBITMAPINFOHEADER* bitmapInfoHeader, string flag);
string encryptPassword(char* password);
string decryptPassword(char* password);
string convertPassword(string password);
void trimExtension(char* string);
int main(int argc, char* argv[]) {
printf("Program started:\n");
// check if there are five arguments being passed
if (argc != 4) {
printf("ERROR: Please check your parameters again.\n");
printf("Format: [programName] [flag] [filename] [password]\n");
return 0;
}
unsigned char* bitmapData;
unsigned char* mmapMemory;
string flag;
char fileName[100];
char fileNameCP[100];
char password[7];
int isCompress = 0;
// check if password is valid
if (strlen(argv[3]) != 6) {
printf("ERROR: Invalid password.\n");
return 0;
}
else {
strcpy(password,argv[3]);
}
// check if the bmp or hbmp filename is valid
if (bmpFileIsValid(argv[2])) {
strcpy(fileName,argv[2]);
strcpy(fileNameCP,argv[2]);
trimExtension(fileNameCP);
strcat(fileNameCP,".hbmp");
isCompress = 1;
}
else if (hbmpFileIsValid(argv[2])) {
strcpy(fileName,argv[2]);
strcpy(fileNameCP,argv[2]);
trimExtension(fileNameCP);
strcat(fileNameCP,".bmp");
isCompress = 0;
}
else {
printf("ERROR: Invalid bmp or hbmp file.\n");
return 0;
}
// check if flag is valid
if (flagIsValid(argv[1])) {
flag = argv[1];
}
else {
printf("ERROR: Invalid flag.\n");
return 0;
}
tagBITMAPFILEHEADER bitmapFileHeader;
tagBITMAPINFOHEADER bitmapInfoHeader;
Headers header;
header.fileHeader = &bitmapFileHeader;
header.infoHeader = &bitmapInfoHeader;
if (isCompress == 1) {
printf("Compressing image..\n");
string encryptedP = encryptPassword(password);
string bitsP = convertPassword(encryptedP);
clock_t start = clock();
LeafNodes *leafNodesUNMOD;
bitmapData = loadBMPFile(fileName,&bitmapInfoHeader,&bitmapFileHeader);
header.bitmapData = bitmapData;
mmapMemory = (unsigned char*)mmap(NULL, (header.infoHeader->biSizeImage), PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_SHARED, -1, 0);
// With fork()
if (fork() == 0) {
...