Ú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
De jó fej vagy... Pont azt csinálnám, de ahhoz előbb tudni kéne, melyik algoritmusról is van szó! Pont ezt kérdezem.
Bocs, de ha így van, akkor miért is nem tökmindegy, hogy a Windows melyiket használja?
Science for fun...
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? És akkor senkit sem érdekel, mi van a Windowsban.
tr '[:lower:]' '[:upper:]' <<<locsemege
LOCSEMEGE
Pontosan ez a cél.
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.
De nem pont az a lényeg a rand-nál, hogy ne legyen ugyanaz az eredmény, akár ugyanazon a rendszeren két különböző futtatásnál? Vagy elszáll valamiért?
Ha jól veszem ki, itt az a cél, hogy ugyanarra a seed-re ugyanazt adja akármilyen rendszeren (felteszem valamiféle szinkron miatt).
Ehhez meg nyilván azonos algoritmus kell.
Science for fun...
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?
pszeudorandom. ha ugyanaz a seed, akkor ugyanazt a szamsort kell hogy adja. Kulso szemlelonek ez is random, nem tudja megkulonboztetni egy valodi random sorozattol.
Viszont ha valamit tesztelni akarsz, akkor elonyos, ha a seed-del pszeudo-random sorozatot tudsz kesziteni.
Ú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?
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).
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.
tr '[:lower:]' '[:upper:]' <<<locsemege
LOCSEMEGE
Az eredeti fejlesztőnek bármi megfelel(t), ő nem akart reprodukálni semmit.
Debian - The "What?!" starts not!
http://nyizsa.blogspot.com
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.
Rendben, így már világos. :)
tr '[:lower:]' '[:upper:]' <<<locsemege
LOCSEMEGE
É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)
Ez tény, nem véletlenül kezdtem úgy a topikot, hogy "Újabb hülye kérdés a részemről :-)"
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)
Nem. Az eredeti fejlesztő konkrétan arra épít, hogy nem az.
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.
Mennyit fizetsz érte? Ekkora faszság nem lesz olcsó, előre szólok.
Én ilyen elcseszett program portolásáért is vastagabban nyomnám meg a ceruzát :D
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)
Gondolod, nincs titkosítva? És ha nincs, azonnal evidencia a formátum?
tr '[:lower:]' '[:upper:]' <<<locsemege
LOCSEMEGE
A MS kompetenciáját ismerve arra tippelnék, hogy nincs tikosítva. Bár ki tudja, nyilván elméletileg lehetséges minden.
“The world runs on Excel spreadsheets.” (Dylan Beattie)
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?
Chaotic good. Lájkolom!
Vagy még azt se kell, mert például Park-Millerhez van kód a GitHub-on.
Science for fun...
Ja, csak a Windows nem azt használja, szóval...
https://xkcd.com/221/
stackoverlowzás helyett visszafejtettem volna gyorsan az orig win proggiból
Lássuk, Te hogy csinálnád ezt! HINT: az orig win proggiban nincs is benne, csupán csak egy CALL utasítás rá.
A konkrét implementációt a MSVC szállítja a cstdlib ill. random nevű függvénykönyvtárakban.
teszek egy töréspontot a call targetre, és feltárom a nyúlfarknyi rutin működését
Vagy a disassemblyt le lehet fordítani Linuxon és meg se kell fejteni. Bár ez súlyos megszegése lenne a licenszfeltételeknek.
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.
Ha windowsod van, az Eclipse CDT valahogy debuggol windowson is. FOSS program.
emellett semmi másra nem lesz szükség ;)
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)
Ez tök véletlenül jött szembe, de gondoltam megerősítem amit írtál:
https://rosettacode.org/wiki/Linear_congruential_generator
tl;dr
Egy-két mondatban leírnátok, hogy lehet ellopni egy bitcoin-t?