mapping incoming bs+pc (beginner question)

[avogra]

hey,

i'm scratching my head about the following for some time:

my keyboard sends bs+pc on ch 0 when i press one out of 24 instrument buttons. i want to identify the button pressed and forward an individual message to the midi-out. unfortunately those messages are not in any order but arbitrary sets from the gx-standard (i suppose), so i can't ignore the bs and apply some offset to the pc to get a button-number.

at the moment i can think of 2 solutions to parse those incoming messages, but i'm not very pleased with both of them:

Option 1: straight forward - compare incoming sets to a table of known sets

-have a table, where each button is represented by its bs(msb) + bs(lsb) + pc

-store incoming bs+pc in a temporary struct-variable

-when pc was received, compare the set in the variable with each set in the table. the index of the table-entry that matches the variable, gives me the button number.

Option 2: a finite-state machine (did this already for incoming sysex-messages):

example code for 2 buttons:

//        BS-MSB BS-LSB   PC
// button1 0x00   0x70   0x01
// button2 0x00   0x44   0x05

unsigned char state; // 0xFF = set complete, 0xFE = unknown set
unsigned char last_state;
unsigned char button_pressed;

void process_messages(unsigned char msg_type, unsigned char value) {
  // msg_type 0x00=BS-MSB, 0x20=BS-LSB, 0xC0=PC
  last_state=state;
  switch state {
    case 0:						//no bytes received so far
      switch value {
        case 0x00:
          state=1;
      }
    case 1:          //0x00 received
      switch value {
        case 0x70:
          state=2;
          break;
        case 0x44:
          state=3;
      }
    case 2:          //0x00 0x70 received
      switch value {
        case 0x01:
          button_pressed=1;
          state=0xFF;
      }
    case 3:          //0x00 0x44 received
      switch value {
        case 0x05:
          button_pressed=2;
          state=0xFF;
      }
  }
  if (state == 0xFF)       //button recognized, do something with it
    do_something(button_pressed);
  if (last_state == state) //state didn't change -> unknown set
    state = 0xFE;
  if (msg_type == 0xC0)    //set completed -> start over
    state = 0;
}

Option 1 means, that in worst case, the programm has to do 24x3=72 table-lookups. i read those are really slow. as my app isn't doing too much at the moment, this might be a minor issue, but i don't like to start out that unefficient :)

Option 2 lacks overview, as the actual sets are spread over many cases, also the code really explodes, if i do this for all the 24 buttons. At the same time the function becomes quite complex (regarding execution paths). in the sdcc manual i read, that complexity shouldnt be more than 10, which i go far beyond. so this option seems to drop out completely.

Do you have any other ideas, how to do this? or maybe a way, to improve my options?

As i mentioned, i'm using option 2 for parsing sysex messages and it works (30 states). but i feel, it's really ugly and it is hard to read out the messages or add new ones. so any ideas here are very welcome too :)

Thanks!

Alex

[TK.]

I would prefer method 1 due to the better overview.

But I wouldn't start the search for a matching sequence once all three values have been received, instead I would do this on-the-fly whenever a new MIDI event has been received to improve the realtime responsiveness of the application.

Just use a single table which contains the three values + a pointer to the function which should be called in each line.

Something like this:

const my_search_structure_t search_structure[] = {
  // BC LSB  MSB  PC  Function
  {   0x00, 0x70, 0x01, &DoThisFunction },
  {   0x00, 0x44, 0x05, &DoThatFunction },
};
[/code]


Strategy:
- when the first event (BC MSB) is received, search for the first member in the table with matching MSB number
- when the second event (BC LSB) is received, check if the second value is matching as well, if not search for any of the following members with matching MSB/LSB number
- same when PC is received. First check for matching PC, and if it doesn't match search for the next matching MSB/LSB/PC element.
- finally you should know the member which is completely matching, so that the function can be called


A way to speed up the search would be a sorted table (something you can do manually, especially because the table structure doesn't change during runtime), so that your algorithm can break the search once the incoming number is lower/higher than the value of the current structure member.


And a way to speed up the search even more: set a threshold for the starting point. 
E.g. 64 (or any number which is in the middle of the search values in the first column).
This allows you set the optimal starting point for the search.


Alternatively to method 2: you could program a code generator (e.g. based on a small perl script) which generates the parser based on a human readable table. But I'm not sure, if it would run faster (on the PIC) compared to the table search method I mentioned above.


Warning: there is a typical programming error in your code:
[code]
 switch state {
    case 0:						//no bytes received so far
      // ...
    case 1:          //0x00 received

there is no break before "case 1", accordingly case 0 will execute the code after case 1 as well (same for other case statements)

Best Regards, Thorsten.

[avogra]

hey Thorsten,

thanks for the input!

your suggestion for improving the table-search is quite obvious, now that you showed me :) this is definitely a go.

you're right with the breaks. i have them in the sysex-parser, just forgot them in the example ^^

it's just 20 minutes, that i came up with another option myself: hash-functions. if i find a function, that creates a unique byte out of my 24 message-sets, i could populate a simple byte array with 24 entries in MPROC_Init. then, when i receive a set, calculate the hash thereof and search it in the byte array. still your solution might be even faster. although, if i use the right hash-function, i could also do a sorted table... hmmm :)

this might be very interesting for the sysex-parser too, it's only 10 messages to find. but might be tricky, to find a function there... if i don't, i might still think of your search as an alternative. is certainly better to read, and maybe not too slow...

arrgg, i should get some more coding practice, instead of evaluating air castles.

best thing will be, i do all of them and then decide on one :)

Cheers, Alex

[TK.]

Of course, if it is possible to create a unique byte value from the 2^(3*7) = 2^21 bit range, than a hash function is a practicable solution. But it will be less flexible, as you have to adapt the calculation of the hash value whenever new value sequences have to be parsed (no problem for you, as the sent MIDI events of your keyboard are known and won't be changed)

It would be different if you would use a 32bit controller (like MBHP_CORE_STM32 :)), because here it doesn't matter if the hash is 8bit, 16bit, 32bit - in any case the CPU will need the same time to compare the value.

For 8bit controllers it means that comparing values with range >8bit is very *very* expensive, since many instructions have to be executed to get the complete result.

Accordingly, your coding strategy has to consider such limitations.

Btw.: a binary tree search would also be an option, but a good solution would use a code generator (resp. parse tree generator) as well.

Best Regards, Thorsten.