M-Sequence generator in CoffeeScript

mseq.coffee

###

  M-Sequence Generator
  https://en.wikipedia.org/wiki/Maximum_length_sequence
  Johan Nordberg <[email protected]>

###

noop = ->

class BitField
  if Buffer?
    Container = Buffer
  else if Int8Array?
    Container = Int8Array
  else
    Container = Array

  constructor: (@length) ->
    len = @length
    len += 1 << 3 if len % 8 != 0
    @buffer = new Container len >> 3

  get: (index) ->
    !!(@buffer[index >> 3] & (128 >> (index % 8)))

  set: (index, bit) ->
    if bit
      @buffer[index >> 3] |= 128 >> (index % 8)
    else
      @buffer[index >> 3] &= ~(128 >> (index % 8))

  slice: (start, stop) ->
    len = stop - start
    rv = new BitField len
    for i in [0...len]
      rv.set i, @get(start + i)
    return rv

  toString: ->
    str = ''
    for i in [0...@length]
      str += if @get(i) then '1' else '0'
    return str

randomBit = -> (Math.random() > 0.5)

makeSeed = (length) ->
  rv = []
  rv.push randomBit() while rv.length < length
  return rv

findPosition = (seq, bits) ->
  i = 0
  while i < seq.length
    valid = true
    for j in [0...bits.length]
      if seq.get(i + j) isnt bits.get(j)
        valid = false
        break
    break if valid
    i++
  return i

makeSequence = (m, seed, progress=noop) ->
  n = Math.pow(2, m) - 1
  seed ?= makeSeed m

  seq = new BitField n
  for i in [0...m]
    seq.set i, seed[i]

  bit = true
  i = m

  while i < n
    seq.set i++, bit
    bit = !bit
    pos = findPosition seq, seq.slice(i - m, i)
    if pos != i - m
      seq.set i - 1, bit
      bit = !bit
    if (i % 100) == 0
      progress i / n

  return seq

module.exports = {BitField, makeSequence, findPosition, makeSeed}

if require.main == module
  m = parseInt process.argv.slice(-1)
  if isNaN m
    process.stderr.write "Usage: #{ __filename } <mbits>\n"
    process.exit 1

  seq = makeSequence m, null, (p) ->
    process.stderr.clearLine()
    process.stderr.cursorTo 0
    process.stderr.write "  #{ (p * 100).toFixed(2) }%"

  process.stderr.clearLine()
  process.stderr.cursorTo 0
  process.stderr.write 'Done!\n'

  process.stdout.write JSON.stringify seq.buffer
  process.stdout.write '\n\n'

  for i in [0...seq.length]
    process.stdout.write if seq.get(i) then '1' else '0'

  process.exit 0