Efficient CRC calculation with minimal memory footprint

Almost every form of digital information exchange can introduce communication errors. Sometimes, these errors can be ignored (for example, an erroneous pixel in a high-resolution video is merely unnoticeable). However, most of the time, they cannot be ignored, and we want to ensure that the receiver gets an absolutely correct stream of information.

In order to overcome the inherent inaccuracy of information transmission, a few methods for error detection and correction have been developed. Generally speaking, these methods introduce some redundancy to the actual message, which in turn can be used to detect errors and in some cases to recover the original data.

One of the most common methods is the use of the CRC (cyclic redundancy check) function, a family of codes commonly used to ensure data integrity in digital data streams by detecting errors due to noise or dropouts of bits in the message stream. The CRC calculates a series of bits (also commonly referred to as a CRC) that is appended to the data stream and transmitted along with the message. The receiver performs a CRC function on the message and compares the result with the received CRC code to verify the integrity of the message. CRC is commonly used in a number of applications such as digital communications and computer data storage systems.

The CRC is performed through binary polynomial division between the transmitted message and a polynomial divisor and is usually implemented using a linear feedback shift register (LFSR). An LFSR is a shift register where its next state is a linear combination of its previous state and input bits. In our context, the linear operators are Logical XOR and Logical AND. Since the operation of an LFSR circuit is deterministic, and the CRC is shorter than the message, typically few messages are mapped to each CRC value. A well-chosen polynomial ensures an evenly distributed mapping of messages to CRC values (for example, if all messages were mapped to the same CRC, detection of an error in a message bit would be impossible).

The trick in an embedded systems design is to implement this technique in the most efficient way possible and in the smallest possible footprint. In this article, we discuss aspects of the theory and implementation of LFSRs and CRCs, illustrated using a family of instructions on Analog Devices’ Blackfin processor specifically defined for addressing the task of efficient LFSR implementation. We also provide a method for converting an implementation from an Internal LFSR form to an External LFSR form.

Links: http://embedded.com/design/206901030

The ‘C’ test. Part – XVI

Obscure syntax

16. ‘C’ allows some appalling constructs. Is this construct legal, and if so what does this code do?

int a = 5, b = 7, c;
c = a+++b;

This question is intended to be a lighthearted end to the quiz, as, believe it or not, this is perfectly legal syntax. The question is how does the compiler treat it? Those poor compiler writers actually debated this issue, and came up with the “maximum munch” rule, which stipulates that the compiler should bite off as big (and legal) a chunk as it can. Hence, this code is treated as:

c = a++ + b;

Thus, after this code is executed, a = 6, b = 7, and c = 12.

If you knew the answer, or guessed correctly, well done. If you didn’t know the answer then I wouldn’t consider this to be a problem. I find the greatest benefit of this question is that it is good for stimulating questions on coding styles, the value of code reviews, and the benefits of using lint.

Well folks, there you have it. That was my version of the C test. I hope you had as much fun taking it as I had writing it. If you think the test is a good test, then by all means use it in your recruitment. Who knows, I may get lucky in a year or two and end up being on the receiving end of my own work.

 Links:

for “The ‘C’ test. Part – I”  to  “The ‘C’ test. Part – XVI”

http://www.embedded.com/2000/0005/0005feat2.htm

http://www.embedded.com/98/9811/9811fe3.htm 

The ‘C’ test. Part – XV

Typedef
15. Typedef is frequently used in C to declare synonyms for pre-existing data types. It is also possible to use the preprocessor to do something similar. For instance, consider the following code fragment:

#define dPS struct s *
typedef struct s * tPS;

The intent in both cases is to define dPS and tPS to be pointers to structure s. Which method, if any, is preferred and why?

This is a very subtle question, and anyone who gets it right (for the right reason) is to be congratulated or condemned (“get a life” springs to mind). The answer is the typedef is preferred. Consider the declarations:

dPS p1,p2;
tPS p3,p4;

The first expands to:

struct s * p1, p2;

which defines p1 to be a pointer to the structure and p2 to be an actual structure, which is probably not what you wanted. The second example correctly defines p3 and p4 to be pointers

The ‘C’ test. Part – XIV

Dynamic memory allocation

14. Although not as common as in non-embedded computers, embedded systems do still dynamically allocate memory from the heap. What are the problems with dynamic memory allocation in embedded systems?

Here, I expect the user to mention memory fragmentation, problems with garbage collection, variable execution time, and so on. This topic has been covered extensively in ESP , mainly by P.J. Plauger. His explanations are far more insightful than anything I could offer here, so go and read those back issues! Having lulled the candidate into a sense of false security, I then offer up this tidbit:

What does the following code fragment output and why?

char *ptr;
if ((ptr = (char *)malloc(0)) ==NULL)

puts(“Got a null pointer”);
else
puts(“Got a valid pointer”);

This is a fun question. I stumbled across this only recently when a colleague of mine inadvertently passed a value of 0 to malloc and got back a valid pointer! That is, the above code will output “Got a valid pointer.” I use this to start a discussion on whether the interviewee thinks this is the correct thing for the library routine to do. Getting the right answer here is not nearly as important as the way you approach the problem and the rationale for your decision.

…to be continued 

The ‘C’ test. Part – XIII

13. Comment on the following code fragment.

unsigned int zero = 0;
unsigned int compzero = 0xFFFF;
/*1’s complement of zero */

On machines where an int is not 16 bits, this will be incorrect. It should be coded:

unsigned int compzero = ~0;

This question really gets to whether the candidate understands the importance of word length on a computer. In my experience, good embedded programmers are critically aware of the underlying hardware and its limitations, whereas computer programmers tend to dismiss the hardware as a necessary annoyance.

By this stage, candidates are either completely demoralized-or they’re on a roll and having a good time. If it’s obvious that the candidate isn’t very good, then the test is terminated at this point. However, if the candidate is doing well, then I throw in these supplemental questions. These questions are hard, and I expect that only the very best candidates will do well on them. In posing these questions, I’m looking more at the way the candidate tackles the problems, rather than the answers.

…to be continued