ZAMLYA CHAN: Let's save the day with Recover.
In Recover, we provide you with a memory card,
but we've accidentally deleted all of the photos on it.
So your job is to recover all of those JPEGs
so that we can see those pictures again.
Now, this might seem a little bit daunting, especially because there's
no distribution code to work off of.
But grab your pen and paper, get ready to draw some concepts out.
We're going to get this done.
Let's break this up into manageable pieces.
So first, I'll talk about how to open the memory card file.
Then we'll talk about how all JPEGs have a distinct header, so we can use this
to find the beginning of a new JPEG.
Once you've done that, we'll open the JPEG and write 512 bytes at a time
until we reach the end of that JPEG and the beginning of another.
From there, we also need to detect once we've
reached the end of the memory card.
First things first, let's open the memory card file.
Using the fopen function, you can do this.
But always remember to check the return value of fopen
to ensure that you didn't get some null value.
So once we open the file, let's find the beginning of a JPEG.
Let's talk about JPEGs.
JPEGs are just sequences of bytes, just like any other file.
What makes JPEGs extinct is that they start with a distinct header.
The first three bytes are always going to be the same for any JPEG,
and then there's a variety of options for the last byte of that header.
You can find these details in the problem's specification.
Now, JPEGs will be stored side-to-side on the memory card,
and each block is 512 bytes.
This is going to be really important, and we'll take advantage of this.
Throughout this problem you might find it
useful to draw for yourself your conception of a JPEG.
Here's just one of the ways that I might draw it out.
Here every box represents 512 bytes.
So from the beginning of the file, each block
is 512 bytes until I reach the beginning of a JPEG, indicated
by a starred block.
From there you'll see that all of the JPEGs follow continuously,
each 512 block at a time, until I reach my end of file.
To read into our memory card, we'll use the fread function, which
takes in four parameters-- first, the pointer to a struct that
will contain the bytes that you're reading;
second, the size of each element to read,
and then the number of elements to read; and finally, the file
pointer that you're reading from.
So how might we do this for the memory card?
In the beginning, we'll start reading in 512 blocks at a time, every time,
checking to see whether the first four bytes indicate a JPEG header.
If not, we don't need to worry about that block and we can proceed
to the next block of 512 bytes, checking that to see
if the header is that of a JPEG.
We continue this process until we reach the first 512 block,
where the first four bytes do indicate a JPEG header.
From there we know that we found our first JPEG.
And from there on out, all of the blocks,
side-by-side, will belong to JPEGs.
So we continue reading in, building up this red JPEG,
in this case, until we reach another block which
indicates the header for a JPEG.
So we know that the red JPEG has ended, so we can close that and then start
a new one.
We continue this process, reading 512 blocks at a time,
until we reach a block that indicates the beginning of a new JPEG.
In which case, we close the previous one and open the next, all the way
until we reach the end of the memory card file.
So how do we read into the file?
Well, we've already talked about the fread function,
but there are actually two ways to do this.
We know that we want to read in 512 bytes at a time,
but we could either read in one block of 512 bytes or 512 blocks one byte each.
Think about this for a second as we talk about the rest of the problem,
and we'll come back to this slide later.
Let's go back to identifying JPEGs.
So we know, per the problem's spec, that each JPEG
starts with a distinct header.
We can definitely check the first three bytes easily,
but then when it comes to the last byte, we
have so many options that writing a condition for checking the header could
get pretty messy pretty quick.
So instead I propose that we use a bitwise AND operator.
Say you've read in 512 bytes into an array called buffer.
Well, then, you can use this code to check whether the first four
bytes of buffer correspond to a JPEG.
If this code returns as true, then you found a JPEG.
All right, so now that we found the beginning of a JPEG, let's
talk about opening it.
The file names, per the spec, need to be formatted
with three digits dot J-P-G, named in the order in which they were found,
starting at zero.
So make sure that you're keeping track of how many JPEGs you found thus far.
We'll use the sprintf function to create a file name for our new JPEG.
Once we have that, we can open, using fopen our new file,
making sure to include writing permissions.
So once we've created the new JPEG and opened that file,
then we need to write 512 bytes at a time until a new JPEG is found.
How do we write those files?
In order to write the 512 bytes into our new file,
we'll use the fwrite function, which takes in four parameters.
The first is a pointer to the struct that contains the bytes that you're
reading from, then the size and number of bytes,
and lastly, the file pointer that you're writing to.
So in this case, the first parameter will be where the 512 bytes are,
and then the out pointer will be our new image file that we've just created.
So now we know how to read into a memory card
and then how to write into a JPEG image file.
So the next step is to figure out, well, when do we stop?
Let's go back to the representation of the memory card.
As we've discussed already, we'll be reading 512 blocks at a time,
checking the header every time, until we reach the start of a new JPEG.
Once we find that, we continue building on 512 blocks at a time.
Let's fast forward to the end, where we've already identified our last JPEG,
indicated by these pink blocks here.
We read in 512 bytes at a time until we reach
the end of a file, which will be less than 512 bytes long.
OK, so knowing that the very last time that we try to read in 512 bytes,
we'll actually get something shorter than that.
Then let's go back to our two options for fread parameters.
When we're reading into the memory card file,
either we could read in 512 blocks, one by each, or, in the second case,
read in one block 512 bytes long.
So which one do we choose?
Well, fread will return how many items of size size were read.
And ideally, this will return the number that we asked for, until it doesn't.
So with that hint, try to see if you can come up
with a condition for when we've read in successfully our 512 bytes,
and then figure out a condition for when we've reached the end of a file.
So let's bring all these pieces together and make some pseudocode.
First we want to open the memory card file.
Then, repeating until we've reached the end of the card file,
we'll read 512 bytes in.
Then we'll ask whether we're at the start of a new JPEG.
If we are, then we'll ask whether we've already found a JPEG.
If we haven't, then that means that we'll start our very first JPEG.
But if we already have found a JPEG, then that
means that we need to close the previous file and then open our new one.
Now, say we've read 512 bytes in and we haven't
reached the start of a new JPEG.
Well, then we ask ourselves, well, have we already found a JPEG or not?
Because if we haven't, then that means that we can simply
discard those 512 bytes and then go to the start of our loop.
But if we have already found a JPEG, then that
means that those 512 bytes belong to the currently opened file.
Finally, once we've reached the end of the memory card, we can exit the loop
and close any remaining files.
Now we're almost done.
The only thing that I ask is that you take pen and paper
and draw out your own representation and your own schematic of how the memory
card works and how those blocks are laid out.
It's really important to understand that,
and then writing the code will be that much easier.
My name is Zamyla, and this was Recover.