12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120 |
- #include "libbb.h"
- #include "archive.h"
- #ifdef DEBUG
- # define Assert(cond,msg) { if (!(cond)) bb_error_msg(msg); }
- # define Trace(x) fprintf x
- # define Tracev(x) {if (verbose) fprintf x; }
- # define Tracevv(x) {if (verbose > 1) fprintf x; }
- # define Tracec(c,x) {if (verbose && (c)) fprintf x; }
- # define Tracecv(c,x) {if (verbose > 1 && (c)) fprintf x; }
- #else
- # define Assert(cond,msg)
- # define Trace(x)
- # define Tracev(x)
- # define Tracevv(x)
- # define Tracec(c,x)
- # define Tracecv(c,x)
- #endif
- #define SMALL_MEM
- #ifndef INBUFSIZ
- # ifdef SMALL_MEM
- # define INBUFSIZ 0x2000
- # else
- # define INBUFSIZ 0x8000
- # endif
- #endif
- #ifndef OUTBUFSIZ
- # ifdef SMALL_MEM
- # define OUTBUFSIZ 8192
- # else
- # define OUTBUFSIZ 16384
- # endif
- #endif
- #ifndef DIST_BUFSIZE
- # ifdef SMALL_MEM
- # define DIST_BUFSIZE 0x2000
- # else
- # define DIST_BUFSIZE 0x8000
- # endif
- #endif
- #define ASCII_FLAG 0x01
- #define CONTINUATION 0x02
- #define EXTRA_FIELD 0x04
- #define ORIG_NAME 0x08
- #define COMMENT 0x10
- #define RESERVED 0xC0
- #define UNKNOWN 0xffff
- #define BINARY 0
- #define ASCII 1
- #ifndef WSIZE
- # define WSIZE 0x8000
- #endif
- #define MIN_MATCH 3
- #define MAX_MATCH 258
- #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
- #define MAX_DIST (WSIZE-MIN_LOOKAHEAD)
- #ifndef MAX_PATH_LEN
- # define MAX_PATH_LEN 1024
- #endif
- #define seekable() 0
- #define translate_eol 0
- #ifndef BITS
- # define BITS 16
- #endif
- #define INIT_BITS 9
- #define BIT_MASK 0x1f
- #ifdef MAX_EXT_CHARS
- # define MAX_SUFFIX MAX_EXT_CHARS
- #else
- # define MAX_SUFFIX 30
- #endif
- #ifdef SMALL_MEM
- # define HASH_BITS 13
- #endif
- #ifdef MEDIUM_MEM
- # define HASH_BITS 14
- #endif
- #ifndef HASH_BITS
- # define HASH_BITS 15
-
- #endif
- #define HASH_SIZE (unsigned)(1<<HASH_BITS)
- #define HASH_MASK (HASH_SIZE-1)
- #define WMASK (WSIZE-1)
- #ifndef TOO_FAR
- # define TOO_FAR 4096
- #endif
- typedef uint8_t uch;
- typedef uint16_t ush;
- typedef uint32_t ulg;
- typedef int32_t lng;
- typedef ush Pos;
- typedef unsigned IPos;
- enum {
- WINDOW_SIZE = 2 * WSIZE,
- max_chain_length = 4096,
- max_lazy_match = 258,
- max_insert_length = max_lazy_match,
- good_match = 32,
- nice_match = 258,
- };
- struct globals {
- lng block_start;
- unsigned ins_h;
- #define H_SHIFT ((HASH_BITS+MIN_MATCH-1) / MIN_MATCH)
- unsigned prev_length;
- unsigned strstart;
- unsigned match_start;
- unsigned lookahead;
- #define DECLARE(type, array, size) \
- type * array
- #define ALLOC(type, array, size) \
- array = xzalloc((size_t)(((size)+1L)/2) * 2*sizeof(type))
- #define FREE(array) \
- do { free(array); array = NULL; } while (0)
-
-
-
- DECLARE(uch, l_buf, INBUFSIZ);
- DECLARE(ush, d_buf, DIST_BUFSIZE);
- DECLARE(uch, outbuf, OUTBUFSIZ);
- DECLARE(uch, window, 2L * WSIZE);
-
- DECLARE(ush, prev, 1L << BITS);
-
- #define head (G1.prev + WSIZE)
- ulg isize;
- #define ifd STDIN_FILENO
- #define ofd STDOUT_FILENO
- #ifdef DEBUG
- unsigned insize;
- #endif
- unsigned outcnt;
- smallint eofile;
- unsigned short bi_buf;
- #undef BUF_SIZE
- #define BUF_SIZE (8 * sizeof(G1.bi_buf))
- int bi_valid;
- #ifdef DEBUG
- ulg bits_sent;
- #endif
-
- uint32_t crc;
- };
- #define G1 (*(ptr_to_globals - 1))
- static void flush_outbuf(void)
- {
- if (G1.outcnt == 0)
- return;
- xwrite(ofd, (char *) G1.outbuf, G1.outcnt);
- G1.outcnt = 0;
- }
- #define put_8bit(c) \
- do { \
- G1.outbuf[G1.outcnt++] = (c); \
- if (G1.outcnt == OUTBUFSIZ) flush_outbuf(); \
- } while (0)
- static void put_16bit(ush w)
- {
- if (G1.outcnt < OUTBUFSIZ - 2) {
- G1.outbuf[G1.outcnt++] = w;
- G1.outbuf[G1.outcnt++] = w >> 8;
- } else {
- put_8bit(w);
- put_8bit(w >> 8);
- }
- }
- static void put_32bit(ulg n)
- {
- put_16bit(n);
- put_16bit(n >> 16);
- }
- static void updcrc(uch * s, unsigned n)
- {
- G1.crc = crc32_block_endian0(G1.crc, s, n, global_crc32_table );
- }
- static unsigned file_read(void *buf, unsigned size)
- {
- unsigned len;
- Assert(G1.insize == 0, "l_buf not empty");
- len = safe_read(ifd, buf, size);
- if (len == (unsigned)(-1) || len == 0)
- return len;
- updcrc(buf, len);
- G1.isize += len;
- return len;
- }
- static void send_bits(int value, int length)
- {
- #ifdef DEBUG
- Tracev((stderr, " l %2d v %4x ", length, value));
- Assert(length > 0 && length <= 15, "invalid length");
- G1.bits_sent += length;
- #endif
-
- if (G1.bi_valid > (int) BUF_SIZE - length) {
- G1.bi_buf |= (value << G1.bi_valid);
- put_16bit(G1.bi_buf);
- G1.bi_buf = (ush) value >> (BUF_SIZE - G1.bi_valid);
- G1.bi_valid += length - BUF_SIZE;
- } else {
- G1.bi_buf |= value << G1.bi_valid;
- G1.bi_valid += length;
- }
- }
- static unsigned bi_reverse(unsigned code, int len)
- {
- unsigned res = 0;
- while (1) {
- res |= code & 1;
- if (--len <= 0) return res;
- code >>= 1;
- res <<= 1;
- }
- }
- static void bi_windup(void)
- {
- if (G1.bi_valid > 8) {
- put_16bit(G1.bi_buf);
- } else if (G1.bi_valid > 0) {
- put_8bit(G1.bi_buf);
- }
- G1.bi_buf = 0;
- G1.bi_valid = 0;
- #ifdef DEBUG
- G1.bits_sent = (G1.bits_sent + 7) & ~7;
- #endif
- }
- static void copy_block(char *buf, unsigned len, int header)
- {
- bi_windup();
- if (header) {
- put_16bit(len);
- put_16bit(~len);
- #ifdef DEBUG
- G1.bits_sent += 2 * 16;
- #endif
- }
- #ifdef DEBUG
- G1.bits_sent += (ulg) len << 3;
- #endif
- while (len--) {
- put_8bit(*buf++);
- }
- }
- static void fill_window(void)
- {
- unsigned n, m;
- unsigned more = WINDOW_SIZE - G1.lookahead - G1.strstart;
-
-
- if (more == (unsigned) -1) {
-
- more--;
- } else if (G1.strstart >= WSIZE + MAX_DIST) {
-
- Assert(WINDOW_SIZE == 2 * WSIZE, "no sliding with BIG_MEM");
- memcpy(G1.window, G1.window + WSIZE, WSIZE);
- G1.match_start -= WSIZE;
- G1.strstart -= WSIZE;
- G1.block_start -= WSIZE;
- for (n = 0; n < HASH_SIZE; n++) {
- m = head[n];
- head[n] = (Pos) (m >= WSIZE ? m - WSIZE : 0);
- }
- for (n = 0; n < WSIZE; n++) {
- m = G1.prev[n];
- G1.prev[n] = (Pos) (m >= WSIZE ? m - WSIZE : 0);
-
- }
- more += WSIZE;
- }
-
- if (!G1.eofile) {
- n = file_read(G1.window + G1.strstart + G1.lookahead, more);
- if (n == 0 || n == (unsigned) -1) {
- G1.eofile = 1;
- } else {
- G1.lookahead += n;
- }
- }
- }
- static int longest_match(IPos cur_match)
- {
- unsigned chain_length = max_chain_length;
- uch *scan = G1.window + G1.strstart;
- uch *match;
- int len;
- int best_len = G1.prev_length;
- IPos limit = G1.strstart > (IPos) MAX_DIST ? G1.strstart - (IPos) MAX_DIST : 0;
-
- #if HASH_BITS < 8 || MAX_MATCH != 258
- # error Code too clever
- #endif
- uch *strend = G1.window + G1.strstart + MAX_MATCH;
- uch scan_end1 = scan[best_len - 1];
- uch scan_end = scan[best_len];
-
- if (G1.prev_length >= good_match) {
- chain_length >>= 2;
- }
- Assert(G1.strstart <= WINDOW_SIZE - MIN_LOOKAHEAD, "insufficient lookahead");
- do {
- Assert(cur_match < G1.strstart, "no future");
- match = G1.window + cur_match;
-
- if (match[best_len] != scan_end
- || match[best_len - 1] != scan_end1
- || *match != *scan || *++match != scan[1]
- ) {
- continue;
- }
-
- scan += 2, match++;
-
- do {
- } while (*++scan == *++match && *++scan == *++match &&
- *++scan == *++match && *++scan == *++match &&
- *++scan == *++match && *++scan == *++match &&
- *++scan == *++match && *++scan == *++match && scan < strend);
- len = MAX_MATCH - (int) (strend - scan);
- scan = strend - MAX_MATCH;
- if (len > best_len) {
- G1.match_start = cur_match;
- best_len = len;
- if (len >= nice_match)
- break;
- scan_end1 = scan[best_len - 1];
- scan_end = scan[best_len];
- }
- } while ((cur_match = G1.prev[cur_match & WMASK]) > limit
- && --chain_length != 0);
- return best_len;
- }
- #ifdef DEBUG
- static void check_match(IPos start, IPos match, int length)
- {
-
- if (memcmp(G1.window + match, G1.window + start, length) != 0) {
- bb_error_msg(" start %d, match %d, length %d", start, match, length);
- bb_error_msg("invalid match");
- }
- if (verbose > 1) {
- bb_error_msg("\\[%d,%d]", start - match, length);
- do {
- bb_putchar_stderr(G1.window[start++]);
- } while (--length != 0);
- }
- }
- #else
- # define check_match(start, match, length) ((void)0)
- #endif
- #define MAX_BITS 15
- #define MAX_BL_BITS 7
- #define LENGTH_CODES 29
- #define LITERALS 256
- #define END_BLOCK 256
- #define L_CODES (LITERALS+1+LENGTH_CODES)
- #define D_CODES 30
- #define BL_CODES 19
- static const uint8_t extra_lbits[LENGTH_CODES] ALIGN1 = {
- 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4,
- 4, 4, 5, 5, 5, 5, 0
- };
- static const uint8_t extra_dbits[D_CODES] ALIGN1 = {
- 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9,
- 10, 10, 11, 11, 12, 12, 13, 13
- };
- static const uint8_t extra_blbits[BL_CODES] ALIGN1 = {
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7 };
- static const uint8_t bl_order[BL_CODES] ALIGN1 = {
- 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
- #define STORED_BLOCK 0
- #define STATIC_TREES 1
- #define DYN_TREES 2
- #ifndef LIT_BUFSIZE
- # ifdef SMALL_MEM
- # define LIT_BUFSIZE 0x2000
- # else
- # ifdef MEDIUM_MEM
- # define LIT_BUFSIZE 0x4000
- # else
- # define LIT_BUFSIZE 0x8000
- # endif
- # endif
- #endif
- #ifndef DIST_BUFSIZE
- # define DIST_BUFSIZE LIT_BUFSIZE
- #endif
- #define REP_3_6 16
- #define REPZ_3_10 17
- #define REPZ_11_138 18
- typedef struct ct_data {
- union {
- ush freq;
- ush code;
- } fc;
- union {
- ush dad;
- ush len;
- } dl;
- } ct_data;
- #define Freq fc.freq
- #define Code fc.code
- #define Dad dl.dad
- #define Len dl.len
- #define HEAP_SIZE (2*L_CODES + 1)
- typedef struct tree_desc {
- ct_data *dyn_tree;
- ct_data *static_tree;
- const uint8_t *extra_bits;
- int extra_base;
- int elems;
- int max_length;
- int max_code;
- } tree_desc;
- struct globals2 {
- ush heap[HEAP_SIZE];
- int heap_len;
- int heap_max;
- ct_data dyn_ltree[HEAP_SIZE];
- ct_data dyn_dtree[2 * D_CODES + 1];
- ct_data static_ltree[L_CODES + 2];
- ct_data static_dtree[D_CODES];
- ct_data bl_tree[2 * BL_CODES + 1];
- tree_desc l_desc;
- tree_desc d_desc;
- tree_desc bl_desc;
- ush bl_count[MAX_BITS + 1];
- uch depth[2 * L_CODES + 1];
- uch length_code[MAX_MATCH - MIN_MATCH + 1];
- uch dist_code[512];
- int base_length[LENGTH_CODES];
- int base_dist[D_CODES];
- uch flag_buf[LIT_BUFSIZE / 8];
- unsigned last_lit;
- unsigned last_dist;
- unsigned last_flags;
- uch flags;
- uch flag_bit;
- ulg opt_len;
- ulg static_len;
- ulg compressed_len;
- };
- #define G2ptr ((struct globals2*)(ptr_to_globals))
- #define G2 (*G2ptr)
- static void gen_codes(ct_data * tree, int max_code);
- static void build_tree(tree_desc * desc);
- static void scan_tree(ct_data * tree, int max_code);
- static void send_tree(ct_data * tree, int max_code);
- static int build_bl_tree(void);
- static void send_all_trees(int lcodes, int dcodes, int blcodes);
- static void compress_block(ct_data * ltree, ct_data * dtree);
- #ifndef DEBUG
- # define SEND_CODE(c, tree) send_bits(tree[c].Code, tree[c].Len)
- #else
- # define SEND_CODE(c, tree) \
- { \
- if (verbose > 1) bb_error_msg("\ncd %3d ", (c)); \
- send_bits(tree[c].Code, tree[c].Len); \
- }
- #endif
- #define D_CODE(dist) \
- ((dist) < 256 ? G2.dist_code[dist] : G2.dist_code[256 + ((dist)>>7)])
- static void init_block(void)
- {
- int n;
-
- for (n = 0; n < L_CODES; n++)
- G2.dyn_ltree[n].Freq = 0;
- for (n = 0; n < D_CODES; n++)
- G2.dyn_dtree[n].Freq = 0;
- for (n = 0; n < BL_CODES; n++)
- G2.bl_tree[n].Freq = 0;
- G2.dyn_ltree[END_BLOCK].Freq = 1;
- G2.opt_len = G2.static_len = 0;
- G2.last_lit = G2.last_dist = G2.last_flags = 0;
- G2.flags = 0;
- G2.flag_bit = 1;
- }
- #define SMALLER(tree, n, m) \
- (tree[n].Freq < tree[m].Freq \
- || (tree[n].Freq == tree[m].Freq && G2.depth[n] <= G2.depth[m]))
- static void pqdownheap(ct_data * tree, int k)
- {
- int v = G2.heap[k];
- int j = k << 1;
- while (j <= G2.heap_len) {
-
- if (j < G2.heap_len && SMALLER(tree, G2.heap[j + 1], G2.heap[j]))
- j++;
-
- if (SMALLER(tree, v, G2.heap[j]))
- break;
-
- G2.heap[k] = G2.heap[j];
- k = j;
-
- j <<= 1;
- }
- G2.heap[k] = v;
- }
- static void gen_bitlen(tree_desc * desc)
- {
- ct_data *tree = desc->dyn_tree;
- const uint8_t *extra = desc->extra_bits;
- int base = desc->extra_base;
- int max_code = desc->max_code;
- int max_length = desc->max_length;
- ct_data *stree = desc->static_tree;
- int h;
- int n, m;
- int bits;
- int xbits;
- ush f;
- int overflow = 0;
- for (bits = 0; bits <= MAX_BITS; bits++)
- G2.bl_count[bits] = 0;
-
- tree[G2.heap[G2.heap_max]].Len = 0;
- for (h = G2.heap_max + 1; h < HEAP_SIZE; h++) {
- n = G2.heap[h];
- bits = tree[tree[n].Dad].Len + 1;
- if (bits > max_length) {
- bits = max_length;
- overflow++;
- }
- tree[n].Len = (ush) bits;
-
- if (n > max_code)
- continue;
- G2.bl_count[bits]++;
- xbits = 0;
- if (n >= base)
- xbits = extra[n - base];
- f = tree[n].Freq;
- G2.opt_len += (ulg) f *(bits + xbits);
- if (stree)
- G2.static_len += (ulg) f * (stree[n].Len + xbits);
- }
- if (overflow == 0)
- return;
- Trace((stderr, "\nbit length overflow\n"));
-
-
- do {
- bits = max_length - 1;
- while (G2.bl_count[bits] == 0)
- bits--;
- G2.bl_count[bits]--;
- G2.bl_count[bits + 1] += 2;
- G2.bl_count[max_length]--;
-
- overflow -= 2;
- } while (overflow > 0);
-
- for (bits = max_length; bits != 0; bits--) {
- n = G2.bl_count[bits];
- while (n != 0) {
- m = G2.heap[--h];
- if (m > max_code)
- continue;
- if (tree[m].Len != (unsigned) bits) {
- Trace((stderr, "code %d bits %d->%d\n", m, tree[m].Len, bits));
- G2.opt_len += ((int32_t) bits - tree[m].Len) * tree[m].Freq;
- tree[m].Len = bits;
- }
- n--;
- }
- }
- }
- static void gen_codes(ct_data * tree, int max_code)
- {
- ush next_code[MAX_BITS + 1];
- ush code = 0;
- int bits;
- int n;
-
- for (bits = 1; bits <= MAX_BITS; bits++) {
- next_code[bits] = code = (code + G2.bl_count[bits - 1]) << 1;
- }
-
- Assert(code + G2.bl_count[MAX_BITS] - 1 == (1 << MAX_BITS) - 1,
- "inconsistent bit counts");
- Tracev((stderr, "\ngen_codes: max_code %d ", max_code));
- for (n = 0; n <= max_code; n++) {
- int len = tree[n].Len;
- if (len == 0)
- continue;
-
- tree[n].Code = bi_reverse(next_code[len]++, len);
- Tracec(tree != G2.static_ltree,
- (stderr, "\nn %3d %c l %2d c %4x (%x) ", n,
- (n > ' ' ? n : ' '), len, tree[n].Code,
- next_code[len] - 1));
- }
- }
- #define SMALLEST 1
- #define PQREMOVE(tree, top) \
- do { \
- top = G2.heap[SMALLEST]; \
- G2.heap[SMALLEST] = G2.heap[G2.heap_len--]; \
- pqdownheap(tree, SMALLEST); \
- } while (0)
- static void build_tree(tree_desc * desc)
- {
- ct_data *tree = desc->dyn_tree;
- ct_data *stree = desc->static_tree;
- int elems = desc->elems;
- int n, m;
- int max_code = -1;
- int node = elems;
-
- G2.heap_len = 0;
- G2.heap_max = HEAP_SIZE;
- for (n = 0; n < elems; n++) {
- if (tree[n].Freq != 0) {
- G2.heap[++G2.heap_len] = max_code = n;
- G2.depth[n] = 0;
- } else {
- tree[n].Len = 0;
- }
- }
-
- while (G2.heap_len < 2) {
- int new = G2.heap[++G2.heap_len] = (max_code < 2 ? ++max_code : 0);
- tree[new].Freq = 1;
- G2.depth[new] = 0;
- G2.opt_len--;
- if (stree)
- G2.static_len -= stree[new].Len;
-
- }
- desc->max_code = max_code;
-
- for (n = G2.heap_len / 2; n >= 1; n--)
- pqdownheap(tree, n);
-
- do {
- PQREMOVE(tree, n);
- m = G2.heap[SMALLEST];
- G2.heap[--G2.heap_max] = n;
- G2.heap[--G2.heap_max] = m;
-
- tree[node].Freq = tree[n].Freq + tree[m].Freq;
- G2.depth[node] = MAX(G2.depth[n], G2.depth[m]) + 1;
- tree[n].Dad = tree[m].Dad = (ush) node;
- #ifdef DUMP_BL_TREE
- if (tree == G2.bl_tree) {
- bb_error_msg("\nnode %d(%d), sons %d(%d) %d(%d)",
- node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
- }
- #endif
-
- G2.heap[SMALLEST] = node++;
- pqdownheap(tree, SMALLEST);
- } while (G2.heap_len >= 2);
- G2.heap[--G2.heap_max] = G2.heap[SMALLEST];
-
- gen_bitlen((tree_desc *) desc);
-
- gen_codes((ct_data *) tree, max_code);
- }
- static void scan_tree(ct_data * tree, int max_code)
- {
- int n;
- int prevlen = -1;
- int curlen;
- int nextlen = tree[0].Len;
- int count = 0;
- int max_count = 7;
- int min_count = 4;
- if (nextlen == 0) {
- max_count = 138;
- min_count = 3;
- }
- tree[max_code + 1].Len = 0xffff;
- for (n = 0; n <= max_code; n++) {
- curlen = nextlen;
- nextlen = tree[n + 1].Len;
- if (++count < max_count && curlen == nextlen)
- continue;
- if (count < min_count) {
- G2.bl_tree[curlen].Freq += count;
- } else if (curlen != 0) {
- if (curlen != prevlen)
- G2.bl_tree[curlen].Freq++;
- G2.bl_tree[REP_3_6].Freq++;
- } else if (count <= 10) {
- G2.bl_tree[REPZ_3_10].Freq++;
- } else {
- G2.bl_tree[REPZ_11_138].Freq++;
- }
- count = 0;
- prevlen = curlen;
- max_count = 7;
- min_count = 4;
- if (nextlen == 0) {
- max_count = 138;
- min_count = 3;
- } else if (curlen == nextlen) {
- max_count = 6;
- min_count = 3;
- }
- }
- }
- static void send_tree(ct_data * tree, int max_code)
- {
- int n;
- int prevlen = -1;
- int curlen;
- int nextlen = tree[0].Len;
- int count = 0;
- int max_count = 7;
- int min_count = 4;
- if (nextlen == 0)
- max_count = 138, min_count = 3;
- for (n = 0; n <= max_code; n++) {
- curlen = nextlen;
- nextlen = tree[n + 1].Len;
- if (++count < max_count && curlen == nextlen) {
- continue;
- } else if (count < min_count) {
- do {
- SEND_CODE(curlen, G2.bl_tree);
- } while (--count);
- } else if (curlen != 0) {
- if (curlen != prevlen) {
- SEND_CODE(curlen, G2.bl_tree);
- count--;
- }
- Assert(count >= 3 && count <= 6, " 3_6?");
- SEND_CODE(REP_3_6, G2.bl_tree);
- send_bits(count - 3, 2);
- } else if (count <= 10) {
- SEND_CODE(REPZ_3_10, G2.bl_tree);
- send_bits(count - 3, 3);
- } else {
- SEND_CODE(REPZ_11_138, G2.bl_tree);
- send_bits(count - 11, 7);
- }
- count = 0;
- prevlen = curlen;
- if (nextlen == 0) {
- max_count = 138;
- min_count = 3;
- } else if (curlen == nextlen) {
- max_count = 6;
- min_count = 3;
- } else {
- max_count = 7;
- min_count = 4;
- }
- }
- }
- static int build_bl_tree(void)
- {
- int max_blindex;
-
- scan_tree(G2.dyn_ltree, G2.l_desc.max_code);
- scan_tree(G2.dyn_dtree, G2.d_desc.max_code);
-
- build_tree(&G2.bl_desc);
-
-
- for (max_blindex = BL_CODES - 1; max_blindex >= 3; max_blindex--) {
- if (G2.bl_tree[bl_order[max_blindex]].Len != 0)
- break;
- }
-
- G2.opt_len += 3 * (max_blindex + 1) + 5 + 5 + 4;
- Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", G2.opt_len, G2.static_len));
- return max_blindex;
- }
- static void send_all_trees(int lcodes, int dcodes, int blcodes)
- {
- int rank;
- Assert(lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes");
- Assert(lcodes <= L_CODES && dcodes <= D_CODES
- && blcodes <= BL_CODES, "too many codes");
- Tracev((stderr, "\nbl counts: "));
- send_bits(lcodes - 257, 5);
- send_bits(dcodes - 1, 5);
- send_bits(blcodes - 4, 4);
- for (rank = 0; rank < blcodes; rank++) {
- Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
- send_bits(G2.bl_tree[bl_order[rank]].Len, 3);
- }
- Tracev((stderr, "\nbl tree: sent %ld", G1.bits_sent));
- send_tree((ct_data *) G2.dyn_ltree, lcodes - 1);
- Tracev((stderr, "\nlit tree: sent %ld", G1.bits_sent));
- send_tree((ct_data *) G2.dyn_dtree, dcodes - 1);
- Tracev((stderr, "\ndist tree: sent %ld", G1.bits_sent));
- }
- static int ct_tally(int dist, int lc)
- {
- G1.l_buf[G2.last_lit++] = lc;
- if (dist == 0) {
-
- G2.dyn_ltree[lc].Freq++;
- } else {
-
- dist--;
- Assert((ush) dist < (ush) MAX_DIST
- && (ush) lc <= (ush) (MAX_MATCH - MIN_MATCH)
- && (ush) D_CODE(dist) < (ush) D_CODES, "ct_tally: bad match"
- );
- G2.dyn_ltree[G2.length_code[lc] + LITERALS + 1].Freq++;
- G2.dyn_dtree[D_CODE(dist)].Freq++;
- G1.d_buf[G2.last_dist++] = dist;
- G2.flags |= G2.flag_bit;
- }
- G2.flag_bit <<= 1;
-
- if ((G2.last_lit & 7) == 0) {
- G2.flag_buf[G2.last_flags++] = G2.flags;
- G2.flags = 0;
- G2.flag_bit = 1;
- }
-
- if ((G2.last_lit & 0xfff) == 0) {
-
- ulg out_length = G2.last_lit * 8L;
- ulg in_length = (ulg) G1.strstart - G1.block_start;
- int dcode;
- for (dcode = 0; dcode < D_CODES; dcode++) {
- out_length += G2.dyn_dtree[dcode].Freq * (5L + extra_dbits[dcode]);
- }
- out_length >>= 3;
- Trace((stderr,
- "\nlast_lit %u, last_dist %u, in %ld, out ~%ld(%ld%%) ",
- G2.last_lit, G2.last_dist, in_length, out_length,
- 100L - out_length * 100L / in_length));
- if (G2.last_dist < G2.last_lit / 2 && out_length < in_length / 2)
- return 1;
- }
- return (G2.last_lit == LIT_BUFSIZE - 1 || G2.last_dist == DIST_BUFSIZE);
-
- }
- static void compress_block(ct_data * ltree, ct_data * dtree)
- {
- unsigned dist;
- int lc;
- unsigned lx = 0;
- unsigned dx = 0;
- unsigned fx = 0;
- uch flag = 0;
- unsigned code;
- int extra;
- if (G2.last_lit != 0) do {
- if ((lx & 7) == 0)
- flag = G2.flag_buf[fx++];
- lc = G1.l_buf[lx++];
- if ((flag & 1) == 0) {
- SEND_CODE(lc, ltree);
- Tracecv(lc > ' ', (stderr, " '%c' ", lc));
- } else {
-
- code = G2.length_code[lc];
- SEND_CODE(code + LITERALS + 1, ltree);
- extra = extra_lbits[code];
- if (extra != 0) {
- lc -= G2.base_length[code];
- send_bits(lc, extra);
- }
- dist = G1.d_buf[dx++];
-
- code = D_CODE(dist);
- Assert(code < D_CODES, "bad d_code");
- SEND_CODE(code, dtree);
- extra = extra_dbits[code];
- if (extra != 0) {
- dist -= G2.base_dist[code];
- send_bits(dist, extra);
- }
- }
- flag >>= 1;
- } while (lx < G2.last_lit);
- SEND_CODE(END_BLOCK, ltree);
- }
- static ulg flush_block(char *buf, ulg stored_len, int eof)
- {
- ulg opt_lenb, static_lenb;
- int max_blindex;
- G2.flag_buf[G2.last_flags] = G2.flags;
-
- build_tree(&G2.l_desc);
- Tracev((stderr, "\nlit data: dyn %ld, stat %ld", G2.opt_len, G2.static_len));
- build_tree(&G2.d_desc);
- Tracev((stderr, "\ndist data: dyn %ld, stat %ld", G2.opt_len, G2.static_len));
-
-
- max_blindex = build_bl_tree();
-
- opt_lenb = (G2.opt_len + 3 + 7) >> 3;
- static_lenb = (G2.static_len + 3 + 7) >> 3;
- Trace((stderr,
- "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u dist %u ",
- opt_lenb, G2.opt_len, static_lenb, G2.static_len, stored_len,
- G2.last_lit, G2.last_dist));
- if (static_lenb <= opt_lenb)
- opt_lenb = static_lenb;
-
- if (stored_len <= opt_lenb && eof && G2.compressed_len == 0L && seekable()) {
-
- if (buf == NULL)
- bb_error_msg("block vanished");
- copy_block(buf, (unsigned) stored_len, 0);
- G2.compressed_len = stored_len << 3;
- } else if (stored_len + 4 <= opt_lenb && buf != NULL) {
-
-
- send_bits((STORED_BLOCK << 1) + eof, 3);
- G2.compressed_len = (G2.compressed_len + 3 + 7) & ~7L;
- G2.compressed_len += (stored_len + 4) << 3;
- copy_block(buf, (unsigned) stored_len, 1);
- } else if (static_lenb == opt_lenb) {
- send_bits((STATIC_TREES << 1) + eof, 3);
- compress_block((ct_data *) G2.static_ltree, (ct_data *) G2.static_dtree);
- G2.compressed_len += 3 + G2.static_len;
- } else {
- send_bits((DYN_TREES << 1) + eof, 3);
- send_all_trees(G2.l_desc.max_code + 1, G2.d_desc.max_code + 1,
- max_blindex + 1);
- compress_block((ct_data *) G2.dyn_ltree, (ct_data *) G2.dyn_dtree);
- G2.compressed_len += 3 + G2.opt_len;
- }
- Assert(G2.compressed_len == G1.bits_sent, "bad compressed size");
- init_block();
- if (eof) {
- bi_windup();
- G2.compressed_len += 7;
- }
- Tracev((stderr, "\ncomprlen %lu(%lu) ", G2.compressed_len >> 3,
- G2.compressed_len - 7 * eof));
- return G2.compressed_len >> 3;
- }
- #define UPDATE_HASH(h, c) (h = (((h)<<H_SHIFT) ^ (c)) & HASH_MASK)
- #define FLUSH_BLOCK(eof) \
- flush_block( \
- G1.block_start >= 0L \
- ? (char*)&G1.window[(unsigned)G1.block_start] \
- : (char*)NULL, \
- (ulg)G1.strstart - G1.block_start, \
- (eof) \
- )
- #define INSERT_STRING(s, match_head) \
- do { \
- UPDATE_HASH(G1.ins_h, G1.window[(s) + MIN_MATCH-1]); \
- G1.prev[(s) & WMASK] = match_head = head[G1.ins_h]; \
- head[G1.ins_h] = (s); \
- } while (0)
- static ulg deflate(void)
- {
- IPos hash_head;
- IPos prev_match;
- int flush;
- int match_available = 0;
- unsigned match_length = MIN_MATCH - 1;
-
- while (G1.lookahead != 0) {
-
- INSERT_STRING(G1.strstart, hash_head);
-
- G1.prev_length = match_length;
- prev_match = G1.match_start;
- match_length = MIN_MATCH - 1;
- if (hash_head != 0 && G1.prev_length < max_lazy_match
- && G1.strstart - hash_head <= MAX_DIST
- ) {
-
- match_length = longest_match(hash_head);
-
- if (match_length > G1.lookahead)
- match_length = G1.lookahead;
-
- if (match_length == MIN_MATCH && G1.strstart - G1.match_start > TOO_FAR) {
-
- match_length--;
- }
- }
-
- if (G1.prev_length >= MIN_MATCH && match_length <= G1.prev_length) {
- check_match(G1.strstart - 1, prev_match, G1.prev_length);
- flush = ct_tally(G1.strstart - 1 - prev_match, G1.prev_length - MIN_MATCH);
-
- G1.lookahead -= G1.prev_length - 1;
- G1.prev_length -= 2;
- do {
- G1.strstart++;
- INSERT_STRING(G1.strstart, hash_head);
-
- } while (--G1.prev_length != 0);
- match_available = 0;
- match_length = MIN_MATCH - 1;
- G1.strstart++;
- if (flush) {
- FLUSH_BLOCK(0);
- G1.block_start = G1.strstart;
- }
- } else if (match_available) {
-
- Tracevv((stderr, "%c", G1.window[G1.strstart - 1]));
- if (ct_tally(0, G1.window[G1.strstart - 1])) {
- FLUSH_BLOCK(0);
- G1.block_start = G1.strstart;
- }
- G1.strstart++;
- G1.lookahead--;
- } else {
-
- match_available = 1;
- G1.strstart++;
- G1.lookahead--;
- }
- Assert(G1.strstart <= G1.isize && lookahead <= G1.isize, "a bit too far");
-
- while (G1.lookahead < MIN_LOOKAHEAD && !G1.eofile)
- fill_window();
- }
- if (match_available)
- ct_tally(0, G1.window[G1.strstart - 1]);
- return FLUSH_BLOCK(1);
- }
- static void bi_init(void)
- {
- G1.bi_buf = 0;
- G1.bi_valid = 0;
- #ifdef DEBUG
- G1.bits_sent = 0L;
- #endif
- }
- static void lm_init(ush * flagsp)
- {
- unsigned j;
-
- memset(head, 0, HASH_SIZE * sizeof(*head));
-
-
- *flagsp |= 2;
-
- G1.strstart = 0;
- G1.block_start = 0L;
- G1.lookahead = file_read(G1.window,
- sizeof(int) <= 2 ? (unsigned) WSIZE : 2 * WSIZE);
- if (G1.lookahead == 0 || G1.lookahead == (unsigned) -1) {
- G1.eofile = 1;
- G1.lookahead = 0;
- return;
- }
- G1.eofile = 0;
-
- while (G1.lookahead < MIN_LOOKAHEAD && !G1.eofile)
- fill_window();
- G1.ins_h = 0;
- for (j = 0; j < MIN_MATCH - 1; j++)
- UPDATE_HASH(G1.ins_h, G1.window[j]);
-
- }
- static void ct_init(void)
- {
- int n;
- int length;
- int code;
- int dist;
- G2.compressed_len = 0L;
- #ifdef NOT_NEEDED
- if (G2.static_dtree[0].Len != 0)
- return;
- #endif
-
- length = 0;
- for (code = 0; code < LENGTH_CODES - 1; code++) {
- G2.base_length[code] = length;
- for (n = 0; n < (1 << extra_lbits[code]); n++) {
- G2.length_code[length++] = code;
- }
- }
- Assert(length == 256, "ct_init: length != 256");
-
- G2.length_code[length - 1] = code;
-
- dist = 0;
- for (code = 0; code < 16; code++) {
- G2.base_dist[code] = dist;
- for (n = 0; n < (1 << extra_dbits[code]); n++) {
- G2.dist_code[dist++] = code;
- }
- }
- Assert(dist == 256, "ct_init: dist != 256");
- dist >>= 7;
- for (; code < D_CODES; code++) {
- G2.base_dist[code] = dist << 7;
- for (n = 0; n < (1 << (extra_dbits[code] - 7)); n++) {
- G2.dist_code[256 + dist++] = code;
- }
- }
- Assert(dist == 256, "ct_init: 256+dist != 512");
-
-
- n = 0;
- while (n <= 143) {
- G2.static_ltree[n++].Len = 8;
- G2.bl_count[8]++;
- }
- while (n <= 255) {
- G2.static_ltree[n++].Len = 9;
- G2.bl_count[9]++;
- }
- while (n <= 279) {
- G2.static_ltree[n++].Len = 7;
- G2.bl_count[7]++;
- }
- while (n <= 287) {
- G2.static_ltree[n++].Len = 8;
- G2.bl_count[8]++;
- }
-
- gen_codes((ct_data *) G2.static_ltree, L_CODES + 1);
-
- for (n = 0; n < D_CODES; n++) {
- G2.static_dtree[n].Len = 5;
- G2.static_dtree[n].Code = bi_reverse(n, 5);
- }
-
- init_block();
- }
- static void zip(ulg time_stamp)
- {
- ush deflate_flags = 0;
- G1.outcnt = 0;
-
-
-
-
- put_32bit(0x00088b1f);
- put_32bit(time_stamp);
-
- G1.crc = ~0;
- bi_init();
- ct_init();
- lm_init(&deflate_flags);
- put_8bit(deflate_flags);
- put_8bit(3);
- deflate();
-
- put_32bit(~G1.crc);
- put_32bit(G1.isize);
- flush_outbuf();
- }
- static
- IF_DESKTOP(long long) int FAST_FUNC pack_gzip(unpack_info_t *info UNUSED_PARAM)
- {
- struct stat s;
-
- G1.outcnt = 0;
- #ifdef DEBUG
- G1.insize = 0;
- #endif
- G1.isize = 0;
-
- memset(&G2, 0, sizeof(G2));
- G2.l_desc.dyn_tree = G2.dyn_ltree;
- G2.l_desc.static_tree = G2.static_ltree;
- G2.l_desc.extra_bits = extra_lbits;
- G2.l_desc.extra_base = LITERALS + 1;
- G2.l_desc.elems = L_CODES;
- G2.l_desc.max_length = MAX_BITS;
-
- G2.d_desc.dyn_tree = G2.dyn_dtree;
- G2.d_desc.static_tree = G2.static_dtree;
- G2.d_desc.extra_bits = extra_dbits;
-
- G2.d_desc.elems = D_CODES;
- G2.d_desc.max_length = MAX_BITS;
-
- G2.bl_desc.dyn_tree = G2.bl_tree;
-
- G2.bl_desc.extra_bits = extra_blbits,
-
- G2.bl_desc.elems = BL_CODES;
- G2.bl_desc.max_length = MAX_BL_BITS;
-
- s.st_ctime = 0;
- fstat(STDIN_FILENO, &s);
- zip(s.st_ctime);
- return 0;
- }
- #if ENABLE_FEATURE_GZIP_LONG_OPTIONS
- static const char gzip_longopts[] ALIGN1 =
- "stdout\0" No_argument "c"
- "to-stdout\0" No_argument "c"
- "force\0" No_argument "f"
- "verbose\0" No_argument "v"
- #if ENABLE_GUNZIP
- "decompress\0" No_argument "d"
- "uncompress\0" No_argument "d"
- "test\0" No_argument "t"
- #endif
- "quiet\0" No_argument "q"
- "fast\0" No_argument "1"
- "best\0" No_argument "9"
- ;
- #endif
- int gzip_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
- #if ENABLE_GUNZIP
- int gzip_main(int argc, char **argv)
- #else
- int gzip_main(int argc UNUSED_PARAM, char **argv)
- #endif
- {
- unsigned opt;
- #if ENABLE_FEATURE_GZIP_LONG_OPTIONS
- applet_long_options = gzip_longopts;
- #endif
-
- opt = getopt32(argv, "cfv" IF_GUNZIP("dt") "q123456789n");
- #if ENABLE_GUNZIP
- if (opt & 0x18)
- return gunzip_main(argc, argv);
- #endif
- option_mask32 &= 0x7;
-
-
-
- argv += optind;
- SET_PTR_TO_GLOBALS((char *)xzalloc(sizeof(struct globals)+sizeof(struct globals2))
- + sizeof(struct globals));
-
- ALLOC(uch, G1.l_buf, INBUFSIZ);
- ALLOC(uch, G1.outbuf, OUTBUFSIZ);
- ALLOC(ush, G1.d_buf, DIST_BUFSIZE);
- ALLOC(uch, G1.window, 2L * WSIZE);
- ALLOC(ush, G1.prev, 1L << BITS);
-
- global_crc32_table = crc32_filltable(NULL, 0);
- return bbunpack(argv, pack_gzip, append_ext, "gz");
- }
|