So I couldn't get to sleep and started thinking about how to find reflexives properly. I'm going to do this in a bit of a formal method so bare with me. I'm going to get the basics out of the way for completeness.
The form of the reflexive is as follows:
Code: Select all
int32 chunk_count //signed
int32 translation //relative to start of meta
int32 zero //always zero
Also assuming certain values such as:
Code: Select all
meta_size //the size in bytes of the meta file
offset //the offset of the reflexive data structure
1. Chunk counts are positive. (Predicated on a signed chunk count.)
2. Zero is always zero.
3. Translations are within the meta. (Some optimizations can be made here based on assumptions of minimum chunk sizes.)
Code: Select all
if translation >= meta_size then false
4. Translations only point forward. (Included full size of reflexive data structure.)
Code: Select all
if translation <= offset + 8 then false
So those are the basic assumptions and knowns of reflexives. Now here are a few more that I can think of that could lead to greater accuracy.
5. All discrete elements of a meta file are in 32-bit increments.
Code: Select all
if translation mod 4 != 0 then false
6. The first recorded reflexive is correct.
This is based off the idea that meta files put organizational data first and then any raw data is kept further along.
7. There is no padding between the start of one reflexives chunk data and another reflexives chunk data.
Using 5, 6 and 7 allows for some interesting checks. For example:
Code: Select all
//reflexives start sorted by translation
//remove any reflexives that don't align with the previous reflexive
for i = 0 to reflexives.ubound - 1
while (i+1 <= reflexives.ubound) AND ((reflexives(i+1).translation - reflexives(i).translation) mod (reflexives(i).chunk_count * 4) <> 0)
reflexives.remove(i+1)
wend
next
//remove any final reflexive that doesn't align with the end of the meta file
while (reflexives.ubound >= 0) AND ((meta_size - reflexives(reflexives.ubound).translation) mod (reflexives(reflexives.ubound).chunk_count * 4) <> 0)
reflexives.remove(reflexives.ubound)
wend
The lynch pin of the first part is that the first recorded reflexive is correct. If it's not then that section falls to pieces. If you don't assume 6 then it becomes much more interesting. The process to solve for which reflexives don't align with all the others becomes a very fun optimization problem. I believe there may be a
dynamic programming solution to that problem.
An exhaustive (and inefficient and boring) approach would be along these lines:
For all reflexives pick one and assume it is correct.
For all other reflexives that align (can be ahead of or after) with the previous, pick one and assume it is correct.
Recurse until no more reflexives align.
Save that list of reflexives.
Iterate over the solutions and find the maximum list of reflexives.
I can't think of the dynamic approach right now but it would be some variation on that except that it would take advantage of previous solutions in some way. Another approach might be to create a graph where each node is a reflexive and each edge joins two reflexives that align to each other and then determining the
longest path. I'm not sure that the graph could be made directed acyclic (and thus solveable) or not.
Thoughts?