自然順ソート(マルチバイト対応)
2019/4/17 追記
改良版書きました!!
前回、前々回 の続きですが、マルチバイトの数字には対応できていなかったので対応させました。こちら を参考にしつつ、Windows エクスプローラー準拠の動作を実現させました。
前回のコードのままだと strconv.Atoi() でマルチバイト数字はパースエラーとなってしまうので、その前段に golang.org/x/text/width パッケージを挟むことで、全角数字を半角数字にしてから数字に変換しています。golang にはこういうパッケージが標準/準標準でたくさんあるのでありがたいですね。
package main import ( "fmt" "sort" "strconv" "unicode" "golang.org/x/text/width" ) func getRune(ru []rune, i int) (rune, int) { for x := i; x < len(ru); x++ { if unicode.IsSpace(ru[x]) { continue } return ru[x], x } return rune(0), len(ru) } func natualSort0(a, b []rune) int { var ca, cb rune var ai, bi int for { if len(a) <= ai && len(b) <= bi { return 0 } if len(a) <= ai { return -1 } if len(b) <= bi { return 1 } ca, ai = getRune(a, ai) cb, bi = getRune(b, bi) if unicode.IsNumber(ca) && unicode.IsNumber(cb) { aj := ai + 1 for len(a) > aj { if !unicode.IsNumber(rune(a[aj])) { aj-- break } aj++ } bj := bi + 1 for len(b) > bj { if !unicode.IsNumber(rune(b[bj])) { bj-- break } bj++ } sa := a[ai:aj] if len(sa) == 0 { sa = []rune{a[ai]} } ia, err := strconv.Atoi(width.Narrow.String(string(sa))) if err != nil { panic(err) } sb := b[bi:bj] if len(sb) == 0 { sb = []rune{b[bi]} } ib, err := strconv.Atoi(width.Narrow.String(string(sb))) if err != nil { panic(err) } if ia < ib { return -1 } if ia > ib { return 1 } // Windows エクスプローラーの仕様と合わせるために // 今回は削除 // if len(a[ai:aj]) < len(b[bi:bj]) { // return -1 // } // if len(a[ai:aj]) > len(b[bi:bj]) { // return -1 // } // ai = aj // bi = bj } if ca < cb { return -1 } if ca > cb { return 1 } ai++ bi++ } } func naturalSort(strings []string) func(i, j int) bool { return func(i, j int) bool { return natualSort0([]rune(strings[i]), []rune(strings[j])) <= 0 } } func dumpByNaturalSort(strings []string) { sort.Slice(strings, naturalSort(strings)) for i, s := range strings { if i != 0 { fmt.Print(" < ") } fmt.Printf("%+v", s) } fmt.Println() } func main() { dumpByNaturalSort([]string{"a20", "a10", "a2", "a1b", "a1a", "a1", "a0", "a"}) // a < a0 < a1 < a1a < a1b < a2 < a10 < a20 dumpByNaturalSort([]string{"x8-y8", "x2-y08", "x2-y7", "x2-g8"}) // x2-g8 < x2-y7 < x2-y08 < x8-y8 dumpByNaturalSort([]string{"1.3", "1.1", "1.02", "1.010", "1.002", "1.001"}) // 1.001 < 1.1 < 1.002 < 1.02 < 1.3 < 1.010 dumpByNaturalSort([]string{"001", "01", "1", "10", "010", "2", "002"}) // 001 < 01 < 1 < 002 < 2 < 010 < 10 dumpByNaturalSort([]string{"a001", "a01", "a1", "a10", "a010", "a2", "a002"}) // a001 < a01 < a1 < a002 < a2 < a010 < a10 dumpByNaturalSort([]string{"３", "1", "10", "2", "20"}) // 1 < 2 < ３ < 10 < 20 }
自然順ソート別実装(Windows エクスプローラー準拠?)
2019/4/17 追記
改良版書きました!!
前の記事 の最後に、ゼロパディングされた数値とそうでない数値が存在した場合に数値順に並んでくれないという問題があると書きました。今回はそれを解消したいと思います。
考え方としては単純で、文字列中の数値の部分を取り出して数値に変換したのちに大小比較をするだけです。もし数値が同じであれば桁数で比較して大小を決定します。
Goでの実装
今回もGoで実装しました。前回の記事から変更している部分は naturalSort0 の 数値かどうかを判定するif文の中のみです。数値の始まりと数値の終わりのインデックスを取得して、部分文字列を作成し、部分文字列を数値に変換したのち大小比較を行っています。初めは、比較結果がイコールだった場合は桁数も比較していたのですが、Windows の エクスプローラーの仕様と合わせるために削除しました。
package main import ( "fmt" "sort" "strconv" "unicode" ) func getRune(s string, i int) (rune, int) { for x := i; x < len(s); x++ { if unicode.IsSpace(rune(s[x])) { continue } return rune(s[x]), x } return rune(0), len(s) } func natualSort0(a, b string) int { var ca, cb rune var ai, bi int for { if len(a) <= ai && len(b) <= bi { return 0 } if len(a) <= ai { return -1 } if len(b) <= bi { return 1 } ca, ai = getRune(a, ai) cb, bi = getRune(b, bi) if unicode.IsDigit(ca) && unicode.IsDigit(cb) { aj := ai + 1 for len(a) > aj { if !unicode.IsDigit(rune(a[aj])) { aj-- break } aj++ } bj := bi + 1 for len(b) > bj { if !unicode.IsDigit(rune(b[bj])) { bj-- break } bj++ } sa := a[ai:aj] if sa == "" { sa = string(a[ai]) } ia, _ := strconv.Atoi(sa) sb := b[bi:bj] if sb == "" { sb = string(b[bi]) } ib, _ := strconv.Atoi(sb) if ia < ib { return -1 } if ia > ib { return 1 } // Windows エクスプローラーの仕様と合わせるために // 今回は削除 // if len(a[ai:aj]) < len(b[bi:bj]) { // return -1 // } // if len(a[ai:aj]) > len(b[bi:bj]) { // return -1 // } // ai = aj // bi = bj } if ca < cb { return -1 } if ca > cb { return 1 } ai++ bi++ } } func naturalSort(strings []string) func(i, j int) bool { return func(i, j int) bool { return natualSort0(strings[i], strings[j]) <= 0 } } func dumpByNaturalSort(strings []string) { sort.Slice(strings, naturalSort(strings)) for i, s := range strings { if i != 0 { fmt.Print(" < ") } fmt.Printf("%+v", s) } fmt.Println() } func main() { dumpByNaturalSort([]string{"a20", "a10", "a2", "a1b", "a1a", "a1", "a0", "a"}) // a < a0 < a1 < a1a < a1b < a2 < a10 < a20 dumpByNaturalSort([]string{"x8-y8", "x2-y08", "x2-y7", "x2-g8"}) // x2-g8 < x2-y7 < x2-y08 < x8-y8 dumpByNaturalSort([]string{"1.3", "1.1", "1.02", "1.010", "1.002", "1.001"}) // 1.001 < 1.1 < 1.002 < 1.02 < 1.3 < 1.010 dumpByNaturalSort([]string{"001", "01", "1", "10", "010", "2", "002"}) // 001 < 01 < 1 < 002 < 2 < 010 < 10 dumpByNaturalSort([]string{"a001", "a01", "a1", "a10", "a010", "a2", "a002"}) // a001 < a01 < a1 < a002 < a2 < a010 < a10 }
まとめ
自然順ソートでゼロパディングされた数値とそれ以外の数値が混在していたとしても数値順に並ぶようなアルゴリズムを考え、Go言語で実装しました。 しかし、この実装だと、小数点の場合に順番に並んでくれないため、小数点を使うようなソートには向いていません。 ただ、ファイル名等を順番に並べるようなケースでは重宝すると思います。
自然順ソートをGoで実装
文字列の中に数値があるような場合、ソートの時にその数値の桁がそろっていないと意図しない順番になることがあります。
a1 a10 a2
のようなケースです。実際には
a1 a2 a10
のように数字順に並んでほしいですよね、それを実現するのが自然順ソート(Natural Sort) です。
アルゴリズム
以下のURLに詳細なアルゴリズムが記述されています。
Natural Order String Comparison
ただ、いかんせん英語なのであまり理解ができませんでした。
同ページにC言語で記述されたソースコードへのリンク(http://sourcefrog.net/projects/natsort/strnatcmp.c) があったので、それをもとに私の理解を以下に記します。
文字列を1文字ずつ走査して数値が出現したタイミングで数値比較を行います。ゼロパディング(数値の頭をそろえるために0埋めすること)をされている場合は左寄せ比較(文字列比較とほぼ等価の比較)を行い、それ以外の場合は右寄せ比較を行います。右寄せ比較では桁数が判明するまで1文字ずつ数値比較を行い、桁数が判明した段階で、大小関係を確定させます。また、空白は無視します。結構単純なアルゴリズムですが、これだけのことで数値があべこべにならずにソートされます。
左寄せ比較
左寄せ比較では、文字が数値以外になるまで左から順番に文字比較を行います。数値がイコールなら次の文字を比較し、大小関係が判明すればその時点で比較は終了します。もし、数値以外の文字がどちらかの比較文字に現れた場合は、もう片方の数値より桁が小さいということになり、その時点で大小関係が判明するので比較は終了します。もし同時に数値ではない文字が現れた場合は数値部分はイコールとなり、文字列比較を続けます。
例1 : ゼロパディングされた数値 A: 0012 B: 0135 A[0] -> 0, B[0] -> 0 : 数値なので数値比較, 数値が0なので左寄せ比較 A[1] -> 1, B[1] -> 0 : A[1] < B[1] なので A < B となり比較終了
例2 : 数値以外の文字が後ろにつくケース
A: 01a
B: 015
A[0] -> 0, B[0] -> 0 : 数値なので数値比較, 数値が0なので左寄せ比較
A[1] -> 1, B[1] -> 1 : 数値がイコールなので次の文字を比較
A[2] -> a, B[2] -> 5 : A[2]が文字なので、Bのほうが数値の桁数が多いと
判断できるため、A < B となり比較終了
例3 : 数値が文字列中に複数回存在する場合
A: 0a03a
B: 0a02b
A[0] -> 0, B[0] -> 0 : 数値なので数値比較, 数値が0なので左寄せ比較
数値はイコールなので次の文字を比較
A[1] -> a, B[1] -> a : 数値以外の文字が出現したので左寄せ数値比較は行わず
文字比較を行う。比較の結果イコールであるため
次の文字を比較
A[2] -> 0, B[2] -> 0 : 数値なので数値比較, 数値が0なので左寄せ比較
数値はイコールなので次の文字を比較
A[3] -> 3, B[3] -> 2 : A[3] > B[3] なので A > B となり比較終了
右寄せ比較
右寄せ比較では、左寄せ比較と同様に左から一文字ずつ数値比較を行いますが、大小関係が判明しても比較を終了せず、桁数が判明するまで大小関係を保持します。桁数が同じだった場合、保持していた大小比較でもって大小判定を行い、桁数が違った場合は桁数で大小判定を行います。
例1 : 桁数が同じ場合 A: a20 B: a15 A[0] -> a, B[0] -> a : 文字列比較、イコールなので次の文字を比較 A[1] -> 2, B[1] -> 1 : A > B となるが、桁数が確定しないので、大小比較結果を保存し、次の文字を比較 A[2] -> 0, B[2] -> 5 : 数値の続きなので、比較をスキップし次の文字を比較 A[3] -> *, B[3] -> * : 両方が終端に達し、桁数が同じなので、保存していた大小結果を最終結果とする
例2 : 桁数が違う場合 A: a2b B: a15c A[0] -> a, B[0] -> a : 文字列比較、イコールなので次の文字を比較 A[1] -> 2, B[1] -> 1 : A > B となるが、桁数が確定しないので、次の文字を比較 A[2] -> b, B[2] -> 5 : Aが終端に達したので 桁数が A < B となり、大小判定が確定
Goでの実装
2019/4/16 AM 8:00 追記
すでに実装があるので、そちらを見ていただいたほうがいいと思います。 mattn.kaoriya.net せっかくなので以下のソースは残しておきます。
2019/4/17 追記
改良版書きました!!
Goでの実装はこんな感じになります。もうちょっとうまく書く方法がありそうですが、さしあたってはうまく動いているようです。
package main import ( "fmt" "sort" "unicode" ) func compareLeft(a, b string) int { var ai, bi int for { if (len(a) <= ai || !unicode.IsDigit(rune(a[ai]))) && (len(b) <= bi || !unicode.IsDigit(rune(b[bi]))) { return 0 } if len(a) <= ai || !unicode.IsDigit(rune(a[ai])) { return -1 } if len(b) <= bi || !unicode.IsDigit(rune(b[bi])) { return 1 } ca, cb := rune(a[ai]), rune(b[bi]) if ca < cb { return -1 } if ca > cb { return 1 } ai++ bi++ } } func compareRight(a, b string) (bias int) { for ai, bi := 0, 0; ; ai, bi = ai+1, bi+1 { if (len(a) <= ai || !unicode.IsDigit(rune(a[ai]))) && (len(b) <= bi || !unicode.IsDigit(rune(b[bi]))) { return bias } if len(a) <= ai || !unicode.IsDigit(rune(a[ai])) { return -1 } if len(b) <= bi || !unicode.IsDigit(rune(b[bi])) { return 1 } ca, cb := rune(a[ai]), rune(b[bi]) switch { case ca < cb: if bias == 0 { bias = -1 } case ca > cb: if bias == 0 { bias = 1 } } } } func getRune(s string, i int) (rune, int) { for x := i; x < len(s); x++ { if unicode.IsSpace(rune(s[x])) { continue } return rune(s[x]), x } return rune(0), len(s) } func natualSort0(a, b string) int { var ca, cb rune for ai, bi := 0, 0; ; ai, bi = ai+1, bi+1 { if len(a) <= ai && len(b) <= bi { return 0 } if len(a) <= ai { return -1 } if len(b) <= bi { return 1 } ca, ai = getRune(a, ai) cb, bi = getRune(b, bi) if unicode.IsDigit(ca) && unicode.IsDigit(cb) { if ca == '0' || cb == '0' { if ret := compareLeft(a[ai:], b[bi:]); ret != 0 { return ret } } else { if ret := compareRight(a[ai:], b[bi:]); ret != 0 { return ret } } } if ca < cb { return -1 } if ca > cb { return 1 } } } func naturalSort(strings []string) func(i, j int) bool { return func(i, j int) bool { return natualSort0(strings[i], strings[j]) <= 0 } } func dumpByNaturalSort(strings []string) { sort.Slice(strings, naturalSort(strings)) for i, s := range strings { if i != 0 { fmt.Print(" < ") } fmt.Printf("%+v", s) } fmt.Println() } func main() { dumpByNaturalSort([]string{"a20", "a10", "a2", "a1b", "a1a", "a1", "a0", "a"}) // a < a0 < a1 < a1a < a1b < a2 < a10 < a20 dumpByNaturalSort([]string{"x8-y8", "x2-y08", "x2-y7", "x2-g8"}) // x2-g8 < x2-y08 < x2-y7 < x8-y8 dumpByNaturalSort([]string{"1.3", "1.1", "1.02", "1.010", "1.002", "1.001"}) // 1.001 < 1.002 < 1.010 < 1.02 < 1.1 < 1.3 dumpByNaturalSort([]string{"001", "01", "1", "10", "010", "2", "002"}) // 001 < 002 < 01 < 010 < 1 < 2 < 10 dumpByNaturalSort([]string{"a001", "a01", "a1", "a10", "a010", "a2", "a002"}) // a001 < a002 < a01 < a010 < a1 < a2 < a10 }
まとめ
自然順ソートについて理解し、Goで実装してみました。ある程度はうまく動いているようですが、ゼロパディングされた数値とそうでない数値が混在するような場合や、ゼロパディングされた数値同士でも桁が違う場合などは期待した結果にはなってくれませんでした。これを解決する案はぼんやりあって、ゼロパディングされた数値文字列を取り出して数値比較を行うことで解決できるんじゃないかなぁとは思っていますが、まだ実装するには至っていません。
ブルームフィルタをGoで書く
要約
Turing Complete FM #13 を聞いていると、ブルームフィルタというデータ構造についての話題がありました。ブルームフィルタというものを知らなかったので色々調べてみると面白そうだったのでGoで実装してみました。
ブルームフィルタとは?
誤解を恐れず言うと、存在可否をすごい早く判定できるけど誤判定する可能性があるデータ構造です。ただ「存在しない」という結果の場合は誤判定はせず 100% 存在しませんが、「存在する」という結果の場合は実際は存在しない場合があります。
| 判定結果 | 実際 |
|---|---|
| 存在しない | 存在しない |
| 存在する | 存在する or 存在しない |
この「存在しなけど存在すると判定する」ことを「偽陽性」というらしいです。
ブルームフィルタの作り方
ブルームフィルタでは存在するもののリストを一つの固定長ビット列に保存します。リストの要素を複数のハッシュ関数でハッシュ化し、そのデータをビット列に重ね書きすることでブルームフィルタが完成します。ただ、ハッシュ化したデータをそのままビット列に書くのではなく、ハッシュ値をインデックスとみなして、インデックスのビットをセットすることで要素を保存していきます。
ハッシュ関数は同じ関数でもよいですが、その場合はそれぞれで別々のハッシュ値を取り出すためにそれぞれに別々のシードをつけてあげる必要があります。
要素の検索
ブルームフィルタを作った後、要素を検索します。検索する要素をフィルタを作った時と同じハッシュ関数にかけて、インデックスを算出します。算出したインデックスのビットがすべて1ならその要素は存在していると判断され、インデックスのビットのうち、どれか一つでも0なら存在しないと判断されます。
誤判定ケース
存在しない要素でも、計算したインデックスが偶然すべて1になると誤判定になります。
誤判定の確率
誤判定の確率はビット配列のサイズ(m)、登録する要素の数(n)、ハッシュ関数の数(k) で決まります。確率を(p)とすると以下の公式になるそうです。
僕はビット配列サイズと確率が固定の場合に最大要素登録数となるハッシュ関数の個数が知りたかったので n を左辺とする式に変形しました。
例えば、m = 8192 で p = 0.01 の場合の n と k の関係をグラフ化すると以下のようになります。
これを見ると、k = 7 の時に n = 854 となり、このラインが 偽陽性 0.01 を超えない最大の格納数となるようです。
使いどころ
誤判定するようなものに使いどころがあるのか？と思ってしまうけど、キャッシュ存在判定によく使われているようです。SQLのテーブル結合でも内部的に使用している場合もあるようです。フィルタというくらいなので、検索要素が多く、その検索が重い場合にその前段にブルームフィルタを置いて、検索要素数を減らしたうえで、本来の検索をする。といったような用途に使うのがいいのかもしれません。
- Kazuho's Weblog: ソート済の整数列を圧縮する件
- pixivでBloomFilterを使うためにやったこと - pixiv inside [archive]
- SQL実行時のブルームフィルタ(Bloom Filter)アルゴリズム | Future Tech Blog - フューチャーアーキテクト
Goで実装してみる。
上記を踏まえて実装したのが以下のコードになります。今回はハッシュ関数に Goの標準パッケージに添付されている hash/fnv を使用しました。また、k個のハッシュ関数を hash/fnv から導くために ダブルハッシュ法を使用しました (参考資料: C++でブルームフィルタを実装する方法 | POSTD) ダブルハッシュ法に関してはよくわかってないですが、ハッシュ値とシード値をダブルハッシュ関数に渡すことでランダムはハッシュ関数がお手軽に手に入れられるもの。という認識です。main() 関数ではランダムな要素を854個登録し、そのあとで、ランダムな要素 百万個を検索したときの偽陽性と登録した要素がすべてマッチするかを調べています。実行の結果、偽陽性に関しては理論値の0.01に近い確率で偽陽性が判定できていて、登録した要素もすべてマッチするので実装としては問題ないかと思っています。
package main import ( "fmt" "hash" "hash/fnv" "io" "math/rand" "time" ) func NewBloomFilter(msize, hsize int, hfunc func() hash.Hash64) *BloomFilter { m := make([]bool, msize) return &BloomFilter{ m, hsize, hfunc, } } type BloomFilter struct { m []bool hsize int hfunc func() hash.Hash64 } func (b *BloomFilter) Set(data string) { hashA, hashB := b.hash(data) for i := 0; i < b.hsize; i++ { ofs := b.nthHash(hashA, hashB, i, len(b.m)) b.m[ofs] = true } } func (b *BloomFilter) IsMatch(data string) bool { hashA, hashB := b.hash(data) for i := 0; i < b.hsize; i++ { ofs := b.nthHash(hashA, hashB, i, len(b.m)) if !b.m[ofs] { return false } } return true } func (b *BloomFilter) hash(data string) (uint32, uint32) { h := b.hfunc() io.WriteString(h, data) hash := h.Sum64() ha := uint32(hash) hb := uint32(hash >> 32) return ha, hb } func (b *BloomFilter) nthHash(ha, hb uint32, n, size int) uint32 { return (ha + uint32(n)*hb) % uint32(size) } func main() { b := NewBloomFilter(8192, 7, fnv.New64) lines := make(map[string]bool, 0) rand.Seed(42) for i := 0; i < 854; i++ { key := fmt.Sprintf("%v", rand.Intn(4294967294)) lines[key] = true b.Set(key) } rand.Seed(time.Now().UnixNano()) total := 0 match := 0 miss := 0 for i := 0; i < 1000000; i++ { key := fmt.Sprintf("%v", rand.Intn(4294967294)) total++ if b.IsMatch(key) { match++ if _, ok := lines[key]; !ok { miss++ } } } fmt.Printf("total:%d, match:%d, miss:%d, p:%v\n", total, match, miss, float64(miss)/float64(total)) total = 0 match = 0 miss = 0 for key := range lines { total++ if b.IsMatch(key) { match++ if _, ok := lines[key]; !ok { miss++ } } } fmt.Printf("total:%d, match:%d, miss:%d\n", total, match, miss) }
まとめ
ブルームフィルタとは何かを理解し、Goで実装してみました。実装も予想していたよりも簡単に実装できたのが意外でした。ただ使いどころがいまいち思いついていなくて、実際の業務に使うことはあまりないのかもしれません。あと、Goではboolの配列(スライス)を作ると1要素に1バイト使用するので無駄なビットが出てしまうことが気になっています。無駄をなくすには別途1バイトにビットを詰めるようなクラス(構造体(?))を作るなどして対応する必要がありそうです。
Go製 Felica ライブラリ pasori に MAC付きRead とMAC付きWriteを足した
前回のブログ の続きです。前回はMACをつけないRead/Writeのコマンドを足しましたが、今回はMAC付きのRead/Writeのコマンドを足しました。前回から10日間ずっと、この実装のバグが取れずに悩んでたのでようやくブログにできる程度に実装できたのは素直にうれしいですね。
MAC といっても MAC(Media Control address)アドレスの MACではなく、Message Authentication Code の略で、データが改ざんされていないかをチェックするためのコードのことです。
参考資料
SONYのFelica技術情報 から 『FeliCa Lite-Sユーザーズマニュアル』のPDFを参照。(なぜか直接リンクだと表示されないので、いったん技術情報のページに繊維してから「ダウンロード」を選択すること)
[PASMO] FeliCa から情報を吸い出してみる - FeliCaの仕様編 [Android][Kotlin] - Qiita
FeliCa Liteの片側認証 - hiro99ma site
使い方
MAC付き読み出しは2種類あります。MACブロックを使う方法とMAC_Aブロックを使う方法です。MACブロックはFelica Lite からの互換性のために存在していて、Felica Lite-S ではMAC_Aブロックを使うことが推奨されています。MACブロックを使ってMAC付き書き込みはできないので、MAC付き書き込みを行う場合はMAC_Aブロックを使います。
注意点として、MAC付き読み出し/書き込みを行う前に、事前にカード鍵ブロックにカード鍵を書き込んでおく必要があります。また、カード接触後にランダムチャレンジブロックにランダムな値を事前に書き込んでおく必要があります。
MACブロックを使ってのMAC付読み出し
基本的な使い方は cmd/with_mac に例があるのでそれを掲載します
package main import ( "fmt" "crypto/rand" "github.com/bamchoh/pasori" ) func main() { var err error fmt.Println("Please touch FeliCa") // pasori 初期化 psr, err := pasori.InitPasori() if err != nil { panic(err) } defer psr.Release() // ランダムチャレンジデータ生成 psr.RC = make([]byte, 16) _, err = rand.Read(psr.RC) if err != nil { panic(err) } // ランダムチャレンジブロックに書き込み err = psr.FelicaWriteWithoutEncryption(pasori.RC, psr.RC) if err != nil { panic(err) } // カード鍵生成 // [注意] // カード鍵は悪意のある第三者にバレると改ざんされてしまうので // 本来はソースコードに記述するのではなく、外部ファイル等で // 管理しておくことをお勧めします。 // // あと、カードにいったん同じ鍵を書き込んでおくこと。そうしないと // MAC生成時にエラーになります。 // 書き込みは普通に WriteWithoutEncryption で書き込めばOK psr.CK = []byte{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16} // S_PAD0 ブロックに適当に書き込み err = psr.FelicaWriteWithoutEncryption(pasori.S_PAD0, []byte{3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3}) if err != nil { panic(err) } // MAC付き読み出し // 第一引数にはサービスコード、第二引数以降には読み出し先ブロック番号を指定 blocks, err := psr.FelicaReadWithMAC(pasori.SERVICE_RO, pasori.S_PAD0) if err != nil { panic(err) } fmt.Println("s_pad0", blocks[0]) }
MAC_Aブロックを使ってのMAC付読み出し/書き込み
基本的な使い方は cmd/with_mac_a に例があるのでそれを掲載します
package main import ( "fmt" "crypto/rand" "github.com/bamchoh/pasori" ) func main() { var err error fmt.Println("Please touch FeliCa") // pasori 初期化 psr, err := pasori.InitPasori() if err != nil { panic(err) } defer psr.Release() // ランダムチャレンジデータ生成 psr.RC = make([]byte, 16) _, err = rand.Read(psr.RC) if err != nil { panic(err) } // ランダムチャレンジブロックに書き込み err = psr.FelicaWriteWithoutEncryption(pasori.RC, psr.RC) if err != nil { panic(err) } // カード鍵生成 // [注意] // カード鍵は悪意のある第三者にバレると改ざんされてしまうので // 本来はソースコードに記述するのではなく、外部ファイル等で // 管理しておくことをお勧めします。 psr.CK = []byte{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16} // MAC付き書き込み // 第一引数には書き込み先ブロック番号、第二引数には書き込みデータ err = psr.FelicaWriteWithMAC_A(pasori.S_PAD0, []byte{3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3}) if err != nil { panic(err) } // MAC付き読み出し // 第一引数にはサービスコード、第二引数以降には読み出し先ブロック番号を指定 blocks, err := psr.FelicaReadWithMAC_A(pasori.SERVICE_RO, pasori.S_PAD0, pasori.S_PAD1) if err != nil { panic(err) } fmt.Println("s_pad0", blocks[0]) fmt.Println("s_pad1", blocks[1]) }
MACの計算のハマりポイント
felica のDES暗号をGoで表現するには?
Felica の MAC生成には 2-key Triple DES-CBC が使われています。 DES暗号はGoではdes パッケージで取り扱うことができます。ちょうど Triple DES もパッケージの中にあるので、それを使いました。des.NewTripleDESCiper で初期化しますが、引数の key に渡すバイト配列は 24バイトでなければならず、はじめ、なにを設定すればいいのかわかりませんでした。ただ、『Felica Lite-S ユーザーズマニュアル』には セッション鍵であれば、Key1, Key2, Key3 として CK1[0]-[7], CK2[0]-[7], CK1[0]-[7] と記載があります。それを連結させた値を des パッケージの key に渡すのだと思い当たるのにそれほど時間は要りませんでした。ただ、単純に24バイトの連結した値を指定すればいいのではなくバイト単位で配列を反転させて設定してやる必要がありました。(これは Felica 側の仕様で、Triple DES の仕様ではないようです) つまり、指定する24バイトの配列は、セッション鍵生成時のTriple DESであれば、CK1[7]-[0], CK2[7]-[0], CK1[7]-[0] を連結させた24バイトを指定しなければなりませんでした。
MAC付き読み出し(MACブロック)、MAC付き読み出し(MAC_Aブロック)、MAC付き書き込みで入力パラメータが微妙に違う
全ての方法において、2-key Triple DES-CBC を使用して MACを算出するというのは同じなんですが、KEYに指定するパラメータが違ったり、初期値として代入するデータが違ったりします。(当たり前か)
| メソッド | key1 | key2 | key3 | 入力値 |
|---|---|---|---|---|
| セッション鍵の生成 | CK1 | CK2 | CK1 | RC1 |
| MAC付き読み出し(MACブロック) | SK1 | SK2 | SK1 | RC1 と ブロックデータ1[0]-[7] との排他的論理和 |
| MAC付き読み出し(MAC_Aブロック) | SK1 | SK2 | SK1 | RC1 と ブロック番号との排他的論理和 |
| MAC付き書き込み(MAC_Aブロック) | SK2 | SK1 | SK2 | RC1 と 複合ブロック(※1)との排他的論理和 |
(※1) WCNT と 書き込みブロック番号を8バイトに詰め込んで1ブロックとしたもの
読み出しはMACブロックが値として取得できるので、計算結果との検算がしやすいのだが、書き込みの場合は検算ができないので、正しく書き込めたかどうかぐらいしか情報がなく、デバッグにどえらい時間がかかってしまった。また、KEYが書き込みの時だけ逆だったり、WCNTの値を取得してこなければならなかったりと、書き込みだけ複雑な構造をしているので余計にハマりやすかった。
メモリコンフィギュレーションブロックにMAC付きアクセスの設定をしておかないとエラーになる
メモリコンフィギュレーションブロック(MC) というブロックがあり、各ブロックへのアクセス権限を設定できるようになっている。初期状態では、MAC付きアクセスなしの状態なので、MAC付きアクセスありの状態にしてやる必要がある。また、MAC付きアクセスありの設定にすると元に戻すことはできないらしいので注意が必要。どのビットがどのブロックに対応しているかは『Felica Lite-S ユーザーズマニュアル』を参照のこと。
Go製 Felica ライブラリ pasori に read without encryption コマンドと write without encryption コマンドを足した
Windows だけだが、拙作の Go製 Felica ライブラリ pasori に read without encryption と write without encryption コマンドを足した。
参考にした記事/サイト一覧
[PASMO] FeliCa から情報を吸い出してみる - FeliCaの仕様編 [Android][Kotlin] - Qiita
FeliCa Liteの片側認証 - hiro99ma site
使い方
基本的な使い方は cmd/dump を見てもらえばいい。今のところ、FelicaWriteWithoutEncryption に渡す書き込み値は最初の16バイトをユーザーブロック0に書くのみ。
MAC付読み込み/書き込みは今のところサポートしてない。
package main import ( "fmt" "github.com/bamchoh/pasori" ) func dump_buffer(buf []byte) string { str := "" for _, b := range buf { str += fmt.Sprintf("%02X", b) } return str } var ( VID uint16 = 0x054C // SONY PID uint16 = 0x06C3 // RC-S380 ) func main() { var err error fmt.Println("Please touch FeliCa") psr, err := pasori.InitPasori() if err != nil { panic(err) } defer psr.Release() err = psr.FelicaWriteWithoutEncryption([]byte{16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}) if err != nil { panic(err) } b, err := psr.FelicaReadWithoutEncryption() if err != nil { panic(err) } fmt.Println(b) }
TODOアプリに react-beautiful-dnd を追加する
TODO アプリに ドラッグ&ドロップでタスクを動かせるようにした。
苦労した点1 Typescript と react-beautiful-dnd の相性
react-beautiful-dnd では公式には Typescript をサポートしていません。型定義にはflowtypeを使用しています。
ただ、@types/react-beautiful-dnd はあるようなので今回はそちらを使用しました。バージョンは10.0.3
しかし、この定義ファイルにも問題があるようで、そのままで使うと webpack のビルドでエラーが発生しました。
なので、node_modules/@types/react-beautiful-dnd/index.d.ts の中の React.ReactElement の部分を React.ReactElement<any> に書き換え
とりあえずビルドを通して使うことにしました。
苦労した点2 firebase realtime database との連携
上記の画像のように入れ替えを行うためには、移動させたい要素を移動させたい位置に挿入することで行うわけですが、realtime database には要素のインデックスは無く挿入用のAPIはありませんので、set()かupdate()で行う必要があります。set() は単体の値を設定するときの関数で、update() 関数は複数の値の書き込みに適しています。今回は update() 関数のほうが有用そうでしたので、そちらを使いました。一番初めに思いついた作戦は、移動させる要素をremove()で削除して、移動先以降の要素も削除して再度push() と set() で要素を追加する方法だったのですが、コストや処理の複雑さからやめました。二番目に思いついたのは移動元と移動先の間にある要素すべてに対して、値だけをスワップさせる方法です。
onDragEnd(payload:any) { const { dst, src, todos } = payload const database:any = this.getDatabase(); const startAt = dst.index const endAt = src.index+1 var todoAry:any = [] // 元の位置から移動先の位置までの部分配列を作成する // 自身より手前に挿入するか、後に挿入するかで作成方法を // 変えている。具体的には、手前に挿入する場合は要素の // 手前から部分配列の要素として挿入し、後ろに挿入する // 場合は後ろから挿入する。 // こうすることで、一番初めに移動させたい要素がくるので // 後の挿入処理が一元化できる。 if(dst.index < src.index) { for(var i = src.index;i >= dst.index;i--) { todoAry.push({...todos[i]}) } } else { for(var i = src.index;i <= dst.index;i++) { todoAry.push({...todos[i]}) } } // 挿入処理 // 初めの要素を取り出してから、次の要素を順次手前に移動させる // 移動させ終わったら、最後の要素に初めの要素を挿入する // id 要素だけは移動させてはいけないので、元の要素のidを使用する var tmp = {...todoAry[0]} for(var i:any = 1;i < todoAry.length; i++) { todoAry[i-1] = {...todoAry[i], id: todoAry[i-1].id} } todoAry[todoAry.length-1] = { ...tmp, id: todoAry[todoAry.length-1].id, } const todoRef = database.ref(`todos/${this.uid}`) // 更新がかかった要素を update() する var updates:any = {} todoAry.forEach((val:any) => { updates[`/${val.id}`] = val }) todoRef.update(updates) }
成果物
成果物は以下のリポジトリにある。
GitHub - bamchoh/react-study at b8d395774638edbf3132ea976410a90193496cba
