6
\$\begingroup\$

I created a quick function to convert n bytes into binary for my student. She is not on that level yet, but I think it would be best for her if my demonstrative functions aren't trash.

void binary (void* p, size_t nBytes)
{
    int iBit    = 0;
    int iByte   = 0;

    putchar('[');

    for(iByte = 0; iByte < nBytes; iByte++)
    {
        for(iBit = 0; iBit < CHAR_BIT; iBit++)
        {
            int bit = ((unsigned char* )p)[iByte] >> iBit;

            putchar((bit & 1) ? '1':'0');
        }

        if(iByte < nBytes-1)
        {
            printf("]\t[");
        }
    }

    printf("]\n");
}

it goes with a macro for easier use: #define BINARY(x) binary(&x, sizeof x) and the obvious disadvantage that it expects a variable and not cannot work with literals.

  • And yes, endianness is explained to her.
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Do you really want "[]\n" for binary(0,0)? How about "\n" instead? \$\endgroup\$ Commented Apr 29, 2021 at 19:38

4 Answers 4

8
\$\begingroup\$

It's not terrible as it stands, but I think there are some ways it might be improved.

Include all needed files

The function needs several #include files that are not listed. Specifically, it needs these:

#include <stddef.h>
#include <stdio.h>
#include <limits.h>

It's important to list those, especially for a beginner.

Be careful with signed and unsigned

In the binary function, the compares an int iByte to a size_t nBytes, but size_t is unsigned and int is signed. Instead, declare both variables as size_t types, or better, see the next suggestion.

Count down instead of up

If we count down instead of up, not only do many compilers generate more efficient code, but we also avoid the signed/unsigned problem mentioned above.

Declare variables in as small a scope as practical

Putting all definitions at the top of the function is an antique style of C. In modern C (C99 and later) we declare variables as late as practical, ideally as they are defined, to avoid problems of uninitialized variables.

Use a bitmask directly instead of calculating

I would write the inner loop like this:

for(unsigned char mask = 1U << (CHAR_BIT-1); mask; mask >>= 1) 

That makes it very clear that we're using a bitmask and how it is calculated and handled.

Use a convenience cast

Rather than casting p every time, I'd be inclined to declare an internal unsigned char * variable and use that instead.

Avoid encoding types in names

C is a statically typed language, so it is neither necessary nor desirable to encode the type within the name. See NL.5 for more. (Those are C++ guidelines, but this is equally applicable to C.)

Use pointers

Sooner or later, even beginners are going to need to learn how to use pointers. They have the considerable advantage here in simplifying the code.

Use const where practical

The function does not and should not modify the pointed-to value, so it's better to make that explicit and declare it const.

Consider separating the function into two

One way to think of this code is that it's printing one or more bytes with additional separators and formatting. That suggests an alternative which is to separate out the part that just prints the ones and zeroes from the loop.

Results

Here's the slightly refactored code using all of the suggestions above:

#include <stddef.h>
#include <stdio.h>
#include <limits.h>

void toBinary(const unsigned char *ptr) {
    for(unsigned char mask = 1U << (CHAR_BIT-1); mask; mask >>= 1) {
        putchar(*ptr & mask ? '1' : '0');
    }
}

void binary(const void* p, size_t nBytes) {
    for(const unsigned char* ptr = p; nBytes; --nBytes) {
        putchar('[');
        toBinary(ptr++);
        putchar(']');
        if(nBytes > 1) {
            putchar('\t');
        }
    }
    putchar('\n');
}

#define BINARY(x) binary(&x, sizeof x)

int main(void) {
    char a = 85;
    int b = 0x12345678;
    BINARY(a);
    BINARY(b);
}
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$
    – Malachi
    Commented Apr 29, 2021 at 18:29
  • \$\begingroup\$ This answer has different output that OP's when nBytes== 0 \$\endgroup\$ Commented Apr 29, 2021 at 19:30
  • \$\begingroup\$ The different output is intentional, as is printing the most significant bit first. As for moving to C2x, that's an excellent suggestion. I also wondered about returning a value such as the return value of putchar. \$\endgroup\$
    – Edward
    Commented Apr 29, 2021 at 20:52
6
\$\begingroup\$

Interface

I find it helps if we use verbs for function names. Instead of saying, "Here's some memory, let's binary() it," it's more natural to say, "Here's some memory, let's print() it." Now obviously print is much too general a name in C that has no overloading or namespaces, so we'd have to qualify: print_as_binary().

Since we don't plan to modify the pointed-to variable, we should accept p as a pointer to const void.

size_t is absolutely the right choice for a count variable such as nBytes.

Implementation

We don't need to create iBit and iByte up-front like that in modern C. We can give them smaller scope by declaring them within their respective for initialisations.

iByte really ought to match the type of nBytes - comparing signed and unsigned types is tricky, and we need to have at least the same range as what's passed to the function. The type of iBit doesn't matter, as we know that CHAR_BIT will be well within its range, regardless.

for (size_t iByte = 0;  iByte < nBytes;  iByte++)

When choosing the character to print, we could take advantage of the fact that C guarantees that 0 and 1 will have consecutive character codes:

putchar('0' + (bit & 1));

It's probably easier to print the separator string before the data, as that makes for a simpler test (iByte != 0).

We might want to assign p to an unsigned char* variable rather than explicitly casting it in the loop.

It's very surprising to see binary numbers written backwards like that. The standard convention in mathematics and programming is to write the most-significant bit first.

The macro

It's good practice to wrap all expansions of macro arguments within parentheses, so that if we are passed an expression, it is treated as a single unit:

#define BINARY(x) binary(&(x), sizeof (x))

Modified code:

#include <limits.h>
#include <stdint.h>
#include <stdio.h>

void print_as_binary(const void *p, size_t nBytes)
{
    const unsigned char *const q = p;

    putchar('[');
    for (size_t iByte = 0;  iByte < nBytes;  ++iByte) {
        if (iByte) {
            fputs("]\t[", stdout);
        }
        for (int iBit = CHAR_BIT;  iBit > 0;  --iBit) {
            int bit = q[iByte] >> (iBit - 1);
            putchar('0' + (bit & 1));
        }
    }

    printf("]\n");
}

#define PRINT_AS_BINARY(x) print_as_binary(&(x), sizeof (x))

int main(void)
{
    int t = 1000000;
    PRINT_AS_BINARY(t);
}
\$\endgroup\$
2
  • \$\begingroup\$ "Endian" only applies to separately-addressable chunks of a larger type. e.g. byte-addressable memory introduce the possibility of endianness for wider integers. A word-addressable machine doesn't have endianness for word-sized integers. Displaying the bits of a byte LSB-first isn't "little endian", it's just backwards, unless you're on a bit-addressable machine (like a small memory region on 8051). In C, endianness is meaningless for any type with sizeof(T) == 1, which is true by definition for unsigned char. It only has binary place value. (I wrote an answer that includes that.) \$\endgroup\$ Commented Apr 29, 2021 at 4:23
  • \$\begingroup\$ Yes, sorry for the slip. Edited with correct wording. \$\endgroup\$ Commented Apr 29, 2021 at 6:15
4
\$\begingroup\$

Many good ideas already covered by others. Some additional ones:

Literals

it goes with a macro for easier use: #define BINARY(x) binary(&x, sizeof x) and the obvious disadvantage that it expects a variable and not cannot work with literals.

OP's conclusion is incorrect. C has only 2 literals: string literals and compund literals. Macro works fine. Perhaps OP was thinking of constants.

Size first?

If you want to move toward the new C2x principle, consider void binary(size_t nBytes, const void* p).

Lots of I/O calls

To reduce I/O call overhead by 10x, form a buffer and print that.

Return info

Like other output functions, consider returning the error status.

More distinctive function name


Putting that together:

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

// Return 0 on success, else EOF
int binary_print(size_t nBytes, const void* p) {
  const unsigned char *uc = p;
  //       [   01....10   ]   \0
  char buf[1 + CHAR_BIT + 1 + 1];
  buf[0] = '[';
  buf[1 + CHAR_BIT] = ']';
  buf[1 + CHAR_BIT + 1] = '\0';

  while (nBytes-- > 0) {
    unsigned value = *uc++;
    for (int index = CHAR_BIT; index > 0; index--) {
      buf[index] = (char) ('0' + (value & 1u));
      value >>= 1;
    }
    if (fputs(buf, stdout) == EOF) {;
      return EOF;
    }
  }
  return putchar('\n') == EOF ? EOF : 0;
}

#define BINARY(x) binary_print(sizeof x, &x)

int main() {
    printf("%d\n", binary_print(0,0));
    printf("%d\n", BINARY("Hello"));
    printf("%d\n", BINARY((int){42}));
    printf("%d\n", BINARY((double){1.0}));
}

Output

(empty line)
0
[01001000][01100101][01101100][01101100][01101111][00000000]
0
[00101010][00000000][00000000][00000000]
0
[00000000][00000000][00000000][00000000][00000000][00000000][11110000][00111111]
0
\$\endgroup\$
1
  • \$\begingroup\$ Nice, that's more like what I was hoping mine would look like when I started writing it. And yeah, doing to formatting yourself is going to be significantly more efficient than letting printf loose on it. Compiling the same way as my answer, with just BINARY((int){42}) (no printf from main), I get ~44232 x86-64 instructions executed, and with another BINARY(int) the total instruction count goes up by about 1336. So it's less than half as many user-space instructions than my version using printf the same way yours uses fputs, even with line-buffered output flushing stdio every line. \$\endgroup\$ Commented Apr 30, 2021 at 0:28
3
\$\begingroup\$

The good:

  • Avoids assumptions on CHAR_BIT being 8. (There are C implementations for modern DSPs with CHAR_BIT = 16, 24, or even 32, so this is not totally irrelevant for portability.)

    Note that @Edward's original suggestion to use mask = 0x80 would undo that. You could use mask = 1U << (CHAR_BIT - 1). Interestingly, that shift can't overflow: if CHAR_BIT is large, by definition unsigned is still at least 1 char wide and thus you won't be shifting by more than the type-width. (And its value-range is to be at least as wide as unsigned char, IIRC, so it can't be the same width but with padding bits).

  • Strict-aliasing safe, char* and unsigned char* can read (and even write) any memory.

  • unsigned char is guaranteed to have no padding bits in its own object-representation, unlike other types including signed char. (And to be a binary integer). So yes, it's the right choice of type for dumping the object-representation of other objects in C.

The bad:

  • You prints bits backwards, in least-significant-first order!!! Endianness is a matter of byte order, not bit order. It's for the bytes within a wider integer (the char units for a type with sizeof(T) > 1), not for the bits within a word or byte. A right shift always divides by 2, and c & 1U is always the ones place.

    There is no sense in which it's meaningful to talk about the order bits are stored within a byte as machine-dependent (unless you're on a microcontroller like 8051 that has a range of bit-addressable memory). Being able to access separate unsigned char chunks of a uint32_t is what creates the notion of endianness, but an unsigned char is by definition the smallest access unit in C.

    Our English writing system with Arabic numerals uses most-to-least significant digits in left-to-right order. i.e. most-significant-first if printing 1 digit at a time into a normal left-to-right output stream. Within a chunk not separated by spaces, digits should always be in most-significant-first order, in any base including 2. For the same reason you'd want to dump 1<<4 as 16, not 61 in decimal.

    Treating more than 1 byte as a single chunk of output digits (e.g. a whole uint32_t with sizeof(uint32_t) == 4, or memcpy into an unsigned and format with printf("%x")) would introduce endianness considerations: different appearance on a little-endian machine from dumping it as one 32-bit chunk with the whole thing in MSB-first order vs. four separate 8-bit chunks each with their MSB at the left.

    There are various ways to solve this problem, like starting with a mask to select the high bit, rotating left by 1 to get the MSB to the bottom (except C only has shifts, not rotates), or store digits into a buffer.

  • You print a single [ if called with nBytes = 0. That's fine if that can never happen.

  • printf is somewhat expensive for a constant string; it has to check it for format characters. fputs would avoid that. Or batch up all the digits for a byte into a buffer, and printf("[%s]", buf) to actually take advantage of printf. (Every stdio call has to lock/unlock the stdout buffer, so putchar isn't as fast as you might hope, and one printf even with some formatting work to do might be faster.)

  • Style: Declaring variables at the top of the function is widely considered less readable, and it's been over 2 decades since C99 made that unnecessary.

    Also, there's a lot going on in some expressions. I'd find it easier to load an unsigned char once in the outer loop, then extract its bits. Probably also more efficient, letting the compiler keep it in a register instead of reloading across I/O function calls like putchar.

The unnecessary:

  • It is safe to assume that '0' + 1 == '1', ISO C guarantees it for decimal digits. So '0' + (c&1) is fine, and perhaps a useful demonstration for a student that not every conditional behaviour has to be by branching / selecting if you can turn it into a simple calculation. OTOH, it's not guaranteed that 'a' .. 'z' are contiguous; that's true in common character sets like ASCII / Unicode, but ISO C doesn't guarantee that. And C implementations for EBCDIC machines do exist.

  • You don't really need to use a variable-count shift. It's a mostly matter of style whether it's easier to increment / decrement a shift count, or to right-shift a mask or the number in a loop. But notably Intel CPUs (unlike AMD) have somewhat less efficient variable-count shifts than fixed-count (3 uops instead of 1), but a smart compiler could still optimize other instructions. And some embedded CPUs only have shift-by-1. Minimizing variable-count shifts is a minor optimization trick that only sometimes applies, and don't worry about it if your source is more readable with it.

Obviously there are a ton of ways to do this, differing in style and which specific output functions you use.

If you want to do it maximally efficiently, machine-specific (with intrinsics) tricks like doing 16 bits -> 16 bytes at once with x86 SSE2 SIMD are much faster than going 1 bit at a time. I updated my answer there with an AVX2 version of binary_dump_4B, which formats into [bits]\t[bits]\t... like this for exactly 4x 8-bit bytes, i.e. an x86-64 int32_t. puts or fputs output is still the most expensive part (now by a very large margin), so this is mostly for fun to see what the code would look like, or if you wanted to adapt to other ways to use the result.

(Ideally compilers would auto-vectorize simple loops like these if you store into a buffer instead of calling putchar for each digit separately, but in practice probably not even then). There is even a portable multiply bithack that can expand the bits of an 8-bit byte into a uint64_t, but storing that to memory in MSB-first printing order (with memcpy) would depend on the machine's endianness. (You've made it clear that the goal is simplicity, so you aren't interested in performance at its expense, but I mention this for the interest of other readers.)

Here's my version, which didn't come out as idiomatic as I'd hoped.

The loop structure is kind of what you'd do if writing by hand in asm (without SIMD or byte-at-a-time bithacks), which is why I came up with it in the first place. That's probably not a good thing, but I didn't need a separate loop counter.

I tried to find a way to avoid peeling the last iteration of the inner loop without totally rewriting it, but unfortunately, it's UB in C for a pointer to even exist that's not pointing to an object or to one-past-the-end. And all the ways I could think of to decrement a pointer either before or after storing would involve doing a decrement past the start of buf, which is not strictly legal even if we're trying to compare that value to anything. I did at least manage to use a while() loop instead of do{}while() which would separate the condition from the initialization.

@chux's answer used a loop counter for that inner loop, which ended up working nicely, but still a pointer increment for reading bytes of the source data.

Pointer increments are normal, and a style I often prefer, but indexing an unsigned char* with size_t is perfectly normal, too and something many other readers seem to find more comfortable. int as an index is ok if you don't care about being asked to dump gigantic buffers. Changing to a pointer-increment for the outer loop did reduce the need to think of names for variables, or for readers to keep track of them. (OTOH, debugging experience is often nicer if you keep your incoming function args unmodified.) Casting to const unsigned char* for every dereference of the void* was never very nice, and something you'd want to pull out into a variable anyway.

Positive things in this version:

  • Prints digits in the correct order, formatting into a char buffer starting with the LSB at the end, finishing with (what was) the MSB at the lowest address.
  • One printf per byte (unsigned char) to be dumped handling all the formatting and the digits should be good for efficiency.
  • Loading from the input once in the outer loop into a local var is good for efficiency: the compiler knows that the local var won't be modified by any function calls or stores. It also makes it easy to see how we're just shifting the bits of that integer. (I loaded into an unsigned int, because zero-extending into that preserves the binary value, and is at least as efficient to manipulate as an unsigned char.)
  • var names don't have i prefixes; that's not normal C style. (I borrowed the print_as_binary function name from @Toby's answer)
  • Easily adaptable to print only a newline if called with bytecount = 0. (Although yours could just have done if (!n) return; at the top)
  • Branchless handling of no tab ('\t') on the first iteration by unconditionally selecting a new format string after the first print. Keeps all the conditional stuff tied up in what printf does when you pass it a string. Using a 1 byte offset into a string literal avoids needing two separate string literals. A single unconditional assignment is more efficient than branching on a loop counter to maybe do extra printing.

Negative things in this version:

  • It introduces a buffer, making off-by-one errors and other pointer errors much more possible. I think the way I loop over it makes the correctness fairly easy to see, without any random +1 or -1 offsets to sizes. Introducing more variables would be more to keep track of and be overall worse, IMO.

  • Unusual usage of a %.8s or %.*s format (printf on cppreference) to print a char array that's not zero-terminated. (I could have made the array 1 longer and zeroed the last byte, but I chose the more efficient(?)1 way for fun; IDK how much more work it takes printf to parse this format vs. a plain %s!).

  • The inner loop "had to" peel the final iteration, so we repeat the '0' + (bits&1) logic. (With the &1 optimized away because it's the last iteration).

    If were were going to make the buffer larger to allow rearranging the inner and its condition to avoid going off the start of the array (which would be UB) while still detecting loop exit after storing the last bit inside the loop; probably the best bet would be to format the "\t[....]" manually in that buffer and using fputs or fwrite. (Especially after single-stepping into printf and seeing how much work it does parsing a format string and copying the fixed-string parts before/after the format.)

Some other changes are basically different for no reason, not particularly better, just to demonstrate the alternative.

// includes, macro, and main borrowed from @TobySpeight's answer.
#include <limits.h>
#include <stdint.h>
#include <stdio.h>

void print_as_binary(const void *input, size_t bytecount)
{
    // bytecount assumed to be non-zero, although we *could* use while(bytecount--) { } and print nothing for count==0
    const unsigned char *inp = input;
    const char *tab_format = "\t[%.*s]";
    const char *format = tab_format + 1;  // without the tab for first iteration
    do {
        unsigned int bits = *inp++;

        char buf[CHAR_BIT];
        char *bitp = buf + CHAR_BIT;    // one past end
        while(bitp != buf) {
            *--bitp = '0' + (bits&1);    // LSB into buf, working backwards from the end
            bits >>= 1;
        }
        *bitp = '0' + bits;   // it would be UB to end with bitp pointing before buf, so we can't use *bitp-- with a different start / end condition.  Peeling this last iteration works

        // alternative: fwrite(buf, 1, CHAR_BIT, stdout)  with separate fputs("\t[") and putchar(']')
        printf(format, CHAR_BIT, buf);  // format includes a width limit because buf[] is *not* 0-terminated.
        format = tab_format;            // branchless way to include a separator at the start of later prints.
    } while(--bytecount);

    putchar('\n');
}

#define PRINT_AS_BINARY(x) print_as_binary(&(x), sizeof (x))

int main(void)
{
    int t = 1000000;
    PRINT_AS_BINARY(t);
}

Tested and works, on the Godbolt compiler explorer, makes pretty decent looking asm for x86-64. But unfortunately compilers don't manage constant-propagation for a constant arg; I was kind of hoping it might inline as four 8-byte stores of ASCII digits, not even for a single uint8_t.

Compilers also don't auto-vectorize the inner loop even once the print function calls are sunk out of it. (They will fully unroll, so they still do see that the inner iteration count is fixed at CHAR_BIT.)


Footnote 1: I had expected that taking the width as another arg via a %.*s format would be slightly more work for printf than parsing a single digit, but it turns out that's not the case.

x86-64 Arch Linux GNU/Linux glibc 2.35-2 (which was built with gcc10.2), runs about 40 to 50 fewer instructions total according to perf stat --all-user, for the whole executable, for the variable-width format. Source compiled with the same gcc10.2, gcc -O2 -g -fno-plt itob.c -o itob-var-width. About 207,926 instructions executed +-2 or 3. But the version using a CPP stringify macro on CHAR_BIT to embed it into the format string (see initial version of this answer) ran about 207,963 to 207,976 instructions, more variability for some reason. This is only an approximate proxy for actually faster vs. slower; I didn't check if one had more branching than the other. A better version of glibc's read_int internal helper function might help; printf ends up doing more work than I expected to handle a single digit.

Similar results with gcc -O2 -static -no-pie -fno-pie on the same system (again measured with perf stat --all-user -r10 with perf 5.10 on Linux 5.9.14 on i7-6700k Skylake):

  • 45,630 +- 2 user-space insns per run of the whole program for "%.8s" embedded width
  • 45,568 +- 3 user-space insns for "%.*s" with an extra CHAR_BIT arg

(Calling PRINT_AS_BINARY() again from main after t++, %*.s runs ~48,635 instructions, so ~3067 is about the incremental cost of another 4 printf calls (and one putchar). (The 6 instructions per bit in the inner loop, and other overhead outside the printf calls, is minor compared to printf). For %.8s, the incremental cost is ~3095 instructions per PRINT_AS_BINARY. Formatting into a buffer manually and calling write manually, even written like this in plain compiled C without any bithacks, would likely take under 300 x86-64 instructions, bypassing stdio buffering. Again, real performance is measured in cycles, not instructions, and the system call still probably dominates, especially when we're line-buffered and writing to a TTY.)

I also tried Intel's sde -mix dynamic binary-instrumentation program to count user-space instructions, but it's not constant either. Perhaps some retries based on RDTSC wrapping?

\$\endgroup\$
16
  • \$\begingroup\$ @TobySpeight: Passing another arg to printf at runtime is presumably slower than having it embedded in the format string. (I think I mentioned that buried in a bullet point in the answer, but easy to miss.) I also considered using char buf[CHAR_BIT+1] and then printf(format, bitp) or something, or maybe just buf+1, but inventing more variables or scattering more +1s is more stuff to keep track of when making sure there's no off-by-one / array out of bounds error. If I wanted a larger array, I'd just store buf[CHAR_BIT] = 0; outside the outer loop and avoid field-width shenanigans. \$\endgroup\$ Commented Apr 29, 2021 at 7:09
  • \$\begingroup\$ @Toby: The thing that makes me guess it would be slower is that printf is variadic. The AMD64 System V calling convention isn't optimized for passing varargs the way Windows x64 is, so although it will probably have already paid the cost to dump its integer register args into an array on function entry, every time it wants to fetch another one it has to check an index to see if it should switch to the stack args. (Windows x64 has shadow space so it can dump args there, forming a contiguous array with the stack args. A few other calling conventions work like this, but ARM64 doesn't AFAIK) \$\endgroup\$ Commented Apr 29, 2021 at 7:23
  • 1
    \$\begingroup\$ @TobySpeight: but OTOH, assuming CHAR_BIT = 8, it's just parsing a single-digit integer until it reaches a non-digit, which should be pretty cheap if the code is written well and the compiler does a good job. e.g. in hand-written asm it looks like this: NASM Assembly convert input to integer?. Although if it does a locale-aware isdigit that could be slower. I'm probably going to go single-step into printf now and see what it looks like :/ \$\endgroup\$ Commented Apr 29, 2021 at 7:25
  • \$\begingroup\$ @TobySpeight: For the record, "\t[%.8s]" makes a binary that executes somewhere between 207963 and 207976 instructions in user-space, according to perf stat --all-user, on x86-64 Arch Linux, glibc 2.32-5 (built by GCC10.2.0). (glibc's read_int helper function doesn't get inlined, and it's written fairly inefficiently: godbolt.org/z/o983rT4Kb has a better version I think is safe, but having to check for int overflow makes it take more work than I expected, and non-inline) \$\endgroup\$ Commented Apr 29, 2021 at 11:24
  • 1
    \$\begingroup\$ @TobySpeight: After switching to \t[%.*s] and removing the clutter, it looks dramatically nicer; hadn't realized how much of the ugliness was coming from the STRINGIFY crap! \$\endgroup\$ Commented Apr 29, 2021 at 12:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.