19
\$\begingroup\$

I'm writing a minimal C runtime targeting an old 32-bit Windows XP machine as a personal project. The C runtime provided by compilers is quite bloated. I wouldn't mind some library bloats up to several megabytes if this was some paid project, since even a very old PC would load it very fast anyway, but as a personal project, I'm just doing whatever comforts me. (1)

This printf can currently only handle %d, %lld, %u, and %llu.

The routine is optimized for size, not for speed. IO doesn't happen in a middle of a hot loop - if it does, it is not a hot loop - so it makes more sense to take the minimal amount of size in an executable.

  • div with a constant divisor is preferred over multiply and shift with the multiplicative inverse.
  • mov xl, byte [] instead of movsx exx, byte []; saves a byte
  • packed code, unaligned jump targets
  • Code duplication is avoided whenever possible.

Non-variadic functions follow the regparm(3) calling convention. The arguments are passed to eax, edx, and ecx in order, and the return value is stored in eax and edx. A local function divq10 disobeys the rule by also returning with ecx.

printf.s

    section .bss

stdout:
    resb 4

    section .text

    extern _GetStdHandle@4
    extern _WriteFile@20

err:
    ud2

    global _initstdout
_initstdout:
    push -11
    call _GetStdHandle@4
    cmp eax, -1
    je err
    mov [stdout], eax
    ret

divq10: ; edx:eax <- edx:eax / 10, ecx <- remainder
    push ebx
    mov ecx, eax
    mov eax, edx
    xor edx, edx
    mov ebx, 10
    div ebx
    mov ebx, eax
    mov eax, ecx
    mov ecx, 10
    div ecx
    mov ecx, edx
    mov edx, ebx
    pop ebx
    ret

llu2str: ; edx:eax -> *ecx (string), eax <- count
    push ebx
    push edi
    push esi
    push ebp
    mov edi, eax
    mov esi, edx
    mov ebp, ecx
    xor ebx, ebx
.0:
    inc ebx
    call divq10
    mov ecx, eax
    or ecx, edx
    jnz .0
    mov eax, edi
    mov edx, esi
    mov edi, ebx
.1:
    call divq10
    add ecx, '0'
    dec ebx
    mov [ebp + ebx], cl
    jnz .1
    mov eax, edi
    pop ebp
    pop esi
    pop edi
    pop ebx
    ret

    global _printf
_printf:
    push ebx
    push edi
    push esi
    push ebp
    lea ebp, [esp + 24]
    mov esi, [ebp - 4]
    sub esp, 1024
    mov edi, esp
.start:
    mov bl, [esi]
    test bl, bl
    jz .end
    cmp bl, '%'
    jne .copy
    inc esi
    mov bl, [esi]
    cmp bl, 'u'
    jne .d0
    mov eax, [ebp]
    add ebp, 4
    xor edx, edx
.u1:
    mov ecx, edi
    call llu2str
    add edi, eax
    jmp .next
.d0:
    mov bl, [esi]
    cmp bl, 'd'
    jne .ll
    mov eax, [ebp]
    add ebp, 4
    cdq
.d1:
    mov ecx, edx
    shr ecx, 31
    jz .u1
    mov byte [edi], '-'
    inc edi
    neg eax
    adc edx, 0
    neg edx
    jmp .u1
.ll:
    mov bl, [esi]
    cmp bl, 'l'
    jne err
    inc esi
    mov bl, [esi]
    cmp bl, 'l'
    jne err
    inc esi
    mov eax, [ebp]
    mov edx, [ebp + 4]
    add ebp, 8
    mov bl, [esi]
    cmp bl, 'u'
    je .u1
    cmp bl, 'd'
    je .d1
    jmp err
.copy:
    mov [edi], bl
    inc edi
.next:
    inc esi
    jmp .start
.end:
    mov eax, esp
    push 0
    push edi
    sub edi, eax
    push edi
    push eax
    push dword [stdout]
    call _WriteFile@20
    test eax, eax
    jz err
    add esp, 1024
    pop ebp
    pop esi
    pop edi
    pop ebx
    ret

test.c

void initstdout(void);
void printf();

void start() {
    initstdout();
    printf("Hello, world!\n");
    printf("%d %u %lld %llu\n", 0, 0, 0, 0);
    int dm = 1u << 31;
    int dx = (1u << 31) - 1;
    int ux = -1;
    long long lldm = 1llu << 63;
    long long lldx = (1llu << 63) - 1;
    long long llux = -1;
    printf("%d %d %d\n%lld %lld %lld\n", dm, dx, ux, lldm, lldx, llux);
    printf("%u %u %u\n%llu %llu %llu\n", dm, dx, ux, lldm, lldx, llux);
}

build.sh

O="-O3 -msse2 -fno-builtin -fno-asynchronous-unwind-tables"
S="-std=c11 -pedantic -masm=intel"
F="$O $S"
LF="--entry=_start --subsystem=console --enable-stdcall-fixup"
SYS="/c/Windows/SysWOW64"
gcc -c $F test.c
nasm -fwin32 printf.s
ld -or.exe $LF *.o *.obj $SYS/kernel32.dll

I used gcc and ld, but MSVC's cl and link should also work fine. I had to put --enable-stdcall-fixup to shut up warnings, but I currently don't know why those warnings are happening. AFAIK Windows API functions have _@ decorations on 32-bit, but the linker is complaining that I shouldn't have put those decorations.

output

Hello, world!
0 0 0 0
-2147483648 2147483647 -1
-9223372036854775808 9223372036854775807 -1
2147483648 2147483647 4294967295
9223372036854775808 9223372036854775807 18446744073709551615

(1) MinGW GCC creates a 100KB executable for a single call to printf, including all the initialization code, and its own fix-up code to patch the default Windows C runtime. MSVC provides a several-hundred-KB DLL runtime, which should always be provided as-is to distribute freely.

\$\endgroup\$
2
  • \$\begingroup\$ I think that you've already recognised this to have hobby (endearingly, "comfort") value only. If you want to dig into something like this where it actually has impact, consider targeting an embedded platform. \$\endgroup\$
    – Reinderien
    Feb 15 at 2:31
  • \$\begingroup\$ codegolf.stackexchange.com \$\endgroup\$
    – emanresu A
    Feb 16 at 8:53

4 Answers 4

15
\$\begingroup\$

If, for the sake of this exercise, codesize is the only thing that you care about, then I would dare suggest the following:

For divq10, not having to reload the constant will save 5 bytes, and using xchg with the EAX register is shorter as it is a 1-byte instruction. Total savings 12 bytes.

divq10: ; edx:eax <- edx:eax / 10, ecx <- remainder
 push ebx             push ebx
 mov ecx, eax         xor  ecx, ecx
 mov eax, edx         xchg eax, ecx
 xor edx, edx         xchg eax, edx
 mov ebx, 10          mov  ebx, 10
 div ebx              div  ebx
 mov ebx, eax         xchg eax, ecx
 mov eax, ecx         div  ebx
 mov ecx, 10          xchg ecx, edx
 div ecx              pop  ebx
 mov ecx, edx         ret
 mov edx, ebx
 pop ebx
 ret

In llu2str you essentially use the EDI and ESI registers for preservation. Why not simply push/pop the values so you can omit preserving these registers themselves? Total savings 10 bytes.

llu2str: ; edx:eax -> *ecx (string), eax <- count
 push ebx                 push ebx     
 push edi
 push esi
 push ebp                 push ebp
 mov edi, eax             push eax              ; (1)
 mov esi, edx             push edx              ; (2)
 mov ebp, ecx             mov  ebp, ecx
 xor ebx, ebx             xor  ebx, ebx
.0:                      .0:
 inc ebx                  inc  ebx
 call divq10              call divq10
 mov ecx, eax             mov  ecx, eax
 or ecx, edx              or   ecx, edx
 jnz .0                   jnz  .0
 mov eax, edi             pop  eax              ; (2)
 mov edx, esi             pop  edx              ; (1)
 mov edi, ebx             push ebx              ; (3)
.1:                      .1:
 call divq10              call divq10
 add ecx, '0'             add  ecx, '0'
 dec ebx                  dec  ebx
 mov [ebp + ebx], cl      mov  [ebp + ebx], cl
 jnz .1                   jnz  .1
 mov eax, edi             pop  eax              ; (3)
 pop ebp                  pop  ebp
 pop esi
 pop edi
 pop ebx                  pop  ebx
 ret                      ret

In _printf, when hopping to .d0, the BL register did not change and when branching to .ll it didn't change either. You can omit mov bl, [esi] that reloads it.
The code to see if the number is negative mov ecx, edx shr ecx, 31 jz .u1 can be replaced by the shorter test edx, edx jns .u1.
Checking for the double 'll' can happen in one go:

.ll:                     .ll:
 mov bl, [esi]            cmp  word [esi], 'll'
 cmp bl, 'l'              jne  err
 jne err                  inc  esi
 inc esi                  inc  esi
 mov bl, [esi]
 cmp bl, 'l'
 jne err
 inc esi
\$\endgroup\$
9
\$\begingroup\$

Make Your Function Modular and Re-Usable

Let’s say you want to call fprintf( stderr, "Error opening file: s.\n", errMsg ); Your function can’t do that, because it only implements printf. You could copy and paste everything but the code that initializes the output handle to standard output, but that would be silly. What you obviously would do, especially when saving space, is to implement printf( format, ... ) as a wrapper for vfprintf( stdout, format, args ). Then fprintf() and vprintf() are also trivial wrappers for vfprintf.

Now let’s say you want to add snprintf() someday. Can you re-use this code? Well, you can copy-and-paste it. But it’s hardcoded to call _WriteFile@20. So you have to replace that everywhere with a call to strncpy instead.

But you can instead define the output function as a higher-order type:

/* On Windows, we use low-level file I/O.
 */
#if defined(_WIN32) && !defined(_WIN64)

#include <io.h>

typedef int fd;

#else // Some other OS.  Probably POSIX-compatible?
#error "Implement low-level I/O for this platform."
#endif // Platform check.

/* An output function takes a buffer, a count of characters to output, and a
 * pointer to a state object specific to that output function, which it
 * updates.
 *
 * Returns the number of bytes written on success, or a negative value on
 * failure.  Might also set errno.
 */
typedef int (*output_func)( const char*, size_t, void* );

static int printfd_output_func( const char* const buffer,
                                const size_t n,
                                void* const p
                              )
/* Passes a buffer of size n to a low-level output function.  The
 * pointer argument p is a pointer to a file descriptor, cast to a void*.
 *
 * Returns n on success, or a negative value on error.
 */
{
#if defined(_WIN32) && !defined(_WIN64)
  return _write( *(fd*)p, buffer, n );
#else
#  error "Implement printf_output_func()!"
#endif
}

The output_func type is a function that takes an input buffer, a range of characters to copy, and an arbitrary pointer to some state that can vary. For this example, which outputs to a file descriptor, it can be as simple as a pointer to a file descriptor (or you could even pass the file descriptor as a machine word without going through a pointer conversion, in assembler). For the snprintf example, the relevant state object might be the current position in the output buffer and the number of bytes remaining.

if you don’t want the overhead of pushing and popping arguments on the stack, many compilers and assemblers for Win32 will let you give this function the __fastcall convention, which is very similar to the one you used.

This lets the function you actually implement in another source file become something like:

extern int my_output_helper( output_func engine,
                             void* output_state,
                             const char* format,
                             va_list args
                           );

Essentially all of the standard library can be implemented with this plus a small handful of short output functions. For example, printf becomes:

int my_printf( const char* const format, ... )
{
  fd fd_stdout = 1;
  va_list args;
  va_start( args, format );

  const int written = my_output_helper( printfd_output_func,
                                        &fd_stdout,
                                        format,
                                        args
                                      );
  va_end(args);
  return written;
}

Whereas fprintf would instead look up the file descriptor of the FILE* you pass in as the first argument and pass that to the output_state, vfprintf would pass it the va_list argument it received, and different output functions would support printing to a Windows file handle, a string, a message window and so on.

if you want to save space, don’t rewrite the same function more than once! And, as a nice bonus, you get runtime polymorphism.

Have the Assembler Mangle Names For You

it should let you declare external functions for both the C calling convention and the STDCALL convention used by Windows system calls. There are also .inc and .lib header files for the Windows API in MASM.

MASM Compatibility

You write that you haven’t tested with other assemblers, but you expect it to be compatible. Unfortunately, ML.EXE doesn’t support gas-style local labels, such as .start:.

Consider Writing MSVC-Compatible Code with LLVM

A command line such as

clang --std=c17 -target i386-windows-pc-msvc -march=i686 -Os -Wall -Wextra -Wpedantic -Wconversion -Wdeprecated -o myprintf.exe myprintf.c my_output_helper.obj

will compile code compatible with gcc and link it with the standard MSVC runtime, instead of MINGW’s. (You can also get it to compile for Win32 using MINGW.) There is also a LLVM assembler that should be more compatible with gas than MASM is.

How Serious Are You About Making This Useful?

Time for the frame challenge. You likely already know this and are just reinventing the wheel as a learning exercise. If so, great!

In practice, you’re not going to be able to avoid loading the C runtime in a real-world app. There are some embedded applications where optimizing individual bytes matters, and you would want to link to a smaller replacement for the standard library, but those do not run on top of Win32.

In that case, the 100K or so overhead of the runtime is a cost you’re going to have to pay. And once you do, the standard library runtime (MSVCRT, libc.so, etc.) is something that will always be loaded into system memory anyway. And you’ll eventually want more than 100K worth of features in your version anyway. Using the shared library takes up less space than reimplementing and statically linking it.

You’re also not going to save significant amounts of space writing the function in assembly, as opposed to compiling a portable version implementing a state machine with the optimize-for-space setting. It is, however, a great exercise to learn i386 assembler!

Always Check for Buffer Overruns

Always, always, always! Really.

Currently, despite optimizing for size, you’re allocating a full kibibyte on the stack as a buffer before calling the function, and then never bounds-checking in the function itself.

In this case, you actually can guarantee that three bytes of ASCII per byte of binary integer is enough to hold the decimal digits (since the maximum value of a N-byte unsigned int is 2**8**N = 256**N < 1000**N = 10**3**N), and you can get the size of the input with sizeof(long long int). You can prove a tighter bound, 5*N/2, if you want. (Technically: assuming 8-bit bytes, but you’re writing in x86 assembler anyway.)

But it’s a very bad habit to skip security checks because you think you can assume your buffers are big enough. At the very least, pass in the bound of your output buffer and check you don’t exceed it.

Edit:

As an example of how easy it is to make this kind of mistake in C, the first version I posted had a risk in that, if you called u2a with the start and the end of the buffer switched, the compiler would not notice anything was wrong, but would gleefully underflow and cause a memory-corruption bug. This was because I only checked whether the lower bound of the array was equal to the iterator each time it decremented, not whether it was less than or equal.

I ended up going back and refactoring to always take a fixed-sized buffer, and only generate pointers within that buffer internally. I still left an assertion that the pointer stays within range.

So you can see why I’m so paranoid about buffer overruns in C.

Start from the End of the Buffer and Count Down

Currently, you have two loops that call divq10, one to count up to the number of digits, and one to count back down to 0. You can simplify this a lot by passing the start and end of the buffer, and filling each digit in at the end. You can then return a pointer to the start of the numeral within the buffer. This also eliminates the need to have a separate divq10 function, since now you only need the code in a single loop, and do not have to call it at all.

Avoid Copying the Format String

Copying to a 1 KiB buffer is not only inefficient in both time and memory, it’s insecure because you never check if your user-provided format string smashes the stack. What you should be doing instead is tracking the range of bytes that you want to echo literally, and flushing it whenever you see a % sign in the format string. This involves making more system calls, but your stated requirements are that you don’t care about speed, only space.

A Sample Implementation

This is neither optimized for space nor written in assembler, but it could give you a good starting point, in the right compiler.

You can definitely improve on this. It doesn’t support %ll, but does support %s and %%. I added my_snprintf and my_printf as examples of two different output callbacks, and put in a lot of error checking.

if, however, you see it as worthwhile to replace part of the generated code by hand-optimized assembly, compiling to assembly (with -S on most compilers or FAu on MSVC) and editing the output listings is a good place to begin.

myprintf.h:

#ifndef MYPRINTF_H_INCLUDED
#  define MYPRINTF_H_INCLUDED

/* You might wish to reimplement this as part of your project:
 */
#include <stdarg.h>
#include <stddef.h>

#ifndef EXIT_SUCCESS
#  define EXIT_SUCCESS 0
#endif

#if __GNUC__ || __clang__
#  define NORETURN __attribute__((noreturn))
#elif _MSC_VER
#  define NORETURN __declspec(noreturn)
#else
#  define NORETURN /**/
#endif

#ifdef _M_IX86
#  define OUTPUT_FUNC __fastcall
#elif __i386 && __GNUC__
#  define OUTPUT_FUNC __attribute__((fastcall))
#else
#  define OUTPUT_FUNC /**/
#endif

#if __clang__
#  define MUSTTAIL __attribute__((musttail))
#else
#  define MUSTTAIL /**/
#endif

extern int my_printf( const char* format, ... );
extern int my_snprintf( char* s, size_t n, const char* format, ... );
extern void NORETURN fatal_error(const char* msg);

/* An output function takes a buffer, a count of characters to output, and a
 * pointer to a state object specific to that output function, which it
 * updates.
 *
 * Returns the number of bytes written on success, or a negative value on
 * failure.  Might also set errno.
 */
typedef int (OUTPUT_FUNC * output_func)( const char*, size_t, void* restrict );

#endif /* MYPRINTF_H_INCLUDED */

myprintf.c:

#include <assert.h>
#include <limits.h> // for INT_MAX
#include <stdlib.h> // For abort
#include <string.h> // For memcpy, strlen
#include "myprintf.h"

/* On Windows, we use low-level file I/O.
 */
#if defined(_WIN32) && !defined(_WIN64)

#include <io.h>

typedef int fd_t;
#define FD_STDOUT (1)
#define FD_STDERR (2)

#else // Some other OS.  Probably POSIX-compatible?

#error "Implement low-level I/O for this platform."
#define OUTPUT_FUNC /**/

#endif // Platform check.

#define MSG_OVERFLOW_ERR "Overflow error."

NORETURN void fatal_error(const char* const msg)
{
  _commit(FD_STDOUT); // Don't cross the streams!
  _write( FD_STDERR, msg, strlen(msg) );
  abort();
}

static int OUTPUT_FUNC
  printfd_output_func( const char* const buffer,
                       const size_t n,
                       void* const restrict p
                     )
/* Passes a buffer of size n to a low-level output function.  The
 * pointer argument p is a pointer to a file descriptor, cast to a void*.
 *
 * Returns n on success, or a negative value on error.
 */
{
#if defined(_WIN32) && !defined(_WIN64)
  return _write( *(fd_t*)p, buffer, n );
#else
#  error "Implement printf_output_func()!"
#endif
}

typedef struct snprintf_state_t {
  char* it;
  size_t remaining; // Leave space for the terminatng null!
} snprintf_state_t;

static int OUTPUT_FUNC
  snprintf_output_func( const char* const buffer,
                        const size_t n,
                        void* const restrict p
                      )
{
  snprintf_state_t *state = p;
  const size_t nbytes = (n <= state->remaining) ? n : state->remaining;
  if ( nbytes > (unsigned)INT_MAX ) {
    fatal_error(MSG_OVERFLOW_ERR);
  }
  memcpy( state->it, buffer, nbytes );
  state->it += nbytes;
  state->remaining -= nbytes;
  return (int)nbytes;
}

extern int my_output_helper( output_func engine,
                             void* restrict engine_state,
                             const char* format,
                             va_list args
                           );

int my_printf( const char* const format, ... )
{
  fd_t fd_stdout = FD_STDOUT;
  va_list args;
  va_start( args, format );

  const int written = my_output_helper( printfd_output_func,
                                        &fd_stdout,
                                        format,
                                        args
                                      );
  va_end(args);
  return written;
}

int my_snprintf( char* const s, size_t n, const char* const format, ... )
{
  va_list args;
  va_start( args, format );

  snprintf_state_t state = { .it = s,
                             .remaining = n-1
                           };

  const int written = my_output_helper( snprintf_output_func,
                                        &state,
                                        format,
                                        args
                                      );

  assert((unsigned)written < n); // This SHOULD be redundant.
  s[written] = '\0';

  va_end(args);
  return written;
}

my_output_helper.c:

#include <assert.h>
#include <limits.h> // For INT_MAX
#include <string.h> // For strlen
#include "myprintf.h"

#define MSG_WRITE_ERR "Write error."
#define MSG_FORMAT_ERR "Invalid format string."
#define MSG_OVERFLOW_ERR "Overflow error."
#define MSG_BOUNDS_ERR  "Array access out of bounds!"

#define ITOA_BUF_LEN (sizeof(int)*5U/2U + 2U)

 static char* u2a_helper( const unsigned n,
                          char* const current,
                          const char* const lower_bound
                        )
/* Meant to be called only from u2a.  Fills in the buffer from back to front,
 * stopping if it reaches the start of the buffer (which should not happen).
 */
{
  static const unsigned radix = 10;
 
  const unsigned residue = n/radix;
  *current = (char)('0' + n%radix);
  
  if (residue > 0) {
    assert( current > lower_bound );
    MUSTTAIL return u2a_helper( residue, current-1, lower_bound );
  }
  
  return current;
}

static char* u2a( const unsigned n,
                  char buffer[ITOA_BUF_LEN]
                )
/* Fills a buffer from back to front with the ASCII representation of
 * n.  The string is null-terminated.
 *
 * Returns a pointer to the subrange of the buffer containing the
 * numeral.
 */
{
  buffer[ITOA_BUF_LEN-1] = '\0';
  return u2a_helper( n, &buffer[ITOA_BUF_LEN-2], buffer );
}

int print_unsigned( const unsigned n,
                    const output_func func_engine,
                    void* const engine_state
                  )
/* Prints n as a decimal numeral using the given output callback with the
 * provided state.  Only returns if there waas no error (although some digits
 * might not have been printed).
 */
{
  char buffer[ITOA_BUF_LEN] = {0};
  const char* const ascii_val = u2a( n, buffer );
  const size_t len = ITOA_BUF_LEN - (size_t)(ascii_val - buffer) - 1;
  const int result = func_engine( ascii_val, len, engine_state );
  if (result < 0) {
    fatal_error(MSG_WRITE_ERR);
  }
  
  return result;
}

int print_signed( const int n,
                  const output_func func_engine,
                  void* const engine_state
                )
/* Prints n as a decimal numeral using the given output callback with the
 * provided state.  Only returns if there waas no error (although some digits
 * might not have been printed).
 */
{
  char buffer[ITOA_BUF_LEN] = {0};
  const unsigned a = (unsigned)((n >= 0) ? n : -n);
  char* const ascii_val = u2a( a, buffer );
  if (n < 0) {
    if (ascii_val == buffer) {
    /* Generating a pointer that underflows is technically undefined behavior,
     * which some compiler writers consider enough of an excuse to break a
     * program and introduce security bugs.  Therefore, we must check for
     * underflow before decrementing the pointer.
     */
      fatal_error(MSG_BOUNDS_ERR);
    }
    char* const negative_val = ascii_val - 1;
    *negative_val = '-';
    const size_t len = ITOA_BUF_LEN - (size_t)(negative_val - buffer) - 1U;
    const int result = func_engine( negative_val, len, engine_state );
    if (result < 0) {
      fatal_error(MSG_WRITE_ERR);
    }

    return result;
  } // end if (n < 0)

  const size_t len = ITOA_BUF_LEN - (size_t)(ascii_val - buffer) - 1U;
  const int result = func_engine( ascii_val, len, engine_state );
  if (result < 0) {
    fatal_error(MSG_WRITE_ERR);
  }
  
  return result;
}

static int fmt_state_literal( const size_t chars_written,
                              const size_t chars_to_echo,
                              const output_func func_engine,
                              void* restrict engine_state,
                              const char* const format,
                              va_list args
                            );
                            
static int fmt_state_percent( const size_t chars_written,
                              const size_t chars_to_echo,
                              const output_func func_engine,
                              void* restrict engine_state,
                              const char* const format,
                              va_list args
                            );
                            
static int fmt_state_width_mod( const size_t chars_written,
                                const size_t chars_to_echo,
                                const output_func func_engine,
                                void* restrict engine_state,
                                const char* const format,
                                va_list args
                              );


static int fmt_state_width_mod( const size_t chars_written,
                                const size_t chars_to_echo,
                                const output_func func_engine,
                                void* const restrict engine_state,
                                const char* const format,
                                va_list args
                              )
{
  (void)chars_to_echo; // Suppress unused argument warning.
  switch(*format) {
    case 'u': {
      const int result = print_unsigned( va_arg( args, unsigned int ),
                                         func_engine,
                                         engine_state
                                        );
      MUSTTAIL return
        fmt_state_literal( chars_written + (unsigned)result,
                           0,
                           func_engine,
                           engine_state,
                           format + 1,
                           args
                         );
    }
    case 'd': {
      const int result = print_signed( va_arg( args, int ),
                                       func_engine,
                                       engine_state
                                     );
      MUSTTAIL return
        fmt_state_literal( chars_written + (unsigned)result,
                           0,
                           func_engine,
                           engine_state,
                           format + 1,
                           args
                         );
    }
    default:
      fatal_error(MSG_FORMAT_ERR);
  }
}

static int fmt_state_percent( const size_t chars_written,
                              const size_t chars_to_echo,
                              const output_func func_engine,
                              void* const restrict engine_state,
                              const char* const format,
                              va_list args
                            )
{
  (void)chars_to_echo; // Suppresses warning.
  switch (*format) {
    case 'l':
      static_assert( sizeof(long) == sizeof(int), "" );
      /* We do not yet support %lld, %llu, or %ls. */
      MUSTTAIL return
        fmt_state_width_mod( chars_written,
                             0,
                             func_engine,
                             engine_state,
                             format + 1,
                             args
                           );
    case 'h':
      /* A short variadic argument is always widened. */
      MUSTTAIL return 
        fmt_state_width_mod( chars_written,
                             0,
                             func_engine,
                             engine_state,
                             format + 1,
                             args
                           );
    case 'u': {
      const int result = print_unsigned( va_arg( args, unsigned int ),
                                         func_engine,
                                         engine_state
                                        );
      MUSTTAIL return
        fmt_state_literal( chars_written + (unsigned)result,
                           0,
                           func_engine,
                           engine_state,
                           format + 1,
                           args
                         );
    }
    case 'd': {
      const int result = print_signed( va_arg( args, int ),
                                       func_engine,
                                       engine_state
                                     );
      MUSTTAIL return
        fmt_state_literal( chars_written + (unsigned)result,
                           0,
                           func_engine,
                           engine_state,
                           format + 1,
                           args
                         );
    }
    case 's': {
      const char* const s = va_arg( args, const char* );
      const int result = func_engine( s,
                                      strlen(s),
                                      engine_state
                                    );
      if (result < 0) {
        fatal_error(MSG_WRITE_ERR);
      }
      MUSTTAIL return
        fmt_state_literal( chars_written + (unsigned)result,
                           0,
                           func_engine,
                           engine_state,
                           format + 1,
                           args
                         );
    }
    case '%': {
      static const char percent_sign[] = {'%'};
      const int result = func_engine( percent_sign,
                                      sizeof(percent_sign),
                                      engine_state
                                    );
      if (result < 0) {
        fatal_error(MSG_WRITE_ERR);
      }
      MUSTTAIL return
        fmt_state_literal( chars_written + (unsigned)result,
                           0,
                           func_engine,
                           engine_state,
                           format + 1,
                           args
                         );
    }
    default:
      fatal_error(MSG_FORMAT_ERR);
  }
}

static int fmt_state_literal( const size_t chars_written,
                              const size_t chars_to_echo,
                              const output_func func_engine,
                              void* const restrict engine_state,
                              const char* const format,
                              va_list args
                            )
{
  switch(*format) {
    case '\0': {
      const int result = func_engine( format - chars_to_echo,
                                      chars_to_echo,
                                      engine_state
                                    );
      if (result < 0) {
        fatal_error(MSG_WRITE_ERR);
      }
      
      if ( (unsigned)(INT_MAX - result) < chars_written ) {
      /* Signed underflow is undefined behavior, so we must again code
       * defensively, and check for it without writing undefined behavior
       * that would make some compilers gleefully break the check.
       */
        fatal_error(MSG_OVERFLOW_ERR);
      }

      return (int)chars_written + result;
    }
    case '%': {
      const int result = func_engine( format - chars_to_echo,
                                      chars_to_echo,
                                      engine_state
                                    );
      if (result < 0) {
        fatal_error(MSG_WRITE_ERR);
      }
      MUSTTAIL return
        fmt_state_percent( chars_written + (unsigned)result,
                           0,
                           func_engine,
                           engine_state,
                           format + 1,
                           args
                          );
    }
    default:
      MUSTTAIL return
        fmt_state_literal( chars_written,
                           chars_to_echo + 1,
                           func_engine,
                           engine_state,
                           format + 1,
                           args
                         );
  }
}

int my_output_helper( const output_func func_engine,
                      void* const restrict engine_state,
                      const char* const format,
                      va_list args
                    )
{
  return fmt_state_literal( 0, 0, func_engine, engine_state, format, args );
}

And, finally, test_myprintf.c:

#include <assert.h>
#include "myprintf.h"

int main(void)
{
  const int n1 = my_printf( "Message: %s, %s", "hello", "world!" );
  my_printf( " (%d)\n", n1 );
  const int n2 = my_printf( "1 + 1 = %u, and %hu%% not %lu.", 1+1, 100, 1234567890UL );
  my_printf( " (%d)\n", n2 );
  const int n3 = my_printf( "%hd minus %d is %ld.", 1, 2000000000, 1 - 2000000000 );
  my_printf( " (%d)\n", n3 );
  char abc[4] = "xxxx";
  my_snprintf( abc, sizeof(abc), "ABC!!! THIS SHOULD NOT PRINT !!!" );
  const int n4 = my_printf( "%s and %d.", abc, 123 );
  my_printf( " (%d)\n", n4 );

  return EXIT_SUCCESS;
}

Let’s take a closer look at the code four major compilers generate for this, on x86. The function we’ll be looking at is u2a_helper, corresponding most closely to the code you shared:

 static char* u2a_helper( const unsigned n,
                          char* const current,
                          const char* const lower_bound
                        )
/* Meant to be called only from u2a.  Fills in the buffer from back to front,
 * stopping if it reaches the start of the buffer (which should not happen).
 */
{
  static const unsigned radix = 10;
 
  const unsigned residue = n/radix;
  *current = (char)('0' + n%radix);
  
  if (residue > 0) {
    assert( current > lower_bound );
    MUSTTAIL return u2a_helper( residue, current-1, lower_bound );
  }
  
  return current;
}

GCC 11.2 does an excellent job with this program. (I slightly modified it to compile on Linux, with -std=c17 -m32 -Os -fomit-frame-pointer -foptimize-sibling-calls -march=x86-64-v3). Even without support for the musttail extension, to tell it that tail-call optimization is necessary, it was smart enough to perform it.

.LC1:
        .string "current > lower_bound"
u2a_helper:
        push    edi
        mov     edi, 10
        push    esi
        mov     esi, ecx
        mov     ecx, edx
        push    ebx
        mov     ebx, eax
.L4:
        mov     eax, ebx
        xor     edx, edx
        div     edi
        add     edx, 48
        mov     BYTE PTR [ecx], dl
        cmp     ebx, 9
        jbe     .L1
        cmp     ecx, esi
        ja      .L3
        push    OFFSET FLAT:__PRETTY_FUNCTION__.1
        push    76
        push    OFFSET FLAT:.LC0
        push    OFFSET FLAT:.LC1
        call    __assert_fail
.L3:
        dec     ecx
        mov     ebx, eax
        jmp     .L4
.L1:
        pop     ebx
        mov     eax, ecx
        pop     esi
        pop     edi
        ret

Nearly all of this is preamble and the underflow check (which could be omitted in hot code, since we “know” the buffer is always big enough). The critical path compiles to a div loop nine instructions long. This is essentially what you wanted, and any improvement you could get by hand-optimizing that further would be extremely marginal.

Next, clang 13.0.0. This is a great compiler to use on Windows, since it supports -target i386-windows-pc-msvc, with variations for specific CPUs and versions of Visual C to emulate. Crucially, this target generates code compatible with Microsoft’s runtime, and other Windows libraries and headers. It can also target MingW32 and generate code compatible with GCC.

Clang sees that u2a_helper is called only from u2a and inlines it, so I’ll show u2a.

    .def     _u2a;
    .scl    3;
    .type   32;
    .endef
_u2a:                                   # -- Begin function u2a
                                        # @u2a
# %bb.0:
    pushl   %ebp
    pushl   %ebx
    pushl   %edi
    pushl   %esi
    movl    %edx, %esi
    movl    %ecx, %ebx
    movb    $0, 11(%edx)
    movl    $-858993459, %ebp               # imm = 0xCCCCCCCD
    movl    %ecx, %edx
    mulxl   %ebp, %eax, %eax
    leal    10(%esi), %edi
    shrl    $2, %eax
    andl    $-2, %eax
    leal    (%eax,%eax,4), %eax
    subl    %eax, %ecx
    orb $48, %cl
    movb    %cl, 10(%esi)
    cmpl    $10, %ebx
    jb  LBB1_4
LBB1_1:                                 # =>This Inner Loop Header: Depth=1
    cmpl    %esi, %edi
    ja  LBB1_3
# %bb.2:                                #   in Loop: Header=BB1_1 Depth=1
    pushl   $27
    pushl   $"??_C@_1CG@MKELDBMD@?$AAm?$AAy?$AA_?$AAo?$AAu?$AAt?$AAp?$AAu?$AAt?$AA_?$AAh?$AAe?$AAl?$AAp?$AAe?$AAr?$AA?4?$AAc?$AA?$AA@"
    pushl   $"??_C@_1CM@MNODEPHG@?$AAc?$AAu?$AAr?$AAr?$AAe?$AAn?$AAt?$AA?5?$AA?$DO?$AA?5?$AAl?$AAo?$AAw?$AAe?$AAr?$AA_?$AAb?$AAo?$AAu?$AAn?$AAd?$AA?$AA@"
    calll   __wassert
    addl    $12, %esp
LBB1_3:                                 #   in Loop: Header=BB1_1 Depth=1
    movl    %ebx, %edx
    mulxl   %ebp, %edx, %edx
    shrl    $3, %edx
    mulxl   %ebp, %eax, %eax
    shrl    $2, %eax
    andl    $-2, %eax
    leal    (%eax,%eax,4), %eax
    movl    %edx, %ecx
    subl    %eax, %ecx
    orb $48, %cl
    movb    %cl, -1(%edi)
    decl    %edi
    cmpl    $99, %ebx
    movl    %edx, %ebx
    ja  LBB1_1
LBB1_4:
    movl    %edi, %eax
    popl    %esi
    popl    %edi
    popl    %ebx
    popl    %ebp
    retl

Clang transforms the tail-recursive / and % expressions into a mul loop, even when told to optimize for space. It supports a musttail extension, which I used heavily for this functional-style code, to force it to eliminate tail calls. Without the hint, it did not correctly compile the state machine. It’s my preferred compiler largely because of this.

ICX 2022.0.0 is based on Clang, and supports the same extensions, but only Intel CPUs as targets. It generates similar code, but can often optimize better. It therefore, unsurprisingly, also inlines u2a_helper. In this case, I tested on Linux again.

u2a:                                    # 
        push    ebp
        push    ebx
        push    edi
        push    esi
        sub     esp, 12
        mov     esi, edx
        mov     byte ptr [edx + 11], 0
        mov     edi, -858993459
        mov     edx, ecx
        mulx    edx, edx, edi
        lea     eax, [esi + 10]
        shr     edx, 2
        and     edx, -2
        lea     edx, [edx + 4*edx]
        mov     ebx, ecx
        sub     ebx, edx
        or      bl, 48
        mov     byte ptr [esi + 10], bl
        cmp     ecx, 10
        jb      .LBB1_3
.LBB1_1:                                # =>This Inner Loop Header: Depth=1
        cmp     eax, esi
        jbe     .LBB1_4
        mov     edx, ecx
        mulx    ebp, ebp, edi
        shr     ebp, 3
        mov     edx, ebp
        mulx    ebx, ebx, edi
        shr     ebx, 2
        and     ebx, -2
        lea     ebx, [ebx + 4*ebx]
        sub     edx, ebx
        or      dl, 48
        mov     byte ptr [eax - 1], dl
        dec     eax
        cmp     ecx, 99
        mov     ecx, ebp
        ja      .LBB1_1
.LBB1_3:
        add     esp, 12
        pop     esi
        pop     edi
        pop     ebx
        pop     ebp
        ret
.LBB1_4:
        push    offset .L__PRETTY_FUNCTION__.u2a_helper
        push    76
        push    offset .L.str.3
        push    offset .L.str.2
        call    __assert_fail

The most interesting part of the code is .LBB1_1: Here, ICX generates a slightly-different loop with two multiplications. This compiler seems to really want to optimize for speed, even when I tell it to optimize for space with -Os.

Finally, I tried this on MSVC 19.30.30706 for x86, with the command line

cl /utf-8 /std:c17 /W4 /external:anglebrackets /external:W0 /FAu /Os /arch:AVX512 /c my_output_helper.c

MSVC has some serious problems with this code. It does not seem to be able to deal with recursion at all. When optimizing for space with /Os, It does an okay job with the body of u2a_helper, compiling it to a nice div loop. However, it misses the tail-recursion optimization and generates a call u2a_helper rather than a jmp.

_TEXT   SEGMENT
_residue$ = -4                      ; size = 4
_n$ = 8                         ; size = 4
_current$ = 12                      ; size = 4
_lower_bound$ = 16                  ; size = 4
_u2a_helper PROC
; File C:\Users\Loreh\Documents\Src\my_output_helper.c
; Line 20
    push    ebp
    mov ebp, esp
    push    ecx
; Line 23
    mov eax, DWORD PTR _n$[ebp]
    xor edx, edx
    div DWORD PTR ?radix@?1??u2a_helper@@9@9
    mov DWORD PTR _residue$[ebp], eax
; Line 24
    mov eax, DWORD PTR _n$[ebp]
    xor edx, edx
    div DWORD PTR ?radix@?1??u2a_helper@@9@9
    add edx, 48                 ; 00000030H
    mov eax, DWORD PTR _current$[ebp]
    mov BYTE PTR [eax], dl
; Line 26
    cmp DWORD PTR _residue$[ebp], 0
    jbe SHORT $LN2@u2a_helper
; Line 27
    mov eax, DWORD PTR _current$[ebp]
    cmp eax, DWORD PTR _lower_bound$[ebp]
    ja  SHORT $LN4@u2a_helper
    push    27                  ; 0000001bH
    push    OFFSET $SG7109
    push    OFFSET $SG7110
    call    __wassert
    add esp, 12                 ; 0000000cH
$LN4@u2a_helper:
; Line 28
    push    DWORD PTR _lower_bound$[ebp]
    mov eax, DWORD PTR _current$[ebp]
    dec eax
    push    eax
    push    DWORD PTR _residue$[ebp]
    call    _u2a_helper
    add esp, 12                 ; 0000000cH
    jmp SHORT $LN1@u2a_helper
$LN2@u2a_helper:
; Line 31
    mov eax, DWORD PTR _current$[ebp]
$LN1@u2a_helper:
; Line 32
    leave
    ret 0
_u2a_helper ENDP
_TEXT   ENDS
END

When compiled with /O2 instead, to optimize for speed, it correctly converts the div loop into a multiplication loop and also becomes able to optimize the tail-recursion in u2a_helper. However, it is unable to optimize the state machine like the other three compilers all can, and therefore generates code that will cause a stack overflow on a long format string.

Therefore, with MSVC, you still need to write while loops, not tail calls.

But if You Really, Truly Want to Do it That Way

See this answer on StackOverflow.

Again, the major problems are that you’re going to have to duplicate the entire code as soon as you want even a little flexibility (like being able to use fatal_error to write formatted output to standard error instead of standard output), and that you’re using a fixed-sized buffer on the stack with no bounds checking. You do not want to optimize this code prematurely.

\$\endgroup\$
3
\$\begingroup\$

Minor

Avoid test code with its C implementation defined behavior (IDB) (assigning out of range value to int) and undefined behavior (UB) (printing - specifier/type mismatch). Consider that this code may run well on your machine, but if test code run on another, it is best to avoid IDB and UB to achieve compatibles results.

Use limits from <limits.h>

// int dm = 1u << 31;     // IDB
// printf("%u %u %u\n%llu %llu %llu\n", dm, dx, ux, lldm, lldx, llux); // UB

printf("%d %d %d\n%lld %lld %lld\n", 
    INT_MIN, INT_MAX, -1, 
    LLONG_MIN, LLONG_MAX, -1LL);
printf("%u %u %u\n%llu %llu %llu\n", 
    (unsigned)INT_MIN, (unsigned)INT_MAX, UINT_MAX, 
    (unsigned long long)LLONG_MIN, (unsigned long long)LLONG_MAX, ULLONG_MAX);

Or do the math correctly without IDB and print without UB.

int dm = -(1 << 30) - (1 << 30);
int dx = (int)((1u << 31) - 1);  // Cast optional: it quiets pedantic warnings
int ux = -1;
printf("%d %d %d\n", dm, dx, ux);
printf("%u %u %u\n", (unsigned) dm, (unsigned) dx, (unsigned) ux);
// Likewise for long long
\$\endgroup\$
2
  • \$\begingroup\$ That was my big mistake! The printf for 0s actually allocates stack for 4 ints, so the function is reading uninitialized stack for a long long, but that uninitialized data just happens to be 0. \$\endgroup\$
    – xiver77
    Feb 16 at 1:01
  • \$\begingroup\$ xiver77, True. printf("%d %u %lld %llu\n", 0, 0, 0, 0); should have been printf("%d %u %lld %llu\n", 0, 0, 0LL, 0LL);. ` \$\endgroup\$ Feb 16 at 13:22
1
\$\begingroup\$

ntdll.dll has _vsnprintf on Windows 2000 and later:

    global _printf
_printf:
BUFFER_SIZE equ 1024
    push ebp
    mov  ebp, esp
    push ebx
    sub  esp, BUFFER_SIZE+36
    lea  eax, [ebp+12]
    lea  ebx, [ebp-BUFFER_SIZE-8]
    push eax
    push dword [ebp+8]
    push BUFFER_SIZE
    push ebx
    call __vsnprintf
    lea  edx, [ebp-BUFFER_SIZE-12]
    mov  dword [esp], 0
    mov  dword [ebp-BUFFER_SIZE-28], eax
    push edx
    push eax
    push ebx
    push dword [stdout]
    call _WriteFile@20
    mov  eax, dword [ebp-BUFFER_SIZE-28]
    mov  ebx, dword [ebp-4]
    leave
    ret
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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