https://paiza.jp/poh/kirishima
> ※ 実際のプロジェクトではこの様には行きませんので、人員を増やす場合は慎重に検討する事をお勧めいたします。
1万円の下請けってどんなところなんだろうか。
まあ典型的なナップザック問題なので、さっくり解いてしまいましょう。
実に簡単ですね。
人数をキーにしたせいで動的計画法というより総当たりになってしまった気もしますがまあいいや。
さっそく実行。
あっさり合格しました。
めでたし。
まあ、ここに辿り着くまでに実は2回も失敗しているのですが。
http://paiza.jp/poh/kirishima/result/4f809703f962fdb735dd00dd83943b22
最初、何も考えずに『単価の安い順に足していく』という頭の悪すぎる実装をやってしまいテスト5で失敗。
10人でいいプロジェクトに単価の安い100人を送り込まれてもねえ。
http://paiza.jp/poh/kirishima/result/a5ec246afdb9c754e44f003bae62ab97
まじめに考えてきちんと動的計画法を適用したのに何故かテスト7だけ失敗。
その日は何処にも間違う要素無いだろうがーなんでだーと延々悩んで結局答えが出なかったのですが、翌日見直してみたら
$minTotal = 5000000;
とか書いてあって即死。
いやあこれは酷い。
さてこのアルゴリズム、テスト7では3秒以上かかっていますが、PHPで既に0.01秒というおかしな値が達成されています。
いったい果たしてどんな書き方がなされているのでしょうか。
> ※ 実際のプロジェクトではこの様には行きませんので、人員を増やす場合は慎重に検討する事をお勧めいたします。
1万円の下請けってどんなところなんだろうか。
まあ典型的なナップザック問題なので、さっくり解いてしまいましょう。
<?php
// 入力をパース
$input = file('php://stdin', FILE_IGNORE_NEW_LINES|FILE_SKIP_EMPTY_LINES);
// 1行目は必要人数
$ninzuu = (int)$input[0];
// 2行目は会社数 使わない
// $kaishasuu = (int)$input[1];
// 3行目以降は人数+価格 最大50社しかない
unset($input[0]);unset($input[1]);
$list = array_map(function($a){
// 0=>人数,1=>価格
$t=explode(' ', $a, 2);
return [(int)$t[0],(int)$t[1]];
}, $input);
// 動的計画法
$data = [0=>0];
foreach($list as $key1=>$val1){
// 1社で越えている場合は0にだけ足せばいい
if($val1[0]>=$ninzuu){
if(isset($data[$val1[0]])){
$data[$val1[0]] = min($data[$val1[0]], $val1[1]);
}else{
$data[$val1[0]] = $val1[1];
}
continue;
}
foreach($data as $key2=>$val2){
// 既に人数を越えている場合は計算不要
if($key2 >= $ninzuu){ continue; }
// 対象人数の金額を登録
$num = $key2+$val1[0];
if(isset($data[$num])){
// 既に値がある場合は安い方
$data[$num] = min($data[$num], $val2+$val1[1]);
}else{
$data[$num] = $val2+$val1[1];
}
}
}
// 最低人数越えのキーのうち、最低金額のものを選択
$minTotal = 250000000;
foreach($data as $key=>$val){
if($key >= $ninzuu && $val < $minTotal ){
$minTotal = $val;
}
}
print($minTotal . PHP_EOL);
普通に動的計画法を適用しただけです。実に簡単ですね。
人数をキーにしたせいで動的計画法というより総当たりになってしまった気もしますがまあいいや。
さっそく実行。
ようやく突破。ものすごくしょうもないところで詰まってた。 http://t.co/FEQmErTYki #paizahack_lite
— ラナ・クアール (@rana_kualu) 2014, 8月 1
http://paiza.jp/poh/kirishima/result/bebdc876df9e6cd24b4ee916a06eeea3 | Test case 1 | 通過 | 実行時間： 0.01 秒 |
| Test case 2 | 通過 | 実行時間： 0.01 秒 |
| Test case 3 | 通過 | 実行時間： 0.01 秒 |
| Test case 4 | 通過 | 実行時間： 0.01 秒 |
| Test case 5 | 通過 | 実行時間： 0.01 秒 |
| Test case 6 | 通過 | 実行時間： 0.27 秒 |
| Test case 7 | 通過 | 実行時間： 3.33 秒 |
あっさり合格しました。
めでたし。
まあ、ここに辿り着くまでに実は2回も失敗しているのですが。
とりあえず作ってみたらテスト5でコケた。 やはりいきなり突破は無理か。 http://t.co/M9KLP5vFf8 #paizahack_lite
— ラナ・クアール (@rana_kualu) 2014, 7月 30
http://paiza.jp/poh/kirishima/result/4f809703f962fdb735dd00dd83943b22
最初、何も考えずに『単価の安い順に足していく』という頭の悪すぎる実装をやってしまいテスト5で失敗。
10人でいいプロジェクトに単価の安い100人を送り込まれてもねえ。
本気で実装してみたが何故かテスト7に失敗。 http://t.co/Q65KNKOsDE タイムアウトやメモリオーバーならともかく間違い？意味がわからんぞ？？？ #paizahack_lite
— ラナ・クアール (@rana_kualu) 2014, 7月 31
http://paiza.jp/poh/kirishima/result/a5ec246afdb9c754e44f003bae62ab97
まじめに考えてきちんと動的計画法を適用したのに何故かテスト7だけ失敗。
その日は何処にも間違う要素無いだろうがーなんでだーと延々悩んで結局答えが出なかったのですが、翌日見直してみたら
$minTotal = 5000000;
とか書いてあって即死。
いやあこれは酷い。
さてこのアルゴリズム、テスト7では3秒以上かかっていますが、PHPで既に0.01秒というおかしな値が達成されています。
いったい果たしてどんな書き方がなされているのでしょうか。
PR
<?php
$date = new DateTime('2014/01/01 00:00:00', new DateTimeZone('Asia/Tokyo'));
$date->modify('first day of -1 second');
var_dump($date->format('Y-m-d H:i:s')); // 2013-12-31 23:59:59
var_dump($date->getTimestamp()); // 1385909999 → 2013-12-01 23:59:59
var_dump($date->format('Y-m-d H:i:s')); // 2013-12-01 23:59:59
何故か日付が変わっています。なんだこれ。
更に深刻なことにはDateTimeImmutableでも発生します。
<?php
$date = new DateTimeImmutable('2014/01/01 00:00:00');
$date2 = $date->modify('first day of -1 second');
var_dump($date2->format('Y-m-d H:i:s')); // 2013-12-31 23:59:59
var_dump($date2->getTimestamp()); // 1385909999 → 2013-12-01 23:59:59
var_dump($date2->format('Y-m-d H:i:s')); // 2013-12-01 23:59:59
あかんこれ。ポイントは'first day of -1 second'と複数の変更を一気に指定するところです。
$date->modify('first day of');
$date->modify('-1 second');
と分けて記述すると何故か発生しません。
また'-1 minute'や'-1 hour'では発生しますが'-1 day'や'+1 second'は正常に計算されます。
'first Saturday of next month -1 second'や'Monday next week -1 second'などでも発生しません。
'first day'や'last day'と一日以下のマイナス計算が入っているとバグる模様。
カレンダーを作ったときに見つけたのですが、意味がわからなかったので放置していたところ、先日バグレポートが上がっていました。
せっかくだから報告でもしてみればよかったかな。
このバグは、PHP5.6RC2の時点ではまだ修正されていません。
DateTime関連は何気にバグやバグだかなんだかわからない挙動があったりするので、使うときは気をつけないといけませんね。
【Smarty】配列のキーにハイフンを使ったらアウトらしい
http://qiita.com/seihowlow24/items/713e12c459fa47df7eb1
こういう記事がありました。
Smartyでは連想配列のキーに-を使用できないという問題です。
では何故使えないのかというのを少し調べてみたので記載。
使用したバージョンはSmarty3.1.19。
まあ言ってしまうとマイナスと区別が付かないからです。
index.php
index.html
{$hoge.a-1}は$hoge['a-1']ではなく$hoge['a']-1と解釈され、結果は「9」になります。
実際コンパイル後のファイルは
<?php echo $_smarty_tpl->tpl_vars['hoge']->value['a']-1;?>
となっています。
これはSmartyが演算をサポートするかぎりどうしようもないですね。
http://www.smarty.net/docs/ja/language.math.tpl
PHPの配列キーには他の演算子や記号や日本語なども大概入れられますが、Smartyテンプレートでは大半が使用できません。
$など使っただけでFatal errorが発生します。
index.php
index.html
<?php echo $_smarty_tpl->tpl_vars['hoge']->value['some']-'key';?>
$_smarty_tpl->tpl_vars['hoge']->value['some']は未定義なのでNULL - 'key'というよくわからない演算となり、結果は「0」となります。
当然Undefined indexのNoticeも発生します。
おっと、参考サイトと何故か結果が違ってますね。
参考サイトは『{$hoge['some-key']}と書けない』とか言ってるので、だいぶ古いバージョンだと思われます。
最近のバージョンでは{$hoge['some-key']}と問題なく書くことが可能です。
こちらであれば記号や日本語などの配列キーもそのまま使えるので、常にこちらの記法で書くとか決めてしまってもいいかもしれません。
ちなみに構文解析の実体はSMARTY_SYSPLUGINS_DIR.smarty_internal_templatelexer.phpあたりにありますが、
preg_match('/\G(\{\})|\G(\{\*([\S\s]*?)\*\})|\G(\{\s*strip\s*\})|\G(\{\s*\/strip\s*\})|\G(\{\s*literal\s*\})|\G(\{\s*(if|elseif|else if|while)\s+)|\G(\{\s*for\s+)|\G(\{\s*foreach(?![^\s]))|\G(\{\s*setfilter\s+)|\G(\{\s*\/)|\G(\{\s*)|\G(<\?(?:php\w+|=|[a-zA-Z]+)?)|\G(\?>)|\G(\s*\})|\G(<%)|\G(%>)|\G([\S\s])/iS', $contents);
うん、これ読むの無理。
これとかSmarty_Internal_Templateparserはいったい何なのか誰か教えて下さい。
http://qiita.com/seihowlow24/items/713e12c459fa47df7eb1
こういう記事がありました。
Smartyでは連想配列のキーに-を使用できないという問題です。
では何故使えないのかというのを少し調べてみたので記載。
使用したバージョンはSmarty3.1.19。
まあ言ってしまうとマイナスと区別が付かないからです。
index.php
<?php
$hoge = [
'a'=>10,
'a-1'=>5,
];
$smarty->assign('hoge', $hoge);
$smarty->display('index.html');
index.html
{$hoge.a-1}
{$hoge.a-1}は$hoge['a-1']ではなく$hoge['a']-1と解釈され、結果は「9」になります。
実際コンパイル後のファイルは
<?php echo $_smarty_tpl->tpl_vars['hoge']->value['a']-1;?>
となっています。
これはSmartyが演算をサポートするかぎりどうしようもないですね。
http://www.smarty.net/docs/ja/language.math.tpl
PHPの配列キーには他の演算子や記号や日本語なども大概入れられますが、Smartyテンプレートでは大半が使用できません。
$など使っただけでFatal errorが発生します。
index.php
<?php
$hoge = [ 'some-key'=>'val' ];
$smarty->assign('hoge', $hoge);
$smarty->display('index.html');
index.html
{$hoge.some-key}
コンパイル後。<?php echo $_smarty_tpl->tpl_vars['hoge']->value['some']-'key';?>
$_smarty_tpl->tpl_vars['hoge']->value['some']は未定義なのでNULL - 'key'というよくわからない演算となり、結果は「0」となります。
当然Undefined indexのNoticeも発生します。
おっと、参考サイトと何故か結果が違ってますね。
参考サイトは『{$hoge['some-key']}と書けない』とか言ってるので、だいぶ古いバージョンだと思われます。
最近のバージョンでは{$hoge['some-key']}と問題なく書くことが可能です。
こちらであれば記号や日本語などの配列キーもそのまま使えるので、常にこちらの記法で書くとか決めてしまってもいいかもしれません。
ちなみに構文解析の実体はSMARTY_SYSPLUGINS_DIR.smarty_internal_templatelexer.phpあたりにありますが、
preg_match('/\G(\{\})|\G(\{\*([\S\s]*?)\*\})|\G(\{\s*strip\s*\})|\G(\{\s*\/strip\s*\})|\G(\{\s*literal\s*\})|\G(\{\s*(if|elseif|else if|while)\s+)|\G(\{\s*for\s+)|\G(\{\s*foreach(?![^\s]))|\G(\{\s*setfilter\s+)|\G(\{\s*\/)|\G(\{\s*)|\G(<\?(?:php\w+|=|[a-zA-Z]+)?)|\G(\?>)|\G(\s*\})|\G(<%)|\G(%>)|\G([\S\s])/iS', $contents);
うん、これ読むの無理。
これとかSmarty_Internal_Templateparserはいったい何なのか誰か教えて下さい。
http://qiita.com/Nabetani/items/7ba11167ea28c929fcf2
http://nabetani.sakura.ne.jp/hena/ord23snakemoinc/
くねくね増加列
5*5のマス目から単調増加列を全て取り出した場合、最も長いものを探す。
極めてふつーに、伸ばせるところに手を伸ばしているだけです。
メモ化すら行っていないという手抜きっぷり。
まあ計算量が問題になるサイズではないからいいでしょう。
かかった時間は50分くらい。
ところで概ね毎回のことなんだが、他人の回答例を見てみても全く理解できぬ。
http://nabetani.sakura.ne.jp/hena/ord23snakemoinc/
くねくね増加列
5*5のマス目から単調増加列を全て取り出した場合、最も長いものを探す。
<?php
class SNAKEMOINC{
/**
* くねくね増加列
* @param String 「01224/82925/69076/32298/21065」みたいな文字列
* @return int 「6」みたいな数値
*/
public function get($input){
$input = str_replace('/', '', $input);
$tmp=[];
for($i=0;$i<strlen($input);$i++){
// 各升スタートでの最大長を取得
$tmp[] = $this->getMax($input, $i, 1);
}
// 一番長かった枝
return max($tmp);
}
/**
* 最長ルートを取得
* @param String input
* @param int 開始位置
* @param int 現在のルート長
* @return int 最大ルート長
*/
private function getMax($input, $pos, $loop){
$tmp=[$loop];
foreach($this->getLargeAdjacent($input, $pos) as $val){
$tmp[] = $this->getMax($input, $val, $loop+1);
}
return max($tmp);
}
/**
* 隣接4箇所のうち、自分より大きいところがあれば取得
* @param String input
* @param int 現在位置
* @return [] 隣接位置
*/
private function getLargeAdjacent($input, $pos){
$ret = [];
foreach($this->getAdjacent($pos) as $val){
if($input[$pos] < $input[$val]){
$ret[] = $val;
}
}
return $ret;
}
/**
* 隣接4箇所の位置を取得
* @param int 現在位置
* @return [] 隣接位置
*/
private function getAdjacent($pos){
if($pos>=5){ $ret[] = $pos-5; } // 上
if($pos<20){ $ret[] = $pos+5; } // 下
if($pos%5!==0){ $ret[] = $pos-1; } // 左
if($pos%5!==4){ $ret[] = $pos+1; } // 右
return $ret;
}
}
// テスト
$test = [
['01224/82925/69076/32298/21065', '6'],
/* 省略 */
];
$snakemoinc = new SNAKEMOINC();
foreach($test as $key=>$data){
$answer = $snakemoinc->get($data[0]);
if($answer !== (int)$data[1]){
print('えらー');
}
}
極めてふつーに、伸ばせるところに手を伸ばしているだけです。
メモ化すら行っていないという手抜きっぷり。
まあ計算量が問題になるサイズではないからいいでしょう。
かかった時間は50分くらい。
ところで概ね毎回のことなんだが、他人の回答例を見てみても全く理解できぬ。
ArrayIteratorは、ソート中に自分自身を変更することはできません。
まあ普通は、ソート中に中身を書き換えられたらすごく困りますね。
ところで何となくJVNを見ていたらJVNDB-2014-003302、CVE-2014-4698というものを発見しました。
http://jvndb.jvn.jp/ja/contents/2014/JVNDB-2014-003302.html
https://bugs.php.net/bug.php?id=67539
解放して、もう使わなくなったはずのメモリにアクセスしてしまうバグだそうです。
場合によってはサービス運用妨害に至るそうです。
これはバッファオーバーランなのかな？
2014/06/29に発見され、2014/07/02に修正されています。
当然PHP5.6.0RC2の時点では修正されていません。
エラーは出ませんが、実はC言語レベルでは不正なメモリ読み出しが発生しています。
そのあたりはMemcheckで確認可能です。
あとはArrayIteratorの中身をうまいこと書き換えれば、メモリの不正な読み出し箇所にコードを忍ばせて何か攻撃できるかもしれません。
が、そのあたりは詳しくないので具体的にどのようにすればいいかはよくわかりません。
というか、そもそもソート中に中身を書き換えるようなソースを書く方が悪いだろこれ。
JVNでの深刻度は4.6ですが、本当にこれで影響を受けるシステムが存在するのか疑問に思うレベル。
ちなみに
意味がわからぬ。
まあ普通は、ソート中に中身を書き換えられたらすごく困りますね。
<?php
$arrayIterator = new ArrayIterator(['A','B']);
$GLOBALS['arrayIterator'][0] = 'C'; // 問題なし
// ソート中に中身を変更
function badsort($a, $b) {
$GLOBALS['arrayIterator'][0] = 'D';
return $a > $b;
}
$arrayIterator->uksort('badsort'); // Warning: Modification of ArrayObject during sorting is prohibited
Warningが発生し、中身の変更は拒否されます。ところで何となくJVNを見ていたらJVNDB-2014-003302、CVE-2014-4698というものを発見しました。
http://jvndb.jvn.jp/ja/contents/2014/JVNDB-2014-003302.html
https://bugs.php.net/bug.php?id=67539
解放して、もう使わなくなったはずのメモリにアクセスしてしまうバグだそうです。
場合によってはサービス運用妨害に至るそうです。
これはバッファオーバーランなのかな？
2014/06/29に発見され、2014/07/02に修正されています。
当然PHP5.6.0RC2の時点では修正されていません。
<?php
$arrayIterator = new ArrayIterator(['A','B']);
// ソート中にunserialize
function badsort($a, $b) {
$GLOBALS['it']->unserialize($GLOBALS['it']->serialize());
return $a > $b;
}
$a->uksort('badsort'); // エラーは出ない
unserializeだとエラーが発生せずに中身が書き換えられます。エラーは出ませんが、実はC言語レベルでは不正なメモリ読み出しが発生しています。
そのあたりはMemcheckで確認可能です。
あとはArrayIteratorの中身をうまいこと書き換えれば、メモリの不正な読み出し箇所にコードを忍ばせて何か攻撃できるかもしれません。
が、そのあたりは詳しくないので具体的にどのようにすればいいかはよくわかりません。
というか、そもそもソート中に中身を書き換えるようなソースを書く方が悪いだろこれ。
JVNでの深刻度は4.6ですが、本当にこれで影響を受けるシステムが存在するのか疑問に思うレベル。
ちなみに
<?php
$arrayIterator = new ArrayIterator(['A','B']);
// ソート中にunserializeで中身を入れ替え
function badsort($a, $b) {
$d = new ArrayIterator(['C','D']);
$e = $d->serialize();
$GLOBALS['arrayIterator']->unserialize($e);
return $a > $b;
}
$a->uksort('badsort');
// ソート中に$arrayIteratorを直接変更
function badsort2($a, $b) {
$GLOBALS['arrayIterator'] = new ArrayIterator(['C','D']);
return $a > $b;
}
$arrayIterator->uksort('badsort2');
このように書くと書き換えができるうえに不正なメモリ読み出しも発生しません。意味がわからぬ。
http://www.php.net/manual/ja/function.gmp-nextprime.php
前エラトステネスの篩で素数を求めたのですが、普通に標準関数に存在していました。
なんでもありだなPHP。
ということで速度はそれなり、メモリ使用量はずっと少ない、そして見た目が圧倒的に簡単という結果になりました。
どうしても速度をひたすら追求しなければならないんだ、なんて時以外はgmp_nextprime()を使っておけば十分でしょう。
というか速度が必要なら他の言語を使え。
前エラトステネスの篩で素数を求めたのですが、普通に標準関数に存在していました。
なんでもありだなPHP。
<?php
// GMPを使ったエラトステネスの篩
// 初期値
$max = 1000000;
$now = 1;
$prime = '';
// 素数を求める
while(($now = gmp_nextprime($now)) < $max){
$prime .= $now.PHP_EOL;
}
// 出力
echo $prime;
| ファイル名 | 10000件時間(秒) | 1000件メモリ(kb) | 1000000件時間(秒) | 1000000件メモリ(kb) |
|---|---|---|---|---|
| katsurayama_sosu.php | 0.00400043 | 134.38 | 1.78117800 | 1362.41 |
| maeda_sosu.php | 0.30502999 | 991.88 | Maximum execution time of 180 seconds exceeded | |
| sosu_sample.php | 2.81178141 | 992.17 | Maximum execution time of 180 seconds exceeded | |
| tanaka_sosu.php | 0.00449991 | 248.15 | 0.99830055 | 8166.82 |
| NurseAngel ArrayIterator | 0.00450063 | 993.30 | 0.48954952 | 84322.09 |
| NurseAngel str_repeat | 0.00250053 | 145.05 | 0.19101894 | 2363.26 |
| NurseAngel gmp_nextprime | 0.01266773 | 136.09 | 0.96109605 | 1361.86 |
ということで速度はそれなり、メモリ使用量はずっと少ない、そして見た目が圧倒的に簡単という結果になりました。
どうしても速度をひたすら追求しなければならないんだ、なんて時以外はgmp_nextprime()を使っておけば十分でしょう。
というか速度が必要なら他の言語を使え。
RFC6570というRFCがあります。
http://tools.ietf.org/html/rfc6570
簡単に言うと、
『http://example.com/{controller}/{action}』を『http://example.com/hoge/fuga』に展開できたら楽じゃね、という最近のフレームワークでよく見かけるルーティングをRFCに仕上げたものです。
フレームワークならだいたい最初から付属しているし、自力で作るにしても簡単なのならSmartyなりZend\Uri\Uriなりで十分ですが、RFC6570に沿ったエクステンションがあったので試してみます。
使用したバージョンは1.0です。
RFC6570には4段階のレベルがありますが、uri_templateは全レベル対応しています。
完全にRFC6570に従ったURIを出力しました。
これでURIを組み立てるのが便利に…なるのか？
普通にrawurlencodeとか使った方が早い気がしないでもない。
http://tools.ietf.org/html/rfc6570
簡単に言うと、
『http://example.com/{controller}/{action}』を『http://example.com/hoge/fuga』に展開できたら楽じゃね、という最近のフレームワークでよく見かけるルーティングをRFCに仕上げたものです。
フレームワークならだいたい最初から付属しているし、自力で作るにしても簡単なのならSmartyなりZend\Uri\Uriなりで十分ですが、RFC6570に沿ったエクステンションがあったので試してみます。
使用したバージョンは1.0です。
<?php
// 変換テーブル
$table = [
'var' => 'value',
'hello' => 'Hello World!',
'path' => '/foo/bar',
'empty' => '',
'x' => '1024',
'y' => '768',
'list' => ['red', 'green', 'blue'],
'keys' => ['semi'=>';','dot'=>'.','comma'=>','],
];
// レベル1
$level1 = [
'{var}' => 'value',
'{hello}' => 'Hello%20World%21',
];
// レベル2
$level2 = [
'{+var}' => 'value',
'{+hello}' => 'Hello%20World!',
'{+path}/here' => '/foo/bar/here',
'here?ref={+path}'=>'here?ref=/foo/bar',
'X{#var}'=>'X#value',
'X{#hello}'=>'X#Hello%20World!',
];
// レベル3
$level3 = [
'map?{x,y}' => 'map?1024,768',
'{x,hello,y}' => '1024,Hello%20World%21,768',
'{+x,hello,y}' => '1024,Hello%20World!,768',
'{+path,x}/here' => '/foo/bar,1024/here',
'{#x,hello,y}' => '#1024,Hello%20World!,768',
'{#path,x}/here' => '#/foo/bar,1024/here',
'X{.var}' => 'X.value',
'X{.x,y}' => 'X.1024.768',
'{/var}' => '/value',
'{/var,x}/here' => '/value/1024/here',
'{;x,y}' => ';x=1024;y=768',
'{;x,y,empty}' => ';x=1024;y=768;empty',
'{?x,y}' => '?x=1024&y=768',
'{?x,y,empty}' => '?x=1024&y=768&empty=',
'?fixed=yes{&x}' => '?fixed=yes&x=1024',
'{&x,y,empty}' => '&x=1024&y=768&empty=',
];
// レベル4
$level4 = [
'{var:3}' => 'val',
'{var:30}' => 'value',
'{list}' => 'red,green,blue',
'{list*}' => 'red,green,blue',
'{keys}' => 'semi,%3B,dot,.,comma,%2C',
'{keys*}' => 'semi=%3B,dot=.,comma=%2C',
'{+path:6}/here' => '/foo/b/here',
'{+list}' => 'red,green,blue',
'{+list*}' => 'red,green,blue',
'{+keys}' => 'semi,;,dot,.,comma,,',
'{+keys*}' => 'semi=;,dot=.,comma=,',
'{#path:6}/here' => '#/foo/b/here',
'{#list}' => '#red,green,blue',
'{#list*}' => '#red,green,blue',
'{#keys}' => '#semi,;,dot,.,comma,,',
'{#keys*}' => '#semi=;,dot=.,comma=,',
'X{.var:3}' => 'X.val',
'X{.list}' => 'X.red,green,blue',
'X{.list*}' => 'X.red.green.blue',
'X{.keys}' => 'X.semi,%3B,dot,.,comma,%2C',
'X{.keys*}' => 'X.semi=%3B.dot=..comma=%2C',
'{/var:1,var}' => '/v/value',
'{/list}' => '/red,green,blue',
'{/list*}' => '/red/green/blue',
'{/list*,path:4}' => '/red/green/blue/%2Ffoo',
'{/keys}' => '/semi,%3B,dot,.,comma,%2C',
'{/keys*}' => '/semi=%3B/dot=./comma=%2C',
'{;hello:5}' => ';hello=Hello',
'{;list}' => ';list=red,green,blue',
'{;list*}' => ';list=red;list=green;list=blue',
'{;keys}' => ';keys=semi,%3B,dot,.,comma,%2C',
'{;keys*}' => ';semi=%3B;dot=.;comma=%2C',
'{?var:3}' => '?var=val',
'{?list}' => '?list=red,green,blue',
'{?list*}' => '?list=red&list=green&list=blue',
'{?keys}' => '?keys=semi,%3B,dot,.,comma,%2C',
'{?keys*}' => '?semi=%3B&dot=.&comma=%2C',
'{&var:3}' => '&var=val',
'{&list}' => '&list=red,green,blue',
'{&list*}' => '&list=red&list=green&list=blue',
'{&keys}' => '&keys=semi,%3B,dot,.,comma,%2C',
'{&keys*}' => '&semi=%3B&dot=.&comma=%2C',
];
// 確認
$level = array_merge($level1, $level2, $level3, $level4);
foreach($level as $key=>$val){
// 変換
$template = uri_template($key, $table);
if($template !== $val){
print('えらー');
}
}
エラーは出ません。RFC6570には4段階のレベルがありますが、uri_templateは全レベル対応しています。
完全にRFC6570に従ったURIを出力しました。
これでURIを組み立てるのが便利に…なるのか？
普通にrawurlencodeとか使った方が早い気がしないでもない。
その1 / その2 / その3
日本語化
$ vi /etc/sysconfig/i18n
#LANG="en_US.utf8"
LANG="ja_JP.utf8"
en_USをja_JPに変更。
再起動。
「標準フォルダの名前を現在の言語に合わせて更新しますか？」には「古い名前のままにする」を選択。
X Windowが日本語になっていることを確認。
WinSCPでログイン
プロトコルSFTP、ホスト名192.168.33.10、ポート番号20、IDとパスワードはvagrant。
普通に入れる。
デフォルトではDocumentRootの編集権限がないので、
root/vagrantでも入れる。
公開サーバならPermitRootLogin noのするところだが、ローカルなので特に制限しない。
PHPを更新
CentOSデフォルトのPHPは5.3なので、最新版に更新する。
remiに早くもPHP5.6ができてたので、そちらを見るようにする。
# yum remove php*
# wget http://rpms.famillecollet.com/enterprise/remi-release-6.rpm
# wget http://ftp.iij.ad.jp/pub/linux/fedora/epel/6/i386/epel-release-6-8.noarch.rpm
# rpm -Uvh remi-release-6.rpm
# rpm -Uvh epel-release-6-8.noarch.rpm
インストールを実行
# yum install --enablerepo=remi --enablerepo=remi-php56 php
# service httpd restart
これでPHP5.6がインストールされる。
PHP5.6.0RC1だった。はええよ。
ただ必要最低限しか入れていないため、mbstringすらない。
$ yum list --enablerepo=remi > hoge
とかやってリストから必要なパッケージを選択する。
remiにはPHPだけではなくPEARとかPECLとかSmartyとかSymfonyとかphpMyAdminまで入ってる。いみわからん。
とりあえずこんなかんじで選択。
# yum install --enablerepo=remi --enablerepo=remi-php56 php php-common php-cli php-pdo php-mysql php-devel php-gd php-bcmath php-pecl-apc php-pecl-imagick php-pecl-hrtime php-pecl-spl-types php-tidy php-mbstring php-mcrypt
gitをインストール
# yum install curl-devel expat-devel gettext-devel openssl-devel zlib-devel
# yum install git
$ git config --global user.name NurseAngel
$ git config --global user.email hoge@example.com
現状を保存
いつでもこの時点に戻せるように、現在のサーバ状態を保存する。
> vagrant package
> vagrant box add centos_65_32_php56 package.box
> vagrant init centos_65_32_php56
> * Vagrantfile編集
> vagrant up
vagrant packageで現在の状態がpackage.boxに保存される。
> vagrant destroy
> vagrant up
でpackage時点に戻る。
==> default: Configuring and enabling network interfaces...
The following SSH command responded with a non-zero exit status.
Vagrant assumes that this means the command failed!
ARPCHECK=no /sbin/ifup eth1 2> /dev/null
Stdout from the command:
Stderr from the command:
戻らなかった。
なんかエラーにが出る。
192.168.33.10のIPアドレスが割り振られない。
http://www.absolute-keitarou.net/blog/?p=583
vagrant package前に対応しないといけないらしい。
$ sudo ln -s -f /dev/null /etc/udev/rules.d/70-persistent-net.rules
> vagrant halt
> * package.boxを削除
> vagrant package
> vagrant box remove centos_65_32_php56
> vagrant box add centos_65_32_php56 package.box
> vagrant init centos_65_32_php56
> * Vagrantfile編集
> vagrant up
これで正常にIPアドレスが割り振られるようになった。
完成
とりあえずPHPが自由に使えるサーバができた。
これで無事、やりたいことがやれるようになる。
が、特にやりたいことがなかった。
日本語化
$ vi /etc/sysconfig/i18n
#LANG="en_US.utf8"
LANG="ja_JP.utf8"
en_USをja_JPに変更。
再起動。
「標準フォルダの名前を現在の言語に合わせて更新しますか？」には「古い名前のままにする」を選択。
X Windowが日本語になっていることを確認。
WinSCPでログイン
プロトコルSFTP、ホスト名192.168.33.10、ポート番号20、IDとパスワードはvagrant。
普通に入れる。
デフォルトではDocumentRootの編集権限がないので、
root/vagrantでも入れる。
公開サーバならPermitRootLogin noのするところだが、ローカルなので特に制限しない。
PHPを更新
CentOSデフォルトのPHPは5.3なので、最新版に更新する。
remiに早くもPHP5.6ができてたので、そちらを見るようにする。
# yum remove php*
# wget http://rpms.famillecollet.com/enterprise/remi-release-6.rpm
# wget http://ftp.iij.ad.jp/pub/linux/fedora/epel/6/i386/epel-release-6-8.noarch.rpm
# rpm -Uvh remi-release-6.rpm
# rpm -Uvh epel-release-6-8.noarch.rpm
インストールを実行
# yum install --enablerepo=remi --enablerepo=remi-php56 php
# service httpd restart
これでPHP5.6がインストールされる。
PHP5.6.0RC1だった。はええよ。
ただ必要最低限しか入れていないため、mbstringすらない。
$ yum list --enablerepo=remi > hoge
とかやってリストから必要なパッケージを選択する。
remiにはPHPだけではなくPEARとかPECLとかSmartyとかSymfonyとかphpMyAdminまで入ってる。いみわからん。
とりあえずこんなかんじで選択。
# yum install --enablerepo=remi --enablerepo=remi-php56 php php-common php-cli php-pdo php-mysql php-devel php-gd php-bcmath php-pecl-apc php-pecl-imagick php-pecl-hrtime php-pecl-spl-types php-tidy php-mbstring php-mcrypt
gitをインストール
# yum install curl-devel expat-devel gettext-devel openssl-devel zlib-devel
# yum install git
$ git config --global user.name NurseAngel
$ git config --global user.email hoge@example.com
現状を保存
いつでもこの時点に戻せるように、現在のサーバ状態を保存する。
> vagrant package
> vagrant box add centos_65_32_php56 package.box
> vagrant init centos_65_32_php56
> * Vagrantfile編集
> vagrant up
vagrant packageで現在の状態がpackage.boxに保存される。
> vagrant destroy
> vagrant up
でpackage時点に戻る。
==> default: Configuring and enabling network interfaces...
The following SSH command responded with a non-zero exit status.
Vagrant assumes that this means the command failed!
ARPCHECK=no /sbin/ifup eth1 2> /dev/null
Stdout from the command:
Stderr from the command:
戻らなかった。
なんかエラーにが出る。
192.168.33.10のIPアドレスが割り振られない。
http://www.absolute-keitarou.net/blog/?p=583
vagrant package前に対応しないといけないらしい。
$ sudo ln -s -f /dev/null /etc/udev/rules.d/70-persistent-net.rules
> vagrant halt
> * package.boxを削除
> vagrant package
> vagrant box remove centos_65_32_php56
> vagrant box add centos_65_32_php56 package.box
> vagrant init centos_65_32_php56
> * Vagrantfile編集
> vagrant up
これで正常にIPアドレスが割り振られるようになった。
完成
とりあえずPHPが自由に使えるサーバができた。
これで無事、やりたいことがやれるようになる。
が、特にやりたいことがなかった。
http://qiita.com/sakana_kirai/items/6e512f7aea2898a6e8f2
http://qiita.com/mpyw/items/939964377766a54d4682
アップロードされたファイルについて、getimagesize()やfinfo::file()でMIMEタイプを判定しています。
まあMIMEタイプがimage/gifだとわかったので、ファイルは見えないところに隠しておいて、出力時にきちんとContent-Typeヘッダを出してあげれば問題ありません。
お、おう。
これはIEでのみ発生する可能性のあるXSSです。
IEは設定されたContent-Typeをあまり気にせず、ファイルの中身を見て適切な形式で出力してくれるという素敵極まりない機能が付いています。
で、IEは「GIF8」をgifとはみなさず、後続のHTMLを見てHTMLと判断してくれやがるようです。
「GIF87」にすると画像と判断されます。
X-Content-Type-OptionsというHTTPヘッダによって、この余計で傍迷惑な機能を止めることができます。
http://d.hatena.ne.jp/hasegawayosuke/20110106/p1
http://blog.everqueue.com/chiba/2011/01/06/484/
結果としては、とりあえずあらゆる出力にX-Content-Type-Optionsを書いとけ、というところでしょうか。
ちなみに
http://d.hatena.ne.jp/hasegawayosuke/20110106/p1
> あらゆるコンテンツのレスポンスヘッダに X-Content-Type-Options: nosniff を付与するようにしましょう
とか書いてるこのページにはX-Content-Type-Optionsが設定されていません。
http://qiita.com/mpyw/items/939964377766a54d4682
アップロードされたファイルについて、getimagesize()やfinfo::file()でMIMEタイプを判定しています。
<?php
// hoge.pngを判定
$imagesize = getimagesize('path/to/hoge.png');
$finfo = new finfo(FILEINFO_MIME_TYPE);
$finfofile = $finfo->file('path/to/hoge.png');
var_dump($imagesize, $finfofile);
ここでhoge.pngの中身を以下のように書き換えてみます。 GIF8<script>alert("xss");</script>
結果。array(6) {
[0]=>
int(29283)
[1]=>
int(28777)
[2]=>
int(1)
[3]=>
string(28) "width="29283" height="28777""
["channels"]=>
int(3)
["mime"]=>
string(9) "image/gif"
}
string(9) "image/gif"
なんと頭に「GIF8」と書いておくだけでMIMEタイプの判定をすり抜けてしまいました。まあMIMEタイプがimage/gifだとわかったので、ファイルは見えないところに隠しておいて、出力時にきちんとContent-Typeヘッダを出してあげれば問題ありません。
<?php
header('Content-type: image/gif');
readfile('path/to/hoge.png');
これで完璧！お、おう。
これはIEでのみ発生する可能性のあるXSSです。
IEは設定されたContent-Typeをあまり気にせず、ファイルの中身を見て適切な形式で出力してくれるという素敵極まりない機能が付いています。
で、IEは「GIF8」をgifとはみなさず、後続のHTMLを見てHTMLと判断してくれやがるようです。
「GIF87」にすると画像と判断されます。
X-Content-Type-OptionsというHTTPヘッダによって、この余計で傍迷惑な機能を止めることができます。
http://d.hatena.ne.jp/hasegawayosuke/20110106/p1
http://blog.everqueue.com/chiba/2011/01/06/484/
<?php
header('Content-type: image/gif');
header('X-Content-Type-Options: nosniff');
readfile('hoge.png');
これでIEでもXSSが発生しないようになります。結果としては、とりあえずあらゆる出力にX-Content-Type-Optionsを書いとけ、というところでしょうか。
ちなみに
http://d.hatena.ne.jp/hasegawayosuke/20110106/p1
> あらゆるコンテンツのレスポンスヘッダに X-Content-Type-Options: nosniff を付与するようにしましょう
とか書いてるこのページにはX-Content-Type-Optionsが設定されていません。
その1 / その2 / その3
X Windowをインストール
ウィンドウが1枚しかないと不便なのでX Windowをインストールする。
http://qiita.com/snaka/items/4fc6f83022e01daea58a
$ sudo yum groupinstall -y "Desktop" "Desktop Platform" "X Window System" "Fonts" "Japanese Support"
$ sudo yum install vnc-server
"が『：』のキーに割り振られてて、:が『Shift+;』になってて超使いにくい。
keyconfigでは何故か直せなかった。
> vagrant reload
$ startx
無事GUIが起動した。
この後System→Preferences→Keyboardでキーボードを直すことができた。
ApacheとPHPをインストール
$ sudo yum -y install httpd
$ sudo yum -y groupinstall "PHP support"
$ sudo service httpd start
何の問題もなくインストール完了。
iptables
80番ポートが塞がれているので許可する。
$ sudo vi /etc/sysconfig/iptables
-A INPUT -m state --state NEW -m tcp -p tcp --dport 80 -j ACCEPT
-A INPUT -m state --state NEW -m tcp -p tcp --dport 443 -j ACCEPT
2行を追加。
iptablesとApacheを再起動。Apacheはいらないかも。
$ sudo service iptables restart
$ sudo service httpd restart
ブラウザに
http://192.168.33.10/
でApacheにアクセス成功。
何故デフォルトが33.10かは不明。
自動起動設定
X WindowやApacheを自動起動するようにしておく。
$ sudo chkconfig httpd on
$ sudo vi /etc/inittab
id:3となってるところをid:5に変更。
再起動。
自動的にX Windowが起動し、192.168.33.10にアクセスできることを確認。
OSの更新
X Windowの右上あたりにある星みたいなマークをクリックするとアップデート情報が表示される。
30件出てきたが、よくわからないのでとりあえず全てInstall Updateしておいた。
まあ古いよりは新しい方がいいだろう。
VirtureBox Guest Additionsをインストール
現時点ではクリップボードやドラッグドロップを双方向にしてもコピペができない。
不便なのでどうにかする。
ホストOS(Windows側)のVirtualBoxの「デバイス」→「Guest AdditionsのCDイメージ挿入」
ゲストOSでCDが自動起動するのでインストール。
『4.3.12』だった。
何もせずともインストール完了。
なんか
Removing installed version 4.2.16 of VirtualBox Guest Additions
とか出てきたので実は要らなかったかもしれない。
で、インストールは完了したけどコピペできなかった。何故？
X Windowをインストール
ウィンドウが1枚しかないと不便なのでX Windowをインストールする。
http://qiita.com/snaka/items/4fc6f83022e01daea58a
$ sudo yum groupinstall -y "Desktop" "Desktop Platform" "X Window System" "Fonts" "Japanese Support"
$ sudo yum install vnc-server
"が『：』のキーに割り振られてて、:が『Shift+;』になってて超使いにくい。
keyconfigでは何故か直せなかった。
> vagrant reload
$ startx
無事GUIが起動した。
この後System→Preferences→Keyboardでキーボードを直すことができた。
ApacheとPHPをインストール
$ sudo yum -y install httpd
$ sudo yum -y groupinstall "PHP support"
$ sudo service httpd start
何の問題もなくインストール完了。
iptables
80番ポートが塞がれているので許可する。
$ sudo vi /etc/sysconfig/iptables
-A INPUT -m state --state NEW -m tcp -p tcp --dport 80 -j ACCEPT
-A INPUT -m state --state NEW -m tcp -p tcp --dport 443 -j ACCEPT
2行を追加。
iptablesとApacheを再起動。Apacheはいらないかも。
$ sudo service iptables restart
$ sudo service httpd restart
ブラウザに
http://192.168.33.10/
でApacheにアクセス成功。
何故デフォルトが33.10かは不明。
自動起動設定
X WindowやApacheを自動起動するようにしておく。
$ sudo chkconfig httpd on
$ sudo vi /etc/inittab
id:3となってるところをid:5に変更。
再起動。
自動的にX Windowが起動し、192.168.33.10にアクセスできることを確認。
OSの更新
X Windowの右上あたりにある星みたいなマークをクリックするとアップデート情報が表示される。
30件出てきたが、よくわからないのでとりあえず全てInstall Updateしておいた。
まあ古いよりは新しい方がいいだろう。
VirtureBox Guest Additionsをインストール
現時点ではクリップボードやドラッグドロップを双方向にしてもコピペができない。
不便なのでどうにかする。
ホストOS(Windows側)のVirtualBoxの「デバイス」→「Guest AdditionsのCDイメージ挿入」
ゲストOSでCDが自動起動するのでインストール。
『4.3.12』だった。
何もせずともインストール完了。
なんか
Removing installed version 4.2.16 of VirtualBox Guest Additions
とか出てきたので実は要らなかったかもしれない。
で、インストールは完了したけどコピペできなかった。何故？
