2 * Copyright (C) 2004-2007 Internet Systems Consortium, Inc. ("ISC")
3 * Copyright (C) 1999-2001 Internet Software Consortium.
5 * Permission to use, copy, modify, and/or distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
9 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
10 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
11 * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
12 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
13 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
14 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
15 * PERFORMANCE OF THIS SOFTWARE.
18 /* $Id: compress.c,v 1.59 2007/06/19 23:47:16 tbox Exp $ */
22 #define DNS_NAME_USEINLINE 1
27 #include <isc/string.h>
30 #include <dns/compress.h>
31 #include <dns/fixedname.h>
33 #include <dns/result.h>
35 #define CCTX_MAGIC ISC_MAGIC('C', 'C', 'T', 'X')
36 #define VALID_CCTX(x) ISC_MAGIC_VALID(x, CCTX_MAGIC)
38 #define DCTX_MAGIC ISC_MAGIC('D', 'C', 'T', 'X')
39 #define VALID_DCTX(x) ISC_MAGIC_VALID(x, DCTX_MAGIC)
46 dns_compress_init(dns_compress_t *cctx, int edns, isc_mem_t *mctx) {
49 REQUIRE(cctx != NULL);
50 REQUIRE(mctx != NULL); /* See: rdataset.c:towiresorted(). */
54 for (i = 0; i < DNS_COMPRESS_TABLESIZE; i++)
55 cctx->table[i] = NULL;
58 cctx->magic = CCTX_MAGIC;
59 return (ISC_R_SUCCESS);
63 dns_compress_invalidate(dns_compress_t *cctx) {
64 dns_compressnode_t *node;
67 REQUIRE(VALID_CCTX(cctx));
70 for (i = 0; i < DNS_COMPRESS_TABLESIZE; i++) {
71 while (cctx->table[i] != NULL) {
72 node = cctx->table[i];
73 cctx->table[i] = cctx->table[i]->next;
74 if (node->count < DNS_COMPRESS_INITIALNODES)
76 isc_mem_put(cctx->mctx, node, sizeof(*node));
84 dns_compress_setmethods(dns_compress_t *cctx, unsigned int allowed) {
85 REQUIRE(VALID_CCTX(cctx));
87 cctx->allowed &= ~DNS_COMPRESS_ALL;
88 cctx->allowed |= (allowed & DNS_COMPRESS_ALL);
92 dns_compress_getmethods(dns_compress_t *cctx) {
93 REQUIRE(VALID_CCTX(cctx));
94 return (cctx->allowed & DNS_COMPRESS_ALL);
98 dns_compress_setsensitive(dns_compress_t *cctx, isc_boolean_t sensitive) {
99 REQUIRE(VALID_CCTX(cctx));
102 cctx->allowed |= DNS_COMPRESS_CASESENSITIVE;
104 cctx->allowed &= ~DNS_COMPRESS_CASESENSITIVE;
108 dns_compress_getsensitive(dns_compress_t *cctx) {
109 REQUIRE(VALID_CCTX(cctx));
111 return (ISC_TF((cctx->allowed & DNS_COMPRESS_CASESENSITIVE) != 0));
115 dns_compress_getedns(dns_compress_t *cctx) {
116 REQUIRE(VALID_CCTX(cctx));
120 #define NODENAME(node, name) \
122 (name)->length = (node)->r.length; \
123 (name)->labels = (node)->labels; \
124 (name)->ndata = (node)->r.base; \
125 (name)->attributes = DNS_NAMEATTR_ABSOLUTE; \
129 * Find the longest match of name in the table.
130 * If match is found return ISC_TRUE. prefix, suffix and offset are updated.
131 * If no match is found return ISC_FALSE.
134 dns_compress_findglobal(dns_compress_t *cctx, const dns_name_t *name,
135 dns_name_t *prefix, isc_uint16_t *offset)
137 dns_name_t tname, nname;
138 dns_compressnode_t *node = NULL;
139 unsigned int labels, hash, n;
141 REQUIRE(VALID_CCTX(cctx));
142 REQUIRE(dns_name_isabsolute(name) == ISC_TRUE);
143 REQUIRE(offset != NULL);
145 if (cctx->count == 0)
148 labels = dns_name_countlabels(name);
151 dns_name_init(&tname, NULL);
152 dns_name_init(&nname, NULL);
154 for (n = 0; n < labels - 1; n++) {
155 dns_name_getlabelsequence(name, n, labels - n, &tname);
156 hash = dns_name_hash(&tname, ISC_FALSE) %
157 DNS_COMPRESS_TABLESIZE;
158 for (node = cctx->table[hash]; node != NULL; node = node->next)
160 NODENAME(node, &nname);
161 if ((cctx->allowed & DNS_COMPRESS_CASESENSITIVE) != 0) {
162 if (dns_name_caseequal(&nname, &tname))
165 if (dns_name_equal(&nname, &tname))
174 * If node == NULL, we found no match at all.
180 dns_name_reset(prefix);
182 dns_name_getlabelsequence(name, 0, n, prefix);
184 *offset = node->offset;
188 static inline unsigned int
189 name_length(const dns_name_t *name) {
191 dns_name_toregion(name, &r);
196 dns_compress_add(dns_compress_t *cctx, const dns_name_t *name,
197 const dns_name_t *prefix, isc_uint16_t offset)
204 dns_compressnode_t *node;
206 unsigned int tlength;
207 isc_uint16_t toffset;
209 REQUIRE(VALID_CCTX(cctx));
210 REQUIRE(dns_name_isabsolute(name));
212 dns_name_init(&tname, NULL);
214 n = dns_name_countlabels(name);
215 count = dns_name_countlabels(prefix);
216 if (dns_name_isabsolute(prefix))
219 length = name_length(name);
221 if (offset >= 0x4000)
223 dns_name_getlabelsequence(name, start, n, &tname);
224 hash = dns_name_hash(&tname, ISC_FALSE) %
225 DNS_COMPRESS_TABLESIZE;
226 tlength = name_length(&tname);
227 toffset = (isc_uint16_t)(offset + (length - tlength));
229 * Create a new node and add it.
231 if (cctx->count < DNS_COMPRESS_INITIALNODES)
232 node = &cctx->initialnodes[cctx->count];
234 node = isc_mem_get(cctx->mctx,
235 sizeof(dns_compressnode_t));
239 node->count = cctx->count++;
240 node->offset = toffset;
241 dns_name_toregion(&tname, &node->r);
242 node->labels = (isc_uint8_t)dns_name_countlabels(&tname);
243 node->next = cctx->table[hash];
244 cctx->table[hash] = node;
252 dns_compress_rollback(dns_compress_t *cctx, isc_uint16_t offset) {
254 dns_compressnode_t *node;
256 REQUIRE(VALID_CCTX(cctx));
258 for (i = 0; i < DNS_COMPRESS_TABLESIZE; i++) {
259 node = cctx->table[i];
261 * This relies on nodes with greater offsets being
262 * closer to the beginning of the list, and the
263 * items with the greatest offsets being at the end
264 * of the initialnodes[] array.
266 while (node != NULL && node->offset >= offset) {
267 cctx->table[i] = node->next;
268 if (node->count >= DNS_COMPRESS_INITIALNODES)
269 isc_mem_put(cctx->mctx, node, sizeof(*node));
271 node = cctx->table[i];
281 dns_decompress_init(dns_decompress_t *dctx, int edns,
282 dns_decompresstype_t type) {
284 REQUIRE(dctx != NULL);
285 REQUIRE(edns >= -1 && edns <= 255);
287 dctx->allowed = DNS_COMPRESS_NONE;
290 dctx->magic = DCTX_MAGIC;
294 dns_decompress_invalidate(dns_decompress_t *dctx) {
296 REQUIRE(VALID_DCTX(dctx));
302 dns_decompress_setmethods(dns_decompress_t *dctx, unsigned int allowed) {
304 REQUIRE(VALID_DCTX(dctx));
306 switch (dctx->type) {
307 case DNS_DECOMPRESS_ANY:
308 dctx->allowed = DNS_COMPRESS_ALL;
310 case DNS_DECOMPRESS_NONE:
311 dctx->allowed = DNS_COMPRESS_NONE;
313 case DNS_DECOMPRESS_STRICT:
314 dctx->allowed = allowed;
320 dns_decompress_getmethods(dns_decompress_t *dctx) {
322 REQUIRE(VALID_DCTX(dctx));
324 return (dctx->allowed);
328 dns_decompress_edns(dns_decompress_t *dctx) {
330 REQUIRE(VALID_DCTX(dctx));
336 dns_decompress_type(dns_decompress_t *dctx) {
338 REQUIRE(VALID_DCTX(dctx));