枕を欹てて聴く

decodeURIComponentのもろもろについて

Unicode, ECMAScript | 21:44 |

追記1

SpiderMonkeyのサロゲートエリアのbug issue は修正されました! (該当commit) 記事の一番下を御覧ください.

追記2

V8のサロゲートエリアのbug issue は修正されました!(該当commit)

これで以下の記事のサロゲートエリアのbugはV8, SpiderMonkey, JSCで修正されました

普段1.5ヶ月に1記事しか書かないのに, 今日は3つも書いて正気の沙汰じゃないで...

id:piro_or さんよりcommentで, id:nanto_vi さんの以下の記事の話を受けましたのでー. (commentついたの1年ぶりで感涙)

文字列と UTF-8 バイト列の相互変換: Days on the Moon

リンク先の記事では, 以下の方法によるUTF-16 <=> UTF-8の変換が記載されています.

function toUTF8Octets(string) {
  return unescape(encodeURIComponent(string));
}

function fromUTF8Octets(octets) {
  return decodeURIComponent(escape(octets));
}

素晴らしいことに, これで要件を済ませることができます. すごい!! さっすがnanto_viさん! engineが正確に仕様準拠であるならば, 完全にこれで大丈夫です. lv5でも確認できました.

なぜなら, ES5.1, section 15.1.3にあるとおり, encodeURIComponentはUTF-16のmulti byte文字列を%HH%HHという風にUTF-8にconvertし, unescapeはAnnex B2.2をみると, %xy形式のものをHexDigitとしてcode pointを構築し, 何のcheckもなくそのままUTF-16 code pointとしてappendしてしまうからです(step 14). 結果返ってくるstringにはcode pointとして生のUTF-8と全く同じものが入ります. 逆も同様にです. 素晴らしいことに!!!

ただし... edge case

ただし現実のengineはES5仕様の楽園に住んでいるわけではなく, 完全に仕様準拠というわけでもないので, 2011/05/30現在, edge caseに限りおかしな変換結果を返します. これは2つpatternがあるのですが, まずは将来的にも治らないであろう, 意図的な仕様違反を見てみます.

decodeURIComponent(encodeURIComponent('\uFFFF')) !== '\uFFFF'

SpiderMonkeyでは,

decodeURIComponent(encodeURIComponent('\uFFFE')) !== '\uFFFE';
decodeURIComponent(encodeURIComponent('\uFFFF')) !== '\uFFFF';

です. ES5仕様に照らし合わせれば仕様違反ではあるのですが, 意図的なものです.

これはencodeURIComponentまでは正確なのですが, decodeURIComponentでUTF-16に直す時に意図的に置き換えるためです.

https://bugzilla.mozilla.org/show_bug.cgi?id=520095#c2

というわけで意図的に, BOMと誤認識するかもしれない\uFFFE, \uFFFFを\uFFFDに変換します.

よって, \uFFFD, \uFFFFを含む文字列の場合, SpiderMonkeyでは上記の方法は失敗します.

fromUTF8Octets(toUTF8Octets('\uFFFF')) === '\uFFFD';

となってしまうためです. edge case...

ただ, 上記でも触れられているとおり, \uFFFE, \uFFFFに文字が与えられる場合はないので, 通常の文字列の場合は問題ないでしょう. ただ, その特性を利用して文字の区切りとかに使っていたり, UTF-8がこのような表現がたまたま入っていた場合は, \uFFFDという普通の文字に変えられてしまい, \uFFFFの文字として現れないという特性が失われてしまったりするという感じです.

サロゲートエリアさん...

このUnicode変換を実装し, RFC3629を読んでいて, なるほどここに気をつけないといけないのかーと思いながら書いていたのですが, ふと見るとある気をつけるべき部分が「あれっ? この対策ってSpiderMonkeyやってたcodeを見た覚えがない...」となっていた部分でもあります.

それは, 3bytesのUTF-8 => UCS4変換におけるサロゲートエリアの除外です. 上記記事でも一度変換を弾くように書いている,

%xED %A0 10000000

すなわち, encodeURIComponent表現で%ED%A0%80をSpiderMonkeyのdecodeURIComponentに食べさせてみましょう.

decodeURIComponent('%ED%A0%80') === '\uD800'

というわけでURIError飛ばずに通ってしまいました. 果たしてこれは仕様と照らし合わせてどうなのか.

みんな大好きECMA262 5.1th section 15.1.3 Decodeのstep 4-d-vii-8によると,

Let V be the value obtained by applying the UTF-8 transformation to Octets, that is, from an array of octets into a 32-bit value. If Octets does not contain a valid UTF-8 encoding of a Unicode code point throw a URIError exception.

http://es5.github.com/#x15.1.3

というわけで, RFC3629に照らし合わせればこれはvalid UTF-8 encodingではないので, URIErrorが出されねばならず, 仕様違反であると解釈できます.

ということは, このようなbyte列,

var str = "\u00ED\u00A0\u0080";
fromUTF8Octets(str);  // this is not valid UTF-8, so must throw error

invalidにもかかわらず, "\uD800"が出てしまいます. これならまったくサロゲートペア関係ないinvalidなUTF-8 3bytesのcode point2つつかって, サロゲートペアと誤認識させることができたりしますね...

というわけで, ぶっちゃけ2つめはengineのbugです. V8, SpiderMonkeyで確認しました. JSCにはこのbugがありませんでした. wtf/unicode/UTF.cppのdecodeUTF8Sequence関数のHandle 3bytes sequencesをみるときちんと,

    // Handle 3-byte sequences.
    if ((b2 & 0xC0) != 0x80)
        return -1;
    const unsigned char b3 = sequence[3];
    if (length == 3) {
        if (b3)
            return -1;
        const int c = ((b0 & 0xF) << 12) | ((b1 & 0x3F) << 6) | (b2 & 0x3F);
        if (c < 0x800)
            return -1;
        // UTF-16 surrogates should never appear in UTF-8 data.
        if (c >= 0xD800 && c <= 0xDFFF)
            return -1;
        return c;
    }

surrogate areaは弾くようにきちんと対策されていますね. lv5は下のentryに書いたC++のcodeを用いているのでもちろん弾きます.

結論

というわけで, SpiderMonkey, V8にそれぞれissueをreportしました.

http://code.google.com/p/v8/issues/detail?id=1415

https://bugzilla.mozilla.org/show_bug.cgi?id=660612

lv5開発, 変なところで貢献してるな...

非常に面白いお話をありがとうございました.

追記

id:koichik さんよりcommentを頂きました. ありがとうございますー. ということで, V8はUTF-16でなくUCS-2をサポートしている, つまりsurrogate pairはそもそもサポートしていないそうです, ってまじですか...

追記

fixされました.

http://hg.mozilla.org/mozilla-central/rev/0d5626387b8a

ChromeFullFeedが公開停止になった話

Chrome, Extension | 05:41 |

ChromeFullFeedがGoogleのiconっぽいとかいう理由で一撃必殺, 公開停止になった id:Constellation です! 中身とかいちいち見てるはず無いので, おそらくあのFのアイコンだと思うのですが, あれってGoogleを暗示してますかね? いやいやいやいや, それはどうなのー, しかも説明文もGoogle関係ないじゃん...ということで, 現在反論のmailを送っていますが返ってきません!! id:os0x さんにはご迷惑をおかけして申し訳ないです...

一周してテンション高くなってきて, つい記念にscreenshotをとったりしています. すごい! 珍しい! BAN!

追記

your item [ChromeFullFeed] has been removed from the Chrome Web Store because it uses Google marks and/or icons in a way that doesn’t comply with our branding policies:

http://code.google.com/chrome/webstore/branding.html

だそうで, てっきりiconが問題になっているものと思っていたのですが, TMを付けろという話なんじゃないかというアドバイスを頂いたので, とりあえずTM付けてreview pendingの状態にして, mailでどっちが問題になってるのか聞いてみることにします.

これで逆にiconsの問題じゃなくて, TM付けたらあっさり通ったら, 勘違いで騒いで申し訳ない+恥ずかしい...

追記2

id:h2u さんのアドバイスに従い, TMを付けたところ通りましたー! mark or/and iconで, markもすっかりiconの一種だと思っていてiconではねられたものだと思い, 完全に勘違いしていました. お騒がせして申し訳ないです. すみません...

Excuse me, the guideline point this extension breaks is mark or icon.

which is it?

... 以下いろいろと続く

と拙い英語で聞いたところ, 今日

// ... いろいろ

Please also change your item name.

// ... いろいろ

と返信が来まして, 再公開となりました. 短絡的に勘違いしてしまいすみません...

以後, 気をつけていきたいと思います. ありがとうございました.

vs UTF-8, UTF-16, UCS4

Unicode, C++, JavaScript, ECMAScript | 03:51 |

前置き

おはミルキィ! ChromeFullFeedが公開停止になった話を前置きとして書いていたのですが, あまり関係がないのと, 長くなりそうになってきたので, 別の記事に分けました. http://d.hatena.ne.jp/Constellation/20110530/1306701693

概要

という前置きで.

ECMAScriptと切っても切れない文字コード, UTF-16. iv / lv5はUnicode変換のためにICUに依存していたのですが, UTF-8 <=> UTF-16なら何とか自分でも書けるのではないかと思い, Unicode Converterを書きました. これでlv5の依存はlibboost, libgc (Boehm GC)に減りましたー.

Unicodeの変換の教授, bugつぶしにおいて, id:masa141421356 さんに非常にお世話になりました. ありがとうございます. ようやくICUを外して身軽になりました.

というわけでUnicode変換の話. 文字コードの専門家というわけでは全然ないので, ひたすら変換処理自体の実務的な話をします.

bugを見つけた場合, iv / lv5の方のissueに向かって文句言ってもらえるとbugをつぶせてすごーくありがたいです.

source codeはivのunicode.hです. LicenseはNew BSDなので, 使いたいという物好きな方がいらしたらどうぞ. tr1が必要ですが...

https://github.com/Constellation/iv/blob/master/src/unicode.h

下の方でECMAScriptの話もしているので, ECMAScripterの方で面倒になってきた方は一気にjumpしてもらっても.

UTF-8 format

RFC3629出典のUTF-8 format表です. RFC3629, 意外と短い!!

RFC3629

日本語訳

Char. number range  |        UTF-8 octet sequence
   (hexadecimal)    |              (binary)
--------------------+-------------------------------------
0000 0000-0000 007F | 0xxxxxxx
0000 0080-0000 07FF | 110xxxxx 10xxxxxx
0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

先頭byteで長さを(bitの立っている数), その後(10xxxxxx)2で6byteずつ表現していくわけで,

byte数	content
1	7
2	11
3	16
4	21

というふうになっています.

素晴らしいことに, 1byteの時の7bitというのはASCII rangeであり, ASCII文字ならそのままUTF-8と受け取っても問題ないという特徴があります. UTF-16とは異なりますね(一文字あたり通常uint16_tひとつなので当たり前).

また, tailing byteが10xxxxxxという風になっていることで, ASCII文字と勘違いすることがないという特徴があるそうです. 賢い!!(ASCIIは7bitなので, 先頭bitが立つことは無い). つまり, ダメ文字"\\"が入って問題になるということがそもそもないのですね.

では, まずUTF-8をUCS4に変換していきたいと思います.

UTF-8 => UCS4

UTF-8のときのxxxxxを取り出して, uint32_t上に並べればそれでUCS4の完成です. 簡単そうです. では具体的な処理を見ていきます.

UTF-8の長さを取得する

まず必要なのは, 1byte見て, その文字が何byteで構成されているかを数えることです. lv5 unicode.hでは以下のような関数を用いています.

template<typename UC8InputIter>
inline typename std::iterator_traits<UC8InputIter>::difference_type
UTF8ByteCount(UC8InputIter it) {
  // not use loop
  const uint8_t ch = Mask<8>(*it);
  if (ch < 0x80) {
    // ASCII range
    return 1;
  } else if ((ch >> 5) == 0x6) {
    // 110xxxxx
    return 2;
  } else if ((ch >> 4) == 0xE) {
    // 1110xxxx
    return 3;
  } else if ((ch >> 3) == 0x1E) {
    // 11110xxx
    return 4;
  }
  // invalid utf8
  return 0;
}

• 0x80は(10000000)2ですね. つまり, 先頭bitが立っていない場合です. これは上の表で見たとおり1byteで文字を表すASCII互換部分ですので, 長さは1です.
• 次に, 5bit 右シフトして, 0x6, (110)2と比較します. 8bitのうち5bit shiftしたので, 下3bit以外は0です. さて個別に見ると,
  • まず0x80以上であることが確定しているので, 1xxであることは確定です.
  • 2byteの時は110, 3-4byteのときは111になりますね(上の参照), よって0x6, 110と==になるときは2byteであると確定できます.
    • invalidなものがきたと考えましょう. 100, 101などはinvalidな表現です. この時これには一致しないので次の条件に回されます. しかしこれ以降の条件は先ほど3-4byteのとき111となったのを確認したとおり, この部分が111である場合しか一致しませんので, 最後までifで一致せず, invalid utf8として長さ0が返されます.
• 次に, 4bit 右シフトして, 0xE, (1110)2と比較します. 表を参照すれば, これは3byteのpatternです.
  • 一致する場合は3byteですね. 4byteの場合は(1111)2になるので一致しません.
• そして3bit 右シフトして, 0x1E, (11110)2と比較します.
  • これで一致すれば4byteです.
• ここまで来て一致しなかったものはUTF-8の表現としてinvalidです. よって長さ0をもって不正値であるとします.

これ以外にも, そもそも1byteは256 patternしか無いのだから, すべてのpattern持っていたとしても何の問題もないという考え方もあります.

UTF-8 の文字列を一文字ずつ区切る - mooz deceives you

上のものは5-6byteも考えているので(RFC3629ではなくなりました), RFC3629にしたがって, 4byteまでで制限したらこんな感じでしょうか. これは先程の関数と同じ値を返すものです.

#include <cstdint>
#include <array>

inline std::size_t UTF8ByteCount(uint8_t byte) {
  static const std::array<uint8_t, UINT8_MAX + 1> kLengthMap = { {
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,  // 00000000 -> 00011111
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,  // 00100000 -> 00111111
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,  // 01000000 -> 01011111
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,  // 01100000 -> 01111111  ASCII range end
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,  // 10000000 -> 10011111  invalid
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,  // 10100000 -> 10111111  invalid
    2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,  // 11000000 -> 11011111  2 bytes range
    3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,                                  // 11100000 -> 11101111  3 bytes range
    4,4,4,4,4,4,4,4,                                                  // 11110000 -> 11110111  4 bytes range
    0,0,0,0,0,0,0,0                                                   // 11111000 -> 11111111  invalid
  } };
  return kLengthMap[byte];
}

これのほうが計算少ないので高速かもしれません. 対して変わらないかもですが.

組み立て

長さが手に入ればこっちものですね. この長さに従って, まず先頭byteから取得すべきbitを取得. そののち, 後続byteから10xxxxxxの6bit分をもらってきて構築していきます.

注意として, 長さはあくまでUTF-8 formatによる自己申告だということです. 当然, 本当にその長さ分あるのかどうかはわかりませんのでcheckしながら組み立てる必要があります.

ちなみに, 機械的にできると思わせて, 実はそれぞれちょっとずつcheckしないといけなかったりするので, 意外と4つ書いたほうが楽です. 高々4 patternですし.

https://github.com/Constellation/iv/blob/b8a507f99bb8921033334899ebaaad904ef1fde1/src/unicode.h#L175...L321

組み立て: 1byte

template<std::size_t N>
struct UTF8ToCodePoint;

template<>
struct UTF8ToCodePoint<1> {
  template<typename UC8InputIter>
  static inline uint32_t Get(UC8InputIter it, UC8InputIter last, UTF8Error* e) {
    if (it != last) {
      return Mask<8>(*it);
    } else {
      *e = NOT_ENOUGH_SPACE;
    }
    return 0;
  }
};

別にmeta metaする予定はないのですが, なんかこんな感じに.

UTF8ToCodePoint<1>は見てのとおり, ただ単にcastしている以上の何物でもないですね. BitMaskだけかけています.

組み立て: 2bytes

template<>
struct UTF8ToCodePoint<2> {
  template<typename UC8InputIter>
  static inline uint32_t Get(UC8InputIter it, UC8InputIter last, UTF8Error* e) {
    static const uint32_t kMin = 0x00000080;  // 2 bytes => 0000000010000000
    if (it != last) {
      // remove size bits from 1st byte
      // 110xxxxx
      uint32_t res = Mask<5>(*it++) << 6;
      if (it != last) {
        if (IsTrail(*it)) {
          // max value is 11111111111 => 2047 => 0x7FF
          // so no check out of range: max
          res = res | Mask<6>(*it);
          if (res >= kMin) {
            return res;
          } else {
            *e = INVALID_SEQUENCE;
          }
        } else {
          *e = INVALID_SEQUENCE;
        }
      } else {
        *e = NOT_ENOUGH_SPACE;
      }
    } else {
      *e = NOT_ENOUGH_SPACE;
    }
    return 0;
  }
};

UTF8ToCodePoint<2>も基本的に構築しているだけです. 最初のbyteはLength確認の時点でformatとしては正しいものだったと仮定しています. この内必要なのは110xxxxxの下5bitなので, 5bitでBitMaskをかけ, 次に後続6bitがくる予定なので6 bit shiftしています. で, 長さは自己申告なので, きちんとiteratorが続くかどうか確認したあと, まず, IsTrailでcheckしています.

IsTrailは,

template<typename UC8>
inline bool IsTrail(UC8 ch) {
  // UTF8 String (not 1st) should be 10xxxxxx (UTF8-tail)
  // 0xC0 => (11000000) 0x80 => (10000000)
  return (ch & 0xC0) == 0x80;
}

で, つまり, 10xxxxxxの形式になっているかというcheckです.

そのあと, 6bit取り出して, 前のものにORをとって合成. これで2byte文字のUCS4表現を取得できました.

しかし, おや, ちょっと待ってください. なにか他にも処理があります. その説明をします.

UTF-8は多重表現を許可していません. これが許可されると非常に面倒で, 例えば, code point 1を表現しようとすれば,

1byte| 0xxxxxxx                            | 00000001
2byte| 110xxxxx 10xxxxxx                   | 11000000 10000001
3byte| 1110xxxx 10xxxxxx 10xxxxxx          | 11100000 10000000 10000001
4byte| 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx | 11110000 10000000 10000000 10000001

の4 patternがあることになってしまいます. 要は多くbyteをとって, 上をすべて0で埋めてしまえば良いのですね. これは困ります.

このため1は00000001というふうに最小byteで表現するよう制限があります.

で, 今の構築では, うっかり2byteのところで上をすべて0で埋められてもスルーしてしまいます. これではいけません. そこで

    static const uint32_t kMin = 0x00000080;  // 2 bytes => 0000000010000000
    // ...
          if (res >= kMin) {
            return res;
          } else {
            *e = INVALID_SEQUENCE;
          }

の部分です.

2byteで表現される文字は1byteで表現される文字とかぶっていてはいけません. つまり1byteで表現される範囲 0x00 <= code < 0x80とかぶっていてはいけないのです.

よって, kMin = 0x80より上かどうかをcheckすることで, 1byteで表現できるものをわざと2byteで表現していないかというのをcheckし, 弾くことができるのです.

組み立て: 3bytes

template<>
struct UTF8ToCodePoint<3> {
  template<typename UC8InputIter>
  static inline uint32_t Get(UC8InputIter it, UC8InputIter last, UTF8Error* e) {
    static const uint32_t kMin = 0x00000800;  // 3 bytes => 0000100000000000
    if (it != last) {
      // remove size bits from 1st byte
      // 1110xxxx
      uint32_t res = Mask<4>(*it++) << 12;
      if (it != last) {
        if (IsTrail(*it)) {
          res = res | Mask<6>(*it++) << 6;
          if (it != last) {
            if (IsTrail(*it)) {
              // max value is 1111111111111111 => 0xFFFF
              // so no check out of range: max
              res = res | Mask<6>(*it);
              if (res >= kMin) {
                // and if res in surrogate range, this code is invalid.
                if (res < kSurrogateMin || kSurrogateMax < res) {
                  return res;
                } else {
                  *e = INVALID_SEQUENCE;
                }
              } else {
                *e = INVALID_SEQUENCE;
              }
            } else {
              *e = INVALID_SEQUENCE;
            }
          } else {
            *e = NOT_ENOUGH_SPACE;
          }
        } else {
          *e = INVALID_SEQUENCE;
        }
      } else {
        *e = NOT_ENOUGH_SPACE;
      }
    } else {
      *e = NOT_ENOUGH_SPACE;
    }
    return 0;
  }
};

ほとんど2bytesと同じですが, 一部異なるところがあります. それは, surrogate areaに入っていないかです.

3bytesの表現は12bitから16bit, つまり, 0x0800から0xFFFFです. これは後述のUTF-16のサロゲートエリアである0xD800から0xDBFF, 0xDC00から0xDFFF, 連続しているので, つまり0xD800から0xDFFFの領域を含んでいます. UCS4上にsurrogate area文字が現れてしまいます.

UCS4からUTF-16にするとき, 0xFFFF以下の物はそのままUTF-16のcodeとします. そして0x10000以上のものをsurrogate pairに2分割して用いるわけですが, このままUCS4にsurrogate area文字を許可してしまうと, UTF-16でsurrogate areaの文字が出てきたときに, この文字はもともとUCS4でsurrogate areaの文字だったのか, surrogate pairでこれに変換されているのか区別がつかないですね. 割り当てがかぶってしまうわけです. よってサロゲートエリアのcodeは許可されていません. サロゲートエリアの場合はinvalidであるとして弾く必要があります.

これはRFC3629の中では文章, 及びABNFで表現されています. ではABNFの該当部分を引っ張ってきましょう.

UTF8-3      = %xE0 %xA0-BF UTF8-tail / %xE1-EC 2( UTF8-tail ) /
              %xED %x80-9F UTF8-tail / %xEE-EF 2( UTF8-tail )

%xE0 %xA0-BF UTF8-tail

の制限は, 12bit以上のbitに一つでもbitが立つようにの制限ですね. kMinで行っているものです. 重複を許さないというBNF上での表現です.

その後, 普通にUTF8-tailが続きますが, ところが, 途中でぶった切っている表現がありますね.

%xED %x80-9F UTF8-tail

先頭byteが0xEDの時は, 2byte目を0x80-0x9Fに制限しています. じゃあ制限されている部分を作ってみましょう. では制限されている表現の中で一番小さな,

%xED %A0 10000000

は, 先頭の0xEDが(11101101)2で, 下位4bit1101, 0xA0が(10100000)で, 100000が6bit, 構築して,

(1101100000000000)2が制限先の最小codeですね. これは

console.log(parseInt("1101100000000000", 2).toString(16));  // => 0xd800

はい, サロゲート領域最小code, 0xD800が出てきましたね.

という要領で確認すれば, surrogate areaがたしかに制限されているのがわかります.

組み立て: 4bytes

template<>
struct UTF8ToCodePoint<4> {
  template<typename UC8InputIter>
  static inline uint32_t Get(UC8InputIter it, UC8InputIter last, UTF8Error* e) {
    static const uint32_t kMin = 0x00010000;  // 4 bytes => surrogate pair only
    if (it != last) {
      // remove size bits from 1st byte
      // 11110xxx
      uint32_t res = Mask<3>(*it++) << 18;
      if (it != last) {
        if (IsTrail(*it)) {
          res = res | Mask<6>(*it++) << 12;
          if (it != last) {
            if (IsTrail(*it)) {
              res = res | Mask<6>(*it++) << 6;
              if (it != last) {
                if (IsTrail(*it)) {
                  // max value is 111111111111111111111 => 0x1FFFFF
                  // so must check this value is in surrogate pair range
                  res = res | Mask<6>(*it);
                  if (res >= kMin) {
                    if (res <= 0x10FFFF) {
                      return res;
                    } else {
                      *e = INVALID_SEQUENCE;
                    }
                  } else {
                    *e = INVALID_SEQUENCE;
                  }
                } else {
                  *e = INVALID_SEQUENCE;
                }
              } else {
                *e = NOT_ENOUGH_SPACE;
              }
            } else {
              *e = INVALID_SEQUENCE;
            }
          } else {
            *e = NOT_ENOUGH_SPACE;
          }
        } else {
          *e = INVALID_SEQUENCE;
        }
      } else {
        *e = NOT_ENOUGH_SPACE;
      }
    } else {
      *e = NOT_ENOUGH_SPACE;
    }
    return 0;
  }
};

2bytesと基本的には同じです.

しかし一部異なる点といえば,

                  if (res >= kMin) {
                    if (res <= 0x10FFFF) {
                      return res;
                    } else {
                      *e = INVALID_SEQUENCE;
                    }
                  } else {
                    *e = INVALID_SEQUENCE;
                  }

で, kMinだけでなく, 0x10FFFF以下かどうかもcheckしています. これは何か?

4byteになったときに使えるbit数は6 * 3 + 3 = 21bitで, かつ3bytesの時には6 * 2 + 4 = 16だったのですから, 4byteで表すべきbitは17bit -> 21bitということになります.

ところが, 今までの0 -> 16bitの領域まではinvalidなcode pointというものはなかったので問題なかったのですが, ここに来て問題が出ます. つまり, Unicodeのcode pointで0x10FFFFより上は存在しないのです (rangeがU+0000 ... U+10FFFFである). これはUTF-16 accessible rangeです. UTF-8の許可領域がUTF-16 accessible rangeと同じであるということは, UTF-16 <=> UTF-8の変換で情報の損失が起こらないことも意味します.

で, 今回21bitということで, maxで(111111111111111111111)2 => 0x1FFFFF, ということで超えてしまいます. よって0x10FFFFより上のものになっていた場合はinvalidであるというふうなcheckをしなければいけないのです.

というわけで, それぞれcheckすべき部分がちょいちょい異なるので, 4つとも説明しました.

やりました! これできちんとinvalidなものをはじきながらUTF-8をUCS4に変換したのです.

UTF-16 format

RFC2781

日本語訳

・0x10000 未満の値を持つ文字は、値を文字のそれに等しい状態にして1つ
  の 16ビット整数として表現される。
・0x10000 〜 0x10FFFF の範囲内の値を持つ文字は、0xD800〜0xDBFF (いわ
  ゆる高位ハーフゾーン、または高位サロゲートエリア) の間の値を持つ16
  ビット整数に続き、0xDC00〜0xDFFF (いわゆる下位ハーフゾーン、または
  下位サロゲートエリア) の間の値を持つ16ビット整数で表される。
・0x10FFFF を超える値を持つ文字は、UTF-16 では符号化することができな
  い。

というはなし. つまり, 0x10000より下ならば, 問答無用でcastしてUTF-16として扱うことが可能です.

そして, 0x10000 <= code <= 0x10FFFFは, 2bytesに分割され, 高位0xD800から0xDBFF, 下位0xDC00から0xDFFFの2bytesのpairで表現されます. みんな大好きサロゲートペアですね.

ここで注目したいのは, サロゲートペアになるのが0x10000以上という話. これは(10000000000000000)2で17bitですね. ちょうどUTF-8の4bytesの表現範囲が17bitから21bitだったはずです. つまり, UTF-8で4bytesで表現されていた文字がちょうどUTF-16でサロゲートペアとして表現されます.

UCS4 => UTF-16

UCS4からUTF-16に変換することで, 念願のUTF-16文字列が手に入ります.

今回UCS4は外部から取得するということはないので, 完全にvalidな表現のみであるという仮定のもと変換を行います(invalidなものはUTF-8 => UCS4で弾かれている)

2.1 UTF-16 の符号化

    ISO 10646 文字値から UTF-16 までの1つの文字の符号化は、次のとおりに
  続く。U は 0x10FFFF を超えない文字番号である。

   1) U < 0x10000 なら、Uを16ビット無符号整数として符号化し、終了する。

   2) U' = U - 0x10000 と置く。U が 0x10FFFF 以下なので、U' は 0xFFFFF
      以下となるはずだ。すなわち、U'は20ビットで表現可能である。

   3) 2つの16ビット無符号整数 W1 および W2 に、それぞれ 0xD800 と 0xDC00
      を初期設定する。これらの整数はそれぞれ自由に計20ビットの文字値を符
      号化することができる10ビットを持っている。

   4) U' の 20ビットのうち、上位10ビットをW1の下位10ビットに割り当て、U'
      の下位10ビットを W2の下位10ビットへ割り当て、終了する。

   図で示すと、ステップ2から4までが以下のように見える:

   U' = yyyyyyyyyyxxxxxxxxxx
   W1 = 110110yyyyyyyyyy
   W2 = 110111xxxxxxxxxx

という風に表現されていて, もうそれこそそのままなので, UCS4 => UTF-16というのは非常に簡単なのです.

static const uint32_t kSurrogateBits = 10;
static const uint32_t kHighSurrogateOffset = kHighSurrogateMin - (0x10000 >> 10);
static const uint32_t kLowSurrogateMin = 0xDC00;

inline uint16_t ToHighSurrogate(uint32_t uc) {
  return static_cast<uint16_t>((uc >> kSurrogateBits) + kHighSurrogateOffset);
}

inline uint16_t ToLowSurrogate(uint32_t uc) {
  return static_cast<uint16_t>((uc & kLowSurrogateMask) + kLowSurrogateMin);
}

手順としては

• 0x10000より下かどうかcheck (もしくは0xFFFFより上ならsurrogate pairという言い方もできる)
  • 下なら, そのまま代入
• 上ならsurrogate pairとして表現. まず0x10000を引く
  • 高位は上10bitなので, 10bit shiftして, 1101100000000000, つまり0xD800とORをとれば完成
  • 下位は下10bitなので, 10bitでmaskして, 1101110000000000, つまり0xDC00とORをとれば完成

ですが, 0x10000は17bitあり, かつsurrogate pairは0x10000以上であることが保証されているので, 引こうが引くまいが下位10bitには影響がありません. よって, 上のC++ sourceではLowSurrogateの時は引き算を行わず10bit maskをかけています.

これで, UCS4からUTF16への変換は終了です.

UTF-8 => UTF-16

これを2つ組み合わせると,

template<typename UC8InputIter>
inline UC8InputIter NextUCS4FromUTF8(UC8InputIter it, UC8InputIter last, uint32_t* out, UTF8Error* e) {
  typedef typename std::iterator_traits<UC8InputIter>::difference_type diff_type;
  const diff_type len = UTF8ByteCount(it);
  if (len == 0) {
    *e = INVALID_SEQUENCE;
    return it;
  }
  uint32_t res;
  switch (len) {
    case 1:
      res = UTF8ToCodePoint<1>::Get(it, last, e);
      break;

    case 2:
      res = UTF8ToCodePoint<2>::Get(it, last, e);
      break;

    case 3:
      res = UTF8ToCodePoint<3>::Get(it, last, e);
      break;

    case 4:
      res = UTF8ToCodePoint<4>::Get(it, last, e);
      break;
  };
  if (*e == NO_ERROR) {
    std::advance(it, len);
  }
  *out = res;
  return it;
}

// ...

template<typename UC8InputIter, typename UC16OutputIter>
inline UTF8Error UTF8ToUTF16(UC8InputIter it, UC8InputIter last, UC16OutputIter result) {
  UTF8Error error = NO_ERROR;
  uint32_t res;
  while (it != last) {
    it = NextUCS4FromUTF8(it, last, &res, &error);
    if (error != NO_ERROR) {
      return error;
    } else {
      if (res > 0xFFFF) {
        // surrogate pair only ch > 0xFFFF
        // because NextUCS4FromUTF8 checks code point is valid
        *result++ = ToHighSurrogate(res);
        *result++ = ToLowSurrogate(res);
      } else {
        *result++ = static_cast<uint16_t>(res);
      }
    }
  }
  return NO_ERROR;
}

という感じでしょうか. 意外と何とかなりますね!

UTF-16 => UCS4

こんどは逆です. consoleに文字を出すためにはUTF-16をUTF-8にしてSTDOUTに出さないといけません. UTF-16は当然invalidなものも含まれるという想定のもと変換を行います.

2.2 UTF-16 の復号

    UTF-16 から ISO 10646 文字値までの 1 つの文字の復号は、次のとおりに
  続く。

    W1 はテクストを表す整数列における次の16ビット整数とする。W2 は W1 の
  後に続く (最終的な) の次の整数だとする。

   1) W1 < 0xD800 または W1 > 0xDFFF なら、文字値 U は W1 の値とし、終了
      する。

   2) W1 が 0xD800〜0xDBFF かどうかを決定する。もしそうでなければ、その
      シーケンスは間違っており、そして正当な文字は W1 を用いて得ることが
      できない。終了する。

   3) W2 (すなわちそのシーケンスが W1 で終わる) が無い、もしくは W2 が
      0xDC00〜0xDFFF で無いなら、そのシーケンスは間違っている。終了する。

   4) W1 の下位10ビットを上位10ビット、W2 の下位10ビットを下位10ビットと
      して、20ビット無符号整数 U' を組み立てること。

   5) 文字値 U を得るために U' に 0x10000 を加えること。終了する。

template<typename UC16>
inline bool IsHighSurrogate(UC16 uc) {
  return (static_cast<uint32_t>(uc) & ~kHighSurrogateMask) == kHighSurrogateMin;
}

template<typename UC16>
inline bool IsLowSurrogate(UC16 uc) {
  return (static_cast<uint32_t>(uc) & ~kLowSurrogateMask) == kLowSurrogateMin;
}

template<typename UC16>
inline bool IsSurrogate(UC16 uc) {
  return (static_cast<uint32_t>(uc) & ~kSurrogateMask) == kSurrogateMin;
}

inline uint32_t DecodeSurrogatePair(uint16_t high, uint16_t low) {
  return (static_cast<uint32_t>(high & kHighSurrogateMask) << kSurrogateBits) +
      static_cast<uint32_t>(low & kLowSurrogateMask) + 0x10000;
}

template<typename UTF16InputIter, typename UC8OutputIter>
inline UTF8Error UTF16ToUTF8(UTF16InputIter it, UTF16InputIter last, UC8OutputIter result) {
  while (it != last) {
    uint32_t res = Mask<16>(*it++);
    if (IsSurrogate(res)) {
      if (IsHighSurrogate(res)) {
        if (it == last) {
          return INVALID_SEQUENCE;
        }
        const uint32_t low = Mask<16>(*it++);
        if (!IsLowSurrogate(low)) {
          return INVALID_SEQUENCE;
        }
        res = DecodeSurrogatePair(res, low);
      } else {
        // starts with low surrogate is error
        return INVALID_SEQUENCE;
      }
    }
    result = Append(res, result);
  }
  return NO_ERROR;
}

• UTF-16にてinvalidなものとは何でしょうか? 16bitのため0x0000 => 0xFFFFより, この中でサロゲートエリアに入っていない場合はそのままUCS4にできます. つまり0xD800より下, 0xDFFFより上ならそのままUCS4とします.
  • C++ sourceではIsSurrogateという関数を使って判断しています. サロゲートペアとは, 110110yyyyyyyyyy and 110111xxxxxxxxxxでした. よって情報領域の10bit + 一番下でHigh / Low Surrogateを分けるbitである1bitを足した11bitを弾くと, サロゲートペアの場合のみ1101100000000000になります.
• サロゲートペアの場合, 先にHigh Surrogateがこないとおかしいです. よってIsHighSurrogateで確認し, もしLowSurrogateが先に来ていた場合はerrorとします.
• サロゲートペアの場合は次の文字がLowSurrogateである必要があります. これもIsLowSurrogateで確認しています.
• そしてサロゲートペアをUCS4に戻します. それぞれ10bitでmaskし, Highの場合は10bit上に上げます. そして合成したあと, 0x10000を足します.

UCS4 => UTF-8

今回もUCS4は外部から来ないので, UCS4は完全にvalidであると仮定します.

   文字番号範囲        |        UTF-8 オクテット列
      (16進数)         |              (2進数)
   --------------------+---------------------------------------------
   0000 0000-0000 007F | 0xxxxxxx
   0000 0080-0000 07FF | 110xxxxx 10xxxxxx
   0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
   0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

   UTF-8への文字の符号化は、以下のとおりに続く:


   1.  上記のテーブルの文字値から必要なオクテットおよび最初のカラム番
       号を決定すること。テーブルの列が相互に排他的であること。すなわ
       ち、与えられた 文字を符号化するのにただ 一つだけ有効な方法があ
       ることに注意することが重要である。

   2.  テーブルの2番目のカラムに従ってオクテットの最上位ビットを準備す
       ること。

   3.  バイナリにおいて表現された文字数のビットからビットマークxを埋め
       てください。最初に文字番号の下位ビットをシーケンスの最終オクテッ
       トの下位ビットに入れ、そして、文字番号の次のより高位ビットをそ
       のオクテットなどの次のより高位の位置に入れ、最後のオクテットの
       xビットが埋められる時には次に進み、そして最後の手前のオクテット
       という順で埋めていきすべてのxビットを埋めるまで続ける。

template<typename UC8OutputIter>
inline UC8OutputIter Append(uint32_t uc, UC8OutputIter result) {
  if (uc < 0x80) {
    // 0000 0000-0000 007F | 0xxxxxxx
    *result++ = static_cast<uint8_t>(uc);
  } else if (uc < 0x800) {
    // 0000 0080-0000 07FF | 110xxxxx 10xxxxxx
    *result++ = static_cast<uint8_t>((uc >> 6) | 0xC0);
    *result++ = static_cast<uint8_t>((uc & 0x3F) | 0x80);
  } else if (uc < 0x10000) {
    // 0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
    *result++ = static_cast<uint8_t>((uc >> 12) | 0xE0);
    *result++ = static_cast<uint8_t>(((uc >> 6) & 0x3F) | 0x80);
    *result++ = static_cast<uint8_t>((uc & 0x3F) | 0x80);
  } else {
    assert(uc <= kUnicodeMax);
    // 0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
    *result++ = static_cast<uint8_t>((uc >> 18) | 0xF0);
    *result++ = static_cast<uint8_t>(((uc >> 12) & 0x3F) | 0x80);
    *result++ = static_cast<uint8_t>(((uc >> 6) & 0x3F) | 0x80);
    *result++ = static_cast<uint8_t>((uc & 0x3F) | 0x80);
  }
  return result;
}

uint32_t, つまりUCS4 codeをUTF-8に変換しています

• まず0x80未満, つまりASCII rangeのものをcheckします. この範囲内にある場合は, そのまま1byteのUTF-8 codeとして解釈できます.
• 表を見ると分かりやすいですが, 2byteは0x7FFまで表現できるので, 0x800未満のものを2byteとしてencodeします. この時, 0x80未満のものはすでに1byteとして符号化済みなので, 重複表現が現れる(1byteで表現すべきものを2byteで表現してしまう)がことはありません.
  • 下6bitを切って上5bitを取り出し, 0xC0, つまり(11000000)2とORをとって1byte目を作ります.
  • 0x3F, つまり(111111)2でmaskし6bitを取り出し, これを0x80, (10000000)2とORをとって2byte目をつくります.
    • UTF-8のtailはみな上2bitが10のため, 0x80とORをとって作ることになります.
• また表より3bytesは0xFFFFまでなので, 0x10000未満のものをencodeします.
  • この時, 0xD800->0xDFFFはUCS4の時点で除かれていて, validな表現しか来ないと考えているので, 対策はする必要がありません.
  • 下12bitを削って4bitを取り出し, 0xE0, つまり(11100000)2とORをとって1byte目をつくります.
  • 下6bitを削って10bitを取り出し, 0x3F, つまり(111111)2でmaskして真ん中の6bitを取り出し, 0x80とORをとって2byte目
  • 0x3F, (111111)2でmaskして最下位の6bitを取り出し, 0x80とORをとって3byte目
• 残りは4bytesになります. 最大0x10FFFFの制限はすでにUCS4に変換する時点で成り得ないので(surrogate pairをdecodeしても最大0x10FFFFまで), checkを省いています. assertをいれておきました.
  • 下18bitを削って3bitを取り出し, 0xF0, つまり(11110000)2とORをとって1byte目
  • 下12bitを削って9bitを取り出し, 0x3Fで6bit mask. かつ0x80とORをとって2byte目
  • 下6bitを削って15bitを取り出し, 0x3Fで6bit mask. かつ0x80とORをとって3byte目
  • 0x3Fで6bit mask. かつ0x80とORをとって4byte目

本編

はい, JSer / ECMAScripterの方々に至りましては「さあどうせここからECMAScriptの話になるんだろう!」と期待していらっしゃると思いまして, ご期待に答えたいと思います. というか期待されてなくてもやりたい放題です.

というわけでUTF-8 <=> UTF-16をJSで作りました. Uint8Array使えるときはそっちを使ったりします.

誰得...

https://gist.github.com/997992

(function(module) {
  var length_buffer = [
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,  // 00000000 -> 00011111
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,  // 00100000 -> 00111111
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,  // 01000000 -> 01011111
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,  // 01100000 -> 01111111  ASCII range end
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,  // 10000000 -> 10011111  invalid
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,  // 10100000 -> 10111111  invalid
    2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,  // 11000000 -> 11011111  2 bytes range
    3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,                                  // 11100000 -> 11101111  3 bytes range
    4,4,4,4,4,4,4,4,                                                  // 11110000 -> 11110111  4 bytes range
    0,0,0,0,0,0,0,0                                                   // 11111000 -> 11111111  invalid
  ];
  if (typeof Uint8Array !== 'undefined') {
    var kLengthArray = new Uint8Array(length_buffer);
  } else {
    var kLengthArray = length_buffer;
  }

  const k1BitMask = (1 << 1) - 1;
  const k2BitMask = (1 << 2) - 1;
  const k3BitMask = (1 << 3) - 1;
  const k4BitMask = (1 << 4) - 1;
  const k5BitMask = (1 << 5) - 1;
  const k6BitMask = (1 << 6) - 1;
  const k7BitMask = (1 << 7) - 1;
  const k8BitMask = (1 << 8) - 1;
  const k16BitMask = (1 << 16) - 1;

  const kSurrogateBits = 10;

  const kHighSurrogateMin = 0xD800;
  const kHighSurrogateMax = 0xDBFF;
  const kHighSurrogateMask = (1 << kSurrogateBits) - 1;

  const kLowSurrogateMin = 0xDC00;
  const kLowSurrogateMax = 0xDFFF;
  const kLowSurrogateMask = (1 << kSurrogateBits) - 1;

  const kSurrogateMin = kHighSurrogateMin;
  const kSurrogateMax = kLowSurrogateMax;
  const kSurrogateMask = (1 << (kSurrogateBits + 1)) - 1;

  const kHighSurrogateOffset = kHighSurrogateMin - (0x10000 >> 10);

  const kUnicodeMin = 0x000000;
  const kUnicodeMax = 0x10FFFF;

  const kUTF16Min = 0x0000;
  const kUTF16Max = 0xFFFF;

  const kUCS2Min = 0x0000;
  const kUCS2Max = 0xFFFF;

  const kUCS4Min = 0x00000000;
  const kUCS4Max = 0x7FFFFFFF;

  const INVALID_SEQUENCE = "Invalid Sequence";
  const NOT_ENOUGH_SPACE = "No Enough Space";

  function IsTrail(ch) {
    // UTF8 String (not 1st) should be 10xxxxxx (UTF8-tail)
    // 0xC0 => (11000000) 0x80 => (10000000)
    return (ch & 0xC0) == 0x80;
  }

  function Get1CodePoint(view, pos, last) {
    if (pos != last) {
      return view[pos] & k8BitMask;
    }
    throw new Error(NOT_ENOUGH_SPACE);
  }

  function Get2CodePoint(view, pos, last) {
    const kMin = 0x80;  // 2 bytes => 0000000010000000
    if (pos != last) {
      // remove size bits from 1st byte
      // 110xxxxx
      var res = (view[pos++] & k5BitMask) << 6;
      if (pos != last) {
        if (IsTrail(view[pos])) {
          // max value is 11111111111 => 2047 => 0x7FF
          // so no check out of range: max
          res = res | (view[pos] & k6BitMask);
          if (res >= kMin) {
            return res;
          } else {
            throw new Error(INVALID_SEQUENCE);
          }
        } else {
          throw new Error(INVALID_SEQUENCE);
        }
      } else {
        throw new Error(NOT_ENOUGH_SPACE);
      }
    } else {
      throw new Error(NOT_ENOUGH_SPACE);
    }
  }

  function Get3CodePoint(view, pos, last) {
    const kMin = 0x00000800;  // 3 bytes => 0000100000000000
    if (pos != last) {
      // remove size bits from 1st byte
      // 1110xxxx
      var res = (view[pos++] & k4BitMask) << 12;
      if (pos != last) {
        if (IsTrail(view[pos])) {
          res = res | (view[pos++] & k6BitMask) << 6;
          if (pos != last) {
            if (IsTrail(view[pos])) {
              // max value is 1111111111111111 => 0xFFFF
              // so no check out of range: max
              res = res | (view[pos] & k6BitMask);
              if (res >= kMin) {
                // and if res in surrogate range, this code is invalid.
                if (res < kSurrogateMin || kSurrogateMax < res) {
                  return res;
                } else {
                  throw new Error(INVALID_SEQUENCE);
                }
              } else {
                throw new Error(INVALID_SEQUENCE);
              }
            } else {
              throw new Error(INVALID_SEQUENCE);
            }
          } else {
            throw new Error(NOT_ENOUGH_SPACE);
          }
        } else {
          throw new Error(INVALID_SEQUENCE);
        }
      } else {
        throw new Error(NOT_ENOUGH_SPACE);
      }
    } else {
      throw new Error(NOT_ENOUGH_SPACE);
    }
  }

  function Get4CodePoint(view, pos, last) {
    const kMin = 0x00010000;  // 4 bytes => surrogate pair only
    if (pos != last) {
      // remove size bits from 1st byte
      // 11110xxx
      var res = (view[pos++] & k3BitMask) << 18;
      if (pos != last) {
        if (IsTrail(view[pos])) {
          res = res | (view[pos++] & k6BitMask) << 12;
          if (pos != last) {
            if (IsTrail(view[pos])) {
              res = res | (view[pos++] & k6BitMask) << 6;
              if (pos != last) {
                if (IsTrail(view[pos])) {
                  // max value is 111111111111111111111 => 0x1FFFFF
                  // so must check this value is in surrogate pair range
                  res = res | (view[pos] & k6BitMask);
                  if (res >= kMin) {
                    if (res <= kUnicodeMax) {
                      return res;
                    } else {
                      throw new Error(INVALID_SEQUENCE);
                    }
                  } else {
                    throw new Error(INVALID_SEQUENCE);
                  }
                } else {
                  throw new Error(INVALID_SEQUENCE);
                }
              } else {
                throw new Error(NOT_ENOUGH_SPACE);
              }
            } else {
              throw new Error(INVALID_SEQUENCE);
            }
          } else {
            throw new Error(NOT_ENOUGH_SPACE);
          }
        } else {
          throw new Error(INVALID_SEQUENCE);
        }
      } else {
        throw new Error(NOT_ENOUGH_SPACE);
      }
    } else {
      throw new Error(NOT_ENOUGH_SPACE);
    }
  }

  function UTF8ByteCount(ch) {
    return kLengthArray[ch];
  }

  function IsHighSurrogate(uc) {
    return ((uc) & ~kHighSurrogateMask) == kHighSurrogateMin;
  }

  function IsLowSurrogate(uc) {
    return ((uc) & ~kLowSurrogateMask) == kLowSurrogateMin;
  }

  function IsSurrogate(uc) {
    return ((uc) & ~kSurrogateMask) == kSurrogateMin;
  }

  function DecodeSurrogatePair(high, low) {
    return ((high & kHighSurrogateMask) << kSurrogateBits) + (low & kLowSurrogateMask) + 0x10000;
  }

  function ToHighSurrogate(uc) {
    return (uc >> kSurrogateBits) + kHighSurrogateOffset;
  }

  function ToLowSurrogate(uc) {
    return (uc & kLowSurrogateMask) + kLowSurrogateMin;
  }

  const parseFunctionTable = [
    null,
    Get1CodePoint,
    Get2CodePoint,
    Get3CodePoint,
    Get4CodePoint
  ];

  function NextUCS4FromUTF8(view, pos, last, result_place) {
    const len = kLengthArray[view[pos]];
    if (len == 0) {
      throw new Error(INVALID_SEQUENCE);
    }

    result_place[0] = parseFunctionTable[len](view, pos, last);
    return pos + len;
  }

  function UTF8ToUTF16Array(view, pos, last) {
    var buffer = [];
    var result_place = [];
    while (pos != last) {
      pos = NextUCS4FromUTF8(view, pos, last, result_place);
      var res = result_place[0];
      if (res > 0xFFFF) {
        buffer.push(ToHighSurrogate(res), ToLowSurrogate(res));
      } else {
        buffer.push(res);
      }
    }
    return buffer;
  }

  function UTF8ToUTF16(view, pos, last) {
    var ary = UTF8ToUTF16Array(view, pos, last);
    for (var i = 0, len = ary.length; i < len; ++i) {
      ary[i] = String.fromCharCode(ary[i]);
    }
    return ary.join('');
  }

  function Append(uc, buffer) {
    if (uc < 0x80) {
      // 0000 0000-0000 007F | 0xxxxxxx
      buffer.push(uc);
    } else if (uc < 0x800) {
      // 0000 0080-0000 07FF | 110xxxxx 10xxxxxx
      buffer.push(((uc >> 6) | 0xC0), ((uc & 0x3F) | 0x80));
    } else if (uc < 0x10000) {
      // 0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
      buffer.push(((uc >> 12) | 0xE0), (((uc >> 6) & 0x3F) | 0x80), ((uc & 0x3F) | 0x80));
    } else {
      // 0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
      buffer.push(
        ((uc >> 18) | 0xF0),
        (((uc >> 12) & 0x3F) | 0x80),
        (((uc >> 6) & 0x3F) | 0x80)
        ((uc & 0x3F) | 0x80));
    }
  }

  function UTF16ArrayToUTF8(view, pos, last) {
    var buffer = [];
    while (pos != last) {
      var res = (view[pos++] & k16BitMask);
      if (IsSurrogate(res)) {
        if (IsHighSurrogate(res)) {
          if (pos == last) {
            throw new Error(INVALID_SEQUENCE);
          }
          var low = (view[pos++] & k16BitMask);
          if (!IsLowSurrogate(low)) {
            throw new Error(INVALID_SEQUENCE);
          }
          res = DecodeSurrogatePair(res, low);
        } else {
          // starts with low surrogate is error
          throw new Error(INVALID_SEQUENCE);
        }
      }
      Append(res, buffer);
    }
    return buffer;
  }

  function UTF16ToUTF8(str, pos, last) {
    var buffer = new Array(str.length);
    for (var i = 0, len = str.length; i < len; ++i) {
      buffer[i] = str.charCodeAt(i);
    }
    return UTF16ArrayToUTF8(buffer, pos, last);
  }

  module.UTF8ToUTF16Array = UTF8ToUTF16Array;
  module.UTF8ToUTF16 = UTF8ToUTF16;
  module.UTF16ArrayToUTF8 = UTF16ArrayToUTF8;
  module.UTF16ToUTF8 = UTF16ToUTF8;
})(this);

//  if (typeof Uint8Array !== 'undefined') {
//    var buffer = new Uint8Array([227, 129, 147, 227, 130, 147, 227, 129, 171, 227, 129, 161, 227, 129, 175]);
//  } else {
//    var buffer = [227, 129, 147, 227, 130, 147, 227, 129, 171, 227, 129, 161, 227, 129, 175];
//  }
//  var str = UTF8ToUTF16(buffer, 0, buffer.length);
//  var utf8 = UTF16ToUTF8(str, 0, str.length);
//  var str2 = UTF8ToUTF16(utf8, 0, utf8.length);

Google Chrome上でのv8, 及び自作engineのlv5で動作を確認しました.

試してみましょう!

まず, おもむろにGoogle Chromeで「ロッテのおもちゃ！」の公式ページを開きまして TVアニメ『アスタロッテのおもちゃ！』公式サイト 上記scriptと以下のscriptをconsoleに貼り付けます. すると,

function request(type, callback) {
  var xhr = new XMLHttpRequest();
  xhr.open('GET', 'http://www.rotte-omocha.com/', false);  // ロッテのおもちゃ！
  if (type) {
    xhr.responseType = type;
  }
  xhr.onload = function() {
    callback(xhr);
  }
  xhr.send();
}
request('arraybuffer', function onLoad(res) {
  var buffer = res.response;
  var view = new Uint8Array(buffer);
  var result1 = UTF8ToUTF16(view, 0, view.length);
  request(null, function onLoad2(res) {
    var result2 = res.responseText;
    console.log(result1 === result2);
  });
});

何をやっているかは明白ですね. XHRでArrayBufferで取得し, それをUint8ArrayのviewからUTF-16文字列に変換, XHRでresponseTextで取得したものと同じであるかを確認しています.

このtrueは大きな意味がありますね!!!

参考

RFCの邦訳. ありがたいです.

RFC日本語化計画

非常に分かりやすく, 大変参考になりました. ありがとうございます.

文字コードに関する覚え書きと実験

補足

RFC, 意外に短く, 分かりやすくてとてもいいですね.