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