------ art_42361_32297987.1179175046637 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline Here's an interim solution. I'm working on writing and reading binary huffman encoded files. There is code here which isn't used yet by the demo code. I figured that the time had come to publish my approach to building the tree, and encoding and decoding. The current code is more pedagogical than useful since the 'compressed' data is represented by a string representation of the bit string. There are three files attached. huffman.rb is a module and some core extensions. huffman_demo1.rb runs the example from the quiz, dumping the tree and various computed data. Then 'compresses' and 'decompresses' the sample string. huffman_wikipedia.rb is an earlier version which uses the algorithm in the wikipedia article. A few remarks. I started out using the wikipedia algorithm. Once I got that working, I decided that it would be better to use a priority queue instead of two separate queues. For this I used Brian Schroeder's PriorityQueue gem. To handle the problem of padding to a given word length, I add an artificial 'character' to the tree with an occurrence count of 0. This should ensure that it doesn't take a shorter encoding away from a character which actually occurs in the input data. In order to decode the compressed data, I use a regex which is a simple alternation of all of the string representations of the codes, anchored at the begining of the string. Since the huffman encoding algorithm ensures that no code is a prefix of any other code, this regex can be used to find the code at the head of the input stream. So walking through a string representation of a huffman encoded bit stream can be done by matching this pattern against the string, the match will be the code. After this match, the string can be replaced by the string remaining after the match. Extending this to binary data will involve making an input stream class which reads the binary data and converts it into reasonably sized binary string representations, and an output stream which accumulates the string representation of the codes and writes them as binary as enough data is produced. The huffman.rb file contains these classes in an embrionic form. -- Rick DeNatale My blog on Ruby http://talklikeaduck.denhaven2.com/ ------ art_42361_32297987.1179175046637 Content-Type: application/x-ruby; name=huffman_demo1.rb Content-Transfer-Encoding: base64 X-Attachment-Id: f_f1pdncyy Content-Disposition: attachment; filename="huffman_demo1.rb" cmVxdWlyZSAnaHVmZm1hbicKCnRnID0gSHVmZm1hbjo6VHJlZUdlbmVyYXRvci5uZXcKdGcuYW5h bHlzZSgiQUJSUktCQUFSQUEiKSAKY29kZWMgPSBIdWZmbWFuOjpDb2RlYy5uZXcodGcuZ2VuZXJh dGVfdHJlZSkKcHV0cyBjb2RlYy5yb290LnRvX3MKcHV0cyAiY29kZV9wYXR0ZXJuID0gI3tjb2Rl Yy5jb2RlX3BhdHRlcm4uaW5zcGVjdH0iCgplbmNvZGVkID0gY29kZWMuZW5jb2RlX3N0cmluZygi QUJSUktCQUFSQUEiKQpwdXRzICJlbmNvZGVkID0gI3tlbmNvZGVkfSIKcHV0cyAiZGVjb2RlZCA9 ICN7Y29kZWMuZGVjb2RlX3N0cmluZyhlbmNvZGVkLCAiIil9IgoKcmVxdWlyZSAneWFtbCcKCnkg PSBZQU1MLmR1bXAodGcuZ2VuZXJhdGVfdHJlZSkKY29kZWMgPSBIdWZmbWFuOjpDb2RlYy5uZXco WUFNTC5sb2FkKHkpKQpwdXRzIGNvZGVjLnJvb3QudG9fcwpwdXRzICJjb2RlX3BhdHRlcm4gPSAj e2NvZGVjLmNvZGVfcGF0dGVybi5pbnNwZWN0fSIKCmVuY29kZWQgPSBjb2RlYy5lbmNvZGVfc3Ry aW5nKCJBQlJSS0JBQVJBQSIpCnB1dHMgImVuY29kZWQgPSAje2VuY29kZWR9IgpwdXRzICJkZWNv ZGVkID0gI3tjb2RlYy5kZWNvZGVfc3RyaW5nKGVuY29kZWQsICIiKX0iCgoKCg ------ art_42361_32297987.1179175046637 Content-Type: application/x-ruby; name=huffman_wikipedia.rb Content-Transfer-Encoding: base64 X-Attachment-Id: f_f1pdo3ir Content-Disposition: attachment; filename="huffman_wikipedia.rb" bW9kdWxlIEh1ZmZtYW4KCiAgY2xhc3MgTm9kZQoKICAgIGF0dHJfcmVhZGVyIDpzeW0sIDp3dCwg OnBhcmVudAogICAgZGVmICsob3RoZXJfbm9kZSkKICAgICAgSW50ZXJuYWxOb2RlLm5ldyhzZWxm LCBvdGhlcl9ub2RlKQogICAgZW5kCgogICAgZGVmIHRvX3MKICAgICAgIk5vZGUoI0BzeW0sICNA d3QpIgogICAgZW5kCgogICAgZGVmIDw9PihvdGhlcikKICAgICAgd3QgPD0+IG90aGVyLnd0CiAg ICBlbmQKCiAgICBwcm90ZWN0ZWQKICAgIGF0dHJfd3JpdGVyIDpwYXJlbnQKCiAgZW5kCgogIGNs YXNzIEludGVybmFsTm9kZSA8IE5vZGUKICAgIGF0dHJfcmVhZGVyIDpsZWZ0LCA6cmlnaHQKICAg IGRlZiBpbml0aWFsaXplKGNoaWxkMSwgY2hpbGQyKQogICAgICBAbGVmdCwgQHJpZ2h0ID0gKihb Y2hpbGQxLCBjaGlsZDJdLnNvcnQpCiAgICAgIGNoaWxkMS5wYXJlbnQgPSBjaGlsZDIucGFyZW50 ID0gc2VsZgogICAgICBAd3QgPSBjaGlsZDEud3QgKyBjaGlsZDIud3QKICAgICAgQHN5bSA9IEBs ZWZ0LnN5bSArIEByaWdodC5zeW0KICAgIGVuZAoKPWJlZ2luCiAgICBkZWYgPD0+KG90aGVyX25v ZGUpCiAgICAgIG90aGVyX25vZGUuY21wX3dpdGhfaW50ZXJuYWwoc2VsZikKICAgIGVuZAoKICAg IGRlZiBjbXBfd2l0aF9pbnRlcm5hbChvdGhlcl9ub2RlKQogICAgICBvdGhlcl9ub2RlLnd0IDw9 PiB3dAogICAgZW5kCgogICAgZGVmIGNtcF93aXRoX2xlYWYobGVhZikKICAgICAgcmV0dXJuIDEg aWYgbGVhZi53dCA9PSB3dAogICAgICBsZWFmLnd0IDw9PiB3dAogICAgZW5kCj1lbmQKCiAgICBk ZWYgaW5zcGVjdAogICAgICAiTm9kZSgjQHN5bSwgI0B3dCkiCiAgICBlbmQKCiAgICBkZWYgdG9f cwogICAgICBpbmRlbnRlZCgwKQogICAgZW5kCgogICAgZGVmIGluZGVudGVkKGluZGVudCkKICAg ICAgIiN7KCIgICIgKiBpbmRlbnQpfSN7aW5zcGVjdH1cbiN7bGVmdC5pbmRlbnRlZChpbmRlbnQg KyAxKX1cbiN7cmlnaHQuaW5kZW50ZWQoaW5kZW50ICsgMSl9IgogICAgZW5kCgogICAgZGVmIGNv bXB1dGVfaGFzaGVzKGVuY29kZV9oYXNoLCBkZWNvZGVfaGFzaCwgcGF0aD0iIikKICAgICAgbGVm dC5jb21wdXRlX2hhc2hlcyhlbmNvZGVfaGFzaCwgZGVjb2RlX2hhc2gsIHBhdGggKyAiMCIpCiAg ICAgIHJpZ2h0LmNvbXB1dGVfaGFzaGVzKGVuY29kZV9oYXNoLCBkZWNvZGVfaGFzaCwgcGF0aCAr ICIxIikKICAgIGVuZAoKICBlbmQKCiAgY2xhc3MgTGVhZk5vZGUgPCBOb2RlCgogICAgZGVmIGlu aXRpYWxpemUoc3ltLHd0KQogICAgICBAc3ltLCBAd3QgPSBzeW0sIHd0CiAgICBlbmQKCiAgICBk ZWYgaW5kZW50ZWQoaW5kZW50KQogICAgICAiI3soIiAgIiAqIGluZGVudCl9I3tpbnNwZWN0fSIK ICAgIGVuZAoKICAgIGRlZiBpbnNwZWN0CiAgICAgIHRvX3MKICAgIGVuZAoKICAgIGRlZiBjb21w dXRlX2hhc2hlcyhlbmNvZGVfaGFzaCwgZGVjb2RlX2hhc2gsIHBhdGg9IjAiKQogICAgICBlbmNv ZGVfaGFzaFtzeW1dID0gcGF0aAogICAgICBkZWNvZGVfaGFzaFtwYXRoXSA9IHN5bQogICAgZW5k Cgo9YmVnaW4KICAgIGRlZiA8PT4ob3RoZXJfbm9kZSkKICAgICAgb3RoZXJfbm9kZS5jbXBfd2l0 aF9sZWFmKHNlbGYpCiAgICBlbmQKCiAgICBkZWYgY21wX3dpdGhfaW50ZXJuYWwob3RoZXJfbm9k ZSkKICAgICAgcmV0dXJuIDEgaWYgb3RoZXJfbm9kZS53dCA9PSB3dAogICAgICBvdGhlcl9ub2Rl Lnd0IDw9PiB3dAogICAgZW5kCgogICAgZGVmIGNtcF93aXRoX2xlYWYobGVhZikKICAgICAgd3Qg PD0+IGxlYWYud3QKICAgIGVuZAo9ZW5kCgogIGVuZAoKICBtb2R1bGUgQ29tcGFyYWJsZVF1ZXVl CgogICAgaW5jbHVkZSBDb21wYXJhYmxlCgogICAgZGVmIDw9PihvdGhlcikKICAgICAgZW1wdHk/ ID8gMSA6IG90aGVyLnd0X2NtcChmaXJzdC53dCkKICAgIGVuZAoKICAgIGRlZiB3dF9jbXAob3Ro ZXJfd3QpCiAgICAgIGVtcHR5PyA/IC0xIDogb3RoZXJfd3QgPD0+IGZpcnN0Lnd0CiAgICBlbmQK ICBlbmQKCiAgY2xhc3MgVHJlZUdlbmVyYXRvcgoKICAgIHByaXZhdGUKICAgIGF0dHJfYWNjZXNz b3IgOmhpc3RvZ3JhbQoKICAgIGRlZiBoaXN0b2dyYW0KICAgICAgQGhpc3RvZ3JhbSB8fD0gSGFz aC5uZXcge3xoLGt8IGhba10gPSAwfQogICAgZW5kCgogICAgZGVmIHNvcnRlZF9wYWlycwogICAg ICBoaXN0b2dyYW0udG9fYS5zb3J0X2J5IHt8YXwgYS5sYXN0fQogICAgZW5kCgogICAgcHVibGlj CiAgICBkZWYgYW5hbHlzZShzdHIpCiAgICAgIEByb290ID0gQHNvcnRlZCA9IEBlbmNvZGVfaGFz aCA9IEBkZWNvZGVfaGFzaCA9IEBjb2RlX3BhdHRlcm4gPSBuaWwKICAgICAgc3RyLnNjYW4oLy4v KS5lYWNoIHsgfCBjaGFyIHxoaXN0b2dyYW1bY2hhcl0gKz0gMX0KICAgIGVuZAoKICAgIGRlZiBz b3J0ZWRfbm9kZXMKICAgICAgQHNvcnRlZCB8fD0gc29ydGVkX3BhaXJzCiAgICAgIEBzb3J0ZWQu aW5qZWN0KFtdKSB7fG5vZGVzLCBwYWlyfCBub2RlcyA8PCBMZWFmTm9kZS5uZXcoKnBhaXIpfQog ICAgZW5kCgogICAgZGVmIGxvd2VzdChxMSwgcTIpCiAgICAgIHExIDwgcTIgPyBxMS5zaGlmdCA6 IHEyLnNoaWZ0CiAgICBlbmQKCiAgICBkZWYgZ2VuZXJhdGVfdHJlZQogICAgICBxMSxxMiA9IHNv cnRlZF9ub2RlcywgW10KICAgICAgcTEuZXh0ZW5kKENvbXBhcmFibGVRdWV1ZSkKICAgICAgcTIu ZXh0ZW5kKENvbXBhcmFibGVRdWV1ZSkKICAgICAgd2hpbGUgKHExLnNpemUgKyBxMi5zaXplKSA+ IDEKCXEyIDw8IEludGVybmFsTm9kZS5uZXcobG93ZXN0KHExLHEyKSwgbG93ZXN0KHExLHEyKSkK ICAgICAgZW5kCiAgICAgIChxMStxMikuZmlyc3QKICAgIGVuZAoKICAgIGRlZiByb290CiAgICAg IEByb290IHx8PSBnZW5lcmF0ZV90cmVlCiAgICBlbmQKCiAgICBkZWYgY29tcHV0ZV9oYXNoZXMK ICAgICAgQHJvb3QgfHw9IGdlbmVyYXRlX3RyZWUKICAgICAgQGVuY29kZV9oYXNoID0ge30KICAg ICAgQGRlY29kZV9oYXNoID0ge30KICAgICAgQHJvb3QuY29tcHV0ZV9oYXNoZXMoQGVuY29kZV9o YXNoLCBAZGVjb2RlX2hhc2gpCiAgICBlbmQKCiAgICBkZWYgZW5jb2RlX2hhc2gKICAgICAgY29t cHV0ZV9oYXNoZXMgdW5sZXNzIEBlbmNvZGVfaGFzaAogICAgICBAZW5jb2RlX2hhc2gKICAgIGVu ZAoKICAgIGRlZiBkZWNvZGVfaGFzaAogICAgICBjb21wdXRlX2hhc2hlcyB1bmxlc3MgQGRlY29k ZV9oYXNoCiAgICAgIEBkZWNvZGVfaGFzaAogICAgZW5kCgogICAgZGVmIGNvZGVfcGF0dGVybgog ICAgICBAY29kZV9wYXR0ZXJuIHx8PSAlcnteKCN7ZGVjb2RlX2hhc2gua2V5cy5qb2luKCd8Jyl9 KX0KICAgIGVuZAoKICAgIGRlZiBlbmNvZGUoc3RyKQogICAgICBzdHIuc3BsaXQoLy8pLmluamVj dCgiIikge3xyZXN1bHQsIGNofCByZXN1bHQgPDwgZW5jb2RlX2hhc2hbY2hdfQogICAgZW5kCgog ICAgZGVmIGRlY29kZShzdHIpCiAgICAgIHRtcCA9IHN0ci5kdXAKICAgICAgcmVzdWx0ID0gIiIK ICAgICAgcGF0ID0gY29kZV9wYXR0ZXJuCiAgICAgIHB1dHMgInBhdCBpcyAje3BhdH0iCiAgICAg IHVudGlsIHRtcC5lbXB0eT8KCW1hdGNoID0gdG1wLm1hdGNoKHBhdCkKCXJlc3VsdCA8PCBkZWNv ZGVfaGFzaFttYXRjaFsxXV0KCXRtcCA9IG1hdGNoLnBvc3RfbWF0Y2gKICAgICAgZW5kCiAgICAg IHJlc3VsdAogICAgZW5kCiAgZW5kCmVuZAoKdGcgPSBIdWZmbWFuOjpUcmVlR2VuZXJhdG9yLm5l dwp0Zy5hbmFseXNlKCJBQlJSS0JBQVJBQSIpIApyb290ID0gdGcuZ2VuZXJhdGVfdHJlZQpwdXRz IHJvb3QudG9fcwpwdXRzICJlbmNvZGVfaGFzaCA9ICN7dGcuZW5jb2RlX2hhc2guaW5zcGVjdH0i CnB1dHMgImRlY29kZV9oYXNoID0gI3t0Zy5kZWNvZGVfaGFzaC5pbnNwZWN0fSIKcHV0cyAiY29k ZV9wYXR0ZXJuID0gI3t0Zy5jb2RlX3BhdHRlcm4uaW5zcGVjdH0iCgplbmNvZGVkID0gdGcuZW5j b2RlKCJBQlJSS0JBQVJBQSIpCnB1dHMgImVuY29kZWQgPSAje2VuY29kZWR9IgpwdXRzICJkZWNv ZGVkID0gI3t0Zy5kZWNvZGUoZW5jb2RlZCl9Igo------ art_42361_32297987.1179175046637 Content-Type: application/x-ruby; name=huffman.rb Content-Transfer-Encoding: base64 X-Attachment-Id: f_f1pec081 Content-Disposition: attachment; filename="huffman.rb" IyEvdXNyL21hdGgvYmluL3J1YnkKCgptb2R1bGUgSHVmZm1hbgoKICByZXF1aXJlICdydWJ5Z2Vt cycKICByZXF1aXJlICdwcmlvcml0eV9xdWV1ZScKICByZXF1aXJlICdzdHJpbmdpbycKCiAgRW5k U3ltYm9sID0gIkVORCIKCiAgY2xhc3MgTm9kZQoKICAgIGF0dHJfcmVhZGVyIDpzeW0sIDp3dCwg OnBhcmVudAogICAgZGVmICsob3RoZXJfbm9kZSkKICAgICAgSW50ZXJuYWxOb2RlLm5ldyhzZWxm LCBvdGhlcl9ub2RlKQogICAgZW5kCgogICAgZGVmIHRvX3MKICAgICAgIk5vZGUoI0BzeW0sICNA d3QpIgogICAgZW5kCgogICAgZGVmIDw9PihvdGhlcikKICAgICAgd3QgPD0+IG90aGVyLnd0CiAg ICBlbmQKCiAgICBwcm90ZWN0ZWQKICAgIGF0dHJfd3JpdGVyIDpwYXJlbnQKCiAgZW5kCgogIGNs YXNzIEludGVybmFsTm9kZSA8IE5vZGUKICAgIGF0dHJfcmVhZGVyIDpsZWZ0LCA6cmlnaHQKICAg IGRlZiBpbml0aWFsaXplKGNoaWxkMSwgY2hpbGQyKQogICAgICBAbGVmdCwgQHJpZ2h0ID0gKihb Y2hpbGQxLCBjaGlsZDJdLnNvcnQpCiAgICAgIGNoaWxkMS5wYXJlbnQgPSBjaGlsZDIucGFyZW50 ID0gc2VsZgogICAgICBAd3QgPSBjaGlsZDEud3QgKyBjaGlsZDIud3QKICAgICAgQHN5bSA9IEBs ZWZ0LnN5bSArIEByaWdodC5zeW0KICAgIGVuZAoKICAgIGRlZiBpbnNwZWN0CiAgICAgICJOb2Rl KCNAc3ltLCAjQHd0KSIKICAgIGVuZAoKICAgIGRlZiB0b19zCiAgICAgIGluZGVudGVkKDApCiAg ICBlbmQKCiAgICBkZWYgaW5kZW50ZWQoaW5kZW50KQogICAgICAiI3soIiAgIiAqIGluZGVudCl9 I3tpbnNwZWN0fVxuI3tsZWZ0LmluZGVudGVkKGluZGVudCArIDEpfVxuI3tyaWdodC5pbmRlbnRl ZChpbmRlbnQgKyAxKX0iCiAgICBlbmQKCiAgICBkZWYgY29tcHV0ZV9oYXNoZXMoZW5jb2RlX2hh c2gsIGRlY29kZV9oYXNoLCBwYXRoPSIiKQogICAgICBsZWZ0LmNvbXB1dGVfaGFzaGVzKGVuY29k ZV9oYXNoLCBkZWNvZGVfaGFzaCwgcGF0aCArICIwIikKICAgICAgcmlnaHQuY29tcHV0ZV9oYXNo ZXMoZW5jb2RlX2hhc2gsIGRlY29kZV9oYXNoLCBwYXRoICsgIjEiKQogICAgZW5kCgogICAgZGVm IGRlcHRoCiAgICAgIDEgKyBbbGVmdC5kZXB0aCwgcmlnaHQuZGVwdGhdLm1heAogICAgZW5kCgog IGVuZAoKICBjbGFzcyBMZWFmTm9kZSA8IE5vZGUKCiAgICBkZWYgaW5pdGlhbGl6ZShzeW0sd3Qp CiAgICAgIEBzeW0sIEB3dCA9IHN5bSwgd3QKICAgIGVuZAoKICAgIGRlZiBpbmRlbnRlZChpbmRl bnQpCiAgICAgICIjeygiICAiICogaW5kZW50KX0je2luc3BlY3R9IgogICAgZW5kCgogICAgZGVm IGluc3BlY3QKICAgICAgdG9fcwogICAgZW5kCgogICAgZGVmIGNvbXB1dGVfaGFzaGVzKGVuY29k ZV9oYXNoLCBkZWNvZGVfaGFzaCwgcGF0aD0iMCIpCiAgICAgIGVuY29kZV9oYXNoW3N5bV0gPSBw YXRoCiAgICAgIGRlY29kZV9oYXNoW3BhdGhdID0gc3ltCiAgICBlbmQKCiAgICBkZWYgZGVwdGgK ICAgICAgMQogICAgZW5kCgogIGVuZAoKICBjbGFzcyBOb2RlUXVldWUKICAgIGRlZiBpbml0aWFs aXplCiAgICAgIEBxID0gQ1ByaW9yaXR5UXVldWUubmV3CiAgICBlbmQKCiAgICBkZWYgPDwobm9k ZSkKICAgICAgcVtub2RlXSA9IG5vZGUud3QKICAgIGVuZAoKICAgIGRlZiBuZXh0CiAgICAgIHEu ZGVsZXRlX21pbl9yZXR1cm5fa2V5CiAgICBlbmQKCiAgICBkZWYgc2l6ZQogICAgICBxLmxlbmd0 aAogICAgZW5kCgogICAgZGVmIGZpcnN0CiAgICAgIHEubWluX2tleQogICAgZW5kCgogICAgcHJp dmF0ZQogICAgYXR0cl9yZWFkZXIgOnEKCiAgZW5kCgogIGNsYXNzIElucHV0U3RyZWFtCiAgICBk ZWYgaW5pdGlhbGl6ZShwYXR0ZXJuLCBsZW5ndGgsIHNlbnRpbmVsKQogICAgICBAcGF0LCBAbGVu LCBAc2VudGluZWwgPSBwYXR0ZXJuLCBsZW5ndGgsIHNlbnRpbmVsCiAgICBlbmQKCiAgICBkZWYg ZW9mPwogICAgICBjaHVuay5tYXRjaChwYXQpWzFdID09IHNlbnRpbmVsCiAgICBlbmQKCiAgICBk ZWYgbmV4dAogICAgICBtYXRjaCA9IGNodW5rLm1hdGNoKHBhdCkKICAgICAgc2VsZi5jaHVuayA9 IG1hdGNoLnBvc3RfbWF0Y2gKICAgICAgbWF0Y2hbMV0KICAgIGVuZAoKICAgIHByb3RlY3RlZAog ICAgYXR0cl9hY2Nlc3NvciA6Y2h1bmssIDpwYXQsIDpzZW50aW5lbAogIGVuZAogIGNsYXNzIEVu Y29kZXJPdXRwdXRTdHJlYW0KCiAgICBkZWYgaW5pdGlhbGl6ZShzZW50aW5lbCkKICAgICAgQHNl bnRpbmVsID0gc2VudGluZWwKICAgICAgQGJ1ZmZlciA9ICIiCiAgICBlbmQKCiAgICBwcm90ZWN0 ZWQgCiAgICBhdHRyX3JlYWRlciA6c2VudGluZWwKICAgIGF0dHJfYWNjZXNzb3IgOmJ1ZmZlcgog IGVuZAogIGNsYXNzIEZpbGVPdXRwdXRTdHJlYW0gPCBFbmNvZGVyT3V0cHV0U3RyZWFtCgogICAg ZGVmIGluaXRpYWxpemUoZmlsZSwgc2VudGluZWwpCiAgICAgIHN1cGVyKHNlbnRpbmVsKQogICAg ICBzZWxmLmZpbGUgPSBmaWxlCiAgICBlbmQKCiAgICBkZWYgc2VsZi5vcGVuKGZpbGVfbmFtZSwg c2VudGluZWwsICZibG9jaykKICAgICAgRmlsZS5vcGVuKGZpbGVfbmFtZSwgInciKSBkbyB8Zmls ZXwKCWZvcyA9IG5ldyhmaWxlLCBzZW50aW5lbCkKCWJlZ2luCgkgIGJsb2NrLmNhbGwoZm9zKQoJ ZW5zdXJlCgkgIGZvcy5mbHVzaAoJZW5kCiAgICAgIGVuZAogICAgZW5kCgogICAgZGVmIDw8KHN0 cikKICAgICAgYnVmZmVyIDw8IHN0cgogICAgICB3cml0ZV9idWZmZXIKICAgIGVuZAoKICAgIGRl ZiBmbHVzaAogICAgICB3cml0ZV9idWZmZXIKICAgICAgdW5sZXNzIEBidWZmZXIuZW1wdHk/Cgli dWZmZXIgPDwgc2VudGluZWwgPDwgIjAiKjgKCXdyaXRlX2J1ZmZlcgogICAgICBlbmQKICAgIGVu ZAoKICAgIHByaXZhdGUKICAgIGRlZiB3cml0ZV9idWZmZXIKICAgICAgd2hpbGUgc2VsZi5idWZm ZXIubGVuZ3RoID49IDgKCXNlbGYuZmlsZSA8PCBzZWxmLmJ1ZmZlclswLi43XS50b19pCglzZWxm LmJ1ZmZlciA9IHNlbGYuYnVmZmVyWzguLi0xXQogICAgICBlbmQKICAgIGVuZAogIGVuZAoKICBj bGFzcyBTdHJpbmdJbnB1dCA8IElucHV0U3RyZWFtCiAgICBkZWYgaW5pdGlhbGl6ZShzdHJpbmcs IHBhdHRlcm4sIGxlbmd0aCwgZW5kX3NlbnRpbmVsKQogICAgICBAY2h1bmsgPSBzdHJpbmcKICAg ICAgc3VwZXIocGF0dGVybiwgbGVuZ3RoLCBlbmRfc2VudGluZWwpCiAgICBlbmQKICBlbmQKCgog IGNsYXNzIFRyZWVHZW5lcmF0b3IKCiAgICBwcml2YXRlCiAgICBhdHRyX2FjY2Vzc29yIDpoaXN0 b2dyYW0KCiAgICBkZWYgaGlzdG9ncmFtCiAgICAgIEBoaXN0b2dyYW0gfHw9IEhhc2gubmV3IHt8 aCxrfCBoW2tdID0gMH0KICAgIGVuZAoKICAgIGRlZiBpbml0aWFsX3F1ZXVlCiAgICAgIHEgPSBO b2RlUXVldWUubmV3CiAgICAgIHEgPDwgTGVhZk5vZGUubmV3KEVuZFN5bWJvbCwwKSAjIFNwZWNp YWwgZW5kIHN5bWJvbAogICAgICBoaXN0b2dyYW0udG9fYS5lYWNoIGRvIHxzeW1fd3R8CglxIDw8 IExlYWZOb2RlLm5ldygqc3ltX3d0KQogICAgICBlbmQKICAgICAgcQogICAgZW5kCgogICAgcHVi bGljCiAgICBkZWYgYW5hbHlzZShzdHIpCiAgICAgIEByb290ID0gQGVuY29kZV9oYXNoID0gQGRl Y29kZV9oYXNoID0gQGNvZGVfcGF0dGVybiA9IG5pbAogICAgICBzdHIuc2NhbigvLi8pLmVhY2gg eyB8IGNoYXIgfGhpc3RvZ3JhbVtjaGFyXSArPSAxfQogICAgZW5kCgoKICAgIGRlZiBnZW5lcmF0 ZV90cmVlCiAgICAgIHF1ZXVlID0gaW5pdGlhbF9xdWV1ZQogICAgICB3aGlsZSAocXVldWUuc2l6 ZSkgPiAxCglxdWV1ZSA8PCBJbnRlcm5hbE5vZGUubmV3KHF1ZXVlLm5leHQsIHF1ZXVlLm5leHQp CiAgICAgIGVuZAogICAgICBxdWV1ZS5maXJzdAogICAgZW5kCgogIGVuZAoKICBjbGFzcyBDb2Rl YwoKICAgIGF0dHJfcmVhZGVyIDpyb290CgoKICAgIGRlZiBpbml0aWFsaXplKHRyZWUpCiAgICAg IEByb290ID0gdHJlZQogICAgZW5kCgogICAgZGVmIGNvbXB1dGVfaGFzaGVzCiAgICAgIEBlbmNv ZGVfaGFzaCA9IHt9CiAgICAgIEBkZWNvZGVfaGFzaCA9IHt9CiAgICAgIHJvb3QuY29tcHV0ZV9o YXNoZXMoQGVuY29kZV9oYXNoLCBAZGVjb2RlX2hhc2gpCiAgICBlbmQKCiAgICBkZWYgZW5jb2Rl X2hhc2gKICAgICAgY29tcHV0ZV9oYXNoZXMgdW5sZXNzIEBlbmNvZGVfaGFzaAogICAgICBAZW5j b2RlX2hhc2gKICAgIGVuZAoKICAgIGRlZiBkZWNvZGVfaGFzaAogICAgICBjb21wdXRlX2hhc2hl cyB1bmxlc3MgQGRlY29kZV9oYXNoCiAgICAgIEBkZWNvZGVfaGFzaAogICAgZW5kCgogICAgZGVm IGNvZGVfcGF0dGVybgogICAgICBAY29kZV9wYXR0ZXJuIHx8PSAlcnteKCN7ZGVjb2RlX2hhc2gu a2V5cy5qb2luKCd8Jyl9KX0KICAgIGVuZAoKICAgIGRlZiBlbmNvZGVfc3RyaW5nKHN0cikKICAg ICAgKHN0ci5zcGxpdCgvLykgPDwgRW5kU3ltYm9sKS5pbmplY3QoIiIpIHt8cmVzdWx0LCBjaHwg cmVzdWx0IDw8IGVuY29kZV9oYXNoW2NoXX0KICAgIGVuZAoKICAgIGRlZiBlbmNvZGUoaW5wdXQs IG91dHB1dCkKICAgICAgaW5wdXQuZWFjaF9ieXRlIHt8Ynl0ZXwgb3V0cHV0IDw8IGVuY29kZV9o YXNoW2J5dGUuY2hyXX0KICAgIGVuZAoKICAgIGRlZiBkZWNvZGUoaW5wdXQsIG91dHB1dCkKICAg ICAgb3V0cHV0IDw8IGRlY29kZV9oYXNoW2lucHV0Lm5leHRdIHVudGlsIGlucHV0LmVvZj8KICAg IGVuZAoKICAgIGRlZiBkZWNvZGVfc3RyaW5nKHNvdXJjZSwgc2luaz0iIikKICAgICAgaW5wdXQg PSBzb3VyY2UuaHVmZm1hbl9kZWNvZGVyX2lucHV0X3N0cmVhbShjb2RlX3BhdHRlcm4sIHJvb3Qu ZGVwdGgsIGVuY29kZV9oYXNoW0VuZFN5bWJvbF0pCiAgICAgIG91dHB1dCA9IHNpbmsuaHVmZm1h bl9kZWNvZGVyX291dHB1dF9zdHJlYW0KICAgICAgZGVjb2RlKGlucHV0LCBvdXRwdXQpCiAgICAg IG91dHB1dC5zdHJpbmcKICAgIGVuZAogIGVuZAplbmQKCmNsYXNzIFN0cmluZwogIGRlZiBodWZm bWFuX2RlY29kZXJfaW5wdXRfc3RyZWFtKHBhdCwgbGVuZ3RoLCBlbmRfc2VudGluZWwpCiAgICBI dWZmbWFuOjpTdHJpbmdJbnB1dC5uZXcoc2VsZiwgcGF0LCBsZW5ndGgsIGVuZF9zZW50aW5lbCkK ICBlbmQKCiAgZGVmIGh1ZmZtYW5fZGVjb2Rlcl9vdXRwdXRfc3RyZWFtCiAgICBTdHJpbmdJTy5u ZXcoc2VsZikKICBlbmQKCmVuZAoK ------ art_42361_32297987.1179175046637--