pintos-os.org Git - pintos-anon/blob - src/lib/lib.c

   1 #include <stdint.h>
   2 #include <stdarg.h>
   3 #include <stdbool.h>
   4 #include <stddef.h>
   5 #include "debug.h"
   6 #include "lib.h"
   7 #include "serial.h"
   8 #include "vga.h"
   9
  10 void *
  11 memset (void *dst_, int value, size_t cnt)
  12 {
  13   unsigned char *dst = dst_;
  14
  15   while (cnt-- > 0)
  16     *dst++ = value;
  17
  18   return dst_;
  19 }
  20
  21 void *
  22 memcpy (void *dst_, const void *src_, size_t cnt)
  23 {
  24   unsigned char *dst = dst_;
  25   const unsigned char *src = src_;
  26
  27   while (cnt-- > 0)
  28     *dst++ = *src++;
  29
  30   return dst_;
  31 }
  32
  33 void *
  34 memmove (void *dst_, const void *src_, size_t cnt)
  35 {
  36   unsigned char *dst = dst_;
  37   const unsigned char *src = src_;
  38
  39   if (dst < src)
  40     {
  41       while (cnt-- > 0)
  42         *dst++ = *src++;
  43     }
  44   else
  45     {
  46       dst += cnt;
  47       src += cnt;
  48       while (cnt-- > 0)
  49         *--dst = *--src;
  50     }
  51
  52   return dst;
  53 }
  54
  55 void *
  56 memchr (const void *block_, int ch_, size_t size)
  57 {
  58   const unsigned char *block = block_;
  59   unsigned char ch = ch_;
  60
  61   for (; size-- > 0; block++)
  62     if (*block == ch)
  63       return (void *) block;
  64
  65   return NULL;
  66 }
  67
  68 int
  69 memcmp (const void *a_, const void *b_, size_t size)
  70 {
  71   const unsigned char *a = a_;
  72   const unsigned char *b = b_;
  73
  74   for (; size-- > 0; a++, b++)
  75     if (*a != *b)
  76       return *a > *b ? +1 : -1;
  77   return 0;
  78 }
  79
  80 size_t
  81 strlcpy (char *dst, const char *src, size_t size)
  82 {
  83   size_t src_len = strlen (src);
  84   if (size > 0)
  85     {
  86       size_t dst_len_max = size - 1;
  87       size_t dst_len = src_len < dst_len_max ? src_len : dst_len_max;
  88       memcpy (dst, src, dst_len);
  89       dst[dst_len] = '\0';
  90     }
  91   return src_len;
  92 }
  93
  94 size_t
  95 strlen (const char *string)
  96 {
  97   const char *p;
  98
  99   for (p = string; *p != '\0'; p++)
 100     continue;
 101   return p - string;
 102 }
 103
 104 char *
 105 strchr (const char *string, int c_)
 106 {
 107   char c = c_;
 108
 109   for (;;)
 110     if (*string == c)
 111       return (char *) string;
 112     else if (*string == '\0')
 113       return NULL;
 114     else string++;
 115 }
 116
 117 static void
 118 vprintf_core (const char *format, va_list args,
 119               void (*output) (char, void *), void *aux);
 120
 121 static void
 122 output_console (char ch, void *aux __attribute__ ((unused)))
 123 {
 124   vga_putc (ch);
 125   serial_outb (ch);
 126 }
 127
 128 void
 129 vprintk (const char *format, va_list args)
 130 {
 131   vprintf_core (format, args, output_console, NULL);
 132 }
 133
 134 void
 135 printk (const char *format, ...)
 136 {
 137   va_list args;
 138
 139   va_start (args, format);
 140   vprintk (format, args);
 141   va_end (args);
 142 }
 143 \f
 144 /* printf() and friends internals.  You do not need to understand
 145    this code. */
 146
 147 struct printf_conversion
 148   {
 149     enum
 150       {
 151         MINUS = 1 << 0,
 152         PLUS = 1 << 1,
 153         SPACE = 1 << 2,
 154         POUND = 1 << 3,
 155         ZERO = 1 << 4
 156       }
 157     flags;
 158
 159     int width;
 160     int precision;
 161
 162     enum
 163       {
 164         CHAR = 1,
 165         SHORT = 2,
 166         INT = 3,
 167         INTMAX = 4,
 168         LONG = 5,
 169         LONGLONG = 6,
 170         PTRDIFFT = 7,
 171         SIZET = 8
 172       }
 173     type;
 174   };
 175
 176 static const char *
 177 parse_conversion (const char *format, struct printf_conversion *c, va_list *args)
 178 {
 179   /* Parse flag characters. */
 180   c->flags = 0;
 181   for (;;)
 182     {
 183       switch (*format++)
 184         {
 185         case '-':
 186           c->flags |= MINUS;
 187           break;
 188         case '+':
 189           c->flags |= PLUS;
 190           break;
 191         case ' ':
 192           c->flags |= SPACE;
 193           break;
 194         case '#':
 195           c->flags |= POUND;
 196           break;
 197         case '0':
 198           c->flags |= ZERO;
 199           break;
 200         default:
 201           format--;
 202           goto not_a_flag;
 203         }
 204     }
 205  not_a_flag:
 206   if (c->flags & MINUS)
 207     c->flags &= ~ZERO;
 208   if (c->flags & PLUS)
 209     c->flags &= ~SPACE;
 210
 211   /* Parse field width. */
 212   c->width = 0;
 213   if (*format == '*')
 214     {
 215       format++;
 216       c->width = va_arg (*args, int);
 217     }
 218   else
 219     {
 220       for (; isdigit (*format); format++)
 221         c->width = c->width * 10 + *format - '0';
 222     }
 223   if (c->width < 0)
 224     {
 225       c->width = -c->width;
 226       c->flags |= MINUS;
 227     }
 228
 229   /* Parse precision. */
 230   c->precision = -1;
 231   if (*format == '.')
 232     {
 233       format++;
 234       if (*format == '*')
 235         {
 236           format++;
 237           c->precision = va_arg (*args, int);
 238         }
 239       else
 240         {
 241           c->precision = 0;
 242           for (; isdigit (*format); format++)
 243             c->precision = c->precision * 10 + *format - '0';
 244         }
 245       if (c->precision < 0)
 246         c->precision = -1;
 247     }
 248   if (c->precision >= 0)
 249     c->flags &= ~ZERO;
 250
 251   /* Parse type. */
 252   c->type = INT;
 253   switch (*format++)
 254     {
 255     case 'h':
 256       if (*format == 'h')
 257         {
 258           format++;
 259           c->type = CHAR;
 260         }
 261       else
 262         c->type = SHORT;
 263       break;
 264
 265     case 'j':
 266       c->type = INTMAX;
 267       break;
 268
 269     case 'l':
 270       if (*format == 'l')
 271         {
 272           format++;
 273           c->type = LONGLONG;
 274         }
 275       else
 276         c->type = LONG;
 277       break;
 278
 279     case 'L':
 280     case 'q':
 281       c->type = LONGLONG;
 282       break;
 283
 284     case 't':
 285       c->type = PTRDIFFT;
 286       break;
 287
 288     case 'z':
 289     case 'Z':
 290       c->type = SIZET;
 291       break;
 292
 293     default:
 294       format--;
 295       break;
 296     }
 297
 298   return format;
 299 }
 300
 301 static void
 302 output_dup (char ch, size_t cnt, void (*output) (char, void *), void *aux)
 303 {
 304   while (cnt-- > 0)
 305     output (ch, aux);
 306 }
 307
 308 static void
 309 printf_integer (uintmax_t value, bool negative, const char *digits,
 310                 struct printf_conversion *c,
 311                 void (*output) (char, void *), void *aux)
 312
 313 {
 314   int base = strlen (digits);
 315
 316   char buf[64];
 317   char *const buf_end = buf + sizeof buf;
 318   char *bp;
 319
 320   int pad;
 321
 322   /* Accumulate digits into buffer.
 323      This algorithm produces digits in reverse order, so we count
 324      backward from the end of the array. */
 325   bp = buf_end;
 326   while (value > 0)
 327     {
 328       *--bp = digits[value % base];
 329       value /= base;
 330     }
 331
 332   /* Prepend enough zeros to match precision.
 333      If precision is 0, then a value of zero is rendered as a
 334      null string.  Otherwise at least one digit is presented. */
 335   if (c->precision < 0)
 336     c->precision = 1;
 337   while (buf_end - bp < c->precision && bp > buf + 3)
 338     *--bp = '0';
 339
 340   /* Prepend sign. */
 341   if (c->flags & PLUS)
 342     *--bp = negative ? '-' : '+';
 343   else if (c->flags & SPACE)
 344     *--bp = negative ? '-' : ' ';
 345   else if (negative)
 346     *--bp = '-';
 347
 348   /* Prepend base. */
 349   if ((c->flags & POUND) && base != 10)
 350     {
 351       *--bp = digits[0xa] == 'a' ? 'x' : 'X';
 352       *--bp = '0';
 353     }
 354
 355   /* Calculate number of pad characters to fill field width. */
 356   pad = c->width - (buf_end - bp);
 357   if (pad < 0)
 358     pad = 0;
 359
 360   /* Do output. */
 361   if ((c->flags & (MINUS | ZERO)) == 0)
 362     output_dup (' ', pad, output, aux);
 363   if (bp < buf_end && strchr (digits, *bp) == NULL)
 364     output (*bp++, aux);
 365   if (c->flags & ZERO)
 366     output_dup ('0', pad, output, aux);
 367   while (bp < buf_end)
 368     output (*bp++, aux);
 369   if (c->flags & MINUS)
 370     output_dup (' ', pad, output, aux);
 371 }
 372
 373 static void
 374 printf_string (const char *string, size_t length,
 375                struct printf_conversion *c,
 376                void (*output) (char, void *), void *aux)
 377 {
 378   if (c->width > 1 && (c->flags & MINUS) == 0)
 379     output_dup (' ', c->width - 1, output, aux);
 380   while (length-- > 0)
 381     output (*string++, aux);
 382   if (c->width > 1 && (c->flags & MINUS) != 0)
 383     output_dup (' ', c->width - 1, output, aux);
 384 }
 385
 386 static void
 387 printf_core (const char *format,
 388              void (*output) (char, void *), void *aux, ...)
 389 {
 390   va_list args;
 391
 392   va_start (args, aux);
 393   vprintf_core (format, args, output, aux);
 394   va_end (args);
 395 }
 396
 397 static void
 398 vprintf_core (const char *format, va_list args,
 399               void (*output) (char, void *), void *aux)
 400 {
 401   for (; *format != '\0'; format++)
 402     {
 403       struct printf_conversion c;
 404
 405       /* Literally copy non-conversions to output. */
 406       if (*format != '%')
 407         {
 408           output (*format, aux);
 409           continue;
 410         }
 411       format++;
 412
 413       /* %% => %. */
 414       if (*format == '%')
 415         {
 416           output ('%', aux);
 417           continue;
 418         }
 419
 420       format = parse_conversion (format, &c, &args);
 421       switch (*format)
 422         {
 423         case 'd':
 424         case 'i':
 425           {
 426             intmax_t value;
 427             uintmax_t abs_value;
 428             bool negative = false;
 429
 430             switch (c.type)
 431               {
 432               case CHAR:
 433                 value = (signed char) va_arg (args, int);
 434                 break;
 435               case SHORT:
 436                 value = (short) va_arg (args, int);
 437                 break;
 438               case INT:
 439                 value = va_arg (args, int);
 440                 break;
 441               case LONG:
 442                 value = va_arg (args, long);
 443                 break;
 444               case LONGLONG:
 445                 value = va_arg (args, long long);
 446                 break;
 447               case PTRDIFFT:
 448                 value = va_arg (args, ptrdiff_t);
 449                 break;
 450               case SIZET:
 451                 value = va_arg (args, size_t);
 452                 break;
 453               default:
 454                 NOT_REACHED ();
 455               }
 456
 457             if (value < 0)
 458               {
 459                 negative = true;
 460                 abs_value = -value;
 461               }
 462             else
 463               abs_value = value;
 464
 465             printf_integer (abs_value, negative, "0123456789",
 466                             &c, output, aux);
 467           }
 468           break;
 469
 470         case 'o':
 471         case 'u':
 472         case 'x':
 473         case 'X':
 474           {
 475             uintmax_t value;
 476             const char *digits;
 477
 478             switch (c.type)
 479               {
 480               case CHAR:
 481                 value = (unsigned char) va_arg (args, unsigned);
 482                 break;
 483               case SHORT:
 484                 value = (unsigned short) va_arg (args, unsigned);
 485                 break;
 486               case INT:
 487                 value = va_arg (args, unsigned);
 488                 break;
 489               case LONG:
 490                 value = va_arg (args, unsigned long);
 491                 break;
 492               case LONGLONG:
 493                 value = va_arg (args, unsigned long long);
 494                 break;
 495               case PTRDIFFT:
 496                 value = va_arg (args, ptrdiff_t);
 497                 break;
 498               case SIZET:
 499                 value = va_arg (args, size_t);
 500                 break;
 501               default:
 502                 NOT_REACHED ();
 503               }
 504
 505             switch (*format)
 506               {
 507               case 'o':
 508                 digits = "01234567";
 509                 break;
 510               case 'u':
 511                 digits = "0123456789";
 512                 break;
 513               case 'x':
 514                 digits = "0123456789abcdef";
 515                 break;
 516               case 'X':
 517                 digits = "0123456789ABCDEF";
 518                 break;
 519               default:
 520                 NOT_REACHED ();
 521               }
 522
 523             printf_integer (value, false, digits, &c, output, aux);
 524           }
 525           break;
 526
 527         case 'c':
 528           {
 529             char ch = va_arg (args, int);
 530             printf_string (&ch, 1, &c, output, aux);
 531           }
 532           break;
 533
 534         case 's':
 535           {
 536             const char *s;
 537             size_t length;
 538
 539             s = va_arg (args, char *);
 540             if (s == NULL)
 541               s = "(null)";
 542
 543             if (c.precision >= 0)
 544               {
 545                 const char *zero = memchr (s, '\0', c.precision);
 546                 if (zero != NULL)
 547                   length = zero - s;
 548                 else
 549                   length = c.precision;
 550               }
 551             else
 552               length = strlen (s);
 553
 554             printf_string (s, length, &c, output, aux);
 555           }
 556           break;
 557
 558         case 'p':
 559           {
 560             void *p = va_arg (args, void *);
 561
 562             c.flags = POUND;
 563             if (p != NULL)
 564               printf_integer ((uintptr_t) p,
 565                               false, "0123456789abcdef", &c,
 566                               output, aux);
 567             else
 568               printf_string ("(nil)", 5, &c, output, aux);
 569           }
 570           break;
 571
 572         case 'f':
 573         case 'e':
 574         case 'E':
 575         case 'g':
 576         case 'G':
 577         case 'n':
 578           printf_core ("<<no %%%c in kernel>>", output, aux, *format);
 579           break;
 580
 581         default:
 582           printf_core ("<<no %%%c conversion>>", output, aux, *format);
 583           break;
 584         }
 585     }
 586 }