flat assembler
Message board for the users of flat assembler.

Index > Main > [fasmg] Optimal relocation

Author
Thread Post new topic Reply to topic
marste



Joined: 05 May 2015
Posts: 44
marste 19 Sep 2017, 09:09
Here I’m again to see if fasmg can again exceed my expectations… Cool

In my little program I’ve some code that I can relocate. More: I need to relocate it in order to respect some constrain that I have (e.g. some label is within some address range), and depending on the parameters that I select for compilations this pieces should be relocated differently in order to respect the constraints.

I’ve seen examples in which fasmg resolve some second degree equation finding automatically values fitting a constraint, so I was thinking something as including the pieces (many little ones) of code in many places with a condition fitting just in one place, e.g.:

Code:
Relocatablecode.inc:
  if PIECE_1_LOC=THISLOC
    Relocatable code…
  end if

mainfile.asm:
  …code…
  THISLOC=1
  Include Relocatablecode.inc
  …more code…
  THISLOC=2
  Include Relocatablecode.inc
  ..etc..
    


But not sure how to let fasmg calculate PIECE_1_LOC… And maybe there are different way also to have the same result!…

Additionally if possible (and I really this is difficult) there are other conditions (e.g. some label address mod 256 equal 0) that are not strictly required but if possible a nice to have (I can even add some “weights” to this conditions in order to have a value to minimize or maximize for example).

Hope I was clear enough but anyway available for any more clarification! Smile

Thank you!
Post 19 Sep 2017, 09:09
View user's profile Send private message Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 8356
Location: Kraków, Poland
Tomasz Grysztar 19 Sep 2017, 09:33
If you use multiple conditions to place constraints on what can be assembled where, fasm[g] is going to look for a solution until it finds one. Unfortunately, even if a solution exists, there is no guarantee that fasm is going to find it (and the existence of a solution is one of the undecidable problems). You may get the "could not generate code within the allowed number of passes" error.

One of the possible obstacles is the "oscillator problem", please read about it.

What I would suggest is to write the IF blocks to place various constraints, and keep adding them until you get the "could not generate code" error. If that happens, we may look at the specific problem to see how we can guide fasmg to find the right solution with some additional flags and conditions (like in the case of the "oscillator problem").
Post 19 Sep 2017, 09:33
View user's profile Send private message Visit poster's website Reply with quote
marste



Joined: 05 May 2015
Posts: 44
marste 19 Sep 2017, 13:45
Do you suggest to start with something like this?

Code:
Relocatablecode.inc:
  if PIECE_1_LOC = THISLOC
    Relocatable code…
    PIECE_1_LOC = THISLOC
  end if
  if PIECE_2_LOC = THISLOC
    Other relocatable code…
    PIECE_2_LOC = THISLOC
  end if

mainfile.asm:
  …code…
  THISLOC = 1
  Include Relocatablecode.inc
  …more code…
  THISLOC = 2
  Include Relocatablecode.inc
  THISLOC = 3
  Include Relocatablecode.inc
  …etc…
  assert PIECE_1_LOC
  assert PIECE_2_LOC
  …end
    
Post 19 Sep 2017, 13:45
View user's profile Send private message Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 8356
Location: Kraków, Poland
Tomasz Grysztar 19 Sep 2017, 15:40
I have prepared a very simplified example that demonstrates some of the ideas. I have used numbered macros to define pieces of code that get moved around:
Code:
macro piece_1
     first:
     db 'first',13,10
end macro

macro piece_2
     second:
     db 'second',13,10
end macro

macro piece_3
     third:
     db 'third',13,10
end macro

macro piece_4
     fourth:
     db 'fourth',13,10
end macro


macro place_piece number
        repeat 1, n:number
                piece_#n
                macro piece_#n          ; do not assemble same piece again
                end macro
        end repeat
end macro


repeat 4
        ; if address is aligned, place piece that prefers alignment:
        if $ and 3 = 0
                place_piece 2
        end if
        if $ and 3 = 0
                place_piece 4
        end if
        ; otherwise keep placing pieces consecutively:
        place_piece %
end repeat    
Or:
Code:
NUMBER_OF_PIECES = 100

repeat NUMBER_OF_PIECES
        macro piece_#%
                p#%:
                db `%,13,10
        end macro
end repeat

macro place_piece number
        repeat 1, n:number
                piece_#n
                macro piece_#n          ; do not assemble same piece again
                end macro
        end repeat
end macro


repeat NUMBER_OF_PIECES
        ; if we are sufficiently near piece 30, place ones that need to be near it
        if p30 - 100 < $ & $ < p30 + 100
                place_piece 14
        end if
        if p30 - 100 < $ & $ < p30 + 100
                place_piece 28
        end if
        if p30 - 100 < $ & $ < p30 + 100
                place_piece 49
        end if
        if p30 - 100 < $ & $ < p30 + 100
                place_piece 99
        end if
        place_piece %
end repeat

; we can use assertion to force assembly to fail when some end up too far from each other to be acceptable
assert p14 - p30 < 100 | p30 - p14 < 100    

The main problem here is that need to write rules that are easy to apply, like above. For any constraints that you have, you need to have an idea what kind of reordering may help. In the worst case you may actually need to test every possible order.
Post 19 Sep 2017, 15:40
View user's profile Send private message Visit poster's website Reply with quote
marste



Joined: 05 May 2015
Posts: 44
marste 20 Sep 2017, 08:37
The proposed approach might be good if you have some condition that can determine “without search” the optimal solution.

I’ve a different scenario. To simplify, imagine that I should fit the more piece I can below a certain address. The if then can read something like “if $<limit then place piece”, but this is not guaranteeing an optimal solution.

As for example to simplify: imagine the address is 20 and the pieces are (in order) 8 7 6 6 long, with the proposed method 8 and 7 will fit while the 6s will not find anymore available space (5 is remaining); while an optimal solution should fit the 8 and the two 6 blocks (leaving just the 7 outside).
Post 20 Sep 2017, 08:37
View user's profile Send private message Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 8356
Location: Kraków, Poland
Tomasz Grysztar 20 Sep 2017, 08:45
As I noted above, if you do not have at least a good heuristic to begin with, you are left with no other option than trying all permutations. This is viable when there are just few pieces, for larger numbers you would have to keep fingers crossed that it finds an acceptable solution within early tries (you could randomize generated permutations instead of using the lexicographical order).
Post 20 Sep 2017, 08:45
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 8356
Location: Kraków, Poland
Tomasz Grysztar 20 Sep 2017, 09:50
I have prepared an example that looks through all the permutations to find the solution in the simplified case you mentioned:
Code:
macro piece_1
        db 8 dup '1'
end macro

macro piece_2
        db 7 dup '2'
end macro

macro piece_3
        db 6 dup '3'
end macro

macro piece_4
        db 6 dup '4'
end macro

if PIECES_FITTING >= 3                  ; if we found the solution,
        PERMUTATION = PERMUTATION       ;  keep the permutation
else if ~ PERMUTATION
        PERMUTATION = 1234h             ; this is the permutation we start with
else
; the following code mutates the permutation to the next one lexicographically
        PERM = PERMUTATION
        BUFFER = 0
        while PERM & PERM and 0Fh > BUFFER and 0Fh
                BUFFER = (BUFFER shl 4) or (PERM and 0Fh)
                PERM = PERM shr 4
        end while
        INDEX = 0
        while PERM and 0Fh < (BUFFER shr (INDEX+4)) and 0Fh
                INDEX = INDEX + 4
        end while
        TMP = PERM and 0Fh
        PERM = (PERM and not 0Fh) or ((BUFFER shr INDEX) and 0Fh)
        BUFFER = (BUFFER and not (0Fh shl INDEX)) or (TMP shl INDEX)
        PERM = (PERM shl ((bsr BUFFER shr 2 + 1) shl 2)) or BUFFER
        PERMUTATION = PERM
end if

COUNT = 0
repeat 4
        repeat 1, i:(PERMUTATION shr ((%%-%)*4)) and 0Fh        ; extract digit from permutation
                piece_#i
        end repeat
        if $ <= 20
                COUNT = COUNT + 1               ; count pieces that fit in the first 20 bytes
        end if
end repeat
PIECES_FITTING := COUNT    
If the solution cannot be found, assembly is never going to finish and will abort upon reaching the limit of passes.

As I mentioned in the previous post, instead of looking through the permutations consecutively you could also try generating them in some pseudo-random order. When the space of acceptable solutions is a large set, such method could give results faster.
Post 20 Sep 2017, 09:50
View user's profile Send private message Visit poster's website Reply with quote
marste



Joined: 05 May 2015
Posts: 44
marste 20 Sep 2017, 12:23
For me permutations will be good (I have a condition flexible enough), just that with 6 "mobile pieces" 720 will be the overall possiblities (I can anyway pilot more result and reduce search).

Anyway with condition that have to be explicit (and not something as max among possiblities) the solution cannot find optimal ones in general as e.g. in the given example having lists as: 8,7,6,8 (8+8 optimal) or 4,4,4,4,4,4 (4+4+4+4+4 optimal).

But I think we are already much much better than a "standard" assembler!!! Smile
Post 20 Sep 2017, 12:23
View user's profile Send private message Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 8356
Location: Kraków, Poland
Tomasz Grysztar 26 May 2019, 09:02
Discussion in another thread has reminded me of this one and I realized that I am now able to enhance the idea.

In the meantime I have been working on a series of articles about multi-pass assembly and I must admit that my own abilities to utilize it have improved thanks to that.

So here comes a vastly improved variant of the above sample, one that looks through a set number of randomly generated permutations and sticks to the best solution that it finds:
Code:
macro piece_1                                                                                                 
        db 8 dup '1'                                                                                          
end macro                                                                                                     
                                                                                                              
macro piece_2                                                                                                 
        db 7 dup '2'                                                                                          
end macro                                                                                                     
                                                                                                              
macro piece_3                                                                                                 
        db 6 dup '3'                                                                                          
end macro                                                                                                     
                                                                                                              
macro piece_4                                                                                                 
        db 6 dup '4'                                                                                          
end macro                                                                                                     
                                                                                                              
macro piece_5                                                                                                 
        db 3 dup '5'                                                                                          
end macro                                                                                                     
                                                                                                              
macro piece_6                                                                                                 
        db 4 dup '6'                                                                                          
end macro                                                                                                     
                                                                                                              
SIZE_LIMIT := 20                        ; size of the area where we want to fit as many pieces as possible    
                                                                                                              
MAX_TRIES := 50                         ; make sure to have fasmg's passes limit setting higher than this     
                                                                                                              
; random number generator:                                                                                    
                                                                                                              
struc rand32                                                                                                  
        . = XORSHIFT shr 96                                                                                   
        . = ( . xor (. shl 11) xor (. shr 8) xor (XORSHIFT) xor (XORSHIFT shr 19) ) and 0FFFFFFFFh            
        XORSHIFT = (. or XORSHIFT shl 32) and 0FFFFFFFF_FFFFFFFF_FFFFFFFFh                                    
end struc                                                                                                     
                                                                                                              
struc rand limit                                                                                              
        while 1                                                                                               
                . rand32                                                                                      
                . = . and (1 shl (bsr (limit) + 1) - 1)                                                       
                if . <= limit                                                                                 
                        break                                                                                 
                end if                                                                                        
        end while                                                                                             
end struc                                                                                                     
                                                                                                              
; permutation generator:                                                                                      
                                                                                                              
if PASS >= MAX_TRIES                                                                                          
        PASS := MAX_TRIES                                                                                     
        PERMUTATION := BEST_PERMUTATION                                                                                                                                                               
else if ~ PERMUTATION                                                                                         
        PASS := 1                                                                                             
        PERMUTATION := '123456'         ; this is the permutation we start with                               
        SEED := %t                                                                                            
else                                                                                                          
        PASS := PASS + 1                                                                                      
        XORSHIFT = SEED                                                                                       
        ; generate another random permutation (via Knuth shuffle):                                            
        virtual at 1                                                                                          
                db PERMUTATION                                                                                
                repeat lengthof PERMUTATION - 1                                                               
                        SWAP rand lengthof PERMUTATION - %                                                    
                        if SWAP                                                                               
                                load A: byte from %                                                           
                                load B: byte from %+SWAP                                                      
                                store A: byte at %+SWAP                                                       
                                store B: byte at %                                                            
                        end if                                                                                
                end repeat                                                                                    
                load PERMUTATION: lengthof PERMUTATION from 1                                                 
        end virtual                                                                                           
        SEED := XORSHIFT                                                                                      
end if                                                                                                        
                                                                                                              
; shuffle pieces of code and evaluate:                                                                        
                                                                                                              
COUNT = 0                                                                                                     
repeat lengthof PERMUTATION                                                                                   
        repeat 1, i: (PERMUTATION shr ((%-1)*8)) and 0Fh        ; extract a single digit                      
                piece_#i                                                                                      
        end repeat                                                                                            
        if $ <= SIZE_LIMIT                                                                                    
                COUNT = COUNT + 1       ; count pieces that fit                                               
        end if                                                                                                
end repeat                                                                                                    
PIECES_FITTING := COUNT                                                                                       
                                                                                                              
if PASS >= MAX_TRIES | ( BEST_PERMUTATION & PIECES_FITTING <= BEST_PIECES_FITTING )                           
        BEST_PERMUTATION := BEST_PERMUTATION                                                                  
        BEST_PIECES_FITTING := BEST_PIECES_FITTING                                                            
else                                                                                                          
        BEST_PERMUTATION := PERMUTATION                                                                       
        BEST_PIECES_FITTING := PIECES_FITTING                                                                 
end if                                                                                                        
                                                                                                              
display 'Found permutation ',BEST_PERMUTATION,' with ','0'+BEST_PIECES_FITTING,' pieces fitting in the limit.'    
By replacing %t with a constant in initial seed definition it can be made fully deterministic.

Also, additional clause may be added to end search prematurely when the solution is already "good enough" according to some metric. For this purpose it is enough to replace:
Code:
if PASS >= MAX_TRIES    
with something like:
Code:
if PASS >= MAX_TRIES | BEST_PIECES_FITTING >= 4    
The number of passes taken is then going to be random, depending on how quickly a good permutation is found. And if no such permutation is found, the best found solution is going to be used, after reaching the maximum number of tries.
Post 26 May 2019, 09:02
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 8356
Location: Kraków, Poland
Tomasz Grysztar 27 May 2019, 12:55
I have translated this idea into a simple macro package that should be easier to adapt for other experiments:
Code:
define Randomizer

if ~ defined Randomizer.SEED
        Randomizer.SEED := %t
else
        postpone
                Randomizer.SEED := Randomizer.XORSHIFT
        end postpone
end if

Randomizer.XORSHIFT = Randomizer.SEED

struc Randomizer.rand32
        . = Randomizer.XORSHIFT shr 96
        . = ( . xor (. shl 11) xor (. shr 8) xor (Randomizer.XORSHIFT) xor (Randomizer.XORSHIFT shr 19) ) and 0FFFFFFFFh
        Randomizer.XORSHIFT = (. or Randomizer.XORSHIFT shl 32) and 0FFFFFFFF_FFFFFFFF_FFFFFFFFh
end struc                                                                                                     
                                                                                                              
struc Randomizer.rand limit
        while 1                                                                                               
                . Randomizer.rand32
                . = . and (1 shl (bsr (limit) + 1) - 1)                                                       
                if . <= limit                                                                                 
                        break                                                                                 
                end if                                                                                        
        end while                                                                                             
end struc                                                                                                     


define Permutator

Permutator.MaxTries := 50    ; make sure to have fasmg's passes limit setting higher than this

macro Permutator.begin

        local Block

        Block.__FILE__ = __FILE__
        Block.__LINE__ = __LINE__

        Block.CURRENT = 1

        macro Permutator.next!
                        esc end macro
                end repeat
                Block.CURRENT = Block.CURRENT + 1
                repeat 1, i:Block.CURRENT
                        esc macro Block.i
        end macro

        macro Permutator.enough value
                Block.GoodEnough := value
        end macro

        macro Permutator.end!

                        esc end macro
                end repeat

                if Block.PASS >= Permutator.MaxTries | ( defined Block.GoodEnough & Block.BEST_SCORE >= Block.GoodEnough )
                        Block.PASS := Permutator.MaxTries
                        Block.PERMUTATION := Block.BEST_PERMUTATION
                else if ~ Block.PERMUTATION
                        Block.PASS := 1
                        virtual
                                repeat Block.CURRENT
                                        db %
                                end repeat
                                load Block.PERMUTATION : Block.CURRENT from $$        ; initial permutation
                        end virtual
                else
                        Block.PASS := Block.PASS + 1
                        ; generate another random permutation (via Knuth shuffle):
                        virtual at 1
                                db Block.PERMUTATION
                                repeat lengthof Block.PERMUTATION - 1
                                        SWAP Randomizer.rand lengthof Block.PERMUTATION - %
                                        if SWAP
                                                load A: byte from %
                                                load B: byte from %+SWAP
                                                store A: byte at %+SWAP
                                                store B: byte at %
                                        end if
                                end repeat
                                load Block.PERMUTATION: lengthof Block.PERMUTATION from 1
                        end virtual
                end if

                repeat lengthof Block.PERMUTATION
                        repeat 1, i: (Block.PERMUTATION shr ((%-1)*8)) and 0FFh
                                Block.i
                        end repeat
                end repeat

        end macro

        macro Permutator.score expression

                if Block.PASS >= Permutator.MaxTries | ( Block.BEST_PERMUTATION & expression <= Block.BEST_SCORE )
                        Block.BEST_PERMUTATION := Block.BEST_PERMUTATION
                        Block.BEST_SCORE := Block.BEST_SCORE
                else
                        Block.BEST_PERMUTATION := Block.PERMUTATION
                        Block.BEST_SCORE := expression
                end if

                ; show summary:
                display Block.__FILE__,'['
                repeat 1, line: Block.__LINE__
                        display `line,']: '
                end repeat
                display 'permutation {'
                repeat lengthof Block.PERMUTATION
                        repeat 1, i: (Block.PERMUTATION shr ((%-1)*8)) and 0FFh
                                if % > 1
                                        display ','
                                end if
                                display `i
                        end repeat
                end repeat
                repeat 1, best: Block.BEST_SCORE
                        display '} with score ',`best,'.',13,10
                end repeat

        end macro

        repeat 1, i: Block.CURRENT
                esc macro Block.1

end macro    
Use it like:
Code:
include 'permutator.inc'

FIT = 0

Permutator.begin

        db 8 dup '1'

        if $ < 20
                FIT = FIT + 1
        end if

    Permutator.next

        db 7 dup '2'

        if $ < 20
                FIT = FIT + 1
        end if

    Permutator.next

        db 6 dup '3'

        if $ < 20
                FIT = FIT + 1
        end if

    Permutator.next

        db 6 dup '4'

        if $ < 20
                FIT = FIT + 1
        end if

Permutator.end
Permutator.enough 3     ; this line is optional
Permutator.score FIT    
It even allows to define more than one shuffled block in the same source.
Post 27 May 2019, 12:55
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


Copyright © 1999-2024, Tomasz Grysztar. Also on GitHub, YouTube.

Website powered by rwasa.