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