[Powered by Google Translate] [Settimana 5] [David J. Malan - Harvard University] [Questo è CS50. - CS50.TV] 

Questo è CS50, settimana 5. Oggi e questa settimana, si introduce un po 'del mondo della medicina legale nel contesto del problema posto 4. Oggi sarà una lezione abbreviato perché c'è un evento speciale qui in seguito. Quindi dovremo dare un'occhiata e prendere in giro sia a studenti e genitori di oggi con alcune delle cose che sono all'orizzonte. 

Tra questi, come di Lunedi, si avrà un paio di compagni di classe. edx, Harvard e la nuova iniziativa on line del MIT OpenCourseWare e per di più, sta lanciando nel campus di Harvard il Lunedi, il che significa venire Lunedi si avrà, a partire dal le ultime stime, 86.000 compagni supplementari che sarà seguito con lezioni CS50 e le sezioni e procedure dettagliate e set problema. E come parte di questo, si diventa membri della classe inaugurale del CS50 e ora CS50x. Come parte di questo momento, si rendono conto che ci saranno alcuni aspetti positivi pure. Per prepararsi a questo, per il numero enorme di studenti, basti dire che, anche se abbiamo 108 TF e CA, non è proprio il miglior rapporto studenti-insegnanti, una volta abbiamo raggiunto 80.000 studenti. Non sta andando ad essere un problema di classificazione tanti imposta manualmente, così introdotto questa settimana nel set problema sarà CS50 Check, che sta per essere una riga di comando all'interno dell'apparecchio che si otterrà una volta che si aggiorna dopo questo fine settimana. Sarete in grado di eseguire un comando, check50, sul pset proprio, e si otterrà un feedback immediato sul fatto che il programma è giusta o sbagliata secondo le specifiche di progetto diversi che abbiamo fornito. Più su che nella specifica set problema. I compagni di classe CS50x quali si utilizza questo pure. 

Set Problema 4 è tutto forense, e questo pset era davvero ispirato da alcuni vita reale roba per cui quando ero a scuola di specializzazione ho internato per un po ' con sede procuratore distrettuale della contea di Middlesex sta facendo il lavoro forense con il loro capo ricercatore forense. Ciò che questo è pari a, come penso ho già detto un paio di settimane passate, è la Polizia di Stato di massa o altri sarebbe venuto in, avrebbero lasciare le cose come hard disk e CD e floppy disk e simili, e quindi l'obiettivo dell'ufficio forense era accertare se ci fosse o meno la prova di qualche tipo. Questa è stata la Squadra Speciale Investigativa, quindi era criminalità dei colletti bianchi. Era una specie più inquietante di delitti, qualsiasi azione che comporti una sorta di media digitali. Si scopre che non è che molte persone scrivere una e-mail dicendo: "L'ho fatto." Così molto spesso, queste ricerche forensi non si presentò tutto ciò che molto frutto, ma a volte la gente scrivere tali e-mail. Così a volte, gli sforzi sono stati premiati. 

Ma per portare a questo pset forense, saremo in pset4 introdurre un po 'di grafica. Probabilmente prendere queste cose per scontato - JPEG, GIF, e simili - in questi giorni. Ma se davvero pensate, un'immagine, proprio come il viso di Rob, potrebbe essere modellato come una sequenza di punti o pixel. Nel caso della faccia di Rob, ci sono tutti i colori, e abbiamo iniziato a vedere i singoli punti, altrimenti noti come pixel, una volta che abbiamo iniziato a Immagine Ma se semplificare il mondo un po 'e solo dire che questo qui è Rob in bianco e nero, per rappresentare in bianco e nero, si può semplicemente utilizzare binario. E se abbiamo intenzione di utilizzare binario, 1 o 0, siamo in grado di esprimere questa stessa immagine del volto sorridente di Rob con questo modello di bit. 11000011 rappresenta il bianco, bianco, nero, nero, nero, nero, bianco, bianco. E quindi non è un enorme balzo in poi cominciare a parlare di fotografie colorate, le cose che ci si vede su Facebook o prendere con una macchina fotografica digitale. Ma certamente quando si tratta di colori, avete bisogno di più bit. E abbastanza comune nel mondo delle fotografie è di non usare 1-bit di colore, come questo suggerisce, ma colori a 24 bit, in cui è effettivamente ottenere milioni di colori. Così come nel caso in cui ci zoom su occhi di Rob, che era un numero qualsiasi di milioni di differenti possibilità colorati. Quindi dovremo introdurre questo nel set Problema 4, nonché nella procedura dettagliata, che sarà oggi alle 3:30 invece del solito a causa della conferenza 02:30 Venerdì qui. Ma il video sarà online da domani al solito. 

Inoltre, ti introducono in un altro formato di file. Questo è deliberatamente vuole guardare intimidatorio in un primo momento, ma questo è solo un po 'di documentazione per una struct C. Si scopre che anni fa, Microsoft ha contribuito a diffondere questo formato chiamato il formato di file bitmap, bmp, e questo era un super semplice, formato di file grafico colorato che è stato utilizzato per un bel po 'di tempo e, a volte ancora per sfondi per desktop. Se si pensa di nuovo a Windows XP e le dolci colline e l'azzurro del cielo, che era tipicamente un'immagine bmp o bitmap. Bitmap sono divertenti per noi perché hanno la complessità di un po 'di più. Non è così semplice come questa griglia di 0 e 1. Invece, avete cose come un colpo di testa all'inizio di un file. In altre parole, all'interno di un file. Bmp è un insieme di 0 e 1, ma c'è qualche ulteriore 0s e 1s in là. E si scopre che quello che abbiamo probabilmente dato per scontato da anni - formati di file come. doc o. xls o. mp3, mp4., a prescindere dai formati di file che si ha familiarità con - cosa vuol dire essere anche un formato di file, perché alla fine della giornata tutti questi file usiamo avere solo 0 e 1. E forse coloro 0 e 1 rappresentano ABC tramite ASCII o simili, ma alla fine della giornata, è ancora solo 0 e 1. Così gli esseri umani solo occasionalmente decide di inventare un nuovo formato di file dove standardizzare ciò che i modelli di bit effettivamente dire. E in questo caso qui, la gente che ha progettato il formato di file bitmap ha detto che al primo byte in un file bitmap, come indicato da 0 Offset lì, ci sarà un po 'di nomi incomprensibili bfType variabile chiamata, che sta solo per tipo di file bitmap, che tipo di file bitmap è questo. Si può dedurre, forse dalla seconda fila che ha compensato 2, numero byte 2, ha un modello di 0 e 1 che rappresenta ciò che? La dimensione di qualcosa. E si va avanti da lì. Così nel Set Problema 4, sarete camminato attraverso alcune di queste cose. Non finirà per prendersi cura di ognuno di loro. Ma nota che inizia a diventare interessante in giro byte 54: rgbtBlue, verde e rosso. Se hai mai sentito la sigla RGB - rosso, verde, blu - questo è un riferimento a tale perché è venuto fuori è possibile dipingere tutti i colori dell'arcobaleno con una combinazione di rosso e blu e verde. E infatti, i genitori nella stanza può ricordare alcuni dei primi proiettori. In questi giorni, si vede solo una luce forte proveniente da una lente, ma nel giorno in cui ha avuto la lente rossa, la lente blu, e la lente verde, e insieme volto a uno schermo e formato un immagine colorata. E molto spesso, scuole medie e scuole superiori avrebbero quelle lenti sempre in modo leggermente di traverso, in modo che erano una specie di vedere immagini doppie o triple. Ma questa era l'idea. Hai avuto luce rossa e verde e blu dipingere un quadro. E questo stesso principio è usato nei computer. 

Quindi, tra le sfide allora per voi in Problema Set 4 stanno per essere un paio di cose. Uno è quello di ridimensionare un immagine, di prendere in un modello di 0 e 1, capire quali pezzi di 0 e 1 rappresentano ciò che in una struttura come questa, e poi capire come replicare i pixel - i rossi, i blu, i verdi - all'interno in modo che, quando un'immagine è simile inizialmente, potrebbe apparire come questo, invece dopo. Tra le altre sfide troppo sarà che ti verrà consegnato un immagine forense di un file vero e proprio da una fotocamera digitale. E su quella macchina fotografica, un tempo, erano un sacco di foto. Il problema è che accidentalmente cancellati o ha avuto l'immagine danneggiato in qualche modo. Le cose brutte succedono con le fotocamere digitali. E così abbiamo subito copiato tutti i off 0 e 1 di quella carta per voi, salvati tutti in un unico grande file, e poi noi li consegnare a voi in Problema Set 4 in modo che sia possibile scrivere un programma in C con il quale recuperare tutti quei file JPEG, idealmente. E si scopre che i file JPEG, anche se sono un po 'di un formato di file complesso - sono molto più complesso di questo volto sorridente qui - si scopre che ogni JPEG inizia con gli stessi schemi di 0 e 1. Quindi, utilizzando, in ultima analisi, un ciclo while o un ciclo for o simili, è possibile scorrere tutte le 0 e 1 in questa immagine forense, e ogni volta che si vede il motivo speciale che è definito nella specifica set problema, si può assumere ecco, con elevata probabilità, l'inizio di un JPEG. E non appena si trova lo stesso modello un certo numero di byte o kilobyte o in megabyte successive, è possibile assumere qui è un secondo JPEG, la foto che ho scattato dopo il primo. Vorrei smettere di leggere quel file in primo luogo, iniziare a scrivere questo nuovo, e l'uscita del programma per pset4 sta per essere fino a 50 JPEG. E se non è 50 file JPEG, si dispone di un po 'di un ciclo. Se si dispone di un numero infinito di file JPEG, si dispone di un ciclo infinito. Quindi, anche questo sarà un bel caso comune. Ecco, questo è ciò che è all'orizzonte. 

Quiz 0, dietro di noi, per realizzare il mio e-mail che ci sono sempre persone che sono entrambi felici, sorta di folle, e triste intorno quiz 0 Tempo. E vi prego di non entrare in contatto con me, la testa TF Zamyla, il TF proprio, o uno dei CA che si sa se si vuole discutere di come sono andate le cose. 

Quindi, per impressionare i genitori qui in camera, che è la libreria CS50? [Risate] Ottimo lavoro. Qual è la biblioteca CS50? Gia '. >> [Studente] E 'un pre-scritto insieme di codice [incomprensibile] Ok, bene. Si tratta di un pre-scritto insieme di codice che abbiamo scritto il personale, che offriamo a voi, che fornisce alcune funzionalità comuni, roba come farmi una stringa, mi ottenere un int - tutte le funzioni che sono elencate qui. 

A partire da ora, si comincia a prendere realmente queste ruote di formazione off. Stiamo per iniziare a togliere una stringa da te, richiamo che era solo un sinonimo di ciò che tipo di dati effettivo? [>> Più studenti] Char *. * Char. Per i genitori, che era probabilmente [rende il suono sibilante]. Questo è un bene. * Char inizieremo a vedere sullo schermo tanto più dal momento che eliminiamo stringa dal nostro vocabolario, almeno quando si tratta di realtà la scrittura di codice. Allo stesso modo, ci smettere di usare alcune di queste funzioni il più perché i nostri programmi stanno andando ottenere più sofisticati. Piuttosto che scrivere programmi che si trovano lì con un lampeggiante prompt, attesa che l'utente a digitare qualcosa, avrai gli ingressi da qualche altra parte. Per esempio, potrai ottenere da una serie di bit sul disco rigido locale. Avrete invece ottenere in futuro da una connessione di rete, qualche sito da qualche parte. 

Quindi cerchiamo di togliere questo strato per la prima volta e tirare il CS50 Appliance e questo file chiamato cs50.h, che hai # anche per settimane, ma cerchiamo di realmente vedere cosa c'è dentro di questo. La parte superiore del file in blu è solo un insieme di commenti: informazioni sulla garanzia e la concessione di licenze. Questa è una sorta di paradigma comune nel software perché un sacco di software in questi giorni è ciò che si chiama open source, il che significa che qualcuno ha scritto il codice e reso liberamente disponibile non solo per correre e da usare, ma in realtà per leggere e modificare e integrare nel proprio lavoro. Ecco, questo è quello che hai usato, il software open source, anche se in una forma molto piccola. Se scorrere verso il basso oltre i commenti, però, che inizieremo a vedere alcune cose più familiari. Si noti in alto qui che il file cs50.h comprende un insieme di file di intestazione. La maggior parte di questi, che non abbiamo mai visto prima, ma è familiare. Quale di questi abbiamo visto, anche se brevemente, fino ad ora? >> [Studente] libreria standard. Si ', libreria standard. stdlib.h ha malloc. Una volta che abbiamo iniziato a parlare di allocazione dinamica della memoria, che torneremo la prossima settimana pure, abbiamo iniziato anche il file. Si scopre che bool e vero e il falso in realtà non esiste in C per sé a meno che non si include questo file qui. Ci siamo stati per settimane tra stdbool.h in modo che è possibile utilizzare il concetto di un bool, vero o falso. Senza questo, si dovrebbe ordinare di fingere e utilizzare un int e solo arbitrariamente supporre che 0 è falso e 1 è vero. Se scorrere verso il basso più, ecco la nostra definizione di una stringa. Si scopre, come abbiamo detto prima, che dove questa stella non ha molta importanza. Si può anche avere lo spazio tutto intorno. Abbiamo questo semestre sono state promuovendo come questo per chiarire la stella che ha a che fare con il tipo, ma rendersi conto di come comune, se non un po 'più comune, è quello di mettere lì, ma funzionalmente è la stessa cosa. Ma ora se leggiamo ulteriormente verso il basso, diamo un'occhiata a GetInt perché abbiamo usato che, forse, prima di ogni altra cosa questo semestre. Ecco GetInt. Questo è ciò? >> [Studente] Un prototipo. >> Questo è solo un prototipo. Spesso, abbiamo messo prototipi ai vertici della nostra. File c, ma si può anche mettere prototipi nei file di intestazione, h. file, come questo qui in modo che quando si scrive alcune funzioni che si desidera che altre persone di essere in grado di utilizzare, che è esattamente il caso della biblioteca CS50, non solo implementare le funzioni in qualcosa come cs50.c, è anche mettere i prototipi non all'inizio del file, ma nella parte superiore di un file di intestazione. Poi quel file di intestazione è quello che amici e colleghi sono con # include nel proprio codice. Quindi tutto questo tempo, hai anche tutti questi prototipi, efficacemente nella parte superiore del file, ma per mezzo di questo # include meccanismo, che essenzialmente copie e paste di questo file nel vostro. Ecco un po 'di documentazione molto dettagliata. Abbiamo più o meno per scontato che GetInt ottiene un int, ma è venuto fuori ci sono alcuni casi particolari. Che cosa succede se l'utente digita in un numero che è troppo grande, un trilione, che proprio non può andare bene all'interno di un int? Qual è il comportamento previsto? Idealmente, è prevedibile. Quindi, in questo caso, se effettivamente leggere la stampa fine, ci troveremo a vedere che se la linea non può essere letto, questo INT_MAX restituisce. Non abbiamo mai parlato di questo, ma in base alla sua capitalizzazione, che è probabilmente? [Studente] Una costante. >> E 'una costante. E 'una costante speciale che probabilmente dichiarato in una di quelle file di intestazione che è più in alto nel file, e INT_MAX è probabilmente qualcosa di simile a circa 2 miliardi di euro, l'idea è che, perché abbiamo bisogno di indicare in qualche modo che qualcosa è andato storto, noi, sì, hanno 4000000000 numeri a nostra disposizione: -2 miliardi fino a 2 miliardi di euro, prendere o lasciare. Ebbene, ciò che è comune nella programmazione è rubi solo uno di questi numeri, forse 0, forse 2 miliardi di euro, forse -2000000000, in modo da trascorrere uno dei vostri valori possibili in modo che si può commettere al mondo che se qualcosa va storto, io tornerò questo valore super grande. Ma non si desidera che l'utente digita qualcosa di criptico come 234 ..., un numero molto grande. Lo generalizzare invece come una costante. Quindi, veramente, se venivano anale nelle ultime settimane, ogni volta che si chiama GetInt, si sarebbe dovuto verificare con una condizione if ha fatto il tipo di utente a INT_MAX, o, più precisamente, ha fatto ritorno INT_MAX GetInt, perché se lo facesse, questo significa che in realtà non lo scrivere. Qualcosa è andato storto in questo caso. Quindi questo è ciò che è noto come un valore sentinella, che significa semplicemente speciale. 

Passiamo ora nel file. C. Il file C è esistita nel apparecchio per molto tempo. E infatti, l'apparecchio ha il pre-compilato per voi in che cosa abbiamo chiamato codice oggetto, ma semplicemente non importa a voi dove è perché il sistema sa in questo caso è: l'apparecchio. Andiamo ora a scorrere verso il basso e vedere come getInt GetInt ha lavorato per tutto questo tempo. Qui ci sono commenti simili da prima. Vorrei ingrandire solo la porzione di codice. E quello che abbiamo per GetInt è la seguente. Ci vuole nessun input. Esso restituisce un int, while (true), quindi abbiamo un ciclo infinito deliberata, ma presumibilmente faremo uscire da questo in qualche modo o da restituire all'interno di questo. 

Vediamo come funziona. Ci sembrano utilizzare GetString in questa prima linea all'interno del ciclo, 166. Questo è ora buona pratica perché in quali circostanze potrebbe tornare GetString la parola chiave null speciale? >> [Studente] Se qualcosa va storto. Se qualcosa va storto. E cosa potrebbe andare male quando si chiama qualcosa come GetString? Gia '. >> [Studente] Malloc non riesce a dare le int. Gia '. Forse malloc fallisce. Da qualche parte sotto il cofano, GetString sta chiamando malloc, che alloca la memoria, che consente al negozio di computer tutti i personaggi che l'utente digita nella tastiera. E se l'utente ha avuto un sacco di tempo libero e scritto di più, per esempio, di 2 miliardi di caratteri, numero di caratteri superiore al computer ha anche RAM. GetString deve essere in grado di indicare che vi. Anche se questo è un super, super-angolo caso non comune, deve essere in qualche modo in grado di gestire questo, e così GetString, se siamo andati indietro e leggere la sua documentazione, fa in NULL fatto ritorno. Così ora se GetString fallisce restituendo NULL, GetInt sta per fallire restituendo INT_MAX proprio come una sentinella. Questi sono solo convenzioni umane. L'unico modo sarebbe che questo è il caso è quello di leggere la documentazione. 

Facciamo scorrere fino al punto in cui l'int è effettivamente ottenuto. Se scorrere verso il basso un po 'più, in linea 170, abbiamo un commento di cui sopra queste righe. Si dichiara nel 172 un int, n, e un char, c, e quindi questa nuova funzione, che alcuni di voi hanno imbattuto prima, sscanf. Questo sta per scanf stringa. In altre parole, dammi una stringa e lo esamina per pezzi di informazioni di interesse. Che cosa vuol dire? Supponiamo che digito, letteralmente, 123 alla tastiera e poi premere Invio. Qual è il tipo di dati di 123 in caso di ritorno da GetString? >> [Studente] Stringa. E 'ovviamente una stringa, giusto? Ho una stringa. Quindi 123 è davvero, quote-unquote, 123 con il \ 0 alla fine di esso. Questo non è un int. Questo non è un numero. Si presenta come un numero, ma non è in realtà. Così che cosa GetInt fare? Si deve esaminare la stringa da sinistra a destra - 123 \ 0 - e in qualche modo convertire in numero intero reale. Si può capire come fare questo. Se ripenso a pset2, che presumibilmente ottenuto un po 'confortevole con Cesare o Vigenère, in modo da poter scorrere una stringa, è possibile convertire i caratteri da int. Ma diamine, è un sacco di lavoro. Perché non chiamare una funzione come sscanf che fa per voi? Così sscanf si aspetta un argomento - in questo caso chiamato linea, che è una stringa. È quindi possibile specificare tra virgolette, molto simile a printf, che cosa vi aspettate di vedere in questa stringa. E quello che sto dicendo qui è mi aspetto di vedere un numero decimale e forse un carattere. E vedremo perché questo è il caso in un attimo. E si scopre che questa notazione è ora ricorda di cose abbiamo iniziato a parlare poco più di una settimana fa. Che cosa è & n e & c facendo per noi qui? >> [Studente] Indirizzo di n e l'indirizzo di c. Gia '. Mi sta dando l'indirizzo di n e l'indirizzo di c. Perché è così importante? Voi sapete che con le funzioni in C, si può sempre restituire un valore o nessun valore. È possibile restituire un int, una stringa, un galleggiante, un char, qualunque cosa, oppure è possibile restituire void, ma si può restituire solo una cosa al massimo. Ma qui vogliamo sscanf tornare me forse un int, un numero decimale, e anche un char, e ti spiego il perché il carattere in un momento. Si effettivamente desidera sscanf tornare due cose, ma non è solo possibile in C. È possibile lavorare in giro che passando in due indirizzi perché non appena vi consegnerà una funzione di due indirizzi, che cosa può fare con loro funzione? >> [Studente] Scrivi a quegli indirizzi. E 'in grado di scrivere a questi indirizzi. È possibile utilizzare l'operazione di stella e andare lì, a ciascuna di tali indirizzi. È un po 'questo meccanismo di back-door, ma molto comune per la modifica dei valori delle variabili più di un luogo - in questo caso, due. Ora notate sto controllando == 1 e poi tornare n se si, in effetti, restituiscono true. Allora, cosa sta succedendo? Tecnicamente, tutto quello che vuole veramente accadere in GetInt è questo. Vogliamo analizzare, per così dire, vogliamo leggere la stringa - fine citazione quote-123 - e se sembra che ci sia un numero, quello che stiamo dicendo di fare sscanf è mettere quel numero - 123 - in questa variabile n per me. Perché allora io in realtà sono anche questo? Qual è il ruolo di sscanf dicendo che si potrebbe anche ottenere un carattere qui? [Risposta degli studenti incomprensibile] >> Un punto decimale in realtà potrebbe funzionare. Facciamo ritengono che pensò per un momento. Che altro? [Studente] Potrebbe essere NULL. >> Buon pensiero. Potrebbe essere il carattere null. Non è in realtà in questo caso. Gia '. >> [Studente] ASCII. ASCII. Oppure vorrei generalizzare ancora di più. Il c% è solo per il controllo degli errori. Non vogliamo che ci sia un carattere dopo il numero, ma ciò che questo mi permette di fare è la seguente. Risulta che sscanf, oltre a memorizzare i valori N e C in questo esempio qui, quello che fa è anche restituisce il numero di variabili messo valori trovi Quindi, se solo digitare 123, quindi solo il% d sta per corrispondenza, e solo n viene memorizzato con un valore come 123, e nulla viene messo in c. C resta un valore spazzatura, per così dire - spazzatura perché non è mai stato inizializzato a un valore. Quindi, in questo caso, sscanf restituisce 1 perché ho popolato 1 di tali puntatori, in questo caso grande, ho un int in modo da liberare la linea per liberare la memoria che GetString effettivamente stanziato, e poi torno n, altrimenti se siete mai chiesti dove Riprova dichiarazione che viene, viene da qui. Quindi, se, al contrario, di tipo I in 123foo - solo una sequenza casuale di testo - sscanf è andare a vedere il numero, numero, numero, f, e sta andando a mettere il 123 in n; sta andando a mettere il f in c e poi tornare 2. Così abbiamo, usando solo la definizione di base del comportamento sscanf, un modo molto semplice - bene, complesso a prima vista, ma alla fine della giornata meccanismo abbastanza semplice - di dire vi è un int e in tal caso, è che l'unica cosa che ho trovato? E lo spazio bianco qui è intenzionale. Se andate a leggere la documentazione per sscanf, ti dice che se si include un pezzo di spazio bianco all'inizio o alla fine, sscanf troppo permetterà all'utente, per qualsiasi motivo, per toccare 123 bar nello spazio e che sarà legittimo. Non urlare l'utente solo perché hanno colpito la barra spaziatrice all'inizio o alla fine, che è solo un po 'più user-friendly. 

Tutte le domande poi su GetInt? Gia '. >> [Studente] Che cosa succede se hai appena messo in un char? Bella domanda. Che cosa succede se hai appena digitato un carattere come f e premere Invio senza mai digitare 123? Cosa ne pensi del comportamento di questa riga di codice sarebbe allora? [Risposta degli studenti incomprensibile] Si ', quindi sscanf in grado di coprire anche questo perché in quel caso, non sta andando a riempire n o c. E 'intenzione di tornare invece 0, nel qual caso sto anche la cattura di questo scenario perché il valore atteso che voglio è 1. Voglio solo una e una sola cosa da riempire. Bella domanda. 

Altri? Bene. 

Non lasciare che il passare attraverso tutte le funzioni qui dentro, ma quello che sembra essere forse interessante rimanente è GetString perché si scopre che getFloat, GetInt, GetDouble, GetLongLong tutti i punt un sacco di loro funzionalità per GetString. Quindi, diamo uno sguardo a come si è implementato qui. Questo sembra un po 'complessa, ma utilizza i fondamenti stessi che abbiamo iniziato a parlare la settimana scorsa. In GetString, che prende alcun argomento secondo il vuoto qui e restituisce una stringa, a quanto pare mi dichiaro una stringa chiamata buffer. Io non so davvero che cosa che sta per essere utilizzato per ancora, ma staremo a vedere. Sembra che la capacità è di default 0. Non del tutto sicuro di dove questo sta andando, non so cosa n sta per essere utilizzato per ancora, ma ora sta diventando un po 'più interessante. In linea 243, dichiariamo un int, c. Questa è una sorta di un dettaglio stupido. Un char è di 8 bit, e 8 bit in grado di memorizzare il numero di valori diversi? >> [Studente] 256. >> 256. Il problema è che se si vuole avere 256 caratteri ASCII diversi, i quali vi sono se si pensa di nuovo - e questo non è una cosa da memorizzare. Ma se ripenso a quel grande grafico ASCII abbiamo avuto settimane fa, ci sono stati in questo caso 128 o 256 caratteri ASCII. Abbiamo usato tutti i modelli fino 0 e 1. Questo è un problema se si vuole essere in grado di rilevare un errore perché se si sta già utilizzando 256 valori per i tuoi personaggi, che in realtà non pianificare in anticipo, perché ora non avete modo di dire, questo non è un carattere legittimo, questo è un messaggio errato. Quindi, ciò che il mondo non è che usano il valore più prossimo, qualcosa di simile a un int, in modo da avere un numero pazzesco di bit, 32, per 4 miliardi di possibili valori in modo che si può semplicemente finire con essenzialmente 257 di loro, Uno dei quali ha un significato speciale come un errore. 

Quindi cerchiamo di vedere come funziona. In linea 246, ho questo grande anello mentre quello sta chiamando fgetc, f file significato, così getc, e poi stdin. Si scopre questo è solo il modo più preciso per dire leggere l'input da tastiera. Tastiera standard mezzi di input, standard output significa schermo, e l'errore standard, che vedremo nel pset4, significa che lo schermo ma una parte speciale dello schermo in modo che non è tutt'uno con uscita effettiva che si intende stampare. Ma più su che in futuro. Così fgetc significa solo leggere un carattere dalla tastiera e conservarla dove? Conservare in c. E quindi controllare - quindi sto usando solo alcune congiunzioni booleane qui - verificare che non è uguale a - \ n, in modo che l'utente ha premere Invio, si vuole fermare a quel punto, fine del ciclo - e vogliamo anche per verificare la costante EOF speciale, che se si conosce o indovinare, che cosa rappresenta? >> [Studente] Fine del file. Fine >> del file. Questa è una specie di assurdo, perché se sto scrivendo sulla tastiera, non c'è davvero alcun file coinvolti in questo, ma questa è solo una specie di termine generico usato per indicare che nessun altro è in arrivo dalle dita del dell'essere umano. EOF - fine del file. Per inciso, se hai mai colpito Control D a vostra tastiera non, che si dovrebbe ancora - hai colpito di controllo C - Control D invia questa costante speciale chiamato EOF. Così ora non ci resta che un po 'di allocazione dinamica della memoria. 

Quindi, se (n + 1 capacità>). Ora ti spiego n. N è solo il numero di byte attualmente nel buffer, la stringa che si sta costruendo da parte dell'utente. Se si dispone di più caratteri nel buffer di quello che hai capacità nel buffer, intuitivamente quello che dobbiamo fare è quindi allocare più capacità. Quindi ho intenzione di sorvolare su alcune delle aritmetica qui e concentrarsi solo su questa funzione qui. Sai cosa malloc è o sono almeno generalmente familiare. Prova a indovinare cosa realloc fa. >> [Studente] Aggiunge memoria. Non è del tutto l'aggiunta di memoria. Esso rialloca memoria come segue. Se c'è ancora spazio alla fine della stringa per dare più di quel ricordo che dà origine, allora si otterrà che la memoria aggiuntiva. Così si può solo continuare a mettere i caratteri della stringa, back to back to back to back. Ma se non è questo il caso, perché hai aspettato troppo a lungo e qualcosa di casuale ha lasciato cadere in memoria ci ma non c'è memoria aggiuntiva qui, va bene. Realloc sta andando a fare tutto il lavoro pesante per voi, spostare la stringa che hai letto in modo molto lontano da qui, messo lì, e poi vi darà pista ancora un po 'a quel punto. 

Così, con un gesto della mano, lasciatemi dire che quello che sta facendo GetString si sta partendo con un buffer piccolo, forse un singolo carattere, e se l'utente digita in due personaggi, GetString finisce per chiamare realloc e dice: un personaggio non era abbastanza, dammi due caratteri. Poi se si legge attraverso la logica del ciclo, sta andando a dire l'utente ha digitato in 3 caratteri; mi danno ora non 2 ma 4 caratteri, allora dammi 8, poi dammi 16 e 32. Il fatto che io sono il raddoppio della capacità di volta in volta significa che il buffer non ha intenzione di crescere lentamente, sta andando a crescere super veloce. E quale potrebbe essere il vantaggio di questo? Perché sto raddoppiare la dimensione del buffer anche se l'utente può solo bisogno di un carattere in più dalla tastiera? [Risposta degli studenti incomprensibile] >> Che cos'è? >> [Studente] Non c'è bisogno di crescere come spesso. Esattamente. Non c'è bisogno di crescere come spesso. E questo è solo tipo di copertura che stai qui le vostre scommesse, l'idea è che non si vuole chiamare realloc molto perché tende ad essere lento. Ogni volta che si chiede il sistema operativo per la memoria, come vedrete presto in un set di problema futuro, tende a richiedere un certo tempo. Quindi, riducendo al minimo tale periodo di tempo, anche se si sta perdendo un po 'di spazio, tende ad essere una buona cosa. 

Ma se si legge attraverso la parte finale del GetString qui - e ancora capire ogni singola riga qui non è così importante oggi - notare che alla fine chiama malloc di nuovo e alloca esattamente byte quanti ne sono necessari per la stringa e poi getta via chiamando gratuitamente il buffer di dimensioni eccessive se davvero ha raddoppiato troppe volte. Così, in breve, è così che GetString ha lavorato per tutto questo tempo. Tutto ciò che fa è leggere un carattere alla volta ancora e ancora e ancora, e ogni volta che ha bisogno di un po 'di memoria aggiuntiva, si chiede al sistema operativo per lo chiamando realloc. 

Hai ancora domande? Bene. 

Un attacco. Ora che abbiamo capito i puntatori o per lo meno sono sempre più familiari con i puntatori, prendiamo in considerazione come il mondo intero inizia a crollare se non riesco a difendersi contro gli utenti contraddittorio, le persone che stanno cercando di penetrare nel vostro sistema, persone che stanno cercando di rubare il software aggirando qualche codice di registrazione che potrebbero altrimenti essere necessario digitare trovi 

Date un'occhiata a questo esempio qui, che è solo il codice C che ha una funzione principale nella parte inferiore che chiama una funzione foo. E che cosa sta passando a foo? [Studente] Un singolo argomento. >> [Malan] Un singolo argomento. Quindi, argv [1], il che significa che la prima parola che l'utente ha digitato nella riga di comando dopo a.out o qualunque sia il programma si chiama. Così foo in alto prende in un char *. Ma char * è proprio quello? >> [Studente] Una stringa. [Malan] Una stringa, quindi non c'è nulla di nuovo qui. Tale stringa viene arbitrariamente chiamato bar. In questa linea qui, char c [12], in una sorta di semi-inglese tecnico, cosa sta facendo questa linea? [Studente] Matrice di - Array di >>? >> [Studente] caratteri. Personaggi >>. Dammi un array di 12 caratteri. Così si potrebbe chiamare questo un buffer. E 'tecnicamente chiamato c, ma un buffer in programmazione significa solo un mucchio di spazio che si può mettere un po 'di roba trovi Poi infine, memcpy non abbiamo usato prima, ma si può intuire ciò che fa. Esso copia della memoria. Che cosa fa? E a quanto pare copia bar, il suo ingresso, in c ma solo fino alla lunghezza della barra. Ma c'è un bug qui. >> [Studente] è necessario il carattere sizeof. Va bene >>. Tecnicamente, si dovrebbe davvero fare strlen (bar) * sizeof (char)). Questo è corretto. Ma nel peggiore dei casi qui, supponiamo che that's - Va bene. Poi ci sono due errori. Quindi, sizeof (char)); Facciamo in modo che questo un po 'di più. Così ora c'è ancora un bug, che è quello che? >> [Risposta degli studenti incomprensibile] Controllare per cosa? >> [Studente] Verificare la presenza di NULL. Dovremmo essere generalmente controllando NULL perché le cose vanno così male quando il puntatore è NULL, perché si potrebbe finire per andare lì, e non si dovrebbe mai andare a NULL deferenziandolo con l'operatore stella. Quindi questo è un bene. E cos'altro stiamo facendo? Logicamente, c'è un difetto anche qui. [Studente] Controllare se argc è> = a 2. Quindi verificare se argc è> = 2. Ok, quindi ci sono tre errori in questo programma. Stiamo verificando se l'utente ha effettivamente digitato qualcosa in argv [1]. Buona. Allora qual è il bug terzo? Gia '. >> [Studente] C potrebbe non essere abbastanza grande. Buona. Abbiamo controllato uno scenario. Abbiamo controllato implicitamente non copiare più memoria di quella superare la lunghezza della barra. Quindi, se la stringa che l'utente digitato è di 10 caratteri, questo sta dicendo solo copiare 10 caratteri. E va bene così. Ma cosa succede se l'utente ha digitato in una parola al prompt come una parola di 20 caratteri? Questo sta dicendo copia 20 caratteri dalla barra in che cosa? C, altrimenti noto come il buffer, il che significa che i dati appena scritto a 8 posizioni di byte che non si è proprietari, e tu non ne sei il proprietario, nel senso che non li avete mai assegnato. Quindi questo è ciò che è comunemente noto come l'attacco di tipo buffer overflow o di sovraccarico del buffer di attacco. Ed è un attacco, nel senso che se l'utente o il programma che sta chiamando la funzione sta facendo questo maliziosamente, ciò che effettivamente accade prossimo potrebbe in realtà essere piuttosto male. 

Quindi diamo un'occhiata a questa immagine qui. Questa foto rappresenta la tua pila di memoria. Ricordiamo che ogni volta che si chiama una funzione si ottiene questo quadro poco nello stack e poi un altro e poi un altro e un altro. E fin qui, abbiamo solo un po 'astratta questi come rettangoli sia sul bordo o sulla schermata qui. Ma se zoomare su uno di quei rettangoli, quando si chiama una funzione foo, si scopre che c'è di più all'interno pila di quel frame in quel rettangolo non solo x e y e a e b, come abbiamo fatto parlare di swap. Si scopre che ci sono alcuni dettagli di basso livello, tra i quali l'indirizzo di ritorno. Così si scopre quando principale chiama foo, principale deve informare foo quale indirizzo principale è nella memoria del computer perché altrimenti, non appena foo è fatto esecuzione, come in questo caso qui, una volta raggiunto questo tutore chiuso riccio alla fine di foo, come cavolo si foo sa dove il controllo del programma dovrebbe andare? Si scopre che la risposta a questa domanda è in questo rettangolo rosso qui. Si tratta di un puntatore, e sta al computer per memorizzare temporaneamente sulla cosiddetta pila l'indirizzo principale in modo che non appena foo è fatto esecuzione, il computer sa dove e cosa linea principale per tornare a. Puntatore del fotogramma salvato si riferisce in modo simile a questo. Bar * Char qui rappresenta ciò? Ora questo segmento blu è qui cornice di foo. Che cosa è il bar? Bar è solo l'argomento per la funzione foo. Così ora siamo tornati a una sorta di quadro familiare. Ci sono più cose e più distrazioni sullo schermo, ma questo segmento azzurro è proprio quello che abbiamo disegnare alla lavagna per qualcosa come swap. Questo è il quadro per foo. E l'unica cosa che in questo momento è il bar, che è questo parametro. Ma che altro dovrebbe essere nello stack in base a questo codice qui? [Studente] char c [12]. >> [Malan] char c [12]. Dovremmo anche vedere 12 quadrati di memoria assegnati a una variabile denominata c, e infatti noi abbiamo che sullo schermo. La cima è c [0], e poi l'autore di questo schema non si preoccupò di disegnare tutte le piazze, ma ci sono davvero 12 si perché se si guarda in basso a destra, c [11] se si conta da 0 è il byte 12 ° del genere. Ma ecco il problema. In quale direzione sta crescendo c? Sorta di top-down se inizia in alto e cresce verso il basso. Non sembra come ci siamo lasciati pista molto qui a tutti. Abbiamo tipo di noi stessi in un angolo, e che c [11] è proprio contro il bar, che si trova proprio di fronte puntatore del fotogramma salvato, che si trova proprio di fronte l'indirizzo di ritorno. Non c'è più spazio. Allora, qual è l'implicazione poi se si avvitare e provare a leggere 20 byte in un buffer di 12 byte? Dove questi 8 byte aggiuntivi intenzione di andare? >> [Studente] Inside - All'interno tutto il resto, alcuni dei quali è super importante. E la cosa più importante, potenzialmente, è la scatola rossa lì, indirizzo del mittente, perché supponiamo che si sia accidentalmente o contraddittorio sovrascrivere quei 4 byte, che l'indirizzo del puntatore, non solo ai rifiuti, ma con un numero di che succede a rappresentare un indirizzo effettivo in memoria. Qual è l'implicazione, logicamente? >> [Studente] Funzione sta per tornare in un luogo diverso. Esattamente. Quando ritorna foo e colpisce che parentesi graffe, il programma sta per procedere non per tornare alla pagina principale, sta andando per tornare a qualsiasi indirizzo si trova in quella scatola rossa. 

Nel caso di registrazione del software eludere, cosa succede se l'indirizzo che viene restituito è la funzione che normalmente viene chiamata dopo aver pagato per il software e immesso il codice di registrazione? È possibile ordinare di trucco del computer in non andare qui ma andando qui. Oppure, se sei davvero intelligente, un avversario può effettivamente digitare sulla tastiera, ad esempio, non una parola vera, non 20 caratteri, ma supponiamo lui o lei in realtà i tipi della alcuni personaggi che rappresentano il codice. E non sarà il codice C, in realtà sta per essere i personaggi che rappresentano il codice binario della macchina, 0 e 1. Ma se sono abbastanza intelligenti per farlo, per incollare in qualche modo in qualcosa GetString richiesta che è essenzialmente il codice compilato, e gli ultimi 4 byte sovrascrivere l'indirizzo di ritorno. E che cosa vuol indirizzo di ingresso fare? Memorizza effettivamente in questo rettangolo rosso l'indirizzo del primo byte del buffer. Quindi devi essere molto intelligente, e questo è un sacco di tentativi ed errori per le persone cattive là fuori, ma se si riesce a capire quanto è grande questo buffer è tale che gli ultimi bytes nell'input fornire al programma capita di essere equivalente al indirizzo iniziale del buffer, si può fare questo. Se diciamo di solito ciao e \ 0, questo è ciò che finisce nel buffer. Ma se siamo più intelligenti e riempire il buffer con quello che ci chiamiamo genericamente codice di attacco - AAA, attacco, attacco, attacco - dove questo è solo qualcosa che fa qualcosa di male, cosa succede se sei molto intelligente, si potrebbe fare questo. Nella scatola rossa qui è una sequenza di numeri - 80, C0, 35, 08. Si noti che che corrisponde al numero che è qui. E 'in ordine inverso, ma più su che un'altra volta. Si noti che questo indirizzo di ritorno siano stati deliberatamente modificati per eguagliare l'indirizzo qui, non l'indirizzo del principale. Quindi, se il cattivo è super intelligente, lui o lei sta andando a includere in tale codice di attacco qualcosa di simile a eliminare tutti i file dell'utente o copiare le password o creare un account utente che posso quindi accedere al - nulla. 

E questo è sia il pericolo e il potere di C. Perché si ha accesso alla memoria tramite puntatori e si può quindi scrivere tutto quello che vuoi nella memoria di un computer, si può fare un computer a fare tutto quello che vuoi semplicemente averlo saltare nel suo spazio di memoria. E così fino ad oggi tanti programmi e siti web così tanti che sono compromessi si riducono a persone che beneficiano di questo. E questo potrebbe sembrare un attacco super sofisticato, ma non sempre iniziare in quel modo. La realtà è che ciò che le persone cattive in genere fare è, se si tratta di un programma a riga di comando o un programma con interfaccia grafica o un sito web, basta iniziare a fornire una sciocchezza. Si digita in una parola molto grande nel campo di ricerca e premere Invio, e si aspetta di vedere se il sito si blocca o si aspetta di vedere se il programma si manifesta qualche messaggio di errore perché se sei fortunato come il cattivo e di fornire alcuni input pazzo che va in crash il programma, che significa che il programmatore non ha previsto il tuo cattivo comportamento, il che significa che si può probabilmente con uno sforzo sufficiente prova, abbastanza ed errori, capire come condurre un attacco più preciso. Così tanto una parte della sicurezza non è solo di evitare questi attacchi del tutto ma li avverte e in realtà guardando i log e vedere quali fattori pazzi sono persone digitato nel tuo sito web, quali termini di ricerca sono le persone digitato nel tuo sito web nella speranza di un po 'di traboccante buffer. E questo tutto si riduce a semplici le basi di ciò che è un array e cosa significa per allocare e utilizzare la memoria. 

Relativo a che poi è anche questo. Diciamo solo un'occhiata all'interno di un hard disk ancora una volta. Vi ricordate di una o due settimane fa, che quando si trascina i file sul cestino o cestino, che cosa succede? >> [Studente] Niente. >> Assolutamente niente, giusto? Alla fine se si esegue poco spazio su disco, Windows o Mac OS avvierà l'eliminazione dei file per te. Ma se si trascina qualcosa in là, che non è affatto sicuro. Tutto il tuo compagno di stanza o un amico o un familiare ha a che fare un doppio clic e, voilà, ci sono tutti i file abbozzato che stai cercando di eliminare. La maggior parte di noi almeno sappiamo che è necessario fare clic destro o di controllo fare clic su e svuotare il cestino o qualcosa del genere. Ma anche allora che non farà il trucco perché ciò che succede quando si ha un file sul disco rigido che rappresenta circa il documento di Word o un JPEG, e questo rappresenta il disco rigido, e diciamo che questo frammento qui rappresenta quel file, ed è composto da un insieme di 0 e 1. Cosa succede quando non solo trascinare il file nel cestino o nel cestino ma anche svuotarla? Una specie di nulla. Non è assolutamente nulla. Ora è solo niente perché un po 'di qualcosa che accade in forma di questa tabella. Quindi c'è una sorta di database o una tabella all'interno della memoria di un computer che ha essenzialmente una colonna per i nomi dei file e una colonna per i file 'ubicazione, in cui questo potrebbe essere posizione 123, solo un numero casuale. Così potremmo avere qualcosa di simile a x.jpeg e la posizione 123. Che cosa succede allora quando effettivamente svuotare il cestino? Che se ne va. Ma ciò che non va via è la 0 e 1. 

Allora, qual è quindi la connessione al pset4? Bene, con pset4, solo perché abbiamo accidentalmente cancellato la scheda Compact Flash che aveva tutte queste foto o semplicemente perché dalla sfortuna è corrotto non significa che la 0 e 1 non sono ancora lì. Forse alcuni di loro si perdono perché qualcosa ha danneggiato nel senso che alcuni 0s divenne 1s 1s e 0s diventato. Le cose brutte possono accadere a causa di software difettoso o hardware difettoso. Ma molti di questi frammenti, forse anche il 100% di loro, sono ancora lì. E 'solo che il computer o la fotocamera non sa dove JPEG1 cominciato e dove JPEG2 iniziato. Ma se si, il programmatore, sapere con un po 'di buon senso in cui tali file JPEG sono o il loro aspetto in modo da poter analizzare la 0 e 1 e dire: JPEG, JPEG, è possibile scrivere un programma con essenzialmente solo un ciclo for o while che recupera ognuno di quei file. Quindi la lezione è quindi di avviare in modo sicuro cancellare i file se vuoi evitare questo del tutto. Sì. 

[Studente] Come mai si dice sul tuo computer di avere più memoria di quella che hai fatto prima? Avere più memoria di quanto si faceva prima - >> [studente] più memoria disponibile. Oh. Bella domanda. Allora, perché poi dopo lo svuotamento del cestino del computer non vi dico di avere più spazio libero che avete fatto prima? In poche parole, perché sta mentendo. Più tecnicamente, si ha più spazio perché ora che hai detto si può mettere altre cose in cui il file era una volta. Ma questo non significa che i bit stanno andando via, e questo non significa che i bit vengono modificate per tutti 0, per esempio, per la vostra protezione. Così invece, se in modo sicuro cancellare i file o distruggere fisicamente il dispositivo, questo è davvero l'unico modo a volte intorno a quella. 

Allora perché non lasciamo che il semi-spaventoso nota, e ci vedremo il Lunedi. [Applausi] 

[CS50.TV]