Index
> Main > [fasmg] Optimal relocation |
| Author |
|
|
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"). |
|||
19 Sep 2017, 09:33 |
|
|
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 |
|||
|
19 Sep 2017, 13:45 |
|
|
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 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. |
|||
|
19 Sep 2017, 15:40 |
|
|
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). |
|||
|
20 Sep 2017, 08:37 |
|
|
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).
|
|||
|
20 Sep 2017, 08:45 |
|
|
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 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. |
|||
|
20 Sep 2017, 09:50 |
|
|
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!!!  |
|||
|
20 Sep 2017, 12:23 |
|
|
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.' 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 Code: if PASS >= MAX_TRIES | BEST_PIECES_FITTING >= 4 |
|||
|
26 May 2019, 09:02 |
|
|
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 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 |
|||
|
27 May 2019, 12:55 |
|
< Last Thread | Next Thread > |
Forum Rules:
|