Wiederherstellung

Aufgabe

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!

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!

$

wget https://inf.zone/download/exercises/04/recover.zip

unzip recover.zip

rm recover.zip

cd recover

recover/ $

ls

Hintergrund

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:

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). Damit Sie nicht unnötig Zeit damit verschwenden, über Millionen von 0en zu iterieren, haben wir nur die ersten paar Megabytes der Speicherkarte gesichert. Insgesamt sollten Sie 50 JPEGs auf dem Abbild finden.

Details zur Umsetzung

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 FAT-Dateisystem). Sie können z.B. ein entsprechend großes Array des Typs uint8_t - deklariert in stdint.h - verwenden, da dieser genau 8 Bits (1 Byte) speichert (siehe Lautstärke).
  • Um eine JPEG-Signatur zu identifizieren, können Sie in C Werte direkt in ihrer hexadezimalen Darstellung vergleichen, d.h. zum Beispiel if (buffer[0] == 0xff), wenn buffer[0] einen Inhalt der Größe “1” Byte repräsentiert. 0x markiert also auch in C den Beginn einer hexadezimalen Zahlendarstellung. Wie können Sie diese Möglichkeit nutzen, um am Anfang eines Datenblockes zu prüfen, ob mit diesem eine neue JPEG-Datei beginnt?
  • Doch wie kann geprüft werden, ob die ersten vier Bits des vierten Bytes 1110 (bzw. 0xe in Hexadezimal) sind? Nun, alle 16 möglichen Hex-Werte zu vergleichen und mit dem || Operator zu verknüpfen wäre eine Möglichkeit - aber etwas unelegant. Wenn Sie noch einmal das Short Operatoren (ab 12:09) ansehen, erinnern Sie sich vielleicht an die bitweise UND-Operation (ein einfaches & zwischen zwei Variablen). Wenn wir sicherstellen könnten, dass im vierten Byte nach den ersten vier Bits immer die Bits 0000 folgen, könnten wir zum Vergleichen des vierten Bytes einfach buffer[3] == 0xe0 verwenden. Wenn Sie möchten, können Sie ein wenig knobeln, wie man das mit dem &-Operator bewerkstelligen kann - eine Erklärung dazu finden Sie aber auch unter dem entsprechenden Aufklapp-Element in der Hilfestellung.
• 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.
  • Machen Sie sich mit sprintf vertraut und beachten Sie, dass sprintf eine formatierte Zeichenkette an einer Stelle im Speicher speichert. Wie viele Bytes, d.h. chars, sollten Sie angesichts des vorgeschriebenen Formats ###.jpg für den Dateinamen eines JPEGs für diesen String reservieren? (Vergessen Sie nicht das NUL-Zeichen!)
• 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!

#include <stdio.h>
#include <stdlib.h>

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
}

#include <stdio.h>
#include <stdlib.h>

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
}

#include <stdio.h>
#include <stdlib.h>

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
}

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

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
}

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

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

    }
}

((buffer[3] & 0xf0) == 0xe0)

(buffer[3] & 0xf0)

((buffer[3] & 0xf0) == 0xe0)

rm *.jpg

rm -f *.jpg

Testen

Programm ausführen

./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:

check50 -l cs50/problems/2024/x/recover

Style

Führen Sie den folgenden Befehl aus, um den Stil Ihres Codes mit style50 zu analysieren:

style50 recover.c