An XSLT linear feedback shift register

The Linear Feedback Shift Register (LFSR) provides a simple yet very versatile solution for the generation of pseudo-random sequences of bits. This concept, can be efficiently emulated using XSLT 2.0 or 3.0, the sample show here uses XSLT 3.0 because it is quite neat to use a closure to maintain the state of the function that manipulates the shift-register.

The XSLT snippet below shows the low-level emulation of the shift-register. This takes a boolean sequence as an input argument which is then shifted right a single ‘bit’, the result of an XOR operation on the output bit (right-most bit) and bits at 2 tap points is then fed back to the left-most bit of the ‘register’.

<xsl:function name="fn:shift-sequence" as="xs:boolean*">    <xsl:param name="sequence" as="xs:boolean+"/>        <xsl:variable name="output-bit" as="xs:boolean" select="$sequence[last()]"/>    <xsl:variable name="bit1" as="xs:boolean" select="$sequence[$tap-point-1]"/>    <xsl:variable name="bit2" as="xs:boolean" select="$sequence[$tap-point-2]"/>    <xsl:variable name="new-bit" as="xs:boolean"       select="fn:xor($bit2, fn:xor($output-bit, $bit1))"/>        <xsl:sequence select="      ($new-bit,      subsequence($sequence, 1, count($sequence) - 1)      )"/>      xsl:function>    <xsl:function name="fn:xor" as="xs:boolean">    <xsl:param name="operand1"/>    <xsl:param name="operand2"/>    <xsl:sequence select="($operand1 and not($operand2)) or (not($operand1) and $operand2)"/>  xsl:function>

Now that we have this low-level function, we need a way to maintain the state of the shift-register for each subsequent bit in the generated sequence. The approach I’ve taken is to use the following function that takes a bit sequence seed as an argument and returns an updated version of itself, along with the current output bit:

  <xsl:function name="fn:generator-function" as="function(*)">    <xsl:param name="seed" as="xs:boolean*"/>    <xsl:variable name="new-sequence" select="fn:shift-sequence($seed)"/>    <xsl:sequence select="function() as item()* {      (      fn:generator-function($new-sequence),      $new-sequence[last()])      }"/>  xsl:function>

We can now use this function in any number of ways, but this example shows how xsl:iterate can be used to generate a specific number of bits:

  <xsl:function name="fn:generate-bit-sequence" as="xs:boolean*">    <xsl:param name="generator-function" as="function(*)"/>    <xsl:param name="count" as="xs:integer"/>             <xsl:iterate select="1 to $count">      <xsl:param name="bit-generator" as="function(*)+" select="$generator-function"/>      <xsl:variable name="generator-result" as="item()*" select="$bit-generator()"/>      <xsl:sequence select="$generator-result[$BIT_INDEX]"/>      <xsl:next-iteration>        <xsl:with-param name="bit-generator" select="$generator-result[$FN_INDEX]"/>      xsl:next-iteration>        xsl:iterate>      xsl:function>

So, that is really all the XSLT we need to generate a pseudo-random sequence of bits. I have then just added some extra functionality to make the result more readable by showing bit-sequences a 8-bit words with ‘1’ and ‘0’ characters. The final complete test XSLT can be run against itself:

Input seed: 1011101101010111

Output sequence: