Good day.
Current checksum is not calculated in intended way and
has the flaw.
Single round function is written as:
#define CHECKSUM_COMP(checksum, value) do {\
uint32 __tmp = (checksum) ^ (value);\
(checksum) = __tmp * FNV_PRIME ^ (__tmp >> 17);\
} while (0)
And looks like it was intended to be
(checksum) = (__tmp * FNV_PRIME) ^ (__tmp >> 17);
At least original Florian Pflug suggestion were correctly written
in this way (but with shift 1):
https://www.postgresql.org/message-id/99343716-5F5A-45C8-B2F6-74B9BA357396%40phlo.org
But due to C operation precedence it is actually calculated as:
(checksum) = __tmp * (FNV_PRIME ^ (__tmp >> 17));
It has more longer collision chains and worse: it has 256 pathological
result slots of shape 0xXX000000 each has 517 collisions in average.
Totally 132352 __tmp values are collided into this 256 slots.
That is happens due to if top 16 bits are happens to be
0x0326 or 0x0327, then `FNV_PRIME ^ (__tmp >> 17) == 0x1000000`,
and then `__tmp * 0x1000000` keeps only lower 8 bits. That means,
9 bits masked by 0x0001ff00 are completely lost.
mix(0x03260001) == mix(0x03260101) = mix(0x0327aa01) == mix(0x0327ff01)
(where mix is a `__tmp` to `checksum` transformation)
regards,
Yura Sokolov
y.soko...@postgrespro.ru
funny.fal...@gmail.com
PS. Test program in Crystal language is attached and output for current
CHECKSUM_COMP implementation and "correct" (intended).
Excuse me for Crystal, it is prettier to write for small compiled
scripts.- 17 items at 38 slots
- 16 items at 114 slots
- 15 items at 456 slots
- 14 items at 1690 slots
- 13 items at 3706 slots
- 12 items at 11128 slots
- 11 items at 30994 slots
- 10 items at 84940 slots
- 9 items at 259160 slots
- 8 items at 778102 slots
- 7 items at 2413624 slots
- 6 items at 8670652 slots
- 5 items at 27772912 slots
- 4 items at 93426142 slots
- 3 items at 288544882 slots
- 2 items at 752648630 slots
- 1 items at 1332584708 slots
- 0 items at 1787735418 slots
Pathological 513 collisions at slot 00000000
Pathological 515 collisions at slot 01000000
Pathological 517 collisions at slot 02000000
Pathological 518 collisions at slot 03000000
Pathological 516 collisions at slot 04000000
Pathological 514 collisions at slot 05000000
Pathological 516 collisions at slot 06000000
Pathological 516 collisions at slot 07000000
Pathological 515 collisions at slot 08000000
Pathological 518 collisions at slot 09000000
Pathological 516 collisions at slot 0a000000
Pathological 516 collisions at slot 0b000000
Pathological 517 collisions at slot 0c000000
Pathological 515 collisions at slot 0d000000
Pathological 516 collisions at slot 0e000000
Pathological 514 collisions at slot 0f000000
Pathological 515 collisions at slot 10000000
Pathological 516 collisions at slot 11000000
Pathological 515 collisions at slot 12000000
Pathological 518 collisions at slot 13000000
Pathological 514 collisions at slot 14000000
Pathological 516 collisions at slot 15000000
Pathological 515 collisions at slot 16000000
Pathological 516 collisions at slot 17000000
Pathological 515 collisions at slot 18000000
Pathological 516 collisions at slot 19000000
Pathological 515 collisions at slot 1a000000
Pathological 519 collisions at slot 1b000000
Pathological 516 collisions at slot 1c000000
Pathological 517 collisions at slot 1d000000
Pathological 515 collisions at slot 1e000000
Pathological 517 collisions at slot 1f000000
Pathological 514 collisions at slot 20000000
Pathological 517 collisions at slot 21000000
Pathological 517 collisions at slot 22000000
Pathological 518 collisions at slot 23000000
Pathological 515 collisions at slot 24000000
Pathological 517 collisions at slot 25000000
Pathological 519 collisions at slot 26000000
Pathological 516 collisions at slot 27000000
Pathological 514 collisions at slot 28000000
Pathological 518 collisions at slot 29000000
Pathological 515 collisions at slot 2a000000
Pathological 516 collisions at slot 2b000000
Pathological 517 collisions at slot 2c000000
Pathological 514 collisions at slot 2d000000
Pathological 516 collisions at slot 2e000000
Pathological 517 collisions at slot 2f000000
Pathological 515 collisions at slot 30000000
Pathological 517 collisions at slot 31000000
Pathological 518 collisions at slot 32000000
Pathological 519 collisions at slot 33000000
Pathological 515 collisions at slot 34000000
Pathological 519 collisions at slot 35000000
Pathological 517 collisions at slot 36000000
Pathological 517 collisions at slot 37000000
Pathological 516 collisions at slot 38000000
Pathological 516 collisions at slot 39000000
Pathological 519 collisions at slot 3a000000
Pathological 517 collisions at slot 3b000000
Pathological 517 collisions at slot 3c000000
Pathological 516 collisions at slot 3d000000
Pathological 517 collisions at slot 3e000000
Pathological 518 collisions at slot 3f000000
Pathological 514 collisions at slot 40000000
Pathological 518 collisions at slot 41000000
Pathological 515 collisions at slot 42000000
Pathological 515 collisions at slot 43000000
Pathological 517 collisions at slot 44000000
Pathological 515 collisions at slot 45000000
Pathological 516 collisions at slot 46000000
Pathological 516 collisions at slot 47000000
Pathological 516 collisions at slot 48000000
Pathological 518 collisions at slot 49000000
Pathological 515 collisions at slot 4a000000
Pathological 517 collisions at slot 4b000000
Pathological 515 collisions at slot 4c000000
Pathological 517 collisions at slot 4d000000
Pathological 516 collisions at slot 4e000000
Pathological 518 collisions at slot 4f000000
Pathological 515 collisions at slot 50000000
Pathological 516 collisions at slot 51000000
Pathological 518 collisions at slot 52000000
Pathological 517 collisions at slot 53000000
Pathological 514 collisions at slot 54000000
Pathological 520 collisions at slot 55000000
Pathological 516 collisions at slot 56000000
Pathological 518 collisions at slot 57000000
Pathological 516 collisions at slot 58000000
Pathological 519 collisions at slot 59000000
Pathological 515 collisions at slot 5a000000
Pathological 517 collisions at slot 5b000000
Pathological 516 collisions at slot 5c000000
Pathological 517 collisions at slot 5d000000
Pathological 517 collisions at slot 5e000000
Pathological 516 collisions at slot 5f000000
Pathological 514 collisions at slot 60000000
Pathological 518 collisions at slot 61000000
Pathological 517 collisions at slot 62000000
Pathological 516 collisions at slot 63000000
Pathological 517 collisions at slot 64000000
Pathological 518 collisions at slot 65000000
Pathological 517 collisions at slot 66000000
Pathological 517 collisions at slot 67000000
Pathological 517 collisions at slot 68000000
Pathological 515 collisions at slot 69000000
Pathological 517 collisions at slot 6a000000
Pathological 519 collisions at slot 6b000000
Pathological 517 collisions at slot 6c000000
Pathological 518 collisions at slot 6d000000
Pathological 518 collisions at slot 6e000000
Pathological 516 collisions at slot 6f000000
Pathological 516 collisions at slot 70000000
Pathological 518 collisions at slot 71000000
Pathological 518 collisions at slot 72000000
Pathological 519 collisions at slot 73000000
Pathological 517 collisions at slot 74000000
Pathological 517 collisions at slot 75000000
Pathological 517 collisions at slot 76000000
Pathological 517 collisions at slot 77000000
Pathological 515 collisions at slot 78000000
Pathological 518 collisions at slot 79000000
Pathological 517 collisions at slot 7a000000
Pathological 517 collisions at slot 7b000000
Pathological 517 collisions at slot 7c000000
Pathological 517 collisions at slot 7d000000
Pathological 518 collisions at slot 7e000000
Pathological 516 collisions at slot 7f000000
Pathological 514 collisions at slot 80000000
Pathological 520 collisions at slot 81000000
Pathological 516 collisions at slot 82000000
Pathological 517 collisions at slot 83000000
Pathological 516 collisions at slot 84000000
Pathological 519 collisions at slot 85000000
Pathological 516 collisions at slot 86000000
Pathological 518 collisions at slot 87000000
Pathological 517 collisions at slot 88000000
Pathological 517 collisions at slot 89000000
Pathological 517 collisions at slot 8a000000
Pathological 518 collisions at slot 8b000000
Pathological 515 collisions at slot 8c000000
Pathological 517 collisions at slot 8d000000
Pathological 517 collisions at slot 8e000000
Pathological 520 collisions at slot 8f000000
Pathological 515 collisions at slot 90000000
Pathological 517 collisions at slot 91000000
Pathological 516 collisions at slot 92000000
Pathological 518 collisions at slot 93000000
Pathological 518 collisions at slot 94000000
Pathological 515 collisions at slot 95000000
Pathological 518 collisions at slot 96000000
Pathological 520 collisions at slot 97000000
Pathological 515 collisions at slot 98000000
Pathological 518 collisions at slot 99000000
Pathological 517 collisions at slot 9a000000
Pathological 517 collisions at slot 9b000000
Pathological 517 collisions at slot 9c000000
Pathological 518 collisions at slot 9d000000
Pathological 518 collisions at slot 9e000000
Pathological 518 collisions at slot 9f000000
Pathological 516 collisions at slot a0000000
Pathological 516 collisions at slot a1000000
Pathological 518 collisions at slot a2000000
Pathological 517 collisions at slot a3000000
Pathological 517 collisions at slot a4000000
Pathological 517 collisions at slot a5000000
Pathological 517 collisions at slot a6000000
Pathological 518 collisions at slot a7000000
Pathological 516 collisions at slot a8000000
Pathological 517 collisions at slot a9000000
Pathological 518 collisions at slot aa000000
Pathological 517 collisions at slot ab000000
Pathological 517 collisions at slot ac000000
Pathological 516 collisions at slot ad000000
Pathological 517 collisions at slot ae000000
Pathological 517 collisions at slot af000000
Pathological 515 collisions at slot b0000000
Pathological 519 collisions at slot b1000000
Pathological 517 collisions at slot b2000000
Pathological 515 collisions at slot b3000000
Pathological 517 collisions at slot b4000000
Pathological 519 collisions at slot b5000000
Pathological 516 collisions at slot b6000000
Pathological 519 collisions at slot b7000000
Pathological 516 collisions at slot b8000000
Pathological 519 collisions at slot b9000000
Pathological 517 collisions at slot ba000000
Pathological 518 collisions at slot bb000000
Pathological 516 collisions at slot bc000000
Pathological 519 collisions at slot bd000000
Pathological 518 collisions at slot be000000
Pathological 518 collisions at slot bf000000
Pathological 515 collisions at slot c0000000
Pathological 517 collisions at slot c1000000
Pathological 518 collisions at slot c2000000
Pathological 518 collisions at slot c3000000
Pathological 517 collisions at slot c4000000
Pathological 520 collisions at slot c5000000
Pathological 516 collisions at slot c6000000
Pathological 519 collisions at slot c7000000
Pathological 516 collisions at slot c8000000
Pathological 517 collisions at slot c9000000
Pathological 520 collisions at slot ca000000
Pathological 519 collisions at slot cb000000
Pathological 517 collisions at slot cc000000
Pathological 519 collisions at slot cd000000
Pathological 517 collisions at slot ce000000
Pathological 517 collisions at slot cf000000
Pathological 517 collisions at slot d0000000
Pathological 519 collisions at slot d1000000
Pathological 517 collisions at slot d2000000
Pathological 519 collisions at slot d3000000
Pathological 518 collisions at slot d4000000
Pathological 517 collisions at slot d5000000
Pathological 519 collisions at slot d6000000
Pathological 517 collisions at slot d7000000
Pathological 518 collisions at slot d8000000
Pathological 517 collisions at slot d9000000
Pathological 517 collisions at slot da000000
Pathological 517 collisions at slot db000000
Pathological 517 collisions at slot dc000000
Pathological 520 collisions at slot dd000000
Pathological 516 collisions at slot de000000
Pathological 520 collisions at slot df000000
Pathological 516 collisions at slot e0000000
Pathological 517 collisions at slot e1000000
Pathological 518 collisions at slot e2000000
Pathological 517 collisions at slot e3000000
Pathological 517 collisions at slot e4000000
Pathological 520 collisions at slot e5000000
Pathological 519 collisions at slot e6000000
Pathological 518 collisions at slot e7000000
Pathological 517 collisions at slot e8000000
Pathological 518 collisions at slot e9000000
Pathological 518 collisions at slot ea000000
Pathological 518 collisions at slot eb000000
Pathological 517 collisions at slot ec000000
Pathological 520 collisions at slot ed000000
Pathological 519 collisions at slot ee000000
Pathological 519 collisions at slot ef000000
Pathological 516 collisions at slot f0000000
Pathological 520 collisions at slot f1000000
Pathological 517 collisions at slot f2000000
Pathological 519 collisions at slot f3000000
Pathological 519 collisions at slot f4000000
Pathological 517 collisions at slot f5000000
Pathological 518 collisions at slot f6000000
Pathological 518 collisions at slot f7000000
Pathological 517 collisions at slot f8000000
Pathological 519 collisions at slot f9000000
Pathological 519 collisions at slot fa000000
Pathological 518 collisions at slot fb000000
Pathological 516 collisions at slot fc000000
Pathological 520 collisions at slot fd000000
Pathological 517 collisions at slot fe000000
Pathological 519 collisions at slot ff000000
- 520 items at 12 slots
- 519 items at 28 slots
- 518 items at 47 slots
- 517 items at 82 slots
- 516 items at 47 slots
- 515 items at 29 slots
- 514 items at 10 slots
- 513 items at 1 slots
- 22 items at 2 slots
- 21 items at 3 slots
- 20 items at 31 slots
- 19 items at 76 slots
- 18 items at 250 slots
- 17 items at 693 slots
- 16 items at 2027 slots
- 15 items at 5766 slots
- 14 items at 15425 slots
- 13 items at 39906 slots
- 12 items at 101199 slots
- 11 items at 247770 slots
- 10 items at 600878 slots
- 9 items at 1440024 slots
- 8 items at 3436515 slots
- 7 items at 8188413 slots
- 6 items at 19516765 slots
- 5 items at 46532614 slots
- 4 items at 111084180 slots
- 3 items at 265462851 slots
- 2 items at 627298436 slots
- 1 items at 1341157172 slots
- 0 items at 1869836044 slots
# Build:
# crystal build --release checksum.cr
# Run:
# ./checksum current | tee checksum_current.out
# ./checksum correct | tee checksum_correct.out
struct BA
def initialize
@bytes = Pointer(UInt8).malloc(1u32<<31)
@extra = Hash(UInt32,UInt32).new(0)
end
def [](index : UInt32) : UInt32
ix, off = index.divmod(2)
off *= 4
v = @bytes[ix]
v = (v>>off) & 0xf
v < 0xf ? v.to_u32 : @extra[index]
end
def []=(index : UInt32, value : UInt32)
ix, off = index.divmod(2)
off *= 4
b = @bytes[ix]
if value < 0xf
b &= ~(0xfu8 << off)
b |= value.to_u8 << off
else
b |= 0xfu8 << off
@extra[index] = value
end
@bytes[ix] = b
value
end
end
ba = BA.new
FNV = 16777619u32
case (ARGV[0]||"current")
when "current"
0u32.upto(~0u32) do |i|
c : UInt32 = i &* (FNV ^ (i >> 17))
ba[c] += 1
end
when "correct"
0u32.upto(~0u32) do |i|
c : UInt32 = (i &* FNV) ^ (i >> 17)
ba[c] += 1
end
when "murmur"
0u32.upto(~0u32) do |i|
c : UInt32 = i ^ (i >> 16)
c = c &* 0x85ebca6bu32
c ^= c >> 13
c = c &* 0xc2b2ae35u32
c ^= c >> 16
ba[c] += 1
end
else
raise "Unrecognized algo"
end
collisions = Hash(UInt32, UInt64).new(0)
0u32.upto(~0u32) do |i|
v = ba[i]
collisions[v] += 1
if v >= 255
printf "Pathologic %d collisions at slot %08x\n", v, i
end
end
collisions.to_a.
sort_by{|k,v| k}.
reverse.
each do |k,v|
printf "- %d items at %d slots\n", k, v
end
