From: Michael Selig Date: 2008-09-16T14:11:59+09:00 Subject: [ruby-core:18616] Re: Ruby 1.9 string performance ------------ar8A6atvBig2BqGDbbHp53 Content-Type: text/plain; format=flowed; delsp=yes; charset=utf-8 Content-Transfer-Encoding: 7bit > On Fri, 12 Sep 2008 02:16:51 +1000, NARUSE, Yui > wrote: > >> >> If you split your patch into small atomic patches, >> your patch will be merged rapidly. >> Here are 3 other patches for String performance. Please apply "codepoint.pat" last after all the other patches (including the 2 from the previous mail) becuase it overlaps. Details for ChangeLog: casecmp.pat: - Optimize String#casecmp for single-byte character strings case.pat: - Optimize String#upcase, downcase & swapcase for single-byte character strings codepoint.pat: - Added new rb_enc_codepoint_l() function to encoding.c which returns the codepoint, same as rb_enc_codepoint(), plus returns the character length - Modified string.c to use it, avoiding extra calls to determine length of character - Changed "single_byte_optimizable()" to a #define (for compilers which don't do "inline" properly) - All these changes make many methods on multi-byte character strings somewhat faster (maybe 4 -5% on UTF-8 - haven't tested others, but I think should be similar) I also have some comments and questions: 1) Currently "String#rstrip" on multi-byte character sets seems to work from the start to the end of the string. Can't it work backwards, which would be faster? 2) A recent change to tr_trans() (used by String#tr & others) fix the "coderange" issue mentioned earlier, sets the coderange of the result to that of the calling string object but only if the coderange of both the "from" string and the "to" string are the same as the input string. It is my understanding that the coderange of the result is dependent upon only the "calling" string object and the "to" string - not the "from" string. If this is right (please tell me if I am not!), then I think a better implementation is to use something like cr = ENC_CODERANGE_AND(ENC_CODERANGE(str), ENC_CODERANGE(to_str)); because this will preserve the "valid" flag if one of the strings is 7-bit ascii, and the other isn't (eg: UTF-8). 3) rb_str_modify() is actually a slight problem due to the fact that it clears the coderange flags. In many cases you then have to reset them back the way they were to avoid costly string re-scans. But sometimes you actually may want to reset the flags if they indicated "broken" and an "innocuous" change is then made (eg: changing a byte), because the change may make the string valid again. It seems to me that a neat implementation would be to have a function called say "str_modify()" which is almost the same as rb_str_modify()", but if the coderange says "broken", it clears it (forcing a leter rescan). If the coderange is valid it should leave it. Then this new function can be used in most places in string.c to save mucking around with the coderange flags. Cheers, Mike ------------ar8A6atvBig2BqGDbbHp53 Content-Disposition: attachment; filename=case.pat Content-Type: application/octet-stream; name=case.pat Content-Transfer-Encoding: Base64 SW5kZXg6IHN0cmluZy5jCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIHN0cmluZy5j CShyZXZpc2lvbiAxOTM3NCkKKysrIHN0cmluZy5jCSh3b3JraW5nIGNvcHkpCkBA IC00MDQxLDE3ICs0MDQxLDMwIEBACiAgICAgcmJfc3RyX21vZGlmeShzdHIpOwog ICAgIGVuYyA9IFNUUl9FTkNfR0VUKHN0cik7CiAgICAgcyA9IFJTVFJJTkdfUFRS KHN0cik7IHNlbmQgPSBSU1RSSU5HX0VORChzdHIpOwotICAgIHdoaWxlIChzIDwg c2VuZCkgewotCXVuc2lnbmVkIGludCBjID0gcmJfZW5jX2NvZGVwb2ludChzLCBz ZW5kLCBlbmMpOworICAgIGlmIChzaW5nbGVfYnl0ZV9vcHRpbWl6YWJsZShzdHIp KSB7CisJd2hpbGUgKHMgPCBzZW5kKSB7CisJICAgIHVuc2lnbmVkIGludCBjID0g Kih1bnNpZ25lZCBjaGFyICopczsKIAotCWlmIChyYl9lbmNfaXNsb3dlcihjLCBl bmMpKSB7Ci0JICAgIC8qIGFzc3VtaW5nIHRvdXBwZXIgcmV0dXJucyBjb2RlcG9p bnQgd2l0aCBzYW1lIHNpemUgKi8KLQkgICAgcmJfZW5jX21iY3B1dChyYl9lbmNf dG91cHBlcihjLCBlbmMpLCBzLCBlbmMpOwotCSAgICBtb2RpZnkgPSAxOworCSAg ICBpZiAocmJfZW5jX2lzbG93ZXIoYywgZW5jKSkgeworCQkqcyA9IHJiX2VuY190 b3VwcGVyKGMgLCBlbmMpOworCQltb2RpZnkgPSAxOworCSAgICB9CisJICAgIHMr KzsKIAl9Ci0JcyArPSByYl9lbmNfY29kZWxlbihjLCBlbmMpOwogICAgIH0KKyAg ICBlbHNlIHsKKwl3aGlsZSAocyA8IHNlbmQpIHsKKwkgICAgdW5zaWduZWQgaW50 IGMgPSByYl9lbmNfY29kZXBvaW50KHMsIHNlbmQsIGVuYyk7CiAKKwkgICAgaWYg KHJiX2VuY19pc2xvd2VyKGMsIGVuYykpIHsKKwkJLyogYXNzdW1pbmcgdG91cHBl ciByZXR1cm5zIGNvZGVwb2ludCB3aXRoIHNhbWUgc2l6ZSAqLworCQlyYl9lbmNf bWJjcHV0KHJiX2VuY190b3VwcGVyKGMsIGVuYyksIHMsIGVuYyk7CisJCW1vZGlm eSA9IDE7CisJICAgIH0KKwkgICAgcyArPSByYl9lbmNfY29kZWxlbihjLCBlbmMp OworCX0KKyAgICB9CisKICAgICBFTkNfQ09ERVJBTkdFX1NFVChzdHIsIGNyKTsK ICAgICBpZiAobW9kaWZ5KSByZXR1cm4gc3RyOwogICAgIHJldHVybiBRbmlsOwpA QCAtNDA5OSwxNyArNDExMiwzMCBAQAogICAgIHJiX3N0cl9tb2RpZnkoc3RyKTsK ICAgICBlbmMgPSBTVFJfRU5DX0dFVChzdHIpOwogICAgIHMgPSBSU1RSSU5HX1BU UihzdHIpOyBzZW5kID0gUlNUUklOR19FTkQoc3RyKTsKLSAgICB3aGlsZSAocyA8 IHNlbmQpIHsKLQl1bnNpZ25lZCBpbnQgYyA9IHJiX2VuY19jb2RlcG9pbnQocywg c2VuZCwgZW5jKTsKKyAgICBpZiAoc2luZ2xlX2J5dGVfb3B0aW1pemFibGUoc3Ry KSkgeworCXdoaWxlIChzIDwgc2VuZCkgeworCSAgICB1bnNpZ25lZCBpbnQgYyA9 ICoodW5zaWduZWQgY2hhciAqKXM7CiAKLQlpZiAocmJfZW5jX2lzdXBwZXIoYywg ZW5jKSkgewotCSAgICAvKiBhc3N1bWluZyB0b3VwcGVyIHJldHVybnMgY29kZXBv aW50IHdpdGggc2FtZSBzaXplICovCi0JICAgIHJiX2VuY19tYmNwdXQocmJfZW5j X3RvbG93ZXIoYywgZW5jKSwgcywgZW5jKTsKLQkgICAgbW9kaWZ5ID0gMTsKKwkg ICAgaWYgKHJiX2VuY19pc3VwcGVyKGMsIGVuYykpIHsKKwkJKnMgPSByYl9lbmNf dG9sb3dlcihjICwgZW5jKTsKKwkJbW9kaWZ5ID0gMTsKKwkgICAgfQorCSAgICBz Kys7CiAJfQotCXMgKz0gcmJfZW5jX2NvZGVsZW4oYywgZW5jKTsKICAgICB9Cisg ICAgZWxzZSB7CisJd2hpbGUgKHMgPCBzZW5kKSB7CisJICAgIHVuc2lnbmVkIGlu dCBjID0gcmJfZW5jX2NvZGVwb2ludChzLCBzZW5kLCBlbmMpOwogCisJICAgIGlm IChyYl9lbmNfaXN1cHBlcihjLCBlbmMpKSB7CisJCS8qIGFzc3VtaW5nIHRvbG93 ZXIgcmV0dXJucyBjb2RlcG9pbnQgd2l0aCBzYW1lIHNpemUgKi8KKwkJcmJfZW5j X21iY3B1dChyYl9lbmNfdG9sb3dlcihjLCBlbmMpLCBzLCBlbmMpOworCQltb2Rp ZnkgPSAxOworCSAgICB9CisJICAgIHMgKz0gcmJfZW5jX2NvZGVsZW4oYywgZW5j KTsKKwl9CisgICAgfQorCiAgICAgRU5DX0NPREVSQU5HRV9TRVQoc3RyLCBjcik7 CiAgICAgaWYgKG1vZGlmeSkgcmV0dXJuIHN0cjsKICAgICByZXR1cm4gUW5pbDsK QEAgLTQyMjgsMjAgKzQyNTQsMzcgQEAKICAgICByYl9zdHJfbW9kaWZ5KHN0cik7 CiAgICAgZW5jID0gU1RSX0VOQ19HRVQoc3RyKTsKICAgICBzID0gUlNUUklOR19Q VFIoc3RyKTsgc2VuZCA9IFJTVFJJTkdfRU5EKHN0cik7Ci0gICAgd2hpbGUgKHMg PCBzZW5kKSB7Ci0JdW5zaWduZWQgaW50IGMgPSByYl9lbmNfY29kZXBvaW50KHMs IHNlbmQsIGVuYyk7CisgICAgaWYgKHNpbmdsZV9ieXRlX29wdGltaXphYmxlKHN0 cikpIHsKKwl3aGlsZSAocyA8IHNlbmQpIHsKKwkgICAgdW5zaWduZWQgaW50IGMg PSAqKHVuc2lnbmVkIGNoYXIgKilzOwogCi0JaWYgKHJiX2VuY19pc3VwcGVyKGMs IGVuYykpIHsKLQkgICAgLyogYXNzdW1pbmcgdG91cHBlciByZXR1cm5zIGNvZGVw b2ludCB3aXRoIHNhbWUgc2l6ZSAqLwotCSAgICByYl9lbmNfbWJjcHV0KHJiX2Vu Y190b2xvd2VyKGMsIGVuYyksIHMsIGVuYyk7Ci0JICAgIG1vZGlmeSA9IDE7CisJ ICAgIGlmIChyYl9lbmNfaXN1cHBlcihjLCBlbmMpKSB7CisJCSpzID0gcmJfZW5j X3RvbG93ZXIoYyAsIGVuYyk7CisJCW1vZGlmeSA9IDE7CisJICAgIH0KKwkgICAg ZWxzZSBpZiAocmJfZW5jX2lzbG93ZXIoYywgZW5jKSkgeworCQkqcyA9IHJiX2Vu Y190b3VwcGVyKGMgLCBlbmMpOworCQltb2RpZnkgPSAxOworCSAgICB9CisJICAg IHMrKzsKIAl9Ci0JZWxzZSBpZiAocmJfZW5jX2lzbG93ZXIoYywgZW5jKSkgewot CSAgICAvKiBhc3N1bWluZyB0b3VwcGVyIHJldHVybnMgY29kZXBvaW50IHdpdGgg c2FtZSBzaXplICovCi0JICAgIHJiX2VuY19tYmNwdXQocmJfZW5jX3RvdXBwZXIo YywgZW5jKSwgcywgZW5jKTsKLQkgICAgbW9kaWZ5ID0gMTsKKyAgICB9CisgICAg ZWxzZSB7CisJd2hpbGUgKHMgPCBzZW5kKSB7CisJICAgIHVuc2lnbmVkIGludCBj ID0gcmJfZW5jX2NvZGVwb2ludChzLCBzZW5kLCBlbmMpOworCisJICAgIGlmIChy Yl9lbmNfaXN1cHBlcihjLCBlbmMpKSB7CisJCS8qIGFzc3VtaW5nIHRvdXBwZXIg cmV0dXJucyBjb2RlcG9pbnQgd2l0aCBzYW1lIHNpemUgKi8KKwkJcmJfZW5jX21i Y3B1dChyYl9lbmNfdG9sb3dlcihjLCBlbmMpLCBzLCBlbmMpOworCQltb2RpZnkg PSAxOworCSAgICB9CisJICAgIGVsc2UgaWYgKHJiX2VuY19pc2xvd2VyKGMsIGVu YykpIHsKKwkJLyogYXNzdW1pbmcgdG91cHBlciByZXR1cm5zIGNvZGVwb2ludCB3 aXRoIHNhbWUgc2l6ZSAqLworCQlyYl9lbmNfbWJjcHV0KHJiX2VuY190b3VwcGVy KGMsIGVuYyksIHMsIGVuYyk7CisJCW1vZGlmeSA9IDE7CisJICAgIH0KKwkgICAg cyArPSByYl9lbmNfY29kZWxlbihjLCBlbmMpOwogCX0KLQlzICs9IHJiX2VuY19j b2RlbGVuKGMsIGVuYyk7CiAgICAgfQogCiAgICAgRU5DX0NPREVSQU5HRV9TRVQo c3RyLCBjcik7Cg== ------------ar8A6atvBig2BqGDbbHp53 Content-Disposition: attachment; filename=casecmp.pat Content-Type: application/octet-stream; name=casecmp.pat Content-Transfer-Encoding: Base64 SW5kZXg6IHN0cmluZy5jCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIHN0cmluZy5j CShyZXZpc2lvbiAxOTM3NCkKKysrIHN0cmluZy5jCSh3b3JraW5nIGNvcHkpCkBA IC0yMDY3LDE5ICsyMDY3LDMzIEBACiAKICAgICBwMSA9IFJTVFJJTkdfUFRSKHN0 cjEpOyBwMWVuZCA9IFJTVFJJTkdfRU5EKHN0cjEpOwogICAgIHAyID0gUlNUUklO R19QVFIoc3RyMik7IHAyZW5kID0gUlNUUklOR19FTkQoc3RyMik7Ci0gICAgd2hp bGUgKHAxIDwgcDFlbmQgJiYgcDIgPCBwMmVuZCkgewotCXVuc2lnbmVkIGludCBj MSA9IHJiX2VuY19jb2RlcG9pbnQocDEsIHAxZW5kLCBlbmMpOwotCXVuc2lnbmVk IGludCBjMiA9IHJiX2VuY19jb2RlcG9pbnQocDIsIHAyZW5kLCBlbmMpOworICAg IGlmIChzaW5nbGVfYnl0ZV9vcHRpbWl6YWJsZShzdHIxKSAmJiBzaW5nbGVfYnl0 ZV9vcHRpbWl6YWJsZShzdHIyKSkgeworCXdoaWxlIChwMSA8IHAxZW5kICYmIHAy IDwgcDJlbmQpIHsKKwkgICAgaWYgKCpwMSAhPSAqcDIpIHsKKwkJaW50IGMxID0g cmJfZW5jX3RvdXBwZXIoKih1bnNpZ25lZCBjaGFyICopcDEsIGVuYyk7CisJCWlu dCBjMiA9IHJiX2VuY190b3VwcGVyKCoodW5zaWduZWQgY2hhciAqKXAyLCBlbmMp OworCQlpZiAoYzEgPiBjMikgcmV0dXJuIElOVDJGSVgoMSk7CisJCWlmIChjMSA8 IGMyKSByZXR1cm4gSU5UMkZJWCgtMSk7CisJICAgIH0KKwkgICAgcDErKzsKKwkg ICAgcDIrKzsKKwl9CisgICAgfQorICAgIGVsc2UgeworCXdoaWxlIChwMSA8IHAx ZW5kICYmIHAyIDwgcDJlbmQpIHsKKwkgICAgdW5zaWduZWQgaW50IGMxID0gcmJf ZW5jX2NvZGVwb2ludChwMSwgcDFlbmQsIGVuYyk7CisJICAgIHVuc2lnbmVkIGlu dCBjMiA9IHJiX2VuY19jb2RlcG9pbnQocDIsIHAyZW5kLCBlbmMpOwogCi0JaWYg KGMxICE9IGMyKSB7Ci0JICAgIGMxID0gcmJfZW5jX3RvdXBwZXIoYzEsIGVuYyk7 Ci0JICAgIGMyID0gcmJfZW5jX3RvdXBwZXIoYzIsIGVuYyk7Ci0JICAgIGlmIChj MSA+IGMyKSByZXR1cm4gSU5UMkZJWCgxKTsKLQkgICAgaWYgKGMxIDwgYzIpIHJl dHVybiBJTlQyRklYKC0xKTsKKwkgICAgaWYgKGMxICE9IGMyKSB7CisJCWMxID0g cmJfZW5jX3RvdXBwZXIoYzEsIGVuYyk7CisJCWMyID0gcmJfZW5jX3RvdXBwZXIo YzIsIGVuYyk7CisJCWlmIChjMSA+IGMyKSByZXR1cm4gSU5UMkZJWCgxKTsKKwkJ aWYgKGMxIDwgYzIpIHJldHVybiBJTlQyRklYKC0xKTsKKwkgICAgfQorCSAgICBs ZW4gPSByYl9lbmNfY29kZWxlbihjMSwgZW5jKTsKKwkgICAgcDEgKz0gbGVuOwor CSAgICBwMiArPSBsZW47CiAJfQotCWxlbiA9IHJiX2VuY19jb2RlbGVuKGMxLCBl bmMpOwotCXAxICs9IGxlbjsKLQlwMiArPSBsZW47CiAgICAgfQogICAgIGlmIChS U1RSSU5HX0xFTihzdHIxKSA9PSBSU1RSSU5HX0xFTihzdHIyKSkgcmV0dXJuIElO VDJGSVgoMCk7CiAgICAgaWYgKFJTVFJJTkdfTEVOKHN0cjEpID4gUlNUUklOR19M RU4oc3RyMikpIHJldHVybiBJTlQyRklYKDEpOwo= ------------ar8A6atvBig2BqGDbbHp53 Content-Disposition: attachment; filename=codepoint.pat Content-Type: application/octet-stream; name=codepoint.pat Content-Transfer-Encoding: Base64 SW5kZXg6IGVuY29kaW5nLmMKPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQotLS0gZW5jb2Rp bmcuYwkocmV2aXNpb24gMTkzNzQpCisrKyBlbmNvZGluZy5jCSh3b3JraW5nIGNv cHkpCkBAIC03NjgsNiArNzY4LDIyIEBACiAJcmJfcmFpc2UocmJfZUFyZ0Vycm9y LCAiaW52YWxpZCBieXRlIHNlcXVlbmNlIGluICVzIiwgcmJfZW5jX25hbWUoZW5j KSk7CiB9CiAKKy8qIEFzIGFib3ZlLCBidXQgYWxzbyByZXR1cm4gY2hhcmFjdGVy IGxlbmd0aCAqLwordW5zaWduZWQgaW50CityYl9lbmNfY29kZXBvaW50X2woY29u c3QgY2hhciAqcCwgY29uc3QgY2hhciAqZSwgaW50ICpsZW4sIHJiX2VuY29kaW5n ICplbmMpCit7CisgICAgaW50IHI7CisgICAgaWYgKGUgPD0gcCkKKyAgICAgICAg cmJfcmFpc2UocmJfZUFyZ0Vycm9yLCAiZW1wdHkgc3RyaW5nIik7CisgICAgciA9 IHJiX2VuY19wcmVjaXNlX21iY2xlbihwLCBlLCBlbmMpOworICAgIGlmIChNQkNM RU5fQ0hBUkZPVU5EX1AocikpIHsKKwkqbGVuID0gcjsKKyAgICAgICAgcmV0dXJu IHJiX2VuY19tYmNfdG9fY29kZXBvaW50KHAsIGUsIGVuYyk7CisgICAgfQorICAg IGVsc2UKKwlyYl9yYWlzZShyYl9lQXJnRXJyb3IsICJpbnZhbGlkIGJ5dGUgc2Vx dWVuY2UgaW4gJXMiLCByYl9lbmNfbmFtZShlbmMpKTsKK30KKwogaW50CiByYl9l bmNfY29kZWxlbihpbnQgYywgcmJfZW5jb2RpbmcgKmVuYykKIHsKSW5kZXg6IGlu Y2x1ZGUvcnVieS9lbmNvZGluZy5oCj09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIGlu Y2x1ZGUvcnVieS9lbmNvZGluZy5oCShyZXZpc2lvbiAxOTM3NCkKKysrIGluY2x1 ZGUvcnVieS9lbmNvZGluZy5oCSh3b3JraW5nIGNvcHkpCkBAIC0xMjEsNiArMTIx LDcgQEAKIAogLyogLT4gY29kZSBvciByYWlzZSBleGNlcHRpb24gKi8KIHVuc2ln bmVkIGludCByYl9lbmNfY29kZXBvaW50KGNvbnN0IGNoYXIgKnAsIGNvbnN0IGNo YXIgKmUsIHJiX2VuY29kaW5nICplbmMpOwordW5zaWduZWQgaW50IHJiX2VuY19j b2RlcG9pbnRfbChjb25zdCBjaGFyICpwLCBjb25zdCBjaGFyICplLCBpbnQgKmxl biwgcmJfZW5jb2RpbmcgKmVuYyk7CiAjZGVmaW5lIHJiX2VuY19tYmNfdG9fY29k ZXBvaW50KHAsIGUsIGVuYykgT05JR0VOQ19NQkNfVE9fQ09ERShlbmMsKFVDaGFy KikocCksKFVDaGFyKikoZSkpCiAKIC8qIC0+IGNvZGVsZW4+MCBvciByYWlzZSBl eGNlcHRpb24gKi8KSW5kZXg6IHN0cmluZy5jCj09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0K LS0tIHN0cmluZy5jLm9sZAkyMDA4LTA5LTE2IDEzOjAwOjEyLjAwMDAwMDAwMCAr MTAwMAorKysgc3RyaW5nLmMJMjAwOC0wOS0xNiAxMzowNToxMS4wMDAwMDAwMDAg KzEwMDAKQEAgLTExMiwyMyArMTEyLDkgQEAKIAogI2RlZmluZSBTVFJfRU5DX0dF VChzdHIpIHJiX2VuY19mcm9tX2luZGV4KEVOQ09ESU5HX0dFVChzdHIpKQogCi1z dGF0aWMgaW5saW5lIGludAotc2luZ2xlX2J5dGVfb3B0aW1pemFibGUoVkFMVUUg c3RyKQotewotICAgIHJiX2VuY29kaW5nICplbmM7Ci0KLSAgICAvKiBDb25zZXJ2 YXRpdmUuICBJdCBtYXkgYmUgRU5DX0NPREVSQU5HRV9VTktOT1dOLiAqLwotICAg IGlmIChFTkNfQ09ERVJBTkdFKHN0cikgPT0gRU5DX0NPREVSQU5HRV83QklUKQot ICAgICAgICByZXR1cm4gMTsKLQotICAgIGVuYyA9IFNUUl9FTkNfR0VUKHN0cik7 Ci0gICAgaWYgKHJiX2VuY19tYm1heGxlbihlbmMpID09IDEpCi0gICAgICAgIHJl dHVybiAxOwotCi0gICAgLyogQ29uc2VydmF0aXZlLiAgUG9zc2libHkgc2luZ2xl IGJ5dGUuCi0gICAgICogIlx4YTEiIGluIFNoaWZ0X0pJUyBmb3IgZXhhbXBsZS4g Ki8KLSAgICByZXR1cm4gMDsKLX0KKy8qIENvbnNlcnZhdGl2ZS4gIFBvc3NpYmx5 IHNpbmdsZSBieXRlLgorICogIlx4YTEiIGluIFNoaWZ0X0pJUyBmb3IgZXhhbXBs ZS4gKi8KKyNkZWZpbmUgc2luZ2xlX2J5dGVfb3B0aW1pemFibGUoc3RyKSAoRU5D X0NPREVSQU5HRShzdHIpID09IEVOQ19DT0RFUkFOR0VfN0JJVCB8fCByYl9lbmNf bWJtYXhsZW4oU1RSX0VOQ19HRVQoc3RyKSkgPT0gMSkKIAogVkFMVUUgcmJfZnM7 CiAKQEAgLTIwNzYsNyArMjA2Miw3IEBACiBzdGF0aWMgVkFMVUUKIHJiX3N0cl9j YXNlY21wKFZBTFVFIHN0cjEsIFZBTFVFIHN0cjIpCiB7Ci0gICAgbG9uZyBsZW47 CisgICAgaW50IGxlbjsKICAgICByYl9lbmNvZGluZyAqZW5jOwogICAgIGNoYXIg KnAxLCAqcDFlbmQsICpwMiwgKnAyZW5kOwogCkBAIC0yMTAyLDcgKzIwODgsNyBA QAogICAgIH0KICAgICBlbHNlIHsKIAl3aGlsZSAocDEgPCBwMWVuZCAmJiBwMiA8 IHAyZW5kKSB7Ci0JICAgIHVuc2lnbmVkIGludCBjMSA9IHJiX2VuY19jb2RlcG9p bnQocDEsIHAxZW5kLCBlbmMpOworCSAgICB1bnNpZ25lZCBpbnQgYzEgPSByYl9l bmNfY29kZXBvaW50X2wocDEsIHAxZW5kLCAmbGVuLCBlbmMpOwogCSAgICB1bnNp Z25lZCBpbnQgYzIgPSByYl9lbmNfY29kZXBvaW50KHAyLCBwMmVuZCwgZW5jKTsK IAogCSAgICBpZiAoYzEgIT0gYzIpIHsKQEAgLTIxMTEsNyArMjA5Nyw2IEBACiAJ CWlmIChjMSA+IGMyKSByZXR1cm4gSU5UMkZJWCgxKTsKIAkJaWYgKGMxIDwgYzIp IHJldHVybiBJTlQyRklYKC0xKTsKIAkgICAgfQotCSAgICBsZW4gPSByYl9lbmNf Y29kZWxlbihjMSwgZW5jKTsKIAkgICAgcDEgKz0gbGVuOwogCSAgICBwMiArPSBs ZW47CiAJfQpAQCAtMzg3Niw4ICszODYxLDcgQEAKICAgICAgICAgfQogICAgICAg ICBuID0gTUJDTEVOX0NIQVJGT1VORF9MRU4obik7CiAKLQljID0gcmJfZW5jX2Nv ZGVwb2ludChwLCBwZW5kLCBlbmMpOwotCW4gPSByYl9lbmNfY29kZWxlbihjLCBl bmMpOworCWMgPSByYl9lbmNfY29kZXBvaW50X2wocCwgcGVuZCwgJm4sIGVuYyk7 CiAKIAlwICs9IG47CiAJaWYgKGMgPT0gJyInfHwgYyA9PSAnXFwnIHx8CkBAIC00 MDg5LDE0ICs0MDczLDE1IEBACiAgICAgfQogICAgIGVsc2UgewogCXdoaWxlIChz IDwgc2VuZCkgewotCSAgICB1bnNpZ25lZCBpbnQgYyA9IHJiX2VuY19jb2RlcG9p bnQocywgc2VuZCwgZW5jKTsKKwkgICAgaW50IGNsZW47CisJICAgIHVuc2lnbmVk IGludCBjID0gcmJfZW5jX2NvZGVwb2ludF9sKHMsIHNlbmQsICZjbGVuLCBlbmMp OwogCiAJICAgIGlmIChyYl9lbmNfaXNsb3dlcihjLCBlbmMpKSB7CiAJCS8qIGFz c3VtaW5nIHRvdXBwZXIgcmV0dXJucyBjb2RlcG9pbnQgd2l0aCBzYW1lIHNpemUg Ki8KIAkJcmJfZW5jX21iY3B1dChyYl9lbmNfdG91cHBlcihjLCBlbmMpLCBzLCBl bmMpOwogCQltb2RpZnkgPSAxOwogCSAgICB9Ci0JICAgIHMgKz0gcmJfZW5jX2Nv ZGVsZW4oYywgZW5jKTsKKwkgICAgcyArPSBjbGVuOwogCX0KICAgICB9CiAKQEAg LTQxNjAsMTQgKzQxNDUsMTUgQEAKICAgICB9CiAgICAgZWxzZSB7CiAJd2hpbGUg KHMgPCBzZW5kKSB7Ci0JICAgIHVuc2lnbmVkIGludCBjID0gcmJfZW5jX2NvZGVw b2ludChzLCBzZW5kLCBlbmMpOworCSAgICBpbnQgY2xlbjsKKwkgICAgdW5zaWdu ZWQgaW50IGMgPSByYl9lbmNfY29kZXBvaW50X2wocywgc2VuZCwgJmNsZW4sIGVu Yyk7CiAKIAkgICAgaWYgKHJiX2VuY19pc3VwcGVyKGMsIGVuYykpIHsKIAkJLyog YXNzdW1pbmcgdG9sb3dlciByZXR1cm5zIGNvZGVwb2ludCB3aXRoIHNhbWUgc2l6 ZSAqLwogCQlyYl9lbmNfbWJjcHV0KHJiX2VuY190b2xvd2VyKGMsIGVuYyksIHMs IGVuYyk7CiAJCW1vZGlmeSA9IDE7CiAJICAgIH0KLQkgICAgcyArPSByYl9lbmNf Y29kZWxlbihjLCBlbmMpOworCSAgICBzICs9IGNsZW47CiAJfQogICAgIH0KIApA QCAtNDIyMCwyNSArNDIwNiwyNiBAQAogICAgIGludCBtb2RpZnkgPSAwOwogICAg IHVuc2lnbmVkIGludCBjOwogICAgIGludCBjciA9IEVOQ19DT0RFUkFOR0Uoc3Ry KTsKKyAgICBpbnQgY2xlbjsKIAogICAgIHJiX3N0cl9tb2RpZnkoc3RyKTsKICAg ICBlbmMgPSBTVFJfRU5DX0dFVChzdHIpOwogICAgIGlmIChSU1RSSU5HX0xFTihz dHIpID09IDAgfHwgIVJTVFJJTkdfUFRSKHN0cikpIHJldHVybiBRbmlsOwogICAg IHMgPSBSU1RSSU5HX1BUUihzdHIpOyBzZW5kID0gUlNUUklOR19FTkQoc3RyKTsK IAotICAgIGMgPSByYl9lbmNfY29kZXBvaW50KHMsIHNlbmQsIGVuYyk7CisgICAg YyA9IHJiX2VuY19jb2RlcG9pbnRfbChzLCBzZW5kLCAmY2xlbiwgZW5jKTsKICAg ICBpZiAocmJfZW5jX2lzbG93ZXIoYywgZW5jKSkgewogCXJiX2VuY19tYmNwdXQo cmJfZW5jX3RvdXBwZXIoYywgZW5jKSwgcywgZW5jKTsKIAltb2RpZnkgPSAxOwog ICAgIH0KLSAgICBzICs9IHJiX2VuY19jb2RlbGVuKGMsIGVuYyk7CisgICAgcyAr PSBjbGVuOwogICAgIHdoaWxlIChzIDwgc2VuZCkgewotCWMgPSByYl9lbmNfY29k ZXBvaW50KHMsIHNlbmQsIGVuYyk7CisJYyA9IHJiX2VuY19jb2RlcG9pbnRfbChz LCBzZW5kLCAmY2xlbiwgZW5jKTsKIAlpZiAocmJfZW5jX2lzdXBwZXIoYywgZW5j KSkgewogCSAgICByYl9lbmNfbWJjcHV0KHJiX2VuY190b2xvd2VyKGMsIGVuYyks IHMsIGVuYyk7CiAJICAgIG1vZGlmeSA9IDE7CiAJfQotCXMgKz0gcmJfZW5jX2Nv ZGVsZW4oYywgZW5jKTsKKwlzICs9IGNsZW47CiAgICAgfQogCiAgICAgRU5DX0NP REVSQU5HRV9TRVQoc3RyLCBjcik7CkBAIC00MzA2LDcgKzQyOTMsOCBAQAogICAg IH0KICAgICBlbHNlIHsKIAl3aGlsZSAocyA8IHNlbmQpIHsKLQkgICAgdW5zaWdu ZWQgaW50IGMgPSByYl9lbmNfY29kZXBvaW50KHMsIHNlbmQsIGVuYyk7CisJICAg IGludCBjbGVuOworCSAgICB1bnNpZ25lZCBpbnQgYyA9IHJiX2VuY19jb2RlcG9p bnRfbChzLCBzZW5kLCAmY2xlbiwgZW5jKTsKIAogCSAgICBpZiAocmJfZW5jX2lz dXBwZXIoYywgZW5jKSkgewogCQkvKiBhc3N1bWluZyB0b3VwcGVyIHJldHVybnMg Y29kZXBvaW50IHdpdGggc2FtZSBzaXplICovCkBAIC00MzE4LDcgKzQzMDYsNyBA QAogCQlyYl9lbmNfbWJjcHV0KHJiX2VuY190b3VwcGVyKGMsIGVuYyksIHMsIGVu Yyk7CiAJCW1vZGlmeSA9IDE7CiAJICAgIH0KLQkgICAgcyArPSByYl9lbmNfY29k ZWxlbihjLCBlbmMpOworCSAgICBzICs9IGNsZW47CiAJfQogICAgIH0KIApAQCAt NDM1OSwxOSArNDM0NywyMSBAQAogc3RhdGljIHVuc2lnbmVkIGludAogdHJuZXh0 KHN0cnVjdCB0ciAqdCwgcmJfZW5jb2RpbmcgKmVuYykKIHsKKyAgICBpbnQgbGVu OworCiAgICAgZm9yICg7OykgewogCWlmICghdC0+Z2VuKSB7CiAJICAgIGlmICh0 LT5wID09IHQtPnBlbmQpIHJldHVybiAtMTsKIAkgICAgaWYgKHQtPnAgPCB0LT5w ZW5kIC0gMSAmJiAqdC0+cCA9PSAnXFwnKSB7CiAJCXQtPnArKzsKIAkgICAgfQot CSAgICB0LT5ub3cgPSByYl9lbmNfY29kZXBvaW50KHQtPnAsIHQtPnBlbmQsIGVu Yyk7Ci0JICAgIHQtPnAgKz0gcmJfZW5jX2NvZGVsZW4odC0+bm93LCBlbmMpOwor CSAgICB0LT5ub3cgPSByYl9lbmNfY29kZXBvaW50X2wodC0+cCwgdC0+cGVuZCwg JmxlbiwgZW5jKTsKKwkgICAgdC0+cCArPSBsZW47CiAJICAgIGlmICh0LT5wIDwg dC0+cGVuZCAtIDEgJiYgKnQtPnAgPT0gJy0nKSB7CiAJCXQtPnArKzsKIAkJaWYg KHQtPnAgPCB0LT5wZW5kKSB7Ci0JCSAgICB1bnNpZ25lZCBpbnQgYyA9IHJiX2Vu Y19jb2RlcG9pbnQodC0+cCwgdC0+cGVuZCwgZW5jKTsKLQkJICAgIHQtPnAgKz0g cmJfZW5jX2NvZGVsZW4oYywgZW5jKTsKKwkJICAgIHVuc2lnbmVkIGludCBjID0g cmJfZW5jX2NvZGVwb2ludF9sKHQtPnAsIHQtPnBlbmQsICZsZW4sIGVuYyk7CisJ CSAgICB0LT5wICs9IGxlbjsKIAkJICAgIGlmICh0LT5ub3cgPiBjKSBjb250aW51 ZTsKIAkJICAgIHQtPmdlbiA9IDE7CiAJCSAgICB0LT5tYXggPSBjOwpAQCAtNDQ5 MCw4ICs0NDgwLDggQEAKIAljaGFyICpidWYgPSBBTExPQ19OKGNoYXIsIG1heCks ICp0ID0gYnVmOwogCiAJd2hpbGUgKHMgPCBzZW5kKSB7Ci0JICAgIGMwID0gYyA9 IHJiX2VuY19jb2RlcG9pbnQocywgc2VuZCwgZW5jKTsKLQkgICAgdGxlbiA9IGNs ZW4gPSByYl9lbmNfY29kZWxlbihjLCBlbmMpOworCSAgICBjMCA9IGMgPSByYl9l bmNfY29kZXBvaW50X2wocywgc2VuZCwgJmNsZW4sIGVuYyk7CisJICAgIHRsZW4g PSBjbGVuOwogCiAJICAgIHMgKz0gY2xlbjsKIAkgICAgaWYgKGMgPCAyNTYpIHsK QEAgLTQ1NTcsOCArNDU0Nyw4IEBACiAJY2hhciAqYnVmID0gQUxMT0NfTihjaGFy LCBtYXgpLCAqdCA9IGJ1ZjsKIAogCXdoaWxlIChzIDwgc2VuZCkgewotCSAgICBj MCA9IGMgPSByYl9lbmNfY29kZXBvaW50KHMsIHNlbmQsIGVuYyk7Ci0JICAgIHRs ZW4gPSBjbGVuID0gcmJfZW5jX2NvZGVsZW4oYywgZW5jKTsKKwkgICAgYzAgPSBj ID0gcmJfZW5jX2NvZGVwb2ludF9sKHMsIHNlbmQsICZjbGVuLCBlbmMpOworCSAg ICB0bGVuID0gY2xlbjsKIAogCSAgICBpZiAoYyA8IDI1NikgewogCQljID0gdHJh bnNbY107CkBAIC00NzY0LDggKzQ3NTQsOCBAQAogICAgIGlmICghcyB8fCBSU1RS SU5HX0xFTihzdHIpID09IDApIHJldHVybiBRbmlsOwogICAgIHNlbmQgPSBSU1RS SU5HX0VORChzdHIpOwogICAgIHdoaWxlIChzIDwgc2VuZCkgewotCXVuc2lnbmVk IGludCBjID0gcmJfZW5jX2NvZGVwb2ludChzLCBzZW5kLCBlbmMpOwotCWludCBj bGVuID0gcmJfZW5jX2NvZGVsZW4oYywgZW5jKTsKKwlpbnQgY2xlbjsKKwl1bnNp Z25lZCBpbnQgYyA9IHJiX2VuY19jb2RlcG9pbnRfbChzLCBzZW5kLCAmY2xlbiwg ZW5jKTsKIAogCWlmICh0cl9maW5kKGMsIHNxdWVleiwgZGVsLCBub2RlbCkpIHsK IAkgICAgbW9kaWZ5ID0gMTsKQEAgLTQ4NjcsOCArNDg1Nyw3IEBACiAJCXMrKzsK IAkgICAgfQogCSAgICBlbHNlIHsKLQkJYyA9IHJiX2VuY19jb2RlcG9pbnQocywg c2VuZCwgZW5jKTsKLQkJY2xlbiA9IHJiX2VuY19jb2RlbGVuKGMsIGVuYyk7CisJ CWMgPSByYl9lbmNfY29kZXBvaW50X2wocywgc2VuZCwgJmNsZW4sIGVuYyk7CiAK IAkJaWYgKGMgIT0gc2F2ZSB8fCAoYXJnYyA+IDAgJiYgIXRyX2ZpbmQoYywgc3F1 ZWV6LCBkZWwsIG5vZGVsKSkpIHsKIAkJICAgIGlmICh0ICE9IHMpIHJiX2VuY19t YmNwdXQoYywgdCwgZW5jKTsKQEAgLTUwMDgsOCArNDk5Nyw3IEBACiAJICAgIHMr KzsKIAl9CiAJZWxzZSB7Ci0JICAgIGMgPSByYl9lbmNfY29kZXBvaW50KHMsIHNl bmQsIGVuYyk7Ci0JICAgIGNsZW4gPSByYl9lbmNfY29kZWxlbihjLCBlbmMpOwor CSAgICBjID0gcmJfZW5jX2NvZGVwb2ludF9sKHMsIHNlbmQsICZjbGVuLCBlbmMp OwogCSAgICBpZiAodHJfZmluZChjLCB0YWJsZSwgZGVsLCBub2RlbCkpIHsKIAkJ aSsrOwogCSAgICB9CkBAIC01MTMxLDExICs1MTE5LDEyIEBACiAJY2hhciAqYnB0 ciA9IHB0cjsKIAlpbnQgc2tpcCA9IDE7CiAJdW5zaWduZWQgaW50IGM7CisJaW50 IGNsZW47CiAKIAllbmQgPSBiZWc7CiAJd2hpbGUgKHB0ciA8IGVwdHIpIHsKLQkg ICAgYyA9IHJiX2VuY19jb2RlcG9pbnQocHRyLCBlcHRyLCBlbmMpOwotCSAgICBw dHIgKz0gcmJfZW5jX21iY2xlbihwdHIsIGVwdHIsIGVuYyk7CisJICAgIGMgPSBy Yl9lbmNfY29kZXBvaW50X2wocHRyLCBlcHRyLCAmY2xlbiwgZW5jKTsKKwkgICAg cHRyICs9IGNsZW47CiAJICAgIGlmIChza2lwKSB7CiAJCWlmIChyYl9lbmNfaXNz cGFjZShjLCBlbmMpKSB7CiAJCSAgICBiZWcgPSBwdHIgLSBicHRyOwpAQCAtNTM2 MiwxMyArNTM1MSwxMiBAQAogICAgIH0KIAogICAgIHdoaWxlIChwIDwgcGVuZCkg ewotCXVuc2lnbmVkIGludCBjID0gcmJfZW5jX2NvZGVwb2ludChwLCBwZW5kLCBl bmMpOworCXVuc2lnbmVkIGludCBjID0gcmJfZW5jX2NvZGVwb2ludF9sKHAsIHBl bmQsICZuLCBlbmMpOwogCiAgICAgICBhZ2FpbjoKLQluID0gcmJfZW5jX2NvZGVs ZW4oYywgZW5jKTsKIAlpZiAocnNsZW4gPT0gMCAmJiBjID09IG5ld2xpbmUpIHsK IAkgICAgcCArPSBuOwotCSAgICBpZiAocCA8IHBlbmQgJiYgKGMgPSByYl9lbmNf Y29kZXBvaW50KHAsIHBlbmQsIGVuYykpICE9IG5ld2xpbmUpIHsKKwkgICAgaWYg KHAgPCBwZW5kICYmIChjID0gcmJfZW5jX2NvZGVwb2ludF9sKHAsIHBlbmQsICZu LCBlbmMpKSAhPSBuZXdsaW5lKSB7CiAJCWdvdG8gYWdhaW47CiAJICAgIH0KIAkg ICAgd2hpbGUgKHAgPCBwZW5kICYmIHJiX2VuY19jb2RlcG9pbnQocCwgcGVuZCwg ZW5jKSA9PSBuZXdsaW5lKSB7CkBAIC01NzE1LDEwICs1NzAzLDExIEBACiAgICAg ZSA9IHQgPSBSU1RSSU5HX0VORChzdHIpOwogICAgIC8qIHJlbW92ZSBzcGFjZXMg YXQgaGVhZCAqLwogICAgIHdoaWxlIChzIDwgZSkgewotCXVuc2lnbmVkIGludCBj YyA9IHJiX2VuY19jb2RlcG9pbnQocywgZSwgZW5jKTsKKwlpbnQgY2xlbjsKKwl1 bnNpZ25lZCBpbnQgY2MgPSByYl9lbmNfY29kZXBvaW50X2wocywgZSwgJmNsZW4s IGVuYyk7CiAJCiAJaWYgKCFyYl9lbmNfaXNzcGFjZShjYywgZW5jKSkgYnJlYWs7 Ci0JcyArPSByYl9lbmNfY29kZWxlbihjYywgZW5jKTsKKwlzICs9IGNsZW47CiAg ICAgfQogCiAgICAgaWYgKHMgPiBSU1RSSU5HX1BUUihzdHIpKSB7CkBAIC01Nzg3 LDcgKzU3NzYsOCBAQAogCXdoaWxlIChzIDwgdCAmJiByYl9lbmNfaXNzcGFjZSgq KHQtMSksIGVuYykpIHQtLTsKICAgICB9IGVsc2UgewogICAgICAgICB3aGlsZSAo cyA8IGUpIHsKLQkgICAgdW5zaWduZWQgaW50IGNjID0gcmJfZW5jX2NvZGVwb2lu dChzLCBlLCBlbmMpOworCSAgICBpbnQgY2xlbjsKKwkgICAgdW5zaWduZWQgaW50 IGNjID0gcmJfZW5jX2NvZGVwb2ludF9sKHMsIGUsICZjbGVuLCBlbmMpOwogCiAJ ICAgIGlmICghY2MgfHwgcmJfZW5jX2lzc3BhY2UoY2MsIGVuYykpIHsKIAkgICAg ICAgIGlmICghc3BhY2Vfc2VlbikgdCA9IHM7CkBAIC01Nzk2LDcgKzU3ODYsNyBA QAogCSAgICBlbHNlIHsKIAkgICAgICAgIHNwYWNlX3NlZW4gPSBRZmFsc2U7CiAJ ICAgIH0KLQkgICAgcyArPSByYl9lbmNfY29kZWxlbihjYywgZW5jKTsKKwkgICAg cyArPSBjbGVuOwogCX0KIAlpZiAoIXNwYWNlX3NlZW4pIHQgPSBzOwogICAgIH0K ------------ar8A6atvBig2BqGDbbHp53--