[General] Code Versioning w/ Error Detection

[Nestharus]

So.... originally I was using a checksum with a crc.


I'd have a big number and multiply the checksum in last. The checksum would be the checksum+version and the maximum would be checksum max + version max. The crc, first thing added in, would be the version. I'd divide the combined checksum version out at the back, get the checksum for the code, and subtract the retrieved checksum from the stored one to get the remaining version. After dividing out all of the values (left with crc), I'd compare the crc to the version that was left over from the checksum and make sure they were equal. This allowed me to store the version of the code in a much smaller space =).


I'm moving over to the Hamming Code for error detection, which is much, much better than a checksum (both smaller and 100% error detection). The only problem with this is that I now don't know how I should put in the version.


Any ideas?


For those who don't know, a the Hamming Code converts the number into binary and places a parity bit in every power of 2 position of the number. For example, a number of 8 digits would have a parity bit at 1, 2, 4, and 8 (all powers of 2). The parity bits are based on the xor of all of the digits with a 1 in the position of the parity bit's position. For example, 2 would require a 1 in position 2. Looking at 9 in binary, it's 1001. A 0 is in position 2 -> 10[0]1. However, the 9 would be used in the XOR for the first parity bit as a 1 is in position 1 -> 100[1].


For those who don't know what XOR is, XOR is true if there are an odd number of 1s and false if there are an even number of 1s.


1 != 1 -> 0
1 != 0 -> 1
1 != 1 != 1 -> 0 != 1 -> 1



So in a final example, given a 12 bit binary number -> 100110101101, which is 2477, the parities would be inserted like this

[1][2]1[4]001[8]1010110[16]1


Position 1 would XOR all bits in positions with 1 in position 1 of the position excluding the parity bit positions.


1: 1 - P
2: 10 - P
3: 11
4: 100
5: 101
6: 110
7: 111
8: 1000 - P
9: 1001
10: 1010
11: 1011
12: 1100
13: 1101
14: 1110
15: 1111
16: 10000 - P
17: 10001


So 1 would XOR positions 3, 5, 7, 9, 11, 13, 15, and 17.

[1][2]1[4]001[8]1010110[16]1

[1] = 1 XOR 0 XOR 1 XOR 0 XOR 0 XOR 1 XOR 1


There are 4 1's, making the first position 0 as 4 is even.

0[2]1[4]001[8]1010110[16]1


And you just keep going from there =). Now, when using this with save/load, the parity bits have to be tacked to the lowest placeholders because there can't be 0s in front.

100110101101[1][2][4][8][16]


Of course, when processing, the parity bits need to be moved back into their correct positions =).




So yea... back on track. Does anyone know a good way to store the version? The version doesn't have to be stored as the CRC either... I know how to do CRC checking without actually storing the CRC : ).

 

[Dr Super Good]

You could encode the version into paritybit mismatches. By inducing mismatches at specific positions it should be possible to store binary data which could be a number. After generating the version from parity errors (and validating it), you can then restore the code by fixing the induced parity errors and decoding. Obviously this comprimises your Hammering Code's safety to some extent.

 

[Nestharus]

Hm.... I could do that and store the version as a crc, thus keeping the hamming code safety ; ).


Now, the other problem I see is that the Hamming Code makes it so that too many codes are valid, lol... 1 in 512 working codes isn't cool for a big save/load code ; P.


How do I increase Hamming Distance to something like 20?


Should I just use the Hamming and then a small checksum like 950000, cuz that'll increase the distance : ).

 

[Dr Super Good]

1 in 512 is secure enough for a WC3 save load system. The average player will not start the map 512 times. I doubt even the most dedicated fan will not play a map 4 times that. Thus guessing is as good as impossible.

 

[Nestharus]

Well, it's still possible to type in some random code and have it work : P. In custom hero footies, it used to use a 256 checksum. People would type in random codes like -load SCREW-THIS and it'd work, lol.

 

[rysnt11]

I'm playing fferpg more than 2 times a week, same does for other my loved rpg
So i think, code versioning is needed

 

[Dr Super Good]

Well, it's still possible to type in some random code and have it work

It always will be possible. Although I would not trust my money with such a system, it is more than is required for a WC3 map. You are trying to overdesign the security of codes to such a point you are probably hurting its usability.

1 in 512 means that about every 512 attempts someone will get a valid code. However, that does not mean that code is even good as most states you can load are not desireable. Thus it is secure as it becomes far easier to generate a code via manipulating the map script than it is to random one.

 

[Nestharus]

Well, I actually think that adding a 256 checksum to the back would be good : ). It'd be like 1 in 131072 working codes and would be like 18 bits total =). It'd also allow me to do the easy version+checksum thing to store the version ^)^.


Now, if I went the other route with just the Hamming Code, I wouldn't need a CRC store (push a bit on upon loading to make sure 1 is left over at the end) and I could store the version with the error things as you said... however... Hamming Code can only detect up to 3 different bit changes, meaning that only like 7 versions would be able to be supported.... it's a good idea, but don't think it'll work out ; P.


I just want to make sure that the Hamming Space is large enough so that a person won't be able to type in some random code and have it work (a very, very small change).



Anyways, I'll be sure to keep everything split up so that people can pick and choose exactly what they want : ).



I've still yet to come up with a good way to store the version of a code while just using Hamming and be able to support like 10,000 different code versions.


Oh yes, soon I will have a list of binary numbers from 1 to 1024 for the purposes of things like Hamming Code ; ).

edit
hmm.. Hamming code algorithm is actually pretty simple : D. I have the if statement in there to handle the special power of 1 case =P.

    globals
        private boolean array bit
        private integer count = 70
    endglobals
    
    //applies hamming code for specific power of 2
    function ApplyHamming takes integer power returns nothing
        local integer i = 0
        local integer c = power - 1
        local boolean xor = false
        
        if (1 == power) then
            set i = 1
            loop
                set i = i + 2
                if (i > count) then
                    set bit[power] = xor
                    return
                endif
                if (bit[i]) then
                    set xor = not xor
                endif
            endloop
        else
            loop
                set i = i + power + 1
                loop
                    if (i > count) then
                        set bit[power] = xor
                        return
                    endif
                    if (bit[i]) then
                        set xor = not xor
                    endif
                    
                    set c = c - 1
                    exitwhen 0 == c
                    
                    set i = i + 1
                endloop
                set c = power
            endloop
        endif
    endfunction

The algorithm for loading a big int into the boolean array is also simple, but I shall save that for another time as I have to get up at an obscenely early hour tomorrow : (.



Now to the big question... how to support up to version 10,000+ in the save/load code while storing it in minimal space =O. I could cut off 1 bit by storing a portion of it as an error, but... o-o

 

[Nestharus]

Hamming Code officially useless for save/load.

//uncomment line 172 to make this load the original ints back up again
//go to the very bottom to play around with this

//issues: while there are 0 collisions, the hamming distance is extremely small... that is it's 3. What this means
//is that every time 3 bits change, there is a valid code. A standard knuth checksum will have less working
//codes overall, but this is because it allows for collisions. The question is, should every single code
//have its own key (checksum), or should there be repeating checksums. Repeating checksums ensure very large
//hamming distances but lots of repetition. Hamming codes ensure absolutely no repeating parity bit sequences, but
//have rather small hamming distances.
//
//with 6 bits, a knuth checksum can make it so that only 1 in 64 codes work. Hamming only does about 1 in 14.
//However, the Hamming codes ensure small amounts of bits for extremely large numbers while again maintaining
//absolutely unique parity bit sequences.
//
//in save/load, the data can already not be read, so doing something like changing 1 or 2 bits or adding values
//is extremely difficult. It is this kind of thing that the Hanning protects against. It's more important to have
//a maximized Hamming Distance than unique parity sequences. Yes, if the code was cracked, unique parity sequences
//would make it harder to generate codes, but good codes are never really cracked, the maps are.
//
//Thus I present the Hamming code, which is rather useless for save/load but interesting nonethless ; ).
scope Hamming
    globals
        private Base base2
        
        private boolean array bit
        private integer count = 0
        private trigger tval
        private trigger tval2
        private trigger tval3
        private BigInt loaded
        private integer power
        private boolean parity
    endglobals
    
    private function GetHammingPower takes nothing returns boolean
        local integer i = 0
        local integer c = power - 1
        local boolean xor = false
        
        if (1 == power) then
            set i = 1
            loop
                set i = i + 2
                if (i > count) then
                    return xor
                endif
                if (bit[i]) then
                    set xor = not xor
                endif
            endloop
        else
            loop
                set i = i + power + 1
                loop
                    if (i > count) then
                        return xor
                    endif
                    if (bit[i]) then
                        set xor = not xor
                    endif
                    
                    set c = c - 1
                    exitwhen 0 == c
                    
                    set i = i + 1
                endloop
                set c = power
            endloop
        endif
        return false
    endfunction
    private function LoadBigInt takes BigInt i returns nothing
        local integer pow = 1
        loop
            set i = i.next
            exitwhen i.end
            loop
                set count = count + 1
                exitwhen count != pow
                set pow = pow * 2
                call loaded.push(1)
            endloop
            set bit[count] = 0 != i.digit
        endloop
    endfunction
    private function ApplyHamming takes nothing returns nothing
        set power = 1
        loop
            exitwhen power > count
            set bit[power] = TriggerEvaluate(tval2)
            set power = power * 2
        endloop
    endfunction
    private function GetParity takes nothing returns boolean
        local integer pow = 1
        local boolean xor = false
        loop
            exitwhen pow > count
            if (bit[pow]) then
                set xor = not xor
            endif
            set pow = pow * 2
        endloop
        return xor
    endfunction
    private function UnloadBigInt takes BigInt i returns nothing
        local integer d = count
        
        loop
            set i = i.previous
            exitwhen i.end
            if (bit[d]) then
                set i.digit = 1
            else
                set i.digit = 0
            endif
            set d = d - 1
        endloop
        
        if (GetParity()) then
            call i.push(1)
        else
            call i.push(0)
        endif
    endfunction
    
    private function Eval takes nothing returns boolean
        call LoadBigInt(loaded)
        call ApplyHamming()
        call UnloadBigInt(loaded)
        
        return false
    endfunction
    
    function ApplyHammingCode takes BigInt i returns nothing
        local Base prevBase = i.base
        set loaded = i
        set i.base = base2
        call TriggerEvaluate(tval)
        set i.base = prevBase
    endfunction
    
    private function LoadBigInt2 takes BigInt i returns nothing
        set count = 0
        loop
            set i = i.next
            exitwhen i.end
            set count = count + 1
            set bit[count] = i.digit != 0
        endloop
    endfunction
    private function CheckHamming takes nothing returns boolean
        set power = 1
        loop
            exitwhen power > count
            if (bit[power] != TriggerEvaluate(tval2)) then
                return false
            endif
            set power = power * 2
        endloop
        return true
    endfunction
    private function UnloadBigInt2 takes BigInt i returns nothing
        local integer pow = 1
        local integer c = 1
        loop
            exitwhen pow > count
            call i.pop()
            set pow = pow * 2
        endloop
        set pow = 1
        loop
            loop
                exitwhen c != pow
                set pow = pow * 2
                set c = c + 1
            endloop
            set i = i.next
            exitwhen i.end
            if (bit[c]) then
                set i.digit = 1
            else
                set i.digit = 0
            endif
            set c = c + 1
        endloop
    endfunction
    private function Eval2 takes nothing returns boolean
        set parity = (0 != loaded.pop())
        call LoadBigInt2(loaded)
        if (parity == GetParity() and CheckHamming()) then
            //call UnloadBigInt2(loaded)
            if (parity) then
                call loaded.push(1)
            else
                call loaded.push(0)
            endif
            return true
        else
            if (parity) then
                call loaded.push(1)
            else
                call loaded.push(0)
            endif
        endif
        return false
    endfunction
    function CheckHammingCode takes BigInt i returns boolean
        local Base prevBase = i.base
        local boolean checked
        set loaded = i
        set i.base = base2
        set checked = TriggerEvaluate(tval3)
        set i.base = prevBase
        return checked
    endfunction
    
    private module Init
        private static method onInit takes nothing returns nothing
            set base2 = Base["01"]
            set tval = CreateTrigger()
            call TriggerAddCondition(tval, Condition(function Eval))
            set tval2 = CreateTrigger()
            call TriggerAddCondition(tval2, Condition(function GetHammingPower))
            set tval3 = CreateTrigger()
            call TriggerAddCondition(tval3, Condition(function Eval2))
        endmethod
    endmodule
    private struct Inits extends array
        implement Init
    endstruct
    
    globals
        private trigger etest = CreateTrigger()
        private BigInt toTest
        private integer cc = 0
        private integer sum
    endglobals
    private function TT takes nothing returns boolean
        local integer m = 700
        loop
            set cc = cc + 1
            call toTest.add(1,0)
            if (CheckHammingCode(toTest)) then
                /*if (toTest.mod(256) == sum) then
                    return true
                else
                    call ApplyHammingCode(toTest)
                endif*/
                return true
            endif
            set m = m - 1
            exitwhen 0 == m
        endloop
        return false
    endfunction
    private function Test takes BigInt i returns integer
        //set cc = 0
        set toTest = i
        loop
            exitwhen TriggerEvaluate(etest)
        endloop
        return cc
    endfunction
    private function Run takes nothing returns nothing
        local Base base10
        local BigInt int
        
        local integer pow
        
        call TriggerAddCondition(etest, Condition(function TT))
    
        set base10 = Base["0123456789"]
        
        set int = BigInt.convertString("123456", base10)
        set int.base = base2
        
        call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,int.toString())
        
        call ApplyHammingCode(int)
        call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,int.toString())
        /*
        if (CheckHammingCode(int)) then
            call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"Validate Level 1: "+int.toString())
        else
            call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"Invalid Code")
        endif
        */
        
        call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"Validated at: "+I2S(Test(int)))
        call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"Validated at: "+I2S(Test(int)))
        call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"Validated at: "+I2S(Test(int)))
        call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"Validated at: "+I2S(Test(int)))
        call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"Validated at: "+I2S(Test(int)))
        call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"Validated at: "+I2S(Test(int)))
        call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"Validated at: "+I2S(Test(int)))
        
        call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,int.toString())
        
        
        call DestroyTimer(GetExpiredTimer())
    endfunction
    private struct Tester extends array
        private static method onInit takes nothing returns nothing
            call TimerStart(CreateTimer(),0,false,function Run)
        endmethod
    endstruct
endscope