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