Converting from decimal to word

I'm still investigating the problem with decimal to word conversion. I understood the basics, but now my goal is to learn how to add in base-26 (the English alphabet) or base-52 ([a-zA-Z]) or base-62 ([a-zA-Z0-9]), etc.

I've written the following code and it works, but I think it could be written better and run faster.

```
#include
#include
#include
#include "setup.h"

/[1]/
struct Word {
uchar num[MAX_LEN];
char w[MAX_LEN+1], alpha, pass;
};

/[2]/
uchar conv(struct Word *wrd, uchar step, uchar p, uchar base) {
uchar k=wrd->num[p]+step;
if (knum[p]=k;
wrd->w[p]=wrd->alpha[wrd->num[p]-1];
return p;
} else {
uchar n=k/base, d=k-(base*n); // equal to k%base;

/[3]/

if (!d) {wrd->num[p]=base; --n;}
else wrd->num[p]=d;
/[4]/
wrd->w[p]=wrd->alpha[wrd->num[p]-1];
return conv(wrd,n,p-1,base);
}
}

// That seems to be OK, it was written only for testing.
int main(int argc, char **argv) {

if (argc 6) {
printf("\nUsage: %s start stop alpha [k] [d]\n", argv[0]);
puts(" \
\tstart - number to start from\n \
\tstop - number to stop at\n\talpha - alphabet to use\n \
\tk - (optional) print every k-th combination, every 1000th by default\n \
\td - (optional) generate combinations with step=d\n \
");
return -1;
}

uint PE=1000;
uchar step=1, maxlen=MAX_LEN, d=0, base=0;

struct Word p;

p.w[MAX_LEN+1]=0;

p.alpha=calloc(65,1);
ull stop=strtoull(argv[2],NULL,10), start=strtoull(argv[1],NULL,10),cnt=start;
strncpy(p.alpha, argv[3], MAX_ALPHA_LEN);
base=(uchar)strlen(p.alpha);

if (argc >= 5) PE=atoi(argv[4]);
if (argc == 6) step=(uchar)atoi(argv[5]);

/[5]/ memset(p.num,0,MAX_LEN);

/[6]/
for (;cnt;cnt=(cnt-1)/base,--maxlen) {
p.num[maxlen]=(cnt-1)%base+1;
p.w[maxlen]=p.alpha[p.num[maxlen]-1];
}

/[7]/
p.pass=&(p.w[++maxlen]);

for (;start<=stop;start+=step) {

if (!(sta

Bugs

There are a few buffer overflows in your program:

-
In conv(), every time you use wrd->num[p] is a buffer overflow, because p is passed in as MAX_LEN, and num is of size MAX_LEN. This is off by one.

-
In main(), you have p.w[MAX_LEN+1]=0, but w is of size MAX_LEN+1. This is also off by one.

-
In main(), you allocate this buffer p.alpha=calloc(65,1), but then fill it like this: strncpy(p.alpha, argv[3], MAX_ALPHA_LEN), where MAX_ALPHA_LEN is 127.

Your indentation/bracing style also caused you to have this bug:

if (d<maxlen) maxlen=d; p.pass=&(p.w[maxlen]);

Here, you only need to set p.pass if you change maxlen. But you put it all on one line so you can't see that you are doing the second statement outside of the if statement. It should be:

if (d<maxlen) {
      maxlen=d;
      p.pass=&(p.w[maxlen]);
  }

Thoughts on speeding up the code

After the clarification that the program is supposed to print permutations instead of baseN numbers, here are some ideas:

-
If you are only going to print every 1000th number, you shouldn't be generating the other 999 numbers. In main, I would replace the code after the memset with this:

step = step * PE;
for (int num = start+step-1; num <= stop; num += step) {
   uchar len = conv(&p, num, base);
   puts(&p.w[len]);
}

where conv() would essentially be the code that you already have to construct the first permutation (the loop marked with comment #6):

uchar conv(struct Word *wrd, int num, uchar base) {
   uchar maxlen;
   for (maxlen = MAX_LEN;num;num=(num-1)/base,--maxlen)
      wrd->w[maxlen]=wrd->alpha[(num-1)%base];
   return maxlen+1;
}

Notice that you no longer need wrd->num or wrd->pass any more.

-
If you didn't do the above, you could still make your program a lot simpler by handling zeros better. Right now you do something strange where in num, you hold index+1 and then later you subtract off 1 to get the correct alphabet letter. If you got rid of that, here's what conv() would look like:

uchar conv(struct Word *wrd, uchar step, uchar p, uchar base) {
   wrd->num[p] += step;
   while (wrd->num[p] >= base) {
      uchar n = wrd->num[p]/base;
      wrd->num[p] -= n * base;
      wrd->w[p] = wrd->alpha[wrd->num[p]];
      wrd->num[--p] += n;
   }
   wrd->w[p] = wrd->alpha[wrd->num[p]];
   return p;
}

You would also need to change a line in main() as well:

// Change to 0xff to make the new `conv()` work correctly.
/*[5]*/ memset(p.num,0xff,MAX_LEN);

StackExchange Code Review Q#96922, answer score: 3