Prüfsumme berechnen



  • Hallo zusammen,

    ich arbeite gerade an einem netzwerk-lockstep-protokoll für ein spiel und brauche zur überprüfung, ob noch alles synchron ist eine checksumme, die aus dem gesamten Gamestate berechnet wird.

    Ich suche entweder ein möglichst einfaches Verfahren, dass ich auf die schnelle implementieren kann, oder eine fertige bibliothek (am besten header only).

    Ich stelle mir das so vor, dass ich erstmal funktionen hab um basistypen zu hashen und funktionen um 2 hashs miteinander zu kombinieren.
    Dann kann ich hierarschich alles auf basistypen zurückführen die gehasht werden und diese hashs werden zu einer gesamtprüfsumme zusammengerechnet.
    (Ich hab hier mal Hash und Prüfsumme gleichgesetzt).
    Ist uint64 sinnvoll als checksummendatentyp?

    Könnte dann so in der art aussehen:

    typedef unsigned long long uint64;
    uint64 hash(int i)
    {
       return 3*i; // oder einfach i? oder ne konstante dazu noch?
    }
    
    uint64 hash(char c)
    {
       return 5*c + 42;
    }
    
    //...
    
    uint64 hash(uint64 hash1, uint64 hash2)
    {
       return hash1 + hash2;
    }
    
    struct A
    {
       int i;
       char c;
    }
    
    uint64 hash(const A& a)
    {
        return hash(hash(a.i), hash(a.c));
    }
    //bei großen klassen könnt das ganz schön aufwändig werden
    

    So wies bisher ist ists vermutlich grottenschlecht^^ Wollt nur ma zeigen wie ichs mir bisher vorgestellt hab.
    Habt ihr ne Idee, wie das gut geht?

    Edit: Und wie hashe ich float/double? Mit reinterpret cast an die bytes gehen?
    Und um der Frage vorzubeugen: Ich bin mir bewusst, dass floating-point-arithmetik normalerweise nicht deterministisch ist. Es gibt aber tricks, wie mans deterministisch machen kann (habs noch nicht getestet, aber hab davon gelesen und werdes testen, sobald die checksumme bereit ist).



  • Ich würde es in diese Richtung umbiegen.

    typedef unsigned long long uint64;
    uint64 hash(uint64 i)
    {
       return 234324231*i; // ungerade Zahl mit vielen gesetzten und ungesetzten Bits
    }
    uint64 hash(int i)
    {
       return hash(uint64(i))
    }
    
    uint64 hash(char c)
    {
       return hash(uint64(c))
    }
    
    //...
    
    uint64 hashCombine(uint64 hash1, uint64 hash2)
    {
       return hash1 + hash(hash2);
    }
    
    struct A
    {
       int i;
       char c;
    }
    
    uint64 hash(const A& a)
    {
        return hashCombine(hash(a.i), hash(a.c));
    }
    //bei großen klassen könnt das ganz schön aufwändig werden
    

    Vielleicht geht was mit variadic templates, daß man direkt

    struct A
    {
       int i;
       char c;
       Foo f;
       Bar b;
       friend uint64 hash(const A& a)
       {
          return hash(i,c,f,b);//macht irgendwie return hashCombine(hash(i),hash(c,f,b)) 
       }
    }
    

    machen kann. Hat PI nicht neulich was ähnliches gebaut?

    Also recht einfach sollte es sein. Und auch gar nicht so schlecht. Vielleicht aber ein wenig langsam.

    Wenn stört, daß {0,0L,'\0',""} und {0,0L,NULL} typischerweise auf 0ULL abbilden, bzw auf den selben Hashwert, kann man abhelfen mit

    friend uint64 hash(const A& a)
    {
       return hash(i,c,f,b,17);//17 ist magic number für struct A
    }
    


  • Variardic templates unterstützt mein compiler (MSVC10) soweit ich weiß leider nicht.
    Aber ich könnte es ja auch für 1 bis ~10 argumente manuell überladen, wird aber etwas arbeit...

    Würde das für 4 Argumente dann so aussehen:

    template<class T, class U, class V, class W>
    uint64 hash(const T& t, const U& u, const V& v, const W& w)
    {
      return hashCombine(hashCombine(hashCombine(hash(t), hash(u)), v), w);
    }
    

    ?

    Oder vielleicht gestaffelt:

    template<class T, class U, class V>
    uint64 hash(const T& t, const U& u, const V& v)
    {
        return hashCombine(hash(t, u), v);
    }
    
    template<class T, class U, class V, class W>
    uint64 hash(const T& t, const U& u, const V& v, const W& w)
    {
        return hashCombine(hash(t,u, v), w);
    }
    

    Und wie mach ich das dann mit floats/doubles? Einfach mit reinterpret-cast das bytemuster in uint32/64 casten?



  • Q schrieb:

    Oder vielleicht gestaffelt:

    Haha, natürlich gestaffelt.

    Q schrieb:

    Und wie mach ich das dann mit floats/doubles? Einfach mit reinterpret-cast das bytemuster in uint32/64 casten?

    Nee, glaube nicht. Neulich war hier ein Thread über hash(double). Um eben doubles in eine unordered_map stopfen zu können. Dein Compiler hat doch bestimmt auch eine unordered_map und dann bestimmt auch hash(double) und den Quellcode schau mal an.

    ps: Ich würde mit class A anfangen, sonst ist nach 7 Parametern schon Ende Alphabet. Wobei Dein Compiler ja griechisch kann, und Du kannst nach α, β, γ ausweichen.



  • template<>
    	class hash<float>
    		: public unary_function<float, size_t>
    	{	// hash functor
    public:
    	typedef float _Kty;
    	typedef _Uint32t _Inttype;	// use first 32 bits
    
    	size_t operator()(const _Kty& _Keyval) const
    		{	// hash _Keyval to size_t value by pseudorandomizing transform
    		_Inttype _Bits = *(_Inttype *)&_Keyval;
    		return (hash<_Inttype>()(_Bits == 0x80000000 ? 0 : _Bits));
    		}
    	};
    
    template<>
    	class hash<double>
    		: public unary_function<double, size_t>
    	{	// hash functor
    public:
    	typedef double _Kty;
    	typedef _ULonglong _Inttype;	// use first 2*32 bits
    
    	size_t operator()(const _Kty& _Keyval) const
    		{	// hash _Keyval to size_t value by pseudorandomizing transform
    		_Inttype _Bits = *(_Inttype *)&_Keyval;
    		return (hash<_Inttype>()(
    			(_Bits & (_ULLONG_MAX >> 1)) == 0 ? 0 : _Bits));
    		}
    	};
    

    Sieht mir sehr nach einem reinterpret_cast aus (nur halt als C-Style)



  • Q schrieb:

    Sieht mir sehr nach einem reinterpret_cast aus (nur halt als C-Style)

    Und vielleicht ein Bißchen mehr.
    +0f == -0f //sozusagen.
    Also das Vorzeichenbit ist umnerheblich, wenn der Wert 0 ist. Ich meine, es gibt zwei Darstellungen für die 0 und beide sollten auf den gleichen Hashwert fallen. Vielleicht ist das das Gerechne, was über den reinterpret_cast da hinaushegt.



  • Q schrieb:

    Ich suche entweder ein möglichst einfaches Verfahren, dass ich auf die schnelle implementieren kann, oder eine fertige bibliothek (am besten header only).

    Vielleicht Boost.Functional/Hash? Wäre header-only und ist für viele Typen bereits implementiert. Gibts übrigens auch im TR1 deiner Standardbibliothek.



  • Habs jetzt so gemacht:

    #include <functional>
    typedef std::size_t checksumType;
    
    template<class T>
    inline checksumType checksum(T t)
    {
    	return std::hash<T>()(t);
    };
    
    //spezialisierung um kopie zu vermeiden
    template<>
    inline checksumType checksum(const std::string& s)
    {
    	return std::hash<std::string>()(s);
    }
    
    template<class T, class U>
    inline checksumType checksum(T t, U u)
    {
    	return t + checksum(u);
    };
    
    template<class T, class U, class V>
    inline checksumType checksum(T t, U u, V v)
    {
    	return checksum(t, u) + checksum(v);
    };
    
    template<class T, class U, class V, class W>
    inline checksumType checksum(T t, U u, V v, W w)
    {
    	return checksum(t, u, v) + checksum(w);
    };
    
    template<class T, class U, class V, class W, class X>
    inline checksumType checksum(T t, U u, V v, W w, X x)
    {
    	return checksum(t, u, v, w) + checksum(x);
    };
    
    template<class T, class U, class V, class W, class X, class Y>
    inline checksumType checksum(T t, U u, V v, W w, X x, Y y)
    {
    	return checksum(t, u, v, w, x) + checksum(y);
    };
    
    template<class T, class U, class V, class W, class X, class Y, class Z>
    inline checksumType checksum(T t, U u, V v, W w, X x, Y y, Z z)
    {
    	return checksum(t, u, v, w, x, y) + checksum(z);
    };
    

    Kompilieren tuts schonmal. Ich werd dann gleich mal testen, inwiefern es brauchbar ist^^
    Wenn noch wer Verbesserungsvorschläge hat - immer her damit bitte 🙂

    Am besten wäres noch type traits einzusetzen um primitive typen von anderen zu unterscheiden und dadurch zu bestimmen, ob man per referenz oder value übergibt.



  • und funktionen um 2 hashs miteinander zu kombinieren.

    Das widerspricht aber der Logik von Hash/Prüfsummen Algos.

    Das die Hash's Prüfsummen möglichst sicher und Kollisions-arm funktionieren, solltest du immer einen Hash/Prüfsumme über dein Ganzen zu hashenden Bereich machen.
    Im zweifelsfall lieber 2 Hashes pflegen, als 2 zu einem kombinieren.

    Hat man die daten nicht am stueck vorliegen, baut man meist Hash/Prüfsummen funktionen so, das man nen Hash vorgang startet (Salt zuweist), dann immer Binaere Blöcke zu added, und wenn man ist, wird der vorgang abgeschlossen, und man kann sich den hash/checksumme abholen.

    Die funktion um Binaere Blöcke zu adden kann man auch leicht templatisieren ....

    Es gibt zigtausend algos, fuer hashes / checksummen, und das nicht ohne Grund.
    Um einen geeigneten zu finden, sollt man mehr ueber die daten (Kollisionswahrscheinlichkeiten) und über die PerformanceAnforderungen wissen.
    Platform (welche schnellen operationen hab ich zur verfuegung ... etc) spielt auch ne wesentliche rolle manchmal 🙂

    Suchst du einen recht einfachen, aber performanten ... schau nach crc Algos (crc32 etc)
    Fuehrst du deinen Code auf einen Prozessor mit recht komplexen befehlssätzen aus (MMX/SSE/3DNow), werden dir andere, vom befehlssatz unterstuetzte Algos mehr (weniger kollisionswahrscheinlichkeiten etc) bei vergleichsweisse weniger Prozessorlast bieten

    Ciao ...



  • Nochmal zu den Anforderungen:

    Es soll 100 mal pro Sekunde der Hash des gesamten Gamestates berechnet werden (wenn das zu lange dauern sollte wärs auch kein Problem, das seltener zu tun).
    Kollisionen sind im Prinzip nicht schlimm, solange sie nicht über mehrere Sekunden hinweg stattfinden.
    Es geht nur dadrum, um zu überprüfen, ob die Daten noch synchron sind.

    Ich hatte vor, (zumindest erstmal) etwas möglichst einfaches zu nehmen.

    CRC werd ich mir mal angucken, aber ich vermute, dass das nicht mehr ganz so einfach ist.

    Was ist denn eigentlich so schlimm daran, 2 hash miteinander zu einem neuen zu kombinieren?



  • Q schrieb:

    Was ist denn eigentlich so schlimm daran, 2 hash miteinander zu einem neuen zu kombinieren?

    Es schränkt Dich auf bestimmte Hashverfahren ein, nämlich welche ohne weiteren Zustand außer dem bisherigen Hashwert. Ich schätze, CRC kann man damit noch hinkriegen. Aber man muß voll nachdenken.

    Und bei uns war unklar, was hash(uint64) machen soll. Hashen oder nur weiterleiten für den eigentlichen hasher, den hashCombine? Das wird bei RHBaums Trennung viel klarer.



  • struct A
    {
       int i;
       char c;
       Foo f;
       Bar b;
    }
    
    template<typename HashAlgo>
    void hash(HashAlgo& ha,A const& a){
       ha.put(a.i);
       ha.put(a.c);
       hash(ha,f);
       hash(ha,b);
    }
    int main(){
    ...
       CRC32 crc;//Morgen wird die Onkel Pauls Hash-Klasse für Benutzung der AES-Hardware 
    //hier mal ausprobiert
       crc.put(theSalt);
    
       //Ab hier keine Änderung nötig
       hash(crc,theA);
       for(...
          hash(crc,myVec[i]);
    


  • Hab jetzt eine CRC-Klasse gebastelt (Teile aus einer Klasse aus dem Internet übernommen und Teile selbst hinzugefügt).
    Sieht jetzt so aus:

    class Crc
    {
    public:
    	typedef unsigned long Type;
    
    	Crc(Type key);
    	~Crc();
    	Type Done();
    	friend Crc& operator<<(Crc& crc, char c);
    	friend Crc& operator<<(Crc& crc, unsigned char c);
    	friend Crc& operator<<(Crc& crc, bool b);
    	friend Crc& operator<<(Crc& crc, short s);
    	friend Crc& operator<<(Crc& crc, unsigned short s);
    	friend Crc& operator<<(Crc& crc, int i);
    	friend Crc& operator<<(Crc& crc, unsigned int i);
    	friend Crc& operator<<(Crc& crc, long long l);
    	friend Crc& operator<<(Crc& crc, unsigned long long l);
    	friend Crc& operator<<(Crc& crc, float f);
    	friend Crc& operator<<(Crc& crc, double d);
    	friend Crc& operator<<(Crc& crc, const std::string& s);
    private:
    	void PutByte(unsigned int byte);
    	class Table
    	{
    	public:
    		Table () : key_ (0) {}
    		void Init (Crc::Type key);
    		Crc::Type operator [] (unsigned i)
    		{
    			return table_ [i];
    		}
    	private:
    		Crc::Type table_ [256];
    		Crc::Type key_;
    	};
    private:
    	Table table_;
    	Type key_;	// really 33-bit key, counting implicit 1 top-bit
    	Type register_;
    
    	template<class T>
    	friend void Write(Crc& crc, T t);
    };
    
    Crc::Crc(Crc::Type key):
    key_ (key), register_ (0)
    {
    	table_.Init(key);
    }
    
    Crc::Type Crc::Done()
    {
    	Type tmp = register_;
    	register_ = 0;
    	return tmp;
    }
    
    void Crc::Table::Init (Crc::Type key)
    {
    	assert (key != 0);
    	if (key == key_)
    		return;
    	key_ = key;
    
    	// for all possible byte values
    	for (unsigned i = 0; i < 256; ++i)
    	{
    		Crc::Type reg = i << 24;
    		// for all bits in a byte
    		for (int j = 0; j < 8; ++j)
    		{
    			bool topBit = (reg & 0x80000000) != 0;
    			reg <<= 1;
    			if (topBit)
    				reg ^= key_;
    		}
    		table_ [i] = reg;
    	}
    }
    
    void Crc::PutByte (unsigned int byte)
    {
    	unsigned top = register_ >> 24;
    	top ^= byte;
    	register_ = (register_ << 8) ^ table_ [top];
    }
    
    template<class T>
    inline void Write(Crc& crc, T t)
    {
    	unsigned char * c = reinterpret_cast<unsigned char*>(&t);
    	for(int i = 0; i < sizeof(T); ++i)
    	{
    		crc.PutByte(c[i]);
    	}
    }
    
    Crc& operator<<(Crc& crc, bool b)
    {
    	crc.PutByte(static_cast<unsigned int>(b));
    	return crc;
    }
    
    //...
    
    //alle typen außer string, bool, char und unsigned char laufen nach dem muster ab:
    Crc& operator<<(Crc& crc, short s)
    {
        Write(crc, s);
        return crc;
    }
    

Log in to reply