(gelöst) [C++] Bit-Stream

Design Patterns, Erklärungen zu Algorithmen, Optimierung, Softwarearchitektur
Forumsregeln
Wenn das Problem mit einer Programmiersprache direkt zusammenhängt, bitte HIER posten.
Antworten
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

(gelöst) [C++] Bit-Stream

Beitrag von Krishty »

Hi,

Ich brauche einen Stream, in den ich Elemente beliebiger Länge in Bits (von bool bis zu einfachen Klassen) eintragen und wieder auslesen kann (zwecks Kompression).

Bietet die Standardbibliothek Klassen, die ich dazu missbrauchen kann (aus std::vector<bool> ;) )? Oder empfehlt ihr selberschreiben?

Mir würden auch schon gute Artikel zum Thema reichen … ich dachte ja, dass es dazu im Internet haufenweise Material gäbe … aber dem ist leider nicht so …

Gruß, Ky
Zuletzt geändert von Krishty am 20.05.2009, 19:16, insgesamt 2-mal geändert.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Gelöschter Benutzer
Beiträge: 92
Registriert: 26.02.2009, 22:09

Re: [C++] Bit-Stream

Beitrag von Gelöschter Benutzer »

Meinst du jetzt einen virtuellen binären stream oder wie darf man das verstehen? Wenn ja mach dir doch einen vector<char> und packe dir dort in Bits alles rein:

Code: Alles auswählen

...
// Der virtuelle Datenstrom
vector<char> datastream;

// Reserviert eine Datengröße
void ReserveSize(size_t Bytes) datastream.reserve(Bytes); }

// Fügt Daten ein
template<typename T> void Assign(T data)
{
    char *tmpdata = new char[sizeof(T)];
    memcpy((void**)&tmpdata, data, sizeof(T));
    for(int i = 0; i < sizeof(T); i++)
        datastream.push_back(tmpdata[i]);
}

// Liest Daten aus dem Datenstream
template<typename T> const bool GetData(T *val, unsigned int position) const
{
    if(sizeof(T) + position > datastream.size()) return false;
    char *tmpdata = new char[sizeof(T)];
    for(int i = 0; i < sizeof(T); i++)
        tmpdata[i] = datastream[i+position];
    memcpy((void**)&val, tmpdata, sizeof(T));
    return true;
}

// Löscht den Stream
void ReleaseStream() { datastream.clear(); }
...
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Bit-Stream

Beitrag von Krishty »

Nein, ich meine einen Stream, den ich Bit für Bit auslesen kann … ungefähr so:

Code: Alles auswählen

bool SomeBool;
int SomeInt;
float SomeFloat;
Stream.LoadBits(&SomeBool, 1);
Stream.LoadBits(&SomeInt, 5);
Stream.LoadFloat(&SomeFloat, 32);
wobei die Daten im Stream so angeordnet wären:

Code: Alles auswählen

// B für die Daten der bool,
// I für int,
// F für float
BIIIIIFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFF__
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Bit-Stream

Beitrag von Krishty »

Habe mal selbst Hand angelegt und mein Prototyp funktioniert soweit – jetzt wurmt mich nurnoch die Endianess. Welche Funktionen bietet die Standardbibliothek zum Wecheln des Endians? ntohl() und htonl() soll man schonmal nicht benutzen …
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
dowhilefor
Moderator
Beiträge: 173
Registriert: 27.02.2009, 15:44
Alter Benutzername: 6SidedDice
Echter Name: Nico Probst
Wohnort: Bochum
Kontaktdaten:

Re: [C++] Bit-Stream

Beitrag von dowhilefor »

Welche Funktionen bietet die Standardbibliothek zum Wecheln des Endians? ntohl() und htonl() soll man schonmal nicht benutzen …
Dein Link hat doch schon die Lösung parat, nämlich hier.
Mein Gehirn besteht nur noch aus einem hash-index, ich weiss was ich kenn aber kenn nicht was ich weiss
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Bit-Stream

Beitrag von Krishty »

Ja, aber selber schreiben möchte ich solchen Code nicht, sonst hätte ich das längst getan … :)
Habe eben eine ansprechende Lösung gefunden, mit Intrinsics für Visual C++ und builtins für GCC. Die werden noch schnell gewrappt und fertig ist die optimale Lösung.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Helmut
Establishment
Beiträge: 237
Registriert: 11.07.2002, 15:49
Wohnort: Bonn
Kontaktdaten:

Re: [C++] Bit-Stream

Beitrag von Helmut »

Basiert deine Streamklasse eigentlich auf virtuals oder templates? Falls ersteres würde ich den Performanceverlust durch virtuals+Bitshiferei nicht vernachlässigen. Habe sowas schon mal gemacht..:)
Inzwischen würd ich das mit Templates wie die Boost Serialization] API machen.. Ev. kann man die sogar direkt auf Bitstreams erweitern, dürfte nicht so schwer sein.

Ansonsten kannst du zum Thema Bitstreams auch in Raknet reinschnuppern, aber das weißte wahrscheinlich schon:)

Ciao
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Bit-Stream

Beitrag von Krishty »

Helmut hat geschrieben:Basiert deine Streamklasse eigentlich auf virtuals oder templates?
Weder noch … ich wüsste auch nicht, warum, ich brauche ja nicht mehr als eine Funktion, die eine bestimmte Anzahl Bits ab einer bestimmten Adresse kopiert (bzw. davon eine zum Lesen und eine zum Schreiben) … C-Niveau eigentlich …

Boost und Raknet kommen gerade recht, jetzt wo mein Stream läuft ;) Mit Serialisierung habe ich nichts zu tun, aber in Raknets Packaging könnte ich mal reinschnuppern. Nach Kompression wäre das eigentlich das nächste Fachgebiet, von dem ich dachte, dass es dort zum Grundrepertoire gehören müsste.

Edit: Hmm, auch Boost bietet nur die Serialisierung in Byte-Happen an, soweit ich das jetzt überflogen habe („Binary Objects“) …
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Helmut
Establishment
Beiträge: 237
Registriert: 11.07.2002, 15:49
Wohnort: Bonn
Kontaktdaten:

Re: [C++] Bit-Stream

Beitrag von Helmut »

Krishty hat geschrieben:Boost und Raknet kommen gerade recht, jetzt wo mein Stream läuft ;) Mit Serialisierung habe ich nichts zu tun, aber in Raknets Packaging könnte ich mal reinschnuppern. Nach Kompression wäre das eigentlich das nächste Fachgebiet, von dem ich dachte, dass es dort zum Grundrepertoire gehören müsste.
Hm? Raknet hat doch sowohl Bitstreams, als auch Kompression? Wenn du die Lib benutzt würd ich auch die Features nutzen:)

Und deine Streamklasse hat weder großartige Templates noch virtuals? Komisch, aber egal... brauchste net extra erklären:) Glaub ich bin heut nur etwas verwirrt:)

Ciao
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Bit-Stream

Beitrag von Krishty »

Helmut hat geschrieben:Hm? Raknet hat doch sowohl Bitstreams, als auch Kompression? Wenn du die Lib benutzt würd ich auch die Features nutzen:)
Ich benutze die Lib nicht, habe sie mir auch gerade zum ersten Mal angesehen, hätte sie aber sofort genutzt, wenn ich davon gehört hätte bevor mein eigener Entwurf fertig wurde :)
Helmut hat geschrieben:Und deine Streamklasse hat weder großartige Templates noch virtuals? Komisch, aber egal...
Ist das eine Anspielung auf mein Virtual-File-Mapping damals? :D
Helmut hat geschrieben:brauchste net extra erklären:) Glaub ich bin heut nur etwas verwirrt:)
Geht mir nicht anders, mir kommt es vor als könnte ich mich hier einfach nicht artikulieren – keiner versteht, was ich will, obwohl das doch eigentlich total trivial ist … :/
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Bit-Stream

Beitrag von Krishty »

Soo …

Der Stream hat sich jetzt auch unter Einsatzbedingungen bewiesen … dabei habe ich die Endians dann doch nicht benötigt. Zuvor habe ich noch alle nativen Typen und einigen Klassen überprüft und ein paar Tests drübergejagt, in denen je einige Millionen Zufallswerte von einem Bit bis 64 Bits Größe eingefügt und wieder extrahiert wurden.

Ich werde mich noch um ein paar Details kümmern und dann den Code hier verlinken … damit er Suchenden einen Einstieg bietet.

Edit: Bitte – Beispiel ganz unten.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Helmut
Establishment
Beiträge: 237
Registriert: 11.07.2002, 15:49
Wohnort: Bonn
Kontaktdaten:

Re: (gelöst) [C++] Bit-Stream

Beitrag von Helmut »

Gefällt mir:) Allerdings ist dir ja hoffentlich klar, dass dein Beispiel unten von der Bytereihenfolge abhängig ist? Little und Big endian würden also je unterschiedliche Daten generieren. Ich würde deshalb Funktionen a la:

Code: Alles auswählen

IInStream& ReadInRange(int& Integer, int Min, int Max /*exclusive*/)
{
	Integer = 0;
	ReadBits(&Integer, NeededBitsForRange(Max-Min));
	Integer += Min;
	assert(Integer>=Min && Integer<Max);
	return *this;
}
IOutStream& WriteInRange(int Integer, int Min, int Max /*exclusive*/)
{
	assert(Integer>=Min && Integer<Max);
	Integer -= Min;
	WriteBits(&Integer, NeededBitsForRange(Max-Min));
	return *this;
}
uint NeededBitsForRange(uint Possibilities)
{
	Possibilities--;
	uint NeededBits = 0;
	while(Possibilities != 0)//sieht langsam aus, ist es abe nicht:)
	{
		NeededBits++;
		Possibilities/=2;
	}
	return NeededBits;
}

anbieten. (ist little endian abhängig, lässt sich aber trivial big endian kompatibel machen:))

Ciao

ps: diese & Dinger sind irgendwie nervig..
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: (gelöst) [C++] Bit-Stream

Beitrag von Krishty »

Helmut hat geschrieben:Allerdings ist dir ja hoffentlich klar, dass dein Beispiel unten von der Bytereihenfolge abhängig ist? Little und Big endian würden also je unterschiedliche Daten generieren.
Ja, das ist ein enormes Problem – vor allem, wenn es darum geht, Klassen zu packen, deren Endianess sich nicht mal schnell umdrehen lässt … ich habe mir lange den Kopf darüber zerbrechen müssen und immernoch keine befriedigende Antwort parat … ich habe mich dann einfach mal an Schrompf in einem anderen Thread erinnert: 99% der Programme laufen ja eh nie auf anderen Systemen. Da alle zur Zeit verbreiteten Systeme Little-Endian einsetzen (und das Ganze auf die x64-Kompatibilität keinen Einfluss hat), lasse ich es einfach mal gut sein :/
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
NytroX
Establishment
Beiträge: 358
Registriert: 03.10.2003, 12:47

Re: (gelöst) [C++] Bit-Stream

Beitrag von NytroX »

Hi,

nochmal ne blöde Frage von mir...

warum soll man htonl() usw. nicht benutzen ?
Die Funktionen ändern die endianness immer auf big endian (network byte order) bzw. zurück. Wenn das aktuelle System aber schon big endian hat, dann tun sie logischerweise nichts.
Ist das nicht genau das, was man haben will ?
Warum sollte ich die endianness IMMER switchen wollen ?? Dann verstehen sich die Programme doch wieder nicht ?!

Code: Alles auswählen

host_LE (little endian)
 |
htonl() (konvertiert zu big endian, weil auf LE system)
 |
 |
network byte order (big endian)
 |
 |
nltoh() (macht nix, weil auf BE system)
 |
host_BE (big endian)
Und da es die Funktionen sowohl unter windows gibt als auch im POSIX standard, ist es unwahrscheinlich, dass es sie mal nicht auf der zeilplattform gibt...
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: (gelöst) [C++] Bit-Stream

Beitrag von Krishty »

NytroX hat geschrieben:warum soll man htonl() usw. nicht benutzen ?
Die Funktionen ändern die endianness immer auf big endian (network byte order) bzw. zurück. Wenn das aktuelle System aber schon big endian hat, dann tun sie logischerweise nichts.
Ist das nicht genau das, was man haben will ?
Warum sollte ich die endianness IMMER switchen wollen ?? Dann verstehen sich die Programme doch wieder nicht ?!
Das ist garkeine blöde Frage ... ich wollte garnicht immer konvertieren ... da muss zwischen zwei Situationen unterschieden werden: Zum einen, wenn die Daten eingelesen werden und zum anderen, wenn sie bitweise im Speicher liegen. Aber kurz: Little Endian ist immer zu bevorzugen.

Fangen wir mit dem Einlesen der Daten an ... es ist beabsichtigt, immer die niederwertigsten Bits zu schreiben, bei der Binärzahl 10111 wären die vier niederwertigsten 111. So kann man z.B. drei Bits eines unsigned longs, von dem man weiß, dass seine Werte im Bereich 0 ... 7 liegen, in den Stream packen indem man die Adresse der Variablen und die Zahl drei Bits angibt.
Da die Bitmasken ebenfalls als unsigned longs verarbeitet werden, landen in diesem Beispiel auch auf Big-Endian-Systemen die untersten drei Bits im Speicher.
Das große Problem ist nun aber, dass die Größe der Speicheradresse, die man übergibt, beliebig ist. shorts oder alles, was nicht die Wortgröße des Streams hat, wird falsch maskiert und geschrieben. Da auch Arrays übergeben werden können sollen, fällt ein bloßes Wechseln des Endians anhand der Größe hier aus ...

Dann geht es ans Speichern der Daten. Hier spielt die 64-Bit-Kompatibilität die ausschlaggebende Rolle, nicht die Netzwerkfähigkeit: 32-Bit-Systeme parsen den Stream in 32-Bit-Stücken, 64-Bit-Systeme in 64-Bit-Stücken. Würde ein 32-Bit-System die Daten im Big-Endian speichern und sie würden auf demselben System im 64-Bit-Modus geparst, würde der Stream unterschiedlich extrahiert.

Wenn ich da was durcheinanderwürfle, bitte sofort beschweren - das ist das erste Mal, dass ich mich mit Endianess rumschlagen muss und mir brummt noch der Schädel ... aber das ist mein momentaner Eindruck.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
NytroX
Establishment
Beiträge: 358
Registriert: 03.10.2003, 12:47

Re: (gelöst) [C++] Bit-Stream

Beitrag von NytroX »

32-Bit-Systeme parsen den Stream in 32-Bit-Stücken, 64-Bit-Systeme in 64-Bit-Stücken.
Oha, da hast du natürlich recht, deshalb gibts auch ein htonl() und htons(), um die verschieden großen datentypen zu codieren...

Tatsächlich gibts da anscheinend keine wirklich gute Lösung für, besonders wenn du das zeugs halt in nem bitstream hast...

Danke nochmal für die Erklärung :-)
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: (gelöst) [C++] Bit-Stream

Beitrag von Krishty »

Ich hatte einen ersten Entwurf, der auf einer per-Byte-Basis gearbeitet hat … damit wären solche Probleme nicht entstanden, allerdings lag die Performance durchgängig bei 30 bis 50% der derzeitigen Version mit der Wortbreite, weil die meisten Daten, die ich reinquetsche, irgendwo zwischen 8 und 24 Bits liegen und entsprechend viele Schleifendurchläufe brauchen.

Man kann diese Limitierung aber – theoretisch – umgehen, indem das typedef size_t Word; durch typedef unsigned char Word; ersetzt wird. Dann müsste wieder auf einer Endian-unabhängigen per-Byte-Basis gearbeitet werden … getestet habe ich es aber nicht.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: (gelöst) [C++] Bit-Stream

Beitrag von Krishty »

Ein Hinweis, falls tatsächlich jemand meinen Code benutzen sollte: Die Funktion Resize() war buggy. Der korrigierte Quelltext (Zeile 145) hier.

Das zeigt mal wieder, dass ::memcpy() totaler Müll ist … ich hätte an der Stelle wirklich einen ::std::vector nutzen sollen …
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Antworten