Merge lib into kern

There are no precise enough criteria to justify the separation of these
two directories.

1 files changed, 550 insertions, 0 deletions

diff --git a/kern/sprintf.c b/kern/sprintf.c
new file mode 100644
index 00000000..13f2671e
--- /dev/null
+++ b/kern/sprintf.c
@@ -0,0 +1,550 @@
+/*
+ * Copyright (c) 2010 Richard Braun.
+ *
+ * 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
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <stdarg.h>
+
+#include <kern/limits.h>
+#include <kern/sprintf.h>
+#include <kern/stddef.h>
+#include <kern/stdint.h>
+
+/*
+ * Formatting flags.
+ *
+ * FORMAT_LOWER must be 0x20 as it is OR'd with digits, eg.
+ * '0': 0x30 | 0x20 => 0x30 ('0')
+ * 'A': 0x41 | 0x20 => 0x61 ('a')
+ */
+#define SPRINTF_FORMAT_ALT_FORM     0x01
+#define SPRINTF_FORMAT_ZERO_PAD     0x02
+#define SPRINTF_FORMAT_LEFT_JUSTIFY 0x04
+#define SPRINTF_FORMAT_BLANK        0x08
+#define SPRINTF_FORMAT_SIGN         0x10
+#define SPRINTF_FORMAT_LOWER        0x20
+#define SPRINTF_FORMAT_CONV_SIGNED  0x40
+
+enum {
+    SPRINTF_MODIFIER_NONE,
+    SPRINTF_MODIFIER_CHAR,
+    SPRINTF_MODIFIER_SHORT,
+    SPRINTF_MODIFIER_LONG,
+    SPRINTF_MODIFIER_LONGLONG,
+    SPRINTF_MODIFIER_PTR,       /* Used only for %p */
+    SPRINTF_MODIFIER_SIZE,
+    SPRINTF_MODIFIER_PTRDIFF
+};
+
+enum {
+    SPRINTF_SPECIFIER_INVALID,
+    SPRINTF_SPECIFIER_INT,
+    SPRINTF_SPECIFIER_CHAR,
+    SPRINTF_SPECIFIER_STR,
+    SPRINTF_SPECIFIER_NRCHARS,
+    SPRINTF_SPECIFIER_PERCENT
+};
+
+/*
+ * Size for the temporary number buffer. The minimum base is 8 so 3 bits
+ * are consumed per digit. Add one to round up. The conversion algorithm
+ * doesn't use the null byte.
+ */
+#define SPRINTF_MAX_NUM_SIZE (((sizeof(uint64_t) * CHAR_BIT) / 3) + 1)
+
+/*
+ * Special size for vsnprintf(), used by sprintf()/vsprintf() when the
+ * buffer size is unknown.
+ */
+#define SPRINTF_NOLIMIT ((size_t)-1)
+
+static const char sprintf_digits[] = "0123456789ABCDEF";
+
+static inline char *
+sprintf_putchar(char *str, char *end, char c)
+{
+    if (str < end)
+        *str = c;
+
+    str++;
+
+    return str;
+}
+
+static inline int
+sprintf_isdigit(char c)
+{
+    return (c >= '0') && (c <= '9');
+}
+
+int
+sprintf(char *str, const char *format, ...)
+{
+    va_list ap;
+    int length;
+
+    va_start(ap, format);
+    length = vsprintf(str, format, ap);
+    va_end(ap);
+
+    return length;
+}
+
+int
+vsprintf(char *str, const char *format, va_list ap)
+{
+    return vsnprintf(str, SPRINTF_NOLIMIT, format, ap);
+}
+
+int
+snprintf(char *str, size_t size, const char *format, ...)
+{
+    va_list ap;
+    int length;
+
+    va_start(ap, format);
+    length = vsnprintf(str, size, format, ap);
+    va_end(ap);
+
+    return length;
+}
+
+int
+vsnprintf(char *str, size_t size, const char *format, va_list ap)
+{
+    unsigned long long n;
+    int i, len, found, flags, width, precision, modifier, specifier, shift;
+    unsigned char r, base, mask;
+    char c, *s, *start, *end, sign, tmp[SPRINTF_MAX_NUM_SIZE];
+
+    start = str;
+
+    if (size == 0)
+        end = NULL;
+    else if (size == SPRINTF_NOLIMIT)
+        end = (char *)-1;
+    else
+        end = start + size - 1;
+
+    while ((c = *format) != '\0') {
+        if (c != '%') {
+            str = sprintf_putchar(str, end, c);
+            format++;
+            continue;
+        }
+
+        /* Flags */
+
+        found = 1;
+        flags = 0;
+
+        do {
+            format++;
+            c = *format;
+
+            switch (c) {
+            case '#':
+                flags |= SPRINTF_FORMAT_ALT_FORM;
+                break;
+            case '0':
+                flags |= SPRINTF_FORMAT_ZERO_PAD;
+                break;
+            case '-':
+                flags |= SPRINTF_FORMAT_LEFT_JUSTIFY;
+                break;
+            case ' ':
+                flags |= SPRINTF_FORMAT_BLANK;
+                break;
+            case '+':
+                flags |= SPRINTF_FORMAT_SIGN;
+                break;
+            default:
+                found = 0;
+                break;
+            }
+        } while (found);
+
+        /* Width */
+
+        if (sprintf_isdigit(c)) {
+            width = 0;
+
+            while (sprintf_isdigit(c)) {
+                width = width * 10 + (c - '0');
+                format++;
+                c = *format;
+            }
+        } else if (c == '*') {
+            width = va_arg(ap, int);
+
+            if (width < 0) {
+                flags |= SPRINTF_FORMAT_LEFT_JUSTIFY;
+                width = -width;
+            }
+
+            format++;
+            c = *format;
+        } else {
+            width = 0;
+        }
+
+        /* Precision */
+
+        if (c == '.') {
+            format++;
+            c = *format;
+
+            if (sprintf_isdigit(c)) {
+                precision = 0;
+
+                while (sprintf_isdigit(c)) {
+                    precision = precision * 10 + (c - '0');
+                    format++;
+                    c = *format;
+                }
+            } else if (c == '*') {
+                precision = va_arg(ap, int);
+
+                if (precision < 0)
+                    precision = 0;
+
+                format++;
+                c = *format;
+            } else {
+                precision = 0;
+            }
+        } else {
+            /* precision is >= 0 only if explicit */
+            precision = -1;
+        }
+
+        /* Length modifier */
+
+        switch (c) {
+        case 'h':
+        case 'l':
+            format++;
+
+            if (c == *format) {
+                modifier = (c == 'h')
+                           ? SPRINTF_MODIFIER_CHAR
+                           : SPRINTF_MODIFIER_LONGLONG;
+                goto skip_modifier;
+            } else {
+                modifier = (c == 'h')
+                           ? SPRINTF_MODIFIER_SHORT
+                           : SPRINTF_MODIFIER_LONG;
+                c = *format;
+            }
+
+            break;
+        case 'z':
+            modifier = SPRINTF_MODIFIER_SIZE;
+            goto skip_modifier;
+        case 't':
+            modifier = SPRINTF_MODIFIER_PTRDIFF;
+skip_modifier:
+            format++;
+            c = *format;
+            break;
+        default:
+            modifier = SPRINTF_MODIFIER_NONE;
+            break;
+        }
+
+        /* Specifier */
+
+        switch (c) {
+        case 'd':
+        case 'i':
+            flags |= SPRINTF_FORMAT_CONV_SIGNED;
+        case 'u':
+            base = 10;
+            goto integer;
+        case 'o':
+            base = 8;
+            goto integer;
+        case 'p':
+            flags |= SPRINTF_FORMAT_ALT_FORM;
+            modifier = SPRINTF_MODIFIER_PTR;
+        case 'x':
+            flags |= SPRINTF_FORMAT_LOWER;
+        case 'X':
+            base = 16;
+integer:
+            specifier = SPRINTF_SPECIFIER_INT;
+            break;
+        case 'c':
+            specifier = SPRINTF_SPECIFIER_CHAR;
+            break;
+        case 's':
+            specifier = SPRINTF_SPECIFIER_STR;
+            break;
+        case 'n':
+            specifier = SPRINTF_SPECIFIER_NRCHARS;
+            break;
+        case '%':
+            specifier = SPRINTF_SPECIFIER_PERCENT;
+            break;
+        default:
+            specifier = SPRINTF_SPECIFIER_INVALID;
+            break;
+        }
+
+        /* Output */
+
+        switch (specifier) {
+        case SPRINTF_SPECIFIER_INT:
+            switch (modifier) {
+            case SPRINTF_MODIFIER_CHAR:
+                if (flags & SPRINTF_FORMAT_CONV_SIGNED)
+                    n = (signed char)va_arg(ap, int);
+                else
+                    n = (unsigned char)va_arg(ap, int);
+                break;
+            case SPRINTF_MODIFIER_SHORT:
+                if (flags & SPRINTF_FORMAT_CONV_SIGNED)
+                    n = (short)va_arg(ap, int);
+                else
+                    n = (unsigned short)va_arg(ap, int);
+                break;
+            case SPRINTF_MODIFIER_LONG:
+                if (flags & SPRINTF_FORMAT_CONV_SIGNED)
+                    n = va_arg(ap, long);
+                else
+                    n = va_arg(ap, unsigned long);
+                break;
+            case SPRINTF_MODIFIER_LONGLONG:
+                if (flags & SPRINTF_FORMAT_CONV_SIGNED)
+                    n = va_arg(ap, long long);
+                else
+                    n = va_arg(ap, unsigned long long);
+                break;
+            case SPRINTF_MODIFIER_PTR:
+                n = (unsigned long)va_arg(ap, void *);
+                break;
+            case SPRINTF_MODIFIER_SIZE:
+                if (flags & SPRINTF_FORMAT_CONV_SIGNED)
+                    n = va_arg(ap, ssize_t);
+                else
+                    n = va_arg(ap, size_t);
+                break;
+            case SPRINTF_MODIFIER_PTRDIFF:
+                n = va_arg(ap, ptrdiff_t);
+                break;
+            default:
+                if (flags & SPRINTF_FORMAT_CONV_SIGNED)
+                    n = va_arg(ap, int);
+                else
+                    n = va_arg(ap, unsigned int);
+                break;
+            }
+
+            if ((flags & SPRINTF_FORMAT_LEFT_JUSTIFY) || (precision >= 0))
+                flags &= ~SPRINTF_FORMAT_ZERO_PAD;
+
+            sign = 0;
+
+            if (flags & SPRINTF_FORMAT_ALT_FORM) {
+                /* '0' for octal */
+                width--;
+
+                /* '0x' or '0X' for hexadecimal */
+                if (base == 16)
+                    width--;
+            } else if (flags & SPRINTF_FORMAT_CONV_SIGNED) {
+                if ((long long)n < 0) {
+                    sign = '-';
+                    width--;
+                    n = -(long long)n;
+                } else if (flags & SPRINTF_FORMAT_SIGN) {
+                    /* SPRINTF_FORMAT_SIGN must precede SPRINTF_FORMAT_BLANK. */
+                    sign = '+';
+                    width--;
+                } else if (flags & SPRINTF_FORMAT_BLANK) {
+                    sign = ' ';
+                    width--;
+                }
+            }
+
+            /* Conversion, in reverse order */
+
+            i = 0;
+
+            if (n == 0) {
+                if (precision != 0)
+                    tmp[i++] = '0';
+            } else if (base == 10) {
+                /*
+                 * Try to avoid 64 bits operations if the processor doesn't
+                 * support them. Note that even when using modulus and
+                 * division operators close to each other, the compiler will
+                 * forge two calls to __udivdi3() and __umoddi3() instead of
+                 * one to __udivmoddi3(), whereas processor instructions are
+                 * generally correctly used once, giving both the remainder
+                 * and the quotient, through plain or reciprocal division.
+                 */
+#ifndef __LP64__
+                if (modifier == SPRINTF_MODIFIER_LONGLONG) {
+#endif /* __LP64__ */
+                    do {
+                        r = n % 10;
+                        n /= 10;
+                        tmp[i++] = sprintf_digits[r];
+                    } while (n != 0);
+#ifndef __LP64__
+                } else {
+                    unsigned long m;
+
+                    m = (unsigned long)n;
+
+                    do {
+                        r = m % 10;
+                        m /= 10;
+                        tmp[i++] = sprintf_digits[r];
+                    } while (m != 0);
+                }
+#endif /* __LP64__ */
+            } else {
+                mask = base - 1;
+                shift = (base == 8) ? 3 : 4;
+
+                do {
+                    r = (unsigned char)n & mask;
+                    n >>= shift;
+                    tmp[i++] = sprintf_digits[r]
+                               | (flags & SPRINTF_FORMAT_LOWER);
+                } while (n != 0);
+            }
+
+            if (i > precision)
+                precision = i;
+
+            width -= precision;
+
+            if (!(flags & (SPRINTF_FORMAT_LEFT_JUSTIFY
+                           | SPRINTF_FORMAT_ZERO_PAD)))
+                while (width-- > 0)
+                    str = sprintf_putchar(str, end, ' ');
+
+            if (flags & SPRINTF_FORMAT_ALT_FORM) {
+                str = sprintf_putchar(str, end, '0');
+
+                if (base == 16)
+                    str = sprintf_putchar(str, end,
+                                          'X' | (flags & SPRINTF_FORMAT_LOWER));
+            } else if (sign) {
+                str = sprintf_putchar(str, end, sign);
+            }
+
+            if (!(flags & SPRINTF_FORMAT_LEFT_JUSTIFY)) {
+                c = (flags & SPRINTF_FORMAT_ZERO_PAD) ? '0' : ' ';
+
+                while (width-- > 0)
+                    str = sprintf_putchar(str, end, c);
+            }
+
+            while (i < precision--)
+                str = sprintf_putchar(str, end, '0');
+
+            while (i-- > 0)
+                str = sprintf_putchar(str, end, tmp[i]);
+
+            while (width-- > 0)
+                str = sprintf_putchar(str, end, ' ');
+
+            break;
+        case SPRINTF_SPECIFIER_CHAR:
+            c = (unsigned char)va_arg(ap, int);
+
+            if (!(flags & SPRINTF_FORMAT_LEFT_JUSTIFY))
+                while (--width > 0)
+                    str = sprintf_putchar(str, end, ' ');
+
+            str = sprintf_putchar(str, end, c);
+
+            while (--width > 0)
+                str = sprintf_putchar(str, end, ' ');
+
+            break;
+        case SPRINTF_SPECIFIER_STR:
+            s = va_arg(ap, char *);
+
+            if (s == NULL)
+                s = "(null)";
+
+            len = 0;
+
+            for (len = 0; s[len] != '\0'; len++)
+                if (len == precision)
+                    break;
+
+            if (!(flags & SPRINTF_FORMAT_LEFT_JUSTIFY))
+                while (len < width--)
+                    str = sprintf_putchar(str, end, ' ');
+
+            for (i = 0; i < len; i++) {
+                str = sprintf_putchar(str, end, *s);
+                s++;
+            }
+
+            while (len < width--)
+                str = sprintf_putchar(str, end, ' ');
+
+            break;
+        case SPRINTF_SPECIFIER_NRCHARS:
+            if (modifier == SPRINTF_MODIFIER_CHAR) {
+                signed char *ptr = va_arg(ap, signed char *);
+                *ptr = str - start;
+            } else if (modifier == SPRINTF_MODIFIER_SHORT) {
+                short *ptr = va_arg(ap, short *);
+                *ptr = str - start;
+            } else if (modifier == SPRINTF_MODIFIER_LONG) {
+                long *ptr = va_arg(ap, long *);
+                *ptr = str - start;
+            } else if (modifier == SPRINTF_MODIFIER_LONGLONG) {
+                long long *ptr = va_arg(ap, long long *);
+                *ptr = str - start;
+            } else if (modifier == SPRINTF_MODIFIER_SIZE) {
+                ssize_t *ptr = va_arg(ap, ssize_t *);
+                *ptr = str - start;
+            } else if (modifier == SPRINTF_MODIFIER_PTRDIFF) {
+                ptrdiff_t *ptr = va_arg(ap, ptrdiff_t *);
+                *ptr = str - start;
+            } else {
+                int *ptr = va_arg(ap, int *);
+                *ptr = str - start;
+            }
+
+            break;
+        case SPRINTF_SPECIFIER_PERCENT:
+        case SPRINTF_SPECIFIER_INVALID:
+            str = sprintf_putchar(str, end, '%');
+            break;
+        default:
+            break;
+        }
+
+        if (specifier != SPRINTF_SPECIFIER_INVALID)
+            format++;
+    }
+
+    if (str < end)
+        *str = '\0';
+    else if (end != NULL)
+        *end = '\0';
+
+    return str - start;
+}