diff options
Diffstat (limited to 'na')
56 files changed, 2624 insertions, 0 deletions
diff --git a/na/include/libc-shim/bits/alltypes.h b/na/include/libc-shim/bits/alltypes.h new file mode 100644 index 0000000..cf21a5e --- /dev/null +++ b/na/include/libc-shim/bits/alltypes.h @@ -0,0 +1,15 @@ +/* Shim: provide types musl string functions need */ +#ifndef _BITS_ALLTYPES_H +#define _BITS_ALLTYPES_H + +#ifndef __cplusplus +typedef unsigned long size_t; +#endif + +typedef long ssize_t; +typedef unsigned long uintptr_t; + +/* locale_t stub — unused in kernel, but declared by some headers */ +typedef void *locale_t; + +#endif diff --git a/na/include/libc-shim/endian.h b/na/include/libc-shim/endian.h new file mode 100644 index 0000000..8346386 --- /dev/null +++ b/na/include/libc-shim/endian.h @@ -0,0 +1,9 @@ +/* Shim: endianness for musl string functions */ +#ifndef _ENDIAN_H +#define _ENDIAN_H + +#define __LITTLE_ENDIAN 1234 +#define __BIG_ENDIAN 4321 +#define __BYTE_ORDER __LITTLE_ENDIAN /* RISC-V is LE */ + +#endif diff --git a/na/include/libc-shim/features.h b/na/include/libc-shim/features.h new file mode 100644 index 0000000..a3466c8 --- /dev/null +++ b/na/include/libc-shim/features.h @@ -0,0 +1,12 @@ +/* Shim: musl expects this header */ +#ifndef _FEATURES_H +#define _FEATURES_H + +/* weak_alias: musl uses this for symbol aliasing (e.g. __memrchr -> memrchr) */ +#define weak_alias(old, new) \ + extern __typeof(old) new __attribute__((__weak__, __alias__(#old))) + +/* hidden attribute used by some musl sources */ +#define hidden __attribute__((__visibility__("hidden"))) + +#endif diff --git a/na/include/libc-shim/limits.h b/na/include/libc-shim/limits.h new file mode 100644 index 0000000..a1d546e --- /dev/null +++ b/na/include/libc-shim/limits.h @@ -0,0 +1,17 @@ +/* Shim: limits for musl string functions (memmem uses SIZE_MAX) */ +#ifndef _LIMITS_H +#define _LIMITS_H + +#define CHAR_BIT 8 +#define UCHAR_MAX 255 +#define SCHAR_MAX 127 +#define SCHAR_MIN (-128) +#define INT_MAX 2147483647 +#define INT_MIN (-INT_MAX - 1) +#define UINT_MAX 4294967295U +#define LONG_MAX 9223372036854775807L +#define LONG_MIN (-LONG_MAX - 1L) +#define ULONG_MAX 18446744073709551615UL +#define SIZE_MAX ULONG_MAX + +#endif diff --git a/na/include/libc-shim/stdint.h b/na/include/libc-shim/stdint.h new file mode 100644 index 0000000..650bdcf --- /dev/null +++ b/na/include/libc-shim/stdint.h @@ -0,0 +1,21 @@ +/* Shim: stdint types for musl string functions */ +#ifndef _STDINT_H +#define _STDINT_H + +typedef unsigned char uint8_t; +typedef unsigned short uint16_t; +typedef unsigned int uint32_t; +typedef unsigned long uint64_t; +typedef signed char int8_t; +typedef signed short int16_t; +typedef signed int int32_t; +typedef signed long int64_t; +typedef unsigned long uintptr_t; +typedef long intptr_t; + +#define UINT8_MAX 0xFF +#define UINT16_MAX 0xFFFF +#define UINT32_MAX 0xFFFFFFFFU +#define UINT64_MAX 0xFFFFFFFFFFFFFFFFUL + +#endif diff --git a/na/include/libc-shim/string.h b/na/include/libc-shim/string.h new file mode 100644 index 0000000..8a86304 --- /dev/null +++ b/na/include/libc-shim/string.h @@ -0,0 +1,110 @@ +#ifndef _STRING_H +#define _STRING_H + +#ifdef __cplusplus +extern "C" { +#endif + +#include <features.h> + +#if __cplusplus >= 201103L +#define NULL nullptr +#elif defined(__cplusplus) +#define NULL 0L +#else +#define NULL ((void*)0) +#endif + +#define __NEED_size_t +#if defined(_POSIX_SOURCE) || defined(_POSIX_C_SOURCE) \ + || defined(_XOPEN_SOURCE) || defined(_GNU_SOURCE) \ + || defined(_BSD_SOURCE) +#define __NEED_locale_t +#endif + +#include <bits/alltypes.h> + +void *memcpy (void *__restrict, const void *__restrict, size_t); +void *memmove (void *, const void *, size_t); +void *memset (void *, int, size_t); +int memcmp (const void *, const void *, size_t); +void *memchr (const void *, int, size_t); + +char *strcpy (char *__restrict, const char *__restrict); +char *strncpy (char *__restrict, const char *__restrict, size_t); + +char *strcat (char *__restrict, const char *__restrict); +char *strncat (char *__restrict, const char *__restrict, size_t); + +int strcmp (const char *, const char *); +int strncmp (const char *, const char *, size_t); + +int strcoll (const char *, const char *); +size_t strxfrm (char *__restrict, const char *__restrict, size_t); + +char *strchr (const char *, int); +char *strrchr (const char *, int); + +size_t strcspn (const char *, const char *); +size_t strspn (const char *, const char *); +char *strpbrk (const char *, const char *); +char *strstr (const char *, const char *); +char *strtok (char *__restrict, const char *__restrict); + +size_t strlen (const char *); + +char *strerror (int); + +#if defined(_BSD_SOURCE) || defined(_GNU_SOURCE) +#include <strings.h> +#endif + +#if defined(_POSIX_SOURCE) || defined(_POSIX_C_SOURCE) \ + || defined(_XOPEN_SOURCE) || defined(_GNU_SOURCE) \ + || defined(_BSD_SOURCE) +char *strtok_r (char *__restrict, const char *__restrict, char **__restrict); +int strerror_r (int, char *, size_t); +char *stpcpy(char *__restrict, const char *__restrict); +char *stpncpy(char *__restrict, const char *__restrict, size_t); +size_t strnlen (const char *, size_t); +char *strdup (const char *); +char *strndup (const char *, size_t); +char *strsignal(int); +char *strerror_l (int, locale_t); +int strcoll_l (const char *, const char *, locale_t); +size_t strxfrm_l (char *__restrict, const char *__restrict, size_t, locale_t); +void *memmem(const void *, size_t, const void *, size_t); +#endif + +#if defined(_XOPEN_SOURCE) || defined(_GNU_SOURCE) \ + || defined(_BSD_SOURCE) +void *memccpy (void *__restrict, const void *__restrict, int, size_t); +#endif + +#if defined(_GNU_SOURCE) || defined(_BSD_SOURCE) +char *strsep(char **, const char *); +size_t strlcat (char *, const char *, size_t); +size_t strlcpy (char *, const char *, size_t); +void explicit_bzero (void *, size_t); +#endif + +#ifdef _GNU_SOURCE +#define strdupa(x) strcpy(alloca(strlen(x)+1),x) +int strverscmp (const char *, const char *); +char *strchrnul(const char *, int); +char *strcasestr(const char *, const char *); +void *memrchr(const void *, int, size_t); +void *mempcpy(void *, const void *, size_t); +#endif + +/* musl internal symbols used across translation units */ +char *__strchrnul(const char *, int); +void *__memrchr(const void *, int, size_t); +char *__stpcpy(char *__restrict, const char *__restrict); +char *__stpncpy(char *__restrict, const char *__restrict, size_t); + +#ifdef __cplusplus +} +#endif + +#endif diff --git a/na/include/libc-shim/strings.h b/na/include/libc-shim/strings.h new file mode 100644 index 0000000..b7a5ea0 --- /dev/null +++ b/na/include/libc-shim/strings.h @@ -0,0 +1,40 @@ +#ifndef _STRINGS_H +#define _STRINGS_H + +#ifdef __cplusplus +extern "C" { +#endif + +#include <features.h> + +#define __NEED_size_t +#define __NEED_locale_t +#include <bits/alltypes.h> + +#if defined(_GNU_SOURCE) || defined(_BSD_SOURCE) || defined(_POSIX_SOURCE) \ + || (defined(_POSIX_C_SOURCE) && _POSIX_C_SOURCE+0 < 200809L) \ + || (defined(_XOPEN_SOURCE) && _XOPEN_SOURCE+0 < 700) +int bcmp (const void *, const void *, size_t); +void bcopy (const void *, void *, size_t); +void bzero (void *, size_t); +char *index (const char *, int); +char *rindex (const char *, int); +#endif + +#if defined(_XOPEN_SOURCE) || defined(_GNU_SOURCE) || defined(_BSD_SOURCE) +int ffs (int); +int ffsl (long); +int ffsll (long long); +#endif + +int strcasecmp (const char *, const char *); +int strncasecmp (const char *, const char *, size_t); + +int strcasecmp_l (const char *, const char *, locale_t); +int strncasecmp_l (const char *, const char *, size_t, locale_t); + +#ifdef __cplusplus +} +#endif + +#endif diff --git a/na/lib/string/COPYRIGHT b/na/lib/string/COPYRIGHT new file mode 100644 index 0000000..2f15edc --- /dev/null +++ b/na/lib/string/COPYRIGHT @@ -0,0 +1,193 @@ +musl as a whole is licensed under the following standard MIT license: + +---------------------------------------------------------------------- +Copyright © 2005-2020 Rich Felker, et al. + +Permission is hereby granted, free of charge, to any person obtaining +a copy of this software and associated documentation files (the +"Software"), to deal in the Software without restriction, including +without limitation the rights to use, copy, modify, merge, publish, +distribute, sublicense, and/or sell copies of the Software, and to +permit persons to whom the Software is furnished to do so, subject to +the following conditions: + +The above copyright notice and this permission notice shall be +included in all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, +TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE +SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. +---------------------------------------------------------------------- + +Authors/contributors include: + +A. Wilcox +Ada Worcester +Alex Dowad +Alex Suykov +Alexander Monakov +Andre McCurdy +Andrew Kelley +Anthony G. Basile +Aric Belsito +Arvid Picciani +Bartosz Brachaczek +Benjamin Peterson +Bobby Bingham +Boris Brezillon +Brent Cook +Chris Spiegel +Clément Vasseur +Daniel Micay +Daniel Sabogal +Daurnimator +David Carlier +David Edelsohn +Denys Vlasenko +Dmitry Ivanov +Dmitry V. Levin +Drew DeVault +Emil Renner Berthing +Fangrui Song +Felix Fietkau +Felix Janda +Gianluca Anzolin +Hauke Mehrtens +He X +Hiltjo Posthuma +Isaac Dunham +Jaydeep Patil +Jens Gustedt +Jeremy Huntwork +Jo-Philipp Wich +Joakim Sindholt +John Spencer +Julien Ramseier +Justin Cormack +Kaarle Ritvanen +Khem Raj +Kylie McClain +Leah Neukirchen +Luca Barbato +Luka Perkov +Lynn Ochs +M Farkas-Dyck (Strake) +Mahesh Bodapati +Markus Wichmann +Masanori Ogino +Michael Clark +Michael Forney +Mikhail Kremnyov +Natanael Copa +Nicholas J. Kain +orc +Pascal Cuoq +Patrick Oppenlander +Petr Hosek +Petr Skocik +Pierre Carrier +Reini Urban +Rich Felker +Richard Pennington +Ryan Fairfax +Samuel Holland +Segev Finer +Shiz +sin +Solar Designer +Stefan Kristiansson +Stefan O'Rear +Szabolcs Nagy +Timo Teräs +Trutz Behn +Will Dietz +William Haddon +William Pitcock + +Portions of this software are derived from third-party works licensed +under terms compatible with the above MIT license: + +The TRE regular expression implementation (src/regex/reg* and +src/regex/tre*) is Copyright © 2001-2008 Ville Laurikari and licensed +under a 2-clause BSD license (license text in the source files). The +included version has been heavily modified by Rich Felker in 2012, in +the interests of size, simplicity, and namespace cleanliness. + +Much of the math library code (src/math/* and src/complex/*) is +Copyright © 1993,2004 Sun Microsystems or +Copyright © 2003-2011 David Schultz or +Copyright © 2003-2009 Steven G. Kargl or +Copyright © 2003-2009 Bruce D. Evans or +Copyright © 2008 Stephen L. Moshier or +Copyright © 2017-2018 Arm Limited +and labelled as such in comments in the individual source files. All +have been licensed under extremely permissive terms. + +The ARM memcpy code (src/string/arm/memcpy.S) is Copyright © 2008 +The Android Open Source Project and is licensed under a two-clause BSD +license. It was taken from Bionic libc, used on Android. + +The AArch64 memcpy and memset code (src/string/aarch64/*) are +Copyright © 1999-2019, Arm Limited. + +The implementation of DES for crypt (src/crypt/crypt_des.c) is +Copyright © 1994 David Burren. It is licensed under a BSD license. + +The implementation of blowfish crypt (src/crypt/crypt_blowfish.c) was +originally written by Solar Designer and placed into the public +domain. The code also comes with a fallback permissive license for use +in jurisdictions that may not recognize the public domain. + +The smoothsort implementation (src/stdlib/qsort.c) is Copyright © 2011 +Lynn Ochs and is licensed under an MIT-style license. + +The x86_64 port was written by Nicholas J. Kain and is licensed under +the standard MIT terms. + +The mips and microblaze ports were originally written by Richard +Pennington for use in the ellcc project. The original code was adapted +by Rich Felker for build system and code conventions during upstream +integration. It is licensed under the standard MIT terms. + +The mips64 port was contributed by Imagination Technologies and is +licensed under the standard MIT terms. + +The powerpc port was also originally written by Richard Pennington, +and later supplemented and integrated by John Spencer. It is licensed +under the standard MIT terms. + +All other files which have no copyright comments are original works +produced specifically for use as part of this library, written either +by Rich Felker, the main author of the library, or by one or more +contibutors listed above. Details on authorship of individual files +can be found in the git version control history of the project. The +omission of copyright and license comments in each file is in the +interest of source tree size. + +In addition, permission is hereby granted for all public header files +(include/* and arch/*/bits/*) and crt files intended to be linked into +applications (crt/*, ldso/dlstart.c, and arch/*/crt_arch.h) to omit +the copyright notice and permission notice otherwise required by the +license, and to use these files without any requirement of +attribution. These files include substantial contributions from: + +Bobby Bingham +John Spencer +Nicholas J. Kain +Rich Felker +Richard Pennington +Stefan Kristiansson +Szabolcs Nagy + +all of whom have explicitly granted such permission. + +This file previously contained text expressing a belief that most of +the files covered by the above exception were sufficiently trivial not +to be subject to copyright, resulting in confusion over whether it +negated the permissions granted in the license. In the spirit of +permissive licensing, and of not having licensing issues being an +obstacle to adoption, that text has been removed. diff --git a/na/lib/string/aarch64/memcpy.S b/na/lib/string/aarch64/memcpy.S new file mode 100644 index 0000000..48bb8a8 --- /dev/null +++ b/na/lib/string/aarch64/memcpy.S @@ -0,0 +1,186 @@ +/* + * memcpy - copy memory area + * + * Copyright (c) 2012-2020, Arm Limited. + * SPDX-License-Identifier: MIT + */ + +/* Assumptions: + * + * ARMv8-a, AArch64, unaligned accesses. + * + */ + +#define dstin x0 +#define src x1 +#define count x2 +#define dst x3 +#define srcend x4 +#define dstend x5 +#define A_l x6 +#define A_lw w6 +#define A_h x7 +#define B_l x8 +#define B_lw w8 +#define B_h x9 +#define C_l x10 +#define C_lw w10 +#define C_h x11 +#define D_l x12 +#define D_h x13 +#define E_l x14 +#define E_h x15 +#define F_l x16 +#define F_h x17 +#define G_l count +#define G_h dst +#define H_l src +#define H_h srcend +#define tmp1 x14 + +/* This implementation of memcpy uses unaligned accesses and branchless + sequences to keep the code small, simple and improve performance. + + Copies are split into 3 main cases: small copies of up to 32 bytes, medium + copies of up to 128 bytes, and large copies. The overhead of the overlap + check is negligible since it is only required for large copies. + + Large copies use a software pipelined loop processing 64 bytes per iteration. + The destination pointer is 16-byte aligned to minimize unaligned accesses. + The loop tail is handled by always copying 64 bytes from the end. +*/ + +.global memcpy +.type memcpy,%function +memcpy: + add srcend, src, count + add dstend, dstin, count + cmp count, 128 + b.hi .Lcopy_long + cmp count, 32 + b.hi .Lcopy32_128 + + /* Small copies: 0..32 bytes. */ + cmp count, 16 + b.lo .Lcopy16 + ldp A_l, A_h, [src] + ldp D_l, D_h, [srcend, -16] + stp A_l, A_h, [dstin] + stp D_l, D_h, [dstend, -16] + ret + + /* Copy 8-15 bytes. */ +.Lcopy16: + tbz count, 3, .Lcopy8 + ldr A_l, [src] + ldr A_h, [srcend, -8] + str A_l, [dstin] + str A_h, [dstend, -8] + ret + + .p2align 3 + /* Copy 4-7 bytes. */ +.Lcopy8: + tbz count, 2, .Lcopy4 + ldr A_lw, [src] + ldr B_lw, [srcend, -4] + str A_lw, [dstin] + str B_lw, [dstend, -4] + ret + + /* Copy 0..3 bytes using a branchless sequence. */ +.Lcopy4: + cbz count, .Lcopy0 + lsr tmp1, count, 1 + ldrb A_lw, [src] + ldrb C_lw, [srcend, -1] + ldrb B_lw, [src, tmp1] + strb A_lw, [dstin] + strb B_lw, [dstin, tmp1] + strb C_lw, [dstend, -1] +.Lcopy0: + ret + + .p2align 4 + /* Medium copies: 33..128 bytes. */ +.Lcopy32_128: + ldp A_l, A_h, [src] + ldp B_l, B_h, [src, 16] + ldp C_l, C_h, [srcend, -32] + ldp D_l, D_h, [srcend, -16] + cmp count, 64 + b.hi .Lcopy128 + stp A_l, A_h, [dstin] + stp B_l, B_h, [dstin, 16] + stp C_l, C_h, [dstend, -32] + stp D_l, D_h, [dstend, -16] + ret + + .p2align 4 + /* Copy 65..128 bytes. */ +.Lcopy128: + ldp E_l, E_h, [src, 32] + ldp F_l, F_h, [src, 48] + cmp count, 96 + b.ls .Lcopy96 + ldp G_l, G_h, [srcend, -64] + ldp H_l, H_h, [srcend, -48] + stp G_l, G_h, [dstend, -64] + stp H_l, H_h, [dstend, -48] +.Lcopy96: + stp A_l, A_h, [dstin] + stp B_l, B_h, [dstin, 16] + stp E_l, E_h, [dstin, 32] + stp F_l, F_h, [dstin, 48] + stp C_l, C_h, [dstend, -32] + stp D_l, D_h, [dstend, -16] + ret + + .p2align 4 + /* Copy more than 128 bytes. */ +.Lcopy_long: + + /* Copy 16 bytes and then align dst to 16-byte alignment. */ + + ldp D_l, D_h, [src] + and tmp1, dstin, 15 + bic dst, dstin, 15 + sub src, src, tmp1 + add count, count, tmp1 /* Count is now 16 too large. */ + ldp A_l, A_h, [src, 16] + stp D_l, D_h, [dstin] + ldp B_l, B_h, [src, 32] + ldp C_l, C_h, [src, 48] + ldp D_l, D_h, [src, 64]! + subs count, count, 128 + 16 /* Test and readjust count. */ + b.ls .Lcopy64_from_end + +.Lloop64: + stp A_l, A_h, [dst, 16] + ldp A_l, A_h, [src, 16] + stp B_l, B_h, [dst, 32] + ldp B_l, B_h, [src, 32] + stp C_l, C_h, [dst, 48] + ldp C_l, C_h, [src, 48] + stp D_l, D_h, [dst, 64]! + ldp D_l, D_h, [src, 64]! + subs count, count, 64 + b.hi .Lloop64 + + /* Write the last iteration and copy 64 bytes from the end. */ +.Lcopy64_from_end: + ldp E_l, E_h, [srcend, -64] + stp A_l, A_h, [dst, 16] + ldp A_l, A_h, [srcend, -48] + stp B_l, B_h, [dst, 32] + ldp B_l, B_h, [srcend, -32] + stp C_l, C_h, [dst, 48] + ldp C_l, C_h, [srcend, -16] + stp D_l, D_h, [dst, 64] + stp E_l, E_h, [dstend, -64] + stp A_l, A_h, [dstend, -48] + stp B_l, B_h, [dstend, -32] + stp C_l, C_h, [dstend, -16] + ret + +.size memcpy,.-memcpy diff --git a/na/lib/string/aarch64/memset.S b/na/lib/string/aarch64/memset.S new file mode 100644 index 0000000..f0d29b7 --- /dev/null +++ b/na/lib/string/aarch64/memset.S @@ -0,0 +1,115 @@ +/* + * memset - fill memory with a constant byte + * + * Copyright (c) 2012-2020, Arm Limited. + * SPDX-License-Identifier: MIT + */ + +/* Assumptions: + * + * ARMv8-a, AArch64, Advanced SIMD, unaligned accesses. + * + */ + +#define dstin x0 +#define val x1 +#define valw w1 +#define count x2 +#define dst x3 +#define dstend x4 +#define zva_val x5 + +.global memset +.type memset,%function +memset: + + dup v0.16B, valw + add dstend, dstin, count + + cmp count, 96 + b.hi .Lset_long + cmp count, 16 + b.hs .Lset_medium + mov val, v0.D[0] + + /* Set 0..15 bytes. */ + tbz count, 3, 1f + str val, [dstin] + str val, [dstend, -8] + ret + nop +1: tbz count, 2, 2f + str valw, [dstin] + str valw, [dstend, -4] + ret +2: cbz count, 3f + strb valw, [dstin] + tbz count, 1, 3f + strh valw, [dstend, -2] +3: ret + + /* Set 17..96 bytes. */ +.Lset_medium: + str q0, [dstin] + tbnz count, 6, .Lset96 + str q0, [dstend, -16] + tbz count, 5, 1f + str q0, [dstin, 16] + str q0, [dstend, -32] +1: ret + + .p2align 4 + /* Set 64..96 bytes. Write 64 bytes from the start and + 32 bytes from the end. */ +.Lset96: + str q0, [dstin, 16] + stp q0, q0, [dstin, 32] + stp q0, q0, [dstend, -32] + ret + + .p2align 4 +.Lset_long: + and valw, valw, 255 + bic dst, dstin, 15 + str q0, [dstin] + cmp count, 160 + ccmp valw, 0, 0, hs + b.ne .Lno_zva + +#ifndef SKIP_ZVA_CHECK + mrs zva_val, dczid_el0 + and zva_val, zva_val, 31 + cmp zva_val, 4 /* ZVA size is 64 bytes. */ + b.ne .Lno_zva +#endif + str q0, [dst, 16] + stp q0, q0, [dst, 32] + bic dst, dst, 63 + sub count, dstend, dst /* Count is now 64 too large. */ + sub count, count, 128 /* Adjust count and bias for loop. */ + + .p2align 4 +.Lzva_loop: + add dst, dst, 64 + dc zva, dst + subs count, count, 64 + b.hi .Lzva_loop + stp q0, q0, [dstend, -64] + stp q0, q0, [dstend, -32] + ret + +.Lno_zva: + sub count, dstend, dst /* Count is 16 too large. */ + sub dst, dst, 16 /* Dst is biased by -32. */ + sub count, count, 64 + 16 /* Adjust count and bias for loop. */ +.Lno_zva_loop: + stp q0, q0, [dst, 32] + stp q0, q0, [dst, 64]! + subs count, count, 64 + b.hi .Lno_zva_loop + stp q0, q0, [dstend, -64] + stp q0, q0, [dstend, -32] + ret + +.size memset,.-memset + diff --git a/na/lib/string/arm/__aeabi_memcpy.s b/na/lib/string/arm/__aeabi_memcpy.s new file mode 100644 index 0000000..3a527e4 --- /dev/null +++ b/na/lib/string/arm/__aeabi_memcpy.s @@ -0,0 +1,45 @@ +.syntax unified + +.global __aeabi_memcpy8 +.global __aeabi_memcpy4 +.global __aeabi_memcpy +.global __aeabi_memmove8 +.global __aeabi_memmove4 +.global __aeabi_memmove + +.type __aeabi_memcpy8,%function +.type __aeabi_memcpy4,%function +.type __aeabi_memcpy,%function +.type __aeabi_memmove8,%function +.type __aeabi_memmove4,%function +.type __aeabi_memmove,%function + +__aeabi_memmove8: +__aeabi_memmove4: +__aeabi_memmove: + cmp r0, r1 + bls 3f + cmp r2, #0 + beq 2f + adds r0, r0, r2 + adds r2, r1, r2 +1: subs r2, r2, #1 + ldrb r3, [r2] + subs r0, r0, #1 + strb r3, [r0] + cmp r1, r2 + bne 1b +2: bx lr +__aeabi_memcpy8: +__aeabi_memcpy4: +__aeabi_memcpy: +3: cmp r2, #0 + beq 2f + adds r2, r1, r2 +1: ldrb r3, [r1] + adds r1, r1, #1 + strb r3, [r0] + adds r0, r0, #1 + cmp r1, r2 + bne 1b +2: bx lr diff --git a/na/lib/string/arm/__aeabi_memset.s b/na/lib/string/arm/__aeabi_memset.s new file mode 100644 index 0000000..f9f6058 --- /dev/null +++ b/na/lib/string/arm/__aeabi_memset.s @@ -0,0 +1,31 @@ +.syntax unified + +.global __aeabi_memclr8 +.global __aeabi_memclr4 +.global __aeabi_memclr +.global __aeabi_memset8 +.global __aeabi_memset4 +.global __aeabi_memset + +.type __aeabi_memclr8,%function +.type __aeabi_memclr4,%function +.type __aeabi_memclr,%function +.type __aeabi_memset8,%function +.type __aeabi_memset4,%function +.type __aeabi_memset,%function + +__aeabi_memclr8: +__aeabi_memclr4: +__aeabi_memclr: + movs r2, #0 +__aeabi_memset8: +__aeabi_memset4: +__aeabi_memset: + cmp r1, #0 + beq 2f + adds r1, r0, r1 +1: strb r2, [r0] + adds r0, r0, #1 + cmp r1, r0 + bne 1b +2: bx lr diff --git a/na/lib/string/arm/memcpy.S b/na/lib/string/arm/memcpy.S new file mode 100644 index 0000000..869e344 --- /dev/null +++ b/na/lib/string/arm/memcpy.S @@ -0,0 +1,479 @@ +/* + * Copyright (C) 2008 The Android Open Source Project + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS + * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED + * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT + * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + + +/* + * Optimized memcpy() for ARM. + * + * note that memcpy() always returns the destination pointer, + * so we have to preserve R0. + */ + +/* + * This file has been modified from the original for use in musl libc. + * The main changes are: addition of .type memcpy,%function to make the + * code safely callable from thumb mode, adjusting the return + * instructions to be compatible with pre-thumb ARM cpus, removal of + * prefetch code that is not compatible with older cpus and support for + * building as thumb 2 and big-endian. + */ + +.syntax unified + +.global memcpy +.type memcpy,%function +memcpy: + /* The stack must always be 64-bits aligned to be compliant with the + * ARM ABI. Since we have to save R0, we might as well save R4 + * which we can use for better pipelining of the reads below + */ + .fnstart + .save {r0, r4, lr} + stmfd sp!, {r0, r4, lr} + /* Making room for r5-r11 which will be spilled later */ + .pad #28 + sub sp, sp, #28 + + /* it simplifies things to take care of len<4 early */ + cmp r2, #4 + blo copy_last_3_and_return + + /* compute the offset to align the source + * offset = (4-(src&3))&3 = -src & 3 + */ + rsb r3, r1, #0 + ands r3, r3, #3 + beq src_aligned + + /* align source to 32 bits. We need to insert 2 instructions between + * a ldr[b|h] and str[b|h] because byte and half-word instructions + * stall 2 cycles. + */ + movs r12, r3, lsl #31 + sub r2, r2, r3 /* we know that r3 <= r2 because r2 >= 4 */ + ldrbmi r3, [r1], #1 + ldrbcs r4, [r1], #1 + ldrbcs r12,[r1], #1 + strbmi r3, [r0], #1 + strbcs r4, [r0], #1 + strbcs r12,[r0], #1 + +src_aligned: + + /* see if src and dst are aligned together (congruent) */ + eor r12, r0, r1 + tst r12, #3 + bne non_congruent + + /* Use post-incriment mode for stm to spill r5-r11 to reserved stack + * frame. Don't update sp. + */ + stmea sp, {r5-r11} + + /* align the destination to a cache-line */ + rsb r3, r0, #0 + ands r3, r3, #0x1C + beq congruent_aligned32 + cmp r3, r2 + andhi r3, r2, #0x1C + + /* conditionnaly copies 0 to 7 words (length in r3) */ + movs r12, r3, lsl #28 + ldmcs r1!, {r4, r5, r6, r7} /* 16 bytes */ + ldmmi r1!, {r8, r9} /* 8 bytes */ + stmcs r0!, {r4, r5, r6, r7} + stmmi r0!, {r8, r9} + tst r3, #0x4 + ldrne r10,[r1], #4 /* 4 bytes */ + strne r10,[r0], #4 + sub r2, r2, r3 + +congruent_aligned32: + /* + * here source is aligned to 32 bytes. + */ + +cached_aligned32: + subs r2, r2, #32 + blo less_than_32_left + + /* + * We preload a cache-line up to 64 bytes ahead. On the 926, this will + * stall only until the requested world is fetched, but the linefill + * continues in the the background. + * While the linefill is going, we write our previous cache-line + * into the write-buffer (which should have some free space). + * When the linefill is done, the writebuffer will + * start dumping its content into memory + * + * While all this is going, we then load a full cache line into + * 8 registers, this cache line should be in the cache by now + * (or partly in the cache). + * + * This code should work well regardless of the source/dest alignment. + * + */ + + /* Align the preload register to a cache-line because the cpu does + * "critical word first" (the first word requested is loaded first). + */ + @ bic r12, r1, #0x1F + @ add r12, r12, #64 + +1: ldmia r1!, { r4-r11 } + subs r2, r2, #32 + + /* + * NOTE: if r12 is more than 64 ahead of r1, the following ldrhi + * for ARM9 preload will not be safely guarded by the preceding subs. + * When it is safely guarded the only possibility to have SIGSEGV here + * is because the caller overstates the length. + */ + @ ldrhi r3, [r12], #32 /* cheap ARM9 preload */ + stmia r0!, { r4-r11 } + bhs 1b + + add r2, r2, #32 + +less_than_32_left: + /* + * less than 32 bytes left at this point (length in r2) + */ + + /* skip all this if there is nothing to do, which should + * be a common case (if not executed the code below takes + * about 16 cycles) + */ + tst r2, #0x1F + beq 1f + + /* conditionnaly copies 0 to 31 bytes */ + movs r12, r2, lsl #28 + ldmcs r1!, {r4, r5, r6, r7} /* 16 bytes */ + ldmmi r1!, {r8, r9} /* 8 bytes */ + stmcs r0!, {r4, r5, r6, r7} + stmmi r0!, {r8, r9} + movs r12, r2, lsl #30 + ldrcs r3, [r1], #4 /* 4 bytes */ + ldrhmi r4, [r1], #2 /* 2 bytes */ + strcs r3, [r0], #4 + strhmi r4, [r0], #2 + tst r2, #0x1 + ldrbne r3, [r1] /* last byte */ + strbne r3, [r0] + + /* we're done! restore everything and return */ +1: ldmfd sp!, {r5-r11} + ldmfd sp!, {r0, r4, lr} + bx lr + + /********************************************************************/ + +non_congruent: + /* + * here source is aligned to 4 bytes + * but destination is not. + * + * in the code below r2 is the number of bytes read + * (the number of bytes written is always smaller, because we have + * partial words in the shift queue) + */ + cmp r2, #4 + blo copy_last_3_and_return + + /* Use post-incriment mode for stm to spill r5-r11 to reserved stack + * frame. Don't update sp. + */ + stmea sp, {r5-r11} + + /* compute shifts needed to align src to dest */ + rsb r5, r0, #0 + and r5, r5, #3 /* r5 = # bytes in partial words */ + mov r12, r5, lsl #3 /* r12 = right */ + rsb lr, r12, #32 /* lr = left */ + + /* read the first word */ + ldr r3, [r1], #4 + sub r2, r2, #4 + + /* write a partial word (0 to 3 bytes), such that destination + * becomes aligned to 32 bits (r5 = nb of words to copy for alignment) + */ + movs r5, r5, lsl #31 + +#if __ARMEB__ + movmi r3, r3, ror #24 + strbmi r3, [r0], #1 + movcs r3, r3, ror #24 + strbcs r3, [r0], #1 + movcs r3, r3, ror #24 + strbcs r3, [r0], #1 +#else + strbmi r3, [r0], #1 + movmi r3, r3, lsr #8 + strbcs r3, [r0], #1 + movcs r3, r3, lsr #8 + strbcs r3, [r0], #1 + movcs r3, r3, lsr #8 +#endif + + cmp r2, #4 + blo partial_word_tail + +#if __ARMEB__ + mov r3, r3, lsr r12 + mov r3, r3, lsl r12 +#endif + + /* Align destination to 32 bytes (cache line boundary) */ +1: tst r0, #0x1c + beq 2f + ldr r5, [r1], #4 + sub r2, r2, #4 +#if __ARMEB__ + mov r4, r5, lsr lr + orr r4, r4, r3 + mov r3, r5, lsl r12 +#else + mov r4, r5, lsl lr + orr r4, r4, r3 + mov r3, r5, lsr r12 +#endif + str r4, [r0], #4 + cmp r2, #4 + bhs 1b + blo partial_word_tail + + /* copy 32 bytes at a time */ +2: subs r2, r2, #32 + blo less_than_thirtytwo + + /* Use immediate mode for the shifts, because there is an extra cycle + * for register shifts, which could account for up to 50% of + * performance hit. + */ + + cmp r12, #24 + beq loop24 + cmp r12, #8 + beq loop8 + +loop16: + ldr r12, [r1], #4 +1: mov r4, r12 + ldmia r1!, { r5,r6,r7, r8,r9,r10,r11} + subs r2, r2, #32 + ldrhs r12, [r1], #4 +#if __ARMEB__ + orr r3, r3, r4, lsr #16 + mov r4, r4, lsl #16 + orr r4, r4, r5, lsr #16 + mov r5, r5, lsl #16 + orr r5, r5, r6, lsr #16 + mov r6, r6, lsl #16 + orr r6, r6, r7, lsr #16 + mov r7, r7, lsl #16 + orr r7, r7, r8, lsr #16 + mov r8, r8, lsl #16 + orr r8, r8, r9, lsr #16 + mov r9, r9, lsl #16 + orr r9, r9, r10, lsr #16 + mov r10, r10, lsl #16 + orr r10, r10, r11, lsr #16 + stmia r0!, {r3,r4,r5,r6, r7,r8,r9,r10} + mov r3, r11, lsl #16 +#else + orr r3, r3, r4, lsl #16 + mov r4, r4, lsr #16 + orr r4, r4, r5, lsl #16 + mov r5, r5, lsr #16 + orr r5, r5, r6, lsl #16 + mov r6, r6, lsr #16 + orr r6, r6, r7, lsl #16 + mov r7, r7, lsr #16 + orr r7, r7, r8, lsl #16 + mov r8, r8, lsr #16 + orr r8, r8, r9, lsl #16 + mov r9, r9, lsr #16 + orr r9, r9, r10, lsl #16 + mov r10, r10, lsr #16 + orr r10, r10, r11, lsl #16 + stmia r0!, {r3,r4,r5,r6, r7,r8,r9,r10} + mov r3, r11, lsr #16 +#endif + bhs 1b + b less_than_thirtytwo + +loop8: + ldr r12, [r1], #4 +1: mov r4, r12 + ldmia r1!, { r5,r6,r7, r8,r9,r10,r11} + subs r2, r2, #32 + ldrhs r12, [r1], #4 +#if __ARMEB__ + orr r3, r3, r4, lsr #24 + mov r4, r4, lsl #8 + orr r4, r4, r5, lsr #24 + mov r5, r5, lsl #8 + orr r5, r5, r6, lsr #24 + mov r6, r6, lsl #8 + orr r6, r6, r7, lsr #24 + mov r7, r7, lsl #8 + orr r7, r7, r8, lsr #24 + mov r8, r8, lsl #8 + orr r8, r8, r9, lsr #24 + mov r9, r9, lsl #8 + orr r9, r9, r10, lsr #24 + mov r10, r10, lsl #8 + orr r10, r10, r11, lsr #24 + stmia r0!, {r3,r4,r5,r6, r7,r8,r9,r10} + mov r3, r11, lsl #8 +#else + orr r3, r3, r4, lsl #24 + mov r4, r4, lsr #8 + orr r4, r4, r5, lsl #24 + mov r5, r5, lsr #8 + orr r5, r5, r6, lsl #24 + mov r6, r6, lsr #8 + orr r6, r6, r7, lsl #24 + mov r7, r7, lsr #8 + orr r7, r7, r8, lsl #24 + mov r8, r8, lsr #8 + orr r8, r8, r9, lsl #24 + mov r9, r9, lsr #8 + orr r9, r9, r10, lsl #24 + mov r10, r10, lsr #8 + orr r10, r10, r11, lsl #24 + stmia r0!, {r3,r4,r5,r6, r7,r8,r9,r10} + mov r3, r11, lsr #8 +#endif + bhs 1b + b less_than_thirtytwo + +loop24: + ldr r12, [r1], #4 +1: mov r4, r12 + ldmia r1!, { r5,r6,r7, r8,r9,r10,r11} + subs r2, r2, #32 + ldrhs r12, [r1], #4 +#if __ARMEB__ + orr r3, r3, r4, lsr #8 + mov r4, r4, lsl #24 + orr r4, r4, r5, lsr #8 + mov r5, r5, lsl #24 + orr r5, r5, r6, lsr #8 + mov r6, r6, lsl #24 + orr r6, r6, r7, lsr #8 + mov r7, r7, lsl #24 + orr r7, r7, r8, lsr #8 + mov r8, r8, lsl #24 + orr r8, r8, r9, lsr #8 + mov r9, r9, lsl #24 + orr r9, r9, r10, lsr #8 + mov r10, r10, lsl #24 + orr r10, r10, r11, lsr #8 + stmia r0!, {r3,r4,r5,r6, r7,r8,r9,r10} + mov r3, r11, lsl #24 +#else + orr r3, r3, r4, lsl #8 + mov r4, r4, lsr #24 + orr r4, r4, r5, lsl #8 + mov r5, r5, lsr #24 + orr r5, r5, r6, lsl #8 + mov r6, r6, lsr #24 + orr r6, r6, r7, lsl #8 + mov r7, r7, lsr #24 + orr r7, r7, r8, lsl #8 + mov r8, r8, lsr #24 + orr r8, r8, r9, lsl #8 + mov r9, r9, lsr #24 + orr r9, r9, r10, lsl #8 + mov r10, r10, lsr #24 + orr r10, r10, r11, lsl #8 + stmia r0!, {r3,r4,r5,r6, r7,r8,r9,r10} + mov r3, r11, lsr #24 +#endif + bhs 1b + +less_than_thirtytwo: + /* copy the last 0 to 31 bytes of the source */ + rsb r12, lr, #32 /* we corrupted r12, recompute it */ + add r2, r2, #32 + cmp r2, #4 + blo partial_word_tail + +1: ldr r5, [r1], #4 + sub r2, r2, #4 +#if __ARMEB__ + mov r4, r5, lsr lr + orr r4, r4, r3 + mov r3, r5, lsl r12 +#else + mov r4, r5, lsl lr + orr r4, r4, r3 + mov r3, r5, lsr r12 +#endif + str r4, [r0], #4 + cmp r2, #4 + bhs 1b + +partial_word_tail: + /* we have a partial word in the input buffer */ + movs r5, lr, lsl #(31-3) +#if __ARMEB__ + movmi r3, r3, ror #24 + strbmi r3, [r0], #1 + movcs r3, r3, ror #24 + strbcs r3, [r0], #1 + movcs r3, r3, ror #24 + strbcs r3, [r0], #1 +#else + strbmi r3, [r0], #1 + movmi r3, r3, lsr #8 + strbcs r3, [r0], #1 + movcs r3, r3, lsr #8 + strbcs r3, [r0], #1 +#endif + + /* Refill spilled registers from the stack. Don't update sp. */ + ldmfd sp, {r5-r11} + +copy_last_3_and_return: + movs r2, r2, lsl #31 /* copy remaining 0, 1, 2 or 3 bytes */ + ldrbmi r2, [r1], #1 + ldrbcs r3, [r1], #1 + ldrbcs r12,[r1] + strbmi r2, [r0], #1 + strbcs r3, [r0], #1 + strbcs r12,[r0] + + /* we're done! restore sp and spilled registers and return */ + add sp, sp, #28 + ldmfd sp!, {r0, r4, lr} + bx lr + diff --git a/na/lib/string/bcmp.c b/na/lib/string/bcmp.c new file mode 100644 index 0000000..d4c093f --- /dev/null +++ b/na/lib/string/bcmp.c @@ -0,0 +1,11 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#define _BSD_SOURCE +#include <string.h> +#include <strings.h> + +int bcmp(const void *s1, const void *s2, size_t n) +{ + return memcmp(s1, s2, n); +} diff --git a/na/lib/string/bcopy.c b/na/lib/string/bcopy.c new file mode 100644 index 0000000..25e98a2 --- /dev/null +++ b/na/lib/string/bcopy.c @@ -0,0 +1,11 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#define _BSD_SOURCE +#include <string.h> +#include <strings.h> + +void bcopy(const void *s1, void *s2, size_t n) +{ + memmove(s2, s1, n); +} diff --git a/na/lib/string/bzero.c b/na/lib/string/bzero.c new file mode 100644 index 0000000..08f1398 --- /dev/null +++ b/na/lib/string/bzero.c @@ -0,0 +1,11 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#define _BSD_SOURCE +#include <string.h> +#include <strings.h> + +void bzero(void *s, size_t n) +{ + memset(s, 0, n); +} diff --git a/na/lib/string/explicit_bzero.c b/na/lib/string/explicit_bzero.c new file mode 100644 index 0000000..c94f25f --- /dev/null +++ b/na/lib/string/explicit_bzero.c @@ -0,0 +1,11 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#define _BSD_SOURCE +#include <string.h> + +void explicit_bzero(void *d, size_t n) +{ + d = memset(d, 0, n); + __asm__ __volatile__ ("" : : "r"(d) : "memory"); +} diff --git a/na/lib/string/i386/memcpy.s b/na/lib/string/i386/memcpy.s new file mode 100644 index 0000000..0608dd8 --- /dev/null +++ b/na/lib/string/i386/memcpy.s @@ -0,0 +1,32 @@ +.global memcpy +.global __memcpy_fwd +.hidden __memcpy_fwd +.type memcpy,@function +memcpy: +__memcpy_fwd: + push %esi + push %edi + mov 12(%esp),%edi + mov 16(%esp),%esi + mov 20(%esp),%ecx + mov %edi,%eax + cmp $4,%ecx + jc 1f + test $3,%edi + jz 1f +2: movsb + dec %ecx + test $3,%edi + jnz 2b +1: mov %ecx,%edx + shr $2,%ecx + rep + movsl + and $3,%edx + jz 1f +2: movsb + dec %edx + jnz 2b +1: pop %edi + pop %esi + ret diff --git a/na/lib/string/i386/memmove.s b/na/lib/string/i386/memmove.s new file mode 100644 index 0000000..2a6a504 --- /dev/null +++ b/na/lib/string/i386/memmove.s @@ -0,0 +1,22 @@ +.global memmove +.type memmove,@function +memmove: + mov 4(%esp),%eax + sub 8(%esp),%eax + cmp 12(%esp),%eax +.hidden __memcpy_fwd + jae __memcpy_fwd + push %esi + push %edi + mov 12(%esp),%edi + mov 16(%esp),%esi + mov 20(%esp),%ecx + lea -1(%edi,%ecx),%edi + lea -1(%esi,%ecx),%esi + std + rep movsb + cld + lea 1(%edi),%eax + pop %edi + pop %esi + ret diff --git a/na/lib/string/i386/memset.s b/na/lib/string/i386/memset.s new file mode 100644 index 0000000..d00422c --- /dev/null +++ b/na/lib/string/i386/memset.s @@ -0,0 +1,76 @@ +.global memset +.type memset,@function +memset: + mov 12(%esp),%ecx + cmp $62,%ecx + ja 2f + + mov 8(%esp),%dl + mov 4(%esp),%eax + test %ecx,%ecx + jz 1f + + mov %dl,%dh + + mov %dl,(%eax) + mov %dl,-1(%eax,%ecx) + cmp $2,%ecx + jbe 1f + + mov %dx,1(%eax) + mov %dx,(-1-2)(%eax,%ecx) + cmp $6,%ecx + jbe 1f + + shl $16,%edx + mov 8(%esp),%dl + mov 8(%esp),%dh + + mov %edx,(1+2)(%eax) + mov %edx,(-1-2-4)(%eax,%ecx) + cmp $14,%ecx + jbe 1f + + mov %edx,(1+2+4)(%eax) + mov %edx,(1+2+4+4)(%eax) + mov %edx,(-1-2-4-8)(%eax,%ecx) + mov %edx,(-1-2-4-4)(%eax,%ecx) + cmp $30,%ecx + jbe 1f + + mov %edx,(1+2+4+8)(%eax) + mov %edx,(1+2+4+8+4)(%eax) + mov %edx,(1+2+4+8+8)(%eax) + mov %edx,(1+2+4+8+12)(%eax) + mov %edx,(-1-2-4-8-16)(%eax,%ecx) + mov %edx,(-1-2-4-8-12)(%eax,%ecx) + mov %edx,(-1-2-4-8-8)(%eax,%ecx) + mov %edx,(-1-2-4-8-4)(%eax,%ecx) + +1: ret + +2: movzbl 8(%esp),%eax + mov %edi,12(%esp) + imul $0x1010101,%eax + mov 4(%esp),%edi + test $15,%edi + mov %eax,-4(%edi,%ecx) + jnz 2f + +1: shr $2, %ecx + rep + stosl + mov 4(%esp),%eax + mov 12(%esp),%edi + ret + +2: xor %edx,%edx + sub %edi,%edx + and $15,%edx + mov %eax,(%edi) + mov %eax,4(%edi) + mov %eax,8(%edi) + mov %eax,12(%edi) + sub %edx,%ecx + add %edx,%edi + jmp 1b diff --git a/na/lib/string/index.c b/na/lib/string/index.c new file mode 100644 index 0000000..8f6894c --- /dev/null +++ b/na/lib/string/index.c @@ -0,0 +1,11 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#define _BSD_SOURCE +#include <string.h> +#include <strings.h> + +char *index(const char *s, int c) +{ + return strchr(s, c); +} diff --git a/na/lib/string/memccpy.c b/na/lib/string/memccpy.c new file mode 100644 index 0000000..99f146f --- /dev/null +++ b/na/lib/string/memccpy.c @@ -0,0 +1,37 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> +#include <stdint.h> +#include <limits.h> + +#define ALIGN (sizeof(size_t)-1) +#define ONES ((size_t)-1/UCHAR_MAX) +#define HIGHS (ONES * (UCHAR_MAX/2+1)) +#define HASZERO(x) ((x)-ONES & ~(x) & HIGHS) + +void *memccpy(void *restrict dest, const void *restrict src, int c, size_t n) +{ + unsigned char *d = dest; + const unsigned char *s = src; + + c = (unsigned char)c; +#ifdef __GNUC__ + typedef size_t __attribute__((__may_alias__)) word; + word *wd; + const word *ws; + if (((uintptr_t)s & ALIGN) == ((uintptr_t)d & ALIGN)) { + for (; ((uintptr_t)s & ALIGN) && n && (*d=*s)!=c; n--, s++, d++); + if ((uintptr_t)s & ALIGN) goto tail; + size_t k = ONES * c; + wd=(void *)d; ws=(const void *)s; + for (; n>=sizeof(size_t) && !HASZERO(*ws^k); + n-=sizeof(size_t), ws++, wd++) *wd = *ws; + d=(void *)wd; s=(const void *)ws; + } +#endif + for (; n && (*d=*s)!=c; n--, s++, d++); +tail: + if (n) return d+1; + return 0; +} diff --git a/na/lib/string/memchr.c b/na/lib/string/memchr.c new file mode 100644 index 0000000..d0f670f --- /dev/null +++ b/na/lib/string/memchr.c @@ -0,0 +1,30 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> +#include <stdint.h> +#include <limits.h> + +#define SS (sizeof(size_t)) +#define ALIGN (sizeof(size_t)-1) +#define ONES ((size_t)-1/UCHAR_MAX) +#define HIGHS (ONES * (UCHAR_MAX/2+1)) +#define HASZERO(x) ((x)-ONES & ~(x) & HIGHS) + +void *memchr(const void *src, int c, size_t n) +{ + const unsigned char *s = src; + c = (unsigned char)c; +#ifdef __GNUC__ + for (; ((uintptr_t)s & ALIGN) && n && *s != c; s++, n--); + if (n && *s != c) { + typedef size_t __attribute__((__may_alias__)) word; + const word *w; + size_t k = ONES * c; + for (w = (const void *)s; n>=SS && !HASZERO(*w^k); w++, n-=SS); + s = (const void *)w; + } +#endif + for (; n && *s != c; s++, n--); + return n ? (void *)s : 0; +} diff --git a/na/lib/string/memcmp.c b/na/lib/string/memcmp.c new file mode 100644 index 0000000..15606f4 --- /dev/null +++ b/na/lib/string/memcmp.c @@ -0,0 +1,11 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +int memcmp(const void *vl, const void *vr, size_t n) +{ + const unsigned char *l=vl, *r=vr; + for (; n && *l == *r; n--, l++, r++); + return n ? *l-*r : 0; +} diff --git a/na/lib/string/memcpy.c b/na/lib/string/memcpy.c new file mode 100644 index 0000000..de26a00 --- /dev/null +++ b/na/lib/string/memcpy.c @@ -0,0 +1,127 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> +#include <stdint.h> +#include <endian.h> + +void *memcpy(void *restrict dest, const void *restrict src, size_t n) +{ + unsigned char *d = dest; + const unsigned char *s = src; + +#ifdef __GNUC__ + +#if __BYTE_ORDER == __LITTLE_ENDIAN +#define LS >> +#define RS << +#else +#define LS << +#define RS >> +#endif + + typedef uint32_t __attribute__((__may_alias__)) u32; + uint32_t w, x; + + for (; (uintptr_t)s % 4 && n; n--) *d++ = *s++; + + if ((uintptr_t)d % 4 == 0) { + for (; n>=16; s+=16, d+=16, n-=16) { + *(u32 *)(d+0) = *(u32 *)(s+0); + *(u32 *)(d+4) = *(u32 *)(s+4); + *(u32 *)(d+8) = *(u32 *)(s+8); + *(u32 *)(d+12) = *(u32 *)(s+12); + } + if (n&8) { + *(u32 *)(d+0) = *(u32 *)(s+0); + *(u32 *)(d+4) = *(u32 *)(s+4); + d += 8; s += 8; + } + if (n&4) { + *(u32 *)(d+0) = *(u32 *)(s+0); + d += 4; s += 4; + } + if (n&2) { + *d++ = *s++; *d++ = *s++; + } + if (n&1) { + *d = *s; + } + return dest; + } + + if (n >= 32) switch ((uintptr_t)d % 4) { + case 1: + w = *(u32 *)s; + *d++ = *s++; + *d++ = *s++; + *d++ = *s++; + n -= 3; + for (; n>=17; s+=16, d+=16, n-=16) { + x = *(u32 *)(s+1); + *(u32 *)(d+0) = (w LS 24) | (x RS 8); + w = *(u32 *)(s+5); + *(u32 *)(d+4) = (x LS 24) | (w RS 8); + x = *(u32 *)(s+9); + *(u32 *)(d+8) = (w LS 24) | (x RS 8); + w = *(u32 *)(s+13); + *(u32 *)(d+12) = (x LS 24) | (w RS 8); + } + break; + case 2: + w = *(u32 *)s; + *d++ = *s++; + *d++ = *s++; + n -= 2; + for (; n>=18; s+=16, d+=16, n-=16) { + x = *(u32 *)(s+2); + *(u32 *)(d+0) = (w LS 16) | (x RS 16); + w = *(u32 *)(s+6); + *(u32 *)(d+4) = (x LS 16) | (w RS 16); + x = *(u32 *)(s+10); + *(u32 *)(d+8) = (w LS 16) | (x RS 16); + w = *(u32 *)(s+14); + *(u32 *)(d+12) = (x LS 16) | (w RS 16); + } + break; + case 3: + w = *(u32 *)s; + *d++ = *s++; + n -= 1; + for (; n>=19; s+=16, d+=16, n-=16) { + x = *(u32 *)(s+3); + *(u32 *)(d+0) = (w LS 8) | (x RS 24); + w = *(u32 *)(s+7); + *(u32 *)(d+4) = (x LS 8) | (w RS 24); + x = *(u32 *)(s+11); + *(u32 *)(d+8) = (w LS 8) | (x RS 24); + w = *(u32 *)(s+15); + *(u32 *)(d+12) = (x LS 8) | (w RS 24); + } + break; + } + if (n&16) { + *d++ = *s++; *d++ = *s++; *d++ = *s++; *d++ = *s++; + *d++ = *s++; *d++ = *s++; *d++ = *s++; *d++ = *s++; + *d++ = *s++; *d++ = *s++; *d++ = *s++; *d++ = *s++; + *d++ = *s++; *d++ = *s++; *d++ = *s++; *d++ = *s++; + } + if (n&8) { + *d++ = *s++; *d++ = *s++; *d++ = *s++; *d++ = *s++; + *d++ = *s++; *d++ = *s++; *d++ = *s++; *d++ = *s++; + } + if (n&4) { + *d++ = *s++; *d++ = *s++; *d++ = *s++; *d++ = *s++; + } + if (n&2) { + *d++ = *s++; *d++ = *s++; + } + if (n&1) { + *d = *s; + } + return dest; +#endif + + for (; n; n--) *d++ = *s++; + return dest; +} diff --git a/na/lib/string/memmem.c b/na/lib/string/memmem.c new file mode 100644 index 0000000..cfd23bb --- /dev/null +++ b/na/lib/string/memmem.c @@ -0,0 +1,152 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#define _GNU_SOURCE +#include <string.h> +#include <stdint.h> + +static char *twobyte_memmem(const unsigned char *h, size_t k, const unsigned char *n) +{ + uint16_t nw = n[0]<<8 | n[1], hw = h[0]<<8 | h[1]; + for (h+=2, k-=2; k; k--, hw = hw<<8 | *h++) + if (hw == nw) return (char *)h-2; + return hw == nw ? (char *)h-2 : 0; +} + +static char *threebyte_memmem(const unsigned char *h, size_t k, const unsigned char *n) +{ + uint32_t nw = (uint32_t)n[0]<<24 | n[1]<<16 | n[2]<<8; + uint32_t hw = (uint32_t)h[0]<<24 | h[1]<<16 | h[2]<<8; + for (h+=3, k-=3; k; k--, hw = (hw|*h++)<<8) + if (hw == nw) return (char *)h-3; + return hw == nw ? (char *)h-3 : 0; +} + +static char *fourbyte_memmem(const unsigned char *h, size_t k, const unsigned char *n) +{ + uint32_t nw = (uint32_t)n[0]<<24 | n[1]<<16 | n[2]<<8 | n[3]; + uint32_t hw = (uint32_t)h[0]<<24 | h[1]<<16 | h[2]<<8 | h[3]; + for (h+=4, k-=4; k; k--, hw = hw<<8 | *h++) + if (hw == nw) return (char *)h-4; + return hw == nw ? (char *)h-4 : 0; +} + +#define MAX(a,b) ((a)>(b)?(a):(b)) +#define MIN(a,b) ((a)<(b)?(a):(b)) + +#define BITOP(a,b,op) \ + ((a)[(size_t)(b)/(8*sizeof *(a))] op (size_t)1<<((size_t)(b)%(8*sizeof *(a)))) + +static char *twoway_memmem(const unsigned char *h, const unsigned char *z, const unsigned char *n, size_t l) +{ + size_t i, ip, jp, k, p, ms, p0, mem, mem0; + size_t byteset[32 / sizeof(size_t)] = { 0 }; + size_t shift[256]; + + /* Computing length of needle and fill shift table */ + for (i=0; i<l; i++) + BITOP(byteset, n[i], |=), shift[n[i]] = i+1; + + /* Compute maximal suffix */ + ip = -1; jp = 0; k = p = 1; + while (jp+k<l) { + if (n[ip+k] == n[jp+k]) { + if (k == p) { + jp += p; + k = 1; + } else k++; + } else if (n[ip+k] > n[jp+k]) { + jp += k; + k = 1; + p = jp - ip; + } else { + ip = jp++; + k = p = 1; + } + } + ms = ip; + p0 = p; + + /* And with the opposite comparison */ + ip = -1; jp = 0; k = p = 1; + while (jp+k<l) { + if (n[ip+k] == n[jp+k]) { + if (k == p) { + jp += p; + k = 1; + } else k++; + } else if (n[ip+k] < n[jp+k]) { + jp += k; + k = 1; + p = jp - ip; + } else { + ip = jp++; + k = p = 1; + } + } + if (ip+1 > ms+1) ms = ip; + else p = p0; + + /* Periodic needle? */ + if (memcmp(n, n+p, ms+1)) { + mem0 = 0; + p = MAX(ms, l-ms-1) + 1; + } else mem0 = l-p; + mem = 0; + + /* Search loop */ + for (;;) { + /* If remainder of haystack is shorter than needle, done */ + if (z-h < l) return 0; + + /* Check last byte first; advance by shift on mismatch */ + if (BITOP(byteset, h[l-1], &)) { + k = l-shift[h[l-1]]; + if (k) { + if (k < mem) k = mem; + h += k; + mem = 0; + continue; + } + } else { + h += l; + mem = 0; + continue; + } + + /* Compare right half */ + for (k=MAX(ms+1,mem); k<l && n[k] == h[k]; k++); + if (k < l) { + h += k-ms; + mem = 0; + continue; + } + /* Compare left half */ + for (k=ms+1; k>mem && n[k-1] == h[k-1]; k--); + if (k <= mem) return (char *)h; + h += p; + mem = mem0; + } +} + +void *memmem(const void *h0, size_t k, const void *n0, size_t l) +{ + const unsigned char *h = h0, *n = n0; + + /* Return immediately on empty needle */ + if (!l) return (void *)h; + + /* Return immediately when needle is longer than haystack */ + if (k<l) return 0; + + /* Use faster algorithms for short needles */ + h = memchr(h0, *n, k); + if (!h || l==1) return (void *)h; + k -= h - (const unsigned char *)h0; + if (k<l) return 0; + if (l==2) return twobyte_memmem(h, k, n); + if (l==3) return threebyte_memmem(h, k, n); + if (l==4) return fourbyte_memmem(h, k, n); + + return twoway_memmem(h, h+k, n, l); +} diff --git a/na/lib/string/memmove.c b/na/lib/string/memmove.c new file mode 100644 index 0000000..56e1a81 --- /dev/null +++ b/na/lib/string/memmove.c @@ -0,0 +1,45 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> +#include <stdint.h> + +#ifdef __GNUC__ +typedef __attribute__((__may_alias__)) size_t WT; +#define WS (sizeof(WT)) +#endif + +void *memmove(void *dest, const void *src, size_t n) +{ + char *d = dest; + const char *s = src; + + if (d==s) return d; + if ((uintptr_t)s-(uintptr_t)d-n <= -2*n) return memcpy(d, s, n); + + if (d<s) { +#ifdef __GNUC__ + if ((uintptr_t)s % WS == (uintptr_t)d % WS) { + while ((uintptr_t)d % WS) { + if (!n--) return dest; + *d++ = *s++; + } + for (; n>=WS; n-=WS, d+=WS, s+=WS) *(WT *)d = *(WT *)s; + } +#endif + for (; n; n--) *d++ = *s++; + } else { +#ifdef __GNUC__ + if ((uintptr_t)s % WS == (uintptr_t)d % WS) { + while ((uintptr_t)(d+n) % WS) { + if (!n--) return dest; + d[n] = s[n]; + } + while (n>=WS) n-=WS, *(WT *)(d+n) = *(WT *)(s+n); + } +#endif + while (n) n--, d[n] = s[n]; + } + + return dest; +} diff --git a/na/lib/string/mempcpy.c b/na/lib/string/mempcpy.c new file mode 100644 index 0000000..1f33e45 --- /dev/null +++ b/na/lib/string/mempcpy.c @@ -0,0 +1,10 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#define _GNU_SOURCE +#include <string.h> + +void *mempcpy(void *dest, const void *src, size_t n) +{ + return (char *)memcpy(dest, src, n) + n; +} diff --git a/na/lib/string/memrchr.c b/na/lib/string/memrchr.c new file mode 100644 index 0000000..8d5c742 --- /dev/null +++ b/na/lib/string/memrchr.c @@ -0,0 +1,14 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +void *__memrchr(const void *m, int c, size_t n) +{ + const unsigned char *s = m; + c = (unsigned char)c; + while (n--) if (s[n]==c) return (void *)(s+n); + return 0; +} + +weak_alias(__memrchr, memrchr); diff --git a/na/lib/string/memset.c b/na/lib/string/memset.c new file mode 100644 index 0000000..e780c71 --- /dev/null +++ b/na/lib/string/memset.c @@ -0,0 +1,93 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> +#include <stdint.h> + +void *memset(void *dest, int c, size_t n) +{ + unsigned char *s = dest; + size_t k; + + /* Fill head and tail with minimal branching. Each + * conditional ensures that all the subsequently used + * offsets are well-defined and in the dest region. */ + + if (!n) return dest; + s[0] = c; + s[n-1] = c; + if (n <= 2) return dest; + s[1] = c; + s[2] = c; + s[n-2] = c; + s[n-3] = c; + if (n <= 6) return dest; + s[3] = c; + s[n-4] = c; + if (n <= 8) return dest; + + /* Advance pointer to align it at a 4-byte boundary, + * and truncate n to a multiple of 4. The previous code + * already took care of any head/tail that get cut off + * by the alignment. */ + + k = -(uintptr_t)s & 3; + s += k; + n -= k; + n &= -4; + +#ifdef __GNUC__ + typedef uint32_t __attribute__((__may_alias__)) u32; + typedef uint64_t __attribute__((__may_alias__)) u64; + + u32 c32 = ((u32)-1)/255 * (unsigned char)c; + + /* In preparation to copy 32 bytes at a time, aligned on + * an 8-byte bounary, fill head/tail up to 28 bytes each. + * As in the initial byte-based head/tail fill, each + * conditional below ensures that the subsequent offsets + * are valid (e.g. !(n<=24) implies n>=28). */ + + *(u32 *)(s+0) = c32; + *(u32 *)(s+n-4) = c32; + if (n <= 8) return dest; + *(u32 *)(s+4) = c32; + *(u32 *)(s+8) = c32; + *(u32 *)(s+n-12) = c32; + *(u32 *)(s+n-8) = c32; + if (n <= 24) return dest; + *(u32 *)(s+12) = c32; + *(u32 *)(s+16) = c32; + *(u32 *)(s+20) = c32; + *(u32 *)(s+24) = c32; + *(u32 *)(s+n-28) = c32; + *(u32 *)(s+n-24) = c32; + *(u32 *)(s+n-20) = c32; + *(u32 *)(s+n-16) = c32; + + /* Align to a multiple of 8 so we can fill 64 bits at a time, + * and avoid writing the same bytes twice as much as is + * practical without introducing additional branching. */ + + k = 24 + ((uintptr_t)s & 4); + s += k; + n -= k; + + /* If this loop is reached, 28 tail bytes have already been + * filled, so any remainder when n drops below 32 can be + * safely ignored. */ + + u64 c64 = c32 | ((u64)c32 << 32); + for (; n >= 32; n-=32, s+=32) { + *(u64 *)(s+0) = c64; + *(u64 *)(s+8) = c64; + *(u64 *)(s+16) = c64; + *(u64 *)(s+24) = c64; + } +#else + /* Pure C fallback with no aliasing violations. */ + for (; n; n--, s++) *s = c; +#endif + + return dest; +} diff --git a/na/lib/string/rindex.c b/na/lib/string/rindex.c new file mode 100644 index 0000000..897e19e --- /dev/null +++ b/na/lib/string/rindex.c @@ -0,0 +1,11 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#define _BSD_SOURCE +#include <string.h> +#include <strings.h> + +char *rindex(const char *s, int c) +{ + return strrchr(s, c); +} diff --git a/na/lib/string/stpcpy.c b/na/lib/string/stpcpy.c new file mode 100644 index 0000000..0c1f1b4 --- /dev/null +++ b/na/lib/string/stpcpy.c @@ -0,0 +1,32 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> +#include <stdint.h> +#include <limits.h> + +#define ALIGN (sizeof(size_t)) +#define ONES ((size_t)-1/UCHAR_MAX) +#define HIGHS (ONES * (UCHAR_MAX/2+1)) +#define HASZERO(x) ((x)-ONES & ~(x) & HIGHS) + +char *__stpcpy(char *restrict d, const char *restrict s) +{ +#ifdef __GNUC__ + typedef size_t __attribute__((__may_alias__)) word; + word *wd; + const word *ws; + if ((uintptr_t)s % ALIGN == (uintptr_t)d % ALIGN) { + for (; (uintptr_t)s % ALIGN; s++, d++) + if (!(*d=*s)) return d; + wd=(void *)d; ws=(const void *)s; + for (; !HASZERO(*ws); *wd++ = *ws++); + d=(void *)wd; s=(const void *)ws; + } +#endif + for (; (*d=*s); s++, d++); + + return d; +} + +weak_alias(__stpcpy, stpcpy); diff --git a/na/lib/string/stpncpy.c b/na/lib/string/stpncpy.c new file mode 100644 index 0000000..ca2ef78 --- /dev/null +++ b/na/lib/string/stpncpy.c @@ -0,0 +1,35 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> +#include <stdint.h> +#include <limits.h> + +#define ALIGN (sizeof(size_t)-1) +#define ONES ((size_t)-1/UCHAR_MAX) +#define HIGHS (ONES * (UCHAR_MAX/2+1)) +#define HASZERO(x) ((x)-ONES & ~(x) & HIGHS) + +char *__stpncpy(char *restrict d, const char *restrict s, size_t n) +{ +#ifdef __GNUC__ + typedef size_t __attribute__((__may_alias__)) word; + word *wd; + const word *ws; + if (((uintptr_t)s & ALIGN) == ((uintptr_t)d & ALIGN)) { + for (; ((uintptr_t)s & ALIGN) && n && (*d=*s); n--, s++, d++); + if (!n || !*s) goto tail; + wd=(void *)d; ws=(const void *)s; + for (; n>=sizeof(size_t) && !HASZERO(*ws); + n-=sizeof(size_t), ws++, wd++) *wd = *ws; + d=(void *)wd; s=(const void *)ws; + } +#endif + for (; n && (*d=*s); n--, s++, d++); +tail: + memset(d, 0, n); + return d; +} + +weak_alias(__stpncpy, stpncpy); + diff --git a/na/lib/string/strcat.c b/na/lib/string/strcat.c new file mode 100644 index 0000000..723c2ff --- /dev/null +++ b/na/lib/string/strcat.c @@ -0,0 +1,10 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +char *strcat(char *restrict dest, const char *restrict src) +{ + strcpy(dest + strlen(dest), src); + return dest; +} diff --git a/na/lib/string/strchr.c b/na/lib/string/strchr.c new file mode 100644 index 0000000..ddeca01 --- /dev/null +++ b/na/lib/string/strchr.c @@ -0,0 +1,10 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +char *strchr(const char *s, int c) +{ + char *r = __strchrnul(s, c); + return *(unsigned char *)r == (unsigned char)c ? r : 0; +} diff --git a/na/lib/string/strchrnul.c b/na/lib/string/strchrnul.c new file mode 100644 index 0000000..6fc86d1 --- /dev/null +++ b/na/lib/string/strchrnul.c @@ -0,0 +1,31 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> +#include <stdint.h> +#include <limits.h> + +#define ALIGN (sizeof(size_t)) +#define ONES ((size_t)-1/UCHAR_MAX) +#define HIGHS (ONES * (UCHAR_MAX/2+1)) +#define HASZERO(x) ((x)-ONES & ~(x) & HIGHS) + +char *__strchrnul(const char *s, int c) +{ + c = (unsigned char)c; + if (!c) return (char *)s + strlen(s); + +#ifdef __GNUC__ + typedef size_t __attribute__((__may_alias__)) word; + const word *w; + for (; (uintptr_t)s % ALIGN; s++) + if (!*s || *(unsigned char *)s == c) return (char *)s; + size_t k = ONES * c; + for (w = (void *)s; !HASZERO(*w) && !HASZERO(*w^k); w++); + s = (void *)w; +#endif + for (; *s && *(unsigned char *)s != c; s++); + return (char *)s; +} + +weak_alias(__strchrnul, strchrnul); diff --git a/na/lib/string/strcmp.c b/na/lib/string/strcmp.c new file mode 100644 index 0000000..afcb1b7 --- /dev/null +++ b/na/lib/string/strcmp.c @@ -0,0 +1,10 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +int strcmp(const char *l, const char *r) +{ + for (; *l==*r && *l; l++, r++); + return *(unsigned char *)l - *(unsigned char *)r; +} diff --git a/na/lib/string/strcpy.c b/na/lib/string/strcpy.c new file mode 100644 index 0000000..a761577 --- /dev/null +++ b/na/lib/string/strcpy.c @@ -0,0 +1,10 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +char *strcpy(char *restrict dest, const char *restrict src) +{ + __stpcpy(dest, src); + return dest; +} diff --git a/na/lib/string/strcspn.c b/na/lib/string/strcspn.c new file mode 100644 index 0000000..ba55fe6 --- /dev/null +++ b/na/lib/string/strcspn.c @@ -0,0 +1,20 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +#define BITOP(a,b,op) \ + ((a)[(size_t)(b)/(8*sizeof *(a))] op (size_t)1<<((size_t)(b)%(8*sizeof *(a)))) + +size_t strcspn(const char *s, const char *c) +{ + const char *a = s; + size_t byteset[32/sizeof(size_t)]; + + if (!c[0] || !c[1]) return __strchrnul(s, *c)-a; + + memset(byteset, 0, sizeof byteset); + for (; *c && BITOP(byteset, *(unsigned char *)c, |=); c++); + for (; *s && !BITOP(byteset, *(unsigned char *)s, &); s++); + return s-a; +} diff --git a/na/lib/string/strlcat.c b/na/lib/string/strlcat.c new file mode 100644 index 0000000..a61821d --- /dev/null +++ b/na/lib/string/strlcat.c @@ -0,0 +1,12 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#define _BSD_SOURCE +#include <string.h> + +size_t strlcat(char *d, const char *s, size_t n) +{ + size_t l = strnlen(d, n); + if (l == n) return l + strlen(s); + return l + strlcpy(d+l, s, n-l); +} diff --git a/na/lib/string/strlcpy.c b/na/lib/string/strlcpy.c new file mode 100644 index 0000000..c2a5142 --- /dev/null +++ b/na/lib/string/strlcpy.c @@ -0,0 +1,37 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#define _BSD_SOURCE +#include <string.h> +#include <stdint.h> +#include <limits.h> + +#define ALIGN (sizeof(size_t)-1) +#define ONES ((size_t)-1/UCHAR_MAX) +#define HIGHS (ONES * (UCHAR_MAX/2+1)) +#define HASZERO(x) ((x)-ONES & ~(x) & HIGHS) + +size_t strlcpy(char *d, const char *s, size_t n) +{ + char *d0 = d; + size_t *wd; + + if (!n--) goto finish; +#ifdef __GNUC__ + typedef size_t __attribute__((__may_alias__)) word; + const word *ws; + if (((uintptr_t)s & ALIGN) == ((uintptr_t)d & ALIGN)) { + for (; ((uintptr_t)s & ALIGN) && n && (*d=*s); n--, s++, d++); + if (n && *s) { + wd=(void *)d; ws=(const void *)s; + for (; n>=sizeof(size_t) && !HASZERO(*ws); + n-=sizeof(size_t), ws++, wd++) *wd = *ws; + d=(void *)wd; s=(const void *)ws; + } + } +#endif + for (; n && (*d=*s); n--, s++, d++); + *d = 0; +finish: + return d-d0 + strlen(s); +} diff --git a/na/lib/string/strlen.c b/na/lib/string/strlen.c new file mode 100644 index 0000000..76e14f2 --- /dev/null +++ b/na/lib/string/strlen.c @@ -0,0 +1,25 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> +#include <stdint.h> +#include <limits.h> + +#define ALIGN (sizeof(size_t)) +#define ONES ((size_t)-1/UCHAR_MAX) +#define HIGHS (ONES * (UCHAR_MAX/2+1)) +#define HASZERO(x) ((x)-ONES & ~(x) & HIGHS) + +size_t strlen(const char *s) +{ + const char *a = s; +#ifdef __GNUC__ + typedef size_t __attribute__((__may_alias__)) word; + const word *w; + for (; (uintptr_t)s % ALIGN; s++) if (!*s) return s-a; + for (w = (const void *)s; !HASZERO(*w); w++); + s = (const void *)w; +#endif + for (; *s; s++); + return s-a; +} diff --git a/na/lib/string/strncat.c b/na/lib/string/strncat.c new file mode 100644 index 0000000..a144e37 --- /dev/null +++ b/na/lib/string/strncat.c @@ -0,0 +1,13 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +char *strncat(char *restrict d, const char *restrict s, size_t n) +{ + char *a = d; + d += strlen(d); + while (n && *s) n--, *d++ = *s++; + *d++ = 0; + return a; +} diff --git a/na/lib/string/strncmp.c b/na/lib/string/strncmp.c new file mode 100644 index 0000000..b98473b --- /dev/null +++ b/na/lib/string/strncmp.c @@ -0,0 +1,12 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +int strncmp(const char *_l, const char *_r, size_t n) +{ + const unsigned char *l=(void *)_l, *r=(void *)_r; + if (!n--) return 0; + for (; *l && *r && n && *l == *r ; l++, r++, n--); + return *l - *r; +} diff --git a/na/lib/string/strncpy.c b/na/lib/string/strncpy.c new file mode 100644 index 0000000..a828465 --- /dev/null +++ b/na/lib/string/strncpy.c @@ -0,0 +1,10 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +char *strncpy(char *restrict d, const char *restrict s, size_t n) +{ + __stpncpy(d, s, n); + return d; +} diff --git a/na/lib/string/strnlen.c b/na/lib/string/strnlen.c new file mode 100644 index 0000000..8931c52 --- /dev/null +++ b/na/lib/string/strnlen.c @@ -0,0 +1,10 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +size_t strnlen(const char *s, size_t n) +{ + const char *p = memchr(s, 0, n); + return p ? p-s : n; +} diff --git a/na/lib/string/strpbrk.c b/na/lib/string/strpbrk.c new file mode 100644 index 0000000..82fbc92 --- /dev/null +++ b/na/lib/string/strpbrk.c @@ -0,0 +1,10 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +char *strpbrk(const char *s, const char *b) +{ + s += strcspn(s, b); + return *s ? (char *)s : 0; +} diff --git a/na/lib/string/strrchr.c b/na/lib/string/strrchr.c new file mode 100644 index 0000000..a45b459 --- /dev/null +++ b/na/lib/string/strrchr.c @@ -0,0 +1,9 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +char *strrchr(const char *s, int c) +{ + return __memrchr(s, c, strlen(s) + 1); +} diff --git a/na/lib/string/strsep.c b/na/lib/string/strsep.c new file mode 100644 index 0000000..2d513f4 --- /dev/null +++ b/na/lib/string/strsep.c @@ -0,0 +1,16 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#define _GNU_SOURCE +#include <string.h> + +char *strsep(char **str, const char *sep) +{ + char *s = *str, *end; + if (!s) return NULL; + end = s + strcspn(s, sep); + if (*end) *end++ = 0; + else end = 0; + *str = end; + return s; +} diff --git a/na/lib/string/strspn.c b/na/lib/string/strspn.c new file mode 100644 index 0000000..f27710d --- /dev/null +++ b/na/lib/string/strspn.c @@ -0,0 +1,23 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +#define BITOP(a,b,op) \ + ((a)[(size_t)(b)/(8*sizeof *(a))] op (size_t)1<<((size_t)(b)%(8*sizeof *(a)))) + +size_t strspn(const char *s, const char *c) +{ + const char *a = s; + size_t byteset[32/sizeof(size_t)] = { 0 }; + + if (!c[0]) return 0; + if (!c[1]) { + for (; *s == *c; s++); + return s-a; + } + + for (; *c && BITOP(byteset, *(unsigned char *)c, |=); c++); + for (; *s && BITOP(byteset, *(unsigned char *)s, &); s++); + return s-a; +} diff --git a/na/lib/string/strstr.c b/na/lib/string/strstr.c new file mode 100644 index 0000000..07e2982 --- /dev/null +++ b/na/lib/string/strstr.c @@ -0,0 +1,157 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> +#include <stdint.h> + +static char *twobyte_strstr(const unsigned char *h, const unsigned char *n) +{ + uint16_t nw = n[0]<<8 | n[1], hw = h[0]<<8 | h[1]; + for (h++; *h && hw != nw; hw = hw<<8 | *++h); + return *h ? (char *)h-1 : 0; +} + +static char *threebyte_strstr(const unsigned char *h, const unsigned char *n) +{ + uint32_t nw = (uint32_t)n[0]<<24 | n[1]<<16 | n[2]<<8; + uint32_t hw = (uint32_t)h[0]<<24 | h[1]<<16 | h[2]<<8; + for (h+=2; *h && hw != nw; hw = (hw|*++h)<<8); + return *h ? (char *)h-2 : 0; +} + +static char *fourbyte_strstr(const unsigned char *h, const unsigned char *n) +{ + uint32_t nw = (uint32_t)n[0]<<24 | n[1]<<16 | n[2]<<8 | n[3]; + uint32_t hw = (uint32_t)h[0]<<24 | h[1]<<16 | h[2]<<8 | h[3]; + for (h+=3; *h && hw != nw; hw = hw<<8 | *++h); + return *h ? (char *)h-3 : 0; +} + +#define MAX(a,b) ((a)>(b)?(a):(b)) +#define MIN(a,b) ((a)<(b)?(a):(b)) + +#define BITOP(a,b,op) \ + ((a)[(size_t)(b)/(8*sizeof *(a))] op (size_t)1<<((size_t)(b)%(8*sizeof *(a)))) + +static char *twoway_strstr(const unsigned char *h, const unsigned char *n) +{ + const unsigned char *z; + size_t l, ip, jp, k, p, ms, p0, mem, mem0; + size_t byteset[32 / sizeof(size_t)] = { 0 }; + size_t shift[256]; + + /* Computing length of needle and fill shift table */ + for (l=0; n[l] && h[l]; l++) + BITOP(byteset, n[l], |=), shift[n[l]] = l+1; + if (n[l]) return 0; /* hit the end of h */ + + /* Compute maximal suffix */ + ip = -1; jp = 0; k = p = 1; + while (jp+k<l) { + if (n[ip+k] == n[jp+k]) { + if (k == p) { + jp += p; + k = 1; + } else k++; + } else if (n[ip+k] > n[jp+k]) { + jp += k; + k = 1; + p = jp - ip; + } else { + ip = jp++; + k = p = 1; + } + } + ms = ip; + p0 = p; + + /* And with the opposite comparison */ + ip = -1; jp = 0; k = p = 1; + while (jp+k<l) { + if (n[ip+k] == n[jp+k]) { + if (k == p) { + jp += p; + k = 1; + } else k++; + } else if (n[ip+k] < n[jp+k]) { + jp += k; + k = 1; + p = jp - ip; + } else { + ip = jp++; + k = p = 1; + } + } + if (ip+1 > ms+1) ms = ip; + else p = p0; + + /* Periodic needle? */ + if (memcmp(n, n+p, ms+1)) { + mem0 = 0; + p = MAX(ms, l-ms-1) + 1; + } else mem0 = l-p; + mem = 0; + + /* Initialize incremental end-of-haystack pointer */ + z = h; + + /* Search loop */ + for (;;) { + /* Update incremental end-of-haystack pointer */ + if (z-h < l) { + /* Fast estimate for MAX(l,63) */ + size_t grow = l | 63; + const unsigned char *z2 = memchr(z, 0, grow); + if (z2) { + z = z2; + if (z-h < l) return 0; + } else z += grow; + } + + /* Check last byte first; advance by shift on mismatch */ + if (BITOP(byteset, h[l-1], &)) { + k = l-shift[h[l-1]]; + if (k) { + if (k < mem) k = mem; + h += k; + mem = 0; + continue; + } + } else { + h += l; + mem = 0; + continue; + } + + /* Compare right half */ + for (k=MAX(ms+1,mem); n[k] && n[k] == h[k]; k++); + if (n[k]) { + h += k-ms; + mem = 0; + continue; + } + /* Compare left half */ + for (k=ms+1; k>mem && n[k-1] == h[k-1]; k--); + if (k <= mem) return (char *)h; + h += p; + mem = mem0; + } +} + +char *strstr(const char *h, const char *n) +{ + /* Return immediately on empty needle */ + if (!n[0]) return (char *)h; + + /* Use faster algorithms for short needles */ + h = strchr(h, *n); + if (!h || !n[1]) return (char *)h; + if (!h[1]) return 0; + if (!n[2]) return twobyte_strstr((void *)h, (void *)n); + if (!h[2]) return 0; + if (!n[3]) return threebyte_strstr((void *)h, (void *)n); + if (!h[3]) return 0; + if (!n[4]) return fourbyte_strstr((void *)h, (void *)n); + + return twoway_strstr((void *)h, (void *)n); +} diff --git a/na/lib/string/strtok.c b/na/lib/string/strtok.c new file mode 100644 index 0000000..86d9c97 --- /dev/null +++ b/na/lib/string/strtok.c @@ -0,0 +1,16 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +char *strtok(char *restrict s, const char *restrict sep) +{ + static char *p; + if (!s && !(s = p)) return NULL; + s += strspn(s, sep); + if (!*s) return p = 0; + p = s + strcspn(s, sep); + if (*p) *p++ = 0; + else p = 0; + return s; +} diff --git a/na/lib/string/strtok_r.c b/na/lib/string/strtok_r.c new file mode 100644 index 0000000..a702703 --- /dev/null +++ b/na/lib/string/strtok_r.c @@ -0,0 +1,15 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +char *strtok_r(char *restrict s, const char *restrict sep, char **restrict p) +{ + if (!s && !(s = *p)) return NULL; + s += strspn(s, sep); + if (!*s) return *p = 0; + *p = s + strcspn(s, sep); + if (**p) *(*p)++ = 0; + else *p = 0; + return s; +} diff --git a/na/lib/string/x86_64/memcpy.s b/na/lib/string/x86_64/memcpy.s new file mode 100644 index 0000000..3d960ef --- /dev/null +++ b/na/lib/string/x86_64/memcpy.s @@ -0,0 +1,25 @@ +.global memcpy +.global __memcpy_fwd +.hidden __memcpy_fwd +.type memcpy,@function +memcpy: +__memcpy_fwd: + mov %rdi,%rax + cmp $8,%rdx + jc 1f + test $7,%edi + jz 1f +2: movsb + dec %rdx + test $7,%edi + jnz 2b +1: mov %rdx,%rcx + shr $3,%rcx + rep + movsq + and $7,%edx + jz 1f +2: movsb + dec %edx + jnz 2b +1: ret diff --git a/na/lib/string/x86_64/memmove.s b/na/lib/string/x86_64/memmove.s new file mode 100644 index 0000000..172c025 --- /dev/null +++ b/na/lib/string/x86_64/memmove.s @@ -0,0 +1,16 @@ +.global memmove +.type memmove,@function +memmove: + mov %rdi,%rax + sub %rsi,%rax + cmp %rdx,%rax +.hidden __memcpy_fwd + jae __memcpy_fwd + mov %rdx,%rcx + lea -1(%rdi,%rdx),%rdi + lea -1(%rsi,%rdx),%rsi + std + rep movsb + cld + lea 1(%rdi),%rax + ret diff --git a/na/lib/string/x86_64/memset.s b/na/lib/string/x86_64/memset.s new file mode 100644 index 0000000..2d3f5e5 --- /dev/null +++ b/na/lib/string/x86_64/memset.s @@ -0,0 +1,72 @@ +.global memset +.type memset,@function +memset: + movzbq %sil,%rax + mov $0x101010101010101,%r8 + imul %r8,%rax + + cmp $126,%rdx + ja 2f + + test %edx,%edx + jz 1f + + mov %sil,(%rdi) + mov %sil,-1(%rdi,%rdx) + cmp $2,%edx + jbe 1f + + mov %ax,1(%rdi) + mov %ax,(-1-2)(%rdi,%rdx) + cmp $6,%edx + jbe 1f + + mov %eax,(1+2)(%rdi) + mov %eax,(-1-2-4)(%rdi,%rdx) + cmp $14,%edx + jbe 1f + + mov %rax,(1+2+4)(%rdi) + mov %rax,(-1-2-4-8)(%rdi,%rdx) + cmp $30,%edx + jbe 1f + + mov %rax,(1+2+4+8)(%rdi) + mov %rax,(1+2+4+8+8)(%rdi) + mov %rax,(-1-2-4-8-16)(%rdi,%rdx) + mov %rax,(-1-2-4-8-8)(%rdi,%rdx) + cmp $62,%edx + jbe 1f + + mov %rax,(1+2+4+8+16)(%rdi) + mov %rax,(1+2+4+8+16+8)(%rdi) + mov %rax,(1+2+4+8+16+16)(%rdi) + mov %rax,(1+2+4+8+16+24)(%rdi) + mov %rax,(-1-2-4-8-16-32)(%rdi,%rdx) + mov %rax,(-1-2-4-8-16-24)(%rdi,%rdx) + mov %rax,(-1-2-4-8-16-16)(%rdi,%rdx) + mov %rax,(-1-2-4-8-16-8)(%rdi,%rdx) + +1: mov %rdi,%rax + ret + +2: test $15,%edi + mov %rdi,%r8 + mov %rax,-8(%rdi,%rdx) + mov %rdx,%rcx + jnz 2f + +1: shr $3,%rcx + rep + stosq + mov %r8,%rax + ret + +2: xor %edx,%edx + sub %edi,%edx + and $15,%edx + mov %rax,(%rdi) + mov %rax,8(%rdi) + sub %rdx,%rcx + add %rdx,%rdi + jmp 1b |