.
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: 0 1 2 3 4 5 6 7 8 9 A B C D E F ------------------------------------------------------------------------------ 00000000 34 00 0f 3a 00 69 6e 64 69 66 66 65 72 65 6e 63 |4..:.indifferenc| 00000010 65 05 3f 00 62 65 05 47 00 62 79 06 02 00 66 6f |e.?.be.G.by...fo| 00000020 72 0a 68 00 70 65 6e 61 6c 74 79 09 74 00 70 75 |r.h.penalty.t.pu| 00000030 62 6c 69 63 06 21 00 54 68 65 05 2b 00 74 6f 08 |blic.!.The.+.to.| 00000040 16 00 72 75 6c 65 64 07 4e 00 65 76 69 6c 07 55 |..ruled.N.evil.U| 00000050 00 6d 65 6e 2e 05 5a 00 2d 2d 08 00 00 50 6c 61 |.men..Z.--...Pla| 00000060 74 6f 06 83 00 6d 65 6e 07 62 00 67 6f 6f 64 05 |to...men.b.good.| 00000070 11 00 74 6f 0a 7e 00 61 66 66 61 69 72 73 05 6f |..to.~.affairs.o| 00000080 00 69 73 06 1b 00 70 61 79 |.is...pay| ------------------------------------------------------------------------------ 0 1 2 3 4 5 6 7 8 9 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: 06 21 00 54 68 65 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 54 68 65, which represent the characters "The". The offset of the next record is 0x0021. The second word record consists of the bytes: 0a 68 00 70 65 6e 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 array supplied by the caller. * * Pre: Fmt == CLEAR or ENCRYPTED * pBuffer points to a region of memory formatted as specified * wordList points to an empty array large enough to hold all the * WordRecord objects you'll need to create * Post: wordList[0:nWords-1] hold WordRecord objects, where nWords is * is 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 array provided by the caller. You will also implement a function that will deallocate all the dynamic content of such an array of WordRecord objects: /** * Deallocates an array of WordRecord objects. * * Pre: wordList points to a dynamically-allocated array holding nWords * WordRecord objects * Post: all dynamic memory related to the array has been freed */ void clearWordRecords(WordRecord* const wordList, uint8_t nWords); Let's consider how to interpret the hexdump shown earlier: 0 1 2 3 4 5 6 7 8 9 A B C D E F ------------------------------------------------------------------------------ 00000000 34 00 0f 3a 00 69 6e 64 69 66 66 65 72 65 6e 63 |4..:.indifferenc| 00000010 65 05 3f 00 62 65 05 47 00 62 79 06 02 00 66 6f |e.?.be.G.by...fo| 00000020 72 0a 68 00 70 65 6e 61 6c 74 79 09 74 00 70 75 |r.h.penalty.t.pu| 00000030 62 6c 69 63 06 21 00 54 68 65 05 2b 00 74 6f 08 |blic.!.The.+.to.| 00000040 16 00 72 75 6c 65 64 07 4e 00 65 76 69 6c 07 55 |..ruled.N.evil.U| 00000050 00 6d 65 6e 2e 05 5a 00 2d 2d 08 00 00 50 6c 61 |.men..Z.--...Pla| 00000060 74 6f 06 83 00 6d 65 6e 07 62 00 67 6f 6f 64 05 |to...men.b.good.| 00000070 11 00 74 6f 0a 7e 00 61 66 66 61 69 72 73 05 6f |..to.~.affairs.o| 00000080 00 69 73 06 1b 00 70 61 79 |.is...pay| ------------------------------------------------------------------------------ 0 1 2 3 4 5 6 7 8 9 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: 08 00 00 50 6c 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 array 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