Branch data Line data Source code
1 : : // Copyright (C) 2009 Internet Systems Consortium, Inc. ("ISC")
2 : : //
3 : : // Permission to use, copy, modify, and/or distribute this software for any
4 : : // purpose with or without fee is hereby granted, provided that the above
5 : : // copyright notice and this permission notice appear in all copies.
6 : : //
7 : : // THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
8 : : // REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
9 : : // AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
10 : : // INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
11 : : // LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
12 : : // OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
13 : : // PERFORMANCE OF THIS SOFTWARE.
14 : :
15 : : #include <cctype>
16 : : #include <cassert>
17 : : #include <iterator>
18 : : #include <functional>
19 : : #include <vector>
20 : : #include <iostream>
21 : : #include <algorithm>
22 : :
23 : : #include <util/buffer.h>
24 : : #include <dns/exceptions.h>
25 : : #include <dns/name.h>
26 : : #include <dns/name_internal.h>
27 : : #include <dns/messagerenderer.h>
28 : :
29 : : using namespace std;
30 : : using namespace isc::util;
31 : : using isc::dns::NameComparisonResult;
32 : : using namespace isc::dns::name::internal;
33 : :
34 : : namespace isc {
35 : : namespace dns {
36 : :
37 : : namespace {
38 : : ///
39 : : /// These are shortcut arrays for efficient character conversion.
40 : : /// digitvalue converts a digit character to the corresponding integer.
41 : : /// maptolower convert uppercase alphabets to their lowercase counterparts.
42 : : /// We once used a helper non-local static object to avoid hardcoding the
43 : : /// array members, but we then realized it's susceptible to static
44 : : /// initialization order fiasco: Since these constants are used in a Name
45 : : /// constructor, a non-local static Name object defined in another translation
46 : : /// unit than this file may not be initialized correctly.
47 : : /// There are several ways to address this issue, but in this specific case
48 : : /// we chose the naive but simple hardcoding approach.
49 : : ///
50 : : /// These definitions are derived from BIND 9's libdns module.
51 : : /// Note: we could use the standard tolower() function instead of the
52 : : /// maptolower array, but a benchmark indicated that the private array could
53 : : /// improve the performance of message rendering (which internally uses the
54 : : /// array heavily) about 27%. Since we want to achieve very good performance
55 : : /// for message rendering in some cases, we'll keep using it.
56 : : const char digitvalue[256] = {
57 : : -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 16
58 : : -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 32
59 : : -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 48
60 : : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1, // 64
61 : : -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 80
62 : : -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 96
63 : : -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 112
64 : : -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 128
65 : : -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
66 : : -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
67 : : -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
68 : : -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
69 : : -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
70 : : -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
71 : : -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
72 : : -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 256
73 : : };
74 : : }
75 : :
76 : : namespace name {
77 : : namespace internal {
78 : : const unsigned char maptolower[] = {
79 : : 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
80 : : 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
81 : : 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
82 : : 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
83 : : 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
84 : : 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
85 : : 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
86 : : 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
87 : : 0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, // ..., 'A' - 'G'
88 : : 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, // 'H' - 'O'
89 : : 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, // 'P' - 'W'
90 : : 0x78, 0x79, 0x7a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, // 'X' - 'Z', ...
91 : : 0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
92 : : 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
93 : : 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
94 : : 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f,
95 : : 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
96 : : 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
97 : : 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
98 : : 0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
99 : : 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
100 : : 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
101 : : 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
102 : : 0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
103 : : 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
104 : : 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
105 : : 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
106 : : 0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
107 : : 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
108 : : 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
109 : : 0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
110 : : 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff
111 : : };
112 : : } // end of internal
113 : : } // end of name
114 : :
115 : : namespace {
116 : : ///
117 : : /// Textual name parser states.
118 : : ///
119 : : typedef enum {
120 : : ft_init = 0, // begin of the name
121 : : ft_start, // begin of a label
122 : : ft_ordinary, // parsing an ordinary label
123 : : ft_initialescape, // just found '\'
124 : : ft_escape, // begin of handling a '\'-escaped sequence
125 : : ft_escdecimal, // parsing a '\DDD' octet.
126 : :
127 : : // Unused at this moment. We'll revisit this when we support master file
128 : : // parser where @ is used to mean an origin name.
129 : : ft_at
130 : : } ft_state;
131 : : }
132 : :
133 : 49 : Name::Name(const std::string &namestring, bool downcase) {
134 : : //
135 : : // Initialize things to make the compiler happy; they're not required.
136 : : //
137 : 290959 : unsigned int digits = 0;
138 : 290959 : unsigned int value = 0;
139 : 290959 : unsigned int count = 0;
140 : :
141 : : //
142 : : // Set up the state machine.
143 : : //
144 : 290959 : std::string::const_iterator s = namestring.begin();
145 : 290959 : std::string::const_iterator send = namestring.end();
146 : 290959 : bool done = false;
147 : 290959 : bool is_root = false;
148 : 290959 : ft_state state = ft_init;
149 : :
150 : : std::vector<unsigned char> offsets;
151 [ + - ]: 290959 : offsets.reserve(Name::MAX_LABELS);
152 [ + - ]: 290959 : offsets.push_back(0);
153 : :
154 : 290959 : std::string ndata;
155 [ + - ]: 290959 : ndata.reserve(Name::MAX_WIRE);
156 : :
157 : : // should we refactor this code using, e.g, the state pattern? Probably
158 : : // not at this point, as this is based on proved code (derived from BIND9)
159 : : // and it's less likely that we'll have more variations in the domain name
160 : : // syntax. If this ever happens next time, we should consider refactor
161 : : // the code, rather than adding more states and cases below.
162 [ + + ][ + + ]: 6130265 : while (ndata.size() < Name::MAX_WIRE && s != send && !done) {
[ - + ][ + + ]
163 : 5839347 : unsigned char c = *s++;
164 : :
165 [ + + + + : 5839347 : switch (state) {
+ + - ]
166 : : case ft_init:
167 : : //
168 : : // Is this the root name?
169 : : //
170 [ + + ]: 290957 : if (c == '.') {
171 [ + + ]: 7270 : if (s != send) {
172 [ + - ][ + - ]: 8 : isc_throw(EmptyLabel,
[ + - ]
173 : : "non terminating empty label in " << namestring);
174 : : }
175 : : is_root = true;
176 [ + + ][ - + ]: 283687 : } else if (c == '@' && s == send) {
[ + + ]
177 : : // handle a single '@' as the root name.
178 : 1 : is_root = true;
179 : : }
180 : :
181 [ + + ]: 290953 : if (is_root) {
182 [ + - ]: 7267 : ndata.push_back(0);
183 : : done = true;
184 : : break;
185 : : }
186 : :
187 : : // FALLTHROUGH
188 : : case ft_start:
189 [ + - ]: 905596 : ndata.push_back(0); // placeholder for the label length field
190 : 905596 : count = 0;
191 [ + + ]: 905596 : if (c == '\\') {
192 : : state = ft_initialescape;
193 : : break;
194 : : }
195 : 905573 : state = ft_ordinary;
196 [ - + ]: 905573 : assert(ndata.size() < Name::MAX_WIRE);
197 : : // FALLTHROUGH
198 : : case ft_ordinary:
199 [ + + ]: 5830621 : if (c == '.') {
200 [ + + ]: 890273 : if (count == 0) {
201 [ + - ][ + - ]: 32 : isc_throw(EmptyLabel,
[ + - ]
202 : : "duplicate period in " << namestring);
203 : : }
204 [ + - ]: 890257 : ndata.at(offsets.back()) = count;
205 [ + - ]: 890257 : offsets.push_back(ndata.size());
206 [ + + ]: 890257 : if (s == send) {
207 [ + - ]: 268347 : ndata.push_back(0);
208 : : done = true;
209 : : }
210 : : state = ft_start;
211 [ + + ]: 4940348 : } else if (c == '\\') {
212 : : state = ft_escape;
213 : : } else {
214 [ + + ]: 4939884 : if (++count > MAX_LABELLEN) {
215 [ + - ][ + - ]: 18 : isc_throw(TooLongLabel,
[ + - ]
216 : : "label is too long in " << namestring);
217 : : }
218 [ + + ][ + - ]: 4939875 : ndata.push_back(downcase ? maptolower[c] : c);
219 : : }
220 : : break;
221 : : case ft_initialescape:
222 [ + + ]: 22 : if (c == '[') {
223 : : // This looks like a bitstring label, which was deprecated.
224 : : // Intentionally drop it.
225 [ + - ][ + - ]: 6 : isc_throw(BadLabelType,
[ + - ]
226 : : "invalid label type in " << namestring);
227 : : }
228 : : state = ft_escape;
229 : : // FALLTHROUGH
230 : : case ft_escape:
231 [ + + ]: 483 : if (!isdigit(c & 0xff)) {
232 [ + + ]: 9 : if (++count > MAX_LABELLEN) {
233 [ + - ][ + - ]: 4 : isc_throw(TooLongLabel,
[ + - ]
234 : : "label is too long in " << namestring);
235 : : }
236 [ - + ][ + - ]: 7 : ndata.push_back(downcase ? maptolower[c] : c);
237 : : state = ft_ordinary;
238 : : break;
239 : : }
240 : : digits = 0;
241 : : value = 0;
242 : : state = ft_escdecimal;
243 : : // FALLTHROUGH
244 : : case ft_escdecimal:
245 [ + + ]: 1420 : if (!isdigit(c & 0xff)) {
246 [ + - ][ + - ]: 4 : isc_throw(BadEscape,
[ + - ]
247 : : "mixture of escaped digit and non-digit in "
248 : : << namestring);
249 : : }
250 : 1418 : value *= 10;
251 : 1418 : value += digitvalue[c];
252 : 1418 : digits++;
253 [ + + ]: 1418 : if (digits == 3) {
254 [ + + ]: 470 : if (value > 255) {
255 [ + - ][ + - ]: 6 : isc_throw(BadEscape,
[ + - ]
256 : : "escaped decimal is too large in "
257 : : << namestring);
258 : : }
259 [ + + ]: 467 : if (++count > MAX_LABELLEN) {
260 [ + - ][ + - ]: 4 : isc_throw(TooLongLabel,
[ + - ]
261 : : "label is too long in " << namestring);
262 : : }
263 [ + + ][ + - ]: 465 : ndata.push_back(downcase ? maptolower[value] : value);
264 : : state = ft_ordinary;
265 : : }
266 : : break;
267 : : default:
268 : : // impossible case
269 : 5839306 : assert(false);
270 : : }
271 : : }
272 : :
273 [ + + ]: 290918 : if (!done) { // no trailing '.' was found.
274 [ + + ]: 15304 : if (ndata.size() == Name::MAX_WIRE) {
275 [ + - ][ + - ]: 6 : isc_throw(TooLongName,
[ + - ]
276 : : "name is too long for termination in " << namestring);
277 : : }
278 [ - + ]: 15301 : assert(s == send);
279 [ + + ]: 15301 : if (state != ft_ordinary && state != ft_at) {
280 [ + - ][ + + ]: 10 : isc_throw(IncompleteName,
[ + - ][ + - ]
[ + - ][ + - ]
281 : : "incomplete textual name in " <<
282 : : (namestring.empty() ? "<empty>" : namestring));
283 : : }
284 [ + - ]: 15296 : if (state == ft_ordinary) {
285 [ - + ]: 15296 : assert(count != 0);
286 [ + - ]: 15296 : ndata.at(offsets.back()) = count;
287 : :
288 [ + - ]: 15296 : offsets.push_back(ndata.size());
289 : : // add a trailing \0
290 [ + - ]: 15296 : ndata.push_back('\0');
291 : : }
292 : : }
293 : :
294 : 581820 : labelcount_ = offsets.size();
295 [ - + ]: 290910 : assert(labelcount_ > 0 && labelcount_ <= Name::MAX_LABELS);
296 [ + - ]: 290910 : ndata_.assign(ndata.data(), ndata.size());
297 : 581820 : length_ = ndata_.size();
298 : 290910 : offsets_.assign(offsets.begin(), offsets.end());
299 : 290910 : }
300 : :
301 : : namespace {
302 : : ///
303 : : /// Wire-format name parser states.
304 : : ///
305 : : typedef enum {
306 : : fw_start = 0, // beginning of a label
307 : : fw_ordinary, // inside an ordinary (non compressed) label
308 : : fw_newcurrent // beginning of a compression pointer
309 : : } fw_state;
310 : : }
311 : :
312 : 25 : Name::Name(InputBuffer& buffer, bool downcase) {
313 : : std::vector<unsigned char> offsets;
314 [ + - ]: 3607 : offsets.reserve(Name::MAX_LABELS);
315 : :
316 : : /*
317 : : * Initialize things to make the compiler happy; they're not required.
318 : : */
319 : 3607 : unsigned int n = 0;
320 : :
321 : : //
322 : : // Set up.
323 : : //
324 : 3607 : bool done = false;
325 : 3607 : unsigned int nused = 0;
326 : 3607 : bool seen_pointer = false;
327 : 3607 : fw_state state = fw_start;
328 : :
329 : 3607 : unsigned int cused = 0; // Bytes of compressed name data used
330 : 3607 : unsigned int current = buffer.getPosition();
331 : 3607 : unsigned int pos_begin = current;
332 : 3607 : unsigned int biggest_pointer = current;
333 : :
334 : : // Make the compiler happy; this is not required.
335 : : // XXX: bad style in that we initialize it with a dummy value and define
336 : : // it far from where it's used. But alternatives seemed even worse.
337 : 3607 : unsigned int new_current = 0;
338 : :
339 : : //
340 : : // Note: The following code is not optimized for speed, but
341 : : // rather for correctness. Speed will be addressed in the future.
342 : : //
343 [ + + ][ + + ]: 63748 : while (current < buffer.getLength() && !done) {
[ + + ]
344 : 60158 : unsigned int c = buffer.readUint8();
345 : 60158 : current++;
346 [ + + ]: 60158 : if (!seen_pointer) {
347 : 32013 : cused++;
348 : : }
349 : :
350 [ + + + - ]: 60158 : switch (state) {
351 : : case fw_start:
352 [ + + ]: 15226 : if (c <= MAX_LABELLEN) {
353 [ + - ]: 12585 : offsets.push_back(nused);
354 [ + + ]: 12585 : if (nused + c + 1 > Name::MAX_WIRE) {
355 [ + - ][ + - ]: 9 : isc_throw(DNSMessageFORMERR, "wire name is too long: "
[ + - ]
356 : : << nused + c + 1 << " bytes");
357 : : }
358 : 12582 : nused += c + 1;
359 [ + - ]: 12582 : ndata_.push_back(c);
360 [ + + ]: 12582 : if (c == 0) {
361 : 3582 : done = true;
362 : : }
363 : 12582 : n = c;
364 : 12582 : state = fw_ordinary;
365 [ + + ]: 2641 : } else if ((c & COMPRESS_POINTER_MARK8) == COMPRESS_POINTER_MARK8) {
366 : : //
367 : : // Ordinary 14-bit pointer.
368 : : //
369 : 2632 : new_current = c & ~COMPRESS_POINTER_MARK8;
370 : 2632 : n = 1;
371 : 2632 : state = fw_newcurrent;
372 : : } else {
373 : : // this case includes local compression pointer, which hasn't
374 : : // been standardized.
375 [ + - ][ + - ]: 27 : isc_throw(DNSMessageFORMERR, "unknown label character: " << c);
376 : : }
377 : : break;
378 : : case fw_ordinary:
379 [ + + ]: 42301 : if (downcase) {
380 : 6 : c = maptolower[c];
381 : : }
382 [ + - ]: 42301 : ndata_.push_back(c);
383 [ + + ]: 42301 : if (--n == 0) {
384 : 9000 : state = fw_start;
385 : : }
386 : : break;
387 : : case fw_newcurrent:
388 : 2631 : new_current *= 256;
389 : 2631 : new_current += c;
390 [ + - ]: 2631 : if (--n != 0) {
391 : : break;
392 : : }
393 [ + + ]: 2631 : if (new_current >= biggest_pointer) {
394 [ + - ][ + - ]: 15 : isc_throw(DNSMessageFORMERR,
395 : : "bad compression pointer (out of range): " <<
396 : : new_current);
397 : : }
398 : 2626 : biggest_pointer = new_current;
399 : 2626 : current = new_current;
400 : 2626 : buffer.setPosition(current);
401 : 2626 : seen_pointer = true;
402 : 2626 : state = fw_start;
403 : 2626 : break;
404 : : default:
405 : 60141 : assert(false);
406 : : }
407 : : }
408 : :
409 [ + + ]: 3590 : if (!done) {
410 [ + - ][ + - ]: 16 : isc_throw(DNSMessageFORMERR, "incomplete wire-format name");
411 : : }
412 : :
413 : 7164 : labelcount_ = offsets.size();
414 : 3582 : length_ = nused;
415 : 3582 : offsets_.assign(offsets.begin(), offsets.end());
416 : 3582 : buffer.setPosition(pos_begin + cused);
417 : 3582 : }
418 : :
419 : : void
420 : 572 : Name::toWire(OutputBuffer& buffer) const {
421 : 1716 : buffer.writeData(ndata_.data(), ndata_.size());
422 : 572 : }
423 : :
424 : : void
425 : 652 : Name::toWire(AbstractMessageRenderer& renderer) const {
426 : 652 : renderer.writeName(*this);
427 : 652 : }
428 : :
429 : : std::string
430 : 41821 : Name::toText(bool omit_final_dot) const {
431 [ + + ]: 41821 : if (length_ == 1) {
432 : : //
433 : : // Special handling for the root label. We ignore omit_final_dot.
434 : : //
435 [ + - ][ - + ]: 673 : assert(labelcount_ == 1 && ndata_[0] == '\0');
436 : 673 : return (".");
437 : : }
438 : :
439 : 82296 : std::string::const_iterator np = ndata_.begin();
440 : 82296 : std::string::const_iterator np_end = ndata_.end();
441 : 41148 : unsigned int labels = labelcount_; // use for integrity check
442 : : // init with an impossible value to catch error cases in the end:
443 : 41148 : unsigned int count = MAX_LABELLEN + 1;
444 : :
445 : : // result string: it will roughly have the same length as the wire format
446 : : // name data. reserve that length to minimize reallocation.
447 : 41821 : std::string result;
448 [ + - ]: 41148 : result.reserve(length_);
449 : :
450 [ + - ]: 155333 : while (np != np_end) {
451 : 155333 : labels--;
452 : 155333 : count = *np++;
453 : :
454 [ + + ]: 155333 : if (count == 0) {
455 [ + + ]: 41148 : if (!omit_final_dot) {
456 [ + - ]: 40573 : result.push_back('.');
457 : : }
458 : : break;
459 : : }
460 : :
461 [ + - ]: 114185 : if (count <= MAX_LABELLEN) {
462 [ - + ]: 114185 : assert(np_end - np >= count);
463 : :
464 [ + + ]: 187222 : if (!result.empty()) {
465 : : // just after a non-empty label. add a separating dot.
466 [ + - ]: 73037 : result.push_back('.');
467 : : }
468 : :
469 [ + + ]: 697811 : while (count-- > 0) {
470 : 583626 : unsigned char c = *np++;
471 [ + + ]: 583626 : switch (c) {
472 : : case 0x22: // '"'
473 : : case 0x28: // '('
474 : : case 0x29: // ')'
475 : : case 0x2E: // '.'
476 : : case 0x3B: // ';'
477 : : case 0x5C: // '\\'
478 : : // Special modifiers in zone files.
479 : : case 0x40: // '@'
480 : : case 0x24: // '$'
481 [ + - ]: 38 : result.push_back('\\');
482 [ + - ]: 38 : result.push_back(c);
483 : : break;
484 : : default:
485 [ + + ]: 583588 : if (c > 0x20 && c < 0x7f) {
486 : : // append printable characters intact
487 [ + - ]: 583425 : result.push_back(c);
488 : : } else {
489 : : // encode non-printable characters in the form of \DDD
490 [ + - ]: 163 : result.push_back(0x5c);
491 [ + - ]: 163 : result.push_back(0x30 + ((c / 100) % 10));
492 [ + - ]: 163 : result.push_back(0x30 + ((c / 10) % 10));
493 [ + - ]: 583626 : result.push_back(0x30 + (c % 10));
494 : : }
495 : : }
496 : : }
497 : : } else {
498 [ # # ][ # # ]: 41148 : isc_throw(BadLabelType, "unknown label type in name data");
499 : : }
500 : : }
501 : :
502 [ - + ]: 41148 : assert(labels == 0);
503 [ - + ]: 41148 : assert(count == 0); // a valid name must end with a 'dot'.
504 : :
505 [ + - ]: 41148 : return (result);
506 : : }
507 : :
508 : : NameComparisonResult
509 : 204233 : Name::compare(const Name& other) const {
510 : : // Determine the relative ordering under the DNSSEC order relation of
511 : : // 'this' and 'other', and also determine the hierarchical relationship
512 : : // of the names.
513 : :
514 : 204233 : unsigned int nlabels = 0;
515 : 204233 : unsigned int l1 = labelcount_;
516 : 204233 : unsigned int l2 = other.labelcount_;
517 : 204233 : int ldiff = (int)l1 - (int)l2;
518 [ + + ]: 204233 : unsigned int l = (ldiff < 0) ? l1 : l2;
519 : :
520 [ + + ]: 786367 : while (l > 0) {
521 : 727953 : --l;
522 : 727953 : --l1;
523 : 727953 : --l2;
524 : 1455906 : size_t pos1 = offsets_[l1];
525 : 1455906 : size_t pos2 = other.offsets_[l2];
526 : 1455906 : unsigned int count1 = ndata_[pos1++];
527 : 1455906 : unsigned int count2 = other.ndata_[pos2++];
528 : :
529 : : // We don't support any extended label types including now-obsolete
530 : : // bitstring labels.
531 [ - + ]: 727953 : assert(count1 <= MAX_LABELLEN && count2 <= MAX_LABELLEN);
532 : :
533 : 727953 : int cdiff = (int)count1 - (int)count2;
534 [ + + ]: 727953 : unsigned int count = (cdiff < 0) ? count1 : count2;
535 : :
536 [ + + ]: 2732383 : while (count > 0) {
537 : 4285854 : unsigned char label1 = ndata_[pos1];
538 : 4285854 : unsigned char label2 = other.ndata_[pos2];
539 : :
540 : 2142927 : int chdiff = (int)maptolower[label1] - (int)maptolower[label2];
541 [ + + ]: 2142927 : if (chdiff != 0) {
542 : : return (NameComparisonResult(chdiff, nlabels,
543 : 138497 : NameComparisonResult::COMMONANCESTOR));
544 : : }
545 : 2004430 : --count;
546 : 2004430 : ++pos1;
547 : 2004430 : ++pos2;
548 : : }
549 [ + + ]: 589456 : if (cdiff != 0) {
550 : : return (NameComparisonResult(cdiff, nlabels,
551 : 7322 : NameComparisonResult::COMMONANCESTOR));
552 : : }
553 : 582134 : ++nlabels;
554 : : }
555 : :
556 [ + + ]: 58414 : if (ldiff < 0) {
557 : : return (NameComparisonResult(ldiff, nlabels,
558 : 8473 : NameComparisonResult::SUPERDOMAIN));
559 [ + + ]: 49941 : } else if (ldiff > 0) {
560 : : return (NameComparisonResult(ldiff, nlabels,
561 : 39050 : NameComparisonResult::SUBDOMAIN));
562 : : }
563 : :
564 : 204233 : return (NameComparisonResult(ldiff, nlabels, NameComparisonResult::EQUAL));
565 : : }
566 : :
567 : : bool
568 : 24978 : Name::equals(const Name& other) const {
569 [ + + ]: 24978 : if (length_ != other.length_ || labelcount_ != other.labelcount_) {
570 : : return (false);
571 : : }
572 : :
573 [ + + ]: 55368 : for (unsigned int l = labelcount_, pos = 0; l > 0; --l) {
574 : 60780 : unsigned char count = ndata_[pos];
575 [ + - ]: 30390 : if (count != other.ndata_[pos]) {
576 : : return (false);
577 : : }
578 : 30390 : ++pos;
579 : :
580 [ + + ]: 137477 : while (count-- > 0) {
581 : 216976 : unsigned char label1 = ndata_[pos];
582 : 216976 : unsigned char label2 = other.ndata_[pos];
583 : :
584 [ + + ]: 108488 : if (maptolower[label1] != maptolower[label2]) {
585 : : return (false);
586 : : }
587 : 107087 : ++pos;
588 : : }
589 : : }
590 : :
591 : : return (true);
592 : : }
593 : :
594 : : bool
595 : 9 : Name::leq(const Name& other) const {
596 : 9 : return (compare(other).getOrder() <= 0);
597 : : }
598 : :
599 : : bool
600 : 9 : Name::geq(const Name& other) const {
601 : 9 : return (compare(other).getOrder() >= 0);
602 : : }
603 : :
604 : : bool
605 : 44381 : Name::lthan(const Name& other) const {
606 : 44381 : return (compare(other).getOrder() < 0);
607 : : }
608 : :
609 : : bool
610 : 11 : Name::gthan(const Name& other) const {
611 : 11 : return (compare(other).getOrder() > 0);
612 : : }
613 : :
614 : : bool
615 : 3253 : Name::isWildcard() const {
616 [ + + ][ + + ]: 3253 : return (length_ >= 2 && ndata_[0] == 1 && ndata_[1] == '*');
[ + + ]
617 : : }
618 : :
619 : : Name
620 : 425 : Name::concatenate(const Name& suffix) const {
621 [ + - ][ - + ]: 425 : assert(length_ > 0 && suffix.length_ > 0);
622 [ + - ][ - + ]: 425 : assert(labelcount_ > 0 && suffix.labelcount_ > 0);
623 : :
624 : 425 : unsigned int length = length_ + suffix.length_ - 1;
625 [ + + ]: 425 : if (length > Name::MAX_WIRE) {
626 [ + - ]: 6 : isc_throw(TooLongName, "names are too long to concatenate");
627 : : }
628 : :
629 : 0 : Name retname;
630 [ + - ]: 422 : retname.ndata_.reserve(length);
631 [ + - ]: 422 : retname.ndata_.assign(ndata_, 0, length_ - 1);
632 : 422 : retname.ndata_.insert(retname.ndata_.end(),
633 [ + - ]: 422 : suffix.ndata_.begin(), suffix.ndata_.end());
634 [ - + ]: 422 : assert(retname.ndata_.size() == length);
635 : 422 : retname.length_ = length;
636 : :
637 : : //
638 : : // Setup the offsets vector. Copy the offsets of this (prefix) name,
639 : : // excluding that for the trailing dot, and append the offsets of the
640 : : // suffix name with the additional offset of the length of the prefix.
641 : : //
642 : 422 : unsigned int labels = labelcount_ + suffix.labelcount_ - 1;
643 [ - + ]: 422 : assert(labels <= Name::MAX_LABELS);
644 [ + - ]: 422 : retname.offsets_.reserve(labels);
645 : 844 : retname.offsets_.assign(&offsets_[0], &offsets_[0] + labelcount_ - 1);
646 : : transform(suffix.offsets_.begin(), suffix.offsets_.end(),
647 : 422 : back_inserter(retname.offsets_),
648 : 422 : bind2nd(plus<char>(), length_ - 1));
649 [ - + ]: 422 : assert(retname.offsets_.size() == labels);
650 : 422 : retname.labelcount_ = labels;
651 : :
652 : 422 : return (retname);
653 : : }
654 : :
655 : : Name
656 : 7127 : Name::reverse() const {
657 : 0 : Name retname;
658 : : //
659 : : // Set up offsets: The size of the string and number of labels will
660 : : // be the same in as in the original.
661 : : //
662 [ + - ]: 7127 : retname.offsets_.reserve(labelcount_);
663 [ + - ]: 7127 : retname.ndata_.reserve(length_);
664 : :
665 : : // Copy the original name, label by label, from tail to head.
666 : 7127 : vector<unsigned char>::const_reverse_iterator rit0 = offsets_.rbegin();
667 : : vector<unsigned char>::const_reverse_iterator rit1 = rit0 + 1;
668 : 14254 : string::const_iterator n0 = ndata_.begin();
669 [ + - ]: 7127 : retname.offsets_.push_back(0);
670 [ + + ]: 29262 : while (rit1 != offsets_.rend()) {
671 : 66405 : retname.ndata_.append(n0 + *rit1, n0 + *rit0);
672 [ + - ]: 22135 : retname.offsets_.push_back(retname.ndata_.size());
673 : : ++rit0;
674 : : ++rit1;
675 : : }
676 [ + - ]: 7127 : retname.ndata_.push_back(0);
677 : :
678 : 7127 : retname.labelcount_ = labelcount_;
679 : 7127 : retname.length_ = length_;
680 : :
681 : 7127 : return (retname);
682 : : }
683 : :
684 : : Name
685 : 24522 : Name::split(const unsigned int first, const unsigned int n) const {
686 [ + + ][ + + ]: 24522 : if (n == 0 || n > labelcount_ || first > labelcount_ - n) {
[ + + ]
687 [ + - ]: 12 : isc_throw(OutOfRange, "Name::split: invalid split range");
688 : : }
689 : :
690 : 0 : Name retname;
691 : : // If the specified range doesn't include the trailing dot, we need one
692 : : // more label for that.
693 [ + + ]: 24516 : unsigned int newlabels = (first + n == labelcount_) ? n : n + 1;
694 : :
695 : : //
696 : : // Set up offsets: copy the corresponding range of the original offsets
697 : : // with subtracting an offset of the prefix length.
698 : : //
699 [ + - ]: 24516 : retname.offsets_.reserve(newlabels);
700 : 49032 : transform(offsets_.begin() + first, offsets_.begin() + first + newlabels,
701 : 24516 : back_inserter(retname.offsets_),
702 : 49032 : bind2nd(plus<char>(), -offsets_[first]));
703 : :
704 : : //
705 : : // Set up the new name. At this point the tail of the new offsets specifies
706 : : // the position of the trailing dot, which should be equal to the length of
707 : : // the extracted portion excluding the dot. First copy that part from the
708 : : // original name, and append the trailing dot explicitly.
709 : : //
710 [ + - ]: 24516 : retname.ndata_.reserve(retname.offsets_.back() + 1);
711 : 49032 : retname.ndata_.assign(ndata_, offsets_[first], retname.offsets_.back());
712 [ + - ]: 24516 : retname.ndata_.push_back(0);
713 : :
714 : 49032 : retname.length_ = retname.ndata_.size();
715 : 24516 : retname.labelcount_ = retname.offsets_.size();
716 [ - + ]: 24516 : assert(retname.labelcount_ == newlabels);
717 : :
718 : 24516 : return (retname);
719 : : }
720 : :
721 : : Name
722 : 3986 : Name::split(const unsigned int level) const {
723 [ + + ]: 3986 : if (level >= getLabelCount()) {
724 [ + - ][ + - ]: 9 : isc_throw(OutOfRange, "invalid level for name split (" << level
[ + - ]
725 : : << ") for name " << *this);
726 : : }
727 : :
728 : 3983 : return (split(level, getLabelCount() - level));
729 : : }
730 : :
731 : : Name&
732 : 612 : Name::downcase() {
733 : 612 : unsigned int nlen = length_;
734 : 612 : unsigned int labels = labelcount_;
735 : 612 : unsigned int pos = 0;
736 : :
737 [ + + ]: 2967 : while (labels > 0 && nlen > 0) {
738 : 2355 : --labels;
739 : 2355 : --nlen;
740 : :
741 : : // we assume a valid name, and do abort() if the assumption fails
742 : : // rather than throwing an exception.
743 : 2355 : unsigned int count = ndata_.at(pos++);
744 [ - + ]: 2355 : assert(count <= MAX_LABELLEN);
745 [ + - ]: 2355 : assert(nlen >= count);
746 : :
747 [ + + ]: 11471 : while (count > 0) {
748 : 9116 : ndata_.at(pos) =
749 : 9116 : maptolower[static_cast<unsigned char>(ndata_.at(pos))];
750 : 9116 : ++pos;
751 : 9116 : --nlen;
752 : 9116 : --count;
753 : : }
754 : : }
755 : :
756 : 612 : return (*this);
757 : : }
758 : :
759 : : std::ostream&
760 : 12436 : operator<<(std::ostream& os, const Name& name) {
761 [ + - ]: 12436 : os << name.toText();
762 : 12436 : return (os);
763 : : }
764 : : }
765 : 25075 : }
|
