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

Solving Common Challenges with Inaccurate Document Management

20 August 2024

/

0 Comments

Discover practical strategies to overcome common challenges in regulated industries.

How to avoid non-compliance when updating technical documents in regulated industries

20 August 2024

/

0 Comments

Navigate the challenges of updating technical documents in regulated industries.

Built-in XML Comparison vs Document Management Systems (DMS)

20 August 2024

/

0 Comments

Compare using specialised XML comparison software versus a DMS in regulated industries.

How Move Detection Improves Document Management

3 July 2024

/

0 Comments

Learn how move detection technology improves document management by accurately tracking relocated content.

Streamlining Data Syndication in PIM Systems through JSON Comparison

3 July 2024

/

0 Comments

Utilise JSON comparison to reduce errors, labour costs, and system downtime.

Configuring XML Compare for Efficient XML Comparison

21 May 2024

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

20 May 2024

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

Tackling Tracked Changes & Overcoming Hurdles in Managing Large Document Revisions

1 March 2024

Managing large document revisions is challenging with tracked changes.

Everything Great About DeltaJSON

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.

XML Compare →

XML Data Compare →

DITA Compare →

DocBook Compare →

Watch our latest video

How DeltaXML are the Industry Standard

XML Merge →

DITA Merge →

New Release for Merge

Mastering table comparison and merging

Content Compare S1000D →

Content Compare JATS →

Content Compare BITS →

Content Compare NISO-STS →

Content Compare XSL-FO →

Watch our latest video

Getting started with Content Compare

DeltaJSON →

Book a demo

Integrate DeltaJSON into your workflows and applications

ConversionQA →

Meet your new best friend

Getting started with ConversionQA

Resources →

Events and webinars →

Customer stories →

Partners →

Speak to an expert →

Story spotlight

How Karnov Group Merged Two Legal Publishing Companies’ Incompatible Content Databases

All documentation →

Support portal →

BitBucket repositories →

AWS AMI documentation →

Licensing user guide →

Trialing our software?

Get up and running with your DeltaXML evaluation with our video playlist

oXygen Adaptor →

XSLT / Xpath → 55K+ installs

CALS Table Viewer → 534 installs

XPath Notebook → 6K+ installs

Looking for something specific?

We’re confident we can beat any XML comparison challenge

Share this blog

An XSLT linear feedback shift register

Conclusion

Share this blog

Keep Reading

Never miss an update on DeltaXML

Our Products

Resources

Company

Follow us

Integrate and customise comparison results within your systems and processes. Learn More

Never miss an update

XSLT / Xpath → ^{55K+ installs}

CALS Table Viewer → ^{534 installs}

XPath Notebook → ^{6K+ installs}