From: Kenta Murata Date: 2007-08-07T00:50:27+09:00 Subject: [ruby-dev:31352] Re: Bignum#to_s の Karatsuba 基数変換による高速化 ------=_Part_127821_28137269.1186415421044 Content-Type: text/plain; charset=ISO-2022-JP Content-Transfer-Encoding: 7bit Content-Disposition: inline むらたです．こんばんわ． [ruby-dev:31323] で提出したパッチに対して，テーブル周辺の処理を変更した 改良版をこしらえました．一つ目の添付パッチがそれです．この変更で， いくらか高速化できましたので，以下で報告します． 07/08/03 に Kenta Murata さんは書きました: > 07/08/02 に Yusuke ENDOH さんは書きました: > > > どう見ても遠藤さんの実装のほうが平均すると高速であるように見えます． > > > > いえ、平均するとむらたさんの方が早いです。 私の実装が遠藤さんの実装よりも平均して速かった理由が分かりました． 遠藤さんの実装において，big2str_karatsuba() 関数のはじめの方で 基数ベキを生成しているループがあります．その中で，必ず一回だけ， 余分な bigsqr が呼び出されてしまいます (結果は比較で使うだけ)． もう一点．遠藤さんの実装では，変換対象の数値を，2^n で2等分することを 繰り返して処理しています．僕の実装はというと，2等分ではなくて 2^n で divmod した結果の値に応じて基数ベキの大きさを変えているので， 除算の結果が急激に小さな値になった場合に再帰呼び出しの回数が少なくなります． この違いが，平均速度の差に現れているように思えます． 再帰よりもループの方が僅かながら軽いはずですから，従って， to_s される値の内部表現によっては，僕の実装の方が遅くなることがある かもしれません (ないかもしれません)． > > 特に一回目の to_s が著しく遅いので、何か下手をしている気がします。 遠藤さんの実装で初回の to_s が著しく遅い理由は，今のところ発見できていません orz > > 蛇足ですが、むらたさん版だと to_s(2) に失敗することがあるみたいです。 (snip) > これは・・・最初の警告はきっと基数のベキを求めようとしたときに発生して > るものだと思います (そこしかないですし)． その通りでした．基数が小さいと，rb_big_pow でベキを計算できなくなる ことを考えていませんでした．新しいパッチでは，遠藤さんの実装を参考に， 小さなベキから bigsqr を使って計算するようにしたので，この問題は解決しています． > 私が昨日提出したパッチと，[ruby-dev:31323] で私が提出したパッチの > 速度をまだ比較していませんでした．とりあえず，その比較結果を後ほど > 報告したいと思います． で，このメールに添付したパッチと，[ruby-dev:31339] に添付したパッチの 速度を比較した結果を以下に示します．比較用に両方の変更をマージしたパッチを ２つ目のファイルとして添付しました．コンパイルオプションは CFLAGS='-O6 -mtune=pentium4 -march=i686' としています． 次のような簡単なテストで，私の新しい方が平均的に速いことが分かりました． $ ruby -e '100.times { puts "(#{rand(50000)}**#{rand(50000)}).to_s(#{rand(35) + 2})" }' > test_bignum_endoh.rb $ sed -e 's/to_s/to_s2/g' test_bignum_endoh.rb > test_bignum_muraken.rb $ time ./ruby test_bignum_endoh.rb > res.endoh.txt real 11m7.579s user 3m45.882s sys 0m0.036s $ time ./ruby test_bignum_muraken.rb > res.muraken.txt real 10m14.448s user 3m23.973s sys 0m0.028s 今回の改変作業中に，bigdivmod，bigsqr，もしくは rb_big_mul0 のいずれかの バグ(?)を見つけました (まだ直してはいません)． 僕が確認した症状は，bigdivmod の引数 y が正規化されていない場合に， 商 q が不正な値になります．具体例を出すと， x = [3326864467, 3907086170, 971956897, 690519217, 3899134773, 3795824570, 442283194, 1330259551, 2003237075, 185150596, 3356760681, 1324341631, 2994369366, 4193523868, 856144703, 901986172, 819949625, 3949855622, 1036270654, 861377302, 1540531469, 1872568982, 2117697280, 1626080396, 914652449, 2236519255, 1632014126, 2752481805, 1004969631, 2885238682, 746945629, 2700918791, 1532651932, 15071 ] y = [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 ] となっている (y が正規化されていない) ときに商 q が不正な値になります． 剰余 r には影響はありませんでした． 一つ目の添付のパッチを当てたソースでこの症状が出る部分は，1101行目にある bigdivmod(x, b, &q, &r) という呼び出しです．ここで，b が正規化されていない ために症状が発生したわけですが，b は rb_big_pow か bigsqr のどちらかによって 生成されるオブジェクトです．両者のコードを見ると，bigsqr で呼び出している rb_big_mul0 の中で作られる Bignum が bigtrunc もしくは bignorm されずに 戻されているので，これが原因ではないかと思います． もっとも，bigdivmod を非正規化オブジェクトでも正しく動くように修正することでも対応 出来ると思いますが，bigsqr の中で rb_big_mul0 を呼び出しているところに bigtrunc を被せるだけで修正できるので，bigsqr をいじるほうが簡単だと思います （もしくは rb_big_mul0 で z を bigtrunc する）． どちらを行うべきかは Bignum のライブラリとしての仕様の問題だと思うので， 最終的にはまつもとさんの判断にお任せします． -- Kenta Murata OpenPGP FP = FA26 35D7 4F98 3498 0810 E0D5 F213 966F E9EB 0BCC ------=_Part_127821_28137269.1186415421044 Content-Type: application/octet-stream; name=bignum_to_s_karatsuba_20070806.patch Content-Transfer-Encoding: base64 X-Attachment-Id: f_f51539tz Content-Disposition: attachment; filename="bignum_to_s_karatsuba_20070806.patch" SW5kZXg6IGJpZ251bS5jCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIGJpZ251bS5jCSjjg6rjg5Pjgrjjg6fjg7Mg MTI4NTkpCisrKyBiaWdudW0uYwko5L2c5qWt44Kz44OU44O8KQpAQCAtNjM1LDEwMiArNjM1LDMx NSBAQAogfQogCiBjb25zdCBjaGFyIHJ1YnlfZGlnaXRtYXBbXSA9ICIwMTIzNDU2Nzg5YWJjZGVm Z2hpamtsbW5vcHFyc3R1dnd4eXoiOwotVkFMVUUKLXJiX2JpZzJzdHIwKHgsIGJhc2UsIHRyaW0p Ci0gICAgVkFMVUUgeDsKKworc3RhdGljIFZBTFVFIGJpZ3NxcihWQUxVRSB4KTsKK3N0YXRpYyB2 b2lkIGJpZ2Rpdm1vZChWQUxVRSB4LCBWQUxVRSB5LCBWQUxVRSAqZGl2cCwgVkFMVUUgKm1vZHAp OworCisjZGVmaW5lIFBPVzJfUCh4KSAoKCh4KSYoKHgpLTEpKT09MCkKKworc3RhdGljIGlubGlu ZSBpbnQKK29uZXMocmVnaXN0ZXIgdW5zaWduZWQgbG9uZyB4KQoreworI2lmIFNJWkVPRl9VTE9O RyA9PSA4CisjIGRlZmluZSBNQVNLXzU1IDB4NTU1NTU1NTU1NTU1NTU1NVVMCisjIGRlZmluZSBN QVNLXzMzIDB4MzMzMzMzMzMzMzMzMzMzM1VMCisjIGRlZmluZSBNQVNLXzBmIDB4MGYwZjBmMGYw ZjBmMGYwZlVMCisjZWxzZQorIyBkZWZpbmUgTUFTS181NSAweDU1NTU1NTU1VUwKKyMgZGVmaW5l IE1BU0tfMzMgMHgzMzMzMzMzM1VMCisjIGRlZmluZSBNQVNLXzBmIDB4MGYwZjBmMGZVTAorI2Vu ZGlmCisgIHggLT0gKHggPj4gMSkgJiBNQVNLXzU1OworICB4ID0gKCh4ID4+IDIpICYgTUFTS18z MykgKyAoeCAmIE1BU0tfMzMpOworICB4ID0gKCh4ID4+IDQpICsgeCkgJiBNQVNLXzBmOworICB4 ICs9ICh4ID4+IDgpOworICB4ICs9ICh4ID4+IDE2KTsKKyNpZiBTSVpFT0ZfVUxPTkcgPT0gOAor ICB4ICs9ICh4ID4+IDMyKTsKKyNlbmRpZgorICByZXR1cm4gKGludCkoeCAmIDB4N2YpOworI3Vu ZGVmIE1BU0tfMGYKKyN1bmRlZiBNQVNLXzMzCisjdW5kZWYgTUFTS181NQorfQorCitzdGF0aWMg aW5saW5lIHVuc2lnbmVkIGxvbmcKK25leHRfcG93MihyZWdpc3RlciB1bnNpZ25lZCBsb25nIHgp Cit7CisgIHggfD0geCA+PiAxOworICB4IHw9IHggPj4gMjsKKyAgeCB8PSB4ID4+IDQ7CisgIHgg fD0geCA+PiA4OworICB4IHw9IHggPj4gMTY7CisjaWYgU0laRU9GX1VMT05HID09IDgKKyAgeCB8 PSB4ID4+IDMyOworI2VuZGlmCisgIHJldHVybiB4ICsgMTsKK30KKworc3RhdGljIGlubGluZSBp bnQKK2Zsb29yX2xvZzIocmVnaXN0ZXIgdW5zaWduZWQgbG9uZyB4KQoreworICB4IHw9IHggPj4g MTsKKyAgeCB8PSB4ID4+IDI7CisgIHggfD0geCA+PiA0OworICB4IHw9IHggPj4gODsKKyAgeCB8 PSB4ID4+IDE2OworI2lmIFNJWkVPRl9VTE9ORyA9PSA4CisgIHggfD0geCA+PiAzMjsKKyNlbmRp ZgorICByZXR1cm4gKGludClvbmVzKHgpIC0gMTsKK30KKworc3RhdGljIGlubGluZSBpbnQKK2Nl aWxfbG9nMihyZWdpc3RlciB1bnNpZ25lZCBsb25nIHgpCit7CisgIHJldHVybiBmbG9vcl9sb2cy KHgpICsgIVBPVzJfUCh4KTsKK30KKworI2RlZmluZSBMT0cyX0tBUkFUU1VCQV9ESUdJVFMgNwor I2RlZmluZSBLQVJBVFNVQkFfRElHSVRTICgxTDw8TE9HMl9LQVJBVFNVQkFfRElHSVRTKQorI2Rl ZmluZSBNQVhfQklHMlNUUl9UQUJMRV9FTlRSSUVTIDY0CisKK3N0YXRpYyBWQUxVRSBiaWcyc3Ry X3Bvd2VyX2NhY2hlWzM1XVtNQVhfQklHMlNUUl9UQUJMRV9FTlRSSUVTXTsKKworc3RhdGljIHZv aWQKK3Bvd2VyX2NhY2hlX2luaXQodm9pZCkKK3sKKyAgaW50IGksIGo7CisgIGZvciAoaSA9IDA7 IGkgPCAzNTsgKytpKSB7CisgICAgYmlnMnN0cl9wb3dlcl9jYWNoZVtpXVswXSA9CisgICAgICBy Yl9iaWdfcG93KHJiX2ludDJiaWcoaSsyKSwgSU5UMkZJWChLQVJBVFNVQkFfRElHSVRTKSk7Cisg ICAgcmJfZ2xvYmFsX3ZhcmlhYmxlKCZiaWcyc3RyX3Bvd2VyX2NhY2hlW2ldWzBdKTsKKyAgICBm b3IgKGogPSAxOyBqIDwgTUFYX0JJRzJTVFJfVEFCTEVfRU5UUklFUzsgKytqKSB7CisgICAgICBi aWcyc3RyX3Bvd2VyX2NhY2hlW2ldW2pdID0gUW5pbDsKKyAgICB9CisgIH0KK30KKworc3RhdGlj IGlubGluZSBWQUxVRQorcG93ZXJfY2FjaGVfZ2V0X3Bvd2VyMChiYXNlLCBpKQoreworICBpZiAo TklMX1AoYmlnMnN0cl9wb3dlcl9jYWNoZVtiYXNlIC0gMl1baV0pKSB7CisgICAgYmlnMnN0cl9w b3dlcl9jYWNoZVtiYXNlIC0gMl1baV0gPQorICAgICAgYmlnbm9ybShiaWdzcXIocG93ZXJfY2Fj aGVfZ2V0X3Bvd2VyMChiYXNlLCBpIC0gMSkpKTsKKyAgICByYl9nbG9iYWxfdmFyaWFibGUoJmJp ZzJzdHJfcG93ZXJfY2FjaGVbYmFzZSAtIDJdW2ldKTsKKyAgfQorICByZXR1cm4gYmlnMnN0cl9w b3dlcl9jYWNoZVtiYXNlIC0gMl1baV07Cit9CisKK3N0YXRpYyBWQUxVRQorcG93ZXJfY2FjaGVf Z2V0X3Bvd2VyKGJhc2UsIG4xLCBtMSkKICAgICBpbnQgYmFzZTsKLSAgICBpbnQgdHJpbTsKKyAg ICBsb25nIG4xOworICAgIGxvbmcqIG0xOwogewotICAgIHZvbGF0aWxlIFZBTFVFIHQ7Ci0gICAg QkRJR0lUICpkczsKLSAgICBsb25nIGksIGosIGhiYXNlOwotICAgIFZBTFVFIHNzOwotICAgIGNo YXIgKnM7CisgIGxvbmcgaSwgaiwgbTsKKyAgVkFMVUUgdDsKIAorICBpZiAobjEgPD0gS0FSQVRT VUJBX0RJR0lUUykKKyAgICByYl9idWcoIm4xID4gS0FSQVRTVUJBX0RJR0lUUyIpOworCisgIG0g PSBjZWlsX2xvZzIobjEpOworICBpZiAobTEpICptMSA9IDEgPDwgbTsKKyAgaSA9IG0gLSBMT0cy X0tBUkFUU1VCQV9ESUdJVFM7CisgIGlmIChpID49IE1BWF9CSUcyU1RSX1RBQkxFX0VOVFJJRVMp CisgICAgaSA9IE1BWF9CSUcyU1RSX1RBQkxFX0VOVFJJRVMgLSAxOworICB0ID0gcG93ZXJfY2Fj aGVfZ2V0X3Bvd2VyMChiYXNlLCBpKTsKKworICBqID0gS0FSQVRTVUJBX0RJR0lUUyooMSA8PCBp KTsKKyAgd2hpbGUgKG4xID4gaikgeworICAgIHQgPSBiaWdzcXIodCk7CisgICAgaiAqPSAyOwor ICB9CisgIHJldHVybiBiaWdub3JtKHQpOworfQorCisvKiBiaWcyc3RyX211cmFrZW5fZmluZF9u MQorICoKKyAqIExldCBhIG5hdHVyYWwgbnVtYmVyIHggaXMgZ2l2ZW4gYnk6CisgKiB4ID0gMl4w ICogeF8wICsgMl4xICogeF8xICsgLi4uICsgMl4oQipuXzAgLSAxKSAqIHhfe0Iqbl8wIC0gMX0s CisgKiB3aGVyZSBCIGlzIEJJVFNQRVJESUcgKGkuZS4gQkRJR0lUUypDSEFSX0JJVCkgYW5kIG5f MCBpcworICogUkJJR05VTSh4KS0+bGVuLgorICoKKyAqIE5vdywgd2UgYXNzdW1lIG5fMSA9IG1p bl9uIFx7IG4gfCAyXihCKm5fMC8yKSA8PSBiXzFeKG5fMSkgXH0sIHNvCisgKiBpdCBpcyByZWFs aXplZCB0aGF0IDJeKEIqbl8wKSA8PSB7Yl8xfV57MipuXzF9LCB3aGVyZSBiXzEgaXMgYQorICog Z2l2ZW4gcmFkaXggbnVtYmVyLiBBbmQgdGhlbiwgd2UgaGF2ZSBuXzEgPD0gKEIqbl8wKSAvCisg KiAoMipsb2dfMihiXzEpKSwgdGhlcmVmb3JlIG5fMSBpcyBnaXZlbiBieSBjZWlsKChCKm5fMCkg LworICogKDIqbG9nXzIoYl8xKSkpLgorICovCitzdGF0aWMgbG9uZworYmlnMnN0cl9maW5kX24x KFZBTFVFIHgsIGludCBiYXNlKQoreworICAgIHN0YXRpYyBjb25zdCBkb3VibGUgbG9nXzJbXSA9 IHsKKyAgICAgICAgMS4wLCAgICAgICAgICAgICAgMS41ODQ5NjI1MDA3MjExNiwgMi4wLAorICAg ICAgICAyLjMyMTkyODA5NDg4NzM2LCAyLjU4NDk2MjUwMDcyMSwgICAyLjU4NDk2MjUwMDcyMTE2 LAorICAgICAgICAyLjgwNzM1NDkyMjA1NzYsICAzLjAsICAgICAgICAgICAgICAzLjE2OTkyNTAw MTQ0MjMxLAorICAgICAgICAzLjMyMTkyODA5NDg4NzM2LCAzLjQ1OTQzMTYxODYzNzMsICAzLjU4 NDk2MjUwMDcyMTE2LAorICAgICAgICAzLjcwMDQzOTcxODE0MTA5LCAzLjgwNzM1NDkyMjA1NzYs ICAzLjkwNjg5MDU5NTYwODUyLAorICAgICAgICA0LjAsICAgICAgICAgICAgICA0LjA4NzQ2Mjg0 MTI1MDM0LCA0LjE2OTkyNTAwMTQ0MjMxLAorICAgICAgICA0LjI0NzkyNzUxMzQ0MzU5LCA0LjMy MTkyODA5NDg4NzM2LCA0LjM5MjMxNzQyMjc3ODc2LAorICAgICAgICA0LjQ1OTQzMTYxODYzNzMs ICA0LjUyMzU2MTk1NjA1NzAxLCA0LjU4NDk2MjUwMDcyMTE2LAorICAgICAgICA0LjY0Mzg1NjE4 OTc3NDcyLCA0LjcwMDQzOTcxODE0MTA5LCA0Ljc1NDg4NzUwMjE2MzQ3LAorICAgICAgICA0Ljgw NzM1NDkyMjA1NzYsICA0Ljg1Nzk4MDk5NTEyNzU3LCA0LjkwNjg5MDU5NTYwODUyLAorICAgICAg ICA0Ljk1NDE5NjMxMDM4Njg4LCA1LjAsICAgICAgICAgICAgICA1LjA0NDM5NDExOTM1ODQ1LAor ICAgICAgICA1LjA4NzQ2Mjg0MTI1MDM0LCA1LjEyOTI4MzAxNjk0NDk3LCA1LjE2OTkyNTAwMTQ0 MjMxCisgICAgfTsKKyAgICBsb25nIGJpdHMsIG4sIGk7CisKKyAgICBpZiAoYmFzZSA8IDIgJiYg MzYgPCBiYXNlKQorICAgICAgcmJfYnVnKCJpbGxlZ2FsIHJhZGl4ICVkIiwgYmFzZSk7CisKICAg ICBpZiAoRklYTlVNX1AoeCkpIHsKLQlyZXR1cm4gcmJfZml4MnN0cih4LCBiYXNlKTsKKyAgICAg ICAgYml0cyA9IChTSVpFT0ZfTE9ORypDSEFSX0JJVCAtIDEpLzIgKyAxOwogICAgIH0KLSAgICBp ID0gUkJJR05VTSh4KS0+bGVuOwotICAgIGlmIChCSUdaRVJPUCh4KSkgewotCXJldHVybiByYl9z dHJfbmV3MigiMCIpOworICAgIGVsc2UgaWYgKEJJR1pFUk9QKHgpKSB7CisgICAgICAgIHJldHVy biAwOwogICAgIH0KLSAgICBqID0gU0laRU9GX0JESUdJVFMqQ0hBUl9CSVQqaTsKLSAgICBzd2l0 Y2ggKGJhc2UpIHsKLSAgICAgIGNhc2UgMjogYnJlYWs7Ci0gICAgICBjYXNlIDM6Ci0JaiA9IGog KiA1M0wgLyA4NCArIDE7Ci0JYnJlYWs7Ci0gICAgICBjYXNlIDQ6IGNhc2UgNTogY2FzZSA2OiBj YXNlIDc6Ci0JaiA9IChqICsgMSkgLyAyOwotCWJyZWFrOwotICAgICAgY2FzZSA4OiBjYXNlIDk6 Ci0JaiA9IChqICsgMikgLyAzOwotCWJyZWFrOwotICAgICAgY2FzZSAxMDogY2FzZSAxMTogY2Fz ZSAxMjogY2FzZSAxMzogY2FzZSAxNDogY2FzZSAxNToKLQlqID0gaiAqIDI4TCAvIDkzICsgMTsK LQlicmVhazsKLSAgICAgIGNhc2UgMTY6IGNhc2UgMTc6IGNhc2UgMTg6IGNhc2UgMTk6IGNhc2Ug MjA6IGNhc2UgMjE6Ci0gICAgICBjYXNlIDIyOiBjYXNlIDIzOiBjYXNlIDI0OiBjYXNlIDI1OiBj YXNlIDI2OiBjYXNlIDI3OgotICAgICAgY2FzZSAyODogY2FzZSAyOTogY2FzZSAzMDogY2FzZSAz MToKLQlqID0gKGogKyAzKSAvIDQ7Ci0JYnJlYWs7Ci0gICAgICBjYXNlIDMyOiBjYXNlIDMzOiBj YXNlIDM0OiBjYXNlIDM1OiBjYXNlIDM2OgotCWogPSAoaiArIDQpIC8gNTsKLQlicmVhazsKLSAg ICAgIGRlZmF1bHQ6Ci0JcmJfcmFpc2UocmJfZUFyZ0Vycm9yLCAiaWxsZWdhbCByYWRpeCAlZCIs IGJhc2UpOwotCWJyZWFrOworICAgIGVsc2UgeworICAgICAgICBiaXRzID0gQklUU1BFUkRJRypS QklHTlVNKHgpLT5sZW47CiAgICAgfQotICAgIGorKzsJCQkvKiBzcGFjZSBmb3Igc2lnbiAqLwog Ci0gICAgaGJhc2UgPSBiYXNlICogYmFzZTsKLSNpZiBTSVpFT0ZfQkRJR0lUUyA+IDIKLSAgICBo YmFzZSAqPSBoYmFzZTsKLSNlbmRpZgorICAgIHJldHVybiAobG9uZyljZWlsKGJpdHMvKDIqbG9n XzJbYmFzZSAtIDJdKSk7Cit9CiAKLSAgICB0ID0gcmJfYmlnX2Nsb25lKHgpOwotICAgIGRzID0g QkRJR0lUUyh0KTsKLSAgICBzcyA9IHJiX3N0cl9uZXcoMCwgaisxKTsKLSAgICBzID0gUlNUUklO RyhzcyktPnB0cjsKK3N0YXRpYyBsb25nCitiaWcyc3RyX29yaWcoeCwgYmFzZSwgcHRyLCBsZW4s IGhiYXNlLCB0cmltKQorICBWQUxVRSB4OworICBpbnQgYmFzZTsKKyAgY2hhciogcHRyOworICBs b25nIGxlbjsKKyAgbG9uZyBoYmFzZTsKKyAgaW50IHRyaW07Cit7CisgIGxvbmcgaSA9IFJCSUdO VU0oeCktPmxlbiwgaiA9IGxlbjsKKyAgQkRJR0lUKiBkcyA9IEJESUdJVFMoeCk7CiAKLSAgICBz WzBdID0gUkJJR05VTSh4KS0+c2lnbiA/ICcrJyA6ICctJzsKLSAgICB3aGlsZSAoaSAmJiBqID4g MSkgewotCWxvbmcgayA9IGk7Ci0JQkRJR0lUX0RCTCBudW0gPSAwOworICB3aGlsZSAoaSAmJiBq ID4gMCkgeworICAgIGxvbmcgayA9IGk7CisgICAgQkRJR0lUX0RCTCBudW0gPSAwOwogCi0Jd2hp bGUgKGstLSkgewotCSAgICBudW0gPSBCSUdVUChudW0pICsgZHNba107Ci0JICAgIGRzW2tdID0g KEJESUdJVCkobnVtIC8gaGJhc2UpOwotCSAgICBudW0gJT0gaGJhc2U7Ci0JfQotCWlmICh0cmlt ICYmIGRzW2ktMV0gPT0gMCkgaS0tOwotCWsgPSBTSVpFT0ZfQkRJR0lUUzsKLQl3aGlsZSAoay0t KSB7Ci0JICAgIHNbLS1qXSA9IHJ1YnlfZGlnaXRtYXBbbnVtICUgYmFzZV07Ci0JICAgIG51bSAv PSBiYXNlOwotCSAgICBpZiAoIXRyaW0gJiYgaiA8IDEpIGJyZWFrOwotCSAgICBpZiAodHJpbSAm JiBpID09IDAgJiYgbnVtID09IDApIGJyZWFrOwotCX0KKyAgICB3aGlsZSAoay0tKSB7ICAgICAg ICAgICAgICAgLyogeCAvIGhiYXNlICovCisgICAgICBudW0gPSBCSUdVUChudW0pICsgZHNba107 CisgICAgICBkc1trXSA9IChCRElHSVQpKG51bSAvIGhiYXNlKTsKKyAgICAgIG51bSAlPSBoYmFz ZTsKICAgICB9Ci0gICAgaWYgKHRyaW0pIHt3aGlsZSAoc1tqXSA9PSAnMCcpIGorKzt9Ci0gICAg aSA9IFJTVFJJTkcoc3MpLT5sZW4gLSBqOwotICAgIGlmIChSQklHTlVNKHgpLT5zaWduKSB7Ci0J bWVtbW92ZShzLCBzK2osIGkpOwotCVJTVFJJTkcoc3MpLT5sZW4gPSBpLTE7CisgICAgaWYgKHRy aW0gJiYgZHNbaS0xXSA9PSAwKSBpLS07CisgICAgayA9IFNJWkVPRl9CRElHSVRTOworICAgIHdo aWxlIChrLS0pIHsKKyAgICAgIHB0clstLWpdID0gcnVieV9kaWdpdG1hcFtudW0gJSBiYXNlXTsK KyAgICAgIG51bSAvPSBiYXNlOworICAgICAgaWYgKCF0cmltICYmIGogPD0gMCkgYnJlYWs7Cisg ICAgICBpZiAodHJpbSAmJiBpID09IDAgJiYgbnVtID09IDApIGJyZWFrOwogICAgIH0KKyAgfQor ICBpZiAodHJpbSkgeworICAgIHdoaWxlIChwdHJbal0gPT0gJzAnKSBqKys7CisgICAgTUVNTU9W RShwdHIsIHB0ciArIGosIGNoYXIsIGxlbiAtIGopOworICAgIGxlbiAtPSBqOworICB9CisgIHJl dHVybiBsZW47Cit9CisKK3N0YXRpYyBsb25nCitiaWcyc3RyX2thcmF0c3ViYSh4LCBiYXNlLCBw dHIsIG4xLCBsZW4sIGhiYXNlLCB0cmltKQorICAgIFZBTFVFIHg7CisgICAgaW50IGJhc2U7Cisg ICAgY2hhciogcHRyOworICAgIGxvbmcgbjE7CisgICAgbG9uZyBsZW47CisgICAgbG9uZyBoYmFz ZTsKKyAgICBpbnQgdHJpbTsKK3sKKyAgbG9uZyBsaCwgbGwsIG0xOworICBWQUxVRSBiLCBxLCBy OworCisgIGlmIChGSVhOVU1fUCh4KSkgeworICAgIFZBTFVFIHN0ciA9IHJiX2ZpeDJzdHIoeCwg YmFzZSk7CisgICAgaWYgKHRyaW0pIHsKKyAgICAgIGlmIChGSVgySU5UKHgpID09IDApIHJldHVy biAwOworICAgICAgTUVNQ1BZKHB0ciwgUlNUUklORyhzdHIpLT5wdHIsIGNoYXIsIFJTVFJJTkco c3RyKS0+bGVuKTsKKyAgICAgIHJldHVybiBSU1RSSU5HKHN0ciktPmxlbjsKKyAgICB9CiAgICAg ZWxzZSB7Ci0JbWVtbW92ZShzKzEsIHMraiwgaSk7Ci0JUlNUUklORyhzcyktPmxlbiA9IGk7Cisg ICAgICBtZW1zZXQocHRyLCAnMCcsIGxlbiAtIFJTVFJJTkcoc3RyKS0+bGVuKTsKKyAgICAgIE1F TUNQWShwdHIgKyBsZW4gLSBSU1RSSU5HKHN0ciktPmxlbiwgUlNUUklORyhzdHIpLT5wdHIsCisg ICAgICAgICAgICAgY2hhciwgUlNUUklORyhzdHIpLT5sZW4pOworICAgICAgcmV0dXJuIGxlbjsK ICAgICB9Ci0gICAgc1tSU1RSSU5HKHNzKS0+bGVuXSA9ICdcMCc7CisgIH0KKyAgaWYgKEJJR1pF Uk9QKHgpKSB7CisgICAgaWYgKHRyaW0pIHJldHVybiAwOworICAgIGVsc2UgeworICAgICAgbWVt c2V0KHB0ciwgJzAnLCBsZW4pOworICAgICAgcmV0dXJuIGxlbjsKKyAgICB9CisgIH0KIAotICAg IHJldHVybiBzczsKKyAgaWYgKG4xIDw9IEtBUkFUU1VCQV9ESUdJVFMpIHsKKyAgICByZXR1cm4g YmlnMnN0cl9vcmlnKHgsIGJhc2UsIHB0ciwgbGVuLCBoYmFzZSwgdHJpbSk7CisgIH0KKworICBi ID0gcG93ZXJfY2FjaGVfZ2V0X3Bvd2VyKGJhc2UsIG4xLCAmbTEpOworICBiaWdkaXZtb2QoeCwg YiwgJnEsICZyKTsKKyAgbGggPSBiaWcyc3RyX2thcmF0c3ViYShxLCBiYXNlLCBwdHIsICAgICAg KGxlbiAtIG0xKS8yLAorICAgICAgICAgICAgICAgICAgICAgICAgIGxlbiAtIG0xLCBoYmFzZSwg dHJpbSk7CisgIGxsID0gYmlnMnN0cl9rYXJhdHN1YmEociwgYmFzZSwgcHRyICsgbGgsIG0xLzIs CisgICAgICAgICAgICAgICAgICAgICAgICAgbTEsICAgICAgIGhiYXNlLCAhbGggJiYgdHJpbSk7 CisKKyAgcmV0dXJuIGxoICsgbGw7CiB9CiAKIFZBTFVFCityYl9iaWcyc3RyMCh4LCBiYXNlLCB0 cmltKQorICBWQUxVRSB4OworICBpbnQgYmFzZTsKKyAgaW50IHRyaW07Cit7CisgIGludCBvZmY7 CisgIFZBTFVFIHNzLCB4eDsKKyAgbG9uZyBuMSwgbGVuLCBoYmFzZTsKKworICBpZiAoRklYTlVN X1AoeCkpIHsKKyAgICByZXR1cm4gcmJfZml4MnN0cih4LCBiYXNlKTsKKyAgfQorICBpZiAoQklH WkVST1AoeCkpIHsKKyAgICByZXR1cm4gcmJfc3RyX25ldzIoIjAiKTsKKyAgfQorCisgIGlmIChi YXNlIDwgMiAmJiAzNiA8IGJhc2UpCisgICAgcmJfcmFpc2UocmJfZUFyZ0Vycm9yLCAiaWxsZWdh bCByYWRpeCAlZCIsIGJhc2UpOworCisgIG4xID0gYmlnMnN0cl9maW5kX24xKHgsIGJhc2UpOwor ICBzcyA9IHJiX3N0cl9uZXcoMCwgMipuMSArIDEpOyAvKiBwbHVzIG9uZSBmb3Igc2lnbiAqLwor ICBSU1RSSU5HKHNzKS0+cHRyWzBdID0gUkJJR05VTSh4KS0+c2lnbiA/ICcrJyA6ICctJzsKKwor ICBoYmFzZSA9IGJhc2UqYmFzZTsKKyNpZiBTSVpFT0ZfQkRJR0lUUyA+IDIKKyAgaGJhc2UgKj0g aGJhc2U7CisjZW5kaWYKKyAgb2ZmID0gIVJURVNUKHRyaW0pICYmICFSQklHTlVNKHgpLT5zaWdu OworICB4eCA9IHJiX2JpZ19jbG9uZSh4KTsKKyAgUkJJR05VTSh4eCktPnNpZ24gPSAxOworICBp ZiAobjEgPD0gS0FSQVRTVUJBX0RJR0lUUykgeworICAgIGxlbiA9IGJpZzJzdHJfb3JpZyh4eCwg YmFzZSwgUlNUUklORyhzcyktPnB0ciArIG9mZiwKKyAgICAgICAgICAgICAgICAgICAgICAgMipu MSwgaGJhc2UsIFJURVNUKHRyaW0pKTsKKyAgfQorICBlbHNlIHsKKyAgICBsZW4gPSBiaWcyc3Ry X2thcmF0c3ViYSh4eCwgYmFzZSwgUlNUUklORyhzcyktPnB0ciArIG9mZiwKKyAgICAgICAgICAg ICAgICAgICAgICAgICAgICBuMSwgMipuMSwgaGJhc2UsIFJURVNUKHRyaW0pKTsKKyAgfQorCisg IFJTVFJJTkcoc3MpLT5wdHJbbGVuXSA9ICdcMCc7CisgIHJiX3N0cl9yZXNpemUoc3MsIGxlbik7 CisKKyAgcmV0dXJuIHNzOworfQorCitWQUxVRQogcmJfYmlnMnN0cihWQUxVRSB4LCBpbnQgYmFz ZSkKIHsKLSAgICByZXR1cm4gcmJfYmlnMnN0cjAoeCwgYmFzZSwgUXRydWUpOworICByZXR1cm4g cmJfYmlnMnN0cjAoeCwgYmFzZSwgMSk7CiB9CiAKIC8qCkBAIC0yMzQ0LDQgKzI1NTcsNiBAQAog ICAgIHJiX2RlZmluZV9tZXRob2QocmJfY0JpZ251bSwgInRvX2YiLCByYl9iaWdfdG9fZiwgMCk7 CiAgICAgcmJfZGVmaW5lX21ldGhvZChyYl9jQmlnbnVtLCAiYWJzIiwgcmJfYmlnX2FicywgMCk7 CiAgICAgcmJfZGVmaW5lX21ldGhvZChyYl9jQmlnbnVtLCAic2l6ZSIsIHJiX2JpZ19zaXplLCAw KTsKKworICAgIHBvd2VyX2NhY2hlX2luaXQoKTsKIH0K ------=_Part_127821_28137269.1186415421044 Content-Type: application/octet-stream; name=bignum_to_s_karatsuba_20070806_with_31339.patch Content-Transfer-Encoding: base64 X-Attachment-Id: f_f5153hfp Content-Disposition: attachment; filename="bignum_to_s_karatsuba_20070806_with_31339.patch" SW5kZXg6IGJpZ251bS5jCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIGJpZ251bS5jCSjjg6rjg5Pjgrjjg6fjg7Mg MTI4NTkpCisrKyBiaWdudW0uYwko5L2c5qWt44Kz44OU44O8KQpAQCAtNjM1LDYgKzYzNSw5NSBA QAogfQogCiBjb25zdCBjaGFyIHJ1YnlfZGlnaXRtYXBbXSA9ICIwMTIzNDU2Nzg5YWJjZGVmZ2hp amtsbW5vcHFyc3R1dnd4eXoiOworc3RhdGljIGlubGluZSBpbnQKK2JpZzJzdHJfbm9ybWFsKFZB TFVFIHgsIGxvbmcgaiwgaW50IGJhc2UsIGludCBoYmFzZSwgY2hhciAqcywgaW50IHRyaW0pCit7 CisgICAgbG9uZyBpID0gUkJJR05VTSh4KS0+bGVuOworICAgIEJESUdJVCAqZHMgPSBCRElHSVRT KHgpOworCisgICAgd2hpbGUgKGkgJiYgaiA+IDEpIHsKKyAgICAgICBsb25nIGsgPSBpOworICAg ICAgIEJESUdJVF9EQkwgbnVtID0gMDsKKworICAgICAgIHdoaWxlIChrLS0pIHsKKyAgICAgICAg ICAgbnVtID0gQklHVVAobnVtKSArIGRzW2tdOworICAgICAgICAgICBkc1trXSA9IChCRElHSVQp KG51bSAvIGhiYXNlKTsKKyAgICAgICAgICAgbnVtICU9IGhiYXNlOworICAgICAgIH0KKyAgICAg ICBpZiAodHJpbSAmJiBkc1tpLTFdID09IDApIGktLTsKKyAgICAgICBrID0gU0laRU9GX0JESUdJ VFM7CisgICAgICAgd2hpbGUgKGstLSkgeworICAgICAgICAgICBzWy0tal0gPSBydWJ5X2RpZ2l0 bWFwW251bSAlIGJhc2VdOworICAgICAgICAgICBudW0gLz0gYmFzZTsKKyAgICAgICAgICAgaWYg KCF0cmltICYmIGogPCAxKSBicmVhazsKKyAgICAgICAgICAgaWYgKHRyaW0gJiYgaSA9PSAwICYm IG51bSA9PSAwKSBicmVhazsKKyAgICAgICB9CisgICAgfQorICAgIHJldHVybiBqOworfQorCisj ZGVmaW5lIExPRzJfS0FSQVRTVUJBX0RJR0lUUyA4CisjZGVmaW5lIEtBUkFUU1VCQV9ESUdJVFMg KDFMPDxMT0cyX0tBUkFUU1VCQV9ESUdJVFMpCisjZGVmaW5lIE1BWF9CSUcyU1RSX1RBQkxFX0VO VFJJRVMgNjQKK3N0YXRpYyBWQUxVRSBiaWcyc3RyX3RhYmxlWzM3XVtNQVhfQklHMlNUUl9UQUJM RV9FTlRSSUVTXTsKKworc3RhdGljIFZBTFVFIGJpZ3NxcihWQUxVRSB4KTsKK3N0YXRpYyB2b2lk IGJpZ2Rpdm1vZChWQUxVRSB4LCBWQUxVRSB5LCBWQUxVRSAqZGl2cCwgVkFMVUUgKm1vZHApOwor CitzdGF0aWMgaW5saW5lIGludAorYmlnMnN0cl9rYXJhdHN1YmEoVkFMVUUgeCwgaW50IG4sIGlu dCBiYXNlLCBpbnQgaGJhc2UsIGNoYXIgKnMsIGludCB0cmltKQoreworICAgIGxvbmcgaSwgaiwg aywgYnNfbGVuLCBzaWduID0gUkJJR05VTSh4KS0+c2lnbjsKKyAgICB2b2xhdGlsZSBWQUxVRSB0 ID0gYmlnMnN0cl90YWJsZVtiYXNlXVswXSwgdDI7CisgICAgVkFMVUUgKmFzLCAqYnMsIHEsIHI7 CisKKyAgICBqID0gUkJJR05VTSh0KS0+bGVuOworICAgIGZvciAoaT0wOyBqIDw9IFJCSUdOVU0o eCktPmxlbjsgaSsrKSBqICo9IDI7CisKKyAgICBhcyA9IEFMTE9DQV9OKFZBTFVFLCBpKTsKKwor ICAgIGZvciAoaT0wLGo9MTsgOyBpKyssaio9MikgeworICAgICAgIGFzW2ldID0gdDsKKyAgICAg ICBpZihiaWcyc3RyX3RhYmxlW2Jhc2VdW2kgKyAxXSkgeworICAgICAgICAgICB0MiA9IGJpZzJz dHJfdGFibGVbYmFzZV1baSArIDFdOworICAgICAgIH0KKyAgICAgICBlbHNlIHsKKyAgICAgICAg ICAgdDIgPSBiaWdzcXIodCk7CisgICAgICAgICAgIGlmKGkgKyAxIDwgTUFYX0JJRzJTVFJfVEFC TEVfRU5UUklFUykgeworICAgICAgICAgICAgICAgYmlnMnN0cl90YWJsZVtiYXNlXVtpICsgMV0g PSB0MjsKKyAgICAgICAgICAgICAgIHJiX2dsb2JhbF92YXJpYWJsZSgmYmlnMnN0cl90YWJsZVti YXNlXVtpICsgMV0pOworICAgICAgICAgICB9CisgICAgICAgfQorICAgICAgIGlmKFJCSUdOVU0o eCktPmxlbiA8IFJCSUdOVU0odDIpLT5sZW4pIGJyZWFrOworICAgICAgIHQgPSB0MjsKKyAgICB9 CisKKyAgICBic19sZW4gPSBqICogMjsKKyAgICBicyA9IEFMTE9DQV9OKFZBTFVFLCBic19sZW4p OworICAgIGJzWzBdID0geDsKKyAgICBSQklHTlVNKHgpLT5zaWduID0gMTsKKyAgICBmb3IgKDsg aj4wOyBpLS0sIGovPTIpIHsKKyAgICAgICBmb3IgKGs9MDsgazxic19sZW47IGsrPWoqMikgewor ICAgICAgICAgICBiaWdkaXZtb2QoYnNba10sIGFzW2ldLCAmcSwgJnIpOworICAgICAgICAgICBi c1trXSA9IHE7CisgICAgICAgICAgIGJzW2sgKyBqXSA9IHI7CisgICAgICAgfQorICAgIH0KKyAg ICBSQklHTlVNKHgpLT5zaWduID0gc2lnbjsKKworICAgIGogPSAwOworICAgIHdoaWxlKFJCSUdO VU0oYnNbal0pLT5sZW4gPT0gMSAmJiBCRElHSVRTKGJzW2pdKVswXSA9PSAwKSBqKys7CisgICAg Zm9yIChpPWJzX2xlbi0xOyBpPmo7IGktLSkgeworICAgICAgIGsgPSBiaWcyc3RyX25vcm1hbCgK KyAgICAgICAgICAgYnNbaV0sIEtBUkFUU1VCQV9ESUdJVFMsIGJhc2UsIGhiYXNlLAorICAgICAg ICAgICBzICsgbiAtIEtBUkFUU1VCQV9ESUdJVFMsIFFmYWxzZSk7CisgICAgICAgbiAtPSBLQVJB VFNVQkFfRElHSVRTIC0gazsKKyAgICB9CisgICAgbiA9IGJpZzJzdHJfbm9ybWFsKGJzW2pdLCBu LCBiYXNlLCBoYmFzZSwgcywgdHJpbSk7CisKKyAgICByZXR1cm4gbjsKK30KKwogVkFMVUUKIHJi X2JpZzJzdHIwKHgsIGJhc2UsIHRyaW0pCiAgICAgVkFMVUUgeDsKQEAgLTY0Miw3ICs3MzEsNiBA QAogICAgIGludCB0cmltOwogewogICAgIHZvbGF0aWxlIFZBTFVFIHQ7Ci0gICAgQkRJR0lUICpk czsKICAgICBsb25nIGksIGosIGhiYXNlOwogICAgIFZBTFVFIHNzOwogICAgIGNoYXIgKnM7CkBA IC02ODksMjkgKzc3NywxNiBAQAogI2VuZGlmCiAKICAgICB0ID0gcmJfYmlnX2Nsb25lKHgpOwot ICAgIGRzID0gQkRJR0lUUyh0KTsKICAgICBzcyA9IHJiX3N0cl9uZXcoMCwgaisxKTsKICAgICBz ID0gUlNUUklORyhzcyktPnB0cjsKIAogICAgIHNbMF0gPSBSQklHTlVNKHgpLT5zaWduID8gJysn IDogJy0nOwotICAgIHdoaWxlIChpICYmIGogPiAxKSB7Ci0JbG9uZyBrID0gaTsKLQlCRElHSVRf REJMIG51bSA9IDA7Ci0KLQl3aGlsZSAoay0tKSB7Ci0JICAgIG51bSA9IEJJR1VQKG51bSkgKyBk c1trXTsKLQkgICAgZHNba10gPSAoQkRJR0lUKShudW0gLyBoYmFzZSk7Ci0JICAgIG51bSAlPSBo YmFzZTsKLQl9Ci0JaWYgKHRyaW0gJiYgZHNbaS0xXSA9PSAwKSBpLS07Ci0JayA9IFNJWkVPRl9C RElHSVRTOwotCXdoaWxlIChrLS0pIHsKLQkgICAgc1stLWpdID0gcnVieV9kaWdpdG1hcFtudW0g JSBiYXNlXTsKLQkgICAgbnVtIC89IGJhc2U7Ci0JICAgIGlmICghdHJpbSAmJiBqIDwgMSkgYnJl YWs7Ci0JICAgIGlmICh0cmltICYmIGkgPT0gMCAmJiBudW0gPT0gMCkgYnJlYWs7Ci0JfQorICAg IGlmIChSQklHTlVNKHgpLT5sZW4gPiBSQklHTlVNKGJpZzJzdHJfdGFibGVbYmFzZV1bMF0pLT5s ZW4gKiA0KSB7CisgICAgICAgaiA9IGJpZzJzdHJfa2FyYXRzdWJhKHQsIGosIGJhc2UsIGhiYXNl LCBzLCB0cmltKTsKICAgICB9CisgICAgZWxzZSB7CisgICAgICAgaiA9IGJpZzJzdHJfbm9ybWFs KHQsIGosIGJhc2UsIGhiYXNlLCBzLCB0cmltKTsKKyAgICB9CiAgICAgaWYgKHRyaW0pIHt3aGls ZSAoc1tqXSA9PSAnMCcpIGorKzt9CiAgICAgaSA9IFJTVFJJTkcoc3MpLT5sZW4gLSBqOwogICAg IGlmIChSQklHTlVNKHgpLT5zaWduKSB7CkBAIC03MjcsNiArODAyLDIyIEBACiAgICAgcmV0dXJu IHNzOwogfQogCitzdGF0aWMgdm9pZAoraW5pdF9iaWcyc3RyX3RhYmxlKHZvaWQpCit7CisgICAg aW50IGksIGo7CisgICAgVkFMVUUgdjsKKworICAgIGZvciAoaT0wOyBpPDM3OyBpKyspIHsKKyAg ICAgICB2ID0gcmJfYmlnX3BvdyhyYl9pbnQyYmlnKGkpLCBJTlQyRklYKEtBUkFUU1VCQV9ESUdJ VFMpKTsKKyAgICAgICBiaWcyc3RyX3RhYmxlW2ldWzBdID0gdjsKKyAgICAgICByYl9nbG9iYWxf dmFyaWFibGUoJmJpZzJzdHJfdGFibGVbaV1bMF0pOworICAgICAgIGZvciAoaj0xOyBqIDwgTUFY X0JJRzJTVFJfVEFCTEVfRU5UUklFUzsgaisrKSB7CisgICAgICAgICAgIGJpZzJzdHJfdGFibGVb aV1bal0gPSBRZmFsc2U7CisgICAgICAgfQorICAgIH0KK30KKwogVkFMVUUKIHJiX2JpZzJzdHIo VkFMVUUgeCwgaW50IGJhc2UpCiB7CkBAIC03NjIsNiArODUzLDMyNyBAQAogICAgIHJldHVybiBy Yl9iaWcyc3RyKHgsIGJhc2UpOwogfQogCisjZGVmaW5lIFBPVzJfUCh4KSAoKCh4KSYoKHgpLTEp KT09MCkKKworc3RhdGljIGlubGluZSBpbnQKK29uZXMocmVnaXN0ZXIgdW5zaWduZWQgbG9uZyB4 KQoreworI2lmIFNJWkVPRl9VTE9ORyA9PSA4CisjIGRlZmluZSBNQVNLXzU1IDB4NTU1NTU1NTU1 NTU1NTU1NVVMCisjIGRlZmluZSBNQVNLXzMzIDB4MzMzMzMzMzMzMzMzMzMzM1VMCisjIGRlZmlu ZSBNQVNLXzBmIDB4MGYwZjBmMGYwZjBmMGYwZlVMCisjZWxzZQorIyBkZWZpbmUgTUFTS181NSAw eDU1NTU1NTU1VUwKKyMgZGVmaW5lIE1BU0tfMzMgMHgzMzMzMzMzM1VMCisjIGRlZmluZSBNQVNL XzBmIDB4MGYwZjBmMGZVTAorI2VuZGlmCisgIHggLT0gKHggPj4gMSkgJiBNQVNLXzU1OworICB4 ID0gKCh4ID4+IDIpICYgTUFTS18zMykgKyAoeCAmIE1BU0tfMzMpOworICB4ID0gKCh4ID4+IDQp ICsgeCkgJiBNQVNLXzBmOworICB4ICs9ICh4ID4+IDgpOworICB4ICs9ICh4ID4+IDE2KTsKKyNp ZiBTSVpFT0ZfVUxPTkcgPT0gOAorICB4ICs9ICh4ID4+IDMyKTsKKyNlbmRpZgorICByZXR1cm4g KGludCkoeCAmIDB4N2YpOworI3VuZGVmIE1BU0tfMGYKKyN1bmRlZiBNQVNLXzMzCisjdW5kZWYg TUFTS181NQorfQorCitzdGF0aWMgaW5saW5lIHVuc2lnbmVkIGxvbmcKK25leHRfcG93MihyZWdp c3RlciB1bnNpZ25lZCBsb25nIHgpCit7CisgIHggfD0geCA+PiAxOworICB4IHw9IHggPj4gMjsK KyAgeCB8PSB4ID4+IDQ7CisgIHggfD0geCA+PiA4OworICB4IHw9IHggPj4gMTY7CisjaWYgU0la RU9GX1VMT05HID09IDgKKyAgeCB8PSB4ID4+IDMyOworI2VuZGlmCisgIHJldHVybiB4ICsgMTsK K30KKworc3RhdGljIGlubGluZSBpbnQKK2Zsb29yX2xvZzIocmVnaXN0ZXIgdW5zaWduZWQgbG9u ZyB4KQoreworICB4IHw9IHggPj4gMTsKKyAgeCB8PSB4ID4+IDI7CisgIHggfD0geCA+PiA0Owor ICB4IHw9IHggPj4gODsKKyAgeCB8PSB4ID4+IDE2OworI2lmIFNJWkVPRl9VTE9ORyA9PSA4Cisg IHggfD0geCA+PiAzMjsKKyNlbmRpZgorICByZXR1cm4gKGludClvbmVzKHgpIC0gMTsKK30KKwor c3RhdGljIGlubGluZSBpbnQKK2NlaWxfbG9nMihyZWdpc3RlciB1bnNpZ25lZCBsb25nIHgpCit7 CisgIHJldHVybiBmbG9vcl9sb2cyKHgpICsgIVBPVzJfUCh4KTsKK30KKworI2RlZmluZSBMT0cy X0tBUkFUU1VCQV9ESUdJVFNfTVVSQUtFTiAoTE9HMl9LQVJBVFNVQkFfRElHSVRTLTEpCisjZGVm aW5lIEtBUkFUU1VCQV9ESUdJVFNfTVVSQUtFTiAoS0FSQVRTVUJBX0RJR0lUUz4+MSkKKworc3Rh dGljIFZBTFVFIGJpZzJzdHJfcG93ZXJfY2FjaGVbMzVdW01BWF9CSUcyU1RSX1RBQkxFX0VOVFJJ RVNdOworCitzdGF0aWMgdm9pZAorcG93ZXJfY2FjaGVfaW5pdCh2b2lkKQoreworICBpbnQgaSwg ajsKKyAgZm9yIChpID0gMDsgaSA8IDM1OyArK2kpIHsKKyAgICBiaWcyc3RyX3Bvd2VyX2NhY2hl W2ldWzBdID0KKyAgICAgIHJiX2JpZ19wb3cocmJfaW50MmJpZyhpKzIpLCBJTlQyRklYKEtBUkFU U1VCQV9ESUdJVFNfTVVSQUtFTikpOworICAgIHJiX2dsb2JhbF92YXJpYWJsZSgmYmlnMnN0cl9w b3dlcl9jYWNoZVtpXVswXSk7CisgICAgZm9yIChqID0gMTsgaiA8IE1BWF9CSUcyU1RSX1RBQkxF X0VOVFJJRVM7ICsraikgeworICAgICAgYmlnMnN0cl9wb3dlcl9jYWNoZVtpXVtqXSA9IFFuaWw7 CisgICAgfQorICB9Cit9CisKK3N0YXRpYyBpbmxpbmUgVkFMVUUKK3Bvd2VyX2NhY2hlX2dldF9w b3dlcjAoYmFzZSwgaSkKK3sKKyAgaWYgKE5JTF9QKGJpZzJzdHJfcG93ZXJfY2FjaGVbYmFzZSAt IDJdW2ldKSkgeworICAgIGJpZzJzdHJfcG93ZXJfY2FjaGVbYmFzZSAtIDJdW2ldID0KKyAgICAg IGJpZ25vcm0oYmlnc3FyKHBvd2VyX2NhY2hlX2dldF9wb3dlcjAoYmFzZSwgaSAtIDEpKSk7Cisg ICAgcmJfZ2xvYmFsX3ZhcmlhYmxlKCZiaWcyc3RyX3Bvd2VyX2NhY2hlW2Jhc2UgLSAyXVtpXSk7 CisgIH0KKyAgcmV0dXJuIGJpZzJzdHJfcG93ZXJfY2FjaGVbYmFzZSAtIDJdW2ldOworfQorCitz dGF0aWMgVkFMVUUKK3Bvd2VyX2NhY2hlX2dldF9wb3dlcihiYXNlLCBuMSwgbTEpCisgICAgaW50 IGJhc2U7CisgICAgbG9uZyBuMTsKKyAgICBsb25nKiBtMTsKK3sKKyAgbG9uZyBpLCBqLCBtOwor ICBWQUxVRSB0OworCisgIGlmIChuMSA8PSBLQVJBVFNVQkFfRElHSVRTX01VUkFLRU4pCisgICAg cmJfYnVnKCJuMSA+IEtBUkFUU1VCQV9ESUdJVFNfTVVSQUtFTiIpOworCisgIG0gPSBjZWlsX2xv ZzIobjEpOworICBpZiAobTEpICptMSA9IDEgPDwgbTsKKyAgaSA9IG0gLSBMT0cyX0tBUkFUU1VC QV9ESUdJVFNfTVVSQUtFTjsKKyAgaWYgKGkgPj0gTUFYX0JJRzJTVFJfVEFCTEVfRU5UUklFUykK KyAgICBpID0gTUFYX0JJRzJTVFJfVEFCTEVfRU5UUklFUyAtIDE7CisgIHQgPSBwb3dlcl9jYWNo ZV9nZXRfcG93ZXIwKGJhc2UsIGkpOworCisgIGogPSBLQVJBVFNVQkFfRElHSVRTX01VUkFLRU4q KDEgPDwgaSk7CisgIHdoaWxlIChuMSA+IGopIHsKKyAgICB0ID0gYmlnc3FyKHQpOworICAgIGog Kj0gMjsKKyAgfQorICByZXR1cm4gYmlnbm9ybSh0KTsKK30KKworLyogYmlnMnN0cl9tdXJha2Vu X2ZpbmRfbjEKKyAqCisgKiBMZXQgYSBuYXR1cmFsIG51bWJlciB4IGlzIGdpdmVuIGJ5OgorICog eCA9IDJeMCAqIHhfMCArIDJeMSAqIHhfMSArIC4uLiArIDJeKEIqbl8wIC0gMSkgKiB4X3tCKm5f MCAtIDF9LAorICogd2hlcmUgQiBpcyBCSVRTUEVSRElHIChpLmUuIEJESUdJVFMqQ0hBUl9CSVQp IGFuZCBuXzAgaXMKKyAqIFJCSUdOVU0oeCktPmxlbi4KKyAqCisgKiBOb3csIHdlIGFzc3VtZSBu XzEgPSBtaW5fbiBceyBuIHwgMl4oQipuXzAvMikgPD0gYl8xXihuXzEpIFx9LCBzbworICogaXQg aXMgcmVhbGl6ZWQgdGhhdCAyXihCKm5fMCkgPD0ge2JfMX1eezIqbl8xfSwgd2hlcmUgYl8xIGlz IGEKKyAqIGdpdmVuIHJhZGl4IG51bWJlci4gQW5kIHRoZW4sIHdlIGhhdmUgbl8xIDw9IChCKm5f MCkgLworICogKDIqbG9nXzIoYl8xKSksIHRoZXJlZm9yZSBuXzEgaXMgZ2l2ZW4gYnkgY2VpbCgo QipuXzApIC8KKyAqICgyKmxvZ18yKGJfMSkpKS4KKyAqLworc3RhdGljIGxvbmcKK2JpZzJzdHJf ZmluZF9uMShWQUxVRSB4LCBpbnQgYmFzZSkKK3sKKyAgICBzdGF0aWMgY29uc3QgZG91YmxlIGxv Z18yW10gPSB7CisgICAgICAgIDEuMCwgICAgICAgICAgICAgIDEuNTg0OTYyNTAwNzIxMTYsIDIu MCwKKyAgICAgICAgMi4zMjE5MjgwOTQ4ODczNiwgMi41ODQ5NjI1MDA3MjEsICAgMi41ODQ5NjI1 MDA3MjExNiwKKyAgICAgICAgMi44MDczNTQ5MjIwNTc2LCAgMy4wLCAgICAgICAgICAgICAgMy4x Njk5MjUwMDE0NDIzMSwKKyAgICAgICAgMy4zMjE5MjgwOTQ4ODczNiwgMy40NTk0MzE2MTg2Mzcz LCAgMy41ODQ5NjI1MDA3MjExNiwKKyAgICAgICAgMy43MDA0Mzk3MTgxNDEwOSwgMy44MDczNTQ5 MjIwNTc2LCAgMy45MDY4OTA1OTU2MDg1MiwKKyAgICAgICAgNC4wLCAgICAgICAgICAgICAgNC4w ODc0NjI4NDEyNTAzNCwgNC4xNjk5MjUwMDE0NDIzMSwKKyAgICAgICAgNC4yNDc5Mjc1MTM0NDM1 OSwgNC4zMjE5MjgwOTQ4ODczNiwgNC4zOTIzMTc0MjI3Nzg3NiwKKyAgICAgICAgNC40NTk0MzE2 MTg2MzczLCAgNC41MjM1NjE5NTYwNTcwMSwgNC41ODQ5NjI1MDA3MjExNiwKKyAgICAgICAgNC42 NDM4NTYxODk3NzQ3MiwgNC43MDA0Mzk3MTgxNDEwOSwgNC43NTQ4ODc1MDIxNjM0NywKKyAgICAg ICAgNC44MDczNTQ5MjIwNTc2LCAgNC44NTc5ODA5OTUxMjc1NywgNC45MDY4OTA1OTU2MDg1MiwK KyAgICAgICAgNC45NTQxOTYzMTAzODY4OCwgNS4wLCAgICAgICAgICAgICAgNS4wNDQzOTQxMTkz NTg0NSwKKyAgICAgICAgNS4wODc0NjI4NDEyNTAzNCwgNS4xMjkyODMwMTY5NDQ5NywgNS4xNjk5 MjUwMDE0NDIzMQorICAgIH07CisgICAgbG9uZyBiaXRzLCBuLCBpOworCisgICAgaWYgKGJhc2Ug PCAyICYmIDM2IDwgYmFzZSkKKyAgICAgIHJiX2J1ZygiaWxsZWdhbCByYWRpeCAlZCIsIGJhc2Up OworCisgICAgaWYgKEZJWE5VTV9QKHgpKSB7CisgICAgICAgIGJpdHMgPSAoU0laRU9GX0xPTkcq Q0hBUl9CSVQgLSAxKS8yICsgMTsKKyAgICB9CisgICAgZWxzZSBpZiAoQklHWkVST1AoeCkpIHsK KyAgICAgICAgcmV0dXJuIDA7CisgICAgfQorICAgIGVsc2UgeworICAgICAgICBiaXRzID0gQklU U1BFUkRJRypSQklHTlVNKHgpLT5sZW47CisgICAgfQorCisgICAgcmV0dXJuIChsb25nKWNlaWwo Yml0cy8oMipsb2dfMltiYXNlIC0gMl0pKTsKK30KKworc3RhdGljIGxvbmcKK2JpZzJzdHJfb3Jp Z19tdXJha2VuKHgsIGJhc2UsIHB0ciwgbGVuLCBoYmFzZSwgdHJpbSkKKyAgVkFMVUUgeDsKKyAg aW50IGJhc2U7CisgIGNoYXIqIHB0cjsKKyAgbG9uZyBsZW47CisgIGxvbmcgaGJhc2U7CisgIGlu dCB0cmltOworeworICBsb25nIGkgPSBSQklHTlVNKHgpLT5sZW4sIGogPSBsZW47CisgIEJESUdJ VCogZHMgPSBCRElHSVRTKHgpOworCisgIHdoaWxlIChpICYmIGogPiAwKSB7CisgICAgbG9uZyBr ID0gaTsKKyAgICBCRElHSVRfREJMIG51bSA9IDA7CisKKyAgICB3aGlsZSAoay0tKSB7ICAgICAg ICAgICAgICAgLyogeCAvIGhiYXNlICovCisgICAgICBudW0gPSBCSUdVUChudW0pICsgZHNba107 CisgICAgICBkc1trXSA9IChCRElHSVQpKG51bSAvIGhiYXNlKTsKKyAgICAgIG51bSAlPSBoYmFz ZTsKKyAgICB9CisgICAgaWYgKHRyaW0gJiYgZHNbaS0xXSA9PSAwKSBpLS07CisgICAgayA9IFNJ WkVPRl9CRElHSVRTOworICAgIHdoaWxlIChrLS0pIHsKKyAgICAgIHB0clstLWpdID0gcnVieV9k aWdpdG1hcFtudW0gJSBiYXNlXTsKKyAgICAgIG51bSAvPSBiYXNlOworICAgICAgaWYgKCF0cmlt ICYmIGogPD0gMCkgYnJlYWs7CisgICAgICBpZiAodHJpbSAmJiBpID09IDAgJiYgbnVtID09IDAp IGJyZWFrOworICAgIH0KKyAgfQorICBpZiAodHJpbSkgeworICAgIHdoaWxlIChwdHJbal0gPT0g JzAnKSBqKys7CisgICAgTUVNTU9WRShwdHIsIHB0ciArIGosIGNoYXIsIGxlbiAtIGopOworICAg IGxlbiAtPSBqOworICB9CisgIHJldHVybiBsZW47Cit9CisKK3N0YXRpYyBsb25nCitiaWcyc3Ry X2thcmF0c3ViYV9tdXJha2VuKHgsIGJhc2UsIHB0ciwgbjEsIGxlbiwgaGJhc2UsIHRyaW0pCisg ICAgVkFMVUUgeDsKKyAgICBpbnQgYmFzZTsKKyAgICBjaGFyKiBwdHI7CisgICAgbG9uZyBuMTsK KyAgICBsb25nIGxlbjsKKyAgICBsb25nIGhiYXNlOworICAgIGludCB0cmltOworeworICBsb25n IGxoLCBsbCwgbTE7CisgIFZBTFVFIGIsIHEsIHI7CisKKyAgaWYgKEZJWE5VTV9QKHgpKSB7Cisg ICAgVkFMVUUgc3RyID0gcmJfZml4MnN0cih4LCBiYXNlKTsKKyAgICBpZiAodHJpbSkgeworICAg ICAgaWYgKEZJWDJJTlQoeCkgPT0gMCkgcmV0dXJuIDA7CisgICAgICBNRU1DUFkocHRyLCBSU1RS SU5HKHN0ciktPnB0ciwgY2hhciwgUlNUUklORyhzdHIpLT5sZW4pOworICAgICAgcmV0dXJuIFJT VFJJTkcoc3RyKS0+bGVuOworICAgIH0KKyAgICBlbHNlIHsKKyAgICAgIG1lbXNldChwdHIsICcw JywgbGVuIC0gUlNUUklORyhzdHIpLT5sZW4pOworICAgICAgTUVNQ1BZKHB0ciArIGxlbiAtIFJT VFJJTkcoc3RyKS0+bGVuLCBSU1RSSU5HKHN0ciktPnB0ciwKKyAgICAgICAgICAgICBjaGFyLCBS U1RSSU5HKHN0ciktPmxlbik7CisgICAgICByZXR1cm4gbGVuOworICAgIH0KKyAgfQorICBpZiAo QklHWkVST1AoeCkpIHsKKyAgICBpZiAodHJpbSkgcmV0dXJuIDA7CisgICAgZWxzZSB7CisgICAg ICBtZW1zZXQocHRyLCAnMCcsIGxlbik7CisgICAgICByZXR1cm4gbGVuOworICAgIH0KKyAgfQor CisgIGlmIChuMSA8PSBLQVJBVFNVQkFfRElHSVRTX01VUkFLRU4pIHsKKyAgICByZXR1cm4gYmln MnN0cl9vcmlnX211cmFrZW4oeCwgYmFzZSwgcHRyLCBsZW4sIGhiYXNlLCB0cmltKTsKKyAgfQor CisgIGIgPSBwb3dlcl9jYWNoZV9nZXRfcG93ZXIoYmFzZSwgbjEsICZtMSk7CisgIGJpZ2Rpdm1v ZCh4LCBiLCAmcSwgJnIpOworICBsaCA9IGJpZzJzdHJfa2FyYXRzdWJhX211cmFrZW4ocSwgYmFz ZSwgcHRyLCAgICAgIChsZW4gLSBtMSkvMiwKKyAgICAgICAgICAgICAgICAgICAgICAgICAgICAg ICAgIGxlbiAtIG0xLCBoYmFzZSwgdHJpbSk7CisgIGxsID0gYmlnMnN0cl9rYXJhdHN1YmFfbXVy YWtlbihyLCBiYXNlLCBwdHIgKyBsaCwgbTEvMiwKKyAgICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgIG0xLCAgICAgICBoYmFzZSwgIWxoICYmIHRyaW0pOworCisgIHJldHVybiBsaCArIGxs OworfQorCitzdGF0aWMgVkFMVUUKK3JiX2JpZzJzdHIwX211cmFrZW4oeCwgYmFzZSwgdHJpbSkK KyAgVkFMVUUgeDsKKyAgaW50IGJhc2U7CisgIFZBTFVFIHRyaW07Cit7CisgIGludCBvZmY7Cisg IFZBTFVFIHNzLCB4eDsKKyAgbG9uZyBuMSwgbGVuLCBoYmFzZTsKKworICBpZiAoRklYTlVNX1Ao eCkpIHsKKyAgICByZXR1cm4gcmJfZml4MnN0cih4LCBiYXNlKTsKKyAgfQorICBpZiAoQklHWkVS T1AoeCkpIHsKKyAgICByZXR1cm4gcmJfc3RyX25ldzIoIjAiKTsKKyAgfQorCisgIGlmIChiYXNl IDwgMiAmJiAzNiA8IGJhc2UpCisgICAgcmJfcmFpc2UocmJfZUFyZ0Vycm9yLCAiaWxsZWdhbCBy YWRpeCAlZCIsIGJhc2UpOworCisgIG4xID0gYmlnMnN0cl9maW5kX24xKHgsIGJhc2UpOworICBz cyA9IHJiX3N0cl9uZXcoMCwgMipuMSArIDEpOyAvKiBwbHVzIG9uZSBmb3Igc2lnbiAqLworICBS U1RSSU5HKHNzKS0+cHRyWzBdID0gUkJJR05VTSh4KS0+c2lnbiA/ICcrJyA6ICctJzsKKworICBo YmFzZSA9IGJhc2UqYmFzZTsKKyNpZiBTSVpFT0ZfQkRJR0lUUyA+IDIKKyAgaGJhc2UgKj0gaGJh c2U7CisjZW5kaWYKKyAgb2ZmID0gIVJURVNUKHRyaW0pICYmICFSQklHTlVNKHgpLT5zaWduOwor ICB4eCA9IHJiX2JpZ19jbG9uZSh4KTsKKyAgUkJJR05VTSh4eCktPnNpZ24gPSAxOworICBpZiAo bjEgPD0gS0FSQVRTVUJBX0RJR0lUU19NVVJBS0VOKSB7CisgICAgbGVuID0gYmlnMnN0cl9vcmln X211cmFrZW4oeHgsIGJhc2UsIFJTVFJJTkcoc3MpLT5wdHIgKyBvZmYsCisgICAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgMipuMSwgaGJhc2UsIFJURVNUKHRyaW0pKTsKKyAgfQorICBlbHNl IHsKKyAgICBsZW4gPSBiaWcyc3RyX2thcmF0c3ViYV9tdXJha2VuKHh4LCBiYXNlLCBSU1RSSU5H KHNzKS0+cHRyICsgb2ZmLAorICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbjEs IDIqbjEsIGhiYXNlLCBSVEVTVCh0cmltKSk7CisgIH0KKworICBSU1RSSU5HKHNzKS0+cHRyW2xl bl0gPSAnXDAnOworICByYl9zdHJfcmVzaXplKHNzLCBsZW4pOworCisgIHJldHVybiBzczsKK30K KworVkFMVUUKK3JiX2JpZzJzdHJfbXVyYWtlbihWQUxVRSB4LCBpbnQgYmFzZSkKK3sKKyAgcmV0 dXJuIHJiX2JpZzJzdHIwX211cmFrZW4oeCwgYmFzZSwgMSk7Cit9CisKK3N0YXRpYyBWQUxVRQor cmJfYmlnX3RvX3NfbXVyYWtlbihhcmdjLCBhcmd2LCB4KQorICAgIGludCBhcmdjOworICAgIFZB TFVFICphcmd2OworICAgIFZBTFVFIHg7Cit7CisgICAgVkFMVUUgYjsKKyAgICBpbnQgYmFzZTsK KworICAgIHJiX3NjYW5fYXJncyhhcmdjLCBhcmd2LCAiMDEiLCAmYik7CisgICAgaWYgKGFyZ2Mg PT0gMCkgYmFzZSA9IDEwOworICAgIGVsc2UgYmFzZSA9IE5VTTJJTlQoYik7CisgICAgcmV0dXJu IHJiX2JpZzJzdHJfbXVyYWtlbih4LCBiYXNlKTsKK30KKwogc3RhdGljIHVuc2lnbmVkIGxvbmcK IGJpZzJ1bG9uZyh4LCB0eXBlKQogICAgIFZBTFVFIHg7CkBAIC0yMzE1LDYgKzI3MjcsNyBAQAog ICAgIHJiX2NCaWdudW0gPSByYl9kZWZpbmVfY2xhc3MoIkJpZ251bSIsIHJiX2NJbnRlZ2VyKTsK IAogICAgIHJiX2RlZmluZV9tZXRob2QocmJfY0JpZ251bSwgInRvX3MiLCByYl9iaWdfdG9fcywg LTEpOworICAgIHJiX2RlZmluZV9tZXRob2QocmJfY0JpZ251bSwgInRvX3MyIiwgcmJfYmlnX3Rv X3NfbXVyYWtlbiwgLTEpOwogICAgIHJiX2RlZmluZV9tZXRob2QocmJfY0JpZ251bSwgImNvZXJj ZSIsIHJiX2JpZ19jb2VyY2UsIDEpOwogICAgIHJiX2RlZmluZV9tZXRob2QocmJfY0JpZ251bSwg Ii1AIiwgcmJfYmlnX3VtaW51cywgMCk7CiAgICAgcmJfZGVmaW5lX21ldGhvZChyYl9jQmlnbnVt LCAiKyIsIHJiX2JpZ19wbHVzLCAxKTsKQEAgLTIzNDQsNCArMjc1Nyw3IEBACiAgICAgcmJfZGVm aW5lX21ldGhvZChyYl9jQmlnbnVtLCAidG9fZiIsIHJiX2JpZ190b19mLCAwKTsKICAgICByYl9k ZWZpbmVfbWV0aG9kKHJiX2NCaWdudW0sICJhYnMiLCByYl9iaWdfYWJzLCAwKTsKICAgICByYl9k ZWZpbmVfbWV0aG9kKHJiX2NCaWdudW0sICJzaXplIiwgcmJfYmlnX3NpemUsIDApOworCisgICAg aW5pdF9iaWcyc3RyX3RhYmxlKCk7CisgICAgcG93ZXJfY2FjaGVfaW5pdCgpOwogfQo= ------=_Part_127821_28137269.1186415421044--