Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1vFuZG-003KbE-Qx for pgsql-hackers@arkaria.postgresql.org; Mon, 03 Nov 2025 13:25:54 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.94.2) (envelope-from ) id 1vFuYH-003aNn-FY for pgsql-hackers@arkaria.postgresql.org; Mon, 03 Nov 2025 13:24:52 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1vFuYG-003aKb-QY for pgsql-hackers@lists.postgresql.org; Mon, 03 Nov 2025 13:24:52 +0000 Received: from mail-qt1-x842.google.com ([2607:f8b0:4864:20::842]) by makus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.96) (envelope-from ) id 1vFuYC-005Dg2-2W for pgsql-hackers@lists.postgresql.org; Mon, 03 Nov 2025 13:24:50 +0000 Received: by mail-qt1-x842.google.com with SMTP id d75a77b69052e-4eba313770dso56676171cf.3 for ; Mon, 03 Nov 2025 05:24:48 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1762176288; x=1762781088; darn=lists.postgresql.org; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=G32ssCINRDQ56vJIBySaPa8AYvie7/SQOM8j4hz1rVc=; b=Q+1AOKpnAFwSgsOts/D0+nqUs61DvO11b0O3evnnVWeCh95Db1bU7XvrP4BiwcSQWP oW+FqvlQMomdUH28B0gb7DTT/qVMh2apnJ2TBouaF2gSX1PJr39PewBWz5oN29jCc6EZ hNaYP/K9mhGgdGGJqO/gybC6WjKJbRgNMniPDm4mFxeg/Wm3dCKBii5vvO0EushrZals gCa6lFe3Fivnpyd3INrxNejrsHB/DGKBzlKhmp4Tu5Ji17R207dR0eveLar0FM589/s1 Eu4dyFXvk8TnlU43tqFn+Pe6ZKX/NF2PKBimC9Lnvl3AIvfT2v3PKodjK4bFYutfww8M BxNw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762176288; x=1762781088; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=G32ssCINRDQ56vJIBySaPa8AYvie7/SQOM8j4hz1rVc=; b=GSPXYTJHZ4BNi4tLTtU2MS13T8/Kmqpp6uItMtSbPILT7UNyIP7lkH8gR3+CBQq0Ft rkj5F8UjzVI59jAhyLDvWh9/phKziyUutY6iffBFs3Q9z8+4QumwlMRuu13cDcEKsaXt RkIeR9wDo+df69Op2sc8lowdsvauKli0L2gcZTjxGNphYJHmuGPX0OVyj0VL1giyKH/n FDbi3vQJRHFl/CixIiEAvL+VNMtlMmaTCO2n/4Kr08tWYvkme1SO9kVeoacfOMfI9mNu /inY1MQnRH48j3tqvFpL79FwgyG+YQfjLaKJ0/daSIi0VFQGZ+HXhntILU5gOikJ/id9 +qVQ== X-Gm-Message-State: AOJu0YygsBzI7hq6ZWME3nLthCC6FM85NEYQnwy8pfjif/zKtlD5jq/n 0jiwSjUvRO5eA7ffDi8F4+9b6lZhCfQsbUl10WLZYOxkeJ0XNq6MU5kcKS+5cHp0lz1Xp/uNN0/ BPuTESmSmivKL+m7T1cCE4U+6hMg1d/pnQmXoOzo7kg== X-Gm-Gg: ASbGnctGKlVilHOIILl2zKNLyMqQX8cZAAQZ6y8k33dai55LhNWgPA0rur9KHj5hLgl AuzgtNPCC4MvoUX8LEhHljc6nVYly+a1tBaAR6JvY3dlGRuoJofwmUQrG3yGoy+6mddfkr3Wnaw 8R6+LyOL9tODaetXdHaQohBDG81F17fPbMWBTUC8vbPy43LdSJsQtubaAg+/fRE2t0eMhxPVLSk dFP2mBYrNYpg9DVZp17TfgV8o+hY287IPHldMC6PqEccN9LOOM8v3whQN6n3oZm+lJLcjCZRWlE kVNZixaw9UUWYf/SSeJLVIzQyBUGsSzPWuxY0aLbLE/86pJ0ee9yriMBau6qBqFw3MGhY+7kD5U 5cf/j3Q8XCqHBjf1UzPf/KfUesA== X-Google-Smtp-Source: AGHT+IFeK4IZ3yNlrW8XH5E90LclZkxDcDdIcO1lO8bWNirgA9vURCvjkMT/jNvYmWpH1cl9vsbtHihcbFnUy0teEXk= X-Received: by 2002:a05:622a:514d:b0:4eb:77f5:394c with SMTP id d75a77b69052e-4ed310a6bc3mr167650841cf.48.1762176287598; Mon, 03 Nov 2025 05:24:47 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: John Naylor Date: Mon, 3 Nov 2025 20:24:35 +0700 X-Gm-Features: AWmQ_bl9WNqH3dg8sMApFyhC20_ZyZ46SslTtuHcJS1cIkP9S2ZvlafZJGSqtc0 Message-ID: Subject: Re: tuple radix sort To: PostgreSQL Hackers Cc: Peter Geoghegan Content-Type: multipart/mixed; boundary="000000000000a79dc30642b0a3f5" List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk --000000000000a79dc30642b0a3f5 Content-Type: text/plain; charset="UTF-8" I wrote: > The v1 patch > has some optimizations, but in other ways things are simple and/or > wasteful. Exactly how things fit together will be informed by what, if > anything, has to be done to avoid regressions. In v1, radix sort diverts to qsort_tuple for small partitions (similar to how quicksort diverts to insertion sort), but qsort_tuple is inefficient because the comparator is called via a function pointer. I also thought having two different radix sorts was too complex, so I wondered if it'd be better to get rid of the smaller radix sort (whose control flow I find harder to understand, even ignoring the unsightly goto) and have the larger sort divert to a new quicksort specialization that compares on the conditioned datum. That allows skipping branches for NULL comparisons and order reversal. I've done this in v2. It makes sense to replace the three current integer-comparison quicksorts with one. v1 was careful to restore isnull1 to false when diverting to quicksort for the tiebreak. v2 doesn't bother, since the only tiebreak in core that looks at isnull1 is comparetup_datum_tiebreak, which is not reachable by radix sort, requiring a pass-by-value datum that compares like an integer. This is a bit of a risk, since it's possible a third party fork could be doing something weird. Seems unlikely, but something to keep in mind. I used a standalone program (attached) to microbenchmark this new fallback qsort vs. a pass of radix sort on one byte to get a decent threshold value. This is not quite fair, since the quicksort will then be finished, but the radix sort could still need to recurse to the next byte(s), so these number could underestimate the threshold. This is just to get an idea. The numbers are in RDTSC ticks per element sorted. cardinality: 256 number of elements: 100 qsort: 35.4 radix: 49.2 number of elements: 200 qsort: 34.9 radix: 38.1 number of elements: 400 qsort: 42.4 radix: 34.4 number of elements: 800 qsort: 95.0 radix: 29.2 number of elements: 1600 qsort: 115.0 radix: 22.4 number of elements: 3200 qsort: 125.5 radix: 19.4 number of elements: 6400 qsort: 128.1 radix: 17.6 With the highest cardinality possible on a single byte, radix sort is actually not bad at low inputs. Notice that the time per element is consistently going down with larger inputs. Smaller inputs have large constant overheads, made worse by my unrolling the counting step. cardinality: 2 number of elements: 100 qsort: 09.2 radix: 28.0 number of elements: 200 qsort: 09.1 radix: 19.5 number of elements: 400 qsort: 10.4 radix: 15.7 number of elements: 800 qsort: 10.1 radix: 14.5 number of elements: 1600 qsort: 10.4 radix: 13.7 number of elements: 3200 qsort: 15.8 radix: 13.6 number of elements: 6400 qsort: 22.2 radix: 13.8 This is an extreme best case for B&M quicksort, which is basically O(n) -- the point at which the per-element time goes up seems purely due to exceeding L1 cache. Radix sort takes a big input to catch up, but it doesn't seem awful, either. cardinality: 16 number of elements: 100 qsort: 19.5 radix: 34.5 number of elements: 200 qsort: 18.7 radix: 22.6 number of elements: 400 qsort: 18.5 radix: 17.2 number of elements: 800 qsort: 25.0 radix: 14.8 number of elements: 1600 qsort: 43.8 radix: 13.8 number of elements: 3200 qsort: 51.2 radix: 13.2 number of elements: 6400 qsort: 59.0 radix: 12.8 This is still low cardinality, but behaves more like the high cardinality case. I've set the threshold to 400 for now, but I'm not claiming that's the end story. In addition to the underestimation mentioned above, unrolling the counting step is a factor. Unrolling makes smaller inputs worse (which we can reach by recursing from larger inputs), but unrolling seems important for large inputs with low cardinality (a few percent, but I haven't shared numbers yet). We've found that a large input with only 4-5 distinct values just barely wins with radix sort. I'll be curious to see if unrolling is actually needed to prevent regressions there. Other things to consider: - I don't quite like how the NULL partitioning step looks, and it could be costly when the distribution of NULL is not predictable, so I'm thinking of turning part of that into a branch-free cyclic permutation, similar to https://www.postgresql.org/message-id/CANWCAZbAmaZ7P%2BARjS97sJLXsBB5CPZyzFgqNDiqe-L%2BBqXzug%40mail.gmail.com - The quicksort on the NULL partition still compares isnull1 -- the branches are predictable but perhaps it's worth it to add a specialization that skips that. -- John Naylor Amazon Web Services --000000000000a79dc30642b0a3f5 Content-Type: text/x-patch; charset="US-ASCII"; name="v2-0001-Use-radix-sort-when-datum1-is-an-integer-type.patch" Content-Disposition: attachment; filename="v2-0001-Use-radix-sort-when-datum1-is-an-integer-type.patch" Content-Transfer-Encoding: base64 Content-ID: X-Attachment-Id: f_mhj5w4g30 RnJvbSA4ZDY0M2E2MTM4NmQxMGE3OTk2ZjljZGRiMDk2NWYxOGVjMGZlODMyIE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBKb2huIE5heWxvciA8am9obi5uYXlsb3JAcG9zdGdyZXNxbC5v cmc+CkRhdGU6IEZyaSwgMTcgT2N0IDIwMjUgMDk6NTc6NDMgKzA3MDAKU3ViamVjdDogW1BBVENI IHYyXSBVc2UgcmFkaXggc29ydCB3aGVuIGRhdHVtMSBpcyBhbiBpbnRlZ2VyIHR5cGUKClhYWCBy ZWdyZXNzaW9uIHRlc3RzIGRvbid0IHBhc3MgZm9yIHVuZGVyc3BlY2lmaWVkIHF1ZXJpZXM7IHRo aXMKaXMgZXhwZWN0ZWQKLS0tCiBzcmMvYmFja2VuZC91dGlscy9taXNjL2d1Y19wYXJhbWV0ZXJz LmRhdCB8ICAgNyArCiBzcmMvYmFja2VuZC91dGlscy9zb3J0L3R1cGxlc29ydC5jICAgICAgICB8 IDUwNiArKysrKysrKysrKysrKysrKysrKystCiBzcmMvaW5jbHVkZS91dGlscy9ndWMuaCAgICAg ICAgICAgICAgICAgICB8ICAgMSArCiBzcmMvaW5jbHVkZS91dGlscy90dXBsZXNvcnQuaCAgICAg ICAgICAgICB8ICAxMiArLQogNCBmaWxlcyBjaGFuZ2VkLCA1MDYgaW5zZXJ0aW9ucygrKSwgMjAg ZGVsZXRpb25zKC0pCgpkaWZmIC0tZ2l0IGEvc3JjL2JhY2tlbmQvdXRpbHMvbWlzYy9ndWNfcGFy YW1ldGVycy5kYXQgYi9zcmMvYmFja2VuZC91dGlscy9taXNjL2d1Y19wYXJhbWV0ZXJzLmRhdApp bmRleCBkNmZjODMzMzg1MC4uZjhmYzZjODgwODIgMTAwNjQ0Ci0tLSBhL3NyYy9iYWNrZW5kL3V0 aWxzL21pc2MvZ3VjX3BhcmFtZXRlcnMuZGF0CisrKyBiL3NyYy9iYWNrZW5kL3V0aWxzL21pc2Mv Z3VjX3BhcmFtZXRlcnMuZGF0CkBAIC02ODEsNiArNjgxLDEzIEBACiAgIGJvb3RfdmFsID0+ICdm YWxzZScsCiB9LAogCit7IG5hbWUgPT4gJ3dpcF9yYWRpeF9zb3J0JywgdHlwZSA9PiAnYm9vbCcs IGNvbnRleHQgPT4gJ1BHQ19VU0VSU0VUJywgZ3JvdXAgPT4gJ0RFVkVMT1BFUl9PUFRJT05TJywK KyAgc2hvcnRfZGVzYyA9PiAnVGVzdCByYWRpeCBzb3J0IGZvciBkZWJ1Z2dpbmcuJywKKyAgZmxh Z3MgPT4gJ0dVQ19OT1RfSU5fU0FNUExFJywKKyAgdmFyaWFibGUgPT4gJ3dpcF9yYWRpeF9zb3J0 JywKKyAgYm9vdF92YWwgPT4gJ3RydWUnLAorfSwKKwogIyB0aGlzIGlzIHVuZG9jdW1lbnRlZCBi ZWNhdXNlIG5vdCBleHBvc2VkIGluIGEgc3RhbmRhcmQgYnVpbGQKIHsgbmFtZSA9PiAndHJhY2Vf c3luY3NjYW4nLCB0eXBlID0+ICdib29sJywgY29udGV4dCA9PiAnUEdDX1VTRVJTRVQnLCBncm91 cCA9PiAnREVWRUxPUEVSX09QVElPTlMnLAogICBzaG9ydF9kZXNjID0+ICdHZW5lcmF0ZSBkZWJ1 Z2dpbmcgb3V0cHV0IGZvciBzeW5jaHJvbml6ZWQgc2Nhbm5pbmcuJywKZGlmZiAtLWdpdCBhL3Ny Yy9iYWNrZW5kL3V0aWxzL3NvcnQvdHVwbGVzb3J0LmMgYi9zcmMvYmFja2VuZC91dGlscy9zb3J0 L3R1cGxlc29ydC5jCmluZGV4IDVkNDQxMWRjMzNmLi5hYzkxMDg5YWM0MiAxMDA2NDQKLS0tIGEv c3JjL2JhY2tlbmQvdXRpbHMvc29ydC90dXBsZXNvcnQuYworKysgYi9zcmMvYmFja2VuZC91dGls cy9zb3J0L3R1cGxlc29ydC5jCkBAIC0xMDQsNiArMTA0LDcgQEAKICNpbmNsdWRlICJjb21tYW5k cy90YWJsZXNwYWNlLmgiCiAjaW5jbHVkZSAibWlzY2FkbWluLmgiCiAjaW5jbHVkZSAicGdfdHJh Y2UuaCIKKyNpbmNsdWRlICJwb3J0L3BnX2JpdHV0aWxzLmgiCiAjaW5jbHVkZSAic3RvcmFnZS9z aG1lbS5oIgogI2luY2x1ZGUgInV0aWxzL2d1Yy5oIgogI2luY2x1ZGUgInV0aWxzL21lbXV0aWxz LmgiCkBAIC0xMjIsNiArMTIzLDcgQEAKIAogLyogR1VDIHZhcmlhYmxlcyAqLwogYm9vbAkJdHJh Y2Vfc29ydCA9IGZhbHNlOworYm9vbAkJd2lwX3JhZGl4X3NvcnQgPSB0cnVlOwogCiAjaWZkZWYg REVCVUdfQk9VTkRFRF9TT1JUCiBib29sCQlvcHRpbWl6ZV9ib3VuZGVkX3NvcnQgPSB0cnVlOwpA QCAtNDkwLDYgKzQ5MiwyNSBAQCBzdGF0aWMgdm9pZCB0dXBsZXNvcnRfdXBkYXRlbWF4KFR1cGxl c29ydHN0YXRlICpzdGF0ZSk7CiAgKiBhYmJyZXZpYXRpb25zIG9mIHRleHQgb3IgbXVsdGkta2V5 IHNvcnRzLiAgVGhlcmUgY291bGQgYmUhICBJcyBpdCB3b3J0aCBpdD8KICAqLwogCisvKiBVc2Vk IGZvciBjb25kaXRpb25lZCBkYXR1bXMsIHNvIHdlIGNhbiBpZ25vcmUgTlVMTHMgYW5kIHNvcnQg ZGlyZWN0aW9uLiAqLworc3RhdGljIHBnX2F0dHJpYnV0ZV9hbHdheXNfaW5saW5lIGludAorcXNv cnRfdHVwbGVfY29uZGl0aW9uZWRfY29tcGFyZShTb3J0VHVwbGUgKmEsIFNvcnRUdXBsZSAqYiwg VHVwbGVzb3J0c3RhdGUgKnN0YXRlKQoreworCWlmIChhLT5jb25kX2RhdHVtMSA8IGItPmNvbmRf ZGF0dW0xKQorCQlyZXR1cm4gLTE7CisJaWYgKGEtPmNvbmRfZGF0dW0xID4gYi0+Y29uZF9kYXR1 bTEpCisJCXJldHVybiAxOworCisJLyoKKwkgKiBObyBuZWVkIHRvIHdhc3RlIGVmZm9ydCBjYWxs aW5nIHRoZSB0aWVicmVhayBmdW5jdGlvbiB3aGVuIHRoZXJlIGFyZSBubworCSAqIG90aGVyIGtl eXMgdG8gc29ydCBvbi4KKwkgKi8KKwlpZiAoc3RhdGUtPmJhc2Uub25seUtleSAhPSBOVUxMKQor CQlyZXR1cm4gMDsKKworCXJldHVybiBzdGF0ZS0+YmFzZS5jb21wYXJldHVwX3RpZWJyZWFrKGEs IGIsIHN0YXRlKTsKK30KKwogLyogVXNlZCBpZiBmaXJzdCBrZXkncyBjb21wYXJhdG9yIGlzIHNz dXBfZGF0dW1fdW5zaWduZWRfY21wICovCiBzdGF0aWMgcGdfYXR0cmlidXRlX2Fsd2F5c19pbmxp bmUgaW50CiBxc29ydF90dXBsZV91bnNpZ25lZF9jb21wYXJlKFNvcnRUdXBsZSAqYSwgU29ydFR1 cGxlICpiLCBUdXBsZXNvcnRzdGF0ZSAqc3RhdGUpCkBAIC01NjcsNiArNTg4LDE1IEBAIHFzb3J0 X3R1cGxlX2ludDMyX2NvbXBhcmUoU29ydFR1cGxlICphLCBTb3J0VHVwbGUgKmIsIFR1cGxlc29y dHN0YXRlICpzdGF0ZSkKICAqIGNvbW1vbiBjb21wYXJpc29uIGZ1bmN0aW9ucyBvbiBwYXNzLWJ5 LXZhbHVlIGxlYWRpbmcgZGF0dW1zLgogICovCiAKKyNkZWZpbmUgU1RfU09SVCBxc29ydF90dXBs ZV9jb25kaXRpb25lZAorI2RlZmluZSBTVF9FTEVNRU5UX1RZUEUgU29ydFR1cGxlCisjZGVmaW5l IFNUX0NPTVBBUkUoYSwgYiwgc3RhdGUpIHFzb3J0X3R1cGxlX2NvbmRpdGlvbmVkX2NvbXBhcmUo YSwgYiwgc3RhdGUpCisjZGVmaW5lIFNUX0NPTVBBUkVfQVJHX1RZUEUgVHVwbGVzb3J0c3RhdGUK KyNkZWZpbmUgU1RfQ0hFQ0tfRk9SX0lOVEVSUlVQVFMKKyNkZWZpbmUgU1RfU0NPUEUgc3RhdGlj CisjZGVmaW5lIFNUX0RFRklORQorI2luY2x1ZGUgImxpYi9zb3J0X3RlbXBsYXRlLmgiCisKICNk ZWZpbmUgU1RfU09SVCBxc29ydF90dXBsZV91bnNpZ25lZAogI2RlZmluZSBTVF9FTEVNRU5UX1RZ UEUgU29ydFR1cGxlCiAjZGVmaW5lIFNUX0NPTVBBUkUoYSwgYiwgc3RhdGUpIHFzb3J0X3R1cGxl X3Vuc2lnbmVkX2NvbXBhcmUoYSwgYiwgc3RhdGUpCkBAIC02MTUsNiArNjQ1LDIzNSBAQCBxc29y dF90dXBsZV9pbnQzMl9jb21wYXJlKFNvcnRUdXBsZSAqYSwgU29ydFR1cGxlICpiLCBUdXBsZXNv cnRzdGF0ZSAqc3RhdGUpCiAjZGVmaW5lIFNUX0RFRklORQogI2luY2x1ZGUgImxpYi9zb3J0X3Rl bXBsYXRlLmgiCiAKKworLyoKKyAqIFdJUDogRm9yIG5vdyBwcmVmZXIgdGVzdCBjb3ZlcmFnZSBv ZiByYWRpeCBzb3J0IGluIEFzc2VydCBidWlsZHMuCisgKi8KKyNpZmRlZiBVU0VfQVNTRVJUX0NI RUNLSU5HCisjZGVmaW5lIFFTT1JUX1RIUkVTSE9MRCAwCisjZWxzZQorI2RlZmluZSBRU09SVF9U SFJFU0hPTEQgNDAwCisjZW5kaWYKKwordHlwZWRlZiBzdHJ1Y3QgUGFydGl0aW9uSW5mbworewor CXVuaW9uCisJeworCQlzaXplX3QJCWNvdW50OworCQlzaXplX3QJCW9mZnNldDsKKwl9OworCXNp emVfdAkJbmV4dF9vZmZzZXQ7Cit9CQkJUGFydGl0aW9uSW5mbzsKKworc3RhdGljIGlubGluZSB1 aW50OF90CitleHRyYWN0X2tleShEYXR1bSBrZXksIGludCBsZXZlbCkKK3sKKwlyZXR1cm4gKGtl eSA+PiAoKChTSVpFT0ZfREFUVU0gLSAxKSAtIGxldmVsKSAqIDgpKSAmIDB4RkY7Cit9CisKK3N0 YXRpYyBpbmxpbmUgdm9pZAorc3dhcChTb3J0VHVwbGUgKmEsIFNvcnRUdXBsZSAqYikKK3sKKwlT b3J0VHVwbGUJdG1wID0gKmE7CisKKwkqYSA9ICpiOworCSpiID0gdG1wOworfQorCisvKgorICog Q29uZGl0aW9uIGRhdHVtIHRvIHdvcmsgd2l0aCBwdXJlIHVuc2lnbmVkIGNvbXBhcmlzb24sCisg KiB0YWtpbmcgQVNDL0RFU0MgaW50byBhY2NvdW50IGFzIHdlbGwuCisgKi8KK3N0YXRpYyBpbmxp bmUgRGF0dW0KK2NvbmRpdGlvbl9kYXR1bShEYXR1bSBvcmlnLCBTb3J0U3VwcG9ydCBzc3VwKQor eworCURhdHVtCQljb25kX2RhdHVtMTsKKworCWlmIChzc3VwLT5jb21wYXJhdG9yID09IHNzdXBf ZGF0dW1fc2lnbmVkX2NtcCkKKwl7CisJCS8qIGl0IHdhcyBhbHJlYWR5IGNhc3QgdG8gdW5zaWdu ZWQgd2hlbiBzdG9yZWQgKi8KKwkJY29uZF9kYXR1bTEgPSBvcmlnIF4gKFVJTlQ2NENPTlNUKDEp IDw8IDYzKTsKKwl9CisJZWxzZSBpZiAoc3N1cC0+Y29tcGFyYXRvciA9PSBzc3VwX2RhdHVtX2lu dDMyX2NtcCkKKwl7CisJCS8qCisJCSAqIEZpcnN0IG5vcm1hbGl6ZSB0byB1aW50MzIuIFRlY2hu aWNhbGx5LCB3ZSBkb24ndCBuZWVkIHRvIGRvIHRoaXMsCisJCSAqIGJ1dCBpdCBmb3JjZXMgdGhl IHVwcGVyIGJ5dGVzIHRvIHJlbWFpbiB0aGUgc2FtZSByZWdhcmRsZXNzIG9mCisJCSAqIHNpZ24u CisJCSAqLworCQl1aW50MzIJCXUzMiA9IERhdHVtR2V0VUludDMyKG9yaWcpIF4gKCh1aW50MzIp IDEgPDwgMzEpOworCisJCWNvbmRfZGF0dW0xID0gVUludDMyR2V0RGF0dW0odTMyKTsKKwl9CisJ ZWxzZQorCXsKKwkJQXNzZXJ0KHNzdXAtPmNvbXBhcmF0b3IgPT0gc3N1cF9kYXR1bV91bnNpZ25l ZF9jbXApOworCQljb25kX2RhdHVtMSA9IG9yaWc7CisJfQorCisJaWYgKHNzdXAtPnNzdXBfcmV2 ZXJzZSkKKwkJY29uZF9kYXR1bTEgPSB+Y29uZF9kYXR1bTE7CisKKwlyZXR1cm4gY29uZF9kYXR1 bTE7Cit9CisKKy8qCisgKiBCYXNlZCBvbiBpbXBsZW1lbnRhdGlvbiBpbiBodHRwczovL2dpdGh1 Yi5jb20vc2thcnVwa2Uvc2thX3NvcnQgKEJvb3N0IGxpY2Vuc2UpLAorICogd2l0aCB0aGUgZm9s bG93aW5nIGNoYW5nZXM6CisgKiAgLSB1bnJvbGwgbG9vcCBpbiBjb3VudGluZyBzdGVwCisgKiAg LSBjb3VudCBzb3J0ZWQgcGFydGl0aW9ucyBpbiBldmVyeSBwYXNzLCByYXRoZXIgdGhhbiBtYWlu dGFpbmluZyBsaXN0IG9mIHVuc29ydGVkIHBhcnRpdGlvbnMKKyAqIFRPRE86IG1hdGNoIHFzb3J0 IEFQSSB3aXRoIG51bWJlciBvZiBlbGVtZW50cyByYXRoZXIgdGhhbiBlbmQgcG9pbnRlcgorICov CitzdGF0aWMgdm9pZAorc2thX2J5dGVfc29ydChTb3J0VHVwbGUgKmJlZ2luLAorCQkJICBTb3J0 VHVwbGUgKmVuZCwgaW50IGxldmVsLCBUdXBsZXNvcnRzdGF0ZSAqc3RhdGUpCit7CisJLyogc2l6 ZV90CQljb3VudHMwWzI1Nl0gPSB7MH07ICovCisJc2l6ZV90CQljb3VudHMxWzI1Nl0gPSB7MH07 CisJc2l6ZV90CQljb3VudHMyWzI1Nl0gPSB7MH07CisJc2l6ZV90CQljb3VudHMzWzI1Nl0gPSB7 MH07CisJUGFydGl0aW9uSW5mbyBwYXJ0aXRpb25zWzI1Nl0gPSB7MH07CisJdWludDhfdAkJcmVt YWluaW5nX3BhcnRpdGlvbnNbMjU2XSA9IHswfTsKKwlzaXplX3QJCXRvdGFsID0gMDsKKwlpbnQJ CQludW1fcGFydGl0aW9ucyA9IDA7CisJaW50CQkJbnVtX3JlbWFpbmluZzsKKwlTb3J0VHVwbGUg ICpjdHVwOworCisJLyogY291bnQga2V5IGNodW5rcywgdW5yb2xsZWQgZm9yIHNwZWVkICovCisK Kwlmb3IgKGN0dXAgPSBiZWdpbjsgY3R1cCArIDQgPCBlbmQ7IGN0dXAgKz0gNCkKKwl7CisJCXVp bnQ4CQlrZXlfY2h1bmswID0gZXh0cmFjdF9rZXkoKGN0dXAgKyAwKS0+Y29uZF9kYXR1bTEsIGxl dmVsKTsKKwkJdWludDgJCWtleV9jaHVuazEgPSBleHRyYWN0X2tleSgoY3R1cCArIDEpLT5jb25k X2RhdHVtMSwgbGV2ZWwpOworCQl1aW50OAkJa2V5X2NodW5rMiA9IGV4dHJhY3Rfa2V5KChjdHVw ICsgMiktPmNvbmRfZGF0dW0xLCBsZXZlbCk7CisJCXVpbnQ4CQlrZXlfY2h1bmszID0gZXh0cmFj dF9rZXkoKGN0dXAgKyAzKS0+Y29uZF9kYXR1bTEsIGxldmVsKTsKKworCQlwYXJ0aXRpb25zW2tl eV9jaHVuazBdLmNvdW50Kys7CisJCWNvdW50czFba2V5X2NodW5rMV0rKzsKKwkJY291bnRzMltr ZXlfY2h1bmsyXSsrOworCQljb3VudHMzW2tleV9jaHVuazNdKys7CisKKwl9CisKKwlmb3IgKHNp emVfdCBpID0gMDsgaSA8IDI1NjsgaSsrKQorCQlwYXJ0aXRpb25zW2ldLmNvdW50ICs9IGNvdW50 czFbaV0gKyBjb3VudHMyW2ldICsgY291bnRzM1tpXTsKKworCWZvciAoOyBjdHVwIDwgZW5kOyBj dHVwKyspCisJeworCQl1aW50OAkJa2V5X2NodW5rOworCisJCWtleV9jaHVuayA9IGV4dHJhY3Rf a2V5KGN0dXAtPmNvbmRfZGF0dW0xLCBsZXZlbCk7CisJCXBhcnRpdGlvbnNba2V5X2NodW5rXS5j b3VudCsrOworCX0KKworCS8qIGNvbXB1dGUgcGFydGl0aW9uIG9mZnNldHMgKi8KKwlmb3IgKGlu dCBpID0gMDsgaSA8IDI1NjsgKytpKQorCXsKKwkJc2l6ZV90CQljb3VudCA9IHBhcnRpdGlvbnNb aV0uY291bnQ7CisKKwkJaWYgKGNvdW50KQorCQl7CisJCQlwYXJ0aXRpb25zW2ldLm9mZnNldCA9 IHRvdGFsOworCQkJdG90YWwgKz0gY291bnQ7CisJCQlyZW1haW5pbmdfcGFydGl0aW9uc1tudW1f cGFydGl0aW9uc10gPSBpOworCQkJKytudW1fcGFydGl0aW9uczsKKwkJfQorCQlwYXJ0aXRpb25z W2ldLm5leHRfb2Zmc2V0ID0gdG90YWw7CisJfQorCisJbnVtX3JlbWFpbmluZyA9IG51bV9wYXJ0 aXRpb25zOworCisJLyoKKwkgKiBQZXJtdXRlIHR1cGxlcyB0byBjb3JyZWN0IHBhcnRpdGlvbi4g SWYgd2Ugc3RhcnRlZCB3aXRoIG9uZSBwYXJ0aXRpb24sCisJICogdGhlcmUgaXMgbm90aGluZyB0 byBkby4gSWYgYSBwZXJtdXRhdGlvbiBmcm9tIGEgcHJldmlvdXMgaXRlcmF0aW9uCisJICogcmVz dWx0cyBpbiBhIHNpbmdsZSBwYXJ0aXRpb24gdGhhdCBoYXNuJ3QgYmVlbiBtYXJrZWQgYXMgc29y dGVkLCB3ZQorCSAqIGtub3cgaXQncyBhY3R1YWxseSBzb3J0ZWQuCisJICovCisJd2hpbGUgKG51 bV9yZW1haW5pbmcgPiAxKQorCXsKKwkJLyoKKwkJICogV2UgY2FuIG9ubHkgZXhpdCB0aGUgbG9v cCB3aGVuIGFsbCBwYXJ0aXRpb25zIGFyZSBzb3J0ZWQsIHNvIG11c3QKKwkJICogcmVzZXQgZXZl cnkgaXRlcmF0aW9uCisJCSAqLworCQludW1fcmVtYWluaW5nID0gbnVtX3BhcnRpdGlvbnM7CisK KwkJZm9yIChpbnQgaSA9IDA7IGkgPCBudW1fcGFydGl0aW9uczsgaSsrKQorCQl7CisJCQl1aW50 OAkJaWR4ID0gcmVtYWluaW5nX3BhcnRpdGlvbnNbaV07CisKKwkJCVBhcnRpdGlvbkluZm8gcGFy dCA9IHBhcnRpdGlvbnNbaWR4XTsKKworCQkJZm9yIChTb3J0VHVwbGUgKnN0ID0gYmVnaW4gKyBw YXJ0Lm9mZnNldDsKKwkJCQkgc3QgPCBiZWdpbiArIHBhcnQubmV4dF9vZmZzZXQ7CisJCQkJIHN0 KyspCisJCQl7CisJCQkJdWludDgJCXRoaXNfcGFydGl0aW9uID0gZXh0cmFjdF9rZXkoc3QtPmNv bmRfZGF0dW0xLCBsZXZlbCk7CisJCQkJc2l6ZV90CQlvZmZzZXQgPSBwYXJ0aXRpb25zW3RoaXNf cGFydGl0aW9uXS5vZmZzZXQrKzsKKworCQkJCUFzc2VydChiZWdpbiArIG9mZnNldCA8IGVuZCk7 CisJCQkJc3dhcChzdCwgYmVnaW4gKyBvZmZzZXQpOworCQkJfTsKKworCQkJaWYgKHBhcnQub2Zm c2V0ID09IHBhcnQubmV4dF9vZmZzZXQpCisJCQl7CisJCQkJLyogcGFydGl0aW9uIGlzIHNvcnRl ZDsgc2tpcCAqLworCQkJCW51bV9yZW1haW5pbmctLTsKKwkJCX0KKwkJfQorCX0KKworCXsKKwkJ c2l6ZV90CQlzdGFydF9vZmZzZXQgPSAwOworCQlTb3J0VHVwbGUgICpwYXJ0aXRpb25fYmVnaW4g PSBiZWdpbjsKKworCQlmb3IgKHVpbnQ4X3QgKml0ID0gcmVtYWluaW5nX3BhcnRpdGlvbnMsICpl bmQgPSByZW1haW5pbmdfcGFydGl0aW9ucyArIG51bV9wYXJ0aXRpb25zOworCQkJIGl0ICE9IGVu ZDsKKwkJCSArK2l0KQorCQl7CisJCQlzaXplX3QJCWVuZF9vZmZzZXQgPSBwYXJ0aXRpb25zWypp dF0ubmV4dF9vZmZzZXQ7CisJCQlTb3J0VHVwbGUgICpwYXJ0aXRpb25fZW5kID0gYmVnaW4gKyBl bmRfb2Zmc2V0OworCQkJcHRyZGlmZl90CW51bV9lbGVtZW50cyA9IGVuZF9vZmZzZXQgLSBzdGFy dF9vZmZzZXQ7CisKKwkJCWlmIChudW1fZWxlbWVudHMgPiAxKQorCQkJeworCQkJCWlmIChsZXZl bCA8IFNJWkVPRl9EQVRVTSAtIDEpCisJCQkJeworCQkJCQlpZiAobnVtX2VsZW1lbnRzIDwgUVNP UlRfVEhSRVNIT0xEKQorCQkJCQl7CisJCQkJCQlxc29ydF90dXBsZV9jb25kaXRpb25lZChwYXJ0 aXRpb25fYmVnaW4sCisJCQkJCQkJCQkJCQludW1fZWxlbWVudHMsCisJCQkJCQkJCQkJCQlzdGF0 ZSk7CisJCQkJCX0KKwkJCQkJZWxzZQorCQkJCQl7CisJCQkJCQlza2FfYnl0ZV9zb3J0KHBhcnRp dGlvbl9iZWdpbiwKKwkJCQkJCQkJCSAgcGFydGl0aW9uX2VuZCwKKwkJCQkJCQkJCSAgbGV2ZWwg KyAxLAorCQkJCQkJCQkJICBzdGF0ZSk7CisJCQkJCX0KKwkJCQl9CisJCQkJZWxzZSBpZiAoc3Rh dGUtPmJhc2Uub25seUtleSA9PSBOVUxMKQorCQkJCXsKKwkJCQkJLyoKKwkJCQkJICogRmluaXNo ZWQgcmFkaXggc29ydCBvbiBhbGwgYnl0ZXMgb2YgY29uZF9kYXR1bTEKKwkJCQkJICogKHBvc3Np YmlseSBhYmJyZXZpYXRlZCksIG5vdyBxc29ydCB3aXRoIHRpZWJyZWFrCisJCQkJCSAqIGNvbXBh cmF0b3IuCisJCQkJCSAqIFhYWCBjb21wYXJldHVwX3RpZWJyZWFrIGNhbm5vdCBpbnNwZWN0IGlz bnVsbDEuCisJCQkJCSAqIEluIGNvcmUsIHRoZSBvbmx5IHRpZWJyZWFrIHRoYXQgZG9lcyBzbyBp cyBjb21wYXJldHVwX2RhdHVtX3RpZWJyZWFrLAorCQkJCQkgKiBidXQgd2Ugd291bGRuJ3QgaGF2 ZSBnb3R0ZW4gaGVyZSBpZiB0aGF0J3MgdGhlIGNhc2UuCisJCQkJCSAqLworCQkJCQlxc29ydF90 dXBsZShwYXJ0aXRpb25fYmVnaW4sCisJCQkJCQkJCW51bV9lbGVtZW50cywKKwkJCQkJCQkJc3Rh dGUtPmJhc2UuY29tcGFyZXR1cF90aWVicmVhaywKKwkJCQkJCQkJc3RhdGUpOworCQkJCX0KKwkJ CX0KKwkJCXN0YXJ0X29mZnNldCA9IGVuZF9vZmZzZXQ7CisJCQlwYXJ0aXRpb25fYmVnaW4gPSBw YXJ0aXRpb25fZW5kOworCQl9CisJfQorfQorCiAvKgogICoJCXR1cGxlc29ydF9iZWdpbl94eHgK ICAqCkBAIC0yNjYzLDggKzI5MjIsMjAzIEBAIHNvcnRfYm91bmRlZF9oZWFwKFR1cGxlc29ydHN0 YXRlICpzdGF0ZSkKIAlzdGF0ZS0+Ym91bmRVc2VkID0gdHJ1ZTsKIH0KIAorLyogV0lQOiBhbGxv dyB0dXJuaW5nIGNvbW1vbiBwcmVmaXggc2tpcHBpbmcgb2ZmIGZvciB0ZXN0aW5nICovCisjZGVm aW5lIENPTU1PTl9QUkVGSVgKKworLyoKKyAqIENvbXB1dGUgY29uZGl0aW9uZWQgZGF0dW1zIGZv ciBTb3J0VHVwbGVzIHNvIHRoYXQgYSBzaW5nbGUKKyAqIHVuc2lnbmVkIGNvbXBhcmlzb24gcmVz b2x2ZXMgdGhlIHNvcnQgb3JkZXIgdXAgdG8gY29tcGFyZXR1cF8qX3RpZWJyZWFrLgorICogVGhl biBkaXNwYXRjaCB0byBlaXRoZXIgcmFkaXggc29ydCBvciBhIHNwZWNpYWxpemVkIHFzb3J0Lgor ICovCitzdGF0aWMgdm9pZAorc29ydF90dXBsZV9jb25kaXRpb25lZChUdXBsZXNvcnRzdGF0ZSAq c3RhdGUpCit7CisJU29ydFN1cHBvcnREYXRhIHNzdXAgPSBzdGF0ZS0+YmFzZS5zb3J0S2V5c1sw XTsKKworCWJvb2wJCW51bGxzX2ZpcnN0ID0gc3N1cC5zc3VwX251bGxzX2ZpcnN0OworCVNvcnRU dXBsZSAgKmZpcnN0ID0gc3RhdGUtPm1lbXR1cGxlczsKKwlTb3J0VHVwbGUgICpsYXN0ID0gc3Rh dGUtPm1lbXR1cGxlcyArIHN0YXRlLT5tZW10dXBjb3VudDsKKwlTb3J0VHVwbGUgICpub3RfbnVs bF9zdGFydDsKKwlzaXplX3QJCWQxLAorCQkJCWQyLAorCQkJCW5vdF9udWxsX2NvdW50OworI2lm ZGVmIENPTU1PTl9QUkVGSVgKKwlEYXR1bQkJZmlyc3RfZGF0dW0gPSAwOworCURhdHVtCQljb21t b25fdXBwZXJfYml0cyA9IDA7CisjZW5kaWYKKwlpbnQJCQljb21tb25fcHJlZml4OworCisJLyoK KwkgKiBQYXJ0aXRpb24gYnkgaXNudWxsMSwgc2luY2Ugd2UgY2FuIG9ubHkgcmFkaXggc29ydCBv biBub24tTlVMTAorCSAqIGVsZW1lbnRzLgorCSAqLworCisJLyoKKwkgKiBGaW5kIHRoZSBsZWZ0 bW9zdCBOT1QgTlVMTCB0dXBsZSBpZiBOVUxMUyBGSVJTVCwgb3IgbGVmdG1vc3QgTlVMTAorCSAq IGVsZW1lbnQgaWYgTlVMTFMgTEFTVC4KKwkgKi8KKwl3aGlsZSAoZmlyc3QgPCBsYXN0ICYmIGZp cnN0LT5pc251bGwxID09IG51bGxzX2ZpcnN0KQorCQlmaXJzdCsrOworCisJLyoKKwkgKiBYWFgg V2UgbXVzdCBzdGFydCAibGFzdCIgYWZ0ZXIgdGhlIGZpbmFsIHR1cGxlIHRvIG1haW50YWluIHRo ZQorCSAqIGludmFyaWFudCB0aGF0IGl0IGVuZHMgdXAgb25lIGFmdGVyIHRoZSBmaXJzdCBwYXJ0 aXRpb24sIGFuZCB0aGUgZmlyc3QKKwkgKiBwYXJ0aXRpb24gbWF5IGNvcnJlc3BvbmQgdG8gdGhl IGVudGlyZSBhcnJheS4gSWYgImZpcnN0IiBpc24ndCBnb3R0ZW4KKwkgKiB0aGlzIGZhciwgd2Ug bmVlZCB0byBwcmUtZGVjcmVtZW50ICJsYXN0IiBiZWZvcmUgYmVnaW5uaW5nIGl0cyBsb29wLgor CSAqLworCWlmIChmaXJzdCA8IGxhc3QpCisJCWxhc3QtLTsKKworCS8qCisJICogRmluZCB0aGUg cmlnaHRtb3N0IE5VTEwgdHVwbGUgaWYgTlVMTFMgRklSU1QsIG9yIHJpZ2h0bW9zdCBOT1QgTlVM TAorCSAqIHR1cGxlIGlmIE5VTExTIExBU1QuCisJICovCisJd2hpbGUgKGZpcnN0IDwgbGFzdCAm JiBsYXN0LT5pc251bGwxICE9IG51bGxzX2ZpcnN0KQorCQlsYXN0LS07CisKKwkvKiBzd2FwIHBh aXJzIG9mIHR1cGxlcyB0aGF0IGFyZSBpbiB0aGUgd3Jvbmcgb3JkZXIgKi8KKwl3aGlsZSAoZmly c3QgPCBsYXN0KQorCXsKKwkJc3dhcChmaXJzdCwgbGFzdCk7CisJCXdoaWxlIChmaXJzdCA8IGxh c3QgJiYgZmlyc3QtPmlzbnVsbDEgPT0gbnVsbHNfZmlyc3QpCisJCQlmaXJzdCsrOworCQl3aGls ZSAoZmlyc3QgPCBsYXN0ICYmIGxhc3QtPmlzbnVsbDEgIT0gbnVsbHNfZmlyc3QpCisJCQlsYXN0 LS07CisJfQorCisJZDEgPSBsYXN0IC0gc3RhdGUtPm1lbXR1cGxlczsKKwlkMiA9IHN0YXRlLT5t ZW10dXBjb3VudCAtIGQxOworCisJQXNzZXJ0KGxhc3QgPT0gZmlyc3QpOworCUFzc2VydChsYXN0 ICsgZDIgPT0gc3RhdGUtPm1lbXR1cGxlcyArIHN0YXRlLT5tZW10dXBjb3VudCk7CisJZm9yIChT b3J0VHVwbGUgKnBtID0gc3RhdGUtPm1lbXR1cGxlczsKKwkJIHBtIDwgc3RhdGUtPm1lbXR1cGxl cyArIGQxOworCQkgcG0rKykKKwkJQXNzZXJ0KHBtLT5pc251bGwxID09IG51bGxzX2ZpcnN0KTsK Kwlmb3IgKFNvcnRUdXBsZSAqcG0gPSBsYXN0OworCQkgcG0gPCBsYXN0ICsgZDI7CisJCSBwbSsr KQorCQlBc3NlcnQocG0tPmlzbnVsbDEgIT0gbnVsbHNfZmlyc3QpOworCisJLyoKKwkgKiBTb3J0 IG51bGwgcGFydGl0aW9uIHVzaW5nIHRpZWJyZWFrIGNvbXBhcmF0b3IuIFhYWCB0aGlzIHdpbGwg cmVwZWF0IHRoZQorCSAqIE5VTEwgY2hlY2sgZm9yIGFiYnJldmlhdGVkIGtleXMuCisJICovCisJ aWYgKG51bGxzX2ZpcnN0KQorCXsKKwkJcXNvcnRfdHVwbGUoc3RhdGUtPm1lbXR1cGxlcywKKwkJ CQkJZDEsCisJCQkJCXN0YXRlLT5iYXNlLmNvbXBhcmV0dXBfdGllYnJlYWssCisJCQkJCXN0YXRl KTsKKwkJbm90X251bGxfc3RhcnQgPSBsYXN0OworCQlub3RfbnVsbF9jb3VudCA9IGQyOworCX0K KwllbHNlCisJeworCQlxc29ydF90dXBsZShsYXN0LAorCQkJCQlkMiwKKwkJCQkJc3RhdGUtPmJh c2UuY29tcGFyZXR1cF90aWVicmVhaywKKwkJCQkJc3RhdGUpOworCQlub3RfbnVsbF9zdGFydCA9 IHN0YXRlLT5tZW10dXBsZXM7CisJCW5vdF9udWxsX2NvdW50ID0gZDE7CisJfQorCisJLyoKKwkg KiBDb25kaXRpb24gZGF0dW0gc28gdGhhdCB1bnNpZ25lZCBjb21wYXJpc2lvbiBpcyBvcmRlci1w cmVzZXJ2aW5nLCBhbmQKKwkgKiBjb21wdXRlIHRoZSBjb21tb24gcHJlZml4IHRvIHNraXAgdW5w cm9kdWN0aXZlIHJlY3Vyc2lvbiBzdGVwcyBkdXJpbmcKKwkgKiByYWRpeCBzb3J0LgorCSAqLwor CWZvciAoU29ydFR1cGxlICp0dXAgPSBub3RfbnVsbF9zdGFydDsKKwkJIHR1cCA8IG5vdF9udWxs X3N0YXJ0ICsgbm90X251bGxfY291bnQ7CisJCSB0dXArKykKKwl7CisJCURhdHVtCQljb25kX2Rh dHVtMSA9IGNvbmRpdGlvbl9kYXR1bSh0dXAtPmRhdHVtMSwgJnNzdXApOworI2lmZGVmIENPTU1P Tl9QUkVGSVgKKwkJaWYgKHR1cCA9PSBub3RfbnVsbF9zdGFydCkKKwkJeworCQkJLyogTmVlZCB0 byBzdGFydCB3aXRoIHNvbWUgdmFsdWUsIG1heSBhcyB3ZWxsIGJlIHRoZSBmaXJzdCBvbmUuICov CisJCQlmaXJzdF9kYXR1bSA9IGNvbmRfZGF0dW0xOworCQl9CisJCWVsc2UKKwkJeworCQkJRGF0 dW0JCXRoaXNfY29tbW9uX2JpdHM7CisKKwkJCS8qIFRoZSBiaXRzIGluIGNvbW1vbiB3aWxsIGJl IHplcm8gKi8KKwkJCXRoaXNfY29tbW9uX2JpdHMgPSBmaXJzdF9kYXR1bSBeIGNvbmRfZGF0dW0x OworCisJCQkvKgorCQkJICogV2UncmUgcmVhbGx5IG9ubHkgaW50ZXJlc3RlZCBpbiB0aGUgY2Fz ZSB3aGVyZSB0aGUgcmlnaHRtb3N0CisJCQkgKiBvbmUgYml0IGlzIGZ1cnRoZXIgcmlnaHQsIGJ1 dCB0aGlzIGJyYW5jaCBzaG91bGQgYmUgcmFyZSBlbm91Z2gKKwkJCSAqIG5vdCB0byB3YXN0ZSBj eWNsZXMgdHJ5aW5nIGhhcmRlci4KKwkJCSAqLworCQkJaWYgKHRoaXNfY29tbW9uX2JpdHMgPiBj b21tb25fdXBwZXJfYml0cykKKwkJCQljb21tb25fdXBwZXJfYml0cyA9IHRoaXNfY29tbW9uX2Jp dHM7CisJCX0KKyNlbmRpZgorCQl0dXAtPmNvbmRfZGF0dW0xID0gY29uZF9kYXR1bTE7CisJfQor CisJaWYgKG5vdF9udWxsX2NvdW50IDwgUVNPUlRfVEhSRVNIT0xEKQorCQlxc29ydF90dXBsZV9j b25kaXRpb25lZChub3RfbnVsbF9zdGFydCwKKwkJCQkJCQkJbm90X251bGxfY291bnQsCisJCQkJ CQkJCXN0YXRlKTsKKwllbHNlCisJeworCisJCS8qCisJCSAqIFRoZSB1cHBlciBiaXRzIGFyZSB6 ZXJvIHdoZXJlIGFsbCB2YWx1ZXMgYXJlIHRoZSBzYW1lLCBpZiBhbnkuIFR1cm4KKwkJICogdGhl IGJ5dGUgcG9zaXRpb24gb2YgdGhlIHJpZ2h0bW9zdCBvbmUgYml0IGludG8gdGhlIGJ5dGUgd2hl cmUKKwkJICogcmFkaXggc29ydCBzaG91bGQgc3RhcnQgYnVja2V0aW5nLiBPUi1pbmcgaW4gdGhl IGxvd2VzdCBiaXQgZ3VhcmRzCisJCSAqIGFnYWluc3QgdW5kZWZpbmVkIGJlaGF2aW9yIHdpdGhv dXQgY2hhbmdpbmcgdGhlIHJlc3VsdC4KKwkJICovCisjaWZkZWYgQ09NTU9OX1BSRUZJWAorCQlj b21tb25fcHJlZml4ID0gc2l6ZW9mKERhdHVtKSAtIDEgLQorCQkJKHBnX2xlZnRtb3N0X29uZV9w b3M2NChjb21tb25fdXBwZXJfYml0cyB8IDEpIC8gQklUU19QRVJfQllURSk7CisjZWxzZQorCQlj b21tb25fcHJlZml4ID0gMDsKKyNlbmRpZgorCQkvKiBwZXJmb3JtIHRoZSByYWRpeCBzb3J0IG9u IHRoZSBub3QtTlVMTCBwYXJ0aXRpb24gKi8KKwkJc2thX2J5dGVfc29ydChub3RfbnVsbF9zdGFy dCwKKwkJCQkJICBub3RfbnVsbF9zdGFydCArIG5vdF9udWxsX2NvdW50LAorCQkJCQkgIGNvbW1v bl9wcmVmaXgsCisJCQkJCSAgc3RhdGUpOworCX0KKworCS8qCisJICogUmVzdG9yZSBmaWVsZHMg dGhhdCB3ZXJlIG92ZXJ3cml0dGVuIHdpdGggdGVtcG9yYXJ5IGNvbmRpdGlvbmVkIGRhdHVtMQor CSAqLworCWZvciAoU29ydFR1cGxlICp0dXAgPSBub3RfbnVsbF9zdGFydDsKKwkJIHR1cCA8IG5v dF9udWxsX3N0YXJ0ICsgbm90X251bGxfY291bnQ7CisJCSB0dXArKykKKwl7CisJCS8qIG5lZWQg dG8gcmVzdG9yZSBOT1QgTlVMTCAqLworCQl0dXAtPmlzbnVsbDEgPSBmYWxzZTsKKwkJLyogYmUg dGlkeSAqLworCQl0dXAtPnNyY3RhcGUgPSAwOworCX0KK30KKworLyogVmVyaWZ5IHNvcnQgdXNp bmcgc3RhbmRhcmQgY29tcGFyYXRvci4gKi8KK3N0YXRpYyB2b2lkCitjaGVja19zb3J0ZWQoVHVw bGVzb3J0c3RhdGUgKnN0YXRlKQoreworI2lmZGVmIFVTRV9BU1NFUlRfQ0hFQ0tJTkcKKwlmb3Ig KFNvcnRUdXBsZSAqcG0gPSBzdGF0ZS0+bWVtdHVwbGVzICsgMTsKKwkJIHBtIDwgc3RhdGUtPm1l bXR1cGxlcyArIHN0YXRlLT5tZW10dXBjb3VudDsKKwkJIHBtKyspCisJeworI2lmIDAKKwkJQXNz ZXJ0KENPTVBBUkVUVVAoc3RhdGUsIHBtIC0gMSwgcG0pIDw9IDApOworI2Vsc2UKKwkJaWYgKENP TVBBUkVUVVAoc3RhdGUsIHBtIC0gMSwgcG0pID4gMCkKKwkJCWVsb2coRVJST1IsICJTT1JUIEZB SUxFRCIpOworI2VuZGlmCisJfQorI2VuZGlmCit9CisKIC8qCi0gKiBTb3J0IGFsbCBtZW10dXBs ZXMgdXNpbmcgc3BlY2lhbGl6ZWQgcXNvcnQoKSByb3V0aW5lcy4KKyAqIFNvcnQgYWxsIG1lbXR1 cGxlcyB1c2luZyBzcGVjaWFsaXplZCByb3V0aW5lcy4KICAqCiAgKiBRdWlja3NvcnQgaXMgdXNl ZCBmb3Igc21hbGwgaW4tbWVtb3J5IHNvcnRzLCBhbmQgZXh0ZXJuYWwgc29ydCBydW5zLgogICov CkBAIC0yNjgxLDI2ICszMTM1LDQyIEBAIHR1cGxlc29ydF9zb3J0X21lbXR1cGxlcyhUdXBsZXNv cnRzdGF0ZSAqc3RhdGUpCiAJCSAqLwogCQlpZiAoc3RhdGUtPmJhc2UuaGF2ZURhdHVtMSAmJiBz dGF0ZS0+YmFzZS5zb3J0S2V5cykKIAkJewotCQkJaWYgKHN0YXRlLT5iYXNlLnNvcnRLZXlzWzBd LmNvbXBhcmF0b3IgPT0gc3N1cF9kYXR1bV91bnNpZ25lZF9jbXApCi0JCQl7Ci0JCQkJcXNvcnRf dHVwbGVfdW5zaWduZWQoc3RhdGUtPm1lbXR1cGxlcywKLQkJCQkJCQkJCSBzdGF0ZS0+bWVtdHVw Y291bnQsCi0JCQkJCQkJCQkgc3RhdGUpOwotCQkJCXJldHVybjsKLQkJCX0KLQkJCWVsc2UgaWYg KHN0YXRlLT5iYXNlLnNvcnRLZXlzWzBdLmNvbXBhcmF0b3IgPT0gc3N1cF9kYXR1bV9zaWduZWRf Y21wKQorCQkJU29ydFN1cHBvcnREYXRhIHNzdXAgPSBzdGF0ZS0+YmFzZS5zb3J0S2V5c1swXTsK KworCQkJaWYgKHdpcF9yYWRpeF9zb3J0KQogCQkJewotCQkJCXFzb3J0X3R1cGxlX3NpZ25lZChz dGF0ZS0+bWVtdHVwbGVzLAotCQkJCQkJCQkgICBzdGF0ZS0+bWVtdHVwY291bnQsCi0JCQkJCQkJ CSAgIHN0YXRlKTsKLQkJCQlyZXR1cm47CisJCQkJaWYgKChzc3VwLmNvbXBhcmF0b3IgPT0gc3N1 cF9kYXR1bV91bnNpZ25lZF9jbXAgfHwKKwkJCQkJIHNzdXAuY29tcGFyYXRvciA9PSBzc3VwX2Rh dHVtX3NpZ25lZF9jbXAgfHwKKwkJCQkJIHNzdXAuY29tcGFyYXRvciA9PSBzc3VwX2RhdHVtX2lu dDMyX2NtcCkpCisJCQkJeworCQkJCQlzb3J0X3R1cGxlX2NvbmRpdGlvbmVkKHN0YXRlKTsKKwkJ CQkJY2hlY2tfc29ydGVkKHN0YXRlKTsKKwkJCQkJcmV0dXJuOworCQkJCX0KIAkJCX0KLQkJCWVs c2UgaWYgKHN0YXRlLT5iYXNlLnNvcnRLZXlzWzBdLmNvbXBhcmF0b3IgPT0gc3N1cF9kYXR1bV9p bnQzMl9jbXApCisJCQllbHNlCiAJCQl7Ci0JCQkJcXNvcnRfdHVwbGVfaW50MzIoc3RhdGUtPm1l bXR1cGxlcywKLQkJCQkJCQkJICBzdGF0ZS0+bWVtdHVwY291bnQsCi0JCQkJCQkJCSAgc3RhdGUp OwotCQkJCXJldHVybjsKKwkJCQlpZiAoc3RhdGUtPmJhc2Uuc29ydEtleXNbMF0uY29tcGFyYXRv ciA9PSBzc3VwX2RhdHVtX3Vuc2lnbmVkX2NtcCkKKwkJCQl7CisJCQkJCXFzb3J0X3R1cGxlX3Vu c2lnbmVkKHN0YXRlLT5tZW10dXBsZXMsCisJCQkJCQkJCQkJIHN0YXRlLT5tZW10dXBjb3VudCwK KwkJCQkJCQkJCQkgc3RhdGUpOworCQkJCQlyZXR1cm47CisJCQkJfQorCQkJCWVsc2UgaWYgKHN0 YXRlLT5iYXNlLnNvcnRLZXlzWzBdLmNvbXBhcmF0b3IgPT0gc3N1cF9kYXR1bV9zaWduZWRfY21w KQorCQkJCXsKKwkJCQkJcXNvcnRfdHVwbGVfc2lnbmVkKHN0YXRlLT5tZW10dXBsZXMsCisJCQkJ CQkJCQkgICBzdGF0ZS0+bWVtdHVwY291bnQsCisJCQkJCQkJCQkgICBzdGF0ZSk7CisJCQkJCXJl dHVybjsKKwkJCQl9CisJCQkJZWxzZSBpZiAoc3RhdGUtPmJhc2Uuc29ydEtleXNbMF0uY29tcGFy YXRvciA9PSBzc3VwX2RhdHVtX2ludDMyX2NtcCkKKwkJCQl7CisJCQkJCXFzb3J0X3R1cGxlX2lu dDMyKHN0YXRlLT5tZW10dXBsZXMsCisJCQkJCQkJCQkgIHN0YXRlLT5tZW10dXBjb3VudCwKKwkJ CQkJCQkJCSAgc3RhdGUpOworCQkJCQlyZXR1cm47CisJCQkJfQogCQkJfQogCQl9CiAKZGlmZiAt LWdpdCBhL3NyYy9pbmNsdWRlL3V0aWxzL2d1Yy5oIGIvc3JjL2luY2x1ZGUvdXRpbHMvZ3VjLmgK aW5kZXggZjIxZWMzN2RhODkuLmJjNmY3ZmE2MGYzIDEwMDY0NAotLS0gYS9zcmMvaW5jbHVkZS91 dGlscy9ndWMuaAorKysgYi9zcmMvaW5jbHVkZS91dGlscy9ndWMuaApAQCAtMzI0LDYgKzMyNCw3 IEBAIGV4dGVybiBQR0RMTElNUE9SVCBpbnQgdGNwX3VzZXJfdGltZW91dDsKIGV4dGVybiBQR0RM TElNUE9SVCBjaGFyICpyb2xlX3N0cmluZzsKIGV4dGVybiBQR0RMTElNUE9SVCBib29sIGluX2hv dF9zdGFuZGJ5X2d1YzsKIGV4dGVybiBQR0RMTElNUE9SVCBib29sIHRyYWNlX3NvcnQ7CitleHRl cm4gUEdETExJTVBPUlQgYm9vbCB3aXBfcmFkaXhfc29ydDsKIAogI2lmZGVmIERFQlVHX0JPVU5E RURfU09SVAogZXh0ZXJuIFBHRExMSU1QT1JUIGJvb2wgb3B0aW1pemVfYm91bmRlZF9zb3J0Owpk aWZmIC0tZ2l0IGEvc3JjL2luY2x1ZGUvdXRpbHMvdHVwbGVzb3J0LmggYi9zcmMvaW5jbHVkZS91 dGlscy90dXBsZXNvcnQuaAppbmRleCBlZjc5ZjI1OWY5My4uYjJlY2JiYzllNTEgMTAwNjQ0Ci0t LSBhL3NyYy9pbmNsdWRlL3V0aWxzL3R1cGxlc29ydC5oCisrKyBiL3NyYy9pbmNsdWRlL3V0aWxz L3R1cGxlc29ydC5oCkBAIC0xNDksOCArMTQ5LDE2IEBAIHR5cGVkZWYgc3RydWN0CiB7CiAJdm9p ZAkgICAqdHVwbGU7CQkJLyogdGhlIHR1cGxlIGl0c2VsZiAqLwogCURhdHVtCQlkYXR1bTE7CQkJ LyogdmFsdWUgb2YgZmlyc3Qga2V5IGNvbHVtbiAqLwotCWJvb2wJCWlzbnVsbDE7CQkvKiBpcyBm aXJzdCBrZXkgY29sdW1uIE5VTEw/ICovCi0JaW50CQkJc3JjdGFwZTsJCS8qIHNvdXJjZSB0YXBl IG51bWJlciAqLworCisJdW5pb24KKwl7CisJCXN0cnVjdAorCQl7CisJCQlib29sCQlpc251bGwx OwkJLyogaXMgZmlyc3Qga2V5IGNvbHVtbiBOVUxMPyAqLworCQkJaW50CQkJc3JjdGFwZTsJCS8q IHNvdXJjZSB0YXBlIG51bWJlciAqLworCQl9OworCQlEYXR1bQkJY29uZF9kYXR1bTE7CQkvKiBz b3J0IGtleSBmb3IgcmFkaXggc29ydCAqLworCX07CiB9IFNvcnRUdXBsZTsKIAogdHlwZWRlZiBp bnQgKCpTb3J0VHVwbGVDb21wYXJhdG9yKSAoY29uc3QgU29ydFR1cGxlICphLCBjb25zdCBTb3J0 VHVwbGUgKmIsCi0tIAoyLjUxLjAKCg== --000000000000a79dc30642b0a3f5 Content-Type: text/x-csrc; charset="US-ASCII"; name="test-ska-byte-sort-threshold.c" Content-Disposition: attachment; filename="test-ska-byte-sort-threshold.c" Content-Transfer-Encoding: base64 Content-ID: X-Attachment-Id: f_mhj5wc4s1 I2luY2x1ZGUgPHN0ZGRlZi5oPgojaW5jbHVkZSA8c3RkaW50Lmg+CiNpbmNsdWRlIDxzdGRpby5o PgojaW5jbHVkZSA8c3RkYm9vbC5oPgojaW5jbHVkZSA8c3RkbGliLmg+CiNpbmNsdWRlIDxzdHJp bmcuaD4KCiNpbmNsdWRlIDx4ODZpbnRyaW4uaD4KCi8qI2RlZmluZSBERUJVRzEqLwoKdHlwZWRl ZiB1aW50OF90IHVpbnQ4Owp0eXBlZGVmIHVpbnQ2NF90IHVpbnQ2NDsKdHlwZWRlZiB1aW50NjRf dCBEYXR1bTsKdHlwZWRlZiBpbnQ2NF90IGludDY0OwojZGVmaW5lIFNJWkVPRl9EQVRVTSA4CiNk ZWZpbmUgbGVuZ3Rob2YoYXJyYXkpIChzaXplb2YgKGFycmF5KSAvIHNpemVvZiAoKGFycmF5KVsw XSkpCiNkZWZpbmUgQXNzZXJ0KHgpCiNkZWZpbmUgQ3BwQ29uY2F0KHgsIHkpICAgICAgICAgICAg ICAgICB4IyN5CiNkZWZpbmUgQ0hFQ0tfRk9SX0lOVEVSUlVQVFMoKQojZGVmaW5lIE1pbih4LCB5 KQkJKCh4KSA8ICh5KSA/ICh4KSA6ICh5KSkKCiNpZiBkZWZpbmVkKF9fR05VQ19fKQojZGVmaW5l IHBnX25vaW5saW5lIF9fYXR0cmlidXRlX18oKG5vaW5saW5lKSkKLyogbXN2YyB2aWEgZGVjbHNw ZWMgKi8KI2VsaWYgZGVmaW5lZChfTVNDX1ZFUikKI2RlZmluZSBwZ19ub2lubGluZSBfX2RlY2xz cGVjKG5vaW5saW5lKQojZWxzZQojZGVmaW5lIHBnX25vaW5saW5lCiNlbmRpZgoKI2lmIGRlZmlu ZWQoX19HTlVDX18pICYmIGRlZmluZWQoX19PUFRJTUlaRV9fKQovKiBHQ0Mgc3VwcG9ydHMgYWx3 YXlzX2lubGluZSB2aWEgX19hdHRyaWJ1dGVfXyAqLwojZGVmaW5lIHBnX2F0dHJpYnV0ZV9hbHdh eXNfaW5saW5lIF9fYXR0cmlidXRlX18oKGFsd2F5c19pbmxpbmUpKSBpbmxpbmUKI2VsaWYgZGVm aW5lZChfTVNDX1ZFUikKLyogTVNWQyBoYXMgYSBzcGVjaWFsIGtleXdvcmQgZm9yIHRoaXMgKi8K I2RlZmluZSBwZ19hdHRyaWJ1dGVfYWx3YXlzX2lubGluZSBfX2ZvcmNlaW5saW5lCiNlbHNlCi8q IE90aGVyd2lzZSwgdGhlIGJlc3Qgd2UgY2FuIGRvIGlzIHRvIHNheSAiaW5saW5lIiAqLwojZGVm aW5lIHBnX2F0dHJpYnV0ZV9hbHdheXNfaW5saW5lIGlubGluZQojZW5kaWYKCgp0eXBlZGVmIHN0 cnVjdAp7Cgl2b2lkCSAgICp0dXBsZTsJCQkvKiB0aGUgdHVwbGUgaXRzZWxmICovCglEYXR1bQkJ ZGF0dW0xOwkJCS8qIHZhbHVlIG9mIGZpcnN0IGtleSBjb2x1bW4gKi8KCXVuaW9uCgl7CgkJc3Ry dWN0CgkJewoJCQlib29sCQlpc251bGwxOwkJLyogaXMgZmlyc3Qga2V5IGNvbHVtbiBOVUxMPyAq LwoJCQlpbnQJCQlzcmN0YXBlOwkJLyogc291cmNlIHRhcGUgbnVtYmVyICovCgkJfTsKCQlEYXR1 bQkJY29uZF9kYXR1bTE7Cgl9Owp9IFNvcnRUdXBsZTsKCgovKiBVc2VkIGZvciBjb25kaXRpb25l ZCBkYXR1bXMsIHNvIHdlIGNhbiBpZ25vcmUgTlVMTHMgYW5kIHNvcnQgZGlyZWN0aW9uLiAqLwpz dGF0aWMgcGdfYXR0cmlidXRlX2Fsd2F5c19pbmxpbmUgaW50CnFzb3J0X3R1cGxlX2NvbmRpdGlv bmVkX2NvbXBhcmUoU29ydFR1cGxlICphLCBTb3J0VHVwbGUgKmIpCnsKCWlmIChhLT5jb25kX2Rh dHVtMSA8IGItPmNvbmRfZGF0dW0xKQoJCXJldHVybiAtMTsKCWlmIChhLT5jb25kX2RhdHVtMSA+ IGItPmNvbmRfZGF0dW0xKQoJCXJldHVybiAxOwoKCS8qCgkgKiBObyBuZWVkIHRvIHdhc3RlIGVm Zm9ydCBjYWxsaW5nIHRoZSB0aWVicmVhayBmdW5jdGlvbiB3aGVuIHRoZXJlIGFyZSBubwoJICog b3RoZXIga2V5cyB0byBzb3J0IG9uLgoJICovCgkvL2lmIChzdGF0ZS0+YmFzZS5vbmx5S2V5ICE9 IE5VTEwpCgkJcmV0dXJuIDA7CgoJLy9yZXR1cm4gc3RhdGUtPmJhc2UuY29tcGFyZXR1cF90aWVi cmVhayhhLCBiLCBzdGF0ZSk7Cn0KCiNkZWZpbmUgU1RfU09SVCBxc29ydF90dXBsZV9jb25kaXRp b25lZAojZGVmaW5lIFNUX0VMRU1FTlRfVFlQRSBTb3J0VHVwbGUKI2RlZmluZSBTVF9DT01QQVJF KGEsIGIpIHFzb3J0X3R1cGxlX2NvbmRpdGlvbmVkX2NvbXBhcmUoYSwgYikKI2RlZmluZSBTVF9D SEVDS19GT1JfSU5URVJSVVBUUwojZGVmaW5lIFNUX1NDT1BFIHN0YXRpYwojZGVmaW5lIFNUX0RF RklORQojaW5jbHVkZSAibGliL3NvcnRfdGVtcGxhdGUuaCIKCgp0eXBlZGVmIHN0cnVjdCBQYXJ0 aXRpb25JbmZvCnsKICAgIHVuaW9uCiAgICB7CiAgICAgICAgc2l6ZV90IGNvdW50OwogICAgICAg IHNpemVfdCBvZmZzZXQ7CiAgICB9OwogICAgc2l6ZV90IG5leHRfb2Zmc2V0Owp9IFBhcnRpdGlv bkluZm87CgpzdGF0aWMgaW5saW5lIHVpbnQ4X3QKZXh0cmFjdF9rZXkoRGF0dW0ga2V5LCBpbnQg bGV2ZWwpCnsKCXJldHVybiAoa2V5ID4+ICgoKFNJWkVPRl9EQVRVTSAtIDEpIC0gbGV2ZWwpICog OCkpICYgMHhGRjsKfQoKc3RhdGljIGlubGluZSB2b2lkCnN3YXAoU29ydFR1cGxlICogYSwgU29y dFR1cGxlICogYikKewoJU29ydFR1cGxlIHRtcCA9ICphOwoKCSphID0gKmI7CgkqYiA9IHRtcDsK fQoKCnN0YXRpYyB2b2lkCnBnX25vaW5saW5lCnNrYV9ieXRlX3NvcnQoU29ydFR1cGxlICpiZWdp biwKCQkJICBTb3J0VHVwbGUgKmVuZCwgaW50IGxldmVsKQp7CgkvKiBzaXplX3QJCWNvdW50czBb MjU2XSA9IHswfTsgKi8KCXNpemVfdAkJY291bnRzMVsyNTZdID0gezB9OwoJc2l6ZV90CQljb3Vu dHMyWzI1Nl0gPSB7MH07CglzaXplX3QJCWNvdW50czNbMjU2XSA9IHswfTsKCVBhcnRpdGlvbklu Zm8gcGFydGl0aW9uc1syNTZdID0gezB9OwoJdWludDhfdAkJcmVtYWluaW5nX3BhcnRpdGlvbnNb MjU2XSA9IHswfTsKCXNpemVfdAkJdG90YWwgPSAwOwoJaW50CQkJbnVtX3BhcnRpdGlvbnMgPSAw OwoJaW50CQkJbnVtX3JlbWFpbmluZzsKCVNvcnRUdXBsZSAgKmN0dXA7CgoJLyogY291bnQga2V5 IGNodW5rcywgdW5yb2xsZWQgZm9yIHNwZWVkICovCgoJZm9yIChjdHVwID0gYmVnaW47IGN0dXAg KyA0IDwgZW5kOyBjdHVwICs9IDQpCgl7CgkJdWludDgJCWtleV9jaHVuazAgPSBleHRyYWN0X2tl eSgoY3R1cCArIDApLT5jb25kX2RhdHVtMSwgbGV2ZWwpOwoJCXVpbnQ4CQlrZXlfY2h1bmsxID0g ZXh0cmFjdF9rZXkoKGN0dXAgKyAxKS0+Y29uZF9kYXR1bTEsIGxldmVsKTsKCQl1aW50OAkJa2V5 X2NodW5rMiA9IGV4dHJhY3Rfa2V5KChjdHVwICsgMiktPmNvbmRfZGF0dW0xLCBsZXZlbCk7CgkJ dWludDgJCWtleV9jaHVuazMgPSBleHRyYWN0X2tleSgoY3R1cCArIDMpLT5jb25kX2RhdHVtMSwg bGV2ZWwpOwoKCQlwYXJ0aXRpb25zW2tleV9jaHVuazBdLmNvdW50Kys7CgkJY291bnRzMVtrZXlf Y2h1bmsxXSsrOwoJCWNvdW50czJba2V5X2NodW5rMl0rKzsKCQljb3VudHMzW2tleV9jaHVuazNd Kys7CgoJfQoKCWZvciAoc2l6ZV90IGkgPSAwOyBpIDwgMjU2OyBpKyspCgkJcGFydGl0aW9uc1tp XS5jb3VudCArPSBjb3VudHMxW2ldICsgY291bnRzMltpXSArIGNvdW50czNbaV07CgoJZm9yICg7 IGN0dXAgPCBlbmQ7IGN0dXArKykKCXsKCQl1aW50OAkJa2V5X2NodW5rOwoKCQlrZXlfY2h1bmsg PSBleHRyYWN0X2tleShjdHVwLT5jb25kX2RhdHVtMSwgbGV2ZWwpOwoJCXBhcnRpdGlvbnNba2V5 X2NodW5rXS5jb3VudCsrOwoJfQoKCS8qIGNvbXB1dGUgcGFydGl0aW9uIG9mZnNldHMgKi8KCWZv ciAoaW50IGkgPSAwOyBpIDwgMjU2OyArK2kpCgl7CgkJc2l6ZV90CQljb3VudCA9IHBhcnRpdGlv bnNbaV0uY291bnQ7CgoJCWlmIChjb3VudCkKCQl7CgkJCXBhcnRpdGlvbnNbaV0ub2Zmc2V0ID0g dG90YWw7CgkJCXRvdGFsICs9IGNvdW50OwoJCQlyZW1haW5pbmdfcGFydGl0aW9uc1tudW1fcGFy dGl0aW9uc10gPSBpOwoJCQkrK251bV9wYXJ0aXRpb25zOwoJCX0KCQlwYXJ0aXRpb25zW2ldLm5l eHRfb2Zmc2V0ID0gdG90YWw7Cgl9CgoJbnVtX3JlbWFpbmluZyA9IG51bV9wYXJ0aXRpb25zOwoK CS8qCgkgKiBQZXJtdXRlIHR1cGxlcyB0byBjb3JyZWN0IHBhcnRpdGlvbi4gSWYgd2Ugc3RhcnRl ZCB3aXRoIG9uZSBwYXJ0aXRpb24sCgkgKiB0aGVyZSBpcyBub3RoaW5nIHRvIGRvLiBJZiBhIHBl cm11dGF0aW9uIGZyb20gYSBwcmV2aW91cyBpdGVyYXRpb24KCSAqIHJlc3VsdHMgaW4gYSBzaW5n bGUgcGFydGl0aW9uIHRoYXQgaGFzbid0IGJlZW4gbWFya2VkIGFzIHNvcnRlZCwgd2UKCSAqIGtu b3cgaXQncyBhY3R1YWxseSBzb3J0ZWQuCgkgKi8KCXdoaWxlIChudW1fcmVtYWluaW5nID4gMSkK CXsKCQkvKgoJCSAqIFdlIGNhbiBvbmx5IGV4aXQgdGhlIGxvb3Agd2hlbiBhbGwgcGFydGl0aW9u cyBhcmUgc29ydGVkLCBzbyBtdXN0CgkJICogcmVzZXQgZXZlcnkgaXRlcmF0aW9uCgkJICovCgkJ bnVtX3JlbWFpbmluZyA9IG51bV9wYXJ0aXRpb25zOwoKCQlmb3IgKGludCBpID0gMDsgaSA8IG51 bV9wYXJ0aXRpb25zOyBpKyspCgkJewoJCQl1aW50OAkJaWR4ID0gcmVtYWluaW5nX3BhcnRpdGlv bnNbaV07CgoJCQlQYXJ0aXRpb25JbmZvIHBhcnQgPSBwYXJ0aXRpb25zW2lkeF07CgoJCQlmb3Ig KFNvcnRUdXBsZSAqc3QgPSBiZWdpbiArIHBhcnQub2Zmc2V0OwoJCQkJIHN0IDwgYmVnaW4gKyBw YXJ0Lm5leHRfb2Zmc2V0OwoJCQkJIHN0KyspCgkJCXsKCQkJCXVpbnQ4CQl0aGlzX3BhcnRpdGlv biA9IGV4dHJhY3Rfa2V5KHN0LT5jb25kX2RhdHVtMSwgbGV2ZWwpOwoJCQkJc2l6ZV90CQlvZmZz ZXQgPSBwYXJ0aXRpb25zW3RoaXNfcGFydGl0aW9uXS5vZmZzZXQrKzsKCgkJCQlBc3NlcnQoYmVn aW4gKyBvZmZzZXQgPCBlbmQpOwoJCQkJc3dhcChzdCwgYmVnaW4gKyBvZmZzZXQpOwoJCQl9OwoK CQkJaWYgKHBhcnQub2Zmc2V0ID09IHBhcnQubmV4dF9vZmZzZXQpCgkJCXsKCQkJCS8qIHBhcnRp dGlvbiBpcyBzb3J0ZWQ7IHNraXAgKi8KCQkJCW51bV9yZW1haW5pbmctLTsKCQkJfQoJCX0KCX0K CS8qIG5vIHJlY3Vyc2lvbiAqLwp9CgoKCmludAptYWluICgpCnsKCXVpbnQ2NF90IHN0YXJ0OwoJ dWludDY0X3QgZmluaXNoOwoJZG91YmxlIHF0aWNrczsKCWRvdWJsZSBydGlja3M7CiNkZWZpbmUg Q09VTlQgODAwMAoJaW50IGxlbmd0aHNbXSA9IHsgMTAwLCAyMDAsIDQwMCwgODAwLCAxNjAwLCAz MjAwLCA2NDAwIH07CglTb3J0VHVwbGUgKnN0ID0gbWFsbG9jKENPVU5UICogc2l6ZW9mKFNvcnRU dXBsZSkpOwoJU29ydFR1cGxlICp0ZXN0X3JhZGl4ID0gbWFsbG9jKENPVU5UICogc2l6ZW9mKFNv cnRUdXBsZSkpOwoJU29ydFR1cGxlICp0ZXN0X3Fzb3J0ID0gbWFsbG9jKENPVU5UICogc2l6ZW9m KFNvcnRUdXBsZSkpOwoKLy8gMjU2IG9yIGxlc3Mgc28gdGhhdCBhbGwgZW50cm9weSBpcyBpbiBh IHNpbmdsZSBieXRlCiNkZWZpbmUgQ0FSRElOQUxJVFkgMjU2CglwcmludGYoImNhcmRpbmFsaXR5 OiAlZFxuIiwgQ0FSRElOQUxJVFkpOwoJZm9yIChpbnQgaT0wOyBpPENPVU5UOyBpKyspCgl7CgkJ Ly8gb25seSBsb3dlc3QgYnl0ZSBpcyBwb3B1bGF0ZWQKCQlpbnQ2NCB2YWwgPSByYW5kb20oKSAl IENBUkRJTkFMSVRZOwoJCVNvcnRUdXBsZSB4ID0geyAuY29uZF9kYXR1bTEgPSB2YWwgfTsKCQlz dFtpXSA9IHg7Cgl9CgoJZm9yIChpbnQgaj0wOyBqPCBsZW5ndGhvZihsZW5ndGhzKTsgaisrKQoJ ewoJCWludCBsZW4gPSBsZW5ndGhzW2pdOwoJCXF0aWNrcyA9IHJ0aWNrcyA9IDA7CgoJCXByaW50 ZigibnVtYmVyIG9mIGVsZW1lbnRzOiAlNGQgICAiLCBsZW4pOwoKI2RlZmluZSBOVU1fTUVBU1VS RU1FTlRTIDEwMDAwMDAKCQlmb3IgKGludCBrPTA7IGs8TlVNX01FQVNVUkVNRU5UUzsgaysrKQoJ CXsKCQkJLy8gcmVwb3B1bGF0ZSB0ZXN0CgkJCW1lbWNweSh0ZXN0X3Fzb3J0LCBzdCwgbGVuICog c2l6ZW9mKFNvcnRUdXBsZSkpOwoKCQkJc3RhcnQgPSBfX3JkdHNjKCk7CgkJCS8vIG9ubHkgc29y dCBsb3dlc3QgYnl0ZQoJCQlxc29ydF90dXBsZV9jb25kaXRpb25lZCh0ZXN0X3Fzb3J0LCBsZW4p OwoJCQlmaW5pc2ggPSBfX3JkdHNjKCk7CgkJCXF0aWNrcyArPSBmaW5pc2ggLSBzdGFydDsKCgkJ CW1lbWNweSh0ZXN0X3JhZGl4LCBzdCwgbGVuICogc2l6ZW9mKFNvcnRUdXBsZSkpOwoKI2lmZGVm IERFQlVHMQoJCQlwcmludGYoImJlZm9yZTpcbiIpOwoJCQlmb3IgKGludCBpPTA7IGk8bGVuOyBp KyspCgkJCQlwcmludGYoIiVsZFxuIiwgdGVzdF9yYWRpeFtpXS5jb25kX2RhdHVtMSk7CiNlbmRp ZgoKCQkJc3RhcnQgPSBfX3JkdHNjKCk7CgkJCS8vIG9ubHkgc29ydCBsb3dlc3QgYnl0ZQoJCQlz a2FfYnl0ZV9zb3J0KHRlc3RfcmFkaXgsIHRlc3RfcmFkaXggKyBsZW4sIDcpOwoJCQlmaW5pc2gg PSBfX3JkdHNjKCk7CgkJCXJ0aWNrcyArPSBmaW5pc2ggLSBzdGFydDsKCQl9CgoJCXByaW50Zigi cXNvcnQ6ICUwNC4xZiByYWRpeDogJTA0LjFmXG4iLCBxdGlja3MgLyBOVU1fTUVBU1VSRU1FTlRT IC8gbGVuLAoJCQkJCQkJCQkJCXJ0aWNrcyAvIE5VTV9NRUFTVVJFTUVOVFMgLyBsZW4pOwoKI2lm ZGVmIERFQlVHMQoJCQlwcmludGYoImFmdGVyOlxuIik7CgkJCWZvciAoaW50IGk9MDsgaTxsZW47 IGkrKykKCQkJCXByaW50ZigiJWxkXG4iLCB0ZXN0X3JhZGl4W2ldLmNvbmRfZGF0dW0xKTsKI2Vu ZGlmCgl9Cgp9Cg== --000000000000a79dc30642b0a3f5--