ChecksumPíšu si vlastní patcher, programek co vyrobí rozdílový derivát mezi starou a novou verzí binárního souboru. Musí umět zvládnout až stovky gigabajtů. Řeším to metodou částečných checksumů počítaných z fragmentů. Fragmentů může být až několik stovek tisíc. I tak může mít jeden fragment několik desítek i stovek kilobajtů (ani megabajt není výjimkou)
No a potřeboval bych něco jako průběžný checksum. Problém je, že ho nechci počítat po každém bajtu a přesto bych potřeboval, aby odpovídal checksumu načtených bajtů ve fragment bufferu.
Když si spočítám složitost výpočtu po každém bajtu, dojdu k tomuto:
počet cyklu = M * N, kde N je velikost souboru a M je velikost fragmentu.
A protože M = k * N
O = M * N = k * N * N = k * N2 = N2
Přestože k<<1, tak N2 přímo nahání hrůzu
Potřeboval bych checksum, který by byl silný (dobře by vyjadřoval obsah fragmentu), zároveň abych uměl reflektovat odebrání prvního bajtu, posun fronty a přdání bajtu na konec. Napadli mne tyto varianty
- chk = chk + b (prostý součet)
- chk = chk + (b rotl fn(b))
- chk = (chk rotl k) xor b
rotl - rotace vlevo
1 je prostý checksum, 2 je jen vylepšený checksum pro využití celého rozsahu proměnné. 3 je xorovaný checksum, který jako jediný je nekomutativní (abcd je jiný výsledek než dcba).
Ve všech případech ale se bojím, že checksum není dost silný a povede ke spoustě falešných poplachů (kdy patcher bude zbytečně zkoumat fragmenty, které nejsou stejné ale mají stejný checksum).
Měl by někdo nápad na lepší řešení? Nesetkal se někdo s něčím takovým? |
Registrace nového uživatele 
