CS 242 Spring 2010 : Assignment 2.1

This page last changed on Mar 02, 2010 by m3rabb.

Assignment 2.1 – Binary file manipulation in C

This assignment is due in your SVN repository by 2010-03-03 23:59 CST in a directory named Assignment2.1.
This assignment should be much easier than the 1.x assignments. However, you are advised to start using your chosen C development environment ASAP. We also recommend learning to use your IDE’s debugger.

You will be given a file of data. This file is a formatted set of data and data graphics transformation operations. This data file would be interpreted by a real-time system meant to display the items in the display list.

  • In Assignment 2.1, you will write stubs and descriptions of the function that you want another student to write to aid in processing the binary data file.
  • In Assignment 2.2, you will implement the functions given to you by another student.
  • In Assignment 2.3, you will use the code written by the other student, written to your spec, to complete the assignment.

Tools

You are welcome to use whichever C development environment you prefer.

Mac OS

For the Mac, we recommend that you use either Apple’s Xcode, which is free if you register
with Apple, or Eclipse with CDT (C/C++ Development Tools) (which requires gcc be installed on your machine, and the easiest way to get it is to install XCode). On the eclipse webpage there is a download for a version of eclipse already set up for C/C++ developement, or you can install the CDT through the help menu->install new software->select Galileo update site, then select CDT from the Programming Languages category. Once you launch Eclipse for the first time, it should automatically configure itself to use the proper libraries and compiler for C development (at least it did on my machine)

Windows

For Windows, we recommend you use either Visual Studio 2008 or Dev-C++. VS is free from the web store for engineers (http://webstore.illinois.edu click on the departments tab once you login).
You are welcome to use Eclipse, but unfortunately configuring the Eclipse C development environment can be tricky.

Linux

For Linux, we recommend using Eclipse with CDT, installed using the same method mentioned above for Mac. Before you install the CDT or download the C/C++ version of eclipse, make sure you have all the necessary build tools installed on your machine first, since it will allow eclipse to autoconfigure itself rather than you doing it manually after the fact. To install the necesary files on popular distributions:

  • Ubuntu/Debian: sudo apt-get install build-essential
  • Fedora/Red Hat: sudo yum groupinstall “Development Tools”
  • SuSE: zypper install -t pattern devel_C_C++
On all of the above mentioned platforms, try to stay away from using a text editor like notepad, textedit, or vim with manually built makefiles, since one of the goals of this course is to expose you to new tools that will hopefully make your life easier once you get to know them.

Structure of the data file

The data file will be composed of a header region followed by a data region The header region is contains two header blocks, and the data region contains a number of data blocks. Each data block represents either data coordinates, and transformations to be applied to data coordinates.

You must authenticate the file and successively trace through each data block.

Header Region

The header region contains an authentication block followed by an offset table block.

Authentication block

  1. A byte representing the authentication string length
  2. The byte-string: “CS242 Indirect Data”

Offset table block

  1. A byte representing the number of rows
  2. A byte representing the number of columns
  3. A list of (rows * columns) 2-byte offsets

The offsets contained in the table in the header are used to locate the start of the data blocks within the data region. Each offset represents the number of bytes after the end of the authentication block to the start the offset data block. The data blocks may or may not occur in memory in the order that their offsets occur.

A sequence of data blocks referenced from an offset is completed when you encounter a data return block.

Data Region

Following the header block is the data region containing the data blocks.

It is possible that there will be gaps in the data between the data blocks. It is also possible that the number of data blocks does not match the rows*columns. To successfully complete Assignment 2.x, you will need to be able to trace through the data file. It will not work to simply linearly scanning the data file – this will hurt you

Data blocks

Below are the byte formats of the possible data blocks. Each block begins with a one byte record id which determines its type:

Centroid

Centroid bytes
record id: 0x01 1
scaling factor 1
x 4
y 4
z 4
block size 14

A centroid sets the context for subsequent coordinates; i.e. coordinates are are offset relative to the current centroid stack. When you output coordinates, you should always output their absolute coordinates. If the same set of coordinated are “called” after a different centroid, you will output a different set of absolute coordinates. Whenever you encounter a new centroid it replaced the previous one.

If there were 4 successive calls to a set of coordinates you would output those coordinates 4 separate times.

Coordinates

Coordinate List bytes
record id: 0x0a 1
coords count 1
x 2
y 2
z 2
0 or more coords 6 / per coord
block size 6 * (coord count) + 2

Each list of 3D coordinates represent the raw data. Each coordinate is always relative to the current centroid.

When doing calculations with coordinates, you must cast up and down properly to handle overflow. Centroids are 32-bits and coordinates are 16-bits.

Scaling

Scaling Factor bytes
record id: 0x02 1
scaling factor 1
block size 2

When you encounter a scaling factor, you scale relative coordinates by shifting them left by the indicated number of bits. For example, a scaling factor of 5 will result in all x, y, and z coordinates to be shifted left 5 bits. Beware of shifting a coordinate value and causing an unintended overflow.

Calling & Rotation

Call Local Data bytes
record id: 0x0b 1
offset 2
block size 3

This operation jumps the trace to the data block at the specified offset. When a data return occurs, you must be able to return to the following data block.

  • The offset is a 16-bit offset in bytes from the address of the beginning of this data block to the address of the data block where you should continue your trace through the data.
Call Rotate Local Data bytes
record id: 0x1b 1
offset 2
rotation angle 2
block size 5

As with the previous operation, this operation jumps to the data block at the specified offset. However, it also causes a rotational transformation on the subsequent coordinates. When a data return occurs, it undoes the current rotational transformation, and returns like the previous operation. New rotation calls build upon previous rotation calls, so you must be able to handle the stacked rotational contexts.

  • The offset is a 16-bit offset in bytes from the address of the beginning of this data block to the address of the data block where you should continue your trace through the data.
  • The rotation angle ranges from 0 increasing around the circle clockwise through 65535, with 0 representing 12 o’clock. You will need to convert this value to radians which are measured
    counterclockwise.
Use the following equations to calculate a rotational transformation:

x' = x cos (theta) - y sin (theta)
y' = y cos (theta) + x sin (theta)

Data return

Data Return bytes
record id: 0x0f 1
block size 1

The data return pops your trace back to the position in the data block immediately following the previous call.

If there are no other return addresses on the data return stack, the trace returns to next offset in the offset table block.

Sample file

We have included a sample file, cs242data.bin, for you to use to develop your work. It is in little endian format. We have provided a decoding of the file.

Output

Ultimately, you will need to output a human readable version of the data as if you traced an entire “frame” of a simulation. Some of the interpreted instructions will branch to other locations within the data and return to continue where they had left off.

You will need to output coordinates and indications of state changes. Coordinate values must be output in hexadecimal.

You must authenticate the binary data file and successively trace through each data block in the order in which its offset appears in the table. As you trace through the file you will output the encountered centroids, graphic transformations, and the values of absolute coordinates in a human readable form.

When a call occurs, you must:

  • convert the rotation angle (16-bit, relative to vertical, increasing clockwise) to normal radians
  • branch to the location
  • apply the rotation and scaling factor to relative coordinates
  • add to most-recent 32-bit centroid
  • output coordinates in hexadecimal

Requirements for 2.1

Write specifications for a library of C functions that you will use to complete this assignment. You will give those specifications to another student in the form of comments describing the functionality you want and function “stubs”. A stub is the first line of the function declaration indicating the arguments and their order as well as the return type. In C these stubs are known as function prototypes. Your comments must be Doxygen compliant. Your commented prototype functions should be composed into a single valid .h header file.

Example

/**
* @file Assignment2.1.h  
* @author Maurice Rabb
* @date 2010-03-02
*/ 

/**
* A trick to make a bool type in C.
* @see http://www.codeguru.com/forum/archive/index.php/t-238109.html
*/
typedef enum {false = 0, true = 1} bool;

/**   
* Takes two integers and adds them together   
* @param header a pointer to a header region  
* @param isIndirect a boolean specifying whether the format is indirect data or not 
* @return a boolean confirming whether or not the header is valid 
*/   
bool authenticateHeader(byte* header, bool isIndirect);    

You will receive specifications from another student assigned to you. The person for whom you are writing specifications and the person for whom you are writing code may not be the same person.

Present your specification in discussion section, pass them to the assigned student. Be prepared to review the specifications of the student assigned to you. You will be writing code to this specification the following week. The second week you will present the code of the person that wrote code to your specification.

What functions should you specify?

Remember, one of the core goals of this course is to learn the power of small, focused and well-named functions and methods. You should specify functions that would be both necessary and useful to process the data file, such as:

  • Functions to process each type of block.
  • Functions to transform points, such as: scaling, rotation, relative to absolute positioning, etc.
  • Functions to output the block elements as they occur, such as: that centroid or scaling factor has been encountered, display a coordinate in hexidecimal, etc.

Rubric

  • Documentation
    • Your function stubs are commented adequately: 2
    • Your function comments are Doxygen compliant: 2
  • Coverage
    • Your library functions cover all of the required header and data cases: 4
    • Your library functions are well thought out: 4
    • Your C file is properly constructed: 2
  • Participation
    • You submit your code properly and on time: 2
    • You present the code well and make thoughtful comments: 2
Total 18

cs242data.bin (application/macbinary)
Document generated by Confluence on Feb 22, 2012 18:15

  1. No comments yet.

  1. No trackbacks yet.