/*************/
/* palin05.c */
/***************************************************************/
/* Vincent Prosper, Sébastien Veigneau                         */
/* Looking for a palindromic word by iteration of the addition */
/* between an integer and its mirror                           */
/* Algorithm on arrays of chars                                */
/* Best algorithm, optimized program                           */
/***************************************************************/

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

#define MAXBASIS      10
#define MAXSTEP   430280                /* default number of iterations */
#define MAXTAB  ((MAXSTEP)>>1)
#define DUMPSTEP 1000000                /* dump frequency */

int base=MAXBASIS;			    /* default basis */

int ToBase(int n, char t[])
{ char tmp; int i=0;
  if (!n) { t[0]=0; t[1]=0; return 1; }
  else
  { while(n) { t[i++]=n%base; n/=base; }
    for(n=0;n<(i>>1);n++) { tmp=t[n]; t[n]=t[i-n-1]; t[i-n-1]=tmp; }
    t[i]=0;
  }
  return i;
}

int main(int argc, char **argv)
{ char *t0, *t1, tmp[64], *working, *notworking, carry=0, carry_tmp=0;
  register unsigned int dumpstep=0, result;
  register unsigned i, j=0, k, step=0, test=1,
                    maxstep=MAXSTEP,
                    nbdumpstep=DUMPSTEP, lgworking=0, halflgworking;
  unsigned start, end;
  if (argc<3)
  { fprintf(stderr,"Usage: %s start end [-m<nb>] [-d<nb>] [-b<nb>]\n",*argv);
    fprintf(stderr,"* start, end: decimals\n");
    fprintf(stderr,"*         -m: max. number of iterations\n");
    fprintf(stderr,"*         -d: nb iterations per dump\n");
    fprintf(stderr,"*         -b: base <=10\n");
    fprintf(stderr,"For each integer between startd and end, it creates a file.\n");
    fprintf(stderr,"This file answer to the question : is it a palindrom now?\n");
    exit(0);
  }

  start=atoi(argv[1]); end=atoi(argv[2]);
  for(i=3;i<argc;i++)
  { if (strstr(argv[i], "-m")) { maxstep=atoi(argv[i]+2); continue; }
    if (strstr(argv[i], "-b")) { base=atoi(argv[i]+2); continue; }
    if (strstr(argv[i], "-d")) { nbdumpstep=atoi(argv[i]+2); continue; }
  }
  base=base>MAXBASIS?MAXBASIS:base;
  fprintf(stderr, "Computing palindromic reversal numbers from %d up to %d in base %d\n", start,end,base);
  lgworking=ToBase(start,tmp);

  t0=(char *)calloc(MAXTAB, sizeof(char)); t1=(char *)calloc(MAXTAB, sizeof(char));
  if (!t0 || !t1) { fprintf(stderr, "Not enough memory...\n"); exit(1); }

  while(start<=end)
  { for (i=lgworking;i>0;i--) t0[j++]=tmp[i-1];
    while(test && step!=maxstep)
    { if (step & 1)
      { working=t1; notworking=t0; }
      else
      { working=t0; notworking=t1; }
      working[lgworking]='\0';
      halflgworking=lgworking>>1;
      for (i=0,k=lgworking-1;i<halflgworking && (working[i]==working[k-i]);++i);
      if (i==halflgworking)
        test=0;
      else
      { step++; carry=0;
        for(i=lgworking;i>0;i--)
        {
	  result=working[lgworking-i]+working[i-1]+carry;
          notworking[lgworking-i]=(carry=(result>=base))?result-base:result;
        }
        if (carry) { notworking[lgworking-i]=1; lgworking++; }
      }
       
      if ((++dumpstep)==nbdumpstep || !test)
      {
        char buf[96], tmpp[96];
        FILE *f;
        strcpy(buf, "dump."); sprintf(tmpp, "%d.%d", start, step);
        strcat(buf, tmpp);
        f=fopen(buf, "w");
        if (test) for (i=lgworking;i>0;--i) fprintf(f,"%c",
        notworking[i-1]+'0');
        else fprintf(f,"%s", working);
        fclose(f);
        dumpstep=0;
      }
    }
    start++; step=0; test=1; j=0; carry=0;
    lgworking=ToBase(start,tmp);
  }
  fprintf(stderr,"done\n");
  free(t0);
  free(t1);
  exit(0);
}