From: Kenta Murata <muraken@...>
Date: 2007-08-07T02:11:41+09:00
Subject: [ruby-dev:31354] Re: Bignum#to_s 	の Karatsuba 	基数変換による高速化

------=_Part_129521_1380815.1186420296292
Content-Type: text/plain; charset=ISO-2022-JP
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

むらたです．

07/08/07 に Yukihiro Matsumoto<matz@ruby-lang.org> さんは書きました:
> まつもと ゆきひろです
>
> In message "Re: [ruby-dev:31352] Re: Bignum#to_s        の Karatsuba     基数変換による高速化"
>     on Tue, 7 Aug 2007 00:50:27 +0900, "Kenta Murata" <muraken@gmail.com> writes:
>
> |[ruby-dev:31323] で提出したパッチに対して，テーブル周辺の処理を変更した
> |改良版をこしらえました．一つ目の添付パッチがそれです．この変更で，
> |いくらか高速化できましたので，以下で報告します．
>
> ありがとうございます。パッチはどうやらちょっと古いtrunkがベー
> スになっているようですが、すでに前回のパッチが取り込まれてい
> ますから、現在のtrunkとの差分を提出していただけませんか？

1.8.x のブランチで作業してました．

# 次の 1.8.x のリリースに混ざれればいいなぁと思いまして・・・

> とりあえずbigdivmodを非正規化オブジェクトでも動くようにする意
> 図はないので、bigsqrの修正で対応するのがよいのではないでしょ
> うか。こちらもパッチを作っていただけませんか？

bigsqr への修正も含めた現在の trunk に対する patch を添付しました．
どうぞ，お納めください．

ちなみに， [ruby-dev:31352] で使ったテストスクリプトと同じものを
trunk 版で実行して時間を計ってみると (CFLAGS は同じ)

$ time ./ruby ../ruby_1_8_bignum_to_s/test_bignum_endoh.rb > res
real    9m24.412s
user    3m24.145s
sys     0m0.048s

さらに1分ほど速くなったわけですが，制御構造が何一つ無いスクリプトでも
YARV 効果が現れるんですね．初めて 1.9 を動かしましたが，驚きです．

-- 
Kenta Murata
OpenPGP FP = FA26 35D7 4F98 3498 0810 E0D5 F213 966F E9EB 0BCC

------=_Part_129521_1380815.1186420296292
Content-Type: application/octet-stream; 
	name=bignum_to_s_karatsuba_20070807.patch
Content-Transfer-Encoding: base64
X-Attachment-Id: f_f517vvjw
Content-Disposition: attachment; filename="bignum_to_s_karatsuba_20070807.patch"

SW5kZXg6IGJpZ251bS5jCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09
PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIGJpZ251bS5jCSjjg6rjg5Pjgrjjg6fjg7Mg
MTI4ODkpCisrKyBiaWdudW0uYwko5L2c5qWt44Kz44OU44O8KQpAQCAtNTk2LDE4OSArNTk2LDI5
OCBAQAogCiBjb25zdCBjaGFyIHJ1YnlfZGlnaXRtYXBbXSA9ICIwMTIzNDU2Nzg5YWJjZGVmZ2hp
amtsbW5vcHFyc3R1dnd4eXoiOwogCitzdGF0aWMgVkFMVUUgYmlnc3FyKFZBTFVFIHgpOworc3Rh
dGljIHZvaWQgYmlnZGl2bW9kKFZBTFVFIHgsIFZBTFVFIHksIFZBTFVFICpkaXZwLCBWQUxVRSAq
bW9kcCk7CisKKyNkZWZpbmUgUE9XMl9QKHgpICgoKHgpJigoeCktMSkpPT0wKQorCiBzdGF0aWMg
aW5saW5lIGludAotYmlnMnN0cl9ub3JtYWwoVkFMVUUgeCwgbG9uZyBqLCBpbnQgYmFzZSwgaW50
IGhiYXNlLCBjaGFyICpzLCBpbnQgdHJpbSkKK29uZXMocmVnaXN0ZXIgdW5zaWduZWQgbG9uZyB4
KQogewotICAgIGxvbmcgaSA9IFJCSUdOVU0oeCktPmxlbjsKLSAgICBCRElHSVQgKmRzID0gQkRJ
R0lUUyh4KTsKKyNpZiBTSVpFT0ZfVUxPTkcgPT0gOAorIyBkZWZpbmUgTUFTS181NSAweDU1NTU1
NTU1NTU1NTU1NTVVTAorIyBkZWZpbmUgTUFTS18zMyAweDMzMzMzMzMzMzMzMzMzMzNVTAorIyBk
ZWZpbmUgTUFTS18wZiAweDBmMGYwZjBmMGYwZjBmMGZVTAorI2Vsc2UKKyMgZGVmaW5lIE1BU0tf
NTUgMHg1NTU1NTU1NVVMCisjIGRlZmluZSBNQVNLXzMzIDB4MzMzMzMzMzNVTAorIyBkZWZpbmUg
TUFTS18wZiAweDBmMGYwZjBmVUwKKyNlbmRpZgorICAgIHggLT0gKHggPj4gMSkgJiBNQVNLXzU1
OworICAgIHggPSAoKHggPj4gMikgJiBNQVNLXzMzKSArICh4ICYgTUFTS18zMyk7CisgICAgeCA9
ICgoeCA+PiA0KSArIHgpICYgTUFTS18wZjsKKyAgICB4ICs9ICh4ID4+IDgpOworICAgIHggKz0g
KHggPj4gMTYpOworI2lmIFNJWkVPRl9VTE9ORyA9PSA4CisgICAgeCArPSAoeCA+PiAzMik7Cisj
ZW5kaWYKKyAgICByZXR1cm4gKGludCkoeCAmIDB4N2YpOworI3VuZGVmIE1BU0tfMGYKKyN1bmRl
ZiBNQVNLXzMzCisjdW5kZWYgTUFTS181NQorfQogCi0gICAgd2hpbGUgKGkgJiYgaiA+IDEpIHsK
LSAgICAgICBsb25nIGsgPSBpOwotICAgICAgIEJESUdJVF9EQkwgbnVtID0gMDsKK3N0YXRpYyBp
bmxpbmUgdW5zaWduZWQgbG9uZworbmV4dF9wb3cyKHJlZ2lzdGVyIHVuc2lnbmVkIGxvbmcgeCkK
K3sKKyAgICB4IHw9IHggPj4gMTsKKyAgICB4IHw9IHggPj4gMjsKKyAgICB4IHw9IHggPj4gNDsK
KyAgICB4IHw9IHggPj4gODsKKyAgICB4IHw9IHggPj4gMTY7CisjaWYgU0laRU9GX1VMT05HID09
IDgKKyAgICB4IHw9IHggPj4gMzI7CisjZW5kaWYKKyAgICByZXR1cm4geCArIDE7Cit9CiAKLSAg
ICAgICB3aGlsZSAoay0tKSB7Ci0gICAgICAgICAgIG51bSA9IEJJR1VQKG51bSkgKyBkc1trXTsK
LSAgICAgICAgICAgZHNba10gPSAoQkRJR0lUKShudW0gLyBoYmFzZSk7Ci0gICAgICAgICAgIG51
bSAlPSBoYmFzZTsKLSAgICAgICB9Ci0gICAgICAgaWYgKHRyaW0gJiYgZHNbaS0xXSA9PSAwKSBp
LS07Ci0gICAgICAgayA9IFNJWkVPRl9CRElHSVRTOwotICAgICAgIHdoaWxlIChrLS0pIHsKLSAg
ICAgICAgICAgc1stLWpdID0gcnVieV9kaWdpdG1hcFtudW0gJSBiYXNlXTsKLSAgICAgICAgICAg
bnVtIC89IGJhc2U7Ci0gICAgICAgICAgIGlmICghdHJpbSAmJiBqIDwgMSkgYnJlYWs7Ci0gICAg
ICAgICAgIGlmICh0cmltICYmIGkgPT0gMCAmJiBudW0gPT0gMCkgYnJlYWs7Ci0gICAgICAgfQot
ICAgIH0KLSAgICByZXR1cm4gajsKK3N0YXRpYyBpbmxpbmUgaW50CitmbG9vcl9sb2cyKHJlZ2lz
dGVyIHVuc2lnbmVkIGxvbmcgeCkKK3sKKyAgICB4IHw9IHggPj4gMTsKKyAgICB4IHw9IHggPj4g
MjsKKyAgICB4IHw9IHggPj4gNDsKKyAgICB4IHw9IHggPj4gODsKKyAgICB4IHw9IHggPj4gMTY7
CisjaWYgU0laRU9GX1VMT05HID09IDgKKyAgICB4IHw9IHggPj4gMzI7CisjZW5kaWYKKyAgICBy
ZXR1cm4gKGludClvbmVzKHgpIC0gMTsKIH0KIAotI2RlZmluZSBLQVJBVFNVQkFfRElHSVRTIDEy
OAorc3RhdGljIGlubGluZSBpbnQKK2NlaWxfbG9nMihyZWdpc3RlciB1bnNpZ25lZCBsb25nIHgp
Cit7CisgICAgcmV0dXJuIGZsb29yX2xvZzIoeCkgKyAhUE9XMl9QKHgpOworfQorCisjZGVmaW5l
IExPRzJfS0FSQVRTVUJBX0RJR0lUUyA3CisjZGVmaW5lIEtBUkFUU1VCQV9ESUdJVFMgKDFMPDxM
T0cyX0tBUkFUU1VCQV9ESUdJVFMpCiAjZGVmaW5lIE1BWF9CSUcyU1RSX1RBQkxFX0VOVFJJRVMg
NjQKLXN0YXRpYyBWQUxVRSBiaWcyc3RyX3RhYmxlXzBbMzctMl1bTUFYX0JJRzJTVFJfVEFCTEVf
RU5UUklFU107Ci0jZGVmaW5lIGJpZzJzdHJfdGFibGUgKGJpZzJzdHJfdGFibGVfMC0yKQogCi1z
dGF0aWMgVkFMVUUgYmlnc3FyKFZBTFVFIHgpOwotc3RhdGljIHZvaWQgYmlnZGl2bW9kKFZBTFVF
IHgsIFZBTFVFIHksIFZBTFVFICpkaXZwLCBWQUxVRSAqbW9kcCk7CitzdGF0aWMgVkFMVUUgYmln
MnN0cl9wb3dlcl9jYWNoZVszNV1bTUFYX0JJRzJTVFJfVEFCTEVfRU5UUklFU107CiAKLXN0YXRp
YyBpbmxpbmUgaW50Ci1iaWcyc3RyX2thcmF0c3ViYShWQUxVRSB4LCBpbnQgbiwgaW50IGJhc2Us
IGludCBoYmFzZSwgY2hhciAqcywgaW50IHRyaW0pCitzdGF0aWMgdm9pZAorcG93ZXJfY2FjaGVf
aW5pdCh2b2lkKQogewotICAgIGxvbmcgaSwgaiwgaywgYnNfbGVuLCBzaWduID0gUkJJR05VTSh4
KS0+c2lnbjsKLSAgICB2b2xhdGlsZSBWQUxVRSB0ID0gYmlnMnN0cl90YWJsZVtiYXNlXVswXSwg
dDI7Ci0gICAgVkFMVUUgKmFzLCAqYnMsIHEsIHI7CisgICAgaW50IGksIGo7CisgICAgZm9yIChp
ID0gMDsgaSA8IDM1OyArK2kpIHsKKyAgICAgICAgYmlnMnN0cl9wb3dlcl9jYWNoZVtpXVswXSA9
CisgICAgICAgICAgICByYl9iaWdfcG93KHJiX2ludDJiaWcoaSsyKSwgSU5UMkZJWChLQVJBVFNV
QkFfRElHSVRTKSk7CisgICAgICAgIHJiX2dsb2JhbF92YXJpYWJsZSgmYmlnMnN0cl9wb3dlcl9j
YWNoZVtpXVswXSk7CisgICAgICAgIGZvciAoaiA9IDE7IGogPCBNQVhfQklHMlNUUl9UQUJMRV9F
TlRSSUVTOyArK2opIHsKKyAgICAgICAgICAgIGJpZzJzdHJfcG93ZXJfY2FjaGVbaV1bal0gPSBR
bmlsOworICAgICAgICB9CisgICAgfQorfQogCi0gICAgaiA9IFJCSUdOVU0odCktPmxlbjsKLSAg
ICBmb3IgKGk9MDsgaiA8PSBSQklHTlVNKHgpLT5sZW47IGkrKykgaiAqPSAyOworc3RhdGljIGlu
bGluZSBWQUxVRQorcG93ZXJfY2FjaGVfZ2V0X3Bvd2VyMChpbnQgYmFzZSwgaW50IGkpCit7Cisg
ICAgaWYgKE5JTF9QKGJpZzJzdHJfcG93ZXJfY2FjaGVbYmFzZSAtIDJdW2ldKSkgeworICAgICAg
ICBiaWcyc3RyX3Bvd2VyX2NhY2hlW2Jhc2UgLSAyXVtpXSA9CisgICAgICAgICAgICBiaWdzcXIo
cG93ZXJfY2FjaGVfZ2V0X3Bvd2VyMChiYXNlLCBpIC0gMSkpOworICAgICAgICByYl9nbG9iYWxf
dmFyaWFibGUoJmJpZzJzdHJfcG93ZXJfY2FjaGVbYmFzZSAtIDJdW2ldKTsKKyAgICB9CisgICAg
cmV0dXJuIGJpZzJzdHJfcG93ZXJfY2FjaGVbYmFzZSAtIDJdW2ldOworfQogCi0gICAgYXMgPSBB
TExPQ0FfTihWQUxVRSwgaSk7CitzdGF0aWMgVkFMVUUKK3Bvd2VyX2NhY2hlX2dldF9wb3dlcihp
bnQgYmFzZSwgbG9uZyBuMSwgbG9uZyogbTEpCit7CisgICAgbG9uZyBpLCBqLCBtOworICAgIFZB
TFVFIHQ7CiAKLSAgICBmb3IgKGk9MCxqPTE7IDsgaSsrLGoqPTIpIHsKLSAgICAgICBhc1tpXSA9
IHQ7Ci0gICAgICAgaWYgKGJpZzJzdHJfdGFibGVbYmFzZV1baSArIDFdKSB7Ci0gICAgICAgICAg
IHQyID0gYmlnMnN0cl90YWJsZVtiYXNlXVtpICsgMV07Ci0gICAgICAgfQotICAgICAgIGVsc2Ug
ewotICAgICAgICAgICB0MiA9IGJpZ3Nxcih0KTsKLSAgICAgICAgICAgaWYgKGkgKyAxIDwgTUFY
X0JJRzJTVFJfVEFCTEVfRU5UUklFUykgewotICAgICAgICAgICAgICAgYmlnMnN0cl90YWJsZVti
YXNlXVtpICsgMV0gPSB0MjsKLSAgICAgICAgICAgICAgIHJiX2dsb2JhbF92YXJpYWJsZSgmYmln
MnN0cl90YWJsZVtiYXNlXVtpICsgMV0pOwotICAgICAgICAgICB9Ci0gICAgICAgfQotICAgICAg
IGlmIChSQklHTlVNKHgpLT5sZW4gPCBSQklHTlVNKHQyKS0+bGVuKSBicmVhazsKLSAgICAgICB0
ID0gdDI7CisgICAgaWYgKG4xIDw9IEtBUkFUU1VCQV9ESUdJVFMpCisgICAgICAgIHJiX2J1Zygi
bjEgPiBLQVJBVFNVQkFfRElHSVRTIik7CisKKyAgICBtID0gY2VpbF9sb2cyKG4xKTsKKyAgICBp
ZiAobTEpICptMSA9IDEgPDwgbTsKKyAgICBpID0gbSAtIExPRzJfS0FSQVRTVUJBX0RJR0lUUzsK
KyAgICBpZiAoaSA+PSBNQVhfQklHMlNUUl9UQUJMRV9FTlRSSUVTKQorICAgICAgICBpID0gTUFY
X0JJRzJTVFJfVEFCTEVfRU5UUklFUyAtIDE7CisgICAgdCA9IHBvd2VyX2NhY2hlX2dldF9wb3dl
cjAoYmFzZSwgaSk7CisKKyAgICBqID0gS0FSQVRTVUJBX0RJR0lUUyooMSA8PCBpKTsKKyAgICB3
aGlsZSAobjEgPiBqKSB7CisgICAgICAgIHQgPSBiaWdzcXIodCk7CisgICAgICAgIGogKj0gMjsK
ICAgICB9CisgICAgcmV0dXJuIHQ7Cit9CiAKLSAgICBic19sZW4gPSBqICogMjsKLSAgICBicyA9
IEFMTE9DQV9OKFZBTFVFLCBic19sZW4pOwotICAgIGJzWzBdID0geDsKLSAgICBSQklHTlVNKHgp
LT5zaWduID0gMTsKLSAgICBmb3IgKDsgaj4wOyBpLS0sIGovPTIpIHsKLSAgICAgICBmb3IgKGs9
MDsgazxic19sZW47IGsrPWoqMikgewotICAgICAgICAgICBiaWdkaXZtb2QoYnNba10sIGFzW2ld
LCAmcSwgJnIpOwotICAgICAgICAgICBic1trXSA9IHE7Ci0gICAgICAgICAgIGJzW2sgKyBqXSA9
IHI7Ci0gICAgICAgfQorLyogYmlnMnN0cl9tdXJha2VuX2ZpbmRfbjEKKyAqCisgKiBMZXQgYSBu
YXR1cmFsIG51bWJlciB4IGlzIGdpdmVuIGJ5OgorICogeCA9IDJeMCAqIHhfMCArIDJeMSAqIHhf
MSArIC4uLiArIDJeKEIqbl8wIC0gMSkgKiB4X3tCKm5fMCAtIDF9LAorICogd2hlcmUgQiBpcyBC
SVRTUEVSRElHIChpLmUuIEJESUdJVFMqQ0hBUl9CSVQpIGFuZCBuXzAgaXMKKyAqIFJCSUdOVU0o
eCktPmxlbi4KKyAqCisgKiBOb3csIHdlIGFzc3VtZSBuXzEgPSBtaW5fbiBceyBuIHwgMl4oQipu
XzAvMikgPD0gYl8xXihuXzEpIFx9LCBzbworICogaXQgaXMgcmVhbGl6ZWQgdGhhdCAyXihCKm5f
MCkgPD0ge2JfMX1eezIqbl8xfSwgd2hlcmUgYl8xIGlzIGEKKyAqIGdpdmVuIHJhZGl4IG51bWJl
ci4gQW5kIHRoZW4sIHdlIGhhdmUgbl8xIDw9IChCKm5fMCkgLworICogKDIqbG9nXzIoYl8xKSks
IHRoZXJlZm9yZSBuXzEgaXMgZ2l2ZW4gYnkgY2VpbCgoQipuXzApIC8KKyAqICgyKmxvZ18yKGJf
MSkpKS4KKyAqLworc3RhdGljIGxvbmcKK2JpZzJzdHJfZmluZF9uMShWQUxVRSB4LCBpbnQgYmFz
ZSkKK3sKKyAgICBzdGF0aWMgY29uc3QgZG91YmxlIGxvZ18yW10gPSB7CisgICAgICAgIDEuMCwg
ICAgICAgICAgICAgIDEuNTg0OTYyNTAwNzIxMTYsIDIuMCwKKyAgICAgICAgMi4zMjE5MjgwOTQ4
ODczNiwgMi41ODQ5NjI1MDA3MjEsICAgMi41ODQ5NjI1MDA3MjExNiwKKyAgICAgICAgMi44MDcz
NTQ5MjIwNTc2LCAgMy4wLCAgICAgICAgICAgICAgMy4xNjk5MjUwMDE0NDIzMSwKKyAgICAgICAg
My4zMjE5MjgwOTQ4ODczNiwgMy40NTk0MzE2MTg2MzczLCAgMy41ODQ5NjI1MDA3MjExNiwKKyAg
ICAgICAgMy43MDA0Mzk3MTgxNDEwOSwgMy44MDczNTQ5MjIwNTc2LCAgMy45MDY4OTA1OTU2MDg1
MiwKKyAgICAgICAgNC4wLCAgICAgICAgICAgICAgNC4wODc0NjI4NDEyNTAzNCwgNC4xNjk5MjUw
MDE0NDIzMSwKKyAgICAgICAgNC4yNDc5Mjc1MTM0NDM1OSwgNC4zMjE5MjgwOTQ4ODczNiwgNC4z
OTIzMTc0MjI3Nzg3NiwKKyAgICAgICAgNC40NTk0MzE2MTg2MzczLCAgNC41MjM1NjE5NTYwNTcw
MSwgNC41ODQ5NjI1MDA3MjExNiwKKyAgICAgICAgNC42NDM4NTYxODk3NzQ3MiwgNC43MDA0Mzk3
MTgxNDEwOSwgNC43NTQ4ODc1MDIxNjM0NywKKyAgICAgICAgNC44MDczNTQ5MjIwNTc2LCAgNC44
NTc5ODA5OTUxMjc1NywgNC45MDY4OTA1OTU2MDg1MiwKKyAgICAgICAgNC45NTQxOTYzMTAzODY4
OCwgNS4wLCAgICAgICAgICAgICAgNS4wNDQzOTQxMTkzNTg0NSwKKyAgICAgICAgNS4wODc0NjI4
NDEyNTAzNCwgNS4xMjkyODMwMTY5NDQ5NywgNS4xNjk5MjUwMDE0NDIzMQorICAgIH07CisgICAg
bG9uZyBiaXRzLCBuLCBpOworCisgICAgaWYgKGJhc2UgPCAyICYmIDM2IDwgYmFzZSkKKyAgICAg
ICAgcmJfYnVnKCJpbGxlZ2FsIHJhZGl4ICVkIiwgYmFzZSk7CisKKyAgICBpZiAoRklYTlVNX1Ao
eCkpIHsKKyAgICAgICAgYml0cyA9IChTSVpFT0ZfTE9ORypDSEFSX0JJVCAtIDEpLzIgKyAxOwog
ICAgIH0KLSAgICBSQklHTlVNKHgpLT5zaWduID0gc2lnbjsKKyAgICBlbHNlIGlmIChCSUdaRVJP
UCh4KSkgeworICAgICAgICByZXR1cm4gMDsKKyAgICB9CisgICAgZWxzZSB7CisgICAgICAgIGJp
dHMgPSBCSVRTUEVSRElHKlJCSUdOVU0oeCktPmxlbjsKKyAgICB9CiAKLSAgICBqID0gMDsKLSAg
ICB3aGlsZShSQklHTlVNKGJzW2pdKS0+bGVuID09IDEgJiYgQkRJR0lUUyhic1tqXSlbMF0gPT0g
MCkgaisrOwotICAgIGZvciAoaT1ic19sZW4tMTsgaT5qOyBpLS0pIHsKLSAgICAgICBrID0gYmln
MnN0cl9ub3JtYWwoCi0gICAgICAgICAgIGJzW2ldLCBLQVJBVFNVQkFfRElHSVRTLCBiYXNlLCBo
YmFzZSwKLSAgICAgICAgICAgcyArIG4gLSBLQVJBVFNVQkFfRElHSVRTLCBRZmFsc2UpOwotICAg
ICAgIG4gLT0gS0FSQVRTVUJBX0RJR0lUUyAtIGs7CisgICAgcmV0dXJuIChsb25nKWNlaWwoYml0
cy8oMipsb2dfMltiYXNlIC0gMl0pKTsKK30KKworc3RhdGljIGxvbmcKK2JpZzJzdHJfb3JpZyhW
QUxVRSB4LCBpbnQgYmFzZSwgY2hhciogcHRyLCBsb25nIGxlbiwgbG9uZyBoYmFzZSwgaW50IHRy
aW0pCit7CisgICAgbG9uZyBpID0gUkJJR05VTSh4KS0+bGVuLCBqID0gbGVuOworICAgIEJESUdJ
VCogZHMgPSBCRElHSVRTKHgpOworCisgICAgd2hpbGUgKGkgJiYgaiA+IDApIHsKKyAgICAgICAg
bG9uZyBrID0gaTsKKyAgICAgICAgQkRJR0lUX0RCTCBudW0gPSAwOworCisgICAgICAgIHdoaWxl
IChrLS0pIHsgICAgICAgICAgICAgICAvKiB4IC8gaGJhc2UgKi8KKyAgICAgICAgICAgIG51bSA9
IEJJR1VQKG51bSkgKyBkc1trXTsKKyAgICAgICAgICAgIGRzW2tdID0gKEJESUdJVCkobnVtIC8g
aGJhc2UpOworICAgICAgICAgICAgbnVtICU9IGhiYXNlOworICAgICAgICB9CisgICAgICAgIGlm
ICh0cmltICYmIGRzW2ktMV0gPT0gMCkgaS0tOworICAgICAgICBrID0gU0laRU9GX0JESUdJVFM7
CisgICAgICAgIHdoaWxlIChrLS0pIHsKKyAgICAgICAgICAgIHB0clstLWpdID0gcnVieV9kaWdp
dG1hcFtudW0gJSBiYXNlXTsKKyAgICAgICAgICAgIG51bSAvPSBiYXNlOworICAgICAgICAgICAg
aWYgKCF0cmltICYmIGogPD0gMCkgYnJlYWs7CisgICAgICAgICAgICBpZiAodHJpbSAmJiBpID09
IDAgJiYgbnVtID09IDApIGJyZWFrOworICAgICAgICB9CiAgICAgfQotICAgIG4gPSBiaWcyc3Ry
X25vcm1hbChic1tqXSwgbiwgYmFzZSwgaGJhc2UsIHMsIHRyaW0pOworICAgIGlmICh0cmltKSB7
CisgICAgICAgIHdoaWxlIChwdHJbal0gPT0gJzAnKSBqKys7CisgICAgICAgIE1FTU1PVkUocHRy
LCBwdHIgKyBqLCBjaGFyLCBsZW4gLSBqKTsKKyAgICAgICAgbGVuIC09IGo7CisgICAgfQorICAg
IHJldHVybiBsZW47Cit9CiAKLSAgICByZXR1cm4gbjsKK3N0YXRpYyBsb25nCitiaWcyc3RyX2th
cmF0c3ViYShWQUxVRSB4LCBpbnQgYmFzZSwgY2hhciogcHRyLAorICAgICAgICAgICAgICAgICAg
bG9uZyBuMSwgbG9uZyBsZW4sIGxvbmcgaGJhc2UsIGludCB0cmltKQoreworICAgIGxvbmcgbGgs
IGxsLCBtMTsKKyAgICBWQUxVRSBiLCBxLCByOworCisgICAgaWYgKEZJWE5VTV9QKHgpKSB7Cisg
ICAgICAgIFZBTFVFIHN0ciA9IHJiX2ZpeDJzdHIoeCwgYmFzZSk7CisgICAgICAgIGNoYXIqIHN0
cl9wdHIgPSBSU1RSSU5HX1BUUihzdHIpOworICAgICAgICBsb25nIHN0cl9sZW4gPSBSU1RSSU5H
X0xFTihzdHIpOworICAgICAgICBpZiAodHJpbSkgeworICAgICAgICAgICAgaWYgKEZJWDJJTlQo
eCkgPT0gMCkgcmV0dXJuIDA7CisgICAgICAgICAgICBNRU1DUFkocHRyLCBzdHJfcHRyLCBjaGFy
LCBzdHJfbGVuKTsKKyAgICAgICAgICAgIHJldHVybiBzdHJfbGVuOworICAgICAgICB9CisgICAg
ICAgIGVsc2UgeworICAgICAgICAgICAgbWVtc2V0KHB0ciwgJzAnLCBsZW4gLSBzdHJfbGVuKTsK
KyAgICAgICAgICAgIE1FTUNQWShwdHIgKyBsZW4gLSBzdHJfbGVuLCBzdHJfcHRyLCBjaGFyLCBz
dHJfbGVuKTsKKyAgICAgICAgICAgIHJldHVybiBsZW47CisgICAgICAgIH0KKyAgICB9CisgICAg
aWYgKEJJR1pFUk9QKHgpKSB7CisgICAgICAgIGlmICh0cmltKSByZXR1cm4gMDsKKyAgICAgICAg
ZWxzZSB7CisgICAgICAgICAgICBtZW1zZXQocHRyLCAnMCcsIGxlbik7CisgICAgICAgICAgICBy
ZXR1cm4gbGVuOworICAgICAgICB9CisgICAgfQorCisgICAgaWYgKG4xIDw9IEtBUkFUU1VCQV9E
SUdJVFMpIHsKKyAgICAgICAgcmV0dXJuIGJpZzJzdHJfb3JpZyh4LCBiYXNlLCBwdHIsIGxlbiwg
aGJhc2UsIHRyaW0pOworICAgIH0KKworICAgIGIgPSBwb3dlcl9jYWNoZV9nZXRfcG93ZXIoYmFz
ZSwgbjEsICZtMSk7CisgICAgYmlnZGl2bW9kKHgsIGIsICZxLCAmcik7CisgICAgbGggPSBiaWcy
c3RyX2thcmF0c3ViYShxLCBiYXNlLCBwdHIsICAgICAgKGxlbiAtIG0xKS8yLAorICAgICAgICAg
ICAgICAgICAgICAgICAgICAgbGVuIC0gbTEsIGhiYXNlLCB0cmltKTsKKyAgICBsbCA9IGJpZzJz
dHJfa2FyYXRzdWJhKHIsIGJhc2UsIHB0ciArIGxoLCBtMS8yLAorICAgICAgICAgICAgICAgICAg
ICAgICAgICAgbTEsICAgICAgIGhiYXNlLCAhbGggJiYgdHJpbSk7CisKKyAgICByZXR1cm4gbGgg
KyBsbDsKIH0KIAogVkFMVUUKIHJiX2JpZzJzdHIwKFZBTFVFIHgsIGludCBiYXNlLCBpbnQgdHJp
bSkKIHsKLSAgICB2b2xhdGlsZSBWQUxVRSB0OwotICAgIGxvbmcgaSwgaiwgaGJhc2U7Ci0gICAg
VkFMVUUgc3M7Ci0gICAgY2hhciAqczsKKyAgICBpbnQgb2ZmOworICAgIFZBTFVFIHNzLCB4eDsK
KyAgICBsb25nIG4xLCBsZW4sIGhiYXNlOworICAgIGNoYXIqIHB0cjsKIAogICAgIGlmIChGSVhO
VU1fUCh4KSkgewotCXJldHVybiByYl9maXgyc3RyKHgsIGJhc2UpOworICAgICAgICByZXR1cm4g
cmJfZml4MnN0cih4LCBiYXNlKTsKICAgICB9CiAgICAgaWYgKEJJR1pFUk9QKHgpKSB7Ci0JcmV0
dXJuIHJiX3N0cl9uZXcyKCIwIik7CisgICAgICAgIHJldHVybiByYl9zdHJfbmV3MigiMCIpOwog
ICAgIH0KLSAgICBpID0gUkJJR05VTSh4KS0+bGVuOwotICAgIGogPSBTSVpFT0ZfQkRJR0lUUypD
SEFSX0JJVCppOwotICAgIHN3aXRjaCAoYmFzZSkgewotICAgICAgY2FzZSAyOiBicmVhazsKLSAg
ICAgIGNhc2UgMzoKLQlqID0gaiAqIDUzTCAvIDg0ICsgMTsKLQlicmVhazsKLSAgICAgIGNhc2Ug
NDogY2FzZSA1OiBjYXNlIDY6IGNhc2UgNzoKLQlqID0gKGogKyAxKSAvIDI7Ci0JYnJlYWs7Ci0g
ICAgICBjYXNlIDg6IGNhc2UgOToKLQlqID0gKGogKyAyKSAvIDM7Ci0JYnJlYWs7Ci0gICAgICBj
YXNlIDEwOiBjYXNlIDExOiBjYXNlIDEyOiBjYXNlIDEzOiBjYXNlIDE0OiBjYXNlIDE1OgotCWog
PSBqICogMjhMIC8gOTMgKyAxOwotCWJyZWFrOwotICAgICAgY2FzZSAxNjogY2FzZSAxNzogY2Fz
ZSAxODogY2FzZSAxOTogY2FzZSAyMDogY2FzZSAyMToKLSAgICAgIGNhc2UgMjI6IGNhc2UgMjM6
IGNhc2UgMjQ6IGNhc2UgMjU6IGNhc2UgMjY6IGNhc2UgMjc6Ci0gICAgICBjYXNlIDI4OiBjYXNl
IDI5OiBjYXNlIDMwOiBjYXNlIDMxOgotCWogPSAoaiArIDMpIC8gNDsKLQlicmVhazsKLSAgICAg
IGNhc2UgMzI6IGNhc2UgMzM6IGNhc2UgMzQ6IGNhc2UgMzU6IGNhc2UgMzY6Ci0JaiA9IChqICsg
NCkgLyA1OwotCWJyZWFrOwotICAgICAgZGVmYXVsdDoKLQlyYl9yYWlzZShyYl9lQXJnRXJyb3Is
ICJpbGxlZ2FsIHJhZGl4ICVkIiwgYmFzZSk7Ci0JYnJlYWs7Ci0gICAgfQotICAgIGorKzsJCQkv
KiBzcGFjZSBmb3Igc2lnbiAqLwogCi0gICAgaGJhc2UgPSBiYXNlICogYmFzZTsKKyAgICBpZiAo
YmFzZSA8IDIgJiYgMzYgPCBiYXNlKQorICAgICAgICByYl9yYWlzZShyYl9lQXJnRXJyb3IsICJp
bGxlZ2FsIHJhZGl4ICVkIiwgYmFzZSk7CisKKyAgICBuMSA9IGJpZzJzdHJfZmluZF9uMSh4LCBi
YXNlKTsKKyAgICBzcyA9IHJiX3N0cl9uZXcoMCwgMipuMSArIDEpOyAvKiBwbHVzIG9uZSBmb3Ig
c2lnbiAqLworICAgIHB0ciA9IFJTVFJJTkdfUFRSKHNzKTsKKyAgICBwdHJbMF0gPSBSQklHTlVN
KHgpLT5zaWduID8gJysnIDogJy0nOworCisgICAgaGJhc2UgPSBiYXNlKmJhc2U7CiAjaWYgU0la
RU9GX0JESUdJVFMgPiAyCiAgICAgaGJhc2UgKj0gaGJhc2U7CiAjZW5kaWYKLQotICAgIHQgPSBy
Yl9iaWdfY2xvbmUoeCk7Ci0gICAgc3MgPSByYl9zdHJfbmV3KDAsIGorMSk7Ci0gICAgcyA9IFJT
VFJJTkdfUFRSKHNzKTsKLQotICAgIHNbMF0gPSBSQklHTlVNKHgpLT5zaWduID8gJysnIDogJy0n
OwotICAgIGlmIChSQklHTlVNKHgpLT5sZW4gPiBSQklHTlVNKGJpZzJzdHJfdGFibGVbYmFzZV1b
MF0pLT5sZW4gKiA0KSB7Ci0gICAgICAgaiA9IGJpZzJzdHJfa2FyYXRzdWJhKHQsIGosIGJhc2Us
IGhiYXNlLCBzLCB0cmltKTsKKyAgICBvZmYgPSAhUlRFU1QodHJpbSkgJiYgIVJCSUdOVU0oeCkt
PnNpZ247CisgICAgeHggPSByYl9iaWdfY2xvbmUoeCk7CisgICAgUkJJR05VTSh4eCktPnNpZ24g
PSAxOworICAgIGlmIChuMSA8PSBLQVJBVFNVQkFfRElHSVRTKSB7CisgICAgICAgIGxlbiA9IGJp
ZzJzdHJfb3JpZyh4eCwgYmFzZSwgcHRyICsgb2ZmLCAyKm4xLCBoYmFzZSwgUlRFU1QodHJpbSkp
OwogICAgIH0KICAgICBlbHNlIHsKLSAgICAgICBqID0gYmlnMnN0cl9ub3JtYWwodCwgaiwgYmFz
ZSwgaGJhc2UsIHMsIHRyaW0pOworICAgICAgICBsZW4gPSBiaWcyc3RyX2thcmF0c3ViYSh4eCwg
YmFzZSwgcHRyICsgb2ZmLCBuMSwKKyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgMipu
MSwgaGJhc2UsIFJURVNUKHRyaW0pKTsKICAgICB9Ci0gICAgaWYgKHRyaW0pIHt3aGlsZSAoc1tq
XSA9PSAnMCcpIGorKzt9Ci0gICAgaSA9IFJTVFJJTkdfTEVOKHNzKSAtIGo7Ci0gICAgaWYgKFJC
SUdOVU0oeCktPnNpZ24pIHsKLQltZW1tb3ZlKHMsIHMraiwgaSk7Ci0JaS0tOwotICAgIH0KLSAg
ICBlbHNlIHsKLQltZW1tb3ZlKHMrMSwgcytqLCBpKTsKLSAgICB9Ci0gICAgcmJfc3RyX3NldF9s
ZW4oc3MsIGkpOwogCisgICAgcHRyW2xlbl0gPSAnXDAnOworICAgIHJiX3N0cl9yZXNpemUoc3Ms
IGxlbik7CisKICAgICByZXR1cm4gc3M7CiB9CiAKLXN0YXRpYyB2b2lkCi1pbml0X2JpZzJzdHJf
dGFibGUodm9pZCkKLXsKLSAgICBpbnQgaSwgajsKLSAgICBWQUxVRSB2OwotCi0gICAgZm9yIChp
PTI7IGk8Mzc7IGkrKykgewotICAgICAgIHYgPSByYl9iaWdfcG93KHJiX2ludDJiaWcoaSksIElO
VDJGSVgoS0FSQVRTVUJBX0RJR0lUUykpOwotICAgICAgIGJpZzJzdHJfdGFibGVbaV1bMF0gPSB2
OwotICAgICAgIHJiX2dsb2JhbF92YXJpYWJsZSgmYmlnMnN0cl90YWJsZVtpXVswXSk7Ci0gICAg
ICAgZm9yIChqPTE7IGogPCBNQVhfQklHMlNUUl9UQUJMRV9FTlRSSUVTOyBqKyspIHsKLSAgICAg
ICAgICAgYmlnMnN0cl90YWJsZVtpXVtqXSA9IFFmYWxzZTsKLSAgICAgICB9Ci0gICAgfQotfQot
CiBWQUxVRQogcmJfYmlnMnN0cihWQUxVRSB4LCBpbnQgYmFzZSkKIHsKLSAgICByZXR1cm4gcmJf
YmlnMnN0cjAoeCwgYmFzZSwgUXRydWUpOworICAgIHJldHVybiByYl9iaWcyc3RyMCh4LCBiYXNl
LCAxKTsKIH0KIAogLyoKQEAgLTE3MDcsNyArMTgxNiw3IEBACiAgICAgQkRJR0lUX0RCTCBudW07
CiAKICAgICBpZiAobGVuIDwgNDAwMCAvIEJJVFNQRVJESUcpIHsKLQlyZXR1cm4gcmJfYmlnX211
bDAoeCwgeCk7CisJcmV0dXJuIGJpZ3RydW5jKHJiX2JpZ19tdWwwKHgsIHgpKTsKICAgICB9CiAK
ICAgICBhID0gYmlnbmV3KGxlbiAtIGssIDEpOwpAQCAtMjMxOCw1ICsyNDI3LDUgQEAKICAgICBy
Yl9kZWZpbmVfbWV0aG9kKHJiX2NCaWdudW0sICJhYnMiLCByYl9iaWdfYWJzLCAwKTsKICAgICBy
Yl9kZWZpbmVfbWV0aG9kKHJiX2NCaWdudW0sICJzaXplIiwgcmJfYmlnX3NpemUsIDApOwogCi0g
ICAgaW5pdF9iaWcyc3RyX3RhYmxlKCk7CisgICAgcG93ZXJfY2FjaGVfaW5pdCgpOwogfQo=
------=_Part_129521_1380815.1186420296292--