Hallo again, first let us revisit the assignUnassigned function from Part 3. As I already mentioned, the code was not very optimal, because the backtracking was done twice for each section. One time to check if there is a solution for the block, and afterward build the solution.
So here is an updated version of the function:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
let private assignUnassigned (sections: Section list) (blocks: Block list) : Result<Section list, string> =
// get all available blocks whith at least 'len' bytes.
let getBlockCandidates len blocks =
blocks
|> List.choose (fun b ->
match b with
| Available blk ->
if blk.Length > len then
Some blk
else
None
| Assigned _ -> None
)
// recursively try to assign the next section in the list.
let rec tryAssign (sections: Section list) (blocks: Block list) : Result<Section list, string> =
match sections with
| head::rest ->
// get the candidates for the current section
let candidates = getBlockCandidates head.Length blocks
// and try to assign the section to one of them.
let rec tryAssignToBlock (addrs: AddressRange list) (blocks: Block list) =
match addrs with
| addr::candidates ->
let head = {head with Origin = Some addr.Address }
let updatedBlocks = assignSectionToBlock addr head blocks
// try to assign the other sections:
match tryAssign rest updatedBlocks with
| Ok list ->
// found a solution
Ok (head :: list)
| Error _ ->
// this block can't provide a solution, so try the other blocks.
tryAssignToBlock candidates blocks
| [] -> Error "Unable to assign section to any address space."
tryAssignToBlock candidates blocks
| [] -> Ok sections
let sections =
sections
|> List.sortByDescending (fun s -> s.Length) // assign large sections first.
tryAssign sections blocks
|
Now that all sections are in place, we need to apply the patches that we’ve got from the assembler.
For example you have the following assembler code:
1
2
3
4
5
6
7
8
9
10
11
12
13
|
SECTION WRAM 0 ; -- Allocated somewhere at RAM Bank 0
Player::
DS 10 ; 10 Bytes of space for the name
DS 1 ; 1 Bytes for the health
SECTION ROM 0 ; -- Allocated somewhere at ROM Bank 0
DamagePlayer:
LD A, [Player+10] ; Load current health to A-Register
DEC A
LD [Player+10], A ; Save the decremented value back to the memory location
|
At the time of assembling, we have no idea where the linker would place the memory for the player, so the assembler will ask the linker to patch that address. For the sake of simplicity we use a Reverse Polish Notation and a stack machine.
So Player+10 will become
1
2
3
|
Push Address of "Player"
Push 10
ADD
|
Lets setup the operations for the stack machine:
1
2
3
4
5
6
7
8
9
10
11
12
|
type Operation =
| Push of int32 // Push a constant value to the stack
| Add // Add the two topmost values from the stack
| Sub // Substract the two topmost values from the stack
| Mult // Multiply the two topmost values from the stack
| BitAnd // Combine the top two topmost values with bitwise AND
| BitOr // Combine the top two topmost values with bitwise AND
| SymAdr of SymbolName // Push the Address of the given symbol to the stack
| SymBank of SymbolName // Push the Bank number of the given symbol to the stack
| CurAdr // Push the address of the current patch to the stack
| Hi // Push the upper byte from the topmost 16-bit value from the stack
| Lo // Push the lower byte from the topmost 16-bit value from the stack
|
the code calculate the result from a list of these Operations is also straightforward:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
let Run (curAdr:uint16) (getSymAdr: SymbolName -> (BankNo * uint16) option) (ops: Operation list) : Result<int, string> =
// Push a value to the given stack and return the new stack
let push v stack =
Ok (v::stack)
// Pop a value from the stack and return the value + the new stack.
let pop stack =
match stack with
| top::rest ->
Ok (top,rest)
| [] -> Error "Stack is empty"
// run a single operation
let runOperation (stack: int list) (op: Operation) =
// run a binary operation on the topmost values of the stack and push it back to the stack.
let binOp (op: int->int->int) =
match pop stack with
| Ok (b, stack) ->
match pop stack with
| Ok (a, stack) ->
push (op a b) stack
| Error e -> Error e
| Error e -> Error e
// run a unary operation on the topmost value of the stack and push it back to the stack.
let unaryOp (op: int->int) =
match pop stack with
| Ok (v, stack) ->
push (op v) stack
| Error e -> Error e
match op with
| Push p -> push p stack
| Add -> binOp (+)
| Sub-> binOp (-)
| Mult -> binOp (*)
| BitAnd -> binOp (&&&)
| BitOr -> binOp (|||)
| SymAdr name ->
match getSymAdr name with
| Some (_, addr) -> push (int addr) stack
| None -> Error (sprintf "Unknown Symbol %A" name)
| SymBank name ->
match getSymAdr name with
| Some (bank, _) -> push bank stack
| None -> Error (sprintf "Unknown Symbol %A" name)
| CurAdr ->
push (int curAdr) stack
| Hi -> unaryOp (fun v -> ((v>>>8)&&&0xFF))
| Lo -> unaryOp (fun v -> v&&&0xFF)
ops
|> FoldResults runOperation List.Empty // Fold the operations with runOperation
|> Result.bind pop // Take the topmost item from the stack
|> Result.map (fun (v, _) -> v) // and return just the value.
|
for the gameboy we could have three different kinds of values: an 8-bit unsigned integer, a 16-bit unsigned integer or an 8-bit signed integer. The only thing left to think of before we could start the patching is, which symbols are visible at which section.
As the symbols might be exported or only local, we need to create a symbol-map for each section which only contains all symbols of that section and all exported symbols of the other section. So let’s start with the byte patching:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
type PatchSize
= BYTE
| SBYTE
| WORD
type Patch = {
Offset : int // The offset of the bytes to patch within the data of the section
Size: PatchSize // How many bytes to patch
Expr: Operation list // the operations to calculate the actual value of the patch
}
// function to lookup a symbol address from a given "symbol table" for the patching stack machine.
let private getSymbolAddress (symbols:Map<SymbolName, (Section*Symbol)>) (symName:SymbolName) : (BankNo * uint16) option =
let dat = Map.tryFind symName symbols
let sectionOffset =
dat
|> Option.bind (fun (s, _) -> s.Origin)
let addrMapper ((_:Section), (sym:Symbol)) (offset:uint16) =
sym.Offset + offset
let addr = Option.map2 addrMapper dat sectionOffset
let bank = Option.map (fun (s, _) ->getBankNo s) dat
Option.map2 (fun a b -> (b, a)) addr bank
let private applyPatches (sects:Section list) :Result<Section list, string> =
let getExports (sect: Section) = // returns all exported symbols of the given section.
sect.Symbols
|> List.where (fun s -> s.Exported)
|> List.map (fun sym -> (sym.Name, (sect, sym)))
let allExports = List.collect getExports sects // collect the exported symbols of all sections.
let getSymbolMapForSec (sect:Section) = // creates a map of all visible symbols for the given section prefering the local symbols
let locals =
sect.Symbols
|> List.map (fun s -> (s.Name, (sect, s)))
(List.append locals allExports)
|> List.distinctBy (fun (k, _) -> k)
|> Map.ofList
let applyPatches (sect: Section) = // applies the patches of the current section
match sect.Rom with // but only if that section got a ROM part. since there is no need to patch RAM values.
| Some rom ->
let getOffset = getSymbolAddress (getSymbolMapForSec sect)
match sect.Origin with
| Some sectOff ->
// recursively apply the patches:
let rec applyNextPatch (patches: Patch list) =
match patches with
| [] -> Ok ()
| patch::patches ->
// helper function to write the new value of the patch to the data array.
let writePatch value =
match patch.Size with
| SBYTE ->
if (value < -128) || (value > 127) then
Error (sprintf "Value %d out of range" value)
else
rom.Data.[patch.Offset] <- byte value
applyNextPatch patches
| BYTE ->
rom.Data.[patch.Offset] <- byte value
applyNextPatch patches
| WORD ->
let value = int16 value
rom.Data.[patch.Offset] <- byte value
rom.Data.[patch.Offset+1] <- byte (value>>>8)
applyNextPatch patches
// get the target-address of the patch
let curAdr = (int sectOff) + patch.Offset
// calculate the value of the patch and write it to the data array:
Run (uint16 curAdr) getOffset patch.Expr
|> Result.bind writePatch
applyNextPatch rom.Patches
| None -> Error "Section not placed"
| None -> Ok ()
let res =
sects
|> List.map applyPatches
|> CollectResults
match res with
| Ok _ -> Ok sects
| Error e -> Error e
|
There is one last thing to be done for the linker: Writing the rom file. See you next time :)