/*
pcboot - bootable PC demo/game kernel
-Copyright (C) 2018 John Tsiombikas <nuclear@member.fsf.org>
+Copyright (C) 2018-2019 John Tsiombikas <nuclear@member.fsf.org>
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
along with this program. If not, see <https://www.gnu.org/licenses/>.
*/
#include <stdlib.h>
+#include <string.h>
#include <ctype.h>
+#include <limits.h>
+#include <assert.h>
+#include <alloca.h>
int atoi(const char *str)
{
{
long acc = 0;
int sign = 1;
+ int valid = 0;
+ const char *start = str;
while(isspace(*str)) str++;
}
while(*str) {
- long val;
+ long val = LONG_MAX;
char c = tolower(*str);
if(isdigit(c)) {
val = *str - '0';
- } else if(c >= 'a' || c <= 'f') {
+ } else if(c >= 'a' && c <= 'f') {
val = 10 + c - 'a';
+ } else {
+ break;
}
if(val >= base) {
break;
}
+ valid = 1;
acc = acc * base + val;
str++;
}
if(endp) {
- *endp = (char*)str;
+ *endp = (char*)(valid ? str : start);
}
return sign > 0 ? acc : -acc;
*buf = 0;
}
+double atof(const char *str)
+{
+ return strtod(str, 0);
+}
+
+
+double strtod(const char *str, char **endp)
+{
+ char *ep;
+ const char *start = str;
+ int valid = 0;
+ long ival = 0, dval = 0;
+ int ddig = 0;
+ double res;
+
+ /* integer part */
+ ival = strtol(str, &ep, 10);
+ if(ep == str && *str != '.') {
+ if(endp) *endp = (char*)str;
+ return 0.0;
+ }
+ if(ep != str) valid = 1;
+ str = *ep == '.' ? ep + 1 : ep;
+ if(!isdigit(*str)) {
+ goto done;
+ }
+ valid = 1;
+
+ dval = strtol(str, &ep, 10);
+ assert(dval >= 0);
+ ddig = ep - str;
+ str = ep;
+
+done:
+ if(*endp) {
+ *endp = (char*)(valid ? str : start);
+ }
+
+ res = (double)ival;
+ if(ddig) {
+ double d = (double)dval;
+ while(ddig-- > 0) {
+ d /= 10.0;
+ }
+ res += d;
+ }
+ return res;
+}
+
+int atexit(void (*func)(void))
+{
+ /* there's no concept of exiting at the moment, so this does nothing */
+ return 0;
+}
+
+void abort(void)
+{
+ panic("Aborted\n");
+}
+
+#define QSORT_THRESHOLD 4
+#define ITEM(idx) ((char*)arr + (idx) * itemsz)
+
+#define SWAP(p, q) \
+ do { \
+ int nn = itemsz; \
+ char *pp = (p); \
+ char *qq = (q); \
+ do { \
+ char tmp = *pp; \
+ *pp++ = *qq; \
+ *qq++ = tmp; \
+ } while(--nn > 0); \
+ } while(0)
+
+static void ins_sort(void *arr, size_t count, size_t itemsz, int (*cmp)(const void*, const void*))
+{
+ int i;
+ char *it, *a, *b;
+
+ if(count <= 1) return;
+
+ it = (char*)arr + itemsz;
+ for(i=1; i<count; i++) {
+ a = it;
+ it += itemsz;
+ while(a > (char*)arr && cmp(a, (b = a - itemsz)) < 0) {
+ SWAP(a, b);
+ a -= itemsz;
+ }
+ }
+}
+
+void qsort(void *arr, size_t count, size_t itemsz, int (*cmp)(const void*, const void*))
+{
+ char *ma, *mb, *mc, *left, *right;
+ size_t sepidx, nleft, nright;
+
+ if(count <= 1) return;
+
+ if(count < QSORT_THRESHOLD) {
+ ins_sort(arr, count, itemsz, cmp);
+ return;
+ }
+
+ ma = arr;
+ mb = ITEM(count / 2);
+ mc = ITEM(count - 1);
+ if(cmp(ma, mb) < 0) SWAP(ma, mb);
+ if(cmp(mc, ma) < 0) SWAP(mc, ma);
+
+ left = ma + itemsz;
+ right = mc - itemsz;
+ for(;;) {
+ while(cmp(left, ma) < 0) left += itemsz;
+ while(cmp(ma, right) < 0) right -= itemsz;
+ if(left >= right) break;
+ SWAP(left, right);
+ }
+ SWAP(ma, right);
+ sepidx = (right - (char*)arr) / itemsz;
+ nleft = sepidx;
+ nright = count - nleft - 1;
+
+ qsort(ma, nleft, itemsz, cmp);
+ qsort(right + itemsz, nright, itemsz, cmp);
+}