286N/ACopyright (C) 1999-2001 Internet Software Consortium.
286N/A $Id: compression,v 1.8 2001/01/09 21:46:40 bwelling Exp $
286N/A BIND
4.x and BIND
8.x only had one methods of compression to deal
286N/A with 14 bit compression. BIND 9 has 3 methods of compression
286N/A to deal with 14 bit, 16 bit and local compression (14 and 16 bit).
286N/A In addition to this the allowed compression methods vary across
286N/A types and across client revisions thanks to EDNS.
286N/A To be able to compress a domain name you need to some or all of
286N/A the following pieces of information.
286N/A 1. where the message starts.
286N/A 2. where the current rdata starts in the message (local compression).
286N/A 3. what the current owner name is (local compression).
286N/A 4. existing global 14 bit compression targets.
286N/A 5. existing global 16 bit compression targets.
286N/A 6. existing local compression targets.
286N/A 7. the current domain name.
286N/A 8. what are allowable compression methods, these are not constant
286N/A BIND
4.x and BIND
8.x used a table of existing 14 bit compression
286N/A The implicit assumption is that we will use compression whenever
286N/A possible and when ever there are multiple alternatives available
286N/A we will choose the one that minimises the size of the message.
286N/A We will need functions that determine the allowable compression
286N/A methods, find the "best" match among the available compression
286N/A targets, add new compression targets.
286N/A We need to be able to back out any changes made to the compression
286N/A targets if we are unable to add a complete RR (RRset?). This is
286N/A only a problem for the global compression targets.
286N/A We will maintain two RBT, one for local compression targets and
286N/A one for global compression targets. The data for these RBT will
286N/A be the offset values. The local compression RBT only needs to
286N/A be maintained when local compression is possible. The global
286N/A compression RBT is maintained regardless. Unless there is a
286N/A perfect match (or the name is ".") we will add the name to the
286N/A compression RBTs provide the offset would not be too large for
286N/A the valid compression methods of the RBT. All nodes of the RBT
286N/A will have an offset excluding the root node.
286N/A The local compression RBT will be initalised with the owner name
286N/A and the start of the rdata will be recorded.
286N/A We will use deepest partial match to find the potential
286N/A We only need to maintain one global RBT as 16 bit compression
286N/A pointers are either valid or invalid for the whole message.
286N/A dns_rdata_towire() will set the allowed methods based on the
286N/A dns_compress_init(dns_compress_t *cctx, int edns, isc_mem_t *mctx);
286N/A Initalises cctx to empty and sets whether 16 bit global
286N/A compression targets are to be added to the global RBT based on the
286N/A dns_compress_localinit(dns_compress_t *cctx, dns_name_t *owner,
286N/A Initalise a RBT for local compression, freeing and existing RBT.
286N/A dns_compress_invalidate(dns_compress_t *cctx);
286N/A Free any RBT's and make empty.
286N/A dns_compress_localinvalidate(dns_compress_t *cctx);
286N/A dns_compress_setmethods(dns_compress_t *cctx, unsigned int allowed);
286N/A dns_compress_getmethods(dns_compress_t *cctx);
286N/A dns_compress_getedns(dns_compress_t *cctx);
286N/A dns_name_towire(dns_name_t *name, dns_compress_t *cctx,
286N/A 'name' contains the current name to be added to the message 'target'.
286N/A 'target' is assumed to only contain the message.
286N/A 'cctx' contains the compression context and has to hold all the
286N/A information required that cannot be obtained from 'name' or 'target'.
286N/A unsigned int allowed; /* Allowed methods. */
286N/A unsigned int rdata; /* Start of local rdata */
286N/A isc_boolean_t global16; /* 16 bit offsets allowed */
286N/A dns_rbt_t *local; /* Local RBT */
286N/A dns_rbt_t *global; /* Global RBT */
286N/A isc_mem_t *mctx; /* Required by RBT */
286N/A sets allowed based on the value of edns.
286N/A dns_compress_findglobal(dns_compress_t *cctx, dns_name_t *name,
286N/A dns_name_t *prefix, dns_name_t *suffix,
286N/A isc_uint16_t *offset, isc_buffer_t *workspace);
286N/A dns_compress_findlocal(dns_compress_t *cctx, dns_name_t *name,
286N/A dns_name_t *prefix, dns_name_t *suffix,
286N/A isc_uint16_t *offset, isc_buffer_t *workspace);
286N/A Find the best best match in the global / local RBT. Returns prefix,
286N/A suffix and offset of the bestmatch. Findglobal(), findlocal()
286N/A requires as workspace as it may be neccessary to spit a bit stream
286N/A label. The result prefix will be such that it can be added to the
286N/A wire format followed by a compression pointer pointing to offset.
286N/A Suffix is returned so that it is possible to add the compression
286N/A pointers via dns_compress_add().
286N/A dns_compress_add(dns_compress_t *cctx, dns_name_t *prefix,
286N/A dns_name_t *suffix, isc_uint16_t offset);
286N/A Add compression pointers pointing to lebels (if any) in prefix.
286N/A The offset to the first label is passed in offset.
286N/A Requires RBT deepest match.
286N/A Requires the ability to walk the RBT and remove any node which
286N/A meets the removal condition.