Converting from decimal to word

Question

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 <stdio.h>
#include <string.h>
#include <stdlib.h>
#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 (k<=base) {
      wrd->num[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 <4 || 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 (!(start%PE)) puts(p.pass);
      d=conv(&p, step, MAX_LEN, base);
      /*[8]*/
      if (d<maxlen) maxlen=d; p.pass=&(p.w[maxlen]);

   }

   free(p.alpha);
   return 0;

}

---

/* setup.h */

typedef unsigned int uint;
typedef unsigned short ushort;
typedef unsigned long ull;
typedef unsigned char uchar;

#define MAX_LEN 64
#define MAX_ALPHA_LEN 127

---

Code explanation

1. That's a struct that contains num[MAX_LEN], that holds numbers for w[MAX_LEN+1] like this:

   • num[]={1,2,3}
   • w[]={alphabet[0], alphabet[1], alphabet[2]}

2. That's a function responsible for adding decimal numbers to word. Returns current position in a word.

   • "abcd" -> "abce" -> "abcf" -> ... -> "abc< last_letter_of_alphabet >"

3. That's what I don't like: these ifs/elses.

4. Another thing I don't know how to get rid of: repetition of wrd->w[p]=wrd->alpha[wrd->num[p]-1];
5. All numbers in num should be zeroes.
6. That's called only once and converts the number we start from to word.

7. p.pass is a pointer I'm using to print the words

   • w[]=="\0\0\0ab"; -> p.pass==&(w[3]);

8. That runs when a new character's added to word

You may find this part of code (uchar n=k/base, d=k-(base*n);) a bit complicated, I'll explain it as well.

As the comment says, d=k-(base*n); does the same as d=k%base;. I'm using it because I was told that modulo operation on 64-bit integers will be (and it is) pretty slow on 32-bit platforms. Moreover, I already know the quotient, so I can easily calculate the remainder.

---

How to use

Compile that as an ordinary C program and run the following:

./gen <start from> <stop at> <alphabet> <print each N-th combination> <generate every N-th combination>

For example, ./gen 1 10 abcd 1 2 will result in the following

a
c
aa
ac
ba

It generates every 2nd combination and prints all generated words.

That program can add any number to the word. I've got another program that lacks the if/else statement ([3]) but fails to add a number if k%base is zero (zeroes are not allowed).

---

What does this program do?

This program was made to generate permutations with repetition of a given alphabet. When you supply a number to start with, it converts it to a so called 'word' using the given alphabet. In other words, it computes the N-th permutation with repetition. The first is always the first letter of the given alphabet while the last is unknown as there is an infinite number of permutations. The permutations ('words') become longer and longer as the number (the position of each permutation) increases.

If you have an alphabet of length 62, you get 62 words of length 1, 62^2 words of length 2 and 62^k words of length k. The first permutation is alphabet[0], the 62-th is alphabet[62-1] and the third is alphabet[0]+alphabet[0].

The goal is not to convert decimal numbers to any base but to generate permutations with repetition using bases.

---

Questions

1. Is it possible to remove the if/else statement I was talking about in p. 3?
2. Is it possible to get rid of code repetition I was talking about in p. 4?
3. How can I speed up the code?

Answer 1

Bugs

There are a few buffer overflows in your program:

1. 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.

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

3. 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:

1. 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.

2. 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); 
   

Answer 2

Code explanation

I am known for posting answers on non-executable parts of code (comments, whitespace, etc), but this answer is going to be even less about the source code (but an important point to be made nonetheless).

Your code has scarcely little in the way of comments. And I'd wager that the comments that are in your code are only put there for the sake of this post so that the Code Explanation section of your question is easier to write.

Here's the thing... if you have to go back in and leave reference points for an entire section of your post to explain what it is that your code does, then your source code isn't readable enough.

I've said it before:

Your code is not allowed to be comment-free until your code is self-documenting enough that anyone with an understanding of how the language’s syntax works can get the gist of what your code is doing. Well-written code should read relatively close to plain English.

You might be able to improve some of the readability of your code with better variable names and better function names.

But until you've got your code to that point, you need to put the comments in the source code itself. You should require an entire passage of plain text outside the code to explain what the code does. I've never seen a clearer sign the source code is clearly lacking in comments.

Answer 3

Your program is hard to read. Put spaces around operators and split complex statements up into multiple, easier to grasp statements. This will make maintaining the code easier, and will make bugs more apparent.

ull stop=strtoull(argv[2],NULL,10), start=strtoull(argv[1],NULL,10),cnt=start;

It's impossible to quickly scan this line and understand it's purpose and side-effects. Variable initialisation should be done one per line. Put a space after a comma.

ull stop = strtoull(argv[2], NULL, 10);
ull start = strtoull(argv[1], NULL, 10);
ull cnt = start;

Variable names should be pronounceable - this makes it easier to read the code (at least for me). Why was removing one character from "word" to wrd necessary?

I don't understand why you don't like the if/else-statement. I think it's clear enough.

d = k - (base * n); // equal to k%base;

If that comment is true, why don't you just do k % base? Make your code clean and you won't need comments like these. It would probably be faster since it's just one instruction.

I don't like how your using typedefs for primitive types. Sure it saves you some typing, but now the person has to jump between setup.h and your .c file to understand what each type is. I think this is bad practice.

The program doesn't seem to work.

$ ./a.out 1 20 0123456789abcdef 1
0
1
2
3
4
5
6
7
8
9
a
b
c
d
e
f
00
01
02
03
*** Error in `./a.out': free(): invalid next size (fast): 0x0000000000ed8010 ***
Aborted

This is the hexadecimal "alphabet". First of all, 0 is not between 1 and 20. Secondly, when it gets to 16 (10 in hex), it prints 00 instead (and so on). And then it crashes.

Why does it print every 1000th by default? It would feel more intuitive if it printed every character between start and stop by default.

Answer 4

My suggestion would be to compute the result for all 256 k%base for the desired base, store the results in an associative array and then just look up the pre-computed value, instead of calculating it during runtime.