import 'babel-polyfill'
import LFSR from './lfsr'

/**
 * A Fibonacci implementation of a linear feedback shift register (LFSR).
 *
 * @class
 * @augments LFSR
 *
 * @example <caption>A 3-tap m-sequence (maximum-length sequence)</caption>
 * var size = 3
 * var lfsr = new FibonacciLFSR(size, [size, 2])
 * console.log(lfsr.current_state, lfsr.current_state.toString(2))
 * //=> 1, "1"
 *
 * for (var n = 1; n <= lfsr.maximum_sequence_length; n++) {
 *   var bit = lfsr.next()
 *
 *   console.log(bit, bit.toString(2))
 * }
 * //=> 0, "0"
 * //=> 0, "0"
 * //=> 1, "1"
 * //=> 0, "0"
 * //=> 1, "1"
 * //=> 1, "1"
 * //=> 1, "1"
 *
 * @see https://en.wikipedia.org/wiki/Linear_feedback_shift_register
 * @see http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr.htm
 */
class FibonacciLFSR extends LFSR {
  /**
   * Generate the next state in the sequence.
   *
   * @returns {number} The output bit.
   * @override
   *
   * @example
   * XXX
   */
  next() {
    let state = this.current_state

    // The input bit is the binary sum (XOR) of the feedback taps' values.
    //
    // It looks odd to use just `active_tapped_bits` as the predicate with no
    // comparisons, but it means the loop will exit as soon as
    // `active_tapped_bits` is bit shifted to be all `0`s. If there are only a
    // few taps, set early in the mask, this skips a lot of useless iteration.
    //
    // @see http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan
    let active_tapped_bits = state & this.feedback_tap_mask
    let active_bit_count = 0
    for (; active_tapped_bits; active_bit_count++) {
      active_tapped_bits &= active_tapped_bits - 1
    }
    let input_bit = active_bit_count % 2

    // Drop previous output bit.
    state >>= 1
    // Prepend the input bit.
    //
    // @note `-1` because the input bit takes up a slot.
    state |= (input_bit << (this.m - 1))

    this.current_state = state

    return state & 1
  }

  /**
   * Validate and process feedback tap indices.
   *
   * @type {number[]}
   * @override
   * @protected
   * @static
   */
  get sanitized_feedback_taps() {
    const taps = super.sanitized_feedback_taps

    // Fibonacci LFSRs always use the last tap (`tap_j = m`). It will be
    // manually added in as part of setting the tap mask.
    const adjusted = taps.filter((tap_j) => tap_j < this.m).
      map((tap_j) => this.m - (tap_j - 1))
    adjusted.push(1)

    return adjusted
  }
}

export default FibonacciLFSR

@@ -978,17 +978,682 @@
 mple
-%0A   * XXX
+ %3Ccaption%3EHow the next state is calculated%3C/caption%3E%0A   *   var lfsr = new FibonacciLFSR(3, %5B3, 1%5D, 4)%0A   *   var state = lfsr.current_state // 4%0A   *   //=%3E 0b100%0A   *   var active_tapped_bits = state & this.feedback_tap_mask%0A   *   // = 0b100 & 0b101%0A   *   // = 4%0A   *   //=%3E 0b100%0A   *   var active_bit_count = 0%0A   *   for (; active_tapped_bits; active_bit_count++) %7B%0A   *     active_tapped_bits &= active_tapped_bits - 1%0A   *   %7D%0A   *   var input_bit = active_bit_count %25 2%0A   *   // = 1 %25 2%0A   *   //=%3E 1%0A   *   state %3E%3E= 1 // 2%0A   *   //=%3E 0b010%0A   *   state %7C= (input_bit %3C%3C (this.m - 1))%0A   *   // = 1 %3C%3C (3 - 1)%0A   *   //=%3E 110%0A   *   state & 1 // 0%0A   *   //=%3E 0
 %0A   

Document FibonacciLFSR#next data flow