| |
|
|
Checksums Simplified |
by Colin Flournoy, IAR Systems |
| |
Have you ever asked yourself the question before, “Are checksums really necessary in my given application?” This article delves into the rudiments of checksums and illustrates the facilities provided to you by IAR Embedded Workbench to enable you to implement a checksum algorithm.
Electrical systems and board layout are prone to Electromagnetic Interference (EMI) because any alternating current in a conductor generates a propagating electromagnetic field. This field can induce currents in nearby electrical components and cause them to produce unexpected and/or incorrect behavior. Depending on how the system has been designed and whether or not signals have been shielded correctly, the introduction of errors due to EMI can vary quite substantially, e.g. network data transmissions can produce errors such as toggled, missing or duplicated bits. Consequently, the data received will not be concordant with the data transmitted.
In their most basic form, checksums are a form of a redundancy check which allow the end user to protect the integrity of the system. Because transmission errors are inevitable, embedded protocols often utilize some form of a checksum to detect such errors. The transmitter typically will calculate the checksum which will then be sent with the data to the receiver. It is the job of the receiver (in this case the target MCU) to verify that the checksum matches with the data and the original checksum. In theory, a checksum can be generated on any medium for which verification of the intended message to the receiver is necessary to ensure that said message was delivered correctly.
The most basic checksum algorithms entail adding up components or patterns in a message and then comparing these totals to the checksum value of the original message to provide a form of authentication. They can take on various forms depending upon the nature of the transmission and the needed reliability of the algorithm. Often there is a three-way tradeoff between the computing power used on the checksum, the size of the checksum itself and the probability of not detecting an error. These basic checksums can fail to detect an error if two bytes are transposed in the code (since addition is a commutative operation), but more complex algorithms such as a Cyclic Redundancy Check (CRC) compensate for this loophole.
Version 5.20 of IAR Embedded Workbench ARM offers a variety of checksums for your given application from the most basic arithmetic checksums to a more thorough CRC checksum. These checksums can be enabled and are directly accessible in the project options under the “Linker” category. The source code is provided for the end user to verify the checksum directly with one’s own application.
The most basic form of a checksum offered with IAR ILINK Linker is the arithmetic checksum. The arithmetic checksum simply adds up all of the asserted bits in the binary image of the application and compares this to what is read back on the receiver end. As previously mentioned, arithmetic checksums suffer from deficiencies which do not account for bit positioning at all, making them less reliable than other techniques such as CRC algorithms. Bit positioning in a string can change leaving the sum of all asserted bits identical and thereby not detecting the error. Although easy to implement, arithmetic checksums fall short in providing the user confidence that the code received by a device is identical to that which was transmitted.
In the simple example below, checking the number of asserted bits in a string can give the same checksum value although the data being sent is completely different. |
1100 0011 1101 0001 0000 1100 1000 0110 = 13 = 0xD
0011 0110 1100 1100 1001 1001 0001 0000 = 13 = 0xD |
There are three obvious downsides with most arithmetic checksum calculations:
- changing the order of data words;
- inserting or deleting words with all bits set to zero;
- flipping an even number of bits with the same position in the word.
When addition does not suffice for reliability, we fortunately do not have to look far for a more reliable alternative. Division (as opposed to summation) is a logical choice for that added reliability since the division operation is not commutative. As an alternative to additive checksums, Cyclic Redundancy Check (CRC) checksums are available which account for not just the total number of asserted bits in an image, but also the bit positioning.
The most computationally expensive checksum that is used commonly is a CRC. Strictly speaking, a CRC is not a sum, but rather an error detection code computed using polynomial division. CRC computation can be a significant CPU load in exchange for which the user gets a much higher reliability of detecting errors in the message. It will not only detect bit assertion in a message, but also takes into account bit ordering, thus making the algorithm much more reliable.
Within any IAR Embedded Workbench project, implementing a checksum algorithm is quite straightforward and there is a minimal amount of work that needs actually done by the end user. To become more acquainted with the implementation of checksums in the IAR Embedded Workbench environment, users are provided an example workspace from the IAR Systems support website which is available for download. Technical note 11927 outlines checksums in IAR Embedded Workbench V5.20 for ARM and provides a link to the example workspace which is demonstrated running IAR C-SPY Simulator.
The first step in implementing a checksum in your given application is to turn on the checksum calculation option which is found in the project options menu. You will first be required to check, “fill unused code memory”. Keep in mind that the range that you select is for the actual checksum calculation as well as the fill region. All unused code will be filled with the pattern of your choice. After checking this box, providing a range to perform the calculation and a fill pattern, you will then be able to generate the checksum as seen below. |
 |
| Click to enlarge image |
|
|
| Upon enabling the checksum in the project options, you will then need to decide where the checksum calculation will be stored in the image. Looking at the example project provided in the technical note, you will notice that the project has three different build configurations for demonstrating this. |
 |
| Click to enlarge image |
|
|
The first configuration places the checksum calculation at the end of ROM, whereas the second and third build configurations place the checksum calculation in the end and the beginning of the application respectively.
As an example, choosing to place the checksum value at the end of ROM will require creating a checksum section and informing the linker to place it at the end of the ROM region. A modification of your linker file (.icf) might require something as follows: |
place at end of ROM_region { readonly section .checksum };
place in ROM_region { readonly }; |
| You will notice that deciding to place the checksum value at the end of ROM will be quite different from choosing to place the checksum in the beginning of the application. In this case the linker file might contain the following modifications (note that the linker file and the choice of the checksum placement will require you to modify your (.icf) file for your specific target): |
define block CHECKSUM { section .checksum };
place in ROM_region { readonly, first block CHECKSUM }; |
 |
| Click to enlarge image |
|
|
Simply by running the simulator project and opening the Terminal I/O window you can verify the checksum calculation. In this case we are looking at the “PlaceEndofROM” build configuration and expect the checksum calculation to be placed at the end of ROM and the value to match from what is generated by the IELFTOOL. A simple printf( ) statement redirected to the Terminal I/O window will return the checksum value and verify this.
The next step in implementing this on your target is to customize one of the example .icf files provided in the example project. As you will notice when you look at the .icf file, they are not designed for a specific device and will need some minor changes to work on your hardware platform. Depending on where you want to place the checksum, this will vary slightly between linker files.
Finally implementation on your hardware requires us to include the source for the CRC16 algorithm in you application. The source is provided in the example project which we downloaded earlier from the support website.
You will notice when you go to include the source code for the CRC16 in you application that there are two basic CRC16 variations. The default setting uses a much faster version of the algorithm, but will require more ROM as it utilizes a constant table method which must reside in non-volatile memory. The alternative performs the actual polynomial division, which is most commonly associated with CRCs, but will require more execution time. On the example project alone you will save approximately 600 bytes in read-only memory when choosing to use the slow CRC method.
There are some small considerations when adding the source for the checksum to your own example project:
- Checksum calculations must not be made over the existing checksum value
- If the slow CRC is used, then a final call needs to be made to the CRC calculation with an input parameter of zero and the number of bytes of the actual checksum value.
As with any other linker options, the checksum calculation can also be invoked directly with the command line tools provided by IAR Embedded Workbench. When running the command line tool, the linker must first be invoked followed by the IELFTOOL which performs the actual checksum. An example of this is included below for your reference.
The options used in the (place first) example are:
Fill unused code memory
Fill pattern 0xFF (can be any pattern)
Start address 0x84 (adjust to your application)
End address 0xFFFF (adjust to your application)
Generate checksum; size = 2 bytes; CRC16; Complement = as is; Bit order = MSB first; initial value = 0.
The corresponding command line option is: |
| ielftool --fill 0xFF;0x84-0xffff --checksum __checksum:2,crc16,0x0;0x84-0xffff |
 |
| Click to enlarge image |
|
|
Using the command line option might be useful if you would like to perform the calculation over several ranges in memory. The GUI only accepts one range, so you would need to turn off all of the options in checksum tab to perform this. The command line would then need to be added in the menu.
Project > Options... > Linker > "Extra options”
Several ranges could now be added to the “Extra options” tab. Some of the checksum symbols defined by the GUI will not be available in the actual source, so you will need to adjust the ranges being used as parameters to the actual CRC calls. |
A Final Word |
As with most engineering endeavors, there will usually be tradeoffs and checksums are no exception to the rule. When choosing what (if any) checksum algorithm to implement, one must consider the needed reliability of the algorithm in your system as well as the available resources to use that algorithm. The example project used in this toolbox can be applied to any target using IAR XLINK Linker or IAR ILINK Linker. Checksum capability is not exclusive to the IAR Embedded Workbench for ARM tool chain. With the wide range of options provided in IAR Embedded Workbench, choosing the correct checksum and implementing this in your system is quite straightforward.
For more information about checksums in general and their implementation, please refer to the following:
|
|
|
This article was published in e-News from IAR Systems.
SUBSCRIBE to free, monthly newsletter. |
|
