VHDL character set generation

Question

I need to generate all the possible combinations from a character set.

"abcdefghijklmnopqstuvxyz"

The patterns generated should be outputed like this.

a
b
...
z
aa
ab
...
az
ba
...

This will be done for an length of 8. I.e a=>zzzzzzzz. I have tackled the problem by writing an example in C, and I used an recursive function for this. I know it's written quick-and-dirty, but hopefully you'll get an idea.

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

#define WIDTH 8
char *charset = "abcdefghijklmnopqrstuvxyz";

void charset_r(int width, int pos, char *s)
{
    char buf[WIDTH];
    char *p = charset;

    while(*p!='\0')
    {
        strcpy(buf, s);
        if(pos<width)
        {
            strncat(buf, p, 1);
            printf("%s\n", buf);
            charset_r(width, pos+1, buf);
        }
        p++;
    }
}

int main(void)
{
    int i;
    for(i=0;i<=WIDTH;i++)
        charset_r(i,0,"");
}

My question is twofold:

1. Should I use recursion in VHDL?
2. If not, how can I tackle the problem?

Update:

So, the ultimate goal is to synthesize the code and put the values out on a clocked port. As I understand by reading the comments recursion might be a bad idea beyond depth 2 so it is probably best to solve it in some other way, without recursion.

Since I'm having trouble thinking about this in any other way than with recursion (can't seem to figure it out), any pointers or suggestions (even code!) would be greatly appreciated.

Answer 1

You may be better served to think of this as a hardware problem and not a software problem. You have eight state variables - one for each character in the sequence. If you use a 5-bit counter for each character then you can represent all of the characters [a-z], plus a null-state (zero, perhaps) to know when not to output the character.

You then need some sort of state machine to increment the counters along a set of simple rules: "increment counter 0 always. If counter 0 is at 26, then set it to 0 and increment counter 1... etc". That will drive your internal states.

Then create an output process that looks at the counters and decides which character to output in time (or no character at all if the counter hasn't incremented past zero). This process will take different amounts of time to execute if you're putting the characters out serially, so it will probably act as a trigger to advance your state machine.

No code, here, just an outline of the approach. But I think it will help you if you think about it along these lines.

Answer 2

You can treat each combination of characters as number written in base 26(which is number of characters in your sequence). This way, each number implicitly tell you the string sequence behind. You can convert numbers to base 26 and obtain the strings. Of course you need to repeat this procedure for each lengths of strings. I have written a simple code for you to demonstrate the idea. you can implement it in VHDL using synthesizable language subset.

for( int i = 1 ; i<= 8 ; ++i )
{
    for( int j = 0 ; j < pow(26,i) ; ++j )
    {
           foo( j , i  );
    }
}


void foo( int num , int len)
{
    char digits[len+1];
    // convert num from base 10 to base 26 and fill digits array with proper values in range 0-25
    toBase26(num,digits,len);
    digits[len] = '\0';
    for( int i = 0 ; i < len ; ++i )
    {
              digits[i] = digits[i] + 97 ; //  97 == 'a'
    }
    // do proper thing with your sequence

}