libc

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

Embedded Artistry libc

If you've been following along with recent posts, you've likely seen many from the Embedded Artistry libc bringup series. I've been documenting and publishing the process of putting together my embedded libc.

I've decided to make my libc source a standalone repository. You can build the library and include it in the link step, or you can import the source code directly into your project.

One thing to note is that you will need the Embedded Artistry libmalloc library to find the malloc definitions. If you prefer to use a single malloc definition directly, you will need to add malloc source code into stdlib.

You can find the libc repository on Github.. libc is also listed on the Embedded Artistry Github organization page.

libc: stdlib, pt. 1

The C standard library is a widely used resource, as it provides the base functionality for many more advanced features. The C standard library provides functionality like:

  • string-to-number conversion
  • math features like division and absolute value
  • memory allocation (malloc, calloc, realloc)
  • random number generation
  • abort/exit

However, the usefulness of the standard library doesn't stop at C. Many standard library features are also needed to bringup libc++, which we will be tackling in the future.

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.

Note: For the remainder of the article, I will be referring to the standard library as stdlib.

Implemented Functions

I implemented the following functions in my first-pass of stdlib. These provide essential building blocks for our systems.

  • abs
  • atoi
  • atol
  • atoll
  • bsearch
  • calloc
  • div
  • free
  • labs
  • ldiv
  • llabs
  • lldiv
  • malloc
  • rand (host-only, non-portable)
  • realloc
  • reallocf
  • srand (host-only, non-portable)
  • strtod
  • strtol
  • strtoll
  • strtoul
  • strtoull

Functions Pending Implementation

The functions listed below currently remain unimplemented and will be tackled in part 2. Note that even with the pending functions stdlib will not be completed. I am only targeting a reduced subset of stdlib that is useful for embedded systems.

  • Floating point functions
    • atof
    • strtof
    • strtold
  • imax* functions
  • Exit/Abort functionality
    • abort
    • atexit
    • at_quick_exit
    • exit
    • _Exit
    • quick_exit
  • qsort

Custom Function Implementations

Many of the stdlib functions are directly ported from Apple open source projects. There are a small subset of functions that I did not pilfer:

  • atoi
  • atol
  • atoll
  • realloc
  • reallocf
  • calloc

Let's see what each of these implementations looks like.

atoi

atoi is a relatively simple function. This version assumes all numbers are in base 10, and builds upon the ctype functions we implemented a few weeks ago.

int atoi(const char *str)
{
    bool neg = false;
    int val = 0;

    switch(*str)
    {
        case '-':
            neg = true;
            //intentional fallthrough to advance str
        case '+':
            str++;
    }

    while (isdigit(*str)) {
        val = (10 * val) + (*str++ - '0');
    }

    return (neg ? -val : val);
}

atol

atol follows the same pattern as atoi, but uses different values to account for the different types.

long atol(const char *str)
{
    long val = 0;
    bool neg = false;

    while(isspace(*str))
    {
        str++;
    }

    switch (*str) {
        case '-':
            neg = true;
        //intentional fallthrough
        case '+':
            str++;
    }

    while (isdigit(*str))
    {
        val = (10 * val) + (*str++ - '0');
    }

    return neg ? -val : val;
}

atoll

atoll is the last in the set, and like its predecessors operates in the same way. C++ function overloading and templating sure starts to look nice, as we could skip these duplicate implementations.

long long atoll(const char *str)
{
    long long val=0;
    bool neg = false;

    while(isspace(*str))
    {
        str++;
    }

    switch (*str) {
        case '-':
            neg = true;
            //Intentional fallthrough
        case '+':
            str++;
    }

    while (isdigit(*str))
    {
        val = (10 * val) + (*str++ - '0');
    }
    return neg ? -val : val;
}

calloc

/*
 * This is sqrt(SIZE_MAX+1), as s1*s2 <= SIZE_MAX
 * if both s1 < MUL_NO_OVERFLOW and s2 < MUL_NO_OVERFLOW
 */
#define MUL_NO_OVERFLOW (1UL << (sizeof(size_t) * 4))

void *calloc(size_t num, size_t size)
{
    /* num * size unsigned integer wrapping check */
    if ((num >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
        num > 0 && SIZE_MAX / num < size)
    {
        return NULL;
    }

    size_t total_size = num * size;
    void *ptr = malloc(total_size);

    if (ptr)
    {
        memset(ptr, 0, total_size);
    }

    return ptr;
}

realloc

I implemented my own realloc because I have an opinion on how I want to handle the realloc(ptr,0) special case: I want to return NULL. The original data will not be freed.

void *realloc(void *ptr, size_t size)
{
    void * new_data = NULL;

    if(size)
    {
        if (!ptr)
        {
            return malloc(size);
        }

        new_data = malloc(size);
        if (new_data)
        {
            memcpy(new_data, ptr, size); //TODO: unsafe copy...
            free(ptr); //we always move the data. free.
        }
    }

    return new_data;
}

reallocf

reallocf is a FreeBSD extension to realloc that I like: if realloc fails, the original data pointer is freed. This helps account for option #2 when calling realloc(ptr,0), since realloc uses option #1.

Implementation is simple:

void *reallocf(void *ptr, size_t size)
{
    void *p = realloc(ptr, size);

    if ((p == NULL) && (ptr != NULL))
    {
        free(ptr);
    }

    return p;
}

Note that I do not hand the BSD case of realloc(ptr,0) freeing the original data pointer.

Ported Functions

I am a staunch believer in not re-inventing the wheel unless absolutely necessary. Many of the stdlib function implementations were ported from various Apple Open Source libraries. I've provided links to each function's original source and noted any modifications made.

Apple Open Source Libc:

I removed errno support from strtoull, as I have not ported the errno functionality.

Apple Open Source XNU

Apple Open Source TCL

I removed errno support, as I have not ported the errno functionality.

Apple Open Source Lukemftp

I removed errno support, as I have not ported the errno functionality.

Current stdlib.h Header

Here's the current stdlib.h header contents, based on the first pass functions:

#ifndef __STDLIB_H_
#define __STDLIB_H_

#include <stddef.h>

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

typedef struct {
    int quot;
    int rem;
} div_t;

typedef struct {
    long quot;
    long rem;
} ldiv_t;

typedef struct {
    long long quot;
    long long rem;
} lldiv_t;

#define EXIT_FAILURE 1
#define EXIT_SUCCESS 0
#define RAND_MAX (0x7fffffff)

int atoi (const char *);
long atol (const char *);
long long atoll (const char *);
double atof (const char *);

double strtod (const char *__restrict, char **__restrict);
long strtol (const char *__restrict, char **__restrict, int);
unsigned long strtoul (const char *__restrict, char **__restrict, int);
long long strtoll (const char *__restrict, char **__restrict, int);
unsigned long long strtoull (const char *__restrict, char **__restrict, int);

int abs (int);
long labs (long);
long long llabs (long long);

div_t div (int, int);
ldiv_t ldiv (long, long);
lldiv_t lldiv (long long, long long);

int rand (void);
void srand (unsigned);

void *bsearch (const void *, const void *, size_t, size_t, int (*)(const void *, const void *));

void * malloc(size_t size);
void free(void * ptr);
void * calloc(size_t num, size_t size);
void *realloc(void *ptr, size_t size);
void *reallocf(void *ptr, size_t size);

#ifdef __cplusplus
}
#endif //__cplusplus

#endif // __STDLIB_H_

Putting it All Together

You can find the current stdlib implementation in the embedded-resources Github repository.

Further Reading: