# Keys That Aren't Plain Integers

*Task 6 of 6 · [Radix Sort](https://gpu.rocks/learn/radix-sort-fd3ff796.md) · GPU.js Learn*

The sort has a requirement it never had to say out loud: the key must be a
**non-negative integer**, because `Math.floor(key / place) % 16`
is only a digit for those. Hand it `−5` and the "digit" is `−5`,
`starts[−5]` is off the front of the bucket table, and the pass returns junk.

Signed integers have a clean fix that costs one map each way: **bias**
them. Add 2,048 and the range −2048…2047 becomes 0…4095 — same order, all non-negative.
Sort, then subtract the 2,048 back off. Production libraries call this step encoding the
key, and the rule is the only one that matters: any order-preserving, invertible map into
the unsigned integers makes radix sort work on your type.

Floats are the same idea and a harder map — and this is where gpu.js stops. A float's
ordering *is* its bit pattern's ordering, for positives; IEEE-754 negatives carry a
sign bit on top and sort backwards under an unsigned comparison, so real implementations
reinterpret the 32 bits and flip them (`x ^ 0x80000000` for a positive,
`~x` for a negative) before sorting and flip back after. gpu.js does have
`&`, `|`, `^`, `<<` and
`>>` inside kernels, but the WebGL backend emulates them with GLSL integer
loops and they part company with JavaScript the moment an operand goes negative
(`-8 & 15` is 8 in JavaScript and on the CPU backend, and 0 on WebGL). More
to the point, there is no way to *see* a float's bits at all: GLSL ES 1.00 has no
`floatBitsToInt` and gpu.js exposes none, so `key & 15` truncates
the value to an integer first — `3.5 & 15` is 3, the number's integer part,
never its bit pattern. This course therefore sorts non-negative integer keys, and signed
ones through the bias below; a CUDA or WebGPU implementation runs the same six kernels with
a bit-flipping encoder in front.

## Goal

**Goal:** sort `readings`, which run from −2048 to 2047, by
biasing them into non-negative integers, sorting, and taking the bias back off.

## Requirements

- `encode` adds `this.constants.bias` to every reading
- `decode` subtracts it again
- Run the given `radixSort` on the *encoded* values, and decode the result
- `console.log` the sorted readings' smallest and largest values

## Hint 1 — the two maps

Both kernels are one-line maps over their own cell — one adds
`this.constants.bias`, the other subtracts it. Nothing about the sort
changes.

## Hint 2 — the wiring

```js
const sorted = await decode(await radixSort(await encode(readings)));
```

Encode on the way in, decode on the way out. Miss the decode and every value
comes back 2,048 too high; miss the encode and the negative keys index off the front
of the bucket table.

## Same idea elsewhere

Every serious sorting library has this seam. CUB twiddles a key's bits in and out
around the sort so that floats, signed integers and custom types all reduce to unsigned
digits; rocPRIM and Thrust do the same, and newer CUB versions let you hand it a
*decomposer* for your own struct. The sort never changes — only the map into
unsigned integers does.

## Starter code

```js
// The sort below is finished. It only accepts non-negative integer keys.
const gpu = new GPU({ mode });

const encode = gpu.createKernel(function (v) {
  // TODO: shift every reading up so the smallest one becomes 0
  return v[this.thread.x];
}, { output: [256], constants: { bias: 2048 } });

const decode = gpu.createKernel(function (v) {
  // TODO: undo the shift
  return v[this.thread.x];
}, { output: [256], constants: { bias: 2048 } });

const histogram = gpu.createKernel(function (keys, place) {
  let count = 0;
  for (let i = 0; i < this.constants.n; i++) {
    const d = Math.floor(keys[i] / place) % this.constants.radix;
    if (d === this.thread.x) {
      count++;
    }
  }
  return count;
}, { output: [16], constants: { n: 256, radix: 16 } });

const offsets = gpu.createKernel(function (counts) {
  let start = 0;
  for (let b = 0; b < this.constants.radix; b++) {
    if (b < this.thread.x) {
      start += counts[b];
    }
  }
  return start;
}, { output: [16], constants: { radix: 16 } });

const destinations = gpu.createKernel(function (keys, place, starts) {
  const mine = Math.floor(keys[this.thread.x] / place) % this.constants.radix;
  let rank = 0;
  for (let j = 0; j < this.constants.n; j++) {
    const d = Math.floor(keys[j] / place) % this.constants.radix;
    if (d === mine && j < this.thread.x) {
      rank++;
    }
  }
  return starts[mine] + rank;
}, { output: [256], constants: { n: 256, radix: 16 } });

const gather = gpu.createKernel(function (keys, dest) {
  let value = 0;
  for (let i = 0; i < this.constants.n; i++) {
    if (dest[i] === this.thread.x) {
      value = keys[i];
    }
  }
  return value;
}, { output: [256], constants: { n: 256 } });

async function radixSort(values) {
  // gpu.js locks an argument's type on a kernel's first call, and every pass
  // feeds one kernel's output into the next — so the chain starts as a
  // Float32Array whatever it was handed. Each stage is awaited before the
  // next reads it: the passes are a chain, not a set.
  let v = Float32Array.from(values);
  for (let place = 1; place <= 256; place *= 16) {
    const counts = await histogram(v, place);
    const starts = await offsets(counts);
    const dest = await destinations(v, place, starts);
    v = await gather(v, dest);
  }
  return v;
}

// TODO: bias the readings on the way in, and take the bias off on the way out.
const sorted = await radixSort(readings);
console.log('smallest:', sorted[0], '| largest:', sorted[255]);
```

---

Interactive version: https://gpu.rocks/learn/radix-sort-fd3ff796/6

[Previous task](https://gpu.rocks/learn/radix-sort-fd3ff796/5.md)