Der Teil des Gehirns, der für Byte Order zuständig ist

TyRoXx

... scheint vielen Programmierern zu fehlen. Sehr oft stößt man in Code auf die Annahme, dass die Zahldarstellung der CPU irgendwie relevant wäre beim Kodieren von Zahlen. Mich erstaunt das deswegen immer wieder, weil das verlustfreie Aufteilen von Zahlen in kleinere Zahlen so unglaublich einfach ist und trotzdem von erwachsenen Menschen meist nicht richtig verstanden wird. Das Prinzip wird doch schon in der Grundschule unterrichtet. Mehrstellige Zahlen müssen die Schüler dort in Einer, Zehner, Hunderter und Tausender zerlegen. Nichts anderes ist die Zerlegung in Bytes. Und die Byte Order legt einfach fest, ob zuerst die Einer oder zuerst die Tausender (bzw 256er) kommen.

(ein Artikel, der das Problem erklärt: The byte order fallacy)

Selbst bei relativ kompetenten Communitys wie Stack Overflow überwiegen unportable, umständliche Lösungen für dieses Non-Problem.

Eigentlich sollte es nur in seltenen Fällen im Kernel Space als eine der letzten Mikrooptimierungen überhaupt in Frage kommen die Bytes umzudrehen. Keine Ahnung wozu, aber ich kann mir ntohl dort ganz tief unten in einem Treiber vorstellen.

Man kann solche Funktionen in reinem C implementieren ohne etwas über den Prozessor zu wissen. Ganz nebenbei ist das sogar die kürzeste Variante. In C++ ist der Unterschied noch krasser, weil es Funktions-Templates gibt.

Mal ein Code-Beispiel zur Illustration:

#include <cstdint>
#include <ostream>
#include <stdexcept>
#include <array>
#include <climits>
#include <fstream>

#include <netinet/in.h>

struct Object
{
	std::uint32_t i;
};

template <class Integer>
void encode_big_endian_wrong(std::ostream &out, Integer value)
{
	switch (sizeof(value))
	{
	case 1: break;
	case 2: value = htons(value); break;
	case 4: value = htonl(value); break;
	default: throw std::invalid_argument("I am too stupid to support arbitrary integer sizes");
	}
	out.write(reinterpret_cast<char *>(&value), sizeof(value));
}

//value muss unsigned sein, weil bei negativen Werten das Shiften undefiniertes Verhalten hätte.
template <class Unsigned>
typename std::enable_if<std::is_unsigned<Unsigned>::value, void>::type
encode_big_endian_correct_impl(std::ostream &out, Unsigned value)
{
	//Der Puffer soll die Anzahl der Aufrufe von out.write verringern, damit das nicht langsamer
	//wird als die falsche Variante.
	std::array<unsigned char, sizeof(value)> buffer;
	for (std::size_t i = 0; i < buffer.size(); ++i)
	{
		buffer[i] = static_cast<unsigned char>(value >> ((buffer.size() - i - 1) * CHAR_BIT));
	}
	out.write(reinterpret_cast<char *>(buffer.data()), buffer.size());
}

template <class Integer>
void encode_big_endian_correct(std::ostream &out, Integer value)
{
	encode_big_endian_correct_impl(out, static_cast<typename std::make_unsigned<Integer>::type>(value));
}

int main()
{
	std::ofstream file("out.bin", std::ios::binary);
	if (!file)
	{
		return 1;
	}
	Object o;
	o.i = 0xAABB;
	encode_big_endian_correct(file, o.i);
	encode_big_endian_wrong(file, o.i);

	//Beide "funktionieren", aber nur eine Variante
	//ist portabel und funktioniert für alle Integer-Größen.
}

So ein Funktions-Template gehört, noch etwas verallgemeinert, in Boost und dann in die Standardbibliothek. Davon könnten anscheinend viele profitieren.

EDIT: Interessant ist vielleicht noch der Code, den der Compiler daraus jeweils macht. Die wesentlichen Stellen in GNU AMD64 (erzeugt mit g++ main.cpp -std=c++11 -S -O3 ):

; encode_big_endian_correct(file, o.i);
	leaq	16(%rsp), %rsi
	leaq	32(%rsp), %rdi
	movl	$4, %edx
	movb	$0, 16(%rsp)
	movb	$0, 17(%rsp)
	movb	$-86, 18(%rsp)
	movb	$-69, 19(%rsp)
	call	_ZNSo5writeEPKcl
	; encode_big_endian_wrong(file, o.i);
	leaq	12(%rsp), %rsi
	leaq	32(%rsp), %rdi
	movl	$4, %edx
	movl	$-1146486784, 12(%rsp)
	call	_ZNSo5writeEPKcl

Die unportable Variante mit htonl ist tatsächlich kürzer. GCC bekommt das Loop Unrolling und Inlining zwar hin. Die vier Bytes werden bei der portablen Variante jedoch einzeln gesetzt. Ich bin kein Experte, aber ich halte es für eine triviale Optimierung ein paar mov s zusammenzufügen. Dass das auf -O3 nicht gemacht wird, könnte man als Bug bezeichnen.
Der Compiler ist übrigens g++ (Ubuntu/Linaro 4.7.3-1ubuntu1) 4.7.3 .
Ich würde trotzdem die portable Variante nehmen, weil es bei IO nicht auf die paar CPU-Takte ankommt. Zudem ist es wahrscheinlich, dass zukünftige Compiler hier besser optimieren werden. Clang 3.2 erzeugt mit den gleichen Optionen wie GCC bei beiden Varianten bereits den gleichen Code.

cooky451

Das erzeugt allerdings deutlich langsameren Code als Shifts für 32-bit. Und dann gibt's da ja auch noch bswap.
Siehe auch http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3620.pdf
und https://groups.google.com/a/isocpp.org/forum/?fromgroups#!searchin/std-proposals/swap/std-proposals/9wioV_jxuZs/itFbN0_9LrcJ
und (hat sich nichts geändert) http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3646.pdf

Edit: Jetzt hast du den generierten Code eineditiert.

Ich würde trotzdem die portable Variante nehmen, weil es bei IO nicht auf die paar CPU-Takte ankommt.

Bei Netzwerk-Kram vermutlich nicht, aber bei anderen Dingen (z.B. Verschlüsselung/Hashing) kann das schon einen Unterschied machen. Wenn Clang allerdings überall das gleiche generiert, zeigt das zumindest die Richtung an. Aber wie sieht's eigentlich mit std::reverse aus?

Wenn man mit htons, htonl usw. nutzt, kann man damit dann auch ein unsigned long übers Netzwerk schicken und es wird garantiert korrekt ankommen?

Vorausgesetzt die Gegenseite ruft ntohs und nthol auf?

TyRoXx

cooky451 schrieb:

Das erzeugt allerdings deutlich langsameren Code als Shifts für 32-bit.

Meinst du x86? Warum sollte da etwas anderes generiert werden?

cooky451 schrieb:

Und dann gibt's da ja auch noch bswap.
Siehe auch http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3620.pdf
und https://groups.google.com/a/isocpp.org/forum/?fromgroups#!searchin/std-proposals/swap/std-proposals/9wioV_jxuZs/itFbN0_9LrcJ
und (hat sich nichts geändert) http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3646.pdf

cooky451 schrieb:

Aber wie sieht's eigentlich mit std::reverse aus?

Ich will gar keine Bytes tauschen. Niemand sollte das wollen, darum geht es hier doch.

gfhffgh schrieb:

Wenn man mit htons, htonl usw. nutzt, kann man damit dann auch ein unsigned long übers Netzwerk schicken und es wird garantiert korrekt ankommen?

Vorausgesetzt die Gegenseite ruft ntohs und nthol auf?

Nö, aber mit meiner portablen Lösung geht das problemlos.

knivil

1.) Was zur Hoelle ist dein Problem?
2.) Deine "korrekte" Loesung ist kacke. Kann man auch ohne Template machen, wenn gleich ein (unsigned) char* akzeptiert wird.
3.) Und wenn schon Templates, dann mit Spezialisierung fuer die einzelnen Typen.
4.) Dein Code ist nicht performant, da zu viele Speicherzugriffe. Arbeiten auf Registern ist erwuenscht.
5.) Keine Begruendung fuer "unportabel" geliefert.

Ich will gar keine Bytes tauschen. Niemand sollte das wollen, darum geht es hier doch.

Ach, und was machst du dann?

otze

1.) hat er geschrieben
2.) Das ist hässlich.
3.) Warum?
4.) Clang erzeugt den gleichen Code in beiden Varianten. Praxis schlägt Theorie.
5.) htonl gibts nicht im Standard.

TyRoXx schrieb:

Sehr oft stößt man in Code auf die Annahme, dass die Zahldarstellung der CPU irgendwie relevant wäre beim Kodieren von Zahlen.

Sehr oft ist sie auch richtig, weil fast keiner für mehrere (Betriebs)systeme programmiert.

Zunächst mal ist die Berechnung der "falschen" Funktion aus deinem Assembly komplett wegoptimiert. Du wirst feststellen, dass

movl    $-1146486784, 12(%rsp)

schlicht den bereits vorgeswappten Wert ins Register schiebt, bevor write aufgerufen wird (-1146486784 == 0xbbaa0000).

Ersetz mal

o.i = 0xAABB;

durch

#include <ctime>
#include <cstdlib>

...

std::srand(std::time(0));
o.i = std::rand();

und schau nochmal, was der Compiler ausspuckt. Relevanter Teil:

bswap   %ebx

...und jeder Code, der da auf nem x86 was anderes erzeugt, gehört von vorneherein in die Tonne.

Kellerautomat

Ich bleib bei reinterpret_cast fuer Serialisierung, danke trotzdem.

Tja schrieb:

TyRoXx schrieb:

Sehr oft stößt man in Code auf die Annahme, dass die Zahldarstellung der CPU irgendwie relevant wäre beim Kodieren von Zahlen.

Sehr oft ist sie auch richtig, weil fast keiner für mehrere (Betriebs)systeme programmiert.

Was die Annahme nicht richtiger macht bzw. völlig orthogonal dazu ist. Aber unabhängig davon: du schreibst also nur Wegwerfprogramme?

Guck dich doch mal um wieviel Code, der vor vielen Jahren geschrieben wurde, heute noch im Einsatz ist. Die verwendete Hardware und die verwendeten Systeme haben sich (zum Teil massiv) verändert, aber der Code läuft immer noch.

Selbst wenn du heute nur x86-Maschinen einsetzt, kann sich die Welt ganz schnell verändern. Ist es denn so undenkbar, dass dein Code plötzlich auf einer ganz anderen Geräteklasse laufen könnte, z.B. weil die verfügbare Rechenleistung sich dort stark erhöht hat?

Siehe Embedded-Systeme in den letzten Jahren. Dort läuft heute oft Code, der vor einiger Zeit noch großen Timesharing-Systemen und später den Workstations/PCs vorbehalten war.

knivil

1.) hat er geschrieben

Und ich verstehe es nicht, was problematisch sein soll.

2.) Das ist hässlich.

Die for-Schleife und Speicherzugriffe sind haesslich, weil unnoetig.

3.) Warum?

Damit man bswap16, bswap32 und bswap64 oder aehnliches einsetzen kann. Damit es eben nur fuer primitive Typen definiert ist und nicht fuer jede Klasse. Damit die Operation fuer Integer mit mehr Bit auf den mit weniger Bit aufbauen kann.

4.) Clang erzeugt den gleichen Code in beiden Varianten. Praxis schlägt Theorie.

Der Bockmist wurde schon geklaert.

5.) htonl gibts nicht im Standard.

Nicht alles triviale muss im Standard sein.

Noch als Anmerkung: Der "korrekte" Code funktioniert nur auf Little-Endian-Maschinen, ist also alles andere als portabel. Auf Big-Endian-Maschinen müssen ntohl etc. nichts machen. Mixed-Endian ist etwas aus der Mode gekommen, aber damit klappt das natürlich auch nicht. Ich glaube, es gibt auf ARM einen corner case mit packed structs, wo einem mixed-endian passieren kann, müsste das aber nachprüfen.

Ah, ich nehme das zurück. Habe mich da verlesen.

cooky451

TyRoXx schrieb:

Meinst du x86? Warum sollte da etwas anderes generiert werden?

Wegen bswap, und sogar shifts wären schneller.

TyRoXx schrieb:

Ich will gar keine Bytes tauschen. Niemand sollte das wollen, darum geht es hier doch.

Versteh ich nicht.. macht encode_big_endian_correct_impl nicht genau das, bytes tauschen?

TyRoXx schrieb:

//value muss unsigned sein, weil bei negativen Werten das Shiften undefiniertes Verhalten hätte.
template <class Unsigned>
typename std::enable_if<std::is_unsigned<Unsigned>::value, void>::type
encode_big_endian_correct_impl(std::ostream &out, Unsigned value)
{
	//Der Puffer soll die Anzahl der Aufrufe von out.write verringern, damit das nicht langsamer
	//wird als die falsche Variante.
	std::array<unsigned char, sizeof(value)> buffer;
	for (std::size_t i = 0; i < buffer.size(); ++i)
	{
		buffer[i] = static_cast<unsigned char>(value >> ((buffer.size() - i - 1) * CHAR_BIT));
	}
	out.write(reinterpret_cast<char *>(buffer.data()), buffer.size());
}

template <class Integer>
void encode_big_endian_correct(std::ostream &out, Integer value)
{
	encode_big_endian_correct_impl(out, static_cast<typename std::make_unsigned<Integer>::type>(value));
}

Wenn du schon das Maul so weit aufreisst, dann schreibe doch bitte richtigen Code. Deiner ist nämlich falsch.
1. Funktioniert nicht mit bool
2. Strict Aliasing wird verletzt, UB

template <class Integer,
          typename = typename std::enable_if<std::is_integral<Integer>::value>::type>
Integer hton2(Integer value)
{
  using unsigned_integer = typename std::make_unsigned<Integer>::type;
  unsigned_integer x(value);
  static_assert(CHAR_BIT == 8, "I'm too stupid, please use htons");
  unsigned char arr[sizeof(x)];
  for (std::size_t i=0; i<sizeof(x); ++i)
    arr[i] = (value>>(8*(sizeof(x) - 1 - i)))&0xFF;
  std::memcpy(static_cast<void*>(&x), arr, sizeof(x));
  return x;
}
char hton2(bool value) { return hton2(static_cast<char>(value)); }

template <class Integer>
void encode_big_endian_correct(std::ostream &out, Integer value)
{
  out.write(hton2(value), sizeof(value));
}

Was war nochmal dein Argument? hton sei unnötig!?

cooky451

punner schrieb:

2. Strict Aliasing wird verletzt, UB

Nö. Lies 3.10/10 noch mal genau.

TyRoXx

Ich habe das noch einmal für Werte aus std::rand gemacht. Zu meiner Überraschung können Compiler das nicht optimieren. Weder GCC noch Clang erkennt das Muster und generiert bswap . htonl wird aber durch bswap ersetzt.

Clang 3.2 generiert folgendes:

calll	rand
	movl	%eax, %ebx

	shrl	$24, %eax
	movb	%al, 296(%esp)
	movl	%ebx, %eax
	shrl	$16, %eax
	movb	%al, 297(%esp)
	movb	%bh, 298(%esp)
	movb	%bl, 299(%esp)
	leal	296(%esp), %eax
	movl	%eax, 4(%esp)
	movl	%edi, (%esp)
	movl	$4, 8(%esp)
	calll	_ZNSo5writeEPKci

	bswapl	%ebx
	movl	%ebx, 300(%esp)
	leal	300(%esp), %eax
	movl	%eax, 4(%esp)
	movl	%edi, (%esp)
	movl	$4, 8(%esp)
	calll	_ZNSo5writeEPKci

Wieder etwas gelernt. Hier sollte man dem Compiler dabei helfen optimalen Code zu generieren. Wenn htonl zur Verfügung steht, kann man es benutzen, um Premature Pessimization zu vermeiden. Die Variante mit der Schleife kann dann als Fallback dienen und kommt bei long long zum Einsatz. Wenn man ganz sicher weiß, dass die native Byte Order Big Endian ist, kann man die Schleife weglassen, um den Compiler nicht zu verwirren.

#include <cstdint>
#include <ostream>
#include <climits>
#include <fstream>
#include <cstdlib>

#define BIG_ENDIAN_HOST_DETECTED 0

#define HTONL_DETECTED 1
#include <netinet/in.h>

template <class T>
struct is_non_bool_integral : std::is_integral<T>
{
};

template <>
struct is_non_bool_integral<bool> : std::false_type
{
};

template <class Integer>
typename std::enable_if<is_non_bool_integral<typename std::decay<Integer>::type>::value, void>::type
encode_big_endian_compromise(std::ostream &out, Integer value)
{
	Integer buffer;
	switch (sizeof(value))
	{
#if HTONL_DETECTED
	case 2:
		buffer = htons(value);
		break;

	case 4:
		buffer = htonl(value);
		break;
#endif

	default:
		{
#if !BIG_ENDIAN_HOST_DETECTED
			typedef typename std::make_unsigned<Integer>::type Unsigned;
			Unsigned const shiftableValue = value;
			unsigned char * const digits = reinterpret_cast<unsigned char *>(&buffer);
			for (std::size_t i = 0; i < sizeof(buffer); ++i)
			{
				digits[i] = static_cast<unsigned char>(
				             shiftableValue >> ((sizeof(buffer) - i - 1) * CHAR_BIT)
				            );
			}
#endif
			break;
		}
	}
	out.write(reinterpret_cast<char *>(&buffer), sizeof(buffer));
}

int main()
{
	std::ofstream file("out.bin", std::ios::binary);
	if (!file)
	{
		return 1;
	}
	std::uint32_t const i = std::rand();
	encode_big_endian_compromise(file, i);
}

punner schrieb:

1. Funktioniert nicht mit bool

Soll es auch nicht.

Danke für die Antworten, die konstruktiv sind.

knivil

Danke für die Antworten, die konstruktiv sind.

Danke, dass du auf Kritikpunkte nicht eingegangen bist. Danke, dass dein Code noch komplexer geworden ist. Danke, fuer eine inperformante Loesung eines gut untersuchten und mittlerweile voellig trivialen Problems. Danke, dass es an streams gekoppelt ist. Danke, dass es nicht fuer Arrays funktioniert. Danke fuer all die Template-Magic und die Makros. Danke dafuer, dass du dir keine Anregungen long long z.B. hier geholt hast.

otze

kann jemand Zeile 120-133 Standardkonform und portabel aufschreiben? Dann hat ja knivil recht und der Thread kann geschlossen werden.

TyRoXx

cooky451 schrieb:

TyRoXx schrieb:

Ich will gar keine Bytes tauschen. Niemand sollte das wollen, darum geht es hier doch.

Versteh ich nicht.. macht encode_big_endian_correct_impl nicht genau das, bytes tauschen?

Nein, dann würde das Template swap oder so im Namen haben. Es soll nur Zahlen kodieren (High Level) und die konkrete Implementation auf der Plattform interessiert nicht (Low Level). Auf einer Big-Endian-Plattform würde nicht einmal etwas vertauscht werden.

Die "falsche" Variante besteht aus zwei Schritten: Zahl vorbereiten ( htonl ), vorbereitete Zahl als POD wegschreiben. (Im ersten Beispiel-Code habe ich die zwei Schritte zusammengefasst, aber typischerweise machen die Leute nicht einmal das.)
Die "richtige" ist nur ein Schritt: Zahl im richtigen Format wegschreiben.

Ob die zweite Variante mit htonl implementiert ist, interessiert dabei nicht. Die Kodierung ist genau ein mal in einem Header implementiert und kann idiotensicher benutzt werden. Der Anwender kommt nicht mit plattformabhängigen Funktionen wie htons in Berührung. Er profitiert aber trotzdem von den Optimierungen.

knivil schrieb:

Danke, dass du auf Kritikpunkte nicht eingegangen bist.

Worauf soll ich denn noch eingehen?

knivil schrieb:

Danke, dass dein Code noch komplexer geworden ist. [...]Danke, dass es an streams gekoppelt ist. Danke, dass es nicht fuer Arrays funktioniert. Danke fuer all die Template-Magic und die Makros.

Tut mir leid, dass du nicht mehr mitkommst. Irgendwo im Forum gibt es einen Thread mit guten Büchern über C++.

knivil schrieb:

Danke, fuer eine inperformante Loesung eines gut untersuchten und mittlerweile voellig trivialen Problems.

Hast du eigentlich mein letztes Programm verstanden? Was soll da noch performanter gehen, ich verwende doch schon htonl . Ich habe gemerkt, dass Compiler damit besser arbeiten können und meinen Code entsprechend angepasst.

knivil schrieb:

Danke dafuer, dass du dir keine Anregungen long long z.B. hier geholt hast.

Intrinsics für long long . Wow, High Tech. Das wäre jetzt voll wichtig gewesen für meine Argumentation. Reicht ja nicht, dass mein Programm schon für 16 und 32 Bit optimal ist und nur zur Demonstration des Prinzips dienen soll.

otze schrieb:

kann jemand Zeile 120-133 Standardkonform und portabel aufschreiben? Dann hat ja knivil recht und der Thread kann geschlossen werden.

Genau, schließt alle interessanten Diskussionen!

knivil

1.) Der union-Trick funktioniert auf allen mir bekannten Compilern/Architekturen (zugegeben, sind nicht viel). Vielleicht sollte der Standard diesbezueglich nachgeruestet werden.
2.) Zeile 100-108 sieht auch gut aus. Man kann gern noch etwas make unsigned rumspielen.