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.

```
#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.