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:

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

Configuring XML Compare for Efficient XML Comparison

/
Define pipelines and fine-tune the comparison process with various configuration options for output format, parser features, and more.

A Beginner’s Guide to Comparing XML Files

/
With XML Compare, you receive more than just a basic comparison tool. Get started with the most intelligent XML Comparison software.

Everything Great About DeltaJSON

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.

Simplifying Your JSON Management Experience with DeltaJSON

DeltaJSON simplifies JSON data management with the introduction of an NPM package.

Cyber Resilience for SMEs: A Chat with DeltaXML’s Systems Administrator

Peter Anderson, IT System Administrator, relays the importance of cyber resilience for SMEs.

Navigating XML Change in Aviation

Discover how the aviation industry can effectively manage XML changes to ensure compliance and safety while enhancing operational excellence.

S1000D and Beyond: Navigating the Skies of Aviation Data with XML

/
This blog explores the significance of XML in aviation data management, highlighting standards like S1000D.

Making Tax Digital: Embracing XML Technology for HMRC Compliance

The Making Tax Digital (MTD) initiative by HMRC aims to digitise the UK tax system, but what does that mean for UK businesses?

Never miss an update

Sign up to our newsletter and never miss an update on upcoming features or new products