játékfejlesztés.hu
FórumGarázsprojectekCikkekSegédletekJf.hu versenyekKapcsolatokEgyebek
Legaktívabb fórumozók:
Asylum:    5440
FZoli:    4892
Kuz:    4455
gaborlabor:    4449
kicsy:    4304
TPG:    3402
monostoria:    3284
DMG:    3172
HomeGnome:    2919
Matzi:    2519

Pretender:    2498
szeki:    2440
Seeting:    2306
Geri:    2185
Orphy:    1893
Joga:    1791
Bacce:    1783
MaNiAc:    1735
ddbwo:    1625
syam:    1491
Gaborious - Tag | 50 hsz       Online status #103123   2009.01.21 14:00 GMT+1 óra  
Most kedvedért lemértem hogy 32bit használata jelen esetben kemény +10-15% tempót eredményezett.

Sztem ezek a dolgok itt mind részben fordító és cpu függők is, jelen esetben az én környezetemben core2duo és MSVC2008 as fordítóval sse2 optimalizációval ezeket produkálta.

Persze igazad is van, mert az a kódrész ami számomra eddig nagyon cpulimites volt 10-15% ot gyorsult 32 biten , míg más kódrész biztosan gyorsult +100% -t is akár, csak az ritkábban fut le...

Mérlegelés kérdése az egész, pro és kontra.
[Silent Vertigo] { Solarah }
SilentVertigo Honlap
   
Asylum - Törzstag | 5440 hsz       Online status #103106   2009.01.21 13:39 GMT+1 óra  
hashítás látom te is nyelvujto vagy
a 64 vs 32 bit nem ram kérdése...egy 32 bites procin a 64 bites int csak két regiszterben fér el, és haddnemondjam, hogy ez mennyivel lassitja a cuccot.
C++ fordítóval és macival alszom
http://darthasylum.blog.hu/
   
Gaborious - Tag | 50 hsz       Online status #103099   2009.01.21 13:32 GMT+1 óra  
http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
[url]http://en.literateprograms.org/Hash_function_comparison_(C,_sh)[/url]

Én is így tanultam... a piacon viszont vannak más elképzelések is.
Továbbá mindegyik hashító fv mindig más fajta előnyökkel hátrányokkal rendelkezik.
Egyik gyorsabb, másik jobban szór másik csak rövidekre hatékony, megint másik hosszú stringekre hatékony stb...

És bezony tök jó ha baromi gyorsan megvan egy keresett elem, még akkor is megéri ha ezért több ramot kell feláldozni, de manapság a ram sokkal olcsóbb mint a bika cpu.
[Silent Vertigo] { Solarah }
SilentVertigo Honlap
   
Asylum - Törzstag | 5440 hsz       Online status #103090   2009.01.21 13:15 GMT+1 óra  
az egy dolog hogy jó ha 1 lépésben megvan a keresett elem na de ennyire?
egyébként épp most ahogy kidogloztam a sziglroati tételeket került elö a hashelés is; azon belül a szrozómódszer ami valami ilyesmi

Kód:
0 < A < 1 rögzitett
h(k) = alsoegészrész(M * törtrész(k*A))

ahol k a kulcs amire a hash-t akarod kiszámolni
M pedig a hash lehetö legnagyobb értéke


Knuth szerint A = (gyök(5) - 1) / 2 -re a legjobb és egyenletesen szór.
C++ fordítóval és macival alszom
http://darthasylum.blog.hu/
   
Gaborious - Tag | 50 hsz       Online status #103087   2009.01.21 13:11 GMT+1 óra  
Részben azért választottam 64 bitet hogy minimalizáljam a hash érték ütközést, vagyis azonos hash értéket kapjak két eltérő string esetében.

Merthát a SDBMHash sem tökéletes és csinál ütközést, azáltal hogy 32 bitről 64 bitre váltottam, ezáltal az ütközés esélye nagyon a 0 hoz konvergál.
[Silent Vertigo] { Solarah }
SilentVertigo Honlap
   
Asylum - Törzstag | 5440 hsz       Online status #103057   2009.01.21 10:43 GMT+1 óra  
hát jó sok adatot tárolhatsz ha 64 bites hash kell hozzá
kis fejszámolás után ez 1.8 * 10^19 en féle adat, tegyük fel, hogy egy adat mondjuk átlagosan 4 bájt, igy az egész összesen (kapaszkodj)

Kód:
67108864 terabyte


szoljatok ha elszámoltam
32 bites inttel pedig 16 TB; szerintem ez reálisabb adattömeg, és 32 bites procikon joval gyorsabb 32 mint 64 bittel.

sztem ird meg 32 bitre is és a proci tipusának függvényében használd ezt v azt (akár #define makróként is).
C++ fordítóval és macival alszom
http://darthasylum.blog.hu/
   
TPG - Tag | 3402 hsz       Online status #103056   2009.01.21 10:31 GMT+1 óra  
Idézet
Gaborious :
Jelenlegi leggyorsabb megoldás (64bit):
Kód:
//SDBMHash
int64 GetHash(const string& key)
{
   const char* buf = key.c_str();
   unsigned int length = key.length();
   int64 hash = 0;

   for(unsigned int i = 0; i < length; i++)
   {
      hash = buf[i] + (hash << 6) + (hash << 16) - hash;
   }

   return (hash & 0x7FFFFFFFFFFFFFFF);

}

Nah ezen viszont már MMX-el se lehet segíteni, annak az ereje a packed arithmetic típusú utasításokban lenne, de itt erre nincs szükség mert most ezzel kb annyi műveletet végzel mintha MMX-el 64bites blokkokon dolgoznál úgy hogy azok több értéket tartalmaznak. A loop unroll-t azt ezen a kódon próbáltad? Mert ha nem akkor lehetne egy próbát tenni itt is.

Reality is almost always wrong. - House

   
Gaborious - Tag | 50 hsz       Online status #103055   2009.01.21 10:09 GMT+1 óra  
Hát sorry ez eléggé c++ os topic-ba illő dolog volt és piszkítom itt az asm talajt
[Silent Vertigo] { Solarah }
SilentVertigo Honlap
   
Gaborious - Tag | 50 hsz       Online status #103054   2009.01.21 10:06 GMT+1 óra  
Tehát summarum:
Eredeti kód:
Kód:
//SDBMHash
int64 GetHash(const string& key)
{
   
   int64 hash = 0;

   for(unsigned int i = 0; i < key.length(); i++)
   {
      hash = key[i] + (hash << 6) + (hash << 16) - hash;
   }

   return (hash & 0x7FFFFFFFFFFFFFFF);

}


tempo: 100%

MOD1

Kód:
const char* buf = key.c_str();
unsigned int length = key.length();


tempo: 154%

MOD2

Mod1 átírva
Kód:
+hash*65599


tempo: 144%

MOD3
Kipróbáltam a unrolled verziót és kiderült nem érte meg ...

tempo: 106%


Jelenlegi leggyorsabb megoldás (64bit):
Kód:
//SDBMHash
int64 GetHash(const string& key)
{
   const char* buf = key.c_str();
   unsigned int length = key.length();
   int64 hash = 0;

   for(unsigned int i = 0; i < length; i++)
   {
      hash = buf[i] + (hash << 6) + (hash << 16) - hash;
   }

   return (hash & 0x7FFFFFFFFFFFFFFF);

}
[Silent Vertigo] { Solarah }
SilentVertigo Honlap
   
sirpalee - Tag | 1282 hsz       Online status #103053   2009.01.21 08:53 GMT+1 óra  
Idézet
Asylum :
pont ezé kötöttem bele mert NEM volt bezárojelezve



Jah oks
raytraceisten és übermedic
   
Asylum - Törzstag | 5440 hsz       Online status #103052   2009.01.21 08:47 GMT+1 óra  
pont ezé kötöttem bele mert NEM volt bezárojelezve
C++ fordítóval és macival alszom
http://darthasylum.blog.hu/
   
sirpalee - Tag | 1282 hsz       Online status #103051   2009.01.21 08:40 GMT+1 óra  
Idézet
Asylum :
ezzel a

Kód:
*buf++


kódrészlettel vigyázz, mert nem elöre definiált, hogy melyik értékelődik ki elöbb (hasonloan a buff[i++] -nál sem.



Ha zárójelezed akkor igen .
raytraceisten és übermedic
   
TPG - Tag | 3402 hsz       Online status #103050   2009.01.21 08:32 GMT+1 óra  
Idézet
nadam :
Megtaláltam a hibát, i+4 helyett i+=4 kell.

Kód:
unsigned int GetHash(const string& key)
{
   const char* buf = key.c_str();
   unsigned int hash = 0;
   unsigned int length = key.length();
   unsigned int k = (length >> 2) << 2;
   for(unsigned int i = 0; i < k; i+=4)
   {
      hash = buf[i] + (hash << 6) + (hash << 16) - hash;
      hash = buf[i+1] + (hash << 6) + (hash << 16) - hash;
      hash = buf[i+2] + (hash << 6) + (hash << 16) - hash;
      hash = buf[i+3] + (hash << 6) + (hash << 16) - hash;
   }
   for(unsigned int i = k; i < length; i++)
   {
     hash = buf[i] + (hash << 6) + (hash << 16) - hash;
   }
   return hash;
}



És ha már ASM topic, a két ciklusmagot csodásan át lehetne írni MMX-esre. Mondjuk én inkább MMX intrinsic fv-kkel csinálnám meg mint konkrét ASM utasításokkal. A kérdés hogy itt mennyit lehetne ezzel nyerni, vagy lehet-e egyáltalán nyerni, ha jól emlékszem az MMX felélesztése nem olcsó mulatság, így ha a ciklusok túl kevésszer futnak le lehet hogy nem generálna a bennük lévő MMX-es kód annyi plusz ami kiütné az init költségeit.

Szerk: Nah ez mégse lesz olyan egyszerű, de megpróbálom MMX-esre átalakítani.

Ezt a hozzászólást TheProGamer módosította (2009.01.21 08:44 GMT+1 óra, ---)
Reality is almost always wrong. - House

   
Joga - Törzstag | 1791 hsz       Online status #103049   2009.01.21 08:29 GMT+1 óra  
Az határozza meg, hogy hol van a ++
buff[i++]
buff[++i]

Ha utána van, akkor előbb felhasználódik az érték, és csak utána nő egyel az értéke, ha előtte van, akkor egyel nő, majd a megnövelt érték használódik fel
Asszem...
(ಠ ›ಠ) Stewie!

   
Asylum - Törzstag | 5440 hsz       Online status #103048   2009.01.21 08:26 GMT+1 óra  
ezzel a

Kód:
*buf++


kódrészlettel vigyázz, mert nem elöre definiált, hogy melyik értékelődik ki elöbb (hasonloan a buff[i++] -nál sem.
C++ fordítóval és macival alszom
http://darthasylum.blog.hu/
   
nadam - Törzstag | 364 hsz       Online status #103047   2009.01.21 08:13 GMT+1 óra  
Megtaláltam a hibát, i+4 helyett i+=4 kell.

Kód:
unsigned int GetHash(const string& key)
{
   const char* buf = key.c_str();
   unsigned int hash = 0;
   unsigned int length = key.length();
   unsigned int k = (length >> 2) << 2;
   for(unsigned int i = 0; i < k; i+=4)
   {
      hash = buf[i] + (hash << 6) + (hash << 16) - hash;
      hash = buf[i+1] + (hash << 6) + (hash << 16) - hash;
      hash = buf[i+2] + (hash << 6) + (hash << 16) - hash;
      hash = buf[i+3] + (hash << 6) + (hash << 16) - hash;
   }
   for(unsigned int i = k; i < length; i++)
   {
     hash = buf[i] + (hash << 6) + (hash << 16) - hash;
   }
   return hash;
}
   
nadam - Törzstag | 364 hsz       Online status #103045   2009.01.21 08:01 GMT+1 óra  
Fura, nem látok benne végtelen ciklusra utaló hibát. Sajos nincs előttem C++ fordító, de majd este megnézem otthon.
   
Gaborious - Tag | 50 hsz       Online status #103044   2009.01.21 08:00 GMT+1 óra  
Egyszer majd kibogarászom mi lehet a gond, most már értem hogy menne az unrlling.
[Silent Vertigo] { Solarah }
SilentVertigo Honlap
   
Gaborious - Tag | 50 hsz       Online status #103043   2009.01.21 07:54 GMT+1 óra  
Az utóbbi unrolled kód futási ideje végtelen , vhol nagyon végtelen ciklusba ment érzésem szerint.
[Silent Vertigo] { Solarah }
SilentVertigo Honlap
   
Gaborious - Tag | 50 hsz       Online status #103041   2009.01.21 07:46 GMT+1 óra  
Találtam egy picivel gyorsabb megoldást, ámde határozottan csak stringekre jó:
Kód:
const char* buf = str.c_str();
int64 hash = 0;
while(*buf) hash=*buf++ + (hash<<6) + (hash<<16) - hash;


Ámde én ezen hash fv picit módosított verzióját pl nyers bináris adatokra is használom, így ez nem jó nekem, bár sima /0 ás stringekre sztem kiváló .
[Silent Vertigo] { Solarah }
SilentVertigo Honlap
   
nadam - Törzstag | 364 hsz       Online status #103039   2009.01.21 07:38 GMT+1 óra  
Szívesen. Esetleg megírhatod majd, hogy segített-e néhány százalékot az unrolling, mert én sem vagyok benne biztos, hogy segít, illetve nem tudom mennyit segít.
   
Gaborious - Tag | 50 hsz       Online status #103037   2009.01.21 07:34 GMT+1 óra  
A stringek általában 10-200 char vagy 100-100K s tartományban vannak.
A 10-200 as gyakoribb.


Köszi a kódot
[Silent Vertigo] { Solarah }
SilentVertigo Honlap
   
nadam - Törzstag | 364 hsz       Online status #103036   2009.01.21 07:22 GMT+1 óra  
Itt van pl. egy visznylag egyszerű loop unrolling megoldás. Remélem nem rontottam el, nem próbáltam ki. Elvileg minél nagyobb stringjeid vannak annál inkább segíthet, mert az overheadje annál inkább elenyészik a nyereségéhez képest. (mekkorák a stringjeid?)

Kód:
unsigned int GetHash(const string& key)
{
   const char* buf = key.c_str();
   unsigned int hash = 0;
   unsigned int length = key.length();
   unsigned int k = (length >> 2) << 2;
   for(unsigned int i = 0; i < k; i+4)
   {
      hash = buf[i] + (hash << 6) + (hash << 16) - hash;
      hash = buf[i+1] + (hash << 6) + (hash << 16) - hash;
      hash = buf[i+2] + (hash << 6) + (hash << 16) - hash;
      hash = buf[i+3] + (hash << 6) + (hash << 16) - hash;
   }
   for(unsigned int i = k; i < length; i++)
   {
     hash = buf[i] + (hash << 6) + (hash << 16) - hash;
   }
   return hash;
}
   
Gaborious - Tag | 50 hsz       Online status #103035   2009.01.21 07:21 GMT+1 óra  
kipróbáltam +-2 %. gyakorlatilag nem gyorsabb..

Loop unroling-al még nem igazán foglalkoztam tudatosan, hogyan kezdjek neki?
[Silent Vertigo] { Solarah }
SilentVertigo Honlap
   
nadam - Törzstag | 364 hsz       Online status #103033   2009.01.21 07:08 GMT+1 óra  
Esetleg ez segít egy-két százalékot? (nem az index mozog, hanem a pointer)

Kód:
unsigned int GetHash(const string& key)
{
   const char* buf = key.c_str();
   const char* bufend = buf + key.length();
   unsigned int hash = 0;
   for(;buf != bufend; buf++)
   {
      hash = *buf + (hash << 6) + (hash << 16) - hash;
   }
   return hash;
}


Igen, még meg lehet próbálni a loop unrollingot (főleg ha elég nagyok a stringjeid...)
   
Gaborious - Tag | 50 hsz       Online status #103032   2009.01.21 06:59 GMT+1 óra  
Kód:
const char* buf = key.c_str();
unsigned int length = key.length();


beiktatása a fv +54% kal lett gyorsabb

a
Kód:
+hash*65599
viszont kb 8% csökkenést produkált (wtf)

Köszi a segítséget... esetleg további opció lehetne a loop unrolling?
[Silent Vertigo] { Solarah }
SilentVertigo Honlap
   
nadam - Törzstag | 364 hsz       Online status #103031   2009.01.21 06:57 GMT+1 óra  
Közben utánanéztem a C++-os string-nek.
Az érintett függvények forrása:

Kód:
size_type size() const { return _M_finish - _M_start; }
size_type length() const { return size(); }

reference operator[](size_type __n)
    { return *(_M_start + __n); }


Ezek inline függvények, és elég gyorsak, így sajnos nem sokat lehet azzal optimalizálni, hogy a cikluson kívül előre lekéred a hosszt és a karaktertömböt.
(De azzal, hogy 32 bites procin 32bites intet fogsz használni 64 bites helyett, szerintem sokat fog gyorsulni a cucc. Meg talán a szorzásos trükk is segít minimálisat.)
   
Gaborious - Tag | 50 hsz       Online status #103030   2009.01.21 06:36 GMT+1 óra  
Oké, megpróbálom a c_str() -t

A stringből való leörököltetéses módszer nem hinném hogy segítene, mert a program működéséből adódóan. Ugyanis egy stringre többször nem igazán számolok hasht, így akárhogy nézzük a hasht egyszer ki kell számolni akárhogy csűrömcsavarom.
[Silent Vertigo] { Solarah }
SilentVertigo Honlap
   
nadam - Törzstag | 364 hsz       Online status #103029   2009.01.21 06:29 GMT+1 óra  
Gaborious:
Ismerni kellene a C++-os string megvalósítását, anélkül csak azt tudom mondani, hogy próbálj ki minél több változatot. (meg amúgy is)
Azért a c_str() - es megoldást, amit utoljára írtam próbáld ki. Nem ismerem a C++-os standard string megvalósítását, de ha véletlen függvényhívást csinál az elemelérésből, vagy neadjisten indexhatárokat ellenőriz akkor a c_str() - es megoldás jóval gyorsabb.

A Hash kódot én úgy cachelném, hogy lenne egy saját string osztályom 'MyString' amit pl. a 'string'-ből leörököltetsz, vagy esetleg csak memberként tartalmaz egy igazi 'string'-et. Ebben a MyString-ben kell egy 'unsigned int hash' member, amit 0-ra inicializálnék.

És egy ilyen member functionnel kérném tőle a hash-t:

Kód:
unsigned int getHash()
{
if(hash == 0) hash = calculateHash();
return hash;
}


Ezt hívtam cachelésnek, de asszem lusta elérésnek is hívják talán.
   
dothumour - Tag | 75 hsz       Online status #103027   2009.01.21 06:23 GMT+1 óra  
Idézet
nadam :
Miért 2^6 + 2^16 - 1 az nem 65599? Mit nézek el?


Semmit, én néztem el... << helyett >>-re gondoltam, bocsi.
٩(͡๏̯͡๏)۶

   
Gaborious - Tag | 50 hsz       Online status #103026   2009.01.21 06:18 GMT+1 óra  
Hogyan tudnám cachelni a hash kódot?

// Tényleg most esett le hogy csak 32bites az algo, de a cél a 64 bit volt valszeg elfelejtettem átírni azzá

@nadam
régebben én is próbálkoztam hasonló "gyorsításokkal" de elképedve láttam hogy pl a
profiler a korábbinál több időt jelzett ezen módosítások után
Így pl külön változóba kimenteni a string méretét vmiért "lassította" a dolgot...

Talán azt nem árultam el, hogy nem csak a cikluson belüli számítást kell gyorsítani mert az egy dolog... Maga a fv sokszor hívódik meg így talán hátrányos lehet ha minden fv híváskor kelleténél több változó jön létre.
[Silent Vertigo] { Solarah }
SilentVertigo Honlap
   
nadam - Törzstag | 364 hsz       Online status #103025   2009.01.21 06:06 GMT+1 óra  
Idézet
dothumour :
Bocs, nadam, de szerintem a szorzásos trükköd nem jó.
Egyébként a loop unrollolása (ez hogy van magyarul? A ciklus kifejtése/kibontása?) dobhat rajta sokat.



Miért 2^6 + 2^16 - 1 az nem 65599? Mit nézek el?

Igen, loop unrolling még dobhat rajta.

Szerk.:
Részletesen levezetve:

(hash << 6) + (hash << 16) - hash

= hash * 2^6 + hash * 2 ^ 16 - hash

=hash*(2^6 + 2^16 - 1)

=hash*65599

Ami nagyon régi procikon még nem biztos hogy gyorsabb volt, mert a shifelés annyival gyorsabb volt mint a szorzás, de egy mai procin asszem az integer mul is 1 órajel.

Ezt a hozzászólást nadam módosította (2009.01.21 06:21 GMT+1 óra, ---)
   
dothumour - Tag | 75 hsz       Online status #103024   2009.01.21 06:01 GMT+1 óra  
Bocs, nadam, de szerintem a szorzásos trükköd nem jó.
Egyébként a loop unrollolása (ez hogy van magyarul? A ciklus kifejtése/kibontása?) dobhat rajta sokat.
٩(͡๏̯͡๏)۶

   
nadam - Törzstag | 364 hsz       Online status #103023   2009.01.21 05:54 GMT+1 óra  
dothumour:
megelőztél, amit írtál az már elég optimálisnak tűnik. Talán a szorzásos trükköm hoz egy minimálisat rajta... (nameg érdemes cachelni a hash kódot)
(szvsz asm-ra átírni valamit csak akkor éri meg ha már végképp nincs más optimalizálni való , ami persze csak agyonoptimalizált kóddal esik meg. És szvsz ha átírjuk ASM-ra önmagában nemigen lesz gorsabb, leginkább tényleg csak akkor ha speciális utasításokat használunk, mint az MMX...)

Ezt a hozzászólást nadam módosította (2009.01.21 06:03 GMT+1 óra, ---)
   
nadam - Törzstag | 364 hsz       Online status #103022   2009.01.21 05:51 GMT+1 óra  
Gaborious:
Talán lehet rajta optimalizálni ASM nélkül is:
Így talán gyorsabb egy kicsit:

Kód:
int64 GetHash(const string& key)
{
   int64 hash = 0;
   unsigned int length = key.length();
   for(unsigned int i = 0; i < length; i++)
   {
      hash = key[i] + hash*65599;
   }
   return (hash & 0x7FFFFFFF);
}


32 bitesen biztos, hogy nem jó?
Pl. így:

Kód:
unsigned int GetHash(const string& key)
{
   unsigned int hash = 0;
   unsigned int length = key.length();
   for(unsigned int i = 0; i < length; i++)
   {
      hash = key[i] + hash*65599;
   }
   return hash;
}


Esetleg így még gyorsabb, ki kéne próbálni:

Kód:
unsigned int GetHash(const string& key)
{
   const char* buf = key.c_str();
   unsigned int hash = 0;
   unsigned int length = key.length();
   for(unsigned int i = 0; i < length; i++)
   {
      hash = buf[i] + hash*65599;
   }
   return hash;
}


+Ha lehet és van értelme, akkor cachelném a hash kódot: ha egy stringre egyszer kiszámoltam, akkor már ne kelljen mégegyszer.
   
dothumour - Tag | 75 hsz       Online status #103020   2009.01.21 05:45 GMT+1 óra  
Csak azért kérdezem, mert a 0x7FFFFFFF az 31 bitet enged át szóval 32 elégnek tűnik, teljesen biztos vagy benne, hogy 64-bit kell?

Rákerestem Google-n a "SDBMHash" kifejezésre és ezt az implementációt találtam, itt csak 32 bites...
Kód:
unsigned int SDBMHash(unsigned char *str, unsigned int len)
{
   unsigned int hash = 0;
   unsigned int i    = 0;

   for(i = 0; i < len; str++, i++)
   {
      hash = (*str) + (hash << 6) + (hash << 16) - hash;
   }

   return hash;
}
٩(͡๏̯͡๏)۶

   
Gaborious - Tag | 50 hsz       Online status #103019   2009.01.21 05:35 GMT+1 óra  
int64 kell , az int32 nem elég és preferálnám az mmx kódot (mivel az remélhetőleg gyorsabb)
[Silent Vertigo] { Solarah }
SilentVertigo Honlap
   
dothumour - Tag | 75 hsz       Online status #103018   2009.01.21 05:28 GMT+1 óra  
Gaborious: Biztos kell, hogy int64 legyen a hash? Sima x86 kód vagy MMX kód kell?
٩(͡๏̯͡๏)۶

   
Gaborious - Tag | 50 hsz       Online status #103009   2009.01.21 04:07 GMT+1 óra  
Tudna nekem vki segíteni? Egy kis c++ kódot kéne átültetni asm be ...

Kód:
//SDBMHash
int64 GetHash(const string& key)
{
   
   int64 hash = 0;

   for(unsigned int i = 0; i < key.length(); i++)
   {
      hash = key[i] + (hash << 6) + (hash << 16) - hash;
   }

   return (hash & 0x7FFFFFFF);

}


igazándiból a sebesség miatt kéne átírni asm be...

Előre is köszönöm a segítséget.
[Silent Vertigo] { Solarah }
SilentVertigo Honlap
   
HCodename47 - Törzstag | 231 hsz       Online status #98276   2008.11.03 08:15 GMT+1 óra  
Angolul van, mégis jobban értem, mint a tanár hablatyát! THX!
Maximális tisztelettel: Codename47

-Desktop PC: Intel i5 2.8 Ghz, 8Gb DDR3, ATi HD 5770 (W7 SP1 x64)
-Laptop: Acer Aspire 5112 - AMD Turio64 x2 1.6 Ghz, 3Gb DDR2, ATi Mobility Radeon X1600 (XP SP3 x86)
http://codename47.bayi.hu
   
Asylum - Törzstag | 5440 hsz       Online status #98265   2008.11.03 07:52 GMT+1 óra  
http://www.jegerlehner.ch/intel/IntelCodeTable.pdf

mindenre ottvan, hogy hogyan számolja.
C++ fordítóval és macival alszom
http://darthasylum.blog.hu/
   
HCodename47 - Törzstag | 231 hsz       Online status #98224   2008.11.03 00:08 GMT+1 óra  
Üdv,

Igen, így ahogy van volt fenn egy fórumon. És nekem is ez a fő bajom vele, hogy 2 regiszter kellene hozzá... meg hogy én baromira nem tudok ilyen kis lépésekben gondolkodni, mint az asm
Maximális tisztelettel: Codename47

-Desktop PC: Intel i5 2.8 Ghz, 8Gb DDR3, ATi HD 5770 (W7 SP1 x64)
-Laptop: Acer Aspire 5112 - AMD Turio64 x2 1.6 Ghz, 3Gb DDR2, ATi Mobility Radeon X1600 (XP SP3 x86)
http://codename47.bayi.hu
   
Asylum - Törzstag | 5440 hsz       Online status #98218   2008.11.02 17:35 GMT+1 óra  
az a vicc ebben, hogy az x86 regiszterei 4 bájtosak, tehát a quadwordhöz két regisztert is fel kell használni.

a gyökvonásos kódot igy asm kódként vadásztad? mert akkor itt van c++ -ban (érthetöbb)

Kód:
float mysqrt(const float in)
{
    float r = in / 2.0f;

    for( int i = 0; i < PRECISION; i++ )
        r = (r + (in / r)) / 2.0f;

    return r;
}


egyébként babiloni módszernek hivják.
ha esetleg a regiszterek nem lennének elegek, akkor ott a stack.
C++ fordítóval és macival alszom
http://darthasylum.blog.hu/
   
HCodename47 - Törzstag | 231 hsz       Online status #98129   2008.11.02 10:05 GMT+1 óra  
Üdv!

Egy kis segítségre lenne szükségem a hozzáértőbbektől. Beadandó feladatnak kaptunk Assembly programozás órán, hogy vonjunk gyököt a neptun kódunkból (aki nem tudja hogy az mi, mondok rá példát: B2QWMP). Ugyebár ebben vannak betűk, de az nem gond, mert ASCII kódként vannak tárolva. Netről vadásztam egy gyökvonásos kódot:

Kód:
TITLE  Negyzetgyokvonas elojel nelkuli egesz szambol
        .MODEL SMALL
        .386
;-------------------------------------------------------------------------
        .CODE                     ;Code szegmens
Sqrt_Dw PROC                      ;Az Sqrt_Dw procedura kezdete
        PUBLIC Sqrt_Dw
        CMP EAX,0                 ;megvizsgalja, hogy  n=0 teljesul-e
        JZ  vege                  ;ha igen, a futas veget er, ha nem, tovabbmegy
        CMP EAX,1                 ;megvizsgalja, hogy n=1 teljesul-e
        JZ  egy                   ;ha igen, az 'egy' kezdetu sorra ugrik, ha nem, tovabbmegy
        MOV EDI,0
        PUSH EBX
        PUSH ECX                  ;Regiszterek mentesenek vege
        MOV EDX,EAX               ;Az eredeti szamot atteszi EDX-be
        BSR ECX,EDX
        SHR CL,1
        MOV EAX,EDX
        SHR EDX,CL
mehet:  MOV ECX,EAX               ;az eredeti szam ECX-ben
        MOV EAX,EDX               ;EAX regiszterbe betesszuk az an-t
iter:   MOV EBX,EAX               ;a newton-algoritmus kezdete,an EBX-ben
        MOV EAX,ECX               ;az eredeti szam EAX-ban
        MOV EDX,0
        DIV EBX                   ;n osztva an-nel
        ADD EAX,EBX               ;(n/an)+an
        SHR EAX,1                 ;((n/an)+an)/2
        CMP EDI,1
        JNE nincs
        CMP EAX,ESI
        JE ki
        DEC EDI
        MOV ESI,EAX
        JMP nem
nincs:  INC EDI
nem:    CMP EAX,EBX               ;an es a(n+1) osszehasonlitasa
        JNE iter                  ;ha nem egyenlo, ujra fut a ciklus
ki:     MOV EAX,ECX               ;eredeti szam EAX-ba
        MOV EDX,0                 ;EDX nullazasa
        DIV EBX                   ;n mod an
        MOV EAX,EBX               ;an az EAX-ba
        POP ECX                   ;hivas elotti regiszterertekek vissza-
        POP EBX                   ;hozasa a stack-bol
        JMP vege                  ;A procedura vege
egy:    MOV DX,0                  ;ha n=1, x(mod n)=0
vege:   RET                       ;visszateres a hivo procedurahoz

Sqrt_Dw ENDP                      ;Az sqrt procedura vege
;
;****************************************************************************
;*          Sqrt_Dw procedura vege                                          *
;****************************************************************************
        END


De ez dupla szó méretű számból von gyököt, ami 4 bájt, a neptun kód viszont 6 karakter, tehát quadword kéne hozzá. Gondolom nem elég ha a DW-t átírom QW-re... Viszont nem igazán sikerült felfognom amit a tanár magyaráz, így egyedül nem megy a fenti kód átalakítása. Meg mintha hiányos is lenne ... Valaki, ha van egy kis szabadideje pls. segítsen! Előre is köszönöm!
Maximális tisztelettel: Codename47

-Desktop PC: Intel i5 2.8 Ghz, 8Gb DDR3, ATi HD 5770 (W7 SP1 x64)
-Laptop: Acer Aspire 5112 - AMD Turio64 x2 1.6 Ghz, 3Gb DDR2, ATi Mobility Radeon X1600 (XP SP3 x86)
http://codename47.bayi.hu
   
Geri - Törzstag | 2185 hsz       Online status #97146   2008.10.17 09:44 GMT+1 óra  
Megvan félmillió sor?

   
Asylum - Törzstag | 5440 hsz       Online status #97145   2008.10.17 09:39 GMT+1 óra  
de azért imádom, hogy igy látatlanban megmondanak rolam mindent (pl. hogy copyzom a kódokat), mintha csak itt ülne mellettem. A következö az lesz, hogy az enginemet se én irom, hanem a szomszéd Magdi néni...ja bocsánat hiszen az nem is engine...
C++ fordítóval és macival alszom
http://darthasylum.blog.hu/
   
Geri - Törzstag | 2185 hsz       Online status #97142   2008.10.17 07:33 GMT+1 óra  
Ne vitatkozz, én is elloptam a végtelentextúra technológiáját 1 évvel azelőtt, hogy kitalálta volna.

   
Asylum - Törzstag | 5440 hsz       Online status #97131   2008.10.16 16:35 GMT+1 óra  
már megbocsáss de magamtól írtam az egészet, a formális nyelvtantól kezdve (merthogy elöször azt kellett beadni, txt formában be is linkeltem valamikor). Egyébként meg honnan copyztam volna monddmérmeg amikor ez egy teljesen spciális nekünk kitalált feladat volt?....
C++ fordítóval és macival alszom
http://darthasylum.blog.hu/
   
newversion - Tag | 197 hsz       Online status #97130   2008.10.16 16:25 GMT+1 óra  
csak mértékkel vágjál fel azzal a koddal, mert te is tudod hogy nagyrészét copyztad
belenéztem a kodba
   
Geri - Törzstag | 2185 hsz       Online status #97122   2008.10.16 14:24 GMT+1 óra  
Nekem anno nagyon tetszett ez a cuccod, Asylum. Azt sajnálom, hogy nem c kompatibilisre írtad, sokra is vihette volna még ez a cucc sztem.