Hasz dla permutacji

[Borneq]

Mam permutację np. 5 7 1 2 8 ..4
chce każdą oznaczyć haszem, chętnie 64 bitowym by uniknąć kolizji 32
bitów choć ostatecznie 32 bity to też male prawdopodobieństwo kolizji.
Ma mieć własności:
- nie działam na bitach ale na liczbach, np. 1204 999 451 1021...
nieduże liczby

- prosty hasz z możliwością generowania przyrostowego:
jak zamieniam liczbę numer 21 z 45 to ze starego generuję nowy hasz,
najlepiej nie z całej tablicy, tak działa prosty XOR, tylko problem: ma
być conajmniej 32 bity a nie tyle bitów ile mają liczby

[Borneq]

Post by Borneq
Mam permutację np. 5 7 1 2 8 ..4
chce każdą oznaczyć haszem, chętnie 64 bitowym by uniknąć kolizji 32
bitów choć ostatecznie 32 bity to też male prawdopodobieństwo kolizji.
- nie działam na bitach ale na liczbach, np. 1204 999 451 1021...
nieduże liczby
jak zamieniam liczbę numer 21 z 45 to ze starego generuję nowy hasz,
najlepiej nie z całej tablicy, tak działa prosty XOR, tylko problem: ma
być conajmniej 32 bity a nie tyle bitów ile mają liczby

XOR jest nieczuły na kolejność, więc xor wraz z numerem pozycji:
0 xor tab[0] xor 1 xor tab[1] xor 2 xor tab[2] xor...
wada: dla małych liczb hash będzie mały, nie całe 32/64 bity, więc
byłoby niebezpieczeństwo że dwie permiutacje będą miały ten sam hash.

[Mateusz Viste]

Post by Borneq

Post by Borneq
Mam permutację np. 5 7 1 2 8 ..4
chce każdą oznaczyć haszem, chętnie 64 bitowym by uniknąć kolizji
32 bitów choć ostatecznie 32 bity to też male prawdopodobieństwo
- nie działam na bitach ale na liczbach, np. 1204 999 451 1021...
nieduże liczby
jak zamieniam liczbę numer 21 z 45 to ze starego generuję nowy
hasz, najlepiej nie z całej tablicy, tak działa prosty XOR, tylko
problem: ma być conajmniej 32 bity a nie tyle bitów ile mają
liczby

0 xor tab[0] xor 1 xor tab[1] xor 2 xor tab[2] xor...
wada: dla małych liczb hash będzie mały, nie całe 32/64 bity, więc
byłoby niebezpieczeństwo że dwie permiutacje będą miały ten sam hash.

Rób dwie operacje: xor oraz shift jednego bitu... Tak działa BSD sum.
Zalety takie, że jeszt bardzo szybki oraz wrażliwy na inwersję
wartości. Szerokość takiego hashu sobie możesz dopasować sam, wystarczy
użyć innego clampingu.

3 lata temu popełniłem tego implementację:
https://sourceforge.net/p/bsum/code/HEAD/tree/trunk/bsum.asm

Mateusz

[Borneq]

Post by Mateusz Viste
Rób dwie operacje: xor oraz shift jednego bitu... Tak działa BSD sum.
Zalety takie, że jeszt bardzo szybki oraz wrażliwy na inwersję
wartości. Szerokość takiego hashu sobie możesz dopasować sam, wystarczy
użyć innego clampingu.
https://sourceforge.net/p/bsum/code/HEAD/tree/trunk/bsum.asm

Zastanwiam się, bo taki hasz ma okreśłoną "pojemność" po 32 takich
przeunięciach wcześniejsze wartości nie będą miały żadnego wpływu na sumę.
Sam crc można lokalnie modyfikować:
https://github.com/drmikehenry/crc_incremental, metoda testIncrFile i
zmienna fastNewCrc. ALE
zmiana to pętla w pętli w calcCrcZeros

mi chodzi o prostą sumę.
Może tak (pomijając obcinanie do długości słowa):
checkusm = SUMA (data[i] * (i+1))

mnożenie na dzisiejszych kompach jest bardzo szybkie
jest wrażliwy na kolejność
czy to byłoby dobre?

[Mateusz Viste]

Post by Borneq

Post by Mateusz Viste
Rób dwie operacje: xor oraz shift jednego bitu... Tak działa BSD
sum. Zalety takie, że jeszt bardzo szybki oraz wrażliwy na inwersję
wartości. Szerokość takiego hashu sobie możesz dopasować sam,
wystarczy użyć innego clampingu.
https://sourceforge.net/p/bsum/code/HEAD/tree/trunk/bsum.asm

Zastanwiam się, bo taki hasz ma okreśłoną "pojemność" po 32 takich
przeunięciach wcześniejsze wartości nie będą miały żadnego wpływu na sumę.

Mój błąd, z rozpędu i przyzwyczajenia napisałem "shift", a powinno być
"rotate". W kodzie który podlinkowałem zobaczysz "ror".

Mateusz

[Borneq]

Post by Mateusz Viste

Post by Borneq

Post by Mateusz Viste
Rób dwie operacje: xor oraz shift jednego bitu... Tak działa BSD
sum. Zalety takie, że jeszt bardzo szybki oraz wrażliwy na inwersję
wartości. Szerokość takiego hashu sobie możesz dopasować sam,
wystarczy użyć innego clampingu.
https://sourceforge.net/p/bsum/code/HEAD/tree/trunk/bsum.asm

Zastanwiam się, bo taki hasz ma okreśłoną "pojemność" po 32 takich
przeunięciach wcześniejsze wartości nie będą miały żadnego wpływu na sumę.

Mój błąd, z rozpędu i przyzwyczajenia napisałem "shift", a powinno być
"rotate". W kodzie który podlinkowałem zobaczysz "ror".
Mateusz

No tak, ale jak potem zamienić jeden bajt na inny?
Z mnożeniem świetnie wychodzi, kod w c++

#include <iostream>
#include <vector>

using namespace std;

int sum1 (vector<int8_t> &v) {
int res = 1;
for (int i=0; i<v.size();i++){
res += v[i]*(i+1);
}
return res;
}


int main() {
vector<int8_t> v;
v.clear();
v.push_back(1);
v.push_back(3);
v.push_back(32);
v.push_back(2);
int sum = sum1(v);
std::cout << sum << std::endl;
v[2]=127;
int fastsum = sum + 3*(127-32);
std::cout << fastsum << " " << sum1(v) << std::endl;
return 0;
}

[Mateusz Viste]

Post by Borneq
No tak, ale jak potem zamienić jeden bajt na inny?

Nie znam prostej metody.

Post by Borneq
Z mnożeniem świetnie wychodzi, kod w c++

No to pozostaje ci już tylko zaimplementować obie wersje i sprawdzić w
warunkach rzeczywistych dla każdego:
- czas wykonania
- statystyczny rozkład
- częstotliwość kolizji

Mateusz

[Borneq]

Post by Borneq
0 xor tab[0] xor 1 xor tab[1] xor 2 xor tab[2] xor...
wada: dla małych liczb hash będzie mały, nie całe 32/64 bity, więc
byłoby niebezpieczeństwo że dwie permiutacje będą miały ten sam hash.

Fletcher sum?