From patchwork Mon Jun 13 02:57:39 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: develop--- via Libc-alpha X-Patchwork-Id: 55041 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 2AD273853577 for ; Mon, 13 Jun 2022 02:59:06 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 2AD273853577 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1655089146; bh=STgrwDYroo4JoD2oXwA5+aFCcZWHKUA0wKSLxmMhjDo=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=yQ9Q9oGldncdy39Vxr6Eu/3WVJaXZp/4eBkGQTs+ecnvJ5DjKmr4n9JxPt17qIu8A tkEilBdvreT893AjKBGopdh7hsgB1PVCkaTrR3MBlNrxyf/Lmy1VqFtEPhe3jnuxEK IbZzrFlUdlikJe29fuarsjWyAEH9kduI0MKqrxUA= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-pf1-x436.google.com (mail-pf1-x436.google.com [IPv6:2607:f8b0:4864:20::436]) by sourceware.org (Postfix) with ESMTPS id E1519386C580 for ; Mon, 13 Jun 2022 02:58:08 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org E1519386C580 Received: by mail-pf1-x436.google.com with SMTP id 15so4602222pfy.3 for ; Sun, 12 Jun 2022 19:58:08 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=STgrwDYroo4JoD2oXwA5+aFCcZWHKUA0wKSLxmMhjDo=; b=FLIp0u4T53aPSKQvd1ihaOAD79uVOrBM6eeIWAd9WnSVZ0S6gbKfx6deP/ADE/BQ53 peEGSuwgZgroTs1u25MOAsH5bpansPI0IIkyZH5nMa/q0fi1a/Zj1dCmKQ+oFQrfx8EF HPiqu8yl+5hnU7ymLrs7n+yRib6/TBwuPp0U+7w2f2npVoL454dvCXs/Qehvpci7YB/N 7lDxhpSVOoDgN7tS312C3uSvDGEvSx5uL20Jm/DrnUhV3HZojW6pn2SWDNeEuLNX726h LoJm0xpjFbvadGX1BGyWAn868/ExVYdcMYP6S34C2fLvAYqi5sH8rCUA/UAM/r7h7zJT hCYA== X-Gm-Message-State: AOAM532ylkdT/wTJnEKQj4QSJXTT30kr/LGA3watNqEMh2p9XdRFBEGU FVVU6uAwrLp+/ONsIsDz6kb6wv8UYj4= X-Google-Smtp-Source: ABdhPJyRdxddDk3cxyjRe49bOb7Z2LpXHUYKehq2cdrFrfdTmc4HCeras7rSXE74/JJcmvaRVc2cvA== X-Received: by 2002:a63:e944:0:b0:3fe:462d:cb66 with SMTP id q4-20020a63e944000000b003fe462dcb66mr20691455pgj.240.1655089087467; Sun, 12 Jun 2022 19:58:07 -0700 (PDT) Received: from sgwld-bfoong1.us.drwholdings.com ([103.58.110.6]) by smtp.gmail.com with ESMTPSA id p15-20020a1709027ecf00b00165103c9903sm3742167plb.113.2022.06.12.19.58.06 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 12 Jun 2022 19:58:07 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH 1/1] string: Add basic implementation of mempbrk Date: Mon, 13 Jun 2022 10:57:39 +0800 Message-Id: <20220613025739.23612-2-brandonfoongyankai@gmail.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20220613025739.23612-1-brandonfoongyankai@gmail.com> References: <20220613025739.23612-1-brandonfoongyankai@gmail.com> X-Spam-Status: No, score=-9.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: brandonfoongyankai--- via Libc-alpha From: develop--- via Libc-alpha Reply-To: brandonfoongyankai@gmail.com Cc: Brandon Foong Errors-To: libc-alpha-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libc-alpha" From: Brandon Foong --- include/string.h | 1 + string/Makefile | 2 + string/Versions | 1 + string/mempbrk.c | 56 ++++++++++ string/string.h | 15 +++ string/test-mempbrk.c | 242 ++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 317 insertions(+) create mode 100644 string/mempbrk.c create mode 100644 string/test-mempbrk.c diff --git a/include/string.h b/include/string.h index 21f641a413..ff84288d65 100644 --- a/include/string.h +++ b/include/string.h @@ -151,6 +151,7 @@ libc_hidden_builtin_proto (strrchr) libc_hidden_builtin_proto (strspn) libc_hidden_builtin_proto (strstr) libc_hidden_builtin_proto (ffs) +libc_hidden_builtin_proto (mempbrk) #if IS_IN (rtld) extern __typeof (__stpcpy) __stpcpy attribute_hidden; diff --git a/string/Makefile b/string/Makefile index 641e062bbb..3d8819d9f0 100644 --- a/string/Makefile +++ b/string/Makefile @@ -114,6 +114,7 @@ routines := \ swab \ wordcopy \ xpg-strerror \ + mempbrk \ # routines tests := \ @@ -183,6 +184,7 @@ tests := \ tst-svc \ tst-svc2 \ tst-xbzero-opt \ + test-mempbrk \ # tests # Both tests require the .mo translation files generated by msgfmt. diff --git a/string/Versions b/string/Versions index 864c4cf7a4..1f071a1da5 100644 --- a/string/Versions +++ b/string/Versions @@ -91,5 +91,6 @@ libc { } GLIBC_2.35 { __memcmpeq; + mempbrk; } } diff --git a/string/mempbrk.c b/string/mempbrk.c new file mode 100644 index 0000000000..575409b1a2 --- /dev/null +++ b/string/mempbrk.c @@ -0,0 +1,56 @@ +/* Copyright (C) 1991-2022 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +#include +#include + +#undef mempbrk + +#ifndef MEMPBRK +# define MEMPBRK mempbrk +#endif + +/* Find the first occurrence of any character in ACCEPT + in the first N bytes of S. */ +void * +MEMPBRK (const void *s, const char *accept, size_t n) +{ + const unsigned char *t; + + if (__glibc_unlikely (accept[0] == '\0')) + return NULL; + + if (__glibc_unlikely (accept[1] == '\0')) + return memchr (s, accept[0], n); + + /* Use multiple small memsets to enable inlining on most targets. */ + unsigned char table[256]; + unsigned char *p = memset (table, 0, 64); + memset (p + 64, 0, 64); + memset (p + 128, 0, 64); + memset (p + 192, 0, 64); + + for (t = (unsigned char*) accept; *t; ++t) + p[*t] = 1; + + for (t = (unsigned char*) s; n > 0; --n, ++t) + if (p[*t]) + return (void *) t; + + return NULL; +} +libc_hidden_builtin_def (mempbrk) diff --git a/string/string.h b/string/string.h index 54dd8344de..24badfef50 100644 --- a/string/string.h +++ b/string/string.h @@ -136,6 +136,21 @@ extern void *memrchr (const void *__s, int __c, size_t __n) # endif #endif +/* Find the first occurrence of any character in ACCEPT + in the first N bytes of S. */ +#ifdef __CORRECT_ISO_CPP_STRING_H_PROTO +extern "C++" +{ +extern void *mempbrk (void *__s, const char *__accept, size_t __n) + __THROW __asm ("mempbrk") __attribute_pure__ __nonnull ((1, 2)); +extern const void *mempbrk (const void *__s, const char *__accept, size_t __n) + __THROW __asm ("mempbrk") __attribute_pure__ __nonnull ((1, 2)); +} +#else +extern void *mempbrk (const void *__s, const char *__accept, size_t __n) + __THROW __attribute_pure__ __nonnull ((1, 2)); +#endif + /* Copy SRC to DEST. */ extern char *strcpy (char *__restrict __dest, const char *__restrict __src) diff --git a/string/test-mempbrk.c b/string/test-mempbrk.c new file mode 100644 index 0000000000..8d50039952 --- /dev/null +++ b/string/test-mempbrk.c @@ -0,0 +1,242 @@ +/* Test and measure strpbrk functions. + Copyright (C) 1999-2022 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +#ifndef WIDE +# define CHAR char +# define UCHAR unsigned char +# define STRLEN strlen +# define STRCHR strchr +# define BIG_CHAR CHAR_MAX +# define SMALL_CHAR 127 +#else +# include +# define CHAR wchar_t +# define UCHAR wchar_t +# define STRLEN wcslen +# define STRCHR wcschr +# define BIG_CHAR WCHAR_MAX +# define SMALL_CHAR 1273 +#endif /* WIDE */ + +#ifndef MEMPBRK_RESULT +# define TEST_MAIN +# ifndef WIDE +# define TEST_NAME "mempbrk" +# else +# define TEST_NAME "wmempbrk" +# endif /* WIDE */ +# include "test-string.h" + +# ifndef WIDE +# define MEMPBRK mempbrk +# define SIMPLE_MEMPBRK simple_mempbrk +# else +# include +# define MEMPBRK wmempbrk +# define SIMPLE_MEMPBRK simple_wmempbrk +# endif /* WIDE */ + +typedef void *(*proto_t) (const void *, const CHAR *, size_t); + +IMPL (MEMPBRK, 1) + +/* Naive implementation to verify results. */ + +CHAR * +SIMPLE_MEMPBRK (const void *s, const CHAR *rej, size_t n) +{ + const CHAR *r; + CHAR c; + + while (c = *(char *) s++, n--) + for (r = rej; *r != '\0'; ++r) + if (*r == c) + return (void *) s - 1; + return NULL; +} + +#endif /* !MEMPBRK_RESULT */ + +static void +do_one_test (impl_t *impl, const void *s, const CHAR *acc, size_t n, void * exp_res) +{ + void * res = CALL (impl, s, acc, n); + if (res != exp_res) + { + error (0, 0, "Wrong result in function %s %p %p", impl->name, + res, exp_res); + ret = 1; + return; + } +} + +static void +do_test (size_t align, size_t pos, size_t len) +{ + size_t i; + int c, byte_exists; + void * result; + CHAR *rej, *s; + + align &= 7; + if ((align + pos + 10) * sizeof (CHAR) >= page_size || len > 240) + return; + + rej = (CHAR *) (buf2) + (random () & 255); + s = (CHAR *) (buf1) + align; + + for (i = 0; i < len; ++i) + { + rej[i] = random () & BIG_CHAR; + if (!rej[i]) + rej[i] = random () & BIG_CHAR; + if (!rej[i]) + rej[i] = 1 + (random () & SMALL_CHAR); + } + rej[len] = '\0'; + for (c = 1; c <= BIG_CHAR; ++c) + if (STRCHR (rej, c) == NULL) + break; + + for (i = 0; i < pos + 10; ++i) + { + s[i] = random () & BIG_CHAR; + if (STRCHR (rej, s[i])) + { + s[i] = random () & BIG_CHAR; + if (STRCHR (rej, s[i])) + s[i] = c; + } + } + byte_exists = (random() & 1) && len; + s[pos] = byte_exists ? rej[random () % len] : s[pos]; + result = byte_exists ? s + pos : NULL; + + FOR_EACH_IMPL (impl, 0) + do_one_test (impl, s, rej, pos + 10, result); +} + +static void +do_random_tests (void) +{ + size_t i, j, n, align, pos, len, rlen; + void * result; + int c, byte_exists; + UCHAR *p = (UCHAR *) (buf1 + page_size) - 512; + UCHAR *rej; + + for (n = 0; n < ITERATIONS; n++) + { + align = random () & 15; + pos = random () & 511; + if (pos + align >= 511) + pos = 510 - align - (random () & 7); + len = random () & 511; + if (pos >= len && (random () & 1)) + len = pos + 1 + (random () & 7); + if (len + align >= 512) + len = 511 - align - (random () & 7); + if (random () & 1) + rlen = random () & 63; + else + rlen = random () & 15; + rej = (UCHAR *) (buf2 + page_size) - rlen - 1 - (random () & 7); + for (i = 0; i < rlen; ++i) + { + rej[i] = random () & BIG_CHAR; + if (!rej[i]) + rej[i] = random () & BIG_CHAR; + if (!rej[i]) + rej[i] = 1 + (random () & SMALL_CHAR); + } + rej[i] = '\0'; + for (c = 1; c <= BIG_CHAR; ++c) + if (STRCHR ((CHAR *) rej, c) == NULL) + break; + j = (pos > len ? pos : len) + align + 64; + if (j > 512) + j = 512; + + byte_exists = (random() & 1) && rlen; + for (i = 0; i < j; i++) + { + if (i == pos + align) + p[i] = byte_exists ? rej[random () % rlen] : '\0'; + else if (i < align || i > len + align) + p[i] = random () & BIG_CHAR; + else + { + p[i] = random () & BIG_CHAR; + if (STRCHR ((CHAR *) rej, p[i])) + { + p[i] = random () & BIG_CHAR; + if (STRCHR ((CHAR *) rej, p[i])) + p[i] = c; + } + } + } + + result = pos < len && byte_exists ? (CHAR *) p + align + pos : NULL; + + FOR_EACH_IMPL (impl, 1) + if (CALL (impl, (CHAR *) p + align, (CHAR *) rej, len) != result) + { + error (0, 0, "Iteration %zd - wrong result in function %s (%zd, %p, %zd, %zd, %zd) %p != %p", + n, impl->name, align, rej, rlen, pos, len, + (void *) CALL (impl, (CHAR *) (p + align), (CHAR *) rej, len), + (void *) result); + ret = 1; + } + } +} + +int +test_main (void) +{ + size_t i; + + test_init (); + + printf ("%32s", ""); + FOR_EACH_IMPL (impl, 0) + printf ("\t%s", impl->name); + putchar ('\n'); + + for (i = 0; i < 32; ++i) + { + do_test (0, 512, i); + do_test (i, 512, i); + } + + for (i = 1; i < 8; ++i) + { + do_test (0, 16 << i, 4); + do_test (i, 16 << i, 4); + } + + for (i = 1; i < 8; ++i) + do_test (i, 64, 10); + + for (i = 0; i < 64; ++i) + do_test (0, i, 6); + + do_random_tests (); + return ret; +} + +#include