1#include <limits.h>
2#include <mem/alloc.h>
3#include <stdarg.h>
4#include <stdbool.h>
5#include <stddef.h>
6#include <stdint.h>
7#include <string.h>
8
9#undef memset
10#undef memcpy
11#undef memmove
12#undef memcmp
13
14void *memcpy(void *dest, const void *src, size_t n) {
15 return __memcpy_inline(dest, src, n);
16}
17
18void *memset(void *s, int c, size_t n) {
19 return __memset_inline(s, c, n);
20}
21
22void *memmove(void *dest, const void *src, size_t n) {
23 return __memmove_inline(dest, src, n);
24}
25
26int memcmp(const void *s1, const void *s2, size_t n) {
27 return __memcmp_inline(s1, s2, n);
28}
29size_t strlen(const char *str) {
30 size_t length = 0;
31
32 while (str[length] != '\0') {
33 length++;
34 }
35
36 return length;
37}
38
39char *strcpy(char *dest, const char *src) {
40 char *original_dest = dest;
41 while ((*dest++ = *src++))
42 ;
43 return original_dest;
44}
45
46char *strcat(char *dest, const char *src) {
47 char *original_dest = dest;
48 while (*dest) {
49 dest++;
50 }
51 while ((*dest++ = *src++))
52 ;
53
54 return original_dest;
55}
56
57int strncmp(const char *s1, const char *s2, size_t n) {
58 for (size_t i = 0; i < n; i++) {
59 if (s1[i] != s2[i] || s1[i] == '\0') {
60 return s1[i] < s2[i] ? -1 : 1;
61 }
62 }
63 return 0;
64}
65
66char *strncpy(char *dest, const char *src, size_t n) {
67 char *original_dest = dest;
68 size_t i;
69 for (i = 0; i < n && src[i] != '\0'; i++) {
70 dest[i] = src[i];
71 }
72 for (; i < n; i++) {
73 dest[i] = '\0';
74 }
75 return original_dest;
76}
77
78void *memchr(const void *s, int c, size_t n) {
79 const uint8_t *p = (const uint8_t *) s;
80 for (size_t i = 0; i < n; i++) {
81 if (p[i] == (uint8_t) c) {
82 return (void *) (p + i);
83 }
84 }
85 return NULL;
86}
87
88void *memrchr(const void *s, int c, size_t n) {
89 const uint8_t *p = (const uint8_t *) s;
90 for (size_t i = n; i > 0; i--) {
91 if (p[i - 1] == (uint8_t) c) {
92 return (void *) (p + (i - 1));
93 }
94 }
95 return NULL;
96}
97
98int strcmp(const char *str1, const char *str2) {
99 while (*str1 != '\0' && *str2 != '\0') {
100 if (*str1 != *str2) {
101 return (unsigned char) (*str1) - (unsigned char) (*str2);
102 }
103 str1++;
104 str2++;
105 }
106 return (unsigned char) (*str1) - (unsigned char) (*str2);
107}
108
109char *strchr(const char *s, int c) {
110 do {
111 if (*s == c) {
112 return (char *) s;
113 }
114 } while (*s++);
115 return (0);
116}
117
118int islower(int c) {
119 return (unsigned) c - 'a' < 26;
120}
121
122int isupper(int c) {
123 return (unsigned) c - 'A' < 26;
124}
125
126int isdigit(int c) {
127 return (unsigned) c - '0' < 10;
128}
129
130int isalpha(int c) {
131 return islower(c) || isupper(c);
132}
133
134int isalnum(int c) {
135 return isalpha(c) || isdigit(c);
136}
137
138int isspace(int c) {
139 return c == ' ' || c == '\t' || c == '\n' || c == '\r' || c == '\f' ||
140 c == '\v';
141}
142
143int isprint(int c) {
144 return (unsigned) c - 0x20 < 0x5f;
145}
146
147int toupper(int c) {
148 if (islower(c))
149 return c & 0x5f;
150 return c;
151}
152
153int tolower(int c) {
154 if (isupper(c))
155 return c | 0x20;
156 return c;
157}
158
159char *strdup(const char *str) {
160 if (!str)
161 return NULL;
162
163 size_t len = 0;
164 while (str[len] != '\0')
165 len++;
166
167 char *copy = (char *) kmalloc(len + 1);
168 if (!copy)
169 return NULL;
170
171 for (size_t i = 0; i <= len; i++)
172 copy[i] = str[i];
173
174 return copy;
175}
176
177char *strrchr(const char *s, int c) {
178 const char *last = NULL;
179 do {
180 if (*s == (char) c)
181 last = s;
182 } while (*s++);
183 return (char *) last;
184}
185
186size_t strspn(const char *s, const char *accept) {
187 size_t i = 0;
188 while (s[i]) {
189 const char *a = accept;
190 bool found = false;
191 while (*a) {
192 if (s[i] == *a++) {
193 found = true;
194 break;
195 }
196 }
197 if (!found)
198 break;
199 i++;
200 }
201 return i;
202}
203
204size_t strcspn(const char *s, const char *reject) {
205 size_t i = 0;
206 while (s[i]) {
207 const char *r = reject;
208 while (*r) {
209 if (s[i] == *r++)
210 goto done;
211 }
212 i++;
213 }
214done:
215 return i;
216}
217
218char *strpbrk(const char *s, const char *accept) {
219 while (*s) {
220 const char *a = accept;
221 while (*a) {
222 if (*s == *a++)
223 return (char *) s;
224 }
225 s++;
226 }
227 return NULL;
228}
229
230char *strstr(const char *haystack, const char *needle) {
231 if (!*needle)
232 return (char *) haystack;
233 size_t nlen = strlen(str: needle);
234 size_t hlen = strlen(str: haystack);
235 if (nlen > hlen)
236 return NULL;
237
238 // Build KMP failure table
239 int64_t table[nlen];
240 table[0] = -1;
241 int64_t k = -1;
242 for (size_t i = 1; i < nlen; i++) {
243 while (k >= 0 && needle[k + 1] != needle[i])
244 k = table[k];
245 if (needle[k + 1] == needle[i])
246 k++;
247 table[i] = k;
248 }
249
250 int64_t q = -1;
251 for (size_t i = 0; i < hlen; i++) {
252 while (q >= 0 && needle[q + 1] != haystack[i])
253 q = table[q];
254 if (needle[q + 1] == haystack[i])
255 q++;
256 if (q == (int64_t) nlen - 1)
257 return (char *) (haystack + i - nlen + 1);
258 }
259 return NULL;
260}
261
262char *strtok(char *str, const char *delim) {
263 static char *saved = NULL;
264 if (str)
265 saved = str;
266 if (!saved || !*saved)
267 return NULL;
268
269 saved += strspn(s: saved, accept: delim);
270 if (!*saved) {
271 saved = NULL;
272 return NULL;
273 }
274
275 char *token_start = saved;
276 saved += strcspn(s: saved, reject: delim);
277 if (*saved)
278 *saved++ = '\0';
279 else
280 saved = NULL;
281 return token_start;
282}
283
284char *strtok_r(char *str, const char *delim, char **saveptr) {
285 if (str)
286 *saveptr = str;
287 if (!*saveptr || !**saveptr)
288 return NULL;
289
290 *saveptr += strspn(s: *saveptr, accept: delim);
291 if (!**saveptr) {
292 *saveptr = NULL;
293 return NULL;
294 }
295
296 char *token_start = *saveptr;
297 *saveptr += strcspn(s: *saveptr, reject: delim);
298 if (**saveptr)
299 *(*saveptr)++ = '\0';
300 else
301 *saveptr = NULL;
302 return token_start;
303}
304
305char *strncat(char *dest, const char *src, size_t n) {
306 char *d = dest;
307 while (*d)
308 d++;
309 while (n-- && *src)
310 *d++ = *src++;
311 *d = '\0';
312 return dest;
313}
314
315size_t strnlen(const char *s, size_t maxlen) {
316 size_t i = 0;
317 while (i < maxlen && s[i] != '\0')
318 i++;
319 return i;
320}
321
322int64_t atoi(const char *str) {
323 while (isspace(c: (unsigned char) *str))
324 str++;
325 int64_t sign = 1;
326 if (*str == '-') {
327 sign = -1;
328 str++;
329 } else if (*str == '+')
330 str++;
331 int64_t result = 0;
332 while (isdigit(c: (unsigned char) *str))
333 result = result * 10 + (*str++ - '0');
334 return sign * result;
335}
336
337size_t atoui(const char *str) {
338 while (isspace(c: (unsigned char) *str))
339 str++;
340 if (*str == '+')
341 str++;
342 size_t result = 0;
343 while (isdigit(c: (unsigned char) *str))
344 result = result * 10 + (*str++ - '0');
345 return result;
346}
347
348size_t atohex(const char *str) {
349 while (isspace(c: (unsigned char) *str))
350 str++;
351 if (str[0] == '0' && (str[1] == 'x' || str[1] == 'X'))
352 str += 2;
353 size_t result = 0;
354 while (1) {
355 char c = *str++;
356 if (c >= '0' && c <= '9')
357 result = result * 16 + (c - '0');
358 else if (c >= 'a' && c <= 'f')
359 result = result * 16 + (c - 'a' + 10);
360 else if (c >= 'A' && c <= 'F')
361 result = result * 16 + (c - 'A' + 10);
362 else
363 break;
364 }
365 return result;
366}
367
368char *itoa(int64_t value, char *buf, int base) {
369 static const char digits[] = "0123456789abcdefghijklmnopqrstuvwxyz";
370 if (base < 2 || base > 36) {
371 buf[0] = '\0';
372 return buf;
373 }
374
375 char *p = buf;
376 char *start;
377 bool negative = (base == 10 && value < 0);
378 size_t uval = negative ? -(size_t) value : (size_t) value;
379
380 do {
381 *p++ = digits[uval % base];
382 uval /= base;
383 } while (uval);
384
385 if (negative)
386 *p++ = '-';
387 *p = '\0';
388
389 start = buf;
390 char *end = p - 1;
391 while (start < end) {
392 char tmp = *start;
393 *start++ = *end;
394 *end-- = tmp;
395 }
396 return buf;
397}
398
399char *utoa(size_t value, char *buf, int base) {
400 static const char digits[] = "0123456789abcdefghijklmnopqrstuvwxyz";
401 if (base < 2 || base > 36) {
402 buf[0] = '\0';
403 return buf;
404 }
405
406 char *p = buf;
407 char *start;
408 do {
409 *p++ = digits[value % base];
410 value /= base;
411 } while (value);
412 *p = '\0';
413
414 start = buf;
415 char *end = p - 1;
416 while (start < end) {
417 char tmp = *start;
418 *start++ = *end;
419 *end-- = tmp;
420 }
421 return buf;
422}
423
424int strcasecmp(const char *s1, const char *s2) {
425 while (*s1 && *s2) {
426 int d = tolower(c: (unsigned char) *s1) - tolower(c: (unsigned char) *s2);
427 if (d)
428 return d;
429 s1++;
430 s2++;
431 }
432 return tolower(c: (unsigned char) *s1) - tolower(c: (unsigned char) *s2);
433}
434
435int strncasecmp(const char *s1, const char *s2, size_t n) {
436 while (n-- && *s1 && *s2) {
437 int d = tolower(c: (unsigned char) *s1) - tolower(c: (unsigned char) *s2);
438 if (d)
439 return d;
440 s1++;
441 s2++;
442 }
443 if (n == (size_t) -1)
444 return 0;
445 return tolower(c: (unsigned char) *s1) - tolower(c: (unsigned char) *s2);
446}
447
448char *strrev(char *s) {
449 char *l = s, *r = s + strlen(str: s) - 1;
450 while (l < r) {
451 char t = *l;
452 *l++ = *r;
453 *r-- = t;
454 }
455 return s;
456}
457
458char *strtoupper(char *s) {
459 for (char *p = s; *p; p++)
460 *p = (char) toupper(c: (unsigned char) *p);
461 return s;
462}
463
464char *strtolower(char *s) {
465 for (char *p = s; *p; p++)
466 *p = (char) tolower(c: (unsigned char) *p);
467 return s;
468}
469
470char *strndup(const char *str, size_t n) {
471 if (!str)
472 return NULL;
473 size_t len = strnlen(s: str, maxlen: n);
474 char *copy = (char *) kmalloc(len + 1);
475 if (!copy)
476 return NULL;
477 memcpy(dest: copy, src: str, n: len);
478 copy[len] = '\0';
479 return copy;
480}
481
482long strtol(const char *nptr, char **endptr, int base) {
483 const char *s = nptr;
484
485 while (*s && isspace(c: (unsigned char) *s)) {
486 s++;
487 }
488
489 int neg = 0;
490 if (*s == '+' || *s == '-') {
491 neg = (*s == '-');
492 s++;
493 }
494
495 if (base != 0 && (base < 2 || base > 36)) {
496 if (endptr)
497 *endptr = (char *) nptr;
498 return 0;
499 }
500
501 if (base == 0) {
502 if (*s == '0') {
503 if (s[1] == 'x' || s[1] == 'X') {
504 base = 16;
505 s += 2;
506 } else {
507 base = 8;
508 s += 1;
509 }
510 } else {
511 base = 10;
512 }
513 } else {
514 if (base == 16 && *s == '0' && (s[1] == 'x' || s[1] == 'X')) {
515 s += 2;
516 }
517 }
518
519 const char *start_digits = s;
520
521 unsigned long acc = 0;
522
523 unsigned long limit =
524 neg ? (unsigned long) LONG_MAX + 1UL : (unsigned long) LONG_MAX;
525
526 for (;;) {
527 int digit;
528
529 char c = *s;
530 if (c >= '0' && c <= '9')
531 digit = c - '0';
532 else if (c >= 'a' && c <= 'z')
533 digit = 10 + (c - 'a');
534 else if (c >= 'A' && c <= 'Z')
535 digit = 10 + (c - 'A');
536 else
537 break;
538
539 if (digit >= base)
540 break;
541
542 if (acc > (limit - (unsigned long) digit) / (unsigned long) base) {
543 while (1) {
544 s++;
545 char dch = *s;
546 if (dch >= '0' && dch <= '9')
547 digit = dch - '0';
548 else if (dch >= 'a' && dch <= 'z')
549 digit = 10 + (dch - 'a');
550 else if (dch >= 'A' && dch <= 'Z')
551 digit = 10 + (dch - 'A');
552 else
553 break;
554 if (digit >= base)
555 break;
556 }
557 break;
558 }
559
560 acc = acc * (unsigned long) base + (unsigned long) digit;
561 s++;
562 }
563
564 if (endptr)
565 *endptr = (char *) s;
566
567 if (s == start_digits) {
568 return 0;
569 }
570
571 if (neg) {
572 if (acc == (unsigned long) LONG_MAX + 1UL)
573 return LONG_MIN;
574 return -(long) acc;
575 } else {
576 return (long) acc;
577 }
578}
579
580unsigned long long strtoull(const char *nptr, char **endptr, int base) {
581 const char *s = nptr;
582
583 while (*s && isspace(c: (unsigned char) *s))
584 s++;
585
586 int neg = 0;
587 if (*s == '+' || *s == '-') {
588 neg = (*s == '-');
589 s++;
590 }
591
592 if (base != 0 && (base < 2 || base > 36)) {
593 if (endptr)
594 *endptr = (char *) nptr;
595 return 0;
596 }
597
598 if (base == 0) {
599 if (*s == '0' && (s[1] == 'x' || s[1] == 'X')) {
600 base = 16;
601 s += 2;
602 } else if (*s == '0') {
603 base = 8;
604 } else {
605 base = 10;
606 }
607 } else if (base == 16 && *s == '0' && (s[1] == 'x' || s[1] == 'X')) {
608 s += 2;
609 }
610
611 const char *start_digits = s;
612 unsigned long long acc = 0;
613 int overflow = 0;
614
615 for (;;) {
616 int digit;
617 char c = *s;
618 if (c >= '0' && c <= '9')
619 digit = c - '0';
620 else if (c >= 'a' && c <= 'z')
621 digit = 10 + (c - 'a');
622 else if (c >= 'A' && c <= 'Z')
623 digit = 10 + (c - 'A');
624 else
625 break;
626
627 if (digit >= base)
628 break;
629
630 if (overflow || acc > (ULLONG_MAX - (unsigned long long) digit) /
631 (unsigned long long) base)
632 overflow = 1; /* keep consuming digits so endptr stays correct */
633 else
634 acc = acc * (unsigned long long) base + (unsigned long long) digit;
635
636 s++;
637 }
638
639 if (endptr)
640 *endptr = (char *) (s == start_digits ? nptr : s);
641
642 if (s == start_digits)
643 return 0;
644
645 if (overflow)
646 return ULLONG_MAX;
647
648 return neg ? (0ULL - acc) : acc;
649}
650
651unsigned long strtoul(const char *nptr, char **endptr, int base) {
652 return (unsigned long) strtoull(nptr, endptr, base);
653}
654
655long long strtoll(const char *nptr, char **endptr, int base) {
656 return (long long) strtol(nptr, endptr, base);
657}
658
659size_t strlcpy(char *dst, const char *src, size_t size) {
660 size_t srclen = strlen(str: src);
661 if (size) {
662 size_t n = (srclen < size - 1) ? srclen : size - 1;
663 memcpy(dest: dst, src, n);
664 dst[n] = '\0';
665 }
666 return srclen;
667}
668
669size_t strlcat(char *dst, const char *src, size_t size) {
670 size_t dstlen = strnlen(s: dst, maxlen: size);
671 size_t srclen = strlen(str: src);
672
673 if (dstlen == size)
674 return size + srclen;
675
676 size_t avail = size - dstlen;
677 size_t n = (srclen < avail - 1) ? srclen : avail - 1;
678 memcpy(dest: dst + dstlen, src, n);
679 dst[dstlen + n] = '\0';
680 return dstlen + srclen;
681}
682
683char *strsep(char **stringp, const char *delim) {
684 char *start = *stringp;
685 if (!start)
686 return NULL;
687
688 char *p = strpbrk(s: start, accept: delim);
689 if (p) {
690 *p = '\0';
691 *stringp = p + 1;
692 } else {
693 *stringp = NULL;
694 }
695 return start;
696}
697
698char *strchrnul(const char *s, int c) {
699 while (*s && *s != (char) c)
700 s++;
701 return (char *) s;
702}
703