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