The Path "Encryption"

[IsmAvatar]

I've been working on cracking the path format, and I've basically started charting each input/output pair in hopes to find a pattern.
The good news is, I'm starting to see a pattern.
The bad news is, the pattern I see is very inefficient and I haven't a clue why Mark decided to use it.

And now, for your pleasure, the list (will be updated with new breakthroughs, and other such blogs)


Encrypted number = Hex Code = hex-to-decimal (change since last)
0 = 00000000 = 0.0.0.0
1 = 0000F03F = 0.0.240.63
2 = 00000040 = 0.0.0.64 (0.0.16.0)
3 = 00000840 = 0.0.8.64 (0.0.8.0)
4 = 00001040 = 0.0.16.64 (0.0.8.0)
5 = 00001440 = 0.0.20.64 (0.0.4.0)
6 = 00001840 = 0.0.24.64 (0.0.4.0)
7 = 00001C40 = 0.0.28.64 (0.0.4.0)
8 = 00002040 = 0.0.32.64 (0.0.4.0)
9 = 00002240 = 0.0.34.64 (0.0.2.0)
10 = 00002440 = 0.0.36.64 (0.0.2.0)
11 = 00002640 = 0.0.38.64
12 = 00002840 = 0.0.40.64
13 = 00002A40 = 0.0.42.64
14 = 00002C40 = 0.0.44.64
15 = 00002E40 = 0.0.46.64 (0.0.2.0)
16 = 00003040 = 0.0.48.64 (0.0.2.0)
17 = 00003140 = 0.0.49.64 (0.0.1.0)
18 = 00003240 = 0.0.50.64
19 = 00003340 = 0.0.51.64
20 = 00003440 = 0.0.52.64
21 = 00003540 = 0.0.53.64
22 = 00003640 = 0.0.54.64
23 = 00003740 = 0.0.55.64
24 = 00003840 = 0.0.56.64
25 = 00003940 = 0.0.57.64
26 = 00003A40 = 0.0.58.64
27 = 00003B40 = 0.0.59.64
28 = 00003C40 = 0.0.60.64
29 = 00003D40 = 0.0.61.64
30 = 00003E40 = 0.0.62.64
31 = 00003F40 = 0.0.63.64 (0.0.1.0)
32 = 00004040 = 0.0.64.64 (0.0.1.0)
33 = 00804040 = 0.128.64.64 (0.128.0.0)
34 = 00004140 = 0.0.65.64 (0.128.0.0)
35 = 00804140 = 0.128.65.64 (0.128.0.0)
...
63 = 00804F40 = 0.128.79.64 (0.128.0.0)
64 = 00005040 = 0.0.80.64 (0.128.0.0)
65 = 00405040 = 0.64.80.64 (0.64.0.0)
...
128 = 00006040 = 0.0.96.64 (0.64.0.0)
129 = 00206040 = 0.32.96.64 (0.32.0.0)
130 = 00406040 = 0.64.96.64 (0.32.0.0)

65536 ~= 0000F040 (added in as an experiment)


There is obviously a pattern.
Where did Mark come up with this scheme >.<
I'm going to have one heck of a time making a formula for it.
It seems to be a kind of 32/x scheme and it changes at every 2ⁿ.

[IsmAvatar]

Here are those numbers in longint form:

x -> [y ][(dx[ = dx[) (y]])]

0 -> 0
1 -> 1072693248
2 -> 1073741824 (1048576 = 2²⁰) (2³⁰)
3 -> 1074266112 (524288 = 2¹⁹)
4 -> 1074790400 (524288)
5 -> 1075052544 (262144 = 2¹⁸)
6 -> (262144)
7 -> (262144)
8 -> (262144)
9 -> (131072)
10 -> (131072)
11 -> (131072)
12 -> (131072)

and I've found that the formula to get the change in x is
y' = 2²⁰/floor(log₂(x)). Unfortunately, I don't know how to get the antiderivative of a log₂, so I'll need to locate someone who knows math better than I do.

[IsmAvatar]

(where S is the integral sign)

S log(x) dx = x*log(x)-x + C
and log₂(x) = log(x)/log(2)

y' = 2²⁰/log₂(x) = 2²⁰/(log(x)/log(2))

So we throw the integral in front, and slap the dx on the end.

S 2²⁰/(log(x)/log(2)) dx

and we can bring the constant out in front (and simplify the fraction in the process)

2²⁰*S log₂(x)^-1 dx

the result appears to be

2²⁰*x*ln(2)*ln(log₂(x)) + C

where C is any constant

[IsmAvatar]

Sorry, looks like I got the derivative wrong.
It's actually this:

y' = 2^{20-floor(log₂(x-1))}

S 2^{20-floor(log₂(x-1))} dx

which, if i'm not mistaken, should come out to simply be

y = (x-1)*2^{20-floor(log₂(x-1))} + C

[IsmAvatar]

Unfortunately, the above function does not return the desired result, which means that I probably calculated it incorrectly.

On a brighter note, I have discovered a recursive way to obtain the desired result (pascal code)

function dif(x : longint) : longint;
begin
 if x = 1 then
  dif := 1072693248
 else
  dif := dif(x-1) + trunc(  power(2,20-trunc(log2(x-1)))  );
end;

This works perfectly on a domain of [1,infinity)
Just remember that dif(0) is 0.
Again, 1072693248 is 2³⁰-2²⁰

The formula for this is

[IsmAvatar]

I was able to replace the recursion with a loop, so it's much faster now.

I was also able to solve both ways. f2p is File To Path [number], f2pp is File To Path Precise (allowing for numbers inbetween the standards), and p2f is Path To File.

function dif(m : longint) : longint;
begin
 if m = 1 then
  dif := 1072693248
 else
  dif := 2 ** (20-trunc(log2(m-1)));
end;

function p2f(m : longint) : longint;
var b : longint;
begin
 p2f := 1072693248;
 for b := 2 to m do p2f += dif(b);
end;

function f2pp(m : longint) : longint;
var b : longint;
begin
 b := 1;
 while m > (p2f(b) - dif(b) div 2) do b += 1;
 f2pp := b-1;
end;

function f2p(m : longint) : longint;
var b : longint;
begin
 b := 1;
 while m >= 1072693248 do
 begin
  b += 1;
  m -= dif(b);
 end;
 f2p := b - 1;
end;

I replaced power with **, since they are the same thing, only ** is the proper operator, and returns the same type as the operands, so I don't have to trunc( ) it anymore.

[IsmAvatar]

Because of Pascal's rounding off after a while, trunc(log2(x)) when x is 128 will return 6 instead of 7. This will cause a slight inaccuracy, like where a GM path says 128 or 129, this program will read in 127 or 128 respectively, unfortunately. Unfortunate, because 128 is a rather small number, considering it's only 2⁷

I'm looking into a solution to this problem. It would be nice if there was a round(x,d) where x is the number to be rounded and d is the number to round it off at. Then the solution would simply be round(log2(x),.999999999)

For those who are interested, pascal's log2(128) = (approx.) 6.9999999999999999995663191310057982[3]

[IsmAvatar]

I went to the developers chatroom and asked about it, and one of the guys reminded me of the decimal rounding trick. Multiply, round, divide.

I paid him my thanks, but no credit is necessary for such a simple concept.

The solution:

function dif(m : longint) : longint;
begin
 if m = 1 then
  dif := 1072693248
 else
  dif := 2 ** (20-(round(log2(m-1)*100000) div 100000));
end;

Will get you up to 65535 and then some. To get higher, simply add more 0's to the 100000's.
A friendly reminder, after maybe 10 zeroes or so, you'll lose accuracy. What's happening is it's rounding off the 9's deep into the decimal. After a while, you run out of 9's and start to get numbers that round down instead of up.

When put to the test, it held up perfectly.



I am now done cracking the Path Encryption.

[IsmAvatar]

After a tip that the date format may use the Double, 8 bytes, I tried this and the date format most definately is a double. By a mere suspicion, since the paths use 8 bytes, I tried it on the paths.

As it turns out, I have cracked more than the Path "Encryption", but the Double format...


Game over guys. The paths use doubles for some random reason. What a waste of time and brainpower spent in doing that...