📄 bzip2outputstream.cs
字号:
}
unHi--;
}
if (unLo > unHi) {
break;
}
{
int temp = zptr[unLo];
zptr[unLo] = zptr[unHi];
zptr[unHi] = temp;
unLo++;
unHi--;
}
}
if (gtHi < ltLo) {
stack[sp].ll = lo;
stack[sp].hh = hi;
stack[sp].dd = d+1;
sp++;
continue;
}
n = ((ltLo-lo) < (unLo-ltLo)) ? (ltLo-lo) : (unLo-ltLo);
Vswap(lo, unLo-n, n);
m = ((hi-gtHi) < (gtHi-unHi)) ? (hi-gtHi) : (gtHi-unHi);
Vswap(unLo, hi-m+1, m);
n = lo + unLo - ltLo - 1;
m = hi - (gtHi - unHi) + 1;
stack[sp].ll = lo;
stack[sp].hh = n;
stack[sp].dd = d;
sp++;
stack[sp].ll = n + 1;
stack[sp].hh = m - 1;
stack[sp].dd = d+1;
sp++;
stack[sp].ll = m;
stack[sp].hh = hi;
stack[sp].dd = d;
sp++;
}
}
void MainSort()
{
int i, j, ss, sb;
int[] runningOrder = new int[256];
int[] copy = new int[256];
bool[] bigDone = new bool[256];
int c1, c2;
int numQSorted;
/*--
In the various block-sized structures, live data runs
from 0 to last+NUM_OVERSHOOT_BYTES inclusive. First,
set up the overshoot area for block.
--*/
// if (verbosity >= 4) fprintf ( stderr, " sort initialise ...\n" );
for (i = 0; i < BZip2Constants.NUM_OVERSHOOT_BYTES; i++) {
block[last + i + 2] = block[(i % (last + 1)) + 1];
}
for (i = 0; i <= last + BZip2Constants.NUM_OVERSHOOT_BYTES; i++) {
quadrant[i] = 0;
}
block[0] = (byte)(block[last + 1]);
if (last < 4000) {
/*--
Use simpleSort(), since the full sorting mechanism
has quite a large constant overhead.
--*/
for (i = 0; i <= last; i++) {
zptr[i] = i;
}
firstAttempt = false;
workDone = workLimit = 0;
SimpleSort(0, last, 0);
} else {
numQSorted = 0;
for (i = 0; i <= 255; i++) {
bigDone[i] = false;
}
for (i = 0; i <= 65536; i++) {
ftab[i] = 0;
}
c1 = block[0];
for (i = 0; i <= last; i++) {
c2 = block[i + 1];
ftab[(c1 << 8) + c2]++;
c1 = c2;
}
for (i = 1; i <= 65536; i++) {
ftab[i] += ftab[i - 1];
}
c1 = block[1];
for (i = 0; i < last; i++) {
c2 = block[i + 2];
j = (c1 << 8) + c2;
c1 = c2;
ftab[j]--;
zptr[ftab[j]] = i;
}
j = ((block[last + 1]) << 8) + (block[1]);
ftab[j]--;
zptr[ftab[j]] = last;
/*--
Now ftab contains the first loc of every small bucket.
Calculate the running order, from smallest to largest
big bucket.
--*/
for (i = 0; i <= 255; i++) {
runningOrder[i] = i;
}
int vv;
int h = 1;
do {
h = 3 * h + 1;
} while (h <= 256);
do {
h = h / 3;
for (i = h; i <= 255; i++) {
vv = runningOrder[i];
j = i;
while ((ftab[((runningOrder[j-h])+1) << 8] - ftab[(runningOrder[j-h]) << 8]) > (ftab[((vv)+1) << 8] - ftab[(vv) << 8])) {
runningOrder[j] = runningOrder[j-h];
j = j - h;
if (j <= (h - 1)) {
break;
}
}
runningOrder[j] = vv;
}
} while (h != 1);
/*--
The main sorting loop.
--*/
for (i = 0; i <= 255; i++) {
/*--
Process big buckets, starting with the least full.
--*/
ss = runningOrder[i];
/*--
Complete the big bucket [ss] by quicksorting
any unsorted small buckets [ss, j]. Hopefully
previous pointer-scanning phases have already
completed many of the small buckets [ss, j], so
we don't have to sort them at all.
--*/
for (j = 0; j <= 255; j++) {
sb = (ss << 8) + j;
if(!((ftab[sb] & SETMASK) == SETMASK)) {
int lo = ftab[sb] & CLEARMASK;
int hi = (ftab[sb+1] & CLEARMASK) - 1;
if (hi > lo) {
QSort3(lo, hi, 2);
numQSorted += (hi - lo + 1);
if (workDone > workLimit && firstAttempt) {
return;
}
}
ftab[sb] |= SETMASK;
}
}
/*--
The ss big bucket is now done. Record this fact,
and update the quadrant descriptors. Remember to
update quadrants in the overshoot area too, if
necessary. The "if (i < 255)" test merely skips
this updating for the last bucket processed, since
updating for the last bucket is pointless.
--*/
bigDone[ss] = true;
if (i < 255) {
int bbStart = ftab[ss << 8] & CLEARMASK;
int bbSize = (ftab[(ss+1) << 8] & CLEARMASK) - bbStart;
int shifts = 0;
while ((bbSize >> shifts) > 65534) {
shifts++;
}
for (j = 0; j < bbSize; j++) {
int a2update = zptr[bbStart + j];
int qVal = (j >> shifts);
quadrant[a2update] = qVal;
if (a2update < BZip2Constants.NUM_OVERSHOOT_BYTES) {
quadrant[a2update + last + 1] = qVal;
}
}
if (!(((bbSize-1) >> shifts) <= 65535)) {
Panic();
}
}
/*--
Now scan this big bucket so as to synthesise the
sorted order for small buckets [t, ss] for all t != ss.
--*/
for (j = 0; j <= 255; j++) {
copy[j] = ftab[(j << 8) + ss] & CLEARMASK;
}
for (j = ftab[ss << 8] & CLEARMASK; j < (ftab[(ss+1) << 8] & CLEARMASK); j++) {
c1 = block[zptr[j]];
if (!bigDone[c1]) {
zptr[copy[c1]] = zptr[j] == 0 ? last : zptr[j] - 1;
copy[c1] ++;
}
}
for (j = 0; j <= 255; j++) {
ftab[(j << 8) + ss] |= SETMASK;
}
}
}
}
void RandomiseBlock()
{
int i;
int rNToGo = 0;
int rTPos = 0;
for (i = 0; i < 256; i++) {
inUse[i] = false;
}
for (i = 0; i <= last; i++) {
if (rNToGo == 0) {
rNToGo = (int)BZip2Constants.rNums[rTPos];
rTPos++;
if (rTPos == 512) {
rTPos = 0;
}
}
rNToGo--;
block[i + 1] ^= (byte)((rNToGo == 1) ? 1 : 0);
// handle 16 bit signed numbers
block[i + 1] &= 0xFF;
inUse[block[i + 1]] = true;
}
}
void DoReversibleTransformation()
{
workLimit = workFactor * last;
workDone = 0;
blockRandomised = false;
firstAttempt = true;
MainSort();
if (workDone > workLimit && firstAttempt) {
RandomiseBlock();
workLimit = workDone = 0;
blockRandomised = true;
firstAttempt = false;
MainSort();
}
origPtr = -1;
for (int i = 0; i <= last; i++) {
if (zptr[i] == 0) {
origPtr = i;
break;
}
}
if (origPtr == -1) {
Panic();
}
}
bool FullGtU(int i1, int i2)
{
int k;
byte c1, c2;
int s1, s2;
c1 = block[i1 + 1];
c2 = block[i2 + 1];
if (c1 != c2) {
return c1 > c2;
}
i1++;
i2++;
c1 = block[i1 + 1];
c2 = block[i2 + 1];
if (c1 != c2) {
return c1 > c2;
}
i1++;
i2++;
c1 = block[i1 + 1];
c2 = block[i2 + 1];
if (c1 != c2) {
return c1 > c2;
}
i1++;
i2++;
c1 = block[i1 + 1];
c2 = block[i2 + 1];
if (c1 != c2) {
return c1 > c2;
}
i1++;
i2++;
c1 = block[i1 + 1];
c2 = block[i2 + 1];
if (c1 != c2) {
return c1 > c2;
}
i1++;
i2++;
c1 = block[i1 + 1];
c2 = block[i2 + 1];
if (c1 != c2) {
return c1 > c2;
}
i1++;
i2++;
k = last + 1;
do {
c1 = block[i1 + 1];
c2 = block[i2 + 1];
if (c1 != c2) {
return c1 > c2;
}
s1 = quadrant[i1];
s2 = quadrant[i2];
if (s1 != s2) {
return s1 > s2;
}
i1++;
i2++;
c1 = block[i1 + 1];
c2 = block[i2 + 1];
if (c1 != c2) {
return c1 > c2;
}
s1 = quadrant[i1];
s2 = quadrant[i2];
if (s1 != s2) {
return s1 > s2;
}
i1++;
i2++;
c1 = block[i1 + 1];
c2 = block[i2 + 1];
if (c1 != c2) {
return c1 > c2;
}
s1 = quadrant[i1];
s2 = quadrant[i2];
if (s1 != s2) {
return s1 > s2;
}
i1++;
i2++;
c1 = block[i1 + 1];
c2 = block[i2 + 1];
if (c1 != c2) {
return c1 > c2;
}
s1 = quadrant[i1];
s2 = quadrant[i2];
if (s1 != s2) {
return s1 > s2;
}
i1++;
i2++;
if (i1 > last) {
i1 -= last;
i1--;
}
if (i2 > last) {
i2 -= last;
i2--;
}
k -= 4;
++workDone;
} while (k >= 0);
return false;
}
/*--
Knuth's increments seem to work better
than Incerpi-Sedgewick here. Possibly
because the number of elems to sort is
usually small, typically <= 20.
--*/
readonly int[] incs = new int[] {
1, 4, 13, 40, 121, 364, 1093, 3280,
9841, 29524, 88573, 265720,
797161, 2391484
};
void AllocateCompressStructures()
{
int n = BZip2Constants.baseBlockSize * blockSize100k;
block = new byte[(n + 1 + BZip2Constants.NUM_OVERSHOOT_BYTES)];
quadrant = new int[(n + BZip2Constants.NUM_OVERSHOOT_BYTES)];
zptr = new int[n];
ftab = new int[65537];
if (block == null || quadrant == null || zptr == null || ftab == null) {
// int totalDraw = (n + 1 + NUM_OVERSHOOT_BYTES) + (n + NUM_OVERSHOOT_BYTES) + n + 65537;
// compressOutOfMemory ( totalDraw, n );
}
/*
The back end needs a place to store the MTF values
whilst it calculates the coding tables. We could
put them in the zptr array. However, these values
will fit in a short, so we overlay szptr at the
start of zptr, in the hope of reducing the number
of cache misses induced by the multiple traversals
of the MTF values when calculating coding tables.
Seems to improve compression speed by about 1%.
*/
// szptr = zptr;
szptr = new short[2 * n];
}
void GenerateMTFValues()
{
char[] yy = new char[256];
int i, j;
char tmp;
char tmp2;
int zPend;
int wr;
int EOB;
MakeMaps();
EOB = nInUse+1;
for (i = 0; i <= EOB; i++) {
mtfFreq[i] = 0;
}
wr = 0;
zPend = 0;
for (i = 0; i < nInUse; i++) {
yy[i] = (char) i;
}
for (i = 0; i <= last; i++) {
char ll_i;
ll_i = unseqToSeq[block[zptr[i]]];
j = 0;
tmp = yy[j];
while (ll_i != tmp) {
j++;
tmp2 = tmp;
tmp = yy[j];
yy[j] = tmp2;
}
yy[0] = tmp;
if (j == 0) {
zPend++;
} else {
if (zPend > 0) {
zPend--;
while (true) {
switch (zPend % 2) {
case 0:
szptr[wr] = (short)BZip2Constants.RUNA;
wr++;
mtfFreq[BZip2Constants.RUNA]++;
break;
case 1:
szptr[wr] = (short)BZip2Constants.RUNB;
wr++;
mtfFreq[BZip2Constants.RUNB]++;
break;
}
if (zPend < 2) {
break;
}
zPend = (zPend - 2) / 2;
}
zPend = 0;
}
szptr[wr] = (short)(j + 1);
wr++;
mtfFreq[j + 1]++;
}
}
if (zPend > 0) {
zPend--;
while (true) {
switch (zPend % 2) {
case 0:
szptr[wr] = (short)BZip2Constants.RUNA;
wr++;
mtfFreq[BZip2Constants.RUNA]++;
break;
case 1:
szptr[wr] = (short)BZip2Constants.RUNB;
wr++;
mtfFreq[BZip2Constants.RUNB]++;
break;
}
if (zPend < 2) {
break;
}
zPend = (zPend - 2) / 2;
}
}
szptr[wr] = (short)EOB;
wr++;
mtfFreq[EOB]++;
nMTF = wr;
}
}
}
/* This file was derived from a file containing under this license:
*
* This file is a part of bzip2 and/or libbzip2, a program and
* library for lossless, block-sorting data compression.
*
* Copyright (C) 1996-1998 Julian R Seward. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. The origin of this software must not be misrepresented; you must
* not claim that you wrote the original software. If you use this
* software in a product, an acknowledgment in the product
* documentation would be appreciated but is not required.
*
* 3. Altered source versions must be plainly marked as such, and must
* not be misrepresented as being the original software.
*
* 4. The name of the author may not be used to endorse or promote
* products derived from this software without specific prior written
* permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
* OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
* GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
* WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
* Java version ported by Keiron Liddle, Aftex Software <keiron@aftexsw.com> 1999-2001
*/
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -