compress.c revision 1d6572f9d4766a7329e2d207b9f7af50092663ae
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews/*
499b34cea04a46823d003d4c0520c8b03e8513cbBrian Wellington * Copyright (C) 1999 Internet Software Consortium.
40f53fa8d9c6a4fc38c0014495e7a42b08f52481David Lawrence *
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews * Permission to use, copy, modify, and distribute this software for any
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews * purpose with or without fee is hereby granted, provided that the above
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews * copyright notice and this permission notice appear in all copies.
40f53fa8d9c6a4fc38c0014495e7a42b08f52481David Lawrence *
15a44745412679c30a6d022733925af70a38b715David Lawrence * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS
15a44745412679c30a6d022733925af70a38b715David Lawrence * ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES
15a44745412679c30a6d022733925af70a38b715David Lawrence * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE
15a44745412679c30a6d022733925af70a38b715David Lawrence * CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL
15a44745412679c30a6d022733925af70a38b715David Lawrence * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
15a44745412679c30a6d022733925af70a38b715David Lawrence * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
15a44745412679c30a6d022733925af70a38b715David Lawrence * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
15a44745412679c30a6d022733925af70a38b715David Lawrence * SOFTWARE.
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews */
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews
dcc7ea97174501f0409c0c919b3ca04083e4e1b8Andreas Gustafsson /* $Id: compress.c,v 1.14 1999/04/28 03:16:50 marka Exp $ */
9c3531d72aeaad6c5f01efe6a1c82023e1379e4dDavid Lawrence
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews#include <config.h>
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews#include <string.h>
92ef1a9b9dbd48ecb507b42ac62c15afefdaf838David Lawrence
1a69a1a78cfaa86f3b68bbc965232b7876d4da2aDavid Lawrence#include <isc/types.h>
34ee961fa2f0f5f2ee3cff40fdb4d7d7b48b7728Mark Andrews#include <isc/assertions.h>
34ee961fa2f0f5f2ee3cff40fdb4d7d7b48b7728Mark Andrews#include <isc/buffer.h>
34ee961fa2f0f5f2ee3cff40fdb4d7d7b48b7728Mark Andrews
34ee961fa2f0f5f2ee3cff40fdb4d7d7b48b7728Mark Andrews#include <dns/compress.h>
e21d199dca95aff5d50f133d6b064309e209af00Brian Wellington#include <dns/fixedname.h>
e43b9a20054cdda6946ab758e1c2005f2b25641aBrian Wellington
34ee961fa2f0f5f2ee3cff40fdb4d7d7b48b7728Mark Andrews#define CCTX_MAGIC 0x43435458U /* CCTX */
34ee961fa2f0f5f2ee3cff40fdb4d7d7b48b7728Mark Andrews#define VALID_CCTX(x) ((x) != NULL && (x)->magic == CCTX_MAGIC)
8b61d2012063306528286680bd9f086fa868d86eMark Andrews
34ee961fa2f0f5f2ee3cff40fdb4d7d7b48b7728Mark Andrews#define DCTX_MAGIC 0x44435458U /* DCTX */
19d1b1667d073850d4366352aaf8319efc5debeeBrian Wellington#define VALID_DCTX(x) ((x) != NULL && (x)->magic == DCTX_MAGIC)
19d1b1667d073850d4366352aaf8319efc5debeeBrian Wellington
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrewsstatic void free_offset(void *offset, void *mctx);
09f22ac5b09e70bc526015f37168ba33e21ea91fDavid Lawrenceisc_boolean_t compress_find(dns_rbt_t *root, dns_name_t *name,
19d1b1667d073850d4366352aaf8319efc5debeeBrian Wellington dns_name_t *prefix, dns_name_t *suffix,
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews isc_uint16_t *offset,
92ef1a9b9dbd48ecb507b42ac62c15afefdaf838David Lawrence isc_buffer_t *workspace);
92ef1a9b9dbd48ecb507b42ac62c15afefdaf838David Lawrencevoid compress_add(dns_rbt_t *root, dns_name_t *prefix,
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews dns_name_t *suffix, isc_uint16_t offset,
92ef1a9b9dbd48ecb507b42ac62c15afefdaf838David Lawrence isc_boolean_t global16, isc_mem_t *mctx);
92ef1a9b9dbd48ecb507b42ac62c15afefdaf838David Lawrence
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews#undef MPADCL
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews#ifdef MPADCL
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrewsisc_buffer_t x;
440164d3e36353a4b9801fcc05fe66b6cf1fb8ceMark Andrewschar xxxx[1024];
440164d3e36353a4b9801fcc05fe66b6cf1fb8ceMark Andrews#endif
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff/***
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff *** Compression
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff ***/
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrewsdns_result_t
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graffdns_compress_init(dns_compress_t *cctx, int edns, isc_mem_t *mctx)
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff{
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff dns_result_t result;
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff
46993e1d9d18410a5852b7d990338b70b158855cMichael Graff REQUIRE(cctx != NULL);
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff REQUIRE(mctx != NULL);
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff cctx->allowed = 0;
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff cctx->rdata = 0;
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff cctx->global16 = (edns >= 1) ? ISC_TRUE : ISC_FALSE;
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff cctx->edns = edns;
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff cctx->local = NULL;
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff cctx->global = NULL;
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews result = dns_rbt_create(mctx, free_offset, mctx, &cctx->global);
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews if (result != DNS_R_SUCCESS)
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews return (result);
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff cctx->mctx = mctx;
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff cctx->magic = CCTX_MAGIC;
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff return (DNS_R_SUCCESS);
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff}
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graffdns_result_t
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graffdns_compress_localinit(dns_compress_t *cctx, dns_name_t *owner,
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff isc_buffer_t *target)
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff{
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff dns_result_t result;
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff unsigned int labels;
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff unsigned int ll; /* logical label length w/o root label */
0f80bfec687db08a6e6ce945ef1d818da06c7ca9Brian Wellington unsigned int wl; /* wire labels */
19d1b1667d073850d4366352aaf8319efc5debeeBrian Wellington unsigned int bits;
8126e45e8cc3fd54517c034dd30a42928f5206e3Andreas Gustafsson dns_name_t name;
8126e45e8cc3fd54517c034dd30a42928f5206e3Andreas Gustafsson dns_name_t prefix;
34ee961fa2f0f5f2ee3cff40fdb4d7d7b48b7728Mark Andrews dns_name_t suffix;
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews dns_label_t label;
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews isc_uint16_t *data;
046a9aca49bdc25bd57d75fd0dd34c021722f095Mark Andrews unsigned char buf[34];
046a9aca49bdc25bd57d75fd0dd34c021722f095Mark Andrews unsigned char namebuf[255];
046a9aca49bdc25bd57d75fd0dd34c021722f095Mark Andrews isc_buffer_t t;
046a9aca49bdc25bd57d75fd0dd34c021722f095Mark Andrews isc_region_t region;
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews REQUIRE(VALID_CCTX(cctx));
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews REQUIRE(cctx->local == NULL);
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews REQUIRE(dns_name_isabsolute(owner) == ISC_TRUE);
046a9aca49bdc25bd57d75fd0dd34c021722f095Mark Andrews REQUIRE(isc_buffer_type(target) == ISC_BUFFERTYPE_BINARY);
046a9aca49bdc25bd57d75fd0dd34c021722f095Mark Andrews
0ad8ee89c532951a55b7de25317eeca2c3b2ed63Andreas Gustafsson result = dns_rbt_create(cctx->mctx, free_offset, cctx->mctx,
0ad8ee89c532951a55b7de25317eeca2c3b2ed63Andreas Gustafsson &cctx->local);
f53848e17123569387b279578f0100dca5407da5Mark Andrews if (result != DNS_R_SUCCESS)
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews return (result);
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews /*
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews * Errors from here on are not passed back up.
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews */
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews cctx->rdata = target->used; /* XXX layer violation */
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews labels = dns_name_countlabels(owner);
440164d3e36353a4b9801fcc05fe66b6cf1fb8ceMark Andrews if (labels <= 1) /* can't compress root label */
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews return (DNS_R_SUCCESS);
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews ll = 0; /* logical label index 0 == TLD not root */
59abb512d344bfa09012cc11b7d814966f035da4Mark Andrews wl = 2; /* minimum number of wire labels */
559bb1016f1b00a3661cb2790dc837a977057b86Mark Andrews dns_name_init(&name, NULL);
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews dns_name_init(&prefix, NULL);
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews dns_name_init(&suffix, NULL);
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews /*
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews * Work from the TLD label to the least signfiant label.
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews */
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews while (labels >= wl) {
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews dns_name_getlabelsequence(owner, labels - wl, wl, &name);
8b61d2012063306528286680bd9f086fa868d86eMark Andrews dns_name_getlabel(&name, 0, &label);
8126e45e8cc3fd54517c034dd30a42928f5206e3Andreas Gustafsson /*
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews * If it is not a bit string label add to tree.
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews */
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews if (dns_label_type(&label) != dns_labeltype_bitstring) {
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews data = isc_mem_get(cctx->mctx, sizeof *data);
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews if (data == NULL)
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews return (DNS_R_SUCCESS);
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews *data = ll;
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews#ifdef MPADCL
46993e1d9d18410a5852b7d990338b70b158855cMichael Graff isc_buffer_init(&x, xxxx, sizeof xxxx,
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff ISC_BUFFERTYPE_TEXT);
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews dns_name_totext(&name, ISC_FALSE, &x);
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews fprintf(stdout,
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews "dns_rbt_addname(local, \"%.*s\", %d)\n",
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews (int)x.used, (char*)x.base, *data);
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews#endif
34ee961fa2f0f5f2ee3cff40fdb4d7d7b48b7728Mark Andrews
34ee961fa2f0f5f2ee3cff40fdb4d7d7b48b7728Mark Andrews result = dns_rbt_addname(cctx->local, &name, data);
440164d3e36353a4b9801fcc05fe66b6cf1fb8ceMark Andrews if (result != DNS_R_SUCCESS) {
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews isc_mem_put(cctx->mctx, data, sizeof *data);
8b61d2012063306528286680bd9f086fa868d86eMark Andrews return (DNS_R_SUCCESS);
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews }
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews wl++;
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews ll++;
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews if (ll > 254)
46993e1d9d18410a5852b7d990338b70b158855cMichael Graff return (DNS_R_SUCCESS);
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff continue;
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews }
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews /*
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews * Have to compute logical for bit string labels.
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews */
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews /* XXX MPA need to test once rbt supports bit labels fully */
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews bits = dns_label_countbits(&label);
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews INSIST(label.length < sizeof buf);
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews memcpy(buf, label.base, label.length);
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews region.base = buf;
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews dns_name_getlabelsequence(owner, 1, wl - 1, &suffix);
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews /*
34ee961fa2f0f5f2ee3cff40fdb4d7d7b48b7728Mark Andrews * It is easier to do this the reverse way.
419590499823ce15b5d2ad4fe71eaf04bd5a86c0Michael Graff * Adding 'bits' to 'll' may exceed the maximum logical
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews * offset index. Throw away bits until ll <= 254.
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews */
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews ll += bits - 1;
440164d3e36353a4b9801fcc05fe66b6cf1fb8ceMark Andrews while (ll > 254 && bits > 0) {
440164d3e36353a4b9801fcc05fe66b6cf1fb8ceMark Andrews /* clear bit */
419590499823ce15b5d2ad4fe71eaf04bd5a86c0Michael Graff bits--;
440164d3e36353a4b9801fcc05fe66b6cf1fb8ceMark Andrews buf[2 + bits / 8] &= ~(1 << (7 - (bits % 8)));
5e387b9ce6bafdfadedb5b34e4c33a4404e5d589Brian Wellington ll--;
5e387b9ce6bafdfadedb5b34e4c33a4404e5d589Brian Wellington }
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews /*
440164d3e36353a4b9801fcc05fe66b6cf1fb8ceMark Andrews * Add entries to tree.
440164d3e36353a4b9801fcc05fe66b6cf1fb8ceMark Andrews */
440164d3e36353a4b9801fcc05fe66b6cf1fb8ceMark Andrews do {
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews region.length = 2 + (bits + 7) / 8;
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews buf[1] = bits;
46993e1d9d18410a5852b7d990338b70b158855cMichael Graff dns_name_fromregion(&prefix, &region);
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff isc_buffer_init(&t, namebuf, sizeof namebuf,
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews ISC_BUFFERTYPE_BINARY);
34ee961fa2f0f5f2ee3cff40fdb4d7d7b48b7728Mark Andrews result = dns_name_concatenate(&prefix, &suffix, &name,
34ee961fa2f0f5f2ee3cff40fdb4d7d7b48b7728Mark Andrews &t);
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews if (result != DNS_R_SUCCESS)
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews return (DNS_R_SUCCESS);
34ee961fa2f0f5f2ee3cff40fdb4d7d7b48b7728Mark Andrews data = isc_mem_get(cctx->mctx, sizeof *data);
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews if (data == NULL)
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews return (DNS_R_SUCCESS);
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews *data = ll;
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews#ifdef MPADCL
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews isc_buffer_init(&x, xxxx, sizeof xxxx,
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews ISC_BUFFERTYPE_TEXT);
440164d3e36353a4b9801fcc05fe66b6cf1fb8ceMark Andrews dns_name_totext(&name, ISC_FALSE, &x);
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews fprintf(stdout,
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews "dns_rbt_addname(local, \"%.*s\", %d)\n",
8b61d2012063306528286680bd9f086fa868d86eMark Andrews (int)x.used, (char *)x.base,
8b61d2012063306528286680bd9f086fa868d86eMark Andrews *data);
8b61d2012063306528286680bd9f086fa868d86eMark Andrews#endif
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews result = dns_rbt_addname(cctx->local, &name, data);
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews if (result != DNS_R_SUCCESS) {
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews isc_mem_put(cctx->mctx, data, sizeof *data);
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews return (DNS_R_SUCCESS);
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews }
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews /* clear bit */
78838d3e0cd62423c23de5503910e01884d2104bBrian Wellington bits--;
78838d3e0cd62423c23de5503910e01884d2104bBrian Wellington buf[2 + bits / 8] &= ~(1 << (7 - (bits % 8)));
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews ll--;
8b61d2012063306528286680bd9f086fa868d86eMark Andrews } while (bits > 0);
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews wl++;
78838d3e0cd62423c23de5503910e01884d2104bBrian Wellington bits = dns_label_countbits(&label);
78838d3e0cd62423c23de5503910e01884d2104bBrian Wellington ll += bits;
78838d3e0cd62423c23de5503910e01884d2104bBrian Wellington if (ll > 254)
78838d3e0cd62423c23de5503910e01884d2104bBrian Wellington return (DNS_R_SUCCESS);
78838d3e0cd62423c23de5503910e01884d2104bBrian Wellington }
78838d3e0cd62423c23de5503910e01884d2104bBrian Wellington return (DNS_R_SUCCESS);
78838d3e0cd62423c23de5503910e01884d2104bBrian Wellington}
78838d3e0cd62423c23de5503910e01884d2104bBrian Wellington
78838d3e0cd62423c23de5503910e01884d2104bBrian Wellingtonvoid
78838d3e0cd62423c23de5503910e01884d2104bBrian Wellingtondns_compress_invalidate(dns_compress_t *cctx) {
78838d3e0cd62423c23de5503910e01884d2104bBrian Wellington
78838d3e0cd62423c23de5503910e01884d2104bBrian Wellington REQUIRE(VALID_CCTX(cctx));
78838d3e0cd62423c23de5503910e01884d2104bBrian Wellington
78838d3e0cd62423c23de5503910e01884d2104bBrian Wellington cctx->magic = 0;
78838d3e0cd62423c23de5503910e01884d2104bBrian Wellington if (cctx->global != NULL)
78838d3e0cd62423c23de5503910e01884d2104bBrian Wellington dns_rbt_destroy(&cctx->global);
78838d3e0cd62423c23de5503910e01884d2104bBrian Wellington if (cctx->local != NULL)
78838d3e0cd62423c23de5503910e01884d2104bBrian Wellington dns_rbt_destroy(&cctx->local);
78838d3e0cd62423c23de5503910e01884d2104bBrian Wellington cctx->allowed = 0;
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews cctx->rdata = 0;
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews cctx->global16 = ISC_FALSE;
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews cctx->edns = -1;
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews}
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrewsvoid
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrewsdns_compress_localinvalidate(dns_compress_t *cctx) {
78838d3e0cd62423c23de5503910e01884d2104bBrian Wellington
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews REQUIRE(VALID_CCTX(cctx));
8b61d2012063306528286680bd9f086fa868d86eMark Andrews
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews if (cctx->local != NULL)
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews dns_rbt_destroy(&cctx->local);
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews}
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrewsvoid
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrewsdns_compress_setmethods(dns_compress_t *cctx, unsigned int allowed) {
40f53fa8d9c6a4fc38c0014495e7a42b08f52481David Lawrence REQUIRE(VALID_CCTX(cctx));
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews if (cctx->edns >= 1 && (allowed & DNS_COMPRESS_GLOBAL14) != 0)
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews allowed |= DNS_COMPRESS_GLOBAL16;
8b61d2012063306528286680bd9f086fa868d86eMark Andrews cctx->allowed = allowed;
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews}
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrewsunsigned int
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrewsdns_compress_getmethods(dns_compress_t *cctx) {
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews REQUIRE(VALID_CCTX(cctx));
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews return (cctx->allowed);
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews}
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrewsint
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrewsdns_compress_getedns(dns_compress_t *cctx) {
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews REQUIRE(VALID_CCTX(cctx));
4be19dcd14cea678511f1d1b269ab89273e987eeMark Andrews return (cctx->edns);
4be19dcd14cea678511f1d1b269ab89273e987eeMark Andrews}
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews
4be19dcd14cea678511f1d1b269ab89273e987eeMark Andrewsisc_boolean_t
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrewsdns_compress_findglobal(dns_compress_t *cctx, dns_name_t *name,
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews dns_name_t *prefix, dns_name_t *suffix,
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews isc_uint16_t *offset, isc_buffer_t *workspace)
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews{
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews REQUIRE(VALID_CCTX(cctx));
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews REQUIRE(dns_name_isabsolute(name) == ISC_TRUE);
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews REQUIRE(offset != NULL);
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews#ifdef MPADCL
78838d3e0cd62423c23de5503910e01884d2104bBrian Wellington isc_buffer_init(&x, xxxx, sizeof xxxx,
78838d3e0cd62423c23de5503910e01884d2104bBrian Wellington ISC_BUFFERTYPE_TEXT);
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews dns_name_totext(name, ISC_FALSE, &x);
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews fprintf(stdout, "compress_find(global, name \"%.*s\", ...)\n",
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews (int)x.used, (char*)x.base);
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews#endif
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews
8b61d2012063306528286680bd9f086fa868d86eMark Andrews return (compress_find(cctx->global, name, prefix, suffix, offset,
8b61d2012063306528286680bd9f086fa868d86eMark Andrews workspace));
8b61d2012063306528286680bd9f086fa868d86eMark Andrews}
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrewsisc_boolean_t
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrewsdns_compress_findlocal(dns_compress_t *cctx, dns_name_t *name,
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews dns_name_t *prefix, dns_name_t *suffix,
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews isc_uint16_t *offset, isc_buffer_t *workspace)
f53848e17123569387b279578f0100dca5407da5Mark Andrews{
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews REQUIRE(VALID_CCTX(cctx));
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews REQUIRE(dns_name_isabsolute(name) == ISC_TRUE);
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews REQUIRE(offset != NULL);
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews
8b61d2012063306528286680bd9f086fa868d86eMark Andrews if (cctx->local == NULL)
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews return (ISC_FALSE);
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews#ifdef MPADCL
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews isc_buffer_init(&x, xxxx, sizeof xxxx,
8b61d2012063306528286680bd9f086fa868d86eMark Andrews ISC_BUFFERTYPE_TEXT);
8b61d2012063306528286680bd9f086fa868d86eMark Andrews dns_name_totext(name, ISC_FALSE, &x);
8b61d2012063306528286680bd9f086fa868d86eMark Andrews fprintf(stdout, "compress_find(local, name \"%.*s\", ...)\n",
8b61d2012063306528286680bd9f086fa868d86eMark Andrews (int)x.used, (char*)x.base);
4be19dcd14cea678511f1d1b269ab89273e987eeMark Andrews#endif
4be19dcd14cea678511f1d1b269ab89273e987eeMark Andrews
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews
4be19dcd14cea678511f1d1b269ab89273e987eeMark Andrews return (compress_find(cctx->local, name, prefix, suffix, offset,
4be19dcd14cea678511f1d1b269ab89273e987eeMark Andrews workspace));
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews}
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrewsvoid
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrewsdns_compress_add(dns_compress_t *cctx, dns_name_t *prefix,
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews dns_name_t *suffix, isc_uint16_t offset,
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews isc_boolean_t local)
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews{
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews isc_uint16_t localoffset;
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews REQUIRE(VALID_CCTX(cctx));
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews
78838d3e0cd62423c23de5503910e01884d2104bBrian Wellington if (cctx->local != NULL && (cctx->allowed & DNS_COMPRESS_LOCAL) != 0) {
78838d3e0cd62423c23de5503910e01884d2104bBrian Wellington REQUIRE(cctx->rdata <= offset);
34ee961fa2f0f5f2ee3cff40fdb4d7d7b48b7728Mark Andrews localoffset = offset - cctx->rdata + 256;
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews#ifdef MPADCL
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews fprintf(stdout, "compress_add(local, ...)\n");
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews#endif
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews compress_add(cctx->local, prefix, suffix, localoffset, ISC_TRUE,
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews cctx->mctx);
8b61d2012063306528286680bd9f086fa868d86eMark Andrews }
8b61d2012063306528286680bd9f086fa868d86eMark Andrews if ((cctx->edns > -1) || !local) {
8b61d2012063306528286680bd9f086fa868d86eMark Andrews#ifdef MPADCL
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews fprintf(stdout, "compress_add(global, ...)\n");
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews#endif
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews compress_add(cctx->global, prefix, suffix, offset,
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews cctx->global16, cctx->mctx);
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews }
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews}
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrewsvoid
34ee961fa2f0f5f2ee3cff40fdb4d7d7b48b7728Mark Andrewsdns_compress_backout(dns_compress_t *cctx, isc_uint16_t offset) {
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews REQUIRE(VALID_CCTX(cctx));
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews /* XXX MPA need tree walking code */
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews /* Remove all nodes in cctx->global that have *data >= offset. */
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews
8b61d2012063306528286680bd9f086fa868d86eMark Andrews}
8b61d2012063306528286680bd9f086fa868d86eMark Andrews
8b61d2012063306528286680bd9f086fa868d86eMark Andrews/***
8b61d2012063306528286680bd9f086fa868d86eMark Andrews *** Decompression
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews ***/
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrewsvoid
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrewsdns_decompress_init(dns_decompress_t *dctx, int edns, isc_boolean_t strict) {
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews
34ee961fa2f0f5f2ee3cff40fdb4d7d7b48b7728Mark Andrews REQUIRE(dctx != NULL);
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews REQUIRE(edns >= -1 && edns <= 255);
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews dctx->allowed = DNS_COMPRESS_NONE;
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews dctx->edns = edns;
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews dctx->strict = strict;
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews dctx->rdata = 0;
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews dns_name_init(&dctx->owner_name, NULL);
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews dns_name_invalidate(&dctx->owner_name);
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews dctx->magic = DCTX_MAGIC;
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews}
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrewsvoid
8b61d2012063306528286680bd9f086fa868d86eMark Andrewsdns_decompress_localinit(dns_decompress_t *dctx, dns_name_t *name,
8b61d2012063306528286680bd9f086fa868d86eMark Andrews isc_buffer_t *source)
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews{
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews REQUIRE(VALID_DCTX(dctx));
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews REQUIRE(dns_name_isabsolute(name) == ISC_TRUE);
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews REQUIRE(isc_buffer_type(source) == ISC_BUFFERTYPE_BINARY);
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews dctx->rdata = source->current;
e44487bfc23599b6b240e09d83d1c862fecfcc82Michael Graff dctx->owner_name = *name;
e44487bfc23599b6b240e09d83d1c862fecfcc82Michael Graff}
e44487bfc23599b6b240e09d83d1c862fecfcc82Michael Graff
e44487bfc23599b6b240e09d83d1c862fecfcc82Michael Graffvoid
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrewsdns_decompress_invalidate(dns_decompress_t *dctx) {
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews REQUIRE(VALID_DCTX(dctx));
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews dctx->magic = 0;
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews}
440164d3e36353a4b9801fcc05fe66b6cf1fb8ceMark Andrews
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrewsvoid
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrewsdns_decompress_localinvalidate(dns_decompress_t *dctx) {
8b61d2012063306528286680bd9f086fa868d86eMark Andrews
440164d3e36353a4b9801fcc05fe66b6cf1fb8ceMark Andrews REQUIRE(VALID_DCTX(dctx));
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews dns_name_invalidate(&dctx->owner_name);
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews}
5e387b9ce6bafdfadedb5b34e4c33a4404e5d589Brian Wellington
440164d3e36353a4b9801fcc05fe66b6cf1fb8ceMark Andrewsvoid
5e387b9ce6bafdfadedb5b34e4c33a4404e5d589Brian Wellingtondns_decompress_setmethods(dns_decompress_t *dctx, unsigned int allowed) {
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews REQUIRE(VALID_DCTX(dctx));
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews dctx->allowed = allowed;
34ee961fa2f0f5f2ee3cff40fdb4d7d7b48b7728Mark Andrews}
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrews
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrewsunsigned int
a5c30de2601a1d130a15a78cf3dc7610a02b2d85Mark Andrewsdns_decompress_getmethods(dns_decompress_t *dctx) {
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews
b54630c4518a1a173fee3478f4bf51dff450b6dcMark Andrews REQUIRE(VALID_DCTX(dctx));
440164d3e36353a4b9801fcc05fe66b6cf1fb8ceMark Andrews
440164d3e36353a4b9801fcc05fe66b6cf1fb8ceMark Andrews return (dctx->allowed);
8b61d2012063306528286680bd9f086fa868d86eMark Andrews}
440164d3e36353a4b9801fcc05fe66b6cf1fb8ceMark Andrews
440164d3e36353a4b9801fcc05fe66b6cf1fb8ceMark Andrewsint
440164d3e36353a4b9801fcc05fe66b6cf1fb8ceMark Andrewsdns_decompress_edns(dns_decompress_t *dctx) {
440164d3e36353a4b9801fcc05fe66b6cf1fb8ceMark Andrews
668eb43f1f24c887b6972f6a1610b4b38b281080Brian Wellington REQUIRE(VALID_DCTX(dctx));
440164d3e36353a4b9801fcc05fe66b6cf1fb8ceMark Andrews
440164d3e36353a4b9801fcc05fe66b6cf1fb8ceMark Andrews return (dctx->edns);
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews}
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrewsisc_boolean_t
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrewsdns_decompress_strict(dns_decompress_t *dctx) {
046a9aca49bdc25bd57d75fd0dd34c021722f095Mark Andrews
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews REQUIRE(VALID_DCTX(dctx));
8b61d2012063306528286680bd9f086fa868d86eMark Andrews
8b61d2012063306528286680bd9f086fa868d86eMark Andrews return (dctx->strict);
390b2077fc751105e40174ceaa1ce34ef06e7dd4Mark Andrews}
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews
6e49e91bd08778d7eae45a2229dcf41ed97cc636David Lawrence/***
046a9aca49bdc25bd57d75fd0dd34c021722f095Mark Andrews *** Private
046a9aca49bdc25bd57d75fd0dd34c021722f095Mark Andrews ***/
046a9aca49bdc25bd57d75fd0dd34c021722f095Mark Andrews
046a9aca49bdc25bd57d75fd0dd34c021722f095Mark Andrewsstatic void
046a9aca49bdc25bd57d75fd0dd34c021722f095Mark Andrewsfree_offset(void *offset, void *mctx) {
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews REQUIRE(offset != NULL);
78da321b437bbb690ef570ccf17dcc8583a5a4a0Mark Andrews REQUIRE(mctx != NULL);
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington isc_mem_put(mctx, offset, sizeof(isc_uint16_t));
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington}
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington/*
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington * Add the labels in prefix to RBT.
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington */
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellingtonvoid
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellingtoncompress_add(dns_rbt_t *root, dns_name_t *prefix, dns_name_t *suffix,
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington isc_uint16_t offset, isc_boolean_t global16, isc_mem_t *mctx)
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington{
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington dns_name_t name;
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington dns_name_t full;
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington dns_label_t label;
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington unsigned int count;
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington unsigned int start;
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington unsigned int limit;
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington isc_uint16_t *data;
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington dns_result_t result;
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington unsigned char buffer[255];
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington isc_buffer_t target;
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington dns_offsets_t offsets;
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington count = dns_name_countlabels(prefix);
8126e45e8cc3fd54517c034dd30a42928f5206e3Andreas Gustafsson limit = dns_name_isabsolute(prefix) ? 1 : 0;
8126e45e8cc3fd54517c034dd30a42928f5206e3Andreas Gustafsson start = 0;
8126e45e8cc3fd54517c034dd30a42928f5206e3Andreas Gustafsson dns_name_init(&full, offsets);
8126e45e8cc3fd54517c034dd30a42928f5206e3Andreas Gustafsson dns_name_init(&name, NULL);
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington while (count > limit) {
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington if (offset >= 16384 && !global16)
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington break;
ac6afcd0caf72aaa2a537e0003de30b363b4a68bBrian Wellington dns_name_getlabelsequence(prefix, start, count, &name);
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington isc_buffer_init(&target, buffer, sizeof buffer,
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington ISC_BUFFERTYPE_BINARY);
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington result = dns_name_concatenate(&name, suffix, &full, &target);
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington if (result != DNS_R_SUCCESS)
dac1e1dd18b62be8cc3bec1a3656968b7b8633e6Brian Wellington return;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews data = isc_mem_get(mctx, sizeof *data);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews if (data == NULL)
97f26b88f62b10a9c26a91ebe8387d2e498c2d00Andreas Gustafsson return;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews *data = offset;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews#ifdef MPADCL
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews isc_buffer_init(&x, xxxx, sizeof xxxx,
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews ISC_BUFFERTYPE_TEXT);
97f26b88f62b10a9c26a91ebe8387d2e498c2d00Andreas Gustafsson dns_name_totext(&full, ISC_FALSE, &x);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews fprintf(stdout,
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews "dns_rbt_addname(root, \"%.*s\", %d)\n",
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews (int)x.used, (char*)x.base, *data);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews#endif
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews result = dns_rbt_addname(root, &full, data);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews if (result != DNS_R_SUCCESS) {
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews isc_mem_put(mctx, data, sizeof *data);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews return;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews }
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews dns_name_getlabel(&name, 0, &label);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews offset += label.length;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews start++;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews count--;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews }
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews}
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews/*
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews * Find the loggest match of name in root.
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews * If match is found return ISC_TRUE. prefix, suffix and offset
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews * are updated.
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews * If no match is found return ISC_FALSE.
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews */
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrewsisc_boolean_t
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrewscompress_find(dns_rbt_t *root, dns_name_t *name, dns_name_t *prefix,
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews dns_name_t *suffix, isc_uint16_t *offset,
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews isc_buffer_t *workspace)
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews{
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews dns_fixedname_t found;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews dns_name_t *foundname;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews dns_name_t tmpprefix;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews dns_name_t tmpsuffix;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews dns_result_t result;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews isc_uint16_t *data = NULL;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews dns_label_t foundlabel;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews dns_label_t namelabel;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews unsigned int foundlabels;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews unsigned int namelabels;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews unsigned int foundbits;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews unsigned int namebits;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews unsigned int bits;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews unsigned int prefixlen;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews unsigned int j;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews unsigned char buf[2 + 256/8]; /* size of biggest bit label */
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews dns_bitlabel_t bit;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews isc_region_t region;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews dns_fixedname_init(&found);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews foundname = dns_fixedname_name(&found);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews result = dns_rbt_findname(root, name, foundname, (void *)&data);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews if (result != DNS_R_SUCCESS && result != DNS_R_PARTIALMATCH)
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews return (ISC_FALSE);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews if (data == NULL) /* root label */
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews return (ISC_FALSE);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews#ifdef MPADCL
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews isc_buffer_init(&x, xxxx, sizeof xxxx,
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews ISC_BUFFERTYPE_TEXT);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews dns_name_totext(foundname, ISC_FALSE, &x);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews fprintf(stdout, "foundname \"%.*s\" %d\n",
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews (int)x.used, (char*)x.base, *data);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews#endif
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews /*
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews * Do we have to do bit string processing?
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews */
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews dns_name_getlabel(foundname, 0, &foundlabel);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews foundlabels = dns_name_countlabels(foundname);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews INSIST(foundlabels > 1); /* root labels are not added to tree */
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews namelabels = dns_name_countlabels(name);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews if (dns_label_type(&foundlabel) == dns_labeltype_bitstring) {
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews dns_name_getlabel(name, namelabels - foundlabels, &namelabel);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews INSIST(dns_label_type(&namelabel) == dns_labeltype_bitstring);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews foundbits = dns_label_countbits(&foundlabel);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews namebits = dns_label_countbits(&namelabel);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews } else
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews namebits = foundbits = 0;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews if (namebits == foundbits) {
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews INSIST(namelabels >= foundlabels);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews prefixlen = namelabels - foundlabels;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews if (prefixlen == 0) {
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews prefix->length = 0;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews prefix->labels = 0;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews } else
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews dns_name_getlabelsequence(name, 0, prefixlen, prefix);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews dns_name_getlabelsequence(foundname, 0, foundlabels, suffix);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews *offset = *data;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews#ifdef MPADCL
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews if (prefixlen != 0) {
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews isc_buffer_init(&x, xxxx, sizeof xxxx,
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews ISC_BUFFERTYPE_TEXT);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews dns_name_totext(prefix, ISC_FALSE, &x);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews fprintf(stdout, "prefix \"%.*s\"\n",
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews (int)x.used, (char*)x.base);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews } else
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews fprintf(stdout, "prefix <EMPTY>\n");
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews isc_buffer_init(&x, xxxx, sizeof xxxx,
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews ISC_BUFFERTYPE_TEXT);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews dns_name_totext(suffix, ISC_FALSE, &x);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews fprintf(stdout, "suffix \"%.*s\"\n",
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews (int)x.used, (char*)x.base);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews#endif
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews return (ISC_TRUE);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews }
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews /* XXX MPA needs to be tested */
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews /*
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews * At this stage we have a bit string label to split in two.
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews * There is potentially a prefix before this label and definitly
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews * a suffix after it (if only the root).
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews */
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews INSIST(result == DNS_R_PARTIALMATCH);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews dns_name_getlabelsequence(foundname, 0, foundlabels, suffix);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews prefixlen = namelabels - foundlabels;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews dns_name_init(&tmpprefix, NULL);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews dns_name_init(&tmpsuffix, NULL);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews if (prefixlen != 0) {
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews dns_name_getlabelsequence(name, 0, prefixlen, &tmpprefix);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews }
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews INSIST(namebits > foundbits);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews bits = namebits - foundbits;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews j = 0;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews memset(buf, 0, sizeof buf);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews INSIST((bits / 8 + 1) < sizeof buf);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews /*
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews * Copy least significant bits.
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews */
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews while (j < bits) {
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews bit = dns_label_getbit(&namelabel, foundbits + j);
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews if (bit)
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews buf[2 + j / 8] |= (1 << (7 - (j % 8)));
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews j++;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews }
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews buf[0] = DNS_LABELTYPE_BITSTRING;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews buf[1] = j;
7c2dce3c4d2c863ff268576f13c4ddd6f29d67edMark Andrews region.base = buf;
056141f2878d1046306ef0ba035263a00de57f98Mark Andrews region.length = 2 + (j + 7) / 8;
056141f2878d1046306ef0ba035263a00de57f98Mark Andrews dns_name_fromregion(&tmpsuffix, &region);
056141f2878d1046306ef0ba035263a00de57f98Mark Andrews result = dns_name_concatenate(&tmpprefix, &tmpsuffix, prefix,
056141f2878d1046306ef0ba035263a00de57f98Mark Andrews workspace);
056141f2878d1046306ef0ba035263a00de57f98Mark Andrews if (result != DNS_R_SUCCESS)
056141f2878d1046306ef0ba035263a00de57f98Mark Andrews return (ISC_FALSE);
056141f2878d1046306ef0ba035263a00de57f98Mark Andrews *offset = *data;
056141f2878d1046306ef0ba035263a00de57f98Mark Andrews
056141f2878d1046306ef0ba035263a00de57f98Mark Andrews#ifdef MPADCL
056141f2878d1046306ef0ba035263a00de57f98Mark Andrews isc_buffer_init(&x, xxxx, sizeof xxxx,
056141f2878d1046306ef0ba035263a00de57f98Mark Andrews ISC_BUFFERTYPE_TEXT);
056141f2878d1046306ef0ba035263a00de57f98Mark Andrews dns_name_totext(prefix, ISC_FALSE, &x);
056141f2878d1046306ef0ba035263a00de57f98Mark Andrews fprintf(stdout, "prefix \"%.*s\"\n",
056141f2878d1046306ef0ba035263a00de57f98Mark Andrews (int)x.used, (char*)x.base);
056141f2878d1046306ef0ba035263a00de57f98Mark Andrews
056141f2878d1046306ef0ba035263a00de57f98Mark Andrews isc_buffer_init(&x, xxxx, sizeof xxxx,
056141f2878d1046306ef0ba035263a00de57f98Mark Andrews ISC_BUFFERTYPE_TEXT);
056141f2878d1046306ef0ba035263a00de57f98Mark Andrews dns_name_totext(suffix, ISC_FALSE, &x);
056141f2878d1046306ef0ba035263a00de57f98Mark Andrews fprintf(stdout, "suffix \"%.*s\"\n",
056141f2878d1046306ef0ba035263a00de57f98Mark Andrews (int)x.used, (char*)x.base);
056141f2878d1046306ef0ba035263a00de57f98Mark Andrews#endif
056141f2878d1046306ef0ba035263a00de57f98Mark Andrews
056141f2878d1046306ef0ba035263a00de57f98Mark Andrews return (ISC_TRUE);
6ef15459b8fd3fc8b5672da4ad72c19a755dbe45Mark Andrews}
6ef15459b8fd3fc8b5672da4ad72c19a755dbe45Mark Andrews