ABC: A System for Sequential Synthesis and Verification
 
Loading...
Searching...
No Matches
Macros | Functions
blocksort.c File Reference
#include "bzlib_private.h"
Include dependency graph for blocksort.c:

Go to the source code of this file.

Macros

#define fswap(zz1, zz2)
 
#define fvswap(zzp1, zzp2, zzn)
 
#define fmin(a, b)
 
#define fpush(lz, hz)
 
#define fpop(lz, hz)
 
#define FALLBACK_QSORT_SMALL_THRESH   10
 
#define FALLBACK_QSORT_STACK_SIZE   100
 
#define SET_BH(zz)
 
#define CLEAR_BH(zz)
 
#define ISSET_BH(zz)
 
#define WORD_BH(zz)
 
#define UNALIGNED_BH(zz)
 
#define mswap(zz1, zz2)
 
#define mvswap(zzp1, zzp2, zzn)
 
#define mmin(a, b)
 
#define mpush(lz, hz, dz)
 
#define mpop(lz, hz, dz)
 
#define mnextsize(az)
 
#define mnextswap(az, bz)
 
#define MAIN_QSORT_SMALL_THRESH   20
 
#define MAIN_QSORT_DEPTH_THRESH   (BZ_N_RADIX + BZ_N_QSORT)
 
#define MAIN_QSORT_STACK_SIZE   100
 
#define BIGFREQ(b)
 
#define SETMASK   (1 << 21)
 
#define CLEARMASK   (~(SETMASK))
 

Functions

void BZ2_blockSort (EState *s)
 

Macro Definition Documentation

◆ BIGFREQ

#define BIGFREQ ( b)
Value:
(ftab[((b)+1) << 8] - ftab[(b) << 8])

Definition at line 748 of file blocksort.c.

◆ CLEAR_BH

#define CLEAR_BH ( zz)
Value:
bhtab[(zz) >> 5] &= ~(1 << ((zz) & 31))

Definition at line 208 of file blocksort.c.

◆ CLEARMASK

#define CLEARMASK   (~(SETMASK))

Definition at line 750 of file blocksort.c.

◆ FALLBACK_QSORT_SMALL_THRESH

#define FALLBACK_QSORT_SMALL_THRESH   10

Definition at line 90 of file blocksort.c.

◆ FALLBACK_QSORT_STACK_SIZE

#define FALLBACK_QSORT_STACK_SIZE   100

Definition at line 91 of file blocksort.c.

◆ fmin

#define fmin ( a,
b )
Value:
((a) < (b)) ? (a) : (b)

Definition at line 80 of file blocksort.c.

◆ fpop

#define fpop ( lz,
hz )
Value:
{ sp--; \
lz = stackLo[sp]; \
hz = stackHi[sp]; }

Definition at line 86 of file blocksort.c.

86#define fpop(lz,hz) { sp--; \
87 lz = stackLo[sp]; \
88 hz = stackHi[sp]; }

◆ fpush

#define fpush ( lz,
hz )
Value:
{ stackLo[sp] = lz; \
stackHi[sp] = hz; \
sp++; }

Definition at line 82 of file blocksort.c.

82#define fpush(lz,hz) { stackLo[sp] = lz; \
83 stackHi[sp] = hz; \
84 sp++; }

◆ fswap

#define fswap ( zz1,
zz2 )
Value:
{ Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
Int32
int Int32
Definition bzlib_private.h:46

Definition at line 65 of file blocksort.c.

65#define fswap(zz1, zz2) \
66 { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }

◆ fvswap

#define fvswap ( zzp1,
zzp2,
zzn )
Value:
{ \
Int32 yyp1 = (zzp1); \
Int32 yyp2 = (zzp2); \
Int32 yyn = (zzn); \
while (yyn > 0) { \
fswap(fmap[yyp1], fmap[yyp2]); \
yyp1++; yyp2++; yyn--; \
} \
}

Definition at line 68 of file blocksort.c.

68#define fvswap(zzp1, zzp2, zzn) \
69{ \
70 Int32 yyp1 = (zzp1); \
71 Int32 yyp2 = (zzp2); \
72 Int32 yyn = (zzn); \
73 while (yyn > 0) { \
74 fswap(fmap[yyp1], fmap[yyp2]); \
75 yyp1++; yyp2++; yyn--; \
76 } \
77}

◆ ISSET_BH

#define ISSET_BH ( zz)
Value:
(bhtab[(zz) >> 5] & (1 << ((zz) & 31)))

Definition at line 209 of file blocksort.c.

◆ MAIN_QSORT_DEPTH_THRESH

#define MAIN_QSORT_DEPTH_THRESH   (BZ_N_RADIX + BZ_N_QSORT)

Definition at line 619 of file blocksort.c.

◆ MAIN_QSORT_SMALL_THRESH

#define MAIN_QSORT_SMALL_THRESH   20

Definition at line 618 of file blocksort.c.

◆ MAIN_QSORT_STACK_SIZE

#define MAIN_QSORT_STACK_SIZE   100

Definition at line 620 of file blocksort.c.

◆ mmin

#define mmin ( a,
b )
Value:
((a) < (b)) ? (a) : (b)

Definition at line 596 of file blocksort.c.

◆ mnextsize

#define mnextsize ( az)
Value:
(nextHi[az]-nextLo[az])

Definition at line 609 of file blocksort.c.

◆ mnextswap

#define mnextswap ( az,
bz )
Value:
{ Int32 tz; \
tz = nextLo[az]; nextLo[az] = nextLo[bz]; nextLo[bz] = tz; \
tz = nextHi[az]; nextHi[az] = nextHi[bz]; nextHi[bz] = tz; \
tz = nextD [az]; nextD [az] = nextD [bz]; nextD [bz] = tz; }

Definition at line 611 of file blocksort.c.

611#define mnextswap(az,bz) \
612 { Int32 tz; \
613 tz = nextLo[az]; nextLo[az] = nextLo[bz]; nextLo[bz] = tz; \
614 tz = nextHi[az]; nextHi[az] = nextHi[bz]; nextHi[bz] = tz; \
615 tz = nextD [az]; nextD [az] = nextD [bz]; nextD [bz] = tz; }

◆ mpop

#define mpop ( lz,
hz,
dz )
Value:
{ sp--; \
lz = stackLo[sp]; \
hz = stackHi[sp]; \
dz = stackD [sp]; }

Definition at line 603 of file blocksort.c.

603#define mpop(lz,hz,dz) { sp--; \
604 lz = stackLo[sp]; \
605 hz = stackHi[sp]; \
606 dz = stackD [sp]; }

◆ mpush

#define mpush ( lz,
hz,
dz )
Value:
{ stackLo[sp] = lz; \
stackHi[sp] = hz; \
stackD [sp] = dz; \
sp++; }

Definition at line 598 of file blocksort.c.

598#define mpush(lz,hz,dz) { stackLo[sp] = lz; \
599 stackHi[sp] = hz; \
600 stackD [sp] = dz; \
601 sp++; }

◆ mswap

#define mswap ( zz1,
zz2 )
Value:
{ Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }

Definition at line 569 of file blocksort.c.

569#define mswap(zz1, zz2) \
570 { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }

◆ mvswap

#define mvswap ( zzp1,
zzp2,
zzn )
Value:
{ \
Int32 yyp1 = (zzp1); \
Int32 yyp2 = (zzp2); \
Int32 yyn = (zzn); \
while (yyn > 0) { \
mswap(ptr[yyp1], ptr[yyp2]); \
yyp1++; yyp2++; yyn--; \
} \
}

Definition at line 572 of file blocksort.c.

572#define mvswap(zzp1, zzp2, zzn) \
573{ \
574 Int32 yyp1 = (zzp1); \
575 Int32 yyp2 = (zzp2); \
576 Int32 yyn = (zzn); \
577 while (yyn > 0) { \
578 mswap(ptr[yyp1], ptr[yyp2]); \
579 yyp1++; yyp2++; yyn--; \
580 } \
581}

◆ SET_BH

#define SET_BH ( zz)
Value:
bhtab[(zz) >> 5] |= (1 << ((zz) & 31))

Definition at line 207 of file blocksort.c.

◆ SETMASK

#define SETMASK   (1 << 21)

Definition at line 749 of file blocksort.c.

◆ UNALIGNED_BH

#define UNALIGNED_BH ( zz)
Value:
((zz) & 0x01f)

Definition at line 211 of file blocksort.c.

◆ WORD_BH

#define WORD_BH ( zz)
Value:
bhtab[(zz) >> 5]

Definition at line 210 of file blocksort.c.

Function Documentation

◆ BZ2_blockSort()

void BZ2_blockSort ( EState * s)

Definition at line 1033 of file blocksort.c.

1034{
1035 UInt32* ptr = s->ptr;
1036 UChar* block = s->block;
1037 UInt32* ftab = s->ftab;
1038 Int32 nblock = s->nblock;
1039 Int32 verb = s->verbosity;
1040 Int32 wfact = s->workFactor;
1041 UInt16* quadrant;
1042 Int32 budget;
1043 Int32 budgetInit;
1044 Int32 i;
1045
1046 if (nblock < 10000) {
1047 fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );
1048 } else {
1049 /* Calculate the location for quadrant, remembering to get
1050 the alignment right. Assumes that &(block[0]) is at least
1051 2-byte aligned -- this should be ok since block is really
1052 the first section of arr2.
1053 */
1054 i = nblock+BZ_N_OVERSHOOT;
1055 if (i & 1) i++;
1056 quadrant = (UInt16*)(&(block[i]));
1057
1058 /* (wfact-1) / 3 puts the default-factor-30
1059 transition point at very roughly the same place as
1060 with v0.1 and v0.9.0.
1061 Not that it particularly matters any more, since the
1062 resulting compressed stream is now the same regardless
1063 of whether or not we use the main sort or fallback sort.
1064 */
1065 if (wfact < 1 ) wfact = 1;
1066 if (wfact > 100) wfact = 100;
1067 budgetInit = nblock * ((wfact-1) / 3);
1068 budget = budgetInit;
1069
1070 mainSort ( ptr, block, quadrant, ftab, nblock, verb, &budget );
1071 if (verb >= 3)
1072 VPrintf3 ( " %d work, %d block, ratio %5.2f\n",
1073 budgetInit - budget,
1074 nblock,
1075 (float)(budgetInit - budget) /
1076 (float)(nblock==0 ? 1 : nblock) );
1077 if (budget < 0) {
1078 if (verb >= 2)
1079 VPrintf0 ( " too repetitive; using fallback"
1080 " sorting algorithm\n" );
1081 fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );
1082 }
1083 }
1084
1085 s->origPtr = -1;
1086 for (i = 0; i < s->nblock; i++)
1087 if (ptr[i] == 0)
1088 { s->origPtr = i; break; };
1089
1090 AssertH( s->origPtr != -1, 1003 );
1091}
BZ_N_OVERSHOOT
#define BZ_N_OVERSHOOT
Definition bzlib_private.h:191
UInt32
unsigned int UInt32
Definition bzlib_private.h:47
VPrintf3
#define VPrintf3(zf, za1, za2, za3)
Definition bzlib_private.h:81
UChar
unsigned char UChar
Definition bzlib_private.h:45
AssertH
#define AssertH(cond, errcode)
Definition bzlib_private.h:61
UInt16
unsigned short UInt16
Definition bzlib_private.h:49
VPrintf0
#define VPrintf0(zf)
Definition bzlib_private.h:75
EState::block
UChar * block
Definition bzlib_private.h:219
EState::nblock
Int32 nblock
Definition bzlib_private.h:232
EState::workFactor
Int32 workFactor
Definition bzlib_private.h:224
EState::ftab
UInt32 * ftab
Definition bzlib_private.h:214
EState::ptr
UInt32 * ptr
Definition bzlib_private.h:218
EState::arr1
UInt32 * arr1
Definition bzlib_private.h:212
EState::verbosity
Int32 verbosity
Definition bzlib_private.h:251
EState::arr2
UInt32 * arr2
Definition bzlib_private.h:213
EState::origPtr
Int32 origPtr
Definition bzlib_private.h:215
Here is the caller graph for this function: