1 00:00:00,000 --> 00:00:02,750 [Section 9] [More Comfortable] 2 00:00:02,750 --> 00:00:04,750 [Rob Bowden] [Harvard University] 3 00:00:04,750 --> 00:00:06,750 [This is CS50.] [CS50.TV] 4 00:00:06,750 --> 00:00:12,130 >> All right. Basically today it's all up to you guys to ask some questions. 5 00:00:12,130 --> 00:00:15,070 I might be able to wander with some topics 6 00:00:15,070 --> 00:00:17,570 for a bit if no one has any questions to ask. 7 00:00:17,570 --> 00:00:20,660 Hopefully you do. Does anyone have any questions? 8 00:00:20,660 --> 00:00:25,220 Maybe from past quizzes, things you're not comfortable with currently. 9 00:00:34,630 --> 00:00:37,850 >> Yes. >>[Student] Can you go over buffer overflow attacks? >>[Rob] Sure. 10 00:00:37,850 --> 00:00:45,530 The main example actually might be right here. 11 00:00:45,530 --> 00:00:48,720 The main deal behind buffer overflow attacks are 12 00:00:48,720 --> 00:00:51,540 we have some buffer, here. 13 00:00:51,540 --> 00:00:54,110 Char c--which is only of size 12-- 14 00:00:54,110 --> 00:00:57,580 but then we are inserting something into that buffer 15 00:00:57,580 --> 00:01:00,050 but not checking exactly how much we are inserting. 16 00:01:00,050 --> 00:01:06,740 Here we are inserting strlen(bar) into C, but who knows how long bar is. 17 00:01:06,740 --> 00:01:11,970 If it's longer than 12 characters then this is going to overflow this buffer. 18 00:01:11,970 --> 00:01:15,830 Looking at this picture-- 19 00:01:15,830 --> 00:01:20,840 if you take 61 you'll get much more familiar with this sort of layout 20 00:01:20,840 --> 00:01:25,760 and dealing with the saved frame pointer and return address and parent's routine stack 21 00:01:25,760 --> 00:01:27,760 and all of these actual things. 22 00:01:27,760 --> 00:01:31,340 But here you just need to know that we have 23 00:01:31,340 --> 00:01:35,990 this little space for our buffer. 24 00:01:35,990 --> 00:01:39,480 Here we have c(0) and then we have c, 1, 2, 3, 4, 5 and so on. 25 00:01:39,480 --> 00:01:44,810 Under normal circumstances we would fill this buffer as per usual. 26 00:01:44,810 --> 00:01:50,480 If we inserted 'hello' we'd have h-e-l-l-o/0, 27 00:01:50,480 --> 00:01:52,900 and then just a bunch of empty space. 28 00:01:52,900 --> 00:01:57,910 For a hacker--oh, I guess this is the example. 29 00:01:57,910 --> 00:02:02,470 For a hacker we get something like this where 30 00:02:02,470 --> 00:02:04,760 what they're specifically trying to do is 31 00:02:04,760 --> 00:02:07,890 usually override the return address. 32 00:02:07,890 --> 00:02:12,510 Whenever you call a function and your stack frame gets pushed onto the stack 33 00:02:12,510 --> 00:02:14,690 that stack frame needs to know how-- 34 00:02:14,690 --> 00:02:21,020 well, the function that has been called needs to know how to return to the function that called it. 35 00:02:21,020 --> 00:02:23,780 So, if main calls foo, foo needs to return to main, 36 00:02:23,780 --> 00:02:26,300 and so that's what this return address does. 37 00:02:26,300 --> 00:02:28,800 But what the hacker's going to do is 38 00:02:28,800 --> 00:02:30,820 override it with a special return address 39 00:02:30,820 --> 00:02:40,090 where again--Little Indian--it's not straightforward but each byte is backwards. 40 00:02:40,090 --> 00:02:47,300 This return address as far as the computer is concerned 41 00:02:47,300 --> 00:02:51,390 returning to this address is equivalent to returning to foo or main 42 00:02:51,390 --> 00:02:53,850 or whatever function called it. 43 00:02:53,850 --> 00:02:54,800 So it's going to return to this address 44 00:02:54,800 --> 00:02:58,130 which just so happens to be this address 45 00:02:58,130 --> 00:03:04,740 which either sometimes what they do here is use the return address 46 00:03:04,740 --> 00:03:09,150 of a specific function that they know is already there. 47 00:03:09,150 --> 00:03:12,630 I can't remember what the function's called. 48 00:03:12,630 --> 00:03:14,630 I'll look it up later. 49 00:03:14,630 --> 00:03:17,570 >> Here what they're doing is passing the return address 50 00:03:17,570 --> 00:03:26,310 to the stack itself, and this is somewhat strange where 51 00:03:26,310 --> 00:03:29,530 there are examples of memory where-- 52 00:03:29,530 --> 00:03:34,350 memory can be split up into read-only, read-write, and executable memory 53 00:03:34,350 --> 00:03:38,710 where we have seen read-only memory before where the-- 54 00:03:38,710 --> 00:03:43,960 if I say char*s = hello I can't modify hello. 55 00:03:43,960 --> 00:03:46,200 That's read-only memory. 56 00:03:46,200 --> 00:03:49,570 There's also this idea of executable memory 57 00:03:49,570 --> 00:03:53,870 where the executable memory would be the text segment of your code. 58 00:03:53,870 --> 00:03:57,350 Looking at your usual address space layout-- 59 00:03:57,350 --> 00:04:03,090 I believe that's going to be a good picture-- 60 00:04:08,200 --> 00:04:12,170 this works--where we have our stack up here. We have data memory. 61 00:04:12,170 --> 00:04:16,360 Ignore this basically. This is our heap. 62 00:04:16,360 --> 00:04:18,810 And then we have down here our main program code. 63 00:04:18,810 --> 00:04:27,480 This is similar to the place where we put our strings like char* = hello 64 00:04:27,480 --> 00:04:29,730 and that's read-only. 65 00:04:29,730 --> 00:04:33,590 But you could also mark this main program code as executable. 66 00:04:33,590 --> 00:04:37,950 And if you are doing that or your operating system does that correctly 67 00:04:37,950 --> 00:04:40,910 then this should be the only place in memory 68 00:04:40,910 --> 00:04:44,830 that code can actually execute 69 00:04:44,830 --> 00:04:48,550 which means that this sort of buffer overflow attack we have over here 70 00:04:48,550 --> 00:04:53,800 would be ineffective because this is trying to execute memory up here in our stack. 71 00:04:53,800 --> 00:04:57,230 Notice the pictures are first. 72 00:04:57,230 --> 00:04:59,270 We have our stack growing up. 73 00:04:59,270 --> 00:05:01,270 Here the stack is growing down. 74 00:05:01,270 --> 00:05:03,270 For CS50 purposes the stack grows up. 75 00:05:03,270 --> 00:05:09,520 >> It is possible to circumvent this particular type of buffer overflow 76 00:05:09,520 --> 00:05:15,110 by having these executable regions of memory in non-executable regions. 77 00:05:15,110 --> 00:05:21,420 But it just so happens that rarely is executable memory marked as executable. 78 00:05:21,420 --> 00:05:26,520 It just tends to be read-only and re-write are the only things that are used, 79 00:05:26,520 --> 00:05:28,990 so this is still very effective. 80 00:05:28,990 --> 00:05:31,950 And here we could put whatever we want. 81 00:05:31,950 --> 00:05:35,020 It wasn't actually done as a Pset in 61 this year, 82 00:05:35,020 --> 00:05:38,400 but if you look at last year's offering of it or any previous year 83 00:05:38,400 --> 00:05:44,110 one Pset is you're specifically supposed to insert in here code that is supposed to 84 00:05:44,110 --> 00:05:48,960 print some specific value or return a value that is different from 85 00:05:48,960 --> 00:05:51,400 the value that is supposed to be printed. 86 00:05:51,400 --> 00:05:57,770 Or even more cleverly, it wants you to call or write-- 87 00:05:57,770 --> 00:06:03,320 so this will return up to here and then you'll execute some coding here, 88 00:06:03,320 --> 00:06:09,720 and the cleverest of overflows will then return to what this return address used to be. 89 00:06:09,720 --> 00:06:11,970 So even though we needed to override this 90 00:06:11,970 --> 00:06:16,720 to come up here, we still remember that return address somewhere 91 00:06:16,720 --> 00:06:18,890 so that we can return to main or whatever, 92 00:06:18,890 --> 00:06:23,800 and it's like we never even noticed that things went wrong. 93 00:06:23,800 --> 00:06:30,100 But things did so that's the case where maybe inside of here we gelbroke our iPhone. 94 00:06:30,100 --> 00:06:35,670 Things go as normal--like we run some program and things end up returning to 95 00:06:35,670 --> 00:06:38,540 whatever it's supposed to return to, but in the meantime 96 00:06:38,540 --> 00:06:41,820 you managed to destroy the entire operating system. 97 00:06:41,820 --> 00:06:50,950 You don't need to know code concerning buffer overflows or actually taking advantage of it. 98 00:06:50,950 --> 00:06:58,060 You do need to know the basic ideas of this is the buffer that's being overflowed, 99 00:06:58,060 --> 00:07:02,010 and this is the reason that it can be overflowed because we're not checking whether 100 00:07:02,010 --> 00:07:06,110 we're actually within the bounds of it. 101 00:07:06,110 --> 00:07:09,880 >> [Student] The solution for preventing it is just checking the bounds? 102 00:07:09,880 --> 00:07:13,600 [Rob] Yes. In this case the solution would be 103 00:07:13,600 --> 00:07:20,850 you could either say if strlen of bar is greater than 12-1-- 104 00:07:20,850 --> 00:07:24,970 because you need the /0 at the end-- 105 00:07:24,970 --> 00:07:34,090 or you could manually do a for loop that only copies the first 11 characters, 106 00:07:34,090 --> 00:07:39,710 or just anything where you're actually checking to make sure you don't overflow that buffer. 107 00:07:45,580 --> 00:07:49,050 >> Other questions? Yes? 108 00:07:49,050 --> 00:07:52,760 [Student] Can you talk about tries and maybe something about programming (inaudible). 109 00:07:52,760 --> 00:07:58,720 [Rob] Sure. 110 00:07:58,720 --> 00:08:03,500 The actual program-- 111 00:08:03,500 --> 00:08:08,190 we would never make you do an implementation of a trie on the exam 112 00:08:08,190 --> 00:08:12,840 because it would be unfair to those who did hash tables. 113 00:08:12,840 --> 00:08:16,030 And similarly we would never make you implement a hash table on the exam 114 00:08:16,030 --> 00:08:18,560 because it would be unfair to those who did tries. 115 00:08:18,560 --> 00:08:25,220 You should nevertheless know the struct of a trie or the struct of a hash table or whatever. 116 00:08:25,220 --> 00:08:30,230 That's actually true of any sort of data structure we've seen. 117 00:08:30,230 --> 00:08:33,559 Linked lists, stacked skews, binary trees-- 118 00:08:33,559 --> 00:08:38,190 you should be able to define those structs by heart. 119 00:08:38,190 --> 00:08:44,810 A trie--that means the only thing you will need to do is maybe we'll give you 120 00:08:44,810 --> 00:08:50,070 some word or something and we'll say construct the trie that-- 121 00:08:50,070 --> 00:08:52,870 we'll give you maybe a set of words 122 00:08:52,870 --> 00:08:56,280 and we're like construct a trie that represents this dictionary. 123 00:08:56,280 --> 00:09:05,980 >> Let's make our dictionary cat and dog. 124 00:09:05,980 --> 00:09:10,790 The idea of the trie is we start out with this array-- 125 00:09:10,790 --> 00:09:16,510 26 slots-- 126 00:09:16,510 --> 00:09:24,490 and in each slot the actual index of the slot corresponds to the letter we're concerned with. 127 00:09:24,490 --> 00:09:28,560 So here, if we're trying to insert cat into our trie 128 00:09:28,560 --> 00:09:35,360 the first character is 'c' which is going to be 'if a is 0 then b is 1, c is 2.' 129 00:09:35,360 --> 00:09:38,090 We're going to go into the second index, 130 00:09:38,090 --> 00:09:41,100 and we're going to create a trie off of that. 131 00:09:41,100 --> 00:09:47,080 We're going to have 26 slots. 132 00:09:47,080 --> 00:09:51,140 And then we are going to index the second character of cat. 133 00:09:51,140 --> 00:09:53,340 That's 'a' which is going to be the 0 spot. 134 00:09:53,340 --> 00:09:56,960 And that's going to have 26 spots. 135 00:09:56,960 --> 00:10:05,650 Then we go to 't' and we would also have that coming down which is actually kind of important 136 00:10:05,650 --> 00:10:13,990 because--let's have it come up here. Here's our trie for 't'. 137 00:10:13,990 --> 00:10:23,370 Let's say this is index 't' is 19. 138 00:10:23,370 --> 00:10:31,020 The important thing to remember about tries is you can't just keep track of these pointers. 139 00:10:31,020 --> 00:10:35,470 You also have to keep track of whether this is actually the end of a word. 140 00:10:35,470 --> 00:10:38,570 So, inside of here we need some kind of flag that says 141 00:10:38,570 --> 00:10:41,520 okay, this is actually the end of a word. 142 00:10:41,520 --> 00:10:46,830 The reason being if we later try to insert catastrophic into our dictionary 143 00:10:46,830 --> 00:10:49,930 which has the same starting 3 characters 144 00:10:49,930 --> 00:10:57,250 but goes on further we need to recognize that this is the end of a word. 145 00:10:57,250 --> 00:11:01,330 Or alternatively if we try to look up 'ca' which maybe isn't a word 146 00:11:01,330 --> 00:11:06,100 but we get down to here then we-- 147 00:11:06,100 --> 00:11:10,270 or would it be c and then we look at a-- 148 00:11:10,270 --> 00:11:13,940 we need to recognize that even though there's a pointer coming out of this node 149 00:11:13,940 --> 00:11:15,940 it doesn't represent the end of the word. 150 00:11:15,940 --> 00:11:19,430 >> So, what does that mean--what were you going to say? 151 00:11:19,430 --> 00:11:22,760 What does that mean our struct looks like? 152 00:11:22,760 --> 00:11:25,760 [Student] It's an array of pointers that is 26 long and then a bool were or not were. 153 00:11:25,760 --> 00:11:47,430 [Rob] Yeah. So, we'll have a struct trie* pointers--here we'll say [26] on 154 00:11:47,430 --> 00:11:49,590 and then the semicolon over here. 155 00:11:49,590 --> 00:11:53,210 But on the Pset, we also need to account for apostrophes, 156 00:11:53,210 --> 00:11:58,170 which meant you needed to hard-code that apostrophe with index 27 or something. 157 00:11:58,170 --> 00:12:00,440 But here we only care about 26. 158 00:12:00,440 --> 00:12:11,830 And then we need maybe a char in or bool--let's call it is word. 159 00:12:11,830 --> 00:12:18,120 That's 2 of the 3 things I think you would ever need to know about tries-- 160 00:12:18,120 --> 00:12:24,370 building them, the struct of them, and the last thing is the run-time of them. 161 00:12:24,370 --> 00:12:28,250 >> What is the runtime of a trie--or the lookup in a trie? 162 00:12:28,250 --> 00:12:47,500 This is where we say it's o(k) where k is the length of the word we happen to be looking up; 163 00:12:47,500 --> 00:12:53,850 but at the same time we say--at least for Pset 5 speller's sake--we say 164 00:12:53,850 --> 00:12:59,470 the longest word in the dictionary is 45 characters, so this is basically 165 00:12:59,470 --> 00:13:04,900 the O of 45 which is constant time. 166 00:13:04,900 --> 00:13:09,660 So, if there is an upper bound on your longest word then-- 167 00:13:09,660 --> 00:13:15,130 or even like the English dictionary--there is an upper bound on your longest word. 168 00:13:15,130 --> 00:13:19,970 Or any dictionary--there is a longest bound on your upper word. 169 00:13:19,970 --> 00:13:25,480 No matter what you're doing is constant time, 170 00:13:25,480 --> 00:13:33,810 but O of k is nice because there actually is a difference between running say 171 00:13:33,810 --> 00:13:40,120 45-character word versus an alphabet which only has words up to 3 characters. 172 00:13:40,120 --> 00:13:52,870 Another thing about that is that the-- 173 00:13:52,870 --> 00:13:57,520 oh, because just saying that 45 happens to be our longest word 174 00:13:57,520 --> 00:14:02,330 is kind of silly because at the same time let's say an algorithm is O of N. 175 00:14:02,330 --> 00:14:06,510 Well okay, because memory only supports up to 2^32 bytes, 176 00:14:06,510 --> 00:14:11,770 then N is at most 4 billion and that's constant time, which is why at some point 177 00:14:11,770 --> 00:14:14,870 it's silly to say this sort of thing where there's an upper bound 178 00:14:14,870 --> 00:14:19,540 that we can just reduce to constant time because everything is constant time 179 00:14:19,540 --> 00:14:22,320 when you think of it in that way. 180 00:14:22,320 --> 00:14:25,470 But we would probably accept both of these. 181 00:14:25,470 --> 00:14:31,780 In any case explain either that O(1) means you have an upper-bounded length of word; 182 00:14:31,780 --> 00:14:34,070 O(k) means your length of the word-- 183 00:14:34,070 --> 00:14:40,900 well, k means length of the word. 184 00:14:44,060 --> 00:14:47,280 >> Yeah. >>[Student] Does the bool--because when you made your trie 185 00:14:47,280 --> 00:14:53,220 it seemed like it was--you would go c-a-t and then you go to the next pointer 186 00:14:53,220 --> 00:14:59,860 and then you tell if that equals true--would you put that true at like with the t? 187 00:14:59,860 --> 00:15:06,560 [Rob] Let's think this is the case where a lot of examples you can just try and come up with 188 00:15:06,560 --> 00:15:12,310 simple and/or extreme examples and what it should be, so let's think of the word 'a'. 189 00:15:12,310 --> 00:15:21,320 In our original trie-- 190 00:15:21,320 --> 00:15:35,510 would we want to put a 1 here, or we'd want to put a 1 down here. 191 00:15:35,510 --> 00:15:41,350 I would say that in the end it would probably be either/or. 192 00:15:41,350 --> 00:15:46,000 I can't think of a reason--or really you wouldn't-- 193 00:15:46,000 --> 00:15:51,060 the reason I wouldn't put it down there is because you don't even need to go that far. 194 00:15:51,060 --> 00:15:55,820 We never need to allocate this trie. 195 00:15:55,820 --> 00:15:57,950 We just put the 1 up there. 196 00:15:57,950 --> 00:16:03,310 This is still pointing to NULL. 197 00:16:03,310 --> 00:16:09,430 If we're only going to have single characters 198 00:16:09,430 --> 00:16:17,220 there's no reason to extend down to another trie just to mark that letter as used. 199 00:16:17,220 --> 00:16:21,260 Similarly, if we had put the 'a' down there 200 00:16:21,260 --> 00:16:27,860 then necessarily all of these would just be 0 at all times. 201 00:16:27,860 --> 00:16:36,060 >> [Student] But don't we need a starting trie that will point to this 'a'? 202 00:16:36,060 --> 00:16:43,570 [Rob] We have some global or something struct trie* t 203 00:16:43,570 --> 00:16:47,270 which points here, but that's just a pointer. 204 00:16:47,270 --> 00:16:51,500 It's not a full-blown trie that's pointing to it. 205 00:16:51,500 --> 00:17:02,000 [Student] Okay. How would we assign the letter 'i'--with the word I? 206 00:17:02,000 --> 00:17:06,380 [Rob] His question might be answering that. Hold on. 207 00:17:06,380 --> 00:17:15,060 That is an issue where a trie in and of itself-- 208 00:17:15,060 --> 00:17:17,880 I don't know the way the Pset would have written it. 209 00:17:17,880 --> 00:17:19,880 The previous struct was bad. 210 00:17:19,880 --> 00:17:41,690 But we could also do struct node is a bool--and a pointer-- 211 00:17:41,690 --> 00:17:46,500 there's actually multiple ways you could write it. 212 00:17:46,500 --> 00:18:01,800 Alternatively a trie doesn't need to be a struct. 213 00:18:01,800 --> 00:18:21,250 It could even be trie--typedef node*-- 214 00:18:21,250 --> 00:18:34,760 node [26] is a trie; and this is no longer struct. 215 00:18:34,760 --> 00:18:44,270 Now there's going to be--I'm trying to think of the way that Pset would have expected you to. 216 00:18:44,270 --> 00:18:47,650 [Student] I pulled up that review session and I think they just go-- 217 00:18:47,650 --> 00:18:50,670 like if you have an a then you go to the next-- >>[Rob] That's how they do it? 218 00:18:50,670 --> 00:18:53,750 [Student] And then if there's a true there it doesn't work-- 219 00:18:53,750 --> 00:18:58,710 [Rob] Yeah. That does work. It wastes the space of-- 220 00:18:58,710 --> 00:19:03,910 you necessarily have a whole other level of trie that you wouldn't need in the first place. 221 00:19:03,910 --> 00:19:08,410 Here it's getting ugly with each-- 222 00:19:08,410 --> 00:19:11,530 basically what I'm trying to do here is associate-- 223 00:19:11,530 --> 00:19:15,000 instead of being 26 pointers to your tries, 224 00:19:15,000 --> 00:19:20,810 it's 26 bool pointer, bool pointer, bool pointer, and so on. 225 00:19:28,940 --> 00:19:34,410 >> [Student] You can't make that 2 arrays? An array of bools and an array of pointers? 226 00:19:34,410 --> 00:19:38,060 [Rob] You could but then you'd need to-- 227 00:19:38,060 --> 00:19:41,500 2 arrays of booleans and pointers. 228 00:19:41,500 --> 00:19:47,340 You would need to then build your array of booleans-- 229 00:19:47,340 --> 00:19:51,240 your array of booleans needs to be as big as the trie 230 00:19:51,240 --> 00:19:53,200 because you can't just have 26 booleans. 231 00:19:53,200 --> 00:19:57,010 It has to grow with each possible-- 232 00:19:57,010 --> 00:20:03,240 like your trie has more than 26 true or false possible words. 233 00:20:03,240 --> 00:20:08,240 At that point they may as well just be a single struct that your trie grows down with. 234 00:20:08,240 --> 00:20:15,210 This doesn't seem right because--what do I want here? 235 00:20:15,210 --> 00:20:23,640 So, trie* t-- 236 00:20:23,640 --> 00:20:30,200 can you do typedef (node*)[26] trie; 237 00:20:30,200 --> 00:20:33,090 that might be the syntax I'm looking for. 238 00:20:36,740 --> 00:20:41,450 And this should just be a regular trie. 239 00:20:44,900 --> 00:20:47,440 I'm not sure. 240 00:20:47,440 --> 00:20:54,850 But that is the way we did it in the review, so that works perfectly fine, too. 241 00:20:54,850 --> 00:20:57,850 In which case if it is just bool is word and then an array of 26 242 00:20:57,850 --> 00:21:01,750 then you do have to go to the next level. 243 00:21:01,750 --> 00:21:05,420 I'll think about the way I would do that. 244 00:21:07,500 --> 00:21:09,550 >> Other questions? 245 00:21:09,550 --> 00:21:12,540 [Student] Can I ask questions about something else? >>[Rob] Yes. 246 00:21:12,540 --> 00:21:19,040 [Student] Can you go over what the difference is and when you'd use jQuery versus Ajax? 247 00:21:19,040 --> 00:21:24,550 [Rob] They are in and of themselves completely different. 248 00:21:24,550 --> 00:21:32,720 JQuery does enable Ajax. It does give us some easier use of Ajax. 249 00:21:32,720 --> 00:21:38,480 But Ajax comes shipped with JavaScript. JavaScript has Ajax capabilities. 250 00:21:38,480 --> 00:21:47,490 All Ajax means is liken I'm already on a page and when I want to-- 251 00:21:47,490 --> 00:21:52,820 when I click on something I don't need to reload the page to download that new information. 252 00:21:52,820 --> 00:21:55,020 I just request that new information. 253 00:21:55,020 --> 00:22:01,220 You can look at it in Facebook or something. 254 00:22:01,220 --> 00:22:05,580 Inspect network. 255 00:22:05,580 --> 00:22:07,460 Shrink this. 256 00:22:12,070 --> 00:22:14,940 Down here we see that we're getting all these requests. 257 00:22:14,940 --> 00:22:18,990 Now when I click on--well, it's doing Ajax before I even click on anything. 258 00:22:18,990 --> 00:22:24,140 But if I click on this, then it's going to make a bunch of requests down here 259 00:22:24,140 --> 00:22:33,530 which just making these requests--oh, now it's over here. 260 00:22:33,530 --> 00:22:36,590 Let's refresh. 261 00:22:36,590 --> 00:22:38,580 Do this again. 262 00:22:38,580 --> 00:22:42,090 We see that we get all these requests, but this could still be in the process of the page loading. 263 00:22:42,090 --> 00:22:47,400 Notice Facebook is making these constant requests even after the page has loaded. 264 00:22:47,400 --> 00:22:51,470 And if I click on here, it'll make some more requests for some data 265 00:22:51,470 --> 00:22:54,990 that is in response to the thing I just clicked on. 266 00:22:54,990 --> 00:23:04,660 That's just what Ajax is. It lets you pull for data that wasn't downloaded with the page originally. 267 00:23:04,660 --> 00:23:12,050 >> JQuery is separate. JQuery is just a JavaScript library that makes a lot of things easier. 268 00:23:12,050 --> 00:23:28,660 With jQuery it's a lot of the advantage is this just-- 269 00:23:28,660 --> 00:23:34,030 dollar sign--dollar sign is a valid variable in JavaScript. 270 00:23:34,030 --> 00:23:43,460 So, jQuery--all it's doing is saying like var$= a whole bunch of stuff-- 271 00:23:43,460 --> 00:23:46,690 like some big function with all this stuff in it-- 272 00:23:46,690 --> 00:23:52,650 and then you use that dollar sign in ways like 273 00:23:52,650 --> 00:24:23,940 $("#footer").style ("text-align", "center"). 274 00:24:23,940 --> 00:24:32,330 JQuery gives us this sort of syntax where a big advantage-- 275 00:24:32,330 --> 00:24:35,650 it has other features but what we want you to focus on most 276 00:24:35,650 --> 00:24:38,760 is just being able to select elements like this. 277 00:24:38,760 --> 00:24:42,780 In regular, plain-old JavaScript you can do things like 278 00:24:42,780 --> 00:24:50,490 document-dot-get element by ID footer-dot--I don't know what it is at that point-- 279 00:24:50,490 --> 00:24:52,790 something about CSS or style or something-- 280 00:24:52,790 --> 00:24:58,930 but then alternatively, let's say we wanted to select by class. 281 00:24:58,930 --> 00:25:06,330 Now we are styling everything with a class footer with this style. 282 00:25:06,330 --> 00:25:16,070 Even if we wanted to style any paragraphs. 283 00:25:16,070 --> 00:25:22,000 So, this selector--being able to select things in the dom like this is incredibly convenient 284 00:25:22,000 --> 00:25:29,420 since in plain old JavaScript you would have to do document-dot-get elements by class name 285 00:25:29,420 --> 00:25:34,260 or whatever it is; or if I wanted a tag I'd need to say get elements by tag name. 286 00:25:34,260 --> 00:25:37,530 So, I need to know the specific ways that I access all of these things. 287 00:25:37,530 --> 00:25:40,810 The functions are going to be different depending on whether I'm using a class or an ID 288 00:25:40,810 --> 00:25:46,420 or a tag or what, whereas jQuery just does that for me. 289 00:25:46,420 --> 00:25:53,120 >> [Student] Is jQuery going to be used when you're doing initial styling of the page? 290 00:25:53,120 --> 00:25:56,570 Or in order to change the styling after it's already-- >>[Rob] To change it. 291 00:25:56,570 --> 00:25:58,440 [Student] After it's already loaded. >>[Rob] Yeah. 292 00:25:58,440 --> 00:26:07,020 Any initial styling--well, even the-- 293 00:26:07,020 --> 00:26:09,970 generally you would use this sort of change. 294 00:26:09,970 --> 00:26:14,330 You wouldn't change--this would work perfectly fine. 295 00:26:14,330 --> 00:26:17,720 But usually you wouldn't change the style like this. 296 00:26:17,720 --> 00:26:20,610 Instead, you'd give it a new class or something 297 00:26:20,610 --> 00:26:24,650 whereas the CSS has already been defined for that class in a certain way. 298 00:26:24,650 --> 00:26:28,920 By giving these items I'm selecting a new class 299 00:26:28,920 --> 00:26:32,200 I'm applying the styles that have already been downloaded. 300 00:26:32,200 --> 00:26:36,720 [Student] So you select a couple of checkboxes and the things that you've selected 301 00:26:36,720 --> 00:26:41,820 change to a new style and start looking different. >>[Rob] Yeah. 302 00:26:41,820 --> 00:26:45,490 The other things to remember about-- 303 00:26:45,490 --> 00:26:48,350 well, there are several functions you should remember about jQuery. 304 00:26:48,350 --> 00:26:55,570 Let's say that we are selecting something with ID P. 305 00:26:55,570 --> 00:27:00,500 >> [Student] Do you always have to use the pound? 306 00:27:00,500 --> 00:27:09,600 [Rob] This means ID. It's equivalent to CSS, so CSS selectors--it's inspired by that. 307 00:27:09,600 --> 00:27:12,410 Where in CSS if I wanted to style a footer-- 308 00:27:12,410 --> 00:27:16,950 or something with ID footer-- 309 00:27:16,950 --> 00:27:23,490 it would be like text-align: center; 310 00:27:23,490 --> 00:27:28,820 you won't need to write CSS on the exam, but you need to know the selectors. 311 00:27:28,820 --> 00:27:34,280 You need to know what--you need to know how to read it. 312 00:27:34,280 --> 00:27:36,000 But we would never-- 313 00:27:36,000 --> 00:27:42,390 you don't need to memorize all of the different possible styling things. Or any of them. 314 00:27:42,390 --> 00:27:50,020 >> JQuery things you should remember-- 315 00:27:50,020 --> 00:27:58,380 you should remember dot-HTML, and a common pattern in jQuery--let's re-write this. 316 00:27:58,380 --> 00:28:09,640 A common pattern is we have $("#f").html 317 00:28:09,640 --> 00:28:15,650 If I put just plain parentheses that means get the HTML; 318 00:28:15,650 --> 00:28:23,870 whereas if I say HTML and put whatever I want in here--some link to something-- 319 00:28:23,870 --> 00:28:30,410 putting something inside of the parentheses now sets the HTML. 320 00:28:30,410 --> 00:28:33,760 That's pretty common amongst a bunch of functions. 321 00:28:33,760 --> 00:28:38,360 There's the same deal with text. 322 00:28:38,360 --> 00:28:41,720 The difference between HTML and text is that text is going to insert this 323 00:28:41,720 --> 00:28:46,350 as literal less-than a, greater-than instead of as an anchor tag. 324 00:28:46,350 --> 00:28:53,000 And text is going to be the same if I just do this. 325 00:28:53,000 --> 00:28:55,760 It's going to retrieve the text of the document--not the HTML of the document 326 00:28:55,760 --> 00:29:01,810 but just the text within this element. 327 00:29:01,810 --> 00:29:08,430 Another one is if 'f' happens to be an ID for an input, 328 00:29:08,430 --> 00:29:14,250 then hash-f-dot-val--if I want to set the input to something like-- 329 00:29:14,250 --> 00:29:17,900 let's say I hit a checkbox and I want to set a default value-- 330 00:29:17,900 --> 00:29:26,070 dot-val--I don't even know--3--so that will automatically insert into the text box 3, 331 00:29:26,070 --> 00:29:35,980 but if I say 3-dot-val, that will retrieve whatever is currently in the text box for me. 332 00:29:35,980 --> 00:29:39,690 >> This is useful for form validation where 333 00:29:39,690 --> 00:29:48,030 if I just want to make sure that they actually filled out all of the things. 334 00:29:48,030 --> 00:29:54,710 One way of doing that is if after I hit submit it's inevitably sent to some page on the server-- 335 00:29:54,710 --> 00:30:00,190 like for us it would be PHP--and that would try to process the data and it would say 336 00:30:00,190 --> 00:30:03,030 they didn't fill something out, so that now redirects them to another page that says 337 00:30:03,030 --> 00:30:05,050 you didn't fill everything out. 338 00:30:05,050 --> 00:30:11,650 Instead of having to do that, in JavaScript/jQuery you can just see if val is empty. 339 00:30:11,650 --> 00:30:17,270 Or is val--empty quotes. 340 00:30:17,270 --> 00:30:23,120 That's going to just--now we can alert them that you didn't fill out this field. 341 00:30:23,120 --> 00:30:26,990 Inevitably you do need to do the PHP server-side checking because 342 00:30:26,990 --> 00:30:31,210 you can just disable JavaScript in all the browsers. 343 00:30:31,210 --> 00:30:36,180 But JavaScript makes it convenient for those who do have it activated, 344 00:30:36,180 --> 00:30:42,940 and virtually ninety-nine-point-something percent of browsers have it on nowadays. 345 00:30:42,940 --> 00:30:46,630 Very few people turn JavaScript off. 346 00:30:46,630 --> 00:30:52,850 It is a user convenience. You need to do PHP validation. 347 00:30:52,850 --> 00:30:55,990 You should do JavaScript validation. 348 00:30:55,990 --> 00:30:57,950 >> [Student] What does #f refer to here? 349 00:30:57,950 --> 00:31:00,020 [Rob] What does #f refer to? 350 00:31:00,020 --> 00:31:04,350 There is some element in my document with ID 'f'. 351 00:31:04,350 --> 00:31:09,850 We'll look at--probably Facebook has plenty of examples where if I come to elements 352 00:31:09,850 --> 00:31:17,820 looking here under the elements tag I see this particular div that's being highlighted up here-- 353 00:31:17,820 --> 00:31:22,670 or is it the whole page--yeah, it's up there. This has ID pagelet_bluebar. 354 00:31:22,670 --> 00:31:26,730 In console I assume they're using jQuery. 355 00:31:26,730 --> 00:31:40,030 So, I could select pagelet_bluebar so that selects that, and I did something wrong. 356 00:31:46,470 --> 00:31:52,250 Let's try--or maybe they aren't using jQuery and that character's mapped to something else. 357 00:31:52,250 --> 00:32:04,970 A better example in something I know is using jQuery-- 358 00:32:04,970 --> 00:32:10,600 still looking at our elements here--we have here class equals navbar. 359 00:32:10,600 --> 00:32:12,330 This is something with class navbar, 360 00:32:12,330 --> 00:32:19,180 so inside of our console we can look up the thing with class navbar. 361 00:32:19,180 --> 00:32:21,770 Here we can scroll over this and see that's what this is. 362 00:32:21,770 --> 00:32:29,850 If I wanted to do .text this is the text of that, so I see settings for report above log out 363 00:32:29,850 --> 00:32:35,760 which are all under here, but that's still text within that HTML tag. 364 00:32:35,760 --> 00:32:52,230 I could set the HTML to just some link, 365 00:32:52,230 --> 00:32:56,550 so I'll get rid of my bar. Now that got rid of the header entirely just so it's linked to YouTube. 366 00:32:56,550 --> 00:32:59,630 >> And is there any form example? 367 00:32:59,630 --> 00:33:01,940 Here's a form. 368 00:33:01,940 --> 00:33:05,830 I can right-click and inspect element to come to it right here. 369 00:33:05,830 --> 00:33:08,460 I see that its ID is text search, 370 00:33:08,460 --> 00:33:16,910 so down here if I do ID text search. 371 00:33:16,910 --> 00:33:23,190 I'll bring over it and I see that is the correct thing I was searching for. 372 00:33:23,190 --> 00:33:27,670 If I want to do .val it would give me what I had typed there. 373 00:33:27,670 --> 00:33:36,010 If I wanted to do hello it'll change it up here to hello--jQuery. 374 00:33:36,010 --> 00:33:45,780 Of course I could do ridiculous like document.get element by ID--text search-- 375 00:33:45,780 --> 00:33:54,000 I don't even know what it is at this point--dot value--no, I forgot that guy. 376 00:33:54,000 --> 00:33:59,110 So, that's hello. I don't know how I'd set it equals something. 377 00:33:59,110 --> 00:34:00,930 Yeah, so that changed that. 378 00:34:00,930 --> 00:34:07,510 But you don't need to use these and very many websites at this point use jQuery. 379 00:34:07,510 --> 00:34:13,050 Even like on a final project--if you're doing a web project--the first thing 380 00:34:13,050 --> 00:34:20,030 I recommend is just including jQuery so you can get the convenience of all these functions. 381 00:34:22,580 --> 00:34:27,750 >> [Student] I think I saw a different way to get to a element using dom. 382 00:34:27,750 --> 00:34:32,520 Do you have to use dot and then keep going down? 383 00:34:32,520 --> 00:34:36,630 [Rob] You can do that. I don't know if it would work very well. 384 00:34:36,630 --> 00:34:38,900 It's difficult to navigate that way. 385 00:34:38,900 --> 00:34:43,179 One example is--I don't even know if we have any forms-- 386 00:34:43,179 --> 00:34:48,940 but document.forms is going to return the list of forms that's on this page, 387 00:34:48,940 --> 00:34:55,070 then I can do document.forms 0 is going to be the first form. 388 00:34:55,070 --> 00:35:03,070 Dot--I don't know what we've called that--so it doesn't even have a name, 389 00:35:03,070 --> 00:35:08,050 so maybe inputs will work. No. 390 00:35:08,050 --> 00:35:11,050 I don't even know how to get at this--get element-I-tag name input. 391 00:35:11,050 --> 00:35:23,630 Yeah, that gave me the input, and now I want the 0 to input 392 00:35:23,630 --> 00:35:31,320 and I want to select its value, so that's going to be text. 393 00:35:31,320 --> 00:35:33,890 I had to end up doing get elements by tag name anyway. 394 00:35:33,890 --> 00:35:36,210 There might be some way to select it directly 395 00:35:36,210 --> 00:35:43,480 through form 0, but the nice thing about this is still like I only had to get the tags called input 396 00:35:43,480 --> 00:35:49,880 that were a child of this form; otherwise if I just do that straight up front 397 00:35:49,880 --> 00:35:56,680 this would select all elements on the entire page, in the entire document 398 00:35:56,680 --> 00:36:00,580 instead of just that form and it probably won't even be the one I want. 399 00:36:00,580 --> 00:36:06,180 I don't even know which one it is. I don't know. 400 00:36:06,180 --> 00:36:13,450 I guess the first input element on our page is this little checkbox. 401 00:36:13,450 --> 00:36:20,450 >> [Student] This is pretty unrelated 402 00:36:20,450 --> 00:36:27,420 and possibly kind of silly, but on the answer key it says that PHP-- 403 00:36:27,420 --> 00:36:35,660 I don't know whether it's the answer key or notes but it says PHP is server-side 404 00:36:35,660 --> 00:36:39,590 and JavaScript is client-side. What is the difference between the 2? 405 00:36:39,590 --> 00:36:45,550 [Rob] The difference between JavaScript client-side and PHP server-side. 406 00:36:45,550 --> 00:36:51,890 If you have heard of slash/used node js before you would think that 407 00:36:51,890 --> 00:36:56,280 JavaScript isn't just client-side but for CS50 purposes it is-- 408 00:36:56,280 --> 00:36:59,340 or at least for this quiz's purposes it is. 409 00:36:59,340 --> 00:37:03,800 PHP being server-side. No JavaScript. 410 00:37:03,800 --> 00:37:08,700 When you write your webpage you will be writing PHP on the server. 411 00:37:08,700 --> 00:37:11,670 You will never be writing JavaScript on the server. 412 00:37:11,670 --> 00:37:17,190 JavaScript ends up getting sent to the browser where the JavaScript code executes. 413 00:37:17,190 --> 00:37:22,250 And the JavaScript code needs to live in the browser because otherwise when I want to 414 00:37:22,250 --> 00:37:25,830 just do any sort of JavaScript-y thing like clicking on this, 415 00:37:25,830 --> 00:37:31,720 I'm not reloading a page. This is just JavaScript re-formatting things for me. 416 00:37:31,720 --> 00:37:36,490 If JavaScript lived on the server, then I would need to inevitably request something 417 00:37:36,490 --> 00:37:39,490 of the server to know what to do. 418 00:37:39,490 --> 00:37:45,380 PHP--there is no such thing as PHP in the browser. 419 00:37:45,380 --> 00:37:52,090 When I request a page--so let's say here I requested this particular page. 420 00:37:52,090 --> 00:37:57,270 That means that this is going to request-- 421 00:37:57,270 --> 00:38:04,270 refresh--it's going to refresh this page-- 422 00:38:04,270 --> 00:38:07,210 so this request goes out to our server. 423 00:38:07,210 --> 00:38:13,190 It sees that it needs to return this particular thread with this particular ID, 424 00:38:13,190 --> 00:38:23,740 so now that's going to be some PHP that the PHP interpreter is going to interpret that page 425 00:38:23,740 --> 00:38:28,680 and transform it into just HTML, CSS, maybe JavaScript, whatever. 426 00:38:28,680 --> 00:38:36,930 It's PHP that processes this request and retrieves all of the text and stuff 427 00:38:36,930 --> 00:38:39,170 that I'm actually looking for from the database. 428 00:38:39,170 --> 00:38:44,750 But what leaves the server is just HTML/JS/CSS. 429 00:38:44,750 --> 00:38:48,630 There's no PHP which leaves the server because if it actually did 430 00:38:48,630 --> 00:38:53,890 then the browser would have no idea what to do with it because it doesn't know what PHP is. 431 00:38:53,890 --> 00:39:00,250 But in the same thought because JavaScript is client-side, 432 00:39:00,250 --> 00:39:02,250 you can never access MySQL from it. 433 00:39:02,250 --> 00:39:07,430 Because PHP is server-side you do access MySQL from it. 434 00:39:07,430 --> 00:39:12,880 >> [Student] Can you go over some of the security concerns with cookies in HTTP? 435 00:39:12,880 --> 00:39:18,390 [Rob] Those are not things we're going to need to know. 436 00:39:18,390 --> 00:39:24,500 Some of the security concerns with cookies in HTTP. 437 00:39:24,500 --> 00:39:28,550 The big question here is we see here that my cookie is PHP/ID. 438 00:39:28,550 --> 00:39:33,560 That's like the universal PHP your session. 439 00:39:33,560 --> 00:39:39,550 Your session is something that inside of PHP will never need to be validated 440 00:39:39,550 --> 00:39:45,690 because it's the server that has complete control over the session. 441 00:39:45,690 --> 00:39:47,690 You can't touch it at all. 442 00:39:47,690 --> 00:39:53,120 But it's this cookie--this one-- 443 00:39:53,120 --> 00:39:57,500 and I guess you could log in as me right now if you wanted to use that-- 444 00:39:57,500 --> 00:40:06,610 but it's that cookie that the--inevitably you make a single request to the server. 445 00:40:06,610 --> 00:40:09,890 The server returns the page. The request is done. 446 00:40:09,890 --> 00:40:12,580 It no longer has any idea who you are. 447 00:40:12,580 --> 00:40:17,230 So, the next request you make is going to include that cookie so that it knows 448 00:40:17,230 --> 00:40:19,810 this is the person who made this request before. 449 00:40:19,810 --> 00:40:23,830 This is the session data that is associated with this user. 450 00:40:23,830 --> 00:40:28,210 That's why you don't have to log in for each and every page you use. 451 00:40:28,210 --> 00:40:33,380 The security issue here is that that cookie is sent out over the web. 452 00:40:33,380 --> 00:40:41,490 We're using HTTPS here, so in this case that means that we are encrypting this stuff. 453 00:40:41,490 --> 00:40:49,870 Someone can't come in and just steal my cookie and now the server will think they're me. 454 00:40:49,870 --> 00:40:52,060 But with straight HTTP they can. 455 00:40:52,060 --> 00:40:57,650 Just like this WireShark/FireSheep stuff that you can just listen to all of the wi-fis in the air 456 00:40:57,650 --> 00:41:01,380 and intercept whatever you want, so yeah. 457 00:41:01,380 --> 00:41:12,430 >> [Student] A sort of similar security risk is storing user ID's in post 458 00:41:12,430 --> 00:41:16,860 because that can be freely edited using consoles and things. 459 00:41:16,860 --> 00:41:23,410 [Rob] Yes. There's plenty of issues where like just anything that comes from the user 460 00:41:23,410 --> 00:41:26,940 you need to validate. 461 00:41:26,940 --> 00:41:37,650 There are plenty of cases where it would be useful for like I'm about to make a post. 462 00:41:37,650 --> 00:41:39,650 Blah, blah, blah, blah, blah. Then I hit reply. 463 00:41:39,650 --> 00:41:44,540 It would be very useful if the post request included my ID because 464 00:41:44,540 --> 00:41:48,610 I want to associate this post with me. 465 00:41:48,610 --> 00:41:54,820 But I can't do that because I am free to make a post request--just like manually 466 00:41:54,820 --> 00:41:57,820 come up with my own post request-- 467 00:41:57,820 --> 00:42:00,960 that uses your user ID and now it will post as you. 468 00:42:00,960 --> 00:42:07,440 That's why server-side I can't rely on post requests containing the correct user ID. 469 00:42:07,440 --> 00:42:09,720 That's why it has to belong in my session. 470 00:42:09,720 --> 00:42:15,140 So I look up your user ID in my session array and I insert that into my database 471 00:42:15,140 --> 00:42:17,580 as the user who actually made this post. 472 00:42:17,580 --> 00:42:19,580 [Student] And that's based on your cookie? 473 00:42:19,580 --> 00:42:24,690 [Rob] Yeah. It uses the cookie to match up you as the user who made that request. 474 00:42:24,690 --> 00:42:30,570 It pulls out the user ID from that session and that then inserts into the database 475 00:42:30,570 --> 00:42:32,960 using that user ID. 476 00:42:32,960 --> 00:42:40,330 This like button--what that's actually doing is-- 477 00:42:40,330 --> 00:42:43,810 I'm not going to find it here. It's going to be an Ajax function 478 00:42:43,810 --> 00:42:46,780 What is Ajax function? 479 00:42:46,780 --> 00:42:55,500 Let me find out what my JavaScript is. 480 00:42:55,500 --> 00:42:59,710 It was a CS50 project a while ago. 481 00:42:59,710 --> 00:43:02,880 I can't remember what it is. 482 00:43:02,880 --> 00:43:12,530 Ajax function--all Ajax function is doing is making an Ajax request to a page with this ID-- 483 00:43:12,530 --> 00:43:15,810 with the ID 22453. 484 00:43:15,810 --> 00:43:20,180 It's not even a post request. It's a get request which makes it even easier. 485 00:43:20,180 --> 00:43:27,860 If I knew what the URL is--it's something like like this/ID=22453-- 486 00:43:27,860 --> 00:43:33,290 or ?ID=22453-- 487 00:43:33,290 --> 00:43:40,290 so visiting this URL will like that. 488 00:43:40,290 --> 00:43:44,600 Which wouldn't be as much of a problem but it's incredibly easy to write a loop 489 00:43:44,600 --> 00:43:48,500 which is just going to visit this URL over and over again, which is why you see 490 00:43:48,500 --> 00:43:51,180 Isawyouharvard post with thousands of things. 491 00:43:51,180 --> 00:43:56,960 And they tend to be CS50-based Isawyouharvard posts. 492 00:43:56,960 --> 00:44:01,200 How do I find the most-liked? 493 00:44:01,200 --> 00:44:03,720 They tend to get deleted pretty quickly, too. 494 00:44:03,720 --> 00:44:06,490 This is not the most-liked. There we go. 495 00:44:06,490 --> 00:44:13,400 Cheaters on the most liked page--that's pretty relevant to this right now. 496 00:44:13,400 --> 00:44:21,230 Oh wow. They've already deleted any of the ones from this year which have been 497 00:44:21,230 --> 00:44:25,590 cheated on. Those have all been deleted. 498 00:44:25,590 --> 00:44:28,680 There will never be a post that gets this high. 499 00:44:28,680 --> 00:44:32,860 This one was obviously cheated on to get on to the most liked page. 500 00:44:36,570 --> 00:44:39,310 >> More questions? 501 00:44:39,310 --> 00:44:46,050 [Student] What should we know about XHTML? 502 00:44:46,050 --> 00:44:49,710 [Rob] Virtually nothing. Just what it is. 503 00:44:49,710 --> 00:44:59,220 The difference between it and HTML being that XML is very similar in appearance 504 00:44:59,220 --> 00:45:09,080 to HTML except in HTML we just have to have a predefined set of tags. 505 00:45:09,080 --> 00:45:15,380 But with XML--XML is just like a general format where you can make an XML document 506 00:45:15,380 --> 00:45:17,580 for whatever purposes you want. 507 00:45:17,580 --> 00:45:25,950 So, for example, if I wanted I could construct an XML for the courses-- 508 00:45:25,950 --> 00:45:28,860 and I actually think that CS50 has an API for this. 509 00:45:28,860 --> 00:45:31,590 My XML document could look something like-- 510 00:45:31,590 --> 00:45:39,330 courses and of course I need some end courses. 511 00:45:39,330 --> 00:45:48,920 I could have a course and it could have name equals CS50. 512 00:45:48,920 --> 00:45:58,080 And then my end course and I could put inside of here students, 513 00:45:58,080 --> 00:46:07,010 and then inside of students I have a list of one student whose name is whatever. 514 00:46:07,010 --> 00:46:10,180 I end that student and so on. 515 00:46:10,180 --> 00:46:16,070 I just happen to have constructed some arbitrary XML document, but it is valid XML. 516 00:46:16,070 --> 00:46:23,700 XML--all it is is this sort of structure and the nice thing--the reason that we even call it XML 517 00:46:23,700 --> 00:46:26,820 is that this sort of thing is very easy to parse. 518 00:46:26,820 --> 00:46:32,580 It's very easy to take this document and make an array out of it. 519 00:46:32,580 --> 00:46:39,370 And so XHTML is an attempt to get HTML to be valid XML. 520 00:46:39,370 --> 00:46:42,580 Already this looks pretty similar to HTML. 521 00:46:42,580 --> 00:46:52,160 Some of the differences are HTML you are able to do things like input maybe type equals text 522 00:46:52,160 --> 00:46:55,550 which is the default so I don't need to say that. 523 00:46:55,550 --> 00:47:00,010 Disabled. 524 00:47:00,010 --> 00:47:05,160 >> There are 2 things in here that make this invalid XHTML. 525 00:47:05,160 --> 00:47:08,750 The first thing is that all XML tags need a closing tag. 526 00:47:08,750 --> 00:47:13,040 So in the case of input I need to do the--which direction of slash is it? 527 00:47:13,040 --> 00:47:15,060 This direction? That looks wrong. 528 00:47:15,060 --> 00:47:19,380 Other direction. 529 00:47:19,380 --> 00:47:21,960 Self-closing tag. 530 00:47:21,960 --> 00:47:29,560 The second thing is that with XML you need these sorts of like key value pairs. 531 00:47:29,560 --> 00:47:32,130 It needs a value associated with it. 532 00:47:32,130 --> 00:47:35,050 So, even though disabled in and of itself expresses what I want-- 533 00:47:35,050 --> 00:47:37,110 this input should be disabled-- 534 00:47:37,110 --> 00:47:39,110 that's invalid XHTML. 535 00:47:39,110 --> 00:47:47,110 What I actually need to write is disabled equals disabled. 536 00:47:47,110 --> 00:47:49,620 Now it's valid XHTML. 537 00:47:49,620 --> 00:47:54,850 And these are just these slight differences that transform HTML to an XML-based sort of thing. 538 00:47:54,850 --> 00:48:04,880 >> [Student] XML is about like pull through your own X altogether like why is it (inaudible) 539 00:48:04,880 --> 00:48:19,450 [Rob] The thing of like a CSV--a CSV you have just values separated by-- 540 00:48:19,450 --> 00:48:23,550 just think of a spreadsheet. A CSV is basically a spreadsheet. 541 00:48:23,550 --> 00:48:26,720 You have maybe columns and you have a bunch of rows that 542 00:48:26,720 --> 00:48:29,600 associate data with those columns but that's it. 543 00:48:29,600 --> 00:48:38,310 XML is much more versatile in that you can--you have an arbitrary hierarchy of data. 544 00:48:38,310 --> 00:48:43,200 I could have multiple courses that have multiple students within it 545 00:48:43,200 --> 00:48:45,460 where it would be difficult to think of a spreadsheet that-- 546 00:48:45,460 --> 00:48:51,010 just that single spreadsheet--CSV especially is like just a single spreadsheet-- 547 00:48:51,010 --> 00:48:58,760 so that single spreadsheet having all CS50, 51, and 61 and within those all of the 548 00:48:58,760 --> 00:49:03,230 students related to those times, maybe meeting times and all of that sort of thing. 549 00:49:03,230 --> 00:49:09,140 The other thing is that the tag names give a nice name to all of the elements 550 00:49:09,140 --> 00:49:13,140 so reading a CSV file can be difficult to try and parse what it's actually seeing. 551 00:49:13,140 --> 00:49:20,130 XML is much more human-readable so that's why like--come up to some person who doesn't 552 00:49:20,130 --> 00:49:26,380 really know what a CSV file is or like isn't a programmer or something-- 553 00:49:26,380 --> 00:49:30,640 you can give them like a template XML file and they can follow the lines and-- 554 00:49:30,640 --> 00:49:33,590 oh, I'm supposed to insert my name here. 555 00:49:33,590 --> 00:49:37,440 It's a much more usable format. 556 00:49:37,440 --> 00:49:42,440 CSV has plenty of uses but XML has different uses. 557 00:49:46,050 --> 00:49:49,680 >> More questions? 558 00:49:49,680 --> 00:49:51,900 Other questions? 559 00:49:56,410 --> 00:50:00,520 [Student] From the previous quiz--vertical scaling versus horizontal scaling. 560 00:50:00,520 --> 00:50:04,660 [Rob] You would not need to know that. I don't think we even discussed that. 561 00:50:04,660 --> 00:50:07,340 I'm guessing it was just a one-off comment. 562 00:50:07,340 --> 00:50:12,660 Oh. Horizontal versus vertical scaling is not something you'll need to know. 563 00:50:12,660 --> 00:50:18,570 I think the difference is just like--oh well, the answer key will say the difference. 564 00:50:18,570 --> 00:50:26,030 Vertical scaling is just like oh, my computer's doing poorly. I'll get a better one. 565 00:50:26,030 --> 00:50:29,150 Whereas horizontal scaling is oh, my computer is doing poorly-- 566 00:50:29,150 --> 00:50:33,360 let me get 20 of them to all work on the same task. 567 00:50:40,300 --> 00:50:45,520 >> [Student] Can we go over the linked list way of making queues. >>[Rob] Sure. 568 00:50:45,520 --> 00:50:50,000 That's easier than the array way. 569 00:50:50,000 --> 00:50:53,140 The linked list way of making queues. 570 00:50:53,140 --> 00:50:58,350 First, what does our struct for a linked list look like? 571 00:50:58,350 --> 00:51:17,060 [Student] Are we doing it for-- >>[Rob] Let's do its--yeah. 572 00:51:17,060 --> 00:51:30,000 Int val; then struct node* next; 573 00:51:30,000 --> 00:51:34,560 so that's what we'll use for the example here. 574 00:51:34,560 --> 00:51:37,660 Let's actually type up this stuff. 575 00:51:40,030 --> 00:51:49,600 Let's do linked_list. 576 00:51:51,750 --> 00:51:53,750 Our struct-- 577 00:52:05,360 --> 00:52:13,060 Okay. Now looking at our queue we have the-- 578 00:52:13,060 --> 00:52:16,090 let's just make a global queue. 579 00:52:16,090 --> 00:52:23,130 It'll be node* queue; and we have a dequeue function. 580 00:52:23,130 --> 00:52:28,330 I guess these things could also overturn true or false--let's do that. 581 00:52:28,330 --> 00:52:38,690 Bool dequeue--and we're dequeueing--oh. Hmm. 582 00:52:38,690 --> 00:52:45,200 Int dequeue--what did we do with this before? 583 00:52:45,200 --> 00:52:54,340 Int dequeue and we have bool enqueue and we need to enqueue some means true. 584 00:52:54,340 --> 00:53:01,360 Let's do enqueue first. 585 00:53:01,360 --> 00:53:06,520 We have our queue. We want to insert something into the queue. 586 00:53:06,520 --> 00:53:12,720 What is the best way to do that? 587 00:53:12,720 --> 00:53:20,270 Over here our queue currently looks like we have some global pointer to start. 588 00:53:20,270 --> 00:53:24,910 There's our queue. 589 00:53:24,910 --> 00:53:30,350 Assuming that we dequeue by taking the first element, 590 00:53:30,350 --> 00:53:36,570 where are we going to want to insert our node so that queues work as they should? 591 00:53:36,570 --> 00:53:43,440 [Student] At the very end. >>[Rob] Yeah. Queues are supposed to be first in, first out. 592 00:53:43,440 --> 00:53:48,030 Which means that the new element should be inserted over here. Okay. 593 00:53:48,030 --> 00:53:53,220 >> Coming back to code, 594 00:53:53,220 --> 00:53:59,760 that means that we will want to loop over our queue. 595 00:53:59,760 --> 00:54:10,210 Let's do node* current = queue; while current does not equal NULL. 596 00:54:10,210 --> 00:54:16,960 I would do--all right, let's do it separately. 597 00:54:16,960 --> 00:54:20,460 First, current = queue. 598 00:54:20,460 --> 00:54:24,660 What do we do if current starts off as NULL? 599 00:54:24,660 --> 00:54:28,410 We'll do this 2 ways. First this way. 600 00:54:28,410 --> 00:54:31,450 What do we do if current is NULL? 601 00:54:31,450 --> 00:54:34,850 Is this equivalent to if queue is NULL? 602 00:54:38,550 --> 00:54:43,960 [Student] It's going to return false. >>[Rob] Should we return false? 603 00:54:43,960 --> 00:54:47,120 What's wrong with inserting something into an empty list? 604 00:54:47,120 --> 00:54:49,080 [Student] Nothing is wrong with that. Sorry. 605 00:54:49,080 --> 00:54:55,980 [Rob] Yeah. So here the only difference is my global queue is being sent to my new node. 606 00:54:57,840 --> 00:55:02,880 And then I have to do my checks of if queue is NULL. 607 00:55:02,880 --> 00:55:05,960 Return false. 608 00:55:05,960 --> 00:55:20,910 And then queue val equals i; queue next equals NULL; return true. 609 00:55:20,910 --> 00:55:25,890 Okay. I'm going to jump the gun right here. 610 00:55:25,890 --> 00:55:29,570 Remember what we did that last time 611 00:55:29,570 --> 00:55:35,660 where we said it was much easier to work with node** with this sort of thing. 612 00:55:35,660 --> 00:55:43,880 So now current is going to be &queue, and coming down to here-- 613 00:55:43,880 --> 00:55:53,010 while current--while *current does not equal NULL-- 614 00:55:53,010 --> 00:55:58,230 so let me just do current--we'll talk about this in a second. 615 00:55:58,230 --> 00:56:00,860 Current next. Okay. 616 00:56:00,860 --> 00:56:12,910 Looking at it in this way, this is iterating over all of my pointers until I reach a null pointer. 617 00:56:12,910 --> 00:56:17,710 The null pointer is going to be the pointer I want to replace with my new node. 618 00:56:17,710 --> 00:56:21,910 Looking at iPad version-- 619 00:56:21,910 --> 00:56:27,800 if my original pointer and the linked list is empty then current is going to point here. 620 00:56:27,800 --> 00:56:29,630 This is going to point to null, 621 00:56:29,630 --> 00:56:34,440 so this is the pointer I end up moving to point to some other new node. 622 00:56:34,440 --> 00:56:38,150 Whereas if the example is this case up here 623 00:56:38,150 --> 00:56:42,720 then current is going to traverse from here--I messed up slightly. 624 00:56:42,720 --> 00:56:50,700 Where current is supposed to be the address of current next. 625 00:56:50,700 --> 00:57:00,200 Is that what I want? Current so *current gives me a node. 626 00:57:00,200 --> 00:57:04,440 Next traverses to the next one. 627 00:57:04,440 --> 00:57:10,700 I'm currently pointing here. 628 00:57:10,700 --> 00:57:13,720 Let's do red--so I'm currently pointing here. 629 00:57:13,720 --> 00:57:19,710 Then *current is going to reference this node. 630 00:57:19,710 --> 00:57:25,080 And *current next references this node, but that's not what I want. 631 00:57:25,080 --> 00:57:27,700 I want this pointer to that node. 632 00:57:27,700 --> 00:57:40,530 So, that pointer to this node is ampersand (*current) next. 633 00:57:47,660 --> 00:57:54,360 >> At this point in time I've officially reached the node that I want to replace. 634 00:57:54,360 --> 00:58:13,770 Let's replace all of these queues current--and now we're done. 635 00:58:13,770 --> 00:58:21,760 There may be typos, but the idea is that with insert in this sort of way 636 00:58:21,760 --> 00:58:28,130 it is easier to work with the pointers that we want to change 637 00:58:28,130 --> 00:58:32,780 instead of needing to keep track of--okay, is my start NULL? 638 00:58:32,780 --> 00:58:36,430 Oh it is? Then I need to create the start node to be something specific 639 00:58:36,430 --> 00:58:40,310 else I'll want to iterate until the next thing I point to is NULL, 640 00:58:40,310 --> 00:58:46,740 and then I'll replace that--what the next thing is--to my malloc node. 641 00:58:46,740 --> 00:58:50,740 Instead of needing to separate those cases, here I only deal with the case of 642 00:58:50,740 --> 00:58:54,990 what is the pointer that is NULL that I no longer want to be NULL, 643 00:58:54,990 --> 00:59:01,820 and that makes life easier except these should all be *current now because-- 644 00:59:01,820 --> 00:59:05,460 [Student] Are they still the size of a node? 645 00:59:05,460 --> 00:59:10,480 [Rob] Yes. I'm still mallocing a node. 646 00:59:10,480 --> 00:59:12,980 [Student] Is it going to be the size of a node*? 647 00:59:12,980 --> 00:59:20,990 [Rob] Coming back to here, think of the case if this is our linked list. 648 00:59:28,330 --> 00:59:33,190 This guy points off to NULL. 649 00:59:33,190 --> 00:59:36,950 After that why loop, current points to here 650 00:59:36,950 --> 00:59:41,510 because this is the pointer that is NULL. 651 00:59:41,510 --> 00:59:50,380 Now I want to change this pointer to point to a new node. 652 00:59:50,380 --> 00:59:58,390 First I malloc that new node--so malloc size of node. 653 00:59:58,390 --> 01:00:11,070 And that returns a node* and now changing this pointer is building to *current equals 654 01:00:11,070 --> 01:00:15,780 this new node that I allocated. 655 01:00:15,780 --> 01:00:26,490 So, if current is a node**, then *current is going to be a node*, 656 01:00:26,490 --> 01:00:32,540 and if I'm mallocing something the size of node then this is returning a pointer to a node 657 01:00:32,540 --> 01:00:39,630 so this is a node*--so both sides correctly have the same type. 658 01:00:39,630 --> 01:00:46,610 And so if what I just allocated was NULL, return false; 659 01:00:46,610 --> 01:00:54,750 else finish setting them to what I want them to be--except these need parentheses 660 01:00:54,750 --> 01:00:57,730 because that's not how the order of things work. 661 01:00:57,730 --> 01:00:59,690 Without the parentheses that was being interpreted as 662 01:00:59,690 --> 01:01:03,010 current-arrow-val dereference that. 663 01:01:03,010 --> 01:01:07,010 Instead I want to dereference current which brings me to a node. 664 01:01:07,010 --> 01:01:10,620 Then I want to get the value associated with that node. 665 01:01:10,620 --> 01:01:17,670 >> [Student] I thought arrows allowed you to bypass that and go straight to the value. 666 01:01:17,670 --> 01:01:22,640 [Rob] They do. That's if I have--let's say queue is an example. 667 01:01:22,640 --> 01:01:28,400 I'm allowed to do queue-arrow-val equals i because queue is a node*. 668 01:01:28,400 --> 01:01:39,160 If there were some nice syntax of like current-longer arrow-val or something 669 01:01:39,160 --> 01:01:42,540 which did 2 dereferences, then this would work well. 670 01:01:42,540 --> 01:01:44,790 [Student] So the arrow is only for 1 dereference. >>[Rob] Yeah. 671 01:01:44,790 --> 01:01:53,590 Alternatively I could write this as (**current.val). 672 01:01:53,590 --> 01:02:02,490 Just like I could also write queue as (*queue).val. 673 01:02:04,430 --> 01:02:09,250 So let's insert. Well, that's in queue I guess. 674 01:02:09,250 --> 01:02:12,030 Dequeue is going to be significantly shorter. 675 01:02:12,030 --> 01:02:18,280 Let's put void in here for cleanliness. 676 01:02:18,280 --> 01:02:22,820 So, dequeue. What element am I dequeueing? 677 01:02:22,820 --> 01:02:24,820 [Student] The first one? >>[Rob] Yeah. 678 01:02:24,820 --> 01:02:32,880 If my first one is NULL--return--I don't know what we want to return--INT_MAX; 679 01:02:32,880 --> 01:02:37,580 and then you should do a check to see if INT_MAX was returned. 680 01:02:37,580 --> 01:02:44,090 That's the sort of thing that get inc does else we want to-- 681 01:02:44,090 --> 01:02:54,610 can we just return queue val? Is that what we want to do? 682 01:02:54,610 --> 01:02:58,010 Dequeue also implicitly removes the item from the queue, 683 01:02:58,010 --> 01:03:10,840 so let's first say--let's get a tmp to point to the first node of our queue. 684 01:03:10,840 --> 01:03:15,510 Now we want to advance our queue to point to the next thing in the queue. 685 01:03:15,510 --> 01:03:21,450 Now we have tmp left. Tmp val is the thing we want to return. 686 01:03:21,450 --> 01:03:24,180 So, val = tmp->val; 687 01:03:24,180 --> 01:03:31,190 but before we return it we should free tmp and return val. 688 01:03:31,190 --> 01:03:36,350 The order of operations here is important in that we need to grab a tmp 689 01:03:36,350 --> 01:03:40,520 before we move queue to the next element. 690 01:03:40,520 --> 01:03:44,860 We need to get the value before we free tmp, 691 01:03:44,860 --> 01:03:48,710 and then we can return the val. 692 01:03:48,710 --> 01:03:50,680 >> [Student] Should we set the queue to queue next? 693 01:03:50,680 --> 01:03:57,800 [Rob] Yes. That was creating a bad loop/it wouldn't work after freeing it anyway. 694 01:03:57,800 --> 01:03:59,900 Queue = queue->next. 695 01:03:59,900 --> 01:04:03,230 We want to advance the queue into the next element not advance the next element 696 01:04:03,230 --> 01:04:08,170 to what the element currently is. 697 01:04:08,170 --> 01:04:17,660 Stacks would be significantly--like even easier in that dequeue is exactly the same 698 01:04:17,660 --> 01:04:20,190 because we're pulling off the front of the stack. 699 01:04:20,190 --> 01:04:24,030 End queue would be very similar where we just want to allocate a node 700 01:04:24,030 --> 01:04:27,670 and insert into the front of the stack, so we don't even need to loop over anything. 701 01:04:27,670 --> 01:04:31,420 We just insert directly at the front. 702 01:04:42,500 --> 01:04:44,640 Is everyone good on that? 703 01:04:44,640 --> 01:04:49,760 >> Okay. More questions? 704 01:04:49,760 --> 01:04:56,570 [Student] What major things should I keep in mind from the most recent lecture? 705 01:04:56,570 --> 01:04:58,730 [Rob] The most recent lecture. 706 01:04:58,730 --> 01:05:01,620 You do not need to know any code. 707 01:05:01,620 --> 01:05:07,590 You should know the overarching ideas. 708 01:05:07,590 --> 01:05:11,650 Nate's half didn't have any code and so those slides are online. 709 01:05:11,650 --> 01:05:15,220 They're just like look at them and they have the major ideas. 710 01:05:15,220 --> 01:05:28,630 My half--knowing the overall idea of first you can't trust anything. 711 01:05:28,630 --> 01:05:38,070 The fact that like maybe the process of the compiler can be bad, 712 01:05:38,070 --> 01:05:40,870 but it doesn't even matter that the source code looks fine. 713 01:05:40,870 --> 01:05:46,390 Because the compiler might be specifically altered to change the source code 714 01:05:46,390 --> 01:05:50,860 in the process of compiling. 715 01:05:50,860 --> 01:05:58,140 At the same time just like--I think those are like the major ideas of it. 716 01:05:59,560 --> 01:06:09,030 >> [Student] Did you mention that we don't need to know anything related to Firesheep-- 717 01:06:09,030 --> 01:06:13,110 or do we need to know that? 718 01:06:13,110 --> 01:06:18,360 [Rob] With Nate's half of things, anything that Nate touched on-- 719 01:06:18,360 --> 01:06:22,760 like FireSheep, WireShark--I don't even think he did Firesheep in detail. 720 01:06:22,760 --> 01:06:28,620 You also did something with that--was it Firesheep--last week? 721 01:06:28,620 --> 01:06:31,110 Did you touch on that? 722 01:06:31,110 --> 01:06:34,060 [Student] Yeah, I think we might have-- >>[Rob] Yeah. 723 01:06:34,060 --> 01:06:40,880 We're not going to give you Firesheep output and say interpret this. 724 01:06:40,880 --> 01:06:44,960 It's just going to be--it would be a question like what is Firesheep? 725 01:06:44,960 --> 01:06:47,290 What is it used for? 726 01:06:47,290 --> 01:06:52,120 [Student] I think it only works on version 4 of Firefox or something. 727 01:06:52,120 --> 01:06:55,320 [Rob] It might be broken by now. 728 01:07:11,430 --> 01:07:14,070 I have no idea. 729 01:07:14,070 --> 01:07:18,330 They don't seem to have disabled it manually, 730 01:07:18,330 --> 01:07:21,210 but maybe it doesn't work with the most recent Firefox. 731 01:07:21,210 --> 01:07:24,790 [Student] I actually tried installing it because it said it would be compatible. 732 01:07:24,790 --> 01:07:28,880 [Rob] So, I guess it doesn't work with the most recent Firefox. 733 01:07:28,880 --> 01:07:32,360 But the idea still stands of what it was meant to show. 734 01:07:32,360 --> 01:07:39,430 It was absurd how much of the world was not living in HTTPS at the time. 735 01:07:39,430 --> 01:07:43,820 Even in the last 2 years or whatever, it's still--there's dramatic improvement in the 736 01:07:43,820 --> 01:07:47,210 number of websites which use HTTPS. 737 01:07:49,920 --> 01:07:52,580 >> [Student] Do we need to go over HTTP? 738 01:07:52,580 --> 01:07:58,050 [Rob] The protocol of it? >>[Student] Some of the things that we should know. 739 01:07:58,050 --> 01:08:06,220 [Rob] All right. Basic things are everything you can see in your network tab. 740 01:08:06,220 --> 01:08:12,160 When I request a page--coming back up to the top for the main things. 741 01:08:12,160 --> 01:08:16,090 You can see here the request that I make. 742 01:08:16,090 --> 01:08:19,220 Chrome happens to format it all nicely for us 743 01:08:19,220 --> 01:08:21,970 where the request URL was this, the request method was GET, 744 01:08:21,970 --> 01:08:24,800 and the status code was 200 OK. 745 01:08:24,800 --> 01:08:28,279 If I hit view source, I see more directly that-- 746 01:08:28,279 --> 01:08:35,680 and this is--we could show you either of these, but it isn't too difficult to interpret between them. 747 01:08:35,680 --> 01:08:41,729 Here is the direct request I made, so this means that I went to 748 01:08:41,729 --> 01:08:48,160 apps.cs50.net/discuss/threads/inbox/all/HTTP/1.1. 749 01:08:48,160 --> 01:08:57,569 And the protocol it used was HTTP/1.1 which is virtually--it's always going to be that. 750 01:08:57,569 --> 01:09:01,490 Over here we used GET, so this might also be POST. 751 01:09:01,490 --> 01:09:04,660 And then coming down--all the way down to response headers--if we view that source, 752 01:09:04,660 --> 01:09:07,740 it's where we see the 200 OK. 753 01:09:07,740 --> 01:09:11,069 Know the possible different status codes of these. 754 01:09:11,069 --> 01:09:15,520 I think in the review we do say a couple of these, 755 01:09:15,520 --> 01:09:20,640 so 403, 404--those kind of common ones. 756 01:09:20,640 --> 01:09:26,810 That's the major idea of it. 757 01:09:29,990 --> 01:09:35,120 The difference just between HTTP and HTTPS is this encryption. 758 01:09:35,120 --> 01:09:42,319 >> [Student] Are you done? >>[Rob] I think so. Well, yep. 759 01:09:42,319 --> 01:09:46,470 [Student] Will you talk very generally about how encryption works? 760 01:09:46,470 --> 01:09:49,920 Because we talked for example when compressing Huffman files, 761 01:09:49,920 --> 01:09:54,890 you know how to decompress them because you actually sent the hashtable within the file 762 01:09:54,890 --> 01:09:56,950 so how does encryption work? 763 01:09:56,950 --> 01:10:00,830 How do you know how to encrypt information if you haven't actually sent the client 764 01:10:00,830 --> 01:10:05,740 the key to the--and you can actually grab that key from--? 765 01:10:05,740 --> 01:10:07,740 How does the general process work? 766 01:10:07,740 --> 01:10:09,870 [Rob] The general process of encryption-- 767 01:10:09,870 --> 01:10:15,590 that is an incredibly detailed question I will answer. 768 01:10:15,590 --> 01:10:21,490 There is a short--well, Tommy and I made the short. 769 01:10:21,490 --> 01:10:26,060 Unfortunately it is like 26 minutes, so it is not a short. It is a long. 770 01:10:26,060 --> 01:10:31,530 But our short was on RSA which is just one example of these, 771 01:10:31,530 --> 01:10:40,420 and this RSA is part of the overall HTTPS protocol. 772 01:10:40,420 --> 01:10:46,060 The idea--RSA is an example of public key cryptography, 773 01:10:46,060 --> 01:10:49,690 which means you have 2 separate keys. 774 01:10:49,690 --> 01:10:51,690 You use 1 key to actually encrypt things, 775 01:10:51,690 --> 01:10:54,410 and you use another key to decrypt things. 776 01:10:54,410 --> 01:10:58,360 This key that you use to encrypt things is the one that's public. 777 01:10:58,360 --> 01:11:03,500 The website can send you this encryption key. 778 01:11:03,500 --> 01:11:08,280 They do send you that encryption key, and when you want to send something back to them 779 01:11:08,280 --> 01:11:13,550 you use that encryption key to encrypt all of your data and send it to them. 780 01:11:13,550 --> 01:11:16,110 So, they are the only ones with the private key. 781 01:11:16,110 --> 01:11:22,630 If that private key became known then anyone would be able to decrypt your data. 782 01:11:22,630 --> 01:11:27,980 But that private key--which is mathematically related to the public key but you cannot 783 01:11:27,980 --> 01:11:33,640 figure one out from the other--so that private key can be used to decrypt the data. 784 01:11:33,640 --> 01:11:36,630 Since they are the only ones with the private key, 785 01:11:36,630 --> 01:11:38,920 they're the only ones who can read the data. 786 01:11:38,920 --> 01:11:44,170 So even though the public key is public, 787 01:11:44,170 --> 01:11:47,660 I use the same--when I go to Google.com or whatever, 788 01:11:47,660 --> 01:11:50,010 they might have multiple, I don't know--but if I go to Google.com, 789 01:11:50,010 --> 01:11:54,770 he goes to Google.com, she goes to Google.com-- 790 01:11:54,770 --> 01:11:59,250 we all can use the same public key to encrypt our own information however we want. 791 01:11:59,250 --> 01:12:04,010 But none of us are going to be able to figure out--are going to be able to decrypt 792 01:12:04,010 --> 01:12:09,940 to their information because the public key isn't able to decrypt. 793 01:12:09,940 --> 01:12:13,050 It can only encrypt. 794 01:12:13,050 --> 01:12:23,250 And it's fun/detailed math of--like a bunch of module operators and exponentials and stuff, 795 01:12:23,250 --> 01:12:28,890 that it just works out that the private key is the only thing that can 796 01:12:28,890 --> 01:12:33,620 decrypt the public key's encryption stuff. 797 01:12:33,620 --> 01:12:38,020 Yeah. See the RSA short for more details. 798 01:12:38,020 --> 01:12:41,880 [Student] Is that on the website? 799 01:12:41,880 --> 01:12:46,210 [Rob] Yeah, I think it is at this point. Or at least a YouTube link to it was posted. 800 01:12:51,330 --> 01:12:57,190 Let's see. Shorts. I think it would have been week 2-related. Yeah. RSA. 801 01:12:57,190 --> 01:13:03,780 And it is--we're not going to play this--24 minutes. 802 01:13:03,780 --> 01:13:05,780 It's a long one. 803 01:13:07,740 --> 01:13:09,740 >> More questions? 804 01:13:09,740 --> 01:13:14,770 [Student] Could you talk briefly about the bitmasks? >>[Rob] Sure. 805 01:13:14,770 --> 01:13:23,090 Briefly, the idea is just that like-- >>[Student] What is it, Rob? 806 01:13:23,090 --> 01:13:32,760 [Rob] Bitmasks. The idea is--let's just say we have some--we're using some integer-- 807 01:13:32,760 --> 01:13:41,490 int x--so, we start it off at 0. 808 01:13:41,490 --> 01:13:47,900 Now, this integer is 32 bits, so any single 1 of those bits can be used to represent 809 01:13:47,900 --> 01:13:50,600 a specific FLAC. 810 01:13:50,600 --> 01:13:56,210 This is where if you look at operating system codes, they use this all over the place 811 01:13:56,210 --> 01:14:03,900 where maybe up top somewhere they hash-define-- 812 01:14:03,900 --> 01:14:09,020 Let's see some examples. 813 01:14:09,020 --> 01:14:22,720 Man-2-open--the open-system call we can see here that one of its arguments is int flags-- 814 01:14:22,720 --> 01:14:29,120 what it expects as that argument are some of these flags. 815 01:14:29,120 --> 01:14:33,030 We see O_append, O_ASYNC, O_CLOEXEC, 816 01:14:33,030 --> 01:14:37,130 O_CREAT, and so on. 817 01:14:37,130 --> 01:14:45,260 O_DIRECT. These sorts of flags are hash-defined somewhere. 818 01:14:45,260 --> 01:14:47,260 And all of them are exactly 1 bit. 819 01:14:47,260 --> 01:14:57,600 So, O_CREAT might be hash-defined as 1, left-shift, 4 (1<<4). 820 01:14:57,600 --> 01:15:02,280 That's going to be the--whenever I use O_CREAT that's just going to be-- 821 01:15:02,280 --> 01:15:09,350 in binary 1, 0, 0, 0, and 30-ish zeros before it. 822 01:15:09,350 --> 01:15:13,930 It's only a single bit a set, and that bit represents this flag. 823 01:15:13,930 --> 01:15:18,160 And so no other flag is going to be left-shifted by 4. 824 01:15:18,160 --> 01:15:30,390 I'm able to represent up to 32 flags in a single integer by doing-- 825 01:15:30,390 --> 01:15:40,850 x = O_CREAT bit wise or O_DIRECT. 826 01:15:40,850 --> 01:15:43,640 You're just picking any 2 of those flags. 827 01:15:43,640 --> 01:15:48,600 Now x is going to have 2 bits set which correspond to the 2 bits 828 01:15:48,600 --> 01:15:53,490 of O_CREAT and O_DIRECT. 829 01:15:53,490 --> 01:15:58,740 The way that then--so then we passed x into the open function, 830 01:15:58,740 --> 01:16:02,950 and open needs to see what flags were actually set. 831 01:16:02,950 --> 01:16:06,480 So, that's where it's going to do things like 832 01:16:06,480 --> 01:16:19,340 if (x & O_CREAT) do something, 833 01:16:19,340 --> 01:16:27,110 or if ( x & O_DIRECT) do something else, 834 01:16:27,110 --> 01:16:30,300 and then there may be some flag that we didn't have set-- 835 01:16:30,300 --> 01:16:35,730 if (x & O_--I don't know what the other flags were-- 836 01:16:35,730 --> 01:16:42,140 (x & O_RDONLY)--that particular condition is not going to be executed. 837 01:16:42,140 --> 01:16:44,030 Or that block of code is not going to be executed, 838 01:16:44,030 --> 01:16:48,030 but these 2 are because those 2 flags were set. 839 01:16:48,030 --> 01:16:57,400 And notice that in C, any value that is not 0 is true. 840 01:16:57,400 --> 01:17:05,020 So, (x & O_CREAT) will be either 0 or O_CREAT 841 01:17:05,020 --> 01:17:07,990 because O_CREAT only has a single bit set. 842 01:17:07,990 --> 01:17:12,800 If that bit is set next, then this is going to return O_CREAT-- 843 01:17:12,800 --> 01:17:16,640 the binary where just that bit is set. 844 01:17:16,640 --> 01:17:23,400 If that bit next is not set, then it's going to return 0, in which case we know the flag was not set. 845 01:17:23,400 --> 01:17:25,400 That's how you use bitmasks. 846 01:17:25,400 --> 01:17:29,050 I think on a previous exam or maybe in class or something-- 847 01:17:29,050 --> 01:17:35,150 you can also use bitmasks to print out the binary of a variable. 848 01:17:35,150 --> 01:17:46,250 So I can use--looping over--1, left-shift, 0--and then print if x & that-- 849 01:17:46,250 --> 01:17:52,570 if x & 1, left shift, 0--then print a 0 or 1. Or print a 1 else print a 0. 850 01:17:52,570 --> 01:18:00,620 And then I go over once more--if x & 1, left-shift, 2--then that means that the second bit 851 01:18:00,620 --> 01:18:04,450 of the variable is set, so I print a 1 else I print a 0. 852 01:18:04,450 --> 01:18:06,860 And I think we might actually want to do that in the reverse order because 853 01:18:06,860 --> 01:18:10,120 usually you want the left side to be the highest-order bits 854 01:18:10,120 --> 01:18:24,510 and the right side to be the lowest-order bits, so it would probably loop 4 int i = 31 until I hit 0, 855 01:18:24,510 --> 01:18:32,320 then do that exact condition--if x & 1, left-shift, i; print 1 else 0. 856 01:18:32,320 --> 01:18:34,320 [Student] Thank you. 857 01:18:36,280 --> 01:18:38,550 >> [Rob] I think we're out of time. 858 01:18:38,550 --> 01:18:42,840 Any more questions in the last couple of out-of-time seconds? 859 01:18:42,840 --> 01:18:47,710 All right. Good luck tomorrow. 860 01:18:47,710 --> 01:18:54,780 This was the last section where next week's going to be optional. 861 01:18:54,780 --> 01:19:03,770 I'll give back quizzes and we can go over them and maybe go over other things that 862 01:19:03,770 --> 01:19:09,230 you were interested in, or final project things, or future CS classes things or--I don't know. 863 01:19:09,230 --> 01:19:12,070 But this is the last material-filled section. 864 01:19:12,070 --> 01:19:15,070 Bye! 865 01:19:15,070 --> 01:19:20,970 (applause) 866 01:19:22,250 --> 01:19:24,420 >> [CS50.TV]