jumphost.k

/ jumphost https://arxiv.org/pdf/1406.2294.pdf
/ usage: jh[k;n]
/ k: 64-bit key; n: num_buckets
/ Targeting the K6 and K8 dialects. Tested with ngn/k and shakti 2021.07.10
rsh:{$[x<0;1073741823+_(x-9223372036854775808)%8589934592;_x%8589934592]}
jhr:{[b;j;k;n] b:j;k:1+k*2862933555777941757;j:_(b+1)*2147483648%1+rsh[k]; $[j<n;jhr[b;j;k;n];b]}
jh:jhr[-1;0]

/ k doesn't have unsigned integers nor does have bitshifts
/ the rsh function shifts right by dividing after manually clearing the MSB
/ if the number is negative and setting it back after the divide.
/ This is necessary on K9 (shakti) since the decode operation (`2\`) works only on the first 32 bits of the integer.
/ Also, we're using recursion instead of while because while is broken on K9

wdemo.k

  "/dev/stdout" 0:""/'-4$$(+(1+!14)),+({x@y}'({jh[x]}'(123+!5)))'1+!14
   1   2   3   4   5   6   7   8   9  10  11  12  13  14
   0   0   0   0   0   0   0   0   0   0   0  11  11  11
   0   0   0   0   4   4   4   4   4   4  10  10  10  10
   0   0   2   2   4   4   4   4   8   8   8   8   8  13
   0   1   2   2   2   5   5   5   5   5   5   5   5   5
   0   1   1   1   1   1   1   1   1   9   9   9   9   9

zdemo.c

// outputs:
//   1   2   3   4   5   6   7   8   9  10  11  12  13  14
//   0   0   0   0   0   0   0   0   0   0   0  11  11  11
//   0   0   0   0   4   4   4   4   4   4  10  10  10  10
//   0   0   2   2   4   4   4   4   8   8   8   8   8  13
//   0   1   2   2   2   5   5   5   5   5   5   5   5   5
//   0   1   1   1   1   1   1   1   1   9   9   9   9   9

#include <stdint.h>
#include <stdio.h>

int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
  int64_t b = -1, j = 0;
  while (j < num_buckets) {
    b = j;
    key = key * 2862933555777941757ULL + 1;
    j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
  }
  return b;
}

int main() {
  uint64_t key = 123;
  for (int i = 1; i <= 14; i++) {
    printf("%4d", i);
  }
  printf("\n");
  for (int j = 0; j < 5; j++) {
    for (int i = 1; i <= 14; i++) {
      printf("%4d", JumpConsistentHash(key + j, i));
    }
    printf("\n");
  }
}