1/*	$NetBSD: compress.c,v 1.2.6.1 2012/06/05 21:15:01 bouyer Exp $	*/
2
3/*
4 * Copyright (C) 2004-2007  Internet Systems Consortium, Inc. ("ISC")
5 * Copyright (C) 1999-2001  Internet Software Consortium.
6 *
7 * Permission to use, copy, modify, and/or distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
10 *
11 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
12 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
13 * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
14 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
15 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
16 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
17 * PERFORMANCE OF THIS SOFTWARE.
18 */
19
20/* Id: compress.c,v 1.59 2007/06/19 23:47:16 tbox Exp  */
21
22/*! \file */
23
24#define DNS_NAME_USEINLINE 1
25
26#include <config.h>
27
28#include <isc/mem.h>
29#include <isc/string.h>
30#include <isc/util.h>
31
32#include <dns/compress.h>
33#include <dns/fixedname.h>
34#include <dns/rbt.h>
35#include <dns/result.h>
36
37#define CCTX_MAGIC	ISC_MAGIC('C', 'C', 'T', 'X')
38#define VALID_CCTX(x)	ISC_MAGIC_VALID(x, CCTX_MAGIC)
39
40#define DCTX_MAGIC	ISC_MAGIC('D', 'C', 'T', 'X')
41#define VALID_DCTX(x)	ISC_MAGIC_VALID(x, DCTX_MAGIC)
42
43/***
44 ***	Compression
45 ***/
46
47isc_result_t
48dns_compress_init(dns_compress_t *cctx, int edns, isc_mem_t *mctx) {
49	unsigned int i;
50
51	REQUIRE(cctx != NULL);
52	REQUIRE(mctx != NULL);	/* See: rdataset.c:towiresorted(). */
53
54	cctx->allowed = 0;
55	cctx->edns = edns;
56	for (i = 0; i < DNS_COMPRESS_TABLESIZE; i++)
57		cctx->table[i] = NULL;
58	cctx->mctx = mctx;
59	cctx->count = 0;
60	cctx->magic = CCTX_MAGIC;
61	return (ISC_R_SUCCESS);
62}
63
64void
65dns_compress_invalidate(dns_compress_t *cctx) {
66	dns_compressnode_t *node;
67	unsigned int i;
68
69	REQUIRE(VALID_CCTX(cctx));
70
71	cctx->magic = 0;
72	for (i = 0; i < DNS_COMPRESS_TABLESIZE; i++) {
73		while (cctx->table[i] != NULL) {
74			node = cctx->table[i];
75			cctx->table[i] = cctx->table[i]->next;
76			if (node->count < DNS_COMPRESS_INITIALNODES)
77				continue;
78			isc_mem_put(cctx->mctx, node, sizeof(*node));
79		}
80	}
81	cctx->allowed = 0;
82	cctx->edns = -1;
83}
84
85void
86dns_compress_setmethods(dns_compress_t *cctx, unsigned int allowed) {
87	REQUIRE(VALID_CCTX(cctx));
88
89	cctx->allowed &= ~DNS_COMPRESS_ALL;
90	cctx->allowed |= (allowed & DNS_COMPRESS_ALL);
91}
92
93unsigned int
94dns_compress_getmethods(dns_compress_t *cctx) {
95	REQUIRE(VALID_CCTX(cctx));
96	return (cctx->allowed & DNS_COMPRESS_ALL);
97}
98
99void
100dns_compress_setsensitive(dns_compress_t *cctx, isc_boolean_t sensitive) {
101	REQUIRE(VALID_CCTX(cctx));
102
103	if (sensitive)
104		cctx->allowed |= DNS_COMPRESS_CASESENSITIVE;
105	else
106		cctx->allowed &= ~DNS_COMPRESS_CASESENSITIVE;
107}
108
109isc_boolean_t
110dns_compress_getsensitive(dns_compress_t *cctx) {
111	REQUIRE(VALID_CCTX(cctx));
112
113	return (ISC_TF((cctx->allowed & DNS_COMPRESS_CASESENSITIVE) != 0));
114}
115
116int
117dns_compress_getedns(dns_compress_t *cctx) {
118	REQUIRE(VALID_CCTX(cctx));
119	return (cctx->edns);
120}
121
122#define NODENAME(node, name) \
123do { \
124	(name)->length = (node)->r.length; \
125	(name)->labels = (node)->labels; \
126	(name)->ndata = (node)->r.base; \
127	(name)->attributes = DNS_NAMEATTR_ABSOLUTE; \
128} while (/*CONSTCOND*/0)
129
130/*
131 * Find the longest match of name in the table.
132 * If match is found return ISC_TRUE. prefix, suffix and offset are updated.
133 * If no match is found return ISC_FALSE.
134 */
135isc_boolean_t
136dns_compress_findglobal(dns_compress_t *cctx, const dns_name_t *name,
137			dns_name_t *prefix, isc_uint16_t *offset)
138{
139	dns_name_t tname, nname;
140	dns_compressnode_t *node = NULL;
141	unsigned int labels, hash, n;
142
143	REQUIRE(VALID_CCTX(cctx));
144	REQUIRE(dns_name_isabsolute(name) == ISC_TRUE);
145	REQUIRE(offset != NULL);
146
147	if (cctx->count == 0)
148		return (ISC_FALSE);
149
150	labels = dns_name_countlabels(name);
151	INSIST(labels > 0);
152
153	dns_name_init(&tname, NULL);
154	dns_name_init(&nname, NULL);
155
156	for (n = 0; n < labels - 1; n++) {
157		dns_name_getlabelsequence(name, n, labels - n, &tname);
158		hash = dns_name_hash(&tname, ISC_FALSE) %
159		       DNS_COMPRESS_TABLESIZE;
160		for (node = cctx->table[hash]; node != NULL; node = node->next)
161		{
162			NODENAME(node, &nname);
163			if ((cctx->allowed & DNS_COMPRESS_CASESENSITIVE) != 0) {
164				if (dns_name_caseequal(&nname, &tname))
165					break;
166			} else {
167				if (dns_name_equal(&nname, &tname))
168					break;
169			}
170		}
171		if (node != NULL)
172			break;
173	}
174
175	/*
176	 * If node == NULL, we found no match at all.
177	 */
178	if (node == NULL)
179		return (ISC_FALSE);
180
181	if (n == 0)
182		dns_name_reset(prefix);
183	else
184		dns_name_getlabelsequence(name, 0, n, prefix);
185
186	*offset = node->offset;
187	return (ISC_TRUE);
188}
189
190static inline unsigned int
191name_length(const dns_name_t *name) {
192	isc_region_t r;
193	dns_name_toregion(name, &r);
194	return (r.length);
195}
196
197void
198dns_compress_add(dns_compress_t *cctx, const dns_name_t *name,
199		 const dns_name_t *prefix, isc_uint16_t offset)
200{
201	dns_name_t tname;
202	unsigned int start;
203	unsigned int n;
204	unsigned int count;
205	unsigned int hash;
206	dns_compressnode_t *node;
207	unsigned int length;
208	unsigned int tlength;
209	isc_uint16_t toffset;
210
211	REQUIRE(VALID_CCTX(cctx));
212	REQUIRE(dns_name_isabsolute(name));
213
214	dns_name_init(&tname, NULL);
215
216	n = dns_name_countlabels(name);
217	count = dns_name_countlabels(prefix);
218	if (dns_name_isabsolute(prefix))
219		count--;
220	start = 0;
221	length = name_length(name);
222	while (count > 0) {
223		if (offset >= 0x4000)
224			break;
225		dns_name_getlabelsequence(name, start, n, &tname);
226		hash = dns_name_hash(&tname, ISC_FALSE) %
227		       DNS_COMPRESS_TABLESIZE;
228		tlength = name_length(&tname);
229		toffset = (isc_uint16_t)(offset + (length - tlength));
230		/*
231		 * Create a new node and add it.
232		 */
233		if (cctx->count < DNS_COMPRESS_INITIALNODES)
234			node = &cctx->initialnodes[cctx->count];
235		else {
236			node = isc_mem_get(cctx->mctx,
237					   sizeof(dns_compressnode_t));
238			if (node == NULL)
239				return;
240		}
241		node->count = cctx->count++;
242		node->offset = toffset;
243		dns_name_toregion(&tname, &node->r);
244		node->labels = (isc_uint8_t)dns_name_countlabels(&tname);
245		node->next = cctx->table[hash];
246		cctx->table[hash] = node;
247		start++;
248		n--;
249		count--;
250	}
251}
252
253void
254dns_compress_rollback(dns_compress_t *cctx, isc_uint16_t offset) {
255	unsigned int i;
256	dns_compressnode_t *node;
257
258	REQUIRE(VALID_CCTX(cctx));
259
260	for (i = 0; i < DNS_COMPRESS_TABLESIZE; i++) {
261		node = cctx->table[i];
262		/*
263		 * This relies on nodes with greater offsets being
264		 * closer to the beginning of the list, and the
265		 * items with the greatest offsets being at the end
266		 * of the initialnodes[] array.
267		 */
268		while (node != NULL && node->offset >= offset) {
269			cctx->table[i] = node->next;
270			if (node->count >= DNS_COMPRESS_INITIALNODES)
271				isc_mem_put(cctx->mctx, node, sizeof(*node));
272			cctx->count--;
273			node = cctx->table[i];
274		}
275	}
276}
277
278/***
279 ***	Decompression
280 ***/
281
282void
283dns_decompress_init(dns_decompress_t *dctx, int edns,
284		    dns_decompresstype_t type) {
285
286	REQUIRE(dctx != NULL);
287	REQUIRE(edns >= -1 && edns <= 255);
288
289	dctx->allowed = DNS_COMPRESS_NONE;
290	dctx->edns = edns;
291	dctx->type = type;
292	dctx->magic = DCTX_MAGIC;
293}
294
295void
296dns_decompress_invalidate(dns_decompress_t *dctx) {
297
298	REQUIRE(VALID_DCTX(dctx));
299
300	dctx->magic = 0;
301}
302
303void
304dns_decompress_setmethods(dns_decompress_t *dctx, unsigned int allowed) {
305
306	REQUIRE(VALID_DCTX(dctx));
307
308	switch (dctx->type) {
309	case DNS_DECOMPRESS_ANY:
310		dctx->allowed = DNS_COMPRESS_ALL;
311		break;
312	case DNS_DECOMPRESS_NONE:
313		dctx->allowed = DNS_COMPRESS_NONE;
314		break;
315	case DNS_DECOMPRESS_STRICT:
316		dctx->allowed = allowed;
317		break;
318	}
319}
320
321unsigned int
322dns_decompress_getmethods(dns_decompress_t *dctx) {
323
324	REQUIRE(VALID_DCTX(dctx));
325
326	return (dctx->allowed);
327}
328
329int
330dns_decompress_edns(dns_decompress_t *dctx) {
331
332	REQUIRE(VALID_DCTX(dctx));
333
334	return (dctx->edns);
335}
336
337dns_decompresstype_t
338dns_decompress_type(dns_decompress_t *dctx) {
339
340	REQUIRE(VALID_DCTX(dctx));
341
342	return (dctx->type);
343}
344