Subscribed unsubscribe Subscribe Subscribe

枕を欹てて聴く

香炉峰の雪は簾を撥げて看る

vs UTF-8, UTF-16, UCS4

前置き

おはミルキィ! 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-16UTF-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で取得したものと同じであるかを確認しています.
f:id:Constellation:20110530033958p:image
このtrueは大きな意味がありますね!!!

参考

RFCの邦訳. ありがたいです.
RFC日本語化計画
非常に分かりやすく, 大変参考になりました. ありがとうございます.
文字コードに関する覚え書きと実験

補足

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