Implementing libc: stdlib, pt. 2

Earlier this year I was focusing on bringing up an embedded framework. I've been distracted with client work, but am finally resuming framework development. The first stage in that journey is finishing off the Embedded Artistry libc so I can begin work on my memory allocation library and the C++ libraries.

Early warning: If you're unfamiliar with the the standard library functions, I recommend reading this "Guide to C stdlib functions". I will not be describing what each function does.

This article continues from the first stdlib bringup article and cites the primary source and any modifications made for these stdlib functions:

  • atof
  • strtof
  • heapsort
  • qsort
  • qsort_r (reentrant)
  • imaxabs
  • imaxdiv
  • rand
  • rand_r (reentrant)
  • srand

I also implemented the following "support" functions:

  • fls
  • flsl
  • flsll

I have decided to leave strtold (string-to-long-double) unimplemented at this time. The odds that we will need to use it on embedded systems seems exceedingly low, and I will tackle it whenever the time comes. The following functions will be covered in a future article:

  • abort
  • atexit
  • at_quick_exit
  • exit
  • _Exit
  • quick_exit

Header Changes

A new strings.h header has been added due to the fls function family, and stdlib.h has been updated to reflect the new functions.

stdlib.h Updates

The stdlib.h header has been updated to reflect the new features.

The header now include stdint.h due to the imax* function prototypes:

#include <stdint.h>

The imaxdiv_t type was defined to support the imax* functions:

typedef struct
{
    intmax_t quot;
    intmax_t rem;
} imaxdiv_t;

The following function prototypes were added:

float strtof(const char* __restrict, char** __restrict);
intmax_t imaxabs(intmax_t j);
imaxdiv_t imaxdiv(intmax_t numer, intmax_t denom);
int rand_r(unsigned int* ctx);
int rand(void);
void srand(unsigned seed);
int heapsort(void* vbase, size_t nmemb, size_t size, int (*compar)(const void*, const void*));
void qsort_r(void* a, size_t n, size_t es, void* thunk,
             int (*cmp)(void*, const void*, const void*));
void qsort(void* a, size_t n, size_t es, int (*compar)(const void*, const void*));

strings.h

The POSIX header strings.h has been added in a very basic way. The fls family of functions is defined here.

My strings.h implementation:

#ifndef __STRINGS_H_
#define __STRINGS_H_

#include <stddef.h>
#include <stdint.h>

#ifdef __cplusplus
extern "C" {
#endif //__cplusplus

int fls(int mask);
int flsl(long mask);
int flsll(long long mask);

#ifdef __cplusplus
}
#endif //__cplusplus

#endif // __STRINGS_H_

atof

I imported the Apple Open Source atof, which simply serves as a strtod wrapper:

#include <stdlib.h>

double atof(const char* ascii)
{
    return (strtod(ascii, NULL));
}

strtof

I imported the old Sun Microsystems implementation of strtof rather than the more complicated gtoa library.

Since the function is long, I will refer you to the source code. I have converted to the standard type names (TRUE becomes true, CONST becomes const) and removed dead code. The logic is still the same.

imaxabs

I've imported the FreeBSD implementation of imaxabs:

#include <stdlib.h>

intmax_t imaxabs(intmax_t j)
{
    return (j < 0 ? -j : j);
}

imaxdiv

I've imported the FreeBSD implementation of imaxdiv:

#include <stdlib.h>

/* See comments in div.c for implementation details. */
imaxdiv_t imaxdiv(intmax_t numer, intmax_t denom)
{
    imaxdiv_t retval;

    retval.quot = numer / denom;
    retval.rem = numer % denom;
    if(numer >= 0 && retval.rem < 0)
    {
        retval.quot++;
        retval.rem -= denom;
    }
    return (retval);
}

rand and company

I used the Apple Open Source rand.c file as a reference for my basic rand implementation.

Since we're targeting an embedded system, I've cleaned up the code to remove the tests and the random device references. I also converted the rand, srand, and rand_r implementations to be weakly linked, so that we can override these functions on our target architectures.

The resulting rand.c implementation:

#include <stdlib.h>

static unsigned long next = 1;
static int do_rand(unsigned long* ctx)
{
#ifdef USE_WEAK_SEEDING
    /*
     * Historic implementation compatibility.
     * The random sequences do not vary much with the seed,
     * even with overflowing.
     */
    return ((*ctx = *ctx * 1103515245 + 12345) % ((unsigned long)RAND_MAX + 1));
#else /* !USE_WEAK_SEEDING */
    /*
     * Compute x = (7^5 * x) mod (2^31 - 1)
     * without overflowing 31 bits:
     *      (2^31 - 1) = 127773 * (7^5) + 2836
     * From "Random number generators: good ones are hard to find",
     * Park and Miller, Communications of the ACM, vol. 31, no. 10,
     * October 1988, p. 1195.
     */
    long hi, lo, x;

    /* Can't be initialized with 0, so use another value. */
    if(*ctx == 0)
        *ctx = 123459876;
    hi = *ctx / 127773;
    lo = *ctx % 127773;
    x = 16807 * lo - 2836 * hi;
    if(x < 0)
        x += 0x7fffffff;
    return ((*ctx = x) % ((unsigned long)RAND_MAX + 1));
#endif /* !USE_WEAK_SEEDING */
}

__attribute__((weak)) int rand_r(unsigned int* ctx)
{
    unsigned long val = (unsigned long)*ctx;
    int r = do_rand(&val);

    *ctx = (unsigned int)val;
    return (r);
}

__attribute__((weak)) int rand()
{
    return (do_rand(&next));
}

__attribute__((weak)) void srand(unsigned seed)
{
    next = seed;
}

fls Family

The fls function family was imported from Apple's Open Source libplatform. I separated the functions into three files rather than Apple's single source file.

Each implementation will prefer the builtin function version if it exists.

fls

#include <strings.h>

/*
 * Find Last Set bit
 */
int fls(int mask)
{
#if __has_builtin(__builtin_fls)
    return __builtin_fls(mask);
#elif __has_builtin(__builtin_clz)
    if(mask == 0)
        return (0);

    return (sizeof(mask) << 3) - __builtin_clz(mask);
#else
    int bit;

    if(mask == 0)
        return (0);
    for(bit = 1; mask != 1; bit++)
        mask = (unsigned)mask >> 1;
    return (bit);
#endif
}

flsl

#include <strings.h>

/*
 * Find Last Set bit
 */
int flsl(long mask)
{
#if __has_builtin(__builtin_flsl)
    return __builtin_flsl(mask);
#elif __has_builtin(__builtin_clzl)
    if(mask == 0)
        return (0);

    return (sizeof(mask) << 3) - __builtin_clzl(mask);
#else
    int bit;

    if(mask == 0)
        return (0);
    for(bit = 1; mask != 1; bit++)
        mask = (unsigned long)mask >> 1;
    return (bit);
#endif
}

flsll

#include <strings.h>

/*
 * Find Last Set bit
 */
int flsll(long long mask)
{
#if __has_builtin(__builtin_flsll)
    return __builtin_flsll(mask);
#elif __has_builtin(__builtin_clzll)
    if(mask == 0)
        return (0);

    return (sizeof(mask) << 3) - __builtin_clzll(mask);
#else
    int bit;

    if(mask == 0)
        return (0);
    for(bit = 1; mask != 1; bit++)
        mask = (unsigned long long)mask >> 1;
    return (bit);
#endif
}

Sorting Functions

heapsort

I imported the Apple Open Source heapsort implementation. Since the file is quite large, I will refer you directly to the source code.

qsort

I imported the Apple Open Source qsort implementation. I have kept most of the logic in place, but have removed all I_AM_QSORT_B definitions from the file. I left I_AM_QSORT_R defined so that I could implement the qsort_r function in a simple way.

Since the file is quite large, I will refer you directly to the source code.

qsort_r

I have kept the qsort_r.c strategy used in the Apple Open Source implementation:

/*
 * This file is in the public domain.  Originally written by Garrett
 * A. Wollman.
 *
 * $FreeBSD: src/lib/libc/stdlib/qsort_r.c,v 1.1 2002/09/10 02:04:49 wollman Exp $
 */
#define I_AM_QSORT_R
#include "qsort.c"

Putting it All Together

I want to showcase where I find open source function implementations and how I modify them to fit my purposes. I don't believe in re-inventing the wheel, so I am trying to reuse as much code as possible. In many cases in my career, I've seen these functions re-implemented rather than referencing quality implementations that are available and widely used.

The Embedded Artistry libc implementation is nearing completion. The current suite of functions is more than capable of meeting the needs of embedded systems developers. In future articles we will be covering the exit/abort functionality and unit testing support.

Further Reading