Top Description Fields Constructors Methods
org.apache.commons.compress.compressors.bzip2

pack-priv final Class BlockSort

extends Object
Class Inheritance
Imports
java.util.Arrays, .BitSet
Encapsulates the Burrows-Wheeler sorting algorithm needed by BZip2CompressorOutputStream.

This class is based on a Java port of Julian Seward's blocksort.c in his libbzip2

The Burrows-Wheeler transform is a reversible transform of the original data that is supposed to group similar bytes close to each other. The idea is to sort all permutations of the input and only keep the last byte of each permutation. E.g. for "Commons Compress" you'd get: 

 CompressCommons
Commons Compress
CompressCommons
essCommons Compr
mmons CompressCo
mons CompressCom
mpressCommons Co
ns CompressCommo
ommons CompressC
ompressCommons C
ons CompressComm
pressCommons Com
ressCommons Comp
s CompressCommon
sCommons Compres
ssCommons Compre

Which results in a new text "ss romooCCmmpnse", in adition the index of the first line that contained the original text is kept - in this case it is 1. The idea is that in a long English text all permutations that start with "he" are likely suffixes of a "the" and thus they end in "t" leading to a larger block of "t"s that can better be compressed by the subsequent Move-to-Front, run-length und Huffman encoding steps.

For more information see for example:

Field Summary

Modifier and TypeField and Description
private static final int
CLEARMASK

private static final int
DEPTH_THRESH

private int[]
eclass

private static final int
FALLBACK_QSORT_SMALL_THRESH

private static final int
FALLBACK_QSORT_STACK_SIZE

private boolean
firstAttempt

private final int[]
ftab

private static final int
FTAB_LENGTH

private static final int[]
INCS

private final boolean[]
mainSort_bigDone

private final int[]
mainSort_copy

private final int[]
mainSort_runningOrder

private static final int
QSORT_STACK_SIZE

private final char[]
quadrant

Array instance identical to Data's sfmap, both are used only temporarily and indepently, so we do not need to allocate additional memory.

private static final int
SETMASK

private static final int
SMALL_THRESH

private final int[]
stack_dd

private final int[]
stack_hh

private final int[]
stack_ll

private static final int
STACK_SIZE

private static final int
WORK_FACTOR

private int
workDone

private int
workLimit

Constructor Summary

AccessConstructor and Description
pack-priv
BlockSort(final BZip2CompressorOutputStream.Data data)

Method Summary

Modifier and TypeMethod and Description
pack-priv void
blockSort(final BZip2CompressorOutputStream.Data data, final int last)

private void
fallbackQSort3(final int[]
points to the index of the starting point of a permutation inside the block of data in the current partially sorted order
fmap, final int[]
points from the index of a character inside the block to the first index in fmap that contains the bucket of its suffix that is sorted in this step.
eclass, final int
lower boundary of the fmap-interval to be sorted
loSt, final int
upper boundary of the fmap-interval to be sorted
hiSt)

private void
fallbackSimpleSort(final int[]
points to the index of the starting point of a permutation inside the block of data in the current partially sorted order
fmap, final int[]
points from the index of a character inside the block to the first index in fmap that contains the bucket of its suffix that is sorted in this step.
eclass, final int
lower boundary of the fmap-interval to be sorted
lo, final int
upper boundary of the fmap-interval to be sorted
hi)

pack-priv void
fallbackSort(final BZip2CompressorOutputStream.Data data, final int last)

Adapt fallbackSort to the expected interface of the rest of the code, in particular deal with the fact that block starts at offset 1 (in libbzip2 1.0.6 it starts at 0).

pack-priv void
fallbackSort(final int[]
points to the index of the starting point of a permutation inside the block of data in the current partially sorted order
fmap, final byte[]
the original data
block, final int
size of the block
nblock)

private int[]
fpop(final int sp)

private void
fpush(final int sp, final int lz, final int hz)

private void
fswap(final int[] fmap, final int zz1, final int zz2)

swaps two values in fmap

private void
fvswap(final int[] fmap, int yyp1, int yyp2, int yyn)

swaps two intervals starting at yyp1 and yyp2 of length yyn inside fmap.

private int[]
getEclass()

private void
mainQSort3(final BZip2CompressorOutputStream.Data dataShadow, final int loSt, final int hiSt, final int dSt, final int last)

Method "mainQSort3", file "blocksort.c", BZip2 1.0.2

private boolean
mainSimpleSort(final BZip2CompressorOutputStream.Data dataShadow, final int lo, final int hi, final int d, final int lastShadow)

This is the most hammered method of this class.

pack-priv void
mainSort(final BZip2CompressorOutputStream.Data dataShadow, final int lastShadow)

private static int
med3(final int a, final int b, final int c)

private static void
vswap(final int[] fmap, int p1, int p2, int n)

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

CLEARMASKback to summary
private static final int CLEARMASK
DEPTH_THRESHback to summary
private static final int DEPTH_THRESH
eclassback to summary
private int[] eclass
FALLBACK_QSORT_SMALL_THRESHback to summary
private static final int FALLBACK_QSORT_SMALL_THRESH
FALLBACK_QSORT_STACK_SIZEback to summary
private static final int FALLBACK_QSORT_STACK_SIZE
firstAttemptback to summary
private boolean firstAttempt
ftabback to summary
private final int[] ftab
FTAB_LENGTHback to summary
private static final int FTAB_LENGTH
INCSback to summary
private static final int[] INCS
mainSort_bigDoneback to summary
private final boolean[] mainSort_bigDone
mainSort_copyback to summary
private final int[] mainSort_copy
mainSort_runningOrderback to summary
private final int[] mainSort_runningOrder
QSORT_STACK_SIZEback to summary
private static final int QSORT_STACK_SIZE
quadrantback to summary
private final char[] quadrant

Array instance identical to Data's sfmap, both are used only temporarily and indepently, so we do not need to allocate additional memory.

SETMASKback to summary
private static final int SETMASK
SMALL_THRESHback to summary
private static final int SMALL_THRESH
stack_ddback to summary
private final int[] stack_dd
stack_hhback to summary
private final int[] stack_hh
stack_llback to summary
private final int[] stack_ll
STACK_SIZEback to summary
private static final int STACK_SIZE
WORK_FACTORback to summary
private static final int WORK_FACTOR
workDoneback to summary
private int workDone
workLimitback to summary
private int workLimit

Constructor Detail

BlockSortback to summary
pack-priv BlockSort(final BZip2CompressorOutputStream.Data data)

Method Detail

blockSortback to summary
pack-priv void blockSort(final BZip2CompressorOutputStream.Data data, final int last)
fallbackQSort3back to summary
private void fallbackQSort3(final int[] fmap, final int[] eclass, final int loSt, final int hiSt)
Parameters
fmap:int[]

points to the index of the starting point of a permutation inside the block of data in the current partially sorted order

eclass:int[]

points from the index of a character inside the block to the first index in fmap that contains the bucket of its suffix that is sorted in this step.

loSt:int

lower boundary of the fmap-interval to be sorted

hiSt:int

upper boundary of the fmap-interval to be sorted

fallbackSimpleSortback to summary
private void fallbackSimpleSort(final int[] fmap, final int[] eclass, final int lo, final int hi)
Parameters
fmap:int[]

points to the index of the starting point of a permutation inside the block of data in the current partially sorted order

eclass:int[]

points from the index of a character inside the block to the first index in fmap that contains the bucket of its suffix that is sorted in this step.

lo:int

lower boundary of the fmap-interval to be sorted

hi:int

upper boundary of the fmap-interval to be sorted

fallbackSortback to summary
pack-priv void fallbackSort(final BZip2CompressorOutputStream.Data data, final int last)

Adapt fallbackSort to the expected interface of the rest of the code, in particular deal with the fact that block starts at offset 1 (in libbzip2 1.0.6 it starts at 0).

fallbackSortback to summary
pack-priv void fallbackSort(final int[] fmap, final byte[] block, final int nblock)
Parameters
fmap:int[]

points to the index of the starting point of a permutation inside the block of data in the current partially sorted order

block:byte[]

the original data

nblock:int

size of the block

fpopback to summary
private int[] fpop(final int sp)
fpushback to summary
private void fpush(final int sp, final int lz, final int hz)
fswapback to summary
private void fswap(final int[] fmap, final int zz1, final int zz2)

swaps two values in fmap

fvswapback to summary
private void fvswap(final int[] fmap, int yyp1, int yyp2, int yyn)

swaps two intervals starting at yyp1 and yyp2 of length yyn inside fmap.

getEclassback to summary
private int[] getEclass()
mainQSort3back to summary
private void mainQSort3(final BZip2CompressorOutputStream.Data dataShadow, final int loSt, final int hiSt, final int dSt, final int last)

Method "mainQSort3", file "blocksort.c", BZip2 1.0.2

mainSimpleSortback to summary
private boolean mainSimpleSort(final BZip2CompressorOutputStream.Data dataShadow, final int lo, final int hi, final int d, final int lastShadow)

This is the most hammered method of this class.

This is the version using unrolled loops. Normally I never use such ones in Java code. The unrolling has shown a noticeable performance improvement on JRE 1.4.2 (Linux i586 / HotSpot Client). Of course it depends on the JIT compiler of the vm.

mainSortback to summary
pack-priv void mainSort(final BZip2CompressorOutputStream.Data dataShadow, final int lastShadow)
med3back to summary
private static int med3(final int a, final int b, final int c)
vswapback to summary
private static void vswap(final int[] fmap, int p1, int p2, int n)