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 size)
  13 {
  14   unsigned char *dst = dst_;
  15
  16   ASSERT (dst != NULL || size == 0);
  17
  18   while (size-- > 0)
  19     *dst++ = value;
  20
  21   return dst_;
  22 }
  23
  24 void *
  25 memcpy (void *dst_, const void *src_, size_t size)
  26 {
  27   unsigned char *dst = dst_;
  28   const unsigned char *src = src_;
  29
  30   ASSERT (dst != NULL || size == 0);
  31   ASSERT (src != NULL || size == 0);
  32
  33   while (size-- > 0)
  34     *dst++ = *src++;
  35
  36   return dst_;
  37 }
  38
  39 void *
  40 memmove (void *dst_, const void *src_, size_t size)
  41 {
  42   unsigned char *dst = dst_;
  43   const unsigned char *src = src_;
  44
  45   ASSERT (dst != NULL || size == 0);
  46   ASSERT (src != NULL || size == 0);
  47
  48   if (dst < src)
  49     {
  50       while (size-- > 0)
  51         *dst++ = *src++;
  52     }
  53   else
  54     {
  55       dst += size;
  56       src += size;
  57       while (size-- > 0)
  58         *--dst = *--src;
  59     }
  60
  61   return dst;
  62 }
  63
  64 void *
  65 memchr (const void *block_, int ch_, size_t size)
  66 {
  67   const unsigned char *block = block_;
  68   unsigned char ch = ch_;
  69
  70   ASSERT (block != NULL || size == 0);
  71
  72   for (; size-- > 0; block++)
  73     if (*block == ch)
  74       return (void *) block;
  75
  76   return NULL;
  77 }
  78
  79 int
  80 memcmp (const void *a_, const void *b_, size_t size)
  81 {
  82   const unsigned char *a = a_;
  83   const unsigned char *b = b_;
  84
  85   ASSERT (a != NULL || size == 0);
  86   ASSERT (b != NULL || size == 0);
  87
  88   for (; size-- > 0; a++, b++)
  89     if (*a != *b)
  90       return *a > *b ? +1 : -1;
  91   return 0;
  92 }
  93
  94 size_t
  95 strlcpy (char *dst, const char *src, size_t size)
  96 {
  97   size_t src_len;
  98
  99   ASSERT (dst != NULL);
 100   ASSERT (src != NULL);
 101
 102   src_len = strlen (src);
 103   if (size > 0)
 104     {
 105       size_t dst_len_max = size - 1;
 106       size_t dst_len = src_len < dst_len_max ? src_len : dst_len_max;
 107       memcpy (dst, src, dst_len);
 108       dst[dst_len] = '\0';
 109     }
 110   return src_len;
 111 }
 112
 113 size_t
 114 strlen (const char *string)
 115 {
 116   const char *p;
 117
 118   ASSERT (string != NULL);
 119
 120   for (p = string; *p != '\0'; p++)
 121     continue;
 122   return p - string;
 123 }
 124
 125 char *
 126 strchr (const char *string, int c_)
 127 {
 128   char c = c_;
 129
 130   ASSERT (string != NULL);
 131
 132   for (;;)
 133     if (*string == c)
 134       return (char *) string;
 135     else if (*string == '\0')
 136       return NULL;
 137     else
 138       string++;
 139 }
 140
 141 int
 142 strcmp (const char *a_, const char *b_)
 143 {
 144   const unsigned char *a = (const unsigned char *) a_;
 145   const unsigned char *b = (const unsigned char *) b_;
 146
 147   ASSERT (a != NULL);
 148   ASSERT (b != NULL);
 149
 150   while (*a != '\0' && *a == *b)
 151     {
 152       a++;
 153       b++;
 154     }
 155
 156   return *a < *b ? -1 : *a > *b;
 157 }
 158
 159 char *
 160 strtok_r (char *s, const char *delimiters, char **save_ptr)
 161 {
 162   char *token;
 163
 164   ASSERT (delimiters != NULL);
 165   ASSERT (save_ptr != NULL);
 166
 167   /* If S is nonnull, start from it.
 168      If S is null, start from saved position. */
 169   if (s == NULL)
 170     s = *save_ptr;
 171   ASSERT (s != NULL);
 172
 173   /* Skip any DELIMITERS at our current position. */
 174   while (strchr (delimiters, *s) != NULL)
 175     {
 176       /* strchr() will always return nonnull if we're searching
 177          for a null byte, because every string contains a null
 178          byte (at the end). */
 179       if (*s == '\0')
 180         {
 181           *save_ptr = s;
 182           return NULL;
 183         }
 184
 185       s++;
 186     }
 187
 188   /* Skip any non-DELIMITERS up to the end of the string. */
 189   token = s;
 190   while (strchr (delimiters, *s) == NULL)
 191     s++;
 192   if (*s != '\0')
 193     {
 194       *s = '\0';
 195       *save_ptr = s + 1;
 196     }
 197   else
 198     *save_ptr = s;
 199   return token;
 200 }
 201
 202 int
 203 atoi (const char *s)
 204 {
 205   bool negative;
 206   int value;
 207
 208   /* Skip white space. */
 209   while (isspace (*s))
 210     s++;
 211
 212   /* Parse sign. */
 213   negative = false;
 214   if (*s == '+')
 215     s++;
 216   else if (*s == '-')
 217     {
 218       negative = true;
 219       s++;
 220     }
 221
 222   /* Parse digits.  We always initially parse the value as
 223      negative, and then make it positive later, because the
 224      negative range of an int is bigger than the positive range
 225      on a 2's complement system. */
 226   for (value = 0; isdigit (*s); s++)
 227     value = value * 10 - (*s - '0');
 228   if (!negative)
 229     value = -value;
 230
 231   return value;
 232 }
 233 \f
 234 static void
 235 vprintf_core (const char *format, va_list args,
 236               void (*output) (char, void *), void *aux);
 237
 238 static void
 239 vprintk_helper (char ch, void *aux UNUSED)
 240 {
 241   vga_putc (ch);
 242   serial_outb (ch);
 243 }
 244
 245 void
 246 vprintk (const char *format, va_list args)
 247 {
 248   enum intr_level old_level = intr_disable ();
 249   vprintf_core (format, args, vprintk_helper, NULL);
 250   intr_set_level (old_level);
 251 }
 252
 253 void
 254 printk (const char *format, ...)
 255 {
 256   va_list args;
 257
 258   va_start (args, format);
 259   vprintk (format, args);
 260   va_end (args);
 261 }
 262 \f
 263 struct vsnprintf_aux
 264   {
 265     char *p;
 266     int length;
 267     int max_length;
 268   };
 269
 270 static void
 271 vsnprintf_helper (char ch, void *aux_)
 272 {
 273   struct vsnprintf_aux *aux = aux_;
 274
 275   if (aux->length++ < aux->max_length)
 276     *aux->p++ = ch;
 277 }
 278
 279 int
 280 vsnprintf (char *buffer, size_t buf_size,
 281            const char *format, va_list args)
 282 {
 283   struct vsnprintf_aux aux;
 284   aux.p = buffer;
 285   aux.length = 0;
 286   aux.max_length = buf_size > 0 ? buf_size - 1 : 0;
 287
 288   vprintf_core (format, args, vsnprintf_helper, &aux);
 289
 290   if (buf_size > 0)
 291     *aux.p = '\0';
 292
 293   return aux.length;
 294 }
 295
 296 int
 297 snprintf (char *buffer, size_t buf_size,
 298           const char *format, ...)
 299 {
 300   va_list args;
 301   int retval;
 302
 303   va_start (args, format);
 304   retval = vsnprintf (buffer, buf_size, format, args);
 305   va_end (args);
 306
 307   return retval;
 308 }
 309 \f
 310 /* printf() and friends internals.  You do not need to understand
 311    this code. */
 312
 313 struct printf_conversion
 314   {
 315     enum
 316       {
 317         MINUS = 1 << 0,
 318         PLUS = 1 << 1,
 319         SPACE = 1 << 2,
 320         POUND = 1 << 3,
 321         ZERO = 1 << 4,
 322         GROUP = 1 << 5
 323       }
 324     flags;
 325
 326     int width;
 327     int precision;
 328
 329     enum
 330       {
 331         CHAR = 1,
 332         SHORT = 2,
 333         INT = 3,
 334         INTMAX = 4,
 335         LONG = 5,
 336         LONGLONG = 6,
 337         PTRDIFFT = 7,
 338         SIZET = 8
 339       }
 340     type;
 341   };
 342
 343 static const char *
 344 parse_conversion (const char *format, struct printf_conversion *c,
 345                   va_list *args)
 346 {
 347   /* Parse flag characters. */
 348   c->flags = 0;
 349   for (;;)
 350     {
 351       switch (*format++)
 352         {
 353         case '-':
 354           c->flags |= MINUS;
 355           break;
 356         case '+':
 357           c->flags |= PLUS;
 358           break;
 359         case ' ':
 360           c->flags |= SPACE;
 361           break;
 362         case '#':
 363           c->flags |= POUND;
 364           break;
 365         case '0':
 366           c->flags |= ZERO;
 367           break;
 368         case '\'':
 369           c->flags |= GROUP;
 370           break;
 371         default:
 372           format--;
 373           goto not_a_flag;
 374         }
 375     }
 376  not_a_flag:
 377   if (c->flags & MINUS)
 378     c->flags &= ~ZERO;
 379   if (c->flags & PLUS)
 380     c->flags &= ~SPACE;
 381
 382   /* Parse field width. */
 383   c->width = 0;
 384   if (*format == '*')
 385     {
 386       format++;
 387       c->width = va_arg (*args, int);
 388     }
 389   else
 390     {
 391       for (; isdigit (*format); format++)
 392         c->width = c->width * 10 + *format - '0';
 393     }
 394   if (c->width < 0)
 395     {
 396       c->width = -c->width;
 397       c->flags |= MINUS;
 398     }
 399
 400   /* Parse precision. */
 401   c->precision = -1;
 402   if (*format == '.')
 403     {
 404       format++;
 405       if (*format == '*')
 406         {
 407           format++;
 408           c->precision = va_arg (*args, int);
 409         }
 410       else
 411         {
 412           c->precision = 0;
 413           for (; isdigit (*format); format++)
 414             c->precision = c->precision * 10 + *format - '0';
 415         }
 416       if (c->precision < 0)
 417         c->precision = -1;
 418     }
 419   if (c->precision >= 0)
 420     c->flags &= ~ZERO;
 421
 422   /* Parse type. */
 423   c->type = INT;
 424   switch (*format++)
 425     {
 426     case 'h':
 427       if (*format == 'h')
 428         {
 429           format++;
 430           c->type = CHAR;
 431         }
 432       else
 433         c->type = SHORT;
 434       break;
 435
 436     case 'j':
 437       c->type = INTMAX;
 438       break;
 439
 440     case 'l':
 441       if (*format == 'l')
 442         {
 443           format++;
 444           c->type = LONGLONG;
 445         }
 446       else
 447         c->type = LONG;
 448       break;
 449
 450     case 'L':
 451     case 'q':
 452       c->type = LONGLONG;
 453       break;
 454
 455     case 't':
 456       c->type = PTRDIFFT;
 457       break;
 458
 459     case 'z':
 460     case 'Z':
 461       c->type = SIZET;
 462       break;
 463
 464     default:
 465       format--;
 466       break;
 467     }
 468
 469   return format;
 470 }
 471
 472 static void
 473 output_dup (char ch, size_t cnt, void (*output) (char, void *), void *aux)
 474 {
 475   while (cnt-- > 0)
 476     output (ch, aux);
 477 }
 478
 479 static void
 480 printf_integer (uintmax_t value, bool negative, const char *digits,
 481                 struct printf_conversion *c,
 482                 void (*output) (char, void *), void *aux)
 483
 484 {
 485   char buf[64], *cp;
 486   int base;
 487   const char *base_name;
 488   int pad_cnt, group_cnt;
 489
 490   base = strlen (digits);
 491
 492   /* Accumulate digits into buffer.
 493      This algorithm produces digits in reverse order, so later we
 494      will output the buffer's content in reverse.  This is also
 495      the reason that later we append zeros and the sign. */
 496   cp = buf;
 497   group_cnt = 0;
 498   while (value > 0)
 499     {
 500       if ((c->flags & GROUP) && group_cnt++ == 3)
 501         {
 502           *cp++ = ',';
 503           group_cnt = 0;
 504         }
 505       *cp++ = digits[value % base];
 506       value /= base;
 507     }
 508
 509   /* Append enough zeros to match precision.
 510      If precision is 0, then a value of zero is rendered as a
 511      null string.  Otherwise at least one digit is presented. */
 512   if (c->precision < 0)
 513     c->precision = 1;
 514   while (cp - buf < c->precision && cp - buf < (int) sizeof buf - 8)
 515     *cp++ = '0';
 516
 517   /* Append sign. */
 518   if (c->flags & PLUS)
 519     *cp++ = negative ? '-' : '+';
 520   else if (c->flags & SPACE)
 521     *cp++ = negative ? '-' : ' ';
 522   else if (negative)
 523     *cp++ = '-';
 524
 525   /* Get name of base. */
 526   base_name = "";
 527   if (c->flags & POUND)
 528     {
 529       if (base == 8)
 530         base_name = "0";
 531       else if (base == 16)
 532         base_name = digits[0xa] == 'a' ? "0x" : "0X";
 533     }
 534
 535   /* Calculate number of pad characters to fill field width. */
 536   pad_cnt = c->width - (cp - buf) - strlen (base_name);
 537   if (pad_cnt < 0)
 538     pad_cnt = 0;
 539
 540   /* Do output. */
 541   if ((c->flags & (MINUS | ZERO)) == 0)
 542     output_dup (' ', pad_cnt, output, aux);
 543   while (*base_name != '\0')
 544     output (*base_name++, aux);
 545   if (c->flags & ZERO)
 546     output_dup ('0', pad_cnt, output, aux);
 547   while (cp > buf)
 548     output (*--cp, aux);
 549   if (c->flags & MINUS)
 550     output_dup (' ', pad_cnt, output, aux);
 551 }
 552
 553 static void
 554 printf_string (const char *string, size_t length,
 555                struct printf_conversion *c,
 556                void (*output) (char, void *), void *aux)
 557 {
 558   if (c->width > 1 && (c->flags & MINUS) == 0)
 559     output_dup (' ', c->width - 1, output, aux);
 560   while (length-- > 0)
 561     output (*string++, aux);
 562   if (c->width > 1 && (c->flags & MINUS) != 0)
 563     output_dup (' ', c->width - 1, output, aux);
 564 }
 565
 566 static void
 567 printf_core (const char *format,
 568              void (*output) (char, void *), void *aux, ...)
 569 {
 570   va_list args;
 571
 572   va_start (args, aux);
 573   vprintf_core (format, args, output, aux);
 574   va_end (args);
 575 }
 576
 577 static void
 578 vprintf_core (const char *format, va_list args,
 579               void (*output) (char, void *), void *aux)
 580 {
 581   for (; *format != '\0'; format++)
 582     {
 583       struct printf_conversion c;
 584
 585       /* Literally copy non-conversions to output. */
 586       if (*format != '%')
 587         {
 588           output (*format, aux);
 589           continue;
 590         }
 591       format++;
 592
 593       /* %% => %. */
 594       if (*format == '%')
 595         {
 596           output ('%', aux);
 597           continue;
 598         }
 599
 600       format = parse_conversion (format, &c, &args);
 601       switch (*format)
 602         {
 603         case 'd':
 604         case 'i':
 605           {
 606             intmax_t value;
 607             uintmax_t abs_value;
 608             bool negative = false;
 609
 610             switch (c.type)
 611               {
 612               case CHAR:
 613                 value = (signed char) va_arg (args, int);
 614                 break;
 615               case SHORT:
 616                 value = (short) va_arg (args, int);
 617                 break;
 618               case INT:
 619                 value = va_arg (args, int);
 620                 break;
 621               case LONG:
 622                 value = va_arg (args, long);
 623                 break;
 624               case LONGLONG:
 625                 value = va_arg (args, long long);
 626                 break;
 627               case PTRDIFFT:
 628                 value = va_arg (args, ptrdiff_t);
 629                 break;
 630               case SIZET:
 631                 value = va_arg (args, size_t);
 632                 break;
 633               default:
 634                 NOT_REACHED ();
 635               }
 636
 637             if (value < 0)
 638               {
 639                 negative = true;
 640                 abs_value = -value;
 641               }
 642             else
 643               abs_value = value;
 644
 645             printf_integer (abs_value, negative, "0123456789",
 646                             &c, output, aux);
 647           }
 648           break;
 649
 650         case 'o':
 651         case 'u':
 652         case 'x':
 653         case 'X':
 654           {
 655             uintmax_t value;
 656             const char *digits;
 657
 658             switch (c.type)
 659               {
 660               case CHAR:
 661                 value = (unsigned char) va_arg (args, unsigned);
 662                 break;
 663               case SHORT:
 664                 value = (unsigned short) va_arg (args, unsigned);
 665                 break;
 666               case INT:
 667                 value = va_arg (args, unsigned);
 668                 break;
 669               case LONG:
 670                 value = va_arg (args, unsigned long);
 671                 break;
 672               case LONGLONG:
 673                 value = va_arg (args, unsigned long long);
 674                 break;
 675               case PTRDIFFT:
 676                 value = va_arg (args, ptrdiff_t);
 677                 break;
 678               case SIZET:
 679                 value = va_arg (args, size_t);
 680                 break;
 681               default:
 682                 NOT_REACHED ();
 683               }
 684
 685             switch (*format)
 686               {
 687               case 'o':
 688                 digits = "01234567";
 689                 break;
 690               case 'u':
 691                 digits = "0123456789";
 692                 break;
 693               case 'x':
 694                 digits = "0123456789abcdef";
 695                 break;
 696               case 'X':
 697                 digits = "0123456789ABCDEF";
 698                 break;
 699               default:
 700                 NOT_REACHED ();
 701               }
 702
 703             printf_integer (value, false, digits, &c, output, aux);
 704           }
 705           break;
 706
 707         case 'c':
 708           {
 709             char ch = va_arg (args, int);
 710             printf_string (&ch, 1, &c, output, aux);
 711           }
 712           break;
 713
 714         case 's':
 715           {
 716             const char *s;
 717             size_t length;
 718
 719             s = va_arg (args, char *);
 720             if (s == NULL)
 721               s = "(null)";
 722
 723             if (c.precision >= 0)
 724               {
 725                 const char *zero = memchr (s, '\0', c.precision);
 726                 if (zero != NULL)
 727                   length = zero - s;
 728                 else
 729                   length = c.precision;
 730               }
 731             else
 732               length = strlen (s);
 733
 734             printf_string (s, length, &c, output, aux);
 735           }
 736           break;
 737
 738         case 'p':
 739           {
 740             void *p = va_arg (args, void *);
 741
 742             c.flags = POUND;
 743             if (p != NULL)
 744               printf_integer ((uintptr_t) p,
 745                               false, "0123456789abcdef", &c,
 746                               output, aux);
 747             else
 748               printf_string ("(nil)", 5, &c, output, aux);
 749           }
 750           break;
 751
 752         case 'f':
 753         case 'e':
 754         case 'E':
 755         case 'g':
 756         case 'G':
 757         case 'n':
 758           printf_core ("<<no %%%c in kernel>>", output, aux, *format);
 759           break;
 760
 761         default:
 762           printf_core ("<<no %%%c conversion>>", output, aux, *format);
 763           break;
 764         }
 765     }
 766 }
 767 \f
 768 void
 769 hex_dump (const void *buffer, size_t size, bool ascii)
 770 {
 771   const size_t n_per_line = 16;
 772   const uint8_t *p = buffer;
 773   size_t ofs = 0;
 774
 775   while (size > 0)
 776     {
 777       size_t n, i;
 778
 779       printk ("%08zx", ofs);
 780       n = size >= n_per_line ? n_per_line : size;
 781       for (i = 0; i < n; i++)
 782         printk ("%c%02x", i == n_per_line / 2 ? '-' : ' ', (unsigned) p[i]);
 783
 784       if (ascii)
 785         {
 786           for (; i < n_per_line; i++)
 787             printk ("   ");
 788           printk (" |");
 789           for (i = 0; i < n; i++)
 790             printk ("%c", isprint (p[i]) ? p[i] : '.');
 791           for (; i < n_per_line; i++)
 792             printk (" ");
 793           printk ("|");
 794         }
 795       printk ("\n");
 796
 797       p += n;
 798       ofs += n;
 799       size -= n;
 800     }
 801 }