Practice Exercise #4

I once had an array of bytes, named buf. The bytes were uninitialized, so had random values. I then hid a string in buf, encoding it using a doubly linked list. Each element of the list contained one character, and told me how to find the next element. More particularly, each element of the list was an instance of this structure 

typedef struct element_st {
  uint32_t next;
  uint32_t prev;
  char     c;
} element;
An element structure could be located starting at any byte offset in buf. The next and prev values are byte offsets into buf, except that value 0 means null (no next element). For instance, if next equals 102, it means that the next element structure is stored in the bytes that begin at &buf[102]. The prev pointer of the first element is null, and the next element of the last element is null. So long as I remember where the first element of the linked list is, I can recover my string by traversing the linked list.

I lost the information about where the first element is. But, I still have the data bytes, in a file.

Write a C program that will recover my string by:

  • using open (man 2 open) to open a binary data file, fstat to determine its length, and read (man 2 read) to read the file contents into an appropriately sized, malloc'ed, in memory buffer.
  • applying some heuristics to find my string in among all those random bytes.
Your code should be in a single file named findData.c, and should have behavior like this: 
bash$ ./findData secretFile.txt
Don't lose the location of the head element or you won't be able to find this string.
bash$ ./findData findData.c
No string found
bash$ ./findData /usr/bin/gcc
@
Sample files that contain embedded strings are in directory ex04_files.