Peres randomness extractor

peres.js

/**
 * Peres extractor as described in http://dx.doi.org/10.1214/aos/1176348543
 * @param {Array} bits - an array of biased bits to debias
 * @param {Array} extracted - an array of extracted, unbiased bits
 * @returns {Array} - an array of exatracted, unbiased bits
 */
function peres(bits, extracted) {
  const u = [];  // discarded bits Psi(u1, u2, u3, ...)
  const v = [];  // discarded bits Psi(v1, v2, v3, ...)
  const l = bits.length - (bits.length & 1); // ensure an even length, dropping the last bit if odd

  if (l === 0) return;

  for (let i = 0; i < l; i += 2) {
    u.push(bits[i] ^ bits[i + 1]);
    if (bits[i] != bits[i + 1]) extracted.push(bits[i]); // standard von neumann extractor
    else v.push(bits[i]);
  }

  // Concatenation order is Psi(x) || Psi(u1, ...) || Psi(v1, ...)
  peres(u, extracted); // Recursion over Psi(u1, ...) first
  peres(v, extracted); // Then recursion over Psi(v1, ...)

  return extracted;
}