Now that we have setup the basics (See Part1 and Part 2), we could start with the actual linking process.
We get a list of sections which need to be setup to the correct positions in the rom file and after that we patch some of the opcodes with the actual addresses.
So lets setup the actual linking funktion:
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
|
// helper function to convert a list of results to a result of list
let CollectResults (l : Result<'T, 'e> list) : Result<'T list, 'e> =
let folder value curList =
match curList with
| Error e -> Error e
| Ok lst ->
match value with
| Error e -> Error e
| Ok v -> Ok (v :: lst)
List.foldBack folder l (Ok List.empty)
let Link (header: CartridgeHeader) (sections:Section list) : Result<LinkRes, string> =
let clearInvalidRomData s =
match s.Area with
| Rom _ -> s
| _ -> { s with Rom = None }
sections
// 1. Remove any data from sections which are not on the rom (we don't need that data...)
|> List.map clearInvalidRomData
// 2. Group everything by area (rom, ram etc)
|> List.groupBy (fun s-> s.Area)
// 3. Arrange each area on its own
|> List.map arrangeSectionsForArea
// 4. Convert the list of results to a result of list
|> CollectResults
// 5. flatten the Result<Section list list, string> to Result<Section list, string>
|> Result.map (List.collect (fun l -> l))
// 6. apply the patches to the opcode
|> Result.bind applyPatches
// 7. build the writers from the assigned+patched sections
|> Result.map (linkerResFromSections header)
|
Steps 1, 2, 4 and 5 are trivial so I will not go into detail for these. So let’s start with step 3 and arrange the sections.
To arrange the section we first need to get the available space for the given area which we want to arange. We have already seen the actual layout of the gameboys memory in Part 2 so we can write a function to convert the area union to a list of available spaces:
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
|
type private AddressRange = {
Address: uint16
Length: uint16
}
// A Block of memory, which is either assigned to a section or not yet assigned.
type private Block =
| Available of AddressRange
| Assigned of Section
// getBlocks returns a sequence of available address ranges as descriped in the gameboy memory layout.
let private getBlocks (a:Area) : Block seq =
let range f t =
Available {
Address = f
Length = (t+1us) - f
}
match a with
| Rom bn ->
if bn = 0 then
seq {
yield range 0x0000us 0x0103us // Restart and Interrupt Vectors + Entry Point.
yield range 0x0150us 0x3FFFus // Actual free space of rom bank 0
}
else
seq { yield range 0x4000us 0x7FFFus } // all other banks are mapped to the same space.
| WRam bn ->
if bn = 0 then
seq { yield range 0xC000us 0xCFFFus }
else
seq { yield range 0xD000us 0xDFFFus }
| VRam -> seq { yield range 0x8000us 0x9FFFus } // it might be a good idea to split the range to background map 1, 2 and sprite data.
| HRam -> seq { yield range 0xFF80us 0xFFFEus }
| SRam -> seq { yield range 0xA000us 0xBFFFus }
| OAM -> seq { yield range 0xFE00us 0xFEFFus }
|
Now that we know in what area we could arrange the sections for the area we can follow the following workflow:
- Get a list of all available memory blocks
- Try to assign every section that has a fixed address
- Assign all other sections.
So we get:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
let private arrangeSectionsForArea (area, (sections: Section list)) =
// split the sections to two list, one with all assigned sections one with all unassigned sections.
let (assigned, unassigned) =
sections
|> List.fold (fun (a, u) s ->
if s.Origin.IsSome then
(s::a), u
else
a, (s::u)
) (List.empty, List.empty)
// find the available space in an unallocated state
let blocks = getBlocks area |> Seq.toList
// remove all memory which is blocked by sections with fixed addresses.
let blocks = FoldResults assignSection blocks assigned
// and at last: try to arrange all unassigned sections
blocks
|> Result.bind (assignUnassigned unassigned)
|> Result.map (List.append assigned)
|
to arrange the already assigned sections we do the following:
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
|
let FoldResults<'a, 'b, 'e> (f: 'b->'a->Result<'b,'e>) (start:'b) (items : 'a list) : Result<'b, 'e> =
let rec walkitems s items =
match items with
| head::rest ->
let next = f s head
match next with
| Ok n -> walkitems n rest
| x -> x
| [] -> Ok s
walkitems start items
let private blockContains addr block =
let (start, length) =
match block with
| Available av -> av.Address, av.Length
| Assigned sect ->
match sect.Origin with
| None -> 0us, 0us
| Some origin -> origin, sect.Length
addr >= start && addr < (start + length)
// Assigns an allocated section the a specific block and returns an updated block list.
let private assignSectionToBlock block section allBlocks =
let splitBlock (b: AddressRange) (s: Section) : Block list =
let blocks = seq {
let endAddr = s.Origin.Value + s.Length
// block before the selected address
yield Available {
Address = b.Address
Length = s.Origin.Value - b.Address
}
// the new assigned block
yield Assigned s
// the block behind the section
yield Available {
Address = endAddr
Length = b.Length - endAddr
}
}
let blockNotEmpty b =
match b with
| Assigned s -> s.Length > 0us
| Available a -> a.Length > 0us
blocks
|> Seq.where blockNotEmpty
|> Seq.toList
allBlocks
|> List.except (Seq.singleton (Available block))
|> List.append (splitBlock block section)
// assign a section with a fixed address to the block it contains.
let private assignSection (blocks: Block list) (section: Section) =
match section.Origin with
| Some origin ->
let targetBlock =
blocks
|> List.where (blockContains origin)
|> List.where (blockContains (origin + (section.Length-1us)))
|> List.tryHead
match targetBlock with
| None -> Error (sprintf "Invalid address $%x" origin)
| Some (Assigned _) -> Error (sprintf "address $%x already in use" origin)
| Some (Available blk) ->
Ok (assignSectionToBlock blk section blocks)
| None -> Ok blocks
|
and the unallocated sections can be done with some backtracking:
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
|
let private assignUnassigned (sections: Section list) (blocks: Block list) : Result<Section list, string> =
// gets a list of all available blocks, which are larger then the given length.
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
)
let rec tryAssign (sections: Section list) (blocks: Block list) : Result<Section list, string> =
match sections with
| head::rest ->
// Get all candidates for the section
let candidates = getBlockCandidates head.Length blocks
if candidates.IsEmpty then
Error "Unable to store section"
else
// check if the candidate results in a valid section layout.
let isValidTarget blk =
let blocks = assignSectionToBlock blk head blocks
let res = tryAssign rest blocks
match res with
| Ok _ -> true
| Error _ -> false
// try to find a solution which can assign all blocks.
let res = candidates |> List.tryFind isValidTarget
match res with
| Some space ->
// assign the space address to the section
let head = {head with Origin = Some space.Address}
// continue with the rest.
assignSection blocks head
|> Result.bind (tryAssign rest)
|> Result.map (fun others -> head::others)
| None -> Error "Invalid candidate"
| [] -> Ok sections
let sections =
sections
|> List.sortByDescending (fun s -> s.Length) // assign larger sections first.
tryAssign sections blocks
|
I know this function should be optimized, because it does the whole work multiple times but for now this should work fine.
Next time we patch the binary data and create the writer. So stay tuned.