-
Notifications
You must be signed in to change notification settings - Fork 0
/
CandidatesInWindowFinder.cs
99 lines (85 loc) · 3.38 KB
/
CandidatesInWindowFinder.cs
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
94
95
96
97
98
99
using PixelWorld.Machines;
using System;
using System.Collections.Generic;
using System.Linq;
namespace PixelWorld.OffsetFinders;
/// <summary>
/// Find offsets that contain a minimum number of candidates within a sliding window of the buffer.
/// Use in conjunction with a screen parser to collect candidates from the title screen in RAM.
/// </summary>
public static class CandidatesInWindowFinder
{
const int MinUniqueInWindow = 36;
class CandidateLocation
{
public readonly int Offset;
public readonly int Candidate;
public CandidateLocation(int offset, int candidate)
{
Offset = offset;
Candidate = candidate;
}
}
public static List<int> FindOffsets(byte[] buffer, byte[][] candidates)
{
// We don't have enough candidates to even look
if (candidates.Length < MinUniqueInWindow) return new List<int>();
var end = buffer.Length - Spectrum.FontSize;
var ranges = new Dictionary<int, int>();
// This is our rolling window of candidates - we have one for each 'skew' as a matched glyph is
// only valid on the 8 byte boundary
var windows = Enumerable.Range(0, 8).Select(_ => new Queue<CandidateLocation>()).ToArray();
for (var i = 0; i < end; i++)
{
var window = windows[i % 8]; // Decide which window to use based on skewing
for (var c = 0; c < candidates.Length; c++)
{
// Look to see if the current byte is any of our candidates
var y = 0;
var found = false;
while (y < 8 && buffer[i + y] == candidates[c][y])
{
if (++y == 8)
found = true;
}
if (found)
{
window.Enqueue(new CandidateLocation(i, c));
break; // Can only match one as they are unique
}
}
if (window.Count > MinUniqueInWindow)
{
// See if we have enough unique candidates
var uniqueCount = window.Select(w => w.Candidate).Distinct().Count();
if (uniqueCount > MinUniqueInWindow)
{
// Look back to the previous space
var backOffset = window.Peek().Offset;
var foundSpace = false;
for (var b = backOffset; b > backOffset - Spectrum.FontSize && b > 0; b -= 8)
{
if (buffer.IsEmpty(b))
{
backOffset = b;
foundSpace = true;
break;
}
}
if (foundSpace)
{
ranges.TryGetValue(backOffset, out var currentUniqueCount);
ranges[backOffset] = Math.Max(uniqueCount, currentUniqueCount);
}
}
}
while (window.Count > 0 && window.Peek().Offset < i - Spectrum.FontSize)
window.Dequeue();
}
// Okay, we now have a list of ranges and a count of the uniques they contain
var offsets = new List<int>();
if (ranges.Count < 25)
offsets.AddRange(ranges.Keys);
return offsets.ToList();
}
}