An idea for progressive resigning.

[jlddodger]

Progressive Resigning
The tired old way of calculating a map signature is to XOR every dword in the file starting from 2048. The unfortunate drawback to this is that a full pass through a large file is required. File access costs performance several factors of ten. However, it should be notable that XOR is associative, commutative, and its own inverse. The properties of commutativity and self-inversion allow for a much faster resigning process. The three basic functions are shown below.

To add a value into a map one can simply XOR the new value onto the current signature. This is because XOR is commutative:

Code: Select all

(A^B)^C=A^(B^C)
A 1000    B 1010
B 1010    C 1110
  ----      ----
  0010      0100
C 1110    A 1000
  ----      ----
  1100      1100

Order doesn't matter.

To remove a value one can XOR the old value with the current signature. This is because XOR is its own inverse.

Code: Select all

A^B^A = B
A 1000  B 1101
B 1101
  ----
  0101
A 1000
  ----
  1101

XOR undoes itself.

To change an existing value one can XOR the old value with the current signature and then XOR the new value with that result (or vice versa):

Code: Select all

A^B^B^C = A^C
A 1000    A 1000
B 1101    C 0110
  ----      ----
  0101      1110
B 1101
  ----
  1000
C 0110
  ----
  1110

This involves both commutativity and self-inversion.

Basically, for the sake of people writing editors the following process could be used:

• 1. Adopt the first changed dword as your base value.
  2. XOR every following changed dword onto that base value.
  3. When closing or committing changes XOR the final base value onto the files encryptomatic signature.

This process avoids an O(n) full pass through the file, and instead is constant time(O(1)). The overhead for tracking these changes is minimal. Also, since the final signature doesn't write to the map file until the moment of closure or committal, any changes made outside the editor won't conflict. This would only work for changes that were tracked. So if a change were made outside of a progressively resigning editor, the change would have to be manually XORed onto the ES.