From unknown Tue Aug 12 08:32:41 2025 X-Loop: help-debbugs@gnu.org Subject: bug#17013: [PATCH] grep: optimization by using the Galil rule for Boyer-Moore algorithm in KWSet Resent-From: Norihiro Tanaka Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Fri, 14 Mar 2014 12:22:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 17013 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: 17013@debbugs.gnu.org X-Debbugs-Original-To: submit@debbugs.gnu.org Received: via spool by submit@debbugs.gnu.org id=B.139479969827160 (code B ref -1); Fri, 14 Mar 2014 12:22:02 +0000 Received: (at submit) by debbugs.gnu.org; 14 Mar 2014 12:21:38 +0000 Received: from localhost ([127.0.0.1]:36537 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WOR7J-00073z-VR for submit@debbugs.gnu.org; Fri, 14 Mar 2014 08:21:38 -0400 Received: from pbsg501.nifty.com ([202.248.238.71]:51774) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WOR7F-00073k-AY for submit@debbugs.gnu.org; Fri, 14 Mar 2014 08:21:36 -0400 Received: from [10.120.1.51] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) (authenticated) by pbsg501.nifty.com with ESMTP id s2ECLJmt024841 for ; Fri, 14 Mar 2014 21:21:20 +0900 X-Nifty-SrcIP: [118.21.128.66] Date: Fri, 14 Mar 2014 21:21:21 +0900 From: Norihiro Tanaka Message-Id: <20140314212120.7E5E.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_531AAC47000000000212_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.64.06 [ja] X-Spam-Score: 1.2 (+) X-Spam-Report: Spam detection software, running on the system "debbugs.gnu.org", has identified this incoming email as possible spam. The original message has been attached to this so you can view it (if it isn't spam) or label similar future email. If you have any questions, see the administrator of that system for details. Content preview: Package: grep Tags: patch The Boyer-Moore algorithm runs in O(m n) in the worst case, which perhaps it may be much slower than the DFA. The Galil rule enables to change O(m n) into O(n) for its case without overheads and/or slow-down for other cases by avoiding to compare more than once for a position in the text. This patch implements it. [...] Content analysis details: (1.2 points, 10.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- 1.2 RCVD_IN_BL_SPAMCOP_NET RBL: Received via a relay in bl.spamcop.net [Blocked - see ] -0.0 SPF_HELO_PASS SPF: HELO matches SPF record -0.0 T_RP_MATCHES_RCVD Envelope sender domain matches handover relay domain -0.0 SPF_PASS SPF: sender matches SPF record X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 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.2 (+) X-Spam-Report: Spam detection software, running on the system "debbugs.gnu.org", has identified this incoming email as possible spam. The original message has been attached to this so you can view it (if it isn't spam) or label similar future email. If you have any questions, see the administrator of that system for details. Content preview: Package: grep Tags: patch The Boyer-Moore algorithm runs in O(m n) in the worst case, which perhaps it may be much slower than the DFA. The Galil rule enables to change O(m n) into O(n) for its case without overheads and/or slow-down for other cases by avoiding to compare more than once for a position in the text. This patch implements it. [...] Content analysis details: (1.2 points, 10.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- 1.2 RCVD_IN_BL_SPAMCOP_NET RBL: Received via a relay in bl.spamcop.net [Blocked - see ] -0.0 SPF_HELO_PASS SPF: HELO matches SPF record -0.0 T_RP_MATCHES_RCVD Envelope sender domain matches handover relay domain -0.0 SPF_PASS SPF: sender matches SPF record --------_531AAC47000000000212_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit Package: grep Tags: patch The Boyer-Moore algorithm runs in O(m n) in the worst case, which perhaps it may be much slower than the DFA. The Galil rule enables to change O(m n) into O(n) for its case without overheads and/or slow-down for other cases by avoiding to compare more than once for a position in the text. This patch implements it. I prepare following string, which makes a worst case for Boyer-Moore algorithm, to measure the performance. yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 > ../k I run the test with the patch (best-of-5 trials): env LC_ALL=C time -p src/grep kjjjjjjjjjjjjjjjjjjj k real 0.70 user 0.32 sys 0.38 Back out that commit (temporarily), recompile, and rerun the experiment: env LC_ALL=C time -p src/grep kjjjjjjjjjjjjjjjjjjj k real 3.97 user 3.56 sys 0.40 Norihiro --------_531AAC47000000000212_MULTIPART_MIXED_ Content-Type: application/octet-stream; name="grep.patch" Content-Disposition: attachment; filename="grep.patch" Content-Transfer-Encoding: base64 RnJvbSBlNTA2OTM3ZGZmNWViYjk3Njk4NmEyN2Q4Y2I4NGE2OGQ0MWNlM2E1IE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBOb3JpaGlybyBUYW5ha2EgPG5vcml0bmtAa2NuLm5lLmpwPgpE YXRlOiBGcmksIDE0IE1hciAyMDE0IDIxOjEzOjU3ICswOTAwClN1YmplY3Q6IFtQQVRDSF0gZ3Jl cDogb3B0aW1pemF0aW9uIGJ5IHVzaW5nIHRoZSBHYWxpbCBydWxlIGZvciBCb3llci1Nb29yZQog YWxnb3JpdGhtIGluIEtXU2V0CgpUaGUgQm95ZXItTW9vcmUgYWxnb3JpdGhtIHJ1bnMgaW4gTyht IG4pIGluIHRoZSB3b3JzdCBjYXNlLAogd2hpY2ggcGVyaGFwcyBpdCBtYXkgYmUgbXVjaCBzbG93 ZXIgdGhhbiB0aGUgREZBLgoKVGhlIEdhbGlsIHJ1bGUgZW5hYmxlcyB0byBjaGFuZ2UgTyhtIG4p IGludG8gTyhuKSBmb3IgaXRzIGNhc2Ugd2l0aG91dApvdmVyaGVhZHMgYW5kL29yIHNsb3ctZG93 biBmb3Igb3RoZXIgY2FzZXMgYnkgYXZvaWRpbmcgdG8gY29tcGFyZSBtb3JlCnRoYW4gb25jZSBm b3IgYSBwb3NpdGlvbiBpbiB0aGUgdGV4dC4gIFRoaXMgcGF0Y2ggaW1wbGVtZW50cyBpdC4KCkkg cHJlcGFyZSBmb2xsb3dpbmcgc3RyaW5nLCB3aGljaCBtYWtlcyBhIHdvcnN0IGNhc2UgZm9yIEJv eWVyLU1vb3JlCmFsZ29yaXRobSwgdG8gbWVhc3VyZSB0aGUgcGVyZm9ybWFuY2UuCgogICAgeWVz IGpqampqampqampqampqampqampqampqampqampqampqampqampqamogfCBoZWFkIC0xMDAwMDAw MCA+IC4uL2sKCkkgcnVuIHRoZSB0ZXN0IHdpdGggdGhlIHBhdGNoIChiZXN0LW9mLTUgdHJpYWxz KToKCiAgICBlbnYgTENfQUxMPUMgdGltZSAtcCBzcmMvZ3JlcCBrampqampqampqampqampqampq aiBrCiAgICAgICAgcmVhbCAwLjcwICAgICAgIHVzZXIgMC4zMiAgICAgICBzeXMgMC4zOAoKQmFj ayBvdXQgdGhhdCBjb21taXQgKHRlbXBvcmFyaWx5KSwgcmVjb21waWxlLCBhbmQgcmVydW4gdGhl IGV4cGVyaW1lbnQ6CgogICAgZW52IExDX0FMTD1DIHRpbWUgLXAgc3JjL2dyZXAga2pqampqampq ampqampqampqamogawogICAgICAgIHJlYWwgMy45NyAgICAgICB1c2VyIDMuNTYgICAgICAgc3lz IDAuNDAKCiogc3JjL2t3c2V0LmMgKHN0cnVjdCBrd3NldCk6IFJlcGxhY2UgbWVtYmVyIGBtaW5k MicgdG8gYHNoaWZ0Jy4KKGt3c3ByZXApOiBDYWxjdWxhdGUgc2hpZnQgdmFsdWVzIGF0IHRoZSBm YWlsIGF0IGVhY2ggcG9zaXRpb24uCihibWV4ZWMpOiBVc2UgaXQuCi0tLQogc3JjL2t3c2V0LmMg fCA5MyArKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrLS0tLS0t LS0tLS0tLS0tCiAxIGZpbGUgY2hhbmdlZCwgNzAgaW5zZXJ0aW9ucygrKSwgMjMgZGVsZXRpb25z KC0pCgpkaWZmIC0tZ2l0IGEvc3JjL2t3c2V0LmMgYi9zcmMva3dzZXQuYwppbmRleCA0MTBlMDQ2 Li45MDZkYjAxIDEwMDY0NAotLS0gYS9zcmMva3dzZXQuYworKysgYi9zcmMva3dzZXQuYwpAQCAt ODMsNyArODMsNyBAQCBzdHJ1Y3Qga3dzZXQKICAgdW5zaWduZWQgY2hhciBkZWx0YVtOQ0hBUl07 CS8qIERlbHRhIHRhYmxlIGZvciByYXBpZCBzZWFyY2guICovCiAgIHN0cnVjdCB0cmllICpuZXh0 W05DSEFSXTsJLyogVGFibGUgb2YgY2hpbGRyZW4gb2YgdGhlIHJvb3QuICovCiAgIGNoYXIgKnRh cmdldDsJCQkvKiBUYXJnZXQgc3RyaW5nIGlmIHRoZXJlJ3Mgb25seSBvbmUuICovCi0gIGludCBt aW5kMjsJCQkvKiBVc2VkIGluIEJveWVyLU1vb3JlIHNlYXJjaCBmb3Igb25lIHN0cmluZy4gKi8K KyAgaW50ICpzaGlmdDsJCQkvKiBVc2VkIGluIEJveWVyLU1vb3JlIHNlYXJjaCBmb3Igb25lIHN0 cmluZy4gKi8KICAgY2hhciBjb25zdCAqdHJhbnM7CQkvKiBDaGFyYWN0ZXIgdHJhbnNsYXRpb24g dGFibGUuICovCiB9OwogCkBAIC0zODUsNyArMzg1LDcgQEAgY29uc3QgY2hhciAqCiBrd3NwcmVw IChrd3NldF90IGt3cykKIHsKICAgc3RydWN0IGt3c2V0ICprd3NldDsKLSAgaW50IGk7CisgIGlu dCBpLCBqOwogICBzdHJ1Y3QgdHJpZSAqY3VycjsKICAgY2hhciBjb25zdCAqdHJhbnM7CiAgIHVu c2lnbmVkIGNoYXIgZGVsdGFbTkNIQVJdOwpAQCAtNDAxLDggKzQwMSw2IEBAIGt3c3ByZXAgKGt3 c2V0X3Qga3dzKQogICAgICBvZiB0aGUgaGFpcnkgY29tbWVudHotd2FsdGVyIGFsZ29yaXRobS4g Ki8KICAgaWYgKGt3c2V0LT53b3JkcyA9PSAxICYmIGt3c2V0LT50cmFucyA9PSBOVUxMKQogICAg IHsKLSAgICAgIGNoYXIgYzsKLQogICAgICAgLyogTG9va2luZyBmb3IganVzdCBvbmUgc3RyaW5n LiAgRXh0cmFjdCBpdCBmcm9tIHRoZSB0cmllLiAqLwogICAgICAga3dzZXQtPnRhcmdldCA9IG9i c3RhY2tfYWxsb2MoJmt3c2V0LT5vYnN0YWNrLCBrd3NldC0+bWluZCk7CiAgICAgICBpZiAoIWt3 c2V0LT50YXJnZXQpCkBAIC00MTcsMTEgKzQxNSwyMyBAQCBrd3NwcmVwIChrd3NldF90IGt3cykK ICAgICAgICAgZGVsdGFbVShrd3NldC0+dGFyZ2V0W2ldKV0gPSBrd3NldC0+bWluZCAtIChpICsg MSk7CiAgICAgICAvKiBGaW5kIHRoZSBtaW5pbWFsIGRlbHRhMiBzaGlmdCB0aGF0IHdlIG1pZ2h0 IG1ha2UgYWZ0ZXIKICAgICAgICAgIGEgYmFja3dhcmRzIG1hdGNoIGhhcyBmYWlsZWQuICovCi0g ICAgICBjID0ga3dzZXQtPnRhcmdldFtrd3NldC0+bWluZCAtIDFdOwotICAgICAgZm9yIChpID0g a3dzZXQtPm1pbmQgLSAyOyBpID49IDA7IC0taSkKLSAgICAgICAgaWYgKGt3c2V0LT50YXJnZXRb aV0gPT0gYykKLSAgICAgICAgICBicmVhazsKLSAgICAgIGt3c2V0LT5taW5kMiA9IGt3c2V0LT5t aW5kIC0gKGkgKyAxKTsKKyAgICAgIGt3c2V0LT5zaGlmdCA9IChpbnQgKikgb2JzdGFja19hbGxv Yygma3dzZXQtPm9ic3RhY2ssCisgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgc2l6ZW9mICgqa3dzZXQtPnNoaWZ0KSAqIChrd3NldC0+bWluZCAtIDEpKTsKKyAgICAg IGZvciAoaSA9IDE7IGkgPCBrd3NldC0+bWluZDsgKytpKQorICAgICAgIHsKKyAgICAgICAgIGZv ciAoaiA9IGkgKyAxOyBqIDw9IGt3c2V0LT5taW5kOyArK2opCisgICAgICAgICAgIGlmIChtZW1j bXAgKGt3c2V0LT50YXJnZXQgKyBrd3NldC0+bWluZCAtIGosIGt3c2V0LT50YXJnZXQgKyBrd3Nl dC0+bWluZCAtIGksIGkpID09IDApCisgICAgICAgICAgICAgYnJlYWs7CisgICAgICAgICBpZiAo aiA8PSBrd3NldC0+bWluZCkKKyAgICAgICAgICAga3dzZXQtPnNoaWZ0W2kgLSAxXSA9IGogLSBp OworICAgICAgICAgZWxzZQorICAgICAgICAgICB7CisgICAgICAgICAgICAgZm9yIChqID0gaSAt IDE7IGogPj0gMTsgLS1qKQorICAgICAgICAgICAgICAgaWYgKG1lbWNtcCAoa3dzZXQtPnRhcmdl dCwga3dzZXQtPnRhcmdldCArIGt3c2V0LT5taW5kIC0gaiwgaikgPT0gMCkKKyAgICAgICAgICAg ICAgICAgYnJlYWs7CisgICAgICAgICAgICAga3dzZXQtPnNoaWZ0W2kgLSAxXSA9IGt3c2V0LT5t aW5kIC0gajsKKyAgICAgICAgICAgfQorICAgICAgIH0KICAgICB9CiAgIGVsc2UKICAgICB7CkBA IC01MDMsNyArNTEzLDcgQEAgYm1leGVjIChrd3NldF90IGt3cywgY2hhciBjb25zdCAqdGV4dCwg c2l6ZV90IHNpemUpCiAgIHN0cnVjdCBrd3NldCBjb25zdCAqa3dzZXQ7CiAgIHVuc2lnbmVkIGNo YXIgY29uc3QgKmQxOwogICBjaGFyIGNvbnN0ICplcCwgKnNwLCAqdHA7Ci0gIGludCBkLCBnYywg aSwgbGVuLCBtZDI7CisgIGludCBkLCBnYywgaSwgaiwgbGVuOwogCiAgIGt3c2V0ID0gKHN0cnVj dCBrd3NldCBjb25zdCAqKSBrd3M7CiAgIGxlbiA9IGt3c2V0LT5taW5kOwpAQCAtNTIxLDcgKzUz MSw2IEBAIGJtZXhlYyAoa3dzZXRfdCBrd3MsIGNoYXIgY29uc3QgKnRleHQsIHNpemVfdCBzaXpl KQogICBkMSA9IGt3c2V0LT5kZWx0YTsKICAgc3AgPSBrd3NldC0+dGFyZ2V0ICsgbGVuOwogICBn YyA9IFUoc3BbLTJdKTsKLSAgbWQyID0ga3dzZXQtPm1pbmQyOwogICB0cCA9IHRleHQgKyBsZW47 CiAKICAgLyogU2lnbmlmaWNhbmNlIG9mIDEyOiAxIChpbml0aWFsIG9mZnNldCkgKyAxMCAoc2tp cCBsb29wKSArIDEgKG1kMikuICovCkBAIC01NTAsMTQgKzU1OSwzMyBAQCBibWV4ZWMgKGt3c2V0 X3Qga3dzLCBjaGFyIGNvbnN0ICp0ZXh0LCBzaXplX3Qgc2l6ZSkKICAgICAgICAgICB9CiAgICAg ICAgIGJyZWFrOwogICAgICAgZm91bmQ6Ci0gICAgICAgIGlmIChVKHRwWy0yXSkgPT0gZ2MpCisg ICAgICAgIGogPSAzOworICAgICAgICB3aGlsZSAoMSkKICAgICAgICAgICB7Ci0gICAgICAgICAg ICBmb3IgKGkgPSAzOyBpIDw9IGxlbiAmJiBVKHRwWy1pXSkgPT0gVShzcFstaV0pOyArK2kpCi0g ICAgICAgICAgICAgIDsKLSAgICAgICAgICAgIGlmIChpID4gbGVuKQotICAgICAgICAgICAgICBy ZXR1cm4gdHAgLSBsZW4gLSB0ZXh0OworICAgICAgICAgICAgaWYgKFUodHBbLTJdKSA9PSBnYykK KyAgICAgICAgICAgICAgeworICAgICAgICAgICAgICAgIGZvciAoaSA9IDM7IGkgPD0gZCAmJiB0 cFstaV0gPT0gc3BbLWldOyArK2kpCisgICAgICAgICAgICAgICAgICA7CisgICAgICAgICAgICAg ICAgaWYgKGkgPiBkKQorICAgICAgICAgICAgICAgICAgeworICAgICAgICAgICAgICAgICAgICBm b3IgKGkgPSBqOyBpIDw9IGxlbiAmJiB0cFstaV0gPT0gc3BbLWldOyArK2kpCisgICAgICAgICAg ICAgICAgICAgICAgOworICAgICAgICAgICAgICAgICAgICBpZiAoaSA+IGxlbikKKyAgICAgICAg ICAgICAgICAgICAgICByZXR1cm4gdHAgLSBsZW4gLSB0ZXh0OworICAgICAgICAgICAgICAgICAg fQorICAgICAgICAgICAgICAgIGQgPSBrd3NldC0+c2hpZnRbaSAtIDJdOyB0cCArPSBkOworICAg ICAgICAgICAgICAgIGlmICh0cCA+IGVwIHx8IHRwWy0xXSAhPSBzcFstMV0pCisgICAgICAgICAg ICAgICAgICBicmVhazsKKyAgICAgICAgICAgICAgICBqID0gZCArIGk7CisgICAgICAgICAgICAg IH0KKyAgICAgICAgICAgIGVsc2UKKyAgICAgICAgICAgICAgeworICAgICAgICAgICAgICAgIGQg PSBrd3NldC0+c2hpZnRbMF07IHRwICs9IGQ7CisgICAgICAgICAgICAgICAgaWYgKHRwID4gZXAg fHwgdHBbLTFdICE9IHNwWy0xXSkKKyAgICAgICAgICAgICAgICAgIGJyZWFrOworICAgICAgICAg ICAgICAgIGogPSBkICsgMjsKKyAgICAgICAgICAgICAgfQogICAgICAgICAgIH0KLSAgICAgICAg dHAgKz0gbWQyOwogICAgICAgfQogCiAgIC8qIE5vdyB3ZSBoYXZlIG9ubHkgYSBmZXcgY2hhcmFj dGVycyBsZWZ0IHRvIHNlYXJjaC4gIFdlCkBAIC01NjksMTQgKzU5NywzMyBAQCBibWV4ZWMgKGt3 c2V0X3Qga3dzLCBjaGFyIGNvbnN0ICp0ZXh0LCBzaXplX3Qgc2l6ZSkKICAgICAgIGQgPSBkMVtV KCh0cCArPSBkKVstMV0pXTsKICAgICAgIGlmIChkICE9IDApCiAgICAgICAgIGNvbnRpbnVlOwot ICAgICAgaWYgKFUodHBbLTJdKSA9PSBnYykKKyAgICAgIGogPSAzOworICAgICAgd2hpbGUgKDEp CiAgICAgICAgIHsKLSAgICAgICAgICBmb3IgKGkgPSAzOyBpIDw9IGxlbiAmJiBVKHRwWy1pXSkg PT0gVShzcFstaV0pOyArK2kpCi0gICAgICAgICAgICA7Ci0gICAgICAgICAgaWYgKGkgPiBsZW4p Ci0gICAgICAgICAgICByZXR1cm4gdHAgLSBsZW4gLSB0ZXh0OworICAgICAgICAgIGlmIChVKHRw Wy0yXSkgPT0gZ2MpCisgICAgICAgICAgICB7CisgICAgICAgICAgICAgIGZvciAoaSA9IDM7IGkg PD0gZCAmJiB0cFstaV0gPT0gc3BbLWldOyArK2kpCisgICAgICAgICAgICAgICAgOworICAgICAg ICAgICAgICBpZiAoaSA+IGQpCisgICAgICAgICAgICAgICAgeworICAgICAgICAgICAgICAgICAg Zm9yIChpID0gajsgaSA8PSBsZW4gJiYgdHBbLWldID09IHNwWy1pXTsgKytpKQorICAgICAgICAg ICAgICAgICAgICA7CisgICAgICAgICAgICAgICAgICBpZiAoaSA+IGxlbikKKyAgICAgICAgICAg ICAgICAgICAgcmV0dXJuIHRwIC0gbGVuIC0gdGV4dDsKKyAgICAgICAgICAgICAgICB9CisgICAg ICAgICAgICAgIGQgPSBrd3NldC0+c2hpZnRbaSAtIDJdOyB0cCArPSBkOworICAgICAgICAgICAg ICBpZiAodHAgPiBlcCB8fCB0cFstMV0gIT0gc3BbLTFdKQorICAgICAgICAgICAgICAgIGJyZWFr OworICAgICAgICAgICAgICBqID0gZCArIGk7CisgICAgICAgICAgICB9CisgICAgICAgICAgZWxz ZQorICAgICAgICAgICAgeworICAgICAgICAgICAgICBkID0ga3dzZXQtPnNoaWZ0WzBdOyB0cCAr PSBkOworICAgICAgICAgICAgICBpZiAodHAgPiBlcCB8fCB0cFstMV0gIT0gc3BbLTFdKQorICAg ICAgICAgICAgICAgIGJyZWFrOworICAgICAgICAgICAgICBqID0gZCArIDI7CisgICAgICAgICAg ICB9CiAgICAgICAgIH0KLSAgICAgIGQgPSBtZDI7CiAgICAgfQogCiAgIHJldHVybiAtMTsKLS0g CjEuOS4wCgo= --------_531AAC47000000000212_MULTIPART_MIXED_-- From unknown Tue Aug 12 08:32:41 2025 X-Loop: help-debbugs@gnu.org Subject: bug#17013: [PATCH] grep: optimization by using the Galil rule for Boyer-Moore algorithm in KWSet Resent-From: Norihiro Tanaka Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Sat, 15 Mar 2014 06:07:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 17013 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: 17013@debbugs.gnu.org Received: via spool by 17013-submit@debbugs.gnu.org id=B17013.139486359625932 (code B ref 17013); Sat, 15 Mar 2014 06:07:02 +0000 Received: (at 17013) by debbugs.gnu.org; 15 Mar 2014 06:06:36 +0000 Received: from localhost ([127.0.0.1]:37257 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WOhjv-0006k9-J4 for submit@debbugs.gnu.org; Sat, 15 Mar 2014 02:06:36 -0400 Received: from pbsg500.nifty.com ([202.248.238.70]:28998) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WOhjq-0006jn-Bu for 17013@debbugs.gnu.org; Sat, 15 Mar 2014 02:06:33 -0400 Received: from [10.120.1.25] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) (authenticated) by pbsg500.nifty.com with ESMTP id s2F66NhG032466 for <17013@debbugs.gnu.org>; Sat, 15 Mar 2014 15:06:23 +0900 X-Nifty-SrcIP: [118.21.128.66] Date: Sat, 15 Mar 2014 15:06:23 +0900 From: Norihiro Tanaka In-Reply-To: <20140314212120.7E5E.27F6AC2D@kcn.ne.jp> References: <20140314212120.7E5E.27F6AC2D@kcn.ne.jp> Message-Id: <20140315150609.6C6D.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_5323EC49000000006C58_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.64.06 [ja] X-Spam-Score: 1.2 (+) X-Spam-Report: Spam detection software, running on the system "debbugs.gnu.org", has identified this incoming email as possible spam. The original message has been attached to this so you can view it (if it isn't spam) or label similar future email. If you have any questions, see the administrator of that system for details. Content preview: I changed the patch so that the delta2 shift is extracted from the trie, because it's very excellent. Norihiro From 932e0774428e9b5015c9de31b8a509a5d01c4abe Mon Sep 17 00:00:00 2001 From: Norihiro Tanaka Date: Sat, 15 Mar 2014 14:41:52 +0900 Subject: [PATCH] grep: optimization by using the Galil rule for Boyer-Moore algorithm in KWSet [...] Content analysis details: (1.2 points, 10.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- 1.2 RCVD_IN_BL_SPAMCOP_NET RBL: Received via a relay in bl.spamcop.net [Blocked - see ] -0.0 SPF_HELO_PASS SPF: HELO matches SPF record -0.0 T_RP_MATCHES_RCVD Envelope sender domain matches handover relay domain -0.0 SPF_PASS SPF: sender matches SPF record X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 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.2 (+) X-Spam-Report: Spam detection software, running on the system "debbugs.gnu.org", has identified this incoming email as possible spam. The original message has been attached to this so you can view it (if it isn't spam) or label similar future email. If you have any questions, see the administrator of that system for details. Content preview: I changed the patch so that the delta2 shift is extracted from the trie, because it's very excellent. Norihiro From 932e0774428e9b5015c9de31b8a509a5d01c4abe Mon Sep 17 00:00:00 2001 From: Norihiro Tanaka Date: Sat, 15 Mar 2014 14:41:52 +0900 Subject: [PATCH] grep: optimization by using the Galil rule for Boyer-Moore algorithm in KWSet [...] Content analysis details: (1.2 points, 10.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- 1.2 RCVD_IN_BL_SPAMCOP_NET RBL: Received via a relay in bl.spamcop.net [Blocked - see ] -0.0 SPF_HELO_PASS SPF: HELO matches SPF record -0.0 T_RP_MATCHES_RCVD Envelope sender domain matches handover relay domain -0.0 SPF_PASS SPF: sender matches SPF record --------_5323EC49000000006C58_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit I changed the patch so that the delta2 shift is extracted from the trie, because it's very excellent. Norihiro --------_5323EC49000000006C58_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Disposition: attachment; filename="patch.txt" Content-Transfer-Encoding: 7bit >From 932e0774428e9b5015c9de31b8a509a5d01c4abe Mon Sep 17 00:00:00 2001 From: Norihiro Tanaka Date: Sat, 15 Mar 2014 14:41:52 +0900 Subject: [PATCH] grep: optimization by using the Galil rule for Boyer-Moore algorithm in KWSet The Boyer-Moore algorithm runs in O(m n) in the worst case, which perhaps it may be much slower than the DFA. The Galil rule enables to change O(m n) into O(n) for its case without overheads and/or slow-down for other cases by avoiding to compare more than once for a position in the text. To use the Galil rule, looking for the delta2 shift at each position from the trie instead of `mind2' value. I prepare following string, which makes a worst case for Boyer-Moore algorithm, to measure the performance. yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 > k I run the test with the patch (best-of-5 trials): env LC_ALL=C time -p src/grep kjjjjjjjjjjjjjjjjjjj k real 0.70 user 0.32 sys 0.38 Back out that commit (temporarily), recompile, and rerun the experiment: env LC_ALL=C time -p src/grep kjjjjjjjjjjjjjjjjjjj k real 3.97 user 3.56 sys 0.40 * src/kwset.c (struct kwset): Replace member `mind2' to `shift'. (kwsprep): Looking for the delta2 shift. (bmexec): Use it. --- src/kwset.c | 214 ++++++++++++++++++++++++++++++++++++------------------------ 1 file changed, 127 insertions(+), 87 deletions(-) diff --git a/src/kwset.c b/src/kwset.c index 410e046..e0bf6b2 100644 --- a/src/kwset.c +++ b/src/kwset.c @@ -83,7 +83,7 @@ struct kwset unsigned char delta[NCHAR]; /* Delta table for rapid search. */ struct trie *next[NCHAR]; /* Table of children of the root. */ char *target; /* Target string if there's only one. */ - int mind2; /* Used in Boyer-Moore search for one string. */ + int *shift; /* Used in Boyer-Moore search for one string. */ char const *trans; /* Character translation table. */ }; @@ -397,12 +397,70 @@ kwsprep (kwset_t kws) node at which an outgoing edge is labeled by that character. */ memset(delta, kwset->mind < UCHAR_MAX ? kwset->mind : UCHAR_MAX, NCHAR); + struct trie *fail; + struct trie *last, *next[NCHAR]; + + /* Traverse the nodes of the trie in level order, simultaneously + computing the delta table, failure function, and shift function. */ + for (curr = last = kwset->trie; curr; curr = curr->next) + { + /* Enqueue the immediate descendants in the level order queue. */ + enqueue(curr->links, &last); + + curr->shift = kwset->mind; + curr->maxshift = kwset->mind; + + /* Update the delta table for the descendants of this node. */ + treedelta(curr->links, curr->depth, delta); + + /* Compute the failure function for the descendants of this node. */ + treefails(curr->links, curr->fail, kwset->trie); + + /* Update the shifts at each node in the current node's chain + of fails back to the root. */ + for (fail = curr->fail; fail; fail = fail->fail) + { + /* If the current node has some outgoing edge that the fail + doesn't, then the shift at the fail should be no larger + than the difference of their depths. */ + if (!hasevery(fail->links, curr->links)) + if (curr->depth - fail->depth < fail->shift) + fail->shift = curr->depth - fail->depth; + + /* If the current node is accepting then the shift at the + fail and its descendants should be no larger than the + difference of their depths. */ + if (curr->accepting && fail->maxshift > curr->depth - fail->depth) + fail->maxshift = curr->depth - fail->depth; + } + } + + /* Traverse the trie in level order again, fixing up all nodes whose + shift exceeds their inherited maxshift. */ + for (curr = kwset->trie->next; curr; curr = curr->next) + { + if (curr->maxshift > curr->parent->maxshift) + curr->maxshift = curr->parent->maxshift; + if (curr->shift > curr->maxshift) + curr->shift = curr->maxshift; + } + + /* Create a vector, indexed by character code, of the outgoing links + from the root node. */ + for (i = 0; i < NCHAR; ++i) + next[i] = NULL; + treenext(kwset->trie->links, next); + + if ((trans = kwset->trans) != NULL) + for (i = 0; i < NCHAR; ++i) + kwset->next[i] = next[U(trans[i])]; + else + memcpy(kwset->next, next, NCHAR * sizeof(struct trie *)); + /* Check if we can use the simple boyer-moore algorithm, instead of the hairy commentz-walter algorithm. */ if (kwset->words == 1 && kwset->trans == NULL) { - char c; - /* Looking for just one string. Extract it from the trie. */ kwset->target = obstack_alloc(&kwset->obstack, kwset->mind); if (!kwset->target) @@ -410,80 +468,22 @@ kwsprep (kwset_t kws) for (i = kwset->mind - 1, curr = kwset->trie; i >= 0; --i) { kwset->target[i] = curr->links->label; - curr = curr->links->trie; + curr = curr->next; } - /* Build the Boyer Moore delta. Boy that's easy compared to CW. */ - for (i = 0; i < kwset->mind; ++i) - delta[U(kwset->target[i])] = kwset->mind - (i + 1); - /* Find the minimal delta2 shift that we might make after - a backwards match has failed. */ - c = kwset->target[kwset->mind - 1]; - for (i = kwset->mind - 2; i >= 0; --i) - if (kwset->target[i] == c) - break; - kwset->mind2 = kwset->mind - (i + 1); - } - else - { - struct trie *fail; - struct trie *last, *next[NCHAR]; - - /* Traverse the nodes of the trie in level order, simultaneously - computing the delta table, failure function, and shift function. */ - for (curr = last = kwset->trie; curr; curr = curr->next) + /* Looking for the delta2 shift that we might make after a + backwards match has failed. Extract it from the trie. */ + if (kwset->mind > 1) { - /* Enqueue the immediate descendants in the level order queue. */ - enqueue(curr->links, &last); - - curr->shift = kwset->mind; - curr->maxshift = kwset->mind; - - /* Update the delta table for the descendants of this node. */ - treedelta(curr->links, curr->depth, delta); - - /* Compute the failure function for the descendants of this node. */ - treefails(curr->links, curr->fail, kwset->trie); - - /* Update the shifts at each node in the current node's chain - of fails back to the root. */ - for (fail = curr->fail; fail; fail = fail->fail) + kwset->shift = obstack_alloc(&kwset->obstack, + sizeof (*kwset->shift) * (kwset->mind - 1)); + if (!kwset->shift) + return _("memory exhausted"); + for (i = 0, curr = kwset->trie->next; i < kwset->mind - 1; ++i) { - /* If the current node has some outgoing edge that the fail - doesn't, then the shift at the fail should be no larger - than the difference of their depths. */ - if (!hasevery(fail->links, curr->links)) - if (curr->depth - fail->depth < fail->shift) - fail->shift = curr->depth - fail->depth; - - /* If the current node is accepting then the shift at the - fail and its descendants should be no larger than the - difference of their depths. */ - if (curr->accepting && fail->maxshift > curr->depth - fail->depth) - fail->maxshift = curr->depth - fail->depth; + kwset->shift[i] = curr->shift; + curr = curr->next; } } - - /* Traverse the trie in level order again, fixing up all nodes whose - shift exceeds their inherited maxshift. */ - for (curr = kwset->trie->next; curr; curr = curr->next) - { - if (curr->maxshift > curr->parent->maxshift) - curr->maxshift = curr->parent->maxshift; - if (curr->shift > curr->maxshift) - curr->shift = curr->maxshift; - } - - /* Create a vector, indexed by character code, of the outgoing links - from the root node. */ - for (i = 0; i < NCHAR; ++i) - next[i] = NULL; - treenext(kwset->trie->links, next); - - if ((trans = kwset->trans) != NULL) - for (i = 0; i < NCHAR; ++i) - kwset->next[i] = next[U(trans[i])]; - else - memcpy(kwset->next, next, NCHAR * sizeof(struct trie *)); } /* Fix things up for any translation table. */ @@ -503,7 +503,8 @@ bmexec (kwset_t kws, char const *text, size_t size) struct kwset const *kwset; unsigned char const *d1; char const *ep, *sp, *tp; - int d, gc, i, len, md2; + int d, i, len, skip; + char gc1, gc2; kwset = (struct kwset const *) kws; len = kwset->mind; @@ -520,9 +521,10 @@ bmexec (kwset_t kws, char const *text, size_t size) d1 = kwset->delta; sp = kwset->target + len; - gc = U(sp[-2]); - md2 = kwset->mind2; + gc1 = sp[-1]; + gc2 = sp[-2]; tp = text + len; + skip = 0; /* Significance of 12: 1 (initial offset) + 10 (skip loop) + 1 (md2). */ if (size > 12 * len) @@ -550,14 +552,33 @@ bmexec (kwset_t kws, char const *text, size_t size) } break; found: - if (U(tp[-2]) == gc) + d = len; + while (1) { - for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]); ++i) - ; - if (i > len) - return tp - len - text; + if (tp[-2] == gc2) + { + for (i = 3; i <= d && tp[-i] == sp[-i]; ++i) + ; + if (i > d) + { + for (i = d + skip + 1; i <= len && tp[-i] == sp[-i]; ++i) + ; + if (i > len) + return tp - len - text; + } + d = kwset->shift[i - 2]; tp += d; + if (tp > ep || tp[-1] != gc1) + break; + skip = i - 1; + } + else + { + d = kwset->shift[0]; tp += d; + if (tp > ep || tp[-1] != gc1) + break; + skip = 1; + } } - tp += md2; } /* Now we have only a few characters left to search. We @@ -569,14 +590,33 @@ bmexec (kwset_t kws, char const *text, size_t size) d = d1[U((tp += d)[-1])]; if (d != 0) continue; - if (U(tp[-2]) == gc) + d = len; + while (1) { - for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]); ++i) - ; - if (i > len) - return tp - len - text; + if (tp[-2] == gc2) + { + for (i = 3; i <= d && tp[-i] == sp[-i]; ++i) + ; + if (i > d) + { + for (i = d + skip + 1; i <= len && tp[-i] == sp[-i]; ++i) + ; + if (i > len) + return tp - len - text; + } + d = kwset->shift[i - 2]; tp += d; + if (tp > ep || tp[-1] != gc1) + break; + skip = i - 1; + } + else + { + d = kwset->shift[0]; tp += d; + if (tp > ep || tp[-1] != gc1) + break; + skip = 1; + } } - d = md2; } return -1; -- 1.9.0 --------_5323EC49000000006C58_MULTIPART_MIXED_-- From unknown Tue Aug 12 08:32:41 2025 X-Loop: help-debbugs@gnu.org Subject: bug#17013: [PATCH] grep: optimization by using the Galil rule for Boyer-Moore algorithm in KWSet Resent-From: Jim Meyering Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Sat, 15 Mar 2014 17:14:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 17013 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: Norihiro Tanaka Cc: 17013@debbugs.gnu.org Received: via spool by 17013-submit@debbugs.gnu.org id=B17013.139490360211390 (code B ref 17013); Sat, 15 Mar 2014 17:14:02 +0000 Received: (at 17013) by debbugs.gnu.org; 15 Mar 2014 17:13:22 +0000 Received: from localhost ([127.0.0.1]:37636 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WOs9B-0002xd-DW for submit@debbugs.gnu.org; Sat, 15 Mar 2014 13:13:21 -0400 Received: from mail-pa0-f42.google.com ([209.85.220.42]:50973) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WOs97-0002xT-VG for 17013@debbugs.gnu.org; Sat, 15 Mar 2014 13:13:18 -0400 Received: by mail-pa0-f42.google.com with SMTP id fb1so3989920pad.29 for <17013@debbugs.gnu.org>; Sat, 15 Mar 2014 10:13:17 -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:cc:content-type; bh=z/jQCN1idwZkFI1DrJ6GnkH16AibVTqG7i1Kwpl5GzI=; b=h0tTF/n6WyRDoWKQMOamMUGSaN/Ga+2YcAdaM+JtBv2IMVXJKkXo3cFYiuPuV6SwsY Kvr+sXx0a7KgWXok+zEigqXuccWP+L3yFyLtq3v8y0WgfSU6WBthlZD1WlaOzfYf+4YF 3GabFk3n1JqPTN4nBc1GEUFyTmwoQxguQXRiAqqCSppT0hqjeLiQrtnE9U6wxvBp3LKA iP3MXRcxP4t3wDmhSxQoy7PYfiyBnDy3bxpygxuwISzpuv4/bHeZM2Qxz1CT7+ZCtxzG 95y16+tR5Bj3pmj69b7GBFjjQmGgC+jVFJ+o71SulJ204pSLWg48D2zKF88q+Ae+k/BB +ICA== X-Received: by 10.66.164.135 with SMTP id yq7mr16127749pab.126.1394903596831; Sat, 15 Mar 2014 10:13:16 -0700 (PDT) MIME-Version: 1.0 Received: by 10.68.201.231 with HTTP; Sat, 15 Mar 2014 10:12:56 -0700 (PDT) In-Reply-To: <20140315150609.6C6D.27F6AC2D@kcn.ne.jp> References: <20140314212120.7E5E.27F6AC2D@kcn.ne.jp> <20140315150609.6C6D.27F6AC2D@kcn.ne.jp> From: Jim Meyering Date: Sat, 15 Mar 2014 10:12:56 -0700 X-Google-Sender-Auth: 0Tmh_XJ02eZ0F0uTKkb0ALQ95hY Message-ID: Content-Type: text/plain; charset=ISO-8859-1 X-Spam-Score: -0.7 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 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 Fri, Mar 14, 2014 at 11:06 PM, Norihiro Tanaka wrote: > I changed the patch so that the delta2 shift is extracted from the trie, > because it's very excellent. Very nice. I've begun to review these patches, and really like the improved performance. Your first version (decreasing worst-case O(M*N) to O(M+N)) gives 30x speed-up in some cases. The delta2-from-trie change brings it closer to 40x. From unknown Tue Aug 12 08:32:41 2025 X-Loop: help-debbugs@gnu.org Subject: bug#17013: [PATCH] grep: optimization by using the Galil rule for Boyer-Moore algorithm in KWSet Resent-From: Paolo Bonzini Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Tue, 01 Apr 2014 09:08:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 17013 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: Jim Meyering , Norihiro Tanaka Cc: 17013@debbugs.gnu.org Received: via spool by 17013-submit@debbugs.gnu.org id=B17013.139634324718810 (code B ref 17013); Tue, 01 Apr 2014 09:08:01 +0000 Received: (at 17013) by debbugs.gnu.org; 1 Apr 2014 09:07:27 +0000 Received: from localhost ([127.0.0.1]:58775 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WUufG-0004tK-F0 for submit@debbugs.gnu.org; Tue, 01 Apr 2014 05:07:26 -0400 Received: from mail-we0-f177.google.com ([74.125.82.177]:47042) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WUufE-0004tB-Do for 17013@debbugs.gnu.org; Tue, 01 Apr 2014 05:07:24 -0400 Received: by mail-we0-f177.google.com with SMTP id u57so5823426wes.22 for <17013@debbugs.gnu.org>; Tue, 01 Apr 2014 02:07:23 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=sender:message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:content-type:content-transfer-encoding; bh=897yBkJJrtnvYMhd5wUrZrjzGLONP9XesZB4+yag0yo=; b=bKruPP9zNqoJwIHSUHnoay9gE9APLNMxj7fYvaXaK1+HlCe2s0XZcSOMitWjRX22Dp c9ayDBeEtu7NdKrEyr/nIR3Zpr0RrDRrHHGydbe1HM4uJOKYkEAZHv/MzkSeltj2EngF TV5S6lm4H0MQySwjV5XBg2t2ItEtwc34gXAbFZ/G8QqFQfr2TeeYQ4us8ixenNYveGYO U32LEBhmylexw5UswL7ledzdM/Vrh0X32AO8HDGSp922c6PtDZ5MYiEHESa1JdJPG0ER kQna2HEG7r68QzNuvBC0h1ihgHV/T0top0m12hm7nRHd4X29h7ZOhdqZ8PE1N3ohCIzc 650w== X-Received: by 10.194.204.199 with SMTP id la7mr20962797wjc.4.1396343243553; Tue, 01 Apr 2014 02:07:23 -0700 (PDT) Received: from yakj.usersys.redhat.com (net-37-117-156-129.cust.vodafonedsl.it. [37.117.156.129]) by mx.google.com with ESMTPSA id 48sm39141707eee.2.2014.04.01.02.07.18 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Tue, 01 Apr 2014 02:07:22 -0700 (PDT) Message-ID: <533A81BD.9050409@gnu.org> Date: Tue, 01 Apr 2014 11:07:09 +0200 From: Paolo Bonzini User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.4.0 MIME-Version: 1.0 References: <20140314212120.7E5E.27F6AC2D@kcn.ne.jp> <20140315150609.6C6D.27F6AC2D@kcn.ne.jp> In-Reply-To: X-Enigmail-Version: 1.6 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -0.7 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 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 (/) Il 15/03/2014 18:12, Jim Meyering ha scritto: > On Fri, Mar 14, 2014 at 11:06 PM, Norihiro Tanaka wrote: >> I changed the patch so that the delta2 shift is extracted from the trie, >> because it's very excellent. > > Very nice. > I've begun to review these patches, and really like the > improved performance. Your first version (decreasing > worst-case O(M*N) to O(M+N)) gives 30x speed-up in > some cases. The delta2-from-trie change brings it > closer to 40x. Thanks Jim, I'll leave the review to you then! Paolo From unknown Tue Aug 12 08:32:41 2025 X-Loop: help-debbugs@gnu.org Subject: bug#17013: [PATCH] grep: optimization by using the Galil rule for Boyer-Moore algorithm in KWSet Resent-From: Norihiro Tanaka Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Wed, 02 Apr 2014 23:46:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 17013 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: 17013@debbugs.gnu.org Received: via spool by 17013-submit@debbugs.gnu.org id=B17013.139648234913845 (code B ref 17013); Wed, 02 Apr 2014 23:46:01 +0000 Received: (at 17013) by debbugs.gnu.org; 2 Apr 2014 23:45:49 +0000 Received: from localhost ([127.0.0.1]:33466 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WVUql-0003b7-P1 for submit@debbugs.gnu.org; Wed, 02 Apr 2014 19:45:48 -0400 Received: from pbsg501.nifty.com ([202.248.238.71]:24372) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WVUqf-0003ar-4t for 17013@debbugs.gnu.org; Wed, 02 Apr 2014 19:45:40 -0400 Received: from [10.120.1.7] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) (authenticated) by pbsg501.nifty.com with ESMTP id s32NjMT2024616 for <17013@debbugs.gnu.org>; Thu, 3 Apr 2014 08:45:22 +0900 X-Nifty-SrcIP: [118.21.128.66] Date: Thu, 03 Apr 2014 08:45:22 +0900 From: Norihiro Tanaka In-Reply-To: <20140315150609.6C6D.27F6AC2D@kcn.ne.jp> References: <20140314212120.7E5E.27F6AC2D@kcn.ne.jp> <20140315150609.6C6D.27F6AC2D@kcn.ne.jp> Message-Id: <20140403084521.6667.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_533CA08A000000006667_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-Spam-Score: -0.6 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 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.6 (/) --------_533CA08A000000006667_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit In second patch, I changed so that Boyer-Moore algorithm could be used also to case-insensitive matching if MB_CUR_MAX == 1. It works with patch#17019 and patch#17034. --------_533CA08A000000006667_MULTIPART_MIXED_ Content-Type: text/plain; charset="UTF-8" Content-Disposition: attachment; filename="patch.txt" Content-Transfer-Encoding: base64 RnJvbSAyNWY3MjIzOGNkZGE0ZjMzNzJhYWE5MTgxMDc1Zjk3NTgzMmVmNTBmIE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBOb3JpaGlybyBUYW5ha2EgPG5vcml0bmtAa2NuLm5lLmpwPgpE YXRlOiBTYXQsIDE1IE1hciAyMDE0IDE0OjQxOjUyICswOTAwClN1YmplY3Q6IFtQQVRDSCAxLzJd IGdyZXA6IG9wdGltaXphdGlvbiBieSB1c2luZyB0aGUgR2FsaWwgcnVsZSBmb3IKIEJveWVyLU1v b3JlIGFsZ29yaXRobSBpbiBLV1NldAoKVGhlIEJveWVyLU1vb3JlIGFsZ29yaXRobSBydW5zIGlu IE8obSBuKSBpbiB0aGUgd29yc3QgY2FzZSwgd2hpY2gKcGVyaGFwcyBpdCBtYXkgYmUgbXVjaCBz bG93ZXIgdGhhbiB0aGUgREZBLgoKVGhlIEdhbGlsIHJ1bGUgZW5hYmxlcyB0byBjaGFuZ2UgTyht IG4pIGludG8gTyhuKSBmb3IgaXRzIGNhc2Ugd2l0aG91dApvdmVyaGVhZHMgYW5kL29yIHNsb3ct ZG93biBmb3Igb3RoZXIgY2FzZXMgYnkgYXZvaWRpbmcgdG8gY29tcGFyZSBtb3JlCnRoYW4gb25j ZSBmb3IgYSBwb3NpdGlvbiBpbiB0aGUgdGV4dC4KClRvIHVzZSB0aGUgR2FsaWwgcnVsZSwgbG9v a2luZyBmb3IgdGhlIGRlbHRhMiBzaGlmdCBhdCBlYWNoIHBvc2l0aW9uCmZyb20gdGhlIHRyaWUg aW5zdGVhZCBvZiBgbWluZDInIHZhbHVlLgoKSSBwcmVwYXJlIGZvbGxvd2luZyBzdHJpbmcsIHdo aWNoIG1ha2VzIGEgd29yc3QgY2FzZSBmb3IgQm95ZXItTW9vcmUKYWxnb3JpdGhtLCB0byBtZWFz dXJlIHRoZSBwZXJmb3JtYW5jZS4KCiAgICB5ZXMgampqampqampqampqampqampqampqampqampq ampqampqampqampqaiB8IGhlYWQgLTEwMDAwMDAwID4gawoKSSBydW4gdGhlIHRlc3Qgd2l0aCB0 aGUgcGF0Y2ggKGJlc3Qtb2YtNSB0cmlhbHMpOgoKICAgIGVudiBMQ19BTEw9QyB0aW1lIC1wIHNy Yy9ncmVwIGtqampqampqampqampqampqampqIGsKICAgICAgICByZWFsIDAuNzAgICAgICAgdXNl ciAwLjMyICAgICAgIHN5cyAwLjM4CgpCYWNrIG91dCB0aGF0IGNvbW1pdCAodGVtcG9yYXJpbHkp LCByZWNvbXBpbGUsIGFuZCByZXJ1biB0aGUgZXhwZXJpbWVudDoKCiAgICBlbnYgTENfQUxMPUMg dGltZSAtcCBzcmMvZ3JlcCBrampqampqampqampqampqampqaiBrCiAgICAgICAgcmVhbCAzLjk3 ICAgICAgIHVzZXIgMy41NiAgICAgICBzeXMgMC40MAoKKiBzcmMva3dzZXQuYyAoc3RydWN0IGt3 c2V0KTogUmVwbGFjZSBtZW1iZXIgYG1pbmQyJyB0byBgc2hpZnQnLgooa3dzcHJlcCk6IExvb2tp bmcgZm9yIHRoZSBkZWx0YTIgc2hpZnQuCihibWV4ZWMpOiBVc2UgaXQuCi0tLQogc3JjL2t3c2V0 LmMgfCAyMTQgKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tCiAxIGZpbGUgY2hhbmdlZCwgMTI3IGluc2VydGlvbnMoKyksIDg3IGRlbGV0 aW9ucygtKQoKZGlmZiAtLWdpdCBhL3NyYy9rd3NldC5jIGIvc3JjL2t3c2V0LmMKaW5kZXggNDEw ZTA0Ni4uZTBiZjZiMiAxMDA2NDQKLS0tIGEvc3JjL2t3c2V0LmMKKysrIGIvc3JjL2t3c2V0LmMK QEAgLTgzLDcgKzgzLDcgQEAgc3RydWN0IGt3c2V0CiAgIHVuc2lnbmVkIGNoYXIgZGVsdGFbTkNI QVJdOwkvKiBEZWx0YSB0YWJsZSBmb3IgcmFwaWQgc2VhcmNoLiAqLwogICBzdHJ1Y3QgdHJpZSAq bmV4dFtOQ0hBUl07CS8qIFRhYmxlIG9mIGNoaWxkcmVuIG9mIHRoZSByb290LiAqLwogICBjaGFy ICp0YXJnZXQ7CQkJLyogVGFyZ2V0IHN0cmluZyBpZiB0aGVyZSdzIG9ubHkgb25lLiAqLwotICBp bnQgbWluZDI7CQkJLyogVXNlZCBpbiBCb3llci1Nb29yZSBzZWFyY2ggZm9yIG9uZSBzdHJpbmcu ICovCisgIGludCAqc2hpZnQ7CQkJLyogVXNlZCBpbiBCb3llci1Nb29yZSBzZWFyY2ggZm9yIG9u ZSBzdHJpbmcuICovCiAgIGNoYXIgY29uc3QgKnRyYW5zOwkJLyogQ2hhcmFjdGVyIHRyYW5zbGF0 aW9uIHRhYmxlLiAqLwogfTsKIApAQCAtMzk3LDEyICszOTcsNzAgQEAga3dzcHJlcCAoa3dzZXRf dCBrd3MpCiAgICAgIG5vZGUgYXQgd2hpY2ggYW4gb3V0Z29pbmcgZWRnZSBpcyBsYWJlbGVkIGJ5 IHRoYXQgY2hhcmFjdGVyLiAqLwogICBtZW1zZXQoZGVsdGEsIGt3c2V0LT5taW5kIDwgVUNIQVJf TUFYID8ga3dzZXQtPm1pbmQgOiBVQ0hBUl9NQVgsIE5DSEFSKTsKIAorICBzdHJ1Y3QgdHJpZSAq ZmFpbDsKKyAgc3RydWN0IHRyaWUgKmxhc3QsICpuZXh0W05DSEFSXTsKKworICAvKiBUcmF2ZXJz ZSB0aGUgbm9kZXMgb2YgdGhlIHRyaWUgaW4gbGV2ZWwgb3JkZXIsIHNpbXVsdGFuZW91c2x5Cisg ICAgIGNvbXB1dGluZyB0aGUgZGVsdGEgdGFibGUsIGZhaWx1cmUgZnVuY3Rpb24sIGFuZCBzaGlm dCBmdW5jdGlvbi4gKi8KKyAgZm9yIChjdXJyID0gbGFzdCA9IGt3c2V0LT50cmllOyBjdXJyOyBj dXJyID0gY3Vyci0+bmV4dCkKKyAgICB7CisgICAgICAvKiBFbnF1ZXVlIHRoZSBpbW1lZGlhdGUg ZGVzY2VuZGFudHMgaW4gdGhlIGxldmVsIG9yZGVyIHF1ZXVlLiAqLworICAgICAgZW5xdWV1ZShj dXJyLT5saW5rcywgJmxhc3QpOworCisgICAgICBjdXJyLT5zaGlmdCA9IGt3c2V0LT5taW5kOwor ICAgICAgY3Vyci0+bWF4c2hpZnQgPSBrd3NldC0+bWluZDsKKworICAgICAgLyogVXBkYXRlIHRo ZSBkZWx0YSB0YWJsZSBmb3IgdGhlIGRlc2NlbmRhbnRzIG9mIHRoaXMgbm9kZS4gKi8KKyAgICAg IHRyZWVkZWx0YShjdXJyLT5saW5rcywgY3Vyci0+ZGVwdGgsIGRlbHRhKTsKKworICAgICAgLyog Q29tcHV0ZSB0aGUgZmFpbHVyZSBmdW5jdGlvbiBmb3IgdGhlIGRlc2NlbmRhbnRzIG9mIHRoaXMg bm9kZS4gICovCisgICAgICB0cmVlZmFpbHMoY3Vyci0+bGlua3MsIGN1cnItPmZhaWwsIGt3c2V0 LT50cmllKTsKKworICAgICAgLyogVXBkYXRlIHRoZSBzaGlmdHMgYXQgZWFjaCBub2RlIGluIHRo ZSBjdXJyZW50IG5vZGUncyBjaGFpbgorICAgICAgICAgb2YgZmFpbHMgYmFjayB0byB0aGUgcm9v dC4gKi8KKyAgICAgIGZvciAoZmFpbCA9IGN1cnItPmZhaWw7IGZhaWw7IGZhaWwgPSBmYWlsLT5m YWlsKQorICAgICAgICB7CisgICAgICAgICAgLyogSWYgdGhlIGN1cnJlbnQgbm9kZSBoYXMgc29t ZSBvdXRnb2luZyBlZGdlIHRoYXQgdGhlIGZhaWwKKyAgICAgICAgICAgICBkb2Vzbid0LCB0aGVu IHRoZSBzaGlmdCBhdCB0aGUgZmFpbCBzaG91bGQgYmUgbm8gbGFyZ2VyCisgICAgICAgICAgICAg dGhhbiB0aGUgZGlmZmVyZW5jZSBvZiB0aGVpciBkZXB0aHMuICovCisgICAgICAgICAgaWYgKCFo YXNldmVyeShmYWlsLT5saW5rcywgY3Vyci0+bGlua3MpKQorICAgICAgICAgICAgaWYgKGN1cnIt PmRlcHRoIC0gZmFpbC0+ZGVwdGggPCBmYWlsLT5zaGlmdCkKKyAgICAgICAgICAgICAgZmFpbC0+ c2hpZnQgPSBjdXJyLT5kZXB0aCAtIGZhaWwtPmRlcHRoOworCisgICAgICAgICAgLyogSWYgdGhl IGN1cnJlbnQgbm9kZSBpcyBhY2NlcHRpbmcgdGhlbiB0aGUgc2hpZnQgYXQgdGhlCisgICAgICAg ICAgICAgZmFpbCBhbmQgaXRzIGRlc2NlbmRhbnRzIHNob3VsZCBiZSBubyBsYXJnZXIgdGhhbiB0 aGUKKyAgICAgICAgICAgICBkaWZmZXJlbmNlIG9mIHRoZWlyIGRlcHRocy4gKi8KKyAgICAgICAg ICBpZiAoY3Vyci0+YWNjZXB0aW5nICYmIGZhaWwtPm1heHNoaWZ0ID4gY3Vyci0+ZGVwdGggLSBm YWlsLT5kZXB0aCkKKyAgICAgICAgICAgIGZhaWwtPm1heHNoaWZ0ID0gY3Vyci0+ZGVwdGggLSBm YWlsLT5kZXB0aDsKKyAgICAgICAgfQorICAgIH0KKworICAvKiBUcmF2ZXJzZSB0aGUgdHJpZSBp biBsZXZlbCBvcmRlciBhZ2FpbiwgZml4aW5nIHVwIGFsbCBub2RlcyB3aG9zZQorICAgICBzaGlm dCBleGNlZWRzIHRoZWlyIGluaGVyaXRlZCBtYXhzaGlmdC4gKi8KKyAgZm9yIChjdXJyID0ga3dz ZXQtPnRyaWUtPm5leHQ7IGN1cnI7IGN1cnIgPSBjdXJyLT5uZXh0KQorICAgIHsKKyAgICAgIGlm IChjdXJyLT5tYXhzaGlmdCA+IGN1cnItPnBhcmVudC0+bWF4c2hpZnQpCisgICAgICAgIGN1cnIt Pm1heHNoaWZ0ID0gY3Vyci0+cGFyZW50LT5tYXhzaGlmdDsKKyAgICAgIGlmIChjdXJyLT5zaGlm dCA+IGN1cnItPm1heHNoaWZ0KQorICAgICAgICBjdXJyLT5zaGlmdCA9IGN1cnItPm1heHNoaWZ0 OworICAgIH0KKworICAvKiBDcmVhdGUgYSB2ZWN0b3IsIGluZGV4ZWQgYnkgY2hhcmFjdGVyIGNv ZGUsIG9mIHRoZSBvdXRnb2luZyBsaW5rcworICAgICBmcm9tIHRoZSByb290IG5vZGUuICovCisg IGZvciAoaSA9IDA7IGkgPCBOQ0hBUjsgKytpKQorICAgIG5leHRbaV0gPSBOVUxMOworICB0cmVl bmV4dChrd3NldC0+dHJpZS0+bGlua3MsIG5leHQpOworCisgIGlmICgodHJhbnMgPSBrd3NldC0+ dHJhbnMpICE9IE5VTEwpCisgICAgZm9yIChpID0gMDsgaSA8IE5DSEFSOyArK2kpCisgICAgICBr d3NldC0+bmV4dFtpXSA9IG5leHRbVSh0cmFuc1tpXSldOworICBlbHNlCisgICAgbWVtY3B5KGt3 c2V0LT5uZXh0LCBuZXh0LCBOQ0hBUiAqIHNpemVvZihzdHJ1Y3QgdHJpZSAqKSk7CisKICAgLyog Q2hlY2sgaWYgd2UgY2FuIHVzZSB0aGUgc2ltcGxlIGJveWVyLW1vb3JlIGFsZ29yaXRobSwgaW5z dGVhZAogICAgICBvZiB0aGUgaGFpcnkgY29tbWVudHotd2FsdGVyIGFsZ29yaXRobS4gKi8KICAg aWYgKGt3c2V0LT53b3JkcyA9PSAxICYmIGt3c2V0LT50cmFucyA9PSBOVUxMKQogICAgIHsKLSAg ICAgIGNoYXIgYzsKLQogICAgICAgLyogTG9va2luZyBmb3IganVzdCBvbmUgc3RyaW5nLiAgRXh0 cmFjdCBpdCBmcm9tIHRoZSB0cmllLiAqLwogICAgICAga3dzZXQtPnRhcmdldCA9IG9ic3RhY2tf YWxsb2MoJmt3c2V0LT5vYnN0YWNrLCBrd3NldC0+bWluZCk7CiAgICAgICBpZiAoIWt3c2V0LT50 YXJnZXQpCkBAIC00MTAsODAgKzQ2OCwyMiBAQCBrd3NwcmVwIChrd3NldF90IGt3cykKICAgICAg IGZvciAoaSA9IGt3c2V0LT5taW5kIC0gMSwgY3VyciA9IGt3c2V0LT50cmllOyBpID49IDA7IC0t aSkKICAgICAgICAgewogICAgICAgICAgIGt3c2V0LT50YXJnZXRbaV0gPSBjdXJyLT5saW5rcy0+ bGFiZWw7Ci0gICAgICAgICAgY3VyciA9IGN1cnItPmxpbmtzLT50cmllOworICAgICAgICAgIGN1 cnIgPSBjdXJyLT5uZXh0OwogICAgICAgICB9Ci0gICAgICAvKiBCdWlsZCB0aGUgQm95ZXIgTW9v cmUgZGVsdGEuICBCb3kgdGhhdCdzIGVhc3kgY29tcGFyZWQgdG8gQ1cuICovCi0gICAgICBmb3Ig KGkgPSAwOyBpIDwga3dzZXQtPm1pbmQ7ICsraSkKLSAgICAgICAgZGVsdGFbVShrd3NldC0+dGFy Z2V0W2ldKV0gPSBrd3NldC0+bWluZCAtIChpICsgMSk7Ci0gICAgICAvKiBGaW5kIHRoZSBtaW5p bWFsIGRlbHRhMiBzaGlmdCB0aGF0IHdlIG1pZ2h0IG1ha2UgYWZ0ZXIKLSAgICAgICAgIGEgYmFj a3dhcmRzIG1hdGNoIGhhcyBmYWlsZWQuICovCi0gICAgICBjID0ga3dzZXQtPnRhcmdldFtrd3Nl dC0+bWluZCAtIDFdOwotICAgICAgZm9yIChpID0ga3dzZXQtPm1pbmQgLSAyOyBpID49IDA7IC0t aSkKLSAgICAgICAgaWYgKGt3c2V0LT50YXJnZXRbaV0gPT0gYykKLSAgICAgICAgICBicmVhazsK LSAgICAgIGt3c2V0LT5taW5kMiA9IGt3c2V0LT5taW5kIC0gKGkgKyAxKTsKLSAgICB9Ci0gIGVs c2UKLSAgICB7Ci0gICAgICBzdHJ1Y3QgdHJpZSAqZmFpbDsKLSAgICAgIHN0cnVjdCB0cmllICps YXN0LCAqbmV4dFtOQ0hBUl07Ci0KLSAgICAgIC8qIFRyYXZlcnNlIHRoZSBub2RlcyBvZiB0aGUg dHJpZSBpbiBsZXZlbCBvcmRlciwgc2ltdWx0YW5lb3VzbHkKLSAgICAgICAgIGNvbXB1dGluZyB0 aGUgZGVsdGEgdGFibGUsIGZhaWx1cmUgZnVuY3Rpb24sIGFuZCBzaGlmdCBmdW5jdGlvbi4gKi8K LSAgICAgIGZvciAoY3VyciA9IGxhc3QgPSBrd3NldC0+dHJpZTsgY3VycjsgY3VyciA9IGN1cnIt Pm5leHQpCisgICAgICAvKiBMb29raW5nIGZvciB0aGUgZGVsdGEyIHNoaWZ0IHRoYXQgd2UgbWln aHQgbWFrZSBhZnRlciBhCisgICAgICAgICBiYWNrd2FyZHMgbWF0Y2ggaGFzIGZhaWxlZC4gIEV4 dHJhY3QgaXQgZnJvbSB0aGUgdHJpZS4gKi8KKyAgICAgIGlmIChrd3NldC0+bWluZCA+IDEpCiAg ICAgICAgIHsKLSAgICAgICAgICAvKiBFbnF1ZXVlIHRoZSBpbW1lZGlhdGUgZGVzY2VuZGFudHMg aW4gdGhlIGxldmVsIG9yZGVyIHF1ZXVlLiAqLwotICAgICAgICAgIGVucXVldWUoY3Vyci0+bGlu a3MsICZsYXN0KTsKLQotICAgICAgICAgIGN1cnItPnNoaWZ0ID0ga3dzZXQtPm1pbmQ7Ci0gICAg ICAgICAgY3Vyci0+bWF4c2hpZnQgPSBrd3NldC0+bWluZDsKLQotICAgICAgICAgIC8qIFVwZGF0 ZSB0aGUgZGVsdGEgdGFibGUgZm9yIHRoZSBkZXNjZW5kYW50cyBvZiB0aGlzIG5vZGUuICovCi0g ICAgICAgICAgdHJlZWRlbHRhKGN1cnItPmxpbmtzLCBjdXJyLT5kZXB0aCwgZGVsdGEpOwotCi0g ICAgICAgICAgLyogQ29tcHV0ZSB0aGUgZmFpbHVyZSBmdW5jdGlvbiBmb3IgdGhlIGRlc2NlbmRh bnRzIG9mIHRoaXMgbm9kZS4gICovCi0gICAgICAgICAgdHJlZWZhaWxzKGN1cnItPmxpbmtzLCBj dXJyLT5mYWlsLCBrd3NldC0+dHJpZSk7Ci0KLSAgICAgICAgICAvKiBVcGRhdGUgdGhlIHNoaWZ0 cyBhdCBlYWNoIG5vZGUgaW4gdGhlIGN1cnJlbnQgbm9kZSdzIGNoYWluCi0gICAgICAgICAgICAg b2YgZmFpbHMgYmFjayB0byB0aGUgcm9vdC4gKi8KLSAgICAgICAgICBmb3IgKGZhaWwgPSBjdXJy LT5mYWlsOyBmYWlsOyBmYWlsID0gZmFpbC0+ZmFpbCkKKyAgICAgICAgICBrd3NldC0+c2hpZnQg PSBvYnN0YWNrX2FsbG9jKCZrd3NldC0+b2JzdGFjaywKKyAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgICAgICAgIHNpemVvZiAoKmt3c2V0LT5zaGlmdCkgKiAoa3dzZXQtPm1pbmQgLSAx KSk7CisgICAgICAgICAgaWYgKCFrd3NldC0+c2hpZnQpCisgICAgICAgICAgICByZXR1cm4gXygi bWVtb3J5IGV4aGF1c3RlZCIpOworICAgICAgICAgIGZvciAoaSA9IDAsIGN1cnIgPSBrd3NldC0+ dHJpZS0+bmV4dDsgaSA8IGt3c2V0LT5taW5kIC0gMTsgKytpKQogICAgICAgICAgICAgewotICAg ICAgICAgICAgICAvKiBJZiB0aGUgY3VycmVudCBub2RlIGhhcyBzb21lIG91dGdvaW5nIGVkZ2Ug dGhhdCB0aGUgZmFpbAotICAgICAgICAgICAgICAgICBkb2Vzbid0LCB0aGVuIHRoZSBzaGlmdCBh dCB0aGUgZmFpbCBzaG91bGQgYmUgbm8gbGFyZ2VyCi0gICAgICAgICAgICAgICAgIHRoYW4gdGhl IGRpZmZlcmVuY2Ugb2YgdGhlaXIgZGVwdGhzLiAqLwotICAgICAgICAgICAgICBpZiAoIWhhc2V2 ZXJ5KGZhaWwtPmxpbmtzLCBjdXJyLT5saW5rcykpCi0gICAgICAgICAgICAgICAgaWYgKGN1cnIt PmRlcHRoIC0gZmFpbC0+ZGVwdGggPCBmYWlsLT5zaGlmdCkKLSAgICAgICAgICAgICAgICAgIGZh aWwtPnNoaWZ0ID0gY3Vyci0+ZGVwdGggLSBmYWlsLT5kZXB0aDsKLQotICAgICAgICAgICAgICAv KiBJZiB0aGUgY3VycmVudCBub2RlIGlzIGFjY2VwdGluZyB0aGVuIHRoZSBzaGlmdCBhdCB0aGUK LSAgICAgICAgICAgICAgICAgZmFpbCBhbmQgaXRzIGRlc2NlbmRhbnRzIHNob3VsZCBiZSBubyBs YXJnZXIgdGhhbiB0aGUKLSAgICAgICAgICAgICAgICAgZGlmZmVyZW5jZSBvZiB0aGVpciBkZXB0 aHMuICovCi0gICAgICAgICAgICAgIGlmIChjdXJyLT5hY2NlcHRpbmcgJiYgZmFpbC0+bWF4c2hp ZnQgPiBjdXJyLT5kZXB0aCAtIGZhaWwtPmRlcHRoKQotICAgICAgICAgICAgICAgIGZhaWwtPm1h eHNoaWZ0ID0gY3Vyci0+ZGVwdGggLSBmYWlsLT5kZXB0aDsKKyAgICAgICAgICAgICAga3dzZXQt PnNoaWZ0W2ldID0gY3Vyci0+c2hpZnQ7CisgICAgICAgICAgICAgIGN1cnIgPSBjdXJyLT5uZXh0 OwogICAgICAgICAgICAgfQogICAgICAgICB9Ci0KLSAgICAgIC8qIFRyYXZlcnNlIHRoZSB0cmll IGluIGxldmVsIG9yZGVyIGFnYWluLCBmaXhpbmcgdXAgYWxsIG5vZGVzIHdob3NlCi0gICAgICAg ICBzaGlmdCBleGNlZWRzIHRoZWlyIGluaGVyaXRlZCBtYXhzaGlmdC4gKi8KLSAgICAgIGZvciAo Y3VyciA9IGt3c2V0LT50cmllLT5uZXh0OyBjdXJyOyBjdXJyID0gY3Vyci0+bmV4dCkKLSAgICAg ICAgewotICAgICAgICAgIGlmIChjdXJyLT5tYXhzaGlmdCA+IGN1cnItPnBhcmVudC0+bWF4c2hp ZnQpCi0gICAgICAgICAgICBjdXJyLT5tYXhzaGlmdCA9IGN1cnItPnBhcmVudC0+bWF4c2hpZnQ7 Ci0gICAgICAgICAgaWYgKGN1cnItPnNoaWZ0ID4gY3Vyci0+bWF4c2hpZnQpCi0gICAgICAgICAg ICBjdXJyLT5zaGlmdCA9IGN1cnItPm1heHNoaWZ0OwotICAgICAgICB9Ci0KLSAgICAgIC8qIENy ZWF0ZSBhIHZlY3RvciwgaW5kZXhlZCBieSBjaGFyYWN0ZXIgY29kZSwgb2YgdGhlIG91dGdvaW5n IGxpbmtzCi0gICAgICAgICBmcm9tIHRoZSByb290IG5vZGUuICovCi0gICAgICBmb3IgKGkgPSAw OyBpIDwgTkNIQVI7ICsraSkKLSAgICAgICAgbmV4dFtpXSA9IE5VTEw7Ci0gICAgICB0cmVlbmV4 dChrd3NldC0+dHJpZS0+bGlua3MsIG5leHQpOwotCi0gICAgICBpZiAoKHRyYW5zID0ga3dzZXQt PnRyYW5zKSAhPSBOVUxMKQotICAgICAgICBmb3IgKGkgPSAwOyBpIDwgTkNIQVI7ICsraSkKLSAg ICAgICAgICBrd3NldC0+bmV4dFtpXSA9IG5leHRbVSh0cmFuc1tpXSldOwotICAgICAgZWxzZQot ICAgICAgICBtZW1jcHkoa3dzZXQtPm5leHQsIG5leHQsIE5DSEFSICogc2l6ZW9mKHN0cnVjdCB0 cmllICopKTsKICAgICB9CiAKICAgLyogRml4IHRoaW5ncyB1cCBmb3IgYW55IHRyYW5zbGF0aW9u IHRhYmxlLiAqLwpAQCAtNTAzLDcgKzUwMyw4IEBAIGJtZXhlYyAoa3dzZXRfdCBrd3MsIGNoYXIg Y29uc3QgKnRleHQsIHNpemVfdCBzaXplKQogICBzdHJ1Y3Qga3dzZXQgY29uc3QgKmt3c2V0Owog ICB1bnNpZ25lZCBjaGFyIGNvbnN0ICpkMTsKICAgY2hhciBjb25zdCAqZXAsICpzcCwgKnRwOwot ICBpbnQgZCwgZ2MsIGksIGxlbiwgbWQyOworICBpbnQgZCwgaSwgbGVuLCBza2lwOworICBjaGFy IGdjMSwgZ2MyOwogCiAgIGt3c2V0ID0gKHN0cnVjdCBrd3NldCBjb25zdCAqKSBrd3M7CiAgIGxl biA9IGt3c2V0LT5taW5kOwpAQCAtNTIwLDkgKzUyMSwxMCBAQCBibWV4ZWMgKGt3c2V0X3Qga3dz LCBjaGFyIGNvbnN0ICp0ZXh0LCBzaXplX3Qgc2l6ZSkKIAogICBkMSA9IGt3c2V0LT5kZWx0YTsK ICAgc3AgPSBrd3NldC0+dGFyZ2V0ICsgbGVuOwotICBnYyA9IFUoc3BbLTJdKTsKLSAgbWQyID0g a3dzZXQtPm1pbmQyOworICBnYzEgPSBzcFstMV07CisgIGdjMiA9IHNwWy0yXTsKICAgdHAgPSB0 ZXh0ICsgbGVuOworICBza2lwID0gMDsKIAogICAvKiBTaWduaWZpY2FuY2Ugb2YgMTI6IDEgKGlu aXRpYWwgb2Zmc2V0KSArIDEwIChza2lwIGxvb3ApICsgMSAobWQyKS4gKi8KICAgaWYgKHNpemUg PiAxMiAqIGxlbikKQEAgLTU1MCwxNCArNTUyLDMzIEBAIGJtZXhlYyAoa3dzZXRfdCBrd3MsIGNo YXIgY29uc3QgKnRleHQsIHNpemVfdCBzaXplKQogICAgICAgICAgIH0KICAgICAgICAgYnJlYWs7 CiAgICAgICBmb3VuZDoKLSAgICAgICAgaWYgKFUodHBbLTJdKSA9PSBnYykKKyAgICAgICAgZCA9 IGxlbjsKKyAgICAgICAgd2hpbGUgKDEpCiAgICAgICAgICAgewotICAgICAgICAgICAgZm9yIChp ID0gMzsgaSA8PSBsZW4gJiYgVSh0cFstaV0pID09IFUoc3BbLWldKTsgKytpKQotICAgICAgICAg ICAgICA7Ci0gICAgICAgICAgICBpZiAoaSA+IGxlbikKLSAgICAgICAgICAgICAgcmV0dXJuIHRw IC0gbGVuIC0gdGV4dDsKKyAgICAgICAgICAgIGlmICh0cFstMl0gPT0gZ2MyKQorICAgICAgICAg ICAgICB7CisgICAgICAgICAgICAgICAgZm9yIChpID0gMzsgaSA8PSBkICYmIHRwWy1pXSA9PSBz cFstaV07ICsraSkKKyAgICAgICAgICAgICAgICAgIDsKKyAgICAgICAgICAgICAgICBpZiAoaSA+ IGQpCisgICAgICAgICAgICAgICAgICB7CisgICAgICAgICAgICAgICAgICAgIGZvciAoaSA9IGQg KyBza2lwICsgMTsgaSA8PSBsZW4gJiYgdHBbLWldID09IHNwWy1pXTsgKytpKQorICAgICAgICAg ICAgICAgICAgICAgIDsKKyAgICAgICAgICAgICAgICAgICAgaWYgKGkgPiBsZW4pCisgICAgICAg ICAgICAgICAgICAgICAgcmV0dXJuIHRwIC0gbGVuIC0gdGV4dDsKKyAgICAgICAgICAgICAgICAg IH0KKyAgICAgICAgICAgICAgICBkID0ga3dzZXQtPnNoaWZ0W2kgLSAyXTsgdHAgKz0gZDsKKyAg ICAgICAgICAgICAgICBpZiAodHAgPiBlcCB8fCB0cFstMV0gIT0gZ2MxKQorICAgICAgICAgICAg ICAgICAgYnJlYWs7CisgICAgICAgICAgICAgICAgc2tpcCA9IGkgLSAxOworICAgICAgICAgICAg ICB9CisgICAgICAgICAgICBlbHNlCisgICAgICAgICAgICAgIHsKKyAgICAgICAgICAgICAgICBk ID0ga3dzZXQtPnNoaWZ0WzBdOyB0cCArPSBkOworICAgICAgICAgICAgICAgIGlmICh0cCA+IGVw IHx8IHRwWy0xXSAhPSBnYzEpCisgICAgICAgICAgICAgICAgICBicmVhazsKKyAgICAgICAgICAg ICAgICBza2lwID0gMTsKKyAgICAgICAgICAgICAgfQogICAgICAgICAgIH0KLSAgICAgICAgdHAg Kz0gbWQyOwogICAgICAgfQogCiAgIC8qIE5vdyB3ZSBoYXZlIG9ubHkgYSBmZXcgY2hhcmFjdGVy cyBsZWZ0IHRvIHNlYXJjaC4gIFdlCkBAIC01NjksMTQgKzU5MCwzMyBAQCBibWV4ZWMgKGt3c2V0 X3Qga3dzLCBjaGFyIGNvbnN0ICp0ZXh0LCBzaXplX3Qgc2l6ZSkKICAgICAgIGQgPSBkMVtVKCh0 cCArPSBkKVstMV0pXTsKICAgICAgIGlmIChkICE9IDApCiAgICAgICAgIGNvbnRpbnVlOwotICAg ICAgaWYgKFUodHBbLTJdKSA9PSBnYykKKyAgICAgIGQgPSBsZW47CisgICAgICB3aGlsZSAoMSkK ICAgICAgICAgewotICAgICAgICAgIGZvciAoaSA9IDM7IGkgPD0gbGVuICYmIFUodHBbLWldKSA9 PSBVKHNwWy1pXSk7ICsraSkKLSAgICAgICAgICAgIDsKLSAgICAgICAgICBpZiAoaSA+IGxlbikK LSAgICAgICAgICAgIHJldHVybiB0cCAtIGxlbiAtIHRleHQ7CisgICAgICAgICAgaWYgKHRwWy0y XSA9PSBnYzIpCisgICAgICAgICAgICB7CisgICAgICAgICAgICAgIGZvciAoaSA9IDM7IGkgPD0g ZCAmJiB0cFstaV0gPT0gc3BbLWldOyArK2kpCisgICAgICAgICAgICAgICAgOworICAgICAgICAg ICAgICBpZiAoaSA+IGQpCisgICAgICAgICAgICAgICAgeworICAgICAgICAgICAgICAgICAgZm9y IChpID0gZCArIHNraXAgKyAxOyBpIDw9IGxlbiAmJiB0cFstaV0gPT0gc3BbLWldOyArK2kpCisg ICAgICAgICAgICAgICAgICAgIDsKKyAgICAgICAgICAgICAgICAgIGlmIChpID4gbGVuKQorICAg ICAgICAgICAgICAgICAgICByZXR1cm4gdHAgLSBsZW4gLSB0ZXh0OworICAgICAgICAgICAgICAg IH0KKyAgICAgICAgICAgICAgZCA9IGt3c2V0LT5zaGlmdFtpIC0gMl07IHRwICs9IGQ7CisgICAg ICAgICAgICAgIGlmICh0cCA+IGVwIHx8IHRwWy0xXSAhPSBnYzEpCisgICAgICAgICAgICAgICAg YnJlYWs7CisgICAgICAgICAgICAgIHNraXAgPSBpIC0gMTsKKyAgICAgICAgICAgIH0KKyAgICAg ICAgICBlbHNlCisgICAgICAgICAgICB7CisgICAgICAgICAgICAgIGQgPSBrd3NldC0+c2hpZnRb MF07IHRwICs9IGQ7CisgICAgICAgICAgICAgIGlmICh0cCA+IGVwIHx8IHRwWy0xXSAhPSBnYzEp CisgICAgICAgICAgICAgICAgYnJlYWs7CisgICAgICAgICAgICAgIHNraXAgPSAxOworICAgICAg ICAgICAgfQogICAgICAgICB9Ci0gICAgICBkID0gbWQyOwogICAgIH0KIAogICByZXR1cm4gLTE7 Ci0tIAoxLjkuMQoKCkZyb20gOWJlOTFiMjI2OGQ4NjFlZTZiMTZmMjgxZWFjNjg3M2E3MjQ0ZjZm YiBNb24gU2VwIDE3IDAwOjAwOjAwIDIwMDEKRnJvbTogTm9yaWhpcm8gVGFuYWthIDxub3JpdG5r QGtjbi5uZS5qcD4KRGF0ZTogVGh1LCAyMCBNYXIgMjAxNCAwODowNzoyNSArMDkwMApTdWJqZWN0 OiBbUEFUQ0ggMi8yXSBncmVwOiBtYXkgYWxzbyB1c2UgQm95ZXItTW9vcmUgYWxnb3JpdGhtIGZv cgogY2FzZS1pbnNlbnNpdGl2ZSBtYXRjaGluZwoKKiBzcmMva3dzZXQuYyAoYm1leGVjKTogVXNl IGNoYXJhY3RlciB0cmFuc2xhdGlvbiB0YWJsZS4KKGt3c2V4ZWMpOiBDYWxsIGJtZXhlYyBmb3Ig Y2FzZS1pbnNlbnNpdGl2ZSBtYXRjaGluZy4KKGt3c3ByZXApOiBDaGFuZ2UgdGhlIGBpZicgY29u ZGl0aW9uLgotLS0KIHNyYy9rd3NldC5jIHwgMTU3ICsrKysrKysrKysrKysrKysrKysrKysrKysr KysrKysrKysrKysrKysrKysrKy0tLS0tLS0tLS0tLS0tLQogMSBmaWxlIGNoYW5nZWQsIDExOSBp bnNlcnRpb25zKCspLCAzOCBkZWxldGlvbnMoLSkKCmRpZmYgLS1naXQgYS9zcmMva3dzZXQuYyBi L3NyYy9rd3NldC5jCmluZGV4IGUwYmY2YjIuLjkyMGJjN2EgMTAwNjQ0Ci0tLSBhL3NyYy9rd3Nl dC5jCisrKyBiL3NyYy9rd3NldC5jCkBAIC00NTksNyArNDU5LDcgQEAga3dzcHJlcCAoa3dzZXRf dCBrd3MpCiAKICAgLyogQ2hlY2sgaWYgd2UgY2FuIHVzZSB0aGUgc2ltcGxlIGJveWVyLW1vb3Jl IGFsZ29yaXRobSwgaW5zdGVhZAogICAgICBvZiB0aGUgaGFpcnkgY29tbWVudHotd2FsdGVyIGFs Z29yaXRobS4gKi8KLSAgaWYgKGt3c2V0LT53b3JkcyA9PSAxICYmIGt3c2V0LT50cmFucyA9PSBO VUxMKQorICBpZiAoa3dzZXQtPndvcmRzID09IDEpCiAgICAgewogICAgICAgLyogTG9va2luZyBm b3IganVzdCBvbmUgc3RyaW5nLiAgRXh0cmFjdCBpdCBmcm9tIHRoZSB0cmllLiAqLwogICAgICAg a3dzZXQtPnRhcmdldCA9IG9ic3RhY2tfYWxsb2MoJmt3c2V0LT5vYnN0YWNrLCBrd3NldC0+bWlu ZCk7CkBAIC01MDUsOSArNTA1LDExIEBAIGJtZXhlYyAoa3dzZXRfdCBrd3MsIGNoYXIgY29uc3Qg KnRleHQsIHNpemVfdCBzaXplKQogICBjaGFyIGNvbnN0ICplcCwgKnNwLCAqdHA7CiAgIGludCBk LCBpLCBsZW4sIHNraXA7CiAgIGNoYXIgZ2MxLCBnYzI7CisgIGNoYXIgY29uc3QgKnRyYW5zOwog CiAgIGt3c2V0ID0gKHN0cnVjdCBrd3NldCBjb25zdCAqKSBrd3M7CiAgIGxlbiA9IGt3c2V0LT5t aW5kOworICB0cmFucyA9IGt3c2V0LT50cmFuczsKIAogICBpZiAobGVuID09IDApCiAgICAgcmV0 dXJuIDA7CkBAIC01MTUsMTUgKzUxNywzMCBAQCBibWV4ZWMgKGt3c2V0X3Qga3dzLCBjaGFyIGNv bnN0ICp0ZXh0LCBzaXplX3Qgc2l6ZSkKICAgICByZXR1cm4gLTE7CiAgIGlmIChsZW4gPT0gMSkK ICAgICB7CisgICAgICBpZiAodHJhbnMpCisgICAgICAgIHsKKyAgICAgICAgICBmb3IgKHRwID0g dGV4dDsgdHAgPCB0ZXh0ICsgc2l6ZTsgdHArKykKKyAgICAgICAgICAgIGlmICh0cmFuc1tVKCp0 cCldID09IGt3c2V0LT50YXJnZXRbMF0pCisgICAgICAgICAgICAgIGJyZWFrOworICAgICAgICAg IHJldHVybiB0cCA8IHRleHQgKyBzaXplID8gdHAgLSB0ZXh0IDogLTE7CisgICAgICAgIH0KICAg ICAgIHRwID0gbWVtY2hyICh0ZXh0LCBrd3NldC0+dGFyZ2V0WzBdLCBzaXplKTsKICAgICAgIHJl dHVybiB0cCA/IHRwIC0gdGV4dCA6IC0xOwogICAgIH0KIAogICBkMSA9IGt3c2V0LT5kZWx0YTsK ICAgc3AgPSBrd3NldC0+dGFyZ2V0ICsgbGVuOwotICBnYzEgPSBzcFstMV07Ci0gIGdjMiA9IHNw Wy0yXTsKICAgdHAgPSB0ZXh0ICsgbGVuOworICBpZiAodHJhbnMpCisgICAgeworICAgICAgZ2Mx ID0gdHJhbnNbVShzcFstMV0pXTsKKyAgICAgIGdjMiA9IHRyYW5zW1Uoc3BbLTJdKV07CisgICAg fQorICBlbHNlCisgICAgeworICAgICAgZ2MxID0gc3BbLTFdOworICAgICAgZ2MyID0gc3BbLTJd OworICAgIH0KICAgc2tpcCA9IDA7CiAKICAgLyogU2lnbmlmaWNhbmNlIG9mIDEyOiAxIChpbml0 aWFsIG9mZnNldCkgKyAxMCAoc2tpcCBsb29wKSArIDEgKG1kMikuICovCkBAIC01NTMsMzAgKzU3 MCw2MiBAQCBibWV4ZWMgKGt3c2V0X3Qga3dzLCBjaGFyIGNvbnN0ICp0ZXh0LCBzaXplX3Qgc2l6 ZSkKICAgICAgICAgYnJlYWs7CiAgICAgICBmb3VuZDoKICAgICAgICAgZCA9IGxlbjsKLSAgICAg ICAgd2hpbGUgKDEpCisgICAgICAgIGlmICh0cmFucykKICAgICAgICAgICB7Ci0gICAgICAgICAg ICBpZiAodHBbLTJdID09IGdjMikKKyAgICAgICAgICAgIHdoaWxlICgxKQogICAgICAgICAgICAg ICB7Ci0gICAgICAgICAgICAgICAgZm9yIChpID0gMzsgaSA8PSBkICYmIHRwWy1pXSA9PSBzcFst aV07ICsraSkKLSAgICAgICAgICAgICAgICAgIDsKLSAgICAgICAgICAgICAgICBpZiAoaSA+IGQp CisgICAgICAgICAgICAgICAgaWYgKHRyYW5zW1UodHBbLTJdKV0gPT0gZ2MyKQogICAgICAgICAg ICAgICAgICAgewotICAgICAgICAgICAgICAgICAgICBmb3IgKGkgPSBkICsgc2tpcCArIDE7IGkg PD0gbGVuICYmIHRwWy1pXSA9PSBzcFstaV07ICsraSkKKyAgICAgICAgICAgICAgICAgICAgZm9y IChpID0gMzsgaSA8PSBkICYmIHRyYW5zW1UodHBbLWldKV0gPT0gdHJhbnNbVShzcFstaV0pXTsg KytpKQogICAgICAgICAgICAgICAgICAgICAgIDsKLSAgICAgICAgICAgICAgICAgICAgaWYgKGkg PiBsZW4pCi0gICAgICAgICAgICAgICAgICAgICAgcmV0dXJuIHRwIC0gbGVuIC0gdGV4dDsKKyAg ICAgICAgICAgICAgICAgICAgaWYgKGkgPiBkKQorICAgICAgICAgICAgICAgICAgICAgIHsKKyAg ICAgICAgICAgICAgICAgICAgICAgIGZvciAoaSA9IGQgKyBza2lwICsgMTsgaSA8PSBsZW4gJiYg dHJhbnNbVSh0cFstaV0pXSA9PSB0cmFuc1tVKHNwWy1pXSldOyArK2kpCisgICAgICAgICAgICAg ICAgICAgICAgICAgIDsKKyAgICAgICAgICAgICAgICAgICAgICAgIGlmIChpID4gbGVuKQorICAg ICAgICAgICAgICAgICAgICAgICAgICByZXR1cm4gdHAgLSBsZW4gLSB0ZXh0OworICAgICAgICAg ICAgICAgICAgICAgIH0KKyAgICAgICAgICAgICAgICAgICAgZCA9IGt3c2V0LT5zaGlmdFtpIC0g Ml07IHRwICs9IGQ7CisgICAgICAgICAgICAgICAgICAgIGlmICh0cCA+IGVwIHx8IHRyYW5zW1Uo dHBbLTFdKV0gIT0gZ2MxKQorICAgICAgICAgICAgICAgICAgICAgIGJyZWFrOworICAgICAgICAg ICAgICAgICAgICBza2lwID0gaSAtIDE7CisgICAgICAgICAgICAgICAgICB9CisgICAgICAgICAg ICAgICAgZWxzZQorICAgICAgICAgICAgICAgICAgeworICAgICAgICAgICAgICAgICAgICBkID0g a3dzZXQtPnNoaWZ0WzBdOyB0cCArPSBkOworICAgICAgICAgICAgICAgICAgICBpZiAodHAgPiBl cCB8fCB0cmFuc1tVKHRwWy0xXSldICE9IGdjMSkKKyAgICAgICAgICAgICAgICAgICAgICBicmVh azsKKyAgICAgICAgICAgICAgICAgICAgc2tpcCA9IDE7CiAgICAgICAgICAgICAgICAgICB9Ci0g ICAgICAgICAgICAgICAgZCA9IGt3c2V0LT5zaGlmdFtpIC0gMl07IHRwICs9IGQ7Ci0gICAgICAg ICAgICAgICAgaWYgKHRwID4gZXAgfHwgdHBbLTFdICE9IGdjMSkKLSAgICAgICAgICAgICAgICAg IGJyZWFrOwotICAgICAgICAgICAgICAgIHNraXAgPSBpIC0gMTsKICAgICAgICAgICAgICAgfQot ICAgICAgICAgICAgZWxzZQorICAgICAgICAgIH0KKyAgICAgICAgZWxzZQorICAgICAgICAgIHsK KyAgICAgICAgICAgIHdoaWxlICgxKQogICAgICAgICAgICAgICB7Ci0gICAgICAgICAgICAgICAg ZCA9IGt3c2V0LT5zaGlmdFswXTsgdHAgKz0gZDsKLSAgICAgICAgICAgICAgICBpZiAodHAgPiBl cCB8fCB0cFstMV0gIT0gZ2MxKQotICAgICAgICAgICAgICAgICAgYnJlYWs7Ci0gICAgICAgICAg ICAgICAgc2tpcCA9IDE7CisgICAgICAgICAgICAgICAgaWYgKHRwWy0yXSA9PSBnYzIpCisgICAg ICAgICAgICAgICAgICB7CisgICAgICAgICAgICAgICAgICAgIGZvciAoaSA9IDM7IGkgPD0gZCAm JiB0cFstaV0gPT0gc3BbLWldOyArK2kpCisgICAgICAgICAgICAgICAgICAgICAgOworICAgICAg ICAgICAgICAgICAgICBpZiAoaSA+IGQpCisgICAgICAgICAgICAgICAgICAgICAgeworICAgICAg ICAgICAgICAgICAgICAgICAgZm9yIChpID0gZCArIHNraXAgKyAxOyBpIDw9IGxlbiAmJiB0cFst aV0gPT0gc3BbLWldOyArK2kpCisgICAgICAgICAgICAgICAgICAgICAgICAgIDsKKyAgICAgICAg ICAgICAgICAgICAgICAgIGlmIChpID4gbGVuKQorICAgICAgICAgICAgICAgICAgICAgICAgICBy ZXR1cm4gdHAgLSBsZW4gLSB0ZXh0OworICAgICAgICAgICAgICAgICAgICAgIH0KKyAgICAgICAg ICAgICAgICAgICAgZCA9IGt3c2V0LT5zaGlmdFtpIC0gMl07IHRwICs9IGQ7CisgICAgICAgICAg ICAgICAgICAgIGlmICh0cCA+IGVwIHx8IHRwWy0xXSAhPSBnYzEpCisgICAgICAgICAgICAgICAg ICAgICAgYnJlYWs7CisgICAgICAgICAgICAgICAgICAgIHNraXAgPSBpIC0gMTsKKyAgICAgICAg ICAgICAgICAgIH0KKyAgICAgICAgICAgICAgICBlbHNlCisgICAgICAgICAgICAgICAgICB7Cisg ICAgICAgICAgICAgICAgICAgIGQgPSBrd3NldC0+c2hpZnRbMF07IHRwICs9IGQ7CisgICAgICAg ICAgICAgICAgICAgIGlmICh0cCA+IGVwIHx8IHRwWy0xXSAhPSBnYzEpCisgICAgICAgICAgICAg ICAgICAgICAgYnJlYWs7CisgICAgICAgICAgICAgICAgICAgIHNraXAgPSAxOworICAgICAgICAg ICAgICAgICAgfQogICAgICAgICAgICAgICB9CiAgICAgICAgICAgfQogICAgICAgfQpAQCAtNTkx LDMwICs2NDAsNjIgQEAgYm1leGVjIChrd3NldF90IGt3cywgY2hhciBjb25zdCAqdGV4dCwgc2l6 ZV90IHNpemUpCiAgICAgICBpZiAoZCAhPSAwKQogICAgICAgICBjb250aW51ZTsKICAgICAgIGQg PSBsZW47Ci0gICAgICB3aGlsZSAoMSkKKyAgICAgIGlmICh0cmFucykKICAgICAgICAgewotICAg ICAgICAgIGlmICh0cFstMl0gPT0gZ2MyKQorICAgICAgICAgIHdoaWxlICgxKQogICAgICAgICAg ICAgewotICAgICAgICAgICAgICBmb3IgKGkgPSAzOyBpIDw9IGQgJiYgdHBbLWldID09IHNwWy1p XTsgKytpKQotICAgICAgICAgICAgICAgIDsKLSAgICAgICAgICAgICAgaWYgKGkgPiBkKQorICAg ICAgICAgICAgICBpZiAodHJhbnNbVSh0cFstMl0pXSA9PSBnYzIpCiAgICAgICAgICAgICAgICAg ewotICAgICAgICAgICAgICAgICAgZm9yIChpID0gZCArIHNraXAgKyAxOyBpIDw9IGxlbiAmJiB0 cFstaV0gPT0gc3BbLWldOyArK2kpCisgICAgICAgICAgICAgICAgICBmb3IgKGkgPSAzOyBpIDw9 IGQgJiYgdHJhbnNbVSh0cFstaV0pXSA9PSB0cmFuc1tVKHNwWy1pXSldOyArK2kpCiAgICAgICAg ICAgICAgICAgICAgIDsKLSAgICAgICAgICAgICAgICAgIGlmIChpID4gbGVuKQotICAgICAgICAg ICAgICAgICAgICByZXR1cm4gdHAgLSBsZW4gLSB0ZXh0OworICAgICAgICAgICAgICAgICAgaWYg KGkgPiBkKQorICAgICAgICAgICAgICAgICAgICB7CisgICAgICAgICAgICAgICAgICAgICAgZm9y IChpID0gZCArIHNraXAgKyAxOyBpIDw9IGxlbiAmJiB0cmFuc1tVKHRwWy1pXSldID09IHRyYW5z W1Uoc3BbLWldKV07ICsraSkKKyAgICAgICAgICAgICAgICAgICAgICAgIDsKKyAgICAgICAgICAg ICAgICAgICAgICBpZiAoaSA+IGxlbikKKyAgICAgICAgICAgICAgICAgICAgICAgIHJldHVybiB0 cCAtIGxlbiAtIHRleHQ7CisgICAgICAgICAgICAgICAgICAgIH0KKyAgICAgICAgICAgICAgICAg IGQgPSBrd3NldC0+c2hpZnRbaSAtIDJdOyB0cCArPSBkOworICAgICAgICAgICAgICAgICAgaWYg KHRwID4gZXAgfHwgdHJhbnNbVSh0cFstMV0pXSAhPSBnYzEpCisgICAgICAgICAgICAgICAgICAg IGJyZWFrOworICAgICAgICAgICAgICAgICAgc2tpcCA9IGkgLSAxOworICAgICAgICAgICAgICAg IH0KKyAgICAgICAgICAgICAgZWxzZQorICAgICAgICAgICAgICAgIHsKKyAgICAgICAgICAgICAg ICAgIGQgPSBrd3NldC0+c2hpZnRbMF07IHRwICs9IGQ7CisgICAgICAgICAgICAgICAgICBpZiAo dHAgPiBlcCB8fCB0cmFuc1tVKHRwWy0xXSldICE9IGdjMSkKKyAgICAgICAgICAgICAgICAgICAg YnJlYWs7CisgICAgICAgICAgICAgICAgICBza2lwID0gMTsKICAgICAgICAgICAgICAgICB9Ci0g ICAgICAgICAgICAgIGQgPSBrd3NldC0+c2hpZnRbaSAtIDJdOyB0cCArPSBkOwotICAgICAgICAg ICAgICBpZiAodHAgPiBlcCB8fCB0cFstMV0gIT0gZ2MxKQotICAgICAgICAgICAgICAgIGJyZWFr OwotICAgICAgICAgICAgICBza2lwID0gaSAtIDE7CiAgICAgICAgICAgICB9Ci0gICAgICAgICAg ZWxzZQorICAgICAgICB9CisgICAgICBlbHNlCisgICAgICAgIHsKKyAgICAgICAgICB3aGlsZSAo MSkKICAgICAgICAgICAgIHsKLSAgICAgICAgICAgICAgZCA9IGt3c2V0LT5zaGlmdFswXTsgdHAg Kz0gZDsKLSAgICAgICAgICAgICAgaWYgKHRwID4gZXAgfHwgdHBbLTFdICE9IGdjMSkKLSAgICAg ICAgICAgICAgICBicmVhazsKLSAgICAgICAgICAgICAgc2tpcCA9IDE7CisgICAgICAgICAgICAg IGlmICh0cFstMl0gPT0gZ2MyKQorICAgICAgICAgICAgICAgIHsKKyAgICAgICAgICAgICAgICAg IGZvciAoaSA9IDM7IGkgPD0gZCAmJiB0cFstaV0gPT0gc3BbLWldOyArK2kpCisgICAgICAgICAg ICAgICAgICAgIDsKKyAgICAgICAgICAgICAgICAgIGlmIChpID4gZCkKKyAgICAgICAgICAgICAg ICAgICAgeworICAgICAgICAgICAgICAgICAgICAgIGZvciAoaSA9IGQgKyBza2lwICsgMTsgaSA8 PSBsZW4gJiYgdHBbLWldID09IHNwWy1pXTsgKytpKQorICAgICAgICAgICAgICAgICAgICAgICAg OworICAgICAgICAgICAgICAgICAgICAgIGlmIChpID4gbGVuKQorICAgICAgICAgICAgICAgICAg ICAgICAgcmV0dXJuIHRwIC0gbGVuIC0gdGV4dDsKKyAgICAgICAgICAgICAgICAgICAgfQorICAg ICAgICAgICAgICAgICAgZCA9IGt3c2V0LT5zaGlmdFtpIC0gMl07IHRwICs9IGQ7CisgICAgICAg ICAgICAgICAgICBpZiAodHAgPiBlcCB8fCB0cFstMV0gIT0gZ2MxKQorICAgICAgICAgICAgICAg ICAgICBicmVhazsKKyAgICAgICAgICAgICAgICAgIHNraXAgPSBpIC0gMTsKKyAgICAgICAgICAg ICAgICB9CisgICAgICAgICAgICAgIGVsc2UKKyAgICAgICAgICAgICAgICB7CisgICAgICAgICAg ICAgICAgICBkID0ga3dzZXQtPnNoaWZ0WzBdOyB0cCArPSBkOworICAgICAgICAgICAgICAgICAg aWYgKHRwID4gZXAgfHwgdHBbLTFdICE9IGdjMSkKKyAgICAgICAgICAgICAgICAgICAgYnJlYWs7 CisgICAgICAgICAgICAgICAgICBza2lwID0gMTsKKyAgICAgICAgICAgICAgICB9CiAgICAgICAg ICAgICB9CiAgICAgICAgIH0KICAgICB9CkBAIC03ODcsNyArODY4LDcgQEAgc2l6ZV90CiBrd3Nl eGVjIChrd3NldF90IGt3cywgY2hhciBjb25zdCAqdGV4dCwgc2l6ZV90IHNpemUsIHN0cnVjdCBr d3NtYXRjaCAqa3dzbWF0Y2gpCiB7CiAgIHN0cnVjdCBrd3NldCBjb25zdCAqa3dzZXQgPSAoc3Ry dWN0IGt3c2V0ICopIGt3czsKLSAgaWYgKGt3c2V0LT53b3JkcyA9PSAxICYmIGt3c2V0LT50cmFu cyA9PSBOVUxMKQorICBpZiAoa3dzZXQtPndvcmRzID09IDEpCiAgICAgewogICAgICAgc2l6ZV90 IHJldCA9IGJtZXhlYyAoa3dzLCB0ZXh0LCBzaXplKTsKICAgICAgIGlmIChyZXQgIT0gKHNpemVf dCkgLTEpCi0tIAoxLjkuMQoK --------_533CA08A000000006667_MULTIPART_MIXED_-- From unknown Tue Aug 12 08:32:41 2025 MIME-Version: 1.0 X-Mailer: MIME-tools 5.503 (Entity 5.503) X-Loop: help-debbugs@gnu.org From: help-debbugs@gnu.org (GNU bug Tracking System) To: Norihiro Tanaka Subject: bug#17013: closed (Re: bug#17013: [PATCH] grep: optimization by using the Galil rule for Boyer-Moore algorithm in KWSet) Message-ID: References: <5343655D.4020301@cs.ucla.edu> <20140314212120.7E5E.27F6AC2D@kcn.ne.jp> X-Gnu-PR-Message: they-closed 17013 X-Gnu-PR-Package: grep X-Gnu-PR-Keywords: patch Reply-To: 17013@debbugs.gnu.org Date: Tue, 08 Apr 2014 02:57:03 +0000 Content-Type: multipart/mixed; boundary="----------=_1396925823-25530-1" This is a multi-part message in MIME format... ------------=_1396925823-25530-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Your bug report #17013: [PATCH] grep: optimization by using the Galil rule for Boyer-Moore = algorithm in KWSet 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 17013@debbugs.gnu.org. --=20 17013: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D17013 GNU Bug Tracking System Contact help-debbugs@gnu.org with problems ------------=_1396925823-25530-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at 17013-done) by debbugs.gnu.org; 8 Apr 2014 02:56:44 +0000 Received: from localhost ([127.0.0.1]:40118 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WXMDJ-0006d6-MY for submit@debbugs.gnu.org; Mon, 07 Apr 2014 22:56:43 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:57683) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WXMDD-0006cu-9j for 17013-done@debbugs.gnu.org; Mon, 07 Apr 2014 22:56:38 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id 646D9A60001; Mon, 7 Apr 2014 19:56:34 -0700 (PDT) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu Received: from smtp.cs.ucla.edu ([127.0.0.1]) by localhost (smtp.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id KQpOFILH1pFv; Mon, 7 Apr 2014 19:56:30 -0700 (PDT) Received: from [192.168.1.9] (pool-108-0-233-62.lsanca.fios.verizon.net [108.0.233.62]) by smtp.cs.ucla.edu (Postfix) with ESMTPSA id D9B2839E8008; Mon, 7 Apr 2014 19:56:29 -0700 (PDT) Message-ID: <5343655D.4020301@cs.ucla.edu> Date: Mon, 07 Apr 2014 19:56:29 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.4.0 MIME-Version: 1.0 To: Norihiro Tanaka , 17013-done@debbugs.gnu.org Subject: Re: bug#17013: [PATCH] grep: optimization by using the Galil rule for Boyer-Moore algorithm in KWSet References: <20140314212120.7E5E.27F6AC2D@kcn.ne.jp> <20140315150609.6C6D.27F6AC2D@kcn.ne.jp> <20140403084521.6667.27F6AC2D@kcn.ne.jp> In-Reply-To: <20140403084521.6667.27F6AC2D@kcn.ne.jp> Content-Type: multipart/mixed; boundary="------------090507030209050109000008" X-Spam-Score: -2.6 (--) X-Debbugs-Envelope-To: 17013-done X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 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: -2.6 (--) This is a multi-part message in MIME format. --------------090507030209050109000008 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Norihiro Tanaka wrote: > In second patch, I changed so that Boyer-Moore algorithm could be used > also to case-insensitive matching if MB_CUR_MAX == 1. Thanks, I merged this patch into the savannah git master (attachment 1), applied a fixup patch for clarity and to fix some minor style issues (attachment 2), and fixed some longstanding kwset memory-allocation infelicities mostly having to do with unecessary code (attachment 3). --------------090507030209050109000008 Content-Type: text/plain; charset=UTF-8; name="0001-grep-use-the-Galil-rule-for-Boyer-Moore-algorithm-in.patch" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename*0="0001-grep-use-the-Galil-rule-for-Boyer-Moore-algorithm-in.pa"; filename*1="tch" RnJvbSBhZDAzZDRlYjIyYmUxYjkwNzIyMWFmNzhmNGEzYjRiY2Q4NWUxZmMyIE1vbiBTZXAg MTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBOb3JpaGlybyBUYW5ha2EgPG5vcml0bmtAa2NuLm5l LmpwPgpEYXRlOiBTYXQsIDE1IE1hciAyMDE0IDE0OjQxOjUyICswOTAwClN1YmplY3Q6IFtQ QVRDSCAxLzNdIGdyZXA6IHVzZSB0aGUgR2FsaWwgcnVsZSBmb3IgQm95ZXItTW9vcmUgYWxn b3JpdGhtIGluCiBLV1NldAoKVGhlIEJveWVyLU1vb3JlIGFsZ29yaXRobSBpcyBPKG0qbiks IHdoaWNoIG1lYW5zIGl0IG1heSBiZSBtdWNoCnNsb3dlciB0aGFuIHRoZSBERkEuICBJdHMg R2FsaWwgcnVsZSB2YXJpYW50IGlzIE8obikgYW5kIGluY3JlYXNlcwplZmZpY2llbmN5IGlu IHRoZSB0eXBpY2FsIGNhc2U7IGl0IHNraXBzIHNlY3Rpb25zIHRoYXQgYXJlIGtub3duCnRv IG1hdGNoIGFuZCBkb2VzIG5vdCBjb21wYXJlIG1vcmUgdGhhbiBvbmNlIGZvciBhIHBvc2l0 aW9uIGluIHRoZSB0ZXh0LgpUbyB1c2UgdGhlIEdhbGlsIHJ1bGUsIGxvb2sgZm9yIHRoZSBk ZWx0YTIgc2hpZnQgYXQgZWFjaCBwb3NpdGlvbgpmcm9tIHRoZSB0cmllIGluc3RlYWQgb2Yg dGhlICdtaW5kMicgdmFsdWUuCiogc3JjL2t3c2V0LmMgKHN0cnVjdCBrd3NldCk6IFJlcGxh Y2UgbWVtYmVyICdtaW5kMicgd2l0aCAnc2hpZnQnLgooa3dzcHJlcCk6IExvb2sgZm9yIHRo ZSBkZWx0YTIgc2hpZnQuCihibWV4ZWMpOiBVc2UgaXQuCi0tLQogc3JjL2t3c2V0LmMgfCAy MTQgKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tCiAxIGZpbGUgY2hhbmdlZCwgMTI3IGluc2VydGlvbnMoKyksIDg3IGRlbGV0 aW9ucygtKQoKZGlmZiAtLWdpdCBhL3NyYy9rd3NldC5jIGIvc3JjL2t3c2V0LmMKaW5kZXgg NDEwZTA0Ni4uZTBiZjZiMiAxMDA2NDQKLS0tIGEvc3JjL2t3c2V0LmMKKysrIGIvc3JjL2t3 c2V0LmMKQEAgLTgzLDcgKzgzLDcgQEAgc3RydWN0IGt3c2V0CiAgIHVuc2lnbmVkIGNoYXIg ZGVsdGFbTkNIQVJdOwkvKiBEZWx0YSB0YWJsZSBmb3IgcmFwaWQgc2VhcmNoLiAqLwogICBz dHJ1Y3QgdHJpZSAqbmV4dFtOQ0hBUl07CS8qIFRhYmxlIG9mIGNoaWxkcmVuIG9mIHRoZSBy b290LiAqLwogICBjaGFyICp0YXJnZXQ7CQkJLyogVGFyZ2V0IHN0cmluZyBpZiB0aGVyZSdz IG9ubHkgb25lLiAqLwotICBpbnQgbWluZDI7CQkJLyogVXNlZCBpbiBCb3llci1Nb29yZSBz ZWFyY2ggZm9yIG9uZSBzdHJpbmcuICovCisgIGludCAqc2hpZnQ7CQkJLyogVXNlZCBpbiBC b3llci1Nb29yZSBzZWFyY2ggZm9yIG9uZSBzdHJpbmcuICovCiAgIGNoYXIgY29uc3QgKnRy YW5zOwkJLyogQ2hhcmFjdGVyIHRyYW5zbGF0aW9uIHRhYmxlLiAqLwogfTsKIApAQCAtMzk3 LDEyICszOTcsNzAgQEAga3dzcHJlcCAoa3dzZXRfdCBrd3MpCiAgICAgIG5vZGUgYXQgd2hp Y2ggYW4gb3V0Z29pbmcgZWRnZSBpcyBsYWJlbGVkIGJ5IHRoYXQgY2hhcmFjdGVyLiAqLwog ICBtZW1zZXQoZGVsdGEsIGt3c2V0LT5taW5kIDwgVUNIQVJfTUFYID8ga3dzZXQtPm1pbmQg OiBVQ0hBUl9NQVgsIE5DSEFSKTsKIAorICBzdHJ1Y3QgdHJpZSAqZmFpbDsKKyAgc3RydWN0 IHRyaWUgKmxhc3QsICpuZXh0W05DSEFSXTsKKworICAvKiBUcmF2ZXJzZSB0aGUgbm9kZXMg b2YgdGhlIHRyaWUgaW4gbGV2ZWwgb3JkZXIsIHNpbXVsdGFuZW91c2x5CisgICAgIGNvbXB1 dGluZyB0aGUgZGVsdGEgdGFibGUsIGZhaWx1cmUgZnVuY3Rpb24sIGFuZCBzaGlmdCBmdW5j dGlvbi4gKi8KKyAgZm9yIChjdXJyID0gbGFzdCA9IGt3c2V0LT50cmllOyBjdXJyOyBjdXJy ID0gY3Vyci0+bmV4dCkKKyAgICB7CisgICAgICAvKiBFbnF1ZXVlIHRoZSBpbW1lZGlhdGUg ZGVzY2VuZGFudHMgaW4gdGhlIGxldmVsIG9yZGVyIHF1ZXVlLiAqLworICAgICAgZW5xdWV1 ZShjdXJyLT5saW5rcywgJmxhc3QpOworCisgICAgICBjdXJyLT5zaGlmdCA9IGt3c2V0LT5t aW5kOworICAgICAgY3Vyci0+bWF4c2hpZnQgPSBrd3NldC0+bWluZDsKKworICAgICAgLyog VXBkYXRlIHRoZSBkZWx0YSB0YWJsZSBmb3IgdGhlIGRlc2NlbmRhbnRzIG9mIHRoaXMgbm9k ZS4gKi8KKyAgICAgIHRyZWVkZWx0YShjdXJyLT5saW5rcywgY3Vyci0+ZGVwdGgsIGRlbHRh KTsKKworICAgICAgLyogQ29tcHV0ZSB0aGUgZmFpbHVyZSBmdW5jdGlvbiBmb3IgdGhlIGRl c2NlbmRhbnRzIG9mIHRoaXMgbm9kZS4gICovCisgICAgICB0cmVlZmFpbHMoY3Vyci0+bGlu a3MsIGN1cnItPmZhaWwsIGt3c2V0LT50cmllKTsKKworICAgICAgLyogVXBkYXRlIHRoZSBz aGlmdHMgYXQgZWFjaCBub2RlIGluIHRoZSBjdXJyZW50IG5vZGUncyBjaGFpbgorICAgICAg ICAgb2YgZmFpbHMgYmFjayB0byB0aGUgcm9vdC4gKi8KKyAgICAgIGZvciAoZmFpbCA9IGN1 cnItPmZhaWw7IGZhaWw7IGZhaWwgPSBmYWlsLT5mYWlsKQorICAgICAgICB7CisgICAgICAg ICAgLyogSWYgdGhlIGN1cnJlbnQgbm9kZSBoYXMgc29tZSBvdXRnb2luZyBlZGdlIHRoYXQg dGhlIGZhaWwKKyAgICAgICAgICAgICBkb2Vzbid0LCB0aGVuIHRoZSBzaGlmdCBhdCB0aGUg ZmFpbCBzaG91bGQgYmUgbm8gbGFyZ2VyCisgICAgICAgICAgICAgdGhhbiB0aGUgZGlmZmVy ZW5jZSBvZiB0aGVpciBkZXB0aHMuICovCisgICAgICAgICAgaWYgKCFoYXNldmVyeShmYWls LT5saW5rcywgY3Vyci0+bGlua3MpKQorICAgICAgICAgICAgaWYgKGN1cnItPmRlcHRoIC0g ZmFpbC0+ZGVwdGggPCBmYWlsLT5zaGlmdCkKKyAgICAgICAgICAgICAgZmFpbC0+c2hpZnQg PSBjdXJyLT5kZXB0aCAtIGZhaWwtPmRlcHRoOworCisgICAgICAgICAgLyogSWYgdGhlIGN1 cnJlbnQgbm9kZSBpcyBhY2NlcHRpbmcgdGhlbiB0aGUgc2hpZnQgYXQgdGhlCisgICAgICAg ICAgICAgZmFpbCBhbmQgaXRzIGRlc2NlbmRhbnRzIHNob3VsZCBiZSBubyBsYXJnZXIgdGhh biB0aGUKKyAgICAgICAgICAgICBkaWZmZXJlbmNlIG9mIHRoZWlyIGRlcHRocy4gKi8KKyAg ICAgICAgICBpZiAoY3Vyci0+YWNjZXB0aW5nICYmIGZhaWwtPm1heHNoaWZ0ID4gY3Vyci0+ ZGVwdGggLSBmYWlsLT5kZXB0aCkKKyAgICAgICAgICAgIGZhaWwtPm1heHNoaWZ0ID0gY3Vy ci0+ZGVwdGggLSBmYWlsLT5kZXB0aDsKKyAgICAgICAgfQorICAgIH0KKworICAvKiBUcmF2 ZXJzZSB0aGUgdHJpZSBpbiBsZXZlbCBvcmRlciBhZ2FpbiwgZml4aW5nIHVwIGFsbCBub2Rl cyB3aG9zZQorICAgICBzaGlmdCBleGNlZWRzIHRoZWlyIGluaGVyaXRlZCBtYXhzaGlmdC4g Ki8KKyAgZm9yIChjdXJyID0ga3dzZXQtPnRyaWUtPm5leHQ7IGN1cnI7IGN1cnIgPSBjdXJy LT5uZXh0KQorICAgIHsKKyAgICAgIGlmIChjdXJyLT5tYXhzaGlmdCA+IGN1cnItPnBhcmVu dC0+bWF4c2hpZnQpCisgICAgICAgIGN1cnItPm1heHNoaWZ0ID0gY3Vyci0+cGFyZW50LT5t YXhzaGlmdDsKKyAgICAgIGlmIChjdXJyLT5zaGlmdCA+IGN1cnItPm1heHNoaWZ0KQorICAg ICAgICBjdXJyLT5zaGlmdCA9IGN1cnItPm1heHNoaWZ0OworICAgIH0KKworICAvKiBDcmVh dGUgYSB2ZWN0b3IsIGluZGV4ZWQgYnkgY2hhcmFjdGVyIGNvZGUsIG9mIHRoZSBvdXRnb2lu ZyBsaW5rcworICAgICBmcm9tIHRoZSByb290IG5vZGUuICovCisgIGZvciAoaSA9IDA7IGkg PCBOQ0hBUjsgKytpKQorICAgIG5leHRbaV0gPSBOVUxMOworICB0cmVlbmV4dChrd3NldC0+ dHJpZS0+bGlua3MsIG5leHQpOworCisgIGlmICgodHJhbnMgPSBrd3NldC0+dHJhbnMpICE9 IE5VTEwpCisgICAgZm9yIChpID0gMDsgaSA8IE5DSEFSOyArK2kpCisgICAgICBrd3NldC0+ bmV4dFtpXSA9IG5leHRbVSh0cmFuc1tpXSldOworICBlbHNlCisgICAgbWVtY3B5KGt3c2V0 LT5uZXh0LCBuZXh0LCBOQ0hBUiAqIHNpemVvZihzdHJ1Y3QgdHJpZSAqKSk7CisKICAgLyog Q2hlY2sgaWYgd2UgY2FuIHVzZSB0aGUgc2ltcGxlIGJveWVyLW1vb3JlIGFsZ29yaXRobSwg aW5zdGVhZAogICAgICBvZiB0aGUgaGFpcnkgY29tbWVudHotd2FsdGVyIGFsZ29yaXRobS4g Ki8KICAgaWYgKGt3c2V0LT53b3JkcyA9PSAxICYmIGt3c2V0LT50cmFucyA9PSBOVUxMKQog ICAgIHsKLSAgICAgIGNoYXIgYzsKLQogICAgICAgLyogTG9va2luZyBmb3IganVzdCBvbmUg c3RyaW5nLiAgRXh0cmFjdCBpdCBmcm9tIHRoZSB0cmllLiAqLwogICAgICAga3dzZXQtPnRh cmdldCA9IG9ic3RhY2tfYWxsb2MoJmt3c2V0LT5vYnN0YWNrLCBrd3NldC0+bWluZCk7CiAg ICAgICBpZiAoIWt3c2V0LT50YXJnZXQpCkBAIC00MTAsODAgKzQ2OCwyMiBAQCBrd3NwcmVw IChrd3NldF90IGt3cykKICAgICAgIGZvciAoaSA9IGt3c2V0LT5taW5kIC0gMSwgY3VyciA9 IGt3c2V0LT50cmllOyBpID49IDA7IC0taSkKICAgICAgICAgewogICAgICAgICAgIGt3c2V0 LT50YXJnZXRbaV0gPSBjdXJyLT5saW5rcy0+bGFiZWw7Ci0gICAgICAgICAgY3VyciA9IGN1 cnItPmxpbmtzLT50cmllOworICAgICAgICAgIGN1cnIgPSBjdXJyLT5uZXh0OwogICAgICAg ICB9Ci0gICAgICAvKiBCdWlsZCB0aGUgQm95ZXIgTW9vcmUgZGVsdGEuICBCb3kgdGhhdCdz IGVhc3kgY29tcGFyZWQgdG8gQ1cuICovCi0gICAgICBmb3IgKGkgPSAwOyBpIDwga3dzZXQt Pm1pbmQ7ICsraSkKLSAgICAgICAgZGVsdGFbVShrd3NldC0+dGFyZ2V0W2ldKV0gPSBrd3Nl dC0+bWluZCAtIChpICsgMSk7Ci0gICAgICAvKiBGaW5kIHRoZSBtaW5pbWFsIGRlbHRhMiBz aGlmdCB0aGF0IHdlIG1pZ2h0IG1ha2UgYWZ0ZXIKLSAgICAgICAgIGEgYmFja3dhcmRzIG1h dGNoIGhhcyBmYWlsZWQuICovCi0gICAgICBjID0ga3dzZXQtPnRhcmdldFtrd3NldC0+bWlu ZCAtIDFdOwotICAgICAgZm9yIChpID0ga3dzZXQtPm1pbmQgLSAyOyBpID49IDA7IC0taSkK LSAgICAgICAgaWYgKGt3c2V0LT50YXJnZXRbaV0gPT0gYykKLSAgICAgICAgICBicmVhazsK LSAgICAgIGt3c2V0LT5taW5kMiA9IGt3c2V0LT5taW5kIC0gKGkgKyAxKTsKLSAgICB9Ci0g IGVsc2UKLSAgICB7Ci0gICAgICBzdHJ1Y3QgdHJpZSAqZmFpbDsKLSAgICAgIHN0cnVjdCB0 cmllICpsYXN0LCAqbmV4dFtOQ0hBUl07Ci0KLSAgICAgIC8qIFRyYXZlcnNlIHRoZSBub2Rl cyBvZiB0aGUgdHJpZSBpbiBsZXZlbCBvcmRlciwgc2ltdWx0YW5lb3VzbHkKLSAgICAgICAg IGNvbXB1dGluZyB0aGUgZGVsdGEgdGFibGUsIGZhaWx1cmUgZnVuY3Rpb24sIGFuZCBzaGlm dCBmdW5jdGlvbi4gKi8KLSAgICAgIGZvciAoY3VyciA9IGxhc3QgPSBrd3NldC0+dHJpZTsg Y3VycjsgY3VyciA9IGN1cnItPm5leHQpCisgICAgICAvKiBMb29raW5nIGZvciB0aGUgZGVs dGEyIHNoaWZ0IHRoYXQgd2UgbWlnaHQgbWFrZSBhZnRlciBhCisgICAgICAgICBiYWNrd2Fy ZHMgbWF0Y2ggaGFzIGZhaWxlZC4gIEV4dHJhY3QgaXQgZnJvbSB0aGUgdHJpZS4gKi8KKyAg ICAgIGlmIChrd3NldC0+bWluZCA+IDEpCiAgICAgICAgIHsKLSAgICAgICAgICAvKiBFbnF1 ZXVlIHRoZSBpbW1lZGlhdGUgZGVzY2VuZGFudHMgaW4gdGhlIGxldmVsIG9yZGVyIHF1ZXVl LiAqLwotICAgICAgICAgIGVucXVldWUoY3Vyci0+bGlua3MsICZsYXN0KTsKLQotICAgICAg ICAgIGN1cnItPnNoaWZ0ID0ga3dzZXQtPm1pbmQ7Ci0gICAgICAgICAgY3Vyci0+bWF4c2hp ZnQgPSBrd3NldC0+bWluZDsKLQotICAgICAgICAgIC8qIFVwZGF0ZSB0aGUgZGVsdGEgdGFi bGUgZm9yIHRoZSBkZXNjZW5kYW50cyBvZiB0aGlzIG5vZGUuICovCi0gICAgICAgICAgdHJl ZWRlbHRhKGN1cnItPmxpbmtzLCBjdXJyLT5kZXB0aCwgZGVsdGEpOwotCi0gICAgICAgICAg LyogQ29tcHV0ZSB0aGUgZmFpbHVyZSBmdW5jdGlvbiBmb3IgdGhlIGRlc2NlbmRhbnRzIG9m IHRoaXMgbm9kZS4gICovCi0gICAgICAgICAgdHJlZWZhaWxzKGN1cnItPmxpbmtzLCBjdXJy LT5mYWlsLCBrd3NldC0+dHJpZSk7Ci0KLSAgICAgICAgICAvKiBVcGRhdGUgdGhlIHNoaWZ0 cyBhdCBlYWNoIG5vZGUgaW4gdGhlIGN1cnJlbnQgbm9kZSdzIGNoYWluCi0gICAgICAgICAg ICAgb2YgZmFpbHMgYmFjayB0byB0aGUgcm9vdC4gKi8KLSAgICAgICAgICBmb3IgKGZhaWwg PSBjdXJyLT5mYWlsOyBmYWlsOyBmYWlsID0gZmFpbC0+ZmFpbCkKKyAgICAgICAgICBrd3Nl dC0+c2hpZnQgPSBvYnN0YWNrX2FsbG9jKCZrd3NldC0+b2JzdGFjaywKKyAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgIHNpemVvZiAoKmt3c2V0LT5zaGlmdCkgKiAo a3dzZXQtPm1pbmQgLSAxKSk7CisgICAgICAgICAgaWYgKCFrd3NldC0+c2hpZnQpCisgICAg ICAgICAgICByZXR1cm4gXygibWVtb3J5IGV4aGF1c3RlZCIpOworICAgICAgICAgIGZvciAo aSA9IDAsIGN1cnIgPSBrd3NldC0+dHJpZS0+bmV4dDsgaSA8IGt3c2V0LT5taW5kIC0gMTsg KytpKQogICAgICAgICAgICAgewotICAgICAgICAgICAgICAvKiBJZiB0aGUgY3VycmVudCBu b2RlIGhhcyBzb21lIG91dGdvaW5nIGVkZ2UgdGhhdCB0aGUgZmFpbAotICAgICAgICAgICAg ICAgICBkb2Vzbid0LCB0aGVuIHRoZSBzaGlmdCBhdCB0aGUgZmFpbCBzaG91bGQgYmUgbm8g bGFyZ2VyCi0gICAgICAgICAgICAgICAgIHRoYW4gdGhlIGRpZmZlcmVuY2Ugb2YgdGhlaXIg ZGVwdGhzLiAqLwotICAgICAgICAgICAgICBpZiAoIWhhc2V2ZXJ5KGZhaWwtPmxpbmtzLCBj dXJyLT5saW5rcykpCi0gICAgICAgICAgICAgICAgaWYgKGN1cnItPmRlcHRoIC0gZmFpbC0+ ZGVwdGggPCBmYWlsLT5zaGlmdCkKLSAgICAgICAgICAgICAgICAgIGZhaWwtPnNoaWZ0ID0g Y3Vyci0+ZGVwdGggLSBmYWlsLT5kZXB0aDsKLQotICAgICAgICAgICAgICAvKiBJZiB0aGUg Y3VycmVudCBub2RlIGlzIGFjY2VwdGluZyB0aGVuIHRoZSBzaGlmdCBhdCB0aGUKLSAgICAg ICAgICAgICAgICAgZmFpbCBhbmQgaXRzIGRlc2NlbmRhbnRzIHNob3VsZCBiZSBubyBsYXJn ZXIgdGhhbiB0aGUKLSAgICAgICAgICAgICAgICAgZGlmZmVyZW5jZSBvZiB0aGVpciBkZXB0 aHMuICovCi0gICAgICAgICAgICAgIGlmIChjdXJyLT5hY2NlcHRpbmcgJiYgZmFpbC0+bWF4 c2hpZnQgPiBjdXJyLT5kZXB0aCAtIGZhaWwtPmRlcHRoKQotICAgICAgICAgICAgICAgIGZh aWwtPm1heHNoaWZ0ID0gY3Vyci0+ZGVwdGggLSBmYWlsLT5kZXB0aDsKKyAgICAgICAgICAg ICAga3dzZXQtPnNoaWZ0W2ldID0gY3Vyci0+c2hpZnQ7CisgICAgICAgICAgICAgIGN1cnIg PSBjdXJyLT5uZXh0OwogICAgICAgICAgICAgfQogICAgICAgICB9Ci0KLSAgICAgIC8qIFRy YXZlcnNlIHRoZSB0cmllIGluIGxldmVsIG9yZGVyIGFnYWluLCBmaXhpbmcgdXAgYWxsIG5v ZGVzIHdob3NlCi0gICAgICAgICBzaGlmdCBleGNlZWRzIHRoZWlyIGluaGVyaXRlZCBtYXhz aGlmdC4gKi8KLSAgICAgIGZvciAoY3VyciA9IGt3c2V0LT50cmllLT5uZXh0OyBjdXJyOyBj dXJyID0gY3Vyci0+bmV4dCkKLSAgICAgICAgewotICAgICAgICAgIGlmIChjdXJyLT5tYXhz aGlmdCA+IGN1cnItPnBhcmVudC0+bWF4c2hpZnQpCi0gICAgICAgICAgICBjdXJyLT5tYXhz aGlmdCA9IGN1cnItPnBhcmVudC0+bWF4c2hpZnQ7Ci0gICAgICAgICAgaWYgKGN1cnItPnNo aWZ0ID4gY3Vyci0+bWF4c2hpZnQpCi0gICAgICAgICAgICBjdXJyLT5zaGlmdCA9IGN1cnIt Pm1heHNoaWZ0OwotICAgICAgICB9Ci0KLSAgICAgIC8qIENyZWF0ZSBhIHZlY3RvciwgaW5k ZXhlZCBieSBjaGFyYWN0ZXIgY29kZSwgb2YgdGhlIG91dGdvaW5nIGxpbmtzCi0gICAgICAg ICBmcm9tIHRoZSByb290IG5vZGUuICovCi0gICAgICBmb3IgKGkgPSAwOyBpIDwgTkNIQVI7 ICsraSkKLSAgICAgICAgbmV4dFtpXSA9IE5VTEw7Ci0gICAgICB0cmVlbmV4dChrd3NldC0+ dHJpZS0+bGlua3MsIG5leHQpOwotCi0gICAgICBpZiAoKHRyYW5zID0ga3dzZXQtPnRyYW5z KSAhPSBOVUxMKQotICAgICAgICBmb3IgKGkgPSAwOyBpIDwgTkNIQVI7ICsraSkKLSAgICAg ICAgICBrd3NldC0+bmV4dFtpXSA9IG5leHRbVSh0cmFuc1tpXSldOwotICAgICAgZWxzZQot ICAgICAgICBtZW1jcHkoa3dzZXQtPm5leHQsIG5leHQsIE5DSEFSICogc2l6ZW9mKHN0cnVj dCB0cmllICopKTsKICAgICB9CiAKICAgLyogRml4IHRoaW5ncyB1cCBmb3IgYW55IHRyYW5z bGF0aW9uIHRhYmxlLiAqLwpAQCAtNTAzLDcgKzUwMyw4IEBAIGJtZXhlYyAoa3dzZXRfdCBr d3MsIGNoYXIgY29uc3QgKnRleHQsIHNpemVfdCBzaXplKQogICBzdHJ1Y3Qga3dzZXQgY29u c3QgKmt3c2V0OwogICB1bnNpZ25lZCBjaGFyIGNvbnN0ICpkMTsKICAgY2hhciBjb25zdCAq ZXAsICpzcCwgKnRwOwotICBpbnQgZCwgZ2MsIGksIGxlbiwgbWQyOworICBpbnQgZCwgaSwg bGVuLCBza2lwOworICBjaGFyIGdjMSwgZ2MyOwogCiAgIGt3c2V0ID0gKHN0cnVjdCBrd3Nl dCBjb25zdCAqKSBrd3M7CiAgIGxlbiA9IGt3c2V0LT5taW5kOwpAQCAtNTIwLDkgKzUyMSwx MCBAQCBibWV4ZWMgKGt3c2V0X3Qga3dzLCBjaGFyIGNvbnN0ICp0ZXh0LCBzaXplX3Qgc2l6 ZSkKIAogICBkMSA9IGt3c2V0LT5kZWx0YTsKICAgc3AgPSBrd3NldC0+dGFyZ2V0ICsgbGVu OwotICBnYyA9IFUoc3BbLTJdKTsKLSAgbWQyID0ga3dzZXQtPm1pbmQyOworICBnYzEgPSBz cFstMV07CisgIGdjMiA9IHNwWy0yXTsKICAgdHAgPSB0ZXh0ICsgbGVuOworICBza2lwID0g MDsKIAogICAvKiBTaWduaWZpY2FuY2Ugb2YgMTI6IDEgKGluaXRpYWwgb2Zmc2V0KSArIDEw IChza2lwIGxvb3ApICsgMSAobWQyKS4gKi8KICAgaWYgKHNpemUgPiAxMiAqIGxlbikKQEAg LTU1MCwxNCArNTUyLDMzIEBAIGJtZXhlYyAoa3dzZXRfdCBrd3MsIGNoYXIgY29uc3QgKnRl eHQsIHNpemVfdCBzaXplKQogICAgICAgICAgIH0KICAgICAgICAgYnJlYWs7CiAgICAgICBm b3VuZDoKLSAgICAgICAgaWYgKFUodHBbLTJdKSA9PSBnYykKKyAgICAgICAgZCA9IGxlbjsK KyAgICAgICAgd2hpbGUgKDEpCiAgICAgICAgICAgewotICAgICAgICAgICAgZm9yIChpID0g MzsgaSA8PSBsZW4gJiYgVSh0cFstaV0pID09IFUoc3BbLWldKTsgKytpKQotICAgICAgICAg ICAgICA7Ci0gICAgICAgICAgICBpZiAoaSA+IGxlbikKLSAgICAgICAgICAgICAgcmV0dXJu IHRwIC0gbGVuIC0gdGV4dDsKKyAgICAgICAgICAgIGlmICh0cFstMl0gPT0gZ2MyKQorICAg ICAgICAgICAgICB7CisgICAgICAgICAgICAgICAgZm9yIChpID0gMzsgaSA8PSBkICYmIHRw Wy1pXSA9PSBzcFstaV07ICsraSkKKyAgICAgICAgICAgICAgICAgIDsKKyAgICAgICAgICAg ICAgICBpZiAoaSA+IGQpCisgICAgICAgICAgICAgICAgICB7CisgICAgICAgICAgICAgICAg ICAgIGZvciAoaSA9IGQgKyBza2lwICsgMTsgaSA8PSBsZW4gJiYgdHBbLWldID09IHNwWy1p XTsgKytpKQorICAgICAgICAgICAgICAgICAgICAgIDsKKyAgICAgICAgICAgICAgICAgICAg aWYgKGkgPiBsZW4pCisgICAgICAgICAgICAgICAgICAgICAgcmV0dXJuIHRwIC0gbGVuIC0g dGV4dDsKKyAgICAgICAgICAgICAgICAgIH0KKyAgICAgICAgICAgICAgICBkID0ga3dzZXQt PnNoaWZ0W2kgLSAyXTsgdHAgKz0gZDsKKyAgICAgICAgICAgICAgICBpZiAodHAgPiBlcCB8 fCB0cFstMV0gIT0gZ2MxKQorICAgICAgICAgICAgICAgICAgYnJlYWs7CisgICAgICAgICAg ICAgICAgc2tpcCA9IGkgLSAxOworICAgICAgICAgICAgICB9CisgICAgICAgICAgICBlbHNl CisgICAgICAgICAgICAgIHsKKyAgICAgICAgICAgICAgICBkID0ga3dzZXQtPnNoaWZ0WzBd OyB0cCArPSBkOworICAgICAgICAgICAgICAgIGlmICh0cCA+IGVwIHx8IHRwWy0xXSAhPSBn YzEpCisgICAgICAgICAgICAgICAgICBicmVhazsKKyAgICAgICAgICAgICAgICBza2lwID0g MTsKKyAgICAgICAgICAgICAgfQogICAgICAgICAgIH0KLSAgICAgICAgdHAgKz0gbWQyOwog ICAgICAgfQogCiAgIC8qIE5vdyB3ZSBoYXZlIG9ubHkgYSBmZXcgY2hhcmFjdGVycyBsZWZ0 IHRvIHNlYXJjaC4gIFdlCkBAIC01NjksMTQgKzU5MCwzMyBAQCBibWV4ZWMgKGt3c2V0X3Qg a3dzLCBjaGFyIGNvbnN0ICp0ZXh0LCBzaXplX3Qgc2l6ZSkKICAgICAgIGQgPSBkMVtVKCh0 cCArPSBkKVstMV0pXTsKICAgICAgIGlmIChkICE9IDApCiAgICAgICAgIGNvbnRpbnVlOwot ICAgICAgaWYgKFUodHBbLTJdKSA9PSBnYykKKyAgICAgIGQgPSBsZW47CisgICAgICB3aGls ZSAoMSkKICAgICAgICAgewotICAgICAgICAgIGZvciAoaSA9IDM7IGkgPD0gbGVuICYmIFUo dHBbLWldKSA9PSBVKHNwWy1pXSk7ICsraSkKLSAgICAgICAgICAgIDsKLSAgICAgICAgICBp ZiAoaSA+IGxlbikKLSAgICAgICAgICAgIHJldHVybiB0cCAtIGxlbiAtIHRleHQ7CisgICAg ICAgICAgaWYgKHRwWy0yXSA9PSBnYzIpCisgICAgICAgICAgICB7CisgICAgICAgICAgICAg IGZvciAoaSA9IDM7IGkgPD0gZCAmJiB0cFstaV0gPT0gc3BbLWldOyArK2kpCisgICAgICAg ICAgICAgICAgOworICAgICAgICAgICAgICBpZiAoaSA+IGQpCisgICAgICAgICAgICAgICAg eworICAgICAgICAgICAgICAgICAgZm9yIChpID0gZCArIHNraXAgKyAxOyBpIDw9IGxlbiAm JiB0cFstaV0gPT0gc3BbLWldOyArK2kpCisgICAgICAgICAgICAgICAgICAgIDsKKyAgICAg ICAgICAgICAgICAgIGlmIChpID4gbGVuKQorICAgICAgICAgICAgICAgICAgICByZXR1cm4g dHAgLSBsZW4gLSB0ZXh0OworICAgICAgICAgICAgICAgIH0KKyAgICAgICAgICAgICAgZCA9 IGt3c2V0LT5zaGlmdFtpIC0gMl07IHRwICs9IGQ7CisgICAgICAgICAgICAgIGlmICh0cCA+ IGVwIHx8IHRwWy0xXSAhPSBnYzEpCisgICAgICAgICAgICAgICAgYnJlYWs7CisgICAgICAg ICAgICAgIHNraXAgPSBpIC0gMTsKKyAgICAgICAgICAgIH0KKyAgICAgICAgICBlbHNlCisg ICAgICAgICAgICB7CisgICAgICAgICAgICAgIGQgPSBrd3NldC0+c2hpZnRbMF07IHRwICs9 IGQ7CisgICAgICAgICAgICAgIGlmICh0cCA+IGVwIHx8IHRwWy0xXSAhPSBnYzEpCisgICAg ICAgICAgICAgICAgYnJlYWs7CisgICAgICAgICAgICAgIHNraXAgPSAxOworICAgICAgICAg ICAgfQogICAgICAgICB9Ci0gICAgICBkID0gbWQyOwogICAgIH0KIAogICByZXR1cm4gLTE7 Ci0tIAoxLjkuMAoK --------------090507030209050109000008 Content-Type: text/plain; charset=UTF-8; name="0002-grep-minor-cleanups-for-Galil-speedups.patch" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="0002-grep-minor-cleanups-for-Galil-speedups.patch" RnJvbSA2NTQ2ZjI1NTI1ZjI5MTJjMDczM2UxZTE5ZTRlMzhlNDEwZGYyOGIwIE1vbiBTZXAg MTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBQYXVsIEVnZ2VydCA8ZWdnZXJ0QGNzLnVjbGEuZWR1 PgpEYXRlOiBNb24sIDcgQXByIDIwMTQgMTI6MTg6MzMgLTA3MDAKU3ViamVjdDogW1BBVENI IDIvM10gZ3JlcDogbWlub3IgY2xlYW51cHMgZm9yIEdhbGlsIHNwZWVkdXBzCgoqIHNyYy9r d3NldC5jOiBVcGRhdGUgY2l0YXRpb25zLgpJbmNsdWRlIHN0ZGJvb2wuaC4KKGt3c2luY3Is IGt3c3ByZXApOiBDbGFyaWZ5IGJ5IHVzaW5nIEM5OSBkZWNscyBhZnRlciBzdGF0ZW1lbnRz Lgooa3dzcHJlcCk6IENsYXJpZnkgYnkgdXNpbmcgTUlOLiAgQXZvaWQgYSBjb3VwbGUgb2Yg YnVmZmVyIGNvcGllcwp3aGVuICFUUkFOUy4KKGJtZXhlYyk6IFVzZSBib29sIGZvciBib29s ZWFuLiAgUHJlZmVyICJjb250aW51ZTsiIHRvICI7Ii4KLS0tCiBzcmMva3dzZXQuYyB8IDEy MSArKysrKysrKysrKysrKysrKysrKysrKysrKysrKy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0KIDEgZmlsZSBjaGFuZ2VkLCA1OSBpbnNlcnRpb25zKCspLCA2MiBkZWxldGlv bnMoLSkKCmRpZmYgLS1naXQgYS9zcmMva3dzZXQuYyBiL3NyYy9rd3NldC5jCmluZGV4IGUw YmY2YjIuLjZjMDcyNDkgMTAwNjQ0Ci0tLSBhL3NyYy9rd3NldC5jCisrKyBiL3NyYy9rd3Nl dC5jCkBAIC0yMywxMyArMjMsMTYgQEAKIAogLyogVGhlIGFsZ29yaXRobSBpbXBsZW1lbnRl ZCBieSB0aGVzZSByb3V0aW5lcyBiZWFycyBhIHN0YXJ0bGluZyByZXNlbWJsYW5jZQogICAg dG8gb25lIGRpc2NvdmVyZWQgYnkgQmVhdGUgQ29tbWVudHotV2FsdGVyLCBhbHRob3VnaCBp dCBpcyBub3QgaWRlbnRpY2FsLgotICAgU2VlICJBIFN0cmluZyBNYXRjaGluZyBBbGdvcml0 aG0gRmFzdCBvbiB0aGUgQXZlcmFnZSwiIFRlY2huaWNhbCBSZXBvcnQsCi0gICBJQk0tR2Vy bWFueSwgU2NpZW50aWZpYyBDZW50ZXIgSGVpZGVsYmVyZywgVGllcmdhcnRlbnN0cmFzc2Ug MTUsIEQtNjkwMAotICAgSGVpZGVsYmVyZywgR2VybWFueS4gIFNlZSBhbHNvIEFobywgQS5W LiwgYW5kIE0uIENvcmFzaWNrLCAiRWZmaWNpZW50Ci0gICBTdHJpbmcgTWF0Y2hpbmc6ICBB biBBaWQgdG8gQmlibGlvZ3JhcGhpYyBTZWFyY2gsIiBDQUNNIEp1bmUgMTk3NSwKLSAgIFZv bC4gMTgsIE5vLiA2LCB3aGljaCBkZXNjcmliZXMgdGhlIGZhaWx1cmUgZnVuY3Rpb24gdXNl ZCBiZWxvdy4gKi8KKyAgIFNlZTogQ29tbWVudHotV2FsdGVyIEIuIEEgc3RyaW5nIG1hdGNo aW5nIGFsZ29yaXRobSBmYXN0IG9uIHRoZSBhdmVyYWdlLgorICAgTGVjdHVyZSBOb3RlcyBp biBDb21wdXRlciBTY2llbmNlIDcxICgxOTc5KSwgMTE4LTMyCisgICA8aHR0cDovL2R4LmRv aS5vcmcvMTAuMTAwNy8zLTU0MC0wOTUxMC0xXzEwPi4KKyAgIFNlZSBhbHNvOiBBaG8gQVYs IENvcmFzaWNrIE1KLiBFZmZpY2llbnQgc3RyaW5nIG1hdGNoaW5nOiBhbiBhaWQgdG8KKyAg IGJpYmxpb2dyYXBoaWMgc2VhcmNoLiBDQUNNIDE4LCA2ICgxOTc1KSwgMzMzLTQwCisgICA8 aHR0cDovL2R4LmRvaS5vcmcvMTAuMTE0NS8zNjA4MjUuMzYwODU1Piwgd2hpY2ggZGVzY3Jp YmVzIHRoZQorICAgZmFpbHVyZSBmdW5jdGlvbiB1c2VkIGJlbG93LiAqLwogCiAjaW5jbHVk ZSA8Y29uZmlnLmg+CisjaW5jbHVkZSA8c3RkYm9vbC5oPgogI2luY2x1ZGUgPHN5cy90eXBl cy5oPgogI2luY2x1ZGUgInN5c3RlbS5oIgogI2luY2x1ZGUgImt3c2V0LmgiCkBAIC0xMzEs MzIgKzEzNCwyOCBAQCBrd3NhbGxvYyAoY2hhciBjb25zdCAqdHJhbnMpCiBjb25zdCBjaGFy ICoKIGt3c2luY3IgKGt3c2V0X3Qga3dzLCBjaGFyIGNvbnN0ICp0ZXh0LCBzaXplX3QgbGVu KQogewotICBzdHJ1Y3Qga3dzZXQgKmt3c2V0OwotICBzdHJ1Y3QgdHJpZSAqdHJpZTsKLSAg dW5zaWduZWQgY2hhciBsYWJlbDsKLSAgc3RydWN0IHRyZWUgKmxpbms7Ci0gIGludCBkZXB0 aDsKLSAgc3RydWN0IHRyZWUgKmxpbmtzW0RFUFRIX1NJWkVdOwotICBlbnVtIHsgTCwgUiB9 IGRpcnNbREVQVEhfU0laRV07Ci0gIHN0cnVjdCB0cmVlICp0LCAqciwgKmwsICpybCwgKmxy OworICBzdHJ1Y3Qga3dzZXQgKmt3c2V0ID0ga3dzOworICBzdHJ1Y3QgdHJpZSAqdHJpZSA9 IGt3c2V0LT50cmllOworICBjaGFyIGNvbnN0ICp0cmFucyA9IGt3c2V0LT50cmFuczsKIAot ICBrd3NldCA9IChzdHJ1Y3Qga3dzZXQgKikga3dzOwotICB0cmllID0ga3dzZXQtPnRyaWU7 CiAgIHRleHQgKz0gbGVuOwogCiAgIC8qIERlc2NlbmQgdGhlIHRyaWUgKGJ1aWx0IG9mIHJl dmVyc2VkIGtleXdvcmRzKSBjaGFyYWN0ZXItYnktY2hhcmFjdGVyLAogICAgICBpbnN0YWxs aW5nIG5ldyBub2RlcyB3aGVuIG5lY2Vzc2FyeS4gKi8KICAgd2hpbGUgKGxlbi0tKQogICAg IHsKLSAgICAgIGxhYmVsID0ga3dzZXQtPnRyYW5zID8ga3dzZXQtPnRyYW5zW1UoKi0tdGV4 dCldIDogKi0tdGV4dDsKKyAgICAgIHVuc2lnbmVkIGNoYXIgdWMgPSAqLS10ZXh0OworICAg ICAgdW5zaWduZWQgY2hhciBsYWJlbCA9IHRyYW5zID8gdHJhbnNbdWNdIDogdWM7CiAKICAg ICAgIC8qIERlc2NlbmQgdGhlIHRyZWUgb2Ygb3V0Z29pbmcgbGlua3MgZm9yIHRoaXMgdHJp ZSBub2RlLAogICAgICAgICAgbG9va2luZyBmb3IgdGhlIGN1cnJlbnQgY2hhcmFjdGVyIGFu ZCBrZWVwaW5nIHRyYWNrCiAgICAgICAgICBvZiB0aGUgcGF0aCBmb2xsb3dlZC4gKi8KLSAg ICAgIGxpbmsgPSB0cmllLT5saW5rczsKKyAgICAgIHN0cnVjdCB0cmVlICpsaW5rID0gdHJp ZS0+bGlua3M7CisgICAgICBzdHJ1Y3QgdHJlZSAqbGlua3NbREVQVEhfU0laRV07CisgICAg ICBlbnVtIHsgTCwgUiB9IGRpcnNbREVQVEhfU0laRV07CiAgICAgICBsaW5rc1swXSA9IChz dHJ1Y3QgdHJlZSAqKSAmdHJpZS0+bGlua3M7CiAgICAgICBkaXJzWzBdID0gTDsKLSAgICAg IGRlcHRoID0gMTsKKyAgICAgIGludCBkZXB0aCA9IDE7CiAKICAgICAgIHdoaWxlIChsaW5r ICYmIGxhYmVsICE9IGxpbmstPmxhYmVsKQogICAgICAgICB7CkBAIC0yMTUsNiArMjE0LDgg QEAga3dzaW5jciAoa3dzZXRfdCBrd3MsIGNoYXIgY29uc3QgKnRleHQsIHNpemVfdCBsZW4p CiAgICAgICAgICAgaWYgKGRlcHRoICYmICgoZGlyc1tkZXB0aF0gPT0gTCAmJiAtLWxpbmtz W2RlcHRoXS0+YmFsYW5jZSkKICAgICAgICAgICAgICAgICAgICAgICAgIHx8IChkaXJzW2Rl cHRoXSA9PSBSICYmICsrbGlua3NbZGVwdGhdLT5iYWxhbmNlKSkpCiAgICAgICAgICAgICB7 CisgICAgICAgICAgICAgIHN0cnVjdCB0cmVlICp0LCAqciwgKmwsICpybCwgKmxyOworCiAg ICAgICAgICAgICAgIHN3aXRjaCAobGlua3NbZGVwdGhdLT5iYWxhbmNlKQogICAgICAgICAg ICAgICAgIHsKICAgICAgICAgICAgICAgICBjYXNlIChjaGFyKSAtMjoKQEAgLTM4NCw1OSAr Mzg1LDU2IEBAIHRyZWVuZXh0IChzdHJ1Y3QgdHJlZSBjb25zdCAqdHJlZSwgc3RydWN0IHRy aWUgKm5leHRbXSkKIGNvbnN0IGNoYXIgKgoga3dzcHJlcCAoa3dzZXRfdCBrd3MpCiB7Ci0g IHN0cnVjdCBrd3NldCAqa3dzZXQ7CisgIHN0cnVjdCBrd3NldCAqa3dzZXQgPSBrd3M7Cisg IGNoYXIgY29uc3QgKnRyYW5zID0ga3dzZXQtPnRyYW5zOwogICBpbnQgaTsKLSAgc3RydWN0 IHRyaWUgKmN1cnI7Ci0gIGNoYXIgY29uc3QgKnRyYW5zOwotICB1bnNpZ25lZCBjaGFyIGRl bHRhW05DSEFSXTsKLQotICBrd3NldCA9IChzdHJ1Y3Qga3dzZXQgKikga3dzOworICB1bnNp Z25lZCBjaGFyIGRlbHRhYnVmW05DSEFSXTsKKyAgdW5zaWduZWQgY2hhciAqZGVsdGEgPSB0 cmFucyA/IGRlbHRhYnVmIDoga3dzZXQtPmRlbHRhOwogCiAgIC8qIEluaXRpYWwgdmFsdWVz IGZvciB0aGUgZGVsdGEgdGFibGU7IHdpbGwgYmUgY2hhbmdlZCBsYXRlci4gIFRoZQogICAg ICBkZWx0YSBlbnRyeSBmb3IgYSBnaXZlbiBjaGFyYWN0ZXIgaXMgdGhlIHNtYWxsZXN0IGRl cHRoIG9mIGFueQogICAgICBub2RlIGF0IHdoaWNoIGFuIG91dGdvaW5nIGVkZ2UgaXMgbGFi ZWxlZCBieSB0aGF0IGNoYXJhY3Rlci4gKi8KLSAgbWVtc2V0KGRlbHRhLCBrd3NldC0+bWlu ZCA8IFVDSEFSX01BWCA/IGt3c2V0LT5taW5kIDogVUNIQVJfTUFYLCBOQ0hBUik7Ci0KLSAg c3RydWN0IHRyaWUgKmZhaWw7Ci0gIHN0cnVjdCB0cmllICpsYXN0LCAqbmV4dFtOQ0hBUl07 CisgIG1lbXNldCAoZGVsdGEsIE1JTiAoa3dzZXQtPm1pbmQsIFVDSEFSX01BWCksIHNpemVv ZiBkZWx0YWJ1Zik7CiAKICAgLyogVHJhdmVyc2UgdGhlIG5vZGVzIG9mIHRoZSB0cmllIGlu IGxldmVsIG9yZGVyLCBzaW11bHRhbmVvdXNseQotICAgICBjb21wdXRpbmcgdGhlIGRlbHRh IHRhYmxlLCBmYWlsdXJlIGZ1bmN0aW9uLCBhbmQgc2hpZnQgZnVuY3Rpb24uICovCisgICAg IGNvbXB1dGluZyB0aGUgZGVsdGEgdGFibGUsIGZhaWx1cmUgZnVuY3Rpb24sIGFuZCBzaGlm dCBmdW5jdGlvbi4gICovCisgIHN0cnVjdCB0cmllICpjdXJyLCAqbGFzdDsKICAgZm9yIChj dXJyID0gbGFzdCA9IGt3c2V0LT50cmllOyBjdXJyOyBjdXJyID0gY3Vyci0+bmV4dCkKICAg ICB7Ci0gICAgICAvKiBFbnF1ZXVlIHRoZSBpbW1lZGlhdGUgZGVzY2VuZGFudHMgaW4gdGhl IGxldmVsIG9yZGVyIHF1ZXVlLiAqLwotICAgICAgZW5xdWV1ZShjdXJyLT5saW5rcywgJmxh c3QpOworICAgICAgLyogRW5xdWV1ZSB0aGUgaW1tZWRpYXRlIGRlc2NlbmRhbnRzIGluIHRo ZSBsZXZlbCBvcmRlciBxdWV1ZS4gICovCisgICAgICBlbnF1ZXVlIChjdXJyLT5saW5rcywg Jmxhc3QpOwogCiAgICAgICBjdXJyLT5zaGlmdCA9IGt3c2V0LT5taW5kOwogICAgICAgY3Vy ci0+bWF4c2hpZnQgPSBrd3NldC0+bWluZDsKIAotICAgICAgLyogVXBkYXRlIHRoZSBkZWx0 YSB0YWJsZSBmb3IgdGhlIGRlc2NlbmRhbnRzIG9mIHRoaXMgbm9kZS4gKi8KLSAgICAgIHRy ZWVkZWx0YShjdXJyLT5saW5rcywgY3Vyci0+ZGVwdGgsIGRlbHRhKTsKKyAgICAgIC8qIFVw ZGF0ZSB0aGUgZGVsdGEgdGFibGUgZm9yIHRoZSBkZXNjZW5kYW50cyBvZiB0aGlzIG5vZGUu ICAqLworICAgICAgdHJlZWRlbHRhIChjdXJyLT5saW5rcywgY3Vyci0+ZGVwdGgsIGRlbHRh KTsKIAogICAgICAgLyogQ29tcHV0ZSB0aGUgZmFpbHVyZSBmdW5jdGlvbiBmb3IgdGhlIGRl c2NlbmRhbnRzIG9mIHRoaXMgbm9kZS4gICovCi0gICAgICB0cmVlZmFpbHMoY3Vyci0+bGlu a3MsIGN1cnItPmZhaWwsIGt3c2V0LT50cmllKTsKKyAgICAgIHRyZWVmYWlscyAoY3Vyci0+ bGlua3MsIGN1cnItPmZhaWwsIGt3c2V0LT50cmllKTsKIAogICAgICAgLyogVXBkYXRlIHRo ZSBzaGlmdHMgYXQgZWFjaCBub2RlIGluIHRoZSBjdXJyZW50IG5vZGUncyBjaGFpbgotICAg ICAgICAgb2YgZmFpbHMgYmFjayB0byB0aGUgcm9vdC4gKi8KKyAgICAgICAgIG9mIGZhaWxz IGJhY2sgdG8gdGhlIHJvb3QuICAqLworICAgICAgc3RydWN0IHRyaWUgKmZhaWw7CiAgICAg ICBmb3IgKGZhaWwgPSBjdXJyLT5mYWlsOyBmYWlsOyBmYWlsID0gZmFpbC0+ZmFpbCkKICAg ICAgICAgewogICAgICAgICAgIC8qIElmIHRoZSBjdXJyZW50IG5vZGUgaGFzIHNvbWUgb3V0 Z29pbmcgZWRnZSB0aGF0IHRoZSBmYWlsCiAgICAgICAgICAgICAgZG9lc24ndCwgdGhlbiB0 aGUgc2hpZnQgYXQgdGhlIGZhaWwgc2hvdWxkIGJlIG5vIGxhcmdlcgotICAgICAgICAgICAg IHRoYW4gdGhlIGRpZmZlcmVuY2Ugb2YgdGhlaXIgZGVwdGhzLiAqLwotICAgICAgICAgIGlm ICghaGFzZXZlcnkoZmFpbC0+bGlua3MsIGN1cnItPmxpbmtzKSkKKyAgICAgICAgICAgICB0 aGFuIHRoZSBkaWZmZXJlbmNlIG9mIHRoZWlyIGRlcHRocy4gICovCisgICAgICAgICAgaWYg KCFoYXNldmVyeSAoZmFpbC0+bGlua3MsIGN1cnItPmxpbmtzKSkKICAgICAgICAgICAgIGlm IChjdXJyLT5kZXB0aCAtIGZhaWwtPmRlcHRoIDwgZmFpbC0+c2hpZnQpCiAgICAgICAgICAg ICAgIGZhaWwtPnNoaWZ0ID0gY3Vyci0+ZGVwdGggLSBmYWlsLT5kZXB0aDsKIAogICAgICAg ICAgIC8qIElmIHRoZSBjdXJyZW50IG5vZGUgaXMgYWNjZXB0aW5nIHRoZW4gdGhlIHNoaWZ0 IGF0IHRoZQogICAgICAgICAgICAgIGZhaWwgYW5kIGl0cyBkZXNjZW5kYW50cyBzaG91bGQg YmUgbm8gbGFyZ2VyIHRoYW4gdGhlCi0gICAgICAgICAgICAgZGlmZmVyZW5jZSBvZiB0aGVp ciBkZXB0aHMuICovCisgICAgICAgICAgICAgZGlmZmVyZW5jZSBvZiB0aGVpciBkZXB0aHMu ICAqLwogICAgICAgICAgIGlmIChjdXJyLT5hY2NlcHRpbmcgJiYgZmFpbC0+bWF4c2hpZnQg PiBjdXJyLT5kZXB0aCAtIGZhaWwtPmRlcHRoKQogICAgICAgICAgICAgZmFpbC0+bWF4c2hp ZnQgPSBjdXJyLT5kZXB0aCAtIGZhaWwtPmRlcHRoOwogICAgICAgICB9CiAgICAgfQogCiAg IC8qIFRyYXZlcnNlIHRoZSB0cmllIGluIGxldmVsIG9yZGVyIGFnYWluLCBmaXhpbmcgdXAg YWxsIG5vZGVzIHdob3NlCi0gICAgIHNoaWZ0IGV4Y2VlZHMgdGhlaXIgaW5oZXJpdGVkIG1h eHNoaWZ0LiAqLworICAgICBzaGlmdCBleGNlZWRzIHRoZWlyIGluaGVyaXRlZCBtYXhzaGlm dC4gICovCiAgIGZvciAoY3VyciA9IGt3c2V0LT50cmllLT5uZXh0OyBjdXJyOyBjdXJyID0g Y3Vyci0+bmV4dCkKICAgICB7CiAgICAgICBpZiAoY3Vyci0+bWF4c2hpZnQgPiBjdXJyLT5w YXJlbnQtPm1heHNoaWZ0KQpAQCAtNDQ2LDIwICs0NDQsMTggQEAga3dzcHJlcCAoa3dzZXRf dCBrd3MpCiAgICAgfQogCiAgIC8qIENyZWF0ZSBhIHZlY3RvciwgaW5kZXhlZCBieSBjaGFy YWN0ZXIgY29kZSwgb2YgdGhlIG91dGdvaW5nIGxpbmtzCi0gICAgIGZyb20gdGhlIHJvb3Qg bm9kZS4gKi8KLSAgZm9yIChpID0gMDsgaSA8IE5DSEFSOyArK2kpCi0gICAgbmV4dFtpXSA9 IE5VTEw7Ci0gIHRyZWVuZXh0KGt3c2V0LT50cmllLT5saW5rcywgbmV4dCk7Ci0KLSAgaWYg KCh0cmFucyA9IGt3c2V0LT50cmFucykgIT0gTlVMTCkKKyAgICAgZnJvbSB0aGUgcm9vdCBu b2RlLiAgKi8KKyAgc3RydWN0IHRyaWUgKm5leHRidWZbTkNIQVJdOworICBzdHJ1Y3QgdHJp ZSAqKm5leHQgPSB0cmFucyA/IG5leHRidWYgOiBrd3NldC0+bmV4dDsKKyAgbWVtc2V0IChu ZXh0LCAwLCBzaXplb2YgbmV4dGJ1Zik7CisgIHRyZWVuZXh0IChrd3NldC0+dHJpZS0+bGlu a3MsIG5leHQpOworICBpZiAodHJhbnMpCiAgICAgZm9yIChpID0gMDsgaSA8IE5DSEFSOyAr K2kpCiAgICAgICBrd3NldC0+bmV4dFtpXSA9IG5leHRbVSh0cmFuc1tpXSldOwotICBlbHNl Ci0gICAgbWVtY3B5KGt3c2V0LT5uZXh0LCBuZXh0LCBOQ0hBUiAqIHNpemVvZihzdHJ1Y3Qg dHJpZSAqKSk7CiAKICAgLyogQ2hlY2sgaWYgd2UgY2FuIHVzZSB0aGUgc2ltcGxlIGJveWVy LW1vb3JlIGFsZ29yaXRobSwgaW5zdGVhZAogICAgICBvZiB0aGUgaGFpcnkgY29tbWVudHot d2FsdGVyIGFsZ29yaXRobS4gKi8KLSAgaWYgKGt3c2V0LT53b3JkcyA9PSAxICYmIGt3c2V0 LT50cmFucyA9PSBOVUxMKQorICBpZiAoIXRyYW5zICYmIGt3c2V0LT53b3JkcyA9PSAxKQog ICAgIHsKICAgICAgIC8qIExvb2tpbmcgZm9yIGp1c3Qgb25lIHN0cmluZy4gIEV4dHJhY3Qg aXQgZnJvbSB0aGUgdHJpZS4gKi8KICAgICAgIGt3c2V0LT50YXJnZXQgPSBvYnN0YWNrX2Fs bG9jKCZrd3NldC0+b2JzdGFjaywga3dzZXQtPm1pbmQpOwpAQCAtNDcxLDExICs0NjcsMTIg QEAga3dzcHJlcCAoa3dzZXRfdCBrd3MpCiAgICAgICAgICAgY3VyciA9IGN1cnItPm5leHQ7 CiAgICAgICAgIH0KICAgICAgIC8qIExvb2tpbmcgZm9yIHRoZSBkZWx0YTIgc2hpZnQgdGhh dCB3ZSBtaWdodCBtYWtlIGFmdGVyIGEKLSAgICAgICAgIGJhY2t3YXJkcyBtYXRjaCBoYXMg ZmFpbGVkLiAgRXh0cmFjdCBpdCBmcm9tIHRoZSB0cmllLiAqLworICAgICAgICAgYmFja3dh cmRzIG1hdGNoIGhhcyBmYWlsZWQuICBFeHRyYWN0IGl0IGZyb20gdGhlIHRyaWUuICAqLwog ICAgICAgaWYgKGt3c2V0LT5taW5kID4gMSkKICAgICAgICAgewotICAgICAgICAgIGt3c2V0 LT5zaGlmdCA9IG9ic3RhY2tfYWxsb2MoJmt3c2V0LT5vYnN0YWNrLAotICAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgc2l6ZW9mICgqa3dzZXQtPnNoaWZ0KSAqIChr d3NldC0+bWluZCAtIDEpKTsKKyAgICAgICAgICBrd3NldC0+c2hpZnQKKyAgICAgICAgICAg ID0gb2JzdGFja19hbGxvYyAoJmt3c2V0LT5vYnN0YWNrLAorICAgICAgICAgICAgICAgICAg ICAgICAgICAgICBzaXplb2YgKmt3c2V0LT5zaGlmdCAqIChrd3NldC0+bWluZCAtIDEpKTsK ICAgICAgICAgICBpZiAoIWt3c2V0LT5zaGlmdCkKICAgICAgICAgICAgIHJldHVybiBfKCJt ZW1vcnkgZXhoYXVzdGVkIik7CiAgICAgICAgICAgZm9yIChpID0gMCwgY3VyciA9IGt3c2V0 LT50cmllLT5uZXh0OyBpIDwga3dzZXQtPm1pbmQgLSAxOyArK2kpCkBAIC00ODcsMTEgKzQ4 NCw5IEBAIGt3c3ByZXAgKGt3c2V0X3Qga3dzKQogICAgIH0KIAogICAvKiBGaXggdGhpbmdz IHVwIGZvciBhbnkgdHJhbnNsYXRpb24gdGFibGUuICovCi0gIGlmICgodHJhbnMgPSBrd3Nl dC0+dHJhbnMpICE9IE5VTEwpCisgIGlmICh0cmFucykKICAgICBmb3IgKGkgPSAwOyBpIDwg TkNIQVI7ICsraSkKICAgICAgIGt3c2V0LT5kZWx0YVtpXSA9IGRlbHRhW1UodHJhbnNbaV0p XTsKLSAgZWxzZQotICAgIG1lbWNweShrd3NldC0+ZGVsdGEsIGRlbHRhLCBOQ0hBUik7CiAK ICAgcmV0dXJuIE5VTEw7CiB9CkBAIC01NTMsMTYgKzU0OCwxNiBAQCBibWV4ZWMgKGt3c2V0 X3Qga3dzLCBjaGFyIGNvbnN0ICp0ZXh0LCBzaXplX3Qgc2l6ZSkKICAgICAgICAgYnJlYWs7 CiAgICAgICBmb3VuZDoKICAgICAgICAgZCA9IGxlbjsKLSAgICAgICAgd2hpbGUgKDEpCisg ICAgICAgIHdoaWxlICh0cnVlKQogICAgICAgICAgIHsKICAgICAgICAgICAgIGlmICh0cFst Ml0gPT0gZ2MyKQogICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgZm9yIChpID0g MzsgaSA8PSBkICYmIHRwWy1pXSA9PSBzcFstaV07ICsraSkKLSAgICAgICAgICAgICAgICAg IDsKKyAgICAgICAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgICAgICAgICAgIGlmIChp ID4gZCkKICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgZm9yIChp ID0gZCArIHNraXAgKyAxOyBpIDw9IGxlbiAmJiB0cFstaV0gPT0gc3BbLWldOyArK2kpCi0g ICAgICAgICAgICAgICAgICAgICAgOworICAgICAgICAgICAgICAgICAgICAgIGNvbnRpbnVl OwogICAgICAgICAgICAgICAgICAgICBpZiAoaSA+IGxlbikKICAgICAgICAgICAgICAgICAg ICAgICByZXR1cm4gdHAgLSBsZW4gLSB0ZXh0OwogICAgICAgICAgICAgICAgICAgfQpAQCAt NTkxLDE2ICs1ODYsMTYgQEAgYm1leGVjIChrd3NldF90IGt3cywgY2hhciBjb25zdCAqdGV4 dCwgc2l6ZV90IHNpemUpCiAgICAgICBpZiAoZCAhPSAwKQogICAgICAgICBjb250aW51ZTsK ICAgICAgIGQgPSBsZW47Ci0gICAgICB3aGlsZSAoMSkKKyAgICAgIHdoaWxlICh0cnVlKQog ICAgICAgICB7CiAgICAgICAgICAgaWYgKHRwWy0yXSA9PSBnYzIpCiAgICAgICAgICAgICB7 CiAgICAgICAgICAgICAgIGZvciAoaSA9IDM7IGkgPD0gZCAmJiB0cFstaV0gPT0gc3BbLWld OyArK2kpCi0gICAgICAgICAgICAgICAgOworICAgICAgICAgICAgICAgIGNvbnRpbnVlOwog ICAgICAgICAgICAgICBpZiAoaSA+IGQpCiAgICAgICAgICAgICAgICAgewogICAgICAgICAg ICAgICAgICAgZm9yIChpID0gZCArIHNraXAgKyAxOyBpIDw9IGxlbiAmJiB0cFstaV0gPT0g c3BbLWldOyArK2kpCi0gICAgICAgICAgICAgICAgICAgIDsKKyAgICAgICAgICAgICAgICAg ICAgY29udGludWU7CiAgICAgICAgICAgICAgICAgICBpZiAoaSA+IGxlbikKICAgICAgICAg ICAgICAgICAgICAgcmV0dXJuIHRwIC0gbGVuIC0gdGV4dDsKICAgICAgICAgICAgICAgICB9 CkBAIC02OTEsNyArNjg2LDggQEAgY3dleGVjIChrd3NldF90IGt3cywgY2hhciBjb25zdCAq dGV4dCwgc2l6ZV90IGxlbiwgc3RydWN0IGt3c21hdGNoICprd3NtYXRjaCkKICAgICAgIGQg PSB0cmllLT5zaGlmdDsKICAgICAgIHdoaWxlIChiZWcgPiB0ZXh0KQogICAgICAgICB7Ci0g ICAgICAgICAgYyA9IHRyYW5zID8gdHJhbnNbVSgqLS1iZWcpXSA6ICotLWJlZzsKKyAgICAg ICAgICB1bnNpZ25lZCBjaGFyIHVjID0gKi0tYmVnOworICAgICAgICAgIGMgPSB0cmFucyA/ IHRyYW5zW3VjXSA6IHVjOwogICAgICAgICAgIHRyZWUgPSB0cmllLT5saW5rczsKICAgICAg ICAgICB3aGlsZSAodHJlZSAmJiBjICE9IHRyZWUtPmxhYmVsKQogICAgICAgICAgICAgaWYg KGMgPCB0cmVlLT5sYWJlbCkKQEAgLTc0Miw3ICs3MzgsOCBAQCBjd2V4ZWMgKGt3c2V0X3Qg a3dzLCBjaGFyIGNvbnN0ICp0ZXh0LCBzaXplX3QgbGVuLCBzdHJ1Y3Qga3dzbWF0Y2ggKmt3 c21hdGNoKQogICAgICAgZCA9IHRyaWUtPnNoaWZ0OwogICAgICAgd2hpbGUgKGJlZyA+IHRl eHQpCiAgICAgICAgIHsKLSAgICAgICAgICBjID0gdHJhbnMgPyB0cmFuc1tVKCotLWJlZyld IDogKi0tYmVnOworICAgICAgICAgIHVuc2lnbmVkIGNoYXIgdWMgPSAqLS1iZWc7CisgICAg ICAgICAgYyA9IHRyYW5zID8gdHJhbnNbdWNdIDogdWM7CiAgICAgICAgICAgdHJlZSA9IHRy aWUtPmxpbmtzOwogICAgICAgICAgIHdoaWxlICh0cmVlICYmIGMgIT0gdHJlZS0+bGFiZWwp CiAgICAgICAgICAgICBpZiAoYyA8IHRyZWUtPmxhYmVsKQotLSAKMS45LjAKCg== --------------090507030209050109000008 Content-Type: text/plain; charset=UTF-8; name="0003-grep-simplify-memory-allocation-in-kwset.patch" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="0003-grep-simplify-memory-allocation-in-kwset.patch" RnJvbSAyMmFmODdiMWE4ZGUxOTU4ZDUwNGI1ZTZlMTc1NTNlZTExOTMwYjZjIE1vbiBTZXAg MTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBQYXVsIEVnZ2VydCA8ZWdnZXJ0QGNzLnVjbGEuZWR1 PgpEYXRlOiBNb24sIDcgQXByIDIwMTQgMTk6NDg6MzMgLTA3MDAKU3ViamVjdDogW1BBVENI IDMvM10gZ3JlcDogc2ltcGxpZnkgbWVtb3J5IGFsbG9jYXRpb24gaW4ga3dzZXQKCiogc3Jj L2t3c2V0LmM6IEluY2x1ZGUga3dzZXQuaCBmaXJzdCwgdG8gY2hlY2sgaXRzIHByZXJlcXMu CkluY2x1ZGUgeGFsbG9jLmgsIGZvciB4bWFsbG9jLgooa3dzYWxsb2MpOiBVc2UgeG1hbGxv Yywgbm90IG1hbGxvYywgc28gdGhhdCB0aGUgY2FsbGVyIG5lZWQgbm90CndvcnJ5IGFib3V0 IG1lbW9yeSBhbGxvY2F0aW9uIGZhaWx1cmUuCihrd3NhbGxvYywga3dzaW5jciwga3dzcHJl cCk6IERvIG5vdCB3b3JyeSBhYm91dCBvYnN0YWNrX2FsbG9jCnJldHVybmluZyBOVUxMLCBh cyB0aGF0J3Mgbm90IHBvc3NpYmxlLgooa3dzYWxsb2MsIGt3c2luY3IsIGt3c3ByZXAsIGJt ZXhlYywgY3dleGVjLCBrd3NleGVjLCBrd3NmcmVlKToKT21pdCB1bm5lY2Vzc2FyeSBjb252 ZXJzaW9uIGJldHdlZW4gc3RydWN0IGt3c2V0ICogYW5kIGt3c2V0X3QuCihrd3NpbmNyLCBr d3NwcmVwKTogUmV0dXJuIHZvaWQgc2luY2UgbWVtb3J5LWFsbG9jYXRpb24gZmFpbHVyZSBp cwpub3QgcG9zc2libGUgbm93LiAgQWxsIHVzZXMgY2hhbmdlZC4KKiBzcmMva3dzZXQuaDog SW5jbHVkZSA8c3RkZGVmLmg+LCBmb3Igc2l6ZV90LCBzbyB0aGF0IHRoaXMKaW5jbHVkZSBm aWxlIGRvZXNuJ3QgcmVxdWlyZSBvdGhlciBmaWxlcyB0byBiZSBpbmNsdWRlZCBmaXJzdC4K LS0tCiBzcmMvZGZhc2VhcmNoLmMgfCAxMCArKy0tLS0tCiBzcmMva3dzZWFyY2guYyAgfCAg NyArKy0tLQogc3JjL2t3c2V0LmMgICAgIHwgOTMgKysrKysrKysrKysrKysrKysrLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCiBzcmMva3dzZXQuaCAgICAgfCAx NyArKysrKy0tLS0tLQogNCBmaWxlcyBjaGFuZ2VkLCA0MiBpbnNlcnRpb25zKCspLCA4NSBk ZWxldGlvbnMoLSkKCmRpZmYgLS1naXQgYS9zcmMvZGZhc2VhcmNoLmMgYi9zcmMvZGZhc2Vh cmNoLmMKaW5kZXggYWRlYzRlMi4uNDQzNjBiNiAxMDA2NDQKLS0tIGEvc3JjL2RmYXNlYXJj aC5jCisrKyBiL3NyYy9kZmFzZWFyY2guYwpAQCAtOTAsNyArOTAsNiBAQCBrd3NtdXN0cyAo dm9pZCkKICAgc3RydWN0IGRmYW11c3QgY29uc3QgKmRtID0gZGZhbXVzdHMgKGRmYSk7CiAg IGlmIChkbSkKICAgICB7Ci0gICAgICBjaGFyIGNvbnN0ICplcnI7CiAgICAgICBrd3Npbml0 ICgma3dzZXQpOwogICAgICAgLyogRmlyc3QsIHdlIGNvbXBpbGUgaW4gdGhlIHN1YnN0cmlu Z3Mga25vd24gdG8gYmUgZXhhY3QKICAgICAgICAgIG1hdGNoZXMuICBUaGUga3dzZXQgbWF0 Y2hlciB3aWxsIHJldHVybiB0aGUgaW5kZXgKQEAgLTEwMCw4ICs5OSw3IEBAIGt3c211c3Rz ICh2b2lkKQogICAgICAgICAgIGlmICghZG0tPmV4YWN0KQogICAgICAgICAgICAgY29udGlu dWU7CiAgICAgICAgICAgKytrd3NldF9leGFjdF9tYXRjaGVzOwotICAgICAgICAgIGlmICgo ZXJyID0ga3dzaW5jciAoa3dzZXQsIGRtLT5tdXN0LCBzdHJsZW4gKGRtLT5tdXN0KSkpICE9 IE5VTEwpCi0gICAgICAgICAgICBlcnJvciAoRVhJVF9UUk9VQkxFLCAwLCAiJXMiLCBlcnIp OworICAgICAgICAgIGt3c2luY3IgKGt3c2V0LCBkbS0+bXVzdCwgc3RybGVuIChkbS0+bXVz dCkpOwogICAgICAgICB9CiAgICAgICAvKiBOb3csIHdlIGNvbXBpbGUgdGhlIHN1YnN0cmlu Z3MgdGhhdCB3aWxsIHJlcXVpcmUKICAgICAgICAgIHRoZSB1c2Ugb2YgdGhlIHJlZ2V4cCBt YXRjaGVyLiAgKi8KQEAgLTEwOSwxMSArMTA3LDkgQEAga3dzbXVzdHMgKHZvaWQpCiAgICAg ICAgIHsKICAgICAgICAgICBpZiAoZG0tPmV4YWN0KQogICAgICAgICAgICAgY29udGludWU7 Ci0gICAgICAgICAgaWYgKChlcnIgPSBrd3NpbmNyIChrd3NldCwgZG0tPm11c3QsIHN0cmxl biAoZG0tPm11c3QpKSkgIT0gTlVMTCkKLSAgICAgICAgICAgIGVycm9yIChFWElUX1RST1VC TEUsIDAsICIlcyIsIGVycik7CisgICAgICAgICAga3dzaW5jciAoa3dzZXQsIGRtLT5tdXN0 LCBzdHJsZW4gKGRtLT5tdXN0KSk7CiAgICAgICAgIH0KLSAgICAgIGlmICgoZXJyID0ga3dz cHJlcCAoa3dzZXQpKSAhPSBOVUxMKQotICAgICAgICBlcnJvciAoRVhJVF9UUk9VQkxFLCAw LCAiJXMiLCBlcnIpOworICAgICAga3dzcHJlcCAoa3dzZXQpOwogICAgIH0KIH0KIApkaWZm IC0tZ2l0IGEvc3JjL2t3c2VhcmNoLmMgYi9zcmMva3dzZWFyY2guYwppbmRleCBkZDAxNTE4 Li5kZjk0OTUxIDEwMDY0NAotLS0gYS9zcmMva3dzZWFyY2guYworKysgYi9zcmMva3dzZWFy Y2guYwpAQCAtMzIsNyArMzIsNiBAQCBzdGF0aWMga3dzZXRfdCBrd3NldDsKIHZvaWQKIEZj b21waWxlIChjaGFyIGNvbnN0ICpwYXR0ZXJuLCBzaXplX3Qgc2l6ZSkKIHsKLSAgY2hhciBj b25zdCAqZXJyOwogICBzaXplX3QgcHNpemUgPSBzaXplOwogICBtYl9sZW5fbWFwX3QgKm1h cCA9IE5VTEw7CiAgIGNoYXIgY29uc3QgKnBhdCA9IChtYXRjaF9pY2FzZSAmJiBNQl9DVVJf TUFYID4gMQpAQCAtNjUsMTQgKzY0LDEyIEBAIEZjb21waWxlIChjaGFyIGNvbnN0ICpwYXR0 ZXJuLCBzaXplX3Qgc2l6ZSkKICNlbmRpZgogICAgICAgICB9CiAKLSAgICAgIGlmICgoZXJy ID0ga3dzaW5jciAoa3dzZXQsIGJlZywgZW5kIC0gYmVnKSkgIT0gTlVMTCkKLSAgICAgICAg ZXJyb3IgKEVYSVRfVFJPVUJMRSwgMCwgIiVzIiwgZXJyKTsKKyAgICAgIGt3c2luY3IgKGt3 c2V0LCBiZWcsIGVuZCAtIGJlZyk7CiAgICAgICBiZWcgPSBsaW07CiAgICAgfQogICB3aGls ZSAoYmVnIDwgcGF0ICsgcHNpemUpOwogCi0gIGlmICgoZXJyID0ga3dzcHJlcCAoa3dzZXQp KSAhPSBOVUxMKQotICAgIGVycm9yIChFWElUX1RST1VCTEUsIDAsICIlcyIsIGVycik7Cisg IGt3c3ByZXAgKGt3c2V0KTsKIH0KIAogLyogQXBwbHkgdGhlIE1BUCAoY3JlYXRlZCBieSBt YnRvdXBwZXIpIHRvIHRoZSB1cHBlcmNhc2UtYnVmZmVyLXJlbGF0aXZlCmRpZmYgLS1naXQg YS9zcmMva3dzZXQuYyBiL3NyYy9rd3NldC5jCmluZGV4IDZjMDcyNDkuLmQ1ZGIxMmYgMTAw NjQ0Ci0tLSBhL3NyYy9rd3NldC5jCisrKyBiL3NyYy9rd3NldC5jCkBAIC0zMiwxMSArMzIs MTQgQEAKICAgIGZhaWx1cmUgZnVuY3Rpb24gdXNlZCBiZWxvdy4gKi8KIAogI2luY2x1ZGUg PGNvbmZpZy5oPgorCisjaW5jbHVkZSAia3dzZXQuaCIKKwogI2luY2x1ZGUgPHN0ZGJvb2wu aD4KICNpbmNsdWRlIDxzeXMvdHlwZXMuaD4KICNpbmNsdWRlICJzeXN0ZW0uaCIKLSNpbmNs dWRlICJrd3NldC5oIgogI2luY2x1ZGUgIm9ic3RhY2suaCIKKyNpbmNsdWRlICJ4YWxsb2Mu aCIKIAogI2RlZmluZSBsaW5rIGt3c2V0X2xpbmsKIApAQCAtOTEsMjUgKzk0LDE1IEBAIHN0 cnVjdCBrd3NldAogfTsKIAogLyogQWxsb2NhdGUgYW5kIGluaXRpYWxpemUgYSBrZXl3b3Jk IHNldCBvYmplY3QsIHJldHVybmluZyBhbiBvcGFxdWUKLSAgIHBvaW50ZXIgdG8gaXQuICBS ZXR1cm4gTlVMTCBpZiBtZW1vcnkgaXMgbm90IGF2YWlsYWJsZS4gKi8KKyAgIHBvaW50ZXIg dG8gaXQuICAqLwoga3dzZXRfdAoga3dzYWxsb2MgKGNoYXIgY29uc3QgKnRyYW5zKQogewot ICBzdHJ1Y3Qga3dzZXQgKmt3c2V0OworICBzdHJ1Y3Qga3dzZXQgKmt3c2V0ID0geG1hbGxv YyAoc2l6ZW9mICprd3NldCk7CiAKLSAga3dzZXQgPSAoc3RydWN0IGt3c2V0ICopIG1hbGxv YyhzaXplb2YgKHN0cnVjdCBrd3NldCkpOwotICBpZiAoIWt3c2V0KQotICAgIHJldHVybiBO VUxMOwotCi0gIG9ic3RhY2tfaW5pdCgma3dzZXQtPm9ic3RhY2spOworICBvYnN0YWNrX2lu aXQgKCZrd3NldC0+b2JzdGFjayk7CiAgIGt3c2V0LT53b3JkcyA9IDA7Ci0gIGt3c2V0LT50 cmllCi0gICAgPSAoc3RydWN0IHRyaWUgKikgb2JzdGFja19hbGxvYygma3dzZXQtPm9ic3Rh Y2ssIHNpemVvZiAoc3RydWN0IHRyaWUpKTsKLSAgaWYgKCFrd3NldC0+dHJpZSkKLSAgICB7 Ci0gICAgICBrd3NmcmVlKChrd3NldF90KSBrd3NldCk7Ci0gICAgICByZXR1cm4gTlVMTDsK LSAgICB9CisgIGt3c2V0LT50cmllID0gb2JzdGFja19hbGxvYyAoJmt3c2V0LT5vYnN0YWNr LCBzaXplb2YgKmt3c2V0LT50cmllKTsKICAga3dzZXQtPnRyaWUtPmFjY2VwdGluZyA9IDA7 CiAgIGt3c2V0LT50cmllLT5saW5rcyA9IE5VTEw7CiAgIGt3c2V0LT50cmllLT5wYXJlbnQg PSBOVUxMOwpAQCAtMTIyLDE5ICsxMTUsMTcgQEAga3dzYWxsb2MgKGNoYXIgY29uc3QgKnRy YW5zKQogICBrd3NldC0+dGFyZ2V0ID0gTlVMTDsKICAga3dzZXQtPnRyYW5zID0gdHJhbnM7 CiAKLSAgcmV0dXJuIChrd3NldF90KSBrd3NldDsKKyAgcmV0dXJuIGt3c2V0OwogfQogCiAv KiBUaGlzIHVwcGVyIGJvdW5kIGlzIHZhbGlkIGZvciBDSEFSX0JJVCA+PSA0IGFuZAogICAg ZXhhY3QgZm9yIENIQVJfQklUIGluIHsgNC4uMTEsIDEzLCAxNSwgMTcsIDE5IH0uICovCiAj ZGVmaW5lIERFUFRIX1NJWkUgKENIQVJfQklUICsgQ0hBUl9CSVQvMikKIAotLyogQWRkIHRo ZSBnaXZlbiBzdHJpbmcgdG8gdGhlIGNvbnRlbnRzIG9mIHRoZSBrZXl3b3JkIHNldC4gIFJl dHVybiBOVUxMCi0gICBmb3Igc3VjY2VzcywgYW4gZXJyb3IgbWVzc2FnZSBvdGhlcndpc2Uu ICovCi1jb25zdCBjaGFyICoKLWt3c2luY3IgKGt3c2V0X3Qga3dzLCBjaGFyIGNvbnN0ICp0 ZXh0LCBzaXplX3QgbGVuKQorLyogQWRkIHRoZSBnaXZlbiBzdHJpbmcgdG8gdGhlIGNvbnRl bnRzIG9mIHRoZSBrZXl3b3JkIHNldC4gICovCit2b2lkCitrd3NpbmNyIChrd3NldF90IGt3 c2V0LCBjaGFyIGNvbnN0ICp0ZXh0LCBzaXplX3QgbGVuKQogewotICBzdHJ1Y3Qga3dzZXQg Kmt3c2V0ID0ga3dzOwogICBzdHJ1Y3QgdHJpZSAqdHJpZSA9IGt3c2V0LT50cmllOwogICBj aGFyIGNvbnN0ICp0cmFucyA9IGt3c2V0LT50cmFuczsKIApAQCAtMTcxLDE5ICsxNjIsMTAg QEAga3dzaW5jciAoa3dzZXRfdCBrd3MsIGNoYXIgY29uc3QgKnRleHQsIHNpemVfdCBsZW4p CiAgICAgICAgICBhIGxpbmsgaW4gdGhlIGN1cnJlbnQgdHJpZSBub2RlJ3MgdHJlZS4gKi8K ICAgICAgIGlmICghbGluaykKICAgICAgICAgewotICAgICAgICAgIGxpbmsgPSAoc3RydWN0 IHRyZWUgKikgb2JzdGFja19hbGxvYygma3dzZXQtPm9ic3RhY2ssCi0gICAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHNpemVvZiAoc3RydWN0IHRyZWUp KTsKLSAgICAgICAgICBpZiAoIWxpbmspCi0gICAgICAgICAgICByZXR1cm4gXygibWVtb3J5 IGV4aGF1c3RlZCIpOworICAgICAgICAgIGxpbmsgPSBvYnN0YWNrX2FsbG9jICgma3dzZXQt Pm9ic3RhY2ssIHNpemVvZiAqbGluayk7CiAgICAgICAgICAgbGluay0+bGxpbmsgPSBOVUxM OwogICAgICAgICAgIGxpbmstPnJsaW5rID0gTlVMTDsKLSAgICAgICAgICBsaW5rLT50cmll ID0gKHN0cnVjdCB0cmllICopIG9ic3RhY2tfYWxsb2MoJmt3c2V0LT5vYnN0YWNrLAotICAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBzaXpl b2YgKHN0cnVjdCB0cmllKSk7Ci0gICAgICAgICAgaWYgKCFsaW5rLT50cmllKQotICAgICAg ICAgICAgewotICAgICAgICAgICAgICBvYnN0YWNrX2ZyZWUoJmt3c2V0LT5vYnN0YWNrLCBs aW5rKTsKLSAgICAgICAgICAgICAgcmV0dXJuIF8oIm1lbW9yeSBleGhhdXN0ZWQiKTsKLSAg ICAgICAgICAgIH0KKyAgICAgICAgICBsaW5rLT50cmllID0gb2JzdGFja19hbGxvYyAoJmt3 c2V0LT5vYnN0YWNrLCBzaXplb2YgKmxpbmstPnRyaWUpOwogICAgICAgICAgIGxpbmstPnRy aWUtPmFjY2VwdGluZyA9IDA7CiAgICAgICAgICAgbGluay0+dHJpZS0+bGlua3MgPSBOVUxM OwogICAgICAgICAgIGxpbmstPnRyaWUtPnBhcmVudCA9IHRyaWU7CkBAIC0yODMsOCArMjY1 LDYgQEAga3dzaW5jciAoa3dzZXRfdCBrd3MsIGNoYXIgY29uc3QgKnRleHQsIHNpemVfdCBs ZW4pCiAgICAga3dzZXQtPm1pbmQgPSB0cmllLT5kZXB0aDsKICAgaWYgKHRyaWUtPmRlcHRo ID4ga3dzZXQtPm1heGQpCiAgICAga3dzZXQtPm1heGQgPSB0cmllLT5kZXB0aDsKLQotICBy ZXR1cm4gTlVMTDsKIH0KIAogLyogRW5xdWV1ZSB0aGUgdHJpZSBub2RlcyByZWZlcmVuY2Vk IGZyb20gdGhlIGdpdmVuIHRyZWUgaW4gdGhlCkBAIC0zODIsMTAgKzM2Miw5IEBAIHRyZWVu ZXh0IChzdHJ1Y3QgdHJlZSBjb25zdCAqdHJlZSwgc3RydWN0IHRyaWUgKm5leHRbXSkKIAog LyogQ29tcHV0ZSB0aGUgc2hpZnQgZm9yIGVhY2ggdHJpZSBub2RlLCBhcyB3ZWxsIGFzIHRo ZSBkZWx0YQogICAgdGFibGUgYW5kIG5leHQgY2FjaGUgZm9yIHRoZSBnaXZlbiBrZXl3b3Jk IHNldC4gKi8KLWNvbnN0IGNoYXIgKgota3dzcHJlcCAoa3dzZXRfdCBrd3MpCit2b2lkCitr d3NwcmVwIChrd3NldF90IGt3c2V0KQogewotICBzdHJ1Y3Qga3dzZXQgKmt3c2V0ID0ga3dz OwogICBjaGFyIGNvbnN0ICp0cmFucyA9IGt3c2V0LT50cmFuczsKICAgaW50IGk7CiAgIHVu c2lnbmVkIGNoYXIgZGVsdGFidWZbTkNIQVJdOwpAQCAtNDU4LDkgKzQzNyw3IEBAIGt3c3By ZXAgKGt3c2V0X3Qga3dzKQogICBpZiAoIXRyYW5zICYmIGt3c2V0LT53b3JkcyA9PSAxKQog ICAgIHsKICAgICAgIC8qIExvb2tpbmcgZm9yIGp1c3Qgb25lIHN0cmluZy4gIEV4dHJhY3Qg aXQgZnJvbSB0aGUgdHJpZS4gKi8KLSAgICAgIGt3c2V0LT50YXJnZXQgPSBvYnN0YWNrX2Fs bG9jKCZrd3NldC0+b2JzdGFjaywga3dzZXQtPm1pbmQpOwotICAgICAgaWYgKCFrd3NldC0+ dGFyZ2V0KQotICAgICAgICByZXR1cm4gXygibWVtb3J5IGV4aGF1c3RlZCIpOworICAgICAg a3dzZXQtPnRhcmdldCA9IG9ic3RhY2tfYWxsb2MgKCZrd3NldC0+b2JzdGFjaywga3dzZXQt Pm1pbmQpOwogICAgICAgZm9yIChpID0ga3dzZXQtPm1pbmQgLSAxLCBjdXJyID0ga3dzZXQt PnRyaWU7IGkgPj0gMDsgLS1pKQogICAgICAgICB7CiAgICAgICAgICAga3dzZXQtPnRhcmdl dFtpXSA9IGN1cnItPmxpbmtzLT5sYWJlbDsKQEAgLTQ3Myw4ICs0NTAsNiBAQCBrd3NwcmVw IChrd3NldF90IGt3cykKICAgICAgICAgICBrd3NldC0+c2hpZnQKICAgICAgICAgICAgID0g b2JzdGFja19hbGxvYyAoJmt3c2V0LT5vYnN0YWNrLAogICAgICAgICAgICAgICAgICAgICAg ICAgICAgICBzaXplb2YgKmt3c2V0LT5zaGlmdCAqIChrd3NldC0+bWluZCAtIDEpKTsKLSAg ICAgICAgICBpZiAoIWt3c2V0LT5zaGlmdCkKLSAgICAgICAgICAgIHJldHVybiBfKCJtZW1v cnkgZXhoYXVzdGVkIik7CiAgICAgICAgICAgZm9yIChpID0gMCwgY3VyciA9IGt3c2V0LT50 cmllLT5uZXh0OyBpIDwga3dzZXQtPm1pbmQgLSAxOyArK2kpCiAgICAgICAgICAgICB7CiAg ICAgICAgICAgICAgIGt3c2V0LT5zaGlmdFtpXSA9IGN1cnItPnNoaWZ0OwpAQCAtNDg3LDIy ICs0NjIsMTcgQEAga3dzcHJlcCAoa3dzZXRfdCBrd3MpCiAgIGlmICh0cmFucykKICAgICBm b3IgKGkgPSAwOyBpIDwgTkNIQVI7ICsraSkKICAgICAgIGt3c2V0LT5kZWx0YVtpXSA9IGRl bHRhW1UodHJhbnNbaV0pXTsKLQotICByZXR1cm4gTlVMTDsKIH0KIAogLyogRmFzdCBib3ll ci1tb29yZSBzZWFyY2guICovCiBzdGF0aWMgc2l6ZV90IF9HTF9BVFRSSUJVVEVfUFVSRQot Ym1leGVjIChrd3NldF90IGt3cywgY2hhciBjb25zdCAqdGV4dCwgc2l6ZV90IHNpemUpCiti bWV4ZWMgKGt3c2V0X3Qga3dzZXQsIGNoYXIgY29uc3QgKnRleHQsIHNpemVfdCBzaXplKQog ewotICBzdHJ1Y3Qga3dzZXQgY29uc3QgKmt3c2V0OwogICB1bnNpZ25lZCBjaGFyIGNvbnN0 ICpkMTsKICAgY2hhciBjb25zdCAqZXAsICpzcCwgKnRwOwotICBpbnQgZCwgaSwgbGVuLCBz a2lwOworICBpbnQgZCwgaSwgc2tpcDsKICAgY2hhciBnYzEsIGdjMjsKLQotICBrd3NldCA9 IChzdHJ1Y3Qga3dzZXQgY29uc3QgKikga3dzOwotICBsZW4gPSBrd3NldC0+bWluZDsKKyAg aW50IGxlbiA9IGt3c2V0LT5taW5kOwogCiAgIGlmIChsZW4gPT0gMCkKICAgICByZXR1cm4g MDsKQEAgLTYxOSw5ICs1ODksOCBAQCBibWV4ZWMgKGt3c2V0X3Qga3dzLCBjaGFyIGNvbnN0 ICp0ZXh0LCBzaXplX3Qgc2l6ZSkKIAogLyogSGFpcnkgbXVsdGlwbGUgc3RyaW5nIHNlYXJj aC4gKi8KIHN0YXRpYyBzaXplX3QgX0dMX0FSR19OT05OVUxMICgoNCkpCi1jd2V4ZWMgKGt3 c2V0X3Qga3dzLCBjaGFyIGNvbnN0ICp0ZXh0LCBzaXplX3QgbGVuLCBzdHJ1Y3Qga3dzbWF0 Y2ggKmt3c21hdGNoKQorY3dleGVjIChrd3NldF90IGt3c2V0LCBjaGFyIGNvbnN0ICp0ZXh0 LCBzaXplX3QgbGVuLCBzdHJ1Y3Qga3dzbWF0Y2ggKmt3c21hdGNoKQogewotICBzdHJ1Y3Qg a3dzZXQgY29uc3QgKmt3c2V0OwogICBzdHJ1Y3QgdHJpZSAqIGNvbnN0ICpuZXh0OwogICBz dHJ1Y3QgdHJpZSBjb25zdCAqdHJpZTsKICAgc3RydWN0IHRyaWUgY29uc3QgKmFjY2VwdDsK QEAgLTYzOCw3ICs2MDcsNiBAQCBjd2V4ZWMgKGt3c2V0X3Qga3dzLCBjaGFyIGNvbnN0ICp0 ZXh0LCBzaXplX3QgbGVuLCBzdHJ1Y3Qga3dzbWF0Y2ggKmt3c21hdGNoKQogI2VuZGlmCiAK ICAgLyogSW5pdGlhbGl6ZSByZWdpc3RlciBjb3BpZXMgYW5kIGxvb2sgZm9yIGVhc3kgd2F5 cyBvdXQuICovCi0gIGt3c2V0ID0gKHN0cnVjdCBrd3NldCAqKSBrd3M7CiAgIGlmIChsZW4g PCBrd3NldC0+bWluZCkKICAgICByZXR1cm4gLTE7CiAgIG5leHQgPSBrd3NldC0+bmV4dDsK QEAgLTc3NSwxOCArNzQzLDE4IEBAIGN3ZXhlYyAoa3dzZXRfdCBrd3MsIGNoYXIgY29uc3Qg KnRleHQsIHNpemVfdCBsZW4sIHN0cnVjdCBrd3NtYXRjaCAqa3dzbWF0Y2gpCiAgIHJldHVy biBtY2ggLSB0ZXh0OwogfQogCi0vKiBTZWFyY2ggVEVYVCBmb3IgYSBtYXRjaCBvZiBhbnkg bWVtYmVyIG9mIHRoZSBrZXl3b3JkIHNldCwgS1dTLgorLyogU2VhcmNoIFRFWFQgZm9yIGEg bWF0Y2ggb2YgYW55IG1lbWJlciBvZiBLV1NFVC4KICAgIFJldHVybiB0aGUgb2Zmc2V0IChp bnRvIFRFWFQpIG9mIHRoZSBmaXJzdCBieXRlIG9mIHRoZSBtYXRjaGluZyBzdWJzdHJpbmcs CiAgICBvciAoc2l6ZV90KSAtMSBpZiBubyBtYXRjaCBpcyBmb3VuZC4gIFVwb24gYSBtYXRj aCwgc3RvcmUgZGV0YWlscyBpbgogICAgKktXU01BVENIOiBpbmRleCBvZiBtYXRjaGVkIGtl eXdvcmQsIHN0YXJ0IG9mZnNldCAoc2FtZSBhcyB0aGUgcmV0dXJuCiAgICB2YWx1ZSksIGFu ZCBsZW5ndGguICAqLwogc2l6ZV90Ci1rd3NleGVjIChrd3NldF90IGt3cywgY2hhciBjb25z dCAqdGV4dCwgc2l6ZV90IHNpemUsIHN0cnVjdCBrd3NtYXRjaCAqa3dzbWF0Y2gpCitrd3Nl eGVjIChrd3NldF90IGt3c2V0LCBjaGFyIGNvbnN0ICp0ZXh0LCBzaXplX3Qgc2l6ZSwKKyAg ICAgICAgIHN0cnVjdCBrd3NtYXRjaCAqa3dzbWF0Y2gpCiB7Ci0gIHN0cnVjdCBrd3NldCBj b25zdCAqa3dzZXQgPSAoc3RydWN0IGt3c2V0ICopIGt3czsKICAgaWYgKGt3c2V0LT53b3Jk cyA9PSAxICYmIGt3c2V0LT50cmFucyA9PSBOVUxMKQogICAgIHsKLSAgICAgIHNpemVfdCBy ZXQgPSBibWV4ZWMgKGt3cywgdGV4dCwgc2l6ZSk7CisgICAgICBzaXplX3QgcmV0ID0gYm1l eGVjIChrd3NldCwgdGV4dCwgc2l6ZSk7CiAgICAgICBpZiAocmV0ICE9IChzaXplX3QpIC0x KQogICAgICAgICB7CiAgICAgICAgICAga3dzbWF0Y2gtPmluZGV4ID0gMDsKQEAgLTc5Niwx NiArNzY0LDEzIEBAIGt3c2V4ZWMgKGt3c2V0X3Qga3dzLCBjaGFyIGNvbnN0ICp0ZXh0LCBz aXplX3Qgc2l6ZSwgc3RydWN0IGt3c21hdGNoICprd3NtYXRjaCkKICAgICAgIHJldHVybiBy ZXQ7CiAgICAgfQogICBlbHNlCi0gICAgcmV0dXJuIGN3ZXhlYyhrd3MsIHRleHQsIHNpemUs IGt3c21hdGNoKTsKKyAgICByZXR1cm4gY3dleGVjIChrd3NldCwgdGV4dCwgc2l6ZSwga3dz bWF0Y2gpOwogfQogCiAvKiBGcmVlIHRoZSBjb21wb25lbnRzIG9mIHRoZSBnaXZlbiBrZXl3 b3JkIHNldC4gKi8KIHZvaWQKLWt3c2ZyZWUgKGt3c2V0X3Qga3dzKQora3dzZnJlZSAoa3dz ZXRfdCBrd3NldCkKIHsKLSAgc3RydWN0IGt3c2V0ICprd3NldDsKLQotICBrd3NldCA9IChz dHJ1Y3Qga3dzZXQgKikga3dzOwotICBvYnN0YWNrX2ZyZWUoJmt3c2V0LT5vYnN0YWNrLCBO VUxMKTsKLSAgZnJlZShrd3MpOworICBvYnN0YWNrX2ZyZWUgKCZrd3NldC0+b2JzdGFjaywg TlVMTCk7CisgIGZyZWUgKGt3c2V0KTsKIH0KZGlmZiAtLWdpdCBhL3NyYy9rd3NldC5oIGIv c3JjL2t3c2V0LmgKaW5kZXggMmQzY2RkOS4uMTJhZmI4ZSAxMDA2NDQKLS0tIGEvc3JjL2t3 c2V0LmgKKysrIGIvc3JjL2t3c2V0LmgKQEAgLTIxLDYgKzIxLDggQEAKICAgIFRoZSBhdXRo b3IgbWF5IGJlIHJlYWNoZWQgKEVtYWlsKSBhdCB0aGUgYWRkcmVzcyBtaWtlQGFpLm1pdC5l ZHUsCiAgICBvciAoVVMgbWFpbCkgYXMgTWlrZSBIYWVydGVsIGMvbyBGcmVlIFNvZnR3YXJl IEZvdW5kYXRpb24uICovCiAKKyNpbmNsdWRlIDxzdGRkZWYuaD4KKwogc3RydWN0IGt3c21h dGNoCiB7CiAgIHNpemVfdCBpbmRleDsJCQkvKiBJbmRleCBudW1iZXIgb2YgbWF0Y2hpbmcg a2V5d29yZC4gKi8KQEAgLTMzLDIwICszNSwxNyBAQCBzdHJ1Y3Qga3dzbWF0Y2gKIHN0cnVj dCBrd3NldDsKIHR5cGVkZWYgc3RydWN0IGt3c2V0ICprd3NldF90OwogCi0vKiBSZXR1cm4g YW4gb3BhcXVlIHBvaW50ZXIgdG8gYSBuZXdseSBhbGxvY2F0ZWQga2V5d29yZCBzZXQsIG9y IE5VTEwKLSAgIGlmIGVub3VnaCBtZW1vcnkgY2Fubm90IGJlIG9idGFpbmVkLiAgVGhlIGFy Z3VtZW50IGlmIG5vbi1OVUxMCisvKiBSZXR1cm4gYW4gb3BhcXVlIHBvaW50ZXIgdG8gYSBu ZXdseSBhbGxvY2F0ZWQga2V5d29yZCBzZXQuICBBIG5vbm51bGwgYXJnCiAgICBzcGVjaWZp ZXMgYSB0YWJsZSBvZiBjaGFyYWN0ZXIgdHJhbnNsYXRpb25zIHRvIGJlIGFwcGxpZWQgdG8g YWxsCi0gICBwYXR0ZXJuIGFuZCBzZWFyY2ggdGV4dC4gKi8KKyAgIHBhdHRlcm4gYW5kIHNl YXJjaCB0ZXh0LiAgKi8KIGV4dGVybiBrd3NldF90IGt3c2FsbG9jIChjaGFyIGNvbnN0ICop OwogCiAvKiBJbmNyZW1lbnRhbGx5IGV4dGVuZCB0aGUga2V5d29yZCBzZXQgdG8gaW5jbHVk ZSB0aGUgZ2l2ZW4gc3RyaW5nLgotICAgUmV0dXJuIE5VTEwgZm9yIHN1Y2Nlc3MsIG9yIGFu IGVycm9yIG1lc3NhZ2UuICBSZW1lbWJlciBhbiBpbmRleAotICAgbnVtYmVyIGZvciBlYWNo IGtleXdvcmQgaW5jbHVkZWQgaW4gdGhlIHNldC4gKi8KLWV4dGVybiBjb25zdCBjaGFyICpr d3NpbmNyIChrd3NldF90LCBjaGFyIGNvbnN0ICosIHNpemVfdCk7CisgICBSZW1lbWJlciBh biBpbmRleCBudW1iZXIgZm9yIGVhY2gga2V5d29yZCBpbmNsdWRlZCBpbiB0aGUgc2V0LiAg Ki8KK2V4dGVybiB2b2lkIGt3c2luY3IgKGt3c2V0X3QsIGNoYXIgY29uc3QgKiwgc2l6ZV90 KTsKIAotLyogV2hlbiB0aGUga2V5d29yZCBzZXQgaGFzIGJlZW4gY29tcGxldGVseSBidWls dCwgcHJlcGFyZSBpdCBmb3IKLSAgIHVzZS4gIFJldHVybiBOVUxMIGZvciBzdWNjZXNzLCBv ciBhbiBlcnJvciBtZXNzYWdlLiAqLwotZXh0ZXJuIGNvbnN0IGNoYXIgKmt3c3ByZXAgKGt3 c2V0X3QpOworLyogV2hlbiB0aGUga2V5d29yZCBzZXQgaGFzIGJlZW4gY29tcGxldGVseSBi dWlsdCwgcHJlcGFyZSBpdCBmb3IgdXNlLiAgKi8KK2V4dGVybiB2b2lkIGt3c3ByZXAgKGt3 c2V0X3QpOwogCiAvKiBTZWFyY2ggdGhyb3VnaCB0aGUgZ2l2ZW4gYnVmZmVyIGZvciBhIG1l bWJlciBvZiB0aGUga2V5d29yZCBzZXQuCiAgICBSZXR1cm4gYSBwb2ludGVyIHRvIHRoZSBs ZWZ0bW9zdCBsb25nZXN0IG1hdGNoIGZvdW5kLCBvciBOVUxMIGlmCi0tIAoxLjkuMAoK --------------090507030209050109000008-- ------------=_1396925823-25530-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at submit) by debbugs.gnu.org; 14 Mar 2014 12:21:38 +0000 Received: from localhost ([127.0.0.1]:36537 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WOR7J-00073z-VR for submit@debbugs.gnu.org; Fri, 14 Mar 2014 08:21:38 -0400 Received: from pbsg501.nifty.com ([202.248.238.71]:51774) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WOR7F-00073k-AY for submit@debbugs.gnu.org; Fri, 14 Mar 2014 08:21:36 -0400 Received: from [10.120.1.51] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) (authenticated) by pbsg501.nifty.com with ESMTP id s2ECLJmt024841 for ; Fri, 14 Mar 2014 21:21:20 +0900 X-Nifty-SrcIP: [118.21.128.66] Date: Fri, 14 Mar 2014 21:21:21 +0900 From: Norihiro Tanaka To: submit@debbugs.gnu.org Subject: [PATCH] grep: optimization by using the Galil rule for Boyer-Moore algorithm in KWSet Message-Id: <20140314212120.7E5E.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_531AAC47000000000212_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.64.06 [ja] X-Spam-Score: 1.2 (+) X-Spam-Report: Spam detection software, running on the system "debbugs.gnu.org", has identified this incoming email as possible spam. The original message has been attached to this so you can view it (if it isn't spam) or label similar future email. If you have any questions, see the administrator of that system for details. Content preview: Package: grep Tags: patch The Boyer-Moore algorithm runs in O(m n) in the worst case, which perhaps it may be much slower than the DFA. The Galil rule enables to change O(m n) into O(n) for its case without overheads and/or slow-down for other cases by avoiding to compare more than once for a position in the text. This patch implements it. [...] Content analysis details: (1.2 points, 10.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- 1.2 RCVD_IN_BL_SPAMCOP_NET RBL: Received via a relay in bl.spamcop.net [Blocked - see ] -0.0 SPF_HELO_PASS SPF: HELO matches SPF record -0.0 T_RP_MATCHES_RCVD Envelope sender domain matches handover relay domain -0.0 SPF_PASS SPF: sender matches SPF record X-Debbugs-Envelope-To: submit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 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.2 (+) X-Spam-Report: Spam detection software, running on the system "debbugs.gnu.org", has identified this incoming email as possible spam. The original message has been attached to this so you can view it (if it isn't spam) or label similar future email. If you have any questions, see the administrator of that system for details. Content preview: Package: grep Tags: patch The Boyer-Moore algorithm runs in O(m n) in the worst case, which perhaps it may be much slower than the DFA. The Galil rule enables to change O(m n) into O(n) for its case without overheads and/or slow-down for other cases by avoiding to compare more than once for a position in the text. This patch implements it. [...] Content analysis details: (1.2 points, 10.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- 1.2 RCVD_IN_BL_SPAMCOP_NET RBL: Received via a relay in bl.spamcop.net [Blocked - see ] -0.0 SPF_HELO_PASS SPF: HELO matches SPF record -0.0 T_RP_MATCHES_RCVD Envelope sender domain matches handover relay domain -0.0 SPF_PASS SPF: sender matches SPF record --------_531AAC47000000000212_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit Package: grep Tags: patch The Boyer-Moore algorithm runs in O(m n) in the worst case, which perhaps it may be much slower than the DFA. The Galil rule enables to change O(m n) into O(n) for its case without overheads and/or slow-down for other cases by avoiding to compare more than once for a position in the text. This patch implements it. I prepare following string, which makes a worst case for Boyer-Moore algorithm, to measure the performance. yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 > ../k I run the test with the patch (best-of-5 trials): env LC_ALL=C time -p src/grep kjjjjjjjjjjjjjjjjjjj k real 0.70 user 0.32 sys 0.38 Back out that commit (temporarily), recompile, and rerun the experiment: env LC_ALL=C time -p src/grep kjjjjjjjjjjjjjjjjjjj k real 3.97 user 3.56 sys 0.40 Norihiro --------_531AAC47000000000212_MULTIPART_MIXED_ Content-Type: application/octet-stream; name="grep.patch" Content-Disposition: attachment; filename="grep.patch" Content-Transfer-Encoding: base64 RnJvbSBlNTA2OTM3ZGZmNWViYjk3Njk4NmEyN2Q4Y2I4NGE2OGQ0MWNlM2E1IE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBOb3JpaGlybyBUYW5ha2EgPG5vcml0bmtAa2NuLm5lLmpwPgpE YXRlOiBGcmksIDE0IE1hciAyMDE0IDIxOjEzOjU3ICswOTAwClN1YmplY3Q6IFtQQVRDSF0gZ3Jl cDogb3B0aW1pemF0aW9uIGJ5IHVzaW5nIHRoZSBHYWxpbCBydWxlIGZvciBCb3llci1Nb29yZQog YWxnb3JpdGhtIGluIEtXU2V0CgpUaGUgQm95ZXItTW9vcmUgYWxnb3JpdGhtIHJ1bnMgaW4gTyht IG4pIGluIHRoZSB3b3JzdCBjYXNlLAogd2hpY2ggcGVyaGFwcyBpdCBtYXkgYmUgbXVjaCBzbG93 ZXIgdGhhbiB0aGUgREZBLgoKVGhlIEdhbGlsIHJ1bGUgZW5hYmxlcyB0byBjaGFuZ2UgTyhtIG4p IGludG8gTyhuKSBmb3IgaXRzIGNhc2Ugd2l0aG91dApvdmVyaGVhZHMgYW5kL29yIHNsb3ctZG93 biBmb3Igb3RoZXIgY2FzZXMgYnkgYXZvaWRpbmcgdG8gY29tcGFyZSBtb3JlCnRoYW4gb25jZSBm b3IgYSBwb3NpdGlvbiBpbiB0aGUgdGV4dC4gIFRoaXMgcGF0Y2ggaW1wbGVtZW50cyBpdC4KCkkg cHJlcGFyZSBmb2xsb3dpbmcgc3RyaW5nLCB3aGljaCBtYWtlcyBhIHdvcnN0IGNhc2UgZm9yIEJv eWVyLU1vb3JlCmFsZ29yaXRobSwgdG8gbWVhc3VyZSB0aGUgcGVyZm9ybWFuY2UuCgogICAgeWVz IGpqampqampqampqampqampqampqampqampqampqampqampqampqamogfCBoZWFkIC0xMDAwMDAw MCA+IC4uL2sKCkkgcnVuIHRoZSB0ZXN0IHdpdGggdGhlIHBhdGNoIChiZXN0LW9mLTUgdHJpYWxz KToKCiAgICBlbnYgTENfQUxMPUMgdGltZSAtcCBzcmMvZ3JlcCBrampqampqampqampqampqampq aiBrCiAgICAgICAgcmVhbCAwLjcwICAgICAgIHVzZXIgMC4zMiAgICAgICBzeXMgMC4zOAoKQmFj ayBvdXQgdGhhdCBjb21taXQgKHRlbXBvcmFyaWx5KSwgcmVjb21waWxlLCBhbmQgcmVydW4gdGhl IGV4cGVyaW1lbnQ6CgogICAgZW52IExDX0FMTD1DIHRpbWUgLXAgc3JjL2dyZXAga2pqampqampq ampqampqampqamogawogICAgICAgIHJlYWwgMy45NyAgICAgICB1c2VyIDMuNTYgICAgICAgc3lz IDAuNDAKCiogc3JjL2t3c2V0LmMgKHN0cnVjdCBrd3NldCk6IFJlcGxhY2UgbWVtYmVyIGBtaW5k MicgdG8gYHNoaWZ0Jy4KKGt3c3ByZXApOiBDYWxjdWxhdGUgc2hpZnQgdmFsdWVzIGF0IHRoZSBm YWlsIGF0IGVhY2ggcG9zaXRpb24uCihibWV4ZWMpOiBVc2UgaXQuCi0tLQogc3JjL2t3c2V0LmMg fCA5MyArKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrLS0tLS0t LS0tLS0tLS0tCiAxIGZpbGUgY2hhbmdlZCwgNzAgaW5zZXJ0aW9ucygrKSwgMjMgZGVsZXRpb25z KC0pCgpkaWZmIC0tZ2l0IGEvc3JjL2t3c2V0LmMgYi9zcmMva3dzZXQuYwppbmRleCA0MTBlMDQ2 Li45MDZkYjAxIDEwMDY0NAotLS0gYS9zcmMva3dzZXQuYworKysgYi9zcmMva3dzZXQuYwpAQCAt ODMsNyArODMsNyBAQCBzdHJ1Y3Qga3dzZXQKICAgdW5zaWduZWQgY2hhciBkZWx0YVtOQ0hBUl07 CS8qIERlbHRhIHRhYmxlIGZvciByYXBpZCBzZWFyY2guICovCiAgIHN0cnVjdCB0cmllICpuZXh0 W05DSEFSXTsJLyogVGFibGUgb2YgY2hpbGRyZW4gb2YgdGhlIHJvb3QuICovCiAgIGNoYXIgKnRh cmdldDsJCQkvKiBUYXJnZXQgc3RyaW5nIGlmIHRoZXJlJ3Mgb25seSBvbmUuICovCi0gIGludCBt aW5kMjsJCQkvKiBVc2VkIGluIEJveWVyLU1vb3JlIHNlYXJjaCBmb3Igb25lIHN0cmluZy4gKi8K KyAgaW50ICpzaGlmdDsJCQkvKiBVc2VkIGluIEJveWVyLU1vb3JlIHNlYXJjaCBmb3Igb25lIHN0 cmluZy4gKi8KICAgY2hhciBjb25zdCAqdHJhbnM7CQkvKiBDaGFyYWN0ZXIgdHJhbnNsYXRpb24g dGFibGUuICovCiB9OwogCkBAIC0zODUsNyArMzg1LDcgQEAgY29uc3QgY2hhciAqCiBrd3NwcmVw IChrd3NldF90IGt3cykKIHsKICAgc3RydWN0IGt3c2V0ICprd3NldDsKLSAgaW50IGk7CisgIGlu dCBpLCBqOwogICBzdHJ1Y3QgdHJpZSAqY3VycjsKICAgY2hhciBjb25zdCAqdHJhbnM7CiAgIHVu c2lnbmVkIGNoYXIgZGVsdGFbTkNIQVJdOwpAQCAtNDAxLDggKzQwMSw2IEBAIGt3c3ByZXAgKGt3 c2V0X3Qga3dzKQogICAgICBvZiB0aGUgaGFpcnkgY29tbWVudHotd2FsdGVyIGFsZ29yaXRobS4g Ki8KICAgaWYgKGt3c2V0LT53b3JkcyA9PSAxICYmIGt3c2V0LT50cmFucyA9PSBOVUxMKQogICAg IHsKLSAgICAgIGNoYXIgYzsKLQogICAgICAgLyogTG9va2luZyBmb3IganVzdCBvbmUgc3RyaW5n LiAgRXh0cmFjdCBpdCBmcm9tIHRoZSB0cmllLiAqLwogICAgICAga3dzZXQtPnRhcmdldCA9IG9i c3RhY2tfYWxsb2MoJmt3c2V0LT5vYnN0YWNrLCBrd3NldC0+bWluZCk7CiAgICAgICBpZiAoIWt3 c2V0LT50YXJnZXQpCkBAIC00MTcsMTEgKzQxNSwyMyBAQCBrd3NwcmVwIChrd3NldF90IGt3cykK ICAgICAgICAgZGVsdGFbVShrd3NldC0+dGFyZ2V0W2ldKV0gPSBrd3NldC0+bWluZCAtIChpICsg MSk7CiAgICAgICAvKiBGaW5kIHRoZSBtaW5pbWFsIGRlbHRhMiBzaGlmdCB0aGF0IHdlIG1pZ2h0 IG1ha2UgYWZ0ZXIKICAgICAgICAgIGEgYmFja3dhcmRzIG1hdGNoIGhhcyBmYWlsZWQuICovCi0g ICAgICBjID0ga3dzZXQtPnRhcmdldFtrd3NldC0+bWluZCAtIDFdOwotICAgICAgZm9yIChpID0g a3dzZXQtPm1pbmQgLSAyOyBpID49IDA7IC0taSkKLSAgICAgICAgaWYgKGt3c2V0LT50YXJnZXRb aV0gPT0gYykKLSAgICAgICAgICBicmVhazsKLSAgICAgIGt3c2V0LT5taW5kMiA9IGt3c2V0LT5t aW5kIC0gKGkgKyAxKTsKKyAgICAgIGt3c2V0LT5zaGlmdCA9IChpbnQgKikgb2JzdGFja19hbGxv Yygma3dzZXQtPm9ic3RhY2ssCisgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgc2l6ZW9mICgqa3dzZXQtPnNoaWZ0KSAqIChrd3NldC0+bWluZCAtIDEpKTsKKyAgICAg IGZvciAoaSA9IDE7IGkgPCBrd3NldC0+bWluZDsgKytpKQorICAgICAgIHsKKyAgICAgICAgIGZv ciAoaiA9IGkgKyAxOyBqIDw9IGt3c2V0LT5taW5kOyArK2opCisgICAgICAgICAgIGlmIChtZW1j bXAgKGt3c2V0LT50YXJnZXQgKyBrd3NldC0+bWluZCAtIGosIGt3c2V0LT50YXJnZXQgKyBrd3Nl dC0+bWluZCAtIGksIGkpID09IDApCisgICAgICAgICAgICAgYnJlYWs7CisgICAgICAgICBpZiAo aiA8PSBrd3NldC0+bWluZCkKKyAgICAgICAgICAga3dzZXQtPnNoaWZ0W2kgLSAxXSA9IGogLSBp OworICAgICAgICAgZWxzZQorICAgICAgICAgICB7CisgICAgICAgICAgICAgZm9yIChqID0gaSAt IDE7IGogPj0gMTsgLS1qKQorICAgICAgICAgICAgICAgaWYgKG1lbWNtcCAoa3dzZXQtPnRhcmdl dCwga3dzZXQtPnRhcmdldCArIGt3c2V0LT5taW5kIC0gaiwgaikgPT0gMCkKKyAgICAgICAgICAg ICAgICAgYnJlYWs7CisgICAgICAgICAgICAga3dzZXQtPnNoaWZ0W2kgLSAxXSA9IGt3c2V0LT5t aW5kIC0gajsKKyAgICAgICAgICAgfQorICAgICAgIH0KICAgICB9CiAgIGVsc2UKICAgICB7CkBA IC01MDMsNyArNTEzLDcgQEAgYm1leGVjIChrd3NldF90IGt3cywgY2hhciBjb25zdCAqdGV4dCwg c2l6ZV90IHNpemUpCiAgIHN0cnVjdCBrd3NldCBjb25zdCAqa3dzZXQ7CiAgIHVuc2lnbmVkIGNo YXIgY29uc3QgKmQxOwogICBjaGFyIGNvbnN0ICplcCwgKnNwLCAqdHA7Ci0gIGludCBkLCBnYywg aSwgbGVuLCBtZDI7CisgIGludCBkLCBnYywgaSwgaiwgbGVuOwogCiAgIGt3c2V0ID0gKHN0cnVj dCBrd3NldCBjb25zdCAqKSBrd3M7CiAgIGxlbiA9IGt3c2V0LT5taW5kOwpAQCAtNTIxLDcgKzUz MSw2IEBAIGJtZXhlYyAoa3dzZXRfdCBrd3MsIGNoYXIgY29uc3QgKnRleHQsIHNpemVfdCBzaXpl KQogICBkMSA9IGt3c2V0LT5kZWx0YTsKICAgc3AgPSBrd3NldC0+dGFyZ2V0ICsgbGVuOwogICBn YyA9IFUoc3BbLTJdKTsKLSAgbWQyID0ga3dzZXQtPm1pbmQyOwogICB0cCA9IHRleHQgKyBsZW47 CiAKICAgLyogU2lnbmlmaWNhbmNlIG9mIDEyOiAxIChpbml0aWFsIG9mZnNldCkgKyAxMCAoc2tp cCBsb29wKSArIDEgKG1kMikuICovCkBAIC01NTAsMTQgKzU1OSwzMyBAQCBibWV4ZWMgKGt3c2V0 X3Qga3dzLCBjaGFyIGNvbnN0ICp0ZXh0LCBzaXplX3Qgc2l6ZSkKICAgICAgICAgICB9CiAgICAg ICAgIGJyZWFrOwogICAgICAgZm91bmQ6Ci0gICAgICAgIGlmIChVKHRwWy0yXSkgPT0gZ2MpCisg ICAgICAgIGogPSAzOworICAgICAgICB3aGlsZSAoMSkKICAgICAgICAgICB7Ci0gICAgICAgICAg ICBmb3IgKGkgPSAzOyBpIDw9IGxlbiAmJiBVKHRwWy1pXSkgPT0gVShzcFstaV0pOyArK2kpCi0g ICAgICAgICAgICAgIDsKLSAgICAgICAgICAgIGlmIChpID4gbGVuKQotICAgICAgICAgICAgICBy ZXR1cm4gdHAgLSBsZW4gLSB0ZXh0OworICAgICAgICAgICAgaWYgKFUodHBbLTJdKSA9PSBnYykK KyAgICAgICAgICAgICAgeworICAgICAgICAgICAgICAgIGZvciAoaSA9IDM7IGkgPD0gZCAmJiB0 cFstaV0gPT0gc3BbLWldOyArK2kpCisgICAgICAgICAgICAgICAgICA7CisgICAgICAgICAgICAg ICAgaWYgKGkgPiBkKQorICAgICAgICAgICAgICAgICAgeworICAgICAgICAgICAgICAgICAgICBm b3IgKGkgPSBqOyBpIDw9IGxlbiAmJiB0cFstaV0gPT0gc3BbLWldOyArK2kpCisgICAgICAgICAg ICAgICAgICAgICAgOworICAgICAgICAgICAgICAgICAgICBpZiAoaSA+IGxlbikKKyAgICAgICAg ICAgICAgICAgICAgICByZXR1cm4gdHAgLSBsZW4gLSB0ZXh0OworICAgICAgICAgICAgICAgICAg fQorICAgICAgICAgICAgICAgIGQgPSBrd3NldC0+c2hpZnRbaSAtIDJdOyB0cCArPSBkOworICAg ICAgICAgICAgICAgIGlmICh0cCA+IGVwIHx8IHRwWy0xXSAhPSBzcFstMV0pCisgICAgICAgICAg ICAgICAgICBicmVhazsKKyAgICAgICAgICAgICAgICBqID0gZCArIGk7CisgICAgICAgICAgICAg IH0KKyAgICAgICAgICAgIGVsc2UKKyAgICAgICAgICAgICAgeworICAgICAgICAgICAgICAgIGQg PSBrd3NldC0+c2hpZnRbMF07IHRwICs9IGQ7CisgICAgICAgICAgICAgICAgaWYgKHRwID4gZXAg fHwgdHBbLTFdICE9IHNwWy0xXSkKKyAgICAgICAgICAgICAgICAgIGJyZWFrOworICAgICAgICAg ICAgICAgIGogPSBkICsgMjsKKyAgICAgICAgICAgICAgfQogICAgICAgICAgIH0KLSAgICAgICAg dHAgKz0gbWQyOwogICAgICAgfQogCiAgIC8qIE5vdyB3ZSBoYXZlIG9ubHkgYSBmZXcgY2hhcmFj dGVycyBsZWZ0IHRvIHNlYXJjaC4gIFdlCkBAIC01NjksMTQgKzU5NywzMyBAQCBibWV4ZWMgKGt3 c2V0X3Qga3dzLCBjaGFyIGNvbnN0ICp0ZXh0LCBzaXplX3Qgc2l6ZSkKICAgICAgIGQgPSBkMVtV KCh0cCArPSBkKVstMV0pXTsKICAgICAgIGlmIChkICE9IDApCiAgICAgICAgIGNvbnRpbnVlOwot ICAgICAgaWYgKFUodHBbLTJdKSA9PSBnYykKKyAgICAgIGogPSAzOworICAgICAgd2hpbGUgKDEp CiAgICAgICAgIHsKLSAgICAgICAgICBmb3IgKGkgPSAzOyBpIDw9IGxlbiAmJiBVKHRwWy1pXSkg PT0gVShzcFstaV0pOyArK2kpCi0gICAgICAgICAgICA7Ci0gICAgICAgICAgaWYgKGkgPiBsZW4p Ci0gICAgICAgICAgICByZXR1cm4gdHAgLSBsZW4gLSB0ZXh0OworICAgICAgICAgIGlmIChVKHRw Wy0yXSkgPT0gZ2MpCisgICAgICAgICAgICB7CisgICAgICAgICAgICAgIGZvciAoaSA9IDM7IGkg PD0gZCAmJiB0cFstaV0gPT0gc3BbLWldOyArK2kpCisgICAgICAgICAgICAgICAgOworICAgICAg ICAgICAgICBpZiAoaSA+IGQpCisgICAgICAgICAgICAgICAgeworICAgICAgICAgICAgICAgICAg Zm9yIChpID0gajsgaSA8PSBsZW4gJiYgdHBbLWldID09IHNwWy1pXTsgKytpKQorICAgICAgICAg ICAgICAgICAgICA7CisgICAgICAgICAgICAgICAgICBpZiAoaSA+IGxlbikKKyAgICAgICAgICAg ICAgICAgICAgcmV0dXJuIHRwIC0gbGVuIC0gdGV4dDsKKyAgICAgICAgICAgICAgICB9CisgICAg ICAgICAgICAgIGQgPSBrd3NldC0+c2hpZnRbaSAtIDJdOyB0cCArPSBkOworICAgICAgICAgICAg ICBpZiAodHAgPiBlcCB8fCB0cFstMV0gIT0gc3BbLTFdKQorICAgICAgICAgICAgICAgIGJyZWFr OworICAgICAgICAgICAgICBqID0gZCArIGk7CisgICAgICAgICAgICB9CisgICAgICAgICAgZWxz ZQorICAgICAgICAgICAgeworICAgICAgICAgICAgICBkID0ga3dzZXQtPnNoaWZ0WzBdOyB0cCAr PSBkOworICAgICAgICAgICAgICBpZiAodHAgPiBlcCB8fCB0cFstMV0gIT0gc3BbLTFdKQorICAg ICAgICAgICAgICAgIGJyZWFrOworICAgICAgICAgICAgICBqID0gZCArIDI7CisgICAgICAgICAg ICB9CiAgICAgICAgIH0KLSAgICAgIGQgPSBtZDI7CiAgICAgfQogCiAgIHJldHVybiAtMTsKLS0g CjEuOS4wCgo= --------_531AAC47000000000212_MULTIPART_MIXED_-- ------------=_1396925823-25530-1--