タグ

AlgorithmとLinuxに関するclavierのブックマーク (5)

  • spliceを使って高速・省メモリでGzipからZIPを作る - knqyf263's blog

    良い話を含むので概要の最初だけでも読んでもらえると幸いです。この話が実用的かと言うと多分全然実用的ではないので理解しても仕方ないかなと言う気がします。 概要 ファイルフォーマット gzip 10-byteのヘッダ 拡張ヘッダ ファイル体 フッタ(trailer) zip ローカルファイルヘッダ Data descriptor セントラルディレクトリエントリ セントラルディレクトリの終端レコード gzipからzipへの変換 gzipヘッダの処理 gzipファイル体の処理 gzip trailerの処理 複数gzipファイルの連結 PoC まとめ 概要 先日Dirty PipeというLinuxカーネルの脆弱性が公表されました。 dirtypipe.cm4all.com この脆弱性の原理自体も面白いのですが、その前に報告者の組織で行っているGzipZIPの処理で引っかかったのでまず先にそち

    spliceを使って高速・省メモリでGzipからZIPを作る - knqyf263's blog
  • Linuxカーネルのコードを読んで勉強になったこと - φ(・・*)ゞ ウーン カーネルとか弄ったりのメモ

    Linuxカーネルのコードを読んでて、なるほど〜と思うことはよくあるけど、その中でも特に今までの考え方をぶち壊してくれたのはなんだっけと思ったところ、やっぱりリスト構造かなと言うところ。 c言語でリスト構造を作る場合、一般的な教科書方式だと↓のようにデータとnextポインタは密結合になってると思います。これの場合、struct foobarのポインタをnext要素に使っているので、他の構造体(例えば、struct hogehoge)で同じことをしようとすると、その構造体ではstruct hogehoge *nextというメンバ変数を持つ必要があります。 ヘッド要素はstruct foobarです。 struct foobar { int n; char s[64]; struct foobar *next; }; struct foobar head; Linuxカーネルの場合、データとリ

    Linuxカーネルのコードを読んで勉強になったこと - φ(・・*)ゞ ウーン カーネルとか弄ったりのメモ
  • いまさらgrepが10倍高速化したのはなぜか – はむかず!

    最近GNU grepコマンドの最新バージョンがリリースされ、速度が10倍になったとのアナウンスがあった。それを聞いて、なんであんな枯れた技術に10倍もの高速化の余地があったのだろうと不思議に思った人も多いだろう。 ニュース記事:grepコマンド最新版、”-i”で10倍の高速化 家のリリースノート:grep – News: grep-2.17 released [stable] 今回のリリースでは正確には、マルチバイトロケールで、-iオプション(–ignore-case、つまり大文字小文字を区別しないオプション)をオンにした時の速度が10倍くらいになったそうだ。 なぜそんなに速くなったのか?逆を言えば今までなぜそんなに遅かったのか? そもそも、多くの日人にとって「大文字小文字の区別」というと英語のアルファベットか、せいぜいフランス語とかドイツ語とかのアクサン記号・ウムラウトがついたものく

  • ImageMagick 改造入門 (その参) 減色処理後編 | GREE Engineering

    こんにちは。クライアント基盤チームのよやです。 減色処理の話の続きで、ImageMagick の改造についてお話します。 前回 > ImageMagick 改造入門 (その弐) 減色処理前編 ImageMagick 減色処理の3つのフェーズのうち2つ目にあたる「RGB 空間で分割された立方体の統合処理」で特に時間がかかっていたので、少し手を加えて高速化しました。 前回のこの図に相当する処理です。 ImageMagick の既存の処理 前回、説明した「RGB 空間で分割された立方体の統合処理」のより細かい解説です。 統合処理の詳細 既存の ImageMagick の減色処理では、quantize_error の小さい順にRGB色空間内の立方体を削除して、それらのひとつ親の立方体に統合する処理を繰り返します。 対応コード (magick/quantize.c) 望みの色数になるまで繰り返す (

    ImageMagick 改造入門 (その参) 減色処理後編 | GREE Engineering
  • VOYAGE GROUP エンジニアブログ : Linuxカーネルのlist, rbtree, sortを使ってみた!

    2012年12月21日10:40 カテゴリ Linuxカーネルのlist, rbtree, sortを使ってみた! ※ このエントリーは、VOYAGE GROUPエンジニアblog Advent Calendarの12/21分です。 こんにちは、VGエンジニアのポール(@pank7)です。 多分知ってる人はいらっしゃいますが、半年前にvgtechブログを書いた際にはまだ日語がまだダメなので、英語で書きました。今回はできるだけ頑張って日語で書きます。ご指導よろしくお願いいたします。 何を書きますか 私が書ける言語はそんな多くないですけど、普段自分が好きな言語だといえば、C言語はその中の1つです。Cのメリットとしてはやはり多いと思います。シンプルや移植性が良いや効率的やUNIX系OSと仲良いなどというのがあります。でも今の仕事で使っている言語のPHPPerlPython、Shellとか

  • 1