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 later we
 326      will output the buffer's content in reverse.  This is also
 327      the reason that later we append zeros and the sign. */
 328   cp = buf;
 329   while (value > 0)
 330     {
 331       *cp++ = digits[value % base];
 332       value /= base;
 333     }
 334
 335   /* Append enough zeros to match precision.
 336      If precision is 0, then a value of zero is rendered as a
 337      null string.  Otherwise at least one digit is presented. */
 338   if (c->precision < 0)
 339     c->precision = 1;
 340   while (cp - buf < c->precision && cp - buf < (int) sizeof buf - 8)
 341     *cp++ = '0';
 342
 343   /* Append sign. */
 344   if (c->flags & PLUS)
 345     *cp++ = negative ? '-' : '+';
 346   else if (c->flags & SPACE)
 347     *cp++ = negative ? '-' : ' ';
 348   else if (negative)
 349     *cp++ = '-';
 350
 351   /* Get name of base. */
 352   base_name = "";
 353   if (c->flags & POUND)
 354     {
 355       if (base == 8)
 356         base_name = "0";
 357       else if (base == 16)
 358         base_name = digits[0xa] == 'a' ? "0x" : "0X";
 359     }
 360
 361   /* Calculate number of pad characters to fill field width. */
 362   pad_cnt = c->width - (cp - buf) - strlen (base_name);
 363   if (pad_cnt < 0)
 364     pad_cnt = 0;
 365
 366   /* Do output. */
 367   if ((c->flags & (MINUS | ZERO)) == 0)
 368     output_dup (' ', pad_cnt, output, aux);
 369   while (*base_name != '\0')
 370     output (*base_name++, aux);
 371   if (c->flags & ZERO)
 372     output_dup ('0', pad_cnt, output, aux);
 373   while (cp > buf)
 374     output (*--cp, aux);
 375   if (c->flags & MINUS)
 376     output_dup (' ', pad_cnt, output, aux);
 377 }
 378
 379 static void
 380 printf_string (const char *string, size_t length,
 381                struct printf_conversion *c,
 382                void (*output) (char, void *), void *aux)
 383 {
 384   if (c->width > 1 && (c->flags & MINUS) == 0)
 385     output_dup (' ', c->width - 1, output, aux);
 386   while (length-- > 0)
 387     output (*string++, aux);
 388   if (c->width > 1 && (c->flags & MINUS) != 0)
 389     output_dup (' ', c->width - 1, output, aux);
 390 }
 391
 392 static void
 393 printf_core (const char *format,
 394              void (*output) (char, void *), void *aux, ...)
 395 {
 396   va_list args;
 397
 398   va_start (args, aux);
 399   vprintf_core (format, args, output, aux);
 400   va_end (args);
 401 }
 402
 403 static void
 404 vprintf_core (const char *format, va_list args,
 405               void (*output) (char, void *), void *aux)
 406 {
 407   for (; *format != '\0'; format++)
 408     {
 409       struct printf_conversion c;
 410
 411       /* Literally copy non-conversions to output. */
 412       if (*format != '%')
 413         {
 414           output (*format, aux);
 415           continue;
 416         }
 417       format++;
 418
 419       /* %% => %. */
 420       if (*format == '%')
 421         {
 422           output ('%', aux);
 423           continue;
 424         }
 425
 426       format = parse_conversion (format, &c, &args);
 427       switch (*format)
 428         {
 429         case 'd':
 430         case 'i':
 431           {
 432             intmax_t value;
 433             uintmax_t abs_value;
 434             bool negative = false;
 435
 436             switch (c.type)
 437               {
 438               case CHAR:
 439                 value = (signed char) va_arg (args, int);
 440                 break;
 441               case SHORT:
 442                 value = (short) va_arg (args, int);
 443                 break;
 444               case INT:
 445                 value = va_arg (args, int);
 446                 break;
 447               case LONG:
 448                 value = va_arg (args, long);
 449                 break;
 450               case LONGLONG:
 451                 value = va_arg (args, long long);
 452                 break;
 453               case PTRDIFFT:
 454                 value = va_arg (args, ptrdiff_t);
 455                 break;
 456               case SIZET:
 457                 value = va_arg (args, size_t);
 458                 break;
 459               default:
 460                 NOT_REACHED ();
 461               }
 462
 463             if (value < 0)
 464               {
 465                 negative = true;
 466                 abs_value = -value;
 467               }
 468             else
 469               abs_value = value;
 470
 471             printf_integer (abs_value, negative, "0123456789",
 472                             &c, output, aux);
 473           }
 474           break;
 475
 476         case 'o':
 477         case 'u':
 478         case 'x':
 479         case 'X':
 480           {
 481             uintmax_t value;
 482             const char *digits;
 483
 484             switch (c.type)
 485               {
 486               case CHAR:
 487                 value = (unsigned char) va_arg (args, unsigned);
 488                 break;
 489               case SHORT:
 490                 value = (unsigned short) va_arg (args, unsigned);
 491                 break;
 492               case INT:
 493                 value = va_arg (args, unsigned);
 494                 break;
 495               case LONG:
 496                 value = va_arg (args, unsigned long);
 497                 break;
 498               case LONGLONG:
 499                 value = va_arg (args, unsigned long long);
 500                 break;
 501               case PTRDIFFT:
 502                 value = va_arg (args, ptrdiff_t);
 503                 break;
 504               case SIZET:
 505                 value = va_arg (args, size_t);
 506                 break;
 507               default:
 508                 NOT_REACHED ();
 509               }
 510
 511             switch (*format)
 512               {
 513               case 'o':
 514                 digits = "01234567";
 515                 break;
 516               case 'u':
 517                 digits = "0123456789";
 518                 break;
 519               case 'x':
 520                 digits = "0123456789abcdef";
 521                 break;
 522               case 'X':
 523                 digits = "0123456789ABCDEF";
 524                 break;
 525               default:
 526                 NOT_REACHED ();
 527               }
 528
 529             printf_integer (value, false, digits, &c, output, aux);
 530           }
 531           break;
 532
 533         case 'c':
 534           {
 535             char ch = va_arg (args, int);
 536             printf_string (&ch, 1, &c, output, aux);
 537           }
 538           break;
 539
 540         case 's':
 541           {
 542             const char *s;
 543             size_t length;
 544
 545             s = va_arg (args, char *);
 546             if (s == NULL)
 547               s = "(null)";
 548
 549             if (c.precision >= 0)
 550               {
 551                 const char *zero = memchr (s, '\0', c.precision);
 552                 if (zero != NULL)
 553                   length = zero - s;
 554                 else
 555                   length = c.precision;
 556               }
 557             else
 558               length = strlen (s);
 559
 560             printf_string (s, length, &c, output, aux);
 561           }
 562           break;
 563
 564         case 'p':
 565           {
 566             void *p = va_arg (args, void *);
 567
 568             c.flags = POUND;
 569             if (p != NULL)
 570               printf_integer ((uintptr_t) p,
 571                               false, "0123456789abcdef", &c,
 572                               output, aux);
 573             else
 574               printf_string ("(nil)", 5, &c, output, aux);
 575           }
 576           break;
 577
 578         case 'f':
 579         case 'e':
 580         case 'E':
 581         case 'g':
 582         case 'G':
 583         case 'n':
 584           printf_core ("<<no %%%c in kernel>>", output, aux, *format);
 585           break;
 586
 587         default:
 588           printf_core ("<<no %%%c conversion>>", output, aux, *format);
 589           break;
 590         }
 591     }
 592 }