Optimization

Optimization

Although the word “optimization” shares the same root as “optimal,” it is rare for the process of optimization to produce a truly optimal system. The optimized system will typically only be optimal in one application or for one audience. One might reduce the amount of time that a program takes to perform some task at the price of making it consume more memory. In an application where memory space is at a premium, one might deliberately choose a slower algorithm in order to use less memory. Often there is no “one size fits all” design which works well in all cases, so engineers make trade-offs to optimize the attributes of greatest interest. Additionally, the effort required to make a piece of software completely optimal—incapable of any further improvement— is almost always more than is reasonable for the benefits that would be accrued; so the process of optimization may be halted before a completely optimal solution has been reached. Fortunately, it is often the case that the greatest improvements come early in the process.

 

Links:

http://en.wikipedia.org/wiki/Program_optimization

http://www.tantalon.com/pete/cppopt/main.htm

http://en.wikipedia.org/wiki/Compiler_optimization

Stack

Stack - PUSH/POP

LIFO stack

Stacks are a type of container adaptors, specifically designed to operate in a LIFO context (last-in first-out), where elements are inserted and extracted only from the end of the container.

stacks are implemented as containers adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements. Elements are pushed/popped from the “back” of the specific container, which is known as the top of the stack.

The underlying container may be any of the standard container class templates or some other specifically designed container class. The only requirement is that it supports the following operations:

• back()
• push_back()
• pop_back()

Link:

http://www.cplusplus.com/reference/stl/stack/

http://en.wikipedia.org/wiki/Stack_(data_structure)

Asserts

 

Assert Safely

 

Expert programmers use the assert() macro to seed their code with debugging statements. So should we all.

The macro must have no effect on the system – it shouldn’t change memory, interrupt state, or I/O, and it should make no function calls. The user must feel free to sprinkle these at will throughout the program. Disabling the asserts in released code must never change the way the program operates.

The macro generally looks something like:

#define
assert(s)
if (s)
{}else (printf("Error at %s %d: ", __FILE__, __LINE__)

It’s sort of an odd way to write code – if the condition is true (in which case assert() takes no action) there’s a null pair of braces. Why not test the negation of the statement “s”?

Links: http://www.ganssle.com/articles/adifasts.htm

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