(****************************************************************)
(* General Shift Registers      V 1.0                           *)
(* Klaus Pommerening                                            *)
(* 17. Juli 2008                                                *)
(* Last Change: 20. Juli 2008                                   *)
(****************************************************************)

(****************************************************************)
(* This Mathematica program module deals with Boolean          *)
(* functions of n (binary) variables, represented in algebraic  *)
(* normal form (ANF).                                           *)
(* It uses them for constructing general shift registers that   *)
(* have an - in general nonlinear - Boolean feedback function.  *)
(****************************************************************)

(****************************************************************)
(* This program module uses the following data structures:      *)
(* Bit list or binary vector: A list of integers 0 or 1         *)
(*   - A bit list may be represented by the integer whose       *) (*     base 2 representation is given by this bit list,         *)(*     less significant bits at the right end.                  *)
(* Binary monomial in several variables                         *)
(*   - A monomial is represented by a bit list or by the        *)
(*     corresponding integer. Explanation:                      *)
(*     n Bits {e1, ...,en} define a binary monomial in n        *)
(*     Variables T1, ..., Tn as follows:                        *)
(*            T1^e1 ... Tn^en.                                  *)
(* Boolean function in Algebraic normal form (ANF)              *)
(*   - A Boolean function of n variables in ANF is specified    *)(*     by the list of monomials in n indeterminates T1, ..., Tn *)
(*     that have coefficient 1. Each monomial in turn is        *)
(*     specified by a bit list or an integer.                   *)
(*     Note: This representation of Boolean functions makes     *)
(*     sense only for small n or for sparse polynomials.        *)
(* Integer                                                      *)
(*   - An integer may represent itself, a bit list or a binary  *)
(*     monomial.                                                *)
(* NOTE: LSBs = least significant bits,                         *)
(*       MSBs = most significant bits.                          *)
(****************************************************************)

(****************************************************************)
(* i2b: Convert integer to bit list.                            *)
(*      Gives the list of n LSBs of the integer x.              *)
(* Input parameters: n = length of the wanted list              *)
(*                   x = number to be decomposed into bits      *)
(* Preconditions: n ≥ 1, 0 ≤ x ≤ 2^n -1                         *)
(* Error and special situations:                                *)
(*   If n ≤ 0, the output is the empty list {}.                 *)
(*   If x ≤ 0, set x = 0.                                       *)
(*   If x ≥ 2^n, truncate excess MSBs.                          *)
(*   If x < 2^(n-1), pad left end of list with zeroes.          *)
(****************************************************************)

i2b[n_Integer,x_Integer]:=
Module[{y,binDig,l},
If[n≤0,Return[{}],];
If[x<0,y=0,y=x];
binDig=IntegerDigits[y,2];
l=Length[binDig];
If[l>n,
Return[Drop[binDig,l-n]],
Return[Join[Table[0,{n-l}],binDig]]]
]

(****************************************************************)
(* b2i: Convert bit list to integer.                            *)
(*   b2i interprets a binary vector as integer in base 2        *) (*   representation and returns this integer.                   *)
(* Input parameter: binlist = list of bits                      *)
(*                  MSB to the left, LSB to the right           *)
(* Preconditions: binlist consists of 0's and 1's.              *)
(* Error situation: If binlist contains other entries, the      *)
(*   result is anything.                                        *)
(****************************************************************)

b2i[binlist_]:=
Module[{l,i,a=0},
l=Length[binlist];
Do[a=a+binlist[[i]]*2^(l-i),{i,l}];
Return[a]
]

(****************************************************************)
(* monAtB: Evaluate monomial at binary vector.                 *)
(*   monAtB evaluates the monomial given by the list of n LSBs *) (*   of the integer e at the n-tuple bitl.                      *)
(* Input parameters: n = number of variables/ arguments         *)
(*                   e = integer describing the monomial        *)
(*                       i. e. the exponent vector              *)
(*                   bitl = argument vector                     *)
(* Preconditions: n ≥ 1, 0 ≤ e ≤ 2^n -1                         *)
(*                bitl has length n and consists of 01 and 1s.  *)
(* Error and special situations:                                *)
(*   If n ≤ 0, the return value is 0.                           *)
(*   If e is outside its range, this is handled by i2b.         *)
(*   If bitl is shorter then n, the function fails.             *)
(*   If bitl is longer than n, the exceeding bits to the right  *)
(*     are ignored.                                             *)
(* Note: If e gives the zero exponent vector (that is e≤0),     *)
(*    the monomial is the constant 1 and therefore gives the    *)
(*    value 1 at any argument vector (except when n≤0).         *)
(* Calls: i2b                                                   *)
(****************************************************************)

monAtB[n_Integer,e_Integer,bitl_]:=
Module[{exponents,value=1,i},
If[n≤0,Return[0],];
exponents=i2b[n,e];
For[i=1,i≤n,i++,
If[exponents[[i]]==1,value=value*bitl[[i]],]
];
Return[value]
]

(****************************************************************)
(* monAtI: Evaluate monomial at binary vector represented       *)
(*   by an integer.                                             *)
(*   monAtI evaluates the monomial given by the list of n LSBs  *)
(*   of the integer e at the n-tuple of n LSBs of the integer x.*)
(* Input parameters: n = number of variables/ arguments         *)
(*                   e = integer describing the monomial        *)
(*                       i. e. the exponent vector              *)
(*                   x = integer describing the argument vector *)
(* Preconditions: n ≥ 1, 0 ≤ e, x ≤ 2^n -1                      *)
(* Error and special situations:                                *)
(*   If n ≤ 0, the return value is 0.                           *)
(*   If e or x are outside their ranges, this is handled        *)
(*     by i2b.                                                  *)
(* Note: If e gives the zero exponent vector (that is e≤0),     *)
(*    the monomial is the constant 1 and therefore gives the    *)
(*    value 1 at any argument vector (except when n≤0).         *)
(* Calls: i2b, monAtB                                           *)
(****************************************************************)

monAtI[n_Integer,e_Integer,x_Integer]:=
Module[{arguments,value},
If[n≤0,Return[0],];
arguments=i2b[n,x];
value=monAtB[n,e,arguments];
Return[value]
]

(****************************************************************)
(* cleanANF: Take a list of integers and force each entry into  *)
(*   the range [0 ... 2^n-1]. Then remove repeating entries.    *)
(* Input parameters: n = the number of variables                *)
(*                   intlist = the list of integers             *)
(*                      representing the monomials occuring in  *)
(*                      an ANF.                                 *)
(* Preconditions: n≥1                                           *)
(*                intlist consists of integers.                 *)
(* Error situations: If n≤0, then output is the empty list.     *)
(*                   The case of non-integer entries in         *)
(*                   intlist is not caught and gives            *)
(*                   unpredictable results.                     *)
(****************************************************************)

cleanANF[n_Integer,intlist_]:=
Module[{l,i,dummylist,cleanlist},
If[n≤0,Return[{}],];
dummylist=intlist;
l=Length[dummylist];
For[i=1,i≤l,i++,
If[dummylist[[i]]<0,dummylist=ReplacePart[dummylist,0,i],];
If[dummylist[[i]]≥2^n,dummylist=ReplacePart[dummylist,Mod[dummylist[[i]],2^n],i],]
];
cleanlist=Union[dummylist];
Return[cleanlist]
]

(****************************************************************)
(* evalBFatB: Evaluate a Boolean function of n variables,       *) 
(*   given in ANF, at a binary argument vector.                 *)
(* Input parameters: n = number of variables/ arguments         *)
(*                   monList = list of monomials                *)
(*                   bitl = argument vector                     *)
(* Preconditions: n≥1                                           *)
(*                monList consists of integers                  *)
(*                bitl consists of 0s and 1s.                   *)
(* Error situations: If n≤0, then the return value is 0.        *)
(*                   The case of non-integer entries in         *)
(*                   monList is not caught and gives            *)
(*                   unpredictable results.                     *)
(*                   Non admissible values in bitl are handled  *)
(*                   by monAtB.                                 *)
(* Calls: cleanANF, monAtB                                      *)
(*        Indirect call: i2b                                    *)
(****************************************************************)

evalBFatB[n_Integer,monList_,bitl_]:=
Module[{value=0,newlist,l},
If[n≤0,Return[0],];
newlist=cleanANF[n,monList];
l=Length[newlist];
Do[value=value+monAtB[n,newlist[[i]],bitl],{i,l}];
Return[Mod[value,2]]
]

(****************************************************************)
(* evalBFatI: Evaluate a Boolean function of n variables at an  *)
(*   n dimensional binary argument vector, given by the         *)
(*   base 2 representation of an integer.                       *)
(* Input parameters: n = number of variables/ arguments         *)
(*                   monList = list of monomials                *)
(*                   x = integer describing the argument vector *)
(* Preconditions: n≥1                                           *)
(*                monList consists of integers                  *)
(* Error situations: If n≤0, then the return value is 0.        *)
(*                   The case of non-integer entries in         *)
(*                   monList is not caught and gives            *)
(*                   unpredictable results.                     *)
(*                   Non admissible values of x are handled by  *)
(*                   monAtI.                                    *)
(* Calls: cleanANF, monAtI                                      *)
(*        Indirect call: i2b, monAtB                            *)
(****************************************************************)

evalBFatI[n_Integer,monList_,x_Integer]:=
Module[{value=0,newlist,l},
If[n≤0,Return[0],];
newlist=cleanANF[n,monList];
l=Length[newlist];
Do[value=value+monAtI[n,newlist[[i]],x],{i,l}];
Return[Mod[value,2]]
]

(****************************************************************)
(* shiftReg: Define a general shift register and generate a     *)
(*   bit sequence.                                              *)
(* Input parameters: n = length of the register                 *)
(*                   mlist = list of monomials for the Booelan  *)
(*                     feedback function in ANF                 *)
(*                   seed = bit list describing start vector    *)
(*                   q = number of output bits                  *)
(* Preconditions: n≥1                                           *)
(*                mlist consists of integers.                   *)
(*                seed is a list of length n consisting of 0s   *)
(*                  and 1s.                                     *)
(*                q is an integer ≥1.                           *)
(* Error situations: If n≤0, then the output is the empty list  *)
(*                     {}.                                      *)
(*                   Entries of mlist outside of 0 ... 2^n-1    *)
(*                     and multiple entries in mlist            *)
(*                     are handled by cleanANF.                 *)
(*                     The case of non-integer entries in       *)
(*                     mlist is not caught and gives            *)
(*                     unpredictable results.                   *)
(*                   If the length of seed is < n or > n, the   *)
(*                     output is the empty list {}.             *)
(*                     Entries other than 0 or 1 in mlist give  *)
(*                     undefined results.                       *)
(*                   If q≤0, then the output is the empty list  *)
(*                     {}.                                      *)
(* Calls: evalBFatB                                             *)
(*        Indirect call: cleanANF, i2b, monAtB                  *)
(****************************************************************)

shiftReg[n_Integer,mlist_,seed_,q_Integer] :=
Module[{x,i,y, outlist = {}},
If[n≤0,Return[{}],];
If[Length[seed]<n, Return[{}],];
If[Length[seed]>n, Return[{}],];
x=seed;
For[i=0,i<q,i++,
outlist = Append[outlist,Last[x]];
y = evalBFatB[n,mlist,x];
x = RotateRight[x];
x[[1]] = y
];
Return[outlist]
]

(****************************************************************)
(* Examples                                                     *)
(****************************************************************)

(****************************************************************)
(* Length 4, ANF T1*T2 + T3*T4 = {12,3}, seed 1011 -> 11.        *)
(* Generate 40 bits.                                            *)
(****************************************************************)

shiftReg[4,{3,12},{1,0,1,1},100]

(****************************************************************)
(* Length 3, ANF T1 + T3 = {4,1}, seed 111 -> 7.                 *)
(* Generate 10 bits.                                            *)
(* Golomb, p. 29                                                *)
(****************************************************************)

shiftReg[3,{1,4},{1,1,1},10]

(****************************************************************)
(* Length 4, ANF T3 + T4 = {2,1}, seed 1111 -> 15.               *)
(* Generate 19 bits.                                            *)
(* Golomb, p. 111                                               *)
(****************************************************************)

shiftReg[4,{1,2},{1,1,1,1},19]

(****************************************************************)
(* Length 3, ANF T2*T3 = {3}, seed 110 -> 6.                     *)
(* Generate 8 bits.                                             *)
(* Golomb, p. 115                                               *)
(****************************************************************)

shiftReg[3,{3},{1,1,0},8]

(****************************************************************)
(* Length 3, ANF T2*T3 = {3}, seed 100 -> 4.                     *)
(* Generate 8 bits.                                             *)
(* Golomb, p. 115                                               *)
(****************************************************************)

shiftReg[3,{3},{1,0,0},8]

(****************************************************************)
(* Length 3, ANF T2*T3 = {3}, seed 111 -> 7.                     *)
(* Generate 8 bits.                                             *)
(* Golomb, p. 115                                               *)
(****************************************************************)

shiftReg[3,{3},{1,1,1},8]

(****************************************************************)
(* Length 4, ANF T1*T2 + T4 = {12,1}, seed 0011 -> 3.            *)
(* Generate 19 bits.                                            *)
(* Golomb, p. 170                                               *)
(****************************************************************)

shiftReg[4,{1,12},{0,0,1,1},19]

(****************************************************************)
(* Jetzt Länge steigern                                         *)
(****************************************************************)

shiftReg[4,{1,12},{0,0,1,1},40]

shiftReg[4,{1,12},{0,0,1,1},100]

(****************************************************************)
(* Length 4, ANF T1*T2*T4 + T3 = {13,2}, seed 0011 -> 3.         *)
(* Generate 100 bits.                                           *)
(****************************************************************)

shiftReg[4,{2,13},{0,0,1,1},100]

shiftReg[8,{1,12,129},{1,0,1,1,0,0,1,1},50]

shiftReg[16,{1,12,129,65000},{1,0,0,1,0,1,1,0,1,0,1,1,0,0,1,1},100]

shiftReg[32,{1,12,129,65000,123456},{1,0,0,1,0,1,1,0,1,0,1,1,0,0,1,1,1,0,0,1,0,1,1,0,1,0,1,1,0,0,1,1},200]

shiftReg[32,{1,12,63,129,256,65000,123456,2147483640},{1,0,0,1,0,1,1,0,1,0,1,1,0,0,1,1,1,0,0,1,0,1,1,0,1,0,1,1,0,0,1,0},2000]

shiftReg[64,{1,12,63,129,256,65000,123456,2147483640},{1,0,0,1,0,1,1,0,1,0,1,1,0,0,1,1,1,0,0,1,0,1,1,0,1,0,1,1,0,0,1,0,1,0,0,1,0,1,1,0,1,0,1,1,0,0,1,1,1,0,0,1,0,1,1,0,1,0,1,1,0,0,1,0},2000]