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: