module LinearShiftRegisters

export LSR_period, LCG_period

function _repeated_substring(source)
	len = length(source)
	
	# had to account for weird edge case in which length 2 vectors always returns themselves
	if len < 3
		len == 1 && return nothing
	
		s1, s2 = source
		if len == 2 && s1 == s2
			return s1
		else
			return nothing
		end
	end
	
	# Check candidate strings
	for i in 1:(len ÷ 2 + 1)
		repeat_count, remainder = divrem(len, i)
		
		# Check for no leftovers characters, and equality when repeated
		if remainder == 0 && source == repeat(source[1:i], repeat_count)
			return source[1:i]#, repeat_count
		end
	end
	
	return nothing
end

function _LSR_period(const_vec::AbstractVector, init_vec::AbstractVector)
	sequence_vec = reverse(init_vec)

	res = nothing
	while isnothing(res)
		new_val = mod(sum(map(i -> const_vec[i] * sequence_vec[end - (i - 1)], 1:4)), 2)
		push!(sequence_vec, new_val)
		res = _repeated_substring(sequence_vec)
	end
	
	return res
end

@doc raw"""
```julia
LSR_period(const_str::AbstractVector{T}, init_str::AbstractVector{R}) where {T, R <: Integer} -> AbstractVector
LSR_period(const_str::AbstractString, init_str::AbstractString) -> String
```

Given a starting binary string (`init_str`) and a constant mutating string (`const_str`), `LSR_period` will find the repeating sequence generated from these.

!!! note

    As this method looks for recurring sequences, it is possible that this function does not terminate—or maybe it does terminate, but I haven't waited long enough to find out.


---

### Description

A (linear) shift register with feedback is an arrangement of registers in a row, each register being capable of holding either the digit 1 (on) or 0 (off).  Suppose the system has ``n`` registers, ``R_1,\ldots,R_n``, and ``X_i(t)`` denotes the content of register ``R_i`` at time ``t``.  Initially, let the system be given

Given

### Examples

```julia
julia> LSR_period("1001", "0100")
"001000111101011"

julia> LSR_period("1001", "0101")
"101011001000111"
```
"""
function LSR_period(const_vec::AbstractVector{T}, init_vec::AbstractVector{R}) where {T, R <: Integer}
	return _LSR_period(const_vec, init_vec)
end
function LSR_period(const_str::AbstractString, init_str::AbstractString)
	const_vec = parse.(Int8, collect(const_str))
	init_vec = parse.(Int8, collect(init_str))
	
	return join(_LSR_period(const_vec, init_vec))
end

function _LCG_period(m::Integer, a::Integer, b::Integer, x0::T) where {T <: Integer}
	sequence_vec = T[x0]

	new_x, res = x0, nothing
	while isnothing(res)
		new_x =  mod(a * new_x + b, m)
		push!(sequence_vec, new_x)
		res = _repeated_substring(sequence_vec)
	end

	return res
end

@doc raw"""
```julia
LCG_period(m::Integer, a::Integer, b::Integer, x0::Integer) -> String
```

Given `m`, `a`, `b`, and `x0`, finds the period generated by these parameters from a Linear Congruential Generator, and returns this sequence as a string.

!!! note

    As this method looks for recurring sequences, it is possible that this function does not terminate—or maybe it does terminate, but I haven't waited long enough to find out.


---

### Description

Choose m, a positive integer.  Choose a, b (mod m) integers.

The Linear Congruential Generator is given to us by

```math
x_1 \equiv ax_0+b\mod m\\
x_2 \equiv ax_1+b\mod m\\
\vdots\\
x_{n + 1} \equiv ax_n + b \mod m\\
\vdots
```

Eventually, ``x_n = x_i`` for some ``n``, ``i`` (let's suppose ``n>i`` and ``i`` is not necessarily ``0``).  Then, clearly,

```math
x_{n+1} = x_{i+1},\ldots.
```

So

```math
x_i, x_{i+1},\dots, x_{n-1}
```

Will be repeated forever.

From a cryptography point of view, LCG is too vulnerable (although all pseudorandom number generators are vulnerable), but it is still useful for other perposes that require pseudorandom numbers.

For essentially a more sophisticated version of LCG in the sense that it is based on recurring linear relations, see `LSR_period`.

---

### Examples

```julia
julia> println(LinearShiftRegisters._LCG_period(9, 5, 2, 0))
[0, 2, 3, 8, 6, 5]

julia> LCG_period(9, 5, 2, 0)
"023865"
```
"""
function LCG_period(m::Integer, a::Integer, b::Integer, x0::Integer)
	return join(_LCG_period(m, a, b, x0))
end

end # end module
