1 files changed, 101 insertions, 0 deletions
diff --git a/src/lib/dhcpsrv/ip_range_permutation.cc b/src/lib/dhcpsrv/ip_range_permutation.cc
new file mode 100644
index 0000000..8785e54
--- /dev/null
+++ b/src/lib/dhcpsrv/ip_range_permutation.cc
@@ -0,0 +1,101 @@
+// Copyright (C) 2020 Internet Systems Consortium, Inc. ("ISC")
+//
+// This Source Code Form is subject to the terms of the Mozilla Public
+// License, v. 2.0. If a copy of the MPL was not distributed with this
+// file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+#include <config.h>
+#include <asiolink/addr_utilities.h>
+#include <dhcpsrv/ip_range_permutation.h>
+
+#include <iostream>
+
+using namespace isc::asiolink;
+
+namespace isc {
+namespace dhcp {
+
+IPRangePermutation::IPRangePermutation(const AddressRange& range)
+    : range_start_(range.start_), step_(1), cursor_(addrsInRange(range_start_, range.end_) - 1),
+      state_(), done_(false), generator_() {
+    std::random_device rd;
+    generator_.seed(rd());
+}
+
+IPRangePermutation::IPRangePermutation(const PrefixRange& range)
+    : range_start_(range.start_), step_(static_cast<uint64_t>(1) << (128 - range.delegated_length_)),
+      cursor_(prefixesInRange(range.prefix_length_, range.delegated_length_) - 1),
+      state_(), done_(false), generator_() {
+}
+
+IOAddress
+IPRangePermutation::next(bool& done) {
+    // If we're done iterating over the pool let's return zero address and
+    // set the user supplied done flag to true.
+    if (done_) {
+        done = true;
+        return (range_start_.isV4() ? IOAddress::IPV4_ZERO_ADDRESS() : IOAddress::IPV6_ZERO_ADDRESS());
+    }
+
+    // If there is one address left, return this address.
+    if (cursor_ == 0) {
+        done = done_ = true;
+        return (state_.at(0));
+    }
+
+    // We're not done.
+    done = false;
+
+    // The cursor indicates where we're in the range starting from its end. The
+    // addresses between the cursor and the end of the range have been already
+    // returned by this function. Therefore we focus on the remaining cursor-1
+    // addresses. Let's get random address from this sub-range.
+    std::uniform_int_distribution<int> dist(0, cursor_ - 1);
+    auto next_loc = dist(generator_);
+
+    IOAddress next_loc_address = IOAddress::IPV4_ZERO_ADDRESS();
+
+    // Check whether this address exists in our map or not. If it exists
+    // it means it was swapped with some other address in previous calls to
+    // this function.
+    auto next_loc_existing = state_.find(next_loc);
+    if (next_loc_existing != state_.end()) {
+        // Address exists, so let's record it.
+        next_loc_address = next_loc_existing->second;
+    } else {
+        // Address does not exist on this position. We infer this address from
+        // its position by advancing the range start by position. For example,
+        // if the range is 192.0.2.1-192.0.2.10 and the picked random position is
+        // 5, the address we get is 192.0.2.6. This random address will be later
+        // returned to the caller.
+        next_loc_address = offsetAddress(range_start_, next_loc * step_);
+    }
+
+    // Let's get the address at cursor position in the same way.
+    IOAddress cursor_address = IOAddress::IPV4_ZERO_ADDRESS();
+    auto cursor_existing = state_.find(cursor_);
+    if (cursor_existing != state_.end()) {
+        cursor_address = cursor_existing->second;
+    } else {
+        cursor_address = offsetAddress(range_start_, cursor_ * step_);
+    }
+
+    // Now we swap them.... in fact we don't swap because as an optimization
+    // we don't record the addresses we returned by this function. We merely
+    // replace the address at random position with the address from cursor
+    // position. This address will be returned in the future if we get back
+    // to this position as a result of randomization.
+    if (next_loc_existing == state_.end()) {
+        state_.insert(std::make_pair(next_loc, cursor_address));
+    } else {
+        state_.at(next_loc) = cursor_address;
+    }
+    // Move the cursor one position backwards.
+    --cursor_;
+
+    // Return the address from the random position.
+    return (next_loc_address);
+}
+
+} // end of namespace isc::dhcp
+} // end of namespace isc