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