Bit Message (Electronic Station) - ビットメッセージを解読

Electronic Station最後の問題。この問題は、すっごい苦労した。

難問というより、説明文がよくわからないし、明記されていない事が多い。例題から問題文に書かれていない部分を推測するのも難しい。実際のテストで何度もFAILになるので、そのたびにエラーメッセージを見て、コードを修正するという、かなり手間のかかる問題だった。

じゃあ、つまんない問題だったかというと、そうでもなくて、少しずつ仕様が明らかになっていくあたりが、ゲームのセーブデータを解析しているようで、わりと楽しかった。

どんな問題？

Bit Message
http://www.checkio.org/mission/bit-message/

16進数の文字列で表記されたビットメッセージがある。このビットメッセージにはヘッダと本文が含まれている。ヘッダから日時情報とメッセージの長さ、そしてメッセージ本文を取得せよ。

説明文に、詳しい仕様書が付いている。それを見ながら、16進数の文字列を解析して、ヘッダ情報やメッセージを読み出すという問題。
ビットメッセージは、最大149オクテット。最初の9オクテットはヘッダで、残りが本文となる。

戻り値は、[タイムスタンプ, メッセージの長さ, メッセージ] のリストで返す。

例題：

assert(checkio('002080629173148007EDF27C1E3E9701') ==
        ['26 Aug 2002 19:37:41 GMT +2', 7, 'message']), "First Test"
assert(checkio('00317050201171820FD3323BDC0ED341C4303DEC3E8700') ==
        ['05 Jul 2013 02:11:17 GMT +7', 15, u'Selamat Datang!']), "Second Test, 7 bit"
assert(checkio('000130925161956915C8729E054A82C26D50DA0D7296EFA0EC5BBE06') ==
        ['29 Mar 2010 15:16:59 GMT -4', 21, 'Hey, I am in New York']), "Third Test, negative timezone"
assert(checkio('08071010101010611F04180441043A043B044E04470435043D043804350020043F043E04340442043204350440043604340430043504420020043F0440043004320438043B043E') ==
        ['01 Jan 1970 01:01:01 GMT +4', 31, 'Исключение подтверждает правило']), "Fourth Test, simulate 32-bit signed integer real life problem"
assert(checkio('088310913041804C23805E4E0D82E5805E4E4B002C805E4E4B4E0D82E5898B4E4B002C898B4E4B4E0D82E577E54E4B002C77E54E4B4E0D82E5884C4E4B002C5B7881F365BC884C4E4B800C6B6277E3 ') ==
        ['19 Jan 2038 03:14:08 GMT -11', 35, '聞不若聞之,聞之不若見之,見之不若知之,知之不若行之,學至於行之而止矣']), "But, we pass Y2K38 problem"

どうやって解く？

まず、オクテット(Octet)とは8ビットのこと。1バイトって言えばいいのに、って思ったけど、Wikipedia先生によると、1バイト＝8ビットとは限らないそうだ。へー。

メッセージ本文は、7bit、8bit、16bitのいずれかで、それはヘッダのTYPEを見て判断する。
8bitなら1バイトで1文字、16bitなら2バイトで1文字だけど、7bitだと1bit分ずつずれてしまう。
ちなみに、例題には、メッセージタイプが8bitのものは含まれていない。（実際のテストには8bitのものも出てくる。）

文字列から、nオクテット目を取り出す

まずは、16進数の文字列から指定場所のオクテットを読み出せるようにしよう。

1オクテットは、10進数なら0～255、16進数なら00～FF、2進数なら00000000～11111111 となる。16進数の文字列であれば、2文字で1オクテットというわけだ。
nオクテット目を読み出すには、

data[n*2:n*2+2]

とする。16進数の文字列を数字に変換するには、 int('FF', 16) とすればいいので、

def get_octet(octet):
    return int(data[octet * 2:octet * 2 + 2], 16)

これで、指定場所のオクテットを数字で取得できる。

TYPE (7bit or 8bit or 16bit)

仕様書によると、Octet 0 の Bit 2-3 にTYPEが格納されているらしい。このBitというのは後ろから数えるようだ。ややこしい。（そういうものなの？）

Bit

追記：2進数を'10111001'のような文字列として考えていたから混乱してしまった。よく考えたら Bit 0 が一番後ろなのはあたりまえか。（10進数だって一の桁が一番後ろだから）

Bit3とBit2から、メッセージタイプが 7bit、8bit、16bit のどれかがわかる。

Bit 3	Bit 2	10進数	TYPE
0	0	0	7 bit
0	1	1	8 bit
1	0	2	16 bit
1	1	3	未定義

オクテットから、Bit 2-3だけの情報を取り出すには、ビット演算を使う。

octet & 00001100

＆を使ってマスク処理することで、Bit2-3だけを有効にできる。

(octet & 00001100) >> 2

さらに右に2つずらして、Bit2-3の値を取得する。

TYPEの値を 7,8,16 の数字で取得する get_type() 関数がこちら。

def get_type(octet=0):
    value = (get_octet(octet) & int('00001100', 2)) >> 2
    return [7, 8, 16][value]  # 0: 7bit, 1: 8bit, 2: 16bit

タイムスタンプ

Octet 1 から Octet 7 まではタイムスタンプだ。ここも苦労した。まず、説明文のこれ。

contains specific swapped nibbles. for specific format identifier

英文の意味はよく分からんが、とにかくswap nibbles というのは、上位4ビットと下位4ビットの値を入れ替える、ということらしい。
で、ややこしいのが、タイムスタンプでは文字列を16進数ではなく10進数として扱う。ただし、swap nibbles だから、十の桁と一の桁を入れ替える。

つまり、
文字列が '13' なら、31
文字列が '20' なら、02
となる。

タイムスタンプのそれぞれの値を取得する get_time() 関数がこちら。

def get_time(octet):
    return int(data[octet * 2:octet * 2 + 2][::-1], 10)

これが、年、月、日、時、分、秒　と続く。

年は2桁なので、4桁に直す必要がある。結論から言えば、70未満なら2000年代、70以上なら1900年代とする。

year = get_time(1)
year += 2000 if year < 70 else 1900

タイムゾーン

さらにややこしいのがタイムゾーンだ。

In the first of the two semi-octets, the first bit represents the algebraic sign of this difference (0 : positive, 1 : negative)

最初のセミ・オクテットの最初のビットが符号、と書いてある。最初ってどっちが最初？とわからなくなるが、結論からいうと、Bit 3が符号となる。理由はわからないが、これでテストは通った。

Bit

残りのBit 2-0が十の桁、Bit 7-4が一の桁となる。
取得した数字は15分単位の値なので、* 15 / 60 で時間単位に直す。

def get_tz(octet=7):
    o = get_octet(octet)
    sign = -1 if o & int('00001000', 2) else 1
    num = (o & int('00000111', 2)) * 10 + ((o & int('11110000', 2)) >> 4)
    return sign * num * 15 // 60

メッセージの長さ

Octet 8 にはメッセージの長さが格納されている。メッセージ本文を取得するんだから、メッセージの長さなんて不要だろうと思うかもしれないが、これが後で必要になった。
単純にoctetを数字として取得すればいい。

def get_length(octet=8):
    return get_octet(octet)

メッセージ本文

メッセージ本文は、Octet 9 以降なので、

message_data = data[9 * 2:]

として取得しておく

まず、8bitなら、文字列を2文字ずつ読んでいって、chr()する。

message = ''
for i in range(0, len(message_data), 2):
    message += chr(int(message_data[i:i + 2], 16))

16bitなら、4文字ずつ読む。

message = ''
for i in range(0, len(message_data), 4):
    message += chr(int(message_data[i:i + 4], 16))

ここまでは簡単なんだが、問題は、7bit。これは、もう何が何だかわけがわからない。

例題の1問目を使って説明すると、

メッセージ本文のデータは、Octet 9 以降なので、
'EDF27C1E3E9701'
最初のOctetは'ED'
これを2進数に直すと '11101101'
右から7bitを読み取ると、'1101101'
文字に直すと 'm'
これがメッセージの1文字目

次のOctetは'F2'
これを2進数に直すと '11110010'
さっき使わなかった8bit目の'1'を右に追加すると、'111100101'
右から7bitを読み取ると、'1100101'
文字に直すと 'e'
これがメッセージの2文字目

と、続く。

これを、もう少し簡単に処理するため、以下のような手順で行った。

メッセージデータを反転する。

ED F2 7C 1E 3E 97 01
　　　↓
01 97 3E 1E 7C F2 ED

これを2進数に直す。

0000001 10010111 00111110 00011110 01111100 11110010 11101101

右から7bitずつ分割して、文字に直す。メッセージ長が7なので7文字目以後は無視する。

000000 1100101 1100111 1100001 1110011 1110011 1100101 1101101
       [  e  ] [  g  ] [  a  ] [  s  ] [  s  ] [  e  ] [  m  ]

文字を反転する。

'message'

これでメッセージ本文が得られた。

まとめ

import datetime

def checkio(data):
    def get_octet(octet):
        return int(data[octet * 2:octet * 2 + 2], 16)

    def get_type(octet=0):
        type_value = (get_octet(octet) & int('00001100', 2)) >> 2
        return [7, 8, 16][type_value]  # 0: 7bit, 1: 8bit, 2: 16bit

    def get_time(octet):
        return int(data[octet * 2:octet * 2 + 2][::-1], 10)

    def get_tz(octet=7):
        o = get_octet(octet)
        sign = -1 if o & int('00001000', 2) else 1
        num = (o & int('00000111', 2)) * 10 + ((o & int('11110000', 2)) >> 4)
        return sign * num * 15 // 60

    def get_length(octet=8):
        return get_octet(octet)

    data = data.strip()

    # timestamp
    year = get_time(1)
    year += 2000 if year < 70 else 1900
    d = datetime.datetime(year, get_time(2), get_time(3), get_time(4), get_time(5), get_time(6))
    timestamp = d.strftime('%d %b %Y %H:%M:%S') + ' GMT {0:+d}'.format(get_tz())

    # message
    bit_length = get_type()
    message = ''
    message_data = data[9 * 2:]
    if bit_length == 7:  # 7bit
        reversed_data = ''.join(a + b for a, b in zip(message_data[-2::-2], message_data[-1::-2]))
        reversed_bits = ''.join([format(int(c, 16), '04b') for c in reversed_data])
        for i in range(len(reversed_bits) - 7, -1, -7):
            message += chr(int(reversed_bits[i:i + 7], 2))
    else:
        # 8bit/16bit
        char_size = bit_length // 4
        for i in range(0, len(message_data), char_size):
            message += chr(int(message_data[i:i + char_size], 16))

    l = get_length()
    return [timestamp, l, message[:l]]

そうそう、引数のdataの末尾にスペースが付いているケースがあるので、data.strip()している。

さて、これで、Electronic Stationは完了！

次は、Incineratorに行ってみる。焼却炉って意味らしい。

summer_tree_home

Check iOでPython3をマスターするぜっ