flat assembler
Message board for the users of flat assembler.

 flat assembler > Macroinstructions > Markov-algorithms with fasm :shock:
Author
MCD

Joined: 21 Aug 2004
Posts: 604
Location: Germany
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

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: 7108
Location: Slovakia
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: 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
_->_    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

_________________
MCD - the inevitable return of the Mad Computer Doggy

-||__/
.|+-~
.|| ||
31 Jan 2007, 17:23
MHajduk

Joined: 30 Mar 2006
Posts: 5994
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 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.

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

06 Feb 2007, 14:06
vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7108
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.
06 Feb 2007, 15:28
MHajduk

Joined: 30 Mar 2006
Posts: 5994
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.
06 Feb 2007, 16:30
vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7108
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.
06 Feb 2007, 16:51
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.
03 Nov 2017, 10:07
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsCompiler InternalsIDE DevelopmentOS ConstructionNon-x86 architecturesHigh Level LanguagesProgramming Language DesignProjects and IdeasExamples and Tutorials Other----------------FeedbackHeapTest Area

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