CS50-MCZ

Recover

Problema a Resolver

Implemente um programa que recupere arquivos JPEG de uma imagem forense, como mostrado abaixo.

$ ./recover card.raw

Contexto

Antecipando este problema, passamos os últimos dias tirando fotos no campus, todas salvas em uma câmera digital como JPEGs em um cartão de memória. Infelizmente, acabamos deletando todas elas! Felizmente, no mundo da informática, "deletado" geralmente não significa "deletado" tanto quanto "esquecido". Mesmo que a câmera insista que o cartão agora está em branco, temos certeza de que isso não é totalmente verdade. Na verdade, estamos esperando (bem, esperando mesmo!) que você possa escrever um programa que recupere as fotos para nós!

Embora os arquivos JPEG sejam mais complicados do que os BMPs, eles têm "assinaturas", padrões de bytes que podem distingui-los de outros formatos de arquivo. Especificamente, os primeiros três bytes dos arquivos JPEG são

0xff 0xd8 0xff

Do primeiro ao terceiro byte, da esquerda para a direita. Enquanto isso, o quarto byte é um dos seguintes: 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, ou 0xef. Em outras palavras, os primeiros quatro bits do quarto byte são 1110.

É provável que, se você encontrar esse padrão de quatro bytes em mídias conhecidas por armazenar fotos (por exemplo, meu cartão de memória), eles demarcam o início de um arquivo JPEG. Para ser justo, você pode encontrar esses padrões em alguns discos por puro acaso, portanto, a recuperação de dados não é uma ciência exata.

Felizmente, as câmeras digitais tendem a armazenar fotografias contiguamente em cartões de memória, em que cada foto é armazenada imediatamente após a foto anteriormente tirada. Consequentemente, o início de um JPEG geralmente demarca o fim de outro. No entanto, as câmeras digitais geralmente inicializam cartões com um sistema de arquivos FAT cujo "tamanho do bloco" é de 512 bytes (B). A implicação é que essas câmeras só gravam nesses cartões em unidades de 512 B. Uma foto que tenha 1 MB (ou seja, 1.048.576 B) ocupa assim 1048576 ÷ 512 = 2048 "blocos" em um cartão de memória. Mas o mesmo ocorre com uma foto que seja, por exemplo, um byte menor (ou seja, 1.048.575 B)! O espaço desperdiçado no disco é chamado de "espaço ocioso". Investigadores forenses muitas vezes examinam o espaço ocioso em busca de vestígios de dados suspeitos.

A implicação de todos esses detalhes é que você, o investigador, provavelmente pode escrever um programa que itera sobre uma cópia do meu cartão de memória, procurando pelas assinaturas dos arquivos JPEG. Cada vez que você encontrar uma assinatura, pode abrir um novo arquivo para escrita e começar a preencher esse arquivo com bytes do meu cartão de memória, fechando esse arquivo somente quando encontrar outra assinatura. Além disso, em vez de ler os bytes do meu cartão de memória um de cada vez, você pode ler 512 deles de uma vez em um buffer, por questões de eficiência. Graças ao sistema de arquivos FAT, você pode confiar que as assinaturas dos arquivos JPEG estarão "alinhadas com o bloco". Ou seja, você só precisa procurar essas assinaturas nos primeiros quatro bytes de um bloco.

Perceba, é claro, que os arquivos JPEG podem se estender por blocos contíguos. Caso contrário, nenhum arquivo JPEG poderia ser maior do que 512 B. Mas o último byte de um arquivo JPEG pode não estar no final de um bloco. Lembre-se da possibilidade de espaço livre. Mas não se preocupe. Como este cartão de memória era novo quando comecei a tirar fotos, é provável que ele tenha sido "zerado" (ou seja, preenchido com 0s) pelo fabricante, o que significa que qualquer espaço livre será preenchido com 0s. Está tudo bem se esses 0s finais acabarem nos arquivos JPEG que você recuperar; eles ainda devem ser visualizáveis.

Agora, eu só tenho um cartão de memória, mas há muitos de vocês! Então eu criei uma "imagem forense" do cartão, armazenando seu conteúdo, byte por byte, em um arquivo chamado card.raw. Para que você não perca tempo iterando desnecessariamente por milhões de 0s, eu só criei a imagem dos primeiros poucos megabytes do cartão de memória. Mas você deve encontrar, em última análise, que a imagem contém 50 arquivos JPEG.

Começando

Acesse o cs50.dev, clique na sua janela do terminal e execute cd sozinho. Você deve encontrar que o prompt da sua janela do terminal se assemelha ao abaixo:

$

Em seguida, execute

wget https://cdn.cs50.net/2023/fall/psets/4/recover.zip

Para baixar um arquivo ZIP chamado recover.zip em seu codespace.

Em seguida, execute

unzip recover.zip

para criar uma pasta chamada recover. Você não precisa mais do arquivo ZIP, então pode executar

rm recover.zip

e responda com "y" seguido de Enter no prompt para remover o arquivo ZIP que você baixou.

Agora digite

cd recover

seguido de Enter para mover-se para (ou seja, abrir) esse diretório. Seu prompt agora deve se parecer com o abaixo.

recover/ $

Se tudo ocorreu com sucesso, você deve executar:

ls

e veja dois arquivo chamados recover.c e 'card.raw'. Executando code runoff.c deverá abrir o arquivo onde você irá digitar o seu código para este conjunto de problemas. Se não, refaça seus passos e veja se consegue determinar onde errou!

Especificação

Implemente um programa chamado recover que recupera arquivos JPEG de uma imagem forense.

• Implemente seu programa em um arquivo chamado recover.c em um diretório chamado recover.
• Seu programa deve aceitar exatamente um argumento de linha de comando, o nome de uma imagem forense da qual recuperar arquivos JPEG.
• Se o seu programa não for executado com exatamente um argumento de linha de comando, ele deve lembrar o usuário do uso correto e main deve retornar 1.
• Se a imagem forense não puder ser aberta para leitura, seu programa deve informar o usuário disso, e main deve retornar 1.
• Os arquivos que você gerar devem ser nomeados como ###.jpg, onde ### é um número decimal de três dígitos, começando com 000 para a primeira imagem e contando para cima.
• Seu programa, se usar malloc, não deve vazar memória.

Uso

Seu programa deve se comportar conforme o exemplo abaixo:

$ ./recover
  Usage: ./recover IMAGE
  

onde IMAGE é o nome da imagem forense. Por exemplo:

$ ./recover card.raw
  

Dicas

Lembre-se de que você pode abrir o arquivo card.raw programaticamente com fopen, assim como abaixo, desde que argv[1] exista.

FILE *file = fopen(argv[1], "r");

Quando executado, seu programa deve recuperar todos os arquivos JPEG de card.raw, armazenando cada um como um arquivo separado em seu diretório de trabalho atual. Seu programa deve numerar os arquivos que ele produz ao nomear cada um como ###.jpg, onde ### é um número decimal de três dígitos a partir de 000 em diante. Torne-se amigo de sprintf e observe que sprintf armazena uma string formatada em um local na memória. Dado o formato prescrito de ###.jpg para o nome do arquivo JPEG, quantos bytes você deve alocar para essa string? (Não se esqueça do caractere NUL!)

Não é necessário tentar recuperar os nomes originais dos arquivos JPEG. Para verificar se os JPEGs que seu programa produziu estão corretos, basta clicar duas vezes e dar uma olhada! Se cada foto aparecer intacta, sua operação provavelmente foi bem-sucedida!

No entanto, é provável que os JPEGs que o primeiro rascunho do seu código produzir não estejam corretos. (Se você abri-los e não ver nada, provavelmente não estão corretos!) Execute o comando abaixo para excluir todos os arquivos JPEG no seu diretório de trabalho atual.

$ rm *.jpg

Se você preferir não ser solicitado a confirmar cada exclusão, execute o comando abaixo em vez disso.

$ rm -f *.jpg

Apenas tenha cuidado com o interruptor -f, pois ele "força" a exclusão sem solicitar confirmação.

Se você deseja criar um novo tipo para armazenar um byte de dados, pode fazê-lo através do código abaixo, que define um novo tipo chamado BYTE como um uint8_t (um tipo definido em stdint.h, representando um inteiro não assinado de 8 bits).

typedef uint8_t BYTE;

Lembre-se também que você pode ler dados de um arquivo usando fread, que lerá dados de um arquivo para uma localização na memória. Conforme sua página do manual, fread retorna o número de bytes que leu, caso em que deverá retornar 512 ou 0, dado que card.raw contém algum número de blocos de 512 bytes. Para ler todos os blocos de card.raw, depois de abri-lo com fopen, deve ser suficiente usar um loop como:

while (fread(buffer, 1, BLOCK_SIZE, raw_file) == BLOCK_SIZE)
{


}  

Dessa forma, assim que fread retornar 0 (o que é efetivamente false), seu loop terminará.

Testando

Execute o abaixo para avaliar a correção do seu código usando check50. Mas certifique-se de compilar e testar também!

check50 cs50/problems/2024/x/recover

Execute o código abaixo para avaliar o estilo do seu código usando style50.

style50 recover.c

Como Submeter

No seu terminal, execute o comando abaixo para submeter o seu trabalho.

submit50 cs50/problems/2024/x/recover