# Wiederherstellung Quelle: https://dev.inf.zone/exercises/07/recover/ ![Wiederhergestelltes Bild](https://dev.inf.zone/exercises/07/recover/./recovered_image.png) ## Aufgabe **Auf einen Blick** - **Was:** Ein Programm `recover`, das gelöschte JPEG-Fotos aus dem Abbild einer Speicherkarte (`card.raw`) wiederherstellt. - **Datei:** `recover.c` in einem Ordner `recover`. Die Datei enthält nur eine leere `main`-Funktion. - **Aufruf:** `./recover card.raw` - **Ausgabe:** die Fotos als Dateien `000.jpg`, `001.jpg`, … im aktuellen Ordner – insgesamt 50 Stück. - **Fehlerfälle:** nicht genau ein Kommandozeilenargument oder Datei nicht lesbar → Hinweis ausgeben, Rückgabewert `1`. ### So sind die Bilder auf der Karte gespeichert 1. Die Karte ist in **Blöcke zu 512 Byte** eingeteilt. `card.raw` enthält diese Blöcke Byte für Byte hintereinander. 2. Jedes JPEG beginnt **am Anfang eines Blocks** mit diesen vier Bytes: `0xff 0xd8 0xff`, dann ein Byte zwischen `0xe0` und `0xef` (dessen erste vier Bits `1110` sind). 3. Die Bilder liegen **direkt hintereinander**: Ein JPEG reicht über beliebig viele Blöcke bis zu dem Block, in dem das nächste JPEG beginnt – das letzte bis zum Ende der Datei. 4. Vor dem ersten JPEG stehen Blöcke, die zu keinem Bild gehören. Am Ende eines Bildes ist der letzte Block oft mit Nullen aufgefüllt; die dürfen mit in die Datei. Warum gelöschte Fotos überhaupt noch auf der Karte stehen, steht am Ende der Seite unter „Zum Weiterlesen“. ## Aufgabenmaterial Für diese Aufgabe erhalten Sie das Speicherkarten-Abbild, aus dem Sie die "gelöschten" JPEGs rekonstruieren sollen, sowie die C-Datei, in der Sie Ihren Code schreiben sollen. Im Unterschied zu den vorherigen Aufgaben ist in dieser Datei noch keine Funktionalität vorimplementiert! **Aufgabenmaterial herunterladen** Öffnen Sie VS Code entsprechend Ihrem [Setup](https://dev.inf.zone/extras/setup/). Öffnen Sie Ihr Terminalfenster und führen Sie dann `cd` aus. Die Eingabeaufforderung Ihres Terminalfensters sollte wie folgt aussehen: ```bash $ ``` Geben Sie dann ```bash wget https://dev.inf.zone/download/exercises/07/recover.zip ``` ein und führen Sie den Befehl mit der Eingabetaste aus, um eine ZIP-Datei namens `recover.zip` in den aktuellen Ordner herunterzuladen. Achten Sie darauf, dass Sie das Leerzeichen zwischen `wget` und der folgenden URL nicht übersehen, und auch kein anderes Zeichen! Führen Sie jetzt ```bash unzip recover.zip ``` aus, um das ZIP-Archiv in einen Ordner namens `recover` zu extrahieren. Sie brauchen die ZIP-Datei nicht mehr, also können Sie ```bash rm recover.zip ``` ausführen. Antworten Sie mit "y", gefolgt von der Eingabetaste, um die heruntergeladene ZIP-Datei zu entfernen. Führen Sie dann ```bash cd recover ``` aus, um in dieses Verzeichnis zu wechseln. Ihre Eingabeaufforderung sollte nun wie folgt aussehen: ```bash recover/ $ ``` Wenn alles funktioniert hat, sollten Sie nach dem Ausführen von ```bash ls ``` zwei Dateien sehen: `recover.c` und `card.raw`. ## Spezifikation Implementieren Sie ein Programm namens `recover`, das JPEGs aus einem forensischen Abbild wiederherstellt. - Implementieren Sie Ihr Programm in einer Datei namens `recover.c` in einem Verzeichnis namens `recover`. - Ihr Programm sollte genau ein Kommandozeilenargument entgegennehmen, den Namen eines forensischen Abbilds, von dem JPEGs wiederhergestellt werden sollen. - Wenn Ihr Programm nicht mit genau einem Kommandozeilenargument ausgeführt wird, sollte es den Benutzer an die korrekte Verwendung erinnern und `main` sollte `1` zurückgeben. - Wenn das forensische Bild nicht zum Lesen geöffnet werden kann, sollte Ihr Programm den Benutzer darüber informieren und `main` sollte `1` zurückgeben. - Ihr Programm sollte den Inhalt von `card.raw` blockweise einlesen, d.h. der Puffer, den Sie verwenden, muss 512 Byte groß sein (siehe [So sind die Bilder auf der Karte gespeichert](#so-sind-die-bilder-auf-der-karte-gespeichert)). - Die Dateien, die Sie erzeugen, sollten jeweils den Namen `###.jpg` haben, wobei `###` eine dreistellige Dezimalzahl ist, beginnend mit `000` für das erste Bild und aufwärts zählend. - Ihr Programm darf, falls es `malloc` verwendet, keine Memory-Leaks haben. Die Verwendung von `malloc` ist für die Bearbeitung der Aufgabe jedoch nicht zwingend erforderlich. ## Hilfestellung Klicken Sie auf die folgenden Tipps, um einige Ratschläge zu erhalten! **Versuchen Sie das Problem in Pseudocode zu beschreiben** Wenn Sie unsicher sind, wie Sie das größere Problem lösen können, zerlegen Sie es in kleinere Probleme, die Sie wahrscheinlich einfacher lösen können. Diese Aufgabe besteht eigentlich nur aus einer Handvoll kleinerer Probleme: 1. Die Annahme eines einzigen Befehlszeilenarguments: den Namen einer Speicherkarte. 2. Das Öffnen der Speicherkarte. 3. Solange noch Daten auf der Speicherkarte vorhanden sind, die gelesen werden können: 1. JPEGs aus den Daten erstellen. Fügen Sie diese kleineren Probleme nun in Form von Pseudocode als Kommentare ein, um Sie dann nacheinander bearbeiten zu können: ```c #include #include int main(int argc, char *argv[]) { // Accept a single command-line argument // Open the memory card // While there's still data left to read from the memory card // Create JPEGs from the data } ``` **Wandeln Sie den Pseudocode in Code um** Überlegen Sie zunächst, wie Sie ein einzelnes Befehlszeilenargument entgegennehmen können. Wenn der Benutzer das Programm falsch verwendet, sollten Sie ihm die richtige Verwendung des Programms erklären. ```c #include #include int main(int argc, char *argv[]) { // Accept a single command-line argument if (argc != 2) { printf("Usage: ./recover FILE\n"); return 1; } // Open the memory card // While there's still data left to read from the memory card // Create JPEGs from the data } ``` Nun, da Sie die ordnungsgemäße Verwendung geprüft haben, können Sie die Speicherkarte öffnen. Erinnern Sie sich daran, dass Sie die Datei `card.raw` programmatisch mit `fopen` öffnen können, wie im folgenden Code: ```c #include #include int main(int argc, char *argv[]) { // Accept a single command-line argument if (argc != 2) { printf("Usage: ./recover FILE\n"); return 1; } // Open the memory card FILE *card = fopen(argv[1], "r"); // While there's still data left to read from the memory card // Create JPEGs from the data } ``` Prüfen Sie natürlich auch, ob das Öffnen der Datei erfolgreich war! Wenn nicht, informieren Sie den Benutzer und beenden Sie das Programm. Diesen Teil überlassen wir jedoch Ihnen. Als nächstes sollte Ihr Programm die Daten von der Karte (d.h. aus der geöffneten Datei) lesen, bis es keine Daten mehr zu lesen gibt. Währenddessen sollte Ihr Programm jedes einzelne JPEG aus `card.raw` wiederherstellen und als separate Datei in Ihrem aktuellen Arbeitsverzeichnis speichern. Überlegen Sie zunächst, wie Sie die Datei `card.raw` vollständig lesen können. Um Daten aus einer Datei zu lesen, müssen die Daten vorübergehend in einem "Puffer" gespeichert werden. Denken Sie daran, dass `card.raw` die Daten in Blöcken von 512 Byte speichert. Daher macht es Sinn, einen Puffer von 512 Bytes zu erstellen, um die Datenblöcke zu speichern, während sie nacheinander eingelesen werden. Hierfür bietet sich die Verwendung des Typs `uint8_t` aus `stdint.h` an (siehe [Lautstärke](https://dev.inf.zone/exercises/07/volume/#details-zur-umsetzung)), da dieser genau 8 Bits (1 Byte) speichert. Der Typ heißt `uint8_t`, da er eine vorzeichenlose/positive/nicht-negative ganze Zahl speichert, die 8 Bits Platz benötigt (d.h. ein Byte). ```c #include #include #include int main(int argc, char *argv[]) { // Accept a single command-line argument if (argc != 2) { printf("Usage: ./recover FILE\n"); return 1; } // Open the memory card FILE *card = fopen(argv[1], "r"); // Create a buffer for a block of data uint8_t buffer[512]; // While there's still data left to read from the memory card // Create JPEGs from the data } ``` Es ist aber wahrscheinlich _nicht_ die beste Idee, hier 512 als ["magische Zahl"](https://dev.inf.zone/lectures/1-c/short-1-6-magic-numbers/) zu verwenden. Wie könnten Sie dieses Design noch verbessern? Betrachten wir nun, wie man Daten von der Speicherkarte liest. Laut dem [CS50-Handbuch](https://manual.cs50.io/3/fread) gibt `fread` die Anzahl der vollständig gelesenen Elemente zurück; hier ist ein Element 1 Byte groß (zweites Argument), es sollte also entweder `512` oder `0` zurückgeben - vorausgesetzt, dass `card.raw` eine gewisse Anzahl von 512-Byte-Blöcken enthält. Um nach dem Öffnen mit `fopen` jeden Block von `card.raw` zu lesen, sollte eine Schleife wie diese ausreichen (Achtung: auch hier taucht wieder die 512 als "magische Zahl" auf): ```c #include #include #include int main(int argc, char *argv[]) { // Accept a single command-line argument if (argc != 2) { printf("Usage: ./recover FILE\n"); return 1; } // Open the memory card FILE *card = fopen(argv[1], "r"); // Create a buffer for a block of data uint8_t buffer[512]; // While there's still data left to read from the memory card while (fread(buffer, 1, 512, card) == 512) { // Create JPEGs from the data } } ``` Wenn alle Blöcke gelesen wurden, gibt `fread` `0` zurück. In diesem Fall wird die Bedingung zu `false` evaluiert und die Schleife beendet. Der Aufruf von `fread` in `while` wäre auch mit `fread(buffer, 512, 1, card) == 1` möglich. Wissen Sie, warum das so ist? Wir überlassen es Ihnen, herauszufinden, wie Sie JPEGs programmatisch erstellen, während Sie weiterhin aus `card.raw` lesen. Beachten Sie, dass Sie sich dabei nur um die programmatische Erstellung der Dateien kümmern müssen. Die Daten, die eine JPEG-Datei repräsentieren, befinden sich schließlich bereits auf `card.raw` und müssen lediglich identifiziert und kopiert werden. Denken Sie daran, dass Ihr Programm die Dateien, die es ausgibt, nummerieren sollte, indem Sie sie `###.jpg` nennen, wobei `###` eine dreistellige Dezimalzahl von `000` aufwärts ist. Machen Sie sich mit [`sprintf`](https://manual.cs50.io/3/sprintf) vertraut und beachten Sie, dass `sprintf` eine formatierte Zeichenkette an einer Stelle im Speicher speichert. Wie viele Bytes sollten Sie angesichts des vorgeschriebenen Formats `###.jpg` für den Dateinamen eines JPEGs für diesen String reservieren? (Vergessen Sie nicht das NUL-Zeichen!) Und denken Sie natürlich daran, jede Datei, die Sie mit `fopen` geöffnet haben, mit `fclose` wieder zu schließen! **Vergleich der ersten vier Bits eines Bytes mit dem bitweisen UND-Operator `&`** Um eine [JPEG-Signatur](#so-sind-die-bilder-auf-der-karte-gespeichert) zu erkennen, können Sie in C Werte direkt in ihrer hexadezimalen Darstellung vergleichen, zum Beispiel `if (buffer[0] == 0xff)`, wenn `buffer[0]` ein Byte ist. `0x` markiert auch in C den Beginn einer hexadezimalen Zahl. Doch wie prüft man, ob die ersten vier Bits des vierten Bytes `1110` (bzw. `0xe`) sind? Alle 16 möglichen Werte mit `||` zu verknüpfen ginge, ist aber unelegant. Im Short [Operatoren](https://dev.inf.zone/lectures/1-c/short-1-2-operatoren/) (ab 12:09) kommt die bitweise UND-Operation vor (ein einfaches `&` zwischen zwei Werten). Wenn im vierten Byte nach den ersten vier Bits immer `0000` folgte, könnten wir einfach mit `buffer[3] == 0xe0` vergleichen. Wenn Sie möchten, knobeln Sie zuerst selbst, wie man das mit `&` erreicht. Hier ist die Antwort: ```c ((buffer[3] & 0xf0) == 0xe0) ``` Was in diesem Ausdruck passiert? Gehen wir es der Reihe nach durch: ```c (buffer[3] & 0xf0) ``` Mit dem `&` werden die beiden Variablen bitweise nach der UND-Logik ausgewertet. Durch die Verwendung der hexadezimalen Ziffer `f` für die ersten vier Bits (also `1111`) wird sichergestellt, dass die ersten vier Bits aus `buffer[3]` unverändert bleiben. Denn: Wenn z.B. das erste Bit von `buffer[3]` `0` ist, dann ist `0 & 1` auch wieder `0`. Im Falle einer `1` ist `1 & 1` dann wieder `1`, sodass auch in diesem Fall das Bit von `buffer[3]` unverändert bleibt. Durch die Verwendung der hexadezimalen Ziffer `0` für die zweiten vier Bits (also `0000`) wird dagegen sichergestellt, dass die zweiten vier Bits aus `buffer[3]` immer jeweils `0` sind, d.h. `0000`. Denn: Wenn das fünfte Bit von `buffer[3]` `0` ist, dann ist `0 & 0` `0` und wenn es `1` ist, wird aus `1 & 0` letztlich auch wieder eine `0`. Daher ist für den abschließenden Vergleich nur entscheidend, welche Werte die ersten vier Bits des vierten Bytes von `buffer` haben: ```c ((buffer[3] & 0xf0) == 0xe0) ``` Der Vergleich mit `0xe0` wird also immer dann als `true` ausgewertet, wenn die ersten vier Bits von `buffer[3]` gleich `1110` (also `0xe`) sind. Denn die ersten vier Bits gehen **unverändert** aus der bitweisen UND-Operation hervor, während die zweiten vier Bits durch diese **immer** auf `0000` gesetzt werden. **Halten Sie Ihr Arbeitsverzeichnis sauber** Wahrscheinlich sind die JPEGs, die der erste Entwurf Ihres Programms erstellt, nicht korrekt. (Wenn Sie sie öffnen und nichts sehen, sind sie wahrscheinlich nicht korrekt!) Führen Sie den folgenden Befehl aus, um alle JPEGs in Ihrem aktuellen Arbeitsverzeichnis zu löschen: ```bash rm *.jpg ``` Wenn Sie nicht bei jeder Löschung zur Bestätigung aufgefordert werden möchten, führen Sie stattdessen den folgenden Befehl aus: ```bash rm -f *.jpg ``` Seien Sie jedoch vorsichtig mit der `-f` Option, da diese das Löschen "erzwingt", ohne Sie zur Bestätigung aufzufordern. ## Testen ### Programm ausführen ```bash ./recover card.raw ``` Um zu überprüfen, ob die JPEGs, die Ihr Programm erstellt, korrekt sind, machen Sie einfach einen Doppelklick und schauen Sie nach! Wenn jedes Foto intakt erscheint, war Ihre Wiederherstellung wahrscheinlich erfolgreich! ### Korrektheit Führen Sie in Ihrem Terminal den folgenden Befehl aus, um die Korrektheit Ihrer Arbeit zu überprüfen: ```bash check50 -l inf-zone/exercises/2026/recover ``` ### Style Führen Sie den folgenden Befehl aus, um den Stil Ihres Codes mit `style50` zu analysieren: ```bash style50 recover.c ``` ## Abgeben Geben Sie im Ordner `recover` ab: ```bash inf upload recover ``` Danach sehen Sie, welche Tests Ihr Programm besteht und ob die Übung für die Bonuspunkte zählt. Wie Sie `inf` installieren und sich anmelden, steht unter [Abgeben mit `inf`](https://dev.inf.zone/faq/uebung-solutions/#inf-installieren). ## Zum Weiterlesen: Gelöscht heißt nicht weg Für die Lösung der Aufgabe nicht nötig. Zur Vorbereitung dieser Aufgabe wurden Fotos rund um den Harvard Campus gemacht, die alle von einer Digitalkamera als JPEGs auf einer Speicherkarte gespeichert wurden. Leider haben wir sie alle irgendwie gelöscht! Glücklicherweise bedeutet "gelöscht" in der Computerwelt nicht wirklich "gelöscht", sondern eher "vergessen". Auch wenn die Kamera anzeigt, dass die Karte jetzt leer ist, sind wir uns ziemlich sicher, dass das nicht ganz stimmt. Wir hoffen, dass Sie ein Programm schreiben können, das die Fotos für uns wiederherstellt! ### JPEG-Signaturen Zwar sind JPEGs komplizierter als BMPs, aber auch JPEGs haben "Signaturen", d.h. bestimmte Muster von Bytes, die sie von anderen Dateiformaten unterscheiden können. Die ersten drei Bytes eines JPEGs haben immer die folgenden Werte: ```plaintext 0xff 0xd8 0xff ``` Diese erscheinen immer in genau dieser Reihenfolge am Anfang jeder JPEG-Datei. Das Präfix `0x` bedeutet, dass die beiden folgenden Ziffern als hexadezimale Werte zu interpretieren sind. Das vierte Byte hingegen ist entweder `0xe0`, `0xe1`, `0xe2`, `0xe3`, `0xe4`, `0xe5`, `0xe6`, `0xe7`, `0xe8`, `0xe9`, `0xea`, `0xeb`, `0xec`, `0xed`, `0xee` oder `0xef`. Mit anderen Worten, die ersten vier Bits des vierten Bytes sind `1110` (d.h. `0xe` in Hexadezimal). Wenn Sie dieses 4-Byte-Muster auf einem Datenträger finden, auf dem bekanntermaßen Fotos gespeichert werden (z.B. auf einer Speicherkarte), stehen die Chancen gut, dass sie den Beginn eines JPEGs markieren. Allerdings können diese Muster auf manchen Datenträgern auch rein zufällig vorkommen. Die Datenwiederherstellung ist also keine exakte Wissenschaft. ### FAT-Dateisystem Glücklicherweise speichern Digitalkameras die Fotos in der Regel zusammenhängend auf Speicherkarten, d.h. jedes Foto wird unmittelbar nach dem zuvor aufgenommenen gespeichert. Dementsprechend markiert der Anfang eines JPEGs normalerweise das Ende eines anderen. Digitalkameras initialisieren die Karten häufig mit einem FAT-Dateisystem, dessen "Blockgröße" 512 Byte (B) beträgt. Das bedeutet, dass diese Kameras nur in Einheiten von 512 B auf die Karte schreiben. Ein Foto mit einer Größe von 1 MB (d.h. 1.048.576 B) belegt also 1048576 ÷ 512 = 2048 "Blöcke" auf einer Speicherkarte. Die gleiche Anzahl von Blöcken wird aber auch von einem Foto belegt, das z.B. ein Byte kleiner ist (d.h. 1.048.575 B)! In diesem Fall ist der letzte Block nicht vollständig belegt. Dort wäre theoretisch noch 1 B frei. Dieser "vergeudete" Platz auf der Festplatte wird "slack space" genannt. Wenn eine Datei den letzten verwendeten Block nicht vollständig belegt, bedeutet dies, dass ursprünglich an dieser Stelle stehende Daten auch nicht bis zum letzten Byte überschrieben werden. Forensische Ermittler suchen daher im Schlupfspeicher oft nach Resten verdächtiger Daten. Was können wir aus all diesen Informationen mitnehmen? Nun, es sollte möglich sein, ein Programm zu schreiben, das eine Kopie der gelöschten Speicherkarte durchläuft und nach JPEG-Signaturen sucht. Jedes Mal, wenn Sie eine Signatur finden, können Sie eine neue Datei zum Schreiben öffnen und beginnen, diese Datei mit Bytes von der Speicherkarte zu füllen, und diese Datei erst schließen, wenn Sie auf eine andere Signatur stoßen. Anstatt die Bytes der Speicherkarte einzeln zu lesen, können Sie auch 512 Bytes (d.h. die Blockgröße des FAT-Dateisystems) auf einmal in einen Puffer einlesen, um die Effizienz zu erhöhen. Dank FAT können Sie sich darauf verlassen, dass die Signaturen von JPEGs "blockorientiert" sind. Das heißt, Sie brauchen nur in den ersten vier Bytes eines Blocks nach diesen Signaturen zu suchen. Natürlich können JPEGs mehrere aufeinanderfolgende Blöcke umfassen. Andernfalls könnte kein JPEG größer als 512 B sein. Das letzte Byte eines JPEGs muss jedoch nicht unbedingt am Ende eines Blocks stehen. Denken Sie an die Möglichkeit des "slack space". Aber kein Grund zur Sorge. Da diese Speicherkarte brandneu war, bevor die Fotos gemacht wurden, wurde sie wahrscheinlich vom Hersteller "genullt" (d.h. mit 0en gefüllt), so dass jeder "slack space" mit 0en gefüllt sein wird. Es ist in Ordnung, wenn diese 0en in den JPEGs auftauchen, die Sie wiederherstellen; sie sollten dennoch ansehbar sein. Natürlich können wir nicht jedem Studierenden eine Speicherkarte zur Verfügung stellen. Deshalb haben wir ein "forensisches Abbild" der Karte erstellt und ihren Inhalt Byte für Byte in einer Datei namens `card.raw` gespeichert (siehe [Aufgabenmaterial](#aufgabenmaterial)). Damit Sie nicht unnötig Zeit damit verschwenden, über Millionen von 0en zu iterieren, haben wir nur den Anfang der Speicherkarte gesichert (knapp 500 KB). Insgesamt sollten Sie 50 JPEGs auf dem Abbild finden.