« Posts under Code

Alternative Representations in C and C++

When you go back to C/C++ after a week of coding in Python, funny things can happen. I already described such a case in this post.

Recently, I had another surprising incident. I was scanning my code changes in order to find a bug that had pestered me for quite a while. I rubbed my eyes in disbelief when I came across this ‘if’ statement:

How could this even compile? Instead of ‘&&’ I inadvertently typed ‘and’, the Python logical ‘and’ operator. At first, I thought that this must either be a g++ extension or some clever guy* had defined

somewhere in a header file that I pulled. Being biased towards the second theory, I did an experiment and undefined ‘and’ just before my ‘if’ statement:

but it didn’t compile. Luckily, the compiler message that I got from g++ unraveled the mystery:

Whoa! ‘and’ is an operator (a token) in C++ that hitherto I’d never heard of. In fact, there’s a whole bunch of what the C++ standard calles “alternative tokens” (or sometimes “alternative representations”):

Alternative Token Equivalent To
and &&
and_eq &=
bitand &
bitor |
compl ~
not !
not_eq !=
or ||
or_eq |=
xor ^
xor_eq ^=

It didn’t take long and the feeling of surprise was replaced with a feeling of disappointment. Some of the bit-wise operators have a ‘bit’ prefix while others don’t. ‘and’ and ‘bitand’, for instance, but ‘and_eq’ should actually be ‘bitand_eq’, because ‘&=’ is a bitwise operator — sigh! The same goes for ‘or’, ‘bitor’ and ‘or_eq’. By the same token (pun intended!), ‘xor’ and ‘xor_eq’ should really be ‘bitxor’ and ‘bitxor_eq’, if you’d ask me.

Not so confusing, actually quite beneficial, are the operators ‘and’, ‘or’, and ‘not’ by themselves. Consider:

While using these newly discovered keywords is certainly not a huge thing, I do believe that alternative operators are more readable than their cryptic, traditional counterparts. Habitually used, they even avoid classic blunders like forgetting to put a second ‘&’ or ‘|’ in logic expressions. I think I’ll give them a try — but this time as a deliberate act, instead of a Freudian slip like last time.

Note, however, that in C, these alternative representations don’t exist as keywords. Instead, they are defined in iso646.h as macros — just like the “clever guy” would have done it :-)

________________________________

*) Once, such a “clever guy” made fun of our team’s coding standard by defining this macro (the letter O) in a global header file:
#define O (1 – 1)
and using ‘O’ in his code whenever he needed a literal ‘0’ (zero):
for (int i = O; i < max; ++i) {

}
When I asked him why on earth he did such an insane thing, he replied, “Well, our coding standard says that we MUST not use octal literals, but 0 is an octal literal since it starts with a ‘0’. Smartass!

The Happy Path to Modern C++

“Show the readers everything, tell them nothing.”
― Ernest Hemingway

Considering all the C++ job offers that I’ve received over the last couple of months, it looks like modern C++ (any C++ release beyond C++03) is picking up momentum, especially in embedded systems. Why embedded systems? I think it’s because C++ has always put a lot of emphasis on efficiency and thus the features offered by C++11 and C++14 not only simplify a programmer’s life but also stand a good chance of yielding more performant code. Now that C++11 and C++14 are supported by almost all contemporary compilers, there’s no reason to hold back anymore.

Alas, reading standard documents or even books on the subject is no fun. While the idea behind new features is usually easy to grasp, there are often intricacies that dim a feature’s shine. Clearly, studying books and learning about subtleties is necessary at some point, but isn’t there an accelerated way to get started (or motivated)?

Now there is, at least that’s my goal with this new project that I’ve created: The Happy Path to Modern C++. The idea is to tackle modern C++ by example not by text; that is, by code snippets that demonstrate the beauty of language features, not their nitty-gritty details.

Every code snippet can be compiled and run in a debugger to explore its behavior. Thus familiarizing (and experimenting) with modern C++ language features should be painless (maybe even fun?).

Let me show you what I mean. The following snippet (which is part of cpp11/01_core_features/core_features.cpp) introduces range-based for-loops:

Just go to cpp11/01_core_features and execute

to compile the code and

to run it.

With this set-up, it’s easy to toy around: just uncomment the line in ‘test_range_based_for_loops’ that constitutes a syntax error (the line that attempts to modify the read-only variable), rerun make and see what happens. Contrast this hands-on approach with the (fine) documentation on cppreference.com, which is exact and comprehensive (and ten times more readable than the official language standardese), but nevertheless intimidating for beginners.

Be aware that you are looking at work in progress. My aim of this first release was to cover most of C++11 and C++14 core language features as well features pertaining to classes. Obviously, a lot is still missing, like

– Const expressions
– Variadic templates
– Lambdas
– Concurrency
– Move semantics
– Regexps

Contributions to this project are more than welcome, just send me your pull requests. Please keep in mind that the overall goal is to have crisp code examples that capture the essence of features, not the ugly corner cases. When in doubt, leave it out, keep it simple, keep it beautiful.

Pointers in C: Part VI, Faking ‘restrict’

Pointers in C

“”But then acting is all about faking. We’re all very good at faking things that we have no competence with.”
— John Cleese

As so often in life, people love to do the exact opposite of what you advise. In my previous post I claimed that the ‘restrict’ feature isn’t that all-important and guess what? I received questions on whether it was possible to achieve the (promised) effects of ‘restrict’ even if a particular C dialect doesn’t support it (in case you are using C++ or some C version predating C99, for example).

YES WE CAN!

We just need to creatively combine the wisdom from the previous “Pointers in C” installments. In particular:

  1. Pointer access involving multiple pointers can be optimized if the pointers point to incompatible types.
  2. structs with different tag names constitute different, incompatible types, regardless of whether the struct members are identical or not.
  3. A pointer can be converted to a pointer to a different type as long as the resulting pointer is suitably aligned for the target type.
  4. A pointer to struct points to its initial member.

Do you ‘C’ it?

SPOILER ALERT!

Again, I use the ‘silly’ example to demonstrate the technique. The idea is to wrap the original types (‘int’) in structs with different tag names thus yielding different (incompatible) types:

Believe it or not — it works:

Why? To the compiler, the pointer types are different (item 2) and hence it doesn’t assume that they point to the same memory (item 1). Because of item 3 and 4 in the list above, the calling code can still pass plain ‘int’ arrays/pointers, just like in the original code. However, nasty casts are required when calling ‘silly4’ from C++ code:

Contrary to C++, C is only weakly typed so such casts are not necessary officially, unless you want to get rid of compiler warnings, which you always want to, don’t you?

You could argue that these strange ‘struct int’ pointers that are used in the signature of ‘silly4’ kind of document the fact that the passed pointers are “restricted” and mustn’t overlap. However, I prefer to keep the original ‘int*’ interface and hide this struct business from callers altogether:

The generated code is identical to the one derived from ‘silly4’.

I still stick with my original recommendation that the ‘restrict’ feature is not that useful as it’s a legally binding contract for the caller while the compiler is free to ignore this plea for performance. If you want to use ‘restrict’ regardless of my advice, even if your compiler doesn’t support it, you now know how to emulate it in a portable fashion.

Pointers in C, Part V: The ‘restrict’ Qualifier

Pointers in C

“Le vrai est trop simple, il faut y arriver toujours par le compliqué.”
(“The truth is too simple: one must always get there by a complicated route.”)
― George Sand, Letter to Armand Barbès, 12 May 1867”

Exactly one year ago, I started this series on pointers, but what I really wanted to blog about originally was a rather arcane and rarely used keyword that first appeared in the C99 language standard: the ‘restrict’ qualifier. But after trying to digest the formal definition in chapter 6.7.3.1 I decided that taking a little detour would make my and my reader’s life much easier.

Let me set the stage for ‘restrict’ by summarizing what I wrote in episode 3 about the “strict aliasing rule”:

1. The compiler might optimize code involving multiple pointers, provided the pointers are not aliased; that is, they don’t point to the same object or memory.

2. The compiler assumes that pointers to incompatible types never alias.

3. The compiler assumes that pointers to compatible types (same types, apart from CV-qualification and signedness) potentially alias.

Therefore, a function with this signature is eligible for compiler optimization:

whereas this one is not:

This is unfortunate, because most likely, the arrays passed to the second version of ‘transform’ are in completely different, non-overlapping memory regions. But the compiler doesn’t know and hence stubbornly adheres to the strict aliasing rule.

The ‘restrict’ qualifier, which — contrary to the ‘const’ and ‘volatile’ qualifiers — can only be applied to pointers, is a promise given by the programmer to the compiler that pointers don’t alias even though they point to objects of the same type. Therefore, this version of ‘transform’ can be optimized by the compiler:

Let’s put this to the test with the ‘silly’ example from episode 3:

Before knowing about the strict aliasing rule, we were surprised to see that the memory access to ‘x’ in the return statement was not replaced with a simple ‘return 0’. After having learned about the strict alias rule, it’s clear: since ‘x and ‘y’ point to the same type, the compiler must assume that they may point to the same memory location and hence it loads the value pointed to by ‘x’ from memory afresh:

Now, if we tell the compiler that ‘x’ and ‘y’ never point to the same memory location, optimization is possible:

Nice, isn’t it?

If you use the ‘restrict’ qualifier on a pointer, you promise that — at least for the lifetime of the restricted pointer — the object pointed to is only accessed through this pointer. Break that promise and you get undefined behavior. (In the ‘silly3’ example, the lifetime of the pointers ‘x’ and ‘y’ end once the call to ‘silly3’ returns.)

In the C99 language standard, many functions from the standard library have been revised and now make use of the ‘restrict’ keyword. Take ‘memcpy’, for instance:

As everybody knows, ‘memcpy’ can only copy non-overlapping blocks of memory and this fact is nicely highlighted by the use of the ‘restrict’ keyword: during the call to ‘memcpy’ the memory regions src[0] to src[n] as well as dst[0] to dst[n] are exclusively owned and may not be accessed by other pointers. Since ‘memmove’ can copy overlapping blocks of memory (with a little speed penalty, of course), ‘memmove’ consequently doesn’t declare restricted pointers:

Please be aware that ‘restrict’ is not supported by the C++ language standard and it’s unclear whether it ever will be. If you mix C99 and C++ code, you might have to strip the ‘restrict’ keyword from C99 headers to avoid compilation errors:

In general, I’m not a big fan of optimization features that the compiler is free to ignore. If utmost performance is important, you want dependable performance. Most likely, your routine is not on the performance critical path, anyway. If you think it is, carefully profile your code and after you proved that it is, you’d better code that part in assembly language. Without such evidence, sprinkling your code with ‘restrict’ is little short of premature optimization. (I complained here about the unnecessarily overused ‘inline’ keyword for the same reason.)

What I do like about the ‘restrict’ keyword, though, is that by unraveling it, we’ve made a beautiful journey through important everyday programming topics like “pointers vs. arrays”, “type qualifiers”, “pointer conversion rules”, and the “strict aliasing rule”. The journey was the destination.

BBC micro:bit —The End of All Excuses for Not Learning Programming

“He that is good for making excuses is seldom good for anything else”
— Benjamin Franklin

The BBC micro:bit, or Micro Bit, is a small embedded computer designed by the BBC for use in computer education in the UK. Every British schoolchild of grade 6 – 8 gets a Micro Bit for free. But before you become too envious: You can buy one for about 18 EUR—just do an Internet search to find a local dealer.

In my view, the Micro Bit is an excellent platform for learning programming since it sports many attractive features, such as:

– 5 x 5 LED matrix display
– Temperature sensor
– Ambient light sensor
– Accelerometer
– Magnetometer/compass
– Bluetooth connectivity
– Input buttons
– Various GPIO ports to attach sensors/actuators
– Audio output jack

But the coolest thing about it is that it comes without friction. The development environment is available online, which means that you can do all your programming in your favorite web browser—no need to install any software or drivers. The Micro Bit presents itself as a USB mass storage device onto which you just drag & drop your executable files.

COMMON EXCUSES

Let me show you more of the Micro Bit’s features by dispelling some common excuses for not starting to write code for it today:

Excuse: I don’t possess a Micro Bit!
Response: You don’t need one. There’s a powerful simulator directly on the Block Editor coding environment. I highly recommend starting out with the Block Editor, anyway. Try it out now, before reading on! (Let’s put it this way: If I recommend something provided by Microsoft, it must really mean something, right?)

Excuse: I have no idea what to code.
Response: There are dozens of step-by-step tutorials and pre-built examples on the Block Editor page. Just click on “Projects” and then again “Projects” or “Examples.”

Excuse: Graphical programming sucks and is only for wimps.
Response: While I’m a big fan of text-based programming languages, I think it’s a good idea to toy around with the Block Editor for a while, just to familiarize yourself with Micro Bit’s features. Once you’ve learned what it’s capable of, you can do the rest of your programming in JavaScript or Python.

Excuse: I am (or want to become) a hardcore embedded coder and I’m not interested in high-level, wimpy JavaScript and Python programming.
Response: The Micro Bit is based on ARM’s Mbed IoT platform. There’s an online IDE on Mbed’s website that allows you to program your Micro Bit in C/C++, if you want.

Excuse: I live in a cabin in the woods and have poor Internet connectivity. Online programming is not an option.
Response: Once you’ve visited the Block Editor, you can access it from your browser even if there’s no Internet connection. But since you’re living in a cabin in the woods, you are probably a hardcore C/C++ coder, aren’t you? Well, thanks to the Yotta build system from Mbed, you can do command-line based builds and write your code in Emacs or vi, just as you please.

Excuse: I don’t have time.
Response: This is a lame excuse and I truly detest it. We’re all busy yet have plenty of time for things that are important to us. When we say, “I don’t have time,” we are really saying, “I’m a lazy bum and such a coward that I don’t dare confessing it to you.” Don’t get me wrong: It’s completely OK if you don’t like programming and have other priorities in life, but if you read my blog and you’ve made it this far, you should at least give it a quick try so that you can make an informed decision.

PLAYFUL TESTING

The Micro Bit does look like the perfect learning platform, doesn’t it?

In fact, there’s only one thing I wasn’t so happy about, at least initially: As far as I know, you can only use the simulator if you code in the Block Editor or JavaScript. My preferred Micro Bit language, however, is Python.

I scratched my head a bit and came to the conclusion that this was not really a problem, after all. Why? A simulator basically means manual testing, and manual testing isn’t really something we should ever aim for—it’s no fun at all. Instead, I want to use automated unit tests to ensure that my code behaves correctly even after the most minute change.

But there’s a catch: If you want to run Python unit tests on a host PC (not on the real Micro Bit device) you have a problem. Naturally, the ‘microbit‘ package, which provides access to the Micro Bit’s runtime and it’s peripherals, isn’t part of the standard Python distribution.

As a remedy, I set out to create a little Micro Bit playground, one that comes with a ‘microbit’ package containing mock objects for all the API objects that the original ‘microbit’ package offers. Here’s the essence of the ‘happy_sad’ example contained in the playground GitHub repository:

And here are the corresponding test cases using the mocked microbit.py module:

Just run ‘make’ to execute the test cases and ‘make install’ to transfer the code to your plugged-in Micro Bit. It can’t get any more convenient. No more excuses left!

Pointers in C, Part IV: Pointer Conversion Rules

Pointers in C

“Failure is the key to success; each mistake teaches us something.
— Morihei Ueshiba

Sometimes, someone walks up to you and claims that there is a bug in your well-crafted code. Then, after having successfully proved that individual wrong, it occurs to you that there is indeed a bug—albeit a different one! Those are quite humbling experiences, but experiences that we should be most grateful for.

SETTING THE STAGE

This episode was triggered by feedback that I received from a reader regarding a “Dangerously Confusing Interfaces” post. In said post, I advise that instead of accepting a pointer to “uncopied” memory like this:

‘WriteAsync’ should rather take a pointer to an opaque data structure named ‘uncopied_memory’:

“uncopied” memory means that for the sake of efficiency, the called function doesn’t copy the provided data but instead expects you to keep it alive and unchanged while the called function is executed asynchronously. Since the suggested interface change requires an explicit cast to an ‘uncopied_memory’ pointer, it’s a lot less likely that a temporary buffer allocated from the stack is passed accidentally. The idea of the proposed approach is that every call to ‘WriteAsync’ requires an explicit cast that acts as a reminder to the programmer that the buffer’s contents must be preserved.

For instance, if you wanted to pass a structure that I used in the previous installment of this series to ‘WriteAsync’, you would do it like this:

But back to the question. What the reader was worried about is that since ‘measurements_t’ and ‘uncopied_memory’ are by no means compatible, wouldn’t a cast to an ‘uncopied_memory’ pointer constitute a violation of the “strict aliasing rule“?

Actually, when it comes to the “strict aliasing rule,” the fact that these structs have incompatible members doesn’t really matter—even if you accessed the stored value through a pointer to a struct with an identical set of members you would be in trouble; if the tag names of the structs are different, it already counts as a violation of the “strict aliasing rule.”

The key word here is access. If you just create a pointer to incompatible types, everything is fine. Within ‘WriteAsync’ you just cast the received ‘uncopied_memory’ pointer into a ‘uint8_t’ pointer and access the provided data byte-wise, which is always safe, as you know (if you didn’t know, go back and read my previous post).

So far, so good. We don’t access stored memory through incompatible pointers; we only do pointer conversion, which is always safe, isn’t it? I replied to my reader that everything was fine, there was no violation of the “strict aliasing rule.”

Nevertheless, I couldn’t rid myself of this nagging feeling about whether the conversion/cast is really always safe.

POINTER CONVERSION RULES

The venerable book “The C Programming Language” by Brian Kernighan and Dennies Ritchie has this to say on pointer conversions:

A pointer to one type may be converted to a pointer to another type. The resulting pointer may cause addressing exceptions if the subject pointer does not refer to an object suitably aligned in storage. It is guaranteed that a pointer to an object may be converted to a pointer to an object whose type requires less or equally strict storage alignment and back again without change; the notion of “alignment” is implementation-dependent, but objects of the char types have least strict alignment requirements. As described in Par.A.6.8, a pointer may also be converted to type void * and back again without change.

Let me paraphrase: pointer conversion is safe unless the alignment requirements of the target type are less or equal to the alignment requirements of the source type. The converted pointer can be converted back to the original pointer without problems.

Though, the statement “The resulting pointer may cause addressing exceptions” is not clear to me. What does it mean? If the target type has stricter alignment requirements, do you get “addressing exceptions” when you create the pointer or when you access memory through it? Let’s assume that we are on a typical platform where objects of type ‘double’ are aligned on an 8-byte boundary and ‘chars’ have no alignment requirements (‘chars’ are aligned on a 1-byte boundary, so to speak.):

The conversion (1) is 100% safe and so is the corresponding read-access (2): the alignment requirements of type ‘char’ are less than the alignment requirements of type ‘double’. (4) is 100% unsafe, but what about (3)? Aren’t we just creating a pointer? To find out, I had to dig deep into my copy of the C99 language standard. Eventually, I found what I call the “pointer conversion rule”:

6.3.2.3/7 A pointer to an object or incomplete type may be converted to a pointer to a different object or incomplete type. If the resulting pointer is not correctly aligned for the pointed-to type, the behavior is undefined. Otherwise, when converted back again, the result shall compare equal to the original pointer. When a pointer to an object is converted to a pointer to a character type, the result points to the lowest addressed byte of the object.

There you have it and much more precise than the paragraph from “The C Programming Language.” Believe it or not—statement (3), the sheer pointer conversion already gets you into the realm of undefined behavior. Who knew?

So what does this mean regarding the conversion/cast from a ‘measurements_t’ pointer to an ‘uncopied_memory’ pointer? As we know from the standard, it would be safe if the alignment requirements for ‘uncopied_memory’ were less or equal to the alignment requirements of ‘measurements_t’.

In the previous example, we had to deal with primitive types (‘char’, ‘double’) whose alignment requirements can easily be determined. In order to find out about the alignment requirements for structs, we need to dive once more into the C99 standard document:

6.7.2.1/13 A pointer to a structure object, suitably converted, points to its initial member (or if that member is a bit-field, then to the unit in which it resides), and vice versa. There may be unnamed padding within a structure object, but not at its beginning.

Meditate on this for a while. Paraphrased, this all means that the alignment requirements of a struct are the same as the alignment requirements of a struct’s first member. So the question boils down to this: Are the alignment requirements of a ‘void’ pointer (‘uncopied_memory’s first member) less or equal to the alignment requirements of a ‘char’ (‘measurements_t’s first member)?

Of course, they’re not! A pointer type (like void*) is more or less just an integer type in disguise that is capable of holding all the addresses of your system and as such, pointer types have the same alignment requirements as regular integer types. On a 32-bit platform, pointers typically comprise 4 bytes. Thus, on typical 32-bit platforms, they will need to be aligned on 4-byte boundaries.

By contrast, a character (like the first element of measurements_t) comprises exactly one byte and thus has no alignment requirement—it can be stored at any address in memory.

Since the alignment requirements of the first element of ‘uncopied_memory’ are stronger than the alignment requirements of ‘measurements_t’, we can conclude that my advice to cast to ‘uncopied_memory’ may yield undefined behavior. Not because of the “strict aliasing rule,” but because of a violation of the “pointer conversion rules.”

To solve the problem, the type of the ‘dummy’ member of ‘uncopied_memory’ needs to be changed to ‘char’, a type that has the weakest alignment requirements. I have updated the “Dangerously Confusing Interfaces” post accordingly.