/*
  basen.c - Convert numbers between bases.

  Jason Hood, 18 & 19 October, 2003 (originally 8 April, 1997).
  Public Domain.

  v2.00, 6 to 14 May, 2010:
  - fixed 32-bit binary numbers (wrote NUL wrong in numtostr);
  * increase to base 64;
  * use 64 bits, if available;
  * allow 100 decimals;
  + recognise repeated decimals;
  + allow display of a minimum number of digits before the point;
  * only use the local point;
  - indicate if a large fraction was approximated.
*/

#define PVERS "2.00"
#define PDATE "14 May, 2010"


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <limits.h>

#ifdef __DJGPP__
#include <dpmi.h>
#include <go32.h>
#include <sys/farptr.h>
void   __crt0_load_environment_file( char* dummy ) { }
char** __crt0_glob_function( char* dummy ) { return 0; }

#elif defined(_WIN32)
#define WIN32_LEAN_AND_MEAN
#include <windows.h>
# ifdef __MINGW32__
int _CRT_glob = 0;
# endif

#else
#include <dos.h>
#endif

#ifndef min
#define min( a, b ) ((a) <= (b) ? (a) : (b))
#endif


#ifdef ULLONG_MAX
typedef unsigned long long TULONG;
#define TULONG_MAX ULLONG_MAX
#else
typedef unsigned long TULONG;
#define TULONG_MAX ULONG_MAX
#endif

#define DIGITS	 (sizeof(TULONG) * CHAR_BIT)	// number of bits for binary
#define DECIMALS 100				// max. digits after the point
#define MAXNUMSTR (1 + DIGITS*2 + DECIMALS*2)	// ~1_2_3....1_2_3.4...
#define MINBASE   2
#define MAXBASE  64

const char digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
		      "abcdefghijklmnopqrstuvwxyz@$";

int    numeral[1 << CHAR_BIT];	// character to digit


char   point = '.';             // separator between integer and fraction
int    minimum[MAXBASE+1];	// number of digits before the decimal
int    places = 9;		// number of digits after the decimal
int    before, after;		// grouping before and after the decimal
int    fraction;		// vulgar fraction was given
TULONG whole, numer, denom;	// number to convert
int    rem_count;		// detect repeating decimals
TULONG rem_buf[DECIMALS];
char*  rem_pos[DECIMALS];


TULONG strtotul( const char* str, char** end, int base );
char*  tultostr( TULONG num, char* str, int base, int width );
int    strtonum( const char* str, int base );
char*  numtostr( char* str, int base );
void   printnum( int base );
void   printfrac( int base );
char*  repeating( TULONG rem, char* pos );


void get_point( void )
{
#ifdef _WIN32
  char sep;

  if (GetLocaleInfo( LOCALE_USER_DEFAULT, LOCALE_SDECIMAL, &sep, 1 ))
    point = sep;

#elif defined( __DJGPP__ )
  __dpmi_regs regs;

  regs.x.ax = 0x3800;
  regs.x.ds = __tb >> 4;
  regs.x.dx = __tb & 0x0f;
  __dpmi_int( 0x21, &regs );
  if (!(regs.x.flags & 1))
    point = _farpeekb( _dos_ds, (__tb & 0xfffff) + 9 );

#else
  struct COUNTRY ci;

  if (country( 0, &ci ))
    point = *ci.co_desep;

#endif
}


#ifdef __GNUC__
void help( void ) __attribute__((noreturn));
#endif

void help( void )
{
  printf(

"BaseN by Jason Hood <jadoxa@yahoo.com.au>.\n"
"Version " PVERS " (" PDATE ").  Public Domain.\n"
"http://misc.adoxa.cjb.net/\n"
"\n"
"Convert numbers in any base (%d-%d) to any other base(s).\n"
"\n"
"basen [*[min.][max]] [_[N][.M]] [#[=]base[:min]] number... [=|/base[-base]]...\n"
"\n"
"  min      Minimum number of digits before the point\n"
"  max      Maximum number of digits after the point (default %d)\n"
"  N, M     Add an underscore every N digits before the point, M digits after\n"
"  #base    Input base (default 10)\n"
"  number   Number(s) in the input base\n"
"  =base    Output base(s) (default 10)\n"
"  /base    Force decimals to be output as fractions\n"
"\n"
"Any non-digit can be used to separate min & places and N & M.\n"
"Numbers can contain a point or fraction, but are limited to %d bits.\n"
"A second point is used to indicate the following digits repeat.\n"
"If a minus sign is present, it is ignored; underscores are also ignored.\n"
"Bases above 36 use A-Z for 10-35, a-z for 36-61, @ for 62 and $ for 63.\n"
"Decimals are truncated, not rounded.\n"
"\n"
"Eg: 3%c333_333 3-1/3 3+1/3 \"3 1/3\"\n"
"    0%c16   -> 4/25\n"
"    0%c1%c6  -> 1/6\n"
"    *3 1/7 -> 0%c142\n"

	  , MINBASE, MAXBASE, places, (int)DIGITS,
	  point, point, point, point, point );

  exit( 0 );
}


int check_base( const char* str, char** end )
{
  int base = (int)strtol( str, end, 10 );
  if (base < MINBASE || base > MAXBASE)
  {
    fprintf( stderr, "Invalid base: %d\n", base );
    exit( 1 );
  }

  if (**end == ':')
    minimum[base] = (int)strtol( *end + 1, end, 10 );

  return base;
}


void set_base( int base )
{
  int ch;

  memset( numeral, -1, sizeof(numeral) );

  for (ch = '0' + min( base, 10 ); --ch >= '0';)
    numeral[ch] = ch - '0';

  if (base > 10 && base <= 36)
  {
    for (ch = 'A' + base - 10; --ch >= 'A';)
      numeral[ch] = numeral[ch | 0x20] = ch - 'A' + 10;
  }
  else if (base > 36)
  {
    for (ch = 'A'; ch <= 'Z'; ++ch)
      numeral[ch] = ch - 'A' + 10;
    for (ch = 'a' + min( base, 62 ) - 36; --ch >= 'a';)
      numeral[ch] = ch - 'a' + 36;
    if (base > 62)
      numeral['@'] = 62;
    if (base > 63)
      numeral['$'] = 63;
  }
}


int main( int argc, char* argv[] )
{
  int	inpos,	outpos, lastnum;
  int	inbase, outbase[MAXBASE];
  int	bases;
  char* bp;
  int	j, k;

  get_point();

  if (argc < 2 || strcmp( argv[1], "/?" ) == 0
	       || strcmp( argv[1], "-?" ) == 0
	       || strcmp( argv[1], "--help" ) == 0)
  {
    help();
  }
  if (strcmp( argv[1], "--version" ) == 0)
  {
    puts( "BaseN version " PVERS " (" PDATE ")." );
    return 0;
  }

  if (argv[1][0] == '*')
  {
    if (argv[1][1] == '\0')
      places = DECIMALS;
    else
    {
      j = (int)strtol( argv[1] + 1, &bp, 10 );
      if (*bp != '\0')
      {
	for (k = MINBASE; k <= MAXBASE; ++k)
	  minimum[k] = j;
	if (bp[1] != '\0')
	  places = atoi( bp + 1 );
      }
      else
	places = j;
      if (places < 1 || places > DECIMALS)
      {
	fprintf( stderr, "Places must be between 1 and %d: %s\n",
			 DECIMALS, argv[1] );
	return 1;
      }
    }
    inpos = 2;
  }
  else
    inpos = 1;

  if (inpos < argc && argv[inpos][0] == '_')
  {
    before = (int)strtol( argv[inpos] + 1, &bp, 10 );
    if (*bp != '\0')
      after = atoi( bp + 1 );
    ++inpos;
  }

  while (inpos < argc)
  {
    int inoutpos = 0;
    fraction = 0;
    inbase = 10;
    bases = 0;
    for (lastnum = inpos; lastnum < argc; ++lastnum)
    {
      if (argv[lastnum][0] == '=' || argv[lastnum][0] == '/')
	break;
    }
    outpos = lastnum;
    while (outpos < argc && (argv[outpos][0] == '=' || argv[outpos][0] == '/'))
    {
      if (bases == MAXBASE)
      {
	fputs( "Too many output bases.\n", stderr );
	return 1;
      }
      if (argv[outpos][0] == '/')
	fraction = 1;
      j = outbase[bases++] = check_base( argv[outpos] + 1, &bp );
      if (*bp == '-')
      {
	k = check_base( bp + 1, &bp );
	if (bases + abs( k - j ) > MAXBASE)
	{
	  bases = MAXBASE;
	  break;
	}
	if (j < k)
	{
	  while (++j <= k)
	    outbase[bases++] = j;
	}
	else
	{
	  while (--j >= k)
	    outbase[bases++] = j;
	}
      }
      ++outpos;
    }
    if (bases == 0 && argv[inpos][1] != '=')
      outbase[bases++] = 10;

    set_base( 10 );
    for (j = inpos; j < lastnum; ++j)
    {
      if (argv[j][0] == '#')
      {
	int inout = 0;
	bp = argv[j++] + 1;
	if (*bp == '=')
	{
	  inout = 1;
	  ++bp;
	}
	inbase = check_base( bp, &bp );
	set_base( inbase );
	if (inout && bases < MAXBASE)
	{
	  memmove( outbase + 1, outbase, bases * sizeof(int) );
	  outbase[inoutpos++] = inbase;
	  ++bases;
	}
	if (j == lastnum)
	  break;
      }
      if (!strtonum( argv[j], inbase ))
      {
	fprintf( stderr, "%s: %s\n",
		 (errno == ERANGE) ? "Number out of range"
				   : "Invalid number", argv[j] );
      }
      else
      {
	for (k = 0; k < bases; ++k)
	{
	  if (inbase == outbase[k])
	  {
	    char  buf[MAXNUMSTR];
	    char* str;
	    str = numtostr( buf, inbase );
	    if (numer == 0)
	    {
	      if (strcmp( argv[j], str ) == 0)
		continue;
	      printf( "%s = %s ", argv[j], str );
	    }
	    else if (fraction)
	    {
	      printfrac( inbase );
	      printf( "= %s ", str );
	    }
	    else
	    {
	      printf( "%s = ", str );
	      printfrac( inbase );
	    }
	    printf( "(base %d)\n", inbase );
	  }
	  else
	  {
	    printnum( inbase );
	    fputs( " = ", stdout );
	    printnum( outbase[k] );
	    putchar( '\n' );
	  }
	}
      }
    }
    inpos = outpos;
  }

  return 0;
}


// Print the number and its base.
void printnum( int base )
{
  char	sbuf[MAXNUMSTR];
  char* str;
  const char* fmt;

  str = numtostr( sbuf, base );
  if (fraction && numer != 0)
  {
    printfrac( base );
    fmt = "(%s) base %d";
  }
  else
    fmt = "%s base %d";

  printf( fmt, str, base );
}


// Print the number as a fraction.
void printfrac( int base )
{
  char fbuf[2][DIGITS*2];

  if (whole != 0)
    printf( "%s ",    tultostr( whole, fbuf[0], base, minimum[base] ) );
  if (numer != 0)
    printf( "%s/%s ", tultostr( numer, fbuf[0], base, 0 ),
		      tultostr( denom, fbuf[1], base, 0 ) );
}


// Convert the number in str according to base, setting end to the position
// where conversion stopped.  Underscores are ignored.
TULONG strtotul( const char* str, char** end, int base )
{
  TULONG num = 0;
  TULONG limit;
  int	 digit;
  int	 last;

  limit = TULONG_MAX / base;
  last	= (int)(TULONG_MAX % base);
  for (; *str; ++str)
  {
    if (*str == '_')
      continue;
    digit = numeral[(unsigned char)*str];
    if (digit == -1)
      break;
    if (num > limit || (num == limit && digit > last))
      errno = ERANGE;
    num = num * base + digit;
  }

  if (end)
    *end = (char*)str;

  return num;
}


// Convert the number in str according to base.
// Returns 1 if successful, 0 otherwise (errno == ERANGE if too big).
int strtonum( const char* str, int base )
{
  TULONG limit;
  TULONG rnumer, rdenom;
  char*  bp;

  if (*str == '-')
    ++str;

  numer = rnumer = 0;
  denom = 1;

  limit = TULONG_MAX / base;
  errno = 0;

  whole = strtotul( str, &bp, base );

  if (*bp == point)
  {
    str = bp + 1;
    numer = strtotul( str, &bp, base );
    if (*bp == '\0' || *bp == point)
    {
      if (str == bp)
	denom = 1;
      else
      {
	denom = base;
	while (++str < bp)
	{
	  if (denom > limit)
	  {
	    errno = ERANGE;
	    break;
	  }
	  denom *= base;
	}
      }
      if (*bp == point)
      {
	rnumer = strtotul( ++str, &bp, base );
	if (*bp == '\0')
	{
	  rdenom = base - 1;
	  while (++str < bp)
	  {
	    if (rdenom >= limit)
	    {
	      errno = ERANGE;
	      break;
	    }
	    rdenom = rdenom * base + base - 1;
	  }
	  numer  = numer * rdenom + rnumer;
	  denom *= rdenom;
	}
      }
    }
  }
  else if (*bp == '-' || *bp == '+' || *bp == ' ')
  {
    numer = strtotul( bp + 1, &bp, base );
    if (*bp == '/')
    {
      denom = strtotul( bp + 1, &bp, base );
      fraction = 1;
    }
  }
  else if (*bp == '/')
  {
    fraction = 1;
    numer = whole;
    denom = strtotul( bp + 1, &bp, base );
    whole = 0;
  }

  if (numer != 0 && denom != 0)
  {
    // Reduce the fraction.
    TULONG f, g, h;

    if (numer >= denom)
    {
      whole += numer / denom;
      numer %= denom;
    }

    if (numer != 0)
    {
      // Euclidean algorithm for finding the greatest common divisor.
      for (f = denom, g = numer; (h = f % g) != 0; f = g, g = h) ;
      numer /= g;
      denom /= g;
    }
  }

  return (*bp == '\0' && errno != ERANGE);
}


// Convert num to a string, using base. The number is placed at the END of str,
// which should be at least DIGITS*2 bytes.
// Returns the start of the number.
char* tultostr( TULONG num, char* str, int base, int width )
{
  int underscore;
  int cnt;

  str += DIGITS*2 - 1;
  *str = '\0';
  underscore = before;
  cnt = width;
  do
  {
    if (before && underscore-- == 0)
    {
      *--str = '_';
      underscore = before - 1;
    }
    --cnt;
    *--str = digits[(int)(num % base)];
    num /= base;
  } while (num != 0 || cnt > 0);

  return str;
}


// Convert the number to a string, using base. The point is placed in the
// middle of str, which should be at least MAXNUMSTR bytes.
// Returns the start of the number.
char* numtostr( char* str, int base )
{
  char*  start;
  int	 cnt;
  TULONG w, n, d, limit;
  int	 approx;

  w = whole;
  n = numer;
  d = denom;
  limit = TULONG_MAX / base;
  approx = 0;
  if (n > limit)
  {
    approx = 1;
    do
    {
      d >>= 1;
      n >>= 1;
    } while (n > limit);

    if (n >= d)
    {
      w += n / d;
      n %= d;
    }
  }

  start = tultostr( w, str + 1, base, minimum[base] );
  if (approx)
    *--start = '~';

  if (n != 0)
  {
    int   underscore;
    char* repeat;

    cnt = 0;
    str += DIGITS*2;
    *str++ = point;
    underscore = after;
    rem_count = 0;
    do
    {
      repeat = repeating( n, str );
      if (repeat != NULL)
      {
	if (*repeat == '_')
	  *repeat = point;
	else
	{
	  memmove( repeat + 1, repeat, str - repeat );
	  *repeat = point;
	  ++str;
	}
	break;
      }
      if (after && underscore-- == 0)
      {
	*str++ = '_';
	underscore = after - 1;
      }
      n *= base;
      *str++ = digits[(int)(n / d)];
      n %= d;
    } while (n != 0 && ++cnt < places);
    *str = '\0';
  }

  return start;
}


char* repeating( TULONG rem, char* pos )
{
  int i;

  for (i = 0; i < rem_count; ++i)
  {
    if (rem == rem_buf[i])
      return rem_pos[i];
  }

  rem_buf[rem_count]   = rem;
  rem_pos[rem_count++] = pos;
  return NULL;
}