<commit_before>#include "clustering/administration/tables/split_points.hpp"

#include "clustering/administration/real_reql_cluster_interface.hpp"
#include "math.hpp"   /* for `clamp()` */
#include "rdb_protocol/real_table.hpp"

/* `interpolate_key()` produces a `store_key_t` that is interpolated between `in1` and
`in2`. For example, if `fraction` is 0.50, the return value will be halfway between `in1`
and `in2`; if it's 0.25, the return value will be closer to `in1`; and so on. This
function is not exact; the only absolute guarantee it provides is that the return value
will lie in the range `in1 <= out <= in2`. */
static store_key_t interpolate_key(store_key_t in1, store_key_t in2, double fraction) {
    rassert(in1 <= in2);
    rassert(fraction >= 0 && fraction <= 1);
    const uint8_t *in1_buf = in1.contents(), *in2_buf = in2.contents();
    uint8_t out_buf[MAX_KEY_SIZE];

    /* Calculate the shared prefix of `in1` and `in2` */
    size_t i = 0;
    while (i < static_cast<size_t>(in1.size()) &&
           i < static_cast<size_t>(in2.size()) &&
           in1_buf[i] == in2_buf[i]) {
        out_buf[i] = in1_buf[i];
        ++i;
    }

    /* Convert the first non-shared parts of `in1` and `in2` into integers so we can do
    arithmetic on them. If `in1` or `in2` terminates early, pad it with zeroes. This
    isn't perfect but the error doesn't matter for our purposes. */
    uint32_t in1_tail = 0, in2_tail = 0;
    static const size_t num_interp = 4;
    rassert(sizeof(in1_tail) >= num_interp);
    for (size_t j = i; j < i + num_interp; ++j) {
        uint8_t c1 = j < static_cast<size_t>(in1.size()) ? in1_buf[j] : 0;
        uint8_t c2 = j < static_cast<size_t>(in2.size()) ? in2_buf[j] : 0;
        in1_tail = (in1_tail << 8) + c1;
        in2_tail = (in2_tail << 8) + c2;
    }
    rassert(in1_tail <= in2_tail);

    /* Compute an integer representation of the interpolated value */
    uint32_t out_tail = in1_tail*(1-fraction) + in2_tail*fraction;

    /* Append the interpolated value onto `out_buf` */
    for (size_t k = 0; k < num_interp; ++k) {
        uint8_t c = (out_tail >> (8 * (num_interp - k))) & 0xFF;
        if (i + k < MAX_KEY_SIZE) {
            out_buf[i + k] = c;
        }
    }

    /* Construct the final result */
    store_key_t out(
        std::min(i + num_interp, static_cast<size_t>(MAX_KEY_SIZE)),
        out_buf);

    /* For various reasons (rounding errors, corner cases involving keys very close
    together, etc.), it's possible that the above procedure will produce an `out` that is
    not between `in1` and `in2`. Rather than trying to interpolate properly in these
    complicated cases, we just clamp the result. */
    out = clamp(out, in1, in2);

    return out;
}

/* `ensure_distinct()` ensures that all of the `store_key_t`s in the given vector are<commit_msg>fixing error in key interpolation<commit_after>#include "clustering/administration/tables/split_points.hpp"

#include "clustering/administration/real_reql_cluster_interface.hpp"
#include "math.hpp"   /* for `clamp()` */
#include "rdb_protocol/real_table.hpp"

/* `interpolate_key()` produces a `store_key_t` that is interpolated between `in1` and
`in2`. For example, if `fraction` is 0.50, the return value will be halfway between `in1`
and `in2`; if it's 0.25, the return value will be closer to `in1`; and so on. This
function is not exact; the only absolute guarantee it provides is that the return value
will lie in the range `in1 <= out <= in2`. */
static store_key_t interpolate_key(store_key_t in1, store_key_t in2, double fraction) {
    rassert(in1 <= in2);
    rassert(fraction >= 0 && fraction <= 1);
    const uint8_t *in1_buf = in1.contents(), *in2_buf = in2.contents();
    uint8_t out_buf[MAX_KEY_SIZE];

    /* Calculate the shared prefix of `in1` and `in2` */
    size_t i = 0;
    while (i < static_cast<size_t>(in1.size()) &&
           i < static_cast<size_t>(in2.size()) &&
           in1_buf[i] == in2_buf[i]) {
        out_buf[i] = in1_buf[i];
        ++i;
    }

    /* Convert the first non-shared parts of `in1` and `in2` into integers so we can do
    arithmetic on them. If `in1` or `in2` terminates early, pad it with zeroes. This
    isn't perfect but the error doesn't matter for our purposes. */
    uint32_t in1_tail = 0, in2_tail = 0;
    for (size_t j = i; j < i + sizeof(in1_tail); ++j) {
        uint8_t c1 = j < static_cast<size_t>(in1.size()) ? in1_buf[j] : 0;
        uint8_t c2 = j < static_cast<size_t>(in2.size()) ? in2_buf[j] : 0;
        in1_tail = (in1_tail << 8) + c1;
        in2_tail = (in2_tail << 8) + c2;
    }
    rassert(in1_tail <= in2_tail);

    /* Compute an integer representation of the interpolated value */
    uint32_t out_tail = in1_tail * (1 - fraction) + in2_tail * fraction;

    /* Append the interpolated value onto `out_buf`, discarding trailing null bytes */
    size_t num_interp = 0;
    while (num_interp < sizeof(out_tail) && out_tail != 0 && i + num_interp < MAX_KEY_SIZE) {
        out_buf[i + num_interp] = (out_tail >> 24) & 0xFF;
        ++num_interp;
        out_tail <<= 8;
    }

    /* Construct the final result */
    store_key_t out(i + num_interp, out_buf);

    /* For various reasons (rounding errors, corner cases involving keys very close
    together, etc.), it's possible that the above procedure will produce an `out` that is
    not between `in1` and `in2`. Rather than trying to interpolate properly in these
    complicated cases, we just clamp the result. */
    out = clamp(out, in1, in2);

    return out;
}

/* `ensure_distinct()` ensures that all of the `store_key_t`s in the given vector are
{'fraction_non_alphanumeric': 0.12224982256919802, 'fraction_numerical': 0.02785663591199432, 'mean_word_length': 3.1817507418397626, 'pattern_counts': {'":': 0, '<': 46, '<?xml version=': 0, '>': 19, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1366121', 'n_tokens_mistral': 2045, 'n_tokens_neox': 1946, 'n_words': 621}