はてなブックマーク

参照: http://www.unicode.org/versions/Unicode6.0.0/ch03.pdf の "Table 3-7. Well-Formed UTF-8 Byte Sequences" アルゴリズムを理解する上で重要なUTF-8の特徴について述べます。 1コードポイントは1-4バイトのシーケンスで表現される 上位ニブル（1バイト8ビットのうち、上位4ビット）を確認することでシーケンスの情報が得られる そのバイトがシーケンス先頭バイトかどうかわかる もしそれがシーケンス先頭バイトだったなら、何バイトのシーケンスかわかる 先頭でないバイトは基本的に0x80..0xBFの範囲が許容されているが、何箇所か例外があるのでそれもバリデーションしなければならない 例外の箇所は表では太字で示した 例えば、表を見て分かるように、先頭バイトが0xE0のとき2バイト目は0xA0..0x

この記事でお題にするのはCPUレジスタ上の整数除算です。以下、単に除算とも書きます。 除算は非常に高コストな演算なため、コンパイラは最適化によって、できるだけ整数除算を別の計算に置き換えようとします。 最適化ができる場合の一つとして、割る数が定数である場合があります。頭のいいコンパイラは、除算を乗算とビットシフト等を駆使した演算に置き換えます。この記事では、そういった最適化の背景にある理屈を部分的に解説します。 計算機環境としてはモダンなx86 CPUを仮定します。したがってレジスタは32/64ビットであり、負数は2の補数表現になっています。ある程度は他の命令セットでも通用する話になっているかもしれません。 そもそも整数の除算とは プログラミングにおける整数の除算の定義について確認します。整数$n$を整数$d$で割るとき $$ n = q \times d + r $$ が成り立つように除

Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article?

この記事で紹介するのは高スループットなBase64エンコードの実装方法です。 Base64は、Webの世界を始めとして、世界中さまざまな箇所で使われているエンコード方式です。とてもよく使われるので、高速化についてもしばしば研究されてきたようです。 高速化の最新成果として、2019年10月に、Wojciech Muła, Daniel Lemireによる新しい論文がarxivに投稿されました。なかなか強烈なタイトルが付いています。 Base64 encoding and decoding at almost the speed of a memory copy 論文の主張としては、x86 CPUの持つ最新の命令群を駆使することで、非常に高効率なBase64エンコード・デコードが実現できたというものです。このQiita記事では論文の内容の一部を紹介します。 Base64は問題としては単純に見え

Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article?

UTF-8文字列からコードポイント数を計算するアルゴリズムについて紹介します。コードポイント数カウントは、シンプルに書くのはそれほど難しくないものの、高効率な実装は意外にややこしいです。 内容は二本立てです。 実践的な実装について、Ruby(CRuby)の内部実装(string.c)で使われているものを紹介します。 標準Cの範囲を超えて、SIMD命令(AVX/AVX2)を使った実装についても述べます 軽く検索する限りだと既知のアルゴリズムが見当たらなかったので、アドホックな実装をひねり出しましたが、そんなに効率は悪くなさそうです おまけで簡単な性能評価をやってみました。 なお、UTF-8文字列はバリデーション済み（不正なシーケンスでないことが分かっている）であるとします。 Rubyの内部実装だとどうやっているか まずは、それがコードポイントの先頭バイト(leading byte)かを判定す

動画コーデック/動画エンコード周りの話です。これは一例ですが、巷には「H.265はH.264と同等画質でデータ量が半分になる」みたいな言説が見られます。 H.264/MPEG-4 AVC以上に圧縮効率を高めて半分以下のビットレートを実現する。モバイルデバイスや、4K解像度などの超解像度ビデオにおける利用を想定している。 https://pc.watch.impress.co.jp/docs/news/585297.html たぶんより新しい技術だからすごいんだろうと思う一方で、画質・ビットレートに関する根拠というか考え方がさっぱりわかりません 画質と言われても何をどうやって測定しているのか どんな条件でもぴったり半分になるのか？ さすがにそんなことはなさそう？ よくわからなさすぎて困ったので、会社の自席の近くにいる動画エンコーダの専門家に基本的な事項について教わってみたので、その内容をまと

Double HMACパターンというものの存在を最近知ったので、まとめました。 記事の前半では、文字列比較に関するタイミング攻撃の概要と、対策方法（特に定数時間比較について）をまとめます。後半では対策方法の一つであるDouble HMAC Verificationについて紹介します。 ……などと偉そうに書いてはいますが、筆者はセキュリティ専門家でもなんでもないので、記述内容を参照される方はその点ご留意ください。セキュリティの分野は本来、素人が実装をするべきではないとは思います。 読んだサイト Double HMAC Verification タイミング攻撃 サイドチャンネル攻撃という攻撃方法があります。処理にかかる時間・消費電力・電磁波など、その処理から漏れ出た情報を元に、本来入手できないはずの情報を得る手法です。 サイドチャンネル攻撃の一形態として、タイミング攻撃というものがあります。

https://help.github.com/enterprise/2.15/admin/guides/installation/installing-github-enterprise-on-vmware/#hardware-considerations しかしながら、表はかなり利用頻度が低い状況を想定しているようです。たぶん普通は、これだけのスペックでは足りません。 そもそもこの値は古代のGHE 2.1の頃から更新されていない様子がある上、特に最近はGHE 2.14からリソース消費が激しくなったように思います。 GitHub Enterprise 2.12 → 2.14 にしてパフォーマンスデグレしてると思うのでサポートに連絡しつつしぶしぶオーバーサイズなスケールアップをして、お話の結果「うん、スケールアップしてCPUに余裕出てるね^^」と言われて「は?」ってなっている。 — そらは

最近、SIMD命令を使ったプログラミングというものに触れる機会があったので、どうやって入門していったかについてまとめます。この分野はどうしても「分かっている人向け」の記事が多くなりがちのようなので、基本的な知識についてまとめつつ、発展的な資料へのURL等も極力載せるようにしました。 ※ 記事で取り扱うSIMD命令はAVX-512を対象としますが、その他の命令体系（e.g. x86のAVX/AVX2やARMのNEON等）とも多少は共通点があるかもしれません 前提知識とスコープ C/C++のごく基本的な構文を理解している人向けの記述になっています 記事を読む上で、計算機の構造についての基本的な理解が必要かもしれません e.g. CPUがあってメモリがあって〜程度でたぶん大丈夫です 開発環境としてLinux上のClang 5.0.1を想定します（とはいえGCC等でも同じような話になるはずです）

公開HTTPSサーバを立てるときに悩む点の一つが、SSL/TLS周りの設定です。 SSL/TLSや暗号周りの知識がないと適切な設定を選ぶのは難しい そもそも設定が何を意味しているのか読み取れない 「推奨される設定」が各種サイトでいくつも、微妙に違うものが紹介されていて、どれが良いのか選べない とりわけ暗号が関連する選択肢は呪文めいていて、専門知識を持たないWebエンジニアにとっては、なかなか難しいものがあると思います。 筆者もSSL/TLSの専門家ではありません。 専門家でないなりに極力信頼できそうなソースや実例を参考にしつつ、まとめました。もともとは自分用調査資料集のような記事です。 すごく長くなってしまいました（若干力尽きている）。 TL;DR MozillaのTLS設定ガイドをひな形にして設定する。Config Generatorもある とりあえず従っていれば酷いことにはならない 現

Wikipediaを漁っていたところScalable Bloom Filters(SBF)というデータ構造を発見してしまったので紹介します1。 参照した論文 http://haslab.uminho.pt/cbm/publications/scalable-bloom-filters Bloom Filter SBFの説明に入る前に、Bloom Filterについて簡単に紹介します。もっとも、日本語のWikipediaでも十分詳しい説明が載っていたりするのですが……。 ささっと説明 Bloom Filterはちょっと不思議な性質を持つデータ構造の一種です2。 いわゆるSetと同じ操作を提供する 要素を入れる操作と、ある要素が入っているかを調べる操作 どちらも時間計算量O(1)で実現できる ハッシュテーブルなどを用いて実装される同種のデータ型と比して、とても空間効率が良い その代わりに、ある

Erlangは数年前にほんの少し書いたことがあるだけなのですが、会社では同じフロアにErlangをガリガリ書く部隊1がいます。彼らにちょっと教わりつつ久しぶりに書いてみました。 はじめに 最近のマイブームは映像や音声の配信でおなじみRTMPなので、この記事ではErlangでRTMPを取り扱ってみようかと思います。本当はデータの中身をちゃんと取り扱う所までを書きたかったのですが作業時間があまりなく、対象をハンドシェイクと呼ばれるプロトコル初期のフェーズまでに限定します。 RTMPとは Adobe社が制定したReal Time Messaging Protocolのことです。その成り立ちからFlashと相性がよく、音声や動画の配信によく用いられる2プロトコルです。 RTMPは仕様が公開されているので、誰でもプロトコルを理解・解析することができます。 http://wwwimages.adobe

HAProxy1とは何か？ から始まり、基本的な使い方までを調べました。 HAProxyとは 多機能なプロキシサーバです。ソフトウェアロードバランサの一種でもあります。古くから開発が続けられ、非常に高速かつ堅牢で信頼性が高いことを売りにしているようです。 HAProxyが何であって何でないかは、 ドキュメントに箇条書きで記載 されています。 ざっくりまとめると、こんな感じのことが書かれています。 TCP接続のプロキシとして動作させ、アクセス経路を設定することができる HTTPリバースプロキシとしての機能を持ち、ルールに従ってリクエストを別のサーバに渡すことができる このとき、URLやヘッダの書き換えも行える SSLやHTTP圧縮を肩代わりできる TCP/HTTPの正規化器(normalizer)となる 不正なトラフィックからの防護を提供する 負荷分散機能を提供する ロギング機能を持つので、

前回の記事で紹介したのは、Google GuiceのDI機能のうちの一つ、Linked Bindingsだけでした。この記事はその続きです。 サンプルはScalaで書きましたが、例によってScalaっぽいコードが出てくるわけではないですね……Guiceをどう使えばScalaとよりよく連携できるようになるかは、まだよく分かっていません1。 さて、Guiceはもうちょっと色々な方法でDIができるので、それについても調べて紹介します。 以下では例示のために、前回も使用したServiceとその実装クラス2つを使います。 trait Service { def doSomething(): Unit } class FakeService extends Service { def doSomething() { println("FakeService") } } class RealServic

Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article?

あまり目新しい内容ではないですが、Google Guice理解のために、改めてまとめました。 ScalaにおけるDI Javaなどの言語と同様に、Scalaにおいても依存性注入(DI)を実現する方法はいくつかあるようです。 Constructor InjectionやSetter Injectionを使う Cake PatternなどのScala特有の言語機能を使った方法 (Google Guiceなどの)DIフレームワークを使う 構造的部分型を使うetc.... この記事では3.のGoogle Guiceを使う方法について調べました。そういえばPlay Frameworkの2.4でも導入されるとか聞いたような……？ Google Guiceの基本的な使い方（Java） いくつかの典型的なパターンと比較しているという点でも、公式のチュートリアルがとても分かりやすいかなと思います。Guice