--tThc/1wpZn/ma/RB Content-Type: text/plain; charset=us-ascii Content-Disposition: inline
Sorry for the delay in submitting the patch. I wanted to double-check that no third party would lay a credible claim to it.
For good measure, I have split the patch in two: the first only addresses the primary issue, and is obviously too simple to be copyrightable. The second addresses the need for falling back to straight Fisher-Yates in the middle of the shuffle, and may or may not be copyrightable so I'll say this:
The attached patch files are derived from OpenLDAP Software. All of the modifications to OpenLDAP Software represented therein were developed by me, Sergio Gelato. I have not assigned rights and/or interest in this work to any party. The modifications are subject to the following notice:
Copyright 2015 Sergio Gelato Redistribution and use in source and binary forms, with or without modification, are permitted according to the terms of the OpenLDAP Public License.
--tThc/1wpZn/ma/RB Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="0001-Remove-bias-towards-the-first-record-in-RFC2782-shuf.patch"
From adb64c957308e5aee08a2f8aa893992a262d3243 Mon Sep 17 00:00:00 2001
From: Sergio Gelato Sergio.Gelato@astro.su.se Date: Sun, 6 Dec 2015 12:57:46 +0100 Subject: [PATCH 1/2] Remove bias towards the first record in RFC2782 shuffle implementation.
Prior to this change, given two records of weight 1 the algorithm would return them in the order (0,1) with 100% probability instead of the desired 50%. This was due to an off-by-one error in the range test.
srv_rand() returns a float in the range [0.0, 1.0[, so r is an integer in the range [0, total[. The correct probability for record 0 to be chosen is a[0].weight/total, not (a[0].weight+1)/total. --- libraries/libldap/dnssrv.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/libraries/libldap/dnssrv.c b/libraries/libldap/dnssrv.c index da89b4a..8d30552 100644 --- a/libraries/libldap/dnssrv.c +++ b/libraries/libldap/dnssrv.c @@ -234,7 +234,7 @@ static void srv_shuffle(srv_record *a, int n) { r = srv_rand() * total; for (j=0; j<p; j++) { r -= a[j].weight; - if (r <= 0) { + if (r < 0) { if (j) { srv_record t = a[0]; a[0] = a[j];