need algorithm: is 8-bit value valid given mask?

[tschak909]

Hi guys,

 

Am pondering a much needed routine for BB65, to determine if a menu character (8 bit quantity as char), is valid given a mask (another 8-bit quantity).

 

e.g.

 

if (!is_valid_option(toupper(key),CHAR_1|CHAR_2|CHAR_3|CHAR_A|CHAR_B|CHAR_C))
    {
        printf("Invalid Option!\n");
    }

 

As such, I can of course manually assign values to the bits in the 8-bit mask and compare against them, but I know there's a far more efficient way to organize the bit fields in the mask so that it could be done simply with a few well placed adds/substracts/ANDs or shifts...but I am drawing a blank as to how to organize the mask, or algorithm...of course, I did just start thinking about it, but I thought I'd ask here for ideas as well...

 

any ideas?

 

-Thom

[Bryan]

Do you need:

 

A value that is bound to certain ranges?

 

or A value that is one of several scattered values?

 

It seems like what you want is the 2nd. That is, you want to reject anything that isn't a proper menu selection.

 

This is often done as part of the menu handling routine:

 

if char = A ...

if char = C ...

if char = E ...

else bad char

 

Sometimes a non-ASCII or non-ALPHA test is done first, but there's no way to test against an arbitrary list other than doing the comparisons or making a pass-fail LUT.

 

The LUT could be fairly short if it only needs to represent letters:

 

1. Subtract 'A' from the value

2. Make sure it's 0-25

3. Look up whether it's a menu option.

 

You could also pack 8 results per byte and shift the letter down 3, but the table savings are eaten by extra shifting code.

Edited September 12, 2014 by Bryan

[Bryan]

Some pseudo C code:

 

 

 
bool  is_valid_option(byte key)
{
     static byte table[]={1,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,1,0,0,0};
 
     key=key-'A';
 
     if (key>25)
         return 0;
 
     return table[key];
}
 

Declaring it static might make the routine shorter by eliminating code to create the variable on each call.

 

You could shorten the table if the extremes aren't used (A or Z). Also, you might want an UPPER conversion in there if you're not case sensitive.

Edited September 12, 2014 by Bryan

[tschak909]

Nice, but, wanting to be able to pass in a mask of allowable characters.. I'll think on it.

 

-Thom

[Bryan]

I see, you need to specify both...

 

I think passing a pointer to the acceptance string/array would be best here.

 

Here's a condensed idea: (4 bytes per input list)

 

//one bit per letter.
menu_options[]={0b00101010, 0b00101010, 0b00101010, 0b00100000}



byte is_valid_option(byte key, byte* menu_options)
{

     byte bitnum;

     key=key-'A';
 
     if (key>25)
         return 0;

     bitnum=key&0x07;

     return menu_options[key>>3]&(1<<bitnum);
}

Although, if I were specifying bitwise tables as above, I'd probably change the last expression to (0x80>>bitnum) so the first bit on the left would be 'A'. Edited September 13, 2014 by Bryan

[tschak909]

very interesting...thanks

 

-Thom

[Shawn Jefferson]

If you want to save some memory, I guess the second option would be better, but I think the first will compile to better code. Plus if you design your menu structures with the mask in mind, the memory issues may become a moot point-probably you want to take that into account when designing this function. Trade-offs everywhere I suppose.

 

What does your menu structure look like? I'm assuming you will offer your "check_valid_option" function as callable by any module, so your mask/char array/whatever, will be passed as an argument. With your use case, I imagine if you can use the same structure for menu display as you use for checking whether a valid option is chosen you will save memory in the end, and memory is probably going to be your issue, not speed (assuming we're talking about your BBS here.)

Edited September 20, 2014 by Shawn Jefferson