Tags

, , , , , , , , , , , ,

Course: Harvard’s CS50

Problem Set 5: Forensics

pset5 is quite easy (IMHO) to complete and its potential utility is obvious. hacker5 is quite a bit tougher, but if you take a methodical approach to it, It can become manageable. A hack-things-together approach (like I ended up with at hacker3-game of fifteen), may not work well here.

By now you already are, or you will become comfortable with: structs, pointers and hexadecimal.

For pset5/hacker5 you get to:

    • Learn about data storage (clusters, blocks..)
    • Use xxd.
    • Deal with data file I/O.
    • Recover pictures from an ‘accidentally’ formatted memory card.
    • Understand and modify Bitmaps (.bmp)
      • Resize (enlarge) Bitmaps.
      • (hacker5:) Resize (resample) Bitmaps.

pset5

whodunit

Reveal the hidden message in clue.bmp

whodunit.c (view | download)

resize

Resize (enlarge only) a bmp image. Don’t forget to: create or (modify) the header for the new bmp file, Handle the new file’s padding.

NOTE: Uhhm, this probably should not work, but it does (probably due to -std=c99, I am not sure.)… Line 103 has a run-time array declaration. This should be easy to fix, modify it to use a pointer and malloc. Or skip to the awesome bilinear version below.

resize.c (view | download)

CSI

Recover .jpg files from an ‘accidentally’ formatted memory card. This one’s quite easy because:

  • You are told the files are not fragmented at all.
  • The storage medium’s block size is known.
  • The storage medium holds only .jpg files and nothing else.

recover.c (view | download)

hacker5

Before starting with that I did rotate.c.

Train of thought.

  • Red, Green, Blue values that form a pixel
  • Pixels form a scanline. (or: image width * pixel = scanline)
  • Scanlines form an image body (or: image height * scanline = body)

Of course to get a usable image format out of that we have to have some metadata, ie. information headers and other optimization-oriented specifications like padding on scanlines etc; all that can be added later. The general idea gives us something like this:


typedef struct
{
 uint32_t hDimension;
 RGBTRIPLE triple[];
} SCANLINE;

typedef struct
{
 uint32_t vDimension;
 SCANLINE *scanlines[];
} BODY;

typedef struct
{
 BITMAPFILEHEADER *bf;
 BITMAPINFOHEADER *bi;
 BODY *bd;
} BITMAP24;

Resize

This one took some research into image scaling algorithms. But it was worth every minute of it!
The source contains two resampling algorithms: Nearest neightbour and Bilinear interpolation. You can toggle between them in resize.h.

resize.c (view | download)
resize.h (view | download)

Extras

For me this was a stepping stone before making hacker5’s resize.c. I used it as an exercise, to get more comfortable with bitmaps.

rotate.c (view | download)
rotate.h (view | download)

Get bmp.h from the problem set’s distribution packages.

Enjoy!

Advertisements