From unknown Tue Sep 09 13:20:26 2025 X-Loop: help-debbugs@gnu.org Subject: bug#17230: [PATCH 1/2] grep: may also use Boyer-Moore algorithm for case-insensitive matching Resent-From: Norihiro Tanaka Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Wed, 09 Apr 2014 13:56:07 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 17230 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: 17230@debbugs.gnu.org X-Debbugs-Original-To: bug-grep@gnu.org Received: via spool by submit@debbugs.gnu.org id=B.139705173110385 (code B ref -1); Wed, 09 Apr 2014 13:56:07 +0000 Received: (at submit) by debbugs.gnu.org; 9 Apr 2014 13:55:31 +0000 Received: from localhost ([127.0.0.1]:38698 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WXsyQ-0002hL-30 for submit@debbugs.gnu.org; Wed, 09 Apr 2014 09:55:30 -0400 Received: from eggs.gnu.org ([208.118.235.92]:45969) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WXsyL-0002gn-HL for submit@debbugs.gnu.org; Wed, 09 Apr 2014 09:55:26 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WXsy9-0006Tk-5F for submit@debbugs.gnu.org; Wed, 09 Apr 2014 09:55:20 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=0.8 required=5.0 tests=BAYES_50 autolearn=disabled version=3.3.2 Received: from lists.gnu.org ([2001:4830:134:3::11]:44946) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WXsy9-0006Tg-24 for submit@debbugs.gnu.org; Wed, 09 Apr 2014 09:55:13 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:47656) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WXsy2-0000da-Nu for bug-grep@gnu.org; Wed, 09 Apr 2014 09:55:13 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WXsxr-00067q-PK for bug-grep@gnu.org; Wed, 09 Apr 2014 09:55:06 -0400 Received: from pbsg500.nifty.com ([202.248.238.70]:34750) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WXsxr-00066V-4Q for bug-grep@gnu.org; Wed, 09 Apr 2014 09:54:55 -0400 Received: from [10.120.1.47] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) (authenticated) by pbsg500.nifty.com with ESMTP id s39DsdDS017046 for ; Wed, 9 Apr 2014 22:54:41 +0900 X-Nifty-SrcIP: [118.21.128.66] Date: Wed, 09 Apr 2014 22:54:42 +0900 From: Norihiro Tanaka Message-Id: <20140409225440.785F.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_5343FA290000000010DE_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.4.x X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2001:4830:134:3::11 X-Spam-Score: -4.0 (----) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.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: -4.0 (----) --------_5343FA290000000010DE_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit Boyer-Moore algorithm is faster than Beate Commentz-Walter, in especially worst case, because Galil rule is applicable only for Boyer-Moore algorithm. This patch enables to use Boyer-Moore algorithm for case-insensitive matching. Norihiro --------_5343FA290000000010DE_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII"; name="patch.txt" Content-Disposition: attachment; filename="patch.txt" Content-Transfer-Encoding: base64 RnJvbSAwNjlkNTU3MDU5NzNkZGVjYmQ1ZjA0YTQxMDk3ODkzMjI0ZDU1MDk1IE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBOb3JpaGlybyBUYW5ha2EgPG5vcml0bmtAa2NuLm5lLmpwPgpE YXRlOiBUaHUsIDIwIE1hciAyMDE0IDA4OjA3OjI1ICswOTAwClN1YmplY3Q6IFtQQVRDSCAxLzJd IGdyZXA6IG1heSBhbHNvIHVzZSBCb3llci1Nb29yZSBhbGdvcml0aG0gZm9yCiBjYXNlLWluc2Vu c2l0aXZlIG1hdGNoaW5nCgoqIHNyYy9rd3NldC5jIChibWV4ZWMpOiBVc2UgY2hhcmFjdGVyIHRy YW5zbGF0aW9uIHRhYmxlLgooa3dzZXhlYyk6IENhbGwgYm1leGVjIGZvciBjYXNlLWluc2Vuc2l0 aXZlIG1hdGNoaW5nLgooa3dzcHJlcCk6IENoYW5nZSB0aGUgYGlmJyBjb25kaXRpb24uCi0tLQog c3JjL2t3c2V0LmMgfCAyMTUgKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysr KysrKysrKysrLS0tLS0tLS0tLS0tCiAxIGZpbGUgY2hhbmdlZCwgMTczIGluc2VydGlvbnMoKyks IDQyIGRlbGV0aW9ucygtKQoKZGlmZiAtLWdpdCBhL3NyYy9rd3NldC5jIGIvc3JjL2t3c2V0LmMK aW5kZXggZDVkYjEyZi4uOGQ4YWEwNyAxMDA2NDQKLS0tIGEvc3JjL2t3c2V0LmMKKysrIGIvc3Jj L2t3c2V0LmMKQEAgLTQzNCw3ICs0MzQsNyBAQCBrd3NwcmVwIChrd3NldF90IGt3c2V0KQogCiAg IC8qIENoZWNrIGlmIHdlIGNhbiB1c2UgdGhlIHNpbXBsZSBib3llci1tb29yZSBhbGdvcml0aG0s IGluc3RlYWQKICAgICAgb2YgdGhlIGhhaXJ5IGNvbW1lbnR6LXdhbHRlciBhbGdvcml0aG0uICov Ci0gIGlmICghdHJhbnMgJiYga3dzZXQtPndvcmRzID09IDEpCisgIGlmIChrd3NldC0+d29yZHMg PT0gMSkKICAgICB7CiAgICAgICAvKiBMb29raW5nIGZvciBqdXN0IG9uZSBzdHJpbmcuICBFeHRy YWN0IGl0IGZyb20gdGhlIHRyaWUuICovCiAgICAgICBrd3NldC0+dGFyZ2V0ID0gb2JzdGFja19h bGxvYyAoJmt3c2V0LT5vYnN0YWNrLCBrd3NldC0+bWluZCk7CkBAIC00NzMsNiArNDczLDcgQEAg Ym1leGVjIChrd3NldF90IGt3c2V0LCBjaGFyIGNvbnN0ICp0ZXh0LCBzaXplX3Qgc2l6ZSkKICAg aW50IGQsIGksIHNraXA7CiAgIGNoYXIgZ2MxLCBnYzI7CiAgIGludCBsZW4gPSBrd3NldC0+bWlu ZDsKKyAgY2hhciBjb25zdCAqdHJhbnMgPSBrd3NldC0+dHJhbnM7CiAKICAgaWYgKGxlbiA9PSAw KQogICAgIHJldHVybiAwOwpAQCAtNDgwLDE1ICs0ODEsMzMgQEAgYm1leGVjIChrd3NldF90IGt3 c2V0LCBjaGFyIGNvbnN0ICp0ZXh0LCBzaXplX3Qgc2l6ZSkKICAgICByZXR1cm4gLTE7CiAgIGlm IChsZW4gPT0gMSkKICAgICB7Ci0gICAgICB0cCA9IG1lbWNociAodGV4dCwga3dzZXQtPnRhcmdl dFswXSwgc2l6ZSk7Ci0gICAgICByZXR1cm4gdHAgPyB0cCAtIHRleHQgOiAtMTsKKyAgICAgIGlm ICh0cmFucykKKyAgICAgICAgeworICAgICAgICAgIGZvciAodHAgPSB0ZXh0OyB0cCA8IHRleHQg KyBzaXplOyB0cCsrKQorICAgICAgICAgICAgaWYgKHRyYW5zW1UoKnRwKV0gPT0ga3dzZXQtPnRh cmdldFswXSkKKyAgICAgICAgICAgICAgcmV0dXJuIHRwIC0gdGV4dDsKKyAgICAgICAgICByZXR1 cm4gLTE7CisgICAgICAgIH0KKyAgICAgIGVsc2UKKyAgICAgICAgeworICAgICAgICAgIHRwID0g bWVtY2hyICh0ZXh0LCBrd3NldC0+dGFyZ2V0WzBdLCBzaXplKTsKKyAgICAgICAgICByZXR1cm4g dHAgPyB0cCAtIHRleHQgOiAtMTsKKyAgICAgICAgfQogICAgIH0KIAogICBkMSA9IGt3c2V0LT5k ZWx0YTsKICAgc3AgPSBrd3NldC0+dGFyZ2V0ICsgbGVuOwotICBnYzEgPSBzcFstMV07Ci0gIGdj MiA9IHNwWy0yXTsKICAgdHAgPSB0ZXh0ICsgbGVuOworICBpZiAodHJhbnMpCisgICAgeworICAg ICAgZ2MxID0gdHJhbnNbVShzcFstMV0pXTsKKyAgICAgIGdjMiA9IHRyYW5zW1Uoc3BbLTJdKV07 CisgICAgfQorICBlbHNlCisgICAgeworICAgICAgZ2MxID0gc3BbLTFdOworICAgICAgZ2MyID0g c3BbLTJdOworICAgIH0KICAgc2tpcCA9IDA7CiAKICAgLyogU2lnbmlmaWNhbmNlIG9mIDEyOiAx IChpbml0aWFsIG9mZnNldCkgKyAxMCAoc2tpcCBsb29wKSArIDEgKG1kMikuICovCkBAIC01MTgs MzAgKzUzNyw4NiBAQCBibWV4ZWMgKGt3c2V0X3Qga3dzZXQsIGNoYXIgY29uc3QgKnRleHQsIHNp emVfdCBzaXplKQogICAgICAgICBicmVhazsKICAgICAgIGZvdW5kOgogICAgICAgICBkID0gbGVu OwotICAgICAgICB3aGlsZSAodHJ1ZSkKKyAgICAgICAgaWYgKHRyYW5zKQogICAgICAgICAgIHsK LSAgICAgICAgICAgIGlmICh0cFstMl0gPT0gZ2MyKQorICAgICAgICAgICAgd2hpbGUgKHRydWUp CiAgICAgICAgICAgICAgIHsKLSAgICAgICAgICAgICAgICBmb3IgKGkgPSAzOyBpIDw9IGQgJiYg dHBbLWldID09IHNwWy1pXTsgKytpKQotICAgICAgICAgICAgICAgICAgY29udGludWU7Ci0gICAg ICAgICAgICAgICAgaWYgKGkgPiBkKQorICAgICAgICAgICAgICAgIGlmICh0cmFuc1tVKHRwWy0y XSldID09IGdjMikKICAgICAgICAgICAgICAgICAgIHsKLSAgICAgICAgICAgICAgICAgICAgZm9y IChpID0gZCArIHNraXAgKyAxOyBpIDw9IGxlbiAmJiB0cFstaV0gPT0gc3BbLWldOyArK2kpCi0g ICAgICAgICAgICAgICAgICAgICAgY29udGludWU7Ci0gICAgICAgICAgICAgICAgICAgIGlmIChp ID4gbGVuKQotICAgICAgICAgICAgICAgICAgICAgIHJldHVybiB0cCAtIGxlbiAtIHRleHQ7Cisg ICAgICAgICAgICAgICAgICAgIGZvciAoaSA9IDM7IGkgPD0gZDsgKytpKQorICAgICAgICAgICAg ICAgICAgICAgIGlmICh0cmFuc1tVKHRwWy1pXSldICE9IHRyYW5zW1Uoc3BbLWldKV0pCisgICAg ICAgICAgICAgICAgICAgICAgICBicmVhazsKKyAgICAgICAgICAgICAgICAgICAgaWYgKGkgPiBk KQorICAgICAgICAgICAgICAgICAgICAgIHsKKyAgICAgICAgICAgICAgICAgICAgICAgIGZvciAo aSA9IGQgKyBza2lwICsgMTsgaSA8PSBsZW47ICsraSkKKyAgICAgICAgICAgICAgICAgICAgICAg ICAgaWYgKHRyYW5zW1UodHBbLWldKV0gIT0gdHJhbnNbVShzcFstaV0pXSkKKyAgICAgICAgICAg ICAgICAgICAgICAgICAgICBicmVhazsKKyAgICAgICAgICAgICAgICAgICAgICAgIGlmIChpID4g bGVuKQorICAgICAgICAgICAgICAgICAgICAgICAgICByZXR1cm4gdHAgLSBsZW4gLSB0ZXh0Owor ICAgICAgICAgICAgICAgICAgICAgIH0KKyAgICAgICAgICAgICAgICAgICAgZCA9IGt3c2V0LT5z aGlmdFtpIC0gMl07IHRwICs9IGQ7CisgICAgICAgICAgICAgICAgICAgIGlmICh0cCA+IGVwKQor ICAgICAgICAgICAgICAgICAgICAgIGJyZWFrOworICAgICAgICAgICAgICAgICAgICBpZiAodHJh bnNbVSh0cFstMV0pXSAhPSBnYzEpCisgICAgICAgICAgICAgICAgICAgICAgeworICAgICAgICAg ICAgICAgICAgICAgICAgZCA9IGQxW1UodHBbLTFdKV0sIHRwICs9IGQ7CisgICAgICAgICAgICAg ICAgICAgICAgICBicmVhazsKKyAgICAgICAgICAgICAgICAgICAgICB9CisgICAgICAgICAgICAg ICAgICAgIHNraXAgPSBpIC0gMTsKKyAgICAgICAgICAgICAgICAgIH0KKyAgICAgICAgICAgICAg ICBlbHNlCisgICAgICAgICAgICAgICAgICB7CisgICAgICAgICAgICAgICAgICAgIGQgPSBrd3Nl dC0+c2hpZnRbMF07IHRwICs9IGQ7CisgICAgICAgICAgICAgICAgICAgIGlmICh0cCA+IGVwKQor ICAgICAgICAgICAgICAgICAgICAgIGJyZWFrOworICAgICAgICAgICAgICAgICAgICBpZiAodHJh bnNbVSh0cFstMV0pXSAhPSBnYzEpCisgICAgICAgICAgICAgICAgICAgICAgeworICAgICAgICAg ICAgICAgICAgICAgICAgZCA9IGQxW1UodHBbLTFdKV0sIHRwICs9IGQ7CisgICAgICAgICAgICAg ICAgICAgICAgICBicmVhazsKKyAgICAgICAgICAgICAgICAgICAgICB9CisgICAgICAgICAgICAg ICAgICAgIHNraXAgPSAxOwogICAgICAgICAgICAgICAgICAgfQotICAgICAgICAgICAgICAgIGQg PSBrd3NldC0+c2hpZnRbaSAtIDJdOyB0cCArPSBkOwotICAgICAgICAgICAgICAgIGlmICh0cCA+ IGVwIHx8IHRwWy0xXSAhPSBnYzEpCi0gICAgICAgICAgICAgICAgICBicmVhazsKLSAgICAgICAg ICAgICAgICBza2lwID0gaSAtIDE7CiAgICAgICAgICAgICAgIH0KLSAgICAgICAgICAgIGVsc2UK KyAgICAgICAgICB9CisgICAgICAgIGVsc2UKKyAgICAgICAgICB7CisgICAgICAgICAgICB3aGls ZSAodHJ1ZSkKICAgICAgICAgICAgICAgewotICAgICAgICAgICAgICAgIGQgPSBrd3NldC0+c2hp ZnRbMF07IHRwICs9IGQ7Ci0gICAgICAgICAgICAgICAgaWYgKHRwID4gZXAgfHwgdHBbLTFdICE9 IGdjMSkKLSAgICAgICAgICAgICAgICAgIGJyZWFrOwotICAgICAgICAgICAgICAgIHNraXAgPSAx OworICAgICAgICAgICAgICAgIGlmICh0cFstMl0gPT0gZ2MyKQorICAgICAgICAgICAgICAgICAg eworICAgICAgICAgICAgICAgICAgICBmb3IgKGkgPSAzOyBpIDw9IGQ7ICsraSkKKyAgICAgICAg ICAgICAgICAgICAgICBpZiAodHBbLWldICE9IHNwWy1pXSkKKyAgICAgICAgICAgICAgICAgICAg ICAgIGJyZWFrOworICAgICAgICAgICAgICAgICAgICBpZiAoaSA+IGQpCisgICAgICAgICAgICAg ICAgICAgICAgeworICAgICAgICAgICAgICAgICAgICAgICAgZm9yIChpID0gZCArIHNraXAgKyAx OyBpIDw9IGxlbjsgKytpKQorICAgICAgICAgICAgICAgICAgICAgICAgICBpZiAodHBbLWldICE9 IHNwWy1pXSkKKyAgICAgICAgICAgICAgICAgICAgICAgICAgICBicmVhazsKKyAgICAgICAgICAg ICAgICAgICAgICAgIGlmIChpID4gbGVuKQorICAgICAgICAgICAgICAgICAgICAgICAgICByZXR1 cm4gdHAgLSBsZW4gLSB0ZXh0OworICAgICAgICAgICAgICAgICAgICAgIH0KKyAgICAgICAgICAg ICAgICAgICAgZCA9IGt3c2V0LT5zaGlmdFtpIC0gMl07IHRwICs9IGQ7CisgICAgICAgICAgICAg ICAgICAgIGlmICh0cCA+IGVwKQorICAgICAgICAgICAgICAgICAgICAgIGJyZWFrOworICAgICAg ICAgICAgICAgICAgICBpZiAodHBbLTFdICE9IGdjMSkKKyAgICAgICAgICAgICAgICAgICAgICB7 CisgICAgICAgICAgICAgICAgICAgICAgICBkID0gZDFbVSh0cFstMV0pXSwgdHAgKz0gZDsKKyAg ICAgICAgICAgICAgICAgICAgICAgIGJyZWFrOworICAgICAgICAgICAgICAgICAgICAgIH0KKyAg ICAgICAgICAgICAgICAgICAgc2tpcCA9IGkgLSAxOworICAgICAgICAgICAgICAgICAgfQorICAg ICAgICAgICAgICAgIGVsc2UKKyAgICAgICAgICAgICAgICAgIHsKKyAgICAgICAgICAgICAgICAg ICAgZCA9IGt3c2V0LT5zaGlmdFswXTsgdHAgKz0gZDsKKyAgICAgICAgICAgICAgICAgICAgaWYg KHRwID4gZXApCisgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CisgICAgICAgICAgICAgICAg ICAgIGlmICh0cFstMV0gIT0gZ2MxKQorICAgICAgICAgICAgICAgICAgICAgIHsKKyAgICAgICAg ICAgICAgICAgICAgICAgIGQgPSBkMVtVKHRwWy0xXSldLCB0cCArPSBkOworICAgICAgICAgICAg ICAgICAgICAgICAgYnJlYWs7CisgICAgICAgICAgICAgICAgICAgICAgfQorICAgICAgICAgICAg ICAgICAgICBza2lwID0gMTsKKyAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgfQog ICAgICAgICAgIH0KICAgICAgIH0KQEAgLTU1NiwzMCArNjMxLDg2IEBAIGJtZXhlYyAoa3dzZXRf dCBrd3NldCwgY2hhciBjb25zdCAqdGV4dCwgc2l6ZV90IHNpemUpCiAgICAgICBpZiAoZCAhPSAw KQogICAgICAgICBjb250aW51ZTsKICAgICAgIGQgPSBsZW47Ci0gICAgICB3aGlsZSAodHJ1ZSkK KyAgICAgIGlmICh0cmFucykKICAgICAgICAgewotICAgICAgICAgIGlmICh0cFstMl0gPT0gZ2My KQorICAgICAgICAgIHdoaWxlICh0cnVlKQogICAgICAgICAgICAgewotICAgICAgICAgICAgICBm b3IgKGkgPSAzOyBpIDw9IGQgJiYgdHBbLWldID09IHNwWy1pXTsgKytpKQotICAgICAgICAgICAg ICAgIGNvbnRpbnVlOwotICAgICAgICAgICAgICBpZiAoaSA+IGQpCisgICAgICAgICAgICAgIGlm ICh0cmFuc1tVKHRwWy0yXSldID09IGdjMikKKyAgICAgICAgICAgICAgICB7CisgICAgICAgICAg ICAgICAgICBmb3IgKGkgPSAzOyBpIDw9IGQ7ICsraSkKKyAgICAgICAgICAgICAgICBpZiAodHJh bnNbVSh0cFstaV0pXSAhPSB0cmFuc1tVKHNwWy1pXSldKQorICAgICAgICAgICAgICAgICAgYnJl YWs7CisgICAgICAgICAgICAgICAgICBpZiAoaSA+IGQpCisgICAgICAgICAgICAgICAgICAgIHsK KyAgICAgICAgICAgICAgICAgICAgICBmb3IgKGkgPSBkICsgc2tpcCArIDE7IGkgPD0gbGVuOyAr K2kpCisgICAgICAgICAgICAgICAgICAgICAgICBpZiAodHJhbnNbVSh0cFstaV0pXSAhPSB0cmFu c1tVKHNwWy1pXSldKQorICAgICAgICAgICAgICAgICAgICAgICAgICBicmVhazsKKyAgICAgICAg ICAgICAgICAgICAgICBpZiAoaSA+IGxlbikKKyAgICAgICAgICAgICAgICAgICAgICAgIHJldHVy biB0cCAtIGxlbiAtIHRleHQ7CisgICAgICAgICAgICAgICAgICAgIH0KKyAgICAgICAgICAgICAg ICAgIGQgPSBrd3NldC0+c2hpZnRbaSAtIDJdOyB0cCArPSBkOworICAgICAgICAgICAgICAgICAg aWYgKHRwID4gZXApCisgICAgICAgICAgICAgICAgICAgIGJyZWFrOworICAgICAgICAgICAgICAg ICAgaWYgKHRyYW5zW1UodHBbLTFdKV0gIT0gZ2MxKQorICAgICAgICAgICAgICAgICAgICB7Cisg ICAgICAgICAgICAgICAgICAgICAgZCA9IGQxW1UodHBbLTFdKV07CisgICAgICAgICAgICAgICAg ICAgICAgYnJlYWs7CisgICAgICAgICAgICAgICAgICAgIH0KKyAgICAgICAgICAgICAgICAgIHNr aXAgPSBpIC0gMTsKKyAgICAgICAgICAgICAgICB9CisgICAgICAgICAgICAgIGVsc2UKICAgICAg ICAgICAgICAgICB7Ci0gICAgICAgICAgICAgICAgICBmb3IgKGkgPSBkICsgc2tpcCArIDE7IGkg PD0gbGVuICYmIHRwWy1pXSA9PSBzcFstaV07ICsraSkKLSAgICAgICAgICAgICAgICAgICAgY29u dGludWU7Ci0gICAgICAgICAgICAgICAgICBpZiAoaSA+IGxlbikKLSAgICAgICAgICAgICAgICAg ICAgcmV0dXJuIHRwIC0gbGVuIC0gdGV4dDsKKyAgICAgICAgICAgICAgICAgIGQgPSBrd3NldC0+ c2hpZnRbMF07IHRwICs9IGQ7CisgICAgICAgICAgICAgICAgICBpZiAodHAgPiBlcCkKKyAgICAg ICAgICAgICAgICAgICAgYnJlYWs7CisgICAgICAgICAgICAgICAgICBpZiAodHJhbnNbVSh0cFst MV0pXSAhPSBnYzEpCisgICAgICAgICAgICAgICAgICAgIHsKKyAgICAgICAgICAgICAgICAgICAg ICBkID0gZDFbVSh0cFstMV0pXTsKKyAgICAgICAgICAgICAgICAgICAgICBicmVhazsKKyAgICAg ICAgICAgICAgICAgICAgfQorICAgICAgICAgICAgICAgICAgc2tpcCA9IDE7CiAgICAgICAgICAg ICAgICAgfQotICAgICAgICAgICAgICBkID0ga3dzZXQtPnNoaWZ0W2kgLSAyXTsgdHAgKz0gZDsK LSAgICAgICAgICAgICAgaWYgKHRwID4gZXAgfHwgdHBbLTFdICE9IGdjMSkKLSAgICAgICAgICAg ICAgICBicmVhazsKLSAgICAgICAgICAgICAgc2tpcCA9IGkgLSAxOwogICAgICAgICAgICAgfQot ICAgICAgICAgIGVsc2UKKyAgICAgICAgfQorICAgICAgZWxzZQorICAgICAgICB7CisgICAgICAg ICAgd2hpbGUgKHRydWUpCiAgICAgICAgICAgICB7Ci0gICAgICAgICAgICAgIGQgPSBrd3NldC0+ c2hpZnRbMF07IHRwICs9IGQ7Ci0gICAgICAgICAgICAgIGlmICh0cCA+IGVwIHx8IHRwWy0xXSAh PSBnYzEpCi0gICAgICAgICAgICAgICAgYnJlYWs7Ci0gICAgICAgICAgICAgIHNraXAgPSAxOwor ICAgICAgICAgICAgICBpZiAodHBbLTJdID09IGdjMikKKyAgICAgICAgICAgICAgICB7CisgICAg ICAgICAgICAgICAgICBmb3IgKGkgPSAzOyBpIDw9IGQ7ICsraSkKKyAgICAgICAgICAgICAgICAg ICAgaWYgKHRwWy1pXSAhPSBzcFstaV0pCisgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7Cisg ICAgICAgICAgICAgICAgICBpZiAoaSA+IGQpCisgICAgICAgICAgICAgICAgICAgIHsKKyAgICAg ICAgICAgICAgICAgICAgICBmb3IgKGkgPSBkICsgc2tpcCArIDE7IGkgPD0gbGVuOyArK2kpCisg ICAgICAgICAgICAgICAgICAgICAgICBpZiAodHBbLWldICE9IHNwWy1pXSkKKyAgICAgICAgICAg ICAgICAgICAgICAgICAgYnJlYWs7CisgICAgICAgICAgICAgICAgICAgICAgaWYgKGkgPiBsZW4p CisgICAgICAgICAgICAgICAgICAgICAgICByZXR1cm4gdHAgLSBsZW4gLSB0ZXh0OworICAgICAg ICAgICAgICAgICAgICB9CisgICAgICAgICAgICAgICAgICBkID0ga3dzZXQtPnNoaWZ0W2kgLSAy XTsgdHAgKz0gZDsKKyAgICAgICAgICAgICAgICAgIGlmICh0cCA+IGVwKQorICAgICAgICAgICAg ICAgICAgICBicmVhazsKKyAgICAgICAgICAgICAgICAgIGlmICh0cFstMV0gIT0gZ2MxKQorICAg ICAgICAgICAgICAgICAgICB7CisgICAgICAgICAgICAgICAgICAgICAgZCA9IGQxW1UodHBbLTFd KV07CisgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CisgICAgICAgICAgICAgICAgICAgIH0K KyAgICAgICAgICAgICAgICAgIHNraXAgPSBpIC0gMTsKKyAgICAgICAgICAgICAgICB9CisgICAg ICAgICAgICAgIGVsc2UKKyAgICAgICAgICAgICAgICB7CisgICAgICAgICAgICAgICAgICBkID0g a3dzZXQtPnNoaWZ0WzBdOyB0cCArPSBkOworICAgICAgICAgICAgICAgICAgaWYgKHRwID4gZXAp CisgICAgICAgICAgICAgICAgICAgIGJyZWFrOworICAgICAgICAgICAgICAgICAgaWYgKHRwWy0x XSAhPSBnYzEpCisgICAgICAgICAgICAgICAgICAgIHsKKyAgICAgICAgICAgICAgICAgICAgICBk ID0gZDFbVSh0cFstMV0pXTsKKyAgICAgICAgICAgICAgICAgICAgICBicmVhazsKKyAgICAgICAg ICAgICAgICAgICAgfQorICAgICAgICAgICAgICAgICAgc2tpcCA9IDE7CisgICAgICAgICAgICAg ICAgfQogICAgICAgICAgICAgfQogICAgICAgICB9CiAgICAgfQpAQCAtNzUyLDcgKzg4Myw3IEBA IHNpemVfdAoga3dzZXhlYyAoa3dzZXRfdCBrd3NldCwgY2hhciBjb25zdCAqdGV4dCwgc2l6ZV90 IHNpemUsCiAgICAgICAgICBzdHJ1Y3Qga3dzbWF0Y2ggKmt3c21hdGNoKQogewotICBpZiAoa3dz ZXQtPndvcmRzID09IDEgJiYga3dzZXQtPnRyYW5zID09IE5VTEwpCisgIGlmIChrd3NldC0+d29y ZHMgPT0gMSkKICAgICB7CiAgICAgICBzaXplX3QgcmV0ID0gYm1leGVjIChrd3NldCwgdGV4dCwg c2l6ZSk7CiAgICAgICBpZiAocmV0ICE9IChzaXplX3QpIC0xKQotLSAKMS45LjEKCg== --------_5343FA290000000010DE_MULTIPART_MIXED_-- From unknown Tue Sep 09 13:20:26 2025 X-Loop: help-debbugs@gnu.org Subject: bug#17230: [PATCH 1/2] grep: may also use Boyer-Moore algorithm for case-insensitive matching Resent-From: Norihiro Tanaka Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Sun, 20 Apr 2014 08:22:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 17230 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: 17230@debbugs.gnu.org Received: via spool by 17230-submit@debbugs.gnu.org id=B17230.139798209930213 (code B ref 17230); Sun, 20 Apr 2014 08:22:01 +0000 Received: (at 17230) by debbugs.gnu.org; 20 Apr 2014 08:21:39 +0000 Received: from localhost ([127.0.0.1]:52956 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Wbn0M-0007rA-G7 for submit@debbugs.gnu.org; Sun, 20 Apr 2014 04:21:39 -0400 Received: from mailgw05.kcn.ne.jp ([61.86.7.212]:50973) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Wbn0I-0007qu-Ng for 17230@debbugs.gnu.org; Sun, 20 Apr 2014 04:21:36 -0400 Received: from imp02 (mailgw6.kcn.ne.jp [61.86.15.232]) by mailgw05.kcn.ne.jp (Postfix) with ESMTP id DF51D67FED for <17230@debbugs.gnu.org>; Sun, 20 Apr 2014 17:21:32 +0900 (JST) Received: from mail06.kcn.ne.jp ([61.86.6.185]) by imp02 with bizsmtp id s8MY1n00e3zXHqt018MYRL; Sun, 20 Apr 2014 17:21:32 +0900 X-OrgRCPT: 17230@debbugs.gnu.org Received: from [10.120.1.58] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail06.kcn.ne.jp (Postfix) with ESMTPA id B12751BF0094 for <17230@debbugs.gnu.org>; Sun, 20 Apr 2014 17:21:32 +0900 (JST) Date: Sun, 20 Apr 2014 17:21:32 +0900 From: Norihiro Tanaka In-Reply-To: <20140409225440.785F.27F6AC2D@kcn.ne.jp> References: <20140409225440.785F.27F6AC2D@kcn.ne.jp> Message-Id: <20140420172110.9008.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_5353825E000000008FF8_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] 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 (/) --------_5353825E000000008FF8_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit I simplified the patch by macros to work delta2 in bmexec(). --------_5353825E000000008FF8_MULTIPART_MIXED_ Content-Type: text/plain; charset="UTF-8"; name="patch.txt" Content-Disposition: attachment; filename="patch.txt" Content-Transfer-Encoding: base64 RnJvbSA4ZWRhOGQ4Yjc2YTBhM2UzOTVjYTFhNjE3MTVlNmFiMjU5MGNkNjM4IE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBOb3JpaGlybyBUYW5ha2EgPG5vcml0bmtAa2NuLm5lLmpwPgpE YXRlOiBUaHUsIDIwIE1hciAyMDE0IDA4OjA3OjI1ICswOTAwClN1YmplY3Q6IFtQQVRDSCAxLzNd IGdyZXA6IG1heSBhbHNvIHVzZSBCb3llci1Nb29yZSBhbGdvcml0aG0gZm9yCiBjYXNlLWluc2Vu c2l0aXZlIG1hdGNoaW5nCgoqIHNyYy9rd3NldC5jIChCTV9ERUxUQTJfU0VBUkNILCBMQVNUX1NI SUZULCBUUkFOUyk6IE5ldyBtYWNyby4KKGJtZXhlYyk6IFVzZSBjaGFyYWN0ZXIgdHJhbnNsYXRp b24gdGFibGUuCihrd3NleGVjKTogQ2FsbCBibWV4ZWMgZm9yIGNhc2UtaW5zZW5zaXRpdmUgbWF0 Y2hpbmcuCihrd3NwcmVwKTogQ2hhbmdlIHRoZSBgaWYnIGNvbmRpdGlvbi4KLS0tCiBzcmMva3dz ZXQuYyB8IDE3NSArKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKy0tLS0t LS0tLS0tLS0tLS0tLS0KIDEgZmlsZSBjaGFuZ2VkLCAxMTkgaW5zZXJ0aW9ucygrKSwgNTYgZGVs ZXRpb25zKC0pCgpkaWZmIC0tZ2l0IGEvc3JjL2t3c2V0LmMgYi9zcmMva3dzZXQuYwppbmRleCBk NWRiMTJmLi5kMjEyZDU5IDEwMDY0NAotLS0gYS9zcmMva3dzZXQuYworKysgYi9zcmMva3dzZXQu YwpAQCAtNDM0LDcgKzQzNCw3IEBAIGt3c3ByZXAgKGt3c2V0X3Qga3dzZXQpCiAKICAgLyogQ2hl Y2sgaWYgd2UgY2FuIHVzZSB0aGUgc2ltcGxlIGJveWVyLW1vb3JlIGFsZ29yaXRobSwgaW5zdGVh ZAogICAgICBvZiB0aGUgaGFpcnkgY29tbWVudHotd2FsdGVyIGFsZ29yaXRobS4gKi8KLSAgaWYg KCF0cmFucyAmJiBrd3NldC0+d29yZHMgPT0gMSkKKyAgaWYgKGt3c2V0LT53b3JkcyA9PSAxKQog ICAgIHsKICAgICAgIC8qIExvb2tpbmcgZm9yIGp1c3Qgb25lIHN0cmluZy4gIEV4dHJhY3QgaXQg ZnJvbSB0aGUgdHJpZS4gKi8KICAgICAgIGt3c2V0LT50YXJnZXQgPSBvYnN0YWNrX2FsbG9jICgm a3dzZXQtPm9ic3RhY2ssIGt3c2V0LT5taW5kKTsKQEAgLTQ2NCw2ICs0NjQsNzYgQEAga3dzcHJl cCAoa3dzZXRfdCBrd3NldCkKICAgICAgIGt3c2V0LT5kZWx0YVtpXSA9IGRlbHRhW1UodHJhbnNb aV0pXTsKIH0KIAorI2RlZmluZSBCTV9ERUxUQTJfU0VBUkNIIAkJCQlcCisgIGlmIChUUkFOUyh0 cFstMl0pID09IGdjMikJCQkJXAorICAgIHsJCQkJCQkJXAorICAgICAgZm9yIChpID0gMzsgaSA8 PSBsZW47ICsraSkJCQlcCisgICAgICAgIGlmIChUUkFOUyh0cFstaV0pICE9IFRSQU5TKHNwWy1p XSkpCQlcCisgICAgICAgICAgYnJlYWs7CQkJCQlcCisgICAgICBpZiAoaSA+IGxlbikJCQkJCVwK KyAgICAgICAgcmV0dXJuIHRwIC0gbGVuIC0gdGV4dDsJCQkJXAorICAgICAgZCA9IGt3c2V0LT5z aGlmdFtpIC0gMl07IHRwICs9IGQ7CQkJXAorICAgICAgaWYgKHRwID4gZXApCQkJCQlcCisgICAg ICAgIGJyZWFrOwkJCQkJCVwKKyAgICAgIGlmIChUUkFOUyh0cFstMV0pICE9IGdjMSkJCQkJXAor ICAgICAgICB7CQkJCQkJXAorICAgICAgICAgIGQgPSBkMVtVKHRwWy0xXSldOyBMQVNUX1NISUZU OwkJXAorICAgICAgICAgIGNvbnRpbnVlOwkJCQkJXAorICAgICAgICB9CQkJCQkJXAorICAgICAg c2tpcCA9IGkgLSAxOwkJCQkJXAorICAgIH0JCQkJCQkJXAorICBlbHNlCQkJCQkJCVwKKyAgICB7 CQkJCQkJCVwKKyAgICAgIGQgPSBrd3NldC0+c2hpZnRbMF07IHRwICs9IGQ7CQkJXAorICAgICAg aWYgKHRwID4gZXApCQkJCQlcCisgICAgICAgIGJyZWFrOwkJCQkJCVwKKyAgICAgIGlmIChUUkFO Uyh0cFstMV0pICE9IGdjMSkJCQkJXAorICAgICAgICB7CQkJCQkJXAorICAgICAgICAgIGQgPSBk MVtVKHRwWy0xXSldOyBMQVNUX1NISUZUOwkJXAorICAgICAgICAgIGNvbnRpbnVlOwkJCQkJXAor ICAgICAgICB9CQkJCQkJXAorICAgICAgc2tpcCA9IDE7CQkJCQkJXAorICAgIH0JCQkJCQkJXAor ICB3aGlsZSAodHJ1ZSkJCQkJCQlcCisgICAgewkJCQkJCQlcCisgICAgICBpZiAoVFJBTlModHBb LTJdKSA9PSBnYzIpCQkJCVwKKyAgICAgICAgewkJCQkJCVwKKyAgICAgICAgICBmb3IgKGkgPSAz OyBpIDw9IGQ7ICsraSkJCQlcCisgICAgICAgICAgICBpZiAoVFJBTlModHBbLWldKSAhPSBUUkFO UyhzcFstaV0pKQkJXAorICAgICAgICAgICAgICBicmVhazsJCQkJCVwKKyAgICAgICAgICBpZiAo aSA+IGQpCQkJCQlcCisgICAgICAgICAgICB7CQkJCQkJXAorICAgICAgICAgICAgICBmb3IgKGkg PSBkICsgc2tpcCArIDE7IGkgPD0gbGVuOyArK2kpCVwKKyAgICAgICAgICAgICAgICBpZiAoVFJB TlModHBbLWldKSAhPSBUUkFOUyhzcFstaV0pKQlcCisgICAgICAgICAgICAgICAgICBicmVhazsJ CQkJXAorICAgICAgICAgICAgICBpZiAoaSA+IGxlbikJCQkJXAorICAgICAgICAgICAgICAgIHJl dHVybiB0cCAtIGxlbiAtIHRleHQ7CQkJXAorICAgICAgICAgICAgfQkJCQkJCVwKKyAgICAgICAg ICBkID0ga3dzZXQtPnNoaWZ0W2kgLSAyXTsgdHAgKz0gZDsJCVwKKyAgICAgICAgICBpZiAodHAg PiBlcCkJCQkJCVwKKyAgICAgICAgICAgIGJyZWFrOwkJCQkJXAorICAgICAgICAgIGlmIChUUkFO Uyh0cFstMV0pICE9IGdjMSkJCQlcCisgICAgICAgICAgICB7CQkJCQkJXAorICAgICAgICAgICAg ICBkID0gZDFbVSh0cFstMV0pXTsgTEFTVF9TSElGVDsJCVwKKyAgICAgICAgICAgICAgYnJlYWs7 CQkJCQlcCisgICAgICAgICAgICB9CQkJCQkJXAorICAgICAgICAgIHNraXAgPSBpIC0gMTsJCQkJ CVwKKyAgICAgICAgfQkJCQkJCVwKKyAgICAgIGVsc2UJCQkJCQlcCisgICAgICAgIHsJCQkJCQlc CisgICAgICAgICAgZCA9IGt3c2V0LT5zaGlmdFswXTsgdHAgKz0gZDsJCQlcCisgICAgICAgICAg aWYgKHRwID4gZXApCQkJCQlcCisgICAgICAgICAgICBicmVhazsJCQkJCVwKKyAgICAgICAgICBp ZiAoVFJBTlModHBbLTFdKSAhPSBnYzEpCQkJXAorICAgICAgICAgICAgewkJCQkJCVwKKyAgICAg ICAgICAgICAgZCA9IGQxW1UodHBbLTFdKV07IExBU1RfU0hJRlQ7CQlcCisgICAgICAgICAgICAg IGJyZWFrOwkJCQkJXAorICAgICAgICAgICAgfQkJCQkJCVwKKyAgICAgICAgICBza2lwID0gMTsJ CQkJCVwKKyAgICAgICAgfQkJCQkJCVwKKyAgICB9CisKKwogLyogRmFzdCBib3llci1tb29yZSBz ZWFyY2guICovCiBzdGF0aWMgc2l6ZV90IF9HTF9BVFRSSUJVVEVfUFVSRQogYm1leGVjIChrd3Nl dF90IGt3c2V0LCBjaGFyIGNvbnN0ICp0ZXh0LCBzaXplX3Qgc2l6ZSkKQEAgLTQ3Myw2ICs1NDMs NyBAQCBibWV4ZWMgKGt3c2V0X3Qga3dzZXQsIGNoYXIgY29uc3QgKnRleHQsIHNpemVfdCBzaXpl KQogICBpbnQgZCwgaSwgc2tpcDsKICAgY2hhciBnYzEsIGdjMjsKICAgaW50IGxlbiA9IGt3c2V0 LT5taW5kOworICBjaGFyIGNvbnN0ICp0cmFucyA9IGt3c2V0LT50cmFuczsKIAogICBpZiAobGVu ID09IDApCiAgICAgcmV0dXJuIDA7CkBAIC00ODAsMTUgKzU1MSwzMyBAQCBibWV4ZWMgKGt3c2V0 X3Qga3dzZXQsIGNoYXIgY29uc3QgKnRleHQsIHNpemVfdCBzaXplKQogICAgIHJldHVybiAtMTsK ICAgaWYgKGxlbiA9PSAxKQogICAgIHsKLSAgICAgIHRwID0gbWVtY2hyICh0ZXh0LCBrd3NldC0+ dGFyZ2V0WzBdLCBzaXplKTsKLSAgICAgIHJldHVybiB0cCA/IHRwIC0gdGV4dCA6IC0xOworICAg ICAgaWYgKHRyYW5zKQorICAgICAgICB7CisgICAgICAgICAgZm9yICh0cCA9IHRleHQ7IHRwIDwg dGV4dCArIHNpemU7IHRwKyspCisgICAgICAgICAgICBpZiAodHJhbnNbVSgqdHApXSA9PSBrd3Nl dC0+dGFyZ2V0WzBdKQorICAgICAgICAgICAgICByZXR1cm4gdHAgLSB0ZXh0OworICAgICAgICAg IHJldHVybiAtMTsKKyAgICAgICAgfQorICAgICAgZWxzZQorICAgICAgICB7CisgICAgICAgICAg dHAgPSBtZW1jaHIgKHRleHQsIGt3c2V0LT50YXJnZXRbMF0sIHNpemUpOworICAgICAgICAgIHJl dHVybiB0cCA/IHRwIC0gdGV4dCA6IC0xOworICAgICAgICB9CiAgICAgfQogCiAgIGQxID0ga3dz ZXQtPmRlbHRhOwogICBzcCA9IGt3c2V0LT50YXJnZXQgKyBsZW47Ci0gIGdjMSA9IHNwWy0xXTsK LSAgZ2MyID0gc3BbLTJdOwogICB0cCA9IHRleHQgKyBsZW47CisgIGlmICh0cmFucykKKyAgICB7 CisgICAgICBnYzEgPSB0cmFuc1tVKHNwWy0xXSldOworICAgICAgZ2MyID0gdHJhbnNbVShzcFst Ml0pXTsKKyAgICB9CisgIGVsc2UKKyAgICB7CisgICAgICBnYzEgPSBzcFstMV07CisgICAgICBn YzIgPSBzcFstMl07CisgICAgfQogICBza2lwID0gMDsKIAogICAvKiBTaWduaWZpY2FuY2Ugb2Yg MTI6IDEgKGluaXRpYWwgb2Zmc2V0KSArIDEwIChza2lwIGxvb3ApICsgMSAobWQyKS4gKi8KQEAg LTUxNywzMiArNjA2LDE5IEBAIGJtZXhlYyAoa3dzZXRfdCBrd3NldCwgY2hhciBjb25zdCAqdGV4 dCwgc2l6ZV90IHNpemUpCiAgICAgICAgICAgfQogICAgICAgICBicmVhazsKICAgICAgIGZvdW5k OgotICAgICAgICBkID0gbGVuOwotICAgICAgICB3aGlsZSAodHJ1ZSkKKyN1bmRlZiBMQVNUX1NI SUZUCisjZGVmaW5lIExBU1RfU0hJRlQgdHAgKz0gZAorICAgICAgICBpZiAodHJhbnMpCiAgICAg ICAgICAgewotICAgICAgICAgICAgaWYgKHRwWy0yXSA9PSBnYzIpCi0gICAgICAgICAgICAgIHsK LSAgICAgICAgICAgICAgICBmb3IgKGkgPSAzOyBpIDw9IGQgJiYgdHBbLWldID09IHNwWy1pXTsg KytpKQotICAgICAgICAgICAgICAgICAgY29udGludWU7Ci0gICAgICAgICAgICAgICAgaWYgKGkg PiBkKQotICAgICAgICAgICAgICAgICAgewotICAgICAgICAgICAgICAgICAgICBmb3IgKGkgPSBk ICsgc2tpcCArIDE7IGkgPD0gbGVuICYmIHRwWy1pXSA9PSBzcFstaV07ICsraSkKLSAgICAgICAg ICAgICAgICAgICAgICBjb250aW51ZTsKLSAgICAgICAgICAgICAgICAgICAgaWYgKGkgPiBsZW4p Ci0gICAgICAgICAgICAgICAgICAgICAgcmV0dXJuIHRwIC0gbGVuIC0gdGV4dDsKLSAgICAgICAg ICAgICAgICAgIH0KLSAgICAgICAgICAgICAgICBkID0ga3dzZXQtPnNoaWZ0W2kgLSAyXTsgdHAg Kz0gZDsKLSAgICAgICAgICAgICAgICBpZiAodHAgPiBlcCB8fCB0cFstMV0gIT0gZ2MxKQotICAg ICAgICAgICAgICAgICAgYnJlYWs7Ci0gICAgICAgICAgICAgICAgc2tpcCA9IGkgLSAxOwotICAg ICAgICAgICAgICB9Ci0gICAgICAgICAgICBlbHNlCi0gICAgICAgICAgICAgIHsKLSAgICAgICAg ICAgICAgICBkID0ga3dzZXQtPnNoaWZ0WzBdOyB0cCArPSBkOwotICAgICAgICAgICAgICAgIGlm ICh0cCA+IGVwIHx8IHRwWy0xXSAhPSBnYzEpCi0gICAgICAgICAgICAgICAgICBicmVhazsKLSAg ICAgICAgICAgICAgICBza2lwID0gMTsKLSAgICAgICAgICAgICAgfQorI3VuZGVmIFRSQU5TCisj ZGVmaW5lIFRSQU5TKGNoKSB0cmFuc1tVKGNoKV0KKyAgICAgICAgICAgIEJNX0RFTFRBMl9TRUFS Q0g7CisgICAgICAgICAgfQorICAgICAgICBlbHNlCisgICAgICAgICAgeworI3VuZGVmIFRSQU5T CisjZGVmaW5lIFRSQU5TKGNoKSBjaAorICAgICAgICAgICAgQk1fREVMVEEyX1NFQVJDSDsKICAg ICAgICAgICB9CiAgICAgICB9CiAKQEAgLTU1NSwzMiArNjMxLDE5IEBAIGJtZXhlYyAoa3dzZXRf dCBrd3NldCwgY2hhciBjb25zdCAqdGV4dCwgc2l6ZV90IHNpemUpCiAgICAgICBkID0gZDFbVSgo dHAgKz0gZClbLTFdKV07CiAgICAgICBpZiAoZCAhPSAwKQogICAgICAgICBjb250aW51ZTsKLSAg ICAgIGQgPSBsZW47Ci0gICAgICB3aGlsZSAodHJ1ZSkKKyN1bmRlZiBMQVNUX1NISUZUCisjZGVm aW5lIExBU1RfU0hJRlQKKyAgICAgIGlmICh0cmFucykKICAgICAgICAgewotICAgICAgICAgIGlm ICh0cFstMl0gPT0gZ2MyKQotICAgICAgICAgICAgewotICAgICAgICAgICAgICBmb3IgKGkgPSAz OyBpIDw9IGQgJiYgdHBbLWldID09IHNwWy1pXTsgKytpKQotICAgICAgICAgICAgICAgIGNvbnRp bnVlOwotICAgICAgICAgICAgICBpZiAoaSA+IGQpCi0gICAgICAgICAgICAgICAgewotICAgICAg ICAgICAgICAgICAgZm9yIChpID0gZCArIHNraXAgKyAxOyBpIDw9IGxlbiAmJiB0cFstaV0gPT0g c3BbLWldOyArK2kpCi0gICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlOwotICAgICAgICAgICAg ICAgICAgaWYgKGkgPiBsZW4pCi0gICAgICAgICAgICAgICAgICAgIHJldHVybiB0cCAtIGxlbiAt IHRleHQ7Ci0gICAgICAgICAgICAgICAgfQotICAgICAgICAgICAgICBkID0ga3dzZXQtPnNoaWZ0 W2kgLSAyXTsgdHAgKz0gZDsKLSAgICAgICAgICAgICAgaWYgKHRwID4gZXAgfHwgdHBbLTFdICE9 IGdjMSkKLSAgICAgICAgICAgICAgICBicmVhazsKLSAgICAgICAgICAgICAgc2tpcCA9IGkgLSAx OwotICAgICAgICAgICAgfQotICAgICAgICAgIGVsc2UKLSAgICAgICAgICAgIHsKLSAgICAgICAg ICAgICAgZCA9IGt3c2V0LT5zaGlmdFswXTsgdHAgKz0gZDsKLSAgICAgICAgICAgICAgaWYgKHRw ID4gZXAgfHwgdHBbLTFdICE9IGdjMSkKLSAgICAgICAgICAgICAgICBicmVhazsKLSAgICAgICAg ICAgICAgc2tpcCA9IDE7Ci0gICAgICAgICAgICB9CisjdW5kZWYgVFJBTlMKKyNkZWZpbmUgVFJB TlMoY2gpIHRyYW5zW1UoY2gpXQorICAgICAgICAgIEJNX0RFTFRBMl9TRUFSQ0g7CisgICAgICAg IH0KKyAgICAgIGVsc2UKKyAgICAgICAgeworI3VuZGVmIFRSQU5TCisjZGVmaW5lIFRSQU5TKGNo KSBjaAorICAgICAgICAgIEJNX0RFTFRBMl9TRUFSQ0g7CiAgICAgICAgIH0KICAgICB9CiAKQEAg LTc1Miw3ICs4MTUsNyBAQCBzaXplX3QKIGt3c2V4ZWMgKGt3c2V0X3Qga3dzZXQsIGNoYXIgY29u c3QgKnRleHQsIHNpemVfdCBzaXplLAogICAgICAgICAgc3RydWN0IGt3c21hdGNoICprd3NtYXRj aCkKIHsKLSAgaWYgKGt3c2V0LT53b3JkcyA9PSAxICYmIGt3c2V0LT50cmFucyA9PSBOVUxMKQor ICBpZiAoa3dzZXQtPndvcmRzID09IDEpCiAgICAgewogICAgICAgc2l6ZV90IHJldCA9IGJtZXhl YyAoa3dzZXQsIHRleHQsIHNpemUpOwogICAgICAgaWYgKHJldCAhPSAoc2l6ZV90KSAtMSkKLS0g CjEuOS4yCgo= --------_5353825E000000008FF8_MULTIPART_MIXED_-- From unknown Tue Sep 09 13:20:26 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#17230: closed (Re: bug#17230: [PATCH 1/2] grep: may also use Boyer-Moore algorithm for case-insensitive matching) Message-ID: References: <53573FAB.8070000@cs.ucla.edu> <20140409225440.785F.27F6AC2D@kcn.ne.jp> X-Gnu-PR-Message: they-closed 17230 X-Gnu-PR-Package: grep X-Gnu-PR-Keywords: patch Reply-To: 17230@debbugs.gnu.org Date: Wed, 23 Apr 2014 04:22:03 +0000 Content-Type: multipart/mixed; boundary="----------=_1398226923-29371-1" This is a multi-part message in MIME format... ------------=_1398226923-29371-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Your bug report #17230: [PATCH 1/2] grep: may also use Boyer-Moore algorithm for case-insen= sitive matching 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 17230@debbugs.gnu.org. --=20 17230: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D17230 GNU Bug Tracking System Contact help-debbugs@gnu.org with problems ------------=_1398226923-29371-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at 17230-done) by debbugs.gnu.org; 23 Apr 2014 04:21:15 +0000 Received: from localhost ([127.0.0.1]:55601 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WcogM-0007cR-SI for submit@debbugs.gnu.org; Wed, 23 Apr 2014 00:21:15 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:47895) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WcogK-0007cD-6T for 17230-done@debbugs.gnu.org; Wed, 23 Apr 2014 00:21:13 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id 47871A60007; Tue, 22 Apr 2014 21:21:11 -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 q1mKae0eZrhb; Tue, 22 Apr 2014 21:21:05 -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 14A63A60003; Tue, 22 Apr 2014 21:21:05 -0700 (PDT) Message-ID: <53573FAB.8070000@cs.ucla.edu> Date: Tue, 22 Apr 2014 21:20:59 -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 , 17230-done@debbugs.gnu.org Subject: Re: bug#17230: [PATCH 1/2] grep: may also use Boyer-Moore algorithm for case-insensitive matching References: <20140409225440.785F.27F6AC2D@kcn.ne.jp> <20140420172110.9008.27F6AC2D@kcn.ne.jp> In-Reply-To: <20140420172110.9008.27F6AC2D@kcn.ne.jp> Content-Type: multipart/mixed; boundary="------------020601030603020806000307" X-Spam-Score: -3.0 (---) X-Debbugs-Envelope-To: 17230-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: -3.0 (---) This is a multi-part message in MIME format. --------------020601030603020806000307 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Thanks much for this performance improvement. I puzzled for a while to figure out what was going on, and was confused by that tricky macro expansion. Nowadays functions are typically not significantly slower than macros, so unless there's a major performance difference I'd prefer to use functions. I installed the performance improvement patch and followed up with the attached patch, which uses C functions instead of macros and which coalesces some of the near-duplicate code. The followup patch also includes some comments to try to explain the new functions. --------------020601030603020806000307 Content-Type: text/plain; charset=UTF-8; name="0001-kwset-simplify-Boyer-Moore-with-unibyte-i.patch" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="0001-kwset-simplify-Boyer-Moore-with-unibyte-i.patch" RnJvbSBhMzEwOTI0NTI0M2NlYWQ0NTVlZmU5M2Q3NjhiYTkyMDBhYjJmMmNkIE1vbiBTZXAg MTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBQYXVsIEVnZ2VydCA8ZWdnZXJ0QGNzLnVjbGEuZWR1 PgpEYXRlOiBNb24sIDIxIEFwciAyMDE0IDE3OjE1OjU2IC0wNzAwClN1YmplY3Q6IFtQQVRD SF0ga3dzZXQ6IHNpbXBsaWZ5IEJveWVyLU1vb3JlIHdpdGggdW5pYnl0ZSAtaQoKVGhpcyBj aGFuZ2UgZG9lc24ndCBzaWduaWZpY2FudGx5IGFmZmVjdCBwZXJmb3JtYW5jZSBvbiBteSBw bGF0Zm9ybSwKYW5kIHNob3VsZCBtYWtlIHRoZSBjb2RlIGVhc2llciB0byBtYWludGFpbi4K KiBzcmMva3dzZXQuYyAoQk1fREVMVEEyX1NFQVJDSCwgTEFTVF9TSElGVCwgVFJBTlMpOgpS ZW1vdmUgdGhlc2UgbWFjcm9zLCBpbiBmYXZvciBvZiAuLi4KKHRyLCBibV9kZWx0YTJfc2Vh cmNoKTogTmV3IGZ1bmN0aW9ucy4gIEFsbCB1c2VzIGNoYW5nZWQuClRoZSBsYXR0ZXIgZnVu Y3Rpb24gaXMgaW5saW5lIGJlY2F1c2UgdGhpcyBpbXByb3ZlcyBjb2RlIHNpemUgYW5kCnJ1 bnRpbWUgQ1BVIHNsaWdodGx5IG9uIHg4Ni02NCB3aXRoIGdjYyAtTzIgKEdDQyA0LjkuMCku CihibWV4ZWMpOiBQcmVmZXIgdHIgd2hlbiB0aGF0J3Mgc2ltcGxlci4KLS0tCiBzcmMva3dz ZXQuYyB8IDE3MyArKysrKysrKysrKysrKysrKysrKysrKy0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0KIDEgZmlsZSBjaGFuZ2VkLCA2NSBpbnNlcnRpb25zKCspLCAx MDggZGVsZXRpb25zKC0pCgpkaWZmIC0tZ2l0IGEvc3JjL2t3c2V0LmMgYi9zcmMva3dzZXQu YwppbmRleCBkMjEyZDU5Li42OWIwYTU1IDEwMDY0NAotLS0gYS9zcmMva3dzZXQuYworKysg Yi9zcmMva3dzZXQuYwpAQCAtNDY0LDc1ICs0NjQsNjYgQEAga3dzcHJlcCAoa3dzZXRfdCBr d3NldCkKICAgICAgIGt3c2V0LT5kZWx0YVtpXSA9IGRlbHRhW1UodHJhbnNbaV0pXTsKIH0K IAotI2RlZmluZSBCTV9ERUxUQTJfU0VBUkNIIAkJCQlcCi0gIGlmIChUUkFOUyh0cFstMl0p ID09IGdjMikJCQkJXAotICAgIHsJCQkJCQkJXAotICAgICAgZm9yIChpID0gMzsgaSA8PSBs ZW47ICsraSkJCQlcCi0gICAgICAgIGlmIChUUkFOUyh0cFstaV0pICE9IFRSQU5TKHNwWy1p XSkpCQlcCi0gICAgICAgICAgYnJlYWs7CQkJCQlcCi0gICAgICBpZiAoaSA+IGxlbikJCQkJ CVwKLSAgICAgICAgcmV0dXJuIHRwIC0gbGVuIC0gdGV4dDsJCQkJXAotICAgICAgZCA9IGt3 c2V0LT5zaGlmdFtpIC0gMl07IHRwICs9IGQ7CQkJXAotICAgICAgaWYgKHRwID4gZXApCQkJ CQlcCi0gICAgICAgIGJyZWFrOwkJCQkJCVwKLSAgICAgIGlmIChUUkFOUyh0cFstMV0pICE9 IGdjMSkJCQkJXAotICAgICAgICB7CQkJCQkJXAotICAgICAgICAgIGQgPSBkMVtVKHRwWy0x XSldOyBMQVNUX1NISUZUOwkJXAotICAgICAgICAgIGNvbnRpbnVlOwkJCQkJXAotICAgICAg ICB9CQkJCQkJXAotICAgICAgc2tpcCA9IGkgLSAxOwkJCQkJXAotICAgIH0JCQkJCQkJXAot ICBlbHNlCQkJCQkJCVwKLSAgICB7CQkJCQkJCVwKLSAgICAgIGQgPSBrd3NldC0+c2hpZnRb MF07IHRwICs9IGQ7CQkJXAotICAgICAgaWYgKHRwID4gZXApCQkJCQlcCi0gICAgICAgIGJy ZWFrOwkJCQkJCVwKLSAgICAgIGlmIChUUkFOUyh0cFstMV0pICE9IGdjMSkJCQkJXAotICAg ICAgICB7CQkJCQkJXAotICAgICAgICAgIGQgPSBkMVtVKHRwWy0xXSldOyBMQVNUX1NISUZU OwkJXAotICAgICAgICAgIGNvbnRpbnVlOwkJCQkJXAotICAgICAgICB9CQkJCQkJXAotICAg ICAgc2tpcCA9IDE7CQkJCQkJXAotICAgIH0JCQkJCQkJXAotICB3aGlsZSAodHJ1ZSkJCQkJ CQlcCi0gICAgewkJCQkJCQlcCi0gICAgICBpZiAoVFJBTlModHBbLTJdKSA9PSBnYzIpCQkJ CVwKLSAgICAgICAgewkJCQkJCVwKLSAgICAgICAgICBmb3IgKGkgPSAzOyBpIDw9IGQ7ICsr aSkJCQlcCi0gICAgICAgICAgICBpZiAoVFJBTlModHBbLWldKSAhPSBUUkFOUyhzcFstaV0p KQkJXAotICAgICAgICAgICAgICBicmVhazsJCQkJCVwKLSAgICAgICAgICBpZiAoaSA+IGQp CQkJCQlcCi0gICAgICAgICAgICB7CQkJCQkJXAotICAgICAgICAgICAgICBmb3IgKGkgPSBk ICsgc2tpcCArIDE7IGkgPD0gbGVuOyArK2kpCVwKLSAgICAgICAgICAgICAgICBpZiAoVFJB TlModHBbLWldKSAhPSBUUkFOUyhzcFstaV0pKQlcCi0gICAgICAgICAgICAgICAgICBicmVh azsJCQkJXAotICAgICAgICAgICAgICBpZiAoaSA+IGxlbikJCQkJXAotICAgICAgICAgICAg ICAgIHJldHVybiB0cCAtIGxlbiAtIHRleHQ7CQkJXAotICAgICAgICAgICAgfQkJCQkJCVwK LSAgICAgICAgICBkID0ga3dzZXQtPnNoaWZ0W2kgLSAyXTsgdHAgKz0gZDsJCVwKLSAgICAg ICAgICBpZiAodHAgPiBlcCkJCQkJCVwKLSAgICAgICAgICAgIGJyZWFrOwkJCQkJXAotICAg ICAgICAgIGlmIChUUkFOUyh0cFstMV0pICE9IGdjMSkJCQlcCi0gICAgICAgICAgICB7CQkJ CQkJXAotICAgICAgICAgICAgICBkID0gZDFbVSh0cFstMV0pXTsgTEFTVF9TSElGVDsJCVwK LSAgICAgICAgICAgICAgYnJlYWs7CQkJCQlcCi0gICAgICAgICAgICB9CQkJCQkJXAotICAg ICAgICAgIHNraXAgPSBpIC0gMTsJCQkJCVwKLSAgICAgICAgfQkJCQkJCVwKLSAgICAgIGVs c2UJCQkJCQlcCi0gICAgICAgIHsJCQkJCQlcCi0gICAgICAgICAgZCA9IGt3c2V0LT5zaGlm dFswXTsgdHAgKz0gZDsJCQlcCi0gICAgICAgICAgaWYgKHRwID4gZXApCQkJCQlcCi0gICAg ICAgICAgICBicmVhazsJCQkJCVwKLSAgICAgICAgICBpZiAoVFJBTlModHBbLTFdKSAhPSBn YzEpCQkJXAotICAgICAgICAgICAgewkJCQkJCVwKLSAgICAgICAgICAgICAgZCA9IGQxW1Uo dHBbLTFdKV07IExBU1RfU0hJRlQ7CQlcCi0gICAgICAgICAgICAgIGJyZWFrOwkJCQkJXAot ICAgICAgICAgICAgfQkJCQkJCVwKLSAgICAgICAgICBza2lwID0gMTsJCQkJCVwKLSAgICAg ICAgfQkJCQkJCVwKKy8qIFVzZSBUUkFOUyB0byB0cmFuc2xpdGVyYXRlIEMuICBBIG51bGwg VFJBTlMgZG9lcyBubyB0cmFuc2xpdGVyYXRpb24uICAqLworc3RhdGljIGNoYXIKK3RyIChj aGFyIGNvbnN0ICp0cmFucywgY2hhciBjKQoreworICByZXR1cm4gdHJhbnMgPyB0cmFuc1tV KGMpXSA6IGM7Cit9CisKKy8qIERlbHRhMiBwb3J0aW9uIG9mIGEgQm95ZXItTW9vcmUgc2Vh cmNoLiAgKlRQIGlzIHRoZSBzdHJpbmcgdGV4dAorICAgcG9pbnRlcjsgaXQgaXMgdXBkYXRl ZCBpbiBwbGFjZS4gIEVQIGlzIHRoZSBlbmQgb2YgdGhlIHN0cmluZyB0ZXh0LAorICAgYW5k IFNQIHRoZSBlbmQgb2YgdGhlIHBhdHRlcm4uICBMRU4gaXMgdGhlIHBhdHRlcm4gbGVuZ3Ro OyBpdCBtdXN0CisgICBiZSBhdCBsZWFzdCAyLiAgVFJBTlMsIGlmIG5vbm51bGwsIGlzIHRo ZSBpbnB1dCB0cmFuc2xhdGlvbiB0YWJsZS4KKyAgIEdDMSBhbmQgR0MyIGFyZSB0aGUgbGFz dCBhbmQgc2Vjb25kLWZyb20gbGFzdCBieXRlcyBvZiB0aGUgcGF0dGVybiwKKyAgIHRyYW5z bGl0ZXJhdGVkIGJ5IFRSQU5TOyB0aGUgY2FsbGVyIHByZWNvbXB1dGVzIHRoZW0gZm9yCisg ICBlZmZpY2llbmN5LiAgSWYgRDEgaXMgbm9ubnVsbCwgaXQgaXMgYSBkZWx0YTEgdGFibGUg Zm9yIHNoaWZ0aW5nICpUUAorICAgd2hlbiBmYWlsaW5nLiAgS1dTRVQtPnNoaWZ0IHNheXMg aG93IG11Y2ggdG8gc2hpZnQuICAqLworc3RhdGljIGlubGluZSBib29sCitibV9kZWx0YTJf c2VhcmNoIChjaGFyIGNvbnN0ICoqdHBwLCBjaGFyIGNvbnN0ICplcCwgY2hhciBjb25zdCAq c3AsIGludCBsZW4sCisgICAgICAgICAgICAgICAgICBjaGFyIGNvbnN0ICp0cmFucywgY2hh ciBnYzEsIGNoYXIgZ2MyLAorICAgICAgICAgICAgICAgICAgdW5zaWduZWQgY2hhciBjb25z dCAqZDEsIGt3c2V0X3Qga3dzZXQpCit7CisgIGNoYXIgY29uc3QgKnRwID0gKnRwcDsKKyAg aW50IGQgPSBsZW4sIHNraXAgPSAwOworCisgIHdoaWxlICh0cnVlKQorICAgIHsKKyAgICAg IGludCBpID0gMjsKKyAgICAgIGlmICh0ciAodHJhbnMsIHRwWy0yXSkgPT0gZ2MyKQorICAg ICAgICB7CisgICAgICAgICAgd2hpbGUgKCsraSA8PSBkKQorICAgICAgICAgICAgaWYgKHRy ICh0cmFucywgdHBbLWldKSAhPSB0ciAodHJhbnMsIHNwWy1pXSkpCisgICAgICAgICAgICAg IGJyZWFrOworICAgICAgICAgIGlmIChpID4gZCkKKyAgICAgICAgICAgIHsKKyAgICAgICAg ICAgICAgZm9yIChpID0gZCArIHNraXAgKyAxOyBpIDw9IGxlbjsgKytpKQorICAgICAgICAg ICAgICAgIGlmICh0ciAodHJhbnMsIHRwWy1pXSkgIT0gdHIgKHRyYW5zLCBzcFstaV0pKQor ICAgICAgICAgICAgICAgICAgYnJlYWs7CisgICAgICAgICAgICAgIGlmIChpID4gbGVuKQor ICAgICAgICAgICAgICAgIHsKKyAgICAgICAgICAgICAgICAgICp0cHAgPSB0cCAtIGxlbjsK KyAgICAgICAgICAgICAgICAgIHJldHVybiB0cnVlOworICAgICAgICAgICAgICAgIH0KKyAg ICAgICAgICAgIH0KKyAgICAgICAgfQorCisgICAgICB0cCArPSBkID0ga3dzZXQtPnNoaWZ0 W2kgLSAyXTsKKyAgICAgIGlmICh0cCA+IGVwKQorICAgICAgICBicmVhazsKKyAgICAgIGlm ICh0ciAodHJhbnMsIHRwWy0xXSkgIT0gZ2MxKQorICAgICAgICB7CisgICAgICAgICAgaWYg KGQxKQorICAgICAgICAgICAgdHAgKz0gZDFbVSh0cFstMV0pXTsKKyAgICAgICAgICBicmVh azsKKyAgICAgICAgfQorICAgICAgc2tpcCA9IGkgLSAxOwogICAgIH0KIAorICAqdHBwID0g dHA7CisgIHJldHVybiBmYWxzZTsKK30KKwogCiAvKiBGYXN0IGJveWVyLW1vb3JlIHNlYXJj aC4gKi8KIHN0YXRpYyBzaXplX3QgX0dMX0FUVFJJQlVURV9QVVJFCkBAIC01NDAsOCArNTMx LDcgQEAgYm1leGVjIChrd3NldF90IGt3c2V0LCBjaGFyIGNvbnN0ICp0ZXh0LCBzaXplX3Qg c2l6ZSkKIHsKICAgdW5zaWduZWQgY2hhciBjb25zdCAqZDE7CiAgIGNoYXIgY29uc3QgKmVw LCAqc3AsICp0cDsKLSAgaW50IGQsIGksIHNraXA7Ci0gIGNoYXIgZ2MxLCBnYzI7CisgIGlu dCBkOwogICBpbnQgbGVuID0ga3dzZXQtPm1pbmQ7CiAgIGNoYXIgY29uc3QgKnRyYW5zID0g a3dzZXQtPnRyYW5zOwogCkBAIC01NjgsMTcgKzU1OCw4IEBAIGJtZXhlYyAoa3dzZXRfdCBr d3NldCwgY2hhciBjb25zdCAqdGV4dCwgc2l6ZV90IHNpemUpCiAgIGQxID0ga3dzZXQtPmRl bHRhOwogICBzcCA9IGt3c2V0LT50YXJnZXQgKyBsZW47CiAgIHRwID0gdGV4dCArIGxlbjsK LSAgaWYgKHRyYW5zKQotICAgIHsKLSAgICAgIGdjMSA9IHRyYW5zW1Uoc3BbLTFdKV07Ci0g ICAgICBnYzIgPSB0cmFuc1tVKHNwWy0yXSldOwotICAgIH0KLSAgZWxzZQotICAgIHsKLSAg ICAgIGdjMSA9IHNwWy0xXTsKLSAgICAgIGdjMiA9IHNwWy0yXTsKLSAgICB9Ci0gIHNraXAg PSAwOworICBjaGFyIGdjMSA9IHRyICh0cmFucywgc3BbLTFdKTsKKyAgY2hhciBnYzIgPSB0 ciAodHJhbnMsIHNwWy0yXSk7CiAKICAgLyogU2lnbmlmaWNhbmNlIG9mIDEyOiAxIChpbml0 aWFsIG9mZnNldCkgKyAxMCAoc2tpcCBsb29wKSArIDEgKG1kMikuICovCiAgIGlmIChzaXpl ID4gMTIgKiBsZW4pCkBAIC02MDYsMjAgKzU4Nyw4IEBAIGJtZXhlYyAoa3dzZXRfdCBrd3Nl dCwgY2hhciBjb25zdCAqdGV4dCwgc2l6ZV90IHNpemUpCiAgICAgICAgICAgfQogICAgICAg ICBicmVhazsKICAgICAgIGZvdW5kOgotI3VuZGVmIExBU1RfU0hJRlQKLSNkZWZpbmUgTEFT VF9TSElGVCB0cCArPSBkCi0gICAgICAgIGlmICh0cmFucykKLSAgICAgICAgICB7Ci0jdW5k ZWYgVFJBTlMKLSNkZWZpbmUgVFJBTlMoY2gpIHRyYW5zW1UoY2gpXQotICAgICAgICAgICAg Qk1fREVMVEEyX1NFQVJDSDsKLSAgICAgICAgICB9Ci0gICAgICAgIGVsc2UKLSAgICAgICAg ICB7Ci0jdW5kZWYgVFJBTlMKLSNkZWZpbmUgVFJBTlMoY2gpIGNoCi0gICAgICAgICAgICBC TV9ERUxUQTJfU0VBUkNIOwotICAgICAgICAgIH0KKyAgICAgICAgaWYgKGJtX2RlbHRhMl9z ZWFyY2ggKCZ0cCwgZXAsIHNwLCBsZW4sIHRyYW5zLCBnYzEsIGdjMiwgZDEsIGt3c2V0KSkK KyAgICAgICAgICByZXR1cm4gdHAgLSB0ZXh0OwogICAgICAgfQogCiAgIC8qIE5vdyB3ZSBo YXZlIG9ubHkgYSBmZXcgY2hhcmFjdGVycyBsZWZ0IHRvIHNlYXJjaC4gIFdlCkBAIC02MzEs MjAgKzYwMCw4IEBAIGJtZXhlYyAoa3dzZXRfdCBrd3NldCwgY2hhciBjb25zdCAqdGV4dCwg c2l6ZV90IHNpemUpCiAgICAgICBkID0gZDFbVSgodHAgKz0gZClbLTFdKV07CiAgICAgICBp ZiAoZCAhPSAwKQogICAgICAgICBjb250aW51ZTsKLSN1bmRlZiBMQVNUX1NISUZUCi0jZGVm aW5lIExBU1RfU0hJRlQKLSAgICAgIGlmICh0cmFucykKLSAgICAgICAgewotI3VuZGVmIFRS QU5TCi0jZGVmaW5lIFRSQU5TKGNoKSB0cmFuc1tVKGNoKV0KLSAgICAgICAgICBCTV9ERUxU QTJfU0VBUkNIOwotICAgICAgICB9Ci0gICAgICBlbHNlCi0gICAgICAgIHsKLSN1bmRlZiBU UkFOUwotI2RlZmluZSBUUkFOUyhjaCkgY2gKLSAgICAgICAgICBCTV9ERUxUQTJfU0VBUkNI OwotICAgICAgICB9CisgICAgICBpZiAoYm1fZGVsdGEyX3NlYXJjaCAoJnRwLCBlcCwgc3As IGxlbiwgdHJhbnMsIGdjMSwgZ2MyLCBOVUxMLCBrd3NldCkpCisgICAgICAgIHJldHVybiB0 cCAtIHRleHQ7CiAgICAgfQogCiAgIHJldHVybiAtMTsKLS0gCjEuOS4wCgo= --------------020601030603020806000307-- ------------=_1398226923-29371-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at submit) by debbugs.gnu.org; 9 Apr 2014 13:55:31 +0000 Received: from localhost ([127.0.0.1]:38698 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WXsyQ-0002hL-30 for submit@debbugs.gnu.org; Wed, 09 Apr 2014 09:55:30 -0400 Received: from eggs.gnu.org ([208.118.235.92]:45969) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WXsyL-0002gn-HL for submit@debbugs.gnu.org; Wed, 09 Apr 2014 09:55:26 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WXsy9-0006Tk-5F for submit@debbugs.gnu.org; Wed, 09 Apr 2014 09:55:20 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=0.8 required=5.0 tests=BAYES_50 autolearn=disabled version=3.3.2 Received: from lists.gnu.org ([2001:4830:134:3::11]:44946) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WXsy9-0006Tg-24 for submit@debbugs.gnu.org; Wed, 09 Apr 2014 09:55:13 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:47656) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WXsy2-0000da-Nu for bug-grep@gnu.org; Wed, 09 Apr 2014 09:55:13 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WXsxr-00067q-PK for bug-grep@gnu.org; Wed, 09 Apr 2014 09:55:06 -0400 Received: from pbsg500.nifty.com ([202.248.238.70]:34750) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WXsxr-00066V-4Q for bug-grep@gnu.org; Wed, 09 Apr 2014 09:54:55 -0400 Received: from [10.120.1.47] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) (authenticated) by pbsg500.nifty.com with ESMTP id s39DsdDS017046 for ; Wed, 9 Apr 2014 22:54:41 +0900 X-Nifty-SrcIP: [118.21.128.66] Date: Wed, 09 Apr 2014 22:54:42 +0900 From: Norihiro Tanaka To: bug-grep@gnu.org Subject: [PATCH 1/2] grep: may also use Boyer-Moore algorithm for case-insensitive matching Message-Id: <20140409225440.785F.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_5343FA290000000010DE_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.4.x X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2001:4830:134:3::11 X-Spam-Score: -4.0 (----) X-Debbugs-Envelope-To: submit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.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: -4.0 (----) --------_5343FA290000000010DE_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit Boyer-Moore algorithm is faster than Beate Commentz-Walter, in especially worst case, because Galil rule is applicable only for Boyer-Moore algorithm. This patch enables to use Boyer-Moore algorithm for case-insensitive matching. Norihiro --------_5343FA290000000010DE_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII"; name="patch.txt" Content-Disposition: attachment; filename="patch.txt" Content-Transfer-Encoding: base64 RnJvbSAwNjlkNTU3MDU5NzNkZGVjYmQ1ZjA0YTQxMDk3ODkzMjI0ZDU1MDk1IE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBOb3JpaGlybyBUYW5ha2EgPG5vcml0bmtAa2NuLm5lLmpwPgpE YXRlOiBUaHUsIDIwIE1hciAyMDE0IDA4OjA3OjI1ICswOTAwClN1YmplY3Q6IFtQQVRDSCAxLzJd IGdyZXA6IG1heSBhbHNvIHVzZSBCb3llci1Nb29yZSBhbGdvcml0aG0gZm9yCiBjYXNlLWluc2Vu c2l0aXZlIG1hdGNoaW5nCgoqIHNyYy9rd3NldC5jIChibWV4ZWMpOiBVc2UgY2hhcmFjdGVyIHRy YW5zbGF0aW9uIHRhYmxlLgooa3dzZXhlYyk6IENhbGwgYm1leGVjIGZvciBjYXNlLWluc2Vuc2l0 aXZlIG1hdGNoaW5nLgooa3dzcHJlcCk6IENoYW5nZSB0aGUgYGlmJyBjb25kaXRpb24uCi0tLQog c3JjL2t3c2V0LmMgfCAyMTUgKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysr KysrKysrKysrLS0tLS0tLS0tLS0tCiAxIGZpbGUgY2hhbmdlZCwgMTczIGluc2VydGlvbnMoKyks IDQyIGRlbGV0aW9ucygtKQoKZGlmZiAtLWdpdCBhL3NyYy9rd3NldC5jIGIvc3JjL2t3c2V0LmMK aW5kZXggZDVkYjEyZi4uOGQ4YWEwNyAxMDA2NDQKLS0tIGEvc3JjL2t3c2V0LmMKKysrIGIvc3Jj L2t3c2V0LmMKQEAgLTQzNCw3ICs0MzQsNyBAQCBrd3NwcmVwIChrd3NldF90IGt3c2V0KQogCiAg IC8qIENoZWNrIGlmIHdlIGNhbiB1c2UgdGhlIHNpbXBsZSBib3llci1tb29yZSBhbGdvcml0aG0s IGluc3RlYWQKICAgICAgb2YgdGhlIGhhaXJ5IGNvbW1lbnR6LXdhbHRlciBhbGdvcml0aG0uICov Ci0gIGlmICghdHJhbnMgJiYga3dzZXQtPndvcmRzID09IDEpCisgIGlmIChrd3NldC0+d29yZHMg PT0gMSkKICAgICB7CiAgICAgICAvKiBMb29raW5nIGZvciBqdXN0IG9uZSBzdHJpbmcuICBFeHRy YWN0IGl0IGZyb20gdGhlIHRyaWUuICovCiAgICAgICBrd3NldC0+dGFyZ2V0ID0gb2JzdGFja19h bGxvYyAoJmt3c2V0LT5vYnN0YWNrLCBrd3NldC0+bWluZCk7CkBAIC00NzMsNiArNDczLDcgQEAg Ym1leGVjIChrd3NldF90IGt3c2V0LCBjaGFyIGNvbnN0ICp0ZXh0LCBzaXplX3Qgc2l6ZSkKICAg aW50IGQsIGksIHNraXA7CiAgIGNoYXIgZ2MxLCBnYzI7CiAgIGludCBsZW4gPSBrd3NldC0+bWlu ZDsKKyAgY2hhciBjb25zdCAqdHJhbnMgPSBrd3NldC0+dHJhbnM7CiAKICAgaWYgKGxlbiA9PSAw KQogICAgIHJldHVybiAwOwpAQCAtNDgwLDE1ICs0ODEsMzMgQEAgYm1leGVjIChrd3NldF90IGt3 c2V0LCBjaGFyIGNvbnN0ICp0ZXh0LCBzaXplX3Qgc2l6ZSkKICAgICByZXR1cm4gLTE7CiAgIGlm IChsZW4gPT0gMSkKICAgICB7Ci0gICAgICB0cCA9IG1lbWNociAodGV4dCwga3dzZXQtPnRhcmdl dFswXSwgc2l6ZSk7Ci0gICAgICByZXR1cm4gdHAgPyB0cCAtIHRleHQgOiAtMTsKKyAgICAgIGlm ICh0cmFucykKKyAgICAgICAgeworICAgICAgICAgIGZvciAodHAgPSB0ZXh0OyB0cCA8IHRleHQg KyBzaXplOyB0cCsrKQorICAgICAgICAgICAgaWYgKHRyYW5zW1UoKnRwKV0gPT0ga3dzZXQtPnRh cmdldFswXSkKKyAgICAgICAgICAgICAgcmV0dXJuIHRwIC0gdGV4dDsKKyAgICAgICAgICByZXR1 cm4gLTE7CisgICAgICAgIH0KKyAgICAgIGVsc2UKKyAgICAgICAgeworICAgICAgICAgIHRwID0g bWVtY2hyICh0ZXh0LCBrd3NldC0+dGFyZ2V0WzBdLCBzaXplKTsKKyAgICAgICAgICByZXR1cm4g dHAgPyB0cCAtIHRleHQgOiAtMTsKKyAgICAgICAgfQogICAgIH0KIAogICBkMSA9IGt3c2V0LT5k ZWx0YTsKICAgc3AgPSBrd3NldC0+dGFyZ2V0ICsgbGVuOwotICBnYzEgPSBzcFstMV07Ci0gIGdj MiA9IHNwWy0yXTsKICAgdHAgPSB0ZXh0ICsgbGVuOworICBpZiAodHJhbnMpCisgICAgeworICAg ICAgZ2MxID0gdHJhbnNbVShzcFstMV0pXTsKKyAgICAgIGdjMiA9IHRyYW5zW1Uoc3BbLTJdKV07 CisgICAgfQorICBlbHNlCisgICAgeworICAgICAgZ2MxID0gc3BbLTFdOworICAgICAgZ2MyID0g c3BbLTJdOworICAgIH0KICAgc2tpcCA9IDA7CiAKICAgLyogU2lnbmlmaWNhbmNlIG9mIDEyOiAx IChpbml0aWFsIG9mZnNldCkgKyAxMCAoc2tpcCBsb29wKSArIDEgKG1kMikuICovCkBAIC01MTgs MzAgKzUzNyw4NiBAQCBibWV4ZWMgKGt3c2V0X3Qga3dzZXQsIGNoYXIgY29uc3QgKnRleHQsIHNp emVfdCBzaXplKQogICAgICAgICBicmVhazsKICAgICAgIGZvdW5kOgogICAgICAgICBkID0gbGVu OwotICAgICAgICB3aGlsZSAodHJ1ZSkKKyAgICAgICAgaWYgKHRyYW5zKQogICAgICAgICAgIHsK LSAgICAgICAgICAgIGlmICh0cFstMl0gPT0gZ2MyKQorICAgICAgICAgICAgd2hpbGUgKHRydWUp CiAgICAgICAgICAgICAgIHsKLSAgICAgICAgICAgICAgICBmb3IgKGkgPSAzOyBpIDw9IGQgJiYg dHBbLWldID09IHNwWy1pXTsgKytpKQotICAgICAgICAgICAgICAgICAgY29udGludWU7Ci0gICAg ICAgICAgICAgICAgaWYgKGkgPiBkKQorICAgICAgICAgICAgICAgIGlmICh0cmFuc1tVKHRwWy0y XSldID09IGdjMikKICAgICAgICAgICAgICAgICAgIHsKLSAgICAgICAgICAgICAgICAgICAgZm9y IChpID0gZCArIHNraXAgKyAxOyBpIDw9IGxlbiAmJiB0cFstaV0gPT0gc3BbLWldOyArK2kpCi0g ICAgICAgICAgICAgICAgICAgICAgY29udGludWU7Ci0gICAgICAgICAgICAgICAgICAgIGlmIChp ID4gbGVuKQotICAgICAgICAgICAgICAgICAgICAgIHJldHVybiB0cCAtIGxlbiAtIHRleHQ7Cisg ICAgICAgICAgICAgICAgICAgIGZvciAoaSA9IDM7IGkgPD0gZDsgKytpKQorICAgICAgICAgICAg ICAgICAgICAgIGlmICh0cmFuc1tVKHRwWy1pXSldICE9IHRyYW5zW1Uoc3BbLWldKV0pCisgICAg ICAgICAgICAgICAgICAgICAgICBicmVhazsKKyAgICAgICAgICAgICAgICAgICAgaWYgKGkgPiBk KQorICAgICAgICAgICAgICAgICAgICAgIHsKKyAgICAgICAgICAgICAgICAgICAgICAgIGZvciAo aSA9IGQgKyBza2lwICsgMTsgaSA8PSBsZW47ICsraSkKKyAgICAgICAgICAgICAgICAgICAgICAg ICAgaWYgKHRyYW5zW1UodHBbLWldKV0gIT0gdHJhbnNbVShzcFstaV0pXSkKKyAgICAgICAgICAg ICAgICAgICAgICAgICAgICBicmVhazsKKyAgICAgICAgICAgICAgICAgICAgICAgIGlmIChpID4g bGVuKQorICAgICAgICAgICAgICAgICAgICAgICAgICByZXR1cm4gdHAgLSBsZW4gLSB0ZXh0Owor ICAgICAgICAgICAgICAgICAgICAgIH0KKyAgICAgICAgICAgICAgICAgICAgZCA9IGt3c2V0LT5z aGlmdFtpIC0gMl07IHRwICs9IGQ7CisgICAgICAgICAgICAgICAgICAgIGlmICh0cCA+IGVwKQor ICAgICAgICAgICAgICAgICAgICAgIGJyZWFrOworICAgICAgICAgICAgICAgICAgICBpZiAodHJh bnNbVSh0cFstMV0pXSAhPSBnYzEpCisgICAgICAgICAgICAgICAgICAgICAgeworICAgICAgICAg ICAgICAgICAgICAgICAgZCA9IGQxW1UodHBbLTFdKV0sIHRwICs9IGQ7CisgICAgICAgICAgICAg ICAgICAgICAgICBicmVhazsKKyAgICAgICAgICAgICAgICAgICAgICB9CisgICAgICAgICAgICAg ICAgICAgIHNraXAgPSBpIC0gMTsKKyAgICAgICAgICAgICAgICAgIH0KKyAgICAgICAgICAgICAg ICBlbHNlCisgICAgICAgICAgICAgICAgICB7CisgICAgICAgICAgICAgICAgICAgIGQgPSBrd3Nl dC0+c2hpZnRbMF07IHRwICs9IGQ7CisgICAgICAgICAgICAgICAgICAgIGlmICh0cCA+IGVwKQor ICAgICAgICAgICAgICAgICAgICAgIGJyZWFrOworICAgICAgICAgICAgICAgICAgICBpZiAodHJh bnNbVSh0cFstMV0pXSAhPSBnYzEpCisgICAgICAgICAgICAgICAgICAgICAgeworICAgICAgICAg ICAgICAgICAgICAgICAgZCA9IGQxW1UodHBbLTFdKV0sIHRwICs9IGQ7CisgICAgICAgICAgICAg ICAgICAgICAgICBicmVhazsKKyAgICAgICAgICAgICAgICAgICAgICB9CisgICAgICAgICAgICAg ICAgICAgIHNraXAgPSAxOwogICAgICAgICAgICAgICAgICAgfQotICAgICAgICAgICAgICAgIGQg PSBrd3NldC0+c2hpZnRbaSAtIDJdOyB0cCArPSBkOwotICAgICAgICAgICAgICAgIGlmICh0cCA+ IGVwIHx8IHRwWy0xXSAhPSBnYzEpCi0gICAgICAgICAgICAgICAgICBicmVhazsKLSAgICAgICAg ICAgICAgICBza2lwID0gaSAtIDE7CiAgICAgICAgICAgICAgIH0KLSAgICAgICAgICAgIGVsc2UK KyAgICAgICAgICB9CisgICAgICAgIGVsc2UKKyAgICAgICAgICB7CisgICAgICAgICAgICB3aGls ZSAodHJ1ZSkKICAgICAgICAgICAgICAgewotICAgICAgICAgICAgICAgIGQgPSBrd3NldC0+c2hp ZnRbMF07IHRwICs9IGQ7Ci0gICAgICAgICAgICAgICAgaWYgKHRwID4gZXAgfHwgdHBbLTFdICE9 IGdjMSkKLSAgICAgICAgICAgICAgICAgIGJyZWFrOwotICAgICAgICAgICAgICAgIHNraXAgPSAx OworICAgICAgICAgICAgICAgIGlmICh0cFstMl0gPT0gZ2MyKQorICAgICAgICAgICAgICAgICAg eworICAgICAgICAgICAgICAgICAgICBmb3IgKGkgPSAzOyBpIDw9IGQ7ICsraSkKKyAgICAgICAg ICAgICAgICAgICAgICBpZiAodHBbLWldICE9IHNwWy1pXSkKKyAgICAgICAgICAgICAgICAgICAg ICAgIGJyZWFrOworICAgICAgICAgICAgICAgICAgICBpZiAoaSA+IGQpCisgICAgICAgICAgICAg ICAgICAgICAgeworICAgICAgICAgICAgICAgICAgICAgICAgZm9yIChpID0gZCArIHNraXAgKyAx OyBpIDw9IGxlbjsgKytpKQorICAgICAgICAgICAgICAgICAgICAgICAgICBpZiAodHBbLWldICE9 IHNwWy1pXSkKKyAgICAgICAgICAgICAgICAgICAgICAgICAgICBicmVhazsKKyAgICAgICAgICAg ICAgICAgICAgICAgIGlmIChpID4gbGVuKQorICAgICAgICAgICAgICAgICAgICAgICAgICByZXR1 cm4gdHAgLSBsZW4gLSB0ZXh0OworICAgICAgICAgICAgICAgICAgICAgIH0KKyAgICAgICAgICAg ICAgICAgICAgZCA9IGt3c2V0LT5zaGlmdFtpIC0gMl07IHRwICs9IGQ7CisgICAgICAgICAgICAg ICAgICAgIGlmICh0cCA+IGVwKQorICAgICAgICAgICAgICAgICAgICAgIGJyZWFrOworICAgICAg ICAgICAgICAgICAgICBpZiAodHBbLTFdICE9IGdjMSkKKyAgICAgICAgICAgICAgICAgICAgICB7 CisgICAgICAgICAgICAgICAgICAgICAgICBkID0gZDFbVSh0cFstMV0pXSwgdHAgKz0gZDsKKyAg ICAgICAgICAgICAgICAgICAgICAgIGJyZWFrOworICAgICAgICAgICAgICAgICAgICAgIH0KKyAg ICAgICAgICAgICAgICAgICAgc2tpcCA9IGkgLSAxOworICAgICAgICAgICAgICAgICAgfQorICAg ICAgICAgICAgICAgIGVsc2UKKyAgICAgICAgICAgICAgICAgIHsKKyAgICAgICAgICAgICAgICAg ICAgZCA9IGt3c2V0LT5zaGlmdFswXTsgdHAgKz0gZDsKKyAgICAgICAgICAgICAgICAgICAgaWYg KHRwID4gZXApCisgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CisgICAgICAgICAgICAgICAg ICAgIGlmICh0cFstMV0gIT0gZ2MxKQorICAgICAgICAgICAgICAgICAgICAgIHsKKyAgICAgICAg ICAgICAgICAgICAgICAgIGQgPSBkMVtVKHRwWy0xXSldLCB0cCArPSBkOworICAgICAgICAgICAg ICAgICAgICAgICAgYnJlYWs7CisgICAgICAgICAgICAgICAgICAgICAgfQorICAgICAgICAgICAg ICAgICAgICBza2lwID0gMTsKKyAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgfQog ICAgICAgICAgIH0KICAgICAgIH0KQEAgLTU1NiwzMCArNjMxLDg2IEBAIGJtZXhlYyAoa3dzZXRf dCBrd3NldCwgY2hhciBjb25zdCAqdGV4dCwgc2l6ZV90IHNpemUpCiAgICAgICBpZiAoZCAhPSAw KQogICAgICAgICBjb250aW51ZTsKICAgICAgIGQgPSBsZW47Ci0gICAgICB3aGlsZSAodHJ1ZSkK KyAgICAgIGlmICh0cmFucykKICAgICAgICAgewotICAgICAgICAgIGlmICh0cFstMl0gPT0gZ2My KQorICAgICAgICAgIHdoaWxlICh0cnVlKQogICAgICAgICAgICAgewotICAgICAgICAgICAgICBm b3IgKGkgPSAzOyBpIDw9IGQgJiYgdHBbLWldID09IHNwWy1pXTsgKytpKQotICAgICAgICAgICAg ICAgIGNvbnRpbnVlOwotICAgICAgICAgICAgICBpZiAoaSA+IGQpCisgICAgICAgICAgICAgIGlm ICh0cmFuc1tVKHRwWy0yXSldID09IGdjMikKKyAgICAgICAgICAgICAgICB7CisgICAgICAgICAg ICAgICAgICBmb3IgKGkgPSAzOyBpIDw9IGQ7ICsraSkKKyAgICAgICAgICAgICAgICBpZiAodHJh bnNbVSh0cFstaV0pXSAhPSB0cmFuc1tVKHNwWy1pXSldKQorICAgICAgICAgICAgICAgICAgYnJl YWs7CisgICAgICAgICAgICAgICAgICBpZiAoaSA+IGQpCisgICAgICAgICAgICAgICAgICAgIHsK KyAgICAgICAgICAgICAgICAgICAgICBmb3IgKGkgPSBkICsgc2tpcCArIDE7IGkgPD0gbGVuOyAr K2kpCisgICAgICAgICAgICAgICAgICAgICAgICBpZiAodHJhbnNbVSh0cFstaV0pXSAhPSB0cmFu c1tVKHNwWy1pXSldKQorICAgICAgICAgICAgICAgICAgICAgICAgICBicmVhazsKKyAgICAgICAg ICAgICAgICAgICAgICBpZiAoaSA+IGxlbikKKyAgICAgICAgICAgICAgICAgICAgICAgIHJldHVy biB0cCAtIGxlbiAtIHRleHQ7CisgICAgICAgICAgICAgICAgICAgIH0KKyAgICAgICAgICAgICAg ICAgIGQgPSBrd3NldC0+c2hpZnRbaSAtIDJdOyB0cCArPSBkOworICAgICAgICAgICAgICAgICAg aWYgKHRwID4gZXApCisgICAgICAgICAgICAgICAgICAgIGJyZWFrOworICAgICAgICAgICAgICAg ICAgaWYgKHRyYW5zW1UodHBbLTFdKV0gIT0gZ2MxKQorICAgICAgICAgICAgICAgICAgICB7Cisg ICAgICAgICAgICAgICAgICAgICAgZCA9IGQxW1UodHBbLTFdKV07CisgICAgICAgICAgICAgICAg ICAgICAgYnJlYWs7CisgICAgICAgICAgICAgICAgICAgIH0KKyAgICAgICAgICAgICAgICAgIHNr aXAgPSBpIC0gMTsKKyAgICAgICAgICAgICAgICB9CisgICAgICAgICAgICAgIGVsc2UKICAgICAg ICAgICAgICAgICB7Ci0gICAgICAgICAgICAgICAgICBmb3IgKGkgPSBkICsgc2tpcCArIDE7IGkg PD0gbGVuICYmIHRwWy1pXSA9PSBzcFstaV07ICsraSkKLSAgICAgICAgICAgICAgICAgICAgY29u dGludWU7Ci0gICAgICAgICAgICAgICAgICBpZiAoaSA+IGxlbikKLSAgICAgICAgICAgICAgICAg ICAgcmV0dXJuIHRwIC0gbGVuIC0gdGV4dDsKKyAgICAgICAgICAgICAgICAgIGQgPSBrd3NldC0+ c2hpZnRbMF07IHRwICs9IGQ7CisgICAgICAgICAgICAgICAgICBpZiAodHAgPiBlcCkKKyAgICAg ICAgICAgICAgICAgICAgYnJlYWs7CisgICAgICAgICAgICAgICAgICBpZiAodHJhbnNbVSh0cFst MV0pXSAhPSBnYzEpCisgICAgICAgICAgICAgICAgICAgIHsKKyAgICAgICAgICAgICAgICAgICAg ICBkID0gZDFbVSh0cFstMV0pXTsKKyAgICAgICAgICAgICAgICAgICAgICBicmVhazsKKyAgICAg ICAgICAgICAgICAgICAgfQorICAgICAgICAgICAgICAgICAgc2tpcCA9IDE7CiAgICAgICAgICAg ICAgICAgfQotICAgICAgICAgICAgICBkID0ga3dzZXQtPnNoaWZ0W2kgLSAyXTsgdHAgKz0gZDsK LSAgICAgICAgICAgICAgaWYgKHRwID4gZXAgfHwgdHBbLTFdICE9IGdjMSkKLSAgICAgICAgICAg ICAgICBicmVhazsKLSAgICAgICAgICAgICAgc2tpcCA9IGkgLSAxOwogICAgICAgICAgICAgfQot ICAgICAgICAgIGVsc2UKKyAgICAgICAgfQorICAgICAgZWxzZQorICAgICAgICB7CisgICAgICAg ICAgd2hpbGUgKHRydWUpCiAgICAgICAgICAgICB7Ci0gICAgICAgICAgICAgIGQgPSBrd3NldC0+ c2hpZnRbMF07IHRwICs9IGQ7Ci0gICAgICAgICAgICAgIGlmICh0cCA+IGVwIHx8IHRwWy0xXSAh PSBnYzEpCi0gICAgICAgICAgICAgICAgYnJlYWs7Ci0gICAgICAgICAgICAgIHNraXAgPSAxOwor ICAgICAgICAgICAgICBpZiAodHBbLTJdID09IGdjMikKKyAgICAgICAgICAgICAgICB7CisgICAg ICAgICAgICAgICAgICBmb3IgKGkgPSAzOyBpIDw9IGQ7ICsraSkKKyAgICAgICAgICAgICAgICAg ICAgaWYgKHRwWy1pXSAhPSBzcFstaV0pCisgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7Cisg ICAgICAgICAgICAgICAgICBpZiAoaSA+IGQpCisgICAgICAgICAgICAgICAgICAgIHsKKyAgICAg ICAgICAgICAgICAgICAgICBmb3IgKGkgPSBkICsgc2tpcCArIDE7IGkgPD0gbGVuOyArK2kpCisg ICAgICAgICAgICAgICAgICAgICAgICBpZiAodHBbLWldICE9IHNwWy1pXSkKKyAgICAgICAgICAg ICAgICAgICAgICAgICAgYnJlYWs7CisgICAgICAgICAgICAgICAgICAgICAgaWYgKGkgPiBsZW4p CisgICAgICAgICAgICAgICAgICAgICAgICByZXR1cm4gdHAgLSBsZW4gLSB0ZXh0OworICAgICAg ICAgICAgICAgICAgICB9CisgICAgICAgICAgICAgICAgICBkID0ga3dzZXQtPnNoaWZ0W2kgLSAy XTsgdHAgKz0gZDsKKyAgICAgICAgICAgICAgICAgIGlmICh0cCA+IGVwKQorICAgICAgICAgICAg ICAgICAgICBicmVhazsKKyAgICAgICAgICAgICAgICAgIGlmICh0cFstMV0gIT0gZ2MxKQorICAg ICAgICAgICAgICAgICAgICB7CisgICAgICAgICAgICAgICAgICAgICAgZCA9IGQxW1UodHBbLTFd KV07CisgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CisgICAgICAgICAgICAgICAgICAgIH0K KyAgICAgICAgICAgICAgICAgIHNraXAgPSBpIC0gMTsKKyAgICAgICAgICAgICAgICB9CisgICAg ICAgICAgICAgIGVsc2UKKyAgICAgICAgICAgICAgICB7CisgICAgICAgICAgICAgICAgICBkID0g a3dzZXQtPnNoaWZ0WzBdOyB0cCArPSBkOworICAgICAgICAgICAgICAgICAgaWYgKHRwID4gZXAp CisgICAgICAgICAgICAgICAgICAgIGJyZWFrOworICAgICAgICAgICAgICAgICAgaWYgKHRwWy0x XSAhPSBnYzEpCisgICAgICAgICAgICAgICAgICAgIHsKKyAgICAgICAgICAgICAgICAgICAgICBk ID0gZDFbVSh0cFstMV0pXTsKKyAgICAgICAgICAgICAgICAgICAgICBicmVhazsKKyAgICAgICAg ICAgICAgICAgICAgfQorICAgICAgICAgICAgICAgICAgc2tpcCA9IDE7CisgICAgICAgICAgICAg ICAgfQogICAgICAgICAgICAgfQogICAgICAgICB9CiAgICAgfQpAQCAtNzUyLDcgKzg4Myw3IEBA IHNpemVfdAoga3dzZXhlYyAoa3dzZXRfdCBrd3NldCwgY2hhciBjb25zdCAqdGV4dCwgc2l6ZV90 IHNpemUsCiAgICAgICAgICBzdHJ1Y3Qga3dzbWF0Y2ggKmt3c21hdGNoKQogewotICBpZiAoa3dz ZXQtPndvcmRzID09IDEgJiYga3dzZXQtPnRyYW5zID09IE5VTEwpCisgIGlmIChrd3NldC0+d29y ZHMgPT0gMSkKICAgICB7CiAgICAgICBzaXplX3QgcmV0ID0gYm1leGVjIChrd3NldCwgdGV4dCwg c2l6ZSk7CiAgICAgICBpZiAocmV0ICE9IChzaXplX3QpIC0xKQotLSAKMS45LjEKCg== --------_5343FA290000000010DE_MULTIPART_MIXED_-- ------------=_1398226923-29371-1-- From unknown Tue Sep 09 13:20:26 2025 X-Loop: help-debbugs@gnu.org Subject: bug#17230: [PATCH 1/2] grep: may also use Boyer-Moore algorithm for case-insensitive matching Resent-From: Norihiro Tanaka Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Wed, 23 Apr 2014 17:52:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 17230 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: Paul Eggert Cc: 17230-done@debbugs.gnu.org Received: via spool by 17230-done@debbugs.gnu.org id=D17230.139827549917575 (code D ref 17230); Wed, 23 Apr 2014 17:52:02 +0000 Received: (at 17230-done) by debbugs.gnu.org; 23 Apr 2014 17:51:39 +0000 Received: from localhost ([127.0.0.1]:56396 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Wd1Kd-0004ZO-4z for submit@debbugs.gnu.org; Wed, 23 Apr 2014 13:51:39 -0400 Received: from mailgw05.kcn.ne.jp ([61.86.7.212]:54644) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Wd1Ka-0004ZE-Pr for 17230-done@debbugs.gnu.org; Wed, 23 Apr 2014 13:51:37 -0400 Received: from imp01 (mailgw5.kcn.ne.jp [61.86.15.231]) by mailgw05.kcn.ne.jp (Postfix) with ESMTP id 63FB6678DC for <17230-done@debbugs.gnu.org>; Thu, 24 Apr 2014 02:51:34 +0900 (JST) Received: from mail04.kcn.ne.jp ([61.86.6.183]) by imp01 with bizsmtp id tVra1n0053wvxAM01VraLJ; Thu, 24 Apr 2014 02:51:34 +0900 X-OrgRCPT: 17230-done@debbugs.gnu.org Received: from [10.120.1.12] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail04.kcn.ne.jp (Postfix) with ESMTPA id 2C399129009B; Thu, 24 Apr 2014 02:51:34 +0900 (JST) Date: Thu, 24 Apr 2014 02:51:35 +0900 From: Norihiro Tanaka In-Reply-To: <53573FAB.8070000@cs.ucla.edu> References: <20140420172110.9008.27F6AC2D@kcn.ne.jp> <53573FAB.8070000@cs.ucla.edu> Message-Id: <20140424025134.31FF.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-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 (/) Paul, thanks for a lot of reviews and commits. However, it may be wrong. I ran several tests for the worst case. $ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 >../k $ env LANG=C time -p src/grep -i kjjjjjjjjjjjjjjjjjjj ../k My version: real 0.74 user 0.43 sys 0.30 Simplified version: real 2.06 user 1.74 sys 0.31 It's slower than DFA. $ env LANG=C time -p src/grep -i 'a\|kjjjjjjjjjjjjjjjjjjj' ../k real 1.26 user 0.96 sys 0.30 I ran the test on Solaris 10 (SPARC) and HP-UX 11v2 (Itanium) - On HP-UX 11v2 $ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 >../k $ env LANG=C time -p src/grep -i kjjjjjjjjjjjjjjjjjjj ../k My version: real 2.9 user 2.6 sys 0.2 Simplified version: real 7.5 user 7.3 sys 0.2 Using DFA: $ env LANG=C time -p src/grep -i 'a\|kjjjjjjjjjjjjjjjjjjj' ../k real 3.2 user 3.0 sys 0.2 - On Solaris 10 $ env LANG=C time -p src/grep -i kjjjjjjjjjjjjjjjjjjj ../k My version: real 7.61 user 6.89 sys 0.71 Simplified version: real 24.44 user 23.71 sys 0.72 Using DFA: $ env LANG=C time -p src/grep -i 'a\|kjjjjjjjjjjjjjjjjjjj' ../k real 8.03 user 7.31 sys 0.71 Norihiro From unknown Tue Sep 09 13:20:26 2025 X-Loop: help-debbugs@gnu.org Subject: bug#17230: [PATCH 1/2] grep: may also use Boyer-Moore algorithm for case-insensitive matching Resent-From: Paul Eggert Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Wed, 23 Apr 2014 20:48:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 17230 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: Norihiro Tanaka Cc: 17230@debbugs.gnu.org Received: via spool by 17230-submit@debbugs.gnu.org id=B17230.13982860715788 (code B ref 17230); Wed, 23 Apr 2014 20:48:02 +0000 Received: (at 17230) by debbugs.gnu.org; 23 Apr 2014 20:47:51 +0000 Received: from localhost ([127.0.0.1]:56501 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Wd457-0001VG-Ks for submit@debbugs.gnu.org; Wed, 23 Apr 2014 16:47:50 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:34701) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Wd453-0001V1-R5 for 17230@debbugs.gnu.org; Wed, 23 Apr 2014 16:47:47 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id 7B464A60001; Wed, 23 Apr 2014 13:47:44 -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 B7iFUm3JHtIV; Wed, 23 Apr 2014 13:47:35 -0700 (PDT) Received: from penguin.cs.ucla.edu (Penguin.CS.UCLA.EDU [131.179.64.200]) by smtp.cs.ucla.edu (Postfix) with ESMTPSA id 976E639E8017; Wed, 23 Apr 2014 13:47:35 -0700 (PDT) Message-ID: <535826E7.2070209@cs.ucla.edu> Date: Wed, 23 Apr 2014 13:47:35 -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 References: <20140420172110.9008.27F6AC2D@kcn.ne.jp> <53573FAB.8070000@cs.ucla.edu> <20140424025134.31FF.27F6AC2D@kcn.ne.jp> In-Reply-To: <20140424025134.31FF.27F6AC2D@kcn.ne.jp> Content-Type: multipart/mixed; boundary="------------040404020302090307010000" X-Spam-Score: -3.0 (---) 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: -3.0 (---) This is a multi-part message in MIME format. --------------040404020302090307010000 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit On 04/23/2014 10:51 AM, Norihiro Tanaka wrote: > Paul, thanks for a lot of reviews and commits. However, it may be wrong. > I ran several tests for the worst case. > > $ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 >../k > $ env LANG=C time -p src/grep -i kjjjjjjjjjjjjjjjjjjj ../k > > My version: > real 0.74 > user 0.43 > sys 0.30 > > Simplified version: > real 2.06 > user 1.74 > sys 0.31 > > It's slower than DFA. > That's odd, as I'm not observing this slowdown. I'm running on Fedora 20 x86-64 with GCC 4.9.0. The current master (b0a087b4c7196782d8e76f00c45de1540daf5b91) runs a bit faster on your benchmark than the branch with your patch (dd0de0dce596add9098e1fb6e294c190c9b04f18): about 1.167 seconds versus about 1.230 seconds real time, both in the C locale. I'm not using any special compiler flags, just the -g -O2 that 'configure' deduces. I'll attach the exact difference between these two versions, as the two branches have diverged with time and perhaps something else is affecting these numbers. More generally, I don't even understand why your patch would speed things up. To my mind, it should slow things down a bit, which is what I'm observing. And (as I mentioned) it causes 'make check' to fail. Possibly I'm simply not understanding the proposed change. As far as Solaris and HP-UX goes, I'd like to wait until we've figured out the GNU situation. Those platforms are lower priority, and the code's correct for them, it's just a performance issue. --------------040404020302090307010000 Content-Type: text/x-patch; name="17230.diff" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="17230.diff" diff --git a/src/dfa.c b/src/dfa.c index 42a9736..65fc03d 100644 --- a/src/dfa.c +++ b/src/dfa.c @@ -339,9 +339,8 @@ struct dfa with dfaparse. */ unsigned int mb_cur_max; /* Cached value of MB_CUR_MAX. */ token utf8_anychar_classes[5]; /* To lower ANYCHAR in UTF-8 locales. */ - mbstate_t mbs; /* Multibyte conversion state. */ - /* The following are valid only if mb_cur_max > 1. */ + /* The following are used only if MB_CUR_MAX > 1. */ /* The value of multibyte_prop[i] is defined by following rule. if tokens[i] < NOTCHAR @@ -423,7 +422,7 @@ struct dfa struct dfamust *musts; /* List of strings, at least one of which is known to appear in any r.e. matching the dfa. */ - position_set mb_follows; /* Follow set added by ANYCHAR and/or MBCSET + position_set *mb_follows; /* Follow set added by ANYCHAR and/or MBCSET on demand. */ int *mb_match_lens; /* Array of length reduced by ANYCHAR and/or MBCSET. */ @@ -463,34 +462,33 @@ dfambcache (struct dfa *d) } } -/* Store into *PWC the result of converting the leading bytes of the - multibyte buffer S of length N bytes, using the mbrtowc_cache in *D - and updating the conversion state in *D. On conversion error, - convert just a single byte as-is. Return the number of bytes - converted. +/* Given the dfa D, store into *PWC the result of converting the + leading bytes of the multibyte buffer S of length N bytes, updating + the conversion state in *MBS. On conversion error, convert just a + single byte as-is. Return the number of bytes converted. - This differs from mbrtowc (PWC, S, N, &D->mbs) as follows: + This differs from mbrtowc (PWC, S, N, MBS) as follows: - * The last arg is a dfa *D instead of merely a multibyte conversion - state D->mbs. D also contains an mbrtowc_cache for speed. + * Extra arg D, containing an mbrtowc_cache for speed. * N must be at least 1. * S[N - 1] must be a sentinel byte. * Shift encodings are not supported. * The return value is always in the range 1..N. - * D->mbs is always valid afterwards. + * *MBS is always valid afterwards. * *PWC is always set to something. */ static size_t -mbs_to_wchar (wchar_t *pwc, char const *s, size_t n, struct dfa *d) +mbs_to_wchar (struct dfa *d, wchar_t *pwc, char const *s, size_t n, + mbstate_t *mbs) { unsigned char uc = s[0]; wint_t wc = d->mbrtowc_cache[uc]; if (wc == WEOF) { - size_t nbytes = mbrtowc (pwc, s, n, &d->mbs); + size_t nbytes = mbrtowc (pwc, s, n, mbs); if (0 < nbytes && nbytes < (size_t) -2) return nbytes; - memset (&d->mbs, 0, sizeof d->mbs); + memset (mbs, 0, sizeof *mbs); wc = uc; } @@ -840,6 +838,7 @@ static int minrep, maxrep; /* Repeat counts for {m,n}. */ static int cur_mb_len = 1; /* Length of the multibyte representation of wctok. */ /* These variables are used only if (MB_CUR_MAX > 1). */ +static mbstate_t mbs; /* mbstate for mbrtowc. */ static wchar_t wctok; /* Wide character representation of the current multibyte character. */ @@ -857,7 +856,7 @@ static wchar_t wctok; /* Wide character representation of the current else \ { \ wchar_t _wc; \ - size_t nbytes = mbs_to_wchar (&_wc, lexptr, lexleft, dfa); \ + size_t nbytes = mbs_to_wchar (dfa, &_wc, lexptr, lexleft, &mbs); \ cur_mb_len = nbytes; \ (wc) = _wc; \ (c) = nbytes == 1 ? to_uchar (*lexptr) : EOF; \ @@ -1933,7 +1932,7 @@ dfaparse (char const *s, size_t len, struct dfa *d) if (MB_CUR_MAX > 1) { cur_mb_len = 0; - memset (&d->mbs, 0, sizeof d->mbs); + memset (&mbs, 0, sizeof mbs); } if (!syntax_bits_set) @@ -3113,7 +3112,8 @@ transit_state_consume_1char (struct dfa *d, state_num s, s2 = s1; rs = transit_state_singlebyte (d, s2, (*pp)++, &s1); } - copy (&d->states[s1].elems, &d->mb_follows); + /* Copy the positions contained by 's1' to the set 'd->mb_follows'. */ + copy (&(d->states[s1].elems), d->mb_follows); /* Add all of the positions which can be reached from 's' by consuming a single character. */ @@ -3123,7 +3123,7 @@ transit_state_consume_1char (struct dfa *d, state_num s, for (j = 0; j < d->follows[d->states[s].mbps.elems[i].index].nelem; j++) insert (d->follows[d->states[s].mbps.elems[i].index].elems[j], - &d->mb_follows); + d->mb_follows); } /* FIXME: this return value is always ignored. */ @@ -3151,7 +3151,7 @@ transit_state (struct dfa *d, state_num s, unsigned char const **pp, We check whether each of them can match or not. */ { /* Note: caller must free the return value of this function. */ - mbclen = mbs_to_wchar (&wc, (char const *) *pp, end - *pp, d); + mbclen = mbs_to_wchar (d, &wc, (char const *) *pp, end - *pp, &mbs); match_lens = check_matching_with_multibyte_ops (d, s, (char const *) *pp, wc, mbclen); @@ -3179,7 +3179,7 @@ transit_state (struct dfa *d, state_num s, unsigned char const **pp, } /* This state has some operators which can match a multibyte character. */ - d->mb_follows.nelem = 0; + d->mb_follows->nelem = 0; /* 'maxlen' may be longer than the length of a character, because it may not be a character but a (multi character) collating element. @@ -3187,12 +3187,12 @@ transit_state (struct dfa *d, state_num s, unsigned char const **pp, 'maxlen' bytes. */ transit_state_consume_1char (d, s, pp, wc, mbclen, match_lens); - s1 = state_index (d, &d->mb_follows, wchar_context (wc)); + s1 = state_index (d, d->mb_follows, wchar_context (wc)); realloc_trans_if_necessary (d, s1); while (*pp - p1 < maxlen) { - mbclen = mbs_to_wchar (&wc, (char const *) *pp, end - *pp, d); + mbclen = mbs_to_wchar (d, &wc, (char const *) *pp, end - *pp, &mbs); transit_state_consume_1char (d, s1, pp, wc, mbclen, NULL); for (i = 0; i < nelem; i++) @@ -3201,10 +3201,10 @@ transit_state (struct dfa *d, state_num s, unsigned char const **pp, for (j = 0; j < d->follows[d->states[s1].mbps.elems[i].index].nelem; j++) insert (d->follows[d->states[s1].mbps.elems[i].index].elems[j], - &d->mb_follows); + d->mb_follows); } - s1 = state_index (d, &d->mb_follows, wchar_context (wc)); + s1 = state_index (d, d->mb_follows, wchar_context (wc)); realloc_trans_if_necessary (d, s1); } return s1; @@ -3244,9 +3244,15 @@ dfaexec (struct dfa *d, char const *begin, char *end, if (d->mb_cur_max > 1) { - memset (&d->mbs, 0, sizeof d->mbs); - d->mb_match_lens = xnmalloc (d->nleaves, sizeof *d->mb_match_lens); - alloc_position_set (&d->mb_follows, d->nleaves); + static bool mb_alloc = false; + memset (&mbs, 0, sizeof (mbstate_t)); + if (!mb_alloc) + { + d->mb_match_lens = xnmalloc (d->nleaves, sizeof *d->mb_match_lens); + d->mb_follows = xmalloc (sizeof *d->mb_follows); + alloc_position_set (d->mb_follows, d->nleaves); + mb_alloc = true; + } } for (;;) @@ -3271,8 +3277,8 @@ dfaexec (struct dfa *d, char const *begin, char *end, character. */ wchar_t wc; while (mbp < p) - mbp += mbs_to_wchar (&wc, (char const *) mbp, - end - (char const *) mbp, d); + mbp += mbs_to_wchar (d, &wc, (char const *) mbp, + end - (char const *) mbp, &mbs); p = mbp; if ((char *) p >= end) @@ -3401,6 +3407,7 @@ free_mbdata (struct dfa *d) size_t i; free (d->multibyte_prop); + d->multibyte_prop = NULL; for (i = 0; i < d->nmbcsets; ++i) { @@ -3420,7 +3427,14 @@ free_mbdata (struct dfa *d) } free (d->mbcsets); - free (d->mb_follows.elems); + d->mbcsets = NULL; + d->nmbcsets = 0; + + if (d->mb_follows) + { + free (d->mb_follows->elems); + free (d->mb_follows); + } free (d->mb_match_lens); } diff --git a/src/kwset.c b/src/kwset.c index f86ee03..ce127e2 100644 --- a/src/kwset.c +++ b/src/kwset.c @@ -55,6 +55,35 @@ #define U(c) (to_uchar (c)) +#if defined(__i386__) || defined(__x86_64__) +#define SHIFT(p, d) \ + switch (d) \ + { \ + default: \ + p += d; \ + break; \ + case 8: \ + ++p; \ + case 7: \ + ++p; \ + case 6: \ + ++p; \ + case 5: \ + ++p; \ + case 4: \ + ++p; \ + case 3: \ + ++p; \ + case 2: \ + ++p; \ + case 1: \ + ++p; \ + } +#else +#define SHIFT(p, d) \ + p += d; +#endif + /* Balanced tree of edges and labels leaving a given trie node. */ struct tree { @@ -508,13 +537,14 @@ bm_delta2_search (char const **tpp, char const *ep, char const *sp, int len, } } - tp += d = kwset->shift[i - 2]; + d = kwset->shift[i - 2]; + SHIFT(tp, d); if (tp > ep) break; if (tr (trans, tp[-1]) != gc1) { if (d1) - tp += d1[U(tp[-1])]; + SHIFT(tp, d1[U(tp[-1])]); break; } skip = i - 1; @@ -524,20 +554,6 @@ bm_delta2_search (char const **tpp, char const *ep, char const *sp, int len, return false; } -/* Return the address of the first byte in the buffer S that equals C. - S contains N bytes. If TRANS is nonnull, use it to transliterate - S's bytes before comparing them. */ -static char const * -memchr_trans (char const *s, char c, size_t n, char const *trans) -{ - if (! trans) - return memchr (s, c, n); - char const *slim = s + n; - for (; s < slim; s++) - if (trans[U(*s)] == c) - return s; - return NULL; -} /* Fast boyer-moore search. */ static size_t _GL_ATTRIBUTE_PURE @@ -555,8 +571,18 @@ bmexec (kwset_t kwset, char const *text, size_t size) return -1; if (len == 1) { - tp = memchr_trans (text, kwset->target[0], size, trans); - return tp ? tp - text : -1; + if (trans) + { + for (tp = text; tp < text + size; tp++) + if (trans[U(*tp)] == kwset->target[0]) + return tp - text; + return -1; + } + else + { + tp = memchr (text, kwset->target[0], size); + return tp ? tp - text : -1; + } } d1 = kwset->delta; @@ -568,33 +594,48 @@ bmexec (kwset_t kwset, char const *text, size_t size) /* Significance of 12: 1 (initial offset) + 10 (skip loop) + 1 (md2). */ if (size > 12 * len) /* 11 is not a bug, the initial offset happens only once. */ - for (ep = text + size - 11 * len; tp <= ep; ) + for (ep = text + size - 11 * len;;) { - d = d1[U(tp[-1])], tp += d; - d = d1[U(tp[-1])], tp += d; - if (d != 0) + while (tp <= ep) { - d = d1[U(tp[-1])], tp += d; - d = d1[U(tp[-1])], tp += d; - d = d1[U(tp[-1])], tp += d; - if (d != 0) + d = d1[U(tp[-1])]; SHIFT(tp, d); + d = d1[U(tp[-1])]; SHIFT(tp, d); + if (d == 0) + goto found; + d = d1[U(tp[-1])]; SHIFT(tp, d); + d = d1[U(tp[-1])]; SHIFT(tp, d); + d = d1[U(tp[-1])]; SHIFT(tp, d); + if (d == 0) + goto found; + d = d1[U(tp[-1])]; SHIFT(tp, d); + d = d1[U(tp[-1])]; SHIFT(tp, d); + d = d1[U(tp[-1])]; SHIFT(tp, d); + if (d == 0) + goto found; + /* memchar() of glibc is faster than seeking by delta1 on + some platforms. When there is no chance to match for a + while, use it on them. */ +#if defined(__GLIBC__) && (defined(__i386__) || defined(__x86_64__)) + if (!trans) { - d = d1[U(tp[-1])], tp += d; - d = d1[U(tp[-1])], tp += d; - d = d1[U(tp[-1])], tp += d; - if (d != 0) + tp = memchr (tp - 1, gc1, size + text - tp + 1); + if (tp) { - /* Typically memchr is faster than seeking by - delta1 when there is no chance to match for - a while. */ - tp--; - tp = memchr_trans (tp, gc1, text + size - tp, trans); - if (! tp) - return -1; - tp++; + ++tp; + goto found; } + else + return -1; + } + else +#endif + { + d = d1[U(tp[-1])]; SHIFT(tp, d); + d = d1[U(tp[-1])]; SHIFT(tp, d); } } + break; + found: if (bm_delta2_search (&tp, ep, sp, len, trans, gc1, gc2, d1, kwset)) return tp - text; } @@ -605,7 +646,8 @@ bmexec (kwset_t kwset, char const *text, size_t size) d = d1[U(tp[-1])]; while (d <= ep - tp) { - d = d1[U((tp += d)[-1])]; + SHIFT(tp, d); + d = d1[U(tp[-1])]; if (d != 0) continue; if (bm_delta2_search (&tp, ep, sp, len, trans, gc1, gc2, NULL, kwset)) @@ -659,17 +701,18 @@ cwexec (kwset_t kwset, char const *text, size_t len, struct kwsmatch *kwsmatch) { if (qlim && end <= qlim) { - end += d - 1; while ((d = delta[c = *end]) && end < qlim) { - end += d; - end += delta[U(*end)]; - end += delta[U(*end)]; + SHIFT(end, d); + d = delta[U(end[-1])]; SHIFT(end, d); + d = delta[U(end[-1])]; SHIFT(end, d); } - ++end; } else - d = delta[c = (end += d)[-1]]; + { + SHIFT(end, d); + d = delta[c = end[-1]]; + } if (d) continue; beg = end - 1; @@ -718,7 +761,8 @@ cwexec (kwset_t kwset, char const *text, size_t len, struct kwsmatch *kwsmatch) d = 1; while (lim - end >= d) { - if ((d = delta[c = (end += d)[-1]]) != 0) + SHIFT(end, d); + if ((d = delta[c = end[-1]]) != 0) continue; beg = end - 1; if (!(trie = next[c])) --------------040404020302090307010000-- From unknown Tue Sep 09 13:20:26 2025 X-Loop: help-debbugs@gnu.org Subject: bug#17230: [PATCH 1/2] grep: may also use Boyer-Moore algorithm for case-insensitive matching Resent-From: Norihiro Tanaka Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Thu, 24 Apr 2014 00:00:03 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 17230 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: Paul Eggert Cc: 17230@debbugs.gnu.org Received: via spool by 17230-submit@debbugs.gnu.org id=B17230.139829758625151 (code B ref 17230); Thu, 24 Apr 2014 00:00:03 +0000 Received: (at 17230) by debbugs.gnu.org; 23 Apr 2014 23:59:46 +0000 Received: from localhost ([127.0.0.1]:56613 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Wd74q-0006Xa-O4 for submit@debbugs.gnu.org; Wed, 23 Apr 2014 19:59:45 -0400 Received: from mailgw04.kcn.ne.jp ([61.86.7.211]:44067) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Wd74m-0006XP-Jh for 17230@debbugs.gnu.org; Wed, 23 Apr 2014 19:59:42 -0400 Received: from imp01 (mailgw5.kcn.ne.jp [61.86.15.231]) by mailgw04.kcn.ne.jp (Postfix) with ESMTP id C5E9D6C15DA for <17230@debbugs.gnu.org>; Thu, 24 Apr 2014 08:59:37 +0900 (JST) Received: from mail05.kcn.ne.jp ([61.86.6.184]) by imp01 with bizsmtp id tbzd1n00D3yDdWd01bzdLn; Thu, 24 Apr 2014 08:59:37 +0900 X-OrgRCPT: 17230@debbugs.gnu.org Received: from [10.120.1.25] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail05.kcn.ne.jp (Postfix) with ESMTPA id 6F4097D0099; Thu, 24 Apr 2014 08:59:37 +0900 (JST) Date: Thu, 24 Apr 2014 08:59:38 +0900 From: Norihiro Tanaka In-Reply-To: <535826E7.2070209@cs.ucla.edu> References: <20140424025134.31FF.27F6AC2D@kcn.ne.jp> <535826E7.2070209@cs.ucla.edu> Message-Id: <20140424085935.6B3F.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_53584AF3000000006B30_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] 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 (/) --------_53584AF3000000006B30_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit Paul Eggert wrote: > That's odd, as I'm not observing this slowdown. Though I apply 17230.diff and tests, I don't observed slowdown. However, I cann't find macros `BM_DELTA2_SEARCH' etc in 17230.diff. Could you also consider them, and run (A) instead of (B)? It means that overheads by `yes' and `head' should be ignored. (A) $ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 >k $ grep -i jk (B) $ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 | grep -i jk I attach the difference between current master and my version. Though I don't analyze detail still, don't seem that overhead by check for `trans' in `tr' function, which is called each time the comparison of a character, can be ignorable. Norihiro --------_53584AF3000000006B30_MULTIPART_MIXED_ Content-Type: text/plain; charset="UTF-8"; name="17230.diff" Content-Disposition: attachment; filename="17230.diff" Content-Transfer-Encoding: base64 ZGlmZiAtLWdpdCBhL3NyYy9rd3NldC5jIGIvc3JjL2t3c2V0LmMKaW5kZXggZjg2ZWUwMy4uM2M1 M2U4MSAxMDA2NDQKLS0tIGEvc3JjL2t3c2V0LmMKKysrIGIvc3JjL2t3c2V0LmMKQEAgLTU1LDYg KzU1LDM1IEBACiAKICNkZWZpbmUgVShjKSAodG9fdWNoYXIgKGMpKQogCisjaWYgZGVmaW5lZChf X2kzODZfXykgfHwgZGVmaW5lZChfX3g4Nl82NF9fKQorI2RlZmluZSBTSElGVChwLCBkKQlcCisg IHN3aXRjaCAoZCkJCVwKKyAgICB7CQkJXAorICAgIGRlZmF1bHQ6CQlcCisgICAgICBwICs9IGQ7 CQlcCisgICAgICBicmVhazsJCVwKKyAgICBjYXNlIDg6CQlcCisgICAgICArK3A7CQlcCisgICAg Y2FzZSA3OgkJXAorICAgICAgKytwOwkJXAorICAgIGNhc2UgNjoJCVwKKyAgICAgICsrcDsJCVwK KyAgICBjYXNlIDU6CQlcCisgICAgICArK3A7CQlcCisgICAgY2FzZSA0OgkJXAorICAgICAgKytw OwkJXAorICAgIGNhc2UgMzoJCVwKKyAgICAgICsrcDsJCVwKKyAgICBjYXNlIDI6CQlcCisgICAg ICArK3A7CQlcCisgICAgY2FzZSAxOgkJXAorICAgICAgKytwOwkJXAorICAgIH0KKyNlbHNlCisj ZGVmaW5lIFNISUZUKHAsIGQpCVwKKyAgcCArPSBkOworI2VuZGlmCisKIC8qIEJhbGFuY2VkIHRy ZWUgb2YgZWRnZXMgYW5kIGxhYmVscyBsZWF2aW5nIGEgZ2l2ZW4gdHJpZSBub2RlLiAqLwogc3Ry dWN0IHRyZWUKIHsKQEAgLTQ2NCw4MCArNDkzLDc1IEBAIGt3c3ByZXAgKGt3c2V0X3Qga3dzZXQp CiAgICAgICBrd3NldC0+ZGVsdGFbaV0gPSBkZWx0YVtVKHRyYW5zW2ldKV07CiB9CiAKLS8qIFVz ZSBUUkFOUyB0byB0cmFuc2xpdGVyYXRlIEMuICBBIG51bGwgVFJBTlMgZG9lcyBubyB0cmFuc2xp dGVyYXRpb24uICAqLwotc3RhdGljIGNoYXIKLXRyIChjaGFyIGNvbnN0ICp0cmFucywgY2hhciBj KQotewotICByZXR1cm4gdHJhbnMgPyB0cmFuc1tVKGMpXSA6IGM7Ci19Ci0KLS8qIERlbHRhMiBw b3J0aW9uIG9mIGEgQm95ZXItTW9vcmUgc2VhcmNoLiAgKlRQIGlzIHRoZSBzdHJpbmcgdGV4dAot ICAgcG9pbnRlcjsgaXQgaXMgdXBkYXRlZCBpbiBwbGFjZS4gIEVQIGlzIHRoZSBlbmQgb2YgdGhl IHN0cmluZyB0ZXh0LAotICAgYW5kIFNQIHRoZSBlbmQgb2YgdGhlIHBhdHRlcm4uICBMRU4gaXMg dGhlIHBhdHRlcm4gbGVuZ3RoOyBpdCBtdXN0Ci0gICBiZSBhdCBsZWFzdCAyLiAgVFJBTlMsIGlm IG5vbm51bGwsIGlzIHRoZSBpbnB1dCB0cmFuc2xhdGlvbiB0YWJsZS4KLSAgIEdDMSBhbmQgR0My IGFyZSB0aGUgbGFzdCBhbmQgc2Vjb25kLWZyb20gbGFzdCBieXRlcyBvZiB0aGUgcGF0dGVybiwK LSAgIHRyYW5zbGl0ZXJhdGVkIGJ5IFRSQU5TOyB0aGUgY2FsbGVyIHByZWNvbXB1dGVzIHRoZW0g Zm9yCi0gICBlZmZpY2llbmN5LiAgSWYgRDEgaXMgbm9ubnVsbCwgaXQgaXMgYSBkZWx0YTEgdGFi bGUgZm9yIHNoaWZ0aW5nICpUUAotICAgd2hlbiBmYWlsaW5nLiAgS1dTRVQtPnNoaWZ0IHNheXMg aG93IG11Y2ggdG8gc2hpZnQuICAqLwotc3RhdGljIGlubGluZSBib29sCi1ibV9kZWx0YTJfc2Vh cmNoIChjaGFyIGNvbnN0ICoqdHBwLCBjaGFyIGNvbnN0ICplcCwgY2hhciBjb25zdCAqc3AsIGlu dCBsZW4sCi0gICAgICAgICAgICAgICAgICBjaGFyIGNvbnN0ICp0cmFucywgY2hhciBnYzEsIGNo YXIgZ2MyLAotICAgICAgICAgICAgICAgICAgdW5zaWduZWQgY2hhciBjb25zdCAqZDEsIGt3c2V0 X3Qga3dzZXQpCi17Ci0gIGNoYXIgY29uc3QgKnRwID0gKnRwcDsKLSAgaW50IGQgPSBsZW4sIHNr aXAgPSAwOwotCi0gIHdoaWxlICh0cnVlKQotICAgIHsKLSAgICAgIGludCBpID0gMjsKLSAgICAg IGlmICh0ciAodHJhbnMsIHRwWy0yXSkgPT0gZ2MyKQotICAgICAgICB7Ci0gICAgICAgICAgd2hp bGUgKCsraSA8PSBkKQotICAgICAgICAgICAgaWYgKHRyICh0cmFucywgdHBbLWldKSAhPSB0ciAo dHJhbnMsIHNwWy1pXSkpCi0gICAgICAgICAgICAgIGJyZWFrOwotICAgICAgICAgIGlmIChpID4g ZCkKLSAgICAgICAgICAgIHsKLSAgICAgICAgICAgICAgZm9yIChpID0gZCArIHNraXAgKyAxOyBp IDw9IGxlbjsgKytpKQotICAgICAgICAgICAgICAgIGlmICh0ciAodHJhbnMsIHRwWy1pXSkgIT0g dHIgKHRyYW5zLCBzcFstaV0pKQotICAgICAgICAgICAgICAgICAgYnJlYWs7Ci0gICAgICAgICAg ICAgIGlmIChpID4gbGVuKQotICAgICAgICAgICAgICAgIHsKLSAgICAgICAgICAgICAgICAgICp0 cHAgPSB0cCAtIGxlbjsKLSAgICAgICAgICAgICAgICAgIHJldHVybiB0cnVlOwotICAgICAgICAg ICAgICAgIH0KLSAgICAgICAgICAgIH0KLSAgICAgICAgfQotCi0gICAgICB0cCArPSBkID0ga3dz ZXQtPnNoaWZ0W2kgLSAyXTsKLSAgICAgIGlmICh0cCA+IGVwKQotICAgICAgICBicmVhazsKLSAg ICAgIGlmICh0ciAodHJhbnMsIHRwWy0xXSkgIT0gZ2MxKQotICAgICAgICB7Ci0gICAgICAgICAg aWYgKGQxKQotICAgICAgICAgICAgdHAgKz0gZDFbVSh0cFstMV0pXTsKLSAgICAgICAgICBicmVh azsKLSAgICAgICAgfQotICAgICAgc2tpcCA9IGkgLSAxOworI2RlZmluZSBCTV9ERUxUQTJfU0VB UkNIIAkJCQlcCisgIGlmIChUUkFOUyh0cFstMl0pID09IGdjMikJCQkJXAorICAgIHsJCQkJCQkJ XAorICAgICAgZm9yIChpID0gMzsgaSA8PSBsZW47ICsraSkJCQlcCisgICAgICAgIGlmIChUUkFO Uyh0cFstaV0pICE9IFRSQU5TKHNwWy1pXSkpCQlcCisgICAgICAgICAgYnJlYWs7CQkJCQlcCisg ICAgICBpZiAoaSA+IGxlbikJCQkJCVwKKyAgICAgICAgcmV0dXJuIHRwIC0gbGVuIC0gdGV4dDsJ CQkJXAorICAgICAgZCA9IGt3c2V0LT5zaGlmdFtpIC0gMl07IFNISUZUKHRwLCBkKTsJCVwKKyAg ICAgIGlmICh0cCA+IGVwKQkJCQkJXAorICAgICAgICBicmVhazsJCQkJCQlcCisgICAgICBpZiAo VFJBTlModHBbLTFdKSAhPSBnYzEpCQkJCVwKKyAgICAgICAgewkJCQkJCVwKKyAgICAgICAgICBk ID0gZDFbVSh0cFstMV0pXTsgTEFTVF9TSElGVDsJCVwKKyAgICAgICAgICBjb250aW51ZTsJCQkJ CVwKKyAgICAgICAgfQkJCQkJCVwKKyAgICAgIHNraXAgPSBpIC0gMTsJCQkJCVwKKyAgICB9CQkJ CQkJCVwKKyAgZWxzZQkJCQkJCQlcCisgICAgewkJCQkJCQlcCisgICAgICBkID0ga3dzZXQtPnNo aWZ0WzBdOyBTSElGVCh0cCwgZCk7CQlcCisgICAgICBpZiAodHAgPiBlcCkJCQkJCVwKKyAgICAg ICAgYnJlYWs7CQkJCQkJXAorICAgICAgaWYgKFRSQU5TKHRwWy0xXSkgIT0gZ2MxKQkJCQlcCisg ICAgICAgIHsJCQkJCQlcCisgICAgICAgICAgZCA9IGQxW1UodHBbLTFdKV07IExBU1RfU0hJRlQ7 CQlcCisgICAgICAgICAgY29udGludWU7CQkJCQlcCisgICAgICAgIH0JCQkJCQlcCisgICAgICBz a2lwID0gMTsJCQkJCQlcCisgICAgfQkJCQkJCQlcCisgIHdoaWxlICh0cnVlKQkJCQkJCVwKKyAg ICB7CQkJCQkJCVwKKyAgICAgIGlmIChUUkFOUyh0cFstMl0pID09IGdjMikJCQkJXAorICAgICAg ICB7CQkJCQkJXAorICAgICAgICAgIGZvciAoaSA9IDM7IGkgPD0gZDsgKytpKQkJCVwKKyAgICAg ICAgICAgIGlmIChUUkFOUyh0cFstaV0pICE9IFRSQU5TKHNwWy1pXSkpCQlcCisgICAgICAgICAg ICAgIGJyZWFrOwkJCQkJXAorICAgICAgICAgIGlmIChpID4gZCkJCQkJCVwKKyAgICAgICAgICAg IHsJCQkJCQlcCisgICAgICAgICAgICAgIGZvciAoaSA9IGQgKyBza2lwICsgMTsgaSA8PSBsZW47 ICsraSkJXAorICAgICAgICAgICAgICAgIGlmIChUUkFOUyh0cFstaV0pICE9IFRSQU5TKHNwWy1p XSkpCVwKKyAgICAgICAgICAgICAgICAgIGJyZWFrOwkJCQlcCisgICAgICAgICAgICAgIGlmIChp ID4gbGVuKQkJCQlcCisgICAgICAgICAgICAgICAgcmV0dXJuIHRwIC0gbGVuIC0gdGV4dDsJCQlc CisgICAgICAgICAgICB9CQkJCQkJXAorICAgICAgICAgIGQgPSBrd3NldC0+c2hpZnRbaSAtIDJd OyBTSElGVCh0cCwgZCk7CVwKKyAgICAgICAgICBpZiAodHAgPiBlcCkJCQkJCVwKKyAgICAgICAg ICAgIGJyZWFrOwkJCQkJXAorICAgICAgICAgIGlmIChUUkFOUyh0cFstMV0pICE9IGdjMSkJCQlc CisgICAgICAgICAgICB7CQkJCQkJXAorICAgICAgICAgICAgICBkID0gZDFbVSh0cFstMV0pXTsg TEFTVF9TSElGVDsJCVwKKyAgICAgICAgICAgICAgYnJlYWs7CQkJCQlcCisgICAgICAgICAgICB9 CQkJCQkJXAorICAgICAgICAgIHNraXAgPSBpIC0gMTsJCQkJCVwKKyAgICAgICAgfQkJCQkJCVwK KyAgICAgIGVsc2UJCQkJCQlcCisgICAgICAgIHsJCQkJCQlcCisgICAgICAgICAgZCA9IGt3c2V0 LT5zaGlmdFswXTsgU0hJRlQodHAsIGQpOwkJXAorICAgICAgICAgIGlmICh0cCA+IGVwKQkJCQkJ XAorICAgICAgICAgICAgYnJlYWs7CQkJCQlcCisgICAgICAgICAgaWYgKFRSQU5TKHRwWy0xXSkg IT0gZ2MxKQkJCVwKKyAgICAgICAgICAgIHsJCQkJCQlcCisgICAgICAgICAgICAgIGQgPSBkMVtV KHRwWy0xXSldOyBMQVNUX1NISUZUOwkJXAorICAgICAgICAgICAgICBicmVhazsJCQkJCVwKKyAg ICAgICAgICAgIH0JCQkJCQlcCisgICAgICAgICAgc2tpcCA9IDE7CQkJCQlcCisgICAgICAgIH0J CQkJCQlcCiAgICAgfQogCi0gICp0cHAgPSB0cDsKLSAgcmV0dXJuIGZhbHNlOwotfQotCi0vKiBS ZXR1cm4gdGhlIGFkZHJlc3Mgb2YgdGhlIGZpcnN0IGJ5dGUgaW4gdGhlIGJ1ZmZlciBTIHRoYXQg ZXF1YWxzIEMuCi0gICBTIGNvbnRhaW5zIE4gYnl0ZXMuICBJZiBUUkFOUyBpcyBub25udWxsLCB1 c2UgaXQgdG8gdHJhbnNsaXRlcmF0ZQotICAgUydzIGJ5dGVzIGJlZm9yZSBjb21wYXJpbmcgdGhl bS4gICovCi1zdGF0aWMgY2hhciBjb25zdCAqCi1tZW1jaHJfdHJhbnMgKGNoYXIgY29uc3QgKnMs IGNoYXIgYywgc2l6ZV90IG4sIGNoYXIgY29uc3QgKnRyYW5zKQotewotICBpZiAoISB0cmFucykK LSAgICByZXR1cm4gbWVtY2hyIChzLCBjLCBuKTsKLSAgY2hhciBjb25zdCAqc2xpbSA9IHMgKyBu OwotICBmb3IgKDsgcyA8IHNsaW07IHMrKykKLSAgICBpZiAodHJhbnNbVSgqcyldID09IGMpCi0g ICAgICByZXR1cm4gczsKLSAgcmV0dXJuIE5VTEw7Ci19CiAKIC8qIEZhc3QgYm95ZXItbW9vcmUg c2VhcmNoLiAqLwogc3RhdGljIHNpemVfdCBfR0xfQVRUUklCVVRFX1BVUkUKQEAgLTU0NSw3ICs1 NjksOCBAQCBibWV4ZWMgKGt3c2V0X3Qga3dzZXQsIGNoYXIgY29uc3QgKnRleHQsIHNpemVfdCBz aXplKQogewogICB1bnNpZ25lZCBjaGFyIGNvbnN0ICpkMTsKICAgY2hhciBjb25zdCAqZXAsICpz cCwgKnRwOwotICBpbnQgZDsKKyAgaW50IGQsIGksIHNraXA7CisgIGNoYXIgZ2MxLCBnYzI7CiAg IGludCBsZW4gPSBrd3NldC0+bWluZDsKICAgY2hhciBjb25zdCAqdHJhbnMgPSBrd3NldC0+dHJh bnM7CiAKQEAgLTU1NSw0OCArNTgwLDk0IEBAIGJtZXhlYyAoa3dzZXRfdCBrd3NldCwgY2hhciBj b25zdCAqdGV4dCwgc2l6ZV90IHNpemUpCiAgICAgcmV0dXJuIC0xOwogICBpZiAobGVuID09IDEp CiAgICAgewotICAgICAgdHAgPSBtZW1jaHJfdHJhbnMgKHRleHQsIGt3c2V0LT50YXJnZXRbMF0s IHNpemUsIHRyYW5zKTsKLSAgICAgIHJldHVybiB0cCA/IHRwIC0gdGV4dCA6IC0xOworICAgICAg aWYgKHRyYW5zKQorICAgICAgICB7CisgICAgICAgICAgZm9yICh0cCA9IHRleHQ7IHRwIDwgdGV4 dCArIHNpemU7IHRwKyspCisgICAgICAgICAgICBpZiAodHJhbnNbVSgqdHApXSA9PSBrd3NldC0+ dGFyZ2V0WzBdKQorICAgICAgICAgICAgICByZXR1cm4gdHAgLSB0ZXh0OworICAgICAgICAgIHJl dHVybiAtMTsKKyAgICAgICAgfQorICAgICAgZWxzZQorICAgICAgICB7CisgICAgICAgICAgdHAg PSBtZW1jaHIgKHRleHQsIGt3c2V0LT50YXJnZXRbMF0sIHNpemUpOworICAgICAgICAgIHJldHVy biB0cCA/IHRwIC0gdGV4dCA6IC0xOworICAgICAgICB9CiAgICAgfQogCiAgIGQxID0ga3dzZXQt PmRlbHRhOwogICBzcCA9IGt3c2V0LT50YXJnZXQgKyBsZW47CiAgIHRwID0gdGV4dCArIGxlbjsK LSAgY2hhciBnYzEgPSB0ciAodHJhbnMsIHNwWy0xXSk7Ci0gIGNoYXIgZ2MyID0gdHIgKHRyYW5z LCBzcFstMl0pOworICBpZiAodHJhbnMpCisgICAgeworICAgICAgZ2MxID0gdHJhbnNbVShzcFst MV0pXTsKKyAgICAgIGdjMiA9IHRyYW5zW1Uoc3BbLTJdKV07CisgICAgfQorICBlbHNlCisgICAg eworICAgICAgZ2MxID0gc3BbLTFdOworICAgICAgZ2MyID0gc3BbLTJdOworICAgIH0KKyAgc2tp cCA9IDA7CiAKICAgLyogU2lnbmlmaWNhbmNlIG9mIDEyOiAxIChpbml0aWFsIG9mZnNldCkgKyAx MCAoc2tpcCBsb29wKSArIDEgKG1kMikuICovCiAgIGlmIChzaXplID4gMTIgKiBsZW4pCiAgICAg LyogMTEgaXMgbm90IGEgYnVnLCB0aGUgaW5pdGlhbCBvZmZzZXQgaGFwcGVucyBvbmx5IG9uY2Uu ICovCi0gICAgZm9yIChlcCA9IHRleHQgKyBzaXplIC0gMTEgKiBsZW47IHRwIDw9IGVwOyApCisg ICAgZm9yIChlcCA9IHRleHQgKyBzaXplIC0gMTEgKiBsZW47OykKICAgICAgIHsKLSAgICAgICAg ZCA9IGQxW1UodHBbLTFdKV0sIHRwICs9IGQ7Ci0gICAgICAgIGQgPSBkMVtVKHRwWy0xXSldLCB0 cCArPSBkOwotICAgICAgICBpZiAoZCAhPSAwKQorICAgICAgICB3aGlsZSAodHAgPD0gZXApCiAg ICAgICAgICAgewotICAgICAgICAgICAgZCA9IGQxW1UodHBbLTFdKV0sIHRwICs9IGQ7Ci0gICAg ICAgICAgICBkID0gZDFbVSh0cFstMV0pXSwgdHAgKz0gZDsKLSAgICAgICAgICAgIGQgPSBkMVtV KHRwWy0xXSldLCB0cCArPSBkOwotICAgICAgICAgICAgaWYgKGQgIT0gMCkKKyAgICAgICAgICAg IGQgPSBkMVtVKHRwWy0xXSldOyBTSElGVCh0cCwgZCk7CisgICAgICAgICAgICBkID0gZDFbVSh0 cFstMV0pXTsgU0hJRlQodHAsIGQpOworICAgICAgICAgICAgaWYgKGQgPT0gMCkKKyAgICAgICAg ICAgICAgZ290byBmb3VuZDsKKyAgICAgICAgICAgIGQgPSBkMVtVKHRwWy0xXSldOyBTSElGVCh0 cCwgZCk7CisgICAgICAgICAgICBkID0gZDFbVSh0cFstMV0pXTsgU0hJRlQodHAsIGQpOworICAg ICAgICAgICAgZCA9IGQxW1UodHBbLTFdKV07IFNISUZUKHRwLCBkKTsKKyAgICAgICAgICAgIGlm IChkID09IDApCisgICAgICAgICAgICAgIGdvdG8gZm91bmQ7CisgICAgICAgICAgICBkID0gZDFb VSh0cFstMV0pXTsgU0hJRlQodHAsIGQpOworICAgICAgICAgICAgZCA9IGQxW1UodHBbLTFdKV07 IFNISUZUKHRwLCBkKTsKKyAgICAgICAgICAgIGQgPSBkMVtVKHRwWy0xXSldOyBTSElGVCh0cCwg ZCk7CisgICAgICAgICAgICBpZiAoZCA9PSAwKQorICAgICAgICAgICAgICBnb3RvIGZvdW5kOwor ICAgICAgICAgICAgLyogbWVtY2hhcigpIG9mIGdsaWJjIGlzIGZhc3RlciB0aGFuIHNlZWtpbmcg YnkgZGVsdGExIG9uCisgICAgICAgICAgICAgICBzb21lIHBsYXRmb3Jtcy4gIFdoZW4gdGhlcmUg aXMgbm8gY2hhbmNlIHRvIG1hdGNoIGZvciBhCisgICAgICAgICAgICAgICB3aGlsZSwgdXNlIGl0 IG9uIHRoZW0uICAqLworI2lmIGRlZmluZWQoX19HTElCQ19fKSAmJiAoZGVmaW5lZChfX2kzODZf XykgfHwgZGVmaW5lZChfX3g4Nl82NF9fKSkKKyAgICAgICAgICAgIGlmICghdHJhbnMpCiAgICAg ICAgICAgICAgIHsKLSAgICAgICAgICAgICAgICBkID0gZDFbVSh0cFstMV0pXSwgdHAgKz0gZDsK LSAgICAgICAgICAgICAgICBkID0gZDFbVSh0cFstMV0pXSwgdHAgKz0gZDsKLSAgICAgICAgICAg ICAgICBkID0gZDFbVSh0cFstMV0pXSwgdHAgKz0gZDsKLSAgICAgICAgICAgICAgICBpZiAoZCAh PSAwKQorICAgICAgICAgICAgICAgIHRwID0gbWVtY2hyICh0cCAtIDEsIGdjMSwgc2l6ZSArIHRl eHQgLSB0cCArIDEpOworICAgICAgICAgICAgICAgIGlmICh0cCkKICAgICAgICAgICAgICAgICAg IHsKLSAgICAgICAgICAgICAgICAgICAgLyogVHlwaWNhbGx5IG1lbWNociBpcyBmYXN0ZXIgdGhh biBzZWVraW5nIGJ5Ci0gICAgICAgICAgICAgICAgICAgICAgIGRlbHRhMSB3aGVuIHRoZXJlIGlz IG5vIGNoYW5jZSB0byBtYXRjaCBmb3IKLSAgICAgICAgICAgICAgICAgICAgICAgYSB3aGlsZS4g ICovCi0gICAgICAgICAgICAgICAgICAgIHRwLS07Ci0gICAgICAgICAgICAgICAgICAgIHRwID0g bWVtY2hyX3RyYW5zICh0cCwgZ2MxLCB0ZXh0ICsgc2l6ZSAtIHRwLCB0cmFucyk7Ci0gICAgICAg ICAgICAgICAgICAgIGlmICghIHRwKQotICAgICAgICAgICAgICAgICAgICAgIHJldHVybiAtMTsK LSAgICAgICAgICAgICAgICAgICAgdHArKzsKKyAgICAgICAgICAgICAgICAgICAgKyt0cDsKKyAg ICAgICAgICAgICAgICAgICAgZ290byBmb3VuZDsKICAgICAgICAgICAgICAgICAgIH0KKyAgICAg ICAgICAgICAgICBlbHNlCisgICAgICAgICAgICAgICAgICByZXR1cm4gLTE7CisgICAgICAgICAg ICAgIH0KKyAgICAgICAgICAgIGVsc2UKKyNlbmRpZgorICAgICAgICAgICAgICB7CisgICAgICAg ICAgICAgICAgZCA9IGQxW1UodHBbLTFdKV07IFNISUZUKHRwLCBkKTsKKyAgICAgICAgICAgICAg ICBkID0gZDFbVSh0cFstMV0pXTsgU0hJRlQodHAsIGQpOwogICAgICAgICAgICAgICB9CiAgICAg ICAgICAgfQotICAgICAgICBpZiAoYm1fZGVsdGEyX3NlYXJjaCAoJnRwLCBlcCwgc3AsIGxlbiwg dHJhbnMsIGdjMSwgZ2MyLCBkMSwga3dzZXQpKQotICAgICAgICAgIHJldHVybiB0cCAtIHRleHQ7 CisgICAgICAgIGJyZWFrOworICAgICAgZm91bmQ6CisjdW5kZWYgTEFTVF9TSElGVAorI2RlZmlu ZSBMQVNUX1NISUZUIFNISUZUKHRwLCBkKTsKKyAgICAgICAgaWYgKHRyYW5zKQorICAgICAgICAg IHsKKyN1bmRlZiBUUkFOUworI2RlZmluZSBUUkFOUyhjaCkgdHJhbnNbVShjaCldCisgICAgICAg ICAgICBCTV9ERUxUQTJfU0VBUkNIOworICAgICAgICAgIH0KKyAgICAgICAgZWxzZQorICAgICAg ICAgIHsKKyN1bmRlZiBUUkFOUworI2RlZmluZSBUUkFOUyhjaCkgY2gKKyAgICAgICAgICAgIEJN X0RFTFRBMl9TRUFSQ0g7CisgICAgICAgICAgfQogICAgICAgfQogCiAgIC8qIE5vdyB3ZSBoYXZl IG9ubHkgYSBmZXcgY2hhcmFjdGVycyBsZWZ0IHRvIHNlYXJjaC4gIFdlCkBAIC02MDUsMTEgKzY3 NiwyNCBAQCBibWV4ZWMgKGt3c2V0X3Qga3dzZXQsIGNoYXIgY29uc3QgKnRleHQsIHNpemVfdCBz aXplKQogICBkID0gZDFbVSh0cFstMV0pXTsKICAgd2hpbGUgKGQgPD0gZXAgLSB0cCkKICAgICB7 Ci0gICAgICBkID0gZDFbVSgodHAgKz0gZClbLTFdKV07CisgICAgICBTSElGVCh0cCwgZCk7Cisg ICAgICBkID0gZDFbVSh0cFstMV0pXTsKICAgICAgIGlmIChkICE9IDApCiAgICAgICAgIGNvbnRp bnVlOwotICAgICAgaWYgKGJtX2RlbHRhMl9zZWFyY2ggKCZ0cCwgZXAsIHNwLCBsZW4sIHRyYW5z LCBnYzEsIGdjMiwgTlVMTCwga3dzZXQpKQotICAgICAgICByZXR1cm4gdHAgLSB0ZXh0OworI3Vu ZGVmIExBU1RfU0hJRlQKKyNkZWZpbmUgTEFTVF9TSElGVAorICAgICAgaWYgKHRyYW5zKQorICAg ICAgICB7CisjdW5kZWYgVFJBTlMKKyNkZWZpbmUgVFJBTlMoY2gpIHRyYW5zW1UoY2gpXQorICAg ICAgICAgIEJNX0RFTFRBMl9TRUFSQ0g7CisgICAgICAgIH0KKyAgICAgIGVsc2UKKyAgICAgICAg eworI3VuZGVmIFRSQU5TCisjZGVmaW5lIFRSQU5TKGNoKSBjaAorICAgICAgICAgIEJNX0RFTFRB Ml9TRUFSQ0g7CisgICAgICAgIH0KICAgICB9CiAKICAgcmV0dXJuIC0xOwpAQCAtNjU5LDE3ICs3 NDMsMTkgQEAgY3dleGVjIChrd3NldF90IGt3c2V0LCBjaGFyIGNvbnN0ICp0ZXh0LCBzaXplX3Qg bGVuLCBzdHJ1Y3Qga3dzbWF0Y2ggKmt3c21hdGNoKQogICAgIHsKICAgICAgIGlmIChxbGltICYm IGVuZCA8PSBxbGltKQogICAgICAgICB7Ci0gICAgICAgICAgZW5kICs9IGQgLSAxOwotICAgICAg ICAgIHdoaWxlICgoZCA9IGRlbHRhW2MgPSAqZW5kXSkgJiYgZW5kIDwgcWxpbSkKKyAgICAgICAg ICBTSElGVChlbmQsIGQpOworICAgICAgICAgIHdoaWxlICgoZCA9IGRlbHRhW2MgPSBlbmRbLTFd XSkgJiYgZW5kIDw9IHFsaW0pCiAgICAgICAgICAgICB7Ci0gICAgICAgICAgICAgIGVuZCArPSBk OwotICAgICAgICAgICAgICBlbmQgKz0gZGVsdGFbVSgqZW5kKV07Ci0gICAgICAgICAgICAgIGVu ZCArPSBkZWx0YVtVKCplbmQpXTsKKyAgICAgICAgICAgICAgU0hJRlQoZW5kLCBkKTsKKyAgICAg ICAgICAgICAgZCA9IGRlbHRhW1UoZW5kWy0xXSldOyBTSElGVChlbmQsIGQpOworICAgICAgICAg ICAgICBkID0gZGVsdGFbVShlbmRbLTFdKV07IFNISUZUKGVuZCwgZCk7CiAgICAgICAgICAgICB9 Ci0gICAgICAgICAgKytlbmQ7CiAgICAgICAgIH0KICAgICAgIGVsc2UKLSAgICAgICAgZCA9IGRl bHRhW2MgPSAoZW5kICs9IGQpWy0xXV07CisgICAgICAgIHsKKyAgICAgICAgICBTSElGVChlbmQs IGQpOworICAgICAgICAgIGQgPSBkZWx0YVtjID0gZW5kWy0xXV07CisgICAgICAgIH0KICAgICAg IGlmIChkKQogICAgICAgICBjb250aW51ZTsKICAgICAgIGJlZyA9IGVuZCAtIDE7CkBAIC03MTgs NyArODA0LDggQEAgY3dleGVjIChrd3NldF90IGt3c2V0LCBjaGFyIGNvbnN0ICp0ZXh0LCBzaXpl X3QgbGVuLCBzdHJ1Y3Qga3dzbWF0Y2ggKmt3c21hdGNoKQogICBkID0gMTsKICAgd2hpbGUgKGxp bSAtIGVuZCA+PSBkKQogICAgIHsKLSAgICAgIGlmICgoZCA9IGRlbHRhW2MgPSAoZW5kICs9IGQp Wy0xXV0pICE9IDApCisgICAgICBTSElGVChlbmQsIGQpOworICAgICAgaWYgKChkID0gZGVsdGFb YyA9IGVuZFstMV1dKSAhPSAwKQogICAgICAgICBjb250aW51ZTsKICAgICAgIGJlZyA9IGVuZCAt IDE7CiAgICAgICBpZiAoISh0cmllID0gbmV4dFtjXSkpCg== --------_53584AF3000000006B30_MULTIPART_MIXED_-- From unknown Tue Sep 09 13:20:26 2025 X-Loop: help-debbugs@gnu.org Subject: bug#17230: [PATCH 1/2] grep: may also use Boyer-Moore algorithm for case-insensitive matching Resent-From: Paul Eggert Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Thu, 24 Apr 2014 01:50:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 17230 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: Norihiro Tanaka Cc: 17230@debbugs.gnu.org Received: via spool by 17230-submit@debbugs.gnu.org id=B17230.13983041644739 (code B ref 17230); Thu, 24 Apr 2014 01:50:02 +0000 Received: (at 17230) by debbugs.gnu.org; 24 Apr 2014 01:49:24 +0000 Received: from localhost ([127.0.0.1]:56687 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Wd8mx-0001EK-UP for submit@debbugs.gnu.org; Wed, 23 Apr 2014 21:49:24 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:47960) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Wd8mu-0001E8-6A for 17230@debbugs.gnu.org; Wed, 23 Apr 2014 21:49:21 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id E5F7339E8017; Wed, 23 Apr 2014 18:49:18 -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 HiZzlk07YKOp; Wed, 23 Apr 2014 18:49:16 -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 C74D739E8012; Wed, 23 Apr 2014 18:49:16 -0700 (PDT) Message-ID: <53586D9C.90007@cs.ucla.edu> Date: Wed, 23 Apr 2014 18:49:16 -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 References: <20140424025134.31FF.27F6AC2D@kcn.ne.jp> <535826E7.2070209@cs.ucla.edu> <20140424085935.6B3F.27F6AC2D@kcn.ne.jp> In-Reply-To: <20140424085935.6B3F.27F6AC2D@kcn.ne.jp> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -3.0 (---) 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: -3.0 (---) Norihiro Tanaka wrote: > Could you also > consider them, and run (A) instead of (B)? It means that overheads by > `yes' and `head' should be ignored. Sure, I did that, using the updated 17230.diff patch, and found that the patch slowed grep down on my machine. Your benchmark took about 0.58s real-time with grep master, and about about 0.89s real-time with the updated patch. I normally time with an AMD Phenom II X4 910e; this is a 65W Deneb processor released January 2010. I just now tried a different processor, an Intel Xeon E5620 under RHEL 6.5; this is an 80W Westmere-EP processor released March 2010. As with the AMD machine, I compiled with GCC 4.9.0 with default (-O2) optimizations. The same benchmark took about 0.40s real-time with the master, and about 0.83s real-time with the updated patch. > Though I don't analyze detail still, don't seem that overhead by check > for `trans' in `tr' function, which is called each time the comparison > of a character, can be ignorable. I haven't looked into the details either, but I'd guess that the compiler and/or branch prediction optimizes most of that stuff away. Even if it didn't, we could use inlining rather than macroexpansion to optimize it away by hand, though I'd rather not bother unless the performance improvement is worthwhile. By the way, the updated patch does pass 'make check', so my earlier version of the patch was incorrect and its timings should be ignored.