PSET4 Recover.c not clearing Check50

Question

In Pset4 everything is going fine, but recover.c, which inside the IDE works pretty well, recovering all the 50 images in card.raw flawlessly, fails miserably with check50.

when I run it through Check50 (check50 2015.fall.pset4.recover recover.c), it returns the following

:) recover.c exists

:) recover.c compiles

:( recovers 000.jpg correctly

   \ killed by server

:( recovers middle files correctly

   \ killed by server

:( recovers last file correctly

   \ killed by server

Also please note that that the size of jpgs recovered and the size of card.raw is 17094144 and 17095168 respectively i.e., there is a difference of 1kb exact between the two.

Please find my code below :

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <cs50.h>

typedef uint8_t  BYTE;

int main(int argc, char* argv[]){


char* infile = "card.raw";
char name[10];
BYTE sign[4];
BYTE mem[512];
int d;

int counter = -1;

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

if(img == NULL){
    printf("Could not open file %s",infile);
    return 1;
}

do{
    counter++;
    sprintf(name,"%03d.jpg",counter);
    FILE* photo = fopen(name,"w");

    if(photo == NULL){
        fclose(img);
        fprintf(stderr, "Could not create %s.\n", name);
        return 2;
    }

    fread(sign,4,1,img);

    while(!((sign[0] == 0xff) && (sign[1] == 0xd8) && (sign[2] == 0xff) && (sign[3] >= 0xe0) && (sign[3] <= 0xef))){
        fseek(img,-3,SEEK_CUR);
        fread(sign,4,1,img);
    }
    do{
        fseek(img,-4,SEEK_CUR);
        d = fread(mem,512,1,img);
        if(d==1){
            fwrite(mem,512,1,photo);
        }else{
            break;
        }



        fread(sign,4,1,img);
    }while(!((sign[0] == 0xff) && (sign[1] == 0xd8) && (sign[2] == 0xff) && (sign[3] >= 0xe0) && (sign[3] <= 0xef)));
    fclose(photo);
    fseek(img,-4,SEEK_CUR);

    if(d!=1) break;
}while(true);


fclose(img);
return 0;

}

I would greatly appreciate if someone could help me find what I am doing wrong in my code. Thank you!

Answer 1

The 'killed by server' result happens when the program is taking too long to execute. There's an execution time limit built into check50 (I think it's 30 seconds, maybe less), and your code appears to be hitting it. Your program is also running in a more heavily loaded environment, so performance will also be impacted by system load. Without doing an in-depth analysis of your code, it seems to have efficiency issues.

Keep in mind that each disk read (assuming spinning HDDs, not SSD drives), takes about 1000 times longer than a memory read, maybe more. Your code looks for the first signature by checking for it at every byte in the file. That means that it makes 512 checks for every 512 byte block when it only needs to make 1 check. Only the first 4 bytes should be checked. In fact, if there happens to be a random data string in the middle of a 512 byte block that matches a signature, it will generate a false positive.

The problem is further compounded because it reads the data twice - first storing it in the sign buffer and then storing it in the mem buffer. You could cut half of the reads and dramatically improve performance by reading 512 bytes into the mem buffer and simply checking the first 4 bytes for the signature.

You have to realize that in a disk read, it takes about the same amount of time and resources to read 512 bytes as it does to read 4 bytes (same for writes). The actual read is only about 5% of the time and resources required. The vast majority of the time and resources are expended on overhead - positioning the drive heads, rotating the disk to the right place on the disk, etc. (There is only a difference between reading 4 bytes and 512 bytes, or something larger, when the amount of data read exceeds the block size of the disk. A HDD lays down data in blocks. It will consume a whole block of space for any amount of data equal to or less than a full block. For example, a block size may be 4k. A 200 byte text file will be stored in a single block, but the whole block will be allocated for that file, and only that file. The remaining space is unused, and is known as slack space. Similarly, a 4100 byte file would be stored in 2 blocks. The point is that data reads will take the same amount of time unless the data spans multiple blocks on the drive.)

Given that the test data has about 16Mb of garbage data (the check50 test data is not the same as the data you are given), your program is doing about 33 million reads and as many fseeks when it only needs to do about 33,000 - or about 1024 more reads than necessary. The problem continues as the rest of the file is processed.

In short, this is an inefficient program because of all the disk reads and it is hitting the check50 time limits. If you can improve the efficiency, it should pass.

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