Markov-algorithms with fasm :shock:

Index > Macroinstructions > Markov-algorithms with fasm :shock:

Author

Thread

MCD

Joined: 21 Aug 2004
Posts: 602
Location: Germany

MCD 31 Jan 2007, 11:33

I was doing Markov-algorithms recently and I got the wicked thought that fasm would also be able to do this with it's preprocessor, since it's a text-based system.

If you don't know what Markov-algorithms are all about, see here:http://en.wikipedia.org/wiki/Markov_algorithm

The only requirement for that is that fasm's preprocessor (still) works with those priority:
1st: fix
2nd: macros, strucs, rept, match, irp, irps...
3rd: equ

if this is true and if fasm got conditional (match...) and looping (rept, irp, irps) macros, than it would be possible to do Markov-algorithms in fasm.
An example, which takes a string starting with any number greater or equal than 1 of "l"s and duplicates the number of "l"s, where "_->_" is the macro/struc that should declare a rule. The dot "." is a kind of metasymbol that indicates that that rule should terminate the algorithm.

Code:

al _->_ lla
a _->_ .
l _->_ al

Usually I post my ideas after I got a solution, but unfortunately it's a long time since I extensively used macros and I have no time getting into that subject right now and writing the required macros on my own Sad

So if anyone has an idea how to do that with fasm, please reply. It would be just another interesting prove of concept for fasm.

_________________
MCD - the inevitable return of the Mad Computer Doggy

-||__/
.|+-~
.|| ||

31 Jan 2007, 11:33

vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia

vid 31 Jan 2007, 12:18

Quote:

Markov algorithms have been shown to be Turing-complete

that would mean you can make x86 emulator with FASM macros? :]

31 Jan 2007, 12:18

MCD

Joined: 21 Aug 2004
Posts: 602
Location: Germany

MCD 31 Jan 2007, 17:23

vid wrote:

Quote:
Markov algorithms have been shown to be Turing-complete

that would mean you can make x86 emulator with FASM macros? :]

that is an unavoidable consequence of that, but such emulation would [large]EXTREMELY[/large] unefficient in both space and time aspects.

An easier and a bit more efficient aproach of that would be to directly implement a deterministic Turing-machine or even something more directly tied to the concepts of real CPUs.

Another 4 thought I got about the Markov-algorithm are the following:

I.] It's probably difficult to define macros that define rules with strucs (infix notation, operation/command in the middle) like this:

Code:

al    _->_    lla

because in a struc it may be difficult to access the "basename"-identifier of the current sructure.

So it would be easier to use macros for that (prefix or polish notation, operation/command at the beginning, like in most assemblers):

Code:

_->_    al,lla

II.] My original idea was that if a Markov-algorithm should be applied to a string, you simply had to write it down after you had defined the rules, see like this:

Code:

;these should form the rules
al _->_ lla 
a _->_ . 
l _->_ al

llll    ;this line should be transformed by the preprocessor to "llllllll"

But since the preprocessor only does 1 pass (if that hasn't changed in the time of my absence), you wouldn't be able to have Markov-algorithms that does more than 1 repeat (some kind of meta-rule of Markov is that repeat first rule until it's no longer applieable).
So we need to pass the string to operate on to a kind of "doMarkov" macro like this:
(also notation is transformed to polish, prefix here)

Code:

;these should form the rules
_->_    al, lla 
_->_    a, . 
_->_    l, al

doMarkov        llll        ;this line should be transformed by the preprocessor to "llllllll"

(note: I still have no idea how those macros actually look like)

III.] Another big implementation problem is that you need to split the passed identifier to "doMarkov" because you search for the first substring in an identifer, and I'm not sure if such is yet possible in fasm. Consider this pseudocode:

Code:

macro    SomeMacro    A
{
  ;B should be a symbolic constant with a name that is formed by extracting chars 4 to 7 from the other symbolic constant A
  B    equ A[4..7]    
}

Can any macro-guru answer if that is possible?

IV.] What's the purpose of those Markov-algorithms in fasm? Well, you can apply those rules to any string if you want, including all assembler instructions and symbols. You could also extend those Rules to return multiple lines/instructions.

The result of all that is, that you could do stuff like the famous code obfuscating (MazeGen) or compile time code optimizing without changing fasm or coding any external program.

Or code something more fun that assembles to a random program which actually does something (more or less) useful and/or funny, e.g. not just random instructions that crash, hang or immediatly terminate.
I mean you could generate random programs in a very similar way than those did for generating random scientific papers:http://pdos.csail.mit.edu/scigen/
(their program that generates the papers is based upon a context-free grammar, and Markov-algorithms are 1 way to implement those grammars)

That was the longest post I did in 2 years I think Very Happy

_________________
MCD - the inevitable return of the Mad Computer Doggy

-||__/
.|+-~
.|| ||

31 Jan 2007, 17:23

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 06 Feb 2007, 14:06

MCD:

MCD wrote:

Can any macro-guru answer if that is possible?

My answer is: Yes, it's possible to create macros for executing Markov's algorithms!

For a given set of rules:

Code:

al _->_ lla 
a _->_ . 
l _->_ al

I wrote a set of macros which allows to execute these rules ('Markov.inc'):

Code:

; Set of macros which allows realization of Markov's agorithms
; with using FASM preprocessor.
;
; (C) Mikolaj Hajduk, 06.02.2007.
;

; Main macro which realizes execution of Markov's rules for
; a given list of symbols.
;
macro   Markov [args]
{
        common
        
        match     , args \{EXIT\}

        match list, args 
        \{
                DONE equ NO

                match     L,           list \\{ListRule1 L\\}           
                match =NO L, RULE1DONE list \\{ListRule2 L\\}
                match =NO L, RULE2DONE list \\{ListRule3 L\\}
        
                Markov OutputList

                match =YES, DONE \\{EXIT\\}     
        \}
}

; Macro which appends to a given list one or more elements.
;
macro   Append list, [elements]
{
        common
        match L:e, list:elements \{list equ L, e\}
        match  :e, list:elements \{list equ e\}
}

;
; Macros for every Markov's rule.
;

; Macro for 'al _->_ lla' rule.
;
macro   Rule1 char1, char2
{
        Output equ char1, char2

        match =a=l, char1 char2 
        \{
                Output equ l, l, a
                RULE1DONE equ YES
        \}
}

; Macro for 'a _->_ .' rule.
;
macro   Rule2 char
{
        Output equ char

        match =a, char
        \{
                Output equ
                DONE equ YES
                RULE2DONE equ YES
        \}
}

; Macro for 'l _->_ al' rule.
;
macro   Rule3 char
{
        Output equ char

        match =l, char 
        \{
                Output equ a, l
                RULE3DONE equ YES
        \}
}

;
; Macros which execute defined Markov's rules on a whole 
; list of symbols.
;

; Macro executing first rule on a given list of symbols.
;
macro   ListRule1 [p,q]
{
        common
                RULE1DONE equ NO

                OutputList equ

        forward
                match   P:Q, p:q 
                \{
                        match  =YES, RULE1DONE \\{Append OutputList, P, Q\\}

                        match   =NO, RULE1DONE 
                        \\{
                                Rule1 P, Q
                                Append OutputList, Output
                        \\}
                \}

                match   P:, p:q \{Append OutputList, P\}
}

; Macros which execute second and third rules on a given
; list of symbols.
;
rept 2 rn:2
{
        macro   ListRule#rn [list]
        \{

                \common
                        RULE#rn#DONE equ NO

                        OutputList equ

                \forward
                        match   L =YES, list RULE#rn#DONE \\{Append OutputList, L\\}

                        match   L  =NO, list RULE#rn#DONE
                        \\{
                                Rule#rn L
                                Append OutputList, Output
                        \\}
       \}
}

But, of course, there are two limitations:

we operate on lists of symbols, not on strings,
for multiple preprocessing we use special batch file.

Yes, I know, that macros could be executed recursively, but to avoid out of memory error I decided to write special batch file for executing FASM preprocessor in loop ('Markov.bat'):

Code:

rem Batch file which allows realization of Markov's 
rem algorithms in FASM:
rem
rem     - gets data file (from 'data.asm'),
rem     - runs FASM preprocessor in loop, until
rem       'tmp.bat' file doesn't contain word 'EXIT'
rem       (generated by preprocessor after happily
rem       ended data processing).
rem 
rem Result of a given data processing is stored in
rem 'logfile.txt'.
rem
rem
rem (C) Mikolaj Hajduk, 06.02.2007.
rem

copy data.asm tmp1.asm
copy data.asm logfile.txt

:loop
        copy Markov.inc tmp2.asm
        type tmp1.asm >> tmp2.asm

        fasmpre tmp2.asm tmp1.asm 
        fasmpre tmp1.asm tmp2.asm

        type tmp2.asm | find "Markov" >> logfile.txt
        type tmp2.asm | find "EXIT" > tmp.bat 

        call tmp.bat 

        goto loop

For data file 'data.asm':

Code:

Markov l,l,l,l,l

we obtain such output (in 'logfile.txt'):

Code:

Markov l,l,l,l,l
Markov a,l,l,l,l,l
Markov l,l,a,l,l,l,l
Markov l,l,l,l,a,l,l,l
Markov l,l,l,l,l,l,a,l,l
Markov l,l,l,l,l,l,l,l,a,l
Markov l,l,l,l,l,l,l,l,l,l,a
Markov l,l,l,l,l,l,l,l,l,l

I've attached all needed pieces of this 'puzzle'. To run just double click icon of 'Markov.bat' file. Very Happy

Description:	Set of macros and batch file for executing Markov's algorithms with FASM preprocessor.	Download
Filename:	Markov.zip
Filesize:	1.44 KB
Downloaded:	620 Time(s)

06 Feb 2007, 14:06

vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia

vid 06 Feb 2007, 15:28

MHajduk: you can implement condition-delimited loop in FASM by macro which redefines and uses itself. Then, even the batch file is not needed.

06 Feb 2007, 15:28

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 06 Feb 2007, 16:30

vid:
Yes, I know about it. But this technique (recursion http://board.flatassembler.net/topic.php?t=5241) is good for simplier macros. For more complicated I got "out of memory" error. Maybe I should try again. Very Happy

06 Feb 2007, 16:30

vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia

vid 06 Feb 2007, 16:51

well, this is problem of implementation. I wanted to prove that FASM preprocessor design *IS* turing-complete.

EDIT: Sorry, i missed the note that you already knew about that method.

06 Feb 2007, 16:51

Bobee1994

Joined: 03 Nov 2017
Posts: 1
Location: USA

Bobee1994 03 Nov 2017, 10:07

That feel when you always prefer to stay away from Markov algorithm. Not really smooth as for me.

Regards,
William - <snip>.

Edit by revolution: Removed spam link.

03 Nov 2017, 10:07

< Last Thread | Next Thread >

Forum Rules:

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum