NB. ampharmex's hashing function NB. ischtche%uwaterloo.ca 2014-04-10 NB. attempt 1: quick and dirty C1 =: 16b5c7f0d2e6c0f1c83 C2 =: 16b358b76aef8ce1568 C3 =: 16bd2e6ef7d83b5285c NB. too big somehow? C3 =: 15197097314967955548 NB. use this? rotl =: 32 b.~ NB. this fails with C3 as an argument... rotr =: rotl - hash =: 3 : 0 NB. direct transcription of C function y =. y XOR y * C1 XOR C2 y =. y rotr 16 | y y =. y * y -~ C2 XOR C3 y =. y rotl 16 | y y =. y + y * C3 XOR C1 y =. y rotl 80 | y y ) hash =: (rotl 80&|)@:(+ (C3 XOR C1)&*)@:(rotl 16&|)@:(* (C2 XOR C3)&-)@:(rotr 16&|)@:(XOR (C1 XOR C2)&*) NB. fails rotl =: (64#2) #. ] |. (64#2) #: [ xor =: ~:&.((64$2)&#:) xxor =: x: @ xor & x hash =: (rotl 80&|)@:(+ (C3 xxor C1)&*)@:(rotl 16&|)@:(* (C2 xxor C3)&-)@:(rotr 16&|)@:(xxor (C1 xxor C2)&*) NB. succeeds, incorrect hash 1295719822172x NB. this attempt fails because j has 64-bit signed integers and the problem calls for unsigned NB. attempt number 2: if you want it done right, do it yourself bv =: ([: , 2 2 2 2 #: '0123456789abcdef' i. ])"1 :. hex NB. bitvector bvi =: 64&bvi : (-@[ {."1 #:@]) :. #. NB. bitvector from int hex =: ('0123456789abcdef' {~ _4 #.\ ])"1 :. bv 'c1 c2 c3' =: bv '5c7f0d2e6c0f1c83','358b76aef8ce1568',:'d2e6ef7d83b5285c' NB. xor NB. trivial in this representation, as are other logical bitops xor =: ~: NB. addition NB. first, laminate under reversal, to align the numbers right NB. then, repeatedly make sum and carry bv's, shift carry bv, and add NB. finally, discard the useless 0 row and unreverse add =: {. @: ((~: ,: |.!.0 @: *.)/^:_) @: ,: &. |. NB. subtraction NB. add the two's complement negative, which is 1 + bitwise negation on +ve neg =: (,1) add -. sub =: add neg NB. multiplication NB. use the right argument to shift the left over to each bit place NB. then add them all up via folding mul =: add/ @: (1&(|.!.0)"0 _~ I.@|.) NB. assertions '69f47b8094c109eb' -: hex (c1 xor c2) '92739049018d2174' -: hex (c1 xor c2) mul bvi 1295719822172x NB. modulus NB. observe that, for modulo 80: NB. 80 | n0 + (16 * n1) + (256 * n2) + (4096 * n3) + ... NB. => 80 | n0 + (80 | 16 * n1) + (80 | 256 * n2) + (80 | 4096 * n3) + ... NB. => 80 | n0 + ((80|16) * 80|n1) + ((80|256) * 80|n2) + ((80|4096) * 80|n3) + ... NB. => 80 | n0 + (16 * 80|n1) + (16 * 80|n2) + (16 * 80|n3) + ... NB. => 80 | n0 + 16 * 80 | n1 + n2 + n3 + ... NB. this is not too big for j to handle, so we're just going to cheat m16 =: [: #. _4 {. ] m80 =: 80 | _ 16 #. [: (+/@}: , {:) _4 #.\ ] rotl =: |.~ NB. x is a bv, y is a j integer rotr =: rotl - NB. as above empty 0 : 0 00:38 < ischtche> ampharmex, could you print all of the intermediate values of your hash function for this value 1295719822172? 00:38 < ischtche> i.e. the value of v after each assignment 00:41 < ampharmex> 92739164af665228 // v ^= (C1 ^ C2) * v; 00:41 < ampharmex> 2892739164af6652 // v = rotr(v, v & 0xF); 00:41 < ampharmex> c366078ab166e064 // v *= (C2 ^ C3) - v; 00:41 < ampharmex> 366078ab166e064c // v = rotl(v, v & 0xF); 00:41 < ampharmex> e5d27cb780c4f280 // v += (C3 ^ C1) * v; 00:41 < ampharmex> e5d27cb780c4f280 // v = rotl(v, v % 80); 00:41 < ampharmex> e5d27cb780c4f280 // return v; ) hash =: (rotl m80)@:(add (c3~:c1)&mul)@:(rotl m16)@:(mul (c2~:c3)&sub)@:(rotr m16)@:(xor (c1~:c2)&mul) NB. it works! 'e5d27cb780c4f280' -: hex hash bvi 1295719822172x