C - Funktion von Strlen verstehen

[Müller (Gast)]

Hallo zusammen,

vorweg mir geht es darum die Funktion von strlen zu verstehen. Bzw. wie 
genau der Ablauf dieser Funktion ist. Ich schaue da nicht ganz hinter, 
würde mich freuen, wenn ihr mir auf die Sprünge helfen könntent :)

Also geht um dieses Snippet:

size_t __cdecl strlen (const char* text) {
    const char *s;
    const uint32_t* pdwText;
    register uint32_t dwText;
 
    pdwText = (uint32_t*)text;
    while (1) {
        dwText = *pdwText;
 
        if ((dwText - 0x01010101UL) & ~dwText & 0x80808080UL) {
            s = (const char*)pdwText;
            while (*s) s++;
            return s - text;
        }
 
        pdwText++;
    }
}

Es stammt von dieser Seite: 
https://fredmameri.wordpress.com/2011/04/24/on-the-performance-of-strlen/

Ich versuche es mal mit meinen Worten zu erklären.

Sagen wir mal ich definiere einen String(Char Array) der den Inhalt 
"12345678"+(\0) hat, das wären ja 8 Bytes.

Ich gehe mal die Funktion durch:

----------------------------------------------------------------------

size_t __cdecl strlen (const char* text)

- Das cdecl irritiert mich schon direkt :( Das macht der Compiler doch 
schon von sich aus vor eine Funktion oder nicht?

----------------------------------------------------------------------

    const char *s;
    const uint32_t* pdwText;
    register uint32_t dwText;
 
    pdwText = (uint32_t*)text;

- Hier sind die Variablen Deklarationen
- der Pointer s wird benötigt für die innere Schleife
-> Dieser definiert sich aus pdwText welches dann explizit durch (const 
char*) gecastet wird.
-> Kann man den nicht weglassen?! pdwText ist doch auch ein Pointer vom 
Typ unsigned int, char ist doch im Prinzip auch ein Uint oder nicht?
- dwText soll mit dem Kennwort register einem Prozessor Register 
zugewiesen werden z.b.(eax). Im Prinzip ist das register doch "nur eine 
Empfehlung für den Compiler" oder etwa nicht?
- Der Pointer pdwText bekommt den Pointer von Text, jedoch mit einer 
Breite von 4 Bytes korrekt?
-> Ich hatte ja gesagt Text sei = "12345678", das sind ja 8 Bytes.
-> Wie sieht das bitte intern aus?? pdwText[0] = 1234, pdwText[1] = 
5678?
-> Erste 4 Bytes = pdwText[0], zweite 4 Bytes = pdwText[1]

----------------------------------------------------------------------

while (1) {
        dwText = *pdwText;

- while(1) wird niemals beendet, weil 1 eins ist, und nie Null werden 
kann
- dwText was im Prozessor Register optional liegt, bekommt die "ersten" 
4 Bytes vom pdwText also = "1234" bzw. die Adresse wo die ersten 4 Bytes 
sind, korrekt???

----------------------------------------------------------------------

if ((dwText - 0x01010101UL) & ~dwText & 0x80808080UL) {

- Offentsichtlich wird hier geprüft ob die 4 Bytes von dwText eine Null 
('\0') enthalten.
- Absolute Verwirrung pur ... :(
-> der Adressbereich der ersten 4 Bytes wird der ersten Hex Zahl 
abgezogen
-> Das Ergebnis wird bitweise verundet mit der Negation des 
Adressbereich der ersten 4 Bytes
-> Und dann wird das ganze nochmal verundet mit der zweiten Hex Zahl
-> Wenn das Ergebnis 1 ist, gehts in die innere Schleife.
-> Im Testfall der ersten 4 Bytes würde er jetzt nicht hierrein springen
-> Große Verwirrung... :(

----------------------------------------------------------------------

            s = (const char*)pdwText;
            while (*s) s++;
            return s - text;

- Sagen wir mal ich wäre beim zweiten Durchlauf, also die nächsten 4 
Bytes=(5678)
- s bekommt pdwText, jedoch mit einer Breite von einem Byte.
-> Dass heißt für den zweiten Durchlauf:
-> s[0] = 5, s[1] = 6, s[2] = 7, s[3] = 8, s[4] = '\0'
- Jetzt wird der Pointer solange hochgezählt bis while('\0') ist, dann 
wird while beendet
- Bedeutet dann im return : Adresse von '\0' - Adresse von "12345678"
- Das return wird dann implizit als size_t gecastet, und gibt dann 8 
zurück
- Bin total durcheinander :/

----------------------------------------------------------------------

       pdwText++;
    }
}

- Im ersten Durchlauf springt der hier direkt hin, und zählt den 
Adressbereich des Pointers um 4 Bytes hoch(weil ja u int 32 = 4 bytes), 
korrekt?
- Danach fängt er vorne an.
- Im zweiten Durchlauf kommt der gar nicht hierrein


Ich denke mal ich hab das komplett falsch verstanden, deswegen frag ich 
euch ja =)

Hoffe ihr könnt mir auf die Sprünge helfen.

Herzlichen Dank

Lieben gruß

[Rene H. (Gast)]

Deine Annahmen sind schon mal falsch.
1. es sind 9 Byte
2. char ist nicht zwingend uint. Das ist System und Compiler abhängig.

Den rest habe ich keine Lust durchzuspielen.

R.

[Johannes O. (jojo_2)]

also auf die schnelle kapier ich den Code auch nicht komplett, aber ich 
versuch mal ein paar Tipps zu geben. Übrigens finde ich den Code SEHR 
schlecht, dazu aber später mehr.


Müller schrieb:
> - while(1) wird niemals beendet, weil 1 eins ist, und nie Null werden
> kann

doch, weil es innerhalb des while(1) Schleife ein "return ..." gibt ;-)


Müller schrieb:
> -> Kann man den nicht weglassen?! pdwText ist doch auch ein Pointer vom
> Typ unsigned int, char ist doch im Prinzip auch ein Uint oder nicht?

Ein char ist erstmal 1 byte breit. Ein Int, abhängig von der Maschine 
kanns mal 2 oder auch 4 Byte usw. sein. Ein Pointer drauf ist natürlich 
immer gleich groß. ABER er macht den Cast explizit, da dies "guter Stil" 
ist und von manchen Coding Guidelines gefordert wird.


Du kannst den Code auch mal manuell durchsteppen, dann siehst du recht 
schnell was los ist.


Müller schrieb:
> Offentsichtlich wird hier geprüft ob die 4 Bytes von dwText eine Null
> ('\0') enthalten.
> - Absolute Verwirrung pur ... :(
> -> der Adressbereich der ersten 4 Bytes wird der ersten Hex Zahl
> abgezogen
> -> Das Ergebnis wird bitweise verundet mit der Negation des
> Adressbereich der ersten 4 Bytes
> -> Und dann wird das ganze nochmal verundet mit der zweiten Hex Zahl
> -> Wenn das Ergebnis 1 ist, gehts in die innere Schleife.
> -> Im Testfall der ersten 4 Bytes würde er jetzt nicht hierrein springen
> -> Große Verwirrung... :(

Pass auf, das sind KEINE Pointer mehr! In dwText steht bereits ein Teil 
deines Strings!
Der Code überprüft, ob mindestens 1 Byte davon 0 ist. Falls ja, dann 
wird die innere Schleife ausgeführt. Da wird nicht mit "Adressbereichen" 
gerechnet, sondern direkt mit dem Inhalt an der Adresse! Siehe Zeile 
darüber: "dwText = *pdwText;"


Generell halte ich den Code aber für NICHT empfehlenswert, da er auf 
anderen Architekturen Probleme machen kann:
- Er lädt grundsätzlich 4 Byte, egal wie lang der String ist. Wenn er 
doch nur 3 Byte lang ist, dann liest er über das Ende hinaus. Das geht 
meistens gut, aber nicht immer bzw. lässt sich das nicht wirklich 
beweisen.
- Noch schwerwiegender: Beim Cast von char* auf uint32_t* ist es NICHT 
mehr sichergestellt, dass das Alignment passt! Char* kann auf beliebige 
Adressen zeigen, das klappt normalerweise immer. Bei uint32_t* erfordern 
aber gewisse Architekturen, dass die Adresse ohne Rest durch 4 teilbar 
ist. Wenn du den Code also zum Beispiel auf SPARC laufen lässt, dann 
wird er dir in 3 von 4 Fällen um die Ohren fliegen und du bekommst vom 
Prozessor eine unaligned access exception.
Der Code ist also nur mit Einschränkungen zu empfehlen, sei dir klar, 
dass dies nicht das gelbe vom Ei ist ;-)

[Klaus (Gast)]

@Müller

So geht das nicht. Du hast so viele Lücken in den Grundlagen, dass es 
angebracht ist, erst einmal diese zu füllen. Daher rührt auch Deine 
überwältigende Verwirrung. Fange bei den einfachen Sachen an - nicht bei 
den komplizierten.

[Müller (Gast)]

Hey,
Mit geht es nur um das Verständnis. Der Vorteil soll wohl sein, dass 4 
Bytes gleichzeitig auf 0 geprüft werden können, denke ich.
Gruß

[Rene H. (Gast)]

Müller schrieb:
> Hey,
> Mit geht es nur um das Verständnis. Der Vorteil soll wohl sein, dass 4
> Bytes gleichzeitig auf 0 geprüft werden können, denke ich.
> Gruß

Da denkst Du richtig. Bedenke aber auch das der Code sowohl 
Betriebssystem als auch Architektur unabhängig ist.

Und bedenke das ASCII ursprünglich nur 127 Byte hatte. Also nicht 
signed.

R.

[Peter II (Gast)]

Kann jemand überblicken ob diese Optimierung Überhaupt sinnvoll ist?

schon diese 4 Rechenschritte,

if ((dwText - 0x01010101UL) & ~dwText & 0x80808080UL) {

brauchen doch schon die 4 fache Zeit von deinen einfachen Vergleich auf 
\0.

Dann sehe ich auch noch das Problem bei Stringende, wenn der String nur 
char[2] ist, dann greifst er auf 2byte zu, die schon nicht mehr zum 
Speicher der Variable gehören.

[Rene H. (Gast)]

Peter II schrieb:
> Kann jemand überblicken ob diese Optimierung Überhaupt sinnvoll ist?

Ich vermute signed/unsigned. Hab es aber nicht überprüft.

[Di P. (drpepper)]

Peter II schrieb:
> Kann jemand überblicken ob diese Optimierung Überhaupt sinnvoll ist?
>
> schon diese 4 Rechenschritte,
>
>

> if ((dwText - 0x01010101UL) & ~dwText & 0x80808080UL) {
>

>
> brauchen doch schon die 4 fache Zeit von deinen einfachen Vergleich auf
> \0.
>
> Dann sehe ich auch noch das Problem bei Stringende, wenn der String nur
> char[2] ist, dann greifst er auf 2byte zu, die schon nicht mehr zum
> Speicher der Variable gehören.

Deshalb halte ich den gezeigten Code auch nur bei 32 bit Architekturen 
für sinnvoll. Man müsste mal raussuchen, wie strlen für 8-Bit-AVR 
implementiert ist...

[apr (Gast)]

Peter II schrieb:
> Kann jemand überblicken ob diese Optimierung Überhaupt sinnvoll ist?
>
> schon diese 4 Rechenschritte,
> if ((dwText - 0x01010101UL) & ~dwText & 0x80808080UL) {
>
> brauchen doch schon die 4 fache Zeit von deinen einfachen Vergleich auf
> \0.
Ja, aber beim Vergleich von mehr Bytes, muss er das seltener machen. 
Noch schlimmer: Wenn man Pech hat bedeutet der Zugriff auf ein char, 
dass es zunächst maskiert und eventuell geshiftet werden muss.

Ich hatte es mal bei einer Kopierroutine getestet. Da brachte das einen 
ziemlichen Vorteil (auf einer x86 Architektur).

[apr (Gast)]

Di P. schrieb:
> Deshalb halte ich den gezeigten Code auch nur bei 32 bit Architekturen
> für sinnvoll. Man müsste mal raussuchen, wie strlen für 8-Bit-AVR
> implementiert ist...

http://svn.savannah.nongnu.org/viewvc/trunk/avr-libc/libc/string/strlen.S?root=avr-libc&view=markup

[Peter II (Gast)]

apr schrieb:
> Peter II schrieb:
>> Kann jemand überblicken ob diese Optimierung Überhaupt sinnvoll ist?
>>
>> schon diese 4 Rechenschritte,
>> if ((dwText - 0x01010101UL) & ~dwText & 0x80808080UL) {
>>
>> brauchen doch schon die 4 fache Zeit von deinen einfachen Vergleich auf
>> \0.
> Ja, aber beim Vergleich von mehr Bytes, muss er das seltener machen.
> Noch schlimmer: Wenn man Pech hat bedeutet der Zugriff auf ein char,
> dass es zunächst maskiert und eventuell geshiftet werden muss.
wo kann man denn nicht direkt auf ein Byte zugreifen?

> Ich hatte es mal bei einer Kopierroutine getestet. Da brachte das einen
> ziemlichen Vorteil (auf einer x86 Architektur).
beim kopieren muss ja diese "komplizierte" Rechnung nicht gemacht 
werden, dann ist ja klar das 4bytes auf einmal kopieren schneller ist 
als jedes Byte einzeln.

[Di P. (drpepper)]

Okay, hier ist die Implemetierung in der avr-libc: (too late, apr ;) )

#include "macros.inc"

#define src_hi r25
#define src_lo r24

; 10 words, (14 + strlen(src) * 5) cycles

  ASSEMBLY_CLIB_SECTION
  .global  _U(strlen)
  .type  _U(strlen), @function
_U(strlen):
  X_movw  ZL, src_lo
.L_strlen_loop:
  ld  __tmp_reg__, Z+
  tst  __tmp_reg__
  brne  .L_strlen_loop
; Z points one character past the terminating NUL
; return Z - 1 - src = (-1 - src) + Z = ~src + Z
  com  src_lo
  com  src_hi
  add  src_lo, ZL
  adc  src_hi, ZH
  ret
.L_strlen_end:
  .size  _U(strlen), .L_strlen_end - _U(strlen)

Kann kein Assembler, aber vielleicht erkennt ja jemand Parallelen oder 
Unterschiede...

[Frank (Gast)]

Determine if a word has a zero byte
[...]
There is yet a faster method — use hasless(v, 1), which is defined 
below; it works in 4 operations and requires no subsquent verification. 
It simplifies to

#define haszero(v) (((v) - 0x01010101UL) & ~(v) & 0x80808080UL)

The subexpression (v - 0x01010101UL), evaluates to a high bit set in any 
byte whenever the corresponding byte in v is zero or greater than 0x80. 
The sub-expression ~v & 0x80808080UL evaluates to high bits set in bytes 
where the byte of v doesn't have its high bit set (so the byte was less 
than 0x80). Finally, by ANDing these two sub-expressions the result is 
the high bits set where the bytes in v were zero, since the high bits 
set due to a value greater than 0x80 in the first sub-expression are 
masked off by the second.

Paul Messmer suggested the fast pretest improvement on October 2, 2004. 
Juha Järvi later suggested hasless(v, 1) on April 6, 2005, which he 
found on Paul Hsieh's Assembly Lab; previously it was written in a 
newsgroup post on April 27, 1987 by Alan Mycroft.

http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord

[asdfasd (Gast)]

> mir geht es darum die Funktion von strlen zu verstehen

Geht es dir darum, was strlen per Standard macht oder darum, wie das 
deine Beispielimplementation erreicht?

Falls letzteres: falscher Zeitpunkt.  Deine Fragen zeigen, dass du 
Anfänger bist und die Implementation von strlen, die du dir rausgesucht 
hast, ist eine stark optimierte Version, die, wie man hier sieht, selbst 
erfahrene Programmierer aufs Glatteis führen kann (sie ist fehlerhaft). 
In der Mathematik fängst du ja auch mit den Grundrechenarten an, nicht 
mit der Analysis.

Wenn es dir darum geht, die Funktion von strlen anhand einer 
Implementation zu "erforschen", hier zwei normale Implementationen:

size_t strlen_v1(const char *str)
{
    const char *p = str;

    while (*p)
        p++;

    return p - str;
}

size_t strlen_v2(const char *str)
{
    size_t n = 0;

    while (*str++)
        n++;

    return n;
}

[Rene H. (Gast)]

Müller schrieb:
> pdwText = (uint32_t*)text;

Auf einer Sparc würde das unter umständen mit Core dump enden, wegen 
paging fault.

Somit ist dieser Code auch nicht portabel.

[mar IO (Gast)]

Di P. schrieb:
> Deshalb halte ich den gezeigten Code auch nur bei 32 bit Architekturen
> für sinnvoll. Man müsste mal raussuchen, wie strlen für 8-Bit-AVR
> implementiert ist...

Wie in den Link beschrieben, ist der gezeigte Code für 32 Bit gedacht. 
Für einen 8-Bittler ist der Code nicht gedacht.

Ich habe mal ein paar weitere strlen() zusammengesucht (für 32-Bittler):

gnu libc strlen()
https://github.com/lattera/glibc/blob/master/string/strlen.c

freebsd libc strlen()
http://svnweb.freebsd.org/base/head/lib/libc/string/strlen.c?view=markup

ulibc libc strlen()
http://git.uclibc.org/uClibc/tree/libc/string/strlen.c

ulibc libc arm strlen()
http://git.uclibc.org/uClibc/tree/libc/string/arm/strlen.S

OS X 10.10 libc strlen()
http://www.opensource.apple.com/source/Libc/Libc-1044.40.1/string/FreeBSD/strlen.c

Wenn ich das richtig gesehen habe, dann macht das FreeBSD ähnlich.

Der Code von OS X 10.10 ist eine alte Version von FreeBSD
http://svnweb.freebsd.org/base/head/lib/libc/string/strlen.c?revision=187707&view=markup

[mar IO (Gast)]

mar IO schrieb im Beitrag #4306616 und merkt an:
> gnu libc strlen()

strlen() für x86. Für andere Architekturen z.B. sparc findet man unter 
sysdeps/.

[apr (Gast)]

Peter II schrieb:
>> Ja, aber beim Vergleich von mehr Bytes, muss er das seltener machen.
>> Noch schlimmer: Wenn man Pech hat bedeutet der Zugriff auf ein char,
>> dass es zunächst maskiert und eventuell geshiftet werden muss.
> wo kann man denn nicht direkt auf ein Byte zugreifen?
>
Keine Ahnung – Möglich wärs aber ;) (tatsächlich dachte ich ARM hätte 
solche Probleme…)

>> Ich hatte es mal bei einer Kopierroutine getestet. Da brachte das einen
>> ziemlichen Vorteil (auf einer x86 Architektur).
> beim kopieren muss ja diese "komplizierte" Rechnung nicht gemacht
> werden, dann ist ja klar das 4bytes auf einmal kopieren schneller ist
> als jedes Byte einzeln.
Naja wer misst, misst Mist:
opt ist die oben geschriebene Funktion. In Klammern die größe des 
Datentyps. Dann kommt die Anzahl der Elemente in "text" und die 
gemessene Zeit.

Optimizer: OFF
1000000 iterations
opt (4):          10: 12ms,       20: 17ms,      100: 106ms,     500: 292ms,    1000: 572ms
v1:               10: 16ms,       20: 35ms,      100: 225ms,     500: 1072ms,   1000: 2129ms
v2:               10: 19ms,       20: 37ms,      100: 202ms,     500: 971ms,    1000: 1968ms
opt (8):          10: 7ms,        20: 9ms,       100: 34ms,      500: 421ms,    1000: 282ms
opt (16):         10: 411ms,      20: 408ms,     100: 398ms,     500: 374ms,    1000: 252ms

Optimizer: ON
1000000 iterations
opt (4):          10: 6ms,        20: 9ms,       100: 54ms,      500: 148ms,    1000: 182ms
v1:               10: 9ms,        20: 18ms,      100: 51ms,      500: 214ms,    1000: 409ms
v2:               10: 4ms,        20: 12ms,      100: 52ms,      500: 219ms,    1000: 434ms
opt (8):          10: 2ms,        20: 2ms,       100: 14ms,      500: 60ms,     1000: 97ms
opt (16):         10: 86ms,       20: 85ms,      100: 83ms,      500: 77ms,     1000: 55ms

[Mikro 7. (mikro77)]

Rene H. schrieb:
> Auf einer Sparc würde das unter umständen mit Core dump enden, wegen
> paging fault.

Die "richtigen" Implementierungen (siehe Beitrag mar IO) scheinen vorher 
ein Alignment durchzuführen. Dadurch hatte man "passende" Zugriffe und 
fällt auch auf keine falsche Page.

Peter II schrieb:
> ...brauchen doch schon die 4 fache Zeit von deinen einfachen Vergleich

Vergleich ist nicht gleich Vergleich. Speicherzugriffe sind bspw. recht 
teuer. Hatte letztens einen Fall wo 10 Operationen eine 8-Bit Lookup 
Table outperformed haben (Intel x86_64).

apr schrieb:
> Naja wer misst...

Interessant. Danke. :-)

Hätte nicht gedacht, dass das sooo viel bringt. Ich hätte spekuliert, 
dass das Nachfüllen des Caches das Bottleneck ist und die Optimierung 
daher ins Leere läuft.

[Di P. (drpepper)]

Wie ist denn bei Wortlänge 16byte zu erklären, dass bei 1000 Zeichen in 
der Kette weniger Zeit benötigt wird, als bei 10?

[Mikro 7. (mikro77)]

Wollte mal gucken, ob der Cache vllt. nicht doch das Bottleneck ist. -- 
Ist er nicht. Wen's interessiert, anbei die Zeiten (s) für 64GiB checks.

      (A)    (B)    (C)    (D)
(1)  3.70  43.72  19.31  12.84
(2)  6.15  43.35  20.86  13.04
(3) 10.56  45.25  24.05  13.48
(4) 10.06  41.28  18.31  11.26

2nd run:

      (A)    (B)    (C)    (D)
(1)  3.71  43.77  19.35  13.65
(2)  6.17  43.41  20.91  12.96
(3) 10.67  45.39  24.26  13.66
(4) 10.09  41.40  18.21  11.17

1 - 256 bytes cached          A - strlen (C-lib)             
2 - 256 bytes less cached     B - byte by byte
3 - 256 bytes not (?) cached  C - 4-byte blocks
4 - consecutive 256MiB block  D - 8 byte blocks

[temp (Gast)]

Interessant ist das ganze bei uns auch gewesen in Verbindung mit Visual 
C++ 2010. Da steckt in den libs auch eine strlen-Version die 
schnarchlangsam ist. Hier hat die Implementierung einer eigenen Funktion 
ähnlich wie ganz oben einen Faktor 10 gebracht. Es ging dabei um 
Datenbankimporte von mehreren 100 Mio Datensätzen. Ob in den neueren 
Versionen das anders ist haben wir aber nie untersucht. Es war auf alle 
Fälle schon ein Erkenntnisgewinn festzustellen, dass strlen den 
dramatischen Performanceunterschied zur Linux und OSX-Version des selben 
Programmteils verursachte.
Natürlich ist nicht immer strlen in den innersten Schleifen beteiligt, 
da spielt die ganze Betrachtung keine Rolle. Aber wehe sie wird 
millionenfach in engen Schleifen benutzt, dann kann man schon 
Überraschungen erleben.

[Peter II (Gast)]

temp schrieb:
> Hier hat die Implementierung einer eigenen Funktion
> ähnlich wie ganz oben einen Faktor 10 gebracht.

kann ich fast nicht glauben, wie in den Beispielen von  S. J. geht es 
dort maximal um Faktor 4. Zwischen der primitivsten und optimiertesten 
Version.

Oder arbeitet ihr mit Wide / Unicode Strings?

[temp (Gast)]

Genaue Zahlen habe ich nicht mehr, dazu ist das zu lange her. Einigen 
wir uns auf "gefühlte" 10. Der Unterschied war jedenfalls dramatisch. 
Wir setzen jetzt unter Windows die glibc-Variante ein. z.B. hier:

https://github.com/zerovm/glibc/blob/master/string/strlen.c

[Peter II (Gast)]

S. J. schrieb:
> Wollte mal gucken, ob der Cache vllt. nicht doch das Bottleneck ist. --
> Ist er nicht. Wen's interessiert, anbei die Zeiten (s) für 64GiB checks.

Kann das nicht zu fehler führen?

size_t strlen_3(char const *s)

unsigned long const *q = (unsigned long*)p ;

  while (0 == ((*q - 0x0101010101010101ul) & ~(*q) & 0x8080808080808080ul))
    ++q ;

hier wird ja mit sizeof( Long ) über den String gesprungen. Was ist wenn 
der speicherbreich für die Variabel gar nicht so gross ist?

char[2] x = 'a'

dann werden doch noch 6byte gelesen die nicht mehr dazugehören. Wenn das 
ganze auf einer Segmetgrenze kommt, dann kann es doch so einer 
Read-Access-Violation kommen oder nicht? Oder hoft man einfach das das 
nie der Fall ist?

[Michael B. (laberkopp)]

Müller schrieb:
> Es stammt von dieser Seite:

Der Code ist falsch.

Er greift bis 3 Bytes hinter das Ende des Strings zu,
das kann bei Prozessorarchitekturen mit Speicherschutz schon mal einen 
Absturz ergeben,
und er greift beginnend mit dem Anfang des Strings auf 32 bit Werte zu, 
das kann bei Prozessorarchitekturen deren Prozessoren nur aligned 
zugreifen dürfen wie Sparc auch eine Exception geben,
denn character-Strings dürfen an jeder byte-Position beginnen.

So etwas darf man in einer Standard-Library machen die zu einem 
Prozessor gehört wenn man sich sicher ist, daß er das akzeptiert, aber 
nicht in selbst geschriebenem code der eines Tages mal auf eine andere 
Plattform soll.

[Peter II (Gast)]

Michael B. schrieb:
> Müller schrieb:
>> Es stammt von dieser Seite:
>
> Der Code ist falsch.
>
> Er greift bis 3 Bytes hinter das Ende des Strings zu,
> das kann bei Prozessorarchitekturen mit Speicherschutz schon mal einen
> Absturz ergeben,

das machen merkwürdigerweise alle "schnellen" Implementierungen von 
strlen. (was auch gar nicht anders geht, wenn man mehr als 1byte 
gleichzeitig prüfen will).

Scheinbar hoffen alle, das der String nicht am ende einer Page liegt - 
oder ist das irgendwo sichergestellt?

[Mikro 7. (mikro77)]

Peter II schrieb:
> ... Wenn das
> ganze auf einer Segmetgrenze kommt, dann kann es doch so einer
> Read-Access-Violation kommen oder nicht? Oder hoft man einfach das das
> nie der Fall ist?

Davor steht aber...

  while (1) {
    if (p[0] == '\0')
      return p - s ;
    if (0x0 == ((unsigned long)p & (sizeof(p)-1)))
      break ;
    ++p ;
  }

Wobei ich gerade sehe, dass das eine "optimierte" version ist.
(if Abfragen andersherum ist in fast allen Fällen besser)

[Peter II (Gast)]

S. J. schrieb:
> Davor steht aber...

ja und? dann liest er immer noch hinter der Variabel Daten aus.

[Mikro 7. (mikro77)]

Und? Was passiert dann? Welches System hat Page oder "Segmentgrenzen" 
die nicht aligned sind? Nur bei denen, kann es zu Problemen kommen.

[Peter II (Gast)]

S. J. schrieb:
> Und? Was passiert dann? Welches System hat Page oder "Segmentgrenzen"
> die nicht aligned sind? Nur bei denen, kann es zu Problemen kommen.

das ist ja die große Frage. C legt es zumindest nicht fest. Es könnte 
auch für jede Variable eine Page in der größe der Variable vorhanden 
sein.

[Michael B. (laberkopp)]

S. J. schrieb:
> Und? Was passiert dann? Welches System hat Page oder
> "Segmentgrenzen"
> die nicht aligned sind? Nur bei denen, kann es zu Problemen kommen.

Da der String nicht-aligned beginnen kann

x = strlen(strchr("Hallo Welt",'W'))

kann hinter der '\0' durchaus eine Page-Grenze zu Ende sein.

[Mikro 7. (mikro77)]

Peter II schrieb:

> Es könnte
> auch für jede Variable eine Page in der größe der Variable vorhanden
> sein.

Prinzipiell hast Du Recht.

Nenn mir aber eine Architektur/OS wo Pages oder Speicherschutz nicht 
aligned sind.

@ Michael Bertrandt: Guck Dir den Code an.
-> Beitrag "Re: C - Funktion von Strlen verstehen"

[Michael B. (laberkopp)]

S. J. schrieb:
> @ Michael Bertrandt: Guck Dir den Code an.
> -> Beitrag "Re: C - Funktion von Strlen verstehen"

Gilt aber, wenn ich das so verstehe, nicht für die Funktion von Müller, 
sondern für eine besser implementierte Libraryfunktion.

[Hans (Gast)]

Michael B. schrieb:
> S. J. schrieb:
>> Und? Was passiert dann? Welches System hat Page oder
>> "Segmentgrenzen"
>> die nicht aligned sind? Nur bei denen, kann es zu Problemen kommen.
>
> Da der String nicht-aligned beginnen kann
>
> x = strlen(strchr("Hallo Welt",'W'))
>
> kann hinter der '\0' durchaus eine Page-Grenze zu Ende sein.

In den korrekten Implementierungen werden die Wörter nur aligned 
gelesen. Wenn hinter der '\0' die Page zu Ende ist, dann war die '\0' 
das letzte Byte innerhalb des Worts. Danach wird kein weiteres Wort mehr 
gelesen.

[Peter II (Gast)]

Hans schrieb:
> In den korrekten Implementierungen werden die Wörter nur aligned
> gelesen. Wenn hinter der '\0' die Page zu Ende ist, dann war die '\0'
> das letzte Byte innerhalb des Worts. Danach wird kein weiteres Wort mehr
> gelesen.

das hoffen alle, festgelegt ist das nirgends.

[Mikro 7. (mikro77)]

lach -- Die typische Page Size ist numal 4K. Kann man bestimmt auch iwo 
nachlesen...

Michael B. schrieb:

> Gilt aber, wenn ich das so verstehe, nicht für die Funktion von Müller,
> sondern für eine besser implementierte Libraryfunktion.

Er bezog sich auf "meine" Implementierung. Und da ist das drin.