>> David: Welcome back.
This is Week 5 of CS50 and this is Sudoku in Problem Set 4.
If you haven't dived in already this week you will be again
handed some so called distribution code.
Lines of code that we have written that provides you
with a framework with which to begin this problem set
and there, from there you then have to proceed to fill
in some blanks namely to implement this game of Sudoku.
Now for those unfamiliar,
this is a game that's still pretty popular
in various newspapers that you get on the subway and the like
and you can fill in some boxes with numbers
and it looks a little something like this.
Now this screen shot here is of the staff's implementation
of the hacker edition actually
and what we've used is a little bit
of so called ASCII using the characters on the keyboard
in order to render a Graphical User Interface
but what's interesting about problem set four is
that with problem set three the game of 15, it too was a game
and it too had a GUI of sorts,
but recall that for problem set three to print that GUI
out all we kept doing was calling print F from the top
of the screen all the way down and when we had a special line
of code that would clear the screen
and then we would redraw the whole board from top to bottom.
Now, this doesn't really lend itself to very good animation
and it's certainly not terribly efficient if just
to update the board you essentially have
to redraw the whole screen.
In fact, if you play with hence forth problem set three your
implementation on a really slow Internet connection,
maybe back home over vacation you might actually see the
screen redrawing if your connection is sufficiently slow
that you literally see each line getting drawn.
So much more efficient at least conceptually would be
if you want to update part
of the screen don't redraw the whole darn board top
to bottom, left to right.
Just update the individual character that you care about.
And so we introduce in problem set four a graphical library.
It's called ncurses, for new curses, and this is a C library
that is code that other people wrote that you can integrate
into your own programs that allows you
to have a much more compelling graphical interface.
Now at the end of the day the graphics are still just
characters from the keyboard, ASCII codes themselves.
Toward the end of the semester we'll introduce actual graphics
and in the context of web programming
but as this board here suggests you can actually
in this game ultimately move a cursor up, down, left,
right as you can see with the actual running code here.
So the game of Sudoku for those unfamiliar gives you a board
like this, a grid.
It's got nine numbers across, nine numbers down,
and then it's divided into nine squares and you're given a bunch
of numbers from the start such as those depicted here in yellow
and the challenge of this game is to figure
out what numbers you should put where all of these blanks are,
where all of these dots are and the constraints are as follows.
You can only put each number from 1 to 9 in a row once.
So, you can have the numbers 1, 2, 3, 4, 5, 6, 7, 8,
9 in any order in that top row,
but you can't repeat any of those digits.
Similarly you have to obey that constraint
with every vertical row in the chart and then finally you have
to make sure that you never reuse the same number
within each individual square.
So those are the three primary constraints
and to be honest even if you've never played this game before
it's actually kind of neat in that especially if you play one
of the n00b levels as we call them; one of the easier levels
where you can pretty much always make forward progress
if you look for logically a hole that you can fill in.
The strategy that you can implement is something
like this.
Let's see if we can't find an easy one to fill out ourselves.
So, for instance down here in the bottom left-hand corner
if I move my cursor, I definitely cannot put 9, 7 or 5.
I could put 6, 7, I could not also put 6, 7 or 3, but I could,
for instance put for now the number 1, but no, I can't.
Now, this is not a feature you have to implement
in the standard edition,
but notice in the hacker edition I changed the colors
of all those dots to red.
That's because I've violated one of the constraints.
Why can I not put 1 in the corner?
So 1 is already in that same square
and so this is the basic idea and what's neat in the end is
that you'll have the ability to actually play this game
and if you choose to elect the hacker edition of this pset,
well, much like God mode in the game of 15 you can just kind
of hang on to the number 8 for hint and the game will be solved
for you, but that's for this hacker edition only
and the standard edition you implement the game itself.
Some more on that in the specification.
For those then who caught on to that definition
of Sudoku pretty quickly, here's a little bit for geek humor.
Right, pretty lame game at this point,
but there is one correct solution to this problem.
All right if you're not sure what that means,
go ahead and ask in sections.
It's a pretty simple game that one.
So quiz zero is coming up.
So this is the first of two milestones in the course.
This is really meant to be not an opportunity just regurgitate
things we've said, this is not an opportunity
to see how well you can code on a piece of paper,
but rather how well you've mastered certain concepts
in the course, how you can spot say problems in code
or how you can draw or how you can pen a few lines for code
in the order of tens of lines of code in the context of a quiz.
You're not going to have, of course, a computer with you,
you're not going to have a compiler with you
and so the quiz will be designed in a way
that understands the constraints of this problem we'll hand
out a PDF, print out of a PDF this Wednesday
that will tell you exactly what to do next Wednesday
so the quiz is in lieu of lecture next Wednesday
so that you guys actually have something to draw on.
We will not be in Sanders.
We've reserved a few rooms elsewhere on campus
with actual writing surfaces, and you'll be dispatched
to different rooms according to this printout based
on the first letter of your last name.
So more on that on Wednesday,
but know that there are innumerable resources coming
up available to you.
So, one, this Sunday during the regularly scheduled walk
through time will be a course-wide review session.
The details of that will be on this handout on Wednesday,
but that will be 7PM this Sunday.
All sections this coming Sunday, Monday,
Tuesday will also involve quiz review.
Because of the quiz there is no pset due next week.
>> Student: Oh.
[Laughter]
>> David: Very sorry.
There is no pset due next week so if there's a silver lining
in having any sort of examination it is
that there's no pset that corresponds to it.
[Laughter] So, let's regroup here.
So, more on that on Wednesday, but also actually in terms
of resources there are three years' worth of past quizzes
and sample solutions on the course's website.
Just click quizzes so those are probably the best guide toward
getting a sense of what format to expect
and if you haven't noticed them already let me draw some
explicit attention to what's on the lecture's page
and has been here for some time.
Everything we use and do in lecture ends up on this page.
Now, if you expand everything at once,
it looks a little overwhelming, but the juiciest stuff,
for instance, are things like the scribe notes that one
of our teaching fellows, Andrew Sellergren, produces.
These are meant to be sort
of an authoritative teaching fellow's guide to what happened
in lectures and they're actually quite fun to read.
Andrew like me is a fan of snarky little foot notes.
In fact, he commented to me recently
when writing the scribe notes why does everyone clap
at the end of a computer science lecture?
It's just a computer science lecture and I actually agree.
You're all very kind sometimes to have this awkward applause
at the end of lecture, but it's just a computer science lecture
so feel free to get right up out of your seats
as soon as we're done.
No need for that.
That will make Andrew happy, hello, Andrew.
Andrew scribes these lectures based on the video
so what we say ends up written down.
All right.
So, for those of you who are thinking of switching either
to graded status or to pass/fail status, today is, in fact,
that fifth Monday of the term.
We will have pink sheets on the sides of the stage here.
Feel free to just chat with me during break or afterward
if you're a bit on the fence as to what to do.
For those of you who are feeling like maybe you want neither
of those options I thought I'd take a quick tour with you
through bugs from years past
that you can find actually in popular culture.
These are all screen shots that random people some
of them staff, some of them people
on the Internet have taken and if you're feeling
like your code is perpetually buggy
and there's always something wrong, well, realize it is,
in fact, not just you.
So, this of course, was the first such bug
with which we'll set the stage here
that was actually found inside of one of the first computers.
This is perhaps a screen that some of you are familiar with.
It's Windows own blue screen of death.
So, if you'll look here, there's not all much information that's
useful to a normal person other than control alt delete
at bottom left here, but there are some details
that might start to feel
at least a little comprehensible even
if you're not quite sure what to make of them.
On the top left, for instance,
there's this cryptic looking sequence of digits, 0010E36.
Well, this is just a hexadecimal number and this is just a way
of encoding a number slightly more efficiently than decimal
and what this likely refer to?
So it might very well be an error code,
it might very well be an address, too, as we've started
to play with gdb recall that we often see these similarly
looking codes.
a little bit of numbers, a little bit of characters,
these hexadecimal notation
and it often refers to memory addresses.
So, it seems that here a fatal exception,
which just means error, zero E so this just happens
to represent the number 14,
but in this system called hexadecimal,
but more on that to come.
At this location, whatever that means,
but it's mostly numeric or hexadecimal there.
VXD happens to stand for Virtual Device Driver,
which is just Window's way of saying some piece of hardware
that came with like a CD or some driver that you installed
into this computer itself probably had the bug
and that triggered the entirety of Windows to crash in this way.
So, a little more light heartedly, do you see things
that are just a little playful?
And here you see that this is clearly an address of some sort.
We've seen things like this in gdb,
but I've always thought it's kind of amusing at the end
that they kind of simplify it
with the memory could not be read with a little bit
of finger quotes there
with these same pop-ups though do you see errors within errors?
[Laughter] So this is literally a screen shot.
A slightly more amusing is literally this one.
[Laughter] And no joke this is a bug from the mid-1990's
that appeared in Windows.
[Laughter] So that is what happens
when you don't consider corner cases.
Things can certainly get out of control.
a few years ago pop-ups were all the rage on the Web.
You get scenarios like this.
a bit out of control.
It turns out that operating systems like Windows, Mac OS,
Linux and others are actually used in the real world including
by brokers like Fidelity where if you run Windows
on your sign you get blue signs of death.
a little ticker outside some city corner there.
This was from let's say, oh, this was one
of my favorites back in the Vista era.
This was from like a Best Buy or something like that
where they were selling the product.
[Laughter] So that's kind of amusing.
Behind glass no less so it can't easily be fixed.
Now with have Mac OS in fairness.
So Apple kind of simplifies things for people.
They don't tell you
that something has gone wrong they just advise you you need
to restart your computer now, but this is not, in fact,
a good thing when this happens.
Cent OS, which is a variant of Linux,
one that we're actually using in the cluster,
this is probably not what you need to do at this point
in an installation process,
inserting the disk number negative 99.
This one is one of my favorites if only
because I was ordering pizza late one night on Dominos.com,
and I was like ah-ha, this is as perfect lecture example.
What's the bug here?
>> Student: [inaudible].
>> David: So 6.3, right?
So this is printf error of some sort.
Now they probably didn't implement their website
in C. They used some other language,
but this function printf and several variants of it
that we'll see over time are very common in other languages
as well, and it looks like the programmer
that wrote this little advert
for these chicken kickers did not realize
that US currency is typically formatted to point to F
as opposed to just percent F as a format string.
Let's see, one other here that was given to us
by a former student so this is bankofamerica.com, you log in
but this particular day this user logged in
and there is, in fact, a bug.
Allow me to zoom in at top left.
[Laughter] That really should not be, any hypotheses
as to why this actually happened?
It's probably something like a time zone difference
or the time zone setting was wrong, something like this,
but not really inspiring of confidence in a place
where you're storing your money.
So, real screen shot there.
This is not actually a bug, but it's perhaps been written
into infamy by the movie Office Space.
It's something that you can still see in printers on campus.
This is really just an example of an idiotic design decision
when 99% of the time all you need to be told is
to refill the thing, but instead HP decided to introduce this
into the American lexicon.
PC load letter anyone?
Paper, cassette, load letter-sized paper, right?
Instead of just add paper.
So, if you've never seen this movie that I keep referring to,
Office Space, do rent it and you will see three guys go to town
on a printer like this in a very famous scene.
So, without further ado, those are bugs that other people make.
It's quite normal to be making them initially yourself
and now is our transition to exactly the kind
of code we've been writing so many bugs in.
So, we had this picture, this mental model,
for the past couple of days
and this really just represents a computer's memory
and we've started kind
of arbitrarily allocating different areas of our RAM
to different purposes.
So at the very bottom there we have these things called
environment variables, which we don't play with much,
but they have to do with system-wide settings generally.
The stack though has been of particular interest.
It's on the stack that any local variables go.
Any time you call a function it gets a chunk
of memory called a frame on the stack
and you keep layering them again and again
and again every time one function calls another,
but then as soon as that function recall stops executing,
that memory goes away or at least it's no longer valid
so it's not safe to trust,
but we have on occasion seen variables containing
garbage values.
If you just declare int X semicolon, recall that on one
or two occasions we've actually used printf and printed
out its value and once I think it was zero just by luck,
but then some other time it was some completely random value.
Well, where did that come from?
Well, if you're using this stack and reusing this stack
and you're just changing what bits are
where by assigning variables values
and then you're just forgetting where those values were,
certainly if you reuse that memory later
on in your program might you have some bogus value inside a
new variable because it just happens
to have been put inside RAM where something once was.
And since this is why it's terribly important
to always initialize variables
to some knowing state least you accidently use some value that's
not yours or actually follow a pointer, an address,
that's not, in fact, valid.
This is actually a security concern, too.
You can imagine a program whose purpose in life is
to ask someone for their user name and their password
and you check that their user name and password are correct
by calling a function and so while you're in that function,
you need to store what the user typed in for user name
and for password in the frame on the stack.
Well, as soon as you've checked that their user name
and password is correct, this function might return,
the program might go on executing,
but where is the potential security danger here?
Yeah?
>> Student: [inaudible]
>> David: Yeah.
So, your user name and more importantly your password might
actually be lingering somewhere there in memory.
Now, so long as your program is trustworthy,
you yourself have written it, that's maybe not such a big deal
because only you, the programmer of that program,
can later access that same memory,
but we'll talk briefly this week
about something called a buffer overflow exploit that is one
of the most common ways, some random person on the Internet
or some hacker can compromise a program by inserting data
into your program and tricking it
into running some other code that they wrote.
So, if this is the case whereby you can leave secret stuff
like passwords somewhere in your memory but there is a chance
that someone else can access that memory,
therein lies the potential security threat.
So, more on that in more technical detail to come.
This thing called the heap.
What was the difference about the heap that we touched
on at the end of last week?
What's it used for?
Yeah?
>> Student: The memory that you allocate...
[inaudible].
>> David: Okay, good.
Let me tweak the jargon, but the memory you allocate on the
so called heap does not get reused
until you yourself free it up.
So, if you ask the operating system for memory
and you grab it from this thing called the heap,
that memory is yours until you call a function
that we'll see today called free that explicitly hands
that memory back to the operating system.
The up side of that is that any function you write can ask
for as much memory as it wants and it's not going to disappear,
it's not going to get reused because it's not coming
from that place called the stack.
Now, we introduced this toward the tail end of last week
because we realized this is really stupid.
If I have to write programs that have to know
in advance how much memory the user is going to need,
case in point was the quizzes example.
What if the number of quizzes in some semester changes?
I don't want to go back and change my source code,
recompile my program just to change
that hard-coded constant from 2 to 3.
I'd much rather ask the user
when they run the program how many quizzes were there
this semester?
And then dynamically get data from the user.
Well, we introduced a function last week with which we can ask
for chunks of memory and this thing was called what?
So this was malloc, memory alloc,
and this was just a function that took a number
as an argument how many bytes of memory do you want
and you get it and then we'll see today that you better return
that memory otherwise you induce what's generally called a
memory leak.
So first let's actually play with some of these ideas
in a real environment.
So I'm going to go ahead into a file
from last week called bar.c. So if you have your printouts
from last week this is in bar.c. If not, not to worry.
We're going to step through it deliberately on the screen.
This is a pretty stupid program.
It's been contrived only for the purposes of stepping through it
with gdb, but so that we can see some interesting detail.
So, at the very top of this function we have a function
called main.
It takes no command line arguments
so I've explicitly said void.
It seems to allocate an integer called a
and then a char * called S
and as an aside even though I've gotten into the habit
of always putting the star right next to S,
you may see in textbooks or the TF sections spaces sometimes.
That's okay, but this is perhaps a little more clear.
S is the pointer now.
All right.
So we have a char * and this is synonymous with what?
So string, right?
We started to take off
that training wheel verbally last week.
What we used to call string is now char * and this makes sense
because what's really being stored in memory
for a string is the address of a sequence of characters.
The address of an array of characters.
In this case, hello world.
Now, this is just a line of printf,
but notice I'm doing something a little funky here.
I'm first treating S as though it's an array
and that really is true conceptually.
S bracket S gives me the seventh location, 0 index,
of S. So what should that be?
Well, this is 0 the H, 0, 1, 2, 3, 4, 5, 6, 7.
So I count from 0 and I get W at location 7.
So, S bracket 7 would give me a char namely W. What does
ampersand S bracket 7 give me?
It gives me the address of.
So ampersand is the address
of operator even though we haven't seen it
in this context being prefixed
to an array it's just the same question,
at what address can I find the character W?
And so it turns out that this is really going
to be whatever the address of H is plus 7.
So one of the tricks we'll start to see is that what's neat
about pointers is that you can do arithmetic on them.
You can start at one pointer, add some number like 7
and you can make your way to another part
of the string its location
because the computer does not care where strings begin.
The only thing that's important here when I print
out this here is that the string that starts
at location 7 also still ends somewhere
and what was the special character
that demarks the end of a string?
>> Student: [inaudible]
>> David: Yeah, so '0' was a character, a special character.
It's really just the number 0,
but it's a character representing the number 0
that demarks the end of the string
and conceptually it's right after the D here.
We don't see it, but it is, in fact,
going to be used there underneath the hood.
So, in the end, what should this print?
This line of code if I'm printing out the string starting
at the address of the 7th character?
What should print?
Just world.
It's the same idea.
I'm passing in an address of a string
to printf ampersand S says here comes a string so I am passing
in a string but only part of the string
because now I'm leveraging this fact
that pointers can let me get to any location in memory
so if I want to go to the 7th location in this string
and then get the address of it,
I can absolutely now pretend that's a string because notice
that hello world and also just world will have what
at the end of both of them?
They both have that '0'.
So I'm not changing where the string ends;
I'm essentially just starting in the middle
of the string at location 7.
So we'll see this in just a moment as to what this means.
Now in the next line of code here I just arbitrarily say a
gets 5 so that I actually assign it a value.
Then I call foo.
If I step into that, I now have a parameter called N. It's going
to initially have the value of 5 because I passed in A=5.
I declare a local variable here called B. B arbitrarily gets
assigned to N. I do a little bit of mathematics and now just
because I pass B into this last function called bar.
So this last function called bar simply says, hi,
I'm bar as though to confirm that it was, in fact, called,
but notice I'm not even using that int N and why?
This is completely arbitrary.
I just wanted some interesting constructs
with which we could now play with the code
and actually confirm that what we've been preaching verbally
is, in fact, true in reality.
So let's go ahead and make bar.
I'm going to run gdb on this program called bar,
and I'm going to go ahead and type break main
to get a break point at my function
and then notice this OX80483FD represents what perhaps?
So that's the address where main is in memory.
What does that mean?
Well, recall from last week that that chunk of memory
at the very top of RAM is the so-called .text segment.
Those are the 0's and 1's that represent all
of the functions I wrote and then compiled.
So when gdb says, oh, well, main is at OX080483FD that jus means
that is the numeric address
of the function called main in that text segment.
Generally not useful, but it turns
out in C you can actually pass functions around just
as you can variables and you can pass functions around by way
of their addresses, but that's not something we'll
generally do.
Now just a quick crash course
in something that'll be a little more fun in Visual once we get
to Web programming since everyone likes to change colors
of things it turns out that the same notation hexadecimal
notation is used for color codes and Photoshop
and Web development and so forth,
but for now we just need a simple definition.
So, in the world of binary, we represented the number 0 with 0,
the number 1 with 1, the number 2 with?
10 and then the number 3 with 11
and then 100 an notice the pattern.
So I didn't quite line them up optimally,
but I can right now draw this, can I fix this?
Not really.
Well, let's just leave it like that.
So, 0 goes to 1, 1 plus 1 is technically 2,
but I don't have the digit 2 in the binary system so I have
to carry that 1 and so I get 10.
I then add 1, this is easy, get 11 or 1, 1.
Then I add 1 again.
Well, 1 plus 1 is 2, but 2 doesn't exist so I have
to carry the 1 and so forth.
That's how you end up getting the same number here 1 0 0.
Now, in decimal, these things are pretty straightforward.
So this is just 0 1 2 3 4.
Well, what about in hexadecimal?
Actually it starts off the same.
Zero is 0, 1 is 1, 2 is 2, dot, dot, dot,
but now let me do some dot, dot, dot down here.
When I get to the number 9 and then 10 in decimal,
now I've used up all of those digits, but it turns
out in hexadecimal I can go up to 9.
There is no 10 but there is, in fact, A, B, C, D, E,
F. So in this notation called hexadecimal,
you can effectively count from 0 on up to 1, 2, 3, 4, 5, 6, 7, 8,
9, 10, 11, 12, 13, 14, 15.
You can count to 15 by using 0 though 9 and then
when you run out a through F.
Now who cares?
Why is this interesting?
Well, the bigger picture taken away is
that you know have more digits at your disposal
so for representing really large numbers in the millions
and the billions and higher,
you can actually write them using fewer characters
because you have more expressive capabilities
with each single digit.
That is it only takes one character F
to represent 15 whereas in decimal it would take 1, 5,
2 and how about in binary?
How do you represent 15?
It's 1111.
So one's place, two's place, four's, eight.
So 8 plus 4 plus 2 plus 1 gives me 15.
So this is the idea.
With all these different base systems,
really it's just a convention, a convenience for humans.
Hexadecimal tends to be used when you start talking
about larger numbers because you can fit more information
into fewer characters.
Now as an aside so that this feels a little more real and so
that those of you already familiar
with Photoshop can see the connection,
turns out in the graphics world if you want
to represent the number, the color red, you just express it
with what's called and RGB code, red, green, blue.
And so if you want to represent the number red,
you would generally say FF0000.
Now why this?
Here's how much blue you want, here's how much green you want,
here's how much red you want.
So, because each F is 1111, FF is 11111111 so that's cranking
up all the possible red that's available whereas 0 is no green,
0 is no blue so this is how the world represents red.
How does the world represent green?
Well, 00FF00 and you can infer from that.
a good quiz question maybe what blue is actually
represented with.
So for now the whole point is just this is a different way
of expressing numbers and the human convention is generally
to put this character 0X at the start
of any hexadecimal number just to make clear
to the reader here comes a hexadecimal number.
The 0 and the X are not information unto themselves,
they're not part of the address, it's just a notation,
a hint that says here comes a hexadecimal number.
If you ever see any alphabetical letters though in a number,
odds are it's hexadecimal.
If you see G in a number, odds are it's not hexadecimal
because we can't count that high as G. Okay, so back on track.
Here's main.
I've set a break point in this program called bar.c. Let me go
ahead now and run my program by typing run.
We've done this before.
It hits the break point in main.
That first line of code declares a string S, but wait a minute.
Let me type list just so I can see that code again.
Well, it turns out I have an int A. It didn't bother showing it
to me because that was just allocating space.
There was no statement, there was no assignment
so let's do one sanity check.
Let me go ahead and print out the value of a in gdb.
What is this value?
All right.
Garbage value that was not put there by us necessarily.
There was some start-up process that happened
when I first ran my program whereby that memory
on the stack was used for some purpose unbeknownst to me
and I cannot now trust that a has been initialized
to any fixed value because who knows what's there?
But that's okay because in a few lines from now I'm going
to explicitly initialize a to some value so it's a problem
that it's initialized to some junk value.
I just had better not use that for any purpose yet.
So I'm going to go ahead now and print the value
of S. Notice I haven't started executing the lines
of code in this function.
All I did was list the lines and then I printed a now I'm going
to print S and what do I see?
Well, what's this?
It's definitely hexadecimal so it turns
out that S2 is just a variable.
It happens to be a variable of a different type.
It's a pointer to a char, which means it's the address
of some character in memory but at this point
in the story this line of code, line 20,
has not been executed yet.
So because S is a variable just
like a is S2 can have some garbage value.
So the garbage value that's apparently an S is this thing
here, OX312FF4.
That's just whatever number happens
to be there gdb is showing it in hexadecimal notation
because it knows it should be an address
but that doesn't mean it's not a garbage value.
In fact, what is at that garbage value?
Well, gdb is actually telling me it's checking in advance
for me apparently the string that starts
with a vertical bar then a curly brace then this special
code there.
So it's just some junk value.
It's just a coincidence and it's a coincidence, too,
that this string that's at that address is only a few characters
long because gdb stops showing what's there as soon
as it hits a '0' so just by luck there is, in fact,
a 0 byte in the vicinity of that address
and that's why the string does not look longer.
Now, why did this happen here?
Who knows.
It's just an artifact of having run this program
on this machine.
Yeah?
>> Student: [inaudible].
>> David: s plus 30?
Okay so we can do this.
So jumping slightly ahead let me go ahead
and print let's do s plus 30 and now I've advanced,
if you do the math, I've advanced 30 bytes in memory
and what's apparently 30 bytes away
from S's current bogus address is this random character there.
So, you can poke around with gdb anywhere you want in memory.
In fact, if you continue on next year with a course called CS61,
which is low-level systems programming,
one of the first problem sets actually involves they hand you
a program that the staff wrote that they compiled whose purpose
in life is to ask for passwords and then check
if you've typed in the right value.
The problem is if you input the wrong password
into this special problem set program,
it emails the staff saying David got this question wrong.
So the goal of that pset is to actually figure
out what the user's passwords are without triggering this bomb
to go off, without triggering the email to get sent out.
So you obviously can't just run the program at the command line
and start inputting your passwords
because clearly the odds of your guessing the password right the
first time is not going to happen and so you instead have
to run, making I'm making next year's problem set too easy
for you, you could certainly use a tool like gdb, right?
Because with gdb can you pause execution at main
and then start stepping through it poking around, poking around
and if they've hard coded the right passwords
into the program, surely by printing random parts and memory
out can you poke around and see what's actually there.
So, if you take CS61 remember
that don't tell them I said this in lecture.
[Laughter]
All right.
So now let's continue.
Here's the program we're working on.
Let me go ahead and remind you
in main dot C the main function notice I've just initialized S
or I'm about to initialize S to hello world and then we're going
to start printing things out for real.
So let me go ahead and type next in gdb
so now I've executed line 20 so now if I print out what's
at location S notice that S itself is still an address
but it's now the address of this string in memory.
Now where did that end up?
That ended up specifically to be clear at this address.
Now let's go ahead and call printf.
So I'm going to go ahead and type next
and sure enough it printed out the word world
on the left hand side there and let's see why this is.
Well, let me go ahead and printout S bracket 7.
That should print out the 7th character
in the string called S, and in fact, it does.
It prints out W whose ASCII code if you look it
up in the chart is 119 just as lower case a was 97.
So, W is 119.
Well, let me go ahead now and print the address
of S bracket S, and I shouldn't get W per se.
I should instead get the address at that location,
which is this again and yet it shows me world
because gdb realizes, oh, this is the start of a string,
I'm going to just keep showing you character after character
after character until I hit what special value?
Back slash 0 and so I happen to see the word world again
and that's exactly why printf itself printed
out just the word world.
So, now let's go ahead and advance.
If I hit next now, I'm at line 22 so a is currently Print A,
it's currently some bogus value, but now if I do next
and now I Print A, notice that a is now 5, which is as expected.
Now, if I type next again, foo will get called
but gdb won't step into it.
It will just step right over it, foo will do its thing
and that's kind of useless because then my program will end
so I'm instead going to type not next but step that steps me
into recall the function, gdb is reminding me, all right,
I'm in bar.c line 31 so you can do a little sanity check
in another window or on a printout.
I've called a function called foo with an argument of 5.
What do I do here?
Well, I'm going to go ahead and hit next, I'm going to go ahead
and hit next and now let's see what N is.
Well, N is still 5 because that was the argument
that goes passed into foo.
Well, what should B be at this point?
So hopefully B is 10.
That makes sense because I initialize B to N
and then I multiplied B times 2.
This special shorthand notation just means B equals B times 2
so now it's 10 and now what I'm going to do next let me go ahead
and step into bar and now if I print out M the argument
to bar it's indeed 10.
So, at this point now I'm just doing some useless stuff
because it's just going to print high on bar so I'm going
to type continue because I'm getting bored with the process
so the whole thing finishes executing
without breaking again, program exists normally,
which means it returned zero and voila, but the point
for now is not what this program actually did but that using gdb
where we able to confirm that this whole layout of memory is,
in fact, the case and if we look specifically at the addresses
without just saying hexadecimal, hexadecimal,
if you actually look at the numbers, you'll see that all
of the locations of these values are
at different points in this process.
Let's do one sanity check.
Let me go ahead and rerun gdb on bar.
I'm going to set another break point in main and now I'm going
to type run and now I'm going to do this.
So notice that print the value
of a it is some bogus value again,
but let's print the address of a and it looks like the address
of a is here; OXBFFFFF688.
So we'll leave that on the screen.
Let me now type a couple of commands.
Next. Next.
Next. All right I'm going to step.
I want to go into foo for a moment.
Now I'm going to step into foo.
Now, foo recall has an argument.
It's called N. So on this picture foo should be higher
on the stack than main's own variables, right?
Because main has called foo
and eventually foo is going to call bar.
So the stack is growing upward in this way,
but we're about to see a curiosity.
Let me go ahead and print out N, N is indeed 5, let me go ahead
and print out B. B is some bogus value,
but if I execute B equals N by typing next now I print B
and it should be what?
Should be 5 also because I said B equal to N and now last step
if you're following along let me go ahead and print
out the address of B, which is a local variable
in foo and now notice.
So it's a little cryptic at first.
Here is where a was and a is a local variable in main.
Now down here B is a local variable in foo
and notice their addresses.
They're almost the same.
They both start with BFFFF and then a 6, but then we have,
what, 5C and then we have 88.
So, in which direction do things seem to be growing?
So it looks like even though we think of the address,
even though we think of the stack as growing up,
recall that main is going to be on the bottom here
and then foo is going to be on top of it pictorially here and
yet notice foo's address.
Is it bigger or smaller if you compare the two?
So, it's actually smaller so this is actually a problem
and it lends itself
to a security exploit we'll soon see even though conceptually
frankly we call it the stack, it makes nice sense
to say the frames get stacked up and up and up just
like in a cafeteria, but in reality you'll actually see
in some textbooks the pictures reversed
where the stack grows down, which is fine.
You just have to flip your mental model,
but then the whole cafeteria example doesn't really make
as much sense and it's kind of weird
that they called it a stack, but so be it.
But in this case with gdb we're actually confirming visually
that here's a local variable in main and it's
at a decently high, a big address.
Notice that this is a local variable in foo,
but its address is smaller.
So, that means big addresses in RAM are actually at the bottom;
small addresses in RAM at higher up.
So even though I've kind of been cheating
and saying suppose this is byte 0 and this is 1 and this is 2,
it's actually the reverse on most systems
and this is a problem because we'll see this week
that you can exploit that feature of the order of memory
and insert as big a chunk of data as you want
into someone's function and what's going to happen is
because these addresses are going from small to big,
when you insert big chunk of memory, you're going to end
up overwriting previous frames on the stack
and by doing this can you take over the machine
or take over that program.
So that's very abstract for now.
Why don't we go ahead and take a five-minute break
and we'll resume with more detail.
All right so that was a lot all at once and I recognize
that it's kind of hard to follow through gdb
when the screen starts becoming a mess.
So, let's take a look at some perhaps simpler pictures just
to set the stage here, again, mentally.
The story we're telling is that memory is still laid
out relatively speaking the same way it's been
for the past few weeks, but it turns out that byte 0
in your computer's memory is actually up here
and byte 2 billion if you have 2 gigabytes of RAM is lower
in this picture even though the stack itself grows upward
pictorially the addresses must be going from big address
to smaller, to smaller to smaller.
Now why is this of concern?
Well, consider this chunk of code here.
This is a pretty small C program, but it demonstrates one
of the most common attacks
that still compromises servers and programs today.
So here's main down here.
It does, in fact, take command line arguments.
As an aside, you might see in sections
or in textbooks there's this other notation
for ARG V. We generally say char * and then ARG V
with square brackets to make very clear
that ARG V is an array of char *s aka strings
and array of strings.
Well, because an array can also be treated as we've started
to see last week in this
as itself just an address it is also possible to write ARG V
as char * star so consider this just for now a teaser.
You can have things called pointers, two pointers,
that can be useful but for now will generally use our original
notation with square brackets.
But for now it's the same thing.
So this program here calls foo, which is this function up here
and it just blindly passes in ARG V bracket one.
Now just instinctively what is potentially wrong
with this implementation?
So the real answer is going to be no bounds checking,
but there's another problem in main itself.
What am I not doing in main?
So, I'm not checking ARG C. Right,
even though thus far we've been writing main for you recently
in game of 15 and Sudoku, think back to caesar in vigenere
when you had to accept the command line argument assuming
you implemented the requirements
of the specification you probably
at least checked is ARG C equal equal to the number 2
so that you knew there was going to be a number after caesar
or after vigenere's name at the command line.
Here we're just assuming blindly that ARG C is going
to have a count of 2 or more, and I'm passing in bracket 1
of ARG V. So the first word typed after the program's name,
but what if there is no word there?
Well, it looks like I'm going to be jumping
into memory that's not necessarily my own.
So that's one problem, but now let's look
at what foo actually does.
It looks like foo takes a single argument, a string,
aka char *. It then has a local variable called C, C is the name
of an array with 12 characters available in it
and now I'm using this function.
So there's all sorts of fun memory-related functions
in C. We saw one last week, malloc that will keep using.
There's free as we'll see and there's memcpy,
which does as the name implies.
It's not a typo.
Someone decided that saving
that individual character just made the function easier to type
so memcpy, C-P-Y, what does it do?
Well, its purpose in life if we've read the man page is
to take, use the first argument here as a destination,
use the second argument as the source that is what you want to,
what bytes do you want to copy into the destination
and then it takes a third argument,
which is how many bytes do you want to copy?
So, casually speaking memcpy is supposed to copy this many bytes
from bar into C. Now there's a comment here,
which says no bounds checking, but what does that mean?
What really is the danger here?
Yeah?
>> Student: [inaudible]
>> David: Perfect.
So if I type a really long word at the command line
after this program's name, it's not just foo.
It's not just 13.
It is "a really long sentence".
Which if you count that up, that's going to be more
than a really long, I think that's more
than 12 characters you're going
to overflow it seems this buffer.
In other words, I am not only just assuming there's something
in ARG V bracket 1, I'm also then blindly copying the
entirety of that string
into C even though I've only allocated how many bytes
for this variable C. So 12.
So what does this mean in reality?
Well, this means that it will work.
It will copy that many bytes from bar into C,
but there's a danger here as you've seen in your own code
that if you start touching memory that's not yours,
odds are the program is going to do what?
It's going to seg fault, it's going to crash and that's
because you're touching memory that's not your own,
but if you don't type a crazy long string
but one that's a little longer than 12,
but not something ridiculous like a thousand
or a million just, you know,
something a little long that's still in that sweet spot
where the computer doesn't realize that it should crash,
it doesn't realize that that really isn't your memory,
you can actually overwrite some really important information
that's also on the stack that we've not mentioned thus far.
Thus far we've always said
that on the stack goes a function's local variables
and its parameters and that repeats
for each function that's called, but it turns
out we've been taking for granted the fact
that if main calls foo and foo calls bar,
that the computer just knows how to get back from bar to foo
and how to get back from foo to main.
In other words, we've just waved our hands at this detail
of unwinding the stack, removing frames
and we've just assumed the computer knows
where it came from, but that's not the case.
C in a programming language is very low level.
You need to tell the computer
when this function is done executing where to go back
to so it turns out that one of the other pieces
of information that's been stored
on the stack all this time not by you,
but the compiler has been doing this for you, also what goes
on the stack is something called a return address.
So here's a little picture of just the stack.
Consider this a zoomed in version
where it says parent routine stack here.
Suppose this is main.
Now, main lives somewhere in memory in that text segment,
but when you call foo, for instance,
which is this guy up here.
So this is foo up in the blue at the top here,
foo takes this argument and has this local array called C,
when foo gets called, once it's done executing the computer
needs to know what address to go back to.
That is it needs to know go back to main.
So one of the things
that happens inside memory is what goes here
in red is the return address, the address of the line in code
in main that should get executed after foo is done running.
So, this red bar just represents, again,
the address of the specific line of code
that the computer should go back to once foo is done
after you hit that curly brace.
Now notice the danger here now.
If addresses are small up here and big up here,
notice if you pass in more bytes than is expected,
where do those extra dangerous bytes end up?
They end up going this way, right,
and so as this redness suggests,
going over the red part is not a good thing
because it means you could clobber, you could change
that return address to be something else.
Now, if you're the bad guy and you are deliberately typing
in a word at the command line that's not just a word,
it actually represents code that you want to be executed,
if through trial and error
or really smart savvy you know exactly what you should type
at the command line so that the different number ends up here
in the return address, what you can do is trick the computer
by passing in enough bytes
to overload not just the blue segment
and this green segment here
but also this red segment you can trick the computer
into returning to the address not of main
but of the code you yourself just typed in.
So what you can be passing
in to this blue portion is actual executable code
if you know how to represent it with ASCII characters
and you can trick the program
into running your own code what might the program then do?
Well, if this is an installation
of Photoshop you could be tricking it into skipping
that next line of code that says ask user for their serial number
or their registration code and just skip right over it
and execute your line of code instead.
If it's a server, you might be tricking the server
into skipping over that very important line of code
that says check user's password and if you just skip it,
the user might have now unfettered access to the system.
So if have the ability to control the flow of a program
by changing where it's going in memory, you can essentially take
over that program or server and do anything you want thereafter.
So here's a picture so here is to be clear the array called C
and just like I always do
on the blackboard we're representing each byte in
or each char in that array is just a square here's the 0th
one, here's the 11th one, 0 index, so suppose we pass
in an actual word like hello?
It gets passed in as H-E-L-L-O back slash zero
and then this rest of the 12 bytes
that were allocated they're wasted, they're not being used,
but nothing bad has happened,
but now suppose I insert some attack code.
So, just some letters or numbers that happen
to represent executable code what can happen is you can
over run that segment.
So notice before hello is confined to this blue box.
If I now insert some attack code, whatever it looks like,
it might actually overflow everything here and notice
because I've been really smart I've included some numbers,
four hexadecimal numbers, at the very end of my attack code,
which hopefully represent what?
Hopefully represent the address of the code that I inserted
where hello used to be.
So, it's fairly sophisticated and yet a lot
of these attacks are done by trial and error.
It's pretty hard to know a priori
if you didn't write the program what the return address in main
or where rather the return address is.
Where exactly this red bar is,
but what attackers generally do both on the Internet and even
with installations of Photoshop, Microsoft Word,
whatever it is they're trying to crack,
you just try running your attack code again and again
and again and you know what?
If you crash that server or crash that program
or blue screen of death the computer, you know,
that's not actually a bad thing if you're the attacker.
It means you've found a bug, you've found an opportunity
to exploit because if you can run programs and get them
to crash, there's an opportunity there.
Odds are you've passed it too much attack code
or too much input so maybe if you scale back your attack
and send fewer bytes and different addresses,
maybe you can hit that sweet spot
and actually trick the computer into executing your code.
Now a lot of programs today that we all run
on our computers are written in languages like C
and C++ objective C and a whole bunch of other languages
that do not do, offer a number of safety features
that other languages do, for instance,
what we're describing here you can't really do in Java
and frankly even with modern compilers you can generally
check a box in your compiler if you're using like Visual Studio
that will essentially ward off this attack,
but it's frankly just lack of knowledge or lack of savvy
that continues to, that developers continue
to write code that's vulnerable to this and if you read
about some attack
on the Internet involving so-called buffer overflow
or buffer over run exploit,
what they're describing is something like this.
Someone had an array and someone did not check the bounds
of that array and just blindly copy memory data into it
or just blindly tried to print it
or just generally did not check the bounds of that array.
Yeah?
>> Student: [inaudible].
>> David: Good question.
If you yourself have written the code
and you know how big the memory is and will be, it might be safe
to say, okay, you know what you're doing then go ahead
and not bother checking memory but the reality is
if you actually pursue this in a professional capacity
and research capacity, you're not going
to be the only programmer on some projects.
So, whereas you might know what you're doing the next person
might not realize you made some assumption
so frankly the best rule of thumb especially
since we have millions of CPU cycles
at our disposal these days is spin some on the additional
if condition just to protect you from yourself or some colleague.
So, with that said any other questions?
Don't try and run off and do this tonight.
Yeah?
>> Student: [inaudible].
>> David: So parameter is the input to a function,
the thing you put inside the parenthesis when you call it.
That's an argument aka parameter.
>> Student: [inaudible].
>> David: Yep, exactly.
>> Student: [inaudible].
>> David: So, good question, what goes on the stack,
what goes on the heap to recap.
What goes on the stack as we've seen are local variables,
parameters, aka arguments,
and also it appears today something called return
addresses and there's some other stuff, too, that I'll gloss
over for today's purposes,
but this frame pointer there's other sophisticated numbers
that end up on the stack for useful purposes
but they're not as germane right now.
So those three things; arguments, aka parameters,
local variables and return addresses.
What goes on the heap any time you call malloc,
which we're going to start doing today onward
with increased frequency, ends up on the heap.
So, anytime you call malloc, it ends up on the heap.
So that's actually a good segue.
So, let me go ahead and pull up some
of the code we started that's among last week's printouts
and that's namely this one, structs one dot C.
And let's introduce a new feature that's actually quite
useful so that we can get away from stupid little examples
where all we do is store chars and ints.
Let's actually start storing some more real-world data.
So this is structs1.c. It is from, it's the last program
from last week's printout and then we'll, oh, actually
and I did just in case you didn't bring that it's also
in today's printout at the very end.
It's a duplicate of last weeks.
So, in structs1.c, I appear to be doing something a big crazy.
Even though we've only talked about ints and chars and floats
and doubles and strings and pointers and all of this turns
out there's a data type called student, but not quite.
The goal of this program ultimately is
to store some student's specific information.
I want to actually implement a slightly more real-world program
involving students, maybe like the registrar's database,
and I'm assuming every student has an ID number like an int,
a name, a string, and a house, a string also, but I don't want
to have like three different variables for every student
because if I have two students that's six variables,
three students that's nine variables,
a 100 students that's 300 variables feels
like this is an opportunity not only for an array
but it would also be nice to bundle up all
of each student's variables into just one sort of metavariable.
One container variable inside of which is their ID
and their name and their house.
So it turns out we can do that.
At the very top of this file notice I'm just using this
convention, which is pretty common.
If you have some data structures
that you yourself have created it's very typical to put them
into a header file, a .h file and now notice
as you might have seen in recent distribution code any time
you're using a standard,
official library whether it's CS50's or the standard libraries
that come with C itself, you use angled brackets.
If you want to write your own dot H file,
which you're given, in fact, for Sudoku.
There is a sudoku.h file.
You use double quotes just to make clear this is my file
in this directory it's not
in the special directories owned by the system.
So inside of structs.h must be something interesting.
Let's go into structs.h, which you should have as well.
Not much. It's mostly comments,
but notice one new feature of C here.
It turns out if you want
to bundle together multiple variables just
because conceptually it makes more sense to lump them together
and call them by one name, for instance, student.
You can say this, type def for type definition, struct.
So typedef strict then a pair of curly braces
and inside the curly braces you simply list one
by one semicolons at the end of each line what variables,
what types of variables you want to associate
with this particular structure.
Then outside the curly brace you give these type a name.
I'm going to go with the obvious,
I'm going to call this student so now hence forth C
or gcc not only knows about ints and chars and floats and strings
and all of that it will also know about a new data type
that you created called student and inside
of a student struct is going to be three variables
that you can access by name as well.
So now let's actually use this.
There's a new piece of syntax here
but it's actually pretty straightforward.
Let's go ahead and open up structs1.c again.
Let me scroll down.
First take note that just
so that I have a fixed sized program I didn't want
to mix examples so I went back
to the approach of using a constant.
I'm not going to use malloc dynamically just yet.
I'm going to define number of students supported
by this program to be hard coded as three just
so we have something slightly interesting to play with.
Now notice what main does.
main allocates an array called class and inside
of that array are not ints, not chars not floats,
but student structure.
So the syntax is the same it's declaring an array of ints
and array of chars or anything else I just now say student.
Now here's a for loop.
It's going to iterate from 0 up to 3 because students
in all caps is a constant called initialize the 3
and then there's some slightly new syntax mixed with old.
First I use printf and I say students ID,
I'm calling get int, but now I don't have an int variable
per se.
I have a student variable inside of which is an int
so the new piece of syntax here is dot notation.
If you want to go inside of a struct and class[i] is going
to be the i'th student in this array,
if I want to get access not just to the student structure itself
but inside that structure is an ID field.
I go .id and I assign it the return value of GetInt.
Now next recall that name and house were declared as char *s.
So those are strings, which means I can call get string
and assign them a value,
technically assignment the address of a string,
but I can assign them a return value of get string
so I use the same notation.
Get the i'th student
in the array dot name equals get string.
And now notice this would be wrong
because what does class bracket I represent?
It represents a student struct.
So you can't assign a string on the right hand side to a student
on the left hand side, but if you dive into that structure
and say give me the name field inside of that student struct,
then absolutely can you assign
that name the return value of get string.
Yeah?
>> Student: [inaudible]
>> David: How is a struct stored and memory?
So essentially when you declare something simple like an int.
We always draw the as something like this.
So this is the int called a and it's represented as a box.
If I now declare a student with something
like student s semicolon, this too, gives me a chunk of memory
but let's see it has enough memory for an int
and then a char * and then another char *.
So what actually ends up in memory here is an int further ID
but then next to that in memory is also going to be a char *,
which by coincidence is also 32 bits.
The same as an int we said and then also allocated
for a student is this field we called house,
but this is also a char * so a pointer.
So, in fact, I get three, 32 bit chunks of memory back to back
to back or 12 bytes total contiguous.
So it looks like this in memory
or if you ignore the divisions it's just a bigger chunk
of memory that you're handed
because you've clustered it together.
Now that's a slight white lie.
It's possible that the compiler might give you more memory
than you actually asked for just so things line
up in a nice mathematical way,
but conceptually that's what happens.
Yeah?
>> Student: [inaudible]
>> David: Okay.
>> Student: [inaudible]
>> David: Correct.
So, what's really happening then
if I declare student class bracket 3 what happens is
exactly the same story.
I'm going to have to zoom out to make it fit better,
but here is the first student's chunk of memory.
Because this is an array all of the students will be back
to back to back so the next student ends up here
and then the last student ends up not to scale down there.
So this bracket notation though is actually not saying go
to byte one, go to byte two, go to byte three.
When I say S or rather when I say class bracket I,
it's not going to the i'th byte.
It's going to the i'th data member in this array
so the computer checks well how big is a student structure?
It's 12 bytes so when you say class bracket one that's
actually going 12 bytes away from the first student.
It's not going for instance right there.
So all of this happens for you thanks to something we'll look
at actually before long called pointer arithmetic
and it's done sort of magically for you,
but for now just consider the utility of having this ability.
We now have a struct, we can bundle
up together inside one variable or an array of variables and ID
and name and a house together now what's this chunk
of code here that I've stripped the comments
from actually doing?
This for loop in the middle here?
Let's first see if we can infer from context.
So it's doing a comparison.
strcmp is "string comparison."
It checks two strings for equality.
So what is this loop doing?
>> Student: [inaudible]
>> David: Yeah, it's just going to say, it's going to iterate
over all the students, three students in this case,
and it's just going to proclaim so and so [inaudible]
if that's indeed the case.
And so you'll see this in actually you will see this
in Sudoku source code where we use strcmp.
String compare takes two strings, left and right,
and it returns 0 if they're equal
but what's nice is it also returns negative 1
if 1 alphabetically should come before the other
or it returns positive 1
if the other string should go before the other
so you can actually use this
as we'll eventually see the sort strings which can be useful
for dictionaries and spell checkers and things like that,
but for now we're just using it for a silly proclamation.
So and so is in Mather but then down here notice what I'm doing.
Just as I called malloc last week,
it turns out you guys have been writing buggy code
with our blessing for five weeks now.
Every time you call get string that string has to be stored not
in the stack because if the words you typed
in were getting stored
on the stack you could not trust what get string is returning.
So, just conceptually based on the definition we've been using
in recent days of memory when you call get string
to get a string from the user,
where in this picture must the words you type
in be getting stored?
So in the heap, right?
But if they're stored in the heap
and you're just using those strings
and you're never actually saying
to the operating system I am done with this string,
you actually for five weeks now have been leaking memory sort
of unbeknownst to you or maybe you didn't notice as much
because what get string actually calls itself underneath the hood
is this function called malloc and so now hence forth
as we start to take off some of these training wheels
because I've called get string which itself calls malloc
if I want to free the memory that I asked for implicitly
by calling get string,
I just have to call this new function it's not hard to use,
called free, and I pass it, the pointer that's pointing
at the chunk of memory that was handed to me.
So notice here I'm using get strings return value
and remembering it as the name and we said last week that, yes,
this is a string conceptually,
but underneath the hood it's the address
of those characters in memory.
Same deal for house.
Well, later it's really proper now to be freeing the memory
that we've asked the operating system for.
So, let's go ahead and run this program.
So let me go ahead and make struct 1, let me go ahead
and run structs 1 and let's do student ID 1, David, Mather.
Student ID 2, Cansu, Eliot.
Student ID 3, Yuhki, lives in Mather.
Enter. And so we see David is in Mather, Yuhki is in Mather,
but the point really is that underneath the hood I was able
to store all three of those variables, data types,
for each student in its own struct and then bundled them
up together in print just the ones I cared about.
Let me go ahead into the second version of this.
So this is structs2.c. It's also toward the end
of this week's printout.
This is kind of a useless program I just ran.
All I did was ask you for all this input, nine lines of input;
ID numbers, names, and houses and then I did something stupid
like check for "Mather" and then I quit which meant all
that hard work from the user was really for naught.
So suppose we want to do something reasonable
like actually start storing information from users to disks.
Well, thus far you guys have only stored things in variables,
maybe in arrays, but at the end
of the day the program runs any work you did while running
that program, any keystrokes you typed, get lost forever.
So suppose we now want to start creating own our files
and actually store the data on disks it's actually pretty easy
and we can use a function that's very,
very similar to printf to do this.
So, this is up top the exact same program.
I declare an array of students called class.
I then call this loop just to get some data from the human,
but now rather than just do the silly little Mather comparison
in the middle here notice I've added a chunk of code down here.
Now at first glance it might look a little cryptic,
but let's tease it apart line by line.
So here's a new function, open.
It's called "file open."
So this opens a file.
Now that file doesn't have to exist in advance
because you can first specify the name of a file
but then the second argument to F open is what's called the mode
and if you put in "r" that means read this file.
Load it from disk, but that's not the point of this program.
The point of this program is to write to the disk,
write to the hard drive, so you pass "w".
And what this will do is
if a file called database does not exist
in your current working directory
because I've said W it will create it for me.
It will be empty initially, but it will now exist
under the name database.
Here's a little sanity check.
F opens returns a pointer to a new data type
so thus far we've only talked about built-in types like ints
and chars and floats, we made up our own called student,
but there is another one that's built in that's quite useful.
For whatever reason it's in all caps, but it's called FILE
so this is returning one of these things called a pointer
but it's really conceptually a pointer to a file.
Somewhere on disk, I don't know where it is, I don't really care
where it is, I just know that via this file pointer, fp,
by convention can I find that file on disk and add stuff
to it, but first the sanity check.
Almost always when you use pointers should you make sure
they're not NULL because if you follow a NULL pointer what tends
to happen?
Seg faults and you've not probably done this too often
if at all yourselves, but very soon will this be a risk.
So here's a loop.
I'm just iterating over all of my students
and now I'm calling this other function that's probably new
called F printf but F just stands for file.
So this is not printf to the screen,
this is file printf, print to a file.
What file do I want to print to?
Why, I don't redundantly say the name
of the file again and again.
I instead just paste in the name of the pointer that I got back.
So what this means is I'm going to print
to this file percent D back slash N.
So this means print an integer to the file.
Right integer to the file, what integer?
Print the i'th students ID then go ahead
on a new line print the name of that student, the i'th student
in the classes name and then do the same thing for the house.
So in the end, and then F close,
F P once I'm all done just means close the file.
It's like going to file save in most any program on the computer
and then at the bottom here I again called free just
to free up that RAM.
Now as an aside, even though
up until now we've been intentionally
or accidentally writing memory leaks whereby we're asking
for memory and never giving it back, the reality is
when you quit a program generally the memory you asked
for is returned so this isn't necessarily a horrible,
horrible sin we've been committing,
but it's certainly not good practice to ask for memory
and never give it back since there will be situations
where it doesn't get freed automatically.
Case in point most of you I think a few weeks ago kind
of raised your hand or nodded in familiarity
when I asked have you ever sat in front of your computer
after using it for a while and the thing is just getting slower
and slower and slower?
You try to tab between different programs
or click a different icon and it takes forever
for the windows to actually change.
That's generally indicative of your running out of memory.
Now that might not be your fault.
It might be because some of the programs you ran
since you first booted your computer asked for RAM
and never actually gave it back
and so the computer thinks it doesn't have much memory to play
with so things slow down.
So, let's see what actually happens here.
So make structs 2 let me go ahead and run structs 2
and let's do the same kind of input.
Student 1, David Mather, student 2, Cansu Eliot, student 3,
Yuhki, and then Mather, Enter.
Okay nothing seems to have happened, but if I type LS now
for list files there's a whole bunch of stuff
that we'll be able to play with her but the interesting one is,
ah, this one, database.
Let me go ahead and open up database.
This was actually a file that I wrote.
So now what does it mean to create a file?
Well, most of you guys write essays
in things called .doc files or .dock these days
and Excel files are dot xls.
And there's all of these file extensions, file formats
that we're familiar with.
What does that really mean?
Well, this is now the CS50 file format.
We just arbitrarily decided that to store students
in a database we're just going to write each student
on a triple of lines, one after the other,
and then for the next student we're going
to write the next lines of data for that student
and then again and again.
So, if we were to read these same students in for memory,
we would have to have a loop that reads three lines
at a time, grabs an int from each
and then stores them somewhere in memory.
So this is a file format in only so far as we came
up with this arbitrary format
and we've decided how this data is going
to be laid out in memory.
Same as Microsoft done with the dot doc format they just put
things in places they want them to be
and they call it their own proprietary format.
So now let's look at what we've actually been using that's put
these memory, that's created these leaks in the first place.
So let me go ahead and scroll down here.
This is CS50 dot C. So this is the first printout from today.
We won't spend too much time on the library itself
because it's a lot more fun to just take for granted
that these things work but let's at least zoom in on one of them.
So, if you scroll down visually
to the function called get string, let's just get a taste
of what get string has been doing for you all this time
and frankly have perhaps a bit of appreciation for the headache
that is getting user input on, say, Week 0 of a class
if you're not handed helper functions like this.
Even in languages like Java it's a little easier
but it's not nearly as easy
as just calling a function like get string.
So what do I appear to be doing
in this implementation of get string?
So this is, again, the code in the CS50 library
that you've been taking for granted for a couple of weeks.
So the first line of code here string buffer gets NULL.
So it turns out get string does not know in advance, of course,
how long a string, how long a word or sentence you're going
to type in so we assume 0.
We assume that you're not going to type anything just
so we start from an arbitrary starting point.
Maybe not the most efficient, but at least we can't go wrong
if we subsequently grow the amount of space we're using.
So, I declare an int called capacity saying there are no
bytes available yet and then I declare another int called N,
which specifies how many characters are in the buffer.
So in other words conceptually, get string has a buffer.
It's initially this big and we keep track
of not only how big it can be
but also how big it currently is.
So, at the moment it can fit 0 characters
and it has 0 characters.
Now what's the deal with unsigned?
Turns out with a lot of C data types you can prefix them
with keywords like signed or unsigned.
Why might it make sense to call capacity and int unsigned ints?
What's that?
>> Student: [inaudible]
>> David: I haven't initialized it,
but more importantly it's not going to be negative, right?
I can't have a negative amount of space.
Contrary to some of the silly error messages we saw today,
you can't have a negative amount of space and
yet if I'm allowing my numbers to just be an int recall
that an int can be negative and positive
but that's pretty wasteful
because if you use just a signed int
by default integers are signed if you don't specify signed
or unsigned, by default they can be negative or positive
which means in 32 bit int you are throwing away 2 billion
possible values if you know you're never going
to use the negative ones you're just wasting all of those bits.
So rather if I say unsigned,
this means I can now have a string that's between 0
and not 2 billion but 0 and 4 billion characters long.
Now it may be excessive in fairness,
but it's such an easy fix here to not throw away half
of my number space so I went ahead
and prefixed it with unsigned.
So, now let's go ahead and read through what happens next.
I have an int called C, which is actually going
to represent a character and it turns
out we're using a C function called F get C
to get 1 character after another from the user.
So I'm not going to dwell too long on these lines because,
again, we handed this to you for a reason
because this is more sophistication early
on than I think is all that enlightening,
but notice conceptually what we're doing.
F gets C's purpose in life is to get from a special thing
from standard in, S-T-D-I-N.
This essentially represents the keyboard.
So this function F get C gets one character
at a time from the keyboard.
This check here is making sure that the current character C
that we just got from the keyboard is not a special
character called EOF.
So the way a computer signifies, huh-uh,
there's nothing else that the users typed.
They hit enter or they hit control D
or they stopped typing, EOF is a special symbol that signifies
to the computer there's nothing more here
and that's why this loop will terminate as soon as we hit EOF.
Now, let's ignore all of these lines for just a moment
and fast forward just to the bottom of this loop.
At the very bottom of this loop is this line of code here.
This buffer, which initially is this size,
apparently I just keep storing character after character
after character inside of this buffer, but I can't do that
yet because initially the size of this buffer is zero.
So the code I just glossed over is a whole bunch of lines
of code whose purpose in life is
to check all right is the current size, N,
plus 1 over our capacity?
In other words, if I allocated let's say 8 bytes
and I'm already at 8 so 8 plus 1 is 9 and 9 is greater
than 8, I'm out of space.
That means the users typed a ninth character,
my buffer is this big, and I need some more space
over here so what do I do?
You have to jump through some hoops.
I first check and make sure that I'm not going to run
out of memory completely because of the maximum size of an int
but I'm going to completely wave my hands at this one
and let's just focus on the one
that uses a more familiar function or a cousin thereof.
Notice what I do here.
There's another function besides malloc called realloc whose name
implies reallocate memory.
So notice what I'm doing here is I'm reallocating the buffer
to a new size because if we scroll up and this is, again,
why we hand this function to you,
the key detail is this one here.
Every time I run out of space based on that line
of code alone what do I apparently do to my buffer?
I double it.
So, I initially it starts at 0
and then I think we initialize it to, we add one at some point.
I'd have to check the code.
Then it goes to 2 then to 8, then to 4 then to 8 then
to 16 then to 32 and so forth so any time we run
out of space we ask for more memory
but because we're getting things character by character at a time
with fgetc, there's absolutely no risk in the CS50 library
of someone exploiting our code
because you can't possibly pass us a bigger string
than we're expecting because we're only looking at it one
at a time but notice the headache that is this code
and why we bundle it all up in a function called get string
but notice, too, if you look through this code
at your leisure you'll see that almost all of the functions
in the CS50 library use get string to first get the input
from the user and then we convert those strings
to integers.
Now who cares about all of these details?
Well, there are now ways
in which we now have the expressive capabilities
to store things on disk.
Unfortunately, once you have this ability to store things
on disks you have to worry about cleaning things up
and most operating systems today including Windows,
Mac OS and Linux leave a ridiculous number
of bread crumbs, leave quite the paper trail
on your computer even when you so called delete a program
and even if you're just visiting some website
and you're not saving any files but those images
or that text is resident in RAM turns
out that even those photos you're looking at could end
up on your computer's hard drive
in something called virtual memory but more on that
and the solutions there to on Wednesday.
[ Applause ]
Thank you.
Andrew will be please.