Class Bzip2DivSufSort

java.lang.Object
io.netty.handler.codec.compression.Bzip2DivSufSort

final class Bzip2DivSufSort extends Object
DivSufSort suffix array generator.
Based on libdivsufsort 1.2.3 patched to support Bzip2.
This is a simple conversion of the original C with two minor bugfixes applied (see "BUGFIX" comments within the class). Documentation within the class is largely absent.
  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    private static class 
     
    private static class 
     
    private static class 
     
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private static final int
     
    private static final int
     
    private static final int
     
    private static final int[]
     
    private final int
     
    private final int[]
     
    private static final int
     
    private static final int
     
    private final byte[]
     
  • Constructor Summary

    Constructors
    Constructor
    Description
    Bzip2DivSufSort(byte[] block, int[] bwtBlock, int blockLength)
     
  • Method Summary

    Modifier and Type
    Method
    Description
    private static int
    BUCKET_B(int c0, int c1)
     
    private static int
    BUCKET_BSTAR(int c0, int c1)
     
    int
    bwt()
    Performs a Burrows Wheeler Transform on the input array.
    private int
    constructBWT(int[] bucketA, int[] bucketB)
     
    private static int
    getIDX(int a)
     
    private void
    lsIntroSort(int isa, int isaD, int isaN, int first, int last)
     
    private void
    lsSort(int isa, int n, int depth)
     
    private void
    lsUpdateGroup(int isa, int first, int last)
     
    private int
    sortTypeBstar(int[] bucketA, int[] bucketB)
     
    private static void
    ssBlockSwap(int[] array1, int first1, int[] array2, int first2, int size)
     
    private int
    ssCompare(int p1, int p2, int depth)
     
    private int
    ssCompareLast(int pa, int p1, int p2, int depth, int size)
     
    private void
    ssFixdown(int td, int pa, int sa, int i, int size)
     
    private void
    ssHeapSort(int td, int pa, int sa, int size)
     
    private void
    ssInsertionSort(int pa, int first, int last, int depth)
     
    private static int
    ssLog(int n)
     
    private int
    ssMedian3(int td, int pa, int v1, int v2, int v3)
     
    private int
    ssMedian5(int td, int pa, int v1, int v2, int v3, int v4, int v5)
     
    private void
    ssMerge(int pa, int first, int middle, int last, int[] buf, int bufoffset, int bufsize, int depth)
     
    private void
    ssMergeBackward(int pa, int[] buf, int bufoffset, int first, int middle, int last, int depth)
     
    private void
    ssMergeCheckEqual(int pa, int depth, int a)
     
    private void
    ssMergeForward(int pa, int[] buf, int bufoffset, int first, int middle, int last, int depth)
     
    private void
    ssMultiKeyIntroSort(int pa, int first, int last, int depth)
     
    private int
    ssPivot(int td, int pa, int first, int last)
     
    private int
    ssSubstringPartition(int pa, int first, int last, int depth)
     
    private void
    subStringSort(int pa, int first, int last, int[] buf, int bufoffset, int bufsize, int depth, boolean lastsuffix, int size)
     
    private static void
    swapElements(int[] array1, int idx1, int[] array2, int idx2)
     
    private void
    trCopy(int isa, int isaN, int first, int a, int b, int last, int depth)
     
    private void
    trFixdown(int isa, int isaD, int isaN, int sa, int i, int size)
     
    private int
    trGetC(int isa, int isaD, int isaN, int p)
     
    private void
    trHeapSort(int isa, int isaD, int isaN, int sa, int size)
     
    private void
    trInsertionSort(int isa, int isaD, int isaN, int first, int last)
     
    private void
    trIntroSort(int isa, int isaD, int isaN, int first, int last, Bzip2DivSufSort.TRBudget budget, int size)
     
    private static int
    trLog(int n)
     
    private int
    trMedian3(int isa, int isaD, int isaN, int v1, int v2, int v3)
     
    private int
    trMedian5(int isa, int isaD, int isaN, int v1, int v2, int v3, int v4, int v5)
     
    trPartition(int isa, int isaD, int isaN, int first, int last, int v)
     
    private int
    trPivot(int isa, int isaD, int isaN, int first, int last)
     
    private void
    trSort(int isa, int n, int depth)
     

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

    • STACK_SIZE

      private static final int STACK_SIZE
      See Also:
    • BUCKET_A_SIZE

      private static final int BUCKET_A_SIZE
      See Also:
    • BUCKET_B_SIZE

      private static final int BUCKET_B_SIZE
      See Also:
    • SS_BLOCKSIZE

      private static final int SS_BLOCKSIZE
      See Also:
    • INSERTIONSORT_THRESHOLD

      private static final int INSERTIONSORT_THRESHOLD
      See Also:
    • LOG_2_TABLE

      private static final int[] LOG_2_TABLE
    • SA

      private final int[] SA
    • T

      private final byte[] T
    • n

      private final int n
  • Constructor Details

    • Bzip2DivSufSort

      Bzip2DivSufSort(byte[] block, int[] bwtBlock, int blockLength)
      Parameters:
      block - The input array
      bwtBlock - The output array
      blockLength - The length of the input data
  • Method Details

    • swapElements

      private static void swapElements(int[] array1, int idx1, int[] array2, int idx2)
    • ssCompare

      private int ssCompare(int p1, int p2, int depth)
    • ssCompareLast

      private int ssCompareLast(int pa, int p1, int p2, int depth, int size)
    • ssInsertionSort

      private void ssInsertionSort(int pa, int first, int last, int depth)
    • ssFixdown

      private void ssFixdown(int td, int pa, int sa, int i, int size)
    • ssHeapSort

      private void ssHeapSort(int td, int pa, int sa, int size)
    • ssMedian3

      private int ssMedian3(int td, int pa, int v1, int v2, int v3)
    • ssMedian5

      private int ssMedian5(int td, int pa, int v1, int v2, int v3, int v4, int v5)
    • ssPivot

      private int ssPivot(int td, int pa, int first, int last)
    • ssLog

      private static int ssLog(int n)
    • ssSubstringPartition

      private int ssSubstringPartition(int pa, int first, int last, int depth)
    • ssMultiKeyIntroSort

      private void ssMultiKeyIntroSort(int pa, int first, int last, int depth)
    • ssBlockSwap

      private static void ssBlockSwap(int[] array1, int first1, int[] array2, int first2, int size)
    • ssMergeForward

      private void ssMergeForward(int pa, int[] buf, int bufoffset, int first, int middle, int last, int depth)
    • ssMergeBackward

      private void ssMergeBackward(int pa, int[] buf, int bufoffset, int first, int middle, int last, int depth)
    • getIDX

      private static int getIDX(int a)
    • ssMergeCheckEqual

      private void ssMergeCheckEqual(int pa, int depth, int a)
    • ssMerge

      private void ssMerge(int pa, int first, int middle, int last, int[] buf, int bufoffset, int bufsize, int depth)
    • subStringSort

      private void subStringSort(int pa, int first, int last, int[] buf, int bufoffset, int bufsize, int depth, boolean lastsuffix, int size)
    • trGetC

      private int trGetC(int isa, int isaD, int isaN, int p)
    • trFixdown

      private void trFixdown(int isa, int isaD, int isaN, int sa, int i, int size)
    • trHeapSort

      private void trHeapSort(int isa, int isaD, int isaN, int sa, int size)
    • trInsertionSort

      private void trInsertionSort(int isa, int isaD, int isaN, int first, int last)
    • trLog

      private static int trLog(int n)
    • trMedian3

      private int trMedian3(int isa, int isaD, int isaN, int v1, int v2, int v3)
    • trMedian5

      private int trMedian5(int isa, int isaD, int isaN, int v1, int v2, int v3, int v4, int v5)
    • trPivot

      private int trPivot(int isa, int isaD, int isaN, int first, int last)
    • lsUpdateGroup

      private void lsUpdateGroup(int isa, int first, int last)
    • lsIntroSort

      private void lsIntroSort(int isa, int isaD, int isaN, int first, int last)
    • lsSort

      private void lsSort(int isa, int n, int depth)
    • trPartition

      private Bzip2DivSufSort.PartitionResult trPartition(int isa, int isaD, int isaN, int first, int last, int v)
    • trCopy

      private void trCopy(int isa, int isaN, int first, int a, int b, int last, int depth)
    • trIntroSort

      private void trIntroSort(int isa, int isaD, int isaN, int first, int last, Bzip2DivSufSort.TRBudget budget, int size)
    • trSort

      private void trSort(int isa, int n, int depth)
    • BUCKET_B

      private static int BUCKET_B(int c0, int c1)
    • BUCKET_BSTAR

      private static int BUCKET_BSTAR(int c0, int c1)
    • sortTypeBstar

      private int sortTypeBstar(int[] bucketA, int[] bucketB)
    • constructBWT

      private int constructBWT(int[] bucketA, int[] bucketB)
    • bwt

      public int bwt()
      Performs a Burrows Wheeler Transform on the input array.
      Returns:
      the index of the first character of the input array within the output array