A Generic API for Bit Manipulation in C
The built-in facilities for bit manipulation in C may be sufficient for interaction with memory-mapped device registers, but they are often insufficient for other uses. This article presents a solution to the bit manipulation problems that is portable to any platform.
Embedded software almost always involves some sort of bit manipulations — the reading, setting, and clearing of bit locations within memory. There are several reasons for this. Most often, bit manipulation occurs with respect to the registers of peripheral devices — DMA, serial, and interrupt controllers, for example — that are mapped into the processor’s memory space. Such manipulations are well handled with C’s built-in facilities.
However, situations arise in which bit manipulation must be done in a manner that is incompatible with these built-in facilities. For example, a lack of available RAM resources frequently results in bit-level manipulation to compress or decompress data, store tabular data efficiently, and implement complex algorithms in as little space as possible. Embedded systems may also interface to devices that receive or transmit binary encoded streams that must be either encoded or decoded in real time and in the processor’s memory.
Problems with C
Part of the reason for the C language’s success in embedded systems development is its ability to manipulate individual bits. If the manipulation in question involves only device registers, then the native C facilities aren’t too much trouble. The programmer just writes some macros that shift or mask the appropriate bits to get what is desired. However, if the data involves longer binary encoded records, the C API runs into a problem. I have, over the years, seen many lengthy, complex binary records described with the short or long integer bit-field definition facilities. C limits these bit fields to subfields of integer-defined variables, which implies two limitations: first of all, that bit fields may be no wider, in bits, than the underlying variable; and secondly, that no bit field should overlap the underlying variable boundaries. Complex records are usually composed of several contiguous long integers populated with bit-subfield definitions.
ANSI-compliant compilers are free to impose these size and alignment restrictions and to specify, in an implementation-dependent but predictable way, how bit fields are packed into the underlying machine word structure. Structure memory alignment often isn’t portable, but bit field memory is even less so.
Generally, one of three techniques is used to manipulate bit fields: the structure construct, with bit fields specified by a post declarator colon and integer field width; the << and >> shift operators; or single or multiple bit macro defines. Examples of each follow:
This struct defines how bit fields are normally specified and illustrates the syntactic complexity of C’s bit field usage. Bit field types may be signed int, unsigned int, or “plain” int. Unsigned ints are straightforward; signed ints are not. Whether the >> shift operator shifts zeros or ones in from the left depends on the implementation. For “plain” ints, the implementor may use signed, unsigned, or “pseudo-signed” (meaning that it contains only the unsigned value, but the usual unary conversions apply as if it is signed).
Unnamed bit fields may be specified to provide padding between named bit fields. The contents of the pad bits cannot be initialized nor used at run time. Thus, if the structure is to be output, there is no control over the value of these bits. In some cases this is unimportant because the data is to be read back into the same structure and pad bits. In other cases, for binary data, these values may be important.
Zero-length bit fields specify next-field machine alignment at the boundary appropriate to their type. This, again, is machine dependent, depending as it does on the natural unit of alignment of that type on that machine.
The shift operators are sometimes used to isolate bit fields by shifting left and then shifting right to zero out unwanted bits and to right justify the bits desired, like so:
which would isolate bits 29 to 2, right justified in i. The unwary may be taken in, if i is signed and negative (a 1 bit at bit position 31), by the implementation-specified zeros or ones shifted in from the left. Even more obscurely, the result is undefined if the right operand of a shift is negative, or the shift is greater than the size in bits of the left operand type.
Macro defines, with the wanted bits set to ones, are used to declare bit masks to be ANDed with some object variable to zero unwanted bits, while leaving the mask bits alone. You can isolate the necessary bits with something like:
#define MASK 0x0001fff0
but you still need a right shift to right justify the bit field, if arithmetic operation is desired on the bit field. The bit field is also limited to the boundaries of the underlying object — some fundamental C type — and thus cannot be used to extract some boundary-crossing bit field in an arbitrary binary record. More complicated operations to extract both ends of such a bit field and put them back together are necessary. This historical limitation of C has resulted in the construction of many standards-based binary records that have boundaries naturally suited to C. Just look at TCP/IP headers, for example.
My point here is not to provide a tutorial on the details and variability of C bit-field manipulation, but to illustrate that so much is implementation-dependent or undefined, and that considerable effort must be expended to manipulate complex binary records. See C: A Reference Manual, by Samuel P. Harbison and Guy Steele, Jr. (Englewood Cliffs, NJ: Prentice Hall, 1995), for all the necessary details.
An alternative solution
After many years of noodling with the C approach — both with my own code and several dark encounters with others’ code — I decided to write a simpler API. This API would be easy to use, would isolate the bit picking inside subroutines, and would make code based on the API more easily updated if the underlying machine changed either in instruction set or in the fundamental word length that could be bit shifted.
I thought it would be nice to have some routine(s) that would take an unsigned character array of arbitrary length and a bit number location, independent of char boundaries along the array, and insert (or extract) a bit field of specified arbitrary length at that location (well, almost arbitrary; I’ll explain in more detail in the section on caveats). And so were born the bit field insert, bfi(), and bit field extract, bfx() functions. Their prototypes follow:
void bfi(unsigned char *cptr,
• cptr—pointer to unsigned char array
• bit_offset—bit offset (starting from 1) from the start of the char array
• bit_len—bit length of field to insert
• value —value to be inserted
unsigned long bfx(unsigned char
• cptr—pointer to unsigned char array
• bit_offset—bit offset (starting from 1) from the start of the char array
• bit_len—bit length of field to extract
This solution seemed compellingly simple. Arbitrary binary records could now be specified in a C type-independent and underlying type boundary-independent way. I chose to start with bit 1 in order to make the bit numbering scheme as intuitive as possible — the first bit is bit 1. Examples of this API usage for a two-byte array follow.
At this point, cp will be set to 0x70ff.
I use integer arguments here in order to show explicitly the bit offsets and lengths; however, in practice I use defines for the offsets and bit field lengths, like so:
This approach allows the definition of a complex binary record to be described entirely by a series of field and length defines, and for easy visual scanning of these defines to understand the record. All extracted fields are right justified in the returned variable and can thus be arithmetically manipulated directly.
Now for the caveats
Normally, you needn’t check for reasonable values of bit_offset or bit_len. An excessive value for bit_offset will address beyond the end of the unsigned char array, just as any C subscripting misuse will do. The value of bit_len should be between 25 and 32, depending on the value of bit_offset.
The routines always use a memmove() of four bytes from the char array to temporary storage in which logical operations are performed, and the result is returned to the char array. This means that a bit field is limited to 32 bits. However, if the start bit of the bit field is in the middle of a byte, the bit field can only extend from the rest of the start byte to the end of the next three bytes. In the worst case — a start bit at the end of the start byte — only that bit plus three more bytes (24 bits) can be used, for a total of 25 bits. In most cases, this restriction is not a major one because arbitrarily long bit fields are almost never encountered in practice. Bit fields are keyed to be used in the natural short or long words of the machine, and these are not larger than a long int type. If a 32-bit bit field is used, it will almost always be aligned on a byte boundary. The start bit is then at the start of the first byte and a 32-bit bit field isn’t a problem for this API. If DEBUG is defined, checking is done.
Make sure that the bit_offset+bit_len doesn’t overrun the array, or that a value to be inserted is not too long to fit into the bit field. Otherwise, high-order bits will be truncated. If a value is negative, some of the propagated high-order sign bits will also be truncated.
Finally, because four bytes are always moved into temporary storage, the usage of the last bit of the array will cause three more bytes, beyond the end of the char array, to be read and subsequently written back. Assuming that bit_offset+bit_len is not beyond the end of the array, then no bit in those three extra bytes should be changed. Allocating the unsigned char array with three extra bytes will guard against this; however, in practice this precaution isn’t usually necessary. I’ve run dbx memory access-checking runs that do indeed uncover accesses in violation, but never with any consequence to program operation.
If all goes well, then exactly bit_len bits will be set, and no bit outside the bit field will be changed. I have provided a simple test program that implements the aforementioned series of bit field insertions and extractions, which you can download from www.embedded.com/code/1999code.htm. This code provides a three-byte, zeroed overrun guard, which is printed out to demonstrate that these bits haven’t been modified. I’ve tested this code on a little-endian Intel machine, as well as on the development big-endian Sun platform, and found it to operate correctly. As 64-bit machines and operating systems become more prevalent, extending the length of the allowable bit fields from 57 to 64 bits will be possible. This expansion is due to the available underlying machine word of 64 bits, on which logical operations may be performed.
I’ve also provided some more complex examples of the API usage. These examples are based on reading and writing World Meteorological Organization gridded binary records. These binary records were designed for the most efficient storage and transmission of meteorological data. Download these examples and see how you can apply the API to your individual needs. esp
Richard Hogaboom works for Metamor Information Technology Services at MIT Lincoln Laboratory. Reach him at firstname.lastname@example.org .