name.cc 24.6 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Copyright (C) 2009  Internet Systems Consortium, Inc. ("ISC")
//
// Permission to use, copy, modify, and/or distribute this software for any
// purpose with or without fee is hereby granted, provided that the above
// copyright notice and this permission notice appear in all copies.
//
// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
// AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
// PERFORMANCE OF THIS SOFTWARE.

// $Id$

17
18
#include <cctype>
#include <cassert>
JINMEI Tatuya's avatar
JINMEI Tatuya committed
19
#include <iterator>
JINMEI Tatuya's avatar
JINMEI Tatuya committed
20
#include <functional>
21
22
#include <vector>
#include <iostream>
23
24
#include <algorithm>

25
26
27
28
#include <dns/buffer.h>
#include <dns/exceptions.h>
#include <dns/name.h>
#include <dns/messagerenderer.h>
29

30
using namespace std;
31
32
33
34
35
36
37
38
39
40
41
using isc::dns::NameComparisonResult;
using isc::dns::MessageRenderer;

namespace isc {
namespace dns {

namespace {
///
/// These are shortcut arrays for efficient character conversion.
/// digitvalue converts a digit character to the corresponding integer.
/// maptolower convert uppercase alphabets to their lowercase counterparts.
42
/// We once used a helper non-local static object to avoid hardcoding the
43
44
45
46
/// array members, but we then realized it's susceptible to static
/// initialization order fiasco: Since these constants are used in a Name
/// constructor, a non-local static Name object defined in another translation
/// unit than this file may not be initialized correctly.
47
48
/// There are several ways to address this issue, but in this specific case
/// we chose the naive but simple hardcoding approach.
49
///
50
51
52
53
54
55
/// These definitions are derived from BIND 9's libdns module.
/// Note: it was not clear why the maptolower array was needed rather than
/// using the standard tolower() function.  It was perhaps due performance
/// concern, but we were not sure.  Even if it was performance reasons, we
/// should carefully assess the effect via benchmarking to avoid the pitfall of 
/// premature optimization.  We should revisit this point later.
56
static const char digitvalue[256] = {
57
58
59
60
61
62
63
64
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 16
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 32
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 48
     0,  1,  2,  3,  4,  5,  6,  7,  8,  9, -1, -1, -1, -1, -1, -1, // 64
    -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 80
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 96
    -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 112
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 128
65
66
67
68
69
70
71
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -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
static const unsigned char maptolower[] = {
76
77
78
79
80
81
82
83
    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
    0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
    0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
    0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
    0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
    0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
    0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
84
85
86
87
    0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, // ..., 'A' - 'G'
    0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, // 'H' - 'O'
    0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, // 'P' - 'W'
    0x78, 0x79, 0x7a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, // 'X' - 'Z', ...
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
    0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
    0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
    0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
    0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f,
    0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
    0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
    0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
    0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
    0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
    0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
    0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
    0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
    0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
    0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
    0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
    0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
    0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
    0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
    0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
    0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff
108
109
};
}
110

111
namespace {
112
113
114
///
/// Textual name parser states.
///
115
typedef enum {
116
117
118
119
120
121
122
123
124
125
    ft_init = 0,                // begin of the name
    ft_start,                   // begin of a label
    ft_ordinary,                // parsing an ordinary label
    ft_initialescape,           // just found '\'
    ft_escape,                  // begin of handling a '\'-escaped sequence
    ft_escdecimal,              // parsing a '\DDD' octet.

    // Unused at this moment.  We'll revisit this when we support master file
    // parser where @ is used to mean an origin name.
    ft_at                  
126
} ft_state;
127
}
128

129
Name::Name(const std::string &namestring, bool downcase) {
130
131
132
    //
    // Initialize things to make the compiler happy; they're not required.
    //
133
134
135
    unsigned int digits = 0;
    unsigned int value = 0;
    unsigned int count = 0;
136
137
138
139

    //
    // Set up the state machine.
    //
140
141
142
143
144
145
    std::string::const_iterator s = namestring.begin();
    std::string::const_iterator send = namestring.end();
    bool done = false;
    bool is_root = false;
    ft_state state = ft_init;

JINMEI Tatuya's avatar
JINMEI Tatuya committed
146
    std::vector<unsigned char> offsets;
JINMEI Tatuya's avatar
JINMEI Tatuya committed
147
    offsets.reserve(Name::MAX_LABELS);
JINMEI Tatuya's avatar
JINMEI Tatuya committed
148
149
150
151
152
    offsets.push_back(0);

    std::string ndata;
    ndata.reserve(Name::MAX_WIRE);

153
154
155
156
157
    // should we refactor this code using, e.g, the state pattern?  Probably
    // not at this point, as this is based on proved code (derived from BIND9)
    // and it's less likely that we'll have more variations in the domain name
    // syntax.  If this ever happens next time, we should consider refactor
    // the code, rather than adding more states and cases below.
JINMEI Tatuya's avatar
JINMEI Tatuya committed
158
    while (ndata.size() < Name::MAX_WIRE && s != send && !done) {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
159
        unsigned char c = *s++;
160
161
162

        switch (state) {
        case ft_init:
163
164
165
            //
            // Is this the root name?
            //
166
            if (c == '.') {
167
                if (s != send) {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
168
                    isc_throw(EmptyLabel, "non terminating empty label");
169
170
171
172
173
174
175
176
                }
                is_root = true;
            } else if (c == '@' && s == send) {
                // handle a single '@' as the root name.
                is_root = true;
            }

            if (is_root) {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
177
                ndata.push_back(0);
178
179
180
181
                done = true;
                break;
            }

182
            // FALLTHROUGH
183
        case ft_start:
JINMEI Tatuya's avatar
JINMEI Tatuya committed
184
            ndata.push_back(0); // placeholder for the label length field
185
186
187
188
189
190
            count = 0;
            if (c == '\\') {
                state = ft_initialescape;
                break;
            }
            state = ft_ordinary;
JINMEI Tatuya's avatar
JINMEI Tatuya committed
191
            assert(ndata.size() < Name::MAX_WIRE);
192
            // FALLTHROUGH
193
        case ft_ordinary:
194
            if (c == '.') {
195
                if (count == 0) {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
196
                    isc_throw(EmptyLabel, "duplicate period");
197
                }
JINMEI Tatuya's avatar
JINMEI Tatuya committed
198
199
                ndata.at(offsets.back()) = count;
                offsets.push_back(ndata.size());
200
                if (s == send) {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
201
                    ndata.push_back(0);
202
203
204
205
206
207
                    done = true;
                }
                state = ft_start;
            } else if (c == '\\') {
                state = ft_escape;
            } else {
208
                if (++count > MAX_LABELLEN) {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
209
                    isc_throw(TooLongLabel, "label is too long");
210
                }
JINMEI Tatuya's avatar
JINMEI Tatuya committed
211
                ndata.push_back(downcase ? maptolower[c] : c);
212
213
            }
            break;
214
        case ft_initialescape:
215
            if (c == '[') {
216
217
                // This looks like a bitstring label, which was deprecated.
                // Intentionally drop it.
JINMEI Tatuya's avatar
JINMEI Tatuya committed
218
                isc_throw(BadLabelType, "invalid label type");
219
220
            }
            state = ft_escape;
221
            // FALLTHROUGH
222
        case ft_escape:
223
            if (!isdigit(c & 0xff)) {
224
                if (++count > MAX_LABELLEN) {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
225
                    isc_throw(TooLongLabel, "label is too long");
226
                }
JINMEI Tatuya's avatar
JINMEI Tatuya committed
227
                ndata.push_back(downcase ? maptolower[c] : c);
228
229
230
231
232
233
                state = ft_ordinary;
                break;
            }
            digits = 0;
            value = 0;
            state = ft_escdecimal;
234
            // FALLTHROUGH
235
        case ft_escdecimal:
236
            if (!isdigit(c & 0xff)) {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
237
                isc_throw(BadEscape, "mixture of escaped digit and non-digit");
238
            }
239
            value *= 10;
240
            value += digitvalue[c];
241
242
            digits++;
            if (digits == 3) {
243
                if (value > 255) {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
244
                    isc_throw(BadEscape, "escaped decimal is too large");
245
                }
246
                if (++count > MAX_LABELLEN) {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
247
                    isc_throw(TooLongLabel, "label is too long");
248
                }
JINMEI Tatuya's avatar
JINMEI Tatuya committed
249
                ndata.push_back(downcase ? maptolower[value] : value);
250
251
252
253
                state = ft_ordinary;
            }
            break;
        default:
254
255
            // impossible case
            assert(false);
256
257
258
        }
    }

259
    if (!done) {                // no trailing '.' was found.
JINMEI Tatuya's avatar
JINMEI Tatuya committed
260
        if (ndata.size() == Name::MAX_WIRE) {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
261
            isc_throw(TooLongName, "name is too long for termination");
262
263
264
        }
        assert(s == send);
        if (state != ft_ordinary && state != ft_at) {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
265
            isc_throw(IncompleteName, "incomplete textual name");
266
        }
267
        if (state == ft_ordinary) {
268
            assert(count != 0);
JINMEI Tatuya's avatar
JINMEI Tatuya committed
269
            ndata.at(offsets.back()) = count;
270

JINMEI Tatuya's avatar
JINMEI Tatuya committed
271
            offsets.push_back(ndata.size());
272
            // add a trailing \0
JINMEI Tatuya's avatar
JINMEI Tatuya committed
273
            ndata.push_back('\0');
274
275
276
        }
    }

277
278
    labelcount_ = offsets.size();
    assert(labelcount_ > 0 && labelcount_ <= Name::MAX_LABELS);
JINMEI Tatuya's avatar
JINMEI Tatuya committed
279
    ndata_.assign(ndata.data(), ndata.size());
280
281
    length_ = ndata_.size();
    offsets_.assign(offsets.begin(), offsets.end());
282
283
}

284
285
286
287
namespace {
///
/// Wire-format name parser states.
///
288
typedef enum {
289
290
291
    fw_start = 0,               // beginning of a label
    fw_ordinary,                // inside an ordinary (non compressed) label
    fw_newcurrent               // beginning of a compression pointer
292
} fw_state;
293
}
294

295
Name::Name(InputBuffer& buffer, bool downcase) {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
296
    std::vector<unsigned char> offsets;
JINMEI Tatuya's avatar
JINMEI Tatuya committed
297
    offsets.reserve(Name::MAX_LABELS);
298
299

    /*
300
     * Initialize things to make the compiler happy; they're not required.
301
     */
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
    unsigned int n = 0;

    //
    // Set up.
    //
    bool done = false;
    unsigned int nused = 0;
    bool seen_pointer = false;
    fw_state state = fw_start;

    unsigned int cused = 0;     // Bytes of compressed name data used
    unsigned int current = buffer.getPosition();
    unsigned int pos_begin = current;
    unsigned int biggest_pointer = current;

317
318
319
320
321
    // Make the compiler happy; this is not required.
    // XXX: bad style in that we initialize it with a dummy value and define
    // it far from where it's used.  But alternatives seemed even worse.
    unsigned int new_current = 0;

322
323
324
325
326
327
328
329
330
331
332
333
334
    //
    // Note:  The following code is not optimized for speed, but
    // rather for correctness.  Speed will be addressed in the future.
    //
    while (current < buffer.getLength() && !done) {
        unsigned int c = buffer.readUint8();
        current++;
        if (!seen_pointer) {
            cused++;
        }

        switch (state) {
        case fw_start:
335
            if (c <= MAX_LABELLEN) {
336
337
                offsets.push_back(nused);
                if (nused + c + 1 > Name::MAX_WIRE) {
338
339
                    isc_throw(DNSMessageFORMERR, "wire name is too long: "
                              << nused + c + 1 << " bytes");
340
341
342
343
344
345
346
347
                }
                nused += c + 1;
                ndata_.push_back(c);
                if (c == 0) {
                    done = true;
                }
                n = c;
                state = fw_ordinary;
348
            } else if ((c & COMPRESS_POINTER_MARK8) == COMPRESS_POINTER_MARK8) {
349
350
351
                //
                // Ordinary 14-bit pointer.
                //
352
                new_current = c & ~COMPRESS_POINTER_MARK8;
353
354
355
356
357
                n = 1;
                state = fw_newcurrent;
            } else {
                // this case includes local compression pointer, which hasn't
                // been standardized.
358
                isc_throw(DNSMessageFORMERR, "unknown label character: " << c);
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
            }
            break;
        case fw_ordinary:
            if (downcase) {
                c = maptolower[c];
            }
            ndata_.push_back(c);
            if (--n == 0) {
                state = fw_start;
            }
            break;
        case fw_newcurrent:
            new_current *= 256;
            new_current += c;
            if (--n != 0) {
                break;
            }
            if (new_current >= biggest_pointer) {
377
378
379
                isc_throw(DNSMessageFORMERR,
                          "bad compression pointer (out of range): " <<
                          new_current);
380
381
382
383
384
385
386
387
388
389
390
391
392
            }
            biggest_pointer = new_current;
            current = new_current;
            buffer.setPosition(current);
            seen_pointer = true;
            state = fw_start;
            break;
        default:
            assert(false);
        }
    }

    if (!done) {
393
        isc_throw(DNSMessageFORMERR, "incomplete wire-format name");
394
395
    }

396
    labelcount_ = offsets.size();
397
398
399
400
401
402
    length_ = nused;
    offsets_.assign(offsets.begin(), offsets.end());
    buffer.setPosition(pos_begin + cused);
}

void
403
Name::toWire(OutputBuffer& buffer) const {
404
405
406
407
    buffer.writeData(ndata_.data(), ndata_.size());
}

void
408
Name::toWire(MessageRenderer& renderer) const {
409
410
411
412
    renderer.writeName(*this);
}

std::string
413
Name::toText(bool omit_final_dot) const {
414
415
416
417
    if (length_ == 1) {
        //
        // Special handling for the root label.  We ignore omit_final_dot.
        //
418
        assert(labelcount_ == 1 && ndata_[0] == '\0');
419
420
421
422
423
        return (".");
    }

    std::string::const_iterator np = ndata_.begin();
    std::string::const_iterator np_end = ndata_.end();
424
    unsigned int labels = labelcount_; // use for integrity check
JINMEI Tatuya's avatar
JINMEI Tatuya committed
425
    // init with an impossible value to catch error cases in the end:
426
    unsigned int count = MAX_LABELLEN + 1;
427
428
429
430
431
432
433

    // result string: it will roughly have the same length as the wire format
    // name data.  reserve that length to minimize reallocation.
    std::string result;
    result.reserve(length_);

    while (np != np_end) {
434
        labels--;
435
436
        count = *np++;

437
        if (count == 0) {
438
439
440
            if (!omit_final_dot) {
                result.push_back('.');
            }
441
442
            break;
        }
443
            
444
        if (count <= MAX_LABELLEN) {
445
446
447
448
449
450
451
452
453
            assert(np_end - np >= count);

            if (!result.empty()) {
                // just after a non-empty label.  add a separating dot.
                result.push_back('.');
            }

            while (count-- > 0) {
                unsigned char c = *np++;
454
                switch (c) {
455
456
457
458
459
460
461
462
463
464
465
                case 0x22: // '"'
                case 0x28: // '('
                case 0x29: // ')'
                case 0x2E: // '.'
                case 0x3B: // ';'
                case 0x5C: // '\\'
                    // Special modifiers in zone files.
                case 0x40: // '@'
                case 0x24: // '$'
                    result.push_back('\\');
                    result.push_back(c);
466
467
468
                    break;
                default:
                    if (c > 0x20 && c < 0x7f) {
469
470
                        // append printable characters intact
                        result.push_back(c);
471
                    } else {
472
473
474
475
476
                        // encode non-printable characters in the form of \DDD
                        result.push_back(0x5c);
                        result.push_back(0x30 + ((c / 100) % 10));
                        result.push_back(0x30 + ((c / 10) % 10));
                        result.push_back(0x30 + (c % 10));
477
478
479
                    }
                }
            }
480
        } else {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
481
            isc_throw(BadLabelType, "unknown label type in name data");
482
        }
483
484
    }

485
486
487
488
489
490
491
    assert(labels == 0);
    assert(count == 0);         // a valid name must end with a 'dot'.

    return (result);
}

NameComparisonResult
492
Name::compare(const Name& other) const {
493
494
495
496
497
    // Determine the relative ordering under the DNSSEC order relation of
    // 'this' and 'other', and also determine the hierarchical relationship
    // of the names.

    unsigned int nlabels = 0;
498
499
    unsigned int l1 = labelcount_;
    unsigned int l2 = other.labelcount_;
500
501
502
503
504
505
506
    int ldiff = (int)l1 - (int)l2;
    unsigned int l = (ldiff < 0) ? l1 : l2;

    while (l > 0) {
        --l;
        --l1;
        --l2;
JINMEI Tatuya's avatar
JINMEI Tatuya committed
507
508
509
510
        size_t pos1 = offsets_[l1];
        size_t pos2 = other.offsets_[l2];
        unsigned int count1 = ndata_[pos1++];
        unsigned int count2 = other.ndata_[pos2++];
511
512
513

        // We don't support any extended label types including now-obsolete
        // bitstring labels.
514
        assert(count1 <= MAX_LABELLEN && count2 <= MAX_LABELLEN);
515

JINMEI Tatuya's avatar
JINMEI Tatuya committed
516
517
        int cdiff = (int)count1 - (int)count2;
        unsigned int count = (cdiff < 0) ? count1 : count2;
518
519

        while (count > 0) {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
520
521
522
523
            unsigned char label1 = ndata_[pos1];
            unsigned char label2 = other.ndata_[pos2];

            int chdiff = (int)maptolower[label1] - (int)maptolower[label2];
524
525
526
527
528
            if (chdiff != 0) {
                return (NameComparisonResult(chdiff, nlabels,
                                         NameComparisonResult::COMMONANCESTOR));
            }
            --count;
JINMEI Tatuya's avatar
JINMEI Tatuya committed
529
530
            ++pos1;
            ++pos2;
531
532
533
534
535
536
537
        }
        if (cdiff != 0) {
                return (NameComparisonResult(cdiff, nlabels,
                                         NameComparisonResult::COMMONANCESTOR));
        }
        ++nlabels;
    }
538

539
540
541
542
543
544
545
    if (ldiff < 0) {
        return (NameComparisonResult(ldiff, nlabels,
                                     NameComparisonResult::SUPERDOMAIN));
    } else if (ldiff > 0) {
        return (NameComparisonResult(ldiff, nlabels,
                                     NameComparisonResult::SUBDOMAIN));
    }
546

547
    return (NameComparisonResult(ldiff, nlabels, NameComparisonResult::EQUAL));
548
549
550
}

bool
551
Name::equals(const Name& other) const {
552
    if (length_ != other.length_ || labelcount_ != other.labelcount_) {
553
        return (false);
554
    }
555

556
    for (unsigned int l = labelcount_, pos = 0; l > 0; --l) {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
557
558
        unsigned char count = ndata_[pos];
        if (count != other.ndata_[pos]) {
559
            return (false);
560
        }
JINMEI Tatuya's avatar
JINMEI Tatuya committed
561
        ++pos;
562

563
        while (count-- > 0) {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
564
565
566
567
            unsigned char label1 = ndata_[pos];
            unsigned char label2 = other.ndata_[pos];

            if (maptolower[label1] != maptolower[label2]) {
568
                return (false);
JINMEI Tatuya's avatar
JINMEI Tatuya committed
569
570
            }
            ++pos;
571
572
573
574
575
576
        }
    }

    return (true);
}

JINMEI Tatuya's avatar
JINMEI Tatuya committed
577
bool
578
Name::leq(const Name& other) const {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
579
580
581
582
    return (compare(other).getOrder() <= 0);
}

bool
583
Name::geq(const Name& other) const {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
584
585
586
587
    return (compare(other).getOrder() >= 0);
}

bool
588
Name::lthan(const Name& other) const {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
589
590
591
592
    return (compare(other).getOrder() < 0);
}

bool
593
Name::gthan(const Name& other) const {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
594
595
596
    return (compare(other).getOrder() > 0);
}

597
bool
598
Name::isWildcard() const {
599
600
601
    return (length_ >= 2 && ndata_[0] == 1 && ndata_[1] == '*'); 
}

JINMEI Tatuya's avatar
JINMEI Tatuya committed
602
Name
603
Name::concatenate(const Name& suffix) const {
604
605
    assert(length_ > 0 && suffix.length_ > 0);
    assert(labelcount_ > 0 && suffix.labelcount_ > 0);
JINMEI Tatuya's avatar
JINMEI Tatuya committed
606

607
    unsigned int length = length_ + suffix.length_ - 1;
JINMEI Tatuya's avatar
JINMEI Tatuya committed
608
    if (length > Name::MAX_WIRE) {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
609
        isc_throw(TooLongName, "names are too long to concatenate");
JINMEI Tatuya's avatar
JINMEI Tatuya committed
610
611
612
613
    }

    Name retname;
    retname.ndata_.reserve(length);
614
    retname.ndata_.assign(ndata_, 0, length_ - 1);
JINMEI Tatuya's avatar
JINMEI Tatuya committed
615
616
617
618
619
    retname.ndata_.insert(retname.ndata_.end(),
                          suffix.ndata_.begin(), suffix.ndata_.end());
    assert(retname.ndata_.size() == length);
    retname.length_ = length;

JINMEI Tatuya's avatar
JINMEI Tatuya committed
620
621
622
623
624
    //
    // Setup the offsets vector.  Copy the offsets of this (prefix) name,
    // excluding that for the trailing dot, and append the offsets of the
    // suffix name with the additional offset of the length of the prefix.
    //
625
    unsigned int labels = labelcount_ + suffix.labelcount_ - 1;
JINMEI Tatuya's avatar
JINMEI Tatuya committed
626
627
    assert(labels <= Name::MAX_LABELS);
    retname.offsets_.reserve(labels);
628
    retname.offsets_.assign(&offsets_[0], &offsets_[0] + labelcount_ - 1);
JINMEI Tatuya's avatar
JINMEI Tatuya committed
629
630
    transform(suffix.offsets_.begin(), suffix.offsets_.end(),
              back_inserter(retname.offsets_),
631
              bind2nd(plus<char>(), length_ - 1));
JINMEI Tatuya's avatar
JINMEI Tatuya committed
632
    assert(retname.offsets_.size() == labels);
633
    retname.labelcount_ = labels;
JINMEI Tatuya's avatar
JINMEI Tatuya committed
634
635
636
637

    return (retname);
}

638
Name
639
Name::reverse() const {
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
    Name retname;
    //
    // Set up offsets: The size of the string and number of labels will
    // be the same in as in the original.
    //
    retname.offsets_.reserve(labelcount_);
    retname.ndata_.reserve(length_);

    // Copy the original name, label by label, from tail to head.
    vector<unsigned char>::const_reverse_iterator rit0 = offsets_.rbegin();
    vector<unsigned char>::const_reverse_iterator rit1 = rit0 + 1;
    string::const_iterator n0 = ndata_.begin();
    retname.offsets_.push_back(0);
    while (rit1 != offsets_.rend()) {
        retname.ndata_.append(n0 + *rit1, n0 + *rit0);
        retname.offsets_.push_back(retname.ndata_.size());
        ++rit0;
        ++rit1;
    }
    retname.ndata_.push_back(0);

    retname.labelcount_ = labelcount_;
    retname.length_ = length_;

    return (retname);
}

JINMEI Tatuya's avatar
JINMEI Tatuya committed
667
Name
668
Name::split(const unsigned int first, const unsigned int n) const {
669
    if (n == 0 || n > labelcount_ || first > labelcount_ - n) {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
670
        isc_throw(OutOfRange, "Name::split: invalid split range");
JINMEI Tatuya's avatar
JINMEI Tatuya committed
671
672
673
    }

    Name retname;
674
675
    // If the specified range doesn't include the trailing dot, we need one
    // more label for that.
676
    unsigned int newlabels = (first + n == labelcount_) ? n : n + 1;
JINMEI Tatuya's avatar
JINMEI Tatuya committed
677

678
679
680
681
    //
    // Set up offsets: copy the corresponding range of the original offsets
    // with subtracting an offset of the prefix length.
    //
JINMEI Tatuya's avatar
JINMEI Tatuya committed
682
683
684
    retname.offsets_.reserve(newlabels);
    transform(offsets_.begin() + first, offsets_.begin() + first + newlabels,
              back_inserter(retname.offsets_),
685
              bind2nd(plus<char>(), -offsets_[first]));
JINMEI Tatuya's avatar
JINMEI Tatuya committed
686

687
688
689
690
691
692
    //
    // Set up the new name.  At this point the tail of the new offsets specifies
    // the position of the trailing dot, which should be equal to the length of
    // the extracted portion excluding the dot.  First copy that part from the
    // original name, and append the trailing dot explicitly.
    //
JINMEI Tatuya's avatar
JINMEI Tatuya committed
693
694
695
696
697
    retname.ndata_.reserve(retname.offsets_.back() + 1);
    retname.ndata_.assign(ndata_, offsets_[first], retname.offsets_.back());
    retname.ndata_.push_back(0);

    retname.length_ = retname.ndata_.size();
698
699
    retname.labelcount_ = retname.offsets_.size();
    assert(retname.labelcount_ == newlabels);
JINMEI Tatuya's avatar
JINMEI Tatuya committed
700
701
702

    return (retname);
}
JINMEI Tatuya's avatar
JINMEI Tatuya committed
703

704
705
706
707
708
709
710
711
712
713
Name
Name::split(const unsigned level) const {
    if (level >= getLabelCount()) {
        isc_throw(OutOfRange, "invalid level for name split (" << level
                  << ") for name " << *this);
    }

    return (split(level, getLabelCount() - level));
}

JINMEI Tatuya's avatar
JINMEI Tatuya committed
714
Name&
715
Name::downcase() {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
716
    unsigned int nlen = length_;
717
    unsigned int labels = labelcount_;
JINMEI Tatuya's avatar
JINMEI Tatuya committed
718
719
720
721
722
723
724
725
726
    unsigned int pos = 0;

    while (labels > 0 && nlen > 0) {
        --labels;
        --nlen;

        // we assume a valid name, and do abort() if the assumption fails
        // rather than throwing an exception.
        unsigned int count = ndata_.at(pos++);
727
        assert(count <= MAX_LABELLEN);
JINMEI Tatuya's avatar
JINMEI Tatuya committed
728
729
730
731
732
733
734
735
736
737
738
739
740
        assert(nlen >= count);

        while (count > 0) {
            ndata_.at(pos) =
                maptolower[static_cast<unsigned char>(ndata_.at(pos))];
            ++pos;
            --nlen;
            --count;
        }
    }

    return (*this);
}
JINMEI Tatuya's avatar
JINMEI Tatuya committed
741

742
std::ostream&
743
operator<<(std::ostream& os, const Name& name) {
744
    os << name.toText();
745
746
    return (os);
}
747
748
}
}