flat assembler
Message board for the users of flat assembler.
 Home   FAQ   Search   Register 
 Profile   Log in to check your private messages   Log in 
flat assembler > Macroinstructions > Markov-algorithms with fasm :shock:

Author
Thread Post new topic Reply to topic
MCD



Joined: 21 Aug 2004
Posts: 604
Location: Germany
Markov-algorithms with fasm :shock:
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

-||__/
.|+-~
.|| ||
Post 31 Jan 2007, 11:33
View user's profile Send private message Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7109
Location: Slovakia

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


that would mean you can make x86 emulator with FASM macros? :]
Post 31 Jan 2007, 12:18
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
MCD



Joined: 21 Aug 2004
Posts: 604
Location: Germany

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
_->_    allla 
_->_    a. 
_->_    lal

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

-||__/
.|+-~
.|| ||
Post 31 Jan 2007, 17:23
View user's profile Send private message Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 5921
Location: Poland
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 listargs 
        \{
                DONE equ NO

                match     L,           list \\{ListRule1 L\\}           
                match =NO LRULE1DONE list \\{ListRule2 L\\}
                match =NO LRULE2DONE list \\{ListRule3 L\\}
        
                Markov OutputList

                match =YESDONE \\{EXIT\\}     
        \}
}

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

;
; Macros for every Markov's rule.
;

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

        match =a=lchar1 char2 
        \{
                Output equ lla
                RULE1DONE equ YES
        \}
}

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

        match =achar
        \{
                Output equ
                DONE equ YES
                RULE2DONE equ YES
        \}
}

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

        match =lchar 
        \{
                Output equ al
                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:Qp:q 
                \{
                        match  =YESRULE1DONE \\{Append OutputListPQ\\}

                        match   =NORULE1DONE 
                        \\{
                                Rule1 PQ
                                Append OutputListOutput
                        \\}
                \}

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

; 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 =YESlist RULE#rn#DONE \\{Append OutputListL\\}

                        match   L  =NOlist RULE#rn#DONE
                        \\{
                                Rule#rn L
                                Append OutputListOutput
                        \\}
       \}
}


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 loopuntil
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 (CMikolaj Hajduk06.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: 31 Time(s)

Post 06 Feb 2007, 14:06
View user's profile Send private message Send e-mail Visit poster's website Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7109
Location: Slovakia
MHajduk: you can implement condition-delimited loop in FASM by macro which redefines and uses itself. Then, even the batch file is not needed.
Post 06 Feb 2007, 15:28
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 5921
Location: Poland
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
Post 06 Feb 2007, 16:30
View user's profile Send private message Send e-mail Visit poster's website Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7109
Location: Slovakia
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.
Post 06 Feb 2007, 16:51
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
Bobee1994



Joined: 03 Nov 2017
Posts: 1
Location: USA
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.
Post 03 Nov 2017, 10:07
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< 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


Powered by phpBB © 2001-2005 phpBB Group.

Main index   Download   Documentation   Examples   Message board
Copyright © 2004-2016, Tomasz Grysztar.