Data in recover.c doesn't seem to be aligned at 512-byte intervals... what am I missing?

Question

The instructions for "recover.c" in pset4 seem to indicate that all the jpeg photos will be aligned with a block of 512... eg, I only need to check the first 4 bytes starting at 0, 512, etc to find matches.

I wrote a program initially that only checked every 512 bytes, and only found one match.

Curious, I changed it from 512 bytes to 1 byte, and voila! I got 50 matches. I also printed out the location of each match... and they don't seem to start at 512-byte intervals.

So either something is wrong with my program, or I am failing to understand what the assignment description means when it talks about jpgs being at the start of blocks.

(I will admit, the description already confuses me, as it says both that a new file will end immediately after an old one closes, but also that there can be trailing 0s after the end of a jpg to the beginning of the next block. To me, these seem like contradictory statements, but I suspect I am confused there as well.)

Here is my code:

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

 // #define CARD_SIZE 17095168;

 typedef uint8_t  BYTE;

 typedef struct
{
    BYTE  first;
    BYTE  second;
    BYTE  third;
    BYTE  fourth;
} __attribute__((__packed__))
STARTBYTES;

int main(int argc, char* argv[])
{
    FILE* inptr = fopen("card.raw", "r");
    //should check for error opening file

    STARTBYTES sb;

    int pic_count = 0;
    for(int i =0; i < 17095168 /*CARD_SIZE*/; i += 1/*512*/){
        fread(&sb, sizeof(STARTBYTES), 1, inptr);
        if (sb.first == 0xff && sb.second == 0xd8 && sb.third == 0xff){
        printf("Found an image at %i.\n", i);
        pic_count++;
        }

    }
    printf("Found a total of %i matches.\n", pic_count);

    fclose(inptr);
}

The output:

Found an image at 256. Found an image at 188288. Found an image at 224768. Found an image at 258176. Found an image at 273664. Found an image at 1991936. Found an image at 2020736. Found an image at 2031488. Found an image at 2126720. Found an image at 2173952. Found an image at 2231808. Found an image at 2288256. Found an image at 2365824. Found an image at 2433408. Found an image at 2507264. Found an image at 2540288. Found an image at 2652928. Found an image at 2715648. Found an image at 2774272. Found an image at 2801792. Found an image at 2900096. Found an image at 2931968. Found an image at 2977792. Found an image at 3022336. Found an image at 3060608. Found an image at 3085440. Found an image at 3131648. Found an image at 3137664. Found an image at 3181568. Found an image at 3201408. Found an image at 3261440. Found an image at 3273856. Found an image at 3313792. Found an image at 3326464. Found an image at 3352192. Found an image at 3413760. Found an image at 3443072. Found an image at 3465600. Found an image at 3492352. Found an image at 3520896. Found an image at 3547648. Found an image at 3585024. Found an image at 3688832. Found an image at 3705216. Found an image at 3780864. Found an image at 3844352. Found an image at 3855488. Found an image at 3907840. Found an image at 3948160. Found an image at 4253952.

Found a total of 50 matches.

(note: my real code inserts new lines after each one, but I'm not going to put spaces after every entry here!)

What gives? Am I wrong that the jpegs were supposed to start at a block of 512? Or is my code creating the wrong output somehow?

As a bonus question: as you can see from what I commented out, I initially wanted to define CARD_SIZE as the size of the file (which I checked using ls -l on the jpg folder), but that failed; can you point me to what I'm doing wrong therE?

Update:

Here is the relevant correct code for what I am trying to do (the answer below by Cliff, which I marked as correct, asked me to use a different approach entirely, which is in line with what Zamyla suggests and certainly a good idea, but I'll never learn why my instinctive approach is wrong if I don't work on it until I find an insurmountable problem or an explanation of why it's inferior!)

for(int i =0; i < 17095168/512 /*CARD_SIZE*/; i++)
{
    fseek(inptr, i*512, SEEK_SET);
    fread(&sb, sizeof(STARTBYTES), 1, inptr);
    fseek(inptr, - 4, SEEK_CUR);
    if (sb.first == 0xff && sb.second == 0xd8 && sb.third == 0xff && sb.fourth >= 0xe0 && sb.fourth <= 0xef){)
        {
        printf("Found an image at %i.\n", i * 512);
        pic_count++;
        }
//...

There were a few problems. First, I wasn't setting the read head back 4 spaces after the fread. Second, my loop wasn't doing anything to specify where to read from; it was just iterating once for every byte of the file. I forgot to make the read head change relative to the current iteration.

So from this skeleton code, I don't see why I won't be able to store new jpgs. This also successfully checks only each 512th byte. I guess if I get it working, I'll post a followup question to the boards: if I can do it without creating a 512b temporary buffer, why not do it that way?

PS: 1) I assume there is a trivial command to check the size of a file, which I would use instead of manually entering the size of the file. 2) I'm also interested in why my #DEFINE CARD_SIZE didn't work, letting me plug "CARD_SIZE" into i < CARD_SIZE/512, but I can probably figure that out on my own once I fix the more pressing problems.

Answer 1

There are a number of issues. The code is reading 4*1 bytes at a time, not 1, and not 512. This won't work because an actual signature must appear on a 512 byte boundary. It is possible that by chance, image data could match a signature, so checking intermediate bytes could produce a false positive. (I think there really is at least one buried in the data for this reason.)

You were probably also having problems because you were (I'm guessing, since I don't see that code) trying to read 512 bytes into a 4 byte structure. The buffer has to be big enough to hold the fread output, or it won't do what you expect.

The code isn't storing 512 bytes to be processed and written out - I'll chalk this up to not having gotten that far, but you should do it from the start.

The code is only checking the first 3 bytes, not 4. It should also check for all 16 possible signatures (this year's assignment) and not just the two that Zamyla talks about in her video. There may or may not be 3-byte sequences that match, but the 4th byte doesn't qualify.

You are using a FOR loop based on a specific file size. While this would pass check50, if this were the on-campus class and a real person reviewed this, it would get scored down for not being able to handle any size input file. You should look at a while loop instead.

There may be more issues, but these are significant enough that a rewrite is in order. Discussing other issues would be premature before you have implemented the rest of the program.

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

Answer 2

To answer your comments, you're starting to catch on. First, reading or writing to/from outside storage (We'll call that r/w from now on, unless specifying one or the other) is always slower than r/w to internal memory. If it is to a solid state storage device, it can be a few times slower. If the r/w is to a spinning hard drive, it can take 1000 times longer or more, so yes, it's a big difference. Any r/w operation to a device takes more than just the reading or writing of the data. There is overhead involved - setting up the addressing and the read or write operation, and if it is a spinning disk, positioning of head and spinning the disk around to the right position - in other words, mechanical actions. That's why a hard disk r/w can take 1000 or more times longer to execute. Now, consider that you have that overhead with every read or write.

Why do you say,"Mine, after reading 4 bits, will (once finished) write directly to the file." What are you writing and where are you getting it from?

You seem to have a misconception that I am doing two write actions where you are doing only one to move a 512 byte block from one file to another. To my knowledge, there is no mechanism to write directly from one file to another, so it will be necessary to fread() from the input file and write to internal memory - a buffer variable - and then fwrite() from that buffer to the output file. That has to happen no matter what. Even if there is a direct write, it still has all of the resource usage of a read on the input file and a write on the output file. That resource usage and overhead isn't going to change.

Now, remember the discussion about r/w overhead? Because of that overhead, it takes relatively as much time and resource to read or write 4 bytes as 512 bytes because the overhead for small reads (512 is still small) is most of the resource consumption. By comparison, r/w ops on internal memory have considerably less overhead and most of the resources are expended on the actual read/write. So, it's far more efficient to fread() once from file to memory, do the signature check in memory, and then write the 512 byte block to the output file (or skip the write if the first file hasn't been opened.)

What about fseek() calls? Well, that has it's own resource consumption. Your way requires the file pointer to be changed to a new location based on the start of the file plus an offset that has to be calculated. My method completely eliminates this and the file pointer is updated automatically after each read to the start of the next unread block, which is where we want it to be anyways. In a 20 MB file, that's 40,000 fseek() calls that your code will do and mine will not need.

Let's be completely clear about how I am handling the data. I never read 4 bytes from the file to check the signature. I read in 512 bytes at a time. Once that data is in memory, I check the first 4 bytes for a signature. If it's there, I take certain actions. If not, I take other actions. And no matter what, once the first file is opened, that 512 bytes will be written out to a file. For each 512 byte block, I do one physical read from a file, a signature check, and either discard the data or write it out to a file. That's one read, one write, and no fseek.

Your version doubles the reads and then some because for every 512 byte block, you read 4 bytes, fseek back, then read 512 bytes (although you haven't actually implemented it in your code), and then write out to a file. That's 2 reads, 1 fseek, and 1 fwrite. For a 20 MB input file, multiply that by 40,000. In real terms, it slightly more than doubles processing times.

These are the big concepts here. I could go deeper, but hopefully, you get the idea.

You get points for asking very good questions in order to understand the mechanism of what's going on.