[Powered by Google Translate] [Vecka 5]
[David J. Malan - Harvard University]
[Detta är CS50. - CS50.TV]
>> Detta är CS50, vecka 5.
Idag och denna vecka presenterar vi en liten bit av världen av kriminalteknik
inom ramen av problemet Set 4.
Idag blir en förkortad föreläsning eftersom det finns en särskild händelse här efteråt.
Så vi tar en titt och retas både elever och föräldrar i dag
med några av de saker som är på horisonten.
>> Bland dem, som i måndag, kommer du att ha några fler klasskamrater.
EDX, Harvard och MIT: s nya online-initiativ för OpenCourseWare och mer,
lanserar på Harvards campus på måndag, vilket innebär kommit måndag
du kommer att ha, från och med senaste räkningen, 86.000 nya klasskamrater
som kommer att följa tillsammans med CS50 föreläsningar och sektioner
och genomgångar och sätter problem.
Och som en del av detta kommer du att bli medlemmar i det inledande klass CS50 och nu CS50x.
Som en del av detta nu, inser att det kommer att finnas några upsides också.
Att göra sig redo för det här, för det massiva antalet studenter,
det räcker med att säga att även om vi har 108 TFS och CAS,
det är inte riktigt den bästa elev-lärare förhållandet när vi slog 80.000 av eleverna.
Vi kommer inte att klassificera så många problem sätter manuellt,
så introducerade denna vecka i problemet som kommer att vara CS50 Check,
som kommer att bli en kommandoradsverktyg i apparaten
att du får när du uppdaterar det senare i helgen.
Du kommer att kunna köra ett kommando, check50, på din egen pset,
och du får omedelbar feedback om huruvida programmet är rätt eller fel
enligt olika design specifikationer som vi tillhandahåller.
Mer om detta i problemet inställda specifikationen.
De CS50x klasskamrater kommer att använda detta.
>> Problem Set 4 handlar om kriminalteknik,
och denna pset var verkligen inspirerad av några verkliga saker
varigenom när jag var i forskarskolan jag internerades ett tag
med Middlesex län åklagare kontor gör kriminaltekniska arbetet
med deras bly kriminaltekniska utredare.
Vad detta innebar, eftersom jag tror att jag nämnde ett par veckor tidigare,
är massan statspolisen eller andra skulle komma in,
de skulle släppa av saker som hårddiskar och CD-skivor och disketter och liknande,
och därefter mål kriminalteknik kontoret var att fastställa
om det fanns eller inte var bevis av något slag.
Detta var den särskilda utredningar enhet, så det var ekonomisk brottslighet.
Det var mer oroande slags brott, något som innebär någon form av digitala medier.
Det visar sig att inte så många människor skriver ett e-postmeddelande att säga "jag gjorde det."
Så ofta, har dessa kriminaltekniska sökningar Höj inte så mycket frukt,
men ibland folk skulle skriva sådana meddelanden.
Så ibland var de ansträngningar belönas.
>> Men att leda fram till detta kriminaltekniska pset kommer vi att introducera i pset4 lite grafik.
Du tar förmodligen dessa saker för givet - JPEG, GIF och liknande - i dessa dagar.
Men om du verkligen tänker på det, en bild, ungefär som Rob ansikte,
skulle kunna utformas som en sekvens av punkter eller pixlar.
I fallet av Rob ansikte, det finns alla möjliga färger,
och vi började se de enskilda punkter, annars känd som pixlar,
när vi började att zooma in
Men om vi förenklar världen lite och bara säga att detta här är Rob i svart och vitt,
att representera svart och vitt, kan vi använda bara binärt.
Och om vi ska använda binära, 1 eller 0, kan vi uttrycka samma bild
av Rob leende ansikte med detta mönster av bitar.
11000011 representerar vitt, vitt, svart, svart, svart, svart, vit, vit.
Och så är det inte ett stort steg att sedan börja tala om färgglada fotografier,
saker som du skulle se på Facebook eller ta med en digitalkamera.
Men säkert när det kommer till färger, behöver du fler bitar.
Och ganska vanligt i världen av fotografier är att inte använda 1-bitars färg,
eftersom detta antyder, men 24-bitars färg, där du faktiskt få miljontals färger.
Så som i fallet när vi zoomat in på Rob öga,
Det var ett antal miljoner olika färgglada möjligheter.
Så vi ska införa detta i problembild 4 samt i genomgången,
som kommer att vara idag på 3:30 istället för den vanliga 2:30 på grund av fredagens föreläsning här.
Men video kommer att vara online som vanligt imorgon.
>> Vi kommer också att introducera dig till ett annat filformat.
Detta är avsiktligt tänkt att se hotfull först,
men detta är bara några underlag för en C struct.
Det visar sig att Microsoft år sedan hjälpte popularisera detta format
kallas bitmapp filformat, bmp, och detta var en super enkel, färgglad grafisk filformat
som användes under ganska lång tid och ibland fortfarande för tapeter på stationära datorer.
Om du tänker tillbaka på Windows XP och de rullande kullarna och den blå himlen,
Det var oftast en bmp eller bitmappsbild.
Bitmappar är roligt för oss eftersom de har lite mer komplexitet.
Det är inte riktigt så enkelt som detta nät av 0 och 1.
Istället har du saker som en rubrik i början av en fil.
Så med andra ord, inne i en. Bmp-fil är en hel massa av 0 och 1,
men det finns några ytterligare 0 och 1 där.
Och det visar sig att det vi förmodligen har tagit för givet år -
filformat som. doc eller. xls eller. mp3,. mp4 oavsett filformat
att du är bekant med - vad innebär det även att vara ett filformat,
eftersom i slutet av dagen alla dessa filer använder vi bara har 0 och 1.
Och kanske de 0 och 1 representerar ABC genom ASCII eller liknande,
men i slutet av dagen, det är fortfarande bara 0 och 1.
Så människor bara ibland väljer att uppfinna ett nytt filformat
där de standardisera vilka mönster av bitar i praktiken kommer att innebära.
Och i detta fall här, folk som ritade bitmap-format
sade att den allra första byten i en bitmappsfil som betecknas med offset 0 där,
det kommer att vara några kryptiskt namn variabel kallad bfType,
som bara står för bitmap filtyp, vilken typ av bitmap-fil är det.
Du kan sluta kanske från den andra raden som offset 2, byte nummer 2,
har ett mönster av 0 och 1 som representerar vad? Storleken på något.
Och det fortsätter därifrån.
Så i problembild 4, kommer du att gått igenom några av dessa saker.
Vi kommer inte att sluta bry sig om dem alla.
Men märker det börjar bli intressant runt byte 54: rgbtBlue, Grön och Röd.
Om du någonsin hört förkortningen RGB - röd, grön, blå - detta är en referens till den
eftersom det visar sig att du kan måla alla regnbågens färger
med en kombination av rött och blått och grönt.
Och i själva verket kan föräldrarna i rummet erinra om några av de tidigaste projektorer.
Dessa dagar, ser du bara en ljus som kommer ut ur en lins,
men tillbaka i dag du hade röd lins, blå lins, och den gröna linsen,
och tillsammans syftar till en skärm och bildade en färgstark bild.
Och ganska ofta skulle mellersta skolor och gymnasier har dessa linser
någonsin så lite snett, så du var typ att se dubbla eller tredubbla bilder.
Men det var tanken. Du hade rött och grönt och blått ljus måla en bild.
Och att samma princip används i datorer.
>> Så bland de utmaningar då för dig i problembild 4 kommer att vara ett par saker.
En är att faktiskt ändra storlek på en bild, för att ta i ett mönster av 0 och 1,
reda på vilka bitar av 0 och 1 representerar vad i en struktur som denna,
och sedan räkna ut hur att replikera pixlar - de röda, de blå, de gröna -
inne så att när en bild ser ut så här från början,
kan det se ut så här i stället efter det.
Bland andra utmaningar också kommer att vara att du kommer att överlämnas en rättsmedicinsk bild
av en verklig fil från en digitalkamera.
Och på den kameran, en gång i tiden var en massa bilder.
Problemet är att vi raderas av misstag eller hade bilden skadad på något sätt.
Dåliga saker händer med digitalkameror.
Och så vi kopierade snabbt alla 0 och 1 bort av det kortet för dig,
räddade dem alla i en stor fil, och sedan kommer vi lämna dem till dig i problembild 4
så att du kan skriva ett program i C som man kan återvinna alla dessa JPEG, helst.
Och det visar sig att JPEG, även om de är något av en komplex filformat -
de är mycket mer komplex än så leende ansikte här -
det visar sig att alla JPEG börjar med samma mönster av 0 och 1.
Så använder i slutändan en while-slinga eller en for-slinga eller liknande,
Du kan iterera över alla 0 och 1 i detta kriminaltekniska bild,
och varje gång du ser den speciella mönster som är definierat i problemet inställda specifikation,
Du kan anta här är, med mycket hög sannolikhet, början på en JPEG.
Och så fort du hittar samma mönster visst antal byte
eller kilobyte eller megabyte senare kan du anta här är en andra JPEG,
bilden jag tog efter den första.
Låt mig sluta läsa den första filen, börja skriva den nya en,
och utgången av ditt program för pset4 kommer att bli så många som 50 JPEG-bilder.
Och om det inte är 50 JPEG-bilder, du har en bit av en slinga.
Om du har ett oändligt antal JPEG, har du en oändlig loop.
Så att även kommer att vara ganska vanligt fall.
Så det är vad som finns på horisonten.
>> Quiz 0 bakom oss, inser per min e-post som alltid finns folk som är både glad,
slags neutral och ledsen runt frågesport 0 tid.
Och ska du nå ut till mig, huvudet TF Zamyla, din egen TF,
eller en av de certifikatutfärdare som du vet om du vill diskutera hur det gick.
>> Så för att imponera på föräldrarna här i rummet, vad är det CS50 biblioteket?
[Skratt] Bra jobbat.
Vad är det CS50 biblioteket? Ja. >> [Elev] Det är en redan skrivna uppsättning kod [ohörbart]
Okej, bra.
Det är en redan skrivna uppsättning kod som vi personalen skrev ger vi dig,
som ger vissa gemensamma funktioner,
sånt får mig en sträng, ge mig en int - alla de funktioner som är listade här.
>> Från och med nu börjar vi verkligen ta dessa stödhjul av.
Vi kommer att börja ta bort en sträng från dig,
vilket minns var bara en synonym för vad den faktiska datatypen? >> [Flera studenter] Char *.
Char *. För föräldrar, det var förmodligen [gör whooshing ljud]. Det är bra.
Char * vi börja se på skärmen desto mer när vi tar bort sträng från vårt ordförråd,
åtminstone när det gäller att faktiskt skriva kod.
Likaså kommer vi sluta använda en del av dessa funktioner så mycket
eftersom våra program kommer att få mer sofistikerade.
Snarare än att bara skriva program som sitter där med en snabb blinkande,
väntar på användaren att skriva något i, får du dina insatser från andra håll.
Till exempel får du dem från en rad bitar på den lokala hårddisken.
Du kommer istället få dem i framtiden från en nätverksanslutning,
någon hemsida någonstans.
>> Så låt oss dra tillbaka detta lager för första gången och dra upp CS50 Appliance
och denna fil som heter cs50.h, som du har varit # även för veckor,
men låt oss faktiskt se vad som finns inuti denna.
Den övre delen av filen i blått är bara en massa kommentarer:
garantiinformation och licensiering.
Detta är en slags gemensam paradigm i programvara
eftersom en massa program dessa dagar är vad som kallas öppen källkod,
vilket innebär att någon har skrivit koden och gjort den fritt tillgänglig
inte bara att köra och att använda men att faktiskt läsa och ändra och integrera i ditt eget arbete.
Så det är vad du har använt, öppen källkod, om än i en mycket liten form.
Om jag bläddra ner förbi kommentarer, men vi börjar se lite mer bekanta saker.
Meddelande upptill här att cs50.h filen innehåller en hel del header-filer.
De flesta av dessa, har vi inte sett förut, men en är bekant.
Vilka av dessa har vi sett, om än kortfattat, hittills? >> [Elev] Standard bibliotek.
Ja, standard bibliotek. stdlib.h har malloc.
När vi började prata om dynamisk minnesallokering,
som vi ska återkomma till nästa vecka också, började vi även den filen.
Det visar sig att bool och sant och falskt egentligen inte existerar i C i sig
om du inte inkludera denna fil här.
Vi har i flera veckor varit bland stdbool.h
så att du kan använda begreppet bool, sant eller falskt.
Utan detta, skulle du behöva sortera av falska den och använda en int
och bara godtyckligt anta att 0 är falsk och 1 är sant.
Om vi ​​rulla ner ytterligare, här är vår definition av en sträng.
Det visar sig, som vi har sagt tidigare, att där denna stjärna är egentligen inte spelar någon roll.
Du kan även få utrymme runt.
Vi här terminen har varit att främja det som detta för att göra klart
att stjärnan har att göra med den typ
men inser lika vanligt, om inte lite vanligare,
är att lägga den där, men funktionellt är det samma sak.
Men nu när vi läser ned ytterligare, låt oss ta en titt på getInt
eftersom vi använde det kanske först före allt annat här terminen.
Här är getInt. Detta är vad? >> [Elev] En prototyp. >> Det här är bara en prototyp.
Ofta har vi lagt prototyper på toppen av vår. C-filer,
men du kan också lägga prototyper i header-filer,. h-filer, som den här här
så att när du skriver vissa funktioner som du vill att andra ska kunna använda,
vilket är precis fallet med CS50 biblioteket,
du inte bara genomföra dina uppgifter i något liknande cs50.c,
du sätter också prototyperna inte på toppen av den filen, men på toppen av en huvudfil.
Då header-fil är det som vänner och kollegor har
med # include i sin egen kod.
Så hela den här tiden, du har även alla dessa prototyper,
effektivt på toppen av din fil men genom detta är # mekanism,
som i huvudsak kopior och pastor filen till din egen.
Här är några ganska detaljerad dokumentation.
Vi har ganska mycket tas för givet att getInt får en int,
men det visar sig att det finns vissa hörn fall.
Vad händer om användaren skriver in ett nummer som är alldeles för stor, en kvintiljon,
som bara inte får plats inuti en int? Vad är det förväntade beteendet?
Helst är det förutsägbart.
Så i det här fallet, om du läser faktiskt det finstilta,
du faktiskt se att om linjen inte kan läsas, detta returer INT_MAX.
Vi har aldrig pratat om det här, men baserat på dess kapitalisering, vad är det förmodligen?
[Elev] En konstant. >> Det är en konstant.
Det är några speciella konstant som troligen uttalade i en av dessa header-filer
Det är upp högre i filen och INT_MAX är förmodligen något i stil med cirka 2 miljarder kronor,
Tanken är att eftersom vi måste på något sätt betyda att något gick fel,
Vi, ja, har 4 miljarder siffror till vårt förfogande: -2 miljarder upp till 2 miljarder, ge eller ta.
Nå, vad är vanligt i programmering är du stjäla bara en av dessa siffror,
kanske 0, kanske 2 miljarder, kanske -2.000 miljoner,
så du spenderar en av dina möjliga värden så att du kan engagera sig i världen
att om något går fel, jag återkommer denna super stort värde.
Men du vill inte att användaren skriver något kryptiskt som 234 ..., en riktigt stor siffra.
Man generalisera det istället som en konstant.
Så egentligen, om du är analsex de senaste veckorna, när som helst du ringde getInt,
du borde ha kontroll med om villkor gjorde användartyp i INT_MAX,
eller, mer specifikt, gjorde getInt retur INT_MAX, för om den gjorde det,
det betyder egentligen de inte skriva in det. Något gick fel i det här fallet.
Så detta är vad som allmänt är känt som en vaktpost värde, vilket betyder bara speciell.
>> Låt oss nu övergå till den. C. filen.
C-filen har funnits i apparaten under en längre tid.
Och i själva verket har apparaten den förkompilerade för dig in i det som vi kallade objektkod,
men det bara inte roll för dig om det är på grund av att systemet vet
i detta fall där det är: apparaten.
Låt oss rulla ner nu getInt och se hur getInt har arbetat hela tiden.
Här har vi har liknande kommentarer från tidigare.
Låt mig zooma in på bara koden delen.
Och vad vi har för getInt är följande.
Det tar ingen ingång.
Den returnerar en int, medan (sant), så vi har en medveten oändlig slinga,
men förmodligen kommer vi bryta detta på något sätt eller returnera inifrån detta.
>> Låt oss se hur det fungerar.
Vi verkar använda GetString i denna första raden innanför slingan, 166.
Detta är nu god praxis för under vilka omständigheter skulle GetString tillbaka
den speciella sökord NULL? >> [Elev] Om något går fel.
Om något går fel. Och vad kan gå fel när du ringer något liknande GetString?
Ja. >> [Elev] malloc inte ge den Ints.
Ja. Kanske malloc misslyckas.
Någonstans under huven, är GetString ringer malloc, som fördelar minne,
som låter datorbutik alla tecken
att användare skriver i tangentbordet.
Och antar att användaren hade en hel del ledig tid och skrev mer, till exempel,
än 2 miljarder tecken i, fler tecken än datorn har även RAM.
GetString måste kunna beteckna det till dig.
Även om detta är en super, super ovanligt hörn fall,
det måste på något sätt kunna hantera detta,
och så getString, om vi gick tillbaka och läsa dess dokumentation, faktiskt tillbaka NULL.
Så nu om GetString misslyckas genom att returnera NULL är getInt kommer att misslyckas genom att returnera INT_MAX
precis som en vaktpost. Dessa är bara mänskliga konventioner.
Det enda sättet du skulle veta detta är fallet är att läsa dokumentationen.
>> Låt oss bläddra ner till där int faktiskt fått.
Om jag scrolla ner en bit i linje 170, har vi en kommentar ovanför dessa rader.
Vi förklarar i 172 en int, n, och en röding, c och sedan denna nya funktion,
som vissa av er har snubblat över tidigare, sscanf.
Detta står för sträng scanf.
Med andra ord, ge mig en sträng och jag kommer att söka det för bitar av information av intresse.
Vad betyder det?
Antag att jag skriver i, bokstavligen, 123 på tangentbordet och sedan trycka Enter.
Vad är datatypen för 123 när returneras av GetString? >> [Elev] Sträng.
Det är naturligtvis en sträng, eller hur? Jag fick en sträng.
Så 123 är egentligen citat-unquote, 123 med \ 0 i slutet av den.
Det är inte en int. Det är inte ett nummer. Det ser ut som ett nummer men det är faktiskt inte.
Så vad har getInt att göra?
Den måste avsöka strängen vänster till höger - 123 \ 0 - och på något sätt omvandlas till en faktisk heltal.
Du kan räkna ut hur man gör detta.
Om du tänker tillbaka på pset2, du förmodligen lite bekväm med Caesar
eller Vigenère, så att du kan iterera över en sträng kan du konvertera tecken vare sin.
Men heck, det är en hel del arbete.
Varför inte kalla en funktion som sscanf som gör det åt dig?
Så sscanf förväntar ett argument - i detta fall kallas linje, vilket är en sträng.
Du anger sedan i citat, mycket likt printf, vad du förväntar dig att se i denna sträng.
Och vad jag säger här är jag förväntar mig att se ett decimaltal och kanske ett tecken.
Och vi kommer att se varför detta är fallet på bara ett ögonblick.
Och det visar sig att denna notation nu påminner om saker vi började prata om
drygt en vecka sedan.
Vad är & n och & c gör för oss här? >> [Elev] adress n och adress c..
Ja. Det ger mig adressen till n och adress c.. Varför är det viktigt?
Du vet att med funktioner i C, kan du alltid returnera ett värde eller inget värde alls.
Du kan returnera en int, en sträng, en flottör, en röding, oavsett, eller så kan du gå tillbaka ogiltig,
men du kan bara returnera en sak maximalt.
Men här vill vi sscanf tillbaka mig kanske en int, ett decimaltal,
och även en röding, och jag ska förklara varför röding i ett ögonblick.
Du vill effektivt sscanf tillbaka två saker, men det är bara inte möjligt i C.
Du kan lösa det genom att i två adresser
eftersom så snart du lämnar en funktion två adresser,
vad kan denna funktion göra med dem? >> [Elev] Skriv till dessa adresser.
Den kan skriva till dessa adresser.
Du kan använda stjärnan drift och dit, till var och en av dessa adresser.
Det är typ av denna bakdörren mekanism men mycket vanligt att ändra värdena på variabler
mer än bara en plats - i det här fallet, två.
Nu märker jag söker efter == 1 och sedan återvänder n om det betyder i själva verket utvärderas till sant.
Så vad händer om? Tekniskt sett är allt vi verkligen vill ska hända i getInt detta.
Vi vill tolka, så att säga, vi vill läsa strängen - citat-unquote 123 -
och om det ser ut som det finns ett antal där, vad vi säger sscanf att göra
läggs det numret - 123 - i denna variabel n för mig.
Så varför då hade jag faktiskt detta också?
Vilken roll sscanf säger du också kan få en karaktär här?
[Ohörbart elev svar] >> En decimalpunkt faktiskt skulle kunna fungera.
Låt oss hålla det trodde för ett ögonblick. Vad mer?
[Elev] Det kan vara NULL. >> Bra tanke. Det kan vara noll karaktär.
Det är faktiskt inte i detta fall. Ja. >> [Elev] ASCII.
ASCII. Eller låt mig generalisera ytterligare.
Den% c finns bara för felkontroll.
Vi vill inte att det skall finnas ett tecken efter numret,
men vad detta tillåter mig att göra är följande.
Det visar sig att sscanf, förutom att lagra värden i N och C i detta exempel här,
vad det också gör det returnerar antalet variabler det sätta värden i.
Så om du bara skriva in 123, då endast% d går att matcha,
och endast n får lagras med ett värde som 123,
och ingenting får placeras i C.
C är ett skräp värde, så att säga -
sopor eftersom det aldrig har varit initieras till något värde.
Så i detta fall återvänder sscanf 1 eftersom jag befolkade 1 av dessa pekare,
i vilket fall bra, jag har en int så jag frigöra linjen för att frigöra minne
att GetString tilldelade faktiskt, och sedan jag återvänder n,
annars om du någonsin undrat var som Retry uttalande kommer från, det kommer från höger här.
Så om däremot skriver jag 123foo - bara några slumpmässig sekvens av text -
sscanf kommer att se, antal, nummer, f,
och det kommer att sätta 123 i N, det kommer att sätta fi c och sedan återvända 2.
Så vi har bara använda den grundläggande definitionen av sscanf beteende, ett mycket enkelt sätt -
bra, komplex vid första anblicken, men i slutet av dagen ganska enkel mekanism -
att säga finns det en int och i så fall är att det enda som jag hittade?
Och blanksteg här är avsiktligt.
Om du läser dokumentationen för sscanf, säger det dig att om du inkluderar en bit av blanktecken
vid början eller slutet, sscanf också kan användaren, av någon anledning,
att slå 123 mellanslagstangenten och som kommer att vara legitim.
Du kommer inte skrika på användaren bara för att de drabbade mellanslag
vid början eller slutet, vilket är lite mer användarvänligt.
>> Eventuella frågor sedan på getInt? Ja. >> [Elev] Vad händer om du bara sätta i en röding?
Bra fråga.
Vad händer om du bara skrivit in en röding som f och tryck på Enter utan att någonsin skriva 123?
Vad tror du beteendet hos denna kodrad då vara?
[Ohörbart elev svar]
Ja, så sscanf kan täcka det också eftersom i det fallet, det kommer inte att fylla N-eller C.
Det kommer att i stället återvända 0, i vilket fall jag också fånga det scenariot
eftersom det förväntade värdet jag vill ha är 1.
Jag vill bara en och endast en sak som skall fyllas. Bra fråga.
>> Andra? Okej.
>> Låt oss inte gå igenom alla funktioner i här,
men en som verkar vara kanske av kvarvarande intresse GetString
eftersom det visar sig att getFloat, getInt, GetDouble, GetLongLong
alla punt mycket av sin funktionalitet till GetString.
Så låt oss ta en titt på hur han implementeras här.
Den här ser lite komplicerat, men det använder samma grundläggande
att vi började prata om förra veckan.
I GetString tar som inget argument enligt tomrummet här uppe
och den returnerar en sträng, jag tydligen är att förklara en sträng som heter buffert.
Jag vet inte riktigt vad det kommer att användas för än, men vi får se.
Det ser ut som kapaciteten är som standard 0.
Inte helt säker på var detta kommer, inte säker på vad n ska användas för ännu,
men nu det blir lite mer intressant.
I linje 243, deklarerar vi en int, c.
Detta är en slags dum detalj.
En röding är 8 bitar och 8 bitar kan lagra hur många olika värden? >> [Elev] 256. >> 256.
Problemet är om du vill ha 256 olika ASCII-tecken, där det finns
Om du tänker tillbaka - och detta är inte något att memorera.
Men om du tänker tillbaka på den stora ASCII diagram vi hade veckor sedan,
fanns i så fall 128 eller 256 ASCII-tecken.
Vi använde alla mönster 0 och 1 upp.
Det är ett problem om du vill kunna upptäcka ett fel
för om du redan använder 256 värden för dina karaktärer,
du inte riktigt planera i förväg eftersom du nu har ingen möjlighet att säga,
Detta är inte en äkta karaktär, är detta något felaktigt meddelande.
Så vad världen gör är att de använder den näst största värdet, något som en int,
så att du har en galen antal bitar, 32, för 4 miljarder möjliga värden
så att du enkelt kan sluta med i huvudsak 257 av dem,
1 av som har några speciella betydelse som ett fel.
>> Så låt oss se hur det fungerar.
I linje 246, har jag denna stora while-slinga som ringer fgetc,
F Betydelse filen, så getc och sedan stdin.
Det visar sig detta är bara mer exakt sätt att säga läsa indata från tangentbordet.
Standard input betyder tangentbord, betyder standard ut skärmen,
och standardfelet, som vi ser i pset4 innebär skärmen
men en särskild del av skärmen så att den inte är sammanbinds med den faktiska produktionen
att du ville skriva ut. Men mer om det i framtiden.
Så fgetc betyder bara läsa ett tecken från tangentbordet och förvaras där?
Förvara den i c.
Och sedan kontrollera - så jag bara med några booleska konjunktioner här -
kontrollera att det inte är lika - \ n, så att användaren har drabbat Enter vill vi stanna vid denna punkt,
slutet av slingan - och vi vill också se till det särskilda konstant EOF,
som om du vet eller gissa, vad står på? >> [Elev] Slut på fil. >> Slutet av filen.
Detta är typ av nonsens, för om jag skriver på tangentbordet,
det finns egentligen ingen fil inblandade i detta,
men detta är sortera bara av den generiska termen för att beteckna
att inget annat kommer från mänskliga fingrar.
EOF - slutet av filen.
Som en sidoreplik, om du någonsin drabbats Kontroll D i tangentbordet, inte att du skulle ha ännu -
du nått Kontroll C - Kontroll D sänder denna speciella konstant kallas EOF.
Så nu har vi bara några dynamisk minnesallokering.
>> Så om (n + 1> kapacitet). Nu ska jag förklara n.
N är bara hur många byte är för närvarande i bufferten,
den sträng som du för närvarande bygger upp från användaren.
Om du har fler tecken i din buffert än du har kapacitet i bufferten,
intuitivt vad vi behöver göra då är fördela mer kapacitet.
Så jag kommer att skumma över en del av den aritmetiska här och bara fokusera på denna funktion här.
Du vet vad malloc är eller åtminstone generellt bekant.
Ta en gissning vad realloc gör. >> [Elev] Lägger minne.
Det är inte riktigt lägga till minne. Det omfördelar minne enligt följande.
Om det fortfarande finns rum i slutet av strängen för att ge dig mer av det minne
än det ursprungligen ger dig, så kommer du få det extra minnet.
Så du kan bara hålla sätta strängen karaktärer rygg mot rygg mot rygg mot rygg.
Men om det inte är fallet eftersom du väntat för länge
och något slumpmässigt fick plopped i minnet där
men det finns extra minne här nere, det är okej.
Realloc kommer att göra alla tunga lyft för dig,
flytta strängen du har läst i så långt härifrån, lägg ner där,
och sedan ge dig lite mer landningsbana på den punkten.
>> Så med en handrörelse, låt mig säga att det GetString gör
är det börjar med en liten buffert, kanske en enstaka tecken,
och om användaren skriver in två tecken, slutar GetString upp ringa realloc och säger
ett tecken räckte inte, ge mig två tecken.
Sen om du läser igenom logiken i slingan, det kommer att säga
användaren har skrivit in 3 tecken, ge mig nu inte 2, men 4 tecken,
sedan ge mig 8, så ge mig 16 och 32.
Det faktum att jag fördubbling av kapaciteten varje gång
innebär att bufferten inte kommer att växa långsamt, det kommer att växa supersnabb.
Och vad kan vara fördelen med det?
Varför jag fördubbla storleken på bufferten
även om användaren kanske bara behöver en extra karaktär från tangentbordet?
[Ohörbart elev svar] >> Vad är det? >> [Elev] Du behöver inte odla den så ofta.
Exakt. Du behöver inte att odla den så ofta.
Och detta är bara typ av du säkra dina insatser här,
Tanken är att du inte vill ringa realloc mycket eftersom det tenderar att vara långsam.
Varje gång du frågar operativsystemet för minne,
som ni kommer snart att se i en framtida problembild, tenderar det att ta lite tid.
Så minimera denna tid, även om du slösar bort en del utrymme,
tenderar att vara en bra sak.
>> Men om vi läser igenom den sista delen av getString här -
och återigen förstå varenda rad här är inte så viktigt i dag -
märker att det till slut ringer malloc igen
och det fördelar precis som många byte som den behöver för strängen
och sedan kastar bort genom att ringa gratis till alltför stor buffert
om det verkligen blev dubbelt så många gånger.
Så kort sagt, det är hur GetString har arbetat hela tiden.
Allt det gör är läser ett tecken i tiden igen och igen och igen,
och varje gång den behöver lite extra minne, frågar den operativsystemet för det
genom att ringa realloc.
>> Några frågor? Okej.
>> En attack.
Nu när vi förstår pekare eller åtminstone blir alltmer förtrogna med pekare,
låt oss överväga hur hela världen börjar kollapsa
om du inte riktigt försvara sig mot kontradiktoriska användare,
människor som försöker hacka sig in i systemet,
människor som försöker stjäla din programvara genom att kringgå vissa registreringskod
att de annars måste skriva i.
>> Ta en titt på detta exempel här, vilket är just C-kod som har en funktion huvud i botten
som anropar en funktion foo. Och vad är det som går till foo?
[Eleven] En enda argument. >> [Malan] En enda argument.
Så argv [1], vilket innebär det första ordet som användaren skrivit på kommandoraden
efter a.out eller vad programmet heter.
Så foo överst tar in en char *. Men char * är precis vad? >> [Elev] En sträng.
[Malan] En sträng, så det finns inget nytt här.
Denna sträng är godtyckligt kallas bar.
I denna linje här, röding C [12], i form av semi-teknisk engelska, vad denna linje gör?
[Elev] En array med - >> Array av? >> [Elev] Tecken. >> Tecken.
Ge mig en rad 12 tecken. Så vi kan kalla detta en buffert.
Det tekniskt kallas C, men en buffert i programmering betyder bara en massa utrymme
att du kan lägga några saker i.
Sedan slutligen, memcpy vi inte har använt förut, men du kan nog gissa vad den gör.
Den kopierar minne. Vad gör det?
Den kopierar tydligen bar, dess ingång, till C men endast upp till längden på baren.
Men det finns en bugg här. >> [Eleven] Du behöver sizeof karaktär. >> Okej.
Tekniskt sett ska vi verkligen strlen (bar) * sizeof (char)). Det är korrekt.
Men i värsta fall här, låt oss anta att that -
Okej. Sedan finns två buggar.
Så sizeof (char));
Låt oss göra detta till en lite bredare.
Så nu finns det fortfarande en bugg, vilket är vad? >> [Ohörbart elev svar]
Kontrollera om vad? >> [Elev] Kontrollera NULL.
Vi bör i allmänhet kontroll av NULL eftersom dåliga saker hända
när pekaren är NULL eftersom du kan hamna kommer det,
och du bör inte någonsin kommer att NULL genom dereferencing den med stjärnan operatören.
Så det är bra. Och vad gör vi? Logiskt sett finns det en brist här.
[Elev] Kontrollera om argc är> = till 2.
Så kolla om argc är> = 2. Okej, så det finns tre buggar i programmet här.
Vi bevakar nu kontrollera om användaren faktiskt skrivit i något i argv [1]. Bra.
Så vad är den tredje bugg? Ja. >> [Elev] C kanske inte tillräckligt stor.
Bra. Vi kollade en scenario.
Vi kollade implicit inte kopierar mer minne än vad som skulle överskrida längden på baren.
Så om strängen användaren skrivit in är 10 tecken långt,
Detta säger bara kopiera 10 tecken. Och det är okej.
Men vad händer om användaren skrivit in ett ord vid prompten som en 20-tecken ord?
Detta säger exemplar 20 tecken från bar till vad?
C, annars känd som vår buffert, vilket innebär att du bara skrev uppgifter
till 8 byte platser som du inte äger,
och du inte äger dem i den meningen att du aldrig tilldelats dem.
Så detta är vad som allmänt är känt som buffertspill attack eller buffertöverskridning attack.
Och det är en attack i den meningen att om användaren eller programmet som ringer din funktion
gör detta uppsåtligt, vad som egentligen händer nästa kan faktiskt vara ganska dålig.
>> Så låt oss ta en titt på den här bilden här.
Denna bild representerar din stack minne.
Minns att varje gång du ringer en funktion får du denna lilla ram på stacken
och sedan en annan och sedan en annan och en annan.
Och hittills vi har bara typ av abstraherade dessa som rektanglar
antingen på kortet eller på skärmen här.
Men om vi zooma in på en av dessa rektanglar, när du ringer en funktion foo,
det visar sig att det finns mer på stacken insidan av denna ram i den rektangel
än x och y och a och b, som vi gjorde tala om swap.
Det visar sig att det finns en del på lägre nivå detaljer, bland dem returadress.
Så det visar sig när huvud samtal foo, har stora informera foo
vad främsta adress är i datorns minne
annars är så fort foo gjort exekvera, som i detta fall här,
när du har nått denna slutna klammerparentes i slutet av foo,
Hur i helsike vet foo där kontroll av programmet är tänkt att gå?
Det visar sig att svaret på den frågan är i detta röd rektangel här.
Detta motsvarar en pekare, och det är upp till datorn för att lagra temporärt
den så kallade stacken adressen till huvud så att så fort foo görs köra,
datorn vet var och vad linje i huvud att gå tillbaka till.
Sparade rampekaren avser liknande till detta.
Char * bar här representerar vad?
Nu blå segment är här foo s ram. Vad är bar?
Bar är bara argumentet till foo-funktionen.
Så nu är vi tillbaka på typ av det välbekanta bilden.
Det finns mer saker och fler distraktioner på skärmen,
men denna ljusblå segment är precis vad vi har att rita på tavlan
för något som swap. Det är ramen för foo.
Och det enda i det just nu är bar, som är den här parametern.
Men vad ska vara i stapeln enligt denna kod här?
[Eleven] röding C [12]. >> [Malan] röding C [12].
Vi bör också se 12 rutor minne som tilldelats en variabel som heter C,
och faktiskt vi har det på skärmen.
Högst upp finns c [0] och författare till detta diagram
brydde sig inte dra alla rutorna, men det finns faktiskt 12 finns
för om man tittar på det nedre högra, C [11] om man räknar från 0 är den 12: e sådan byte.
Men här är problemet.
I vilken riktning c växer?
Sortera på uppifrån och ner om det börjar i toppen och växer till botten.
Det ser inte ut som vi lämnade oss mycket banan här alls.
Vi har typ av målat in oss i ett hörn,
och att c [11] är rätt upp mot bar, som är rätt upp mot Sparad Ram pekare,
vilket är rätt upp mot returadress. Det finns ingen mer plats.
Så vad är innebörden så om du skruvar upp
och du försöker läsa 20 byte i en 12-byte buffert?
Vart är de 8 extra byte kommer att gå? >> [Elev] Inside -
Inuti allt annat, är några av dessa super viktigt.
Och det viktigaste, eventuellt är den röda rutan där returadress,
eftersom antar att du antingen av misstag eller adversarially skriva dessa 4 byte,
att pekaren adress, inte bara med skräp, men med ett antal
det händer att representera en verklig adress i minnet.
Vad är innebörden, logiskt? >> [Eleven] Funktion kommer att återgå till en annan plats.
Exakt.
När foo avkastning och träffar som klammerparentes är programmet kommer att fortsätta
inte återvända till huvud, det kommer att återvända till vad adress är i det röda rutan.
>> I fallet kringgå programvara registrering,
vad händer om den adress som är återförs till är den funktion som normalt anropas
efter att du har betalat för programvaran och matas din registreringskod?
Du kan sortera om lura datorn till inte kommer hit utan att gå upp här.
Eller om du är riktigt smart kan en motståndare skriva faktiskt på tangentbordet, till exempel,
inte en verklig ord, inte 20 tecken, men antar han eller hon faktiskt typer i
vissa tecken som representerar kod.
Och det kommer inte att bli C-kod, det kommer faktiskt bli tecknen
som representerar binära maskinkod, 0 och 1.
Men antar att de är smarta nog att göra det,
att på något sätt klistra in den GetString snabb något som är i huvudsak kompilerad kod,
och de sista 4 byte skriva att returadress.
Och vad adress betyder det ingång gör?
Den lagrar faktiskt i denna röd rektangel adressen för den första byten i bufferten.
Så du måste vara riktigt smart, och detta är en hel del trial and error för dåliga människor där ute,
men om du kan lista ut hur stor denna buffert är
så att de sista byte i ingången du ger till programmet
råkar motsvara adressen början av din buffert, kan du göra det här.
Om vi ​​säger normalt hej och \ 0, det är vad hamnar i bufferten.
Men om vi är mer smart och vi fyller denna buffert med vad vi ska generiskt kallar attackkod -
AAA, attack, attack, attack - om det är bara något som gör något dåligt,
vad händer om du är riktigt smart, kan du göra det här.
I den röda rutan här är en sekvens av siffror - 80, C0, 35, 08.
Observera att som matchar numret som är här uppe.
Det är i omvänd ordning, men mer om det en annan gång.
Observera att detta returadress medvetet har ändrats
till lika adressen här uppe, inte adressen till huvud.
Så om den onde är super smart, han eller hon kommer att ingå i den attacken kod
något som tar bort alla användarens filer eller kopiera lösenorden
eller skapa ett användarkonto som jag sedan kan logga in på - något alls.
>> Och detta är både faran och kraften i C.
Eftersom du har tillgång till minnet via pekare
och du kan därför skriva vad du vill i en dators minne,
kan du göra en dator göra vad du vill
helt enkelt genom att ha den hoppar runt i sitt eget minne.
Och så i dag så många program och så många webbplatser som äventyras
koka ner till människor som tar nytta av detta.
Och detta kan tyckas vara en super sofistikerad attack, men det är inte alltid startar på det sättet.
Verkligheten är att det dåliga människor vanligen gör är,
oavsett om det är ett program på en kommandorad eller ett grafiskt program eller en hemsida,
du börjar bara erbjuda nonsens.
Du skriver i en riktigt stor ord i sökfältet och tryck Enter,
och du vänta och se om webbplatsen kraschar
eller om du vänta och se om programmet visar något felmeddelande
för om du har tur som den onde och du ge några galna ingång
som kraschar programmet, som innebär att programmeraren inte förutse dina dåliga beteende,
vilket innebär att du kan förmodligen tillräckligt med ansträngning, tillräckligt försök och misstag,
räkna ut hur att föra en mer exakt attack.
Så lika mycket en del av säkerheten är inte bara undvika dessa attacker helt
men upptäcka dem och faktiskt titta på loggar
och se vad galna ingångar har människor skrivit i din hemsida,
vilka ord har människor skrivit på din hemsida
i hopp om att överfyllda lite buffert.
Och allt detta handlar om att de enkla grunderna i vad en matris
och vad innebär det att fördela och använda minnet.
>> Relaterat till detta då också är det.
Låt oss bara blick inuti en hårddisk ännu en gång.
Du minns från en vecka eller två sedan att när man drar filer till din papperskorgen eller papperskorgen,
vad händer? >> [Elev] Inget. >> Absolut ingenting, eller hur?
Så småningom om du kör låg på diskutrymme,
Windows eller Mac OS kommer att börja ta bort filer för dig.
Men om du drar något där, det är inte alls säkert.
Alla dina rumskompis eller vän eller familjemedlem har att göra är att dubbelklicka och voila,
Det finns alla de skissartade filer som du försökte ta bort.
De flesta av oss åtminstone veta att du måste högerklicka eller kontrollera klicka
och töm papperskorgen eller något liknande.
Men även då det inte gör riktigt susen
eftersom vad som händer när du har en fil på din hårddisk
som står för cirka Word-dokument eller något JPEG och detta representerar din hårddisk,
och låt oss säga detta flisa här representerar filen,
och det består av en hel massa av 0 och 1.
Vad händer när du inte bara dra filen till papperskorgen kan eller papperskorgen
men också tömma den? Sortera ingenting.
Det är inte absolut ingenting nu.
Nu är det bara ingenting eftersom en liten sak som händer i form av den här tabellen.
Så det finns någon form av databas eller tabell inuti en dators minne
som har i huvudsak en kolumn för filer namn och en kolumn för filer "läge,
där detta kan vara platsen 123, bara ett slumptal.
Så vi kanske har något som x.jpeg och plats 123.
Vad händer då när du faktiskt tömma papperskorgen?
Det går undan.
Men vad inte går bort är det 0 och 1.
>> Så vad är då anslutningen till pset4?
Tja, med pset4, bara för att vi har oavsiktligt raderas compact flash-kortet
som hade alla dessa bilder eller bara för att det genom otur blev skadad
betyder inte att den 0 och 1 är inte kvar.
Kanske några av dem går förlorade eftersom något blev skadad
i den meningen att vissa 0s blev 1s och 1s blev 0s.
Dåliga saker kan hända på grund av buggiga program eller defekt hårdvara.
Men många av dessa bitar, kanske 100% av dem, finns fortfarande kvar.
Det är bara att datorn eller kameran inte vet var JPEG1 startade
och där JPEG2 startade.
Men om du, programmeraren, vet med lite vett om dessa JPEG-bilder är
eller hur de ser ut så att du kan analysera 0 och 1 och säga JPEG, JPEG,
Du kan skriva ett program med i huvudsak bara en för eller while-slinga
som återvinner var och en av dessa filer.
Så lektionen är då att börja säkert radera dina filer
Om du vill undvika detta helt och hållet. Ja.
>> [Elev] Hur kommer det står på din dator
att du har mer minne än du gjorde innan?
Har mer minne än vad du gjorde innan - >> [elev] Mer tillgängligt minne.
Åh. Bra fråga.
Så varför då efter tömning av papperskorgen berättar din dator du
att du har mer ledigt utrymme än du gjorde innan?
I ett nötskal, eftersom det ljuger.
Mer tekniskt, har du mer utrymme eftersom du nu har sagt
kan du lägga andra saker där den filen en gång var.
Men det betyder inte att bitarna går bort,
och det betyder inte att de bitarna ändras till enbart 0, till exempel,
för att skydda dig.
Så däremot om du säkert radera filer eller fysiskt förstöra enheten,
det är egentligen det enda sättet ibland runt det.
>> Så varför inte vi lämnar på den semi-skrämmande anmärkning, och vi kommer att se dig på måndag.
[Applåder]
>> [CS50.TV]