commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From bode...@apache.org
Subject svn commit: r1340757 - in /commons/proper/compress/trunk/src: main/java/org/apache/commons/compress/compressors/bzip2/BlockSort.java test/java/org/apache/commons/compress/compressors/bzip2/BlockSortTest.java
Date Sun, 20 May 2012 16:01:21 GMT
Author: bodewig
Date: Sun May 20 16:01:21 2012
New Revision: 1340757

URL: http://svn.apache.org/viewvc?rev=1340757&view=rev
Log:
add fallback sorting algorithm of libbzip2 1.0.6 (actually added with 0.9.5)

Modified:
    commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/bzip2/BlockSort.java
    commons/proper/compress/trunk/src/test/java/org/apache/commons/compress/compressors/bzip2/BlockSortTest.java

Modified: commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/bzip2/BlockSort.java
URL: http://svn.apache.org/viewvc/commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/bzip2/BlockSort.java?rev=1340757&r1=1340756&r2=1340757&view=diff
==============================================================================
--- commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/bzip2/BlockSort.java
(original)
+++ commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/bzip2/BlockSort.java
Sun May 20 16:01:21 2012
@@ -18,6 +18,8 @@
  */
 package org.apache.commons.compress.compressors.bzip2;
 
+import java.util.BitSet;
+
 /**
  * Encapsulates the Burrows-Wheeler sorting algorithm needed by {@link
  * BZip2CompressorOutputStream}.
@@ -92,12 +94,14 @@ class BlockSort {
     /*
      * 2012-05-20 Stefan Bodewig:
      *
-     * The class seems to mix several revisions of libbzip2's code.
+     * This class seems to mix several revisions of libbzip2's code.
      * The mainSort function and those used by it look closer to the
      * 0.9.5 version but show some variations introduced later.  At
      * the same time the logic to randomize the block on bad input has
      * been dropped after 0.9.0 and replaced by a fallback sorting
      * algorithm.
+     *
+     * I've added the fallbackSort function of 1.0.6.
      */
 
     /*
@@ -108,6 +112,12 @@ class BlockSort {
      */
     private static final int QSORT_STACK_SIZE = 1000;
 
+    private static final int FALLBACK_QSORT_STACK_SIZE = 100;
+
+    private static final int STACK_SIZE =
+        QSORT_STACK_SIZE < FALLBACK_QSORT_STACK_SIZE
+        ? FALLBACK_QSORT_STACK_SIZE : QSORT_STACK_SIZE;
+
     private boolean blockRandomised;
 
     /*
@@ -118,8 +128,8 @@ class BlockSort {
     private int workLimit;
     private boolean firstAttempt;
 
-    private final int[] stack_ll = new int[QSORT_STACK_SIZE]; // 4000 byte
-    private final int[] stack_hh = new int[QSORT_STACK_SIZE]; // 4000 byte
+    private final int[] stack_ll = new int[STACK_SIZE]; // 4000 byte
+    private final int[] stack_hh = new int[STACK_SIZE]; // 4000 byte
     private final int[] stack_dd = new int[QSORT_STACK_SIZE]; // 4000 byte
 
     private final int[] mainSort_runningOrder = new int[256]; // 1024 byte
@@ -168,6 +178,350 @@ class BlockSort {
 
 /*---------------------------------------------*/
 
+/*---------------------------------------------*/
+/*--- LBZ2: Fallback O(N log(N)^2) sorting        ---*/
+/*--- algorithm, for repetitive blocks      ---*/
+/*---------------------------------------------*/
+
+    /*
+     * This is the fallback sorting algorithm libbzip2 1.0.6 uses for
+     * repetitive or very short inputs.
+     *
+     * The idea is inspired by Manber-Myers string suffix sorting
+     * algorithm.  First a bucket sort places each permutation of the
+     * block into a bucket based on its first byte.  Permutations are
+     * represented by pointers to their first character kept in
+     * (partially) sorted order inside the array ftab.
+     *
+     * The next step visits all buckets in order and performs a
+     * quicksort on all permutations of the bucket based on the index
+     * of the bucket the second byte of the permutation belongs to,
+     * thereby forming new buckets.  When arrived here the
+     * permutations are sorted up to the second character and we have
+     * buckets of permutations that are identical up to two
+     * characters.
+     *
+     * Repeat the step of quicksorting each bucket, now based on the
+     * bucket holding the sequence of the third and forth character
+     * leading to four byte buckets.  Repeat this doubling of bucket
+     * sizes until all buckets only contain single permutations or the
+     * bucket size exceeds the block size.
+     *
+     * I.e.
+     *
+     * "abraba" form three buckets for the chars "a", "b", and "r" in
+     * the first step with
+     *
+     * fmap = { 'a:' 5, 3, 0, 'b:' 4, 1, 'r', 2 }
+     *
+     * when looking at the bucket of "a"s the second characters are in
+     * the buckets that start with fmap-index 0 (rolled over), 3 and 3
+     * respectively, forming two new buckets "aa" and "ab", so we get
+     *
+     * fmap = { 'aa:' 5, 'ab:' 3, 0, 'ba:' 4, 'br': 1, 'ra:' 2 }
+     *
+     * since the last bucket only contained a single item it didn't
+     * have to be sorted at all.
+     *
+     * There now is just one bucket with more than one permutation
+     * that remains to be sorted.  For the permutation that starts
+     * with index 3 the third and forth char are in bucket 'aa' at
+     * index 0 and for the one starting at block index 0 they are in
+     * bucket 'ra' with sort index 5.  The fully sorted order then becomes.
+     *
+     * fmap = { 5, 3, 0, 4, 1, 2 }
+     * 
+     */
+
+    /**
+     * @param fmap points to the index of the starting point of a
+     *        permutation inside the block of data in the current
+     *        partially sorted order
+     * @param eclass 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.
+     * @param lo lower boundary of the fmap-interval to be sorted 
+     * @param hi upper boundary of the fmap-interval to be sorted 
+     */
+    private void fallbackSimpleSort(int[] fmap, 
+                                    int[] eclass, 
+                                    int lo, 
+                                    int hi) {
+        if (lo == hi) return;
+
+        int j;
+        if (hi - lo > 3) {
+            for (int i = hi - 4; i >= lo; i--) {
+                int tmp = fmap[i];
+                int ec_tmp = eclass[tmp];
+                for (j = i + 4; j <= hi && ec_tmp > eclass[fmap[j]];
+                     j += 4) {
+                    fmap[j - 4] = fmap[j];
+                }
+                fmap[j - 4] = tmp;
+            }
+        }
+
+        for (int i = hi - 1; i >= lo; i--) {
+            int tmp = fmap[i];
+            int ec_tmp = eclass[tmp];
+            for (j = i + 1; j <= hi && ec_tmp > eclass[fmap[j]]; j++) {
+                fmap[j - 1] = fmap[j];
+            }
+            fmap[j-1] = tmp;
+        }
+    }
+
+    private static final int FALLBACK_QSORT_SMALL_THRESH = 10;
+
+    /**
+     * swaps two values in fmap
+     */
+    private void fswap(int[] fmap, int zz1, int zz2) {
+        int zztmp = fmap[zz1];
+        fmap[zz1] = fmap[zz2];
+        fmap[zz2] = zztmp;
+    }
+
+    /**
+     * swaps two intervals starting at yyp1 and yyp2 of length yyn inside fmap.
+     */
+    private void fvswap(int[] fmap, int yyp1, int yyp2, int yyn) {
+        while (yyn > 0) {
+            fswap(fmap, yyp1, yyp2);
+            yyp1++; yyp2++; yyn--;
+        }
+    }
+
+    private int fmin(int a, int b) {
+        return a < b ? a : b;
+    }
+
+    private void fpush(int sp, int lz, int hz) {
+        stack_ll[sp] = lz;
+        stack_hh[sp] = hz;
+    }
+
+    private int[] fpop(int sp) {
+        return new int[] { stack_ll[sp], stack_hh[sp] };
+    }
+
+    /**
+     * @param fmap points to the index of the starting point of a
+     *        permutation inside the block of data in the current
+     *        partially sorted order
+     * @param eclass 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.
+     * @param loSt lower boundary of the fmap-interval to be sorted 
+     * @param hiSt upper boundary of the fmap-interval to be sorted 
+     */
+    private void fallbackQSort3(int[] fmap, 
+                                int[] eclass, 
+                                int loSt, 
+                                int hiSt) {
+        int lo, unLo, ltLo, hi, unHi, gtHi, n;
+
+        long r = 0;
+        int sp = 0;
+        fpush(sp++, loSt, hiSt);
+
+        while (sp > 0) {
+            int[] s = fpop(--sp);
+            lo = s[0]; hi = s[1];
+
+            if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) {
+                fallbackSimpleSort(fmap, eclass, lo, hi);
+                continue;
+            }
+
+            /* LBZ2: Random partitioning.  Median of 3 sometimes fails to
+               avoid bad cases.  Median of 9 seems to help but 
+               looks rather expensive.  This too seems to work but
+               is cheaper.  Guidance for the magic constants 
+               7621 and 32768 is taken from Sedgewick's algorithms
+               book, chapter 35.
+            */
+            r = ((r * 7621) + 1) % 32768;
+            long r3 = r % 3, med;
+            if (r3 == 0) {
+                med = eclass[fmap[lo]]; 
+            } else if (r3 == 1) {
+                med = eclass[fmap[(lo+hi)>>1]];
+            } else {
+                med = eclass[fmap[hi]];
+            }
+
+            unLo = ltLo = lo;
+            unHi = gtHi = hi;
+
+            // looks like the ternary partition attributed to Wegner
+            // in the cited Sedgewick paper
+            while (true) {
+                while (true) {
+                    if (unLo > unHi) break;
+                    n = eclass[fmap[unLo]] - (int) med;
+                    if (n == 0) { 
+                        fswap(fmap, unLo, ltLo); 
+                        ltLo++; unLo++; 
+                        continue; 
+                    };
+                    if (n > 0) break;
+                    unLo++;
+                }
+                while (true) {
+                    if (unLo > unHi) break;
+                    n = eclass[fmap[unHi]] - (int) med;
+                    if (n == 0) {
+                        fswap(fmap, unHi, gtHi); 
+                        gtHi--; unHi--; 
+                        continue; 
+                    };
+                    if (n < 0) break;
+                    unHi--;
+                }
+                if (unLo > unHi) break;
+                fswap(fmap, unLo, unHi); unLo++; unHi--;
+            }
+
+            if (gtHi < ltLo) continue;
+
+            n = fmin(ltLo - lo, unLo - ltLo);
+            fvswap(fmap, lo, unLo - n, n);
+            int m = fmin(hi - gtHi, gtHi - unHi);
+            fvswap(fmap, unHi + 1, hi - m + 1, m);
+
+            n = lo + unLo - ltLo - 1;
+            m = hi - (gtHi - unHi) + 1;
+
+            if (n - lo > hi - m) {
+                fpush(sp++, lo, n);
+                fpush(sp++, m, hi);
+            } else {
+                fpush(sp++, m, hi);
+                fpush(sp++, lo, n);
+            }
+        }
+    }
+
+
+/*---------------------------------------------*/
+
+    private int[] eclass;
+
+    private int[] getEclass() {
+        return eclass == null
+            ? (eclass = new int[quadrant.length / 2]) : eclass;
+    }
+
+    /*
+     * The C code uses an array of ints to represents the bucket-start
+     * flags (bhtab).  It also contains optimizations to skip over 32
+     * consecutively set or consecutively unset bits on word
+     * boundaries at once.  For now I've chosen to use the simpler but
+     * potentially slower code using BitSet - also in the hope that
+     * using the BitSet#nextXXX methods may be fast enough.
+     */
+
+    /**
+     * @param fmap points to the index of the starting point of a
+     *        permutation inside the block of data in the current
+     *        partially sorted order
+     * @param block the original data
+     * @param nblock size of the block
+     * @param off offset of first byte to sort in block
+     */
+    final void fallbackSort(int[] fmap, byte[] block, int nblock) {
+        int[] ftab = new int[257];
+        int H, i, j, k, l, r, cc, cc1;
+        int nNotDone;
+        int nBhtab;
+
+        /*--
+          LBZ2: Initial 1-char radix sort to generate
+          initial fmap and initial BH bits.
+          --*/
+        for (i = 0; i < nblock; i++) ftab[block[i] & 0xff]++;
+        for (i = 1; i < 257;    i++) ftab[i] += ftab[i - 1];
+
+        for (i = 0; i < nblock; i++) {
+            j = block[i] & 0xff;
+            k = ftab[j] - 1;
+            ftab[j] = k;
+            fmap[k] = i;
+        }
+
+        nBhtab = 64 + nblock;
+        BitSet bhtab = new BitSet(nBhtab);
+        for (i = 0; i < 256; i++) bhtab.set(ftab[i]);
+
+        /*--
+          LBZ2: Inductively refine the buckets.  Kind-of an
+          "exponential radix sort" (!), inspired by the
+          Manber-Myers suffix array construction algorithm.
+          --*/
+
+        /*-- LBZ2: set sentinel bits for block-end detection --*/
+        for (i = 0; i < 32; i++) { 
+            bhtab.set(nblock + 2 * i);
+            bhtab.clear(nblock + 2 * i + 1);
+        }
+
+        eclass = getEclass();
+
+        /*-- LBZ2: the log(N) loop --*/
+        H = 1;
+        while (true) {
+
+            j = 0;
+            for (i = 0; i < nblock; i++) {
+                if (bhtab.get(i)) {
+                    j = i;
+                }
+                k = fmap[i] - H;
+                if (k < 0) {
+                    k += nblock;
+                }
+                eclass[k] = j;
+            }
+
+            nNotDone = 0;
+            r = -1;
+            while (true) {
+
+                /*-- LBZ2: find the next non-singleton bucket --*/
+                k = r + 1;
+                k = bhtab.nextSetBit(k);
+                l = k - 1;
+                if (l >= nblock) break;
+                k = bhtab.nextClearBit(k);
+                r = k - 1;
+                if (r >= nblock) break;
+
+                /*-- LBZ2: now [l, r] bracket current bucket --*/
+                if (r > l) {
+                    nNotDone += (r - l + 1);
+                    fallbackQSort3(fmap, eclass, l, r);
+
+                    /*-- LBZ2: scan bucket and generate header bits-- */
+                    cc = -1;
+                    for (i = l; i <= r; i++) {
+                        cc1 = eclass[fmap[i]];
+                        if (cc != cc1) {
+                            bhtab.set(i);
+                            cc = cc1;
+                        };
+                    }
+                }
+            }
+
+            H *= 2;
+            if (H > nblock || nNotDone == 0) break;
+        }
+    }
+
+/*---------------------------------------------*/
+
     /*
      * LBZ2: Knuth's increments seem to work better than Incerpi-Sedgewick here.
      * Possibly because the number of elems to sort is usually small, typically

Modified: commons/proper/compress/trunk/src/test/java/org/apache/commons/compress/compressors/bzip2/BlockSortTest.java
URL: http://svn.apache.org/viewvc/commons/proper/compress/trunk/src/test/java/org/apache/commons/compress/compressors/bzip2/BlockSortTest.java?rev=1340757&r1=1340756&r2=1340757&view=diff
==============================================================================
--- commons/proper/compress/trunk/src/test/java/org/apache/commons/compress/compressors/bzip2/BlockSortTest.java
(original)
+++ commons/proper/compress/trunk/src/test/java/org/apache/commons/compress/compressors/bzip2/BlockSortTest.java
Sun May 20 16:01:21 2012
@@ -66,6 +66,10 @@ public class BlockSortTest {
     private static final byte[] FIXTURE_BWT = { (byte) 128, 0, 3, (byte) 254, 2, 1, 
                                                 (byte) 252, (byte) 255, (byte) 253 };
 
+    private static final int[] FIXTURE_SORTED = {
+        0, 1, 7, 6, 8, 2, 3, 5, 4
+    };
+
     @Test
     public void testSortFixture() {
         BZip2CompressorOutputStream.Data data = new BZip2CompressorOutputStream.Data(1);
@@ -78,4 +82,13 @@ public class BlockSortTest {
         }
         assertEquals(0, data.origPtr);
     }
+
+    @Test
+    public void testFallbackSort() {
+        BZip2CompressorOutputStream.Data data = new BZip2CompressorOutputStream.Data(1);
+        BlockSort s = new BlockSort(data);
+        int[] fmap = new int[FIXTURE.length];
+        s.fallbackSort(fmap, FIXTURE, FIXTURE.length);
+        assertArrayEquals(FIXTURE_SORTED, fmap);
+    }
 }
\ No newline at end of file



Mime
View raw message