Building lists efficiently in fasm

Index > Macroinstructions > Building lists efficiently in fasm

Author

Thread

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20299
Location: In your JS exploiting you and your system

revolution 04 Oct 2010, 06:34

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    { str1: db 'Hello world!',0 }
.data  { var1 dd ? }
.init        { mov [var1],-1 }
.stuff   {
      nop
 rep movsb
   ret
}

.string    { str2: db '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 21 Jul 2020, 11:32; edited 4 times in total

04 Oct 2010, 06:34

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8351
Location: Kraków, Poland

Tomasz Grysztar 04 Oct 2010, 07:58

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?

04 Oct 2010, 07:58

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20299
Location: In your JS exploiting you and your system

revolution 04 Oct 2010, 08:55

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.

04 Oct 2010, 08:55

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20299
Location: In your JS exploiting you and your system

revolution 16 Oct 2010, 03:22

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.
...

16 Oct 2010, 03:22

vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia

vid 16 Oct 2010, 08:55

So, what's the top score so far? Smile

16 Oct 2010, 08:55

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20299
Location: In your JS exploiting you and your system

revolution 16 Oct 2010, 12:41

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

16 Oct 2010, 12:41

sid123

Joined: 30 Jul 2013
Posts: 339
Location: Asia, Singapore

sid123 30 Dec 2014, 03:58

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 ax, 0xff \}

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

Code:

.text \{
mov ax, 0xff
mov bx, 0xfe
; 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

30 Dec 2014, 03:58

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20299
Location: In your JS exploiting you and your system

revolution 30 Dec 2014, 06:03

Don't use the backslash (\) unless the line it is inside another macro.

Moved last post and this post into the actual topic.

30 Dec 2014, 06:03

sid123

Joined: 30 Jul 2013
Posts: 339
Location: Asia, Singapore

sid123 30 Dec 2014, 09:01

Thanks revolution, works fine now!

30 Dec 2014, 09:01

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20299
Location: In your JS exploiting you and your system

revolution 30 Dec 2014, 09:12

Just to be clear: For both cases you posted (single line and multi-line) there should be no backslash.

30 Dec 2014, 09:12

l_inc

Joined: 23 Oct 2009
Posts: 881

l_inc 30 Dec 2014, 15:21

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

30 Dec 2014, 15:21

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20299
Location: In your JS exploiting you and your system

revolution 30 Dec 2014, 15:32

A nice use of the new capabilities.

30 Dec 2014, 15:32

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20299
Location: In your JS exploiting you and your system

revolution 31 Dec 2014, 03:14

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.

31 Dec 2014, 03:14

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20299
Location: In your JS exploiting you and your system

revolution 31 Dec 2014, 03:28

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

31 Dec 2014, 03:28

baldr

Joined: 19 Mar 2008
Posts: 1651

baldr 31 Dec 2014, 08:33

revolution,

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

31 Dec 2014, 08:33

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20299
Location: In your JS exploiting you and your system

revolution 31 Dec 2014, 09:37

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.

31 Dec 2014, 09:37

l_inc

Joined: 23 Oct 2009
Posts: 881

l_inc 31 Dec 2014, 12:58

revolution

Quote:

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

I know.

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

31 Dec 2014, 12:58

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20299
Location: In your JS exploiting you and your system

revolution 31 Dec 2014, 14:34

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.

31 Dec 2014, 14:34

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20299
Location: In your JS exploiting you and your system

revolution 07 Mar 2017, 07:25

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?

07 Mar 2017, 07:25

< 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