0

I am stuck on pset4/recover. My program appears to recover all 50 images, but I am unable to pass the checker. Any tips or pointers (ha) are much appreciated. -Thad

/** * recover.c * * Computer Science 50 * Problem Set 4 * * Recovers JPEGs from a forensic image. */

include

include

include

include

int main(int argc, char* argv[]) { //inport the card.raw file;
FILE* cardin = fopen("card.raw", "r"); if (cardin == NULL) { printf("file format not supported\n"); return 1; }

//define a two hexademical variable type
typedef uint8_t BYTE;
BYTE jbyte1, jbyte2, jbyte3, jbyte4;

//loop through the card.raw file to find the jpg start sites
int location[51];
int counter = 0;

for (int i = 0; i < 1000000000/512; i++)
{
    fread(&jbyte1, sizeof(jbyte1), 1, cardin);
    fread(&jbyte2, sizeof(jbyte2), 1, cardin);
    fread(&jbyte3, sizeof(jbyte3), 1, cardin);
    fread(&jbyte4, sizeof(jbyte4), 1, cardin);

    if (jbyte1 == 0xff && jbyte2 == 0xd8 && jbyte3 == 0xff && (jbyte4 == 0xe0 || jbyte4 == 0xe1 || jbyte4 == 0xe2 || jbyte4 == 0xe3 || jbyte4 == 0xe4 || jbyte4 == 0xe5 || jbyte4 == 0xe6 || jbyte4 == 0xe7 || jbyte4 == 0xe8 || jbyte4 == 0xe9 || jbyte4 == 0xea || jbyte4 == 0xeb || jbyte4 == 0xec || jbyte4 == 0xed || jbyte4 == 0xee || jbyte4 == 0xef))
    {   
        location[counter] = i;
        counter++;
        if (counter == 50)
        {
            break;
        }
    }
    fseek(cardin, (i+1)*512, SEEK_SET);
}

//find the end of the last file
fseek(cardin, location[49]*512, SEEK_SET);

for (int i = 0; i< (1000000000/512-location[49]); i++)
{   
    BYTE zero = 0;
    BYTE sum = 0;
    for (int j = 0; j < 200; j++)
    {
        fread(&zero, sizeof(zero), 1, cardin);
        sum = sum + zero;
    }
    if (sum == 0)
    {
        location[50] = i + location[49];
        break;
    }
    else
    fseek(cardin, (location[49] + (i+1))*512, SEEK_SET);
}    

//printf("start:  %i\n end:  %i\n", location[49], location[50]);

//write the jpg data to output files
char filename[8];
char jpg[5] = ".jpg\0";
BYTE jbyte;

for (int i= 0; i < 50; i++)
{
    sprintf(filename, "%03d%s", i, jpg);
    FILE* cardout = fopen(filename, "w");

    if (cardout == NULL)
    {
        fprintf(stderr, "Could not create outfile");
        return 2;
    }

    fseek(cardin, location[i]*512, SEEK_SET);

    for (int j = 0; j < (location[i+1] - location[i])*512; j++)
    {
        fread(&jbyte, sizeof(jbyte), 1, cardin);
        fwrite(&jbyte, sizeof(jbyte), 1, cardout);
    }
    fclose(cardout);
}

//goodbye return 0; }

1

While your program is technically correct (it recovers the 50 files correctly), it is terribly inefficient. Because it is so inefficient, it is timing out on the server (which has a slightly different environment and many other tasks running.)

Your code is reading one byte at a time from the input file instead of 512 bytes at a time. In addition, you are using fseeks liberally in a program that shouldn't need them. In this pset, the code should start at the beginning of the input file and simply move straight through it to the end.

A note about read/write efficiency:

Think about this - when a read or a write is executed (for now on, read implies both read and write), it isn't just about getting the data from the disk. The computer has to position the read arm and spin the disk to the position on the disk where it needs to read the data. Once it's there, it actually executes the read. Whether it is one byte or a full block of file data (perhaps 4k, hardware dependent), it's always going to mean spending time and resources for all the overhead - positioning the read head, preparing the data, etc. - plus the actual read. That overhead can take considerably longer to execute, up to 1000 times longer or more, than the actual read. (SSD's aren't nearly as bad as a spinning HDD disk.)

Now, consider this. Read 512 bytes one byte at a time and it will take 512 * overhead + 512 bytes read. Read 512 bytes at once, and it's 1 * overhead + 512 bytes read.

I added two counters to your code, one to count the number of reads, the other to count the number of fseeks. The results were:

reads: 17258284, seeks: 33440

The file size of card is: 17095168 Oct 2 2015 card.raw That means that you're doing about 160k more reads than there are bytes in the file, plus 33k fseeks. The program can be done with about 34 thousand reads, not 17 million. It's also calculating sizeof(zero) and sizeof(jbyte) several million times. (You could calculate them once each and save in two vars.) All of this is just sucking up resources and slowing down the system! Since check50 is running in a more heavily utilized system, it's timing out. That's why the code is failing.

So, while the code is technically correct, it might be time to rethink how it's implemented and do something more efficient. As a side note, the code can be written to handle any number of files, rather than hardcoding it for 50 files. (I believe the check50 test data actually does use a different number of files.)

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance.

| improve this answer | |
  • Thanks for the fast reply! I'm encouraged to hear that the program is technically correct. It ran on my computer in less than a second. I guess I'm frustrated that it doesn't pass because of technical reasons on the cs50 end. After all, this was a 50 pic problem, not a 50 million one, so efficiency wasn't my main goal. Either way, thanks for the input! – thad123 Apr 25 '16 at 0:26
  • Your comments helped me to realize a few key things: 1) fread can be used to read 512 bytes at a time. 2) one of the goals of this problem is to write the problem as efficiently as possible (a concept i had not been considering) 3) library functions can return numbers after execution, and this can be very useful. Anyways, after wrestling with this beast for way to long I finally got it to pass the checker. Thanks again for the help, your comments really made me re-think everything I've learned in my brief one month coding life. – thad123 Apr 26 '16 at 15:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .