From patchwork Wed Jan 10 12:47:48 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Adhemerval Zanella X-Patchwork-Id: 124083 Delivered-To: patch@linaro.org Received: by 10.140.22.227 with SMTP id 90csp5235418qgn; Wed, 10 Jan 2018 04:49:47 -0800 (PST) X-Google-Smtp-Source: ACJfBoscaTp2+7qQiplnUPtJNqMbzd7nVlu6ov4Xsn3pgEN7c8NEvA9mBEfnWC1Qh1KctpT0rHtV X-Received: by 10.84.229.136 with SMTP id c8mr3371708plk.171.1515588587224; Wed, 10 Jan 2018 04:49:47 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1515588587; cv=none; d=google.com; s=arc-20160816; b=uFlkk26W5zO9YHhPMMe1gn8VubS5/zIjUMTG8odEgAuEaq0TO/taV3kyFGx649miFH yaJAfXlHjTqsDllHApJx6POP3j9TUbaMSzT+2Ai60LLtk1BZPdIxdM2gRSUIOjPR6X6k qgwMPlXW6HWnm3ixAcMJ+CTTH3VW8SNUqT9FygXhSaxAkfymfMZmxtgiJlZNv/wHLtCT hslui9kS+8vzcyC71o3czBys2hj9VGLj8N+eaZdjv9Mrgu+5qr//rr7ZUP0MP890pNpq SgW+SUgf9E7XaLGq7WHEdlw8NbDLZdr1apJsteIbi8yTylazbXwH+Qxp8Y1KVyv3S9bE VSUQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=references:in-reply-to:message-id:date:subject:to:from:delivered-to :sender:list-help:list-post:list-archive:list-subscribe :list-unsubscribe:list-id:precedence:mailing-list:dkim-signature :domainkey-signature:arc-authentication-results; bh=XBEXX3UZmcJ2Egae4+yud6XvCDchqIlZnQfSyPNbtS8=; b=MpRRhSpmtJ6e4efDlVipQHpU89J81c428gQwAy/mcTI1VFaatK5xMDCdQS0dCPYGUe k6UgY09KWLQNNK9BSzz89lxEuGSEHAIXyGCb3bsjaq4QfqWp9Fse6qOZG55LMT2ygTG5 Jq6q5mfsVZ0EcqMjCxzSpOAPzV2k+7Bav6ym+wxrRJ+Y9th8Rnj63zjF1knq4V/jc5UQ llKet88aJMLijSTGdvmtg/W+poxRKtWmxQjGacG7iOQYoy7DOFSN1OaqIH3nhO85GG29 x6FV3smLzKMsPtfKJkk+yoacUajy61gKRtWeh/WrDrWsBGPoUkQNaT/QmwOsuPBlw5G+ oRzw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=QAFtNY7d; spf=pass (google.com: domain of libc-alpha-return-89006-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=libc-alpha-return-89006-patch=linaro.org@sourceware.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id c1si10504148pgp.517.2018.01.10.04.49.46 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 10 Jan 2018 04:49:47 -0800 (PST) Received-SPF: pass (google.com: domain of libc-alpha-return-89006-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Authentication-Results: mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=QAFtNY7d; spf=pass (google.com: domain of libc-alpha-return-89006-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=libc-alpha-return-89006-patch=linaro.org@sourceware.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:subject:date:message-id:in-reply-to :references; q=dns; s=default; b=Y1DXCgB/nm7XjULdo5TqZNmvFdpl/vV 0G2FyGyD3ksteupeKHfzavDIl/H2WPBpKpxsT81KL7R8xp13VEVGZeTFV413yhe1 sxCDoUeattpkt9GOtBkRhe6sIuuF1tKJFp8evW2T3RTjlqfiFijnrNZG35IQNtov 2CllWpR8dcEU= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:subject:date:message-id:in-reply-to :references; s=default; bh=T3Em+XtKCGK6iZ8P9EKqugoCDi4=; b=QAFtN Y7dHwNCgO3nFOP9pMnp91SRbfMAju2DLrSHkR2GrIaUm7vzYu9VU7fjtpFws4fRN wifrMJYMzJJqDG4WBNk0MZKSfolaFFdP/mcSgDzfNXwE7yOYhIhXpk3tPRdjdhpz Ezk72xwmtv5lWPJDFU7zi271sXrwDzOBIr2aCo= Received: (qmail 130041 invoked by alias); 10 Jan 2018 12:48:43 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 122696 invoked by uid 89); 10 Jan 2018 12:48:30 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-25.9 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy=Kim, sd, inequality X-HELO: mail-qt0-f169.google.com X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references; bh=XBEXX3UZmcJ2Egae4+yud6XvCDchqIlZnQfSyPNbtS8=; b=cBlDQOoog7SGiKEX/zaJ8nE55aezVXlbjKp67R+YoEZM8mLaMJH0cbo69+suVquin5 1kuMiauFMWlNEbGCdID5yBFccoRonIEbXNsJ5hxlsWBG8wATIBEA35bnO7/mFxVgoDSh JYxr7/F4SmTSYKCpdiE/7H9+FOgO95cPAjp/USJoU/iBm4Q+wHIDune0vynsKhkP4+yo 5PAWAEtGvyUwTYgDAdiACAlWS38P0k62IuHhaHuqOqd7jZAC4s0kxmQ4/75riSl1KWHw 0i29kDw58wmXDeolUZOtpebI/1b+h6s5gnA68yIjhzSTPBt7HVPaAKomG8mDOVlfjFAR uESQ== X-Gm-Message-State: AKwxytfmhQQF92gmK2jkHaNQzLdm0BMl8FUGzkVs9Nf18uRxKB3PYchD bxXtOhqsb9jNoQ98XWSBeoWOcoRxfNs= X-Received: by 10.237.50.5 with SMTP id y5mr27316143qtd.7.1515588495433; Wed, 10 Jan 2018 04:48:15 -0800 (PST) From: Adhemerval Zanella To: libc-alpha@sourceware.org Subject: [PATCH v3 04/18] Add string vectorized find and detection functions Date: Wed, 10 Jan 2018 10:47:48 -0200 Message-Id: <1515588482-15744-5-git-send-email-adhemerval.zanella@linaro.org> In-Reply-To: <1515588482-15744-1-git-send-email-adhemerval.zanella@linaro.org> References: <1515588482-15744-1-git-send-email-adhemerval.zanella@linaro.org> This patch adds generic string find and detection implementation meant to be used in generic vectorized string implementation. The idea is to decompose the basic string operation so each architecture can reimplement if it provides any specialized hardware instruction. The 'string-fza.h' provides zero byte detection functions (find_zero_low, find_zero_all, find_eq_low, find_eq_all, find_zero_eq_low, find_zero_eq_all, find_zero_ne_low, and find_zero_ne_all). They are used on both functions provided by 'string-fzb.h' and 'string-fzi'. The 'string-fzb.h' provides boolean zero byte detection with the functions: - has_zero: determine if any byte within a word is zero. - has_eq: determine byte equality between two words. - has_zero_eq: determine if any byte within a word is zero along with byte equality between two words. The 'string-fzi.h' provides zero byte detection along with its positions: - index_first_zero: return index of first zero byte within a word. - index_first_eq: return index of first byte different between two words. - index_first_zero_eq: return index of first zero byte within a word or first byte different between two words. - index_first_zero_ne: return index of first zero byte within a word or first byte equal between two words. - index_last_zero: return index of last zero byte within a word. - index_last_eq: return index of last byte different between two words. Also, to avoid libcalls in the '__builtin_c{t,l}z{l}' calls (which may add performance degradation), inline implementation based on De Bruijn sequences are added (enabled by a configure check). Richard Henderson Adhemerval Zanella * config.h.in (HAVE_BUILTIN_CTZ, HAVE_BUILTIN_CLZ): New defines. * configure.ac: Check for __builtin_ctz{l} with no external dependencies * sysdeps/generic/string-extbyte.h: New file. * sysdeps/generic/string-fza.h: Likewise. * sysdeps/generic/string-fzb.h: Likewise. * sysdeps/generic/string-fzi.h: Likewise. --- config.h.in | 8 ++ configure | 54 ++++++++++ configure.ac | 34 +++++++ sysdeps/generic/string-extbyte.h | 35 +++++++ sysdeps/generic/string-fza.h | 117 +++++++++++++++++++++ sysdeps/generic/string-fzb.h | 49 +++++++++ sysdeps/generic/string-fzi.h | 215 +++++++++++++++++++++++++++++++++++++++ 7 files changed, 512 insertions(+) create mode 100644 sysdeps/generic/string-extbyte.h create mode 100644 sysdeps/generic/string-fza.h create mode 100644 sysdeps/generic/string-fzb.h create mode 100644 sysdeps/generic/string-fzi.h -- 2.7.4 diff --git a/config.h.in b/config.h.in index d928e7d..03bcfe6 100644 --- a/config.h.in +++ b/config.h.in @@ -245,4 +245,12 @@ in i386 6 argument syscall issue). */ #define CAN_USE_REGISTER_ASM_EBP 0 +/* If compiler supports __builtin_ctz{l} without any external depedencies + (libgcc for instance). */ +#define HAVE_BUILTIN_CTZ 0 + +/* If compiler supports __builtin_clz{l} without any external depedencies + (libgcc for instance). */ +#define HAVE_BUILTIN_CLZ 0 + #endif diff --git a/configure b/configure index 7a8bd3f..ff4464f 100755 --- a/configure +++ b/configure @@ -6592,6 +6592,60 @@ if test $libc_cv_builtin_trap = yes; then fi +{ $as_echo "$as_me:${as_lineno-$LINENO}: checking for __builtin_ctz{l} with no external dependencies" >&5 +$as_echo_n "checking for __builtin_ctz{l} with no external dependencies... " >&6; } +if ${libc_cv_builtin_ctz+:} false; then : + $as_echo_n "(cached) " >&6 +else + libc_cv_builtin_ctz=yes +echo 'int foo (unsigned long x) { return __builtin_ctz (x); }' > conftest.c +if { ac_try='${CC-cc} $CFLAGS $CPPFLAGS -S conftest.c -o conftest.s 1>&5' + { { eval echo "\"\$as_me\":${as_lineno-$LINENO}: \"$ac_try\""; } >&5 + (eval $ac_try) 2>&5 + ac_status=$? + $as_echo "$as_me:${as_lineno-$LINENO}: \$? = $ac_status" >&5 + test $ac_status = 0; }; }; then + if grep '__ctz[s,d]i2' conftest.s > /dev/null; then + libc_cv_builtin_ctz=no + fi +fi +rm -f conftest.c conftest.s + +fi +{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $libc_cv_builtin_ctz" >&5 +$as_echo "$libc_cv_builtin_ctz" >&6; } +if test x$libc_cv_builtin_ctz = xyes; then + $as_echo "#define HAVE_BUILTIN_CTZ 1" >>confdefs.h + +fi + +{ $as_echo "$as_me:${as_lineno-$LINENO}: checking for __builtin_clz{l} with no external dependencies" >&5 +$as_echo_n "checking for __builtin_clz{l} with no external dependencies... " >&6; } +if ${libc_cv_builtin_clz+:} false; then : + $as_echo_n "(cached) " >&6 +else + libc_cv_builtin_clz=yes +echo 'int foo (unsigned long x) { return __builtin_clz (x); }' > conftest.c +if { ac_try='${CC-cc} $CFLAGS $CPPFLAGS -S conftest.c -o conftest.s 1>&5' + { { eval echo "\"\$as_me\":${as_lineno-$LINENO}: \"$ac_try\""; } >&5 + (eval $ac_try) 2>&5 + ac_status=$? + $as_echo "$as_me:${as_lineno-$LINENO}: \$? = $ac_status" >&5 + test $ac_status = 0; }; }; then + if grep '__clz[s,d]i2' conftest.s > /dev/null; then + libc_cv_builtin_clz=no + fi +fi +rm -f conftest.c conftest.s + +fi +{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $libc_cv_builtin_clz" >&5 +$as_echo "$libc_cv_builtin_clz" >&6; } +if test x$libc_cv_builtin_clz = xyes; then + $as_echo "#define HAVE_BUILTIN_CLZ 1" >>confdefs.h + +fi + ac_ext=cpp ac_cpp='$CXXCPP $CPPFLAGS' ac_compile='$CXX -c $CXXFLAGS $CPPFLAGS conftest.$ac_ext >&5' diff --git a/configure.ac b/configure.ac index ca1282a..7f9c9f8 100644 --- a/configure.ac +++ b/configure.ac @@ -1675,6 +1675,40 @@ if test $libc_cv_builtin_trap = yes; then AC_DEFINE([HAVE_BUILTIN_TRAP]) fi +AC_CACHE_CHECK(for __builtin_ctz{l} with no external dependencies, + libc_cv_builtin_ctz, [dnl +libc_cv_builtin_ctz=yes +echo 'int foo (unsigned long x) { return __builtin_ctz (x); }' > conftest.c +if AC_TRY_COMMAND(${CC-cc} $CFLAGS $CPPFLAGS -S conftest.c -o conftest.s 1>&AS_MESSAGE_LOG_FD); then +changequote(,)dnl + if grep '__ctz[s,d]i2' conftest.s > /dev/null; then + libc_cv_builtin_ctz=no + fi +changequote([,])dnl +fi +rm -f conftest.c conftest.s +]) +if test x$libc_cv_builtin_ctz = xyes; then + AC_DEFINE(HAVE_BUILTIN_CTZ) +fi + +AC_CACHE_CHECK(for __builtin_clz{l} with no external dependencies, + libc_cv_builtin_clz, [dnl +libc_cv_builtin_clz=yes +echo 'int foo (unsigned long x) { return __builtin_clz (x); }' > conftest.c +if AC_TRY_COMMAND(${CC-cc} $CFLAGS $CPPFLAGS -S conftest.c -o conftest.s 1>&AS_MESSAGE_LOG_FD); then +changequote(,)dnl + if grep '__clz[s,d]i2' conftest.s > /dev/null; then + libc_cv_builtin_clz=no + fi +changequote([,])dnl +fi +rm -f conftest.c conftest.s +]) +if test x$libc_cv_builtin_clz = xyes; then + AC_DEFINE(HAVE_BUILTIN_CLZ) +fi + dnl C++ feature tests. AC_LANG_PUSH([C++]) diff --git a/sysdeps/generic/string-extbyte.h b/sysdeps/generic/string-extbyte.h new file mode 100644 index 0000000..69a78ce --- /dev/null +++ b/sysdeps/generic/string-extbyte.h @@ -0,0 +1,35 @@ +/* Extract by from memory word. Generic C version. + Copyright (C) 2018 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 STRING_EXTBYTE_H +#define STRING_EXTBYTE_H 1 + +#include +#include +#include + +static inline unsigned char +extractbyte (op_t x, unsigned idx) +{ + if (__BYTE_ORDER == __LITTLE_ENDIAN) + return x >> (idx * CHAR_BIT); + else + return x >> (sizeof (x) - 1 - idx) * CHAR_BIT; +} + +#endif /* STRING_EXTBYTE_H */ diff --git a/sysdeps/generic/string-fza.h b/sysdeps/generic/string-fza.h new file mode 100644 index 0000000..ab208bf --- /dev/null +++ b/sysdeps/generic/string-fza.h @@ -0,0 +1,117 @@ +/* Basic zero byte detection. Generic C version. + Copyright (C) 2018 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 STRING_FZA_H +#define STRING_FZA_H 1 + +#include +#include + +/* This function returns non-zero if any byte in X is zero. + More specifically, at least one bit set within the least significant + byte that was zero; other bytes within the word are indeterminate. */ + +static inline op_t +find_zero_low (op_t x) +{ + /* This expression comes from + https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord + Subtracting 1 sets 0x80 in a byte that was 0; anding ~x clears + 0x80 in a byte that was >= 128; anding 0x80 isolates that test bit. */ + op_t lsb = (op_t)-1 / 0xff; + op_t msb = lsb << (CHAR_BIT - 1); + return (x - lsb) & ~x & msb; +} + +/* This function returns at least one bit set within every byte of X that + is zero. The result is exact in that, unlike find_zero_low, all bytes + are determinate. This is usually used for finding the index of the + most significant byte that was zero. */ + +static inline op_t +find_zero_all (op_t x) +{ + /* For each byte, find not-zero by + (0) And 0x7f so that we cannot carry between bytes, + (1) Add 0x7f so that non-zero carries into 0x80, + (2) Or in the original byte (which might have had 0x80 set). + Then invert and mask such that 0x80 is set iff that byte was zero. */ + op_t m = ((op_t)-1 / 0xff) * 0x7f; + return ~(((x & m) + m) | x | m); +} + +/* With similar caveats, identify bytes that are equal between X1 and X2. */ + +static inline op_t +find_eq_low (op_t x1, op_t x2) +{ + return find_zero_low (x1 ^ x2); +} + +static inline op_t +find_eq_all (op_t x1, op_t x2) +{ + return find_zero_all (x1 ^ x2); +} + +/* With similar caveats, identify zero bytes in X1 and bytes that are + equal between in X1 and X2. */ + +static inline op_t +find_zero_eq_low (op_t x1, op_t x2) +{ + op_t lsb = (op_t)-1 / 0xff; + op_t msb = lsb << (CHAR_BIT - 1); + op_t eq = x1 ^ x2; + return (((x1 - lsb) & ~x1) | ((eq - lsb) & ~eq)) & msb; +} + +static inline op_t +find_zero_eq_all (op_t x1, op_t x2) +{ + op_t m = ((op_t)-1 / 0xff) * 0x7f; + op_t eq = x1 ^ x2; + op_t c1 = ((x1 & m) + m) | x1; + op_t c2 = ((eq & m) + m) | eq; + return ~((c1 & c2) | m); +} + +/* With similar caveats, identify zero bytes in X1 and bytes that are + not equal between in X1 and X2. */ + +static inline op_t +find_zero_ne_low (op_t x1, op_t x2) +{ + op_t m = ((op_t)-1 / 0xff) * 0x7f; + op_t eq = x1 ^ x2; + op_t nz1 = (x1 + m) | x1; /* msb set if byte not zero */ + op_t ne2 = (eq + m) | eq; /* msb set if byte not equal */ + return (ne2 | ~nz1) & ~m; /* msb set if x1 zero or x2 not equal */ +} + +static inline op_t +find_zero_ne_all (op_t x1, op_t x2) +{ + op_t m = ((op_t)-1 / 0xff) * 0x7f; + op_t eq = x1 ^ x2; + op_t nz1 = ((x1 & m) + m) | x1; + op_t ne2 = ((eq & m) + m) | eq; + return (ne2 | ~nz1) & ~m; +} + +#endif /* STRING_FZA_H */ diff --git a/sysdeps/generic/string-fzb.h b/sysdeps/generic/string-fzb.h new file mode 100644 index 0000000..d4ab59b --- /dev/null +++ b/sysdeps/generic/string-fzb.h @@ -0,0 +1,49 @@ +/* Zero byte detection, boolean. Generic C version. + Copyright (C) 2018 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 STRING_FZB_H +#define STRING_FZB_H 1 + +#include +#include + +/* Determine if any byte within X is zero. This is a pure boolean test. */ + +static inline _Bool +has_zero (op_t x) +{ + return find_zero_low (x) != 0; +} + +/* Likewise, but for byte equality between X1 and X2. */ + +static inline _Bool +has_eq (op_t x1, op_t x2) +{ + return find_eq_low (x1, x2) != 0; +} + +/* Likewise, but for zeros in X1 and equal bytes between X1 and X2. */ + +static inline _Bool +has_zero_eq (op_t x1, op_t x2) +{ + return find_zero_eq_low (x1, x2); +} + +#endif /* STRING_FZB_H */ diff --git a/sysdeps/generic/string-fzi.h b/sysdeps/generic/string-fzi.h new file mode 100644 index 0000000..57101f2 --- /dev/null +++ b/sysdeps/generic/string-fzi.h @@ -0,0 +1,215 @@ +/* Zero byte detection; indexes. Generic C version. + Copyright (C) 2018 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 STRING_FZI_H +#define STRING_FZI_H 1 + +#include +#include +#include + +/* An improved bitscan routine, multiplying the De Bruijn sequence with a + 0-1 mask separated by the least significant one bit of a scanned integer + or bitboard [1]. + + [1] https://chessprogramming.wikispaces.com/Kim+Walisch */ + +static inline unsigned +index_access (const op_t i) +{ + static const char index[] = + { +# if __WORDSIZE == 64 + 0, 47, 1, 56, 48, 27, 2, 60, + 57, 49, 41, 37, 28, 16, 3, 61, + 54, 58, 35, 52, 50, 42, 21, 44, + 38, 32, 29, 23, 17, 11, 4, 62, + 46, 55, 26, 59, 40, 36, 15, 53, + 34, 51, 20, 43, 31, 22, 10, 45, + 25, 39, 14, 33, 19, 30, 9, 24, + 13, 18, 8, 12, 7, 6, 5, 63 +# else + 0, 9, 1, 10, 13, 21, 2, 29, + 11, 14, 16, 18, 22, 25, 3, 30, + 8, 12, 20, 28, 15, 17, 24, 7, + 19, 27, 23, 6, 26, 5, 4, 31 +# endif + }; + return index[i]; +} + +/* For architecture which only provides __builtin_clz{l} (HAVE_BUILTIN_CLZ) + and/or __builtin_ctz{l} (HAVE_BUILTIN_CTZ) which uses external libcalls + (for intance __c{l,t}z{s,d}i2 from libgcc) the following wrapper provides + inline implementation for both count leading zeros and count trailing + zeros using branchless computation. */ + +static inline unsigned +__ctz (op_t x) +{ +#if !HAVE_BUILTIN_CTZ + op_t i; +# if __WORDSIZE == 64 + i = (x ^ (x - 1)) * 0x03F79D71B4CB0A89ull >> 58; +# else + i = (x ^ (x - 1)) * 0x07C4ACDDU >> 27; +# endif + return index_access (i); +#else + if (sizeof (op_t) == sizeof (long)) + return __builtin_ctzl (x); + else + return __builtin_ctzll (x); +#endif +}; + +static inline unsigned +__clz (op_t x) +{ +#if !HAVE_BUILTIN_CLZ + unsigned r; + op_t i; + + x |= x >> 1; + x |= x >> 2; + x |= x >> 4; + x |= x >> 8; + x |= x >> 16; +# if __WORDSIZE == 64 + x |= x >> 32; + i = x * 0x03F79D71B4CB0A89ull >> 58; +# else + i = x * 0x07C4ACDDU >> 27; +# endif + r = index_access (i); + return r ^ (sizeof (op_t) * CHAR_BIT - 1); +#else + if (sizeof (op_t) == sizeof (long)) + return __builtin_clzl (x); + else + return __builtin_clzll (x); +#endif +} + +/* A subroutine for the index_zero functions. Given a test word C, return + the (memory order) index of the first byte (in memory order) that is + non-zero. */ + +static inline unsigned int +index_first_ (op_t c) +{ + _Static_assert (sizeof (op_t) == sizeof (long) + || sizeof (op_t) == sizeof (long long), + "Unhandled word size"); + + unsigned r; + if (__BYTE_ORDER == __LITTLE_ENDIAN) + r = __ctz (c); + else + r = __clz (c); + return r / CHAR_BIT; +} + +/* Similarly, but return the (memory order) index of the last byte + that is non-zero. */ + +static inline unsigned int +index_last_ (op_t c) +{ + _Static_assert (sizeof (op_t) == sizeof (long) + || sizeof (op_t) == sizeof (long long), + "Unhandled word size"); + + unsigned r; + if (__BYTE_ORDER == __LITTLE_ENDIAN) + r = __clz (c); + else + r = __ctz (c); + return sizeof (op_t) - 1 - (r / CHAR_BIT); +} + +/* Given a word X that is known to contain a zero byte, return the + index of the first such within the word in memory order. */ + +static inline unsigned int +index_first_zero (op_t x) +{ + if (__BYTE_ORDER == __LITTLE_ENDIAN) + x = find_zero_low (x); + else + x = find_zero_all (x); + return index_first_ (x); +} + +/* Similarly, but perform the search for byte equality between X1 and X2. */ + +static inline unsigned int +index_first_eq (op_t x1, op_t x2) +{ + if (__BYTE_ORDER == __LITTLE_ENDIAN) + x1 = find_eq_low (x1, x2); + else + x1 = find_eq_all (x1, x2); + return index_first_ (x1); +} + +/* Similarly, but perform the search for zero within X1 or + equality between X1 and X2. */ + +static inline unsigned int +index_first_zero_eq (op_t x1, op_t x2) +{ + if (__BYTE_ORDER == __LITTLE_ENDIAN) + x1 = find_zero_eq_low (x1, x2); + else + x1 = find_zero_eq_all (x1, x2); + return index_first_ (x1); +} + +/* Similarly, but perform the search for zero within X1 or + inequality between X1 and X2. */ + +static inline unsigned int +index_first_zero_ne (op_t x1, op_t x2) +{ + if (__BYTE_ORDER == __LITTLE_ENDIAN) + x1 = find_zero_ne_low (x1, x2); + else + x1 = find_zero_ne_all (x1, x2); + return index_first_ (x1); +} + +/* Similarly, but search for the last zero within X. */ + +static inline unsigned int +index_last_zero (op_t x) +{ + if (__BYTE_ORDER == __LITTLE_ENDIAN) + x = find_zero_all (x); + else + x = find_zero_low (x); + return index_last_ (x); +} + +static inline unsigned int +index_last_eq (op_t x1, op_t x2) +{ + return index_last_zero (x1 ^ x2); +} + +#endif /* STRING_FZI_H */