stdlib.h

4 files changed, 261 insertions, 10 deletions

diff --git a/05/main.c b/05/main.c
index 59d6ccd..d16347e 100644
--- a/05/main.c
+++ b/05/main.c
@@ -2,9 +2,32 @@
 #include <math.h>
 #include <stdio.h>
 #include <signal.h>
+#include <stdlib.h>
+
+
+int compar(const void *a, const void *b) {
+	int i = *(int *)a;
+	int j = *(int *)b;
+	if (i < j) return -1;
+	if (i > j) return 1;
+	return 0;
+}
 
 int main(int argc, char **argv) {
-	raise(SIGKILL);
+	ldiv_t l = ldiv(1000000000007, 5937448);
+	printf("%ld %ld\n",l.quot,l.rem);
+	int nums[10] = {8,34,1086,3872,-123,5873,3843,1762,INT_MAX,INT_MIN};
+	int i;
+	for (i = 0; i < 10; ++i) nums[i] = abs(nums[i]);
+	qsort(nums, 10, sizeof(int), compar);
+	for (i = 0; i < 10; ++i) printf("%d ", nums[i]);
+	printf("\n");
+	int search = 34;
+	int *p = bsearch(&search, nums, 10, sizeof(int), compar);
+	if (p)
+		printf("Found %d\n",*p);
+	else
+		printf("No match\n");
 	return 0;
 }
 
diff --git a/05/stdc_common.h b/05/stdc_common.h
index 10144a8..a3a8e7f 100644
--- a/05/stdc_common.h
+++ b/05/stdc_common.h
@@ -108,6 +108,23 @@ int getpid(void) {
 	return __syscall(39, 0, 0, 0, 0, 0, 0);
 }
 
+int fork(void) {
+	return __syscall(57, 0, 0, 0, 0, 0, 0);
+}
+
+int execve(const char *pathname, char *const argv[], char *const envp[]) {
+	return __syscall(59, pathname, argv, envp, 0, 0, 0);
+}
+
+
+#define _WEXITSTATUS(status)   (((status) & 0xff00) >> 8)
+#define _WIFEXITED(status) (__WTERMSIG(status) == 0)
+#define _WIFSIGNALED(status) \
+  (((signed char) (((status) & 0x7f) + 1) >> 1) > 0)
+int wait4(int pid, int *status, int options, struct rusage *rusage) {
+	return __syscall(61, pid, status, options, rusage, 0, 0);
+}
+
 #define SIGABRT 6
 #define SIGFPE 8
 #define SIGKILL 9
@@ -184,7 +201,13 @@ int munmap(void *addr, size_t length) {
 	return __syscall(11, addr, length, 0, 0, 0, 0);
 }
 
+#define MREMAP_MAYMOVE 1
+void *_mremap(void *addr, size_t old_size, size_t new_size, int flags) {
+	return __syscall(25, addr, old_size, new_size, flags, 0, 0);
+}
+
 void *malloc(size_t n) {
+	if (!n) return NULL;
 	void *memory;
 	size_t bytes = n + 16;
 	memory = mmap(0, bytes, PROT_READ|PROT_WRITE, MAP_ANONYMOUS|MAP_PRIVATE, -1, 0);
@@ -194,17 +217,12 @@ void *malloc(size_t n) {
 }
 
 void free(void *ptr) {
+	if (!ptr) return;
 	uint64_t *memory = (char *)ptr - 16;
 	uint64_t size = *memory;
 	munmap(memory, size);
 }
 
-void *calloc(size_t nmemb, size_t size) {
-	if (nmemb > 0xffffffffffffffff / size)
-		return NULL;
-	return malloc(nmemb * size);
-}
-
 
 size_t strlen(char *s) {
 	char *t = s;
@@ -212,6 +230,13 @@ size_t strlen(char *s) {
 	return t - s;
 }
 
+void *memcpy(void *s1, const void *s2, size_t n) {
+	char *p = s1, *end = p + n, *q = s2;
+	while (p < end)
+		*p++ = *q++;
+	return s1;
+}
+
 int isspace(int c) {
 	return c == ' ' || c == '\f' || c == '\n' || c == '\r' || c == '\t' || c == '\v';
 }
@@ -430,10 +455,30 @@ double strtod(const char *nptr, char **endptr) {
 	return sum * sign;
 }
 
+char *strerror(int errnum) {
+	switch (errnum) {
+	case ERANGE: return "Range error";
+	case EDOM: return "Domain error";
+	case EIO: return "I/O error";
+	}
+	return "Other error";
+}
+
+typedef void (*_ExitHandler)(void);
+_ExitHandler _exit_handlers[33];
+int _n_exit_handlers;
+
+void exit(int status) {
+	int i;
+	for (i = _n_exit_handlers - 1; i >= 0; --i)
+		_exit_handlers[i]();
+	_Exit(status);
+}
 
 int main();
 
 static char **_envp;
+static uint64_t _rand_seed;
 
 int _main(int argc, char **argv) {
 	int i;
@@ -445,6 +490,12 @@ int _main(int argc, char **argv) {
 	stdout = &_stdout;
 	stderr = &_stderr;
 	
+	/*
+	"If rand is called before any calls to srand have been made,
+	the same sequence shall be generated as when srand is first
+	called with a seed value of 1." C89 § 4.10.2.2 
+	*/
+	_rand_seed = 1;
 	// initialize powers of 10
 	_powers_of_10 = _powers_of_10_dat + _NPOW10;
 	for (i = 0; i < _NPOW10; ++i) {
@@ -464,7 +515,7 @@ int _main(int argc, char **argv) {
 		p.exponent -= 1;
 	}
 	
-	return main(argc, argv);
+	exit(main(argc, argv));
 }
 
 
diff --git a/05/stdio.h b/05/stdio.h
index 3b53d2b..e5a04cc 100644
--- a/05/stdio.h
+++ b/05/stdio.h
@@ -1683,7 +1683,8 @@ int _fopen_flags_from_mode(const char *mode) {
 }
 
 FILE *_FILE_from_fd(int fd) {
-	FILE *fp = calloc(1, sizeof(FILE));
+	FILE *fp = malloc(sizeof(FILE));
+	// NB: our malloc implementation returns zeroed memory
 	fp->fd = fd;
 	return fp;
 }
@@ -2274,7 +2275,9 @@ int scanf(const char *format, ...) {
 }
 
 
-void perror(const char *s); // @TODO
+void perror(const char *s) {
+	printf("%s: %s\n", s, strerror(errno));
+}
 
 #undef STB_SPRINTF_MIN
 
diff --git a/05/stdlib.h b/05/stdlib.h
index e98156b..c2f83eb 100644
--- a/05/stdlib.h
+++ b/05/stdlib.h
@@ -3,6 +3,21 @@
 
 #include <stdc_common.h>
 
+#define EXIT_FAILURE (-1)
+#define EXIT_SUCCESS 0
+#define RAND_MAX 2147483647
+// @NONSTANDARD: we don't define MB_CUR_MAX or any of the mbtowc functions
+
+typedef struct {
+	int quot;
+	int rem;
+} div_t;
+
+typedef struct {
+	long quot;
+	long rem;
+} ldiv_t;
+
 char *getenv(const char *name) {
 	int i, j;
 	for (i = 0; _envp[i]; ++i) {
@@ -16,4 +31,163 @@ char *getenv(const char *name) {
 	return NULL;
 }
 
+double atof(const char *nptr) {
+	return strtod(nptr, NULL);
+}
+
+int atoi(const char *nptr) {
+	return _clamp_long_to_int(strtol(nptr, NULL, 10));
+}
+
+long atol(const char *nptr) {
+	return strtol(nptr, NULL, 10);
+}
+
+int rand(void) {
+	// https://en.wikipedia.org/wiki/Linear_congruential_generator
+	// we're using musl/newlib's constants
+	_rand_seed = 6364136223846793005 * _rand_seed + 1;
+	return _rand_seed >> 33;
+}
+
+void srand(unsigned seed) {
+	_rand_seed = seed;
+}
+
+void *calloc(size_t nmemb, size_t size) {
+	if (nmemb > 0xffffffffffffffff / size)
+		return NULL;
+	// NB: our malloc implementation returns zeroed memory
+	return malloc(nmemb * size);
+}
+
+void *realloc(void *ptr, size_t size) {
+	if (!ptr) return malloc(size);
+	if (!size) {
+		free(ptr);
+		return NULL;
+	}
+	uint64_t *memory = (char *)ptr - 16;
+	uint64_t old_size = *memory;
+	uint64_t *new_memory = _mremap(memory, old_size, size, MREMAP_MAYMOVE);
+	if ((uint64_t)new_memory > 0xffffffffffff0000) return NULL;
+	*new_memory = size;
+	return (char *)new_memory + 16;
+}
+
+
+int atexit(void (*func)(void)) {
+	if (_n_exit_handlers >= 32) return -1;
+	_exit_handlers[_n_exit_handlers++] = func;
+	return 0;
+}
+
+int system(const char *string) {
+	if (!string) return 1;
+	
+	int pid = fork();
+	if (pid < 0) {
+		return -1;
+	} else if (pid == 0) {
+		// child
+		char *argv[] = {
+			"/bin/sh",
+			"-c",
+			0,
+			0
+		};
+		argv[2] = string;
+		execve("/bin/sh", argv, _envp);
+		// on success, execve does not return.
+		_Exit(-1);
+	} else {
+		// parent
+		int status = 0;
+		int ret = wait4(pid, &status, 0, NULL);
+		if (ret != pid) return -1;
+		if (_WIFSIGNALED(status)) return -1;
+		return _WEXITSTATUS(status);
+	}
+	
+}
+
+void *bsearch(const void *key, const void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)) {
+	size_t lo = 0;
+	size_t hi = nmemb;
+	while (lo < hi) {
+		size_t mid = (lo + hi) >> 1;
+		void *elem = (char *)base + mid * size;
+		int cmp = compar(key, elem);
+		if (cmp < 0) {
+			// key < elem
+			hi = mid;
+		} else if (cmp) {
+			// key > elem
+			lo = mid + 1;
+		} else {
+			return elem;
+		}
+	}
+	return NULL;
+}
+
+void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)) {
+	// quicksort
+	if (nmemb < 2) return;
+	
+	void *temp = malloc(size);
+	void *mid = (char *)base + ((nmemb >> 1) * size); // choose middle element to speed up sorting an already-sorted array
+	size_t pivot_index = 0, i;
+	for (i = 0; i < nmemb; ++i) {
+		void *elem = (char *)base + i * size;
+		if (compar(elem, mid) < 0)
+			++pivot_index;
+	}
+	void *pivot = (char *)base + pivot_index * size;
+	memcpy(temp, pivot, size);
+	memcpy(pivot, mid, size);
+	memcpy(mid, temp, size);
+	
+	char *l, *r = (char *)base + (nmemb-1) * size;
+	for (l = base; l < r;) {
+		if (compar(l, pivot) > 0) {
+			// swap l and r
+			memcpy(temp, l, size);
+			memcpy(l, r, size);
+			memcpy(r, temp, size);
+			r -= size;
+		} else {
+			// l is already in the right place
+			l += size;
+		}
+	}
+	
+	qsort(base, pivot_index, size, compar);
+	qsort((char *)pivot + size, nmemb - 1 - pivot_index, size, compar);
+	
+	free(temp);
+}
+
+int abs(int x) {
+	return x >= 0 ? x : -x;
+}
+
+long labs(long x) {
+	return x >= 0 ? x : -x;
+}
+
+div_t div(int numer, int denom) {
+	div_t d;
+	d.quot = numer / denom;
+	d.rem = numer % denom;
+	return d;
+}
+
+ldiv_t ldiv(long numer, long denom) {
+	ldiv_t d;
+	d.quot = numer / denom;
+	d.rem = numer % denom;
+	return d;
+}
+
 #endif // _STDLIB_H