• file
• revisions
• annotate
• diff
• comparison
• raw

security/nss/lib/zlib/inffast.c@b8a032363ba2 (annotated)

security/nss/lib/zlib/inffast.c

Thu, 22 Jan 2015 13:21:57 +0100

author

Michael Schloh von Bennewitz <michael@schloh.com>

date

Thu, 22 Jan 2015 13:21:57 +0100

branch

TOR_BUG_9701

changeset 15

b8a032363ba2

permissions

-rw-r--r--

Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6

michael@0	1	/* inffast.c -- fast decoding
michael@0	2	* Copyright (C) 1995-2008, 2010 Mark Adler
michael@0	3	* For conditions of distribution and use, see copyright notice in zlib.h
michael@0	4	*/
michael@0	5
michael@0	6	#include "zutil.h"
michael@0	7	#include "inftrees.h"
michael@0	8	#include "inflate.h"
michael@0	9	#include "inffast.h"
michael@0	10
michael@0	11	#ifndef ASMINF
michael@0	12
michael@0	13	/* Allow machine dependent optimization for post-increment or pre-increment.
michael@0	14	Based on testing to date,
michael@0	15	Pre-increment preferred for:
michael@0	16	- PowerPC G3 (Adler)
michael@0	17	- MIPS R5000 (Randers-Pehrson)
michael@0	18	Post-increment preferred for:
michael@0	19	- none
michael@0	20	No measurable difference:
michael@0	21	- Pentium III (Anderson)
michael@0	22	- M68060 (Nikl)
michael@0	23	*/
michael@0	24	#ifdef POSTINC
michael@0	25	# define OFF 0
michael@0	26	# define PUP(a) *(a)++
michael@0	27	#else
michael@0	28	# define OFF 1
michael@0	29	# define PUP(a) *++(a)
michael@0	30	#endif
michael@0	31
michael@0	32	/*
michael@0	33	Decode literal, length, and distance codes and write out the resulting
michael@0	34	literal and match bytes until either not enough input or output is
michael@0	35	available, an end-of-block is encountered, or a data error is encountered.
michael@0	36	When large enough input and output buffers are supplied to inflate(), for
michael@0	37	example, a 16K input buffer and a 64K output buffer, more than 95% of the
michael@0	38	inflate execution time is spent in this routine.
michael@0	39
michael@0	40	Entry assumptions:
michael@0	41
michael@0	42	state->mode == LEN
michael@0	43	strm->avail_in >= 6
michael@0	44	strm->avail_out >= 258
michael@0	45	start >= strm->avail_out
michael@0	46	state->bits < 8
michael@0	47
michael@0	48	On return, state->mode is one of:
michael@0	49
michael@0	50	LEN -- ran out of enough output space or enough available input
michael@0	51	TYPE -- reached end of block code, inflate() to interpret next block
michael@0	52	BAD -- error in block data
michael@0	53
michael@0	54	Notes:
michael@0	55
michael@0	56	- The maximum input bits used by a length/distance pair is 15 bits for the
michael@0	57	length code, 5 bits for the length extra, 15 bits for the distance code,
michael@0	58	and 13 bits for the distance extra. This totals 48 bits, or six bytes.
michael@0	59	Therefore if strm->avail_in >= 6, then there is enough input to avoid
michael@0	60	checking for available input while decoding.
michael@0	61
michael@0	62	- The maximum bytes that a single length/distance pair can output is 258
michael@0	63	bytes, which is the maximum length that can be coded. inflate_fast()
michael@0	64	requires strm->avail_out >= 258 for each loop to avoid checking for
michael@0	65	output space.
michael@0	66	*/
michael@0	67	void ZLIB_INTERNAL inflate_fast(strm, start)
michael@0	68	z_streamp strm;
michael@0	69	unsigned start; /* inflate()'s starting value for strm->avail_out */
michael@0	70	{
michael@0	71	struct inflate_state FAR *state;
michael@0	72	unsigned char FAR *in; /* local strm->next_in */
michael@0	73	unsigned char FAR *last; /* while in < last, enough input available */
michael@0	74	unsigned char FAR *out; /* local strm->next_out */
michael@0	75	unsigned char FAR *beg; /* inflate()'s initial strm->next_out */
michael@0	76	unsigned char FAR *end; /* while out < end, enough space available */
michael@0	77	#ifdef INFLATE_STRICT
michael@0	78	unsigned dmax; /* maximum distance from zlib header */
michael@0	79	#endif
michael@0	80	unsigned wsize; /* window size or zero if not using window */
michael@0	81	unsigned whave; /* valid bytes in the window */
michael@0	82	unsigned wnext; /* window write index */
michael@0	83	unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */
michael@0	84	unsigned long hold; /* local strm->hold */
michael@0	85	unsigned bits; /* local strm->bits */
michael@0	86	code const FAR *lcode; /* local strm->lencode */
michael@0	87	code const FAR *dcode; /* local strm->distcode */
michael@0	88	unsigned lmask; /* mask for first level of length codes */
michael@0	89	unsigned dmask; /* mask for first level of distance codes */
michael@0	90	code here; /* retrieved table entry */
michael@0	91	unsigned op; /* code bits, operation, extra bits, or */
michael@0	92	/* window position, window bytes to copy */
michael@0	93	unsigned len; /* match length, unused bytes */
michael@0	94	unsigned dist; /* match distance */
michael@0	95	unsigned char FAR *from; /* where to copy match from */
michael@0	96
michael@0	97	/* copy state to local variables */
michael@0	98	state = (struct inflate_state FAR *)strm->state;
michael@0	99	in = strm->next_in - OFF;
michael@0	100	last = in + (strm->avail_in - 5);
michael@0	101	out = strm->next_out - OFF;
michael@0	102	beg = out - (start - strm->avail_out);
michael@0	103	end = out + (strm->avail_out - 257);
michael@0	104	#ifdef INFLATE_STRICT
michael@0	105	dmax = state->dmax;
michael@0	106	#endif
michael@0	107	wsize = state->wsize;
michael@0	108	whave = state->whave;
michael@0	109	wnext = state->wnext;
michael@0	110	window = state->window;
michael@0	111	hold = state->hold;
michael@0	112	bits = state->bits;
michael@0	113	lcode = state->lencode;
michael@0	114	dcode = state->distcode;
michael@0	115	lmask = (1U << state->lenbits) - 1;
michael@0	116	dmask = (1U << state->distbits) - 1;
michael@0	117
michael@0	118	/* decode literals and length/distances until end-of-block or not enough
michael@0	119	input data or output space */
michael@0	120	do {
michael@0	121	if (bits < 15) {
michael@0	122	hold += (unsigned long)(PUP(in)) << bits;
michael@0	123	bits += 8;
michael@0	124	hold += (unsigned long)(PUP(in)) << bits;
michael@0	125	bits += 8;
michael@0	126	}
michael@0	127	here = lcode[hold & lmask];
michael@0	128	dolen:
michael@0	129	op = (unsigned)(here.bits);
michael@0	130	hold >>= op;
michael@0	131	bits -= op;
michael@0	132	op = (unsigned)(here.op);
michael@0	133	if (op == 0) { /* literal */
michael@0	134	Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
michael@0	135	"inflate: literal '%c'\n" :
michael@0	136	"inflate: literal 0x%02x\n", here.val));
michael@0	137	PUP(out) = (unsigned char)(here.val);
michael@0	138	}
michael@0	139	else if (op & 16) { /* length base */
michael@0	140	len = (unsigned)(here.val);
michael@0	141	op &= 15; /* number of extra bits */
michael@0	142	if (op) {
michael@0	143	if (bits < op) {
michael@0	144	hold += (unsigned long)(PUP(in)) << bits;
michael@0	145	bits += 8;
michael@0	146	}
michael@0	147	len += (unsigned)hold & ((1U << op) - 1);
michael@0	148	hold >>= op;
michael@0	149	bits -= op;
michael@0	150	}
michael@0	151	Tracevv((stderr, "inflate: length %u\n", len));
michael@0	152	if (bits < 15) {
michael@0	153	hold += (unsigned long)(PUP(in)) << bits;
michael@0	154	bits += 8;
michael@0	155	hold += (unsigned long)(PUP(in)) << bits;
michael@0	156	bits += 8;
michael@0	157	}
michael@0	158	here = dcode[hold & dmask];
michael@0	159	dodist:
michael@0	160	op = (unsigned)(here.bits);
michael@0	161	hold >>= op;
michael@0	162	bits -= op;
michael@0	163	op = (unsigned)(here.op);
michael@0	164	if (op & 16) { /* distance base */
michael@0	165	dist = (unsigned)(here.val);
michael@0	166	op &= 15; /* number of extra bits */
michael@0	167	if (bits < op) {
michael@0	168	hold += (unsigned long)(PUP(in)) << bits;
michael@0	169	bits += 8;
michael@0	170	if (bits < op) {
michael@0	171	hold += (unsigned long)(PUP(in)) << bits;
michael@0	172	bits += 8;
michael@0	173	}
michael@0	174	}
michael@0	175	dist += (unsigned)hold & ((1U << op) - 1);
michael@0	176	#ifdef INFLATE_STRICT
michael@0	177	if (dist > dmax) {
michael@0	178	strm->msg = (char *)"invalid distance too far back";
michael@0	179	state->mode = BAD;
michael@0	180	break;
michael@0	181	}
michael@0	182	#endif
michael@0	183	hold >>= op;
michael@0	184	bits -= op;
michael@0	185	Tracevv((stderr, "inflate: distance %u\n", dist));
michael@0	186	op = (unsigned)(out - beg); /* max distance in output */
michael@0	187	if (dist > op) { /* see if copy from window */
michael@0	188	op = dist - op; /* distance back in window */
michael@0	189	if (op > whave) {
michael@0	190	if (state->sane) {
michael@0	191	strm->msg =
michael@0	192	(char *)"invalid distance too far back";
michael@0	193	state->mode = BAD;
michael@0	194	break;
michael@0	195	}
michael@0	196	#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
michael@0	197	if (len <= op - whave) {
michael@0	198	do {
michael@0	199	PUP(out) = 0;
michael@0	200	} while (--len);
michael@0	201	continue;
michael@0	202	}
michael@0	203	len -= op - whave;
michael@0	204	do {
michael@0	205	PUP(out) = 0;
michael@0	206	} while (--op > whave);
michael@0	207	if (op == 0) {
michael@0	208	from = out - dist;
michael@0	209	do {
michael@0	210	PUP(out) = PUP(from);
michael@0	211	} while (--len);
michael@0	212	continue;
michael@0	213	}
michael@0	214	#endif
michael@0	215	}
michael@0	216	from = window - OFF;
michael@0	217	if (wnext == 0) { /* very common case */
michael@0	218	from += wsize - op;
michael@0	219	if (op < len) { /* some from window */
michael@0	220	len -= op;
michael@0	221	do {
michael@0	222	PUP(out) = PUP(from);
michael@0	223	} while (--op);
michael@0	224	from = out - dist; /* rest from output */
michael@0	225	}
michael@0	226	}
michael@0	227	else if (wnext < op) { /* wrap around window */
michael@0	228	from += wsize + wnext - op;
michael@0	229	op -= wnext;
michael@0	230	if (op < len) { /* some from end of window */
michael@0	231	len -= op;
michael@0	232	do {
michael@0	233	PUP(out) = PUP(from);
michael@0	234	} while (--op);
michael@0	235	from = window - OFF;
michael@0	236	if (wnext < len) { /* some from start of window */
michael@0	237	op = wnext;
michael@0	238	len -= op;
michael@0	239	do {
michael@0	240	PUP(out) = PUP(from);
michael@0	241	} while (--op);
michael@0	242	from = out - dist; /* rest from output */
michael@0	243	}
michael@0	244	}
michael@0	245	}
michael@0	246	else { /* contiguous in window */
michael@0	247	from += wnext - op;
michael@0	248	if (op < len) { /* some from window */
michael@0	249	len -= op;
michael@0	250	do {
michael@0	251	PUP(out) = PUP(from);
michael@0	252	} while (--op);
michael@0	253	from = out - dist; /* rest from output */
michael@0	254	}
michael@0	255	}
michael@0	256	while (len > 2) {
michael@0	257	PUP(out) = PUP(from);
michael@0	258	PUP(out) = PUP(from);
michael@0	259	PUP(out) = PUP(from);
michael@0	260	len -= 3;
michael@0	261	}
michael@0	262	if (len) {
michael@0	263	PUP(out) = PUP(from);
michael@0	264	if (len > 1)
michael@0	265	PUP(out) = PUP(from);
michael@0	266	}
michael@0	267	}
michael@0	268	else {
michael@0	269	from = out - dist; /* copy direct from output */
michael@0	270	do { /* minimum length is three */
michael@0	271	PUP(out) = PUP(from);
michael@0	272	PUP(out) = PUP(from);
michael@0	273	PUP(out) = PUP(from);
michael@0	274	len -= 3;
michael@0	275	} while (len > 2);
michael@0	276	if (len) {
michael@0	277	PUP(out) = PUP(from);
michael@0	278	if (len > 1)
michael@0	279	PUP(out) = PUP(from);
michael@0	280	}
michael@0	281	}
michael@0	282	}
michael@0	283	else if ((op & 64) == 0) { /* 2nd level distance code */
michael@0	284	here = dcode[here.val + (hold & ((1U << op) - 1))];
michael@0	285	goto dodist;
michael@0	286	}
michael@0	287	else {
michael@0	288	strm->msg = (char *)"invalid distance code";
michael@0	289	state->mode = BAD;
michael@0	290	break;
michael@0	291	}
michael@0	292	}
michael@0	293	else if ((op & 64) == 0) { /* 2nd level length code */
michael@0	294	here = lcode[here.val + (hold & ((1U << op) - 1))];
michael@0	295	goto dolen;
michael@0	296	}
michael@0	297	else if (op & 32) { /* end-of-block */
michael@0	298	Tracevv((stderr, "inflate: end of block\n"));
michael@0	299	state->mode = TYPE;
michael@0	300	break;
michael@0	301	}
michael@0	302	else {
michael@0	303	strm->msg = (char *)"invalid literal/length code";
michael@0	304	state->mode = BAD;
michael@0	305	break;
michael@0	306	}
michael@0	307	} while (in < last && out < end);
michael@0	308
michael@0	309	/* return unused bytes (on entry, bits < 8, so in won't go too far back) */
michael@0	310	len = bits >> 3;
michael@0	311	in -= len;
michael@0	312	bits -= len << 3;
michael@0	313	hold &= (1U << bits) - 1;
michael@0	314
michael@0	315	/* update state and return */
michael@0	316	strm->next_in = in + OFF;
michael@0	317	strm->next_out = out + OFF;
michael@0	318	strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
michael@0	319	strm->avail_out = (unsigned)(out < end ?
michael@0	320	257 + (end - out) : 257 - (out - end));
michael@0	321	state->hold = hold;
michael@0	322	state->bits = bits;
michael@0	323	return;
michael@0	324	}
michael@0	325
michael@0	326	/*
michael@0	327	inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
michael@0	328	- Using bit fields for code structure
michael@0	329	- Different op definition to avoid & for extra bits (do & for table bits)
michael@0	330	- Three separate decoding do-loops for direct, window, and wnext == 0
michael@0	331	- Special case for distance > 1 copies to do overlapped load and store copy
michael@0	332	- Explicit branch predictions (based on measured branch probabilities)
michael@0	333	- Deferring match copy and interspersed it with decoding subsequent codes
michael@0	334	- Swapping literal/length else
michael@0	335	- Swapping window/direct else
michael@0	336	- Larger unrolled copy loops (three is about right)
michael@0	337	- Moving len -= 3 statement into middle of loop
michael@0	338	*/
michael@0	339
michael@0	340	#endif /* !ASMINF */