x86 uses the C versions of bcmp() and memcmp() now.

Rewrite bcmp() & memcmp() to not use REP CMPS. Seems about 5-10x faster for
small strings on modern hardware.

branches: 1.3.26; 1.3.30;
For all x86_64 string assembly functions that don't overlap (i.e. every
one except memset and bzero) use END() so that symbol size information
is available.

branches: 1.2.28; 1.2.34;
Don't unconditionally clear the direction flag. The ABI says it must always
be clear when making a function call, and 'cld' takes about 50 clock cyles
on the P4.

branches: 1.1.18;
Merge libkern + libc common files. As requested by core.

branches: 1.5.26;
For all x86_64 string assembly functions that don't overlap (i.e. every
one except memset and bzero) use END() so that symbol size information
is available.

branches: 1.4.6; 1.4.12;
Align to the destination buffer.
This probably costs 1 clock (on modern cpus) in the normal case.
But gives a big benefit when the destination is misaligned.
In particular when the source has the same misalignment - although
that may not be a gain on Nehalem!
Fixes PR/35535

Avoid doing two 'rep movs' operations.

Don't unconditionally clear the direction flag. The ABI says it must always
be clear when making a function call, and 'cld' takes about 50 clock cyles
on the P4.

branches: 1.1.18;
Merge libkern + libc common files. As requested by core.

Remove x86_64 bzero.S; which since 2009 has only contained instructions
that it should be removed in 2010.

branches: 1.3.6; 1.3.12;
Remove some long dependant instruction sequences (ie allow parallel code).
Since 'rep stos' will have a long setup time, avoid doing it more than once.
For misaligned (start address or length) write an unaligned word at both
ends of the buffer then aligned 'rep stosd' the middle.
Use the same code for bzero().
bzero.S is left being compiled for a while (empty) - to avoid issues with
duplicate symbols in libc.a after update builds.

Don't unconditionally clear the direction flag. The ABI says it must always
be clear when making a function call, and 'cld' takes about 50 clock cyles
on the P4.

branches: 1.1.18;
Merge libkern + libc common files. As requested by core.

branches: 1.5.26;
For all x86_64 string assembly functions that don't overlap (i.e. every
one except memset and bzero) use END() so that symbol size information
is available.

branches: 1.4.6; 1.4.12;
Put back dsl's string changes, but fix memchr.S to use cmp so that the
condition code is set (and fix the comments 0x10->0x01). From Anon Ymous
We need a test for memchr(x, -1)...

revert changes that made new kernels hang in ACPI detection

Remove a pointless _ALIGN_TEXT.
XXX ffs() ought to be a gcc inline asm.

branches: 1.1.36;
Merge libkern + libc common files. As requested by core.

Delete files that are no longer needed.

branches: 1.1.36;
Merge libkern + libc common files. As requested by core.

branches: 1.6.26;
For all x86_64 string assembly functions that don't overlap (i.e. every
one except memset and bzero) use END() so that symbol size information
is available.

branches: 1.5.6; 1.5.12;
In the misaligned case, xor the read word with the target pattern
before making the unwanted bytes non-zero.
Means that memchr(buf, 0xff) is no longer a special case.

Put back dsl's string changes, but fix memchr.S to use cmp so that the
condition code is set (and fix the comments 0x10->0x01). From Anon Ymous
We need a test for memchr(x, -1)...

revert changes that made new kernels hang in ACPI detection

A better memchr().
Always read aligned words, invalidating unwanted bytes in first word,
and checking that any match in the last word is before the buffer end.
No loops apart from the one through the data.

branches: 1.1.36;
Merge libkern + libc common files. As requested by core.

x86 uses the C versions of bcmp() and memcmp() now.

Back out previous, it's broken.

Rewrite bcmp() & memcmp() to not use REP CMPS. Seems about 5-10x faster for
small strings on modern hardware.

branches: 1.3.26; 1.3.30;
For all x86_64 string assembly functions that don't overlap (i.e. every
one except memset and bzero) use END() so that symbol size information
is available.

branches: 1.2.28; 1.2.34;
Don't unconditionally clear the direction flag. The ABI says it must always
be clear when making a function call, and 'cld' takes about 50 clock cyles
on the P4.

branches: 1.1.18;
Merge libkern + libc common files. As requested by core.

branches: 1.1.94;
Merge libkern + libc common files. As requested by core.

branches: 1.1.94;
Merge libkern + libc common files. As requested by core.

branches: 1.5.24;
fix build for _KERNEL

Put missing END() markers to set ELF symbol size.

branches: 1.3.12; 1.3.24;
Remove some long dependant instruction sequences (ie allow parallel code).
Since 'rep stos' will have a long setup time, avoid doing it more than once.
For misaligned (start address or length) write an unaligned word at both
ends of the buffer then aligned 'rep stosd' the middle.
Use the same code for bzero().
bzero.S is left being compiled for a while (empty) - to avoid issues with
duplicate symbols in libc.a after update builds.

Don't unconditionally clear the direction flag. The ABI says it must always
be clear when making a function call, and 'cld' takes about 50 clock cyles
on the P4.

branches: 1.1.18;
Merge libkern + libc common files. As requested by core.

Delete files that are no longer needed.

branches: 1.1.36;
Merge libkern + libc common files. As requested by core.

branches: 1.2.26;
For all x86_64 string assembly functions that don't overlap (i.e. every
one except memset and bzero) use END() so that symbol size information
is available.

branches: 1.1.50; 1.1.56;
Merge libkern + libc common files. As requested by core.

branches: 1.7.26;
For all x86_64 string assembly functions that don't overlap (i.e. every
one except memset and bzero) use END() so that symbol size information
is available.

branches: 1.6.6; 1.6.12;
Put back dsl's string changes, but fix memchr.S to use cmp (rather
than test) so that the condition code is set correctly (and fix the
comments: 0x10->0x01 and ^->&). From Anon Ymous

XXX: There are similar comment errors in some of the other string code.

XXX: We really need a regression test that includes misaligned memory
with searches designed to catch corner cases such as searching for 0,
-1, etc, and search length limit violations. Searching for 0 on
misaligned memory would have caught this problem.

revert changes that made new kernels hang in ACPI detection

Shorten a dependency chain by using 'sbb, xor' (at a time when carry is set)
instead of 'mov, neg, dec'.
('mov, not' can't be used because it doesn't set the flags.)

Replace with a version that:
1) doesn't do byte compares to find which byte matched
2) doesn't do byte compares if any top bits are set
3) doesn't use a loop when the input is misaligned
4) has less mispredicted branches
Passes regression tests and 'build.sh' doesn't explode (and more than usual).

Change all archs so that strchr.[cS] and strrchr.[cS] exist and generate
duplicate symbols for index() and rindex().

branches: 1.1.36;
Merge libkern + libc common files. As requested by core.

branches: 1.2.26;
For all x86_64 string assembly functions that don't overlap (i.e. every
one except memset and bzero) use END() so that symbol size information
is available.

branches: 1.1.50; 1.1.56;
Merge libkern + libc common files. As requested by core.

branches: 1.2.26;
For all x86_64 string assembly functions that don't overlap (i.e. every
one except memset and bzero) use END() so that symbol size information
is available.

branches: 1.1.50; 1.1.56;
Merge libkern + libc common files. As requested by core.

s/Westley/Wesley/ in a book reference (in comments).

s/efficent/efficient/ in comments.

branches: 1.6.26;
For all x86_64 string assembly functions that don't overlap (i.e. every
one except memset and bzero) use END() so that symbol size information
is available.

branches: 1.5.6; 1.5.12;
Add netbsd copyright.
Reorder a few instructions to interleave a dependency chain.
(I'm really not sure of the best order for those instructions!)

Correct some comments

After alg 2 triggers, mask with ~x (alg 3) to ignore bytes with top bit set.
Then use bit scan to work out which byte is zero.
If the source is misaligned read the aligned word and make the unwanted
(low order) bytes non-zero.
Passes regression test - which probably tests just enough cases.

Change comments about algorithms, 99.6% for random data isn't 'rare' in my book!
(The 'rare' case is any byte values 0x80-0xff.)

branches: 1.1.36;
Merge libkern + libc common files. As requested by core.

branches: 1.3.26;
For all x86_64 string assembly functions that don't overlap (i.e. every
one except memset and bzero) use END() so that symbol size information
is available.

branches: 1.2.6; 1.2.12;
Change all archs so that strchr.[cS] and strrchr.[cS] exist and generate
duplicate symbols for index() and rindex().

branches: 1.1.36;
Merge libkern + libc common files. As requested by core.