DNS Message での圧縮

RFC1035 によると、以下のような形式で参照する場所をOFFSETで指定する事ができます。

    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    | 1  1|                OFFSET                   |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

例えば、既に、example.com という文字列を格納すると以下のような
感じになります。

       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    13 |           6           |           e           |
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    22 |           x           |           a           |
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    24 |           m           |           p           |
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    26 |           l           |           e           |
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    28 |           3           |           c           |
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    30 |           o           |           m           |
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    30 |           0           | 
       +--+--+--+--+--+--+--+--+

で、 www.example.com というURLを返す場合、以降は、


       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    40 |           3           |           w           |
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    42 |           w           |           w           |
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    44 | 1  1|                13                       |
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

といった感じで表現する事が出来るようになります。

Dart で書いてみる圧縮

URLを圧縮するコードを書いてみます。30行くらいのコードで記述できます。

dnsdict.dart

import 'dart:convert';
import 'dart:typed_data' show Uint8List;

class DNSCompressionDictItem {
  int index;
}

class DNSCompressionDict {
  Map<String, DNSCompressionDictItem> dict = {};
  Uint8List add(String item, int index) {
    var items = item.split('.');
    var buffer = <int>[];
    for (var i = 0; i < items.length; i++) {
      var key = items.sublist(i).join('.');
      if (dict.containsKey(key)) {
        // 既に登録されていれば、そのアドレスを返す
        var tmp = dict[key].index | 0xC000;
        buffer.addAll([(tmp >> 8) & 0xFF, tmp & 0xFF]);
        return Uint8List.fromList(buffer);
      } else {
        // 登録されていないならば、保存する
        buffer.add(items[i].length);
        buffer.addAll(ascii.encode(items[i]));
        dict[key] = DNSCompressionDictItem()..index = index;
        index += items[i].length + 1;
      }
    }
    if (buffer.isNotEmpty) {
      buffer.add(0);
    }
    // 登録されていないならば、保存する
    return Uint8List.fromList(buffer);
  }
}

dnsdict_test.dart


import 'package:info.kyorohiro.dns/dns.dart';
import 'package:test/test.dart';

void main() {
  group('DNSName', () {
    setUp(() {});

    test('DNSName.encode()', () {
      var dict = DNSCompressionDict();
      int index = 0;
      {
        var bufferSrc = dict.add('yahoo.co.jp', 0);
        index += bufferSrc.length;
        expect(DNSBuffer.fromList(bufferSrc).toHex(), '057961686f6f02636f026a7000');
      }
      // 057961686f6f02636f026a7000(13)
      // 06676f6f676c65c006(9)

      {
        var bufferSrc = dict.add('google.co.jp', index);
        index += bufferSrc.length;
        expect(DNSBuffer.fromList(bufferSrc).toHex(), '06676f6f676c65c006');
      }
      // 057961686f6f02636f026a7000(13)
      // 06676f6f676c65c006(9)

      {
        var bufferSrc = dict.add('www.google.co.jp', index);
        index += bufferSrc.length;
        expect(DNSBuffer.fromList(bufferSrc).toHex(), '03777777c00d');
      }
      // 057961686f6f02636f026a7000(13)
      // 06676f6f676c65c006(9)
      // 03777777c00d(6)

      {
        var bufferSrc = dict.add('www.google.co.jp', index);
        index += bufferSrc.length;
        expect(DNSBuffer.fromList(bufferSrc).toHex(), 'c016');
      }
    });
  });
}

Dart で書いてみる解凍

C言語などで記述する場合が、不正なメモリーをアクセスしていないか。無限ループになっていないかなどを確認する必要がありますが、Dart なので、その辺りは、省略しています。
無限ループのチェックはしたほうが良いかも知れません。

こちらも、30行くらいのコードで記述できます。

dnsname.dart

  static Tuple2<String, int> createUrlFromName(Uint8List srcBuffer, int index) {
    var outBuffer = StringBuffer();
    var i = index;
    for (; i < srcBuffer.length;) {
      var nameLength = srcBuffer[i];
      if (nameLength == 0) {
        // TEXT END
        i++;
        return Tuple2<String, int>(outBuffer.toString(), i - index);
      } else if ((0xC0 & nameLength) == 0xC0) {
        // Compression
        var v = ((nameLength & 0x3f) << 8) | srcBuffer[++i];
        var r = createUrlFromName(srcBuffer, v);
        if (outBuffer.length > 0) {
          outBuffer.write('.');
        }
        outBuffer.write(r.item1);
        i++;
        return Tuple2<String, int>(outBuffer.toString(), i - index);
      } else {
        var nameBytes = srcBuffer.sublist(i + 1, i + 1 + nameLength);
        if (outBuffer.length > 0) {
          outBuffer.write('.');
        }
        outBuffer.write(ascii.decode(nameBytes, allowInvalid: true));
        i = i + 1 + nameLength;
      }
    }
    throw DNSNameException('Not Found Null Char');
  }

次回

前回、DNSサーバーから取得したDNS Message をParseして、結果を表示します。