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 > Building lists efficiently in fasm

Author
Thread Post new topic Reply to topic
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 14586
Location: Planet Dirt
Building lists efficiently in fasm
Edit: See the message below for an important bug fix to these macros

Building lists efficiently in fasm

The most obvious way to build a list in fasm is to use the equ directive to collect a set of names. Like this:

Code:
.list1_list equ                           ;initialise the list of names

macro .list1 [a] {
        common
      local z
     .list1_list equ .list1_list,z   ;build the list incrementally
       macro z a                       ;open the macro
}

macro list1_list {
    match =,the_list,.list1_list \{
               irp instr,the_list \\{
                       instr           ;replay each line
           \\}
  \}
}

So let's test this with the following command line: "fasm -m 10000 ListBuilder1.asm" (i.e. we limit the memory to 10MB)

Code:
rept 1430 x {
       .list1 \{ db `x,0 \}
}
list1_list


fasm -m 10000 ListBuilder1.asm wrote:

flat assembler version 1.69.24 (10000 kilobytes memory)
1 passes, 6038 bytes.

So far so good. But if we increase the number of repetitions by one more to 1431:

fasm -m 10000 ListBuilder1.asm wrote:
flat assembler version 1.69.24 (10000 kilobytes memory)
error: out of memory.

Not a very good result. Just 6038 bytes of code and using 10MB of memory.

But we can do better. Instead of using equ to build a list of names, instead we can use the rept arithmetic to count the names. thus:

Code:
c equ 0                                     ;initialise the counter

macro .list2 [a] {
      common
      rept 1 x:c+1 \{
           c equ x                 ;update the counter
         macro m\#x a           ;open the macro
     \}
}
macro list2_list {
       rept c x \{
           m\#x                   ;replay each line
   \}
}

So let's test this with the following command line: "fasm -m 10000 ListBuilder2.asm" (i.e. we limit the memory to 10MB)

Code:
rept 13767 x {
      .list2 \{ db `x,0 \}
}
list2_list


fasm -m 10000 ListBuilder2.asm wrote:
flat assembler version 1.69.24 (10000 kilobytes memory)
1 passes, 71496 bytes.

Now we can get 13767 lines using the same 10MB of memory. But there is a catch here, we need to careful about namespace clashes. The macro deliberately uses single character names to save memory, and these names might also be something you are using within your application. So we have just one more thing to add to make the macros play nicely with other label names, we put it into a wrapper macro. This also allows us to easily define more building macros with a single command:

Code:
macro list_builder name {
      local m,c                       ;avoid name clashing
        c equ 0                         ;initialise the counter
     macro .#name [a] \{
           \common
            rept 1 x:c+1 \\{
                 c equ x         ;update the counter
                 macro m\\#x a ;open the macro
             \\}
  \}
    macro name#_list \{
           rept c x \\{
                 m\\#x         ;replay each line
           \\}
  \}
}
list_builder list2

This costs us a little bit of memory but we still get 13480 lines with the same memory usage:

Code:
rept 13480 x {
     .list2 \{ db `x,0 \}
}
list2_list


fasm -m 10000 ListBuilder3.asm wrote:
flat assembler version 1.69.24 (10000 kilobytes memory)
1 passes, 69774 bytes.

And now we can build multiple different lists:

Code:
macro list_builder name {
        local m,c                       ;avoid name clashing
        c equ 0                         ;initialise the counter
     macro .#name [a] \{
           \common
            rept 1 x:c+1 \\{
                 c equ x         ;update the counter
                 macro m\\#x a ;open the macro
             \\}
  \}
    macro name#_list \{
           rept c x \\{
                 m\\#x         ;replay each line
           \\}
  \}
}

;define some lists

list_builder string
list_builder data
list_builder init
list_builder stuff

;put some stuff into the lists

.string    { str1db 'Hello world!',0 }
.data  { var1 dd ? }
.init        { mov [var1],-1 }
.stuff   {
      nop
 rep movsb
   ret
}

.string    { str2db 'Bye bye world',0 }
.data { var2 dd ? }
.init        { mov [var2],-2 }

;place the defined data into the assembly stream

init_list
stuff_list
data_list
string_list



Edit: See the message below for an important bug fix to these macros


Last edited by revolution on 07 Mar 2017, 07:13; edited 3 times in total
Post 04 Oct 2010, 06:34
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar
Assembly Artist


Joined: 16 Jun 2003
Posts: 6253
Location: Kraków, Poland
You can decrease the memory usage further by reducing the number of empty lines generated:

Code:
macro list_builder name {
        local m,c
        c equ 0
        macro .#name [a] \{ 
                \common 
                rept 1 x:c+1 \\{ c equ x
                                 macro m\\#x a \\}
        \} 
        macro name#_list \{ 
                rept c x \\{ m\\#x \\}
        \} 

list_builder list2 

This way it goes up 15311.

And some other interesting version would be to use the numbered lists:

Code:
c equ 0

macro .listx id,[a] {
        common 
        rept 1 x:c+1,y:id*1000000+c+1 \{ c equ x
                                         macro m\#y a \}

macro listx_list id {
        rept c y:id*1000000+1 \{ m\#y \}
}



PS. Yes, I see that those empty lines in preprocessor is something that perhaps deserves optimizing. You would then not get those lines in the preprocessed source in .fas file, but would that really be a problem?
Post 04 Oct 2010, 07:58
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 14586
Location: Planet Dirt
Extreme unreadableness and maximum number of lines:

Code:
macro b n{local m,c
c equ 0
macro .#n[a]\{\common rept 1 x:c+1\\{c equ x
macro m\\#x a\\}\}macro n#_\{rept c x\\{m\\#x\\}\}}
b l
rept 19350 x{.l\{db`x,0\}}l_


fasm -m10000 ListBuilderObfuscated.asm wrote:
flat assembler version 1.69.24 (10000 kilobytes memory)
1 passes, 104994 bytes.

And, yeah, I vote to take the blank lines out of the fas file.
Post 04 Oct 2010, 08:55
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 14586
Location: Planet Dirt
Latest fasm version 1.69.25

WHATSNEW.TXT wrote:
version 1.69.25 (Oct 11, 2010)

[-] Macroinstructions no longer breed the lines that are empty in their
definitions.
...

Post 16 Oct 2010, 03:22
View user's profile Send private message Visit poster's website Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7111
Location: Slovakia
So, what's the top score so far? Smile
Post 16 Oct 2010, 08:55
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 14586
Location: Planet Dirt
Just for vid:

Code:
                            1.69.24 1.69.25
ListBuilder1.asm             1430    1450
ListBuilder2.asm                13767   19693
ListBuilderMacro.asm           13480   19111
ListBuilderTomasz.asm          15311   19996
ListBuilderObfuscated.asm      19350   20205

Post 16 Oct 2010, 12:41
View user's profile Send private message Visit poster's website Reply with quote
sid123



Joined: 30 Jul 2013
Posts: 340
Location: Asia, Singapore
List building macros
Hello,
I read this post by revolution, which introduces list building functionality in fasm through macros (http://board.flatassembler.net/topic.php?t=12012). I'm using them to store sections in proper order in my program, and here's how the header looks like:

Code:

; Changed the name to not make it look out of context
macro DECLARE_SECTION name {
        local m,c
        c equ 0
        macro .#name [a] \{ 
                \common 
                rept 1 x:c+1 \\{ c equ x
                                 macro m\\#x a \\}
        \} 
        macro STORE_SECTION_#name \{ 
                rept c x \\{ m\\#x \\}
        \} 
}
DECLARE_SECTION text
DECLARE_SECTION data
DECLARE_SECTION bss
_text:
        STORE_SECTION_text
_end_text:
_data:
        STORE_SECTION_data
_end_data:
_bss:
        STORE_SECTION_bss
_end_bss:



However I have a problem, this works fine when I have something like this:

Code:
 .text \{ mov ax0xff \}


But as soon as I go multi-line...

Code:
.text \{
mov ax0xff
mov bx0xfe
; Just a random example
\}



FASM shows an error displaying:

Quote:
.text \{
<filename> [line] .text [line]:
macro m\\#x a ;open the macro
<filename> [line] rept [line]:
macro m\\#x a ;open the macro
error: incomplete macro.


_________________
"Those who can make you believe in absurdities can make you commit atrocities" -- Voltaire https://github.com/Benderx2/R3X
XD
Post 30 Dec 2014, 03:58
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 14586
Location: Planet Dirt
Don't use the backslash (\) unless the line it is inside another macro.

Moved last post and this post into the actual topic.
Post 30 Dec 2014, 06:03
View user's profile Send private message Visit poster's website Reply with quote
sid123



Joined: 30 Jul 2013
Posts: 340
Location: Asia, Singapore
Thanks revolution, works fine now!
Post 30 Dec 2014, 09:01
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 14586
Location: Planet Dirt
Just to be clear: For both cases you posted (single line and multi-line) there should be no backslash.
Post 30 Dec 2014, 09:12
View user's profile Send private message Visit poster's website Reply with quote
l_inc



Joined: 23 Oct 2009
Posts: 868
I hope, it's clear that newer fasm capabilities allow for a more efficient usage of memory than the provided macros do. Only the ampersand-feature allows to increase the number of strings by a couple of thousands. If we combine that with an irpv based counter, we could get over 30k:

Code:
macro list_builder name
{
    local c,m
    macro name a&
    \{
        c equ
        macro m a
    \}
    macro name#.put \{irpv v,c \\{m
    purge m\\} \}
}
list_builder list1
rept 32496 x
{
    list1 \{ db`x,0 \}
}
list1.put


An "obfuscated" version:

Code:
macro b n{local c,m
macro n a&\{c equ
macro m a\}macro n#_\{irpv v,c\\{m
purge m\\}\}}
b l
rept 33053 x {l\{db`x,0\}}l_



It should be noted however, that the usage of purge significantly increases the compilation time.

_________________
Faith is a superposition of knowledge and fallacy
Post 30 Dec 2014, 15:21
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 14586
Location: Planet Dirt
Cool A nice use of the new capabilities.
Post 30 Dec 2014, 15:32
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 14586
Location: Planet Dirt

l_inc wrote:
I hope, it's clear that newer fasm capabilities allow for a more efficient usage of memory than the provided macros do. Only the ampersand-feature allows to increase the number of strings by a couple of thousands. If we combine that with an irpv based counter, we could get over 30k:

Code:
macro list_builder name
{
    local c,m
    macro name a&
    \{
        c equ
        macro m a
    \}
    macro name#.put \{irpv v,c \\{m
    purge m\\} \}
}
list_builder list1
rept 32496 x
{
    list1 \{ db`x,0 \}
}
list1.put


I just realised that this outputs the list in reverse order! So be careful what you use this version for. It may, or may not, be a desired feature.
Post 31 Dec 2014, 03:14
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 14586
Location: Planet Dirt
So using the new irpv and & syntaxes we can do this for a forward ordered list:

Code:
macro list_builder name {
        local c
        macro .#name a& \{
                \local m
                c equ m
                macro m a
        \}
        macro name#_list \{
                irpv v,c \\{
                        v
                \\}
        \}
}
list_builder list1
rept 19814 x {
        .list1 \{
                db `x,0
        \}
}
list1_list

And with a small addition of reverse in the right place we can also do it in reverse:

Code:
macro reverse_list_builder name {
        local c
        macro .#name a& \{
                \local m
                c equ m
                macro m a
        \}
        macro name#_list \{
                irpv v,c \\{
                        \\reverse
                        v
                \\}
        \}
}
reverse_list_builder list2
rept 19813 x {
        .list2 \{
                db `x,0
        \}
}
list2_list

Post 31 Dec 2014, 03:28
View user's profile Send private message Visit poster's website Reply with quote
baldr



Joined: 19 Mar 2008
Posts: 1651
revolution,

irpv effectively makes list building efforts unnecessary, unless you have to index into that list.
Post 31 Dec 2014, 08:33
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 14586
Location: Planet Dirt

baldr wrote:
revolution,

irpv effectively makes list building efforts unnecessary, unless you have to index into that list.

Yes, it makes things simpler and clearer. But there is still a need to nicely wrap it in some macro to make it not too much of a pain to use. At least now we have the luxury of hindsight.
Post 31 Dec 2014, 09:37
View user's profile Send private message Visit poster's website Reply with quote
l_inc



Joined: 23 Oct 2009
Posts: 868
revolution

Quote:
I just realised that this outputs the list in reverse order!


I know. Smile

Quote:
It may, or may not, be a desired feature.


I'd assume in most cases it's irrelevant rather than desired or not. But I must admit I'd prefer it to be in forward order.

Quote:
So using the new irpv and & syntaxes we can do this for a forward ordered list


That was my first version, but it didn't beat the best scores. So I gave up on it. It would be cool to find a way for forward ordering with a score over 30k.

_________________
Faith is a superposition of knowledge and fallacy
Post 31 Dec 2014, 12:58
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 14586
Location: Planet Dirt

l_inc wrote:
I'd assume in most cases it's irrelevant rather than desired or not. But I must admit I'd prefer it to be in forward order.

Quite a dangerous assumption IMO. I'd imagine most people would expect it to be forward unless otherwise stated.

l_inc wrote:
It would be cool to find a way for forward ordering with a score over 30k.

Sure. Although the current versions are O(n) so any further improvements are only squeezing more out of the hidden c factor.
Post 31 Dec 2014, 14:34
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 14586
Location: Planet Dirt
Bug fix for the original macros
I recently encountered a problem with some list builder code using the latest version of fasm. There is a name clash with the local name being concatenated with the counter. Previous versions of fasm would generate local names by appending a fixed length counter. Something like 'm' becoming 'm?0000123'. But current versions append a variable length string. Something like 'm' becoming 'm?B6p'. So when appending the counter we can have name clashes. So 'm?A34' could be either the base name 'm?A3' with '4' appended, or be the base name 'm?A' with '34' appended.

To fix this I added an underscore (_) within the concatenation:

Code:
macro list_builder name {
        local m,c                       ;avoid name clashing
        c equ 0                         ;initialise the counter
        macro .#name [a] \{
                \common
                rept 1 x:c+1 \\{
                        c equ x         ;update the counter
                        macro m#_\\#x a ;open the macro
                \\}
        \}
        macro name#_list \{
                rept c x \\{
                        m#_\\#x         ;replay each line
                \\}
        \}
}

Now I have to hope that future versions of fasm won't decide to use the underscore as part of the localised strings.

As an aside, why does the forum code keep altering the tabs within messages and making old posts appear unaligned and ugly?
Post 07 Mar 2017, 07:25
View user's profile Send private message Visit poster's website 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.