Seite 1 von 1
(gelöst) [C++] Bit-Stream
Verfasst: 18.05.2009, 21:32
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
Re: [C++] Bit-Stream
Verfasst: 18.05.2009, 22:10
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(); }
...
Re: [C++] Bit-Stream
Verfasst: 18.05.2009, 22:19
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__
Re: [C++] Bit-Stream
Verfasst: 19.05.2009, 17:39
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 …
Re: [C++] Bit-Stream
Verfasst: 19.05.2009, 18:53
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.
Re: [C++] Bit-Stream
Verfasst: 19.05.2009, 19:14
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.
Re: [C++] Bit-Stream
Verfasst: 19.05.2009, 20:54
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
Re: [C++] Bit-Stream
Verfasst: 19.05.2009, 21:55
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“) …
Re: [C++] Bit-Stream
Verfasst: 19.05.2009, 22:40
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
Re: [C++] Bit-Stream
Verfasst: 19.05.2009, 22:48
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 … :/
Re: [C++] Bit-Stream
Verfasst: 20.05.2009, 19:15
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.
Re: (gelöst) [C++] Bit-Stream
Verfasst: 21.05.2009, 18:53
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..
Re: (gelöst) [C++] Bit-Stream
Verfasst: 21.05.2009, 20:36
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 :/
Re: (gelöst) [C++] Bit-Stream
Verfasst: 22.05.2009, 08:59
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...
Re: (gelöst) [C++] Bit-Stream
Verfasst: 22.05.2009, 10:41
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.
Re: (gelöst) [C++] Bit-Stream
Verfasst: 24.05.2009, 12:26
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 :-)
Re: (gelöst) [C++] Bit-Stream
Verfasst: 24.05.2009, 17:34
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.
Re: (gelöst) [C++] Bit-Stream
Verfasst: 26.05.2009, 00:17
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 …