Posted9 March 2016
byPhil G. Fearon

An XSLT linear feedback shift register

Posted9 March 2016
byPhil G. Fearon

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:

11010101 10111011 00101000 00100001 11011000 11100101 00001010 10111011 00110101 00100001
10001011 11100100 10110011 10111111 00011010 00111101 01000110 10110010 11010001 00011100
00110111 01010100 10000100 10101111 10011111 01001110 11011100 11101000 00010110 10011000
01100001 11001001 00100101 01111111 11111010 01111111 11100111 01111111 10110100 01111110
00001101 01111010 00100010 01100110 11101111 00110000 10001101 10010011 10100000 11111010

THE complete XSLT for generating this sequence is shown below, the XSLT processor used here was Saxon-PE 9.7.0.3 from Saxonica:

xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
  xmlns:xs="http://www.w3.org/2001/XMLSchema"
  xmlns:fn="urn.internal.lrs.functions"
  exclude-result-prefixes="xs fn"
  expand-text="yes"
  version="3.0">
  
  <xsl:output indent="yes"/>
  
  <xsl:variable name="seed-bits" as="xs:boolean*" 
    select="fn:string-to-boolean-sequence('1011101101010111')"/>
  <xsl:variable name="tap-point-1" as="xs:integer" select="15"/>
  <xsl:variable name="tap-point-2" as="xs:integer" select="14"/>
  <xsl:variable name="bits-required" select="8 * 50"/>
  
  <xsl:variable name="FN_INDEX" as="xs:integer" select="1"/>
  <xsl:variable name="BIT_INDEX" as="xs:integer" select="2"/>
  
  <xsl:variable name="initial-generator-function" as="function(*)"
    select="fn:generator-function($seed-bits)"/>
      
 
   
  <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>
  
  
  <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>
  
  <xsl:template match="/">   
    <root>
      <xsl:variable name="result-bits" as="xs:boolean*" 
        select="fn:generate-bit-sequence($initial-generator-function, $bits-required)"/>
      <xsl:sequence select="fn:boolean-sequence-to-binary-string($result-bits)"/>        
    root>
  xsl:template>
    
 
  <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>
  
  
  
  
  <xsl:function name="fn:boolean-sequence-to-binary-string" as="xs:string">
    <xsl:param name="sequence" as="xs:boolean*"/>
    <xsl:variable name="count" as="xs:integer" select="count($sequence)"/>
    <xsl:variable name="displayed-register-length" as="xs:integer" select="8"/>
    <xsl:sequence select="
      string-join(('
',
      for $x in 1 to $count return 
      (if ($sequence[$x]) then '1' else '0',
      if ($x mod 80 eq 0) then '
' else if ($x mod $displayed-register-length eq 0) then ' ' else ''
      )
      ),'')"/>        
  xsl:function>
  
  
  <xsl:function name="fn:string-to-boolean-sequence" as="xs:boolean*">
    <xsl:param name="text" as="xs:string"/>
    <xsl:variable name="codepoint-for-one" as="xs:integer" select="string-to-codepoints('1')"/>
    <xsl:variable name="codepoints" as="xs:integer*" select="string-to-codepoints($text)"/>
    <xsl:variable name="count-codepoints" as="xs:integer" select="count($codepoints)"/>
    <xsl:sequence select="for $x in $codepoints return $x eq $codepoint-for-one"/>
  xsl:function>
  
xsl:stylesheet>

Conclusion

Approaches for random number generation include the fn:random-number-generator function in XPath 3.1. Dimitre Novatchev’s FXSL also has functions for random number generation.

The main motivation when I started this was to explore higher order functions in XSLT 3.0, but the approach I’ve outlined here for generating pseudo-random bit sequences with XSLT will hopefully also be of interest for certain applications.

Keep Reading

Everything Great About DeltaJSON

0 Comments

/

20 February 2024

Accessible through an intuitive online GUI or REST API, DeltaJSON is the complete package for managing changing JSON data. Learn everything about makes DeltaJSON great.