drawing FSM with Graphviz

512 views
Skip to first unread message

indy arm

unread,
Oct 9, 2010, 9:26:45 AM10/9/10
to ml-d...@googlegroups.com, Antony Newman
Hi,

While reading AJ pages about Object States, I was pretty sure we can find a free tool to generate nice drawings of Finite State Machines from a text description.
I just tryied using Graphviz (http://www.graphviz.org/Gallery/directed/fsm.html) and the state machine at http://magiclantern.wikia.com/wiki/2.0.4_StateObjects_LVRecState.

Just download and install Graphviz:
http://www.graphviz.org/Download..php

then I use the following command:

dot -Tsvg lvstate.gv >lvstate.svg

which gives the attached lvstate.svg output from the lvstate.gv (graphviz) input.
I give also the output in PNG.
Svg files can be included in the Wiki.

Maybe it is possible to generate such .gv description from the FW code using an IDA script, with generated names for states (S_n) and inputs (n_Event).

Indy
lvstate.gv
lvstate.svg
lvstate.png

Alex

unread,
Oct 10, 2010, 3:55:40 AM10/10/10
to Magic Lantern firmware development
Looks nice!
I'd use a larger, sans-serif font for better readability, though.

I'll write such a script if you teach me how did you get the state
machine from assembly code :) I did not found those states in the IDA
map (or do they use slightly different name?)


On Oct 9, 4:26 pm, indy arm <arm.indi...@gmail.com> wrote:
> Hi,
>
> While reading AJ pages about Object States, I was pretty sure we can find a
> free tool to generate nice drawings of Finite State Machines from a text
> description.
> I just tryied using Graphviz (http://www.graphviz.org/Gallery/directed/fsm.html) and the state machine athttp://magiclantern.wikia.com/wiki/2.0.4_StateObjects_LVRecState.
>
> Just download and install Graphviz:http://www.graphviz.org/Download..php
>
> then I use the following command:
>
> dot -Tsvg lvstate.gv >lvstate.svg
>
> which gives the attached lvstate.svg output from the lvstate.gv (graphviz)
> input.
> I give also the output in PNG.
> Svg files can be included in the Wiki.
>
> Maybe it is possible to generate such .gv description from the FW code using
> an IDA script, with generated names for states (S_n) and inputs (n_Event).
>
> Indy
>
>  lvstate.gv
> 1KViewDownload
>
>  lvstate.svg
> 17KViewDownload
>
>  lvstate.png
> 71KViewDownload

Antony Newman

unread,
Oct 10, 2010, 8:17:50 AM10/10/10
to ml-d...@googlegroups.com

Hi Alex

If you look at the bottom of this page, there is 'memory map' of how the array of information is stored for state machine.

http://magiclantern.wikia.com/wiki/2.0.4_StateObjects

The two dimensional array is determined by the Total_inputs x Total_states.

Arm.Indy: The pictures definitely look better than text.  Two points to note for 'LVRecState' and 'LVState' state machines:
i) There is some interaction between the two state machines
ii) Some of the states are guesswork at the this stage.

As soon an we can write out the state information in ML to the screen ... we'll be able to work know definitively what the states actually are.

Regards,
Antony



arm.indy

unread,
Oct 10, 2010, 8:53:51 AM10/10/10
to Magic Lantern firmware development
Alex,

see http://magiclantern.wikia.com/wiki/550D_StateObjects and your
mailbox.
I recommanded AJ pages, of course ;-)

Indy


Alex

unread,
Oct 14, 2010, 5:15:50 AM10/14/10
to ml-d...@googlegroups.com
Thanks!

Here is my first attempt to generate the state machine from Indy's binary example. Attached are the script (not yet finished), my test file and the outputs. The script doesn't take any command-line arguments, but you can edit the variables from the first line (input/output files, state matrix address etc.)

Todo (help needed here):
- extract some names for the states and edges (I don't know where I can find them... maybe in the strings file?)
- use a real Canon image file (which I don't have yet)
- try it on other state objects and on 550D image

Alex





--
http://magiclantern.wikia.com/

To post to this group, send email to ml-d...@googlegroups.com
To unsubscribe from this group, send email to ml-devel+u...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/ml-devel?hl=en

states.py
state.png
state.bin
state.gv

Alex

unread,
Oct 14, 2010, 11:09:24 AM10/14/10
to ml-d...@googlegroups.com
I've ran the script on the Canon 500D firmware posted here: http://magiclantern.wikia.com/wiki/500D . Here is an updated version of the script.

I've followed these steps:
1) Open 500d_t1i_ff010000.bin in ghex2 and look for patterns like this: 0a 00 00 00 xx xx xx xx 0b 00 00 00 xx xx xx xx ...
2) Found such a pattern near a string named USB20State. Address: 0x42B770 + 0xFF010000 = 0xFF42B770.
3) Tried to guess the number of states and inputs, by giving small values. The script tries to guess the number of states automatically.
    Result: 11 states, 13 inputs. From Anthony's Table, this is USB20State - USBControlPipe. Yay, it seems correct!
4) The pattern continues after this 11x13 matrix, so there should be more states available. The script outputs:
      Structure start: FF42B770
      Structure end  : FF42BBE8
    So, the next structure address is at FF42BBE8. The same guesswork results in 9 states / 11 inputs, which is USBDataPipeBulkIn. Repeat steps 3 and 4 until USBDeviceEvent.
5) After looking again for state machine patterns in ghex2, I've found another one at 0xFF41E544. Guessed 14 states/23 inputs. From AJ's table, this is LV_StateObj. A huge one! The matrix seems to be consistent to AJ's description (the big colorful tables). I've tweaked a little the script to output shorter labels.

So, right now you have the diagram for LV_StateObj in the attached PDF. Without names for inputs/states, though...

After LV state, there seem to be more states, probably some small ones, but I can't figure out which they are.

The new script outputs:
- lots of .gv sources, one for each state machine
- a .png and a .pdf for each SM
- a big PDF with all the state machines, one per page.

If you want to try the script on another firmware image, you may have to edit the first lines (the ones before 'import' statement). I hope their names and comments are enough for understanding what they do.

Now I'm looking for the state names. Right after the state number, in the code, there is a pointer (I remember reading it's for a subroutine). However, I've tried a few pointers and did not find any subroutine at those addresses.

E.g. FF42B770 00 00 00 00 34 3D 18 FF 00 00 ...

So, the subroutine address should be FF183D34. No subroutine found here... just a big 32-bit integer which I don't know what means.
states.pdf
states.py

arm.indy

unread,
Oct 16, 2010, 3:06:19 PM10/16/10
to Magic Lantern firmware development
hi,

I have listed here
http://magiclantern.wikia.com/wiki/550d_108_StateObjects

ALL State Objects of 550D/1.0.8

Indy

Reply all
Reply to author
Forward
0 new messages