追記:はじめに
@MaverickTse, @mtfmk, @YSRKEN 氏の格闘の結果、超高速されたものが登場しました。
SPROUT_CXX14_CONSTEXPR sprout::array<std::uint8_t, 1000> make_mod_table_ysr() {
sprout::array<std::uint8_t, 1000> re{};
for (size_t i = 0; i < 1000; ++i) {
size_t mod = i % 11;
re[i] = static_cast<std::uint8_t>(mod <= 1 ? 0 : 11 - mod);
}
return re;
}
static inline bool validate(const __m128i& x)
{
__m128i t = _mm_sub_epi8(x, _mm_min_epu8(x, _mm_set1_epi8(9)));
return _mm_test_all_zeros(t, _mm_setr_epi32(-1, -1, 0x00FFFFFF, 0)) == 1;
}
uint8_t calc_check_digit_mtfmk_ysrken(const std::string& str) noexcept
{
static SPROUT_CXX14_CONSTEXPR auto mod_table = make_mod_table_ysr();
if (str.size() != 11) {
return 0xFE;
}
__m128i p_n = _mm_loadu_si128(reinterpret_cast<const __m128i*>(str.c_str()));
p_n = _mm_sub_epi8(p_n, _mm_set1_epi8('0'));
if (!validate(p_n)) {
return 0xFF;
}
__m128i sum = _mm_maddubs_epi16(p_n, _mm_setr_epi8(6, 5, 4, 3, 2, 7, 6, 5, 4, 3, 2, 0, 0, 0, 0, 0));
sum = _mm_sad_epu8(sum, _mm_setzero_si128());
sum = _mm_add_epi32(sum, _mm_srli_si128(sum, 8));
return mod_table[_mm_cvtsi128_si32(sum)];
}
詳細は
- SIMD intrinsicでチェックディジットを計算してみる
- SIMD intrinsicでチェックディジットを計算してみる その2
- yumetodo/benchmark_calc_check_degit: C++でマイナンバーのチェックデジットを計算する
を参照してください。
初めに
どうももうすぐマイナンバーの仮カードが配られるらしい。セキュリティがものすごく不安だ。
まあそんな話はさておき
Ruby - マイナンバーのチェックデジットを計算する - Qiita
が目についた。どうやらマイナンバーにはチェックデジット(検査用数字)なるものがあるらしい。
行政手続における特定の個人を識別するための番号の利用等に関する法律施行令
http://law.e-gov.go.jp/announce/H26SE155.html
(個人番号とすべき番号の構成)
第八条 法第八条第二項の規定により生成される個人番号とすべき番号は、機構が同条第三項の規定により設置される電子情報処理組織を使用して、作為が加わらない方法により生成する次に掲げる要件に該当する十一桁の番号及びその後に付された一桁の検査用数字(個人番号を電子計算機に入力するときに誤りのないことを確認することを目的として、当該十一桁の番号を基礎として総務省令で定める算式により算出される零から九までの整数をいう。第三号において同じ。)により構成されるものとする。
一 住民票コードを変換して得られるものであること。
二 前号の住民票コードを復元することのできる規則性を備えるものでないこと。
三 他のいずれの個人番号(法第七条第二項の従前の個人番号及び個人番号とすべき番号を含む。)を構成する検査用数字以外の十一桁の番号とも異なること。
で検査用数字はどうやって求めるのさ?というと
行政手続における特定の個人を識別するための番号の利用等に関する法律の規定による通知カード及び個人番号カード並びに情報提供ネットワークシステムによる特定個人情報の提供等に関する省令
http://law.e-gov.go.jp/announce/H26F11001000085.html
(検査用数字を算出する算式)
第五条 令第八条の総務省令で定める算式は、次に掲げる算式とする。
算式
11―(n=1(シグマ)11(Pn×Qn))を11で除した余り)
ただし、(n=1(シグマ)11(Pn×Qn))を11で除した余り≦1の場合は、0とする。
算式の符号
Pn 個人番号を構成する検査用数字以外の十一桁の番号の最下位の桁を1桁目としたときのn桁目の数字
Qn 1≦n≦6のとき n+1 7≦n≦11のとき n―5
検査用数字の導出法
つまり
-
検査用数字 : $11 - \Bigl( \displaystyle\sum_{n=1}^{11} P_n \times Q_n \Bigr) \% 11$
- ただし $\Bigl( \displaystyle\sum_{n=1}^{11} P_n \times Q_n \Bigr) \% 11 ≦1 $の場合は、$0$とする
-
$Pn$と$Qn$の定義
- $Pn$ : 個人番号を構成する検査用数字以外の十一桁の番号の最下位の桁を $1$ 桁目としたときの $n$ 桁目の数字
- $Qn$ : $1≦n≦6$ のとき $n+1$、 $7≦n≦11$ のとき $n-5$
ということらしい。
計算式を見たってわかんね~、という人は
マイナンバー(個人番号)の12桁の数字の下一ケタがチェックデジット... - Yahoo!知恵袋
をみるといいと思います。(質問者もBANされていないし取り消したような痕跡もないにもかかわらずなぜか質問が消されているのでWebArchiveにリンク張替え)
C++11での実装
というわけで実装していく。例外のエラーメッセージ適当すぎんだろとか言わない。
#include <string>
#include <utility>
#include <numeric>//std::accumulate()
#include <stdexcept>
#include <cctype>//std::isdigit()
int calc_check_digit(const std::string& num) noexcept(false) {
if (11 != num.length()) throw std::runtime_error("num.digit must be 11");
const int remainder = std::accumulate(num.rbegin(), num.rend(), std::pair<int, int>{}, [](const std::pair<int, int>& s, const char& e){
if(!std::isdigit(e)) throw std::runtime_error("num.digit must be 11");
const int n = s.second + 1;
const int p = e - '0';
const int q = (6 < n) ? n - 5 : n + 1;
return std::pair<int, int>{s.first + p * q, n};
}).first % 11;
return (0 == remainder || 1 == remainder) ? 0 : 11 - remainder;
}
#include <string>
#include <utility>
#include <numeric>
#include <stdexcept>
#include <cctype>
int calc_check_digit(const std::string& n) noexcept(false) {
if (11 != n.size()) throw std::runtime_error("n.digit must be 11");
const int r = std::accumulate(n.rbegin(), n.rend(), std::pair<int, int>{}, [](const auto& s, const char& e) -> std::pair<int, int>{
if(!std::isdigit(e)) throw std::runtime_error("n.digit must be 11");
return {s.first + (e - '0') * ((5 < s.second) ? s.second - 4 : s.second + 2), s.second + 1};
}).first % 11;
return (0 == r || 1 == r) ? 0 : 11 - r;
}
numeric
ヘッダーにあるものだから忘れられがちなstd::accumulate
ですが無茶めちゃ便利です。単に合計を求めるだけでなく、第3, 4引数を工夫することでかなりいろいろできます。
ただしstd::accumulate
の第3引数の型と第4引数で指定する関数の第1引数の型から参照とcv修飾子を除いた型とその戻り値の型、さらにstd::accumulate
の戻り値を受ける変数の型は一致させましょう。あと第1,2引数で指定したイテレータが指すコンテナの要素型と第4引数で指定する関数の第2引数の型から参照とcv修飾子を除いた型もですね。結果が謎になります。
//イメージ
Ret result = std::accumulate(Container<Elem>::iterator begin, Container<Elem>::iterator end, Ret init, [](const Ret& r, const Elem& e) -> Ret{});
検査用数字の導出法が下桁からみていくようだったのでリバースイテレータを使ってます。ruby版だとreverseしてますがそんなことする必要は無いですからね。
このcalc_check_digit
関数は例外を投げうるので、呼ぶときはちゃんと例外処理してください。
実行例
各言語実装まとめ
Qiitaでは一番上のRuby版が最初だと思います。
python版が出てる!これは勝ち確定です!(何に対する?)
Swift版も出たとかついにApple信者(偏見)もマイナンバー対応に動いたのか(違う)。
そして驚くべき言語展開。なんでこんなに流行ってるのさ。
ここまでみて分かる通りすべて文字列として数値を受け取るものばかりです。なぜなら先頭が0のマイナンバーを判別できないからです。数値でやってる人もいた。
ところで「Groovyって何?」となって
http://codezine.jp/article/detail/3757
を見るまで知らなかった件
なんか @h_oki 氏によるBrainfuck版が出てるけど控えめに言って頭おかC・・・いや、なんでもない。
追記
http://qiita.com/rana_kualu/items/f36275032bbc6a3f18b4
チェックディジットは一意に決まるので、実質11桁、たった1000億通りしかありません。
現時点でも適当に1000回撃てば一回通ってしまいます。
IPv6とまでは言わないが、せめて16桁くらい取っておいてもよかっただろ。
お、せやな(棒読み)
実際にマイナンバーが届いた
というわけで実際に実行例のプログラムで試したところ、ちゃんとチェックデジットはあってました。良かった。
追記:ベンチマーク
なんか
ただマイナンバー計算しても面白くないから最速を目指してみた。
なる記事がでた。どう考えても私の記事を煽っている(注:という妄想です)
で、その記事を読んでみたが、4点気に入らない
- 引数が
const array<int, 12>&
だが、常識的に考えて、入力は文字列だろうから、const std::string&
でなければ困る - 無駄にキャストするな、可読性もくそもありゃしねぇ
- helper関数として
Q
という名の関数があるがなんでconstexprじゃねーんだ。constexprは市民の義務だろ! -
clock()
とかいうC++においてはとっととdeprecatedになるべき関数を時間計測に用いている。ありえない。しかも大抵の環境では分解能が低い。std::chrono::high_resolution_clock::now
を使おう(ただしVSの場合VS2013までは分解能が高くない)
というわけで書き換えて、ついでに私のコードと勝負させることにした。
ちなみに私のコードもstd::isdigit
は使わないように書き換えている。わざわざlocale依存の関数を使う必要はよく考えて見ればないからな。ついでにエラー処理と計算部分を分離した。
std::uint8_t calc_check_digit_yumetodo(const std::string& n) noexcept(false) {
if (11 != n.size()) throw std::runtime_error("n.digit must be 11");
for(auto e : n) if(e < '0' || '9' < e) { throw std::runtime_error("in function calc_check_digit_yumetodo : iregal charactor detect.(" + n + ')'); }
const std::uint8_t r = std::accumulate(n.rbegin(), n.rend(), std::pair<int, int>{}, [](const auto& s, const char& e) -> std::pair<int, int>{
return {s.first + (e - '0') * ((5 < s.second) ? s.second - 4 : s.second + 2), s.second + 1};
}).first % 11;
return (0 == r || 1 == r) ? 0 : 11 - r;
}
constexpr unsigned short Q(unsigned char n) {
return (1 <= n && n <= 6) ? n + 1 : n - 5;
}
std::uint8_t calc_check_digit_ryogaelbtn(const std::string& P) {
if (11 != P.size()) throw std::runtime_error("P.digit must be 11");
for(auto e : P) if(e < '0' || '9' < e) { throw std::runtime_error("in function calc_check_digit_ryogaelbtn : iregal charactor detect.(" + P + ')'); }
unsigned int sum = 0;
sum += static_cast<unsigned short>(P[10]) * Q(1);
sum += static_cast<unsigned short>(P[9]) * Q(2);
sum += static_cast<unsigned short>(P[8]) * Q(3);
sum += static_cast<unsigned short>(P[7]) * Q(4);
sum += static_cast<unsigned short>(P[6]) * Q(5);
sum += static_cast<unsigned short>(P[5]) * Q(6);
sum += static_cast<unsigned short>(P[4]) * Q(7);
sum += static_cast<unsigned short>(P[3]) * Q(8);
sum += static_cast<unsigned short>(P[2]) * Q(9);
sum += static_cast<unsigned short>(P[1]) * Q(10);
sum += static_cast<unsigned short>(P[0]) * Q(11);
return sum % 11 <= 1 ? 0 : 11 - sum % 11;
}
計測は一発勝負、ループ回数は元記事の10倍の10000000(10^7)回、環境はだれでも利用できるwandboxを用いる。
generating inputs...done.
start vench mark:
calc_check_digit_ryogaelbtn : 251[ms] (251311496[ns])
calc_check_digit_yumetodo : 265[ms] (265814777[ns])
vench mark finish!
generating inputs...done.
start vench mark:
calc_check_digit_ryogaelbtn : 247[ms] (247027803[ns])
calc_check_digit_yumetodo : 244[ms] (244624077[ns])
vench mark finish!
generating inputs...done.
start vench mark:
calc_check_digit_ryogaelbtn : 255[ms] (255793658[ns])
calc_check_digit_yumetodo : 475[ms] (475591886[ns])
vench mark finish!
generating inputs...done.
start vench mark:
calc_check_digit_ryogaelbtn : 203[ms] (203583920[ns])
calc_check_digit_yumetodo : 202[ms] (202423769[ns])
vench mark finish!
両者差はないかな。GCCの-O2
だけ差がついたのは、std::accumulate
とstd::pair
をうまく消せてないからかな?
結論としては、コンパイラの最適化は鬼がかっているので、無理に読みづらくしてまでコードを書き換えなくていいというありきたりなものになるでしょうか。むしろエラー処理のほうが時間かかっている気がする。実際今回私のコードのエラー処理を分離するだけで350msくらい縮んでいます。
追記:うわ、typoしとる、なにがvench mark
じゃい!benchmark
だわ!戒めとして残しておきます。
追記:税務署でアルバイトしてみて
諸事情あって税務署で短期アルバイトしたんですが、まだまだマイナンバーの混乱は続いていますね~。とりあえずシステムくんだけどマニュアルなんてなかった的なアレ。あと、マイナンバー通知書だけ送ってきて(マイナンバーカードじゃないと本人証明にならない)身分証明書送ってこない人とか多かった。
マイナンバー導入後最初の確定申告が2017/3/15に終わり、電子証明書をほしいがためにマイナンバーカードを申請する人も一段落し、今ならそんなに時間がかからずにマイナンバーカードが手に入るんじゃないかなぁ・・・。
追記:個人情報保護委員会の言論弾圧に物申す
べつに「マイナンバー収集を誤認するようなページ」になっていなければ、入力欄を設置していてかまわないというべき。騙す輩が存在し得ることはまた別のこと。無用な萎縮は、田舎警察を思い上がらせることになるだけ。https://t.co/IBgZSkqDMH
— Hiromitsu Takagi (@HiromitsuTakagi) 2018年8月7日
誤解が広まるからという理由で政府がやめなさいと圧力をかけるのは、表現の自由に対する攻撃であり、見過ごしてはいけない。
— Hiromitsu Takagi (@HiromitsuTakagi) 2018年8月8日
今回のサイトは、 https://t.co/nrPtaInUBt の通り、「JavaScriptで書かれていますので,入力されたものはネットに流れません」と説明しており、誤認させるものではなかった。
というわけで、普通にJavaScriptで書くのはもうたくさんの人がやっている気がするので、C++で書いてWebassemblyに変換してブラウザ上で実行できるようにした。
マイナンバーのチェックデジットをWebassemblyで計算する
Webassembly初めて触ったけどC++からやるのだいぶだるいなぁという印象。