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

do góry

On 8/24/20 8:37 AM, Borneq wrote:
> 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

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.

do góry

2020-08-24 o 10:10 +0200, Borneq napisał:
> On 8/24/20 8:37 AM, Borneq wrote:
> > 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
>
> 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.

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

do góry

On 8/24/20 10:10 AM, Borneq wrote:
> On 8/24/20 8:37 AM, Borneq wrote:
> 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.

Fletcher sum?

do góry

On 8/24/20 10:20 AM, Mateusz Viste wrote:
> 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

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?

do góry

2020-08-24 o 13:31 +0200, Borneq napisał:
> On 8/24/20 10:20 AM, Mateusz Viste wrote:
> > 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
>
> 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

do góry

On 8/24/20 1:48 PM, Mateusz Viste wrote:
> 2020-08-24 o 13:31 +0200, Borneq napisał:
>> On 8/24/20 10:20 AM, Mateusz Viste wrote:
>>> 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
>>
>> 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;
}

do góry

2020-08-24 o 13:52 +0200, Borneq napisał:
> No tak, ale jak potem zamienić jeden bajt na inny?

Nie znam prostej metody.

> 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

do góry