Google PageRank Checksum Algorithm

look at this:

http://www.prweaver.com/blog/2004/09...heksum-toolbar

[doctorow]

Thanks for the info, mosert.

A first glimse into v2.0.114.1 reveals that the Bob Jenkins hash is applied twice now:
1. bobJenkinsHash(info:url) // results in the old checksum seed like used in older toolbar versions
2. generate a 80 byte table from the hash in 1.
3. bobJenkinsHash(80 byte table) // which is the new checksum seed

So all that is necessary is to add the code for converting the first hash into the 80 byte table. I am going to add the assembler snippets in a bit here.

Doc

how did you find these conclusions without the assembler snippet ?

now game has opened : we are toying with google !

[doctorow]

I do have the snippet Just have to clean it up before posting them here.

[Colin Dunstan]

So here is the promised update, in assembler code:

Before Toolbar v2.0.114, this was basically the code to calculate the CH:

PHP Code:

CHStart:
        mov    esi, 0E6359A60h    ; GOOGLE_MAGIC
        push    esi
        push    dword ptr [ebp-3Ch] ; info:URL size
        push    eax        ; info:URL
        call    _bobJenkinsHash 


After that, one only had to convert eax to unsigned integer and prepand CH=6.

In Toolbar v2.0.114, Google doesn't stop here. The code goes on:

PHP Code:

newCode:
        push    eax        ; resulting 32bit hash (used as    final hash in toolbar <    2.0.114
        call    _32bitMutation
        add    esp, 10h
        mov    [ebp+0Ch], eax
        xor    eax, eax
        lea    ecx, [ebp-0B0h]

generate80ByteTable:
        mov    edx, [ebp+0Ch]
        sub    edx, eax
        mov    [ecx], edx
        add    eax, 9
        add    ecx, 4
        cmp    eax, 180
        jb    short generate80ByteTable
        push    esi        ; GOOGLE_MAGIC (0xE6359A60)
        lea    eax, [ebp-0B0h]
        push    80        ; Table    size
        push    eax        ; Table    offset
        call    _bobJenkinsHash 


with function generate80ByteTable:

PHP Code:

_32bitMutation    proc near

hash        = dword    ptr  4

        mov    eax, [esp+4]
        push    esi
        push    0Dh
        pop    ecx
        xor    edx, edx
        div    ecx
        mov    eax, [esp+4+hash]
        push    7
        pop    esi
        mov    ecx, edx
        xor    edx, edx
        div    esi
        and    ecx, 7
        pop    esi
        shl    eax, 2
        or    eax, ecx
        retn
_32bitMutation    endp 


So as I said before, the Bob Jenkins hash is applied twice now:
1. bobJenkinsHash(info:url)
2. the resulting hash (32bit) undergoes a small modification
3. generate a 80 byte table from the modified hash in 1.
4. bobJenkinsHash(80 byte table)

After that, like in previous toolbar versions, you convert eax to unsigned integer and prepand CH=6.

The remaining step is to transcode the assembler snippets into high-level again.

I've got a job now so dont have rediculous amounts of free time to update my code. However I will give it a shot whenever I get a chance if nobody else beats me too it.

Ok, got some spare time tonight, going to comment the new code so we can get an idea of whats going on with the new code

Can you please post a FULL ASM dump of the hash code please, just in case any of the registers being used have changed or something.

[alexstapleton]

PHP Code:

 _32bitMutation    proc near

        hash        = dword    ptr  4
                                    //why is this named hash?
                                    //it seems to be more or less the same as var_4 in the old version
                                    //but positive of course

        mov    eax, [esp+4]            //eax becomes equal to the 4th URL char
            $eax = $url[3];
        
        push    esi                    //esi to stack
                                    //esi is the result of the 4th XOR round of BJHash
                                    //i havent seen the latest dump yet though so this could be wrong
        
        push    0Dh                    // ecx = 13 }
        pop    ecx                    // ecx = 13 }
        
        xor    edx, edx                // edx = 0
            $edx = 0;
        
        div    ecx                    // ecx = ecx/13
            $eax = (int)($eax/13);
        
        mov    eax, [esp+4+hash]    //eax becomes equal to the 8th URL char
            $eax = $url[7];
        
        push    7                    // esi = 7 }
        pop    esi                    // esi = 7 }
        
            $esi = 7;
        
        mov    ecx, edx                // ecx = remainder of the DIV
            $ecx = $eax%13;
        
        xor    edx, edx                // edx = 0
            $edx = 0;
            
        div    esi                    // eax DIV 7
            $eax = $eax/7;
            
        and    ecx, 7                // ecx AND 7
            $ecx = $ecx & 7;
            
        pop    esi                    // return the value to esi we saved at the start
            $esi = $BJHash[3][0];
        
        shl    eax, 2                //multiply eax by 8
            $eax = ($eax << 2);
        
        or    eax, ecx                //eax OR ecx
            $eax = $eax | $ecx;
        
        retn 


[alexstapleton]

please check my above ASM with bits o PHP stuck in for mistakes please

No idea if this gives the right output or not but easier to read.

$p is called so because the 4th char should almost always p
$w is called so because the 8th char should not quite almost always be w

e.g. http://www

capiche?

ive converted this to high level somewhat

PHP Code:

function Mutate($url, $BJHash) {
    $p = $url[3];
    $rem = ($p%13);

    $w = $url[7];
    $w = $w/7;
    $rem = $rem & 7;

    $rem_shl = ($rem << 2);
    $mut = $rem_shl | $rem;
    
    return $mut;
} 


[gprm]

Hi all,

I've just done all the work in C, including a small checksum calculator.
Enjoy and don't forget to greet me in your upcoming tools
http://pagerank.mindsay.com/

Tarakan

[alexstapleton]

almost figured out the 80byte table bit, will post findings tomorrow. need sleep!

someone check my 32 bit mutate stuff and report back!!!

[alexstapleton]

ah right gprm beat me too it, nice one. if nobody has got a php version up by tomorrow evening ill do one. (damned jobs getting in the way of geekdom)

[doctorow]

Nice job guys!

gprm, I hope you don't mind me posting your c source here?

 
/* 
gET my pAGE rANK mOFO !
A piece of code made for fun. This is an extract from GPRM. 
Don't take this checksum thing too seriously. 
Google can't reasonably expect to protect his technology with a table look-up hash algorithm ?!
gprm@altern.org 
This code is published under the GNU Public License.
If you use it, you have to explicitely mention GPRM and me.
Tarakan
*/
 
// checksum calculation, plain C
char data[160];
char url[500];
unsigned int prbuf[20],l;
char site[150];
strcpy(data, "info:");
strcat(data, site);
l=hash((unsigned char *)data, strlen(data), 0xe6359a60);
l=(((l/7) << 2) | ((l%13)&7));
prbuf[0]=l;
for(i=1; i<20; i++) prbuf[i]=prbuf[i-1]-9;
l=hash((BYTE *)prbuf, 80, 0xe6359a60);

[doctorow]

Alex, I know what you mean btw. Often also the opposite is true: geekdom is getting in the way of my job