Parsing Optimierung: Erkennen von " \n\r\t" mit nur einer Abfrage

[Jodocus]

Sind Shifts um mehr als die Bitbreite des geshifteten Typs in C++ überhaupt definiert?

Ist wohl irgendwo zwischen undefined/implementation defined/unspecified:

http://blogs.msdn.com/b/vcblog/archive/2012/10/25/hello-arm-exploring-undefined-unspecified-and-implementation-defined-behavior-in-c.aspx

[hustbaer]

Danke.
D.h. der hier gezeigte Code funktioniert gar nicht.

[SeppJ]

hustbaer schrieb:

Danke.
D.h. der hier gezeigte Code funktioniert gar nicht.

Er funktioniert schon. Er verlässt sich nur auf allerlei Dinge, die in der Theorie undefiniert sind, aber in der Praxis dann in der Regel doch funktionieren (selbst bei eingeschalteten Compileroptimierungen). Zumindest bei derzeitigen Implementierungen auf derzeit üblicher Hardware. Ich habe im letzten Absatz der ersten Antwort schon was dazu geschrieben.

[hustbaer]

@SeppJ
Hast du das ausprobiert?
Denn laut dem Link von Jodocus sollte es wirklich nicht funktionieren.
Sowohl auf x86 als auch auf x64.

ps:
OK, hab's jetzt selbst ausprobiert.
Es funktioniert wie erwartet nicht:

unsigned int i = 1;
	for (unsigned int n = 0; n < 100; n++)
		std::cout << "1 << " << n << " = " << (i << n) << "\n";

=>

1 << 0 = 1
1 << 1 = 2
1 << 2 = 4
1 << 3 = 8
1 << 4 = 16
1 << 5 = 32
1 << 6 = 64
1 << 7 = 128
1 << 8 = 256
1 << 9 = 512
1 << 10 = 1024
1 << 11 = 2048
1 << 12 = 4096
1 << 13 = 8192
1 << 14 = 16384
1 << 15 = 32768
1 << 16 = 65536
1 << 17 = 131072
1 << 18 = 262144
1 << 19 = 524288
1 << 20 = 1048576
1 << 21 = 2097152
1 << 22 = 4194304
1 << 23 = 8388608
1 << 24 = 16777216
1 << 25 = 33554432
1 << 26 = 67108864
1 << 27 = 134217728
1 << 28 = 268435456
1 << 29 = 536870912
1 << 30 = 1073741824
1 << 31 = 2147483648
1 << 32 = 1
1 << 33 = 2
1 << 34 = 4
1 << 35 = 8
1 << 36 = 16
1 << 37 = 32
1 << 38 = 64
1 << 39 = 128
1 << 40 = 256
1 << 41 = 512
1 << 42 = 1024
1 << 43 = 2048
1 << 44 = 4096
1 << 45 = 8192
1 << 46 = 16384
1 << 47 = 32768
1 << 48 = 65536
1 << 49 = 131072
1 << 50 = 262144
1 << 51 = 524288
1 << 52 = 1048576
1 << 53 = 2097152
1 << 54 = 4194304
1 << 55 = 8388608
1 << 56 = 16777216
1 << 57 = 33554432
1 << 58 = 67108864
1 << 59 = 134217728
1 << 60 = 268435456
1 << 61 = 536870912
1 << 62 = 1073741824
1 << 63 = 2147483648
1 << 64 = 1
1 << 65 = 2
1 << 66 = 4
1 << 67 = 8
1 << 68 = 16
1 << 69 = 32
1 << 70 = 64
1 << 71 = 128
1 << 72 = 256
1 << 73 = 512
1 << 74 = 1024
1 << 75 = 2048
1 << 76 = 4096
1 << 77 = 8192
1 << 78 = 16384
1 << 79 = 32768
1 << 80 = 65536
1 << 81 = 131072
1 << 82 = 262144
1 << 83 = 524288
1 << 84 = 1048576
1 << 85 = 2097152
1 << 86 = 4194304
1 << 87 = 8388608
1 << 88 = 16777216
1 << 89 = 33554432
1 << 90 = 67108864
1 << 91 = 134217728
1 << 92 = 268435456
1 << 93 = 536870912
1 << 94 = 1073741824
1 << 95 = 2147483648
1 << 96 = 1
1 << 97 = 2
1 << 98 = 4
1 << 99 = 8

Soviel dazu

[SeppJ]

hustbaer schrieb:

@SeppJ
Hast du das ausprobiert?
Denn laut dem Link von Jodocus sollte es wirklich nicht funktionieren.
Sowohl auf x86 als auch auf x64.

Doch, es sollte funktionieren und funktioniert bei mir durchgaenig, mit verschiedenen Implementierungen.

ps:
OK, hab's jetzt selbst ausprobiert.
Es funktioniert wie erwartet nicht:

unsigned int i = 1;
	for (unsigned int n = 0; n < 100; n++)
		std::cout << "1 << " << n << " = " << (i << n) << "\n";

Und das hat was mit dem Originalcode zu tun? Du hast nur gezeigt, wie unsigned Integer unter Linksshift ueberlaufen. Eine Aktion, die im Originalcode genau 0 Mal vorkommt.

edit: Oder bezog sich das auf meinen Vorschlag, unsigned int statt long fuer die Rechnung zu nehmen? Deswegen habe ich doch auf einen Shift um (c-1) "verbessert".

[hustbaer]

OMFG dann halt mit signed long . Kommt genau das selbe raus.

Da, bitte: http://ideone.com/CF1Bfe

[SeppJ]

hustbaer schrieb:

OMFG dann halt mit signed long . Kommt genau das selbe raus.

Da, bitte: http://ideone.com/CF1Bfe

Somit wurde gezeigt, dass eine Implementierung, welche die hier stillschweigend angenommene Voraussetzung, dass sizeof(long) > 4 , verletzt, tatsaechlich nicht funktioniert. Oh, Wunder ! Wie in der ersten Antwort bereits festgestellt, ist es auch tatsaechlich keine gute Idee, solche Annahmen zu machen. Es bleibt aber der Fakt, dass es auf ueblichen Systemen, die diese Annahme erfuellen, tatsaechlich funktioniert. Denn die anderen stillschweigenden Annahmen (d.h. hauptsaechlich, dass der Rechtsshift so funktioniert, wie es hier erwartet wird) sind nicht sooooo exotisch.

[hustbaer]

Somit wurde gezeigt, dass eine Implementierung, welche die hier stillschweigend angenommene Voraussetzung, dass sizeof(long) > 4, verletzt, tatsaechlich nicht funktioniert

So ziemlich jedes System verletzt diese Annahme. Die einzige Ausnahme ist GCC auf 64 Bit Plattformen. Womit die Annahme nicht "durchaus derzeit auf üblicher Hardware und auf üblichen Plattformen berechtigt" ist.

Das char üblicherweise signed ist scheinen hier auch alle zu vergessen.

Und dann ist immer noch die Frage ob bei "zu weiten" Shifts bloss das Ergebnis implementation defined ist, oder ob der ganze Shift UB ist.
Wenn es UB ist, dann ist der Code sowieso falsch und darf auch auf 64 Bit long unsigned char Plattformen alles beliebige rauskommen sobald c >= 64.

[SeppJ]

hustbaer schrieb:

Somit wurde gezeigt, dass eine Implementierung, welche die hier stillschweigend angenommene Voraussetzung, dass sizeof(long) > 4, verletzt, tatsaechlich nicht funktioniert

So ziemlich jedes System verletzt diese Annahme. Die einzige Ausnahme ist GCC auf 64 Bit Plattformen. Womit die Annahme nicht "durchaus derzeit auf üblicher Hardware und auf üblichen Plattformen berechtigt" ist.

Quatsch. Es ist, wie fast immer, Microsoft vs. alle anderen.

Das char üblicherweise signed ist scheinen hier auch alle zu vergessen.

Das ist inwiefern von Belang? Wenn du glaubst, das Ergebnis von c - 64 hinge davon ab, dann solltest du dir noch einmal deine Integerpromotions angucken.

Und dann ist immer noch die Frage ob bei "zu weiten" Shifts bloss das Ergebnis implementation defined ist, oder ob der ganze Shift UB ist.
Wenn es UB ist, dann ist der Code sowieso falsch und darf auch auf 64 Bit long unsigned char Plattformen alles beliebige rauskommen sobald c >= 64.

Die Frage ist nicht, was rauskommen darf, sondern was tatsaechlich raus kommt. Dass der Code Mist ist, der sogar sein eigenes Ziel, die Optimierung, verfehlt, bestreitet niemand. Aber dass er nicht funktionieren wueerde ist einfach eine dreiste Behauptung, die du leicht durch Ausprobieren haettest widerlegen koennen, anstatt ewig lang aufzufuehren, warum der Code eventuell auch nicht funktionieren koennte. Jeder hier sieht, dass der Code unportabler Mist ist, der beim kleinsten Zeichen von Gefahr nicht mehr funktionieren wird, und warum. Steht in jedem Beitrag von der ersten Antwort an. Aber es ist einfach gelogen, zu behaupten, er wuerde auf der momentanen Zielplattform (anscheinend nicht Windows) nicht zuverlaessig funktionieren. Kein Compiler der momentanen Welt wird dir das falsch optimieren. Und wenn die Datentypen gross genug sind (nimm meinetwegen long long) und der Rechner Zweierkomplement benutzt, dann wird es funktionieren.

(Und noch als Zusatzinfo: LinkssShift von signed(!) Typen um mehr Stellen als der Datentyp breit ist: UB. Rechtsshift von negativen Zahlen: IB. Wenn der Autor also unsigned long long gewaehlt haette, waere die ganze Aktion sogar bestens definiert, da long long immer >= 64 Bits hat und der Shift bei unsigned Typen den ueblichen Ueberlaufregeln folgt. Wie schon gesagt, bestreitet niemand, dass der Code schlecht ist und leicht haette verbessert werden koennen.)

[hustbaer]

SeppJ schrieb:

hustbaer schrieb:

Somit wurde gezeigt, dass eine Implementierung, welche die hier stillschweigend angenommene Voraussetzung, dass sizeof(long) > 4, verletzt, tatsaechlich nicht funktioniert

So ziemlich jedes System verletzt diese Annahme. Die einzige Ausnahme ist GCC auf 64 Bit Plattformen. Womit die Annahme nicht "durchaus derzeit auf üblicher Hardware und auf üblichen Plattformen berechtigt" ist.

Quatsch. Es ist, wie fast immer, Microsoft vs. alle anderen.

Microsoft und so ziemlich alle 32 Bit Plattformen.

SeppJ schrieb:

Das char üblicherweise signed ist scheinen hier auch alle zu vergessen.

Das ist inwiefern von Belang? Wenn du glaubst, das Ergebnis von c - 64 hinge davon ab, dann solltest du dir noch einmal deine Integerpromotions angucken.

Das Problem ist dass ((c - 64) >> 31) nur das gewünschte Ergebnis hat wenn...
* die Interger-Promotion bei (c - 64) zu einem signed Datentyp führt und

• c selbst unsigned ist

Was passiert wenn der Typ von (c - 64) unsigned ist, sollte klar sein.
Und was passiert wenn c selbst signed ist, ist dass der Test nicht mehr für alle möglichen Werte funktioniert. Weil dann z.B. -32 zu einem positiven Ergebnis führt.

Aber dass er nicht funktionieren wueerde ist einfach eine dreiste Behauptung, die du leicht durch Ausprobieren haettest widerlegen koennen, anstatt ewig lang aufzufuehren, warum der Code eventuell auch nicht funktionieren koennte.

Der Code kann funktionieren, abhängig von der Plattform, dem Compiler und dem Typ von cursorChar .
Er funktioniert aber nicht sobald eine der folgenden Bedingungen zutrifft
* Die Plattform ist Windows
* Die Plattform ist 32 Bit und der Compiler ist GCC oder Clang

• cursorChar ist signed
• cursorChar ist grösser oder gleich gross wie int
  Also ja, wirklich eine sehr dreiste Behauptung.

[SeppJ]

Wenn in einer Diskussion um das Praxisverhalten von Code mit Ueberlegungen kommst zu char-Type, die breiter sind als int oder mit negativen ASCII-Werten, dann habe ich dir nichts mehr zu sagen. Du hast keine Argumente und fischt nach irgendwelchen fadenscheinigen Ausfluechten. Oder ich muss annehmen, dass du keine Ahnung von Integer-Promotions hast, aber trotzdem mitreden willst.

Ausser vielleicht einen Kommentar noch, da die folgende Behauptung nicht bloss unrealtistisch, sondern einfach falsch ist:

cursorChar ist signed

Das Vorzeichen von cursorChar ist irrelevant. Ausser du kommbinierst das wieder mit deinem char, der breiter ist als int .

[hustbaer]

SeppJ schrieb:

Ausser vielleicht einen Kommentar noch, da die folgende Behauptung nicht bloss unrealtistisch, sondern einfach falsch ist:

cursorChar ist signed

Das Vorzeichen von cursorChar ist irrelevant. Ausser du kommbinierst das wieder mit deinem char, der breiter ist als int .

Zeig mir bitte wie mit cursorChar = signed char = -32 das richtige rauskommen soll.

SeppJ schrieb:

Oder ich muss annehmen, dass du keine Ahnung von Integer-Promotions hast, aber trotzdem mitreden willst.

Wenn du mich beleidigen willst ist es einfacher dich diverser üblicher Schimpfworte zu bedienen.
Dass ich weiss wie Integer-Promotions funktionieren wissen wir beide.

[SeppJ]

hustbaer schrieb:

SeppJ schrieb:

Ausser vielleicht einen Kommentar noch, da die folgende Behauptung nicht bloss unrealtistisch, sondern einfach falsch ist:

cursorChar ist signed

Das Vorzeichen von cursorChar ist irrelevant. Ausser du kommbinierst das wieder mit deinem char, der breiter ist als int .

Zeig mir bitte wie mit cursorChar = signed char = -32 das richtige rauskommen soll.

Negative ASCII Werte. Nicht diskussionswuerdig.

Dass ich weiss wie Integer-Promotions funktionieren wissen wir beide.

Das will ich auch hoffen. Aber wenn du es weisst, worauf willst du hinaus? Dass der Code nicht funktioniert, wenn sizeof(char) == sizeof(int) und char vorzeichenlos ist? No shit, Sherlock! Man koennte fast meinen, dass der Code allerlei Annahmen macht, die vom Standard nicht garantiert werden. Aber willst du wirklich ernsthaft darueber diskutieren, dass diese Annahme unrealistisch waere? Erstens wurde das sowieso schon zu dem Code gesagt und zweitens ist sizeof(char) == sizeof(int) derart hypothetisch, dass mir jede Sekunde leid tut, die ich darueber schreibe.

Die einzige der stillschweigenden Annahmen, die hier von einer real existierenden Maschine tatsaechlich verletzt werden kann, ist die Annahme sizeof(long) >= 8. Und das wurde ebenfalls schon vor langer Zeit gesagt.

[hustbaer]

SeppJ schrieb:

hustbaer schrieb:

SeppJ schrieb:

Ausser vielleicht einen Kommentar noch, da die folgende Behauptung nicht bloss unrealtistisch, sondern einfach falsch ist:

cursorChar ist signed

Das Vorzeichen von cursorChar ist irrelevant. Ausser du kommbinierst das wieder mit deinem char, der breiter ist als int .

Zeig mir bitte wie mit cursorChar = signed char = -32 das richtige rauskommen soll.

Negative ASCII Werte. Nicht diskussionswuerdig.

Nicht negative ASCII Werte, negative char Werte.
Wenn ich eine Funktion schreibe, die nen char als Input nimmt, dann hab' ich ganz gerne dass die für alle möglichen Inputs nen sinnvollen Output liefert. Und ein sinnvoller Wert für eine "is whitespace" Funktion mit Parameter -32 ist wohl kaum "true". Vor allem wenn sie mit User-Input gefüttert wird.
Wenn du das "nicht diskussionswuerdig" findest, OK.

Du kannst aber nicht einfach eine Aussage von mir, die auf einer Annahme von mir basiert, die du "nicht diskussionswuerdig" findest, hernehmen, diese Annahme komplett ignorieren, und die Aussage dann als "schlicht falsch" bezeichnen. Und dann noch so tun als wüsstest du nicht was ich meine.

SeppJ schrieb:

Dass ich weiss wie Integer-Promotions funktionieren wissen wir beide.

Das will ich auch hoffen. Aber wenn du es weisst, worauf willst du hinaus? Dass der Code nicht funktioniert, wenn sizeof(char) == sizeof(int) und char vorzeichenlos ist? No shit, Sherlock! Man koennte fast meinen, dass der Code allerlei Annahmen macht, die vom Standard nicht garantiert werden. Aber willst du wirklich ernsthaft darueber diskutieren, dass diese Annahme unrealistisch waere? Erstens wurde das sowieso schon zu dem Code gesagt und zweitens ist sizeof(char) == sizeof(int) derart hypothetisch, dass mir jede Sekunde leid tut, die ich darueber schreibe.

Die einzige der stillschweigenden Annahmen, die hier von einer real existierenden Maschine tatsaechlich verletzt werden kann, ist die Annahme sizeof(long) >= 8. Und das wurde ebenfalls schon vor langer Zeit gesagt.

Das, und dass niemals negative Werte reingefüttert werden. Aber das ist ja wieder "nicht diskussionswuerdig".

ps: sizeof(char) == sizeof(int) ist überhaupt nicht hypothetisch. Es ist nur sehr unüblich, und auf Plattformen mit sizeof(char) == sizeof(int) tut man üblicherweise kein JSON parsen sondern z.B. Audiodaten verarbeiten. Aber darum ging es mir eigentlich gar nicht.

[FensterFrage]

Funktioniert das nun auf dem PC(was zu 90% Windows + VS ist) oder nicht?

[SeppJ]

hustbaer schrieb:

Nicht negative ASCII Werte, negative char Werte.

Erster Beitrag macht direkt klar, dass es nur um ASCII geht. Garbage in, garbage out. Nicht diskussionswuerdig.

ps: sizeof(char) == sizeof(int) ist überhaupt nicht hypothetisch. Es ist nur sehr unüblich, und auf Plattformen mit sizeof(char) == sizeof(int) tut man üblicherweise kein JSON parsen sondern z.B. Audiodaten verarbeiten.

Also hypothetisch. Denkst du, ich wuesste nicht, dass so etwas existiert? Ich habe irgendwie das Gefuehl, dass du mich mit deiner Kenntnis ueber "exotische" Computersysteme beeindrucken moechtest. Ich bin nicht beeindruckt.

Ich weiss echt nicht was du willst. Du behauptest, der Code wuerde nicht funktionieren, dabei koenntest du es einfach ausprobieren und sehen, dass er funktioniert. Stattdessen konstruierst du irgendwelche Sonderfaelle, in denen er nicht funktioniert. Als ob das nicht jedem bewusst waere, dass der Code unnoetig unportabel waere. Was willst du?

[hustbaer]

SeppJ schrieb:

Ich weiss echt nicht was du willst. Du behauptest, der Code wuerde nicht funktionieren, dabei koenntest du es einfach ausprobieren und sehen, dass er funktioniert.

Hab ich doch schon längst.

Stattdessen konstruierst du irgendwelche Sonderfaelle, in denen er nicht funktioniert. Als ob das nicht jedem bewusst waere, dass der Code unnoetig unportabel waere.

OK, ich hab' hier Mist geschrieben. Hauptsächlich weil ich deinen ersten Beitrag hier nicht vollständig gelesen habe. Ist vermutlich jedem schonmal passiert.

Also, da es dir so wichtig zu sein scheint: Der Code funktioniert - auf bestimmten Plattformen. 64 Bit usw., haben wir ja mittlerweile schon alles durch.

Was willst du?

Eigentlich nur mehr dass du aufhörst mich hier als Vollidioten hinzustellen, indem du Dinge aus dem Zusammenhang reisst. Und dass du von deinem hohen Ross wieder runterkommst. "Nicht diskussionswürdig" - wenn ich sowas schon lese.

[Columbo]

Sind Shifts um mehr als die Bitbreite des geshifteten Typs in C++ überhaupt definiert?

Eindeutig undefiniertes Verhalten:

[expr.shift]/1 schrieb:

The behavior is undefined if the right operand is […] greater than or equal to the length in bits of the promoted left operand.

[hustbaer]

@Arcoth
Unabhängig von signed/unsigned und Schieberichtung?