Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #34137 > unrolled thread

Hasz dla permutacji

Back to article view | Back to pl.comp.programming

Contents

  Hasz dla permutacji Borneq <borneq@antyspam.hidden.pl> - 2020-08-24 08:37 +0200
    Re: Hasz dla permutacji Borneq <borneq@antyspam.hidden.pl> - 2020-08-24 10:10 +0200
      Re: Hasz dla permutacji Mateusz Viste <mateusz@xyz.invalid> - 2020-08-24 10:20 +0200
        Re: Hasz dla permutacji Borneq <borneq@antyspam.hidden.pl> - 2020-08-24 13:31 +0200
          Re: Hasz dla permutacji Mateusz Viste <mateusz@xyz.invalid> - 2020-08-24 13:48 +0200
            Re: Hasz dla permutacji Borneq <borneq@antyspam.hidden.pl> - 2020-08-24 13:52 +0200
              Re: Hasz dla permutacji Mateusz Viste <mateusz@xyz.invalid> - 2020-08-24 13:57 +0200
      Re: Hasz dla permutacji Borneq <borneq@antyspam.hidden.pl> - 2020-08-24 10:46 +0200

#34137 — Hasz dla permutacji

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

[toc] | [next] | [standalone]

#34138

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.

[toc] | [prev] | [next] | [standalone]

#34139

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

[toc] | [prev] | [next] | [standalone]

#34141

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?

[toc] | [prev] | [next] | [standalone]

#34142

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

[toc] | [prev] | [next] | [standalone]

#34143

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;
}

[toc] | [prev] | [next] | [standalone]

#34144

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

[toc] | [prev] | [next] | [standalone]

#34140

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?

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.programming

csiph-web