flat assembler
Message board for the users of flat assembler.

Index > Macroinstructions > list macros : check for uniqueness

Author
Thread Post new topic Reply to topic
pini



Joined: 04 Jul 2005
Posts: 14
pini
Hi,

I have the following macros for handling list-like structures:

Code:
macro list_new [name*]
{
   forward
      name equ
}

macro list_append list*, [item*]
{
   forward
      list equ list, item
}

macro list_foreach list*, action*
{
   local lst
   match =,lst, list
   \{
      \local item
      \irp item, lst
      \\{
         action item
      \\}
   \}
}
    


And they do fine. I'm now trying to have a macro to add an element to a list only if it's not there already. I'm stuck with the following:

Code:
macro list_insert list*, [item*]
{
   forward
      local has
      ; find
      has = 0
      macro equal it*
      \{
         if it eq item
            has = 1
         end if
      \}
      list_foreach list, equal
      ; append
      if has = 0
         display "insert: ", `item, 10
         list_append list, item
      end if
}
    


When using it, I see the "insert: " lines correctly, but all items are added to the list regardless of the test of "has".

I suppose this is due to the macro expansion of list_append in the if block, which is made of an equ (so preprocess stage VS assembly stage).

I couldn't figure a way to get it to work, can somebody help?

Thanks.
Post 14 Jul 2012, 22:09
View user's profile Send private message Reply with quote
JohnFound



Joined: 16 Jun 2003
Posts: 3502
Location: Bulgaria
JohnFound
Forget about "if".
Post 15 Jul 2012, 05:38
View user's profile Send private message Visit poster's website ICQ Number Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17450
Location: In your JS exploiting you and your system
revolution
You might need to check your use of common when handing the comma separated lists.

Also check that you have correctly enclosed all the macro parameters with angle brackets <> to ensure you get the proper things processed at the right time.
Post 15 Jul 2012, 06:01
View user's profile Send private message Visit poster's website Reply with quote
Kazyaka



Joined: 10 Oct 2011
Posts: 62
Location: Earth
Kazyaka
Look at my idea (I don't know why it doesn't work correctly):
Code:
    macro append list*, [item*]
     {
       match any, list \{
       if ~ item in <list>
       list equ list,item
       end if
       \}
       match , list \{ list equ item \}
     } 
    
Post 15 Jul 2012, 09:07
View user's profile Send private message Reply with quote
JohnFound



Joined: 16 Jun 2003
Posts: 3502
Location: Bulgaria
JohnFound
Kazyaka wrote:
Look at my idea (I don't know why it doesn't work correctly):


Because of the "if". It is not executed in the preprocessor. For the preprocessor your macro looks (approximately) this way:
Code:
    macro append list*, [item*]
     {
       match any, list \{
       list equ list,item
       \}
       match , list \{ list equ item \}
     } 
    


Unfortunately, creation of unique lists is almost impossible in FASM. I tried it many times with two ends: "The trick does not work" and "The trick works extremely slow"
For the "extremely slow" solutions you can see the big commented section in this file and read the notes about this issue in the reference manual.

_________________
Tox ID: 48C0321ADDB2FE5F644BB5E3D58B0D58C35E5BCBC81D7CD333633FEDF1047914A534256478D9
Post 15 Jul 2012, 10:17
View user's profile Send private message Visit poster's website ICQ Number Reply with quote
pini



Joined: 04 Jul 2005
Posts: 14
pini
Thanks for all your replies. I figured a way out:

Code:
macro list_insert list*, [item*]
{
   forward
      local has
      ; find
      has equ no
      macro equal it*
      \{
         \match =it, item
         \\{
            has equ yes
         \\}
      \}
      list_foreach list, equal
      ; append
      match =no, has
      \{
         list_append list, item
      \}
}
    


This seems to work pretty well.

@John: you stated that creation of lists with unique elements is almost impossible, do you see if the above macro behaves wrongly in some cases?

Cheers.
Post 15 Jul 2012, 13:11
View user's profile Send private message Reply with quote
JohnFound



Joined: 16 Jun 2003
Posts: 3502
Location: Bulgaria
JohnFound
pini, I will try your solution.
I am not so good in the FASM macros, so it is very possible my opinion about "almost impossible" is wrong. Smile
Post 15 Jul 2012, 14:13
View user's profile Send private message Visit poster's website ICQ Number Reply with quote
Kazyaka



Joined: 10 Oct 2011
Posts: 62
Location: Earth
Kazyaka
I'm beginner so it took me a lot of time. But it works!

Try this:
Code:
; Adding unique items to list
; by Kazyaka

macro ListAddItem list*, item*
{
 match , list \{ list equ item \}
 match params, list
 \{
 ListAddUniqueItem list, item, params
 \}
}

macro ListAddUniqueItem list*, newItem*, [oldItem*]
{
rep equ no
 forward
 match  newItem, oldItem
 \{
 rep equ yes
 \}
common
 match  =no, rep
 \{
 list equ list, newItem
 \}
}

MyList equ

ListAddItem MyList, 'a'
ListAddItem MyList, 'b'
ListAddItem MyList, 'c'
ListAddItem MyList, 'b'

display MyList
    
Post 15 Jul 2012, 15:39
View user's profile Send private message Reply with quote
pini



Joined: 04 Jul 2005
Posts: 14
pini
@Kazyaka: I came up with a similar solution (see above). I think your proposal does not work as is. You should replace

Code:
match  newItem, oldItem    


by

Code:
match =newItem, oldItem ; <- add an '='    


otherwise oldItem will always be matched by newItem (newItem will be considered as a matcher for any symbol). With the '=' prepended, the value of newItem is substituted and the result is considered for value matching with oldItem.

Cheers.
Post 15 Jul 2012, 18:17
View user's profile Send private message Reply with quote
JohnFound



Joined: 16 Jun 2003
Posts: 3502
Location: Bulgaria
JohnFound
The great idea in your solutions is that the new element has to be checked for presence in the list on the including. All my attempts till now was "add everything and then use only the unique elements".

BTW, using symbolic constants for lists is proved to be slow when the list grows. I use another type of lists with indexed constants:
Code:
macro __InitStringsEngine {
local c, r, v

   c equ 0

  struc text [val] \{
    \common
    \local flag

    \flag equ

    rept c x \\{
       match val, v\\#x \\\{
         flag equ r\\\#x
       \\\}
    \\}

    match lbl, flag \\{
      if defined lbl
        . = lbl
        .len = lbl\\#\\.len
      end if
    \\}

    match , flag \\{
      rept 1 x:c+1 \\\{
        c equ x
        r\\\#x equ .
        v\\\#x equ val
      \\\}
    \\}
  \}


  macro __IncludeAllStrings \{
  \common
    rept c x \\{
        r\\#x db v\\#x
        .len = $-r\\#x
             db 0
             rb ($ + 3) and $fffffffc - $
    \\}
  \}
}

__InitStringsEngine

str1 text 'text1', $0d, $0a
str2 text 'text2'
str3 text 'text3'
str4 text 'text4'
str5 text 'text2'
str6 text 'text2'
str7 text 'text1', $0d, $0a

__IncludeAllStrings
    


The only problem is with the strings that contains "," - like str1 and str7.
They both will be added to the list, because "match" can't match items containing comma.
The above example should create 38 bytes output file, but it creates 46 bytes.

@pini: when the elements of the "match" are strings, there is no need to be matched with "=". The FASM manual states it clearly.

Anyway, it is a great advance. Thanks for the idea!

_________________
Tox ID: 48C0321ADDB2FE5F644BB5E3D58B0D58C35E5BCBC81D7CD333633FEDF1047914A534256478D9
Post 15 Jul 2012, 21:02
View user's profile Send private message Visit poster's website ICQ Number Reply with quote
baldr



Joined: 19 Mar 2008
Posts: 1651
baldr
JohnFound wrote:
The only problem is with the strings that contains ","
Strings do not contain ",", those commas are part of list representing them. Anyway, it's not a problem at all: proper use of <> to delimit items can remedy the issue.
Code:
directive fix struc; since here they aren't 'struc's in any sense

directive reEqu [value] {
; Sets symbolic to 'value' while keeping 'restore' stack clean
common
  match _value, value \{; accounts for 'value' containing references to '.'
    restore .; without 'match' this will clobber 'value' if it refers to '.'
    . equ _value
  \}
}

directive add [value*] {
; Adds 'value's as separate items
  match =., . \{ . equ \}; initialize list if not already
  match some, . \{ . reEqu some, <value> \}; append if not empty
  match , . \{ . reEqu <value> \}; set if empty (guess why not 2 lines earier Wink
}

directive addItem [value*] {
; Helper macro: adds 'value' as single item
common . add <value>
}

directive forEach action*, [args] {
; Generic iterator - invokes 'action' for each item in 'list', passing additional 'args'
common
  match _., . \{; because 'irp' doesn't expand symbolics in list of parameters
    irp item, _. \\{
      action <item>, args
    \\}
  \}
}

directive escape symbol*, [items*] {
; Helper macro: escape each token in 'items' with 'symbol'
common; used instead of implicit 'forward' to ignore "first comma" case
  . equ
  match _items, items \{
    irps item, items \\{
      match _., . \\\{ . reEqu _. symbol item \\\}
      match , . \\\{ . equ symbol item \\\}
    \\}
  \}
}

macro ifMatch x*, y*, action* {
; Pretty convoluted macro, follow the comments
  _x escape =, x; escape tokens for 'match'
  match __x, _x \{; expand escaped 'x'
    singleToken equ +; assume 'y' is single token
    match =<anything=>, y \\{
    ; multiple-token 'y' - matching 'x' is already unwrapped, so wrap it again
      match =<__x=>, y \\\{ action \\\}
      restore singleToken; signal that 'y' is processed
    \\}
    match +, singleToken \\{
    ; 'y' is not processed yet, so it's single token
      match __x, y \\\{ action \\\}
      restore singleToken; clean-up
    \\}
  \}
  restore _x
}

directive addUnique [item*] {
; Adds 'item's if not already in list
  found equ -
  . forEach ifMatch, <item>, found reEqu +
  match -, found \{ . add item \}
  restore found; depends on 'reEqu' for proper cleanup
}

directive addUniqueItem [value*] {
; Helper macro: adds unique 'value' as single item
common
  . addUnique <<value>>; twice because each macro invocation unwraps arguments
                       ; and 'add' macro invocation is two levels deeper
}

directive unwrap item*, [args] {
; Helper macro: removes <>, optionally appending 'args'
common
  match , args \{ . item \}
  match some, args \{ . item, args \}
}

strings addItem "Hello, world!", 13, 10
strings addItem "Goodbye, world!", 13, 10

bytes add 1, 2, 3
bytes add 9, 8, 7, <"The answer", 42>
bytes addUnique 2, 5; adds only 5
; 'ifMatch' madness is all about this case:
bytes addUniqueItem "The answer", 42

db "Here it starts:", 13, 10
strings forEach db unwrap, "|"; without 'unwrap' 'db' directive will fail due to <>s
bytes forEach db unwrap, "."    
This code isn't thoroughly tested -- caveat emptor.
Post 27 Jul 2012, 16:23
View user's profile Send private message Reply with quote
JohnFound



Joined: 16 Jun 2003
Posts: 3502
Location: Bulgaria
JohnFound
baldr, awesome work! This source is almost out of my understanding of FASM macros. I have to meditate on it at least two days. Smile

What about using numbered type of lists (as in my code above)? They are proved to be more effective on big lists.
Post 27 Jul 2012, 19:30
View user's profile Send private message Visit poster's website ICQ Number Reply with quote
baldr



Joined: 19 Mar 2008
Posts: 1651
baldr
JohnFound,

It can be done too.
Code:
directive fix struc

directive reEqu [value] {
common
  match _value, value \{; expand to protect from 'restore'
    restore .
    . equ _value
  \}
}

directive add [item*] {
  match _count, .count \{; expand list.count
    .#\.\#_count equ item; second dot should be protected from 'struc' expansion
    rept 1 count:_count+1 \\{ .count reEqu count \\}; increment counter
  \}
}

directive forEach action* {
  rept .count index:0 \{
    match <item>, <.#\.\#index> \\{; retrieve item
      action item; apply action (it may have own arguments, then add comma as done below)
    \\}
  \}
}

directive escape [list] {
; Escape tokens with = for exact 'match'
common
  . equ
  irps token, list \{ . reEqu . =token \}
}

macro _match literal*, body*, [value*] {
; Helper macro to use with 'forEach'
common
  match literal, value \{ body \}
}

directive addUnique [item*] {
  found equ -; assume not found
  .item escape item
  match _item, .item \{
    . forEach <_match <_item>, restore found,>; last comma is important
  \}
  match -, found \{
    .add <item>
    restore found
  \}
}

macro newList name* {
  name#.count equ 0; initialize counter
  macro name#.add [item*] \{ common name add item \}
  macro name#.addUnique [item*] \{ common name addUnique item \}
  macro name#.forEach action* \{ common name forEach action \}
}

newList strings
strings.add <"Hi there!", 10, 0>, <"Regards, baldr.", 10, 0>
strings.addUnique <"Hi there!", 10, 0>, <"Regards, baldr.", 10, 0>,\
  <"P.S. And thanks for all the fish.", 10, 0>
strings.forEach db    
forEach really needs some lambda notation for its argument. I don't have clean solution yet (existing is plagued with extra backslashing).
Post 28 Jul 2012, 11:27
View user's profile Send private message Reply with quote
JohnFound



Joined: 16 Jun 2003
Posts: 3502
Location: Bulgaria
JohnFound
Hi baldr. Based on your macros I almost managed to make these unique strings macros to work exactly as I wanted. They will be added in the next release of FreshLib and your nickname will be mentioned. (If you want some other name/text to stay in the sources, please let me know).

Regards.
Post 28 Jul 2012, 13:25
View user's profile Send private message Visit poster's website ICQ Number Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2936
Location: vpcmipstrm
bitRAKE
baldr, I'm still trying to better understand these macros. Yet, they seem to be working well.
Code:
macro imports { common
  local ..first

  macro P3 [A*] \{
    match B,A \\{
      irp api,B \\\{
        .\\\#api dq RVA api\\\#_STR
      \\\}
    \\}
  \}
  macro P2 [A*] \{
    match B,A \\{
      irp api,B \\\{
        rb 2 - RVA $ AND 1
        label api\\\#_STR at $-2
        db \\\`api
      \\\}
    \\}
  \}
  macro P1 [A*] \{
    match lib,A \\{
      rb (8 - RVA $ AND 7) AND ..first
      ..first = 15
      lib:
      P3 DLL_\\#lib
    \\}
  \}
  macro P0 [A*] \{
    match lib,A \\{
      lib\\#_STR db \\`lib
      P2 DLL_\\#lib
    \\}
    db 0
  \}
  macro P5 lib*,[dummy] \{
    dd 0,0,0,RVA lib\#_STR,RVA lib
  \}

  ..first = 7
  DLL forEach P0,<>
  DLL forEach P1,<>
  data import
    DLL forEach P5,<>
    rd 5
  end data
  purge P0,P1,P2,P3,P5
}

macro call [A] { common
  match =[B C=],A \{
    DLL addUnique B
    DLL_\#B addUnique C
    call [B\#.\#C]
  \}
}

format PE64 CONSOLE 6.0 at $10000
section '' readable writeable executable
    entry $
    enter 32,0
    call [kernel32 GetCommandLineW]
    xchg rcx,rax
    lea edx,[rbp] ; #32#
    jrcxz .exit
    call [shell32 CommandLineToArgvW]
    mov [rbp+8],rax

    ; do something interesting...

    mov rcx,[rbp+8]
    call [kernel32 LocalFree]
.exit:
    leave
    call [kernel32 ExitProcess]

imports    
Thank you.

p.s. My sense is that I'm miss using them. As I couldn't get the forEach to work in P0/P1 - resulting in breaking down the <>'s in P2/P3.

_________________
¯\(°_o)/¯ unlicense.org
Post 27 Apr 2013, 07:42
View user's profile Send private message Visit poster's website Reply with quote
baldr



Joined: 19 Mar 2008
Posts: 1651
baldr
bitRAKE,

forEach doesn't work because it's not recursive (i.e. action can't directly or indirectly use forEach). That can be fixed. Your case doesn't need such complex macros (list items are simple symbols), something like following will do:
Code:
;;; simpleList.finc

struc newList {
  .count equ 0; list is empty
  .index equ 0; 'find' hasn't found item
  macro .find item \{ . find item \}
}

struc reequ [value] {
; Helper macro: replace symbolic's value
common
  restore .
  . equ value
}

struc reequ! [expression] {
; Helper macro: replace symbolic's value with that of expression
common
  rept 1 value:expression \{ . reequ value \}
}

struc add [item*] {
; Unconditionally add item to list
  .count reequ! .count+1
  match _count, .count \{ .\#\.\#_count equ item \}
}

struc find item* {
; Find item in list; set '.index' to its index (or 0 if not found)
  .index reequ 0
  rept .count index \{
    match =item, .\#\.\#index \\{ .index reequ index \\}
  \}
}

struc addUnique [item*] {
  .find item
  match =0, .index \{ . add item \}
}

macro define_recursive_forEach {
  struc forEach list \{
    define_recursive_forEach
    rept list\#\\.count index \\{
      match item, list\#\\.\\#index \\\{ . item \\\}
    \\}
    purge forEach
  \}
} define_recursive_forEach    
Code:
include "simpleList.finc"

DLL newList

macro imports { common
  local first

  first = 7
  macro make_hint_names name* \{
    rb 2 - rva $ and 1
    label name\#.hint at $-2
    db \`name
  \}

  macro make_names lib* \{
    lib\#.name db \`lib
    \\\make_hint_names forEach DLL_\#lib
    db 0
  \}

  macro make_iat_entry name* \{ .\#name dq rva name\#.hint \}

  macro make_iat lib* \{
    rb (8 - rva $ and 7) and first
    first = 15
    lib: \\\make_iat_entry forEach DLL_\#lib
  \}

  macro make_import_directory_entry lib* \{
    dd 0, 0, 0, RVA lib\#.name, RVA lib
  \}

  \\make_names forEach DLL
  \\make_iat forEach DLL
  data import
    \\make_import_directory_entry forEach DLL
    rd 5
  end data
  purge make_hint_names, make_names, make_iat_entry, make_iat, make_import_directory_entry
}

macro call [A] { common
  match =[B C=],A \{
    DLL addUnique B
    match =0, DLL.index \\{ DLL_\#B newList \\}
    DLL_\#B addUnique C
    call [B\#.\#C]
  \}
}

format PE64 CONSOLE 6.0 at $10000
section '' readable writeable executable
    entry $
    enter 32,0
    call [kernel32 GetCommandLineW]
    xchg rcx,rax
    lea edx,[rbp] ; #32#
    jrcxz .exit
    call [shell32 CommandLineToArgvW]
    mov [rbp+8],rax

    ; do something interesting...

    mov rcx,[rbp+8]
    call [kernel32 LocalFree]
.exit:
    leave
    call [kernel32 ExitProcess]

imports    
I've changed forEach invocation syntax to action forEach list because list forEach action looks slightly like Yoda-speak (and lambda notation for action is still incomplete).

While refactoring addUnique (find macro may be useful later) I thought about checking expression for non-zero value. Straightforward approach, when match sets flag, is acceptable, yet it seems to be an overkill: numeric expressions are special, there must be some other way. From the rest of instant macros only rept seems to be of any use:
Code:
minint equ 0x8000'0000'0000'0000
maxint equ 0x7FFF'FFFF'FFFF'FFFF
macro classify value {
  match =0, value \{ display "Zero", 13, 10 \}
  rept 1 and ((value) or (-(value))) shr 63 \{ display "Non-zero", 13, 10 \}
}
irp value, minint, maxint, 0 { classify value }    
It simply uses the fact that x | -x < 0 for each x != 0 (for x == 0 it's obviously 0). While this method depends on fasm expression evaluator's being 64 (+1) bit, for most practical applications it perhaps would suffice.
Post 29 Apr 2013, 06:35
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


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.