Purpose: To provide an introduction to structured programming using the C/C++ language.
CS 2505 Computer Organization I C07: Chained Records in Memory
Version 5.00 This is a purely individual assignment! 1
C Programming Pointer Accesses to Memory and Bitwise Manipulation
Part 1 [80%] Untangling Clear Data Records in Memory
Here is a hexdump[1] of a memory region containing a scrambled quotation:
XXXXXXXXXX XXXXXXXXXX A B C D E F
------------------------------------------------------------------------------
XXXXXXXXXX0f 3a 00 69 6e XXXXXXXXXX65 6e 63 |4..:.indifferenc|
XXXXXXXXXX3f XXXXXXXXXX XXXXXXXXXX6f |e.?.be.G.by...fo|
XXXXXXXXXX0a XXXXXXXXXX6e 61 6c XXXXXXXXXX75 |r.h.penalty.t.pu|
XXXXXXXXXX6c XXXXXXXXXX XXXXXXXXXX2b 00 74 6f 08 |blic.!.The.+.to.|
XXXXXXXXXX75 6c XXXXXXXXXX4e XXXXXXXXXX6c 07 55 |..ruled.N.evil.U|
XXXXXXXXXX6d 65 6e 2e 05 5a 00 2d 2d XXXXXXXXXX6c 61 |.men..Z.--...Pla|
XXXXXXXXXX6f XXXXXXXXXX6d 65 6e XXXXXXXXXX6f 6f 64 05 |to...men.b.good.|
XXXXXXXXXX6f 0a 7e XXXXXXXXXX XXXXXXXXXX6f |..to.~.affairs.o|
XXXXXXXXXX06 1b XXXXXXXXXX |.is...pay|
------------------------------------------------------------------------------
XXXXXXXXXX XXXXXXXXXX A B C D E F
The first two bytes of the memory region contain the offset at which you will begin processing records: 0x0034.
This offset of the first record is followed by a sequence of word records, each consisting of a positive integer value, another
positive integer value, and a sequence of characters:
Length of record Offset of next record Characters in word
uint8_t uint16_t chars
The first value in each record specifies the total number of bytes in the record. Since words are relatively short, this value
will be stored as a uint8_t, which has a range of 0 – 255. The record length is followed immediately by a uint16_t
value specifying the offset of the next word record in the list. This is followed by a sequence of ASCII codes[2] for the
characters that make up the word. (The term "word" is used a bit loosely here.) There is no terminator after the final
character of the string, so be careful about that.
Note that the length of the record depends upon the number of characters in the word, and so these records vary in length.
That's one reason we must store the offset for each record.
In the case above, the offset of the first record is 0x0034[3]. The first word record consists of the bytes:
XXXXXXXXXX
The length of the first record is 0x06 or 6 in base-10, which means that the string is 3 characters long, since the length field
occupies 1 byte and the offset of the next record occupies 2 bytes. The ASCII codes are XXXXXXXXXX, which represent the
characters "The". The offset of the next record is 0x0021.
The second word record consists of the bytes:
0a XXXXXXXXXX6e 61 6c 74 79
The length is 0x0a (10 in base-10), so the string is 7 characters long (the ASCII codes represent "penalty"), and the next
word record is at the offset 0x0068. And so forth...
CS 2505 Computer Organization I C07: Chained Records in Memory
Version 5.00 This is a purely individual assignment! 2
This assignment requires implementing a function that can be executed in two modes, controlled by a switch specified by a
parameter to the function:
enum _DataFormat {CLEAR, ENCRYPTED};
typedef enum _DataFormat DataFormat;
struct _WordRecord {
uint16_t offset;
offset at which word record was found in memory
char* word;
dynamically alloc'd C-string containing the "word"
};
typedef struct _WordRecord WordRecord;
**
* Untangle() parses a chain of records stored in the memory region pointed
* to by pBuffer, and stores WordRecord objects representing the given data
* into the a
ay supplied by the caller.
*
* Pre: Fmt == CLEAR or ENCRYPTED
* XXXXXXXXXXpBuffer points to a region of memory formatted as specified
* XXXXXXXXXXwordList points to an empty a
ay large enough to hold all the
* XXXXXXXXXXWordRecord objects you'll need to create
* Post: wordList[0:nWords-1] hold WordRecord objects, where nWords is
* XXXXXXXXXXis the value returned by Untangle()
* Returns: the number of "words" found in the supplied quotation.
*/
uint8_t Untangle(DataFormat Fmt, const uint8_t* pBuffer, WordRecord* const wordlist);
The function will access a scrambled quotation, stored in a memory region pointed to by pBuffer. The organization of
the memory region is described in detail below. The function will analyze that memory region, and reconstruct the
quotation by creating a sequence of WordRecord objects and storing them in an a
ay provided by the caller.
You will also implement a function that will deallocate all the dynamic content of such an a
ay of WordRecord objects:
**
* Deallocates an a
ay of WordRecord objects.
*
* Pre: wordList points to a dynamically-allocated a
ay holding nWords
* XXXXXXXXXXWordRecord objects
* Post: all dynamic memory related to the a
ay has been freed
*/
void clearWordRecords(WordRecord* const wordList, uint8_t nWords);
Let's consider how to interpret the hexdump shown earlier:
XXXXXXXXXX XXXXXXXXXX A B C D E F
------------------------------------------------------------------------------
XXXXXXXXXX0f 3a 00 69 6e XXXXXXXXXX65 6e 63 |4..:.indifferenc|
XXXXXXXXXX3f XXXXXXXXXX XXXXXXXXXX6f |e.?.be.G.by...fo|
XXXXXXXXXX0a XXXXXXXXXX6e 61 6c XXXXXXXXXX75 |r.h.penalty.t.pu|
XXXXXXXXXX6c XXXXXXXXXX XXXXXXXXXX2b 00 74 6f 08 |blic.!.The.+.to.|
XXXXXXXXXX75 6c XXXXXXXXXX4e XXXXXXXXXX6c 07 55 |..ruled.N.evil.U|
XXXXXXXXXX6d 65 6e 2e 05 5a 00 2d 2d XXXXXXXXXX6c 61 |.men..Z.--...Pla|
XXXXXXXXXX6f XXXXXXXXXX6d 65 6e XXXXXXXXXX6f 6f 64 05 |to...men.b.good.|
XXXXXXXXXX6f 0a 7e XXXXXXXXXX XXXXXXXXXX6f |..to.~.affairs.o|
XXXXXXXXXX06 1b XXXXXXXXXX |.is...pay|
------------------------------------------------------------------------------
XXXXXXXXXX XXXXXXXXXX A B C D E F
CS 2505 Computer Organization I C07: Chained Records in Memory
Version 5.00 This is a purely individual assignment! 3
The complete quotation, with word record offsets, is:
0x0037: The
0x0024: penalty
0x006B: good
0x0065: men
0x0086: pay
0x001E: for
0x0005: indifference
0x003D: to
0x002E: public
0x0077: affairs
0x0081: is
0x0072: to
0x0014: be
0x0042: ruled
0x0019: by
0x004A: evil
0x0051: men.
0x0058: --
0x005D: Plato
To indicate the end of the sequence of word records, the final word record specifies that its successor is at an offset of 0:
XXXXXXXXXX6c 61 74 6f
Offset 0 cannot be that of a "real" word record, since that's the offset of the pointer to the first word record.
For Part 1, your function will be passed the value CLEAR for the parameter Fmt.
You will use the WordRecord data type shown earlier to represent a parsed word record. You will create one of these
struct variables whenever you parse a word record, and place that struct variable into an a
ay supplied by the caller
of your function[4].
Part 2 [20%] Untangling Mildly Encrypted Data Records in Memory
Read the posted notes on bitwise operations in C, and the related sections in your C reference.
For this case, your function will be passed the value ENCRYPTED for the parameter Fmt.
The memory region pointed to by pBuffer will be formatted in exactly the same way as for case 1, except that the bytes
that