2 files changed, 158 insertions, 65 deletions

diff --git a/utils/static_utoa.h b/utils/static_utoa.h
index 3af9fbb6..d15ed35b 100755
--- a/utils/static_utoa.h
+++ b/utils/static_utoa.h
@@ -5,35 +5,19 @@
 #include "utoa.h"
 
 namespace {
+static const int utoa_bufsize=40; // 64bit safe.
+static const int utoa_bufsizem1=utoa_bufsize-1; // 64bit safe.
 THREADLOCAL char utoa_buf[utoa_bufsize]; // to put end of string character at buf[20]
 }
 
 inline char *static_utoa(unsigned n) {
+  assert(utoa_buf[utoa_bufsizem1]==0);
   return utoa(utoa_buf+utoa_bufsizem1,n);
 }
 
 inline char *static_itoa(int n) {
+  assert(utoa_buf[utoa_bufsizem1]==0);
   return itoa(utoa_buf+utoa_bufsizem1,n);
 }
 
-#ifdef ITOA_SAMPLE
-# include <cstdio>
-# include <sstream>
-# include <iostream>
-using namespace std;
-
-int main(int argc,char *argv[]) {
-  printf("d U d U d U\n");
-  for (int i=1;i<argc;++i) {
-    int n;
-    unsigned un;
-    sscanf(argv[i],"%d",&n);
-    sscanf(argv[i],"%u",&un);
-    printf("%d %u %s",n,un,static_itoa(n));
-    printf(" %s %s %s\n",static_utoa(un),itos(n).c_str(),utos(un).c_str());
-  }
-  return 0;
-}
-#endif
-
 #endif
diff --git a/utils/utoa.h b/utils/utoa.h
index 8d304f97..341965cc 100755
--- a/utils/utoa.h
+++ b/utils/utoa.h
@@ -1,19 +1,61 @@
 #ifndef UTOA_H
 #define UTOA_H
 
+
 #include <stdint.h>
 #include <string>
 #include <cstring>
+#include <limits>
 
+// define this if you're paranoid about converting 0-9 (int) to 0-9 (char) by adding to '0', which is safe for ascii, utf8, etc.
 #ifndef DIGIT_LOOKUP_TABLE
 # define DIGIT_LOOKUP_TABLE 0
 #endif
 
+//TODO: 3 decimal digit lookup table, divide by 1000 faster?
+//TODO: benchmark these two (also, some assembly that does effectively divmod?)
+#if 1
+// maybe this is faster than mod because we are already dividing
+#define NDIV10MOD(rem,n) rem = n; n /= 10; rem -= 10*n;
+#else
+// or maybe optimizer does it just as well or better with this:
+#define NDIV10MOD(rem,n) rem = n%10; n = n/10;
+#endif
+
+template <class T>
+struct signed_for_int {
+};
+
+
+#define DEFINE_SIGNED_FOR_3(t,it,ut)          \
+template <> \
+struct signed_for_int<t> { \
+  typedef ut unsigned_t; \
+  typedef it signed_t; \
+  typedef t original_t; \
+  enum { toa_bufsize = 3 + std::numeric_limits<t>::digits10, toa_bufsize_minus_1=toa_bufsize-1 }; \
+};
+
+// toa_bufsize will hold enough chars for a c string converting to sign,digits (for both signed and unsigned types), because normally an unsigned would only need 2 extra chars.  we reserve 3 explicitly for the case that itoa(buf,UINT_MAX,true) is called, with output +4......
+
+#define DEFINE_SIGNED_FOR(it) DEFINE_SIGNED_FOR_3(it,it,u ## it)    \
+  DEFINE_SIGNED_FOR_3(u ## it,it,u ## it)
+
+DEFINE_SIGNED_FOR(int8_t)
+DEFINE_SIGNED_FOR(int16_t)
+DEFINE_SIGNED_FOR(int32_t)
+DEFINE_SIGNED_FOR(int64_t)
+//DEFINE_SIGNED_FOR_3(int,int,unsigned)
+//DEFINE_SIGNED_FOR_3(unsigned,int,unsigned)
+
+/*
 // The largest 32-bit integer is 4294967295, that is 10 chars
 // 1 more for sign, and 1 for 0-termination of string
-// generally: 2 + std::numeric_limits<T>::is_signed + std::numeric_limits<T>::digits10
 const unsigned utoa_bufsize=12;
 const unsigned utoa_bufsizem1=utoa_bufsize-1;
+const unsigned ultoa_bufsize=22;
+const unsigned ultoa_bufsizem1=utoa_bufsize-1;
+*/
 
 #ifdef DIGIT_LOOKUP_TABLE
 namespace {
@@ -30,72 +72,139 @@ inline char digit_to_char(int d) {
 #endif
 }
 
-// returns n in string [return,num); *num=0 yourself before calling if you want a c_str
-inline char *utoa(char *num,uint32_t n) {
-  if ( !n ) {
-    *--num='0';
+
+// returns n in string [return,num); *num=0 yourself before calling if you want a c_str.  in other words, the sequence [ret,buf) contains the written digits
+template <class Int>
+char *utoa(char *buf,Int n_) {
+  typedef typename signed_for_int<Int>::unsigned_t Uint;
+  Uint n=n_;
+  if (!n) {
+    *--buf='0';
   } else {
-    uint32_t rem;
+    Uint rem;
     // 3digit lookup table, divide by 1000 faster?
-    while ( n ) {
-#if 1
-      rem = n;
-      n /= 10;
-      rem -= 10*n;		// maybe this is faster than mod because we are already dividing
-#else
-      rem = n%10; // would optimizer combine these together?
-      n   = n/10;
-#endif
-      *--num = digit_to_char(rem);
+    while (n) {
+      NDIV10MOD(rem,n);
+      *--buf = digit_to_char(rem);
     }
   }
-  return num;
+  return buf;
 }
 
-inline char *itoa(char *p,int32_t n) {
-  if (n<0) {
-    p=utoa(p,-n); // (unsigned)(-INT_MIN) == 0x1000000 in 2s complement and not == 0.
-    *--p='-';
-    return p;
-  } else
-    return utoa(p,n);
+// left_pad_0(buf,utoa(buf+bufsz,n)) means that [buf,buf+bufsz) is a left-0 padded seq. of digits.  no 0s are added if utoa is already past buf (you must have ensured that this is valid memory, naturally)
+inline void left_pad(char *left,char *buf,char pad='0') {
+  while (buf>left)
+    *--buf=pad;
+  // return buf;
 }
 
-inline std::string utos(uint32_t n) {
-  char buf[utoa_bufsize];
-  char *end=buf+utoa_bufsize;
-  char *p=utoa(end,n);
+template <class Int>
+char *utoa_left_pad(char *buf,char *bufend,Int n, char pad='0') {
+  char *r=utoa(bufend,n);
+  assert(buf<=r);
+  left_pad(buf,r,pad);
+  return buf;
+}
+
+// note: 0 -> 0, but otherwise x000000 -> x (x has no trailing 0s).  same conditions as utoa; [ret,buf) gives the sequence of digits
+// useful for floating point fraction output
+template <class Uint_>
+char *utoa_drop_trailing_0(char *buf,Uint_ n_, unsigned &n_skipped) {
+  typedef typename signed_for_int<Uint_>::unsigned_t Uint;
+  Uint n=n_;
+  n_skipped=0;
+  if (!n) {
+    *--buf='0';
+    return buf;
+  } else {
+    Uint rem;
+    while (n) {
+      NDIV10MOD(rem,n);
+      if (rem) {
+        *--buf = digit_to_char(rem);
+        // some non-0 trailing digits; now output all digits.
+        while (n) {
+          NDIV10MOD(rem,n);
+          *--buf = digit_to_char(rem);
+        }
+        return buf;
+      }
+      ++n_skipped;
+    }
+    assert(0);
+    return 0;
+  }
+}
+
+// desired feature: itoa(unsigned) = utoa(unsigned)
+// positive sign: 0 -> +0, 1-> +1.  obviously -n -> -n
+template <class Int>
+//typename signed_for_int<Int>::original_t instead of Int to give more informative wrong-type message?
+char *itoa(char *buf,Int i,bool positive_sign=false) {
+  typename signed_for_int<Int>::unsigned_t n=i;
+  if (i<0)
+    n=-n; //sidesteps 2s complement issue doing this rather than just u=-n.
+  char * ret=utoa(buf,n);
+  if (i<0) {
+    *--ret='-';
+  } else if (positive_sign)
+    *--ret='+';
+  return ret;
+}
+
+template <class Int>
+char * itoa_left_pad(char *buf,char *bufend,Int i,bool positive_sign=false,char pad='0') {
+  typename signed_for_int<Int>::unsigned_t n=i;
+  if (i<0) {
+    n=-n; //sidesteps 2s complement issue doing this rather than just u=-n.
+    *buf='-';
+  } else if (positive_sign)
+    *buf='+';
+  char * r=utoa(bufend,n);
+  assert(buf<r);
+  left_pad(buf+1,r,pad);
+  return buf;
+}
+
+template <class Int>
+inline std::string itos(Int n) {
+  char buf[signed_for_int<Int>::toa_bufsize];
+  char *end=buf+signed_for_int<Int>::toa_bufsize;
+  char *p=itoa(end,n);
   return std::string(p,end);
 }
 
-inline std::string itos(int32_t n) {
-  char buf[utoa_bufsize];
-  char *end=buf+utoa_bufsize;
+template <class Int>
+inline std::string utos(Int n) {
+  char buf[signed_for_int<Int>::toa_bufsize];
+  char *end=buf+signed_for_int<Int>::toa_bufsize;
   char *p=itoa(end,n);
   return std::string(p,end);
 }
 
 //returns position of '\0' terminating number written starting at to
-inline char* append_utoa(char *to,uint32_t n) {
-  char buf[utoa_bufsize];
-  char *end=buf+utoa_bufsize;
-  char *s=utoa(end,n);
-  int ns=end-s;
-  std::memcpy(to,s,ns);
+template <class Int>
+inline char* append_utoa(char *to,typename signed_for_int<Int>::unsigned_t n) {
+  char buf[signed_for_int<Int>::toa_bufsize];
+  char *end=buf+signed_for_int<Int>::toa_bufsize;
+  char *p=itoa(end,n);
+  int ns=end-p;
+  std::memcpy(to,p,ns);
   to+=ns;
-  *to++=0;
+  *to=0;
   return to;
 }
 
 //returns position of '\0' terminating number written starting at to
-inline char* append_itoa(char *to,int32_t n) {
-  char buf[utoa_bufsize];
-  char *end=buf+utoa_bufsize;
-  char *s=itoa(end,n);
-  int ns=end-s;
-  std::memcpy(to,s,ns);
+template <class Int>
+inline char* append_itoa(char *to,typename signed_for_int<Int>::signed_t n) {
+  char buf[signed_for_int<Int>::toa_bufsize];
+  char *end=buf+signed_for_int<Int>::toa_bufsize;
+  char *p=utoa(end,n);
+  int ns=end-p;
+  std::memcpy(to,p,ns);
   to+=ns;
-  *to++=0;
+  *to=0;
   return to;
 }