Top Description Fields Constructors Methods
org.apache.tools.bzip2

pack-priv Class BlockSort

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

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 addition 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[]
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 independently, 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 CBZip2OutputStream.Data data)

Method Summary

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

private void
fallbackQSort3(int[]
points to the index of the starting point of a permutation inside the block of data in the current partially sorted order
fmap, 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, int
lower boundary of the fmap-interval to be sorted
loSt, int
upper boundary of the fmap-interval to be sorted
hiSt)

private void
fallbackSimpleSort(int[]
points to the index of the starting point of a permutation inside the block of data in the current partially sorted order
fmap, 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, int
lower boundary of the fmap-interval to be sorted
lo, int
upper boundary of the fmap-interval to be sorted
hi)

pack-priv final void
fallbackSort(final CBZip2OutputStream.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 final void
fallbackSort(int[]
points to the index of the starting point of a permutation inside the block of data in the current partially sorted order
fmap, byte[]
the original data
block, int
size of the block
nblock)

private int
fmin(int a, int b)

private int[]
fpop(int sp)

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

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

swaps two values in fmap

private void
fvswap(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 CBZip2OutputStream.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 CBZip2OutputStream.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 final void
mainSort(final CBZip2OutputStream.Data dataShadow, final int lastShadow)

private static byte
med3(byte a, byte b, byte c)

private static void
vswap(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
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 independently, 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
Annotations
@SuppressWarnings:unused
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 CBZip2OutputStream.Data data)

Method Detail

blockSortback to summary
pack-priv void blockSort(final CBZip2OutputStream.Data data, final int last)
fallbackQSort3back to summary
private void fallbackQSort3(int[] fmap, int[] eclass, int loSt, 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(int[] fmap, int[] eclass, int lo, 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 final void fallbackSort(final CBZip2OutputStream.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 final void fallbackSort(int[] fmap, byte[] block, 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

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

swaps two values in fmap

fvswapback to summary
private void fvswap(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 CBZip2OutputStream.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 CBZip2OutputStream.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 final void mainSort(final CBZip2OutputStream.Data dataShadow, final int lastShadow)
med3back to summary
private static byte med3(byte a, byte b, byte c)
vswapback to summary
private static void vswap(int[] fmap, int p1, int p2, int n)