/* Implementation of vsnprintf written by Evan Danaher for CMU 15-410.
 *
 * Based off of the Linux printf(3) man page.  Notably:
 *    - returns the length of the string without truncation, but only puts the
 *      first size characters into the buffer.
 *    - Supports #, 0, -, space, and '+' flags.
 *    - Supports fixed field width, including those specified by '*':
 *          printf("%0*d", 5, -20) -> -0020
 *    - Supports precision to limit string lengths:
 *          printf("%.3s", "test") -> tes
 *    - Supports length modifiers hh, h, l, ll, z
 *    - Supports d, i, o, u, x, X, c, s, p type specifiers.  Does not support
 *      floating point at all.
 */
 

#include <stdio.h>
#include <stdarg.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
   char type;        /* What type it is */
   char sign_char;   /* 0 if no forced padding, otherwise the type */
   char pad_char;    /* Char to pad with - %0d */
   int bytes;        /* How many bytes the output is for ints - h/l */
   int len;          /* Length of output string */
   int pad_len;      /* Length to pad the output to - %5d */
   int pad_start;    /* Where to pad starting from - 0x00045, -0004 */
   int alternate;    /* Alternate output format: %#x -> 0x4 */
   int precision;    /* Used for capping string length */
} printf_spec;

/* Reset a spec to the defaults */
void reset_spec(printf_spec *spec) {
   spec->sign_char = 0;
   spec->pad_char = ' ';
   spec->bytes = 4;
   spec->len = 0;
   spec->pad_len = 0;
   spec->pad_start = 0;
   spec->alternate = 0;
   spec->precision = 0;
}

/* Check for a signed type spec */
int is_signed_type(char tp) {
   return tp == 'i' || tp == 'd';
}

/* Read a len, either the format string or the arg list */
int read_len(const char **formatp, va_list ap) {
   int res = 0;
   const char *format = *formatp;

   if(*format == '*') {
      format++;
      res = va_arg(ap, int);
   } else
      while('0' <= *format && *format <= '9') {
         res = 10 * res + *format - '0';
         format++;
      }

   *formatp = format;
   return res;
}

/* Parse a specification */
int parse_spec(const char **formatp, printf_spec *spec, va_list ap) {
   const char *format = *formatp;
   const char flags[] = "0-# +";
   const char spec_types[] = "diuopxXcs";

   reset_spec(spec);

   format++;

   /* Look for flags */
   while(strchr(flags, *format)) {
      switch(*format) {
         case '0':
            spec->pad_char = '0';
            spec->pad_start = 0;
            break;
         case '-':
            spec->pad_char = ' ';
            spec->pad_start = -1;
            break;
         case '#':
            spec->alternate = 1;
            break;
         case ' ':
            spec->sign_char = ' ';
            break;
         case '+':
            spec->sign_char = '+';
            break;
      }
      format++;
   }

   /* Read a length spec */
   spec->pad_len = read_len(&format, ap);

   /* Read a precision spec (used for limiting string length) */
   if(*format == '.') {
      format++;
      spec->precision = read_len(&format, ap);
   }

   /* Read a length modifier (h/l/z) */
   if(*format == 'h') {
      if(format[1] == 'h') {
         spec->bytes = sizeof(char);
         format += 2;
      } else {
         spec->bytes = sizeof(short);
         format++;
      }
   } else if(*format == 'l') {
      if(format[1] == 'l') {
         spec->bytes = sizeof(long long);
         format += 2;
      } else {
         spec->bytes = sizeof(long);
         format++;
      }
   } else if(*format == 'z') {
      spec->bytes = sizeof(size_t);
      format++;
   }

   /* Read the actual spec type */
   if(strchr(spec_types, *format)) {
      spec->type = *format++;
      *formatp = format;
      return 0;
   }

   /* No spec type - return failure */
   return 1;
}

/* Write a number to a string with some modifiers from the spec */
void int_to_string(char *buffer, printf_spec *spec, unsigned long long n) {
   const char digits[] = "0123456789ABCDEF";
   int len, i;
   unsigned long long n2;
   int prefix_len = 0;
   int base, lowercase = 0;

   switch(spec->type) {
      case 'u':
      case 'd':
      case 'i':
         base = 10;
         break;
      case 'o':
         base = 8;
         break;
      case 'x':
         lowercase = 1;
         /* fall through */
      case 'X':
         base = 16;
         break;
   }

   /* Truncate to the right size */
   if(spec->bytes != sizeof(long long))
      n &= (1LL << (spec->bytes * 8)) - 1;

   /* Check for negative */
   if(n >= 1LL << (spec->bytes * 8 - 1) && is_signed_type(spec->type))  {
      buffer[0] = '-';
      buffer++;
      prefix_len++;
      n = (1LL << spec->bytes * 8) - n;
   } else if(spec->sign_char) {
      /* Positive, but + or _ forces a sign character */
      buffer[0] = spec->sign_char;
      buffer++;
      prefix_len++;
   }

   /* Add alternates: a leading 0 for octal or 0x for hex */
   if(spec->alternate && spec->type == 'o' && n) {
      buffer[0] = '0';
      buffer++;
      prefix_len++;
   }
   if(spec->alternate && spec->type == 'x' && n) {
      buffer[0] = '0';
      buffer[1] = 'x';
      buffer += 2;
      prefix_len += 2;
   }

   /* Write out the number itself */
   for(len = 0, n2 = n; n2 > 0; len++)
      n2 /= base;
   if(n) { /* Nonzero */
      for(i = 0; i < len; i++) {
         buffer[len - i - 1] = digits[n % base] | (lowercase ? 0x20 : 0);
         n /= base;
      }
   } else if(spec->alternate != 2) { /* Zero for non-pointers */
      buffer[0] = '0';
      buffer[1] = 0;
      len = 1;
   } else { /* null pointer */
      strcpy(buffer, "(nil)");
      len = strlen("(nil)");
   }

   buffer[len + prefix_len] = 0;
   if(spec->pad_char == '0')
      spec->pad_start += prefix_len;
   spec->len = len + prefix_len;
}

/* Add a single character to the output if there's space and update len */
void add_char(char *out, int *len, char in, int size) {
   if(*len < size - 1)
      out[*len] = in;
   (*len)++;
}

/* Add a string to the output if there's space and update len */
void add_string(char *out, int *len, char* in, int in_len, int size) {
   if(*len + in_len < size - 1)
      memcpy(out + *len, in, in_len);
   else if(*len < size - 1)
      memcpy(out + *len, in, size - 1 - *len);

   *len += in_len;
}

int my_vsnprintf(char *str, size_t size, const char *format, va_list ap) {
   int len = 0;
   printf_spec spec;
   char *cpybuf;
   int i;
   /* Use a buffer to store the string version of the number, in case there
    * isn't space left in the user buffer.  The longest value in here should be
    * 2^64 - 1 plus a leading + or space, which is 21 characters, so 24 should
    * be plenty. */
   char buffer[24];

   while(*format) {
      /* Literals */
      if(format[0] != '%') {
         add_char(str, &len, format[0], size);
         format++;
         continue;
      }

      /* Literal '%' */
      if(format[1] == '%') {
         add_char(str, &len, '%', size);
         format += 2;
         continue;
      }

      /* Try to parse a spec string */
      if(parse_spec(&format, &spec, ap)) {
         /* Failed - just output the literal characters */
         add_char(str, &len, format[0], size);
         format++;
         continue;
      }

      cpybuf = buffer;
      switch(spec.type) {
         case 'p': /* Pointers are just special hex */
            spec.type = 'x';
            spec.alternate = 2;
            spec.bytes = sizeof(void *);
         case 'i':
         case 'd':
         case 'u':
         case 'o':
         case 'x':
         case 'X':
            /* Apparently anything int or shorter is an int in va_arg... */
            if(spec.bytes <= sizeof(int))
               int_to_string(buffer, &spec, va_arg(ap, int));
            else
               int_to_string(buffer, &spec, va_arg(ap, long long));
            break;
         case 'c':
            buffer[0] = (char)va_arg(ap, int);
            spec.len = 1;
            break;
         case 's':
            cpybuf = va_arg(ap, char *);
            if(spec.precision)
               for(spec.len = 0;
                   spec.len < spec.precision && cpybuf[spec.len];
                   spec.len++);
            else
               spec.len = strlen(cpybuf);
            break;
         default:
            /* THIS SHOULD NOT HAPPEN - spec.type was set in parse_spec, and
             * must be one of the values checke for. */
            exit(1);
      }

      /* If right padding, it's really at the end */
      if(spec.pad_start == -1)
         spec.pad_start = spec.len;

      /* Add output before padding */
      add_string(str, &len, cpybuf, spec.pad_start, size);
      /* Add padding */
      if(spec.pad_len > spec.len)
         for(i = 0; i < spec.pad_len - spec.len; i++)
            add_char(str, &len, spec.pad_char, size);
      /* Add output after padding */
      add_string(str, &len, cpybuf + spec.pad_start, spec.len - spec.pad_start, size);
   }

   /* Null terminate the string */
   if(len < size)
      str[len] = 0;
   else
      str[size - 1] = 0;
   return len;
}

int my_snprintf(char *str, size_t size, const char *format, ...) {
   va_list ap;
   int ret;
   
   va_start(ap, format);
   ret = my_vsnprintf(str, size, format, ap);
   va_end(ap);

   return ret;
}

int main() {
   char out[1000];
   int ret;

   ret = my_snprintf(out, 1000, "This is a test, %X%% correct - it gets %4i/%06d -> %u -> %o -> %c%c.  %6s %-8s - %#x %#07x %-#8o, %hhd.  % d % 05d %+05d %-8.4s %p %08p %p %d %x %0*d .%*.*s. %+d %+d % d % d %+05d %-5d. % bsdf", 256 + 12*16 + 11, 4, -505, -505, -505, 65, -455, "hi", "there", -84, 43, 84, 513, 10, 40, 50, "String", (void *)0, (void *)0x1243, (void *)0x1243, 0, 0, 5, -23, 5, 2, "MAGIC", 34, -45, 34, -45, 45, 4);
   printf("%d: %s\n", ret, out);

   ret = snprintf(out, 1000, "This is a test, %X%% correct - it gets %4i/%06d -> %u -> %o -> %c%c.  %6s %-8s - %#x %#07x %-#8o, %hhd.  % d % 05d %+05d %-8.4s %p %08p %p %d %x %0*d .%*.*s. %+d %+d % d % d %+05d %-5d. % bsdf", 256 + 12*16 + 11, 4, -505, -505, -505, 65, -455, "hi", "there", -84, 43, 84, 513, 10, 40, 50, "String", (void *)0, (void *)0x1243, (void *)0x1243, 0, 0, 5, -23, 5, 2, "MAGIC", 34, -45, 34, -45, 45, 4);
   printf("%d: %s\n", ret, out);
   return 0;
}