* ========== Copyright Header Begin ==========================================
* Hypervisor Software File: comp.c
* Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved.
* - Do no alter or remove copyright notices
* - Redistribution and use of this software in source and binary forms, with
* or without modification, are permitted provided that the following
* - Redistribution of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
* - Redistribution in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* Neither the name of Sun Microsystems, Inc. or the names of contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
* This software is provided "AS IS," without a warranty of any kind.
* ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES,
* INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A
* PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN
* MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL NOT BE LIABLE FOR
* ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
* DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN
* OR ITS LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR
* FOR DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE
* DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY,
* ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE, EVEN IF
* SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
* You acknowledge that this software is not designed, licensed or
* intended for use in the design, construction, operation or maintenance of
* ========== Copyright Header End ============================================
/* @(#) comp.c 1.4@(#) */
* New simplified putcode(), adaptive block compress.
#define HSIZE 18013 /* 91% occupancy */
typedef unsigned char char_type
;
typedef long int count_int
;
#define INIT_BITS 9 /* initial number of bits/code */
static count_int htab
[HSIZE
];
static unsigned short codetab
[HSIZE
];
static char_type magic_header
[] = { "\037\236" }; /* 1F 9E */
static int n_bits
; /* number of bits/code */
static int maxbits
= BITS
; /* user settable max # bits/code */
static code_int maxcode
; /* maximum code, given n_bits */
static code_int maxmaxcode
= 1 << BITS
; /* should NEVER generate this code */
static code_int hsize
= HSIZE
; /* for dynamic table sizing */
#define MAXCODE(n_bits) ((1 << (n_bits)) - 1)
static code_int free_ent
= 0; /* first unused entry */
static long int in_count
= 1; /* length of input */
static long int bytes_out
; /* length of compressed output */
#define ROUNDOUT 4 /* XXX round for SPARC alignment */
static long int alloutbytes
= 0; /* num. of output bytes (w. header) */
* block compression parameters -- after all codes are used up,
* and compression rate changes, start over.
static long int ratio
= 0;
#define CHECK_GAP 10000 /* ratio check interval */
static count_int checkpoint
= CHECK_GAP
;
* the next two codes should not be changed lightly, as they must not
* lie within the contiguous general code space.
#define FIRST 258 /* first free entry */
#define END 257 /* End of file marker */
#define CLEAR 256 /* table clear output code */
* compress stdin to stdout
* Algorithm: use open addressing double hashing (no chaining) on the
* prefix code / next character combination. We do a variant of Knuth's
* algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
* secondary probe. Here, the modular division first probe gives way
* to a faster exclusive-or manipulation. Also do block compression with
* an adaptive reset, whereby the code table is cleared when the compression
* ratio decreases, but after the table fills. The variable-length output
* codes are re-sized at this point, and a special CLEAR code is generated
static unsigned char *inbuf
;
static unsigned char *outbuf
;
#define putchar(x) outbuf[putcount++] = (unsigned char) (x)
#define getchar() ((getcount < srcsize) ? inbuf[getcount++] : EOF )
int comp( src
, size
, dest
)
putstring("#!lzdecode ");
putstring("E "); /* Maxbits */
putstring(argc
< 2 ? "lz.out" : argv
[1] ); /* File name */
putchar(magic_header
[0]);
putchar(magic_header
[1]);
putchar((char)(maxbits
));
register code_int hsize_reg
;
maxcode
= MAXCODE(n_bits
= INIT_BITS
);
for ( fcode
= (long) hsize
; fcode
< 65536L; fcode
*= 2L )
hshift
= 8 - hshift
; /* set hash code range bound */
cl_hash( (count_int
) hsize_reg
); /* clear hash table */
while ( (c
= getchar()) != EOF
) {
fcode
= (long) (((long) c
<< maxbits
) + ent
);
i
= ((c
<< hshift
) ^ ent
); /* xor hashing */
if ( htab
[i
] == fcode
) {
} else if ( (long)htab
[i
] < 0 ) /* empty slot */
disp
= hsize_reg
- i
; /* secondary hash (after G. Knott) */
if ( htab
[i
] == fcode
) {
putcode ( (code_int
) ent
);
* If the next entry is going to be too big for the code size,
* then increase it, if possible.
if ( free_ent
> maxcode
)
maxcode
= MAXCODE(n_bits
);
if ( free_ent
< maxmaxcode
) {
codetab
[i
] = free_ent
++; /* code -> hashtable */
else if ( (count_int
)in_count
>= checkpoint
)
* Put out the final code and the End of File marker.
putcode( (code_int
)ent
);
putcode( (code_int
)END
);
/*****************************************************************
* code: A n_bits-bit integer.
* Assumes that n_bits =< (long)wordsize - 1.
* Outputs code to the file.
bytes_out
= 0; /* Header doesn't count */
static void putcode( code
)
register int r_off
= offset
;
r_code
= (code
<< offset
) + oldcode
;
putchar( r_code
& 0xff );
i
= alloutbytes
% ROUNDOUT
;
static void cl_block () /* table clear for block compress */
checkpoint
= in_count
+ CHECK_GAP
;
if(in_count
> 0x007fffff) { /* shift will overflow */
if(rat
== 0) { /* Don't divide by zero */
rat
= (in_count
<< 8) / bytes_out
; /* 8 fractional bits */
cl_hash ( (count_int
) hsize
);
putcode ( (code_int
) CLEAR
);
maxcode
= MAXCODE (n_bits
= INIT_BITS
);
static void cl_hash(hsize
) /* reset code table */
register count_int hsize
;
register count_int
*htab_p
= htab
+hsize
;
do { /* might use Sys V memset(3) here */
} while ((i
-= 16) >= 0);
for ( i
+= 16; i
> 0; i
-- )