Path: csiph.com!aioe.org!nyPK7k8oeDafdNpooDsxZQ.user.gioia.aioe.org.POSTED!not-for-mail
From: Mateusz Viste <mateusz@xyz.invalid>
Newsgroups: pl.comp.programming
Subject: Re: Co robi permuted congruential generator XSL-RR-RR? =?UTF-8?B?UHLDs2J1asSZIHpyb3p1bWllxIc=?= scheamt =?UTF-8?B?ZHppYcWCYW5p?= =?UTF-8?B?YS4=?=
Date: Sat, 2 Jan 2021 17:15:07 +0100
Organization: . . .
Lines: 86
Message-ID: <20210102171507.40aeb31a@mateusz>
References: <2149118b-1cf9-4f45-b6a3-7b59a60446c4n@googlegroups.com> <20210102144507.535f1472@mateusz> <04697c4a-729b-4051-a3a0-346ded2aecd7n@googlegroups.com> <fbd46930-f562-4199-9336-cc021c363e4en@googlegroups.com> <20210102154922.59e6c404@mateusz> <41a2bd58-3ee9-4872-a80f-3aacb1e7d2c7n@googlegroups.com>
NNTP-Posting-Host: nyPK7k8oeDafdNpooDsxZQ.user.gioia.aioe.org
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
X-Complaints-To: abuse@aioe.org
X-Notice: Filtered by postfilter v. 0.9.2
X-Newsreader: Claws Mail 3.17.8 (GTK+ 2.24.32; x86_64-suse-linux-gnu)
Xref: csiph.com pl.comp.programming:34275

2021-01-02 o 07:25 -0800, osobli...@gmail.com napisa=C5=82:
> Mo=C5=BCe napisz=C4=99 jak ja to rozumiem na ch=C5=82opski rozum.
>=20
> 1. count =3D (int)(x >> 122)
>=20
> We=C5=BA jak=C4=85=C5=9B 128-bitow=C4=85 liczb=C4=99 startow=C4=85 X i zr=
=C3=B3b right shift o 122
> miejsca. 6 najbardziej znacz=C4=85cych bit=C3=B3w trafia w miejsce najmni=
ej
> znacz=C4=85cych i wychodzi nam jaka=C5=9B ma=C5=82a 6-bitowa liczba.

Zgadza si=C4=99. I tutaj, zak=C5=82adaj=C4=85c, =C5=BCe count zosta=C5=82o =
wcze=C5=9Bniej zdefiniowane
jako int, kompilator mo=C5=BCe si=C4=99 poskar=C5=BCy=C4=87 "uwa=C5=BCaj, b=
o pr=C3=B3bujesz przypisa=C4=87
zmienn=C4=85 128-bitow=C4=85 (x) do zmiennej o mniejszej szeroko=C5=9Bci (c=
ount)".
Dlatego programista wykonuje cast wyniku do (int), aby powiedzie=C4=87
kompilatorowi "spokojnie, wiem co robi=C4=99, to naprawd=C4=99 ma by=C4=87 =
int".

> Swoj=C4=85 drog=C4=85 dlaczego autor wymy=C5=9Bli=C5=82 tego shifta akura=
t o 122 bity
> (by=C4=87 mo=C5=BCe z jakich=C5=9B powod=C3=B3w daje najlepsze wyniki)?

To ju=C5=BC nale=C5=BCa=C5=82oby jego zapyta=C4=87. Ew. poczyta=C4=87 publi=
kacje dot. tego
algorytmu.

> 2. low64 =3D rotr64((uint64_t)(x ^ (x >> 64)), count)
>=20
> Oblicz pierwsz=C4=85 po=C5=82=C3=B3wk=C4=99 jako low64. Najpierw policz X=
 XOR X >> 64.
> Wychodzi mi tu 128-bitowa liczba, ale rozumiem, =C5=BCe uint64_t zaw=C4=
=99=C5=BCa j=C4=85
> tylko do 64 najmniej znacz=C4=85cych bit=C3=B3w?

Tak. 64 najbardziej znacz=C4=85ce bity zostaj=C4=85 usuni=C4=99te, za spraw=
=C4=85 castu
(castingu? nie mam pewno=C5=9Bci jak to si=C4=99 m=C3=B3wi po polskiemu) do=
 uint64_t.

> Teraz liczymy na niej rotr64 z przesuni=C4=99ciem o count.

Warto tu zaznaczy=C4=87, =C5=BCe rotr64 to nie C. Po nazwie mog=C4=99 tylko
przypuszcza=C4=87, co robi, ale dla pe=C5=82nej jasno=C5=9Bci nale=C5=BCa=
=C5=82oby doczyta=C4=87
dokumentacj=C4=99 danej implementacji.

> 3. high64 =3D rotr((uint64_t)(x >> 64), low64 & 63)
>=20
> Tu liczymy wy=C5=BCsz=C4=85 po=C5=82=C3=B3wk=C4=99. Tutaj otrzymujemy 64-=
bitow=C4=85 liczb=C4=99 poprzez
> X >> 64 i robimy na niej rotr. Nadal nie rozumiem dlaczego nie mo=C5=BCemy
> tu zrobi=C4=87 i zapisa=C4=87 r=C3=B3wnie=C5=BC rotr64?

Te=C5=BC nie wiem. Tym bardziej, =C5=BCe autor wyszczeg=C3=B3lni=C5=82 cast=
 do uint64_t, a
prototyp rotr() kt=C3=B3ry podaje mi google wskazuje =C5=BCe rotr() oczekuje
inta. Nie mam pewno=C5=9Bci, co autor mia=C5=82 na my=C5=9Bli, ale wygl=C4=
=85da mi to na
pomy=C5=82k=C4=99.

> >> Gdyby X by=C5=82o powiedzmy liczb=C4=85 84 bitow=C4=85, to
> >> 64 zrobi z niej liczb=C4=99 20-bitow=C4=85. Czyli wtedy nie mo=C5=BCem=
y zrobi=C4=87
> >> rotr64 (bo nie mamy 64 bit=C3=B3w)? A w=C5=82a=C5=9Bciwie mo=C5=BCemy,=
 ale otrzymamy
> >> inny wynik, ni=C5=BC rotr na liczbie 20-bitowej. Jedynie takie widz=C4=
=99 tu
> >> uzasadnienie.

Na platformie, na kt=C3=B3rej sizeof(int) =3D=3D 8, wynik b=C4=99dzie ident=
yczny w
obu przypadkach.

> 4. return (uint128_t)high64 << 64 | low64
>=20
> Tutaj rozumiem, =C5=BCe robimy shift na high64 i doklejamy do tego low64?
> low64 to b=C4=99d=C4=85 bity najmniej znacz=C4=85ce.

Tak. A cast do uint128_t jest tutaj konieczny, bo bez niego high64
by si=C4=99 po prostu wyzerowa=C5=82 (wyshiftowa=C5=82).

Mateusz