サーバを作りながら学ぶWebSocketプロトコル

WebSocket, Python |

WebSocketって何?

WebSocketは、Javascriptでサーバとリアルタイム双方向通信をする仕組みです。概要はno titleによくまとまっています。

この記事ではWebSocketサーバを実装しながら、どういうプロトコルかを解説します。サンプルコードはWebSocket Draft 76でechoサーバーを作ってみた - いろいろな何かのものを参考にさせていただいています。ありがとうございます。

※WebSocketプロトコルは現在ドラフトの段階なので、そのうち仕様が変わる可能性があります。この記事は20111/23時点の情報です。

プロトコル概要

WebSocketで通信を行なうおおまかな流れは次のようになります。

1. クライアントとサーバの間でハンドシェイクを行ない、接続を確立する。
2. データを双方向でやりとりする。

これを順番に説明してきます。

クライアントとサーバの間でのハンドシェイク

クライアントが接続するたびに、サーバには次のようなリクエストが送信されます。

GET /demo HTTP/1.1
Host: example.com
Connection: Upgrade
Sec-WebSocket-Key2: 12998 5 Y3 1  .P00
Sec-WebSocket-Protocol: sample
Upgrade: WebSocket
Sec-WebSocket-Key1: 4 @1  46546xW%0l 1 5
Origin: http://example.com

^n:ds[4U

※ 赤字の部分はハンドシェイクに使われる情報なので、接続のたびに変化します。

このリクエストに対して、適切なレスポンスを返すことで接続が確立されます。

まず、Sec-WebSocket-Key1とSec-WebSocket-Key2は暗号化されているので復号する必要があります。復号は数字部分/スペースの個数で行なうので、例えば12998 5 Y3 1 .P00は1299853100/5=259970620です。

これをコードにすると次のようなります。

def decode(self, s):
  '''ハンドシェイク中のキーを解析する。'''
  # 数字の部分だけをとりだす
  n = filter(lambda c : c.isdigit(), s)
  # スペースだけをとりだす
  m = filter(lambda c : c == ' '   , s)
  # 数字部分 / スペースの個数
  return int(n) / len(m)

次に、復号したSec-WebSocket-Key1(32bits)、同じく復号した Sec-WebSocket-Key2(32bits) 、リクエストのボディ部(128bits) を順に並べてmd5を計算し、これをHTTPレスポンストの本体にして送り返すことでハンドシェイクを確立します。

これをコードにすると次のようになります。

part1 = self.decode(fields['sec-websocket-key1'])
part2 = self.decode(fields['sec-websocket-key2'])

# 値を32bitのビッグエンディアンのバイナリーにする
CHALLENGE = struct.pack('>I', part1)

# 値を32bitのビッグエンディアンのバイナリーにする
CHALLENGE += struct.pack('>I', part2)

CHALLENGE += key

# /chalenge/のMD5 fingerprintを/response/に入れる
RESPONSE = hashlib.md5(CHALLENGE).digest()

あとはWebSocketプロトコルにそったヘッダをつけて、クライアントに送り返します。

HTTP/1.1 101 WebSocket Protocol Handshake
Upgrade: WebSocket
Connection: Upgrade
Sec-WebSocket-Origin: http://example.com
Sec-WebSocket-Location: ws://example.com/demo
Sec-WebSocket-Protocol: sample

8jKS'y:G*Co,Wxa-

以上のことを図にまとめると次のようになります。

データ送受信

接続を確立したら、データの送受信ができます。WebSocketではデータの送受信はフレームという単位で行います。

テキストフレームは先頭に\x00、末尾に\xFFがつきます。例えば、"hoge"を送りたい場合は、"\x00hoge\xFF"になります。制御用のフレームもあるけど、こっちはなくてもとりえず動作します。

逆にフレームからテキストを取り出す場合は先頭の\x00と末尾の\xFFを除去すればいいので、次のようなコードになります。

data = self.request.recv(1024)

xs = itertools.takewhile(lambda x : ord(x) != 0xFF, data[1:])
self.RAW_DATA = "".join(list(xs))

コード

以上のことをまとめると以下のようなコードになります。

https://gist.github.com/737068

実行例

参考元の記事と同様に実行できます。

要するに

• ハンドシェイクはちょっとややこしいけど、データの送受信は簡単
• ライブラリ使ったほうが楽だよ。

ツイートする

wc、3たび

Python, 30分プログラム |

30分プログラム、その801。

何度かといてるwc(wc.py - みずぴー日記,http://d.hatena.ne.jp/mzp/20090714/wc)を、また作ってみた。

仕様がちがっとるやんorz。

使い方

$ python wc.py foo.txt
 21  75 431

ソースコード

#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-
from __future__ import with_statement
import sys
import re


def lines(s):
    return len(s.split("\n"))

def chars(s):
    return len(s)

def words(s):
    return len(re.split('\W+', s))

for path in (sys.argv[1:] if len(sys.argv[1:]) != 0 else ["/dev/stdin"]):
    with file(path, 'r') as fp:
        s = fp.read()
        print "%3d %3d %3d" % (lines(s),words(s),chars(s))

参考

• 過去の30分プログラム

ツイートする

各文字の出現回数を数える

Python, 30分プログラム |

30分プログラム、その795。anarchy golf - asunderにインスパイアされました。

入力中のアルファベットの出現回数を数えます。たぶん暗号解読に便利な頻度表の作成に便利なんじゃないですかね(適当)。

使い方

$ echo abc | python asunder.py
A:  0
B:  0
C:  0
D:  0
E:  0
F:  0
G:  0
H:  0
I:  0
J:  0
K:  0
L:  0
M:  0
N:  0
O:  0
P:  0
Q:  0
R:  0
S:  0
T:  0
U:  0
V:  0
W:  0
X:  0
Y:  0
Z:  0
a:  1
b:  1
c:  1
d:  0
e:  0
f:  0
g:  0
h:  0
i:  0
j:  0
k:  0
l:  0
m:  0
n:  0
o:  0
p:  0
q:  0
r:  0
s:  0
t:  0
u:  0
v:  0
w:  0
x:  0
y:  0
z:  0

$ cat sample.txt | python asunder.py
A: 16
B: 19
C:  6
D: 14
E: 12
F: 11
G: 10
H: 13
I:  9
J: 10
K: 12
L:  9
M: 16
N: 11
O:  4
P: 12
Q: 13
R: 15
S:  9
T: 14
U:  9
V:  7
W: 11
X: 10
Y: 15
Z: 12
a: 13
b: 13
c:  9
d: 14
e:  5
f: 20
g:  5
h: 13
i: 10
j: 14
k: 10
l: 11
m: 11
n: 14
o: 11
p: 11
q: 15
r: 14
s:  6
t: 12
u: 12
v:  9
w: 17
x:  8
y: 15
z:  9

ソースコード

#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-
import sys

d = {}
for i in sys.stdin:
    for c in i:
        if c.isalpha():
            d[c] = d.get(c,0) + 1

for k in range(ord('A'),ord('Z')+1) + range(ord('a'),ord('z')+1):
    print "%s: %2d" % (chr(k),d.get(chr(k),0))

参考

• 過去の30分プログラム
• anarchy golf - asunder

ツイートする

ハミング数のリストアップ

Python, 30分プログラム |

30分プログラム、その788。ハミング数の列挙をやってみました。

Regular number - Wikipedia, the free encyclopediaによると2^n・3^m・5^rで表せる整数のことをハミング数と呼ぶらしいです。

なんか遅延リストとfilterを組合せたクールな方法でやりたかったんですけど、うまくいきませんでした。普通に各数字を2と3と5で割れるだけ割って判定してます。

使い方

$ python hamming.py
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18]

ソースコード

#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-
from itertools import *

def take(n, seq):
    return list(islice(seq, n))

def div_by(n,m):
    (q,r) = divmod(n,m)
    if r == 0:
        return div_by(q,m)
    else:
        return n

def is_hamming(n):
    return div_by(div_by(div_by(n,2),3),5) == 1

print filter(is_hamming,range(1,20))

参考

• 過去の30分プログラム
• Regular number - Wikipedia, the free encyclopedia

ツイートする

エンディアンの変換

Python, 30分プログラム |

30分プログラム、その787。anarchy golf - Little Endian Calculatorにインスパイアされて、エンディアンの変換をやってみました。

8ビットごとに区切って順番をひっくりかえしているだけです。

使い方

>>> "%x" % flip_endian(0x3310)
'1033'

t2

ソースコード

#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-

def split(bytes, value):
    if bytes == 0:
        return []
    else:
        return split(bytes-1, value >> 8) + [ value & 0xFF ]

def join(xs):
    return reduce(lambda x,y: (x << 8) | y ,xs)

def flip_endian(n):
    return join(reversed(split(2,n)))

print "%x" % flip_endian(0x3310)

参考

• 過去の30分プログラム

ツイートする

文字列を斜めに表示する

Python, 30分プログラム |

30分プログラム、その780。anarchy golf - slope linesにインスパイアされました。

xs.reverse()は破壊的な操作なのでぐんんよりですけど、reversed(xs)は反転したイテレータを返してくれるのでいい感じです。

使い方

$ python slope-line.py  hello
    o
   l
  l
 e
h

ソースコード

#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-
import sys

def slope(s):
    n = len(s)
    return "\n".join(reversed(map(lambda x,y: (" "*y) + x, s,range(0,n))))

print slope(sys.argv[1])

参考

• 過去の30分プログラム

ツイートする

最長共通部分列(Longest Common Subsequence; LCS)を求めてみる

Python, 30分プログラム |

30分プログラム、その774。最長共通部分列(Longest Common Subsequence; LCS)を求めてみました。

LCSが何かについては 最長共通部分列問題 (Longest Common Subsequence) - naoyaのはてなダイアリーに詳しく書かれているので、そちらを参照してください。

動的計画法が有効だと聞きかじったので、ハッシュテーブルを使って一度計算した値を保存するようにしました。ホントはmemoize関数とか作るのが格好いいんだろうけどなー。

使い方

>>> lcs("ABCBDAB","BDCABA")
"BDAB"

ソースコード

#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-

def maxBy(f, x, y):
    if f(x) > f(y):
        return x
    else:
        return y

table = { ("","") : "" }

def lcs(xs,ys):
    if (xs,ys) in table:
        return table[(xs,ys)]

    ret = ""
    if xs == "" or ys == "":
        ret = ""
    elif xs[-1] == ys[-1]:
        ret = lcs(xs[:-1],ys[:-1]) + xs[-1]
    else:
        ret = maxBy(len,
                    lcs(xs[:-1],ys),
                    lcs(xs,ys[:-1]))
    table[(xs,ys)] = ret
    return ret

print lcs("ABCBDAB","BDCABA")

参考

• 過去の30分プログラム
• 最長共通部分系列長（LCS）を求めるJavaプログラム - sternhellerの日記
• 最長共通部分列問題 (Longest Common Subsequence) - naoyaのはてなダイアリー

ツイートする

述語をもとにリストを2つに分ける関数を書いてみた

Python, 30分プログラム |

30分プログラム、その767。述語をもとにリストを2つに分ける関数を書いてみた。

例えば、整数のリストxsにたいして

partition(lambda x : x % 2 == 0, xs)

とやってやると、偶数のリストと奇数のリストに分割してくれる。

使い方

print partition(lambda x : x % 2 == 0, range(0,10))
# => ([0, 2, 4, 6, 8], [1, 3, 5, 7, 9])

ソースコード

#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-

def partition1(p, xs):
    return (filter(p,xs), filter(lambda x: not p(x),xs))

def partition2(p, xs):
    ys = []
    zs = []
    for x in xs:
        if p(x):
            ys.append(x)
        else:
            zs.append(x)
    return (ys,zs)

def partition(p, xs):
    def f(accum, x):
        if p(x):
            return (accum[0] + [x], accum[1])
        else:
            return (accum[0], accum[1] + [x])
    return reduce(f,xs,([],[]))

print partition(lambda x : x % 2 == 0, range(0,10))

参考

• 過去の30分プログラム

ツイートする

素数を数える

Python, 30分プログラム |

30分プログラム、その762。

またもいいネタがないので、素数を数えました。エラトステネスのふるいを使うのも芸がないので、フェルマーテストにしました。

使い方

$ python prime.py
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

ソースコード

#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-

from random import uniform

def gcd(n, m):
    if m == 0:
        return n
    else:
        return gcd(m, n % m)

def maybePrime(n):
    a = int(uniform(2,n-1))
    if gcd(n, a) != 1:
        return False
    else:
        return a**(n-1) % n == 1

for n in xrange(2,100):
    if maybePrime(n) and maybePrime(n) and maybePrime(n):
        print n

参考

• 過去の30分プログラム
• フェルマーの小定理 - Wikipedia

ツイートする

今月が何日まであるか

Python, 30分プログラム |

30分プログラム、その754。AWK Users JP :: 今月が何日まであるかにインスパイアされて、今月が何日まであるかを表示してみます。

next_monthの計算がちょっと面倒でした。

使い方

~/c/code/croquis $ python month_rest.py
30

ソースコード

#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-

from datetime import *

def month_day(year, month):
    next_month = date(year, month % 12 + 1, 1)
    last_day   = next_month - timedelta(days=1)
    return last_day.day

if __name__ == '__main__':
    today = date.today()
    print month_day(today.year,today.month)

参考

• 過去の30分プログラム
• AWK Users JP :: 今月が何日まであるか

ツイートする