git.mutantstargoat.com Git - bootcensus/blob - src/libc/stdlib.c

   1 /*
   2 pcboot - bootable PC demo/game kernel
   3 Copyright (C) 2018-2019  John Tsiombikas <nuclear@member.fsf.org>
   4
   5 This program is free software: you can redistribute it and/or modify
   6 it under the terms of the GNU General Public License as published by
   7 the Free Software Foundation, either version 3 of the License, or
   8 (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY, without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License
  16 along with this program.  If not, see <https://www.gnu.org/licenses/>.
  17 */
  18 #include <stdlib.h>
  19 #include <string.h>
  20 #include <ctype.h>
  21 #include <limits.h>
  22 #include <assert.h>
  23 #include <alloca.h>
  24
  25 int atoi(const char *str)
  26 {
  27         return strtol(str, 0, 10);
  28 }
  29
  30 long atol(const char *str)
  31 {
  32         return strtol(str, 0, 10);
  33 }
  34
  35 long strtol(const char *str, char **endp, int base)
  36 {
  37         long acc = 0;
  38         int sign = 1;
  39         int valid = 0;
  40         const char *start = str;
  41
  42         while(isspace(*str)) str++;
  43
  44         if(base == 0) {
  45                 if(str[0] == '0') {
  46                         if(str[1] == 'x' || str[1] == 'X') {
  47                                 base = 16;
  48                         } else {
  49                                 base = 8;
  50                         }
  51                 } else {
  52                         base = 10;
  53                 }
  54         }
  55
  56         if(*str == '+') {
  57                 str++;
  58         } else if(*str == '-') {
  59                 sign = -1;
  60                 str++;
  61         }
  62
  63         while(*str) {
  64                 long val = LONG_MAX;
  65                 char c = tolower(*str);
  66
  67                 if(isdigit(c)) {
  68                         val = *str - '0';
  69                 } else if(c >= 'a' && c <= 'f') {
  70                         val = 10 + c - 'a';
  71                 } else {
  72                         break;
  73                 }
  74                 if(val >= base) {
  75                         break;
  76                 }
  77                 valid = 1;
  78
  79                 acc = acc * base + val;
  80                 str++;
  81         }
  82
  83         if(endp) {
  84                 *endp = (char*)(valid ? str : start);
  85         }
  86
  87         return sign > 0 ? acc : -acc;
  88 }
  89
  90 void itoa(int val, char *buf, int base)
  91 {
  92         static char rbuf[16];
  93         char *ptr = rbuf;
  94         int neg = 0;
  95
  96         if(val < 0) {
  97                 neg = 1;
  98                 val = -val;
  99         }
 100
 101         if(val == 0) {
 102                 *ptr++ = '0';
 103         }
 104
 105         while(val) {
 106                 int digit = val % base;
 107                 *ptr++ = digit < 10 ? (digit + '0') : (digit - 10 + 'a');
 108                 val /= base;
 109         }
 110
 111         if(neg) {
 112                 *ptr++ = '-';
 113         }
 114
 115         ptr--;
 116
 117         while(ptr >= rbuf) {
 118                 *buf++ = *ptr--;
 119         }
 120         *buf = 0;
 121 }
 122
 123 void utoa(unsigned int val, char *buf, int base)
 124 {
 125         static char rbuf[16];
 126         char *ptr = rbuf;
 127
 128         if(val == 0) {
 129                 *ptr++ = '0';
 130         }
 131
 132         while(val) {
 133                 unsigned int digit = val % base;
 134                 *ptr++ = digit < 10 ? (digit + '0') : (digit - 10 + 'a');
 135                 val /= base;
 136         }
 137
 138         ptr--;
 139
 140         while(ptr >= rbuf) {
 141                 *buf++ = *ptr--;
 142         }
 143         *buf = 0;
 144 }
 145
 146 double atof(const char *str)
 147 {
 148         return strtod(str, 0);
 149 }
 150
 151
 152 double strtod(const char *str, char **endp)
 153 {
 154         char *ep;
 155         const char *start = str;
 156         int valid = 0;
 157         long ival = 0, dval = 0;
 158         int ddig = 0;
 159         double res;
 160
 161         /* integer part */
 162         ival = strtol(str, &ep, 10);
 163         if(ep == str && *str != '.') {
 164                 if(endp) *endp = (char*)str;
 165                 return 0.0;
 166         }
 167         if(ep != str) valid = 1;
 168         str = *ep == '.' ? ep + 1 : ep;
 169         if(!isdigit(*str)) {
 170                 goto done;
 171         }
 172         valid = 1;
 173
 174         dval = strtol(str, &ep, 10);
 175         assert(dval >= 0);
 176         ddig = ep - str;
 177         str = ep;
 178
 179 done:
 180         if(*endp) {
 181                 *endp = (char*)(valid ? str : start);
 182         }
 183
 184         res = (double)ival;
 185         if(ddig) {
 186                 double d = (double)dval;
 187                 while(ddig-- > 0) {
 188                         d /= 10.0;
 189                 }
 190                 res += d;
 191         }
 192         return res;
 193 }
 194
 195 int atexit(void (*func)(void))
 196 {
 197         /* there's no concept of exiting at the moment, so this does nothing */
 198         return 0;
 199 }
 200
 201 void abort(void)
 202 {
 203         panic("Aborted\n");
 204 }
 205
 206 #define QSORT_THRESHOLD 4
 207 #define ITEM(idx)       ((char*)arr + (idx) * itemsz)
 208
 209 #define SWAP(p, q) \
 210         do { \
 211                 int nn = itemsz; \
 212                 char *pp = (p); \
 213                 char *qq = (q); \
 214                 do { \
 215                         char tmp = *pp; \
 216                         *pp++ = *qq; \
 217                         *qq++ = tmp; \
 218                 } while(--nn > 0); \
 219         } while(0)
 220
 221 static void ins_sort(void *arr, size_t count, size_t itemsz, int (*cmp)(const void*, const void*))
 222 {
 223         int i;
 224         char *it, *a, *b;
 225
 226         if(count <= 1) return;
 227
 228         it = (char*)arr + itemsz;
 229         for(i=1; i<count; i++) {
 230                 a = it;
 231                 it += itemsz;
 232                 while(a > (char*)arr && cmp(a, (b = a - itemsz)) < 0) {
 233                         SWAP(a, b);
 234                         a -= itemsz;
 235                 }
 236         }
 237 }
 238
 239 void qsort(void *arr, size_t count, size_t itemsz, int (*cmp)(const void*, const void*))
 240 {
 241         char *ma, *mb, *mc, *left, *right;
 242         size_t sepidx, nleft, nright;
 243
 244         if(count <= 1) return;
 245
 246         if(count < QSORT_THRESHOLD) {
 247                 ins_sort(arr, count, itemsz, cmp);
 248                 return;
 249         }
 250
 251         ma = arr;
 252         mb = ITEM(count / 2);
 253         mc = ITEM(count - 1);
 254         if(cmp(ma, mb) < 0) SWAP(ma, mb);
 255         if(cmp(mc, ma) < 0) SWAP(mc, ma);
 256
 257         left = ma + itemsz;
 258         right = mc - itemsz;
 259         for(;;) {
 260                 while(cmp(left, ma) < 0) left += itemsz;
 261                 while(cmp(ma, right) < 0) right -= itemsz;
 262                 if(left >= right) break;
 263                 SWAP(left, right);
 264         }
 265         SWAP(ma, right);
 266         sepidx = (right - (char*)arr) / itemsz;
 267         nleft = sepidx;
 268         nright = count - nleft - 1;
 269
 270         qsort(ma, nleft, itemsz, cmp);
 271         qsort(right + itemsz, nright, itemsz, cmp);
 272 }