How to do Perl state machine (FSM) to parse bitstream (byte sequence)?

Question

I'm currently using Perl to parse incoming command sequences which comes from RS232 serial port. I try to use state machine, and its expected behavior is: (1) Receive a series of bytes from serial port; (2) The state machine uses the bytes as input, and jump to appropriate states.

I came up with a simplified demo Perl code (posted below), but encountered a problem: When the code enters "while(1){}", it gets stuck here, and cannot get out. Consequently, the $din byte sequence assignments is blocked by "while(1){}", and is invisible to the state machine. So, the FSM is stuck in "INIT" state, and just do NOT jump at all.

I figured this should be a very easy or entry-level practice in Perl coding, but searching thru Google does not help me too much. Can anyone help me with this? Thanks in advance~

...
my %next_state = (
        "INIT" => sub{
                $din eq "AA" and return "HEADER0" ;
                return "INIT"                     ;
                },
        "HEADER0" => sub{
                $din eq "99" and return "HEADER1" ;
                return "INIT"                     ;
                },
        ...
        );

# Set state machine's initial state.
my $cur_state = "INIT"   ;

# Integer for debugging purpose.
my $itgi = 0;

# Run the state machine.
while(1){
        $cur_state = $next_state{$cur_state}();
        print "$itgi, will jump to: $cur_state\n\n";
        $itgi++;
        }

# Send in input byte sequence, which simulates
# incoming bytes from RS-232 COM port:
$din = "AA"     ;
sleep(1)        ;
...

========== 2020.10.09 22:10 Update ==========

Thanks to the help of @ikegami after some effort and debugging job, now I can get my little sweet Perl state machine up and running, code as posted below.

However, it still has a problem, that is:

The input byte sequence (viz. @seq) must be non-0x00 values; if I put a 0x00 into the command sequence, then the FSM will exit when when it encounters the 0x00.

Why is this? The code uses "$cur_byte >= 0", which seems to me should be capable of handling 0x00 just as it handles non-zero values.

Why does 0x00 pull the state machine out of running?

use strict      ;
use warnings    ;

# input to the state machine
my $din ;

#---------------------------------------------------------------------
# FSM's state table.
#---------------------------------------------------------------------
# Expected input sequence is:
#   AA 99 00 01 ....
# In which:
#   (1) Fixed pattern "AA" and "99" are two bytes of header,
#   (2) Following bytes are uart ID, etc.
my %next_state = (
        "INIT" => sub{
                # If receives "AA" from input,
                # then jumpt to "HEADER0" state:
                $din eq "AA" and return "HEADER0" ; 
                # Otherwise just stay here:
                return "INIT"                     ; 
                },
        "HEADER0" => sub{
                # If receives "99" from input,
                # then proceed to "HEADER1" state:
                $din eq "99" and return "HEADER1" ; 
                # Otherwise, return to initial state:
                return "INIT"                     ; 
                },
        "HEADER1" => sub{
                # Capture first byte of uart ID:
                return "UARTID0";
                },
        "UARTID0" => sub{
                # Capture second byte of uart ID:
                return "UARTID1";
                },
        "UARTID1" => sub{
                # Capture second byte of uart ID:
                return "FINISHED";
                },
        "FINISHED" => sub{
                return "INIT";
                },
        );

#---------------------------------------------------------------------
# Set state machine's initial state.
#---------------------------------------------------------------------
my $cur_state = "INIT"   ;

#---------------------------------------------------------------------
# Send in command sequence
#---------------------------------------------------------------------
my @seq = (-1, 0xAA, -1, 0x99, -1, 0x06, -1, 0x07,
           -1, 0x08, -1, 0x09, -1, 0x0a, -1, 0x0b,
           -1, 0x0c, -1, 0x0d
          );

sub get_next_byte {
        while (@seq) { #(A)
                my $cur_byte = shift(@seq);
                return $cur_byte if $cur_byte >= 0;
                #
                sleep(-$cur_byte);
                }
        return (); #(B)
        }

#---------------------------------------------------------------------
# Run the state machine.
#---------------------------------------------------------------------
# Integer for debugging purpose.
my $itgi = 0;

while( $din = get_next_byte() ){ #(C)
        $din = sprintf("%02X",$din);
        $cur_state = $next_state{$cur_state}();
        print "-- Iteration $itgi, will jump to: $cur_state\n";
        $itgi++;
        }

print "-- Program finish.\n";

So ... the code gets into `while(1)` before it ever sets `$din` variable and thus it's locked into `INIT` state. First "_Send in input byte sequence..._" and _then_ get into `while` ...? — zdim, Oct 09 '20 at 06:07
However, that's not enough since the code bounces back into `INIT` (since `$din` is `99`). Need to "feed" it inside of that `while` loop, between invocations of `%next_state` subs. — zdim, Oct 09 '20 at 06:11
Why not have `while(<>)` and type in input? Or have desired input in a file, and run with that file, `prog filename`. The "magical" `<>` operator reads lines from all files given on the command line, or `STDIN` (so you can type what you want and hit enter) if there are no files — zdim, Oct 09 '20 at 06:14
Tip: There's no reason to work with the hex representations of the byte instead of the bytes themselves. It's extra work for nothing. Instead of `$din eq "AA"`, use `$din == 0xAA`, etc. — ikegami, Oct 09 '20 at 07:25
I would just like to point out that I like the diversity of people and problems we encounter here. For most people (me included, and I've been doing this for a long time) a state machine is anything but entry level. But if you do CS, it probably is. Most questions we get in the Perl tag are "how do I parse this line of text" or similar. Yours is fun! :) — simbabque, Oct 09 '20 at 08:44
@zdim Because I'm currently trying to work out a simplest demo FSM code; and "while(<>)" seems too complex for this purpose :-) — katyusza, Oct 09 '20 at 09:12
"_`while(<>)` seems too complex for this purpose_" -- oh, OK; perhaps I didn't introduce it well -- it's the simplest way to quickly test I think. With `while (my $din = <>) { chomp $din; ... }` the rest of the code stays the same, and now when you run the program it waits for you to type input (and ENTER); it processes that and then stops and waits again, etc. (Or you can put input to test in a file and run the program on that file, and it takes line by line.) If that's still not what you want, fine of course; I just wanted to clarify the use of `<>` — zdim, Oct 09 '20 at 19:19
@zdim thanks buddy, I followed your instructions, and after some debugging job, the state machine is now correctly running as expected! But in the original post (which I updated it), why does that FSM quit running when it reads 0x00 input? It's been frustrating me, and I haven't found a solution yet. — katyusza, Oct 10 '20 at 01:36
This is really killing me -_- Then how do I create a "0x00 effective data byte" rather than a "0x00 null byte" ? — katyusza, Oct 10 '20 at 02:04
zero in hex is `0x30` (but you should be able to always just leave it as `0`) ... but `0` (zero) will make `while` terminate as well, since it's taken as false — zdim, Oct 10 '20 at 02:10
(Removed a comment where I stated that `0x00` is a null byte, not a zero -- because I had a little one-liner demo that was faulty in a silly way. (a `while` loop quits on null but it quits on a zero as well :). But 0x00 _is_ the null, just the "demo" was bad) — zdim, Oct 10 '20 at 02:19

ikegami · Accepted Answer · 2020-10-09T07:36:49.823

5

You enter the loop without ever changing $din. You need something like

# Run the state machine.
while ( my ($din) = get_next_byte() ) {
   $din = sprintf("%02X", $din);
   $cur_state = $next_state{$cur_state}();
   print "$itgi, will jump to: $cur_state\n\n";
   $itgi++;
}

For testing purposes, you could use

my @seq = (-1, 0xAA, -1, 0x99);

sub get_next_byte {
   while (@seq) {
      my $next = shift(@seq);
      return $next if $next >= 0;
      sleep(-$next);
   }

   return ();
}

edited Oct 09 '20 at 07:36

answered Oct 09 '20 at 07:25

ikegami

367,544
15
269
518

Thanks buddy, this seems much neater than the cumbersome fork(), pipe, AnyEvent stuffs taht I'm trying to put into my code. I'll see if I can follow your code snippet and get thru it. – katyusza Oct 09 '20 at 09:05
Thanks buddy @ikegami, I merged your code into mine and now the state machine is starting to run, but the incoming data sequence must be non-0x00 values. If I put a 0x00 into "@seq", then the FSM will exit from this point. I debugged and re-examined the code but got no clue. Any hints on this? – katyusza Oct 09 '20 at 14:28
You changed `while ( my ($din) = get_next_byte() )`. ok, removing the `my` makes sense, but you also removed the parens which were key. See [Scalar vs List Assignment Operator](https://stackoverflow.com/a/54564429/589924) – ikegami Oct 10 '20 at 01:50
Thx buddy, I'll go check it out. Didn't realize Perl has got so many nuance details that gets people crazy. – katyusza Oct 10 '20 at 02:02
As of now, after debugging the conclusion is: the `while( ($din) = get_next_byte() ){ ...}` **does work correctly**, and the `while( my ($din) = get_next_byte() ){...}` will result in Error info *`Use of uninitialized value $din in string eq at ...`* which points to the `$din eq "AA"` line. – katyusza Oct 10 '20 at 02:38
What I don't understand is: (1) What is the point of putting `$din` in parentheses? In my understanding, this makes it a list with one scalar element, but all other codes are using `$din` as a simple scalar variable. Why use `($din)`? (2) Why does the ***`my`*** in front of `($din)` matter so much? – katyusza Oct 10 '20 at 02:44
Re "*What is the point of putting $din in parentheses?*", I linked to a Q&A that explains it in my previous comment /// Re "*In my understanding, this makes it a list with one scalar element*", Parens never create lists. They normally just change precedence. This is an exception in that they affect which assignment operator is used. (This causes the assignment to create a list for its LHS, so it be said the parens indirectly created a list in this situation.) – ikegami Oct 10 '20 at 03:05
Re "*Why does the `my` in front of `($din)` matter so much?*", See [How should I use the “my” keyword in Perl?](https://stackoverflow.com/a/20890822/589924). But in this case, it makes sense to not use `my` there since you want the variable to be global to avoid passing it as a parameter to the callbacks. Might not be the best practice, but it's not the worse either. – ikegami Oct 10 '20 at 03:08
Thanks buddy, I have completely worked it out: ```($din)``` with parens gives a TRUE or FALSE result, while ```$din``` without parens gives the element value of ```@seq```. – katyusza Oct 11 '20 at 09:33
No. The parens cause the assignment to be a list assignment, and a list assignment in scalar context returns the number of elements returned by its right-hand side. See the link I posted in an earlier comment. – ikegami Oct 11 '20 at 09:36

score 1 · Answer 2 · answered Oct 11 '20 at 09:31

Thanks to the help @zdim and @ikegami, now I finally completely worked out this program. I'll post my working code as below, in case someone may have the same question.

Following code is inspired by zdim:

use strict      ;
use warnings    ;

# input to the state machine
my $din ;

# FSM's state table.
# Expected input sequence is:
#   AA 99 00 01 ....
# In which:
#   "AA" and "99" are two bytes of header,
#   "00" and "01" are two bytes of uart ID.
my %next_state = (
        "INIT" => sub{
                # If receives "AA" from input,
                # then jumpt to "HEADER0" state:
                $din eq "AA" and return "HEADER0" ;
                # Otherwise just stay here:
                return "INIT"                     ;
                },
        "HEADER0" => sub{
                # If receives "99" from input,
                # then proceed to "HEADER1" state:
                $din eq "99" and return "HEADER1" ;
                # Otherwise, return to initial state:
                return "INIT"                     ;
                },
        "HEADER1" => sub{
                # Capture first byte of uart ID:
                return "UARTID0";
                },
        "UARTID0" => sub{
                # Capture second byte of uart ID:
                return "UARTID1";
                },
#        "UARTID1" => sub{
#                return "FINISHED";
#                },
        "FINISHED" => sub{
                return "INIT";
                },
        );

# Set state machine's initial state.
my $cur_state = "INIT"   ;

# Integer for debugging purpose.
my $itgi = 0;

# Run the state machine.
while($din = <>){
        chomp $din ;
        $cur_state = $next_state{$cur_state}();
        print "$itgi, will jump to: $cur_state\n\n";
        $itgi++;
        }

# Send in input bytes:
$din = "AA"     ;
sleep(1)        ;
$din = "99"     ;
sleep(1)        ;

Following dode is inspired by ikegami, and pay attention to the difference between ($din) and simply $din without parentheses: with parens, we get a TRUE or FALSE result; without parens, we get the actual element value of @seq, and if this value is 0x00 then while will become while(0) and will exit.

use strict      ;
use warnings    ;

# input to the state machine
my $din ;

#---------------------------------------------------------------------
# FSM's state table.
#---------------------------------------------------------------------
# Expected input sequence is:
#   AA 99 00 01 ....
# In which:
#   (1) Fixed pattern "AA" and "99" are two bytes of header,
#   (2) Following bytes are uart ID, etc.
my %next_state = (
        "INIT" => sub{
                # If receives "AA" from input,
                # then jumpt to "HEADER0" state:
                $din eq "AA" and return "HEADER0" ; #(D)
                # Otherwise just stay here:
                return "INIT"                     ; 
                },
        "HEADER0" => sub{
                # If receives "99" from input,
                # then proceed to "HEADER1" state:
                $din eq "99" and return "HEADER1" ; 
                # Otherwise, return to initial state:
                return "INIT"                     ; 
                },
        "HEADER1" => sub{
                # Capture first byte of uart ID:
                return "UARTID0";
                },
        "UARTID0" => sub{
                # Capture second byte of uart ID:
                return "UARTID1";
                },
        "UARTID1" => sub{
                # Capture second byte of uart ID:
                return "FINISHED";
                },
        "FINISHED" => sub{
                return "INIT";
                },
        );

#---------------------------------------------------------------------
# Set state machine's initial state.
#---------------------------------------------------------------------
my $cur_state = "INIT"   ;

#---------------------------------------------------------------------
# Send in command sequence
#---------------------------------------------------------------------
my @seq = (-1, 0xAA, -1, 0x99, -1, 0x00, -1, 0x00,
           -1, 0x00, -1, 0x00, -1, 0x0a, -1, 0x0b,
           -1, 0x0c, -1, 0x0d
           );

sub get_next_byte {
        while (@seq) { #(A)
                my $cur_byte = shift(@seq);
                return $cur_byte if $cur_byte >= 0;
                #
                sleep(-$cur_byte);
                }
        return (); #(B)
        }

#---------------------------------------------------------------------
# Run the state machine.
#---------------------------------------------------------------------
# Integer for debugging purpose.
my $itgi = 0;

##--while( my ($din) = get_next_byte() ){ #(C)
    while(    ($din) = get_next_byte() ){ #(C)
        $din = sprintf("%02X",$din);
        $cur_state = $next_state{$cur_state}();
        print "-- Iteration $itgi, will jump to: $cur_state\n";
        $itgi++;
        }

print "-- Program finish.\n";

How to do Perl state machine (FSM) to parse bitstream (byte sequence)?

2 Answers2