Patrick Welche <prlw1@cam.ac.uk>
[netbsd-mini2440.git] / external / bsd / bind / dist / lib / dns / compress.c
blob1abd800c319c1a7afd421651d7c22684f3aff8fc
1 /* $NetBSD$ */
3 /*
4 * Copyright (C) 2004-2007 Internet Systems Consortium, Inc. ("ISC")
5 * Copyright (C) 1999-2001 Internet Software Consortium.
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.
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.
20 /* Id: compress.c,v 1.59 2007/06/19 23:47:16 tbox Exp */
22 /*! \file */
24 #define DNS_NAME_USEINLINE 1
26 #include <config.h>
28 #include <isc/mem.h>
29 #include <isc/string.h>
30 #include <isc/util.h>
32 #include <dns/compress.h>
33 #include <dns/fixedname.h>
34 #include <dns/rbt.h>
35 #include <dns/result.h>
37 #define CCTX_MAGIC ISC_MAGIC('C', 'C', 'T', 'X')
38 #define VALID_CCTX(x) ISC_MAGIC_VALID(x, CCTX_MAGIC)
40 #define DCTX_MAGIC ISC_MAGIC('D', 'C', 'T', 'X')
41 #define VALID_DCTX(x) ISC_MAGIC_VALID(x, DCTX_MAGIC)
43 /***
44 *** Compression
45 ***/
47 isc_result_t
48 dns_compress_init(dns_compress_t *cctx, int edns, isc_mem_t *mctx) {
49 unsigned int i;
51 REQUIRE(cctx != NULL);
52 REQUIRE(mctx != NULL); /* See: rdataset.c:towiresorted(). */
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);
64 void
65 dns_compress_invalidate(dns_compress_t *cctx) {
66 dns_compressnode_t *node;
67 unsigned int i;
69 REQUIRE(VALID_CCTX(cctx));
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));
81 cctx->allowed = 0;
82 cctx->edns = -1;
85 void
86 dns_compress_setmethods(dns_compress_t *cctx, unsigned int allowed) {
87 REQUIRE(VALID_CCTX(cctx));
89 cctx->allowed &= ~DNS_COMPRESS_ALL;
90 cctx->allowed |= (allowed & DNS_COMPRESS_ALL);
93 unsigned int
94 dns_compress_getmethods(dns_compress_t *cctx) {
95 REQUIRE(VALID_CCTX(cctx));
96 return (cctx->allowed & DNS_COMPRESS_ALL);
99 void
100 dns_compress_setsensitive(dns_compress_t *cctx, isc_boolean_t sensitive) {
101 REQUIRE(VALID_CCTX(cctx));
103 if (sensitive)
104 cctx->allowed |= DNS_COMPRESS_CASESENSITIVE;
105 else
106 cctx->allowed &= ~DNS_COMPRESS_CASESENSITIVE;
109 isc_boolean_t
110 dns_compress_getsensitive(dns_compress_t *cctx) {
111 REQUIRE(VALID_CCTX(cctx));
113 return (ISC_TF((cctx->allowed & DNS_COMPRESS_CASESENSITIVE) != 0));
117 dns_compress_getedns(dns_compress_t *cctx) {
118 REQUIRE(VALID_CCTX(cctx));
119 return (cctx->edns);
122 #define NODENAME(node, name) \
123 do { \
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 (0)
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.
135 isc_boolean_t
136 dns_compress_findglobal(dns_compress_t *cctx, const dns_name_t *name,
137 dns_name_t *prefix, isc_uint16_t *offset)
139 dns_name_t tname, nname;
140 dns_compressnode_t *node = NULL;
141 unsigned int labels, hash, n;
143 REQUIRE(VALID_CCTX(cctx));
144 REQUIRE(dns_name_isabsolute(name) == ISC_TRUE);
145 REQUIRE(offset != NULL);
147 if (cctx->count == 0)
148 return (ISC_FALSE);
150 labels = dns_name_countlabels(name);
151 INSIST(labels > 0);
153 dns_name_init(&tname, NULL);
154 dns_name_init(&nname, NULL);
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)
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;
171 if (node != NULL)
172 break;
176 * If node == NULL, we found no match at all.
178 if (node == NULL)
179 return (ISC_FALSE);
181 if (n == 0)
182 dns_name_reset(prefix);
183 else
184 dns_name_getlabelsequence(name, 0, n, prefix);
186 *offset = node->offset;
187 return (ISC_TRUE);
190 static inline unsigned int
191 name_length(const dns_name_t *name) {
192 isc_region_t r;
193 dns_name_toregion(name, &r);
194 return (r.length);
197 void
198 dns_compress_add(dns_compress_t *cctx, const dns_name_t *name,
199 const dns_name_t *prefix, isc_uint16_t offset)
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;
211 REQUIRE(VALID_CCTX(cctx));
212 REQUIRE(dns_name_isabsolute(name));
214 dns_name_init(&tname, NULL);
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));
231 * Create a new node and add it.
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;
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--;
253 void
254 dns_compress_rollback(dns_compress_t *cctx, isc_uint16_t offset) {
255 unsigned int i;
256 dns_compressnode_t *node;
258 REQUIRE(VALID_CCTX(cctx));
260 for (i = 0; i < DNS_COMPRESS_TABLESIZE; i++) {
261 node = cctx->table[i];
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.
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];
278 /***
279 *** Decompression
280 ***/
282 void
283 dns_decompress_init(dns_decompress_t *dctx, int edns,
284 dns_decompresstype_t type) {
286 REQUIRE(dctx != NULL);
287 REQUIRE(edns >= -1 && edns <= 255);
289 dctx->allowed = DNS_COMPRESS_NONE;
290 dctx->edns = edns;
291 dctx->type = type;
292 dctx->magic = DCTX_MAGIC;
295 void
296 dns_decompress_invalidate(dns_decompress_t *dctx) {
298 REQUIRE(VALID_DCTX(dctx));
300 dctx->magic = 0;
303 void
304 dns_decompress_setmethods(dns_decompress_t *dctx, unsigned int allowed) {
306 REQUIRE(VALID_DCTX(dctx));
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;
321 unsigned int
322 dns_decompress_getmethods(dns_decompress_t *dctx) {
324 REQUIRE(VALID_DCTX(dctx));
326 return (dctx->allowed);
330 dns_decompress_edns(dns_decompress_t *dctx) {
332 REQUIRE(VALID_DCTX(dctx));
334 return (dctx->edns);
337 dns_decompresstype_t
338 dns_decompress_type(dns_decompress_t *dctx) {
340 REQUIRE(VALID_DCTX(dctx));
342 return (dctx->type);