Libraries
The Contiki system provides a number of libraries that are used both by application programs and by the system code modules itself. The libraries contain modules for manipulating linked lists, for managing ring buffers, for generating random numbers, for calculating Cyclic Redundancy Checksums (CRCs), and for computing an Integer Fast Fourier Transform (IFFT).
The linked list library is used throughout the Contiki code modules in places where a module keeps information on a list. For example, the list library is used for managing packet queues in network protocols, for maintaining lists of neighbors in routing protocols, for keeping track of timers in the timer modules, and for the list of commands in the Contiki shell.
The ring buffer library is used for transporting individual bytes of data between two section of code. It is most often used in device drivers where an interrupt handler inserts bytes into the buffer, from which they are read by an underlying bottom-half handler.
The random number library is used in various places in Contiki where randomness is desired. The most common use is in network protocols, where randomness is needed to avoid negative synchronization effects between communicating nodes.
The CRC library is used to calculate checksums for communication protocols that run over unreliable channels. It is used by radio device drivers that operate hardware devices that do not have their own checksums. The library can also be used by application programs that want to provide a certain guarantee that its data has not been inadvertently changed during transmission.
The IFFT library is used by application programs that do signal processing of sensed data, such as acoustic signals. The IFFT library transforms the data into its equivalent in the frequency domain, which for many types of signals make the data easier to process.
The Contiki list library provides a list on which items can be placed and later retrieved. The library is used throughout Contiki for storing process lists, packet queues, neighbor lists, and various tables. List items are structures that are defined by the module that uses the list library. The only requirement is that the first item is a pointer, which the list library uses to link the items together on the list.
A Contiki list consists of a list handle and a set of list items. Each item is a structure where the first element is a pointer. This pointer is used by the list library to link the list together.
A Contiki list consists of a list handle and zero or more list items, as shown in the figure to the right. The items are linked together forming a singly linked list. The list handle is a pointer that points to the first item on the list.
Items on a list are a structure where the first element is a pointer. This pointer typically is called next and is used by the list library to form the list. The last item on the list has its next pointer set to NULL. An empty list has the list handle set to NULL.
Memory for list handle and the list items are allocated by the module that uses the list. The list library itself does not allocate memory, nor store any state of the lists it manages. Lists are declared through the LIST() macro as list_t types. LIST() creates two objects: one for the list item itself, and one for the pointer to the first item in the list. By separating these two, list_t objects can be copied and references in a less error-prone way. Observe that LIST_INIT() creates a list qualified as a static object. If there is a need to use lists as global objects or in data structures, the macro LIST_STRUCT() declares a list inside a C struct. In case a globally viewable list is desired, a structure of global scope, which contains a list, can be declared. %XXX add this to the API table. Define the arguments.
Items can be put on the list either at the front of the list, at the end of the list, or between two items on the list. After an item has been stored on the list, it retains its position with respect to other items on the list. List items can be removed either by removing the first element, the last element, or a given element.
The full API for the Contiki list library is shown the table below. The Contiki list library provides a function for accessing the first element on the list, called the head element, and the last element of the list, called the tail element. There are two ways to traverse a list: either by using the next pointer, or by using the list_item_next() function. The latter is recommended in case portability is needed with future versions of Contiki, albeit its larger code size than the direct pointer access.
The list library provides a function for obtaining the length of the list, called list_length(). The list does not store the length of the list. Instead, the list_length() function computes the length of the list by walking through the list, counting each element.
The Contiki list API:
void list_init(list_t list); // Initialize a list.
void *list_head(list_t list); // Get a pointer to the first item of a list.
void *list_tail(list_t list); // Get the tail of a list.
void *list_item_next(void *item); // Get the next item of a list.
int list_length(list_t list); // Get the length of a list.
void list_push(list_t list, void *item); // Add an item to the start of the list.
void list_add(list_t list, void *item); // Add an item at the end of a list.
void list_insert(list_t list, void *previtem, void *newitem); // Insert an item after a specified item on the list.
void *list_pop(list_t list); // Remove the first object on a list.
void *list_chop(list_t list); // Remove the last object on the list.
void list_remove(list_t list, void *item); // Remove a specific element from a list.Insertion to a list is done with any of three functions, list_push(), list_add(), and list_insert(). The three functions insert items differently. The list_push() function places the items at the start of the list, list_add() at the end of the list, and list_insert() between two other items on the list.
The implementation of the list_push() function is simple. It simply sets the next pointer of the element to be inserted to point to whatever the list handle points to. It then points the list handle to the new item. If the list was empty, as signified by the list handle being set to NULL, the new item will have its next pointer pointing to NULL.
The implementation of list_add() is slightly more complicated than that of list_push() because the function works differently depending on whether the list is empty or not. For an empty list, the list handle is simply pointed to the new item. For a non-empty list, the last element of the list is obtained, and its next pointer is repointed to the new item.
The list_insert() function implementation is simple: it repoints the next pointers of both item in between which the new item is to be inserted. If the list is empty, the list handle is set to point to the new item.
The insertion functions do not check if the item to be inserted is already on the list. Instead, it is up to the calling module to ensure that an item is not inserted twice. The reason for this design decision is performance: modules that are sure that they will never add an item twice should not be penalized in terms of performance.
Items are removed from a list with the list_pop(), list_chop(), or list_remove() functions. The three functions removes the first item, the last item, and a given item, respectively.
Because memory for the items is not allocated by the list module, but by the module that uses the list module, the memory for a removed item is not deallocated as the item is removed. It is up to the calling module to ensure that items are deallocated, if needed, after they are removed from the list. The removal functions therefor all return a pointer to the item that they removed, except for the list_remove() function where the caller already knows what item is to be removed.
There are several places in Contiki where an interrupt handler needs to feed bytes that can be independently read by another part of Contiki. Because the interrupt handler may preempt any part of the code that reads the data, the interrupt handler and the reader functions must be synchronized to avoid race conditions. A ring buffer is such a synchronization mechanism that lets the reader and writer operate independently of each other, without the risk of race conditions.
A ring buffer with four items, a, b, c, and d. The a item is the next to be removed from the buffer. The d item is the most recently inserted. The first and last pointers point to the two items, respectively.
A ring buffer, sometimes also called a circular buffer, is a data structure that conceptually holds data in a ring as shown the figure to the right. Data is stored in a buffer from where it is read in the same order as it is inserted. The data structure is sometimes also called a First-In-First-Out (FIFO) buffer.
The Contiki ring buffer library implements a ring buffer handling mechanism that stores bytes in an array that must have a size that is a powers of two, and 256 bytes or less. The ring buffer will be able to store a maximum of size_power_of_two - 1 bytes. The reason for requiring that the size is a power of two is that wrapping of the first and last pointer in the ring structure can be implemented using bit-wise Boolean operators. Likewise, the reason for the maximum size of 256 bytes is that the pointers can be held in an 8-bit byte. The 8-bit byte is the only data structure that can be atomically updated, which is important to ensure synchronization between writers and readers to the ring buffer, even if the reader and writer may preempt each other.
The Contiki ring buffer API:
void ringbuf_init(struct ringbuf *r, uint8_t *a, uint8_t size_power_of_two); // Initialize a ring buffer.
int ringbuf_put(struct ringbuf *r, uint8_t c); // Insert a byte into a ring buffer.
int ringbuf_get(struct ringbuf *r); // Get a byte from the ring buffer.
int ringbuf_size(struct ringbuf *r); // Get the size of a ring buffer.
int ringbuf_elements(struct ringbuf *r); // Get the number of elements currently in the ring buffer.The Contiki ring buffer API is shown above. All API functions operate on a ringbuf data structure. The ringbuf data structure is initialized by calling the ringbuf_init(). The module or application that uses the ring buffer must provide memory for the buffer, which is passed as an argument to ringbuf_init(). The ring buffer module only provides the logic for managing a ring buffer; the using module must provide the memory. The API provides one function for inserting elements into the ring, ringbuf_put(), and one function for retrieving and removing elements from the ring, ringbuf_get(). Both functions insert and retrieve bytes. The rinbuf_get() function returns an error if there are no bytes available in the buffer, which is signified by returning -1. The ringbuf_size() function returns the number of available bytes in the buffer, and ringbuf_elements() returns the number of elements that are currently held on the ring.
The Contiki random number library is used by Contiki programs and by the Contiki system itself to obtain random numbers. The library is typically implemented using the random number generator provided by the underlying C library or compiler runtime system. The Contiki code does, however, include a pseudo-random number generator that is used on platforms where no random number generator is available.
The Contiki random number library API:
void random_init(unsigned short seed); // Initialize the random number generator.
unsigned short random_rand(void); // Get a random number between 0 and RANDOM_RAND_MAX.The API for the Contiki random number library is given above. The API provides only two functions: random_init(), which is called by the system during the boot-up procedure, and random_rand(), which produces a random number between 0 and RANDOM_RAND_MAX. RANDOM_RAND_MAX is defined to be 65535, the largest number that can be represented in an unsigned short variable, but this value should not be relied on as it may change in future versions. Instead, programs should use the variable RANDOM_RAND_MAX to scale its random numbers according to the range needed.
Cyclic Redundancy Check (CRC) is a type of checksum that is particularly well-suited to use in low-level communications mechanisms because the CRC catches many bit errors. There are several types of CRCs, each with its own properties in terms of how well it catches different types of bit errors. Although CRCs are especially efficient when implemented in hardware, there are way to efficiently implement CRCs in software.
The Contiki CRC library computes a CRC16 checksum, a particular type of CRC that has been standardized by the International Telecommunications Union (ITU).
The API for the Contiki CRC16 library is shown below. The Contiki CRC16 library uses an accumulator-based approach to computing the CRC16. Every byte of the data over which the CRC16 is computed is processed individually and added to an accumulator variable. This makes it easy to compute CRC16 over data that is available on a byte-by-byte basis, such as data coming from a serial device or a radio transceiver.
The Contiki CRC16 implementation is designed to be compact in terms of code size and memory footprint. Although there are many ways of implementing a CRC16 that have a higher execution-time efficiency than the Contiki CRC16 library, such as table-based approaches, the Contiki CRC16 provides a very small footprint.
The Contiki CRC16 API:
unsigned short crc16_add(unsigned char b, unsigned short crc); // Add one byte to accumulated CRC16.
unsigned short crc16_data(const unsigned char *data, int datalen, unsigned short acc); // Calculate the CRC16 over an array.The integer fast fourier transform library is an integer version of the fast fourier transform. The fourier transform converts sample series in the time domain into a frequency spectrum. The transform can be useful when trying to detect deviations between sample series from accelerometers, microphones, or similar types of sensors. By transforming the sample series into frequency spectrum it is easier to compare the data than a direct comparison between the sample series.
The IFFT library expects the sample arrays to be 8-bit values and the number of samples to be a power of two. The samples are placed in int_16t to avoid overflow during the calculations. The result after the transform is present in the xre array and approximates the magnitude of the frequencies present in the sample series. The frequencies available are from the lowest at xre[0] to the highest frequency at xre[n/2] which corresponds to half the sampling frequency. The IFFT library calculates an approximate magnitude and is mainly intended for comparison between different series of sample data and to find which frequencies have highest or lowest magnitudes.
The Contiki ifft API:
void ifft(int16_t xre[], int16_t xim[], uint16_t n); // calculate fft on samples in xre xim arrays.Contiki contains a set of libraries that are used both by core Contiki modules and by application programs. The libraries are intended to make software development easier by allowing reuse of common functionality.