File Compression and multi-dimensional arrays Scenario

Question

A simple matrix could be used to store data about images by using 1’s and 0’s to represent dark

and light shades of color similar to a bitmap. You will find a file data.txt under your assignment

3 on Moodle. The file looks the image of an X drawn on a canvas.

0110000000000110

0011000000001100

0001100000011000

0000110000110000

0000011001100000

0000001111000000

0000000110000000

0000001111000000

0000011001100000

0000110000110000

0001100000011000

0011000000001100

0110000000000110

If we look at the data in the file, there are a lot of repeated digits present in the file. This causes

a lot of overhead in storing the file as you have to store so many numbers. The goal of this

assignment is to use a compression algorithm to compress the file and try to make it smaller

without loosing any information about the data present in the data file.

Compression Algorithm:

One method of compressing a file is to recognize repeated digits and replace the runs of

repetition with a number representing the repetition length. For instance for a line in you file

such as ;

0110000000000110

Can be represented with the line:

1 2 10 2 1

Because there is 1 zero, 2 ones, 10 zeros, 2 ones and 1 zero. It is already understood that only

zeros and ones appear and that zeros apper first in a given line. Thus storing the new line of

data is much shorter (5 numbers) than the original line (16 numbers)

To decompress the encoded file you can follow the reverse implementation of the method

stated above, for example for the encoded data:

4 2 4 2 4

The decompressed data is:

0000110000110000

Objectives

You have to complete the following tasks to successfully complete the assignment.

1. Read the data file data.txt and store its data in a multi-dimentional array

2. Create a file called compressed.txt

3. For every row in the multi-dimensional array

a. Compress the data the file data using compression scheme discussed above

b. Take the compressed line and write it to your compresed.txt file

4. Create a function called decompress. This function should:

a. Read the data from compressed.txt file

b. Decompress it using decompression scheme shown above

c. Print decompressed data to console

5. Create the main function that carries out all the tasks listed above

1.2.2 Use of Functions in Assignment:

It necessary that you implement this assignment using functions. To obtain the maximum

score you must demonstrate the ability to create and use functions of your own. For

example, you may consider creating and using the following functions in your program:

1. Encoding function

2. Decoding function

3. Printing Welcome Message

1.4 Note:

* In all your program constructs you must write comments where necessary. Don’t write

comments for obvious code, but segments of code which seem complex.

* All input should be validated wherever necessary

Answer 1

using namespace std;

#include <iostream>

#include <string.h>

#include <stdio.h>

#include <stdlib.h>

#define MAX (16) // stores strings of 16 bits

// which is 2 bytes...

// so, a Word is just 2 bytes...

typedef struct _TWord

{

char bitstr[MAX+1]; // the string of 16 bits, including NULL Terminator

//the array of integers and it's size

int iCount;

int intStr[MAX];

bool startingBit; // the first bit in the string

} * TWord;

#define Word_SIZE ( sizeof(struct _TWord))

#define TWord_SIZE ( sizeof(TWord))

int fileSize( char * filename)

{

FILE * fptr = fopen(filename,"r");

size_t pos = ftell(fptr); // Current position

fseek(fptr, 0, SEEK_END); // Go to end

size_t length = ftell(fptr);

fclose(fptr);

return(length);

}

inline GetLineCount(char * filename)

{

return( fileSize(filename)/MAX+1);

}

/**************************************************************************************

// compresses the bit string: NOTE that in the worst case scenario,

// the bits alternate: 1010101010101010 or 0101010101010101

// in which case the output is 1111111111111111, a string of 16 1's

***************************************************************************************/

int bits2Ints( TWord word)

{

int iBitStreak=0;

int intIndex=-1;

word->startingBit = (word->bitstr[0]=='1');

for (int iLoop=0; iLoop<MAX-1; iLoop++) //stops just before last bit

{

iBitStreak++;

if (word->bitstr[iLoop]!=word->bitstr[iLoop+1]) //bits differ

{

word->intStr[++intIndex]=iBitStreak; // end of streak

iBitStreak=0; // resets the counter

}

}

//finalizes the last streak of bits

word->intStr[++intIndex]=iBitStreak+1;

word->iCount = intIndex+1;

return(word->iCount); //index is zero-based

}

/**************************************************************************

decompresses the integer string to a 2 byte string of bits;

bitstring MUST be declared as char bitstr[MAX+1] so as to

allow for the NULL TERMINATOR !!!!

*******************************************************************************/

void ints2Bits( TWord word)

{

char chBit = (word->startingBit) ? '1' : '0';

int bitIndex=-1;

for (int iLoop=0; iLoop<word->iCount; iLoop++) // for each integer

{

for (int jLoop=0; jLoop<word->intStr[iLoop]; jLoop++) // populates the bit string

{

word->bitstr[++bitIndex]=chBit;

}

if (chBit=='0') // switches the bit

{

chBit='1'; // we were pushing zer0s, so next we push one1's

}

else

{

chBit='0'; // we were pushing 1one's, so next we push zer0s

}

} //iLoop

word->bitstr[MAX]=0;//null terminator

}

bool Word_Validate(TWord word)

{

int checkSum=0;

for (int iLoop=0; iLoop<word->iCount; iLoop++)

{

checkSum += word->intStr[iLoop];

}

return(checkSum==MAX);

}

void Word_Dump(TWord word, char * debugMsg=NULL)

{

if (debugMsg!=NULL)

{

cout << "*******************************************************************************" << endl;

cout << debugMsg << endl;

}

cout << "*******************************************************************************" << endl;

cout << "bitStr >" << word->bitstr << "<" <<endl;

for (int iLoop=0; iLoop<word->iCount; iLoop++)

{

cout << word->intStr[iLoop] << endl;

}

cout << "starting bit:" << ((word->startingBit) ? 1 : 0) << endl;

}

/***************************************************************************

// reads and compresses up to N lines or EOF, whichever happens fitst;

//returns the # of lines read and compressed

//

// COMPRESSED FILE FORMAT:

// starting bit # of ints array of ints

//

****************************************************************************/

int CompressFile ( char * inputFilename, char * outputFilename, TWord words, int N)

{

FILE * infile = fopen(inputFilename,"r");

FILE * outfile = fopen(outputFilename,"w");

int iLoop=0;

char debugMsg[25];

if (infile!=NULL)

{

for (iLoop=0; iLoop<N; iLoop++)

{

if (fscanf(infile,"%s",&words[iLoop])!=EOF)

{

bits2Ints(&words[iLoop]); //compression occurs here

sprintf(debugMsg," Line # %d \n",(iLoop+1));

Word_Dump(&words[iLoop],debugMsg);

//writes the compression data to output file

int StartingBit = (words[iLoop].startingBit) ? 1 : 0;

fprintf(outfile,"%d %d", StartingBit, words[iLoop].iCount);

for (int jLoop=0; jLoop<words[iLoop].iCount; jLoop++)

{

fprintf(outfile," %d ",words[iLoop].intStr[jLoop]);

}

fprintf(outfile,"\n");

}

else

{

break;

}

}

}

fclose(infile);

fclose(outfile);

return(iLoop+1);

}

int DecompressFile ( char * inputFilename, char * outputFilename, TWord words, int N)

{

int StartingBit;

int n;

int iLoop=0;

FILE * infile = fopen(inputFilename,"r");

FILE * outfile = fopen(outputFilename,"w");

for (iLoop=0; iLoop<N; iLoop++)

{

if (fscanf(infile,"%d %d",&StartingBit,&n)!=EOF)

{

words[iLoop].startingBit=StartingBit;

words[iLoop].iCount =n;

for (int jLoop=0; jLoop<words[iLoop].iCount; jLoop++)

{

fscanf(infile,"%d",&words[iLoop].intStr[jLoop]);

}

ints2Bits(&words[iLoop]);

fprintf(outfile,"%s\n",words[iLoop].bitstr);

Word_Dump(&words[iLoop]);

}

else

{

break;

}

}

fclose(infile);

fclose(outfile);

return(iLoop+1);

}

int main()

{

struct _TWord words[25];

cout << "Welcome." << endl;

cout << CompressFile( (char*)"data.txt",(char*)"compressed.txt",words,25) << " lines compressed " << endl;

cout << DecompressFile("compressed.txt","copydata.txt",words,25) << " lines decompressed " << endl;

CompressFile("copydata.txt","copycompressed.txt",words,25);

/************ the contents of data.txt and copydata.text should be identical...

the contents of compressed.text and copycompressed.text should be identical ... */

}