Code Friday/Challenge 1: Networking Headers

From A-State Computer Science Wiki
Jump to: navigation, search

Background

Many online protocols (HTTP, MIME, etc.) utilize simple ASCII-text based data encoding, with transport and manifest information kept in a "header section" with the rest of the content kept in a "body section". The header section usually contains one directive (often referred to as a header) per line, and the number of headers may vary. The header section is typically separated from the body section by a completely blank line. Additionally, for compatibility, the "Windows-style" line endings are used; each line must end with the two-character combination "\r\n".

Scenario

You have been asked to write a network-based application for a client, for deployment on an embedded Internet of Things device (the iThumbtack™). As such, the available memory on the device is severely limited. Your program's data section will be allowed to consume at most 128 bytes of memory. Your program should perform the following tasks, using a text file as input to simulate incoming network data:

  • open the file (named "request.dat") for input (the text file is being used as a surrogate for real network data)
  • read the data in the file, looking for headers
  • assemble each header, as a string, in memory
  • output each of the headers found to standard output, one header per line, with a completely blank line separating each header.
  • when the blank line separating the header section from the body section is detected, output "END HEADERS", close the file, and exit.

Details

The file will contain a mock-request that contains one or more headers, each separated by the character sequence "\r\n". The length of each header will vary (there is no guaranteed minimum or maximum length). Headers may contain the '\r' and/or '\n' characters individually (maybe even the unlikely combination "\n\r"), but the combination "\r\n" is guaranteed to occur only at the end of each header.

The end of the header section is marked by a completely blank line; from the point of view of the character stream, this will appear as the sequence "\r\n\r\n" — that is: The last header will have two Windows-style newline sequences following it.

An example of the format of a request is shown (in logical view) below. The line endings are invisible, but understood to be "\r\n":

TITLE=Example of input request.
REFERRER=http://wiki.cs.astate.edu
X-META=Lorem ipsum dolor sit amet, consectetur adipisicing elit
X-FINALHEADER=This is the last header and will be followed by a blank line

This is the body of this message.
Your program will simply ignore it.

When viewed as a single string (or stream) of characters, the above would be:

"TITLE=Example of input request.\r\nREFERRER=http://wiki.cs.astate.edu\r\nX-META=Lorem ipsum dolor sit amet, consectetur adipisicing elit\r\nX-FINALHEADER=This is the last header and will be followed by a blank line\r\n\r\nThis is the body of this message.\r\nYour program will simply ignore it.\r\n"

Approach

A common approach to this problem is to create two equal-sized temporary buffers for reading the headers and copying their values to output. In this case, you could have two 50-character c-string buffers. The first is used for reading directly from the incoming data stream (the file in this case), and the second is used to "assemble" the header for output.

Because the length of each header is completely variable, it is possible that the "read" buffer might contain one or more complete headers, or it might contain one complete header and part of the next, or it might contain only part of one very long header.

Note that for the purposes of this challenge, you may assume that the "protocol limit" on total header length is 50 characters; any header longer than that may be truncated to 50 characters. This does not mean that there will never be headers longer than 50 characters in the input stream! Your program must handle the situation where "oversized" headers exist by storing the first 50 characters for output and ignoring the rest. In the example text shown above, the last two header lines are longer than 50 characters, and so would be truncated in the output.

The output of your program, given the exact input described above, should be:

TITLE=Example of input request.

REFERRER=http://wiki.cs.astate.edu

X-META=Lorem ipsum dolor sit amet, consectetur adi

X-FINALHEADER=This is the last header and will be 

END HEADERS

In addition to the buffer(s) used for reading and assembling the headers, your program may use other supporting varaibles, provided the total size of all your data does not exceed 128 bytes.

Test Data

A test file request.dat that exercises most of the possible boundary conditions has been generated and is available at the following URL:

https://magichat.cs.astate.edu/seafile/d/591a76e1c7/

Note: Be careful when opening the test file in a text editor - your editor will most likely try to "fix" the "line endings" (the stray '\r' and '\n' characters in the data file. Do not allow it to do this or the input file will be broken. You can always download a new copy though. To aid you in visualizing what is in the file, a C++ program that contains code to read the file and print the "raw stream" view of it to the console window is also provided. This program will convert the carriage-return character to \r on screen and the newline to \n so that you can see them.

Limitations

In order to keep the challenge interesting, some strict limitations are placed on your program's use of data:

  • Total required size for all variables used must be less than or equal to 128 bytes.
  • No heap allocation (dynamic memory from new or malloc) is allowed. This rules out the use of the std:string data type.
  • The fully assembled header line (which may be limited to the first 50 characters, as per the protocol) must exist in its full and complete form in memory at some point before being output.

Parting Thoughts

Although we encourage you to take up the full "challenge" complete with the limitations and complications detailed here, you are certainly welcome to solve a simplified or modified version of this problem and present that solution as a {code|friday} talk! Remember, this is all just for fun (and learning, of course)!