Package io.netty.handler.codec.compression

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	Bzip2DivSufSort.PartitionResult
private static class	Bzip2DivSufSort.StackEntry
private static class	Bzip2DivSufSort.TRBudget

Field Summary

Fields

Modifier and Type	Field	Description
private static final int	BUCKET_A_SIZE
private static final int	BUCKET_B_SIZE
private static final int	INSERTIONSORT_THRESHOLD
private static final int[]	LOG_2_TABLE
private final int	n
private final int[]	SA
private static final int	SS_BLOCKSIZE
private static final int	STACK_SIZE
private final byte[]	T

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)
private Bzip2DivSufSort.PartitionResult	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:

• Constant Field Values

BUCKET_A_SIZE

private static final int BUCKET_A_SIZE

See Also:

• Constant Field Values

BUCKET_B_SIZE

private static final int BUCKET_B_SIZE

See Also:

• Constant Field Values

SS_BLOCKSIZE

private static final int SS_BLOCKSIZE

See Also:

• Constant Field Values

INSERTIONSORT_THRESHOLD

private static final int INSERTIONSORT_THRESHOLD

See Also:

• Constant Field Values

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