[MEGOLDVA] Milyen rand algoritmust használ a C++ Windows alatt?

Fórumok

Újabb hülye kérdés a részemről :-) Szóval, melyik pszeudo-random algoritmust használja a Windows alatt az MSVC-vel fordított C++ srand() / rand()?

Kicsit nyomoztam, az MS doksiban azt írták, hogy a Mersenne Twister egyik változata, az MT19937, de nem (ez alapján nem ugyanaz, legalábbis mingw-vel). A másik helyen meg azt olvastam, hogy C++11 óta a Park-Miller, de az sem. Sőt, nem is a Lehner LCG. Na de akkor melyik? Nem az, ami a Linux-os glibc beli, az biztos. Egyébként az is kérdés, van különbség Windows alatt a C-beli rand() és a C++-beli között? Mármint látszatra nem ugyanaz az implementációjuk, de ha C-ben és C++-ban is lefordítok egy minimál programot, akkor ugyanaz az eredményük. Létezik, hogy itt még a mingw is bekavarhat? Mármint a a mingw a Windows-os rand()-ot használja egyáltalán, vagy saját implementációja van abban a libstdc++-ban, amit behúz? Nem azonos a Linux-os glibc-vel, az tuti, de abban nem vagyok biztos, hogy az MSVC-fel fordítottal azonos-e egyáltalán.

Ha számít a fordító és a nyelv is, akkor pontosítok: az MSVC C++ fordító által, a "windows.h" fejléc behúzásakor elérhető srand() és rand() algoritmusa kellene. (Itt egyénként az sem világos, hogy ez a "random" fejlécet, avagy a "cstdlib" fejlécet húzza-e be, merthogy mindkettőben van egy rand(), és nem azonosak.)

És hogy miért kéne: a gondom az, hogy egy jelenlegi Windows-only megoldást próbálok cross-platformként reprodukálni, ami egy voxel világot generál. Sajnos az algoritmusa rand()-ot használ, így hiába ugyanaz a seed érték, Windows és Linux alatt tök más az eredmény, ami nem jó. Ezért akarom kicserélni Linux alatt az srand()-ot és rand()-ot pontosan ugyanarra az implementációra, amit a Windows használ, hogy hordozható legyen az eredmény. Remélem érhető.

Szerk: bakker, mekkora mázlim van, véletlenül belenyúltam a a tutiba az egyik stackoverflow oldal eldugott komment szekciójában! Nem a Lehner, nem is a Park-Miller, hanem egy 1958-as LCG variációt használ, konkrétan ezt:

static int random_seed;

void msvc_cpp_srand(int seed) {
    random_seed = seed;
}

int msvc_cpp_rand() {
    random_seed = (random_seed * 214013 + 2531011) & 0xFFFFFFFF;
    return (random_seed >> 16) & 0x7FFF;
}

Azt továbbra sem tudom, hogy a "windows.h" akkor most a cstdlib-et vagy a random-ot használja-e (illetve azt már tudom, hogy a mingw egyiket sem, külön állatfaj), de már nem is fontos, mivel megvan ez a két konkrét függvény :-)

----------------------------------------------------------------------------------------------------------------------
PONTOSÍTÁS

Szükségét látom tisztázni, mert sokakat félrevezetett (elsőre engem is), hogy az eredeti programban nincs véletlenszám generálás, sőt mi több, valódi véletlenszámokkal garantáltan működésképtelen lenne.

Amire valójában szüksége van, az egy megbízható, kiszámítható bitshuffler. Az, hogy az eredeti fejlesztő erre a rand()-ot használta, csak mert az épp akkor aktuális cstdlib-jében az egy bitshufflerként volt/van implementálva, na az a csillámfaszlámaság csimborasszója.

Hozzászólások

Miért nem implementálod a kódodban? Akkor biztosan ugyanaz lesz.

tr '[:lower:]' '[:upper:]' <<<locsemege
LOCSEMEGE

Az eredeti kód MSVC C++-ban íródott, de ezt nem tudom újrafordítani, mivel nekem csak mingw-m van. Ezért nem világos, hogy

- MSVC C által használt rand() (ami a libc-ben van implementálva)
- MSVC C++ által használt rand() (ami amennyiben a cstdlib-bet használja, akkor a libstdc++-ban van implementálva, de lehet, hogy a random beli mt19937, de azzal nem egyezik)
- mingw C által használt rand() (az vajon a windows-os libc belit hívja, vagy sajátja van a libgcc-ben?)
- mingw C++ által használt (ez szerintem ugyanaz, mint a mingw C)
- valamint a Linux alatti gcc rand() (ez a glibc-beli, egyik fentivel sem azonos)

Szóval adott a seed és a végeredmény, megvan az eredeti program, megvan a forrása is, és valahogy kéne egy olyan programot csinálnom, ami fut Windows alatt és Linux alatt is, és pontosan ugyanazt azt eredményt produkálja. Ez 99,9999999999%-ban meg van oldva, az egyetlen problémám, hogy saját rand()-ot kéne csinálnom hozzá, ami pontosan ugyanazt az algoritmust használja, mint az eredeti MSVC-vel fordított C++ kód (ami nincs benne implementálva, valahonan hívja). Ha a rand()-ot lecserélem egy tömbre konstans értékekkel, akkor remekül működik a programom, na de ez csak egyetlen seed-re jó így.

Azt nem lehet, hogy a windows-os és a linuxos programot is te adod a felhasználónak, amelyben a saját implementációjú pszeudo random függvény van?

Pontosan ez a cél.

És akkor senkit sem érdekel, mi van a Windowsban.

Dehogynem, mert az eredeti azt használta. Az eredetit nem én írtam, még csak lefordítani se tudom mingw-vel. Az meg végképp felejtős, hogy Linux alatt fordulna. Ezért kell újraimplementálnom.

A lényeg: ha az eredeti forrás nem MSVC-only és Windows-only lenne, akkor eleve neki sem álltam volna szívni az átírással. De az volt, ezért nekiálltam, viszont az alapvető követelmény, hogy az új hordozható kód is pontosan ugyanazt az eredményt adja ugyanarra a bemenetre, mint amit az eredeti adott. A konkrét srand() és rand() implementációjának ismeretében ez most már így van.

Evekkel ezelott, amikor Minecraftot upgrade-eltem egy letezo, elkezdett vilag alatt tobb dolog is tort. Ott egy (pszeudo)randomgeneralt terep van, ami egeszen addig nem letezik, amig meg nem kozelited az adott reszt (chunk-ot). Miutan ott a terepet tudod modositani, utana kenytelen elmenteni, hogy mit valtoztattal rajta. Viszont verziovaltaskor modosult valami, ezert a korabban mar legeneralt es mentett resz meg a "friss" kozt volt egy eles tores.

Gondolom az ilyen problemakat akarja elkerulni azzal, hogy azonos helyre azonos terepet general kulonbozo rendszereken. Igy eleg a seedet atvinni.

A strange game. The only winning move is not to play. How about a nice game of chess?

Úgy tudtam, minden ilyen algoritmus-pszeudo random, ami nem használ valami hardveres zajforrást mankónak és még ezek a szoftveres megoldások is elég megbízhatóak tudnak lenni és nehezen áll elő olyan helyzet, hogy ugyanazt a sorozatot lehet velük generálni. De akkor valami teszteléshez kéne valami gyengített megoldás?

nehezen áll elő olyan helyzet, hogy ugyanazt a sorozatot lehet velük generálni

Tévedés. Pont azért "pszeudo-random" a nevük, mert ugyarra a seedre garantáltan mindig ugyanazt a számsort adják. Ha különböző számsort adnak vissza ugyanarra a seed-re, akkor az valódi random (vagy legalábbis nem ismered az összes seed faktorát).

De akkor valami teszteléshez kéne valami gyengített megoldás?

Nem. Azért kell, mert az eredeti fejlesztő balfaszjancsi, aki a Windows-os rand()-ot használta, hogy egy seed alapján kigenerálja a voxelvilág koordinátáit. Hogy ez portolható lehessen, azaz hogy bármilyen rendszeren ugyanarra a seed-re ugyanaz a világ generálódjon, ahhoz ismerni kell a Windows rand() algoritmusát.

Azért mondom, hogy bafaszjancsi emiatt, mert a rand()-ot bármikor bármelyik rendszer bármelyik frissítés során szó nélkül lecserélheti, és akkor borulni fog az eredeti programja. Csak azért, mert amikor a programját írta, pszeudo-random volt, egyáltalán nem biztos, hogy a jövőben is az marad.

Neked követelmény a kompatibilitás, de az eredeti fejlestőnek lehet, hogy a valódi random is megfelel.

Igazából nem. Mármint a kódból tökéletesen egyértelmű, hogy szándékosan nem véletlengeneráláshoz használta, és hogy borulni fog az egész, ha nem az adott számsor jön ki egy bizonyos seed-re.

Szóval annyi esze volt az eredeti fejlesztőnek, hogy tudja, egy LCG vagy bitshuffling pontosan azt nyújtja, ami neki kell, és még azt is tudta, hogy a rand() egy ilyen a cstdlib-ben; de annyi esze már nem volt, hogy maga leimplementálja, ezért inkább meghívta a rand()-ot, amivel portolhatatlanná tette a kódját (arról nem is beszélve, hogy semmi garancia, Windows MSVC cstdlib alatt nem fogják lecserélni, mivel a specifikáció csak annyit mond rá, hogy "implementációfüggő"). Szóval csak a csodával határos, hogy az eredeti program még egyáltalán helyesen működik a legújabb Windows alatt is.

Érdekes amit írsz, de ez elég rétegigény megint, hogy bug-for-bug kompatibilis program kell valahová. Nem mindegy, ha random viselkedik egy program, akkor hogyan is várható el, hogy minden esetben ugyanazt az eredményt adja Windowson és Linuxon is? Mert akkor az nem random, de még csak nem is pszeudórandom, akkor az egy nagy szar, meg gányolás.

Egyébként meg ha csak ennyi a baj, hogy nincs MSVC-d, akkor telepítesz egyet virtuális gépbe. A Windows ingyenes, lemezkép letölthető szabadon a MS oldaláról, még csak aktiválnod sem muszáj, kulcs nélkül használható 30 napig, trükkökkel 180 napig is hosszabbítgatod. Értem egyébként, ez nálam is vallási probléma, ha nem muszáj, Windowst bottal sem piszkálok.

The world runs on Excel spreadsheets. (Dylan Beattie)

Érdekes amit írsz, de ez elég rétegigény megint, hogy bug-for-bug kompatibilis program kell valahová.

Ez tény, nem véletlenül kezdtem úgy a topikot, hogy "Újabb hülye kérdés a részemről :-)"

Nem mindegy, ha random viselkedik egy program, akkor hogyan is várható el, hogy minden esetben ugyanazt az eredményt adja

Téged is megvezetett az a tény, hogy a balfaszjancsi eredeti fejlesztő a rand() hívást használta. Semmi köze a randomhoz, semmi véletlen nincs az eredeti programban, mindössze egy kiszámítható bitshufflingra volt szüksége. A rand()-ot erre használni, csak mert az adott rendszeren az implementációja épp egy LCG, ami valójában egy bitshuffler, na ez az Undefined Behaviour iskolapéldája.

A felhasználás szemszögéből a random az random, teljesen mindegy, hogy mennyire ténylegesen random, vagy csak egy nagyon rossz implementáció (mint C64-en). A lényege, hogy a program futása ne legyen teljesen kiszámítható, legalábbis a felhasználó ne azt érezze, hogy minden futáskor azonos eredményt kap.

Egyébként van neked egy jobb programozási projektem. A Windows telemetriát kéne implementálnod multiplatformos alapon, hogy Linuxról, BSD-ken is lehessen a MS-ot bombázni kamu telemetriaadatokkal, azokat akár a kedvenc random algoritmusod alapján is generálhatod, tehát a kód-újrahasznosítás játszik. Persze elvárom, hogy agilisen írd, Rust-ban vagy JS-ben, és az AI-t is integráljad bele, mert anélkül már nem létezhet semmi.

Külön plusz pont, ha kamu SQLite adabázist is legyárt a Recall-hoz, benne kamu screenshotokkal, ami szintén mehet a MS-nak. Kicsit olyasmit képzelek el, mint a Seti/Folding projekt, tehát aki akarja, futtatja a háttérben, vagy a szerverén, hogy segíthessen.

A MS vezérnek kellenek a felhasználói adatok, segítsünk neki gyűjteni az információs szemetet. Ha azt eladja, abból kap egy új mackófelsőt, meg egy vastagabb keretes szemüveget, meg az AI-t is betaníthatja belőle. A jelenlegi évi 43 milcsi dollcsis fizetéséből még nem futja ilyen úri huncutságokra.

Szerk.: azért elvárnám, hogy ezt valami jobb randomságú algoritmussal vagy megoldással kódold le. Nem a szakmaiság miatt, hanem ha nem elég random az adat, amit gyárt, akkor a MS-nál tudják tömöríteni, itt meg az lenne a lényeg, hogy minél tömöríthetetlenebb, minél több információs szemét legyen. Bár ezt hash-eléssel is meg lehet oldani, rajtad áll, te döntesz a részletekben :D

The world runs on Excel spreadsheets. (Dylan Beattie)

A felhasználás szemszögéből a random az random

Nem. Az eredeti fejlesztő konkrétan arra épít, hogy nem az.

A lényege, hogy a program futása ne legyen teljesen kiszámítható

Nem. Mégegyszer leírom, a program futása tökéletesen kiszámítható, az, hogy ezt rand() hívással valósította meg, mert az kiszámítható (lévén pszeudo-random), az faszság, de neki működött. Garancia nincs, hogy máshol is jó lesz (nem is működik glibc-vel).

Direkt beleírtam a topiknyitóba is, NINCS véletlenszámgenerálás a kódban, akkor sem, ha a rand()-ot hív, ne tévesszen meg a függvény neve.

Egyébként van neked egy jobb programozási projektem.

Mennyit fizetsz érte? Ekkora faszság nem lesz olcsó, előre szólok.

Ja, értem. Akkor az meg, ha kiszámíthatóságot épített pszeudórandomból, az egy oltári csúnya gányolás, és nem újraimplementálni kell, hanem az eredeti fejlesztőt agyonvágni szívlapáttal.

A telemetriáért max. csak válveregetést kapsz, meg a jó érzés tölthet el, hogy a MS-nak segíthetsz, hiszen ők is szeretik a Linuxot meg az open-source-t, akkor az a minimium, hogy mi is visszafelé szeretjük őket. Gondoltam rá, hogy nekikezdek én. Végül is nem olyan nehéz. Kell egy virtuális gép, amiben Windows fut, és a hoston Wireshark-kal kifigyelni, hogy milyen host:port-ok irányában milyen adatokat küldözget, és azt utánozni. Szerintem valami zlib/infozip tömörítésű, egyszerű algoritmus, néhány API/termékkulcs konstanstansot vagy UUID-t küldözgetve, akár még shell scriptben is utánozható, hogy ezeket core utils-szal előállítsd, és netcat-tel küldözgesd elfelé.

Csak azért ajánlottam neked, mert annyira lelkesedsz a programozásért, akár még versenykiírás is lehet belőle. Ez arra is kell, hogy ha Windows normik váltanak, akkor legyenek elérhetők Linuxon a windowsos szutykaik. Már Windows watermark is létezik Linuxra, meg NTFS3 driver, VSCode, Visual Basic pótlék (Gambas), MS-SQL, powershell, .NET Core, Notepad++ pótlék (notepadqq), tűzfal (pl. gfuw). Már csak Registry, reklámok, Telemetria, Recall, aktív vírusirtó kell bele, meg esetleg egy opcionális lassító modul, hogy a Windows usereknek is eljöhessen a Linux desktop éve ©®.

The world runs on Excel spreadsheets. (Dylan Beattie)

Akkor az meg, ha kiszámíthatóságot épített pszeudórandomból, az egy oltári csúnya gányolás

Nem az. Eredetileg arra van.

Ha jol emlekszem, atombomba szimulaciokhoz hasznaltak pszeudorandomot, ami azert kenyelmes, mert ha a seedet eltarolod (nehany byte), ugyanazt a random sorozatot kapod meg, akarhanyszor futtatod, de megis felhasznalhato olyan helyekre, ahova matematikai celra random fuggveny kell (kiveve kripto).

A strange game. The only winning move is not to play. How about a nice game of chess?

stackoverlowzás helyett visszafejtettem volna gyorsan az orig win proggiból

Az orig win proggi disassembly-jében nincs benne ez a rutin, csak egy hívás rá (függvénykönyvtárból jön). Ehhez az MSVC cstdlib-jét kéne disassemblálni. Ha nem bukkanok rá a stackoverflow-n a válaszra, ez lett volna a következő lépés, az objdump csodákra képes és PE-t is eszik.
A törésponthoz meg egy wines debugger kellene, na olyanom sincs.

Igen, nagyon, ha kitudódik vagy tudják bizonyítani. Egyébként le se szarja senki, hacsak nem kezdi kb. az eredeti szoftverrel azonos néven árulni pénzért az alternatívát.

El ne hidd ám, hogy nagy cégeknél a cleanroom implementáció mindig annyira clean. Mert gondolod ott tisztelik a licencfeltételeket, és fair módon játszanak. Persze, aztán megébreszt minket a párnacihára kifolyt, kihűlt nyáltócsa, ébredés után. Közben meg az van, hogy széthekkeleik disassemblerrel meg debugerrel, Ghidra vagy hasonló, aztán mikor kész vannak, akkor visszafelé dolgoznak, írnak egy specifikációt, amit újra lekódolnak, de ezt csak a hivatalosság miatt, hogy később ne lehessen belekötni.

The world runs on Excel spreadsheets. (Dylan Beattie)