From unknown Sat Jun 21 10:34:42 2025 X-Loop: help-debbugs@gnu.org Subject: bug#23932: dfa: use algorithm for single byte character to any single byte character in input text always Resent-From: Norihiro Tanaka Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Sun, 10 Jul 2016 09:53:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 23932 X-GNU-PR-Package: grep X-GNU-PR-Keywords: To: 23932@debbugs.gnu.org X-Debbugs-Original-To: Received: via spool by submit@debbugs.gnu.org id=B.146814434313707 (code B ref -1); Sun, 10 Jul 2016 09:53:01 +0000 Received: (at submit) by debbugs.gnu.org; 10 Jul 2016 09:52:23 +0000 Received: from localhost ([127.0.0.1]:44590 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bMBPT-0003Z1-94 for submit@debbugs.gnu.org; Sun, 10 Jul 2016 05:52:23 -0400 Received: from eggs.gnu.org ([208.118.235.92]:54196) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bMBPR-0003Yp-Hw for submit@debbugs.gnu.org; Sun, 10 Jul 2016 05:52:22 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1bMBPK-00013G-0N for submit@debbugs.gnu.org; Sun, 10 Jul 2016 05:52:16 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=0.8 required=5.0 tests=BAYES_50 autolearn=disabled version=3.3.2 Received: from lists.gnu.org ([2001:4830:134:3::11]:41591) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bMBPJ-000136-Ss for submit@debbugs.gnu.org; Sun, 10 Jul 2016 05:52:13 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:45132) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bMBPH-00050q-0u for bug-grep@gnu.org; Sun, 10 Jul 2016 05:52:12 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1bMBPB-00011Q-3C for bug-grep@gnu.org; Sun, 10 Jul 2016 05:52:10 -0400 Received: from mailgw01.kcn.ne.jp ([61.86.7.208]:40140) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bMBPA-00010m-BR for bug-grep@gnu.org; Sun, 10 Jul 2016 05:52:05 -0400 Received: from mxs02-s (mailgw2.kcn.ne.jp [61.86.15.234]) by mailgw01.kcn.ne.jp (Postfix) with ESMTP id 242E44A078A for ; Sun, 10 Jul 2016 18:51:48 +0900 (JST) X-matriXscan-loop-detect: 310ba3e5f43ef402881df2ed19015b017ea80efe Received: from mail01.kcn.ne.jp ([61.86.6.180]) by mxs02-s with ESMTP; Sun, 10 Jul 2016 18:51:46 +0900 (JST) Received: from [10.120.1.14] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail01.kcn.ne.jp (Postfix) with ESMTPA id 79D7B5A824C for ; Sun, 10 Jul 2016 18:51:46 +0900 (JST) Date: Sun, 10 Jul 2016 18:51:43 +0900 From: Norihiro Tanaka Message-Id: <20160710185143.23FB.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_578213EE0000000023EF_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-matriXscan-Sophos-AV: Clean X-matriXscan-Action: Approve X-matriXscan: Uncategorized X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-Received-From: 2001:4830:134:3::11 X-Spam-Score: -4.0 (----) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -4.0 (----) --------_578213EE0000000023EF_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit In multibyte locales, if a pattern start with period expression, matching is still slow, as transition table is built at run time, even when next character is single byte in input text. This patch changes it into as use algorithm for single byte character to any single byte character in input text always. If transition table has been built already and a next character in input text is single byte, transit to next state by reference of only pre-built transition table, even if from a state including ANYCHAR. $ yes "$(printf 'a%038db\n' 0)" | head -1000000 >in $ env LC_ALL=C gcc -v Reading specs from /usr/local/lib/gcc/x86_64-pc-linux-gnu/4.4.7/specs Target: x86_64-pc-linux-gnu Configured with: ./configure --with-as=/usr/local/bin/as --with-ld=/usr/local/bin/ld --with-system-zlib --enable-__cxa_atexit Thread model: posix gcc version 4.4.7 (GCC) patch#21486 is required before this patch. grep will speed up by this patch additionaly. [grep-2.25] $ time -p env LC_ALL=ja_JP.eucjp grep .a.b in real 4.78 user 4.42 sys 0.16 $ time -p env LC_ALL=ja_JP.eucjp grep '.\{41\}' in real 46.23 user 43.98 sys 0.21 [after patch#21486] $ time -p env LC_ALL=ja_JP.eucjp src/grep .a.b in real 1.26 user 1.08 sys 0.08 $ time -p env LC_ALL=ja_JP.eucjp src/grep '.\{41\}' in real 1.14 user 1.00 sys 0.10 [after this patch] $ time -p env LC_ALL=ja_JP.eucjp src/grep .a.b in real 0.47 user 0.36 sys 0.07 $ time -p env LC_ALL=ja_JP.eucjp src/grep '.\{41\}' in real 0.24 user 0.18 sys 0.05 [locale C (ref.)] $ time -p env LC_ALL=C src/grep .a.b in real 0.23 user 0.11 sys 0.09 $ time -p env LC_ALL=C src/grep '.\{41\}' in real 0.22 user 0.13 sys 0.06 --------_578213EE0000000023EF_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII"; name="0001-dfa-use-algorithm-for-single-byte-character-to-any-s.patch" Content-Disposition: attachment; filename="0001-dfa-use-algorithm-for-single-byte-character-to-any-s.patch" Content-Transfer-Encoding: base64 RnJvbSAzZDBjMTMwODA4Yzk3NGYxMjcxNTYxYzc0MzNiMmFhNjYxYzQ5NTA3IE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBOb3JpaGlybyBUYW5ha2EgPG5vcml0bmtAa2NuLm5lLmpwPgpE YXRlOiBTdW4sIDEwIEp1bCAyMDE2IDEwOjI2OjM5ICswOTAwClN1YmplY3Q6IFtQQVRDSF0gZGZh OiB1c2UgYWxnb3JpdGhtIGZvciBzaW5nbGUgYnl0ZSBjaGFyYWN0ZXIgdG8gYW55IHNpbmdsZSBi eXRlCiBjaGFyYWN0ZXIgaW4gaW5wdXQgdGV4dCBhbHdheXMKCkV2ZW4gaW4gbm9uLVVURjggbG9j YWxlcywgaWYgYSBjaGFyYWN0ZXIgYXQgY3VycmVudCBwb3NpdGlvbiBpbiBpbnB1dAp0ZXh0IGlz IHNpbmdsZSBieXRlLCB3ZSBjYW4gdXNlIENTRVQgdG8gbWF0Y2ggQU5ZQ0hBUi4KCiogc3JjL2Rm YS5jIChjaGFyY2xhc3NfaW5kZXhfYW55Y2hhcik6IE5ldyB2YXIuICBDYWNoZSBpbmRleCBvZiBD U0VUCmZvciBBTllDSEFSLgoobGV4KTogTWFrZSBDU0VUIGZvciBBTllDSEFSLgooc3RhdGVfaW5k ZXgpOiBTaW1wbGlmeS4KKGRmYXN0YXRlKTogQ29uc2lkZXIgQ1NFVCBmb3IgQU5ZQ0hBUi4KKHRy YW5zaXRfc3RhdGVfc2luZ2xlYnl0ZSwgdHJhbnNpdF9zdGF0ZSk6IFJlbW92ZSBoYW5kbGluZyBm b3IgZW9sYnl0ZSwKYXMgd2UgYXNzdW1lIHRoYXQgZW9sYnl0ZSBkb2VzIG5vdCBhcHBlYXIgYXQg Y3VycmVudCBwb3NpdGlvbi4KKGRmYWV4ZWNfbWFpbik6IHVzZSBhbGdvcml0aG0gZm9yIHNpbmds ZSBieXRlIGNoYXJhY3RlciB0byBhbnkgc2luZ2xlCmJ5dGUgY2hhcmFjdGVyIGluIGlucHV0IHRl eHQgYWx3YXlzLgotLS0KIHNyYy9kZmEuYyB8ICAxMTUgKysrKysrKysrKysrKysrKysrKysrKysr LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCiAxIGZpbGVzIGNoYW5nZWQsIDQ2 IGluc2VydGlvbnMoKyksIDY5IGRlbGV0aW9ucygtKQoKZGlmZiAtLWdpdCBhL3NyYy9kZmEuYyBi L3NyYy9kZmEuYwppbmRleCAzYmQwYzY4Li5lOTMyYjJjIDEwMDY0NAotLS0gYS9zcmMvZGZhLmMK KysrIGIvc3JjL2RmYS5jCkBAIC03OSw2ICs3OSw4IEBAIGVudW0KICAgQ0hBUkNMQVNTX1dPUkRT ID0gKE5PVENIQVIgKyBDSEFSQ0xBU1NfV09SRF9CSVRTIC0gMSkgLyBDSEFSQ0xBU1NfV09SRF9C SVRTCiB9OwogCitzdGF0aWMgc2l6ZV90IGNoYXJjbGFzc19pbmRleF9hbnljaGFyID0gLTE7CisK IC8qIFNldHMgb2YgdW5zaWduZWQgY2hhcmFjdGVycyBhcmUgc3RvcmVkIGFzIGJpdCB2ZWN0b3Jz IGluIGFycmF5cyBvZiBpbnRzLiAgKi8KIHR5cGVkZWYgY2hhcmNsYXNzX3dvcmQgY2hhcmNsYXNz W0NIQVJDTEFTU19XT1JEU107CiAKQEAgLTE0MjksMjEgKzE0MzEsMjUgQEAgbGV4ICh2b2lkKQog ICAgICAgICBjYXNlICcuJzoKICAgICAgICAgICBpZiAoYmFja3NsYXNoKQogICAgICAgICAgICAg Z290byBub3JtYWxfY2hhcjsKLSAgICAgICAgICBpZiAoZGZhLT5tdWx0aWJ5dGUpCisgICAgICAg ICAgaWYgKGNoYXJjbGFzc19pbmRleF9hbnljaGFyID09IChzaXplX3QpIC0xKQogICAgICAgICAg ICAgewotICAgICAgICAgICAgICAvKiBJbiBtdWx0aWJ5dGUgZW52aXJvbm1lbnQgcGVyaW9kIG11 c3QgbWF0Y2ggd2l0aCBhIHNpbmdsZQotICAgICAgICAgICAgICAgICBjaGFyYWN0ZXIgbm90IGEg Ynl0ZS4gIFNvIHdlIHVzZSBBTllDSEFSLiAgKi8KLSAgICAgICAgICAgICAgbGFzdHN0YXJ0ID0g ZmFsc2U7Ci0gICAgICAgICAgICAgIHJldHVybiBsYXN0dG9rID0gQU5ZQ0hBUjsKKyAgICAgICAg ICAgICAgemVyb3NldCAoY2NsKTsKKyAgICAgICAgICAgICAgbm90c2V0IChjY2wpOworICAgICAg ICAgICAgICBpZiAoIShzeW50YXhfYml0cyAmIFJFX0RPVF9ORVdMSU5FKSkKKyAgICAgICAgICAg ICAgICBjbHJiaXQgKCdcbicsIGNjbCk7CisgICAgICAgICAgICAgIGlmIChzeW50YXhfYml0cyAm IFJFX0RPVF9OT1RfTlVMTCkKKyAgICAgICAgICAgICAgICBjbHJiaXQgKCdcMCcsIGNjbCk7Cisg ICAgICAgICAgICAgIGlmIChkZmEtPm11bHRpYnl0ZSkKKyAgICAgICAgICAgICAgICB7CisgICAg ICAgICAgICAgICAgICBmb3IgKGMyID0gMDsgYzIgPCBOT1RDSEFSOyArK2MyKQorICAgICAgICAg ICAgICAgICAgICBpZiAobWJydG93Y19jYWNoZVtjMl0gPT0gV0VPRikKKyAgICAgICAgICAgICAg ICAgICAgICBjbHJiaXQgKGMyLCBjY2wpOworICAgICAgICAgICAgICAgIH0KKyAgICAgICAgICAg ICAgY2hhcmNsYXNzX2luZGV4X2FueWNoYXIgPSBjaGFyY2xhc3NfaW5kZXggKGNjbCk7CiAgICAg ICAgICAgICB9Ci0gICAgICAgICAgemVyb3NldCAoY2NsKTsKLSAgICAgICAgICBub3RzZXQgKGNj bCk7Ci0gICAgICAgICAgaWYgKCEoc3ludGF4X2JpdHMgJiBSRV9ET1RfTkVXTElORSkpCi0gICAg ICAgICAgICBjbHJiaXQgKCdcbicsIGNjbCk7Ci0gICAgICAgICAgaWYgKHN5bnRheF9iaXRzICYg UkVfRE9UX05PVF9OVUxMKQotICAgICAgICAgICAgY2xyYml0ICgnXDAnLCBjY2wpOwogICAgICAg ICAgIGxhc3RzdGFydCA9IGZhbHNlOwotICAgICAgICAgIHJldHVybiBsYXN0dG9rID0gQ1NFVCAr IGNoYXJjbGFzc19pbmRleCAoY2NsKTsKKyAgICAgICAgICByZXR1cm4gbGFzdHRvayA9CisgICAg ICAgICAgICBkZmEtPm11bHRpYnl0ZSA/IEFOWUNIQVIgOiBDU0VUICsgY2hhcmNsYXNzX2luZGV4 X2FueWNoYXI7CiAKICAgICAgICAgY2FzZSAncyc6CiAgICAgICAgIGNhc2UgJ1MnOgpAQCAtMjEy NSw3ICsyMTMxLDcgQEAgc3RhdGVfaW5kZXggKHN0cnVjdCBkZmEgKmQsIHBvc2l0aW9uX3NldCBj b25zdCAqcywgaW50IGNvbnRleHQpCiAgICAgICAgIH0KICAgICAgIGVsc2UgaWYgKGQtPnRva2Vu c1tzLT5lbGVtc1tqXS5pbmRleF0gPT0gQkFDS1JFRikKICAgICAgICAgZC0+c3RhdGVzW2ldLmNv bnN0cmFpbnQgPSBOT19DT05TVFJBSU5UOwotICAgICAgaWYgKGQtPm11bHRpYnl0ZSAmJiBkLT50 b2tlbnNbcy0+ZWxlbXNbal0uaW5kZXhdID09IEFOWUNIQVIpCisgICAgICBlbHNlIGlmIChkLT50 b2tlbnNbcy0+ZWxlbXNbal0uaW5kZXhdID09IEFOWUNIQVIpCiAgICAgICAgIHsKICAgICAgICAg ICBpbnQgYWNjZXB0YWJsZSA9IDA7CiAgICAgICAgICAgaWYgKFNVQ0NFRURTX0lOX0NPTlRFWFQg KGNvbnN0cmFpbnQsIGNvbnRleHQsIENUWF9ORVdMSU5FKSkKQEAgLTI1ODgsMTQgKzI1OTQsMTYg QEAgZGZhc3RhdGUgKHN0YXRlX251bSBzLCBzdHJ1Y3QgZGZhICpkLCBzdGF0ZV9udW0gdHJhbnNb XSkKICAgICAgICAgc2V0Yml0IChkLT50b2tlbnNbcG9zLmluZGV4XSwgbWF0Y2hlcyk7CiAgICAg ICBlbHNlIGlmIChkLT50b2tlbnNbcG9zLmluZGV4XSA+PSBDU0VUKQogICAgICAgICBjb3B5c2V0 IChkLT5jaGFyY2xhc3Nlc1tkLT50b2tlbnNbcG9zLmluZGV4XSAtIENTRVRdLCBtYXRjaGVzKTsK LSAgICAgIGVsc2UgaWYgKGQtPm11bHRpYnl0ZSAmJiBkLT50b2tlbnNbcG9zLmluZGV4XSA9PSBB TllDSEFSKQotICAgICAgICAvKiBBTllDSEFSIG11c3QgbWF0Y2ggd2l0aCBhIHNpbmdsZSBjaGFy YWN0ZXIsIHNvIHdlIG11c3QgcHV0Ci0gICAgICAgICAgIGl0IHRvIEQtPnN0YXRlc1tzXS5tYnBz IHdoaWNoIGNvbnRhaW5zIHRoZSBwb3NpdGlvbnMgd2hpY2gKLSAgICAgICAgICAgY2FuIG1hdGNo IHdpdGggYSBzaW5nbGUgY2hhcmFjdGVyIG5vdCBhIGJ5dGUuICBJZiBhbGwKLSAgICAgICAgICAg cG9zaXRpb25zIHdoaWNoIGhhcyBBTllDSEFSIGRvZXMgbm90IGRlcGVuZCBvbiBjb250ZXh0IG9m Ci0gICAgICAgICAgIG5leHQgY2hhcmFjdGVyLCB3ZSBwdXQgdGhlIGZvbGxvd3MgaW5zdGVhZCBv ZiBpdCB0bwotICAgICAgICAgICBELT5zdGF0ZXNbc10ubWJwcyB0byBvcHRpbWl6ZS4gICovCisg ICAgICBlbHNlIGlmIChkLT50b2tlbnNbcG9zLmluZGV4XSA9PSBBTllDSEFSKQogICAgICAgICB7 CisgICAgICAgICAgY29weXNldCAoZC0+Y2hhcmNsYXNzZXNbY2hhcmNsYXNzX2luZGV4X2FueWNo YXJdLCBtYXRjaGVzKTsKKworICAgICAgICAgIC8qIEFOWUNIQVIgbXVzdCBtYXRjaCB3aXRoIGEg c2luZ2xlIGNoYXJhY3Rlciwgc28gd2UgbXVzdCBwdXQKKyAgICAgICAgICAgICBpdCB0byBELT5z dGF0ZXNbc10ubWJwcyB3aGljaCBjb250YWlucyB0aGUgcG9zaXRpb25zIHdoaWNoCisgICAgICAg ICAgICAgY2FuIG1hdGNoIHdpdGggYSBzaW5nbGUgY2hhcmFjdGVyIG5vdCBhIGJ5dGUuICBJZiBh bGwKKyAgICAgICAgICAgICBwb3NpdGlvbnMgd2hpY2ggaGFzIEFOWUNIQVIgZG9lcyBub3QgZGVw ZW5kIG9uIGNvbnRleHQgb2YKKyAgICAgICAgICAgICBuZXh0IGNoYXJhY3Rlciwgd2UgcHV0IHRo ZSBmb2xsb3dzIGluc3RlYWQgb2YgaXQgdG8KKyAgICAgICAgICAgICBELT5zdGF0ZXNbc10ubWJw cyB0byBvcHRpbWl6ZS4gICovCiAgICAgICAgICAgaWYgKGQtPnN0YXRlc1tzXS5jdXJyX2RlcGVu ZGVudCkKICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgaWYgKGQtPnN0YXRlc1tzXS5tYnBz Lm5lbGVtID09IDApCkBAIC0yNjA2LDkgKzI2MTQsMTEgQEAgZGZhc3RhdGUgKHN0YXRlX251bSBz LCBzdHJ1Y3QgZGZhICpkLCBzdGF0ZV9udW0gdHJhbnNbXSkKICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICBkLT5zdGF0ZXNbc10uY29udGV4dCwgQ1RYX0FOWSkpCiAgICAg ICAgICAgICB7CiAgICAgICAgICAgICAgIGlmIChkLT5zdGF0ZXNbc10ubWJwcy5uZWxlbSA9PSAw KQotICAgICAgICAgICAgICAgIGFsbG9jX3Bvc2l0aW9uX3NldCAoJmQtPnN0YXRlc1tzXS5tYnBz LCAxKTsKKyAgICAgICAgICAgICAgICBhbGxvY19wb3NpdGlvbl9zZXQgKCZkLT5zdGF0ZXNbc10u bWJwcywKKyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGQtPmZvbGxvd3NbcG9z LmluZGV4XS5uZWxlbSk7CiAgICAgICAgICAgICAgIGZvciAoaiA9IDA7IGogPCBkLT5mb2xsb3dz W3Bvcy5pbmRleF0ubmVsZW07ICsraikKLSAgICAgICAgICAgICAgICBpbnNlcnQgKGQtPmZvbGxv d3NbcG9zLmluZGV4XS5lbGVtc1tqXSwgJihkLT5zdGF0ZXNbc10ubWJwcykpOworICAgICAgICAg ICAgICAgIGluc2VydCAoZC0+Zm9sbG93c1twb3MuaW5kZXhdLmVsZW1zW2pdLAorICAgICAgICAg ICAgICAgICAgICAgICAgJihkLT5zdGF0ZXNbc10ubWJwcykpOwogICAgICAgICAgICAgfQogICAg ICAgICB9CiAgICAgICBlbHNlCkBAIC0yOTg0LDE2ICsyOTk0LDYgQEAgdHJhbnNpdF9zdGF0ZV9z aW5nbGVieXRlIChzdHJ1Y3QgZGZhICpkLCBzdGF0ZV9udW0gcywgdW5zaWduZWQgY2hhciBjb25z dCAqKnBwKQogewogICBzdGF0ZV9udW0gKnQ7CiAKLSAgaWYgKCoqcHAgPT0gZW9sYnl0ZSkKLSAg ICB7Ci0gICAgICAvKiBTIGlzIGFsd2F5cyBhbiBpbml0aWFsIHN0YXRlIGluIHRyYW5zaXRfc3Rh dGUsIHNvIHRoZQotICAgICAgICAgdHJhbnNpdGlvbiB0YWJsZSBmb3IgdGhlIHN0YXRlIG11c3Qg aGF2ZSBiZWVuIGJ1aWx0IGFscmVhZHkuICAqLwotICAgICAgYXNzZXJ0IChkLT50cmFuc1tzXSB8 fCBkLT5mYWlsc1tzXSk7Ci0KLSAgICAgICsrKnBwOwotICAgICAgcmV0dXJuIGQtPm5ld2xpbmVz W3NdOwotICAgIH0KLQogICBpZiAoZC0+dHJhbnNbc10pCiAgICAgdCA9IGQtPnRyYW5zW3NdOwog ICBlbHNlIGlmIChkLT5mYWlsc1tzXSkKQEAgLTMwMjAsMTUgKzMwMjAsMTIgQEAgc3RhdGljIHN0 YXRlX251bQogdHJhbnNpdF9zdGF0ZSAoc3RydWN0IGRmYSAqZCwgc3RhdGVfbnVtIHMsIHVuc2ln bmVkIGNoYXIgY29uc3QgKipwcCwKICAgICAgICAgICAgICAgIHVuc2lnbmVkIGNoYXIgY29uc3Qg KmVuZCkKIHsKLSAgc3RhdGVfbnVtIHMxOworICBzdGF0ZV9udW0gczEsIHMyOwogICB3aW50X3Qg d2M7CiAgIGludCBzZXBhcmF0ZV9jb250ZXh0czsKLSAgc3RhdGVfbnVtIHN0YXRlLCBzdGF0ZV9u ZXdsaW5lOwogICBzaXplX3QgaSwgajsKIAogICBpbnQgbWJjbGVuID0gbWJzX3RvX3djaGFyICgm d2MsIChjaGFyIGNvbnN0ICopICpwcCwgZW5kIC0gKnBwLCBkKTsKLSAgaW50IGNvbnRleHQgPSB3 YyA9PSBlb2xieXRlID8gQ1RYX05FV0xJTkUgOiBDVFhfTk9ORTsKLSAgYm9vbCBjb250ZXh0X25l d2xpbmUgPSBjb250ZXh0ID09IENUWF9ORVdMSU5FOwogCiAgIC8qIFRoaXMgc3RhdGUgaGFzIHNv bWUgb3BlcmF0b3JzIHdoaWNoIGNhbiBtYXRjaCBhIG11bHRpYnl0ZSBjaGFyYWN0ZXIuICAqLwog ICBkLT5tYl9mb2xsb3dzLm5lbGVtID0gMDsKQEAgLTMwNTEsNyArMzA0OCw3IEBAIHRyYW5zaXRf c3RhdGUgKHN0cnVjdCBkZmEgKmQsIHN0YXRlX251bSBzLCB1bnNpZ25lZCBjaGFyIGNvbnN0ICoq cHAsCiAgICAgICBmb3IgKGkgPSAwOyBpIDwgZC0+c3RhdGVzW3MxXS5tYnBzLm5lbGVtOyArK2kp CiAgICAgICAgIHsKICAgICAgICAgICBpZiAoIVNVQ0NFRURTX0lOX0NPTlRFWFQgKGQtPnN0YXRl c1tzMV0ubWJwcy5lbGVtc1tpXS5jb25zdHJhaW50LAotICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgICAgZC0+c3RhdGVzW3MxXS5jb250ZXh0LCBjb250ZXh0KSkKKyAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgIGQtPnN0YXRlc1tzMV0uY29udGV4dCwgQ1RYX05PTkUp KQogICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgICAgZm9yIChqID0gMDsgaiA8IGQtPmZv bGxvd3NbZC0+c3RhdGVzW3MxXS5tYnBzLmVsZW1zW2ldLmluZGV4XS5uZWxlbTsKICAgICAgICAg ICAgICAgIGorKykKQEAgLTMwNjAsMTAgKzMwNTcsNyBAQCB0cmFuc2l0X3N0YXRlIChzdHJ1Y3Qg ZGZhICpkLCBzdGF0ZV9udW0gcywgdW5zaWduZWQgY2hhciBjb25zdCAqKnBwLAogICAgICAgICB9 CiAKICAgICAgIHNlcGFyYXRlX2NvbnRleHRzID0gc3RhdGVfc2VwYXJhdGVfY29udGV4dHMgKCZk LT5tYl9mb2xsb3dzKTsKLSAgICAgIGlmIChjb250ZXh0X25ld2xpbmUgJiYgc2VwYXJhdGVfY29u dGV4dHMgJiBDVFhfTkVXTElORSkKLSAgICAgICAgcyA9IHN0YXRlX2luZGV4IChkLCAmZC0+bWJf Zm9sbG93cywgQ1RYX05FV0xJTkUpOwotICAgICAgZWxzZQotICAgICAgICBzID0gc3RhdGVfaW5k ZXggKGQsICZkLT5tYl9mb2xsb3dzLCBzZXBhcmF0ZV9jb250ZXh0cyBeIENUWF9BTlkpOworICAg ICAgcyA9IHN0YXRlX2luZGV4IChkLCAmZC0+bWJfZm9sbG93cywgc2VwYXJhdGVfY29udGV4dHMg XiBDVFhfQU5ZKTsKICAgICAgIHJlYWxsb2NfdHJhbnNfaWZfbmVjZXNzYXJ5IChkLCBzKTsKIAog ICAgICAgcmV0dXJuIHM7CkBAIC0zMDkxLDE3ICszMDg1LDE0IEBAIHRyYW5zaXRfc3RhdGUgKHN0 cnVjdCBkZmEgKmQsIHN0YXRlX251bSBzLCB1bnNpZ25lZCBjaGFyIGNvbnN0ICoqcHAsCiAgICAg ICBkLT5zdGF0ZXNbczFdLm1iX3RyaW5kZXggPSBkLT5tYl90cmNvdW50Kys7CiAgICAgfQogCi0g IHNpemVfdCBtYl9pbmRleCA9IGQtPnN0YXRlc1tzMV0ubWJfdHJpbmRleCA8PCAxIHwgKGNvbnRl eHRfbmV3bGluZQotICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICA/IDEgOiAwKTsKLQogICBpZiAoZC0+bWJfdHJhbnNbc10gPT0gTlVMTCkKICAgICB7 Ci0gICAgICBkLT5tYl90cmFuc1tzXSA9IHhubWFsbG9jICgyICogTUFYX1RSQ09VTlQsIHNpemVv ZiAqZC0+bWJfdHJhbnNbc10pOwotICAgICAgZm9yIChpID0gMDsgaSA8IDIgKiBNQVhfVFJDT1VO VDsgaSsrKQorICAgICAgZC0+bWJfdHJhbnNbc10gPSB4bm1hbGxvYyAoTUFYX1RSQ09VTlQsIHNp emVvZiAqZC0+bWJfdHJhbnNbc10pOworICAgICAgZm9yIChpID0gMDsgaSA8IE1BWF9UUkNPVU5U OyBpKyspCiAgICAgICAgIGQtPm1iX3RyYW5zW3NdW2ldID0gLTE7CiAgICAgfQotICBlbHNlIGlm IChkLT5tYl90cmFuc1tzXVttYl9pbmRleF0gPj0gMCkKLSAgICByZXR1cm4gZC0+bWJfdHJhbnNb c11bbWJfaW5kZXhdOworICBlbHNlIGlmIChkLT5tYl90cmFuc1tzXVtkLT5zdGF0ZXNbczFdLm1i X3RyaW5kZXhdID49IDApCisgICAgcmV0dXJuIGQtPm1iX3RyYW5zW3NdW2QtPnN0YXRlc1tzMV0u bWJfdHJpbmRleF07CiAKICAgaWYgKHMgPCAwKQogICAgIGNvcHkgKCZkLT5zdGF0ZXNbczFdLm1i cHMsICZkLT5tYl9mb2xsb3dzKTsKQEAgLTMxMDksMTcgKzMxMDAsMTIgQEAgdHJhbnNpdF9zdGF0 ZSAoc3RydWN0IGRmYSAqZCwgc3RhdGVfbnVtIHMsIHVuc2lnbmVkIGNoYXIgY29uc3QgKipwcCwK ICAgICBtZXJnZSAoJmQtPnN0YXRlc1tzMV0ubWJwcywgJmQtPnN0YXRlc1tzXS5lbGVtcywgJmQt Pm1iX2ZvbGxvd3MpOwogCiAgIHNlcGFyYXRlX2NvbnRleHRzID0gc3RhdGVfc2VwYXJhdGVfY29u dGV4dHMgKCZkLT5tYl9mb2xsb3dzKTsKLSAgc3RhdGUgPSBzdGF0ZV9pbmRleCAoZCwgJmQtPm1i X2ZvbGxvd3MsIHNlcGFyYXRlX2NvbnRleHRzIF4gQ1RYX0FOWSk7Ci0gIGlmIChzZXBhcmF0ZV9j b250ZXh0cyAmIENUWF9ORVdMSU5FKQotICAgIHN0YXRlX25ld2xpbmUgPSBzdGF0ZV9pbmRleCAo ZCwgJmQtPm1iX2ZvbGxvd3MsIENUWF9ORVdMSU5FKTsKLSAgZWxzZQotICAgIHN0YXRlX25ld2xp bmUgPSBzdGF0ZTsKLSAgcmVhbGxvY190cmFuc19pZl9uZWNlc3NhcnkgKGQsIHN0YXRlX25ld2xp bmUpOworICBzMiA9IHN0YXRlX2luZGV4IChkLCAmZC0+bWJfZm9sbG93cywgc2VwYXJhdGVfY29u dGV4dHMgXiBDVFhfQU5ZKTsKKyAgcmVhbGxvY190cmFuc19pZl9uZWNlc3NhcnkgKGQsIHMyKTsK IAotICBkLT5tYl90cmFuc1tzXVttYl9pbmRleCAmIH4wXSA9IHN0YXRlOwotICBkLT5tYl90cmFu c1tzXVttYl9pbmRleCB8IDFdID0gc3RhdGVfbmV3bGluZTsKKyAgZC0+bWJfdHJhbnNbc11bZC0+ c3RhdGVzW3MxXS5tYl90cmluZGV4XSA9IHMyOwogCi0gIHJldHVybiBjb250ZXh0X25ld2xpbmUg PyBzdGF0ZV9uZXdsaW5lIDogc3RhdGU7CisgIHJldHVybiBzMjsKIH0KIAogLyogVGhlIGluaXRp YWwgc3RhdGUgbWF5IGVuY291bnRlciBhIGJ5dGUgd2hpY2ggaXMgbm90IGEgc2luZ2xlIGJ5dGUg Y2hhcmFjdGVyCkBAIC0zMjQ2LDEwICszMjMyLDggQEAgZGZhZXhlY19tYWluIChzdHJ1Y3QgZGZh ICpkLCBjaGFyIGNvbnN0ICpiZWdpbiwgY2hhciAqZW5kLCBib29sIGFsbG93X25sLAogICAgICAg ICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgfQogCi0gICAgICAgICAgICAgIGlmIChk LT5zdGF0ZXNbc10ubWJwcy5uZWxlbSA9PSAwIHx8ICgqcCA9PSBlb2wgJiYgIWFsbG93X25sKQot ICAgICAgICAgICAgICAgICAgfHwgKCpwID09ICdcbicgJiYgIShzeW50YXhfYml0cyAmIFJFX0RP VF9ORVdMSU5FKSkKLSAgICAgICAgICAgICAgICAgIHx8ICgqcCA9PSAnXDAnICYmIChzeW50YXhf Yml0cyAmIFJFX0RPVF9OT1RfTlVMTCkpCi0gICAgICAgICAgICAgICAgICB8fCAoY2hhciAqKSBw ID49IGVuZCkKKyAgICAgICAgICAgICAgaWYgKGQtPnN0YXRlc1tzXS5tYnBzLm5lbGVtID09IDAK KyAgICAgICAgICAgICAgICAgIHx8IG1icnRvd2NfY2FjaGVbKnBdICE9IFdFT0YgfHwgKGNoYXIg KikgcCA+PSBlbmQpCiAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgLyogSWYg YW4gaW5wdXQgY2hhcmFjdGVyIGRvZXMgbm90IG1hdGNoIEFOWUNIQVIsIGRvIGl0CiAgICAgICAg ICAgICAgICAgICAgICBsaWtlIGEgc2luZ2xlLWJ5dGUgY2hhcmFjdGVyLiAgKi8KQEAgLTMyNTgs OCArMzI0Miw2IEBAIGRmYWV4ZWNfbWFpbiAoc3RydWN0IGRmYSAqZCwgY2hhciBjb25zdCAqYmVn aW4sIGNoYXIgKmVuZCwgYm9vbCBhbGxvd19ubCwKICAgICAgICAgICAgICAgZWxzZQogICAgICAg ICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgIHMgPSB0cmFuc2l0X3N0YXRlIChkLCBzLCAm cCwgKHVuc2lnbmVkIGNoYXIgKikgZW5kKTsKLSAgICAgICAgICAgICAgICAgIGlmIChzID49IDAg JiYgcFstMV0gPT0gZW9sKQotICAgICAgICAgICAgICAgICAgICBubGNvdW50Kys7CiAgICAgICAg ICAgICAgICAgICBtYnAgPSBwOwogICAgICAgICAgICAgICAgICAgdHJhbnMgPSBkLT50cmFuczsK ICAgICAgICAgICAgICAgICB9CkBAIC0zMzExLDEwICszMjkzLDcgQEAgZGZhZXhlY19tYWluIChz dHJ1Y3QgZGZhICpkLCBjaGFyIGNvbnN0ICpiZWdpbiwgY2hhciAqZW5kLCBib29sIGFsbG93X25s LAogCiAgICAgICAgICAgczEgPSBzOwogICAgICAgICAgIGlmICghbXVsdGlieXRlIHx8IGQtPnN0 YXRlc1tzXS5tYnBzLm5lbGVtID09IDAKLSAgICAgICAgICAgICAgfHwgKCpwID09IGVvbCAmJiAh YWxsb3dfbmwpCi0gICAgICAgICAgICAgIHx8ICgqcCA9PSAnXG4nICYmICEoc3ludGF4X2JpdHMg JiBSRV9ET1RfTkVXTElORSkpCi0gICAgICAgICAgICAgIHx8ICgqcCA9PSAnXDAnICYmIChzeW50 YXhfYml0cyAmIFJFX0RPVF9OT1RfTlVMTCkpCi0gICAgICAgICAgICAgIHx8IChjaGFyICopIHAg Pj0gZW5kKQorICAgICAgICAgICAgICB8fCBtYnJ0b3djX2NhY2hlWypwXSAhPSBXRU9GIHx8IChj aGFyICopIHAgPj0gZW5kKQogICAgICAgICAgICAgewogICAgICAgICAgICAgICAvKiBJZiBhIGlu cHV0IGNoYXJhY3RlciBkb2VzIG5vdCBtYXRjaCBBTllDSEFSLCBkbyBpdAogICAgICAgICAgICAg ICAgICBsaWtlIGEgc2luZ2xlLWJ5dGUgY2hhcmFjdGVyLiAgKi8KQEAgLTMzMjMsOCArMzMwMiw2 IEBAIGRmYWV4ZWNfbWFpbiAoc3RydWN0IGRmYSAqZCwgY2hhciBjb25zdCAqYmVnaW4sIGNoYXIg KmVuZCwgYm9vbCBhbGxvd19ubCwKICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICB7CiAgICAg ICAgICAgICAgIHMgPSB0cmFuc2l0X3N0YXRlIChkLCBzLCAmcCwgKHVuc2lnbmVkIGNoYXIgKikg ZW5kKTsKLSAgICAgICAgICAgICAgaWYgKHMgPj0gMCAmJiBwWy0xXSA9PSBlb2wpCi0gICAgICAg ICAgICAgICAgbmxjb3VudCsrOwogICAgICAgICAgICAgICBtYnAgPSBwOwogICAgICAgICAgICAg ICB0cmFucyA9IGQtPnRyYW5zOwogICAgICAgICAgICAgfQotLSAKMS43LjEKCg== --------_578213EE0000000023EF_MULTIPART_MIXED_-- From debbugs-submit-bounces@debbugs.gnu.org Tue Aug 16 03:56:42 2016 Received: (at control) by debbugs.gnu.org; 16 Aug 2016 07:56:42 +0000 Received: from localhost ([127.0.0.1]:58746 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bZZEo-0002N3-Ll for submit@debbugs.gnu.org; Tue, 16 Aug 2016 03:56:42 -0400 Received: from zimbra.cs.ucla.edu ([131.179.128.68]:40048) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bZZEn-0002Mo-Dj for control@debbugs.gnu.org; Tue, 16 Aug 2016 03:56:41 -0400 Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id 0FFCC16121F for ; Tue, 16 Aug 2016 00:56:36 -0700 (PDT) Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10032) with ESMTP id OnIqChx7YM4U for ; Tue, 16 Aug 2016 00:56:35 -0700 (PDT) Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id 66856161278 for ; Tue, 16 Aug 2016 00:56:35 -0700 (PDT) X-Virus-Scanned: amavisd-new at zimbra.cs.ucla.edu Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id fDxeiMoX7oCV for ; Tue, 16 Aug 2016 00:56:35 -0700 (PDT) Received: from [192.168.1.9] (unknown [100.32.155.148]) by zimbra.cs.ucla.edu (Postfix) with ESMTPSA id 4D59216121F for ; Tue, 16 Aug 2016 00:56:35 -0700 (PDT) To: control@debbugs.gnu.org From: Paul Eggert Subject: grep bug report maintenance Organization: UCLA Computer Science Department Message-ID: Date: Tue, 16 Aug 2016 00:56:35 -0700 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.2.0 MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -0.5 (/) X-Debbugs-Envelope-To: control X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.5 (/) tags 23932 + patch From unknown Sat Jun 21 10:34:42 2025 X-Loop: help-debbugs@gnu.org Subject: bug#23932: dfa: use algorithm for single byte character to any single byte character in input text always Resent-From: Norihiro Tanaka Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Tue, 16 Aug 2016 14:36:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 23932 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: 23932@debbugs.gnu.org Received: via spool by 23932-submit@debbugs.gnu.org id=B23932.147135813325681 (code B ref 23932); Tue, 16 Aug 2016 14:36:02 +0000 Received: (at 23932) by debbugs.gnu.org; 16 Aug 2016 14:35:33 +0000 Received: from localhost ([127.0.0.1]:59382 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bZfSm-0006g8-Fz for submit@debbugs.gnu.org; Tue, 16 Aug 2016 10:35:33 -0400 Received: from mailgw04.kcn.ne.jp ([61.86.7.211]:34745) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bZfSj-0006fr-Ol for 23932@debbugs.gnu.org; Tue, 16 Aug 2016 10:35:30 -0400 Received: from mxs01-s (mailgw1.kcn.ne.jp [61.86.15.233]) by mailgw04.kcn.ne.jp (Postfix) with ESMTP id 8AB208060D for <23932@debbugs.gnu.org>; Tue, 16 Aug 2016 23:35:23 +0900 (JST) X-matriXscan-loop-detect: 8cdb33797e14c70cb8f4ecb4c62e5a0b80acca27 Received: from mail09.kcn.ne.jp ([61.86.6.188]) by mxs01-s with ESMTP; Tue, 16 Aug 2016 23:35:22 +0900 (JST) Received: from [10.120.1.69] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail09.kcn.ne.jp (Postfix) with ESMTPA id 0296E1BD0096 for <23932@debbugs.gnu.org>; Tue, 16 Aug 2016 23:35:21 +0900 (JST) Date: Tue, 16 Aug 2016 23:35:22 +0900 From: Norihiro Tanaka In-Reply-To: <20160710185143.23FB.27F6AC2D@kcn.ne.jp> References: <20160710185143.23FB.27F6AC2D@kcn.ne.jp> Message-Id: <20160816233521.C15A.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_57B323B900000000C1CB_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-matriXscan-Sophos-AV: Clean X-matriXscan-Action: Approve X-matriXscan: Uncategorized X-Spam-Score: -0.5 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.5 (/) --------_57B323B900000000C1CB_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit On Sun, 10 Jul 2016 18:51:43 +0900 Norihiro Tanaka wrote: > In multibyte locales, if a pattern start with period expression, > matching is still slow, as transition table is built at run time, > even when next character is single byte in input text. > > This patch changes it into as use algorithm for single byte character to > any single byte character in input text always. If transition table has > been built already and a next character in input text is single byte, > transit to next state by reference of only pre-built transition table, > even if from a state including ANYCHAR. > > $ yes "$(printf 'a%038db\n' 0)" | head -1000000 >in > $ env LC_ALL=C gcc -v > Reading specs from /usr/local/lib/gcc/x86_64-pc-linux-gnu/4.4.7/specs > Target: x86_64-pc-linux-gnu > Configured with: ./configure --with-as=/usr/local/bin/as --with-ld=/usr/local/bin/ld --with-system-zlib --enable-__cxa_atexit > Thread model: posix > gcc version 4.4.7 (GCC) > > patch#21486 is required before this patch. grep will speed up by this > patch additionaly. I updated the patch due to change in bug#21486, and added a patch including a minor change. --------_57B323B900000000C1CB_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII"; name="0001-dfa-use-algorithm-for-single-byte-character-to-any-s.patch" Content-Disposition: attachment; filename="0001-dfa-use-algorithm-for-single-byte-character-to-any-s.patch" Content-Transfer-Encoding: base64 RnJvbSBmZjdkMTcxODY4Yjk4YjcyMDMxMzc1Nzk5NTg5NjlhMmU3NzcxZWRkIE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBOb3JpaGlybyBUYW5ha2EgPG5vcml0bmtAa2NuLm5lLmpwPgpE YXRlOiBUdWUsIDE2IEF1ZyAyMDE2IDE4OjUwOjAzICswOTAwClN1YmplY3Q6IFtQQVRDSCAxLzJd IGRmYTogdXNlIGFsZ29yaXRobSBmb3Igc2luZ2xlIGJ5dGUgY2hhcmFjdGVyIHRvIGFueSBzaW5n bGUgYnl0ZSBjaGFyYWN0ZXIgaW4gaW5wdXQgdGV4dCBhbHdheXMKCkV2ZW4gaW4gbm9uLVVURjgg bG9jYWxlcywgaWYgYSBjaGFyYWN0ZXIgYXQgY3VycmVudCBwb3NpdGlvbiBpbiBpbnB1dAp0ZXh0 IGlzIHNpbmdsZSBieXRlLCB3ZSBjYW4gdXNlIENTRVQgdG8gbWF0Y2ggQU5ZQ0hBUi4KCiogc3Jj L2RmYS5jIChjaGFyY2xhc3NfaW5kZXhfYW55Y2hhcik6IE5ldyB2YXIuICBDYWNoZSBpbmRleCBv ZiBDU0VUCmZvciBBTllDSEFSLgoobGV4KTogTWFrZSBDU0VUIGZvciBBTllDSEFSLgooc3RhdGVf aW5kZXgpOiBTaW1wbGlmeS4KKGRmYXN0YXRlKTogQ29uc2lkZXIgQ1NFVCBmb3IgQU5ZQ0hBUi4K KHRyYW5zaXRfc3RhdGVfc2luZ2xlYnl0ZSwgdHJhbnNpdF9zdGF0ZSk6IFJlbW92ZSBoYW5kbGlu ZyBmb3IgZW9sYnl0ZSwKYXMgd2UgYXNzdW1lIHRoYXQgZW9sYnl0ZSBkb2VzIG5vdCBhcHBlYXIg YXQgY3VycmVudCBwb3NpdGlvbi4KKGRmYWV4ZWNfbWFpbik6IHVzZSBhbGdvcml0aG0gZm9yIHNp bmdsZSBieXRlIGNoYXJhY3RlciB0byBhbnkgc2luZ2xlCmJ5dGUgY2hhcmFjdGVyIGluIGlucHV0 IHRleHQgYWx3YXlzLgotLS0KIHNyYy9kZmEuYyB8ICAxMjYgKysrKysrKysrKysrKysrKysrKysr KysrLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQogMSBmaWxlcyBjaGFuZ2Vk LCA1MCBpbnNlcnRpb25zKCspLCA3NiBkZWxldGlvbnMoLSkKCmRpZmYgLS1naXQgYS9zcmMvZGZh LmMgYi9zcmMvZGZhLmMKaW5kZXggYjY0YTE3Ni4uNzFhOGFiNyAxMDA2NDQKLS0tIGEvc3JjL2Rm YS5jCisrKyBiL3NyYy9kZmEuYwpAQCAtNzksNiArNzksOCBAQCBlbnVtCiAgIENIQVJDTEFTU19X T1JEUyA9IChOT1RDSEFSICsgQ0hBUkNMQVNTX1dPUkRfQklUUyAtIDEpIC8gQ0hBUkNMQVNTX1dP UkRfQklUUwogfTsKIAorc3RhdGljIHNpemVfdCBjaGFyY2xhc3NfaW5kZXhfYW55Y2hhciA9IC0x OworCiAvKiBTZXRzIG9mIHVuc2lnbmVkIGNoYXJhY3RlcnMgYXJlIHN0b3JlZCBhcyBiaXQgdmVj dG9ycyBpbiBhcnJheXMgb2YgaW50cy4gICovCiB0eXBlZGVmIGNoYXJjbGFzc193b3JkIGNoYXJj bGFzc1tDSEFSQ0xBU1NfV09SRFNdOwogCkBAIC0xNDMwLDIxICsxNDMyLDI1IEBAIGxleCAodm9p ZCkKICAgICAgICAgY2FzZSAnLic6CiAgICAgICAgICAgaWYgKGJhY2tzbGFzaCkKICAgICAgICAg ICAgIGdvdG8gbm9ybWFsX2NoYXI7Ci0gICAgICAgICAgaWYgKGRmYS0+bXVsdGlieXRlKQorICAg ICAgICAgIGlmIChjaGFyY2xhc3NfaW5kZXhfYW55Y2hhciA9PSAoc2l6ZV90KSAtMSkKICAgICAg ICAgICAgIHsKLSAgICAgICAgICAgICAgLyogSW4gbXVsdGlieXRlIGVudmlyb25tZW50IHBlcmlv ZCBtdXN0IG1hdGNoIHdpdGggYSBzaW5nbGUKLSAgICAgICAgICAgICAgICAgY2hhcmFjdGVyIG5v dCBhIGJ5dGUuICBTbyB3ZSB1c2UgQU5ZQ0hBUi4gICovCi0gICAgICAgICAgICAgIGxhc3RzdGFy dCA9IGZhbHNlOwotICAgICAgICAgICAgICByZXR1cm4gbGFzdHRvayA9IEFOWUNIQVI7CisgICAg ICAgICAgICAgIHplcm9zZXQgKGNjbCk7CisgICAgICAgICAgICAgIG5vdHNldCAoY2NsKTsKKyAg ICAgICAgICAgICAgaWYgKCEoc3ludGF4X2JpdHMgJiBSRV9ET1RfTkVXTElORSkpCisgICAgICAg ICAgICAgICAgY2xyYml0ICgnXG4nLCBjY2wpOworICAgICAgICAgICAgICBpZiAoc3ludGF4X2Jp dHMgJiBSRV9ET1RfTk9UX05VTEwpCisgICAgICAgICAgICAgICAgY2xyYml0ICgnXDAnLCBjY2wp OworICAgICAgICAgICAgICBpZiAoZGZhLT5tdWx0aWJ5dGUpCisgICAgICAgICAgICAgICAgewor ICAgICAgICAgICAgICAgICAgZm9yIChjMiA9IDA7IGMyIDwgTk9UQ0hBUjsgKytjMikKKyAgICAg ICAgICAgICAgICAgICAgaWYgKG1icnRvd2NfY2FjaGVbYzJdID09IFdFT0YpCisgICAgICAgICAg ICAgICAgICAgICAgY2xyYml0IChjMiwgY2NsKTsKKyAgICAgICAgICAgICAgICB9CisgICAgICAg ICAgICAgIGNoYXJjbGFzc19pbmRleF9hbnljaGFyID0gY2hhcmNsYXNzX2luZGV4IChjY2wpOwog ICAgICAgICAgICAgfQotICAgICAgICAgIHplcm9zZXQgKGNjbCk7Ci0gICAgICAgICAgbm90c2V0 IChjY2wpOwotICAgICAgICAgIGlmICghKHN5bnRheF9iaXRzICYgUkVfRE9UX05FV0xJTkUpKQot ICAgICAgICAgICAgY2xyYml0ICgnXG4nLCBjY2wpOwotICAgICAgICAgIGlmIChzeW50YXhfYml0 cyAmIFJFX0RPVF9OT1RfTlVMTCkKLSAgICAgICAgICAgIGNscmJpdCAoJ1wwJywgY2NsKTsKICAg ICAgICAgICBsYXN0c3RhcnQgPSBmYWxzZTsKLSAgICAgICAgICByZXR1cm4gbGFzdHRvayA9IENT RVQgKyBjaGFyY2xhc3NfaW5kZXggKGNjbCk7CisgICAgICAgICAgcmV0dXJuIGxhc3R0b2sgPQor ICAgICAgICAgICAgZGZhLT5tdWx0aWJ5dGUgPyBBTllDSEFSIDogQ1NFVCArIGNoYXJjbGFzc19p bmRleF9hbnljaGFyOwogCiAgICAgICAgIGNhc2UgJ3MnOgogICAgICAgICBjYXNlICdTJzoKQEAg LTIxMTMsNyArMjExOSw3IEBAIHN0YXRlX2luZGV4IChzdHJ1Y3QgZGZhICpkLCBwb3NpdGlvbl9z ZXQgY29uc3QgKnMsIGludCBjb250ZXh0KQogICAgICAgICB9CiAgICAgICBlbHNlIGlmIChkLT50 b2tlbnNbcy0+ZWxlbXNbal0uaW5kZXhdID09IEJBQ0tSRUYpCiAgICAgICAgIGNvbnN0cmFpbnQg PSBOT19DT05TVFJBSU5UOwotICAgICAgaWYgKGQtPm11bHRpYnl0ZSAmJiBkLT50b2tlbnNbcy0+ ZWxlbXNbal0uaW5kZXhdID09IEFOWUNIQVIpCisgICAgICBpZiAoZC0+dG9rZW5zW3MtPmVsZW1z W2pdLmluZGV4XSA9PSBBTllDSEFSKQogICAgICAgICB7CiAgICAgICAgICAgaW50IGFjY2VwdGFi bGUKICAgICAgICAgICAgID0gKChTVUNDRUVEU19JTl9DT05URVhUIChjLCBjb250ZXh0LCBDVFhf TkVXTElORSkKQEAgLTI1OTAsMTMgKzI1OTYsMTUgQEAgZGZhc3RhdGUgKHN0YXRlX251bSBzLCBz dHJ1Y3QgZGZhICpkLCBzdGF0ZV9udW0gdHJhbnNbXSkKICAgICAgICAgc2V0Yml0IChkLT50b2tl bnNbcG9zLmluZGV4XSwgbWF0Y2hlcyk7CiAgICAgICBlbHNlIGlmIChkLT50b2tlbnNbcG9zLmlu ZGV4XSA+PSBDU0VUKQogICAgICAgICBjb3B5c2V0IChkLT5jaGFyY2xhc3Nlc1tkLT50b2tlbnNb cG9zLmluZGV4XSAtIENTRVRdLCBtYXRjaGVzKTsKLSAgICAgIGVsc2UgaWYgKGQtPm11bHRpYnl0 ZSAmJiBkLT50b2tlbnNbcG9zLmluZGV4XSA9PSBBTllDSEFSKQorICAgICAgZWxzZSBpZiAoZC0+ dG9rZW5zW3Bvcy5pbmRleF0gPT0gQU5ZQ0hBUikKICAgICAgICAgewotICAgICAgICAgIC8qIEFO WUNIQVIgbXVzdCBtYXRjaCBhIHNpbmdsZSBjaGFyYWN0ZXIsIHNvIHB1dCBpdCB0bwotICAgICAg ICAgICAgIEQtPnN0YXRlc1tzXS5tYnBzIHdoaWNoIGNvbnRhaW5zIHRoZSBwb3NpdGlvbnMgd2hp Y2ggY2FuCi0gICAgICAgICAgICAgbWF0Y2ggd2l0aCBhIHNpbmdsZSBjaGFyYWN0ZXIgbm90IGEg Ynl0ZS4gIElmIGFsbAotICAgICAgICAgICAgIHBvc2l0aW9ucyB3aXRoIEFOWUNIQVIgZG8gbm90 IGRlcGVuZCBvbiB0aGUgY29udGV4dCBvZgotICAgICAgICAgICAgIHRoZSBuZXh0IGNoYXJhY3Rl ciwgcHV0IGl0cyBmb2xsb3dzIGluc3RlYWQgdG8KKyAgICAgICAgICBjb3B5c2V0IChkLT5jaGFy Y2xhc3Nlc1tjaGFyY2xhc3NfaW5kZXhfYW55Y2hhcl0sIG1hdGNoZXMpOworCisgICAgICAgICAg LyogQU5ZQ0hBUiBtdXN0IG1hdGNoIHdpdGggYSBzaW5nbGUgY2hhcmFjdGVyLCBzbyB3ZSBtdXN0 IHB1dAorICAgICAgICAgICAgIGl0IHRvIEQtPnN0YXRlc1tzXS5tYnBzIHdoaWNoIGNvbnRhaW5z IHRoZSBwb3NpdGlvbnMgd2hpY2gKKyAgICAgICAgICAgICBjYW4gbWF0Y2ggd2l0aCBhIHNpbmds ZSBjaGFyYWN0ZXIgbm90IGEgYnl0ZS4gIElmIGFsbAorICAgICAgICAgICAgIHBvc2l0aW9ucyB3 aGljaCBoYXMgQU5ZQ0hBUiBkb2VzIG5vdCBkZXBlbmQgb24gY29udGV4dCBvZgorICAgICAgICAg ICAgIG5leHQgY2hhcmFjdGVyLCB3ZSBwdXQgdGhlIGZvbGxvd3MgaW5zdGVhZCBvZiBpdCB0bwog ICAgICAgICAgICAgIEQtPnN0YXRlc1tzXS5tYnBzIHRvIG9wdGltaXplLiAgKi8KICAgICAgICAg ICBpZiAoZC0+c3RhdGVzW3NdLmN1cnJfZGVwZW5kZW50KQogICAgICAgICAgICAgewpAQCAtMjYw OCw5ICsyNjE2LDExIEBAIGRmYXN0YXRlIChzdGF0ZV9udW0gcywgc3RydWN0IGRmYSAqZCwgc3Rh dGVfbnVtIHRyYW5zW10pCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAg ZC0+c3RhdGVzW3NdLmNvbnRleHQsIENUWF9BTlkpKQogICAgICAgICAgICAgewogICAgICAgICAg ICAgICBpZiAoZC0+c3RhdGVzW3NdLm1icHMubmVsZW0gPT0gMCkKLSAgICAgICAgICAgICAgICBh bGxvY19wb3NpdGlvbl9zZXQgKCZkLT5zdGF0ZXNbc10ubWJwcywgMSk7Ci0gICAgICAgICAgICAg IGZvciAoaiA9IDA7IGogPCBkLT5mb2xsb3dzW3Bvcy5pbmRleF0ubmVsZW07IGorKykKLSAgICAg ICAgICAgICAgICBpbnNlcnQgKGQtPmZvbGxvd3NbcG9zLmluZGV4XS5lbGVtc1tqXSwgJmQtPnN0 YXRlc1tzXS5tYnBzKTsKKyAgICAgICAgICAgICAgICBhbGxvY19wb3NpdGlvbl9zZXQgKCZkLT5z dGF0ZXNbc10ubWJwcywKKyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGQtPmZv bGxvd3NbcG9zLmluZGV4XS5uZWxlbSk7CisgICAgICAgICAgICAgIGZvciAoaiA9IDA7IGogPCBk LT5mb2xsb3dzW3Bvcy5pbmRleF0ubmVsZW07ICsraikKKyAgICAgICAgICAgICAgICBpbnNlcnQg KGQtPmZvbGxvd3NbcG9zLmluZGV4XS5lbGVtc1tqXSwKKyAgICAgICAgICAgICAgICAgICAgICAg ICYoZC0+c3RhdGVzW3NdLm1icHMpKTsKICAgICAgICAgICAgIH0KICAgICAgICAgfQogICAgICAg ZWxzZQpAQCAtMjk4NiwxNiArMjk5Niw2IEBAIHRyYW5zaXRfc3RhdGVfc2luZ2xlYnl0ZSAoc3Ry dWN0IGRmYSAqZCwgc3RhdGVfbnVtIHMsIHVuc2lnbmVkIGNoYXIgY29uc3QgKipwcCkKIHsKICAg c3RhdGVfbnVtICp0OwogCi0gIGlmICgqKnBwID09IGVvbGJ5dGUpCi0gICAgewotICAgICAgLyog UyBpcyBhbHdheXMgYW4gaW5pdGlhbCBzdGF0ZSBpbiB0cmFuc2l0X3N0YXRlLCBzbyB0aGUKLSAg ICAgICAgIHRyYW5zaXRpb24gdGFibGUgZm9yIHRoZSBzdGF0ZSBtdXN0IGhhdmUgYmVlbiBidWls dCBhbHJlYWR5LiAgKi8KLSAgICAgIGFzc2VydCAoZC0+dHJhbnNbc10gfHwgZC0+ZmFpbHNbc10p OwotCi0gICAgICArKypwcDsKLSAgICAgIHJldHVybiBkLT5uZXdsaW5lc1tzXTsKLSAgICB9Ci0K ICAgaWYgKGQtPnRyYW5zW3NdKQogICAgIHQgPSBkLT50cmFuc1tzXTsKICAgZWxzZSBpZiAoZC0+ ZmFpbHNbc10pCkBAIC0zMDIyLDE1ICszMDIyLDEyIEBAIHN0YXRpYyBzdGF0ZV9udW0KIHRyYW5z aXRfc3RhdGUgKHN0cnVjdCBkZmEgKmQsIHN0YXRlX251bSBzLCB1bnNpZ25lZCBjaGFyIGNvbnN0 ICoqcHAsCiAgICAgICAgICAgICAgICB1bnNpZ25lZCBjaGFyIGNvbnN0ICplbmQpCiB7Ci0gIHN0 YXRlX251bSBzMTsKKyAgc3RhdGVfbnVtIHMxLCBzMjsKICAgd2ludF90IHdjOwogICBpbnQgc2Vw YXJhdGVfY29udGV4dHM7Ci0gIHN0YXRlX251bSBzdGF0ZSwgc3RhdGVfbmV3bGluZSwgbWJfaW5k ZXg7CiAgIHNpemVfdCBpLCBqOwogCiAgIGludCBtYmNsZW4gPSBtYnNfdG9fd2NoYXIgKCZ3Yywg KGNoYXIgY29uc3QgKikgKnBwLCBlbmQgLSAqcHAsIGQpOwotICBpbnQgY29udGV4dCA9IHdjID09 IGVvbGJ5dGUgPyBDVFhfTkVXTElORSA6IENUWF9OT05FOwotICBib29sIGNvbnRleHRfbmV3bGlu ZSA9IGNvbnRleHQgPT0gQ1RYX05FV0xJTkU7CiAKICAgLyogVGhpcyBzdGF0ZSBoYXMgc29tZSBv cGVyYXRvcnMgd2hpY2ggY2FuIG1hdGNoIGEgbXVsdGlieXRlIGNoYXJhY3Rlci4gICovCiAgIGQt Pm1iX2ZvbGxvd3MubmVsZW0gPSAwOwpAQCAtMzA1Miw3ICszMDQ5LDcgQEAgdHJhbnNpdF9zdGF0 ZSAoc3RydWN0IGRmYSAqZCwgc3RhdGVfbnVtIHMsIHVuc2lnbmVkIGNoYXIgY29uc3QgKipwcCwK ICAgICAgIGZvciAoaSA9IDA7IGkgPCBkLT5zdGF0ZXNbczFdLm1icHMubmVsZW07IGkrKykKICAg ICAgICAgewogICAgICAgICAgIGlmICghU1VDQ0VFRFNfSU5fQ09OVEVYVCAoZC0+c3RhdGVzW3Mx XS5tYnBzLmVsZW1zW2ldLmNvbnN0cmFpbnQsCi0gICAgICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICBkLT5zdGF0ZXNbczFdLmNvbnRleHQsIGNvbnRleHQpKQorICAgICAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgZC0+c3RhdGVzW3MxXS5jb250ZXh0LCBDVFhfTk9ORSkpCiAg ICAgICAgICAgICBjb250aW51ZTsKICAgICAgICAgICBmb3IgKGogPSAwOyBqIDwgZC0+Zm9sbG93 c1tkLT5zdGF0ZXNbczFdLm1icHMuZWxlbXNbaV0uaW5kZXhdLm5lbGVtOwogICAgICAgICAgICAg ICAgaisrKQpAQCAtMzA2MSwxMCArMzA1OCw3IEBAIHRyYW5zaXRfc3RhdGUgKHN0cnVjdCBkZmEg KmQsIHN0YXRlX251bSBzLCB1bnNpZ25lZCBjaGFyIGNvbnN0ICoqcHAsCiAgICAgICAgIH0KIAog ICAgICAgc2VwYXJhdGVfY29udGV4dHMgPSBzdGF0ZV9zZXBhcmF0ZV9jb250ZXh0cyAoJmQtPm1i X2ZvbGxvd3MpOwotICAgICAgaWYgKGNvbnRleHRfbmV3bGluZSAmJiBzZXBhcmF0ZV9jb250ZXh0 cyAmIENUWF9ORVdMSU5FKQotICAgICAgICBzID0gc3RhdGVfaW5kZXggKGQsICZkLT5tYl9mb2xs b3dzLCBDVFhfTkVXTElORSk7Ci0gICAgICBlbHNlCi0gICAgICAgIHMgPSBzdGF0ZV9pbmRleCAo ZCwgJmQtPm1iX2ZvbGxvd3MsIHNlcGFyYXRlX2NvbnRleHRzIF4gQ1RYX0FOWSk7CisgICAgICBz ID0gc3RhdGVfaW5kZXggKGQsICZkLT5tYl9mb2xsb3dzLCBzZXBhcmF0ZV9jb250ZXh0cyBeIENU WF9BTlkpOwogICAgICAgcmVhbGxvY190cmFuc19pZl9uZWNlc3NhcnkgKGQsIHMpOwogCiAgICAg ICByZXR1cm4gczsKQEAgLTMwNzcsMTEgKzMwNzEsMTEgQEAgdHJhbnNpdF9zdGF0ZSAoc3RydWN0 IGRmYSAqZCwgc3RhdGVfbnVtIHMsIHVuc2lnbmVkIGNoYXIgY29uc3QgKipwcCwKICAgICB7CiAg ICAgICBpZiAoTUFYX1RSQ09VTlQgPD0gZC0+bWJfdHJjb3VudCkKICAgICAgICAgewotICAgICAg ICAgIHN0YXRlX251bSBzMjsKLSAgICAgICAgICBmb3IgKHMyID0gLTE7IHMyIDwgZC0+dHJhbGxv YzsgczIrKykKKyAgICAgICAgICBzdGF0ZV9udW0gczM7CisgICAgICAgICAgZm9yIChzMyA9IC0x OyBzMyA8IGQtPnRyYWxsb2M7IHMzKyspCiAgICAgICAgICAgICB7Ci0gICAgICAgICAgICAgIGZy ZWUgKGQtPm1iX3RyYW5zW3MyXSk7Ci0gICAgICAgICAgICAgIGQtPm1iX3RyYW5zW3MyXSA9IE5V TEw7CisgICAgICAgICAgICAgIGZyZWUgKGQtPm1iX3RyYW5zW3MzXSk7CisgICAgICAgICAgICAg IGQtPm1iX3RyYW5zW3MzXSA9IE5VTEw7CiAgICAgICAgICAgICB9CiAKICAgICAgICAgICBmb3Ig KGkgPSAwOyBpIDwgZC0+c2luZGV4OyBpKyspCkBAIC0zMDkxLDIyICszMDg1LDE2IEBAIHRyYW5z aXRfc3RhdGUgKHN0cnVjdCBkZmEgKmQsIHN0YXRlX251bSBzLCB1bnNpZ25lZCBjaGFyIGNvbnN0 ICoqcHAsCiAgICAgICBkLT5zdGF0ZXNbczFdLm1iX3RyaW5kZXggPSBkLT5tYl90cmNvdW50Kys7 CiAgICAgfQogCi0gIG1iX2luZGV4ID0gZC0+c3RhdGVzW3MxXS5tYl90cmluZGV4ICogMjsKLQog ICBpZiAoISBkLT5tYl90cmFuc1tzXSkKICAgICB7CiAgICAgICBlbnVtIHsgVFJBTlNQVFJfU0la RSA9IHNpemVvZiAqZC0+bWJfdHJhbnNbc10gfTsKLSAgICAgIGVudW0geyBUUkFOU0FMTE9DX1NJ WkUgPSAyICogTUFYX1RSQ09VTlQgKiBUUkFOU1BUUl9TSVpFIH07CisgICAgICBlbnVtIHsgVFJB TlNBTExPQ19TSVpFID0gTUFYX1RSQ09VTlQgKiBUUkFOU1BUUl9TSVpFIH07CiAgICAgICBkLT5t Yl90cmFuc1tzXSA9IHhtYWxsb2MgKFRSQU5TQUxMT0NfU0laRSk7Ci0gICAgICBmb3IgKGkgPSAw OyBpIDwgMiAqIE1BWF9UUkNPVU5UOyBpKyspCisgICAgICBmb3IgKGkgPSAwOyBpIDwgTUFYX1RS Q09VTlQ7IGkrKykKICAgICAgICAgZC0+bWJfdHJhbnNbc11baV0gPSAtMTsKICAgICB9Ci0gIGVs c2UKLSAgICB7Ci0gICAgICBzdGF0ZSA9IGQtPm1iX3RyYW5zW3NdW21iX2luZGV4ICsgY29udGV4 dF9uZXdsaW5lXTsKLSAgICAgIGlmICgwIDw9IHN0YXRlKQotICAgICAgICByZXR1cm4gc3RhdGU7 Ci0gICAgfQorICBlbHNlIGlmIChkLT5tYl90cmFuc1tzXVtkLT5zdGF0ZXNbczFdLm1iX3RyaW5k ZXhdID49IDApCisgICAgcmV0dXJuIGQtPm1iX3RyYW5zW3NdW2QtPnN0YXRlc1tzMV0ubWJfdHJp bmRleF07CiAKICAgaWYgKHMgPCAwKQogICAgIGNvcHkgKCZkLT5zdGF0ZXNbczFdLm1icHMsICZk LT5tYl9mb2xsb3dzKTsKQEAgLTMxMTQsMTcgKzMxMDIsMTIgQEAgdHJhbnNpdF9zdGF0ZSAoc3Ry dWN0IGRmYSAqZCwgc3RhdGVfbnVtIHMsIHVuc2lnbmVkIGNoYXIgY29uc3QgKipwcCwKICAgICBt ZXJnZSAoJmQtPnN0YXRlc1tzMV0ubWJwcywgJmQtPnN0YXRlc1tzXS5lbGVtcywgJmQtPm1iX2Zv bGxvd3MpOwogCiAgIHNlcGFyYXRlX2NvbnRleHRzID0gc3RhdGVfc2VwYXJhdGVfY29udGV4dHMg KCZkLT5tYl9mb2xsb3dzKTsKLSAgc3RhdGUgPSBzdGF0ZV9pbmRleCAoZCwgJmQtPm1iX2ZvbGxv d3MsIHNlcGFyYXRlX2NvbnRleHRzIF4gQ1RYX0FOWSk7Ci0gIGlmIChzZXBhcmF0ZV9jb250ZXh0 cyAmIENUWF9ORVdMSU5FKQotICAgIHN0YXRlX25ld2xpbmUgPSBzdGF0ZV9pbmRleCAoZCwgJmQt Pm1iX2ZvbGxvd3MsIENUWF9ORVdMSU5FKTsKLSAgZWxzZQotICAgIHN0YXRlX25ld2xpbmUgPSBz dGF0ZTsKLSAgcmVhbGxvY190cmFuc19pZl9uZWNlc3NhcnkgKGQsIHN0YXRlX25ld2xpbmUpOwor ICBzMiA9IHN0YXRlX2luZGV4IChkLCAmZC0+bWJfZm9sbG93cywgc2VwYXJhdGVfY29udGV4dHMg XiBDVFhfQU5ZKTsKKyAgcmVhbGxvY190cmFuc19pZl9uZWNlc3NhcnkgKGQsIHMyKTsKIAotICBk LT5tYl90cmFuc1tzXVttYl9pbmRleF0gPSBzdGF0ZTsKLSAgZC0+bWJfdHJhbnNbc11bbWJfaW5k ZXggKyAxXSA9IHN0YXRlX25ld2xpbmU7CisgIGQtPm1iX3RyYW5zW3NdW2QtPnN0YXRlc1tzMV0u bWJfdHJpbmRleF0gPSBzMjsKIAotICByZXR1cm4gY29udGV4dF9uZXdsaW5lID8gc3RhdGVfbmV3 bGluZSA6IHN0YXRlOworICByZXR1cm4gczI7CiB9CiAKIC8qIFRoZSBpbml0aWFsIHN0YXRlIG1h eSBlbmNvdW50ZXIgYSBieXRlIHdoaWNoIGlzIG5vdCBhIHNpbmdsZSBieXRlIGNoYXJhY3RlcgpA QCAtMzI1MSwxMCArMzIzNCw4IEBAIGRmYWV4ZWNfbWFpbiAoc3RydWN0IGRmYSAqZCwgY2hhciBj b25zdCAqYmVnaW4sIGNoYXIgKmVuZCwgYm9vbCBhbGxvd19ubCwKICAgICAgICAgICAgICAgICAg ICAgfQogICAgICAgICAgICAgICAgIH0KIAotICAgICAgICAgICAgICBpZiAoZC0+c3RhdGVzW3Nd Lm1icHMubmVsZW0gPT0gMCB8fCAoKnAgPT0gZW9sICYmICFhbGxvd19ubCkKLSAgICAgICAgICAg ICAgICAgIHx8ICgqcCA9PSAnXG4nICYmICEoc3ludGF4X2JpdHMgJiBSRV9ET1RfTkVXTElORSkp Ci0gICAgICAgICAgICAgICAgICB8fCAoKnAgPT0gJ1wwJyAmJiAoc3ludGF4X2JpdHMgJiBSRV9E T1RfTk9UX05VTEwpKQotICAgICAgICAgICAgICAgICAgfHwgKGNoYXIgKikgcCA+PSBlbmQpCisg ICAgICAgICAgICAgIGlmIChkLT5zdGF0ZXNbc10ubWJwcy5uZWxlbSA9PSAwCisgICAgICAgICAg ICAgICAgICB8fCBtYnJ0b3djX2NhY2hlWypwXSAhPSBXRU9GIHx8IChjaGFyICopIHAgPj0gZW5k KQogICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgIC8qIElmIGFuIGlucHV0IGNo YXJhY3RlciBkb2VzIG5vdCBtYXRjaCBBTllDSEFSLCBkbyBpdAogICAgICAgICAgICAgICAgICAg ICAgbGlrZSBhIHNpbmdsZS1ieXRlIGNoYXJhY3Rlci4gICovCkBAIC0zMjYzLDggKzMyNDQsNiBA QCBkZmFleGVjX21haW4gKHN0cnVjdCBkZmEgKmQsIGNoYXIgY29uc3QgKmJlZ2luLCBjaGFyICpl bmQsIGJvb2wgYWxsb3dfbmwsCiAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICB7 CiAgICAgICAgICAgICAgICAgICBzID0gdHJhbnNpdF9zdGF0ZSAoZCwgcywgJnAsICh1bnNpZ25l ZCBjaGFyICopIGVuZCk7Ci0gICAgICAgICAgICAgICAgICBpZiAocyA+PSAwICYmIHBbLTFdID09 IGVvbCkKLSAgICAgICAgICAgICAgICAgICAgbmxjb3VudCsrOwogICAgICAgICAgICAgICAgICAg bWJwID0gcDsKICAgICAgICAgICAgICAgICAgIHRyYW5zID0gZC0+dHJhbnM7CiAgICAgICAgICAg ICAgICAgfQpAQCAtMzMyMSwxMCArMzMwMCw3IEBAIGRmYWV4ZWNfbWFpbiAoc3RydWN0IGRmYSAq ZCwgY2hhciBjb25zdCAqYmVnaW4sIGNoYXIgKmVuZCwgYm9vbCBhbGxvd19ubCwKIAogICAgICAg ICAgIHMxID0gczsKICAgICAgICAgICBpZiAoIW11bHRpYnl0ZSB8fCBkLT5zdGF0ZXNbc10ubWJw cy5uZWxlbSA9PSAwCi0gICAgICAgICAgICAgIHx8ICgqcCA9PSBlb2wgJiYgIWFsbG93X25sKQot ICAgICAgICAgICAgICB8fCAoKnAgPT0gJ1xuJyAmJiAhKHN5bnRheF9iaXRzICYgUkVfRE9UX05F V0xJTkUpKQotICAgICAgICAgICAgICB8fCAoKnAgPT0gJ1wwJyAmJiAoc3ludGF4X2JpdHMgJiBS RV9ET1RfTk9UX05VTEwpKQotICAgICAgICAgICAgICB8fCAoY2hhciAqKSBwID49IGVuZCkKKyAg ICAgICAgICAgICAgfHwgbWJydG93Y19jYWNoZVsqcF0gIT0gV0VPRiB8fCAoY2hhciAqKSBwID49 IGVuZCkKICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgLyogSWYgYSBpbnB1dCBjaGFyYWN0 ZXIgZG9lcyBub3QgbWF0Y2ggQU5ZQ0hBUiwgZG8gaXQKICAgICAgICAgICAgICAgICAgbGlrZSBh IHNpbmdsZS1ieXRlIGNoYXJhY3Rlci4gICovCkBAIC0zMzMzLDggKzMzMDksNiBAQCBkZmFleGVj X21haW4gKHN0cnVjdCBkZmEgKmQsIGNoYXIgY29uc3QgKmJlZ2luLCBjaGFyICplbmQsIGJvb2wg YWxsb3dfbmwsCiAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgewogICAgICAgICAgICAgICBz ID0gdHJhbnNpdF9zdGF0ZSAoZCwgcywgJnAsICh1bnNpZ25lZCBjaGFyICopIGVuZCk7Ci0gICAg ICAgICAgICAgIGlmIChzID49IDAgJiYgcFstMV0gPT0gZW9sKQotICAgICAgICAgICAgICAgIG5s Y291bnQrKzsKICAgICAgICAgICAgICAgbWJwID0gcDsKICAgICAgICAgICAgICAgdHJhbnMgPSBk LT50cmFuczsKICAgICAgICAgICAgIH0KLS0gCjEuNy4xCgo= --------_57B323B900000000C1CB_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII"; name="0002-dfa-avoid-invalid-character-matches-period.patch" Content-Disposition: attachment; filename="0002-dfa-avoid-invalid-character-matches-period.patch" Content-Transfer-Encoding: base64 RnJvbSBlOTI4NmI3ZTkyZjA5NGI3YzAzNDJjNmEzOGM2N2Q4ZDMwYzJhMGRlIE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBOb3JpaGlybyBUYW5ha2EgPG5vcml0bmtAa2NuLm5lLmpwPgpE YXRlOiBUdWUsIDE2IEF1ZyAyMDE2IDIzOjIzOjE5ICswOTAwClN1YmplY3Q6IFtQQVRDSCAyLzJd IGRmYTogYXZvaWQgaW52YWxpZCBjaGFyYWN0ZXIgbWF0Y2hlcyBwZXJpb2QKCiogZGZhLmMgKHRy YW5zaXRfc3RhdGUpOiBBdm9pZCBpbnZhbGlkIGNoYXJhY3RlciBtYXRjaGVzIHBlcmlvZC4KLS0t CiBzcmMvZGZhLmMgfCAgICA2ICsrKysrKwogMSBmaWxlcyBjaGFuZ2VkLCA2IGluc2VydGlvbnMo KyksIDAgZGVsZXRpb25zKC0pCgpkaWZmIC0tZ2l0IGEvc3JjL2RmYS5jIGIvc3JjL2RmYS5jCmlu ZGV4IDcxYThhYjcuLmY3OWQ2N2UgMTAwNjQ0Ci0tLSBhL3NyYy9kZmEuYworKysgYi9zcmMvZGZh LmMKQEAgLTMwMzksNiArMzAzOSwxMiBAQCB0cmFuc2l0X3N0YXRlIChzdHJ1Y3QgZGZhICpkLCBz dGF0ZV9udW0gcywgdW5zaWduZWQgY2hhciBjb25zdCAqKnBwLAogICAgIHMgPSB0cmFuc2l0X3N0 YXRlX3NpbmdsZWJ5dGUgKGQsIHMsIHBwKTsKICAgKnBwICs9IG1iY2xlbiAtIGk7CiAKKyAgaWYg KHdjID09IFdFT0YpCisgICAgeworICAgICAgLyogSXQgaXMgaW52YWxpZCBjaGFyYWN0ZXIuICBU aGVuIEFOWUNIQVIgaXMgbm90IGFjY2VwdGVkLiAgKi8KKyAgICAgIHJldHVybiBzOworICAgIH0K KwogICBpZiAoZC0+c3RhdGVzW3MxXS5jdXJyX2RlcGVuZGVudCkKICAgICB7CiAgICAgICBpZiAo cyA8IDApCi0tIAoxLjcuMQoK --------_57B323B900000000C1CB_MULTIPART_MIXED_-- From unknown Sat Jun 21 10:34:42 2025 X-Loop: help-debbugs@gnu.org Subject: bug#23932: dfa: use algorithm for single byte character to any single byte character in input text always Resent-From: Norihiro Tanaka Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Wed, 17 Aug 2016 13:06:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 23932 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: Norihiro Tanaka Cc: 23932@debbugs.gnu.org Received: via spool by 23932-submit@debbugs.gnu.org id=B23932.147143913032193 (code B ref 23932); Wed, 17 Aug 2016 13:06:02 +0000 Received: (at 23932) by debbugs.gnu.org; 17 Aug 2016 13:05:30 +0000 Received: from localhost ([127.0.0.1]:59906 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ba0XC-0008NA-1E for submit@debbugs.gnu.org; Wed, 17 Aug 2016 09:05:30 -0400 Received: from mailgw06.kcn.ne.jp ([61.86.7.213]:38133) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ba0X8-0008Mt-DT for 23932@debbugs.gnu.org; Wed, 17 Aug 2016 09:05:28 -0400 Received: from mxs02-s (mailgw2.kcn.ne.jp [61.86.15.234]) by mailgw06.kcn.ne.jp (Postfix) with ESMTP id 9D479C8002 for <23932@debbugs.gnu.org>; Wed, 17 Aug 2016 22:05:18 +0900 (JST) X-matriXscan-loop-detect: a59f13214f6909f8114fa17b05262c6e4a2bb3f3 Received: from mail06.kcn.ne.jp ([61.86.6.185]) by mxs02-s with ESMTP; Wed, 17 Aug 2016 22:05:10 +0900 (JST) Received: from [10.120.1.52] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail06.kcn.ne.jp (Postfix) with ESMTPA id 858F91BF0092; Wed, 17 Aug 2016 22:05:09 +0900 (JST) Date: Wed, 17 Aug 2016 22:05:09 +0900 From: Norihiro Tanaka In-Reply-To: <20160816233521.C15A.27F6AC2D@kcn.ne.jp> References: <20160710185143.23FB.27F6AC2D@kcn.ne.jp> <20160816233521.C15A.27F6AC2D@kcn.ne.jp> Message-Id: <20160817220507.EFE3.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_57B45F7300000000EFDA_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-matriXscan-Sophos-AV: Clean X-matriXscan-Action: Approve X-matriXscan: Uncategorized X-Spam-Score: -0.5 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.5 (/) --------_57B45F7300000000EFDA_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit On Tue, 16 Aug 2016 23:35:22 +0900 Norihiro Tanaka wrote: > I updated the patch due to change in bug#21486, and added a patch > including a minor change. I wrote third patch. After first patch, we do not have to separate next state by context, transit_state() never treats a eol-byte as current context. So remove it. --------_57B45F7300000000EFDA_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII"; name="0003-dfa-remove-separation-by-context-in-transition-in-no.patch" Content-Disposition: attachment; filename="0003-dfa-remove-separation-by-context-in-transition-in-no.patch" Content-Transfer-Encoding: base64 RnJvbSBiYTIxYjQ3ZDU1MDdlMTUzZGI3MDI0YjJmZjljNDFiY2FmMmM1NGU0IE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBOb3JpaGlybyBUYW5ha2EgPG5vcml0bmtAa2NuLm5lLmpwPgpE YXRlOiBXZWQsIDE3IEF1ZyAyMDE2IDIxOjUzOjU3ICswOTAwClN1YmplY3Q6IFtQQVRDSCAzLzNd IGRmYTogcmVtb3ZlIHNlcGFyYXRpb24gYnkgY29udGV4dCBpbiB0cmFuc2l0aW9uIGluIG5vbi1V VEY4IG11bHRpYnl0ZSBsb2NhbGVzCgoqIHNyYy9kZmEuYyAoc3RydWN0IGRmYSk6IFJlbW92ZSBt ZW1iZXIgY3Vycl9kZXBlbmRlbnQuICBBbGwgdXNlcwpyZW1vdmVkLgotLS0KIHNyYy9kZmEuYyB8 ICAgNTMgKysrLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0KIDEgZmlsZXMgY2hhbmdlZCwgMyBpbnNlcnRpb25zKCspLCA1MCBkZWxldGlvbnMoLSkKCmRp ZmYgLS1naXQgYS9zcmMvZGZhLmMgYi9zcmMvZGZhLmMKaW5kZXggZjc5ZDY3ZS4uZWY5NTI3ZCAx MDA2NDQKLS0tIGEvc3JjL2RmYS5jCisrKyBiL3NyYy9kZmEuYwpAQCAtMjg5LDkgKzI4OSw2IEBA IHR5cGVkZWYgc3RydWN0CiAgIHNpemVfdCBoYXNoOyAgICAgICAgICAgICAgICAgIC8qIEhhc2gg b2YgdGhlIHBvc2l0aW9ucyBvZiB0aGlzIHN0YXRlLiAgKi8KICAgcG9zaXRpb25fc2V0IGVsZW1z OyAgICAgICAgICAgLyogUG9zaXRpb25zIHRoaXMgc3RhdGUgY291bGQgbWF0Y2guICAqLwogICB1 bnNpZ25lZCBjaGFyIGNvbnRleHQ7ICAgICAgICAvKiBDb250ZXh0IGZyb20gcHJldmlvdXMgc3Rh dGUuICAqLwotICBib29sIGN1cnJfZGVwZW5kZW50OyAgICAgICAgICAvKiBUcnVlIGlmIHRoZSBm b2xsb3dzIG9mIGFueSBwb3NpdGlvbnMgd2l0aAotICAgICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICBBTllDSEFSIGRlcGVuZHMgb24gdGhlIG5leHQgY2hhcmFjdGVyJ3MKLSAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgY29udGV4dC4gICovCiAgIHVuc2lnbmVkIHNob3J0 IGNvbnN0cmFpbnQ7ICAgIC8qIENvbnN0cmFpbnQgZm9yIHRoaXMgc3RhdGUgdG8gYWNjZXB0LiAg Ki8KICAgdG9rZW4gZmlyc3RfZW5kOyAgICAgICAgICAgICAgLyogVG9rZW4gdmFsdWUgb2YgdGhl IGZpcnN0IEVORCBpbiBlbGVtcy4gICovCiAgIHBvc2l0aW9uX3NldCBtYnBzOyAgICAgICAgICAg IC8qIFBvc2l0aW9ucyB3aGljaCBjYW4gbWF0Y2ggbXVsdGlieXRlCkBAIC0yMDY1LDcgKzIwNjIs NiBAQCBzdGF0ZV9pbmRleCAoc3RydWN0IGRmYSAqZCwgcG9zaXRpb25fc2V0IGNvbnN0ICpzLCBp bnQgY29udGV4dCkKICAgc2l6ZV90IGhhc2ggPSAwOwogICBpbnQgY29uc3RyYWludCA9IDA7CiAg IHN0YXRlX251bSBpLCBqOwotICBib29sIGN1cnJfZGVwZW5kZW50ID0gZmFsc2U7CiAgIHRva2Vu IGZpcnN0X2VuZCA9IDA7CiAKICAgZm9yIChpID0gMDsgaSA8IHMtPm5lbGVtOyArK2kpCkBAIC0y MTE5LDE3ICsyMTE1LDYgQEAgc3RhdGVfaW5kZXggKHN0cnVjdCBkZmEgKmQsIHBvc2l0aW9uX3Nl dCBjb25zdCAqcywgaW50IGNvbnRleHQpCiAgICAgICAgIH0KICAgICAgIGVsc2UgaWYgKGQtPnRv a2Vuc1tzLT5lbGVtc1tqXS5pbmRleF0gPT0gQkFDS1JFRikKICAgICAgICAgY29uc3RyYWludCA9 IE5PX0NPTlNUUkFJTlQ7Ci0gICAgICBpZiAoZC0+dG9rZW5zW3MtPmVsZW1zW2pdLmluZGV4XSA9 PSBBTllDSEFSKQotICAgICAgICB7Ci0gICAgICAgICAgaW50IGFjY2VwdGFibGUKLSAgICAgICAg ICAgID0gKChTVUNDRUVEU19JTl9DT05URVhUIChjLCBjb250ZXh0LCBDVFhfTkVXTElORSkKLSAg ICAgICAgICAgICAgICA/IENUWF9ORVdMSU5FIDogMCkKLSAgICAgICAgICAgICAgIHwgKFNVQ0NF RURTX0lOX0NPTlRFWFQgKGMsIGNvbnRleHQsIENUWF9MRVRURVIpCi0gICAgICAgICAgICAgICAg ICA/IENUWF9MRVRURVIgOiAwKQotICAgICAgICAgICAgICAgfCAoU1VDQ0VFRFNfSU5fQ09OVEVY VCAoYywgY29udGV4dCwgQ1RYX05PTkUpCi0gICAgICAgICAgICAgICAgICA/IENUWF9OT05FIDog MCkpOwotICAgICAgICAgIGN1cnJfZGVwZW5kZW50IHw9IGFjY2VwdGFibGUgJiYgKGNvbnRleHQg JiB+YWNjZXB0YWJsZSk7Ci0gICAgICAgIH0KICAgICB9CiAKIApAQCAtMjE0MCw3ICsyMTI1LDYg QEAgc3RhdGVfaW5kZXggKHN0cnVjdCBkZmEgKmQsIHBvc2l0aW9uX3NldCBjb25zdCAqcywgaW50 IGNvbnRleHQpCiAgIGFsbG9jX3Bvc2l0aW9uX3NldCAoJmQtPnN0YXRlc1tpXS5lbGVtcywgcy0+ bmVsZW0pOwogICBjb3B5IChzLCAmZC0+c3RhdGVzW2ldLmVsZW1zKTsKICAgZC0+c3RhdGVzW2ld LmNvbnRleHQgPSBjb250ZXh0OwotICBkLT5zdGF0ZXNbaV0uY3Vycl9kZXBlbmRlbnQgPSBjdXJy X2RlcGVuZGVudDsKICAgZC0+c3RhdGVzW2ldLmNvbnN0cmFpbnQgPSBjb25zdHJhaW50OwogICBk LT5zdGF0ZXNbaV0uZmlyc3RfZW5kID0gZmlyc3RfZW5kOwogICBkLT5zdGF0ZXNbaV0ubWJwcy5u ZWxlbSA9IDA7CkBAIC0yNjA2LDE0ICsyNTkwLDggQEAgZGZhc3RhdGUgKHN0YXRlX251bSBzLCBz dHJ1Y3QgZGZhICpkLCBzdGF0ZV9udW0gdHJhbnNbXSkKICAgICAgICAgICAgICBwb3NpdGlvbnMg d2hpY2ggaGFzIEFOWUNIQVIgZG9lcyBub3QgZGVwZW5kIG9uIGNvbnRleHQgb2YKICAgICAgICAg ICAgICBuZXh0IGNoYXJhY3Rlciwgd2UgcHV0IHRoZSBmb2xsb3dzIGluc3RlYWQgb2YgaXQgdG8K ICAgICAgICAgICAgICBELT5zdGF0ZXNbc10ubWJwcyB0byBvcHRpbWl6ZS4gICovCi0gICAgICAg ICAgaWYgKGQtPnN0YXRlc1tzXS5jdXJyX2RlcGVuZGVudCkKLSAgICAgICAgICAgIHsKLSAgICAg ICAgICAgICAgaWYgKGQtPnN0YXRlc1tzXS5tYnBzLm5lbGVtID09IDApCi0gICAgICAgICAgICAg ICAgYWxsb2NfcG9zaXRpb25fc2V0ICgmZC0+c3RhdGVzW3NdLm1icHMsIDEpOwotICAgICAgICAg ICAgICBpbnNlcnQgKHBvcywgJmQtPnN0YXRlc1tzXS5tYnBzKTsKLSAgICAgICAgICAgIH0KLSAg ICAgICAgICBlbHNlIGlmIChTVUNDRUVEU19JTl9DT05URVhUIChwb3MuY29uc3RyYWludCwKLSAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBkLT5zdGF0ZXNbc10uY29udGV4 dCwgQ1RYX0FOWSkpCisgICAgICAgICAgaWYgKFNVQ0NFRURTX0lOX0NPTlRFWFQgKHBvcy5jb25z dHJhaW50LCBkLT5zdGF0ZXNbc10uY29udGV4dCwKKyAgICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgQ1RYX05PTkUpKQogICAgICAgICAgICAgewogICAgICAgICAgICAgICBpZiAoZC0+ c3RhdGVzW3NdLm1icHMubmVsZW0gPT0gMCkKICAgICAgICAgICAgICAgICBhbGxvY19wb3NpdGlv bl9zZXQgKCZkLT5zdGF0ZXNbc10ubWJwcywKQEAgLTMwMjUsNyArMzAwMyw3IEBAIHRyYW5zaXRf c3RhdGUgKHN0cnVjdCBkZmEgKmQsIHN0YXRlX251bSBzLCB1bnNpZ25lZCBjaGFyIGNvbnN0ICoq cHAsCiAgIHN0YXRlX251bSBzMSwgczI7CiAgIHdpbnRfdCB3YzsKICAgaW50IHNlcGFyYXRlX2Nv bnRleHRzOwotICBzaXplX3QgaSwgajsKKyAgc2l6ZV90IGk7CiAKICAgaW50IG1iY2xlbiA9IG1i c190b193Y2hhciAoJndjLCAoY2hhciBjb25zdCAqKSAqcHAsIGVuZCAtICpwcCwgZCk7CiAKQEAg LTMwNDUsMzEgKzMwMjMsNiBAQCB0cmFuc2l0X3N0YXRlIChzdHJ1Y3QgZGZhICpkLCBzdGF0ZV9u dW0gcywgdW5zaWduZWQgY2hhciBjb25zdCAqKnBwLAogICAgICAgcmV0dXJuIHM7CiAgICAgfQog Ci0gIGlmIChkLT5zdGF0ZXNbczFdLmN1cnJfZGVwZW5kZW50KQotICAgIHsKLSAgICAgIGlmIChz IDwgMCkKLSAgICAgICAgZC0+bWJfZm9sbG93cy5uZWxlbSA9IDA7Ci0gICAgICBlbHNlCi0gICAg ICAgIGNvcHkgKCZkLT5zdGF0ZXNbc10uZWxlbXMsICZkLT5tYl9mb2xsb3dzKTsKLQotICAgICAg Zm9yIChpID0gMDsgaSA8IGQtPnN0YXRlc1tzMV0ubWJwcy5uZWxlbTsgaSsrKQotICAgICAgICB7 Ci0gICAgICAgICAgaWYgKCFTVUNDRUVEU19JTl9DT05URVhUIChkLT5zdGF0ZXNbczFdLm1icHMu ZWxlbXNbaV0uY29uc3RyYWludCwKLSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAg IGQtPnN0YXRlc1tzMV0uY29udGV4dCwgQ1RYX05PTkUpKQotICAgICAgICAgICAgY29udGludWU7 Ci0gICAgICAgICAgZm9yIChqID0gMDsgaiA8IGQtPmZvbGxvd3NbZC0+c3RhdGVzW3MxXS5tYnBz LmVsZW1zW2ldLmluZGV4XS5uZWxlbTsKLSAgICAgICAgICAgICAgIGorKykKLSAgICAgICAgICAg IGluc2VydCAoZC0+Zm9sbG93c1tkLT5zdGF0ZXNbczFdLm1icHMuZWxlbXNbaV0uaW5kZXhdLmVs ZW1zW2pdLAotICAgICAgICAgICAgICAgICAgICAmZC0+bWJfZm9sbG93cyk7Ci0gICAgICAgIH0K LQotICAgICAgc2VwYXJhdGVfY29udGV4dHMgPSBzdGF0ZV9zZXBhcmF0ZV9jb250ZXh0cyAoJmQt Pm1iX2ZvbGxvd3MpOwotICAgICAgcyA9IHN0YXRlX2luZGV4IChkLCAmZC0+bWJfZm9sbG93cywg c2VwYXJhdGVfY29udGV4dHMgXiBDVFhfQU5ZKTsKLSAgICAgIHJlYWxsb2NfdHJhbnNfaWZfbmVj ZXNzYXJ5IChkLCBzKTsKLQotICAgICAgcmV0dXJuIHM7Ci0gICAgfQotCiAgIC8qIElmIGFsbCBw b3NpdGlvbnMgd2hpY2ggaGF2ZSBBTllDSEFSIGRvIG5vdCBkZXBlbmQgb24gdGhlIGNvbnRleHQK ICAgICAgb2YgdGhlIG5leHQgY2hhcmFjdGVyLCBjYWxjdWxhdGUgdGhlIG5leHQgc3RhdGUgd2l0 aAogICAgICBwcmUtY2FsY3VsYXRlZCBmb2xsb3dzIGFuZCBjYWNoZSB0aGUgcmVzdWx0LiAgKi8K LS0gCjEuNy4xCgo= --------_57B45F7300000000EFDA_MULTIPART_MIXED_-- From unknown Sat Jun 21 10:34:42 2025 MIME-Version: 1.0 X-Mailer: MIME-tools 5.505 (Entity 5.505) X-Loop: help-debbugs@gnu.org From: help-debbugs@gnu.org (GNU bug Tracking System) To: Norihiro Tanaka Subject: bug#23932: closed (Re: bug#23932: dfa: use algorithm for single byte character to any single byte character in input text always) Message-ID: References: <5899b1c2-d352-61e4-fc3d-eaf3ed59ed26@cs.ucla.edu> <20160710185143.23FB.27F6AC2D@kcn.ne.jp> X-Gnu-PR-Message: they-closed 23932 X-Gnu-PR-Package: grep X-Gnu-PR-Keywords: patch Reply-To: 23932@debbugs.gnu.org Date: Thu, 01 Sep 2016 18:51:02 +0000 Content-Type: multipart/mixed; boundary="----------=_1472755862-3829-1" This is a multi-part message in MIME format... ------------=_1472755862-3829-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Your bug report #23932: dfa: use algorithm for single byte character to any single byte cha= racter in input text always which was filed against the grep package, has been closed. The explanation is attached below, along with your original report. If you require more details, please reply to 23932@debbugs.gnu.org. --=20 23932: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D23932 GNU Bug Tracking System Contact help-debbugs@gnu.org with problems ------------=_1472755862-3829-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at 23932-done) by debbugs.gnu.org; 1 Sep 2016 18:50:10 +0000 Received: from localhost ([127.0.0.1]:46646 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bfX3x-0000yc-Gw for submit@debbugs.gnu.org; Thu, 01 Sep 2016 14:50:10 -0400 Received: from zimbra.cs.ucla.edu ([131.179.128.68]:55292) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bfX3v-0000y1-IS for 23932-done@debbugs.gnu.org; Thu, 01 Sep 2016 14:50:08 -0400 Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id 8F2451613AF; Thu, 1 Sep 2016 11:50:01 -0700 (PDT) Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10032) with ESMTP id hj3niwCP-IQB; Thu, 1 Sep 2016 11:50:00 -0700 (PDT) Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id E80F01613B2; Thu, 1 Sep 2016 11:49:59 -0700 (PDT) X-Virus-Scanned: amavisd-new at zimbra.cs.ucla.edu Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id nOCBYXwBFLR5; Thu, 1 Sep 2016 11:49:59 -0700 (PDT) Received: from [192.168.1.9] (unknown [100.32.155.148]) by zimbra.cs.ucla.edu (Postfix) with ESMTPSA id B94921613AF; Thu, 1 Sep 2016 11:49:59 -0700 (PDT) To: Norihiro Tanaka From: Paul Eggert Subject: Re: bug#23932: dfa: use algorithm for single byte character to any single byte character in input text always Organization: UCLA Computer Science Department Message-ID: <5899b1c2-d352-61e4-fc3d-eaf3ed59ed26@cs.ucla.edu> Date: Thu, 1 Sep 2016 11:49:59 -0700 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.2.0 MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------------A23A259F24AD7A4AD345A2C7" X-Spam-Score: -1.5 (-) X-Debbugs-Envelope-To: 23932-done Cc: 23932-done@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.5 (-) This is a multi-part message in MIME format. --------------A23A259F24AD7A4AD345A2C7 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit Thanks for that set of patches too. I rebased it and tweaked NEWS and installed the resulting patch set (attached) into Savannah master. --------------A23A259F24AD7A4AD345A2C7 Content-Type: text/x-diff; name="0001-dfa-use-single-byte-algorithm-even-in-non-UTF-8.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename*0="0001-dfa-use-single-byte-algorithm-even-in-non-UTF-8.patch" >From a95ba0203afcc43feea0fa99e4d1b8fb923b1aeb Mon Sep 17 00:00:00 2001 From: Norihiro Tanaka Date: Thu, 1 Sep 2016 11:45:18 -0700 Subject: [PATCH 1/4] dfa: use single-byte algorithm even in non-UTF-8 Even in non-UTF8 locales, if the current input character is single byte, we can use CSET to match ANYCHAR. * src/dfa.c (struct dfa): New member canychar. Cache index of CSET for ANYCHAR. (lex): Make CSET for ANYCHAR. (state_index): Simplify. (dfastate): Consider CSET for ANYCHAR. (transit_state_singlebyte, transit_state): Remove handling for eolbyte, as we assume that eolbyte does not appear at current position. (dfaexec_main): Use algorithm for single byte character to any single byte character in input text always. (dfasyntax): Initialize canychar. --- src/dfa.c | 115 ++++++++++++++++++++++++-------------------------------------- 1 file changed, 45 insertions(+), 70 deletions(-) diff --git a/src/dfa.c b/src/dfa.c index 0f5109e..e39d82a 100644 --- a/src/dfa.c +++ b/src/dfa.c @@ -401,6 +401,7 @@ struct dfa charclass *charclasses; /* Array of character sets for CSET tokens. */ size_t cindex; /* Index for adding new charclasses. */ size_t calloc; /* Number of charclasses allocated. */ + size_t canychar; /* Index of anychar class, or (size_t) -1. */ /* Scanner state */ struct lexer_state lex; @@ -1398,21 +1399,24 @@ lex (struct dfa *dfa) case '.': if (backslash) goto normal_char; - if (dfa->localeinfo.multibyte) + if (dfa->canychar == (size_t) -1) { - /* In multibyte environment period must match with a single - character not a byte. So we use ANYCHAR. */ - dfa->lex.laststart = false; - return dfa->lex.lasttok = ANYCHAR; + zeroset (ccl); + notset (ccl); + if (!(dfa->syntax.syntax_bits & RE_DOT_NEWLINE)) + clrbit ('\n', ccl); + if (dfa->syntax.syntax_bits & RE_DOT_NOT_NULL) + clrbit ('\0', ccl); + if (dfa->localeinfo.multibyte) + for (c2 = 0; c2 < NOTCHAR; c2++) + if (dfa->localeinfo.sbctowc[c2] == WEOF) + clrbit (c2, ccl); + dfa->canychar = charclass_index (dfa, ccl); } - zeroset (ccl); - notset (ccl); - if (!(dfa->syntax.syntax_bits & RE_DOT_NEWLINE)) - clrbit ('\n', ccl); - if (dfa->syntax.syntax_bits & RE_DOT_NOT_NULL) - clrbit ('\0', ccl); dfa->lex.laststart = false; - return dfa->lex.lasttok = CSET + charclass_index (dfa, ccl); + return dfa->lex.lasttok = (dfa->localeinfo.multibyte + ? ANYCHAR + : CSET + dfa->canychar); case 's': case 'S': @@ -2077,7 +2081,7 @@ state_index (struct dfa *d, position_set const *s, int context) } else if (d->tokens[s->elems[j].index] == BACKREF) constraint = NO_CONSTRAINT; - if (d->localeinfo.multibyte && d->tokens[s->elems[j].index] == ANYCHAR) + if (d->tokens[s->elems[j].index] == ANYCHAR) { int acceptable = ((SUCCEEDS_IN_CONTEXT (c, context, CTX_NEWLINE) @@ -2554,13 +2558,15 @@ dfastate (state_num s, struct dfa *d, state_num trans[]) setbit (d->tokens[pos.index], matches); else if (d->tokens[pos.index] >= CSET) copyset (d->charclasses[d->tokens[pos.index] - CSET], matches); - else if (d->localeinfo.multibyte && d->tokens[pos.index] == ANYCHAR) + else if (d->tokens[pos.index] == ANYCHAR) { - /* ANYCHAR must match a single character, so put it to - D->states[s].mbps which contains the positions which can - match with a single character not a byte. If all - positions with ANYCHAR do not depend on the context of - the next character, put its follows instead to + copyset (d->charclasses[d->canychar], matches); + + /* ANYCHAR must match with a single character, so we must put + it to D->states[s].mbps which contains the positions which + can match with a single character not a byte. If all + positions which has ANYCHAR does not depend on context of + next character, we put the follows instead of it to D->states[s].mbps to optimize. */ if (d->states[s].curr_dependent) { @@ -2572,7 +2578,8 @@ dfastate (state_num s, struct dfa *d, state_num trans[]) d->states[s].context, CTX_ANY)) { if (d->states[s].mbps.nelem == 0) - alloc_position_set (&d->states[s].mbps, 1); + alloc_position_set (&d->states[s].mbps, + d->follows[pos.index].nelem); for (j = 0; j < d->follows[pos.index].nelem; j++) insert (d->follows[pos.index].elems[j], &d->states[s].mbps); } @@ -2950,16 +2957,6 @@ transit_state_singlebyte (struct dfa *d, state_num s, unsigned char const **pp) { state_num *t; - if (**pp == d->syntax.eolbyte) - { - /* S is always an initial state in transit_state, so the - transition table for the state must have been built already. */ - assert (d->trans[s] || d->fails[s]); - - ++*pp; - return d->newlines[s]; - } - if (d->trans[s]) t = d->trans[s]; else if (d->fails[s]) @@ -2986,15 +2983,12 @@ static state_num transit_state (struct dfa *d, state_num s, unsigned char const **pp, unsigned char const *end) { - state_num s1; + state_num s1, s2; wint_t wc; int separate_contexts; - state_num state, state_newline, mb_index; size_t i, j; int mbclen = mbs_to_wchar (&wc, (char const *) *pp, end - *pp, d); - int context = wc == d->syntax.eolbyte ? CTX_NEWLINE : CTX_NONE; - bool context_newline = context == CTX_NEWLINE; /* This state has some operators which can match a multibyte character. */ d->mb_follows.nelem = 0; @@ -3016,7 +3010,7 @@ transit_state (struct dfa *d, state_num s, unsigned char const **pp, for (i = 0; i < d->states[s1].mbps.nelem; i++) { if (!SUCCEEDS_IN_CONTEXT (d->states[s1].mbps.elems[i].constraint, - d->states[s1].context, context)) + d->states[s1].context, CTX_NONE)) continue; for (j = 0; j < d->follows[d->states[s1].mbps.elems[i].index].nelem; j++) @@ -3025,10 +3019,7 @@ transit_state (struct dfa *d, state_num s, unsigned char const **pp, } separate_contexts = state_separate_contexts (&d->mb_follows); - if (context_newline && separate_contexts & CTX_NEWLINE) - s = state_index (d, &d->mb_follows, CTX_NEWLINE); - else - s = state_index (d, &d->mb_follows, separate_contexts ^ CTX_ANY); + s = state_index (d, &d->mb_follows, separate_contexts ^ CTX_ANY); realloc_trans_if_necessary (d, s); return s; @@ -3041,11 +3032,11 @@ transit_state (struct dfa *d, state_num s, unsigned char const **pp, { if (MAX_TRCOUNT <= d->mb_trcount) { - state_num s2; - for (s2 = -1; s2 < d->tralloc; s2++) + state_num s3; + for (s3 = -1; s3 < d->tralloc; s3++) { - free (d->mb_trans[s2]); - d->mb_trans[s2] = NULL; + free (d->mb_trans[s3]); + d->mb_trans[s3] = NULL; } for (i = 0; i < d->sindex; i++) @@ -3055,22 +3046,16 @@ transit_state (struct dfa *d, state_num s, unsigned char const **pp, d->states[s1].mb_trindex = d->mb_trcount++; } - mb_index = d->states[s1].mb_trindex * 2; - if (! d->mb_trans[s]) { enum { TRANSPTR_SIZE = sizeof *d->mb_trans[s] }; - enum { TRANSALLOC_SIZE = 2 * MAX_TRCOUNT * TRANSPTR_SIZE }; + enum { TRANSALLOC_SIZE = MAX_TRCOUNT * TRANSPTR_SIZE }; d->mb_trans[s] = xmalloc (TRANSALLOC_SIZE); - for (i = 0; i < 2 * MAX_TRCOUNT; i++) + for (i = 0; i < MAX_TRCOUNT; i++) d->mb_trans[s][i] = -1; } - else - { - state = d->mb_trans[s][mb_index + context_newline]; - if (0 <= state) - return state; - } + else if (d->mb_trans[s][d->states[s1].mb_trindex] >= 0) + return d->mb_trans[s][d->states[s1].mb_trindex]; if (s < 0) copy (&d->states[s1].mbps, &d->mb_follows); @@ -3078,17 +3063,12 @@ transit_state (struct dfa *d, state_num s, unsigned char const **pp, merge (&d->states[s1].mbps, &d->states[s].elems, &d->mb_follows); separate_contexts = state_separate_contexts (&d->mb_follows); - state = state_index (d, &d->mb_follows, separate_contexts ^ CTX_ANY); - if (separate_contexts & CTX_NEWLINE) - state_newline = state_index (d, &d->mb_follows, CTX_NEWLINE); - else - state_newline = state; - realloc_trans_if_necessary (d, state_newline); + s2 = state_index (d, &d->mb_follows, separate_contexts ^ CTX_ANY); + realloc_trans_if_necessary (d, s2); - d->mb_trans[s][mb_index] = state; - d->mb_trans[s][mb_index + 1] = state_newline; + d->mb_trans[s][d->states[s1].mb_trindex] = s2; - return context_newline ? state_newline : state; + return s2; } /* The initial state may encounter a byte which is not a single byte character @@ -3215,10 +3195,8 @@ dfaexec_main (struct dfa *d, char const *begin, char *end, bool allow_nl, } } - if (d->states[s].mbps.nelem == 0 || (*p == eol && !allow_nl) - || (*p == '\n' && !(d->syntax.syntax_bits & RE_DOT_NEWLINE)) - || (*p == '\0' && (d->syntax.syntax_bits & RE_DOT_NOT_NULL)) - || (char *) p >= end) + if (d->states[s].mbps.nelem == 0 + || d->localeinfo.sbctowc[*p] != WEOF || (char *) p >= end) { /* If an input character does not match ANYCHAR, do it like a single-byte character. */ @@ -3227,8 +3205,6 @@ dfaexec_main (struct dfa *d, char const *begin, char *end, bool allow_nl, else { s = transit_state (d, s, &p, (unsigned char *) end); - if (s >= 0 && p[-1] == eol) - nlcount++; mbp = p; trans = d->trans; } @@ -3297,8 +3273,6 @@ dfaexec_main (struct dfa *d, char const *begin, char *end, bool allow_nl, else { s = transit_state (d, s, &p, (unsigned char *) end); - if (s >= 0 && p[-1] == eol) - nlcount++; mbp = p; trans = d->trans; } @@ -4106,6 +4080,7 @@ dfasyntax (struct dfa *dfa, struct localeinfo const *linfo, dfa->fast = !dfa->localeinfo.multibyte; + dfa->canychar = -1; dfa->lex.cur_mb_len = 1; dfa->syntax.syntax_bits_set = true; dfa->syntax.syntax_bits = bits; -- 2.7.4 --------------A23A259F24AD7A4AD345A2C7 Content-Type: text/x-diff; name="0002-dfa-avoid-invalid-character-matching-period.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0002-dfa-avoid-invalid-character-matching-period.patch" >From 5644d1c3884286e2a8a6f51b5d0ef00a8fbe4578 Mon Sep 17 00:00:00 2001 From: Norihiro Tanaka Date: Thu, 1 Sep 2016 11:45:18 -0700 Subject: [PATCH 2/4] dfa: avoid invalid character matching period * dfa.c (transit_state): Avoid invalid character matching period. --- src/dfa.c | 6 ++++++ 1 file changed, 6 insertions(+) diff --git a/src/dfa.c b/src/dfa.c index e39d82a..075576c 100644 --- a/src/dfa.c +++ b/src/dfa.c @@ -3000,6 +3000,12 @@ transit_state (struct dfa *d, state_num s, unsigned char const **pp, s = transit_state_singlebyte (d, s, pp); *pp += mbclen - i; + if (wc == WEOF) + { + /* It is an invalid character, so ANYCHAR is not accepted. */ + return s; + } + if (d->states[s1].curr_dependent) { if (s < 0) -- 2.7.4 --------------A23A259F24AD7A4AD345A2C7 Content-Type: text/x-diff; name="0003-dfa-document-previous-change.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0003-dfa-document-previous-change.patch" >From 83db3ea1a09cbff41aa2a9c7d1bd6dc01612c862 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Thu, 1 Sep 2016 11:45:18 -0700 Subject: [PATCH 3/4] dfa: document previous change * NEWS: Adjust to match previous change. --- NEWS | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/NEWS b/NEWS index 91f1bfc..56c735f 100644 --- a/NEWS +++ b/NEWS @@ -13,8 +13,8 @@ GNU grep NEWS -*- outline -*- grep -iF is typically much faster in a multibyte locale, if the pattern and its case counterparts contain only single byte characters. - In multibyte locales that are not UTF-8, grep now handles leading - "." in patterns more efficiently. + In multibyte locales, grep now handles leading "." in patterns more + efficiently. grep now prints a "FILENAME:LINENO: " prefix when diagnosing an invalid regular expression that was read from an '-f'-specified file. -- 2.7.4 --------------A23A259F24AD7A4AD345A2C7 Content-Type: text/x-diff; name="0004-dfa-remove-separation-by-context-in-transition-in-no.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename*0="0004-dfa-remove-separation-by-context-in-transition-in-no.pa"; filename*1="tch" >From 980bcbff1046559d6a5299055f22ba6b8703ed8a Mon Sep 17 00:00:00 2001 From: Norihiro Tanaka Date: Thu, 1 Sep 2016 11:45:18 -0700 Subject: [PATCH 4/4] dfa: remove separation by context in transition in non-UTF8 multibyte locales * src/dfa.c (struct dfa): Remove member curr_dependent. All uses removed. --- src/dfa.c | 53 +++-------------------------------------------------- 1 file changed, 3 insertions(+), 50 deletions(-) diff --git a/src/dfa.c b/src/dfa.c index 075576c..00562ea 100644 --- a/src/dfa.c +++ b/src/dfa.c @@ -303,9 +303,6 @@ typedef struct size_t hash; /* Hash of the positions of this state. */ position_set elems; /* Positions this state could match. */ unsigned char context; /* Context from previous state. */ - bool curr_dependent; /* True if the follows of any positions with - ANYCHAR depends on the next character's - context. */ unsigned short constraint; /* Constraint for this state to accept. */ token first_end; /* Token value of the first END in elems. */ position_set mbps; /* Positions which can match multibyte @@ -2027,7 +2024,6 @@ state_index (struct dfa *d, position_set const *s, int context) size_t hash = 0; int constraint = 0; state_num i, j; - bool curr_dependent = false; token first_end = 0; for (i = 0; i < s->nelem; ++i) @@ -2081,17 +2077,6 @@ state_index (struct dfa *d, position_set const *s, int context) } else if (d->tokens[s->elems[j].index] == BACKREF) constraint = NO_CONSTRAINT; - if (d->tokens[s->elems[j].index] == ANYCHAR) - { - int acceptable - = ((SUCCEEDS_IN_CONTEXT (c, context, CTX_NEWLINE) - ? CTX_NEWLINE : 0) - | (SUCCEEDS_IN_CONTEXT (c, context, CTX_LETTER) - ? CTX_LETTER : 0) - | (SUCCEEDS_IN_CONTEXT (c, context, CTX_NONE) - ? CTX_NONE : 0)); - curr_dependent |= acceptable && (context & ~acceptable); - } } @@ -2102,7 +2087,6 @@ state_index (struct dfa *d, position_set const *s, int context) alloc_position_set (&d->states[i].elems, s->nelem); copy (s, &d->states[i].elems); d->states[i].context = context; - d->states[i].curr_dependent = curr_dependent; d->states[i].constraint = constraint; d->states[i].first_end = first_end; d->states[i].mbps.nelem = 0; @@ -2568,14 +2552,8 @@ dfastate (state_num s, struct dfa *d, state_num trans[]) positions which has ANYCHAR does not depend on context of next character, we put the follows instead of it to D->states[s].mbps to optimize. */ - if (d->states[s].curr_dependent) - { - if (d->states[s].mbps.nelem == 0) - alloc_position_set (&d->states[s].mbps, 1); - insert (pos, &d->states[s].mbps); - } - else if (SUCCEEDS_IN_CONTEXT (pos.constraint, - d->states[s].context, CTX_ANY)) + if (SUCCEEDS_IN_CONTEXT (pos.constraint, d->states[s].context, + CTX_NONE)) { if (d->states[s].mbps.nelem == 0) alloc_position_set (&d->states[s].mbps, @@ -2986,7 +2964,7 @@ transit_state (struct dfa *d, state_num s, unsigned char const **pp, state_num s1, s2; wint_t wc; int separate_contexts; - size_t i, j; + size_t i; int mbclen = mbs_to_wchar (&wc, (char const *) *pp, end - *pp, d); @@ -3006,31 +2984,6 @@ transit_state (struct dfa *d, state_num s, unsigned char const **pp, return s; } - if (d->states[s1].curr_dependent) - { - if (s < 0) - d->mb_follows.nelem = 0; - else - copy (&d->states[s].elems, &d->mb_follows); - - for (i = 0; i < d->states[s1].mbps.nelem; i++) - { - if (!SUCCEEDS_IN_CONTEXT (d->states[s1].mbps.elems[i].constraint, - d->states[s1].context, CTX_NONE)) - continue; - for (j = 0; j < d->follows[d->states[s1].mbps.elems[i].index].nelem; - j++) - insert (d->follows[d->states[s1].mbps.elems[i].index].elems[j], - &d->mb_follows); - } - - separate_contexts = state_separate_contexts (&d->mb_follows); - s = state_index (d, &d->mb_follows, separate_contexts ^ CTX_ANY); - realloc_trans_if_necessary (d, s); - - return s; - } - /* If all positions which have ANYCHAR do not depend on the context of the next character, calculate the next state with pre-calculated follows and cache the result. */ -- 2.7.4 --------------A23A259F24AD7A4AD345A2C7-- ------------=_1472755862-3829-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at submit) by debbugs.gnu.org; 10 Jul 2016 09:52:23 +0000 Received: from localhost ([127.0.0.1]:44590 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bMBPT-0003Z1-94 for submit@debbugs.gnu.org; Sun, 10 Jul 2016 05:52:23 -0400 Received: from eggs.gnu.org ([208.118.235.92]:54196) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bMBPR-0003Yp-Hw for submit@debbugs.gnu.org; Sun, 10 Jul 2016 05:52:22 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1bMBPK-00013G-0N for submit@debbugs.gnu.org; Sun, 10 Jul 2016 05:52:16 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=0.8 required=5.0 tests=BAYES_50 autolearn=disabled version=3.3.2 Received: from lists.gnu.org ([2001:4830:134:3::11]:41591) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bMBPJ-000136-Ss for submit@debbugs.gnu.org; Sun, 10 Jul 2016 05:52:13 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:45132) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bMBPH-00050q-0u for bug-grep@gnu.org; Sun, 10 Jul 2016 05:52:12 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1bMBPB-00011Q-3C for bug-grep@gnu.org; Sun, 10 Jul 2016 05:52:10 -0400 Received: from mailgw01.kcn.ne.jp ([61.86.7.208]:40140) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bMBPA-00010m-BR for bug-grep@gnu.org; Sun, 10 Jul 2016 05:52:05 -0400 Received: from mxs02-s (mailgw2.kcn.ne.jp [61.86.15.234]) by mailgw01.kcn.ne.jp (Postfix) with ESMTP id 242E44A078A for ; Sun, 10 Jul 2016 18:51:48 +0900 (JST) X-matriXscan-loop-detect: 310ba3e5f43ef402881df2ed19015b017ea80efe Received: from mail01.kcn.ne.jp ([61.86.6.180]) by mxs02-s with ESMTP; Sun, 10 Jul 2016 18:51:46 +0900 (JST) Received: from [10.120.1.14] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail01.kcn.ne.jp (Postfix) with ESMTPA id 79D7B5A824C for ; Sun, 10 Jul 2016 18:51:46 +0900 (JST) Date: Sun, 10 Jul 2016 18:51:43 +0900 From: Norihiro Tanaka To: Subject: dfa: use algorithm for single byte character to any single byte character in input text always Message-Id: <20160710185143.23FB.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_578213EE0000000023EF_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-matriXscan-Sophos-AV: Clean X-matriXscan-Action: Approve X-matriXscan: Uncategorized X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-Received-From: 2001:4830:134:3::11 X-Spam-Score: -4.0 (----) X-Debbugs-Envelope-To: submit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -4.0 (----) --------_578213EE0000000023EF_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit In multibyte locales, if a pattern start with period expression, matching is still slow, as transition table is built at run time, even when next character is single byte in input text. This patch changes it into as use algorithm for single byte character to any single byte character in input text always. If transition table has been built already and a next character in input text is single byte, transit to next state by reference of only pre-built transition table, even if from a state including ANYCHAR. $ yes "$(printf 'a%038db\n' 0)" | head -1000000 >in $ env LC_ALL=C gcc -v Reading specs from /usr/local/lib/gcc/x86_64-pc-linux-gnu/4.4.7/specs Target: x86_64-pc-linux-gnu Configured with: ./configure --with-as=/usr/local/bin/as --with-ld=/usr/local/bin/ld --with-system-zlib --enable-__cxa_atexit Thread model: posix gcc version 4.4.7 (GCC) patch#21486 is required before this patch. grep will speed up by this patch additionaly. [grep-2.25] $ time -p env LC_ALL=ja_JP.eucjp grep .a.b in real 4.78 user 4.42 sys 0.16 $ time -p env LC_ALL=ja_JP.eucjp grep '.\{41\}' in real 46.23 user 43.98 sys 0.21 [after patch#21486] $ time -p env LC_ALL=ja_JP.eucjp src/grep .a.b in real 1.26 user 1.08 sys 0.08 $ time -p env LC_ALL=ja_JP.eucjp src/grep '.\{41\}' in real 1.14 user 1.00 sys 0.10 [after this patch] $ time -p env LC_ALL=ja_JP.eucjp src/grep .a.b in real 0.47 user 0.36 sys 0.07 $ time -p env LC_ALL=ja_JP.eucjp src/grep '.\{41\}' in real 0.24 user 0.18 sys 0.05 [locale C (ref.)] $ time -p env LC_ALL=C src/grep .a.b in real 0.23 user 0.11 sys 0.09 $ time -p env LC_ALL=C src/grep '.\{41\}' in real 0.22 user 0.13 sys 0.06 --------_578213EE0000000023EF_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII"; name="0001-dfa-use-algorithm-for-single-byte-character-to-any-s.patch" Content-Disposition: attachment; filename="0001-dfa-use-algorithm-for-single-byte-character-to-any-s.patch" Content-Transfer-Encoding: base64 RnJvbSAzZDBjMTMwODA4Yzk3NGYxMjcxNTYxYzc0MzNiMmFhNjYxYzQ5NTA3IE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBOb3JpaGlybyBUYW5ha2EgPG5vcml0bmtAa2NuLm5lLmpwPgpE YXRlOiBTdW4sIDEwIEp1bCAyMDE2IDEwOjI2OjM5ICswOTAwClN1YmplY3Q6IFtQQVRDSF0gZGZh OiB1c2UgYWxnb3JpdGhtIGZvciBzaW5nbGUgYnl0ZSBjaGFyYWN0ZXIgdG8gYW55IHNpbmdsZSBi eXRlCiBjaGFyYWN0ZXIgaW4gaW5wdXQgdGV4dCBhbHdheXMKCkV2ZW4gaW4gbm9uLVVURjggbG9j YWxlcywgaWYgYSBjaGFyYWN0ZXIgYXQgY3VycmVudCBwb3NpdGlvbiBpbiBpbnB1dAp0ZXh0IGlz IHNpbmdsZSBieXRlLCB3ZSBjYW4gdXNlIENTRVQgdG8gbWF0Y2ggQU5ZQ0hBUi4KCiogc3JjL2Rm YS5jIChjaGFyY2xhc3NfaW5kZXhfYW55Y2hhcik6IE5ldyB2YXIuICBDYWNoZSBpbmRleCBvZiBD U0VUCmZvciBBTllDSEFSLgoobGV4KTogTWFrZSBDU0VUIGZvciBBTllDSEFSLgooc3RhdGVfaW5k ZXgpOiBTaW1wbGlmeS4KKGRmYXN0YXRlKTogQ29uc2lkZXIgQ1NFVCBmb3IgQU5ZQ0hBUi4KKHRy YW5zaXRfc3RhdGVfc2luZ2xlYnl0ZSwgdHJhbnNpdF9zdGF0ZSk6IFJlbW92ZSBoYW5kbGluZyBm b3IgZW9sYnl0ZSwKYXMgd2UgYXNzdW1lIHRoYXQgZW9sYnl0ZSBkb2VzIG5vdCBhcHBlYXIgYXQg Y3VycmVudCBwb3NpdGlvbi4KKGRmYWV4ZWNfbWFpbik6IHVzZSBhbGdvcml0aG0gZm9yIHNpbmds ZSBieXRlIGNoYXJhY3RlciB0byBhbnkgc2luZ2xlCmJ5dGUgY2hhcmFjdGVyIGluIGlucHV0IHRl eHQgYWx3YXlzLgotLS0KIHNyYy9kZmEuYyB8ICAxMTUgKysrKysrKysrKysrKysrKysrKysrKysr LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCiAxIGZpbGVzIGNoYW5nZWQsIDQ2 IGluc2VydGlvbnMoKyksIDY5IGRlbGV0aW9ucygtKQoKZGlmZiAtLWdpdCBhL3NyYy9kZmEuYyBi L3NyYy9kZmEuYwppbmRleCAzYmQwYzY4Li5lOTMyYjJjIDEwMDY0NAotLS0gYS9zcmMvZGZhLmMK KysrIGIvc3JjL2RmYS5jCkBAIC03OSw2ICs3OSw4IEBAIGVudW0KICAgQ0hBUkNMQVNTX1dPUkRT ID0gKE5PVENIQVIgKyBDSEFSQ0xBU1NfV09SRF9CSVRTIC0gMSkgLyBDSEFSQ0xBU1NfV09SRF9C SVRTCiB9OwogCitzdGF0aWMgc2l6ZV90IGNoYXJjbGFzc19pbmRleF9hbnljaGFyID0gLTE7CisK IC8qIFNldHMgb2YgdW5zaWduZWQgY2hhcmFjdGVycyBhcmUgc3RvcmVkIGFzIGJpdCB2ZWN0b3Jz IGluIGFycmF5cyBvZiBpbnRzLiAgKi8KIHR5cGVkZWYgY2hhcmNsYXNzX3dvcmQgY2hhcmNsYXNz W0NIQVJDTEFTU19XT1JEU107CiAKQEAgLTE0MjksMjEgKzE0MzEsMjUgQEAgbGV4ICh2b2lkKQog ICAgICAgICBjYXNlICcuJzoKICAgICAgICAgICBpZiAoYmFja3NsYXNoKQogICAgICAgICAgICAg Z290byBub3JtYWxfY2hhcjsKLSAgICAgICAgICBpZiAoZGZhLT5tdWx0aWJ5dGUpCisgICAgICAg ICAgaWYgKGNoYXJjbGFzc19pbmRleF9hbnljaGFyID09IChzaXplX3QpIC0xKQogICAgICAgICAg ICAgewotICAgICAgICAgICAgICAvKiBJbiBtdWx0aWJ5dGUgZW52aXJvbm1lbnQgcGVyaW9kIG11 c3QgbWF0Y2ggd2l0aCBhIHNpbmdsZQotICAgICAgICAgICAgICAgICBjaGFyYWN0ZXIgbm90IGEg Ynl0ZS4gIFNvIHdlIHVzZSBBTllDSEFSLiAgKi8KLSAgICAgICAgICAgICAgbGFzdHN0YXJ0ID0g ZmFsc2U7Ci0gICAgICAgICAgICAgIHJldHVybiBsYXN0dG9rID0gQU5ZQ0hBUjsKKyAgICAgICAg ICAgICAgemVyb3NldCAoY2NsKTsKKyAgICAgICAgICAgICAgbm90c2V0IChjY2wpOworICAgICAg ICAgICAgICBpZiAoIShzeW50YXhfYml0cyAmIFJFX0RPVF9ORVdMSU5FKSkKKyAgICAgICAgICAg ICAgICBjbHJiaXQgKCdcbicsIGNjbCk7CisgICAgICAgICAgICAgIGlmIChzeW50YXhfYml0cyAm IFJFX0RPVF9OT1RfTlVMTCkKKyAgICAgICAgICAgICAgICBjbHJiaXQgKCdcMCcsIGNjbCk7Cisg ICAgICAgICAgICAgIGlmIChkZmEtPm11bHRpYnl0ZSkKKyAgICAgICAgICAgICAgICB7CisgICAg ICAgICAgICAgICAgICBmb3IgKGMyID0gMDsgYzIgPCBOT1RDSEFSOyArK2MyKQorICAgICAgICAg ICAgICAgICAgICBpZiAobWJydG93Y19jYWNoZVtjMl0gPT0gV0VPRikKKyAgICAgICAgICAgICAg ICAgICAgICBjbHJiaXQgKGMyLCBjY2wpOworICAgICAgICAgICAgICAgIH0KKyAgICAgICAgICAg ICAgY2hhcmNsYXNzX2luZGV4X2FueWNoYXIgPSBjaGFyY2xhc3NfaW5kZXggKGNjbCk7CiAgICAg ICAgICAgICB9Ci0gICAgICAgICAgemVyb3NldCAoY2NsKTsKLSAgICAgICAgICBub3RzZXQgKGNj bCk7Ci0gICAgICAgICAgaWYgKCEoc3ludGF4X2JpdHMgJiBSRV9ET1RfTkVXTElORSkpCi0gICAg ICAgICAgICBjbHJiaXQgKCdcbicsIGNjbCk7Ci0gICAgICAgICAgaWYgKHN5bnRheF9iaXRzICYg UkVfRE9UX05PVF9OVUxMKQotICAgICAgICAgICAgY2xyYml0ICgnXDAnLCBjY2wpOwogICAgICAg ICAgIGxhc3RzdGFydCA9IGZhbHNlOwotICAgICAgICAgIHJldHVybiBsYXN0dG9rID0gQ1NFVCAr IGNoYXJjbGFzc19pbmRleCAoY2NsKTsKKyAgICAgICAgICByZXR1cm4gbGFzdHRvayA9CisgICAg ICAgICAgICBkZmEtPm11bHRpYnl0ZSA/IEFOWUNIQVIgOiBDU0VUICsgY2hhcmNsYXNzX2luZGV4 X2FueWNoYXI7CiAKICAgICAgICAgY2FzZSAncyc6CiAgICAgICAgIGNhc2UgJ1MnOgpAQCAtMjEy NSw3ICsyMTMxLDcgQEAgc3RhdGVfaW5kZXggKHN0cnVjdCBkZmEgKmQsIHBvc2l0aW9uX3NldCBj b25zdCAqcywgaW50IGNvbnRleHQpCiAgICAgICAgIH0KICAgICAgIGVsc2UgaWYgKGQtPnRva2Vu c1tzLT5lbGVtc1tqXS5pbmRleF0gPT0gQkFDS1JFRikKICAgICAgICAgZC0+c3RhdGVzW2ldLmNv bnN0cmFpbnQgPSBOT19DT05TVFJBSU5UOwotICAgICAgaWYgKGQtPm11bHRpYnl0ZSAmJiBkLT50 b2tlbnNbcy0+ZWxlbXNbal0uaW5kZXhdID09IEFOWUNIQVIpCisgICAgICBlbHNlIGlmIChkLT50 b2tlbnNbcy0+ZWxlbXNbal0uaW5kZXhdID09IEFOWUNIQVIpCiAgICAgICAgIHsKICAgICAgICAg ICBpbnQgYWNjZXB0YWJsZSA9IDA7CiAgICAgICAgICAgaWYgKFNVQ0NFRURTX0lOX0NPTlRFWFQg KGNvbnN0cmFpbnQsIGNvbnRleHQsIENUWF9ORVdMSU5FKSkKQEAgLTI1ODgsMTQgKzI1OTQsMTYg QEAgZGZhc3RhdGUgKHN0YXRlX251bSBzLCBzdHJ1Y3QgZGZhICpkLCBzdGF0ZV9udW0gdHJhbnNb XSkKICAgICAgICAgc2V0Yml0IChkLT50b2tlbnNbcG9zLmluZGV4XSwgbWF0Y2hlcyk7CiAgICAg ICBlbHNlIGlmIChkLT50b2tlbnNbcG9zLmluZGV4XSA+PSBDU0VUKQogICAgICAgICBjb3B5c2V0 IChkLT5jaGFyY2xhc3Nlc1tkLT50b2tlbnNbcG9zLmluZGV4XSAtIENTRVRdLCBtYXRjaGVzKTsK LSAgICAgIGVsc2UgaWYgKGQtPm11bHRpYnl0ZSAmJiBkLT50b2tlbnNbcG9zLmluZGV4XSA9PSBB TllDSEFSKQotICAgICAgICAvKiBBTllDSEFSIG11c3QgbWF0Y2ggd2l0aCBhIHNpbmdsZSBjaGFy YWN0ZXIsIHNvIHdlIG11c3QgcHV0Ci0gICAgICAgICAgIGl0IHRvIEQtPnN0YXRlc1tzXS5tYnBz IHdoaWNoIGNvbnRhaW5zIHRoZSBwb3NpdGlvbnMgd2hpY2gKLSAgICAgICAgICAgY2FuIG1hdGNo IHdpdGggYSBzaW5nbGUgY2hhcmFjdGVyIG5vdCBhIGJ5dGUuICBJZiBhbGwKLSAgICAgICAgICAg cG9zaXRpb25zIHdoaWNoIGhhcyBBTllDSEFSIGRvZXMgbm90IGRlcGVuZCBvbiBjb250ZXh0IG9m Ci0gICAgICAgICAgIG5leHQgY2hhcmFjdGVyLCB3ZSBwdXQgdGhlIGZvbGxvd3MgaW5zdGVhZCBv ZiBpdCB0bwotICAgICAgICAgICBELT5zdGF0ZXNbc10ubWJwcyB0byBvcHRpbWl6ZS4gICovCisg ICAgICBlbHNlIGlmIChkLT50b2tlbnNbcG9zLmluZGV4XSA9PSBBTllDSEFSKQogICAgICAgICB7 CisgICAgICAgICAgY29weXNldCAoZC0+Y2hhcmNsYXNzZXNbY2hhcmNsYXNzX2luZGV4X2FueWNo YXJdLCBtYXRjaGVzKTsKKworICAgICAgICAgIC8qIEFOWUNIQVIgbXVzdCBtYXRjaCB3aXRoIGEg c2luZ2xlIGNoYXJhY3Rlciwgc28gd2UgbXVzdCBwdXQKKyAgICAgICAgICAgICBpdCB0byBELT5z dGF0ZXNbc10ubWJwcyB3aGljaCBjb250YWlucyB0aGUgcG9zaXRpb25zIHdoaWNoCisgICAgICAg ICAgICAgY2FuIG1hdGNoIHdpdGggYSBzaW5nbGUgY2hhcmFjdGVyIG5vdCBhIGJ5dGUuICBJZiBh bGwKKyAgICAgICAgICAgICBwb3NpdGlvbnMgd2hpY2ggaGFzIEFOWUNIQVIgZG9lcyBub3QgZGVw ZW5kIG9uIGNvbnRleHQgb2YKKyAgICAgICAgICAgICBuZXh0IGNoYXJhY3Rlciwgd2UgcHV0IHRo ZSBmb2xsb3dzIGluc3RlYWQgb2YgaXQgdG8KKyAgICAgICAgICAgICBELT5zdGF0ZXNbc10ubWJw cyB0byBvcHRpbWl6ZS4gICovCiAgICAgICAgICAgaWYgKGQtPnN0YXRlc1tzXS5jdXJyX2RlcGVu ZGVudCkKICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgaWYgKGQtPnN0YXRlc1tzXS5tYnBz Lm5lbGVtID09IDApCkBAIC0yNjA2LDkgKzI2MTQsMTEgQEAgZGZhc3RhdGUgKHN0YXRlX251bSBz LCBzdHJ1Y3QgZGZhICpkLCBzdGF0ZV9udW0gdHJhbnNbXSkKICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICBkLT5zdGF0ZXNbc10uY29udGV4dCwgQ1RYX0FOWSkpCiAgICAg ICAgICAgICB7CiAgICAgICAgICAgICAgIGlmIChkLT5zdGF0ZXNbc10ubWJwcy5uZWxlbSA9PSAw KQotICAgICAgICAgICAgICAgIGFsbG9jX3Bvc2l0aW9uX3NldCAoJmQtPnN0YXRlc1tzXS5tYnBz LCAxKTsKKyAgICAgICAgICAgICAgICBhbGxvY19wb3NpdGlvbl9zZXQgKCZkLT5zdGF0ZXNbc10u bWJwcywKKyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGQtPmZvbGxvd3NbcG9z LmluZGV4XS5uZWxlbSk7CiAgICAgICAgICAgICAgIGZvciAoaiA9IDA7IGogPCBkLT5mb2xsb3dz W3Bvcy5pbmRleF0ubmVsZW07ICsraikKLSAgICAgICAgICAgICAgICBpbnNlcnQgKGQtPmZvbGxv d3NbcG9zLmluZGV4XS5lbGVtc1tqXSwgJihkLT5zdGF0ZXNbc10ubWJwcykpOworICAgICAgICAg ICAgICAgIGluc2VydCAoZC0+Zm9sbG93c1twb3MuaW5kZXhdLmVsZW1zW2pdLAorICAgICAgICAg ICAgICAgICAgICAgICAgJihkLT5zdGF0ZXNbc10ubWJwcykpOwogICAgICAgICAgICAgfQogICAg ICAgICB9CiAgICAgICBlbHNlCkBAIC0yOTg0LDE2ICsyOTk0LDYgQEAgdHJhbnNpdF9zdGF0ZV9z aW5nbGVieXRlIChzdHJ1Y3QgZGZhICpkLCBzdGF0ZV9udW0gcywgdW5zaWduZWQgY2hhciBjb25z dCAqKnBwKQogewogICBzdGF0ZV9udW0gKnQ7CiAKLSAgaWYgKCoqcHAgPT0gZW9sYnl0ZSkKLSAg ICB7Ci0gICAgICAvKiBTIGlzIGFsd2F5cyBhbiBpbml0aWFsIHN0YXRlIGluIHRyYW5zaXRfc3Rh dGUsIHNvIHRoZQotICAgICAgICAgdHJhbnNpdGlvbiB0YWJsZSBmb3IgdGhlIHN0YXRlIG11c3Qg aGF2ZSBiZWVuIGJ1aWx0IGFscmVhZHkuICAqLwotICAgICAgYXNzZXJ0IChkLT50cmFuc1tzXSB8 fCBkLT5mYWlsc1tzXSk7Ci0KLSAgICAgICsrKnBwOwotICAgICAgcmV0dXJuIGQtPm5ld2xpbmVz W3NdOwotICAgIH0KLQogICBpZiAoZC0+dHJhbnNbc10pCiAgICAgdCA9IGQtPnRyYW5zW3NdOwog ICBlbHNlIGlmIChkLT5mYWlsc1tzXSkKQEAgLTMwMjAsMTUgKzMwMjAsMTIgQEAgc3RhdGljIHN0 YXRlX251bQogdHJhbnNpdF9zdGF0ZSAoc3RydWN0IGRmYSAqZCwgc3RhdGVfbnVtIHMsIHVuc2ln bmVkIGNoYXIgY29uc3QgKipwcCwKICAgICAgICAgICAgICAgIHVuc2lnbmVkIGNoYXIgY29uc3Qg KmVuZCkKIHsKLSAgc3RhdGVfbnVtIHMxOworICBzdGF0ZV9udW0gczEsIHMyOwogICB3aW50X3Qg d2M7CiAgIGludCBzZXBhcmF0ZV9jb250ZXh0czsKLSAgc3RhdGVfbnVtIHN0YXRlLCBzdGF0ZV9u ZXdsaW5lOwogICBzaXplX3QgaSwgajsKIAogICBpbnQgbWJjbGVuID0gbWJzX3RvX3djaGFyICgm d2MsIChjaGFyIGNvbnN0ICopICpwcCwgZW5kIC0gKnBwLCBkKTsKLSAgaW50IGNvbnRleHQgPSB3 YyA9PSBlb2xieXRlID8gQ1RYX05FV0xJTkUgOiBDVFhfTk9ORTsKLSAgYm9vbCBjb250ZXh0X25l d2xpbmUgPSBjb250ZXh0ID09IENUWF9ORVdMSU5FOwogCiAgIC8qIFRoaXMgc3RhdGUgaGFzIHNv bWUgb3BlcmF0b3JzIHdoaWNoIGNhbiBtYXRjaCBhIG11bHRpYnl0ZSBjaGFyYWN0ZXIuICAqLwog ICBkLT5tYl9mb2xsb3dzLm5lbGVtID0gMDsKQEAgLTMwNTEsNyArMzA0OCw3IEBAIHRyYW5zaXRf c3RhdGUgKHN0cnVjdCBkZmEgKmQsIHN0YXRlX251bSBzLCB1bnNpZ25lZCBjaGFyIGNvbnN0ICoq cHAsCiAgICAgICBmb3IgKGkgPSAwOyBpIDwgZC0+c3RhdGVzW3MxXS5tYnBzLm5lbGVtOyArK2kp CiAgICAgICAgIHsKICAgICAgICAgICBpZiAoIVNVQ0NFRURTX0lOX0NPTlRFWFQgKGQtPnN0YXRl c1tzMV0ubWJwcy5lbGVtc1tpXS5jb25zdHJhaW50LAotICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgICAgZC0+c3RhdGVzW3MxXS5jb250ZXh0LCBjb250ZXh0KSkKKyAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgIGQtPnN0YXRlc1tzMV0uY29udGV4dCwgQ1RYX05PTkUp KQogICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgICAgZm9yIChqID0gMDsgaiA8IGQtPmZv bGxvd3NbZC0+c3RhdGVzW3MxXS5tYnBzLmVsZW1zW2ldLmluZGV4XS5uZWxlbTsKICAgICAgICAg ICAgICAgIGorKykKQEAgLTMwNjAsMTAgKzMwNTcsNyBAQCB0cmFuc2l0X3N0YXRlIChzdHJ1Y3Qg ZGZhICpkLCBzdGF0ZV9udW0gcywgdW5zaWduZWQgY2hhciBjb25zdCAqKnBwLAogICAgICAgICB9 CiAKICAgICAgIHNlcGFyYXRlX2NvbnRleHRzID0gc3RhdGVfc2VwYXJhdGVfY29udGV4dHMgKCZk LT5tYl9mb2xsb3dzKTsKLSAgICAgIGlmIChjb250ZXh0X25ld2xpbmUgJiYgc2VwYXJhdGVfY29u dGV4dHMgJiBDVFhfTkVXTElORSkKLSAgICAgICAgcyA9IHN0YXRlX2luZGV4IChkLCAmZC0+bWJf Zm9sbG93cywgQ1RYX05FV0xJTkUpOwotICAgICAgZWxzZQotICAgICAgICBzID0gc3RhdGVfaW5k ZXggKGQsICZkLT5tYl9mb2xsb3dzLCBzZXBhcmF0ZV9jb250ZXh0cyBeIENUWF9BTlkpOworICAg ICAgcyA9IHN0YXRlX2luZGV4IChkLCAmZC0+bWJfZm9sbG93cywgc2VwYXJhdGVfY29udGV4dHMg XiBDVFhfQU5ZKTsKICAgICAgIHJlYWxsb2NfdHJhbnNfaWZfbmVjZXNzYXJ5IChkLCBzKTsKIAog ICAgICAgcmV0dXJuIHM7CkBAIC0zMDkxLDE3ICszMDg1LDE0IEBAIHRyYW5zaXRfc3RhdGUgKHN0 cnVjdCBkZmEgKmQsIHN0YXRlX251bSBzLCB1bnNpZ25lZCBjaGFyIGNvbnN0ICoqcHAsCiAgICAg ICBkLT5zdGF0ZXNbczFdLm1iX3RyaW5kZXggPSBkLT5tYl90cmNvdW50Kys7CiAgICAgfQogCi0g IHNpemVfdCBtYl9pbmRleCA9IGQtPnN0YXRlc1tzMV0ubWJfdHJpbmRleCA8PCAxIHwgKGNvbnRl eHRfbmV3bGluZQotICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICA/IDEgOiAwKTsKLQogICBpZiAoZC0+bWJfdHJhbnNbc10gPT0gTlVMTCkKICAgICB7 Ci0gICAgICBkLT5tYl90cmFuc1tzXSA9IHhubWFsbG9jICgyICogTUFYX1RSQ09VTlQsIHNpemVv ZiAqZC0+bWJfdHJhbnNbc10pOwotICAgICAgZm9yIChpID0gMDsgaSA8IDIgKiBNQVhfVFJDT1VO VDsgaSsrKQorICAgICAgZC0+bWJfdHJhbnNbc10gPSB4bm1hbGxvYyAoTUFYX1RSQ09VTlQsIHNp emVvZiAqZC0+bWJfdHJhbnNbc10pOworICAgICAgZm9yIChpID0gMDsgaSA8IE1BWF9UUkNPVU5U OyBpKyspCiAgICAgICAgIGQtPm1iX3RyYW5zW3NdW2ldID0gLTE7CiAgICAgfQotICBlbHNlIGlm IChkLT5tYl90cmFuc1tzXVttYl9pbmRleF0gPj0gMCkKLSAgICByZXR1cm4gZC0+bWJfdHJhbnNb c11bbWJfaW5kZXhdOworICBlbHNlIGlmIChkLT5tYl90cmFuc1tzXVtkLT5zdGF0ZXNbczFdLm1i X3RyaW5kZXhdID49IDApCisgICAgcmV0dXJuIGQtPm1iX3RyYW5zW3NdW2QtPnN0YXRlc1tzMV0u bWJfdHJpbmRleF07CiAKICAgaWYgKHMgPCAwKQogICAgIGNvcHkgKCZkLT5zdGF0ZXNbczFdLm1i cHMsICZkLT5tYl9mb2xsb3dzKTsKQEAgLTMxMDksMTcgKzMxMDAsMTIgQEAgdHJhbnNpdF9zdGF0 ZSAoc3RydWN0IGRmYSAqZCwgc3RhdGVfbnVtIHMsIHVuc2lnbmVkIGNoYXIgY29uc3QgKipwcCwK ICAgICBtZXJnZSAoJmQtPnN0YXRlc1tzMV0ubWJwcywgJmQtPnN0YXRlc1tzXS5lbGVtcywgJmQt Pm1iX2ZvbGxvd3MpOwogCiAgIHNlcGFyYXRlX2NvbnRleHRzID0gc3RhdGVfc2VwYXJhdGVfY29u dGV4dHMgKCZkLT5tYl9mb2xsb3dzKTsKLSAgc3RhdGUgPSBzdGF0ZV9pbmRleCAoZCwgJmQtPm1i X2ZvbGxvd3MsIHNlcGFyYXRlX2NvbnRleHRzIF4gQ1RYX0FOWSk7Ci0gIGlmIChzZXBhcmF0ZV9j b250ZXh0cyAmIENUWF9ORVdMSU5FKQotICAgIHN0YXRlX25ld2xpbmUgPSBzdGF0ZV9pbmRleCAo ZCwgJmQtPm1iX2ZvbGxvd3MsIENUWF9ORVdMSU5FKTsKLSAgZWxzZQotICAgIHN0YXRlX25ld2xp bmUgPSBzdGF0ZTsKLSAgcmVhbGxvY190cmFuc19pZl9uZWNlc3NhcnkgKGQsIHN0YXRlX25ld2xp bmUpOworICBzMiA9IHN0YXRlX2luZGV4IChkLCAmZC0+bWJfZm9sbG93cywgc2VwYXJhdGVfY29u dGV4dHMgXiBDVFhfQU5ZKTsKKyAgcmVhbGxvY190cmFuc19pZl9uZWNlc3NhcnkgKGQsIHMyKTsK IAotICBkLT5tYl90cmFuc1tzXVttYl9pbmRleCAmIH4wXSA9IHN0YXRlOwotICBkLT5tYl90cmFu c1tzXVttYl9pbmRleCB8IDFdID0gc3RhdGVfbmV3bGluZTsKKyAgZC0+bWJfdHJhbnNbc11bZC0+ c3RhdGVzW3MxXS5tYl90cmluZGV4XSA9IHMyOwogCi0gIHJldHVybiBjb250ZXh0X25ld2xpbmUg PyBzdGF0ZV9uZXdsaW5lIDogc3RhdGU7CisgIHJldHVybiBzMjsKIH0KIAogLyogVGhlIGluaXRp YWwgc3RhdGUgbWF5IGVuY291bnRlciBhIGJ5dGUgd2hpY2ggaXMgbm90IGEgc2luZ2xlIGJ5dGUg Y2hhcmFjdGVyCkBAIC0zMjQ2LDEwICszMjMyLDggQEAgZGZhZXhlY19tYWluIChzdHJ1Y3QgZGZh ICpkLCBjaGFyIGNvbnN0ICpiZWdpbiwgY2hhciAqZW5kLCBib29sIGFsbG93X25sLAogICAgICAg ICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgfQogCi0gICAgICAgICAgICAgIGlmIChk LT5zdGF0ZXNbc10ubWJwcy5uZWxlbSA9PSAwIHx8ICgqcCA9PSBlb2wgJiYgIWFsbG93X25sKQot ICAgICAgICAgICAgICAgICAgfHwgKCpwID09ICdcbicgJiYgIShzeW50YXhfYml0cyAmIFJFX0RP VF9ORVdMSU5FKSkKLSAgICAgICAgICAgICAgICAgIHx8ICgqcCA9PSAnXDAnICYmIChzeW50YXhf Yml0cyAmIFJFX0RPVF9OT1RfTlVMTCkpCi0gICAgICAgICAgICAgICAgICB8fCAoY2hhciAqKSBw ID49IGVuZCkKKyAgICAgICAgICAgICAgaWYgKGQtPnN0YXRlc1tzXS5tYnBzLm5lbGVtID09IDAK KyAgICAgICAgICAgICAgICAgIHx8IG1icnRvd2NfY2FjaGVbKnBdICE9IFdFT0YgfHwgKGNoYXIg KikgcCA+PSBlbmQpCiAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgLyogSWYg YW4gaW5wdXQgY2hhcmFjdGVyIGRvZXMgbm90IG1hdGNoIEFOWUNIQVIsIGRvIGl0CiAgICAgICAg ICAgICAgICAgICAgICBsaWtlIGEgc2luZ2xlLWJ5dGUgY2hhcmFjdGVyLiAgKi8KQEAgLTMyNTgs OCArMzI0Miw2IEBAIGRmYWV4ZWNfbWFpbiAoc3RydWN0IGRmYSAqZCwgY2hhciBjb25zdCAqYmVn aW4sIGNoYXIgKmVuZCwgYm9vbCBhbGxvd19ubCwKICAgICAgICAgICAgICAgZWxzZQogICAgICAg ICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgIHMgPSB0cmFuc2l0X3N0YXRlIChkLCBzLCAm cCwgKHVuc2lnbmVkIGNoYXIgKikgZW5kKTsKLSAgICAgICAgICAgICAgICAgIGlmIChzID49IDAg JiYgcFstMV0gPT0gZW9sKQotICAgICAgICAgICAgICAgICAgICBubGNvdW50Kys7CiAgICAgICAg ICAgICAgICAgICBtYnAgPSBwOwogICAgICAgICAgICAgICAgICAgdHJhbnMgPSBkLT50cmFuczsK ICAgICAgICAgICAgICAgICB9CkBAIC0zMzExLDEwICszMjkzLDcgQEAgZGZhZXhlY19tYWluIChz dHJ1Y3QgZGZhICpkLCBjaGFyIGNvbnN0ICpiZWdpbiwgY2hhciAqZW5kLCBib29sIGFsbG93X25s LAogCiAgICAgICAgICAgczEgPSBzOwogICAgICAgICAgIGlmICghbXVsdGlieXRlIHx8IGQtPnN0 YXRlc1tzXS5tYnBzLm5lbGVtID09IDAKLSAgICAgICAgICAgICAgfHwgKCpwID09IGVvbCAmJiAh YWxsb3dfbmwpCi0gICAgICAgICAgICAgIHx8ICgqcCA9PSAnXG4nICYmICEoc3ludGF4X2JpdHMg JiBSRV9ET1RfTkVXTElORSkpCi0gICAgICAgICAgICAgIHx8ICgqcCA9PSAnXDAnICYmIChzeW50 YXhfYml0cyAmIFJFX0RPVF9OT1RfTlVMTCkpCi0gICAgICAgICAgICAgIHx8IChjaGFyICopIHAg Pj0gZW5kKQorICAgICAgICAgICAgICB8fCBtYnJ0b3djX2NhY2hlWypwXSAhPSBXRU9GIHx8IChj aGFyICopIHAgPj0gZW5kKQogICAgICAgICAgICAgewogICAgICAgICAgICAgICAvKiBJZiBhIGlu cHV0IGNoYXJhY3RlciBkb2VzIG5vdCBtYXRjaCBBTllDSEFSLCBkbyBpdAogICAgICAgICAgICAg ICAgICBsaWtlIGEgc2luZ2xlLWJ5dGUgY2hhcmFjdGVyLiAgKi8KQEAgLTMzMjMsOCArMzMwMiw2 IEBAIGRmYWV4ZWNfbWFpbiAoc3RydWN0IGRmYSAqZCwgY2hhciBjb25zdCAqYmVnaW4sIGNoYXIg KmVuZCwgYm9vbCBhbGxvd19ubCwKICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICB7CiAgICAg ICAgICAgICAgIHMgPSB0cmFuc2l0X3N0YXRlIChkLCBzLCAmcCwgKHVuc2lnbmVkIGNoYXIgKikg ZW5kKTsKLSAgICAgICAgICAgICAgaWYgKHMgPj0gMCAmJiBwWy0xXSA9PSBlb2wpCi0gICAgICAg ICAgICAgICAgbmxjb3VudCsrOwogICAgICAgICAgICAgICBtYnAgPSBwOwogICAgICAgICAgICAg ICB0cmFucyA9IGQtPnRyYW5zOwogICAgICAgICAgICAgfQotLSAKMS43LjEKCg== --------_578213EE0000000023EF_MULTIPART_MIXED_-- ------------=_1472755862-3829-1-- From unknown Sat Jun 21 10:34:42 2025 X-Loop: help-debbugs@gnu.org Subject: bug#23932: dfa: use algorithm for single byte character to any single byte character in input text always Resent-From: Jim Meyering Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Fri, 02 Sep 2016 03:27:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 23932 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: 23932@debbugs.gnu.org, Paul Eggert , Norihiro Tanaka Received: via spool by 23932-submit@debbugs.gnu.org id=B23932.147278681018299 (code B ref 23932); Fri, 02 Sep 2016 03:27:02 +0000 Received: (at 23932) by debbugs.gnu.org; 2 Sep 2016 03:26:50 +0000 Received: from localhost ([127.0.0.1]:46837 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bff7y-0004l5-F8 for submit@debbugs.gnu.org; Thu, 01 Sep 2016 23:26:50 -0400 Received: from mail-vk0-f50.google.com ([209.85.213.50]:33616) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bff7v-0004kq-R8 for 23932@debbugs.gnu.org; Thu, 01 Sep 2016 23:26:48 -0400 Received: by mail-vk0-f50.google.com with SMTP id f76so12895231vke.0 for <23932@debbugs.gnu.org>; Thu, 01 Sep 2016 20:26:47 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to; bh=U4WG5aiqFwtn3BTJBbL+mQaVw/yOGltylJsvIe8r47Y=; b=fxAe0X8vq2IxN3/SDrIMVrhAbSupM1IJg9+P0c9teV+8K44Prbu9XD/u3u6aIiOc7M EpbHHQz1RJbA97l9And9cYLG1T5Enty4wcpD+y7WPeVvejqmMzWJ5QVfiSIwni88cCAj Wo5eN13K+0ICYnkLiHWL/TDxuAXKyGK+C2r1ToD4lXfyFzwWiEEB14uVF9MpVp/2RWNL ckahJtsPZ9xoWPQjfXY4bDmBQbIu8hZa2HLDuY10Vx+2HCtJjZpRRfkNYcaF0C6jN+3Z Mc00CNDp3OsS2N5uJM9g1srG5hQqdHjthNVs5+njWZ+JhMXJB7eUcmPRmlW7N2oksXbO 86vA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:sender:in-reply-to:references:from :date:message-id:subject:to; bh=U4WG5aiqFwtn3BTJBbL+mQaVw/yOGltylJsvIe8r47Y=; b=ctwU9hVHtv87mpT0w4VdZPQ9wtkEpBcfTrVlIk/naSlOyXSYlXpvTgy6nuf+WSJPvQ wzpN2pa34dXGjMHGMFtZKY0C7tdmRECHIi4LA4Iz4/wTOco1JGcPhSDtoKLPiDl9XXsc XNdsYS9dpIzlNf9Q322Qz0qnzNv2EvIUGaFLTcpCzlkYQExsHVtGv8gWyHZR9xHyziPy NdY1wFlXnlkvF+iZtdoLzPrVAQ8ixBKbSw1/Ow1nIl3nL7IH8T7GnmSULq7TcyGgSG2Z VEBUfVm8zlkOqVeZFYP3pFwiMLoGY7jEKCMAuX2MSnuNe7axyz5LYUrIkwBFlZ7nAFjP nIAw== X-Gm-Message-State: AE9vXwMGotcmT1hyjiZqXoh1oR9gha7KYFSRAV+EUGT/lVrJ173ukpD6Rr4WiOvBapL8DD701msZCZ9XrfnhZA== X-Received: by 10.31.148.147 with SMTP id w141mr11659423vkd.1.1472786802332; Thu, 01 Sep 2016 20:26:42 -0700 (PDT) MIME-Version: 1.0 Received: by 10.176.81.172 with HTTP; Thu, 1 Sep 2016 20:26:22 -0700 (PDT) In-Reply-To: <5899b1c2-d352-61e4-fc3d-eaf3ed59ed26@cs.ucla.edu> References: <20160710185143.23FB.27F6AC2D@kcn.ne.jp> <5899b1c2-d352-61e4-fc3d-eaf3ed59ed26@cs.ucla.edu> From: Jim Meyering Date: Thu, 1 Sep 2016 20:26:22 -0700 X-Google-Sender-Auth: IoBe_ycoJu1sGReE5o2FXDI-A9c Message-ID: Content-Type: text/plain; charset=UTF-8 X-Spam-Score: -0.7 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.7 (/) On Thu, Sep 1, 2016 at 11:49 AM, Paul Eggert wrote: > Thanks for that set of patches too. I rebased it and tweaked NEWS and > installed the resulting patch set (attached) into Savannah master. Nice. Thanks to both of you for all that work. From unknown Sat Jun 21 10:34:42 2025 X-Loop: help-debbugs@gnu.org Subject: bug#23932: dfa: use algorithm for single byte character to any single byte character in input text always Resent-From: Norihiro Tanaka Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Sat, 03 Sep 2016 01:28:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 23932 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: Paul Eggert Cc: 23932-done@debbugs.gnu.org Received: via spool by 23932-done@debbugs.gnu.org id=D23932.14728660721876 (code D ref 23932); Sat, 03 Sep 2016 01:28:02 +0000 Received: (at 23932-done) by debbugs.gnu.org; 3 Sep 2016 01:27:52 +0000 Received: from localhost ([127.0.0.1]:48135 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bfzkO-0000UC-1Z for submit@debbugs.gnu.org; Fri, 02 Sep 2016 21:27:52 -0400 Received: from mailgw01.kcn.ne.jp ([61.86.7.208]:38274) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bfzkL-0000U3-Pk for 23932-done@debbugs.gnu.org; Fri, 02 Sep 2016 21:27:50 -0400 Received: from mxs01-s (mailgw1.kcn.ne.jp [61.86.15.233]) by mailgw01.kcn.ne.jp (Postfix) with ESMTP id B58CC4A0854 for <23932-done@debbugs.gnu.org>; Sat, 3 Sep 2016 10:27:46 +0900 (JST) X-matriXscan-loop-detect: d2f843930df2ff4210738cac3d3afee2bc619de4 Received: from mail04.kcn.ne.jp ([61.86.6.183]) by mxs01-s with ESMTP; Sat, 03 Sep 2016 10:27:43 +0900 (JST) Received: from [10.120.1.18] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail04.kcn.ne.jp (Postfix) with ESMTPA id E05C01290022; Sat, 3 Sep 2016 10:27:42 +0900 (JST) Date: Sat, 03 Sep 2016 10:27:40 +0900 From: Norihiro Tanaka In-Reply-To: <5899b1c2-d352-61e4-fc3d-eaf3ed59ed26@cs.ucla.edu> References: <5899b1c2-d352-61e4-fc3d-eaf3ed59ed26@cs.ucla.edu> Message-Id: <20160903102739.DE2A.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_57CA23E500000000DE42_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-matriXscan-Sophos-AV: Clean X-matriXscan-Action: Approve X-matriXscan: Uncategorized X-Spam-Score: -1.5 (-) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.5 (-) --------_57CA23E500000000DE42_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit On Thu, 1 Sep 2016 11:49:59 -0700 Paul Eggert wrote: > Thanks for that set of patches too. I rebased it and tweaked NEWS and installed the resulting patch set (attached) into Savannah master. Thanks for reviewing and installing. BTW, I seem that you lost a part of my proposition on rebase. If it is not intentional, would you review the part again? --------_57CA23E500000000DE42_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII"; name="0001-dfa-additional-change-for-use-single-byte-algorithm-.patch" Content-Disposition: attachment; filename="0001-dfa-additional-change-for-use-single-byte-algorithm-.patch" Content-Transfer-Encoding: base64 RnJvbSAzOTI0MDdiYmEzNmVlMTg5YTYyYWY2YjRhMDhjMTM0NzZmYThmYmJjIE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBOb3JpaGlybyBUYW5ha2EgPG5vcml0bmtAa2NuLm5lLmpwPgpE YXRlOiBTYXQsIDMgU2VwIDIwMTYgMTA6MTE6NTYgKzA5MDAKU3ViamVjdDogW1BBVENIXSBkZmE6 IGFkZGl0aW9uYWwgY2hhbmdlIGZvciB1c2Ugc2luZ2xlLWJ5dGUgYWxnb3JpdGhtIGV2ZW4gaW4g bm9uLVVURi04CgoqIHNyYy9kZmEuYyAoZGZhZXhlY19tYWluKTogRG8gaXQuCi0tLQogc3JjL2Rm YS5jIHwgICAgNSArLS0tLQogMSBmaWxlcyBjaGFuZ2VkLCAxIGluc2VydGlvbnMoKyksIDQgZGVs ZXRpb25zKC0pCgpkaWZmIC0tZ2l0IGEvc3JjL2RmYS5jIGIvc3JjL2RmYS5jCmluZGV4IGUwMDli YzYuLmU3YjkyYmEgMTAwNjQ0Ci0tLSBhL3NyYy9kZmEuYworKysgYi9zcmMvZGZhLmMKQEAgLTMx ODMsMTAgKzMxODMsNyBAQCBkZmFleGVjX21haW4gKHN0cnVjdCBkZmEgKmQsIGNoYXIgY29uc3Qg KmJlZ2luLCBjaGFyICplbmQsIGJvb2wgYWxsb3dfbmwsCiAKICAgICAgICAgICBzMSA9IHM7CiAg ICAgICAgICAgaWYgKCFtdWx0aWJ5dGUgfHwgZC0+c3RhdGVzW3NdLm1icHMubmVsZW0gPT0gMAot ICAgICAgICAgICAgICB8fCAoKnAgPT0gZW9sICYmICFhbGxvd19ubCkKLSAgICAgICAgICAgICAg fHwgKCpwID09ICdcbicgJiYgIShkLT5zeW50YXguc3ludGF4X2JpdHMgJiBSRV9ET1RfTkVXTElO RSkpCi0gICAgICAgICAgICAgIHx8ICgqcCA9PSAnXDAnICYmIChkLT5zeW50YXguc3ludGF4X2Jp dHMgJiBSRV9ET1RfTk9UX05VTEwpKQotICAgICAgICAgICAgICB8fCAoY2hhciAqKSBwID49IGVu ZCkKKyAgICAgICAgICAgICAgfHwgZC0+bG9jYWxlaW5mby5zYmN0b3djWypwXSAhPSBXRU9GIHx8 IChjaGFyICopIHAgPj0gZW5kKQogICAgICAgICAgICAgewogICAgICAgICAgICAgICAvKiBJZiBh IGlucHV0IGNoYXJhY3RlciBkb2VzIG5vdCBtYXRjaCBBTllDSEFSLCBkbyBpdAogICAgICAgICAg ICAgICAgICBsaWtlIGEgc2luZ2xlLWJ5dGUgY2hhcmFjdGVyLiAgKi8KLS0gCjEuNy4xCgo= --------_57CA23E500000000DE42_MULTIPART_MIXED_-- From unknown Sat Jun 21 10:34:42 2025 X-Loop: help-debbugs@gnu.org Subject: bug#23932: dfa: use algorithm for single byte character to any single byte character in input text always Resent-From: Paul Eggert Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Sat, 03 Sep 2016 03:01:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 23932 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: Norihiro Tanaka Cc: 23932-done@debbugs.gnu.org Received: via spool by 23932-done@debbugs.gnu.org id=D23932.147287162110771 (code D ref 23932); Sat, 03 Sep 2016 03:01:02 +0000 Received: (at 23932-done) by debbugs.gnu.org; 3 Sep 2016 03:00:21 +0000 Received: from localhost ([127.0.0.1]:48159 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bg1Bs-0002nf-OF for submit@debbugs.gnu.org; Fri, 02 Sep 2016 23:00:20 -0400 Received: from zimbra.cs.ucla.edu ([131.179.128.68]:45455) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bg1Br-0002nT-LV for 23932-done@debbugs.gnu.org; Fri, 02 Sep 2016 23:00:20 -0400 Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id A9D551613E6; Fri, 2 Sep 2016 20:00:13 -0700 (PDT) Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10032) with ESMTP id ttuFHV7O13rR; Fri, 2 Sep 2016 20:00:13 -0700 (PDT) Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id 0E61B1613DF; Fri, 2 Sep 2016 20:00:13 -0700 (PDT) X-Virus-Scanned: amavisd-new at zimbra.cs.ucla.edu Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id s0JDUbZcJeAz; Fri, 2 Sep 2016 20:00:12 -0700 (PDT) Received: from [192.168.1.9] (unknown [100.32.155.148]) by zimbra.cs.ucla.edu (Postfix) with ESMTPSA id E53321613D5; Fri, 2 Sep 2016 20:00:12 -0700 (PDT) References: <5899b1c2-d352-61e4-fc3d-eaf3ed59ed26@cs.ucla.edu> <20160903102739.DE2A.27F6AC2D@kcn.ne.jp> From: Paul Eggert Organization: UCLA Computer Science Department Message-ID: <12521249-67fe-6fc7-c4c2-85a949e686a9@cs.ucla.edu> Date: Fri, 2 Sep 2016 20:00:12 -0700 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.2.0 MIME-Version: 1.0 In-Reply-To: <20160903102739.DE2A.27F6AC2D@kcn.ne.jp> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -1.5 (-) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.5 (-) Norihiro Tanaka wrote: > I seem that you lost a part > of my proposition on rebase. If it is not intentional, would you review > the part again? Thanks for catching that; it was not intentional. I installed your patch. From unknown Sat Jun 21 10:34:42 2025 X-Loop: help-debbugs@gnu.org Subject: bug#23932: dfa: use algorithm for single byte character to any single byte character in input text always Resent-From: Norihiro Tanaka Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Sat, 03 Sep 2016 03:06:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 23932 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: Paul Eggert Cc: 23932-done@debbugs.gnu.org Received: via spool by 23932-done@debbugs.gnu.org id=D23932.147287194811271 (code D ref 23932); Sat, 03 Sep 2016 03:06:01 +0000 Received: (at 23932-done) by debbugs.gnu.org; 3 Sep 2016 03:05:48 +0000 Received: from localhost ([127.0.0.1]:48167 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bg1HA-0002vi-JI for submit@debbugs.gnu.org; Fri, 02 Sep 2016 23:05:48 -0400 Received: from mailgw06.kcn.ne.jp ([61.86.7.213]:52275) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bg1H8-0002vS-AO for 23932-done@debbugs.gnu.org; Fri, 02 Sep 2016 23:05:46 -0400 Received: from mxs01-s (mailgw1.kcn.ne.jp [61.86.15.233]) by mailgw06.kcn.ne.jp (Postfix) with ESMTP id C7BA9F800F for <23932-done@debbugs.gnu.org>; Sat, 3 Sep 2016 12:05:38 +0900 (JST) X-matriXscan-loop-detect: c93f425f08d44a65d14feade903699c3915c95df Received: from mail09.kcn.ne.jp ([61.86.6.188]) by mxs01-s with ESMTP; Sat, 03 Sep 2016 12:05:38 +0900 (JST) Received: from [10.120.1.18] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail09.kcn.ne.jp (Postfix) with ESMTPA id 30ECD1BD0096; Sat, 3 Sep 2016 12:05:38 +0900 (JST) Date: Sat, 03 Sep 2016 12:05:35 +0900 From: Norihiro Tanaka In-Reply-To: <12521249-67fe-6fc7-c4c2-85a949e686a9@cs.ucla.edu> References: <20160903102739.DE2A.27F6AC2D@kcn.ne.jp> <12521249-67fe-6fc7-c4c2-85a949e686a9@cs.ucla.edu> Message-Id: <20160903120534.DE36.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-matriXscan-Sophos-AV: Clean X-matriXscan-Action: Approve X-matriXscan: Uncategorized X-Spam-Score: -1.5 (-) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.5 (-) On Fri, 2 Sep 2016 20:00:12 -0700 Paul Eggert wrote: > Norihiro Tanaka wrote: > > > I seem that you lost a part > > of my proposition on rebase. If it is not intentional, would you review > > the part again? > > Thanks for catching that; it was not intentional. I installed your patch. Thanks for catching up.